Method and system for implementing a low-complexity scheme in color conversion and down-sampling of image codecs

The present invention generally relates to image processing. More specifically, the present invention relates to an image processing method and system using a low-complexity scheme.

FIG. 1 is a simplified block diagram illustrating a typical image color conversion process. It is typical for image codecs, such as those using the JPEG and MPEG formats, to perform color conversion from the red-green-blue (RGB) model to the YCbCr model, where Y is the luminance component, Cb is the chrominance component for blueness and Cr is the chrominance component for redness. In addition, in order to achieve data reduction, a down-sampling process is performed according to the visual perception of the image being processed. For different components, different down-sampling frequencies may be used. Down-sampling can also be made both vertically and horizontally. As a result, various combinations of down-sampled image data can be obtained for additional processing.

One rate that is commonly used for down-sampling is “4:2:0”, which means that no down-sampling is performed on the Y component and “2:1” vertical and horizontal down-sampling is performed for the Cb component and the Cr component. With the “4:2:0” down-sampling rate, a fifty percent (50%) data reduction can be achieved.

From a computational complexity perspective, however, the color conversion and down-sampling processes are very expensive. That is, a large number of computations are typically needed to process the desired image data. For example, as will be further illustrated below, with a down-sampling rate of “4:2:0” and average processing taken into account, thirteen (13) multiplications and fifteen (15) additions are required to get a down-sampled Cb or Cr component from corresponding RGB formats.

FIG. 2 is a simplified diagram illustrating a down-sampling rate of “4:2:0”. Equations for RGB to YCbCr conversion can be roughly expressed as:

Y= 0.29900 R+ 0.58700 G+ 0.11400 B Cb=− 0.16874 R− 0.33126 G+ 0.50000 B+ 2 SP/2 Cr= 0.50000 R− 0.41869 G− 0.08131 B+ 2 SP/2   Eqs. (1)

where “SP” stands for sample precision. Let Y 0 ′, Y 1 ′, Y 2 ′, Y 3 ′ and Y 0 ″, Y 1 ″, Y 2 ″, Y 3 ″ denote the Y component before and after down-sampling, respectively. Likewise, let Cb 0 ′, Cb 1 ′, Cb 2 ′, Cb 3 ′ and Cb″ denote the Cb component and Cr 0 ′, Cr 1 ′, Cr 2 ′, Cr 3 ′ and Cr″ denote the Cr component, before and after down-sampling, respectively. According to the above definition, for average down-sampling, the following represents equations that can be used to obtain the Y, Cb and Cr components under the YCbCr model:

Referring to Eqs. (1), to convert each RGB pixel to obtain Cb i ′ before down-sampling, three (3) multiplications and three (3) additions are needed, that is, one (1) multiplication each for each RGB component and three (3) additions to sum up the result. Likewise, the same number of multiplications and additions are needed to obtain Cr i ′ before down-sampling.

Referring to Eqs. (2), to obtain Cb″ after down-sampling from RGB, fifteen (15) (3×4+3=15) additions and thirteen (13) (3×4+1=13) multiplications are needed. Likewise, the same number of multiplications and additions are needed to obtain Cr″ after down-sampling.

From a computational complexity perspective, the computational cost to carry out the foregoing becomes very expensive as the number of pixels and the number of bits representing each pixel increase. For each pixel to be converted from the RGB model to the YCbCr model, thirteen (13) multiplications and fifteen (15) additions are required in order to obtain a down-sampled Cb″ or Cr″ component.

It should be noted that the foregoing example is given merely for illustrative purposes. In order to calculate the down-sampled Cb″ and Cr″ components, more generalized equations can be used as follows:

Cb″=α 0 Cb 0 ′+α 1 Cb 1 ′+α 2 Cb 2 ′+α 3 Cb 3 ′

Cr″=β 0 Cr 0 ′+β 1 Cr 1 ′+β 2 Cr 2 ′=β 3 Cr 3 ′  Eqs. (3)

Note that Eqs. (2) above are merely specific instances of Eqs. (3) where α i and βi are one-quarter (¼), where i=0, 1, 2, 3. Similarly, using Eqs. (1) and (3), it can be seen that in order to calculate the down-sampled Cb″, sixteen (16) multiplications and fifteen (15) additions are needed; and the down-sampled Cr″ need the same number of multiplications and additions.

One simple way to reduce this computational complexity is to re-use the value of a pixel for a predetermined number of adjacent, contiguous pixels. In other words, a predetermined number of pixels are skipped and are assumed to have the same values. The drawback of this approach is that it produces serious block effects which compromise the quality of the processed image. Moreover, in order to reduce block effects, filtering processing may need to be performed which adds to the computational costs.

Hence, it would be desirable to provide a method and system that is capable of producing a relatively high image quality at reduced computational costs.

An image processing method and system using a low-complexity scheme is provided. According to one exemplary aspect of the method, input components from a RGB model are used directly to calculate the down-sampled components of a YCbCr model. For a general case, the down-sampled components of the YCbCr model are derived using the following equations:

Y i ′=0.29900 R i +0.58700 G i +0.11400 B i

Cb i ′=−0.16874 R i −0.33126 G i +0.50000 B i +2 SP/2

Cr i ′=0.50000 R i −0.41869 G i −0.08131 B i +2 SP/2

where R i , G i and B i are three input components of the color conversion for the pixel i under the RGB model.

In an exemplary instance where average down-sampling and a down-sampling rate of “4:2:0” are used, the following equations (derived from the equations above) are used to obtain the Y, Cb and Cr components under the YCbCr model:

The present invention provides a number of benefits and advantages. For example, as will be illustrated below, computational cost and complexity associated with image processing may be significantly reduced. Consequently, by reducing computational cost and complexity, the speed or rate of image processing can also be improved.

Reference to the remaining portions of the specification, including the drawings and claims, will realize other features and advantages of the present invention. Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention, are described in detail below with respect to accompanying drawings, like reference numbers indicate identical or functionally similar elements.

FIG. 1 is a simplified block diagram illustrating a typical image color conversion process and down-sampling;

FIG. 2 is a simplified diagram illustrating a down-sampling rate of “4:2:0”; and

FIG. 3 is a simplified block diagram illustrating an exemplary embodiment of the present invention.

The present invention in the form of one or more exemplary embodiments will now be described. The present invention proposes a method and system that can significantly reduce the computational complexity needed for the color conversion and down-sampling stages of image coder/decoders (codecs).

According to an exemplary method of the present invention, as shown in FIG. 3 , the input components from the RGB model are used directly to calculate the down-sampled components of the YCbCr model.

Using the exemplary method, for average down-sampling, the following equations are used to obtain the Y, Cb and Cr components under the YCbCr model:

Y i ″ = ⁢ 0.29900 ⁢ R i + 0.58700 ⁢ G i + 0.11400 ⁢ B i Cb ″ = ⁢ - 0.04219 ⁢ ∑ l = 0 3 ⁢ ⁢ R i - 0.082815 ⁢ ∑ l = 0 3 ⁢ ⁢ G i + 0.12500 ⁢ ∑ l = 0 3 ⁢ ⁢ B i + 2 SP / 2 Cr ″ = ⁢ 0.12500 ⁢ ∑ i = 0 3 ⁢ ⁢ R i - 0.10467 ⁢ ∑ l = 0 3 ⁢ ⁢ G l - 0.02033 ⁢ ∑ i = 0 3 ⁢ ⁢ B l + 2 SP / 2 Eqs . ⁢ ( 4 )

where R i , G i and B i are three input components of the color conversion for the pixel i under the RGB model.

Eqs. (4) are used to calculate the same three down-sampled components as those provided by Eqs. (2) above. As will be further illustrated below, with Eqs. (4), the number of computations (i.e., number of multiplications and additions) needed to calculate Cb″ is reduced from twenty-eight (28) (13+15) to fifteen (15) and the number of computations needed to calculate Cr″ is reduced from twenty-eight (28) to six (6), when compared to Eqs. (2) above. It should be noted that from a computational perspective, a subtraction is equivalent to an addition.

With respect to Eqs. (4), the number of computations needed to calculate Cb″ is determined as follows. For each of the summation of an input component (R i , G i or B i ), three (3) additions are performed, thereby resulting in nine (9) additions for all three input components. Next, three (3) multiplications are performed to multiply the summation results with their respective coefficients. Then, three (3) more additions are performed to sum up the result for Cb″. Therefore, the total number of additions and multiplications are twelve (12) and three (3), respectively, resulting in fifteen (15) total computations.

The number of computations needed to calculate Cr″ is determined as follows. Similarly, the summation of each input component is obtained. It is noted that at this point the summation results are readily available. These results have already been calculated when deriving Cb″. This same computational saving is achieved when the order of calculation of Cb″ and Cr″ is reversed. Likewise, three (3) multiplications are performed to multiply the summation results with their respective coefficients. Then, three (3) more additions are performed to sum up the result representing Cb″. Therefore, the total number of additions and multiplications are three (3) and three (3), respectively, resulting in six (6) total computations.

As previously noted in connection with Eqs. (2), the total computational cost for calculating Cb″ and Cr″ is fifty-six (56), i.e., fifteen (15) additions and thirteen (13) multiplications each. In contrast, under the above exemplary method, the total computational cost for calculating Cb″ and Cr″ is twenty-one (21), i.e., three (3) multiplications and twelve (12) additions for Cb″ and three (3) multiplications and three (3) additions for Cr″, or vice versa. The foregoing computational saving as illustrated above is achieved on a per pixel group basis. As the number of pixels that need to be processed increases, the computational saving correspondingly increases as well.

It should be noted that the results obtained above with respect to Eqs. (4) are based on an input pixel group size of four (4), i.e., i=(0, 1, 2, 3). Data from the corresponding pixels in each input pixel group is down-sampled to generate the corresponding Yi″, Cb″ and Cr″ components. There are four (4) corresponding constituents for each input component, R i , G i and B i (i=0, 1, 2, 3), that are used to calculate every Cb″ and Cr″. It should be understood that the size of the input pixel group may vary depending on the specific design and/or constraints of a particular application. For example, the size of the input pixel group may be eight (8), sixteen (16) or thirty-two (32), etc. A person of ordinary skill in the art will know how to determine the appropriate size for the input pixel group.

Furthermore, the respective coefficients used to calculate Cb″ and Cr″ are determined on an empirical basis. It should be understood that these coefficients do not have to be precise. Substantially similar coefficients may be used depending on the conversion accuracy desired. Based on the disclosure provided herein, a person of ordinary skill in the art will know how to determine and select the appropriate coefficients.

Moreover, Eqs. (4) can be generalized to accommodate the general case as shown below and in Eqs. (3) (as opposed to simple average down-sampling).

According to Eqs. (5), Cb″ is the weighted summation of all Cb 1 ′. With simple arithmetic manipulations, it can be seen that, for Eqs. (5), the number of computations that are needed to obtain Cb″ is twenty-four (24), i.e., twelve (12) multiplications and twelve (12) additions. The foregoing is obtained by expanding out Cb″ and treating the constants “2 sp/2 ” in the four (4) Cb i ′ collectively as one single constant. Likewise, the same number of computations are needed to obtain Cr″ under Eqs. (5). In contrast, as mentioned above in connection with Eqs. (3), the number of computations needed to calculate Cb″ or Cr″ are thirty-one (31) (fifteen (15) additions and sixteen (16) multiplications).

Similarly, as described above, the input pixel group size may vary depending on the specific design and/or constraints of a particular application. With respect to Eqs. (5) above, the input pixel group size is also four (4), i.e., i=(0, 1, 2, 3). Likewise, the respective coefficients used to calculate each Cb i ′ and Cr i ′ are determined on an empirical basis. Again, substantially similar coefficients may be used depending on the conversion accuracy desired and a person of ordinary skill in the art will know how to determine and select the appropriate coefficients.

It should be noted that the present invention as described above could be generalized and applied to other FIR filtering algorithms. The reduction of complexity may vary depending on the specific filtering algorithm involved.

It should be understood that the present invention can be implemented using software, hardware or a combination of both. For example, an exemplary method of the present invention may be implemented in the form of control logic or modules, in an integrated or modular manner, using software or hardware. In another example, an exemplary method of the present invention may be implemented using hardware such as circuits and logic gates. Based on the disclosure provided herein, a person of ordinary skill in the art will know of the various ways and/or methods to implement the present invention.

Furthermore, it should be understood that the present invention can be employed in many different types of applications. For example, the present invention can be employed in a codec or microprocessor for image processing in an image processing or computer system. Based on the disclosure provided herein, a person of ordinary skill in the art will know of the various ways and/or methods to employ or incorporate the present invention in different types of applications.

It is understood that the examples and embodiments described herein are for illustrative purposes only and that various modifications or changes in light thereof will be suggested to persons skilled in the art and are to be included within the spirit and purview of this application and scope of the appended claims. All publications, patents, and patent applications cited herein are hereby incorporated by reference for all purposes in their entirety.