Image Processing

Image Processing

How do we represent pictures?

As a set of measurements in the plane

Signal processing: 1D version (easier)

Sampling

Discrete set of samples – continuous underlying phenomena

Try to understand what the problems are

Sample at discrete points (point sample)

Note that we can miss a small object

Note that we can’t localize an edge

Is the little square better?

Don’t know where small object is (or how small)

If it’s on an edge, gets way to blown up

Average over region? – where this is going

Basic idea:

If something is too small – or changes too fast, can’t capture it

How small an object? Depends on how well we sample

If we allow objects that are too small – many inputs to same representation

Aliasing – many inputs map to same output

What to do about it?

Limit small objects

Blur (Filter) – to get rid of sharp edges (quick changes, small things)

Why Care?

Miss small details

Downsample Checkerboard

All black/all white

Get weird patterns

Jaggies

Where line crosses through box

Where line is close enough to sample point

One pixel per column (or row – depends on quadrant)

Darkness issues

Crawlies

Make most effective use of what samples you have

Light Path Sampling

Sampling Basics

Three basic problems:

• 
  Sampling
  
• 
  Reconstruction
  
• 
  Re-Sampling (reconstruct + sampling)
  

Sampling: how many samples do you need?

Depends on how small an object (fast a change to capture)

Need to formalize this notion of small / fast

Reconstruction

What signal could have created these points

Many possibilities

Need to agree – need to know what to reconstruct

Smoothest signal: no extra wiggles

Can’t have a wiggle between samples

Limits the smallest wiggle allowed

Reconstruct: what signal interpolates, but has no wiggles smaller

Sample: if no wiggles, then samples are enough

What if signal has too many wiggles?

Need to get rid of extra wiggles BEFORE sampling

Example 1: Shader

http://research.cs.wisc.edu/graphics/Courses/559-f2008/Main/ShaderAntiAliasing

1. 
   Hard cutoff = jaggies
   
2. 
   Smooth step (get rid of wiggles) – too smooth = blurry
   
3. 
   Blur the right amount (about 1 pixel) = crisp, not jaggy
   

Example 2: Pre-Filtering

Checkerboard – get white/black

if you sample before filtering, you’re hosed

Once you’ve aliased – you’re stuck

Need to do averaging first

Could “blur” (average) beforehand

Could put averaging as part of the probe

Example 3: Reconstruction Filter

Start with a set of sample values (at discrete locations)

Want to know what signal was at other points

Various forms of interpolation:

Nearest neighbor (get piecewise constant)

Linear interpolation

Smoother

Kernel – multiply and sum

Box filter (too big, too small, just right) – averaging

Tent filter (too big, too small, just right) – lerp via weighted average

0 0 1 0 0 – could be “sharper” (not ideal)

Example 4: Downsample / Upsample

Take image

Divide in half (be sure to pre-filter!)

Double in size – will be blurrier

Some Theory

How do we talk about “wiggles”, “too fast”, “remove wiggles”

Fourier Transform:

Any signal can be made up of a series of sin waves of various frequencies

Modulo a few catches (might need phase / …)

Even a-periodic signals (but those get messy)

Idea:

Faster change, needs a faster sin wave (higher frequency)

Signals with fast changes: have high frequencies

Band-Limited Signal

Maximum frequency

Has a “fastest change” or smallest feature

Must sample fast enough to capture smallest feature

Nyquist frequency

Need > 2x samples

Filter –

Remove high frequencies

Multiply in frequency domain = convolution in time domain