Multi-Dimensional look-up table generation via adaptive node selection based upon color characteristics of an input image

• US 7,706,034 B2
• Filed: 09/11/2007
• Issued: 04/27/2010
• Est. Priority Date: 09/11/2007
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Bala, Raja, Monga, Vishal
• Primary Examiner(s): Zimmerman; Mark K
• Assistant Examiner(s): Cato; Miya J
• Application Number:
  US11/853,652
• Publication Number:
  US 20090067017A1
• Time in Patent Office: 959 Days
• Field of Search: 358/1.9, 358/518, 358/520, 358/522, 358/523, 382/162, 382/167, 345/600, 345/601
• US Class Current: 358/520
• CPC Class Codes: G09G 2340/10 Mixing of images, i.e. displayed pixel being the result of an operation, e.g. adding, on the corresponding input pixels
• CPC Class Codes: G09G 5/06 using colour palettes, e.g. look-up tables
• CPC Class Codes: H04N 1/6019 using look-up tables H04N1/6025 takes precedence

Abstract

What is provided is a system and method for node set construction and look-up table generation to transform image data in the form of color values of an input color image in an input color space to an output color space of an image output system. In the present method, node locations are selected based upon an importance value generated by a significance function which describes a relative importance of a given color value in the input image or a region thereof. A distance weighting function is also provided which is applied to the significance function to balance the significance of a given node against a relative positioning of all other nodes in the multi-dimensional grid. Nodes can be added or deleted according to methods also described herein. Accordingly, a multi-dimensional look-up table is generated wherein node tiling is based upon a significance of color values of an input image.

Claims

1. A method for multi-dimensional look-up table generation via adaptive node selection based upon characteristics of an input image, the method comprising:

receiving, from an image acquisition system, image data representing an input image, said image data comprising a set S of input values of at least a region of said input image, said input values determined to be statistically representative of color values in said input image;

obtaining, from a significance function generator, a significance function describing a relative importance of a transformation accuracy of input values in S to a multi-dimensional look-up table useful for transforming said input values from an input color space to an output color space, said multi-dimensional look-up table comprising a multi-dimensional grid having a node located at each intersection thereof, output color values being stored at each node location, each node being accessible by an input index value, said input values being used to determine respective input index values;

applying, using a dampening function generator, a distance weighting function to said significance function to produce a distance-weighted significance function, said distance weighting function balancing said significance function against a relative positioning of all of nodes in said multi-dimensional look-up table, said distance weighting function controlling a distance between adjacent nodes and comprises;

d(x,y)≧

0,∀

x,yε

V, and d(x,y)=0x=n_max;

and

performing, using an image processing system;

determining a significance value for said input values in set S using said distance-weighted significance function;

sorting said significance values for all inputs in S;

for each of a predetermined number of nodes;

identifying a location in said multi-dimensional look-up table where the input value has a maximum significance value; and

selecting a node at said identified location;

constructing a set of nodes N from said selected nodes;

generating a look-up table from said set of nodes N;

post-processing said set of nodes N to obtain any of a minimum spacing between nodes and a desired lattice size; and

providing said generated look-up table to an image output system configured to generate a hardcopy output image based upon output values retrieved from said generated look-up table.

2. The method of claim 1, wherein said input values comprise any of:

values for the most significant colors in said input image;

values selected based upon a visual inspection of said input image; and

all input RGB values of said input image.

3. The method of claim 1, wherein said significance function is a histogram of colors within a chosen subset of said input values, said importance being dictated by a frequency of colors within S.

4. The method of claim 1, wherein said significance function is a user defined function that emphasizes memory colors for which a characteristic of an object influences a human perception of its color in favor for other colors, wherein if a large region of said input image has one or more objects with a same color, said user selecting S to increase a significance of that color and thus increase an accuracy of color transformations in a vicinity of that color.

5. The method of claim 1, wherein said distance weighting function d(x, y) comprises:

d(x,y)=(1−

e<sup>−

α

∥

x−

y∥

2</sup>),

where α

is a positive, scalar value, and the distance between adjacent nodes being controlled by varying α

, such that, for a given x and y, an increase in α

results in a decrease in e<sup>−

α

∥

x−

y∥

2</sup> and causes d(x, y) to approach 1.

6. The method of claim 1, wherein post-processing said set of nodes N to obtain said minimum spacing between nodes comprising eliminating at least one of said selected nodes to achieve a minimum allowable node spacing along a k^th dimension.

7. The method of claim 6, wherein eliminating at least of said selected nodes comprises:

wherein M is a number of nodes selected, n_j, j=1, 2, . . . , M,

wherein n₁, n₂, . . . , n_M are sorted scalar values of nodes in said k^th dimension, such that;

n₁≦

n₂≦

. . . n_M,

wherein p_k(n) is a separable weighting function for said k^th dimension obtained from a joint multi-dimensional profile p(x),

wherein n₀=n_min and n_m+1=n_max,

wherein p(n_min)=p(n_max)=1,

A) selecting Δ

_min as a minimum allowable spacing along said k^th dimension;

B) adding boundary nodes n_min and n_max to node set N to obtain node set N′

;

C) for each node in node set N′

, beginning with n_j=n_max;

i) determining whether n_j+1−

n_j<

Δ

_min for a node having a highest significance value, and if not, said spacing between node levels being sufficient; and

ii) otherwise determining whether p(n_j+1)>

p(n_j) at node level n_j, and if so retaining node level n_j+1 and eliminating node level n_j, otherwise retaining node level n_j and eliminating node level n_j+1; and

D) generating node set N″

having said selected minimum allowable spacing.

8. The method of claim 1, wherein post-processing said set of nodes N to obtain a desired lattice size comprises adding at least one node between two of said selected nodes wherein a same number of nodes levels is required along a k^th dimension.

9. The method of claim 8, wherein adding at least one node between two of said selected nodes comprises:

wherein M is a number of nodes selected, node n_j, j=1, 2, . . . M,

wherein P_k is a size of an input look-up table in said k^th dimension such that P_k≧

M makes a lattice of size P₁×

P₂×

P₃,

wherein n₁ through n_N are sorted scalar values of nodes along said k^th dimension, with N<

P_k,

A) adding boundary values n_min and n_max to node set N to obtain node set N′

;

B) repeating, for each node in node set N″

, until n*=n_M;

i) determining node n*=(n_j n_j+1)/2; and

ii) inserting node n* between nodes n_j and n_j+1; and

C) generating a node set N′

″

having a final lattice of size;

10. A system for multi-dimensional look-up table generation via adaptive node selection based upon characteristics of an input image, the method comprising:

an image acquisition system configured to receive image data representing an input image, said image data comprising a set S of input values of at least a region of said input image, said input values determined to be statistically representative of color values in said input image;

a significance function generator configured to provide a significance function describing a relative importance of a transformation accuracy of input values in S to a multi-dimensional look-up table useful for transforming said input values from an input color space to an output color space, said multi-dimensional look-up table comprising a multi-dimensional grid having a node located at each intersection thereof, output color values being stored at each node location, each node being accessible by an input index value, said input values being used to determine respective input index values;

applying, using a dampening function generator, a distance weighting function to said significance function to produce a distance-weighted significance function, said distance weighting function balancing said significance function against a relative positioning of all of nodes in said multi-dimensional look-up table, said distance weighting function controlling a distance between adjacent nodes and comprises;

d(x,y)≧

0,∀

x,yε

V, and d(x,y)=0x=n_max;

an image processing system configured to perform;

determining a significance value for said input values in set S using said distance-weighted significance function;

sorting said significance values for all inputs in S;

for each of a predetermined number of nodes;

identifying a location in said multi-dimensional look-up table where the input value has a maximum significance value; and

selecting a node at said identified location;

constructing a set of nodes N from said selected nodes; and

generating a look-up table from said set of nodes N;

post-processing said set of nodes N to obtain any of a minimum spacing between nodes and a desired lattice size; and

an image output system configured to generate a hardcopy output image based upon output values retrieved from said generated look-up table.

11. The system of claim 10, wherein said input values comprise any of:

values for the most significant colors in said input image;

values selected based upon a visual inspection of said input image; and

all input RGB values of said input image.

12. The system of claim 10, wherein said significance function is a histogram of colors within a chosen subset of said input values, said importance being dictated by a frequency of colors within S.

13. The system of claim 10, wherein said significance function is a user defined function that emphasizes memory colors for which a characteristic of an object influences a human perception of its color in favor for other colors, wherein if a large region of said input image has one or more objects with a same color, said user selecting S to increase a significance of that color and thus increase an accuracy of color transformations in a vicinity of that color.

14. The system of claim 10, wherein said distance weighting function d(x, y) comprises:

d(x,y)=(1−

e<sup>−

α

∥

x−

y∥

2</sup>),

where α

is a positive, scalar value, and the distance between adjacent nodes being controlled by varying α

, such that, for a given x and y, an increase in α

results in a decrease in e<sup>−

α

∥

x−

y∥

2</sup> and causes d(x, y) to approach 1.

15. The system of claim 10, wherein post-processing said set of nodes N to obtain said minimum spacing between nodes comprising eliminating at least one of said selected nodes to achieve a minimum allowable node spacing along a k^th dimension.

16. The system of claim 15, wherein eliminating at least of said selected nodes comprises:

wherein M is a number of nodes selected, n_j, j=1, 2, . . . , M,

wherein n₁, n₂, . . . , n_M are sorted scalar values of nodes in said k^th dimension, such that;

n₁≦

n₂≦

. . . n_M,

wherein p_k(n) is a separable weighting function for said k^th dimension obtained from a joint multi-dimensional profile p(x),

wherein n₀=n_min, and n_m+1=n_max,

wherein p(n_min)=p(n_max)=1,

A) selecting Δ

_min as a minimum allowable spacing along said k^th dimension;

B) adding boundary nodes n_min and n_max to node set N to obtain node set N′

;

C) for each node in node set N′

, beginning with n_j=n_max;

i) determining whether n_j+1−

n_j<

Δ

_min for a node having a highest significance value, and if not, said spacing between node levels being sufficient; and

ii) otherwise determining whether p(n_j+1)>

p(n_j) at node level n_j, and if so retaining node level n_j+1 and eliminating node level n_j, otherwise retaining node level n_j and eliminating node level n_j+1; and

D) generating node set N″

having said selected minimum allowable spacing.

17. The system of claim 10, wherein post-processing said set of nodes N to obtain a desired lattice size comprises adding at least one node between two of said selected nodes wherein a same number of nodes levels is required along a k^th dimension.

18. The system of claim 17, wherein adding at least one node between two of said selected nodes comprises:

wherein M is a number of nodes selected, node n_j, j=1, 2, . . . , M,

wherein P_k is a size of an input look-up table in said k^th dimension such that P_k M makes a lattice of size P₁×

P₂×

P₃,

wherein n₁ through n_N are sorted scalar values of nodes along said k^th dimension, with N<

P_k,

A) adding boundary values n_min and n_max to node set N to obtain node set N′

;

B) repeating, for each node in node set N″

, until n*=n_M;

i) determining node n*=(n_j n_j+1)/2; and

ii) inserting node n* between nodes n_j and n_j+1; and

C) generating a node set N′

″

having a final lattice of size;