1


2

 Attendance
 Exams graded but not curved
 Can see yours over break
 Will have them back next week (or in office?)

3

 Discuss
 Lossy Compression

4


5


6

 A backbone of compression
 Used as backend to most lossy algs.
 (need to understand this as we move forward)
 Many people failed to construct the tree

7

 3A Which has higher entropy? Throw of:
 I intended this to be a reasoning problem

8

 Unfortunately two conflicting factors to reason:
 2 dice have more possibilities (11 instead of 6) > RAISE ENTROPY
 2 dice have uneven distribution > LOWER ENTROPY
 Instead requires solution of the entropy calculation
 (or determine relative effect of factors> consider rock in canoe
puzzle)

9

 1 Die
 6 possibilities each with p(e)=1/6
 H(x)=1/6 log(1/6)  … 1/6 log(1/6)
 = 6*1/6 log(1/6)
 = log(1/6)
 = 2.587bits
 We know it must be < 3 bits
 since 3 bits can encode 2^3=8 values…

10

 2 Dice:
 36 possibilities, 11 outcomes
 P(2)=1/36, P(3)=2/36, P(4)=3/36, P(5)=4/36, P(6)=5/36, P(7)=6/36,
P(8)=5/36. P(9)=4/36, P(10)=3/36, P(11)=2/36, P(12)=1/36
 We know that H(X) < 4 since
 4 bits can encode 2^4=16 values…

11

 Crunching the numbers for 2 dice:
 H(x)= 3.2744
 Lower entropy than 1 11sided die
 Higher entropy than 1 6sided die
 Will receive credit for 3a
 (Which has greater entropy)
 So long as you attempted to answer it

12

 Best compression for roll of 1 die:
 Not compressible
 Huffman would yield optimal coding
 Best compression for roll of 2 dice:
 Huffman compression
 Uneven probability distribution
 No intra symbol dependencies
 (result of one roll not dependent on previous)

13

 unsigned *malloc(256*3+100*100);
 Grey scale palette
 Each component contains same value
 (have to assume that our RGB space is already normalized to perception)
 Luminance = Sum of components
 (we discussed this during color matching)

14


15

 Delta coding ‘work’ for everybody?

16

 Huffman wasn’t supposed to offer much compression
 Why did gzip compress the audio?

17

 Anybody design a better predictor?

18

 Fascinating idea:
 A reversible filter can:
 ‘decorrelate’ a signal
 Eliminates statistical dependencies
 Result can be entropy coded

19

 Premidterm
 Postmidterm
 Lossy
 But also:
 Frequency domain techniques

20

 Sampling and Quantization
 Coding
 Psychologically/Physiologically inspired detail removal

21

 We have covered this already:
 Quantization is data representation
 Converting an analog world into digital samples

22

 Sampling frequency
 Spatial resolution (images)
 Temporal resolution (sound)
 Quantization
 Range of values
 (record signal 0 to 96dB)
 (record brightness 0 to 100 candela)
 Resolution

23

 Somewhat cut and dry
 We basically know what we want to capture and capture it

24

 Spent 1^{st} ½ of class on this
 Information theory
 How to remove redundant information

25

 Coding really creates an optimal representation
 Consider Huffman encoding ASCII list of die rolls
 From 16 bits to 3 bits > 5.3:1 improvement

26

 We know the theoretical coding limits
 And how close to the limit we can achieve
 Room for improvement:
 Use of predictive filters
 However our techniques are very good
 Huffman coding: optimal for cases w/o intrasymbol coherence
 Turbo codecs: remarkably close to Shannon limit

27

 Understanding JND: just noticeable differences to discard undetectable
detail
 Lossy techniques
 Tremendous opportunities

28

 ΔI/I = k
 For many phenomena the ratio of detectable intensity I constant
 k, called the weber constant
 Only true for ‘prothetic’ sensations
 Relating to increase in intensity
 Not ‘metathetic’ sensations relating to change in quality ie pitch of
sound
 E. H. Weber experimented on thresholds of perception of lifted weights

29

 For instance could refer to point correctly detected on 75% of trials

30

 Abstracts
 2 essential aspects of decision making
 Into a statistical model
 Enables valid conclusions from data

31

 Stimulus occurs
 Processing is conducted by the subject
 Subject decides if experienced a sensation

32


33

 Test range
 Sound preceded strike by up to 2ms
 Sound follows strike by up to 2ms
 Subjects questioned
 Data
 Random responses across range
 What is going on?

34

 Obviously tested range was insufficient
 Fails thought experiment:
 Hitting glass at arms length
 So 2ms is obviously not long enough:
 Assume 2 foot arm
 Sound travels roughly 1ms per foot

35

 Should have varied timing until
 Subject achieved 75% correct judgment
 Signal Detection theory helps explain this value

36

 Study of mapping between stimulus and sensation
 Stimulus threshold value
 Level of intensity or duration of a stimulus
 Below which a human cannot sense
 Example
 Sound/Touch precedence undetectable at 2ms

37

 Present subject a series of stimuli
 Varying above/below estimated threshold
 Count number of “yes” responses
 Define threshold at value receiving 75% correct “yes” responses
 Any problem with this proposal?

38

 Fails to consider effect of nonsensory variables on the human decision
to say “yes”
 This method assumes that the stimulus completely determines the
probability of a “yes” response
 Example: (eye test)
 If task is to determine a blinking light
 Subject is biases toward saying “yes”

39

 Does not include the possibility that any part of the experiment has
some uncertainty

40

 Model of detection includes
 Monolithic threshold
 Replaced with statistical model

41

 To win:
 Be vigilant
 Any twig snapping could spell danger!

42

 Noise and bias added to detection:

43

 Important addition to model
 Obvious:
 Detection impossible in tremendous noise
 Noise found in both:
 Environment
 i.e. rustling leaves in paintball field
 Sensory system

44

 Can model noise as a Gaussian probability distribution ‘blob’:

45

 Y axis probability of a given X axis value:
 Pressure, temperature, etc.
 Peak of curve indicates:
 Which X value is most likely
 For a symmetric blob

46

 Spread of blob
 Indicates the likely range of X values
 (if we took successive measurements)
 Loosely: the variance

47

 Gaussian noise distributions with increasing variance from left to
right:

48

 Leftmost blob is the least noisy
 Very narrow range of expected values
 Rightmost blob is the most noisy
 Very broad range of expected values

49

 Model combines
 External (environment)
 Internal (sensory system) noise
 Represents result by a single blob
 Blobs are normalized to an area of 1.0
 Equates areas with probabilities

50

 Can also be represented as statistical blob
 Internal/external signal noise in same blob
 Revealing to:
 Plot signal and noise on the same axes
 View Signal + Noise blob as
 Copy of the Noise blob shifted by intensity of the signal

51


52

 If signal is weak compared to background noise
 (Paintball forest)
 The signal can be partially masked by a noise source

53

 The weaker the signal
 (perhaps a distant twig snap)
 The more the signal is masked by noise
 Correspondingly it more difficult to discern
 Intersection between the Noise and Signal + Noise curves represents the
amount of uncertainty.
 A stimulus in the intersection range could be:
 Just Noise
 Or Signal (we desperately want to detect)

54

 Uncertainty where signal, noise overlap

55

 When signal and noise blobs are
far apart
 Near 100% certainty is possible
 As the signal decreases in intensity
 (blobs eventually overlap)
 chance for detecting event decreases to 50%
 Pure chance
 Same result one would achieve from guessing.

56

 The following sequence of blobs shows a sequence of progressively weaker
signals:

57

 Bias is present in any decision
 Inherent in the signal detector
 Us
 Even a machine/algorithm
 We are told that bias is bad
 It is unavoidable
 Not inherently bad

58

 When signal and noise blobs are
far apart
 Near 100% certainty is possible
 As the signal decreases in intensity
 (blobs eventually overlap)
 chance for detecting event decreases to 50%
 Pure chance
 Same result one would achieve from guessing.

59

 The following sequence of blobs shows a sequence of progressively weaker
signals:

60

 Bias is present in any decision
 Inherent in the signal detector
 Us
 Even a machine/algorithm
 We are told that bias is bad
 Not inherently bad
 It is unavoidable

61


62

 In paintball
 Price of inaction outweighs price of action
 Four outcomes:

63

 Given this cost/benefit analysis
 Paintball warrior subconsciously biased to:
 Favor false positive
 Over false negative

64

 Bias may be represented on our graph:
 Stimuli right of bar are considered detected

65

 Shaded regions depict probabilities
 Wrong in article! (articles are preedits)

66

 Every situation has different
 Signal strength
 Noise level
 Appropriate Detector Bias
 Based on benefits/costs of
 False positive
 False negative
 Correct detection
 Correct rejection

67


68

 ROC:
 Receiver
 Operating
 Characteristic
 Curve
 Secret WWII RADAR program

69


70

 Each point on the curve
 Represents a different bias threshold
 For given noise, noise+signal blobs

71

 (shading wrong in preprint)

72

 For a given Noise and Signal + Noise pair
 The ROC is the curve traced out
 from (x,y) = (0,0) to (1,1)
 as decision threshold is swept
 from positive infinity to negative infinity

73

 xcoordinate
 is the area of the Noise blob
 ycoordinate is the area of the Signal + Noise blob to the right of the
threshold

74

 Interesting ROC points:
 Pascal’s Wager
 Paintball Warrior
 Walk in the park

75

 Blobs are normalized
 have an area of 1.0
 equivalent to probabilities
 Probability of False Positive is
 1.0  probability of Correct Reject
 Probability of Correct Detect is
 1.0  probability of False Reject
 Consequently: Each point on the ROC curve
 Encodes all signal and threshold info

76


77

 For a given Signal and Noise
 the area under the corresponding ROC curve
 defines the performance of a subject
 in a signal detection task
 independent of any particular bias
 By taking the area under the curve we factor out the influence of bias!

78

 Area under curve
 Chance of correct detection

79

 Signal is devoid of noise

80

 Extreme plots aren’t interesting
 Pure chance
 Perfect performance

81

 Can’t ask a human to change bias
 Would confuse them w/o extensive training
 (interestingly can set a machine’s threshold)
 So with human subjects
 Can only change the strength of the signal

82

 Original experiment A
 Signal strength (time magnitude) too low

83

 Discrete change
 Continuous change

84

 Smallest object/highest frequency
 (minutes of retinal arc subtended)
 Dimmest object
 Smallest movement
 Smallest displacement

85

 Smallest timing difference
 Fusion frequency

86

 Smallest intensity difference
 Smallest hue difference
 Highest frequency seen in shadow

87

 Smallest intensity difference
 Smallest frequency difference
 Smallest timing difference
 Audio masking
 (sounds undetectable in presence of related sound)
 Largest jitter undetectable
 Largest error undetectable

88

 Smallest pressure
 Smallest pressure change (weight)
 Smallest temperature change

89

 Smallest concentration of chemical
 Smallest change in concentration

90

 Largest distortion undetectable
 Microsoft Talisman affine transform instead of rerender
