THE LAYERED NET SURFACE PROBLEMS IN DISCRETE GEOMETRY AND MEDICAL IMAGE SEGMENTATION

Abstract

Efficient detection of multiple inter-related surfaces representing the boundaries of objects of interest in d-D images (d >/= 3) is important and remains challenging in many medical image analysis applications. In this paper, we study several layered net surface (LNS) problems captured by an interesting type of geometric graphs called ordered multi-column graphs in the d-D discrete space (d >/= 3 is any constant integer). The LNS problems model the simultaneous detection of multiple mutually related surfaces in three or higher dimensional medical images. Although we prove that the d-D LNS problem (d >/= 3) on a general ordered multi-column graph is NP-hard, the (special) ordered multi-column graphs that model medical image segmentation have the self-closure structures and thus admit polynomial time exact algorithms for solving the LNS problems. Our techniques also solve the related net surface volume (NSV) problems of computing well-shaped geometric regions of an optimal total volume in a d-D weighted voxel grid. The NSV problems find applications in medical image segmentation and data mining. Our techniques yield the first polynomial time exact algorithms for several high dimensional medical image segmentation problems. Experiments and comparisons based on real medical data showed that our LNS algorithms and software are computationally efficient and produce highly accurate and consistent segmentation results.

Fig. 1

Illustrating the “unfolding” operations on the transversal cross-sections of vascular MR images of a human femoral artery specimen. (a) A schematic cross-sectional anatomy of a diseased artery. (b) Performing a polar resampling. (c) Each transversal cross-section is embedded as an xz-slice in the 3-D xyz-space.

Fig. 2

(a) A 2-D net model B. (b) A 3-D properly ordered multi-column graph G generated by B and κ = 4 (the edges between Col(u_i) and Col(u_i+1), i = 0,1, 2, are symmetric to those between Col(v_i) and Col(v_i+1), and the edges between Col(v_j) and Col(u_j), j = 1, 2, are symmetric to those between Col(v₃) and Col(u₃); all these edges are omitted for a better readability). (c) Two (l, 2)-separate net surfaces in G marked by heavy edges. (d) Two net surfaces divide the vertex set of G into three disjoint vertex subsets.

Fig. 3

Illustrating the sagittal cross-section based unfolding method, (a) The sagittal and transversal cross-sections of a tubular object, (b) A transversal cross-section of a 3-D intravascular ultrasound vessel image. Resampling is performed at each angle for all transversal cross-sections to form a sagittal cross-section, (c) A sagittal cross-section of a 3-D intravascular ultrasound image at an angle θ_i. (d) A schematic unfolded 3-D image ℐ(x, y, z). Each sagittal cross-section at an angle θ_i is embedded as a yz-slice of ℐ at x = θ_i. (e) Splitting ℐ into two sub-images and . (f) The net model B for ℐ.

Fig. 4

(a) Illustrating the proper ordering of the edges in G. (b) Constructing a subgraph $G_i^{\prime }$ from G. (c) Incorporating the surface separation constraints into the construction of $G_i^{\prime }$ and $G_{i+1}^{\prime }$ (with Li = 1 and U_i = 2).

Fig. 5

(a) Illustrating the proof of Lemma 3. (b) Illustrating Case (2) in the proof of Lemma 6. (c) Illustrating Case (3) in the proof of Lemma 6.

Fig. 6

(a) Illustrating the reverse ordering of G. Columns Col(v) and Col(u) are in reverse order, (b) Constructing a properly ordered graph G′ from G (assume that a, v ∈ Q, u, b ∈ Q̄, and Q ∪ Q̄ = V_B). Each vertex in a parenthesis is a corresponding vertex in G.

Fig. 7

(a) A watershed-monotone region, (b) A weakly watershed-monotone region which is not watershed-monotone to any Γ₁(c). (c) A watershed-monotone shell. (For a better readability, a 2-D pixel grid Γ is used.)

Fig. 8

(a) The extended “upper” boundary surface $S_e^u$ of a weakly watershed-monotone region R (consisting of the shaded pixels). (b) The extended “lower” boundary surface $S_e^l$ of R.

Fig. 9

Computing an optimal weakly watershed-monotone region R. For a better readability, a 2-D pixel grid Γ is used, (a) Illustrating the construction of the graph G′. The shaded pixel is the given weak watershed kernel pixel c. Only a portion of the directed edges from $G_1^{\prime }$ to $G_2^{\prime }$ is shown. The solid vertices shown make up of a closed setin G′. (b) The extended “upper” surface $S_e^u$ defined by the vertices of $G_2^{\prime }$ in . (c) The extended “lower” surface $S_e^l$ defined by the vertices of $G_1^{\prime }$ in . (d) A weakly watershed-monotone region R corresponding to the closed set .

Fig. 10

Computing an optimal watershed-monotone shell. For a better readability, a 2-D pixel grid Γ is used, (a) Illustrating the construction of the graph G′. The shaded pixel is the given watershed kernel pixel c. Only a portion of the edges from $G_1^{\prime }$ to $G_2^{\prime }$ is shown, (b) A watershed-monotone shell R corresponding to the closed set in G′ consisting of all the solid vertices in (a).

Fig. 11

Single-surface methods versus our inter-related surface method, (a) Cross-section of the original synthesized image. (b) Single surface detection, using a standard edge-based cost function, (c) MetaMorphs method segmenting the inner border in 2-D. (d) Double-surface segmentation obtained by our LNS approach.

Fig. 12

Comparisons on airway wall segmentation results. For a better readability of the 3-D surface renderings, only the single luminal surface results are shown. (a), (b), (e), and (f) are the results yielded by the slice-by-slice 2-D graph-search based approach on two different airway segments. Four consecutive slices and the 3-D surface rendering are shown for each airway segment (10 slices). (c), (d), (g), and (h) are the walls segmented by our 3-D LNS approach.

Fig. 13

Results on MR vascular wall surface segmentation. (a) Four consecutive slices from the original image data. (b) Manually identified lumen, IEL, and EEL surfaces. The outermost adventitia surfaces are not shown. (c) Results produced by the program for our LNS algorithm.