Difference between revisions of "Edge Detection: Zero X Non-Maximum Suppression"
(→Background) |
(→Background) |
||
Line 14: | Line 14: | ||
For a 2D image, let's introduce a local coordinate system (u, v) such that at any point in the image P''0''(x''0'',y''0'') v-axis is parallel to the gradient direction at (x''0'',y''0'') and the u-axis is perpendicular to it, i.e., | For a 2D image, let's introduce a local coordinate system (u, v) such that at any point in the image P''0''(x''0'',y''0'') v-axis is parallel to the gradient direction at (x''0'',y''0'') and the u-axis is perpendicular to it, i.e., | ||
− | Equation | + | Equation 1 <div align "left> </div> </br> |
Line 24: | Line 24: | ||
|} | |} | ||
− | <br / | + | <br /> |
Where L is a convolution of an image (represented as a function ''f(x,y'') with the Gaussian kernel defined as: | Where L is a convolution of an image (represented as a function ''f(x,y'') with the Gaussian kernel defined as: | ||
+ | Equation 2 <div align "left> </div> | ||
− | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 37: | Line 37: | ||
|} | |} | ||
− | <br / | + | <br /> |
so that | so that | ||
− | <div | + | Equation 3 <div align "left> </div> |
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 50: | Line 51: | ||
|} | |} | ||
− | <br / | + | <br /> |
where the circle represents convolution of g(x,y;t) and'' f''(x,y) and semicolon in the argument of g implies that the convolution is performed only over the variables x and y, while the scale parameter ''t'' after the semicolon just indicates which scale-space level is being defined. Directional derivatives in this local (u,v) system are related to partial derivatives in the Cartesian coordinate system by the following system of equations, | where the circle represents convolution of g(x,y;t) and'' f''(x,y) and semicolon in the argument of g implies that the convolution is performed only over the variables x and y, while the scale parameter ''t'' after the semicolon just indicates which scale-space level is being defined. Directional derivatives in this local (u,v) system are related to partial derivatives in the Cartesian coordinate system by the following system of equations, | ||
− | <div | + | Equation 4 <div align "left> </div> |
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 63: | Line 65: | ||
|} | |} | ||
− | <br / | + | <br /> |
where, at a given point P''0'' | where, at a given point P''0'' | ||
− | <div | + | Equation 5 <div align "left> </div> |
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 76: | Line 79: | ||
|} | |} | ||
− | <br /> | + | <br /> |
− | + | ||
And this (u,v) coordinate system is characterized by the fact that one of the two first-order derivatives -L''u'', is zero, e.g. | And this (u,v) coordinate system is characterized by the fact that one of the two first-order derivatives -L''u'', is zero, e.g. | ||
− | <div | + | Equation 6 <div align "left> </div> |
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 89: | Line 92: | ||
|} | |} | ||
− | <br /> < | + | <br /> |
+ | Equation 7 <div align "left> </div> | ||
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 98: | Line 103: | ||
|} | |} | ||
− | <br /> < | + | <br /> |
+ | Equation 8 <div align "left> </div> | ||
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 107: | Line 114: | ||
|} | |} | ||
− | <br / | + | <br /> |
Below, are equations used in the method for calculating the second and third derivative - L''vv'' and L''vvv''. | Below, are equations used in the method for calculating the second and third derivative - L''vv'' and L''vvv''. | ||
− | <div | + | Equation 9 <div align "left> </div> |
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 120: | Line 128: | ||
|} | |} | ||
− | <br /> < | + | <br /> |
+ | Equation 10 <div align "left> </div> | ||
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 129: | Line 139: | ||
|} | |} | ||
− | <br /> < | + | <br /> |
+ | Equation 11 <div align "left> </div> | ||
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 138: | Line 150: | ||
|} | |} | ||
− | <br /> < | + | <br /> |
+ | Equation 12 <div align "left> </div> | ||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 147: | Line 160: | ||
|} | |} | ||
− | <br /> < | + | <br /> |
+ | Equation 13<div align "left> </div> | ||
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 163: | Line 178: | ||
** And the third-order directional derivative in the same direction L''vvv'' being'' ''negative, e.g.: | ** And the third-order directional derivative in the same direction L''vvv'' being'' ''negative, e.g.: | ||
− | <div | + | Equation 14 <div align "left> </div> |
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 172: | Line 188: | ||
|} | |} | ||
− | <br / | + | <br /> |
Since only the sign information is important, these conditions can be restated as: | Since only the sign information is important, these conditions can be restated as: | ||
− | <div | + | Equation 15 <div align "left> </div> |
+ | |||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
Line 185: | Line 202: | ||
|} | |} | ||
− | <br / | + | <br /> |
Here, L is the scale-space representation of an image ''f''(x,y;t) at a certain scale t, and the last equation defines the edges of ''f'' at that scale. | Here, L is the scale-space representation of an image ''f''(x,y;t) at a certain scale t, and the last equation defines the edges of ''f'' at that scale. | ||
− | This condition can also be formulated in terms of zero-crossings of the partial derivative of ''L'' with respect to the scale parameter (i.e., as a directional derivative in the vertical scale direction). For more information about the zero-crossings method for detecting edges used in MIPAV, refer to MIPAV User Manual, Volume 2, Algorithms, [Edge_Detection_Zero_X.html#wp1005679 | + | This condition can also be formulated in terms of zero-crossings of the partial derivative of ''L'' with respect to the scale parameter (i.e., as a directional derivative in the vertical scale direction). For more information about the zero-crossings method for detecting edges used in MIPAV, refer to MIPAV User Manual, Volume 2, Algorithms, [[Edge_Detection_Zero_X.html#wp1005679|Edge Detection: Zero X Laplacian]]. |
− | The method evaluates detected zero-crossings using the Marching Squares algorithm to determine only those zero-crossings that corresponds to edges. To learn more about the Marching Squares algorithm, refer to MIPAV User Manual, Volume 2, Algorithms, [MarchingCubes.html#wp999048 | + | The method evaluates detected zero-crossings using the Marching Squares algorithm to determine only those zero-crossings that corresponds to edges. To learn more about the Marching Squares algorithm, refer to MIPAV User Manual, Volume 2, Algorithms, [[MarchingCubes.html#wp999048|Extract Surface (Marching Cubes)]]. |
The resulting image is an unsigned byte image with values of 255 at the edges and 0 elsewhere. | The resulting image is an unsigned byte image with values of 255 at the edges and 0 elsewhere. | ||
Line 198: | Line 215: | ||
{| border="1" cellpadding="5" | {| border="1" cellpadding="5" | ||
− | |+ <div>'''Figure | + | |+ <div>'''Figure 1. The original image and its unsigned byte mask with detected edges.''' </div> |
|- | |- | ||
| | | | ||
− | <div style="font-style: normal; font-weight: normal; margin-bottom: 0pt; margin-left: 0pt; margin-right: 0pt; margin-top: 1pt; text-align: left; text-decoration: none; text-indent: 0pt; text-transform: none; vertical-align: baseline"><font size="2pt"><font color="#000000"><div><center>[[Image:EdgeDetNonMAxSupprOriginal.jpg]]</center></div><br / | + | <div style="font-style: normal; font-weight: normal; margin-bottom: 0pt; margin-left: 0pt; margin-right: 0pt; margin-top: 1pt; text-align: left; text-decoration: none; text-indent: 0pt; text-transform: none; vertical-align: baseline"><font size="2pt"><font color="#000000"><div><center>[[Image:EdgeDetNonMAxSupprOriginal.jpg]]</center></div><br /> |
| | | | ||
− | <div style="font-style: normal; font-weight: normal; margin-bottom: 0pt; margin-left: 0pt; margin-right: 0pt; margin-top: 1pt; text-align: left; text-decoration: none; text-indent: 0pt; text-transform: none; vertical-align: baseline"><font size="2pt"><font color="#000000"><div><center>[[Image:EdgeDetNonMAxSupprResultl.jpg]]</center></div><br / | + | <div style="font-style: normal; font-weight: normal; margin-bottom: 0pt; margin-left: 0pt; margin-right: 0pt; margin-top: 1pt; text-align: left; text-decoration: none; text-indent: 0pt; text-transform: none; vertical-align: baseline"><font size="2pt"><font color="#000000"><div><center>[[Image:EdgeDetNonMAxSupprResultl.jpg]]</center></div><br /> |
|} | |} | ||
− | + | ||
==== Image types ==== | ==== Image types ==== |
Revision as of 20:18, 2 February 2012
Contents
Edge Detection: Zero X Non-Maximum Suppression
This method produces an edge map of the zero-crossings of the non-maximum suppression for 2D and 2.5D images. Edges are defined as the union of points for which the gradient magnitude assumes a maximum in the gradient direction.
Background
For a 2D image, let's introduce a local coordinate system (u, v) such that at any point in the image P0(x0,y0) v-axis is parallel to the gradient direction at (x0,y0) and the u-axis is perpendicular to it, i.e.,
Equation 1
Where L is a convolution of an image (represented as a function f(x,y) with the Gaussian kernel defined as:
Equation 2
so that
Equation 3
where the circle represents convolution of g(x,y;t) and f(x,y) and semicolon in the argument of g implies that the convolution is performed only over the variables x and y, while the scale parameter t after the semicolon just indicates which scale-space level is being defined. Directional derivatives in this local (u,v) system are related to partial derivatives in the Cartesian coordinate system by the following system of equations,
Equation 4
where, at a given point P0
Equation 5
And this (u,v) coordinate system is characterized by the fact that one of the two first-order derivatives -Lu, is zero, e.g.
Below, are equations used in the method for calculating the second and third derivative - Lvv and Lvvv.
Equation 9
</font></font></div>
According to the notion of non-maximum suppression, an edge point is defined as a point at which the gradient magnitude assumes a maximum in the gradient direction. In terms of directional derivatives, such definition can be also expressed as a combination of two conditions:
- The second-order directional derivative in the v-direction Lvv being zero;
- And the third-order directional derivative in the same direction Lvvv being negative, e.g.:
Since only the sign information is important, these conditions can be restated as:
Equation 15
Here, L is the scale-space representation of an image f(x,y;t) at a certain scale t, and the last equation defines the edges of f at that scale.
This condition can also be formulated in terms of zero-crossings of the partial derivative of L with respect to the scale parameter (i.e., as a directional derivative in the vertical scale direction). For more information about the zero-crossings method for detecting edges used in MIPAV, refer to MIPAV User Manual, Volume 2, Algorithms, Edge Detection: Zero X Laplacian.
The method evaluates detected zero-crossings using the Marching Squares algorithm to determine only those zero-crossings that corresponds to edges. To learn more about the Marching Squares algorithm, refer to MIPAV User Manual, Volume 2, Algorithms, Extract Surface (Marching Cubes).
The resulting image is an unsigned byte image with values of 255 at the edges and 0 elsewhere.
Image types
You can apply this algorithm to 2D and 3D grayscale images.
References
Bart M. ter Haar Romeny(Ed.), "Geometry-Driven Diffusion in Computer Vision", Chapter2: Linear Scale'-'Space II: Early Visual Operations by Tony Lindeberg and Bart M. ter Haar Romeny, Kluwer Academic Publishers, 1994, pp. 39-46.
MIPAV User Manual, Volume 2, Algorithms, [Edge_Detection_Zero_X.html#wp1005679 "Edge Detection: Zero X Laplacian" ].
Tony Lindeberg [1996]. "Edge detection and ridge detection with automatic scale selection" Technical report ISRN KTH/NA/P-96/06-SE, May 1996, Revised August 1998. Int. J. of Computer Vision, vol 30, number 2, 1998. (In press). Shortened version in Proc. CVPR'96, San Francisco, June 1996. http://www.nada.kth.se/~tony
Applying the Zero X Non-Maximum Suppression algorithm
To run this algorithm, complete the following steps:
- Open an image of interest;
- Select Algorithms > Edge detection > Zero x non-maximum suppression. The EdgeNMSuppression dialog box opens. For the dialog box options, refer to [Edge_Detection_Zero_X_Non-Maxx_Suppress.html#wp1028172 Figure 20].
- Complete the fields in the dialog box. Click OK.
- The algorithm begins to run, and a status window appears. When the algorithm finishes, the resulting image appears as an unsigned byte mask in a new image window as shown in [Edge_Detection_Zero_X_Non-Maxx_Suppress.html#wp1028301 Figure 21].
Scale of the Gaussian
|
Specifies the standard deviation (from 1.0 to 10.0) of the Gaussian filter in X, Y, and Z directions which were used to determine edges in the image. Note that larger standard deviation produces an image with smaller number of edges. Smoothing the image before applying the algorithm also reduce the number of detected edges. Refer to [Edge_Detection_Zero_X_Non-Maxx_Suppress.html#wp1028301 Figure 21] for more information.
|
|
Use image resolutions to normalize Z scale
|
If checked, the following equation - Z scale*(X resolution/Z resolution) will be used to generate the edge map. If unchecked, only Z scale will be used in generation of the edge map.
| |
Process each slice independently (2.5D)
|
Applies the algorithm to each image slice individually.
| |
Destination
|
New image - this is the default option; Replace image - this option cannot be selected.
| |
Process
|
Whole Image - if checked the edge detection will be calculated for the whole image; VOI region - if checked the edge detection will be calculated for the selected VOI.
| |
OK
|
Applies the algorithm according to the specifications in this dialog box.
| |
Cancel
|
Closes the dialog box.
| |
Help
|
Displays online help for this dialog box.
| |
Figure 20. The EdgeNMSuppression dialog box options
|
a
|
b
|
c
|
d
|
e
|
f
|
Imaging Sciences Laboratory, CIT, NIH Matthew McAullife, Ph.D. mcmatt@exchange.nih.gov 301-594-2432 Building 12A, Room 2041, 9000 Rockville Pike, Bethesda, MD 20892 |