JPH0516625B2 - - 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. The present invention relates to a generalized Hough transform circuit that can extract an arbitrary curve from a binary image by partially changing the Hough transform.

(Prior Art) In digital image processing, generalized Hough transform is a method for extracting an arbitrary region from a grayscale image, and this is processed by software using a computer.

(Problems to be Solved by the Invention) However, there are the following problems when applying the conventionally known generalized Hoff transform method to the case of extracting an arbitrary curve from a binary image.

When applying the generalized Hough transform to a grayscale image,
Information on the direction of change in density Z(x, y) at each point x, y is used. That is, in the grayscale image shown in Fig. 5, the vectors (∂Z/∂x, ∂Z/∂y)
The direction φ is used. However, the sixth
In the binary image shown in the figure, there is no simple method for finding the corresponding direction φ'. In other words, the direction of change (△y/△
There is no operator that can accurately calculate x). Therefore, the generalized Hough transform cannot be directly applied to the problem of extracting an arbitrary curve from a binary image.

If you try to process the Hough transform using a computer and software, the processing time will be long and it is not practical.

The present invention has been made in view of these problems, and its purpose is to create a generalized Hough transform circuit that can extract arbitrary curves from binary images at high speed by changing a part of the generalized Hough transform. The aim is to realize this.

(Means for Solving the Problems) The present invention, which solves the above-mentioned problems, comprises a binary image memory functioning as an image space, a first address counter that provides an address signal to the binary image memory, and a parameter.・Number of point spread functions (ppsf) The buffer where Nppsf is initially set and the number of points from this buffer
A second address counter to which Nppsf is set and a signal from this second address counter are given as address signals, respectively, and the x and y coordinates of ppsf with respect to the origin calculated from the reference object and reference point are stored respectively. x-ppsf table and y-ppsf table, signals x and y from the first address counter, and data △x and △y read from the x-ppsf table and y-ppsf table, respectively. an arithmetic unit that receives input and performs a predetermined operation; a parameter counter string to which the arithmetic results x _c and y _c from the arithmetic unit are given as address signals; and data from the binary image memory and the second address counter. and a control circuit which inputs a "0" detection signal of 1 and provides a control signal to each of the circuits.

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

Although the circuit of the present invention cannot necessarily express the shape as an analytical shape (parameter), it can use a curve (reference object) that can express it as binary data to generate other curves containing noise. This is a system that detects from a binary image (referred to as image space) and learns its position. First, the processing procedure will be explained.

(Procedure) (1) Parameter point spread function: Parameter Point Spread
Creating a Function (hereinafter abbreviated as ppsf) table Set reference points (x _c , y _c ) for the reference target.

For this reference point, the origin (0,0)
Create ppsf table.

The ppsf value of points x and y on the image space is a set of reference points for all reference objects that can pass through points x and y. For example, as shown in FIG. 7, consider a case where the reference object is a circle and the reference point is the center of the circle. At this time, all reference objects passing through (including) the origin of the image space shown in FIG. 8 are considered. Here, the solid line circle is the reference target including the origin, and the broken line circle is the locus of the reference point, that is, the value of ppsf at the origin. Figure 9 is a diagram showing the trajectory of this reference point, where (x ₁ , y ₁ ), (x ₂ ,
y ₂ )...(xn, yn) is the value of ppsf with respect to the origin.

A ppsf table is a table of this as shown in FIG.

11 to 14 are explanatory diagrams when the reference object is an equilateral triangle and the reference point is the center of gravity of the equilateral triangle. FIG. 11 shows the reference object, the reference point, and the first
Figure 2 shows a reference object passing through the origin in the image space, Figure 13 shows the ppsf at the origin, and Figure 14 shows a table of this.

As is clear from the above explanation, the point (x,
The ppsf value of y) is obtained by translating the ppsf value of the origin (0, 0) by (x, y). Therefore, the value of ppsf at the origin is expressed as follows.

_{ (X, _{Y ) |} ) Also, the value of ppsf at points x and y is expressed as follows.

{(X, Y) | X△=x _c −x′+x, Y△=y _c −y′+y} (2) Conversion from image space to parameter space image)
For each point x, y that is "1", the following is performed.

For the values (x _i , y _i ) on the ppsf table,
Find all (x ⁱ _c , y ⁱ _c )△=(x+x _i , y+y _i ).

Here, (x ⁱ _c , y ⁱ _c ) (i=1 to n) is the value of ppsf at points x and y. That is, the points x and y on the image space are (x ⁱ _c , y ⁱ _c ) (i=1 to n)
This means that there is a possibility that it will be a point above any of the objects of reference with .

Add 1 to the points x ⁱ _c and y ⁱ _c in the parameter space. Note that the initial value of each point in the parameter space is "0".

(3) Search of parameter space Search the parameter space shown in FIG. 16 to find maximum points (x ¹ _c , y ¹ _c ), ... (x ⁿ _c , y ⁿ _c ). These become the positions of reference points on the image space.

In the present invention, in the above-described procedure, the part that converts the image space to the parameter space is implemented in hardware, so that curve extraction from a binary image can be performed.

FIG. 1 is a block diagram of an embodiment of the present invention. In the figure, 1 controls the entire circuit,
A timing and control circuit to control (hereinafter simply referred to as a control circuit), 2 a first address counter to which a count-up signal and a clear signal are given from the control circuit 1, and 3 an address signal from the address counter 2; It is a binary image memory that is given , and functions as an image space, and the data read from it is
It is applied to the control circuit 1. 4 is Batsuhua,
A second address counter 5 is set with data from the buffer 4, and is supplied with load and countdown control signals from the control circuit 1.
From here, a signal for "0" detection is applied to the control circuit.

6 is an x-ppsf table, and 7 is a y-ppsf table, both of which use memories and are given address signals from the second address counter 5, respectively. 8 is the data Δx from the x-ppsf table 6 and the first address counter 2
The first arithmetic unit 9 inputs the signal x from the y-ppsf table 7 and the first
a second arithmetic unit which receives the signal y from the address counter 2; and 10 a parameter counter which inputs the calculation results x _c ′ and y _c ′ from the first and second arithmetic units 8 and 9 as address signals. A column that functions as a parameter space. however,
△x, △y are the ppsf values regarding the origin,
x _c ′, y _c ′ are the values of ppsf regarding (x, y).

Note that the parameter counter sequence 10 as this parameter space can be replaced with a random
Access memory (RAM) may also be used.

To explain the operation of the circuit configured in this way,
It is as follows.

First, a computer program not shown here calculates the ppsf value from the reference object and reference point to the origin, and stores its x and y coordinates in the x-ppsf table 6 and the y-ppsf table 7, respectively. Initialize each and set the number of points.
Set Nppsf to buffer 4. In this initial setting state, the first address counter 2 points to the first address of the binary image memory 3 functioning as an image space. Further, the parameter counter column 10 contains all "0"s. After the above initial settings, the following processing operations are performed.

The control circuit 1 increments the first address counter 2 until the image data from the binary image memory 3 becomes "1".

The number Nppsf of ppsf is read out from the buffer 4 and set in the second address counter 5.

The first and second arithmetic units 8 and 9 add the data △x, △y read from the x-ppsf table 6 and y-ppsf table 7, respectively, and the signals x, y from the address counter 2, respectively. Then, shift the ppsf value for the origin to the x, y coordinates of the sample.

Computation results from the first and second computing units 8 and 9
Parameter counter sequence 10 pointed to by x _c ′, y _c ′
Increment the counter in

If the second address counter 5 is “0”,
The first address counter 2 is incremented by 1 and the process returns to the processing operation. Otherwise, the second address counter 5 is decremented by 1 and the process returns to the processing operation.

The operation ends when the first address counter 2 finishes scanning the entire area of the binary image memory. After this, we explore the parameter space and find the local maximum point (x ¹ _c ,
y ¹ _c )...(x ⁿ _c , y ⁿ _c ), and this method is performed using a known technique.

FIG. 2 is a block diagram showing another embodiment of the present invention. In this embodiment, the Hough transform can be performed even when the reference object is unknown not only in its position but also in its size S and direction θ.

In the figure, 11 is an S counter in which the number Ns of enlargement/reduction coefficients of the reference object read out from the buffer 4 is set, 12 is a scale function table that stores the enlargement/reduction coefficients of the reference object, and 13 is from the buffer 4. Rotation angle θ of the reference object to be read
14 is a sin and cos function table storing the values of sin θ and cos θ for the rotation angle θ of the reference object. 15 and 16 are multipliers for multiplying by the coefficient S, and 17 is a rotating part calculation circuit that inputs the signals x and y from this multiplier and the signals sinθ and cosθ from the sin and cos function table 14, and the calculations from here are input. The outputs X and Y are applied to first and second arithmetic units 8 and 9. In this embodiment, the multipliers 15 and 16 and the rotating part calculation circuit 17 are
The point provided between the x-ppsf table 6, y-ppsf table 7 and the first and second arithmetic units 8, 9 is the first point.
This is different from the illustrated embodiment.

FIG. 3 is a detailed block diagram of the rotation calculation circuit 17 in FIG. 2. In this circuit, MUL is a multiplier, SUB is a subtracter,
ADD indicates an adder, and the output X of the subtracter SUB and the output Y of the adder ADD are expressed by the following equation.

X Y = cos θ - sin θ sin θ cos θx y The operation of the circuit configured in this way will be explained as follows, excluding the portions that overlap with the operation of the circuit in FIG.

(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 12, and the number Ns of the coefficients is set in the buffer 4.

sin θ for the rotation angle θ of the reference object considered,
The value of cos θ is set in the sin and cos function table 14, and the number Nθ of this rotation angle θ is set in the buffer 4, respectively.

(Changes in operation) The sections in the explanation of the operation of the circuit shown in FIG. 1 will be changed as follows.

x-ppsf table 6 and y-ppsf table 7
The data △x, △y pointed to by the second address counter 5 are taken out, and the individuality Ns of the coefficient of the buffer 4 is loaded into the S counter 11.
do.

The following processes from -1 to -3 are performed until the value of the S counter 11 becomes "0".

-1 Set the value pointed to by the S counter 11 of the scale function table 12 in the multipliers 15 and 16.

-2 The number Nθ of the rotation angle θ of the buffer 4 is expressed as θ
Load it into the counter 13.

Until the value of the θ counter 13 becomes “0”,
Perform the following processes (a) to (d).

(a) The values (sin θ, cos θ) indicated by the θ counter 13 of the sin, cos function table 14 are set in the rotation calculation circuit 17.

(b) Each arithmetic circuit performs a predetermined arithmetic operation, and (x _c ,
Find _yc ).

(c) The parameter counter row 10 includes an S counter 11, a θ counter 13, and adders 8 and 9.
The counter values corresponding to the signals θ, S, x _c , y _c given from the above are incremented by 1.

(d) Decrement the value of the θ counter 11 by 1.

-3 Decrement the value of S counter 11 by 1.

FIG. 4 shows that instead of using a multiplier to change the size S and direction θ in the embodiment shown in FIG.
and y-ppsf table 7. FIG.

Here, the size of each table 6 and 7 is
Each is multiplied by NθxNs.

(Effects of the Invention) As explained above, according to the present invention, the generalized Hough transform can extract any curve from a binary image at high speed by configuring the main parts by hardware. The circuit can be realized.

[Brief explanation of the drawing]

1 and 2 are configuration block diagrams showing an example of the circuit of the present invention, FIG. 3 is a detailed configuration block diagram of the rotating part calculation circuit in the circuit of FIG. 2, and FIG. 4 is another example of the circuit of the present invention. A block diagram of the main parts showing the
FIG. 5 is an explanatory diagram of a grayscale image, FIG. 6 is an explanatory diagram of a binary image, and FIGS. 7 to 16 are diagrams for explaining the principle of Hough transform by the circuit of the present invention. 1...Control circuit, 2...Address counter, 3
...Binary image memory, 4...Buffer, 5...Address counter, 6...x-ppsf table, 7...
...y-ppsf table, 8, 9...adder, 10...
...parameter counter column.

Claims (1)

[Claims] 1. A binary image memory that functions as an image space, a first address counter that provides an address signal to the binary image memory, and a buffer to which the number Nppsf of parameter point spread functions (ppsf), which is a set of reference points for all possible reference objects, is initially set; a second address counter to which the number Nppsf from this buffer is set; An x-ppsf table and a y-ppsf table in which the signals from this second address counter are respectively given as address signals, and the x and y coordinates of ppsf with respect to the origin calculated from the reference object and reference point are stored, respectively. and signals x, y from the first address counter
and an arithmetic unit that inputs the data △x, △y read from the x-ppsf table and the y-ppsf table, respectively, and performs a predetermined calculation, and the calculation results xc, yc from this arithmetic unit are given as address signals. a parameter counter string stored in the data, and the data from the binary image memory and the second
A generalized Hough transform circuit comprising: a control circuit that receives a "0" detection signal from an address counter of the circuit and provides a control signal to each of the circuits.