The iterative formulas for solving eq. (3.115) and eq. (3.116) are

$p^{\left(n+1\right)}={\overline{p}}^{\left(n\right)}+\frac{1}{\lambda }\left[E\left(x,y\right)-R\left(p^{\left(n\right)},q^{\left(n\right)}\right)\right]\frac{\partial R^{\left(n\right)}}{\partial p}\left(3.117\right)$

$q^{\left(n+1\right)}={\overline{q}}^{\left(n\right)}+\frac{1}{\lambda }\left[E\left(x,y\right)-R\left(p^{\left(n\right)},q^{\left(n\right)}\right)\right]\frac{\partial R^{\left(n\right)}}{\partial q}\left(3.118\right)$

Example 3.11 The flowchart for solving the image brightness constraint equation.

The flowchart for solving Eqs (3.117) and (3.118) is shown in Figure 3.33. It in principle can be used for solving eqs. (3.53) and (3.54), too.

Example 3.12 Illustration of the shape from shading.

Two illustrations of shape from shading are shown in Figure 3.34. Figure 3.34(a) is an image of a ball and Figure 3.34(b) is the corresponding surface orientation map. Figure 3.34(c) is another image of a ball and Figure 3.34(d) is the corresponding surface orientation map.

3.4Texture and Surface Orientation

Shape from texture has been studied for quite some time, Gibson (1950). In the following, the estimation of the surface orientation based on texture distortion is discussed.

3.4.1Single Imaging and Distortion

The boundary of an object is formed by a set of consecutive line segments. When the lines in a 3-D space are projected on a 2-D image plane, several distortions can be produced. The projection of a point is still a point. The projection of a line depends on the projection of the points forming the line. Suppose that the two end points of a line are denoted W1 = [X1 Y1 Z1]T and W2 = [X2 Y2 Z2]T, and the points between them are (0 < p < 1)

$p{W}_1+\left(1-p\right)W_2=p\left[\begin{array}{c}{X}_1\\ Y_1\\ Z_1\end{array}\right]+\left(1-p\right)\left[\begin{array}{c}{X}_2\\ Y_2\\ Z_2\end{array}\right]\left(3.119\right)$

Using the homogenous coordinates, the two end points can be represented by PW1 = [kX1 kY1 kZ1t1]T, PW2 = [kX2 kY2 kZ2t2]T, where t1 = k(f − Z1)/λ, t2 = k(f − Z2)/λ. The points on the line are represented by (0 < p < 1)

$p\left[p{W}_1+\left(1-p\right)W_2\right]=p\left[\begin{array}{c}k{X}_1\\ k{Y}_1\\ k{Z}_1\\ t_1\end{array}\right]+\left(1-p\right)\left[\begin{array}{c}k{X}_2\\ k{Y}_2\\ k{Z}_2\\ t_2\end{array}\right]\left(3.120\right)$

Their image plane coordinates are (0 ≤ p ≤ 1)

$w={\left[x,y\right]}^T={\left[\frac{p{X}_1+\left(1-p\right)X_2}{p{t}_1+\left(1-p\right)t_2}\frac{p{Y}_1+\left(1-p\right)Y_2}{p{t}_1+\left(1-p\right)t_2}\right]}^T\left(3.121\right)$

In the above, the projection results are represented by using p. On the other hand, the two end points on the image planes are w1 = [λX1/(λ − Z1) λY1/(λ − Z1)]T, w2 = [λX2/(λ–Z2) λY2/(λ–Z2)]t, and the points on the line can be represented by (0 < q < 1)

$q{w}_1+\left(1-q\right)w_2=q\left[\begin{array}{c}\frac{\lambda X_1}{\lambda -Z_1}\\ \frac{\lambda Y_1}{\lambda -Z_1}\end{array}\right]+\left(1-q\right)\left[\begin{array}{c}\frac{\lambda X_2}{\lambda -Z_2}\\ \frac{\lambda Y_2}{\lambda -Z_2}\end{array}\right]\left(3.122\right)$

Their image plane coordinates are (represented by using q, with 0 ≤ q ≤ 1)

$w={\left[xY\right]}^T=\left[q\frac{\lambda X_1}{\lambda -Z_1}+\left(1-q\right)\frac{\lambda X_2}{\lambda -Z_2}q\frac{\lambda Y_1}{\lambda -Z_1}+\left(1-q\right)\frac{\lambda Y_2}{\lambda -Z_2}\right]\left(3.123\right)$

Since the projection results represented using p are the image coordinates represented using q, eq. (3.121) and eq. (3.123) should be equal, which is given by

$p=\frac{q{t}_2}{q{t}_2+\left(1-q\right)t_1}\left(3.124\right)$

$q=\frac{p{t}_1}{p{t}_1+\left(1-p\right)t_2}\left(3.125\right)$

The point represented using p in a 3-D space corresponds to only one point represented using q in a 2-D image plane. The projection (except the orthogonal projection) result of a line from a 3-D space to a 2-D image plane is still a line (length can be different). For an orthogonal projection, the result would be a point.

Consider now the distortion of parallel lines. A point (X, Y, Z)on a 3-D line is

$\left[\begin{array}{c}X\\ Y\\ Z\end{array}\right]=\left[\begin{array}{c}{X}_0\\ Y_0\\ Z_0\end{array}\right]+k\left[\begin{array}{c}a\\ b\\ c\end{array}\right]\left(3.126\right)$

where (X0, Y0, Z0) represent the start points, (a, b, c) are the direction cosines and k is a coefficient. For a set of parallel lines, they have the same (a, b, c), but different (X0, Y0, Z0). Substituting eq. (3.126) into eqs. (2.25) and (2.26) of Volume I of this book set yields

$x=\lambda \frac{\left(X_0+ka-D_x\right)\cos \gamma +\left(Y_0+kb-D_{\gamma }\right)\sin \gamma }{-\left(X_0+ka-D_x\right)\sin \alpha \sin \gamma +\left(Y_0+kb-D_y\right)\sin \alpha \cos \gamma -\left(Z_0+kc-D_z\right)\cos \alpha +\lambda }\left(3.127\right)$

$y=\lambda \frac{-\left(X_0+ka-D_x\right)\sin \gamma \cos \alpha +\left(Y_0+kb-D_y\right)\cos \alpha \cos \gamma +\left(Z_0+kc-D_z\right)\sin \alpha }{-\left(X_0+ka-D_x\right)\sin \alpha \sin \gamma +\left(Y_0+kb-D_y\right)\sin \alpha \cos \gamma -\left(Z_0+kc-D_z\right)\cos \alpha +\lambda }\left(3.128\right)$

When the line extends on both sides to infinity, k = ±∞, eq. (3.127) and eq. (3.128) are simplified to

$x_{\infty }=\lambda \frac{\alpha \cos \gamma +b\sin \gamma }{-a\sin \alpha \sin \gamma +b\sin \alpha \cos \gamma -c\cos \alpha }\left(3.129\right)$

$y_{\infty }=\lambda \frac{-\alpha \sin \gamma \cos \alpha +b\cos \alpha \cos \gamma +c\sin \alpha }{-a\sin \alpha \sin \gamma +b\sin \alpha \cos \gamma -c\cos \alpha }.\left(3.130\right)$

It is seen that the projection of parallel lines depends only on (a, b, c), but not on (X0, Y0, Z0). The parallel lines having the same (a, b, c) will cross a point after infinitive extension. This point is called the vanishing point and will be discussed below.

3.4.2Recover Orientation from Texture Gradient

The surface orientation can be determined with the help of surface texture, and particularly with the help of the appearance change of textures. The principle of the structural techniques (Section 12.3) is adopted here. The texture image is often decomposed into primitives, called texels (for texture elements).

When using the surface texture to determine the orientation of a surface, it must consider the imaging process. In this process, the original texture structure can be changed on the projection to the image. This change depends on the orientation of the surface, and carries the 3-D information of the surface orientation. The change of textures can be described by the texture gradients and classified into three groups. The methods for recovering orientation from textures can also be classified into three groups, as shown in Figure 3.35.

3.4.2.1Texel Change in Size

In perspective projection, texels that have different distances from viewers will change their apparent size after projection to the image, as shown in Figure 3.35(a). The direction of the maximum rate of the change of the projected texel size is the direction of the texture gradient. Suppose the image plane is in superposition with the paper and the view direction is pointed toward the inside. The direction of the texture gradient depends on the angle of the texel around the camera line of sight, and the magnitude of the texture gradient indicates how much the plane is tilted with respect to the camera.

Example 3.13 Depth provided by texel change in size.

Figure 3.36 presents two pictures showing the depth provided by the texel change in size. There are many pedals (texels) in Figure 3.36(a), which produce the depth impression of a scene with the gradual change of size from the front to the back. There are many columns and windows (texels) on the building in Figure 3.36(b), whose size change produces the depth impression and helps viewers to know the farthest part of the building.

3.4.2.2Texel Change in Shape

The shape of a texel after projection may change. If the original shape of the texels is known, the surface orientation can be induced by the texel change in shape. The orientation of surface is determined by two angles. For example, texture formed by circles will become ellipses if it is put on a tilted plane, as shown in Figure 3.35(b). Here, the direction of the principal axis specifies the angle around the camera axis, while the ratio (aspect ratio) of the major principal axis and the minor principal axis specifies the tilted angle with respect to the camera line of sight.

Suppose that the plane equation of circular texels is

$ax+by+cz+d=0\left(3.131\right)$

The circle can be viewed as the cross-line between the plane and a sphere that has the equation

$x^2+y^2+z^2=r^2\left(3.132\right)$

Combining eq. (3.131) and eq. (3.132) yields

$\frac{a^2+c^2}{c^2}{x}^2+\frac{b^2+c^2}{c^2}{y}^2+\frac{2adx+2bdy+2abdx}{c^2}=r^2-\frac{a^2}{c^2}\left(3.133\right)$

This is an ellipse equation and can be further written as

$\left[\left(a^2+c^2\right)x+\frac{ad}{a^2+c^2}\right]+{\left[\left(a^2+c^2\right)y+\frac{bd}{b^2+c^2}\right]}^2+2abxy=c^2{r}^2-{\left[\frac{a^2{d}^2+b^2{d}^2}{a^2+c^2}\right]}^2\left(3.134\right)$

From eq. (3.134), the center point’s coordinates, major and minor principal axes can be determined. Based on these parameters, the rotation angle and tilted angle can be calculated.

Another method used to judge the deformation of circular texels is to compute the major and minor principal axes of the ellipses. Look at Figure 3.37. The angle between the texture plane and the y-axis is α. In the image obtained, not only the circular texels become ellipses but also the density in the upside is higher than the downside (forming density gradient).

If the original diameter of the circle is D, for the circle in the center, the major and minor principal axes are

$D_{\text{major}}\left(0,0\right)=\lambda \frac{D}{Z}\left(3.135\right)$

$D_{\min \text{or}}\left(0,0\right)=\lambda \frac{D}{Z}\cos \alpha \left(3.136\right)$

where λ is the focus of the camera and Z is the distance from object to lens.

Consider texels not on the axis of the camera, such as the bright ellipses in Figure 3.37. If the Y-coordinate of the texel is y, the angle between the line from the origin to the texel and the Z-axis is θ, then, Jain (1995)

$D_{\text{major}}\left(0,y\right)=\lambda \frac{D}{Z}\left(1-\tan \theta \tan \alpha \right)\left(3.137\right)$

$D_{\min \text{or}}\left(0,y\right)=\lambda \frac{D}{Z}\cos \alpha {\left(1-\tan \theta \tan \alpha \right)}^2\left(3.138\right)$

The aspect ratio is cos α(1 − tan θ tan α), which will decrease with the increase of θ.

3.4.2.3Texel Change in Spatial Relation

If the texture is composed of a regular grid of texels, then the surface orientation information can be recovered by computing the vanishing point. For a projection map, the vanishing point is produced by the projection of the texels at infinity to the image plane. In other words, the vanishing point is the pool of parallel lines at infinity.

Example 3.14 The regular grid of texels and the vanishing point

Figure 3.38(a) shows a projective map of a cube with parallel grids on the surface; Figure 3.38(b) illustrates the vanishing points of three surfaces.

By using two vanishing points obtained from the same regular grid of texels, the direction of the surface can be determined. The straight line that lies on the two vanishing points is called the vanishing line. The direction of the vanishing line indicates the angle that a texel is around the axis of the camera, while the cross-point of the vanishing line with x = 0 indicates the tilted angle of the texel with respect to the camera line of sight, as shown in Figure 3.35(c).

A summary of the three methods for determining the surface orientation is given in Table 3.1.

3.4.3Determination of Vanishing Points

If a texture is composed of line segments, the vanishing points can be determined with the help of Figure 3.39. In Figure 3.39(a), a line is represented by

$\lambda =x\cos \theta +y\sin \theta \left(3.139\right)$

Denote “” as a transform from one set to another set. The transform {x, y} {λ, θ} maps a line in an image space XY to a point in a parametric space ΛΘ. The set of lines in the XY space that has the same vanishing point (xv, yv) will be projected onto a circle in the ΛΘ space. Taking $\lambda =\sqrt{x^2+y^2}$ and θ = arctan {y/x} into the following equation yields

$\lambda \text{=}{x}_y\cos \theta +y_y\sin \theta \left(3.140\right)$

Writing the result in the Cartesian system yields

${\left(x-\frac{x_v}{2}\right)}^2+{\left(y-\frac{y_v}{2}\right)}^2={\left(\frac{X_v}{2}\right)}^2+{\left(\frac{Y_v}{2}\right)}^2\left(3.141\right)$

Equation (3.141) represents a circle with a radius $\lambda =\sqrt{{\left(x_v/2\right)}^2+{\left(y_v/2\right)}^2}$ and the center (xv/2, yv/2), as shown in Figure 3.39(b). This circle is the trace of the projection of all lines, which have (xv, yv) as the vanishing points, into the space ΛΘ.

The above method for determining the vanishing point has two drawbacks: One is that detecting a circle is more complicated than detecting a line, requiring more computation; the other is when xv → ∞ or yv → ∞, it will have λ → ∞. To overcome these problems, an alternative transform {x, y} {k/λ, θ} can be used, where k is a constant. In this case, eq. (3.140) becomes

$k/\lambda =x_v\cos \theta +y_v\sin \theta \left(3.142\right)$

Mapping eq. (3.142) into the Cartesian system (s = λ cos θ, t = λ sin θ) yields

$k=x_{v}s+y_{v}t\left(3.143\right)$

This is a line equation. The vanishing point at infinity is projected to the origin, and all lines that have the same vanishing point (xv, yv) correspond to a line in the ST space, as shown in Figure 3.39(c). The slope of this line is −yv/xv, so this line is perpendicular to the vector from the origin to the vanishing point (xv, yv), and has a distance from the origin $k/\sqrt{x_v^2+y_v^2}.$ Another Hough transform can be used to detect this line. Take the ST space as the original space and denote the line in the new Hough space RW. The line in the ST space corresponds to a point in the RW space, as shown in Figure 3.39(d), with the location coordinates

$r=\frac{k}{\sqrt{x_v^2+y_v^2}}\left(3.144\right)$

$w=\arctan \left\{\frac{y_v}{x_v}\right\}\left(3.145\right)$

From eq. (3.144) and eq. (3.145), the coordinates of vanishing points can be calculated by

$x_v=\frac{k^2}{r^2\sqrt{1+{\tan }^{2}w}}\left(3.146\right)$

$y_v=\frac{k^2\tan w}{r^2\sqrt{1+{\tan }^{2}w}}\left(3.147\right)$

3.5Depth from Focal Length

The depth of field of a thin lens depends on its focal length λ. The thin lens equation can be derived from Figure 3.40. A ray from object point P parallel to the optical axis passes through the lens and reaches the image plane. From the geometry of Figure 3.40, the thin lens equation can be derived as

$\frac{1}{\lambda }=\frac{1}{d_0}+\frac{1}{d_1}\left(3.148\right)$

where do and di are the distances from the object and from the image to the lens, respectively.

When the projection of an object is in perfect focus on the image plane, a clear image will be captured. If moving P along the optical axis, it will be out of focus. The captured image becomes a blur disk as it also moves along the optical axis. The diameter of the blur disk depends on both the resolution and the depth of field of the camera.

Suppose that the aperture of a lens is A and the diameter of the blur disk is D. Consider the relation between D and the depth of field. Assume that D = 1 (unit is pixel) can be tolerated, what are the nearest do(do1) and farthest do(do2)? Note that at the nearest do, the distance between image and lens is di1, while at the farthest do, the distance between image and lens is di2.

According to Figure 3.40, at the nearest do,

$d_{11}=\frac{A+D}{A}{d}_1\left(3.149\right)$

From eq. (3.148), the nearest object distance is

$d_{\text{o1}}=\frac{\lambda d_{11}}{d_{11}-\lambda }\left(3.150\right)$

Substituting eq. (3.149) into eq. (3.150) yields

$d_{\text{o1}}=\frac{\lambda \frac{A+D}{A}{d}_1}{\frac{A+D}{A}{d}_1-\lambda }=\frac{d_0\lambda \left(A+D\right)}{A\lambda +D{d}_0}\left(3.151\right)$

Similarly, the farthest object distance is

$d_{\text{o2}}=\frac{\lambda \frac{A-D}{A}{d}_1}{\frac{A-D}{A}{d}_1-\lambda }=\frac{d_0\lambda \left(A-D\right)}{A\lambda -D{d}_0}\left(3.152\right)$

The depth of field should be defined as the difference between the farthest and nearest planes for the given imaging parameters and limiting D. In this case,

$\Delta d_0=d_{\text{o2}}-d_{\text{o1}}=\frac{2AD{d}_o\lambda \left(d_o-\lambda \right)}{{\left(D{d}_o\right)}^2-{\left(A\lambda \right)}^2}\left(3.153\right)$