Image processing method and apparatus

What is claimed is:

1. A method of processing a variable-density image of a target object having a contour which includes straight-line portions, said image comprising edge pixels representing said contour, said method comprising: a line labeling step of setting a different one of labels to each of the directions of said straight-line portions; a pixel labeling step of assigning to those of said edge pixels, which have the same direction as any one of the different directions of said straight-line portions, the same label assigned to said any one different direction; and a line segment extracting step of extracting, as a line segment, an assembly consisting of those of said edge pixels which are continuous on said image and have a same one of said labels assigned thereto, said line labeling step, said pixel labeling step and said line segment extracting step being sequentially carried out.

2. The method of claim 1 wherein said line labeling step includes: a histogram making step of preparing a histogram from numbers of edge pixels having different directions; and a peak label setting step of extracting peaks from said histogram and setting a different label to each of the directions of edge pixels corresponding to a different one of the extracted peaks; said histogram making step and said peak label setting step being carried out such that said labels are each set to one of directions of straight-line portions contained in said contour of said target object; and wherein said pixel labeling step comprises the step of assigning each of the different labels set in said peak label setting step to each of the edge pixels having the direction corresponding to the each different label.

3. The method of claim 2 further comprising a unifying step, if the line segments extracted in said line segment extracting step include a pair with a positional displacement smaller than a specified maximum displacement value and a directional difference smaller than a specified maximum directional difference value, of unifying said pair into a single unified segment.

4. The method of claim 2 further comprising a selecting step of selecting, from the extracted line segments in said extracting, those of said line segments satisfying specified line segment selecting conditions.

5. The method of claim 3 further comprising a selecting step of selecting, from the extracted line segments in said extracting step and from the unified line segments in said unifying step, those of said line segments satisfying specified line segment selecting conditions.

6. The method of claim 4 further comprising a display step of distinguishably displaying on said image positions of the line segments selected in said selecting step.

7. The method of claim 5 further comprising a display step of distinguishably displaying on said image positions of the line segments selected in said selecting step.

8. The method of claim 4 further comprising a display step of distinguishably displaying on said image positions of crossing points of extensions of a plurality of the line segments selected in said selecting step.

9. The method of claim 5 further comprising a display step of distinguishably displaying on said image positions of crossing points of extensions of a plurality of the line segments selected in said selecting step.

10. The method of claim 2 further comprising a defect detecting step of determining whether a defect exists or not in straight-line portions of the contour of said target object by examining the line segments extracted in said line segment extracting step.

11. The method of claim 10 wherein it is determined in said defect detecting step, if there is a pair of line segments among the line segments extracted in said line segment extracting step, said pair of line segments having directions of which the difference is within a specified range and having a positional displacement within a specified limit, that there is a defect between said pair of line segments.

12. The method of claim 10 wherein it is determined in said defect detecting step that there is a defect in a straight-line portion of the contour of a target object by comparing the number of line segments extracted in said line segment extracting step with a specified standard value and if said number is different from said specified standard value.

13. The method of claim 1 wherein said line labeling step comprises setting a different one of said labels to each of expected directions of straight-line portions of the contour of said target object and said pixel labeling step comprises assigning said one label to those of the edge pixels having one of said expected directions.

14. The method of claim 13 further comprising a unifying step, if the line segments extracted in said line segment extracting step include a pair with a positional displacement smaller than a specified maximum displacement value and a directional difference smaller than a specified maximum directional difference value, of unifying said pair into a single unified segment.

15. The method of claim 13 further comprising a selecting step of selecting, from the extracted line segments in said extracting, those of said line segments satisfying specified line segment selecting conditions.

16. The method of claim 14 further comprising a selecting step of selecting, from the extracted line segments in said extracting step and from the unified line segments in said unifying step, those of said line segments satisfying specified line segment selecting conditions.

17. The method of claim 13 further comprising a defect detecting step of determining whether a defect exists or not in straight-line portions of the contour of said target object by examining the line segments extracted in said line segment extracting step.

18. An image processing apparatus comprising: image inputting means for inputting a variable-density image of a target object having a contour; edge pixel extracting means for extracting edge pixels contained in said image; orienting means for calculating the directions of said extracted edge pixels; direction setting means for setting directions of straight-line portions contained in said contour; line labeling means for setting a different one of labels to each of the directions of said straight-line portions; pixel labeling means for assigning to those of said edge pixels, which have the same direction as any one of the different directions of said straight-line portions, the same label assigned to said any one different direction; and line segment extracting means for extracting, as a line segment, an assembly consisting of those of said edge pixels which are continuous on said image and have a same one of said labels assigned thereto.

19. The image processing apparatus of claim 18 wherein said direction setting means comprises: histogram making means for preparing a histogram from numbers of edge pixels having different directions; and peak extracting means for extracting peaks from said histogram; wherein said line labeling means sets a different label to each of the directions of edge pixels corresponding to a different one of the extracted peaks; and wherein said pixel labeling means assigns each of the different labels set by said line labeling means to each of the edge pixels having the direction corresponding to the each different label.

20. The image processing apparatus of claim 19 further comprising unifying means for serving, if the line segments extracted by the aforementioned line segment extracting means include a pair with a positional displacement smaller than a specified maximum displacement value and a directional difference smaller than a specified maximum directional difference value, to unify said pair into a single unified segment.

21. The image processing apparatus of claim 19 further selecting means for selecting, from the line segments extracted by said line segment extracting, those of said line segments satisfying specified line segment selecting conditions.

22. The image processing apparatus of claim 20 further comprising selecting means for selecting, from the line segments extracted by said line segment extracting means and from the unified line segments unified by said unifying means, those of said line segments satisfying specified line segment selecting conditions.

23. The image processing apparatus of claim 21 further comprising display means for displaying positions of the line segments selected by said selecting means so as to be distinguishable on said image.

24. The image processing apparatus of claim 22 further comprising display means for displaying positions of the line segments selected by said selecting means so as to be distinguishable on said image.

25. The image processing apparatus of claim 21 further comprising display means for distinguishably displaying on said image positions of crossing points of extensions of a plurality of the line segments selected by said selecting means.

26. The image processing apparatus of claim 22 further comprising display means for distinguishably displaying on said image positions of crossing points of extensions of a plurality of the line segments selected by said selecting.

27. The image processing apparatus of claim 18 further comprising defect detecting means for determining whether a defect exists or not in straight-line portions of the contour of said target object by examining the line segments extracted by said line segment extracting means.

28. The image processing apparatus of claim 27 wherein said defect detecting means determines, if there is a pair of line segments among the line segments extracted by said line segment extracting means, said pair of line segments having directions of which the difference is within a specified range and having a positional displacement within a specified limit, that there is a defect between said pair of line segments.

29. The image processing apparatus of claim 27 wherein said defect detecting means determines that there is a defect in a straight-line portion of the contour of a target object by comparing the number of line segments extracted by said line segment extracting means with a specified standard value and if said number is different from said specified standard value.

30. The image processing apparatus of claim 18 wherein said direction setting means inputs expected directions of the straight-line portions of the contour of said target object, said line labeling means sets a different one of said labels to each of the expected directions inputted by direction setting means, and said pixel labeling means assigns said labels to those of the edge pixels having one of the expected directions inputted by said direction setting means.

31. The image processing apparatus of claim 30 further comprising unifying means for serving, if the line segments extracted by said line segment extracting means include a pair with a positional displacement smaller than a specified maximum displacement value and a directional difference smaller than a specified maximum directional difference value, to unify said pair into a single unified segment.

32. The image processing apparatus of claim 30 further comprising selecting means for selecting, from the line segments extracted by said line segment extracting means, those of said line segments satisfying specified condition.

33. The image processing apparatus of claim 31 further comprising selecting means for selecting, from the line segments extracted by said line segment extracting means and from the unified line segments in said unifying means, those of said line segments satisfying specified condition.

34. The image processing apparatus of claim 30 further comprising defect detecting means for determining whether a defect exists or not in straight-line portions of the contour of said target object by examining the line segments extracted by said line segment extracting means.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

This invention is in the technical field of image processing by means of a computer and relates in particular to methods and apparatus for measuring the position and orientation of a target object with a contour containing straight lines and inspecting whether there is a defect in the contour.

When the position and orientation of an object are observed or defects on its contour are being inspected on a variable-density image, there are situations in which it becomes desirable to extract straight-line portions from the contour of the target object. Conventional methods of extracting the contour of a target object include those by binary representation of the image, those based on the magnitude of the density gradient and those using an expanded or contracted image.

By a binary representation method, an image is divided into areas with white and black pixels and a contour line is formed by the pixels located at their boundary. By a method depending on the density gradient, the density gradient at each pixel is calculated and a contour line is formed by those of the pixels at which the density gradient exceeds a specified threshold value. By a method using an expanded or contracted image, an expanded image and a contracted image are formed by expanding the contracting the bright area of the original image and a contour line is extracted by producing a differential image therefrom.

By any of these methods, what is extracted is the contour line as a whole, and none of them can be used to extract only straight-line portions of the contour. In order to extract a straight-line portion of the contour line, it may be attempted to evaluate the connection pattern of the pixels forming the contour line and to identify the portions which may each be considered to represent a straight line, for example, by considering the pixels on the contour line sequentially to examine whether they are connected in a same direction. If it is attempted to improve the resolution of connection direction, however, an average of directions of connection of several pixels must be considered and hence very small defects which interrupt the connection will have to be ignored. If the contour lines are extracted so as to have a finite width, furthermore, it is difficult enough to establish an algorithm for extracting a straight line.

By any of these prior art methods, furthermore, the characteristics of a contour line (such as its width and position, as well as the sizes of protrusions and indentations thereon) will change, depending on the conditions of the image (such as the difference in density between the background and the target object and the uniformity in brightness). It is therefore difficult to dependably extract a straight-line portion of a contour line by any of these methods relying on evaluation of the connection pattern of pixels.

SUMMARY OF THE INVENTION

It is therefore an object of this invention to accurately and speedily extract a straight-line portion of the contour line of a target object on a variable-density image.

It is another object of this invention to accurately extract a straight-line portion of a target object, independent of the conditions of the image even where the density difference is small between the background and the target object or where the lighting condition is not uniform.

It is a further object of this invention to measure the position or orientation of a target object or to extract a defect on the contour of a target object on the basis of straight lines extracted from the contour of the target object.

For processing a variable-density image of a target object having a contour which is represented by edge pixels and includes straight-line portions according to this invention, the following steps are sequentially carried out: (1) line labeling step of setting a different one of labels to each of the directions of the straight-line portions, (2) pixel labeling step of assigning to those edge pixels which have the same direction as one of the different directions of the straight-line portions the same label assigned to the corresponding one of the different directions of the straight-line portions, and (3) line segment extracting step of extracting, as a line segment, an assembly consisting of those of the edge pixels which are continuous on the image and have the same label assigned thereto. Those of the pixels forming the contour line of a target object on a variable-density image are herein referred to as "edge pixels". The contour line need not have a width of one pixel. It may contain a plurality of edge pixels in the direction of its width.

One of convenient methods of extracting edge pixels is to select those of the pixels at which the density gradient of the image is greater than a specified threshold value. Not all of the pixels extracted by such a method need be finally defined as the edge pixels. A thinning process for thinning a line including all of those pixels initially extracted as edge pixels may be carried out to make the contour line thinner and only those pixels forming such a thinned contour line may be referred to as edge pixels. On the other hand, the concept of density gradient may be ignored in extracting edge pixels, say, by extracting only those pixels corresponding to a boundary line on a binary image with only white and black regions. No matter how edge pixels are extracted, however, those pixels at which the density gradient is relatively large are extracted as edge pixels.

The direction of an edge pixel may be defined in different ways. It is normally defined as the direction perpendicular to the direction of the density gradient at its position because it is convenient, if not strictly necessary, to define the direction of an edge pixel to be the same as the direction of a straight-line portion which contains this edge pixel. In other words, if the direction of a straight-line portion is defined to be the direction perpendicular to the direction of its extension, although it is contrary to or at least different from the conventional definition, the direction of an edge pixel may be accordingly defined, for the purpose of this invention, to be the same as the direction of the density gradient at the pixel. For the convenience of disclosure, however, the direction of an edge pixel will be defined hereinafter as the direction perpendicular to the density gradient at the position of the pixel. The direction of a straight-line portion and that of the edge pixels contained therein need not be exactly the same. In the description of the present invention, their difference is required only to be smaller than by a value specified according to the purpose of the image processing.

When two pixels are said to be continuous or in a continuing relationship, it does not necessarily mean that there are no other pixels between them. It generally means that they satisfy a neighborhood condition specified particularly for the analysis. The so-called four-neighbor condition by which two pixels are connected only if they are next to each other in the horizontal or vertical direction and the so-called eight-neighbor condition by which the four diagonal directions are added to the four-neighbor condition are frequently adopted, but the scope of the neighborhood may be defined more broadly.

In this invention, it is noted that directions of edge pixels can be determined with high accuracy because the density gradient is relatively large at their positions. Thus, line segments are represented as assemblies of edge pixels extracted on the conditions that they have a common label assigned according to their directions and that they are continuous and hence straight-line portions of the contour of a target object on an image can be extracted reliably. Moreover, since the directions of edge pixels can be extracted dependably without regard to the condition of the variable-density image or even where the difference in density between the background and the target object is small or the condition of illumination is not uniform, such straight-line portions can be extracted correctly even under such conditions.

Each of the steps in the method of this invention may be carried out either on a given variable-density image as a whole or by specifying an area of measurement on such an image and only on the specified area.

In the aforementioned line labeling step, labels may be each set to one of the directions of straight-line portions contained in the contour of the target object by carrying out (1a) a histogram making step of preparing a histogram from the numbers of edge pixels having different directions and (1b) a peak label setting step of extracting peaks from this histogram and setting a different label to each of the directions of edge pixels corresponding to a different one of the extracted peaks. In the aforementioned pixel labeling step, each of the different labels set in the peak label setting step is assigned to each of the edge pixels having the corresponding direction. Such a histogram may be made to directly show the numbers themselves of the edge pixels having different directions or by multiplying such numbers with a weight factor such as representing the density gradient at the position of the corresponding edge pixels.

The direction of edge pixels corresponding to a peak may mean the direction of the edge pixels in the corresponding one of the divisions of the histogram or the directions of the edge pixels in a plurality of divisions including those proximal to the corresponding division. Thus, straight-line portions can be extracted from the contour of the target object even if they have any of these directions or even if their directions are not preliminarily known. The extraction of the peaks may be carried out according to a specified criterion such that the tallest peak and a given number of next tallest peaks or all peaks taller than a specified threshold height may be extracted.

If the line segments extracted in the aforementioned line segment extracting step include a pair with a positional displacement smaller than a specified maximum displacement value and a directional difference smaller than a specified maximum directional difference value, such a pair may be unified into a single unified segment. Even if a line segment is divided into two parts by a cut or a protrusion on the contour, the two parts can thus be unified back into a single line segment. Thus, the position and orientation of a target object, even if it has such a cut or a protrusion on its contour, can be accurately measured.

The method may further include a selecting step of selecting, from the extracted line segments in the aforementioned extracting step and from the unified line segments in the unifying step, those of the line segments satisfying specified line segment selecting conditions such that line segments appropriate for the image processing under such specified conditions can be obtained. The conditions for extracting line segments may relate to the range in their lengths, the range in angles they make with a standard direction, the range in the positions, the range in the distance between their end positions, the range in the angle between two line segments and the order of their lengths. The method may also include a display step of displaying on the variable-density image in a distinguishable form positions of the line segments or the crossing points of extensions of a plurality of line segments selected in the selecting step such that the conditions of extraction and selection of line segments can be clearly shown to the user. By observing such a display, the user can ascertain whether or not intended positions such as a corner of the target object has been correctly selected in an area of measurement.

According to another embodiment of the invention, a defect detecting step may be carried out to determine whether a defect is present or absent in straight-line portions of the contour of the target object from the manners in which the line segments are extracted in the aforementioned line segment extracting step. According to this invention, line segments are extracted on the basis of the continuity of edge pixels having directions which may be considered equal. Since the directions of edge pixels change significantly by the presence of even a small defect of only a few pixels in the contour, even such small defects can be detected with a high level of accuracy.

For example, if there is a pair of line segments among the line segments extracted in the line segment extracting step between which the difference in direction is within a specified range and the positional displacement is also within a specified limit, it may be concluded that there is a defect between such pair of line segments. As another example, it may be concluded that there is a defect in a straight-line portion of the contour of a target object by comparing the number of line segments extracted in the line segment extracting step with a specified standard value and if they are different and do not match.

According to another embodiment of the invention, the aforementioned line labeling step is carried out by setting a different label to each of expected directions of straight-line portions of the contour of the target object and the aforementioned pixel labeling step is carried out by assigning the same label to those of the edge pixels having the corresponding one of the expected directions. When the directions of straight-line portions of the contour of a target object can be expected such as when the orientation of the target object is fixed, the process can be carried out speedily because individual labels can be set without making a histogram for each variable-density image to be analyzed. A method according to this embodiment may also be used for determining whether the target object may pass as a product without a defect or for classifying the target objects, into categories on the basis of the determination whether the contour of the tested target object contains straight-line portions in expected directions.

An image processing apparatus embodying this invention may be characterized as comprising image inputting means for inputting a variable-density image of a target object having a contour, edge pixel extracting means for extracting edge pixels contained in this image, orienting means for calculating the directions of these extracted edge pixels, direction setting means for setting directions of straight-line portions contained in the contour; and means for carrying out the aforementioned line labeling, pixel labeling and line segment extracting steps. With an apparatus thus structured, edge pixels are extracted from an inputted variable-density image and their directions are obtained. On the other hand, labels are individually set for each of the directions of straight-line portions of the contour of a target object. Those of the edge pixels with a direction matching any of the directions of the straight-line portions are assigned the label for the straight-line portions of the matching direction. Assemblies of edge pixels having the same label assigned and being continuous are then extracted as line segments. Thus, straight-line portions of the contour of a target object can be extracted accurately.

The image input means is connected to an image generating device such as a camera or a scanner and is adapted to take in a variable-density image obtained thereby. It may comprise an interface circuit or an A/D conversion circuit. For the purpose of inputting an image, it may be composed of a circuit for receiving an image transmitted through telecommunication lines or a reading device for reading an image stored in a memory medium.

Many of the "means" contained in an apparatus as described above may be realized in the form of computer hardware and software for operating it. Some of them may be formed in the form of a circuit block such as ASIC (application specific integrated circuit) with a computer controlling the coordinated operations of the circuit blocks.

A filter for extraction of edge pixels such as a Sobel filter may be used as the edge pixel extracting means and the orienting means. In addition, various methods of extracting a contour may be carried out on the image memory of a computer.

According to an embodiment of the invention, the aforementioned direction setting means may comprise histogram making means for preparing a histogram from numbers of edge pixels having different directions and peak label extracting means for extracting peaks from this histogram. A line labeling means sets a different label to each of the directions of edge pixels corresponding to a different one of the extracted peaks, and each of these different labels is assigned by a pixel labeling means to each of the edge pixels having the direction corresponding thereto.

Various means such as unifying means, selecting means, display means and defect detecting means for respectively carrying out the aforementioned unifying, selecting, display and defect determining steps may be included in an apparatus embodying this invention.

According to another embodiment of the invention, the aforementioned direction setting means inputs expected directions of the straight-line portions of the contour of the target object, the line labeling means sets a different one of the labels to each of the expected directions inputted by the direction setting means, and the pixel labeling means assigns these labels to those of the edge pixels having one of the expected directions inputted by the direction setting means.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1 is a block diagram of an image processing apparatus embodying this invention;

FIG. 2 is a flowchart of an image processing process;

FIG. 3 shows a mask for extracting edge pixels;

FIG. 4 is a drawing for showing the definition of edge code;

FIG. 5A is an example of variable-density image of a target object and FIG. 5B is an edge code histogram which may be obtained by extracting edge pixels according to a method of this invention;

FIGS. 6A and 6B are results of preliminary and final labeling processes, respectively, on the image shown in FIG. 5A;

FIG. 7 shows various characteristics of a line segment calculated according to a method of this invention;

FIG. 8 is a flowchart of a routine for checking whether two line segments can be unified or not;

FIG. 9 is a drawing for explaining the parameters used in the routine of FIG. 8;

FIGS. 10A and 10B show examples of line segments that may be unified and may not be unified;

FIG. 11 shows an example of a plurality of line segments which have been unified;

FIG. 12 shows an example of process for extracting line segments;

FIG. 13 shows another example of a process for extracting line segments; and

FIGS. 14A and 14B show an example of a process for extracting line segments forming a rectangle.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1 shows the structure of an image processing apparatus 1 embodying this invention for extracting on a digital variable-density image (hereinafter simply referred to as the image) straight-line portions on the contour of a target object and, if there are a plurality of such straight-line portions, the crossing points of the extensions of these straight-line portions. The apparatus 1 is composed of an image input device 2, an image memory 3, an image output device 4, a timing controller 5, a character-graphic memory 6, a character memory 7, a control unit 8, a monitor 9 and an I/O port 10.

The image input device 2 is composed of an interface circuit for receiving variable-density image signals from an analog camera (not shown), an A/D converter circuit for converting the variable-density image signals received by the interface circuit into digital signals, and a filter circuit for cutting noise. The invention, however, is not limited to the use of an analog camera. A digital camera may be used within the scope of the invention.

The image memory 3 serves to receive the digital variable-density image data received by the image input device 2 and A/D converted and to store them. The character-graphic memory 6 stores image data necessary for the display of histograms, results of processing and screens for setting conditions for the extraction of line segments, to be explained below.

The character memory 7 stores test data for displaying character data such as inspection results and the positions of display. These memory devices 3, 6 and 7 are individually connected to the control unit 8 through an address/data bus 11 and serve to output data to the image output device 4 or to the address/data bus 11 in response to requests from the control unit 8 and according to timing signals from the timing controller 5.

The control unit 8 is compos