Ellipse detection acceleration method based on generalized Pascal mapping

The present invention relates to the technical field of digital image processing, and in particular to an ellipse detection acceleration method based on generalized Pascal mapping.

As one of the most important basic tasks in the computer vision system, ellipse detection is widely used in various practical scenarios, for example, camera focusing on elliptic objects, robot manipulating cylindrical objects as well as unmanned aerial vehicle landing or medical diagnosis. When ellipse detection is used in these natural scenarios, not only the accurate detection of elliptic objects should be ensured, but also computation should be reduced as much as possible in limited computing resources to ensure the timeliness of actions.

The earliest ellipse detection method was initiated by Hough Transform (HT), which found ellipse edges by voting in the five-dimensional parameter space of an ellipse, and extended the Probability Hough Transform (PHT) and Random Hough Transform (RHT), however, they both involved a large number of voting candidates, so a lot of computing resources were consumed. Another idea is to reduce the number of candidate objects by using geometric constraints of ellipse edges, so as to achieve the purpose of acceleration. However, due to large base number and discreteness of edge points, it is often difficult to give consideration to both accuracy and efficiency without relying on a large amount of computing resources. Some arc-based ellipse detection methods try to use the geometric relationship between arcs to filter some invalid combinations so as to accelerate the fitting. However, inevitably, there is still a need to compute ellipse parameters, so the computation efficiency is not high.

In order to overcome the timeliness problem of the existing ellipse detection method in limited computing resources, the present invention provides an ellipse detection acceleration method based on generalized Pascal mapping, which can be embedded in an ellipse detection method, to select valid candidate arc combinations by an acceleration module through a small amount of computation, reducing computation of invalid ellipse fitting, and ensuring the detection accuracy.

The present invention provides an ellipse detection acceleration method based on generalized Pascal mapping, comprising the following steps:

step 100 , extracting accurate edge points from a real image by means of an edge detection method of an ellipse detection method, connecting edge points into arcs, and taking a de-noised arc set as input of an ellipse detection acceleration method; step 200 , screening out a valid candidate arc combination probably belonging to the same ellipse from the arc set input in step 100 by means of generalized Pascal mapping, including the following specific steps: step 201 , selecting two arcs or three arcs from the arc set input in step 100 ; step 202 , selecting endpoints and midpoints of the two arcs to form six points or selecting endpoints of the three arcs to form six points, and computing coordinate information of three mapping points formed by the six points through generalized Pascal mapping by using coordinate information of the six points; step 203 , fitting a line using the coordinate information of the mapping points by the least squares method, and computing the maximum collinear error of the three mapping points; if the maximum collinear error is less than the threshold, confirming that the three mapping points are collinear, and the corresponding arc combination which contains two arcs or three arcs forms a valid candidate arc combination belonging to the same ellipse; step 300 , according to the valid candidate arc combination output in step 200 , computing five parameters of a candidate ellipse: center coordinates, major axis and minor axis, angle between the major axis and the X coordinate axis; repeating step 200 to step 300 until all valid candidate arc combinations in the arc set and corresponding candidate ellipses are found; step 400 , clustering and verifying candidate ellipse sets by using the clustering and verifying method of the ellipse detection method, eliminating similar ellipses and false positive ellipses caused by errors, obtaining a final detected ellipse set.

Preferably, step 202 of selecting endpoints and midpoints of the two arcs to form six points or selecting endpoints of the three arcs to form six points, and computing coordinate information of three mapping points formed by the six points through generalized Pascal mapping by using coordinate information of the six points specifically includes:

selecting six points {Q x (y) } x=1,2,3 y=1,2 from the two arcs , or three arcs , , selected in step 201 , computing three mapping points {R x } x=1,2,3 of the six points, where:

recording (Q 2 (1) ,Q 3 (1) ) as a straight line where Q 2 (1) ,Q 3 (1) are located, recording <(Q 2 (1) ,Q 3 (1) ),(Q 1 (1) ,Q 1 (2) )> as an intersection of the straight line and a straight line (Q 1 (1) ,Q 1 (2) ); six straight lines intersecting in pairs at three points R 1 , R 2 , R 3 respectively, so R 1 , R 2 , R 3 are the coordinate information about the three mapping points.

Preferably, step 203 of fitting a line using the coordinate information of the mapping points by the least square method, and computing the maximum collinear error of the three mapping points; and if the maximum collinear error is less than the threshold, confirming that the three mapping points are collinear, and the corresponding arc combination which contains two arcs or three arcs forms a valid candidate arc combination belonging to the same ellipse specifically includes:

fitting a line of the three mapping points {R x } x=1,2,3 by means of the least squares method:

L =Least_Squares( R 1 ,R 2 ,R 3 )

computing the distances of the three points to the line by means of the formula of distance from point to line:

obtaining the maximum distance MAX d =max{d 1 , d 2 , d 3 } from the mapping points to the line; if the maximum distance MAX d is less than the threshold Th ED , confirming that the three mapping points are collinear, forming a valid candidate arc combination , or , , which contains two arcs or three arcs belonging to the same ellipse.

The present invention has the advantageous effects that the ellipse detection acceleration method based on generalized Pascal mapping proposed by the present invention can be embedded into the existing arc-based ellipse detection method. Thus, the operating time is reduced, the timeliness problem of the existing ellipse detection method in limited computing resources is solved, and the accuracy of ellipse detection is ensured. The main idea of the present invention is to select valid candidate arc combinations most possibly belonging to the same ellipse by using an acceleration module before ellipse fitting, so as to reduce fitting operations of invalid ellipses, thereby accelerating the ellipse detection method.

FIG. 1 is a workflow chart of an ellipse detection acceleration method based on generalized Pascal mapping provided by the present invention;

FIG. 2 is a schematic diagram of six points selected from an arc combination; and

FIG. 3 is a schematic diagram showing a mapping process of three mapping points on a straight line formed by six points.

To make the technical problem solved, the technical solution adopted and the technical effect achieved by the present invention more clear, the present invention will be further described below in detail in combination with the drawings and the embodiments. It should be understood that the specific embodiments described herein are only used for explaining the present invention, not used for limiting the present invention. In addition, it should be noted that for ease of description, the drawings only show some portions related to the present invention rather than all portions.

FIG. 1 is a workflow chart of an ellipse detection acceleration method based on generalized Pascal mapping provided by the present invention. As shown in FIG. 1 , the present invention provides an ellipse detection acceleration method based on generalized Pascal mapping, comprising the following steps:

Step 100 , extracting accurate edge points from a real image by means of an edge detection method of an ellipse detection method, connecting edge points into arcs, and taking a de-noised arc set as input of an ellipse detection acceleration method.

Edge detection may be conducted by means of frequently-used edge detection methods such as image graying, Canny edge detector, etc. De-noising may be conducted by means of methods such as noise arc filtering, straight arc filtering etc. As shown in FIG. 2 , the arc set is represent by S, S={ , , , , }.

Step 200 , screening out a valid candidate arc combination probably belonging to the same ellipse from the arc set input in step 100 by means of generalized Pascal mapping.

Step 201 , selecting two arcs or three arcs from the arc set input in step 100 .

In this embodiment, two arcs or three arcs are selected, or more arcs may be selected according to actual conditions; arcs may be selected in flexible ways, may be directly traversed or randomly selected from the arc set S; and may be selected in combination with the existing arc selection conditions in the existing ellipse detection method. As shown in FIG. 2 , two arcs , are directly selected, and the selected two arcs or three arcs are taken as one arc combination.

Step 202 , selecting endpoints and midpoints of the two arcs to form six points or selecting endpoints of the three arcs to form six points, and computing coordinate information of three mapping points formed by the six points through generalized Pascal mapping by using coordinate information of the six points.

Generalized Pascal mapping is usually used to describe a mapping relationship between points on a high-dimensional curve and a low-dimensional curve. For example, on a two-dimensional plane, 3n points on one n-order curve may be mapped to obtain 3(n−1) points corresponding thereto on one (n−1)-order curve. In the present invention, constraints are constructed by means of the mapping relationship between points on one n-order curve (n=2) and one n-order curve (n=1) and are applied to ellipse detection.

Specific description: FIG. 2 is a schematic diagram of six points selected from an arc combination. As shown in FIG. 2 , two arcs , are selected from the arc set S in an example diagram, and six points {Q x (y) } x=1,2,3 y=1,2 are selected from the arc combination. Q 1 (2) ,Q 2 (2) represent endpoints of arc , Q 2 (1) represents midpoint of arc ; Q 1 (1) ,Q 3 (1) represent endpoints of arc , Q 3 (2) represents midpoint of arc . P 1 P 2 represents a straight line where Q 1 (1) ,Q 1 (2) are located, P 2 P 3 represent a straight line where Q 2 (1) ,Q 2 (2) are located, and P 3 P 1 represents a straight line where Q 3 (1) ,Q 3 (2) are located. Straight lines P 1 P 2 , P 2 P 3 intersect at a point P 2 , straight lines P 2 P 3 , P 3 P 1 intersect at a point P 3 , and straight lines P 3 P 1 , P 1 P 2 intersect at a point P 1 .

Six points {Q x (y) } x=1,2,3 y=1,2 are selected from the arc combination containing two arcs , selected in step 201 . In this embodiment, endpoints and midpoints of the two arcs are respectively selected to form six points (or endpoints of three arcs are selected to form six points when containing three arcs , , ); three mapping points {R x } x=1,2,3 formed by the six points are computed, where:

(Q 2 (1) ,Q 3 (1) ) is recorded as a straight line where Q 2 (1) ,Q 3 (1) are located, <(Q 2 (1) ,Q 3 (1) ),(Q 1 (1) ,Q 1 (2) )> is recorded as an intersection of the straight line (Q 2 (1) ,Q 3 (1) ) and a straight line (Q 1 (1) ,Q 1 (2) ), and the like. FIG. 3 is a schematic diagram showing a mapping process of three mapping points on a straight line formed by six points. As shown in FIG. 3 , six points {Q x (y) } x=1,2,3 y=1,2 on the same ellipse are mapped to three points {R x } x=1,2,3 on the same straight line. The straight line Q 2 (1) ,Q 3 (1) where (Q 2 (1) ,Q 3 (1) ) are located is recorded as H 1 , the straight line Q 1 (1) ,Q 1 (2) where (Q 1 (1) ,Q 1 (2) ) are located is recorded as P 1 P 2 , and the like, where straight lines H 1 , P 1 P 2 intersect at a point R 1 ; straight lines H 2 , P 2 P 3 intersect at a point R 2 , and straight lines H 3 , P 3 P 1 intersect at a point R 3 . The three points R 1 , R 2 , R 3 obtained by the six straight lines intersecting in pairs are coordinate information about the three mapping points.

Step 203 , fitting a line using the coordinate information of the mapping points by the least squares method, and computing the maximum collinear error of the three mapping points; if the maximum collinear error is less than a threshold, confirming that the three mapping points are collinear, that is, the two arcs or three arcs belonging to the same ellipse, forming a valid candidate arc combination which contains two arcs or three arcs belonging to the same ellipse.

In this step, the valid candidate arc combination is determined mainly by judging the degree of collinearity of the three mapping points, specifically including: fitting a line of the three mapping points {R x } x=1,2,3 by means of the least squares method:

L =Least_Squares( R 1 ,R 2 ,R 3 )

computing the distances of three points to the line by means of the formula of distance from point to line:

obtaining the maximum distance MAX d =max{d 1 , d 2 , d 3 } from the mapping points to the line, the maximum distance being the maximum collinear error. if the maximum distance, i.e. the maximum collinear error MAX d is less than the certain threshold Th ED , confirming that the three mapping points are collinear, that is, the two arcs or three arcs belong to the same ellipse, forming a valid candidate arc combination which contains two arcs or three arcs belonging to the same ellipse, that is, the arc combination , (or , , ) is a valid candidate arc combination probably belonging to the same ellipse.

Step 300 , according to the valid candidate arc combination output in step 200 , computing five parameters of a candidate ellipse: center coordinates (x, y), major axis and minor axis a, b, angle ϕ between the major axis and the X coordinate axis, repeating step 200 to step 300 until all valid candidate arc combinations in the arc set S and corresponding candidate ellipses are found.

In this step, a valid candidate arc combination is selected from the arc set by means of generalized Pascal mapping. Five parameters of a candidate ellipse are computed by means of frequently-used parameter computation methods such as parallel chord method, etc. A set of five parameters of an ellipse can uniquely represent one ellipse. According to the computed five parameters of the ellipse, all valid candidate arc combinations in the arc set S and corresponding candidate ellipses are determined.

Step 400 , clustering and verifying candidate ellipse sets by means of the clustering and verifying method of the ellipse detection method, eliminating similar ellipses and false positive ellipses caused by errors, obtaining a final detected ellipse set.

In this step, candidate ellipse sets are clustered and verified by means of frequently-used methods such as parameter clustering, center point verification, etc.

This embodiment is illustrated in the form of examples as follows:

1. Extracting accurate edge points from a real image by means of a Canny edge detector of an ellipse detection method, connecting edge points into arcs, and taking a de-noised arc set S (as shown in FIG. 2 , S={ , , , , }) as input of an ellipse detection acceleration method. 2. Screening out a valid candidate arc combination probably belonging to the same ellipse from the arc set input in step 1. 2-1. Selecting two arcs , from the arc set. 2-2. Selecting endpoints and midpoints of the two arcs to form six points, and computing coordinate information of three mapping points formed by the six points through generalized Pascal mapping.

As shown in FIG. 2 , six points {Q x (y) } x=1,2,3 y=1,2 are selected from the arc combination containing two arcs , selected in step 2-1. In this patent, endpoints and midpoints of two arcs are respectively selected to form six points. As shown in FIG. 3 , three mapping points {R x } x=1,2,3 formed by the six points are computed, where:

(Q 2 (1) ,Q 3 (1) ) is recorded as a straight line where Q 2 (1) ,Q 3 (1) are located <(Q 2 (1) ,Q 3 (1) ),(Q 1 (1) ,Q 1 (2) )> is recorded as an intersection of the straight line (Q 2 (1) ,Q 3 (1) ) and a straight line (Q 1 (1) ,Q 1 (2) ), and the like. The specific computation process of generalized Pascal mapping is as follows:

The coordinates of the six points are expressed as:

where L Q 2 (1) Q 3 (1) is an equation of the straight line H 1 , L Q 1 (1) Q 1 (2) is an equation of the straight line P 1 P 2 , the two straight lines intersect at a point R 1 , and the like. The three points R 1 , R 2 , R 3 obtained by the six straight lines intersecting in pairs are coordinate information about the three mapping points.

2-3. Judging the degree of collinearity of the three mapping points, screening out a valid candidate arc combination belonging to the same ellipse.

On the basis of step 2-2, a line of the three mapping points {R x } x=1,2,3 is fitted by means of the least squares method:

{ L = Least_Squares ⁢ ( R 1 , R 2 , R 3 ) L : y = - 4.5152 ⁢ x - 3.7565

the distances of the three points to the line are computed by means of the formula of distance from point to line:

{ d 1 = Distance_formula ⁢ ( R 1 , L ) = 0.2225 * 10 - 4 d 2 = Distance_formula ⁢ ( R 2 , L ) = 0.456 * 10 - 4 d 3 = Distance_formula ⁢ ( R 3 , L ) = 0.0259 * 10 - 4

the maximum distance MAX d =max{d 1 , d 2 , d 3 }=0.4560*10 −4 is obtained; if the maximum distance, i.e. the maximum collinear error MAX d is less than a certain threshold Th ED (in this embodiment, the threshold is selected to be Th ED ≤2.97), the slightly large threshold is to set aside a tolerable error range for the noise which possibly exists at image edge points; in this embodiment, the maximum collinear error is relatively small because points are selected accurately and basically fall on the detection ellipse, while most of the points cannot be accurately selected during detection), it is confirmed that the three mapping points are collinear, that is, the arc combination , is a valid candidate arc combination most possibly belonging to the same ellipse.

3. According to the valid candidate arc combination output in step 2, computing five parameters of a candidate ellipse by means of frequently-used parameter computation methods such as parallel chord method, etc.: center coordinates (0,0), major axis and minor axis 10 , 4√{square root over (5)} angle 0° between the major axis and the X coordinate axis (the standard equation thereof is as follows:

x 2 25 + y 2 20 = 1 ) ;

repeating step 200 to step 300 until all valid candidate arc combinations in the arc set S and corresponding candidate ellipses are found.

4. Clustering and verifying candidate ellipse sets by means of frequently-used methods such as parameter clustering, center point verification, etc., eliminating similar ellipses and false positive ellipses caused by errors, obtaining a final detected ellipse set.

Finally, it should be noted that the above embodiments are only used for describing the technical solution of the present invention rather than limiting the present invention. Although the present invention is described in detail by referring to the above embodiments, those ordinary skilled in the art should understand that: the amendments to the technical solution recorded in each of the above embodiments or the equivalent replacements for part of or all the technical features therein do not enable the essence of the corresponding technical solution to depart from the scope of the technical solution of various embodiments of the present invention.