José Rui Figueira
email: jose.figueira@mines.inpl-nancy.fr

Luís Paquete
email: paquete@dei.uc.pt

Marco Simões
email: msimoes@student.dei.uc.pt

Daniel Vanderpooten

Algorithmic Improvements on Dynamic Programming for the Bi-objective {0,1} Knapsack Problem

This paper presents several methodological and algorithmic improvements over a state-of-theart dynamic programming algorithm for solving the bi-objective {0, 1} knapsack problem. The variants proposed make use of new definitions of lower and upper bounds, which allow a large number of states to be discarded. The computation of these bounds are based on the application of dichotomic search, definition of new bound sets, and bi-objective simplex algorithms to solve the relaxed problem. Although these new techniques are not of a common application for dynamic programming, we show that the best variants tested in this work can lead to an average improvement of 20% in CPU-time and significant less memory usage than the original approach in a wide benchmark set of instances, even for the most difficult ones in the literature.

Introduction

The single-objective {0, 1} knapsack problem consists of choosing a subset of objects from a finite set that maximizes the overall profit, which results from the sum of the individual benefits of the selected objects where a capacity constraint must be fulfilled, i.e., the sum of the weights of the selected objects must not surpass a given capacity [START_REF] Kellerer | Knapsack Problems[END_REF][START_REF] Martello | Knapsack Problems -Algorithms and Computer Implementations[END_REF]. The multi-objective version of this problem consists of "maximizing" a finite small number of objective functions under the same budgetary constraint. The operator "maximizing" means to search for all efficient (nondominated) solution (vectors). The expression "efficient solutions" is related to the space of objects while the expression "nondominated vectors" is related to the space of the outcomes or objective functions values. A vector is said to be nondominated if there is no other vector that improves simultaneously the outcomes of all the objectives. The problem of searching for efficient solutions can be stated as a {0, 1} linear programming problem as follows:

"max" f (x) = f 1 (x), f 2 (x), . . . , f (x), . . . , f p (x) subject to: w T x W, x ∈ {0, 1} n

(1)

1
where f (x) = n j=1 v j x j , v j is the benefit of object j on objective , j = 1, . . . , n, = 1, . . . , p, and x = (x 1 , . . . , x j , . . . , x n ) with x j = 1 if object j is included in the subset of the selected objects and x j = 0 otherwise; w = (w 1 , . . . , w j , . . . , w n ) is the weight vector and W is the overall capacity. Operator "max" means that it is not possible to maximize all the objectives simultaneously. Assume, without loss of generality, that v j , w j , and W belong to N, j = 1, . . . , n, = 1, . . . , p and that n j=1 w j > W (to avoid obvious solutions). In this paper, we consider the bi-objective {0, 1} knapsack problem, i.e., the multi-objective {0, 1} knapsack problem with p = 2. Applications of this problem can be found in capital budgeting [START_REF] Rosenblatt | Generating the discrete efficient fronteir to the capital budgeting problem[END_REF][START_REF] Jenkins | A bicriteria knapsack program for planning remediation of contaminated lightstation sites[END_REF], transportation [START_REF] Teng | A multiobjective programming approach for selecting non-independent transportation investiment alternatives[END_REF], and biology [START_REF] Kostreva | Relocation problems arising in conservation biology[END_REF]. Several approaches were developed to deal with the multi-objective {0, 1} knapsack problem. Some are of an exact nature, such as branch-and-bound algorithms [START_REF] Visée | Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem[END_REF] and dynamic programming (DP) [START_REF] Wiecek | Dynamic programming approaches to the multiple criteria knapsack problem[END_REF][START_REF] Captivo | Solving bicriteria 0-1 knapsack problems using a labeling algorithm[END_REF][START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF], while others are approximate approaches including polynomial approximations [START_REF] Erlebach | Approximating multi-objective knapsack problems[END_REF][START_REF] Bazgan | Implementing an efficient fptas for the 0-1 multi-objective knapsack problem[END_REF], heuristics [START_REF] Gomes Da Silva | Core problems in bi-criteria 0,1-knapsack problems[END_REF], metaheuristics [START_REF] Gomes Da Silva | A scatter search method for bi-criteria {0, 1}-knapsack problems[END_REF], and hybrid methods [START_REF] Gomes Da Silva | Integrating partial optimization with scatter search for solving bi-criteria {0, 1}-knapsack problems[END_REF]. Exact based algorithms, such as DP, can deal with different and difficult medium-large size instances in a very efficient way [START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF], while approximation based algorithms appear to be more relevant for very large scale problems. This article deals with several improvements of DP algorithm of Bazgan et al. [START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF] for the bi-objective {0, 1} knapsack problem (herewith called BKP-DP). This approach uses several complementary dominance relations to discard elements from the current pool of partial solutions at each stage. For one of the three dominance relations, the algorithm needs to update two bounds at each stage: an upper bound vector obtained for each partial solution in the pool based on the improved state-of-the-art Martello and Toth bound [START_REF] Martello | Knapsack Problems -Algorithms and Computer Implementations[END_REF], and a lower bound set that contains feasible extensions of partial solutions in the pool. A partial solution is discarded if its upper bound is dominated by some extension in a given lower bound set. Clearly, the tighter the lower and the upper bound are, the larger the number of partial solutions that can be discarded. In this article, we present three ways of tightening the upper bound and the lower bound set. Briefly, the three techniques are described as follows:

• Variant 1, which computes of a small set of efficient solutions by solving a sequence of weighted scalarized bi-objective {0, 1} knapsack problem with dichotomic search.

• Variant 2, which computes the nondominated extreme vectors of the relaxation of the problem solved by a bi-objective simplex algorithm and makes use of a repairing mechanism (the improvement method described by Gomes da Silva et al. [START_REF] Gomes Da Silva | A scatter search method for bi-criteria {0, 1}-knapsack problems[END_REF]) to restore feasibility.

• Variant 3, which generates feasible extensions for each partial solution at a given stage k by adding its profit to the profits obtained through dichotomic search on the reduced bi-objective {0, 1} knapsack problem with the remaining n -k objects.

Note that Variants 1 and 2 will generate a lower bound, whereas Variant 3 will generate an upper bound for each partial solution. In addition, note that Variant 1 and 3 consist of solving several single-objective {0, 1} knapsack problems. However, Variant 1 performs dichotomic search once and Variant 3 is only performed in the last stages.

In this article, we incorporate the computation of these bounds in the state-of-the-art DP algorithm proposed by Bazgan et al. [START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF] and analyze, from an experimental point of view, the performance of several variants on a wide benchmark set of instances. The paper is organized as follows. Section 2 introduces the main definitions and notation in multi-objective optimization as well as an explanation of BKP-DP algorithm. The three variants used for improving the BKP-DP algorithm are presented in Section 3. Section 4 comprises the design of the experiments, computational results and discussion. Finally, Section 5 provides conclusions and lines for future research.

Main concepts, definitions, and notation

This section is devoted to the main concepts in multi-objective combinatorial optimization, their definitions, notation as well as a brief description of BKP-DP algorithm proposed by Bazgan et al. [START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF].

Optimality concepts

Let X denote the set of feasible solutions in the object or decision space and Y their image, Y := f (X), in the objective space. Let x, x ∈ X. We introduce the following dominance relations for p objective functions:

• f (x)∆f (x ) (x dominates x ), if and only if f i (x) f i (x ), i = 1, . . . , p;

• f (x)∆f (x ) (x strictly dominates x ), if and only if x∆x and f (x) = f (x ).

A solution x ∈ X is efficient if and only if there is no other feasible solution x ∈ X such that f (x )∆f (x) and its corresponding objective vector is nondominated. The set of all efficient solutions is called the efficient set and the set of all nondominated vectors is denoted by N D(Y ). The algorithms described in this article output the set N D(Y ). The computation of the efficient set can be obtained by keeping states with the same profit and weight. Very often in multi-objective combinatorial optimization it is usual to distinguish between supported and unsupported vectors (solutions) in the objective (decision) space [START_REF] Steuer | Multiple Criteria Optimization: Theory, Computation and Application[END_REF].

Main features of BKP-DP algorithm

The sequential process used in BKP-DP algorithm consists of n stages. At any stage k, the algorithm generates a set of states S k that correspond to a subset of the feasible solutions made up of objects belonging exclusively to the k first objects, k = 1, . . . , n. A state s = s 1 , s 2 , s 3 ∈ S k represents a feasible solution of profits s 1 and s 2 , and weight s 3 . At each stage k = 1, . . . , n, the states are generated according to the following recursion:

S k := Dom T k := S k-1 ∪ s 1 + v 1 k , s 2 + v 2 k , s 3 + w k : s 3 + w k W, s ∈ S k-1 (2)
with the basis case S 0 := {(0, 0, 0)}. Dom(T k ) denotes the use of certain dominance relations that allow to filter the states in T k . The efficiency of BKP-DP depends strongly on the definition of these relations. Bazgan et al. propose the use of three dominance relations at each stage k = 1, . . . , n that allow to discard states in T k that will not lead to other states that represent nondominated vectors.

At stage k = 1, . . . , n, considering two states s ∈ T k and s ∈ T k , s is discarded, and thus does not belong to S k , if and only if at least one of the following three conditions holds: • (D3)

• (D1) s = s 1 + v 1 k , s 2 + v 2 k , s 3 + w k and s 3 W - n j=k w j , • (D2) s1 , s2 ∆ s 1 , s 2 and s3 s 3 if k < n, s v 6 - f 1 f 2 u(s)
  s1 + j∈J v 1 j , s2 + j∈J v 2 j   ∆ u(s) and s3 W - j∈J w j ,
where u(s) is an upper bound of state s and J corresponds to the indices of the n -k last objects with respect to given pre-ordering of objects provided that the capacity constraint is not violated. Condition (D1) discards states whose residual capacity exceeds or is equal to the sum of the weights of the remaining objects. Condition (D2) generalizes the dominance relation used within the Nemhauser-Ullman algorithm [START_REF] Nemhauser | Discrete dynamic programming and capital allocation[END_REF]. Condition (D3) discards states based on the comparison between lower and upper bounds (right and left-hand side of the first condition of D3, respectively). At each comparison, a lower bound set is given by considering all states s ∈ T k . Figure 1 provides an illustration of this condition where white circles correspond to the lower bound set. In the left-hand-side plot, state s is discarded since u(s) is dominated by a lower bound vector. In the right-hand-side plot, state s is not discarded since u(s) is not dominated by any lower bound vector. The upper bound u(s) := (u 1 , u 2 ) in condition (D3) is computed according to the improved Martello and Toth bound [START_REF] Martello | Knapsack Problems -Algorithms and Computer Implementations[END_REF]. Let W (s) := W -s 3 be the residual capacity associated to state s ∈ S k . We denote by c i the position of the first object in {k + 1, . . . , n} that cannot be added to s due to the capacity constraint, when the objects are ordered according to a given criterion. Thus, given the same ordering of the objects, the upper bound u i , i = 1, 2, is computed as follows:

u i := s i + c i -1 j=k+1 v i j + max W (s) v i c i +1 w c i +1 , v i c i -w c i -W (s) v i c i -1 w c i -1 (3)
Two orderings of the objects were considered by the authors. Let O i corresponds to the sequence of objects ordered according to the ratios v k /w k for objective i and let r i be the rank of a given object with respect to objective i, i = 1, 2. O sum denotes an order according to increasing values of the sum of the positions of objects in orders O 1 and O 2 . O max denotes an order according to the increasing values of the maximum rank of objects in orders O 1 and O 2 , where the worst rank of an object in the orders above is given by max{r 1 , r 2 } + (r 1 + r 2 )/2n. Bazgan et al. [START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF] showed that is possible to devise a DP algorithm that operates under the three dominance conditions and orderings as described above and that S n will contain all and only the elements of N D(Y ). For efficiency reasons, the authors suggest to test conditions (D1) and (D2) first since they are easier to check. Condition (D3), which is more computationally expensive, is a final step at each stage of the algorithm.

Algorithmic variants

In this study, three variants are proposed that explore three different ways of defining upper and lower bounds and that allow to discard further states. Therefore, they redefine condition (D3) as described in Section 2.2 and include a pre-processing step.

Variant BKP-DP1

In variant BKP-DP1, a lower bound set is given by the set of supported solutions of the bi-objective {0, 1} knapsack problem that is computed in a pre-processing step. This is obtained by performing dichotomic search [START_REF] Aneja | Bicriteria transportation problem[END_REF]. This procedure consists of constructing a weighted sum objective function of the bi-objective {0, 1} knapsack problem and optimize according to different weights. The following procedure guarantees that set N DS(Y ) is found:

1. Compute the lexicographic maximal (lexmax) solutions x 1 and x 2 w.r.t. f 1 and f 2 , respectively.

Let

x 1 ∈ arg lexmax f 1 (x), f 2 (x) : x ∈ X and x 2 ∈ arg lexmax f 2 (x), f 1 (x) : x ∈ X . Let y 1 := f (x 1 ), y 2 := f (x 2 ), V := ∅ and k := 2. 2. Let R := {y 1 , . . . , y k } with y 1 1 > y 1 2 > . . . > y 1 k . If R \ V = {y k }, then stop; otherwise let y i ∈ arg max y 1 : y ∈ R \ V . 3. Let λ 1 := y 2 i+1 -y 2 i and λ 2 := y 1 i -y 1 i+1 . Let v * j = λ 1 v 1 j + λ 2 v 2 j , for j = 1, . . . , n.
4. Compute the (single-objective) optimal solution x with respect to profits

v * . If f (x) = y i or f (x) = y i+1 , then V := V ∪ y i ; otherwise, let y k+1 := f (x) and R := R ∪ y k+1 . Let k = k + 1 and go to Step 2.
At the end of above procedure, set R will contain only and all elements of N DS(Y ).

For this variant, we rewrite condition (D3) as given in Section 2.2 as follows: At a stage k = 1, . . . , n, a state s ∈ T k is removed if there exists a vector s ∈ N DS(Y ) such that s∆u(s). Note that, as opposed to the original algorithm proposed by Bazgan et al. [START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF] where a lower bound set is updated for each partial solution in the pool (see condition D3 in Section 2.2), the supported solutions need only to be computed once in a pre-processing step. However, this implies that an NP-hard problem has to be solved for each weighted sum problem. In the implementation used in this study, the code of Pisinger [START_REF] Pisinger | A minimal algorithm for the 0-1 knapsack problem[END_REF] was adapted to solve each weighted sum problem. Preliminary computational results on a wide benchmark set of problems indicated that this implementation is very fast in practice.

Variant BKP-DP2

Variant BKP-DP2 also computes a lower bound set as variant BKP-DP1, but avoids the drawback of solving an NP-hard problem as described in the previous section. This is performed by solving the relaxation of the bi-objective {0, 1} knapsack problem with a simplex algorithm and restoring the feasibility of the relaxed solutions. The simplex algorithm described as follows computes all the nondominated extreme vectors as well as efficient solutions of the bi-objective problem. Hence, it is a more complete version of the algorithm presented in Gomes da Silva et al. [START_REF] Gomes Da Silva | A scatter search method for bi-criteria {0, 1}-knapsack problems[END_REF] that was used to compute only some extreme non-dominated vectors. The continuous 0 -1 bi-objective knapsack problem can be formalized as follows (see Section 1 for the notation and Eq. ( 1) for the discrete variant):

max f (x) = f 1 (x), f 2 (x) subject to: w T x W, x ∈ [0, 1] n (4)
The simplex algorithm computes the set of all nondominated vectors of problem [START_REF] Captivo | Solving bicriteria 0-1 knapsack problems using a labeling algorithm[END_REF]. It start from one lexicographically-optimal solution. Then, it proceeds with an efficient pivoting process until an efficient solution of optimal value for objective f 2 is obtained. In order to obtain the lexicographicallyoptimal solution, the objects are sorted in non-increasing order of the profit-to-weight ratio v 1 k /w k . In case of ties, the objects with the same profit-to-weight ratio are sorted in non-increasing order of the profit-to-weight ratio for v 2 k /w k . Remark 3.1 If two objects j and have the same profit-to-ratio on the first and the second objective, then consider only one object of weights w j + w and of profit (v

1 j + v 1 , v 2 j + v 2
). The lexicographical-optimal solution x * is obtained by using a greedy procedure that includes sorted objects until the capacity is achieved. Let c = min j : j k=1 w j > W be the critical object; then x * = (x * 1 , . . . , x * n ) is such that:

x * j =            1 for j = 1, . . . , c -1, W - c-1 k=1
w k /w c , for j = c, 0 for j = c + 1, . . . , n.

Given that x * c is not equal to zero (that case will be considered later on), it constitutes an efficient basic variable. Note that an efficient basis is constituted by only one efficient basic variable. The algorithm uses a pivoting procedure that ensures the transition from one efficient solution to an adjacent one that decreases the value on the first objective. This procedure, which starts with solution x * and one of its associated efficient basis {x * c }, is described as follows for the general case considering an efficient solution x and one of its associated efficient basis {x c }.

1. Given that variable x c is basic, compute the reduced costs associated to variable x j on the objective i that is V i (c,j) = v i j -v i c • w j /w c , i = 1, 2 and j = 1, . . . , n. The indexes of candidates variables to enter the basis are:

J = j ∈ {1, . . . , n} \ c such that: V 1 (c,j) < 0 and V 2 (c,j) > 0, if x j = 0 V 1 (c,j) > 0 and V 2 (c,j) < 0, if x j = 1
If J is an empty set, the algorithm terminates since it is not possible to increase the value of solution x on the second objective. Hence, x is an efficient solution that is optimal for the second objective. Otherwise, the algorithm proceeds with an efficient pivoting between x c and variable x j * (j * ∈ J), which provides a new efficient solutions such that the slope of the line through this new solution and the previous solution x is the smallest. Then, j * is such that

V 2 (c,j * ) V 1 (c,j * ) = min j∈J V 2 (c,j) V 1 (c,j)
Remark 3.2 Since the objects of the same profit-to-weight ratio for all j ∈ {1, . . . , n} \ c were added, it does not hold that V 1 (c,j) = 0 and V 2 (c,j) = 0. Remark 3.3 However, it is possible to obtain variables such that V 1 (c,j) = 0 and V 2 (c,j) < 0 or V 1 (c,j) < 0 and V 2 (c,j) = 0, for x j = 0, as well as variables such that V 1 (c,j) = 0 and V 2 (c,j) > 0 or V 1 (c,j) > 0 and V 2 (c,j) = 0, for x j = 1. Note that these variables are not candidate to enter the basis since they cannot lead to an efficient pivoting and to a new efficient solution.

Remark 3.4 Index j * is the index in J that maximizes the value of -V 2 (c,j) / V 1 (c,j) -V 2 (c,j)
2. Let δ = w c /w j . The values of variables x c and x j are updated as follows.

if

x j = 0                                    if δx c < 1      x j := δx c x c := 0 x j enters the basis in substitution of x c if δx c > 1      x j := 1 x c := x c -δ x c remains in the basis if δx c = 1      x j := 1 x c := 0
The solution is integer

if x j = 1                                    if δ(1 -x c ) < 1      x j := 1 -δ(1 -x c ) x c := 1 x j enters the basis in substitution of x c if δ(1 -x c ) > 1      x j := 0 x c := x c + δ x c remains in the basis if δ(1 -x c ) = 1      x j := 0 x c := 1
The solution is integer

The final solution is efficient. The pivoting process is repeated with the new basic solution. In case of degeneration, i.e., when we obtain an integer solution, the pivoting procedure is slightly different. We consider all possible increasing pivots between x i and x j for i = 1, . . . , n and j = i + 1, . . . , n satisfying that

V 1 i,j > 0 and V 2 i,j < 0, if x i = 0 and x j = 1 V 1 i,j < 0 and V 2 i,j > 0, if x i = 1 and x j = 0 (5)
Among all these possible pivots satisfying [START_REF] Cormen | Introduction to Algorithms[END_REF], the algorithm pivots between x c and x j * such that

V 2 (c,j * ) V 1 (c,j * ) = min V 2 (c,j) V 1 (c,j)
Hence, the algorithm updates the values of x c and x j * using step 2 described above.

The computation of all the extreme nondominated vectors in the objective space defines an upper bound set for N D(Y ). From these extreme points, a set of feasible vectors can be obtained and used as a pool of solutions for the dynamic programming approach. The improved method to restore feasibility is the one presented by Gomes da Silva et al. [START_REF] Gomes Da Silva | A scatter search method for bi-criteria {0, 1}-knapsack problems[END_REF], the improvement method for the scatter search algorithm. For each solution obtained by the simplex method described above, this repair method iteratively removes the objects with the lowest profit-to-weight ratio to each objective, until feasibility is achieved. Then, at each feasible solution, objects are inserted according to the nonincreasing order of the profit-to-weight ratio for each objective. The final set of solutions become a lower bound set for the original bi-objective problem. Let B denote the set of vectors returned by the procedure above. The condition (D3) as given in Section 2.2 becomes as follows: At a stage k = 1, . . . , n, a state s ∈ T k is removed if there exists a vector s ∈ B such that s∆u(s). Similarly to the procedure described in Section 3.1, set B is computed in a pre-processing step.

- 6 s v 6 - f 1 f 2 v v v u 2 (s) u 3 (s) u 1 (s) A B C - 6 s v 6 - f 1 f 2 v v v u 2 (s) u 1 (s) A B C v v

Variant BKP-DP3

Variant BKP-DP3 follows the same principle of variant BKP-DP1 but the upper bound is computed in a different manner at a later stage. The main idea is to provide a tighter upper bound. At stage k, several solutions for a reduced {0, 1} knapsack problem with the remaining n -k objects that were not yet considered in the chosen partial solution are computed. In particular, two solutions are optimal for each objective of the reduced problem and the remaining ones are optimal for several weighted sum scalarized problems, by varying the weight parameters, or by using dichotomic search (see Section 3.1).

Then, the profits of these solutions are summed up to the state s ∈ T k , which provides several upper bounds. In the following, we consider only one optimal solution for the weighted sum scalarized problem with equal weights. We will denote by u 1 (s) := (u 1 1 , u 1 2 ) and u 2 (s) := (u 2 1 , u 2 2 ), the bounds that were obtained from optimal solutions for f 1 and f 2 , respectively, and by u 3 (s) := (u 3 1 , u 3 2 ), the bound obtained from the scalarized problem with equal weights. The three upper bounds described above define two regions of interest in the objective space, denoted by A, which is delimited by u 1 (s), u 3 (s) and (u 3 1 -u 1 2 + u 3 2 , u 1 2 ), and B, which is delimited by u 2 (s), u 3 (s) and (u 2 1 , u 3 2 -u 2 1 + u 3 1 ). See left-hand-side plot of Figure 2. Note that A and B identify regions where upper bounds can still be found for a scalarized problem with a different combination of weights. However, region f 1 -u 3 1 + f 2 -u 3 2 > 0, denoted by C in the left plot of Figure 2, cannot have an upper bound by the optimality definition of u 3 (s). Note that, since there may be alternative optima for the scalarized problem, one should not expect that the regions A and B are connected, as shown in the right-hand-side plot of Figure 2. The removal, or not, of states in T k works as follows. For a given state s ∈ T k and the sequence 1 , . . . , m of m lower bounds generated as in variant BKP-DP1, sorted in increasing order of f 1 (and decreasing order of f 2 ), consider a monotone rectilinear polyline L that connects the points in this sequence. See the straight line in Figure 3. The state s can only be discarded if L and either region A or B do not intersect. If they intersect at any place, then s cannot be discarded. Figure 3 illustrates the latter case. The detection of whether L intersects a triangular region is performed by a classical technique of segment-segment intersection [START_REF] Cormen | Introduction to Algorithms[END_REF]. For efficient queries, balanced binary trees were used to implement both bound sequences. The experiments were performed in a computer cluster with 6 nodes, each with an AMD Phenom II X6 processor with 3.2GHz, 3 and 6 MB L2 and L3 Cache, respectively, and 12 GB DDR3 SDRAM. All implementations were written in C++ and shared the same data structures. The operating system was Ubuntu 8.04 LTS. All codes were compiled with g++ version 4.2.4 using the -O3 flag. The bi-objective {0, 1} knapsack instances were the same as described by Bazgan et al. [START_REF] Bazgan | Solving efficiently the 0-1 multi-objective knapsack problem[END_REF]. Each weight and profit value of each instance is generated randomly according to an uniform distribution in a given range. Different ranges induces different structure on the input data that may affect algorithm performance. The instances considered are as follows:

• Type A (random instances) with weights and profits uniformly random generated in the range [START_REF] Aneja | Bicriteria transportation problem[END_REF]1000].

• Type B (unconflicting instances) with profits v 1 j and v 2 j of each object j in the range [111, 1000] and [v 1 j -100, v 1 j + 100], respectively; this induces a positive correlation between profits of an object; the weights are in the range 1000].

• Type C (conflicting instances) with the profit v 1 j and weight w j of each object j in the range [START_REF] Aneja | Bicriteria transportation problem[END_REF]1000]; the profit v 2 j is in the range [max{900 -v 1 j , 1}, min{1100 -v 1 j , 1000}], which induces a negative correlation between profits of an object.

• Type D (conflicting instances with correlated weights) Similar to Type C instances, but the weights are in the range [v 1 j + v 2 j -200, v 1 j + v 2 j + 200], which induces a positive correlation between the weight and the two profits of an object.

For every instance, the capacity W is half of the total sum of weight values. Variant BKP-DP3 follows the same principle of variant BKP-DP1 until a given stage i. From this stage on, the algorithm computes an upper bound set of three solutions per state, as mentioned in Section 3.3. We considered i = 0.05 • n, 0.08 • n and 0.1 • n; we denote the corresponding variants by BKP-DP3 .05 , BKP-DP3 .08 and BKP-DP3 .10 , respectively. Preliminary experiments suggest that variant BKP-DP3 takes a large amount of time, if the computation of the new bound is performed at an earlier stage.

Results and discussion

Tables 1 and2 presents the CPU-time and maximum number of states maintained in memory by the implementations of the original BKP-DP and the three variants proposed in this article. The values are averaged over each set of instances of the same type and size. The underlined values are the best for each type and instance size.

The experimental results indicate that variants BKP-DP1 and BKP-DP2 are able to reach an average of 20% improvement of CPU-time with respect to performance of BKP-DP as well as lower maximum number of states. Moreover, in most instances of type B, BKP-DP1 performs relatively faster than BKP-DP2. This fact seems to be related to the lower maximum number of states that are kept by BKP-DP1. However, in the remaining type of instances, the running time of BKP-DP1 and BKP-DP2 is very similar. Except for instances of type B, BKP-DP1 keeps the lowest maximum number of states.

In general, variants BKP-DP3 take more time to terminate than variants BKP-DP1 and BKP-DP2, and even more time than BKP-DP on large instances of type A and C. The results also indicate that it is preferable to start the computation of the upper bound set in BKP-DP3 as latter as possible, which means that the time spent on computing a more precise upper bound does not pay-off the pruning. Still, the time spent by the best performing variant BKP-DP3 is always performing better than the original approach.

Conclusions

In this paper we presented some methodological and computational improvements for the state of the art implementation of dynamic programming based algorithms for bi-objective 0, 1-knapsack problems.

In general, all the proposed variants improved the baseline implementation, and the most performant ones led to an important gain in terms of CPU time and memory requirements, mainly in large instances; on average about 20% less time consuming and 15% less memory usage than the state of the art implementation. This shows that the classical and improved version of dynamic programming

Figure 1 :

 1 Figure 1: Illustration of condition (D3).

Figure 2 :

 2 Figure 2: Illustration of upper bounds in BKP-DP3.

Figure 3 :

 3 Figure 3: Illustration of a case in which state s is not discarded in BKP-DP3.

Table 1 :

 1 Average CPU-time of several approaches for the benchmark set of instances.

	Type	n	|N D(Y )|	BKP-DP	BKP-DP1	BKP-DP2	BKP-DP3.05	BKP-DP3.08	BKP-DP3.10
	A 100	159.3	0.5	0.4	0.4	0.4	0.5	0.5
		200	529.0	26.6	19.7	19.8	21.4	20.7	20.3
		300	1 130.7	204.9	155.3	155.2	163.1	159.4	159.1
		400	1 713.3	835.9	603.5	600.9	630.4	617.2	627.6 16 907.0
	B 600	74.3	2.2	1.6	2.0	1.7	1.7	1.7
		700	78.6	3.6	2.6	3.2	2.7	2.7	2.7
		800	118.1	8.7	6.8	8.0	6.9	6.9	7.1
		900	124.4	11.0	8.7	10.6	8.8	9.1	9.3
		1 000	157.0	19.4	15.0	17.6	16.0	16.4	16.5
		2 000	477.7	624.5	487.5	514.9	493.9	502.3	510.6

Acknowledgment J.R. Figueira, L. Paquete and D. Vanderpooten acknowledge the financial support from the Luso-French bilateral cooperation agreement between CEG-IST (FCT/CNRS 2009) and LAMSADE. J.R. Figueira and M. Simões acknowledge a CEG-IST grant from Instituto Superior Técnico (PTDC/GES/73853/2006). D. Vanderpooten acknowledges the support by the project ANR-09-BLAN-0361 "GUaranteed Efficiency for PAReto optimal solutions Determination (GUEPARD)".

algorithms can be improved with the insertion of non-classical techniques for improving the bound sets on the set of non-dominated solutions for the bi-objective case even for the most difficult instances available in the literature. More variants and combination of variants can be done in future research. One promising line of future research is the one related to variant BKP-DP3 and the computation of more than three solutions for deriving a bound. Another avenue for future research is to use the concept of bi-objective core and the heuristic associated with it to compute a good pool of initial solutions [START_REF] Gomes Da Silva | Core problems in bi-criteria 0,1-knapsack problems[END_REF].


Pavel Tokmakov

Karteek Alahari Inria

Cordelia Schmid

Learning Motion Patterns in Videos

The problem of determining whether an object is in motion, irrespective of camera motion, is far from being solved. We address this challenging task by learning motion patterns in videos. The core of our approach is a fully convolutional network, which is learned entirely from synthetic video sequences, and their ground-truth optical flow and motion segmentation. This encoder-decoder style architecture first learns a coarse representation of the optical flow field features, and then refines it iteratively to produce motion labels at the original high-resolution. We further improve this labeling with an objectness map and a conditional random field, to account for errors in optical flow, and also to focus on moving "things" rather than "stuff". The output label of each pixel denotes whether it has undergone independent motion, i.e., irrespective of camera motion. We demonstrate the benefits of this learning framework on the moving object segmentation task, where the goal is to segment all objects in motion. Our approach outperforms the top method on the recently released DAVIS benchmark dataset, comprising real-world sequences, by 5.6%. We also evaluate on the Berkeley motion segmentation database, achieving state-of-the-art results.

Introduction

The task of analyzing motion patterns has a long history in computer vision [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF][START_REF] Dosovitskiy | FlowNet: Learning optical flow with convolutional networks[END_REF][START_REF] Horn | Determining optical flow[END_REF][START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF][START_REF] Torr | Geometric motion segmentation and model selection[END_REF][START_REF] Vedula | Three-dimensional scene flow[END_REF][START_REF] Xu | LIBSVX: A supervoxel library and benchmark for early video processing[END_REF]. This includes methods for motion estimation [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF][START_REF] Torr | Geometric motion segmentation and model selection[END_REF], scene [START_REF] Vedula | Three-dimensional scene flow[END_REF] and optical [START_REF] Dosovitskiy | FlowNet: Learning optical flow with convolutional networks[END_REF][START_REF] Horn | Determining optical flow[END_REF] flow computation, video segmentation [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF][START_REF] Xu | LIBSVX: A supervoxel library and benchmark for early video processing[END_REF]; all of which aim to estimate or capitalize on motion cues in scenes. Despite this progress, the fundamental problem of identifying if an object is indeed moving, irrespective of camera motion, remains challenging. In this paper, we make significant advances to address this challenge, with a novel CNN-based framework to automatically learn motion patterns in videos, and use it to segment moving objects; see sample results in Figure 1.

To illustrate the task, consider Figure 2, a sequence from the FlyingThings3D dataset [START_REF] Mayer | A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation[END_REF]. It depicts a scene generated synthetically, involving a moving camera (can be easily observed by comparing the top left corners of the images (a) Figure 1. Results on the DAVIS dataset. Left: Optical flow field input to our MP-Net, computed with [START_REF] Brox | Large displacement optical flow: descriptor matching in variational motion estimation[END_REF]. Right: Our segmentation result overlaid on the video frame. Note that our approach accurately segments moving objects, and learns to distinguish between object and camera motions (seen in the flow fields). and (b)), with objects in motion, e.g., the three large objects in the centre of the frame (which are easier to spot in the ground-truth segmentation (d)). The goal of our work is to study such motion patterns in video sequences (using optical flow field (c)), and to learn to distinguish real motion of objects from camera motion. In other words, we target the moving object segmentation in (d).

The core of our approach is a trainable model, motion pattern network (MP-Net), for separating independent object and camera motion, which takes optical flow as input and outputs a per-pixel score for moving objects. Inspired by fully convolutional networks (FCNs) [START_REF] Dosovitskiy | FlowNet: Learning optical flow with convolutional networks[END_REF][START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF][START_REF] Ronneberger | U-Net: Convolutional networks for biomedical image segmentation[END_REF], we propose a related encoder-decoder style architecture to accomplish this two-label classification task. The network is trained from scratch with synthetic data [START_REF] Mayer | A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation[END_REF]. Pixel-level ground-truth labels for training are generated automatically (see Figure 2(d)), and denote whether each pixel has moved in the scene. The input to the network is flow fields, such as the one shown in Figure 2(c). More details of the network, and how it is trained are provided in Section 3. With this training, our model learns to distinguish motion patterns of objects and background. We then refine these labels with objectness cues [START_REF] Pinheiro | Learning to refine object segments[END_REF] and a conditional random field (CRF) model [START_REF] Krähenbühl | Efficient inference in fully connected CRFs with gaussian edge potentials[END_REF] (see §4), to demonstrate the efficacy of the entire framework on the moving object segmentation task (see §6). These refinement steps are im- portant to account for errors in flow fields, and also to target moving objects, instead of stuff such as moving water.

We evaluate on the densely annotated video segmentation (DAVIS) [START_REF] Perazzi | A benchmark dataset and evaluation methodology for video object segmentation[END_REF] and the Freiburg/Berkeley motion segmentation datasets (BMS-26, FBMS) [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF][START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF][START_REF] Ochs | Segmentation of moving objects by long term video analysis[END_REF][START_REF] Tron | A benchmark for the comparison of 3-D motion segmentation algorithms[END_REF], all comprising real-data sequences. We obtain state-of-the-art results on these challenging datasets. In particular, we outperform previous video-level methods by over 5.6%, on the intersection over union score, on DAVIS, despite operating only on the frame level. We have made the source code and the trained models available online. 1

Related Work

Our work is related to the following tasks dealing with motion cues: motion and scene flow estimation, and video object segmentation. We will review the most relevant work on these topics, in addition to a review of related CNN architectures in the remainder of this section.

Motion estimation.

Early attempts for estimating motion have focused on geometry-based approaches, such as [START_REF] Torr | Geometric motion segmentation and model selection[END_REF], where the potential set of motions is identified with RANSAC. Recent approaches have relied on other cues to estimate moving object regions. For example, Papzouglou and Ferrari [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] first extract motion boundaries by measuring changes in optical flow field, and use it to estimate moving regions. They also refine this initial estimate iteratively with appearance features. This approach produces interesting results, but is limited by its heuristic initialization. We show that incorporating our learning-based motion estimation into it improves the results significantly (see Table 4).

Narayana et al. [START_REF] Narayana | Coherent motion segmentation in moving camera videos using optical flow orientations[END_REF] use optical flow orientations in a probabilistic model to assign pixels with labels that are consistent with their respective real-world motion. This approach assumes pure translational camera motion, and is prone to errors when the object and camera motions are consistent with each other. Bideau et al. [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF] presented an alternative to this, where initial estimates of foreground and background motion models are updated over time, with optical flow orientations of the new frames. This initialization is also heuristic, and lacks a robust learning framework. While we also set out with the goal of finding objects in motion, our solution to this problem is a novel 1 http://thoth.inrialpes.fr/research/mpnet learning-based method. Scene flow, i.e., 3D motion field in a scene [START_REF] Vedula | Three-dimensional scene flow[END_REF], is another form of motion estimation, but is computed with additional information, such as disparity values computed from stereo images [START_REF] Huguet | A variational method for scene flow estimation from stereo sequences[END_REF][START_REF] Wedel | Stereoscopic scene flow computation for 3D motion understanding[END_REF], or estimated 3D scene models [START_REF] Vogel | 3D scene flow estimation with a piecewise rigid scene model[END_REF]. None of these methods follows a CNN-based learning approach, in contrast to our MP-Net.

Video object segmentation. The task of segmenting objects in video is to associate pixels belonging to a class spatio-temporally; in other words, extract segments that respect object boundaries, as well as associate object pixels temporally whenever they appear in the video. This can be accomplished by propagating manual segment labels in one or more frames to the rest of the video sequence [START_REF] Badrinarayanan | Label propagation in video sequences[END_REF]. This class of methods is not applicable to our scenario, where no manual segmentation is available.

Our approach to solve the segmentation problem does not require any manually-marked regions. Several methods in this paradigm generate an over-segmentation of videos [START_REF] Brendel | Video object segmentation by tracking regions[END_REF]12,[START_REF] Khoreva | Classifier based graph construction for video segmentation[END_REF][START_REF] Lezama | Track to the future: Spatio-temporal video segmentation with long-range motion cues[END_REF][START_REF] Xu | LIBSVX: A supervoxel library and benchmark for early video processing[END_REF]. While this can be a useful intermediate step for some recognition tasks in video, it has no notion of objects. Indeed, most of the extracted segments in this case do not directly correspond to objects, making it non-trivial to obtain video object segmentation from this intermediate result. An alternative to this is motion segmentation [START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF][START_REF] Fragkiadaki | Video segmentation by tracing discontinuities in a trajectory embedding[END_REF][START_REF] Ochs | Higher order motion models and spectral clustering[END_REF], which produces more coherent regions with point trajectories. They, however, assume homogeneity of motion over the entire object, which is not valid for nonrigid objects.

Another class of segmentation methods cast the problem as a foreground-background classification task [START_REF] Faktor | Video segmentation by non-local consensus voting[END_REF][START_REF] Lee | Key-segments for video object segmentation[END_REF][START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF][START_REF] Taylor | Causal video object segmentation from persistence of occlusions[END_REF][START_REF] Wang | Saliency-aware geodesic video object segmentation[END_REF][START_REF] Zhang | Video object segmentation through spatially accurate and temporally dense extraction of primary object regions[END_REF]. Some of these first estimate a region [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF][START_REF] Wang | Saliency-aware geodesic video object segmentation[END_REF] or regions [START_REF] Lee | Key-segments for video object segmentation[END_REF][START_REF] Zhang | Video object segmentation through spatially accurate and temporally dense extraction of primary object regions[END_REF], which potentially correspond(s) to the foreground object, and then learn foreground/background appearance models. The learned models are then integrated with other cues, e.g., saliency maps [START_REF] Wang | Saliency-aware geodesic video object segmentation[END_REF], pairwise constraints [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF][START_REF] Zhang | Video object segmentation through spatially accurate and temporally dense extraction of primary object regions[END_REF], object shape estimates [START_REF] Lee | Key-segments for video object segmentation[END_REF], to compute the final object segmentation. Alternatives to this framework have used: (i) long-range interactions between distinct parts of the video to overcome noisy initializations in low-quality videos [START_REF] Faktor | Video segmentation by non-local consensus voting[END_REF], and (ii) occluder/occluded relations to obtain a layered segmentation [START_REF] Taylor | Causal video object segmentation from persistence of occlusions[END_REF]. Our proposed method outperforms all the top ones from this class of segmentation approaches (see §6). Related CNN architectures. Our CNN model predicts labels for every pixel, similar to CNNs for other tasks, such as semantic segmentation [13,[START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF][START_REF] Ronneberger | U-Net: Convolutional networks for biomedical image segmentation[END_REF], optical flow [START_REF] Dosovitskiy | FlowNet: Learning optical flow with convolutional networks[END_REF] and disparity/depth [START_REF] Mayer | A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation[END_REF] estimation. We adopt an encoder-decoder style network, inspired by the success of similar architectures in [START_REF] Dosovitskiy | FlowNet: Learning optical flow with convolutional networks[END_REF][START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF][START_REF] Ronneberger | U-Net: Convolutional networks for biomedical image segmentation[END_REF]. They first learn a coarse representation with receptive fields of gradually increasing sizes, and then iteratively refine it with upconvolutional layers, i.e., by upsampling the feature maps and performing convolutions, to obtain an output at the original high-resolution. In contrast to [START_REF] Dosovitskiy | FlowNet: Learning optical flow with convolutional networks[END_REF][START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF], which predict labels in each of the upconvolutional layers, we concatenate features computed at different resolutions to form a strong representation, and estimate the labels in the last layer. Our architecture also has fewer channels in the layers in the encoding part, compared to [START_REF] Ronneberger | U-Net: Convolutional networks for biomedical image segmentation[END_REF], to accommodate larger training-set batches, and thus decrease the training time. More details of our architecture are presented in Section 3.1.

Learning Motion Patterns

Our MP-Net takes the optical flow field corresponding to two consecutive frames of a video sequence as input, and produces per-pixel motion labels. In other words, we treat each video as a sequence of frame pairs, and compute the labels independently for each pair. As shown in Figure 3, the network comprises several "encoding" (convolutional and max-pooling) and "decoding" (upsampling and convolutional) layers. The motion labels are produced by the last layer of the network, which are then rescaled to the original image resolution (see §3.1). We train the network entirely on synthetic data-a scenario where ground-truth motion labels can be acquired easily (see §3.2).

Network architecture

Our encoder-decoder style network is motivated by the goal of segmenting diverse motion patterns in flow fields, which requires a large receptive field as well as an output at the original image resolution. A large receptive field is critical to incorporate context into the model. For example, when the spatial region of support (for performing convolution) provided by a small receptive field falls entirely within an object with non-zero flow values, it is impossible to determine whether it is due to object or camera motion. On the other hand, a larger receptive field will include regions corresponding to the object as well as background, providing sufficient context to determine what is moving in the scene. The second requirement of output generated at the original image resolution is to capture fine details of objects, e.g., when only a part of the object is moving. Our network satisfies these two requirements with: (i) the encoder part learning features with receptive fields of increasing sizes, and (ii) the decoder part upsampling the intermediate layer outputs to finally predict labels at the full resolution.

Figure 3 illustrates our network architecture. Optical flow field input is processed by the encoding part of the network (denoted by (a) in the figure) to generate a coarse representation that is a 32 × 32 downsampled version of the input. Each 3D block here represents a feature map produced by a set of layers. In the encoding part, each feature map is a result of applying convolutions, followed by a ReLU non-linearity layer, and then a 2 × 2 max-pooling layer. The coarse representation learned by the final set of operations in this part, i.e., the 32 × 32 downsampled version, is gradually upsampled by the decoder part ((b) in the figure). In each decoder step, we first upsample the output of the previous step by 2 × 2, and concatenate it with the corresponding intermediate encoded representation, before max-pooling (illustrated with black arrows pointing down in the figure). This upscaled feature map is then processed with two convolutional layers, followed by non-linearities, to produce input for the next (higher-resolution) decoding step. The final decoder step produces a motion label map at half the original resolution. We perform a bilinear interpolation on this result to estimate labels at the original resolution.

Training with synthetic data

We need a large number of fully-labelled examples to train a convolutional network such as the one we propose. In our case, this data corresponds to videos of several types of objects, captured under different conditions (e.g., moving or still camera), with their respective moving object annota- tions. No large dataset of real-world scenes satisfying these requirements is currently available, predominantly due to the cost of generating ground-truth annotations and flow for every frame. We adopt the popular approach of using synthetic datasets, followed in other work [START_REF] Dosovitskiy | FlowNet: Learning optical flow with convolutional networks[END_REF][START_REF] Gaidon | Virtual worlds as proxy for multi-object tracking analysis[END_REF][START_REF] Mayer | A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation[END_REF]. Specifically, we use the FlyingThings3D dataset [START_REF] Mayer | A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation[END_REF] containing 2250 video sequences of several objects in motion, with ground-truth optical flow. We augment this dataset with ground-truth moving object labels, which are accurately estimated using the disparity values and camera parameters available in the dataset, as outlined in Section 5. See We train the network with mini-batch SGD under several settings. The one trained with ground-truth optical flow as input shows the best performance. This is analyzed in detail in Section 6.2. Note that, while we use ground-truth flow for training and evaluating the network on synthetic datasets, all our results on real-world test data use only the estimated optical flow. After convergence of the training procedure, we obtain a learned model for motion patterns.

Our approach capitalizes on the recent success of CNNs for pixel-level labelling tasks, such as semantic image segmentation, which learn feature representations at multiple scales in the RGB space. The key to their top performance is the ability to capture local patterns in images. Various types of object and camera motions also produce consistent local patterns in the flow field, which our model is able to learn to recognize. This gives us a clear advantage over other pixellevel motion estimation techniques [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF][START_REF] Narayana | Coherent motion segmentation in moving camera videos using optical flow orientations[END_REF] that can not detect local patterns. Motion boundary based heuristics used in [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] can be seen as one particular type of pattern, representing independent object motion. Our model is able to learn many such patterns, which greatly improves the quality and robustness of motion estimation.

Detecting Motion Patterns

We apply our trained model on synthetic (FlyingTh-ings3D) as well as real-world (DAVIS, BMS-26, FBMS) test data. Figure 4 shows sample predictions of our model on the FlyingThings3D test set with ground-truth optical flow as input. Examples in the first two rows show that our model accurately identifies fine details in objects: thin structures even when they move subtlely, such as the neck of the guitar in the top-right corner in the first row (see the subtle motion in the optical flow field (b)), fine structures like leaves in the vase, and the guitar's headstock in the second row. Furthermore, our method successfully handles objects exhibiting highly varying motions in the second example. The third row shows a limiting case, where the receptive field of our network falls entirely within the interior of a large object, as the moving object dominates. Traditional approaches, such as RANSAC, do not work in this case either.

In order to detect motion patterns in real-world videos, we first compute optical flow with popular methods [START_REF] Brox | Large displacement optical flow: descriptor matching in variational motion estimation[END_REF][START_REF] Revaud | EpicFlow: Edge-preserving interpolation of correspondences for optical flow[END_REF][START_REF] Sundaram | Dense point trajectories by gpu-accelerated large displacement optical flow[END_REF]. With this flow as input to the network, we estimate a motion label map, as shown in the examples in We address these challenges by: (i) incorporating object proposals [START_REF] Pinheiro | Learning to refine object segments[END_REF] into our framework, and (ii) refining the result with a fully-connected conditional random field (CRF) [START_REF] Krähenbühl | Efficient inference in fully connected CRFs with gaussian edge potentials[END_REF]. The following two sections present these in detail, and their influence is analyzed in Section 6.3.

Segmenting real-world videos

As mentioned in the example above (Figure 5, top row), real-world videos may contain stuff (water in this case) undergoing independent motion. While it is interesting to study this motion, and indeed, our model estimates it (see network prediction (c) in the first row), it is not annotated in any of the standard datasets for moving object segmentation. In order to perform a fair evaluation on standard benchmarks, we introduce the notion of objects, with an objectness score, computed from object proposals, to eliminate "moving stuff." We combine this score with our network output to obtain an updated prediction.

We first generate object proposals in each frame with a state-of-the-art method [START_REF] Pinheiro | Learning to refine object segments[END_REF]. We then use a pixel-level voting scheme to compute an objectness score. The score at a pixel i is the number of proposals that include it. This score is normalized by the total number of proposals to obtain o i , the objectness score at pixel i in the 0 -1 range. In essence, we aggregate several proposals, which are likely to represent objects of interest, to obtain an objectness map, as shown in the examples in Figure 5(d). We then combine this with the motion prediction of our MP-Net at pixel i, m i ∈ [0, 1], to obtain an updated prediction p i as:

p i = min(m i * (k + o i ), 1)
, where k ∈ [0, 1] is a parameter controlling the influence of objectness. It is set to 0.5 to ensure that a high-confidence network prediction m i gets suppressed only when there are no objects proposals supporting it. In the example with the kiteboarder (top row in Figure 5), the objectness map (d) has no object proposals on water, the "moving stuff," and eliminates it, to obtain segmentation (e) that corresponds to the moving object.

Refining the segmentation

As shown on the synthetic test sequences, Figure 4, our model produces accurate object boundaries in several cases. This is in part due to precise optical flow input; recall that we use ground-truth flow for synthetic data. Naturally, computed flow is less accurate than this, and can often fail to provide precise object boundaries (see Figure 5(b)), especially in low-texture regions. Such errors inevitably result in imprecise motion segments. To address this, we follow the common practice of refining segmentation results with a CRF [START_REF] Chen | Semantic image segmentation with deep convolutional nets and fully connected CRFs[END_REF]. We use a fully-connected CRF [START_REF] Krähenbühl | Efficient inference in fully connected CRFs with gaussian edge potentials[END_REF], with our predictions updated with objectness scores as the unary terms, and standard colour-based pairwise terms. The refinement is shown qualitatively in Figure 5(f), which improves over the initial segmentation in (e), e.g., contours of the person pushing the pram in the middle row.

Datasets

FlyingThings3D (FT3D). We train our network with the synthetic FlyingThings3D dataset [START_REF] Mayer | A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation[END_REF]. It contains videos of various objects flying along randomized trajectories, in randomly constructed scenes. The video sequences are generated with complex camera motion, which is also randomized. FT3D comprises 2700 videos, each containing 10 stereo frames. The dataset is split into training and test sets, with 2250 and 450 videos respectively. Ground-truth optical flow, disparity, intrinsic and extrinsic camera parame-ters, and object instance segmentation masks are provided for all the videos. No annotation is directly available to distinguish moving objects from stationary ones, which is required to train our network. We extract this from the data provided as follows. With the given camera parameters and the stereo image pair, we first compute the 3D coordinates of all the pixels in a video frame t. Using ground-truth flow between frames t and t + 1 to find a pair of corresponding pixels, we retrieve their respective 3D scene points. Now, if the pixel has not undergone any independent motion between these two frames, the scene coordinates will be identical (up to small rounding errors). We have made these labels publicly available on our project website. Performance on the test set is measured as the standard intersection over union score between the predicted segmentation and the ground-truth masks. DAVIS. We use the densely annotated video segmentation dataset [START_REF] Perazzi | A benchmark dataset and evaluation methodology for video object segmentation[END_REF] exclusively for evaluating our approach. DAVIS is a very recent dataset containing 50 full HD videos, featuring diverse types of object and camera motion. It includes challenging examples with occlusion, motion blur and appearance changes. Accurate pixel-level annotations are provided for the moving object in all the video frames. Note that only a single object is annotated in each video, even if there are multiple moving objects in the scene. We evaluate our method on DAVIS with the three measures used in [START_REF] Perazzi | A benchmark dataset and evaluation methodology for video object segmentation[END_REF], namely intersection over union for region similarity, F-measure for contour accuracy, and temporal stability for measuring the smoothness of segmentation over time. We follow the protocol in [START_REF] Perazzi | A benchmark dataset and evaluation methodology for video object segmentation[END_REF] and use images downsampled by a factor of two. Other datasets.

We also evaluate on sequences from Berkeley (BMS-26) [START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF][START_REF] Tron | A benchmark for the comparison of 3-D motion segmentation algorithms[END_REF] and Freiburg-Berkeley (FBMS) [START_REF] Ochs | Segmentation of moving objects by long term video analysis[END_REF] motion segmentation datasets. The BMS-26 dataset consists of 26 videos with ground-truth object segmentations for a selection of frames. Observing that annotations in some of these videos do not correspond to objects with independent motion, ten of them were excluded in [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF]. In order to compare with [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF], we follow their experimental protocol, and evaluate on the same subset of BMS-26. FBMS is an extension of BMS- total, and a train and test split of 29 and 30 respectively. We use the test set in this paper. Performance on these two datasets is evaluated with F-measure, as done in [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF][START_REF] Taylor | Causal video object segmentation from persistence of occlusions[END_REF].

Experiments and Results

Implementation details

Training. We use mini-batch SGD with a batch size of 13 images-the maximum possible due to GPU memory constraints. The network is trained from scratch with learning rate set to 0.003, momentum to 0.9, and weight decay to 0.005. Training is done for 27 epochs, and the learning rate and weight decay are decreased by a factor of 0.1 after every 9 epochs. We downsample the original frames of the FT3D training set by a factor 2, and perform data augmentation by random cropping and mirroring. Batch normalization [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] is applied to all the convolutional layers of the network. Other details. We perform zero-mean normalization of the flow field vectors, similar to [START_REF] Simonyan | Two-stream convolutional networks for action recognition in videos[END_REF]. When using flow angle and magnitude together (which we refer to as flow angle field), we scale the magnitude component, to bring the two channels to the same range. We use 100 proposals in each frame to compute the objectness score (see §4.1). Also, for a fair comparison to other methods on DAVIS, we do not learn the parameters of the fully-connected CRF on this dataset, and instead set them to values used for a related pixel-level segmentation task [START_REF] Chen | Semantic image segmentation with deep convolutional nets and fully connected CRFs[END_REF]. Our model is implemented in the Torch framework.

Influence of input modalities

We first analyze the influence of different input modalities on training our network. Specifically, we use RGB data (single frame and image pair), optical flow field (ground truth and estimated one), directly as flow vectors, i.e., flow in x and y axes, or as angle field (flow vector angle concatenated with flow magnitude), and a combination of RGB data and flow. These results are presented on the FT3D test set and also on DAVIS, to study how well the observations on synthetic videos transfer to the real-world ones, in Table 1. For computational reasons we train and test with different modalities on a smaller version of our MP-Net, with one decoder unit instead of four. to train and test the full, deeper version of the network.

From Table 1, the performance on DAVIS is lower than on FT3D. This is expected as there is domain change from synthetic to real data, and that we use ground truth optical flow as input for FT3D test data, but estimated flow [START_REF] Brox | Large displacement optical flow: descriptor matching in variational motion estimation[END_REF][START_REF] Sundaram | Dense point trajectories by gpu-accelerated large displacement optical flow[END_REF] for DAVIS. As a baseline, we train on single RGB frames ('RGB single frame' in the table). Clearly, no motion patterns can be learned in this case, but the network performs reasonably on FT3D test (68.1), as it learns to correlate object appearance with its motion. This intuition is confirmed by the fact that 'RGB single frame' fails on DAVIS (12.7), where the appearance of objects and background is significantly different from FT3D. MP-Net trained on 'RGB pair', i.e., RGB data of two consecutive frames concatenated, performs slightly better on both FT3D (69.1) and DAVIS (16.6), suggesting that it captures some motion-like information, but continues to rely on appearance, as it does not transfer well to DAVIS.

Training on ground-truth flow vectors corresponding to the image pair ('GT flow') improves the performance on FT3D by 5.4% and on DAVIS significantly (27.7%). This shows that MP-Net learned on flow from synthetic examples can be transferred to real-world videos. We then experiment with flow angle as part of the input. As discussed in [START_REF] Narayana | Coherent motion segmentation in moving camera videos using optical flow orientations[END_REF], flow orientations are independent of depth from the camera, unlike flow vectors, when the camera is undergoing only translational motion. Using the ground truth flow angle field (concatenation of flow angles and magnitudes) as input ('GT angle field'), we note a slight decrease in IoU score on FT3D (1.4%), where strong camera rotations are abundant, but in real examples, such motion is usually mild. Hence, 'GT angle field' improves IoU on DAVIS by 2.3%. We use angle field representation in all further experiments.

Using a concatenated flow and RGB representation ('RGB + GT angle field') performs better on FT3D (by 1.7%), but is poorer by 7% on DAVIS, re-confirming our observation that appearance features are not consistent between the two datasets. Finally, training on computed flow [START_REF] Brox | Large displacement optical flow: descriptor matching in variational motion estimation[END_REF] ('LDOF angle field') leads to significant drop on both the datasets: 9.9% on FT3D (with GT flow for testing) and 8.5% on DAVIS, showing the importance of highquality training data for learning accurate models. The full version of our MP-Net, with 4 decoder units, improves the Measure NLC [START_REF] Faktor | Video segmentation by non-local consensus voting[END_REF] CVOS [START_REF] Taylor | Causal video object segmentation from persistence of occlusions[END_REF] TRC [START_REF] Fragkiadaki | Video segmentation by tracing discontinuities in a trajectory embedding[END_REF] MSG [START_REF] Brox | Object segmentation by long term analysis of point trajectories[END_REF] KEY [START_REF] Lee | Key-segments for video object segmentation[END_REF] SAL [START_REF] Wang | Saliency-aware geodesic video object segmentation[END_REF] FST [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] PCM [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF] Table 3. Comparison to state-of-the-art methods on DAVIS with intersection over union (J ), F-measure (F), and temporal stability (T ).

Ground truth

Optical flow [START_REF] Brox | Large displacement optical flow: descriptor matching in variational motion estimation[END_REF] FST [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] NLC [START_REF] Faktor | Video segmentation by non-local consensus voting[END_REF] Ours Figure 6. Qualitative comparison with top-performing methods on DAVIS. Left to right: ground truth, optical flow [START_REF] Brox | Large displacement optical flow: descriptor matching in variational motion estimation[END_REF], results of FST [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF], NLC [START_REF] Faktor | Video segmentation by non-local consensus voting[END_REF], and our approach. The last row shows a failure case of our approach, i.e., a part of the motorbike is missing.

IoU by 12.8% on FT3D and 5.8% on DAVIS over its shallower one-unit equivalent.

Notice that the performance of our full model on FT3D is excellent, with the remaining errors mostly due to inherently ambiguous cases like objects moving close to the camera (see third row in Figure 4), or very strong object/camera motion. On DAVIS the results are considerably lower despite less challenging motion. To investigate the extent to which this is due to errors in flow estimation, we compute LDOF [START_REF] Brox | Large displacement optical flow: descriptor matching in variational motion estimation[END_REF] flow on the FT3D test set and evaluate our full model trained on ground-truth flow. We observe a significant drop in performance by 27.2% (from 85.9% to 58.7%). This confirms the impact of optical flow quality and suggests that improvements in flow estimation can increase the performance of our method on real-world videos.

Evaluation on real videos

We show the performance of our MP-Net on DAVIS in Table 2, along with a study on the influence of additional cues and the flow used. First, we evaluate the importance of the estimated flow quality by comparing EpicFlow [START_REF] Revaud | EpicFlow: Edge-preserving interpolation of correspondences for optical flow[END_REF], a recent method, and LDOF [START_REF] Brox | Large displacement optical flow: descriptor matching in variational motion estimation[END_REF][START_REF] Sundaram | Dense point trajectories by gpu-accelerated large displacement optical flow[END_REF], a more classical method. Using EpicFlow, which leverages motion contours, produces more accurate object boundaries, and improves over MP-Net using LDOF by 4.5%. Incorporating objectness cues with our network ('MP-Net + Objectness' in the table), as described in Section 4.1 improves the segmentation results over 'MP-Net' by 10.9% and 7.6% with LDOF and EpicFlow respectively. Refining these segmentation results with a fully-connected CRF ('MP-Net + Objectness + CRF'), as in Section 4.2, further improves the IoU by 6.4% and 3.5% with LDOF and EpicFlow respectively. This refinement has a significant impact when using LDOF flow, as it improves segmentation around object boundaries, as shown in Figure 5. On the other hand, EpicFlow already incorporates motion boundaries, and a CRF refinement on top of the results with this flow has a less-pronounced improvement. The overall method 'MP-Net + Objectness + CRF' performs better with LDOF (69.7) than EpicFlow (68.0). Although EpicFlow has better precision than LDOF around object boundaries, it tends to make larger errors in other regions, which cannot be corrected with CRF refinement. We thus use LDOF in the following experiments.

Comparison to the state of the art

Table 3 shows comparison with unsupervised state-ofthe-art methods on DAVIS. In addition to comparing with the methods reported in [START_REF] Perazzi | A benchmark dataset and evaluation methodology for video object segmentation[END_REF], we evaluate PCM [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF], the top-performer on BMS-26, with source code provided by the authors. Note that methods which use supervision on DAVIS test sequences (e.g., annotation in the first frame) do perform better, but are not directly comparable to our method. Our frame-level approach 'MP-Net + Objectness + CRF' (Ours) outperforms all the methods significantly, notably by 5.6% on IoU (mean-J ) and 7% on F-measure (mean-F) over the best one in the evaluation [START_REF] Perazzi | A benchmark dataset and evaluation methodology for video object segmentation[END_REF], i.e., Measure CUT [START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF] FST [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] TRC [START_REF] Fragkiadaki | Video segmentation by tracing discontinuities in a trajectory embedding[END_REF] MTM [START_REF] Zamalieva | A multitransformational model for background subtraction with moving cameras[END_REF] CMS [START_REF] Narayana | Coherent motion segmentation in moving camera videos using optical flow orientations[END_REF] PCM [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF] NLC [START_REF] Faktor | Video segmentation by non-local consensus voting[END_REF]. Note that the two top methods, NLC and FST [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] perform a video-level inference by propagating motion labels through the video, unlike our approach using only a pair of video frames at a time. Our network shows the top performance, by a significant margin, with respect to mean and recall on the IoU and F-measure scores. All the methods perform similarly on the decay scores, which quantifies the performance loss/gain over time. As MP-Net uses limited temporal information (two-frame optical flow) and does not perform inference at the video level, it is not the best one on the temporal stability measure. This limitation can be addressed with a post-processing step, such as using a temporal CRF. Figure 6 compares our approach qualitatively to the two top-performing methods, FST [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] and NLC [START_REF] Faktor | Video segmentation by non-local consensus voting[END_REF], on DAVIS. In the first row, FST localizes the moving boat, but its segmentation leaks into the background region around the boat, due to errors in motion tracking. NLC latches onto moving water, whereas our MP-Net segments the boat accurately. In the second row, our segmentation result is more precise and complete than both FST and NLC. The last row shows a failure case, where a part of the motorbike is missing due to highly imprecise flow estimation.

Table 4 shows quantitative comparison on the subset of BMS-26 used in [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF]. We observed that objects are annotated in some of the sequences when they do not undergo independent motion. Thus, the results of our MP-Net with objectness ('MP+Obj' in the table) are not directly comparable to the other methods which use propagation between frames, though they are still on par with many of the previous methods. To account for this mismatch with MP-Net, which only segments moving objects, we incorporate our frame-level motion estimation results into a state-ofthe-art video segmentation method [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF]. This is achieved by replacing the location unary scores in [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] with our motion prediction scores integrated with objectness. The results ('MP+Obj + FST [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF]' in the table) are significantly better than most previous methods, and on par with PCM [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF]. In particular, using our motion prediction in [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] improves the result by 14%. We also evaluated this combination ('MP+Obj + FST') on the FBMS test set, where it achieves 77.5% in F-measure, and is better than state-ofthe-art methods: FST [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] (69.2), CVOS [START_REF] Taylor | Causal video object segmentation from persistence of occlusions[END_REF] (74.9), and CUT [START_REF] Keuper | Motion trajectory segmentation via minimum cost multicuts[END_REF] (76.8).

Figure 7 compares our results on BMS-26 with the topmethod on this dataset, PCM [START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF], and the baseline videolevel approach FST [START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF]. In the first row, FST segments only one of the two moving cars in the foreground, due to very slow motion of the second car. Introducing our motion prediction into FST segments both these cars. This result is comparable to PCM. None of the methods segments the third car in the background however. In the second row, PCM fails to segment the woman, and FST segments only the jacket, but including our motion estimate into FST significantly improves the result. Tracking errors inherent in FST result in the segmentation leaking into the background.

Conclusion

This paper introduces a novel approach for learning motion patterns in videos. Its strength is demonstrated for the task of moving object segmentation, where our method outperforms many complex approaches, that rely on engineered features. Future work includes: (i) development of end-to-end trainable models for video semantic segmentation, (ii) use of a memory module for video object segmentation, (iii) using additional information, e.g., subset of frames annotated by users, to handle ambiguous cases.

Figure 2 .

 2 Figure 2. (a,b) Two example frames from a sequence in the FlyingThings3D dataset [23]. The camera is in motion in this scene, along with four independently moving objects. (c) Ground-truth optical flow of (a), which illustrates motion of both foreground objects and background with respect to the next frame (b). (d) Ground-truth segmentation of moving objects in this scene.

Figure 3 .

 3 Figure 3. Our motion pattern network: MP-Net. The blue arrows in the encoder part (a) denote convolutional layers, together with ReLU and max-pooling layers. The red arrows in the decoder part (b) are convolutional layers with ReLU, 'up' denotes 2 × 2 upsampling of the output of the previous unit. The unit shown in green represents bilinear interpolation of the output of the last decoder unit.

Figure 4 .

 4 Figure 4. Each row shows: (a) example frame from a sequence in FlyingThings3D, (b) ground-truth optical flow of (a), which illustrates motion of both foreground objects and background, with respect to the next frame, and (c) our estimate of moving objects in this scene with ground-truth optical flow as input.

  Figure 2(d) for an illustration.

  Figure 5(c). Although the prediction of our frame-pair feedforward model is accurate in several regions in the frame ((c) in the figure), we are faced with two challenges, which were not observed in the synthetic training set. The first one is motion of stuff [1] in a scene, e.g., patterns on the water due to the kiteboarder's motion (first row in the figure), which is irrelevant for moving object segmentation. The second one is significant errors in optical flow, e.g., in front of the pram ((b) in the bottom row in the figure).

Figure 5 .

 5 Figure 5. Sample results on the DAVIS dataset showing all the components of our approach. Each row shows: (a) video frame, (b) optical flow estimated with LDOF [6], (c) output of our MP-Net with LDOF flow as input, (d) objectness map computed with proposals [29], (e) initial moving object segmentation result, (f) segmentation refined with CRF.

Figure 7 .

 7 Figure 7. Qualitative comparison on two sample sequences from BMS-26. Left to right: ground truth, optical flow [6], results of FST [27], PCM [3], and our MP-Net + Objectness + FST ('MP+Obj + FST [27]').

Table 1 .

 1 Comparing the influence of different input modalities on the FlyingThings3D (FT3D) test set and DAVIS. Performance is shown as mean intersection over union scores. # dec. refers to the number of decoder units in our MP-Net. Ground-truth flow is used for evaluation on FT3D and LDOF flow for DAVIS.

	26, with 59 sequences in

Table 2 .

 2 Then we pick the best modality Performance of our best network (4 decoder units trained on GT angle field) with additional cues (Objectness, CRF) and different flow inputs (LDOF, EpicFlow) on DAVIS.

	Variant of our method	Flow used Mean IoU
	MP-Net	LDOF	52.4
	MP-Net	EpicFlow	56.9
	MP-Net + Objectness	LDOF	63.3
	MP-Net + Objectness	EpicFlow	64.5
	MP-Net + Objectness + CRF LDOF	69.7
	MP-Net + Objectness + CRF EpicFlow	68.0

Table 4 .

 4 MP+Obj MP+Obj + FST[START_REF] Papazoglou | Fast object segmentation in unconstrained video[END_REF] Comparison to state-of-the-art methods on the subset of BMS-26 used in[START_REF] Bideau | It's moving! A probabilistic model for causal motion segmentation in moving camera videos[END_REF] with F-measure. 'MP+Obj' is MP-Net with objectness.

	F	73.0	64.1	72.8	66.0	62.5	78.2	71.8	78.1
		Ground truth		Optical flow [6]	FST [27]		PCM [3]	MP+Obj + FST [27]

Acknowledgments. This work was supported in part by the ERC advanced grant ALLEGRO, the MSR-Inria joint project, a Google research award and a Facebook gift. We gratefully acknowledge the support of NVIDIA with the donation of GPUs used for this research.