Source: https://patents.google.com/patent/US20050147305
Timestamp: 2018-04-27 05:09:18
Document Index: 494616026

Matched Legal Cases: ['art 1810', 'art 1804', 'art 1804', 'art 1820', 'art 1820', 'art 1804', 'art 1820', 'art 1820', 'art 1804']

US20050147305A1 - Statistic calculating method using a template and corresponding sub-image to determine similarity based on sum of squares thresholding - Google Patents
Statistic calculating method using a template and corresponding sub-image to determine similarity based on sum of squares thresholding Download PDF
US20050147305A1
US20050147305A1 US11060400 US6040005A US2005147305A1 US 20050147305 A1 US20050147305 A1 US 20050147305A1 US 11060400 US11060400 US 11060400 US 6040005 A US6040005 A US 6040005A US 2005147305 A1 US2005147305 A1 US 2005147305A1
US11060400
US7082224B2 (en )
Shigeru Shibukawa
This is a continuation of application Ser. No. 09/802,958 filed 12 Mar. 2001, which is a continuation of application Ser. No. 08/994,096 filed 19 Dec. 1997, now U.S. Pat. No. 6,249,608.
In various fields using an image processing, a template matching method is used to search a partial area in an image (referred to as a search image) obtained by a sensor, which resembles a specified image pattern (referred to as a template). Such a template matching method is disclosed, for example, in “Image Analysis Handbook”, by Mikio Takagi and Akihisa Shimoda, University of Tokyo Press (1991). In a template matching method, it is often performed that each pixel is represented by a n-bit data for expressing a multilevel gradation image data, and a normalized correlation coefficient is used as a measure for a similarity of patterns. A normalized correlation coefficient r(i, j) is expressed by the following equation in which t(m, n) (m=0, 1, . . . , M−1; n=0, 1, . . . , N−1) is a data value of a pixel in a template, s (i+m, j+n) (m=0, 1, . . . , M−1; n=0, 1, . . . , N−1); and (I, j) is a starting point of a sub-image in a search image, of which a similarity to the template is to be evaluated, and P is the number of pixels in the template. r ⁡ ( i , j ) = ∑ n = 0 N - 1 ⁢ ⁢ ∑ m = 0 M - 1 ⁢ ⁢ ( s ⁡ ( i + m , j + n ) · t ⁡ ( i , j ) ) - 1 P ⁢ ( ∑ n = 0 N - 1 ⁢ ⁢ ∑ m = 0 M - 1 ⁢ ⁢ ( s ⁡ ( i + m , j + n ) ) · ∑ n = 0 N - 1 ⁢ ⁢ ∑ m = 0 M - 1 ⁢ ⁢ ( s ⁡ ( i + m , j + n ) ) 2 - 1 P ⁢ ( ∑ n = 0 N - 1 ⁢ ⁢ ∑ m = 0 M - 1 ⁢ ⁢ s ⁡ ( i + m , j + n ) ) 2 · ⁢ ( ∑ n = 0 N - 1 ⁢ ⁢ ∑ m = 0 M - 1 ⁢ ⁢ t ⁡ ( i , j ) ) ∑ n = 0 N - 1 ⁢ ⁢ ∑ m = 0 M - 1 ⁢ ⁢ ( t ⁡ ( i , j ) ) 2 - 1 P ⁢ ( ∑ n = 0 N - 1 ⁢ ⁢ ∑ m = 0 M - 1 ⁢ ⁢ t ⁡ ( i , j ) ) 2 ( 2 )
At first, the image data are read out of the external memory, and the data of the template and search images are stored with an array type of 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 of the computer (steps 101 and 102).
Furthermore, 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), a sum of image data values for each area of pixels for 1 column and N rows is calculated (step 405), the number N being equal to that of rows in the template image, further each area corresponding to a starting point (i, 1) (I=0, 1, . . . , I−1). Each sum of image data values for each area of pixels for 1 column and N rows is obtained 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 a pixels to a sum for a previous area and subtracting an image data value of another pixel from the previous area, that is, adding a differential amount between the above two image data values to the sum for the previous area. By accumulating the above-obtained M sums of image data values for M areas, each area being composed of pixels for 1 column and N rows, a sum of image data values for a sub-image corresponding to a starting point (0, 1) is obtained (step 406). Successively, sums of sub-images corresponding to starting points (1, 1), (2, 1), . . . , (I−M, 1) are obtained in turn, by adding a sum of image data values for an area of pixels for 1 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 1 column and N rows from the sum for the previous sub-area, that is, adding a differential amount between the above two sums to the sum for the previous sub-image (step 407).
For J=2, . . . , J−N, a sum of image data values for each sub-image is also obtained by making use of previously calculated results (step 405-step 409), similarly for J=1. Representing a sum of image data values for each sub-image corresponding to a starting point (i, j) by C(i, j) in the search image shown FIG. 14, C(i,j) (i=0, 1, 2; J=0, 1, 2) are as follows.
In a process for obtaining a sum of squares of image data values for all sub-images in the search image, squares of image data values of pixels in the respective template and search images are obtained, and a sum of squares of image data values for each sub-image is further obtained by a process similar to the above-mentioned process for obtaining sums of image data values for all sub-images. Representing a sum of image data values for each sub-image corresponding to a starting point (i, j) by D(i, j) in the search image shown FIG. 14, D(i, j) (i=0, 1, 2; J=0, 1, 2) are as follows.
The above explanation is as to a pre-processing, and in the pre-processing according to the present invention, it is possible to obtain a sum, and a sum of squares, of image data values for each of the template image and the search image by using image data which are obtained by scanning the respective template and search images at one time. Next, a process for obtaining a normalized correlation coefficient is executed for a sub-image to be processed. In the process, at first, a sub-image corresponding to a starting point (0, 0) is selected (step 106), and a threshold value F (0, 0) for closing a process for evaluating a similarity of the sub-image is obtained, based on the following equation 3 (step 107). F ⁡ ( i , j ) = B + D ⁡ ( i , j ) - 2 ⁢ AC ⁡ ( i , j ) P - 2 ⁢ E · B - A 2 P · D ⁡ ( i , j ) - ( C ⁡ ( i , j ) ) 2 P ( 3 )
Hereupon, as to a sub-image corresponding to a starting point (0, 0), a sum A of image data values for the template image is 230, a sum B of squares of image data values for the template image is 6500, a sum C(0, 0) of image data values for the sub-image is 390, a sum D(0, 0) of squares image data values for the sub-image is 20900, the threshold value E for a normalized correlation coefficient is 0.7, and the number of pixels in the template image is 9. Thus, the threshold value F(0, 0) is 5258. The threshold value F(0, 0) is the upper limit to a sum of squares of differences between image data values of pixels in the sub-image and those of the respective corresponding pixels in the template image, such that the sub-image has a normalized correlation coefficient of more than 0.7 to the template image. That is, if a sum of squares of differences between image data values of pixels in the sub-image and those of the respective corresponding pixels in the template image is larger than the threshold value F(0, 0), the normalized correlation coefficient between the sub-image and the template image is less than 0.7. This relation can be proved from equation 2, equation 3, and under the following conditions: the sum of squares of differences between image data values of pixels in the sub-image and those of the respective corresponding pixels in the template image >F(0, 0).
Next, a square of a difference between an image data value of each pixel in the template image and that of a corresponding pixel in the sub-image is obtained in order, further a cumulative addition is performed for each obtained square, and it is determined whether the result of the cumulative addition exceeds the threshold value F(0, 0) (step 108-step 11). Since the result of the cumulative addition monotonously increases, if the result of the cumulative addition exceeds the threshold value F(0, 0), results in successive cumulative addition processes can not decrease from the threshold value F(0, 0). Therefore, when the result of the cumulative addition exceeds the threshold value F(0, 0), the process for estimating a similarity of the sub-image to the template image is closed, and a process for estimating a similarity of a next sub-image is started. When calculation for a sum of squares of differences between image data values of all pixels in the sub-image and those of all pixels in the template image is completed, if the sum does not exceed the threshold value F(0, 0), a normalized correlation coefficient between the sub-image and the template image is more than 0.7, and the starting point (0, 0) of the sub-image is registered. FIG. 15 shows a threshold value F(i, j) for a sub-image corresponding to a starting point (i, j), and results of the cumulative addition of squares of differences between image data values of pixels in the sub-image and those of pixels in the template image. For example, as to the sub-image corresponding to a starting point (0, 0), since an image data value of the first pixel of the sub-image is 30, and that of the corresponding first pixel of the template image is also 30, a sum of a square of a difference between an image data value of the pixel of the sub-image and that of the pixel of the template image is 0, and the sum does not exceed the threshold value F(0, 0). Therefore, successively cumulative addition for squares of the differences is continued. As for the sixth pixels in both images, since the result of cumulative addition is 5700, and it exceeds the threshold value F(0, 0) (=5258), cumulative addition for pixels from the seventh pixels are not performed, and processing of the next sub-image is started.
FIG. 7 shows another embodiment according to the present invention. A flow chart in FIG. 7 shows a modification of the template matching method shown by the flow chart in FIG. 1. Mentioning more in detail, the following step is added to the procedures shown in FIG. 1, that is, if a normalized correlation coefficient calculated for a sub-image is larger than a previously value set to E, the value of E is replaced with the normalized correlation coefficient calculated at this time. Each normalized correlation coefficient is obtained by the following equation 4. r ⁡ ( i , j ) = B + D ⁡ ( i , j ) - 2 ⁢ AC ⁡ ( i , j ) P - G 2 · B - A 2 P · D ⁡ ( i , j ) - ( C ⁡ ( i , j ) ) 2 P ( 4 )
Numerals 915, 916, 917, 918, 919 and 920 indicate registers for storing the number of pixels in the template image, a threshold value E for a normalized correlation coefficient, a sum of image data values of pixels in the template image, a sum of squares of image data values for the template image, a sum of image data values of pixels in a sub-image to be processed, and a sum of squares of image data values for the sub-image, respectively. Representing the respective values stored in the registers 915, 916, 917, 918, 919 and 920 by P, E, A, B, C and D, numeral 921 indicates a calculator for calculating the following equation 5 for the values P, E, A, B, C and D, and numeral 922 indicates a register for storing the result of the calculation executed by the calculator 921. Moreover, numerals 911, 912, 913 and 914 indicate a subtracter, a multiplier, an adder, and a register for storing an interim result of calculation executed in the adder 913, respectively. F = B + D - 2 ⁢ AC P - 2 ⁢ E · B - A 2 P · D - C 2 P ( 5 )
FIG. 19 shows a memory address map of the image memory 1802. The image memory 1802 is composed by using, for example, a SDRAM (synchronous DRAM), and image data of pixels in the image are stored in the image memory 1802, according to the address map shown in FIG. 19. That is, the image memory 1802 composed by using a DRAM, a SDRAM, etc., has the capacity of image data for an area of m rows and n columns, where n and m are natural numbers. Usually, access to a DRAM or a SDRAM is performed by designating a row address and a column address. In FIG. 19, the row address is expressed by m, and the column address is expressed by n. In an embodiment of the present invention, the memory control part 1810 executes a memory access control wherein since a high frequency cycle mode such as a high speed page mode can be used by designating a row address and a plurality of successive column addresses, it becomes possible to realize a high-speed image data write-in to the image memory 1802 and a high-speed image data read-out of the image memory 1802. Hereupon, each image data is expressed, for example, by an eight-bit data.
The calculation part 1804 obtains the moving-average value B of the region 2101 by taking in the image data values A and E of the most right and lowest pixel and the most right and top pixel. The subtracter 2201 for calculating (A−E) takes in the image data value A via the transmission line 1803 a and the image data value E via the transmission line 1802 a, further executes subtraction of (A−E), and outputs the result of the subtraction to a transmission line 2201 a. The shift register 2202 receives each output signal from the subtracter 2201 and holds the output signals by the amount for the region width (five signals in the example shown in FIG. 21). Consequently, an output signal from the shift register 2202 is equal to a value (A−E) shifted by 5 pixels in the left direction, that is, a value (A′−E′). The subtracter 2203 for calculating ((A−E)−(A′−E′)) calculates ((A−E)−(A′−E′)) by receiving an output signal from the subtracter 2201 and an output signal from the shift register 2202, and outputs the results of the subtraction to a transmission line 2203 a. The adder 2204 for calculating (D−C) adds five output signals of ((A−E)−(A′−E′)) output from the subtracter 2203, further calculates (D−C) by using the result of the addition and (D′−C′) output from the latch memory 2205, and outputs the result of the calculation to a transmission line 2204 a. The latch memory 2205 for holding (D−C) output from the adder 2204 delays the held (D−C) by one processing step, and outputs it as (D′−C′) to a transmission line 2205 a. The divider 2210 receives (D−C) output from the adder 2204, further divides the (D−C) by the number N of pixels in the kernel region, and outputs the result of the division to the adder 2207. Hereupon, the number N can be set in advance, or input by a user. The shift register 2206 receives an output signal from the adder 2207 for calculating B in turn, and holds the output signals by the amount for one line of the image (n words for the image shown in FIG. 19). Therefore, an output signal from the shift register 2206 is a value B obtained previously by one line, that is, a moving-average value B′ of the region 2102 shown in FIG. 21. The adder 2207 for calculating B receives an output signal from the shift register 2206 and an output signal from the divider 2210, further calculates a moving-average value B of the present kernel region, and outputs the result of the calculation to the transmission line 1804 a.
In accordance with the above-mentioned procedures, the algorithm based on equations 6 and 7 is implemented. Hereupon, it is possible that the calculation part 1804 performs only addition or subtraction processing and outputs results of final addition processing to the image memory 1805, furthermore, an outside processor performs the division calculation in place of the divider 2210 and obtains the moving-average value B.
The calculation 1804 takes in the image data value A of the most right and lowest pixel and the image data value E of the top pixel 2345 in the vertical area 2314, which are shown in FIG. 23, and obtains the moving-average value B of the region 2301. The subtracter 2201 for calculating (A−E) receives the image data value A of the pixel 2341 via the transmission line 1802 a and the image data value E of the top pixel 2345 in the vertical area 2314 via the transmission line 1803 a, further performs subtraction of (A−E), and outputs the result of the subtraction to the transmission line 2201 a. The shift register 2402 receives an output signal from the adder 2403 for calculating G via a transmission line 2403 a, and holds values of G by the amount of one line. Therefore, an output signal from the shift register 2402 is a value G obtained previously by one line, that is, the value G′ shown in FIG. 23. Moreover, an output signal from the fifth stage of the shift register 2402 is a value G obtained previously by the width of the kernel region, that is, the value F shown in FIG. 23. The adder 2403 for calculating G calculates G by using an output signal from the subtracter 2201 for calculating (A−E) and an output signal G′ from the shift register 2402, and output the results of the calculation to a transmission line 2403 a. The subtracter 2404 for calculating (G−F) calculates (G−F) by using an output signal G from the adder 2403 for calculating G and an output signal F from the shift register 2402, and outputs the result of the calculation to a transmission line 2404 a. The divider 2210 receives an output signal (G−F) from the subtracter 2404 for calculating (G−F), divide (G−F) by the preset number N of pixels in the kernel region, and outputs the result of the division. The adder 2405 for calculating B receives an output signal B″ from the latch memory 2406 for holding a value B″ and an output signal of the divider 2210, further obtains the moving-average value B of the present kernel region, and outputs the obtained moving-average value via the transmission line 1804 a. The latch memory 2406 for holding B″ receives an output signal from the adder 2405 for calculating B, further delays the received output signal by one pixel, and outputs it as B″ via a transmission line 2406 a.
The subtracter 2201 for calculating (A−E) receives the image data value A of the pixel 2341 via the transmission line 1802 a, and the image data value E of the top pixel 2345 in the vertical line area 2134 via the transmission line 1803 a, further perform subtraction of (A−E), and outputs the result of the subtraction to the transmission line 2201 a. The shift register 2502 for holding values G by the number of (one line pixels−pixels by the region width) receives an output signal from the shift register 2507 for holding values G by the amount for the region width via a transmission line 2402 b, and holds values G by the amount of (one line pixels−pixels by the region width, that is, (n−5)) in turn. The shift register 2507 for holding values G receive a value G, and holds values G by the amount for the region width. Therefore, an output signal from the shift register 2507 is a value G obtained previously by the width, that is, the value F shown in FIG. 23. The adder 2403 for calculating G calculates G by using an output signal (A−E) from the subtracter 2201 for calculating (A−E) and an output signal G′ from the shift register 2507 for holding values G by the amount for the region width, and outputs the result of the calculation to the transmission line 2403 a. The subtracter 2404 for calculating (G−F) calculates (G−F) by using an output signal G from the adder 2403 for calculating G and an output signal F from the shift register 2507 for holding values G by the amount for the region width, and outputs the result of the calculation to a transmission line 2404 a. The divider 2210 receives an output signal (G−F) from the subtracter 2404 for calculating (G−F), further divide (G−F) by the preset number N of pixels in the kernel region, and outputs the result of the division. The adder 2405 for calculating B receives an output signal B″ from the latch memory 2406 for holding a value B″ and an output signal of the divider 2210, further obtains the moving-average value B of the present kernel region, and outputs the obtained moving-average value B via the transmission line 1804. The latch memory 2406 for holding B″ receives an output signal B from the adder 2405 for calculating B, delays the received output signal by one pixel, and outputs it as B″ via a transmission line 2406 a.
In this algorithm, the moving-average value B of the present kernel region is obtained by adding (the sum G of the most right vertical line area 2304—the sum F of the most left vertical line area 2302)/N to the moving-average value B′ of the kernel region processed previous by one pixel. Moreover, the value of (the sum G of the most right vertical line area−the sum F of the most left vertical line area) is obtained by adding (the image data value A of the lowest pixel in the vertical line area 2304−the image data value E of the top pixel in the vertical line area 2345) to (the sum G′ of the vertical line area 2314−the sum F′ of the vertical line area 2313) and subtracting (the image data value A′ of the lowest pixel in the vertical line area 2303−the image data value E′ of the top pixel in the vertical line area 2313) from the result of the addition. This algorithm is expressed by equations 9 and 10.
The calculation 1804 takes in the image data values A and E of the most right and lowest pixel and the most right and top pixel, which are shown in FIG. 26, and obtains the moving-average value B of the region 2301. The subtracter 2201 for calculating (A−E) receives the image data value A of the pixel 2341 via the transmission line 1802 a and the image data value E of the pixel 2345 via the transmission line 1803 a, further performs subtraction of (A−E), and outputs the result of the subtraction to the transmission line 2201 a. The shift register 2202 receives an output signal (A−E) from the subtracter 2201 for calculating (A−E) via the transmission line 2201 a, and holds values (A−E) by the amount for the region width. Therefore, an output signal from the shift register 2202 is a value (A−E) obtained previously by the region width, that is, the value (A′−E′) shown in FIG. 26. The subtracter 2203 for calculating ((A−E)−(A′−E′)) calculates ((A−E)−(A′−E′)) by using an output signal from the subtracter 2201 for calculating (A−E) and an output signal from the shift register 2202, and output the results of the calculation to a transmission line 2203 a. The adder 2704 for calculating (G−F) calculates (G−F) by using an output signal from the subtracter 2203 for calculating ((A−E)−(A′−E′)) and an output signal (G′−F′) from the shift register 2707, and outputs the result of the calculation to a transmission line 2704 a. The shift register 2707 receives an output signal from the adder 2704 for calculating (G−F), and holds values (G−F) by the amount for one line in turn. Therefore, an output signal from the shift register 2707 is a value (G−F) obtained previously by one line, that is, the value (G′−F′) shown in FIG. 26. The divider 2210 receives an output signal (G−F) from the adder 2704 for calculating (G−F), further divides (G−F) by the preset number N of pixels in the kernel region, and outputs the result of the division. The adder 2405 for calculating B receives an output signal B′ from the latch memory 2406 for holding a value B′ and an output signal from the divider 2210, further obtains the moving-average value B of the present kernel region, and outputs the obtained moving-average value via the transmission line 1804 a. The latch memory 2406 for holding B′ receives an output signal from the adder 2405 for calculating B via the transmission line 1804 a, further delays the received output signal by one pixel, and outputs it as B′ via a transmission line 2406 a.
In the following, operations of the image processing apparatus shown in FIG. 28 will be explained. Each of image data of the image taken in by the image input device 1801 is stored at an address of each of the image memories 1802 and 2801 via the transmission line 1801 a, which is designated by the memory control part 1820. The designated addresses are equal to each other. This is, the same image data is written at the same address in the respective memories 1802 and 2801. The image processor 1800 reads out an image data A of the pixel 2341 of the present kernel region stored in the image memory 1802, via the transmission line 1802 a, and an image data E of the pixel 2345, stored in the image memory 2801, via the transmission line 1803 a. The memory control part 1820 control image data reading so that an image data of the most right and lowest pixel 2341 is read out of the image memory 1802, and an image data of the most right and top pixel 2345 is read out of the image memory 2801. The calculation part 1804 takes in the image data value A of the pixel 2341 from the memory 1802 and the image data value E of the pixel 2345 from the memory 2801, further calculates the moving-average value B, and outputs the result of the calculation. The calculated moving-average value B is input to the memory 1805 via the transmission line 1804 a, and is stored at an address of the image memory 1805, which is designated by the memory control part 1820. Similarly, in order to obtain a moving-average value of the next kernel region (the kernel region corresponding to the central pixel shifted by one pixel in the right direction from the central pixel of the present kernel region), the memory control part 1820 control image data reading so that an image data of a pixel which is shifted by one pixel in the right direction from the pixel 2341 is read out of the image memory 1802, and at the same time, an image data of a pixel which is shifted by one pixel in the right direction from the most right and top pixel 2345 is read out of the image memory 2801, and so forth. Similarly, in another line, a necessary image data of each pixel is read out in turn in the horizontal direction from each of the memories 1802 and 2801.
The calculation part 1804 obtains the moving-average value B of the region 2301 by taking in the image data values A and E, for the pixel 2141 and the pixel 2145. The subtracter 2201 for calculating (A−E) takes in the image data value A via the transmission line 1802 a, and the image data value E via the transmission line 1803 a, further executes subtraction of (A−E), and outputs the result of the subtraction to a transmission line 2201 a. The shift register 2202 receives each output signal from the subtracter 2201, and holds the output signals by the amount for the region width (five signals in the example shown in FIG. 21). Consequently, an output signal from the shift register 2202 is equal to a value (A−E) shifted by 5 pixels in the left direction, that is, (A′−E′). The subtracter 2203 for calculating ((A−E)−(A′−E′)) calculates ((A−E)−(A′−E′)) by receiving an output signal from the subtracter 2201 and an output signal from the shift register 2202, and outputs the results of the subtraction to a transmission line 2203 a. The adder 2204 for calculating (D−C) adds five output signals of ((A−E)−(A′−E′)) from the subtracter 2203, further calculates (D−C) by using the result of the addition and a value (D′−C′) output from the latch memory 2205, and outputs the result of the calculation to a transmission line 2204 a. The latch memory 2205 for holding (D−C) output from the adder 2204 delays the held (D−C) by one step corresponding to processing of an moving average for one central pixel, and outputs it as (D′−C′) to the transmission line 2205 a. The divider 2210 receives (D−C) output from the adder 2204, further divides the (D−C) by the number N of pixels in the kernel region, and outputs the result of the division to the adder 2207. The line memory 3005 receives an output signal from the adder 2207 for calculating B in turn, and holds the output signals by the amount for one line on the image (n words are held for the image shown in FIG. 19). Therefore, an output signal from the line memory 3005 is a value B obtained previously by one line, that is, a moving-average value B′ of the kernel region 2102 shown in FIG. 21. The adder 2207 for calculating B receives an output signal from the line memory 3005 and an output signal from the divider 2210, further calculates a moving-average value B of the present kernel region, and outputs the result of the calculation to the transmission line 1804 a.
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 a pixels to a sum for a previous area and subtracting an image data value of another pixel from the previous area;
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.
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.
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);
successively obtains sums of squares of sub-images corresponding to starting points (1, 0), (2, 0), . . . , (I−M, 0) in turn, by adding a 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.
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 a pixels to a sum of squares for a previous area and subtracting an image data value of another pixel from the previous area;
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.
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.
US11060400 1996-12-25 2005-02-18 Statistic calculating method using a template and corresponding sub-image to determine similarity based on sum of squares thresholding Expired - Lifetime US7082224B2 (en)
JP9-5399 1997-01-16
US09802958 US6898318B2 (en) 1996-12-25 2001-03-12 Statistic calculating method using a template and corresponding sub-image to determine similarity based on sum of squares thresholding
US20050147305A1 true true US20050147305A1 (en) 2005-07-07
US7082224B2 US7082224B2 (en) 2006-07-25
US20010031086A1 (en) 2001-10-18 application