JP2006065452A - Image data processing method and device by n-dimensional hough transformation - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a technology for extracting dots belonging to a specific shape from the set of dots in an n-dimensional space, and for grasping the existence of the specific shape existing in the n-dimensional space. <P>SOLUTION: Arbitrary three dots are selected from edge dots on image data. When the equation of a graphic to be extracted is y=ax<SP>2</SP>+bx+c, a simultaneous equation is prepared by using the arbitrary three dots, and the equation is solved, and intersections, that is, parameters (a), b and c in a parameter space in Hough transformation are calculated. In the same way, the intersections are calculated from the other arbitrary three dots. A region where the intersection group concentrates is calculated by a voting method or the like. The parameters obtained as mentioned above are substituted in the original equation y=ax<SP>2</SP>+bx+c so that a curve being the variety of the edge dots on the image data can be calculated. <P>COPYRIGHT: (C)2006,JPO&NCIPI

Description

  The present invention relates to a technique for extracting points belonging to a specific shape from a set of points in an n-dimensional space and grasping the existence of the specific shape existing in the n-dimensional space.

A straight line is detected from a point group of a grayscale image obtained from a camera by an image processing technique (see, for example, Patent Document 1). In this case, a point on the xy orthogonal coordinate system is projected to the θ-ρ parameter coordinate system (x cos θ + y sin θ = ρ) by the Hough transform to be converted into a curve. Here, when a plurality of points on a straight line existing on the xy coordinate system are drawn as a plurality of curves in the θ-ρ parameter coordinate system, the plurality of curves intersect at a certain point. By substituting θo and ρo at the intersection P (θo, ρo) into the conversion formula x cosθ + y sinθ = ρ, the parameters a and b of the straight line (y = ax + b) in the xy orthogonal coordinate system are determined.
Japanese Patent No. 2646363

This Hough transform has been established as one of the important methods of image analysis / recognition as a stable straight line detection method from an image including noise.
The principle of the Hough transform will be described below.
The straight line y = a · x + b (a1) where the figure to be extracted from the image is now expressed as a parameter by the inclination a and the intercept b
Express with
The straight line passing through the point (xi, yi) in the image is yi = a · xi + b (a2)
It is expressed. Equation (2) is considered as an equation relating to a and b, and the locus is drawn in the ab space (FIG. 4 (a)).

The same mapping for each feature point in the image (edge point), when the point of intersection many locus (called peak or integrated point) and _{(a 0, b 0),} (a 0, b 0 ) A straight line defined by y = a ₀ · x + b ₀ (a3)
Is present in the image, and among the feature points, the group belonging to this straight line is located almost in the vicinity of this straight line.
In order to obtain the accumulation point, first, an array representing the parameter space (a, b) is prepared, and the value of the element is incremented by 1 each time the trajectory passes through the element of the array. After drawing all the trajectories, the element having the maximum value is searched for as an accumulation point.

The above is the principle of line extraction by Hough transform.
However, the expression (a1) requires an infinitely large array representing the parameter space of (a, b), which is not practical.
ρ = x cos θ + ysin θ (0 ≦ θ <π) (a4)
An expression method using the perpendicular angle θ and the signed distance ρ from the origin has been proposed.
As shown in FIG. 4B, when the ρ−θ expression is used, the parameter space is finite (θ is in the range of 0 ≦ θ <π, and ρ is also finite because the image range is finite), and the locus is sine. It becomes a curve. For this reason, the ρ-θ representation is usually used. However, when the ab expression is used, the locus becomes a straight line, and there is an advantage that the feature extraction in the parameter space and the analysis thereof (for example, the extraction of the straight line group) are facilitated.
The general properties, characteristics, and problems of the Hough transform using the ρ-θ representation as a straight line method are summarized as follows.

<Properties>
1. All straight lines passing through the point (x, y) on the image are mapped to one Hough curve on the parameter space.
2. One point on the parameter space corresponds to one straight line in the image.
3. Hough curves corresponding to arbitrary n points on the same straight line intersect only once in the parameter space.
4). A group of straight lines parallel to each other is mapped onto a straight line perpendicular to the θ axis in the parameter space.
5. A tangent group of circles centered on the origin is mapped on a straight line perpendicular to the ρ axis in the parameter space.

<Features>
1. A straight line can be detected stably without being affected by false feature points due to noise in the image.
2. Even if the line is discontinuous due to concealment or incomplete image processing, it can be detected.
3. Since mapping can be executed independently for each point in the image, speeding up by parallel processing is possible.
4). Multiple straight lines can be detected simultaneously.

<Problem>
1. A large memory is required to represent the parameter space.
2. The criteria for determining the sampling interval (resolution) when digitizing the parameter space is not clear.
3. Since one Hough curve is drawn for each point in the image, the calculation amount increases.
4). The criterion (threshold value) for selecting the locus accumulation point is not very clear.

Combinatorial Hough Transform (Combinatorial Hough Transform: hereinafter referred to as “CHT”) has been proposed as a new method improved from this standard Hough transform. In the standard Hough transform, the voting unit is an edge point, and the voting locus is a sine curve. In contrast, CHT only requires one point. That is, the parameter of the straight line passing through the two edge points (x ₁ , y ₁ ) and (x ₂ , y ₂ ) is calculated from the equation (a4) as follows: ρ ₀ = x ₁ · cos θ ₀ + y ₁ · sin θ ₀ (a5)
θ ₀ = tan ⁻¹ {− (x ₂ −x ₁ ) / (y ₂ −y ₁ )} (a6)
Is determined. Therefore, the voting method is changed such that the voting operation is performed for each pair of edge points, and the voting value 1 is added only to the cell corresponding to each parameter.

The number of combinations when selecting two points from n edge points is
_n C ₂ = n! / {2! (n-2)! } = N (n-1) / 2 (a7)
It is. Therefore, when there are n edge points on one straight line, the vote value of the cell representing the straight line is n in the standard Hough transform and n (n-1) / 2 in CHT. From this, CHT has a more pronounced voting peak than the conventional standard Hough transform, making it easier to detect straight lines. On the other hand, however, the combination of all edge points in the image is enormous. Therefore, the amount of calculation is reduced by dividing the image into several blocks, limiting to a pair of edge points in the block, and voting.

  In CHT, an input image is first divided into K blocks. Subsequently, the pair of edge points is limited to the edge points in the block, and the parameters obtained from all the edge point pairs are voted. After voting, the peak is detected from the parameter plane and the straight line is detected as in the normal Hough transform. Since CHT limits voting only to edge point pairs in a block, there is a risk that the advantage of the Hough transform that global lines can be detected is impaired. Further, the higher the number of divisions, the higher the speed can be expected. However, the image division forcibly roughens the axis of the parameter plane, which adversely affects the straight line detection accuracy. For this reason, there is a problem that accuracy must be sacrificed in order to achieve sufficient speedup.

  If such a Hough transform is to be executed for a point in a three-dimensional space, it takes a long time to calculate and becomes impractical. In addition, a large amount of calculation is required for a circle in the xy orthogonal coordinate system and a point on the spherical surface in the xyz orthogonal coordinate system, and it is difficult to put it to practical use.

Recently, it is possible to obtain three-dimensional image data in a form that can be calculated like an MRI image, and the present invention uses straight lines, circles (parts), planes, spheres from such three-dimensional image data. Useful for extracting shapes such as ellipses.
Basically, the type of line or surface to be detected is expressed in the form of an equation. In the parameter coordinate system of the equation, one point in the original space is a curve or a straight line. In the parameter coordinate system, curves or straight lines corresponding to a plurality of points on a specific shape in the original space intersect at one point.
If attention is paid only to the intersecting intersections, even if a plurality of shapes exist in the original space, peaks corresponding to the plurality of shapes exist in the parameter coordinate system, and it is possible to identify them individually.

  In this calculation, draw a sequence of points that make up all curves or straight lines in the parameter coordinate system, find these intersections and calculate the maximum number of intersections, or sum the points in a partitioned parameter space (voting space) It is an enormous amount of calculation. In the present invention, the amount of calculation is reduced by obtaining intersection points from a minimum point sequence from which parameters can be determined, obtaining intersection points for other point sequences, and detecting peaks from the group of these intersection points. .

The present invention is different from the conventional Hough transform in that the Hough transform is increased in dimension and multi-variable. As described above, the concept of the Hough transform can be easily extended to detection of analytical figures such as circles and ellipses, distance images, three-dimensional planes and curved surfaces from normal vector images. However, equations representing these shapes include many parameters, and a simple method requires a large amount of memory and calculation.
In the conventional method, since all the trajectories of the converted expression are voted, the array of the parameter space becomes infinite, and it cannot be said that a large array is prepared. Has been used.

The configuration of the present invention is shown in FIG.
The image data processing device (7) of the present invention includes an extraction means (1) for acquiring a plurality of edge points from n-dimensional image data, a selection means (2) for selecting m from the acquired edge points, and a specification A creation means (3) for giving n parameters to an equation representing a shape and creating a simultaneous equation consisting of m equations, and a computing means (4) for obtaining an intersection consisting of k parameters as a solution of the created simultaneous equations ) And the intersection of k parameters to a k-dimensional parameter space (voting space), and the intersection of k parameters for at least a part of m edge points, which are at least partially different, is voted in the parameter space. The voting means (5) for performing the determination and the selection means (6) for obtaining the peak at the stage where a plurality of intersections are accumulated. Reference numeral 10 denotes a camera for acquiring image data, an imaging device such as an MRI, and 11 denotes a display device for displaying a processing result.
The operation is generally as follows.
In the image space, two arbitrary points (when the figure to be extracted is a straight line) are taken from the group of edge points. The straight line parameters obtained from these two points are voted as intersections in the parameter space. The other two points (one point may be duplicated) are voted in the same way for the parameter obtained. When a certain number of samples are obtained, a peak point in the parameter space is obtained by a statistical method such as centroid calculation. This is a parameter of the graphic to which the edge point belongs in the image space.

A case where a quadratic curve is extracted in two dimensions will be described as an example.
First, an array {(x ₁ , y ₁ ), (x ₂ , y ₂ ), (x ₃ , y ₃ ),..., (X _i , y _i )} in which edge points in the image are arranged at random Prepared, and in turn, a quadratic equation y = ax ² + bx + c (b1)
Assign to.
From three edge points (x ₁ , y ₁ ), (x ₂ , y ₂ ), (x ₃ , y ₃ )

y ₁ = a · x ₁ ² + b · x ₁ + c (b2),
y ₂ = a · x ₂ ² + b · x ₂ + c (b3),
y ₃ = a · x ₃ ² + b · x ₃ + c (b4)
The following three equations are obtained.
One intersection (a ₁ , b ₁ , c ₁ ) is obtained from these three equations.
Here, this intersection is voted on the parameter space (in this case, the three-dimensional abc space) (FIG. 2).
Next, one intersection point (a ₂ , b ₂ , c ₂ ) is similarly obtained from the edge points (x ₂ , y ₂ ), (x ₃ , y ₃ ), (x ₄ , y ₄ ), and is obtained in the parameter space. Vote. When the voting of the intersection obtained from all the edge points is completed, the intersection of the (i-2) point is voted in this example. Therefore, when a parameter (abc) of a space where a vote exceeds a certain threshold value is substituted into the first quadratic equation y = ax ² + bx + c, this becomes a quadratic curve existing in the image.

Even before the voting of the intersections obtained from all the edge points is completed, if there is a voting exceeding a threshold value in a certain space, it may be terminated halfway. In this way, the calculation amount can be reduced. The threshold setting is a very important part in the Hough transform because it is possible to detect noise when the threshold is set low, and short lines are not detected when the threshold is set high. First, set a temporary threshold value based on the relationship with the number of edge points in the image (a few percent of the number of points, the number of √points, etc.), and then several times Correct the threshold by repeating the test.
There is not necessarily one space where there are votes above a certain threshold, and there may be multiple spaces. This means that there are a plurality of quadratic curves in the original image.

The parameter space (voting space) is demarcated with a range having a width in consideration of fluctuations of edge points (for example, cells are delimited by values of a =..., −Δa, 0, + Δa, + 2Δa,...). Or ignore the lower digits as 2 significant digits).
In this example, the three edge points are partially overlapped and selected, but the edge points (x4, y4) are next to the edge points (x1, y1), (x2, y2), (x3, y3) without overlapping. ), (X5, y5), (x6, y6), or various combinations such as selecting all combinations are conceivable, but this is not essential, so the optimum selection should be adopted as appropriate. That's fine.

In order to remove unnecessary lines of the detected curve, the coordinates of both ends when the edge points used for obtaining the extracted intersection are arranged in order are set as the range of the detection curve, and are represented by line segments.
Further, in order to prevent erroneous detection, it is confirmed whether the detected curve actually passes over the edge point. The distance (error) from the edge points {(x _i , y _i ),...] Used when obtaining the extracted intersection points is calculated. The calculation method is to obtain the length of the perpendicular from the edge point to the detection curve, but if simplified, error = y _i − (a ₀ · x _i ² + b ₀ · x _i + c ₀ ) (b5)
It becomes. This error or the square of the error is calculated for all the edge points used to determine the extracted intersection, and if the average value exceeds the threshold value, it is determined that a false detection has occurred, and this curve is detected. Is invalid.

Also, regarding the voting of intersections, it is difficult to accurately represent the shape of an object with a curve, and it is difficult to have a plurality of exactly the same intersections due to the mixing of noise during image acquisition and the difficulty of accurate edge detection. Therefore, for example, a determination method is adopted in which if the two significant digits of the intersection coincide with each other, they are regarded as the same intersection. In that case, the extracted intersections are slightly shifted. Therefore, an average value of the extracted intersection points is taken and used as an accumulation point.
The above is the principle of quadratic curve detection. FIG. 3 shows this detection algorithm.

Similarly, in order to detect a cubic curve, a combination of four edge points (x _i , y _i ), (x _{i + 1} , y _{i + 1} ), (x _{i + 2} , y _{i + 2} ), (x _{i + 3} , y _{i + 3} ) is represented by a cubic equation. y = a · x ³ + b · x ² + c · x + d (b5)
Substituting into (4), one intersection (a _i , b _i , c _i , d _i ) is obtained from equation 4, and stored and voted.
As described above, the memory amount can be reduced by storing and voting only the intersections, and the accumulation points can be easily extracted as compared with the CHT using the ρ-θ expression. A higher-order curve pattern that requires more variables is y = A ₁ · x ^m + A ₂ · x ^m−1 + A ₃ · x ^m−2 + ... + A _m (b6)
The intersection is (A ₁ , A ₂ , A ₃ ...... A _m )
It can be easily handled simply by increasing the array of intersections. Of course, detection of a shape such as an ellipse or a spherical surface can be considered in the same way.
In order for these simultaneous equations to have a solution, it is preferable to define an equation of a specific shape as a linear combination of parameters, that is, as a linear function.

Next, a case where spherical extraction is performed in three dimensions will be described as an example.
First, an array {(x1, y1, z1), (x2, y2, z2), (x3, y3, z3),..., (Xi, yi, zi)} in which edge points in the image are arranged at random. Prepare this and substitute it into the equation (xa) ² + (y−b) ² + (z−c) ² = r ² in order.
From four edge points (x1, y1, z1), (x2, y2, z2), (x3, y3, z3), (x4, y4, z4)

(x1−a) ² + (y1−b) ² + (z1−c) ² = r ² (c1),
(x2−a) ² + (y2−b) ² + (z2−c) ² = r ² (c2),
(x3−a) ² + (y3−b) ² + (z3−c) ² = r ² (c3),
Four equations (x4−a) ² + (y4−b) ² + (z4−c) ² = r ² (c4) are obtained.
One intersection (a1, b1, c1, r1) is obtained from these four equations.
Here, this intersection is voted on the parameter space (in this case, the four-dimensional abcr space).
Hereinafter, as in the previous examples, a parameter (abbcr) in which the number of intersection points exists is obtained, and this parameter (abbcr) is calculated as the first sphere equation. If (x−a) ² + (y−b) ² + (z−c) ² = r ² is substituted, this becomes a spherical surface existing in the image.
In this case, the spherical equation for obtaining the intersection point is described as (x−a) ² + (y−b) ² + (z−c) ² = r ² , but ax ² + bx + cy which is a linear combination of parameters. By defining ² + dy + ez ² + fz + g = 0, it is easy to obtain a solution.

As described above, the description has been given using the two-dimensional and three-dimensional examples, but it is obvious that this can be applied to the n-dimension.
In the conventional Hough transform, since all the point sequences constituting the Hough curve are voted in the parameter space, a lot of calculation time is required. In the present invention, instead of drawing a Hough curve, it is possible to reduce the amount of calculation by directly obtaining the intersection coordinates and voting these coordinates in the parameter space.

  In the image space, two arbitrary points (when the figure to be extracted is a straight line) are taken from the group of edge points. The parameters of the straight line obtained from these two points are voted to the parameter space. The other two points (one point may be duplicated) are voted in the same way for the parameter obtained. When a certain number of samples are obtained, one point is calculated from the plurality of points in the parameter space by the least square method. A figure is drawn in the image space from this one-point parameter. In applying the method of least squares, it is desirable to exclude points belonging to other figures in advance based on point density information.

  Since there are n (n−1) / 2 straight lines obtained from n edge points, voting a solution obtained from all pairs of edge points to the parameter space requires much calculation time. Therefore, first, edge points are extracted with a sparse density in the image space, a straight line is obtained from the pair, and voted to the parameter space. Projecting (drawing) the image in the image space as a temporary solution where the points are dense in the parameter space. Points close to the figure projected onto the image space are extracted as dense points with high density, and these solutions are voted on to the parameter space. In the parameter space, the true solution is obtained by the least square method, the centroid method, the maximum density method, etc. from the densely packed solution.

  When the figure to be obtained is a curve, in the above method, the density of edge point extraction is changed according to the curvature of the curve in the temporary solution. That is, edge points are extracted at a high density at a portion with a small curvature radius and at a low density at a portion with a large curvature radius. As a result, harmony is achieved between accuracy improvement and calculation time reduction.

1. A specific pattern can be extracted from medical three-dimensional data (CT, MRI, etc.).
2. When applied to a mobile robot or the like, a circumscribed pattern or an inscribed pattern can be created for the measured three-dimensional data. Thereby, a movement plan can be set or an object can be recognized.
3. A specific pattern can be extracted from multidimensional data, that is, a specific change can be extracted from multivariate data.
For example, it is possible to extract a cylindrical shape from three-dimensional data (substantially four-dimensional data) taken from a moving object and extract a motion of a certain object.

Diagram showing the configuration of the device A diagram showing voting for quadratic curve detection (voting to abc space by finding one intersection from three edge points) Diagram showing quadratic curve detection algorithm Diagram showing the principle of the Hough transform

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Extraction means 2 Selection means 3 Creation means 4 Calculation means 5 Voting means 6 Selection means 7 Image data processing apparatus 10 Imaging apparatus 11 Display apparatus

Claims (6)

  An extraction step for acquiring a plurality of edge points from n-dimensional image data, a selection step for selecting m from the acquired edge points, n parameters for an equation representing a specific shape, and m equations A creation step for creating simultaneous equations, an operation step for obtaining an intersection point of k parameters as a solution of the created simultaneous equations, and voting the intersection point of k parameters to a k-dimensional parameter space, at least a part of which is An n-dimensional Hough comprising a voting step for voting intersections composed of k parameters for different m edge points to a parameter space, and a selection step for obtaining a peak when a plurality of intersections are accumulated. Image data processing method by conversion.   2. The image data processing method according to claim 1, wherein the equation representing the specific shape in the creating step is expressed as a linear function of k parameters characterizing the shape.   2. The image data processing method according to claim 1, further comprising a step of obtaining a true intersection by a least square method from a group of intersections belonging to the peak after obtaining the peak by the selecting step.   The method further comprises the step of drawing a graphic in the image space based on the peak obtained in the selection step, extracting edge points with a sparse density in the extraction step, and drawing the graphic in the image space based on the peak obtained from these edge points. 2. The image data processing method according to claim 1, wherein drawing is performed, edge points in the vicinity of the figure are extracted with a dense density, and a peak is obtained again from these edge points.   The method further comprises a step of drawing a figure in an image space based on the peak obtained by the selection step, extracting edge points with a first sparse density in the extraction step, and based on the peaks obtained from these edge points. When the figure has a small radius of curvature, the edge points near the figure are extracted with a dense density, and when the figure has a large radius of curvature, the edge points near the figure have a second sparse density. 2. The image data processing method according to claim 1, wherein a peak is extracted again from these edge points.   An extraction unit that acquires a plurality of edge points from n-dimensional image data, a selection unit that selects m from the acquired edge points, n parameters are given to an equation representing a specific shape, and m equations are included. A creation means for creating simultaneous equations, an arithmetic means for obtaining an intersection point of k parameters as a solution of the created simultaneous equations, and voting the intersection point of k parameters to a k-dimensional parameter space, at least partly An n-dimensional Hough comprising voting means for voting intersections composed of k parameters for different m edge points to a parameter space, and selection means for obtaining a peak when a plurality of intersections are accumulated. Image data processing device by conversion.

Images