Semi-supervised learning of deep metrics for stereo reconstruction
% background 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. % contribution 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. % experimental support 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. % practical implications 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.
cnnmars.tex
 % delete comments to render supplementary in overleaf
 % \input{supplementary.tex}
 
 \documentclass[10pt,twocolumn,a4paper]{article}

 \usepackage{times}
 \usepackage{epsfig}
 \usepackage{graphicx}
 \usepackage{amsmath}
 \usepackage{amssymb}
 \usepackage{multirow} 	 % combine rows
 \usepackage[super]{nth} % 1st 2nd nth

% adding operator for dynamic programming
\newcommand{\argmax}{\operatornamewithlimits{argmax}}

% Include other packages here, before hyperref.
\usepackage{scalerel,stackengine,amsmath}

\usepackage{titling}
\usepackage{authblk}

\setlength{\droptitle}{-9em}   % This is your set screw

\newcommand\equalhat{\mathrel{\stackon[1.5pt]{=}{\stretchto{%
    \scalerel*[\widthof{=}]{\wedge}{\rule{1ex}{3ex}}}{0.5ex}}}}
\usepackage{color, colortbl} % highlight row of tables
%\definecolor{lightgray}{rgb}{0.9,0.9,0.9}
\definecolor{darkgray}{rgb}{0.7,0.7,0.7}

% default figures path
%\graphicspath{{figures/}}

% If you comment hyperref and then uncomment it, you should delete
% egpaper.aux before re-running latex.  (Or just hit 'q' on the first latex
% run, let it finish, and you should be clear).
\usepackage[pagebackref=true,breaklinks=true,colorlinks,bookmarks=false]{hyperref}

\begin{document}

%%%%%%%%% TITLE
\date{}
\title{Semi-supervised learning of deep metrics for stereo reconstruction}

\author[1]{Stepan Tulyakov \thanks{stepan.tulyakov@epfl.ch}}
\author[1]{Anton Ivanov}
\affil[1]{eSpace Center, Swiss Federal Institute of Technology in Lausanne}
\author[2]{Francois Fleuret}
\affil[2]{Computer Vision and Learning Group, Idiap Research Institute and Swiss Federal Institute of Technology in Lausanne}


\maketitle
%\thispagestyle{empty}

% %%%%%%%%% ABSTRACT
\begin{abstract}
% background
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.

% contribution
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.

% experimental support
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.

% practical implications
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.
\end{abstract}

% %%%%%%%%% BODY TEXT
\section{Introduction}\label{sec: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~\cite{Menze2015}, remote sensing~\cite{Shean2016}, and 3D graphics~\cite{Strecha2010}.

% current research and our place
It has been heavily investigated for several decades~\cite{Scharstein2001}, and recent developments focused on designing high-order, region-based and object-specific priors~\cite{Zhang2015, Chakrabarti2015, Yamaguchi2014, Guney2015, Kim2016, Li2016, Vogel2015, Vogel2014}, and improving efficiency of large scale stereo~\cite{Psota2015, Kowalczuk2012,Geiger2010,Barron2016}. Perhaps the most significant recent breakthrough was to use deep metrics~\cite{Chen2015, Zbontar2015}. It led to considerable gains in processing speed and reconstruction accuracy (see Tables~\ref{tab:benchmarking_mb}, \ref{tab:benchmarking_kitti12}, and ~\ref{tab:benchmarking_kitti15}). Our work improves upon this line of research.

\section{Related work}\label{sec:related_work}

% epipolar geometry
Stereo reconstruction algorithms rely on \textit{epipolar geometry}~\cite{Hartley2003}, 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 \textit{epipolar line}, and for a \emph{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 \textit{conjugate}.

% rectification, disparity
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 \textit{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 \textit{disparity} -- allows to compute the distance to the corresponding 3d point, which is the ultimate goal of the stereo reconstruction.

% patch matching
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 \textit{invariant similarity measures} and \textit{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.

\subsection{Similarity measures}
% similarity measures
The invariant similarity measures~\cite{Hirschmuller2007,Hirschm2008} 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)~\cite{Hirschmuller2002} or Bilateral filters~\cite{Ansar2004}.Non-parametric similarity measures, such as Rank and Census~\cite{Zabih1994} are invariant to arbitrary order-preserving local intensity transformations, and measures such as the Mutual Information~(MI)~\cite{Kim2003} 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.
%
\subsection{Descriptors}
% 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~\cite{Lowe2004}, or binary strings of local pairwise pixel comparisons such as BRIEF~\cite{Calonder2012}. Although descriptors are rarely used for stereo, there are some exceptions, such as DAISY~\cite{Tola2010}, 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~\cite{Simonyan2013}, linear feature extraction, as LDAHash~\cite{Strecha2012}, or boosting, as BinBoost~\cite{Trzcinski2012}.

\subsection{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 hand-designed non-linearities, but are not involved in further re-combinations.

% Deep metrics - are most successful in stereo and sparse point matching
The resulting ``deep metrics''
%% , often combining descriptors and similarity measures~\cite{Zagoruko2015, Zbontar2015, Chen2015}, 
demonstrate extremely good performance compared to other similarity measures and descriptors both for sparse point matching~\cite{Jahrer2008, Fischer2014, Simo-Serra2015, Zagoruko2015, XufengHan2015} and stereo reconstruction~\cite{Zbontar2015, Chen2015}.

% architectures of deep metric
Standard deep metric networks have a Siamese architecture, introduced in~\cite{Bromley94}. They consist of two ``embedding'' sub-networks with complete weight sharing that join into a common ``head''. Each embedding sub-network 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~\cite{Jahrer2008}. Later it was shown, that the ``head'' network may be replaced by a fixed similarity such as $L^2$~\cite{Simo-Serra2015} or cosine~\cite{Zbontar2015}, that the embedding sub-networks may not share weights~\cite{Zagoruko2015}, and, finally, that the explicit notion of a descriptor might not be necessary~\cite{Zagoruko2015}.

\subsection{Supervised learning of deep metrics}

% supervised training schemes
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.

% siamese and triplet training
Training either takes one example at the time, positive or negative, and adapts the similarity~\cite{Simo-Serra2015, Chen2015, Jahrer2008, Zagoruko2015, XufengHan2015}, 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~\cite{Zbontar2015, Kumar2016, Balntas2016}. This latter scheme is known as ``Triplet Contrastive learning.''

% problem with supervised training
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.
% current solutions and their problems
This can be mitigated by augmenting the training set with random perturbations~\cite{Zbontar2015} or synthetic training data~\cite{Fischer2014,Mayer2016}. However synthesis procedures are hand-crafted and do not account for the regularities specific to the stereo system and target scene at hand.

\subsection{Semi-supervised learning}

% multi-instance learning
Our work is inspired by Multi-Instance Learning (MIL)~\cite{Babenko2008} and Self-Training~\cite{Triguero2013}. 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~\cite{Wu2015}.

% self-training
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~\cite{Chen2013, Reed2015}.

% dp use
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~\cite{LeCun1998}, in a different context, to train a deep network to recognize handwritten characters, using word-wise 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~\cite{Lefakis2014}, 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 ground-truth~\cite{All2011}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Method}\label{sec:method}

We start by formulating in \S~\ref{sec:problem} the task of semi-supervised deep metric learning for stereo, then in \S~\ref{sec:constraints} we review the stereo matching problem constraints we consider, and in \S~\ref{sec:methods} we describe how we use them to drive the training.

\subsection{Problem formulation}
\label{sec:problem}

% what is given
We are provided with a semi-supervised training set $\mathbf{Tr}=\{ (\mathbf{e}^r, \mathbf{e}^+, \mathbf{e}^- )_n \}_{n=1:N} $. Each training example is a triplet of series of $s\times s$ gray-scale patches:
\begin{list}{\labelitemi}{\leftmargin=1.25em}
\itemsep0em
\item \textit{reference patches} $ {\mathbf{e}^{r}=(p^r_1,p^r_2,..,p^r_W)} $ extracted from a horizontal line of a left rectified stereo image,
\item \textit{positive patches} $ {\mathbf{e}^{+}=(p^+_1,p^+_2,..,p^+_W)} $ extracted from the corresponding horizontal in the right rectified stereo image, and
\item \textit{negative patches} $ {\mathbf{e}^{-}=(p^-_1,p^-_2,..,p^-_W)} $ extracted from another horizontal line of a right rectified stereo image,
\end{list}
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.

% what is required
Our goal is to learn a deep metric $S(x, y)$ such that, for any set of reference $\mathbf{e}^r$ and positive image patches $\mathbf{e}^+$, the row-wise maxima of the \textit{similarity matrix} $ \mathbf{S}^{r+}_{ij}=S\left(p^r_i, \, p^+_j\right)$ correspond to the true matches.

% why epipolars instead of patches
Note, that in contrast to~\cite{Jahrer2008,Zagoruko2015,Simo-Serra2015,Fischer2014,XufengHan2015,Chen2015,Zbontar2015} 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.

\subsection{Matching constraints}
\label{sec:constraints}

The stereo matching problem satisfies the following constraints:
\begin{list}{\labelitemi}{\leftmargin=1.25em}
\itemsep0em

\item[(E)] \textbf{Epipolar constraint.} Every non-occluded reference patch has a matching positive patch~\cite{Hartley2003}[239-241p].

\item[(D)] \textbf{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.

\item[(U)] \textbf{Uniqueness constraint.} The matching positive patch is unique~\cite{Marr1979}.

\item[(C)] \textbf{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~\cite{Marr1979}.

\item[(O)] \textbf{Ordering constraint.} The reference patches are ordered on their lines as the matching positive patches on theirs.
\end{list}

These constraints result in a particular shape of the positive similarity matrix, as pictured in Figure~\ref{fig:constraints}.

\begin{figure}[hbtp]
\centering
\begin{minipage}{.5\textwidth}
  \centering
  \includegraphics[width=0.95\textwidth]{constraints.eps}
  \caption{Positive similarity matrix. The bold line corresponds to the optimal matches that satisfy the stereo constraints. Elements within the disparity range are shown in gray. Note that there are no matches for some points on the reference and positive epipolar lines.}
 \label{fig:constraints}
\end{minipage}%
\end{figure}

\subsection{Proposed semi-supervised methods}
\label{sec:methods}

% explain how methods can be used
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) re-computing 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 $\mathbf{S}^{r+}$, or the three matrices  $\mathbf{S}^{r+}$, $\mathbf{S}^{r-}$ and $\mathbf{S}^{-+}$ defined respectively as follows:
\begin{align}
S^{r+}_{ij} & = \left\{ \begin{array}{ll} S(p_i^r, p_j^+) & 0\le i-j\le d_{max} \\ -\infty & otherwise \\ \end{array} \right.\\
S^{r-}_{ij} & = \left\{ \begin{array}{ll} S(p_i^r, p_j^-) & 0\le i-j\le d_{max} \\ -\infty & otherwise \\ \end{array} \right.\\
S^{-+}_{ij} & = \left\{ \begin{array}{ll} S(p_i^-, p_j^+) & 0\le i-j\le d_{max} \\ -\infty & otherwise \\ \end{array} \right.
\end{align}
In the next sections we describe each method in details.

\subsubsection{MIL method}\label{sec:mil}

% what constraints are used
This method is inspired by Multi-Instance Learning (MIL) paradigm~\cite{Babenko2008} and uses only the epipolar and the disparity range constraints (E) and (D) from \S~\ref{sec:constraints}.

% explain intuition
From these two constraints, we know that every non-occluded 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.

% formalization
The training loss for the MIL method is
%
%% \vspace*{-1em}
%
\begin{multline}\label{eq:mil}
\!\!\!\! \frac{1}{|\mathbf{rows}|} \sum_{i \in \mathbf{rows}} \max(0, -\max_jS^{r+}_{ij} + \max_jS^{r-}_{ij} + \mu) \ \ + \\
\frac{1}{|\mathbf{cols}|} \sum_{j \in \mathbf{cols}}\max(0, -\max_iS^{r+}_{ij} + \max_iS^{-+}_{ij} + \mu),
\end{multline}
%
where
%
% $ \max_{j}S_{ij} $ is a vector of row-wise maxima of the similarity matrix, $ \max_{i}S_{ij} $ is a vector of col-wise maxima of the similarity matrix,
$ \mathbf{rows} = \{d_{max}+1, \dots, W \} $ is a set of  rows of the similarity matrix that are guaranteed to have correct matches (see Fig~\ref{fig:constraints}), $ \mathbf{col} = \{1, \dots, 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 $ \mu $ is a loss margin. Note that the disparity range constraint is taken into account automatically, if we use the similarity matrices as defined in \S~\ref{sec:methods}.

% problem with the metric
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.

\subsubsection{CONTRASTIVE method}
\label{sec:contrastive}

% what constraints are used
This method uses the epipolar, the disparity range, and the uniqueness constraints (E), (D), and (U) from \S~\ref{sec:constraints}.

% intuition
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.

% formalization
The training loss for this CONTRASTIVE method is
\begin{multline}\label{eq:contrastive}
\!\!\!\! \frac{1}{|\mathbf{rows}|} \sum_{i \in \mathbf{rows}} \max(0, -\max_jS^{r+}_{ij} + \max_{j}\hat{S}^{r+}_{ij} + \mu) \ \ + \\
\frac{1}{|\mathbf{cols}|} \sum_{j \in \mathbf{cols}}\max(0, -\max_iS^{r+}_{ij} + \max_i {\check{S}}^{r+}_{ij} + \mu),
\end{multline}
where $ \hat{\mathbf{S}} $ is a similarity matrix with masked out row-wise maxima, $ {\check{\mathbf{S}}} $ is a similarity matrix with masked out column-wise maxima. To mask out elements of similarity of matrix, we simply substitute them with $ -\infty $.

% over-sharpening problem and solution
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 $ \hat{\mathbf{S}} $ and in $ {\check{\mathbf{S}}} $. See the supplementary materials for details.

\subsubsection{MIL-CONTRASTIVE method}
\label{sec:mil_contrastive}

As we showed in previous sections, the CONTRASTIVE 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.

\subsubsection{CONTRASTIVE-DP method}
\label{sec:contrastive_dp}

% what constraints are used
This method uses all constraints listed in \S~\ref{sec:constraints}. 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
\begin{equation}\label{eq:dprog_objective}
p^* = \argmax_{p \in {\mathcal P}} \frac{1}{|p|}\sum_{(i, j) \in p } \mathbf{S}^{r+}_{ij}, \\
\end{equation}
where ${\mathcal P}$ is the set of paths $\{ (i_n, j_n) \}_{n=1:M}$
which are continuous in the following sense:
%
%% \begin{equation}\label{eq:path}
%% \begin{array}{l}
\begin{align*}
&\forall n\!>\!1, (i_n, j_n) - (i_{n-1},j_{n-1}) \in \{ (0,1), (1,0), (1,1) \}, \\
&\text{and} \ \ (i_1, j_1) \in \{ 1 \} \times [1, d_{max}].
%% \end{array}
\end{align*}
%% \end{equation}
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
%\begin{multline}\label{eq:contrastive_dp}
\begin{align}\label{eq:contrastive_dp}
& \frac{1}{|p^*|} \sum_{(i,j) \in p^*} \max(0, -S^{r+}_{ij} + \max_k\tilde{S}^{r+}_{ik} + \mu)+ \nonumber \\ 
& \frac{1}{|p^*|} \sum_{(i,j) \in p^*}\max(0, -S^{r+}_{ij} + \max_l\tilde{S}^{r+}_{lj} + \mu),
\end{align}
%\end{multline}
where $ \tilde{\mathbf{S}} $ is a similarity matrix where all neighbors of elements belonging to $ p^* $ withing radius $ t_{sup} $ are masked out by setting their values to $-\infty$.

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.

\section{Experiments}

Our experiments were done in the Torch framework~\cite{Collobert2011}. Optimization was performed with the ADAM method with standard settings, using mini-batches 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.

\subsection{Data-Sets}

% Introduce data-sets
In our experiments we use three popular benchmark data-sets: KITTI'12~\cite{Geiger2012}, KITTI'15~\cite{Menze2015} and Middlebury~(MB)~\cite{Scharstein2001,Scharstein2003, Scharstein2007, Hirschmuller2007, Scharstein2014}. These data-sets have online scoreboards~\cite{KITTI, MB}, showing comparative performance of all participating stereo methods.

 %% Below we give short description of the data-sets.

% KITTI
KITTI'12 and KITTI'15 data-sets each consist of 200 training and 200 test rectified stereo pairs of resolution 1226$\times$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$\times$ 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$\times$430 to 3000$\times$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.

\subsection{Performance measure}\label{sec: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.

% winner-takes-all vs pipeline error
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 \emph{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.

\subsection{Deep metric architecture}

% explain metric
The main contribution of this work is a new semi-supervised training method, not deep metric architecture, therefore we simply adopt the overall architecture of well performing MC-CNN~fst network from~\cite{Zbontar2015}, shown in Table~\ref{tab:metric_architecture}, and substitute their learning method with ours.  
\begin{table}[ht!]
\resizebox{\columnwidth}{!}{%
\begin{tabular}{lll}
\hline
 \textbf{Parameter}           & \textbf{KITTI'12,15} & \textbf{MB} \\
\hline
 Number of CNN layers         & 4                    & 5                         \\
 Number of features per layer & 64                   & 64                        \\
 Receptive field              & 3x3x64               & 3x3x64                    \\
 Activation function          & ReLU                 & ReLU                      \\
 Equivalent patch size        & 9x9                  & 11x11                     \\
 Similarity metric            & Cosine               & Cosine                    \\
\hline
\end{tabular}
}
\vspace{1mm}
\caption{Network architectures for deep metric from~\cite{Zbontar2015} that we use in our experiments.}\label{tab:metric_architecture}
\end{table}

\subsection{Comparison of semi-supervised methods}
\label{sec:compare_semisupervised_method}

% goal of experiment
In this experiment we compare the performance of the proposed semi-supervised methods. We performed comparison on KITTI'12 data-set using the winner-take-all (WTA) error (see \S~\ref{sec:performance-measure}). The results of the experiments are shown in Table~\ref{tab:compare_semisupervised_methods}.

\begin{table}[ht!]
\resizebox{\columnwidth}{!}{%
\begin{tabular}{lll}
\hline
\textbf{Method} & \textbf{WTA error, [$\%$]} & \textbf{Time, [hr]} \\
\hline
MIL 	   			 	    			& 18.45  & 45  \\
CONTRASTIVE        						& 17.63  & 30  \\
MIL-CONTRASTIVE    						& 16.12  & 65  \\
\textbf{CONTRASTIVE-DP} 				& \textbf{14.61}  & \textbf{68} \\
\hline
\end{tabular}
}
\vspace{1mm}
\caption{Comparison of the proposed semi-supervised learning methods on KITTI'12 set. All methods are used to train the same network architecture. The CONTRASTIVE-DP method, shown in bold, uses all the constraints during learning and achieves the smallest WTA error. Notice that in general increasing the number of constraints increases performance.}\label{tab:compare_semisupervised_methods}
\end{table}

% performance vs number of constraints
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.

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.

\subsection{Comparison with supervised method}\label{sec:comp-with-superv}

In this section, we compare the proposed semi-supervised method with our reference fully supervised deep-metric baseline~\cite{Zbontar2015} on the three different sets, using the winner-take-all (WTA) error (see \S~\ref{sec:performance-measure}).

The results are shown in Table~\ref{tab:comparision_to_supervised}. 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\times$ 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.

\begin{table}[ht!]
\resizebox{\columnwidth}{!}{%
%% \small
\begin{tabular}{llll}
\hline
\multirow{2}{*}{\textbf{Method}}& \multicolumn{3}{c}{\textbf{WTA error, [\%]}} \\
								& \textbf{KITTI'12} & \textbf{KITTI'15} & \textbf{MB}\\
\hline
MC-CNN~fst~\cite{Zbontar2015}	& 15.44 & 15.38 & \textbf{29.94}  \\
MC-CNN-SS~fst (ours)  & \textbf{13.90} & \textbf{14.08} & 30.06 \\
\hline
CENSUS~9x9~\cite{Zabih1994}     & 53.52 & 50.35 & 64.53 \\
AD~9x9            				& 32.36 & 30.67 & 59.39 \\
% DAISY\footnote{Authors implementation \url{http://cvlab.epfl.ch/software/daisy}, accessed 11/11/2016}~30x30~200F~\cite{Tola2010}           & 12.63 & 13.94 & 43.63 \\
% DSIFT\footnote{VLFeat implementation \url{http://www.vlfeat.org/overview/dsift.html}, accessed 11/11/2016}~12x12~128F~\cite{Lowe2004} & 14.01 &  13.44  & 35.18 \\
\hline
\end{tabular}
}
\caption{Comparison of our semi-supervised learning method with the fully supervised baseline using the same network architecture~\cite{Zbontar2015}. 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~\cite{Zbontar2015}, the patches used as input to the deep-learning methods are of size $9 \times 9$ for KITTI'12,'15, and $11 \times 11$ for MB.}\label{tab:comparision_to_supervised}
\end{table}

\subsection{Stereo benchmarking}

In this section we investigate how well our semi-supervised deep metric performs when it is combined with the complete stereo pipeline. For that we plug it in the stereo pipeline from~\cite{Zbontar2015}, and tuned the parameters of the pipeline using simple coordinate descent method, starting from the default values of~\cite{Zbontar2015}. 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 data-sets\cite{KITTI,MB}. The obtained evaluation results are shown in Tables \ref{tab:benchmarking_kitti12}, \ref{tab:benchmarking_kitti15} and \ref{tab:benchmarking_mb}. 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 \S~\ref{sec:comp-with-superv}.

Regarding the processing time, note that the network structure used for our method is identical to that of MC-CNN-fst~\cite{Zbontar2015}, except for the pipeline parameters. The difference in processing times in Tables \ref{tab:benchmarking_kitti12}, \ref{tab:benchmarking_kitti15} and \ref{tab:benchmarking_mb} is only due to the hardware differences.
\begin{table}[ht!]
\resizebox{\columnwidth}{!}{%
\begin{tabular}{ m{0.01\columnwidth} m{0.13\columnwidth} m{0.37\columnwidth}  m{0.33\columnwidth}   m{0.16\columnwidth} }
\hline
\textbf{\#} & \textbf{Date} & \textbf{Algorithm} & \textbf{Pipeline Err, [\%]} & \textbf{Time, [s]}\\
\hline
1 & 01/19/15 & NTDE~\cite{Kim2016} & 7.62 & 300 \\
2 & 08/28/15 & MC-CNN~acrt~\cite{Zbontar2015} & 8.29 & 254 \\
3 & 11/03/15 & MC-CNN+RBS ~\cite{Barron2016} & 8.62 & 345 \\
\textbf{4} & \textbf{01/26/16} & \textbf{MC-CNN~fst~\cite{Zbontar2015}} & \textbf{9.69} & \textbf{2.94} \\
\textbf{5} & \textbf{14/11/16} & \textbf{MC-CNN-SS~(ours)} & \textbf{12.3} & \textbf{5.59}\\
6 & 10/13/15 & MDP~\cite{Li2016} & 12.6 & 130 \\
7 & 04/19/15 & MeshStereo~\cite{Zhang2015} & 13.4 & 146  \\
\hline
\end{tabular}
}
\vspace{1mm}
\caption{MB benchmark~\cite{MB} snapshot from 14/11/2016 with published methods (default view). Methods ranked 1, 2, 3, 4 and 5 use deep metrics for stereo matching. Note that our semi-supervised method MC-CNN-SS, shown in bold, that does not use ground truth data during training, has an error rate very similar to that of the supervised MC-CNN~fst method, also shown in bold, trained with ground truth data. }\label{tab:benchmarking_mb}
\end{table}

\begin{table}[ht!]
\resizebox{\columnwidth}{!}{%
\begin{tabular}{  m{0.01\columnwidth} m{0.13\columnwidth} m{0.37\columnwidth}  m{0.33\columnwidth}   m{0.16\columnwidth} }
\hline
\textbf{\#} & \textbf{Date} & \textbf{Algorithm} & \textbf{Pipeline Err, [\%]} & \textbf{Time, [s]}\\
\hline
1 & 27/04/16 & PBCP~\cite{Seki2016} & 2.36 & 68 \\
2 & 26/10/15 & Displets v2~\cite{Guney2015} & 2.37 & 265 \\
3 & 21/08/15 & MC-CNN acrt~\cite{Zbontar2015} & 2.43 & 67 \\
4 & 30/03/16 & cfusion~\cite{Ntouskos2016} & 2.46 & 70 \\
5 & 16/04/15 & PRSM~\cite{Vogel2015} & 2.78 & 300 \\
\textbf{6} & \textbf{21/08/15} & \textbf{MC-CNN fst~\cite{Zbontar2015}} &\textbf{2.82} & \textbf{0.8} \\
7 & 03/08/15 & SPS-st~\cite{Yamaguchi2014} & 2.83 & 2  \\
\textbf{8} & \textbf{14/11/16} & \textbf{MC-CNN-SS~(ours)} & \textbf{3.02} & \textbf{1.35}\\
9 & 03/03/14 & VC-SF~\cite{Vogel2014} & 3.05 & 300 \\
\hline
\end{tabular}
}
\vspace{1mm}
\caption{KITTI'12 benchmark~\cite{KITTI} snapshot from 14/11/2016 with published  methods (default view). Methods ranked 1, 2, 3, 4, 6, and 7 use deep metrics for stereo matching. Note that our semi-supervised method MC-CNN-SS, shown in bold, that does not use ground truth data during training, has an error rate very similar to that of the supervised MC-CNN~fst method, also shown in bold, trained with ground truth data. Since the MC-CNN~fst method does not appear on KITTI'12 evaluation table, due to restrictions on the number of results for a single paper, we borrowed it from ~\cite{Zbontar2016}}\label{tab:benchmarking_kitti12}
\end{table}

\begin{table}[ht!]
\resizebox{\columnwidth}{!}{%
\begin{tabular}{   m{0.01\columnwidth} m{0.13\columnwidth} m{0.37\columnwidth}  m{0.33\columnwidth}   m{0.16\columnwidth}  }
\hline
\textbf{\#} & \textbf{Date} & \textbf{Algorithm} & \textbf{Pipeline Err, [\%]} & \textbf{Time, [s]}\\
\hline
1 & 26/10/15 & Displets v2~\cite{Guney2015} & 3.43 & 265 \\
2 & 27/04/16 & PBCP~\cite{Seki2016} & 3.61 & 68 \\
3 & 21/08/15 & MC-CNN~acrt~\cite{Zbontar2015} & 3.89 & 2.94 \\
4 & 16/04/15 & PRSM~\cite{Vogel2015} & 4.27 & 300 \\
5 & 06/11/15 & DispNetC~\cite{Mayer2016}  & 4.34 & 0.06 \\
6 & 11/04/16 & ContentCNN~\cite{Luo2016}  & 4.54 & 1 \\
\textbf{7} & \textbf{21/08/15} & \textbf{MC-CNN~fst~\cite{Zbontar2015}} & \textbf{4.62} & \textbf{0.8} \\
\textbf{8} & \textbf{14/11/16} & \textbf{MC-CNN-SS~(ours)} & \textbf{4.97} & \textbf{1.35} \\
9 & 03/08/15 & SPS-st~\cite{Yamaguchi2014} & 5.31 & 2 \\
\hline
\end{tabular}
}
\vspace{1mm}
\caption{KITTI'15 benchmark~\cite{KITTI} snapshot from 14/11/2016 with published methods (default view). Methods ranked 1, 2, 3, 5, 6 and 7 use deep metrics for stereo matching. Note that our semi-supervised method MC-CNN-SS, shown in bold, that does not use ground truth data during training, has an error rate very similar to that of the supervised MC-CNN~fst method, also shown in bold, trained with ground truth data. Since the MC-CNN~fst method does not appear on KITTI'12 evaluation table, due to restrictions on the number of results for a single paper, we borrowed it from ~\cite{Zbontar2016}.}\label{tab:benchmarking_kitti15}
\end{table}

\subsection{What does deep metric learn?}
\label{sec:what_is_learned}

% similarity matrix before and after learning
In Figure~\ref{fig:similarity_matrix} 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.

\begin{figure}[hbtp]
\centering
\begin{minipage}{.5\textwidth}
  \centering
  \includegraphics[width=0.95\textwidth]{similarity_matrix.eps}
  \caption{Diagonal part of the similarity matrix before and after training with MC-CNN-SS on KITTI'12 dataset. Top figure shows one of the stereo images with two highlighted epipolar lines. The pictures below show the positive similarity matrices for these epipolar lines. 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.}
 \label{fig:similarity_matrix}
\end{minipage}%
\end{figure}

In Figure~\ref{fig:failure_cases} we show failure cases of learned deep metric. Most of the failures happen when the ground truth match is visually indistinguishable from the incorrect match picked by the deep metric. This happens if the reference patch is from a flat image area, an area with a repetitive texture, or an area with a horizontal edge.

\begin{figure}[hbtp]
\centering
\begin{minipage}{.5\textwidth}
  \center
  \includegraphics[width=\textwidth]{failure_cases.eps}
  \caption{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).}
\label{fig:failure_cases}
\end{minipage}%
\end{figure}

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.

% \subsection{Parameters tuning}
% \label{sec:parameters_tuning}

% In this section we show how we selected the maximum suppression $ t_{sup} $ and the occlusion $ t_{occ} $ thresholds. To find best value of each parameter, we kept all but one parameter fixed and run the training procedure for small number of iterations on KITTI'12 data-set. Then we compared WTA error on the validation set.

% The results, shown in Table~\ref{tab:parameters_tuning}, confirm our guess from \S~\ref{sec:contrastive} that it is better to mask spatial neighborhood of the first maximum in similarity matrix, before computing the second maximum. They also confirm our guess from \S~\ref{sec:contrastive_dp} that it is better to ignore occluded patches during the learning.

% \begin{table}[ht!]
% \resizebox{\columnwidth}{!}{%
% \begin{tabular}{ l l }
% \hline
% \textbf{Values} & \textbf{WTA error, [$\%$]} \\
% \hline
% $ t_{sup} = \{0, 1, \mathbf{2}, 4, 8, 16\} $ & $\{21.81, 16.83, \mathbf{16.66}, 16.86, 17.02, 17.28\} $ \\
% $ t_{occ} = \{\mathbf{1}, 2, 4, 8, 16\} $ & $\{\mathbf{16.93}, 17.32, 17.62, 17.58, 17.56\} $ \\
% \end{tabular}
% }
% \label{tab:parameters_tuning}
% \caption{Parameters tuning for CONTRASTIVE-DP method on KITTI'12 set. The parameters with smallest error are shown in \textbf{bold}.}
% \end{table}

\subsection{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~\ref{tab:generalization} 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.

\begin{table}[ht!]
\center
\begin{tabular}{llll}
\hline
\multirow{2}{*}{\textbf{Training set}}& \multicolumn{3}{c}{\textbf{WTA error, [\%]}} \\
								& \textbf{KITTI'12} & \textbf{KITTI'15} & \textbf{MB}\\
\hline
KITTI'12    & \textbf{13.90} & 15.52 		  & 34.85   \\
KITTI'15    & 16.61 		 & \textbf{14.08} & 36.66  \\
MB  & 14.22 		 & 15.00 		  & \textbf{30.06}   \\
\hline
\end{tabular}
\vspace{1mm}
\caption{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.}\label{tab:generalization}
\end{table}

% \subsection{Training set size effect}

% In this experiment, we study how size of unlabeled training set  affects WTA error of the deep metric. Recall that KITTI'12 and KITTI'15 are provided with extension -- large body of unlabeled stereo data. We use this stereo data to increase size of unlabeled training set 20x times, compare to the normal. Then we compare WTA error of the deep metric learned with the normal and the extended training sets.

% The results

% \begin{table}[ht!]
% \resizebox{\columnwidth}{!}{%
% \begin{tabular}{ m{0.5\columnwidth} m{0.25\columnwidth} m{0.25\columnwidth} }
% \hline
% \multirow{2}{*}{\textbf{Training set}}& \multicolumn{2}{c}{\textbf{WTA error, [\%]}} \\
% 								      & \textbf{KITTI'12} & \textbf{KITTI'15} \\
% \hline
% Normal		        & 13.99 & 14.04   \\
% Extended (20x)  	& 13.92 & 14.09   \\
% \end{tabular}
% }
% \label{tab:training_size_effect}
% \caption{Training set size effect.  }
% \end{table}

\section{Conclusion}

% contribution : semi-supervised learning method
We proposed novel semi-supervised techniques for training patch similarity measures for stereo reconstruction. 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.

% application & result: train particular net
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~\ref{tab:comparision_to_supervised}).

% results interpretation
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.

% practical implications
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 \ref{tab:comparision_to_supervised}. 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.

{\small
\bibliographystyle{ieee}
\bibliography{cnnmars}
}

\end{document}
listofitems.tex
% Ce fichier contient le code de l'extension "listofitems"
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                    %
\def\loiname                 {listofitems}                           %
\def\loiver                      {1.3}                              %
%                                                                    %
\def\loidate                  {2016/11/18}                           %
%                                                                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% --------------------------------------------------------------------
% This work may be distributed and/or modified under the
% conditions of the LaTeX Project Public License, either version 1.3
% of this license or (at your option) any later version.
% The latest version of this license is in
%
% %     http://www.latex-project.org/lppl.txt
%
% and version 1.3 or later is part of all distributions of LaTeX
% version 2005/12/01 or later.
% --------------------------------------------------------------------
% This work has the LPPL maintenance status `maintained'.
%
% The Current Maintainer of this work is Christian Tellechea
% email: unbonpetit@openmailbox.org
%        Commentaires, suggestions et signalement de bugs bienvenus !
%        Comments, bug reports and suggestions are welcome.
% --------------------------------------------------------------------
% L'extension listofitems est compos\'ee des 7 fichiers suivants :
%   - code               : listofitems            (.tex et .sty)
%   - manuel en francais : listofitems-fr         (.tex et .pdf)
%   - manuel en anglais  : listofitems-en         (.tex et .pdf)
%   - fichier lisezmoi   : README
% --------------------------------------------------------------------
\expandafter\edef\csname loi_restorecatcode\endcsname{\catcode\number`\_=\number\catcode`\_\relax}
\catcode`\_11

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%% gestion des erreurs %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\ifdefined\PackageError
	\def\loi_error#1{\PackageError\loiname{#1}{Read the manual}}% pour LaTeX
\else
	\def\loi_error#1{\errmessage{Package \loiname\space Error: #1^^J}}% pour TeX
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%% v\'erification de la pr`'esence de etex %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begingroup
\edef\__tempa{\meaning\eTeXversion}\edef\__tempb{\string\eTeXversion}%
\ifx\__tempa\__tempb
	\endgroup
\else
	\endgroup
	\loi_error{You are not using an eTeX engine, listofitems cannot work.}%
	\expandafter\loi_restorecatcode\expandafter\endinput
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%% macros auxiliaires %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%---- macros de d\'eveloppement et de manipulation d'arguments
\chardef\loi_stop=0
\def\loi_quark{\loi_quark}
\long\def\loi_identity#1{#1}
\def\loi_gobarg#1{}
\long\def\loi_first#1#2{#1}
\long\def\loi_second#1#2{#2}
\long\def\loi_firsttonil#1#2\_nil{#1}
\long\def\loi_antefi#1#2\fi{#2\fi#1}
\long\def\loi_swaparg#1#2{#2{#1}}
\long\def\loi_exparg#1#2{\expandafter\loi_swaparg\expandafter{#2}{#1}}
\long\def\loi_expafternil#1\_nil{\begingroup\def\loi_temp{\endgroup#1}\expandafter\loi_temp}
\def\loi_macroname{\loi_ifinrange\escapechar[[0:255]]{\expandafter\loi_gobarg}{}\string}
\def\loi_argcsname#1#{\begingroup\def\loi_temp{\endgroup#1}\loi_argcsname_i}
\def\loi_argcsname_i#1{\expandafter\loi_temp\csname#1\endcsname}

%--- macros de test
\def\loi_ifnum#1{\ifnum#1\expandafter\loi_first\else\expandafter\loi_second\fi}
\long\def\loi_ifx#1{\ifx#1\expandafter\loi_first\else\expandafter\loi_second\fi}
\long\def\loi_ifempty#1{\loi_exparg\loi_ifx{\expandafter\relax\detokenize{#1}\relax}}
\def\loi_ifstar#1#2{\def\loi_ifstar_i{\loi_ifx{*\loi_nxttok}{\loi_first{#1}}{#2}}\futurelet\loi_nxttok\loi_ifstar_i}
\long\def\loi_ifcs#1{% #1 est-il une sc ?
	\loi_ifempty{#1}
		\loi_second% si #1 est vide, faux
		{\loi_ifspacefirst{#1}
			\loi_second% si espace en 1er, faux
			{\loi_exparg\loi_ifempty{\loi_gobarg#1}% 1 seul token ?
				{\begingroup \escapechar`\_
					\if\expandafter\loi_firsttonil\string#1\_nil\expandafter\loi_firsttonil\string\relax\_nil
						\endgroup\expandafter\loi_first
					\else
						\endgroup\expandafter\loi_second
					\fi
				}
				\loi_second% si plusieurs tokens, faux
			}%
		}%
}
\def\loi_ifinrange#1[[#2:#3]]{\loi_ifnum{\numexpr(#1-#2)*(#1-#3)>0 }\loi_second\loi_first}

%--- macro de type for
%      Voir codes 150 \`a 155 ici --> http://progtex.fr/wp-content/uploads/2014/09/code.txt
%      et pages 175 \`a 184 du livre "Apprendre \`a programmer en TeX"
\def\loi_fornum#1=#2to#3\do{%
	\edef#1{\number\numexpr#2}\edef\loi_sgncmp{\ifnum#1<\numexpr#3\relax>+\else<-\fi}%
	\loi_argcsname\loi_fornum_i{loi_fornum_\string#1\expandafter}\expandafter{\number\numexpr#3\expandafter}\loi_sgncmp#1%
}
\long\def\loi_fornum_i#1#2#3#4#5#6{\def#1{\unless\ifnum#5#3#2\relax\loi_antefi{#6\edef#5{\number\numexpr#5#41\relax}#1}\fi}#1}

%--- macros retirant les espaces extr\^emes
%      Voir codes 320 \`a 324 ici --> http://progtex.fr/wp-content/uploads/2014/09/code.txt
%      et pages 339 \`a 343 de "Apprendre \`a programmer en TeX"
\long\def\loi_ifspacefirst#1{\expandafter\loi_ifspacefirst_i\detokenize{#10} \_nil}
\long\def\loi_ifspacefirst_i#1 #2\_nil{\loi_ifempty{#1}}
\expandafter\def\expandafter\loi_gobspace\space{}
\def\loi_removefirstspaces{\romannumeral\loi_removefirstspaces_i}
\long\def\loi_removefirstspaces_i#1{\loi_ifspacefirst{#1}{\expandafter\loi_removefirstspaces_i\expandafter{\loi_gobspace#1}}{\loi_stop#1}}
\edef\loi_restorezerocatcode{\catcode0=\number\catcode0 \relax}
\catcode0 12
\long\def\loi_removelastspaces#1{\romannumeral\loi_removelastspaces_i#1^^00 ^^00\_nil}
\long\def\loi_removelastspaces_i#1 ^^00{\loi_removelastspaces_ii#1^^00}
\long\def\loi_removelastspaces_ii#1^^00#2\_nil{\loi_ifspacefirst{#2}{\loi_removelastspaces_i#1^^00 ^^00\_nil}{\loi_stop#1}}
\loi_restorezerocatcode
\long\def\loi_removeextremespaces#1{% #1=texte o\`u les espaces extr\^emes sont retir\'es
	\romannumeral\expandafter\expandafter\expandafter\loi_removelastspaces\expandafter\expandafter\expandafter
	{\expandafter\expandafter\expandafter\loi_stop\loi_removefirstspaces{#1}}%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%% macro publique \setsepchar %%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\setsepchar{\futurelet\loi_nxttok\setsepchar_i}
\def\setsepchar_i{\loi_ifx{[\loi_nxttok}\setsepchar_ii{\setsepchar_ii[/]}}
\long\def\setsepchar_ii[#1]#2{% #1=sepcar de <liste des sepcar>  #2=<liste des sepcar>
	\loi_ifempty{#1}
		{\loi_error{Empty separator not allowed, separator "/" used}%
		\setsepchar_ii[/]{#2}%
		}
		{\def\loi_currentsep{#1}%
		\_removeextremespacesfalse
		\loi_nestcnt1 % r\'einitaliser niveau initial \`a 1
		\def\nestdepth{1}%
		\loi_argcsname\let{loi_previndex[\number\loi_nestcnt]}\empty
		\def\loi_listname{loi_listofsep}%
		\let\loi_def\def \let\loi_edef\edef \let\loi_let\let
		\loi_ifempty{#2}
			{\loi_error{Empty list of separators not allowed, "," used}%
			\readlist_iv1{,}%
			}
			{\readlist_iv1{#2}}%
		\loi_argcsname\let\nestdepth{loi_listofseplen[0]}%
		\loi_argcsname\let\loi_currentsep{loi_listofsep[1]}% 1er car de s\'eparation
		}%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%% macro normalisant l'index %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\loi_normalizeindex#1#2#3{% #1=macroname  #2=liste d'index  #3=profondeur max --> renvoie {err}{indx norm}
	\loi_ifempty{#2}
		{\loi_stop{}{}}
		{\loi_normalizeindex_i1{}{#3}{#1}#2,\loi_quark,}%
}%
\def\loi_normalizeindex_i#1#2#3#4#5,{% #1=compteur de profondeur #2=index pr\'ec\'edents  #3=profondeur max #4=macroname  #5=index courant
	\loi_ifx{\loi_quark#5}
		{\loi_normalizeindex_iii#2\loi_quark}% supprimer la derni\`ere virgule
		{\loi_ifnum{#1>#3 }
			{\loi_invalidindex{Too deeply nested index, index [.] retained}{#2}}% si profondeur trop grande
			{\loi_ifinrange\ifnum\numexpr#5<0 -1*\fi(#5)[[1:\csname #4len[#20]\endcsname]]% si abs(#5) hors de [1,len]
				{\loi_exparg\loi_normalizeindex_ii{\number\numexpr#5\ifnum\numexpr#5<0 +\csname #4len[#20]\endcsname+1\fi}{#1}{#2}{#3}{#4}}
				{\loi_invalidindex{#5 is an invalid index, index [.] retained}{#2}}%
			}%
		}%
}
\def\loi_normalizeindex_ii#1#2#3{\loi_exparg\loi_normalizeindex_i{\number\numexpr#2+1}{#3#1,}}% #1=index \`a rajouter  #2=compteur de profondeur #3=index pr\'ec\'edents
\def\loi_normalizeindex_iii#1,\loi_quark{\loi_stop{}{#1}}
\def\loi_invalidindex#1#2{\loi_ifempty{#2}{\loi_invalidindex_i{#1},}\loi_invalidindex_i{#1}{#2}}
\def\loi_invalidindex_i#1#2{\loi_invalidindex_ii#1\loi_quark#2\loi_quark}
\def\loi_invalidindex_ii#1[.]#2\loi_quark#3,\loi_quark#4\loi_quark,{\loi_stop{#1[#3]#2}{#3}}% #4= index ignor\'es

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%% macro publique \readlist %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcount\loi_nestcnt
\def\greadlist{%
	\let\loi_def\gdef \let\loi_edef\xdef \def\loi_let{\global\let}%
	\loi_nestcnt1 % niveau initial = 1
	\loi_argcsname\loi_let{loi_previndex[\number\loi_nestcnt]}\empty
	\loi_ifstar{\_removeextremespacestrue\readlist_i}{\_removeextremespacesfalse\readlist_i}%
}
\def\readlist{%
	\let\loi_def\def \let\loi_edef\edef \let\loi_let\let
	\loi_nestcnt1 % niveau initial = 1
	\loi_argcsname\let{loi_previndex[\number\loi_nestcnt]}\empty
	\loi_ifstar{\_removeextremespacestrue\readlist_i}{\_removeextremespacesfalse\readlist_i}%
}
\long\def\readlist_i#1#2{% #1=macro stockant les \'el\'ements  #2=liste des \'el\'ements
	\loi_ifcs{#2}
		{\loi_exparg{\readlist_i#1}{#2}}
		{\loi_edef\loi_listname{\loi_macroname#1}%
		\loi_argcsname\loi_let{\loi_listname nest}\nestdepth
		\loi_argcsname\loi_def{\loi_listname[]}{#2}% la liste enti\`ere
		\loi_argcsname\loi_def{\loi_listname sep[]}{}% s\'eparateur vide
		\loi_ifempty{#2}
			{\loi_def#1[##1]{}%
			\loi_argcsname\loi_def{\loi_listname len}{0}\loi_argcsname\loi_def{\loi_listname len[0]}{0}%
			\loi_error{Empty list ignored, nothing to do}%
			}
			{\loi_edef#1[##1]{\unexpanded{\romannumeral\expandafter\loi_auxmacrolistitem\romannumeral\loi_normalizeindex}{\loi_listname}{##1}{\csname\loi_listname nest\endcsname}{\loi_listname}}%
			\loi_argcsname\loi_edef{\loi_listname sep}[##1]{\unexpanded{\romannumeral\expandafter\loi_auxmacrolistitem\romannumeral\loi_normalizeindex}{\loi_listname}{##1}{\csname\loi_listname nest\endcsname}{\loi_listname sep}}%
			\readlist_ii{#2}%
			\loi_argcsname\loi_argcsname\loi_let{\loi_listname len}{\loi_listname len[0]}% longueur du niveau 0
			}%
		}%
}
\def\loi_auxmacrolistitem#1#2#3{%
	\expandafter\expandafter\expandafter\loi_stop\csname#3[#2]\expandafter\endcsname
	\romannumeral\loi_ifempty{#1}{\loi_stop}{\loi_stop\loi_error{#1}}%
}
\def\readlist_ii{%
	\loi_argcsname\loi_let\loi_currentsep{loi_listofsep[\number\loi_nestcnt]}%
	\expandafter\readlist_iii\loi_currentsep||\_nil
}
\long\def\readlist_iii#1||#2\_nil#3{\readlist_iv1{#3#1}}% #1=<sep courant simple>  #3=liste -> rajoute un \'el\'ement vide pour le test ifempty ci dessous
\long\def\readlist_iv#1#2{% #1=compteur d'index  #2=liste d'\'el\'ements \`a examiner
	\loi_ifempty{#2}
		{\loi_argcsname\loi_edef{\loi_listname len[\csname loi_previndex[\number\loi_nestcnt]\endcsname0]}{\number\numexpr#1-1\relax}%
		\advance\loi_nestcnt-1
		\loi_argcsname\loi_let\loi_currentsep{loi_listofsep[\number\loi_nestcnt]}%
		}
		{\loi_expafternil\readlist_vi{#2}{}\_nil\loi_currentsep||\loi_quark||#2\_nil{#1}}% aller isoler le 1er item
}
\long\def\readlist_v#1#2{\readlist_vi{#2}{}#1||\loi_quark||#2\_nil}% #1=liste s\'eparateurs (s\'ep=||)  #2=chaine de tokens
\long\def\readlist_vi#1#2#3||{% #1=liste restante   #2=dernier <sep utile>  #3=<sep courant>
	\loi_ifx{\loi_quark#3}
		{\loi_ifempty{#2}% si #1 vide, aucun <sep utile> n'a \'et\'e trouv\'e, il reste \`a lire "<liste compl\`ete>\_nil"
			{\long\def\readlist_vii##1\_nil##2{\loi_exparg{\readlist_ix{##2}{}}{\loi_gobarg##1}{#2}}}% ##2=compteur d'index
			{\long\def\readlist_vii##1#2{\loi_exparg\readlist_viii{\loi_gobarg##1}\relax}%
			\long\def\readlist_viii##1##2\_nil##3{\loi_exparg{\readlist_ix{##3}}{\loi_gobarg##2}{##1}{#2}}% ##3=compteur d'index
			}%
		\readlist_vii\relax% le \relax meuble l'argument d\'elimit\'e
		}
		{\long\def\readlist_vii##1#3##2\_nil{%
			\loi_ifempty{##2}% si <liste restante> ne contient pas le <sep courant>
				{\readlist_vi{#1}{#2}}% recommencer avec le m\^eme <sep utile>
				{\readlist_vi{##1#3}{#3}}% sinon raccourcir <liste restante> et <sep courant>:=<sep utile>
			}%
		\readlist_vii#1#3\_nil
		}%
}
\long\def\readlist_ix#1#2#3{% #1=compteur d'index  #2=liste restante  #3=\'el\'ement courant
	\loi_ifnum{0\loi_exparg\loi_ifspacefirst{\loi_currentsep}{}1\if_removeextremespaces1\fi=11 }% s'il faur retirer les espaces extr\^emes
		{\loi_exparg{\loi_exparg{\readlist_x{#1}{#2}}}{\loi_removeextremespaces{#3}}}% red\'efinir l'\'el\'ement courant
		{\readlist_x{#1}{#2}{#3}}%
}
\long\def\readlist_x#1#2#3#4{% #1=compteur d'index  #2=liste restante  #3=\'el\'ement courant   #4=sep utilis\'e
	\loi_ifnum{0\if_ignoreemptyitems1\fi\loi_ifempty{#3}1{}=11 }
		{\readlist_iv{#1}{#2}}% si l'on n'ignore pas les \'el\'ements vides :
		{\loi_argcsname\loi_def{\loi_listname[\csname loi_previndex[\number\loi_nestcnt]\endcsname#1]}{#3}% assignation de l'item ctuel \`a la macro
		\loi_argcsname\loi_def{\loi_listname sep[\csname loi_previndex[\number\loi_nestcnt]\endcsname#1]}{#4}% assignation du <sep> actuel \`a la macro \<macrolist>sep
		\loi_ifnum{\loi_nestcnt<\nestdepth\relax}% si imbrication max non atteinte
			{\advance\loi_nestcnt1
			\loi_argcsname\edef{loi_previndex[\number\loi_nestcnt]}{\csname loi_previndex[\number\numexpr\loi_nestcnt-1]\endcsname#1,}%
			\readlist_ii{#3}% recommencer avec l'\'el\'ement courant
			}
			{}%
		\loi_exparg\readlist_iv{\number\numexpr#1+1}{#2}% puis chercher l'\'el\'ement suivant dans la liste restante
		}%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%% macro \listlen %%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\listlen#1[#2]{%
	\romannumeral\loi_ifempty{#2}
		{\expandafter\expandafter\expandafter\loi_stop\csname\loi_macroname#1len[0]\endcsname}
		{\loi_exparg\listlen_i{\romannumeral-`\.\loi_macroname#1}{#2}}%
}
\def\listlen_i#1#2{% #1=macro name   #2=index non normalis\'e    prendre <profondeur max-1>
	\loi_exparg{\expandafter\listlen_ii\romannumeral\loi_normalizeindex{#1}{#2}}{\number\numexpr\csname#1nest\endcsname-1}{#1}%
}
\def\listlen_ii#1#2#3{% #1=err   #2=index normalis\'e  #3=macroname
	\expandafter\expandafter\expandafter\loi_stop\csname#3len[#2,0]\expandafter\endcsname
	\romannumeral\loi_ifempty{#1}{\loi_stop}{\loi_stop\loi_error{#1}}%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%% macro \foreachitem %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\foreachitem#1\in#2{%
	\edef\foreachitem_i{\noexpand\foreachitem_iii\noexpand#1{\expandafter\noexpand\csname\loi_macroname#1cnt\endcsname}{\loi_macroname#2}}%
	\futurelet\loi_nxttok\foreachitem_ii
}
\def\foreachitem_ii{\loi_ifx{\loi_nxttok[}\foreachitem_i{\foreachitem_i[]}}
\def\foreachitem_iii#1#2#3[#4]{% prendre <profondeur max-1>
	\loi_exparg{\expandafter\foreachitem_iv\romannumeral\loi_normalizeindex{#3}{#4}}{\number\numexpr\csname#3nest\endcsname-1}#1{#2}{#3}%
}
\def\foreachitem_iv#1#2{\loi_ifempty{#2}{\foreachitem_v{#1}{}}{\foreachitem_v{#1}{#2,}}}% #1=err  #2=index norm
\long\def\foreachitem_v#1#2#3#4#5#6{% #1=err  #2=index norm  #3=macroiter  #4=compteur associ\'e  #5=nom de macrolist  #6=code
	\loi_ifnum{\csname#5len[#20]\endcsname>0 }
		{\loi_ifempty{#1}{}{\loi_error{#1}}%
		\loi_fornum#4=1to\csname#5len[#20]\endcsname\do{\loi_argcsname\let#3{#5[#2#4]}#6}%
		}
		{}%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%% macro \showitem %%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\showitems{\loi_ifstar{\let\showitems_cmd\detokenize\showitems_i}{\let\showitems_cmd\loi_identity\showitems_i}}
\def\showitems_i#1{\def\showitems_ii{\showitems_iv#1}\futurelet\loi_nxttok\showitems_iii}
\def\showitems_iii{\loi_ifx{\loi_nxttok[}\showitems_ii{\showitems_ii[]}}
\def\showitems_iv#1[#2]{\foreachitem\showitems_iter\in#1[#2]{\showitemsmacro{\expandafter\showitems_cmd\expandafter{\showitems_iter}}}}
\unless\ifdefined\fbox
	\newdimen\fboxrule \newdimen\fboxsep \fboxrule=.4pt \fboxsep=3pt % r\'eglages identiques \`a LaTeX
	\def\fbox#1{% imitation de la macro \fbox de LaTeX, voir codes 251 \`a 254 ici --> http://progtex.fr/wp-content/uploads/2014/09/code.txt
		\hbox{% et pages 271 \`a 274 de "Apprendre \`a programmer en TeX"
			\vrule width\fboxrule
			\vtop{%
				\vbox{\hrule height\fboxrule \kern\fboxsep \hbox{\kern\fboxsep#1\kern\fboxsep}}%
				\kern\fboxsep \hrule height\fboxrule
			}\vrule width\fboxrule
		}%
	}
\fi
\def\showitemsmacro#1{% encadrement par d\'efaut
	\begingroup\fboxsep=0.25pt \fboxrule=0.5pt \fbox{\strut#1}\endgroup
	\hskip0.25em\relax
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%% macro \itemtomacro %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\itemtomacro#1[#2]{% #1[#2]=item  non encore lu: #3=macro
	\edef\loi_listname{\loi_macroname#1}%
	\loi_exparg{\expandafter\itemtomacro_i\romannumeral\expandafter\loi_normalizeindex\expandafter{\loi_listname}{#2}}{\csname\loi_listname nest\endcsname}\let
}
\def\gitemtomacro#1[#2]{% #1[#2]=item
	\xdef\loi_listname{\loi_macroname#1}%
	\loi_exparg{\expandafter\itemtomacro_i\romannumeral\expandafter\loi_normalizeindex\expandafter{\loi_listname}{#2}}{\csname\loi_listname nest\endcsname}{\global\let}%
}
\def\itemtomacro_i#1#2#3#4{%
	\loi_ifempty{#1}{}{\loi_error{#1}}%
	\loi_argcsname#3#4{\loi_listname[#2]}%
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%% r\'eglages par d\'efaut %%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newif\if_removeextremespaces
\newif\if_ignoreemptyitems
\let\ignoreemptyitems\_ignoreemptyitemstrue
\let\reademptyitems\_ignoreemptyitemsfalse
\setsepchar{,}
\reademptyitems

\loi_restorecatcode
\endinput

######################################################################
#                             Historique                             #
######################################################################

v1.0  19/8/2016
      - Premi\`ere version publique

v1.1  01/09/2016
      - Stockage des s\'eparateurs dans <macrolist>sep
      - bug corrig\'e dans \loi_restorecatcode

v1.2  22/10/2016
      - macros \greadlist et \gitemtomacro pour la globalit\'e

v1.3  18/11/2016
      - bugs corrig\'es dans la gestion de la globalit\'e
cnnmars.bbl
\begin{thebibliography}{10}\itemsep=-1pt

\bibitem{KITTI}
{KITTI} 2012, 2015 stereo scoreboards.
\newblock \url{http://www.cvlibs.net/datasets/kitti/}.
\newblock Accessed: 2016-11-14.

\bibitem{MB}
Middlebury scoreboard.
\newblock \sloppy\url{http://vision.middlebury.edu/stereo/}.
\newblock Accessed: 2016-11-14.

\bibitem{All2011}
K.~All, D.~Hasler, and F.~Fleuret.
\newblock {FlowBoost - Appearance learning from sparsely annotated video}.
\newblock In {\em CVPR}, pages 1433--1440, 2011.

\bibitem{Ansar2004}
A.~Ansar, A.~Castano, and L.~Matthies.
\newblock {Enhanced Real-time Stereo Using Bilateral Filtering ∗}.
\newblock {\em 3DPVT}, 2004.

\bibitem{Babenko2008}
B.~Babenko.
\newblock {Multiple instance learning: algorithms and applications}.
\newblock {\em NCBI Google Scholar}, 2008.

\bibitem{Balntas2016}
V.~Balntas, E.~Johns, L.~Tang, and K.~Mikolajczyk.
\newblock {PN-Net: Conjoined Triple Deep Network for Learning Local Image
  Descriptors}.
\newblock {\em CoRR}, 2016.

\bibitem{Barron2016}
J.~T. Barron and B.~Poole.
\newblock The fast bilateral solver.
\newblock {\em ECCV}, 2016.

\bibitem{Bromley94}
J.~Bromley, I.~Guyon, Y.~Lecun, E.~Säckinger, and R.~Shah.
\newblock Signature verification using a "siamese" time delay neural network.
\newblock In {\em NIPS}, 1994.

\bibitem{Calonder2012}
M.~Calonder, V.~Lepetit, M.~{\"{O}}zuysal, T.~Trzcinski, C.~Strecha, and
  P.~Fua.
\newblock {BRIEF: Computing a local binary descriptor very fast}.
\newblock {\em PAMI}, 2012.

\bibitem{Chakrabarti2015}
A.~Chakrabarti, Y.~Xiong, S.~J. Gortler, and T.~Zickler.
\newblock {Low-Level Vision by Consensus in a Spatial Hierarchy of Regions}.
\newblock {\em CVPR}, 2015.

\bibitem{Chen2013}
X.~Chen, A.~Shrivastava, and A.~Gupta.
\newblock {NEIL: Extracting Visual Knowledge from Web Data}.
\newblock In {\em ICCV}, 2013.

\bibitem{Chen2015}
Z.~Chen, X.~Sun, and L.~Wang.
\newblock {A Deep Visual Correspondence Embedding Model for Stereo Matching
  Costs}.
\newblock {\em ICCV}, 2015.

\bibitem{Collobert2011}
R.~Collobert, K.~Kavukcuoglu, and C.~Farabet.
\newblock Torch7: A matlab-like environment for machine learning.
\newblock In {\em BigLearn, NIPS Workshop}, 2011.

\bibitem{Fischer2014}
P.~Fischer, A.~Dosovitskiy, and T.~Brox.
\newblock {Descriptor Matching with Convolutional Neural Networks: a Comparison
  to SIFT}.
\newblock {\em ARXIV}, 2014.

\bibitem{Geiger2012}
A.~Geiger, P.~Lenz, and R.~Urtasun.
\newblock Are we ready for autonomous driving? the kitti vision benchmark
  suite.
\newblock In {\em CVPR}, 2012.

\bibitem{Geiger2010}
A.~Geiger, M.~Roser, and R.~Urtasun.
\newblock {Efficient large-scale stereo matching}.
\newblock {\em ACCV}, 2010.

\bibitem{Guney2015}
F.~G{\"{u}}ney and A.~Geiger.
\newblock {Displets: Resolving Stereo Ambiguities using Object Knowledge}.
\newblock {\em CVPR}, 2015.

\bibitem{Hartley2003}
R.~Hartley and A.~Zisserman.
\newblock {\em {Multiple View Geometry in Computer Vision}}.
\newblock Cambridge University Press, 2003.

\bibitem{Hirschm2008}
H.~Hirschm.
\newblock {Evaluation of Stereo Matching Costs on Images with Radiometric
  Differences}.
\newblock {\em PAMI}, 2008.

\bibitem{Hirschmuller2002}
H.~Hirschm{\"{u}}ller, P.~R. Innocent, and J.~Garibaldi.
\newblock {Real-Time Correlation-Based Stereo Vision with Reduced Border
  Errors}.
\newblock {\em IJCV}, 47, 2002.

\bibitem{Hirschmuller2007}
H.~Hirschmuller and D.~Scharstein.
\newblock {Evaluation of Cost Functions for Stereo Matching}.
\newblock {\em CVPR}, pages 1--8, 2007.

\bibitem{Jahrer2008}
M.~Jahrer, M.~Grabner, and H.~Bischof.
\newblock Learned local descriptors for recognition and matching.
\newblock {\em Computer Vision Winter Workshop}, 2008.

\bibitem{Kim2003}
J.~Kim, V.~Kolmogorov, and R.~Zabih.
\newblock Visual correspondence using energy minimization and mutual
  information.
\newblock In {\em ICCV}, 2003.

\bibitem{Kim2016}
K.~R. Kim and C.~S. Kim.
\newblock Adaptive smoothness constraints for efficient stereo matching using
  texture and edge information.
\newblock In {\em ICIP}, 2016.

\bibitem{Kowalczuk2012}
J.~Kowalczuk, E.~T. Psota, and L.~C. P{\'{e}}rez.
\newblock {Real-time Stereo Matching on CUDA using an Iterative Refinement
  Method for Adaptive Support-Weight Correspondences Real-time Stereo Matching
  on CUDA using an Iterative Refinement Method for Adaptive Support-Weight
  Correspondences}.
\newblock {\em Transactions on Circuits and Systems for Video Technology},
  2012.

\bibitem{Kumar2016}
B.~G.~V. Kumar, G.~Carneiro, and I.~Reid.
\newblock {Learning Local Image Descriptors with Deep Siamese and Triplet
  Convolutional Networks by Minimising Global Loss Functions}.
\newblock {\em CVPR}, 2016.

\bibitem{LeCun1998}
Y.~LeCun, L.~Bottou, Y.~Bengio, and P.~Haffner.
\newblock {Gradient-based learning applied to document recognition}.
\newblock {\em Proceedings of the IEEE}, 86(11):2278--2323, 1998.

\bibitem{Lefakis2014}
L.~Lefakis and F.~Fleuret.
\newblock {Dynamic Programming Boosting for Discriminative Macro-Action
  Discovery}.
\newblock {\em ICML}, 32:1548--1556, 2014.

\bibitem{Li2016}
A.~Li, D.~Chen, Y.~Liu, and Z.~Yuan.
\newblock Coordinating multiple disparity proposals for stereo computation.
\newblock In {\em CVPR}, 2016.

\bibitem{Lowe2004}
D.~G. Lowe.
\newblock {Distinctive Image Features from Scale-Invariant Keypoints}.
\newblock {\em IJCV}, 2004.

\bibitem{Luo2016}
W.~Luo, A.~G. Schwing, and R.~Urtasun.
\newblock Efficient deep learning for stereo matching.
\newblock In {\em CVPR}, 2016.

\bibitem{Marr1979}
D.~Marr and T.~Poggio.
\newblock {A Computational Theory of Human Stereo Vision}.
\newblock {\em Biological Sciences}, 204(1156):301--328, 1979.

\bibitem{Mayer2016}
N.~Mayer, E.~Ilg, P.~H{\"a}usser, P.~Fischer, D.~Cremers, A.~Dosovitskiy, and
  T.~Brox.
\newblock A large dataset to train convolutional networks for disparity,
  optical flow, and scene flow estimation.
\newblock {\em CVPR}, 2016.

\bibitem{Menze2015}
M.~Menze and A.~Geiger.
\newblock {Object scene flow for autonomous vehicles}.
\newblock In {\em CVPR}, 2015.

\bibitem{Ntouskos2016}
V.~Ntouskos and F.~Pirri.
\newblock Confidence driven tgv fusion.
\newblock {\em arXiv preprint arXiv:1603.09302}, 2016.

\bibitem{Psota2015}
E.~T. Psota, J.~Kowalczuk, M.~Mittek, and L.~C. Perez.
\newblock {MAP Disparity Estimation Using Hidden Markov Trees}.
\newblock {\em ICCV}, 2015.

\bibitem{Reed2015}
S.~E. Reed and H.~Lee.
\newblock {Raining deep neural networks on noisy labels with bootstrapping}.
\newblock {\em ICLR}, 2015.

\bibitem{Scharstein2014}
D.~Scharstein, H.~Hirschm{\"{u}}ller, Y.~Kitajima, G.~Krathwohl,
  N.~Ne{\v{s}}i{\'{c}}, X.~Wang, and P.~Westling.
\newblock {High-resolution stereo datasets with subpixel-accurate ground
  truth}.
\newblock {\em Lecture Notes in Computer Science}, 2014.

\bibitem{Scharstein2007}
D.~Scharstein and C.~Pal.
\newblock {Learning conditional random fields for stereo}.
\newblock In {\em CVPR}, 2007.

\bibitem{Scharstein2001}
D.~Scharstein and R.~Szeliski.
\newblock {A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence
  Algorithms}.
\newblock {\em IJCV}, 2001.

\bibitem{Scharstein2003}
D.~Scharstein and R.~Szeliski.
\newblock {High-accuracy stereo depth maps using structured light}.
\newblock {\em CVPR}, 2003.

\bibitem{Seki2016}
A.~Seki and M.~Pollefeys.
\newblock Patch based confidence prediction for dense disparity map.
\newblock In {\em BMVC}, 2016.

\bibitem{Shean2016}
D.~E. Shean, O.~Alexandrov, Z.~M. Moratto, B.~E. Smith, I.~R. Joughin,
  C.~Porter, and P.~Morin.
\newblock {An automated, open-source pipeline for mass production of digital
  elevation models (DEMs) from very-high-resolution commercial stereo satellite
  imagery}.
\newblock {\em {\{}ISPRS{\}} Journal of Photogrammetry and Remote Sensing},
  2016.

\bibitem{Simo-Serra2015}
E.~Simo-Serra, E.~Trulls, L.~Ferraz, I.~Kokkinos, P.~Fua, and F.~Moreno-Noguer.
\newblock {Discriminative Learning of Deep Convolutional Feature Point
  Descriptors}.
\newblock {\em ICCV}, 2015.

\bibitem{Simonyan2013}
K.~Simonyan, A.~Vedaldi, and A.~Zisserman.
\newblock {Descriptor Learning Using Convex Optimization}.
\newblock {\em PAMI}, 2013.

\bibitem{Strecha2012}
C.~Strecha, A.~M. Bronstein, M.~M. Bronstein, and P.~Fua.
\newblock {LDAHash: Improved matching with smaller descriptors}.
\newblock {\em PAMI}, 2012.

\bibitem{Strecha2010}
C.~Strecha, T.~Pylv{\"{a}}n{\"{a}}inen, and P.~Fua.
\newblock {Dynamic and scalable large scale image reconstruction}.
\newblock In {\em CVPR}, 2010.

\bibitem{Tola2010}
E.~Tola.
\newblock {DAISY: A Fast Descriptor for Dense Wide Baseline Stereo and
  Multiview Reconstruction}.
\newblock {\em PAMI}, 2010.

\bibitem{Triguero2013}
I.~Triguero, S.~Garc{\'{\i}}a, and F.~Herrera.
\newblock {Self-labeled techniques for semi-supervised learning: taxonomy,
  software and empirical study}.
\newblock {\em Knowledge and Information Systems}, 2013.

\bibitem{Trzcinski2012}
T.~Trzcinski, M.~Christoudias, V.~Lepetit, and P.~Fua.
\newblock {Learning Image Descriptors with the Boosting-Trick}.
\newblock {\em NIPS}, 2012.

\bibitem{Vogel2014}
C.~Vogel, S.~Roth, and K.~Schindler.
\newblock View-consistent 3d scene flow estimation over multiple frames.
\newblock In {\em ECCV}, 2014.

\bibitem{Vogel2015}
C.~Vogel, K.~Schindler, and S.~Roth.
\newblock 3d scene flow estimation with a piecewise rigid scene model.
\newblock {\em IJCV}, 2015.

\bibitem{Wu2015}
J.~Wu, Y.~Yu, C.~Huang, and K.~Yu.
\newblock {Deep Multiple Instance Learning for Image Classification and
  Auto-Annotation}.
\newblock {\em CVPR}, 2015.

\bibitem{XufengHan2015}
{Xufeng Han}, T.~Leung, Y.~Jia, R.~Sukthankar, and A.~C. Berg.
\newblock {MatchNet: Unifying feature and metric learning for patch-based
  matching}.
\newblock {\em CVPR}, 2015.

\bibitem{Yamaguchi2014}
K.~Yamaguchi, D.~Mcallester, and R.~Urtasun.
\newblock {Efficient Joint Segmentation , Occlusion Labeling , Stereo and Flow
  Estimation}.
\newblock {\em ECCV}, 2014.

\bibitem{Zabih1994}
R.~Zabih and J.~Woodfill.
\newblock {Non-parametric Local Transforms for Computing Visual
  Correspondence}.
\newblock {\em ECCV}, 1994.

\bibitem{Zagoruko2015}
S.~Zagoruko and N.~Komodakis.
\newblock {Learning to Compare Image Patches via Convolutional Neural Networks
  Sergey}.
\newblock {\em CVPR}, 2015.

\bibitem{Zbontar2015}
J.~{\v{Z}}bontar and Y.~LeCun.
\newblock {Computing the Stereo Matching Cost With a Convolutional Neural
  Network}.
\newblock {\em CVPR}, 2015.

\bibitem{Zbontar2016}
J.~Zbontar and Y.~LeCun.
\newblock Stereo matching by training a convolutional neural network to compare
  image patches.
\newblock {\em JMLR}, 2016.

\bibitem{Zhang2015}
C.~Zhang and Z.~Li.
\newblock {MeshStereo : A Global Stereo Model with Mesh Alignment
  Regularization for View Interpolation}.
\newblock {\em ICCV}, 2015.

\end{thebibliography}
