Image processing method and apparatus

• US 6,658,148 B1
• Filed: 06/06/2000
• Issued: 12/02/2003
• Est. Priority Date: 06/06/2000
• Status: Expired due to Fees

• Current Assignee: Panasonic Electric Works Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Works Ltd (Panasonic Holdings Corporation)
• Inventors: Fung, Peter, Nishijima, Jun, Yabuta, Akira, Kadowaki, Nobuaki, Ikeda, Kazutaka
• Primary Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/588,416
• Time in Patent Office: 1,274 Days
• Field of Search: 382/103, 382/181, 382/209, 382/218, 382/219, 382/232, 382/233, 382/235, 382/239, 382/240, 382/243, 382/278, 382/305, 382/217, 348/169, 348/384.1, 348/387.1, 348/390.1, 358/426.01, 375/240, 375/240.02, 375/240.08, 375/240.11
• US Class Current: 382/209
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

An image processing method and apparatus for detecting pattern matching between an input mage and a template image at high speed by reducing memory access times. The image processing apparatus includes a first memory for storing a reference pattern as a template, a second memory for storing an input image for which pattern matching with the template is to be detected, means for compressing the template from the first memory and the input image from the second memory by a predetermined compression ratio, a compressed data memory for storing the compressed input image and the compressed template from the compressing means, a main processor for computing inter-correlation between the compressed input image and the compressed template by scanning the compressed input image for each sub-block thereof and determining a location of the compressed input mage showing a best match in a current pattern matching mode. The current pattern matching mode is one of several matching modes with different degrees of compression ratio involved in the compression means and the inter-correlation is determined through two or more pattern matching modes in the order from higher compression ratio to lower compression ratio.

Claims

1. An image processing apparatus for detecting pattern matching between an input image and a template image, comprising:

a first memory for storing a reference pattern as a template;

a second memory for storing an input image for which pattern matching with the template is to be detected;

means for compressing both the template from the first memory and the input image from the second memory by a same predetermined compression ratio;

a compressed data memory for storing the compressed input image and the compressed template from the compressing means; and

a main processor for computing inter-correlation between averaged pixel values of the compressed input image and that of the compressed template by scanning the compressed input image for each sub-block thereof and determining a location of the compressed input image showing a best match in a current pattern matching mode;

wherein the current pattern matching mode is one of plural matching modes with different degrees of compression ratio involved in the compression means and the inter-correlation is determined through two or more pattern matching modes in the order from higher compression ratio to lower compression ratio, and

wherein a pixel size of the input image from the second memory is gradually increased to properly contain the best match location when it is compressed by the different degrees of compression ratio.

2. An image processing apparatus as defined in claim 1, wherein the plural pattern matching modes include at least three modes having a coarse mode corresponding to the higher compression ratio, a fine mode corresponding to the lower compression ratio, and a mode involving no compression.

3. An image processing apparatus as defined in claim 1, wherein the input image stored in the second memory has a larger number of pixels than that of the template stored in the first memory.

4. An image processing apparatus as defined in claim 1, wherein the pattern matching modes further include a rotation mode wherein either the input image or the template is rotated in a predetermined angle for determining the inter-correlation between the input image and the template by the main processor.

5. An image processing apparatus as defined in claim 1, wherein the pattern matching modes further include a sub-pixel mode wherein the input image sub-block is shifted by one pixel in at least one of left, right, up and down directions for determining sub-pixel adjustment values by using the inter-correlation between the input image sub-block and the template by the main processor.

6. An image processing apparatus as defined in claim 1, wherein each of the first and second memories is configured by a plurality of memory banks for transferring pixel data to the compression means in a parallel fashion or an interleave fashion, thereby increasing an overall data transfer speed.

7. An image processing method for detecting pattern matching between an input image and a template image, comprising the following steps of:

storing a reference pattern in a first memory as a template

storing an input image for which pattern matching with the template is to be detected in a second memory;

compressing both the template from the first memory and the input image from the second memory by a same predetermined compression ratio;

storing the compressed input image and the compressed template from the compressing means in a compressed data memory; and

computing inter-correlation between averaged ixel values of the compressed input image and that of the compressed template by scanning the compressed input image for each sub-block thereof and determining a location of the compressed input image showing a best match in a current pattern matching mode;

wherein the current pattern matching mode is one of plural matching modes with different degrees of compression ratio involved in the compression means and the inter-correlation is determined through two or more pattern matching modes in the order from higher compression ratio to lower compression ratio; and

wherein a pixel size of the input image from the second memory is gradually increased to properly contain the best match location when it is compressed by the different degrees of compression ratio.

8. An image processing method as defined in claim 7, wherein the step of computing the inter-correlation between the input image and the template includes a step of computing summation and self-correlation of the template and summation and self-correlation of the input image sub-block.

9. An image processing method as defined in claim 7, wherein the plural pattern matching modes include at least three modes having a coarse mode corresponding to the higher compression ratio, a fine mode corresponding to the lower compression ratio, and a mode involving no compression.

10. An image processing method as defined in claim 7, wherein the input image stored in the second memory has a larger number of pixels than that of the template stored in the first memory.

11. An image processing method as defined in claim 7, wherein the pattern matching modes further include a rotation mode wherein either the input image or the template is rotated in a predetermined angle for determining the inter-correlation between the input image and the template by the main processor.

12. An image processing method as defined in claim 7, wherein the pattern matching modes further include a sub-pixel mode wherein the input image sub-block is shifted by one pixel in at least one of left, right, up and down directions for determining sub-pixel adjustment values by using the inter-correlation between the input image sub-block and the template by the main processor.

13. An image processing method as defined in claim 7, wherein each of the first and second memories is configured by a plurality of memory banks for transferring pixel data to the compression means in a parallel fashion or an interleave fashion, thereby increasing an overall data transfer speed.