Conversions between standard color spaces

• US 6,758,574 B1
• Filed: 10/29/1999
• Issued: 07/06/2004
• Est. Priority Date: 10/29/1999
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Roberts, Peter Malcolm
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US09/430,021
• Time in Patent Office: 1,712 Days
• Field of Search: 382/162, 382/167, 358/518, 358/519, 358/523, 345/603, 345/604
• US Class Current: 362/162
• CPC Class Codes: H04N 1/6011 with simulation on a subsidiary picture reproducer H04N1/622 takes precedence; matching two or more picture reproducers H04N1/6052
• CPC Class Codes: H04N 1/646 Transmitting or storing colour television type signals, e.g. PAL, Lab; Their conversion into additive or subtractive colour signals or vice versa therefor H04N1/642, H04N1/644 take precedence

Abstract

Disclose are various methods for optimising conversions between color spaces (FIG. 1). A set of atomic mathematical ((a)-(f)) functions are identified which, when performed in sequence, implement the conversions. Specific (first) sequences of the mathematical functions are then identified which when preformed convert colors between particular color spaces. A set of computational operations ((g)-(i)) are then established for evaluation using a computing device, the operations, when performed in (second) sequences cause the color conversions. A particular one of the first sequences required for converting from a first color space to a second color space is then identified and transformed into a (third) sequence of computational operations chosen from the computational operations ((g)-(i)) having substantially the same transformation effect as the particular sequence. Also disclosed is a method of sequentially combining a first color conversion list (FIG. 2A) with a second color conversion list (FIG. 2B) to form a single output conversion list (FIG. 2C) having a corresponding conversion function, each conversion list traversing a chain of color spaces comprising at least a corresponding source color space and a corresponding terminal color space. Also disclosed is a method of determining a processing gamut for intermediate color spaces (304, 306) traversed in a color conversion chain (300) from a source color space (302) to a target color space (308).

Claims

1. A method of optimising conversions between colour spaces, said method comprising the steps of:

(i) identifying a set of mathematical functions which, when performed in sequence, implement said conversions between colour spaces;

(ii) identifying a set of computational operations for evaluation using a computing device, said operations, when performed in (first) sequence cause said colour conversions;

(iii) identifying at least one particular sequence of said mathematical functions which when performed converts colours between a first colour space and a second colour space;

(iv) transforming said particular sequence into a (second) sequence of computational operations chosen from said set of computational operations having substantially the same transformation effect as said particular sequence.

2. A method according to claim 1 wherein steps (iii) and (iv) are performed at a time at which a colour conversion is requested (run-time).

3. A method according to claim 2 wherein said computational operations each have a corresponding (first) computational accuracy and an output of each said mathematical function has a corresponding (second) computational accuracy, and when said corresponding second computational accuracy is better than said corresponding first computational accuracy, said method comprises the further step of modifying said second sequence of operations to minimise an effect of the limited accuracy of the computational operation.

4. A method according to claim 3 wherein said modifying comprises combining a plurality of said computational operations into a single said computational operation.

5. A method according to claim 3 wherein said modifying utilises a state table related to said mathematical functions and a set of states each representing a particular relationship between the corresponding first and second computational accuracies.

6. A method according to claim 2 wherein said set of operations comprises functions selected from the group consisting of:

a matrix multiplication;

a one-dimensional look-up table; and

a multi-dimensional look-up table.

7. A method according to claim 2 wherein said set of mathematical functions comprises functions selected from the group consisting of:

a single variate function;

a single variate function expressed as a look-up table;

a multi-variate function;

a multi-variate function expressed as a look-up table; and

a matrix multiplication.

8. A method according to claim 2 wherein at least part of step (ii) is performed at said time.

9. A method according to claim 1 wherein said second colour space is said first colour space.

14. A method according to claim 1 wherein step (iii) comprises sequentially combining at least two sequences of said mathematical functions to form a single sequence which has the same effect of said at least two when executed.

15. A method according to claim 14, wherein said sequentially combining comprises the sub-steps of:

(ii-a) comparing a last function of a first said sequence and a first function of a second said sequence;

(ii-b) removing both said functions from said sequences if said functions are the mathematical inverse of one another;

(ii-c) repeating steps (ii-a) and (ii-b) until the two said functions are not the mathematical inverse of one another; and

(ii-d) combining the two sequences at a current last function of the first sequence and at a current first function of the second sequence.

16. A method according to claim 1 wherein step (iv) comprises determining a processing gamut for intermediate colour spaces traversed in a colour conversion chain from said first colour space to said second colour space, said determining comprising the substeps of:

(iv-a) forward processing said chain to determine, based from a gamut of said first colour space, an input bounding box of values for each remaining colour space in said chain;

(iv-b) reverse processing said chain to determine, based from a gamut of said second output colour space, an output bounding box for each preceding colour space in said chain;

(iv-c) for each colour space in said chain, determining an intersection between the corresponding input and output bounding boxes to establish a processing gamut for said colour space in said conversion.

17. A method according to claim 16 of wherein steps (iv-a), (iv-b) and (iv-c) comprise:

forming a first list of critical colours in said first colour space;

for each intermediate colour space in said chain, forming a corresponding first list of said critical colours in said intermediate colour space;

for each said intermediate colour space in said chain, forming a corresponding first bounding box enclosing the corresponding first list of critical colours;

forming a second list of critical colours for said second colour space;

for each said intermediate colour space in said chain, transforming said second list of critical colours into a corresponding second list of critical colours for said corresponding intermediate colour space;

for each said intermediate colour space, forming a second bounding box enclosing the corresponding said second list of critical colours; and

for each said intermediate colour space in said chain, reducing said corresponding first bounding box to form an intersection with said corresponding second bounding box, said intersection defining said processing gamut for the corresponding intermediate colour space.

10. A method of optimising a conversion between a first colour space and a second colour space, said conversion traversing a chain of colour spaces including said first and second colour spaces and at least one intermediate colour space between said first and second colour spaces, said method comprising the steps of:

(i) identifying a first set of mathematical functions each defining a conversion between adjacent colour spaces within said chain;

(ii) reducing said first set of mathematical functions to define a second set of computational functions, for converting between said first and second colour spaces; and

(iii) performing a conversion from said first colour space to said second colour space using said second set of functions.

11. A method according to claim 10 wherein step (ii) is performed at a time at which a colour conversion is requested (run-time).

12. A method according claim 11 wherein said first set of mathematical functions is unbounded by computational accuracy, said method comprising the further step of establishing a level of computational accuracy for each conversion of step (i) between adjacent colour spaces in said chain, wherein said second set of computational functions are bounded by a corresponding established level of computational accuracy.

13. A method according to claim 12 wherein said second set of functions comprises functions selected from the group consisting of:

a matrix multiplication;

a one-dimensional look-up table; and

a multi-variate look-up table.

18. A computer readable medium, having a program recorded thereon, where the program is configured to make a computer execute a procedure for optimising conversions between colour spaces, said program comprising:

(i) code for identifying a set of mathematical functions which, when performed in sequence, implement said conversions between colour spaces;

(ii) code for identifying a set of computational operations for evaluation using a computing device, said operations, when performed in (first) sequence cause said colour conversions;

(iii) code for identifying at least one particular sequence of said mathematical functions which when performed converts colours between a first colour space and a second colour space;

(iv) code for transforming said particular sequence into a (second) sequence of computational operations chosen from said set of computational operations having substantially the same transformation effect as said particular sequence.

19. A computer readable medium according to claim 18 wherein said computational operations each have a corresponding (first) computational accuracy and an output of each said mathematical function has a corresponding (second) computational accuracy, and when said corresponding second computational accuracy is better than said corresponding first computational accuracy, said method comprises the further step of modifying said second sequence of operations to minimise an effect of the limited accuracy of the computational operation.

20. A computer readable medium according to claim 19 wherein said modifying comprises combining a plurality of said computational operations into a single said computational operation.

21. A computer readable medium according to claim 19 wherein said modifying utilises a state table related to said mathematical functions and a set of states each representing a particular relationship between the corresponding first and second computational accuracies.

22. A computer readable medium according to claim 18 wherein said set of operations comprises functions selected from the group consisting of:

a matrix multiplication;

a one-dimensional look-up table; and

a multi-dimensional look-up table.

23. A computer readable medium according to claim 18 wherein said set of mathematical functions comprises functions selected from the group consisting of:

a single variate function;

a single variate function expressed as a look-up table;

a multi-variate function;

a multi-variate function expressed as a look-up table; and

a matrix multiplication.

24. A computer readable medium according to claim 18 wherein code (iii) and (iv) are performed at a time at which a colour conversion is requested (run-time).

25. A computer readable medium according to claim 24 wherein at least part of code (ii) is performed at said time.

26. A computer readable medium according to claim 18 wherein said second colour space is said first colour space.

30. A computer readable medium according to claim 18 wherein code (iii) comprises code for sequentially combining at least two sequences of said mathematical functions to form a single sequence which has the same effect of said at least two when executed.

31. A computer readable medium according to claim 30, wherein said sequentially combining comprises code for:

(ii-a) comparing a last function of a first said sequence and a first function of a second said sequence;

(ii-b) removing both said functions from said sequences if said functions are the mathematical inverse of one another;

(ii-c) repeating steps (ii-a) and (ii-b) until the two said functions are not the mathematical inverse of one another; and

(ii-d) combining the two sequences at a current last function of the first sequence and at a current first function of the second sequence.

32. A computer readable medium according to claim 18 wherein said code (iv) comprises further code for determining a processing gamut for intermediate colour spaces traversed in a colour conversion chain from said first colour space to said second colour space, said further code comprising code for:

(iv-a) forward processing said chain to determine, based from a gamut of said first colour space, an input bounding box of values for each remaining colour space in said chain;

(iv-b) reverse processing said chain to determine, based from a gamut of said second output colour space, an output bounding box for each preceding colour space in said chain;

(iv-c) for each colour space in said chain, determining an intersection between the corresponding input and output bounding boxes to establish a processing gamut for said colour space in said conversion.

33. A computer readable medium according to claim 32 of wherein further code (iv-a), (iv-b) and (iv-c) comprise code for:

forming a first list of critical colours in said first colour space;

for each intermediate colour space in said chain, forming a corresponding first list of said critical colours in said intermediate colour space;

for each said intermediate colour space in said chain, forming a corresponding first bounding box enclosing the corresponding first list of critical colours;

forming a second list of critical colours for said second colour space;

for each said intermediate colour space in said chain, transforming said second list of critical colours into a corresponding second list of critical colours for said corresponding intermediate colour space;

for each said intermediate colour space, forming a second bounding box enclosing the corresponding said second list of critical colours; and

for each said intermediate colour space in said chain, reducing said corresponding first bounding box to form an intersection with said corresponding second bounding box, said intersection defining said processing gamut for the corresponding intermediate colour space.

27. A computer readable medium, having a program recorded thereon, where the program is configured to make a computer execute a procedure for optimising a conversion between a first colour space and a second colour space, said conversion traversing a chain of colour spaces including said first and second colour spaces and at least one intermediate colour space between said first and second colour spaces, said program comprising:

(i) code for identifying a first set of mathematical functions each defining a conversion between adjacent colour spaces within said chain;

(ii) code for reducing said first set of mathematical functions to define a second set of computational functions, for converting between said first and second colour spaces; and

(iii) code for performing a conversion from said first colour space to said second colour space using said second set of functions.

28. A computer readable medium according claim 27 wherein said first set of mathematical function are unbounded by computational accuracy, said method comprising the further step of establishing a level of computational accuracy for each conversion of code (i) between adjacent colour spaces in said chain, wherein said second set of computational functions are bounded by a corresponding established level of computational accuracy.

29. A computer readable medium according to claim 28 wherein said second set of functions comprises functions selected from the group consisting of:

a matrix multiplication;

a one-dimensional look-up table; and

a multi-variate look-up table.

34. Apparatus for optimising conversions between colour spaces, said apparatus comprising:

first means for identifying a set of mathematical functions which, when performed in sequence, implement said conversions;

second means for identifying (first) sequences of said mathematical functions which when preformed convert colours between said colour spaces;

third means for identifying a set of computational operations for evaluation using a computing device, said operations, when performed in (second) sequences cause said colour conversions;

fourth means for identifying a particular one of said first sequences required for converting from a first colour space to a second colour space; and

fifth means for transforming said particular sequence into a (third) sequence of computational operations chosen from said set of computational operations having substantially the same transformation effect as said particular sequence.

35. Apparatus according to claim 34 wherein said computational operations each have a corresponding (first) computational accuracy and an output of each said mathematical function has a corresponding (second) computational accuracy, and when said corresponding second computational accuracy is better than said corresponding first computational accuracy, said method comprises the further step of modifying said second sequence of operations to minimise an effect of the limited accuracy of the computational operation.

36. Apparatus according to claim 35 wherein said modifying comprises combining a plurality of said computational operations into a single said computational operation.

37. Apparatus according to claim 35 wherein said modifying utilises a state table related to said mathematical functions and a set of states each representing a particular relationship between the corresponding first and second computational accuracies.

38. Apparatus according to claim 34 wherein said second set of operations comprises functions selected from the group consisting of:

a matrix multiplication;

a one-dimensional look-up table; and

a multi-variate look-up table.

39. Apparatus according to claim 34 wherein said set of mathematical functions comprises functions selected from the group consisting of:

a single variate function;

a single variate function expressed as a look-up table;

a multi-variate function;

a multi-variate function expressed as a look-up table; and

a matrix multiplication.

40. A method of sequentially combining two sequences of colour conversion functions to form a single sequence for conversion between colour spaces, the single sequence having the same effect of said two sequences when executed, said method comprising the steps of:

(a) comparing a last function of a first said sequence and a first function of a second said sequence;

(b) removing both said functions from said sequences if said functions are an inverse of one another;

(c) repeating steps (a) and (b) until the two said functions are not the inverse of one another; and

(d) combining the two sequences at a current last function of the first sequence and at a current first function of the second sequence to obtain the single sequence of colour conversions functions.

41. A method according to claim 40 wherein said two sequences of functions are drawn from a set of such sequences which define colour conversions from a base colour space to and from a set of required colour spaces.

42. A method according to claim 41 wherein said base colour space is the CIE XYZ colour space.

43. A method according to claim 40 wherein one of said colour spaces in at least two of said input sequencies comprises the XYZ colour space.

44. A method of combining a sequential plurality of colour conversion lists to form a single composite colour conversion list having a corresponding conversion function, each said conversion list traversing a chain of colour spaces comprising at least a corresponding source colour space and a corresponding terminal colour space, said method comprising the steps of:

(i) identifying from said input lists an adjacent sequential pair of lists and designating the same as a first input list and a second input list respectively;

(ii) performing the method of claim 40 on said designated first and second input lists to form a corresponding output list;

(iii) substituting said output list into said sequence of said input lists in place of said first and second lists; and

(iv) repeating steps (i) to (iii) until a single list remains and designating said single list as said composite list.

45. A method according to claim 44 wherein one of said colour spaces in at least two of said input lists comprises the XYZ colour space.

47. A computer readable medium, having a program recorded thereon, where the program is configured to make a computer execute a procedure for combining a sequential plurality of colour conversion lists to form a single composite colour conversion list having a corresponding conversion function, each said conversion list traversing a chain of colour spaces comprising at least a corresponding source colour space and a corresponding terminal colour space, said program comprising:

(i) code for identifying from said input lists an adjacent sequential pair of lists and designating the same as a first input list and a second input list respectively;

(ii) code for performing the method of claim 40 on said designated first and second input lists to form a corresponding output list;

(iii) code for substituting said output list into said sequence of said input lists in place of said first and second lists; and

(iv) code for repeatedly calling code (i) to (iii) until a single list remains and designating said single list as said composite list.

48. A computer readable medium according to claim 47 wherein one of said colour spaces in at least two of said input lists comprises the XYZ colour space.

53. Apparatus for combining a sequential plurality of colour conversion lists to form a single composite colour conversion list having a corresponding conversion function, each said conversion list traversing a chain of colour spaces comprising at least a corresponding source colour space and a corresponding terminal colour space, said apparatus comprising the steps o£

first means for identifying from said input lists an adjacent sequential pair of lists and designating the same as a first input list and a second input list respectively;

second means for performing the method of claim 40 on said designated first and second input lists to form a corresponding output list;

third means for substituting said output list into said sequence of said input lists in place of said first and second lists; and

fourth means for repeatedly invoking said first second and third means until a single list remains and designating said single list as said composite list.

54. Apparatus according to claim 53 wherein one of said colour spaces in at least two of said input lists comprises the XYZ colour space.

46. A computer readable medium, having a program recorded thereon, where the program is configured to make a computer execute a procedure for sequentially combining a first colour conversion list with a second colour conversion list to form a single output conversion list having a corresponding conversion function, each said conversion list traversing a chain of colour spaces comprising at least a corresponding source colour space and a corresponding terminal colour space, said program comprising:

(a) code for comparing said terminal colour space of said first list with said source colour space of said second list;

(b) code for terminating said combining where said terminal colour space of said first list does not correspond to said source colour space of said second list;

(c) code for, where said terminal colour space of said first list corresponds to said source colour space of said second list;

(ca) marking one of the compared said terminal or source colour spaces as an intermediate colour space and assigning in each said list a next adjacent colour space as the corresponding terminal colour space and source colour space respectively;

(cb) comparing said assigned terminal colour space of said first list with said assigned source colour space of said second list;

(cc) where said assigned colour spaces correspond, invoking a repeat of code (ca) on said assigned terminal and source colour spaces; and

(cd) where said assigned colour spaces do not correspond, joining said lists between a current said intermediate colour space and said assigned colour space of the other said list.

49. A computer readable medium, having a program recorded thereon, where the program is configured to make a computer execute a procedure for sequentially combining two sequences of colour conversion functions to form a single sequence for conversion between colour spaces, the single sequence having the same effect of said two sequences when executed, said program comprising code for the steps of:

(a) comparing a last function of a first said sequence and a first function of a second said sequence;

(b) removing both said functions from said sequences if said functions are an inverse of one another;

(c) repeating steps (a) and (b) until the two said functions are not an inverse of one another; and

(d) combining the two sequences at a current last function of the first sequence and at a current first function of the second sequence to obtain the single sequence of colour conversion functions.

50. A computer readable medium according to claim 49 wherein said two sequences of functions are drawn from a set of such sequences which define colour conversions from a base colour space to and from a set of required colour spaces.

51. A computer readable medium according to claim 50 wherein said base colour space is the CIE XYZ colour space.

52. Apparatus for sequentially combining a first colour conversion list with a second colour conversion list to form a single output conversion list having a corresponding conversion function, each said conversion list traversing a chain of colour spaces comprising at least a corresponding source colour space and a corresponding terminal colour space, said apparatus comprising the steps of:

means for comparing said terminal colour space of said first list with said source colour space of said second list;

means for determining where said terminal colour space of said first list does not correspond to said source colour space of said second list, and if so, terminating said combining; and

where said terminal colour space of said first list corresponds to said source colour space of said second list, means for;

(ca) marking one of the compared said terminal or source colour spaces as an intermediate colour space and assigning in each said list a next adjacent colour space as the corresponding terminal colour space and source colour space respectively;

(cb) comparing said assigned terminal colour space of said first list with said assigned source colour space, of said second list;

(cc) where said assigned colour spaces correspond, repeating (ca) on said assigned terminal and source colour spaces; and

(cd) where said assigned colour spaces do not correspond, joining said lists between a current said intermediate colour space and said assigned colour space of the other said list.