Visual Coding
• What are the computational problems of visual coding?
• What signal should be sent out of the retina?
• How do we approach this theoretically?
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 1
After the retina...
• at least 23 distinct neural pathways out of the retina
• some receive from a single type of retinal cell, some from many, one eye, both...
• there is no simple function division
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 2
Why is it like this?
Evolutionary viewpoint:
• success depends on whole organism and cooperation of areas and cell types
• there is no opportunity to “redesign”, functions simply pile up
– “layers and layers of goo”
– “not engineering, but tinkering”
• there are few “clean” functional divisions, i.e. there are not distinct channels for
color or motion
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 3
Types of optical systems
• Suprachiasmatic nucleus: generate the circadian rythm
• Accessory optic system: helps stabilize retinal image during head movement
• Superior colliculus: integrates visual and auditory information together with
head movements, directs eyes to regions of interest
• Pretectum: plays role in adjusting size of pupil to changes in light intensity,
and in tracking large moving objects
• Pregeniculate: function unknown, but cells are responsive to ambient light level
• lateral geniculate: main “relay” to visual cortex; contains 6 distinct layers,
each with 2 sublayers. Organization is very complex and cells have a wide range
of sensitivities including contrast, color, and motion.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 4
Where is this headed?
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 5
A theoretical approach
• Look at the system from a function perspective:
What problems does it need to solve?
• abstract from the details, make predictions from theoretical principles
• You can only have data after you do your theory.
• Models are bottom-up, theories are top-down.
• What are the relevant principles?
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 6
Information theory: a short introduction
Entropy:
• measure of irreducible signal complexity
• lower bound on how much a signal can be compressed without loss
Information of symbol w:
I(w) ≡ − log2 P (w)
For a random variable X, with probability P (x), the entropy is the average amount
of information obtained by observing x:
X X
H(X) = P (x)I(x) = − P (x) log2 P (x)
x x
• H only depends on the probabilty, not value
• Gives lower bound on average bits per code word.
Average coding cost for a message of length L (assuming independence) is
LH(X)bits.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 7
Example
A single random variable X with X = 1 with probability p and X = 0 with
probability 1 − p. Note that H(p) is 1 bit when p = 1/2.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 8
Capacity
Capacity is the maximum amount of information per symbol:
C = log2 N
Maximum is when all N symbols have equal probability.
• English: C = log2 27 = 4.73 bits/letter
• Image: 8 × 256 × 256 for 8 bit 2562 image.
Actual entropy, i.e. the irreducible part, is much less.
Why?
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 9
Redundancy
Redundancy is a measure of (in)efficiency or actual entropy relative to capacity:
R = 1 − H(x)/C
Capacity is maximum when
• code words (symbols) have equal frequency
• no inter-symbol redundancy
Examples
• English: letter probs not equal, letters not indep.
• Images: pixel value probs not equal, pixels not indep.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 10
Example of symbols in english: A-Z and space
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 11
A fourth order approximation
Note that as the order is increased:
• entropy decreases: H0 = 4.76 bits, H1 = 4.03 bits, and H4 = 2.8 bits/char
• variables, i.e. P (ci|ci−1, ci−2, . . . , ci−k ), specify more specific structure
• generated samples look more like real English
This is an example of the relationship between efficient coding and representation
of signal structure.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 12
The same model can also be applied to words
Specifying higher-order word models is problemlatic because the number of
variables increases as N k , where N is the number of words (e.g. 50,000 in English)
and k is the order of the model.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 13
A general approach to coding: redundancy reduction
Correlation of adjacent pixels
1
0.8
0.6
0.4
0.2
0
0 0.2 0.4 0.6 0.8 1
Why reduce redundancy?
This is equivalent to efficient coding.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 14
Why code efficiently?
Information bottleneck:
• restriction on information flow rate
– channel capacity
– computational bottleneck
– 5 × 106 → 40 − 50 bits/sec
• need even probabilities for associative learning
– easy to calc joint probs for independent vars
• facilitate pattern recognition
– independent features are more informative
– better sensory codes could simply further processing
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 15
The bottleneck in vision
• Eyes must move ⇒ small, thin “cord”
• 100 million photoreceptors → 1 million optic nerve fibers
• Fovea already provides a great reduction in amount of information
• How do we reliably transmit the important visual information?
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 16
A little more information theory
• H(X) is a measure of how much information it takes on average to describe
random variable X.
• If we know p(X), we can calculate entropy or optimize the model for the data,
but what if we don’t know p(X) and can only approximate it, e.g. with q(X)?
• How many bits does this inaccuracy cost us?
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 17
Relative Entropy
• The relative entropy D(p||q) is a measure of the inefficiency of assuming
distribution q when the true distribution is p.
• If we knew p we could construct code with average code word length H(p).
• If we assume q, the best average code length we can achieve is H(p) + D(p||q)
X p(x)
D(p||q) = p(x) log
x
q(x)
• D(p||q) = 0 ⇐⇒ p = q
• This is also called the Kullback Leibler divergence
• It is not called a distance, becase it is not symmetric and does not satisfy the
triangle inequality.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 18
Information theoretic viewpoint
Use Shannon’s source coding theorm.
X 1
L = E[l(X)] ≥ p(x) log
x
q(x)
X p(x) X 1
= p(x) log + p(x) log
x
q(x) x
p(x)
= DKL(pkq) + H(p)
DKL is the Kullback-Leibler divergence.
If model density q(x) equals true density p(x) then DKL = 0.
⇒ q(x) gives lower bound on average code length.
greater coding efficiency ⇔ more learned structure
Principle
Good codes capture the statistical distribution of sensory patterns.
How do we descibe the distribution?
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 19
Contrast response function in the fly eye (Laughlin, 1981)
• fly LMC (large monopolar cells) – interneuron in compound eye
• output is graded potential
How to set sensitivity?
• too high ⇒ response saturated
• too low ⇒ range under utilized
Idea: predict contrast reponse function using information theory.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 20
Maximizing information transfer with limited channel capacity
• inputs follow given distribution
• transform so that output levels are
used with equal frequency
• each response state has equal area
(⇒ equal probability)
• continuum limit is cumulative pdf
of input distribution
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 21
Another example with different statistics
Mathematical form is as cumulative
probability. For y = g(c)
Z c
y
= P (c0)dc0
ymax cmin
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 22
Testing the theory
Laughlin 1981:
• collect natural scenes to get
stimulus pdf
• 15,000 readings
• use linear scans: 10, 25, or 50◦
• calc contrast within each scan:
∆I/hIi
• measure actual response of LMC
to varying contrasts
⇒ fly LMC transmits information
efficiently
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 23
Coding a natural intensity time series
van Hateren and Snippe (2001)
• recorded with a photometer, walking around outdoors
• dynamic range of intensity is much larger than that of photoreceptors
• large changes can occur on short time-scale
• Most, if not all, species can quickly adjust their gain to changing light levels.
Questions:
• How should the signal be transformed?
• What gain control model should be used?
• How should the optimality the system (the fly in this case) be evaluated?
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 24
An evaluation method for non-linear encoding models
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 25
Measuring the capacity of the system
The noise is given by: N = S − Sest .
The signal to noise ratio is
hSest Sest ∗i
SNR =
hN N ∗i
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 26
A linear model
• prediction of neural response of linear model is poor
• For linear model, coherence is sub-optimal at all frequencies.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 27
Gain model with a static non-linearity: log
Coherence at low frequencies is improved, but coding is not perfect.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 28
Gain model with a static non-linearity: sqrt
sqrt is slightly worse than log.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 29
Gain model with a Dynamic non-linearity
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 30
Gain model with a Dynamic non-linearity
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 31
Gain model with a Dynamic non-linearity
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 32
Best model requires several stages
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 33
Coherence rates of the different models
Upper bound on capacity of fly
photoreceptor is measured by estimating
the variability in the response to the
same stimulus.
á
á á
á
CP08: Visual Coding 1 / Michael S. Lewicki, CMU ? 34