{'fraction_non_alphanumeric': 0.03260750629171682, 'fraction_numerical': 0.01119743225006383, 'mean_word_length': 4.757664846703066, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Semi-supervised learning of deep metrics for stereo reconstruction

Deep-learning metrics have recently demonstrated extremely good performance to match image patches for stereo reconstruction. However, training such metrics requires large amount of labeled stereo images, which can be difficult or costly to collect for certain applications. The main contribution of our work is a new semi-supervised method for learning deep metrics from unlabeled stereo images, given coarse information about the scenes and the optical system. Our method alternatively optimizes the metric with a standard stochastic gradient descent, and applies stereo constraints to regularize its prediction. Experiments on reference data-sets show that, for a given network architecture, training with this new method without ground-truth produces a metric with performance as good as state-of-the-art baselines trained with the said ground-truth. This work has three practical implications. Firstly, it helps to overcome limitations of training sets, in particular noisy ground truth. Secondly it allows to use much more training data during learning. Thirdly, it allows to tune deep metric for a particular stereo system, even if ground truth is not available.


Introduction
The stereo reconstruction problem consists in estimating a depth map from two images taken from different viewpoints. The problem has many practical applications in robotics [34], remote sensing [43], and 3D graphics [47].

Related work
Stereo reconstruction algorithms rely on epipolar geometry [18], according to which to every no-occluded point in one stereo view corresponds a point in the other view lying on a line that does not depend on the scene, but only on the optical system. This line is called an epipolar line, and for a calibrated stereo system, it is known for every image point. Furthermore, for a pinhole camera, all the points lying on a given epipolar line in the second view correspond to points lying on a common epipolar line in the first view. Such two epipolar lines are called conjugate.
It is a standard procedure to warp stereo views in order to make conjugate epipolar lines in these views horizontal and vertically aligned. This is called stereo rectification, and in a rectified stereo pair, every point from the first view corresponds to a point shifted horizontally in the second view. The extension of this shift -also known as a disparity -allows to compute the distance to the corresponding 3d point, which is the ultimate goal of the stereo reconstruction.
So at the core of the stereo reconstruction process lies the matching of similar patches in two images along epipolar lines and the estimation of the disparity. It is not a trivial task, since the local appearance of a physical point in the two views might differ due to radiometric and geometric distortions. The patch matching is usually performed using invariant similarity measures and descriptors, also known as features. Historically, the former were more popular for the stereo reconstruction, while the latter were used for matching sparse points of interest.

Similarity measures
The invariant similarity measures [21,19] are popular for stereo reconstruction, probably due to their low computational complexity. The simplest similarity measures are the sum of absolute differences (SAD), and the sum of squared differences (SSD). Zero-mean variants of these methods (ZSAD, ZSSD), as well as sum of absolute gradient differences (GSAD), are invariant to local brightness changes, which can also be achieved by combining SAD and SSD with background subtraction by mean, Laplacian of Gaussian (LoG) [20] or Bilateral filters [4].Non-parametric similarity measures, such as Rank and Census [56] are invariant to arbitrary order-preserving local intensity transformations, and measures such as the Mutual Information (MI) [23] explicitly model the joint intensity distribution in the two images, and are invariant to arbitrary intensity transformations. All these methods are invariant to radiometric distortions only.

Descriptors
Invariant descriptors are popular for sparse point matching, and are designed to be invariant to both radiometric and geometric distortions. They all are either local histograms of oriented image gradients such as SIFT [30], or binary strings of local pairwise pixel comparisons such as BRIEF [9]. Although descriptors are rarely used for stereo, there are some exceptions, such as DAISY [48], which can be efficiently computed densely.
Recently, the community has moved from these fully hand-crafted descriptors to data-driven descriptors, incorporating machine-learning approaches. Most of such descriptors perform discriminative dimensionality reduction either by feature selection, as VGG [45], linear feature extraction, as LDAHash [46], or boosting, as BinBoost [50].

Deep metrics
As for other application domains of machine learning, the current trend is to move beyond "shallow" models, where the learned quantities interact linearly with handdesigned non-linearities, but are not involved in further re-combinations.
Standard deep metric networks have a Siamese architecture, introduced in [8]. They consist of two "embedding" sub-networks with complete weight sharing that join into a common "head". Each embedding subnetwork is convolutional, it takes an image patch as input, and outputs the patch's descriptor. The "head" is usually fully connected, it takes the two descriptors as input, and outputs a similarity measure. The Siamese architecture was firstly used for image patch matching in its classic form in [22]. Later it was shown, that the "head" network may be replaced by a fixed similarity such as L 2 [44] or cosine [58], that the embedding subnetworks may not share weights [57], and, finally, that the explicit notion of a descriptor might not be necessary [57].

Supervised learning of deep metrics
Existing methods for training a Siamese network for patch matching are supervised, using a training set composed of positive and negative examples. Each positive example (respectively negative) is a pair composed of a reference patch and its matching patch (respectively a non-matching one) from another image.
Training either takes one example at the time, positive or negative, and adapts the similarity [44,12,22,57,54], or takes at each step both a positive and a negative example, and maximizes the difference between the similarities, hence aiming at making the two patches from the positive pair "more similar" than the two patches from the negative pair [58,26,6]. This latter scheme is known as "Triplet Contrastive learning." Although the supervised learning of deep metrics works very well, the complexity of the models requires very large labeled training sets which are hard to collect for real applications. Beside, even when such large sets are available, the ground truth is produced automatically from sensors and, thus, usually noisy and/or may suffer from gross errors. This can be mitigated by augmenting the training set with random perturbations [58] or synthetic training data [14,33]. However synthesis procedures are hand-crafted and do not account for the regularities specific to the stereo system and target scene at hand.

Semi-supervised learning
Our work is inspired by Multi-Instance Learning (MIL) [5] and Self-Training [49]. The main idea behind MIL, is to use "coarsely" labeled data, where one label indicates if a group of samples contains at least one positive sample. This allows to deal with low geometrical accuracy, or even the absence of geometrical information and a labeling at the scene level. It has been applied with success to deep learning [53].
Another strategy to relax the requirement for detailed labeling is Self-Training, where the training set is enriched with unlabeled data. As for transductive learning, self-training works by leveraging the information carried by the unlabeled data about the structure of the data population [11,37].
Our most efficient method uses dynamic programming (DP) to regularize the noisy prediction of the metric as it is currently trained. Similar idea appeared in [27], in a different context, to train a deep network to recognize handwritten characters, using wordwise labels to infer character-wise labels. It has also been used to segment automatically sequences of action demonstrations into macro-actions to deal with non-Markovian decision processes [28], and the k-shortest paths algorithm, which is a generalization of dynamic programming to multiple paths, was used to train a person detector from videos with time-sparse groundtruth [3].

Method
We start by formulating in § 3.1 the task of semisupervised deep metric learning for stereo, then in § 3.2 we review the stereo matching problem constraints we consider, and in § 3.3 we describe how we use them to drive the training.

Problem formulation
We are provided with a semi-supervised training set Tr = {(e r , e + , e − ) n } n=1:N . Each training example is a triplet of series of s × s gray-scale patches: • reference patches e r = (p r 1 , p r 2 , .., p r W ) extracted from a horizontal line of a left rectified stereo image, • positive patches e + = (p + 1 , p + 2 , .., p + W ) extracted from the corresponding horizontal in the right rectified stereo image, and where W is the number of patches per line, and N is the number of training examples. In addition to the training set, we are provided with the maximum possible disparity d max , which depends on the optical system and a prior knowledge about the scene.
Our goal is to learn a deep metric S(x, y) such that, for any set of reference e r and positive image patches e + , the row-wise maxima of the similarity matrix S r+ ij = S p r i , p + j correspond to the true matches. Note, that in contrast to [22,57,44,14,54,12,58] in our case each training example is not a pair of patches, but a triplet of series of patches each taken on an horizontal line of a rectified stereo image, so that we can utilize constraints and loss functions defined on such families of patches jointly. Additionally, processing lines as a whole significantly speeds up the training process by allowing to reuse shared computations.

Matching constraints
The stereo matching problem satisfies the following constraints: (E) Epipolar constraint. Every non-occluded reference patch has a matching positive patch [18][239-241p].
(D) Disparity range constraint. The offset of the reference patch index with respect to the matching positive patch index is bounded by a maximum disparity d max . This comes from the stereo system parameters (focal length, pixel size, baseline) and the distance range of the scenes.
(C) Continuity constraint. The offsets of the reference patches indices with respect to the matching positive patch indices are similar for nearby reference patches everywhere except on depth discontinuities [32].
(O) Ordering constraint. The reference patches are ordered on their lines as the matching positive patches on theirs.
These constraints result in a particular shape of the positive similarity matrix, as pictured in Figure 1.

Proposed semi-supervised methods
We developed several semi-supervised methods that use different subsets of the stereo constraints during training. All methods alternate between two steps: (1) improving the metric, given the current estimate of the matches for the positive examples, and (2) recomputing these matches under the constraints, given the current estimate of the metric. They can be used in combination with any deep metric architecture and any gradient based optimization method.
To each of our methods corresponds a loss function optimized in each of the two steps mentioned above. It takes as an input either S r+ , or the three matrices S r+ , S r− and S −+ defined respectively as follows: In the next sections we describe each method in details.

MIL method
This method is inspired by Multi-Instance Learning (MIL) paradigm [5] and uses only the epipolar and the disparity range constraints (E) and (D) from § 3.2. From these two constraints, we know that every nonoccluded reference patch has a matching positive patch in a known index interval, but does not have a matching negative patch. Therefore, for every reference patch, the similarity of the best reference-positive match should be greater than similarity of the best reference-negative match. Our training objective is to push apart these two similarities.
The training loss for the MIL method is where rows = {d max + 1, . . . , W } is a set of rows of the similarity matrix that are guaranteed to have correct matches (see Fig 1), col = {1, . . . , W − d max } is a set of valid columns of the similarity matrix that are guaranteed to have correct matches, W is the number of patches in a horizontal line of rectified image, and µ is a loss margin. Note that the disparity range constraint is taken into account automatically, if we use the similarity matrices as defined in § 3.3. Experiments shows that the method learns metrics insensitive to small shifts from the optimal match. This problem results in blocky shape of a similarity matrix, where blocks correspond to the areas where the metric is not able to find unique match. This issue motivates the CONTRASTIVE method described in the following section.

CONTRASTIVE method
This method uses the epipolar, the disparity range, and the uniqueness constraints (E), (D), and (U) from § 3.2.
From the epipolar and the disparity range constraints we know that every non-occluded reference patch has a matching positive patch in a known index interval. Furthermore, according to the uniqueness constraint the matching positive patch is unique. Therefore, for every patch, the similarity of the best match should be greater than the similarity of the second best match. Our training objective is to push apart these two quantities.
The training loss for this CONTRASTIVE method is whereŜ is a similarity matrix with masked out rowwise maxima,Š is a similarity matrix with masked out column-wise maxima. To mask out elements of similarity of matrix, we simply substitute them with −∞. Experiments show that this method suffers from a problem opposite to the one exhibited by the MIL method: it produces over-sharpened metric, sensitive even to small shifts from the exact match. This is also detrimental to the performance, since our goal is to find metric invariant to small geometric transformations, such as shift. We solved the problem by masking out all spatial neighbors withing t sup radius from the maximas inŜ and inŠ. See the supplementary materials for details.

MIL-CONTRASTIVE method
As we showed in previous sections, the CON-TRASTIVE and the MIL methods have complementary properties and use the stereo constraints in orthogonal way. Therefore we can combine them into a new method that we call MIL-CONTRASTIVE.

CONTRASTIVE-DP method
This method uses all constraints listed in § 3.2. The only difference with CONTRASTIVE is that it finds the best match under (C) and (O) using dynamic programming (DP), instead of independent maxima.
Formally, it solves where P is the set of paths {(i n , j n )} n=1:M which are continuous in the following sense: ∀n > 1, (i n , j n ) − (i n−1 , j n−1 ) ∈ {(0, 1), (1, 0), (1, 1)}, Which means that only down, right and diagonal steps are allowed. This enforces the continuity and the ordering constraints (C) and (O) in the solution. Notice also that we search for a path that has maximum average energy rather than maximum total energy to prevent a bias toward longer paths and consequently smaller disparities.
Given the best match-path p * found by the dynamic programming we define our loss function as whereS is a similarity matrix where all neighbors of elements belonging to p * withing radius t sup are masked out by setting their values to −∞.
The best match-path computed by the dynamic programming might contain vertical and horizontal segments. These segments correspond to patches that are occluded by foreground objects on one of the views, and thus do not have correct matches. Therefore, in our experiments we ignore vertical and horizontal segments longer than t occ during the learning. For more details, please refer to the supplementary materials.

Experiments
Our experiments were done in the Torch framework [13]. Optimization was performed with the ADAM method with standard settings, using minibatches of size equal to the training images height, and no data augmentation of any sort. The initialization of weights and biases of our deep metric network was done in standard way by random sampling from zero-mean uniform distribution.
We guarantee reproducibility of all experiments in this section by using only available data-sets, and making our code available online under open-source license after publications.
KITTI'12 and KITTI'15 data-sets each consist of 200 training and 200 test rectified stereo pairs of resolution 1226×370 acquired from cars moving around a city. About 30% of the pixels in the training set are supplied with a ground truth disparity acquired by a laser altimeter with error less than 3 pixels. The disparity range is about 230 pixels. Each data-set is supplied with an extension (respectively KITTI'12-EXT and KITTI'15-EXT) that contains 19 additional stereo pairs for each scene, without ground truth disparity. This allows us to use 40× more training data for the semi-supervised learning than for the supervised (actually even more, considering that only about 30% of pixels in the training set have labels).
Middlebury data-set (MB) consists of 60 training and 30 test rectified stereo pairs. The images are acquired by different stereo systems and contain different artificial scenes. Their resolution varies from 380×430 to 3000×2000, and their disparity ranges vary from 30 to 800 pixels. The training images are provided with a dense ground truth disparity acquired by structured light system with error less that 0.2 pixels.

Performance measure
To estimate the performance of deep metrics we compute a prediction error rate defined as the proportion of non-occluded patches for which the predicted disparity is off by more than 3 pixels.
The motivation behind this work is to improve the metric as a mean to match patches in a stand-alone manner, as we have not taken into account the interplay with the additional post-processing that may be applied in a complete stereo pipeline. Performance regarding this main objective is measured by picking the patch with the largest similarity among the patches that belong to a valid disparity range on the epipolar line. We call this the winner-take all (WTA) error rate.
A second measure is the error rate of a complete stereo pipeline with plugged-in deep metric. This is a performance measure of direct practical interest, although not the objective we optimize during our training.

Deep metric architecture
The main contribution of this work is a new semisupervised training method, not deep metric architecture, therefore we simply adopt the overall architecture of well performing MC-CNN fst network from [58], shown in Table 1, and substitute their learning method with ours.

Comparison of semi-supervised methods
In this experiment we compare the performance of the proposed semi-supervised methods. We performed comparison on KITTI'12 data-set using the winnertake-all (WTA) error (see § 4.2). The results of the experiments are shown in Table 2.  The main conclusion is that semi-supervised methods that use more stereo constraints during learning perform better. For example, the MIL, that uses only the epipolar and the disparity range constraints, has larges WTA error, whereas the CONTRASTIVE-DP, that uses the epipolar, the disparity range, the continuity, the uniqueness and the ordering constraints has smallest WTA error.

Method
In all following sections, we use the best performing CONTRASTIVE-DP method only, and refer to it as MC-CNN-SS, where SS stands for semi-supervised.

Comparison with supervised method
In this section, we compare the proposed semisupervised method with our reference fully supervised deep-metric baseline [58] on the three different sets, using the winner-take-all (WTA) error (see § 4.2).
The results are shown in Table 3. As we see, our method outperforms the supervised method in terms of WTA error across two sets, and does virtually as well on the third. This is remarkable considering the fact that our method does not use ground truth disparity during learning.
The success of our method in case of KITTI'12 and KITTI'15 sets can be attributed to the fact that these sets have large amount of unlabeled stereo data, that can be used by our method. In fact, these sets have more than 40× more unlabeled data than labeled training data.
In case of MB data-set our method does not have this advantage over the supervised method. The set has only 30% more unlabeled training data than the labeled training data. This is probably the reason why our method shows slightly worse performance on this dataset than compared to the supervised method.  Table 3: Comparison of our semi-supervised learning method with the fully supervised baseline using the same network architecture [58]. Smallest WTA errors are shown in bold. Our semi-supervised method outperforms the baseline in terms of WTA error across two sets, and does virtually as well on the third. This is remarkable since in contrast to the supervised method, our does not use ground truth disparity during learning. For reference, the two bottom rows show the performance of two standard similarity measures and descriptors. Note that following the setup of [58], the patches used as input to the deep-learning methods are of size 9 × 9 for KITTI'12,'15, and 11 × 11 for MB.

Stereo benchmarking
In this section we investigate how well our semisupervised deep metric performs when it is combined with the complete stereo pipeline. For that we plug it in the stereo pipeline from [58], and tuned the parameters of the pipeline using simple coordinate descent method, starting from the default values of [58]. Note that we used specific metric and pipeline parameters for each data-set. Then we computed disparity maps for the test sets with withheld ground truth, and uploaded the results to the evaluation web sites for the respective datasets [1,2]. The obtained evaluation results are shown in Tables 5, 6 and 4. As we can see, results with our metric trained without ground truth during training are very close to the results of the fully supervised method across all benchmarks.
Those are very encouraging results, given in particular that we did not optimize the deep metric and the pipeline parameters together, and considering the performance in the winner-take-all setup of § 4.5.
Regarding the processing time, note that the network structure used for our method is identical to that of MC-CNN-fst [58], except for the pipeline parameters. The difference in processing times in Tables 5, 6 and 4 is only due to the hardware differences.

What does deep metric learn?
In Figure 2 we show positive similarity matrices before and after the training with MC-CNN-SS on KITTI'12 data-set. While one can not visually distinguish the best match in the similarity matrices before the training, it becomes clearly visible after. This suggests that the training improves discriminative ability of the deep metric.
In Figure 3 we show failure cases of learned deep metric. Most of the failures happen when the ground    The dark elements in the similarity matrices correspond to the higher similarities. WTA error before training is 42.01%, and 14.61% after. Note that before the training we can not visually distinguish the best matches in the similarity matrices, while after the learning they are clearly visible.
with a repetitive texture, or an area with a horizontal edge.
Notably, some failures are triggered by probable errors in the ground truth. These errors might worsen outcomes of the supervised learning but does not affect outcomes of our semi-supervised learning, since it does not use the ground-truth.

Generalization across data-sets
In this experiment, we study how deep metric trained using our semi-supervised method on one data-set performs on another data-sets in terms of WTA error. From Table 7 it appears that a metric always performs better when the train and test population come from the same data-set. This confirms that our semi-supervised metric has great practical value: it allows to tune descriptor for a particular stereo system at hands, even if data-set with ground-truth is not available.

Conclusion
We proposed novel semi-supervised techniques for training patch similarity measures for stereo reconstruc-1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Figure 3: Failure cases of the deep metric trained with our MC-CNN-SS method on the KITTI data-set. For each example the three patches displayed correspond to (from top to bottom): the reference patch, the predicted match and the ground-truth match. Note that as expected, the ground truth and the predicted matches are often visually indistinguishable. This happens if the reference patch is from an area with almost horizontal edges (3, 6, 13), a flat image area (4,5,10), or an area with repetitive texture. Some failures are triggered by likely errors in the ground truth labeling (2,12,14,16).  Table 7: Generalization error across data-sets. The smallest WTA errors, shown in bold correspond to the cases when the train and test population come from the same data-set. This confirms that our semi-supervised metric has great practical value: it tune the descriptors for a particular stereo system, even if no ground truth is available.
tion. These techniques allow to train with data-sets for which ground truth is not available, by relying on simple constraints coming from properties of the optical sensor, and from a rough knowledge about the scenes to process. We applied this framework to the training of a "deep metric", that is a deep siamese neural-network that takes two patches as an input and predicts a similarity measure. Benchmarking on standard data-sets shows that the resulting performance is as good or better than published results with the same network trained on the same but fully labeled data-sets (see Table 3).
This very good performance can be explained by the strong redundancy of a fully labeled data-set, due to the continuity of surfaces, coupled with inevitable labeling errors. The latter can degrade the performance resulting from a fully supervised training process, and could only be mitigated by using a prior knowledge about the regularity of the labeling, similar to the constraints we use.
The techniques we propose open the way first to using stereo reconstruction based on deep metrics for data-sets for which no ground-truth exists, such as planetary measurements. Second, it will allow the training of larger neural networks, with very large unlabeled data-sets. Our experiments show that the network that we are using in our experiments does benefit from an one order of magnitude more training samples, than it is available to supervised method as shown in Table 3. We expect that this effect will be even more significant if we use our training method with larger networks that would over-fit existing labeled training sets.