Edges in a 2D digital image are lines (or surfaces in 3D) where image intensity
changes abruptly (discontinuously). Edge detection is a fundamental step in
2D image processing, image analysis, pattern recognition, and computer vision.
The purpose of 2D edge detection is to create an edge map that may be used
to separate (segment) the image into subsets that belong to different meaningful
components.
The currently available edge detection methods can be roughly divided into two
groups: search-based and zero-crossing based. The search-based methods detect
edges by estimating the edge strength as a first-order derivative (gradient
magnitude and direction) and finding a directional maximum. The zero-crossing
based methods search for zeros in a second-order derivative.
For digital images, gradients (partial derivatives) can be estimated as images
of differences between the intensities of adjacent pixels in a given direction.
Thus, the x-direction gradient can be estimated from pixel intensities S as
S(i+1,j,k)–S(i,j,k). However, this approach is not robust to image noise, because
noise is magnified when differences between pixels are computed. FireVoxel uses
a different approach to defining the gradient, better suited to medical images.
In FireVoxel, several commands and operations perform edge detection
or include it as a component of their algorithms, mainly to perform
segmentation and delineate image structures:
FireVoxel’s unique edge detection algorithm is based on the continuous half-sphere
design. Consider a disk of radius r centered on a given pixel in 2D, or a sphere around
a voxel in 3D (Fig. 16.1). Note that the center of the disk or sphere
is positioned at the vertex of the voxel rather than voxel center.
The diameter splits this disk into two halves A and B (or a plane splits the sphere in 3D
into two hemispheres).
Fig. 16.1 Disk divided by “compass needle” into two halves, A and B.
The direction and magnitude of the gradient may be determined by finding the (A, B) split
with the greatest difference between the halves. This is achieved by “spinning the compass
needle” and considering all (infinite) possible orientations of the (A,B) split. For an image
made of discrete voxels, there is a limited number of unique ways the voxels inside the
disk/sphere can be divided between the two halves. Each such split produces a unique gradient
orientation, along the vector from the center of the sphere to the center of mass of all voxels
in one hemisphere. The gradient magnitude is the edge strength, defined (in the simplest case)
as the difference between the average signal in the two halves:
E = avg(A)–avg(B).
Note that this definition is more robust than digital x-directional gradient.
The radius of the disk/sphere determines the characteristic size (level) of the image features
probed by the edge detector. However, the number of the unique (A, B) splits grows steeply with
the radius. For example, for a sphere with r=3 voxels (as in Figure 1), there are 1053 possible
splits. For a sphere with r=4, the number of splits is already X. Thus, selecting a larger radius
may significantly increase the computation time.
Fig. 16.2 Compass operator of Ruzon and Tomasi dividing the disk into wedges.
The compass operator with the “spinning needle” was first introduced by Ruzon and Tomasi
(Ruzon 1999) to detect step edges by splitting the circle into a finite number
of wedges (Fig. 16.2). FireVoxel’s algorithm incorporates two significant
innovations over the original compass operator: a) generalization to 3D, and b) fully
continuous implementation of the spinning plane.
The signal distributions in the two hemispheres are compared using the distance metrics.
FireVoxel offers two distance metrics: signal difference and Earth Mover Distance (EMD)
(Rubner 2000). The EMD was an innovative feature of the compass operator edge detector, and
FireVoxel retains this feature. The EMD method is sensitive to image texture, which describes
the spatial variation of the image intensity and color. EMD is thus well-suited for medical
images, which are typically rich in subtle detail.
EMD yields at each voxel a texture-sensitive gradient with the magnitude equal to the largest
EMD between the histograms. FireVoxel considers voxels with only one signal component (signal
intensity), which substantially simplifies the definition of the EMD for radiological images.
In this case, EMD measures the distance between two histograms, in which each bin corresponds
to a single unit of the signal intensity for integer-valued voxels. Real-valued volumes are
first discretized to 16-bit integer volumes, which can then use the same EMD definition.
The signal difference method accounts only for the difference between intensity and is not
sensitive to texture. However, it is substantially faster than EMD and may therefore be
preferable in some cases.
For both metrics, the direction of the vector normal to the splitting plane is also available
and can be used to generate vector gradient fields. The direction of the gradient is used
for 3D non-maxima suppression, an essential part of any edge detector similar to 2D non-maxima
suppression in Canny edge detector. For the EMD metric, the calculated distance is a scalar,
and while the 3D axis of the gradient is known, it does not have a direction. For EMD,
the gradient direction is determined as for the signal difference, but the gradient magnitude
is equal to the EMD.
Note that FireVoxel’s edge detector is superior to the Canny edge detector even in
the signal-difference mode. In the Canny edge detector, Gaussian smoothing is first applied to
the image before gradients are determined and edges are tracked. This Gaussian smoothing blurs
the subtle boundaries often found in medical images (e.g., between adjacent organs) and the exact
position of the edge becomes imprecise. In contrast, in FireVoxel the edge detector does not
contain the smoothing step, and the edges can accurately follow even subtle boundaries.
