SYSTEM, METHOD AND COMPUTER PROGRAM FOR AUTOMATED WINDOW MEMOIZATION

• US 20120268471A1
• Filed: 09/24/2010
• Published: 10/25/2012
• Est. Priority Date: 09/25/2009
• Status: Active Grant

• Current Assignee: Farzad Khalvati, Hamid R. Tizhoosh
• Original Assignee: Farzad Khalvati, Hamid R. Tizhoosh
• Inventors: Khalvati, Farzad, Tizhoosh, Hamid R.
• Granted Patent: US 9,076,240 B2
• Time in Patent Office: Days
• US Class Current: 345/522
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements

Abstract

The present invention provides a system, method and computer program providing automated window memoization which is an automated optimization of image processing. The method comprises inputting to a memoization compiler an image set, hardware or software code implementing one or more image processing algorithms, and one or more design parameters. The memoization compiler processes the image set for the image processing algorithms and implements hardware or software code for optimizing the image processing algorithms based on the design parameters.

Claims

1. A computer-implemented method for providing automated window memoization, the method characterized by inputting to a memoization compiler an image set comprising one or more images, input code implementing one or more image processing algorithms, and one or more design parameters, the memoization compiler operable to:

(a) apply the one or more image processing algorithms to the image set; and

(b) configure the one or more design parameters to optimize the one or more image processing algorithms by reducing computational redundancy when applying the one or more image processing algorithms to the image set.

2. The method as claimed in claim 1, characterized in that the image set comprises one or more images, wherein the method comprises the further steps of the memoization compiler segmenting the one or more images into a plurality of windows and the memoization compiler applying the one or more image processing algorithms to the plurality of windows.

3. The method as claimed in claim 2, characterized by the further steps of:

(a) a compression and hashing engine linked to the memoization compiler providing a string corresponding to each window; and

(b) the compression and hashing engine providing a memory address corresponding to each string;

wherein the memory address is associated with a memory location of a reuse table.

4. The method as claimed in claim 3, characterized by the further step of the memoization compiler checking, for each string, whether the memory location of the reuse table is associated with the string and, if so, obtaining a result from the memory location.

5. The method as claimed in claim 4, characterized in that the reducing computational redundancy includes maximizing a hit rate, the hit rate based on the proportion of results obtainable from one of the memory locations for the windows of one or more images.

6. The method as claimed in claim 3, characterized by the further steps of:

(a) the memoization compiler checking, for each string, whether the memory location of the reuse table is associated with the string;

(b) if the memory location of the reuse table is not associated with the string, the memoization compiler applying the one or more image processing algorithms to the window to obtain a result; and

(c) if the memory location of the reuse table is not associated with the string, the memoization compiler storing the string and the result to the memory location.

7. The method as claimed in claim 1, characterized in that the memoization compiler processes the image set for the one or more image processing algorithms and dynamically configures the one or more design parameters to optimize the one or more image processing algorithms.

8. The method as claimed in claim 1, characterized in that the memoization compiler is a hardware-based memoization module.

9. A system for providing automated window memoization, the system characterized by a memoization compiler having a plurality of inputs, the plurality of inputs enabling the input of an image set comprising one or more images, input code implementing one or more image processing algorithms, and one or more design parameters;

wherein the memoization compiler is operable to;

(a) apply the one or more image processing algorithms to the image set; and

(b) configure the one or more design parameters to optimize the one or more image processing algorithms by reducing computational redundancy when applying the one or more image processing algorithms to the image set.

10. The system as claimed in claim 9, characterized in that the image set comprises one or more images, wherein the memoization compiler is further operable to segment the one or more images into a plurality of windows and apply the one or more image processing algorithms to the plurality of windows.

11. The system as claimed in claim 10, further characterized by a compression and hashing engine linked to the memoization compiler, the compression and hashing engine operable to provide a string corresponding to each window, and a memory address corresponding to each string, wherein the memory address is associated with a memory location of a reuse table.

12. The system as claimed in claim 11, characterized in that the memoization compiler is operable to check, for each string, whether the memory location of the reuse table is associated with the string and, if so, obtain a result from the memory location.

13. The system as claimed in claim 12, characterized in that the reducing computational redundancy includes maximizing a hit rate, the hit rate based on the proportion of results obtainable from one of the memory locations for the windows of one or more images.

14. The system as claimed in claim 11, characterized in that the memoization compiler is further operable to:

(a) check, for each string, whether the memory location of the reuse table is associated with the string;

(b) if the memory location of the reuse table is not associated with the string, apply the one or more image processing algorithms to the window to obtain a result; and

(c) if the memory location of the reuse table is not associated with the string, store the string and the result to the memory location.

15. The system as claimed in claim 9, characterized in that the memoization compiler processes the image set for the one or more image processing algorithms and dynamically configures the one or more design parameters to optimize the one or more image processing algorithms.

16. The system as claimed in claim 9, characterized in that the memoization compiler is a hardware-based memoization module.

17. The system as claimed in claim 16, characterized in the memoization module is implemented by an n-wide superscalar pipeline.

18. The system as claimed in claim 17, characterized in that the n-wide superscalar pipeline is a 2-wide superscalar pipeline.

19. The system as claimed in claim 16, further characterized by a reuse table linked to the memoization module.

20. The system as claimed in claim 19, characterized in the reuse table is a two level reuse table.

21. The system as claimed in claim 19, characterized in the reuse table is an efficient memory based on parallel bloom filters.