US 5,568,567 AGrant
Two-Dimensional Image Processing Method and Apparatus for Approximating Circular Arc Configuration of an Object
Issue Date:1996-10-22
•13 Claims
•4 Drawing Sheets
Abstract
Two-dimensional image data of an object is processed to inspect a circular arc configuration of the object. Initially, the two-dimensional image data is subjected to a data extraction process in which image edge points of the circular arc configuration of the object are extracted from the two-dimensional image data. The image edge points are then applied to a process to approximate the circular arc configuration of the object by defining a circle which minimizes a mean value of a fourth power error of the image edge points relative to the circle, the thus defined circle being used to approximate the circular arc configuration of the object.
Metadata
Assignee
- Matsushita Electric Industrial Co., Ltd.
Inventor
- Haruhiko Yokoyama
Application Information
Application Number:US 8241732
Filing Date:1992-01-22
Priority Date:1991-01-22
Art Unit:266
Classifications
IPC:
G06K 946
Field of Search:
38235636422;25;8;203;204;241376;384560
Patent Drawings (4 sheets)
Description
Background of the Invention
The present invention relates to a method and apparatus for measuring or inspecting a circular arc configuration of a product or part such as the circular arc configuration of a thread hole, and more particularly to a method for approximating the center position and radius of the circular arc configuration based on image information.
With reference to the drawings, two examples of conventional method for approximating a circular are configuration are is described below.
The conventional method includes the following three processes (A), (B) and (C).
Process (A):
A sequence of edge points is extracted from a two-dimensional image.
Process (B):
A point sequence is formed based on the edge points.
Process (C):
A circular-arc is approximated based on the point sequence. The circular-arc configuration of the product is detected according to the approximated circular arc.
The two examples 1 and 2 of conventional method which will be described below each include the above-described processes (A) and (B), but are different from each other with respect to process (C).
First, the process (A) for extracting edge points from the two-dimensional image is described. Normally, in measuring or inspecting the configuration of a specified portion of a product or part, there are abrupt changes in the density of the image thereof. The image density suddenly changes at the edge point. Therefore, the absolute value of the differentiated value of the image density is large at the edge point. Thus, the image is filtered by a differential filter so that a point at which the absolute value of the output is large is set as the edge point. A Laplacian filter is an example of a differential filter. FIG. 2 shows an example of an output, obtained by the use of the Laplacian filter, in which a center point having a value "8" is an edge point. In extracting ridges shown in FIG. 3 from a two-dimensional image, a result obtained by using the Laplacian filter is shown in FIG. 4. An edge point is required to satisfy two of the following four conditions.
X.gtoreq.X.sub.0 and X>X.sub.4
X.gtoreq.X.sub.1 and X>X.sub.5
X.gtoreq.X.sub.2 and X>X.sub.6
X.gtoreq.X.sub.3 and X>X.sub.7
The process (B) for forming a point sequence based on edge point is now described. In order to obtain a point sequence from the aggregation of edge points obtained in the process (A), adjacent edge points are connected with each other. In this case, short lines branching from the point sequence are deleted. Of long lines branching from the point sequence, only a point sequence consisting of a branch having a minimum curvature is selected and other branches are cut off to obtain a single point sequence having no branches. The curvature (C) is calculated as follows: A branch point shown in FIG. 5 is assumed as (P). Points spaced at a length (L) from the point (P) are supposed as Q.sub.1 and Q.sub.2. When the difference in the directional angle between a vector Q.sub.1 P and a vector PQ.sub.2 is supposed as .theta., the curvature (C) is found as follows:
The value of (L) is set to be smaller than the radius of a circumference which must be detected so that noise does not have a large inappropriate influence on calculations used for finding the curvature (C) because it is sensitive that the value is set to be too small. The resulting point sequence is expressed as follows:
The process (C) for approximating a circular arc from the point sequence of the process (B) and detecting the circular arc configuration based on the approximated circular arc will now be described. Since the two examples 1 and 2 differ with respect to process (C), the example 1 is first described below. FIG. 6 is an illustration showing the method for calculating a partial curvature C.sub.i+1 of the first example 1.
The partial curvature C.sub.i+1 of a curve formed by three points P.sub.i, P.sub.i+1 and P.sub.i+2 is expressed as follows:
where .theta..sub.i+1 is the difference in the directional angle between a vector (P.sub.i P.sub.i+1) and a vector (P.sub.i+1 P.sub.i+2), and d.sub.i+1 is the average of the length P.sub.i P.sub.i+1 and the length P.sub.i+1 P.sub.i+2.
The curvature C.sub.1 of the entire point sequence is expressed as follows: ##EQU1##
A decision is made according to the value of the variance of the partial curvature C.sub.i+1 with respect to the curvature C.sub.1 of the entire point sequence. If the variance value is smaller than a predetermined value, it is decided that the point sequence is a part of a circular arc and consequently, detected as the circular arc.
The process (C) of example 2 for approximating a circular arc from the point sequence of the process (B) and detecting the circular arc configuration based on the approximated circular arc will now be described. FIG. 7 is an illustration showing the method for calculating a partial curvature C.sub.i+s of the example 2.
According to the example 2, instead of calculating the partial curvature of a curve configured by the three continuous points as in the example 1, the partial curvature C.sub.i+s between two points spaced at (s) pieces of points apart is calculated. If the variance of the partial curvature C.sub.i+s with respect to the curvature C.sub.2 of the entire point sequence is smaller than a predetermined value, it is decided that the point sequence is a part of a circular arc and accordingly detected as the circular arc.
The partial curvature C.sub.i+s of the circular arc formed by three points P.sub.i, P.sub.i+s, and P.sub.i+2s of the point sequence is expressed by the following equation (5):
where .theta..sub.i+s is the difference in the directional angle between a vector [P.sub.i P.sub.i+s ] and a vector [P.sub.i+s P.sub.i+2s ] and d.sub.i+s is the average of the length P.sub.i P.sub.i+s and the length P.sub.i+s P.sub.i+2s.
The curvature C.sub.2 of the entire point sequence is expressed by the following equation (6). ##EQU2##
A decision is made according to the value of the variance of the partial curvature C.sub.i+s with respect to the curvature C.sub.2 of the entire point sequence. If the value of the variance is smaller than a predetermined value, it is decided that the point sequence is a part of a circular arc and consequently is detected as the circular arc.
However, the above-described conventional method have the following disadvantages:
The disadvantage common to the examples 1 and 2 is that in the processes (A) and (B), in forming a point sequence from edge points extracted from the two-dimensional image, false edge points are generated as a result of, for example, dirt adhering to the product or part roughness of the product surface, and electric signal noise. Such false edge points do not coincide with the required true edge points of the actual configuration of the product or parts to be measured or inspected. If extraction of edge points is repeated to remove the false edge points, some of the true edge points will disappear together with the false edge points. As a result, the required edge points decrease and the point sequence becomes short. Consequently, it becomes difficult to make a correct approximation of the circular arc. In addition, edge points serving as the information source of the approximation of a circular arc decrease, and thus, the position and radius of the circular are cannot be accurately calculated.
Further, it takes a long time for the methods of examples 1 and 2 to perform the necessary calculations because a large number of angle calculations is required.
As described previously, according to the example 1, the curvature C.sub.1 of the entire point sequence is expressed by the equation (4). But supposing that d.sub.0 is the length of the entire point sequence and .theta..sub.01 is the variation from the directional angle of a vector P.sub.1 P.sub.2 connecting one edge point of the point sequence and a point adjacent thereto with each other to the directional angle of a vector P.sub.N-1 P.sub.N connecting the other edge point of the point sequence and a point adjacent thereto with each other, the curvature C.sub.1 is expressed as follows: ##EQU3##
Usually the actual outline image of a product or part is not necessarily thin, but thick. According to the above-described method for extracting edge points which uses filtering, large errors are made in determining the coordinates of edge points. In addition, since the average value d.sub.i+1 of the equation (3) is small, a large error is made in the directional angle, between the vector P.sub.1 P.sub.2 and the vector P.sub.N-1 P.sub.N, which determines the variation .theta..sub.01. Thus, a large error occurs in the calculation of the variation .theta..sub.01, namely, in the calculation of the curvature C.sub.1 of the entire point sequence.
According to the example 2, since the average value d.sub.i+s of the equation (5) is (s) times as great as the average value d.sub.i+1 of the equation (3) of the example 1, errors in determining the coordinates of edge points are not large and consequently, the error of the curvature C.sub.2 of the entire point sequence is smaller than that of the example 1. But if the number of point sequences is small, the curvature cannot be calculated depending on the value of (s). Further, according to the example 2, there is no reference value on which an appropriate value of (s) is determined.
Furthermore, according to the examples, the center of the circular arc is not found.
Summary of the Invention
Accordingly, an essential object of the present invention is to provide a method for approximating a circular are in the processing of a two-dimensional image without forming a point sequence based on edge points and any inappropriate influence caused by errors, and capable of performing an approximation with a high accuracy.
In accomplishing these and other objects, according to one aspect of the present invention, there is provided a method for approximating the center position and radius of a circular arc detected in the processing a two-dimensional image, comprising the steps of:
extracting an aggregation of edge points from data of the two-dimensional image of a product or part having the circular arc to be detected, a configuration of which is measured or inspected;
finding the square of the distance between the center of a circular arc and a given edge point of an aggregation of the edge points;
finding the square of the radius of the circular arc used in the first finding step;
finding the square of the difference between the two squares;
taking a mean value of a fourth power error obtained by the square of the difference of the two squares; and
minimizing the mean value of the fourth power error to perform an approximation so as to estimate a circular arc having the minimum mean value as an approximated circular arc of the circular arc to be detected in the aggregation of the edge points..
According to the above construction, since it is unnecessary to perform processing for forming a point sequence based on edge points, a great number of edge points can be provided as the information source for approximating the center position and radius of a circular arc. In addition, even though errors occur in determining the coordinates of edge points, they do not cause calculations to be inappropriately performed. Further, it is unnecessary to perform angle calculations, the center and radius of the circular arc can be approximated with a high accuracy by easy calculations.
Brief Description of the Drawings
These and other objects and features of the present invention will become clear from the following description taken in conjunction with the preferred embodiments thereof with reference to the accompanying drawings, in which:
FIG. 1 is a flowchart according to an embodiment of the present invention;
FIG. 2 is an example of an output of a Laplacian filter to be used in the extraction of edge points in the embodiment of the present invention and the conventional method;
FIG. 3 is an illustration showing the conventional method of extracting edge points;
FIG. 4 is an illustration showing the conventional method of extracting edge points;
FIG. 5 is an illustration showing the conventional method of composing a point sequence;
FIG. 6 is an illustration showing a first example of the conventional method for calculating a radius of curvature; and
FIG. 7 is an illustration showing a second example of the conventional method for calculating a radius of curvature.
Detailed Description of the Invention
Before the description of the present invention proceeds, it is to be noted that like parts are designated by like reference numerals throughout the accompanying drawings.
Referring now to accompanied drawings, the method for approximating the center position and radius of a circular arc in the processing of a two-dimensional image according to an embodiment of the present invention will be described below.
FIG. 1 is a flowchart according to an embodiment of the present invention. In this embodiment, a circular arc configuration of a product or part is approximated using an apparatus including an image pick-up device, an image storing/processing device, and a calculating device.
At step #1, the image of a product or part to be detected having a circular arc configuration is picked up and the density of a two-dimensional image is differentiated based on the data thereof. The image is filtered by a digital differential filter such as ! a Laplacian filter and consequently, the output distribution of the filtering as shown in FIG. 2 is obtained.
At step #2, the aggregation of edge points is extracted from the two-dimensional image.
At the edge point, an image density abruptly changes. The edge point corresponds to an outline at which the image brightness suddenly changes on the product or part to be measured or inspected. The absolute value of the differentiated value of an image density is great at the edge point. Therefore, in the output distribution in FIG. 2 obtained at step #1, points of a great absolute value are extracted as edge points and the aggregation of the edge points is obtained. Although this method generates a few false edge points due to, for example, dirt adhered to of the product or the part, roughness of the product surface, or electric signal noise, the number of required true edge points is high. Therefore, according to this method, inappropriate influence is hardly given in detecting the center position and radius of a circular arc.
At step #3, the center position and radius of a circular arc is approximated and detected by the present method for minimizing a mean fourth power error based on the aggregation of the edge points obtained at step #2.
This method is described below.
The equation (8) indicates a circle having the radius (r) and the center at a point (a, b). The equation (8) can be expressed as follows:
The square of the distance between the center (a, b) of the circular arc to be detected and a given edge point (x.sub.i, y.sub.i) is equal to the left side portion {(x-a).sup.2 +(y-b).sup.2 } of the equation (8).
Supposing that (r) is the radius between the edge point to be detected and the point (a, b), the following equation (10) is established:
(e.sub.i) of the equation (10) is the difference between the square of the distance between the center (a, b) of the circular arc and the edge point (x.sub.i, y.sub.i) and the square of the radius (r) of the circular arc. Thus, the equation (10) can be expressed as follows: ##EQU4##
Finding the average value (E) of the sum of the square of the equation (11) with respect to (N) edge points, the following equation (12) is obtained: ##EQU5##
The center (a, b) of the circular arc and the radius (r) thereof which are approximated by the equations (8) and (9) are obtained by (A), (B), and (C) which minimize the average value (E) of the equation (12). The equation (12) represents the method for minimizing the mean fourth power error according to the embodiment of the present invention.
Supposing that f (x.sub.i, y.sub.i) is the differentiated value of the image density at the given edge point (x.sub.i, y.sub.i), the equation (12) can be expressed as follows: ##EQU6##
The equation (13) may be used instead of the equation (12) by giving the differentiated value of the image density at each edge point as a load to the mean fourth power error at each edge point. In this case, the load may be expressed in the form of a given function of the differentiated value f (x.sub.i, y.sub.i) of the image density, for example, a square root, a logarithmic function, and an exponential function. Since the change in an image brightness can be appropriately reflected in an approximative calculation, approximative calculations can be appropriately performed.
The method for finding (A), (B) and (C) which minimize the average value (E) of the equation (13) is described below. To this end, the equation (13) is partially differentiated by (A), (B) and (C). Then, the following simultaneous equation (14) is solved. ##EQU7##
The simultaneous equations of the equation (14) is solved as follows: ##EQU8##
Supposing Z.sub.i =x.sub.i.sup.2 +y.sub.i.sup.2, these equations (14-1), (14-2), and (14-3)are expressed as follows:
From the equation (14-1), ##EQU9##
From the equation (14-2), ##EQU10##
From the equation (14-3), ##EQU11##
Supposing ##EQU12## and .alpha. is an any value such as x, y, x.sup.2, or x.multidot.y, these equations are as follows:
From the equation (14-41),
From the equation (14-5)
From the equation (14-6)
ti Z-Ax-By+C=.theta. (14-6')
Here,(the left side of the equation (14-4')) -x.times.(the left side of the equation (14-6'))=.theta.,
Here, (the left side of the equation (14-5')) -y.times.(the left side of the equation (14-6))=.theta.,
From the equation (22), ##EQU13##
Similarly, from the equation (23), the following equation is obtained:
From the equation (24), ##EQU14##
Similarly, from the equations (25) and (26),
Substituting the equations (14-12) , (14-9), and (14-11) in the equation (14-7),
Substituting the equations (14-13), (14-10), and (14-11) in the equation (14-8),
The simultaneous equations (14-7') and (14-8') are solved to obtain the equations (15) and (16). ##EQU15##
The following equation (17) is obtained from the equation (14-6').
where
In the above equations, "V()" indicates variance, "C()" indicates covariance and upper bar affixed above x, y, and z indicates average. ##EQU16##
The coorrdinate (a, b) of the center and the radius (r) of the circular arc to be detected are calculated as follows from (A), (B) and (C) and the equations (8) and (9): ##EQU17##
Thus, the center position and radius of the circular arc to be detected from the data of the two-dimensional image can be approximated.
It is decided based on the value of (E) of the equation (13) with respect to (a) of the equation (27), (b) of the equation (28), and (r) of the equation (29) whether or not the aggregation of the edge points forms a circular are.
That is, if the value of (E) is smaller than a predetermined value, it is decided that the aggregation of the edge points forms the circular arc. Thus, a circle of radius (r) with the point (a, b) at the center thereof is detected.
According to the above construction, since it is unnecessary to perform processing for forming a point sequence based on edge points, a great number of edge points can be provided as the information source for approximating the center position and radius of a circular arc. In addition, even though errors occur in determining the coordinates of edge points, they do not cause calculations to be inappropriately performed. Further, it is unnecessary to perform angle calculations, and the center and radius of the circular arc can be approximated with a high accuracy using simple easy calculations. Furthermore, since the differentiated value of the image density at each edge point is given as a load to the mean fourth power error at each edge point, the center position and radius of the circular arc can be accurately found.
Although the present invention has been fully described in connection with the preferred embodiments thereof with reference to the accompanying drawings, it is to be noted that various changes and modifications are apparent to those skilled in the art. Such changes and modifications are to be understood as included within the scope of the present invention as defined by the appended claims unless they depart therefrom.
Claims
What is claimed is:
1. A data processor implemented method for processing two-dimensional image data of an object to inspect a circular arc configuration of the object, the two-dimensional image data representative of a two-dimensional image containing an image of the circular arc configuration of the object, said method comprising: subjecting the two-dimensional image data to a data extraction process to extract edge point image data from the two-dimensional image data, the edge point image data indicative of an aggregation of image edge points of the image of the circular arc configuration of the object; and, subjecting the edge point image data to a data approximation process to approximate the circular arc configuration of the object, said data approximation process including a first data processing step of determining the square of a distance between a center of a given circle having a given radius and each image edge point of the edge point image data, a second data processing step of determining the square of the radius of the given circle, a third data processing step of determining, for each image edge point of the edge point image data, the square of a difference between the square of the distance determined in said first data processing step and the square of the radius determined in said second data processing step, a fourth data processing step of determining a mean of the squares of the differences determined in said third data processing step, the mean of the squares of the differences corresponding to a mean fourth power error of the given circle relative to the aggregation of image edge points of the edge point image data, and a fifth data processing step of defining a circle to be applied as the given circle in said first through third data processing steps which minimizes the mean of the squares of the differences determined in said fourth data processing step, the thus defined circle approximating the circular arc configuration of the object.
2. A data processor implemented method as claimed in claim 1, wherein, in said fourth and fifth data processing steps of said data approximation process, a differentiated value of an image density of each image edge point is applied as a load to the mean fourth power error at each image edge point.
3. A data processor implemented method as claimed in claim 1, wherein, in said fourth and fifth data processing steps of said data approximation process, a given function of a differentiated value of an image density of each image edge point is applied as a load to the mean fourth power error at each image edge point.
4. A data processor implemented method for inspecting a circular arc configuration of an object, said method comprising: viewing the circular arc configuration of the object with an image pick-up device to obtain a two-dimensional image of the circular arc configuration of the object; producing two-dimensional image data of the two-dimensional image obtained in said viewing step, the two-dimensional image data representative of an image density of the two-dimensional image of the circular arc configuration of the object, subjecting the two-dimensional image data to a data extraction process to extract edge point image data from the two-dimensional image data, the edge point image data indicative of an aggregation of image edge points of the image of the circular arc configuration of the object; and, subjecting the edge point image data to a data approximation process to approximate the circular arc configuration of the object, said data approximation process including a first data processing step of determining the square of a distance between a center of a given circle having a given radius and each image edge point of the edge point image data, a second data processing step of determining the square of the radius of the given circle, a third data processing step of determining, for each image edge point of the edge point image data, the square of a difference between the square of the distance determined in said first data processing step and the square of the radius determined in said second data processing step, a fourth data processing step of determining a mean of the squares of the differences determined in said third data processing step, the mean of the squares of the differences corresponding to a mean fourth power error of the given circle relative to the aggregation of image edge points of the edge point image data, and a fifth data processing step of defining a circle to be applied as the given circle in said first through third data processing steps which minimizes the mean of the squares of the differences determined in said fourth data processing step, the thus defined circle approximating the circular arc configuration of the object.
5. A data processor implemented method as claimed in claim 4, wherein said extraction process includes applying the two-dimensional image data to a digital differential filter.
6. A data processor implemented method as claimed in claim 4, wherein said extraction process includes applying the two-dimensional image data to a Laplacian filter.
7. A data processor implemented method as claimed in claim 4, wherein, in said fourth and fifth data processing steps of said data approximation process, a differentiated value of the image density of each image edge point is applied as a load to the mean fourth power error at each image edge point.
8. A data processor implemented method as claimed in claim 4, wherein, in said fourth and fifth data processing steps of said data approximation process, a given function of a differentiated value of the image density of each image edge point is applied as a load to the mean fourth power error at each image edge point.
9. An apparatus for inspecting a circular arc configuration of an object, comprising: an image pick-up device for viewing the circular configuration of the object to obtain a two-dimensional image of the circular arc configuration of the object, and for producing two-dimensional image data of the two-dimensional image, the two-dimensional image data representative of an image density of the two-dimensional image of the circular arc configuration of the object; and an image processing device for subjecting the two-dimensional image data produced by said image pick-up device to a data extraction process to extract edge point image data from the two-dimensional image data, the edge point image data indicative of an aggregation of image edge points of the image of the circular arc configuration of the object, and for subjecting the edge point image data to a data approximation process to approximate the circular arc configuration of the object, said data approximation process including a first data process of determining the square of a distance between a center of a given circle having a given radius and each image edge point of the edge point image data, a second data process of determining the square of the radius of the given circle, a third data process of determining, for each image edge point of the edge point image data, the square of a difference between the square of the distance determined in said first data process and the square of the radius determined in said second data process, a fourth data process of determining a mean of the squares of the differences determined in said third data process, the mean of the squares of the differences corresponding to a mean fourth power error of the given circle relative to the aggregation of image edge points of the edge point image data, and a fifth data process of defining a circle to be applied as the given circle in said first through third processor which minimizes the mean of the squares of the differences determined in said fourth data process, the thus defined circle approximating the circular arc configuration of the object.
10. An apparatus as claimed in claim 9, wherein said data processing device includes a digital differential filter for effecting said data extraction process.
11. An apparatus as claimed in claim 9, wherein said data processing device includes a Laplacian filter for effecting said data extraction process.
12. An apparatus as claimed in claim 9, wherein, in said fourth and fifth data processes of said data approximation process, a differentiated value of the image density of each image edge point is applied as a load to the mean fourth power error at each image edge point.
13. An apparatus as claimed in claim 9, wherein, in said fourth and fifth data processes of said data approximation process, a given function of a differentiated value of the image density of each image edge point is applied as a load to the mean fourth power error at each image edge point.