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 11-sided die
- Higher entropy than 1 6-sided 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
|
- Pre-midterm
- Post-midterm
- 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 1st ½ 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 intra-symbol 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 non-sensory 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 pre-edits)
|
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 pre-print)
|
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
|
- x-coordinate
- is the area of the Noise blob
- y-coordinate 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 re-render
|