On Euclidean Metric Approximation via Graph Cuts (Computer Vision,Imaging and Computer Graphics) Part 2

Experimental Results

Approximation Error

To benchmark the approximations we chose to measure the multiplicative metrication error they give under particular angular orientations in 2D. Graphs of the error are available in Fig. 4. The figure contains 12 graphs where each row corresponds to a particular 2D neighbourhood and each column to a particular anisotropy ratio. We compared our approximation with the method described in [2]. To simulate the anisotropy we had to embed it into a Riemannian metric in the latter case. According to the referenced paper the weights for a Riemannian metric with a constant metric tensor D over an isotropic grid should be set to:

whereand p equals toand 2 in 2D and 3D, respectively. A node spacing change corresponds to a constant metric tensor with eigenvectors aligned with the coordinate system and eigenvaluesHence, the metric tensor simulating the anisotropic grid has the following form:

Notice that if D is the identity matrix the second term in Eq. 15 vanishes and the formula reduces to the isotropic Euclidean case.

The multiplicative error measures in percents the difference between the approximated length of a line under given angular orientation in the cut metric and the actual Euclidean length of the line. Obviously, the larger neighbourhood system is used the smaller is the maximum error of the approximation. As can be seen from Fig. 4, both approaches perform equivalently in the isotropic case for 4- and 8-neighbourhood which is expected. For larger neighbourhoods our approach is almost two times better due to the reduced bias and its invariance to mirroring is also apparent as the graph is symmetrical around values §, π and With increasing anisotropy the gap widens and especially for smaller neighbourhoods the difference is really huge in favour of our method. This is caused by the additional error of the Riemannian metric formulas. Especially the assumption of infinitely small Δφk required to derive Eq. 15 is unrealistic causing a considerable error. However, note that the maximum error depends primarily on sup Δφk in both cases and that this value increases with increasing anisotropy. Thus, for high anisotropy ratios using larger neighbourhood is inevitable.

To conclude this subsection, using a linear programming we have also numerically computed the optimal edge weights with respect to the maximum error across all possible angular orientations. According to this experiment, it seems that the proposed approximation is nearly optimal, i.e., it is not possible to improve the approximation significantly. Nevertheless, we do not know what is the relation between our edge weights and the optimal ones with respect to this criterion or how to compute the optimal edge weights efficiently.

Applications to Image Segmentation

In this subsection we show the practical impact of our results and evaluate the benefits of the improved approximation in biomedical image segmentation. We chose the Chan-Vese segmentation model [6] that is being very popular in this field for its robust segmentation of highly degraded data. The Chan-Vese model is a binary segmentation model which corresponds to piecewise-constant specialization of the well-known Mumford-Shah energy functional [9]. In simple terms, it segments the image into two possibly disconnected regions trying to minimize the length of the frontier between them and the intra-region intensity variance. This functional can be minimized using graph cuts [10] and as it aims for minimization of the boundary length it necessarily depends on the Euclidean metric approximation.

Fig. 5. Two examples of biomedical image segmentation using the Chan-Vese model. (a) yz cross-section of the segmented image. (b) Level-set based method. (c) Graph cuts with anisotropy embedded into the Riemannian metric. (d) Graph cuts with our edge weights.

To test the improvement of our approximation over the previous approach also in 3D we plugged the derived formulas into the algorithm and used it to segment low-quality volumetric images of cell clusters acquired by an optical microscope. The yz crosssections of the segmented images are depicted in Fig. 5a. The dimensions of the images are 280 x 360 x 50, with resolution in the xy plane being about 4.5 times the resolution in the z direction. We used 26-neighbourhood to segment the images.

In Fig. 5b there is the Chan-Vese segmentation computed using level-sets. This technique was much slower than the graph cuts, however, it does not suffer from the metrication errors so we used its results as the ground truth. The results obtained using the method of Boykov and Kolmogorov (where anisotropy is embedded in the Riemannian metric) and our edge weights are depicted in Fig. 5c and Fig. 5d, respectively. Clearly, our method gives a result closer to the level-sets. On the contrary, the segmentation based on the Riemannian metric seems too flat or chopped. Based on the results from the previous subsection it could be probably greatly improved using a larger neighbourhood, but at the cost of higher computational demands.

Conclusions

In this paper, we have improved the method of Boykov and Kolmogorov for Euclidean metric approximation via graph cuts in both 2D and 3D. We derived the requisite formulas and showed that our approach has a significantly smaller metrication error than the original method and that it is invariant to image mirroring. Using the presented results it is possible to exploit graph cut based energy minimization depending on contour length or surface area over images with anisotropic resolution directly without the need to resample them or to use large neighbourhoods for better precision. A possible application of the results was demonstrated on a biomedical image segmentation. It is possible to download implementation of the described methods from http://cbia.fi.muni.cz/projects/graph-cut-library.html.

Finally, as explained in Section 4.1 anisotropic grids correspond to a special case of the Riemannian metric with a constant metric tensor with eigenvectors aligned with the coordinate system. However, the general case of this metric is also being widely used in several fields including image segmentation [2]. For this purpose, we have extended our method exploiting Voronoi diagrams also to this more general class of metrics. Our results in this area are going to be published in the very near future.