Fuzzy match interpolated caching utilized in image-processsing applications

• US 8,879,121 B2
• Filed: 04/01/2013
• Issued: 11/04/2014
• Est. Priority Date: 04/01/2013
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Rumph, David E.
• Primary Examiner(s): TRAN, DUNG D
• Application Number:
  US13/854,243
• Publication Number:
  US 20140293355A1
• Time in Patent Office: 582 Days
• Field of Search: None
• US Class Current: 358/1.9
• CPC Class Codes: H04N 1/58 Edge or detail enhancement; Noise or error suppression, e.g. colour misregistration correction H04N1/62 takes precedence

Abstract

Methods and systems for color conversion used in image-processing. In one approach, a caching strategy can be employed rather than a direct computation or a precomputed table. To improve the hit frequency and reduce storage requirements, a hash calculation in addition to comparison operations can be processed as a “near match” rather than an exact match. In another approach, “fuzzy match” caching can be implemented to reach the proper vicinity in the n-dimensional space, and then interpolation (or extrapolation) can refine the result.

Claims

1. A method for computing trap values used in image-processing, said method comprising:

for each dimension of an input having at least two input values, quantizing said at least two input values using an image processor to produce quantized input values indicative of a pair of colors that define a center point of a hypercube that a cached node will represent;

combining said quantized input values into a cache lookup using a selected hash function; and

providing a lookup via said cache lookup with respect to said cached node utilizing said selected hash function, such that if said cache lookup provides a match, said cached node contains a correct result with respect to a cell center thereby allowing said cached node to be utilized not only for exact input colors but also for nearby colors, thereby increasing a frequency of matches and enhanced efficiency in a color conversion used in image processing.

2. The method of claim 1 wherein if said lookup misses, said cached node is populated with appropriate content on demand from an underlying algorithm.

3. The method of claim 1 wherein said cached node is capable of being recalculated and reached.

4. The method of claim 2 wherein said underlying algorithm comprises a least recently used algorithm.

5. A method for computing trap values used in image-processing, said method comprising:

quantizing an original input value with respect to each dimension of input data associated to produce at least one quantized input value and thereafter calculate a difference in dimension between said at least one quantized input value and said original input value;

combining said at least one quantized input value into a lookup table utilizing a selected hash function comprising at least one hash key to cache lookup a cached node containing a correct result for a cell center and extrapolation data in said each dimension to permit extrapolating from said cell center based on a distance in said input data from said cell center; and

calculating at least one extrapolated output value with respect to said extrapolation data appropriate to a dimension of an output thereof.

6. The method of claim 5 wherein if said cache lookup misses, said cached node is populated with appropriate content on demand from an underlying algorithm.

7. The method of claim 5 further comprising quantizing said original input value utilizing a truncation approach.

8. The method of claim 5 further comprising quantizing said original input value utilizing a rounding approach.

9. The method of claim 5 further comprising quantizing said original input value utilizing said lookup table, wherein said lookup table comprises a one-dimensional lookup table.

10. The method of claim 9 wherein if said cache lookup misses, said cached node is populated with appropriate content on demand.

11. The method of claim 6 further comprising quantizing said original input value utilizing a truncation approach or a rounding approach.

12. A system for computing trap values used in image-processing, said system comprising:

a processor;

a data bus coupled to said processor; and

a computer-usable medium embodying computer program code, said computer-usable medium being coupled to said data bus, said computer program code comprising instructions executable by said processor and configured for;

each dimension of an input having at least two input values, quantizing said at least two input values to produce quantized input values indicative of a pair of colors that define a center point of a hypercube that a cached node will represent;

combining said quantized input values into a cache lookup using a selected hash function; and

providing a lookup via said cache lookup with respect to said cached node utilizing said selected hash function, such that if said cache lookup provides a match, said cached node contains a correct result with respect to a cell center thereby allowing said cached node to be utilized not only for exact input colors but also for nearby colors, thereby increasing a frequency of matches and enhanced efficiency in a color conversion used in image processing.

13. The system of claim 12 wherein if said lookup misses, said cached node is populated with appropriate content on demand from an underlying algorithm.

14. The system of claim 12 wherein said cached node is capable of being recalculated and recached.

15. The system of claim 13 wherein said underlying algorithm comprises a least recently used algorithm.

16. A system for computing trap values used in image-processing, said system comprising:

a processor;

a data bus coupled to said processor; and

a computer-usable medium embodying computer program code, said computer-usable medium being coupled to said data bus, said computer program code comprising instructions executable by said processor and configured for;

quantizing an original input value with respect to each dimension of input data associated to produce at least one quantized input value and thereafter calculate a difference in dimension between said at least one quantized input value and said original input value;

combining said at least one quantized input value into a lookup table utilizing a selected hash function comprising at least one hash key to cache lookup a cached node containing a correct result for a cell center and extrapolation data in said each dimension to permit extrapolating from said cell center based on a distance in said input data from said cell center; and

calculating at least one extrapolated output value with respect to said extrapolation data appropriate to a dimension of an output thereof.

17. The system of claim 16 wherein if said cache lookup misses, said cached node is populated with appropriate content on demand from an underlying algorithm.

18. The system of claim 16 further comprising quantizing said original input value utilizing a truncation approach.

19. The system of claim 16 further comprising quantizing said original input value utilizing a rounding approach.

20. The system of claim 16 further comprising quantizing said original input value utilizing said lookup table, wherein said lookup table comprises a one-dimensional lookup table.