CN103310450B - A kind of image partition method merging direct-connected commensurability bundle - Google Patents

Abstract

The invention discloses a kind of image partition method merging direct-connected commensurability bundle, belong to the crossing domains such as computer vision, computer graphics, image procossing.First pass through the user interface of application program, before interactive specified portions, background.Before then setting up specified portions, the color model of background.It is configured to figure G and the energy function of segmentation.Energy function comprises color constraint and gradient constraint, and direct-connected commensurability bundle proposed by the invention.Finally, employing figure cuts Algorithm for Solving function minimum, obtains segmentation result.If user can add front background clue again to segmentation result is dissatisfied, flow process repetitive cycling performs, until obtaining satisfied segmentation effect.Present invention firstly provides the dividing method merging direct-connected commensurability bundle, compare only color and the traditional method of gradient constraint, on the premise of identical interactive quantity, the present invention is when processing from UNICOM's Object Segmentation, and segmentation effect is more preferable.

Description

A kind of image partition method merging direct-connected commensurability bundle

Technical field

The invention belongs to the crossing domains such as computer vision, computer graphics, image procossing, relate to a kind of fusion direct-connected The interactive image segmentation method of commensurability bundle.

Background technology

Interactive image segmentation be by before the mutual specified portions of a small amount of user, background, then utilize algorithm realize will sense The process that the object of interest splits from image.Image segmentation can be applicable to image synthesis, production of film and TV, and medical science The fields such as graphical analysis.Used by interactive image segmentation, optimized algorithm type is various.Wherein, energy can be obtained owing to figure cuts algorithm The optimal solution of flow function and obtain extensive concern.

It is currently based on figure and cuts the interactive image segmentation method of algorithm, need user's interactive mode to specify a small amount of fore/background picture Element or super-pixel, in order to set up the distribution of color of fore/background.Then, set up energy function, comprise: 1) color constraint, 2) gradient Constraint.Mostly be from UNICOM in view of object to be split, and color and gradient constraint not from terms of UNICOM in addition about Bundle.Retrain from UNICOM if can add, it will improve effect and the efficiency of partitioning algorithm.Work on hand also has by connectedness about Bundle incorporates in energy function.But, these connection constraints are excessively complicated, had a strong impact on calculating speed.

Summary of the invention

It is an object of the invention to explore simply but effectively connect constraint, and merge the dividing method of connection constraint, carry The efficiency of high cutting procedure.

For achieving the above object, the present invention adopts the following technical scheme that: user's user interface by application program, alternately Before formula specified portions, background.Then, before setting up specified portions, the color model of background.It is configured to figure G and the energy of segmentation Flow function.Energy function comprises color constraint and gradient constraint, and direct-connected commensurability bundle proposed by the invention.Finally, use Figure cuts Algorithm for Solving function minimum, obtains segmentation result.If user can add front background again to segmentation result is dissatisfied Clue, flow process repetitive cycling performs, until obtaining satisfied segmentation effect.

Compared with prior art, the innovation of the present invention is: propose to merge the dividing method of direct-connected commensurability bundle first. Comparing only color and the traditional method of gradient constraint, on the premise of identical interactive quantity, the present invention is processing from UNICOM's object During segmentation, segmentation effect is more preferable.

Accompanying drawing explanation

Fig. 1 is method flow diagram involved in the present invention；

Fig. 2 is that straight connected region involved in the present invention calculates schematic diagram；

Fig. 3 is multizone direct-connected commensurability bundle schematic diagram；

Fig. 4 is application example experimental result of the present invention: (a) is classified as the image of input and the inventive method and control methods Before Suo Yong, background clue, dark color is prospect, and light color is background；B () is classified as the segmentation result of the present invention；C () row are to analogy The segmentation result of method.

Detailed description of the invention

The present invention will be further described with detailed description of the invention below in conjunction with the accompanying drawings.

The flow process of the present invention is as it is shown in figure 1, specifically include following steps:

Step one, before interpolation, background clue.

After reading in piece image, user is by background pixel before the specified portions of interface.The present invention uses Yin Li et al. The side used in the paper " lazy snapping " delivered on " ACM Transactions on Graphics " for 2004 Formula, i.e. by input equipments such as mouse, touch screen or writing pencils, delineates the lines of different colours on image, carrys out specifying part Before Fen, background pixel.As shown in Fig. 4 (a) arranges, the pixel that dark strokes covers belongs to prospect, and the pixel that light color lines cover belongs to In background.

Step 2, structural map and energy function.

Image can be expressed as a non-directed graph G=<ν, ε>.ν is the node set in figure G, and ε is the set on limit.In figure G Each node p (p ∈ v), the super-pixel after a pixel of correspondence image or over-segmentation.Assuming that before the interactive part demarcated Scene element belongs to set F, and background pixel belongs to set B, and rest of pixels belongs to set U, then image segmentation can be considered a binary Labelling problem, each node one the unique labelling l of distribution being in set U_p, l_p{ 1,0} represents prospect and the back of the body to ∈ respectively Scape.Above-mentioned labelling assignment problem can solve by minimizing following energy function:

$E\left(L\right)=\underset{p\&Element;v}{\mathrm{\&Sigma;}}{E}_1\left(l_p\right)+\mathrm{\&lambda;}\underset{(p,q)\&Element;\mathrm{\&epsiv;},l_p\&NotEqual;l_q}{\mathrm{\&Sigma;}}{E}_2\left(l_{p,}{l}_q\right)+\underset{p\&Element;\mathrm{\&alpha;}}{\mathrm{\&Sigma;}}{E}_3\left(l_p\right)$

In formula, E₁(l_p) and E₃(l_p) it is unit item, represent and node p (p ∈ ν) is labeled as l_p∈ { cost when 1,0}, E₂ (l_p,l_q) it is binary item, for representing cost when neighbor takes not isolabeling respectively；λ is weight.

Functionally, E₁(l_p)、E₂(l_p,l_q) and E₃(l_p) it is called again color bound term, gradient constraint item and straight Connection geometrical constraint item.According to E₁(l_p) definition, the color of node p is the biggest with the color similarity of the foreground part specified, then l_pThe probability taking prospect labelling is the biggest, i.e. l_p=1；Vice versa.According to E₂(l_p,l_q) definition, the gradient between adjacent node Being worth the biggest, the probability as partitioning boundary is the biggest.According to E₃(l_p) definition, the node running counter to direct-connected commensurability bundle will directly be marked It is designated as background.Due to E₃(l_p) it is to obligate, the size of weight λ does not produce impact to it.Therefore, λ is only used for regulating E₂(l_p, l_q) relative to E₁(l_p) importance.The present invention tests setting constant λ=1000.By E₁(l_p) and E₂(l_p,l_q) it is referred to as non-geometric Bound term, E₃(l_p) it is referred to as geometrical constraint item.

(1) definition non-geometric bound term

For E₁(l_p), the present invention uses Yin Li et al. in 2004 at " ACM Transactions on Graphics " on definition mode in the paper " lazy snapping " delivered: first, by the pixel in F and B is carried out K-means clusters, and obtains 64 prospect classes bunchWith 64 background classes bunchThen, by E₁(l_p) fixed Justice is:

$\left\{\begin{array}{ccc}{E}_1(l_p=1)=0& E_1(l_p=0)=\&infin;& \&ForAll;p\&Element;F\\ E_1(l_p=1)=\&infin;& E_1(l_p=0)=0& \&ForAll;p\&Element;B\\ E_1(l_p=1)=f_1(D_p^F,D_p^B)& E_1(l_p=0)=f_0(D_p^F,D_p^B)& \&ForAll;p\&Element;U\end{array}\right.$

$f_1(D_p^F,D_p^B)=\frac{D_p^F}{D_p^F+D_p^B}$

$f_0(D_p^F,D_p^B)=\frac{D_p^B}{D_p^F+D_p^B}$

In formula,Representing the distance that pixel p is distributed to front, background color respectively, its expression formula is respectively as follows:

$D_p^F=\underset{k=1,...,64}{\min }\left|\right|C_p-C_k^F\left|\right|$

$D_p^B=\underset{k=1,...,64}{\min }\left|\right|C_p-C_k^B\left|\right|$

Gradient constraint item E₂(l_p,l_q) it is defined as:

$E_2(l_p,l_q)=\frac{1}{1+D_{p,q}^2}$

In formula, D_p,q=| | C_p-C_q| | represent the colour-difference between node p and q.

(2) direct-connected logical geometrical constraint item is defined

The definition of direct-connected logical geometrical constraint item is also based on the lines of user's input, and its ultimate principle is: if pixel p quilt Background line covers, and the central point for any prospect line is invisible, then it is assumed that p runs counter to direct-connected commensurability bundle, and p is directly labeled as the back of the body Scape, i.e. l_p=0.

E₃(l_p) it is defined as:

E₃(l_p=1)=∞, E₃(l_p=0)=0,

This bound term specifies that the pixel being positioned at α region is judged to background pixel by rigid.Region alpha is defined as the district that is blocked Territory, i.e. for any prospect lines central point, the node within region alpha is the most invisible.

As in figure 2 it is shown, in the case of only background line and a prospect line, by the prospect line of user's labelling Heart point is expressed as O, the beginning and end of background line is designated as X and Y, ray OX and OY respectively and defines a piece of fan expanded outwardly Shape region, sector region has been further separated into two parts α and β by straight line XY.For any one pixel p, it is judged that whether it The method belonging to α region is as follows:

1) if as in figure 2 it is shown, ∠ XOY ＞ ∠ pOX and ∠ XOY ＞ ∠ pOY, then p ∈ α ∪ β, i.e. ray OX enclose with ray OY The sector region become.

2) if p is ∈ α ∪ β, and ∠ pYO ＞ ∠ XYO, then p ∈ α, i.e. pixel p belong to α region (such as the light gray in Fig. 2 Region).

On same piece image, often have a plurality of prospect lines and background lines, for M bar prospect line and N bar background Line (as it is shown on figure 3, M=1, N=2), the α region after superposition is represented by:

α=(α₁₁∪α₁₂∪...∪α_1n∪...∪α_1N)∪(α₂₁∪α₂₂∪...∪α_2n∪...∪α_2N)

∪...∪(α_M1∪α_M2∪...∪α_mn∪...∪α_MN)

In formula, α_mnRepresent the region that is blocked that the m article prospect lines and nth bar background lines are formed.

Step 3, employing figure cuts algorithm and seeks the optimal solution of energy function.

The present invention uses Yuri Boykov et al. to deliver on " IEEE Transaction on PAMI " in 2004 Paper " An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision " proposed in figure cut algorithm, seek the optimal solution of energy function, obtain segmentation result.With Family, as being unsatisfied with segmentation effect, can return to step one, before continuing to add, background clue.Often add lines, be either Specified portions prospect or background, all will trigger the cutting procedure of Single cell fusion direct-connected commensurability bundle.

An application example of the present invention is given below.

This experiment with the dividing method without direct-connected commensurability bundle, i.e. Yin Li et al. in 2004 at " ACM Transactions on Graphics " on the method that proposes in the paper " lazy snapping " delivered be contrast object.Note Meaning, figure is all defined in pixel scale by this experiment.Fig. 4 is segmentation effect contrast.Fig. 4 (a) is the image and this inputted Before used by inventive method and control methods, background clue, dark color is prospect, and light color is background；Fig. 4 (b) is dividing of the present invention Cut result；Fig. 4 (c) is the segmentation result of control methods.It is seen that on the premise of identical interactive quantity, the present invention's Method can obtain complete cutting object.And a part of error flag of background area is often prospect by control methods, A part such as the background Folium Alangii in 4 (c) is labeled as prospect by mistake.Large stretch of background area in little STOWAGE PLAN is also by mistake terrestrial reference It is designated as prospect.

Claims (1)

1. the image partition method merging direct-connected commensurability bundle, it is characterised in that comprise the following steps:

Step one, before interpolation, background clue；

After reading in piece image, use the input equipments such as mouse, touch screen or writing pencil, by delineating different face on image Before the lines specified portions of color, background pixel；

Step 2, structural map and energy function；

Image can be expressed as a non-directed graph G=<ν, ε>, ν is the node set in figure G, and ε is the set on limit；Figure G in every Super-pixel after one pixel of individual node p (p ∈ v) correspondence image or over-segmentation；Assuming that the interactive part prospect picture demarcated Element belongs to set F, and background pixel belongs to set B, and rest of pixels belongs to set U, then image segmentation can be considered a binary flag Problem, each node one the unique labelling l of distribution being in set U_p∈ { 1,0}, l_p=1 represents prospect, l_p=0 represents Background；Above-mentioned labelling assignment problem can solve by minimizing following energy function:

$E\left(L\right)=\underset{p\&Element;v}{\&Sigma;}{E}_1\left(l_p\right)+\mathrm{\&lambda;}\underset{(p,q)\&Element;\mathrm{\&epsiv;},l_p\&NotEqual;l_q}{\&Sigma;}{E}_2(l_p,l_q)+\underset{p\&Element;\mathrm{\&alpha;}}{\&Sigma;}{E}_3\left(l_p\right)---\left(1\right)$

In formula, E₁(l_p) and E₃(l_p) it is unit item, represent and node p (p ∈ ν) is labeled as l_p∈ { cost when 1,0}, E₂(l_p, l_q) it is binary item, for representing cost when neighbor takes not isolabeling respectively；λ is weight；

E₁(l_p)、E₂(l_p,l_q) and E₃(l_p) it is called again color bound term, gradient constraint item and direct-connected logical geometrical constraint item；Press According to E₁(l_p) definition, the color of node p is the biggest with the color similarity of the foreground part specified, l_pTake the possibility of prospect labelling Property is the biggest, i.e. l_p=1；Vice versa；According to E₂(l_p,l_q) definition, the Grad between adjacent node is the biggest, as segmentation side The probability on boundary is the biggest；According to E₃(l_p) definition, the node running counter to direct-connected commensurability bundle will be directly labeled as background；E₃(l_p) be Obligating, the size of weight λ does not produce impact to it, and λ is only used for regulating E₂(l_p,l_q) relative to E₁(l_p) importance；

(1) definition color bound term, gradient constraint item E₁(l_p) and E₂(l_p,l_q)；

For E₁(l_p), first, by the pixel in F and B is carried out K-means cluster, obtain 64 prospect classes bunchWith 64 background classes bunchThen, by E₁(l_p) it is defined as:

$\left\{\begin{array}{ccc}{E}_1(l_p=1)=0& E_1(l_p=0)=\mathrm{\&infin;}& \&ForAll;p\&Element;F\\ E_1(l_p=1)=\mathrm{\&infin;}& E_1(l_p=0)=0& \&ForAll;p\&Element;B\\ E_1(l_p=1)=f_1(D_p^F,D_p^B)& E_1(l_p=0)=f_0(D_p^F,D_p^B)& \&ForAll;p\&Element;U\end{array}\right.$

$f_1(D_p^F,D_p^B)=\frac{D_p^F}{D_p^F+D_p^B}$

$f_0(D_p^F,D_p^B)=\frac{D_p^B}{D_p^F+D_p^B}$

In formula,Representing the distance that pixel p is distributed to front, background color respectively, its expression formula is respectively as follows:

$D_p^F=\underset{k=1,\mathrm{..},64}{min}\left|\right|C_p-C_k^F\left|\right|$

$D_p^B=\underset{k=1,\mathrm{..},64}{min}\left|\right|C_p-C_k^B\left|\right|$

E₂(l_p,l_q) it is defined as:

$E_2(l_p,l_q)=\frac{1}{1+D_{p,q}^2}$

In formula, D_p,q=| | C_p-C_q| | represent the colour-difference between node p and q；C_p、C_qRepresent the color value of node p and q respectively；Represent the color value of kth class bunch in prospect class bunch and background classes bunch respectively；

(2) direct-connected logical geometrical constraint item E is defined₃(l_p)

The definition of direct-connected logical geometrical constraint item is also based on the lines of user's input, and its ultimate principle is: if pixel p is by background Line covers, and the central point for any prospect line is invisible, then it is assumed that p runs counter to direct-connected commensurability bundle, and p is directly labeled as background, I.e. l_p=0；

E₃(l_p) it is defined as:

$E_3(l_p=1)=\mathrm{\&infin;},E_3(l_p=0)=0,\&ForAll;p\&Element;\mathrm{\&alpha;}$

This bound term specifies that the pixel being positioned at α region is judged to background pixel by rigid；Region alpha is defined as the region that is blocked, I.e. for any prospect lines central point, the node within region alpha is the most invisible；

In the case of only background line and a prospect line, the central point of the prospect line of labelling is expressed as O, by background The beginning and end of line is designated as X and Y, ray OX and OY respectively and defines a piece of sector region expanded outwardly, and straight line XY will fan Shape region has been further separated into two parts α and β；For any one pixel p, it is judged that whether it belongs to the method in α region such as Under:

1) if ∠ XOY ＞ ∠ pOX and ∠ XOY ＞ ∠ pOY, then p ∈ α ∪ β, the sector region that i.e. ray OX surrounds with ray OY；

2) if p is ∈ α ∪ β, and ∠ pYO ＞ ∠ XYO, then p ∈ α, i.e. pixel p belong to α region；

On same piece image, for M bar prospect line and N bar background line, the α region after superposition is represented by:

α=(α₁₁∪α₁₂∪...∪α_1n∪...∪α_1N)∪(α₂₁∪α₂₂∪...∪α_2n∪...∪α_2N)

∪...∪(α_M1∪α_M2∪...∪α_mn∪...∪α_MN)

In formula, α_mnRepresent the region that is blocked that the m article prospect lines and nth bar background lines are formed；

Step 3, employing figure cuts algorithm and seeks the optimal solution of energy function；

Use Y figure to cut algorithm and seek the optimal solution of energy function (1), obtain segmentation result；As segmentation effect is unsatisfied with, can return to Step one, continue add before, background clue；Often add lines, either for specified portions prospect or background, all incite somebody to action Trigger the cutting procedure of Single cell fusion direct-connected commensurability bundle.