1


2

 Attendance (please sign in)
 Textbooks

3

 Won’t regurgitate readings in class
 Will emphasize key concepts
 (Readings Very Important!)
 Thanks for the (continued) feedback!

4

 Who has both books?
 Borders group order?
 Potential 20% discount too…

5

 1,2 resubmission (thanks)
 3, Questions?
 Request to change type of homeworks?

6

 To succeed in any pursuit
 Need to know what is to be accomplished
 Need to be able to measure progress

7

 Many examples from industry of failures less than full success
 We need to emphasize the fundamentals in this class

8

 We are attempting to digitally represent information
 Compression is really optimal representation

9

 Computers are digital
 The world is analog
 What do these terms mean?

10


11

 Analog?
 Digital?
 Something else?

12

 Symbolic description of continuous functions
 Manipulation
 Symbolic: Algebra/Calculus
 Numerical: Computer algorithms
 Ultimate compression/representation

13

 Consider:
 Pretty abstract sine wave…
 (unconstrained)

14

 Consider:
 Sound mathematically is
 Continuous function of amplitude over time

15

 An image can be described mathematically
 As continuous function of intensity over a two dimensional space
 Lumigraph
 Light intensity in 3Space
 MRI

16


17

 Bell Labs 1984
 Manipulation of digital images via mathematical expressions
 JIT compiler!
 Predates Photoshop, etc.
 http://spinroot.com/pico/
 Demo: c:\all\popi

18

 Represents images as
 256x256 array
 of 8 bit intensity values
 JIT Compiles expression
 Iterates expression over pixels

19

 Might be interesting to explore:
 Resolution independence
 Space filling
 (using lazy evaluation)

20

 My research at Microsoft
 Images
 Infinite extent
 Resolution independent
 Full algebra image composition

21

 Media algebra included
 Any form of audio
 Mathematically described fn of time
 Sampled digital sound
 MIDI, etc.
 Video
 Geometry

22

 How many bits required to store equation?
 How many bits for
 1 second of audio?
 Infinite duration audio?

23

 Where does the data we want to represent come from?

24

 I claim two sources:
 Examples?
 Characteristics of each?

25

 By definition:
 “Nature abhors a vacuum”
 Takes infinite energy to create an infinitely fast transition

26

 Can be anything at all
 May be a mathematical expression
 Often represents things impossible to create in reality
 Examples?

27

 An impulse
 Infinitely fast transition…
 But we find those all over:

28

 Doesn’t mean we shouldn’t try
 Very important to understand the limitations of our rendering system
 Ex: Mustn’t attempt to render freqs. higher than can be represented

29

 We understand frequency in sound
 What is frequency in:

30

 We are interested in rapid transitions over space
 Can be high or low amplitude

31

 The phenomena where
 Energy at a frequency that can not be represented
 Appears as incorrect, lower freq. energy
 In sound
 Hi freqs. appear as low frequency tones
 Examples in images? Video?

32

 Try examining a checkerboard pattern in a naďve viewer
 Incrementally shrink the size of the image
 At various points you will see patterns of a lower frequency appear

33

 Consider wagon wheels in ‘westerns’
 At some point an accelerating wagon’s wheels
 appear to slow down
 Then spin in reverse
 What is aliasing?

34

 A signal may be perfectly represented provided it is sampled at a rate
twice the highest frequency component of the signal
 This rate is known as the nyquist rate
 A signal thus sampled may be perfectly reconstructed
 Implies that a sinewave needs to be represented by two ‘samples’ per
period
 But why aliasing?

35

 If you can guarantee that you will examine the watch every minute
 Perfect timekeeping may be kept
 If that guarantee is not kept, then you will have to guess
 Perceptually we ‘guess’ that less than a full minute has passed since we
last checked

36

 We better meet nyquist limitations
 But how?
 Consider the naďve image viewer…

37

 The naďve image viewer must
 Filter high frequencies
 Better yet it must spread the energy in those high frequencies as lower
frequency information
 IE the, perhaps, blue checkerboard must be smeared before it is
decimated

38

 We sample
 To digitally represent the real analog world

39

 Sampling has similar obligations to nyquist
 We must sample at 2x the highest frequency present
 Otherwise aliasing occurs
 And aliasing can’t be removed later…
 But the real world is fractal
 Includes small quantities of extremely high energies everywhere

40

 Nothing is smooth
 Examine any smooth even polished surface under a microscope

41

 Everything in nature is smooth
 The earth at a distance appears to be completely smooth
 Even the highest mountains wouldn’t appear as particularly rough
 12mi diff between deepest trench and highest mountain
 12mi over 8,000mi diameter isn’t noticeable
 Globes, games, grossly exaggerate elevation!

42


43

 Sony/Philips Redbook audio (circa 1980)
 Analog sound is low pass filtered
 To remove freqs. Above 22050Hz
 Resulting signal is sampled 44100 times a second
 Each sample is encoded as a 16 bit value
 Why these values?

44

 22050Hz
 is beyond most adults’ ability to hear
 So the CD covers the full freq. range
 16bit quantization theoretically
 Provides 96dB of dynamic range

45

 But pro audio is
 Sampled 48000 times/second
 A multiple of cinematic 24 frames/second
 A standard before the CD
 Why the weird 44100Hz sampling rate?

46

 Some say
 To allow Beethoven’s 9^{th} to fit on the 120mm CD
 Others
 To make it difficult to digitally record CDs
 Sample rate conversion was very expensive in the early 80’s

47

 Why do audiophiles complain?

48

 Aliasing is not the only issue

49

 Quantizing an Analog Signal
 Equivalent to converting from a real to nbit integer value
 Real value must be rounded or truncated
 It is infinitely unlikely that the real value will ever be precisely a
whole number (representable by an integer)
 Resulting difference is called the quantization error

50


51


52

 Controlled by the clock input
 Converter samples analog input
 On high to low transition of clock
 Presents digital representation on digital bus

53


54


55

 The quantization error
 Has structure
 Is perceptible
 Must be masked

56

 But can allow it to appear as noise
 ‘Super’ sampling enables techniques like noise shaping to ‘hide’ the
noise where it is not perceivable

57

 Seem to hear the quantization error which most gear doesn’t correctly
mask
 Dither must be applied at each requantization stage
 Higher sampling rates and quantization
 Should enable well designed gear to overcome the failings of first
generation digital systems

58

 Digital cameras are engineered systems
 Have optical low pass filter
 Causing smearing across two pixels on the imager
 But the resulting 5MP to 12+MP images need to be resampled for your
application

59

 Video adds another dimension: time
 Typically video doesn’t attempt to perform temporal filtering
 This leads to interesting aliasing
 In NTSC video encodes color as horizontal frequency on 3.57 MHz sub
carrier
 Anyone catch “The Donald’s” illegal rainbow collar lastweek?

60


61

 When we study the Fourier Transform

62

 We decided we can do better than Huffman
 Huffman code provides most efficient coding if symbols must be
individually coded
 Higher order entropy analysis and Shannon tells us we can do better
 Take advantage of intersymbol correlation

63

 By not limiting ourselves to single symbol we can achieve higher
compression ratios using entropy coding techniques
 Dynamically generating multisymbol codebooks solves the problems of
 precomputing optimal tables
 Distributing tables
 LZW is a nice approach with a troubled past

64

 Lempel – Ziv – Welch
 Based on LZ77
 Patented

65

 Formats include
 UNIX compress (circa 1986)
 GIF (circa 1987)
 Provided much better compression than alternatives of the day
 First widely used compression
 Text could expect 2:1 ratios

66

 LZ78 assigned Sperry (Unisys) Filed Aug 10^{th} 1981
 2 assigned IBM
 Another assigned Sperry (Unisys)
 Canadian patent expired June 2004
 (last known LZW patent in effect)

67

 Compressor dynamically builds codebook
 Decompressor dynamically recovers codebook
 Codebook initially has 256 entries
 (one for every 8bit single character string)
 Every time a string not previously encountered is seen that string +
next char is added

68

 Output consists of indexes to the codebook
 Initially 9 bits
 Indexes grow to 16bits
 Special ‘flush’ index
