Template matching image processor utilizing sub image pixel sums and sum of squares thresholding

• US 6,249,608 B1
• Filed: 12/19/1997
• Issued: 06/19/2001
• Est. Priority Date: 12/25/1996
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Hotta, Takashi, Yoda, Haruo, Ikeda, Mitsuji, Nakashima, Keisuke, Katsura, Koyo, Yoshida, Syoji, Shibukawa, Shigeru
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): MILLER, MARTIN E
• Application Number:
  US08/994,096
• Time in Patent Office: 1,278 Days
• Field of Search: 382/209, 382/205, 382/270, 382/272, 382/304
• US Class Current: 382/209
• 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 image processing apparatus obtains a sum A of image data values of pixels in a template image, a sum B of squares of image data values of pixels in a template image, a sum C of image data values of pixels in a sub-image to be processed, of a search image, a sum D of squares of image data values of pixels in the sub-image of the template image, further obtains a threshold value F in advance by using the obtained values A, B, C and D, the number P of pixels in the template image, and the preset value E. Moreover, the apparatus obtains a square of each difference between an image data value of each pixel in the sub-image and that of a corresponding pixel in the template image, and performs cumulative addition for each obtained squares. If the result of cumulative addition exceeds the above-mentioned threshold value, the apparatus closes processing evaluation of a similarity between the sub-image and the template image. Furthermore, the apparatus recursively obtains a moving-average value of image data values of pixels in a rectangular region to be presently processed, by using a moving-average value for a rectangular region which was previously processed and image data read from a first memory and a second memory, each memory stores image data by one line pixels of the image, which include image data of pertinent pixels in the rectangular regions.

Claims

1. An image processing template matching method, used in a calculation device for performing image processing, for evaluating a similarity between a template image and sub-images, contained within a search image, having a size equal to the size of the template image, based on a normalized correlation coefficient, and determining a sub-image resembling said template image in accordance with results of evaluating a similarity, said method comprising the steps of:

obtaining a sum (A) of image data values of pixels in a template image, a sum (B) of squares of image data values of pixels in said template image, a sum (C) of image data values of pixels in one of said sub-images to be processed, a sum (D) of squares of image data values of pixels in said sub-image;

obtaining a threshold value (F), based on equation 1, $\begin{array}{cc}F=B+D-\frac{2<br><br>A<br><br>\text{\hspace{1em}<br><br>}<br><br>C}{P}-2<br><br>E·<br><br>\sqrt{B-\frac{A^2}{P}}·<br><br>\sqrt{D-\frac{C^2}{P}}& \left(1\right)\end{array}$

where (P) is the number of pixels in said template image, and (E) is a preset positive value of less than 1;

obtaining a square of a difference between an image data value of a pixel in said sub-image to be processes, and an image data value of a corresponding pixel in said template image;

performing cumulative addition for said obtained square; and

repeating the step of obtaining a square and the step of performing cumulative addition;

if a result of said cumulative addition exceeds said threshold value, closing evaluation of a similarity for said sub-image, and, if a result of said cumulative addition for all pixels of said template image does not exceed said threshold value, calculating a similarity value by using said cumulative addition;

determining a matching point in said search image by evaluating all similarity values after all evaluations of sub-images terminate; and

storing said matching point in a memory in said calculation device.

2. An image processing method according to claim 1, wherein a sum, and a sum of squares, of image data values for a sub-image neighboring said sub-image which was processed is obtained by making use of said sum (A), and said sum of squares (B), of image data values for said sub-image which was processed.

3. An image processing method according to claim 1, wherein, if a final result of said cumulative addition for said sub-image is less than said threshold value (F), a normalized correlation coefficient between said sub-image and said template image is obtained and said normalized correlation coefficient is used to replace said value E as a new value.

4. An image processing method, comprising the steps of:

obtaining a sum (A) of image data values of pixels in a template image, a sum (B) of squares of image data values of pixels in said template image, a sum (C) of image data values of pixels in one of said sub-images to be processed, a sum (D) of squares of image data values of pixels in said sub-image;

obtaining a threshold value (F), based on equation 1,$\begin{array}{cc}F=B+D-\frac{2<br><br>A<br><br>\text{\hspace{1em}<br><br>}<br><br>C}{P}-2<br><br>E·<br><br>\sqrt{B-\frac{A^2}{P}}·<br><br>\sqrt{D-\frac{C^2}{P}}& \left(1\right)\end{array}$

where (P) is the number of pixels in said template image, and (E) is a preset positive value of less than 1;

obtaining a sum of squares of differences between respective image data values of pixels in said sub-image to be processed, and image data values of respective corresponding pixels in said template image;

repeating the step of obtaining a threshold value and the step of obtaining a sum of squares for all sub-images of said search image; and

extracting those sub-images, for which a sum of squares of differences between respective image data values of pixels in said sub-image to be processed, and an image data value of respective corresponding pixels in said template image, does not exceed a threshold value for said sub-image.

5. An image processing apparatus, comprising:

a memory for storing image data of a template image and a search image having a plurality of sub-images; and

a processor for;

reading image data of said template image and said search image out of said memory, obtaining a sum (A) of image data values of pixels in a template image, a sum (B) of squares of image data values of pixels in said template image, a sum (C) of image data values of pixels in one of said sub-images to be processed, a sum (D) of squares of image data values of pixels in said sub-image;

obtaining a threshold value (F), based on equation 1,$\begin{array}{cc}F=B+D-\frac{2<br><br>A<br><br>\text{\hspace{1em}<br><br>}<br><br>C}{P}-2<br><br>E·<br><br>\sqrt{B-\frac{A^2}{P}}·<br><br>\sqrt{D-\frac{C^2}{P}}& \left(1\right)\end{array}$

where (P) is the number of pixels in said template image, and (E) is a preset positive value of less than 1,

obtaining a square of a difference between an image data value of a pixel in said sub-image to be processed and an image data value of a corresponding pixel in said template image,

performing cumulative addition for said obtained square,

repeating the step of obtaining a square and the step of performing cumulative addition,

if a result of said cumulative addition exceeds said threshold value, closing evaluation of a similarity for said sub-image, and

if a result of said cumulative addition for all pixels of said template image does not exceed said threshold value calculating a similarity value by using said cumulative addition and evaluating a similarity of said sub-image based on a normalized correlation coefficient.

6. An image processing apparatus, comprising:

a first memory for storing image data of a template image;

a second memory for storing image data of a search image;

a first calculator for reading image data values of pixels in said template image out of said first memory, and obtaining a sum, and a sum of squares, of said image data values of said template image, and for reading image data values of pixels in each sub-image of said search image which has a size equal to that of said template image, out of said second memory, and obtaining a sum, and a sum of squares, of said image data values;

a register for storing said obtained sums, and sums of squares, of said image data values for said template image and said sub-image;

a second calculator for calculating a threshold value used to evaluate a similarity of each sub-image of said search image to said template image, which corresponds to a normalized correlation coefficient between each sub-image of said search image by using said sums, and sums of squares, of said image data values for said template image and said sub-image, and a value set from the outside of said second calculator;

a third calculator for performing cumulative addition to obtain respective squares of differences between respective image data values for each sub-image of said search image and respective corresponding image data values for said template image; and

a comparator for comparing, after each addition, said threshold value obtained by said second calculator with a result of said cumulative addition obtained by said third calculator.

7. An image processing apparatus according to claim 6, wherein said first calculator obtains sums of image data values for a plurality of areas of said search image, each area being composed of pixels for one column and the same row number as that of said template image, and said sum of image data values for each sub-image is obtained by combining said sums of image data values for said plurality of said areas, and said first calculator further obtains sums of squares of image data values for a plurality of areas of said search image, each area being composed of pixels for one column and the same row number as that of said template image, and said sum of squares of image data values for each sub-image is obtained by combining said sums of squares of image data values for said plurality of said areas.

8. An image processing apparatus comprising:

a first memory for storing image data of a template image;

a second memory for storing image data of a search image;

a first calculator for reading image data values of pixels in said template image out of said first memory, and obtaining a sum, and a sum of squares, of said image data values of said template image, and for reading image data values of pixels in each sub-image of said search image which has a size equal to that of said template image, out of said second memory, and obtaining a sum, and a sum of squares, of said image data values;

a register for storing said obtained sums, and sums of squares, of said image data values for said template image and said sub-image;

a second calculator for calculating a threshold value used to evaluate a similarity of each sub-image of said search image to said template image, which corresponds to a normalized correlation coefficient between each sub-image of said search image by using said sums, and sums of squares, of said image data values for said template image and said sub-image, and a value set from the outside of said second calculator;

a third calculator for performing cumulative addition to obtain respective squares of differences between respective image data values for each sub-image of said search image and respective corresponding image data values for said template image; and

a comparator for comparing, in each addition, said threshold value obtained by said second calculator with a result of said cumulative addition obtained by third calculator wherein;

said first calculator,

obtains sums of image data values for a plurality of areas of said search image, each area being composed of pixels for one column and the same row number as that of said template image, the starting points of which are in a first line of said search image in a main scanning direction, and

sums of image data values for a next plurality of areas of said search image, each area being composed of pixels for one column and the same row number as that of said template image, of which staring points are in each of other lines of said search image, by subtracting an image data value of a pixel which exists in each area of said previous plurality of said areas but does not exist in each area of a next plurality of areas of said search image, from a sum of image data values for said area, and

adds an image data value of a pixel which exists in each area of a next plurality of areas of said search image but does not exist in each area of said previous plurality of said areas, to a sum of image data values for said area, and said first calculator,

obtains said sum of image data values for each sub-image by combining said obtained sums of image data values for said plurality of said areas, and said first calculator,

further obtains sums of squares image data values for a plurality of areas of said search image, each area being composed of pixels for one column and the same row number as that of said template image, staring points of which are in said first line, and sums of image data values for a next plurality of areas of said search image, each area being composed of pixels for one column and the same row number as that of said template image, staring points of which are in each of other lines of said search image, by subtracting a square of an image data value of a pixel which exists in each area of said previous plurality of said areas but does not exist in each area of a next plurality of areas of said search image, from a sum of squares image data values for said area, and

adds a square of an image data value of a pixel which exists in each area of a next plurality of area of said search image but does not exist in each area of said previous plurality of said areas, to a sum of square of image data values for said area, and said first calculator,

obtains said sum of squares of image data values for each sub-image by combining said obtained sums of squares of image data values for said plurality of said areas.

9. An image processing apparatus, comprising:

a memory for storing image data of a template image and a search image;

an image processor for;

reading image data of said template image and said search image out of said memory, obtaining a sum (A) of image data values of pixels in a template image, a sum (B) of squares of image data values of pixels in said template image, a sum (C) of image data values of pixels in one of said sub-images to be processed, a sum (D) of squares of image data values of pixels in said sub-image;

obtaining a threshold value (F), based on equation 1,$\begin{array}{cc}F=B+D-\frac{2<br><br>A<br><br>\text{\hspace{1em}<br><br>}<br><br>C}{P}-2<br><br>E·<br><br>\sqrt{B-\frac{A^2}{P}}·<br><br>\sqrt{D-\frac{C^2}{P}}& \left(1\right)\end{array}$

where (P) is the number of pixels in said template image, and (E) is a preset positive value of less than 1,

obtaining a square of a differences between an image data value of a pixel in said sub-image to be processed and an image data value of a corresponding pixel in said template image,

performing cumulative addition for said obtained square,

repeating the step of obtaining a square and the step of performing cumulative addition,

if a result of said cumulative addition exceeds said threshold value, closing evaluation of a similarity for said sub-image, and

if a result of said cumulative addition for all pixels of said template image does not exceed said threshold value, calculating a similarity value by using said cumulative addition, and evaluating a similarity of said sub-image;

a host computer for managing processing executed by said image processor; and

a display device for displaying said template image and said search image for which image data are stored in said memory, and for displaying sub-images having a large degree of correlation with the template images.

10. An image processor, for reading image data of pixels in an image to be processed from an external image memory, and obtaining an average value of image data of pixels in each of a plurality of rectangular regions defined as a plurality of rows and a plurality of columns in said image, in turn in the row direction, said image processor comprising:

memory means for storing image data of pixels for at least one line in the row direction of said image;

control means for controlling access to said memory means so that image data of each pixel is read from or written in the memory means in turn in the row direction, and for controlling access to said external memory so that image data of each pixel is read from said external memory in turn in the row direction, wherein said control means controls image data reading so that image data of each pixel existing in said first designated line of said image, which is stored in said memory means, and image data existing at the same column as that of said pixel in said second designated line part from said first designated line by the width of said rectangular region, which is stored in said external memory, are read out in turn; and

calculation means for obtaining an average value of image data values of pixels in a rectangular region to be presently processed, by using an average value for a rectangular region which was previously processed and image data read from said memory means and said external memory, respectively, wherein said calculation means;

obtains an average value of image data values of pixels in a first rectangular region by using an average value of image data values of pixels in a second rectangular region which was processed previously to said first rectangular region, having a partial region in common with said rectangular region, and

a difference between a sum of image data values of pixels included in said first rectangular region and excluded from said second rectangular region, and

a sum of image data values of pixels included in said second rectangular region and excluded from said first rectangular region, which is calculated by using a first value of a first pixel image data in said first designated line of said image, which is latest read from said memory means, a second value of a first pixel image data in said second designated line, said second value being latest read from said external memory; and

two values of pixel image data corresponding to said first and second values previously reed out when said second rectangular region was processed.

11. An image processor, for reading image data of pixels in an image to be processed from an external image memory, and obtaining an average value of image data of pixels in each of a plurality of rectangular regions defined as a plurality of rows and a plurality of columns in said image, in turn in the row direction, said image processor comprising:

memory means for storing image data of pixels for at least one line in the row direction of said image;

control means for controlling access to said memory means so that image data of each pixel is read from or written in the memory means in turn in the row direction, and for controlling access to said external memory so that image data of each pixel is read from said external memory in turn in the row direction, wherein said control means controls image data reading so that image data of each pixel existing in said first designated line of said image, which is stored in said memory means, and image data existing at the same column as that of said pixel in said second designated line part from said first designated line by the width of said rectangular region, which is stored in said external memory, are read out in turn; and

calculation means for obtaining an average value of image data values of pixels in a rectangular region to be presently processed, by using an average value for a rectangular region which was previously processed and image data read from said memory means and said external memory, respectively, wherein said calculation means;

obtains an average value of image data values of pixels in a first rectangular region by using an average value of image data values of pixels in a second rectangular region which was processed previously to said first rectangular region, having a partial region in common with said rectangular region, and

a difference between a sum of image data values of pixels included in said first rectangular region and excluded from said second rectangular region, and

a sum of image data values of pixels included in said second rectangular region and excluded from said first rectangular region, which is calculated by using a first value of a first pixel image data in said first designated line of said image, which is latest read from said memory means, a second value of a first pixel image data in said second designated line, said second value being latest read from said external memory; and

two values of pixel image data corresponding to said first and second values previously reed out when said second rectangular region was processed, and

wherein said calculation means includes;

a first calculator for obtaining a first difference between said first value and said second value,

a shift register for holding said first difference as a new first difference in turn by the amount of the row direction width of said rectangular region,

a second calculator for adding a preset third difference obtained by summing second differences output in turn from said shift register by the amount of the row direction width, to a previous third difference obtained previously to said present third difference,

a divider for dividing the result output from said second calculator by the number of pixels in said rectangular region,

a third calculator for adding the result output from said divider to said old average value of image data values of pixels in said second rectangular region; and

a shift register for holding the result output from said third calculator as a new average value for said second rectangular region.