Method for producing a standard pattern for pattern matching

• US 4,783,831 A
• Filed: 09/19/1985
• Issued: 11/08/1988
• Est. Priority Date: 09/19/1984
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Shima, Yoshihiro, Miyatake, Takafumi, Kashioka, Seiji, Ejiri, Masakazu
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/777,724
• Time in Patent Office: 1,146 Days
• Field of Search: 382/19, 382/25, 382/27, 382/30, 382/34, 382/14
• US Class Current: 382/218
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 10/443 by matching or filtering

Abstract

This invention provides a method and apparatus for automatically producing a standard pattern for local pattern matching. According to the present invention, local patterns equivalent in size to a standard pattern to be obtained are successively removed from the image of an object being examined to prepare standard pattern candidates. Evaluation values representing appropriateness as a standard pattern are obtained from the local patterns successively removed or the local patterns together with the image of the object being examined. The evaluation values are used in an evaluation function expressing the uniqueness of the standard pattern and in an auxiliary evaluation function as an aid to the former. The standard pattern is selected using such evaluation values.

Claims

1. A method of producing a standard pattern comprising:

successively selecting and storing in a memory of plurality of local patterns different in position and equal in size to a standard pattern to be obtained from an image of an object being examined;

obtaining a distribution of pattern detail in picture elements constituting each local pattern; and

chosing a standard pattern from said plurality of local patterns which has a distribution of pattern detail in picture elements most closely in conformity with a predetermined distribution of pattern detail.

2. A method of producing a standard pattern as claimed in claim 1, wherein, when the picture elements have binary values, a determination is made whether or not a number of picture elements having either of two binary values among the picture elements constituting each local pattern satisfies predetermined conditions.

3. A method of producing a standard pattern as claimed in claim 2, wherein said predetermined conditions of the number of picture elements conditions are such that a number of picture elements having either binary value is about half a total of picture elements of said local patterns.

4. A method of producing a standard pattern as claimed in claim 2, wherein a determination is made whether or not boundary lengths included in said local patterns being in conformity with said predetermined conditions are within a predetermined range and standard patterns are obtained from said local patterns within said predetermined range.

5. A method of production of a standard pattern in accordance with claim 1 further comprising the steps:

(a) inputting the image of the object and storing the image in the memory;

(b) loading in a memory a local pattern and making the local pattern a standard pattern candidate;

(c) obtaining a value of minimum matching errors between said standard pattern candidate and each of one or more other local patterns, each of the one or more other local patterns being obtained from a different part of the image than from where the local pattern was selected which was made a standard pattern candidate and being equal in size to said standard pattern candidate;

(d) repeating said steps (b) and (c) for said stored image to generate one or more additional standard pattern candidates and to obtain a number of matching errors for each of the one or more additional local pattern candidates; and

(e) selecting the standard pattern from the standard pattern candidates based upon which of the standard pattern candidates has a largest value of minimum matching errors obtained for each standard pattern candidate.

6. A method of production of a standard pattern comprising the steps:

inputting an image of an object and storing the image;

successively selecting and storing in a memory a plurality of local patterns equal in size to a standard pattern to be produced from said stored image and making each local pattern a standard pattern candidate;

obtaining a value of minimum matching errors between each of said standard pattern candidates and each of one or more additional local patterns, each of the one or more additional local patterns being obtained from a different part of the image than from where the local patterns were selected, and being equal in size to said standard pattern candidates from within said image;

selecting the standard pattern from the standard pattern candidates based upon which of the standard pattern candidates has a largest value of minimum matching errors obtained for each standard pattern candidate;

the plurality of said standard pattern candidates being selected from a plurality of local patterns successively selected from the stored image screened by a judgement that said standard pattern candidates are appropriate as a standard pattern based on data in only said local patterns from which said standard pattern candidates are made; and

wherein said appropriateness of each of said standard pattern candidates is determined by whether or not a distribution of standard pattern detail in picture elements constituting said standard pattern is most closely in conformity with a predetermined distribution of pattern detail.

7. A method of producing a standard pattern as claimed in claim 6, wherein the image is in the form of binary values and said appropriateness of said standard pattern candidates is determined by whether or not the number of picture elements having predetermined values among picture elements constituting said plurality of local patterns successively selected and stored in the memory is within a predetermined range.

8. A method of producing a standard pattern as claimed in claim 6, wherein said appropriateness of said standard pattern candidates is determined by whether or not boundary lines in directions perpendicular to each other exist in said standard pattern candidates.

9. A method of producing a standard pattern as claimed in claim 6, wherein said appropriateness of said pattern candidates is determined by obtaining a number of unit patterns in which four picture elements have a same value among unit payttersn having a 2×

2 matrix of picture elements in said standard pattern candidates, and being determined by whether the number of unit patterns in which four picture elements have a same value is within a predetermined range.