Olivier Duchenne

Francis Bach

In-So Kweon

Jean Ponce

A Tensor-Based Algorithm for High-Order Graph Matching

Keywords: Hypergraphs, Graph Matching, Image Feature Matching

This paper addresses the problem of establishing correspondences between two sets of visual features using higher-order constraints instead of the unary or pairwise ones used in classical methods. Concretely, the corresponding hypergraph matching problem is formulated as the maximization of a multilinear objective function over all permutations of the features. This function is defined by a tensor representing the affinity between feature tuples. It is maximized using a generalization of spectral techniques where a relaxed problem is first solved by a multi-dimensional power method, and the solution is then projected onto the closest assignment matrix. The proposed approach has been implemented, and it is compared to state-of-the-art algorithms on both synthetic and real data.

INTRODUCTION

Establishing correspondences between two sets of visual features is a key problem in computer vision tasks as diverse as feature tracking [START_REF] Birchfield | KLT: An implementation of the Kanade-Lucas-Tomasi feature tracker[END_REF], image classification [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] or retrieval [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF], object detection [START_REF] Berg | Shape matching and object recognition using low distortion correspondence[END_REF], shape matching [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF], [START_REF] Zheng | Robust point matching for nonrigid shapes by preserving local neighborhood structures[END_REF], or widebaseline stereo fusion [START_REF] Pritchett | Wide baseline stereo matching[END_REF]. Different image cues may lead to very different matching strategies. At one end of the spectrum, geometric matching techniques such as RANSAC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF], interpretation trees [START_REF] Grimson | Localizing overlapping parts by searching the interpretation tree[END_REF], or alignment [START_REF] Huttenlocher | Object recognition using alignment[END_REF] can be used to efficiently explore consistent correspondence hypotheses when the mapping between image features is assumed to have some parametric form (e.g., a planar affine transformation), or obey some parametric constraints (e.g., epipolar ones). At the other end of the spectrum, visual appearance alone can be used to find matching features when such an assumption does not hold: For example, bag-of-features methods that discard all spatial information to build some invariance to intra-class variations and viewpoint changes have been applied quite successfully in image classification tasks [START_REF] Zhang | SVM-KNN: Discriminative nearest neighbor classification for visual category recognition[END_REF], [START_REF] Zhang | Local features and kernels for classifcation of texture and object categories: An in-depth study[END_REF]. Modern methods for image matching now tend to mix both geometric and appearance cues to guide the search for correspondences (see, for example, [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF], [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]).

Many matching algorithms proposed in the 80s and 90s have an iterative form but are not explicitly aimed as optimizing a well-defined objective function (this is the case for RANSAC and alignment methods for example). The situation has changed in the past few years, with the advent of combinatorial or mixed continuous/combinatorial optimization approaches to feature matching (see, for example [START_REF] Berg | Shape matching and object recognition using low distortion correspondence[END_REF], [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF], [START_REF] Maciel | A global solution to sparse correspondence problems[END_REF], [START_REF] Oliveira | Optimal multi-frame correspondence with assignment tensors[END_REF], [START_REF] Zheng | Robust point matching for nonrigid shapes by preserving local neighborhood structures[END_REF]) 1 . This paper builds on this work in a framework that can accommodate both (mostly local) geometric invariants and image descriptors. Concretely, the search for correspondences is cast as a hypergraph matching problem using higher-order constraints instead of the unary or pairwise ones used by previous methods: First-order methods based (for example) on local image descriptions are susceptible to image ambiguities due to repeated patterns, textures or non-discriminative local appearance for example. Geometric consistency is normally enforced using pairwise relationships between image features. In contrast, we propose in this paper to use higher-order (mostly third-order) constraints to enforce feature matching consistency (Figure 2). This work generalizes the spectral matching method of [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] to higher-order potentials: The corresponding hypergraph matching problem is formulated as the maximization of a multilinear objective function over all permutations of the features. This function is defined by a tensor representing the affinity between feature tuples. It is maximized by first using a multi-dimensional power method to solve a relaxed version of the problem, whose solution is then projected onto the closest assignment matrix.

The three main contributions of this article are (1) the application of the tensor power iteration method to the highorder matching task, combined with a relaxation based on constraints on the row norms of assignment matrices, which is tighter than previous methods (Section 3), (2) an ℓ 1norm instead of the classical ℓ 2 -norm relaxation, that provides solutions that are more interpretable but still allows an efficient power iteration algorithm (Section 4), and (3) the design of appropriate similarity measures that can be chosen either to improve the invariance of matching, or to improve the expressivity of the model (Section 5). The proposed approach has been implemented, and it is compared to state-of-the-art algorithms on both synthetic and real data. As shown by our experiments (Section 7), our implementation is, overall, as fast as these methods in spite of the higher complexity of the underlying model, with better accuracy on standard databases.

A preliminary version of this work appears in [START_REF] Duchenne | A tensor-based algorithm for high-order graph matching[END_REF]. The source code of our software is available on line at http: //www.di.ens.fr/ ∼ duchenne.

GRAPH MATCHING FOR COMPUTER VISION

Previous work

As noted earlier, finding correspondences between visual features (such as interest points, edges, or even raw pixels) is a key problem in many computer vision tasks. The simplest approach to this problem is to define some measure of similarity between two features (e.g., the Euclidean distance between SIFT descriptors of small image patches [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]), and match each feature in the first image to its nearest neighbor in the second one. This naive approach will fail in the presence of ambiguities such as repeated patterns, textures or nondiscriminative local appearance. To handle this difficulty, some methods try to enforce geometric consistency between pairs of feature correspondences. The basic idea is that if the points p 1 1 , and the one between p 2 and p ′ 2 should be similar. Several pairwise geometric relations have been used. Leordanu and Hebert [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] use only the distance between two points, leading to a matching criterion which is invariant to rotation. In their objective function, Berg et al. [START_REF] Berg | Shape matching and object recognition using low distortion correspondence[END_REF] use a combination of potentials based on distances (rotation-invariant) and angles (scale-invariant), to find a trade-off between rotation and scale invariance. Some other methods (e.g., [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF], [START_REF] Zheng | Robust point matching for nonrigid shapes by preserving local neighborhood structures[END_REF]) use proximity, only assuming that two adjacent points should be matched in the other image to two points which are also close to each other. One difficulty here is to define an appropriate notion of neighborhood.

Recently, the computer vision community has put much effort in increasing the order of complexity of the models used: For example, Kohli et al. [START_REF] Kohli | p 3 and beyond: Solving energies with higher order cliques[END_REF] introduce a high-order clique potential for segmentation, but the type of energy is limited to specific types of functions, using the alpha-expansion framework. Zass and Sashua [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF] formulate the search for higher-order feature correspondences as a hypergraph matching problem. We will use the same formulation but a different optimization setup. In addition, unlike these authors, we will refrain from using independence assumptions (that may or may not be justified depending on the situation) to factor our model into first-order interactions. As will be shown in the comparative experiments of Section 7, explicitly maintaining higher-order interactions in the optimization process leads to superior performance.

First, in Section 2.2 and 2.3, we discuss about classical graph matching. Then, in Section 3, we introduce our method.

Problem statement

We consider two images, and assume that we have extracted N 1 points from image 1, and N 2 from image 2. We do not assume that N 1 = N 2 , i.e., there may be different numbers of points in the two images to be matched. Moreover, instead of points, we could use any other type of visual features such as edges, raw pixels, etc. Throughout this paper, for s = 1, 2, all indices i s , j s , k s will be assumed to vary from 1 to N s . We will also note i = (i 1 , i 2 ), j = (j 1 , j 2 ), k = (k 1 , k 2 ) pairs of potentially matched points.

Let P s n be the n th point of image s. The problem of matching points from image 1 to points from image 2 is equivalent to looking for an N 1 × N 2 assignment matrix X such that X i1,i2 a.k.a. X i is equal to 1 when P 1 i1 is matched to P2 i2 , and to 0 otherwise. In this paper, we assume that a point in the first image is matched to exactly one point in the second image, but that one point in the second image may be matched to an arbitrary number of points in the first image, i.e., we assume that the sums of each row of X is equal to one, but put no constraints on the column sums 2 . Thus, we consider the set X of assignment matrices:

X = {X ∈ {0, 1} N1×N2 , ∀i 1 , i2 X i1,i2 = 1}.
Note that our definition is not symmetric (i.e., if we switch the two images, we obtain different correspondences). It can be made symmetric by considering the two possible matchings (image 1 to image 2 and image 2 to image 1) and combining them (in a mostly application-dependent way), e.g., by taking the union or intersection of matchings.

In [START_REF] Berg | Shape matching and object recognition using low distortion correspondence[END_REF], [START_REF] Cour | Balanced graph matching[END_REF], [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF], the matching problem is formulated as the maximization of the following score over X :

score(X) = i1,i2,j1,j2 H i1,i2,j1,j2 X i1,i2 X j1,j2 ,
where H i1,i2,j1,j2 (which is equal to H i,j with our notations for pairs) is a binary potential corresponding to the pairs of feature nodes (P i1 , P j1 ) of image 1, and (P i2 , P j2 ) of image 2. H is a positive similarity measure, such that high values of H correspond to similar pairs. As described in Section 5, in this paper, we compute for each pair of nodes from the same image a feature vector f , and we compute H as follow:

∀i 1 , i 2 , j 1 , j 2 , H i1,i2,j1,j2 = exp(-γ f i1,j1 -f i2,j2
2 ).

Many other similarity measures are of course possible.

This graph matching problem is actually an integer quadratic programming problem, with no known polynomialtime algorithm for solving it. Approximate methods may be divided into two groups. The first one is composed of methods that use spectral representations of adjacency matrices (e.g., [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF], [START_REF] Umeyama | An eigendecomposition approach to weighted graph matching problems[END_REF]). The second group is composed of algorithms that work directly with the graph adjacency matrices, and typically involve a relaxation of the discrete optimization problem (e.g., [START_REF] Almohamad | A linear programming approach for the weighted graph matching problem[END_REF], [START_REF] Zaslavskiy | A path following algorithm for the graph matching problem[END_REF]). In this paper, we focus on improvements of the second group of methods.

In [START_REF] Cour | Balanced graph matching[END_REF], [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF], the set of binary matrices over which the optimization is performed is thus relaxed to the set of real matrices with Frobenius norm equal to √ N 1 , leading to the simpler problem:

max X F = √ N1 i1,i2,j1,j2 H i1,i2,j1,j2 X i1,i2 X j1,j2 . (1)
Note that all the matrices in X have only N 1 non-zeros coefficients, which are equal to one, therefore they indeed all have their Frobenius norm equal to √ N 1 . In turn, Eq. (1) can be rewritten as max

X 2 = √ N1
XT H X, where X denotes the vector in R N1N2 obtained by concatenating the columns of X and, likewise, H the N 1 N 2 ×N 1 N 2 symmetric matrix obtained by unfolding the tensor H. This is a classical Rayleigh quotient problem, whose solution X * is equal to √ N 1 times the eigenvector associated with the largest eigenvalue (which we refer to as the main eigenvector V ) of the matrix H [START_REF] Golub | Matrix computations[END_REF], and can be computed efficiently by the power iteration method described in the next section.

An important constraint that H must satisfy is that it is pointwise non-negative. This is the main hypothesis of the Perron-Frobenius theorem [START_REF] Frobenius | Ueber matrizen aus nicht negativen elementen[END_REF] that ensures that X * only has non-negative coefficients, which simplifies the interpretation of the result (see [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF]).

In order to obtain an assignment matrix in X , i.e., a matrix with elements in {0, 1} and proper row sums, the authors of [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] discretize the eigenvector X * using a greedy algorithm (see [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] for more details). One could also use the Hungarian algorithm with cost matrix X * to obtain a permutation matrix.

Power iterations for eigenvalue problems

The power iteration method is a very simple algorithm for computing the main eigenvector of a matrix, which is needed for matching.

Input: matrix H Output: V main eigenvector of H 1 initialize V randomly ; 2 repeat 3 V ← HV ; 4 V ← 1 V 2 V ; 5 until convergence;
Algorithm 1: Power iterations for eigenvalue problems.

This algorithm is guaranteed to converge geometrically to the main eigenvector of the input matrix [START_REF] Golub | Matrix computations[END_REF]. As explained in Section 6, in our situation, H is very sparse and we want to take advantage of this. Indeed, each step of the power iteration algorithm requires only O(m) operations, where m is the number of non-zero elements of H. Also, typically, in our situation, the algorithm converges in a few dozen steps.

Thanks to this algorithm description, it becomes easy to see one reason why the output V will have only non-negative values as described in the Perron-Frobenius theorem [START_REF] Frobenius | Ueber matrizen aus nicht negativen elementen[END_REF]. Let us assume we initialize V with only non-negative values (since the algorithm converges to a global optimum, this will not change the output of the algorithm). In our case H is also point-wise non-negative. Therefore at each iteration, each coordinate of V will be replaced by a sum of products of nonnegative values, which is also non-negative. So this property remains true until convergence. We will see that this nice property will be conserved in our higher-order algorithm.

TENSOR FORMULATION OF HYPERGRAPH

MATCHING

We propose to use tensors to solve the high-order feature matching problem. Indeed, using tensors is quite natural to generalize the spectral matching [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] introduced in the previous section which deal with a matrix. Previous work except [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF] only uses one-to-one and pair-to-pair comparisons for matching. In this paper, we want to compare tuples of points. We denote by d the number of points per tuple, and add higher-order terms to the score function defined in Eq. (1). For simplicity, we will focus from now on third-order interactions (d = 3). Generalizations to higher-order potentials are (in theory at least) straightforward. However, in practice, it could lead to an exponential growth of the computational complexity.

We define a new high-order score:

score(X) = i1,i2,j1,j2,k1,k2 H i1,i2,j1,j2,k1,k2 X i1,i2 X j1,j2 X k1,k2 , (2)
where we assume that H is a 6-dimensional super-symmetric tensor, i.e., invariant under permutations of indices in

{i 1 , j 1 , k 1 } or {i 2 , j 2 , k 2 }.
Here, the product X i1,i2 X j1,j2 X k1,k2 will be equal to 1 if and only if the points {i 1 , j 1 , k 1 } are respectively matched to the points {i 2 , j 2 , k 2 }. In this case, it will add H i1,i2,j1,j2,k1,k2 to the total score function and 0 otherwise.

As described in Section 5, H represents a similarity measure, which will be high if the set of features {i 1 , j 1 , k 1 } is similar to the set {i 2 , j 2 , k 2 }. In our experiments, we compute for each triplet of nodes in the same image a feature vector f , and we compute H as follow:

∀i, j, k, H i1,i2,j1,j2,k1,k2 = exp(-γ f i1,j1,k1 -f i2,j2,k2
2 ).

More details are provided in latter sections.

As explained in the next section, we can rewrite the score compactly using tensor notation as:

score( X) = H ⊗ 3 X ⊗ 2 X ⊗ 1 X, (3)
with the same notation as in the matrix case: X = vec(X) and H is rewritten as a tensor H of size

(N 1 N 2 ) d .
This score can be interpreted as a hypergraph matching score. In a hypergraph, an edge can link more than two vertices together (Figure 1). In this framework, any element of H is a matching score between two hyper-edges.

In Section 5, we will explain how higher-orders potentials can be used to have more invariant or more expressive features.

A short introduction to tensors

A tensor is the n-dimensional generalization of a matrix: a matrix can be represented as 2-D rectangular table, and tensors can be viewed as n-dimensional hyper-rectangular tables. Each of the elements of such a tensor is indexed by n numbers:

H = {H i1,i2,...,in }.
A tensor and a vector can be multiplied in different ways. In this article, we use the following notation:

B = A ⊗ k V, B i1,...,i k-1 ,i k+1 ,...,in = i k A i1,...,i k ,...,in V i k ,
where V is a n-dimensional vector and A a n-dimensional tensor. Like a matrix multiplied by a vector produces a vector, an n-dimensional tensor multiplied by a vector is (n -1)dimensional. Also, like the matrix-vector multiplication that can be done in two ways (on the left or on the right), the tensor-vector multiplication can be done in n different ways. The index k in the notation ⊗ k indicates that we multiply on the k th dimension.

In Eq. ( 3), we use the following calculus:

score( X) = H ⊗ 1 X ⊗ 2 X ⊗ 3 X = ((( H ⊗ 1 X) ⊗ 2 X) ⊗ 3 X) = ((( k H i,j,k X k ) i,j ⊗ 2 X) ⊗ 3 X) = i,j,k H i,j,k X i X j X k .
So the two expressions of the score in Eq. ( 2) and (3) are equivalent.

Tensor power iterations

To find the optimum of the high-order score of Eq. (2), we use a generalization of the previously mentioned power iterations, as proposed in [START_REF] Lathauwer | On the best rank-1 and rank-(r1,r2,. . .,rn) approximation of higher-order tensors[END_REF]. The algorithm presented below extends Algorithm 1.

This method is not guaranteed to reach a global optimum. However, it converges to a stationary point for tensors that lead to convex functions of X [START_REF] Regalia | The higher-order power method revisited: convergence proofs and effective initialization[END_REF]. In our experiments, it converges almost always to a very satisfactory solution. Also, the authors of [START_REF] Regalia | The higher-order power method revisited: convergence proofs and effective initialization[END_REF] propose a smart way to initialize it, to lead to a quantifiable proximity to the optimal solution.

We can see that, as in the matrix case, if we initialize V with only non-negative values, the resulting vector will have only non-negative values. This is required to have a meaningful result. Indeed, if negative values of X in the score in Eq. (2) were allowed, some product of negative values could have a positive value. Therefore even coordinates of X with a

Input: supersymmetric tensor H Output: V main eigenvector of H 1 initialize V randomly ; 2 repeat 3 V ← H ⊗ 1 V ⊗ 2 V ; 4 ( i.e. ∀i, V i ← j,k H i,j,k V j V k ) 5 V ← 1 V 2 V ; 6 until convergence;
Algorithm 2: Supersymmetric tensor power iteration (third order). low value could increase the final score, preventing us from interpreting the coordinates of H as a similarity potential activated only when all corresponding pairs are matched.

Tensor power iterations for unit-norm rows

In our context, we want to constrain the norm of each row of X to 1, which is a tighter relaxation of X than matrices of fixed Frobenius norm. In addition, this corresponds to a many-to-one matching setting: all nodes of the first images are matched to exactly one node in the second image, but several nodes in the first images can be matched to the same one in the second image. We denote by C 2 the set of matrices such that all theirs rows have unit Euclidean norm.

We can extend the previous algorithm to this new set of matrices (Algorithm 3). ,:) 2 V (i 1 , :) ; 6 until convergence; Algorithm 3: Supersymmetric tensor power iteration (third order) with unit norm constraints. V (i, :) denotes the vector

Input: supersymmetric tensor H Output: V = [v 1,1 , . . . , v N1,N2 ] T stationary point 1 initialize V randomly ; 2 repeat 3 V ← H ⊗ 1 V ⊗ 2 V ; 4 ( i.e. ∀i, V i ← j,k H i,j,k V j V k ) 5 ∀i 1 , V (i 1 , :) ← 1 V (i1
(V i,1 , V i,2 , . . . , V i,N2 ) T .
As shown in the appendix, we have extended the proof of [START_REF] Regalia | The higher-order power method revisited: convergence proofs and effective initialization[END_REF] to handle those new constraints. In particular, we have shown that this algorithm has the same nice properties of the previous one: if the score is a convex function of X, then Algorithm 3 converges to a stationary point V . Note that we can always make the score convex by adding to it a multiple of the function X⊤ X. Since the X vectors in C 2 all have the same norm, this change the value of the score function only by a constant and thus does not change its optima on C 2 (the set of matrices whose Euclidean norms of each of the N 1 rows are equal to one).

Finally, we want to obtain correspondences and need to compute a binary matrix X from V . We obtain a natural projection step here on the set X : For each row, the coordinate with maximum value in V is set to 1 in X, and the other coordinates of X are set to 0.

Merging potentials of different orders

It could be interesting to include in the matching process, at the same time, information about different potential orders (e.g., considering at the same time pair similarities and triplet similarities). To do this, a first solution is to include the low-order information into the tensor of the highest-order potential H. Cour and Shi [START_REF] Cour | Balanced graph matching[END_REF] present a method to do this, combining second and first-order potential. The generalization to our setting is straightforward. However, in our power iteration framework, it is equivalent to use the simple following algorithm (which could also be extended to constrain rows to have unit norms):

Input: several supersymmetric tensors Hd of order d Output: V main eigenvector of H 1 initialize V randomly ; 2 repeat 3 V ← H4 ⊗ 1 V ⊗ 2 V ⊗ 3 V + 4 H3 ⊗ 1 V ⊗ 2 V + H2 ⊗ 1 V + H1 ; 5 ( i.e. ∀i, V i ← j,k,l H 4 i,j,k,l V j V k V l + j,k H 3 i,j,k V j V k + j H 2 i,j V j + H 1 i ) 6 V ← 1 V 2 V ; 7 until convergence;
Algorithm 4: Multiple order supersymmetric tensor power iteration (fourth order).

ℓ 1 -NORM CONSTRAINT FOR ROWS

One of the main problems of spectral relaxations is that the solution is often nearly uniform, which means that it is hard to extract from it an assignment matrix with values in {0, 1}. This is due in part to the relaxation of the set X of assignment matrices to matrices in C 2 with unit ℓ 2 -norm rows, which does not lead to sparsity. In fact, we can also relax the set X to the matrices in C 1 with rows having unit ℓ 1 -norm (i.e., sum of absolute values). As shown in Figure 3, this leads to results that are more easily interpretable.

In the context of second-order interactions, solving the ℓ 1norm problem cannot be done by power iterations. However, in our higher-order context, this can be done seamlessly. Indeed, solving the following problem on C 1 :

max X∈C1,X 0 i,j H i,j X i X j is equivalent to solving (on C 2 ): max Y ∈C2 i,j H i,j Y 2 i Y 2 j
with the change of variable: Y 2 i = X i . The order of this new problem is 4 when using the tensor power iteration algorithm, but the complexity is still as low as second-order problem (see Algorithm 5). Using this algorithm we usually obtain in practice an almost completely binary solution, as shown on a particular example in Figure 3. This method is easily extended to solve any high-order matching problem. Fig. 3. We run the spectral algorithm to match a random point cloud to a randomly perturbated copy of itself. We show here the resulting assignment matrices by using ℓ 2 or ℓ 1 -norm constraints (respectively Algorithm 1 and 5). The indexing of the points is made such that for all i, the point i of the first cloud corresponds to the point i of the second cloud. So the perfect assignment matrix should be the identity matrix. The horizontal axes correspond to the coordinates of the assignment matrix and the vertical one to its values. Top: Values of the assignment matrix when the ℓ 2 -norm is used. They are hard to project to a matrix in X , i.e., with values in {0, 1}. Bottom: When using the ℓ 1norm, we obtain directly a very clear assignment matrix with minor adjustments. Indeed, its values are nearly boolean.

Input: matrix H Output: V stationary point 1 initialize V randomly ; 2 repeat 3 V ← ( H(V • V )) • V ; 4 ( i.e. ∀i, V i ← V i j H i,j V 2 j ) 5 ∀i 1 , V (i 1 , :) ← 1 V (i1,:
) 2 V (i 1 , :) ; 6 until convergence; Algorithm 5: Tensor power iteration for the ℓ 1 -norm relaxation. Here, • represents the Hadamard product (or pointwise product). V (i, :) denotes the vector

(V i,1 , V i,2 , . . . , V i,N2 ) T .

BUILDING TENSORS FOR COMPUTER VISION

We can use higher-order potentials to increase either the geometric invariance of image features, or the expressivity of the models (see Figure 4). We describe here a few possible potentials. They are all based on computing a Gaussian kernel between appropriate invariant features. Clearly, many other potentials are possible.

In this section we will only consider third-order potentials. As illustrated by Figure 2, classical methods try to remove ambiguities by looking for matches that preserve some properties of point pairs. Here, we will try to preserve properties of point triplets. In particular, in most of the cases, we will use the properties of the triangle formed by three points. Basically, if the points (P 1 1 , P 1 2 , P 1 3 ) are matched to the points (P 2 1 , P 2 2 , P 2 3 ), the corresponding triangles should be similar. In [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF], rotation and translation-invariant potentials based on edge lengths and angles are used since it is impossible to build invariants to larger classes of transformations from feature pairs alone. Here, we propose using potentials based on triplets of points, which can be made invariant to richer classes of transformations, including (planar) similarities, affine transformations, and projective ones.

Similarity-invariant potentials

The angles of a triangle are invariant under similarities. Thus we can describe each triangle by its three angles (Figure 2). However, in our implementation, we rather use the sines of the angles to speed-up the computation.

Affine-invariant potentials

When the camera is moving, in the general case, the transformation of the image is perspective. However, this transformation can also be affine when the seen object is planar or when looking locally at the image. Therefore affine invariance can be a good approximation of perspective invariance.

Concretely, we normalize each triangle into an equilateral one, and then compare the intensity patterns of normalized triangles by normalized cross correlation. This description of the triangle is of course invariant under affine transformation.

Projective-invariant potentials

Inspired by [START_REF] Leordeanu | Beyond local appearance: Category recognition from pairwise interactions of simple features[END_REF], we can also develop higher-order potentials invariant to planar projective transforms with no parametric form when the scene shape is unknown. If we sample only feature points on the contours in the image, we can use the edge direction as an additional feature, and focus on properties of three points and three directions that are conserved under projective transforms. The main property conserved by a projective transform is the cross-ratio. So if we suppose that the object surface in the triangle we are looking at is flat, we can build three lines with four points on each. We compute the descriptor of the three points P 1 , P 2 , P 3 shown in Figure 5. We also show the three vectors N 1 , N 2 , N 3 which are orthogonal to the image gradient at each point. We draw a line from the point P 1 in the direction of vector N 1 which intersects the other lines (P 2 , N 2 ), (P 3 , N 3 ), (P 2 , P 3 ) in the points z 2 , z 3 , z 4 . And we add z 1 = P 1 . If the z i are written with complex numbers, their cross ratio is:

(z 1 , z 2 ; z 3 , z 4 ) = (z 1 -z 3 )(z 2 -z 4 ) (z 2 -z 3 )(z 1 -z 4 ) ,
and this formula is computed for each of the three points. We will use the three cross-ratios defined by those points to make a perspective-invariant descriptor.

More expressive potentials

Most previous approaches focus on using rather simple geometric relationships between points. Typically the descriptor of their pairwise relationship is a scalar or a low-dimensional vector. As a consequence, such descriptors have low discriminative power, and many different pairs of points have Right: in order to describe one of these lines (the green one), we denote the four points by z1 to z4 (complex numbers). Bottom: we use the cross ratio formula to compute one descriptor for each of the three lines.

similar descriptors. Therefore matching becomes ambiguous. We believe that our higher-dimensional framework makes it possible to build more expressive features. Triangles, unlike line segments, have an interior. So, it should be possible to have image-based features to describe this interior. To do this, we can use the simple method explained in section 5.2, or, for instance, a histogram of gradient features. Obviously, many other types of features are possible (e.g., bags of words.). These new features would be more specific, and would have higher discriminative power. Therefore a triplet in one image would have fewer similar triplets in the other. In this situation, the matching would become less ambiguous and easier to compute.

3D potential

We now present a high-order potential to match 3D point clouds. We assume that the vertical axis is known and design a potential which is invariant to scale and rotation about this axis. Clearly, many other potentials are possible depending on the assumptions made (e.g., scale/vertical axis known or unknown). We use a 6-dimensional feature to describe the 3D point triplets (Figure 6): The first three features are the angles between the three edges of the triangle and the vertical. For the three other features we use the angles of the triangle (as in the 2D case).

IMPLEMENTATION

In the case of d-th order potentials, the brute force algorithm (see Algorithm 2) has a complexity O(n 2d ) per iteration, where n = max{N 1 , N 2 }. However, Leordeanu and Hebert [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] argue that, in their case, the matrix H has approximately O(n 3 ) non-zero values. Therefore, the complexity of their algorithm is around O(n 3 ) operations per iteration for secondorder potentials.

As we increase the order of the potential, the number of elements of the tensor H increases exponentially, and the computation time of the standard algorithm would be the same. Therefore an efficient algorithm is required.

The first step of our algorithm is to build the tensor. This step is often neglected in the literature, but actually requires as much computation as the matching itself, even in the case of conventional graph matching. The tensor size (N 1 N 2 ) d is huge . If we computed it completely, it would require O((N 1 N 2 ) d n f ) operations, where n f is the size of the descriptor of a tuple. However, if we use a truncated similarity measure (i.e., with a compact support), the tensor H can be very sparse. Moreover, in practice, it is not necessary to compute H completely. Therefore in our algorithm, we compute only a small part of H.

In our experiment, we use a truncated Gaussian kernel:

H i,j,k = exp(-γ f i1,j1,k1 -f i2,j2,k2
2 ) if f i1,j1,k1f i2,j2,k2 ≤ σ otherwise 0, where f i1,j1,k1 is the feature vector describing the tuple (i 1 , j 1 , k 1 ).

So, for each tuple i of the first image, we need to find the features of image 2 in a neighborhood of size σ. In practice, we only take the k nearest neighbors with k fixed. This allows us to use a standard implementation of approximate nearest neighbors [24], which in practice is very efficient. This ANN search implementation is based on kd-trees. In our experiments using this approximate algorithm does not bring any significant change to the results.

However, doing this for all tuples in image 1 would be very time consuming, and forcing all the tuples to be matched correctly is very redundant. So, as in [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF], we only sample tN 1 triangles in image 1, with fixed t.

Then, we sample all the possible triangles of image 2, and compute their descriptors. We store them in a kdtree to allow an efficiently search. For each of the se-Input: images I 1 , I 2 and point sets P 1 ,P 2 Output: tensor H 1 H ← empty tensor ; 2 foreach t ∈ set of all tuples in P 2 do 3 f ←computetupleFeature(t, I 2 ) ; lected triangles of image 1, we find the k approximate nearest neighbors of image 2. Then we compute the tensor values:

H i1,j1,k1,i2,j2,k2 = exp(-γ triangle(i 1 , j 1 , k 1 ) - triangle(i 2 , j 2 , k 2 ) 2 ) if triangle(i 2 , j 2 , k 2 ) is among the k nearest neighbors of triangle(i 1 , j 1 , k 1 )
, and 0 otherwise. Then we start the power iteration. The total complexity of the algorithm is O(n d log(n) + ntk log(n)) per iteration. The final algorithm typically takes one second for 80 points, t = 20 and k = 500. The complete setup is summarized in Algorithm 6.

Smart selections of triangles

There are several strategies for selecting triangles depending of the final goal. If one wants to match and allow deformations, the triangle should be selected at small scales. On the other hand, if one wants to capture the global property of a shape, one should select big triangles.

Separable Similarity Measure

One important problem with spectral methods (high-order or not) is that H can be huge. But in some cases, it is possible to avoid computing it. H i,j,k should be a similarity measure between the tuples (i 1 , j 1 , k 1 ) and (i 2 , j 2 , k 2 ). In this section, we explain that if we can decompose this measure as the inner product of two descriptors < f i1,j1,k1 , f i2,j2,k2 >, we do not have to compute the whole H. When the similarity function is a positive definite kernel, it is always possible to write it as an inner product. However, we also need to have a finite representation of f .

In this situation, we can write (for the second order case):

H = d F d 1 ⊗ kro F d 2 ,
where ⊗ kro is the Kronecker product, and F m I,i,j is the m th descriptor of the pair (i, j) of image I. These two feature matrices can also be very sparse if one considers only the relationship between certain pairs (e.g., pairs of close points).

In this situation we can simplify the computation of the power iteration step:

X ← H X H X = ( m F m 1 ⊗ kro F m 2 ) X = m vec(F m 2 X(F m 1 ) T ) ∀i 1 , i 2 , X i1,i2 ← j1,m F m 1,i1,j1 j2 X j1,j2 F m 2,i2,j2 (= j2,m F m 2,i2,j2 j1 X j1,j2 F m 1,i1,j1 ),
by using the formula (B T ⊗ kro A)vec(X) = vec(AXB). This decomposition of the similarity measure decreases the amount of memory required by the program. Its time complexity is only O(nnz(F 1 )n + nnz(F 2 )n) per iteration and, unlike the method described in the previous section, it is an exact algorithm.

In the higher-order case, we can also use this decomposition and the new power iteration step can be written as follows (for the third order case) :

∀i 1 , i 2 , X i1,i2 ← j1,k1,j2,k2 H i1,j1,k1,i2,j2,k2 X j1,j2 X k1,k2 = j1,k1,j2,k2,m F m 1,i1,j1,k1 F m 2,i2,j2,k2 X j1,j2 X k1,k2 = j1,k1,m F m 1,i1,j1,k1 j2 X j1,j2 k2 F m 2,i2,j2,k2 X k1,k2 .
Here, the complexity is O(nnz(F 1 )

• n + F 1 inf,0,0 • F 2 0,0,inf • d + nnz(F 2 ) • n) per iteration,
where F 1 inf,0,0 is the number of doublets (j 1 , k 1 ) such that F 1,(•),j1,k1 is not null, and F 2 0,0,inf is the number of doublets (i 2 , j 2 ) such that F 2,i2,j2,(•) is not null.

EXPERIMENTS

In the experiments presented here (with some exceptions detailed in the subsections), we use Algorithm 6 to compute the tensor. Then, we use the tensor power iteration with unit-norm row constraints described in Algorithm 3, and the ℓ 1 -variant of Algorithm 5. The three first experiments use the simple similarity-invariant potential presented in section 5.1. The smart selection of triangles is not used in those experiments. As explained in section 6, we compute H using the following formula: H i,j,k = exp(-γ f i1,j1,k1f i2,j2,k2

2 ). We set the parameter γ as follows: we compute all the ℓ 2 distances between the tuples of image 1 and their nearest neighbors in image 2 as described in Algorithm 6, then we set γ to the inverse of the average of all the squares of the computed distances. More details are given in the following subsections.

Running time

Even though our tensor power iteration is slower than the probabilistic hypergraph matching method proposed in [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF], since both methods have to first compute H, their total running times are similar.

Synthetic data

Following [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF], [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF], we first use synthetic data in order to quantitatively compare our algorithm to the state of the art. We sample randomly and uniformly n = 25 points in the 2D plane. We create a second set of points by perturbing the first one with Gaussian noise on their positions. Then, we compare different algorithms to match those two sets. The algorithm provides n matches. The accuracy of the algorithm is computed as the number of good matches divided by n.

In order to have a fair comparison between our method and probabilistic hypergraph matching [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF], we first compute the tensor as described earlier. Then, we marginalize it as explained in [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF], and we use the resulting vector with the algorithm they provide on line. We also compare our result and [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF] to spectral matching [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] to show the improvement of using higher-order potentials.

First, we add Gaussian noise to the position of the second point set, apply a global rotation, and add outliers. The results are shown in Figure 7 (top). We can see that our method outperforms the other two. Our interpretation is that when many outliers are added, the ambiguity of pairwise methods [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] increases, because many pairs become similar, whereas triplets are less likely to become similar. Moreover, probabilistic hypergraph matching [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF] reduces the high-order problem to a first-order one, so that it is likely to match points which have the same neighborhoods. Such a method thus becomes ambiguous when there are many outliers.

Second, we add Gaussian noise, rotation, and rescaling. Indeed, low-order matching techniques, such as the spectral method, cannot handle those transformations (rotation and rescaling at the same time). In Figure 7 (bottom), we can see that our method and the one of [START_REF] Zass | Probabilistic graph and hypergraph matching[END_REF] are indifferent to those transformations, but the performance of [START_REF] Leordeanu | A spectral technique for correspondence problems using pairwise constraints[END_REF] drops to 50% after a scaling of only 1.1 or 0.9, and quickly reaches chance level at 1.2 or 0.8.

House Dataset

The House dataset [2] is commonly used to test the performance of matching algorithms. Some objects are taken from different viewpoints and n = 30 key points, which are present in every frame, are labeled. The scale is always roughly the same, but the transformation is now perspective (although the experiment has been designed such that it is almost orthographic). Since the ground truth is provided, it is also easy to compute the accuracy of the algorithm. The algorithm provides n matches, and the accuracy is the number of good matches among them divided by n. In Figure 8, we can see that the low-order algorithms cannot handle the fact that in perspective transforms, the relative positions of points change in a complex way.

Natural images

We take images from the Caltech-256 image database [START_REF] Griffin | Caltech-256 object category dataset[END_REF] which depict objects on a clear background. We extract their silhouettes and subsample points on them. We can then match images from the same class using our algorithm; results are presented in Figure 9. Our tensor-based algorithm is able to match objects with different visual appearances in the presence of strong deformations.

3D object matching

We have also experimented with the 3D point descriptor described in Section 5. We have downloaded some freely available 3D models [1], have manually extracted some points at key positions. After that, we execute our algorithm with only our third-order potential (no local description of the shape). Points are not always matched perfectly, but the results is almost always visually good. Some results are shown in Figure 10.

For more completeness, we also use some 3D models from SHREC 2009 dataset [START_REF] Pratikakis | Shrec09 track: Generic shape retrieval[END_REF], randomly select 70 points on each of them, and match them. The results can be seen on Figure 11. The two sets of experiments have been performed with the same set of parameters.

Potentials of different orders

As explained in Section 3.4, we can also simultaneously use potentials of different orders. We have chosen an example (Figure 12) which is both hard for first-order matching based on SIFT-descriptors, and for tensor matching based on triplets only. We have taken two pictures of the same person with changes in both viewing angle and face expression. Since the face is deformable, local descriptors tend to be unreliable. In addition, algorithms based on the assumption that the transformation is parametric (such as RANSAC) are not applicable.

In both pictures, we automatically extract around 300 interest points, and for each of them compute its SIFT descriptor (using the implementation of [START_REF] Vedaldi | A matlab implementation of sift[END_REF]). Then we match each interest point to the one with the closest descriptor in the other image, when the match is unambiguous, as described in [START_REF] David | Distinctive image features from scale-invariant keypoints[END_REF]. The result (Figure 12.a) is not satisfying. We believe that this is due to the non-parametric deformation of the face, occlusion, relatively textureless images, and ambiguities due to the symmetry.

We use also triplet information only, without SIFT descriptors. Here too, the graph nodes are the SIFT interest points, and are automatically extracted. This leads to ambiguity in the matching process: not all nodes in one image have similar nodes in the other image. Moreover, matching with only scale-and rotation-invariant features (see Section 5.1) is too ambiguous. So we use as triplet descriptor the concatenation of the sines of the three angles and the image coordinates (x-y) of the three edges. This descriptor is only translation invariant but can be robust to small scale or rotation changes. In Figure 12.b, one can see that the resulting matching is globally good, but some details are wrong. Since the descriptors are only based on geometry (and not on the image), the algorithm matches the left (resp. right) part of face 1 to the left (resp. right) part of face 2. However, since the face has turned in the second image, the corresponding parts no longer keep their original geometric location, resulting in wrong matches.

As explained in section 3.4, we can also combine both cues. The algorithm can use both image-based cues from the first-order potential and geometry-based cues from the thirdorder potential. The result is very satisfying (Figure 12.c). We

CONCLUSION

In this paper, we have proposed a tensor-based algorithm for high-order graph matching in computer vision applications. We have reached state-of-the-art performance with simple potentials that are invariant to rigid, affine or projective image transformations. This work can be extended in a number of ways, for example by considering more complex features based on three, four or even more point or line features to be fully invariant to richer classes of transformations. It would also be natural to follow the approach of [START_REF] Caetano | Learning graph matching[END_REF] and learn potentials automatically from labeled or partially labeled data.

Fig. 1 .

 1 Fig. 1. Top: Given two graphs, the matching problem is to find node correspondences which preserve their topology. Bottom: In a hypergraph, one hyperedge can link more than 2 nodes. As an example, in this figure four hyper-edges are represented by circles. Each of them regroups 3 nodes that they link together. The three matches drawn on the bottom figures induce a matching between two hyperedges.

Fig. 2 .

 2 Fig. 2. Top: second-order potentials can be made rotationinvariant by comparing distances between matched points. Down: Third-order potentials can be made similarity-invariant by comparing the angles of triangles.

Fig. 4 .

 4 Fig. 4. (a) a scale-invariant pairwise potential, the angle with respect to the horizontal axis. (b) a rotation-invariant pairwise potential, the distance between the two points. (c) a scale and rotation invariant triplet potential, the 3 angles of the triangle. (d) triplets allow the description of the interior of the triangle, which is a much richer description, and can be affine invariant.

Fig. 5 .

 5 Fig. 5. Left: diagram illustrating the features used in theproposed projective-invariant potential. In order to describe the blue triangle, we build three red lines with four points on each. Right: in order to describe one of these lines (the green one), we denote the four points by z1 to z4 (complex numbers). Bottom: we use the cross ratio formula to compute one descriptor for each of the three lines.

Fig. 6 .

 6 Fig. 6. Diagram explaining the 3D invariant construction. The 3 points described (P1 to P3) and their triangle are in blue. f1 to f6 are the angles used as features. The 3 vertical green arrows represent the vertical axis.

4 F 9 N 6 :

 496 ← F ∪ {f } ; 5 end 6 T ←computeANNtree(F) ; 7 S ←select some tuples in I 1 ; 8 foreach s ∈ S do ←search for k nearest-neighbors(T , s) ; 10 foreach n ∈ N do 11 H(index(s), index(n)) ← similarity(descriptor(s), descriptor(n)) ; Efficient ANN-based algorithm for computing the tensor.

Fig. 7 .

 7 Fig. 7. Top: Accuracy as a function of the number of added outliers. Bottom: Accuracy, as a function of the rescaling. (e.g., x = 2, correspond to a scaling of 1.1 2 ).

Fig. 8 .

 8 Fig. 8. House data. Top: Correspondences found by the proposed method in the house dataset. Bottom: Error Rate on this dataset depending on the base line angle, for different methods.

Fig. 9 .

 9 Fig. 9. Matching silhouettes from the Caltech-256 database.

Fig. 10 .

 10 Fig. 10. Two pairs of 3D models matched by our algorithm.

Fig. 11 .

 11 Fig. 11. Random points are selected on each of the two 3D models, and then matched.

Fig. 12 .

 12 Fig. 12. (Best seen in color.) Matching of two different pictures with a) SIFT only, b) tensor matching only, c) combined, and d) combined with dummy nodes

This framework can easily be extended to allow matching points from the first image to no point in the second image adding a dummy node to the second image as in[START_REF] Berg | Shape matching and object recognition using low distortion correspondence[END_REF] (if a point of the first image is matched to this dummy node, it means that it is matched to no point).

ACKNOWLEDGMENTS

We would like to thank Choi Ouk for very helpful discussions, which has inspired a lot this article. This paper was supported in part by a grant from the Agence Nationale de la Recherche (MGA Project), by the ERC grants SIERRA and Vide-oWorld, by the Korea Association of Robot industry(KAR) grant funded by the Korea government(MKE) (No.10031903), and by the Defense Acquisition Program Administration and Agency for Defense Development, Korea, through the Image Information Research Center at KAIST.


Sangkil Kim
email: ksangkil3@gatech.edu

Herve Aubert
email: herve.aubert@enseeiht.fr

Manos M Tentzeris

An Inkjet-printed Flexible Broadband Coupler in Substrate Integrated Waveguide (SIW) Technology for Sensing, RFID and Communication Applications

Keywords: Multi-layer coupler, inkjet-printed electronics, substrate integrated technology, broadband, flexible SIW

The design and implementation of a novel inkjetprinted flexible broadband multilayer coupler on a polyimide film (Kapton) in substrate integrated waveguide (SIW) technology are demonstrated for the first time. A conformal broadband microstrip-to-SIW interconnect is inkjet-printed and its flexibility is experimentally verified. An inkjet-printed multilayer coupler is designed and fabricated based on the flexible SIW interconnect and its frequency response is discussed. The main challenges concerning the additive fabrication process are also thoroughly covered.

I. INTRODUCTION

Low-cost compact multilayer wireless electronics have become a key factor over the past decade to implement integrated sensor and communication systems for quality of life and the Internet of Things (IoT) applications. However, it has been very challenging to implement flexible multilayer structures, because typically required substrate thickness limit the flexibility, while numerous microwave components, such as transmission lines, antennas and resonators, are sensitive to geometric changes and misalignments [START_REF] Nathan | Flexible Electronics: The Next Ubiquitous Platform[END_REF].

First of all, interconnects should be highly flexible in order to maintain the system performance under bending or folding. It is critical to utilize flexible substrates to achieve high flexibility as well as adequate fabrication/metallization methods which are compatible with the chosen substrate and able to stand bending/folding. Via metallization and alignment technique are also important to implement multilayer compact electronic system. The cost efficiency of the whole system should be considered while satisfying the system requirements.

In this paper, a novel approach which utilizes inkjet printing technology to fabricate scalable flexible multilayer 2D/3D electronics in SIW technology, that can be suitable for a variety of communication, RFID and sensing applications, is proposed. The cost effective nanoparticle-based inkjet printing fabrication method is used to utilize the full range of flexible substrates, avoid cleanroom process and achieve low-cost systems. Via holes are utilized as alignment marks for the multiple layers.

This paper is organized as follows. Section II presents the experimental demonstration of the proposed flexible SIW interconnect and multi-layer broadband coupler. Section III discusses the details of the fabrication procedure of the inkjetprinted flexible multi-layer microwave components in SIW technology, while the last section closes with the summary and the future work.

II. FLEXIBLE INKJET-PRINTED MULTILAYER COUPLER DESIGN

A. Flexible SIW Interconnect

As a first step, a SIW interconnect has been printed on a flexible polyimide film as shown in Fig. 1(a). The SIW line was designed for the operation frequency of 5.8 GHz, and for this reason the cutoff frequency of the fundamental mode (f 0 ) was set to 4 GHz. The width of the SIW was 21.7 mm, the diameter of metal vias was 1.0 mm and their pitch was 2 mm. The dimensions of the pitch and the diameter of the via holes were chosen to reduce the radiation leakage as well as to minimize the fabrication error [START_REF] Bozzi | Review of Substrate-Integrated Waveguide Circuits and Antennas[END_REF]. The transition is designed to transform the quasi-TEM mode of microstrip line into the TE 10 mode in the SIW. The ratio of a length to a width is set to 3 and optimized to match the fields of the microstrip line and the SIW [START_REF] Deslandes | Integrated Microstrip and Rectangular Waveguide in Planar Form[END_REF].

The full wave electromagnetic solver, Ansys HFSS, was used to design and simulate the SIW structure including microstrip-to-SIW transitions. The substrate thickness is 254 µ m which has dielectric permittivity ( r ) of 3.0 and the loss tangent (tan ) of 0.03. For the measurements, a Rhode and Schwartz ZVA-8 VNA was used. The measured insertion loss (IL) of the microstip-to-SIW transition is about 0.8 dB while a reported transition has about the IL of 0.2 ~ 0.3 dB because it is built on low loss substrate which loss tangent is usually onetenth of the polyimide film used in this work [START_REF] Deslandes | Integrated Microstrip and Rectangular Waveguide in Planar Form[END_REF]. Measurement and simulation of S-parameters (S 11 & S 21 ) agree very well as shown in Fig. 1(b). The flexibility of the designed SIW interconnect was tested by wrapping it around a cylinder with various diameters (D). The magnitudes of the Sparameters are very stable although the SIW interconnect is bent along cylinders of two radii of curvature (D = 70 mm & 25 mm) as shown in Fig. 2. It should be noted that the inkjetprinted SIW interconnect showed good repeatability since Sparameters were almost identical before and after bending.

B. Inkjet-printed Multilayer Coupler

The geometry of the double-layered SIW coupler consists of two SIWsone on top of the other coupled through two slanted slots as shown in Fig. 3. The length, the angle and the distance of the 1 mm thick slanted slots are optimized to achieve maximum coupling level at the operation frequency of 5.8 GHz [START_REF] Chen | Development of a Low Cost Microwave Mixer using a Broadband Substrate Integrated Waveguide (SIW) Coupler[END_REF]. Two 254 µm thick polyimide films are stacked which results in an overall coupler size of 30 mm 74 mm with total thickness of 0.5 mm. The volume of the proposed coupler (0.74 0 0.42 0 0.01 0 ) in multilayer SIW configuration was successfully miniaturized by about 58 times in terms of wavelength at the operation frequency compared to a previously reported coupler (2 0 1 0 0.09 0 ) [START_REF] Chen | Development of a Low Cost Microwave Mixer using a Broadband Substrate Integrated Waveguide (SIW) Coupler[END_REF]. The two individual SIWs have been printed separately on the two overlying polyimide layers that share a ground plane which has the slanted slot for coupling. The proposed coupler has utilized the same fabrication and design method with the flexible inkjet-printed SIW interconnect. The coupler has been designed and optimized for the operation frequency at 5.8 GHz with a 90 degree phase difference between the coupled (Port3) and the direct port (Port2) [START_REF] Ali | Design and Implementation of Two-Layer Compact Wideband Butler Matrices in SIW Technology for Ku-Band Applications[END_REF]. The measured 4-port S-parameters and the phase difference are shown in Fig. 4. The measured insertion loss of the fabricated multilayer coupler is 9.3 dB and the phase difference is 127 degrees at 5.8 GHz as shown in Fig. 4, while the simulated insertion loss and phase difference are 8.5 dB and 96.7 degrees, respectively. The fabricated coupler has relatively broad bandwidth of 10.3 %. Additional losses from the conductors have occurred due to the fact that the measured thickness of the printed conductive lines is about 2.4 µm while the skin depth of the printed silver nanoparticle layer at 5.8 GHz is about 2.7 µm.

III. PRINTED MULTILAYER COUPLER FABRICATION

The inkjet-printed SIW-based interconnect and broadband coupler proposed in this work are constructed in three steps. The first step involves the cutting of the 254 µm thick substrate along the outline of the design using a laser cutter. Cutting the 254 µm thick polyimide film uses Epilog system's Legend 36EXT with a laser power of 7.2 Watts in a scanning speed of 5.0 cm/s and a resolution of 1200 pulse per inch (PPI). The laser cut substrate is thoroughly washed in flowing water to wash away the blackening and dust.

Step two is to focus on the inkjet printing of the SIW and ground patterns on the prepared substrate. The substrate surface is cleaned using 99% ethanol. A Dimatix DMP-2800 printer is used to print Advanced Nano Products' DGP 40LT-15C silver nanoparticle ink. A 10 pL cartridge is utilized in a nozzle temperature of 37.5 °C and a printer's platen temperature of 60 °C with a drop spacing of 30 µm (847 dpi) in order to prevent running of the printed ink on the polyimide film. A higher platen temperature is desirable to dry the printed silver nanoparticle as fast as possible and optimized drop spacing is required to balance the surface energy of the substrate and the surface tension of the printed ink. The ground plane with the slanted slots is printed on one side and the SIW patterns are printed on the other side of the two layers. Each pattern is printed three times. Solid patterns (without via holes) are printed over the via holes in order to form a The final step is the alignment and the bonding of the printed layers. Two wires with a diameter that fits the via hole dimensions are inserted in two via holes at opposite via walls to align the top and bottom layer. The via holes are filled by a conductive epoxy to maintain the alignment and firm contact of the two layers.

IV. SUMMARY & FUTURE WORK

A flexible SIW interconnect and a compact multilayer broadband coupler utilizing the inkjet printing fabrication method have been demonstrated for the first time. The inkjetprinted SIW interconnect and multilayer compact coupler successfully demonstrated the feasibility of flexible 2D/3D SIW systems utilizing inkjet printing technology. The multilayer coupler is a first step toward the inkjet-printed multilayer electronics systems for wearable, sensing, RFID and communication systems. An inkjet-printed compact multilayer Butler matrix for sensing, RFID and communication applications like a multibeam antenna (MBA) system can be built based on the study presented in this paper.

The relatively high loss can be improved by increasing the metal thickness by printing more layers and using low loss flexible substrates, such BCB and LCP [START_REF] Sharifi | Characterization of Parylene-N as Flexible Substrate and Passivation Layer for Microwave and Millimeter-Wave Integrated Circuits[END_REF]. The conductor loss can be further reduced by increasing the substrate thickness [START_REF] Deslandes | Integrated Microstrip and Rectangular Waveguide in Planar Form[END_REF][START_REF] Moro | Inkjet-Printed Paper-Based Substrate Integrated Waveguide (SIW) Components and Antennas[END_REF].

Fig. 1 .

 1 Fig. 1. (a) Schematic of the designed SIW interconnect. (b) Simulated and measured the microstrip-to-SIW transitions and 20 mm long SIW.

Fig. 2 .

 2 Fig. 2. Flexibility test of the fabricated SIW interconnect.

Fig. 3 .

 3 Fig. 3. Geometry of multilayer broadband coupler.

Fig. 4 .Fig. 5 .

 45 Fig. 4. (a) S-parameters of the inkjet-printed multilayer coupler and (b) phase difference between the direct (Port2) and the coupled port (Port2)

ACKNOWLEDGEMENT

This work was supported by support of National Science Foundation (NSF).


Jan C Van Gemert
email: jan@puzzual.com

Exploiting Photographic Style for Category-Level Image Classification by Generalizing the Spatial Pyramid

Keywords: H.3.1 [Information Storage And Retrieval]: Content Analysis and Indexing-image classification, image aesthetics Imaging, Classification, Retrieval, Indexing, Aesthetics Image classification, Photographic style, Spatial pyramid

This paper investigates the use of photographic style for category-level image classification. Specifically, we exploit the assumption that images within a category share a similar style defined by attributes such as colorfulness, lighting, depth of field, viewpoint and saliency. For these style attributes we create correspondences across images by a generalized spatial pyramid matching scheme. Where the spatial pyramid groups features spatially, we allow more general feature grouping and in this paper we focus on grouping images on photographic style. We evaluate our approach in an object classification task and investigate style differences between professional and amateur photographs. We show that a generalized pyramid with style-based attributes improves performance on the professional Corel and amateur Pascal VOC 2009 image datasets.

INTRODUCTION

There is a relation between the composition of a photograph and its subject. Similar subjects are typically photographed in a similar style [START_REF] Krages | Photography : the art of composition[END_REF]. Depending on the sub- ject, several heuristic photography rules may apply, including: object placement, the rule of thirds, a varying depth of field, etc. Consider figure 1, where similar images share a compositional style. A photographer's use of these styles, however, is influenced by the shape, appearance, and natural surroundings of the subject. For example, a long object is often photographed landscape, a colorful subject may be contrasted against a bland background and a small object typically has low depth of field. Such photographic compositions are often shared when subjects are of the same class.

In this paper we investigate the hypothesis that similar photographic style within object categories can be used to improve object classification. As far as we know, this hypothesis is unexplored in the literature. The state of the art [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2009 Results[END_REF] in category-level object classification is the bag-ofwords model and its variants [START_REF] Khan | Top-down color attention for object recognition[END_REF][START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF][START_REF] Van Gemert | Visual word ambiguity[END_REF]. In this model, local image features are represented by discrete prototypes (visual words) describing an image as a histogram of prototype counts. Prototype-histograms are subsequently used by a classifier to separate images into object categories. Because of the state-of-the-art performance of the visual word model, we use it as our baseline and extend it with photographic style similarity matching.

The use of photographic style in an image can be described by attributes such as colorful, in focus, well-composed, etc. Other, more object-centered types of descriptive attributes have recently been used for object and scene classification [START_REF] Farhadi | Describing objects by their attributes[END_REF][START_REF] Ferrari | Learning visual attributes[END_REF][START_REF] Lampert | Learning to detect unseen object classes by between-class attribute transfer[END_REF][START_REF] Vogel | Semantic modeling of natural scenes for content-based image retrieval[END_REF]. Examples of the attributes used are striped, furry, has wheel, has head, etc. These attributes provide a middle ground between low-level features and high-level categories.

By attribute sharing, only a little amount of training data is required [START_REF] Farhadi | Describing objects by their attributes[END_REF]; it even allows classification with a disjoint training set [START_REF] Lampert | Learning to detect unseen object classes by between-class attribute transfer[END_REF]. In this paper, we are interested in photographic style attributes that aid in object classification. To this end we will design specific style attributes, and use these attributes in combination with the visual word model for image classification.

To incorporate photographic style similarity in the visual word model we draw inspiration from the spatial pyramid introduced by Lazebnik et al . [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] who in turn extend Grauman and Darrell [START_REF] Grauman | The pyramid match kernel: Discriminative classification with sets of image features[END_REF]. The spatial pyramid quantizes the absolute position of visual words in an image to fixed spatial regions. For example the pyramid at level 1 has the quadrants up-left, up-right, low-left, low-right of an image. Higher levels of the pyramid are obtained by quantizing the absolute position in regions of decreasing size. The spatial pyramid creates correspondences between visual words quantized to the same equivalence class (fixed spatial region). In our case, however, instead of relating similar position, we are interested in creating correspondences between similar photographic styles. Therefore, we follow Lazebnik et al ., by quantizing visual words in equivalence classes. However, where they use the absolute position, we are interested in compositional attributes such as colorfulness, lighting, depth of field, viewpoint and saliency. These compositional attributes may be quantized in equivalence classes based on photographic attributes such as saturation, brightness, blur-level, etc. Assigning visual words to these equivalence classes allows us to create correspondences between similar photographic styles.

The contributions of this paper are fourfold. First, we introduce the use of photographic style for category-level object classification. The main assumption of this paper is that similar objects are photographed in a similar manner. Second, we extend the spatial pyramid to a more general version based on equivalence classes, with the spatial pyramid as a special case. Third, we propose several style attributes for creating such equivalence classes. Fourth, we investigate whether photographic style features behave differently on amateur images than on professional photographs.

In the next section we present work related to photographic style classification and automatic photo composition. In section 3 we give our approach for incorporating photographic style in object classifation. Section 4 contains the experimental validation and is followed by our conclusions.

RELATED WORK

Photographic style features can be used for separating professionally made photographs from amateur images. One of the first approaches to this problem is by Tong et al . [START_REF] Tong | Classification of digital photos taken by photographers or home users[END_REF] who feed global features based on blur, contrast, colorfulness and saliency in several classifiers to distinguish between amateur images and a professional image set. Further research [START_REF] Datta | Studying aesthetics in photographic images using a computational approach[END_REF][START_REF] Ke | The design of high-level features for photo quality assessment[END_REF][START_REF] Moorthy | Towards computational models of the visual aesthetic appeal of consumer videos[END_REF] adds various other global image features including blur, average saturation, average brightness and several color-and texture-based features. Feature selection shows that blur is a good performing feature because it determines depth of field. The work by Luo and Tang [START_REF] Luo | Photo and video quality evaluation: Focusing on the subject[END_REF] moves away from global image features. The authors detect a bounding box in the image as the main subject area by determining what is in focus by a blur detection algorithm [START_REF] Levin | Blind motion deblurring using image statistics[END_REF]. The classification results outperform previous work by us-ing features based on the ratio in the subject area versus the image background with features such as brightness, contrast and color. In our work, however, we are not interested in using style features to separate professional photographs from amateur ones, but in using style features to aid image classification. Instead of the compositional differences between images we exploit their compositional similarities. Nevertheless, we draw inspiration from the proposed photographic style features and use local features in the visual word model for creating correspondences between style attributes.

Photographic style is also used for automatically finding good compositions in images. Such automatic compositions provide a user with a "touch-up" button to help enhancing photographic image quality. Automatic compositions can be achieved by directly applying heuristics such as the rule of thirds and blurring of the background [START_REF] Banerjee | In-camera automation of photographic composition rules[END_REF]. In [START_REF] Liu | Optimizing photo composition[END_REF] such heuristic rules are combined with saliency detection in an aesthetic score function. In [START_REF] Chang | Finding good composition in panoramic scenes[END_REF], the authors combine saliency with the GIST image descriptor in a stochastic search algorithm to find a composition that matches one of several well-composed reference images. From these works we can use the heuristics and the proposed saliency. However, these papers optimize an aesthetic function to find a good composition in a single image. In contrast, we use composition similarity between images and refrain from labeling compositions as good or bad.

APPROACH

We aim to exploit similarities in photographic style for image categorization. To this end we create correspondences within the visual word model between similarly-styled image attributes. Examples of such style attributes are colorfulness, intensity and depth of field. To incorporate correspondences between these styles we use techniques inspired by spatial pyramid matching [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF]. However, where the spatial pyramid uses approximate global geometric correspondences between visual words, we are interested in approximate style correspondences. In the next section we will briefly review the spatial pyramid, after which we present our generalization to a style pyramid, and the style attributes themselves.

The spatial pyramid [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] by Lazebnik et al . is based on the pyramid matching scheme by Grauman and Darrell [START_REF] Grauman | The pyramid match kernel: Discriminative classification with sets of image features[END_REF]. Whereas Grauman and Darrel use coarse-to-fine bins in feature space, Lazebnik et al . create a pyramid based on the spatial image layout. The spatial pyramid repeatedly divides an image into fixed sub-regions of finer resolution, where spatial pyramid level ∈ {0, . . . , L} has R( ) = 2 2 sub-regions. In image X all features are assigned to their best visual word index v, selected from a vocabulary V . The frequency of visual word v inside sub-region i of image X is given by the histogram bin H i X (v). Similarity between images X and Y on level of the spatial pyramid [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF] is given by histogram intersection

I (X, Y ) = R( ) i=1 |V | v=1 min H i X (v), H i Y (v) . (1)
After reweighting larger sub-regions on a lower pyramid level, the final spatial pyramid becomes See figure 2(a) for an example of the spatial pyramid.

κ L (X, Y ) = 1 2 L I 0 (X, Y ) + L =1 1 2 L-+1 I (X, Y ). (2) (a) (b) (c)
The spatial pyramid builds correspondences by quantizing the absolute position of an image feature in disjoint equivalence classes. For photographic style correspondences we propose to use the same approach, only for more general equivalence classes based on style. As a running example, let us assume that color saturation is a measure of colorfulness. Then, we propose to quantize the amount of saturation in disjoint equivalence classes, and create correspondences between these equivalence classes. If color saturation ranges between [0, . . . , 1) then an example of two disjoint equivalence classes is given by [0, . . . , 1 2 ), [ 1 2 , . . . , 1) . Each image feature can be assigned to an equivalence class depending on its average amount of saturation. A pyramid may be obtained by creating multiple levels of equivalence classes. More formally, for a visual word v and a scalar style attribute function S(v) with a value range [a, . . . , b), we quantize visual words on level of the pyramid in R( ) = 2 equivalence classes, where the visual words for in each equivalence class {0, ., i, ., R( ) -1} are given by

E(i) = v ∈ X | a + i b -a R( ) ≤ S(v) < a + (i + 1) b -a R( ) .
(3) A style pyramid can be created by replacing the image similarity for the spatial pyramid in equation 1 with the similarity between images X and Y on level of the style pyramid by

I (X, Y ) = R( ) i=1 |V | v=1 min H E(i) X (v), H E(i) Y (v) , (4)
where H

E(i) X
(v) denotes the frequency of visual word v in equivalence class E(i) for image X. Note that the spatial pyramid is a special 2-dimensional case of this approach, where the equivalence classes are based on the x and y position. See figure 2(b) for an example of a style pyramid.

Creating correspondences between photographic styles is now a matter of matching a photographic style to a function S(v). By quantizing this style function S(v), we match similar styled visual words to each other. By relating styles, we aim to relate images that share a similar photographic composition.

Style Attributes

Inspired by the related work in section 2, we selected several style attributes and their corresponding style function S(v). A visual word v represents a patch of pixels in the image. The style values for these pixels are Gaussian weighted and averaged to obtain a single value S(v), unless stated otherwise. These style attributes give us the equivalence classes to match similarly styled images.

Salient Points. The visual word model treats an image as a bag of local features and uses the occurrence counts of feature prototypes for classification. The use of local features has also proved beneficial for classifying professional versus amateur photographs [START_REF] Luo | Photo and video quality evaluation: Focusing on the subject[END_REF]. Therefore, we base our work solely on local features (standard SIFT). We use dense sampling of image features, since this has proven to give good classification results [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF]. Besides dense sampling, local features can be detected based on interesting, or salient image structures such as corners and blobs. Since salient points represent interesting image structure, their occurrence, or lack of occurrence, influences the photographic style. Consider for example figure 3, where all salient points are found on the subject, which is framed by featureless sky. To capture such style similarities we create correspondences between various types of interest point detectors. We use the Harris-Laplace and Hessian-Laplace detectors [START_REF] Mikolajczyk | Scale & affine invariant interest point detectors[END_REF] and a detector based on color interest points [START_REF] Van De Weijer | Boosting color saliency in image feature detection[END_REF]. We put each visual word that originates from the same detector in its own equivalence class. In figure 3 we show examples of the used salient point detectors. Saliency Maps. Professional photographs typically have a clear subject-background separation, whereas amateur ones may have various distracting elements. Such distracting, or salient, regions may be automatically detected. We use two recent salient region detection algorithms. One of these detectors is based on shape and color [START_REF] Valenti | Image saliency by isocentric curvedness and color[END_REF]. The other detector is based on frequency, color and luminance and outperforms other approaches in an object segmentation task [START_REF] Achanta | Frequency-tuned Salient Region Detection[END_REF]. We create equivalence classes based on the saliency values. Note that most work on object classification with saliency keep only the salient regions. In contrast, we create equivalence classes based on saliency, keeping non-salient regions in a class of their own. Hence, our approach retains features that are non-salient. Moreover, if they are consistently nonsalient within an object category, such features will still aid in object classification. In figure 4 we show an example of the two feature maps. For our experiments we use σ = 5 for both methods, and curvedness = 5 for [START_REF] Valenti | Image saliency by isocentric curvedness and color[END_REF].

Viewpoint. We model object viewpoint with a local cooccurrence pyramid of visual words. Consider for example the bus images in figure 1. Similarity in viewpoint may be inferred from the co-occurrence of the wheels at a certain distance. Thus, we use a local co-occurrence pyramid to model the viewpoint. Specifically, we build on the work of Savarese et al . [START_REF] Savarese | Discriminative object class models of appearance and shape by correlatons[END_REF] in their efficient approach to compute visual word correlograms. A correlogram is a binary triangle matrix of size |V | * |V +1| 2 that expresses the co-occurrence of a pair of visual words at a certain distance d. We extend Savarese et al . [START_REF] Savarese | Discriminative object class models of appearance and shape by correlatons[END_REF] by our pyramid of equivalence classes in equation 4. I.e., we calculate the co-occurrence of a pair of visual words (i, j) as d1 ≤ mindist(i,j) < d2, where mindist(i,j) is the minimum distance along the x or y axis between visual word i and j in pixels. In figure 2(c) we illustrate the local co-occurrence pyramid.

Depth of Field. The important parts of an image are typically in focus. This is probably the reason why depth of field by blur detection is a good-performing feature for separating professional images from amateur photographs [START_REF] Datta | Studying aesthetics in photographic images using a computational approach[END_REF][START_REF] Ke | The design of high-level features for photo quality assessment[END_REF][START_REF] Luo | Photo and video quality evaluation: Focusing on the subject[END_REF]. To create correspondences for depth of field, we use the degree of blur as a style function. We implement the method by [START_REF] Luo | Photo and video quality evaluation: Focusing on the subject[END_REF], who extend the horizontal blur detection method in [START_REF] Levin | Blind motion deblurring using image statistics[END_REF] with vertical blur detection. Where they use a uniform kernel we use a Gaussian kernel to extend beyond discrete blur levels. The blur detection approach is based on natural image statistics of derivative filters. Derivative filters measure edge strength which intuitively is inversely related to the blur level. The blur level of a local window in the image is found by the maximum likelihood over a range of image derivative kernel sizes. Specifically, let the derivative distribution p σ (i) of the pixels i in image I be given by p σ (i) ∝ hist(d σ xy * I), where d σ xy is a 2D Gaussian derivative kernel with kernel size σ. Then the log-likelihood of a blur level σ for a window of pixels W in image I is l σ (W ) = i∈W log p σ (i). In our case, each visual word corresponds to a set of pixels in the image, we use these pixels for W . The blur level k over a range of blur levels K of window W is given by the maximum likelihood k = arg max σ∈K l σ (W ). We show a blur detection example in figure 5.

Rule of thirds. One of the basic rules of thumb in photographic style is the rule of thirds [START_REF] Krages | Photography : the art of composition[END_REF]. This rule states that the subject should be located at one of the intersections of the three equally spaced horizontal lines with three equally spaced vertical lines. Effectively, the image has four of these intersections, located in each quadrant. These quadrants are also the equivalence classes for level 1 of the spatial pyramid. Therefore, we will use the standard spatial pyramid to take the rule of thirds into account. In figure 2(a) we illustrate the spatial pyramid. Note that the four equivalence classes each capture an intersecting line from the rule of thirds.

Colorfulness. Color is a powerful cue for contrasting the subject from the background. The background may be less colorful to make the subject stand out, as for example the Cat of the Corel collection in figure 6, or alternatively, the background may be more colorful as for example the Airplane of the Corel collection in figure 6. We do not focus on only the colorful regions, rather we provide the machinery for features to match to approximately the same level of colorfulness. For measuring colorfulness we use the saturation from the HSV color space. Note that the saturation is different from the hue, or from a RGB color histogram. The hue or the histogram would create correspondences between similar colors, whereas the saturation creates correspondences between similar colorful areas irrespective of the color itself. Note that the SIFT descriptor we use, only takes the intensity channel into account. In figure 7 we show an example of local features split by saturation level.

Lighting. Similar to colorfulness, the lighting of an image region may be related to its importance in the photograph. Hence, for similar objects, the lighting level may be the same. Therefore we use the brightness by the Value channel from the HSV color space as a measure of lighting. Note that the SIFT descriptors themselves are invariant to brightness changes. However, by creating correspondences between brightness levels we re-introduce some sensitivity to brightness. In figure 7 we show an example of local features split by brightness level.

EXPERIMENTS

We experimentally validate if style features benefit categorylevel object classification. Moreover, we expect that photographic style is more pronounced in professional photographs than in amateur images. To investigate this hypothesis we compare classification performance between a professional and an amateur photograph collection. For the amateur collection we use the Pascal VOC set [START_REF] Everingham | The PASCAL Visual Object Classes Challenge 2009 Results[END_REF]. This is a well-known set for image categorization and consists of 20 categories of Flickr images. Flickr images are typically amateur images, uploaded by random users on the internet. For the professional set we use similar categories from the Corel collection. We tried to match the categories of the Pascal VOC set in the Corel collection. In figure 6 we show an example per category of the two sets.

Experimental Setup

The Corel set has 100 images per category, with a total of 2000 images. For the Pascal VOC set we combine the 3473 images in the specified train set with the 3581 in the validation set to a single set of 7054 images. We split the Corel and the VOC set in 10 random train and test sets, distributing the positive examples equally over train and test set. Instead of the standard single test set given for the VOC we use 10 repetitions to compute average and standard deviations which allow significance testing. As the performance measure we adopt Average Precision (AP), as it is commonly used for the Pascal VOC. For features we only use standard SIFT. When evaluating salient points we add a minimum baseline of densely sampled SIFT features at every 10 pixels with a Gaussian weighted window size of σ = 2. For the remaining style attributes we use all available salient point detectors. Our visual word vocabulary size |V | = 2000, and is created per training set for each of the 10 splits with K-means on 200.000 randomly sampled SIFT features. For classification, we use libsvm and use its built in cross-validation method to set the best C parameter. For the levels of the style pyramid we use two levels, with 2 and 4 equivalence classes. For the viewpoint feature that uses local co-occurrence, we group all local features from 0-60 pixels with steps of 15 pixels. Thus, this pyramid also includes the levels for 0-30, and 30-60 pixels.

Results

In figure 8 we show results in Average Precision (AP) for all style attributes per category for the amateur Pascal VOC set and professional Corel set. Note that the lesser amount of within-class variation in Corel causes much better overall performance than the Pascal VOC. Some classes in Corel are hard to improve because they are close to perfect (1.0) AP (Engine, Drinks, Buses, Cats, Door, Bonsai). For the professional set there are 21 style features which significantly increase results, whereas the amateur set has 49 significant increases. One reason for this are the six close to perfect categories in Corel that are hard to improve. Furthermore, the standard deviations for the Corel set is larger and therefore harder to significantly improve, which is due to the smaller size of the set. The spatial pyramid and viewpoint generally always improve results for Pascal VOC. The spatial pyramid is better in global shape (bus, train) whereas viewpoint is better for local appearance (bottle, dog, pottedplant, sheep). For the Corel set, viewpoint often performs under the baseline, and the spatial pyramid is only really helpful for obvious contextual scene categories (bird, door, kitchen, offices).

In table 1 we summarize the classification performance for Pascal VOC and Corel over the 10 random draws of the data, measured in mean average precision for the full pyramid, and for single pyramid levels (without the underlying levels). Results for both image sets show no clear preference for a higher level pyramid, but a pyramid is always better than a single level, confirming results of [START_REF] Lazebnik | Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[END_REF][START_REF] Savarese | Discriminative object class models of appearance and shape by correlatons[END_REF]. Most style features improve results, however the least helpful attributes are the saliency maps, where the frequency saliency map never helps (except for bird in Corel) and shape saliency only rarely improves performance. This suggests that automatic detected image saliency is not very consistent on the category level. For the professional images in Corel, the best performing style feature is lighting. This illustrates that simply grouping pixels on brightness level with our generalized pyramid can already outperform the well-known spatial pyramid. For the other style attributes, only the frequency saliency map and the viewpoint do not significantly improve results. For the amateur images in Pascal VOC the viewpoint is the best performing attribute, and colorfulness and frequency saliency map do not significantly improve results. Note that the best performing style attribute on the amateur images (viewpoint) does not help for the professional images. This may be the case because the professional images are the center of attention and typically fill the entire image. Hence, local viewpoint differences capture only part of the object. In contrast, the objects in the amateur images are more cluttered which makes objects share a local context from the photographer's viewpoint. In a similar vain, the best performing attribute on the professional set (lighting) does not help for the amateur images. This confirms the hypothesis that objects in professional images share similar lighting whereas amateur images do not. A similar, but less strong case, can be made for blur and colorfulness, where results improve for the professional set however do not help for the amateur set.

In figure 9 we show results for each salient point detector for adding them all together, and for the salient point pyramid which puts each detector type in a equivalence class. Generally speaking, adding all detections (baseline) outperforms each individual detector. Only for Bird, in the VOC set, dense sampling outperforms the baseline. This may be explained because dense sampling mostly takes the important context (sky) into account. Putting each detector type in a equivalence class performs even better since context and subject information are both present but not wrongly matched against each other as in the baseline. What is more, the salient point pyramid always improves results for all categories for both image sets.

CONCLUSIONS

We presented a method to exploit style correspondences between images for object-level image classification. We achieved this by a generalization of the spatial pyramid by creating equivalence classes between approximately similar style attributes. We experimentally evaluated our method on a professional set and an amateur set of images. The results show that several style-based attributes improve performance over the baseline for both sets. Grouping salient point types and global composition benefits both sets. For amateur images, the local object configuration is most important whereas for professional images the colorfulness, the depth of field and the lighting is most beneficial.

Figure 1 :

 1 Figure 1: An example of similar photographic subjects sharing a composition. The Antelope images in the top row share depth of field and positioning, whereas the Bus images in the bottom row have similar viewpoint and color contrast.

Figure 2 :

 2 Figure 2: (a) Spatial pyramid, (b) Style pyramid, (c) Local co-occurrence pyramid. The star, dot and plus denote three visual word types. The striped, checkered and polka dot patterns represent four equivalence classes. Below the example image are the histograms of the visual words, grouped by equivalence class. Note that the first equivalence class histogram (in white) represents the whole image.

Figure 3 :

 3 Figure 3: Example of interest point detection. (a) Harris-Laplacian (b) Hessian-Laplacian. (c) Color boosted Hessian. Note that we only show 80 points for clarity. Best viewed in color.

Figure 4 :Figure 5 :

 45 Figure 4: Example of saliency maps. (a) Original image. (b) Frequency-tuned saliency map. (c) Isocentric saliency map. The saliency level is given by the brightness.

Figure 6 :Figure 7 :

 67 Figure 6: Example images of the amateur set (Pascal VOC 2009) and the matching categories of the professional set (Corel).

Figure 8 :

 8 Figure 8: Results on Pascal VOC and Corel for the style pyramid for all style attributes per category. The baseline (no style) is in gray where the width of the gray box denotes standard deviation. The x-axis denotes deviation from the baseline where the baseline mean is given on the y-axis in brackets behind the category name. Corresponding categories between the Pascal VOC and Corel are grouped as in fig 6.

Figure 9 :

 9 Figure 9: Results on Pascal VOC and Corel for individual salient point detectors and the salient points style pyramid. The baseline (addition of all detectors) is in gray where the width of the gray box denotes standard deviation. The x-axis denotes deviation from the baseline where the baseline mean is given on the y-axis in brackets behind the category name. Corresponding categories between the Pascal VOC and Corel are grouped as in fig 6.

Table 1 :

 1 Results in Mean Average Precision * 100 for single and full pyramid levels. The best results are given in bold and a significant increase is underlined.

			Pascal VOC 2009			Corel
		Baseline (Level 0): 38.5 ± 0.5		Baseline (Level 0): 74.6±0.7
		Level 1	Level 2	Level 1	Level 2
	Style	Single	Pyramid	Single	Pyramid Single	Pyramid	Single	Pyramid
	Lighting	38.3±0.5	39.5±0.5	38.0±0.3	40.2±0.3	77.1±0.9	78.0±0.8	76.9±0.9	79.0±0.8
	Colorfulness	35.4±0.5	38.2±0.6	34.6±0.4	37.8±0.6	74.1±0.8	76.6±0.8	73.6±0.8	76.5±0.8
	Blur	38.9±0.3	39.9±0.4	35.6±0.5	39.0±0.4	77.1±0.7	77.6±0.6	73.8±0.8	77.1±0.8
	Freq. Saliency	36.3±0.4	38.5±0.4	34.9±0.5	37.7±0.5	71.4±0.8	74.4±0.8	69.3±0.8	73.1±0.7
	Shape Saliency	37.3±0.5	39.1±0.4	37.7±0.6	39.7±0.4	74.3±0.8	76.0±0.9	75.0±0.9	76.8±0.8
	Salient Points		42.0±0.8				77.8±0.6
	Spatial Pyramid 40.7±0.6	42.0±0.4			76.1±0.7	77.5±0.6
	Viewpoint	42.7±0.4	43.6±0.4	42.4±0.4	43.4±0.4 73.3±1.1	75.5±0.9	72.2±0.9	74.1±0.9

Sponsored in part by the 2ACI DGA project and the VideoWorld ERC grant.