Multi-stage function mapping for a range of input values

Abstract

Gamma correction or other powerPower functions and other self- similar functions are generated for correcting the light intensity for digital pixelsimplemented in hardware. Two levels of mapping of segments are preformed to reduce the total number of segments for a given precision. TheA range of inputs is divided into successively smaller segments. Two levels of mapping of segments are performed. Each segment is smaller than the next by a factor of 1/a for a first or primary level, or 1/b for a second level of segments. All inputs are mapped of scaled up to the input range of the largest segment in the primary level. Then the largest primary segment is further divided into several second-level segments, and the input is again mapped or scaled into the largest of the second-level segments. Gamma correctionThe function is performed on the input scaled into the largest second-level segment. A linear approximation within the largest second-level segment is used. The result is de-mapped or scaled down from the largest second-level segment to the actual second-level segment, then it is scaled downand again from the largest primary-level segment to the actual primary-level segment for the original input. Smaller priority encoders and shifters and simplified de-mapping circuits can be used, saving logic .

1. A multi-level segment-mapping function generator comprising:
 an input having an input value within an input range, the input range being divided into a plurality of first-level segments of varying width including a standard first-level segment;  
 a first-level mapper, receiving the input value, for scaling the input value to an intermediate input value within a range of the standard first-level segment, the first-level mapper outputting the intermediate input value to an intermediate input;  
 wherein the intermediate input value output by the first-level mapper is within a second input range equal to the range of the standard first-level segment, the range of the standard first-level segment being divided into a plurality of second-level segments of varying width, the plurality of second-level segments including a standard second-level segment;  
 a second-level mapper, receiving the intermediate input from the first-level mapper, for scaling the intermediate input value to generate a final input having a final input value, the final input value being within a range of the standard second-level segment;  
 a function generator, receiving the final input from the second-level mapper, for generating a result of a pre-determined function from the final input value;  
 a second-level de-mapper, receiving the result from the function generator, for adjusting the result from the function generator to an intermediate result, the intermediate result being a result of the pre-determined function for the intermediate input value; and  
 a first-level de-mapper, receiving the intermediate result from the second-level de-mapper, for adjusting the intermediate result from the second-level de-mapper to a final result, the final result being a result of the pre-determined function for the input value, whereby the final result can be generated for any input value within the input range using the function generator that generates results only within the standard second-level segment.  
 
     
     
       2. The multi-level segment-mapping function generator of  claim 1  wherein the plurality of first-level segments are non-overlapping and ratio-metrically related wherein each smaller first-level segment is 1/a the input width of a next larger first-level segment, wherein a is a positive integer representing a first ratio;
 wherein the standard first-level segment is a largest of the plurality of first-level segments;  
 wherein the plurality of second-level segments are non-overlapping and ratio-metrically related wherein each smaller second-level segment is 1/b the input width of a next larger second-level segment, wherein b is a positive integer representing a second ratio;  
 wherein the standard second-level segment is a largest of the plurality of second-level segments,  
 whereby segments are ratios of larger segments in a level.  
 
     
     
       3. The multi-level segment-mapping function generator of  claim 2  wherein a is not equal to b, 
       whereby each level has segments with different ratios of segment widths. 
     
     
       4. The multi-level segment-mapping function generator of  claim 3  wherein the function generator is a linear interpolator generating the result by multiplying the final input by a slope of a line and adding a constant, 
       whereby the pre-determined function is approximated by a line within the standard second-level segment. 
     
     
       5. The multi-level segment-mapping function generator of  claim 4  wherein the first-level mapper comprises:
 a first priority encoder, receiving the input, for detecting a leading significant bit in multiple bits in the input that represent the input value, the first priority encoder generating a first shift signal determined by a location of the leading significant bit within the input value;  
 a first shifter, receiving the input, for shifting the input value by a shift signal determined by the first shift signal to generate the intermediate input value,  
 whereby the first-level mapper shifts the input value.  
 
     
     
       6. The multi-level segment-mapping function generator of  claim 5  wherein the second-level mapper comprises:
 a second priority encoder, receiving the intermediate input, for detecting a leading significant bit in multiple bits in the intermediate input that represent the intermediate input value, the second priority encoder generating a second shift signal determined by a location of the leading significant bit within the intermediate input value;  
 a second shifter, receiving the intermediate input, for shifting the intermediate input value by a second shift signal determined by the second shift signal to generate the final input value,  
 whereby the second-level mapper shifts the intermediate input value.  
 
     
     
       7. The multi-level segment-mapping function generator of  claim 6  wherein the input value has K binary bits,
 wherein a smallest of the plurality of first-level segments has a range of 1/2 K  of the input range;  
 wherein a total number of segments in the plurality of first-level segments is N 1 ;  
 wherein a total number of segments in the plurality of second-level segments is N 2 ;  
 wherein N 1 +N 2  is less than K;  
 whereby a precision of the function generator is 1/2 K  of the input range but a total number of segments is less than K.  
 
     
     
       8. The multi-level segment-mapping function generator of  claim 6  wherein the first-level de-mapper comprises:
 a reverse shifter, receiving the intermediate result from the second-level de-mapper, for shifting the intermediate result by a number of bit-positions to generate the final result;  
 wherein the number of bit-positions is determined by the first shift signal from the first priority encoder;  
 wherein a full multiplier for multiplying the intermediate result by an arbitrary constant is not required;  
 wherein the reverse shifter shifts the intermediate result in an opposite direction to a direction that the first shifter shifts the input value.  
 
     
     
       9. The multi-level segment-mapping function generator of  claim 8  wherein the second-level de-mapper comprises:
 a constant multiplier, receiving the result from the function generator, for multiplying the result by a constant to generate the intermediate result;  
 wherein the constant is a function of the second shift signal from the second priority encoder.  
 
     
     
       10. The multi-level segment-mapping function generator of  claim 9  wherein the predetermined function is a power function wherein the final result W′ is related to the input value W by an equation:
   W′=W α   
 
       where α is a positive constant. 
     
     
       11. The multi-level segment-mapping function generator of  claim 10  wherein α is a reciprocal of a gamma-correction constant for correcting a light output of a pixel to a driving voltage of a display. 
     
     
       12. The multi-level segment-mapping function generator of  claim 11  wherein the first-level de-mapper implements an equation:
   W′=(1/a) α*m *X′ 
 
       wherein W′ is the final result, X′ is the intermediate result, m is the first shift signal, and a is the first ratio. 
     
     
       13. The multi-level segment-mapping function generator of  claim 12  wherein the second-level de-mapper implements an equation:
   X′=(1/b) α*n *Y′ 
 
       wherein X′ is the intermediate result, Y′ is the result from the function generator, n is the second shift signal, and b is the second ratio. 
     
     
       14. A method for gamma correcting a pixel comprising:
 receiving an input value representing a brightness of a pixel, the input value being within an input range divided into primary segments that include a standard primary segment;  
 determining an original segment that contains the input value, the original segment being one of the primary segments identified by a first encoded signal;  
 shifting the input value to an intermediate input value, the intermediate input value being within the standard primary segment;  
 determining an intermediate second segment that contains the intermediate input value, the intermediate second segment being one of a plurality of second segments, wherein the standard primary segment is divided into the plurality of second segments;  
 shifting the intermediate input value to a final input value, the final input value being within a standard segment in the plurality of second segments;  
 generating a function result from the final input value, the function result being a gamma correction of the final input value;  
 adjusting the function result to generate an intermediate result, the intermediate result being the gamma correction of the intermediate input value; and  
 adjusting the intermediate result to generate a final result, the final result being the gamma correction of the input value,  
 whereby two levels of segment mapping are performed before gamma correction.  
 
     
     
       15. The method of  claim 14  wherein adjusting the intermediate result to generate a final result comprises:
 right-shifting the intermediate result to generate the final result,  
 whereby a multiply by an arbitrary constant that is not a power of 2 is avoided when adjusting the intermediate result to generate a final result.  
 
     
     
       16. The method of  claim 15  wherein shifting the input value to an intermediate input value comprises:
 left-shifting by a multiple of M bits, where M is a location of a most-significant bit in the input value,  
 whereby the input value is first shifted by a multiple of M bits.  
 
     
     
       17. The method of  claim 16  wherein the input value represents a Y luminosity value of a pixel in a YUV format. 
     
     
       18. The method of  claim 16  wherein shifting the intermediate input value to a final input value comprises left-shifting the intermediate input value by a multiple of N bits, where N is a second shift amount determined by a location of a most-significant bit in the intermediate input value;
 wherein adjusting the intermediate result to generate a final result comprises:  
 multiplying the intermediate result by a constant, the constant selected from among a plurality of constants by the second shift amount N.  
 
     
     
       19. A power-function system comprising:
 input means for receiving an input value, the input value being within an input range divided into primary segments that include a standard primary segment;  
 first priority means for determining an original segment that contains the input value, the original segment being one of the primary segments identified by a first encoded signal,  
 first shift means, responsive to the first priority means, for shifting the input value to an intermediate input value, the intermediate input value being within the standard primary segment;  
 second priority means, receiving the intermediate input value from the first shift means, for determining an intermediate second segment that contains the intermediate input value, the intermediate second segment being one of a plurality of second segments, wherein the standard primary segment is divided into the plurality of second segments;  
 second shift means, responsive to the second priority means, for shifting the intermediate input value to a final input value, the final input value being within a standard segment in the plurality of second segments;  
 function means, receiving the final input value, for generating a function result from the final input value, the function result being a pre-defined function of the final input value;  
 second de-map means, responsive to the second plurality means, for adjusting the function result to generate an intermediate result, the intermediate result being the pre-defined function of the intermediate input value; and  
 first de-map means, responsive to the first priority means, for adjusting the intermediate result to generate a final result, the final result being the pre-defined function of the input value,  
 whereby two levels of segment mapping are performed before the pre-defined function.  
 
     
     
       20. The power-function system of  claim 19  wherein the first de-map means comprises:
 shift means for right-shifting the intermediate result to generate the final result, whereby a multiply by an arbitrary constant that is not a power of 2 is avoided when adjusting the intermediate result to generate a final result.  
 
     
     
       21. An apparatus configured to perform a first mathematical function on an original input value to produce a final result value, said apparatus comprising:
   a mapping circuit configured to receive said original input value for said first mathematical function, wherein said original input value is within a predetermined range of values, and wherein said mapping circuit is configured to map said original input value to a final input value, wherein said final input value is within a predetermined segment of said predetermined range of values, and wherein said mapping circuit is configured to perform at least two mapping operations in order to generate said final input value from said original input value;        a function generation circuit configured to receive said final input value and generate an intermediate result corresponding to a value of said first mathematical function at said final input value;        a de - mapping circuit configured to receive said intermediate result and to generate said final result value therefrom by performing at least two de - mapping operations, wherein said final result value corresponds to a value of said first mathematical function at said original input value.     
     
     
       22. The apparatus of  claim 21 , wherein said predetermined segment is one of a plurality of segments of said predetermined range of values, and wherein said plurality of segments are ratiometrically related. 
     
     
       23. The apparatus of  claim 22 , wherein said original input value is within an original segment of said plurality of segments. 
     
     
       24. The apparatus of  claim 23 , wherein said mapping circuit is configured to perform a first mapping operation that maps said original input value from said original segment to an intermediate input value within an intermediate segment of said plurality of segments. 
     
     
       25. The apparatus of  claim 24 , wherein said mapping circuit is configured to perform a second mapping operation that maps said intermediate input value to said final input value. 
     
     
       26. The apparatus of  claim 21 , wherein said predetermined range of values includes a plurality of segments, including a first subset of two or more segments that includes said predetermined segment. 
     
     
       27. Then apparatus of  claim 26 , wherein said at least two mapping operations include a first mapping operation that includes mapping said original input value to an intermediate input value within one of said first subset of segments. 
     
     
       28. The apparatus of  claim 27 , wherein said at least two mapping operations include a second mapping operation that includes mapping said intermediate input value to said final input value within said predetermined segment. 
     
     
       29. The apparatus of  claim 21 , wherein said function generation circuit is configured to perform a linear approximation of said first mathematical function within said predetermined segment of said predetermined range of values. 
     
     
       30. The apparatus of  claim 21 , wherein said function generation circuit is configured to perform a non- linear approximation of said first function within said predetermined segment of said predetermined range.   
     
     
       31. The apparatus of  claim 21 , wherein said mapping circuit includes at least two priority encoders. 
     
     
       32. The apparatus of  claim 21 , wherein said at least two de- mapping operations performed by said de - mapping circuit are complementary to said at least two mapping operations performed by said mapping circuit.   
     
     
       33. The apparatus of  claim 21 , wherein said first mathematical function is a power function. 
     
     
       34. The apparatus of  claim 33 , wherein said first mathematical function is gamma correction. 
     
     
       35. The apparatus of  claim 21 , wherein said apparatus is configured to perform gamma correction of color components of a pixel value. 
     
     
       36. The apparatus of  claim 21 , wherein said apparatus is a digital camera. 
     
     
       37. The apparatus of  claim 21 , wherein said predetermined range of values is between  0  and  1 . 
     
     
       38. The apparatus of  claim 21 , wherein said first mathematical function is a self- similar function, and wherein said function generation circuit is configured to perform a linear approximation of said first mathematical function within said predetermined segment of said predetermined range of values.   
     
     
       39. The apparatus of  claim 25 , wherein said de- mapping circuit is configured to perform de - mapping operations complementary to said first and second mapping operations.   
     
     
       40. The apparatus of  claim 28 , wherein said de- mapping circuit is configured to perform de - mapping operations complementary to said first and second mapping operations.   
     
     
       41. The apparatus of  claim 21 , wherein said predetermined segment is one of a plurality of segments of said predetermined range of values, wherein said plurality of segments includes a first subset of said plurality of segments and a second subset of said plurality of segments, wherein said first subset of segments are ratiometrically related according to a first constant, and wherein said second subset of segments are ratiometrically related according to a second constant that is different from said first constant. 
     
     
       42. The apparatus of  claim 41 , wherein said predetermined segment is one of said second subset of segments, and wherein said original input value is within one of said first subset of segments. 
     
     
       43. The apparatus of  claim 21 , wherein said de- mapping circuit includes a reverse shifter.   
     
     
       44. The apparatus of  claim 21 , wherein said de- mapping circuit includes a multiplier.   
     
     
       45. The apparatus of  claim 37 , wherein said mapping circuit includes first means for detecting a leading one in said original input value. 
     
     
       46. The apparatus of  claim 33 , wherein said power function is a square root function. 
     
     
       47. The apparatus of  claim 33 , wherein said power function is a root- mean - square function.   
     
     
       48. An apparatus for generating a value for a first mathematical function from an original input value, said apparatus comprising:
   first means for mapping said original input value to a final input value using at least two mapping operations, wherein said final input value is within a predetermined segment of a range of input values;        second means for receiving said final input value and determining a value of said first mathematical function at said final input value;        third means for de - mapping said value of said first mathematical function produced by said second means in order to generate an output value of said first mathematical function at said original input value, wherein said de - mapping uses at least two de - mapping operations.     
     
     
       49. The apparatus of  claim 48 , wherein said apparatus is a digital camera. 
     
     
       50. An apparatus, comprising:
   a primary mapping circuit configured to receive an original input value for a first mathematical function, wherein said original input value is located within one of a plurality of segments of a range of input values, and wherein said primary mapping circuit is configured to map said original input value to an intermediate input value located within a first segment of said plurality of segments;        a secondary mapping circuit configured to receive said intermediate input value, wherein said intermediate input value is located within one of a plurality of sub - segments of said first segment, wherein said secondary mapping circuit is configured to map said intermediate input value to a final input value located within a first sub - segment of said first segment;        a function generation circuit configured to receive said final input value and to generate a preliminary output value therefrom, wherein said preliminary output value corresponds to an output value of said first mathematical function at said final input value;        a secondary de - mapping circuit configured to receive said preliminary output value and adjust said original output value to produce an intermediate output value; and        a primary de - mapping circuit configured to receive said intermediate output value and adjust said intermediate output value to produce a final output value, wherein said final output value corresponds to an output value of said first mathematical function for said original input value.     
     
     
       51. The apparatus of  claim 50 , wherein said apparatus is a digital camera. 
     
     
       52. The apparatus of  claim 50 , wherein said first mathematical function is a power function. 
     
     
       53. The apparatus of  claim 50 , wherein said primary mapping circuit is configured to receive a first input value from a first priority encoder, and wherein said primary mapping circuit is configured to perform a first mapping operation upon said original input value in response to receiving said first input value. 
     
     
       54. The apparatus of  claim 53 , wherein said secondary mapping circuit is configured to receive a second input value from a second priority encoder, and wherein said secondary mapping circuit is configured to perform a second mapping operation upon said intermediate input value in response to receiving said second input value. 
     
     
       55. The apparatus of  claim 54 , wherein said secondary de- mapping circuit is configured to perform a second de - mapping operation that is complementary to said second mapping operation.   
     
     
       56. The apparatus of  claim 55 , wherein said primary de- mapping circuit is configured to perform a first de - mapping operation that is complementary to said first mapping operation.   
     
     
       57. The apparatus of  claim 53 , wherein said first mapping operation is a binary shift operation. 
     
     
       58. The apparatus of  claim 54 , wherein said second mapping operation is a binary shift operation. 
     
     
       59. The apparatus of  claim 55 , wherein said second de- mapping operation is a reverse binary shift operation.   
     
     
       60. The apparatus of  claim 55 , wherein said second de- mapping operation is a multiplication operation.   
     
     
       61. The apparatus of  claim 56 , wherein said first de- mapping operation is a reverse binary shift operation.   
     
     
       62. The apparatus of  claim 56 , wherein said first de- mapping operation is a multiplication operation.   
     
     
       63. The apparatus of  claim 50 , wherein said plurality of segments are ratiometrically related. 
     
     
       64. A method for generating, from an original input value, a final output value for a first function, said method comprising:
   receiving, at a mapping circuit of an apparatus, said original input value, wherein said original input value is within a predetermined range of input values;        the mapping circuit performing at least two mapping operations to map said original input value to a final input value, wherein said final input value is located within a first segment of said predetermined range of input values;        a function generation circuit of the apparatus generating a preliminary output value that corresponds to a value of said first function at said final input value;        a de - mapping circuit of the apparatus performing at least two de - mapping operations to adjust said preliminary output value to a final output value, wherein said final output value corresponds to an output value of said first function at said original input value.