Live Wire Segmentation

The first class of algorithms reviewed, which are usually referred to as Live-Wire algorithms [38], belongs to the field of dynamic programming. The foundations of these algorithms lie in the F* algorithm [39], and will briefly be sketched here.

In a Live-Wire algorithm, the image I is considered as a discrete neighborhood graph, where each pixel corresponds to a node in the graph. Generally an 8-Neighborhood (N8, Moore neighborhood) is defined, so that diagonal connections are allowed. A cost function C(I) assigns a value to each node in the graph. Typically, the cost function is based on local features, for example, the output of an edge detector. Once a suitable cost function is defined, the segmentation task is reduced to a minimal cost path search problem between two points in the image graph. These points are usually selected by the user, who defines a starting point s and then drags the endpoint e with the mouse toward a desired location. During dragging the algorithm repeatedly evaluates the minimal cost path Pmin from the starting point s to the current location e as illustrated in Fig. 14.10. In order to evaluate the minimal cost path Pmin, a path array P has to be constructed that accumulates the total costs from the starting point s to any point of the image.

All values of the path array P are initially set to infinity except the start vertex s, which is assigned a value equal to its cost C(s). The elements of the

Figure 14.10: Segmentation of the corpus callosum using the F* algorithm. Note the jumping behavior between the last two images due to global optimum computation.

path array are then updated iteratively until convergence, i.e., until no more values in the array are changed in one iteration. The values of the ith row of P are first adjusted from left to right by the following rule

P (i, j) = min

P(i - 1,

j-

1)

+

C (i,

P (i - 1,

j)

+

C (i,

P(i - 1,

j +

1)

+

C (i,

P (i, j -

1)

+

C (i,

P (i, j)

and then from right to left according to

P(i, j) = min (P(i, j + 1) + C(i, j), P(i, j)). (14.4)

Additional iterations alternate between a bottom-to-top pass (with reversed indices, so that the bottom row corresponds to i = 1) followed by a top-to-bottom pass. In each pass the updating rules 14.3 and 14.4 are applied. Once the minimal cost array P has been generated, the minimal cost path Pmin from any point e' to the starting point s can easily be computed by backtracking from e' to s without recalculating P, thus making the algorithm very fast.

As can be seen in Fig. 14.10, the generated segmentation line approximates the edges present between the start- and endpoint selected. The continuous computation of a global optimum leads to the jumping behavior of the algorithm, as can be observed in the last two images of Fig. 14.10. The last segment of the segmentation line abruptly changes the edges that are approximated.

Modifications of the resulting segmentation cannot be directly integrated in the concept of Live-Wires as the path array P is fixed solely based on the image on initialization, rendering any post processing a cumbersome task. To tackle the discontinuities, the user can generally fix the endpoint of the segmentation line so far if estimated adequately, thus freezing the wire and starting a new segment. A piecewise construction of the segmentation is obviously mandatory for any closed contour.

Different extensions have been proposed to improve the behavior of the Live-Wire algorithms. These extensions include, but are not limited to the definition of more complex cost functions [38], advanced edge feature detections [40] and the extension to 3D [41-43]. The main advantages of the Live-Wire approach are the relatively simple implementation and the computational speed, as the shortest path can be computed online while the user drags the mouse, thus providing direct feedback.

In contrast to Snakes, which will be described next, the selected path is a global optimum of the cost function defined over the complete image, whereas Snakes iteratively adapt their contours based on local information, which will very likely represent a local optimum of their respective target function. Global optimum is a desirable mathematical property in optimization; it is, however, not obvious that the best segmentation is equivalent to this definition of an optimum.

0 0

Post a comment