A kind of improved graph theory dividing method based on super-pixelTechnical field
The invention belongs to image Segmentation Technology neighborhoods, are related to a kind of graph theory dividing method based on super-pixel.
Background technique
GrabCut method is to be handled on the basis of pixel in structure figures, there are apparent splitting speed is slow,The disadvantage of complex scene segmentation effect difference.Compact super-pixel block is obtained by carrying out super-pixel segmentation to image, these are surpassedBlock of pixels constitutes graph model as node, and this method can greatly reduce the quantity of node, reduce the complexity of figure, improvesThe segmentation efficiency of GrabCut.
Super-pixel method can extract middle layer characteristics of image, and this algorithm, which is extracted, perceives significant region in image,Usually as the pre-treatment step of partitioning algorithm, it can be used to replace the pixel grid of rigid structure.Picture is replaced using super-pixelElement is operated, and can accelerate the existing GrabCut algorithm based on pixel grid, or even improve the effect for improving some segmentationsFruit.
Super-pixel method is broadly divided into two classes: the method based on graph theory and the method based on gradient decline.Super-pixel isReferring to has this special adjacent irregular block of pixels for having certain visual meaningaaa being similarly constructed such as similar grain, color, its benefitWith the pixel between pixel, all pixels are grouped, are then substituted with a small amount of block of pixels and super-pixel a large amount ofPixel express the feature of picture, largely reduce the complexity of image procossing, so partitioning algorithm would generally be used asPre-treatment step.
Existing technological deficiency are as follows: the complexity height and segmentation low efficiency of image procossing.
Summary of the invention
Complexity in order to overcome the shortcomings of the image procossing of existing graph theory dividing method is high, segmentation low efficiency, the present inventionIn order to reduce the complexity of image procossing, the speed of service is improved, segmentation efficiency is improved, is provided a kind of improved based on super-pixelGraph theory dividing method.
The technical solution adopted by the present invention to solve the technical problems is:
A kind of improved graph theory dividing method based on super-pixel, includes the following steps:
1) simple linear iteraction cluster (SLIC) is chosen in super-pixel pretreatment, and the process of template matching passes through in original imageSleiding form real-time perfoming matches i.e. on input picture；
2) enhancement is handled
Processing, amalgamation result are merged to the fragmentary region being previously mentioned in step 1)；Create a label table, member in tableElement is -1, moves towards (from left to right, sequence from top to bottom) for discontinuous super-pixel, undersized super-pixel according to " Z " typeIt is reassigned to neighbouring super-pixel, traversed pixel distributes to corresponding label, until all the points traversal finishes；
3) model training and figure building
Cutting object topography is chosen, the distribution of foreground and background is calculated using corresponding local message
4) segmentation result is obtained
Graph model is established according to conventional images, the solution of energy-minimum is carried out using max-flow/minimal cut algorithm, is obtainedFinal image segmentation result, process are as follows:
4.1) figure building is first carried out, using the above-mentioned local message that acquires come structure figures, the central point of super-pixel block has oneselfSpatial position value, calculate the distance between super-pixel block and super-pixel block by xy coordinate, calculation formula is as follows.
Wherein, (x1,y1) and (x2,y2) be respectively any two super-pixel block centre coordinate.(x1,y1).With (x2,y2)It is the centre coordinate of any two super-pixel block respectively.
Then the assignment of n-links is carried out whereby, and in addition to this assignment of t-links is still counted using data distributionIt calculates；
4.2) minimum value of energy function is solved using max-flow/minimal cut；The target circle expression of acquisition just realizesThe tracking of target.
Further, in the step 1), it is assumed that a total of N number of pixel of picture, pre-segmentation are K super-pixel, are matchedJourney is as follows:
1.1) cluster centre is initialized, the size of super-pixel is N/K, then the distance of neighboring seeds point is approximately
1.2) seed point is reselected in the n*n neighborhood of existing seed point；
1.3) to be that each pixel distributes class label in the neighborhood around each seed point；
1.4) distance metric calculates:
Wherein, dc represents color distance, and ds represents space length, and Ns is maximum space distance in class, is defined as, is suitable forEach cluster；Maximum color distance Nc was both different and different with picture, also different and different with cluster, so taking a fixationConstant m is replaced, and value range [Isosorbide-5-Nitrae 0] generally takes 10, final distance metric is as follows:
Since each pixel can be searched by multiple seed points, so each pixel can have one and surrounding kindThe distance of son point, is minimized cluster centre of the corresponding seed point as the pixel；
1.5) the step of repeating (1.2)~(1.4) is less than some minimum until error convergence, i.e. error amount, and pole has canEnergy central point remains unchanged；There is a large amount of scrappy super-pixel block in figure at this time, causes intermediate super-pixel block not compact enough.
Technical concept of the invention are as follows: the reason of selecting using the super-pixel method of SLIC in conjunction with GrabCut is:GrabCut method is handled on the basis of pixel in structure figures, if block of pixels seems rambling, meetingSo that the pixel of pixel adjoining increases, so that differing too big between block of pixels and block of pixels.And use SLIC methodMeeting is so that gap is little between block of pixels, and more easily determines adjacent pixels, while in addition this method is without increasing shape aboutBeam, so that method realization is relatively simple.
This method proposes that method is improved aiming at the problem that complexity height and segmentation low efficiency of GrabCut image procossing.It is firstFirst super-pixel pretreatment, then enhancement processing, then choose and retain the local message of cutting object, then can by xy coordinateThe assignment of n-links is carried out to calculate the distance between super-pixel block and super-pixel block.It is asked using max-flow/minimal cut tEnergy function minimum value is obtained to obtain segmentation result.
Beneficial effects of the present invention are mainly manifested in: 1, the number for carrying out the node in super-pixel treated image is obviousIt reduces, lowers the complexity of figure；2, GrabCut image segmentation algorithm efficiency is improved.
Detailed description of the invention
Fig. 1 is the flow chart of the improved graph theory dividing method based on super-pixel.
Fig. 2 is the detailed process of the segmentation application of natural image and the schematic diagram of operation, wherein (a) is extracted superBlock of pixels, (b) is amalgamation result, (c) carries out model training for selected section cutting object, (d) is to carry out figure structure after trainingIt builds, i.e. n-links, (e) is the profile diagram of image segmentation result, (f) be the binary map of image segmentation result.
Specific embodiment
The invention will be further described below in conjunction with the accompanying drawings.
Referring to Figures 1 and 2, a kind of improved graph theory dividing method based on super-pixel, includes the following steps:
1) super-pixel pre-processes: choosing simple linear iteraction cluster (SLIC)
The process of template matching by original image, that is, input picture sleiding form real-time perfoming match, it is assumed that picture is totalN number of pixel is shared, pre-segmentation is K super-pixel, and process is as follows:
1.1) cluster centre is initialized, the size of super-pixel is N/K, then the distance of neighboring seeds point is approximately
1.2) seed point is reselected in the n*n neighborhood of existing seed point；
1.3) to be that each pixel distributes class label in the neighborhood around each seed point；
1.4) distance metric calculates:
Wherein, dc represents color distance, and ds represents space length, and Ns is maximum space distance in class, is defined as, is suitable forEach cluster；Maximum color distance Nc was both different and different with picture, also different and different with cluster, so taking a fixationConstant m (value range [Isosorbide-5-Nitrae 0] generally takes and 10) replaces, and final distance metric is as follows:
Since each pixel can be searched by multiple seed points, so each pixel can have one and surrounding kindThe distance of son point, is minimized cluster centre of the corresponding seed point as the pixel；
1.5) repeat (1.2)~(1.4) the step of until error convergence (error amount be less than some minimum, it is most likely thatCentral point remains unchanged)；Shown in extracted super-pixel block such as Fig. 2 (a), there is a large amount of scrappy super-pixel in figure at this timeBlock causes intermediate super-pixel block not compact enough；
2) enhancement is handled
Processing is merged to the fragmentary region being previously mentioned in step 1).A label table is created, table interior element is -1,Discontinuous super-pixel, undersized super-pixel are reassigned to according to " Z " type trend (from left to right, sequence from top to bottom)Neighbouring super-pixel, traversed pixel distribute to corresponding label, until all the points traversal finishes.Amalgamation result is such asShown in Fig. 2 (b), super-pixel pre-processed results at this time are compact, belong to ideal segmentation result；
3) model training and figure building
Selected section cutting object carries out model training and carries out figure building, n-links after training as shown in Fig. 2 (c)As shown in Fig. 2 (d)；
4) segmentation result is obtained
Graph model is established according to conventional images, the solution of energy-minimum is carried out using max-flow/minimal cut algorithm, is obtainedShown in final image segmentation result such as Fig. 2 (e) (f), wherein Fig. 2 (e) is the profile diagram of image segmentation result, and 2 (f) be imageThe binary map of segmentation result, process are as follows:
4.1) figure building is first carried out, using the above-mentioned local message that acquires come structure figures.The central point of super-pixel block has oneselfSpatial position value, the distance between super-pixel block and super-pixel block, the following institute of calculation formula can be calculated by xy coordinateShow:
Wherein, (x1,y1) and (x2,y2) be respectively any two super-pixel block centre coordinate.(x1,y1) and (x2,y2) pointIt is not the centre coordinate of any two super-pixel block.
Then the assignment of n-links is carried out whereby, and in addition to this assignment of t-links is still counted using data distributionIt calculates；
4.2) minimum value of energy function is solved using max-flow/minimal cut；The target circle expression of acquisition just realizesThe tracking of target.