EECE253 07 Convolution

EECE\CS 253 Image Processing
Lecture Notes: Spatial Convolution Lecture Notes
Richard Alan Peters II

Department of Electrical Engineering and Computer Science
Fall Semester 2011
This work is licensed under the Creative Commons Attribution-Noncommercial 2.5 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc/2.5/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
Spatial Filtering
Let I and J be images such that J = T[I]. T[] represents a transformation, such that,
J (r , c) = T [ I ](r , c) = f ({ I (r, c) r {r - s,..., r ,...r + s} , c {c - d ,..., c,...c + d } }).
That is, the value of the transformed image, J, at pixel location (r,c) is a function of the values of the original image, I, in a 2s +1 2d +1 rectangular neighborhood centered on pixel location (r,c).
2011-09-29 1999-2011 by Richard Alan Peters II 2
Moving Windows
The value, J(r,c) = T[I](r,c), is a function of a rectangular neighborhood centered on pixel location (r,c) in I. There is a different neighborhood for each pixel location, but if the dimensions of the neighborhood are the same for each location, then transform T is sometimes called a moving window transform.
1999-2011 by Richard Alan Peters II 3
2011-09-29
Moving-Window Transformations
Neutral Buoyancy Facility at NASA Johnson Space Center
Well take a section of this image to demonstrate the MWT
photo: R.A.Peters II, 1999
2011-09-29
1999-2011 by Richard Alan Peters II
operate on this region
2011-09-29
Pixelize the section to better see the effects.
apply a pixel grid
2011-09-29
Pixelize the section to better see the effects.
sample (average in the squares).

lets get some perspective on this

a neighborhood defined by a weight matrix

neighborhoods at other pixel locations

Linear Moving-Window Transformations

( i.e. convolution)
The output of the transform at each pixel is the (weighted) average of the pixels in the neighborhood.
2011-09-29
11
result of a 9 x 9 uniform averaging
2011-09-29
12
Convolution: Mathematical Representation

If a MW transformation is linear then it is a convolution:

J (r , c) = [ I * h ] (r , c) =
- -
I(r - r, c - c)h(r, c) dr d c ,
for a real image (I:), or for a digital image (I:): J (r , c) = [ I * h ] (r , c) =
r =- s c=- d
B ( r - r , c - c) h (r , c)
13
2011-09-29
Convolution Mask (Weight Matrix)

The object, h(,), in the equation is a weighting function, or in the discrete case, a rectangular matrix of numbers. The matrix is the moving window. Pixel (r,c) in the output image is the weighted sum of pixels from the original image in the neighborhood of (r,c) traced by the matrix. Each pixel in the neighborhood of (r,c) is multiplied by the corresponding matrix value after the matrix is rotated by 180. (See slide 22). The sum of those products is the value of pixel (r,c) in the output image
Convolution Masks: Moving Window
mask origin
rotate 180
translate to pixel loc (r,c)

2011-09-29 1999-2011 by Richard Alan Peters II
around pixel loc (r,c)

15
Convolution Masks: Moving Window

multiplies pixel I(r-1,c-2) multiplies pixel I(r-1,c)
multiplies pixel I(r,c-1)
multiplies pixel I(r+1,c+1)

16
2011-09-29
Convolution by Moving Window

f i g
a b c d e f g h i
2011-09-29
17
Another example
Moving Window Transform: Example
original
3x3 average
18
original
3x3 average
19
original
3x3 average
20
original
3x3 average
21
original
3x3 average
22
original
3x3 average
23
original
3x3 average
24
Convolution by Rotating and Shifting the Weight Matrix

Shifted weight matrix Result of sum of products
At the locations not shown, the results were zeros.
Location of impulse
Accumulated nonzero results
The original image has a black impulse at the center and zeros (white) elsewhere.
The weight matrix has a gray L at its left and zeros (white) elsewhere.
The resulting image has a copy of the weight matrix pegged to the impulse location.
2011-09-29
14
25
Symmetric Weight Matrix
A symmetric weight matrix is unchanged by rotation through 180.
2011-09-29
26
Three ways to compute a convolution

1. Moving window transform as just shown. 2. Shift multiply add. 3. Fourier transform.
1.
2.
3.
2011-09-29
27
Shift-Multiply-Add Approach
The image is copied 1 time for each element in the convolution mask. Each copy is shifted relative to the original by the displacement of its associated mask element. Each copy is multiplied by the value of its associated mask element. The set of shifted and multiplied images is summed pixel wise.
2011-09-29
28
Convolution by an Impulse
An impulse is a digital image, that has a single pixel with value 1; all others have value zero. An impulse at location (, ) is represented by:
d ( r - r , c - c) =
1, if r = r and c = c 0, otherwise
If an image is convolved with an impulse of weight w at location (, ), then the image is multiplied by w and shifted in location down by pixels and to the right by pixels.
[I * wd (r - r, c - c)] (r , c) = wI (r - r, c - c).
Convolution by an Impulse
(r 16, c 16)
Shifted down and to the right by 16 pixels.

Convolution by Two Impulses
1 2
d (r - 0, c - 0)
1 2
d (r -16, c -16)
Two copies, one moved, one not moved, averaged.

Convolution by Three Impulses

1 3
d (r + 16, c + 16)
1 3
d (r - 0, c - 0)
1 3
d (r -16, c -16)
Three copies, two moved, Weights 1/3 one not moved, = averaged.
Convolution by Five Impulses

1 5
d (r + 16, c + 16)
1 5
d (r + 16, c -16)
1 5
d (r - 0, c - 0)
1 5
d (r -16, c + 16)
1 5
d (r -16, c -16)
Five copies, four moved, one not moved, averaged.

Moved adjacent to each other, the convolution becomes a blurring filter.
2011-09-29
34
The impulses become values in a 3x3 neighborhood.
2011-09-29
35
The convolution mask has five elements at 1/5 and four at 0.
2011-09-29
36
Convolution by Copying, Multiplying, and Shifting the Image

For each element h(rh,ch) in weight matrix, h, image I is copied into a zero-padded image, P, starting at (rh,ch). Each P is multiplied by the corresponding weight, h(rh,ch). All the P images are summed pixel-wise then divided by the sum of the elements of h. The result is cropped out of the center of the accumulated Ps. original image, I padded image, P effective neighborhood weight matrix aligned pixels to be summed weight for image
2011-09-29
37

The original image has a black impulse at the center and zeros (white) elsewhere.
The weight matrix has a gray L at its left and zeros (white) elsewhere.
The resulting image has a copy of the weight matrix pegged to the impulse location.
original image, I effective neighborhood padded image, P

2011-09-29
In the result, the origin of the weight matrix coincides with the original location of the impulse.
38

The position of the black square relative the center of the weight matrix indicates the shift of the original image relative to the middle of the padded image.
Each copy of the (entire) image is multiplied by the value of the weight matrix in black square (here, white = 0) before being accumulated (pixelwise) in the padded image
In this image, only the pixel in the center is nonzero so only it shows a result when the image is multiplied by a nonzero value
2011-09-29
39

The position of the black square relative the center of the weight matrix indicates the shift of the original image relative to the middle of the padded image.
Each copy of the (entire) image is multiplied by the value of the weight matrix in black square (here, white = 0) before being accumulated (pixelwise) in the padded image
In this image, only the pixel in the center is nonzero so only it shows a result when the image is multiplied by a nonzero value
2011-09-29
40
Zero Padding an Image for Convolution: Variable Names.
weight matrix, h
cpad
n m
rpad
R
cpad = rpad = hcorig hrorig floor( floor( = cpad = rpad n m + + /2) /2) 1 1
Image, I
2011-09-29
41
Convolution by Copying and Shifting the Image

To use the image shift-multiplyaccumulate algorithm, create an accumulator image, A, that is R+m-1 rows by C+n-1 columns
Image I is RxC
C+n-1
A
R+m-1
R n
2011-09-29
42

13x13 image convolved by 6x6 mask. Image is constant; mask has only 6 nonzero values all on the diagonal. Image is shifted to mask location, multiplied by value, and accumulated.
accumulator output image
conv. mask
Convolution by Copying and Shifting the Image
hcorig hrorig
hcorig+C-1
output image, J
When done, copy the output image from the accumulator starting at (hrorig, hcorig) and ending at (hrorig+R-1, hcorig+C-1)
2011-09-29
hrorig+R-1
C
44
Convolution Examples: Original Images
2011-09-29
45
111 1 111 9 111
Convolution Examples: 33 Blur
2011-09-29
46
11111 11111 1 11111 25 1 1 1 1 1 11111
2011-09-29
47
111111111 111111111 111111111 111111111 1 111111111 81 1 1 1 1 1 1 1 1 1 111111111 111111111 111111111
2011-09-29
48
11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 1 11111111111111111 289 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111
2011-09-29
49
Vertical Edge Detection

255
Image
r0
0 -255
Backward Difference
r0
Forward Difference
r0
Sum of Differences
r0
c
50
2011-09-29
Symmetric Edge Detection
510 255 0 -255
-1 2 -1
-1 2 -1
-1 -1 4 -1 -1
2011-09-29
51
2011-09-29
52
1 2 1
Convolution Examples: Vertical Difference
2011-09-29
53
[1
2 1]
Convolution Examples: Horizontal Difference
2011-09-29
54
0 1 0 1 4 1 0 1 0
Convolution Examples: H + V Diff.
2011-09-29
55
1 0 0 0 2 0 0 0 1
Convolution Examples: Diagonal Difference
2011-09-29
56
0 0 1 0 2 0 1 0 0
Convolution Examples: Diagonal Difference
2011-09-29
57
1 0 1 0 4 0 1 0 1
Convolution Examples: D + D Difference
2011-09-29
58
1 1 1 1 8 1 1 1 1
Convolution Examples: H + V + D Diff.
2011-09-29
59
2011-09-29
60

EECE253 07 Convolution

Uploaded by

Copyright:

Available Formats

EECE253 07 Convolution

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

EECE253 07 Convolution

Uploaded by

Copyright:

Available Formats

EECE\CS 253 Image Processing

Lecture Notes: Spatial Convolution Lecture Notes

Richard Alan Peters II

Neutral Buoyancy Facility at NASA Johnson Space Center

Well take a section of this image to demonstrate the MWT

photo: R.A.Peters II, 1999

1999-2011 by Richard Alan Peters II

operate on this region

1999-2011 by Richard Alan Peters II

Pixelize the section to better see the effects.

apply a pixel grid

1999-2011 by Richard Alan Peters II

Pixelize the section to better see the effects.

sample (average in the squares).

lets get some perspective on this

a neighborhood defined by a weight matrix

neighborhoods at other pixel locations

Linear Moving-Window Transformations

1999-2011 by Richard Alan Peters II

result of a 9 x 9 uniform averaging

1999-2011 by Richard Alan Peters II

Convolution: Mathematical Representation

for a real image (I:), or for a digital image (I:): J (r , c) = [ I * h ] (r , c) =

1999-2011 by Richard Alan Peters II

Convolution Mask (Weight Matrix)

Convolution Masks: Moving Window

translate to pixel loc (r,c)

around pixel loc (r,c)

Convolution Masks: Moving Window

multiplies pixel I(r,c-1)

multiplies pixel I(r+1,c+1)

1999-2011 by Richard Alan Peters II

Convolution by Moving Window

1999-2011 by Richard Alan Peters II

Moving Window Transform: Example

Moving Window Transform: Example

Moving Window Transform: Example

Moving Window Transform: Example

Moving Window Transform: Example

Moving Window Transform: Example

Moving Window Transform: Example

Convolution by Rotating and Shifting the Weight Matrix

Accumulated nonzero results

1999-2011 by Richard Alan Peters II

Symmetric Weight Matrix

A symmetric weight matrix is unchanged by rotation through 180.

1999-2011 by Richard Alan Peters II

Three ways to compute a convolution

1999-2011 by Richard Alan Peters II

1999-2011 by Richard Alan Peters II

Shifted down and to the right by 16 pixels.

Convolution by Two Impulses

Two copies, one moved, one not moved, averaged.

Convolution by Three Impulses

Convolution by Five Impulses

Five copies, four moved, one not moved, averaged.

Convolution by Five Impulses

Moved adjacent to each other, the convolution becomes a blurring filter.

1999-2011 by Richard Alan Peters II

Convolution by Five Impulses