Noise Robust Gradient Operators

This page is about efficient gradient operators which combine isotropic noise suppression and precise partial derivatives estimation. They are targeted for applications where differentiation of discrete 2D surface is required: feature/edge detection in image, coordinate measurement machine data processing, etc.

Gradient operator uses linear combination of neighboring points/pixels to approximate partial derivatives at any given point of the discrete surface. Set of coefficients is called filter.

There are several widely used filters – Sobel, Prewitt, Roberts. All of them are based on forward or central differences. Although these numerical methods have favorable theoretical properties, they can be inaccurate in the presence of noise as shown on central differences page.

Digital data derived from real world signals contain noise inherently. Which means that reliable and robust gradient operator should poses important property of noise suppression. One more desired property is to process 2D data isotropically, i.e. remove noise along all directions identically.

Frequency domain is valuable tool to research properties of discrete filters. Let’s consider frequency response of popular Sobel and Prewitt filters to investigate their noise suppression capabilities.

Sobel

Sobel3x3

Prewitt

Prewitt3x3

Parameters w_1 and w_2 are angular frequencies along horizontal and vertical directions correspondingly. Lower values of w_1 and w_2 represent smooth regions in data. Higher indicate regions with abrupt changes which most likely corrupted by noise. Surface plot shows how filter processes particular frequencies and their combination. To be noise robust filter should set to zero high frequencies and tend to 1 near lowest. To be isotropic frequency response’s contour lines should be close to circle with the center at origin.

From these plots we can see that Prewitt filter doesn’t have noise suppression at all. Whereas Sobel has weak noise suppression and it is not isotropic.

I propose 2D differentiating filters which combine isotropic noise suppression and precise gradient estimation in the same time (analogous filters for 1D explained in smooth noise-robust differentiators article). Here are the masks for {{\partial f}/{\partial x}}:

    \[ \displaystyle{\frac{1}{32}}\left[\begin{matrix} -1&-2&0&2&1\\ -2&-4&0&4&2\\ -1&-2&0&2&1 \end{matrix}\right] \]

    \[ \displaystyle{\frac{1}{512}} \left[\begin{array}{ccccccc} -1&-4&-5&0&5&4&1     \\ \noalign{\medskip} -4&-16&-20&0&20&16&4 \\ \noalign{\medskip} -6&-24&-30&0&30&24&6 \\ \noalign{\medskip} -4&-16&-20&0&20&16&4 \\ \noalign{\medskip} -1&-4&-5&0&5&4&1 \end{array}\right] \]

To calculate {{\partial f}/{\partial y}} just rotate mask by 90 degrees. As you can see these filters have efficient computational structure – they fit perfectly for fixed point arithmetic. Frequency responses are plotted below.

5x3

NRIGO5x3

7x5

NRIGO7x5

Disclaimer

You can use materials from this site in any legal activity (research, teaching, engineering, etc.) freely on the basis of respecting my authorship by giving clear statement and reference to my site or particular page on it in your work. Brief description of your project is welcome in the comments below. One point though, if you use my materials in commercial project please consider supporting my site and me by donation.


1 Star2 Stars3 Stars4 Stars5 Stars (15 votes, average: 4.93)
Loading...

12 Comments

  1. Audrius
    Posted October 2, 2009 at 4:15 am | #

    Very interesting work. How would you extend this result to 3D?

    • Posted October 4, 2009 at 8:49 pm | #

      It is possible to extend this work for 3D data. I’ll explain details via e-mail.

      • Nicolas Boulant
        Posted March 1, 2012 at 12:44 am | #

        Hi Pavel,

        Regarding the noise-robust gradient operators, I’d be interested in having the masks in 3D as well. Apparently, somebody asked you the question already. You replied that you would explain the details by email.

        Thanks for your help.

        Nick

      • Laurence D Marks
        Posted January 11, 2021 at 9:27 am | #

        I am also interested in the 3d case

  2. Posted May 18, 2011 at 5:01 am | #

    First of all, thank you.

    I am using your work in my research. I was wondering if there is any paper that I could cite?

    • Posted May 18, 2011 at 10:04 am | #

      Thank you for your feedback,

      Please site this webpage in your paper.

      Record in .bib file:


      @misc{NRIGO,
      Author = {Pavel Holoborodko},
      Title = {Noise Robust Gradient Operators.},
      howpublished = {\url{http://www.holoborodko.com/pavel/image-processing/edge-detection/}}
      year = {2009}
      }

      in LaTeX document preamble:
      \usepackage{url}

      If url package is not acceptable please check this page for other methods on websites referencing:
      http://win.ua.ac.be/~nschloe/content/bibtex-how-cite-website

      Thanks,
      Pavel.

  3. Posted May 20, 2011 at 2:12 am | #

    Thanks for the bibTex record.

  4. Jan
    Posted October 24, 2012 at 5:56 pm | #

    Hi Pavel,

    I’m very much interested in your smoothing differentiator techniques. I’ve already implemented them for the central part of my data (image). Can you elaborate on how to treat the edges of the domain? I know you’ve presented some one-sided differentiators, but currently I did not manage to extend these to this 2D mask.

    Gr. J.

  5. Posted February 11, 2016 at 12:00 am | #

    Hi Pavel,

    Thanks for this beautiful work. Could you tell me how to construct a 2D filter of arbitrary size? As you do for the 1D schemes on your other page.

    Best regards,
    KG

  6. Alexis
    Posted July 28, 2017 at 3:51 am | #

    Pavel.

    This work is really important and incredible. Thank you for creating it.

    Are you not interested in publishing this as a formal scientific article?! I think it would make for a very high-utility foundational paper, and many people would cite you in their articles when they use this (even if you don’t care about recognition per se, it’s good for academic jobs, etc)!

    Anyway, thank you again and all best wishes,

    Alexis

    • Posted July 28, 2017 at 11:31 am | #

      Dear Alexis,

      I am the most grateful for your feedback, support and advice. Thank you!
      I have been thinking about scientific article (other people advise this too), but I am afraid this will not happen soon.
      I am just software engineer. Probably I have to switch to academic world to make this happen :).

      If it is OK, for the time being please cite the web-page, e.g.:

      @misc{NRIGO,
      Author = {Pavel Holoborodko},
      Title = {Noise Robust Gradient Operators.},
      howpublished = {\url{http://www.holoborodko.com/pavel/image-processing/edge-detection/}}
      year = {2009}
      }

  7. Posted April 25, 2018 at 6:55 pm | #

    Hey Pavel,

    First of all thank you a lot for the article on the noise-free derivative. I’m currently using this to calculate my resulting forces from a given potential function V(x). This in order to do some form of molecular dynamics. The potential itself is at some points a little bit noisy due to numerical errors.

    The idea now is to extend this potential to involve more parameters, so: V(x,y,z). Since I now have a 3D derivative, I too am interested in the 3D mask. Is there any way to obtain this? Also for the derivation, are there any hints on how to easily expand the 1D derivation to the 2D and 3D case?

    Cheers,
    Nick

Post a Comment

Your email is never published nor shared.

Use native LaTeX syntax to include formulas: $ ... $, \[ ... \], etc. Do not forget to preview comment before posting.

Also you may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Subscribe without commenting