Image analysis – Image transformation or preprocessing – General purpose image processor
Reexamination Certificate
2000-11-27
2004-03-30
Johnson, Timothy M. (Department: 2625)
Image analysis
Image transformation or preprocessing
General purpose image processor
C382S282000, C382S285000
Reexamination Certificate
active
06714694
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the field of image processing and, more particularly, to the methods for implementing sliding-window digital image processing for associative operators such as MIN, MAX, AND, and OR.
BACKGROUND OF THE INVENTION
In the arts, there are instances in digital image processing systems, either in hardware or software, where one would like to calculate some property of the image in a sliding rectangular window. For example, knowing the average value of pixels in a region around a central pixel gives an indication that is useful for certain noise removal algorithms. As such, knowing the minimum and maximum value of a pixel in a window can be used to identify image regions that are “flat” or considered background.
In order to calculate an average for an interval along a scan line, one can add up the pixel values in the interval. To calculate the sum of the pixel values in an interval that is displaced by one pixel, the value of the pixel leaving the interval can be subtracted and the pixel value of the one entering the interval can be added for a total of two operations required to calculate the sum of the new interval. For long intervals, this is much faster than recalculating the sum of all the pixels in the new interval. This works because the addition operation is associative, commutative, and has an inverse operation, namely subtraction. This technique can be expanded to incrementally calculate the sum of the pixels in a rectangle that is slightly displaced. All of these techniques have limitations to which the present invention is directed, namely, that in certain image processing algorithms one wants to calculate a minimum or maximum value of a sliding window of values and, since the min or max function does not have an inverse the above method is inapplicable. As such, if the length of the sliding window is n and the window is slid m times, then an obvious implementation will use on the order of m*(n−1) operations.
What is needed in the art is a method which overcomes the limitations in the art and which is a faster implementation using less operations and whose time is better than proportional to the length of the window.
SUMMARY OF THE INVENTION
The present invention discloses a fast method of implementing sliding-window image processing for associative operators such as MIN, MAX, AND, and OR. For one dimension, the present method divides the image into blocks according to the sliding window size and for each block calculates two sets of partial results, one working from the left boundary of the block and the other working from the right boundary of the block. The partial results from two adjacent blocks can then be combined in one operation to give a final value for any window straddling two adjacent blocks. The total number of operations is proportional to 3M; where M is the scan length as compared to (n−1)M using prior art; where n is the length of the sliding window. The present invention can be extended to two-dimensional arrays and can be extended to support arbitrary window sizes.
DETAILED DESCRIPTION OF THE INVENTION
Often in a hardware or software digital imaging processing system a sliding window is employed across the digital image data and then, for each position of the window, a function of the windowed data is calculated. One example of a function which is often applied to such windowed data is operation of ADDITION. In this case, the value of the sum of a one-position displaced window is incrementally calculated from the sum of the original window by subtracting off the value that just left the sliding window and adding the value that just entered the sliding window. Because addition has an inverse operation, namely, SUBTRACTION, this methodology works well but it does not work at all for operations without an inverse such as MIN, MAX, AND, or OR. Even though these operations do not possess an inverse, the present invention utilizes the fact that these operations have an associative quality, i.e., (x op y) op z=x op (y op z). As such, the present invention provides an efficient method to speed up any operation that is without and inverse operation but is associative.
The present invention discloses a fast method of implementing sliding-window image processing for associative operators such as MIN, MAX, AND, and OR. For one dimension, the present method divides the image into blocks according to the sliding window size and for each block calculates two sets of partial results, one working from the left boundary of the block and the other working from the right boundary of the block. The partial results two adjacent blocks can then be combined in one operation to give a final value for any window straddling two adjacent blocks. Moreover, the present invention can not only be extended to arbitrary window sizes but can also be applied to each dimension independently.
Briefly, the method of the present invention involves the first step of, for a sliding window of size n, the data is first divided into (n+1)-element blocks. Then, for each element in the block starting from the left end of the block the operation is successively applied to the previous result and the next element of the block. Similarly, from the right end of the block the operation is successively applied to the previous result and the next element of the block. At this point, it should be understood that one does not need to calculate the operation across the entire block as this would be across n+1 elements and the sliding window contains only n elements. The next step of the method of the present invention involves the step of for each position of the sliding window determining which block or blocks lie under the sliding window and, if this is a single block, retrieving the value calculated for the elements of the sliding window, or if there are two blocks, combining the previously calculated values in each block corresponding to the part of the sliding window contained in the block. It takes n−1 operations to calculate the left-end results in each block, n−1 operations to calculate the right-end results in each block, and n−1 operations to calculate the n−1 possible overlap positions thereby generating a total of 3*n−3 operations to calculate n+1 windowed results. Note that two of the sliding window positions do not overlap two blocks and no further calculation is necessary in these cases. This averages to less than 3 operations per calculated value.
For example, to calculate a MIN function in a sliding window of length n, an appropriate block size is n+1 because a window of size n always contains an edge of every block it intersects. Then, in each block, calculate and remember successive cumulative minimums from the left edge and then from the right edge. Now, for any position of the sliding window, the minimum in the sliding window can be calculated with at most one more MIN operation. If the sliding window is completely contained in a single block then either the left edge of the sliding window coincides with the left edge of the containing block or the right edge of the sliding window coincides with the right edge of the containing block and the minimum has already been calculated. If the sliding window overlaps two blocks then the minimum in the sliding window can be calculated by taking the minimum of the part of the left block overlapped by the sliding window and the part of the right block overlapped by the sliding window and both of these values have been previously calculated. The total number of operations for this example is (n−1 operations per block for calculations from the left end of the block)+(n−1 operations per block for calculations from the right end of the block)+(n−1 operations to combine results for cases where the sliding window straddles two blocks)+(0 operations in the two cases when the sliding window is contained within a single block)=3n−3 operations to handle n+1 positions of the sliding wi
Johnson Timothy M.
Kassa Yosef
Xerox Corporation
LandOfFree
Method for sliding window image processing of associative... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for sliding window image processing of associative..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for sliding window image processing of associative... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3277536