JPH01236385A - Circular object recognizing method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] Regarding a method for recognizing a circular object using a two-dimensional wave equation, an object of the present invention is to provide a method for recognizing a circular object i: by providing a plurality of frame memories and increasing the calculation speed. Then, input an image of a circular object or a similar object to a calculation device as a two-dimensional gray value, have it solve a two-dimensional wave equation with the gray value as the initial value, and use the extreme value of the amplitude in the solution of the equation. In a circular object recognition method that confirms the center position of a circular object, it requires a small amount of memory (both two frame memories,
That is, a first frame memory and a second frame memory are provided, the first frame memory is made to hold the two-dimensional gray value of the image after a predetermined time, and the second frame memory is made to hold the time differential value of the two-dimensional gray value. and step 1
In step 2, write the two-dimensional grayscale value of the original image into the first frame memory and assign 0 to the second frame memory.
In step 3, find the Laplacian of the image held in the first frame memory, add this to the contents of the second frame memory, and write the result to the second frame memory.
Multiply the contents of the second frame memory by a predetermined number less than 1, add this value to the contents of the first frame memory, write the result to the first frame memory, and repeat steps 2 and 3 above to obtain the predetermined value. The center position of the circular object is determined from the x, y address of the first frame memory that is equal to or higher than the threshold, and the radius of the circular object is determined from the number of repetitions.

INDUSTRIAL APPLICATION FIELD The present invention relates to a circular object recognition method using a two-dimensional wave equation.

Circular shapes occupy a large proportion of the visual recognition objects in the mechanical industry. Most of the work done by lathes and milling machines is to form circles, and bolts and rivets are fastened to round holes. Furthermore, the terminal portions of printed boards widely used for mounting electronic components are often ring-shaped.

Since the terminals are formed using printed wiring, the position of each terminal is known, but it is inevitable that some misalignment will occur, so when performing automatic bonding, it is necessary to determine the center position of the terminals and ensure accurate bonding. It is desirable that the In production facilities that have robots installed, robots pick up parts one by one that are produced in upstream processes and place them on processing machines, or move them to conveyors for downstream processes. However, in this case as well, it is necessary to correctly recognize the position and shape of the parts.When recognizing a circular object, the views that need to be measured are the coordinates of the center position and radius of the circle.

Conventional technology Various methods for recognizing circular objects have been proposed, but most of the conventional methods extract the contour and calculate the center of gravity and circumference, so when the contour line is interrupted, it cannot be traced as a closed loop. , there was a drawback that the center of gravity and circumference could not be calculated. Techniques are known to fill in the gaps if they are minute, but this is often difficult if large parts are missing.

This drawback is particularly problematic when processing grayscale images using reflected light.

Therefore, the effectiveness of similar processing and macroscopic methods has been pointed out as a recognition method that is not affected by background, surface patterns, or noise. One example is a method in which skeletal lines are extracted by generating waves from around an image.

Using a similar idea, we compare the circumference of a circular object to waves on the water surface.
Japanese Patent Laid-Open No. 58-51387 discloses a figure recognition method for determining the center position by utilizing the fact that waves propagated from the outer periphery converge at the center after a certain period of time and form a peak.

In the figure recognition method disclosed in this publication, a wave equation is used to recognize a circular object, and the wave equation is used from the following viewpoints. For example, when a circular basin is filled with water and an impact is applied to the edge, waves generated from the surroundings will propagate toward the center, and will peak at the center after a predetermined period of time. Therefore, if we consider the area surrounding a circular object as a circular area on the water surface and simulate the movement of waves inside a calculator, a similar peak should occur. If the position of the peak is known, the center position of the circle can be found, and the radius can be determined from the time taken to reach the peak.

The strength of this recognition method is that multiple circles may overlap each other, even if some of the circles are missing. The reason why peaks occur is that waves that occur simultaneously on the circumference all strengthen each other in the same phase at the center point, but even if a part of the circle is missing, the remaining arc has sufficient length. Ba,
This is because there is no difference in the fact that the waves generated from there are in the same phase and strengthen each other. As for the patterns and noise on the surface, unless they are circular, the phase of the waves generated will be random and will not produce large peaks, and will be independent of the waves that are originally generated around the circumference and will not interfere with them.

Problems to be Solved by the Invention The figure recognition method described in the above-mentioned publication has the advantage that it is possible to accurately determine the center position and radius of a circular object without being interfered with by patterns or noise on the surface. However, there was a problem in that the calculation required time.

The present invention has been made in view of these points, and an object of the present invention is to provide a circular object recognition method in which a plurality of frame memories are provided to increase the calculation speed.

Means to solve problems FIG. 1 shows a flow chart of the principle of the present invention.

The present invention uses at least two frame memories. That is, a first frame memory 8 and a second frame memory V are provided, the first frame memory 8 is made to hold the two-dimensional gray scale value of the image after a predetermined time, and the second frame memory 8 is stored as a second frame memory IJV.
holds the time differential value of the two-dimensional gray value.

In step l, the two-dimensional grayscale value A (x, y) of the original image.

O) is written into the first frame memory A, 0 is substituted into the second frame memory (2), and a counter n indicating the number of approximations is set to 1. In step 2, the Laplacian ΔA of the image held in the first frame memory A is determined, and the result of adding this to the contents of the second frame memory V is written in the second frame memo IJV. Next, in step 3, the contents of the second frame memory v are multiplied by a predetermined number less than 1, for example 1/8, and this value is added to the contents of the first frame memory, and the result is written in the first frame memo UA.

In step 4, values of addresses x, y, and n in the first frame memory that are greater than a predetermined darkness value S are detected, and these values are written in the peak table. Counter n in step 5
The value of is incremented by one, and in step 6, n becomes R/
It is determined whether the number of pixels is 25 or more. Here, R is the maximum radius of the circle to be found, and it is assumed that the wave advances by 27 pixels in one approximation cycle. In the case of a negative determination in step 6, steps 2 to 5 are repeated, and in the case of an affirmative determination, this routine is ended.

Through this processing routine, the center position of the circular object is determined from the x and y addresses of the first frame memory A that are greater than or equal to a predetermined threshold value S, and the radius of the circular object is determined from the number of repetitions.

Function: In the present invention, the brightness of a grayscale image is expressed by coordinates x in the horizontal and vertical directions.
, y, and time t.

This is written as A (x, y, t), and the two-dimensional wave equation is defined as the initial value of one frame image A (X, '1. to) input at time to, where a is the speed of the wave. Try to solve. The boundary conditions are on the periphery of the image frame (
square) and always A (x, y, t) = 0. Physically, this is the same as the equation that describes the state of an elastic membrane fixed around the periphery of a square.

In order to convert equation (1) into a difference equation and solve it sequentially, a new variable ■(x, y, t) = 6t A(x, y, t) is introduced to form a first-order simultaneous equation.

That is, if Equation 1 is rewritten using V (x, y, t), it becomes as follows.

Knee V (x, y, t) = a”AA (X, '
/, t) at 82 a2 Δ” ax・+ 6.・ a, to (x, y, t) =V
(x, y, t)at...(2) When formula (2) is replaced with a difference approximation formula, it becomes as follows.

V(x, y, t+δt/2) = V(x, y, t-δt/2)+a'δtΔA(X, y
, t) A(x, y, t+δB= A(x, y, t) + δtV(x, y, t+δt/2
)...(3) The algorithm to solve equation (3) is given by Kagoshita.

Step l: V=0. A=A (0) Step 2
2 ■←V+a”δtΔA Step 3: A−A+δtV Step 4: Return to Step 2 The above-mentioned algorithm with a2δt=1.61-1/8 is the principle flowchart of the present invention shown in FIG. This operation can be effectively executed using a general-purpose locally parallel image processor such as that disclosed in Japanese Patent Application Laid-Open No. 62-137669.

Referring to the principle flowchart of FIG. 1, steps 2 and 3 mean performing calculations on the entire contents of each frame memory, and the time required for each step is one frame period, or about 33 ms. When repeating steps 2 and 3 is called one approximation cycle, the first frame memo IJA holds A (x, y, t+nΔt) at the time when the n-th approximation cycle has progressed.

In steps 2 and 3, it is necessary to perform calculations on the entire contents of the frame memory within one frame cycle, so a high-speed image processor is generally required to execute this processing routine. The peak table for step 4 is shown in Figure 2.
From this peak table, the coordinates x and y of the center of the circle and its radius can be easily determined.

Embodiment Although the flowchart in FIG. 1 illustrates the principle of the present invention, some types of image processors may not be able to execute the processing flow in FIG. For example, in step 2, the Laplacian ΔA is added to the data read from the second frame memory V and then written to the same frame memory V, but it is generally difficult to do this within one frame period. This is because it is necessary to switch between reading and writing the memory element within the sampling period. It is easier to control and to simplify the circuit if each frame memory is always in a read state or a write state within one frame period.

Further, depending on the processor, it may not be possible to apply the Laplacian to one frame memory and add it to another frame memory as in step 2 of FIG. In other words, it may only have a simple frame addition function. In order to execute the present invention on a processor having only such simple functions, the number of working memories may be increased and the processing flow shown in FIG. 3 may be implemented.

That is, in this embodiment, in addition to frame memory A and frame memory V, two work memories lJW, , W,
Add. In step 11, frame memo U
Two-dimensional grayscale values of the original image are written in A, and 0 is assigned to frame memory V.

Further, a counter n indicating the number of times of approximation is set to 1.

Next, the process proceeds to step 12, where the working frame memo +JW- is written into the Laplacian image Δ, and the content of the frame memory v is added to the data read out from the working frame memory W1 and written into the working frame memory W2.
The data read from the working frame memory W2 is written to the frame memory V.

In step 12, each of the above-mentioned calculations is performed sequentially, so a time period of three frames is required. Next, in step 13, the data read from the frame memo IJV is multiplied by 1/8 and written into the working frame memory W, and the data read from the working frame memory W1 and the data read from the frame memory A are added. At the same time, the data in the work frame memory W2 is written in the frame memory A.

In step 13, each calculation described above requires one frame period, so three frame periods are required in total. Step 12 performs the same calculation as step 2 in the flowchart of FIG. 1, and step 13 performs the same calculation as step 3 in FIG.

Next, the process proceeds to step 14, where the values of addresses x, y, and n of frame memory A that are equal to or greater than a predetermined value of 2 are written into a peak table as shown in FIG. Step 15
Now increment the counter n by 1 and proceed to step 16.
It is determined whether n is equal to or greater than R/2F pixels, and if the determination is negative, steps 12 to 15 are repeated, and if the determination is affirmative, this processing routine is ended. As mentioned above, in this embodiment, four frame memories are used,
The time required for one approximation is 6 frame periods.

By using more working memory, operations can also be performed in less time than the embodiment of FIG. FIG. 4 shows an embodiment of the invention using five frame memories.

In FIG. 4, first, in step 21, the frame memo 'I' is
The two-dimensional grayscale value of the original image is written in I Asye, , and 0 is assigned to the frame memory V e V @ fi. Further, a counter n indicating the number of times of approximation is set to 1.

In step 22, the frame memory A@ye,
, the Laplacian image ΔA @ v @. is written to the frame memory W, and the data read from the frame memory W and the data read from the frame memory V@V@11 are added to create a frame memo! j Vo
Write to dd.

In step 23, the frame memory V 5 d
The data read from d is multiplied by 1/8 and written to the frame memory V@V@n, and the data read from the frame memories V, V6 are added to the data read from the frame memories A s v e , , to create a frame. Write to memory A o a d. In steps 22 and 23, one frame period is required to perform each calculation, so two frame periods are required to execute each of steps 22 and 23. Step 22 executes the same calculation as step 2 in the flowchart of FIG.
3 executes an operation equivalent to step 3 in FIG.

Next, the process proceeds to step 24, where the frame memory Aodd
The values of addresses x, y, and n whose values are equal to or greater than a predetermined threshold value S are written into a peak table as shown in FIG. In steps 22 to 24, odd-numbered approximation cycles are executed.

In step 25, the counter n is incremented by one,
Proceeding to steps 26 to 28, even-numbered approximation cycles are executed. Step 26 ~ stave 28 odd e +, , e n of step 22 ~ stave 24
Exactly the same process is executed by replacing odd with even.

In step 29, the value of the counter n is further incremented by one, and then the process proceeds to step 30, where n is R/2-rT.
It is determined whether or not the number of pixels is greater than or equal to a pixel, and if the determination is negative, the processing from step 22 is repeatedly executed, and if the determination is affirmative, this processing routine is ended.

In this embodiment, since five frame memories are used, calculations can be executed in a period of four frames.

FIG. 5 shows a configuration example of an image processing processor suitable for executing the calculations of the present invention, and is particularly suitable for the calculation processing of the embodiment shown in FIG. In the figure, lOo~10.
is a frame memory, and five frame memories are provided. Each frame memory has a bidirectional bus buffer 12
It is connected to an 8-bit video bus 14 via an 8-bit video bus 14.

A spatial filter 16 includes a line buffer 18, a Laplacian processing section 20, and a scaling circuit 22. 24 is an adder circuit, and the adder circuit 24 and the spatial filter 16 are pipeline-coupled via an internal bus (as shown by the broken line). 26 is a conversion circuit that performs A/D conversion and D/A conversion.

Effects of the Invention Since the present invention is constructed as described in detail above, it has the advantage that circular objects can be recognized accurately and at high speed.

[Brief explanation of the drawing]

Fig. 1 is a flowchart of the principle of the present invention, Fig. 2 is a schematic diagram of a peak table, Fig. 3 is a flowchart of an embodiment of the invention, Fig. 4 is a flowchart of another embodiment of the invention, and Fig. 5 is a schematic diagram of a peak table. 1 is a schematic configuration diagram of an image processing processor applicable to the invention; FIG. 10°~104...Frame memory, 12...Bidirectional path buffer, 14...Video bus, 16...Spatial filter, 24
... Addition circuit. Main House θ Month's 7 Birds Process Flow Thousand Sade Diagram 1 Hiku Tefu '2 and Diagram 2 Sj Basi Row 0 Flow + Eid Diagram 3

Claims (1)

[Claims] An image of a circular object or a similar object is input as a two-dimensional gray value to an arithmetic unit, and a two-dimensional wave equation with the gray value as an initial value is solved, and the amplitude in the solution of the equation is calculated. In the circular object recognition method for confirming the center position of the circular object by the extreme value of at least two frame memories,
That is, a first frame memory and a second frame memory are provided, the first frame memory is made to hold the two-dimensional gray value of the image after a predetermined time, and the second frame memory is made to hold the time differential value of the two-dimensional gray value. In step 1, write the two-dimensional grayscale value of the original image into the first frame memory and assign 0 to the second frame memory, and in step 2, calculate the Laplacian of the image held in the first frame memory. , the result of adding this to the contents of the second frame memory is written to the second frame memory, and in step 3, the contents of the second frame memory are multiplied by a predetermined number less than 1, and this value is added to the contents of the first frame memory. The added result is written to the first frame memory, and the above steps 2 and 3 are repeated to find the center position of the circular object from the x and y addresses in the first frame memory that are above a predetermined threshold, and the center position of the circular object is determined from the number of repetitions. A circular object recognition method characterized by finding the radius of a circular object.