Method for collating independent figure elements between images

• US 5,206,917 A
• Filed: 04/10/1991
• Issued: 04/27/1993
• Est. Priority Date: 04/19/1990
• Status: Expired due to Fees

• Current Assignee: Nippon Sheet Glass Company Limited (Nippon Telegraph and Telephone Corporation)
• Original Assignee: Nippon Sheet Glass Company Limited (Nippon Telegraph and Telephone Corporation)
• Inventors: Ueno, Hiroshi, Nishi, Hisami
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/683,557
• Time in Patent Office: 748 Days
• Field of Search: 382/44, 382/45, 382/46, 382/8, 382/34, 382/5, 382/6
• US Class Current: 382/288
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning

Abstract

A method for collating independent figure elements in an object image with a reference image both including independent elements which are not interlinked with each other. The method comprises steps of defining a relative coordinate system in an image plane for the reference image and the object image on the basis of centers of gravity of two distinctive independent elements which are identified with values indicative of features of the elements; and collating pairs of independent elements between the reference image and the object image on the basis of the relative coordinate system.

Claims

1. A method for correlating independent pattern elements in an object image with a reference image both images including elements which are not interlinked with each other, the elements of each image having a fixed positional relationship to one another, comprising steps of:

plotting said elements on orthogonal coordinates and plotting values indicative of features of each element on orthogonal feature coordinates;

selecting two distinctive independent elements in the reference image based on values indicative of features of each element plotted on said orthogonal feature coordinates;

identifying the two distinctive independent elements in the object image based on the values indicative of features of the selected elements;

defining a relative coordinate system in an image plane for each of the reference image and the object image such that a predetermined coordinate of each of the two distinctive independent elements are used to establish one axis of the relative coordinate system;

plotting the elements of each image on the relative coordinate system such that the positional relationships between the elements of each image are not altered; and

correlating pairs of independent elements between the reference image and the object image on the basis of the relative coordinate system.

2. A method according to claim 1, wherein said relative coordinate system is defined with an axis passing through both predetermined coordinates of the distinguished two elements and an orthogonal axis passing through the predetermined coordinate of one of two elements.

3. A method according to claim 1, wherein said features used to identify the distinctive elements of the object image are values of the area and the perimeter of the independent elements.

4. A method according to claim 1, wherein distances from one element of the reference image to each element of the object image are calculated by reference to coordinates indicative of positions of the elements, a minimum distance is found to determine correspondence of one of the elements of the object image with one element of the reference image, and repeating the process to correlate all of the independent elements within both images.

5. A method according to claim 1, wherein the reference image and the object image are digitized on X-Y coordinate system and then converted onto the relative coordinate system.

6. A method according to claim 1, wherein the features of the elements so correlated are compared to perform pattern matching.

7. A method according to claim 1, wherein a distance is calculated from each independent pattern element to the nearest independent pattern element within the reference image, an allowable range smaller than the distance is set so as to correspond to each independent pattern element, and each pattern element in the object image is detected to be located within the allowable range, for pairing elements in the object image with the elements in the reference image.

17. The method of claim 1, wherein the predetermined coordinate of the independent element is indicative of the center of gravity of the independent element.

8. A method for correlating an object image with a reference image both including independent figure elements which are not interlinked with each other, the independent elements having a fixed positional relationship to one another, comprising the steps of:

plotting said elements on orthogonal coordinates and plotting features of figure of each element on orthogonal feature coordinates;

selecting two elements which are distinguished from other elements in the reference image based on features of figure plotted on said orthogonal feature coordinates;

identifying a predetermined coordinate for each of the selected elements;

defining a relative coordinate system with an axis passing through both of the predetermined coordinates and an orthogonal axis passing through one of the predetermined coordinates and then converting the predetermined coordinate of each selected element in the reference image onto the relative coordinate system;

selecting from the object image two elements having substantially identical features with those of the selected elements in the reference image, identifying a predetermined coordinate for each of the selected elements, plotting the selected elements on the relative coordinate system so that an axis passes through both if the identified predetermined coordinates and a normal axis passes through one of the identified predetermined coordinates, and then converting the predetermined coordinate of each element in the object image onto the relative coordinate system without altering the positional relationship between the elements;

comparing the predetermined coordinates of respective elements in the object image with those of elements in the reference image on the relative coordinate system to prepare a list of paired elements between the object image and the reference image; and

correlating features of figure between said paired elements to discriminate an object element different from the corresponding reference element in the feature of figure.

9. A method according to claim 8, wherein said step for preparing a list of paired elements comprising steps of:

calculating a distance from each independent pattern element to the nearest independent pattern element within the reference image with respect to the predetermined coordinates thereof,

setting an allowable range smaller than the distance so as to correspond to each independent pattern element, and

calculating a distance from each pattern element in the reference image to each pattern element in the object image with respect to the predetermined coordinates thereof and pairing these element when the distance is smaller than the allowable range.

10. A method according to claim 8, wherein said features of figure to distinguish the element are attributes which are not affected by positional and rotational shifts of the image.

11. A method according to claim 10, wherein said features of figure are values of the area and the perimeter of the figure elements.

18. The method of claim 8, wherein the predetermined coordinate of the independent element is indicative of the center of gravity of the independent element.

12. A method for collating independent pattern elements in an object image with a reference image, both the reference and object images having pattern elements which are not interlinked with each other, the method comprising the steps of:

selecting two distinctive independent elements in the reference image based on values indicative of features of each element plotted on orthogonal coordinates;

defining a relative coordinate system in an image plane for each of the reference image and the object image such that the centers of gravity of the two distinctive independent elements are used to establish one axis of the relative coordinate system, the two distinctive elements in the object image being identified by the features of the independent elements indicative of the area and the perimeter of the independent elements; and

collating pairs of independent elements of the reference image and the object image on the basis of the relative coordinate system.

13. A method of collating independent pattern elements in an object image with independent pattern elements reference image, both including elements which are not interlinked with each other, the method comprising the steps of:

selecting two distinctive independent elements in the reference image based on values indicative of features of each element plotted on orthogonal coordinates;

defining a relative coordinate system in an image plane for each of the reference image and the object image such that the centers of gravity of the two distinctive independent elements are used to establish one axis of the relative coordinate system, the two distinctive elements in the object image being identified with values indicative of features of the elements;

collating pairs of independent elements of the reference image and the object image on the basis of the relative coordinate system; and

wherein a distance is calculated from each independent pattern element to the nearest independent pattern element within the reference image, an allowable range smaller than the distance is set so as to correspond to each independent pattern element, and each pattern element in the object image is detected to be located within the allowable range thereby pairing the independent elements in the object image with the independent elements in the reference image.

14. A method for collating an object image with a reference image both including independent figure elements which are not interlinked with each other, comprising the steps of:

selecting two elements which are distinguished from other elements in the reference image to have at least one distinctive feature of figure plotted on orthogonal coordinates;

identifying a coordinate indicative of the predetermined coordinate for each of the selected elements;

defining a relative coordinate system with an axis passing through both of the predetermined coordinates and an orthogonal axis passing through one of the predetermined coordinates and then converting the coordinate indicative of the predetermined coordinate of each selected element in the reference image onto the relative coordinate system;

selecting from the object image two elements having identical features with those of the selected elements in the reference image, identifying a coordinate indicative of the predetermined coordinate for each of the selected elements, defining a relative coordinate system with an axis passing through both of the identified coordinates and a normal axis passing through one of the identified coordinates, and then converting the coordinate indicative of the predetermined coordinate of each selected element in the object image onto the relative coordinate system;

comparing coordinates of respective centers of gravity of elements in the object image with those of elements in the reference image on the relative coordinate system to prepare a list of paired elements between the object image and the reference image;

collating features of figure between said paired elements to discriminate an object element different from the corresponding reference element in the feature of figure; and

preparing a list of said paired elements by calculating a distance from each independent pattern element to the nearest independent pattern element within the reference image with respect to the centers of gravity thereof, setting an allowable range smaller than the distance so as to correspond to each independent pattern element, and calculating a distance rom each pattern element in the reference image to each pattern element in the object image with respect to the centers of gravity thereof and pairing these elements when the distance is smaller than the allowable range.

15. A method according to claim 14, wherein said list of said paired elements includes;

distances calculated from one element in the reference image to each of the elements in the object image by reference to coordinates indicative of centers of gravity of the elements, and

minimum distances each between the one element in said reference image and one of the elements in the object image upon repeating the process to collate all of the independent elements within both images.

16. A method for collating an object image with a reference image both including independent figure elements which are not interlinked with each other, comprising the steps of:

selecting two elements which are distinguished from other elements in the reference image to have at least one distinctive feature of figure plotted on orthogonal coordinates;

identifying a coordinate indicative of the predetermined coordinate for each of the selected elements;

defining a relative coordinate system with an axis passing through both of the predetermined coordinates and an orthogonal axis passing through one of the predetermined coordinates and then converting the coordinate indicative of the predetermined coordinate of each selected element in the reference image onto the relative coordinate system;

selecting from the object image two elements having substantially identical features with those of the selected elements in the reference image, identifying a coordinate indicative of the predetermined coordinate for each of the selected elements, defining a relative coordinate system with an axis passing through both of the identified coordinates and a normal axis passing through one of the identified coordinates, and then converting the coordinate indicative of the predetermined coordinate of each selected element in the object image onto the relative coordinate system;

comparing coordinates of respective centers of gravity of elements in the object image with those of elements in the reference image on the relative coordinate system to prepare a list of paired elements between the object image and the reference image; and

collating features of figure between said paired elements to discriminate an object element different from the corresponding reference element in the feature of figure, said features of figure to distinguish the element being attributes which are not affected by positional and rotational shifts of the image, and being values of the area and the perimeter of the figure elements.