rgbcolor-spacelossless-compression

Lossless RGB to Y'CbCr transformation

I am trying to losslessly compress an image, and in order to take advantage of regularities, I want to convert the image from RGB to Y'CbCr. (The exact details of what I mean by RGB and Y'CbCr are not important here; the RGB data consists of three bytes, and I have three bytes to store the result in.)

The conversion process itself is pretty straightforward, but there is one problem: although the transformation is mathematically invertible, in practice there will be rounding errors. Of course these errors are small and virtually unnoticeable, but it does mean that the process is not lossless any more.

My question is: does a transformation exist, that converts three eight-bit integers (representing red, green and blue components) into three other eight-bit integers (representing a colour space similar to Y'CbCr, where two components change only slightly with respect to position, or at least less than in an RGB colour space), and that can be inverted without loss of information?

Solution

  • YCoCg24

    Here is one color transformation I call "YCoCg24" that that converts three eight-bit integers (representing red, green and blue components) into three other eight-bit (signed) integers (representing a colour space similar to Y'CbCr), and is bijective (and therefore can be inversed without loss of information):

     G          R          B     Y          Cg         Co
 |          |          |     |          |          |
 |          |->-(-1)->(+)   (+)<-(-/2)<-|          |
 |          |          |     |          |          |
 |         (+)<-(/2)-<-|     |->-(+1)->(+)         |
 |          |          |     |          |          |
 |->-(-1)->(+)         |     |         (+)<-(-/2)<-|
 |          |          |     |          |          |
(+)<-(/2)-<-|          |     |          |->-(+1)->(+)
 |          |          |     |          |          |
 Y          Cg         Co    G          R          B

forward transformation       reverse transformation

    or in pseudocode:

    function forward_lift( x, y ):
    signed int8 diff = ( y - x ) mod 0x100
    average = ( x + ( diff >> 1 ) ) mod 0x100
    return ( average, diff )

function reverse_lift( average, signed int8 diff ):
    x = ( average - ( diff >> 1 ) ) mod 0x100
    y = ( x + diff ) mod 0x100
    return ( x, y )

function RGB_to_YCoCg24( red, green, blue ):
    (temp, Co) = forward_lift( red, blue )
    (Y, Cg)    = forward_lift( green, temp )
    return( Y, Cg, Co)

function YCoCg24_to_RGB( Y, Cg, Co ):
    (green, temp) = reverse_lift( Y, Cg )
    (red, blue)   = reverse_lift( temp, Co)
    return( red, green, blue )

    Some example colors:

    color        R G B     Y CoCg24
white      0xFFFFFF  0xFF0000
light grey 0xEFEFEF  0xEF0000
dark grey  0x111111  0x110000
black      0x000000  0x000000

red        0xFF0000  0xFF01FF
lime       0x00FF00  0xFF0001
blue       0x0000FF  0xFFFFFF

    G, R-G, B-G color space

    Another color transformation that converts three eight-bit integers into three other eight-bit integers.

    function RGB_to_GCbCr( red, green, blue ):
    Cb = (blue - green) mod 0x100
    Cr = (red  - green) mod 0x100
    return( green, Cb, Cr)

function GCbCr_to_RGB( Y, Cg, Co ):
    blue = (Cb + green) mod 0x100
    red  = (Cr + green) mod 0x100
    return( red, green, blue )

    Some example colors:

    color        R G B     G CbCr
white      0xFFFFFF  0xFF0000
light grey 0xEFEFEF  0xEF0000
dark grey  0x111111  0x110000
black      0x000000  0x000000

    comments

    There seem to be quite a few lossless color space transforms. Several lossless color space transforms are mentioned in Henrique S. Malvar, et al. "Lifting-based reversible color transformations for image compression"; there's the lossless colorspace transformation in JPEG XR; the original reversible color transform (ORCT) used in several "lossless JPEG" proposals; G, R-G, B-G color space; etc. Malvar et al seem pretty excited about the 26-bit YCoCg-R representation of a 24-bit RGB pixel.

    However, nearly all of them require more than 24 bits to store the transformed pixel color.

    The "lifting" technique I use in YCoCg24 is similar to the one in Malvar et al and to the lossless colorspace transformation in JPEG XR.

    Because addition is reversible (and addition modulo 0x100 is bijective), any transform from (a,b) to (x,y) that can be produced by the following Feistel network is reversible and bijective:

     a        b
 |        |
 |->-F->-(+)
 |        |
(+)-<-G-<-|
 |        |
 x        y

    where (+) indicates 8-bit addition (modulo 0x100), a b x y are all 8-bit values, and F and G indicate any arbitrary function.

    details

    Why do you only have 3 bytes to store the result in? That sounds like a counter-productive premature optimization. If your goal is to losslessly compress an image into as small a compressed file as possible in a reasonable amount of time, then the size of the intermediate stages is irrelevant. It may even be counter-productive -- a "larger" intermediate representation (such as Reversible Colour Transform or the 26-bit YCoCg-R) may result in smaller final compressed file size than a "smaller" intermediate representation (such as RGB or YCoCg24).

    EDIT: Oopsies. Either one of "(x) mod 0x100" or "(x) & 0xff" give exactly the same results -- the results I wanted. But somehow I jumbled them together to produce something that wouldn't work.