1	Graphics File Format and Data Compression Techniques (take 2) Week 13
2	Administrivia Attendance Final Monday December 13^th 6:00-7:30 Michelangelo
3	Final Lecture Lots of unanticipated changes Thanks for being flexible I have enjoyed this class
4	Seattle SIGGRAPH Wednesday 6:00, Plato (might move the room) Robert Quattlebaum, Voria Studios 2D’s Not Dead On building an animation studio on your own tools + open source http://seattle.siggraph.org
5	Audio Anecdotes Volume 3 CD Keep those volunteers coming See me after class Email me: keng@sworks.com
6	Tonight Blow through MPEG-4 Wavelets Fractal Compression Final Review
7	MPEG-4 Audio Covers many forms of digital audio Low bitrate speech Full bandwidth audio Structured Audio
8	MPEG-4 Structured Audio 6 Components SAOL: Orchestra Language SASL: Score Language SASBF: Sample Bank Format MIDI semantics Describe how to control SAOL with MIDI Scheduler Takes above and creates sound AudioBIFS Make audio soundtracks in MPEG-4 using tools and effects processing techniques
9	SOAL (pronounced sail) Synthesis language Describes synthesizers Most any technique may be described FM, physical modeling, sampling, granular synth, subtractive synth, etc.
10	SASL Simple language to control SAOL synthesizers Tells SAOL What note to play How loud to play note Tempo How long notes last How to modulate notes Very Similar to MIDI
11	SASBF (“sazz-biff”) Format to encode/transmit banks of sound samples Used in wavetable/sampling sythesis Somewhat compatible with DLS (MIDI downloadable sounds)
12	AudioBIFS Binary Format for Scene Description Describes how different objects in structured audio scene fit together MPEG-4 components: Video clips Sounds Animation BIFS was based on VRML (virtual reality modeling language) For example BIFS might describe the audio ‘mix’ for different instruments, and vocals including attributes like reverb
13	MPEG Session Layer Similar to OSI stack’s Session Layer One below presentation layer One above transport layer mpeg Ties video, audio, and meta data into a common stream for transmission This is where synchronization and media interleaving is performed
14	Wavelets Based on Quantum field theory Signal Analysis Function Space Theory Replaces Fourier methods
15	Wavelets applications Replacement for FFT in Compression Analysis Also used for Noise reduction
16	Comparison: Wavelets vs Fourier Analysis Breaks a signal into constituent Fourier Analysis Series of sinewaves of different frequency Wavelet Analysis Wavelets Shifted/scaled versions of the mother wavelet
17	Fourier Basis Functions Localized in frequency Not in time (small change in freq. make changes everywhere in time domain)
18	Wavelets Localized in frequency (scale) Via dilations Localized in time Via translation
19	Comparison: Sine Wave vs Daubechies5 Wavelet Sine wave: smooth, infinite duration Wavelet: irregular, localized Supports signals with discontinuities or sharp transitions Localize features Images: Joshua Altmann
20	Wavelet properties Continuous Smooth (all derivative should exist) Orthogonal Oscillatory Should integrate to 0 ‘Waves’ as much above 0 as below 0
21	Wavelet properties Diminutive ‘let’ Well localized Zero outside of a finite region Easy calculation of direct and inverse transform Admissibility (band-pass like spectrum)
22	Wavelet properties Stable representation Small change to image yield small change to transform Uniqueness Transform for an image should be unique
23	Computational Complexity FFT (Fast Fourier Transform) O= nlog(n) Fast Wavelet Transform Linear O= n
24	Haar Wavelet Simplest/Oldest Wavelet (used for >80 years) Step function 1 on [0,1/2) -1 on [1/2,1) Can approximate any continuous function
25	Haar Dialations and Translations
26	Haar issues Not continuous Hence uneconomical approximation of smooth functions Many ‘families’ of wavelets
27	Wavelet Transform If One wavelet acts as a bandpass filter Then Multiple dilated filters act as a filter bank (subband coding) Can analyze a signal by iterating over filter bank (each time splitting the signal)
28	Iterative filter bank
29	JPEG2000 .jp2 Motivated by 8x8 blockiness of JPEG Wavelet based Very Large Images 2³²x 2³² vs JPEG’s 2¹⁶ x 2¹⁶ Bitrate of < 0.25bpp (for highly detailed B/W images) Progressive transmission By Resolution or region
30	Adoption issues Perceived Patent danger Highly protected area of mathematics JPEG2000 is not license-free But licenses for core tech made freely available
31	JPEG2000 vs PNG JPEG2000 has a lossless mode Not goot at coding large number of identical pixels Hence JPEG2000 will be used for photos PNG for diagrams (Consider GIF and JPEG presently)
32	Artifact Comparison
33	Artifact Comparison JPEG2000 on the left JPEG on the right Both Images 0.5bpp, 1:48 compression ratio Images from Aleks Jakulin
34	Chroma Subsampling JPEG2000, Original, JPEG
35	Ringing Representing images as sum of smooth oscillating waves Good for smooth gradients Ringing on sudden transitions JPEG2000, Original, JPEG
36	JPEG2000 vs JPEG JPEG 2000 Pros: Eliminates blocky artifacts JPEG 2000 Cons: Creates blurring/smoothness Slightly increases ringing (The cons are seen as less objectionable)
37	Problem: Mixed Content Consider Real world content Magazine articles TV News Websites Mixture of Images/gradients Text/Line art
38	Hybrid techniques Separate text and photo layers in image Compress each layer using most appropriate compression scheme: Photos: JPEG like Diagrams: PNG like Text: OCR then store ASCII, font and color info
39	Proprietary hybrid formats JBIG, DjVu, Microsoft’s document format Example compression: Tiff raw image: 31MB JPEG: 604kB DjVu: 70kB In general these techniques produce high quality representations in roughly the same size as an HTML page: 50KB Viewers available free Compressors expensive
40	Fractal Compression (troubled history) Interesting application of fractals Explored by Michael Barnsley and later by Arnaud Jacquin in the 1980’s Some early commercial ‘wins’ Used in Microsoft’s Encarta Encyclopedia In part hasn’t caught on due to patents
41	Fractal Compression Pros Highly compressed fractal images look better than JPEG images Potentially very quick to decode Resolution independent Appear more ‘natural’ when zoomed in Barnsley claims an effective 2,500:1 compression ratio But this is based on an expanded (zoomed) image
42	Fractal Compression Cons Slower (than JPEG) to encode requires human intervention? Patented
43	Fractal Compression Example Original Enlarged JPEG Enlarged Fractal Notice ‘new’ realistic detail in the fractal?
44	Fractals Self similar patterns Naturally occurring Consider a Shoreline Interesting properties Fractional Dimensionality Shoreline is somewhere between 1D and 2D Example: How long is a shoreline?
45	Shoreline How long is a shoreline? Answer It all depends on what scale you mention length! Imagine going into each inlet, cove, grain of sand…
46	Dimensionality Point: 0D Line: 1D Plane: 2D Space: 3D Jaggy shoreline: ≈1.25 Smooth shoreline: ≈1.0
47	Most famous fractal Mandelbrot Set Z_{n + 1} = Z_nx Z_n + C Iterate at each coordinate (in imaginary plane) until equation diverges to infinity Coordinates that never diverge Are part of set Colored black Other coordinates are colored based on how quickly they diverge
48	Mandelbrot set Entire set Fully ‘zoomed out’ Notice self similar ‘blobs’
49	Mandelbrot set in neighborhood of (0.282, -0.01)
50	Mandelbrot Set History Recursive family of equations first explored around 1905 Required fast computers to analytically explore the space 1975 Mandelbrot released Les Objets Fractals: Forme, Hasard et Dimension
51	Iterated Function Systems Consider a photo copier It shrinks the original image Then prints multiple overlapping copies Repeat ad-infinitim Affine transforms may be applied: Translate, scale, shear, rotate images
52	IFS Attractor When a given IFS is run A unique image emerges Examples: Sierpinski’s triangle Barnsley’s fern Interactive demo at: http://bofh.priv.at/ifs
53	IFS Attractors Real objects may be defined/constructed in a similar way: Real Ferns Brains Lungs Bones
54	Collage Theorem Proves for a large class of real-world images Compact fractal representations must exist However no general purpose algorithm is known
55	A new kind of Science Stephen Wolfram (Creator of Mathematica) Spent 10 years creating the book Makes argument that all phenomena may be explained by cellular automata theory
56	Fractal Compression Summary Fabulously complicated objects (ie Mandelbrot set) may be encoded in tiny form Probably not very interesting for image compression (wavelet approaches currently better) Unless the infinite zoom capability is desireable A great way to encode: Textures, clouds, ferns, etc.
57	Steganography From the Greek: Hidden message Hiding things in plain site Nobody but the intended recipient knows existence of message
58	History Named from Johannes Trithemius’s 1492 book Steganographia Cryptographic/Steganographic treatise disguised as a book on black magic! Spirits communicating over a distance See: http://www.esotericarchives.com/tritheim/stegano.htm
59	Contrast with Cryptography Hiding the meaning of the message Not the presence of the message A steganographic message often may 1^st be encrypted
60	Steganography applications ‘Hot’ topics Watermarking Used by recording industry Communication w/o interception Used by terrorists
61	Watermarking Used to mark media so as to identify owner Media Images, Music, Video
62	Watermarking Challenges Can’t degrade quality But by definition: have to change the content
63	Watermarking Challenges Has to be robust (Difficult to remove) over common operations Imperfect copy Lossy compression Cropping Change of eq/brightness
64	Easier when you care about only the message Then the delivery mechanism is secondary You don’t care about: Degradation of the carrier unless it exposes the presence of a message How robust the message is to change, so long as it reaches its intended destination
65	Classic Steganography Designing text such that every nth letter is part of message
66	Evaluations! Need a student volunteer to turn these in
67	Final: Material Emphasizing material from 2^nd ½ Big concepts from 1^st ½ that pertain to lossy compression will be there too
68	Final: Style Expect much the same mix of problems as midterm Show me that you understand the concepts and can apply them
69	Final: Full Credit People lost potential credit on midterm For full credit: Show all work Show units for all values Start a problem even if you can’t complete it
70	How to study Do all readings! Review all notes (online) Understand how to ‘work’ classic problems/algorithms I.e. Hamming codes
71	Exam Same as midterm Closed book No computers/calculators
72	Good stuff since midterm JPEG Color space conversion Color reduction Macro blocks DCT Quantization/Q-Tables
73	Good stuff since midterm MPEG Motion estimation MP3 Wavelets Fractals IFS Fractal Compression Steganography