JPH0516624B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention relates to a generalized Hough transform circuit for extracting an arbitrary region from a grayscale image in digital image processing.

(Prior art) An object whose shape is known and can be expressed as a silhouette in an image, but which cannot be expressed in an analytical form (parameters) (this is called a reference object) is created using a grayscale image (called an image space). ) to detect the object and find its position (direction and size can also be handled as variable, but in this case the direction and size are assumed to be fixed) is the generalized Hough transform. .

Conventionally, such Hough transform has been processed by software using a computer, and the principle of the procedure will be explained below using FIGS. 10 to 13.

First, a reference point (x _c ,
y _c ). Next, the following is performed for each point (x, y) on the boundary of the reference object IM.

Find the angle φi′ in the normal direction of the boundary of the reference object,
Obtain φi quantized at a predetermined level.

Distance between point (x, y) and reference point (x _c , y _c ) in the x-axis direction and y-axis direction Δx△=x _c −x, Δy△=y _c − y
seek.

Add (Δx, Δy) to the column corresponding to φ in the R table shown in FIG.

The R table is created through the above steps.

Subsequently, a transformation from image space to parameter space is performed (assuming that in image space the reference object is known to be brighter or darker than the background).

That is, the following is performed for each point (x, y) in the image space shown in FIG.

The direction φi' of the gradient of the concentration at the point (x, y) is determined, and φi quantized at a predetermined level is obtained.

All (Δx ₁ ,
Δy ₁ )…(Δxn, Δyn), do the following.

−1 x _c Δ=x+Δxj (j=1 to n) y _c Δ=y+Δyj is calculated.

−2 The value on (x _c , y _c ) in the parameter space is +
Set to 1.

Note that the initial value of each point in the parameter space is "0".

Next, the parameter space shown in FIG. 13 is searched to find maximum points (x ¹ _c , y ¹ _c )...(x ^m _c , y ^m _c ).
These become the positions of reference points on the image space.

(Problems to be Solved by the Invention) The Hough transform processed according to such a procedure has the feature of being resistant to noise, but has the problem that the processing time is long and it is not practical.

The present invention has been made in view of these problems, and its purpose is to realize a circuit that can perform generalized Hough transform at high speed using hardware.

(Means for Solving the Problems) The present invention that solves the above-mentioned problems is such that a gradient image block becomes a reference target when creating an R table, and becomes an image space gradient image block when converting from image space to parameter space. It's hot,
a gradient image memory comprising an area for storing a binary image representing the magnitude of the gradient and an area for storing a grayscale image representing the direction of the gradient; an address counter for supplying an address signal to the gradient image memory; and a grayscale image in the gradient direction. a reference counter column to which data from the image area is given as an address signal;
A down counter into which data from this reference counter array is input, and Δx to which signals from this down counter and data from the gradient direction grayscale image area are respectively given as address signals.
When creating the R table and the R table for Δy, input the signals x, y from the address counter and the coordinate signals x _c , y _c of the reference point,
x-x _c and y-y _c are respectively calculated, and the calculation results are written in the R table for Δx and the R table for Δy, and at the time of conversion from image space to parameter space, the signal x from the address counter is , y and the signals Δx and Δy read from the R table for Δx and the R table for Δy are input, and x+
An arithmetic unit that calculates Δx, y+Δy, a parameter counter array to which the calculation results x+Δx, y+Δy from this arithmetic unit are given as address signals, and a signal from the gradient magnitude binary image area are inputted to each circuit. The present invention is characterized in that it includes a control circuit that provides a control signal.

(Example) Hereinafter, an example of the present invention will be described in detail using the drawings.

FIG. 1 is a block diagram of an embodiment of the present invention. In the figure, 1 is a timing and control circuit that integrates and controls the entire circuit (hereinafter simply referred to as the control circuit), 2 is an address counter to which the count-up signal and clear signal are given from the control circuit 1, and 3 is an address. A gradient image memory to which the address signal from counter 2 is applied, R
When creating a table, it becomes a reference target gradient image block, and when converting from image space to parameter space, it becomes an image space gradient image block. The gradient image memory 3 consists of an area 31 for storing a binary image representing the magnitude of the gradient, and an area 32 for storing a grayscale image representing the direction of the gradient.

Here, the definition of a gradient image is as follows.

As shown in FIG. 2, the gradient image of the grayscale image A (original image) consists of an image representing the gradient magnitude γ and an image representing the gradient direction φ. That is, the point (x,
If the concentration of y) is A(x, y), then the point (x, y)
The gradient gradA(x, y) at is (∂A(x, y)
y)/∂x, ∂A(x, y)/∂y). A binary image representing the magnitude of the gradient is obtained by converting the magnitude γ of the gradient into a binary value, and a grayscale image representing the direction of the gradient is represented by a gray value representing the direction φ of the gradient. FIG. 3 is a diagram explaining the above relationship. Returning to FIG. 1, 4 is the gradient image memory 3
A count-up signal is applied from the control circuit 1 to the reference counter array to which data φ representing the direction of the gradient from the gradient direction grayscale image area 32 is given as an address signal. 5 is a down counter to which data from the reference counter row 4 is given; 6 is an R table for Δy; and 7 is an R table for Δx, all of which use memory, and which receive the signal φ from the gradient direction grayscale image area 32. is given as an address signal, and data from the down counter 5 is given as an address signal.

8 is an arithmetic unit that subtracts or adds the signal from the address counter 2 and the signal switched and applied by the bus switch 9; 10 is a parameter counter column to which the signal from the arithmetic unit 8 is given as an address signal. Note that this parameter counter may use random access memory (RAM).

The operation of the circuit configured as described above will be explained separately as follows: when creating an R table and when converting from image space to parameter space.

(When creating the R table) Figure 4 shows the signal flow and control signals at this time. In this circuit, initial settings are performed as follows.

A gradient image of the reference target image is obtained and its data is set in a gradient image memory (gradient image block) 3.

All "0"s are set in reference counter column 4.

Address counter 2 points to the first address of gradient image memory 3.

After the above initial settings, the following processing operations are performed.

The control circuit 1 increments the address counter 2 until the gradient magnitude binary image data becomes "1".

Reference counter row 4 indicated by data φ from gradient direction grayscale image area 32 at this time
The data is stored in the down counter 5.

The contents of reference counter column 4 pointed to by data φ are incremented by 1.

The arithmetic unit 8 calculates the signals x, y from the address counter 2 input here, and the bus switch 9.
For the reference point coordinate signals x _c and y _c from x-
Calculate x _c and y−y _c , respectively.

The calculation results x-x _c and y-y _c are applied via the bus switch 9 to the predetermined locations of the R table 7 for Δx and the R table 6 for Δy indicated by the data φ and the contents of the down counter 5. Write each.

FIG. 5 is a conceptual diagram showing how data is written to the R table 6 for Δy and the R table 7 for Δx.

The contents of address counter 2 are incremented by 1 and the process returns to the processing operation.

When the address counter 2 finishes scanning the entire area of the gradient image memory 3, the operation ends and all data are written into the R tables 6 and 7. (When converting from image space to parameter space) The signal flow and control signals at this time are shown in FIG.
In this circuit, initial settings are performed as follows.

A gradient image of the image space image is obtained and the data is set in the gradient image memory 3.

All "0"s are set in the parameter counter column 10.

Address counter 2 points to the first address of the gradient image.

After the above initial establishment, the following processing operations are performed.

The control circuit 1 increments the address counter 2 until the gradient magnitude binary image data becomes "1".

The value φ of the point pointed to by the address counter 2 in the gradient direction grayscale image area 32 is extracted.

The contents of the counter corresponding to φ in the reference counter column 4 are stored in the down counter 5.

Until the value of down counter 5 becomes “0”,
Perform the following processes -1 to -4.

-1 Read the data Δx and Δy of the address indicated by φ and the down counter 5 in the R table 7 for Δx and the R table 6 for Δy.

FIG. 7 is a conceptual diagram showing how this data is read from the R tables 6 and 7.

-2 In the arithmetic unit 8, the signals x, y,
For the read data Δx and Δy from the R tables 6 and 7 from the bus switch 9, x+
Calculate Δx, y+Δy, respectively.

−3 x+Δx of parameter counter row 10,
Multiply the counter pointed to by y+Δy by +1.

-4 Decrement the down counter 5 by 1.

The address counter 2 is incremented by 1 and the process returns to the processing operation.

When the address counter 2 finishes scanning the entire gradient image memory 3, the operation ends.

FIG. 8 is a block diagram of the main parts of another embodiment of the present invention. In this embodiment, the Hough transform can be performed even when not only the position of the reference object but also the size S and direction θ are unknown. Vessel 1
1, an _Ns buffer 12, an S counter 13, a scale function table 14, an Nθ buffer 15, a θ counter 16, and a sin and cos function table 17. S counter 13,
The outputs of the θ counter 16 are respectively given to the parameter counter array 10, and the outputs of the scale function table 14, sin and cos function tables 17 are respectively given to the second arithmetic unit 11.

FIG. 9 is a detailed block diagram of the second arithmetic unit 11. As shown in FIG. In this circuit, MUL is a multiplier, ADD is an adder, and SUB is a subtracter. The adder ADD outputs a signal Δx′ that takes into account the magnitude S and direction θ, and the subtracter SUB outputs a signal Δy' that takes into account the magnitude S and direction θ.

The operation of the circuit constructed in this way will be explained as follows, excluding the parts that overlap with the operation of the circuit of FIG.

The operation when creating the R table is the same as that shown in FIG. (When converting from image space to parameter space) (Initial settings to be added) The coefficients for scaling up and down the reference object to be considered are set in the scale function table 14, and the number of the coefficients is set in the Ns buffer 12.

sin θ for the rotation angle θ of the reference object considered,
Set the value of cos θ in the sin and cos function table 17, and set the number of θ in the Nθ buffer 15.
Set to .

(Changes in operation) The operation part until the value of the down counter 5 becomes "0" in the above section is changed as follows.

Until the value of down counter 5 becomes “0”,
Perform the following processes -1 to -4.

−1 φ in R tables 7 and 6 for Δx and Δy
and the data Δx and Δy of the address indicated by the down counter 5 are read out.

-2 The value of Ns buffer 12 is converted to S counter 1.
Store in 3. The value of S counter 13 is “0”
Perform steps (a) to (c) until the result is reached.

(b) S counter 13 of scale function table 14
The value pointed to by is set to the input of the second arithmetic unit 11.

(b) Store the value of the Nθ buffer 15 in the θ counter 16. Until the value of the θ counter becomes “0”,
Processes (Ro-1) to (Ro-4) are performed.

(B-1) The values (sin θ, cos θ) indicated by the θ counter 16 of the sin, cos function table 17 are set to the inputs of the second arithmetic unit 2.

(B-2) Perform predetermined calculations using the second arithmetic unit and the first arithmetic unit to obtain x _c and y _c .

(B-3) Parameter counter row 10 x _c , y _c ,
Let each value of the counter corresponding to S and θ be +1.

(B-4) Decrement the value of the θ counter 16 by 1.

(c) Decrement the value of S counter 13 by 1.

-3 Decrement the down counter 5 by 1.

(Effects of the Invention) As explained above, according to the present invention, the generalized Hough transform is mainly performed by a hardware circuit, and the generalized Hough transform can be performed at high speed. .

[Brief explanation of the drawing]

FIG. 1 is a configuration block diagram showing an example of the circuit of the present invention, FIGS. 2 and 3 are diagrams for explaining the definition of a gradient image, and FIG. 4 is a diagram showing the flow of signals when creating an R table. FIG. 5 is a conceptual diagram showing how data is written to each R table at this time.
FIG. 6 is a diagram showing the signal flow during conversion from image space to parameter space, FIG. 7 is a conceptual diagram showing how data is read from each R table at this time, and FIG. 8 is a circuit of the present invention. FIG. 9 is a block diagram of the configuration of the second arithmetic unit in FIG. 8, and FIGS. 10 to 13 are diagrams explaining the principle of generalized Hough transform. 1...Control circuit, 2...Address counter, 3
...Gradient image memory, 31... Gradient magnitude binary image area, 32... Gradient direction gray image area, 4...
Reference counter row, 5...Down counter, 6...R table for Δy, 7...R table for Δx, 8... Arithmetic unit, 9... Bus switch, 10
...parameter counter column.

Claims (1)

[Claims] 1. Create a reference table that stores the position (Δx, Δy) from the reference point for each point on the boundary of the reference object and the angle of the normal to the boundary of each point on the boundary of the reference object. When converting from image space to parameter space, it becomes a reference gradient image block, and when converting from image space to parameter space, it becomes an image space gradient image block. a gradient image memory consisting of an area for storing an image; an address counter that provides an address signal to the gradient image memory; a reference counter column to which data from the gradient direction gray image area is provided as an address signal; a down counter into which data from the counter row is input; a reference table for Δx and Δy to which signals from the down counter and data from the gradient direction gray image area are respectively given as address signals;
When creating the reference table, the signals x, y from the address counter and the coordinate signals xc,
Input yc and calculate x-xc and y-yc, respectively.
This calculation result is written to the Δx reference table and the Δy reference table, and when converting from image space to parameter space, the signals x and y from the address counter and the Δx reference table and Δy R table are read out. signal Δx,
an arithmetic unit that inputs Δy and calculates x+Δx, y+Δy; a parameter counter array to which the calculation results x+Δx, y+Δy from this arithmetic unit are given as address signals; and a signal from the binary image area representing the magnitude of the gradient. and a control circuit that inputs a control signal to each circuit and provides a control signal to each of the circuits.