{'fraction_non_alphanumeric': 0.033858588602866266, 'fraction_numerical': 0.009950417713781159, 'mean_word_length': 4.632555470543228, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learnable Cost Volume Using the Cayley Representation

Cost volume is an essential component of recent deep models for optical flow estimation and is usually constructed by calculating the inner product between two feature vectors. However, the standard inner product in the commonly-used cost volume may limit the representation capacity of flow models because it neglects the correlation among different channel dimensions and weighs each dimension equally. To address this issue, we propose a learnable cost volume (LCV) using an elliptical inner product, which generalizes the standard inner product by a positive definite kernel matrix. To guarantee its positive definiteness, we perform spectral decomposition on the kernel matrix and re-parameterize it via the Cayley representation. The proposed LCV is a lightweight module and can be easily plugged into existing models to replace the vanilla cost volume. Experimental results show that the LCV module not only improves the accuracy of state-of-the-art models on standard benchmarks, but also promotes their robustness against illumination change, noises, and adversarial perturbations of the input signals.


Introduction
Optical flow estimation is a fundamental computer vision task and has broad applications, such as video interpolation [2], video prediction [21], video segmentation [36,6], and action recognition [22]. Despite the recent progress made by deep learning models, it is still challenging to accurately estimate optical flow for image sequences with large displacements, textureless regions, motion blur, occlusion, illumination changes, and non-Lambertian reflection.
Most deep optical flow models [33,23,12] adopt the idea of coarse-to-fine processing via feature pyramids and construct cost volumes at different levels of the pyramids. The cost volume stores the costs of matching pixels in the source image with their potential matching candidates in the target image. It is typically arXiv:2007.11431v1 [cs.CV] 21 Jul 2020 constructed by calculating the inner product between the convolutional features of one frame and those of the next frame, and then regressed to the estimated optical flow by an estimation sub-network. The accuracy of the estimated optical flow heavily relies on the quality of the constructed cost volume. While the standard Euclidean inner product is widely used to build the cost volume (a.k.a., vanilla cost volume) for optical flow, we argue that it limits the representation capacity of the flow model for two reasons. First, the correlation among different channel dimensions is not taken into consideration by the standard Euclidean inner product. As shown in Fig. 1, we use a simple 2D example for illustration. Given two feature vectors f 1 and f 2 with positive correlation in the standard inner product space, we are able to find a proper elliptical inner product space to make these two feature vectors orthogonal to each other, which gives a zero correlation. Therefore, the specific choice of the inner product space influences the values of the matching costs, and thus should be further exploited. Second, each feature dimension contributes equally to the vanilla cost volume, which may give a sub-optimal solution to constructing the cost volume for flow estimation. Ideally, dimensions corresponding to noises and random perturbations should be suppressed, while those containing discriminative signals for flow estimation should be kept or magnified.
To address these limitations, we propose a learnable cost volume (LCV) module which accounts for the correlation among different channel dimensions and re-weighs the contribution of each feature channel to the cost volume. The LCV generalizes the Euclidean inner product space to an elliptical inner product space, which is parameterized by a symmetric and positive definite kernel matrix. The spectral decomposition of the kernel matrix gives an orthogonal matrix and a diagonal matrix. The orthogonal matrix linearly transforms the features into a new feature space, which accounts for the correlation among different channel dimensions. The diagonal matrix multiplies each transformed feature by a positive scalar, which weighs each feature dimension differently. From a geometric perspective, the orthogonal matrix rotates the axes and the diagonal matrix stretches the axes so that the feature vectors are represented in a learned elliptical inner product space, which generates more discriminative matching costs for flow estimation.
However, directly learning a kernel matrix in an end-to-end manner cannot guarantee the symmetry and positive definiteness of the kernel matrix, which is required by the definition of inner product. To address this issue, we perform spectral decomposition on the kernel matrix and represent each component via the Cayley transform. Specifically, the special orthogonal matrices that exclude −1 as the eigenvalue can be bijectively mapped into the skew-symmetric matrices, and the diagonal matrices can be similarly represented by the composition of the Cayley transform and the arctangent function. In this way, all parameters of the learnable cost volume can be inferred in an end-to-end fashion without explicitly imposing any constraints.
The proposed learnable cost volume is a general version of the vanilla cost volume, and thus can replace the vanilla cost volume in the existing networks. We finetune the existing architectures equipped with LCV by initializing the kernel matrix as the identity matrix and restoring other parameters from the pre-trained models. Experimental results on the Sintel and KITTI benchmark datasets show that the proposed LCV significantly improves the performance of existing methods in both supervised and unsupervised settings. In addition, we demonstrate that LCV is able to promote the robustness of the existing models against illumination changes, noises, and adversarial attacks.
To summarize, we make the following contributions: 1. We propose a learnable cost volume (LCV) to account for correlations among different feature dimensions and weight each dimension separately. 2. We employ the Cayley representation to re-parameterize the kernel matrix in a way that all parameters can be learned in an end-to-end manner. 3. The proposed LCV can easily replace the vanilla cost volume and improve the accuracy and robustness of the state-of-the-art models.

Related Work
Supervised Learning of Optical Flow. Inspired by the success of convolutional neural networks (CNNs) on per-pixel predictions such as semantic segmentation and single-image depth estimation, Dosovitski et al. propose FlowNet [8], the first end-to-end deep neural network capable of learning optical flow. FlowNet predicts a dense optical flow map from two consecutive image frames with an encoder-decoder architecture. FlowNet2.0 [15] extends FlowNet by stacking multiple basic FlowNet modules for iterative refinement and its accuracy is fully on par with those of the state-of-the-art methods at the time. Motivated by the idea of coarse-to-fine refinement in traditional optical flow methods, SpyNet [29] introduces a compact spatial pyramid network that warps images at multiple scales to deal with displacements caused by large motions. PWC-Net [33] extracts feature through pyramidal processing and builds a cost volume at each level from the warped and the target features to iteratively refine the estimated flow. VCN [39] improves the cost volume processing by decoupling the 4D convolution into a 2D spatial filter and a 2D winner-take-all (WTA) filter, while still retaining a large receptive field. HD 3 [40] learns a probabilistic matching density distribution at each scale and merges the matching densities at different scales to recover the global matching density.
Unsupervised Learning of Optical Flow. The advantage of unsupervised methods is that it can sidestep the limitations of the synthetic datasets and exploit the large number of training data in the realistic domain. In [17] and [31], the flow guidance comes from warping the target image according to the predicted flow and comparing against the reference image. The photometric loss is adopted to ensure brightness constancy and spatial smoothness. In some work [37,25], occluded regions are excluded from the photometric loss. As pixels occluded in the target image are also absent in the warped one, enforcing matching of the occluded pixels would misguide the training. Wang et al. [37] obtain an occlusion mask from the range map inferred from the backward flow, while UnFlow [25] relies on the forward-backward consistency to estimate the occlusion mask. Unlike these two methods that predict the occlusion map in advance with certain heuristic, Back2Future [16] estimates the occlusion and optical flow jointly by introducing a multi-frame formulation and reasoning the occlusion in a more advanced manner. DDFlow [23] performs knowledge distillation by cropping patches from the unlabeled images, which provides flow guidance for the occluded regions. SelFlow [24] hallucinates synthetic occlusions by perturbing super-pixels where the occluded regions are guided by a model pre-trained from non-occluded regions.
Correspondence Matching. Typically, stereo matching algorithms [32,11] involve local correspondence extraction and smoothness regularization, where the smoothness regularization is enforced by energy minimization. Recently, handcrafted features are replaced by deep features and minimization of the matching cost is substituted by training convolutional neural networks [42,19]. Xu et al. [38] construct a 4D cost volume using an adaptation of the semi-global matching, and Yang et al. [39] reduce the computation overhead of processing the 4D matching volume by factorizing into two separable filters. Different from these approaches where the correspondence is represented by a hand-crafted matching cost volume, we propose a learnable cost volume that can capture the correlation among different channels by adapting the features to an elliptical inner product space. Such a correlation is automatically learned by optimizing the kernel matrix using the Cayley representation, which is more flexible and effective in optical flow estimation and can be easily plugged into the existing architectures. To our knowledge, this paper is the first one to use the Cayley representation for learning correspondence in optical flow.

Vanilla Cost Volume
Let F 1 , F 2 ∈ R c×h×w be the convolutional feature of the first frame and the warped feature of the second frame, respectively. The vanilla cost volume is defined as the inner product between the query feature F 1 i,j and the potential match candidate F 2 k ,l , i.e., which maps from the space R c×h×w × R c×h×w to R u×v×h×w . Here, u and v are usually odd numbers, indicating the displacement ranges in horizontal and vertical directions, (i, j) denotes the spatial location of the feature map F 1 , and For each location (i, j) of the query feature F 1 , the matching is performed against pixels of F 2 within a u×v search window centered by the location (i, j). Then, the cost volume is either reshaped into uv × h × w and post-processed by 2D convolutions [33], or kept as a 4D tensor on which the separable 4D convolutions [39] are applied.

Learnable Cost Volume
We generalize the standard Euclidean inner product to the elliptical inner product, where the matching cost is computed as follows: Here, W ∈ R c×c is a learnable kernel matrix that determines the elliptical inner product space, and other notations are the same as those in Eq. (1). According to the definition of inner product, W should be a symmetric and positive definite matrix. By spectral decomposition, we obtain where P is an orthogonal matrix, and Λ is a diagonal matrix with positive entries, i.e., Λ = diag(λ 1 , · · · , λ c ) with λ i > 0, ∀i ∈ {1, · · · , c}. The orthogonal matrix P actually rotates the coordinate axes and the diagonal matrix Λ re-weights different dimensions, which directly address the two limitations mentioned in Sec. 1.

Learning with the Cayley Representation
In the proposed LCV module, the entries of the kernel matrix W are the only learnable parameters. However, the constraints of symmetry and positivedefiniteness hinders the gradient-based end-to-end learning of W . To address this issue, we propose to optimize P and Λ instead of W . One way to optimize P is to employ the Riemann gradient descent on the Stiefel manifold, which is defined as All orthogonal matrices lie in the Stiefel manifold. Specifically, P ∈ V c (R c ). Therefore, we can apply the Riemann gradient descent on the Stiefel matrix manifold, where the projection and retraction formula [1] are given by where skew(X) := (X − X )/2. However, to perform the Riemann gradient descent, the projection and retraction operations are required in each training step, and the matrix multiplication brings considerable computational overhead. We can address this issue in a more elegant way using the Cayley Representation [5]. First, we define a set of matrices: where σ(A) denotes the spectrum, i.e., all eigenvalues, of A. SO * (n) is a subset of the special orthogonal group SO(n) and the spectrum of its elements excludes −1. Then, we have the following theorems: Theorem 1 (Cayley Representation) Given any matrix P ∈ SO * (n), there exists a unique skew-symmetric matrix S, i.e., S = −S, such that Theorem 2 The set of matrices SO * (n) is connected.
By Theorem 1, we can initialize the matrix P in Eq. (3) as an identity matrix I ∈ SO * (c), and update S so as to update P using gradient-based optimizer. Let P * be the optimal orthogonal matrix, and we claim that it is possible to reach P * from initializing as the identity matrix P = I. This because SO * (c) is a connected set (Theorem 2), so there exists a continuous path joining I ∈ SO * (c) and any P ∈ SO * (c), including P * .
Due to the positive definiteness of W , the constraint of the diagonal matrix Λ = diag(λ 1 , . . . , λ c ) is λ i > 0, ∀i = 1, . . . , c. Thus, we map R to R + by applying the composition of the Cayley transform and the arctangent function, i.e., where t i ∈ R is free of constraint.
The above re-parameterization trick enables us to update the kernel matrix W in an end-to-end manner using the SGD optimizer or its variants, which alleviates the heavy computation brought by the projection and retraction and makes the training process much easier.

Interpretation
To better understand the learnable cost volume, we analyze several cases here.
1. W = I. This degenerates into the vanilla cost volume, in which the standard Euclidean inner product is adopted.
Let Σ be the covariance matrix, i.e., Gram matrix, of the convolutional feature, then the learnable cost volume is essentially a whitening transformation. Let Q = Λ 1/2 P , and then Eq. (2) can be formulated as where QF 1 i,j represents the transformed feature of F 1 i,j after PCA [18] whitening. Similarly, letting R = P Λ 1/2 P , we can have where RF 1 i,j is the transformed feature of F 1 i,j after ZCA [3] whitening. It has been shown that the high-level styles can be removed with the contextual structures remained by whitening the convolutional features [20].
3. W = P ΛP . The learnable cost volume shares a similar formula as the whitening process, but W is learned over the whole training dataset rather than statistics of two inputs, thus contains certain holistic information of the entire training dataset. Because it has been verified that the certain holistic characteristics of the underlying image can be captured by the Gram matrix along the channel dimension [9,20]. The learnable cost volume performs as whitening features using the common information learned from all frames. Specifically, the orthogonal matrix P re-arranges the information across the channel dimension, while the diagonal matrix Λ filters out insignificant signals, making the correlation more robust to the illumination changes abd noises. (See Sec. 4.4.) It should also be pointed out that the whitening matrix R in Eq. (11) could be viewed as a 1 × 1 conv functioning on the feature, but directly applying a 1 × 1 conv with learnable parameters on features before computing the standard cost volume cannot replace the proposed learned cost volume. Because R R only gives a positive semi-definite matrix even when R is full-rank, which does not meet the positive definiteness property of an inner product.

Relation with the Weighted Sum of Squared Difference
The learnable cost volume can be also formulated by re-thinking the simplest matching criterion for comparing two features, i.e., the weighted sum of squared difference (WSSD): where G : R c → R c denotes a transformation function on the features F i ∈ R c , i = 1, 2, and G i (F ) indicates the i th element of G(F ). By the Taylor series expansion, we have where ∆F =F 2 −F 1 is the feature difference and W = i λ i ∇G i (F 1 )∇G i (F 1 ) is the auto-correlation matrix. Here, W coincides with the kernel matrix of the proposed LCV module in Eq. (2). When λ i = 1(i = 1, . . . , c) and G is an identity map, then W = I, which corresponds to the vanilla cost volume. If we further expand Eq. (13), we can see the connection with the proposed learnable correlation volume as follows: where the last term shares the same formula with the proposed learnable cost volume. This implies that the proposed learnable cost volume is inversely correlated with WSSD. As WSSD measures the discrepancy between two features, the learnable cost volume characterizes a certain kind of similarity between them.

Experiments
In this section, we present the experimental results of optical flow estimation in both supervised and unsupervised settings to demonstrate the effectiveness of the proposed learnable cost volume. Also, we carry out ablation studies to show that the LCV module performs favorably against other counterparts. Moreover, we analyze the behavior of LCV and find it beneficial to handling three challenging cases. More results can be found in the supplementary material and the source code and trained models will be made available to the public.
Training Process. It is well-known that the deep optical flow estimation pipeline consists the following stages in the supervised settings [34]: 1) train the model on the FlyingChairs [7] dataset; 2) finetune the model on the FlyingTh-ings3D [28] dataset; and 3) finetune the model on the Sintel [4] and KITTI [27,26] training sets. Besides, there are lots of tricks such as data augmentation and learning rate disruption, making the training process more complicated.
To avoid the tedious training procedure over multiple datasets, we adopt a more efficient way to train the model equipped with LCV. As mentioned in Sec. 3.4, the vanilla cost volume is a special case of the learnable cost volume when W = I, which means that the learnable cost volume is more general and backward compatible with vanilla cost volume. Therefore, we initialize the kernel matrix W as the identity matrix and other parameters are directly restored from the pre-trained models without using LCV. After that, we finetune the model with LCV on the Sintel or KITTI datasets using the same loss function. This training process not only significantly reduces training time but also plays a crucial role in the success under the unsupervised settings. (See Sec. 4.2.) This approach can also be viewed as fixing the kernal matrix as W = I in the first three training stages, and let W be learnable in the final stage.

Supervised Optical Flow Estimation
First, we incorporate the learnable cost volume in the VCN [39] and RAFT [35] framework, and compare them with other existing methods. As shown in Table 1, our method performs favorably against other state-of-the-art methods on the Sintel Clean/Final pass and the KITTI 2015 benchmark. The proposed LCV module improves the performance of VCN and RAFT by transforming the features of video frames to a whitened space to obtain a clean and robust matching correlation. This could account for the performance improvement on the Sintel Final pass, where the scenarios are much harder. As shown in Fig. 2, the flow estimation error for the snow background at the right side is smaller than other methods. This is a challenging case because the front person's arm renders occlusion to part of the snow background and the  background is nearly all white, providing few clues for matching. However, the LCV module exploits more information from the correlation among different channels, which assists in obtaining the coherent flow estimation in the snow background. The LCV module also has an edge over the vanilla cost volume under the circumstance of light reflection and occlusion. As shown in Fig. 3, the prediction error of our method is smaller around the light reflection region and the rightmost traffic sign.
Although we do not report the model parameters in the table, the proposed LCV module only makes a very slight increase in the model size. The additional parameters come from the kernel matrices W ∈ R c×c at different pyramid levels. Taking VCN+LCV as an example, there are five kernel matrices in total, whose channel dimensions are 64, 64, 128, 128, and 128

Unsupervised Optical Flow Estimation
We also test the LCV module in unsupervised settings on the KITTI 2015 benchmark. We replace the vanilla cost volume with the LCV module in the DDFlow [23] model, and compare it with other unsupervised methods. As shown in Table 2, our model outperforms the DDFlow baseline, and even performs favorably against SelFlow [24], an improved version of DDFlow.
The training process is crucial to the success of the LCV module in the unsupervised methods. Different from the supervised training of optical flow models, there is no ground truth for direct supervision. Instead, most unsupervised methods use the photometric loss as a proxy loss. Specifically, the training of DDFlow consists of two stages: 1) pre-train a non-occlusion model with census transform [10], and 2) train an occlusion model by distillation from the non-occlusion model. If we directly follow the same procedure, the training of DDFlow+LCV will run into trivial solutions, as the photometric loss does not give a strong supervision for the correspondence learning, especially when the LCV module increases the dimension of the solution space. To prevent from trivial solutions, we fix the kenrel matrix as W = I in the pre-train stages, and update W in the distillation stage.

Ablation Study
We evaluate multiple variants of the LCV module based on the VCN baseline: -VCN: the original VCN baseline.
-VCN (ct): continue training the existing VCN using a small learning rate for more epochs. -VCN (W , ct): remove the symmetry and positive definiteness constraint of W , i.e., , not using the Cayley representation. We restore the weights from the pre-trained VCN and continue training the model with free W .
-VCN (Λ, ct): fix P to be an identity matrix and make the diagonal matrix Λ learnable. -VCN (P , ct): fix Λ to be an identity matrix and make the orthogonal matrix P learnable. We randomly split the 200 images with ground truth from the KITTI 2015 training set into the training and validation set by a ratio of 4:1. As shown in Table 3, we report the AEPE/Fl-all scores on the validation set. We observe that continuing training of the VCN model does not bring any benefit, which indicates that the best VCN model is not obtained at the very end of the training. Another interesting observation is that VCN (W , ct) performs better than VCN (ct), showing the benefit of increasing the model capacity. However, it does not outperform VCN, not even VCN+LCV, confirming the importance of using a valid inner product space. Comparing the result of VCN (1x1 conv), we can further conclude that ensuring the positive definiteness via the Cayley representation is crucial to the performance. We can also find that VCN (Λ, ct) gets a lower AEPE and VCN (P , ct) gets a lower Fl-all compared with vanilla VCN. VCN+LCV combines the advantages of both axis rotation and re-weighting, aiming to address two limitations mentioned in the paper.

Robustness Analysis
To further understand the effect of the LCV module, we evaluate the flow estimation performance under three challenging cases, i.e., 1) illumination changes: we adjust the illumination of the input frames by changing the value of γ, where γ = 1.0 is the original image, γ < 1.0 is for a darker image, and γ > 1.0 is for a brighter image. 2) adding noises: we adjust the standard deviation to control the noise magnitude. and 3) inserting adversarial patches: we borrow the universal adversarial patch [30] that can perform a black-box attack for all optical flow models, and insert patches of different sizes to the input frames.
We compare the VCN model and its variant equipped with LCV. Both two models are trained on the KITTI 2015 training set. For qualitative comparison, we perform the above three types of processing on 194 images with the flow groundtruth from the KITTI 2012 as our test set. As shown in Table 4(a), VCN+LCV consistently outperforms the VCN baseline in all three challenging cases. For better illustration, we visualize the effect on an image from KITTI 2015 test set as shown in Fig. 4. It can be seen that the LCV module can help stabilize the flow prediction around the background trees at the top left corner of the frame under the cases of dark illumination and random noise injection. In the third example, the outline of the car body near the patch circle is better preserved by our model. (See the difference map for details.)

Conclusions
In this work, we introduce a learnable cost volume (LCV) module for optical flow estimation. The proposed LCV module generalizes the standard Euclidean inner product into an elliptical inner product with a symmetric and positive definite kernel matrix. To keep its symmetry and positive definiteness, we use the Cayley representation to re-parameterize the kernel matrix for end-to-end training. The proposed LCV is a lightweight module and can be easily plugged into any existing networks to replace the vanilla cost volume. Experimental results show that the proposed LCV module improves both the accuracy and the robustness of stateof-the-art optical flow models.
Acknowledgement. This work is supported in part by NSF CAREER Grant 1149783. We also thank Pengpeng Liu and Jingfeng Wu for kind help.

A Proofs of Theorems
A.1 Proof of Theorem 1 The Theorem of Cayley representation was first given by Cayley in his paper [5]. However, the old paper is not available online. For convenience, we give a simple proof here.
Proof. First, we validate that the P is a orthogonal matrix. The condition that S ∈ SO * (n) ensures that (I + S) is invertible. Since S is skew-symmetric, so S S = −S 2 = SS . Hence we have = I.
Next, we need to show the uniqueness of the Cayley representation.
Therefore, the skew-symmetric matrix S is uniquely represented by P , which concludes the proof.

A.2 Proof of Theorem 2
Before giving the proof, we would like to recall the definition of connectedness.
Definition 1 (Connectedness) A set of matrices G is said to be connected if for all A and B in G, there exists a continuous path A(t), 0 ≤ t ≤ 1, lying with A(0) = A and A(1) = B.
The above definition of connectedness is actually path connectedness in topology. Now we begin our proof of Theorem 2.
Proof. Since the identity matrix I ∈ SO * (n), it suffices to prove that for any X ∈ SO * (n), there exists a continuous path A(t), 0 ≤ t ≤ 1, such that A(0) = I and A(1) = X. For any X ∈ SO * (n), we have its spectral decomposition where the P ∈ O(n) and 0 ≤ q ≤ n/2, and If we put then the path required is B More Results
Here we capture the screenshot of the ranking results by March 8, 2020.

B.2 More Visualization Results
As shown in Fig. 6 and 7, we compare our method with other methods under the supervised settings. We can observe that the flow boundary of the dragon in Fig. 6, which is predicted by VCN+LCV, is better than the other methods and the flow prediction near the tree (in front of the car) and fence by our method in Fig. 7 is more accurate compared with those of the others. The flow prediction for these pixels are are challenging due to the occlusion. LCV explores more information among channel dimensions, which could help alleviate the problem of occlusion to some extent.

B.3 More Visualization Result on Challenging Cases
We provide three videos showing the effectiveness of our method in three types of challenging cases: 1) illumination change; 2) noise; and 3) adversarial patches. The test videos are from the training set in the KITTI tracking benchmark. We compare the flow results under the normal setting with those under challenging settings. We can observer that the flow results of our model in either one of three challenging cases are temporarily consistent and reasonably good.

B.4 Visualization of the Learned Features
We visualize the feature maps for different eigenvalues in Fig. 8. We find that boundaries of (moving) objects are salient in the feature map corresponding to the max eigenvalue while the min eigenvalue mainly corresponds to background information, which results in more discriminative cost volume and more accurate flow estimation.