Scribd Logo
Upload

Welcome to Scribd!

  • 54 views

    By Basar KOC & Ziya ARNAVUT SUNY Fredonia

    Uploaded by

    Kashif Aziz Awan
    This document describes a technique for lossless compression of color-mapped images using a gradient adjusted predictor and pseudo-distance transformation. It begins by providing background on digital color models like RGB and color palettes. It then presents the proposed technique which uses a pseudo-distance matrix to rank color indices for prediction during encoding and decoding. Experimental results show the technique achieves better compression than other methods like GIF and Huffman coding on test images.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd

    By Basar KOC & Ziya ARNAVUT SUNY Fredonia

    Uploaded by

    Kashif Aziz Awan
    54 views20 pages
    This document describes a technique for lossless compression of color-mapped images using a gradient adjusted predictor and pseudo-distance transformation. It begins by providing background on digital color models like RGB and color palettes. It then presents the proposed technique which uses a pseudo-distance matrix to rank color indices for prediction during encoding and decoding. Experimental results show the technique achieves better compression than other methods like GIF and Huffman coding on test images.

    Original Description:

    COMSATS Institute of Information Technology Abbottabad FIT 2011

    Original Title

    FIT 2011 Gradient

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document describes a technique for lossless compression of color-mapped images using a gradient adjusted predictor and pseudo-distance transformation. It begins by providing background on digital color models like RGB and color palettes. It then presents the proposed technique which uses a pseudo-distance matrix to rank color indices for prediction during encoding and decoding. Experimental results show the technique achieves better compression than other methods like GIF and Huffman coding on test images.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    54 views20 pages

    By Basar KOC & Ziya ARNAVUT SUNY Fredonia

    Uploaded by

    Kashif Aziz Awan
    This document describes a technique for lossless compression of color-mapped images using a gradient adjusted predictor and pseudo-distance transformation. It begins by providing background on digital color models like RGB and color palettes. It then presents the proposed technique which uses a pseudo-distance matrix to rank color indices for prediction during encoding and decoding. Experimental results show the technique achieves better compression than other methods like GIF and Huffman coding on test images.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 20

    Gradient Adjusted Predictor with Pseudo-distance Technique for Lossless Compression of Color-mapped Images

    by Basar KOC & Ziya ARNAVUT SUNY Fredonia

    What are digital colors?


    Human beings perceive colors by the nature of the light reflected from an object!
    Achromatic Color: means literally without color
     Only intensities (amount of light)  Gray levels as seen on black/white TV-monitor  Ranges from black to white

    Chromatic Color: All colors other than neutral colors (white, black, and the pure grays), are chromatic.

    The word color in ordinary language is often used to refer exclusively to chromatic colors, e.g., color vs. black-and-white television.
    2

    RGB Color Theory


    RGB stands for Red, Green, Blue RGB color is in use in many devices,
    Televisions, computer screens, digital cameras.

    When the visible color spectrum wavelength (400-700 nm) is broken into thirds,
    RGB colors are the predominant colors.

    Three types of cone cells exist in human eye.


    Each cell is more sensitive to either
     short ( S ), medium( M ), or long( L ) wavelength light.

    These curves are often also referred as the tri-stimulus functions.

    RGB Color Space


    A single pixel consists of three components each in range of [0,255]. Each pixel is a triplet
    128 251 60 Pixel vector in memory = Final pixel in the image

    Caution! Sometimes pixels are not stored as vectors. Instead, first is stored the complete red component, then the complete green, then blue.

    Example RGB

    Size consideration in an RGB image


    The lowest resolution for a monitor
    Displaying a Windows desktop is 640 x 480 pixels.

    In a bitmap of this resolution, then, there would be 3 bytes per pixel,


    For a total of 640 x 480 x 3, or about 900 kilobytes.

    Bit-Depth = Color-Depth
    Number of Colors = 2^(Bit-depth) Bit-depth is the number of bits.
    It is also called Color resolution.

    Bit depth 1-bit 2-bits 3-bits 4-bits 8-bits 16-bits 24-bits


    7

    Color resolution 2 colors 4 colors 8 colors 16 colors 256 colors 65,536 colors 16,777,215 colors

    Calculation 2^1 = 2 2^2 = 4 2^3 = 8 2^4 = 16 2^8 = 256 2^16 = 65536 2^24 = 16.7 million

    Color Palettes
    Images look best
    If theyre stored with as RGB images with 16,777,216 colors.

    However, file seizes may be very large. For practical purposes,


    we would like to reduce the number of colors from 16,777,216 to 256 colors.

    Such files are referred to as using palette-color.


    The colors in a palette-color file are derived from a potential palette of 16,777,216 colors, but no more than 256 of them can be used in any one image.
    8

    Graphics Interchange Format (GIF)


    The GIF is one of the most commonly used graphic file formats, especially on the Internet.
    an indexed color image format.

    The color of the image is indexed in a palette. (a color-table) The GIF is only capable of supporting a maximum of 256 colors. Uses lossless compression algorithm.

    Structure of a BMP Color-Palette Image


    Information 56 bytes
    Size Dimensions
     Width, height Index 0 1 2 3 4 .. 254 255 R 28 19 34 39 44 .. 193 206 G 0 2 1 2 0 .. 211 212 B 1 5 1 3 2 .. 223 222

    Bit per pixel


     8, 4, 2, 1

    Color Table
     3 x 256 bytes at most

    The color-mapped table of an image

    10

    Euclidean Distance Metric


    Let E[a,b] be the Euclidean distance between two color indices a and b. (0 a, b 255)

    where,

    11

    E[a,b]: Distance between index a and index b. eR: Difference between R values of a and b indices. eG: Difference between G values of a and b indices. eB: Difference between B values of a and b indices.

    Euclidean and Pseudo Distance matrices


    Index 0 1 2 3 4 .. 254 255 R 28 19 34 39 44 .. 193 206 G 0 2 1 2 0 .. 211 212 B 1 5 1 3 2 .. 223 222

    Color-map table

    Distance matrix created from the color palette

    converted

    Pseudo-distance matrix
    12

    Encoding

    Reference pixel x and its neighbors

    Ranking with pseudo-distance matrix

    X is the index value to be predicted. a, b, c are neighboring indices. Using (a, x) we determine ranking value, or error e.

    Pseudo-distance matrix
    13

    Decoding
    In error matrix E,
    the index number of the first pixel at the top-left corner, call it a, is copied to I. Later we apply the following:
     Receive the error signal e of the next pixel from the encoded image.  In row a of the pseudo-distance matrix search the error signal value e. Emit the corresponding column value x as the original index value of the image.  Let x be a and repeat the process until we reach to the end of file.

    Clearly, in decoding process, we obtain original index values without any loss.
    14

    Decoding (cont.)
    3 1 2

    e11 e21 .. .. ei1 ..

    e12 e22

    e13 e23

    e14 e24

    e15

    ..

    .. .. a1 .. a2 . .. .. .. .. ..

    x12 .. e12 .. .. ..

    .. .. .. .. .. ..

    x13 .. .. .. e13 ..

    .. .. .. .. ..

    a1

    x1

    x2

    E: Encoded image

    P: Pseudo-distance matrix

    I: Image

    Copy e11 to I(1,1) Let a1 e11 Determine x12 by searching e12 in row a1. I(1,2) x12 Let a2 x12 Determine x13 by searching e13 in row a2. I(1,3) x13 We repeat the process similarly.
    15

    Why do we use the pseudo-distance transformation?


    100% 90% 80% 70% 60% 50% 40% 30% 20% 10% 0% 100% 90% 80% 70% 60% 50% 40% 30% 20% 10% 0%

    0 Sunset

    1 Serrano

    0 2 3 Yahoo Sunset Sea_dusk

    1 Serrano

    3 Yahoo

    Sea_dusk

    Before transformation
    16

    After transformation

    Why do we use the pseudo-distance transformation?

    Distribution of Music.bmp (n = 8) before and after transformation

    Distribution of Serrano.bmp (n = 256) before and after transformation

    17

    Binary Arithmetic Coder


    We observed that after the pseudo-distance metric is applied to indices of various color-mapped images, on some images percentage of 0s varies from 72-90. Hence, we applied context-adaptive binary arithmetic coder which includes run length coding and context modeling.

    This yields better compression gain than Huffman coder, which was originally proposed by Kuroki et al.
    18

    Experimental Results
    Images Benjerry Books Clegg Cwheel Descent Fractal Frymire Gate Ghouse Music Netscape Party8 Pc Sea_dusk Serrano Sunset Winaw Yahoo Average W. Avg. Normalized
    19

    #Colors 48 7 256 256 122 256 256 84 256 8 32 12 6 46 256 204 10 229

    Size 28,326 29,338 719,158 481,078 64,542 389,190 1,238,678 61,302 481,078 6,302 61,382 75,606 1,721,858 157,538 502,886 308,070 148,894 28,110 361,296

    GIF 1.239 3.046 3.623 1.492 2.928 6.923 1.485 2.939 3.713 2.482 2.113 0.854 1.694 0.323 1.629 2.601 0.997 1.983 2.337 2.328 1.223

    Huffman 1.789 3.901 3.161 1.915 3.153 5.72 2.089 2.987 3.802 2.885 2.297 2.273 2.605 1.025 2.07 2.197 2.47 2.498 2.713 2.695 1.415

    SAC 1.218 3.447 2.808 0.984 2.765 5.335 1.373 2.471 3.219 2.305 1.922 0.778 1.723 0.052 1.389 1.59 0.98 1.818 2.01 1.974 1.037

    Proposed 1.207 3.248 2.784 0.941 2.676 5.267 1.392 2.367 2.962 2.373 1.936 0.802 1.603 0.054 1.289 1.547 0.959 1.747 1.953 1.904 1.000

    Thank you!

    Questions?

    20

    You might also like