# Shape-from-shading for Surfaces Applicable to Planes

Jean-Denis Durou, Jean-Marc Schlenker

► To cite this version:

Jean-Denis Durou, Jean-Marc Schlenker. Shape-from-shading for Surfaces Applicable to Planes. 1st International Workshop on Photometric Analysis For Computer Vision - PACV 2007, Oct 2007, Rio de Janeiro, Brazil. pp.1-8. inria-00264881

HAL Id: inria-00264881

https://inria.hal.science/inria-00264881

Submitted on 18 Mar 2008

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Shape-from-shading for Surfaces Applicable to Planes

Jean-Denis DUROU

IRIT, UMR CNRS 5505, Toulouse, France

durou@irit.fr

Jean-Marc SCHLENKER

IMT, UMR CNRS 5219, Toulouse, France

schlenker@math.ups-tlse.fr

## Abstract

Under the classical assumptions of shape-from-shading, we show that the image of any “applicable surface” (surface applicable to a plane) is also the image of a 1-dimensional manifold of applicable surfaces, provided the image contains no singular point. Moreover, we show that the knowledge of a normal in the image suffices to reconstruct the whole shape of the surface, since the problem can be reformulated as an ordinary differential equation w.r.t. the normal, in this case. The usefulness of this theoretical result to document image analysis is straightforward.

## 1. Introduction

Among various computer vision techniques for 3D-reconstruction, shape-from-shading (SFS) is sometimes considered as a “toy problem”, since its results are unsatisfactory on real images [25, 8]. As for photometric stereo, a main problem of SFS is to get the reflectance properties of the materials which constitute the scene. However, even if this knowledge is available, a second problem with SFS is ill-posedness. In the definition by Hadamard, a problem is well-posed if it has a unique solution and if the solution is stable w.r.t. a small perturbation in the data. Many inverse problems are ill-posed because of instability.

In this paper, we focus on the question of uniqueness of the solution. More precisely, we show that for a class of surfaces, namely the applicable surfaces which contain no singular point, there exist a 1-dimensional manifold of solutions to the SFS problem. Moreover, the knowledge of the normal to the surface at one point is enough to compute the whole 3D-shape. This result is of great interest in the framework of document image analysis.

In Section 2, we recall the classical assumptions of SFS as well as its basic model, and we tackle the question of uniqueness of the solution. In Section 3, we show that the image of an applicable surface without singular point is also that of a 1-dimensional manifold of applicable surfaces. This is the theoretical contribution of the paper. In Section 4, a straightforward application of this result con-

sists in reconstructing the 3D-shape of a curved document from its shading. Finally, Section 5 concludes our study and states several perspectives.

## 2. Shape-from-shading and Well-posedness

### 2.1. Shape-from-shading Model

We attach to the camera a three-dimensional coordinate system $Oxyz$, such that $Oxy$ coincides with the image plane $H$. Let us denote $\mathbf{x} = (x, y, z)$ the current point of a scene surface. Under the assumption of orthographic projection on $H$, the visible part of the scene is a graph $z = u(x, y)$. The SFS problem consists in computing the function $u$ for $(x, y) \in \Omega \subset \mathbb{R}^2$, from one image only. As is well known [12], it can be modeled by the “image irradiance equation”:

$$R(\mathbf{N}(\mathbf{x})) = I(x, y), \quad (1)$$

where $I(x, y)$ is the greylevel at a point $(x, y)$ in the image (in fact, $I(x, y)$ is the irradiance, but both quantities are usually proportional) and $R(\mathbf{N}(\mathbf{x}))$ is the reflectance function, giving the value of the light re-emitted by the surface as a function of its orientation i.e., of the unit normal $\mathbf{N}(\mathbf{x})$ to the surface. This normal can easily be expressed as:

$$\mathbf{N}(\mathbf{x}) = \frac{1}{\sqrt{1 + p(x, y)^2 + q(x, y)^2}} (-p(x, y), -q(x, y), 1), \quad (2)$$

where $p = \partial_x u$ and $q = \partial_y u$. Assume that there is a unique light source at infinity whose direction is indicated by the unit vector $\omega = (\omega_1, \omega_2, \omega_3) \in \mathbb{R}^3$. Recalling that, for a Lambertian surface of uniform albedo equal to 1, $R(\mathbf{N}(\mathbf{x})) = \phi \langle \omega, \mathbf{N}(\mathbf{x}) \rangle$, where $\phi$ is the “density” of the illumination, Eq. (1) can be written, using (2):

$$\frac{I(x, y)}{\phi} \sqrt{1 + \|\nabla u(x, y)\|^2 + \langle (\omega_1, \omega_2), \nabla u(x, y) \rangle - \omega_3} = 0, \quad (3)$$

which is a first order non-linear partial differential equation (PDE) of the Hamilton-Jacobi type. Points $(x, y) \in \Omega$ such that $I(x, y) = \phi$ correspond to the particular situation
where $\omega$ and $N(x)$ point in the same direction. These points are usually called the “singular points” [12].

Let us consider the equation which appears in most of the papers and which corresponds to vertical light source at infinity i.e., $\omega = (0, 0, 1)$. Then (3) becomes the “eikonal equation” [5]:

$$p(x, y)^2 + q(x, y)^2 = f(x, y), \quad (4)$$

with $f(x, y) = \phi^2/I(x, y)^2 - 1$. In this particular case, the singular points are those where $p(x, y) = 0$ and $q(x, y) = 0$.

Let us mention that the eikonal equation is not only the SFS model for Lambertian materials, since it also holds for any radially-symmetric reflectance [19]. Finally, more sophisticated models have appeared in the last few years, but we concentrate in this paper on the simple model of the eikonal equation.

## 2.2. Uniqueness of the Solution

The number of solutions to the SFS problem has been addressed in various situations. In [1], Belhumeur et al. determine the set of images of an object under all possible lighting conditions, a problem currently referred to as the “bas-relief ambiguity”. The existence of impossible shaded images is proved in [19, 4, 14]. However, our concern in this paper is uniqueness.

First of all, it is obvious that a translation of the surface in the direction of $Oz$ does not modify the first member of Eq. (4). Moreover, Eq. (4) is also invariant by symmetry w.r.t. the image plane $\mathcal{H}$. This is known as the “concave/convex ambiguity”. In his pionneering work [12], Horn shows that the presence of a singular point in the image much reduces the number of possible ambiguities but, whereas $N$ is completely known at a singular point, only its vertical component $N_z = \langle N, e_z \rangle$ is known at other points. For this reason, SFS is traditionally considered as an ill-posed problem.

Bruss uses a Taylor series expansion at a singular point in order to characterize the solutions [5], and states the first proof of uniqueness, which requires the presence of a closed “occluding contour” i.e., of a contour on which $I(x, y) = 0$ or, equivalently, $p(x, y)^2 + q(x, y)^2 = +\infty$. On such a contour, as well as at a singular point, the normal is computable [15], which is of great importance to constrain the problem. Blake et al. state another uniqueness result [2] in the case where $u$ is known on a closed contour (Dirichlet boundary condition).

Oliensis concentrates on the occluding contours. He claims that, in many situations, regularization techniques (see [13]) should be avoided in SFS, since the problem is well-posed and regularization may distort the solution. He states a uniqueness theorem which is more generic than Bruss' one [19], and partially extends it to the case of any

direction of illumination [18], a situation which is also explored by Saxberg in [23].

Brooks et al. exhibit a counterexample to Bruss' theorem in [3] and address the problem of radially-symmetric eikonal equations. Finally, most of these contributions, which generally use the “characteristic strips method” (see [12] and Section 3.3.1), are updated by Kozera in [16].

The problem of uniqueness in SFS has also been addressed in the framework of “viscosity solutions”, which are solutions in a weak sense [17]. Of course, SFS should be less-constrained if $u$ is a viscosity solution than if it is differentiable. Indeed, uniqueness of the viscosity solution requires, most of the time, Dirichlet boundary conditions as well as the knowledge of $u$ at each singular point [17], since precisely a singular point improves the number of viscosity solutions!

Therefore, the concept of “maximal viscosity solution” [10, 6] eliminates the need for a priori additional information. More recently, Prados et al. prove an existence and uniqueness result for the perspective SFS problem coupled to state constraint boundary condition, in the case where the light source is located at the center of projection [22, 21].

## 2.3. Invisible Continuous Deformations

A somewhat different problem is the search for invisible continuous deformations i.e., manifolds of surfaces which are solutions to the same eikonal equation, and which can therefore be continuously distorted without any change in the image. More precisely, an invisible continuous deformation is a family $\{u_c\}_{c \in \mathbb{R}}$ of functions $\Omega \to \mathbb{R}$, depending on a real parameter $c$, which all are solutions to Eq. (4). Differentiating (4) w.r.t. $c$, it comes:

$$\partial_c \|\nabla u_c(x, y)\|^2 = 0, \quad (5)$$

or:

$$\langle \nabla u_c(x, y), \nabla \partial_c u_c(x, y) \rangle = 0. \quad (6)$$

Nevertheless, this equation does not prove that invisible continuous deformations exist.

Starting from a solution $u_0$, a construction of an invisible deformation could proceed as follows. Consider the family of curves of equations $u_c(\cdot) = h$, for all $h \in \mathbb{R}$, and the family of curves of equations $\partial_c u_c(\cdot) = h$, for all $h \in \mathbb{R}$. Assume that these two families are orthogonal, as required by Eq. (6). This ensures that each $u_c$ is a solution to Eq. (4). Of course, in order to make a proof from this heuristics, one would still have to show that the differential equation (6) could indeed be integrated, especially at a singular point where all the lines $\partial_c u_c(\cdot) = h$, $h \in \mathbb{R}$, converge. Furthermore, all the solutions which are built with this procedure could represent surfaces without real deformation. Consider for instance $f(x, y) = 1$ and $u_0(x, y) = x$. From (6), one
can get $u_c(x, y) = x \cos c - y \sin c$, but $u_c$ is the composition of $u_0$ and of a rotation.

Nevertheless, although this might seem to be almost impossible, the existence of an invisible continuous deformation in presence of a singular point is proved in [9]. In the next section, we will focus on the existence of invisible continuous deformations of applicable surfaces.

# 3. Invisible Continuous Deformations of Applicable Surfaces

## 3.1. Basic Equations

We deal hereafter with some classical tools of differential geometry. We refer the interested reader, e.g., to [24, 7].

Let $S \subset \mathbb{R}^3$ be an applicable surface. It is well known that $S$ is ruled. As a simplification we suppose that through each point $\mathbf{x} \in S$ goes exactly one line $\mathcal{D}_{\mathbf{x}}$ contained in $S$ (there might also be flat pieces in $S$). The lines $\mathcal{D}_{\mathbf{x}}$ project on $\mathcal{H}$ to lines $\Delta_{\mathbf{x}}$ which foliate $\Omega$. The surface $S$ can be locally parameterized as follows:

$$ \mathbf{x}(s, t) = t \mathbf{v}(s) + \mathbf{a}(s), \qquad (7) $$

where $\mathbf{v}(s)$ is a unit vector (along $\mathcal{D}_{\mathbf{x}}$). We can suppose additionally that $\mathbf{a}'(s)$ is orthogonal to $\mathbf{v}(s)$. Let $\mathbf{w}(s)$ be the orthogonal projection of $\mathbf{v}(s)$ on $\mathcal{H}$.

Under the simple SFS model presented in Section 2.1, the vertical component $N_z$ of $\mathbf{N}$ follows from the shading. Let $\mathbf{II}$ be the second fundamental form of $S$.

**Remark** At all $\mathbf{x} \in S$, the kernel of $\mathbf{II}$ is the set of vectors parallel to $\mathcal{D}_{\mathbf{x}}$. It follows that $\mathbf{N}$ is constant along the lines $\mathcal{D}_{\mathbf{x}}$. Thus, $\mathbf{N}$ is a function of $s$ only, and $\partial_s \mathbf{N}$ is orthogonal to $\mathbf{v}$ at each point.

To sum up, at each point:

* $\mathbf{N}'(s)$ is orthogonal to $\mathbf{N}(s)$ and to $\mathbf{v}(s)$, so that it can be expressed in terms of $N'_z(s)$:

$$ \mathbf{N}'(s) = \frac{N'_z(s)}{\langle \mathbf{N}(s) \times \mathbf{v}(s), \mathbf{e}_z \rangle} \mathbf{N}(s) \times \mathbf{v}(s). \quad (8) $$

Note that the denominator in the second member of Eq. (8) vanishes if $\mathbf{N}$ is parallel to $\mathbf{e}_z$ i.e., at a singular point.

* $\mathbf{v}(s)$ is orthogonal to $\mathbf{N}(s)$ and its projection $\mathbf{w}(s)$ to $\mathcal{H}$ is known, so that it can be recovered from $\mathbf{N}(s)$ and $\mathbf{w}(s)$:

$$ \mathbf{v}(s) = \frac{i\mathbf{w}(s) \times \mathbf{N}(s)}{\|i\mathbf{w}(s) \times \mathbf{N}(s)\|}. \quad (9) $$

Here $i\mathbf{w}(s)$ means that we consider the complex structure on $\mathcal{H}$ identified with $\mathbb{R}^2$ and with $\mathbb{C}$.

## 3.2. Deformations with Constant Shading

Our main claim is that many applicable surfaces can be deformed without changing the shading.

**Theorem 1** Suppose that $S$ is an applicable surface which is a graph over $\Omega$, that $\Omega$ is bounded, and that $N$ is nowhere vertical. Then $S$ has a 1-parameter deformation as an applicable surface such that $N_z$, considered as a function over $\Omega$, is constant.

The proof rests on a converse of the remarks in section 3.1.

**Remark** Suppose given $\mathbf{w}, N_z$ and let $\mathbf{v}, \mathbf{N}$ be functions of $s$ satisfying equations (8) and (9). Then there exists a (unique) applicable surface $S$, going through a given point $\mathbf{m} \in \mathbb{R}^3$ over $\Omega$, such that the projection of $\mathbf{v}$ is $\mathbf{w}$ and that the $z$-component of $\mathbf{N}$ is $N_z$.

The condition that the surface goes through a given point $\mathbf{m}$ is necessary to choose one solution among a 1-parameter family invariant under vertical translation.

**Proof of Theorem 1** The starting point is a classical result from differential geometry: given two vector fields $\mathbf{u}, \mathbf{v}$ in $\mathbb{R}^3$, linearly independent at each point, there exists a foliation of $\mathbb{R}^3$ by surfaces to which $\mathbf{u}$ and $\mathbf{v}$ are everywhere tangent if and only if $[\mathbf{u}, \mathbf{v}] \in \text{vect}(\mathbf{u}, \mathbf{v})$ at each point, where $[\cdot, \cdot]$ is the Lie bracket.

Let $\mathbf{v}_{\perp} = \mathbf{N} \times \mathbf{v}$. Then $\mathbf{v}_{\perp}$ is constant along the integral lines of $\mathbf{v}$ i.e.:

$$ D_{\mathbf{v}}\mathbf{v}_{\perp} = 0, \qquad (10) $$

where $D$ is the flat connection of $\mathbb{R}^3$ (directional derivative). It is possible to suppose (in the parametrization of $S$ described above) that $\mathbf{a}'(s)$ is orthogonal to $\mathbf{v}$. It follows that $\mathbf{a}'(s)$ is parallel to $\mathbf{v}_{\perp}$.

Consider $\mathbf{v}, \mathbf{N}$ as two vector fields defined on $\mathbb{R}^3$, invariant by vertical translation. Note now that $\mathbf{N}'(s)$ is orthogonal to $\mathbf{v}(s)$ by Eq. (8). Since $\langle \mathbf{N}(s), \mathbf{v}(s) \rangle = 0$:

$$ \langle \mathbf{N}'(s), \mathbf{v}(s) \rangle + \langle \mathbf{N}(s), \mathbf{v}'(s) \rangle = 0, \qquad (11) $$

so that $\mathbf{v}'(s)$ is orthogonal to $\mathbf{N}(s)$. Thus, the Lie bracket:

$$ [\mathbf{v}, \mathbf{v}_{\perp}] = D_{\mathbf{v}}\mathbf{v}_{\perp} - D_{\mathbf{v}_{\perp}}\mathbf{v} = -D_{\mathbf{v}_{\perp}}\mathbf{v} \qquad (12) $$

is orthogonal to $\mathbf{N}$. This means that the distribution of 2-planes spanned by $\mathbf{v}$ and $\mathbf{v}_{\perp}$ is integrable. Integrating it yields a foliation of the union of vertical lines intersecting $\Omega$ by surfaces. This foliation is invariant under vertical translation.

Moreover the definition shows that the vector field $\mathbf{w}$ lifts to those surfaces as vector fields $\mathbf{v}$ so that the integral curves of $\mathbf{v}$ are straight lines, and the vector field $\mathbf{N}$ considered in the construction is orthogonal to those surfaces. This implies that the second fundamental form of those surfaces
<figure><img src="image_2.png" /><figcaption>Figure 1. Image associated to the eikonal equation (13).</figcaption></figure>

has non-trivial kernel – the kernel is generated by $v$ – and so the surfaces are applicable, by the Gauss equation. ■

### 3.3. Examples

Let us consider the following eikonal equation:

$$p(x, y)^2 + q(x, y)^2 = 1 + x^2. \qquad (13)$$

The lines $\Delta_x$ are parallel to $Oy$. Let us solve Eq. (13) using a classical method of resolution of the first order non-linear PDEs.

#### 3.3.1 Characteristic Strips Method

Since $p^2 + q^2 > 0$ everywhere, there is no singular point in the image (cf. Fig. 1) associated to Eq. (13). The five ordinary differential equations of the so-called “characteristic strips method” [12] are, in our case:

$$\dot{x} = 2p, \qquad (14a)$$

$$\dot{y} = 2q, \qquad (14b)$$

$$\dot{z} = 2(1 + x^2), \qquad (14c)$$

$$\dot{p} = 2x, \qquad (14d)$$

$$\dot{q} = 0, \qquad (14e)$$

where the dot denotes differentiation w.r.t. a real parameter $s$ which could be, for example, an arc-length. In fact, the five unknowns $(x, y, z, p, q)$ depend on another parameter than $s$, but Eqs. (14a)-(14e) suppose that this second parameter $t$ is constant along each characteristic strip. Integrating this system, we can reconstruct the whole shape

from an “initial curve” on which the 5-tuple $(x, y, z, p, q)$ is known. Moreover, at any “starting point” on the initial curve, the vector $(\dot{x}, \dot{y})$, which by definition is tangent to the current characteristic strip, must be non-tangent to the initial curve. Finally, this last vector must be everywhere non-null, which here is guaranteed by the form (13) of $p^2 + q^2$. Let us use, for instance, the axis $Oy$ as initial curve. We can thus define $t$ as the $y$-component of the starting point. For a given starting point $(x, y) = (0, t)$, the 2-tuple $(p, q)$ cannot be uniquely determined from Eq. (13). Let us choose $(p(0, t), q(0, t)) = (f(t), g(t))$, with $f(t)^2 + g(t)^2 = 1$ and $f(t) \neq 0$, so that $(p, q)$ is not parallel to $Oy$. On the one hand, Eqs. (14a) and (14d) give:

$$\partial_s^2 x(s, t) - 4x(s, t) = 0, \qquad (15)$$

with the initial conditions $x(0, t) = 0$ and $\partial_s x(0, t) = 2f(t)$. Then:

$$x(s, t) = f(t) \sinh(2s). \qquad (16)$$

On the other hand, Eqs. (14b) and (14e) give:

$$\partial_s^2 y(s, t) = 0, \qquad (17)$$

with the initial conditions $y(0, t) = t$ and $\partial_s y(0, t) = 2g(t)$. Then:

$$y(s, t) = 2sg(t) + t. \qquad (18)$$

Finally, Eqs. (14c) and (16) give:

$$\partial_s z(s, t) = 2 - f(t)^2 + f(t)^2 \cosh(4s), \qquad (19)$$

with the following initial condition:

$$z(0, t) = \int_{0}^{t} g(u) du + z(0, 0). \qquad (20)$$

Because $z$ has to be fixed at some point, we set $z(0, 0) = 0$. Therefore, from (19) and (20):

$$z(s, t) = (2 - f(t)^2) s + f(t)^2 \frac{\sinh(4s)}{4} + \int_{0}^{t} g(u) du. \qquad (21)$$

#### 3.3.2 Applicable Solutions

For any applicable solution to Eq. (13), it has been proved in Section 3.1 that the normal is uniform along $Oy$, and so are $f$ and $g$ as well. Knowing that $f(t)^2 + g(t)^2 = 1$, there exists a real $\theta \neq 0$ such that $f(t) = \cos\theta$ and $g(t) = \sin\theta$. Eqs. (16), (18) and (21) can thus be rewritten:

$$x(s, t) = \cos\theta \sinh(2s), \qquad (22a)$$

$$y(s, t) = 2s \sin\theta + t, \qquad (22b)$$

$$z(s, t) = (2 - \cos^2\theta) s + \cos^2\theta \frac{\sinh(4s)}{4} + t \sin\theta. \qquad (22c)$$
This is a parametric representation of the solution $S_\theta$, which is parameterized by $\theta$. Its explicit equation is straightforward, since $s$ and $t$ can be expressed from (22a) and (22b):

$$s = \frac{1}{2} \operatorname{argsh} \frac{x(s, t)}{\cos \theta}, \qquad (23a)$$

$$t = y(s, t) - \sin \theta \operatorname{argsh} \frac{x(s, t)}{\cos \theta}. \qquad (23b)$$

Replacing $s$ and $t$ by these expressions in (22c), the explicit equation of $S_\theta$ is:

$$z = \frac{\cos^2 \theta}{2} \operatorname{argsh} \frac{x}{\cos \theta} + \frac{x}{2} \sqrt{x^2 + \cos^2 \theta} + y \sin \theta. \quad (24)$$

from which it arises that all surfaces $S_\theta$ are cylinders, whose generatrices are parallel to the plane $Oyz$. Therefore, a continuous modification of $\theta$ in $]-\pi/2, \pi/2[$ gives rise to an invisible continuous deformation of the surface $S_\theta$. In Fig. 2, three cylinders among this 1-dimensional manifold are shown, for $s \in [-0.9, 0.9]$ and $t \in [-5, 5]$.

### 3.3.3 Other Solutions

Of course, other solutions to Eq. (13) exist, that are not applicable. For instance, for a given real $T \neq 0$, let us choose $f(t) = \cos(t/T)$ and $g(t) = \sin(t/T)$, with $t/T \in ]-\pi/2, \pi/2[$. Eqs. (16), (18) and (21) can be rewritten:

$$x(s, t) = \cos \frac{t}{T} \sinh(2s), \qquad (25a)$$

$$y(s, t) = 2s \sin \frac{t}{T} + t, \qquad (25b)$$

$$z(s, t) = \left(2 - \cos^2 \frac{t}{T}\right)s + \cos^2 \frac{t}{T} \frac{\sinh(4s)}{4} + T\left(1 - \cos \frac{t}{T}\right). \qquad (25c)$$

This is a parametric definition of non-applicable solutions which we call $\mathcal{T}_T$. In Fig. 3, three of these non-applicable solutions are shown, for $s \in [-0.9, 0.9]$ and $t/T \in [-\pi/4, \pi/4]$.

On the one hand, the parametric definition (25a)-(25b)-(25c) is not as easy to transform in an explicit equation as for the applicable solutions. On the other hand, if the surfaces $\mathcal{T}_T$ form a 1-dimensional manifold of solutions, parameterized by $T$, they do not constitute all the non-applicable solutions to Eq. (13).

## 3.4. Presence of an Occluding Contour

Now let us consider the following eikonal equation:

$$p(x, y)^2 + q(x, y)^2 = \frac{1}{x^2}, \quad \text{for } x \neq 0. \qquad (26)$$

This case is interesting because $p^2 + q^2 \to +\infty$ when $x \to 0$, which means that each solution to Eq. (26) has $Ox$

as occluding contour. Therefore, $N \to \pm e_x$ when $x \to 0$. Nevertheless, this knowledge on $N$ does not constrain the applicable solutions. As a proof, here is the explicit equation of a 1-dimensional manifold of applicable solutions to Eq. (26), which are parameterized by a parameter $c$:

$$z = \sqrt{1 - c^2 x^2} - \operatorname{argch} \frac{1}{cx} + cy. \qquad (27)$$

In Eq. (27), however, one has to impose $1/(cx) \ge 1$, since $\operatorname{argch}$ is defined on $[1, +\infty[$.

# 4. Application to Document Image Analysis

Theorem 1 can be straightforwardly applied to document image analysis and, for example, to the simulation of document flattening.

## 4.1. Simulation of Document Flattening

The digitization of documents currently knows an increasing popularity, because of the expansion of Internet browsing. The traditional process, which uses a flatbed scanner, is satisfactory for flat documents, but is unsuitable for curved documents like for example a thick book, since some defects will appear in the digitized image. Several specific systems have been designed, but such systems are sometimes intrusive with regard to the documents and, before all, they cannot be referred to as consumer equipments. An alternative consists in *simulating* the flattening of curved documents i.e., in correcting the defects of images provided by a flatbed scanner or a digital camera. In order to successfully simulate the document flattening, it is necessary to compute its surface shape.

Among many papers dealing with this problem, two only deal with the most general case of applicable surfaces [20, 11] and, moreover, none of both relies on SFS. Our result could potentially lead us to a new algorithm of flattening simulation.

## 4.2. A New Method of 3D-reconstruction

As a concrete application of Theorem 1, we can design a new method of 3D-reconstruction from one shaded image of a document. Given the normal along an “initial curve”, which should be one of the straight lines $\Delta_x$, 3D-reconstruction could of course be carried out through using the characteristic strips method (cf. Section 3.3.1), but the implementation would be tedious: new characteristic strips would have to be created when they separate too much, or deleted when they approach each other too closely [12].

We propose a new method of 3D-reconstruction of a document shape that is much easier to implement, because the choice of an integration path is free. Once the normal is fixed at some point in the image, and knowing that the normal is uniform on each line $\Delta_x$ and that these lines foliate $\Omega$,
<figure><img src="image_3.png" /><figcaption>Figure 2. Three cylinders giving the same image as Fig. 1: $S_0$ (left), $S_{\pi/6}$ (middle); $S_{\pi/3}$ (right).</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3. Three non-applicable surfaces giving the same image as Fig. 1: $T_5$ (left), $T_{7.5}$ (middle); $T_{10}$ (right).</figcaption></figure>

the integration of Eqs. (8) and (9) can be carried out along *any* path in $\Omega$, provided this path crosses all the $\Delta_x$. After that, the integration of the computed normal field is very simple, since Theorem 1 tells us that the normal field of any applicable surface is integrable.

### 4.3. Example

We print a regular black grid on a square sheet (cf. Fig. 4), and we simulate the 3D-warping of this sheet on the three cylinders of Fig. 2, as shown in Fig. 5. It could seem that the three shapes of Fig. 5 are not those of Fig. 2. It happens that, among the three surfaces viewed in Fig. 2, only that on the left would be rectangular after flattening. The others would not, and this is why our appreciation of these shapes in erroneous. The images of the three shapes of Fig. 5, seen from above under the classical assumptions of SFS, are shown in Fig. 6. In the images of Fig.6, the sheet contour, as well as the deformation of the grid, tell us much about the shape of the sheet, but this information may lead us to an erroneous interpretation of the shape, as in the case of Fig. 2!

Using only the shading information in the images of Fig. 6, we cannot avoid the ambiguity expressed in Theorem 1. Moreover, the non-uniform albedo of these scenes requires

<figure><img src="image_5.png" /><figcaption>Figure 4. Regular black grid printed on a square sheet.</figcaption></figure>

a pretreatment in which the inked points, whose albedo is equal to 0, have to be separated from the non-inked points, whose albedo is equal to 1. This could be done, e.g., through
<figure><img src="image_6.png" /><figcaption>Figure 5. Warping of the sheet of Fig. 4 on the three cylinders of Fig. 2: $S_0$ (left), $S_{\pi/6}$ (middle); $S_{\pi/3}$ (right).</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 6. Images of the three scenes of Fig. 5, seen from above under the classical assumptions of SFS.</figcaption></figure>

adaptive thresholding but, since this is out of scope, we use
in fact the non-textured image of Fig. 1 instead of the im-
ages of Fig. 6. The simplest integration path is $Ox$. Three
profiles obtained from three possible normals at (0, 0) are
shown in Fig. 7. This simple example shows, if necessary,
that SFS remains ill-posed in many situations since, even in
the framework of the applicable surfaces, one cannot decide
between the three shapes of Fig. 7 and many others.

**5. Conclusion and Perspectives**

In this paper, we show that SFS is ill-posed, under the
simple model of the eikonal equation, even if the scene
surface is supposed to be applicable to a plane. If no sin-
gular point is visible, the applicable solutions form a 1-
dimensional manifold. The knowledge of one normal thus
suffices to render the problem well-posed. A straightforward application of this theoretical result is document im-
age analysis, and especially the simulation of document flatt-
tening.

Many prospects remain open. First of all, we should ex-
amine how much a singular point constrains the problem.
We must extend Theorem 1 to applicable surfaces with flat

pieces. It is also necessary to address more realistic SFS
models: perspective projection, as well as various direc-
tions of illumination, should be explored. It could happen
that another model better constrains the problem (see [22]).

A remaining problem of our new method of 3D-
reconstruction is that the knowledge of one normal is re-
quired, at some point that can be neither a singular point
nor a point lying on an occluding contour. In order to ren-
der the 3D-reconstruction well-posed, we now address the
information given by the contour, as mentioned in Section
4.3. Moreover, we already proved the following interest-
ing result (which is not detailed in this paper, due to lack of
space): knowing the image of a straight line on the flattened
surface (which is a “geodesic segment” on S) can be used to
recover S without ambiguity from its shading information.

**References**

[1] P. N. Belhumeur, D. J. Kriegman, and A. L. Yuille. The Bas-
Relief Ambiguity. *International Journal of Computer Vision*,
35(1):33–44, Nov. 1999. 2

[2] A. Blake, A. Zisserman, and G. Knowles. Surface descrip-
tions from stereo and shading. *Image and Vision Computing*,
<figure><img src="image_8.png" /><figcaption>Figure 7. Three profiles reconstructed from the image of Fig. 1, using the normals at (0, 0) of: $S_0$ (left), $S_{\pi/6}$ (middle); $S_{\pi/3}$ (right).</figcaption></figure>

3(4):183–191, Nov. 1985. 2

[3] M. J. Brooks, W. Chojnacki, and R. Kozera. Circularly Symmetric Eikonal Equations and Non-uniqueness in Computer Vision. *Journal of Mathematical Analysis and Applications*, 165(1):192–215, 1992. 2

[4] M. J. Brooks, W. Chojnacki, and R. Kozera. Impossible and Ambiguous Shading Patterns. *International Journal of Computer Vision*, 7(2):119–126, Jan. 1992. 2

[5] A. R. Bruss. The Image Irradiance Equation: Its Solution and Application. Technical Report AITR-623, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, June 1981. 2

[6] F. Camilli and L. Grüne. Numerical Approximation of the Maximal Solutions for a Class of Degenerate Hamilton-Jacobi Equations. *SIAM Journal on Numerical Analysis*, 38(5):1540–1560, Dec. 2000. 2

[7] M. P. Do Carmo. *Differential Geometry of Curves and Surfaces*. Prentice-Hall, 1976. 3

[8] J.-D. Durou, M. Falcone, and M. Sagona. Numerical Methods for Shape-from-shading: A New Survey with Benchmarks. *Computer Vision and Image Understanding*, 2007. (to appear). 1

[9] J.-D. Durou and D. Piau. Ambiguous Shape from Shading with Critical Points. *Journal of Mathematical Imaging and Vision*, 12(2):99–108, Apr. 2000. 3

[10] M. Falcone and M. Sagona. An algorithm for the global solution of the Shape-from-Shading model. In *Proceedings of the 9th International Conference on Image Analysis and Processing (volume I)*, volume 1310 of *Lecture Notes in Computer Science*, pages 596–603, Florence, Italy, Sept. 1997. 2

[11] N. Gumerov, A. Zandifar, R. Duraiswami, and L. S. Davis. 3D structure recovery and unwarping of surfaces applicable to planes. *International Journal of Computer Vision*, 66(3):261–281, Mar. 2006. 5

[12] B. K. P. Horn. Obtaining Shape from Shading Information. In P. H. Winston, editor, *The Psychology of Computer Vision*, chapter 4, pages 115–155. McGraw-Hill, 1975. 1, 2, 4, 5

[13] B. K. P. Horn and M. J. Brooks. The Variational Approach to Shape From Shading. *Computer Vision, Graphics, and Image Processing*, 33(2):174–208, Feb. 1986. 2

[14] B. K. P. Horn, R. Szeliski, and A. L. Yuille. Impossible Shaded Images. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 15(2):166–170, Feb. 1993. 2

[15] K. Ikeuchi and B. K. P. Horn. Numerical Shape from Shading and Occluding Boundaries. *Artificial Intelligence*, 17(1–3):141–184, Aug. 1981. 2

[16] R. Kozera. Uniqueness in Shape from Shading Revisited. *Journal of Mathematical Imaging and Vision*, 7(2):123–138, Mar. 1997. 2

[17] P.-L. Lions, E. Rouy, and A. Tourin. Shape-from-Shading, viscosity solutions and edges. *Numerische Mathematik*, 64(3):323–353, Mar. 1993. 2

[18] J. Oliensis. Shape from Shading as a Partially Well-Constrained Problem. *Computer Vision, Graphics, and Image Processing: Image Understanding*, 54(2):163–183, Sept. 1991. 2

[19] J. Oliensis. Uniqueness in Shape from Shading. *International Journal of Computer Vision*, 6(2):75–104, June 1991. 2

[20] M. Pilu. Undoing Paper Curl Distortion Using Applicable Surfaces. In *Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (volume I)*, pages 67–72, Kauai, Hawaii, USA, Dec. 2001. 5

[21] E. Prados and O. Faugeras. A generic and provably convergent Shape-From-Shading Method for Orthographic and Pinhole Cameras. *International Journal of Computer Vision*, 65(1–2):97–125, Nov. 2005. 2

[22] E. Prados, O. Faugeras, and F. Camilli. Shape from Shading: a well-posed problem? Rapport de Recherche 5297, Institut National de Recherche en Informatique et en Automatique, Sophia Antipolis, France, Aug. 2004. 2, 7

[23] B. V. H. Saxberg. Existence and Uniqueness for Shape from Shading around Critical Points: Theory and an Algorithm. *International Journal of Robotics Research*, 11(3):202–224, June 1992. 2

[24] M. Spivak. *A Comprehensive Introduction to Differential Geometry (volume II)*. Publish or Perish, 1970. 3

[25] R. Zhang, P.-S. Tsai, J. E. Cryer, and M. Shah. Shape from Shading: A Survey. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 21(8):690–706, Aug. 1999. 1