Evaluating the performance of the derivative measures

Recall that the masks derived in Appendix B are not themselves the first and second directional derivative measures needed for histogram volume calculation. The directional derivative measures rely on the masks to provide partial derivative measurement, and the partial derivatives are composed into the final directional derivative measure according to the formulas in Section 4.3. We restate the formulas for the directional derivatives here, writing out the partial derivatives where necessary. There is only one measure for the first directional derivative, the gradient magnitude:

$$\mathbf{D}_{\widehat{\nabla f}}f = \Vert\nabla f\Vert = \sqrt{\le... ...partial f}{\partial y}\right)^2 + \left(\frac{\partial f}{\partial z}\right)^2}$$ (46)

For the second directional derivative, we have three measures, the first involving the gradient of the gradient magnitude:

$$\mathbf{D}^{2}_{\widehat{\nabla f}}f = \frac{1}{\Vert\nabla f\Vert} \nabla (\Vert\nabla f\Vert) \cdot \nabla f$$ (47)

The next measure is based on the Hessian:

$$\mathbf{D}^2_{\widehat{\nabla f}}f = \frac{1}{\Vert\nabla f\Vert^2} (\nabla f)^{\mathrm T} \, \mathbf{H} f \, \nabla f$$ (48)

$$= \frac{1}{\Vert\nabla f\Vert^2} \left[ \begin{array}{c} \frac{... ...{\partial y} & \frac{\partial f}{\partial z} \end{array}\right]$$ (49)

The third and last measure, an approximation, is the Laplacian:

$$\mathbf{D}^{2}_{\widehat{\nabla f}}f \approx \nabla^{2} f = \frac... ...\frac{\partial ^2 f}{{\partial y}^{2}} + \frac{\partial ^2 f}{{\partial z}^{2}}$$ (50)

It is relatively easy to perform an analytical Fourier analysis of an individual mask in order to find its frequency response, which is useful information for determining how the mask will respond to ideal boundaries of various thicknesses[BLM96]. But what is more relevant to the problem of histogram volume calculation is determining the frequency response of the directional derivative measure as a whole. Unfortunately, due to the complexity of the directional derivative formulas in Equations C.2, C.3, and C.5, the task is outside the scope of this thesis.

Instead, we evaluate the derivative measures by using them to analyze synthetic volumes containing a range of boundary thicknesses. Specifically, we create a synthetic volume for every boundary thickness between $0.33$ and $8.0$, at increments of $0.33$. The synthetic volumes contain only planar boundaries, so we should keep in mind that the Laplacian second derivative measure will be uncharacteristically accurate, since it gives a correct directional derivative measure only for planar boundaries²¹. All the synthetic volumes were $128^3$ in size. One subtle feature of the volumes was that the boundary planes were purposely not axis aligned. This created more variation in the spatial relationship between the boundary and the sampling grid, which led to a better distribution of voxels along the curves in the scatterplots. Also, to maximize the number of voxels which accumulate along the curves in the scatterplots, multiple boundaries were created in each volume. By varying the spacing between boundaries in proportion to the boundary thickness, we maintain an approximately constant accumulation of hits along the scatterplot curves.

Figure C.1: Renderings of two of the synthetic volumes used for derivative measure performance evaluation. The volume shown in (a) has a boundary thickness of 3.00, the one in (b) has boundary thickness 6.00. Both were rendered by giving the boundary high opacity and the material interiors a very low opacity.

To provide a sense of what these synthetic volumes look like in three dimensions, Figure C.1 gives renderings of two of them, one containing boundaries with thickness 3.00, and the other with boundaries of thickness 6.00.

Three histogram volumes are then calculated for each synthetic volume. While the gradient magnitude is always used for the first directional derivative measure, each of the three different second directional derivative measures are used once. All histogram volumes were calculated at a resolution of $128^3$. These histogram volumes are then projected to create scatterplots which we can visually compare in order to gain a qualitative understanding of how the derivative measures perform for a variety of boundary thicknesses. Recall from Section 4.3 that one important issue in histogram volume calculation is the range of derivative values that should be included on the first and second derivative axes of the histogram volume. In the analysis of these synthetic volumes, for each boundary thickness, the full range of the first and second derivative values which occur within the ideal boundary was calculated, and the range of derivative values to be included in the histogram volume was set to 120% of this. This provides the basis for qualitative evaluation of the derivative measures: by comparing the ideal versus actual sizes of the curves in the scatterplots, we get a sense of how the derivative measures respond to boundaries of a given thickness.

Figures C.3, C.4, and C.5 show the results of this analysis. Each line of the table corresponds to one boundary thickness ($2\sigma$), which is written in the first column. In the next column are slices of the datasets analyzed. After the slice, from left to right, each row contains the $f'(x)$ versus $f(x)$ scatterplot, followed by the three $f''(x)$ versus $f(x)$ scatterplots, using the different second derivative measures: gradient of gradient magnitude (from Equation C.2), Hessian (Equation C.3), and Laplacian (Equation C.5). The tops of the scatterplot columns are labeled to indicate which derivative has been measured and how. The scatterplots are turned on their sides (rotated 90 degrees clockwise from their usual presentation) to facilitate comparison of the peak amplitude in the curves across different thicknesses. Also, a thin dashed line indicates where the peak of the scatterplot curve would be in an ideal measurement. To serve as a basis for comparison, Figure C.2 shows the two ideal scatterplots in the new orientation.

Figure C.2: Rotated ideal scatterplot curves. (a) shows the curve for first directional derivative versus data value; (b) the curve for second directional derivative versus data value. As in the scatterplots in Figures C.3 through C.5, there are dotted lines to indicate the location of the peaks of the ideal curves.

Figure C.3: Derivative measure comparisons for thicknesses 0.33 to 2.66

Figure C.4: Derivative measure comparisons for thicknesses 3.00 to 5.33

Figure C.5: Derivative measure comparisons for thicknesses 5.66 to 8.00

The first thing to notice about the scatterplots in Figures C.3, C.4, and C.5 is that for small thicknesses (around 1.00), none of the derivative measures' responses were very high. Besides being distorted in shape compared to the ideal, the scatterplot curves are compressed towards the $f(x)$ axis. This is an important consideration when analyzing volumes with sharp transitions between material regions. Because the histogram volume will contain a somewhat distorted measure of the boundaries, the $g(v)$, $h(v)$, and $p(v)$ calculations will also be distorted, and there will be a mismatch between the user-specified boundary function $b(x)$ and the actual opacity assigned to the boundaries in the volume by the opacity function created from our algorithm. As was done with the turbine blade dataset (Section 6.1), it may be beneficial to slightly blur the volume as a pre-process, if the resulting slight loss of detail is tolerable.

The row for thickness 2.66 at the bottom of Figure C.3 shows the typical relationship between the three second derivative measures. The measure based on $\nabla \Vert\nabla f \Vert$ gives the smallest amplitude response to the boundary, while the measures based on $\mathbf{H} f$ and $\nabla^2 f$ are closer to the ideal, and are about equal. The more noticeable difference between the three measures is the amount of spread in the range of derivative values at a single data value. The curve from the $\nabla \Vert\nabla f \Vert$ measure is very coherent, but the $\mathbf{H} f$ curve is more dispersed, and the $\nabla^2 f$ curve is even more so.

The dispersion of the scatterplot curves is a result of quantization noise, the error introduced by representing a signal's values with fixed point instead of floating point precision. All the synthetic volumes generated for this analysis contained only 8-bit quantities. As a result, the error in the signal value (as stored in the synthetic dataset) is on average one half of $1/256$, or $1/512$. This amount is small relative to the changes in data value within sharp boundaries, but it is a greater percentage of the change in data value within more blurred boundaries. Thus, as the boundaries become more blurred, the quantization noise will become more and more prominent in a derivative measurement. Also, since second derivative measures are by nature more sensitive to noise than first derivative measures, the effect of quantization is always more evident in the $f''(x)$ scatterplots than in the one for $f'(x)$.

The collection of scatterplots as a whole hints at a fundamental relationship between the bit depth of the data, the boundary thickness, and the derivative measures' robustness against quantization noise, as governed by the mathematical properties of the derivative measures. A thorough exploration of this relationship would be vital to the design of higher quality derivative measures, but for the time being we choose amongst the ones already implemented. As can be seen in Figures C.4 and C.5, the second derivative measures can be ordered by their sensitivity to quantization noise: $\nabla \Vert\nabla f \Vert$, $\mathbf{H} f$, and then $\nabla^2 f$. By the time the thickness has reached 6.00 or higher, the $\nabla^2 f$ curve has become so dispersed as to be unrecognizable, while even at thickness 8.00 the $\nabla \Vert\nabla f \Vert$ curve is still reasonably coherent. Despite this, the $\nabla \Vert\nabla f \Vert$ measure is less accurate than the other two measures, since its curve is always further from the ideal size than the others. Given the trade-offs between the three measures in terms of quantization noise, accuracy, and computational cost, we have generally adopted the Hessian-based second derivative measure as the standard.

Footnotes

... boundaries²¹

To be completely thorough, we would need to create synthetic volumes containing boundaries at a wide variety of orientations and with a wide range of surface curvatures.