APPL-1012 / Page 1 of 211
`Apple Inc. v. Corephotonics
`
`

`

`Texts in Computer Science
`
`Edflnrs
`
`David Gries
`Fred B. Schneider
`
`Fer I'urlher walu mes:
`wwwfipringemcma'sefi EH3 E'H
`
`APPL-1012 / Page 2 of 211
`APPL—1012 / Page 2 of 211
`
`

`

`
`
`Richard Szoliski
`
`Computer Vision
`
`Algorithms and Applications
`
`@ Springer
`
`APPL-1012 / Page 3 of 211
`APPL—1012 / Page 3 of 211
`
`

`

`
`
`Dr. Richard chliiiiii
`Micmsni'l Research
`Uni: Micmmi'l Way
`931352453519 Ruliilnnd
`
`Washington
`USA
`smiiiilii @iiiicmml'mnm
`
`.‘i'r'ri'r'i' Edi-mm
`Diwiii Gnui:
`Dcpzinniciii iil' t‘iiiiiiiiiicr Science
`Union Hall
`Ciirncil University
`I[I1:ii::i. NY I4353-i5li] . L‘Si‘i
`
`Fred Fl. Scliimidm'
`Dcpzu‘tment iii Computer Stir: tire
`Upwn Hiiii
`Cumil'li Ulii‘u'irriiiw
`Iflinflii. NY idii53~T5UI . LISA
`
`ISSN 1363-0941
`ISBN 9'33'1-34832-93-1-3
`DUI | H. iiKiTI‘FJTI'ii- | -H4$H1-E135-U'
`
`c-lSSN ISEE~WSX
`c-ISEN 9?Er1-34$SZ-935-D
`
`Springer Lnndnrn Dimlrtchl HEiiltl'll'rcrg New ank
`
`British Li'hniry Caiulngiiiiig III. i'iihiicririnii Dan-
`.-'4. cal-.iingur rccrird irir lhifi hunk i5 :ii'uilal'ilt I'riJIIi 111i: Hniiaii Library
`
`Lihriiry iifflnngrciis Cunlml Number: Jiilfl‘flfii‘ii?
`
`I} Springrr-erng IJ‘ifliflnl‘l LimitniJ 11H 1
`iiriI-‘rrlc iiiiily. iir ri‘iiirisin m :ui'irw. “"1
`Apari Friuii .1in fair dealing in:
`ilir. piirp-mes- Uf reseairti L'II‘
`permitted undrr liii: Cnpyriglli. Ikfiigii; .-i:iiiJ I‘dlirliLi r'iul I‘M-i3, 111:3 |1uliiicfllinri III-fly i'!l1i_'r' he IrpIiJiJquJ.
`\[iiml ur
`transniilicij.
`in .111}- [um iIr 11:.- any mriins. Wi1i1 lhi: prim prrn'iissmn in writing L11
`lhr
`publishers. m in ilir rim.- iii'repmgmpliiu regirmi union in iiiwrdiniw ‘i'I-‘illl iliu rrriiii: of iirrnsrs iS-Hlfli by
`Hi: {‘iipynghl Liurnsing Agent}. Enquirin cnncrniing rcpnnlurlinn i1u'l‘IiEIJE Iliiii-I: Irrrrii- iiliivillll be H‘III
`[0 I'll: iiiihliiiicric.
`Tin: usi- Hr regimird iirinirec. trridrmr-rksr. rich. in this piihliuritmn 1.1in nm Imply. mm In Ihi: £115an nl a
`specific fitulrn'irni. li‘uil. MIL'II iialnus iu'c riiriiipl I'rum IJ'ir. rirliiviinl ILi'u-‘s Lind niguliiiimis and [iicrri'iirn [IN
`[or gnncm! u.iii:.
`The IJIJI'iIifihEr Illiliith' nii mnrtscntutliin. EK'rllL‘fiii rir lmpilfd. Will'- nmard 11: 111i: autumn}: iit'iiic ini'iirmutliin
`miiiiiiilcd iii 1his brink nnii canniit :bcuc-fil: any Inga] msfiiiisihiiity rir liiii'iilitg.I i'iir any :rrrini nr l1mififiii‘lll5
`li'lili may be made.
`
`Prinlcd iin acid-[Ire purer
`
`Springer iii purl [If Springrr Sun: nL'L'+H'l:|5-i|]|:5$ ii'lrdiiiiwww.5]1rin_i.:i:r.i:uml
`
`APPL-1012 / Page 4 of 211
`APPL—1012 / Page 4 of 211
`
`

`

`Chapter 2
`
`Image formation
`
`2.1 Goomotrio primitives and transformnfions ............. . ..... 29
`2.1.1 Geometric primitives ................ .
`. ........ 29
`2.1.2
`2D lmnsfonmtions ........................... 33
`2.1.3
`31:) lransfonnations ........................... 315
`2.1.4
`3Drolalions.
`.
`. .................... .
`.
`.
`.
`.
`.
`.
`.
`32
`
`2.1.5
`2.1.6
`
`. ...... 42
`.
`.
`.
`3Dto2Dp1-ojoclions ............... .
`Lens distortions ............................. 52
`
`2.2 Phommntflcimago formation .......................... 54
`2.2.1
`Lighting ................................. 54
`2.2.2 Reflectance and shading .............. . ......... 55
`2.2.3 Optics ..................... . ............ 61
`2.3 Thodigitalomnm ......... .... .................. 65
`2.3.1
`Sampling and aliasing ......................... 69
`2.3.2 Color
`.
`.
`. ..................... .
`.
`.
`. ...... 21
`
`2.3.3 Compmsaion ............. . ................ EU
`2.4 Additional reading ........ .
`.
`. ................ .
`.
`.
`.
`32
`25 Exoroises .............................. .
`.
`.
`.
`.
`.
`32
`
`R. hellish. Corn-mum Firmm Algorithm: andAperL-mram. Taxis in Computer Scion;
`D01 no.1momfi-L—34m-935o_2.o Springor-‘r’ctlug Londm Linu'hd 2111 I
`
`22
`
`APPL-1012 / Page 5 of 211
`APPL—1012 / Page 5 of 211
`
`

`

`28
`
`2 Imagefnrrmation
`
`
`
`{C}
`
`{:1}
`
`figure 2.] A few qumponnnts of III: image. farmafiuu PIECE-SS: {a} pampmfivn projecfiou: Eb) light Scattering
`whnn hitting a sunken; [c] lens npfics; {d} Bays-.1“ color filter array.
`
`APPL-1012 / Page 6 of 211
`APPL—1012 / Page 6 of 211
`
`

`

`2.1 Geometric primltlves and transformations
`
`29
`
`Before we can intelligently analyse and manipulate images. we need to establish a vocabulary
`for describing the geometry of a scene. We also need to understand the image formation
`process that prodqu a particular image given a set of lighting conditions, scene geometry.
`surface properties. and camera optics. In this chapter. we present a simplified model of such
`an image formation process.
`‘
`Section 2.1 introduces the basic geometric primitives used duoughout the hook (points.
`lines, and planes} and the geometric Iiansformations that project these 313 quantities into 2D
`image features {Figure 2.1a). Section 2.2 describes how lighting, surface properties {Fig-
`ure 2. | h}. and camera optics (Figure 2.1a} interact in order to produce the color values that
`fall onto the image sensor. Section 2.3 describes how continuous color images are turned into
`discrete digital samples inside the image sensor [Figure 2. id} and how to avoid {or at least
`characterise] sampling deficiencies, such as aliasing.
`
`The material covered in this chapter is but a hriefsummary of a very rich and deep set of
`topics. traditionally covered in a number of separate fields. a more thorough introduction to
`the geometry of points. lines. planes. and projections can he found in textbooks on multi—view
`
`geometry [Hartley and Zisserman 2W4; Faugeras and Luong 2120]} and computer graphics
`(Foley, van Darn, Feiner or m“. 1995). The image formation {synthesis} process is traditionally
`taught as part of a computer graphics curriculum (Foley. van Dam. Feiner ct cl. I995; Glass-
`
`ner 1995; 1Watt 1995; Shirley 2095} hot it is also studied in physics-based computer vision
`(Wolff, Shallor, and Healey 1992a}. Tl'te behavior of camera lens systems is studied in optics
`[Mdllcr 1933; Hccht 2091; Ray 2092). Two good books on color theory are (Wyssecki and
`Stiles 2WD; Healey and Shafer I992), with {liviogstone 2993] providing a more fun and in—
`formal introduction to the topic of color perception. Topics relating to sampling and aliasing
`are covered in textbooks on signal and image processing {Crane 1991'; ldhnc 199?; Uppfllie
`helm and Schafer 199d: Oppenheim, Scholar. and Bach I999; Pratt 2992‘, Russ 243W; Burger
`and Huge 2993: Gonzales and Woods 2098}.
`
`A note to students: If you have already studied computer graphics, you may want to
`skim the material in Section 2.1. although the sections on projective depth and object—centered
`projectictn near the end of Section 2.1.5 may he new to you. Similarly. physics students [as
`well as computer graphics students) will mostly he familiar with Section 2.2. Finally. students
`with a good background in image processing will already he familiar with sampling issues
`{Section 2.3} as well as some of the material in Chapter 3.
`
`2.1 Geometric primitivesand transformations
`
`In this section, we introduce the basic 2D and 3D primitives used in this textbook, namely
`points. lines. and planes. We also descIibe how 3D features are projected into 2]] features.
`More detailed descriptions of these topics [along with a gentler and more intuitive introduc-
`tion} can he found in textbooks on multiple-view geometry t'l-lsrtley and Zisserman 2094:
`Fangeras and Luong 2:111}.
`
`2.1.1 Geometric primitives
`
`Geometric primitives form the basic building blocks used to describe three-dimensional shapes.
`In this section, we introduce points. lines. and planes.
`later sections of the hook discuss
`
`APPL-1012 / Page 7 of 211
`APPL—1012 / Page 7 of 211
`
`

`

`30
`
`'-
`
`I
`
`2 Image ionisation
`
`
`
` {hi
`
`Figure 1.2 {a} 2D line equation and {In} 3D plane equation. expressed in terms of the normal it and distance to
`the origin ti.
`
`curves (Sections 5.1 and 11.2}. surfaoes (Section 12.3}. and volumes {Section 12.5}.
`
`EU paints. 2D points {pixel coordinates in an image] can be denoted using a psiref values,
`:1: = {my} E 122.01“ alternatively.
`
`z = [ m ] .
`
`if
`
`{2.1}
`
`{As stated in the introduction, we use the {231.9331 . . .] notation to denote eoiumn vectors.)
`2D points can also he represented using homogeneous coordinates. i = {£11.13} (-3 P2.
`where vectors that differ only by seals are considered to be equivalent. P2 = R3 — {13,01 ii}
`is coiled the 2D projective space.
`
`A homogeneous vector is can be converted back into so inhomogeneous vector at by
`dividing through by the inst element iii. i.e..
`
`i = (s, s, o} = «ms-.1,“ 1} = no,
`
`{so}
`
`where i = (m, y, l} is the augmented vector. Homogeneous points whose last element is if: =
`D are called ideal points or points at infinity and do not have an equivalent inhomogeneous
`representation.
`
`2D lines can also he repteseuted using homogeneous coordinates i = (o. it. e].
`2D III'IBB.
`The corresponding line equation is
`
`s-i=ex+by+c=o.
`
`{2.3}
`
`We can normalize the line equation vector so that! = (132.11... d] = [fit '3'} Willi "fill = 1- 11‘
`this case. it is the some! vector perpendicular to the line and dis its distance to the origin
`{Figure 2.2}. {'I'he one exception to this normalization is the line or irgfim'ty i- : (0.0.1).
`which includes all {ideal} points at infinity.)
`We can also express it. as a function ot'rotaliou angle 5. it = {one} = (onset, sin ii}
`[Figure 2.2a}. This representation is commonly used in the Hottgh transform iiuefinding
`algorithm, which is discussed in Section 4.3.2. The combination [(9.51]: is also known as
`poior coordinates.
`1|Ill-Then using homogeneous ooordinates, we can compute the intersection of tvro lines as
`
`5'3 = fl 1' 121
`
`{14}
`
`APPL-1012 / Page 8 of 211
`APPL—1012 / Page 8 of 211
`
`

`

`2.1 Geometric primitives and transformations
`
`31
`
`where x is the cross product operator, Sirlailsi'ljr+ the linejoinjng two points can be written as
`
`F=s1x ea.
`
`[2.53
`
`When trying to fit an intersection point to multiple lines or. convcssely. a line to multiple
`points, least squares techniques {Section 6.1.1 and Appendix All can be used, as discussed
`in Exercise 2.1.
`
`2D cont h: . There are other algebraic curves that can he expressed with simple polynomial
`homogeneous equations. For example, the sonic sections {so called because they arise as the
`intersection ofa plane sud a 3D cone] can be mitten using a quodrt'c equation
`
`:ETQE = n.
`
`{2.6}
`
`Quadrle equations play useful roles in the study ofmnltivuiew geometry and camera calibra-
`tion {Hartleyr and Eissertnan 2W; Fhugeras and Luong 1001} but are not used eitttensinrel}r in
`this book.
`
`an points. Point coordinates in three dimensions can be written using inhomogeneous co-
`ordinatesa: = (my, 2:] E R3 orhomogeneous coordinates i = {iiitfil E ‘Pa. selections.
`it is sometimes useful to denote a 3]] point using the augmented vector 5: = {3, p, z. 1} with
`5: = iii.
`
`3]] planes can alsohe represented as homogeneous coordinates 1?: = (a, h, eJ rt}
`3D planes.
`with a corresponding plane equation
`'
`
`tit-rit=ctc+hy+ez+d=fl.
`
`(2.?)
`
`Wecan also normalize the plane equation as m. = {fih fry, fl.“ d} = (Ft, d] with ”fill = 1.
`In This case. it is the sonnet vector perpendicular to the plane and d is its distance to the
`origin [Figure 2.2m. As with the ease of so lines. the plane at infinity in = {one 1].
`which contains all the points atinfinity'1 cannot be nonnslised tie, it does not have a unique
`normal or a finite distance}.
`
`We can express it as afunction oftwo angles {do}.
`
`1‘1: {oochosd.s1‘nHoos¢r.sin¢t}l.
`
`{2.3)
`
`i.e.. using spherical coordinates, but these are less COlnfllUfllj" used than polar coordinates
`since they do not tniifornsty.r sample the space ofpossible normal vectors.
`
`3-D lines. Lines in 3D tireless elegant than either lines in 2D or planes in 31]. One possible
`representation is to use two points on the line, {go}. Any other point on the line can. he
`expressed as a linear combination of dense two points
`
`a'
`
`1" = {1 - its + is.
`
`(1-9}
`
`as shown in Figure 2.3. If we restrict D 5 .1. S, 1. we get the line 5.23th joining p and q.
`
`APPL-1012 / Page 9 of 211
`APPL—1012 / Page 9 of 211
`
`

`

`32‘.
`
`2 Image formation
`
`
`
`Figure 2.3 3D line equation. to = {l — Alp + An.
`
`if we use homogeneous coordinates, we can write the line as
`
`F=p‘+.ltrf.
`
`{2.1m
`
`A special case of this is when the second point is at infi nity. ie.. «E = (six, cl”, EL, {l} = (cl. [I].
`Here. we see that d is the direction of the line. We can then reanite the inhomogeneous 3|}
`line equation as
`
`'r' = p+ sci.
`
`(2.11]
`
`A. disadvantage of the endpoint representation for 3D lines is that: it has too runny degrees
`of freedom. i.e.. six {three for each endpoint} instead of the four degrees that a 31) line truly
`has. However. if we Ith the two points on the line to lie in specific planes. we obtain a rep-
`resentation with tour degrees of freedom. For example. if we are representing nearly vertical
`lines. then 2 = [1 and z = 1 form two suitable planes, i.e.. the {:r, y) coordinates in both
`planes provide the four coordinates describing the line. This kind of two-plane psrmneterh
`zation is used in the iightfleid and henigmph image-based rendering systems described in
`Chapter 13 to retire-sent the collection of rays seen by a camera as it moves in front of an
`ohjecL The two-endpoint representation is also useful for representing line segments. even
`when their exact endpoints cannot be seen [only guessed at}.
`
`If we wish to represent all possible lines without bias towards any particular orientation.
`we can use Plflcker coordinates {Hartley and Zissermnn 2W. fltapter 2; Fangeras and Lueng
`21:101. Chapter 3}. These coordinates are the six independentnon-zero entries in tired x4 skew
`sytnrnetric matrix
`
`L = is? — stir.
`
`(2.12;
`
`where 15 and ii are any two (non—identical] points on the line. This representation has only
`four degrees of freedom. since L is homogeneous and also satisfies detiL] = U. which rctults
`in a quadratic constraint on the Pliieker coordinates.
`
`1“. practice, the minimal representation is not essential for most applications. he ade
`quate model of 31) lines can he obtained by estimating their direction {which may be known
`ahead of time. e.g.. for architecture} and some point within the visible portion of the line
`{see SeBfion Iii} or by using the two endpoints. since lines are most often visible as finite
`line segments. However, if you are interested in more details shout the topic of minimal
`line parameter-lemons. Ftirstner titlflfi} discusses various ways to infer and model 3D lines in
`projective geometry. as well as how to estimate the uncertainty in such fitted models.
`
`APPL-1012 / Page 10 of 211
`APPL-1012 / Page 10 of211
`
`

`

`2.1 Geometric primitives and transformations
`
`33
`
`
`
`Figure 2.4 Basic set of 2D planar transformations.
`
`3D ouadrlea.
`
`"The 3D analog of a sonic section is a quadrie surface
`
`aqu = o
`
`{2.13}
`
`[Henley and Elisserman 2004.. Chapter 2}. Again. while quadrie surfaces are useful in the
`study of mold-view geometry and can also serve as useful modeling primitives (spheres.
`ellipsoids, cylinders}. we do not stud},r them in great detail in this hook.
`
`2.1 .2 2D tranatorrnationa
`
`Having defined our basic primitives. we can now turn our attention to how the}.r can be trans-
`formed. The simplest transfomtations occur in the 2D plane and are illustrated in Figure 2.4.
`
`Translation.
`
`21:: translations can be wa‘itten as at = n: + t or
`
`where I is the [2 x 2} identity matrix or
`
`a“:[ I t]a
`
`I
`
`t
`
`ffllfli iii
`
`(2.14}
`
`{to}
`
`where t] is the zero vector. Using a 2 x 3 matrix results in a more compact notation. whereas
`using a full—rank 3 x 3 matrix (winch can be obtained from the 2 x 3 matrix by appending a
`[HT 1] row] makes it possible to chain transformations using matrix multiplication. Note that
`in any equation where an augmented vector such as it appears on both sidesr it can always be
`replaced with a. full homogeneous vector i
`
`Battalion 1- translation. This transformation is also lrnoa-rn as 2D rigid body motion or
`the 2.0 Euclidean Imasfommrion {sinee Euclidean distanoes are preserved). It can be written
`as m‘ = Ha: + t or
`
`=[n we
`
`where
`
`El
`ti
`.
`ees —eln
`]
`R=laua mes
`,.
`is an orthonormal rotation matrix with RRT = I and [El = l.
`
`{2.16)
`
`{2'17}
`
`APPL-1012 / Page 11 of 211
`APPL-1012/Page 11 of211
`
`

`

`34
`
`1 Image formation
`
`Seated “Italian. Also known as the similarity transform. this transformation can be eit—
`pressed as at’ = slits + t. where s is an arbitrary scale faetor. it one also be written as
`
`m’ = [ sR t 15 = [
`
`b
`
`a —i.'t
`
`a
`
`_
`
`1.:
`
`for];
`
`{2.13}
`
`where we no longer require that n2 + it“ = l. The similarity transform preserves angles
`henseen tines.
`
`Affine. The affine transformation is written as m’ = An, where A is an arbitrary 2 x 3
`matrix. Le.
`
`I: = [ HOD
`
`Bio
`
`illll]
`
`Iii-ti
`
`t']
`
`no 13—:
`
`R12
`
`{.219}
`
`Parallel lines remain parallel under affine n'ansformations.
`
`Projaetlve. This transformation. also known as a perspective tranjorm or hemography,
`operates on homogeneous coordinates.
`
`n’ = fin,
`
`{too}
`
`where I} is an arbitrary 3 :u: 3 matrix. Note that 1:! is homogeneous. in. it is only defined
`up to a scale. and that two fl“ matrices that differ only by sealelare equivalent The resulting
`homogeneous coordinate :E’ must he annualized in order to obtain an inhomogeneous result
`m.i.e..
`
`
`_
`_
`_ iltnfil+htitt+ his
`I: _ hoo$+hoitt+ho2 and
`l
`{2“
`heel“ + hoist + has
`hsnm + hart! + has
`Perspective oansfnnnannns preserve straight lines tie. they remain straight after the unna-
`formation}.
`
`.
`
`2]
`
`Hiararohy of 2D tranafonnatlona. The preceding set of transformations are illuitrated
`in Figure 2.4 and summarised in Table 2.1. The easiest way to think of them is as a set
`of [potentially restricted) 3 x 3 matrices operating on 2D homogeneous coordinate veemrs.
`Hartley and Zisserman {201214) contains a more detailed description of the hierarehy of 2D
`planar transformations.
`The above transformations form a nested set of groups. i.e.. they are elosed under eom—
`position and have an inverse that is a member of the same group. {This will be important
`later when applying these transformations to images in Section 3.6.} Bath {simpler} group is
`a subset of the more oomplett group below it.
`
`{lo-tractors. While the above transformations can be used to transform points in a. 1D
`
`plans. can they also he used directly to n'ansform a line equation? Consider the homogeneous
`equation l . i = it. lfwe transform in“ = Howe obtain
`
`Fan’=ifl'frn=rr§rTf}Tn=i-s=o.
`
`{2.22}
`
`i.e., r = iii—Ti. Thus, the aetion of a projective transfmmafion on a err-vector sneh as a 11']
`line or 3D normal ean be represented by the transposed inverse of the matrix. which is equiv—
`alent to the nose: of 1:1“. since projective transformation matrices are homogeneous. Jim
`
`APPL-1012 / Page 12 of 211
`APPL-1012 / Page 12 of211
`
`

`

`2.1 Geometric primitives and transformations
`
`Transformation
`
`Matrix
`
`# DUI"
`
`Preserves
`
`Ioon
`
`translation
`rigid {Euclidean}
`sinnlarity
`affine
`projective
`
`[ I I
`it lass
`[ fl [
`f. ]m_
`[ HR |
`f. ]“3
`[ A ]2x3
`[ 1? 13K:
`
`2
`3
`4
`E-
`8
`
`i:i
`orientation
`lengths O
`angles
`0
`parallelism E
`straight lines
`I3
`
`Tattle 11 Hierarchy of 2D coordinate transformations. Earth transformation also preserves the properties listed
`in the rows helo'a-r it1 i.e.. similarity;-r preserves not onlyr angles trot also parallelism and straight lines. The ‘2 x 3
`matrices are extended with a third {UT 1] row to form a full 3 x 3 man-ht for homogeneous coordinate transfonna-
`Eons.
`
`Elinll [1993] describes [in Chapters 9 and 1D) the ins and outs of mutating and manipulating
`on-vettnrs.
`
`We the above transfonnations are the ones we use most extensively, a number of addi—
`tional transformations are sometimes used.
`
`Strotohisqunsh. This transformation changes the aspect ratio ofan image,
`tI
`
`1:
`
`= sxm +t1
`
`ii! = Etrif'" :‘III1
`
`and is a restricted form of an affine transformation. Unfortunately, it does not nest cleanly
`with the groups listed in Table 2.1.
`
`'I'lds eighbparmnm transformation {Horn 3936; Bergem Anna.
`Planar surfaoo flow.
`nan, Hanna er ai. 1992; Girod. firemen and Niemann EDD-[ll],
`
`2’ = no+alm+oss+nsai+aras
`
`s’ = ns+ais+ass+arai+asaa
`
`It can thus be thought of as a
`arises when a planar surface undergoes a small 3D motion.
`small motion approximation to a full homography. Its main attraetion is that it is linear in the
`motion parmnetets, up, which are often lhe quantitiets being estimated.
`
`Bitlnear Interpolant. This eight-paramtor transform {Wolherg 1990},
`I
`
`a
`
`= an+aiz+n2s+asmtr
`
`s’ = as + are + on: + area,
`
`can he used to interpolate the deformation due to the motion of The four eot'net' points of
`a square {In fact, it can interpolate die motion of an}r four non-collinear points.) While
`
`APPL-1012 / Page 13 of 211
`APPL-1012 / Page 13 of211
`
`

`

`3d
`
`2. Image fonnation
`
`
`
`
`
`
`
` Transformation Matrix -# DoF Preserves Icon
`
`
`
`
`
`i:i
`orientation
`3
`r. ]m
`[ r |
`translation
`lengths O.
`a
`[ R | a 13“
`rigid (Euclidean)
`angles
`0
`‘t
`[ 51%|: 13“
`similarity
`parallelism fl
`12
`[ a ]m
`affine
`
`
`
`
`projective I [ ri L“ is straight lines
`
`Table 2.2 Hierarchy of 3D coordinate transformations. Each o-ansfortnation also preserves the properties listed
`in the rows 'neloair it. i.e., similarity preserves not only.r angles but also parallelism: and straight lines. The 3 x 4
`man-lees are eatertded with a fourth [UT 1] row to form a full 4 x 4 matrix for homogeneous eoordinate transforv
`motions. The mnemonic icons are drawn in 2]] but are meant to suggest transformations occurring in a full 3D
`cube.
`
`the deformation is linear in tine motion parameters, it does not generally preserve straight
`lines {only lines parallel in the square axes]. However. it is often quite useful. e.g,. in the
`interpolation ofsparse grids using splines [Section 8.3].
`
`2.1 .3 3D transformations
`
`The set of three-dimensional coordinate transformations is very similar to that available for
`2D transformations and is summarized in Table 2.2. As in ED. these transformations form a
`
`nested set of groups. Hartleyr and Zissernian (2004. Section 2.4} give a more detailed descrip-
`tion of this lucreichy.
`
`Waterloo.
`
`31) translations can be written as in“ = to + t or
`
`where I is the {3 x 3} identity matrix and D is the zero vector.
`
`e’=[r e ]e
`
`{2.23}
`
`Rotation -t- translation. Also known as 3D rigid body motion or the 3D Euclidean trans—
`formation. it can be written as te’ = Ra: + t or
`
`z’=[R t]n
`
`{2.24}
`
`where R is a s x a orthonormal rotation man-in: with 3.3“" = r and |Rl = 1. Nate that
`sometimes it is more convenient to describe a rigid motion using
`
`at’ = HIIa: - e} = Ra: — Re,
`
`{2.15}
`
`where c is the center of rotation {often the camera center}.
`
`Compactly parameterizing a EU rotation is a non—trivial task. 1arhicl't we describe in more
`detail below.
`
`APPL-1012 / Page 14 of 211
`APPL-1012/Page 14 of211
`
`

`

`2.1 Geometric primitives and transformations
`
`3'?
`
`Seated rotation. The 3D strafinrity transform can he expressed as :r:’ = 3R1: + It where
`s is an arbitrary scale factor. it can also be written as
`
`This transformation preserves angles between lines and planes.
`
`m“ = [ sfl‘.
`
`e lo.
`
`(2.215)
`
`.
`
`Affine.
`i.c..
`
`'Ihe afiine transform is written as :e‘ = Ari. where A is an arbitrary 3 x It matrix.
`
`’
`z =
`
`“on
`
`“It:
`flan
`
`I111
`1121
`
`em no: nos]
`
`I312
`Ilsa
`
`are
`Baa
`
`a
`
`(2.2?)
`
`Parallel lines and planes remain parallel under afline transformations.
`
`Projeottaa. This transformation. variously lrrtown as a JD perspective fmtlfllfl'l’m, honing—
`rnphy. or collimation. operates on homogeneous coordinates.
`
`a 2 tie.
`
`(2.2s)
`
`where H is an arbitraryr 4 x d homogeneous matrix. are in 2D. the resulting homogeneous
`coordinate a? must be normalized in order to obtain an inhomogeneous result re. Perspective
`
`transformations preserve straight lines fire. they remain straight after the transformation].
`
`2.1.4 3D rotations
`
`The biggest diEemncc between 2E} and 3D coordinate transformations is that the parameter-
`ization of the 3D rotation matrix R is not as straightforward but several possibilities exist.
`
`Euler angtas
`
`a rotation matrix can be formed as the product of three rotations around three cardinal axes.
`
`e.g.. s. y. and z. or a', y. and a. This is generally a bad idea, as the result depends on the
`order in which the treasforrns are applied.
`Ivt‘r'hat is worse. it is not always possible to move
`smoothly in the parameter space. i.e.. sometimes one or more of the Euler angles change
`dramatically in response to a small change in rotation." For these reasons. we do not even
`give the formula for Euler angles in this book—interested readers can look in other textbooks
`or technical reports {Faugeras 1993; Diebel enact. Note that.
`in some applications. if the
`rotations are known to be a set of uni-axial transforms. they can always be represented using
`
`an asphalt set of rigid transformations.
`
`Atrialangla (attportantlal twist}
`
`a relation can be represented by a rotation axis ft. and an angle it. or equivalently by a 3D
`vector to = dr‘i. Figure 2.5 shows how we can compute the equivalent rotation. First, we
`project the vector t.- onto the axis ft. to obtain
`
`I lnrobotlcs. this is secretlnres referred toes girrrbrtttoctt.
`
`u" = are - v] = (salts,
`
`{2.29)
`
`APPL-1012 / Page 15 of 211
`APPL-1012 / Page 15 of211
`
`

`

`33
`
`'
`
`1'. Image Formation
`
`
`
`Figure 2.5 Rotation around an axis 7': h}! an sngic H.
`
`which is the component of ‘t! that is not nfi'cctod by tho rotation. Next. we compntc tho
`perpendicular residual ofn from fi.
`
`1:. = u—u” = tr—nnTiu.
`
`We can wrote this vector lav 91:!“ using the cross product.
`
`ox =fiXu= [film-.111
`
`(can;
`
`{2.31)
`
`when: [fiix in tho matrix form of thc cross prothtct operator with tho vector fl. = (71,, ft“, fix}.
`
`i}
`
`In]t = [ a.
`
`_fiy
`
`—-fi,
`
`Ft,
`
`a —fi. ] .
`
`fix
`
`CI
`
`(2.32}
`
`Note that rotating this vector by snolhor ED“ is oqnivslllt to taking the cross product again.
`
`on = 7‘: X W = [filiv = ‘flLr
`
`andhcncc
`
`1t"='l.t—'I'.IJ_ =fl+flxx ={I+{fi]i]u.
`
`Wt: can nmv compute the in-plsnc component of tho rolntcd vector u as
`
`ui = cos Hui +ninti'ox = {sin fifth — MSW}: in.
`
`Putting all thcsc terms tognthcr. we obtain lilo final rotstcti vector as
`
`u= or +1.!” = {I+sind|fi],. + [1 —oosd}[fi!§¢]u.
`
`{2.33}
`
`We can mcrcforc mitt: tho rotation matrix corrcspornding to s rotation by H around an axis ii.
`35
`
`Rfiflflj =I+smn{a].. +[1—cmn}[n]i.
`
`{2.34:-
`
`whioh is knttv-I'Il an Rodriguez h‘famuiu [hyachc 1989}.
`The product. ofthc axis 15. and angle a, n: = M = [umwwwfih is a minimal reproach;
`tanon [or a 3D rotation. Rotations through common angles such as multiples of 90“ can be
`rcprcsnntod citactlf,r {and oortvcrtotl to oxact matriocn) fit? is stored in dogmas. Unfortunately1
`
`APPL-1012 / Page 16 of 211
`APPL-1012 / Page 16 of211
`
`

`

`2.1 Geometric primitives and Iranshormatiorts
`
`39
`
`this representation is not unique. alone we can always and a multiple of 350° {Err radians] to
`I? and get the same rotation matrix. its well, {r11 15*} anti (—i‘t. —6'} represent the same rotation.
`Honnnrerr for small rotations leg" oon'eotions to rotations). this is an eaeellent choioe.
`In particular. for small {infinitesimal or instantaneous} rotations and 5 expressed in radians.
`I.
`Rodriguez's formula simplifies to
`
`RIEeJ] or I + sin F[fi]x an f+ [flfilp =
`
`—n.rl
`l
`1
`to.
`_wy w:
`
`in”.
`—n.r=
`1
`
`I
`
`[2.35)
`
`which gives a nice linearized relationship between the rotation parameters or and R. We can
`also Write Rfiwln as t: + to x to which is handy when we want to compute the derivative of
`fit: with respect to at.
`
`Li
`
`EEE = _{ulx = [ _t
`
`o
`
`2 —y
`
`z I
`
`one}
`
`Another way to derive a rotation through a finite angle is ealien the smarter-iris! twist
`(Murray, LL and Sastrjrr 1994}. A rotation by an angle t? is equivalent to it rotations through
`Elfin. In the limit as is —r no. we obtain
`
`1
`R{fi.3} = lira {1+ —[sa],Ji =ex'plwlx.
`h—em
`k
`
`{2.31}
`
`If we expand the matrix exponential as a Taylor series [using the identity.r [fil:+2 = —[r'i.]’f¢,
`i; :- fl. and again assuming El is in radians], -
`
`ti”
`33
`Willi-”ls = I+9ifilx +§ifili +filfili +
`2
`n93
`33
`_
`_
`ti"t
`— no- fi‘l‘MJlfllr-CTiF—E‘l'mlifilx
`= r+ans[n]K + {1 - coasnnfi,
`
`{asst
`
`which yields the familiar Rodriguez's formula.
`
`Unit quaternlona
`
`The unit quaternion representation is closely related to the anglefaxis representation. A unit
`quaternion is a unit length d-veetor whose components can be written as q = [on pm an. owl
`or q = (a. p. z, to} for short. Unit quaternions live on the unit sphere ||q|l = l and antiporiai
`[opposite sign} quaternionsrq and —q. represent the same rotation [Figure 2.6}. Other than
`this ambiguity.r [dual oovering}, the unit quaternion representation of a rotation is unique.
`Furthermore. the representation is continuous. i.e.. as rotation matrices vary continuously,
`one can find a oonlinuoos quaternion representation. although the path on the qnsternion
`sphere may wrap all the way around before returning to the "origin" on = {0.0.0.1}. For
`these and other reasons given below. quaternions are a very popular representation for pose
`and for pose interpolation in computer graphics {Shoemalte I985}.
`
`APPL-1012 / Page 17 of 211
`APPL-1012 / Page 17 of211
`
`

`

`4i}
`
`1 Image formation
`
`
`
`Figure 115 Unit quaternions live on the unit sphere ||q|| = 1. This figure shows a smooth trajectory through the
`three quaternions Gc- in. and in. The amipodai point to ‘12- nartieii.r —qg. reprcscuta the same rotation as '12-
`
`Quatemiens can be derived from the aaisi'artglc representation through the formifla
`
`q = {11,191 = {sin 21%., cos g},
`
`{2.39}
`
`where it and d are the rotation axis anti angle Using the trigonometric identities sind =
`25in % cos % and {l — cost?) = 2 sin? %. Rodriguez‘s fonmtla can be converted to
`
`Rise} = r+sns[a]x+t1—coafiiifi]i
`= I+2wla1x+2[a]i.
`
`til-till)
`
`This suggests a quick wavto rotate a vector” by aquaternion using a series of cross products.
`scalings. and additions. To obtain a foimuia for Rfifl as a function of [317, y. z. to}, recall that
`
`[a]x=
`
`y
`t] —z
`z
`[I —e
`—y
`ta
`{1
`
`and [a]§¢=
`
`flag—s:
`my
`at:
`
`my
`—:r“-—s3
`ya
`
`to:
`ya
`—::.-‘—pJ
`
`We thus obtain
`
`1 — ‘EEy3 + 23}
`
`21:2;- — era-:1
`
`flats + pic}
`
`Rig} =
`
`21:31: + m}
`
`l — 2&2 + a“)
`
`2(ys ... aw}
`
`.
`
`{2.41)
`
`an — am}
`
`as: + mi
`
`1 — so} + so
`
`The diagonal terms can he made more symmetrical hv replacing l — Eur2 + 22} with [:c" +
`at“ — y” — z“). etc.
`The nicest aspect of unit quaterniorts is that there is a simple algebra for composing rota—
`tions expressed as unit quaternions. Given two quaternions on = {am we} and q, = [111.1111].
`the quatsmion muitipiy operator is defined as
`
`#2 = csq1=ivu x v: + new: +w1us.wnw1— ”Fri-'1}.
`
`(2.42}
`
`with the property that Riga) = R(qfl]R{q-lj. Note that quatcmion multiplication is not
`commutative. just as 3D rotations and matrix multiplications are not.
`
`APPL-1012 / Page 18 of 211
`APPL-1012 / Page 18 of211
`
`

`

`1.1 Geometrie primitives and transformations
`
`d1
`
`prooeflttre sieipllzqfl, 9'1 , er}:
`
`1- at = arias = [vi—no}
`
`.Ewreflthenqrh—qf
`
`2". return q: = ‘i'u‘i'o
`
`. a =2ten’1flllurlliwr}
`
`- fir =.i"u"'[t.r,:| = ”rillurll
`
`. d.“ = odr
`
`.qg = {singer‘s-moons 3;}
`
`Algorithm 1.! Spherical linear interpolation {sleet-p]. The axis and total angle are first computed from the quater—
`nion ratio. {This computation can be lifted outside an inner loop that generates a set of interpolated position for
`animation.) its increments] qnatesrtion is then eonipnted and multiplied by Ihe stoning rotation quaternion.
`
`Taking the inverse of a quaternion is easy: Just flip the sign of n or ‘Ltl' {but not both”.
`{You ean verify this has the desired effect of transposing the R matrix in {2.41).} Thus. we
`ean also define quarantine division as
`
`'32 = Guilt}: = 'Ioli'fl ={1'tt 3" "I + Weill — “hum —wn1-'-f1 — 1”o ' 111)-
`
`{2-43}
`
`This is useful when the incremental rotation between two rotations is desired.
`
`In particular. if we want to determine a rotation that is partway between two given rela-
`tions, we can oomptlte Ihe incremental rotation, tain: a fraefion of the angle. and compute the
`new rotation. This procedure is called spherical linear interpolation or slot}: for short {Shoo
`make 19135} and is given in Algorithm 2.1. Note that Shoemake presents two formulas other
`Than the one given here. The first exponentiates or by slphs before multiplying the original
`quaternion,
`
`while the seoond treats the quaternions as 4-veflms on a Sphere and uses
`
`on = effing.
`
`=
`
`sinfl — odd
`_
`sinii
`
`its
`
`
`sin of?
`tl'o‘l' 5111391:
`
`(144]
`
`.45
`
`l
`
`[2
`
`where 5' = ens—1WD - :31} and the dot produet is directly bemeen the quatemion d—veotors,
`All of these formulas give comparable results. although care should be taken when fin and in
`are close together. which is why I prefer to use so sretangent to establish the rotation angle.
`
`Whleh rotation representation is better?
`
`The ehoiee of mpresentsfion for 3D rotations depends partly on the