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.
 Sobel3x3 |
 Prewitt3x3 |
Parameters 
and 
are angular frequencies along horizontal and vertical directions correspondingly. Lower values of and 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 combinations. To be noise robust filter should set to zero high frequencies and tend to 
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 
:
![<br />
\displaystyle{\frac{1}{32}}\left[\begin{matrix}<br />
-1&-2&0&2&1\\<br />
-2&-4&0&4&2\\<br />
-1&-2&0&2&1<br />
\end{matrix}\right]<br />](http://www.holoborodko.com/pavel/wp-content/ql-cache/quicklatex-65bbc80375d6f9691357be45df428f10.gif "<br />
\displaystyle{\frac{1}{32}}\left[\begin{matrix}<br />
-1&-2&0&2&1\\<br />
-2&-4&0&4&2\\<br />
-1&-2&0&2&1<br />
\end{matrix}\right]<br />")
![<br />
\displaystyle{\frac{1}{512}}<br />
\left[\begin{array}{ccccccc}<br />
-1&-4&-5&0&5&4&1 \\ \noalign{\medskip}<br />
-4&-16&-20&0&20&16&4 \\ \noalign{\medskip}<br />
-6&-24&-30&0&30&24&6 \\ \noalign{\medskip}<br />
-4&-16&-20&0&20&16&4 \\ \noalign{\medskip}<br />
-1&-4&-5&0&5&4&1<br />
\end{array}\right]<br />](http://www.holoborodko.com/pavel/wp-content/ql-cache/quicklatex-a50c148b1e724650b29f6708f362fa3b.gif "<br />
\displaystyle{\frac{1}{512}}<br />
\left[\begin{array}{ccccccc}<br />
-1&-4&-5&0&5&4&1 \\ \noalign{\medskip}<br />
-4&-16&-20&0&20&16&4 \\ \noalign{\medskip}<br />
-6&-24&-30&0&30&24&6 \\ \noalign{\medskip}<br />
-4&-16&-20&0&20&16&4 \\ \noalign{\medskip}<br />
-1&-4&-5&0&5&4&1<br />
\end{array}\right]<br />")
To calculate 
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.
 NRIGO5x3 |
 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.
(7 votes, average: 4.86)
Loading ...
8 Comments
Very interesting work. How would you extend this result to 3D?
It is possible to extend this work for 3D data. I’ll explain details via e-mail.
I don’t know how you derived your masks but it seems they don’t demonstrate good rotation invariantce. According to my experiments, your NRIGO5x3 are worse than the 3×3 Scharr masks.
omg
1
std Sobel is (-1 0 1) * ( 2 )
1
1
and your 5 x 3 is (-1 0 1) * ( 1 2 1 ) * ( 2 )
1
so you just did extra smoothing
and “respecting my authorship” sounds ridiculous
You have made several obvious mistakes.
#1
You cannot get 3×5 matrix from multiplication of 3×3 matrices.
#2
You messed up with the order of matrices in you product.
(multiplication of one row matrix by one column matrix is a number,
not a matrix).
Correct factorization of NRIGO5x3 is:
where [-1 -2 0 2 1] is differentiator with noise suppression.
So, NRIGO combines smoothing filter and smoothing differentiation in one operation.
oh, i didnt mean multiplication
i ment a sequence of convolutions
if u need more accurate notation i can rewrite my post in this way
convolution with std Sobel kernel
-1 0 1
-2 0 2
-1 0 1
is equivalent to a sequence of convolutions
1) with
-1 0 1
so we get dervtive w.r.t. x
2) and then with
1
2
1
its spational smoothness
convolution with ur
-1 -2 0 2 1
-2 -4 0 4 2
-1 -2 0 2 1
is equivalent to a sequence of convolutions
1) with
-1 0 1
so we get dervtive w.r.t. x
2) then with
1 2 1
3) and finally with
1
2
1
in other words convolution with
-1 -2 0 2 1
is equivalent to a sequence of convolutions
1) with
-1 0 1
2) then with
1 2 1
SO, ur “NRIGO” just does extra smoothing
nothing else
no offense, Pavel
i dont want to say, that this NRIGO is stupid or useless
i just mean there is nothing unique
and a few words about NRIGO’s pros and cons
if u use it for very smooth regions, it will “combine isotropic noise suppression and precise gradient estimation”
but for nonsmooth regions, e.g. regions with edges, such smoothing will result in loss of accuracy of gradient estimation
2D sobel Operator in x and y axis is
-1 0 1 Horizontal Gradient Operator
-2 0 2
-1 0 1
-1 -2 -1 Vertical Gradient Operator
0 0 0
1 2 1
for the above operator, the equavalent equation is to calculate gradient–
Gx(i, j)=Images(i+1,j-1)+2*Images(i+1,j)+Images(i+1,j+1)-(Images(i-1,j-1)+2*Images(i-1,j)+Images(i-1,j+1));
Gy(i, j)=Images(i-1,j+1)+2*Images(i,j+1)+Images(i+1,j+1)-(Images(i-1, j-1)+2*Images(i,j-1)+Images(i+1,j-1));
But my question is -
what will be operator and equation for 3D images?