Vincenzo Caglioti

Pierluigi Taddei

Giacomo Boracchi

Simone Gasparini

Alessandro Giusti

Single-Image Calibration of Off-Axis Catadioptric Cameras Using Lines

We present a novel calibration method for off-axis catadioptric cameras, i.e. standard perspective cameras placed in a generic position w.r.t. an axial-symmetric mirror of unknown shape. The proposed method estimates the intrinsic parameters of the natural perspective camera, the 3D shape of the mirror and its pose w.r.t. the camera.

The peculiarity of our approach is that, unlike several other calibration methods, we do not require any cross section of the mirror to be visible in the image. Instead, we require that the catadioptric image contains at least the image of one generic space line. We then derive some constraints that, combined with the harmonic homology relating the apparent contours of the mirror, allow us to calibrate the off-axis camera. We provide experimental results both on synthetic and camera images that prove the validity of the technique.

Introduction

We present a novel method for calibrating non-central catadioptric cameras with an axial-symmetric mirror whose profile 1 is unknown. In catadioptric cameras the viewing rays coming from the scene are reflected by the mirror before they pass through the camera viewpoint and they cross the image plane. A catadioptric camera is said to be calibrated if the viewing ray associated to each image point is known.

Catadioptric cameras where all the viewing rays are concurrent to the same point are said to be central, as stated by Baker and Nayar [START_REF] Baker | A theory of singleviewpoint catadioptric image formation[END_REF]. Their mirror is a quadric of revolution, with the viewpoint of the perspective camera placed at one of its foci.

In noncentral cameras viewing rays are not all concurrent at a common point. In this paper we consider non- 1 By profile, we mean the SOR generator central catadioptric cameras, whose mirror is a surface of revolution (SOR) of unknown profile (axial symmetric mirrors are easy to manufacture). In particular, we consider off-axis catadioptric cameras, i.e. cameras whose viewpoint is placed at a generic position out of the mirror axis. Unlike central cameras, noncentral cameras allow one to localize space lines [START_REF] Caglioti | How many planar viewing surfaces are there in noncentral catadioptric cameras?" Towards singe-image localization of space lines[END_REF][START_REF] Lanman | Reconstructing a 3d line from a single catadioptric image[END_REF] or spheres [START_REF] Caglioti | Determining radius and position of a sphere from a single catadioptric image[END_REF] from a single image. This peculiarity makes them particularly suited for the 3D reconstruction of indoor scenes: in fact, the single-image approach, unlike methods based on multiple views, does not require the solution of the correspondence problem, and, unlike laser-based methods, is not invasive. Obviously, for 3D reconstruction, a calibrated system is needed.

Several calibration methods exist for central catadioptic cameras, most of which depend on the mirror shape and exploit images of lines [START_REF] Geyer | Paracatadioptric camera calibration[END_REF][START_REF] Ying | Simultaneously calibrating catadioptric camera and detecting line features using hough transform[END_REF], spheres [START_REF] Ying | Linear catadioptric camera calibration from sphere images[END_REF] or calibration patterns [START_REF] Kang | Catadioptric self-calibration[END_REF]. Rather few methods have been proposed for calibrating noncentral cameras; the first attempt was made by Aliaga [START_REF] Aliaga | Accurate catadioptric calibration for realtime pose estimation in room-size environments[END_REF] who introduced a paracatadioptric camera calibration method that relaxes the assumption of the perfect orthographic projection and placement. Later, Mashita et al. in [START_REF] Mashita | Calibration method for misaligned catadioptric camera[END_REF] presented a calibration method for noncentral catadioptric cameras based on a SOR mirror. In particular, they devised a localization procedure for an off-axis catadioptric camera based on an hyperboloidal mirror [START_REF] Yamazawa | Omnidirectional imaging with hyperboloidal projection[END_REF]. Their method estimates the extrinsic parameters of the camera, i.e. the mirror pose with respect to the camera, using the imaged ellipse corresponding to a circular cross section of the mirror; they exploit the calibration method devised for standard perspective cameras by Chen et al. [START_REF] Chen | Camera calibration with two arbitrary coplanar circles[END_REF] and Sun et al. [START_REF] Sun | Planar conic based camera calibration[END_REF]. Both these methods are based on the algorithm described by Kanatani in [START_REF] Kanatani | Geometric computation for machine vision[END_REF], which recovers the 3D orientation of a circle in the scene from its projected image. Sun's method estimates the intrinsic parameters of a standard perspective camera using images with three or more concentric conics under different views. Chen's method estimates the focal length and the extrinsic parameters using a single image with at least two coplanar circumferences. Moreover, Fabrizio et al. in [START_REF] Fabrizio | Calibration of panoramic catadioptric sensors made easier[END_REF] use the mirror boundaries as a calibration pattern for estimating the mirror pose by computing the homographies among the image plane and the planes containing the two boundaries. It is worth noting that all cited methods assume that the mirror profile is exactly known, which requires high manufacturing accuracy.

We propose a calibration method for off-axis cameras, whose mirror has unknown profile. Off axis cameras are not dependent on exact alignment of the camera and mirror, which is often a problem in axial systems. We require a single image, depicting the mirror apparent contours and the catadioptric image of at least one space line in a generic, unknown position. Our method does not require any circular cross section of the mirror to be visible. The image of the mirror axis is obtained by computing the harmonic homology that relates the mirror apparent contours [START_REF] Colombo | Metric 3d reconstruction and texture acquisition of surfaces of revolution from a single uncalibrated view[END_REF]. Then we exploit additional constraints deriving from the image of a space line: in fact, the viewing rays associated to these image points have to intersect a single space line. Thus, we recover the intrinsic camera parameters, the camera position w.r.t. the mirror axis and the mirror profile.

After formalizing the problem in Section 2, we detail the proposed calibration method and its implementation in Sections 3, 4 and 5. In Section 6 we present some experimental results validating the method, while Section 7 concludes and presents ongoing works.

Problem formulation

We consider an off-axis catadioptric camera, based on a natural camera (null skew factor and unit apsect ratio 2 ). We assume that the mirror's lateral apparent contour is visible in the image, without requiring that any circular cross section (such as the mirror base, or the mirror top) is visible. Moreover, the catadioptric image of at least a space line must be available; we also assume that this line satisfies the broad conditions in [START_REF] Caglioti | How many planar viewing surfaces are there in noncentral catadioptric cameras?" Towards singe-image localization of space lines[END_REF].

Our goal is to calibrate the catadioptric system, estimating the intrinsic camera parameters and, up to a scale factor, the mirror profile and the mirror position w.r.t. the camera viewpoint.

In the following section we briefly introduce the harmonic homology and the notation used in the rest of the paper.

Harmonic Homology and Off-axis Cameras

Let π be the symmetry plane containing the mirror axis L and the camera viewpoint O (see Figure 1). Let also γ be the mirror apparent contour. The relation between the points on the two facing parts of γ is described by the harmonic 2 nonunit, but known, aspect ratio can easily be reduced to unit aspect ratio homology H:

H = I -2 v • l T v T • l (1)
being I the 3x3 identity matrix, l the image of the mirror axis, and v the vanishing point of the direction orthogonal to π.

Recently, Colombo et al. in [START_REF] Colombo | Metric 3d reconstruction and texture acquisition of surfaces of revolution from a single uncalibrated view[END_REF] devised a method for computing the harmonic homology given a single perspective image of a SOR. They use the harmonic homology and the image of at least a circular cross section for calibrating a perspective camera. In our work, we use their technique for computing the harmonic homology, and, thus, v and l, which are used as a constraint for camera calibration. On the other hand, we do not assume that a cross section is visible, as detailed in the following section.

Technique

Reduction to two parameters

According to the natural camera assumption, the only intrinsic parameters to be estimated are the principal point and the focal length. Moreover, we exploit l and v, which are derived from γ as previously described. Consider now a generic point p on l: since its viewing ray is orthogonal to the direction represented by vanishing point v, the viewpoint of the perspective camera is constrained to belong to the sphere whose diameter is vp. In particular, let p be the orthogonal projection of v on l: the camera viewpoint O is constrained to belong to the circumference with diameter vp, lying on a plane perpendicular to the image plane.

Let α be the angle between the mirror axis L and its projection l. If the perspective camera is calibrated and α is known, the mirror profile and pose can be determined (see Figure 1). This holds up to a scale factor which we will disregard in what follows; this scale factor can be fixed if any length in the scene (such as the maximum mirror radius) is known.

Once the mirror profile, the camera pose and the camera calibration matrix have been estimated, it is possible to determine the viewing ray associated to any image point. Therefore, in order to calibrate the catadioptric camera, one has to estimate the parameter k (which uniquely defines the perspective camera intrinsic calibration matrix), as well as the angle α. This is accomplished by exploiting the image of a space line, as explained in the following paragraph.

Exploiting the image of a space line

Two image points p and q on γ are said to be corresponding if they are the images of two points on the mirror surface which are symmetric with respect to the plane π. In other words, p and q are the projection of points lying on the same cross section C of the mirror. The harmonic homology H allows us to identify corresponding points on γ. Let p and q be a pair of corresponding points, and let c be the image of C: c is a conic, tangent to γ in p and q. Since the tangents to γ are easily computed, and five constraints determine a planar conic, only one residual parameter defines c. This parameter can be expressed as a function of the two unknowns k and α. In addition, the normal to the mirror surface at any point of C is also known if k and α are given.

Consider six (or more) pairs (p i , q i ) of corresponding points on γ, and consider the image of a space line, consisting in a curve s. Let c i be the imaged cross sections through (p i , q i ), and let b i be the intersection between s and c i : among the named entities, c i , b i and the associated viewing rays can be expressed as functions of the two unknowns. Note that the relationship between the two unknowns and the viewing rays can not be expressed analytically, because s has no analytical form. However, an approximate expression of the partial derivatives of the viewing rays parameters with respect to the unknowns can be obtained; these are then exploited in the subsequent nonlinear minimization (see Section 5).

Consider four of the six viewing rays: there are two possible space lines crossing all the four viewing rays [START_REF] Hilbert | Geometry and the Imagination[END_REF]. These two lines can be also expressed in terms of the two unknown parameters. Two equations in the two unknowns α and k can then be obtained by constraining the two residual viewing rays to cross the same space line. These are sufficient to determine the unknown parameters.

However, for increased robustness, we can use additional constraints which can be obtained by either considering more than six viewing rays from a single image curve, or taking into account multiple images of space lines, when available.

Once the two unknown parameters have been determined, the mirror axis orientation α is known, together with the profile of the part of the mirror whose apparent contours are visible in the image.

Any other cross section whose image does not cross the apparent contour γ is still unknown. These can be reconstructed, provided that they cross the image of at least two lines whose 3D position has already been determined.

Implementation notes

We implemented the calibration method as a nonlinear minimization of an error term e, which we define in the following. For any parameters pair (α, k), we compute the position in space of the mirror axis L, and we recover the mirror profile from γ. Then we consider the image s of a space line and we compute the viewing rays associated to several points of s. These viewing rays constitute a viewing surface.

If we consider a single line, the error term e(α, k) expresses how far the viewing surface is from containing a generic space line; we consider e(α, k) to be the reconstruction error residual r(α, k): it is computed using a robust method for line localization given a set of viewing rays. The method is derived from [START_REF] Caglioti | How many planar viewing surfaces are there in noncentral catadioptric cameras?" Towards singe-image localization of space lines[END_REF] and it is explained in details in [START_REF] Caglioti | Methods for space line localization from single catadioptric images: new proposals and comparisons[END_REF].

In order to improve robustness, more than one image line can be exploited: the error term e(α, k) becomes a weighted average of the reconstruction error residuals r i=1..n . The weight for each viewing surface is given by a nonnegative quadric similarity measure m i=1..n (α, k), which expresses how far the viewing surface is from being a ruled quadric. If the viewing surface is a ruled quadric (m(α, k) = 0), it contains infinite lines besides the viewing rays, therefore the associated residual is not reliable. Conversely, high values of m(α, k) correspond to residuals better related to the quality of the calibration parameters.

In particular, given a set of n image curves s i=1..n , the error term e(α, k) is given by e(α, k)

= n i r i (α, k)/m i (α, k) n i 1/m i (α, k) . (2)
We refer the reader to [START_REF] Caglioti | Methods for space line localization from single catadioptric images: new proposals and comparisons[END_REF] for more details on how to calculate the quadric similarity given a set of straight line lying on a ruled surface.

In order to speed up the process and improve robustness to outliers, it is possible to initially compute the quadric similarity for all surfaces, and evaluating the reconstruction residual only for the subset of surfaces with highest reconstruction quality.

Our implementation of the technique is currently using a stratified approach, in which the camera focal length is known a-priori. The principal point is thus directly determined using the harmonic homology H. In this case, the problem becomes a bounded minimization of the residual error e on the single parameter α. In case k is also consid- ered, we would have to minimize the residual error on k and α simultaneously.

Experimental results

The proposed calibration method has been tested both on synthetic and camera images.

Synthetic images have been generated using the raytracer software POV-Ray [START_REF]Persistency of vision ray tracer (POV-Ray[END_REF]; examples of said images are represented in Figure 2 and Figure 4. These experiments have been designed for validating the calibration method. Therefore we assumed that the mirror axis projection l, the vanishing point v, and the intrinsic camera parameters were known a priori. The mirror apparent contour γ and some images of scene lines have been extracted using the canny edge detector [START_REF] Canny | A computational approach to edge detection[END_REF]. The error term for the considered α values (angles between -90 • and 90 • at 1/6 • step) has been computed with [START_REF] Baker | A theory of singleviewpoint catadioptric image formation[END_REF]. The estimated α value is the one having the minimum error term.

We tested the algorithm on 10 synthetic images, each one obtained with a mirror with a different profile. We used 10 lines in each image for calibration. In the worst case, the estimated α value was 1 • from the ground truth

The method has been used for calibrating an off axis catadioptric camera composed by a 3$, off-the-shelf light bulb which has a reflective coating, and a 10Mpixel Canon EOS 400D camera. Figure 6 shows the experimental setting.

After calibrating the intrinsic camera parameters, we captured the image in Figure 7. The mirror apparent contour γ and the four lines (Figure 7) used for minimization have been extracted using the Canny edge detector. Moreover, the harmonic homology has been computed from γ Also in this case the image of the visible cross section was not exploited using [START_REF] Colombo | Metric 3d reconstruction and texture acquisition of surfaces of revolution from a single uncalibrated view[END_REF], thus recovering l and v. We explored the angle space from 10 • to 90 • at 1/6 • steps. The ground truth in camera test images has been measured (see Figure 6) as about 30 • . The error term is minimized for α = 31.67 • (see Figure 8), yielding satisfactory results.

Conclusion and future works

We presented a single-image calibration method for offaxis catadioptric cameras that only exploits the mirror apparent contour and at least one image of a generic space line. The algorithm has been successfully tested both on synthetic and camera images, confirming its correctness.

Further experiments are underway to explore the parameter space in the case of an uncalibrated natural perspective camera. In this case, minimizing e(k, α) allows us to simultaneously calibrate all the unknown parameters.

Another possible extension is to consider a two mirror catadioptric system. In fact, whenever a space line is visible through both mirrors, we may exploit both viewing surfaces, which gives a better estimation of the reconstructed line [START_REF] Teller | Determining the lines through four lines[END_REF] and a better estimation of the residual error for calibration.

Figure 1 .

 1 Figure 1. The apparent contour on the image plane and a subset of cross sections related to some point of γ are shown.

Figure 2 .

 2 Figure 2. A raytraced mirror; one of the two apparent contours is represented in blue whereas the line image used for the minimization is shown in black. Note a visible cross section (the mirror base), which is not exploited by our technique.

Figure 3 .

 3 Figure 3. Solid line: error among a wide range of values for α; dashed line: related quadric similarity of the viewing surface. Ground truth solution is shown as a vertical dashed line. Note that the reconstruction was only possible in a subset of the total α range (-90 • , 90 • ).

Figure 4 .

 4 Figure 4. A second synthetic image showing the mirror, the extracted profile, represented in blue, and the used line image, shown in black. Also in this case the image of the visible cross section was not exploited

Figure 5 .Figure 6 .

 56 Figure 5. The error and the quadric similarity for the second experiment

Figure 7 .

 7 Figure 7. Source image for the lightbulb experiment. Red curves represent the four line images used for calibration.

Figure 8 .

 8 Figure 8. The weighted mean error (in logarithmic scale). The function is minimized at α = 31.67 •

Figure 9 .

 9 Figure 9. The calibration result showing the reconstructed mirror surface and its relative position w.r.t. the camera. The recovered angle is α = 31.67 • .

Acknowledgements

The authors would thank Carlo Colombo and Dario Comanducci for providing us with the Matlab code to compute the harmonic homology of a solid of revolution.


Wonwoo Lee
email: wlee@gist.ac.kr

Woontack Woo
email: wwoo@gist.ac.kr

Edmond Boyer
email: edmond.boyer@inrialpes.fr

Identifying Foreground from Multiple Images ⋆

In this paper, we present a novel foreground extraction method that automatically identifies image regions corresponding to a common space region seen from multiple cameras. We assume that background regions present some color coherence in each image and we exploit the spatial consistency constraint that several image projections of the same space region must satisfy. Integrating both color and spatial consistency constraints allows to fully automatically segment foreground and background regions in multiple images. In contrast to standard background subtraction approaches, the proposed approach does not require any a priori knowledge on the background nor user interactions. We demonstrate the effectiveness of the method for multiple camera setups with experimental results on standard real data sets.

Introduction

Identifying foreground regions in single or multiple images is a necessary preliminary step of several computer vision applications in object tracking, motion capture or 3D modeling for instance. In particular, several 3D modeling applications optimize an initial model obtained using silhouettes extracted as foreground image regions. Traditionally, foreground regions are segmented under the assumption that the background is static and known beforehand in each image. This operation is usually performed on an individual basis, even when multiple images of the same scene are considered. In this paper, we take a different strategy and propose a method that simultaneously extract foreground regions in multiple images without any a priori knowledge on the background. The interest arises in many applications where multiple images are considered and where background information are not available, for instance when a single image only is available per viewpoint.

The approach we propose relies on a few assumptions that are often satisfied. First, the region of interest should appear entirely in several images. Second, in each image, the background colors should be consistent, i.e. the background is homogeneous to some extent, and differ from the foreground colors. Under these assumptions, we iteratively segment in each image the 2 regions such that one, the background, satisfies color consistency constraints, and the second, the foreground, satisfies geometric consistency constraints with respect to other images. To initiate the iterative process, we use the first assumption above to identify regions in the images that are necessarily background. Such regions are simply image regions which are outside the projections of the observation volume common to all considered viewpoints. These initial regions are then grown iteratively by adding pixels that inconsistently belong to background and foreground regions in other images. We adopt an EM scheme for that, where background and foreground models are updated in one step, and images are segmented in another step using the new model parameters. Some important features of the approach are as follows. The method is fully automatic and does not require a priori knowledge of any type nor user interactions. In addition, a single camera at different locations or several cameras can be considered. In the latter, cameras do not need to be color calibrated since geometric and not color consistency is enforced between viewpoints.

The remainder of the paper is as follows. In section 2, we review existing segmentation methods. Sections 3 and 4 detail the implementation of the proposed method. Experimental results and conclusions are given in sections 5 and 6, respectively.

Related Works

Background subtraction methods usually assume that background pixel values are constant over time while foreground pixel values vary at some time. Based on this fact, several approaches have been proposed which take into account photometric information: greyscale, color texture or image gradient among others, in a monocular context. For non-uniform backgrounds, statistical models are computed for pixels. Several statistical models have been proposed to this purpose, for instance: normal distributions used in conjunction with the Mahalanobis distance [START_REF] Wren | Pfinder: Real-Time Tracking of the Human Body[END_REF], or mixture of Gaussian to account for multi-value pixels located on image edges or belonging to shadow regions [START_REF] Rowe | Statistical mosaics for tracking[END_REF][START_REF] Friedman | Image Segmentation in Video Sequences: A Probabilistic Approach[END_REF]. In addition to these models, and to enforce smoothness constraints over image regions, graph cut methods have been widely used. After the seminal work of Boykov and Jolly [START_REF] Boykov | Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images[END_REF], many derivatives have been proposed. GrabCut reduces the user interaction required for a good result by iterative optimization [START_REF] Rother | Grabcut-interactive goreground extraction using iterated graph cuts[END_REF]. Li et al. proposed a coarse to fine approach in Lazy Snapping. It provides a user interface for boundary editing [START_REF] Li | Lazy snapping[END_REF]. Freedman et al. [START_REF] Freedman | Interactive graph cut based segmentation with shape priors[END_REF] exploit the shape prior information to reduce segmentation error in the area where both the foreground and background have the similar intensities . The current graph cut based methods shows good results with both static images and videos, but user interaction are often required to achieve good results.

All the aforementioned approaches assume a monocular context and do not consider multi-camera cues when available. An early attempt in that direction was to add stereo information, i.e. depth information obtained using 2 cam-eras, to the photometric information used for classification into background and foreground [START_REF] Gordon | Background Estimation and Removal Based on Range and Color[END_REF]. Incorporating depth information makes the process more robust, however it does not account for more than 2 camera consistencies. Zeng and Quan [START_REF] Zeng | Silhouette extraction from multiple images of an unknown background[END_REF] proposed a method which estimates the silhouette of an object from the unknown background. They exploit the relationship between a region of an image and the visual hull. The approach requires however a good color segmentation, since foreground regions are identified based on the regions. Sormann et al. [START_REF] Sormann | Graph cut based multiple view segmentation for 3d reconstruction[END_REF] applied the graph cut method to multiple view segmentation problem. They combine the color and the shape prior for robust segmentation from a complex background but user interactions are still required.

Our contribution with respect to the aforementioned approaches is to provide a fully automatic method that does not require static background prior knowledge, or user interaction. The different steps of the method are depicted in the 3 Probabilistic Modeling

Definitions

We represent the input color images as I and the segmentation map as S. τ is the prior knowledge of the scene. The knowledge of the background and foreground are noted as B and F, respectively. F, B, and S, are unknown variables, and I is the only known variable among all the variables. For a pixel, S has a value of either 0 for the background or 1 for the foreground. We use superscript i to represent a specific view. Subscript x indicates a pixel located at x (u, v). I i x means the color values of the pixel x in the ith image.

Joint Probability Decomposition

With the defined variables, we represent the problem as a Bayesian network. Before we infer the probability of the segmentation map, we need to compute the joint probability of the variables. From the dependencies among the variables we decompose the joint probability as the equation 1.

P r (τ ), P r (B|τ ), and P r (F|τ ) are the prior probabilities. Since we give no constraints on them, we assume that they have uniform distributions. We don't need to consider these priors to infer the probability of the segmentation map. Thus, they are ignored from now on. P r (S|F, τ ) is the spatial consistency term. It represents the probability of the segmentation map, when the foreground information is available. The term P r (I|B, S, τ ) is the image likelihood term. It tells us how much the image is related to the background information we know.

Spatial Consistency Term

Although each camera sees its own background different from the other's, the foreground should be consistent among all the views under our assumption. For a pixel in the ith image I i , the spatial consistency represents how much the other views agree that the pixel belongs to the foreground. It is referred from the segmentation maps S k where i ̸ = k.

To compute the spatial consistency, we exploit the silhouette calibration ratio proposed in [START_REF] Boyer | On using silhouettes for camera calibration[END_REF]. The silhouette ratio computes the probability of a pixel to be foreground from the silhouettes of the other views. We use modified silhouette calibration ratio R x with a Gaussian distribution to give more penalty to the low silhouette calibration ratio value.

R x = e -(1-Cx) 2 /σ 2 (2)
where C x is the silhouette calibration ratio corresponding to x. σ is the standard deviation through which we can control the slope of the probability curve.

σ determines how much penalty is given to the a silhouette calibration ratio value. We give a tolerance to the silhouette calibration ratio through σ, since the knowledge about the foreground inferred from the other views can be wrong. σ is computed from the number of cameras m we allow to miss, the corresponding silhouette calibration ratio C m and the expected probability q.

σ = √ - C 2 m ln (q) (3)
Since S i x has the value of either 0 or 1, the spatial consistency term can be decomposed into two terms, when S i x = 0 and S i x = 1. When S i x = 0, the foreground information inferred from the other views does not give any clue about the background. In this case, we assume the spatial consistency has a uniform distribution P b . When S i x = 1, the spatial consistency term follows the inferred foreground information. Thus, we refer the modified silhouette calibration ratio as the spatial consistency term. Consequently, P r

( S i x |F i , τ
) is computed as the equation 4.

P r

( S i x |F i , τ ) = { P b if S i x = 0 e -(1-Cx) 2 /σ 2 if S i x = 1 (4)

Image Likelihood Term

The image likelihood term P r

( I i x |B i , S i x , τ
) measures the similarity between a pixel's color I i

x and the background information we know. If a pixel is assumed to belong to the background,

( S i x = 0
) , the likelihood of the pixel color is computed from the the statistical color model of the background colors. To represent the color model of the background, several different methods, such as Gaussian mixture model or histogram, can be used.

When the pixel is considered as the foreground

( S i x = 1
) , the knowledge of the background color distribution does not provide any information to us. As we make no assumptions on the colors of the foreground, we set the image likelihood term to a uniform distribution P f in this case. Consequently, the image likelihood term is defined as the following equation.

P r

( I i x |B i , S i x , τ ) = { H B ( I i x ) if S i x = 0 P f if S i x = 1 (5)
where H B represents the statistical model of the background colors.

Segmentation Map Inference

After the joint probability distribution is defined, it is possible to infer the segmentation map from the given conditions by exploiting Bayes' rule. What we want to know is the probability distribution of the segmentation map S, given the variables, F, B, I, and τ .

For a pixel I i x , the probability of the segmentation map is inferred as the equation 6.

P r

( S i x |F i , B i , I i x , τ ) = P r ( S i x , F i , B i , I i x , τ ) ∑ S i x =0,1 P r (S i x , F i , B i , I i x , τ ) (6) = P r ( S i x |F i , τ ) P r ( I i x |B i , S i x , τ ) ∑ S i x =0,1 P r (S i x |F i , τ )P r (I i x |B i , S i x , τ )

Iterative Optimization with Graph-cut

To compute the optimal segmentation maps of all the views, we exploit the graph-cut method. In the same manner of the method proposed in [START_REF] Rother | Grabcut-interactive goreground extraction using iterated graph cuts[END_REF], we iteratively update the unknown variables, F i and B i , and estimate S i for each view.

We build a graph G for every image I i . The pixels of I i become the nodes of G i and each pixel has edges connected to its eight neighbors. There are two special nodes in G i , the source S and the sink T which are connected to every nodes in the graph. Computing min-cut minimizes the the segmentation energy defined in the equation 7.

E total = ∑ x∈I i λ 1 E p (x) + ∑ (x,y)∈N,Sx̸ =Sy λ 2 E n (x, y) (7)
where E p is the prior energy term and E n is the neighborhood energy term. N is the sets of neighboring pixels.

The prior energy represents that how much a pixel is close to the foreground or the background. The neighborhood energy is for the smoothness of the segmentation. If two pixels have large color difference, there is high probability of the existence of the segmentation boundary. Thus, P r

( S i x |F i , B i , I i x , τ
) is used as the prior energy. We define the neighborhood energy as the equation 8 in this work.

E n (x, y) = 1 1 + D (x, y) (8)
where D(x, y) is a color difference measurement between two neighboring pixels, x and y. According to our experiments, the neighborhood energy is not limited to the equation 8. It may have different form, if it is designed to have small value with large color difference and large value with the similar colors of the two pixels. We assign the capacity w (x, y) to every edge between the node x and y in G i . The prior energy assigns the capacities to the edges connected to S and T . For the edges connected to S, we set the capacities as shown in the equation 9. If a pixel is already known as background, we assign infinity to the edge. If not, the capacity follows the inferred probability with with S i x = 0,

w (x, S) = { ∞ if x is known as the background P r ( S i x = 0|F i , B i , I i x , τ ) otherwise (9)
If T is one of vertices of an edge, the capacity is set as the inferred probability with S i x = 1. w (x, T ) = P r

( S i x = 1|F i , B i , I i x , τ ) (10)
For the edges between two neighboring pixels, we assign the scaled neighborhood energy to it.

w (x, y) = λ n E n (x, y) (11)
where λ n is a scale factor.

After the convergence of the iterative optimization process, there can be misclassified pixels. To remove remaining errors, we perform a graph-cut based segmentation again as a post-processing. In the post-processing, the image likelihood term is modified as the equation 12. We use the foreground color model instead of the uniform distribution P f , in the same manner of the conventional graph cut methods.

P r

( I i x |B i , S i x , τ ) = { H B ( I i x ) if S i x = 0 H F ( I i x ) if S i x = 1 (12)
where H B and H F represents the color model of the background and the foreground, respectively.

Experimental Results

To demonstrate the effectiveness of our method, we performed experiments with the 'Dancer' and 'Temple' data sets which contain one foreground object. The 'Dancer' data set consists of 8 images with the size of 780x582. The 'Temple' data set is the selected 10 images with the size of 640x480. Fig 3 shows an intermediate segmentation results with and without the spatial consistency. In the input image, the foreground contains self shadows under the arms and the color of its hair is similar to colors of the background. Thus, some part of the foreground is lost, when only the color difference criterion is used. In contrast, segmentation with the spatial consistency preserves the part of the foreground well.

Fig 4 shows the results with the 'Dancer' data set. The first row shows the selected images among the 8 input images. The initial segmentation computed from the intersection of the viewing volumes are depicted in the second row. The extracted foreground after each iteration is shown from the row 3 to 6. The initial segmentations in the row 2 converge to the results in the row 6 by the iterative optimization we presented in the previous section. Thanks to the spatial consistency, our method removes the background even though there are hard edges between the green mat and the gray floor. After the post-processing, we obtain the final segmentation maps depicted in the last row. Table 1 shows the performance of the proposed method. To measure the performance, we computed the hit rate of the segmentation results from the ground truth. There exist errors in the segmentation, but it still shows good performance with the hit rates over 90 %. shows the visual hulls reconstructed from the silhouettes of the ground truth that is obtained by manual hand operation and the silhouette obtained by the proposed method, respectively. They are not identical because of the segmentation errors, but the visual hull computed from our result still preserves the 3D shape of the foreground well.

Conclusions

In this paper, we proposed a novel method of foreground extraction from multiple images. Our method integrates the spatial consistency with the color information for robust estimation of the foreground from the unknown background. As shown in the experimental results, the spatial consistency provides an important clue to the separation of the foreground from the background. Since the proposed method requires neither the pre-knowledge of the scene nor the user interaction, it is more close to an automatic method than others. As a future work, an interesting issue is to extend the current work to the multi-view video sequence by exploiting both spatial and temporal constraints.

Fig 1 Fig. 1 .

 11 Fig. 1. Overall procedure of the proposed foreground extraction method.

Fig. 2 .

 2 Fig. 2. Bayesian network representing the dependencies among the variables.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Interim segmentation results with and without the spatial consistency. One of the input images(left) Segmentation result with the color difference only (middle) Segmentation result with the color difference and the spatial consistency(right)

Fig 5

 5 shows the experimental results with the 'Temple' data set. Since the Temple data set has almost black background, the segmentation of the foreground looks easier. However, the color similarity between the foreground and the background causes errors. As shown in the Fig 5, our method extracts the foreground successfully. Note that only the selected results among 10 images are presented because of the lack of the space.

5 .

 5 Foreground extraction results with the 'Temple' data set.

Fig. 6 .

 6 Fig. 6. Visual hulls reconstructed from the silhouettes of the ground truth(left) and the silhouette obtained by our method(right).

Table 1 .

 1 Segmentation performance (unit: %)

	View ID	1	2	3	4	5	6	7	8	9	10
	Temple	98.38 98.31 98.20 98.51 98.73 98.25 98.51 98.20 98.05 98.09
	Dancer	93.93 97.74 96.44 93.14 92.41 94.94 97.20 94.93 -	-
	Fig 6

⋆ This project is funded in part by ETRI OCR and in part by the Korea Research Foundation Grant funded by the Korean Government(MOEHRD)(KRF-2006-612-D00081).


Sungho Kim

Kuk-Jin Yoon
email: kjyoon@rcv.kaist.ac.kr

In So Kweon
email: iskweon@kaist.ac.kr

Object Recognition Using a Generalized Robust Invariant Feature and Gestalt's Law of Proximity and Similarity

In this paper, we propose a new context-based method for object recognition.

We first introduce a neurophysiologically motivated visual part detector. We found that the optimal form of the visual part detector is a combination of a radial symmetry detector and a corner-like structure detector. A general context descriptor, named G-RIF (Generalized-Robust Invariant Feature), is then proposed, which encodes edge orientation, edge density and hue information in a unified form. Finally, a context-based voting scheme is proposed. This proposed method is inspired by the function of the human visual system, called figure-ground discrimination. We use the proximity and similarity between features to support each other. The contextual feature descriptor and contextual voting method, which use contextual information, enhance the recognition performance enormously in severely cluttered environments.

Introduction

How to cope with image variations caused by photometric and geometric distortions is one of the main issues in object recognition. It is generally accepted that the local invariant feature-based approach is very successful in this regard. This approach is generally composed of visual part detection, description and classification.

The first step in the local feature-based approach is visual part detection. Lindeberg [9] proposed a pioneering method on blob like image structure detection in scalespace. Shokoufandeh [24] extended this feature to wavelet domain. Schmid et al [START_REF] Schmid | Evaluation of interest point detectors[END_REF] compared various interest point detectors and concluded that the scale-reflected Harris corner detector is most robust to image variations. Mikolajczyk and Schmid [START_REF] Mikolajczyk | Scale & affine invariant interest point detectors[END_REF] also compared visual part extractors and found that the Harris-Laplacian based part detector is suitable for most applications. Recently, several visual de-scriptors have been proposed [10],[14],[5], [26]. Most approaches try to encode local visual information such as spatial orientation or edge.

Based on these local visual features, several object recognition methods, such as the probabilistic voting method [20] and constellation model-based approaches [START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF], [15], have been introduced. However, those approaches occasionally fail to recognize objects with few local features in highly cluttered backgrounds. Recently, Stein and Hebert [25] proposed a background invariant object recognition method by combining local feature with the object segmentation scheme. Because this method is based on prior figureground information, it cannot be used in a general environment. Torralba et al. [START_REF] Torralba | Context-based vision system for place and object recognition[END_REF] introduced a completely different approach that exploits the background clutter information into object recognition. The background information is called place context or exterior context in that method. The exterior context information is very useful for practical applications such as intelligent mobile robotics systems.

Our research interest is how to efficiently extract an object's interior contextual information to enhance object recognition performance in strongly cluttered environments. We concentrate on the properties of a human visual receptive field and propose a computationally efficient local context coding method. We also propose an object recognition method based on the human visual system's figureground discrimination mechanism, which is accomplished by grouping interior contextual information.

Perceptual visual part detection

Appearance-or view-based object recognition methods were proposed in the early 1990s for face recognition and currently have become popular in the object recognition society. However, global appearance representation using a perfect support window as shown in Figure 1(a) cannot recognize objects in cluttered environments because of imperfect figure-ground segmentation. A bypassing method is to approximate an object as the sum of its sub-windows. The main issue in this approach is how to select the location, shape and size of a sub-window as shown in Figure 1(b). For successful object recognition, visual parts have to satisfy the following requirements. First, background information should be excluded as much as possible. Second, they must be perceptually meaningful. Finally, they should be robust to the effects of photometric and geometric distortions. Mahamud [12] suggested a greedy search method to find visual parts that satisfy the above requirements. Image structure-based part detectors are more efficient than regular grid-based part [START_REF] Schmid | Evaluation of interest point detectors[END_REF], [10]. Although these methods work well, they do not exploit the full structural information of interesting objects.

Recently, Serre and Riesenhuber [START_REF] Serre | Object recognition with features inspired by visual cortex[END_REF] proposed a neurocomputational object recognition method by precisely modeling the properties of simple and complex cells. The basic concepts of the model are tuning and MAX operation on both feature detection and recognition. Although this model is a biologically good model, it is computationally inefficient because of the enormous tuning process of the location, size and phase of the Gabor filter.

We approximate the tuning process of a simple cell by two dominant Gabor filters -0°and 90°phases [START_REF] Ringach | Spatial structure and symmetry of simple-cell receptive field in macaque primary visual cortex[END_REF]. A 0°phase Gabor is equivalent to the 2nd derivative of a Gaussian, and a 90°phase is equivalent to the 1st derivative of a Gaussian kernel. According to the complex cell model, location and size invariance are achieved by the MAX operation of various tuning responses. Figure 2 shows the complex cell responses using the approximated model for cross and circle structures. (1) Location tuning using 1st derivative of Gaussian -Select maximal response in all orientations within a 3 × 3 complex cell.

-Suitable method: Harris corner or KLT corner extraction (both eigen values are large).

(2) Location tuning using 2nd derivative of Gaussian -Select maximal response in all orientations within 3 × 3 complex cell.

-Suitable method: Laplacian or DoG gravity center (radial symmetry point).

(3) Scale tuning using convexity -Select maximal response in directional scale-space [START_REF] Okada | Scale selection for anisotropic scale-space: Application to volumetric tumor characterization[END_REF].

-For computational efficiency, a convexity measure such as DoG is suitable. This is related to the properties of the V4 receptive field where the convex part is used to represent visual information [17].

Figure 3 shows the biologically motivated and computationally efficient model. Scale reflected 1st derivative of Gaussian can be approximated by subtracting neighboring pixels in a scale-space image, and 2nd derivative of Gaussian can be approximated by subtracting between scale-space images. This is supported by the psychophysical facts that HVS attends on gravity centers and high curvature points [18], and objects are decomposed into a perceptual part that is convex [START_REF] Latecki | Convexity rule for shape decomposition based on discrete contour evolution[END_REF], [START_REF] Loy | Fast radial symmetry transform for detecting points of interest[END_REF].

Interestingly, the final approximated model of the simple and complex cells receptive field is a conjunction of the Harris-Laplace and DoG-DoG feature detectors. Figure 4 shows the results of the proposed perceptual part detector. Note that the proposed method extracts all possible visual parts complementing each other.

General contextual descriptor

The description of visual parts is very important for object identification or classification. Two important factors in Then, what information has to be represented? We found the solution from the properties of the receptive field in V1, V4. Through simple and complex cells, orientation response maps are generated and fine orientation adaptation occurs on the receptive field within the attended convex part in V4 [2]. The computational method of the orientation adaptation phenomenon is steering filtering [3]. Adapted orientation is calculated by the maximum response spanned by basis responses. Color blobs also exist in the hyper column where opponent color information is stored. Hue represents perceptual color information like the human visual system. Hue is invariant to affine illumination change and highlights. This orientation and color information is combined in V4 [29].

Summarizing these findings, a plausible receptive field response in V4 is shown in Figure 5. Adapted orientation, edge strength and hue field information coexist within the attended convex visual part. Now, how does the HVS encode the receptive field re- 1. The proposed encoding scheme is a general form of the contextual feature representations of [10], [26], [START_REF] Belongie | Shape matching and bject recognition using shape contexts[END_REF]. We can select a suitable level of context depending on applications. In general, as the aperture size is larger, the recall is lower and the precision is higher. Figure 7 shows an example of visual part matching using the proposed part detector and general context descriptor (G-RIF: generalized robust invariant feature). Most visual parts correspond to one another by a simple Euclidean distance measure. More specific details of implementation and invariant properties can be found in [START_REF] Kim | Biologically motivated perceptual feature: Generalized robust invariant feature[END_REF].

Neighboring context-based object recognition

A conventional classifier based on local informative features is direct voting of nearest neighbors as in Figure 8 [20]. Although there are more sophisticated classifiers, such as SVM [START_REF] Wallraven | Recognition with local features: the kernel recipe[END_REF], Adaboost [START_REF] Zhang | Boosting local feature based classifiers for face recognition[END_REF], Bayesian decision theory [15], and strong spatial constraint-based indexing [23], those methods are basically based on the concept of nearest neighbors and their voting. The proposed object recognition method, named neighboring context-based voting, can be modeled as follows:

L = arg max l P (l|X) ≈ arg max l N X i=1 P (l|x i ) (1)
where local feature x i belongs to input feature set X, l is an object label and N x is the number of input local features. The posterior P (l|X) is approximated by the sum rule. We use the following binary probability model to design P (l|x i ):

P (l|x i ) = 1 i ∈ l, S M (i, l) ≥ 0 otherwise (2)
where S M (i, l) is called a feature-label map which represents the strength of the match between an input feature and its label based on neighboring context information. It is calculated as follows:

S M (i, l) = j∈N (i) w(i, j)c(j, l) (3)
where N (i) is the support region (or neighbors) of feature i. As shown in Figure 9, neighboring context information is aggregated by summing over the neighborhood using the above equation. w(i, j) represents the support (contextual) weight at site j in the support region. The support from the neighborhood is valid when the neighboring visual parts have the same label (or object index) as the site of interest. This is the same concept as Gestalt properties, i.e., proximity and similarity. c(j, l) is the goodness of match pair (j, l)

Learning Recognition ¡ ¡ ¡ ¢ ¢ ¢ 1 NN search Label Vote ¡ ¢ £ £ £ £ ¤ ¤ ¤ ¤ Learning Recognition ¡ ¡ ¡ ¢ ¢ ¢ 1 NN search Label Vote ¡ ¢ £ £ £ £ ¤ ¤ ¤ ¤ (a) ¡ ¡ ¡ Label Vote ¡ Context-based Feature-label map ¢ ¢ ¢ ¢ £ £ £ £ ¤ ¤ ¤ ¤ Learning Recognition ¡ ¡ ¡ Label Vote ¡ Context-based Feature-label map ¢ ¢ ¢ ¢ £ £ £ £ ¤ ¤ ¤ ¤ Learning Recognition (b)
The support weight will be proportional to the probability, p(O l j |O l i ) where O l i represents the event that the label of a site i is l:

w(i, j) = k • p(O l j |O l i ) (4)
When we consider the fixed label l, it can be rewritten as:

w(i, j) = k • p(lx i = l, lx j = l) (5)
where lx i represents the label of feature x i and k is normalization factor. The probability of both features coming from the same object l is defined as:

p(lx i = l, lx j = l) = S(lx i = l)S(lx j = l) N L m=1 N L n=1 S(lx i = n)S(lx j = m) (6)
where S(lx i = l) means the similarity that a local feature is mapped to a label l. This is equivalent to the χ 2 kernel value between input feature x i and its nearest neighbor x l 1N N , whose label is l:

S(lx i = l) = K χ 2 (x i , x l 1N N ) (7)
The χ 2 similarity kernel is defined as [START_REF] Wallraven | Recognition with local features: the kernel recipe[END_REF]:

K χ 2 (x, (y)) = exp{-ρχ 2 (x, y)} ( 8
)
where ρ is set to 3∼4 normally. Goodness of match, c(j, l) is also defined as S(lx j = l).

Although the feature-label map S M (i, l) is calculated using the above similarity kernel, it can be formulated in recursive form by simply reusing the feature label map in the next iteration, rather than the similarity kernel.

Figure 10(a) shows the feature label map calculated from the similarity kernel and Figure 10(b) shows the feature label map after applying the proposed method: contextually weighted feature-label map after two recursions. Figure 11 represents a close up view of Figure 10 and displays several feature locations. Note the power of neighboring contextual information, which enhances the strength of figural features (here, f.id: 527, 536) and suppresses the background features (here, f.id: 525).

Experimental results

Although there are several open object databases, such as Amsterdam DB, PASCAL DB, ETH-80 DB, and Caltech DB, we evaluate the proposed method using COIL-100 DB for feature comparison. We also use our DB, CMU DB (available at http://www.cs.cmu.edu/∼stein/BSIFT) which contain background clutter, because our research goal is to recognize general objects in severely cluttered environments. Figure 12 background. These DB and test images are acquired using a SONY F717 digital camera and are resized to 320×240.

First, we compare the performance of the proposed G-RIF with SIFT, which is a state-of-the art descriptor [10], [14]. Typically, visual part detectors are evaluated only in terms of their repeatability. However, the evaluation should be in the context of a task, such as object labeling in this paper. We evaluate the features using the direct voting-based classifier which is used commonly as in Figure 8(a). We use the binary program offered by Lowe [10]. The accuracy of detection rate is used as a comparison measure which is widely used in classification or labeling problems. Figure 13 shows the evaluation results using our DB by changing the similarity threshold of direct voting. G-RIF shows better performance than SIFT and reveals the complementary properties of G-RIF: right path (gravity center point) and G-RIF: left path (high curvature point).

The 2nd and 3rd columns in Table 2 show the overall recognition results using the optimal classifier threshold (0.8). The recognition rate using G-RIF is higher than the SIFT feature by 5.77%. This good performance originates from the complementary properties of the proposed visual part detector and the effective spatial coding of multiple features in a unified way. In this test, we set the aperture level up to L3 and feature level by (1)+(2). Figure 14 shows several successful examples using G-RIF that are incorrect us- originates from the effective use of the neighboring context. The contextual influence was explained in Figure 11.

Figure 16 shows three kinds of recognition examples with both methods. Figure 16(a) is a normal case. Both methods succeeded for textured objects. Finally, we evaluated contextual and direct voting using the CMU database. This database is composed of 110 separate objects and 25 background images. We generated test images by changing objects' sizes on different backgrounds. This is equivalent to changing the background size. Figure 18 shows the evaluation results. Contextual voting shows an equal or better recognition rate than direct voting. Note that the neighboring contextual information has a more important role for object labeling in a severely cluttered background than in a less cluttered background.

Conclusions

In this paper, we propose a biologically motivated visual part selection method that extracts complementary visual parts. In addition, we propose a general contextual descriptor that encodes multi-cue information in a unified form. Recognition performance was improved by using the proposed feature. We also propose a simple and powerful object recognition method based on neighboring contextual information. Neighboring contextual information suppresses the strength of background features and enhances the strength of figural features in the feature-label map. The proposed method shows better recognition performance than other methods in a severe environment. We will extend the context-based voting method for general objectbased image understanding such as labeled figure-ground segmentation.

Figure 1 .

 1 Figure 1. (a) Perfect global object description. (b) Issues in local part-based object description.

Figure 2 .

 2 Figure 2. (a) Location tuning by spatial MAX operation of 1st derivative of Gaussian. (b) Location tuning by spatial MAX operation of 2nd derivative of Gaussian. (c) Scale tuning by scale-space MAX operation of 2nd derivative of Gaussian centered on (a). (d) Scale tuning by scale-space MAX operation of 2nd derivative of Gaussian centered on (b).

Figure 3 .

 3 Figure 3. The final model of perceptual part detection which is an approximated simple and complex cell model of HMAX.

Figure 4 .

 4 Figure 4. (a) Right pass: radial symmetry part. (b) left pass: corner-like part. (c) final visual part detector.

Figure 5 .Figure 6 .

 56 Figure 5. Plausible receptive model in V4: orientation adapted bar with edge strength on the hue field.

  (a) Context Contents of information L1:1 Aperture L2:1,L2:2,L2:3,L2:4,L2:5,L2:6,L2:7,L2:8 size L3:1,L3:2,L3:3,L3:4,L3:5,L3:6,L3:7,L3:8, L3:9,L3:10,L3:11,L3:12 L4:1,L4:2,L4:3,L4:4 (1) Edge orientation [0, π], quan. level:4 Type of (2) Edge density [0, 1] feature (3) Hue information [0, 2π], quan. level:4 etc: (1)+(2), (1)+(3),(2)+(3), (1)+(2)+(3)

Figure 7 .

 7 Figure 7. The matching results on the rotated objects using the perceptual part detector and local contextual descriptor [G-RIF: aperture size L3 and feature type (1)+(2)].

Figure 8 .

 8 Figure 8. (a) Conventional classifier: direct voting of nearest neighbor. (b) Novel classifier: neighboring context-based voting.

Figure 9 .

 9 Figure 9. Concept of feature-label map (strength of match) generation using neighboring context information.

  Figure 10. (a) Initial feature-label map obtained from similarity kernel. (b) Contextually weighted feature-label map using the proposed method.

Figure 11 .

 11 Figure 11. Close-up view of Figure 10 around Label 41 and corresponding feature locations.

Figure 12 .

 12 Figure 12. (Top) examples of 104 general object models, (bottom) corresponding examples of 104 test objects on a highly cluttered background.

Figure 13 .

 13 Figure 13. Comparison of NNC classification accuracy between G-RIF (left, right, both paths in Figure 3) and SIFT.

Figure 14 .

 14 Figure 14. Correct detection using G-RIF (failure cases using SIFT).

Figure 15 .Figure 16 .

 1516 Figure 15. G-RIF vs SIFT on COIL-100 DB).

  Figure 16(b) show ambiguous recognition results by direct voting but stable recognition results by contextual voting. Finally, Figure 16(c) shows the failure case by direct voting, but success with contextual voting. Figure 17 shows other results of Figure 16(c)'s case. Due to many ambiguous features on the cluttered background, the direct voting method labels the wrong object. However, the context-based voting method can reduce the effect of those cluttered features by neighboring contextual information.

Figure 17 .

 17 Figure 17. Correct detection using contextual voting (failure cases using direct voting).

  Figure 18. As the area of background clutter increases, contextual voting shows relatively higher detection accuracy than direct voting.

Table 1 .

 1 Level of local context.

Table 2 .

 2 Recognition accuracy (similarity threshold: 0.8) for 104 test images.

Acknowledgements

This research has been partially supported by the Korean Ministry of Science and Technology for National Research Laboratory Program (Grant number M1-0302-00-0064) and by Microsoft Research Asia.


Jordi Sanchez-Riera

Jordi Salvador

Josep R Casas

INDOOR PTZ CAMERA CALIBRATION WITH CONCURRENT PT AXES

Keywords:

The introduction of active (pan-tilt-zoom or PTZ) cameras in Smart Rooms in addition to fixed static cameras allows to improve resolution in volumetric reconstruction, adding the capability to track smaller objects with higher precision in actual 3D world coordinates. To accomplish this goal, precise camera calibration data should be available for any pan, tilt, and zoom settings of each PTZ camera. The PTZ calibration method proposed in this paper introduces a novel solution to the problem of computing extrinsic and intrinsic parameters for active cameras. We first determine the rotation center of the camera expressed under an arbitrary world coordinate origin. Then, we obtain an equation relating any rotation of the camera with the movement of the principal point to define extrinsic parameters for any value of pan and tilt. Once this position is determined, we compute how intrinsic parameters change as a function of zoom. We validate our method by evaluating the re-projection error and its stability for points inside and outside the calibration set.

INTRODUCTION

Smart Rooms equipped with multiple calibrated cameras allow visual observation of the scene for application to multi-modal interfaces in human-computer interaction environments. Static cameras with wideangle lenses may be used for far-field volumetric analysis of humans and objects in the room. Wide angle lenses might provide maximum room coverage, but the resolution of the images from these far-field static cameras is somewhat limited. The introduction of pan-tilt-zoom (PTZ) cameras permits a more detailed analysis of moving objects of interest by zooming in on the desired positions. In this context, calibration of the PTZ cameras for any pan, tilt, and zoom settings is fundamental to referring the images provided by these cameras to the working geometry of the actual 3D world, commonly employed by static cameras.

Our research group has built a room equipped with six wide-angle static cameras. The purpose of the static cameras is the computation of a 3D volumetric reconstruction of the foreground elements in the room by means of background subtraction techniques fol-lowed by shape-from-silhouette. The volumetric data resulting from this sensor fusion process is exploited by different tracking and analysis algorithms working in the actual 3D world coordinates of the room. With wide angle lenses spatial room coverage from multiple cameras is almost complete, but the precision of the volumetric data is restricted by the resolution of the camera images. Feature extraction analysis operates at a coarse spatial scale, and cannot obtain detailed information, such as the positions of fingers and hands, which might correspond to convex volumetric blobs in the volumetric representation. The introduction of PTZ cameras in the Smart Room helps to provide a higher resolution volumetric reconstruction for hand and gesture recognition algorithms. Hand movements are closely followed by means of realtime adjustment of pan and tilt. The calibration of PTZ cameras is fundamental to referring their images to the common 3D geometry of the computed volumetric data.

Camera calibration methods can be divided into two groups. The first group makes use of a calibration pattern, such as a checkerboard, located at a known 3D world position. Calibration parameters are then inferred from the detected pattern points in order to calibrate either a single camera [START_REF] Tsai | A versatile camera calibration technique for high-accuracy 3d machine vision metrology using off-the-shelf tv cameras and lenses[END_REF][START_REF] Zhang | A flexible new technique for camera calibration[END_REF][START_REF] Heikkila | Geometric camera calibration using circular control points[END_REF], or several cameras simultaneously [START_REF] Svoboda | A convenient multi-camera self-calibration for virtual environments[END_REF]. The disadvantage of methods based on knowledge of the calibration pattern position is that they might not be convenient for large focal lengths. The second group of methods, also known as autocalibration or self-calibration, may also use a calibration pattern, but in any case the 3D world position is not known [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF][START_REF] Agapito | Selfcalibration of a rotating camera with varying intrinsic parameters[END_REF]. These methods are more difficult to implement due to geometrical complexity problems, such as finding the absolute conic. Most of the methods cited above have been developed for static cameras. Calibration of active cameras faces new challenges, such as computing variation of intrinsic and extrinsic parameters, respectively, as a function of the zoom value and the rotation (pan and tilt) angles. Effective calibration of the varying parameters for the PTZ cameras requires adaptation of the algorithms developed for static cameras.

Intrinsics Calibration for PTZs: One approach for zoom calibration considers each zoom position as a static camera and then calibrates the PTZ as multiple static cameras. [START_REF] Willson | Modeling and Calibration of Automated Zoom Lenses[END_REF] provides a study on zoom calibration describing the changes in focal length, principal point, and focus based on Tsai calibration [START_REF] Tsai | A versatile camera calibration technique for high-accuracy 3d machine vision metrology using off-the-shelf tv cameras and lenses[END_REF]. The large number of possible combinations for zoom and focus values makes the computation of intrinsic parameters ineffective. Other approaches limit the re-projection error as described in [START_REF] Chen | Simple and efficient method of calibrating a motorized zoom lens[END_REF], which proposes the calibration of extreme settings followed by the comparison of the re-projection error with an arbitrary threshold. Positions with errors above the threshold are re-calibrated with a mid point and the extreme. The process is repeated until the range of zoom and focus settings is below the re-projection error threshold. A quartic function is finally found to best match the obtained parameters. However, the strategy of multiple static cameras presents problems with increasing zoom values, that reduce the constraints needed to solve the equations making results inconsistent [START_REF] Ruiz | A note on principal point estimability[END_REF]. Huang [START_REF] Huang | Calibrating pantilt cameras with telephoto lenses[END_REF] proposes an algorithm for cameras with telephoto lenses to face this problem. An alternative approach for calibrating intrinsic parameters under varying zoom values is the separate computation of focal length and principal point although, for the latter, [START_REF] Li | Some aspects of zoom lens camera calibration[END_REF] claim that calibration results are not significantly affected if the principal point is assumed to be constant.

Extrinsics Calibration for PTZs: Extrinsic parameters are important for the correct application of intrinsic calibration results, but the methods mentioned so far focus on the computation of intrinsic parameters without describing how to compute extrinsics in much detail. [START_REF] Sinha | Towards calibrating a pan-tilt-zoom camera network[END_REF] proposes computing both intrinsics and extrinsics in an outdoor environment using an homography between images acquired at different pan, tilt and zoom. [START_REF] Davis | Calibrating pan-tilt cameras in wide-area surveillance networks[END_REF]) compute extrinsics by finding the camera rotation axis. Further references for computing both extrinsics and intrinsics for surveillance applications are [START_REF] Kim | Video surveillance using dynamic configuration of multiple active cameras[END_REF][START_REF] Senior | Acquiring multi-scale images by pan-tilt-zoom control and automatic multi-camera calibration[END_REF][START_REF] Lim | Image-based pan-tilt camera control in a multicamera surveillance environment[END_REF].

Proposal: To overcome the problems of the different methods mentioned above for the calibration of active cameras, we propose to find the rotation center of the camera. Once the rotation center is known, extrinsic parameters can be found by simply applying a geometric formula, and then intrinsic parameters can be determined by a simple bundle adjustment.

In the following, we first review the specifics of the active camera model, then describe the proposed calibration method in Section 3, and finally we present the experimental results in Section 4 and draw conclusions to close the paper.

THE PTZ CAMERA MODEL

Camera calibration is important to the relation of the physical world with the images captured by the camera. This relation is defined by a mathematical model. The pin-hole camera model is based on the perspective transform (a 3x3 matrix K) explaining the relation from the 3D world to the 2D image plane. Unfortunately, real camera optics introduce distortion that must be modeled and corrected. The camera model is not complete without positioning the camera in the physical world according to arbitrarily chosen world coordinates. For this we need to know the rotation (a 3x3 matrix R) and translation (a 3x1 vector T ) of the camera coordinates with respect to the world coordinates. The equation resulting from the above description relates the 3D homogeneous points X in world coordinates with 2D homogeneous points x in the image plane as follows:

x = K[R|T ]X
(1)

Extrinsic Parameters

For PTZ cameras, R and T depend on how the principal point changes with pan and tilt movements. If the principal point is different from the rotation center of the camera (e.g. by a shift r in the optical axis), then any change in the pan (or tilt) angle of α degrees will produce a rotation and a translation of the principal point, which, due to the mechanics of the PTZ camera, will describe a sphere of radius r centered on the rotation center. Considering R r and T r , the rotation and translation describing the position of the rotation center as reference position, any pan (or tilt) movement will produce an additional rotation R a and translation T a describing the position of the principal point.

The reference is defined to be at pan and tilt zero, then the rotation R a and translation T a should be applied to the 3D homogeneous points X. Note that this transform is not a trivial operation. When pan and tilt displacement occur at the same time, two rotation matrices are needed and the order in which matrices are multiplied produces different results. Thus, the transform necessary to express the 3D homogeneous points X in correct principal point origin coordinates must be applied in the following order: Rotate the points R r and translate T r , then apply rotation R a and after the translation T a , finally translate the points back to the origin with transform T .

R a = (R t R p ) (2) R = R r (3) T a = T p + T t + [0, 0, r] T (4) T = T a + T r (5)
In the next subsections we describe the parameters in Equations (2-5) and the effects of pan and tilt independently. Our coordinate axis election is described considering z for the optical axis (in the depth direction) and x, y for the Cartesian coordinates on the image plane.

Pan and Tilt Movements

Figure 1 represents the displacement of the principal point when either pan or tilt changes. When pan changes by α degrees, it introduces a rotation R p (α) and a translation T p (α) parameterized by α: When tilt changes by β degrees, it introduces a rotation R t (β) and a translation T t (β) parameterized by β:

R p (α) =   cos(α) 0 sin(α) 0 1 0 -sin(α) 0 cos(α)   (6) T p (α) =   0 h d   =   0 rsin(α) -r(1 -cos(α))   (7)
R t (β) =   1 0 0 0 cos(β) -sin(β) 0 sin(β) cos(β)   (8) T t (β) =   h 0 d   =   rsin(β) 0 -r(1 -cos(β))   (9)

Intrinsic Parameters

The perspective transform provides a 3x3 matrix, K, mapping the 3D space to the 2D camera plane assuming the pin-hole camera model. This mapping is characterized by the principal point and the focal length. The principal point (p x , p y ) is located at the intersection of the optical axis with the image plane. Usually the camera is designed so that the principal point is at the center of the image, but it may shift depending on the camera optics and zoom settings. The focal length is the distance between the principal point and the focal point. Measured in pixels, the focal length is represented by two components ( f x , f y ) (the "aspect ratio" f y / f x is different from 1 only for non-square pixels). For PTZ cameras, we may assume that all the intrinsic parameters are a function of zoom:

K(z) =   f x (z) sk(z) p x (z) 0 f y (z) p y (z) 0 0 1   (10)
sk represents the skew coefficient defining the angle between the x and y image axes. Further, we must consider the distortion introduced by camera lenses, represented by four parameters, two for radial and two for tangential distortion, as described in [START_REF] Bouguet | Camera calibration toolbox for matlab[END_REF].

Calibration Method

The first goal of our calibration method is to find the rotation center of the camera and its distance to the principal point. Then, with just a geometric transform, we can obtain the extrinsic parameters for any given pan, tilt position. Once this is done, we can focus on the intrinsic parameters. Using the extrinsic paramters already found as the valid camera world position, we can obtain the intrinsic parameters considering that, when zoom changes, intrinsic parameters also change.

To compute the rotation center and its distance to the principal point, first we place the calibration pattern in a known and measured position in the room respect our world origin, and we take some images at several known pan and tilt positions at zoom zero (widest lens). One of the images is taken as reference and the others are described by its relative pan and tilt position with respect to the reference. Then a bundle adjustment, shown in Equation ( 11) is applied to minimize the reprojection error.

n ∑ i=1 m ∑ j=1 ||(x i j -x(R i , R pi , R ti , T i , T pi , T ti , X j , kc, a p , a t )|| 2
(11) where x(R i , ..) is the projection of point X j in image i according to Equation (1) with modifications explained in Section 2.1 and, using four parameters for lens distortion kc. R i , T i are the rotation and translation matrices for the reference image. R pi , R ti and T pi , T ti are the additional rotation and translation matrices due to the relative pan and tilt movements, described in Equations (6-9). Our formulation assumes there are n images with m points in each image. Depending on the camera position, it will not be possible to take images of the calibration pattern at pan and tilt zero, thus a p and a t describe the pan and tilt of the reference image respect the zero position. In order to reach convergence, it is important to start from a good initial guess of the parameters' values. In our case the initial guess for the intrinsic and extrinsic parameters is obtained with [START_REF] Bouguet | Camera calibration toolbox for matlab[END_REF], although any other method, such as [START_REF] Tsai | A versatile camera calibration technique for high-accuracy 3d machine vision metrology using off-the-shelf tv cameras and lenses[END_REF], could be equally valid. With the same principle, we can consider the values of rotation center and radius just found after the previous error minimization as an initial guess for a second bundle adjustment. In this case, we aim at minimizing error with respect to all the parameters: Intrinsic and extrinsic (rotation center and radius). This minimization is computed on the functional shown in Equation (12).

n ∑ i=1 m ∑ j=1 ||(x i j -x(K, R i , R pi , R ti , T i , T pi , T ti , X j , kc, a p , a t )|| 2 (12)
Note that the intrinsic parameters K, are not present in the Equation ( 11). With a calibrated PT (pantilt) camera after this second minimization, we need to calibrate the intrinsic parameters as a function of zoom. For this purpose, we take some images at different zoom values of the calibration pattern in the previous reference position. As we increase the zoom, the calibration pattern ends up outside of the image, therefore, a smaller calibration pattern is used. This second pattern must be aligned with the previous one to keep it in the same measured position. In this case, the minimized functional is shown in Equation ( 13).

m ∑ j=1 ||(x j -x(K(z), X j )|| 2 (13)
Note that only one image is used each time and only intrinsic parameters are minimized. In our particular case, the camera has 1000 step positions for zoom. This is a large number of values and it would not be a good idea to perform the minimization for all the possible values. Therefore, we take the images sampling the whole zoom range at equal intervals. With this, we obtain the intrinsic parameters for some of the values of zoom and then, we can fit a function. This function is as simple as a polynomial of n degrees and n + 1 coefficients.

Results

The proposed algorithm has been implemented in Matlab as an extension of the [START_REF] Bouguet | Camera calibration toolbox for matlab[END_REF] toolbox. In order to test the correctness and limits of the method, we have studied how pan and tilt range affects the re-projection error and have determined which is the optimal number of degrees to fit a function and the optimal sampling of the zoom range. Another test performed to ensure that the correct parameters are found consists in the evaluation of the reprojection error of a known 3D position different from those used to calibrate the camera, in the Smart Room.

For all recordings we have used two different calibration patterns consisting of black and white squares.

The images have been grabbed using a Sony-EVI D70 camera, controlled with the Evi-Lib library (EVI-Lib, 2006) for adjustment of pan, tilt, and zoom. Depending on the distance from the calibration pattern to the camera, the range of pan and tilt, such that the camera is able to grab an image of the whole pattern, will vary. In the selected pattern position, we are able to capture a maximum range of 35 degrees from one side to another of pan, and a maximum range of 20 degrees from one side to another of tilt. In Figure 2 we have represented the re-projection error (y-axis) as a function of pan range (x-axis) and tilt range (the lines drawn). Note that, if for any reason, we are not able to work with a tilt range larger than 10, the pan range needs to be at least 25 to keep re-projection error below 3 pixels. For a tilt range larger than 10, the algorithm is more flexible, allowing more variability for pan range and still keeping a re-projection error below 1.5 pixels. In Figure 3 we have represented the reprojection error (y-axis) as a function of the number of coefficients (x-axis) and intervals of zoom sampling (the lines drawn). For intervals of 25 or 50 steps, the results are very similar, except for coefficients larger than 14, when re-projection error of the line corresponding to 50 steps increases. This is because with 50 steps, over a range of 1000 possible steps, there is not enough data to fit a function with more than 14 coefficients. For similar reasons, when data is taken from intervals of 100 steps, it is not possible to fit a function with an arbitrary large number of coefficients. With a small number of coeffs. (e.g. 4), the error is larger than 5 pixels. With camera parameters within correct re-projection error margins, it is also important to acknowledge to what extent the model is able to reproduce the same results for different positions than those used to calibrate the camera. For this purpose a second set of images has been acquired with the calibration pattern at different position. Figure 4 shows two exam-

Conclusions

Calibration of active cameras has to overcome some difficulties that are not present for fixed cameras, such as solving calibration equations for telescopic lenses or large focal lengths and the fact that the rotation center of the PTZ camera is not co-located with the principal point. The goal of this work has been to obtain a calibration algorithm for PTZ cameras that improves the precision of volumetric reconstruction algorithms applied to a combination of fixed and PTZ camera images in our Smart Room. The principal features we wanted were real-time availability of calibration parameters for all range of pan, tilt and zoom values, with re-projection errors smaller than one pixel spac-ing in order to have precise volumetric reconstruction. State of the art methods did not provide a solution for these goals. Methods for static cameras use to fail for large focal lengths and require large tables to store calibration values for the pan-tilt-zoom range. Methods for active cameras were more adequate but provided a good solution for only a small range of pan and tilt. The presented algorithm is flexible in the sense that it provides readily available calibration parameters for any combination of pan, tilt, and zoom, with a small re-projection error, even though it is slightly larger than one pixel. Some sources of error have been identified. Probably, the most influential error source is the assumption of a nearly constant 3D position of the principal point of the camera with respect to the zoom when, in practice, the focal length in the zoom range of the camera can vary up to a few centimeters. The consideration of constant lens distortion for the zoom range is not true either, although its influence in the final results might be insignificant. Another possible source of error is the position of the calibration pattern in the Smart Room. The Smart Room has some predefined points, precisely measured to put the calibration pattern on according to arbitrary coordinates. For each attempt to position the calibration pattern at predefined 3D world coordinates, there is an error of about 0.5cm in the physical location, which is small considering the actual dimensions of the Smart Room(4m × 5m), but still enough to affect camera calibration results.

Figure 1 :

 1 Figure 1: Principal point displacement (black dot) due to pan (left image) and tilt (right image).

Figure 2 :

 2 Figure 2: Reprojection error for extrinsic parameters as a function of pan and tilt

Figure 3 :

 3 Figure 3: Reprojection error for intrinsic parameters for different polynomial degrees

Figure 4 :

 4 Figure 4: Grid projection. Left image zoom 0, error = 0.93 pixels. Right image zoom 550, error 1.83 pixels.

ACKNOWLEDGMENTS

We want to thank to Jeff Mulligan for the ideas given in the algorithm definition and to Albert Gil for the support given for camera grabbing software.