16. Texture Edge Detection

16.1. About edge detection

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.

16.2. FireVoxel commands with texture edge detection

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:

16.3. FireVoxel’s edge detection algorithm

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).

Compass operator illustration

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.

Compass operator Ruzon and Tomasi

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.

16.4. Distance metrics: Signal difference and Earth Mover Distance

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.