System and method for efficiently performing a pattern matching procedure

• US 7,634,139 B2
• Filed: 03/16/2004
• Issued: 12/15/2009
• Est. Priority Date: 03/16/2004
• Status: Expired due to Fees

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Du, Robert, Yang, Chinping
• Primary Examiner(s): PERUNGAVOOR, SATHYANARAYA V
• Application Number:
  US10/802,088
• Publication Number:
  US 20050207651A1
• Time in Patent Office: 2,100 Days
• Field of Search: 382/209
• US Class Current: 382/209
• CPC Class Codes: G06V 10/431 Frequency domain transformation; Autocorrelation
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Abstract

A system and method for efficiently performing a pattern matching procedure includes an enrollment manager that performs an image conversion procedure for converting an initial reference image into a reference template. The image conversion procedure may include at least one of a binarization procedure and a symmetrical reduction procedure to more efficiently utilize system resources such as processing requirements and memory requirements. A verification manager may then convert an initial test image into a transformed test image for combining with the foregoing reference template to produce a correlation image. The verification manager then analyzes matching characteristics of the correlation image to determine whether the initial test image matches the initial reference image.

Claims

1. A system for efficiently performing a pattern matching procedure using an electronic apparatus, comprising:

an enrollment manager that performs an image conversion procedure for converting an initial reference image into a reference template, said image conversion procedure including a binarization procedure and a symmetrical reduction procedure, said binarization procedure converting a non-binary complex number format into a binary number format; and

a verification manager that converts an initial test image into a transformed test image, said verification manager then combining said reference template and said transformed test image into a correlation image, said verification manager analyzing matching characteristics of said correlation image to determine whether said initial test image matches said initial reference image, said enrollment manager performing a first binarization step to create initial binarization values for said binarization procedure by substituting a decimal value of “

1”

for all complex coefficients from said initial reference image that are greater than or equal to zero, said enrollment manager also substituting a decimal value of “

−

1”

for all of said complex coefficients that are less than zero, said initial binarization values then being utilized for any further calculations during said pattern matching procedure, said enrollment manager performing a second binarization step to create stored binarization values for said binarization procedure by substituting a binary value of “

1”

for all of said complex coefficients from said initial binarization values that are equal to “

−

1”

, and by also substituting a binary value of “

0”

for all of said complex coefficients from said initial binarization values that are equal to “

1”

, said complex coefficients thus each being expressed with a single binary bit, said stored binarization values subsequently being converted into said initial binarization values for performing any required mathematical calculations.

2. A system for efficiently performing a pattern matching procedure using an electronic apparatus, comprising:

an enrollment manager that performs an image conversion procedure for converting an initial reference image into a reference template, said image conversion procedure including a binarization procedure and a symmetrical reduction procedure, said binarization procedure converting a non-binary complex number format into a binary number format; and

a verification manager that converts an initial test image into a transformed test image, said verification manager then combining said reference template and said transformed test image into a correlation image, said verification manager analyzing matching characteristics of said correlation image to determine whether said initial test image matches said initial reference image, said verification manager creating said correlation image by performing a multiplication procedure that multiplies corresponding pixel values from said reference template and said transformed test image to produce correlation pixel values for said correlation image, said correlation pixel values being obtained from a multiplication lookup table to conserve system resources such as processing requirements and memory requirements.

3. The system of claim 2 wherein said multiplication lookup table is implemented with initial binarization values from said binarization procedure, each complex value from said reference template and said transformed test image being expressed with one of only four complex numbers, said four complex numbers being “

1+j”

, “

1−

j”

, “

−

1+j”

, and “

−

1−

j”

, said multiplication lookup table including a vertical reference-pixel index column having a first reference pixel value (1+j), a second reference pixel value (1−

j), a third reference pixel value (−

1+j), and a fourth reference pixel value (−

1−

j), said multiplication lookup table also including a horizontal test-pixel index row having a first test pixel value (1+j), a second test pixel value (1−

j), a third test pixel value (−

1+j), and a fourth test pixel value (−

1−

j).

4. A system for efficiently performing a pattern matching procedure using an electronic apparatus, comprising:

an enrollment manager that performs an image conversion procedure for converting an initial reference image into a reference template, said image conversion procedure including a binarization procedure and a symmetrical reduction procedure, said binarization procedure converting a non-binary complex number format into a binary number format; and

a verification manager that converts an initial test image into a transformed test image, said verification manager then combining said reference template and said transformed test image into a correlation image, said verification manager analyzing matching characteristics of said correlation image to determine whether said initial test image matches said initial reference image, said enrollment manager performing a discrete symmetrical reduction procedure upon said binarized reference image to produce a reduced reference image which said enrollment manager stores as said reference template.

5. A system for efficiently performing a pattern matching procedure using an electronic apparatus, comprising:

an enrollment manager that performs an image conversion procedure for converting an initial reference image into a reference template, said image conversion procedure including a binarization procedure and a symmetrical reduction procedure, said binarization procedure converting a non-binary complex number format into a binary number format; and

a verification manager that converts an initial test image into a transformed test image, said verification manager then combining said reference template and said transformed test image into a correlation image, said verification manager analyzing matching characteristics of said correlation image to determine whether said initial test image matches said initial reference image, said verification manager converting said initial test image into an FFT test image by performing a single Fast Fourier Transform procedure upon said initial test image, said verification manager performing a two-step binarization procedure upon said FFT test image to produce a binarized test image that is stored with a single binary bit representing each complex pixel value coefficient, said verification manager performing a symmetrical reduction procedure upon said FFT test image to produce and store a reduced test image, said verification manager performing a complex conjugation procedure upon said reference template to produce a conjugated reference image, said complex conjugation procedure converting each pixel value from said reference template into a corresponding complex conjugate value by inverting an arithmetic operation that connects real and imaginary portions of complex values for said each pixel value from said reference template.

6. The system of claim 5 wherein said verification manager performs a multiplication procedure with said conjugated reference image and said reduced test image to produce a reduced correlation image.

7. The system of claim 6 wherein said verification manager performs said multiplication procedure by referencing a multiplication lookup table to index pixel values from said conjugated reference image and said reduced test image to produce corresponding correlation pixel values for said reduced correlation image.

8. The system of claim 6 wherein said verification manager performs a symmetrical regeneration procedure upon said reduced correlation image to produce a full FFT correlation image.

9. The system of claim 8 wherein said verification manager performs an inverse FFT procedure upon said full FFT correlation image to generate a complex correlation image, said verification manager discarding imaginary values from each pixel value of said complex correlation image to produce a real correlation image, said verification manager then performing an FFT shift procedure to generate a correlation graph that represents pixels from said real correlation image.

10. The system of claim 9 wherein said verification manager computes a peak side-lobe ratio from said correlation graph for comparing with a pre-determined correlation threshold to determine whether said initial test image matches said initial reference image, said peak side-lobe ratio being expressed by a formula:

PSR=(Peak Value−

Mean Value)/STD

where said PSR is said peak side-lobe ratio, said Peak Value is a correlation image pixel with a greatest magnitude, said Mean Value is an arithmetical mean value of correlation image pixels in a pre-defined side-lobe area surrounding said Peak Value, and said STD is a standard deviation of said correlation image pixels in said pre-defined side-lobe area.

11. A method for efficiently performing a pattern matching procedure, comprising:

performing an image conversion procedure with an enrollment manager to convert an initial reference image into a reference template, said image conversion procedure including a binarization procedure and a symmetrical reduction procedure, said binarization procedure converting a non-binary complex number format into a binary number format;

converting an initial test image into a transformed test image with a verification manager;

combining said reference template and said transformed test image into a correlation image with said verification manager; and

analyzing matching characteristics of said correlation image with said verification manager to determine whether said initial test image matches said initial reference image, said enrollment manager performing a first binarization step to create initial binarization values for said binarization procedure by substituting a decimal value of “

1”

for all complex coefficients from said initial reference image that are greater than or equal to zero, said enrollment manager also substituting a decimal value of “

−

1”

for all of said complex coefficients that are less than zero, said initial binarization values then being utilized for any further calculations during said pattern matching procedure, said enrollment manager performing a second binarization step to create stored binarization values for said binarization procedure by substituting a binary value of “

1”

for all of said complex coefficients from said initial binarization values that are equal to “

−

1”

, and by also substituting a binary value of “

0”

for all of said complex coefficients from said initial binarization values that are equal to “

1”

, said complex coefficients thus each being expressed with a single binary bit, said stored binarization values subsequently being converted into said initial binarization values for performing any required mathematical calculations.

12. A method for efficiently performing a pattern matching procedure, comprising:

performing an image conversion procedure with an enrollment manager to convert an initial reference image into a reference template, said image conversion procedure including a binarization procedure and a symmetrical reduction procedure, said binarization procedure converting a non-binary complex number format into a binary number format;

converting an initial test image into a transformed test image with a verification manager;

combining said reference template and said transformed test image into a correlation image with said verification manager; and

analyzing matching characteristics of said correlation image with said verification manager to determine whether said initial test image matches said initial reference image, said verification manager creating said correlation image by performing a multiplication procedure that multiplies corresponding pixel values from said reference template and said transformed test image to produce correlation pixel values for said correlation image, said correlation pixel values being obtained from a multiplication lookup table to conserve system resources such as processing requirements and memory requirements.

13. The method of claim 12 wherein said multiplication lookup table is implemented with initial binarization values from said binarization procedure, each complex value from said reference template and said transformed test image being expressed with one of only four complex numbers, said four complex numbers being “

1+j”

, “

1−

j”

, “

−

1+j”

, and “

−

1−

j”

, said multiplication lookup table including a vertical reference-pixel index column having a first reference pixel value (1+j), a second reference pixel value (1−

j), a third reference pixel value (−

1+j), and a fourth reference pixel value (−

1−

j), said multiplication lookup table also including a horizontal test-pixel index row having a first test pixel value (1+j), a second test pixel value (1−

j), a third test pixel value (−

1+j), and a fourth test pixel value (−

1−

j).

14. A method for efficiently performing a pattern matching procedure, comprising:

performing an image conversion procedure with an enrollment manager to convert an initial reference image into a reference template, said image conversion procedure including a binarization procedure and a symmetrical reduction procedure, said binarization procedure converting a non-binary complex number format into a binary number format;

converting an initial test image into a transformed test image with a verification manager;

combining said reference template and said transformed test image into a correlation image with said verification manager; and

analyzing matching characteristics of said correlation image with said verification manager to determine whether said initial test image matches said initial reference image, said enrollment manager performing a discrete symmetrical reduction procedure upon said binarized reference image to produce a reduced reference image which said enrollment manager stores as said reference template.

15. A method for efficiently performing a pattern matching procedure, comprising:

performing an image conversion procedure with an enrollment manager to convert an initial reference image into a reference template, said image conversion procedure including a binarization procedure and a symmetrical reduction procedure, said binarization procedure converting a non-binary complex number format into a binary number format;

converting an initial test image into a transformed test image with a verification manager;

combining said reference template and said transformed test image into a correlation image with said verification manager; and

analyzing matching characteristics of said correlation image with said verification manager to determine whether said initial test image matches said initial reference image, said verification manager converting said initial test image into an FFT test image by performing a single Fast Fourier Transform procedure upon said initial test image, said verification manager performing a two-step binarization procedure upon said FFT test image to produce a binarized test image that is stored with a single binary bit representing each complex pixel value coefficient, said verification manager performing a symmetrical reduction procedure upon said FFT test image to produce and store a reduced test image, said verification manager performing a complex conjugation procedure upon said reference template to produce a conjugated reference image, said complex conjugation procedure converting each pixel value from said reference template into a corresponding complex conjugate value by inverting an arithmetic operation that connects real and imaginary portions of complex values for said each pixel value from said reference template.

16. The method of claim 15 wherein said verification manager performs a multiplication procedure with said conjugated reference image and said reduced test image to produce a reduced correlation image.

17. The method of claim 16 wherein said verification manager performs said multiplication procedure by referencing a multiplication lookup table to index pixel values from said conjugated reference image and said reduced test image to produce corresponding correlation pixel values for said reduced correlation image.

18. The method of claim 16 wherein said verification manager performs a symmetrical regeneration procedure upon said reduced correlation image to produce a full FFT correlation image.

19. The method of claim 18 wherein said verification manager performs an inverse FFT procedure upon said full FFT correlation image to generate a complex correlation image, said verification manager discarding imaginary values from each pixel value of said complex correlation image to produce a real correlation image, said verification manager then performing an FFT shift procedure to generate a correlation graph that represents pixels from said real correlation image.

20. The method of claim 19 wherein said verification manager computes a peak side-lobe ratio from said correlation graph for comparing with a pre-determined correlation threshold to determine whether said initial test image matches said initial reference image, said peak side-lobe ratio being expressed by a formula:

PSR=(Peak Value−

Mean Value)/STD

where said PSR is said peak side-lobe ratio, said Peak Value is a correlation image pixel with a greatest magnitude, said Mean Value is an arithmetical mean value of correlation image pixels in a pre-defined side-lobe area surrounding said Peak Value, and said STD is a standard deviation of said correlation image pixels in said pre-defined side-lobe area.