J Ponce

K Mchenry

T Papadopoulo

M Teillaud

On the Absolute Quadratic Complex and its Application to Autocalibration

This article introduces the absolute quadratic complex formed by all lines that intersect the absolute conic.

If ω denotes the 3 × 3 symmetric matrix representing the image of that conic under the action of a camera with projection matrix P, it is shown that ω ≈ PΩP T , where P is the 3×6 line projection matrix associated with P, and Ω is a 6 × 6 symmetric matrix of rank 3 representing the absolute quadratic complex. This simple relation between a camera's intrinsic parameters, its projection matrix expressed in a projective coordinate frame, and the metric upgrade separating this frame from a metric one-as respectively captured by the matrices ω, P, and Ω-provides a new framework for autocalibration, particularly well suited to typical digital cameras with rectangular or square pixels since the skew and aspect ratio are decoupled from the other intrinsic parameters in ω.

Introduction

Chasles' absolute conic, an imaginary conic section invariant under similarities, plays a fundamental role in the study of metric properties of pinhole cameras: The problem of estimating the epipolar geometry of a pair of cameras from seven point correspondences was first posed by Chasles [START_REF] Chasles | Question no. 296[END_REF] and solved by Hesse [START_REF] Hesse | Die cubische Gleichung, von welcher die Lösung des Problems der Homographie von M. Chasles abhängt[END_REF]. As shown by Kruppa [START_REF] Kruppa | Zur Ermittung eines Objektes aus zwei Perspektiven mit innerer Orientierung[END_REF] and mentioned by Faugeras and Maybank [START_REF] Faugeras | Motion from point matches: multiplicity of solutions[END_REF], five point correspondences are sufficient for internally calibrated cameras, the absolute conic being used in that case to derive two tangency constraints that make up for the missing point correspondences. As shown by Maybank and Faugeras [START_REF] Maybank | A theory of selfcalibration of a moving camera[END_REF], the absolute conic (together with its image projection) also provides a "virtual" calibration device (Fig. 1) that can be used in autocalibration tasks [START_REF] Bougnoux | From projective to Euclidean space under any practical situation, a criticism of self-calibration[END_REF][START_REF] Fitzgibbon | Automatic 3D model acquisition and generation of new images from video sequences[END_REF][START_REF] Maybank | A theory of selfcalibration of a moving camera[END_REF], where both the intrinsic camera parameters and a metric scene reconstruction are computed from an initial, purely projective scene reconstruction obtained from multiple images, without the use of a physical calibration chart. In practice, it is often convenient to replace the absolute conic by Triggs' absolute quadric [START_REF] Triggs | Auto-calibration and the absolute quadric[END_REF], since it is easy to characterize the projection of this (dual) quadric surface in terms of the internal camera parameters, the projection matrix expressed in some projective frame, and a metric upgrade matrix that maps this coordinate system onto a metric one [START_REF] Pollefeys | Self-calibration and metric reconstruction in spite of varying and unknown internal camera parameters[END_REF][START_REF] Pollefeys | Surviving dominant planes in uncalibrated structure and motion recovery[END_REF][START_REF] Triggs | Auto-calibration and the absolute quadric[END_REF].

Figure 1: Left: Classical calibration devices include physical grid patterns and "virtual" objects such as the absolute conic and the (dual) absolute quadric formed by its tangent planes. The image lines tangent to the projection of the absolute conic form a dual conic, whose preimage is a subset of the absolute quadric. Right: The absolute quadratic complex (or AQC) is a new virtual calibration device formed by all straight lines intersecting the absolute conic. The preimage of the projection of the absolute conic (as opposed to its dual) is a subset of the absolute quadratic complex.

This article shows that similar constraints hold for the absolute quadratic complex formed by all lines intersecting the absolute conic. In particular, if ω denotes the 3 × 3 symmetric matrix representing the image of the absolute conic under the action of a camera with projection matrix P, we will show in Sect. 3 that ω ≈ PΩP T , where P is the 3 × 6 line projection matrix associated with P [START_REF] Faugeras | The Geometry of Multiple Images[END_REF], and Ω is a 6 × 6 symmetric matrix of rank 3 representing the absolute quadratic complex. This simple relation between a camera's intrinsic parameters, its projection matrix, and the corresponding metric upgrade-as respectively captured by the matrices ω, P, and Ω-provides a new framework for autocalibration, particularly well suited to typical digital cameras with rectangular or square pixels since the skew and aspect ratio are decoupled from the other intrinsic parameters in ω. In particular, we present a new derivation of the quasi-linear algorithm proposed by Ponce in [START_REF] Ponce | Metric upgrade of a projective reconstruction under the rectangular pixel assumption[END_REF] for cameras with square pixels but unknown and possibly varying focal length and principal point (see Bougnoux [START_REF] Bougnoux | From projective to Euclidean space under any practical situation, a criticism of self-calibration[END_REF] and Heyden and Åström [START_REF] Heyden | Flexible calibration: minimal cases for auto-calibration[END_REF] for iterative approaches to the same problem), and a novel non-linear algorithm for cameras with square pixels and unknown but fixed focal length and principal point. A quantitative comparison between these two methods and the quasi-linear algorithms proposed by Pollefeys et al. [START_REF] Pollefeys | Self-calibration and metric reconstruction in spite of varying and unknown internal camera parameters[END_REF][START_REF] Pollefeys | Surviving dominant planes in uncalibrated structure and motion recovery[END_REF] in the case of cameras with known principal point is also given.

Notation:

We denote by P 3 the projective completion of R 3 considered as an affine space. Given some fixed coordinate frame for P 3 , we identify points and planes with their homogeneous coordinate vectors in R 4 . In this presentation, line Plücker coordinate vectors are sometimes written in the form δ = (u; v), where u and v are vectors in R 3 , and the ";" symbol is used to indicate that the six coordinates are stacked onto each other to form a vector in R 6 . We use f x, f p, and f δ to denote the coordinate vector of the point x, the plane p, and the line δ in a specific frame (f ).

The symbol "≈" is used to express the fact that two vectors or two matrices are nonzero multiples of each other, e.g., x ≈ y, U ≈ V. Proofs: All propositions presented in the rest of this paper are stated without formal proofs. See [START_REF] Ponce | On the absolute quadratic complex and its application to autocalibration[END_REF] for these.

Line Geometry and Perspective Projection

This section briefly introduces elementary notions of line geometry, and discusses its relationship with the perspective projection process, as required for a good understanding of the rest of this article. This includes a characterization of coplanar lines and line bundles by trilinearities (Sect. 2.3), and the introduction of dual perspective projection (Sect. 2.1.4), topics that may be of interest on their own.

Elements of Line Geometry 2.1.1 Pl ücker Coordinates and the Join Operator

This section introduces some elementary notions of line geometry. Let us first introduce the join operator "∨" that associates with the (homogeneous) coordinate vectors x = (x 1 , x 2 , x 3 , x 4 ) T and y = (y 1 , y 2 , y 3 , y 4 ) T of two points the Plücker coordinate vector of the line joining them:

x ∨ y def = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ x4y1 -x1y4 x4y2 -x2y4 x4y3 -x3y4 x2y3 -x3y2 x3y1 -x1y3 x1y2 -x2y1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ .
Plücker coordinates are homogeneous, and lines form a quadratic hypersurface L 4 of dimension 4 in the projective space P 5 : Indeed, it follows immediately from the definition of the join that the Plücker coordinate vector δ = (u; v) of a line satisfies the quadratic Klein constraint u • v = 0. It is also possible to define an inner product in L 4 by the formula (δ|η) def = u • t + v • s, where δ = (u; v) and η = (s; t). A vector δ in R 6 represents a line if and only if (δ|δ) = 0, and it can also be shown that a necessary and sufficient condition for two lines δ and η to be coplanar is that (δ|η) = 0. For reasons that will shortly become obvious, when δ = (u; v), it is convenient to define the vector δ * = (v; u) so that (δ|η

) = δ * • η = δ • η * .
Remark 1 Consider two finite points with homogeneous coor- dinate vectors x = (x1, x2, x3, 1) T and y = (y1, y2, y3, 1) T in some affine coordinate frame, and denote by x and y the corresponding non-homogeneous coordinate vectors. The Plücker coordinate vector of the line joining these two points is x∨y = (u; v), where u = y -x and v = (x × y ). In particular, the vector u is the affine direction of this line, defined up to scale.

Duality and the Meet Operator

The set of hyperplanes in P n forms a second projective space of dimension n, denoted by P n * and said to be dual to the original (primal) one. The points x in P n such that p • x = 0 for some fixed vector p = 0 of R n+1 form a hyperplane p * of P n , whose dual is the point p of P n * . The dual of a point x in P n is the hyperplane x * of P n * formed by all hyperplanes p of P n that pass through that point-or equivalently, satisfy p • x = 0. We focus of course on the cases n = 2 and n = 3 in this presentation. The dual of a line in P 3 is the one-dimensional pencil of planes passing through that line-that is, a line in P 3 * . It is easy to show that the dual of the line δ is the line δ * . The meet operator associates with two planes p and q the Plücker coordinate vector of the (primal) line p ∧ q where they intersect. This line of P 3 is the dual of the join of the two planes in P 3 * . Thus

p ∧ q = (p ∨ q) * = ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ p2q3 -p3q2 p3q1 -p1q3 p1q2 -p2q1 p4q1 -p1q4 p4q2 -p2q4 p4q3 -p3q4 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ .

Mixed Join and Meet Operators

The join operator can be extended to lines and points: Given a line δ = (u; v) and a point x not lying on δ, we define the join of δ and x as the plane spanned by the line and the point. Algebraically, it is given by δ ∨ x = [δ ∨ ]x, where

[δ ∨ ] def = [u×] v -v T 0
, and [u × ] is the 3 × 3 skew-symmetric matrix such that [u × ]w = u × w for any vector w in R 3 . A necessary and sufficient condition for x to lie on δ is that δ ∨ x = 0. The join of three points x, y, and z is the plane spanned by these points, defined algebraically by

x ∨ y ∨ z def = (x ∨ y) ∨ z.
The meet of a line δ = (u; v) and a plane p is the point where they intersect, which is given by δ

∧ p = [δ ∧ ]p, with [δ ∧ ] def = [δ * ∨ ].
A necessary and sufficient condition for δ to lie in the plane p is that δ ∧ p = 0. The meet of three planes p, q, and r is the the point where these planes intersect, defined algebraically by p ∧ q ∧ r def = (p ∧ q) ∧ r.

Coplanar Lines and Line Bundles

Consider k lines with Plücker coordinate vectors δ i (i = 1, . . . , k) lying in the same plane. Obviously, each one of these vectors verifies the quadratic Klein constraint (δ i |δ i ) = 0, and any two of them satisfy the bilinear constraint (δ i |δ j ) = 0 associated with a pair of coplanar lines. It is easy to show that any three of these vectors also satisfy four independent trilinear constraints (see Appendix), and that any four of them are linearly dependent. A line bundle is a set of lines passing through some point. Any two of these lines are coplanar, and their Plücker coordinate vectors also satisfy the quadratic and bilinear constraints (δ i |δ i ) = 0 and (δ i |δ j ) = 0. In addition, the bundle of lines passing through some point x is the dual of the set of lines lying in the dual plane x * . Therefore, any three lines in the bundle satisfy a dual set of trilinear constraints, and any four of them are linearly dependent (see Appendix).

Perspective Projection

A pinhole camera is defined by its optical center c and its image plane r. The corresponding perspective projection maps every point x distinct from c onto the point x = (c ∨ x) ∧ r, i.e., the intersection of the ray ξ joining c to x with the plane r (Fig. 2). In order to model this mapping analytically, we choose an arbitrary but fixed coordinate system for r and identify this plane with P 2 . Selecting a projective basis for r amounts to picking three non-collinear points x 1 , x 2 , and x 3 in that plane. 1 Using the methodology of [START_REF] Faugeras | The Geometry of Multiple Images[END_REF], it is then easy to show that the image of the point x is given in this coordinate system by x ≈ Px, where P =

p T 1 p T 2 p T 3 ,
and p 1 = c∨x 2 ∨x 3 , p 2 = c∨x 3 ∨x 1 , and p 3 = c∨x 1 ∨x 2 are the projection planes of the camera.

The projection of a straight line under the action of a pinhole camera with projection matrix P is characterized by the corresponding line projection matrix P, defined as follows in terms of the rows p T i (i = 1, 2, 3) of P. 1 Here, as usual, we identify points and their coordinate vectors defined up to scale. The rest of our discussion assumes that the relative scales of the vectors x i are fixed. This can be done (for example) by using a fourth unit point to complete the specification of a projective frame for r.

Definition 1

The line projection matrix associated with a 3 × 4 matrix P is the 3 × 6 matrix

P def = ξ T 1 ξ T 2 ξ T 3
, where

ξ 1 = p 2 ∧ p 3 ≈ c ∨ x1, ξ 2 = p 3 ∧ p 1 ≈ c ∨ x2, ξ 3 = p 1 ∧ p 2 ≈ c ∨ x3.
The line projection matrix will play a fundamental role in the rest of this presentation. The following proposition states its fundamental properties (Fig. 3). See Faugeras et. al [START_REF] Faugeras | The Geometry of Multiple Images[END_REF] for its proof. The columns ξ 1 , ξ 2 , and ξ 3 of P T are the coordinate vectors of three lines passing through c, and thus satisfy the quadratic, bilinear, and trilinear constraints associated with the corresponding bundle. Note that writing that the lines P T 1 x 1 , P T 2 x 2 , and P T 3 x 3 associated with three images x 1 , x 2 , and x 3 of the same point belong to the corresponding bundle, thus providing directly the four trilinear constraints associated with three views of that point, without the intermediate characterization of the trifocal tensor in terms of lines [START_REF] Hartley | Lines and points in three views and the trifocal tensor[END_REF][START_REF] Spetsakis | Structure from motion using line correspondences[END_REF][START_REF] Weng | Motion and structure from line correspondences: closed-form solution, uniqueness, and optimization[END_REF], or the algebraic manipulations traditionally used otherwise [START_REF] Faugeras | On the geometry and algebra of the point and line correspondences between n images[END_REF][START_REF] Shashua | Algebraic functions for recognition[END_REF].

Dual Perspective Projection

The perspective projection process can be decomposed into two mappings: x → ξ = c ∨ x, and ξ → x = ξ ∧ r. Geometrically, the first mapping is the most important one, since the projective structure of the image is independent of the choice of r. In this view, perspective projection maps points onto lines (x → c ∨ x) rather than points, and lines onto planes (δ → c ∨ δ) rather than lines.

It is also useful to consider a dual version of this process:

We first map any plane p different from r onto the line φ where these two planes intersect-that is, p → φ = r ∧ p, then map φ onto the plane p spanned by c and φ-that is, φ → p = φ ∨ c. Whereas (primal) perspective projection maps points onto points, dual perspective projection maps planes onto planes (Fig. 4). In order to model this mapping analytically, we choose an arbitrary but fixed coordinate system for the dual plane c * , and identify it with P 2 * . Selecting a projective basis for c * amounts to picking three linearly independent planes p 1 , p 2 , and p 3 in the bundle of planes passing through c. 2 The image of the plane p is given in this coordinate system by

p T ≈ p T X , where X = [ x 1 x 2 x 3 ] ,
and x 1 = r ∧ p 2 ∧ p 3 , x 2 = r ∧ p 3 ∧ p 1 , and x 3 = r ∧ p 1 ∧ p 2 are points lying in the plane r. The matrix X is what Faugeras et al. [START_REF] Faugeras | The Geometry of Multiple Images[END_REF] call an inverse projection matrix of the projection matrix P with rows p T i . 3 The (primal) perspective image of a line joining two points is the join of their images, and the preimage of a point is a line going through c. In the dual case, the line δ where two planes p and q intersect maps onto the meet δ of their images p and q (see Fig. 5, and note that δ passes through both c and the intersection x of δ with r), and the preimage of a plane p passing through c is the pencil formed by all planes passing through the line φ where p intersects r (Fig. 4). These mappings are characterized by the dual line projection matrix X , defined as follows.

Definition 2 The dual line projection matrix associated with a

4 × 3 matrix X = [x 1 , x 2 , x 3 ] is the 3 × 6 matrix X def = φ T 1 φ T 2 φ T 3
, where

φ 1 = x2 ∨ x3 ≈ r ∧ p 1 , φ 2 = x3 ∨ x1 ≈ r ∧ p 2 , φ 3 = x1 ∨ x2 ≈ r ∧ p 3 .
2 Assuming again that the relative scales of the vectors p i are fixed. 3 Given a perspective projection matrix P, there exists a threeparameter family of inverse projection matrices P † q such that PP † q ≈ Id 3 . They correspond to replacing r by an arbitrary plane q in our definition of the matrix X . In other words, X = P † r . The following proposition states the main properties of the dual line projection matrix. It is a dual statement of Proposition 1, and its proof is omitted.

Proposition 2

The dual line projection matrix X enjoys the following properties: (1) The image of the line δ under the dual perspective projection mapping X is the line δ ≈ X * δ passing through c, where X * is naturally defined as the 3×6 matrix with rows φ * T i (i = 1, 2, 3). (2) The preimage of the plane p passing through c is the pencil of planes whose common line is φ = X T p .

Remark 3

The coordinate vectors for the plane p and the line δ passing through c are expressed here in the dual bases (p 1 , p 2 , p 3 ) and (ξ 1 , ξ 2 , ξ 3 ) for the bundles of planes and lines passing through c. The columns φ 1 , φ 2 , and φ 3 of X T are the Plücker coordinate vectors of three lines that all lie in the plane r, and thus satisfy the corresponding quadratic, bilinear, and trilinear constraints.

Remark 4

It is easy to see that the vector X * δ also defines the point x where δ intersects r in the basis (x1, x2, x3) for this plane. Likewise, the vector X T p defines the line φ where the plane p intersects the retina r in the basis (φ 1 , φ 2 , φ 3 ) for the dual of that plane.

The Absolute Quadratic Complex

The absolute conic-introduced by Chasles to tackle mechanics and optics problems from a projective geometry perspective-is the conic section defined in a metric coordinate system by the equation x 2 1 +x 2 2 +x 2 3 = 0 in the plane at infinity x 4 = 0, and it is (globally) invariant under similarities. This section introduces a new relative of the absolute conic, also invariant under similarities.

Definition 3

The absolute quadratic complex (or AQC) is the set of straight lines that intersect the absolute conic.

The AQC Equation

Let us first show that the absolute quadratic complex is, indeed, a (line) complex of degree two-that is, a set of lines that satisfy both the Klein constraint and a second quadratic equation in Plücker coordinates-and derive its equation in an arbitrary metric coordinate system.

Proposition 3

The AQC is a quadratic complex of rank 3 in L4 . Given a line with Pl ücker coordinate vector δ = (u; v) in a metric coordinate frame, a necessary and sufficient condition for this line to belong to the AQC is that |u| 2 = 0, where |u| denotes the Euclidean norm of the vector u.

Since the absolute conic is invariant under similarities, so is the absolute quadratic complex. Let us now turn to the problem of deriving its equation in an arbitrary projective frame. The following proposition relates projective coordinate changes as they apply to planes, points, and lines.

Proposition 5 The equation of the AQC in a projective coordinate frame separated from a metric one by the homography H = [X , y] is

δ T Ωδ = 0, where Ω ≈ X * T X * .

(1)

Elementary Properties of the AQC

According to Proposition 3, the 6 × 6 symmetric matrix Ω has rank 3. The following proposition spells out its other properties.

Proposition 6

The matrix Ω enjoys the following properties: (1) It maps lines onto lines. (2) Its entries Ω ij satisfy the linear constraint Ω 14 + Ω 25 + Ω 36 = 0. (3) Its columns are the Plücker coordinate vectors of six lines in the bundle defined by the three columns of X * T .

Remark 5

In particular, the symmetric matrix Ω is defined (up to scale) by 19 linearly independent parameters, and its columns satisfy the quadratic, bilinear, and trilinear constraints associated with a line bundle. Since any four lines in a bundle are linearly dependent, Proposition 6 captures the fact that Ω has rank 3.

Triggs [START_REF] Triggs | Auto-calibration and the absolute quadric[END_REF] showed that the absolute quadric formed by the planes tangent to the absolute conic could be used to compute the angle between two planes. As shown by Proposition 8 below, the absolute quadratic complex enjoys a similar property for lines. Let us first state a simple corollary of Proposition 4.

Proposition 7

Consider a projective frame (p) and an affine frame (a) such that the corresponding plane coordinate vectors are related by a p T ≈ p p T H, where H = [X , y] is a nonsingular 4×4 matrix. The coordinate vectors of a finite line and its affine direction in these two coordinate systems are related by a u ≈ X * p δ.

Remark 6

This result easily follows from Proposition 4. Geo- metrically, it is also rather obvious: By definition, the first three columns of H are the coordinate vectors in (p) of the points at infinity with coordinate vectors (1, 0, 0, 0) T , (0, 0, 0, 1) T , and (0, 0, 1, 0) in (a). According to Remark 4, X * thus maps the line with coordinate vector p δ onto the coordinate vector of its intersection with the plane at infinity (i.e., its point at infinity, or, equivalently, its affine direction) in the basis of the plane at infinity formed by these three points, which is by definition a u.

Applying Proposition 7 to a metric coordinate system shows that δ T Ωδ is the metric dot product between the directions of the finite lines δ and δ , and it follows immediately that: 4

Proposition 8

The angle θ between the directions of two finite, oriented lines δ and δ is given by

cos θ = δ T Ωδ δ T Ωδ δ T Ωδ . ( 2
)

Applications to Autocalibration 4.1 Autocalibration and the Absolute Quadric

The image lines tangent to the perspective projection of the absolute conic form a dual conic, whose preimage is a subset of the absolute quadric. The following proposition, due to Triggs [START_REF] Triggs | Auto-calibration and the absolute quadric[END_REF], expresses this property in algebraic terms.

Proposition 9 Given a camera with projection matrix P in some projective coordinate frame, the absolute quadric Ω * and the dual ω * of the image of the absolute conic are related by the equation

PΩ * P T ≈ ω * . ( 3
)
It is easy to show that the absolute quadric is given by the rank-3 symmetric matrix Ω * = X X T , where H = [X , y] is the metric upgrade matrix that maps the projective coordinate frame where P is estimated onto a metric one. The matrix H is only defined up to a similarity, and a valid upgrade is obtained from an estimate of Ω * by taking X to be the square root of this matrix (or its opposite), and y = 0. As shown by Triggs [START_REF] Triggs | Auto-calibration and the absolute quadric[END_REF], the instances of Eq. ( 3) associated with m images of a scene and some projective reconstruction of the corresponding projection matrices provide 5m independent bilinear constraints on the absolute quadric Ω * and the cameras' internal parameters as captured by the matrix ω * . When the latter are arbitrary but fixed, a unique solution can be estimated from at least 3 images by enforcing a priori the rank deficiency of Ω * via nonlinear constrained optimization [START_REF] Triggs | Auto-calibration and the absolute quadric[END_REF]. When the intrinsic parameters are allowed to vary but the principal point (u 0 , v 0 ) T is known, one can take u 0 = v 0 = 0, and the corresponding entries of ω * provide two linear constraints on Ω * , which can be estimated using linear least squares from at least 6 images, before enforcing a posteriori the rank deficiency condition, as proposed by Pollefeys et al. [START_REF] Pollefeys | Self-calibration and metric reconstruction in spite of varying and unknown internal camera parameters[END_REF]. Constraints on the skew γ and magnifications α and β can also be incorporated in this approach [START_REF] Pollefeys | Surviving dominant planes in uncalibrated structure and motion recovery[END_REF], but the principal point must always be known for the corresponding equations to be linear.

Autocalibration and the AQC

Typical digital cameras have rectangular pixels (zero skew, γ = 0) or square ones (zero skew and unit aspect ratio, γ = 0 and α = β), but their focal length may vary through zooming, and the principal point is rarely known accurately due to small manufacturing flaws. However, enforcing zero skew and unit aspect-ratio constraints via the absolute quadric is difficult, because these parameters are mixed with the principal point in ω * . As shown in the rest of this section, the absolute quadratic complex solves this problem. Let us first establish a result similar to Proposition 9, but involving ω instead of its dual. By construction, the preimage of any point on the perspective projection of the absolute conic belongs to the AQC, and it follows immediately from Propositions 1 and 5 that: Proposition 10 Given a camera with projection matrix P in some projective coordinate frame, the corresponding line projection matrix P, the absolute quadratic complex Ω, and the image ω of the absolute conic are related by the equation

PΩP T ≈ ω. ( 4
)
It is easy to show that setting u 0 = v 0 = 0 provides two linear constraints on Ω, namely ξ T 1 Ωξ 3 = ξ T 2 Ωξ 3 = 0, where the vectors ξ i (i = 1, 2, 3) denote as before the columns of P. More interestingly, assuming zero skew and unit aspect ratio gives ω a very simple form, namely

ω ≈ 1 0 a1 0 1 a2 a1 a2 a3
, where a 1 = -u 0 , a 2 = -v 0 , and a 3 = α 2 + u 2 0 + v 2 0 , leading to the simple autocalibration algorithms for cameras with square pixels presented in the next section.

Algorithms

Eliminating the unknown scale factor separating the leftand right-hand sides of Eq. ( 4) yields two independent homogeneous linear equations in Ω alone, namely

ξ T 1 Ωξ 1 = ξ T 2 Ωξ 2 and ξ T 1 Ωξ 2 = 0, (5)
and three bilinear ones (two of which are linearly independent) in Ω and a = (a 1 , a 2 , a 3 ) T , namely

⎡ ⎣ ξ T 1 Ωξ 3 ξ T 2 Ωξ 3 ξ T 3 Ωξ 3 ⎤ ⎦ × a = 0. (6)
Let us consider a camera with square pixels but unknown (and possibly varying) focal length and principal point. In this case, Eq. ( 5) can be used to estimate the matrix Ω (up to scale) via homogeneous linear least squares from at least 10 images, enforcing the fact that it has rank 3 a posteriori via singular value decomposition. The matrix X * can then be computed as the square root of Ω (or its opposite if Ω is negative), and the upgrade matrix X is then easily computed using linear least squares. This is exactly the quasi-linear algorithm originally proposed by Ponce in [START_REF] Ponce | Metric upgrade of a projective reconstruction under the rectangular pixel assumption[END_REF], but derived here through completely different means. When all intrinsic parameters are constant, on the other hand, both Eqs. ( 5) and ( 6) can be used to simultaneously recover Ω and a (up to scale) from at least 6 images via nonlinear optimization, rank constraints on Ω being imposed a posteriori.

Implementation and Results

We have implemented the two methods proposed in the previous section, and compared them using real data consisting of 2480 points tracked in 196 images of a Teddy bear, acquired by a 480 × 720pixel 2 Canon XL1 digital camcorder with fixed (but unknown) focal length. The projective reconstruction of the corresponding scene structure and camera motion was obtained using the iterative method described in [START_REF] Mahamud | Provablyconvergent iterative methods for projective structure from motion[END_REF]. Figure 6 shows the results of this experiment. As shown by the figure, the non-linear variant of our approach (dubbed Aqc-2 from now on) gives a reasonable metric reconstruction of the Teddy bear from 7 images only, whereas the quasi-linear algorithm (dubbed Aqc-1) proposed in [START_REF] Ponce | Metric upgrade of a projective reconstruction under the rectangular pixel assumption[END_REF] fails in this case. When 20 or more images are available, the reconstructions obtained by the two algorithms are almost indistinguishable.

Our next experiment gives a quantitative comparison of these algorithms with the quasi linear technique proposed by Pollefeys et al. for cameras with known principal point, zero skew, and unit aspect ratio. The two variants of this algorithm proposed in [START_REF] Pollefeys | Self-calibration and metric reconstruction in spite of varying and unknown internal camera parameters[END_REF] and [START_REF] Pollefeys | Surviving dominant planes in uncalibrated structure and motion recovery[END_REF] are dubbed Pol98 and Pol02 in this section. Pol02 uses some reasonable guess as a prior for the focal length (e.g., 50mm for a 35mm camera), which boils down to assuming that all intrinsic parameters are known, albeit with different degrees of certainty. 5 The data used in this experiment consists of 72 images of 98 points regularly spaced on the surface of a 30 × 30 × 30cm 3 cube centered at the origin and observed by a 35mm camera with a resolution of 400 × 600pixel 2 and a focal length of 50mm (Figure 7). The image data is corrupted with additive zero-mean Gaussian noise with a standard deviation σ ranging from 0 to 5 pixels. A sample reconstruction obtained by Aqc-1 for σ = 2 is shown in the left part of the figure, along with the recovered camera configurations. Sample reconstructions for the other algorithms are omitted since they are visually indistinguishable from this one at this noise level. We have also measured the distances between the original 3D points and the recovered ones after alignment via a similarity transformation. These distances, averaged over all points and 100 trials, are plotted as a function of σ in the right part of Figure 7. The projective structure-frommotion process (dubbed Proj in the figure) itself is sensitive to noise, and the corresponding reconstruction errors after alignment via a projective transformation are included in the error plot as a baseline for comparison with the upgrade algorithms. We have also included in the figure the results of the non-linear algorithm proposed in [START_REF] Ponce | Metric upgrade of a projective reconstruction under the rectangular pixel assumption[END_REF] (and dubbed Aqc-3 here) that takes the output of Aqc-1 as a starting point, and uses variants of Eq. ( 2) to explicitly enforce the zero skew and unit aspect-ratio constraints. Figure 7 shows that Aqc-3 performs best for this data set, and Pol98 performs worse. Finally, we have conducted another quantitative experiment with real data recorded by a hand-held Canon XL1 digital camcorder, and consisting of 1200 points tracked in 125 images of a toy Star Trek tricorder. The five metric upgrade algorithms output reasonable reconstructions of the tricorder. A (cropped) input image is shown in Figure 8, along with a sample reconstruction obtained by Aqc-1, rendered both as a point cloud and a texture-mapped triangulated surface. The second row of the figure compares, for the five algorithms, the mean (θ) and standard deviation (σ θ ) of the recovered values of 18 right angles between pairs of 14 edges identified manually on the tricorder surface, as well as the mean (r) and standard deviation (σ r ) of the ratios between the true lengths of these edges and the recovered ones (remember that the absolute scale of a scene cannot be recovered by structure-from-motion algorithms). We characterize the "linear" error associated with each algorithm by the corresponding σ r /r value. The mean skew (s) and aspect-ratio (a) of the recovered projection matrices are also given for each method. Aqc-1, Aqc-3, and Pol02 perform the best in this experiment, and all give very good results. These preliminary experiments suggest that algorithms based on the absolute quadratic complex provide a vi-able alternative to the quasi linear methods of Pollefeys et al. [START_REF] Pollefeys | Self-calibration and metric reconstruction in spite of varying and unknown internal camera parameters[END_REF][START_REF] Pollefeys | Surviving dominant planes in uncalibrated structure and motion recovery[END_REF], without the guesswork involved in supplying the position of the principal point. More experiments are needed to ascertain the merits of the two approaches. At this point, picking one over the other is probably more a matter of philosophical preference (using a minimum number of constraints that are known to be satisfied vs using more constraints that may not be strictly satisfied but stabilize the numerical estimation process) than an engineering decision supported by hard experimental evidence.

Figure 2 :

 2 Figure 2: Perspective projection. See text for details.

Figure 3 :Proposition 1 Remark 2

 312 Figure 3: Line projection. See text for details.

Figure 4 :

 4 Figure 4: Dual perspective projection. See text for details.

Figure 5 :

 5 Figure 5: Dual line projection. See text for details.

Proposition 4

 4 Consider two projective coordinate frames (a) and (b) such that the corresponding plane coordinate vectors are related by b p T ≈ a p T H, where H = [X , y] is a nonsingular 4 × 4 matrix, and X and y are respectively a 4 × 3 matrix and a vector in R 4 . The corresponding coordinate transformations for points and lines are respectively expressed by b x ≈ H -1a x and b δ ≈ H a δ, where H def = X * Z * , and Z = (y ∨ x1) T (y ∨ x2) T (y ∨ x3) T . H is what Bartoli and Sturm [2] call the 3D line motion matrix associated with H -1 , although their parameterization of this matrix is different from ours. Let us consider projective and metric frames (p) and (m), and denote by H the homography such that m p T ≈ p p T H. The following result is an immediate corollary of Propositions 3 and 4.

Figure 6 :

 6 Figure 6: Metric reconstructions of a Teddy bear using (top) Aqc-2 with 7 and 20 input images, and (bottom) Aqc-2 and Aqc-1 with 196 input pictures. One of the (cropped) input images is shown in the top row.

Figure 7 :

 7 Figure 7: Experimental results with synthetic data. See text for details.

  5 • 19.0 • 3.55 0.58 16.46% 16.2 • 1.31 Pol02 89.7 • 2.9 • 4.39 0.40 9.1% 2.5 • 0.97 Aqc-1 90.1 • 1.4 • 12.79 1.03 8.0% 2.1 • 1.01 Aqc-2 91.7 • 18.3 • 11.38 1.26 11.1% 4.5 • 1.06 Aqc-3 89.8 • 2.7 • 9.87 0.88 8.9% 0.0 • 1.00

Figure 8 :

 8 Figure 8: Experimental results with a toy tricorder. See text for details.

A similar line of reasoning applies to planes: According to Remark 4, X T p is the intersection of the plane p with the plane at infinity, i.e., its line at infinity, and it follows immediately that the metric dot product of two plane normals is p T Ω * p, a fact already noted by Triggs[START_REF] Triggs | Auto-calibration and the absolute quadric[END_REF].

For example, the zero-skew constraint, which is known to be satisfied, is given a weight of 100, while the focal length constraint, which is just used to give a reasonable prior, is given a weight of 1/9, the weights for the remaining constraints falling in between.Aqc-1 and Aqc-2 give comparable results, and do slightly worse than Pol02 at low noise levels, and slightly better at high noise levels.

Acknowledgments. This work was supported in part by the Beckman Institute, the National Science Foundation under ITR grant IIS-0312438, the UIUC/CNRS/INRIA collaboration agreement, and a grant from the Consulat Général de France in Chicago. Many thanks to Lana Lazebnik, and Peter Sturm for useful discussions and comments.

Appendix: Line Trilinearities

A necessary and sufficient condition for three lines λ, µ, and ν to be coplanar is that there exists a vector p = 0 such that [λ ∧ ]p = [µ ∧ ]p = [ν ∧ ]p = 0, or, equivalently, that all 4 × 4 minors of the 12 × 4 matrix obtained by stacking these three equations have zero determinants. It is easywith the aid of Maple-to show that these determinants can in fact all be written as linear combinations of four 3 × 3 determinants T 453 , T 426 , T 156 , and T 123 , where

In particular, the fact that λ, µ, and ν are coplanar is characterized by the four trilinear constraints

The fourth constraint is not particularly surprising since, for finite lines, it simply enforces the coplanarity of the lines' directions. By duality, triples of lines in the same bundle are characterized by

the changes in indices corresponding to swapping the u and v components of Plücker coordinate vectors in dual lines.

Since three lines lying in the same plane or passing through the same point are pairwise coplanar, the corresponding bilinear constraints are redundant. Conversely, it is easy to show that when these bilinear constraints are enforced separately, one of the four trilinear constraints characterizing triples of lines in the same bundle or in the same plane becomes redundant.


Svetlana Lazebnik
email: slazebni@uiuc.edu

Cordelia Schmid
email: cordelia.schmid@inrialpes.fr

Jean Ponce
email: ponce@cs.uiuc.edu

A Maximum Entropy Framework for Part-Based Texture and Object Recognition

This paper presents a probabilistic part-based approach for texture and object recognition. Textures are represented using a part dictionary found by quantizing the appearance of scale-or affine-invariant keypoints. Object classes are represented using a dictionary of composite semi-local parts, or groups of neighboring keypoints with stable and distinctive appearance and geometric layout. A discriminative maximum entropy framework is used to learn the posterior distribution of the class label given the occurrences of parts from the dictionary in the training set. Experiments on two texture and two object databases demonstrate the effectiveness of this framework for visual classification.

Introduction

By analogy with a text document, an image can be viewed as a collection of parts or "visual words" drawn from a "part dictionary." This parallel has been exploited in recent bag-of-keypoints approaches to visual categorization [START_REF] Csurka | Visual Categorization with Bags of Keypoints[END_REF] and video retrieval [START_REF] Sivic | Video Google: A Text Retrieval Approach to Object Matching in Videos[END_REF]. More generally, image representations based on keypoints, or salient regions, have shown promise for recognizing textures [START_REF] Lazebnik | A Sparse Texture Representation Using Local Affine Regions[END_REF] and object classes [START_REF] Agarwal | Learning a Sparse Representation for Object Detection[END_REF][START_REF] Dorko | Selection of Scale-Invariant Parts for Object Class Detection[END_REF][START_REF] Fergus | Object Class Recognition by Unsupervised Scale-Invariant Learning[END_REF]. For textures, the appearance of local regions is clustered to form characteristic texture elements, or textons. For objects, such clusters can also play the role of generic object parts, though in our previous work [START_REF] Lazebnik | Semi-local Affine Parts for Object Recognition[END_REF], we have introduced a more expressive representation based on composite semi-local parts, defined as geometrically stable configurations of multiple keypoints that are robust against approximately rigid deformations and intra-class variations.

In the present work, our goal is to develop probabilistic learning and inference techniques for reasoning about object and texture models composed of multiple parts. To this end, we adopt a discriminative maximum entropy framework, which has been used successfully for text document classification [START_REF] Berger | A Maximum Entropy Approach to Natural Language Processing[END_REF][START_REF] Nigam | Using Maximum Entropy for Text Classification[END_REF] and image annotation [START_REF] Jeon | Using Maximum Entropy for Automatic Image Annotation[END_REF]. This framework has several characteristics that make it attractive for visual categorization as well: It directly models the posterior distribution of the class label given the image, leading to convex (and tractable) parameter estimation; moreover, classification is performed in a true multi-class fashion, requiring no distinguished background class. Because the maximum entropy framework makes no independence assumptions, it offers a principled way of combining multi-ple kinds of features (e.g., keypoints produced by different detectors), as well as inter-part relations, into the object representation. While maximum entropy has been widely used in the computer vision for generative tasks, e.g., modeling of images as Markov random fields [START_REF] Zhu | Filters, Random Fields, and Maximum Entropy (FRAME): Towards a Unified Theory for Texture Modeling[END_REF], where it runs into issues of intractability for learning and inference, it can be far more efficient for discriminative tasks, e.g. [START_REF] Keysers | Maximum Entropy and Gaussian Models for Image Object Recognition[END_REF][START_REF] Mahamud | Combining Simple Discriminators for Object Discrimination[END_REF]. In this paper, we explore maximum entropy in a part-based setting. We begin in Section 2 by reviewing the basics of maximum entropy. Sections 3 and 4 describe our application of the framework to texture and object recognition, and Section 5 concludes with a summary and discussion of future directions.

The Maximum Entropy Framework

A discriminative maximum entropy approach seeks to estimate the posterior distribution of the class label given the image features that matches the statistics of the features observed in the training set, and yet remains as uniform as possible. Intuitively, such a distribution properly reflects our uncertainty about making a decision given ambiguous image data. Suppose that we have defined a set of feature functions f k (I, c) that depend both on the image I and the class label c (specific definitions will appear in Sections 3 and 4). To estimate the posterior of the class label given the features, we constrain the expected values of the features under the estimated distribution P (c|I) to match those observed in the training set T . The observed "average" value of feature f k in the training set T is

fk = 1 |T | I∈T f k (I, c(I)) .
Given a particular posterior distribution P (c|I), the expected value of f k , taken with respect to the observed empirical distribution P (I) over the training set, is

E[f k ] = 1 |T | I∈T c P (c|I)f k (I, c) .
We seek the P (c|I) that has the maximum conditional entropy H = -1

|T | I∈T

c P (c|I) log P (c|I) subject to the constraints E[f k ] = fk . It can be shown that the desired distribution has the exponential form

P (c|I) = 1 Z exp k λ k f k (I, c) , (1)
where

Z = c exp ( k λ k f k (I, c
)) is the normalizing factor,1 and λ k are parameters whose optimal values are found by maximizing the likelihood of the training data under the exponential model [START_REF] Agarwal | Learning a Sparse Representation for Object Detection[END_REF]. This optimization problem is convex and the global maximum can be found using the improved iterative scaling (IIS) algorithm [START_REF] Berger | A Maximum Entropy Approach to Natural Language Processing[END_REF][START_REF] Nigam | Using Maximum Entropy for Text Classification[END_REF]. At each iteration of IIS, we compute an update δ k to each λ k , such that the likelihood of the training data is increased. The derivation of updates is omitted here, but it can be shown [START_REF] Berger | A Maximum Entropy Approach to Natural Language Processing[END_REF][START_REF] Nigam | Using Maximum Entropy for Text Classification[END_REF] that when the features are normalized, i.e., when k f k (I, c) is a constant S for all I and c, updates can be found efficiently in closed form:

δ k = 1 S log fk -log E λ [f k ] . ( 2
)
In the present work we will use only normalized features.

Because of the form of ( 2), zero values of fk cause the optimization to fail, and low values cause excessive growth of the weights. This tendency to overfit can be alleviated by adding a zero-mean Gaussian prior on the weights [START_REF] Nigam | Using Maximum Entropy for Text Classification[END_REF]. However, in our experiments, we have achieved better results with a basic IIS setup where simple transformations of the feature functions are used to force expectations away from zero. Specifically, for all the feature functions defined in Sections 3 and 4, we use Laplace smoothing, i.e., adding one to each feature value and renormalizing. To simplify the subsequent presentation, we will omit this operation from all feature function definitions.

In practice, it is often convenient to define feature functions based on class-independent features g k (I):

f d,k (I, c) = g k (I) if c = d, 0 otherwise.
Then we have

P (c|I) = Z -1 exp d,k λ d,k f d,k (I, c) = Z -1 exp ( k λ c,k g k (I)
) . Thus, "universal" features g k become associated with class-specific weights λ c,k . All our feature functions will be defined in this way.

Texture Recognition

Feature Functions

We use a sparse image representation [START_REF] Lazebnik | A Sparse Texture Representation Using Local Affine Regions[END_REF] based on scale-or affine-invariant keypoints (regions shaped like circles and ellipses, respectively). A texton dictionary is formed by clustering appearance-based descriptors of keypoints, and each descriptor from a training or test image is then assigned the label of the closest cluster center. Implementation details of these steps will be given in Section 3.2.

In text classification, feature functions are typically based on scaled counds of word occurrences [START_REF] Nigam | Using Maximum Entropy for Text Classification[END_REF]. By analogy, we define feature functions using texton frequencies:

g k (I) = N k (I) k N k (I)
,

where N k (I) is the number of times texton label k occurs in the image I. To enrich the feature set, we also define functions g k, that encode the probability of co-occurrence of pairs of labels at nearby locations. Let k denote the event that a region labeled is adjacent to a region labeled k. Specifically, we say that k if the center of is contained in the neighborhood obtained by "growing" the shape (circle or ellipse) of the kth region by a constant factor (4 in the implementation). Also, let N k (I) denote the number of times the relation occurs in the image I. Then we set

g k, (I) = N k (I) k , N k (I)
.

An image model incorporating co-occurrence counts of pairs of adjacent labels is a counterpart of a bigram language model that estimates the probabilities of two-word strings in natural text. Just as in language modeling, we must deal with sparse probability estimates due to many relations receiving extremely low counts in the training set. Thus, we are led to consider smoothing techniques for probability estimates [START_REF] Chen | An Empirical Study of Smoothing Techniques for Language Modeling[END_REF]. One of the most basic techniques, interpolation with marginal probabilities, leads to the following modified definition of the co-occurrence features:

gk, (I) = (1-α)g k, (I)+α g k, (I) k g k , (I) ,
where α is a constant (0.1 in our implementation). While smoothing addresses the problem of unreliable probability estimates, we are still left with millions of possible cooccurrence relations, and it is necessary to use feature selection to reduce the model to a manageable size. Possible feature selection techniques include greedy selection based on increase of likelihood under the exponential model [START_REF] Berger | A Maximum Entropy Approach to Natural Language Processing[END_REF], mutual information [START_REF] Dorko | Selection of Scale-Invariant Parts for Object Class Detection[END_REF][START_REF] Nigam | Using Maximum Entropy for Text Classification[END_REF] and likelihood ratio [START_REF] Dorko | Selection of Scale-Invariant Parts for Object Class Detection[END_REF]. However, since more frequently occurring relations yield more reliable estimates, we have chosen a simpler likelihood-based scheme: For each class, we find a fixed number of relations that have the highest probability in the training set, and then combine them to get a global "relation dictionary."

Experimental Results

In this section, we show classification results on the Brodatz database (999 images: 111 classes, 9 samples per class) and the UIUC database [START_REF] Lazebnik | A Sparse Texture Representation Using Local Affine Regions[END_REF] (1000 images: 25 classes, 40 samples per class). Figure 1 shows examples of images from the two databases. For the Brodatz database, we use a scale-invariant Laplacian blob detector [START_REF] Lindeberg | Feature Detection with Automatic Scale Selection[END_REF]. For the UIUC database, which contains perspective distortions and nonrigid deformations between samples of the same class, we use an affinely adapted version of the Laplacian detector. In both cases, the appearance of the detected regions is represented using SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF].

To form the texton dictionary, we run K-means clustering on a randomly selected subset of all training descriptors. To limit the memory requirements of the K-means algorithm, we cluster each class separately and concatenate the resulting textons. We find K = 10 and K = 40 textons per class for the Brodatz and the UIUC database, respectively, resulting in dictionaries of size 1110 and 1000. For co-occurrence relations, we select 10K features per class; because the relations selected for different classes sometimes coincide, the total number of g k, features is slightly less than ten times the total number of textons.

Table 1 shows a comparison of classification rates obtained using various methods on the two databases. All the rates are averaged over 10 runs with different randomly selected training subsets; standard deviations of the rates are also reported. The training set consists of 3 (resp. 10) images per class for the Brodatz (resp. UIUC) database. The first row shows results for a popular baseline method using nearest-neighbor classification of texton histograms with the χ 2 distance. The second row shows results for a Naive Bayes baseline using the multinomial event model [START_REF] Mccallum | A Comparison of Event Models for Naive Bayes Text Classification[END_REF]: ) , where P (k|c) is given by the frequency of texton k in the training images for class c. The results for the two baseline methods on the Brodatz database are almost identical, though Naive Bayes has a potential advantage over the χ 2 method, since it does not treat the training samples as independent prototypes, but combines them in order to compute the probabilities P (k|c). This may help to account for the better performance of Naive Bayes on the Brodatz database. The third and fourth rows show results for exponential models based on individual g k (textons only) features and g k, (relations only) features, respectively, and the fifth row shows results for the exponential model with both kinds of features combined. For both databases, the textons-only exponential model performs much better than the two baseline methods; the relations-only models are inferior to the baseline. Interestingly, combining textons and relations does not improve performance. To test whether this is due to overfitting, we compare performance of the g k, features with the smoothed gk, features (last two rows). While the smoothed features do perform better, combining them with textons-only features once again does not bring any improvement. Thus, Overall, the g k exponential model performs the best for both texture databases. For the Brodatz database, our result of 87.37% is comparable to the rate of 87.44% reported in [START_REF] Lazebnik | A Sparse Texture Representation Using Local Affine Regions[END_REF]. Note, however, that the result of [START_REF] Lazebnik | A Sparse Texture Representation Using Local Affine Regions[END_REF] was obtained using a combination of appearance-and shape-based features. In our case, we use only appearance-based features, so we get as much discriminative power with a weaker representation. For the UIUC database, our result of 97.41% exceeds the highest rate reported in [START_REF] Lazebnik | A Sparse Texture Representation Using Local Affine Regions[END_REF], that of 92.61%.

P (I|c) = k P (k|c) N k (I

Object Recognition

Semi-Local Parts

For our texture recognition experiments, Laplacian region detectors have proven to be successful. However, we have found them to be much less satisfactory for detecting object parts with complex internal structures, e.g., eyes, wheels, heads, etc. Instead, for object recognition, we have implemented the scale-invariant detector of Jurie and Schmid [START_REF] Jurie | Scale-invariant Shape Features for Recognition of Object Categories[END_REF], which finds salient circular configurations of edge points, and is robust to clutter and texture variations inside the regions. Just as in Section 3, the appearance of the extracted regions is represented using SIFT descriptors.

For each object class, we construct a dictionary of composite semi-local parts [START_REF] Lazebnik | Semi-local Affine Parts for Object Recognition[END_REF], or groups of several neighboring keypoints whose appearance and spatial configuration occurs repeatably in the training set. The key idea is that consistent occurrence of (approximately) rigid groups of simple features in multiple images is very unlikely to be accidental, and must thus be a strong cue for the presence of the object. Semi-local parts are found in a weakly supervised manner, i.e., from cluttered, unsegmented training images, via correspondence search. The intractable problem of simultaneous alignment of multiple images is reduced to pairwise matching: Candidate parts are initialized by matching several training pairs and then validated against additional images. Matching is accomplished efficiently with the help of strong appearance (descriptor similarity) and geometric consistency constraints (see [START_REF] Lazebnik | Semi-local Affine Parts for Object Recognition[END_REF] for details). Originally, we have introduced semi-local parts in conjunction with affine alignment; however, for the two databases of Section 4.2, scale invariance is sufficient. In the implementation, we still use linear least squares to estimate an affine aligning transformation between the regions in a hypothesized match, and then reject any hypothesis with too much distortion (skew, rotation, anisotropic scaling).

A detected instance of a candidate part in a validation image may have multiple regions missing because of occlusion, failure of the keypoint detector, etc. We define the repeatability ρ k (I) of a detected instance of part k in image I as the number of regions in that instance. If several instances of the part are detected, we select the one with the highest repeatability; if no instance of part k is detected at all, we have ρ k (I) = 0. Next, we compute a validation score for the part by taking the χ 2 distance between the histogram of repeatabilities of the part over the positive class and the histogram of its repeatabilities in all the negative images (for examples of these histograms, see Figures 3 (a) and 4 (a)). The score can range from 1, when the two histograms have no overlap at all, to 0, when they are identical. A fixed number of highest-scoring parts is retained for each class, and their union forms our dictionary. Finally, for each part k and each image I, we compute a normalized feature function based on its repeatability:

g k (I) = ρ k (I) k ρ k (I)
.

Just as in our texture recognition experiments, we also investigate whether, and to what extent, incorporating relations into the object representation improves classification performance. To this end, we define overlap relations between pairs of parts that belong to the same class. Let ω k, (I) be the overlap between detected instances of parts k and in the image I, i.e., the ratio of the intersection of the two parts to their union. This ratio ranges from 0 (disjoint parts) to 1 (coincident parts). Then we define

g k, (I) = ω k, (I) k , ω k , (I)
.

Note that it would be straightforward to define more elaborate relations that take into account the distance, relative scale, or relative orientations of the two parts [START_REF] Agarwal | Learning a Sparse Representation for Object Detection[END_REF]. However, such relations would have less geometric invariance (in particular, they would be unsuitable for non-rigid objects), and would require much more training data to learn reliably.

Experimental Results

This section presents recognition results obtained on two multi-class object databases. The first is a subset of the publicly available CalTech database [START_REF] Fergus | Object Class Recognition by Unsupervised Scale-Invariant Learning[END_REF]. We have taken 300 images each from four classes: airplanes, rear views of cars, faces, and motorbikes (Figure 3). The second database, which we collected from the Web, consists of 100 images each of six different classes of birds: egrets, mandarin ducks, snowy owls, puffins, toucans, and wood ducks (Figure 4). For the CalTech database, 50 randomly chosen images per class are used for creating candidate parts. Each image is paired up to two others, for a total of 100 initialization pairs. Of the several hundred candidate parts yielded by this matching process, the 50 largest ones are retained for training and selection. Candidate parts are then matched against every image from another training set, which also contains 50 randomly chosen images per class, and 20 highest-scoring parts per class are retained to form the part dictionary. The repeatability results of the selected parts on this training set are also used as training data to estimate the parameters of the exponential model. Finally, the remaining 200 images per class make up the test set. We follow the same protocol for the bird dataset, except that 20 images per class are used for finding candidate parts, another 30 for part selection, and the remaining 50 for testing. Unlike the texture recognition results of Section 3.2, the results of this section are not averaged over multiple splits of the databases because of the considerably larger computational expense involved in computing semi-local parts. With our current unoptimized MATLAB implementation, a single run through an entire object database (candidate part computation, part selection, and testing) takes about a week. Parts (a) of Figures 3 and4 illustrate training and part selection. As can be seen from the plots of validation scores for all selected parts, the quality of part dictionaries found for different classes varies widely. Extremely stable, salient parts are formed for faces, motorbikes, and ducks. The classes with the weakest parts are airplanes for the CalTech database and egrets for the bird database. Interestingly, both airplanes and egrets are "thin" objects lacking characteristic texture, so that the keypoints that overlap the object also capture a lot of background, and the SIFT descriptors of these keypoints end up describing mostly clutter.

Tables 2 (a) and (b) show classification performance of several methods with 20 parts per class. The first column of the tables shows the performance of a baseline Naive Bayes approach with likelihood given by P (I|c) = k P (ρ k (I)|c). The distributions P (ρ k |c) are found by histogramming the repeatabilities of part k on all training images from class c. This takes into account the repeatability of parts on images from all classes, not only the class which they describe. Roughly speaking, we expect P (ρ k (I)|c) to be high if part k describes class c and ρ k (I) is high, or if part k does not describe class c and ρ k (I) is low or zero. Thus, to conclude that an object from class c is present in the image, we not only have to observe highrepeatability detections of parts from class c, but also low- repeatability detections of parts from other classes. Note that the exponential model, which encodes the same information in its feature functions, also uses this reasoning.

The second (resp. third, fourth) columns of Tables 2 (a) and (b) show the classification performance obtained with exponential models using the g k features only (resp. the g k, only, g k and g k, combined). For the CalTech database, the Naive Bayes and the exponential parts-only models achieve very similar results, though under the exponential model, airplanes have a lower classification rate, which is intuitively more satisfying given the poor part dictionary for this class. For the bird database, the exponential model outperforms Naive Bayes; for both databases, relations-only features alone perform considerably worse than the parts-only features, and combining parts-based with relation-based features brings no improvement. Figure 2 shows a plot of the classification rate for the exponential model as a function of part dictionary size. Note that adding a part to the dictionary can decrease performance. This behavior may be an artifact of our scoring function for part selection, which is not directly related to classification performance. In the future, we plan to experiment with part selection based on increase of likelihood under the exponential model [START_REF] Berger | A Maximum Entropy Approach to Natural Language Processing[END_REF].

Though we did not conduct a quantitative evaluation of localization accuracy, the reader may get a qualitative idea by examining parts (b) and (c) of Figures 3 and4

Summary and Future Work

In this paper, we have presented a part-based approach to texture and object recognition using a discriminative maximum entropy framework. Our experiments have shown that the exponential model works well for both textures and objects. The classification rate achieved by our method on the UIUC database exceeds the state of the art [START_REF] Lazebnik | A Sparse Texture Representation Using Local Affine Regions[END_REF], and our results on the four CalTech classes are comparable to others in recent literature [START_REF] Csurka | Visual Categorization with Bags of Keypoints[END_REF][START_REF] Dorko | Selection of Scale-Invariant Parts for Object Class Detection[END_REF]. Interestingly, while all our recognition experiments used small training sets (from 3 to 50 images per class), no overfitting effects were observed. In addition, we have found that the Naive Bayes method, which we used as a baseline to evaluate the improvement provided by the exponential model, can be quite powerful in some cases -a finding that is frequently expresssed in the document classification literature [START_REF] Mccallum | A Comparison of Event Models for Naive Bayes Text Classification[END_REF][START_REF] Nigam | Using Maximum Entropy for Text Classification[END_REF].

The most important negative result of this paper is the lack of performance improvement from co-occurrence and overlap relations. Once again, this is consistent with the conventional wisdom in the document classification community, where it was found that for document-level discrimination tasks, a simple orderless "bag-of-words" represententation is effective. For textures, we expect that cooccurrence features may be helpful for distinguishing between different textures that consist of local elements of similar appearance, but different spatial layouts. For object recognition, the lack of improvement from relations can be ascribed, at least partly, to the strong geometric consistency constraints already captured by semi-local parts. For weaker "atomic" parts, relations have indeed been shown to improve performance [START_REF] Agarwal | Learning a Sparse Representation for Object Detection[END_REF]. We currently conjecture that combined with our semi-local part representation, overlap relations may be more useful for localization than for recognition. The key goal of our future experiments is to test this conjecture experimentally.

Figure 1 .

 1 Figure 1. Examples of five classes from the Brodatz database (left) and the UIUC database (right).

Figure 2 .

 2 Figure 2. Classification rate (exp. parts) as a function of dictionary size: CalTech database (left), birds database (right). For the CalTech database, because three of the four classes have extremely strong and redundant parts, performance increases very little as more parts are added. For the bird database, diminishing returns set in as progressively weaker parts are added.

  Modeling and part selection (see caption below). (b) Correctly classified examples under the exponential parts-only model. (c) Misclassified examples.

Figure 3 .

 3 Figure 3. CalTech results. (a) First row: highest-scoring part for each class. The two training images that were originally matched to obtain the part are shown side by side, with the matched regions (yellow circles) superimposed. The aligning transformation between the two groups of matches is indicated by the bounding boxes: the axis-aligned box in the left image is mapped onto the parallelogram in the right image. (Recall that we use an affine alignment model and then discard any transformation that induces too much distortion.) Second row, left of each column: repeatability histograms for the top part. The solid red line (resp. dashed blue line) indicates the histogram of repeatability rates of the part in all positive (resp. negative) training images. Recall that the validation score of the part is given by the χ 2 distance between the two histograms. Second row, right of each column: plot of top 20 part scores following validation. (b) Three examples of correctly classified images per class. Left of each column: original image. Right of each column: transformed bounding boxes of all detected part instances for the given class superimposed on the image. Localization is poor for airplanes and very good for faces (notice the examples with closed eyes and a changed facial expression). For motorbikes, the front wheel is particularly salient. (c) Examples of misclassified images.

Table 1 .

 1 Texture classification results (see text). texton-only features clearly supercede the co-occurrence relations. With these features, 100% recognition rate is achieved by 61 classes from the Brodatz database and by 8 classes from the UIUC database.

		Brodatz database	UIUC database
		Mean (%)	Std. dev.	Mean (%)	Std. dev.
	χ 2	83.09	1.18	94.25	0.59
	Naive Bayes	85.84	0.90	94.08	0.67
	Exp. g k	87.37	1.04	97.41	0.64
	Exp. g k,	75.20	1.34	92.40	0.93
	Exp. g k + g k,	83.44	1.17	97.19	0.57
	Exp. gk,	80.51	1.09	95.85	0.62
	Exp. g k + gk,	83.36	1.14	97.09	0.47

Table 2 .

 2 Classification rates for (a) CalTech (top) and (b) birds (bottom) using 20 parts per class (see text).

	CalTech	Naive	Exp.	Exp.	Exp. parts &
	database	Bayes	parts	relations	relations
	Airplanes	98.0	88.0	78.0	87.5
	Cars (rear)	95.5	99.5	90.5	99.5
	Faces	96.5	98.5	96.5	98.0
	Motorbikes	97.5	99.5	83.0	99.5
	All classes	96.88	96.38	87.0	96.13
	Birds	Naive	Exp.	Exp.	Exp. parts &
	database	Bayes	parts	relations	relations
	Egret	68	90	72	88
	Mandarin	66	90	66	90
	Snowy owl	66	98	52	96
	Puffin	88	94	94	94
	Toucan	88	82	82	82
	Wood duck	96	100	86	100
	All classes	78.67	92.33	75.33	91.67
	1			1
	0.9			0.9
	0.7 0.8 Recognition rate			0.7 0.8 Recognition rate
	0.6	relations only parts only		0.6	relations only parts only
	1 2 4 6 8 10 12 14 16 18 20 0.5 parts and relations	1 2 4 6 8 10 12 14 16 18 20 0.5 parts and relations
		Parts per class		Parts per class

Note that Z involves only a sum over the classes, and thus can be computed efficiently. If we were modeling the distribution of features given a class instead, Z would be a sum over the exponentially many possible combinations of feature values -a major source of difficulty for the generative approach. By contrast, the discriminative approach described here is more related to logistic regression. It is easy to show that (1) yields binary logistic discrimination in the two-class case.

Acknowledgments. This research was supported by Toyota, National Science Foundation grants IIS-0308087 and IIS-0312438, the European project LAVA (IST-2001-34405), and the CNRS-UIUC Collaboration Agreement.

Mandarin