JPH04349583A - Generalized hough transform circuit - Google Patents

Abstract

PURPOSE:To detect the recognition parameter with higher accuracy than the resolution of an input image at the time of generalized Hough transform. CONSTITUTION:With respect to a gradation image, a distance (rj) of a feature point and a reference point and an azimuth phij are stored in an address position of a reference table and from the gradation value data (rj) and the phij value of each picture element (x, y) of the gradation image, signals (x), (y) of an address generator 2, a signal theta of an angle generator 10, and a signal (s) of a size fluctuation correction rate generator 11, the address transform of x+ sXrjocos(theta+phij) and y+sXrjsin(theta+phij) is executed by an address transform part 5. A reciprocal ratio of a distance between a candidate point (xG', yG', thetas) and the corresponding point of an adjacent address is accumulated in an adjacent address position on a parameter accumulation memory 8 by an accumulation arithmetic part 7, a temporary maximum point being above a prescribed threshold is determined from accumulated data, the accumulated data of an adjacent address in the periphery of the maximum point is inputted, an interpolating operation is executed and a position of the maximum point is determined by a parameter determining part 12.

Description

[Detailed description of the invention]

0001

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a highly accurate generalized Hough transform circuit used in a pattern matching circuit required for image recognition of regular objects such as mechanical parts and tools.

0002

2. Description of the Related Art Generalized Hough transform is used to detect the amount of change in the position, orientation, and size of a regular object from a noisy input image. The generalized Hough transform can be applied to objects that overlap and are partially missing, and is widely used in industrial applications. The procedure and circuit configuration of the generalized Hough transform will be described below with reference to FIGS. 3 to 7.

First, a reference point R (
xG, yG). At the same time, an arbitrary feature point Zj (xj, yj) is set within the target object. Generally, there are a plurality of feature points (j=1, . . . M), and any feature value may be given to each feature point. Normally, the direction coefficient of the edge is often used, but here,
To simplify the explanation, we will use grayscale image values (
N level: F1,...,Fi,...,FN) itself will be explained. First, reference data for matching processing is created for each feature point as follows.

1) Distance r that defines the positional relationship between feature point Zj (xj, yj) and reference point R (xG, yG)
A position vector consisting of j and azimuth φj is calculated.

2) Write all the position vectors (rj, φj) of the feature points having the feature value Fi to the address corresponding to the feature value Fi value in the reference table shown in FIG.

The above is the process for creating reference data. Next, the process for pattern matching calculation will be explained using the circuit block diagram of the conventional generalized Hough transform circuit shown in FIG.

Address signals x, y are supplied from the x, y address generator 2 to a grayscale image memory 3 that stores an input image having grayscale values as shown in FIG. Read out. The read gray value f(
x, y) in table memory 4 (rj, φj)
Using the column as an address to access, the (rj, φj) column at the address position is sequentially read. The read rj and φj values, the address signals x and y supplied from the address generator 2, the angle signal φ supplied from the angle generator 10 that provides a candidate value for the rotation angle of the object, and the image size variation correction rate. The correction factor signal s supplied from the correction factor generator 11 that gives a candidate value of
An address conversion of s×rsin(θ+φ) is executed,
Reference point candidate address in input image (xG', yG'
) is calculated. Here, in order to speed up the conversion calculation, a method is usually used in which the sin θ, cos θ table memory 9 is referred to. xG' determined in this way,
With yG', θ, and s as addresses, the value of the corresponding address position of the parameter accumulation memory 8 (FIG. 7 shows an example of the parameter accumulation memory configuration consisting of xG', yG', and θ with fixed s) A(xG', yG', θ, s)
is incremented by 1 by the cumulative calculation unit 7. The above processing is performed using θ specified by the timing and control circuit 1.
This is performed for the variation range of Point (xG”,
yG", θ", s"), and convert those points into the target object's position xG, yG, rotation angle θ, and size variation correction rate S (represents image size variation due to variation in image input magnification, etc.) shall be.

[0008]

[Problems to be Solved by the Invention] In the matching process using the generalized Hough transform realized by such a procedure and configuration, the parameters xG , yG , and θ,s cannot be calculated. Furthermore, the following facts are known regarding the generalized Hough change. The fact is that in the generalized Hough transform, the size (number of pixels) of the input grayscale image is Sx
×Sy, the number of feature points is Nf, the number of rotation increments is Nθ, and the number of increments of size variation correction rate is Ns, then Sx×Sy×
Address conversion must be performed Nf×Nθ×Ns times, and the calculation cost becomes an astronomical number. Here, if the size of the grayscale image, that is, the resolution is reduced, the calculation cost will be approximately reduced on the order of N5. If the parameters can be detected with an accuracy higher than the resolution of the image in the grayscale image memory, then the resolution of the image in the grayscale image memory can be made coarser, and the processing cost of the generalized Hough transform can be reduced. parameters can be detected, and the effect is very large. Also,
It is also extremely effective when it is desired to detect parameters with high accuracy without increasing the number of image pickup elements in the image input device and without increasing the magnification of the optical system.

The present invention has been made in view of the above, and
The purpose is to provide a highly accurate generalized Hough transform circuit that can detect recognition parameters with an accuracy higher than the resolution of an input image in generalized Hough transform.

0010

[Means for Solving the Problems] In order to achieve the above object, the generalized Hough transform circuit of the present invention calculates the position and rotation angle of a reference point (xG, yG) of a target object from the correspondence of feature points in an image. θ, a generalized Hough transform circuit for detecting a size variation correction factor s, and a grayscale image memory that stores input image data or feature image data obtained by performing feature extraction processing on the input image data as a grayscale image;
a reference table that stores the distance r and azimuth angle φ between the feature point and the reference point at the address position using the gray value data of the feature point read from the gray image memory as an address signal when creating reference data; and a pattern. During the matching operation, the address signal x from the address generator,
y and the gray value data at the pixel (x, y) read from the gray image memory using the address signals x, y as address signals, and the values of the distance r and azimuth φ read from the reference table, and the angle generator. With the signal θ from the
=x+s×rcos(θ+φ) and yG =y+s
An address converter that converts the address of ×rsin (θ+φ) and calculates the xG value and yG value, and the address (xG, yG, θ, s) on the parameter accumulation memory.
The address position (xG , yG
, θ, s) and the inverse ratio of the distance between neighboring address positions in the neighboring address position on the parameter accumulation memory; , and a parameter determination unit that determines parameters that provide a true position of the maximum point with high accuracy by performing an interpolation calculation using accumulated data in the vicinity of the maximum point as input.

[0011]

[Operation] In the generalized Hough transform circuit of the present invention, when creating reference data, the distance rj between the feature point and the reference point is calculated using the gray value data of the feature point as an address signal for the gray image.
and azimuth φj are stored in the address position of the reference table, and at the time of pattern matching calculation, the gradation value data at each pixel (x, y) of the gradation image is used as an address to read out the rj and φj values from the reference table, and Using the signals x and y from the address generator, the signal θ from the angle generator, and the signal s from the size variation correction factor generator as input, x+s×rjcos(θ+φj) and y+
The address conversion unit executes address conversion of s×rjsin(θ+φj) to generate reference point candidates (xG', yG')
is calculated, and the address on the parameter cumulative memory (xG
', yG', θ, s), the inverse ratio of the distance between the candidate point (xG', yG', θ, s) and the corresponding point of the neighboring address is the parameter of the neighboring address position on the cumulative memory. The cumulative data is accumulated in the accumulation calculation section, a temporary maximum point above a certain threshold is determined from the accumulated data, and the true maximum point is calculated with high precision by performing interpolation calculation using the accumulated data of neighboring addresses around the maximum point as input. The parameter determining unit determines the parameters that give the position of the .

0012

DESCRIPTION OF THE PREFERRED EMBODIMENTS Examples of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention. In Figure 1, 1 supervises the entire circuit.
2 is an address generator unit that supplies x and y addresses to each image memory;
3 converts analog signals from imaging devices such as TV cameras into A/
This is a grayscale image memory that stores grayscale values of a feature image obtained as a result of extracting features suitable for a recognition target from an input image obtained by D conversion or a grayscale image thereof. Here, the grayscale image memory data itself has a great influence on the recognition rate and robustness against disturbances. For example, edge curvature features that indicate the degree of dispersion of edge directions within a local area are suitable for objects whose shape is meaningful, such as tools, and for objects containing characters or designs. Suitable examples include moment amount, contrast, and complexity features that indicate the frequency of edges within a local area. Furthermore, brightness contrast, which is directly related to brightness, is affected by disturbance fluctuations in illumination conditions. In such cases, it is more stable to use features that provide high frequency components, such as edges, as much as possible.

4 is a reference table memory, and when creating reference data, as in the conventional generalized Hough transform,
The distance r and azimuth angle φ between the feature point and the reference point are stored in the corresponding address position of the reference table memory using the gray value of the feature point read from the gray image memory 3 as an address signal. Here, r and φ need to store values with as high precision as possible.

On the other hand, during the pattern matching calculation, the following processing is performed on the grayscale image memory data f(x,y) at the x and y address positions supplied from the address generator 2.

Reference table memory 4 specified by the data f(x,y) value read out from grayscale image memory 3
If the (rj, φj) column is not registered at the address position, no processing is performed, the next data is read from the grayscale image memory 3, and it is checked whether the (rj, φj) column exists. If there is a (rj, φj) sequence, the following processing is performed for the number of elements of (rj, φj).

The size variation correction factor generator 11 sends out the size variation correction factor signal s in increments at a pitch of Δs within the range in which the size of the object to be recognized can fluctuate, and performs the following processing.

Angle signal θ from the angle generator 10
is incremented at a pitch of Δθ within the angle range in which the recognition target can rotate, and is sent out, and the following processing is performed.

1) Using as input the correction factor signal s supplied from the size variation correction factor generator 11, the angle signal θ supplied from the angle generator 10, and the position vector (rj, φj) read from the reference table, the address is In the conversion unit 5, xG':=x+s×rj cos(θ+φj)yG
':=y+s×rj sin(θ+φj) address conversion is performed, and reference point candidate xG' and yG' values are calculated. In order to perform this calculation at high speed, a lookup table of sin θ and cos θ shown in the table memory 9 may be referred to. However, xG', yG'
The value must be a real number, not an integer.

2) xG',y calculated from the above calculation
When the coordinate point on the parameter space determined by the G' value and the θ, s value is P(xG', yG', θ, s), the n-neighborhood weighting coefficient detection unit 6 performs the following processing. be exposed. The distance between points near P and point P is calculated. The distance is the normal Euclidean distance. When θ and s are fixed, the neighboring points of P are 4 neighboring points ([xG'], [yG'],
θ,s), ([xG']+1,[yG'],θ,s
), ([xG'], [yG']+1, θ, s), (
[xG']+1, [yG']+1,θ,s),
When only s is fixed, the following 12 neighboring points (x, y4 neighboring points x 3) will be used.

[] is a Gauss symbol and takes an integer part.

([xG'], [yG'], θ
,s) ,([xG']+1,[yG']
, θ , s) , ([xG'] , [yG
']+1, θ, s), ([xG']+1,
[yG']+1,θ,s), ([xG'],
[yG'], θ+1,s), ([xG']
+1 , [yG'] , θ+1 , s) , ([x
G'], [yG']+1, θ+1, s), (
[xG']+1, [yG']+1, θ+1, s
), ([xG'], [yG'], θ-1
,s), ([xG']+1,[yG'],
θ−1, s), ([xG'], [yG']+
1, θ−1, s), ([xG']+1, [yG
']+1, θ-1, s) A conceptual diagram is shown in FIG. Further, if xG', yG', θ, and s are all variables, there are 36 neighboring points (x, y4 neighboring points x 3 x 3). In addition, in FIG. 2, each P is as follows.

P; (xG', yG',
θ,s)P0,0,0;([xG'],[yG
'], θ, s) P1, 0, 0; ([xG
']+1,[yG'],θ,s)P0,1,
0; ([xG'], [yG']+1, θ
,s)P1,1,0;([xG']+1,[yG
']+1,θ,s)P0,0,1;([xG'
] , [yG '] , θ+1, s) P1,0,1
;([xG']+1, [yG'], θ+1,
s) P0,1,1; ([xG'], [yG'
]+1,θ+1,s)P1,1,1;([xG']
+1,[yG']+1,θ+1,s)P0,0,-1
;([xG'],[yG'],θ-1,s
)P1,0,-1;([xG']+1,[yG']
,θ-1,s)P0,1,-1;([xG']
,[yG']+1,θ-1,s)P1,1,-1;
([xG']+1, [yG']+1, θ-1, s)
Next, a weight value for each neighboring point is determined from the calculated distance value of each neighboring point. The distance value to each neighboring point is di
(i=1,...,Np: Np is the number of neighboring points), then the weight value wi (i=1,..., Np) for each neighboring point is determined by the following equation.

wi =c/di where c is a coefficient determined by the relational expression Σwi =1.

In order to perform the above calculations at high speed, the distance value calculation calculation and the weight value calculation calculation from the distance value need to be configured using a lookup table reference type.

3) The wi calculated by the n-neighborhood weight coefficient detection unit 6 is accumulated at the address position of each neighboring point on the parameter accumulation memory 8 via the accumulation calculation unit 7.

The pixel position (x, y) is scanned from the upper left corner to the lower right corner, and the above process is repeated.

Reference numeral 12 denotes a parameter determining unit, in which a local maximum point neighborhood interpolation calculating unit 14 calculates a parameter value with higher precision for the parameter value determined by the local maximum point detecting unit 13. The local maximum point detection unit 13 calculates local maximum points that are equal to or greater than a threshold value specified by the timing and control circuit 1 with respect to the parameter cumulative memory data. When there are multiple recognition targets in the input image, there are multiple local maximum points that are equal to or higher than a certain threshold. In addition, as a method of calculating the local maximum point, a constant threshold value is used to calculate the parameter cumulative memory A(xG', yG
', θ, s) and calculates the cluster centroid using a known method.

The local maximum point neighborhood interpolation calculation section 14 performs parameter value detection with higher accuracy. Maximum point detection unit 13
When the cumulative value in the parameter cumulative memory of the neighboring points around the local maximum point detected in is Hi (i=1,...M; M is the number of neighboring points), the coordinates and cumulative value of each neighboring point can be calculated using the following equation. x
By assigning to the variables G, yG, θ, s, H and applying the least squares method, the unknown variables xG ”, yG ”,
Determine θ”, s”, H”, a, b, c, and d.

(xG −xG ”)2 /a2 + (xG
-xG ”)2 /b2 +(θ-θ”)2 /c
2 + (s-s”)2/d2 =-(H-H”) The parameter values calculated here are xG ”, yG ”,
θ'',s'' is sent to the timing and control circuit 1 as the true parameter value. Neighboring points are selected as points adjacent to the maximum point. Therefore, if θ and s are fixed, the maximum number is 8, and if only s is fixed, the maximum is 24, and 4
If all the parameters are variables, there will be a maximum of 72 neighboring points, but the number of approximate points is selected depending on the relationship between processing speed and calculation accuracy of the least squares method. However, in order to ensure sufficient calculation accuracy of the least squares method, approximately twice as many neighboring points as the unknown variable are required.

[0031]

[Effects of the Invention] As explained above, according to the present invention,
Since the local maximum point of the cumulative value that provides the reference point can be determined with high accuracy through interpolation calculation processing, recognition parameter detection of the position, orientation, and size of the recognition target can be performed without increasing the number of image sensors in the image input system. High accuracy can be achieved without increasing the magnification of the system. Furthermore, by applying the present invention, parameters corresponding to the original resolution can be detected while reducing the processing cost of the generalized Hough transform by coarsening the resolution of the image, reducing calculation time and memory for calculation. A big effect is expected on the above.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention.

FIG. 2 is a conceptual diagram of distance value calculation for n-neighborhood weight coefficient calculation.

FIG. 3 is a block diagram showing the configuration of an example of a conventional generalized Hough transform circuit.

FIG. 4 is a configuration diagram of a reference table memory of a conventional generalized Hough transform circuit.

FIG. 5 is an explanatory diagram of the principle of generalized Hough transform.

FIG. 6 is an explanatory diagram of the principle of generalized Hough transform.

FIG. 7 is an explanatory diagram of the principle of generalized Hough transform.

[Explanation of symbols]

1 Timing/control circuit 2 Generator 12, 15
Parameter determination section 13 Maximum point detection section 14 Maximum point neighborhood interpolation calculation section

Claims (1)

[Claims] Claim 1: The position and rotation angle θ of the reference point (xG , yG ) of the target object are determined from the correspondence of feature points in the image.
A generalized Hough transform circuit that detects a correction factor s for size fluctuation, and includes a grayscale image memory that stores input image data or feature image data obtained by performing feature extraction processing on the input image data as a grayscale image, and reference data. A reference table that stores the distance r and azimuth angle φ between the feature point and the reference point at the address position using the gray value data of the feature point read from the gray image memory at the time of creation as an address signal, and a pattern matching calculation. Sometimes, the address signals x, y from an address generator and the gray value data at the pixel (x, y) read out from the gray image memory using the address signals x, y are read out from the reference table as address signals. distance r and azimuth φ
, the signal θ from the angle generator, and the signal s from the size variation correction factor generator as input, xG = x + s × rco
s(θ+φ) and yG =y+s×rsin(θ+φ
) to calculate the xG value and yG value, and the address conversion unit converts the address of address (xG , yG , θ, s) and an accumulation calculation unit that accumulates the inverse ratio of the distance between the address position and the neighboring address position in the neighboring address position on the parameter accumulation memory;
A generalized Hough transform circuit comprising: a parameter determination unit that determines parameters that provide a true position of the maximum point with high accuracy by performing an interpolation calculation using accumulated data in the vicinity of the maximum point as input.