JPH0624029B2 - Image processing device - Google Patents

Description

The present invention relates to an image processing device, and is used for controlling an unmanned traveling vehicle, recognizing a motion of an observed object in real time, and the like.

[Conventional technology]

For example, when controlling an unmanned traveling robot or an autonomous vehicle, it is necessary to capture an image of an identification line previously displayed on the traveling path, a center line or a shoulder line of the road with a camera, and perform image processing in real time.
FIG. 15 is for explaining the recognition of the road by the image. FIG. 15A is an image captured by the camera, and FIG.
Is the luminance (or its change rate, etc.) in the figure (a)
It is the figure which showed the high pixel of a black dot.

As shown in FIG. 1A, a camera image 1 shows a road 3 extending in the infinity direction of a horizon 2, a shoulder line 4 is drawn on both sides of the road 3, and a center line 5 is drawn in the center. Is drawn. Here, the shoulder line 4 and the center line 5 of the road 3 have higher brightness than other parts,
Therefore, in the same figure (b), the dots 4 ', 5'on these parts
Will appear continuously. Such a camera image 1
In order to recognize the traveling direction and the curved shape of the road 3, the approximate straight lines L ₁ , L ₂ , L _{3 of the} curve connecting the dots 4 ′ in FIG.

Conventionally, as a method for obtaining such an approximate straight line L,
A technique called Hough transform is known (for example, US Pat. No. 3,069,654). This is the 16th
This will be described with reference to FIGS. As shown in Figure No. 16 (a), when x-y coordinate system the target point _{P to (x} p, _{y p)} in the original image shown there, linearly l _(l a through this point P, l _(b, etc.) can be drawn infinitely. Then, this straight line _l a, _{l b,} perpendicular to the origin O ... to
For even a straight line passing through (0,0), a straight line _l a, _{l b,} ...
You can draw one for each. Here, the origin O
Regarding a straight line passing through (0, 0), the length up to the straight line 1 (l _a , l _b, etc.) is ρ (ρ _a , ρ _b, etc.), and the angle formed with the x axis is θ (θ _a , θ _b, etc.). ), The above ρ and θ of the straight line passing through the origin are expressed as a sine curve (sine curve), that is, a Hough curve as shown in FIG. Here, the origin O (0, 0) and the processing target point P
The distance ρ _max of (x _p , y _p ) is the longest among the above ρ _a , ρ _b , ...) Regarding this processing target point, and ρ _max = (x _p ² + y _p ² ) ^1/2 , and θ When = 0, ρ ₀ = x _p .

Next, as shown in FIG. 17A, three points P ₁ lined up on the straight line L
When the Hough transform of FIG. 16 is applied to P ₃ , the above sine curve (Hough curve) of the point P ₁ becomes like the dotted line of FIG. 17 (b), and the sine curve of the point P ₂ of FIG. It becomes like the one-dot chain line of (b), and the sine curve about the point P ₃ becomes like the two-dot chain line of the same figure (b). Here, the peaks (ρ ₁ , θ ₁ ), (ρ ₂ , θ ₂ ) and (ρ ₃ , θ ₃ ) of the sine curve of FIG.
0) and the distance ρ ₁ ~ρ ₃ between points _{P 1, P 2, P 3} , x
It corresponds to the angles θ _{1 to} θ ₃ formed with the axis.

Focusing on the point where three Hough curves (sine curves) intersect in FIG. 17 (b), the coordinates are (ρ _t , θ _t ), which is the straight line L in FIG. 17 (a). Ρ _t , θ _{t of a} straight line passing through the origin O (0,0) orthogonal to
Is equal to. Therefore, if the intersection point of such a sine curve is obtained, an approximate straight line of a curve between dots (black dots) drawn in the xy orthogonal coordinate system of the original image (however, in FIG. 17, this curve and the approximate straight line are Match)
Can be asked.

This will be described with reference to FIG. 18. First, in FIG. 18A, a large number of dots (processing target points) to be Hough-converted exist on the xy coordinate plane (original image plane), and these dots are arranged on a curve. And Here, in the figure (a), three approximate straight lines L ₁ , L ₂ , and L ₃ are shown as the curves connecting the dots.
Can be drawn. Therefore, for all of these dots, conversion into a sine curve as shown in FIG.
When the (conversion) is executed, the intersections of the sine curve as shown in FIG. 16 (b) are obtained centering on three points. The coordinates of this crossing point are (ρ _ta , θ _t1 ), (ρ _t2 , θ _t2 ) and (ρ _t3 , θ _t3 ) shown in FIG. 18 (a).
Therefore, when H is represented as the appearance frequency of the crossing points in the coordinate system of ρ, θ, H, it becomes as shown in FIG. Therefore, the approximate straight lines L _{1 to} L ₃ of the curves corresponding to the shoulder line 4 of the road 3 as shown in FIG.
It can be obtained by the values of ρ and θ at the peak of H (frequency of appearance of intersections) in FIG. 18 (b).

[Problems to be Solved by the Invention]

However, the method of Hough transformation as described above is
It was not easy to apply to high-speed and real-time image processing. This is because the coordinate value (x _p , y) of the processing target point P in the original image given as data in FIG.
_p ), in order to obtain the Hough curve (sine curve), the distance from the origin to the straight line 1 is to be obtained. ρ = x _p · sin θ + y _p · cos θ (1) For example, when θ is divided into 512, trigonometric function calculation must be executed 1024 times, multiplication must be executed 1024 times, and addition must be executed 512 times. If the original image to be calculated is composed of, for example, 512 × 512 pixels, the total number of calculations will be extremely large, and if it is processed by an ordinary processor, the processing time will be extremely long.

Of course, it is also possible to store the values of sin θ and cos θ required in the above equation (1) in a ROM or the like to shorten the time required for calculation (for example, “real time Ho
"ugh conversion processor", National Conference of Information Systems Division, IEICE, No. 60 92 or "Hough conversion hardware using ROM" 1987 IEICE 70th anniversary general national conference, No. 158
7). However, even if the data of the trigonometric function is stored in ROM in the former case, the number of multiplications in the calculation of the equation (1) remains the same as before, and considering that the multiplication time is considerably longer than the addition time, the fundamental It cannot be a solution.

On the other hand, considering the latter document “Hough conversion hardware using ROM” described above from another point of view, here, the signal processing as a whole is performed by parallelizing the operation units that perform the operation of the above formula (1). We are trying to speed up. However, _{x p} · sinθ In this way, _{y p} · cos
A memory table (ROM) for obtaining θ is required for the number of arithmetic units connected in parallel, which results in an extremely large scale system in terms of hardware. Also, LS
Not suitable for I conversion. A method of converting the ROM into the RAM can be considered, but this has a problem in terms of integration.

Therefore, it is almost impossible to control a vehicle traveling at high speed in real time based on image data, or to recognize an observed object moving at high speed in real time based on image data. In addition, when attempting to increase the speed by parallelizing the arithmetic units, it is inevitable to increase the size of the hardware.

Therefore, it is an object of the present invention to provide an image processing apparatus capable of executing processing of image data at high speed in real time and also reducing the size of hardware.

[Means for Solving the Problems]

An image processing apparatus according to the present invention is an image processing apparatus that classifies and extracts feature points of an original image from a plurality of processing target points on the original image captured by an image capturing unit, and includes the following elements. That is, DDA (Digital Diffe
digital differential analysis) and a DDA operation means configured by connecting a plurality of operation elements in series, and this DD
Based on the storage means for storing the calculation result of the A calculation means in correspondence with the DDA calculation element and the stored contents of this storage means,
Means for extracting feature points of the original image.

The image processing apparatus according to the present invention is an image processing apparatus that derives an approximate straight line of a curve connecting a plurality of processing target points on the original image captured by the image capturing means, and includes the following elements. That is, the coordinates of one point on the circumference of the approximate circle drawn in the α-β Cartesian coordinate system is (α _i , β _i ), and the coordinates (α _{i + 1} , β _{i + 1} of the next point on the circumference are set. ), Where i is a positive integer, α _{i + 1} = f _α (α _i , β _i , ε) β _{i + 1} = f _β (α _i , β _i , Ε) of the rotational motion recurrence formula for each predetermined rotation angle in a sequential pipeline method, and at least the value of β _i among the results sequentially calculated by the DDA calculation unit It is characterized by comprising a storage means for storing and an approximate straight line deriving means for deriving an approximate straight line from the intersection of the Hough curves for each of the plurality of processing target points obtained based on the stored contents of the storage means.

[Operation] According to the configuration of the present invention, an arithmetic unit can be easily formed by simply connecting in series DDA arithmetic circuits (arithmetic elements) having the same configuration, and it is not necessary to refer to a memory table or the like when performing arithmetic operations. The configuration is remarkably simple and compact. Further, by configuring the arithmetic circuit so as to execute the rotational motion recurrence formula in the pipeline system, it becomes possible to speed up the calculation.

〔Example〕

Hereinafter, based on FIGS. 1 to 14 of the accompanying drawings,
An example of the present invention will be described. In the description of the drawings, the same elements will be denoted by the same reference symbols, without redundant description.

FIG. 1 is a block diagram showing the overall configuration of the image processing apparatus according to the embodiment. In FIG. 1, a camera 11 captures an original image by picking up an object to be processed (for example, a road or a high-speed moving object), and this image signal is digitized by a signal input unit 12 and sent to an edge detection unit 13. . The edge detection unit 13 extracts the edge of the image signal as the edged data having a shade, as will be described later.
It is sent to the multi-value quantization memory 14 as x512 pixel signals (edged pixel signals). The multivalued memory 14 stores edging data for each pixel, and the edging data is sent to the D / A conversion unit 15 every time scanning of one screen is completed and given to the CRT display 16 as an analog signal.
Therefore, this edged data is displayed on the CRT display 16
Is displayed.

On the other hand, the edged pixel signal output from the edge detection unit 13 is given to the pre-processing unit 17, and the edged pixel signal subjected to the pre-processing as described in detail later is performed by the DDA calculation means (hereinafter referred to as the DDA calculation unit). ) 18. DDA operation unit 18 of n DDA computing elements is configured to have a (hereinafter, the DDA operation of _circuit) 18 0 _{~18 n-1,} which are connected in series with each other. Then, the DDA operation unit 1
The output side of 8 has a neighborhood filter 19 and a sorting unit 20.
Are connected, whereby the neighborhood filtering process and the sorting process (detailed later) are performed. In addition, the above circuit elements are connected to the C via the VMEbus 21.
It is connected to the PU 22 to control the signal processing operation and synchronize the processing timing. In addition, the preprocessing unit 17, DD
The A arithmetic unit 18 and the neighborhood filter 19 are the VME bus 23.
Are connected to each other via a control unit for synchronous control of the transfer of the DDA operation result and the transfer of the grayscale value data.

Next, a detailed configuration of a main part of the image processing apparatus shown in FIG. 1 will be described.

FIG. 2 is a block diagram thereof, and the preprocessing unit 17 and DD in FIG.
It corresponds to the A calculator 18 and the neighborhood filter 19.
As shown in the figure, the pre-processing unit 17 uses a FIFO (First-In First-
Out) board 17 '. FIFO 17 'is the coordinate values _(X p, _{Y p)} in the X-Y plane of the target point and inputs as an address signal, and inputs the edging has been gradation value data _{D I} as a data signal. Then, as will be described later, this FIFO 17 'is converted from the XY coordinate to x-
Coordinate conversion to the y coordinate, window setting, and threshold processing are performed, and the results are sequentially output according to the FIFO method.

The 1 DDA computation circuit ₁₈ 0 _{~18 n-1} of the stage shown in FIG Each three flip-flops (F / F) 31,32,3
3 and the F / F 31 has address signals α _{0 to} α _n−1 , β.
_{0 to} β _n-1 are respectively temporarily stored, the F / F 32 temporarily stores the gray value data D _I , respectively, and the F / F 33
Is the histogram data D _{M0 to} D _M read from each of the RAMs 34 (RAM _{0 to} RAM _n-1 ) provided as recording means for each DDA arithmetic circuit 18 ₀ to 18 _n-1.
Store _{M (n-1)} temporarily. DDA37 (DDA _0- D
DA _n-1 ) is for calculating the rotational motion recurrence formula described later for each rotation angle. The address signals α _i , β
_i is input and address signals α _{i + 1} and β _{i + 1} are output. The DDA 35 (ADD _{0 to} ADD _n-1 ) which is an adder is FI
The gradation value data D _I from the FO 17 'and the histogram data D _{M0 to} D _{M (n-1)} from the RAM 34 are respectively added, and the output is temporarily stored in the buffer 36 and then stored in the RAM 36. _{0 to} RAM _n-1 . The timing controller 25 controls the timing of signal processing in these circuit elements and outputs timing pulses φ _{a to} φ _e . Then, it is connected to a command / status interface (I / F) not shown.

Next, an outline of the overall operation of the image processing apparatus shown in FIGS. 1 and 2 will be described with reference to FIG.

FIG. 3 is a flowchart explaining this. First,
A pixel signal for each processing target point on the original image captured by the camera 11 is input via the signal input unit 12 (step 10
2) The edges are detected by the edge detector 13 (step 104), and the edged data is input to the preprocessor 17 (step 106). The processes of steps 102 to 106 described above are repeated each time a pixel signal is input, and the results (edged data) are sequentially sent to the signal pre-processing unit 17 as digital data.

The preprocessing unit 17 performs a predetermined (described later) preprocessing (step 10).
8) is executed and the processed data is processed by the DDA operation unit 18
(Step 110). This pre-processing is also sequentially repeated each time the edged data is given.

Next, the calculation of the rotational motion recurrence formula for obtaining the Hough curve (sine curve) is executed by the DDA calculation means (calculated by the pipeline system) as described later (step 112). In the calculation in the DDA calculation unit 18, all the processes other than the pixels which are excluded from the window signals or those smaller than the threshold value by the preprocessing unit 17 out of the pixel signals of one screen ((original image plane) to be processed are completed. (Step 114), and when completed, the approximation straight line deriving means executes the filtering process (Step 116) and the sorting process (118), which will be described later, with respect to the intersection of the Hough curve by the neighborhood filter 19 and the sorting unit 20, and finally. As a result, an approximate straight line of a curve connecting the processing target points on the original image is obtained.

Next, the method of edge detection and the edged data in the edge detector 13 will be described with reference to FIG.

The original image captured by the camera 11 is now shown in FIG. 4 (a).
When the line indicated by reference numeral 8 in the figure is taken out at the x'coordinate, the luminance S is shown in analog form in FIG. That is, road 3
The outer side of the road has low brightness, and the road 3 and the shoulder have low brightness, but the road shoulder line 4 has very high brightness. Here, the luminance distribution as shown in FIG. 4 (b) is recognized as digital data of 256 gradations in the embodiment, but in order to accurately recognize the shape of the road, such luminance itself cannot be recognized. Understanding the distribution is not enough.

Therefore, when the luminance S of the pixel signal obtained through the signal input unit 12 is differentiated (dS / dx ') with respect to the coordinate x'and grasped as a change rate of the luminance, the edge is clear as shown in FIG. 4 (c). When the absolute value | dS / dx ′ | is shown, it becomes as shown in FIG. 7D, and the edged data (digital data) for clearly recognizing the edge of the road shoulder line 4 is obtained by the edge detector 13. Is obtained by This edge detector 13
The edging data from 1 to 3 is subjected to a predetermined preprocessing by the preprocessing unit 17 in the next step.

FIG. 5 is a flow chart for explaining the preprocessing in the preprocessing unit 17 (FIFO 17 ').

First, the edged data obtained as shown in FIG. 4 is input from the edge detection unit 13 to the preprocessing unit 17 (step 122), and it is determined whether or not this is within a preset window. (Step 124). This window is set as indicated by reference numeral 9 in FIG. 4 (a), for example. Here, whether or not the edged data inside the window 9 can be determined by the coordinate value on the XY coordinate plane of the data, and the following step 126 is executed only for the edged data in the window 9. It

In step 126, whether or not the edging data in the window 9 is equal to or higher than a predetermined threshold value (threshold level) is digitally determined using, for example, a look-up table (LUT) attached to the FIFO 17 '. That is, as shown in FIG. 6, when the LUT is not provided, the input data and the output data of the FIFO 17 'have a one-to-one correspondence (shown in FIG. 6A), but the threshold level is set by using the LUT. For example, when set to I _th , the output data becomes 0 (zero) when the input data is less than or equal to I _th . When the edged data is grasped at 256 gradations, the threshold level I _th can be set arbitrarily between 0 and 255. If this threshold value is shown in an analog manner, for example, it is set as shown by the dotted line in FIG. 4 (d), so that the data after the processing in step 126 is mainly the shoulder line 4 and the center line in the original image. 5
Data (digital data) corresponding to. For this reason, since the only data that should be signal-processed later is the main data (for example, the data corresponding to the shoulder and center lines of the road), it will not be affected by noise components and the overall processing speed will be reduced. Can speed up.

Next, in step 128, coordinate conversion is performed. That is, the XY coordinates shown in FIG. 4 (a) are converted into the xy coordinates. Thus, the coordinates of the target point in the original image _(X p, _{Y p)} are converted into coordinates _(x p, _{y p)} in the x-y coordinate system. By the above processing, Ho
The preprocessing for performing the hugh conversion ends.

The order of steps 124 to 128 in FIG. 5 may be different. For example, the coordinate conversion in step 128 may be performed first, but considering the time required for data processing, it is considered most preferable to perform it in the order shown in FIG.

Next, application of the Hough transform in the present embodiment will be specifically described with reference to FIGS. 7 and 8.

Hou for the point P (x _p , y _p ) shown in FIG.
When the gh curve (sine curve) is obtained, it becomes as shown in FIG. 11C, as already described in FIG. By the way, it is derived from the trigonometric theorem that such a locus of a sine curve is replaced by a locus of circular motion as shown in FIG. In other words, the Hough transformation of the point P (x _p , y _p ) in FIG. 7A to obtain the Hough curve in FIG. 7C is performed by the circular motion shown in FIG. It is equivalent to obtaining the locus of the circumference. Here, the circle R in the figure (b) has a radius R of R = ρ _max = (x _p ² + y _p ² ) ^1/2 (2), and the circular motion is represented by the point P (x _p, point Q (alpha ₀ in the diagram corresponding theta = 0 ° in _{y p) (b), β} 0 When starting from) its initial value _{θ d θ d = π / 2} -θ max where , Tan θ _max = x _p / y _p (3).

The present inventor pays attention to such a fact and applies the recurrence formula of the circular motion when drawing the circle in FIG.
We have found a method that can easily perform the Hough transform of the point P (x _p , y _p ) of FIG. Here, according to the recurrence formula of the circular motion described above, the coordinates (α _{i + 1} ) of a point which is advanced by one rotation angle ε from one point represented by the coordinates (α _i , β _i ) in the α-β Cartesian coordinate system. , Β _{i + 1} ) is α _{i + 1} = f _α (α _i , β _i , ε) β _{i + 1} = f _β (α _i , β _i , ε) when i is a positive integer (4) is required.

As specific contents of the equation (4), several DDAs have been known in the past. For example, the rotation angle ε is set as ε = 2 ^−m (rad) (where m = 0, 1, 2, ...). Then, there is a case where α _{i + 1} = α _i −2 ^−m β _i β _{i + 1} = 2 ^−m α _{i + 1} + β _i (5). In addition, the present inventors have found that the calculation is more accurate and easier to calculate. Α _{i + 1} = α _i (1-2 ^−2m−1 ) −2 ^−m β _i β _{i + 1} = 2 ^{− _{m α i + β i (1-2}} -2m-1) ... (7) or _{α i + 1 = α i (} 1-2 -2m-1) + β i (-2 -m + ε -3m / 6) β i You may use + ₁ = (alpha) _i (2- ^m + (epsilon) ^-3m / 6) + (beta) _i ( ^{1-2-2m -1} ) ... (8) etc.

Therefore, assuming that the recurrence formula of the above formula (7) is applied,
This calculation method will be specifically described prior to the description of the specific operation of the circuit in the figure.

FIG. 8 is a flowchart thereof. First, the data pre-processed by the FIFO 17 'according to FIG.
It is input to the A calculation unit 18 (step 132), and the position Q (corresponding to the angle θ = 0 ° (that is, the angle at which ρ = x _p ) at the processing target point P (x _p , y _p ) in FIG. 7 is obtained. α ₀ ,
Start circular motion from β ₀ ). At this time, the FIFO
(Α ₀ , β ₀ ) from 17 ′ is α ₀ = y _p , β ₀ = x _p (9). Here, by setting the starting position of the circular motion as described above, the initial value for the recurrence formula calculation becomes substantially unnecessary.

Next, after storing the value of β ₀ in RAM ₀ as an address, α ₁ and β ₁ are obtained by the equation (7). This can be obtained from the output of DDA ₀ by substituting α ₀ and β ₀ obtained by the equation (9) into the equation (7) (step 13
4), the results (β ₁ , β ₂ , β ₃ , ...) Are sequentially R after each calculation in DDA ₁ , DDA ₂ , DDA ₃ ,.
It is stored as an address in AM ₁ , RAM ₂ , RAM _3, ... (Step 138). On the other hand, this step 134
And step 138, the gray value data is accumulated. That is, the RAM 34 (R
Histogram data D _Mi and F read from AM _i ).
The gray value data from IFO17 'is added and this is added to RA.
It will again stored in M _i (step 136).

Then, this calculation is repeated for each rotation angle ε until the circuit makes one round (step 140).
Hough curves for one processing target point are the values of β ₀ , β ₁ , β ₂ , β ₃ , ... Stored by the above and θ ₀ ,
Not only is it obtained from the values of θ ₁ , θ _2, ... (Rotation angle ε), but also the result of weighting (D _M0 , D _M1 ,
... D _{M (n-1)} ) is also required. When the processing shown in FIG. 8 is executed for all the processing target points on the original image, a plurality of Hough curves weighted by the grayscale value data will be ρ.
It will be obtained in the −θ coordinate system, and these will have intersections as shown in FIG. 17 (b).

Next, the operation shown in the flowchart of FIG. 9 will be described more specifically with reference to FIG.

First, for the data input in step 132 of FIG. 8, a ready signal is input from the FIFO 17 'of FIG. 2 to the timing controller 25, and then a read strobe signal is input from the timing controller 25 to the FIFO1.
7 ', the coordinate value (x _p ,
address signal α ₀ corresponding to the y _p), the β ₀ FIFO1
This is performed by inputting from 7'to the F / F 31, and also inputting the grayscale value data D _I of the processing target point P into the F / F 32. Here, the address and data are input to the F / Fs 31 and 32 in synchronization with the timing pulse φ _a from the timing controller 25. Then, in synchronization with the rising or falling of the timing pulse φ _a , the address signals α ₀ and β ₀ of the F / F 31 are the first DD.
It is input to A ₀ (37).

In this DDA ₀ , the processing of step 134 in FIG. 8 is performed. That is, the calculation of the recurrence formula according to the above formula (7) is executed, and the calculation result (address signals α ₁ , β ₁ ) is sent to the next DDA ₁ (not shown). put it here,
In the above recurrence formula (7), calculation of trigonometric functions and multiplication are basically not included, and the memory table (R
Since it is not necessary to refer to (OM), the operation can be performed easily and quickly. And, these have sufficient accuracy (small error) in performing the circular movement.

The address signal β ₀ stored in the F / F 31 is a RAM
₀ (34), and the histogram data D _M0 stored in RAM ₀ is read by this. That is, the rotation angle θ is stored in the RAM ₀ with β ₀ as an address.
Histogram data D _M0 relating to another processing target point corresponding to ₀ (θ ′ = 0) is stored in advance (by calculation of the preceding ADD ₀ ), and therefore the address signal β ₀
Is given to the RAM ₀ from the F / F 31, the histogram data D _M0 is sent from the RAM ₀ to the F / F 33 in synchronization with the timing pulse φ _b .

Next, the histogram data D _M0 is sent from the F / F 33 to the ADD ₀ (35) in synchronization with the timing pulse φ _c from the timing controller 25, and the ADD ₀ is the calculation target from the F / F 32. Target point (x
_p, gradation value data _{D I} of _{y p)} is given. Therefore, in ADD ₀ , the histogram data D _M0 corresponding to the rotation angle θ ₀ and the address β ₀ accumulated in the RAM ₀ up to that point and the processing target point (x _p ,
y _p ) rotation angle θ ₀ and grayscale value data D _I corresponding to address β ₀ are added (step 13 in FIG. 8).
6). Then, this addition result (D _M0 ′ = D _M0 + D _I ) is temporarily held in the buffer 36, and then sent to the RAM ₀ in synchronization with the timing pulse φ _d , and according to step 138 in FIG. Storage will be done for address β _{0 of} RAM ₀ corresponding to θ ₀ .

The above-described 1-cycle processing is performed by the DDA operation circuit 18 _i (i
= 1, 2, ... N-1) is shown in FIG.

First, the address signals (initial values) α ₀ and β ₀ corresponding to the coordinate values (x _p , y _p ) of the processing target point are changed to α ₀ , β ₀ → α ₁ ,
_{β 1 → α 2, β 2} → ... α i, β i are sequentially addressed signal alpha _i as a result of the calculation, and beta _i, gradation value data _{D I} of the target point _(x p, _{y p)} is , F / F respectively
Input from 31 and 32 and retained (step 20
2), the address signals α _i and β _i from the F / F 31 are DDA
After sent to _i, the address signal alpha _i in step 204, the operation of the recurrence formulas based on beta _i, is executed in the DDA _i. Then, the resulting address signal α
_{i + 1} and β _{i + 1} are synchronized after the end of the processing of one cycle,
The data is sent to the F / F 31 provided before the DDA _{i + 1 in} the next DDA operation circuit 18 _{i + 1} .

On the other hand, the reading of the histogram data D _Mi based on the address signal β _i is executed in step 206. This step 206 is performed by applying the address signal β _i from the F / F 31 to the RAM _i in FIG. 2 and storing the histogram data D _Mi of the address β _{i in} the F / F 33. Then, in step 208, the histogram data D _Mi
The grayscale value data D _I of is added. This step 20
8 is executed by ADD _i in FIG. After that, the histogram data added in step 208 D _Mi ′ = D _Mi
+ G _I is written to the address β ₀ of RAM _i in step 210.

To explain this accumulation of histogram data in more detail, refer to FIG.

Figure 10 shows the concept of the histogram memory by the RAM34 of FIG. 2, as shown, n-number of _RAM 0 ~
It has a region of RAM _n−1 , and these regions respectively correspond to the rotation angles θ _{0 to} θ _n−1 of the recurrence formula calculation. And each RA
The M area has an address β (= ρ) of +511 to 0-512
16-bit histogram data can be stored in each address. Therefore, in DDA _i , α _{i + 1} and β corresponding to the rotation angle θ _{i + 1} are calculated by the above equation (7).
_{When i + 1} is calculated from the address signals α _i and β _i , the address signal β _i is given to the RAM _i and the histogram data D _{M (i) of the} address β _i is read. Then, the gray level data D _I of the processing target point is added, and the histogram data (D _{M (i)} , D _I ) is again written to the address β _{i of the} RAM _i .

As described above, the calculation of the recurrence formula shown in the formula (7) is performed by the pipeline method by successively passing the address signals α _i and β _i . Then, during the calculation from α _i , β _i to α _{i + 1} , β _{i + 1} , the histogram data D _Mi is accumulated (accumulated) by the grayscale value data D _I.
The time required to process the entire cycle can be shortened.

This one-cycle processing is simultaneously performed in parallel by the DDA arithmetic circuits 18 ₀ to 18 _n−1 that form the DDA arithmetic unit 18. That is, as shown in FIG. 11 (a), the FIFO 17 '
When data of ", empty ,, empty, empty ,, empty" is input from, it becomes as shown in the figure (b) in the first cycle and becomes as shown in the figure (c) in the second cycle. In the 3rd cycle, it becomes like (d) in the figure.
The same processing is performed thereafter, and the result becomes as shown in FIG. Here, (α ₀₁ ,
β ₀₁ ) to (α ₀₄ , β ₀₄ ) are address signals corresponding to the coordinate values (x _p1 , y _p1 ) to (x _p4 , y _p4 ) of the processing target points P _{1 to} P ₄ , respectively, and D _I1 to. D _I4 is the processing target point P ₁
It is gray value data in each of P ₄ to P ₄ . Also,
Θ _{0 to} θ _n-1 in FIGS. 2B to 2E are rotation angles from the processing target point (θ ₀ is the processing target point itself), and are respectively stored in RAM _{0 to} RAM _n-1 in FIG. Correspond.

Next, the neighborhood filtering after the Hough transform is completed will be described.

Now, suppose that the intersection of the Hough curve is represented by the ρ-θ plane as shown in FIG. 12 (a). Note that FIG. 10A shows a histogram H in which the intersection point appearing in each unit of the ρ-θ plane is weighted by the grayscale value data (brightness change ratio) of the pixel (processing target point) in the original image. The contours are represented by contour lines for the sake of clarity, and do not necessarily match the histogram according to the present invention.

Here, it is assumed that the histogram is high at the point p1 in the same figure (a), and the histogram is also high at the other points p2 and p3. Here, focusing on the vicinity of the point p1, it can be seen that high points of the histogram also occur at the points p4, p5, and the like. However, what is particularly important in image processing is to find points p1 to p3 that are separated from each other. For example, point p1 is the shoulder line of the road, point p2 is the center line, and point p3 is the shoulder of the curved road ahead. Corresponds to the line. On the other hand, points p4, p5, etc. in the vicinity of the maximum histogram point p1 often correspond to partial bending of the road shoulder line, and mainly correspond to noise components in image processing.

Therefore, the influence of such a noise component is reduced by, for example, 8-neighbor filtering. That is, an 8-neighboring filter as shown in FIG. 12B is prepared, and histograms at intersections of Hough curves are compared with each other for the areas F _{1 to} F ₉ . Then, the area _{F 5} of the center, when _{the F 5> F 1 ~F 4,} F 6 ~F 9 is satisfied, the data to be detected data in this area _{F 5.} Specifically, for example, when one unit (element area) pixel on the ρ-θ plane is assigned to each of F _{1 to} F ₉ , the number of histograms at intersections is F ₁ = 6, F ₂ = 8, When F ₃ = 4, F ₄ = 2, F ₅ = 14, F ₆ = 10, F ₇ = 7, F ₈ = 9, F ₉ = 8, then F ₅ > F _{1 to} F ₄ , F _{Since 6 to} F ₉ are established, the intersection of F _{5 is set as} the data to be detected. On the other hand, F ₁ = 8, F ₂ = 4, F ₃ = 3, F ₄ = 14, F ₅ = 10, F ₆ = 7, F ₇ = 9, F ₈ = 8, and F ₉ = 2. In this case, since F ₅ <F ₄ , the area of F ₅ is not the data to be detected.

By performing the above filtering process,
The high points p2 and p of the second and third histograms are not affected by the presence of the points p4 and p5 in FIG.
3 can be detected. That is, if the above filtering is not performed, the high histogram points next to the first high histogram point p1 are points p4 and p5, and the points p2 and p3 to be obtained as the second and third high histogram points are These are the 4th and 5th high histogram points, which makes subsequent signal processing extremely difficult.

Next, the sorting process shown as step 118 in FIG. 3 will be described in detail with reference to FIG.

FIG. 13 is a flowchart thereof. First of all, for sorting processing, a plurality of input memories (4 for simplification of description) are input memories (transfer memories) M _I1.
~ M _I4 and comparison memories (result memories) M _{M1 to} M _M4 are prepared and initialized (step 152). Next, data is input to the input memory M _I1 (step 154). If this input data is determined to be present in step 156, steps 158 to 184 are executed, and if not, steps 190 to 199 are executed. I will do it. Here, the processing of steps 190, 196, and 199 is performed in step 15
This is the same as the processing of steps 8 and 160, and steps 192 and 19
8 is the same as the processing of steps 162 to 168, and the processing of step 194 is steps 170 to 1
This is the same as the processing of 76.

Each step 158,162,170,178 and compares the contents of the comparison memory _{M M} and the corresponding input memory _{M I,} when the _{M I} ≦ _{M M} then transfers the contents of the input memory _{M I} (step 164 , 172, 180).
On the other hand, when M _I > M _M , the contents of the comparison memory M _M are transferred to the next input memory M _I (steps 166, 1).
74, 182) both put the contents of the input memory M _I into the corresponding comparison memory M _M (steps 168, 176, 1).
84). Then, finally, the memories M _{M1 to} M _M4 hold four pieces of input data in descending order.

This is specifically shown in FIG. First,
Four memories M _{I1 to} M _I4 are prepared as an input memory, and four memories M _{M1 to} M _M4 are prepared as a comparison memory. The input data is "5, 7," as shown in FIG.
2, 8, 4, 9, 3, 3, 1, 6, 8 ″. Then, the comparison memories M _{M1 to} M _M1 are processed by an operation after initialization as shown in FIG. _The data stored in _M4 changes as shown by the arrow in FIG. 7C, and finally the contents of the comparison memory M _M1 = 9 〃 M _M2 = 8 〃 M _M3 = 8 〃 M _M4 = 7 are stored. The sorting process may be executed by software, and by executing the series of processes described above, all steps of signal processing by the image processing apparatus according to the present invention are completed. Then, the approximate straight line of the curve connecting the processing target points of the original image is obtained by the above values of ρ and θ.

The present invention is not limited to the above embodiments, but various modifications can be made.

For example, the setting of the window shown in step 124 in FIG. 5 may be performed for a plurality of windows, and when the windows overlap, one of them may be preferentially processed. In addition, the window setting itself is not always necessary.
The out conversion may be performed. However, in this case,
Since the peripheral area of the original image indicated by the dotted line Q in FIG. 4 (a) contains many noise components, this portion must be removed in advance when performing accurate image processing.

When obtaining the histogram of the intersections of the Hough curve, by superimposing the binarized data instead of the grayscale value data on the change rate of the luminance (the value of the differentiated edging data), only the concentration of the intersections is histogrammed. Can be understood as Further, the data corresponding to the brightness may be digitally processed as the grayscale value data as it is, instead of being edged data by differentiation, and then the histogram of the intersection points of the Hough curve may be obtained.

The calculation of the rotational motion recurrence formula is not always performed on the entire circumference (1
Lap) is not essential, 1/2 lap, 1
It may be / 4 round or 1/8 round. For example, 1 /
If the calculation is performed by arranging the DDAs in series, which only executes the operation of four rounds for 0 ≦ θ <π / 2 and π ≦ θ <3π / 2, the other circles (π / 2 ≦ θ <π , 3π / 2 ≦ θ <
The value on 2π) can be immediately obtained from these.
Further, it is not always necessary that the rotation angles are the same, and it is not impossible to make them partially different.
Also, due to the nature of the straight line, 1/2 turn (0 ° to 180 °)
It may be a target of the out conversion.

〔The invention's effect〕

As described above in detail, according to the present invention, the D
The arithmetic unit can be easily formed by simply connecting the DA arithmetic circuits in series, and it is not necessary to refer to the memory table or the like in the arithmetic operation, so that the configuration is remarkably simple and compact. Further, by configuring the arithmetic circuit so as to execute the rotational driving recurrence formula by the pipeline method, not only the calculation speed can be increased, but also the initial stage for calculating the rotational motion recurrence formula can be achieved. This has the effect of eliminating the need for value calculation.

[Brief description of drawings]

FIG. 1 is a block diagram showing the overall configuration of an image processing apparatus according to an embodiment of the present invention, FIG. 2 is a block diagram showing the configuration of the main parts of FIG. 1, and FIG. FIG. 4 is a flowchart illustrating an example of an original image and edge detection of an input pixel signal, FIG. 5 is a flowchart illustrating preprocessing of edged data, and FIG. 6 is a lookup table. FIG. 7 is a diagram for explaining Hough transformation in the embodiment of the present invention, FIG. 8 is a flow chart showing calculation of recurrence formula of rotary motion in the embodiment, and FIG. 9 is a diagram for explaining processing of one cycle. FIG. 10 is a conceptual diagram of a histogram memory, FIG. 11 is a diagram illustrating pipeline processing in the embodiment, FIG. 12 is a diagram illustrating 8-neighbor filtering processing, and FIG. 13 is a flowchart illustrating sorting processing. Charts, Fig. 14 specifically explaining to FIG sorting process, FIG. FIG. 15 illustrating the recognition of the road, Figure 16 through Figure 18 the conventional Hough
It is a figure explaining a conversion. 1 ... Camera image, 2 ... Horizontal line, 3 ... Road, 4 ...
Shoulder line, 5 …… Center line, 11 …… Camera,
12 ... signal input section, 13 ... edge detection section, 14 ...
Multi-valued memory, 15 ... D / A converter, 16 ... CRT
Display, 17 ... Preprocessing unit, 17 '... FIF
O, 18 ... DDA calculation unit and histogram memory, 18
_{0 ~18 n-1} ...... DDA computing circuit and the histogram memory, 19 ...... vicinity filter, 20 ...... sorting unit,
21,23 ... VME bus, 22 ... CPU, 31,3
2, 33 ... Flip-flop (F / F), 34 ... R
AM _{0 to} RAM _n-1 (histogram memory), 35 ...
ADD _{0 to} ADD _n-1 (adder), 36 ... Buffer,
37 ... DDA _{0 to} DDA _n-1 (DDA arithmetic circuit).

Claims (9)

[Claims] 1. An image processing apparatus for classifying and extracting a characteristic point of an original image, which indicates each edge of an imaging target, from a plurality of processing target points on the original image captured by an imaging means, wherein Is a means for obtaining a Hough curve represented as a sine curve showing a group of straight lines passing through the processing target points for each of the processing target points by executing the Hough transformation by the DDA calculation element having the same configuration. A plurality of DDA operation elements are connected in series, and each DDA operation element is a DDA operation unit that calculates address information of each point for each predetermined angle on the Hough curve for one processing target point, and each DDA operation element. And a Hough curve intersecting at the point corresponding to the address information, for each address information obtained by the DDA operation element. It is a component of a straight line that approximates each edge of the imaging target on the image based on the storage means for storing the frequency information of each processing target point and the intersection information of each Hough curve corresponding to the frequency information of this storage means. An image processing apparatus, comprising: means for extracting a feature point on the original image from the processing target points. 2. An image processing apparatus for deriving a straight line which connects a plurality of processing target points on an original image captured by an image capturing means and which approximates each edge of the image capturing target on the image. By executing the Hough transform on the target point, an approximate circle equivalent to a Hough curve represented as a sine curve indicating a group of straight lines passing through the target point, which is drawn in the α-β orthogonal coordinate system. When the coordinates of one point on the circumference of the approximate circle are (α _i , β _i ) and the rotation angle to the coordinates (α _{i + 1} , β _{i + 1} ) of the next point on the circumference is ε (Where i is a positive integer), α _{i + 1} = f _α (α _i , β _i , ε) β _{i + 1} = f _β (α _i , β _i , ε) for each processing target point And a DDA calculating means for sequentially calculating a rotational motion recurrence formula for each predetermined rotation angle by a pipeline method. Of each result more are sequentially computed, as an address the value of at least the beta _i, a storage means for storing frequency information of each target point having a Hough curve intersects with the resulting coordinates, the storage means And an approximate straight line deriving means for deriving a straight line that approximates each edge of the imaging target on the image based on the intersection information of the Hough curves corresponding to the frequency information. 3. The DDA calculating means is configured by connecting in series a plurality of arithmetic circuits that respectively calculate the rotational motion recurrence formula for each one rotation angle. Image processing device. 4. The rotational motion recurrence formula defines the rotational angle as ε =
When 2- ^m , α _{i + 1} = α _i (1-2 ^-2m-1 ) -2 ^-m β _i β _{i + 1} = 2- ^m α _i + β _i (1-2 ^-2m-1) The image processing device according to claim 2, wherein 5. The image processing apparatus according to claim 2, wherein the storage means stores at least the value of β _i in association with the rotation angle. 6. The image processing apparatus according to claim 2, wherein the storage means stores gray value data corresponding to the luminance of the processing target point in the original image or its change rate. 7. The image processing apparatus according to claim 5, wherein the storage means stores the grayscale value data of the processing target point in the original image in association with the rotation angle. 8. The approximate straight line deriving means is the Hough.
The image processing apparatus according to claim 2, further comprising a neighborhood filter that performs neighborhood filtering processing on the data regarding the intersection of the curves. 9. The approximate straight line deriving means is the Hough.
7. The image processing apparatus according to claim 6, further comprising a neighborhood filter that superimposes the grayscale value data on the intersection point of the curve and performs neighborhood filtering processing.