Tracking monotonically advancing boundaries in image sequences using graph cuts and recursive kernel shape priors

Abstract

We introduce a probabilistic computer vision technique to track monotonically advancing boundaries of objects within image sequences. Our method incorporates a novel technique for including statistical prior shape information into graph-cut based segmentation, with the aid of a majorization-minimization algorithm. Extension of segmentation from single images to image sequences then follows naturally using sequential Bayesian estimation. Our methodology is applied to two unrelated sets of real biomedical imaging data, and a set of synthetic images. Our results are shown to be superior to manual segmentation.

Fig. 1. Level-set embedding of shapes

Embedding of a region Ω into a signed distance function ϕ_Ω defined on a discrete lattice. ϕ_Ω takes values according to the signed Euclidean distance from the boundary ∂Ω, with negative values inside Ω. The boundary ∂Ω is implicitly embedded as the zero-level set of ϕ_Ω. Shown is a 2-d lattice, however, level set method works for ${ℝ}^d$ with any arbitrary d.

Fig. 2. Embedding of an image into a graph

In the graph cuts framework, pixels are nodes in a graph. Connections between neighboring pixels are made, as well as connections between each pixel and two special nodes called the source (foreground) and sink (background). Depicted is an eight-neighbor system, where s and u are neighbors. These connections are weighted according to the strength of the association between two nodes to the same class (either foreground or background). A segmentation is found by cutting the graph into two parts separating the source and sink such that the edge weights along the cut are minimal. The segmented foreground then consists of the pixels that have intact edges with the source (depicted as solid black lines).

Fig. 3. Examples of monotonic boundary movement

Shown are stills from three image sequences depicting monotonic boundary motion. Top two rows are cortical spreading depression hemodynamical waves. Bottom row is a wound undergoing healing. The noise characteristics in these images, and the shapes that develop, differ markedly.

Fig. 4. Segmentation of a synthetic image sequence

(top) Mask of ground truth wave sequence, with a growing interior region shown in black. The spatial field is of size 320 × 240 pixels. The speed of the front varies between 6 and 10 pixels/frame (shown in fig 5), producing topological changes in the interface. (bottom) Segmentation of images where noise has been added to the ground truth. The image intensity was 0 ± 3 in the exterior and 3 ± 3 in the interior. δt = 7 frames.

Fig. 5. Recovery of interface speed

(left) Ground truth speed field. (right) Reconstructed speed field. Reconstruction of synthetic wave speed using the segmentations shown in figure 4, and second-order upwind finite differences. The ground-truth speed of the interface is 10 pixels/frame as it passes through the UCLA letters, and 6 pixels/frame outside of the letters. The reconstructed speed field has an estimated speed of 9.8 ± 1.5 pixels/frame inside the letters, and 6.0 ± 0.7 pixels/frame outside. Velocity scale shown at right in pixels/frame.

Fig. 6. Updating predictions with new data

(left) Past (yellow), current (green), and predicted future (red) interface positions drawn over mean predicted speed field. Predictions of future interface positions, which act as shape priors, are made using samples from our stochastic speed model. To the left of the green boundary are speeds interpolated from the collection of past interface positions. To the right are interface positions found by propagating the green contour with speeds sampled from the GMRF model. Speed scale shown at left is pixels/frame. (middle) When a new noisy image is acquired, the MM algorithm is initialized at the position obtained by propagating the previous interface position according to its estimated mean speed field. The true boundary deviates from the mean predicted boundary because of developing protrusions. The mean predicted boundary is calculated by propagating the green boundary against the mean speeds given in Eq 8. (right) After a single MM iteration, the protrusions are found. Due to the continuous nature of the kernel density shape prior, our method is able to account for large deformations.

Fig. 7. Segmentation of real in-vivo CSD data

(Left→ Right) CSD shown propagating, δt = 7s. Top: Original unsegmented inter-frame differences showing CSD-related changes in blood signal. Second row: Results from our segmentation method, where we track the moving front probabilistically. Third row: Segmentation of the spreading region done without shape priors.

Fig. 8. Adjusting regularization by adjusting the shape penalty parameter

(Left→Right) and (Top→ Bottom) Biological movement during imaging causes artifacts in the difference image. Failure to adjust for the movement results in less than ideal data. Increasing α, the shape mismatch penalty, can compensate for poorly acquired image data. Our method is able to track the moving front even as it is partially occluded. Top: segmentation without shape prior. Second row α = 2. Third row: α = 3. Fourth row: α = 4. δt = 2s.

Fig. 9. Segmentation of wound healing assays featuring robust shape changes

(Left→Right) and (Top→ Bottom) Wound-healing time stills. Segmentation performed on the sobel filter (shown) of the original image sequence, which is well-modeled by the Gaussian mixture of section II-B. In this application, the boundary is moving inward, while the shape of the inner region is undergoing large changes. The segmentation method works well even for non-convex shapes. δt = 30 min. We are grateful to Prof. C.-L. Guo, Caltech Bioengineering for these images. Resolution: 320 × 240.

Fig. 10. Comparison of results against laborious manual human segmentation of synthetic images

The accuracy of our method’s segmentation of the synthetic image sequence (for the six frames shown in Fig 4) compared to the accuracy of three humans. The error plotted in the y-axis is the average number of misclassified pixels per boundary-length, where boundary-length is the average of the lengths of the ground truth and segmented boundary. Our method differed from the ground truth by 0.30 ± 0.10 pixels. The humans performed significantly worse with error of 0.61 ± 0.14 pixels.

Fig. 11. Comparison of results against laborious manual human segmentation of in-vivo CSD images

Deviation of human segmentations from the results of our automated approach for the image sequence shown in Fig 7. The results from our segmentation method agreed with the results from the manual segmentations to within 1.7 ± 0.6 pixels.