J Lerbet

O Kirillov

M Aldowaji

N Challamel

F Nicot

F Darve

Additional constraints may soften a non-conservative structural system: buckling and vibration analysis

Keywords: Stability, Vibrations, Non-conservative problems, Constrained systems, Secondorder work criterion

The effect of additional kinematic constraints on eigenfrequencies of non conservative systems presenting a non symmetric stiffness matrix is investigated with the use of the second order work criterion. It is shown that there are always additional constraints that may soften structural systems, from both buckling and vibration points of view. The steps for building such constraints are given, consequences on stability are discussed and several illustrating examples are presented.

Introduction

As early as 1980, Tarnai discovered a softening effect induced by kinematic constraint in elastic systems. This softening effect was characterized by a decrease of the critical load of divergence instability in conservative systems with equilibrium positions depending on the loading parameters [START_REF] Tarnai | Destabilizing effect of additional restraint on elastic bar structures[END_REF]. Hence, it was shown to be out of the scope of the usual stability analysis of constrained systems based on Rayleigh's well known theory. In the present paper we show that this surprising phenomenon can be observed in non conservative systems too even if the associated equilibrium positions do not depend on the loading parameters. Recently, Challamel et al. [START_REF] Challamel | Stability of non-conservative elastic structures under additional kinematics constraints[END_REF] demonstrated the possible softening effect of additional constraints in the buckling problem of non conservative systems. Here we perform a similar investigation of the spectrum (within the meaning of the set of eigenfrequencies) of the system and we generalize the approach of [START_REF] Challamel | Stability of non-conservative elastic structures under additional kinematics constraints[END_REF] to the vibration analysis. Although the usual framework of investigations involving spectral analysis, vibrations, buckling, divergence or flutter is linear elasticity as, e.g., in [START_REF] Bolotin | Non-conservative problems of the theory of elatic stability[END_REF], the presented approach remains valid in a more general setting, including, e.g., the incrementally piecewise linear evolution. We mean for example the elasto-plasticity if this evolution takes place in a tensorial zone of a purely constitutive problem or external dry friction forces as it was elegantly investigated in Bigoni's recent paper [START_REF] Bigoni | Experimental evidence of flutter and divergence instabilities induced by dry friction[END_REF]. In order to be valid, the dynamic evolution has only to be described by an equation similar to Eq.( 1) of the present paper.

The effect of constraints on systems the dynamics of which is governed by a symmetric stiffness matrix is actually well known since Rayleigh's and Courant's Minimax theorems: the range of the real spectrum is reduced by a kinematic constraint and the lowest eigenfrequency is then always increasing. We show that the effect of a constraint on systems with the dynamics, governed by any (i.e. non symmetric) stiffness matrix may not be a priori forecast. According to the chosen constraint, the lowest eigenfrequency can either increase or decrease. The paper obviously focuses on the decreasing effect, which we call a stiffness softening effect. Section 1 concerns generalities of the spectral analysis of constrained systems investigated with the use of Lagrange multipliers. After performing necessary calculations in Section 2.1, the Section 2.2 presents the main result: as long as the second order work criterion is valid, there always exists a constraint (and it may be chosen in the kernel of the corresponding operator) that leads to a decrease of the lowest eigenfrequency of the system. Consequences on both divergence and flutter instabilities are investigated (subsections 2.3 and 2.4) and several examples (section 3) using Ziegler's 2 degree of freedom column as a mechanical model illustrate the results.

Statement of the problem

As it is already mentioned in the introduction, in the following we will only assume that after having started with different possible non linear settings, convenient assumptions and approximations lead to a dynamic evolution governed by the following equation of motion of the free system Σ f ree :

M Ẍ + K(p)X = 0 (1)
where K(p) is generally a non-symmetric matrix. For circulatory systems like in [START_REF] Bolotin | Non-conservative problems of the theory of elatic stability[END_REF] or more recently in [START_REF] Bigoni | Experimental evidence of flutter and divergence instabilities induced by dry friction[END_REF], we often may write K(p) = K int -pK ext and the internal elastic stiffness matrix K int is symmetric and positive definite. Clearly, the non-conservativeness comes from the external loading, meaning that K ext is generally a non-symmetric matrix. In the present general approach, the dependency p → K(p) is without any importance. M is a symmetric positive definite matrix, p denotes the loading parameter, and X is the perturbation of dimension n.

The buckling/vibrations equation of this free system Σ f ree is obtained for the divergence-type systems as:

f (p, s) = det(K(p) -s 2 M ) = 0 (2)
We assume that for p = 0, the stiffness matrix K(0) of the free system is symmetric positive definite (it obviously holds for circulatory systems because K(0) then reduces to a pure elastic stiffness matrix). Let ω f ree,k (p) be the 2n roots of the polynomial equation ( 2). If they are real, the positive ones are the natural frequencies of the free system. Since for p = 0 (eventually counted with their multiplicity) ω f ree,k (0) ∈ R for all k = 1, . . . , n because of the above assumption about K(0), then, by continuity, there is an interval [0, p max [, such that ω f ree,k (p) ∈ R for all k = 1, . . . , n. For the rest of the paper, we assume that p ∈ [0, p max [ and the natural frequencies are ordered: ω f ree,1 (p) ≤ . . . ≤ ω f ree,n (p).

We will investigate the spectral properties of such a dynamical system in the presence of an additional kinematic constraint, given by the (linear) holonomic constraint (α is a column vector):

α T .X = 0 (3)
The Lagrange multiplier λ can be introduced for the constrained system as:

M Ẍ + K(p)X + λα = 0 (4)
Leading a similar mathematical approach as in [START_REF] Lerbet | P-positive definite matrices and stability of nonconservative systems[END_REF] for example, the buckling/vibrations equation of the constrained system Σ cons (α) is obtained for the divergence-type systems as:

h(p, s, α) = det    K(p) -s 2 M α α T 0    = 0 (5)
In this paper, we investigate the eventual relationship between the eigenfrequencies ω cons,k (p, α)

of Σ cons (α) and the frequencies ω f ree,k (p) of Σ f ree . More precisely, we will compare the lowest eigenfrequencies ω cons,1 (p, α) and ω f ree,1 (p). It should be reminded that for conservative systems, ω cons,1 (p, α) ≥ ω f ree,1 (p) for any constraint (defined by) α. We claim in this paper that for the nonconservative systems with the dynamics governed by Eq.( 1), there is at least one peculiar constraint α such that ω cons,1 (p, α) < ω f ree,1 (p) as long as the symmetric part of K s (p) is positive definite (second order work criterion), and we present this constraint. We stress however that this dynamic softening effect does not mean that such a constraint leads to divergence-instability of the constraint system. On the contrary, it has been already proved in papers like [START_REF] Challamel | Stability of non-conservative elastic structures under additional kinematics constraints[END_REF], [START_REF] Lerbet | P-positive definite matrices and stability of nonconservative systems[END_REF] that, as long as the symmetric part of K s (p) is positive definite (second order work criterion), no kinematic constraints may induce divergence instabilities. These points are discussed in paragraphs 2.3 and 2.4.

The results

Preliminary calculations

Let α be an ncolumn vector. Let us choose s / ∈ {±ω f ree,k (p), k = 1 . . . , n} such that F (p, s) = K(p)-s 2 M is not singular. Similar calculations as in [START_REF] Challamel | Stability of non-conservative elastic structures under additional kinematics constraints[END_REF] but for the matrix

F (p, s) = K(p)-s 2 M
give then successively:

   F (p, s) α α T 0       F (p, s) -1 -F (p, s) -1 α 0 1    =    I n 0 α T F (p, s) -1 -α T F (p, s) -1 α   
Calculating the determinant of each side of the previous relation leads to:

h(p, s, α) f (p, s) = -α T F (p, s) -1 α (6)
Put β = F (p, s) -1 α. (6) reads:

h(p, s, α) = -f (p, s)β T F (p, s)β
which leads, for all s, p such that f (p, s) = 0 (i.e. s / ∈ {±ω f ree,k (p), k = 1 . . . , n}) to:

h(p, s, α) = -f (p, s)β T F s (p, s))β (7)
with

β = F (p, s) -1 α because obviously β T F (p, s))β = β T F s (p, s))β for F s (p, s) = K s (p) -s 2 M
where K s is the symmetric part of K.

Let Σ * be the associated conservative system with stiffness matrix K s (p) and mass matrix M and let {ω * ,k (p), k = 1 . . . , n} be its spectrum which is included in R for all p. These are the roots of the characteristic polynomial of Σ * defined as:

g(p, s) = det(K s (p) -s 2 M ) = det(F s (p, s)) = 0 (8)
This spectrum can also be calculated from the generalized Rayleigh's quotient R s (X) related to the symmetric part K s of K defined by:

R s (X) = X T K s (p)X X T M X
and the smallest positive root ω * ,1 (p) of ( 8) is for example given by:

ω 2 * ,1 (p) = inf X∈R n X T K s (p)X X T M X
For the rest of the paper, p sw denotes the critical load according to the second order work criterion: this is the smallest positive root of the equation det(K s (p)) = 0. For p = 0, K s (0) = K(0) is supposed to be positive definite (as it is assumed above). Thus det(K s (0)) > 0 and there is an open interval I ⊂ R + (by continuity) such that det(K s (p)) > 0 for all p ∈ I. By definition

p sw = inf(I). If I is bounded then p sw ∈ R + . If I is not bounded then p sw = +∞ meaning det(K s (p)) > 0 for all p > 0.
If p f ree,div is the divergence critical load of the free system Σ f ree (the smallest positive root of det(K(p)) = 0), it has already been proved that p f ree,div ≥ p sw ([12] for example) but it obviously follows from the following result proven by Ostrowski and Taussky (1951) [START_REF] Ostrowski | On the variation of the determinant of a positive definite matrix[END_REF]:

If A is any definite positive matrix (meaning that its symmetric part is definite positive), then det(A) ≥ det(A s ) > 0.

Main results and stiffness softening effect of kinematics constraints

Preserving the same notation as in the previous sections, two results on the relation of the spectrum of the free system and that of the constrained and associated systems are derived. The first one is the following:

Theorem 1 ω * ,1 (p) ≤ ω f ree,1 (p) ∀p ∈ [0, p sw [ (9
(p, s) ≥ g(p, s) > 0 for s ∈ [0, ω f ree,1 (p)[. Because ω f ree,1 (p) is the lowest positive root of s → f (p, s) we obviously conclude that ω f ree,1 (p) / ∈ [0, ω * ,1 (p)[ or that ω * ,1 (p) ≤ ω f ree,1 (p). QED Because det(F s (p, ω * ,1 (p))) = 0, dim Ker(F s (p, ω * ,1 (p)) ≥ 1 and we may choose β = β(p) which is nonzero in Ker(F s (p, ω * ,1 (p)). Let now α = α(p) be in F (ω * ,1 (p))(β(p)).
From [START_REF] Guran | Stability of a column with a follower load and a load dependent elastic support[END_REF], h(p, ω * ,1 (p), α(p)) = 0 meaning that ω * ,1 (p) lies in the spectrum of Σ cons (α(p)). From theorem 1 the second result reads as follows:

Theorem 2 For all p ∈ [0, p sw [ there is a constraint α = α(p) such that ω cons,1 (p) ≤ ω f ree,1 (p) (10)
where ω cons,1 (p) = ω cons,1 (p, α(p)) is the smallest eigenfrequency of the constrained system Σ cons (α(p)).

2 Let us choose the constraint α = α(p) as previously. Because ω * ,1 (p) lies in the spectrum of Σ cons (α(p)) it follows that ω cons,1 (p) ≤ ω * ,1 (p). Thus, from (9), we get:

ω cons,1 (p) ≤ ω * ,1 (p) ≤ ω f ree,1 (p)
which allows to conclude.

Because of the last result, we say that the system is softened by the kinematics constraint meaning stiffness softening because of the direct natural relation between the stiffness of the structure and the lowest eigenfrequency for conservative systems through Rayleigh's quotient.

The paradoxical effect resulting from theorem 2 means that there always exists a kinematics constraint that makes the lowest eigenfrequency smaller in contrast to conservative systems.

Definition 1

The constraint α(p) built as above is called the critical or optimal constraint.

Divergence instability

The buckling problem is obtained as a particular case of this equation, where the divergence buckling load p f ree,div of the free system is calculated from det(K(p)) = 0 or equivalently by

ω f ree,1 (p) = 0 (11)
while for the critical constraint α(p), the divergence buckling load p cons,div is calculated from the equation h(p, 0, α(p)) = 0 or equivalently from

ω cons,1 (p) = 0 (12)
Thus, from [START_REF] Kirillov | Paradoxes of dissipation-induced destabilization or who opened Whitney's umbrella?[END_REF], [START_REF] Kirillov | Standard and helical magnetorotational instability: How singularities create paradoxical phenomena in MHD[END_REF] and [START_REF] Lerbet | About the stability of nonconservative undamped elastic systems: some new elements[END_REF] we deduce that

p cons,div ≤ p f ree,div (13)
Thus, we reproduce by another way the result obtained in [START_REF] Challamel | Stability of non-conservative elastic structures under additional kinematics constraints[END_REF] showing that there always exists a kinematic constraint such that the critical divergence load of the corresponding constrained system is lower than that of the free system and the optimal one is given by the second order work criterion (see e.g. figure 2).

Flutter instability

As mentioned in [START_REF] Challamel | On the stability of nonconservative elastic systems under mixed perturbations[END_REF], there is no direct relationship between the second order work criterion p sw and the critical flutter load p f ree,f l meaning that we may meet p sw < p f ree,f l or p sw > p f ree,f l according to the considered system while p sw ≤ p f ree,div always holds. Thus, similar conclusions hold with p cons = p cons,div and both following situations may occur illustrated in figures 3 and 5 obtained with two different mass matrices and two different values of γ. On figure 3 calculated for a complete follower force (γ = 1) and a uniform mass distribution, we observe that

ω cons,1 (p) ≤ ω * ,1 (p) ≤ ω f ree,1 (p
) for all p ∈ [0, p sw [ and p cons = p cons,div ≤ p f ree,f l while on the figure 5 calculated for a partial follower force (γ = 1 2 ) and another mass matrix, we observe that ω cons,1 (p) ≤ ω * ,1 (p) ≤ ω f ree,1 (p) for all p ∈ [0, p sw [ and p cons = p cons,div ≥ p f ree,f l .

Constraint dependency on the load parameter

Without contradiction to the previous results, it is important to stress that the kinematic constraints are themselves depending on the load parameter p. This phenomenon, already investigated in [START_REF] Guran | Stability of a column with a follower load and a load dependent elastic support[END_REF], is actually the natural consequence of the used method that leads to the optimal constraints for each state of the system, each state precisely depending on the load parameter. The question to know if there is a fixed family of kinematics constraints α not depending on p such that the corresponding constrained system Σ cons (α) still satisfies the condition ω cons,1 (p) ≤ ω f ree,1 (p) for all p ∈ [0, p sw [ is a more difficult problem although there are, by continuity, local results in the neighborhood of each value of the load. For example, there is a neighborhood of p = 0, i.e. an interval [0, p 0 [ such that ω cons,1 (p) ≤ ω f ree,1 (p) for all p ∈ [0, p 0 [ for the constrained system defined by the fixed family of constraints α = α(0) we may call here the fixed constrained system. In figure 6, which is similar to figure 4, the constrained system with fixed p = 0 corresponds to the mixed dashed-dotted gold curve, and we observe that it coincides with the optimal one (dotted blue) on the whole interval [0, p sw [ while on figure 7 plotted for γ = 3 4 , the curve of the fixed constrained system (mixed dashed-dotted gold) coincides only on a subinterval [0, p 0 [ of [0, p sw [ with the optimal constrained system (dotted blue), the eigenfrequency of the fixed constrained system being always higher than (or equal to) the one of the optimal constrained system: this is the property of optimality.

Examples

The mechanical model

To illustrate the previous results, consider the following 2 dof Ziegler column (see figure 1)

( [START_REF] Ziegler | Die Stabilitätskriterien der Elastomechanik[END_REF][START_REF] Bottema | The Routh-Hurwitz condition for the biquadratic equation[END_REF][START_REF] Kirillov | Paradoxes of dissipation-induced destabilization or who opened Whitney's umbrella?[END_REF]). The system Σ consists of two bars OA, AB with OA = AB = linked by two elastic springs with the same stiffness k. The circulatory non conservative load P is such that P , y = γθ 2 with 0 ≤ γ ≤ 1. For γ = 1, it is a complete follower force while for γ = 0 it is a conservative load. The equilibrium position is θ = (θ 1 , θ 2 ) = (0, 0) and the bars are supposed to be homogeneous according to their mass distribution except for figure 5 obtained for another mass matrix. Adopting a dimensionless format, we use p = P k as loading parameter. If Ω 2 = k m 2 , Ω is then a pure elastic frequency parameter of Σ and to simplify the presentation, we put Ω = 1.

Load-frequency boundary for the free system

The equations of motion (1) then read:

   4 3 1 2 1 2 1 3    Ẍ +    2 -p -1 + γ p -1 1 -(1 -γ) p    X = 0 (14)
and the buckling/vibrations equation (2) of this free system is:

f (p, γ, s) = det(K(p, γ) -s 2 M ) = 1 -3 p + 3 γ p + p 2 -γ p 2 + -3 + 5 3 p -5 6 γ p s 2 + 7 36 s 4
and its smallest positive root is:

ω f ree,

Load-frequency boundary for the associated system

The characteristic polynomial of the associated system Σ * reads:

g(p, γ, s) = det(K s (p, γ) -s 2 M ) = 1 -3 p + 3 γ p + p 2 -γ p 2 -

Calculation of the optimal constraint

We follow now the algebraic procedure to find the convenient kinematics constraint given in the previous section.   so, the constraint is given by the vector:

α =    1 2 γ p

Load-frequency boundary of the optimal constrained system

Because for n = 2 it leads to effective and straightforward calculations, we propose here to explicitly calculate the constrained system although obviously it is not the philosophy of the general reasoning.

The constrained system is obviously a one dof system. The general equations of motion (1) of a constrained 2 dof system read:

                      m 11 m 12 m 21 m 22       ẍ1 ẍ2    +    k 11 k 12 k 21 k 22       x 1 x 2    +    λα 1 λα 2    =    0 0    α 1 α 2    x 1 x 2    = 0
By eliminating the variable x 2 in order to keep only one equation in the single variable x 1 , we get the remarkable following form :

-α 2 α 1    m 11 m 12 m 21 m 22       -α 2 α 1    ẍ1 + -α 2 α 1    k 11 k 12 k 21 k 22       -α 2 α 1    x 1 = 0 (15)
or here (x 1 = θ 1 ) which gives

M cons θ1 + K cons θ 1 = 0 with M cons = -
The buckling/vibrations equation of the constrained system is obtained for the divergence-type systems as:

f cons (p, γ, s) = K cons -M cons s 2
whose the smaller positive root obviously is: 3.6 Discussion and analysis of results

ω cons,1 (p, γ) = 1

Comparison of frequencies at fixed loading parameter p

The validity of the results is restricted to the interval [0, p sw [. As already done in [START_REF] Challamel | Stability of non-conservative elastic structures under additional kinematics constraints[END_REF], the critical value p sw of the loading parameter according to the second order work criterion is the lowest root of

det(K s (p)) = det    2 -p -1 + 1 2 γ p -1 + 1 2 γ p 1 -(1 -γ) p    = 0
which leads here to

p sw = 2 (-3 + 3 γ + 5 -14 γ + 10 γ 2 ) -4 + 4 γ + γ 2 .
For γ = 1, the system is Ziegler's model with complete follower load. In this case, the free system loses its stability by flutter. Let us then choose p < p sw = 2, for example p = 3 2 . We then find the corresponding numerical values of the lowest frequencies

ω * ,1 3 2 , 1 ≈ 0.5073 ≤ ω f ree,1 3 2 , 1 ≈ 0.7830
More precisely, the positive roots of det(

F s ( 3 2 , 1, s) = 0 are √ 3 -1 2 √ 6 , √ 3 + 1 2 √
6 and thus, with previous notations ω * ,1

( 3 2 , 1) = √ 3 -1 2 √ 6 ≈ 0.5073.
We obviously conclude that

ω cons,1 3 2 , 1 ≈ 0.5073 ≤ ω * ,1 3 2 , 1 ≈ 0.5073 ≤ ω f ree,1 3 2 , 1 ≈ 0.7830
This is illustrated on figure 2 where the characteristic polynomials and their lowest positive roots (the optimal constrained system in dotted blue line (unique root ω cons,1

2 , 1 ≈ 0.5073) are plotted, the associated system in plain green line (lowest root ω * ,1 3 2 , 1 ≈ 0.5073) and for the free system in dashed red line (lowest root ω f ree,1

3 2 , 1 ≈ 0.7830). For γ = 1 2 . Let us choose p < p sw = 12-4 √ 2 7
≈ 0.9061, for example p = 1 2 . Corresponding numerical values are

ω cons,1 1 2 , 1 2 ≈ 0.3914 ≤ ω * ,1 1 2 , 1 2 ≈ ≤ ω f ree,1 1 2 , 1 2 ≈ 0.3999
It is worth mentioning that any kinematic constraint changes a two degree-of-freedom circulatory non-conservative system into a one-degree-of-freedom conservative system. Especially for γ ∈ [ 1 2 , 1[ the critical load by divergence of the constrained system p cons,div (for any kinematic constraint) is necessarily strictly lower than the critical load by divergence of the free system p f ree,div = +∞!!! (see [START_REF] Challamel | On the stability of nonconservative elastic systems under mixed perturbations[END_REF] for example). Viewed as the decreasing of the critical divergence load, any additional kinematic constraint has then a destabilizing or a sort of stiffness softening effect. This stiffness softening effect however may fail if it is viewed as the decreasing of the lowest eigenfrequency of the system for a given constraint. For example with the constraint θ 1 = θ 2 and for the loading p = 1 2 , γ = 1 2 , we find ω cons,1

( 1 2 , 1 2 ) = √ 3 4 ≈ 0.4330 > ω f ree,1 1
2 , 1 2 ≈ 0.3999.

Frequencies as functions of the loading parameter. Comparison. Stability.

Concerning the flutter instability, because it depends on the considered system, it has been already discussed in 2.4.

For γ = 1, we then find ω f ree,1 (p, 1) =

leading to figure 3 where, as mentioned in 2.4:

ω cons,1 (p) ≤ ω f ree,1 (p) and p cons = p cons,div = 2 ≤ p f ree,f l = 18 5 - 2 5 √ 7 ≈ 2.5416
The non-constrained pendulum is stable at positive p when p < p f ree,f l and unstable by flutter when p > p f ree,f l .

For γ = 1 2 , we then find

ω f ree,1 (p, 1 2 )

Dependency on p

As already discussed in (2.5), the variety of the loading dependency of the constraints is illustrated here on figures 6 and 7. Comparison of the loading dependency optimal constraint and the fixed constraint is done with the fixed p = 0 constraint by adding the curve of the fixed constraint (mixed dashed-dotted gold line) on previous figures 3 and 4. In the first case the added curve coincides with the curve of the optimal constrained system: the optimal constraint is exactly the fixed p = 0 constraint on the whole interval [0, p sw [. In the second one, the added curve does not coincide with the curve of the optimal constrained system and is obviously over the optimal one because precisely the optimality of the constraint.

A singular surface

Finally, we study the frequency of the constrained pendulum as a function of the coefficients of the constraints, α 1 and α 2 in the assumption that γ = 1. According to Eqs. ( 14) and ( 15), this frequency is a root of the polynomial

4 3 α 2 2 -α 2 α 1 + 1 3 α 2 1 ω 2 = 2α 2 2 -α 2 2 p + 2α 2 α 1 -α 2 α 1 p + α 2 1 .
Since the roots depend only on the ratio of the two coefficients, then, introducing α 1 = cos(φ)

and α 2 = sin(φ), we find

ω 2 cons =
-2 -2 sin(φ) cos(φ) + sin(φ) cos(φ)p + cos(φ) 2 + p -cos(φ) 2 p sin(φ) cos(φ) -4/3 + cos(φ) 2 .

In the (φ, ω) plane let us plot the two frequencies, ω f ree,1 and ω cons , for different values of p that are inside the stability interval of the free system, see Fig. 8. The horizontal lines in Fig. 8 show ω f ree,1 for a given p, whereas the curves show the frequencies of the constrained pendulum ±ω cons .

The frequency ω cons,1

2 , 1 ≈ 0.5073 is achieved at a unique constraint that corresponds to the minima visible in the panels (a) and (b) of figure 8. On the panel (a) the minimum is the frequency ω cons,1 3 2 , 1 ≈ 0.5073. For p = 2 it is zero. For p > 2 there is a divergence interval, and the minimal frequencies are zero at its ends, see the panel (c) of figure 8. Therefore, at every p from the stability interval of the free pendulum there is a continuum of the ratios of α 1 to α 2 that yields the effect of softening. The constraint that is found from the general theory developed above is the optimal one, because it gives the minimal possible frequency.

In the (α 1 , α 2 , ω cons ) space we plot the surfaces of frequencies of the constrained system as functions of α 1 and α 2 , see figure 9. The panel (a) corresponds to p = 1.5 and shows two Plücker conoids of degree 2 [START_REF] Berger | Differential Geometry: Manifolds, Curves and Surfaces[END_REF][START_REF] Kirillov | Standard and helical magnetorotational instability: How singularities create paradoxical phenomena in MHD[END_REF]. The panel (b) shows one Plücker conoid of degree 1. The right panel shows the conical wedge of Wallis known in the physical literature under the name of the double coffee-filter [START_REF] Berger | Differential Geometry: Manifolds, Curves and Surfaces[END_REF][START_REF] Kirillov | Standard and helical magnetorotational instability: How singularities create paradoxical phenomena in MHD[END_REF]. The three classical ruled surfaces demonstrate how the constraints introduce singularities in the behavior of eigenfrequencies which explains their high sensitivity to the variation of the constraints coefficients.

Conclusion

In this paper, we generalized the possible paradoxical softening effect that originates after kinematic constraints are applied to a system. We investigated this stiffness softening effect by means of the spectral analysis of the free and constrained systems. With the use of the second order work criterion, it is established that, for each value of the load parameter, there always exists a (family of) constraint(s) allowing to make the lowest eigenfrequency of the system smaller. 2 , 1, s) (dashed red), the associated system characteristic polynomial g( 3 2 , 1, s) (plain green) and the (optimal) constrained system characteristic polynomial h( 32 , 1, s, α) (dotted blue): associated and constrained systems characteristic polynomials have the same lowest root that is lower than the one of the free system 3: γ = 1 Eigenfrequencies ω functions of the load parameter p: lowest eigenfrequency of the free system (plain red), highest eigenfrequency of the free system (dashed green) and (optimal) constrained system (dotted blue): the free system has no divergence instability but only flutter instability and the constrained system has a divergence load which is smaller than the flutter load of the free system Eigenfrequencies ω as functions of the load parameter p: lowest eigenfrequency of the free system (dashed green), highest eigenfrequency of the free system (plain red) and (optimal) constrained system (dotted blue): the free system has no flutter but only flutter instability and the constrained system has a divergence load which is smaller than the divergence load of the free system Figure 5: γ = 1 and another mass matrix. Eigenfrequencies as functions of the load parameter p: lowest eigenfrequency of the free system (dashed green), highest eigenfrequency of the free system (plain red) and (optimal) constrained system (dotted blue): the free system has no divergence instability but only flutter instability and the constrained system has a divergence load which is larger than the flutter load of the free system Figure 6: Eigenfrequencies ω as functions of the load parameter p: lowest eigenfrequency of the free system (dashed green), highest eigenfrequency of the free system (plain red) , optimal constrained system (dotted blue) and fixed (p = 0) constrained system (mixed dashed-dotted gold): the optimal constraint and the fixed constraint give the same curve.

Figure 7: Eigenfrequencies ω as functions of load parameter p: highest eigenfrequency of free system (dashed green), lowest eigenfrequency of the free system (plain red), optimal constrained system (dotted blue) and fixed (p = 0) constrained system (mixed dashed-dotted gold): the optimal constraint curve is lower than the fixed constraint curve.

) 2

 2 Suppose p ∈ [0, p sw [ which means that K(p) (or equivalently K s (p)) is positive definite and let be s ∈ [0, ω * ,1 (p)[. Thus, because g(p, 0) = det(F s (p, 0)) = det(K s (p)), then f (p, 0) ≥ g(p, 0) > 0. Moreover, as long as g(p, s) > 0 the eigenvalues of the real symmetric matrix F s (p, s) cannot vanish and because for s = 0 they are all > 0 (K s positive definite), they are all > 0 for s ∈ [0, ω * ,1 (p)[ which means that F (p, s) remains positive definite for s ∈ [0, ω * ,1 (p)[. Applying then the above result of Ostrowski and Taussky, we deduce that f

  ker(F s (p, γ, ω * ,1 )) = Vect subspace Vect (K s -ω 2 * ,1 .M ).x 1 generated by the vector (K s -ω 2 * ,1 .M ).x 1 is the one-dimensional subspace Vect

  34 + 4 γ p -15 p -3 a) 58 -33 p + 20 γ p -8 a θ 2 = 0 or (58 -33 p + 20 γ p -8 a) θ 1 + (34 + 4 γ p -15 p -3 a) θ 2 = 0

Finally

  [START_REF] Challamel | On the stability of nonconservative elastic systems under mixed perturbations[END_REF] where, as mentioned in 2.4:ω cons,1 (p) ≤ ω f ree,1 (p) and p cons = p cons,div = 2 ≥ p f ree,f l = 5 -2 (3) ≈ 1.536

  Moreover, the second order work criterion provides, in a certain sense, the optimal kinematic constraint. The consequences for the divergence and flutter instabilities are discussed and numerous examples illustrating the results are considered. The behavior of eigenfrequencies as functions of both the load parameter and constraints are also studied. It shows a variety of possible situations for occurrence of flutter and reveals the typical singularities on the eigenfrequency surfaces. The important and difficult problem of finding a global (meaning independent on the load parameter) stiffness softening kinematic constraint is still open.

Figure 1 :Figure 2 :

 12 Figure 1: 2 dof Ziegler's column with partial follower force;γ = 1 corresponds to complete follower force

Figure 4 :

 4 Figure 4: γ = 1 2Eigenfrequencies ω as functions of the load parameter p: lowest eigenfrequency of the free system (dashed green), highest eigenfrequency of the free system (plain red) and (optimal) constrained system (dotted blue): the free system has no flutter but only flutter instability and the constrained system has a divergence load which is smaller than the divergence load of the free system

Figure 8 :

 8 Figure 8: In the (φ, ω) plane the frequencies ω f ree,1 (horizontal lines) and ω cons for (a) p = 1.5, (b) p = 2, and (c) p = 2.1

Figure 9 :

 9 Figure 9: In the (α 1 , α 2 , ω cons ) space the surfaces of frequencies of the constrained system plotted for (a) p = 1.5, (a) p = 2, (c) p = 2.1

7

  √ 21 592 + 192 γ p -552 p + 64 γ 2 p 2 -144 γ p 2 + 144 p 2 -58 a -20 γ p a + 33 p a 19240 -28744 p + 12160 γ p + 14754 p 2 -13704 γ p 2 + 653 γ p 2 a + 4000 γ 2 p 2 -2628 p 3 -2228 a -1034 γ p a + 2278 p a -228 γ 2 p 2 a -2608 γ 2 p 3 + 4068 γ p 3 -618 p 2 a + 640 γ 3 p 3 1

2 592 + 192 γ p -552 p + 64 γ 2 p 2 -144 γ p 2 + 144 p 2 -58 a -20 γ p a + 33 p a (18)

  16584 p + 5050 p 2 -528 p 3 -2228 74 -45 p + 8 p 2 +1244 p 74 -45 p + 8 p 2 -193 p 2 74 -45 p + 8 p 2 592 -360 p + 64 p 2 -58 74 -45 p + 8 p 2 + 13 p 74 -45 p + 8 p 2

				in : International Journal of Solids and Structures, vol 50, n°2, 2013. p.363-370
	and
	ω cons,1 (p, 1) =	1 7	√	21 19240 -1
				2
				13

1 7 378 -21 296 -180 p + 25 p 2 -105 p ω f ree,2 (p, 1) = 1 7 378 + 21 296 -180 p + 25 p 2 -105 p

  592 -456 p + 88 p 2 -58 74 -57 p + 11 p 2 + 23 p 74 -57 p + 11 p 2

									=	1 7	378 -21 296 -228 p +	169 4	p 2 -	315 2	p
					ω f ree,2 (p,	1 2	) =	1 7	378 + 21 296 -228 p +	169 4	p 2 -	315 2	p
	and
	ω cons, 1 2	(p,	1 2	) =	1 7	√	21 19240 -22664 p + 8902 p 2 -1166 p 3 -2228 74 -57 p + 11 p 2
						+1761 p 74 -57 p + 11 p 2 -	697 2	p 2 74 -57 p + 11 p 2
										-1	1 2
										(20)
	leading to figure 4 where, as mentioned in 2.3:
	ω cons,1 (p) ≤ ω f ree,1 (p) and p cons = p cons,div =	12 7	-4/7	√	2 ≈ 0.906 ≤ p f ree,div = 1

in : International Journal of Solids and Structures, vol 50, n°2, 2013. p.363-370


Ramazan Gokberk Cinbis

Stan Sclaroff

Contextual Object Detection using Set-based Classification

We propose a new model for object detection that is based on set representations of the contextual elements. In this formulation, relative spatial locations and relative scores between pairs of detections are considered as sets of unordered items. Directly training classification models on sets of unordered items, where each set can have varying cardinality can be difficult. In order to overcome this problem, we propose SetBoost, a discriminative learning algorithm for building set classifiers. The SetBoost classifiers are trained to rescore detected objects based on object-object and object-scene context. Our method is able to discover composite relationships, as well as intra-class and inter-class spatial relationships between objects. The experimental evidence shows that our set-based formulation performs comparable to or better than existing contextual methods on the SUN and the VOC 2007 benchmark datasets.

Introduction

Object detection is among the most difficult problems in computer vision. Part of this difficulty is caused by ambiguities in low-level features due to background clutter, occlusions, etc., and also by the large amount of variance in the domain.

Recent studies [START_REF] Blaschko | Object localization with global and local context kernels[END_REF][START_REF] Desai | Discriminative models for multi-class object layout[END_REF][START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF] have shown that modeling contextual relationships can help overcome such challenges and improve object detection performance.

In many computer vision tasks, image entities can naturally be represented as sets of items, where each item is a high-dimensional data point. For example, an object in an image can be represented by a set of local image patches. These image patches can be described with various image statistics, such as color and/or shape features. Similarly, the scene of an image can be represented by the set of detected objects within.

Based on these observations, we argue that the contextual relationships can also be represented in terms of sets, where each contextual element is a highdimensional item in the set. In this representation, two main contextual relationships can be considered. First is the object context: some object classes tend to co-occur in particular spatial arrangements, e.g., a person riding a horse. Second is the scene context: some objects tend to be in particular arrangements with respect to the overall scene layout, e.g., cars in a street.

In order to model object context, we first use single object detectors to obtain object detection candidates. We then consider each detection as a reference object and represent its context via the set of the other candidate detections in the 1 Fig. 1. Illustration of our set-based contextual object detection approach. The example reference object(touchpad) is shown with a red rectangle. The contextual properties of each detection relative to the reference object is encoded by a feature vector. The set of all descriptors define the contextual representation surrounding the reference object. The process is repeated by considering each candidate detection as the reference object.

image. Fig. 1 illustrates our representation. The reference object (touchpad) can be difficult to recognize by itself due to ambiguities in the local features or unfamiliar appearance. However, the other objects in the image can give strong cues that the reference object may be a touchpad. To account for this, our context model includes the set of descriptors for the other objects detected in the scene. We describe each item using its detection score, class, and relative bounding box with respect to the reference object. By evaluating these object detections in a set framework, we rescore each of the detections based on the other candidate detections. In addition to object context, we also model scene context in terms of coarse scene shape and the object's spatial position.

Representations that are based on sets of (unordered) high-dimensional items, where each set can have varying cardinality, can be difficult to use directly. Therefore, many of the existing approaches use either individual items, or intermediate representations. Individual items may not contain sufficient information for accurate classification. Using intermediate representations, such as a histogram of quantized items [START_REF] Gemert | Comparing compact codebooks for visual categorization[END_REF], is a common trick to build models. However, such intermediate representations may not be optimum for the final classification task.

In order to work directly with sets and bypass the intermediate representations, we propose a discriminative learning algorithm for set classification, which we call SetBoost. SetBoost is a weakly-supervised learning algorithm in the sense that it requires labels of sets during training but it does not require item labels. This feature allows the algorithm to deal with irrelevant and noisy items.

Our context model has several notable features. First, it can learn the contextual relationships of objects without predefining the relationship types. For example, it can discover composite relationships like "mouse above a table and below a screen", without the need for explicit categorization of spatial relations. Second, it can learn both intra-class and inter-class spatial relationships. Third, our formulation can learn to select one or more detections from a set of overlapping detections and implicitly execute non-maxima suppression [START_REF] Desai | Discriminative models for multi-class object layout[END_REF].

To evaluate the performance of our approach, we use two object detection benchmark datasets: VOC 2007 [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF] and SUN [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF]. Average precision (AP) scores [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF] are used to quantify performance. When we apply our context model to the outputs of the baseline object detectors, we observe significant improvements both on the VOC 2007 dataset and on the SUN dataset. By these results, we demonstrate that our set-based contextual representation provides an improvement over state-of-the-art object context models [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF][START_REF] Desai | Discriminative models for multi-class object layout[END_REF] and performs comparable to [START_REF] Li | Extracting adaptive contextual cues from unlabeled regions[END_REF], which combines background context and object context. We also show that the proposed SetBoost algorithm is more effective than using bag-of-words or PMK [START_REF] Grauman | Approximate correspondences in high dimensions[END_REF].

Related Work

Contextual relationships can be represented in terms of the relations between local image patches [START_REF] Heitz | Learning spatial context: Using stuff to find things[END_REF][START_REF] Liu | Nonparametric scene parsing: Label transfer via dense scene alignment[END_REF], objects [START_REF] Galleguillos | Object categorization using cooccurrence, location and appearance[END_REF][START_REF] Desai | Discriminative models for multi-class object layout[END_REF][START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF], coarse scene characteristics [START_REF] Oliva | Modeling the shape of the scene: A holistic representation of the spatial envelope[END_REF], local background regions [START_REF] Li | Extracting adaptive contextual cues from unlabeled regions[END_REF] and the geometric layout of the scene [START_REF] Hoiem | Putting objects in perspective[END_REF] (see [START_REF] Galleguillos | Context based object categorization: A critical survey[END_REF] for a review). In this paper, we focus on modeling the relationships of objects with respect to other objects and the global scene characteristics.

Choi et al. [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF] propose a tree-structured graphical model to encode object and scene context. Each detection is mapped to a 3D coordinate frame according to predefined object heights, assuming that the camera type and object heights do not change drastically. Spatial relationships are modeled by fitting Gaussian distributions to the relative 3D positions of the object class pairs. In contrast to the generative training of [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF], our context model is discriminatively trained. In addition, we do not make assumptions about the underlying distribution of spatial relationships of objects.

Desai et al. [START_REF] Desai | Discriminative models for multi-class object layout[END_REF] use a structured prediction model to encode relationships of pairs of objects. They quantize the relative locations and sizes of object bounding boxes into predefined categories (above, below, etc.) and the weights of these relationship categories are learned via Structural SVMs. We do not predefine relationship categories; instead, we learn relationships that are important for contextual object detection. Moreover, we directly train our discriminative model to "rescore detections", whereas [START_REF] Desai | Discriminative models for multi-class object layout[END_REF] first trains the model to select a subset of detections and then uses an approximation to rescore these detections.

In [START_REF] Felzenszwalb | Grishick: Object detection with discriminatively trained part based models[END_REF], each detection is re-scored according to its location and the score of the top detection from each class. In contrast, our approach utilizes multiple detections from each class and their relative spatial relationships, which allows much richer context models.

Set-based Classification. One way to formulate the set-based learning problem is to use set kernels. Some kernels proposed for this purpose compare parametric distributions of items [START_REF] Kondor | A kernel between sets of vectors[END_REF][START_REF] Cuturi | Semigroup kernels on finite sets[END_REF], some find correspondences between the items explicitly [START_REF] Lyu | Mercer kernels for object recognition with local features[END_REF] or implicitly [START_REF] Grauman | Approximate correspondences in high dimensions[END_REF]. The Pyramid Match Kernel (PMK) [START_REF] Grauman | Approximate correspondences in high dimensions[END_REF] is particularly appealing as an efficient and effective set kernel. For a given pair of sets, PMK first quantizes the feature space into a multi-resolution grid and counts the number of items for each set within each grid cell. SetBoost differs from PMK in the sense that it can be used to discriminatively learn different weights for different feature dimensions. For example, in SetBoost with decision trees, the partitions and their weights are found by discriminative training, whereas in PMK, they are defined by a heuristic. The learned partitioning and weights in SetBoost can provide appropriate feature selection.

In contrast with codebook based approaches [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF][START_REF] Moosmann | Randomized clustering forests for image classification[END_REF][START_REF] Gemert | Comparing compact codebooks for visual categorization[END_REF], rather than optimizing an intermediate codebook, SetBoost directly minimizes the loss function on the training data. In this respect, our approach bears similarities to [START_REF] Yang | Unifying discriminative visual codebook generation with classifier training for object recognition[END_REF], which includes a boosting algorithm using sets of interest points for image classification. However, [START_REF] Yang | Unifying discriminative visual codebook generation with classifier training for object recognition[END_REF] supports only a specific loss function and SVM item classifiers, whereas SetBoost can be used with any non-increasing margin loss function and any item classifier. Moreover, spatial information is ignored in [START_REF] Yang | Unifying discriminative visual codebook generation with classifier training for object recognition[END_REF].

Multiple Instance Learning (MIL) has some similarities to set-based classification. For example, in [START_REF] Dollar | Multiple component learning for object detection[END_REF], AdaBoost is used with a (weak) MIL classifier for object detection. In MIL, the aim is commonly to learn a model for classifying individual instances, instead of bags. This differs from the set-based classification problem, where the items in a set together form a descriptor.

Contextual Object Detection

Contextual object detection tries to exploit the fact that many objects tend to exist in particular arrangements in natural scenes. Object-object and objectscene relationships are two important types of contextual cues. Object-object relationships include co-occurrences, relative positions, and relative sizes of objects, e.g., "keyboard and mouse". Object-scene relationships include expected object presence and position according to the characteristics of the scene, e.g., "refrigerator in a kitchen". In this section, we first review how we represent the object-object and object-scene context in terms of sets. In the next section, we present our algorithm for learning this set-based context model.

Modeling Object-Object Relationships

To model object-object relationships that may be present within images, we first apply available object detectors and obtain a set of detections together with their initial classification scores. We then use our context model to rescore each detection based on all other detections in the image, i.e., we find the probability of a detection given the evidence from all other detections in the image.

A set-based representation follows our definition of this contextual rescoring. We consider each detection as the reference object and the rest of the detections in the image as items of the set representing the object-object context for the reference object. Each item is represented by a feature vector that encodes the spatial relationship, class and detection confidence of the item with respect to the reference object. A classifier is then used to rescore the reference object detection based on this set of feature vectors computed for the other detections.

Table 1. Features used in our set-based representation. Each detection is represented by a small number of features computed relative to the reference object. The formulae for the features used in forming x are given in Table 1 and summarized below.

Classwise encoded score: We create a vector of length C where its c-th dimension is set to d s and all other dimensions are set to zero. In this encoding, a single threshold on a score dimension (e.g., decision tree node) can filter both the class and score of a detection.

Spatial relations: Several features encode spatial relations of objects. We normalize these features with respect to the height (or width) of the reference object's bounding box to achieve a degree of invariance to scale changes.

-Relative y: Many object class pairs have a distinctive relative y location, e.g., bicycle-person. We do not consider the relative x location since it varies significantly due to changes in perspective. -Relative y (abs): This feature is useful in cases where the relative vertical location can be "above" or "below". For example, objects on a table may appear above or below the center of the table's bounding box. -Relative height and width: We introduce these features to encode the relative scales of objects. -Distance: Contextual interaction may decrease as objects appear farther away from each other.

Overlap ratio: A high overlap between a pair of objects may indicate high contextual coherence, as well as, conflict. For example, an overlapping "mug and table" pair is likely to be contextually coherent, whereas one of the detections in an overlapping "car and table" pair is likely to be incorrect.

Relative scores: These features are intended to help in learning inter-class and intra-class relationships. If one of the object detections has a "significantly" higher score, then the context model may prefer that detection. The "significance" depends on the object classes, and can be learned during training.

In the end, each item descriptor x is a C + 8 dimensional vector, where C is the number of object classes. We evaluate the effect of these features in Sec. 5. Learning. During training, we assume that the training images have ground truth annotations of object bounding boxes for the classes of interest. We first run the baseline object detectors for each class. Then, we evaluate each output of the object detectors using the ground truth bounding boxes and the VOC detection evaluation criteria [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF]. The true positive detections are used as the positive training samples, whereas the false positives are used as the negative training samples for our algorithm. Given the resulting training set, we learn an object-object context model for each object class separately via our learning framework as described in Sec. 4.

In Fig. 2, we show two examples of relationships learned by our model on the VOC 2007 dataset [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF]. In each example, a person detection is used as the example reference object (shown with a white bounding box). The other detected objects are colored by their estimated degree of contextual interaction with the reference object, where red and blue colors correspond to positive and negative interactions, respectively. We observe that our model estimates strong coherence between the pairs "person-horse" and "person-bicycle" in these examples.

Modeling Object-Scene Relationships

For modeling relationships between objects and the scene (scene context), we use GIST descriptors to describe global scene characteristics [START_REF] Oliva | Modeling the shape of the scene: A holistic representation of the spatial envelope[END_REF] and encode the relationships between the objects and the scene as a feature vector. For each detection d in an image with height I h and width I w , we create the feature vector

u d = [ dy I h , d h I h , dw Iw , GIST]
. Our scene context model has similarities to [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF], which also uses GIST descriptors. However, we learn a classification model over spatial position, i.e., the location and size of objects and the scene characteristics jointly, whereas spatial information is discarded in the scene context model of [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF].

Learning. Any vector classifier might be employed to classify a given u d vector. In our framework, we use SetBoost, by considering each u d as a singleton set, with decision tree weak classifiers. For training, we use the same approach that we use in the object-object context model, i.e. for each class we train a classifier over the true and false positive detections. In a test image, a scene context score is obtained by applying the corresponding model to each detection.

Combining Scores

The object and scene context models provide separate scores for each (reference) object. These models do not utilize the detection scores of the reference objects directly; therefore, it is important to combine the raw detection score d s with the context-based scores for the final classification. For this reason, we always use a linear combination of the scores given by the context model(s) and the baseline detector. Combination weights are determined via linear SVMs training.

Learning Set Classifiers via SetBoost

Given training data, we want to build a classifier that operates on sets. Let {X 1 , ..., X N } be the training examples. Each training example X i (i.e., context for i-th reference object) is a set of high-dimensional points x ∈ X i , referred to as items (i.e., context descriptors). For the sake of brevity, we assume that each item is a d-dimensional vector. Each X i has an associated binary class label y i ∈ {-1, +1} corresponding to true positive or false positive detection.

Our goal is to learn a classification function G : X → R such that it minimizes the total loss L(G) = N i=1 L(y i G(X i )) where L(z) : R → R is a loss function (We use exponential loss L(z) = e -z ) and L is the loss functional. In accordance with the boosting terminology, we define strong set classifier G(X) = T t=1 F t (X), where each F t : X → R is a weak set classifier. Each weak set classifier F t is based on a weak item classifier f t :R d → R weighted by some non-negative α t :

F t (X) = α t x∈X k x f t (x) (1)
where the k x are (optional) item weights. Defining k x allows us to introduce prior knowledge on the relevance of an item. We set the k x to the item detection scores in our context model to emphasize high-confidence detections. We use functional gradient descent interpretation of boosting, specifically MarginBoost framework [START_REF] Mason | Boosting algorithms as gradient descent in function space[END_REF], in developing our learning algorithm. According to this interpretation, at each iteration, a new weak classifier F is added such that F minimizes the loss functional L(G+ F ). Assuming L is a non-increasing function, L(G + F ) can be minimized by choosing the weak classifier that maximizes

-∇L (G) , F ∝ - N i=1 y i F (X i )L (y i G(X i )) , (2)
where L (z) is the derivative with respect to z and ∇L (G) is the gradient with respect to G. Substituting Eq. 1 into Eq. 2, we obtain the objective function

-α N i=1 x∈Xi y i k x f (x)L (y i G(X i )) .
Since f (x) is a binary classifier, i.e., f : R d → {-1, +1}, it is equivalent to train f by minimizing the following proxy loss, which is defined in terms of individual items:

N i=1 x∈Xi D(i)k x [f (x) = y i ] , (3)
where D(i) is the sample weight of the i th set,

D(i) = L (y i G(X i )) N i=1 L (y i G(X i )) . ( 4
)
At each iteration, we train an item classifier according to the weights D. In the SetBoost reweighting mechanism, D is updated in order to learn item classifiers that serve as a good discriminant on the sets instead of individual items. Therefore, the set classifier learning problem is reduced to a series of intermediate item classification problems. At iteration t, the weight α t of the new weak set classifier is found by minimizing the total loss N i=1 L (y i (G(X i ) + αF (X i ))) using numerical optimization. We use the LBFGS-B algorithm [START_REF] Byrd | A limited memory algorithm for bound constrained optimization[END_REF].

SetBoost can also be considered as a generalization of AdaBoost [START_REF] Freund | A Decision-Theoretic generalization of On-Line learning and an application to boosting[END_REF] since SetBoost simplifies to AdaBoost when each observed set comprises a single item.

Effective Utilization of Decision Trees

One suitable weak item classifier choice is decision trees. At every iteration of SetBoost, a decision tree minimizing Eq. 3 will be learned. A tree with M leaves will partition the feature space into partitions P 1 , ..., P M . We can assign weights α m to decision tree leaf nodes based on their discriminative power for set classification.

Let the H m (X) = x∈X,x∈Pm k x , which is the total prior vote weight of items that are grouped into the partition P m for a training example X. Once a decision tree is built, we choose leaf node weights by minimizing the total loss:

α = arg min α 1 ,...α M λα T α + N i=1 L y i G(X i ) + y i M m=1 α m H m (X i ) . (5)
We use LBFGS-B [START_REF] Byrd | A limited memory algorithm for bound constrained optimization[END_REF] to optimize over the α values. Optimizing the α values requires only a modest fraction of the time needed to build decision trees.

Stochastic Training

The training time can be an issue for datasets that contain high cardinality sets.

To address this, we propose a sampling-based implementation, summarized in Alg. 1. At each training iteration, a fixed number of sets is sampled. Training examples are subsampled with respect to the sample weight distribution D, rather than from a uniform distribution as in [START_REF] Friedman | Stochastic gradient boosting[END_REF] , in order to "catch" more

i∈I x∈X i D(i) [ft(x) = yi] (c) Solve for [α 1 t , ..., α M t ] via Eq. 5 (d) Let Ft(X) = M m=1 α m t H m t (X) (e) D(i) ← D(i) exp (-yiFt(Xi)) , i = 1...N (f) Normalize D to a probability distribution. 3. Obtain G(X) = T t=1 Ft(X)

Experiments

Experiments are conducted using two object detection benchmark datasets. The first is the PASCAL VOC 2007 dataset [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF], which contains 20 classes and 9963 images. We use the original train-test split (≈ %50 each). The second is the SUN dataset [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF], which contains 4367 training and 4317 test images and significantly more (107) classes. Most images in the VOC 2007 dataset contain at most five object classes, whereas many images in the SUN dataset contain around ten object classes.

In all experiments, the regularization parameter λ = 0.01 is used and each SetBoost strong classifier is trained with 100 decision tree weak classifiers. We report results with both the [26] and [27] versions of the detector of [START_REF] Felzenszwalb | Grishick: Object detection with discriminatively trained part based models[END_REF] as the baseline object detector. In our evaluation, we are most interested in the contextbased improvement obtained for a given set of baseline detections rather than the absolute detection accuracies. For this reason, we always compare different methods using the same input baseline detections. For the other methods in comparison, we use either previously published results or use publicly available implementations. To quantify performance, the VOC object localization criteria [START_REF] Everingham | The PASCAL Visual Object Classes Challenge[END_REF] are used. The effectiveness of a context model is evaluated according to the change in the Average Precision (AP) of the detectors before and after the application of that particular model.

Experiments on VOC 2007

For the VOC 2007 dataset, we use decision trees with (at most) 150 leaf nodes and the maximum set cardinality is 50. Object Context. We first evaluate the effect of each feature dimension in the object context model. Note that each one of the learned object context models contains a set of decision trees. Fig. 3a shows the average frequency of selected feature dimensions in the first 25 weak classifiers among all classes. The first 20 features represent the detected object class and detection score, as defined in Section 3. The next six dimensions encode relative spatial positions, and the final two dimensions encode relative scores of object detection pairs.

The two most frequently chosen feature dimensions are the relative detection scores. An important reason is that relative scores can be used for inter-class and intra-class suppression. For instance, we observe that the AP detection scores for cat, cow, dog and horse classes improve significantly when our context model is applied (see Table 3). Since these animals have a relatively similar body shape, object detectors for these classes tend to return false positive detections for instances of each other class. Fig. 3b shows two images where horse and cat detectors give false positives on dogs. Based on the dog detection, the system suppresses false horse and cat detections in these images.

In Fig. 3a, we also observe that spatial relationship features (relative y, ..., overlap) are also frequently used. Therefore, the context model is not just an object class co-occurrence model; instead, a structured spatial layout of object classes is learned. For example, in Fig. 2 we observe that spatial relationships between "person-horse" and "person-bicycle" classes are learned.

We also note in Fig. 3a that the detection score features for the person class are frequently used in the object context models. This is probably related to the fact that the person class is the most dominant class in the VOC 2007 dataset. Among true positive detections on the training set, 76% of all intra-class pairs are person-person, and 54% of all inter-class pairs involve person objects.

SetBoost vs PMK vs Bag-of-Words. Next, we evaluate SetBoost as opposed to SVM with Vocabulary-Guided Pyramid Match Kernel (PMK) [START_REF] Grauman | Approximate correspondences in high dimensions[END_REF], which is an alternative set classifier, and a Bag-of-Words (BoW) approach. We use PMK with 8 levels and branching factor set to 11. For BoW, we use k-means to construct a vocabulary of size 1000 per class and use SVMs with intersection kernel. The results are given in Table 2. We observe that the PMK and BoW also provide improvements in some of the classes, which assures that the proposed set-based context representation is effective. On the other hand, the performance of SetBoost classifier is clearly better for nearly all classes.

Scene Context. In learning the scene context model, decision trees with 5 leaf nodes are built with 50 weak classifiers. The scene-context has a vector representation, which reduces the required model complexity significantly. To avoid overfitting, we project GIST descriptors to 100 dimensions via PCA.

In the VOC 2007 dataset, there are significant scene changes and there is no dominantly occurring scene. As a result, evaluating scene context on its own yields poor performance, as one would expect: the change in the average AP score is -3.40 over the baseline. On the other hand, we see that scene context is complementary to object context and best performance is attained when the scene context and object context are used together. The average AP score increases by 3.65 when the combined model is used (see Table 3), compared to the 3.14 increase with object context model alone (see Table 2).

Comparison with Other Context Models. We first compare our approach against two state-of-the-art object context models [START_REF] Desai | Discriminative models for multi-class object layout[END_REF] and [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF]. For this purpose, we run all approaches on the outputs of the baseline detector [26].

Table 3 shows the baseline AP scores and the difference in AP scores (AP Diff = AP After -AP Before ) after applying the context models. The best improvement for each row of the table is shown in bold. As can be seen in Table 3, our object context model outperforms the state-of-the-art methods in 14 out of 20 classes, and attains best performance on average.

We also compare against [START_REF] Li | Extracting adaptive contextual cues from unlabeled regions[END_REF], which combines a context model for unlabelled regions (CMO) with the object context model (OOI) of [START_REF] Felzenszwalb | Grishick: Object detection with discriminatively trained part based models[END_REF]. We introduce CMO Example outputs of our system are shown in Fig. 4. Images that include detections before and after contextual set-based rescoring shows how the irrelevant objects are eliminated and detection performance is improved.

Experiments with SUN Dataset

Since the number of objects and the amount of noise increases in SUN dataset, we increase the model complexity by doubling the decision tree size parameter (i.e., 300) and the maximum set cardinality (i.e., 100).

We compare with [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF], which is the state-of-the-art method for this dataset. Table 5.2 shows the AP and AP Diff scores averaged among 107 classes in the SUN dataset for the baseline detectors, [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF] and our context model. When we apply our model, we get AP Diff = 1.68 point improvement, whereas [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF] results in AP Diff = 1.30.

In the SUN dataset, the improvement obtained by applying either our context model or [START_REF] Choi | Exploiting hierarchical context on a large database of object categories[END_REF] is not as high as the improvement for the VOC 2007 dataset. We observe that baseline object detectors work poorly on the SUN dataset; 78% of them (83 out of 107) have an AP score less than 10 and 92% of them have an AP score less than 20. In contrast, on the VOC 2007 dataset, only 40% of the detectors have an AP score less than 20. Thus, although the SUN dataset has richer context in terms of contextual relations, extracting such contextual information is difficult because most of the baseline object detectors perform poorly. One might conclude that context models require sufficiently accurate baseline object detectors in order to gain significant improvement in contextbase rescoring.

Conclusion

We have shown how object-object and object-scene context can be formulated in terms of sets. Our set-based model can learn the contextual relationships of objects without predefining the relationship types. The proposed SetBoost algorithm enables efficient learning of set classifiers. One advantage of SetBoost is its ability to use existing item classifiers (e.g., vector classifiers) to build set classifiers, without requiring intermediate representations. We also formulated a method for tuning decision trees for set-based classification within SetBoost. The effectiveness of our approach to contextual object recognition has been demonstrated on benchmark datasets.

In future work, we plan to address the handling of sets that contain items of varying dimensionalities. Another direction for future work is to handle multiclass classifiers directly.

  encoded score [0, ..., 0, ds, 0, .., 0] distance (dy -d ref y ) 2 + (dx -d ref x ) 2 /d ref h relative y (dy -d ref y )/d ref h overlap d B ∩ d ref B / d B ∪ d ref B relative y (abs) |dy -d ref y |/d ref h score ratio ds/d ref s relative height, width d h /d ref h , dw/d ref w score difference ds -d ref s More formally, given the set of object detections in an image, each detected object d has a score d s normalized to the range [ , 1] where > 0 ( = 0.01 in our experiments), a class d c ∈ {1, 2, ..., C}, where C is the number of classes, and a bounding box d B = [d x , d y , d h , d w ] (x, y location, height and width). We consider each detected object as the reference object d ref and update its detection score according to its contextual relationships with the other detections in the image. Context for the reference object is represented as a set X. Each item x ∈ X is the feature vector for each other detection d = d ref .

Fig. 2 .

 2 Fig. 2. Example learned relationships in the VOC 2007 dataset. White bounding boxes show the reference object with its final score. Red (blue) bounding boxes represent positively (negatively) voting detections. The images to the left show all objects with their contextual votes, where the intensity of colors is scaled with respect to magnitude of the vote. Many noisy/irrelevant detections have approximately zero vote. The images to the right show a reference detection and the detection with the highest contextual influence.

Algorithm 1

 1 Stochastic SetBoost with decision trees. T is the number of weak classifiers used in constructing G(X), N is the total number of examples in the training set, I is the set of sampled example indices at an iteration, where |I| ≤ N . 1. Initialize D(i) = 1/N, i = 1...N and G(X) = 0. 2. For t = 1 to T (a) Sample subset of indices I with respect to D. (b) Train ft(x) to min.

Fig. 3 .

 3 Fig. 3. (a) Average frequency of each feature dimension chosen in the decision tree nodes for all classes in the VOC 2007 dataset. (b) Examples where horse and cat detectors give false positives on dogs in the VOC 2007 dataset.

Fig. 4 .

 4 Fig. 4. Images before/after contextual rescoring. The eight top-scoring detections before and after applying the object context model are on the left and on the right respectively. In a livingroom image (left) the context model decreases the scores of false detections, such as a train and an overly large sofa, and it increases the scores of detected objects that are more likely to be correct. In a diningroom image (right) the model decreases the scores of a false person detection and a false boat detection, while it increases the scores of chair detections around the table.

  difficult examples at each iteration. We set the sample size |I| to the average number of positive training examples among classes in a dataset. As shown in Alg. 1, D(i) is still utilized after the subsampling step. Another potential problem is training with large class imbalances. The number of negative training examples is often much larger than the number of positive training examples. To address this problem, we sample an equal number of positive and negative examples at each boosting iteration. As a result, we can utilize a large set of negative examples during training.

Table 2 .

 2 Comparison of SetBoost algorithm with PMK[START_REF] Grauman | Approximate correspondences in high dimensions[END_REF]. The baseline detector used is[26]. The column BL shows baseline AP scores and subsequent columns show the change in AP scores after applying different classifiers using the proposed object context representation.

		BL	PMK	BoW	Our		BL	PMK	BoW	Our		BL	PMK	BoW	Our
	aero	28.6	1.4	0.4	5.2	cat	16.5	0.0	-2.5	4.7	person	35.8	-0.9	-2.8	3.5
	bike	55.1	-0.2	-2.4	2.3	chair	16.5	-7.2	-0.6	2.4	plant	9.0	2.7	3.8	5.2
	bird	0.6	1.4	1.4	2.4	cow	16.8	0.2	1.0	2.0	sheep	17.4	-0.7	1.4	1.9
	boat	14.5	0.4	-0.2	0.9	dtable	24.6	0.3	3.0	0.9	sofa	22.7	1.0	-2.7	3.7
	bottle	26.5	-3.8	-0.6	3.4	dog	5.0	7.8	0.5	5.3	train	34.0	0.6	-3.0	4.3
	bus	39.7	-0.2	-3.9	0.2	horse	45.2	0.0	0.7	5.1	tv	38.3	-13.9	-13.3	1.5
	car	50.1	-1.9	-3.6	3.2	mbike	38.3	-1.8	-3.0	4.5	AVG	26.8	-0.7	-1.3	3.1

Table 3 .

 3 Comparison of context models on VOC 2007 dataset using the baseline detections of [26]. Our method is using SetBoost with combined object and scene context model.

		BL	[2]	[3]	Our		BL	[2]	[3]	Our		BL	[2]	[3]	Our
	aero	28.6	1.7	2.4	5.4	cat	16.5	.5	3.9	5.0	person	35.8	-2.8	0	3.5
	bike	55.1	0	-4.2	2.7	chair	16.5	-2.8	1.6	0.0	plant	9.0	-1.1	4.7	4.2
	bird	0.6	.1	2.3	9.2	cow	16.8	1.2	0.9	0.7	sheep	17.4	-2.3	3.8	3.1
	boat	14.5	1.4	0.8	0.8	dtable	24.6	-.7	2.3	1.4	sofa	22.7	-0.7	2.8	4.9
	bottle	26.5	0	-1.1	3.2	dog	5.0	.2	6.9	7.9	train	34.0	0.5	4.7	4.9
	bus	39.7	-3.5	-0.2	1.9	horse	45.2	0.5	5.6	5.9	tv	38.3	0	-0.1	0.3
	car	50.1	1.3	-0.4	3.4	mbike	38.3	1.1	2.2	4.6	AVG	26.8	-0.3	1.9	3.6

Table 4 .

 4 Comparison of context model "20CMO+20OOI" of[START_REF] Li | Extracting adaptive contextual cues from unlabeled regions[END_REF] with our approach on VOC 2007 using the baseline detections of[27].scores into our model by simply concatenating per-class maximum CMO score to the scene context representation. Both models are applied to the output of the baseline detector[27]. As shown in Table4, performance of the two approaches are comparable. Our method performs better in 10 out of 20 classes and[START_REF] Li | Extracting adaptive contextual cues from unlabeled regions[END_REF] performs 0.2 points better on average.

		BL	[6] CMO+Our		BL	[6] CMO+Our		BL	[6] CMO+Our
	aero	28.9	2.6	2.9	cat	19.3	5.5	5.9	person	41.9	1.7	1.8
	bike	59.5	2.3	0.4	chair	22.4	1.3	2.7	plant	12.2	2.0	1.1
	bird	10.0	2.4	2.3	cow	25.2	2.0	1.7	sheep	17.9	1.7	2.2
	boat	15.2	2.9	4.7	dtable	23.3	7.4	3.6	sofa	33.6	4.9	3.5
	bottle	25.5	2.2	2.6	dog	11.1	2.6	4.5	train	45.1	4.0	3.9
	bus	49.6	1.9	2.0	horse	56.8	3.7	3.1	tv	41.6	2.7	1.5
	car	57.9	1.9	2.1	mbike	48.8	2.3	2.0	AVG	32.3	2.9	2.7

Table 5 .

 5 Comparison of our contextual object detection model versus the state-of-theart on the SUN dataset.

		Baseline	[3]	Our
	Average AP	7.06	8.37 8.75
	AP Diff in Average AP	-	1.30 1.68

Acknowledgments. This work was supported in part through US NSF grants 0855065, 0910908, and 1029430.