Seed segmentation using l_∞ minimization

[0001] This application claims priority to U.S. Provisional Application Ser. No. 60/840,762, filed on Aug. 29, 2006, which is herein incorporated by reference in its entirety.

[0002] 1. Technical Field

[0003] The present invention relates to image processing, and more particularly to a system and method for seeded image segmentation using l_∞ minimization.

[0004] 2. Discussion of Related Art

[0005] Image segmentation is an important problem in computer vision. Traditionally, segmentation methods have focused on unsupervised segmentation, grouping elements of the image according to a criterion such as homogeneity. Recently, supervised image segmentation methods have gained popularity, giving the user (or preprocessor) the ability to affect the segmentation as needed for a particular application.

[0006] Supervised segmentation methods typically come in three types: 1) The user is asked to provide pieces (e.g., points) of the desired boundary which are then completed by the method, 2) The user is asked to specify an initial boundary that is “close” to the desired boundary which evolves to the desired boundary or 3) The user is asked to provide an initial labeling of some pixels as belonging to the desired object to be segmented or to the background, after which the method completes the labeling for all pixels.

[0007] For supervised segmentation methods taking user provided initial labeling as input, the user provides a partial labeling of the image, known as seeds, after which a complete labeling is constructed. Correction of an erroneous segmentation is accomplished by specifying additional labels for the initializing partial labeling. Two exemplary seeded segmentation methods are the Graph Cuts and Random Walker methods. These methods treat the image as a graph and minimize certain energy functionals on this graph to produce a segmentation. Since these energy functionals are convex, it is possible to find the global optimum. Moreover, due to the method definitions on general graphs, they may be applied without modification to an image of arbitrary dimension.

[0008] In both of the Graph Cuts and Random Walker methods, a weighted graph representation of the image is constructed. Nodes of this graph correspond to pixels in the image and edges are placed between nearby pixels. The edge weights are determined by a similarity measure on these pixels such that an edge connecting two pixels with a high similarity should have a large weight and vice versa.

[0009] In the Graph Cuts method, the foreground/background seeds are treated as source/sink nodes for a max-flow/min-cut operation. Using a maxflow/min-cut method, a set of edges with the minimum total weight is found and then returned as the object boundary. A problem with the Graph Cut method is the “small cut” behavior. Since this method tries to minimize the total edge weights in the cut, it may return very small segmentations as a result of low contrast, a small number of seeds or noise. The minimum-cut criterion may also cause problems by returning solutions in which the boundary takes a “shortcut” over a protruded section of the object in an attempt to minimize boundary length.

[0010] In the Random Walker method, the edge weights are treated as probabilities (when normalized by node degree) of a particle at one node traveling to a neighboring node. Given seeds, one may then compare the probability that a particle initiating at any node (pixel) travels first to the foreground or background seeds and assign that pixel to the corresponding label. It is possible to determine these probabilities for each pixel analytically without any simulation of random walks. While the Random Walker achieves good segmentation in the presence of weak boundaries and is insensitive to seed point selection, it is subject to loose segmentation, for example, in the presence of image noise.

[0011] Therefore a need exists for an improved seeded segmentation method.

[0012] A computer readable medium embodying instructions executable by a processor to perform a method for seeded image segmentation using to minimization, the method including providing an image comprising a set of pixels, wherein a foreground seed label is given for at least one pixel of the image and a background seed label is given for at least another pixel of the image, determining an affinity function for every pair of neighbor pixels, solving the l_∞ minimization, which assigns a probability to each pixel, labeling each pixel as foreground pixel or background pixel according to a threshold of the probability, and outputting the image including the segmentation labels.

[0026] According to an embodiment of the present disclosure, a method for seeded image segmentation uses an l_∞ norm. The method for the l_∞ optimization produces a segmentation that overcomes difficulties associated with the Graph Cuts or Random Walker methods.

[0027] Herein, a method for seeded image segmentation using l_∞ minimization is described.

[0028] Referring now to the method for seeded image segmentation using l_∞ minimization and concepts thereof; A graph includes of a pair G=(V, E) with vertices (nodes) v ε V and edges e ε E⊂ V×V, with n=|V| and m=|E|. An edge, e, spanning two vertices, v_i and v_j, is denoted by e_ij. A weighted graph assigns a value to each edge called a weight. The weight of an edge, e_ij, is denoted by w(e_ij) or w_ij and is assumed here to be nonnegative. The following will also assume that the graph is connected and undirected (i.e., w_ij=w_ji). Herein, an 8-connected lattice is employed as a neighborhood structure. Each node may be identified with a pixel (2D) or voxel (3D), although nodes could be otherwise identified with groups of pixels/voxels.

[0029] Referring to FIG. 9, consider a seeded image segmentation using l_∞ minimization on an image domain, V, written as A: assume that a set of pixels, F, labeled foreground and a set of pixels, B, and labeled background, such that F, B⊂V, F∩B=0 are given (e.g., interactively or via a preprocessor) 901; find a solution to

[0030] $\begin{array}{cc}\underset{s.t.}{\min }{C^{\frac{1}{2}}\mathrm{Ax}}_q^q={\left[\sum _{e_{\mathrm{ij}}\in E}{\left(w_{\mathrm{ij}}x_i-x_j\right)}^q\right]}^{\frac{1}{q}},x_F=1,x_B=0.& \left(1\right)\end{array}$
[for q=∞] (s.t. (“such that”)) where A is the m×n node-edge incidence matrix defined as

[0031] $\begin{array}{cc}{A}_{e_{\mathrm{ij}}{\upsilon }_k}=\{\begin{array}{cc}+1& \mathrm{if}i=k,\\ -1& \mathrm{if}j=k,\\ 0& \mathrm{otherwise},\end{array}& \left(2\right)\end{array}$
and the m×m matrix C is the constitutive matrix, which is a diagonal matrix with the square weights of each edge along the diagonal 902; assign a set of segmentation labels 904/903/905, s: V{0,1} such that

[0032] $\begin{array}{cc}{s}_i=\{\begin{array}{cc}1& \mathrm{if}{x}_i\ge \frac{1}{2},\\ 0& \mathrm{if}{x}_i<\frac{1}{2}.\end{array}& \left(3\right)\end{array}$
; and output the image including the segmentation labels 906, for example, the output may be a display of a segmented image, an output to a computer readable media, etc.

[0033] An example of the method is summarized in FIG. 1. Note that the above formulation could be interpreted from a continuous perspective in which (1) is replaced by
min∥∇ψ∥_q^q  (4)
where the sets F and B represent internal Dirichlet boundary conditions and the gradient operator is modified by an inhomogeneous metric tensor that changes spatially in response to intensity changes.

[0034] For graph based segmentation methods the edge weights may encode image intensity changes. A weighting function in these methods can be given as
w_ij=exp(−√{square root over (β|g_i−g_j|²+|h_i−h_j|²)}),  (5)
where g_i indicates the image intensity at pixel i, h_i indicates the spatial position of pixel i and β is a free parameter. In the context of (4), these weights would be equivalent to a spatially varying metric. Note that pixel affinity could equally be derived from changes in color, texture, etc.

[0035] The method given by FIG. 1 leaves only one remaining choice: the value of q (parameter q is the p—norm of the gradients). Herein, it is shown that the choice of q=1 leads to the Graph Cuts method and the choice of q=2 leads to the Random Walker method. This situation is summarized in FIG. 2. Following the justification of the above statements, the choice q=∞ is described.

[0036] Referring to the q=1 case—Graph Cuts; If q=1 is substituted into (1), and the method given by FIG. 1 gives the solution of:

[0037] $\begin{array}{cc}\underset{s.t.}{\min }C^{\frac{1}{2}}\mathrm{Ax}=\sum _{e_{\mathrm{ij}}\in E}{w}_{\mathrm{ij}}x_i-x_j,x_F=1,x_B=0.& \left(6\right)\end{array}$

[0038] The dual formulation of (6) is
max y_B, s.t. A^Ty=δ_Fy_F+δ_By_B, 0≦y_ij≦w_ij ∀e_ij ε E,  (7)
where δ_F,B are vectors of length n with 1's in entries corresponding to foreground and background seeds respectively, and zeros elsewhere.

[0039] Upon closer inspection, it can be seen that (7) is the maximum-flow problem, where y_B is the total flow, subject to the flow conservation principle. Therefore, formulation (1) gives rise to the min-cut/max-flow problem for q=1. The primal problem (6) also demonstrates the minimum cut problem—Minimize a weighted cut, represented by x, between terminals F and B. The solution of (6) will be a binary solution, x_i ε {0,1}, due to the totally unimodular property of the min-cut problem. Since the solution of (6) will be binary, the thresholding given by FIG. 1 (see also FIG. 9, block 905) will have no consequence, and the labeling (see FIG. 9, block 905) will be equal to the optimal solution of (6). As a result, the Graph Cuts image segmentation method gives the same solution as the method given by FIG. 1 when q=1.

[0040] Referring to the q=2 case—Random Walker; The q=2 case corresponds to the Random Walker segmentation method. For q=2, (1) becomes

[0041] $\begin{array}{cc}\begin{array}{c}\underset{s.t.}{\min }{C^{\frac{1}{2}}\mathrm{Ax}}_2^2=\sum _{e_{\mathrm{ij}}\in E}{w_{\mathrm{ij}}^2\left(x_i-x_j\right)}^2\\ =x^T{A}^T\mathrm{CAx},\end{array}{x}_F=1,x_B=0.& \left(8\right)\end{array}$
A minimization of this form is described in the Random Walker formulation for a case of two labels. Solution of (8) yields the desired Random Walker probabilities, which are then thresholded to produce the foreground/background labeling 905. Therefore, the Random Walker image segmentation method with two labels gives exactly the same solution as the method given by FIG. 1 when q=2.

[0042] Hence, the method given by FIG. 1 is shown to produce the Graph Cuts and Random Walker segmentation solutions when q=1 and q=2, respectively.

[0043] Turning now to the q=∞ case; If q→∞, (1) becomes

[0044] $\begin{array}{cc}\begin{array}{c}{\lim }_{q\to \infty }\sqrt[q]{\sum _{e_{\mathrm{ij}}\in E}{w}_{\mathrm{ij}}^q{x_i-x_j}^q}=\underset{\underset{\rho }{︸}}{\underset{e_{\mathrm{ij}}\in E}{\max }{w}_{\mathrm{ij}}x_i-x_j}{\lim }_{q\to \infty }\\ \underset{\underset{1}{︸}}{\sqrt[q]{\sum _{e_{\mathrm{ij}}\in E}{\left(w_{\mathrm{ij}}\frac{x_i-x_j}{\rho }\right)}^q}}\\ =\rho .\end{array}& \left(9\right)\end{array}$
Consequently, the overall optimization problem 904 may be written as
min max_eijεE w_ij|x_i−x_j|, st x_F=1, x_B=0.  (10)

[0045] This form is a combinatorial formulation of a minimal Lipschitz extension.

[0046] In the following description, let uv denote a path in G from node u ε V to v ε V. Also, let ρ=max_eijE w_ij|x_i−x_j| for a solution x to (10).

[0047] For any path π: Fv, we have the inequalities:

[0048] $\begin{array}{cc}\sum _{e_{\mathrm{ij}}\in \pi }x_i-x_j\ge x_F-x_B=1,& \left(11\right)\\ \sum _{e_{\mathrm{ij}}\in \pi }x_i-x_j\le \sum _{e_{\mathrm{ij}}\in \pi }{w}_{\mathrm{ij}}^{-1}\rho .& \left(12\right)\end{array}$

[0049] Combining these two inequalities yields

[0050] $\begin{array}{cc}\rho \ge {\left(\sum _{e_{\mathrm{ij}}\in \pi }{w}_{\mathrm{ij}}^{-1}\right)}^{-1},\forall \pi :FB.& \left(13\right)\end{array}$

[0051] A maximum lower bound for ρ is attained with the shortest path between a foreground and background seed over the reciprocal weights (w_ij⁻¹).

[0052] Let d_i^F and d_i^B denote the shortest path length from node v_i ε V to a foreground and background node using reciprocal weights respectively.

[0053] Theorem 1. Let x be defined as
x_i=min{ρd_i^B, 1}.  (14)

[0054] This potential vector is an optimal solution for (10).

[0055] Proof. Begin by checking the boundary conditions given in (10).

[0056] x_i=1, i ε F. Since ρ⁻¹≦d_i^B for all i ε F, ρd_i^B≦1, which implies x_i=1.

[0057] x_i=0, i ε B. For all i ε B, d_i^B=0, therefore x_i=0.

[0058] w_ij|x_i−x_j|≦ρ. Without loss of generality, assume x_i≧x_j, which implies that d_i^B≧d_j^B.

[0059] If x_j=1, then x_i=1. Therefore, this property is readily satisfied. Assume otherwise. It is known that d_i^B−d_j^B≦w_ij⁻¹ by the shortest path property. So, we have
w_ij(x_i−x_j)≦w_ij(ρd_i^B−ρd_j^B)≦ρ.

[0060] A practical consequence of Theorem 1 is that the potential vector x may be determined in O(m+n log n) time by finding d_i^B for each node, which needs a single source (treating all nodes in F as a single node) all shortest paths computation. Although the above discussion offers a simple, efficient method of finding an optimal solution to (10), it should be noted that this solution may be achieved using different methods.

[0061] FIG. 3 illustrates to the relationship between the q=1 and q=∞ cases. F is the foreground node (set to unity), B is the background node (set to zero). The remaining node, u, may take any value ranging between [0, 1] without affecting the objective function in (1). For this reason, regularizing the q=∞ case with an l₁ term does not remove the degeneracy and therefore an l₂ regularizer is used. Each edge has unity weight.

[0062] Additionally, the situation in FIG. 3 illustrates the degeneracy of the l₁ minimization of (6) 904, as well. In this graph, the value of x_u can take any value between 0 and 1 without affecting the optimum of (10) or (6). Specifically, for any x_u ε [0,1], l₁(x)=2 and l_∞(x)=1. Hence, there exists an infinite number of solutions for these problems and some regularization 903 is needed to obtain a unique solution. Regardless of the regularization method employed, a surprising aspect of the solution in the l_∞ case (with regards to the segmentation) is that some pixels are guaranteed to take the foreground label (have solution greater than ½) while others are guaranteed to take the background label (have solution less than ½). However, there remains an “ambiguous region” in which the method of regularization 903 determines the labeling 905. These regions may be determined for the l_∞ method.

[0063] Theorem 2. Let ρ be the minimum value of l₁ (x). Then, for any potential vector x satisfying the boundary conditions in (10), with w_ij|x_i−x_j|≦ρ, we have
1−ρd_u^F23 x_u≦ρd_u^B, ∀u ε V.  (15)

[0064] Proof For each node u ε V, let π^F and π^B denote the shortest paths from F and B to u_i respectively. Then

[0065] $\begin{array}{cc}\sum _{e_{\mathrm{ij}}\in {\pi }^F}\left(x_i-x_j\right)=1-x_u,& \left(16\right)\\ \sum _{e_{\mathrm{ij}}\in {\pi }^F}\left(x_i-x_j\right)\le \sum _{e_{\mathrm{ij}}\in {\pi }^F}x_i-x_j\le \rho d_u^F.& \left(17\right)\end{array}$

[0066] Combining these inequalities yields
ρd_u^F≧1−x_ux_u≧1−ρd_u^F.  (18)
The same mechanism allows for derivation of the other inequality.

[0067] These inequalities allow for finding lower and upper bounds on the segmentation areas. In any optimal solution to (10), x, a node u will always be classified as background if

[0068] $\rho d_u^B\le \frac{1}{2}$
and as foreground if

[0069] $\rho d_u^F\le \frac{1}{2}.$
This property allows one to put bounds on the possible segmentations in an efficient way. Additionally, these bounds demonstrate that the l₁ method avoids the shrinking problem associated with Graph Cuts.

[0070] The above analysis also provides another property of the solution to (10). This property is that the solution for any nodes along the shortest path from F to B is fixed, regardless of the regularization method employed. Formally, if d_u^F+d_u^B=ρ⁻¹, meaning that node u lies on a shortest path between F and B then ρd_u^B=ρ(ρ⁻¹−d_u^F)=1−ρd_u^F, which implies that x_u is fixed. The ambiguous region is illustrated in FIG. 4 for three images: A blank (uniform)

image, a weak boundary image and a natural image. Note that an 8-connected lattice was employed.

[0071] Various methods may be implemented for regularizing (10) to yield a unique solution, for example, the use of the other two norms (l₁ and l₂) as regularizers 903 for solving the degeneracy problem 904. Employing the other two norms as regularizers offers one avenue for combining the l_∞ method with Graph Cuts or Random Walker.

[0072] l₁ Regularization 903: one choice for regularization finds a solution which, among all solutions with l_∞(x) minimum, also minimizes l₁ (x). This approach does not solve the degeneracy problem 904, as illustrated with FIG. 3. Here, it can be seen that all solutions minimizing l₁ (x) have l_∞ (x)=1 (the minimum), which means this solution may be obtained by other methods.

[0073] l₂ Regularization 903: A second exemplary approach to solving the degeneracy problem of (10) 904 can be found by searching for the solution which has the minimum l_∞ value and minimizes l₂, if this is rewritten as an optimization problem:
min x^T A^T C Ax, s.t. x_F=1, x_B=0, w_ij|x_i−x_j|≦ρ, ∀e_ij ε E,  (19)
which is a quadratic programming problem. Note that since it is assumed that the graph G is connected, the addition of boundary conditions x_F=1 and x_B=0 cause A^TCA to be positive definite. If it is further assumed that there exists two different optimal solutions, x₁ and x₂, then this implies that every x=θx₁+(1−θx₂), ∀θε (0,1), ∀θε (0,1) is also an optimal solution. Such a situation would imply that A^TCA is still singular with the foreground and background constraints, which is a contradiction. Therefore the solution obtained by l₂ regularization is unique. This l₂ regularization is used to generate segmentation results for the l_∞ method.

[0074] In order to solve the quadratic programming problem of (19), a conjugate gradient may be used based active set method. Results for l₂ regularized l_∞ minimization problems are obtained using this solver.

[0075] Exemplary results for all three seeded image segmentation methods discussed in this paper: Graph Cuts (l₁ minimization), Random Walker (l₂ minimization), and l_∞ minimization with l₂ regularization were determined. In all images, β is taken as 50² for the edge weight computation given in (5). The behavior of these methods on synthetic images has been investigated as well as results with real images.

[0076] Turning to the study the behavior of these methods on weak boundary images. The weak boundary images are known to be solvable by both the Random Walker and Graph Cuts methods. Here, it is shown that the regularized l_∞ minimization method shares this property. The segmentation results for a broken line are shown in FIGS. 5A-D. It can be seen that all three methods are able to complete the weak boundary. The minimum foreground and background segmentations allowed by l_∞ minimization for this image are also shown in FIG. 4(b).

[0077] Referring to the dependency of segmentations on the seed locations; By its formulation, the Graph Cuts method is expected to be the least sensitive to seed placement, while the Random Walker method is expected to exhibit slightly more sensitivity to seed location. Since the l_∞ minimization method depends on the shortest path between the foreground and background seeds, a greater sensitivity to seed location might be expected. The experiment in FIG. 6 confirms that this is indeed the case. Although the segmentation from the l_∞ minimization is more affected by the seed placement, the segmentation is still qualitatively similar.

[0078] The effects of noise on the three methods has been compared. Uniform noise was added in the range [0, ¼] to the weak boundary image presented in FIGS. 5A-D. The results for this segmentation are given in FIGS. 7A-D. The l₁ method (Graph Cuts) is driven toward a small (minimal) cut as noise increases, while the l₂ method (Random Walker) is driven toward a segmentation resembling Voronoi cells. In contrast, the l_∞ method maintains its solution.

[0079] For real images, it can be seen from the results in FIGS. 8Ai-Cv that the l_∞ minimization method (FIGS. 8Ci-v) is able to give “tighter” segmentations than the Random Walker method (FIGS. 8Bi-v) without suffering from the shrinking property of Graph Cuts (FIGS. 8Ai-v). In order to shed more light on this case, FIG. 4C shows the ambiguous region in the l_∞ method for the image in FIG. 8Ci. As shown in FIG. 4C, the minimum segmentation property of the l_∞ minimization places minimal foreground segmentation in some areas declared as background by the Graph Cut method, thus avoiding the shrinking problem.

[0080] Referring to FIGS. 4A-C, although the l_∞ algorithm produces a solution that may be achieved used other methods, the segmentation boundary must lie within a certain “ambiguous region” that is simple to compute. In these fig ures, the red region illustrates this “ambiguous region” in which the segmentation may take either a foreground or background label. Regardless of the regularizer, pixels inside the blue region must take a foreground label and pixels inside the green region must take a background label. Note that the blue and green regions always touch at a point that is halfway along the (weighted) shortest path between the foreground and background seeds. The saturated blue and green pixels indicate the foreground/background seed locations.

[0081] It is to be understood that the present invention may be implemented in various forms of hardware, software, firmware, special purpose processors, or a combination thereof. In one embodiment, the present invention may be implemented in software as an application program tangibly embodied on a program storage device. The application program may be uploaded to, and executed by, a machine comprising any suitable architecture.

[0082] Referring to FIG. 10, according to an embodiment of the present invention, a computer system 1001 for seeded image segmentation using l_∞ minimization can comprise, inter alia, a central processing unit (CPU) 1002, a memory 1003 and an input/output (I/O) interface 1004. The computer system 1001 is generally coupled through the I/O interface 1004 to a display 1005 and various input devices 1006 such as a mouse and keyboard. The support circuits can include circuits such as cache, power supplies, clock circuits, and a communications bus. The memory 1003 can include random access memory (RAM), read only memory (ROM), disk drive, tape drive, etc., or a combination thereof. The present invention can be implemented as a routine 1007 that is stored in memory 1003 and executed by the CPU 1002 to process the signal from the signal source 1008. As such, the computer system 1001 is a general purpose computer system that becomes a specific purpose computer system when executing the routine 1007 of the present invention.

[0083] The computer platform 1001 also includes an operating system and micro instruction code. The various processes and functions described herein may either be part of the micro instruction code or part of the application program (or a combination thereof) which is executed via the operating system. In addition, various other peripheral devices may be connected to the computer platform such as an additional data storage device and a printing device.

[0084] It is to be further understood that, because some of the constituent system components and method steps depicted in the accompanying figures may be implemented in software, the actual connections between the system components (or the process steps) may differ depending upon the manner in which the present invention is programmed. Given the teachings of the present invention provided herein, one of ordinary skill in the related art will be able to contemplate these and similar implementations or configurations of the present invention.

[0085] The seeded image segmentation given by the method given by FIG. 1 has been described which is based on the minimization of l_q norms. It has been shown that two seeded image segmentation methods, Graph Cuts and Random Walker, correspond to the parameter choices of q=1 and q=2 in FIG. 1. Another case of q→∞ proved to be segmentation based on a minimal Lipschitz extension. Although the solution of this problem is degenerate, it has been shown that it is possible to produce a minimal and maximal segmentation, depending on the choice of regularization. In order to solve the associated degeneracy problem, regularization with l₂ may be used. The general method is able to find “tighter” segmentations than the Random Walker method while not suffering from the “small cuts” problem associated with the Graph Cuts method.

[0086] Having described embodiments for a system and method for seeded image segmentation using l_∞ minimization, it is noted that modifications and variations can be made by persons skilled in the art in light of the above teachings. It is therefore to be understood that changes may be made in the particular embodiments of the invention disclosed which are within the scope and spirit of the invention as defined by the appended claims. Having thus described the invention with the details and particularity required by the patent laws, what is claimed and desired protected by Letters Patent is set forth in the appended claims.