US 6,714,694 B1Granted

Method for sliding window image processing of associative operators

AssigneeXerox Corporation

InventorSidney W. Marshall

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for implementing sliding-window image processing for associative operators such as MIN, MAX, AND, and OR is disclosed. 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.

Claims18

Dependent claims

A method of implementing a sliding-window associative operation upon a set of data, the window used in the sliding-window associative operation having a first window dimensional length of m and a second window dimensional length of n, comprising:

(a) dividing the set of image data into a plurality of blocks of data, the blocks of data having a first block dimensional length and a second block dimensional length, the first block dimensional length being greater than m;
(b) executing an associative operation upon each block of data in a first direction and storing the results thereof;
(c) executing the associative operation upon each block of data in a second direction and storing the results thereof, the execution of the associative operation upon each block of data in the first and second directions generating two stored window associative operation values and a plurality of stored partial window associative operation values;
(d) executing a sliding-window associative operation, when the window used in the sliding-window associative operation overlays a portion of a first block of data and a portion of a second block of data, to generate a window associative operation value for the window of data being operated upon, the sliding-window associative operation being executed upon a stored partial window associative operation value associated with the first block of data underlying the window and a stored partial window associative operation value associated with the second block of data underlying the window to generate;
and
(e) retrieving, when the window used in the sliding-window associative operation overlays only a single block of data, a stored window associative operation value associated with the single block of data, the retrieved window associative operation value being the window associative operation value for the window of data being operated upon.

3 more elements

(a) dividing the set of image data into a plurality of blocks of data, the blocks of data having a first block dimensional length and a second block dimensional length, the first block dimensional length being greater than m;
(b) executing an associative operation upon each block of data in a first direction and storing the results thereof;
(c) executing the associative operation upon each block of data in a second direction and storing the results thereof, the execution of the associative operation upon each block of data in the first and second directions generating at least two stored window associative operation values and a plurality of stored partial window associative operation values;
(d) executing a sliding-window associative operation, when the window used in the sliding-window associative operation overlays a portion of a first block of data and a portion of a second block of data, to generate a window associative operation value for the window of data being operated upon, the sliding-window associative operation being executed upon a stored partial window associative operation value associated with the first block of data underlying the window and a single data value associated with the second block of data underlying the window to generate;
and
(e) retrieving, when the window used in the sliding-window associative operation overlays only a single block of data, a stored window associative operation value associated with the single block of data, the retrieved window associative operation value being the window associative operation value for the window of data being operated upon.

3 more elements

Dependencies are inferred from the claim text.