Pattern matching method and apparatus

• US 4,805,224 A
• Filed: 02/27/1987
• Issued: 02/14/1989
• Est. Priority Date: 06/08/1983
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Koezuka, Tetsuo, Nakashima, Masato, Tsukahara, Hiroyuki
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/020,201
• Time in Patent Office: 718 Days
• Field of Search: 358/101, 358/106, 358/107, 382/8, 382/14, 382/30, 382/34, 382/42, 382/48
• US Class Current: 382/141
• CPC Class Codes: G06F 18/211 Selection of the most significant subset of features
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching
• CPC Class Codes: G06V 10/772 Determining representative reference patterns, e.g. averaging or distorting patterns; Generating dictionaries
• CPC Class Codes: Y02E 60/10 Energy storage using batteries

Abstract

Disclosed is a pattern matching method and apparatus, in which an object pattern is collated with a master pattern using pattern matching. As a first step, an area corresponding to a master pattern size is sequentially extracted from a master sample image for forming the master pattern, each extracted pattern is collated and the other patterns in the master sample image. An extracted pattern which has a minimum similarity to all the other patterns, and, as a result, shows the most distinctive pattern, is used for the master pattern. Using the present method and apparatus, pattern matching having a higher recognition rate can be performed. Further, using the present pattern matching method, an apparatus can be obtained for positioning the object to be recognized with a highest positioning accuracy.

Claims

1. A pattern matching method, comprising the steps of:

(a) sequentially extracting patterns from an image to produce extracted patterns each having an area with an extraction pattern size, comprising the substeps of;

(ai) picking a master sample image for forming a master pattern; and

(aii) sequentially extracting the extracted patterns with the extraction pattern size beginning with an initial pattern in the master sample image;

(b) mutually comparing each of the extracted patterns with all other patterns in the image, comprising the substeps of;

(bi) comparing each of the extracted patterns wtih all other patterns in the master sample image;

(bii) calculating pattern matching degrees between each of the extracted patterns and all the other patterns in the master sample image;

(biii) determining a similar matching degree of each of the extracted patterns, the similar matching degree being a maximum of the pattern matching degrees between each of the extracted patterns and all the other patterns;

(biv) calculating a waveform of the pattern matching degrees;

(bv) differentiating the waveform of the pattern matching degrees to form a second order differential waveform; and

(bvi) measuring an interval length between peaks of the second order differential waveform;

(c) registering one of the extracted patterns having the similar matching degree which is a minimum, as a master pattern, when the interval length is within a predetermined range; and

(d) identifying an object pattern by a pattern matching procedure between the image including the object pattern and the master pattern.

2. A pattern matching apparatus, comprising:

an image pickup system for picking up an analog image of a sample placed on a sample feed mechanism;

an analog to digital converter circuit, operatively connected to said image pickup system, for converting the analog image from the image pickup system into a digital signal;

an object pattern memory, operatively connected to said analog to digital converter circuit, for receiving the digital signal from the analog to digital converter circuit and for storing a master pattern image including pattern signals;

a master pattern forming circuit, operatively connected to said object pattern memory, comprising distinctive pattern detection means for detecting and outputting from the object pattern memory extracted pattern portions, each having an area, the extracted pattern portions including a most distinctive pattern portion, said distinctive pattern detection means comprising;

an extraction circuit, operatively connected to said object pattern memory, for sequentially extracting an extracted pattern signal with a master pattern size from said object pattern memory;

a pattern matching control circuit, operatively connected to said extraction circuit, for outputting a signal controlling calculation of pattern matching degree between the extracted pattern signal and all other of the pattern signals in said object pattern memory;

a similar pattern detection circuit for detecting a first rank similar pattern and a similar matching degree of extracted patterns, comprising a master pattern determination circuit for detecting the first rank similar pattern having the similar matching degree which is a minimum, and for detecting an extraction pattern corresponding to the first rank similar pattern, as a master pattern;

second order differential means, operatively connected to said similar pattern detection circuit, for calculating a second order differential waveform from a waveform of the pattern matching degree which is calculated for a scanning position and the pattern matching degree corresponding thereto; and

peak interval decision means, operatively connected to said second order differential means, for measuring a peak interval length of the second order differential waveform, for comparing the peak interval length with a predetermined value and for deciding based on the comparing;

a master pattern memory, operatively connected to said extraction circuit, for initially storing one of the extracted pattern portions as a temporary master pattern and for finally storing the most distinctive pattern portion; and

a pattern matching circuit, operatively connected to said object pattern memory, said pattern matching control circuit, said similar pattern detection circuit, said second order differential means and said master pattern memory, for scanning each of the extracted patterns output from said master pattern forming circuit.

3. A pattern matching apparatus as set forth in claim 2, wherein said master pattern forming circuit further comprises a circuit, operatively connected to said extraction circuit and said similar pattern detection circuit, for sequentially changing an extracting pattern size and for calculating the pattern matching degree for the extraction pattern having the extracting pattern size.

4. A pattern matching apparatus, comprising:

an image pickup system for picking up an analog image of a sample placed on a sample feed mechanism;

an analog to digital converter circuit, operatively connected to said image pickup system, for converting the analog image from the image pickup system into a digital signal;

an object pattern memory, operatively connected to said analog to digital converter circuit, for receiving the digital signal from the analog to digital converter circuit;

a master pattern forming circuit, operatively connected to said object pattern memory, comprising distinctive pattern detection means for detecting and outputting from the object pattern memory extracted pattern portions, each having an area, the extracted pattern portions including a most distinctive pattern portion, said distinctive pattern detection means comprising;

pattern matching degree means for generating a pattern matching degree waveform;

second order differential means, operatively connected to said pattern matching degree means, for calculating a second order differential of the pattern matching degree waveform; and

peak interval decision means, operatively connected to said second order differential means, for measuring a peak interval length of the second order differential of the pattern matching degree waveform and for comparing the peak interval length with a predetermined value to select the most distinctive pattern portion;

a master pattern memory, operatively connected to said master pattern forming circuit and said extraction circuit, for initially storing one of the extracted pattern portions as a temporary master pattern and for finally storing the most distinctive pattern portion; and

a pattern matching circuit, operatively connected to said object pattern memory, said pattern matching degree means, said second order differential means and said master pattern memory, for scanning each of the extracted patterns output from said mater pattern forming circuit.

5. A master pattern selection method for selecting a master pattern from a digital image of a master sample, comprising the steps of:

(a) extracting a first portion of the digital image, the first portion being an array of elements, the array having at least one dimension and the first portion having an extraction size;

(b) determining similarity between the first portion and a second portion of the digital image having the extraction size by comparing each element of the first portion with a corresponding element in the second portion, comprising the sub steps of;

(bi) calculating a waveform of pattern matching degree between the first and second portions of the digital image;

(bii) differentiating the waveform to form a second order differential waveform having peaks; and

(biii) measuring an interval length between the peaks of the second order differential waveform;

(c) repeating step (b) relacing the second portion with all other portions of the digital image having the extraction size to determine a maximum similarity degree for the first portion;

(d) repeating steps (a) through (c), replacing the first portion with each of the second and other portions of the digital image having the extraction size; and

(e) selecting a master pattern from among the first, second and other portions of the digital image having the extraction size based on the interval length being in a predetermined range and the maximum similarity degree being smaller than a predetermined value.

6. A pattern matching apparatus, comprising:

sample input means for inputting a sample image;

memory means, operatively connected to said sample image means, for storing the sample image and a master pattern; and

pattern matching means, operatively connected to said memory means, for extracting an extracted pattern, having an area with an extracted pattern size, from the sample image, for scanning the extracted pattern and other patterns in the sample image to compare the extracted and other patterns, for determining a maximum similarity degree for the extracted pattern and for selecting one of the patterns as the master pattern based on the maximum similarity degree, said pattern matching means comprising;

a pattern matching circuit, operatively connected to said memory means, for comparing the extracted pattern and the other patterns and for generating a waveform of similarity degree; and

master pattern forming means, operatively connected to said memory means and said pattern matching circuit, for forming a master pattern, said master pattern forming means comprising;

an extraction circuit, operatively connected to said memory means, for extracting the extracted pattern;

a pattern matching control circuit, operatively connected to said extraction circuit and said pattern matching circuit, for controlling the comparing in said pattern matching circuit;

a similar pattern detection circuit, operatively connected to said pattern matching circuit, for detecting the master pattern in dependence upon the maximum similarity degree;

a second order differential circuit, operatively connected to said pattern matching circuit and said similar pattern detection circuit, for calculating a second order differential waveform having peaks from the waveform of similarity degree; and

a peak interval checking circuit, operatively connected to said second order differential circuit, for measuring an interval length between the peaks of the second order differential waveform.

7. A pattern matching apparatus, comprising:

sample input means for inputting a sample image;

a frame memory for storing the sample image;

a frame memory controller, operatively connected to said frame memory and said sample input means, for controlling access to said frame memory;

a master pattern memory for storing a master pattern;

a master pattern memory controller, operatively connected to said master pattern memory and said frame memory controller, for accessing said master pattern memory; and

pattern matching means, operatively connected to said memory means, for extracting an extracted pattern, having an area with an extracted pattern size, from the sample image, for scanning the extracted pattern and other patterns in the sample image to compare the extracted and other patterns, for determining a maximum similarity degree for the extracted pattern and for selecting one of the patterns as the master pattern based on the maximum similarity degree, said pattern matching means comprising;

a first shift register operatively connected to said frame memory controller;

a second shift register operatively connected to said master pattern memory controller;

a third shift register operatively connected to said first shift register;

a fourth shift register operatively connected to said second shift register;

a first exclusive NOR gate operatively connected to said third and fourth shift registers;

a fifth shift register operatively connected to said third shift register;

a sixth shift register operatively connected to said fourth shift register;

a second exclusive NOR gate operatively connected to said fifth and sixth shift registers

a first adder operatively connected to said first and second exclusive NOR gates;

a second adder operatively connected to said first adder;

a data register operatively connected to said second adder;

a data memory operatively connected to said data register;

a data memory controller operatively connected to said data register and said data memory; and

master pattern forming means, operatively connected to said memory means and said pattern matching circuit, for forming a master pattern, said master pattern forming means comprising;

an extraction circuit, operatively connected to said frame and master pattern memory controllers, for extracting the extracted pattern;

a pattern matching control circuit, operatively connected to said extraction circuit and said first through sixth shift registers, said first and second adders and said data memory controller, for controlling the comparing in said pattern matching; and

a similar pattern detection circuit, operatively connected to said pattern matching circuit, for detecting the master pattern in dependence upon the maximum similarity degree.

8. A pattern matching method, comprising the steps of:

(a) picking up a master sample image from a master sample to form a master pattern;

(b) sequentially extracting patterns with an extraction pattern size from the master sample image to produce extracted patterns;

(c) scanning each of the extracted patterns;

(d) calculating pattern matching degrees between each of the extracted patterns and all remaining patterns in the master sample image in dependence upon said scanning in step (c);

(e) determining a similar matching degree for each of the extracted patterns, the similar matching degree being a maximum of the pattern matching degrees between each of the extracted patterns and all remaining patterns in the master sample image;

(f) registering one of the extracted patterns as the master pattern, the master pattern having the similar matching degree which is the smallest among all of the extracted patterns, only if the interval length corresponding to the one of the extracted patterns is shorter than a predetermined value;

(g) identifying an object pattern by a pattern matching procedure between the master pattern and an image containing the object pattern;

(h) sequentially storing the pattern matching degrees for corresponding scanning positions and obtaining a matching degree curve;

(i) calculating a second order differential of the matching degree curve; and

(j) measuring an interval length between two peaks of the second order differential of the matching degree curve.

9. A pattern matching apparatus, comprising:

an image pick up system for picking up an analog image of a sample placed on a sample feed mechanism and for producing an analog pick up signal;

an analog to digital converter circuit, operatively connected to said image pick up system, for converting the analog pickup signal from the image pickup system into a digital pickup signal;

an object pattern memory, operatively connected to said analog to digital converter circuit, for storing the digital pickup signal output by the analog to digital converter circuit;

a master pattern forming circuit, operatively connected to said object pattern memory, comprising a distinctive pattern detection circuit for detecting a most distinctive pattern portion, said distinctive pattern detection circuit comprising;

an extraction circuit, operatively connected to said object pattern memory, for sequentially extracting a pattern signal with a master pattern size from said object pattern memory when said object pattern memory includes a master pattern image;

a pattern matching control circuit, operatively connected to said extraction circuit, for controlling calculation of a pattern matching degree between the pattern signal extracted by said extraction circuit and other pattern signals stored in said object pattern memory; and

a similar pattern detection circuit, for detecting a first rank similar pattern and a similar matching degree of extracted patterns, said similar pattern detection circuit comprising a master pattern determination circuit for detecting the first rank similar pattern having the similar matching degree which is smallest among the pattern signals stored in said object pattern memory, and for determining an extraction pattern corresponding to the first rank similar pattern, as a master pattern;

a master pattern memory, operatively connected to said extraction circuit and said similar pattern detection circuit, for initially storing a temporary master pattern and for finally storing the most distinctive pattern portion;

a pattern matching circuit operatively connected to said object pattern memory, said pattern matching control circuit, said similar pattern detection circuit and said master pattern memory, for calculating the pattern matching degree under control of said pattern matching control circuit;

means for sequentially storing the pattern matching degree corresponding to each scanning position and for obtaining a matching degree curve;

second order differential means for calculating a second order differential of the matching degree curve;

peak interval checking means for measuring an interval length between two peaks of the second order differential of the matching degree curve; and

limiting means for limiting a selection range of the master pattern in said master pattern determination circuit to extracted patterns having an interval length shorter than a predetermined value.