New Variants of Frank-Wolfe Algorithm for Video Co-localization Problem

Suppose that we have a set $\mathcal{I}=\{I_{1},I_{2},\dots,I_{n}\}$ of $n$ given images, and our goal is to localize the common object in each image. One approach is to find candidate boxes in each image that potentially contain an object using objectness [5].

While object detectors for images are usually specialized for one object class such as cars, airplanes, cats, or dogs, objectness quantifies how likely it is for an image window to cover an object of any class. In an image, objects have a well-defined boundary and center, cats, dogs, and chairs, as opposed to indefinite background, such as walls, sky, grass, and road. Figure 1 illustrates the desired behavior of an objectness measure. Green windows must score highest windows fitting an object tight, blue windows should score lower windows covering partly an object and partly the background, and red windows should score lowest windows containing only partial background. This approach and the way we score the windows is designed in [5] and explicitly trained to distinguish windows containing an object from background windows.

Using objectness, we generate $m$ candidate boxes (e.g. green boxes in Figure 1) for each image that could potentially contain an object. In other words, if $j\in\{1,2,\dots,n\}$ we define $\mathcal{B}_{j}$ to be the set of all boxed in image $I_{j}\in\mathcal{I}$. Then the goal is to select the box that contains the object, from each image, jointly. Also. for simplicity let $\mathcal{B}=\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\cdots\cup\mathcal{B}_{n}$ and $n_{b}=nm$ the total number of boxes in all images.

Assume that we have determined $m$ candidate boxes in each of two the different images $I_{i}$ and $I_{j}$ for any $i,j\in\{1,2,\dots,m\}$. A common object in $I_{i}$ and $I_{j}$ might be in different shape, scale, color, brightness, angle and many other features. Therefore, it is critical to extract distinctive invariant features from images that can be used to perform reliable matching between different views of an object. David G. Lowe in [9] introduces a method that finds features that are invariant to image scaling and rotation, and partially invariant to change in illumination and 3D camera view point. Using his method, large number of features can be extracted from typical images with efficient algorithms, as well as the cost of extracting these features is minimized. The major stages of computation used to generate the set of image features are as follows.

1. 1.

   Scale-space extrema detection: The first stage of computation searches over all scales and image locations. It is implemented efficiently by using a difference-of-Gaussian function to identify potential interest points that are invariant to scale and orientation.

2. 2.

   Keypoint localization: At each candidate location, a detailed model is fit to determine location and scale. Keypoints are selected based on measures of their stability.

3. 3.

   Orientation assignment: One or more orientations are assigned to each keypoint location based on local image gradient directions. All future operations are performed on image data that has been transformed relative to the assigned orientation, scale, and location for each feature, thereby providing invariance to these transformations.

4. 4.

   Keypoint descriptor: The local image gradients are measured at the selected scale in the region around each keypoint. These are transformed into a representation that allows for significant levels of local shape distortion and change in illumination.

This process is called Scale Invariant Feature Transform (SIFT). SIFT transforms image data into scale-invariant coordinates relative to local features. Using SIFT we can generate large numbers of features that densely cover the image over full range of scales and locations.

Let $b_{k}$ be a box in $\mathcal{B}$. Then we denote the SIFT feature representation of $b_{k}$ as $x_{k}\in\mathbb{R}^{d}$ where $d=10,000$ is the dimensional feature descriptor for each box in $\mathcal{B}$. Finally, we stack the feature vectors to form a feature matrix $X\in\mathbb{R}^{n_{b}\times d}$.

Let us denote the boxes that contain an instance of the common object as positive boxes, and the ones that don’t as negative boxes. Then a prior is introduced for each box that represents a score that the box is positive. This happens using a saliency map [10] for each box and the prior is in fact the average saliency within the box, weighted by the size of the box. Finally we stack these values into the $n_{b}$ dimensional vector $\mathbf{m}$ as the prior vector.

In addition, boxes that have the similar appearance should be labeled the same. This happens through a matrix called similarity matrix denoted by $S$. Similarity matrix of boxes in $\mathcal{B}$ is based on the box feature matrix $X$ described above. Let $b_{i}$ and $b_{j}$ be any two boxes in $\mathcal{B}$ where $i,j\in\{1,2,\dots,n_{b}\}$. Then similarity matrix $S\in\mathbb{R}^{n_{b}\times n_{b}}$ is computed based on the $\chi^{2}$-distance as

where $\gamma=(10d)^{-1/2}$. For $i$ and $j$ where boxes $b_{i}$ and $b_{j}$ belong to the same image we set $S_{ij}=0$. Then the normalized Laplacian matrix [11] is computed as

where $D$ is the diagonal matrix composed of row sums of $S$.

Associated with each box $b_{j,k}\in\mathcal{B}_{j}$ we define a binary variable $z_{j,k}$ where $z_{j,k}=1$ when $b_{j,k}$ is a positive box (contains an instance of the common object) and 0 otherwise. Then we define the integer vector variable

Making the assumption that in each image there exist at most 1 positive box, our set of constraints are define by

As we introduced a prior for each box and defined the $n_{b}$ dimensional vector of average saliency within the boxes, we obtain a linear term that penalizes less salient boxes as part of the objective function:

Similarly, our choice of normalized Laplacian matrix $\mathcal{L}$ defined in (2) results in a quadratic term that handles the selection of similar boxes:

This is motivated by the work of Shi and Malik [11] in which they have taken advantage of eigenvalues of the Laplacian for clustering $\mathbf{z}$ by the similarity matrix. In fact, they have shown that with the eigenvector corresponding to the second smallest eigenvalue of a normalized Laplacian matrix we can cluster $\mathbf{z}$ along the graph defined by the similarity matrix, leading to normalized cuts when used for image segmentation. Also, Belkin and Niyogi [12] showed that this problem is equivalent to minimizing (6) under linear constraints. In fact, the similarity term works as a generative term which selects boxes that cluster well together [4].

Although discriminative learning techniques such as support vector machines and ridge regression has been widely used on many supervised problems in which there are know labels, they can be used in this unsupervised case where the labels of boxes are unknown [13, 14]. Motivated by [15], we consider the ridge regression objective function for boxes:

where $w$ is the $d$ dimensional weight vector of the classifier, and $c$ is the bias. This cost function is being used among discriminative cost functions because the ridge regression problem has a explicit (closed form) solution for weights $w$ and bias $c$ which implies the quadratic function in the box labels [13]:

where

is the discriminative clustering term and $\Pi_{n_{b}}=I_{nb}-\frac{1}{n_{b}}\mathbf{1}_{n_{b}}\mathbf{1}_{n_{b}}^{T}$ in (9) is the centering projection matrix. Note that this quadratic term allows us to utilize a discriminative objective function to penalize the selection of boxes whose features are not easily linearly separable from other boxes.

Summing up our results in (4), (5), (6), and (8), the optimization problem to select the best box in each image is given by

where parameter $\mu$ regularizes the trade-off between the quadratic terms (6) and (8), and parameter $\lambda$ handles the trade-off between the linear term (5) and the quadratic terms (6) and (8). Recall that the linear constraints ensures that one box from each image is selected in the optimal solution. Note that Hastie, Tibshirani, and Friedman in [16] showed that $\mathcal{A}$ is a positive semi-definite matrix. Also, since matrix $\mathcal{L}$ is positive semi-definite as well, the objective function of (10) is convex.

As discussed earlier in this section, objects in consecutive frames in video data are less likely to change drastically in appearance, position, and size. This is a motivation to use a separate prior for frames or images in video case. Temporal consistency [17, 18, 23, 22, 21, 20, 19] is a powerful prior that is often leveraged in video tasks such as tracking [3]. In this approach, in consecutive frames, boxes with great difference in size and position should be unlikely to be selected together. To this end, a simple temporal similarity measure is defined between two boxes $b_{i}$ and $b_{j}$ from consecutive frames with:

A few comments comes in place about the prior defines in (11). First, $b_{i}^{\text{area}}$ is the vector of the pixel area of box $b_{i}$ and $b_{i}^{\text{center}}$ are the vectors of the center coordinates of box $b_{i}$, normalized by the width and height of the frame. Second, the metric defined in (11) is a similarity metric that is defined between all pairs of boxes in adjacent frames. From this metric we can define a weighted graph $\mathcal{G}_{i}$ for video $\mathcal{V}_{i}$ for $i=1,2,\dots,n$ with nodes being the boxes in each frame and edges connecting boxes in consecutive frames and weights of edges defined as temporal similarity in (11). Figure 3 is a graphical representation of graph $\mathcal{G}_{i}$. For small values of similarity measure with some threshold we disconnect the nodes and remove the edge. Finally, as long as we can create a weighted graph with boxes, any similarity measure other than the temporal consistency in (11) can be used to weight the edges between two boxes, which makes the temporal framework pretty flexible.

Let us define

to be the similarity matrix define by the temporal similarity measure, where $b_{i}$ and $b_{j}$ are any two boxes in the set of all boxes in $\mathcal{V}$. Similar to our approach to obtain (2), with $S_{t}$ we can compute the normalized Laplacian

where $D$ is the diagonal matrix composed of the row sums of $S_{t}$. This matrix encourages us to select boxes that are similar based on the temporal similarity metric (11).

As we discussed above, temporal similarity suggests a weighted graph $\mathcal{G}_{i}$ for video $\mathcal{V}_{i}$ for $i=1,2,\dots,n$. In fact, a valid path in $\mathcal{G}_{i}$ from the the first to the last frame in $\mathcal{V}_{i}$ corresponds to feasible boxes chosen in each frame of $\mathcal{V}_{i}$. This motivates us to define a binary variable to be on when there is an edge between any two nodes in $\mathcal{G}_{i}$ and off otherwise. In better words, we define the binary variable $y_{i,j,k}$ for video $i$ and boxes $b_{j}$ and $b_{k}$ in $\mathcal{V}_{i}$ as

In fact, variable $y_{i,j,k}$ corresponds to the existence of edge between boxes $b_{j}$ and $b_{k}$ in $\mathcal{V}_{i}$. Also, we define the binary variable $z_{i,j,k}$ to be 1 if the box $b_{k}$ in frame $j$ of video $i$ contains the common object, and 0 otherwise. A type of constraint that we need to consider here is the fact that there might exist an edge between boxes $b_{j}$ and $b_{k}$ only if they are boxes in two consecutive frames. Then, for a typical box $b_{k}$ in frame $j$ of video $\mathcal{V}_{i}$, we define index sets $p(k_{j})$ and $c(k_{j})$ to be the set of indices of parents and children boxes in frames $j+1$ and $j-1$, respectively, that are connected to $b_{k}$ in frame $j$ in the graph $\mathcal{G}_{i}$. Therefore, a required set of constraints for localization in video case are defines by:

The other set of constraints, which are quite similar to the image co-localization case, are the set of constraints restricting each frame of each video to has only one box that contains the common object. These constraints are defined by:

Finally, we define the vectors of variables

where $n_{b}^{v}=m\sum_{i=1}^{n}l_{i}$. Then if we combine the temporal terms defined by (13) with the terms in the objective function of the original image model (10), then with constraint defines in (15) and (16), we obtain the following optimization formulation to select the box containing the common object in each frame of video:

where $\mu_{t}$ is the trade-off weight for the temporal Laplacian matrix. Note that with the new objective function in problem (17) the extra constraint (15) in video case is necessary and without that the temporal Laplacian matrix would lead the solution to an invalid path. This formulation allows us to incorporate temporal consistency into the image model.

The basic scheme of the ACGS and PCGS methods is obtained by performing a new search direction in CGS method, if the new direction leads the algorithm to smaller Wolfe gap. Also, similar to the CGS algorithm, the classical FW method (as $\mathcal{FW}$ procedure) is incorporated in this algorithm to solve the projection subproblems in the accelerated gradient (AG) with some approximations. The ACGS and PCGS algorithms are described as in 1 and 3.

Note that the purpose of the proposed algorithm is to be applied to the image and video co-localization problems (10) and (17). The objective function in both problems, as discussed before, are convex functions, and the feasible region is a set of finite binary vectors called atoms in $\mathbb{R}^{d}$ for some $d$. We denote this set by $\mathcal{A}$ and its convex hull conv($\mathcal{A}$) by $\mathcal{M}$. As $\mathcal{A}$ is finite, $\mathcal{M}$ is a polytope.

The first difference between the AGCS(PCGS) and the CGS method is that we incorporate the set $\mathcal{S}^{(k)}$ of active atoms in the ACGS(PCGS) algorithm. This set keeps record of atoms (integer points) in $\mathcal{A}$ that are being used for the away direction $d_{K}^{\text{away}}$ at each iteration such that the point $y_{k}$ at current iteration is the sum of corners in $\mathcal{S}^{(k)}$ reweighted by $\alpha^{(k)}$. This direction that is given in (22), is defined by finding the atom $v_{k}$ in $\mathcal{S}^{(k)}$ that maximized the potential of descent given by $\left\langle-f^{\prime}(y_{k-1}),y_{k-1}-v_{k}\right\rangle$. Note that obtaining $v_{k}$ in $\eqref{Alg:ACGS:v}$ is fundamentally easier as the linear optimization is over the $\mathcal{S}^{(k)}$, the active set of possibly small finite set of points.

The second difference is in the way we update the step-size to update the new iteration point. As we observe in (31) we incorporate a line-search method to obtain a step-size with maximum reduction in the objective toward a prespecified direction from the point at current iteration. With $\gamma_{\text{max}}$ defined in (26) and (29) as the maximum step-size for the line-search step the algorithm guarantees that the new iterates $y_{k}=y_{k-1}+\gamma_{\text{max}}d_{k}^{\text{away}}$ stays feasible in each iteration. Note that the parameter $\gamma_{k}$ in CGS algorithm is required to be set up in appropriate way to maintain the feasibility in each iteration. Such set ups are represented in [1] as ${\gamma}_{k}=3/(k+2)$ and ${\gamma}_{k}=2/(k+1)$ and in fact, we can us these set ups for CGS steps in step (26) as the upper bound for $\gamma_{k}$ instead of 1 in line-search step (31). Also, it is easy to check that for the special case of the image and video co-localization problem in which the objective is a convex quadratic function $\gamma_{k}$ in step (31) has the closed form

if $Q\succeq 0$ is the quadratic term in the objective. This value is projected to 0 or $\gamma_{\text{max}}$ if is outside of the range $[0,\gamma_{\text{max}}]$ for (31) case.

Finally, we incorporate the Wolfe gap as an stopping criterion in the ACGS and PCGS algorithms. In fact, at steps (23) and (41), the algorithms checks if they have reached the given threshold to stop before the preset max number of iterations $N$. As in classical FW, the Wolfe gap is an upper bound on the unknown suboptimality and from the convexity of the objective $f$ we have

Note that for the image and video co-localization problem with binary decision variables in a CGS step we have

Also, for $v\in\mathcal{S}^{(k)}\setminus\{s_{k}\}$ we have

On the other hand, for an away step we have

This step is called a drop step. Also, for $v\in\mathcal{S}^{(k)}\setminus\{v_{k}\}$ we have

ACGS and PCGS algorithms are slightly different in the direction that they use to update the new point at each iteration. More precisely, steps (24) to (30) in Algorithm 1 are replaced with steps (42) and (43) in Algorithm 3. Similar to the Paiwise FW, the idea here is to only move weight from the away atom $v_{k}$ to the CGS atom $x_{k}$ and keep all other $\alpha$ weight unchanged. In other words

for some $\gamma\leq\gamma_{\text{max}}:=\alpha_{v_{t}}^{(k)}$.

An important property of the formulation (10) and (17) is that their constraints are separable for each image and video. This helps computation to be more efficient if we use parallel computing. This, however, is a property of any first-order method and practically it is very memory efficient. In addition, as a solution to the convex relaxation is not necessarily an integer solution optimal or feasible to the original problem, we need to come up with a solution as close as possible to the obtained relaxation optimum. In image and video co-localization case, the most natural way of finding such a solution is to solve

where $\mathcal{P}$ is the feasible region of the original problem and $y$ is the solution to the relaxed problem. It is easy to check that the projection problem (53) is equivalent to

which for the video model is just a shortest path problem that can be solved efficiently using dynamic programming.

Algorithm 4 is a variant of FW algorithm proposed in [3] in which the authors examined it on two datasets, the PASCAL VOC 2007 dataset [25] and the Youtube-Objects dataset [26]. This algorithm is in fact the AWF Algorithm introduced in [3] with some slight changes and some extra rounding steps. Also, the set $\mathcal{D}$ in this algorithm is conv$(\mathcal{P})$ the convex hull of the feasible region of problems (10) or (17). Their implementation of Algorithm 4 was coded in MATLAB and they compare it to two standard Quadratic Programming (QP) solvers, Mosek and Gurobi on a single-core 2.66GHz Intel CPU with 6GB of RAM. In addition, they set $\mu=0.4$ for the image model and $\mu=0.6$ for the video model and $\mu_{t}=1.8$ and $\lambda=0.1$, for both image and video models. They extracted 20 objectness boxes from each image and sample each video every 10 frames as there is little change frames in short amount time.

The stopping criterion of Algorithm 4 is based on the relative duality gap. This criterion, that is given in function duality-gap($z$) in the algorithm, is defined as $d=(f-g)/g$, where $f$ is the objective function and $g$ is its dual. In the implementation of this algorithm, authors consider two values $1e$ - 2 and $1e$ - 3 for the stopping threshold $\epsilon$.

Figures 4 presents some comparisons of the Algorithm 4 as a variant of FW algorithm with QP solvers Mosek and Gurobi in logarithmic scale. Indeed, this comparison is based on the CPU time performance of the algorithms depending on the number of images and videos, or in better words, the dimension of the decision variables. This time is the time that takes that algorithms reach a duality gap less than the threshold $\epsilon$. As we can observe from these plots, the variant of FW algorithm with away steps outperforms the standard QP solvers Mosek and Gurobi.

The reason that we review and represent these comparisons directly from [3]local is that in our implementations in next section we will only compare our proposed algorithms to some other first order methods. These first order methods include the AWF algorithm that we already know from this section that it outperforms standard QP solvers.

The PASCAL Visual Object Classes 2007 dataset [25] provides standardized image data of 20 objects for object classes recognition along with annotations for images and bounding box and object class label for each object. Challenges and competitions have been used to recognize objects from a number of visual object classes in realistic scenes. The YouTube-Objects dataset [26] consists of YouTube videos collected for 10 classes from PASCAL [25]: ”aeroplane”, ”bird”, ”boat”, ”car”, ”cat”, ”cow”, ”dog”, ”horse”, ”motorbike”, and ”train”. Although authors in [3] did the study on multiple objects of this dataset, in our implementations our focus will be on the ”aeroplane” object class.

Knowing that AFW Algorithm 4 outperforms the standard QP solvers Mosek and Gurobi from the works in [3], in this section we compare our proposed variants of the CGS algorithm, the ACGS Algorithm 1 and the PCGS Algorithm 3 to some other first order methods, including the AFW method. More precisely, we will compare the performance of our algorithms to all of the variants of the FW namely, the FW, the FW Algorithm with away steps (AFW), and the pairwise FW Algorithm as discussed in [3]. We also compare our algorithms to the original CGS Algorithm [1]. These comparisons include the duality gap, CPU time, and objective function value versus the iterations.

The implementations are over the YouTube Objects dataset [25] explained in previous section, and specifically its ”aeroplane” class. We obtain the dataset for this class and also the codes for AFW and Pairwise FW algorithms available in the repositories for [3, 24, 4]. We only consider the task of video co-localization with the problem formulation defined in (17) for this implementation. All algorithms are coded in MATLAB and run on a computer with Interl Core i5-6500 CPU 3.2 GHz processor with 16 GB of RAM.

In our implementations, we set all algorithms to stop either after the maximum number of iterations or after reaching the Wolfe duality gap threshold. We set the threshold to $\epsilon=1e-5$ and the max number of iterations to 2000 iterations. All of the parameters exist in (17) are set the same as in [24] for consistency in the comparison.

Note that both original versions of FW and CGS algorithms do not reach the desired duality gap before the preset 2000 max number of iterations. Also, the AFW algorithm takes 628 iterations, the Pairwise FW takes 436 iterations, the ACGS takes 84 iterations, and PCGS takes 82 iterations to reach the threshold for the duality gap.

As we observe in Figure 5 both proposed variants of CGS algorithm, the ACGS and PCGS algorithms outperform the FW algorithms and its variants as well as the original CGS algorithm. The performance of the algorithms in terms of the CPU time versus iterations increments also is represented in Figure 6. As we observe in this figure the CPU time per iteration of AFW and ACGS and PCGS are quite similar, although the ACGS and PCGS algorithms reach the gap much earlier than the AFW algorithm.

In addition, while FW algorithm requires one linear optimization oracle per iteration, its CPU time per iteration is not significantly better than the other algorithms. Also, note that out of 84 iteration of the ACGS algorithm, it chooses the away direction in 34 iteration which improves the performance of CGS (with more than 2000 iterations) for this problem significantly.

Finally, authors in [24] proved, for the first time, the global linear convergence of the variants of FW algorithms, AFW and Pairwise FW, under strong convexity of the objective. One potential research work related to the current chapter is figure out the convergence of the proposed algorithms 1 and 3.