Background technology
In many application of object identification, all be the image and the model bank recognition object of coupling object.If profile comprises enough information, Shi Bie problem just is converted into the matching problem of plane curve so.Traditional recognition methods mostly is the key feature point that extracts target to be identified and model curve, and the coupling by unique point reaches identification of targets.But in actual conditions, the impossible entirely accurate of the extraction of unique point, noise exists inevitably with blocking also, therefore adopts the corresponding matching algorithm of traditional some point not prove effective.Being mainly used in the Hausdorff distance (being called for short HD) of measuring matching degree between two point sets does not need to set up the corresponding of point and point between two point sets, can produce effect preferably when template is mated with the target image that is blocked yet.In common Hausdorff distance calculation, owing to be that the object edge picture element is calculated one by one, when the similarity degree of 2 large sized object edge images of direct comparison, its calculated amount is very big.Replace marginal point to calculate the Hausdorff distance with key feature point (angle point, point of contact, flex point), greatly reduce the computation complexity of Hausdorff distance.Nirwan etc. and N.Ayache etc. directly mate with the key feature point, think Feature Points Matching, and these two curves are coupling mutually just.In fact contour curve represents not have uniqueness with unique point, can be linked to be smooth arbitrary curve between two unique points.In robot assembly line, because a plurality of object is piled up or overlaped, the image of object produces and blocks mutually; Aspect remote sensing images identification, object may be blocked by the shadow of tree, house and vehicle, therefore the Study of recognition that is necessary to carry out the partial occlusion object.At present, the identification scholars for the partial occlusion object have carried out some researchs.Krolupper proposes to force the into border of object with circular arc, is the partial descriptions to object, and is robust to blocking.But the border of this method hypothesis object is a closed curve, and object only changes through translation, rotation and ratio.Shan has proposed the model object is expressed as histogrammic set, and histogram and the model histogram with object to be identified mates then.Can solve the coupling of partial occlusion object.Park proposes to describe object with the two-value vector relations between feature, and the mark of object only is subjected to the influence of the two-value relation value between feature, and this method is based on the describing method of local feature.Cho has symmetric characteristics according to a lot of objects, at first recover the be blocked shape of part of object according to symmetry, then mate again, this method can be discerned the three-dimensional body under the rigid body translation, but this method only is suitable for discerning symmetrical structure and the cross section is the partial occlusion object of ellipse or approximate circle.Dinesh has proposed the object that blocks based on perfect Hash method (perfect hash) identification division.Gorman is covered shape with dynamic programming identification, they have at first proposed to describe based on Fourier the line segment method for expressing of son, each shape is divided into several line segments, each line segment is that 2 Fourier describes subrepresentation by a length, Dynamic matching table between computation model and the target to be identified judges whether coupling according to the line segment number that mates at last then.Schwartz directly mates two curves, and two curves are carried out equally spaced cutting apart, and has produced the point set of two curves thus, then with the distance between two curve point sets of least square method calculating.The distance that calculates thinks then that less than given threshold value these two curves mate.This method only is suitable for model curve and has comprised scene curve fully, and the method for this direct coupling lost efficacy under the conversion of complexity.Rajpal has proposed to solve the coverage problem with neural network, and the shape of having used the method for Multilayer Perception net and index to come compatible portion to block has solved to a certain extent and partly covered problem.Above-mentioned other method all only is applicable to rigid body or similarity transformation, can lose efficacy under affined transformation or perspective transform.Open grade and proposed the recognition methods that the existence of plane polygon shape target is blocked, and can be suitable for affined transformation.But on engineering, some object differs approximate with plane polygon surely.Orrite proposes to describe with two point of contacts the local boundary of object, and with Hausdorff distance (the being called for short PHD) measurement model optimized and the matching degree of target, but the property distinguished of this tolerance is little, can cause erroneous judgement, and under the situation that has big geometric transformation, the one-to-one relationship of model and image can not obtain.
Above-mentioned most method all only is suitable for simple rigid body translation and similarity transformation, and the video camera imaging model is not simple rigid body and similarity transformation.Though the recognition methods of Orrite is suitable for perspective transform, but its method Hausdorff distance (the being called for short PHD) measurement model of optimization and the matching degree of target, the property distinguished of this tolerance is little, can cause erroneous judgement, and under the situation that has big geometric transformation, the one-to-one relationship of model and image can not obtain.
Summary of the invention
The present invention is directed to the defective and the deficiency that exist in the prior art, the method that provides a kind of identification division to block curved face object is based on the method for improved Hausdorff distance with the curved face object of the sub-Curves Recognition partial occlusion of coupling.The present invention proposes the key feature point on the contour curve of at first extraction model and target to be identified, based on the contour curve segmentation of naming a person for a particular job of these key features, realizes identification to the whole piece curve by the identification to every cross-talk curve; Propose a kind of new and stable Hausdorff distance (being called for short RHD),, estimate best affine or perspective transformation matrix based on the matching degree of RHD measurement target and aspect of model point set; Matching sections affine based on the best or perspective transformation matrix searching target and all sub-curves of model are right, calculate matching rate, mate curve affine or that block the perspective transform lower part.Every cross-talk curve on this algorithmic match target and the model silhouette curve has solved the not uniqueness problem of representing curve with unique point; New RHD has taken all factors into consideration and the lattice point and the influence of blocking, and can be competent at has the coupling of blocking with the curve of noise.Theoretical analysis and sample result show that the method that this invention proposes is suitable for affined transformation or perspective transform, and noise resisting ability is strong, and be still effective when bigger blocking arranged.
The present invention is achieved like this, and it is characterized in that recognition methods is:
(1) key feature of extraction model profile and objective contour to be identified point at first, with the preliminary contour curve of describing of key feature point, name a person for a particular job objective contour and model silhouette curve of these key features is divided into many sub-curves;
(2) propose a kind of stable Hausdorff distance,, and determine best affine or perspective transformation matrix based on the matching degree of crucial feature point set on stable Hausdorff range observation model and the objective contour curve to be identified;
(3) under the prerequisite of key feature point coupling, mate the every cross-talk curve on target and the model silhouette curve again, designed a kind of new algorithmic match target and the every cross-talk curve on the model silhouette curve;
(4) last right based on the matching section of the best affined transformation battle array searching target that obtains and all sub-curves of model, calculate matching rate, discern curved face object affine or that block the perspective transform lower part.
Key feature of the present invention is put preferred angle point, point of contact and flex point.
Advantage of the present invention is: 1, the video camera imaging model is not simple rigid body and similarity transformation, and the present invention expands to affined transformation or perspective transform with the identification of partial occlusion curved face object; 2, can be competent at the identification of blocking with the curved face object of noise is arranged; 3, replace edge pixel point to calculate the Hausdorff distance with key feature point, can reduce the computation complexity of Hausdorff distance greatly; When estimating affined transformation or perspective transformation matrix, taked the principle of similar some coupling, significantly reduced the search volume, improved the efficient of estimating affined transformation or perspective transformation matrix; 4, set up one-to-one relationship between model and target signature to be identified, solved common matching process based on the Hausdorff distance can not processing feature between the problem of corresponding relation; 5, solved low accuracy problem with polygon or conic section curve of approximation.
Embodiment
1, improved Hausdorff distance
At first, the present invention takes all factors into consideration factor such as lattice point, block, construct a kind of stable Hausdorff distance (being called for short RHD) tolerance key feature point set A and the similarity between the B, wherein point set A is the set of model silhouette through the key feature point after the projective transformation, point set B is the set of objective contour key feature point, considers the influence of blocking and going out lattice point in this metric function simultaneously.
RHD is defined as follows:
The number of unique point among num (A) the representation feature point set A wherein, point set A ' is the set of satisfied { min ‖ a-b ‖<δ }, and δ is the threshold value that is used for eliminating out lattice point, and M is a constant with very big value.When set A ' in element number when being not more than 3, h
RHDBe changed to M; Otherwise h
RHDValue by two decisions, last the main factor of blocking considered, a back influence of mainly considering lattice point, its value is got set A ' middle d
BThe maximal value of (a ').(1) to get 3 be because use three pairs of corresponding point when calculating affine transformation matrix in hypothesis at least to the threshold value in the formula, so no matter whether model and target have corresponding relation, at least all has three pairs of points can satisfy the condition of { min ‖ a-b ‖<δ }.
H
RHD(A B) tries to achieve by following formula
H
RHD(A,B)=max(h
RHD(A,B),h
RHD(B,A)) (2)
By choosing parameter δ rightly, going out lattice point can be overcome well.Similarly, by choosing parameter ρ rightly, occlusion issue can be well solved. so H
RHD(A B) blocks all insensitive to going out lattice point and object.
Method that this paper proposes and Orrite (Carlos Orrite and J.Elias Herrro.Shape matchingof partially occluded curves invariant under projective transformation[J] .ComputerVision and Image Understanding, 2004,93 (2): pp34-64) key distinction of method has following 3 points: 1, the Hausdorff distance of Orrit is that the object edge picture element is calculated one by one, when the similarity of two large sized object edge images of direct comparison, its calculated amount is very big, this paper is with key feature point (angle point, the point of contact, flex point) replaces edge pixel point to calculate the Hausdorff distance, can reduce the computation complexity of Hausdorff distance greatly; 2, Orrite has only considered the influence of lattice point, and in the images match that error image and existence are blocked more greatly, the value of PHD is still bigger, the property distinguished of this tolerance is little, can cause erroneous judgement, this paper has taken all factors into consideration the influence that lattice point and block, and can be competent at has the Curve Matching of blocking with noise; 3, Orrite thinks that it promptly is model with object matching that PHD obtains the pairing model of global minimum, in fact because object blocks the existence with picture noise, making PHD obtain the pairing model of global minimum might not be model with object matching, this paper is in the candidate's model that satisfies RHD<p (p is given threshold value), by sub-curve of further coupling and calculating matching rate, determine model with object matching.2, the key feature point on Matching Model and the contour curve to be identified
The RHD that the present invention proposes is as the key feature point of estimating on Matching Model curve and the curve to be identified, and the coupling that will put is limited on the same type and carries out, and promptly angle point, point of contact, flex point respectively can only be corresponding with angle point, point of contact, flex point.Can significantly reduce the search volume like this, improve matching efficiency.
Replace picture element to calculate RHD with key feature point, and follow similar some matching principle, but it is multiple that the matching scheme of key feature point still has, the present invention estimates the posture changing battle array by the minimum value of asking for RHD, the minimum RHD that tries to achieve is a local minimum, when being a certain curve in the model and objective contour coupling, in the various matching schemes of unique point, RHD gets minimum value.For every in model bank curve all corresponding a local minimum RHD.Satisfy the affine transformation matrix of RHD<p (p is given threshold value) and all think possible best affine or perspective transformation matrix.Because object blocks the existence with picture noise, make the model that the model of the global minimum correspondence in these local minimums is not necessarily asked, so need further verify with matching rate.
The method of coupling key feature point is as follows:
Step1: extract the key feature point on the objective contour to be identified;
Step2: according to the principle of similar some coupling, with model silhouette M
iSimilar point on (n, n are the number of model in the model bank for i=1,2...) mates;
Step3: the affine or perspective transformation matrix T of estimation model curve and curve to be identified, computation model curve after through above-mentioned affine or perspective transform curve and the RHD between curve key feature point to be identified;
Step4: compare with the RHD that calculates with other matching scheme, obtain the local minimum of RHD;
Step5: every curve in target and the model bank mates, and can obtain a local minimum RHD, and the affine transformation matrix that satisfies RHD<p (p is given threshold value) all is possible best affine or perspective transformation matrix (if having m);
Step6: when affine or perspective transformation matrix was obtained, the corresponding relation of the key feature point of model and curve to be identified had also promptly been determined.
3, the sub-curve of Matching Model and objective contour curve to be identified
Article two, the key feature point of curve coupling is not necessarily represented this two Curve Matching.Because between two invariant points, the shape of curve is not unique, promptly represents that with the key feature point curve does not have uniqueness.In order to address this problem, we segment the every cross-talk curve between two key feature points on the curve according to accuracy requirement
[10]Judge whether segmentation point corresponding on two curves satisfies same affine corresponding relation.
As shown in Figure 1 and Figure 2, with arc 12 segmentations, the segmentation point is a according to accuracy requirement, b ... i, cross these segmentation points and make to decide (with the straight line parallel that is connected two unique points) sweep trace of direction respectively.
The algorithm that mates sub-curve is as follows:
(1) segments sub-curve between adjacent two unique points according to accuracy requirement, as 12 among Fig. 1;
(2) these segmentation points of crossing on the model curve are made a series of sweep traces of decide direction, and the line of certain two unique point of mistake is parallel on these sweep traces and the model silhouette curve;
(3) these sweep traces are mapped on the objective plane the corresponding segment of curve 1 ' 2 on the sweep trace after the mapping and the objective contour curve ' a series of intersection point is arranged, as shown in Figure 2 according to affine transformation matrix T;
(4) whether the segmentation point on the corresponding sub-curve with curve to be identified of verification model is corresponding, and whether the relation between the corresponding segmentation point satisfies the affine transformation relationship T that previous calculations goes out;
(5) satisfy as if condition in (4), then this cross-talk Curve Matching of model and curve to be identified.
4, the recognizer of partial occlusion curved face object
The model that satisfies RHD<p in the hypothesized model storehouse has m, its profile M
iExpression, i=1,2..., m, the profile of target to be identified is represented with I.
Concrete recognizer is as follows:
Step1: extract the key feature point on the objective contour curve, according to the name a person for a particular job contour curve segmentation of object to be identified of key feature;
Step2: tentatively mate key feature point on target and the model curve according to similar some matching principle, determine the corresponding relation of key feature point again according to the method for the 2nd joint;
Step3: every cross-talk curve of Matching Model profile and objective contour to be identified, record is the hop count k of coupling mutually
i, if the segment of curve number that the profile of objective contour and i model mates mutually is maximum, i.e. k
iMaximum then is classified as target among the model i, and identification finishes.
Supposing has k since j unique point continuous (if discontinuous, displacement capable of circulation makes it to become continuous)
jSegment model curve and curve to be identified mate mutually, and then matching rate is defined as: f=k
j/ K
i, certain model is relatively promptly got total hop count K of this model in objective contour to be identified and the storehouse
iBe denominator.0<f<1, f approaches 1 more, illustrates that these two curves are similar more.The matching rate that following formula determined is not only The classification basis, but also has reflected the integrated degree of figure.
With instrument and the machine parts of identification on the worktable is purpose, video camera above worktable, video camera to the ratio of the distance of worktable and the maximum height of instrument or machine parts greater than 10.Instrument on the worktable or machine parts can be similar to and be reduced to two-dimentional curved face object.Many group experimental results show that all the method that the present invention proposes is practicable, and effect is better.
In order to verify the stability of the recognition methods that the present invention proposes, the end points coordinate by key feature point that composograph and true picture are extracted increases Gaussian noise, the relation of checking discrimination and noise.
End points to the key feature point that extracts in the image adds σ respectively
2Be 0.5,1,1.5,2.5,3 Gaussian noise repeats experiment, obtains the graph of a relation of discrimination and noise, as shown in Figure 3, Figure 4.The curve that has " o " sign among the figure is document Carlos Orrite and J.Elias Herrro.Shape matching ofpartially occluded curves invariant under projective transformation[J] .ComputerVision and Image Understanding, 2004,93 (2): the discrimination that the discrimination that obtains based on the method for PHD among the pp34-64 and the graph of a relation of noise, the curve that has " * " sign obtain for the method that proposes RHD based on this paper and the graph of a relation of noise.Experimental result shows that the method based on RHD that this paper proposes has better robustness.
In order to verify discrimination and the relation of blocking rate, the ratio of the part that is blocked of input picture slowly increases.Figure in the experiment is blocked 10%, 20%, 30% respectively, and 40%, 50%, 60% repeats experiment, obtains discrimination and the graph of a relation that blocks rate (σ wherein
2=0.5), as shown in Figure 5.The curve that has '+' sign and ' * ' sign among the figure is the rate of blocking of Fig. 5 and the graph of a relation of discrimination, these two curves are very approaching, illustrated that the algorithm that identification division that this paper proposes blocks object has the ability of blocking of handling preferably, as long as contour of object curve to be identified has 40% to survive, the algorithm of this paper just can identify object.