Scribd Logo
Upload

Welcome to Scribd!

  • 22 views

    CSE679: JPEG: JPEG Goals JPEG Compression Steps Lab

    Uploaded by

    banana
    The document describes the goals and steps of JPEG compression. The goals are for JPEG to have tunable compression, be implementable in hardware, and work independently of data format or size. The compression steps include picture preparation into blocks, forward DCT, quantization using tables, and entropy encoding including differential encoding, run-length encoding, and Huffman encoding. A lab project is assigned to implement these steps on sample data.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    CSE679: JPEG: JPEG Goals JPEG Compression Steps Lab

    Uploaded by

    banana
    22 views24 pages
    The document describes the goals and steps of JPEG compression. The goals are for JPEG to have tunable compression, be implementable in hardware, and work independently of data format or size. The compression steps include picture preparation into blocks, forward DCT, quantization using tables, and entropy encoding including differential encoding, run-length encoding, and Huffman encoding. A lab project is assigned to implement these steps on sample data.

    Original Description:

    a

    Original Title

    Jpeg

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes the goals and steps of JPEG compression. The goals are for JPEG to have tunable compression, be implementable in hardware, and work independently of data format or size. The compression steps include picture preparation into blocks, forward DCT, quantization using tables, and entropy encoding including differential encoding, run-length encoding, and Huffman encoding. A lab project is assigned to implement these steps on sample data.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    22 views24 pages

    CSE679: JPEG: JPEG Goals JPEG Compression Steps Lab

    Uploaded by

    banana
    The document describes the goals and steps of JPEG compression. The goals are for JPEG to have tunable compression, be implementable in hardware, and work independently of data format or size. The compression steps include picture preparation into blocks, forward DCT, quantization using tables, and entropy encoding including differential encoding, run-length encoding, and Huffman encoding. A lab project is assigned to implement these steps on sample data.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 24

    CSE679: JPEG

     JPEG goals
     JPEG compression steps
     Lab
    JPEG Goals

     JPEG: Joint Photographic Experts Group


     Applications can tune compression level
     Should have tractable computational complexity
     Should be possible to implement in hardware
     Compression scheme should be independent of
    data format
     PAL/NTSC etc. shouldn’t matter
     Independent of picture size, colors etc.
     Lossless, hierarchical, sequential, and
    progressive coding should be possible.
    JPEG Compression Steps
     Picture preparation
     Pixel
     Block, MCU (Minimum Coded Unit)

     Picture processing
     FDCT

     Quantization
     Entropy encoding
     Differential encoding (belongs to Source encoding)
     Run-length encoding
     Huffman encoding
    Picture Preparation

     JPEG specifies a very general image model.


     A source image consists of at least one and at
    most 255 components.
     Components may be assigned to the three colors RGB,
    YIQ or YUV signals.
     Convert each component into 8 × 8 data blocks
     Each pixel is represented by p (8, or 12) bits.
     If p = 8, each pixel is an integer in the range of 0 to
    255.
    Processing – Forward DCT

     Shift: The pixel values are shifted into the range


    [-128, 127].
     DCT expression

    7 j
    Some Observations of Forward DCT

     All 64 values in the input matrix, P[x, y]


    contribute to each entry in the transform matrix,
    F[x, y] to generate 64 new samples
     F[0,0] is the mean of all 64 values in the matrix,
    known as the DC coefficient, others are called
    as the AC coefficients.
    DCT Computation Features
    DCT Computation Features
    Quantization

     FQ[x, y] = Integer Round (F(x, y)/Q(x, y))


     Different coefficients are treated separately
    based on quantization table.
    An Example of Quantization
    An Example of Quantization Table
    Entropy Encoding
     Vectoring
    o 2-D matrix should represent the values in the form
    of a single-dimension vector.
    o Scan in zig-zag order
    Differential Encoding

     The DC coefficient varies only slowly from one


    block to the next.
     12, 13, 11, 11, 10, ……
     Only the difference in the preceding block is
    encoded.
     12, 1, -2, 0, –1
    Run-length Encoding

     The AC coefficients are encoded in the form of a


    string of pairs of values (skip, value)
     (0,6) (0,7) (0,3) (0,3) (0,3) (0,2) (0,2) (0,2) (0,2) (0,0)
    Huffman Encoding

     Use variable length codes


     Most frequently used symbols coded with fewest bits
     The intermediate symbol sequence
     DC coefficient: (sss, value)
    • sss: the number of bits needed
    • value: the encode value
     AC coefficient: (skip, sss) (value) with run-length encoding
    • skip: the number of consecutive 0s
    • sss: the number of bits needed to encode the value
    • value: the encode value
     Huffman code
     DC coefficients: 12 = (4, 12) = (1011100)

     AC coefficient: (0, 6) = (0, 3) (6) = (100110)


    Summary
     DC coefficient
     Input: 12, 13, 11, 11, 10, ……
     Differential encode: 12, 1, -1,-1,-2…
     The intermediate symbol sequence: (sss, value)
     Huffman code:
    • P160 (b) ⇒ sss
    • P160 (a) ⇒ value
    • Example: 12 = (4, 12) = (1011100)
     AC coefficient
     Input: 6, 7, 3, 0, 0, 3, 3, 2, 0, 0, 0
     Run-length encoding: (0,6) (0,7) (0,3) (2,3) (0,3) (0,2) (0,0)
     The intermediate symbol sequence: (skip, sss) (value)
     Huffman code:
    • P163-164 ⇒ (skip, sss)
    • P160(a) ⇒ value
    • Example: (0, 6) = (0, 3) (6) = (100110)
    Lab Project
     Objective: be familiar with JPEG
     Description
     Input: an original 8 × 8 block ⇒ original data (the value of
    each pixel is in the range of [0, 255]) (given by the
    Instructor)
     Steps:
    • Shifted to the range of [-128, 127]
    • FDCT (round: 1.6 → 2, -1.6 → -2, 1.5 → 2, 1.1 → 1)
    (π = 3.141592654)
    • Quantized with the given quantization table (see the given
    example) (round) (round: 1.6 → 2, -1.6 → -2, 1.5 → 2, 1.1 → 1)
    • Zig-zag coded
    • Converted to the intermediate symbol sequence with run-length
    encoding on AC coefficients
    • Encoded to bit sequence with Huffman encoding (based on the
    given default Huffman codewords tables) ⇒ compressed data
    • The compression ratio
    = original data size (i.e., 64 × 8)/compressed data size
     Output: print out all the results of the above steps into
    different files (The names and formats of output files should
    follow the files put on the web.)
    Lab Project
     Team: 2 or 3 students
     What should be turned in (via email to TA, subject: 679
    project)?
     Put all codes into one file (source_jpeg.c (.cpp) with clear
    comments (softcopy)
    • Make sure TA can understand, compile, and run your codes on
    UNIX machines. All the codes should be in C or C++.
     A report including a summary (2 ≤ page # ≤ 5) and the
    source code file, and result files (hardcopy or softcopy either
    in PDF)
     How will TA grade?
     Correctness: TA will use his own data to test your codes.
     Clearness: TA will check whether your code and report are
    understandable.
     Fairness:
    • Students in the same teams get the same scores.
    • No copy! All students involved in copy will get ZERO.
    Example - Original Block

    140 144 147 140 139 155 179 175

    144 152 140 147 140 148 167 179

    152 155 136 167 163 162 152 172

    168 145 156 160 152 155 136 160

    162 148 156 148 140 136 147 162

    147 167 140 155 155 140 136 162

    136 156 123 167 162 144 140 147

    148 155 136 155 152 147 147 136


    Example - Shifted Block
    12 16 19 12 11 27 51 47

    16 24 12 19 12 20 39 51

    24 27 8 39 35 34 24 44

    40 17 28 32 24 27 8 32

    34 20 28 20 12 8 19 34

    19 39 12 27 27 12 8 34

    8 28 -5 39 34 16 12 19

    20 27 8 27 24 19 19 8
    Example -After FDCT

    186 -18 15 -9 23 -9 -14 -19

    20 -34 27 -9 -11 11 14 7

    -11 -23 -2 6 -18 3 -20 -1


    -8 -5 15 -15 -8 -3 -3 8

    -3 10 8 1 -11 18 18 15
    4 -2 -18 8 8 -3 1 -7
    9 1 -3 4 -1 -7 -1 -2

    0 -8 -2 2 1 4 -6 0
    Example - Quantization Table

    3 5 7 9 11 13 15 17

    5 7 9 11 13 15 17 19

    7 9 11 13 15 17 19 21

    9 11 13 15 17 19 21 23

    11 13 15 17 19 21 23 25

    13 15 17 19 21 23 25 27

    15 17 19 21 23 25 27 29

    17 19 21 23 25 27 29 31
    Example - After Quantization

    62 -4 2 -1 2 -1 -1 -1
    4 -5 3 -1 -1 1 1 0

    -2 -3 0 0 -1 0 -1 0

    -1 0 1 -1 0 0 0 0

    0 1 1 0 -1 1 1 1

    0 0 -1 0 0 0 0 0

    1 0 0 0 0 0 0 0

    0 0 0 0 0 0 0 0
    Example – Other Steps
    Zig-zag sequence
    62,-4,4,-2,-5,2,-1,3,-3,-1,0,0,0,-1,2,-1,-1,0,1,1,0,1,0,1,-
    1,-1,1,-1,-1,1,0,0,0,-1,0,0,0,0,0,-1,0,-
    1,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0
    Intermediate symbol sequence
    (6)(62), (0,3)(-4), (0,3)(4), (0,2)(-2), (0,3)(-5), (0,2)(2),
    (0,1)(-1), (0,2)(3), (0,2)(-3), (0,1)(-1), (3,1)(-1),
    (0,2)(2),(0,1)(-1), (0,1)(-1), (1,1)(1), (0,1)(1), (1,1)(1),
    (1,1)(1), (0,1)(-1), (0,1)(-1), (0,1)(1), (0,1)(-1), (0,1)(-1),
    (0,1)(1),(3,1)(-1), (5,1)(-1), (1,1)(-1), (3,1)(1), (6,1)(1),
    (1,1)(1), (0,0)
    Encoded bit sequence (total 154 bits)
    (1110)(111110) (100)(001) (100)(100) (01)(01)
    (100)(010) (01)(10) (00)(0) (01)(11) (01)(00) (00)(0)
    (111010)(0) (01)(10) (00)(0) (00)(0) (1100)(1) (00)(1)
    (1100)(1) (1100)(1) (00)(0) (00)(0) (00)(1) (00)(0) (00)(0)
    (00)(1) (111010)(0) (1111010)(0) (1100)(0) (111010)(1)
    (1111011)(1) (1100)(1) (1010)
    Conclusion

     JPEG goals
     JPEG compression steps
     Picture Preparation
    • Component, block, and pixel
     Picture Processing
    • Forward DCT
     Quantization
    • Different coefficients are treated separately.
     Entropy coding
     Lab

    You might also like