EECE/CS 253 Image Processing: Lecture Notes: Warping and Rotating Images

EECE\CS 253 Image Processing
Lecture Notes: Warping and Rotating Images 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.
Geometric Remapping
Input Image
Warping Function
Interpolation Function
Output Image
2011-11-07
1999-2011 by Richard Alan Peters II
Geometric Remapping
1. Assume the input image, I, has infinite spatial resolution. 2. Calculate the size, RoutCoutB, of the output image, J, and allocate it. 3. Create an image map (a warping function, ) as follows: a) Allocate an RoutCout2 array, . b) For every pixel location (r,c) in J find the corresponding real-valued pixel location (rf ,cf) in I. c) Set (r,c,1) = rf and set (r,c,2) = cf . 4. Create an interpolation function, , that generates a pixel value from the values of I on a neighborhood, N(rf ,cf). 5. Then set J(r,c) = {I; N(rf ,cf)}.
2011-11-07 1999-2011 by Richard Alan Peters II 3
Photo: JBUK_Planet, http://www.flickr.com/people/jbuk_planet/, Highclere Castle, Highclere Park, Newbury RG20 9RN, England, http://www.highclerecastle.co.uk/, August 26, 2007, Kodak DX6440
Original image with perspective distortion.

2011-11-07 1999-2011 by Richard Alan Peters II
Linear Warping of Images
Image warped to correct perspective distortion.


Select at least 4 key points that are easy to correct. (80, 326) (412, 34) E.g. in this case, the lines should be perfectly vertical. (872, 239)
(52, 632)
(403, 652) Selected correction points.
(913, 624)
2011-11-07

Here, align the top points with the bottom points. (52, 326) (403, 34) I.e. the top column coordinates == the bottom col. Cdts. (913, 239)
(52, 632)
(403, 652) Target correction points.
(913, 624)
2011-11-07

The top part of the (403, 34) image has been stretched more than the bottom (52, 326) Now the building corners are vertical. (913, 239)
(52, 632)
(403, 652)
(913, 624)
Result of linear LMS point remapping.


The top part of the image has been stretched more than the bottom Now the building corners are vertical.
Image warped to correct perspective distortion.

Linear Warping of Images How To Do It

Given a set, X, of points from image I and a set, Y, of target points find H such that
Y = HX
where
x1 x2 x p X = x1 x 2 x p = y y y 1 2 p u1 u2 u p Y = y1 y 2 y p = v v v 1 2 p
-1
and
h h H = 11 12 h21 h22
-1 cJ cJ cI is the warped H = then J (rJ , cJ ) = I H image. rJ rI rJ

2011-11-07
RAPII: see notes for this page!

10
Linear Warping of Images How To Do It

Given a set, X, of points from image I and Y= a set, Y, of target points find H such that There is a problem, however.
HX
where
X = x1 x 2 Y = y1 y 2
-1
This does not work very well. x1 x2 x p This is x p = a 2D linear transform. y y y 1need What we p 2 is a 3D affine h11 H = transform. A 3rd dimension and h 21 enables u us to model more geu u 1 2 p we use neral y p = projections. Thus v v v 1 2 p 3D homogeneous coordinates.
h12 h22
-1 cJ is the warped cJ cI H = then J (rJ , cJ ) = I H rJ rI rJ image.

Linear Warping of Images Homogeneous Cdts.

xi xi = yi 1
Place a 1 in the 3rd dimension of each input pixel location. H is 33. The remapped pixel locs are also 3D. Call each 3rd element ki and write the other two as proportional to ki.
y i = Hxi
ki ui y i = ki vi ki
2011-11-07
12
Linear Warping of Images Homogeneous Cdts.

x1 x2 x p X = y1 y2 y p 1 1 1
Input pixel locations in homogeneous form written as a 33 matrix.
Y = HX
H is 33.
Remapped pixel locations in homogeneous form written as a 33 matrix. Note that usually each ki is different.
k1u1 k2u2 Y = k1v1 k2 v2 k2 k1
k pu p k pvp k p
ki ui h11 h12 h13 xi k v = h h h y i i 21 22 23 i ki h31 h32 h33 1

2011-11-07
Here, for vectors xi and yi are the elements of the transform.
13
Linear Warping of Images Derivation

ki ui = h11 xi + h12 yi + h13 ki vi = h21 xi + h22 yi + h23 ki = h31 xi + h32 yi + h33
For each pixel location there are 3 equations in 3 unknowns. Divide the 1st and 2nd equations by the 3rd.
ui =
h11 xi + h12 yi + h13 h31 xi + h32 yi + h33
h11 xi + h12 yi + h13 ui = h31 xi + h32 yi + 1 vi = h21 xi + h22 yi + h23 h31 xi + h32 yi + 1
h21 xi + h22 yi + h23 vi = h31 xi + h32 yi + h33
Divide both numerator and denominator by h33. Then relabel the coefficients.
2011-11-07
14

(h31 xi + h32 yi + 1) ui = h11 xi + h12 yi + h13 (h31 xi + h32 yi + 1) vi = h21 xi + h22 yi + h23
-h11 xi- h12 yi- h13 + h31 xi ui + h32 yi ui + ui = 0 -h21 xi- h22 yi- h23 + h31 xi vi + h32 yi vi + vi = 0
-xi - yi -1 0 0 0 xi ui yi ui ui 0 0 0 - x - y -1 x v y v v h = 0 i i i i i i i
Multiply both sides by the rights denominator. Subtract the right side from both sides. Write as a matrix equation where
h = [ h11 h12 h13 h21 h22 h23 h31 h32 1] T

2011-11-07
the elements of matrix H are written as vector h.
15

-x1 - y1 -1 0 0 0 x1u1 0 0 0 -x1 - y1 -1 x1v1 -x2 - y2 -1 0 0 0 x2u2 0 0 -x2 - y2 -1 x2 v2 A= 0 0 0 0 x pu p -x p - y p -1 0 0 -x p - y p -1 x p v p 0
Solve for h such that,
u1 v1 u2 v2 y pu p u p y p v p v p y1u1 y1v1 y2 u 2 y2 v2
Collect p 4 pixel locations, remap them as desired, and form the matrix A.
h = [ h11 h12 h13 h21 h22 h23 h31 h32 1] T

Ah = 0.
1999-2011 by Richard Alan Peters II 16
2011-11-07
If the previous def of A led to H that gave wrong results, try this one:

0 x 1 0 A = x2 0 x p 0 -x1 - y1 -1 x1v1 y1v1 v1 1 0 0 0 -x1u1 - y1u1 -u1 0 -x2 - y2 -1 x2 v2 y2 v2 v2 1 0 0 0 -x2u2 - y2u2 -u2 0 0 - x p - y p -1 x p v p y p v p v p 0 0 0 -x p u p - y p u p -u p yp 1 0 y1 0 y2
Collect p 4 pixel locations, remap them as desired, and form the matrix A.
Solve for h such that,
h = [ h11 h12 h13 h21 h22 h23 h31 h32 1] T

Ah = 0.
2011-11-07

svd ( A) = USV T
To find h compute the singular value decomposition (svd) of A. S is a diagonal matrix of singular values.
V = v1 v 2 v p
Write matrix V in terms of its columns. Find k, the smallest sv.
s1 0 S = 0
0 s2 0
0 0 s p
k = arg min {s1 , s2 , , s p }
h = vk
2011-11-07
Then vector h is given by the kth column vector, vk.


If vk is the column vector of V that corresponds to the smallest singular value, then H is given by Now (rI,cI) maps to (rJ,cJ) through H so that. But we want to scan the output image, J, and at each location (rJ,cJ) take a value from I at location (rI,cI), so we do this:
v1k v2 k v3k H = v4 k v5 k v6 k v7 k v8 k v9 k J (rJ , cJ ) = I (rI , cI )

cJ -1 J (rJ , cJ ) = I N H r J 1
19
2011-11-07
Linear Warping of Images Remapping

The inverse mapping of (rJ,cJ,1) through H-1 is (krI,kcJ,k)
cJ k(r ,c)cI H-1 rJ = k(r ,c)rI 1 k (r ,c)

k(r ,c)cI k(r ,c)cI cI 1 = N k(r ,c)rI = k(r ,c) k r rI I r c , ( ) k r c , ( )
and that must be normalized as follows:
Thus for each pixel location (rJ,cJ) in the warped image,
cJ -1 J (rJ , cJ ) = I N H rJ 1
20
2011-11-07
Linear Warping of Images Steps

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Select at least four pixel locations from I, the image to be warped. Create target locations by altering the values of the selected locs. Construct from the location pairs, matrix A as described on slide 16. Compute the singular value decomposition of A = USVT. Select the vector vk that corresponds to the smallest singular value. Construct H from vk . Compute H-1. Create an output image J. For each (rJ , cJ ) in J, select (rI , cI ) from I using the eqns. on slide 19. Since (rI , cI ) is fractional, interpolate on the neighborhood of (rI , cI ) in I to compute J(rJ , cJ ).
2011-11-07
21
Image Rotation
image size:
Rin , C in , B = size (I)

aspect angle:
R in A = tan C in
1
2 2 D = R in + C in
length of diagonal:
2011-11-07
22
Image Rotation
angle of rotation: rotation matrix: cos sin () = - sin cos transforms input image to output image cdts. cdts.1
R in 0 C in 0
r - R R r c = () cin - C in0 + R out0 out0 in0 in
cdts. measured w.r.t. the center of the image:
(R
in0
, C in0 =
) (
1 2
R in + 1, 1 2C in + 1
)
23
2011-11-07
Image Rotation
Compute the dimensions of the output image: number of rows.
R out = round ( Dsin( + A ) ) ,

if 0 < 90.
2011-11-07
24
Image Rotation
Compute the dimensions of the output image: number of columns.
C out = round ( Dcos( -A ) )

if 0 < 90.
2011-11-07
25
Image Rotation
The output dimension calculation depends on the value of as follows:
If 0 < 90: If 90 < 180:
R out = round ( Dsin( + A ) ) , Cout = round ( Dcos( - A ) ).

If 90 < 0:
R out = round ( Dcos(-90- A ) ) , Cout = round ( Dsin(-90 + A ) ).

If 180 < 90:
R out = round ( Dsin( - A ) ) , Cout = round ( Dcos( + A ) ).
R out = round ( Dcos(+90 + A ) ) , Cout = round ( Dsin(+90- A ) ).
2011-11-07
26
Image Rotation
Allocate an output image with dimensions (Rout,Cout), where1
R out = round ( Dsin( + A ) )
C out = round ( Dcos( -A ) )

and center point
R out 0 C out 0
( R out0 , C out0 ) = 1 ( 1 2 R out + 1, 2 C out + 1).

1R out
and Cout below are valid for 0 < 90. Otherwise see slide 7.
2011-11-07
Image Rotation
cos - sin -1 () = sin cos = (- ) Work backward. For every output loc. (r,c) select an input loc. (rf ,cf) by rotating (r,c) around the image center by -. r F ( r , c,:) = f c f r - R out 0 = -1 () c - Cout 0 R + in 0 C in 0
R out 0 C out 0
Image Rotation
Rotating the input image by is equivalent to rotating the ouput image by -. r - R out 0 R in 0 F ( r , c,:) = -1 () + c - Cout 0 C in 0
Image Rotation
After rotation by -, J(r,c) is in nearly the same position as I(rf,cf). r F ( r , c,:) = f c f r - R out 0 = -1 () c - Cout 0 R + in 0 C in 0
Image Rotation
Image Rotation
Image Rotation
J (r , c) = Q {I; N (rf , c f )} .
Interpolation: The output pixel value is (usually) a function of the values on a neighborhood a set of pixels that surrounds (rf ,cf ). Bilinear Interp. uses a 22 neighborhood, bicubic uses a 44. Nearest neighbor is simply, J(r,c) = I(ri ,ci ) where (ri ,ci ) = round(rf ,cf ).
Image Rotation with Interpolation
Original image: San Francisco financial district

Image Rotation with Nearest Neighbor Interpolation
Bicubic Nearest Neighbor

2011-11-07
Nearest Neighbor Bilinear

35
Image Rotation with Bilinear Interpolation
Nearest Neighbor Bilinear

2011-11-07 1999-2011 by Richard Alan Peters II
Bilinear Bicubic
36
Image Rotation with Bicubic Interpolation
Bilinear Bicubic
2011-11-07
Bicubic Nearest Neighbor

Example of Warping: Map Image to Sphere

For the output image, For the input image, d0 = 1 max ( Rin , Cin ) . 2
0 = min ( Rout , Cout ) .
1 2
For each output pixel,

2 2 = rout + cout ,
For each output pixel, the input pixel loc is,
= tan 1 ( cr = sin 1
), ( ).
out out
cin = d cos ( )
rin = d sin ( )
2 d= d 0
2011-11-07
38
Example of Warping: Map Image to Sphere

d: radial distance from center of input image. : same for output image.
2011-11-07
39

EECE/CS 253 Image Processing: Lecture Notes: Warping and Rotating Images

Uploaded by

Copyright:

Available Formats

EECE/CS 253 Image Processing: Lecture Notes: Warping and Rotating Images

Uploaded by

Document Information

Original Title

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

EECE/CS 253 Image Processing: Lecture Notes: Warping and Rotating Images

Uploaded by

Copyright:

Available Formats

EECE\CS 253 Image Processing

1999-2011 by Richard Alan Peters II

Original image with perspective distortion.

Linear Warping of Images

Linear Warping of Images

Image warped to correct perspective distortion.

Linear Warping of Images

(403, 652) Selected correction points.

1999-2011 by Richard Alan Peters II

Linear Warping of Images

(403, 652) Target correction points.

1999-2011 by Richard Alan Peters II

Linear Warping of Images

Result of linear LMS point remapping.

Linear Warping of Images

Image warped to correct perspective distortion.

Linear Warping of Images How To Do It

-1 cJ cJ cI is the warped H = then J (rJ , cJ ) = I H image. rJ rI rJ

RAPII: see notes for this page!

Linear Warping of Images How To Do It

-1 cJ is the warped cJ cI H = then J (rJ , cJ ) = I H rJ rI rJ image.

Linear Warping of Images Homogeneous Cdts.

1999-2011 by Richard Alan Peters II

Linear Warping of Images Homogeneous Cdts.

k1u1 k2u2 Y = k1v1 k2 v2 k2 k1

ki ui h11 h12 h13 xi k v = h h h y i i 21 22 23 i ki h31 h32 h33 1

Here, for vectors xi and yi are the elements of the transform.

1999-2011 by Richard Alan Peters II

Linear Warping of Images Derivation

h11 xi + h12 yi + h13 h31 xi + h32 yi + h33

h21 xi + h22 yi + h23 vi = h31 xi + h32 yi + h33

1999-2011 by Richard Alan Peters II

Linear Warping of Images Derivation

h = [ h11 h12 h13 h21 h22 h23 h31 h32 1] T

the elements of matrix H are written as vector h.

1999-2011 by Richard Alan Peters II

Linear Warping of Images Derivation

h = [ h11 h12 h13 h21 h22 h23 h31 h32 1] T

Linear Warping of Images Derivation

Solve for h such that,

h = [ h11 h12 h13 h21 h22 h23 h31 h32 1] T

Linear Warping of Images Derivation

Write matrix V in terms of its columns. Find k, the smallest sv.

k = arg min {s1 , s2 , , s p }

Then vector h is given by the kth column vector, vk.

Linear Warping of Images Derivation

v1k v2 k v3k H = v4 k v5 k v6 k v7 k v8 k v9 k J (rJ , cJ ) = I (rI , cI )

1999-2011 by Richard Alan Peters II

Linear Warping of Images Remapping

cJ k(r ,c)cI H-1 rJ = k(r ,c)rI 1 k (r ,c)

and that must be normalized as follows:

Thus for each pixel location (rJ,cJ) in the warped image,

1999-2011 by Richard Alan Peters II

Linear Warping of Images Steps

1999-2011 by Richard Alan Peters II

Rin , C in , B = size (I)

1999-2011 by Richard Alan Peters II

r - R R r c = () cin - C in0 + R out0 out0 in0 in

cdts. measured w.r.t. the center of the image: