Statistic calculating method using a template and corresponding sub-image to determine similarity based on sum of squares thresholding

• US 7,082,224 B2
• Filed: 02/18/2005
• Issued: 07/25/2006
• Est. Priority Date: 12/25/1996
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Yoshida, Syoji, Shibukawa, Shigeru, Hotta, Takashi, Yoda, Haruo, Ikeda, Mitsuji, Nakashima, Keisuke, Katsura, Koyo
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US11/060,400
• Publication Number:
  US 20050147305A1
• Time in Patent Office: 522 Days
• Field of Search: 382/278, 382/270, 382/151, 382/205, 382/209, 382/216, 382/218, 382/276, 382/300, 708/5, 348/129
• US Class Current: 382/278
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

An apparatus for calculating a normalized correlation coefficient used as a similarity evaluation measure by using image data values of pixels in a template image and image data values of pixels in a subimage, included in a search image, corresponding to the template image, has a memory that stores image data values of pixels in the search image and calculating means that calculate a sum of image data values of pixels in the template image and a sum of image data values of pixels in the first rectangular region in the search image or a sum of squares of image data values of pixels in the template image and a sum of squares of image data values of pixels in the first rectangular region in the search image. Normalized correlation coefficient calculating means calculate a normalized correlation coefficient on the basis of the sum of image data values of pixels in the template image and the sum of image data values of pixels in the first rectangular region in the search image, or the sum of squares of image data values of pixels in the template image and the sum of squares of image data values of pixels in the first rectangular region in the search image.

Claims

1. An apparatus for calculating a normalized correlation coefficient used as a similarity evaluation measure by using image data values of pixels in a template image and image data values of pixels in a subimage, included in a search image, corresponding to the template image, comprising:

a memory for storing image data values of pixels in the search image;

sum calculating means for calculating a sum of image data values of pixels in a first rectangular region, defined by a plurality of rows and columns, in the search image by using a sum, obtained prior to the sum of image data values of pixels in the first rectangular region, of image data values of pixels in a second rectangular region having a partial region in common with the first rectangular region, and using a difference between image data values of pixels in a region, included in the first rectangular region, other than the partial region and image data values of pixels in a region, included in the second rectangular region, other than the partial region, the difference being calculated by using a first image data value of a pixel which is adjacent to the uppermost pixel in a first column of the first rectangular region positioned on one side thereof on the upper side of the uppermost pixel, a second image data value of the lowermost pixel in the first column, a third image data value of a pixel which is adjacent to the uppermost pixel in a column, positioned on the opposite side to the first column, of the second rectangular region on the upper side of the uppermost pixel, the third image data value having been read out prior to the sum of image data values of pixels in the first rectangular region, and a fourth image data value of the lowermost pixel in the second column of the second rectangular region; and

normalized correlation coefficient calculating means for calculating a normalized correlation coefficient on the basis of a sum of image data values of pixels in the template image and a sum of image data values of pixels in the first rectangular region in the search image.

2. An apparatus for calculating a normalized correlation coefficient according to claim 1 wherein said sum calculating means, at first, in order to obtain sums of image data values for (I−

M+1) sub-images corresponding to respective starting points (i,

     0)(i=0, 1, . . . , I−

M, where I is the number of pixels in the search image in the row direction, and M is the number of pixels in the template image in the row direction);

calculates a sum of image data values for each area composed of pixels for one column and N rows, the number N being equal to that of rows in the template image, further each area corresponding to a starting point (i,

     0)(I=0, 1, . . . , I−

1);

accumulates M sums of image data values for M areas of pixels for 1 column and N rows, to obtain a sum of image data values for a sub-image corresponding to a starting point (0,

     0) is obtained; and

successively obtains sums of sub-images corresponding to starting points (1,

     0), (2,

     0), . . . , (I−

M,

     0) in turn, by adding a sum of image data values for an area of pixels for one column and N rows to a sum for a previous sub-area and subtracting a sum of image data values for another area of pixels for one column and N rows from the sum for the previous sub-area.

3. An apparatus for calculating a normalized correlation coefficient according to claim 2, wherein, in order to obtain sums of image data values for (I−

M+1) sub-images corresponding to the respective starting points (i,

     1)(i=0, 1, . . . , I−

M, where I is the number of pixels in the search image in the row direction, and M is the number of pixels in the template image in the row direction) said sum calculating means;

calculates a sum of image data values for each area of pixels for one column and N rows, the number N being equal to that of rows in the template image for each area corresponding to a starting point (i,

     1)(I=0, 1, . . . , I−

1) by making use of the already obtained sums of image data values for areas corresponding to starting points (i,

     0)(I=0, 1, . . . , I−

1), and adding an image data value of pixels to a sum for a previous area and subtracting an image data value of another pixel from the previous area;

accumulates the M sums of image data values for M areas, each area being composed of pixels for one column and N rows, to obtain a sum of image data values for a sub-image corresponding to a starting point (0,

     1);

successively obtains sums of sub-images corresponding to starting points (1,

     1), (2,

     1), . . . , (I−

M,

     1) in turn, by adding a sum of image data values for an area of pixels for one column and N rows to a sum for a previous sub-area and subtracting a sum of image data values for another area of pixels for one column and N rows from the sum for the previous sub-area; and

obtains, for J=2, . . . , J−

N, a sum of image data values for each sub-image by making use of previously calculated results for J=1, where J is the number of pixels in the search image in the column direction, and N is the number of pixels in the template image in the column direction.

4. An apparatus for calculating a normalized correlation coefficient according to claim 3 wherein said sum calculating means and said normalized correlation coefficient calculating means are implemented in a programmed general purpose digital computer.

5. An apparatus for calculating a normalized correlation coefficient according to claim 4 wherein said memory is an external memory and further including means to read the image data read out of said external memory, and store the data of the template and search images in an array of type t(m, n)(m=0, 1, 2;

n=0, 1,

     2) and s(i, j)(i=0, 1, . . . , 4;

j=0, 1, . . .

     4), respectively in an internal memory in said computer.

6. An apparatus for calculating a normalized correlation coefficient according to claim 1 wherein said sum calculating means and said normalized correlation coefficient calculating means are implemented in a programmed general purpose digital computer.

7. An apparatus for calculating a normalized correlation coefficient according to claim 6 wherein said memory is an external memory and further including means to read the image data read out of said external memory, and store the data of the template and search images in an array of type t(m, n)(m=0, 1, 2;

n=0, 1,

     2) and s(i, j)(i=0, 1, . . . , 4;

j=0, 1, . . .

     4), respectively in an internal memory in said computer.

8. An apparatus for calculating a normalized correlation coefficient used as a similarity evaluation measure by using image data values of pixels in a template image and image data values of pixels in a subimage, included in a search image, corresponding to the template image, comprising:

a memory for storing image data values of pixels in the search image;

a sum-of-squares calculating means for calculating a sum of squares of image data values of pixels in a first rectangular region, defined by a plurality of rows and columns, in the search image by using a sum, obtained prior to the sum of squares of image data values of pixels in the first rectangular region, of image data values of pixels in a second rectangular region having a partial region in common with the first rectangular region, and using a difference between image data values of pixels in a region, included in the first rectangular region, other than the partial region and image data values of pixels in a region, included in the second rectangular region, other than the partial region, the difference being calculated by using a first image data value of a pixel which is adjacent to the uppermost pixel in a first column of the first rectangular region positioned on one side thereof on the upper side of the uppermost pixel, a second image data value of the lowermost pixel in the first column, a third image data value of a pixel which is adjacent to the uppermost pixel in a column, positioned on the opposite side to the first column, of the second rectangular region on the upper side of the uppermost pixel, the third image data value having been read out prior to the sum of squares of image data values of pixels in the first rectangular region, and a fourth image data value of the lowermost pixel in the second column of the second rectangular region; and

normalized correlation coefficient calculating means for calculating a normalized correlation coefficient on the basis of a sum of squares of image data values of pixels in the template image and a sum of squares of image data values of pixels in the first rectangular region in the search image.

9. An apparatus for calculating a normalized correlation coefficient according to claim 8 wherein said sum of squares calculating means, at first, in order to obtain sums of squares of image data values for (I−

M+1) sub-images corresponding to respective starting points (i,

     0)(i=0, 1, . . . , I−

M, where I is the number of pixels in the search image in the row direction, and M is the number of pixels in the template image in the row direction);

calculates a sum of squares of image data values for each area composed of pixels for one column and N rows, the number N being equal to that of rows in the template image, further each area corresponding to a starting point (i,

     0)(I=0, 1, . . . , I−

1);

accumulates M sums of squares of image data values for M areas of pixels for 1 column and N rows, to obtain a sum of squares of image data values for a sub-image corresponding to a starting point (0,

     0) is obtained; and

successively obtains sums of squares of sub-images corresponding to starting points (1,

     0), (2,

     0), . . . , (I−

M,

     0) in turn, by adding image data values for an area of pixels for one column and N rows to a sum of squares for a previous sub-area and subtracting a sum of squares of image data values for another area of pixels for one column and N rows from the sum of squares for the previous sub-area.

10. An apparatus for calculating a normalized correlation coefficient according to claim 9, wherein, in order to obtain sums of squares of image data values for (I−

M+1) sub-images corresponding to the respective starting points (i,

     1)(i=0, 1, . . . , I−

M, where I is the number of pixels in the search image in the row direction, and M is the number of pixels in the template image in the row direction) said sum of squares calculating means;

calculates a sum of squares of image data values for each area of pixels for one column and N rows, the number N being equal to that of rows in the template image for each area corresponding to a starting point (i,

     1)(I=0, 1, . . . , I−

1) by making use of the already obtained sums of squares of image data values for areas corresponding to starting points (i,

     0)(I=0, 1, . . . , I−

1), and adding an image data value of pixels to a sum of squares for a previous area and subtracting an image data value of another pixel from the previous area;

accumulates the M sums of squares of image data values for M areas, each area being composed of pixels for one column and N rows, to obtain a sum of squares of image data values for a sub-image corresponding to a starting point (0,

     1);

successively obtains sums of squares of sub-images corresponding to starting points (1,

     1), (2,

     1), . . . , (I−

M,

     1) in turn, by adding a sum of squares of image data values for an area of pixels for one column and N rows to a sum of squares for a previous sub-area and subtracting a sum of squares of image data values for another area of pixels for one column and N rows from the sum of squares for the previous sub-area; and

obtains, for J=2, . . . , J−

N, a sum of squares of image data values for each sub-image by making use of previously calculated results for J=1, where J is the number of pixels in the search image in the column direction, and N is the number of pixels in the template image in the column direction.

11. An apparatus for calculating a normalized correlation coefficient according to claim 10 wherein said sum of squares calculating means and said normalized correlation coefficient calculating means are implemented in a programmed general purpose digital computer.

12. An apparatus for calculating a normalized correlation coefficient according to claim 11 wherein said memory is an external memory and further including means to read the image data read out of said external memory, and store the data of the template and search images in an array of type t(m, n)(m=0, 1, 2;

n=0, 1,

     2) and s(i, j)(i=0, 1, . . . , 4;

j=0, 1, . . .

     4), respectively in an internal memory in said computer.

13. An apparatus for calculating a normalized correlation coefficient according to claim 8 wherein said sum of squares calculating means and said normalized correlation coefficient calculating means are implemented in a programmed general purpose digital computer.

14. An apparatus for calculating a normalized correlation coefficient according to claim 13 wherein said memory is an external memory and further including means to read the image data read out of said external memory, and store the data of the template and search images in an array of type t(m, n)(m=0, 1, 2;

n=0, 1,

     2) and s(i, j)(i=0, 1, . . . , 4;

j=0, 1, . . .

     4), respectively in an internal memory in said computer.