1 of 123

Nima Kalantari

CSCE 448/748 – Computational Photography

Sampling, Frequency, and Filtering

Many slides from Alexei A. Efros, James Hayes, Rob Fergus

2 of 123

Outline

Sampling and aliasing
Frequency domain
Smoothing filters
Antialiasing
Other filters

3 of 123

Image formation involves sampling

4 of 123

Image formation involves sampling

Scene

Digital image

5 of 123

Aliasing in images (Moire pattern)

Original

Aliased

Credit: Scientific Volume Imaging

6 of 123

Aliasing in video (wagon-wheel effect)

Created by Jesse Mason, https://www.youtube.com/watch?v=QOwzkND_ooU

7 of 123

Aliasing in video (wagon wheel effect)

Slide by Steve Seitz

8 of 123

Aliasing in video (wagon wheel effect)

9 of 123

Sampling Artifacts in Computer Graphics

Artifacts due to sampling - “Aliasing”

Jaggies – sampling in space
Moire – undersampling images (and textures)
Wagon wheel effect – sampling in time
[Many more] …

Aliasing

Fast-changing signals (high frequency) sampled too slowly

10 of 123

Antialiasing

11 of 123

Video: Point vs Antialiased Sampling

Point in Time

Motion Blurred

12 of 123

Video: Point Sampling in Time

30 fps video. 1/800 second exposure is sharp in time, causes time aliasing.

Credit: Aris & cams youtube, https://youtu.be/NoWwxTktoFs

13 of 123

Imaging: sampling in space

Note jagged edges of the flower petals

Sample

14 of 123

Imaging: antialiased sampling

Pre-Filter

Sample

Note antialiased edges

15 of 123

Aliasing and Antialiasing

Why undersampling results in aliasing?
Why pre-filtering reduces aliasing?

16 of 123

Outline

Sampling and aliasing
Frequency domain
Smoothing filters
Antialiasing
Other filters

17 of 123

Image representation with basis functions

18 of 123

Spatial basis (1D example)

Signal

Basis

1

2

3

1

2

3

4

1

2

3

1

2

3

4

1

2

3

1

2

3

4

1

2

3

1

2

3

4

B₁

B₂

B₃

F

F = 4 B₁ + 1 B₂ + 2 B₃

19 of 123

Spatial basis

In 2D, the basis functions will be 2 dimensional
Each basis will have a value of 1 at each pixel
The image can be described as a weighted combination of the basis functions

20 of 123

Frequency domain

Representing a signal using frequency basis functions
The signal is represented as a weighted combination of a series of basis functions at different frequencies

21 of 123

Sines and Cosines

22 of 123

Frequencies

23 of 123

Fourier Transform

Represent a function as a weighted sum

of sines and cosines

Joseph Fourier 1768 - 1830

f(target) = A₀f₀+ A₁f₁ + A₂f₂ + …

24 of 123

Extension to 2D

Image as a sum of basis images

=

25 of 123

Constant

Frequency Domain

(0,0)

Spatial Domain

26 of 123

— frequency 1/32; 32 pixels per cycle

Max signal freq =1/32

(0,0)

Frequency Domain

Spatial Domain

27 of 123

— frequency 1/16; 16 pixels per cycle

Max signal freq =1/16

(0,0)

Frequency Domain

Spatial Domain

28 of 123

Frequency Domain

Spatial Domain

29 of 123

2D Frequency Space

Note: Frequency domain also known as frequency space, Fourier domain, spectrum, …

Frequency Domain

Spatial Domain

30 of 123

Sampling

Simple example: a sine wave

31 of 123

Undersampling

What if we “missed” things between the samples?
Simple example: undersampling a sine wave

Unsurprising result: information is lost

32 of 123

Undersampling

What if we “missed” things between the samples?
Simple example: undersampling a sine wave

Unsurprising result: information is lost
Surprising result: indistinguishable from lower frequency
Aliasing: high frequencies traveling in disguise as low frequencies

33 of 123

Aliasing in images

Original

Aliased

Credit: Scientific Volume Imaging

34 of 123

Moiré Patterns in Imaging

lystit.com

Read every sensor pixel

Skip odd rows and columns

35 of 123

Higher Frequencies Need Faster Sampling

x

f₁(x)

f₂(x)

f₃(x)

f₄(x)

f₅(x)

f₂(x)

f₁(x)

f₃(x)

f₄(x)

f₅(x)

Periodic sampling locations

Low-frequency signal: sampled adequately for reasonable reconstruction

High-frequency signal is insufficiently sampled: reconstruction incorrectly appears to be from a low frequency signal

36 of 123

Nyquist Theorem

Sampling rate should be equal to or greater than twice the highest frequency in the analog signal

Signal Interval

Maximum Acceptable

Sampling Interval

37 of 123

Nyquist Theorem

Sampling rate should be equal to or greater than twice the highest frequency in the analog signal

38 of 123

Nyquist Theorem

Sampling rate should be equal to or greater than twice the highest frequency in the analog signal

39 of 123

Nyquist Theorem

Sampling rate should be equal to or greater than twice the highest frequency in the analog signal

40 of 123

Antialiasing

Fast-changing signals sampled too slowly
What can we do about aliasing?

Sample more often

Join the Megapixel craze of the photo industry
Only shifts the problem to higher frequencies

Make the signal less “wiggly” (filtering)

Get rid of some high frequencies
Will lose information
But it’s better than aliasing

41 of 123

Outline

Sampling and aliasing
Frequency domain
Smoothing filters
Antialiasing
Other filters

42 of 123

Moving Average

Basic idea: define a new function by averaging over a sliding window

43 of 123

Weighted Moving Average

Can add weights to our moving average
Weights [1, 1, 1, 1, 1] / 5

/5

44 of 123

Weighted Moving Average

Bell curve (gaussian-like) weights [1, 4, 6, 4, 1]/16

/5

/16

45 of 123

Weighted Moving Average In 2D

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

Slide by Steve Seitz

46 of 123

Cross-correlation

Let be the image, be the kernel (of size 2k+1 x 2k+1), and be the output image

H is called “filter”, “kernel”, or “mask”
This is called a cross-correlation operation:

47 of 123

Moving Average In 2D

What are the weights H?

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

Slide by Steve Seitz

48 of 123

Image filtering

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0


	0

Credit: S. Seitz

1

49 of 123

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0


	0	10

Image filtering

1

Credit: S. Seitz

50 of 123

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0


0	10	20

Image filtering

1

Credit: S. Seitz

51 of 123

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0


0	10	20	30

Image filtering

1

Credit: S. Seitz

52 of 123

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0


0	10	20	30	30

Image filtering

1

Credit: S. Seitz

53 of 123

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0


0	10	20	30	30




			50

Image filtering

1

Credit: S. Seitz

54 of 123

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0


0	10	20	30	30


					90

			50

Image filtering

1

Credit: S. Seitz

55 of 123


0	10	20	30	30	30	20	10
0	20	40	60	60	60	40	20
0	30	60	90	90	90	60	30
0	30	50	80	80	90	60	30
0	30	50	80	80	90	60	30
0	20	30	50	50	60	40	20
10	20	30	30	30	30	20	10
10	10	10	0	0	0	0	0

Image filtering

1

Credit: S. Seitz

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

56 of 123

Box filter

What does it do?

Replaces each pixel with an average of its neighborhood
Achieve smoothing effect (remove sharp features)

1

Slide credit: David Lowe (UBC)

57 of 123

Cross-correlation vs. Convolution

Cross-correlation:

Convolution = cross-correlation with a horizontally and vertically flipped filter

Slide by Steve Seitz

58 of 123

Convolution

Adapted from F. Durand

59 of 123

Convolution is nice!

Convolution is a multiplication-like operation

Commutative
Associative
Distributes over addition
Scalars factor out
Identity: unit impulse e = […, 0, 0, 1, 0, 0, …]

Conceptually no distinction between filter and signal

60 of 123

Convolution is nice!

Usefulness of associativity

often apply several filters one after another

(((a * b₁) * b₂) * b₃) = a * (b₁ * b₂ * b₃)

61 of 123

Gaussian filtering

A Gaussian kernel gives less weight to pixels further from the center of the window

1	2	1
2	4	2
1	2	1

Slide by Steve Seitz

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

62 of 123

Gaussian filter

This kernel is an approximation of a Gaussian function:

0.003 0.013 0.022 0.013 0.003

0.013 0.059 0.097 0.059 0.013

0.022 0.097 0.159 0.097 0.022

0.013 0.059 0.097 0.059 0.013

0.003 0.013 0.022 0.013 0.003

5 x 5, σ = 1

Slide credit: Christopher Rasmussen

63 of 123

Gaussian Kernel

Standard deviation σ: determines extent of smoothing

Source: K. Grauman

σ = 2 with 30 x 30 kernel

σ = 5 with 30 x 30 kernel

64 of 123

Gaussian filters

= 30 pixels

= 1 pixel

= 5 pixels

= 10 pixels

65 of 123

Choosing kernel width

The Gaussian function has infinite support, but discrete filters use finite kernels

Source: K. Grauman

66 of 123

Practical matters

How big should the filter be?
Values at edges should be near zero
Rule of thumb for Gaussian: set filter half-width to about 3 σ

Side by Derek Hoiem

67 of 123

Gaussian and convolution

Removes “high-frequency” components from the image (low-pass filter)
Convolution with self is another Gaussian

Convolving twice with Gaussian kernel of std. is equal to convolving once with kernel of std.

Source: K. Grauman

*

=

68 of 123

Box vs. Gaussian filtering

Slide by Steve Seitz

69 of 123

Filtering in Frequency Domain

70 of 123

Visualizing Image Frequency Content

Spatial Domain

Frequency Domain

71 of 123

Filtering in the Frequency Domain

Spatial Domain

Frequency Domain

Fourier

Process

Inverse

Fourier

Spatial Domain

Frequency Domain

72 of 123

Filter Out Low Frequencies Only (Edges)

Spatial Domain

Frequency Domain

73 of 123

Filter Out High Frequencies (Blur)

Spatial Domain

Frequency Domain

74 of 123

Filter Out Low and High Frequencies

Spatial Domain

Frequency Domain

75 of 123

Filter Out Low and High Frequencies

Spatial Domain

Frequency Domain

76 of 123

Relationship between the two

77 of 123

The Convolution Theorem

The Fourier transform of the convolution of two functions is the product of their Fourier transforms

Convolution in spatial domain is equivalent to multiplication in frequency domain!

78 of 123

2D convolution theorem example

*

f(x,y)

h(x,y)

g(x,y)

|F(s_x,s_y)|

|H(s_x,s_y)|

|G(s_x,s_y)|

79 of 123

Box vs. Gaussian filtering

Why does the Gaussian give a nice smooth image, but the square filter give edgy artifacts?

Gaussian

Box filter

80 of 123

Gaussian filter

Spatial Domain

Frequency Domain

81 of 123

Box filter

Spatial Domain

Frequency Domain

82 of 123

Outline

Sampling and aliasing
Frequency domain
Smoothing filters
Antialiasing
Other filters

83 of 123

Image formation involves sampling

84 of 123

Antialiasing

Option 1

Filter the scene
Sample the filtered scene at each pixel

Option 2

Average the scene under each pixel

85 of 123

Digital sensors

Fill factor: ratio of light sensitive area to total pixel area

Pixel area

Light sensitive area

small to large fill factor

86 of 123

Fill factor effect

4%

100%

87 of 123

Outline

Sampling and aliasing
Frequency domain
Smoothing filters
Antialiasing
Other filters

88 of 123

Linear filters: examples

Original

1

Blur

(with a mean filter)

Source: D. Lowe

=

89 of 123

Practice with linear filters

0

1

0

Original

?

Source: D. Lowe

90 of 123

Practice with linear filters

0

1

0

Original

Filtered

(no change)

Source: D. Lowe

91 of 123

Practice with linear filters

0

1

0

Original

?

Source: D. Lowe

92 of 123

Practice with linear filters

0

1

0

Original

Shifted left

By 1 pixel

Source: D. Lowe

93 of 123

Linear filters: examples

Original

1

0

2

0

-

Sharpening filter (accentuates edges)

Source: D. Lowe

=

94 of 123

Filtering – sharpening

-

Image

Smoothed

=

Details

95 of 123

Filtering – Sharpening

+α

Image

Details

=

“Sharpened” α=1

96 of 123

Filtering – Sharpening

=

+α

Image

Details

“Sharpened” α=0

97 of 123

Filtering – Sharpening

=

+α

Image

Details

“Sharpened” α=2

98 of 123

Filtering – Sharpening

=

+α

Image

Details

“Sharpened” α=0

99 of 123

Filtering – Extreme Sharpening

=

+α

Image

Details

“Sharpened” α=10

100 of 123

Unsharp mask filter

Gaussian

unit impulse

Laplacian of Gaussian

image

blurred�image

unit impulse�(identity)

101 of 123

Edges

102 of 123

Edges are caused by a variety of factors

depth discontinuity

surface color discontinuity

illumination discontinuity

surface normal discontinuity

Origin of edges

Credit: Ali Farhadi

103 of 123

Characterizing edges

An edge is a place of rapid change in the image intensity function

image

intensity function�(along horizontal scanline)

first derivative

edges correspond to�extrema of derivative

Credit: Ali Farhadi

104 of 123

Partial derivatives with convolution

For 2D function f(x,y), the partial derivative is:

For discrete data, we can approximate using finite differences:

To implement above as convolution, what would be the associated filter?

Source: K. Grauman

-1 1

x

y

105 of 123

Partial derivatives of an image

Which shows changes with respect to x?

-1 1

106 of 123

Finite difference filters

Other approximations of derivative filters exist:

-1	0	1
-1	0	1
-1	0	1

1	1	1
0	0	0
-1	-1	-1

-1	0	1
-2	0	2
-1	0	1

1	2	1
0	0	0
-1	-2	-1

1	0
0	-1

0	1
-1	0

Prewitt

Sobel

Roberts

107 of 123

Image gradient

The gradient of an image:

Gradient points in the direction of most rapid increase in intensity

How does this direction relate to the direction of the edge?

The gradient direction is given by
The edge strength is given by the gradient magnitude��

Source: Steve Seitz

108 of 123

Image Gradient

109 of 123

Effects of noise

Consider a single row the image (shown below)
How can we find the edge?

Source: S. Seitz

110 of 123

Solution: smooth first

Look for peak in to find the edge

f

h

f * h

Source: S. Seitz

111 of 123

Noise in 2D

Noisy Input

dx via [-1,1]

Zoom

Source: D. Fouhey

112 of 123

Noise + Smoothing

Smoothed Input

dx via [-1,1]

Zoom

Source: D. Fouhey

113 of 123

Derivative theorem of convolution

This saves us one operation:

114 of 123

Derivative of Gaussian filter

* [1 -1] =

115 of 123

Derivative of Gaussian filter

Which one finds horizontal/vertical edges?

x-direction

y-direction

Vertical

Horizontal

116 of 123

Practical matters

What is the size of the output?
Python: convolve2d(f, g, shape)

shape = ‘full’: output size is sum of sizes of f and g
shape = ‘same’: output size is same as f
shape = ‘valid’: output size is difference of sizes of f and g

f

g

f

g

f

g

full

same

valid

Source: S. Lazebnik

117 of 123

Practical matters

What about near the edge?

the filter window falls off the edge of the image
need to extrapolate
methods:

clip filter (black)
wrap around
copy edge
reflect across edge

Source: S. Marschner

118 of 123

Summary

Smoothing filters

Gaussian: remove “high-frequency” components; “low-pass” filter
Can the values of a smoothing filter be negative?
What should the values sum to?

One: constant regions are not affected by the filter

Derivative filters

Derivatives of Gaussian
Can the values of a derivative filter be negative?
What should the values sum to?

Zero: no response in constant regions

119 of 123

A cool application

120 of 123

Hybrid images

121 of 123

Hybrid Images

Gaussian

unit impulse

Laplacian of Gaussian

A. Oliva, A. Torralba, P.G. Schyns, “Hybrid Images,” SIGGRAPH 2006

Gaussian

Laplacian

122 of 123

Da Vinci and Peripheral Vision

https://en.wikipedia.org/wiki/Speculations_about_Mona_Lisa#Smile

123 of 123

Da Vinci and Peripheral Vision

Leonardo playing with peripheral vision

Livingstone, Vision and Art: The Biology of Seeing

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0


0	10	20	30	30	30	20	10
0	20	40	60	60	60	40	20
0	30	60	90	90	90	60	30
0	30	50	80	80	90	60	30
0	30	50	80	80	90	60	30
0	20	30	50	50	60	40	20
10	20	30	30	30	30	20	10
10	10	10	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0


0	10	20	30	30	30	20	10
0	20	40	60	60	60	40	20
0	30	60	90	90	90	60	30
0	30	50	80	80	90	60	30
0	30	50	80	80	90	60	30
0	20	30	50	50	60	40	20
10	20	30	30	30	30	20	10
10	10	10	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0

0	0	0	0	0	0
0	0	0	0	0	0
0	90	90	90	90	90
0	90	90	90	90	90
0	90	90	90	90	90
0	90	0	90	90	90
0	90	90	90	90	90
0	0	0	0	0	0
90	0	0	0	0	0
0	0	0	0	0	0


0	10	20	30	30	30	20	10
0	20	40	60	60	60	40	20
0	30	60	90	90	90	60	30
0	30	50	80	80	90	60	30
0	30	50	80	80	90	60	30
0	20	30	50	50	60	40	20
10	20	30	30	30	30	20	10
10	10	10	0	0	0	0	0