Method for sliding window image processing of associative operators

• US 6,714,694 B1
• Filed: 11/27/2000
• Issued: 03/30/2004
• Est. Priority Date: 11/27/2000
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Marshall, Sidney W.
• Primary Examiner(s): Johnson, Timothy M.
• Assistant Examiner(s): Kassa, Yosef
• Application Number:
  US09/721,726
• Time in Patent Office: 1,219 Days
• Field of Search: 382/103, 382/104, 382/105, 382/106, 382/108, 382/109, 382/112, 382/113, 382/149, 382/171, 382/190, 382/252, 382/266, 382/274, 382/282, 382/284, 382/286, 382/294, 382/307, 382/309, 358/516, 358/519, 358/520, 358/450, 358/453, 358/463, 345/779, 345/781, 345/782, 345/783, 345/784, 345/788, 345/790, 345/797
• US Class Current: 382/307
• CPC Class Codes: G06T 5/20 using local operators

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.

Claims

1. 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.

2. The method as claimed in claim 1, wherein the second block dimensional length is greater than n.

3. The method as claimed in claim 1, wherein the second block dimensional length is equal to n.

4. The method as claimed in claim 1, wherein the blocks of data is blocks of image data.

5. The method as claimed in claim 1, wherein the associative operation is a function to determine a minimum data value within a window of data.

6. The method as claimed in claim 1, wherein the associative operation is a function to determine a maximum data value within a window of data.

7. The method as claimed in claim 1, wherein the associative operation is a function to logically AND all data values within a window of data.

8. The method as claimed in claim 1, wherein the associative operation is a function to logically OR all data values within a window of data.

9. The method as claimed in claim 1, wherein the execution of the associative operation upon each block of data in the first and second directions generating more than two stored window associative operation values and a plurality of stored partial window associative operation values.

10. 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 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.

11. The method as claimed in claim 10, wherein the second block dimensional length is greater than n.

12. The method as claimed in claim 10, wherein the second block dimensional length is equal to n.

13. The method as claimed in claim 10, wherein the blocks of data is blocks of image data.

14. The method as claimed in claim 10, wherein the associative operation is a function to determine a minimum data value within a window of data.

15. The method as claimed in claim 10, wherein the associative operation is a function to determine a maximum data value within a window of data.

16. The method as claimed in claim 10, wherein the associative operation is a function to logically AND all data values within a window of data.

18. The method as claimed in claim 10, wherein the execution of the associative operation upon each block of data in the first and second directions generating more than two stored window associative operation values and a plurality of stored partial window associative operation values.

17. The method as claimed in clam 10, wherein the associative operation is a function to logically OR all data values within a window of data.