CN103198470B - Image cutting method and image cutting system - Google Patents

Abstract

The invention provides an image segmentation method and system. Wherein, the method includes the following steps: providing the image to be segmented; obtaining any foreground point and background point from the pixels of the image to be segmented, and calibrating the foreground point and the background point; and background points to construct a flow network graph; use the push-in relabeling method to process the flow network graph to obtain the minimum cut set, where the minimum cut set is the segment that needs to be disconnected in the flow network graph to divide the image to be segmented into foreground and background A set of edges with the smallest similarity; and the image to be segmented is divided into a foreground area and a background area according to the minimum cut set. According to the method of the embodiment of the present invention, by constructing the flow network diagram of the image to be recognized, and pressing and relabeling it, the complexity of the algorithm is simplified, and it is applicable to all images, which is convenient for users to use.

Description

Image segmentation method and system

technical field

The present invention relates to the technical field of image segmentation, in particular to an image segmentation method and system.

Background technique

A digital image refers to an image represented in the form of a two-dimensional array. Digital images can be generated by many different input devices and technologies, for example, digital cameras, scanners, coordinate measuring machines, etc. At first, computers were used to process graphics and image information. Today, digital image processing has a wide range of applications in many fields such as national defense, industrial and agricultural production, and life and entertainment.

Image segmentation refers to the process of subdividing a digital image into a collection of pixels in multiple image sub-regions. Its purpose is to simplify or change the representation of the image, making the image easier to understand and analyze. Practical applications of image segmentation include medical imaging, locating objects in satellite images, face recognition, traffic control systems, etc.

The research on image segmentation algorithms has a history of several decades, and thousands of various types of segmentation algorithms have been proposed with the help of various theories. However, most of these methods are specific to specific problems, so they cannot be applied to all images, and the complexity of existing image segmentation algorithms is relatively high.

Contents of the invention

The object of the present invention is to solve at least one of the above-mentioned technical drawbacks.

In order to achieve the above object, an embodiment of the present invention proposes an image segmentation method, including the following steps: providing an image to be segmented; obtaining any foreground point and background point from the pixels of the image to be segmented, and The foreground points and background points are calibrated; the flow network graph is constructed according to the pixels of the image to be segmented and the calibrated foreground points and background points; A cut set, wherein the minimum cut set is a set of edges with the minimum similarity that the image to be segmented is divided into foreground and background in the flow network diagram; and according to the minimum cut set, the The image to be segmented is divided into a foreground area and a background area.

According to the method of the embodiment of the present invention, by constructing the flow network diagram of the image to be recognized, and pressing and relabeling it, the complexity of the algorithm is simplified, and it is applicable to all images, which is convenient for users to use.

In an example of the present invention, in the flow network graph, the weight of the edge between each pixel point and its adjacent pixel points is W(p, q), and the weight of the edge between the adjacent points of the source point and the sink point The weights of the edges between other pixel points of the point and the source point and the weights of the edges between the adjacent points of the sink point and other pixel points of the source point and the sink point are constants, wherein the source The point is the foreground point, and the sink point is the back point.

In an example of the present invention, the weight W(p,q) between the adjacent pixels is represented by the following formula, Among them, dist(p,q) represents the distance between p and q, σ represents the adjustment parameter, I _p represents the brightness of point p, and I _q represents the brightness of point q.

In an example of the present invention, the constant is represented by the following formula, Among them, N(p) represents the adjacent point set of point p, V represents the set of pixel points, and W(p, q) represents the weight of the edge between point p and q.

In order to achieve the above purpose, an embodiment of the present invention proposes an image segmentation system on the other hand, including: an acquisition module, used to provide an image to be segmented; a calibration module, used to obtain any pixel point from the image to be segmented Foreground points and background points, and the foreground points and background points are calibrated; a construction module is used to construct a flow network diagram according to the pixel points of the image to be segmented and the marked foreground points and background points; a processing module, It is used to process the flow network diagram by using the push-in relabeling method to obtain a minimum cut set, wherein the minimum cut set is to divide the image to be segmented into foreground and background in the flow network diagram. A set of edges with the smallest similarity; and a segmentation module, configured to segment the image to be segmented into a foreground area and a background area according to the minimum cut set.

In an example of the present invention, in the flow network diagram, the weight of the edge between each pixel and its adjacent pixels is W(p, q), and the adjacent points and sink points of the source point are divided The weights of the edges between other pixel points of and the source point and the weights of the edges between other pixel points except the adjacent points of the sink point and the source point and the sink point are constant, wherein the source point is the foreground point, and the sink point is the back point.

In an example of the present invention, the weight W(p,q) between the adjacent pixels is represented by the following formula, Among them, sist(p,q) represents the distance between p and q, σ represents the adjustment parameter, I _p represents the brightness of point p, and I _q represents the brightness of point q.

In an example of the present invention, the constant is represented by the following formula, Among them, N(p) represents the adjacent point set of point p, V represents the set of pixel points, and W(p, q) represents the weight of the edge between point p and q.

According to the system of the embodiment of the present invention, by constructing the flow network diagram of the image to be recognized, and pressing and relabeling it, the complexity of the algorithm is simplified, and it is applicable to all images, which is convenient for users to use.

Additional aspects and advantages of the invention will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention.

Description of drawings

The above and/or additional aspects and advantages of the present invention will become apparent and easy to understand from the following description of the embodiments in conjunction with the accompanying drawings, wherein:

Fig. 1 is the flow chart of the segmentation method of an image according to one embodiment of the present invention;

FIG. 2 is a schematic diagram of edge division of an image to be segmented according to an embodiment of the present invention;

FIG. 3 is a schematic diagram of segmentation of an image to be segmented according to an embodiment of the present invention; and

Fig. 4 is a structural block diagram of an image segmentation system according to an embodiment of the present invention.

detailed description

Embodiments of the present invention are described in detail below, and examples of the embodiments are shown in the drawings, wherein the same or similar reference numerals denote the same or similar elements or elements having the same or similar functions throughout. The embodiments described below by referring to the figures are exemplary only for explaining the present invention and should not be construed as limiting the present invention.

Fig. 1 is a flowchart of a method for classifying similar images according to an embodiment of the present invention. As shown in Figure 1, the similar image classification method according to the embodiment of the present invention includes the following steps:

Step S101, providing an image to be segmented.

Step S102, obtaining arbitrary foreground points and background points from the pixels of the image to be segmented, and marking the foreground points and background points.

Specifically, a foreground point and a background point are arbitrarily determined in the image to be segmented. An interactive method or prior knowledge can be used, such as extracting a point from the four corners and the center area as the background and foreground points respectively.

Step S103, constructing a flow network graph according to the pixel points of the image to be segmented and the marked foreground points and background points.

Specifically, the set of all pixels in the image to be segmented is the vertex set V, and the former point of view S is used as the source point, and the background point T is used as the sink point to construct a flow network graph G=<V, E>. The flow network graph G is an undirected weighted graph, and the weight of the edge E represents the maximum flow that the edge can pass.

The edge set E of the flow network graph G is composed of an edge between each pixel point and each adjacent pixel point, where the adjacent definition can be 4 neighborhoods (up, down, left, right) or 8 neighborhoods (4 Neighborhood plus upper left, lower left, upper right, lower right), for example, in Figure 2, the adjacent edges are represented by thin solid lines. The edge weight between two adjacent points p and q in the image to be segmented is W(p, q), which can be expressed by the following formula, Among them, dist(p,q) represents the distance between p and q, σ represents the adjustment parameter, I _p represents the brightness of point p, and I _q represents the brightness of point q. The distance dist(p,q) can be obtained by the Euclidean distance formula City distance formula dist(p,q)=|x _p -x _q |+y _p -y _q |, or chessboard distance formula dist(p,q)=max(|x _p -x _q |,|y _p - y _q |), where (x _p , y _p ) and (x _q , y _q ) represent the coordinates of point p and point q in the image, respectively.

The weight of the edge (indicated by a thick solid line in Figure 2) between the adjacent points of the source point S and other pixel points of the sink point T and the source point S and the weight of the adjacent points of the sink point T and the source point S The weight of the edge between other pixels and the sink point T (indicated by the dotted line in Figure 2) is a constant K, which can be expressed by the following formula, Among them, dist(p,q) represents the distance between p and q, σ represents the adjustment parameter, I _p represents the brightness of point p, and I _q represents the brightness of point q. The meaning of the formula here is to calculate the sum of the edge weights of a pixel and its adjacent pixels, traverse all the pixels in the image, and add 1 to the maximum value of the sum to get K.

Step S104, process the flow network graph using the push-in relabeling method to obtain a minimum cut set, where the minimum cut set is the edge with the least similarity that needs to be disconnected in the flow network graph to divide the image to be segmented into foreground and background collection.

Specifically, in constructing the flow network graph, the weight of each edge indicates the degree of similarity between the two points connected by the edge. The minimum cut set between the background point and the foreground point represents the set of edges with the least similarity that need to be disconnected to divide the flow network graph into two parts, the foreground and the background. Obtaining the minimum cut of the flow network is equivalent to obtaining the segmented image. According to the fundamental theorem of flow network graph theory, the sum of the flows of the minimum cut is equal to the maximum flow in the network. When the flow network reaches the maximum flow, all edges of a cut set will be saturated, and this cut set is the minimum cut. Therefore, solving the minimum cut is transformed into solving the maximum flow.

Push-in relabeling compares vertices to reservoirs, edges to pipes between reservoirs, and edge weights to the maximum flow that the pipes can pass through. Water flows from a source, travels through the network, and finally flows into a sink. Each reservoir has a certain height, and water can only flow to low places. The water content of each reservoir is the difference between the flow into and out of the reservoir.

p, q represent the points in the flow network graph G: the height d(p) of each point; the water content e(p) of each point; the flow F(p,q) between two points. During the solution process, the traffic on the flow network must always meet the constraints generated by the flow network graph G mentioned above. Take Figure 2 as an example. (1) When two points in the flow network graph G are directly connected by an edge, traffic is allowed between the two points. For example, traffic is allowed between ab and ac, but not between ac. (2) The flow between two points must not exceed the weight of the edge between two points, for example, F(a, b) <= W (a, b), F (S, a) <= K, where, F(p, q ) represents the flow rate between points p and q, d(p) represents the height of point p, and e(p) represents the water content of point p.

First, set the height of the source point S to a value not less than N-1 (N is the number of points in the flow network graph G), the height of the other points is set to 0, the water content of each point is set to 0, and any The flow between two points is set to 0. Then, for each point p connected to the source point S, the water content of the point is set as the upper limit of the flow between the two, that is, the weight of the edge, e(p)=W(S,p), and the two The flow between them is set as the upper limit of the flow between them, that is, F(S,p)=W(S,p). Points in the flow network diagram are pushed or relabeled. For point p and point q, the condition for pushing water from point p to point q is that point p is not source point S or sink point T; point p still has water, that is, e(p)>0; between p and q There is still a margin in the pipeline, that is, W(p,q)-F(p,q)>0; (4) The height of point q is 1 less than the height of point p, that is, d(p)-d(q)=1 .

For point p and point q, the steps to press water from point p to point q are: first, take the smaller value of the water content at point p and the amount of water that can still flow between pq, and record it as f, that is, f=min(e (p), W(p,q)-F(p,q)) Therefore, the water content at point p decreases by f, that is, e(p)=e(p)-f, and the flow between p and q increases by f, that is, F (p,q)=F(p,q)+f.

In one embodiment of the present invention, the conditions for relabeling point p are: (1) point p is not source point S or sink point T; (2) point p still has water, that is, e(p)>0; (3) The push operation cannot be performed from point p to the point connected to it. The step of relabeling point p is to first find out the point set that is connected to p and the pipeline between p and there is still a margin, which is represented by R(p), that is Then, change the height of p to the height of the lowest point in R(p) plus 1, i.e.

Repeat the operation through the above push-in or re-labeling methods, and when no point meets the push-in or re-labeling conditions, the flow on the resulting flow network graph is the maximum flow.

In the flow network diagram at this time, find the minimum cut set that can cut the flow network into two parts including the source point S and the sink point T, corresponding to the real image is where the segmentation boundary is. Specifically, in the current flow network graph, find all the edges whose flow has reached the upper limit, that is, all edges that satisfy F(p,q)=W(p,q), and step by step the edges in the order of flow from small to large Join the minimum cut set until the flow network graph is broken into two parts including source S and sink T respectively. After that, according to the order of flow from large to small, under the condition that the flow network graph can be broken into two parts, the redundant edges in the minimum cut set are gradually deleted, and finally the minimum cut set is obtained.

Step S105, segment the image to be segmented into a foreground area and a background area according to the minimum cut set.

As shown in Figure 3, when the found minimum cut set contains (S, d), (S, g), (S, h), (S, e), (S, f), (S, i), ( T, a), (T, b), (T, c), (a, d), (b, e), (c, f) twelve sides, which correspond to the image to be segmented, should be in the The position of the thickest horizontal line shown in Figure 3 is segmented, S, a, b, and c form the foreground area, and the rest of the points form the background area.

According to the method of the embodiment of the present invention, by constructing the flow network diagram of the image to be recognized, and pressing and relabeling it, the complexity of the algorithm is simplified, and it is applicable to all images, which is convenient for users to use.

Fig. 4 is a structural block diagram of an image segmentation system according to an embodiment of the present invention. As shown in FIG. 4 , the image segmentation system according to the embodiment of the present invention includes an acquisition module 100 , a calibration module 200 , a construction module 300 , a processing module 400 and a segmentation module 500 .

The acquiring module 100 is used for providing an image to be segmented.

The marking module 200 is used to obtain any foreground point and background point from the pixel points of the image to be segmented, and to mark the foreground point and the background point.

Specifically, a foreground point and a background point are arbitrarily determined in the image to be segmented. An interactive method or prior knowledge can be used, such as extracting a point from the four corners and the center area as the background and foreground points respectively.

The construction module 300 is used to construct a flow network graph according to the pixel points of the image to be segmented and the marked foreground points and background points.

Specifically, the set of all pixels in the image to be segmented is the vertex set V, and the former point of view S is used as the source point, and the background point T is used as the sink point to construct a flow network graph G=<V, E>. The flow network graph G is an undirected weighted graph, and the weight of the edge E represents the maximum flow that the edge can pass.

The edge set E of the flow network graph G is composed of an edge between each pixel point and each adjacent pixel point, where the adjacent definition can be 4 neighborhoods (up, down, left, right) or 8 neighborhoods (4 Neighborhood plus upper left, lower left, upper right, lower right), for example, in Figure 2, the adjacent edges are represented by thin solid lines. The edge weight between two adjacent points p and q in the image to be segmented is W(p, q), which can be expressed by the following formula, Among them, dist(p,q) represents the distance between p and q, σ represents the adjustment parameter, I _p represents the brightness of point p, and I _q represents the brightness of point q. The distance dist(p,q) can be obtained by the Euclidean distance formula City distance formula dist(p,q)=|x _p -x _q |+y _p -y _q |, or chessboard distance formula dist(p,q)=max(|x _p -x _q |,|y _p - y _q |), where (x _p , y _p ) and (x _q , y _q ) represent the coordinates of point p and point q in the image, respectively.

The weight of the edge (indicated by a thick solid line in Figure 2) between the adjacent points of the source point S and other pixel points of the sink point T and the source point S and the weight of the adjacent points of the sink point T and the source point S The weight of the edge between other pixels and the sink point T (indicated by the dotted line in Figure 2) is a constant K, which can be expressed by the following formula, Among them, dist(p,q) represents the distance between p and q, σ represents the adjustment parameter, I _p represents the brightness of point p, and I _q represents the brightness of point q. The meaning of the formula here is to calculate the sum of the edge weights of a pixel and its adjacent pixels, traverse all the pixels in the image, and add 1 to the maximum value of the sum to get K.

The processing module 400 is used to process the flow network graph by using the push-in relabeling method to obtain a minimum cut set, wherein the minimum cut set is to divide the image to be segmented into foreground and background with the minimum similarity of disconnection in the flow network graph The set of edges of .

Specifically, in constructing the flow network graph, the weight of each edge indicates the degree of similarity between the two points connected by the edge. The minimum cut set between the background point and the foreground point represents the set of edges with the least similarity that need to be disconnected to divide the flow network graph into two parts, the foreground and the background. Obtaining the minimum cut of the flow network is equivalent to obtaining the segmented image. According to the fundamental theorem of flow network graph theory, the sum of the flows of the minimum cut is equal to the maximum flow in the network. When the flow network reaches the maximum flow, all the edges of a cut set will be saturated, and this cut set is the minimum cut. Therefore, solving the minimum cut is transformed into solving the maximum flow.

Push-in relabeling compares vertices to reservoirs, edges to pipes between reservoirs, and edge weights to the maximum flow that the pipes can pass through. Water flows from a source, travels through the network, and finally flows into a sink. Each reservoir has a certain height, and water can only flow to low places. The water content of each reservoir is the difference between the flow into and out of the reservoir.

p, q represent the points in the flow network graph G: the height d(p) of each point; the water content e(p) of each point; the flow F(p,q) between two points. During the solution process, the traffic on the flow network must always meet the constraints generated by the flow network graph G mentioned above. Take Figure 2 as an example. (1) When two points in the flow network graph G are directly connected by an edge, traffic is allowed between the two points. For example, traffic is allowed between ab and ac, but not between ac. (2) The flow between two points must not exceed the weight of the edge between two points, for example, F(a, b) <= W (a, b), F (S, a) <= K, where, F(p, q ) represents the flow rate between points p and q, d(p) represents the height of point p, and e(p) represents the water content of point p.

First, set the height of the source point S to a value not less than N-1 (N is the number of points in the flow network graph G), the height of the other points is set to 0, the water content of each point is set to 0, and any The flow between two points is set to 0. Then, for each point p connected to the source point S, the water content of the point is set as the upper limit of the flow between the two, that is, the weight of the edge, e(p)=W(S,p), and the two The flow between them is set as the upper limit of the flow between them, that is, F(S,p)=W(S,p). Points in the flow network diagram are pushed or relabeled. For point p and point q, the condition for pushing water from point p to point q is that point p is not source point S or sink point T; point p still has water, that is, e(p)>0; between p and q There is still a margin in the pipeline, that is, W(p,q)-F(p,q)>0; (4) The height of point q is 1 less than the height of point p, that is, d(p)-d(q)=1 .

For point p and point q, the steps to press water from point p to point q are: first, take the smaller value of the water content at point p and the amount of water that can still flow between pq, and record it as f, that is, f=min(e (p), W(p,q)-F(p,q)) Therefore, the water content at point p decreases by f, that is, e(p)=e(p)-f, and the flow between p and q increases by f, that is, F (p,q)=F(p,q)+f.

In one embodiment of the present invention, the conditions for relabeling point p are: (1) point p is not source point S or sink point T; (2) point p still has water, that is, e(p)>0; (3) The push operation cannot be performed from point p to the point connected to it. The step of relabeling point p is to first find out the point set that is connected to p and the pipeline between p and there is still a margin, which is represented by R(p), that is Then, change the height of p to the height of the lowest point in R(p) plus 1, i.e.

Repeat the operation through the above push-in or re-labeling methods, and when no point meets the push-in or re-labeling conditions, the flow on the resulting flow network graph is the maximum flow.

In the flow network diagram at this time, find the minimum cut set that can cut the flow network into two parts including the source point S and the sink point T, corresponding to the real image is where the segmentation boundary is. Specifically, in the current flow network graph, find all the edges whose flow has reached the upper limit, that is, all edges that satisfy F(p,q)=W(p,q), and step by step the edges in the order of flow from small to large Join the minimum cut set until the flow network graph is broken into two parts including source S and sink T respectively. After that, according to the order of flow from large to small, under the condition that the flow network graph can be broken into two parts, the redundant edges in the minimum cut set are gradually deleted, and finally the minimum cut set is obtained.

The segmentation module 500 is used to segment the image to be segmented into a foreground area and a background area according to the minimum cut set.

As shown in Figure 3, when the found minimum cut set contains (S, d), (S, g), (S, h), (S, e), (S, f), (S, i), ( T, a), (T, b), (T, c), (a, d), (b, e), (c, f) twelve sides, which correspond to the image to be segmented, should be in the The position of the thickest horizontal line shown in Figure 3 is segmented, S, a, b, and c form the foreground area, and the rest of the points form the background area.

According to the method of the embodiment of the present invention, by constructing the flow network diagram of the image to be recognized, and pressing and relabeling it, the complexity of the algorithm is simplified, and it is applicable to all images, which is convenient for users to use.

Although the embodiments of the present invention have been shown and described above, it can be understood that the above embodiments are exemplary and cannot be construed as limitations to the present invention. Variations, modifications, substitutions, and modifications to the above-described embodiments are possible within the scope of the present invention.

Claims (4)

1. a kind of dividing method of image is it is characterised in that comprise the following steps：

Image to be split is provided；

Obtain any foreground point and background dot from the pixel of described image to be split, and described foreground point and background are clicked through Rower is fixed；

The described foreground point of the pixel according to described image to be split and demarcation and background dot construction flow network figure, described Flow network in figure, the weight on the side between the pixel that each pixel is adjacent is W (p, q), and the consecutive points except source point The weight on side and other pixels of meeting point and described source point between and remove the consecutive points of meeting point and other pixels of source point The weight on the side between point and described meeting point is constant, and wherein, described source point is described foreground point, and described meeting point is described background Point；

Press-in weight mask method is adopted to be processed to obtain minimal cut set to described flow network figure, wherein, described minimal cut set It is that described image segmentation to be split is become foreground and background on the minimum side of the similarity disconnecting needed for described flow network in figure Set；And

According to described minimal cut set by described image segmentation to be split be foreground area and background area,

Weight W (p, q) between described neighbor pixel is represented by equation below,

$W(p,q)=\exp (-\frac{{(I_p-I_q)}^2}{2{\mathrm{\&sigma;}}^2})\&CenterDot;\frac{1}{dist(p,q)},$

Wherein, dist (p, q) represents the distance between point p and q, and σ represents regulation parameter, I_pRepresent the brightness of p point, I_qRepresent q point Brightness.

2. the dividing method of image as claimed in claim 1 is it is characterised in that described constant is represented by equation below,

$K=1+\underset{p\&Element;V}{max}\underset{q\&Element;N\left(p\right)}{\mathrm{\&Sigma;}}W(p,q),$

Wherein, N (p) represents the adjacent point set of p point, and V represents the set of pixel, and W (p, q) represents point p, the weight on side between q.

3. a kind of segmenting system of image is it is characterised in that include：

Acquisition module, for providing image to be split；

Demarcating module, for obtaining any foreground point and background dot, and to before described from the pixel of described image to be split Sight spot and background dot are demarcated；

Constructing module, the described foreground point for the pixel according to described image to be split and demarcation and background dot construction stream Network, in described flow network in figure, the weight on the side between the pixel that each pixel is adjacent is W (p, q), and removes The weight on side between other pixels of the consecutive points of source point and meeting point and described source point and the consecutive points except meeting point and source The weight on the side between other pixels of point and described meeting point is constant, and wherein, described source point is described foreground point, described remittance Point is described background dot；

Processing module, for adopting press-in weight mask method to be processed to obtain minimal cut set to described flow network figure, wherein, Described minimal cut set is to become foreground and background similar disconnect needed for described flow network in figure described image segmentation to be split Property minimum side set；And

Segmentation module, for according to described minimal cut set will described image segmentation to be split be foreground area and background area,

Weight W (p, q) between described neighbor pixel is represented by equation below,

$W(p,q)=\exp (-\frac{{(I_p-I_q)}^2}{2{\mathrm{\&sigma;}}^2})\&CenterDot;\frac{1}{dist(p,q)},$

Wherein, dist (p, q) represents the distance between point p and q, and σ represents regulation parameter, I_pRepresent the brightness of p point, I_qRepresent q point Brightness.

4. the segmenting system of image as claimed in claim 3 is it is characterised in that described constant is represented by equation below,

$K=1+\underset{p\&Element;V}{max}\underset{q\&Element;N\left(p\right)}{\mathrm{\&Sigma;}}W(p,q),$

Wherein, N (p) represents the adjacent point set of p point, and V represents the set of pixel, and W (p, q) represents point p, the weight on side between q.