Chapter 13 Perspective Projection Geometry

13.1 Introduction Computer vision problems often involve interpreting information on a two-dimensional (2D) image of a three-dimensional (3D) world in order to determine the placement of the 3D objects portrayed in the image. To do this requires understanding the perspective transformation governing the geometric way 3D information is projected onto the 2D image. image formation on the retina, according to Descartes scrape ox eye, observe from darkened room inverted image of scene =====Nalwa, A Guided Tour of Computer Vision, Fig. 2.1=====

13.2 One-Dimensional Perspective Projection f: focal length of lens u: distance between object and lens center v: distance between image and lens center thin-lens equation: lens law:

\frac{1}{f} = \frac{1}{u} + \frac{1}{v}

light passing lens center does not deflect light parallel to optical axis will pass focal point =====Nalwa, A Guided Tour of Computer Vision, Fig. 2.11===== perspective projection: object point projected along straight line —caption— =====Nalwa, A Guided Tour of Computer Vision, Fig. 2.3===== image distortion: room ceiling appears bowed in the image =====Nalwa, A Guided Tour of Computer Vision, Fig. 2.13=====

pinhole camera: infinitesimally small aperture pinhole camera: approximated by lens with aperture adjusted to the smallest pinhole camera: simplest device to form image of 3D scene on 2D surface =====Nalwa, A Guided Tour of Computer Vision, Fig. 2.2===== aperture size decreased: image become sharper diameter of aperture is 0.06 inch, 0.015 inch, 0.0025 inch aperture below certain size: diffraction: bending of light rays around edge =====Nalwa, A Guided Tour of Computer Vision, Fig. 2.10=====

lens oriented along the y-axis and image plane parallel to x-axis perspective projection gives point (r, s) coordinates (rf/s, f) on image =====Fig. 13.1===== f: camera constant (different from above equation) (r, s, 1): homogeneous coordinate system for point (r, s) first linear transformation: translates (r, s, 1) by distance of f second linear transformation: takes perspective transformation to image line

( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}1 & 0 & 0 \\ 0 & 1/f & 1 \end{matrix} ) ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & −f \\ 0 & 0 & 1 \end{matrix} ) ( \begin{matrix}r \\ s \\ 1 \end{matrix} ) = ( \begin{matrix}r \\ s/f \end{matrix} )

1D image line coordinate: x_{I} = u/v = rf/s

lens: at origin and looks down y′-axis image line: distance f in front of lens and parallel to x′-axis x′ − y′ axes: the x − y axes rotated anticlockwise by angle θ =====Fig. 13.2===== rewriting the relationship in terms of homogeneous coordinate system

( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}1 & 0 & 0 \\ 0 & 1/f & 1 \end{matrix} ) ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & −f \\ 0 & 0 & 1 \end{matrix} ) ( \begin{matrix}cos θ & sin θ & 0 \\ − sin θ & cos θ & 0 \\ 0 & 0 & 1 \end{matrix} ) ( \begin{matrix}r \\ s \\ 1 \end{matrix} )

13.3 The Perspective Projection in 3D camera lens: along line parallel to z-axis position of lens: center of perspectivity: (x_{0}, y_{0}, z_{0})

(u, v): coordinates of perspective projection of (x, y, z) on image plane

( \begin{matrix}x^{∗} \\ y^{∗} \\ t^{∗} \end{matrix} ) = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1/f & 1 \end{matrix} ) ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & −f \\ 0 & 0 & 0 & 1 \end{matrix} ) ( \begin{matrix}1 & 0 & 0 & −x_{0} \\ 0 & 1 & 0 & −y_{0} \\ 0 & 0 & 1 & −z_{0} \\ 0 & 0 & 0 & 1 \end{matrix} ) ( \begin{matrix}x \\ y \\ z \\ 1 \end{matrix} )

thus

u = \frac{x^{∗}}{t^{∗}} = f \frac{x − x_{0}}{z − z_{0}} v = \frac{y^{∗}}{t^{∗}} = f \frac{y − y_{0}}{z − z_{0}}

13.3.1 Smaller Appearance of Farther Objects without loss of generality: take center of perspectivity to be origin perspective projection: objects appear smaller the farther they are =====Fig. 13.3===== foreshortening: line segments in plane parallel to image has maximum size =====Fig. 13.4=====

13.3.2 Lines to Lines lines in the 3D world transform to lines in the image plane parallel lines in 3D with nonzero z slope: meet in a vanishing point =====Nalwa, A Guided Tour of Computer Vision, Fig. 2.4=====

13.3.3 Perspective Projection of Convex Polyhedra are Convex proofs in textbook, simple but tedious, study as exercise by yourself

13.3.4 Vanishing Point Perspective projections of parallel 3D lines having nonzero slope along the optic z-axis meet in a vanishing point on the image projection plane.

13.3.5 Vanishing Line All lines lying in planes parallel to the slanted floor have vanishing points that lie along a vanishing line. =====Fig. 13.5===== =====Tour Into Picture===== =====Garfield 17:21=====

13.3.6 3D Lines-2D Perspective Projection Lines There is a relationship between the parameters of a 3D line and the parameters of the perspective projection of the line.

3D line L:

L = \{( \begin{matrix}x \\ y \\ z \end{matrix} ) |for some λ, ( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} ) + λ ( \begin{matrix}b_{1} \\ b_{2} \\ b_{3} \end{matrix} )\}

perspective projection of the line L:

M = \{( \begin{matrix}u \\ v \end{matrix} ) |for some η, ( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}c_{1} \\ c_{2} \end{matrix} ) + η ( \begin{matrix}d_{1} \\ d_{2} \end{matrix} )\}

take camera lens as origin of coordinate system

u = f \frac{x}{z}

v = f \frac{y}{z}

for any given λ, η:

c_{1} + ηd_{1} = f(a_{1} + λb_{1})/(a_{3} + λb_{3})
c_{2} + ηd_{2} = f(a_{2} + λb_{2})/(a_{3} + λb_{3})

eliminate η:

c_{1}d_{2} − c_{2}d_{1} = \frac{d_{2}f(a_{1} + λb_{1}) − d_{1}f(a_{2} + λb_{2})}{a_{3} + λb_{3}}

for any λ:

(c_{1}d_{2} − c_{2}d_{1})a_{3} − (d_{2}a_{1} − d_{1}a_{2})f + λ[b_{3}(c_{1}d_{2} − c_{2}d_{1}) − (d_{2}b_{1} − d_{1}b_{2})f] = 0 thus

d_{2}fa_{1} − d_{1}fa_{2} + (c_{2}d_{1} − c_{1}d_{2})a_{3} = 0
d_{2}fb_{1} − d_{1}fb_{2} + (c_{2}d_{1} − c_{1}d_{2})b_{3} = 0

13.4 2D to 3D Inference Using Perspective Projection perspective projection on unknown 3D line: provides four of six constraints additional constraints: 3D-world-model information about points, lines

13.4.1 Inverse Perspective Projection (u, v): perspective projection of a point f: image plane distance from camera lens thus (u, v, f): 3D coordinate of the point in image plane camera lens: at the origin line L: inverse perspective projection of the point (u, v)

L = \{( \begin{matrix}x \\ y \\ z \end{matrix} ) |( \begin{matrix}x \\ y \\ z \end{matrix} ) = λ ( \begin{matrix}u \\ v \\ f \end{matrix} )\}

13.4.2 Line Segment with Known Direction Cosines and Known Length known:

• δ: line segment length

• ( \begin{matrix}b_{1} \\ b_{2} \\ b_{3} \end{matrix} ): line segment direction cosine

• ( \begin{matrix}u_{1} \\ v_{1} \end{matrix} ) , ( \begin{matrix}u_{2} \\ v_{2} \end{matrix} ): perspective projections of endpoints unknown:

• p_{1} = η_{1} ( \begin{matrix}u_{1} \\ v_{1} \\ f \end{matrix} ) , p_{2} = η_{2} ( \begin{matrix}u_{2} \\ v_{2} \\ f \end{matrix} ): 3D coordinates of endpoints

13.4.3 Collinear Points with Known Interpoint Distances known:

• ( \begin{matrix}u_{n} \\ v_{n} \end{matrix} ): perspective projections of nth collinear points, n = 0, ..., N − 1 • δ_{1}, δ_{2}, ..., δ_{N−1}: distance between (n + 1)th point and first point unknown:

• b = ( \begin{matrix}b_{1} \\ b_{2} \\ b_{3} \end{matrix} ): direction cosine of line

• p = ( \begin{matrix}p_{1} \\ p_{2} \\ p_{3} \end{matrix} ) , p, p + δ_{1}b, ..., p + δ_{N−1}b: 3D coordinates of points

13.4.4 N Parallel Lines known:

• L_{n} = \{( \begin{matrix}u \\ v \end{matrix} ) |( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}c_{n} \\ d_{n} \end{matrix} ) + η ( \begin{matrix}g_{n} \\ h_{n} \end{matrix} )\} , n = 1, ..., N: perspective projections

of nth parallel line unknown:

• b = ( \begin{matrix}b_{1} \\ b_{2} \\ b_{3} \end{matrix} ): direction cosine of line

13.4.5 N Lines Intersecting at a Point with Known Angles known:

• ( \begin{matrix}g \\ h \end{matrix} ): perspective projection of intersecting point

• M_{n} = \{( \begin{matrix}u \\ v \end{matrix} ) |( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}g \\ h \end{matrix} ) + η ( \begin{matrix}α_{n} \\ β_{n} \end{matrix} )\} , n = 1, ..., N: perspective projections

of nth intersecting line

• θ_{pq}: known angle between L_{p} and L_{q} unknown:

• L_{n} = \{( \begin{matrix}x \\ y \\ z \end{matrix} ) |( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}a \\ b \\ c \end{matrix} ) + λ ( \begin{matrix}i_{n} \\ j_{n} \\ k_{n} \end{matrix} )\} , n = 1, ..., N: 3D nth intersecting line

cos θ_{pq} = i_{p}i_{q} + j_{p}j_{q} + k_{p}k_{q}: known angle between line pair

13.4.6 N Intersecting Lines in a Known Plane known:

• ( \begin{matrix}g \\ h \end{matrix} ): perspective projection of intersecting point

• M_{n} = \{( \begin{matrix}u \\ v \end{matrix} ) |( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}g \\ h \end{matrix} ) + η ( \begin{matrix}α_{n} \\ β_{n} \end{matrix} )\} , n = 1, ..., N: perspective projections

of nth intersecting line

• Aa + Bb + Cc + D = 0: plane equation unknown:

• L_{n} = \{( \begin{matrix}x \\ y \\ z \end{matrix} ) |( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}a \\ b \\ c \end{matrix} ) + λ ( \begin{matrix}i_{n} \\ j_{n} \\ k_{n} \end{matrix} )\} , n = 1, ..., N: 3D nth intersecting line

Ai_{n} + Bj_{n} + Ck_{n} = 0

normal vector: perpedicular to direction cosine =====joke=====

13.4.7 Three Lines in a Plane with One Perpendicular to the Other Two known:

• M_{1} = \{( \begin{matrix}u \\ v \end{matrix} ) |( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}g_{1} \\ h_{1} \end{matrix} ) + η ( \begin{matrix}α_{1} \\ β_{1} \end{matrix} )\}: perspective projection of line

• M_{2} = \{( \begin{matrix}u \\ v \end{matrix} ) |( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}g_{2} \\ h_{2} \end{matrix} ) + η ( \begin{matrix}α_{2} \\ β_{2} \end{matrix} )\}: perspective projection of line

• M_{3} = \{( \begin{matrix}u \\ v \end{matrix} ) |( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}g_{3} \\ h_{3} \end{matrix} ) + η ( \begin{matrix}α_{3} \\ β_{3} \end{matrix} )\}: perspective projection of line

unknown: three lines in same plane, one perpendicular to other two

• L_{1} = \{( \begin{matrix}x \\ y \\ z \end{matrix} ) |( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} ) + λ ( \begin{matrix}k_{1} \\ k_{2} \\ k_{3} \end{matrix} )\}: 3D line

• L_{2} = \{( \begin{matrix}x \\ y \\ z \end{matrix} ) |( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}b_{1} \\ b_{2} \\ b_{3} \end{matrix} ) + λ ( \begin{matrix}k_{1} \\ k_{2} \\ k_{3} \end{matrix} )\}: 3D line

• L_{3} = \{( \begin{matrix}x \\ y \\ z \end{matrix} ) |( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}c_{1} \\ c_{2} \\ c_{3} \end{matrix} ) + λ ( \begin{matrix}m_{1} \\ m_{2} \\ m_{3} \end{matrix} )\}: 3D line

k_{1}m_{1} + k_{2}m_{2} + k_{3}m_{3} = 0: since L_{3} perpendicular to L_{1}, L_{2}

13.4.8 Point with Given Distance to a Known Point known:

• ( \begin{matrix}u \\ v \end{matrix} ): perspective projection of unknown point

• ( \begin{matrix}a \\ b \\ c \end{matrix} ): known 3D point

• ρ: distance between the two points unknown:

• ( \begin{matrix}i \\ j \\ k \end{matrix} ): direction cosine between two points \sqrt{(ηu − a)^{2} + (ηv − b)^{2} + (ηf − c)^{2}} = ρ

13.4.9 Point in a Known Plane known:

• ( \begin{matrix}u \\ v \end{matrix} ): perspective projection of unknown point

• Ax + By + Cz + D = 0: known plane equation where point lies unknown:

• ( \begin{matrix}a \\ b \\ c \end{matrix} ): 3D coordinate of the point solution:

• ( \begin{matrix}a \\ b \\ c \end{matrix} ) = ( \begin{matrix}−\frac{Du}{Au+Bv+Cf} \\ −\frac{Dv}{Au+Bv+Cf} \\ −\frac{Df}{Au+Bv+Cf} \end{matrix} ): 3D coordinate of the point

13.4.10 Line in a Known Plane known:

• Ax + By + Cz + D = 0: known plane equation where line lies

• M = \{( \begin{matrix}u \\ v \end{matrix} ) |( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}g \\ h \end{matrix} ) + η ( \begin{matrix}α \\ β \end{matrix} )\}: perspective projection of line

unknown:

• L = \{( \begin{matrix}x \\ y \\ z \end{matrix} ) |( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}a \\ b \\ c \end{matrix} ) + λ ( \begin{matrix}i \\ j \\ k \end{matrix} )\}: 3D line

Ai + Bj + Ck = 0: since line lies in plane Aa + Bb + Cc + D = 0: since line lies in plane

13.4.11 Angle known:

• M = \{( \begin{matrix}u \\ v \end{matrix} ) |( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}g \\ h \end{matrix} ) + η ( \begin{matrix}α \\ β \end{matrix} )\}: perspective projection of the unknown

line

• ( \begin{matrix}i_{0} \\ j_{0} \\ k_{0} \end{matrix} ): direction cosine for the known line • θ: angle between the 3D lines unknown:

• ( \begin{matrix}i_{1} \\ j_{1} \\ k_{1} \end{matrix} ): direction cosine for the unknown line

cos θ = i_{0}i_{1} + j_{0}j_{1} + k_{0}k_{1}: since θ is the angle between 3D lines

13.4.12 Parallelogram known:

• perspective projection of four corner points of a parallelogram unknown:

• ( \begin{matrix}A \\ B \\ C \end{matrix} ): normal to the plane where the parallelogram lies ( \begin{matrix}m_{1} \\ m_{2} \\ m_{3} \end{matrix} ) , ( \begin{matrix}n_{1} \\ n_{2} \\ n_{3} \end{matrix} ): direction cosines of two sides of parallelogram

( \begin{matrix}A \\ B \\ C \end{matrix} ) = \frac{( \begin{matrix}m_{1} \\ m_{2} \\ m_{3} \end{matrix} ) × ( \begin{matrix}n_{1} \\ n_{2} \\ n_{3} \end{matrix} )}{∥( \begin{matrix}m_{1} \\ m_{2} \\ m_{3} \end{matrix} ) × ( \begin{matrix}n_{1} \\ n_{2} \\ n_{3} \end{matrix} )∥}

13.4.13 Triangle with One Vertex Known known:

• ( \begin{matrix}u_{1} \\ v_{1} \end{matrix} ) , ( \begin{matrix}u_{2} \\ v_{2} \end{matrix} ) , ( \begin{matrix}u_{3} \\ v_{3} \end{matrix} ): perspective projection of three vertices

• ( \begin{matrix}x_{1} \\ y_{1} \\ z_{1} \end{matrix} ): one known 3D vertex of the three vertices

• S_{12}, S_{13}, S_{23}: known length of the triangle in 3D

unknown:

• ( \begin{matrix}x_{2} \\ y_{2} \\ z_{2} \end{matrix} ) , ( \begin{matrix}x_{3} \\ y_{3} \\ z_{3} \end{matrix} ): two unknown 3D vertices of the three vertices

(x_{2} − x_{1})^{2} + (y_{2} − y_{1})^{2} + (z_{2} − z_{1})^{2} = S_{12}^{2}

(x_{3} − x_{1})^{2} + (y_{3} − y_{1})^{2} + (z_{3} − z_{1})^{2} = S_{13}^{2} (x_{2} − x_{3})^{2} + (y_{2} − y_{3})^{2} + (z_{2} − z_{3})^{2} = S_{23}^{2}

x_{2} = \frac{u_{2}z_{2}}{f}

y_{2} = \frac{v_{2}z_{2}}{f}

x_{3} = \frac{u_{3}z_{3}}{f}

y_{3} = \frac{v_{3}z_{3}}{f}

13.4.14 Triangle with Orientation of One Leg Known known:

• ( \begin{matrix}u_{1} \\ v_{1} \end{matrix} ) , ( \begin{matrix}u_{2} \\ v_{2} \end{matrix} ) , ( \begin{matrix}u_{3} \\ v_{3} \end{matrix} ): perspective projection of three vertices • S_{12}, S_{13}, S_{23}: known length of the triangle in 3D

• ( \begin{matrix}i_{1} \\ j_{1} \\ k_{1} \end{matrix} ): known direction cosines between the first two vertices unknown:

• ( \begin{matrix}x_{1} \\ y_{1} \\ z_{1} \end{matrix} ) , ( \begin{matrix}x_{2} \\ y_{2} \\ z_{2} \end{matrix} ) , ( \begin{matrix}x_{3} \\ y_{3} \\ z_{3} \end{matrix} ): three unknown 3D vertices

(x_{2} − x_{1})^{2} + (y_{2} − y_{1})^{2} + (z_{2} − z_{1})^{2} = S_{12}^{2} (x_{3} − x_{1})^{2} + (y_{3} − y_{1})^{2} + (z_{3} − z_{1})^{2} = S_{13}^{2} (x_{2} − x_{3})^{2} + (y_{2} − y_{3})^{2} + (z_{2} − z_{3})^{2} = S_{23}^{2}

( \begin{matrix}x_{1} \\ y_{1} \\ z_{1} \end{matrix} ) = ( \begin{matrix}x_{2} \\ y_{2} \\ z_{2} \end{matrix} ) + S_{12} ( \begin{matrix}i_{1} \\ j_{1} \\ k_{1} \end{matrix} )

13.4.15 Triangle: three-point spatial resection problem in photogrammetry known:

• ( \begin{matrix}u_{1} \\ v_{1} \end{matrix} ) , ( \begin{matrix}u_{2} \\ v_{2} \end{matrix} ) , ( \begin{matrix}u_{3} \\ v_{3} \end{matrix} ): perspective projection of three vertices

• S_{12}, S_{13}, S_{23}: known length of the triangle in 3D unknown:

• ( \begin{matrix}x_{1} \\ y_{1} \\ z_{1} \end{matrix} ) , ( \begin{matrix}x_{2} \\ y_{2} \\ z_{2} \end{matrix} ) , ( \begin{matrix}x_{3} \\ y_{3} \\ z_{3} \end{matrix} ): three unknown 3D vertices

four solutions

(x_{2} − x_{1})^{2} + (y_{2} − y_{1})^{2} + (z_{2} − z_{1})^{2} = S_{12}^{2}
(x_{3} − x_{1})^{2} + (y_{3} − y_{1})^{2} + (z_{3} − z_{1})^{2} = S_{13}^{2}
(x_{2} − x_{3})^{2} + (y_{2} − y_{3})^{2} + (z_{2} − z_{3})^{2} = S_{23}^{2}

u_{n} = \frac{fx_{n}}{z_{n}} n = 1, 2, 3

v_{n} = \frac{fy_{n}}{z_{n}} n = 1, 2, 3

13.4.16 Determining the Principal Point by Using Parallel Lines principal point: point through which the optic axis passes principal point: so far assumes origin of image reference frame known:

• M_{n} = \{( \begin{matrix}u \\ v \end{matrix} ) |( \begin{matrix}u \\ v \end{matrix} ) = ( \begin{matrix}g \\ h \end{matrix} ) + η ( \begin{matrix}α_{n} \\ β_{n} \end{matrix} )\} , n = 1, ..., N: perspective projection

of nth parallel line unknown:

• ( \begin{matrix}Δu \\ Δv \end{matrix} ): coordinates of the principal point

13.5 Circles known:

• perspective projection of a circle having known radius d_{0} unknown:

• plane on which the circle lies

• the 3D center of the circle =====Oldie 33:70=====

13.6 Range from Structured Light structured light: active visual sensing technique upon perspective geometry structured light: controlled light source with regular pattern onto scene regular pattern: stripes, grid, ... light striping and a typical arrangement =====Ballard and Brown, Computer Vision, Fig. 2.25===== intensity and range images =====Ballard and Brown, Computer Vision, Fig. 2.26===== Two light sources with cylindrical lenses produce sheets of light that intersect in a line lying on the surface of a conveyor belt. A camera above the belt is aimed so that this line is imaged on a linear array of photosensors. When there is no object present, all the sensor cells are brightly illuminated. When part of an object interrupts the incident light, the corresponding region on the linear array is darkened. The motion of the belt scans the object past the sensor, generating the second image dimension. =====Horn, Robot Vision, Fig. 5.4=====

13.7 Cross-Ratio cross-ratio: of perspective projection of 4 collinear points, takes same value

13.7.1 Cross-Ratio Definitions and Invariance four collinear points: p + λ_{1}b, p + λ_{2}b, p + λ_{3}b, p + λ_{4}b q, r: centers of perspectivity for two projection images =====Fig. 13.7=====

Let p = ( \begin{matrix}p_{1} \\ p_{2} \end{matrix} ) , b = ( \begin{matrix}b_{1} \\ b_{2} \end{matrix} ). by perspective projection equations

u_{n} = f \frac{p_{1} + λ_{n}b_{1}}{p_{2} + λ_{n}b_{2}} n = 1, 2, 3, 4

u_{i} − u_{j} = f \frac{p_{1} + λ_{i}b_{1}}{p_{2} + λ_{i}b_{2}} − f \frac{p_{1} + λ_{j}b_{1}}{p_{2} + λ_{j}b_{2}} = \frac{f(p_{2}b_{1} − p_{1}b_{2})(λ_{i} − λ_{j})}{(p_{2} + λ_{i}b_{2})(p_{2} + λ_{j}b_{2})}

cross-ratio:

γ(u_{1}, u_{2}, u_{3}, u_{4}) = \frac{(u_{1} − u_{2})(u_{3} − u_{4})}{(u_{1} − u_{3})(u_{2} − u_{4})} = \frac{(λ_{1} − λ_{2})(λ_{3} − λ_{4})}{(λ_{1} − λ_{3})(λ_{2} − λ_{4})}

cross-ratio: independent of reference frame, point p, direction cosine b cross-ratio: depends only on directed distance of collinear points

13.7.2 Only One Cross-Ratio each of 4! cross-ratios is a function of cross-ratio γ(u_{1}, u_{2}, u_{3}, u_{4})

γ(u_{1}, u_{2}, u_{3}, u_{4}) = γ(u_{2}, u_{1}, u_{4}, u_{3}) = γ(u_{3}, u_{4}, u_{1}, u_{2}) = γ(u_{4}, u_{3}, u_{2}, u_{1})

γ(u_{1}, u_{2}, u_{4}, u_{3}) = γ(u_{2}, u_{1}, u_{3}, u_{4}) = γ(u_{4}, u_{3}, u_{1}, u_{2}) = γ(u_{3}, u_{4}, u_{2}, u_{1})

= \frac{−γ(u_{1}, u_{2}, u_{3}, u_{4})}{1 − γ(u_{1}, u_{2}, u_{3}, u_{4})}

γ(u_{1}, u_{4}, u_{3}, u_{2}) = γ(u_{4}, u_{1}, u_{2}, u_{3}) = γ(u_{2}, u_{3}, u_{4}, u_{1}) = γ(u_{3}, u_{2}, u_{1}, u_{4})

= 1 − γ(u_{1}, u_{2}, u_{3}, u_{4})

γ(u_{1}, u_{3}, u_{2}, u_{4}) = γ(u_{3}, u_{1}, u_{4}, u_{2}) = γ(u_{4}, u_{2}, u_{3}, u_{1}) = γ(u_{2}, u_{4}, u_{1}, u_{3})

= \frac{1}{γ(u_{1}, u_{2}, u_{3}, u_{4})}

γ(u_{1}, u_{3}, u_{4}, u_{2}) = γ(u_{3}, u_{1}, u_{2}, u_{4}) = γ(u_{2}, u_{4}, u_{3}, u_{1}) = γ(u_{4}, u_{2}, u_{1}, u_{3})

= \frac{1}{1 − γ(u_{1}, u_{2}, u_{3}, u_{4})}

γ(u_{1}, u_{4}, u_{2}, u_{3}) = γ(u_{4}, u_{1}, u_{3}, u_{2}) = γ(u_{2}, u_{3}, u_{1}, u_{4}) = γ(u_{3}, u_{2}, u_{4}, u_{1})

= \frac{1 − γ(u_{1}, u_{2}, u_{3}, u_{4})}{−γ(u_{1}, u_{2}, u_{3}, u_{4})}

13.7.3 Cross-Ratio in Three Dimensions The cross-ratio derived from 1D perspective projections in 2D world can be generalized to 2D perspective projections in 3D world. five co-planar points γ_{23}: cross-ratio for the line segment p_{2}p_{3} and 0 < λ_{1} < λ_{2} < L_{1}

γ_{23} = \frac{λ_{1}(L_{1} − λ_{2})}{λ_{2}(L_{1} − λ_{1})}

γ_{25}: cross-ratio for the line segment p_{2}p_{5} and 0 < η_{1} < η_{2} < L_{2}

γ_{25} = \frac{η_{1}(L_{2} − η_{2})}{η_{2}(L_{2} − η_{1})}

=====Fig. 13.8=====

13.7.4 Using Cross-Ratios cross-ratios: to aid in establishing correspondences =====joke=====

tentative term project problems, (30%) total grade: submit one page in English explaining method, steps, expected results submit report in a month; report progress every other week all right to be the same problem with Master’s thesis objective: a working prototype with new, original, novel ideas objective: not just literature survey objective: not just straightforward implementation of existing algorithms objective: all right to modify existing algorithms 1. Neural Network, Gonzalez, Sec. 9.3.3, p. 595 =====Gonzalez, Digital Image Processing, Fig. 9.14=====

2. Fuzzy Logic

3. Image Compression: JPEG (Joint Photographic Experts Group), MPEG (Moving Picture Experts Group), JPEG 2000, Gonzalez, Sec. 6.6, p. 389

=====Gonzalez, Digital Image Processing, Plate X=====

4. wavelet transform

5. segmentation based on texture, Gonzalez, p. 594 =====Gonzalez, Digital Image Processing, Fig. 9.13=====

6. optical character reading: a, b, c, d, ... 0, 1, 2, ..... =====fonts=====

7. stereo vision, Nalwa, Chapter 7 =====Nalwa, A Guided Tour of Computer Vision, Fig. 7.9===== =====Nalwa, A Guided Tour of Computer Vision, Fig. 7.10===== 8. handwriting recognition: zip code; on-line, off-line Chinese characters ... =====zip===== =====Chinese=====

9. histogram specification: Gonzalez, p. 182, Sec. 4.2.2 =====Gonzalez, Digital Image Processing, Fig. 4.14=====

10. Homomorphic filtering: Gonzalez, Sec. 4.4.3 =====Gonzalez, Digital Image Processing, Fig. 4.41===== =====Gonzalez, Digital Image Processing, Fig. 4.42===== 11. real-time counting number of cars and their sizes.

12. calculating the sizes of stones, cells, cell nucleus. =====t pebbles.im=====

13. trademark resemblance, semi-automatic similarity classification =====trademark.im=====

14. car plate recognition.

15. structured light 3-D reconstruction. Horn, p. 95 =====Horn, Robot Vision, Fig. 5.4===== =====Ballard and Brown, Computer Vision, Fig. 2.25===== =====Ballard and Brown, Computer Vision, Fig. 2.26===== 16. object classification with moments invariant to rotation,

scaling, translation, Gonzalez, p. 514, Sec. 8.3.4 =====Gonzalez, Digital Image Processing, Eq. 8.3-14===== =====Gonzalez, Digital Image Processing, Fig. 8.24===== 17. photometric stereo, Sec. 12.3, p. 16, Eq. 12.14

18. shape from focus, defocus, Sec. 12.4.1, p. 21

19. shape from polarization, Sec. 12.5, p. 22

20. shape from shading, Horn, p. 226 =====Horn, Robot Vision, Fig. 10.18===== =====Horn, Robot Vision, Fig. 10.19===== 21. shape from texture, Nalwa, p. 199 =====Nalwa, A Guided Tour of Computer Vision, Fig. 6.1===== =====Nalwa, A Guided Tour of Computer Vision, Fig. 6.6===== 22. solving correspondence problem or optic flow field =====truck.im=====

23. motion and shape parameter recovery =====truck.im=====

24. segmentation of newspaper, documents into title, figure, caption,.... =====magazine.im=====

25. optical distortion correction, Nalwa, p. 46 =====Nalwa, A Guided Tour of Computer Vision, Fig. 2.13===== 26. line labeling of 2D line drawing of 3D objects, Sec. 17.5, p. 404 =====Fig. 17.13=====

27. Computer Tomography: 3D image reconstruction from 2D projections =====Cho et al., Foundations of Medical Imaging, Fig. 6.6===== =====Wicke, Atlas of Radiologic Anatomy, Fig. 159===== =====Wicke, Atlas of Radiologic Anatomy, Fig. 160=====

28. road surface inspection: cracks, holes, ...

29. traffic counting: number of trucks, cars, motorcycles, ...

30. finger-print validation =====fingerprint.im===== 31. face recognition =====face=====

32. use robot to pick stones out of a bin =====stone.im=====

33. digital morphing =====morphing.im=====

34. model-based diagnosis =====thorax.im=====

35. automatic identification and classification of video scenes for indexing

36. automatic break detection or video partitioning or scene change detection

37. automatic full-video search for objects of interest e.g. find all frames which contain frogs

38. creating video or image database with functions such as efficient querying, indexing, retrieval, browsing

39. recognition of video content invariant to viewing conditions e.g. find all other shots of this scene

40. printed music sheet recognition and translation into MIDI format file =====music.im=====

41. 360 degree image from several pictures (alignment, color interpolation, panorama)

42. wafer defect inspection =====wafer.defect===== 43. wafer critical dimension measurement =====Elliott, Integrated Circuit Fabrication Technology, Fig. 8.54===== 44. IC pin inspection: coplanarity of surface mount device

colinearity of dual-in-line package =====IC.pin=====

45. IC mark printing inspection: smear, contract, scratch, ... =====IC.mark=====

46. electrical contact point inspection =====electrical.contact=====

47. digital watermarking: viewing but no printing due to copyright

48. auto focus in digital camera (edge, high frequency, active, passive)

49. auto exposure in digital camera (shutter speed, aperture diameter, AGC: Auto Gain Control)

50. auto white balance in digital camera (candle light, fluorescent light)

51. color management: sRGB: standard Red, Green, Blue

52. 640X480 ⇒ 1280X960 from single image

53. super resolution: 640X480 ⇒ 1280X960 from multiple images

54. video stabilization for digital camcorder

55. Sony DSC F828 Digital Camera Contest (RGBE: Red, Green, Blue, Emerald)

Project due April 12: camera calibration i.e compute #pixels/mm object displacement calculate field of view in angles. calculate and compare with theoretical values. use lens of focal length: 16mm, 25mm, 50mm object displacement of: 1mm, 5mm, 10mm, 20mm object distance of: 0.5m, 1m, 2m camera parameters: 8mm× 6mm ⇒ 512×485? Are pixels square or rectangular?