Pattern searching method using neural networks and correlation

• US 5,995,652 A
• Filed: 08/13/1997
• Issued: 11/30/1999
• Est. Priority Date: 01/23/1995
• Status: Expired due to Fees

• 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: Oki, Toru, Paolella, Philip, Chiu, Chinchuan
• Primary Examiner(s): Chang, Jon
• Assistant Examiner(s): Patel, Jayanti K.
• Application Number:
  US08/910,265
• Time in Patent Office: 839 Days
• Field of Search: 382/155, 382/156, 382/158, 382/159, 382/209, 382/278, 382/181, 382/195, 382/218, 382/228, 382/276, 382/279, 382/282, 382/294, 349/17, 364/148.03, 706/15
• 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, without examining the content of said image;

processing each sub-image 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 a third set of sub-images, each having one of said candidate patterns at an approximate center thereof;

processing said third set of sub-images with a neural network to produce a fourth set of sub-images, each having one of said candidate patterns at an approximate center thereof; and

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

2. The method of claim 1, wherein the centering of said third and fourth sets of sub-images is determined by examining 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 approximate center of one of said candidate patterns in each of said third set of sub-images and defining each of said fourth set of sub-images such that said approximate center of said candidate pattern is the approximate center of each of said fourth set of sub-images.

4. An apparatus for locating a target pattern in an image, comprising:

means for dividing said image into a first plurality of sub-images, without examining the content of said image;

means for processing each sub-image 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;

means for generating a third set of sub-images, each having one of said candidate patterns at an approximate center thereof;

means for processing said third set of sub-images with a neural network to produce a fourth set of sub-images, each having one of said candidate patterns at an approximate center thereof; and

means for processing said fourth set of sub-images with a correlator to determine which of said fourth set of sub-images contains said target pattern.

5. The apparatus of claim 4, wherein said means for processing said third set of sub-images is further a means for examining which output unit of said neural network has the largest output value.

6. The apparatus of claim 4, wherein said means for processing said third set of sub-images is further a means for finding an approximate center of one of said candidate patterns in each of said third set of sub-images and for defining each of said fourth set of sub-images such that said approximate center of said candidate pattern is the approximate center of each of said fourth set of sub-images.

7. An apparatus that locates a target pattern in an image, comprising:

a circuit configured to divide said image into a first plurality of sub-images, without examining the content of said image;

a neural network configured to process each sub-image to select therefrom a second set of sub-images, each of which includes at least a portion of a candidate pattern;

a circuit configured to generate a third set of sub-images, each having one of said candidate patterns at an approximate center thereof;

a neural network configured to process said third set of sub-images to produce a fourth set of sub-images, each having one of said candidate patterns at an approximate center thereof; and

a correlator configured to process said fourth set of sub-images to determine which of said fourth set of sub-images contains said target pattern.

8. The apparatus of claim 7, wherein said neural network configured to process said third set of sub-images is further configured to examine which output unit of said neural network has the largest output value.

9. The apparatus of claim 7, wherein said neural network configured to process said third set of sub-images is further configured to find an approximate center of one of said candidate patterns in each of said third set of sub-images and configured to define each of said fourth set of sub-images such that said approximate center of said candidate pattern is the approximate center of each of said fourth set of sub-images.