1	Graphics File Format and Data Compression Techniques (take 2) Week 10
2	Administrivia Attendance AES Exams
3	AES Meeting (tomorrow) Tuesday Night Feedback cancellation http://www.aes.org/sections/pnw/
4	Midterm Statistics Average: 82 High: 99, Low 59 Distribution: 9 A’s 13 B’s 8 C’s 3 D’s 1 F
5	Midterms See me if you need clarification Please make an appointment with me if you achieved less than a C
6	HW8 Examining jpeg Just what are the losses in lossy compression? Tools: brighten, difference
7	HW8 At low compression ratios: Compressed image appears the same as original But at higher compression ratios: ??
8	Rate Distortion Theory More Claude Shannon Information theory Determine min. amount of information R Should be communicated over a channel Such that the input signal Can be reconstructed at the receiver (output signal) Given distortion D
9	Rate Distortion Theory Provides theoretical bounds for max compression achievable using lossy techniques Existing lossy compression techniques’s use the general shape of rate-distortion fn’s for: Transforms Quantization Bit rate allocation procedures
10	Rate Distortion Theory Rate Number of bits per data sample Distortion Evolving definition Simplest: Variance of the difference between input and output signal (mean square error of differences) However better to incorporate models of human perception
11	Error classification I(c,r) Original image I'(c,r) An approximation (has been compressed and decompressed) 0 ≤ c < M 0 ≤ r < N The error between the images at a pixel is e(c,r) = I'(c,r) - I(c,r)
12	Mean Absolute Error Used in MPEG
13	Mean Square Error
14	Mean square signal to noise ratio If we write I'(c,r) = e(c,r) + I(c,r) We can view the reconstructed image as the original plus noise
15	RMS signal to noise ratio
16	JPEG Joint Photographic Experts Group ISO standard 10918-1 Digital Compression and Coding of Continuous-tone Still Images http://www.jpeg.org
17	Standards: Design by committee Many agendas: Corporate/Commercial must incorporate support for their product Ego Every participant needs to get something accepted into the std Consequently: standards are rarely fully implemented
18	JPEG Standard Subset commonly used/implemented: Sequential top to bottom encoding Progressive Multiple, progressively higher resolution images Image ‘improves’ as it downloads Not used Lossless Hierarchical
19	JPEG vs JFIF JPEG specifies the compressed bytestream JFIF JPEG File Interchange Format Specifies packing those bytes into a file
20	JFIF A data stream Like GIF or PNG Made up of components separated by markers Markers: 2 bytes, 1^st 0xFF (0xFF rarely occurs in JPEG data and is encoded as 0xFF 0x00)
21	JFIF Markers Start of image End of image Restart Define Huffman Table Define Quantization Tables Define restart interval Start of scan Start of frame, baseline Start of Frame, extended sequential Start of Frame, progressive Comment
22	JFIF Composition Big-endian format Start of Image (SOI) marker (1^st two bytes) 0xFF 0xD8 APP0 (application marker) Optional APP0 extension marker for thumbnails Tables
23	JFIF Composition cont. SOF (start f frame) Tables SOS (start of scan 1) Scan 1 data… Tables SOS (start of scan 2) … EOI (end of image)
24	JFIF is not the only JPEG file format EXIF Used by digital cameras Stores meta data http://exif.org JNG (pronounced jing) JPEG network graphics Related to PNG Supports transparency
25	What is JPEG good for? Compressing photographic content Smooth variation of tone and color Not good for text, line graphics, etc.
26	Motion JPEG (MJPEG) JPEG is used for hi quality video Chosen over MPEG Especially when editing is performed I worked on a COSMO Compress at SGI for Avid
27	JPEG Compression Ratios? Up to 10:1 Nearly indistinguishable results Up to 100:1 Recognizable images with artifacts
28	JPEG Compression Ratio Examples
29	JPEG Artifacts Blockyness Blurryness
30	JPEG Really about: Intelligently throwing away data
31	5 JPEG Encoding Steps (Begin with 24bit RGB image) YUV Color Space Conversion Chroma Subsampling DCT (Discrete Cosine Transform) Quantization Entropy Coding
32	1 YUV Color Space Conversion YUV (also Y,Cb,Cr) Y luminance Cb, Cr (chomaticity) Same color space used in NTSC Television Useful because human vision is more sensitive to detail in brightness than color
33	2 Chroma Subsampling ¼ resolution U, V (1/2 vertical ½ horizontal) Reduce storage requirements in half
34	Chroma Subsampling ratio 3 part ratio Ex: 4:4:4 1^st part: number of luma pixels in sample area 2^nd part: number of chroma pixels in odd lines 3^rd part: number of chroma pixels in even lines Optionally can change or elliminate subsampling
35	Chroma ratio examples From wikipedia
36	JPEG Chroma ratios 4:2:0 Default (decimate by 2x horizontally and vertically) 4:2:2 (decimate by 2x horizontally) 4:4:4 No downsampling
37	3 DCT (Discrete Cosine Transform) Each YUV component of image is tiled into 8x8 blocks DCT is used to convert each tile into frequency space
38	4 Quantization Motivation Human vision Good at seeing: Brightness differences over large areas Poor at distinguishing: Exact strength of high frequency variation So: We can greatly reduce information in high frequencies
39	JPEG Quantization Each component in frequency domain Divided by a constant (for the component) Result rounded to nearest integer Many hi-freq components rounded to zero Many remaining components become small positive or negative values
40	JPEG Quantization This is the largest lossy operation This stage is controlled by Q-Tables Q-Table selection controls the amount of compression By controlling the divisors per component, per frequency
41	Example Q Table
42	5 Entropy Coding Components are zig-zag ordered Groups similar frequencies together Zeros are run length coded Results are Huffman coded
43	Decoding ‘Simply’ reverse the 5 steps
44	JPEG Issues Old Fashioned Wavelet approaches achieve higher compression with better quality JPEG2000 Microsoft decoder contains buffer overrun problems Yes: You can ‘catch’ a virus (or worse) simply by looking at an image Forgent Networks 2002 patent issue?
45	Discrete Cosine Transform (DCT) Type of Fourier Transform Similar to DFT (discrete Fourier Transform) But uses only real numbers Basically a DFT of 2x length operating on real data with even symmetry
46	DCT DCT is used in JPEG because of its “energy compaction” property Most signal information tends to concentrate in low freq. components of DCT (approaches optimal transform for certain signals)
47	DCT-I
48	2D DCT Can be performed by Doing 1D DCT on rows Followed by a 1D DCT on the columns With clever mathematical optimization 8x8 DCT matrix multiplication with 5 multiplies 29 adds
49	Interesting questions What happens if a JPEG compressed image is re-compressed Perhaps at a higher compression ratio Or repeatedly at the same ratio Is additional data degraded?
50	Interesting questions Does an image have to be decompressed to perform standard image operations to? Crop Brighten Create histogram
51	Interesting questions Are certain operations even more efficient in ‘compressed space’?
52	Interesting questions How is it possible to generate optimal QTables for any given image?