Pattern searching method using neural networks and correlation

• US 5,696,838 A
• Filed: 01/23/1995
• Issued: 12/09/1997
• Est. Priority Date: 04/27/1993
• Status: Expired due to Term

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Corporation Of America (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Corporation Of America (Sony Group Corp.)
• Inventors: Chiu, Chinchuan, Oki, Toru, Paolella, Philip
• Primary Examiner(s): Couso, Yon J.
• Assistant Examiner(s): Patel, Jayanti K.
• Application Number:
  US08/376,544
• Time in Patent Office: 1,051 Days
• Field of Search: 382/209, 382/216, 382/156, 382/158, 364/413.1, 345/924
• US Class Current: 382/159
• CPC Class Codes: G06V 10/25 Determination of region of interest [ROI] or a volume of interest [VOI]
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A pattern searching method using neural networks and correlation. This method combines the quickness and adaptiveness of neural networks with the accuracy of the mathematical correlation approach. Images are divided into small sub-images which are presented to the trained neural network. Sub-images that may contain the pattern or partial pattern are selected by the neural network. The neural network also provides the approximate location of the pattern, therefore the selected sub-images can be adjusted to contain the complete pattern. Desired patterns can be located by measuring the new sub-images'"'"' correlation values against the reference models in a small area. Experiments show that this superior method is able to find the desired patterns. Moreover, this method is much faster than traditional pattern searching methods which use only correlation.

Claims

1. A method for locating a target pattern in an image, comprising the steps of:

dividing said image into a first plurality of sub-images, said dividing occurring without regard for image content;

processing each of said first plurality of sub-images with a neural network to select therefrom a second set of sub-images each of which includes at least a portion of a candidate pattern;

generating, based on said second set of sub-images, a third set of sub-images, each containing a candidate pattern at an estimated center thereof;

processing each of said third set of sub-images with a neural network to generate a fourth set of sub-images each containing a candidate pattern; and

processing said fourth set of sub-images with a correlator to determine if each of said fourth set of sub-images actually contains said target pattern.

2. The method of claim 1, wherein said generating of said fourth set of sub-images includes finding an estimated center of said candidate pattern based on which output unit of said neural network has the largest output value.

3. The method of claim 1, wherein said step of processing said third set of sub-images includes finding an estimated center of said candidate pattern in each of said third set of sub-images and defining each of said fourth set of sub-images such that said estimated center of said candidate pattern is the approximate center of said sub-image.

4. A method for locating a target pattern in an image, comprising the steps of:

providing a neural network having a first number of output units;

training said neural network to recognize said target pattern and fragments of said target pattern so that a high output from each of said output units represents a corresponding one of said target pattern and target pattern fragments, each said target pattern fragment representing a fragment resulting from shifting said target pattern about a reference image space and thus representing an estimated center of said target pattern as shifted;

generating a binarized version of said image;

dividing said binarized image into a first plurality of sub-images, said dividing occurring without regard for image content;

first processing each of said first plurality of sub-images with said neural network to select therefrom a second set of sub-images each of which includes at least a portion of a candidate pattern;

generating a third set of sub-images, each having a candidate pattern at an estimated center thereof based upon the output unit having largest weighting in said first processing step;

second processing said third set of sub-images with said neural network to select therefrom a fourth set of sub-images each of which includes at least a portion of a candidate pattern;

generating a fifth set of sub-images, each having a candidate pattern at an estimated center thereof based upon the output unit having largest weighting in said second processing step; and

correlating said fifth set of sub-images with a reference model of said target pattern to determine if each of said fifth set of sub-images actually contains said target pattern.

5. A method for locating a target pattern in an image, comprising the steps of:

providing a neural network having a first number of output units;

training said neural network to recognize said target pattern and fragments of said target pattern so that a high output from each of said first number of output units represents a corresponding one of said target pattern and target pattern fragments, each said target pattern fragment representing a fragment resulting from shifting said target pattern about a reference image space and thus representing an approximate center of a shifted target pattern;

generating a binarized version of said image;

geographically dividing said binarized image into a first plurality of sub-images without regard for the content of said image;

first processing each of said first plurality of sub-images with said neural network to select therefrom a second set of sub-images each of which includes at least a portion of a candidate pattern;

generating a third set of sub-images, each having one of said candidate patterns at an approximate center thereof, the centering being based upon the output unit having largest weighting in said first processing step;

second processing said third set of sub-images with said neural network to select therefrom a fourth set of sub-images each of which includes at least a portion of a candidate pattern;

generating a fifth set of sub-images, each having one of said candidate patterns at an approximate center thereof, the centering being based upon the output unit having largest weighting in said second processing step;

correlating said fifth set of sub-images with a reference model of said target pattern to determine if any of said fifth set of sub-images actually contains said target pattern.