A METHOD FOR REVERSIBLE COLOR TRANSFORM USING

CANONICAL SIGNED DIGIT

Technical Field

[1] The present invention relates to color transform. More particularly, this invention relates to a method for reversible color transform (RCT) that can enhance the speed of invertible integer color transform as a canonical signed digit (CSD) system and a common pattern technique are applied to the invertible integer color transform which can precisely implement an inverse transform matrix without causing a rounding-off error according to integerization. Background Art

[2] A color coordinate system for displaying standard colors is used to process color images for various purposes. Color coordinate systems include RGB, CMY, HSI, YUV, YC _b C _r , etc. Color transform used for performing transformation between color coordinate systems is composed of a 3x3 matrix. If color transform is implemented via a general fixed-point processor, approximate values for color coordinate coefficients are used. This causes a rounding error and makes it impossible to precisely implement an inverse transform matrix.

[3] Technology has been developed to overcome the disadvantages of the fixed-point processor. Recently, an invertible integer color transform was developed by Pei, et al. The reversible integer color transform has an advantage in that it can precisely implement an inverse transform matrix without causing a rounding-off error according to integerization, but its performance speed needs to be enhanced. Disclosure of Invention Technical Problem

[4] The present invention solves the above problems, and provides a method for reversible color transform that can enhance the speed of invertible integer color transform as a canonical signed digit (CSD) system and a common pattern technique are applied to the invertible integer color transform which can precisely implement an inverse transform matrix without causing a rounding-off error according to integerization. Technical Solution

[5] In accordance with an exemplary embodiment of the present invention, the present invention provides a method for reversible color transform using canonical signed digit (CSD), including: (1) transforming respective color coordinate coefficients to CSD numbers; (2) extracting a common pattern from the CSD numbers and previously performing computation with respect to the common pattern; and (3) performing a reversible color transform, using the previously computed result.

[6] Preferably, the CSD numbers are a set of ternary number composed of the digits -1,

0, and +1. There is no case where both numbers at successive CSD digits are not zero.

[7] Preferably, the extraction and the computation includes extracting a common pattern from all of the CSD numbers.

[8] Preferably, the reversible color transform is an invertible integer color transform.

Advantageous Effects

[9] As described above, the method for reversible color transform, according to the present invention, can enhance the speed of invertible integer color transform as a canonical signed digit (CSD) system and a common pattern technique are applied to the invertible integer color transform which can precisely implement an inverse transform matrix without causing a rounding-off error according to integerization. Brief Description of Drawings

[10] The features and advantages of the present invention will become more apparent from the following detailed description in conjunction with the accompanying drawings, in which:

[11] Figure 1 shows a flow chart describing a method for reversible color transform according to an embodiment of the present invention;

[12] Figure 2 shows a table where the last four of the total eight coefficients in a matrix transforming from a RGB color coordinate system to a UVW color coordinate system are expressed as a CSD format;

[13] Figure 3 shows a table where common patterns are expressed using all eight transform coefficients; and

[14] Figure 4 shows a table where common patterns are expressed using various types of color transform coefficients.

[15] <Brief Description of Symbols in the Drawings>

[16] SlO: perform CSD transform

[17] S20: apply common pattern technique

[18] S30: perform reversible color transform

Best Mode for Carrying out the Invention

[19] Hereinafter, exemplary embodiments of the present invention are described in detail with reference to the accompanying drawings.

[20] Figure 1 shows a flow chart describing a method for reversible color transform according to an embodiment of the present invention. As shown in Figure 1, the method includes performing a canonical signed digit (CSD) transform (SlO), applying a common pattern technique (S20), and performing a reversible color transform (S30). [21] At step SlO, respective color coordinate coefficients are transformed to CSD numbers. A CSD system can minimize non-zero numbers and thus reduce the frequency of addition in the hardware multiplier. The encoding system of the CSD system is based on a set of ternary numbers composed of the digits -1, 0, and +1. There is no case where both numbers at successive CSD digits are not zero. That is, this case can be expressed by an equation, C ₁ x C ₁ = 0 (C ₁ denotes the i-th CSD digit). Therefore, if the binary number of N bits is transformed to CSD numbers, the CSD system has less than the (N+l)/2 of non-zero numbers and thus does not need to find the frequency of the number in order to perform multiplication. An estimated value for the number of non-zero numbers at CSD numbers is asymptotically converged to N/3 + 1/9. The CSD number has 33% less non-zero numbers, on the average, than the binary number. Table 1 below shows an example where the binary number of N=4 is transformed to the CSD number. In Table 1, * is indicative of -1. When the binary number is transformed to the CSD number, as described in Table 1, it is ascertained that, with respect to negative numbers, the number of non-zero numbers at the binary number is less than the number of non-zero numbers at the CSD number, and the number 1 is reduced from the total number of 32 to 23.

[22] Table 1

[Table 1] [Table ]

[23] At step S20 in Figure 1, a common pattern is extracted from coefficients of CSD numbers which were transformed at SlO and then previously computed. The present invention employs a common pattern technique to reduce the numbers of adder and subtracter for CSD numbers. As a common pattern is extracted from all CSD coefficients and previously computed by the application of the common pattern technique, the numbers of addition and subtraction can be reduced. When a common pattern is used in hardware of a plurality of multipliers, the total amount of computation can be reduced by 50%.

[24] Figure 2 shows a table where the last four of the total eight coefficients in a matrix transforming from a RGB color coordinate system to a UVW color coordinate system are expressed as a CSD type. In color transform, respective multiplications can be expressed as g,-x, where g, denotes the matrix coefficients in one column (i = 1, ..., 8) and x denotes binary input, 1 or 0. If respective coefficients are expressed as the CSD format, such as (M is the total bit length), the multiplication is expressed by following Math Figure 1. [25] MathFigure 1

[Math.l]

M-I

J = O [26] As shown in the table of Figure 2, the same circle has the same common pattern at the respective coefficients. Arithmetic operations for g ₅ to g ₈ in table of Figure 2 are expressed as the following Math Figure 2, [27] MathFigure 2

[Math.2] g. - χ = -χ + x « 2 g ₆ - x = -x « 3 + x « 5 g _η • x = x + x « 3 + x « 6 g- _g ^■ x = x + x « 2 + x « 5

[28] Where, x « a means that x is shifted left a times (left shift). A common pattern for the four coefficients is 10* (indicated by the solid line circle) and 100* (indicated by the dotted line circle) and can be defined as the following Math Figure 3.

[29] MathFigure 3

[Math.3]

W ₁ = —X + X « 2,

W ₂ = —X + X « 3

[30] Using Math Figure 3, Math Figure 2 can be expressed as the following Math Figure

4. [31] MathFigure 4

[Math.4]

Ss = ^w l

§6 = ^w ι « ³ g ₇ — x + W ₂ « 3

[32] By comparing Math Figure 4 with Math Figure 2, it can be ascertained that the number of addition is reduced from 9 to 5 by using the common patterns, W ₁ . [33] Figure 3 shows a table where common patterns are expressed by using all eight transform coefficients. As shown in the table of Figure 3, when the transform coefficients are expressed by the binary number, the total number of addition is 33. On the contrary, when the transform coefficients are transformed to the CSD format and shared with common patterns, the total number of addition is reduced to 16. The reduction rate is larger if all eight coefficients in the table of Figure 3 are used than if only four coefficients in the table of Figure 2 are used. Through this result, it can be ascertained that a higher number of coefficients in the common pattern technique and an increased rate of multiplication produces a more effective performance.

[34] Figure 4 shows a table where common patterns are expressed in terms of various kinds of color transform coefficients. As shown in the table of Figure 4, a common pattern technique is applied to transform coefficients when an RGB color coordinate is transformed to a KLA color coordinate; RGB to IV ₁ V ₂ ; RGB to YC _b C _r ; RGB to DCT; RGB to YIQ; RGB to XYZ; and RGB to UVW.

[35] At step S30 in Figure 1, a reversible color transform is performed using the result that was previously computed for the common pattern at S20. As described above, the reversible color transform is an invertible integer color transform.

[36] Table 2 below shows the computation rates for respective reversible color transformations by comparing therewith. As shown in Table 2, compared with the conventional reversible color transform (or a transformation using 2's complement), the reversible color transform according to the present invention, i.e., a transformation using a CSD number and a common pattern, can reduce the number of adders by approximately 40-65%.

[37] Table 2 [Table 2] [Table ]

[38] Although preferred embodiments of the present invention have been disclosed for illustrative purposes, those skilled in the art will appreciate that various modifications, additions and substitutions are possible, without departing from the scope and spirit of the invention as disclosed in the accompanying claims.