Akash Kushal

Cordelia Schmid

Lear Team

Jean Ponce

Flexible Object Models for Category-Level 3D Object Recognition

Today's category-level object recognition systems largely focus on fronto-parallel views of objects with characteristic texture patterns. To overcome these limitations, we propose a novel framework for visual object recognition where object classes are represented by assemblies of partial surface models (PSMs) obeying loose local geometric constraints. The PSMs themselves are formed of dense, locally rigid assemblies of image features. Since our model only enforces local geometric consistency, both at the level of model parts and at the level of individual features within the parts, it is robust to viewpoint changes and intra-class variability. The proposed approach has been implemented, and it outperforms the state-of-the-art algorithms for object detection and localization recently compared in [14] on the Pascal 2005 VOC Challenge Cars Test 1 data.

Introduction

Object recognition-or, in a broader sense, scene understanding-is the ultimate scientific challenge of computer vision. After 40 years of research, robustly identifying the familiar objects (chair, person, pet) and scene categories (beach, forest, office) depicted in family pictures or news segments is still far beyond the capabilities of today's vision systems. Despite the limitations of current scene understanding technology, tremendous progress has been accomplished in the past five years, due in part to the formulation of object recognition as a statistical pattern matching problem. The emphasis is in general on the features defining the patterns and the machine learning techniques used to learn and recognize them, rather than on the representation of object and scene categories, or the integrated interpretation of the various scene elements. Modern pattern-matching approaches largely focus on frontoparallel views of objects with characteristic texture patterns, and they have proven successful in that domain for images with moderate amounts of clutter and occlusion. Most methods represent object classes as assemblies of salient parts-that is, (groups of) image features whose appearance remains stable over exemplars. By and large, geometric constraints among parts are either completely ignored (bag-of-parts models [START_REF] Lazebnik | A maximum entropy framework for part-based texture and object recognition[END_REF][START_REF] Zhang | Local features and kernels for classification of texture and object categories: A comprehensive study[END_REF]), or imposed in a rigid manner (constellation/star models [START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF][START_REF] Leibe | Combined object categorization and segmentation with an implicit shape model[END_REF][START_REF] Loeff | Efficient unsupervised learning for localization and detection in object categories[END_REF]). We believe that, as demonstrated by others in the specific object recognition domain [START_REF] Kushal | Modeling 3D objects from stereo views and recognizing them in photographs[END_REF][START_REF] Rothganger | 3D object modeling and recognition using local affine-invariant image descriptors and multi-view spatial constraints[END_REF], geometric constraints are just too powerful to be ignored. For object categories without characteristic textures (e.g., cows, people, etc.), they are also the main image cues available. On the other hand, rigid assemblies of features [START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF][START_REF] Leibe | Combined object categorization and segmentation with an implicit shape model[END_REF][START_REF] Loeff | Efficient unsupervised learning for localization and detection in object categories[END_REF] cannot accommodate the image variability due to significant changes in viewpoint or shape within a category.

In this paper, we propose a novel object model based on the following observation: Even though the geometric relationship between "distant" parts of an object may vary due to intra-class variability and changes in viewpoint, the relative affine transformations among nearby parts are robust to these factors (this is related to the well known fact that arbitrary smooth deformations -including those induced by viewpoint changes for affine cameras or perspectives ones far from the scene relative to its relief-are locally equivalent to affine transformations [START_REF] Koenderink | Affine structure from motion[END_REF]).

Thus, we represent object parts as partial surface models (or PSMs) which are dense, locally rigid assemblies of texture patches. These PSMs are learned by matching repeating patterns of features across training images of each object class (Section 3). Pairs of PSMs which regularly occur near each other at consistent relative positions are linked by edges whose labels reflect the local geometric relationships between these features. These local connections are used to construct a probabilistic graphical model for the geometry and appearance of the PSMs making up an object (Section 4). In turn, the corresponding PSM graph is the basis for an effective algorithm for object detection and localization (Section 5), which outperforms the state-of-theart methods recently compared in [START_REF] Everingham | The 2005 PASCAL Visual Object Classes Challenge[END_REF] on the Pascal 2005 VOC Challenge Cars Test 1 data (Section 6).

Related Work

Fergus et al. [START_REF] Fergus | Object class recognition by unsupervised scale-invariant learning[END_REF] model the joint probability distribution of the relative positions of object parts (which are individual features in their case) as a Gaussian distribution with a full covariance matrix. However, they model each part's location using its x, y image coordinates, making the model highly viewpoint specific. In addition, the learning time is exponential in the number of parts, which limits the number of parts in the model to a maximum of 6 or 7. Loeff et al. [START_REF] Loeff | Efficient unsupervised learning for localization and detection in object categories[END_REF] propose a "star" model in which an object generates a number of parts, each of which generates features with a certain appearance and location relative to the object center. The appearance of the features is modeled as a multinomial distribution over a codebook of feature types and the relative location is modeled as a Gaussian with a mean and covariance for each part. The appearance model of a single part is rather weak in this case since all the features for a given part are generated with independent locations relative to the part center. In addition, the star model enforces rigid geometric constraints among the different object parts and so is viewpoint dependent. Leibe et al. [START_REF] Leibe | Combined object categorization and segmentation with an implicit shape model[END_REF] construct implicit shape models (ISMs) by clustering object features in the training images, and storing for each cluster center the location of the object center and scale relative to the corresponding feature. During recognition, each feature detected on the test image essentially casts probabilistic votes for object centers and scales, and a mean shift procedure is used to find the maxima in this space. The geometric model is again rigid, hence highly viewpoint dependent, and the appearance model is relatively weak since each feature occurrence is considered independently of all others.

Lazebnik et al. [START_REF] Lazebnik | A maximum entropy framework for part-based texture and object recognition[END_REF] propose a bag-of-parts model in which the parts are composed of multiple features linked together in an affinely rigid structure. These parts are quite discriminative and relatively stable against intra-class variations; however, large viewpoint variations result in the affine model no longer holding for the object parts. In this paper, we learn object parts by only enforcing local geometric consistency among the features that make up the part. We also augment the "primary" interest point features of [START_REF] Lazebnik | A maximum entropy framework for part-based texture and object recognition[END_REF] with more general "secondary" texture patches to generate dense and highly discriminative PSMs. Using dense models as opposed to just interest points has been shown to improve matching and recognition performance by [START_REF] Ferrari | Simultaneous object recognition and segmentation by image exploration[END_REF][START_REF] Kushal | Modeling 3D objects from stereo views and recognizing them in photographs[END_REF] in the context of specific 3D object recognition. Dense PSM matches provide an extremely stable coordinate frame to compute the relative positions of other PSM matches robustly. Since our PSMs consist of multiple overlapping features, and some features are more discriminative than others we train a logistic regression model to evaluate the quality of a PSM match based on the individual feature matches.

Recently, Thomas et al. [START_REF] Thomas | Towards multi-view object class detection[END_REF] have proposed a technique which deals with the viewpoint change problem by com-bining models learned for different viewpoints. They use a highly supervised dataset that consists of images of multiple motorbike instances, each from a set of up to 16 viewpoints. First, they construct separate viewpoint dependent ISMs [START_REF] Leibe | Combined object categorization and segmentation with an implicit shape model[END_REF] for each of the different viewing directions. Then, they use the method of [START_REF] Ferrari | Integrating multiple model views for object recognition[END_REF] to match the images of the same motorbike instance across different viewpoints and construct region tracks that are later used to transfer the ISM votes from one viewpoint to its neighboring viewpoints. This is an interesting setup, but it requires highly supervised training data and a dense sampling of viewpoints since the ISMs themselves are highly viewpoint dependent. In addition, since each of the ISMs is learned independently, there is no sharing of parts among the different viewpoints. In contrast, we use a single model that shares its parts (PSMs) among different viewpoints.

Learning PSMs

We use a hypothesize and validate approach to learn PSMs, similar to [START_REF] Lazebnik | A maximum entropy framework for part-based texture and object recognition[END_REF]. A critical difference, however, is that the (relatively) sparse and affinely rigid parts of [START_REF] Lazebnik | A maximum entropy framework for part-based texture and object recognition[END_REF] are replaced by dense and locally rigid PSMs.

PSM Formation

The learning process starts by selecting two images at random from the training set and computing appearancebased primary matches between pairs of salient image regions. To avoid an excessive reliance on characteristic texture patterns, we use a simple operator (essentially a Hough transform) to detect circles in edge maps [START_REF] Jurie | Scale-invariant shape features for recognition of object categories[END_REF], and output the smallest squares enclosing them as candidate regions. Candidate matches between these regions are then computed using the SIFT operator [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF], and a non-linear refinement process is used to correct the initial alignment of these matches. This process considers the patch in the second image as a deformable parallelogram, and optimizes the affine transformation mapping the first patch onto its match so as to minimize the error between the SIFT descriptors of the matched patches. This is essential for matching images of the same patch viewed from different directions.

• Initialization: Once candidate matches have been found, they are partitioned into locally consistent PSM hypotheses using a greedy approach: A PSM hypothesis is initialized with a single match, and nearby matches are iteratively added until the corresponding affine transformations are no longer close enough to those associated with nearby matches already in the PSM hypothesis. An unused match is then chosen at random, and a new PSM hypothesis is grown using the leftover candidates. This process partitions the matches into a set of PSM hypotheses. The hypotheses that contain more matches than a given threshold are passed along to the expansion stage. The composition of the large PSM hypotheses is almost unaffected by the choice of the match used for initialization.

• Expansion: The first image of the training image pair is covered with overlapping square-shaped "secondary" patches, and an expansion step is used to densely cover a region surrounding the PSM hypothesis. Each match in the current PSM hypothesis tries to expand into nearby secondary patches by predicting a match for the secondary patch based on its own affine transformation τ . The "best" predicted match (in terms of SIFT matching score) for each secondary patch is then refined using a non-linear refinement process similar to the one used to align the initial matches. However, now the refinement process also penalizes the deviation of the refined location from the predicted location to prevent the match from drifting too far from its predicted location. 1 Finally, the secondary match is added to the PSM hypothesis if the SIFT matching score exceeds a given threshold. The process is illustrated in Fig. 1. The algorithm continues to expand around the newly added matches until no more secondary matches can be added. The PSM hypothesis consists of all the patches in the first image that were matched successfully.

PSM Matching

A PSM u can be matched to a target image I using a similar process. First, the circle detector is used to detect candidate regions in I and appearance-based matches are computed between the primary patches in u and the detected regions in I. Next, an expansion step uses these initial matches to hypothesize matches for the nearby unmatched patches of u. The hypothesized matches are first refined (as described before) and are iteratively added to the current matches as long as their matching score exceeds a threshold. Finally, all the feature matches are partitioned into groups of PSM matches in the same way as was done for the initially selected image pair. If the number of patch matches within a PSM match exceeds a certain ratio (R = 0.5) of the total number of patches in the corresponding PSM, it is considered correct.

PSM Validation and Selection

The PSM hypotheses learned in Section 3.1 are scored by matching them to a set of validation images containing the object as well as a set of background images. Let N + u (resp. N - u ) be the number of times a PSM candidate u is matched in the validation (resp. background) images. We compute the discriminative power of a PSM u as the ratio R u = N + u /N - u and use it to select PSMs for the object model. The PSM candidates are processed in a decreasing order of R u and are selected only if their validation matches do not have a significant overlap with those of previously selected PSMs. This process helps avoid repeated PSMs. Figure 2 shows a PSM found in training images from the PASCAL VOC 2005 dataset. The two images on the left of the figure are the base images used to hypothesize the PSM, and the images on the right are some validation images.

PSM Appearance Model

We train a logistic regression model to evaluate the quality of individual detections (PSM matches). Concretely, we attach to each match m of a PSM u consisting of n features, a binary appearance vector a = (a 1 , . . . , a n ), where a i is equal to 1 if the corresponding feature has been matched, and -1 otherwise. We also associate a label ℓ ∈ {obj, bkg} with every match m for a PSM u based on whether it matches the object part corresponding to u or some background texture in the image. Let us define P u (a|ℓ) as the probability that a PSM match of u has appearance vector a given that it has label ℓ. Since a PSM consists of multiple overlapping features, the individual feature matches (the components of a) are not independent, making their probabilistic modeling difficult. Thus, instead of learning P u (a|ℓ) directly, we learn a parametric model for Pu(a|obj) Pu(a|bkg) , which will prove sufficient for object detection.

To simplify the learning task, we assume that the training data is generated from a joint distribution P u (a, ℓ) as follows: First, the label is generated from P (ℓ = obj) = P (ℓ = bkg) = 0.5 and then the appearance a is generated given the label from the probability distribution P u (a|ℓ). We begin by training a logistic regression classifier on this data to construct the probability distribution P u (ℓ|a). This now allows us to compute the desired probability ratio as

Pu(a|obj) Pu(a|bkg) = Pu(obj|a)Pu(a) Pu(obj) × Pu(bkg) Pu(bkg|a)Pu(a)
= Pu(obj|a) Pu(bkg|a) .

We now describe the generation of the training data samples (a, ℓ) and the classifier training procedure.

• Generating data from the joint distribution: Every match m of the PSM u provides us with a data point, labeled as obj or bkg depending on whether it has been found in a validation or background image. However, since the number of background instances available is typically much smaller than the number of object instances, we repeatedly sample the background matches as necessary to create as many data points labeled bkg as there are points labeled obj. We assume that the matches observed in the validation images correctly match the corresponding object parts and that the observed appearances a of the matches in the validation (resp. background) images are random samples from P u (a|obj) (resp. P u (a|bkg)).

• Training the classifier: We train the logistic regression model to output the probability P u (ℓ|a) that a data point has label ℓ given that it has appearance a. The binary features used by the logistic regression model are simply the components of a. The weights associated with the features of the model are learned so as to maximize the log-likelihood of labels observed on the training data. This is a convex optimization problem and can be solved efficiently. Since the amount of training data is limited we regularize the maximum likelihood parameter learning process to avoid overfitting by adding a penalty proportional to the squared norm of the weight vector of the logistic regression model [START_REF] Santner | The Statistical Analysis of Discrete Data[END_REF].

Once the PSMs and the corresponding logistic regression models have been learned, the matching process can essentially be thought of as running a set of PSM detectors that fire at certain locations in an image and provide an estimate of the quality of the match based on its appearance. As argued before, since these detectors enforce only local geometric consistency, they are robust to viewpoint changes and intra-class variability.

Learning Object and Background Models

The PSM Graph

We can associate with any instance u ′ of a PSM u detected in an image the 2D affine transformation which is the "mean" of the affine transformations mapping the individual patches of u in the base image roughly to their detected matches u ′ . Intuitively, this transformation represents the affine deformation of the PSM from its base image to its matched location. We denote by A u , the random variable associated with the affine deformation corresponding to PSM u, and we model the joint probability distribution of the variables A u associated with all PSMs in an object model as a MRF (Markov Random Field) structure dubbed the PSM graph. The vertices of this graph are identified with the random variables A u . Nearby PSMs are linked by edges that enforce local consistency between them. An edge joins two PSMs when they co-occur within a specified range from each other in a sufficient number of validation images. Figure 3 shows the PSM graph model for a car learned from the PASCAL VOC 2005 dataset using the technique described in the rest of this section.

The Hammersley-Clifford theorem [START_REF] Besag | Spatial interaction and the statistical analysis of lattice systems[END_REF] allows us to write the joint probability distribution of the variables A u as a product of functions over maximal cliques in the graph. For efficiency reasons, we ignore the cliques of size greater than two while modeling the intra-PSM relations. The pairwise consistency constraints between adjacent PSMs are modeled using normal distributions on the relative affine transformations. Concretely, let R u:v ≡ A u -1 A v denote the affine transformation between the patches of v and u, or equivalently the vector of IR 6 representing the location, scale, skew and orientation of v in the coordinate frame of u, and let µ u:v ∈ IR 6 and σ u:v ∈ IR 6×6 denote the corresponding mean vector and covariance matrix. We model the joint distribution of the PSM positions as

p g (A 1 , A 2 . . . A N ) = 1 Z (u,v)∈E N (R u:v ; µ u:v , σ u:v ),
where N (R; µ, σ) is the normal distribution with mean µ and covariance matrix σ, and Z is a normalization constant. We assume a diagonal form for the covariance matrix σ u:v .

It is important to note that this model is not equivalent to a joint Gaussian model on all the random variables A u . This would indeed be true if the model was constraining the PSM positions instead of relative affine transformations between the PSMs. In that case, the model would be equivalent to a Gaussian model on the random variables with a specific structure imposed on the inverse covariance matrix (the only non-zero entries would be the ones corresponding to the edges in the graph). However, since we impose Gaussian constraints on the relative transformations of PSMs, the model can no longer be written as a joint Gaussian density on the A u . However, as discussed in the introduction, constraining only the relative affine transformations (and not the relative x, y locations) is important to make the model robust to viewpoint and intra-class variations.

Learning the PSM Graph Parameters

Both µ u:v and σ u:v are estimated from the training images in which u and v are seen together. We initialize µ u:v using the mean of the observed relative affine transforms and σ u:v as a diagonal matrix containing the observed variance of each of the entries in µ u:v . However, this estimate is biased and the variances estimated are extremely small. Intuitively, the observed variance between two adjacent nodes occurs as a result of all the constraints in the graph connecting the 2 nodes acting together and attributing the variance to a single constraint makes it too tight. Hence, we use a gradient ascent procedure to optimize the variance parameters σ u:v so that the log likelihood of the PSM matches observed in the validation set is maximized. Let {i 1 . . . i p } be the indices of PSMs observed in some validation image I and let {j 1 . . . j q } be the indices of the PSMs that are not observed in I. The likelihood of the geometrical configuration observed in the ith validation image can be computed by integrating out the unobserved PSMs:

p g (A i1 , . . . A ip ) = j1...jq p g (A 1 , A 2 . . . A N ).
We use loopy belief propagation [START_REF] Murphy | Loopy belief propagation for approximate inference: An empirical study[END_REF] to approximately compute the log-likelihood for the observed configurations in the validation images. The total log-likelihood of the validation set is just the sum of the log-likelihoods for the individual validation images since the images are assumed to be independent. Computing the "exact" gradient of the loglikelihood on the validation images is not computationally feasible since it requires running a belief propagation step for each validation image for every variance parameter on every edge after each iteration. Hence, we compute an efficient approximation to this gradient and use it to optimize the log-likelihood. The details of the gradient ascent procedure are described in Algorithm 1. This algorithm runs a single belief propagation on every validation image after every iteration. Each belief propagation is initialized using the state at the end of the previous iteration and hence converges extremely quickly. In practice, the algorithm converges in less than 10 iterations and the entire optimization process takes less than 10 minutes on a desktop machine for a model with about 30 PSMs and 50 edges. Also, it is usually sufficient to optimize just a single scaling ratio for the entire covariance σ u:v on each edge instead of optimizing the 6 parameters independently.

Object and Background Models

Our object model is generative: First, a PSM graph instance, with an affine transformation A u for every compo- nent PSM u, is chosen from the above distribution. Next, each PSM independently chooses its occlusion state, with probability P vis (u) to be visible, and probably P occ (u) = 1 -P vis (u) to be hidden. If a PSM u is visible it then generates a PSM match m at the location A u . Finally, the appearance of m is chosen independently from the distribution p(m|obj) for each visible PSM. P vis , P occ are learned by just measuring the statistics of the PSM on the validation data.

The background model generates matches for each model PSM u from a Poisson distribution P poiss (n|K u ) with mean K u . The location for each PSM match is selected from a uniform pdf over the size of the image (for position) and a reasonable range of scale, orientation and skew parameters. These ranges are estimated from the background dataset. Finally, the appearance of the PSM match is chosen from the distribution p(m|bkg). The means K u of the Poisson distribution are learned using the statistics observed on the background data. Note that the appearance models P (m|obj) and P (m|bkg) are not learned explicitly. Instead, the logistic regression model associated with every PSM is used to predict their ratio P (m|obj) P (m|bkg) for the PSM. Finally, we assume that the background is present in every image and the number of objects present in it follows a Poisson distribution with mean λ O . Again, this mean λ O may be learned from the training data.

Object Detection/Localization

Object Detection

We start by matching all the PSMs in the object model to the test image independently to obtain a set of PSM matches. Each PSM match m is assigned a probability ratio P (a|obj) P (a|bkg) based on its appearance by the logistic regression model for the corresponding PSM. Let D represent the set of all the PSM matches detected in the test image. Every match in D is generated either by the corresponding PSM from an object or by the background. We denote by O i the subset of D corresponding to instance number i of the object in the image (there may be no such instances, or several ones). Even though D may contain multiple matches for a single PSM, each object instance contains at most one match per PSM. Let Φ denote the set of all the PSMs in the object model, and let Φ S ⊂ Φ for any set of PSM matches S denote the set of PSMs that are matched at least once by matches in S. Finally, let us denote the PSM corresponding to a PSM match m by u m and the appearance of m by a m . Recall that the appearance of a PSM match m is a binary vector containing one coordinate for every feature in a m whose value is either 1 or -1 depending on whether the corresponding feature is matched in m or not. An explanation E = {O 1 , O 2 . . . O k , B} of D is a partition2 of D where the matches in O i correspond to the ith object instance and B is the set of background matches. Let P(D) be the set of all the possible explanations of D.

The probability distribution p(E, D) represents the probability that an explanation E generates the matches D in the image. In other words, if E = {O 1 , . . . O k , B}, then p(E, D) represents the probability that 1) there are k object instances present in the scene, 2) the ith object instance generates the matches in O i , and 3) the background generates the matches in B. Since all the objects in the image and the background generate matches independently of each other, The term p g (m|bkg) is the uniform pdf for the background model described earlier.

• The term P poiss (k|λ O ) represents the prior probability of the image containing k object instances.

• The term p o (O i ) is the probability distribution that the matches in O i and only these matches are generated by the ith instance of the object model. Since the appearance, the geometry and the occlusion state of the PSM matches are independent, we can write p o (O i ) as a product of an appearance term P a (O i |obj), a geometry term p g (O i |obj) and the visibility term P vis (Φ Oi )P occ (Φ \ Φ Oi ). Since we assume that the appearances of the PSMs generated by the object are independent, we can write P a (O i |obj) = m∈Oi P um (a m |obj). The term P g (O i |obj) represents the probability of the geometric configuration of the PSM matches in O i and is computed using the PSM graph. Finally, since the occlusion variables for each PSM are independent, we can write P vis (Φ Oi ) = u∈ΦO i P vis (u) and P occ (Φ \ Φ Oi ) = u∈Φ\ΦO i P occ (u). We want to find the most likely explanation of the scene:

E * = argmax E∈P(D) P (E|D) = argmax E∈P(D) p(E, D).
It is not feasible to search to over all possible explanations of D, and we use a greedy algorithm to build up the "best" explanation. The algorithm is initialized with the explanation E 0 = {D}, assuming that all the matches in D are generated by the background. We then add a single object to the explanation and compute the most likely explanation E 1 = {O 1 , B 1 }, assuming that a single object generates the matches in O 1 and the remaining matches in B 1 = D \ O 1 are generated by the background. If p(E 1 , D) > p(E 0 , D), we fix the matches in O 1 as belonging to the first object instance. Next, the most probable explanation E 2 = {O 1 , O 2 , B 2 } with 2 objects is constructed by splitting the matches in B 1 into O 2 and B 2 . The algorithm iteratively adds the ith object instance to the explanation if p(E i , D) > p(E i-1 , D), and terminates when adding more objects decreases the probability of the explanation. Figure 4 shows an explanation containing two object instances. During the ith iteration, the algorithm has fixed the matches in O 1 , . . . O i-1 and needs to compute the most likely split of the matches in B i-1 into O i and B i . Since it is not feasible to search over all the possible splits of B i , we use a greedy scheme to populate O i starting from an empty set. We move matches from B i to O i one at a time so as to achieve the maximum increase in p(E i , D) at each step. We compute the ratio of p(E i , D) before and after moving a single match m from B i to O i , and use this ratio to choose the best match to move. The process terminates when the best ratio drops below 1. While computing this ratio, the contributions of the terms corresponding to the first i -1 object instances cancel out and we obtain:

p({O1...Oi-1,Oi∪{m},Bi\{m}}) p({O1...Oi-1,Oi,Bi}) = pu m (am|obj) pu m (am|bkg) × pvis(m|obj) pocc(m|obj) × Ppoiss(nm-1|Ku m ) Ppoiss(nm|Ku m ) × pg (Oi∪m|obj) pg (Oi|obj)•pg(m|bkg)
where n m denotes the number of times m is matched in B i . The first term can be computed using the logistic regression model for the PSM. The second and third terms are computed using the learned occlusion parameters p vis , p occ and background Poisson distribution parameter K u . The final term is computed (approximately) by running loopy belief propagation on the graph. In fact, what we need to compute is the ratio pg (Oi∪m|obj) pg (Oi|obj) which can be computed as follows. The nodes in Φ Oi are fixed and belief propagation is run to compute the "approximate" marginal distributions p g (A u |Φ Oi ) on all the nodes u ∈ Φ \ Φ Oi . The required ratio is just p g (A um |Φ Oi ). The term p g ({m}|obj) for an object instance containing a single PSM match m is assumed to be the same as p g (m|bkg).

Localization

Once we have computed an explanation E for the image, we use the PSM matches within each object instance O i to predict a bounding box for it. For every PSM match m u in O i , we transform the bounding box in the base image of u to the test image using A u . The predicted bounding box for O i is just the mean of these bounding boxes for all the matches m ∈ O i . We compute a score β Oi (needed to plot Precision-Recall curves) for each O i using the appearance and visibility terms for the PSMs within O i as

β Oi = log [P a (O i )P vis (Φ Oi )P occ (Φ \ Φ Oi )] .

Experiments and Discussion

We have conducted experiments on the PASCAL VOC Challenge 2005 Cars Test 1 dataset [START_REF] Everingham | The 2005 PASCAL Visual Object Classes Challenge[END_REF], which consists of 275 images containing one or more cars (in a variety of poses) and 414 background images with no cars present. The training data consisted of 272 positive images with 320 annotated cars, and 412 background images.

• Pre-processing of the training data: Since images of cars facing left are identical (up to a flip about the vertical) to cars facing right, we learn a model for detecting cars facing right. The detector is run on the original image as well as its flipped version to be able to detect cars facing both to the left and to the right. To simplify the learning of the object model we correct each image of the training set so that the car is pointing towards the right (by flipping the image, if required). Then we annotate the images with a rough viewing direction from the set {Rear, RearSide, Side, SideF ront, F ront}. Images from a given class are only matched to others from the same class or from neighboring classes during the PSM validation phase. Since our method first learns the object part appearances "independently" and later learns the geometry, it requires a reasonably "clean" set of validation matches while building the model. Thus, we prune the validation image matches based on whether the location of the matching patches within the bounding box in the base image is roughly consistent with the location of the corresponding matches in the bounding box of the validation image.

• Results: Qualitative detection and localization results on the Test 1 data are shown in Fig. 5. As per the rules of the VOC Challenge [START_REF] Everingham | The 2005 PASCAL Visual Object Classes Challenge[END_REF], a detection is considered correct if the intersection area of the predicted bounding box and the annotated bounding box is at least 50% of the union of the two. Also, multiple detections for the same object instance are considered false positives. We have implemented a simple baseline method to judge the performance of the PSMs without the geometric model: Each PSM match m u in the test image casts a vote for its predicted bounding box using A u (similar to Section 5.2) and a mean shift procedure is used to find the modes in this space. The VOC Challenge competition used the average precision (AP) score [START_REF] Everingham | The 2005 PASCAL Visual Object Classes Challenge[END_REF] to rank the results submitted by the participants. Our baseline approach achieves an AP score of 0.590, which is just below the best score of of 0.613 obtained by Dalal and Triggs [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] The results for Dalal and Triggs, Fritz et al., and Garcia and Duffner are taken from [START_REF] Everingham | The 2005 PASCAL Visual Object Classes Challenge[END_REF]. The references in brackets are the publications where the methods used in the challenge have been first described.

in the competition. The PSM graph approach achieves an even higher score of 0.628-the highest obtained so far for this dataset. Figure 6 shows the precision/recall curves corresponding to the baseline method and the full PSM graph algorithm, and compares our AP scores with those obtained by the participants in the VOC 2005 Challenge [START_REF] Everingham | The 2005 PASCAL Visual Object Classes Challenge[END_REF].

• Discussion: These experimental results demonstrate the strength of our model: First, we can see that PSMs are very discriminative, since when combined with a simple voting scheme, they significantly outperform comparable methods based on individual local features [START_REF] Leibe | Combined object categorization and segmentation with an implicit shape model[END_REF]. This style of voting can be thought of as a (simple) implementation of a rigid star model. Our experiments also demonstrate the power added by our loose geometric model, which significantly outperforms all other methods on the Cars Test 1 data of the Pascal 2005 VOC Challenge.

Figure 1 .

 1 Figure 1. Expansion: match prediction and refinement.

Figure 2 .

 2 Figure 2. Left column: the two base images for a PSM; Right: a few validation matches for the same PSM. The outline of the PSM, defined as the union of matched feature regions, is shown in white.

Figure 3 .

 3 Figure 3. An example of learned PSM graph. The top row shows the outlines of the PSM instances corresponding to nodes with the same color in the PSM graph below it. The black nodes represent other nodes in the PSM graph. Please view in color.

Figure 4 .

 4 Figure 4. Explanation using two object instances.

Figure 5 .Figure 6 .

 56 Figure 5. Successful detections on the PASCAL VOC 2005 Cars Test 1. The last two images in the bottom row show correct detections (small red rectangles) showing up as false positives because they were not annotated in the dataset. Please view in color.

Algorithm 1

 1 Optimization of Variance Parameters.

	Input: A set of validation images with detected PSMs, initial es-
	timate of the PSM graph and step length τ .
	Output: Optimized PSM Graph.
	for all validation images I do
	• Initialize the observed PSMs in I;
	• Run BP on I and store the state of messages;
	end for
	repeat
	end for
	end for
	• Update σu:v ← σu:v + τ • Gu:v;
	• Run BP and update the messages on all validation images
	using the updated σu:v;
	until convergence.

• Set gradient Gu:v of σu:v on all edges (u, v) to 0; for all validation images I do for all observed nodes v in I do • Assume v is not observed and compute the belief at v using the incoming messages; • Compute gradient ∂L/∂Mu:v of the log-likelihood of the observed v w.r.t. the incoming messages Mu:v; • Compute gradient ∂L/∂σu:v by multiplying ∂L/∂Mu:v and the Jacobian J(Mu:v, σu:v); • Add gradient to Gu:v for edges (u, v) incident on v;

Since match refinement is relatively time consuming, it is done once for the "best" expansion attempt for each secondary patch, instead of doing it for each expansion attempt and choosing the best match later.

E is not a partition in the strict sense, since it may contain empty blocks. An empty block for an object instance corresponds to the case when the object is present in the image but does not generate any matches (i.e. none of its PSMs are detected in the image). Such an explanation would have a low (but non-zero) probability. Similarly, the background block could also be empty indicating that the background does not generate matches for any of the PSMs.

Acknowledgments: This work was supported in part by the National Science Foundation under grant IIS-0535152, the UIUC/INRIA/CNRS collaboration agreement, and the INRIA associated team Thetys.


Liang Ma
email: ma@irccyn.ec-nantes.fr

Ruina Ma
email: ruina.ma@irccyn.ec-nantes.fr

Damien Chablat
email: damien.chablat@irccyn.ec-nantes.fr

Fouad Bennis
email: fouad.bennis@irccyn.ec-nantes.fr

Using virtual human for an interactive customer-oriented constrained environment design

Keywords: virtual human, constrained environment design, optimization, motion capture, trajectory planning

For industrial product design, it is very important to take into account assembly/disassembly and maintenance operations during the conceptual and prototype design stage. For these operations or other similar operations in a constrained environment, trajectory planning is always a critical and difficult issue for evaluating the design or for the users' convenience. In this paper, a customer-oriented approach is proposed to partially solve ergonomic issues encountered during the design stage of a constrained environment. A single objective optimization based method is taken from the literature to generate the trajectory in a constrained environment automatically. A motion capture based method assists to guide the trajectory planning interactively if a local minimum is encountered within the single objective optimization. At last, a multi-objective evaluation method is proposed to evaluate the operations generated by the algorithm.

1-Introduction

For industrial products, a compact design decreases the required massive space and enhances the appearance of the product. From another aspect, the designers have to consider constrained environments resulting from the compact design. Under constrained situations, assembly/disassembly oriented design has to be taken into consideration, since there are several ergonomic issues for the end user of the product or for the maintenance process. For example, the visibility [SM] and accessibility [LD, RS] of a component during an assembly operation; awkward posture caused by the product layout; physical or mental fatigue from the operations, etc.

For these reasons, virtual human simulations are often engaged during the conceptual design stage to evaluate the accessibility of the virtual environment and other ergonomic aspects [MC1,[START_REF] Rennuit | Passive Control Architecture for Virtual Humans[END_REF]. Thanks to the interaction between the virtual human and the constrained environment, the designers are able to evaluate the manual handling operations, plan the possible trajectories, and further improve the design.

Trajectory planning is one of the most important problems for the use of virtual human in product design. In general, three approaches have been used frequently in the literature to generate the trajectory: inverse kinematics, optimizationbased method, and motion capture method. Inverse kinematics can generate a trajectory automatically and rapidly; however, this method could not generate a collisionfree path easily. In order to overcome this inconvenience, an optimization-based approach has been proposed in [RM] to find a collision-free path iteratively. In comparison to inverse kinematics, direct kinematics has been used in the optimization based approach and it enhances the computation efficiency. However, sometimes, the path can be trapped in a local minimum and it cannot get out from it without external intervention. Using motion capture method, it is convenient to achieve natural movement in a virtual environment. However, the motion data obtained from the motion capture has to be processed using motion retargeting method to adapt it to the overall population.

In our research, we are aiming at creating a trajectory planning and evaluation method to improve the product design during the conceptual design stage. Virtual human modelling is taken to represent the overall population with different anthropometrical data. A single objective optimization based method is used to generate the trajectory at first. Then, motion capture methods or other intervention methods are used to help the algorithm to move out from the local minimum. At last, multi-objective evaluation methods are going to be used to evaluate the generated trajectory.

2-Trajectory planning algorithm

A virtual human is modelled using the modified Devanit-Hartenberg method [KD] with 28 degrees of freedom (DOF) to describe the mobility of all the key joints around human

Copyright IDMME -Virtual Concept body. The kinematic information could be described by a set of general coordinates   q , q , q   , where q is the set of the rotational angles representing the positions of each joint [START_REF] Ma | Multi-objective optimisation method for posture prediction and analysis with consideration of fatigue effect and its application case[END_REF].

2.1 -Single objective optimization 2.1.1 -Trajectory planning algorithm This single objective optimization (SOO) based method was proposed by [RM] in order to generate the trajectory automatically, and its principle is shown in Fig. 1. In this algorithm, the distance between the end effector and the destination is chosen as an objective function. For a virtual human, the position of the destination is known and the current posture q is also known. A change (±dq) to the current posture configuration is added to obtain several posture candidates for the next movement. Candidates without collision to the virtual environment are selected out via collision test. The one among the rest candidates with the smallest distance is selected to update the current posture. One of the greatest technical problems in this method is the local minimum encountered while searching the direction to the destination. This problem is illustrated by a simple example in Fig. 2. During the trajectory planning, it is very possible that the optimization process will encounter the local minimum. In this case, this algorithm will be trapped and cannot advance anymore to its global minimum. In this case, the step length dq can be modified to skip the local minimum, or the configuration q can be changed by another posture configuration. These modifications need to be done using external intervention.

-Technical problem

-Trajectory planning via external intervention

-Modified algorithm

As what has been discussed in the section 2.1, the single objective optimization method cannot avoid local minimum and that results in no evolution for finding a trajectory to the destination. Therefore, a modified algorithm is proposed in this section using external intervention to overcome this difficulty. The algorithm is presented in Fig. 3. Since the step length is constant without intervention, if a posture q has appeared again in the trajectory, there comes local minimum in the trajectory. Get a new q from external intervention end if 4. Update current posture q 5. Update the distance D 6. Add the current new posture q to the trajectory Traj end while SOO based algorithm 1 Get current posture q Initialize the trajectory Traj by adding q to tail Current position of the end effector P_end=direct_kinematic(q) Distance D=Dist(P_end, P_des) while D>ε 1. Generate a set of new postures in the neighbourhood (q±dq) 2 .Select the collision-free postures Calculate the distances Dist_set 3. Find out the nearest collision-free posture q=min(Dist_set) 4. Update current posture q 5. Update the distance D 6. Add the current new posture q to trajectory Traj end while

Copyright IDMME -Virtual Concept

In a virtual space, just using algorithm along could plan a path for the virtual human (Fig. 4(a)). At the same time, operating the virtual human directly by changing its rotational configuration manually could also avoid the obstacles to get to the target position (Fig. 4(b)). Each way has its disadvantages: using Fig. 4(a) will encounter the local minimal obviously; using Fig. 4(b) is difficult to generate human-like action and much more time consuming. For these reasons, the co-operator principle (Fig. 4(c)) is implemented by us to combine the advantages of each way to get a better result [CC].

In order to solve these problems, the direct method is to provide a graphical interface to change the configuration: the posture q or the step length dq. Through changing these parameters the mannequin can be lead to go out of the local minimum situation. Another solution is using motion capture method to skip the local minimum.

In the first solution, changing the posture q can guide the mannequin out of the local minimum situation, but it should be known that it is difficult to have an intuitive manipulation to operate the virtual human by changing the rotational configuration. It requires much more time to manipulate the angular variables directly. Enlarging the step length dq can also guide the mannequin to move out the local minimum situation, but the path will not be so smooth.

In the second solution from a motion tracking system, different motion data of a human body can be obtained. The virtual human could be operated much more naturally to skip the local minimum. In the second method, a motion tracking system is required. Accompanying with this method, inverse kinematics or motion retargeting techniques have to be developed to map the motion data to the simulated trajectory.

The main problem is now to define the algorithm which is able to use the principle of the multi-agent system [CC] and to add the information of the motion capture system.

-Multi-objective evaluation

-Ergonomic objectives for evaluating the constrained environment

As we have mentioned in Introduction, there are different aspects that the designers have to respect. To produce a well designed constrained environment, visibility and accessibility are both important factors. Besides them, the physical influence from the environment should also be assessed in some cases. Therefore, a multi-criteria evaluation system is proposed in this section to evaluate the constrained environment.

Accessibility: this term describes whether the user could obtain an access to a certain component in the environment. It could be evaluated by the number of possible trajectory solutions (N). The larger the number of solutions, the easier the component can be accessed. If there is no solution for the trajectory, the component is not accessible by a human being.

Visibility: this term describes the visual accessibility of a component. This term has been modelled or used to analyze workspace in the literature [CC, MJ, SM]. In our research, the visibility is going to be integrated into trajectory planning by treating it as one of the end effectors, since the visible region is also an important factor determining the feasibility of the operation.

Posture effect: this term describes the effect resulting from posture. This is a traditional subject in ergonomic analysis, and there are several conventional methods for evaluating the posture [MA, ME]. During the ergonomic application, duration of the task, posture engaged in the task, and its physical exposures are taken to evaluate the potential risks of the posture.

Fatigue: this term is used to describe the effect of physical load on the human body. It has been modelled in [START_REF] Ma | A New Simple Dynamic Muscle Fatigue Model and its Validation[END_REF] according to physical exposures related to the manual handling operations. This term is used in our research to evaluate the physical effects of the task realized in the constrained environment.

-Technical approach

As discussed before, multi-criteria evaluation system is going to be established to assess different ergonomic aspects of a constrained environment. In this approach, different aspects are mathematically modelled to create objective evaluation. Those results could be useful to improve the design of constrained environment.

Meanwhile, a multi-objective optimization procedure could also be interesting to determine design parameters of a constrained environment. This algorithm is presented in Fig. 5.

Figure 5: Multi-objective optimization based evaluation and trajectory planning algorithm (MOO)

3-Application case

-Systems

In order to realize our algorithm, a virtual reality platform is constructed. This platform includes two parts: simulation system and motion capture system. The simulation system is mainly responsible for the generation of virtual environment, the collision computation, and the automatic trajectory planning. An optical motion tracking system is in charge of capturing motion data and communicating with the simulation system. The simulation system is developed using OpenGL and C++. The virtual skeleton is shown graphically in Fig. 6. The virtual human is combined by ten body parts: head, torso, thighs, shanks, upper arms, and lower arms. Each body part is modelled as a 3DS model file which is composed of hundreds of triangle facts. The virtual skeleton is driven using direct kinematic method by changing angular values of each key joints. Meanwhile, virtual environments could also be loaded from 3DS files which are converted directly from CAD models.

In the motion capture system (Fig 7), there are totally eight CCD cameras to capture the motion in a range of 2mx2mx2m. Nonlinear direct transformation method is used to calibrate all the cameras. After calibration, the system could capture maximum 13 markers at 25Hz [START_REF] Ma | A Framework for Interactive Work Design based on Motion Tracking, Simulation, and Analysis[END_REF]. Although this tracking speed is not enough for capturing accurate motion, it still provides an acceptable speed to adjust the posture.

-Robot trajectory planning

Since there are too many DOFs in a virtual human, at the very beginning of our research, a trial demonstration of the algorithm has been realized by using a RRR robot and several virtual objects in a virtual environment (see Fig. (20,20,40). From these figures, we can see that in the same environment, different size of the RRR robot can come across various situations. This is necessary and also important, because of a product is not just for a fixed user. Various situation or parameters of a subject should be taken into consideration. The lengths of the links are changed demonstrate different effects of dimensional information. In the obstacle avoiding process, there is always possibility of local minimum. In Fig. 11, a demonstration of local minimum is shown.

Virtual Concept P77

-5-

Copyright IDMME -Virtual Concept Since the obstacles locate between the destination and the end effector and the descending direction is also restricted by the obstacles, the algorithm could not skip the local minimum with a step length 0.08.

-Virtual human trajectory planning

Virtual human trajectory planning using the proposed algorithm is still under construction. There are still several steps to complete the demonstration: motion retargeting, modelling of different aspects, and the complete installation of the motion capture system.

Figure 13: Set of mannequins to be used to test new products

The definition of the trajectories should be not just used for one person, because of a product is designed for a given population (Fig. 13). An automatic path planner can calculate the path from a start point to a destination. But imaging that in a complex environment and for many users, sometimes the algorithm might be failed. In this situation, the user interaction has to be limited to minimize design effort. The ergonomic study of the product can be tested thanks to the definition of a set of tasks: taking a mouse, touching the screen (Fig. 14). Different tasks have different aspects to be respected, and different aspects will result different trajectories.

Different sizes, different weights, different tasks, and different design aspects: all these factors lead trajectory planning for a virtual human to a quite difficult problem. The multi-objective evaluation and optimization approach for virtual human trajectory planning has to be developed with caution.

Conclusions and perspectives

In this paper, an approach of using virtual human in constrained environment design was presented, and a new algorithm was proposed to solve trajectory planning. Our preliminary application of the algorithm demonstrates that this interactive method had a potential to help us solve trajectory planning problem in constrained environment. In our future research, a multi-agent system and multi-objective optimization method will be implemented to facilitate the design process of constrained environments.

Figure 1 :

 1 Figure 1: Single objective optimization based trajectory planning method

Figure 2 :

 2 Figure 2: Local minimum encountered in single objective optimization based method

Figure 3 :

 3 Figure 3: Modified SOO based method 2.2.2. -Technical problems An external intervention is implemented via different methods. In this part, a multi-agent thought is introduced into our system. The thought is explained by Fig. 4.

Figure

  Figure 4: Co-operation principles

Figure 6 :

 6 Figure 6: The virtual skeleton in the simulation system

Figure 7 :

 7 Figure 7: Motion Capture System

  8-10). The robot is composed of three rectangles, and the end effector is the right end. The blue round point denotes the destination of the end effector. There are three obstacles (two triangles and one block) in the environment. Different trajectories will be generated by using our algorithm according to the different length of each revolute joint in the RRR robot. Fig 8 shows that trajectory of RRR robot with the link length parameters (20, 10, 20). Fig 9 shows that the trajectory of RRR robot with the link length parameters (20, 20, 25) and Fig 10 shows that the trajectory of RRR robot with the link length parameters

Figure 8 :Figure 9 :Figure 10 :

 8910 Figure 8: Trajectory planning test using a RRR robot (with link length equals 20, 10, 20)

Figure 11 :

 11 Figure 11: Trajectory planning test using a RRR robot (with local minimum, step=0.08)

Figure 12 :

 12 Figure 12: Trajectory planning test using a RRR robot (External intervention interface, step=0.1) In Fig.12, for the same arrangement of obstacles in Fig 10, the step length has been adjusted to 0.1. As a result, the first obstacle could be passed over without problem.

Figure 14 :

 14 Figure 14: Example of office design for two different women

Copyright IDMME -Virtual Concept

5-Acknowledgements

This research is supported in the context of collaboration between the Ecole Centrale de Nantes (Nantes, France) and Tsinghua University (Beijing, P.R.China). The lead author would also like to thank Ecole Centrale de Nantes for the financial support of the post-doctorate studies. The authors would like to address thanks to the financial support of Ecole Centrale de Nantes, Région des Pays de la Loire in the project Virtual Reality for design (VR4D) and China Scholarship Council (CSC).

6-References