CN119444792A - Interactive image segmentation method combining global seed and sparse local linear reconstruction - Google Patents

Abstract

The invention provides an interactive image segmentation method combining global seeds and sparse local linear reconstruction, which comprises the steps of introducing global seed information items to construct global seed information streams, designing sparse local linear reconstruction regular items, adopting L ₁ norms to achieve segmentation smoothness of segmentation results, simultaneously obtaining objective functions by combining the global seed information items, carrying out iterative solution on the objective functions in an ADMM mode to obtain more complete segmentation objects and achieve a sparse regional boundary segmentation effect, modifying L ₁ norms to L _p norms, converting the L _p norms to L ₁ norms in an iterative re-weighting mode to obtain solutions of minimized objective functions, and obtaining final segmentation results through a threshold method. The model constructed by the invention consists of the global seed information item and the sparse local linear reconstruction regular item, so that not only can complete semantic information be reserved, but also a sparse smoothing effect is shown when a complex image is processed, and a clearer segmentation boundary can be obtained.

Description

Interactive image segmentation method combining global seeds and sparse local linear reconstruction

Technical Field

The invention relates to the technical field of interactive image segmentation, in particular to an interactive image segmentation method combining global seeds and sparse local linear reconstruction.

Background

Image segmentation algorithms play a vital role in the fields of computer vision, pattern recognition and the like, and particularly, the application in the fields of medical image segmentation, video processing, object tracking and the like promotes the rapid development of image segmentation technology and derives a plurality of different types of segmentation algorithms.

The existing interactive image segmentation algorithm can be divided into three categories of an algorithm based on a graph cutting theory, an algorithm based on random walk and an algorithm based on deep learning. The algorithm based on graph cutting theory converts the image segmentation task into the maximum flow/minimum cutting problem in the graph theory, and the final segmentation result is obtained by minimizing the graph energy function. After a user marks part of pixels in the graph as a foreground and a background, the random walk algorithm calculates random walk probabilities from marked pixels to all non-marked pixels, and the marked pixel category with the maximum arrival probability is the category to which the non-marked pixels belong. The image segmentation algorithm based on deep learning can well express and characterize structural information of complex data through hierarchical feature representation of multi-layer network discovery data, and semantic segmentation of targets is achieved.

The main purpose of interactive image segmentation is to be able to obtain complete and well-defined objects with less user interaction of a priori information. However, the prior information obtained by the algorithm is often far apart due to the objectively existing differences between users. How to achieve more excellent segmentation performance with less interaction information is still a problem to be solved. Most of the existing algorithms are based on the principle of local linear reconstruction, and consider that each pixel point can be linearly represented by a neighborhood pixel point, and the higher the similarity between each pixel point and the neighborhood pixel point is, the greater the tag consistency possibility is, namely, the pixel point tag is only determined by the similarity between each pixel point and the neighborhood pixel. And differences exist between texture information or color information in the same target and between different targets on the image, and when the similarity degree between a far pixel point pair on the same target and between a similar pixel point pair between different targets is measured, the differences can cause the model to generate ambiguity for boundary positioning between the targets. Referring to fig. 1, when the seed information is sparse, it is generally difficult to accurately divide the complete divided object by only performing tag propagation depending on the local seed information. In many segmentation methods, unknown pixels acquire tag information through adjacent pixels, but information outside the neighborhood pixels is not utilized, namely most algorithms only consider the similarity of eight neighborhoods of the pixels in the image, but neglect the similarity of the pixels outside the eight neighborhoods of the pixels, which is one of main reasons that the image tag cannot be completely propagated. As shown in fig. 1 (a), three pixel points a to C are non-neighborhood pixel points, and the similarity between the point a and the point C is higher, and the similarity between the point a and the point B is lower. If the pixel point a is marked as a foreground point and the two points B and C are not marked, the point B may obstruct the information transmission of the point a due to the excessive pixel gap between the point a and the point B, so that the point C cannot acquire the tag information from the point a, and the transmission capability of the local seed information is weak.

In interactive image segmentation, since the object boundary occupies only a small fraction of the pixels in the entire image, there are only a small number of pixel pairs from different object regions in the local connected graph. The embedding of the above-mentioned properties is satisfied such that a subset of pixel pairs of sufficiently large distance is preserved, while the distance between any remaining pixel pairs is pushed to zero. Most of the existing interactive segmentation algorithms measure the distance between pixel points by adopting an L ₂ norm, which often results in obvious smooth change of the region boundary to cause boundary positioning errors, and moreover, the L ₂ norm does not generate sparse solution, which means that in high-dimensional data, the interpretation of the solution is poor because most of characteristic weights are non-zero.

Disclosure of Invention

Aiming at the technical problems that the existing interactive image segmentation algorithm has weaker local seed information propagation capability, and the L ₂ norm is adopted to measure the distance between pixel points without generating sparse solution and causing error in boundary positioning, the invention provides an interactive image segmentation method combining global seeds and sparse local linear reconstruction, which can not only segment more complete objects under the condition of less seed interaction, compared with the prior art, the method has excellent boundary positioning capability, and meanwhile, compared with the prior art, the combined global seed information flow and sparse regular model GSSR _p (0<p is less than or equal to 1) constructed by the method is composed of two parts of a global seed information item and a sparse local linear reconstruction regular item, so that complete semantic information can be reserved, a sparse smoothing effect is shown when a simple and complex non-texture image is processed, and a clearer segmentation boundary can be obtained.

In order to solve the technical problems, the invention adopts the following technical scheme:

An interactive image segmentation method combining global seeds and sparse local linear reconstruction, comprising the steps of:

s1, introducing a global seed information item, and constructing a global seed information stream so as to obtain a complete segmented object under the condition of sparse seeds, wherein the specific global seed information item is shown in the following formula:

wherein F represents a foreground, B represents a background, V represents a vertex set of the graph, x _i represents an unknown pixel, w _i* represents the weight from the unknown pixel to a foreground model or a background model, and x _* represents whether the pixel belongs to the foreground or the background;

S2, designing a sparse local linear reconstruction regular term based on the local linear reconstruction idea, adopting an L ₁ norm to realize the slicing smoothness of a segmentation result, and simultaneously combining the global seed information item in the step S1 to obtain a final objective function of L ₁ norm constraint, wherein the specific sparse local linear reconstruction regular term is shown as follows:

Wherein, Representing the degree of a pixel point i, N (i) representing a local set of neighbor pixel points, w _ij representing an edge weight, x _j being one of the N (i) pixel points;

the objective function is shown as follows:

Wherein X= (X ₁,x₂,…,x_n) represents the solution obtained by the objective function last, n is the total number of pixel points, lambda is a balance parameter used for balancing sparse local linear reconstruction regular term and global seed information term;

S3, carrying out iterative solution on the obtained objective function in an alternate direction multiplier method mode, and obtaining a more complete segmentation object and a more sparse region boundary segmentation effect;

S4, modifying the L ₁ norm into an L _p norm, wherein 0< p <1, converting the L _p norm into an L ₁ norm in an iterative re-weighting mode, converting the non-convex optimization problem into a convex optimization problem for solving, and obtaining a solution of a minimized objective function;

s5, obtaining a final segmentation result through a threshold method according to the obtained solution of the minimized objective function.

Further, the step S1 includes the steps of:

s11, modeling interaction information of a user by adopting a Gaussian mixture model, solving through an EM algorithm to obtain a foreground model and a background model respectively, wherein a calculation formula is shown as follows:

Wherein p _v represents the Gaussian mixture probability distribution of the background model or the foreground model, z _i represents the label of the ith observed data I _i belonging to the kth Gaussian component, v E { F, B };. Theta _v＝(π_v1,…,π_vk,θ_v1,…,θ_vk) represents the parameter set, N _vk(I_i|θ_vk)、N_vl(I_i|θ_vl) represents the Gaussian distribution determined by the parameter theta _vk、θ_vl respectively, pi _vk、π_vl represents the weights of the kth Gaussian component and the ith Gaussian component in the model v respectively, and K represents the number of the Gaussian components;

S12, calculating the probability of the picture pixel point to the foreground model and the background model, and constructing a foreground matrix and a background matrix as the distance between the unlabeled pixel point and the foreground and the background, so that the seed information can be globally transmitted, wherein the calculation formula of the distance between the unlabeled pixel point and the foreground is as follows:

The calculation formula of the distance from the unlabeled pixel point to the background is shown as follows:

Where P _F denotes the foreground model, P _B denotes the background model, k denotes the kth Gaussian component, The best model parameters representing the foreground model,The best model parameters representing the background model.

Further, the step S2 includes the steps of:

s21, calculating a graph weight model according to the input image:

the input image is recorded as I, a weight graph G= (V, E, W _E) is defined for constructing a sparse local linear reconstruction regular term, wherein V represents a vertex set of the graph, elements of the vertex set are pixels of the image, E is an edge set of all the eight adjacent pixels in eight neighborhoods, W _E is a weight set of the edges, a local neighbor pixel set N (I) = { j (I, j) epsilon E } represents all pixel sets in the eight neighborhoods of the current pixel I, and the edge weight is specifically defined as follows:

Wherein exp (·) represents an exponential function, σ=ma _(i,j)∈E||I_i-I_j||_∞, in order to ensure propagation stability, this weight calculation method ensures that the edge weight value is always a positive number and is symmetrical, that is, w _ij＝w_ji;I_i and I _j are both color vectors, and the pixel point intensity is measured by RGB or Lab color space, and the weight matrix model of the final graph is as follows:

S22, restraining the propagation of the local seed information by adopting an L ₁ norm, and combining the foreground matrix and the background matrix obtained in the step S1 to obtain a final objective function.

Further, the step S3 includes the steps of:

s31, separating marked pixel points and unmarked pixel points, and reconstructing an energy function:

To ensure that the pixel points obtained by solving the foreground and background areas obtained by the objective function are consistent with the marked pixel points, the method comprises the following steps of AndAs a constraint term for the objective function, the matrix form of the objective function can be written as follows:

Wherein l=d-W, L is a laplace matrix, D is a diagonal matrix satisfying D _ii＝d_i, 1 is an all 1 vector, W is an adjacency weight matrix, D _B and D _F represent a constructed background weight matrix and a front Jing Quan weight matrix, respectively, wherein the elements satisfy I.e.

In order to minimize the objective function and avoid the memory consumption and time overhead caused by inverting the extremely large sparse matrix, the marked pixel points and the unmarked pixel points are separated, the logic structure of the L matrix can be simply and effectively not influenced by recombining the L matrix, U represents the set of unknown pixel points, S is the set of seed pixel points,N _B、N_F、N_U represents the number of background seeds, the number of foreground seeds and the number of unlabeled pixels, respectively, whereby the objective function can be decomposed into the following formula:

wherein X _U represents the set of unlabeled pixels, The dimensions of the matrices D _B and D _F at this time are N _U×N_U,L_S determined by the rows and columns of marked pixels in the L matrix, L _U by the rows and columns of unmarked pixels, and the R matrix by the seed pixel index, the unmarked pixel index determining an adjacent weight matrix of columns, so that the objective function is further developed as:

s32, solving a reconstructed objective function by adopting an alternate direction multiplier method:

To effectively solve the above equation (17), let L _SX_S-RX_U＝d₀,L_UX_U-R^TX_S＝d₁ construct an augmented Lagrangian function by introducing a Lagrangian multiplier, then the objective function is extended to the following equation:

Wherein b ₀、b₁ is an introduced Lagrangian multiplier, ρ is a Lagrangian penalty coefficient, and ρ >0, and for solving the final objective function formula (19), the objective function only contains L ₁ norm and L ₂ norm and is free of constraint, and the derivation minimization is directly carried out.

Further, the step S4 includes the steps of:

S41, restraining sparse local linear reconstruction regular terms in the reconstructed objective function by using an L _p norm, and redefining the constrained objective function as shown in the following formula:

S42, converting the L _p norm solution into the L ₁ norm problem solution by adopting an iterative re-weighting mode, and converting each L _p norm term into the L ₁ norm to carry out constraint, wherein the specific modification of the formula (26) is as follows:

Wherein N _F represents the number of the foreground seeds, Represents one element in vector L _sX_s-RX_U, alpha _i representsN _B represents the number of background seeds, ψ _i represents one element in vector-R ^TX_s+L_UX_U, and β _i represents |ψ _i|^p-1;

converted into a diagonal matrix form II diag (beta) psi ₁, the objective function corresponding to the L _p norm is converted into the following formula:

Wherein, Psi= -R ^TX_s+L_UX_U, alpha is a vector composed of alpha _i, beta is a vector composed of beta _i, so far L _p regular embedding has been converted into L ₁ regular embedding, and in order to ensure the stability of calculation, the next round of iteration weight updating mode of the designed weight item after each round of iteration is as follows:

Where k represents the current iteration round, ε is a small positive number that prevents division by zero, and the objective function solution is converted to the same form as equation (17) and is not described here.

Further, the step S5 of obtaining the final segmentation result through the threshold method comprises binarizing the x vector into y _i∈{x_B,x_F, i epsilon V, and the threshold segmentation adopts the following rule:

Where x _F denotes a foreground pixel value, x _B denotes a background pixel value, and x _i denotes a value obtained after minimizing the objective function as a marker pixel point.

Compared with the prior art, the interactive image segmentation method combining the global seeds and the sparse local linear reconstruction has the following advantages:

1. the invention provides a new interactive segmentation model, which is characterized in that a global seed information item is introduced by fully mining seed information, a global seed information stream is constructed, the connection between the seed and the pixel points outside the neighborhood is established, the propagation capability of the seed is increased, and a complete segmentation object can be obtained under the condition of less interaction of users.

2. The invention not only considers the global propagation of seed information, but also uses sparse local linear reconstruction regularization item, and better reserves weak structure information while reserving image local structure information.

3. The method adopts L _p norm constraint output gradient to obtain a sparse smooth result, is favorable for label propagation to generate a clear boundary, adopts an Alternate Direction Multiplication Method (ADMM) to perform iterative minimization calculation on an objective function when p=1, adopts an iterative re-weighting mode to accelerate matrix operation when 0< p <1, and improves calculation efficiency and verifies effectiveness through experiments.

Drawings

Fig. 1 is a graph of segmentation results of some classical algorithms according to the present invention, which lead to segmentation difficulties due to pixel differences between different regions on the same object.

FIG. 2 is a diagram of a global seed information model constructed in accordance with the present invention.

FIG. 3 is a functional representation of the boundary positioning capability of the present invention.

Fig. 4 is a graph comparing the segmentation results of the model of the present invention using L ₁ canonical sum L _p (p=0.7) and L _p (p=0.8).

Fig. 5 is a visual comparison of the present model with the segmentation results of several classical algorithms.

FIG. 6 is a PR curve, F-score and AUC values for the present invention over a BSD dataset.

FIG. 7 is a PR curve, F-score and AUC values for the present invention on an MSRC dataset.

FIG. 8 is PR curve, F-score and AUC values for the invention using S1 seeds on the MSRC dataset.

FIG. 9 is PR curve, F-score and AUC values for the invention using S2 seeds on the MSRC dataset.

Fig. 10 is a graph of the multi-class segmentation result obtained by the present invention.

FIG. 11 is a graph of the results of the robustness analysis of the present invention at different seed placement locations.

Fig. 12 is a graph of the results of the robustness analysis under gaussian noise of the present invention.

Detailed Description

The invention is further described with reference to the following detailed drawings in order to make the technical means, the creation characteristics, the achievement of the purpose and the effect of the implementation of the invention easy to understand.

The invention provides an interactive image segmentation method combining global seeds and sparse local linear reconstruction, which comprises the following steps:

S1, a new interactive segmentation model is designed, global seed information items are introduced to construct global seed information flow, and the purpose that a complete segmentation object can be obtained under the condition of sparse seeds is achieved, wherein the specific global seed information items are shown in the following formula:

wherein F represents a foreground model, B represents a background model, V represents a vertex set of the graph, x _i represents an unknown pixel, w _i* represents a weight from the unknown pixel to the foreground model or the background model, and x _* represents whether the pixel belongs to the foreground or the background.

As a specific embodiment, the step S1 includes the following steps:

S11, modeling interaction information of a user by adopting a Gaussian mixture model, and solving through an EM algorithm to obtain a foreground model and a background model respectively:

On the spatial domain of a picture, the image is represented by a three-channel matrix (r, g, b) of n pixels. A set of seed pixels for background B and foreground F is given. The seed diffusion of the present invention is no longer limited to a localized area of the seed, but rather diffuses throughout the map, as shown in FIG. 2. In order to find out the pixel point most similar to each unknown pixel point in marked data as far as possible, the invention respectively carries out Gaussian mixture modeling for the foreground and the background and sets respective Gaussian components as K, and the probability model of the Gaussian mixture model of the background B and the foreground F is expressed as follows, wherein the color data model is constructed by adopting the Gaussian mixture model (Gaussian Mixture Model), taking account of different color information in an image:

Wherein v ε { F, B }, I _i represents the observed data; Θ _v＝(π_v1,…,π_vk,θ_v1,…,θ_vk) represents the parameter set; K represents the number of Gaussian components; pi _vk represents the weight of the kth Gaussian component in the model v; N _vk(I_i|θ_vk) represents the Gaussian distribution determined by the parameter θ _vk, N _vk(I_i|θ_vk) has the expression of mean μ _vk and covariance Σ _vk,N_vk(I_i|θ_vk):

Solving the background and background Gaussian mixture model by using an EM algorithm to obtain optimal parameters And calculating the probability that the ith observed data I _i belongs to the kth Gaussian by combining a Bayesian formula, wherein the calculation formula is shown as follows:

Where p _v represents the gaussian mixture probability distribution of the background model or the foreground model, z _i represents the label that the ith observation I _i belongs to the kth gaussian component, pi _vl represents the weight of the ith gaussian component in the model v, and N _vl(I_i|θ_vl) represents the gaussian distribution determined by the parameter θ _vl.

S12, calculating the probability from the picture pixel point to the foreground model and the background model, and constructing a foreground matrix and a background matrix as the distance from the unlabeled pixel point to the foreground and the background, so that the seed information can be globally transmitted:

Each pixel x _i can be brought into the foreground and background models by the gaussian mixture model to calculate probabilities, and weights w _iF and w _iB are defined as probabilities of the unlabeled pixel to the foreground model and the background model respectively.

The calculation formula of the distance from the unlabeled pixel point to the foreground is shown as follows:

The calculation formula of the distance from the unlabeled pixel point to the background is shown as follows:

Where P _F denotes the foreground model, P _B denotes the background model, k denotes the kth Gaussian component, Represents the best model parameters representing the foreground model,Representing the best model parameters representing the background model. Front Jing Juzhen can be constructed based on w _iF and w _iB And background matrixWherein the elements satisfyI.e.

Given the background and foreground tags x _B and x _F, respectively, the following global seed information item can be constructed based on the discussion above:

S2, designing a sparse local linear reconstruction regular term based on the local linear reconstruction idea, adopting an L ₁ norm to realize the slicing smoothness of a segmentation result, and simultaneously combining the global seed information item in the step S1 to obtain a final objective function of L ₁ norm constraint, wherein the specific sparse local linear reconstruction regular term is shown as follows:

Wherein, Representing the degree of a pixel point i, N (i) representing a local set of neighbor pixel points, w _ij representing an edge weight, x _j being one of the N (i) pixel points;

the objective function is shown as follows:

Wherein, X= (X ₁,x₂,…,x_n) represents the solution obtained by the objective function, n is the total number of pixels, and lambda is a balance parameter used for balancing the sparse local linear reconstruction regular term and the global seed information term.

As a specific embodiment, the step S2 includes the following steps:

s21, calculating a graph weight model according to the input image:

In order to construct a sparse local linear reconstruction regular term, the invention defines a weight graph G= (V, E, W _E), wherein V represents a vertex set of the graph, an element of the vertex set is a pixel point of the image, E is an edge set of all connected pixel points in eight neighborhoods, W _E is a weight set of the edge, a local neighbor pixel point set N (I) = { j (I, j) E } represents all pixel point sets in eight neighbors of the current pixel point I, The degree of the pixel i is indicated.

There are various methods for calculating the edge weight of the graph, and strategies such as pixel point intensity, image gradient and the like can be adopted. The edge weight of the invention is specifically defined as follows:

Wherein exp (·) represents an exponential function, σ=ma _(i,j)∈E||I_i-I_j||_∞, in order to ensure propagation stability, this weight calculation method ensures that the edge weight value is always a positive number and is symmetrical, that is, w _ij＝w_ji;I_i and I _j are both color vectors, and the pixel point intensity is measured by RGB or Lab color space, and the weight matrix model of the final graph is as follows:

s22, restraining the propagation of the local seed information by adopting an L ₁ norm, and combining the foreground matrix and the background matrix obtained in the step S1 to obtain a final objective function:

based on the principle of local linear reconstruction, the value of one pixel point is represented by eight neighborhood pixel points, and finally, the sparse local linear reconstruction regular term designed by the invention is shown as follows:

In combination with the step S1, the model provided by the invention finally consists of two parts, namely a global seed information item and a sparse local linear reconstruction regular item, and the objective function expression of the model is as follows:

E (X) =λE _G(X)+E_S (X) formula (13)

Wherein, X= (X ₁,x₂,…,x_n) represents the solution obtained by the final objective function, n is the total number of pixels, lambda is a balance parameter for balancing the sparse local linear reconstruction regularization term and the global seed information item, and the larger lambda indicates the larger influence of the global seed information item, E _G (X) is the global seed information item, and E _S (X) is the sparse local linear reconstruction regularization term. The segmentation task on the image is thus finally transformed to minimize the objective function E (X), i.e

And S3, carrying out iterative solution on the obtained objective function by adopting an Alternate Direction Multiplier Method (ADMM), and obtaining a more complete segmentation object and a more sparse region boundary segmentation effect.

As a specific embodiment, the step S3 includes the following steps:

s31, separating marked pixel points and unmarked pixel points, and reconstructing an energy function:

In order to effectively solve the problem of the global seed information flow and the sparse local linear reconstruction regularization algorithm, the method adopts an iteration mode of an alternate direction multiplier method to solve.

Setting ρ to 1, the objective function that can get the L ₁ norm constraint is as follows:

To ensure that the pixel points obtained by solving the foreground and background areas obtained by the objective function are consistent with the marked pixel points, the method comprises the following steps of AndAs a constraint term for the objective function, the matrix form of the objective function can be written as follows:

Wherein l=d-W, L is a laplace matrix, D is a diagonal matrix satisfying D _ii＝d_i, 1 is an all 1 vector, W is an adjacency weight matrix, D _B and D _F represent a constructed background weight matrix and a front Jing Quan weight matrix, respectively, wherein the elements satisfy I.e.

In order to minimize the objective function and avoid the memory consumption and time overhead caused by inverting the extremely large sparse matrix, the marked pixel points and the unmarked pixel points are separated, the logic structure of the L matrix can be simply and effectively not influenced by recombining the L matrix, U represents the set of unknown pixel points, S is the set of seed pixel points,N _B、N_F、N_U represents the number of background seeds, the number of foreground seeds and the number of unlabeled pixels, respectively, whereby the objective function can be decomposed into the following formula:

wherein X _U represents the set of unlabeled pixels, The dimensions of the matrices D _B and D _F at this time are N _U×N_U,L_S determined by the rows and columns of marked pixels in the L matrix, L _U by the rows and columns of unmarked pixels, and the R matrix by the seed pixel index, the unmarked pixel index determining an adjacent weight matrix of columns, so that the objective function is further developed as:

s32, solving a reconstructed objective function by adopting an alternate direction multiplier method:

For the specific L ₁ regular constraint polynomial of the present invention, namely, to effectively solve the above formula (17), let L _SX_S-RX_U＝d₀,L_UX_U-R^TX_S＝d₁, the problem is equivalent to minimizing the following formula:

By introducing Lagrangian multipliers, an augmented Lagrangian function is constructed, and the objective function is expanded to the following formula:

Wherein b ₀、b₁ is an introduced Lagrangian multiplier, ρ is a Lagrangian penalty coefficient, and ρ >0, and for solving the final objective function formula (19), the objective function only contains L ₁ norm and L ₂ norm and is free of constraint, and the derivation minimization is directly carried out.

In particular for equation (19) can be solved by iterative minimization (ADDM), wherein the minimization sub-problem steps for solving the various parameters of the problem at the k+1th iteration are as follows:

first, fix d ₀、d₁、b₀、b₁, solve for X _U:

Then finally for The solution of (2) may be translated into a solution to a system of linear equations:

Wherein, Variable(s)Are intermediate variables introduced in the ADDM algorithm.

Next, fix X _U、b₀、b₁, solve for d ₀、d₁:

the shrnk operation here may be defined as Max (·) represents the maximum function, y represents the input vector, and γ represents the penalty factor.

Finally, fix X _U、d₀、d₁, solve b ₀、b₁ d₁:

In summary, the present invention summarizes all steps of minimizing the energy function (equation 19) and deriving the unknown pixel solution in algorithm 1, where the linear system of equations for the sub-problem (solving X _U) is defined in lines 3-5, and there are three parameters λ, ρ, η in total, where η is used to control the end of the cycle, and λ and ρ function as described above. The specific algorithm 1 is as follows:

Input image g, seed information X _S, lambda, rho, eta

Output of unlabeled pixel Point set X _U

1, Initializing:

2:

3 constructing an A matrix as shown in formula (21)

4 Constructing a v vector of formula (21)

5 By solving forUpdating

6 Calculation method (22)

7 Calculating formula (23)

8 Calculating (24)

9 Calculating (25) to obtain

10:k=k+1

11:end while

12:

S4, modifying the L ₁ norm into the L _p norm, wherein 0< p <1, converting the L _p norm into the L ₁ norm in an iterative re-weighting mode, and converting the non-convex optimization problem into a convex optimization problem to solve, so as to obtain a solution of the minimized objective function.

As an example, the step S4 includes the following steps:

s41, constraint is carried out on sparse local linear reconstruction regular terms in the reconstructed objective function by using an L _p norm:

In order to improve the robustness of the algorithm and further improve the sparsity of the solution, the invention adopts L _p (0 < p < 1) regular embedding to obtain a more sparse solution, and the constrained objective function is redefined as shown in the following formula:

S42, converting the L _p norm solution into the L ₁ norm problem solution by adopting an iterative re-weighting mode, and carrying out constraint on each L _p norm item by converting the L3962 norm into the L ₁ norm:

when 0< p <1, equation (26) is a non-convex optimization problem, and when faced with a complex objective function optimization task, a sensible strategy is to attempt to transform it into a more simplified optimization problem. A class of optimization methods based on iterative re-weighting has been developed that iteratively optimizes smooth or non-smooth convex objective functions, the weights of each round being dynamically weighted by the coefficients evaluated in the previous iteration. According to the method, in order to embody the iterative re-weighting process, the invention optimally deduces an L _p solving method on the basis of L ₁. Specifically, the formula (26) is modified as shown in the following formula:

Wherein N _F represents the number of the foreground seeds, Represents one element in vector L _sX_s-RX_U, alpha _i representsN _B represents the number of background seeds, ψ _i represents one element in vector-R ^TX_s+L_UX_U, and β _i represents |ψ _i|^p-1;

converted into a diagonal matrix form II diag (beta) psi ₁, the objective function corresponding to the L _p norm is converted into the following formula:

Wherein, Psi= -R ^TX_s+L_UX_U, alpha is a vector composed of alpha _i, beta is a vector composed of beta _i, so far L _p regular embedding has been converted into L ₁ regular embedding, and in order to ensure the stability of calculation, the next round of iteration weight updating mode of the weight item after each round of iteration is as follows:

where k represents the current iteration round, ε is a small positive number and is prevented from being divided by zero, and at this time, the objective function solution is converted into the same form as the equation (17), and then only a solution method similar to the equation (17) is needed, which is not described here again.

S5, obtaining a final segmentation result through a threshold method according to the obtained solution of the minimized objective function:

Once the value of the minimized result X vector of the above formula (20) is obtained, in combination with the above known X _S vector, some simple and convenient classification algorithms can be used to help obtain the final segmentation result, such as clustering algorithms like k-means or threshold segmentation methods like Otsu, and the X vector is binarized into y _i∈{x_B,x_F }, i e V, and the specific simplest threshold segmentation can use the following rules:

Where x _F denotes a foreground pixel value, x _B denotes a background pixel value, and x _i denotes a value obtained after minimizing the objective function as a marker pixel point.

Fig. 4 shows the segmentation results on the same label using L ₁ canonical sum L _p (p=0.7) and L _p (p=0.8). From the figure, it can be seen that the L _p (p=0.8) rule can better distinguish object boundaries to obtain more accurate segmentation results, which is superior to the GSSR model of the norm constraint of L ₁ and L _p (p=0.7). Thus, to achieve more accurate results, the present invention will employ p=0.8 for subsequent experimental comparisons for the L _p (0 < p < 1) constrained GSSR model.

The invention provides a new global seed information item and sparse local linear reconstruction regular item algorithm framework, which not only can divide more complete objects under the condition of less seed interaction, but also has excellent boundary positioning capability compared with the prior method (see figure 3). To verify the necessity and rationality of adopting sparse regularization, the invention will constrain sparse gradient enhancement terms by L ₁ regularization and L _p (p=0.8) regularization, respectively.

The present invention compares GSSR ₁、GSSR_0.8 with several methods for interactive image segmentation, ：Grow Cuts(GRO),Random Walk(RW),Normalized Random Walk(NRW),Normalized Lazy Random Walk(NLRW),One Cut(ONE),Laplacian Coordinates(LC),Multi-layer Random Forest(MRF). the present invention implements all of the above comparison algorithms in MATLAB2020b programming environment, all of which have been developed and all of which employ default parameters provided by the above algorithms. In order to quantify the segmentation results of the evaluation algorithm, the invention adopts a plurality of widely used evaluation indexes, namely, rand Index (RI), information difference index (VoI), boundary Drift Error (BDE) and cross-over ratio (IOU). The invention verifies the feasibility of the GSSR framework on two well-known and GT-providing datasets, BSD dataset and MSRC dataset. Both data sets are open source and free. The MSRC dataset contains 50 natural pictures and the BSD dataset contains 500 pictures, most of them with disturbances that make segmentation more difficult, such as texture clutter and different types of lighting conditions. In order to reduce index errors caused by inconsistency of seed information of artificial subjective labels, labels provided by Andrade and Carrera are further adopted, and two different sparse seed point sets S ₁ and S ₂ on an MSRC data set further show advantages of the algorithm. In order to intuitively demonstrate the comparison between the segmentation capabilities of the above-mentioned methods and the algorithms of the present invention, fig. 5 shows the specific segmentation results of the algorithms on 9 pictures. It can be seen from the figure that although most algorithms output similar results, there are still some nuances that need to be emphasized here. In the Starfish picture, no background seed is arranged at the upper background, so that most algorithms can not handle the situation, and only ONE and GSSR _0.8 obtain a better segmentation result. In church and boat pictures, both the MRF and LC algorithms produced segmentation results that were almost inferior to GSSR _0.8. The GSSR _0.8 algorithm performs optimally when on a squirrel picture, facing a more complex background. When comparing the remaining pictures, it can be seen that both GSSR ₁ and GSSR _0.8 algorithms result in more accurate edges and more complete targets.

In order to more comprehensively show the segmentation details, the invention adopts the median, the mean and the variance to measure the four indexes RI, voI, BDE and IoU. Meanwhile, PR curve, F-score and AUC index are adopted to more comprehensively measure the boundary fitting condition of the segmentation result. Table 1 below shows IoU, voI, BDE and RI index cases for each segmentation algorithm on the BSD dataset. Note that GSSR ₁ method and GSSR _0.8 method exceeded the above-mentioned comparative method in almost all indexes.

TABLE 1 IoU, voI, BDE, RI index quantification of various methods on BSD datasets

To further evaluate the boundary-fitting ability of the segmentation algorithm, FIG. 6 (a) shows the PR curve case for each algorithm. The higher the recall and precision here, the more excellent the segmentation capability of the representative algorithm. Also, to comprehensively consider both accuracy and recall, we present in FIG. 6 (b) an overall case of F-score and AUC index to evaluate the model. It can be seen that the boundary fits of GSSR ₁ and GSSR _0.8 are very similar, but slightly worse than GSSR _0.8. Both exhibited better edge fitting ability and highest F-score and AUC values in all methods than the rest of the comparison methods.

The experimental results on the MSRC dataset are shown in table 2 below. From the data presented in the table, the model added with global seed information, whether using the L ₁ norm or the L _p (p=0.8) norm, has almost exceeded other segmentation methods on all evaluation indexes. The method provided by the invention is better in overall segmentation quality and more stable in segmentation. Similar to the BSD dataset, PR curve, F-score and AUC index are shown in FIG. 7, and it can be seen that GSSR _0.8 achieves the highest score.

TABLE 2 IoU, voI, BDE, RI quantitative analysis of the index for each method on MSRC datasets

In order to reduce index errors caused by inconsistency of seed information of manual subjective labeling. The invention adopts a sparse seed subset S ₁ marked on the MSRC data set to further evaluate the algorithm deeply and complexly. Table 3 below summarizes the index cases of the respective algorithms when the sparse seed S ₁ is used. By analysing the data in the table it can be concluded that when a small number of marked seeds are used, the algorithm using the global seed information stream is almost at the best position on all indexes, and that the indexes are significantly improved. Although GSSR ₁ is slightly different from the GSSR _0.8 algorithm, all indicators remain in the second place of all segmentation algorithms described above. Also to demonstrate the metric boundary fit, the present invention presents the PR curve and the F-score, AUC plots in FIG. 8.

TABLE 3 IoU, voI, BDE, RI index quantitative analysis of various methods on MSRC datasets using S1 seeds

Table 4 below shows another set of comparisons on the MSRC dataset employing another set of sparse seed subsets S ₂ provided by Andrade and Carrera. It can be seen from table 4 that the mean and variance of the proposed method are completely better than the above comparative method, both in the first and second place, indicating that GSSR ₁ and GSSR _0.8 are overall higher and more stable in segmentation quality. The algorithm of the invention is also located in the second and third positions of all methods in the median value, and only lags the ONE method. FIG. 9 shows details of PR curve, F-score and AUC index for each model on MSRC dataset using the S ₂ sub-set.

TABLE 4 IoU, voI, BDE, RI index quantitative analysis of various methods on MSRC datasets using S2 seeds

GSSR _p can be easily extended to a multi-classification problem, here illustrated by the L ₁ norm. For an N-class problem, the solution to the formula (19) is only needed to be carried out N-1 times like the solution to the two-class problem.

Solving the above equation can obtain the final segmentation result. The present invention demonstrates a number of multi-region segmentation results, as shown in fig. 10. Defining a set S of seed labels, the different kinds of labels being denoted asWhere k= {1,..and N }, then for the j-th solutionThe following formula is satisfied:

fig. 11 illustrates the random seed position robustness of GSSR _p, which only requires marking different objects in the image to generate different segmentation results. From the three input seeds (left, middle, right three columns) in fig. 11, multiple targets can be accurately segmented by simply seeding the seeds from GSSR _p model. In order to highlight the robustness of the algorithm in noise immunity, in fig. 12, the image segmentation results under the influence of gaussian noise are shown, and it can be seen that the algorithm can still segment the target object more accurately under the influence of gaussian noise with the mean value of 0.2 and the variance of 0.01.

Compared with the prior art, the interactive image segmentation method combining the global seeds and the sparse local linear reconstruction has the following advantages:

1. the invention provides a new interactive segmentation model, which is characterized in that a global seed information item is introduced by fully mining seed information, a global seed information stream is constructed, the connection between the seed and the pixel points outside the neighborhood is established, the propagation capability of the seed is increased, and a complete segmentation object can be obtained under the condition of less interaction of users.

2. The invention not only considers the global propagation of seed information, but also uses sparse local linear reconstruction regularization item, and better reserves weak structure information while reserving image local structure information.

3. The method adopts L _p norm constraint output gradient to obtain a sparse smooth result, is favorable for label propagation to generate a clear boundary, adopts an Alternate Direction Multiplication Method (ADMM) to perform iterative minimization calculation on an objective function when p=1, adopts an iterative re-weighting mode to accelerate matrix operation when 0< p <1, and improves calculation efficiency and verifies effectiveness through experiments.

Finally, it is noted that the above embodiments are only for illustrating the technical solution of the present invention and not for limiting the same, and although the present invention has been described in detail with reference to the preferred embodiments, it should be understood by those skilled in the art that modifications and equivalents may be made thereto without departing from the spirit and scope of the technical solution of the present invention, which is intended to be covered by the scope of the claims of the present invention.

Claims (6)

1. The interactive image segmentation method combining the global seeds and the sparse local linear reconstruction is characterized by comprising the following steps of:

s1, introducing a global seed information item, and constructing a global seed information stream so as to obtain a complete segmented object under the condition of sparse seeds, wherein the specific global seed information item is shown in the following formula:

wherein F represents a foreground, B represents a background, V represents a vertex set of the graph, x _i represents an unknown pixel, w _i* represents the weight from the unknown pixel to a foreground model or a background model, and x _* represents whether the pixel belongs to the foreground or the background;

S2, designing a sparse local linear reconstruction regular term based on the local linear reconstruction idea, adopting an L ₁ norm to realize the slicing smoothness of a segmentation result, and simultaneously combining the global seed information item in the step S1 to obtain a final objective function of L ₁ norm constraint, wherein the specific sparse local linear reconstruction regular term is shown as follows:

Wherein, Representing the degree of a pixel point i, N (i) representing a local set of neighbor pixel points, w _ij representing an edge weight, x _j being one of the N (i) pixel points;

the objective function is shown as follows:

Wherein X= (X ₁,x₂,…,x_n) represents the solution obtained by the objective function last, n is the total number of pixel points, lambda is a balance parameter used for balancing sparse local linear reconstruction regular term and global seed information term;

S3, carrying out iterative solution on the obtained objective function in an alternate direction multiplier method mode, and obtaining a more complete segmentation object and a more sparse region boundary segmentation effect;

S4, modifying the L ₁ norm into an L _p norm, wherein 0< p <1, converting the L _p norm into an L ₁ norm in an iterative re-weighting mode, converting the non-convex optimization problem into a convex optimization problem for solving, and obtaining a solution of a minimized objective function;

s5, obtaining a final segmentation result through a threshold method according to the obtained solution of the minimized objective function.

2. The interactive image segmentation method combining global seeds with sparse local linear reconstruction according to claim 1, wherein said step S1 comprises the steps of:

s11, modeling interaction information of a user by adopting a Gaussian mixture model, solving through an EM algorithm to obtain a foreground model and a background model respectively, wherein a calculation formula is shown as follows:

Wherein p _v represents the Gaussian mixture probability distribution of the background model or the foreground model, z _i represents the label of the ith observed data I _i belonging to the kth Gaussian component, v E { F, B };. Theta _v＝(v_v1,…,π_vk,θ_v1,…,θ_vk) represents the parameter set, N _vk(I_i|θ_vk)、N_vl(I_i|θ_vl) represents the Gaussian distribution determined by the parameter theta _vk、θ_vl respectively, pi _vk、π_vl represents the weights of the kth Gaussian component and the ith Gaussian component in the model v respectively, and K represents the number of the Gaussian components;

S12, calculating the probability of the picture pixel point to the foreground model and the background model, and constructing a foreground matrix and a background matrix as the distance between the unlabeled pixel point and the foreground and the background, so that the seed information can be globally transmitted, wherein the calculation formula of the distance between the unlabeled pixel point and the foreground is as follows:

The calculation formula of the distance from the unlabeled pixel point to the background is shown as follows:

Where P _F denotes the foreground model, P _B denotes the background model, k denotes the kth Gaussian component, The best model parameters representing the foreground model,The best model parameters representing the background model.

3. The interactive image segmentation method combining global seeds with sparse local linear reconstruction according to claim 2, wherein said step S2 comprises the steps of:

s21, calculating a graph weight model according to the input image:

the input image is recorded as I, a weight graph G= (V, E, W _E) is defined for constructing a sparse local linear reconstruction regular term, wherein V represents a vertex set of the graph, elements of the vertex set are pixels of the image, E is an edge set of all the eight adjacent pixels in eight neighborhoods, W _E is a weight set of the edges, a local neighbor pixel set N (I) = { j (I, j) epsilon E } represents all pixel sets in the eight neighborhoods of the current pixel I, and the edge weight is specifically defined as follows:

Wherein exp (·) represents an exponential function, σ=ma _(i,j)∈E||I_i-I_j||_∞, in order to ensure propagation stability, this weight calculation method ensures that the edge weight value is always a positive number and is symmetrical, that is, w _ij＝w_ji;I_i and I _j are both color vectors, and the pixel point intensity is measured by RGB or Lab color space, and the weight matrix model of the final graph is as follows:

S22, restraining the propagation of the local seed information by adopting an L ₁ norm, and combining the foreground matrix and the background matrix obtained in the step S1 to obtain a final objective function.

4. The interactive image segmentation method combining global seeds with sparse local linear reconstruction of claim 3, wherein said step S3 comprises the steps of:

s31, separating marked pixel points and unmarked pixel points, and reconstructing an energy function:

In order to ensure that the pixels solved by the foreground and background areas obtained by the objective function are consistent with the marked pixels, x _i＝x_B, The number of times of the x _i＝x_F,As a constraint term for the objective function, the matrix form of the objective function can be written as follows:

Wherein l=d-W, L is a laplace matrix, D is a diagonal matrix satisfying D _ii＝d_i, 1 is an all 1 vector, W is an adjacency weight matrix, D _B and D _F represent a constructed background weight matrix and a front Jing Quan weight matrix, respectively, wherein the elements satisfy I.e.

In order to minimize the objective function and avoid the memory consumption and time overhead caused by inverting the extremely large sparse matrix, the marked pixel points and the unmarked pixel points are separated, the logic structure of the L matrix can be simply and effectively not influenced by recombining the L matrix, U represents the set of unknown pixel points, S is the set of seed pixel points,N _B、N_F、N_U represents the number of background seeds, the number of foreground seeds and the number of unlabeled pixels, respectively, whereby the objective function can be decomposed into the following formula:

wherein X _U represents the set of unlabeled pixels, The dimensions of the matrices D _B and D _F at this time are N _U×N_U,L_S determined by the rows and columns of marked pixels in the L matrix, L _U by the rows and columns of unmarked pixels, and the R matrix by the seed pixel index, the unmarked pixel index determining an adjacent weight matrix of columns, so that the objective function is further developed as:

s32, solving a reconstructed objective function by adopting an alternate direction multiplier method:

To effectively solve the above equation (17), let L _SX_S-RX_U＝d₀,L_UX_U-R^TX_S＝d₁ construct an augmented Lagrangian function by introducing a Lagrangian multiplier, then the objective function is extended to the following equation:

Wherein b ₀、b₁ is an introduced Lagrangian multiplier, ρ is a Lagrangian penalty coefficient, and ρ >0, and for solving the final objective function formula (19), the objective function only contains L ₁ norm and L ₂ norm and is free of constraint, and the derivation minimization is directly carried out.

5. The interactive image segmentation method combining global seeds with sparse local linear reconstruction of claim 4, wherein step S4 comprises the steps of:

S41, restraining sparse local linear reconstruction regular terms in the reconstructed objective function by using an L _p norm, and redefining the constrained objective function as shown in the following formula:

S42, converting the L _p norm solution into the L ₁ norm problem solution by adopting an iterative re-weighting mode, and converting each L _p norm term into the L ₁ norm to carry out constraint, wherein the specific modification of the formula (26) is as follows:

Wherein N _F represents the number of the foreground seeds, Represents one element in vector L _sX_s-RX_U, alpha _i representsN _B represents the number of background seeds, ψ _i represents one element in vector-R ^TX_s+L_UX_U, and β _i represents |ψ _i|^p-1;

converted into a diagonal matrix form II diag (beta) psi ₁, the objective function corresponding to the L _p norm is converted into the following formula:

Wherein, Psi= -R ^TX_s+L_UX_U, alpha is a vector composed of alpha _i, beta is a vector composed of beta _i, so far L _p regular embedding has been converted into L ₁ regular embedding, and in order to ensure the stability of calculation, the next round of iteration weight updating mode of the designed weight item after each round of iteration is as follows:

Where k represents the current iteration round, ε is a small positive number that prevents division by zero, and the objective function solution is converted to the same form as equation (17) and is not described here.

6. The method for interactive image segmentation combining global seeds with sparse local linear reconstruction according to claim 5, wherein the step S5 of obtaining the final segmentation result by a thresholding method comprises binarizing an x vector into y _i∈{x_B,x_F, i e V, the thresholding using the following rule:

Where x _F denotes a foreground pixel value, x _B denotes a background pixel value, and x _i denotes a value obtained after minimizing the objective function as a marker pixel point.