Source: http://www.google.com/patents/US6898318?dq=5726663
Timestamp: 2016-05-24 22:19:38
Document Index: 718573942

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

Patent US6898318 - Statistic calculating method using a template and corresponding sub-image to ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsAn 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...http://www.google.com/patents/US6898318?utm_source=gb-gplus-sharePatent US6898318 - Statistic calculating method using a template and corresponding sub-image to determine similarity based on sum of squares thresholdingAdvanced Patent SearchPublication numberUS6898318 B2Publication typeGrantApplication numberUS 09/802,958Publication dateMay 24, 2005Filing dateMar 12, 2001Priority dateDec 25, 1996Fee statusPaidAlso published asDE69729368D1, DE69729368T2, EP0851383A2, EP0851383A3, EP0851383B1, EP0851383B9, US6249608, US7082224, US20010031086, US20050147305Publication number09802958, 802958, US 6898318 B2, US 6898318B2, US-B2-6898318, US6898318 B2, US6898318B2InventorsTakashi HottaOriginal AssigneeHitachi, Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (25), Non-Patent Citations (4), Referenced by (6), Classifications (9), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetStatistic calculating method using a template and corresponding sub-image to determine similarity based on sum of squares thresholding
US 6898318 B2Abstract
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.
1. An image processing method of reading image data of pixels in an image to be processed from, from a memory for storing an image data value of each pixel in said image, 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 method comprising the steps of:
obtaining 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 calculate an average value of image data values of pixels in said first rectangular region, having a partial region in common with said rectangular region, and using a difference between image data values of pixels included in said first rectangular region and excluded from said second rectangular region and image data values of pixels included in said second rectangular region and excluded from said first rectangular region;
wherein said difference is calculated by using a first image data value of a pixel neighboring the top pixel at the upper side of said top pixel in an area of pixels included in said first rectangular region and excluded from said second rectangular region, image data values of which have been read out previously to calculate said average value of image data values of pixels in said first rectangular region, a second image data value of the bottom pixel in said area of pixels included in said first rectangular region and excluded from said second rectangular region, a third image data value of a pixel neighboring the top pixel at the upper side of said top pixel in an area of pixels included in said second rectangular region and excluded from first second rectangular region, a fourth image data value of the bottom pixel in said area of pixels included in said second rectangular region and excluded from said first rectangular region. 2. An image processing method of reading image data of pixels in an image to be processed, from a memory for storing an image data value of each pixel in said image, and obtaining a sum 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 method comprising the steps of:
obtaining a sum of image data values of pixels in a first rectangular region by using a sum of image data values of pixels in a second rectangular region which was processed previously to calculate a sum of image data values of pixels in said first rectangular region, having a partial region in common with said rectangular region, and using a difference between image data values of pixels included in said first rectangular region and excluded from said second rectangular region and image data values of pixels included in said second rectangular region and excluded from said first rectangular region; wherein said difference is calculated by using a first image data value of a pixel neighboring the top pixel at the upper side of said top pixel in an area of pixels included in said first rectangular region and excluded from said second rectangular region, image data values of which have been read out previously to calculate said sum of image data values of pixels in said first rectangular region, a second image data value of the bottom pixel in said area of pixels included in said first rectangular region and excluded from said second rectangular region, a third image data value of a pixel neighboring the top pixel at the upper side of said top pixel in an area of pixels included in said second rectangular region and excluded from first second rectangular region, a fourth image data value of the bottom pixel in said area pixels included in said second rectangular region and excluded from said first rectangular region. 3. An image processing method of reading image data of pixels in an image to be processed, from a memory for storing an image data value of each pixel in said image, and obtaining a sum of squares of image data values 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 method comprising the steps of:
obtaining a sum of squares of image data values of pixels in a first rectangular region by using a sum of squares of image data values of pixels in a second rectangular region which was processed previously to calculate a sum of squares of image data values of pixels in said first rectangular region, having a partial region in common with said rectangular region, and using a difference between image data values of pixels included in said first rectangular region and excluded from said second rectangular region and image data values of pixels included in said second rectangular region and excluded from said first rectangular region; wherein said difference is calculated by using a first image data value of a pixel neighboring the top pixel at the upper side of said top pixel in an area of pixels included in said first rectangular region and excluded from said second rectangular region, image data values of which have been read out previously to calculate said sum of squares of image data values of pixels in said first rectangular region, a second image data value of the bottom pixel in said area of pixels included in said fist rectangular region and excluded from said second rectangular region, a third image data value of a pixel neighboring the top pixel at the upper side of said top pixel in an area of pixels included in said second rectangular region and excluded from first second rectangular region, a fourth image data value of the bottom pixel in said area of pixels included in said second rectangular region and excluded from said first rectangular region.
This 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 t ( i , j ) ) ∑ 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 ) ) 2 - 1 P ( ∑ n = 0 N - 1 ∑ m = 0 M - 1 t ( i , j ) ) 2 ( 2 ) In performing template matching, the above-described normalized correlation coefficient is obtained for each of a plurality of sub-images, and one or plural sub-images which are determined to resemble a template are selected in accordance with the obtained normalized correlation coefficients. A method using a normalized correlation coefficient can perform template matching without receiving effects of variations between image data values of pixels in a template image and those of pixels in a search image, the variation being caused, for example, by changes in lighting.
A moving-average filtering method used as one of filtering methods performs filtering for an image data of each object pixel in an image to be processed, by averaging image data values of pixels in a rectangular region including the object pixel, the size of the rectangular (kernel size) being usually preset. In the following, outline of a moving-average filtering method will be explained with reference to FIGS. 35A and 35B. Hereupon, FIG. 35A is an image composed of 9 pixels in the column direction (the lateral direction)�8 pixels in the row direction. Numerals 211-289 indicate pixels. FIG. 35B shows an image obtained by executing moving-average filtering with a kernel size of 5 pixels�5 pixels, for image data of pixels shown in FIG. 35A. Numerals 211′-289′ indicated pixels of which image data values were filtered. For example, an image data value of a pixel 233′ is an average value of image data values of pixels in a region for 5 pixels in the row direction and 5 pixels in the column direction, in which the pixel 233 is centered, that is, an average value of image data values of pixels 211, 212, 213, 214, 215, 221, 222, 223, 224, 225, 231, 232, 233, 234, 235, 241, 242, 243, 244, 245, 251, 252, 253, 254 and 255. Similarly, an image data value of a pixel 234′ is an average value of image data values of pixels in a region for 5 pixels�5 pixels, in which the pixel 234 is centered, further an image data value of a pixel 235′ is an average value of image data values of pixels in a region for 5 pixels�5 pixels, in which the pixel 235 is centered, and so on. Thus, an image data value of each pixel in the image shown in FIG. 35B has an average value of image data values of pixels in a region having the kernel size for 5 pixels�5 pixels, in which the corresponding pixel in the image shown in FIG. 35A is centered.
Image data of an image input by the image input device 3601 are stored in the image memory 3604, and the calculation circuit 3602 obtains an average value of image data of n pixels in the row direction, in parallel to storing of the image data. In the following, procedures to obtain a moving-average value by using data stored in the memory 3603 will be explained with reference to FIG. 37. In FIG. 37, numeral 2101 indicates a region for 5 pixels�5 pixels, which is to be presently processed for obtaining an moving-average value, and numeral 2102 indicates a region (referred to as kernel region) for 5 pixels�5 pixels, which was previously processed to obtain an moving-average value. Moreover, numerals 2103 and 2104 indicate two areas, each of the areas being composed of n (=5) pixels in the row direction, respectively. A position of a pixel centered in an kernel region changes from the most left position to the most right position in the top row, in the image shown in FIG. 37, and the position of a center pixel similarly changes in the successive rows, and so forth. An moving-average value for the region 2101 is obtained based on the following relation: a moving-average value for the region 2101=a moving-average value for the region 2102—(an average value for the area 2103—an average value for the area 2104)/(the number of lines in the region 2101).
FIG. 22 is a circuit block diagram of a calculation part of the moving- average filter according to the present invention.
A method of efficiently obtaining a sum, and a sum of squares, of image data values for the template image and the search image will be explained with reference to FIG. 2-FIG. 6. A concept of improvement for obtaining the above-mentioned sums are shown in FIG. 2 and FIG. 3. In FIG. 2, a sum G′ of image data values for a present sub-image 201 having the same size as that of the template image is equal to a value obtained by subtracting a sum U of image data values for an area 203 from a sum G of image data values for a previous sub-image 202 which is located at an area shifted from the present sub-image 201 in the reverse main scanning direction by one pixel, and by adding a sum V of image data values for an area 204 to the subtraction result. That is, G′=G−U+V. Furthermore, as shown in FIG. 3, a sum V of image data values for the area 204 is equal to a value obtained by subtracting a image data value y of a pixel 206 from a sum W of image data values for an area 205 which is located at an area shifted from the area 204 in the upper direction by one line, and by adding a image data value z of a pixel 207 to the subtraction result, that is, V=W−y+z. Therefore, it is possible to obtain the sum G′ of image data values for the sub-image 201 by executing fundamentally four times of addition and subtraction, if the sum G of image data values for the sub-image 202 and the sum U of image data values for the area 203 are calculated in advance.
At first, in order to obtain sums of image data values for (I-M+1) sub-images corresponding to the 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), a sum of image data values for each area composed of pixels for 1 column and N rows is calculated (step 401), 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). At first, by accumulating M sums of image data values for M areas of pixels for 1 column and N rows, a sum of image data values for a sub-image corresponding to a starting point (0, 0) is obtained (step 402). Successively, sums of sub-images corresponding to starting points (1, 0), (2, 0), . . . , (I-M, 0) 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 403).
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.
(C(0, 0), C(0, 1), C(0, 2), C(1, 0), C(1, 1), C(1, 2), C(2, 0), C(2, 1), C(2, 2))=(390, 580, 690, 270, 380, 470, 270, 310, 380) 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.
(D(0, 0), D(0, 1), D(0, 2), D(1, 0), D(1, 1), D(1, 2), D(2, 0), D(2, 1), D(2, 2))=(20900, 44800, 58500, 9500, 20400, 30100, 8700, 1190, 19600) FIG. 5 and FIG. 6 show another method of efficiently obtaining a sum, and a sum of squares, of image data values. The method shown in FIG. 2 and FIG. 3 obtains a sum G′ of image data values for the present sub-image 201, based on a difference between a sum of image data values for the sub-image 201 and a sum of image data values for the previous sub-image 202 shifted from the sub-image 201 in the reverse main scanning direction by one pixel. On the other hand, the method shown in FIG. 5 and FIG. 6 obtains a sum of image data values for a present sub-image 501, based on a difference between a sum of image data values for the sub-image 501 and a sum of image data values for a previous sub-image 502 shifted from the sub-image 501 in the upper row direction by one line.
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 A C ( i , j ) P - 2 E � B - A 2 P � D ( i , j ) - ( C ( i , j ) ) 2 P ( 3 ) where A: a sum of image data values for the template image,
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 111). 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 A C ( i , j ) P - G 2 � B - A 2 P � D ( i , j ) - ( C ( i , j ) ) 2 P ( 4 ) where A: a sum of image data values for the template image,
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 A C P - 2 E � B - A 2 P � D - C 2 P ( 5 ) Numeral 923 indicates a comparator for comparing an interim result stored in the register 914 with a threshold value stored in the register 922, and outputting a control signal to close a process for evaluation of a similarity for a present sub-image and to start a process for evaluation of similarity for the next sub-image.
Operations in which a sum of image data values of pixels in a sub-image of the search image is calculated by the calculator 1000 shown in FIG. 10 will be explained with reference to FIG. 2 and FIG. 3. At first, image data of the search image are input to the calculator 1000 in the order of rasher scanning. An image data (referred to as z) input to the calculator 1000 is stored in the line memory 1001, and is input to the subtracted 1002. Hereupon, it is assumed that a present image data input to the calculator is an image data of a pixel 207 shown in FIG. 3. The computer reads an image data (referred to as y) from the line memory 1001, which is stored at the same column as that at which the data z is stored, in a line positioned upper by N lines from a line in which the image data z is stored, and inputs the image data y to the subtracted 1002. The data y is an image data of a pixel 206 shown in FIG. 3. If a pixel corresponding to the data y does not exist in the search image, the value of 0 is set to the initial value for y. The subtracter 1002 executes a calculation of (z-y). The line memory 1004 stores M sums for one line, each being a sum of image data values of pixels in an area of 1 column and N rows. The adder 1003 adds the value (z-y) calculated by the subtracter 1002 to a sum (referred to as W) of image data values of pixels in the area 205 shown in FIG. 3, and outputs the results of the addition as a sum (referred to as V) of image data values of pixels in the area 204 shown in FIG. 2. Image data output from the adder 103 are stored in the line memory 1004, and input to the subtracted 1005. The subtracted 1005 subtracts a sum (referred to as U) of values of image data read out of the line memory 1004, of pixels in the area 203 shown in FIG. 2, from the above value V, and outputs the result of the subtraction. The adder 1006 calculates a sum of image data values of pixels in the sub-image 201 shown in FIG. 2, by adding the above-mentioned result of the subtraction to a sum (referred to as G) which is stored in the register 1007, of image data values of pixels in the sub-image 202 shown in FIG. 2. The calculated sum of image data values for the sub-image 201 is stored in both of the memories 1007 and 1008.
FIG. 20A shows an image which is expressed by an area of 9 pixels in the row direction and 8 pixels in the column directions. Numerals 211-289 indicate respective pixels in the image. The memory control part 1810 controls image data write-in and image data read-out by designating addresses of the image data in the image memory 1802. In image data read-out processing, addresses for all pixels in every one line of the image are designated at one time, and image data corresponding to the designated address are continuously read out. In accordance with this embodiment, for the image shown in FIG. 20A, it is possible that after nine image data from an image data of the most left pixel 211 to an image data of the most right pixel 219 in the top line are read out in turn, nine image data of pixels in another line, for example, image data of pixels 261-269 in the sixth row, are read out in turn. Moreover, FIG. 20B shows an image, in which pixels are indicated by numerals 211′ to 289′, obtained by performing a moving-average filtering process for a kernel region of 5 pixels�5 pixels, of the image shown in FIG. 20A. The position of a central pixel in the kernel area is changed from 211 to 219 in the row direction, next from 221 to 229, further from 231 to 239, and so forth.
In the following, an algorithm of moving-average filtering used in this embodiment will be explained with reference to FIG. 21. In FIG. 21, numeral 2101 indicates a region of which a moving-average (referred to as present region average value) is presently to be processed, and the present region average value is expressed by B. Numeral 2141 indicate a pixel located at the most right and lowest position in the kernel region 2101, and an image data value of the pixel 2141 is expressed by A. Numeral 2102 indicate a kernel region set at the position upper by one line from the kernel region 2101, and a moving-average of the kernel region 2102 is expressed by B′ which was obtained previously by one line to the moving- average B. Numeral 2103 indicate an upper line area in the top line in the kernel region 2102, and a sum of image data values of pixels in the upper line area 2103 is expressed by C. Numeral 2104 indicate a lower line area of the bottom line in the kernel region 2101, and a sum of image data values of pixels in the line area 2104 is expressed by D. Numeral 2145 indicate a pixel located at the most right and top position in the kernel region 2102, and an image data value of the pixel 2141 is expressed by E. Numeral 2153 indicates an upper line area obtained by shifting the upper line area 2103 by one pixel in the left direction, and a sum of image data values of the upper line area 2153 is expressed by C′. Numeral 2154 indicates a lower line area obtained by shifting the lower line area 2104 by one pixel in the left direction, and a sum of image data values of the lower line area 2154 is expressed by D′. Numeral 2151 indicates a pixel located at the most left position in the lower line area 2154, and an image data value of the pixel 2151 is expressed by A′. Numeral 2155 indicates a pixel located at the most left position in the upper line area 2153, and an image data value of the pixel 2153 is expressed by ′.
In an algorithm used for this embodiment according to the present invention, the moving-average value B to be presently obtained is calculated by adding (the sum D of image data values of the lower line area—the sum C of image data values of the upper line area)/(the number N of pixels in the kernel region for moving-average filtering) to the moving-average value B′ of the region 2102 set at the position upper by one line from the region 2101. Furthermore, the value (the sum D of image data values of the lower line area—the sum C of image data values of the upper line area) is obtained by adding (the image data value A of the most right and lowest pixel 2141—the image data value E of the most right and top pixel 2145) to and subtracting (the image data value A′ of the most left and lowest pixel 2154—the image data value E′ of the most left and top pixel 2153) from (the sum C′ of the upper line area shifted by one pixel in the left direction—the sum D′ of the lower line area shifted by one pixel in the left direction). The above-mentioned algorithm is expressed by the following equations 6 and 7.
In the following, an algorithm used in another embodiment will be explained with reference to FIG. 23. Numeral 2301 indicates a kernel region 2301 of which a moving-average value is to be presently obtained, representing the moving- average value as B. Numeral 2341 indicates a pixel located at the most right and lowest position in the region 2301, representing the image data value of the pixel 2341 as A. Numeral 2303 indicates a vertical line area at the left outside of a previous kernel region 2302, representing a sum of image data values of pixels in the line area 2303 as F. Numeral 2304 indicates a vertical line area at the most right position in the region 2301, representing a sum of image data values of pixels in the line area 2304 as G. Numeral 2345 indicates a pixel upper by one line from the top position in the vertical line area 2304, representing the image data value of the pixel 2345 as E. Numeral 2302 indicates the previous kernel region shifted from the kernel region 2301 by one pixel in the left direction, representing a moving-average value of the region 2302 as B″. Numeral 2314 indicates a vertical line area upper by one line from the vertical line area 2304 located at the most right position in the kernel region 2301, representing a sum of image data values of pixels in the line area 2304 as G′. The moving-average value B″ of the region 2302 was obtained previously by one pixel before the moving-average value B of the region 2301 is obtained, and the sum G′ of the line area was obtained previously by one line before the sum G of the line area 2304 is obtained. That is, the moving-average value B″ of the region 2302 and the sum G′ for the area 2314 were already obtained and are held.
In the algorithm shown in FIG. 23, the moving-average value of the region 2301 to be presently obtained is calculated by adding (the sum G of the vertical line area 2304 at the right side position—the sum F of the vertical line area 2303 at the left side position)/N to the moving-average value B″ of the kernel region for the pixel previous by one pixel. Moreover, the sum G for the vertical line area 2304 at the right side position is obtained by adding the image data value A of the pixel 2341 to the sum G′ for the vertical line area 2304, and subtracting the image data value E of the pixel 2345 from the result of the addition. This algorithm is expressed by equations 8 and 9.
B=B″+(G−F) (9)
In FIG. 25, the calculation part 1804 includes the subtracter 2201 for calculating (A−E), a shift register 2502 for holding values G by the number of (one line pixels—pixels by the region width), the adder 2403 for calculating G, the subtracter 2404 for calculating (G−F), the adder 2405 for calculating B, the latch memory 2406 for holding B″, a shift register 2507 for holding values G by the amount for the region width, and the divider 2210.
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 accordance with the above-mentioned operations, the algorithm expressed by equations 8 and 9 is implemented.
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.
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 above later six embodiments which are, for example, shown in FIG. 21, FIG. 23, FIG. 26, FIG. 28, FIG. 29 and FIG. 30, respectively, have the following effects. FIG. 32 shows a time chart of operations in the above embodiments according to the present invention, and FIG. 33 shows a time chart of operations in a conventional method. In the embodiments shown in FIG. 32 and the method shown in FIG. 33, general SDRAMs are used. Each of the time charts shows time sequences of commands and addresses, which are to be processed, and corresponding data to be read out or written in a memory. In the conventional method, since data of discontinuous addresses are read out or written in a memory, a row address and a column address of the item of data should be designated, whenever access to each item of data is performed. Therefore, it takes 24 cycles to read out image data of four pixels (D1-D4), as shown in FIG. 33. On the other hand, in accordance with the above embodiments, each block of data in the column direction can be continuously read out with a burst read mode by designating successive column addresses after designating a row address. Consequently, it is possible to read out image data of four pixels (D1-D4) in 9 cycles. Thus, the above embodiments can read out data more quickly than the conventional method. That is, in accordance with the above embodiment according to the present invention, it is possible to perform moving-average filtering of image at a high speed.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4183013 *Nov 29, 1976Jan 8, 1980Coulter Electronics, Inc.System for extracting shape features from an imageUS4315318Dec 18, 1979Feb 9, 1982Fuji Photo Film Co., Ltd.Method and apparatus for processing a radiation imageUS4541116 *Feb 27, 1984Sep 10, 1985Environmental Research Institute Of MiNeighborhood image processing stage for implementing filtering operationsUS4635292 *Dec 17, 1984Jan 6, 1987Matsushita Electric Industrial Co., Ltd.Image processorUS4703513 *Dec 31, 1985Oct 27, 1987The United States Of America As Represented By The Administrator Of The National Aeronautics And Space AdministrationNeighborhood comparison operatorUS4745562 *Aug 16, 1985May 17, 1988Schlumberger, LimitedSignal processing disparity resolutionUS4747148 *Apr 9, 1984May 24, 1988Kabushiki Kaisha Komatsu SeisakushoMethod of identifying objectsUS5073963 *May 25, 1990Dec 17, 1991Arizona Technology Development Corp.Computerized method of matching two-dimensional (2-d) patternsUS5091963 *May 2, 1988Feb 25, 1992The Standard Oil CompanyMethod and apparatus for inspecting surfaces for contrast variationsUS5113454 *Aug 19, 1988May 12, 1992Kajaani Electronics Ltd.Formation testing with digital image analysisUS5168529 *Aug 29, 1988Dec 1, 1992Rayethon CompanyConfirmed boundary pattern matchingUS5168530 *Aug 29, 1988Dec 1, 1992Raytheon CompanyConfirmed boundary pattern matchingUS5280530 *Sep 5, 1991Jan 18, 1994U.S. Philips CorporationMethod and apparatus for tracking a moving objectUS5390262 *Oct 3, 1991Feb 14, 1995Ncr CorporationMethod for splitting and configuring a multi-channel image processing systemUS5412738 *Aug 10, 1993May 2, 1995Istituto Trentino Di CulturaRecognition system, particularly for recognising peopleUS5495537 *Jun 1, 1994Feb 27, 1996Cognex CorporationMethods and apparatus for machine vision template matching of images predominantly having generally diagonal and elongate featuresUS5579411 *Apr 21, 1995Nov 26, 1996Yozan Inc.High-speed circuit for performing pattern matching of image data and the like suitable for large scale integration implementationUS5623560 *Jul 25, 1995Apr 22, 1997Fuji Photo Film Co., Ltd.Method for adjusting positions of radiation imagesUS5768404 *Apr 13, 1995Jun 16, 1998Matsushita Electric Industrial Co., Ltd.Motion and disparity estimation method, image synthesis method, and apparatus for implementing same methodsUS5850466 *Feb 22, 1995Dec 15, 1998Cognex CorporationGolden template comparison for rotated and/or scaled imagesUS5852678 *May 30, 1996Dec 22, 1998Xerox CorporationDetection and rendering of text in tinted areasDE3740066A Title not availableEP0584701A2Aug 17, 1993Mar 2, 1994Yozan Inc.Pattern matching circuitJPH0751257A Title not availableJPS5675139A Title not available* Cited by examinerNon-Patent CitationsReference1C. T. Dreher et al.: A Potential Discrete Analog Processor for Pattern Recognition, Pattern Recognition, vol. 13, No. 3, 1981, pp. 207-218.2J. Martin et al.: Comparison of Correlation Techniques Intelligent Autonomous Systems, IAS-4, Proceedings of the International Conference, Proceedings of International Conference on Intelligent Autonomous Systems, Karlsruhe, Germany, Mar. 27-30, 1995, pp. 86-93, 1995, Amsterdam, Netherlands, IOS Press, Netherlands.3J. Schurmann: Anschaulicher Vergleich Verschiedener Dimensionier-ungsregeln f�r Linerare Zeichenerkennungssysteme, Wiss. Ber. AEG-Telefunken, vol. 43, No. 3/4, 1970, pp. 209-214.4 *Okutomi et al., Color Stereo Matching and its Application to 3-D Measurement of Optic Nerve Head, Sep. 3, 1992, IEEE, Pattern Recognition, 1992, vol. 1, Conference A: Computer Vision and Applications, Proceedings, 11<SUP>th </SUP>IAPR International Conference.** Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS6980335 *Aug 8, 2001Dec 27, 2005Nec CorporationColor image processing apparatus executing moving-average processing for noise reduction in color image signalsUS7570800Dec 14, 2005Aug 4, 2009Kla-Tencor Technologies Corp.Methods and systems for binning defects detected on a specimenUS20020054395 *Aug 8, 2001May 9, 2002Shinya KuboColor image processing apparatus executing moving-average processing for noise reduction in color image signalsUS20070133860 *Dec 14, 2005Jun 14, 2007Lin Jason ZMethods and systems for binning defects detected on a specimenUS20080007807 *Oct 12, 2006Jan 10, 2008Fujitsu LimitedImage processor and image processing methodUS20090290784 *Aug 3, 2009Nov 26, 2009Kla-Tencor Technologies CorporationMethods and systems for binning defects detected on a specimen* Cited by examinerClassifications U.S. Classification382/209, 382/270, 382/205International ClassificationG06K9/64, G06T7/20Cooperative ClassificationG06T7/20, G06K9/6203European ClassificationG06K9/62A1A, G06T7/20Legal EventsDateCodeEventDescriptionDec 6, 2005CCCertificate of correctionSep 24, 2008FPAYFee paymentYear of fee payment: 4Sep 28, 2012FPAYFee paymentYear of fee payment: 8RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services