METHOD OF PROCESSING DATA BY AN ITERATIVE APPLICATION OF A SAME LUT

Abstract

Instead of using a single LUT to model a processing function, it is proposed to use another smaller LUT, i.e. an iterative LUT, such that, when applied at least two times in succession to data to process, the same processing function is modeled with at least the same accuracy. A specific way to compute this iterative LUT is given. Specific applications are given in the field of color processing. Modeling is more accurate and/or less bins are needed to model complex functions.

Claims

1. A method of processing input values of data x using a lookup-table LUT comprising applying iteratively said lookup-table over at least two iterations.

2. The method of claim 1, wherein the at least two iterations comprise a first iteration in which said lookup-table LUT is applied to said input values resulting in first output values and in which said lookup-table LUT is applied to said first output values resulting in second output values.

3. The method of claim 1, comprising interpolating for said iterative application of said lookup table.

4. The method of claim 3, wherein said interpolating for an application of said lookup table is performed between input values of said lookup table and between output values of said lookup table.

5. The method of claim 4, wherein said interpolating is linear.

6. The method of claim 1, wherein said lookup table is multidimensional.

7. The method of claim 1, wherein said data represent colors.

8. The method claim 7, wherein the at least two iterations of said lookup table models a processing function which is nonlinear and bijective.

9. The method of claim 8, wherein said processing function is chosen in the group composed of a transfer function, a tone mapping and an inverse tone mapping function.

10. A device comprising at least one processor configured to implement the method according to claim 1.

11. The device of claim 10 chosen in the group composed of a mobile device, a communication device, a game device, a laptop, a camera, a chip, a server, a TV set and a Set-Top Box.

12. A computable readable storage medium comprising stored instructions that when executed by a processor performs the method of claim 1.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0020] The invention will be more clearly understood on reading the description which follows, given by way of non-limiting examples and with reference to the appended figures in which:

[0021] FIG. 1 illustrates the representation of a processing function h() by an iterative application of a LUT over two iterations.

[0022] FIG. 2 illustrates the representation of a processing function h(x) by an iterative application of an iterative function f(x) over two iterations.

[0023] FIG. 3 illustrates a comparison between approximating a PQ EOTF processing function using a single application of a 5-bin LUT, or using a single application of a 10-bin LUT, or using a double application of a 5-bin LUT as in the method of FIG. 1.

[0024] FIG. 4 illustrates errors of the approximations of FIG. 3.

[0025] FIG. 5 illustrates that, by incorporating a small k-bin LUT.sub.pp into an iterative function .sub.p(x), the polynomial P.sub.(x) approximating this iterative function .sub.p(x) is not accurate.

[0026] FIG. 6 illustrates a comparison between approximating a Slog3 EOTF processing function using a single application of a 5-bin LUT, or using a single application of a 15-bin LUT, or using a triple application of a 5-bin LUT as in the iterative method disclosed herein.

[0027] FIG. 7 illustrates errors of the approximations of FIG. 6.

DESCRIPTION OF EMBODIMENTS

[0028] It will be appreciated by those skilled in the art that flow charts presented herein represent conceptual views of illustrative circuitry embodying the invention. They may be substantially represented in computer readable media and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.

[0029] The functions of the various elements shown in the figures may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. Explicit use of the term processor should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, Systems on Chip (SOCs) hardware or Field-Programmable Gate Arrays (FPGAs) hardware, read-only memory (ROM) for storing software, random access memory (RAM), and non-volatile storage.

[0030] It is to be understood that the method of processing input values of data may be implemented in various forms of hardware, software, firmware, special purpose processors, or combinations thereof. The invention may be notably implemented as a combination of hardware and software. Moreover, the software may be implemented as an application program tangibly embodied on a program storage unit. The application program may be uploaded to, and executed by, a processing machine comprising any suitable architecture. Preferably, the processing machine is implemented on a platform having hardware such as one or more central processing units (CPU), a random access memory (RAM), and input/output (I/O) interfaces. The platform may also include an operating system and microinstruction code. The various processes and functions described herein may be either part of the microinstruction code or part of the application program, or any combination thereof, which may be executed by a CPU. In addition, various other peripheral units may be connected to the platform such as an additional data storage unit and a display device. The platform may be notably a mobile device as a tablet, a communication device as a smartphone, a game device, a laptop, a camera, a chip as an encoding chip or a decoding chip, a server as a broadcast server or web server, a TV set or a Set-Top Box.

[0031] It is to be understood that input values of data to be processed by the method can be any kind of data, even if the below embodiment is described in the context of processing input values of color data.

[0032] In a first part of this embodiment, an approximation of a processing function h(x) by applying iteratively at least two times an iterative function (x), i.e. according ( . . . . . . )(x) is explained. Then, the obtained result is extended to replace the iterative function (x) with the application of a corresponding iterative LUT resulting to an approximative iterative function (x). FIG. 1 illustrates the representation of a processing function h() by an iterative application of a LUT over two iterations. Similarly, FIG. 2 illustrates the representation of a processing function h(x) by an iterative application of an iterative function f(x) over two iterations (repeated application f(f(x))). FIG. 2 shows that the iterative function f(x) has a lower curvature compared to that of the processing function h(x). The method of representing a processing function h(x) by an iterative application of an LUT or of a function f(x) can also be used similarly over more than two iterations.

[0033] A method to obtain a lookup table LUT to be applied iteratively over two iterations will be first described, in the context of processing color data x through a PQ electro-optical transfer function h.sub.PQ(x) as specified in ITU-R Recommendation BT2100. The variable x corresponds to the variable N in the PQ-EOTF quoted in the background art paragraph above.

[0034] First, a number k of bins is determined, based notably on memory size available on the processing platform. These k input values x.sub.1, . . . , x.sub.j, . . . , x.sub.k are chosen to be distributed uniformly over the range of input values. Therefore, the targeted iterative LUT will have k input values x.sub.1, . . . , x.sub.j, . . . , x.sub.k (and k corresponding output values y.sub.1, . . . y.sub.j, . . . , y.sub.k).

[0035] Then, an iterative function .sub.PQ(x) is defined such that:

h.sub.PQ(x)=.sub.PQ(.sub.PQ(x))

Such an iterative function .sub.PQ(x) can be for instance approximated in a manner known per se by a 6-degree polynomial P.sub.fPQ(x) as follows: P.sub.fPQ(x)=4.0793e.sup.5x.sup.5+0.0116x.sup.4+0.2966x.sup.3+0.4146x.sup.2+0.1455x+0.1317

[0036] Note that, on a sampled grid of 1000 input values x, the mean absolute error of |h.sub.PQ(x).sub.PQ(.sub.PQ(x))| is 1.95 e.sup.5, showing a high degree of correspondence between a double iteration .sub.PQ(.sub.PQ(x)) of the iterative function and the processing function itself h.sub.PQ(x). Similarly, the HLG opto-electrical transfer function (ITU-R Recommendation BT.2100) can be approximated with this procedure to within a mean absolute error of 9.01 e.sup.4.

[0037] Generally, for any processing function h(x), the iterative function (x) cannot be obtained analytically. However, it is generally possible to approximate the iterative function (x) using a polynomial P.sub.(x) of a sufficiently high degree:

[00002]$P_f\left(x\right)=\underset{i=0}{\overset{n}{.Math.}}.Math.m_i.Math.x^{n-i}$

where the polynomial P.sub.(x) is defined by the degree n and the coefficients m.sub.i. The coefficients of the polynomial P.sub.(x) can be determined by the equation:

[00003]$\underset{m_i}{\arg .Math..Math.\min }.Math.{.Math.h\left(x\right)-P_f\left(P_f\left(x\right)\right).Math.}_2^2$

[0038] Here, an iterative polynomial P.sub.(x) is preferably evaluated based only on the k input values x.sub.1, . . . , x.sub.j, . . . , x.sub.k and their corresponding processing function values (x.sub.1), . . . , (x.sub.j), . . . , (x.sub.k). The k resulting values P.sub. (x.sub.1), . . . , P.sub.(x.sub.j), . . . , P.sub.(x.sub.k) output by this iterative polynomial P.sub.() then serve once more as input to this iterative polynomial P.sub.(x). The resulting coarsely k-discretized P.sub.(P.sub.(x.sub.j)) (with j in [1,k]) is then turned in a manner known per se into a LUT.sub.pp representing P.sub.(P.sub.(x.sub.j)) and having the k input values x.sub.1, . . . , x.sub.j, . . . , x.sub.k as entries. This LUT.sub.pp, which represents a function .sub.pp.sup.(x), can be evaluated (by means of linear interpolation) at a large number i of sample points between x[0,1]. Thus, for a large number of points, say 1000, the following iterative function is evaluated:

[00004]$\underset{m_i}{\arg .Math..Math.\min }.Math.{.Math.h\left(x\right)-f_{\mathrm{pp}}^{}\left(x\right).Math.}_2^2$

[0039] After minimizing the difference h(x).sub.p,p.sup.(x).sub.2.sup.2 for this large number i of sample points m.sub.i, another resulting polynomial P.sub.pp() with coefficients m.sub.i is once again evaluated as above at the same k sample points. This other resulting polynomial P.sub.pp(x) is then turned into a final target iterative LUT.sub.pp in a manner known per se.

[0040] As an example, this procedure is applied to the above PQ EOTF using a 6-degree polynomial, and a 5-bin target LUT, with results shown in FIG. 3. This figure illustrates a comparison between approximating the processing function (function to approximate) using a single application of a 5-bin LUT, or using a single application of a 10-bin LUT, or using a double application of a 5-bin LUT as in the above method. This figure shows that the modeling of the processing function by a double application of a 5-bin LUT is as accurate as the modeling of the processing function by a single application of a 10-bin LUT.

[0041] The advantage of approximating a function of input values of data by applying iteratively a small size LUT to these input values will now be shown in comparison with approximating the function of input values of data by applying once a bigger LUT to these input values.

[0042] When comparing the above situation of a two-iterative 5-bin LUT.sub.pp approximating the PQ EOTF with a situation of a single 10-bit LUT approximating the PQ EOTF, the mean absolute error induced by the double application of the small LUT.sub.pp is 0.0046, whereas a single application of a 10-bin bigger LUT induces a higher mean absolute error of 0.0096. The double application of the small LUT.sub.pp is therefore a better approximation of the PQ EOTF that a single application of the 10-bin bigger LUT.

[0043] The distribution shown in FIG. 4 of the absolute errors over the input range of input values shows that the error made by applying two times the smaller LUT.sub.pp is the smallest over the full range of input values. It can also be seen that the error of this iterative method can be both positive and negative, so that the maximum error is small. Comparatively, as shown in FIG. 4, conventional single application of a LUT leads to errors that are always positive or always negative.

[0044] Finally, note that by incorporating a small k-bin LUT.sub.pp into the iterative function .sub.p(x), the approximating polynomial P.sub.(x) is no longer accurate, as shown in FIG. 5. This demonstrates the interest of evaluating an iterative polynomial based not on a sampled grid of a large number of input values (for instance 1000 as described above), but based only on k input values x.sub.1, . . . , x.sub.j, . . . , x.sub.k distributed over the range of input values, where k is the number of bin of the targeted iterative LUT.

[0045] Still in the first part of this embodiment, a method to obtain a lookup table LUT to apply iteratively over more than two iterations will be described.

[0046] To approximate a function h(x) with n repeated applications of an iterative function (x), the iterative function .sub.p(x) is given by:

[00005]$\underset{m_i}{\arg .Math..Math.\min }.Math.{.Math.h\left(x\right)-\left(f_p^{}.Math.f_p^{}.Math..Math.{\mathrm{.Math.}.Math.}^{}.Math.f_p\right).Math.\left(x\right).Math.}_2^2$

[0047] To approximate a function h(x) with an iterative LUT applied over n iterations, the iterative function .sub.p(x) is given by:

[00006]${\underset{m_i}{\arg .Math..Math.\min }.Math..Math.h\left(x\right)-f_{\mathrm{pp}.Math..Math.\mathrm{.Math.}.Math..Math.p}^{}\left(x\right)).Math.}_2^2$

[0048] where .sub.pp . . . p.sup.(x) is a small LUT created by repeating the evaluation of polynomial .sub.p(x) using a LUT of k bins for a total of n times.

[0049] As an example, using the above method, the so-called Slog3 opto-electrical transfer function (OETF) is approximated with an iterative 5-bin LUT applied over 3 iterations. The accuracy of this approximation is shown in FIG. 6 (see curve 3 LUTS, 5 elements compared to 1 LUT, 5 elements or compared to 1 LUT, 15 elements). This figure illustrates that an iterative 5-bin LUT applied over 3 iterations is at least as accurate than a single application of a 15-bin LUT.

[0050] The error induced by this approximation is shown in FIG. 7. The mean absolute error of 3-iterated 5-bin LUT is 0.0038. For comparison, a conventional single-applied 15-bin LUT induces a higher mean absolute error of 0.0048.

[0051] Still in the first part of this embodiment, it may be noticed that, once a processing function h(x) is given, there is generally no uniquely defined solution to determine a iterative function such that:

h(x)=()(x)

[0052] However, under certain circumstances it is possible to approximate an iterative function to an arguably simpler problem, namely to find an approximation to the iterative function such that when applied twice it approximates the processing function h(x):

()(x)h(x)

[0053] where is an approximation to .

[0054] In a second part of this embodiment, a method of processing input values of data x using a lookup-table (LUT) comprising applying iteratively this lookup-table over at least two iterations will be briefly described. This iterative lookup-table is notably defined as described in the first part of this embodiment, using usual computing means.

[0055] The method is notably implemented on a platform comprising at least one processor configured in a manner known per se to implement it. This platform can be for instance a mobile device as a tablet, a communication device as a smartphone, a game device, a laptop, a camera, a chip as an encoding chip, a server as a broadcast server or web server, a TV set or a Set-Top Box.

[0056] This processing method comprises at least two iterations: a first iteration in which the lookup-table is applied to the input values resulting in first output values and a second iteration in which the lookup-table is applied to the first output values resulting in second output values.

[0057] When the input value is different from an input value x.sub.1, . . . , x.sub.j, . . . , x.sub.k of the lookup table, an interpolation is performed between input values of the lookup table to output an output value that is interpolated between the corresponding output values of the lookup table. Such an interpolation is performed in an manner known per se in the field of lookup tables. Preferably, this interpolation is linear, saving then advantageously computing resources. Although interpolation is linear, the approximation of a processing function remains accurate due notably to the multiple iterations of the method.

[0058] Preferably, input values to process represents colors. For instance, input values to process are R,G,B values representing colors in a RGB color space. Preferably, as described in the first part of the embodiment above, the at least two iterations of the lookup table models a transfer function such as an Electro-Optical Transfer Function (EOTF), an Optical Electrical Transfer Function (OETF), a gamma function or a Slog/Slog2/Slog3 function, or models a tone mapping or an inverse tone mapping function. By replacing these processing functions with multiple iterations of one LUT, a high accuracy approximation at a low computational cost may be obtained.

[0059] A processing function h(x) that can be modeled by iterative application of a given LUT preferably adheres to the following characteristics.

[0060] First, the processing function h(x) is preferably strictly monotonically increasing or strictly monotonically decreasing:

[00007]$\frac{\mathrm{dh}\left(x\right)}{\mathrm{dx}}>0.Math..Math.x\left[0,1\right]$$\mathrm{or}$$\frac{\mathrm{dh}\left(x\right)}{\mathrm{dx}}<0.Math..Math.x\left[0,1\right]$

[0061] This means that the processing function h(x) is preferably bijective, although may have inflection points.

[0062] Further, a given non-linear processing function h(x) may have over its range of values a certain (varying) curvature. This curvature, along with the bin spacing and the assumed use of linear interpolation, has direct impact on the accuracy of a LUT. For example, for processing functions that have a smaller curvature (i.e., they are straighter), the accuracy of a corresponding LUT will be higher than for other functions.

[0063] Still further, when a highly non-linear target function h(x) is decomposed into a double application of a same (x) such that h(x)=()(x), then the curvature of (x) is less than that of h(x) in the range x[0,1]. Thus, a LUT with a given number of bins approximating (x) will be of higher accuracy than a LUT with the same number of bins approximating directly h(x). In practice, it is found that applying two k-bin LUTs in succession to approximate ()(x) is twice as accurate as approximating h(x) directly with a single 2k-bin LUT.

[0064] Note that when the processing function h(x) to be approximated is linear, finding a solution (x) such that h(x)=()(x) is trivial. Assuming that h(x)=kx, then (x) can be chosen to be (x)={square root over (k)}x so that:

(x)=({square root over (k)}).sup.2x=kx=h(x)

[0065] When h(x)=x.sup. (as for very usual so-called gamma functions), the iterative function can be (x)=x.sup.{square root over ()}, so that:

(x)=(x.sup.{square root over ()}).sup.{square root over ()}=x.sup.=h(x)

[0066] Preferably, both input and output of a processing function are bounded to a given range. Such a range may be bounded to be between 0 and 1, although any number of other ranges are possible:

x[0,1]

h(x)[0,1]

[0067] The method of processing input values of data is notably advantageous, because an approximation of a processing function h(x) by multiple iteration of a given function (x) has been found generally more accurate than an approximation of this processing function h(x) by different intermediate functions .sub.1(x), . . . , .sub.r(x), . . . , .sub.Q(x) such that h(x)=.sub.1( . . . (.sub.r ( . . . (.sub.Q(x)) . . . )) . . . ).

[0068] Although the illustrative embodiments of the invention have been described herein with reference to the accompanying drawings, it is to be understood that the present invention is not limited to those precise embodiments, and that various changes and modifications may be effected therein by one of ordinary skill in the pertinent art without departing from the invention. All such changes and modifications are intended to be included within the scope of the present invention as set forth in the appended claims.