benchmark (Goyette et al., 2014, 2012; Wang et al., 2014a) and compare our results with
those of 21 methods listed on its online platform as well as the self-reported results of 6
recently published methods (27 in total). Our new approach outperforms most of them in
overall performance, and in most categories taken individually. To make its usage and future
comparisons outside this benchmark easier, we offer the full C++ implementation of PAWCS
along with its entire testing framework online.

Note that our method was previously introduced (St-Charles et al., 2015b); here, we offer an
extended description of our approach, discuss new experiments on the 2014 CDnet dataset,
and compare our results with the new state-of-the-art.

## 5.2 Related Work

Many background modeling paradigms have been introduced over the years: the earliest and
most popular is pixel-level modeling, as it allows simple, scalable, high-speed implementa-
tions. This is due to the fact that this modeling strategy relies on low-level features (e.g.
color intensities, gradients) to track background representations, as opposed to region-level
or object-level information. Two of the three best methods listed by Goyette et al. (2012),
namely PBAS (Hofmann et al., 2012) and ViBe+ (Van Droogenbroeck and Paquot, 2012), fol-
low this paradigm as they are both based on stochastic intensity sampling (Barnich and Van
Droogenbroeck, 2011). Parametric approaches based on Gaussian Mixture Models (GMM,
Stauffer and Grimson, 1999) or non-parametric ones based on Kernel Density Estimation
(KDE, Elgammal et al., 2000) as well as their derivatives (KaewTraKulPong and Bowden,
2002; Zivkovic and van der Heijden, 2006) can all be considered part of this family. With a
goal similar to Zivkovic and van der Heijden (2006), the work of Haines and Xiang (2014)
recently proposed a Dirichlet process Gaussian mixture modeling approach that automati-
cally determines its optimal distribution parameters and component count in a data-driven
fashion. Their “confidence capping” strategy allows background representations to be cap-
tured and forgotten in a principled manner, much like the “maximum negative run-length”
evaluation strategy proposed by Kim et al. (2004). In this latter work, codewords are in-
troduced, which are created by clustering reoccurring background representations during a
training phase. These codewords are then amassed into codebooks at the pixel-level to cre-
ate independent, low-level background models. Compared to classic non-parametric models,
codebooks can accurately describe multimodal background regions and avoid corruption due
to static foreground while having a small memory footprint. This modeling approach was
first improved by Kim et al. (2005) to allow the online adaptation of codebooks, then by Wu
and Peng (2010) by extending codewords to the spatiotemporal domain, and more recently
<figure><img src="image_23.png" /><figcaption>Figure 5.1 Block diagram of the Pixel-based Adaptive Word Consensus Segmenter. Each block represents a major component detailed in Section 5.3.</figcaption></figure>

by Mayer and Mundy (2014) by using duration dependent hidden Markov models to identify and capture periodic background change patterns. Our proposed word-based modeling approach detailed in the following section differs from traditional codebook approaches in that it does not cluster background representations into unique codewords during a training phase. Furthermore, it allows words to be sorted within background models and replaced online based on their persistence in the observed data.

Pixel-based methods are not restricted to use intensity values for background modeling: they can also capture texture information using local descriptors. Doing so helps produce richer, “spatially aware” background samples that are critical for the detection of camouflaged foreground objects. Heikkila and Pietikäinen (2006); St-Charles and Bilodeau (2014); Yang et al. (2015); Silva et al. (2015); Lin et al. (2014) all use Local Binary Patterns (LBP) or other similar binary features for this purpose and achieve good tolerance to illumination variations. The works of Braham and Van Droogenbroeck (2015); Bouwmans (2014) have studied the proper selection and usage of low-level features in pixel-level background modeling.

Frame-level background modeling via Principal Component Analysis (PCA) and low-rank or sparse decomposition approaches is a popular alternative to pixel-level modeling (Oliver et al., 2000; Candès et al., 2011; Zhou et al., 2013; Gao et al., 2014). These approaches are however not ideal for surveillance applications as most rely on batch or offline processing or suffer from scaling problems. Sun et al. (2015) address scaling problems by reformulating principal component analysis for 2D images, and their method achieves much lower memory consumption and computational cost than traditional methods. Some online approaches have also been proposed recently (He et al., 2012; Feng et al., 2013; Seidel et al., 2014), but they are still very computationally expensive.

An early finding in the field is that background modeling should not be limited in scope to frame-wide or pixel-independent processes (Toyama et al., 1999). Doing so would restrict
their perception of change to a single spatial scale and therefore make it harder to address
common background maintenance challenges. Multi-scale and “hybrid” methods such as
those of Toyama et al. (1999); Chen et al. (2007); Wang et al. (2014b); Yang et al. (2015)
have emerged in light of this to improve segmentation coherence at different spatial scales.
Coarse-to-fine and block-based strategies can also be adopted to solve this problem. For ex-
ample, Stagliano et al. (2015) recently proposed a block-based modeling approach based on
sparse coding that relies on patch dictionaries learned online to improve spatial coherence.
Furthermore, features extracted from High-Efficiency Video Coding (HEVC) macroblocks
have been used by Dey and Kundu (2015) for low-cost block-based modeling with good spa-
tiotemporal coherence. Alternative solutions that rely on self-organizing maps (Maddalena
and Petrosino, 2012; Zhao et al., 2015; Ramírez-Alonso and Chacón-Murguía, 2016), neural
networks (Gregorio and Giordano, 2014; Braham and Van Droogenbroeck, 2016), or prob-
abilistic frameworks such as Markov Random Fields (Sheikh and Shah, 2005; Schick et al.,
2012; Wu and Peng, 2010) to expose relationships between independent background models
have also been studied.

A problem common to most classic methods is that they lack flexibility: even though they
can provide good results on individual sequences when tuned properly, few of them can
actually perform equally well across large datasets when used “out-of-the-box”. Modern
methods sometimes propose ways to dynamically control either model complexity (Zivkovic
and van der Heijden, 2006; Haines and Xiang, 2014), adaptation rates (Lin et al., 2011; Chen
and Ellis, 2014) or classification thresholds (Van Droogenbroeck and Paquot, 2012; Wang and
Dudek, 2014) online. These however often rely on complex object-level or frame-level analyses
and react slowly to intermittent changes. In the case of PBAS (Hofmann et al., 2012), which
simultaneously controls model adaptation rates and classification thresholds via pixel-level
feedback loops, delayed and fluctuating sensitivity variations can still cause segmentation
problems. Our previous work (St-Charles et al., 2015a) addressed this by proposing fast-
response feedback loops based on a dual measurement approach, but did not offer a way to
simultaneously control model complexity. The recent solution of Bianco et al. (2015) also
addresses the flexibility problem of segmentation methods by combining them using a genetic
programming approach.

The interested reader is referred to recent surveys of Brutzer et al. (2011); Bouwmans (2014);
Sobral and Vacavant (2014); Bouwmans and Zahzah (2014); Goyette et al. (2014) for details
on the background subtraction field.
## 5.3 Methodology

As shown in Figure 5.1, our proposed method can be split into five components: 1) a full “background model”, actually composed of multiple pixel-level (local) models and a frame-level (global) model; 2) a classifier, which produces “raw” segmentation decisions for each pixel based on outlier detection; 3) a post-processing (or regularization) step that relies on basic morphological operations to measure and eliminate segmentation noise; 4) a recursive measurement filter used to simulate the response of a sliding window over model-observation similarity indicators; and 5) a closed-loop controller block, responsible for adjusting the internal parameters of other components based on their state and output. The pixel- and frame-level models along with our classification strategy are presented in Sections 5.3.1 and 5.3.2. The recursive measurement filter as well as feedback mechanisms and controllers are discussed in Section 5.3.3. Finally, three heuristics adopted to further improve our method’s adaptability are presented in Section 5.3.4.

### 5.3.1 Word consensus for pixel-level modeling

Our novel non-parametric modeling approach is essentially a hybrid between codebook (Kim et al., 2005) and sample consensus strategies (Wang and Suter, 2006; Van Droogenbroeck and Barnich, 2014). “Word consensus” inherits the main advantages of these modeling strategies while avoiding their pitfalls, namely costly updates and high memory requirements. As in other pixel-level, non-parametric modeling approaches, the idea behind word consensus is to simultaneously build independent background models by gathering data samples from local observations. Then, new observations can be classified based on their model overlap. In the following paragraphs, we present an overview of our proposed word-based modeling approach and define some basic terms, and then discuss feature matching, classification and update mechanisms.

**Overview and definitions.** In contrast to the terminology of Kim et al. (2005), we consider model samples as “words” instead of “codewords” since they are not obtained via clustering, and are thus not necessarily unique. Furthermore, our word-based models are termed “dictionary” instead of “codebooks”, as the words they contain are sorted and systematically parsed for matches during classification. We define the “local” dictionary of a given pixel $x$ as

$$B_l(x) = \{\omega_1, \omega_2, \dots, \omega_N\} \qquad (5.1)$$

where $\omega_n$ are background words, and $N$ is the number of words in the dictionary. Each word essentially consists of a background representation (characterized using local image descrip-
tors and/or low-level features) and a transient persistence value. This value is estimated online based on the recurrence (i.e. match count) of the word among recent observations at x. In our modeling approach, persistence defines the basic criteria of word replacement and update policies: the more “persistent” a word is, the less likely it is to be forgotten or replaced by new observations. In comparison to modeling approaches with planned obsolescence policies, our approach is especially useful when segmenting intermittently moving objects.

We evaluate the persistence of a word $\omega$ at time $t$ using

$$q_t(\omega) = \frac{n_{\omega}}{(t_{\omega}^l - t_{\omega}^f) + 2 \cdot (t - t_{\omega}^l) + t_0}, \qquad (5.2)$$

where $n_{\omega}$ is $\omega$'s total occurrence count, $t_{\omega}^l$ and $t_{\omega}^f$ are, respectively, the time at which it was first and last observed, and $t_0$ is a fixed offset value. The principle behind this equation unique to our modeling approach is comparable to the maximum negative run-length measure of Kim et al. (2005) and the confidence capping of distribution components of Haines and Xiang (2014): it promotes the retention of recurring background words and helps forget those that have not been observed recently. The first denominator term, $(t_{\omega}^l - t_{\omega}^f)$, measures the lifespan of $\omega$ and is used to scale the persistence of words to the [0, 1] range. It also reflects the “persistence inertia” of $\omega$, i.e. how well it resists persistence value fluctuations caused by short time spans without occurrences. Besides, note that since the second term of the denominator, $(t - t_{\omega}^l)$, is multiplied by two, the penalty incurred by a distant last occurrence is essentially doubled. This means that while recurrence is important, good words that suddenly disappear from observations can still be eliminated quickly despite very long lifespans. The time offset $t_0$ is only used here to prevent new words from having important persistence values.

Given (5.2), a mandatory training phase to learn and filter words in local dictionaries is not required since the importance of all words can be continuously estimated over the analyzed sequence. Thus, the segmentation process can be fully initialized by sampling local pixel neighborhoods from a single video frame that may contain foreground. Dictionaries will then naturally stabilize over time to contain only recurring background words. This approach however requires proper feature matching and update mechanisms, which will be discussed next. For now, note that our local dictionaries adapt to permanent background changes by learning a new word when local observations cannot be matched to any existing background word. We illustrated the content of a local dictionary for a multimodal background region in Figure 5.2a.

To avoid the infinite expansion of local dictionaries, we cap the number of active words
<figure><img src="image_24.png" /><figcaption>Figure 5.2 Illustrations of possible local dictionary content for dynamic and static background regions. The bars next to each word represents their relative importance in the dictionary based on persistence. In (a), different words are kept active simultaneously while new words are inserted. In (b), the dictionary is shown right after model initialization, and many overlapping words are present due to local neighborhood sampling. In (c), the same dictionary as (b) is presented but at a later time in the sequence, showing a reduced number of active words.</figcaption></figure>

they can contain (N). To keep word counts low, we can ignore or remove words that have negligible persistence values. If a dictionary is full, words with the lowest persistence values are eliminated and replaced by new ones. To make these evaluations and replacements more efficient, we systematically reorder the content of local dictionaries during the matching process using a bubble sort algorithm. That way, more persistent words are checked for matches first, and they are less likely to be replaced by new ones.

**Feature selection and matching.** In PAWCS, we characterize pixel neighborhoods (for both background words and local observations) using RGB intensities and Local Binary Similarity Pattern descriptors (LBSP, Bilodeau et al., 2013). Local descriptors can be used like any other low-level feature in our modeling approach since, by design, we avoid merging or
clustering data samples. The goal of using LBSP here is to improve robustness to illumination variations and enhance segmentation coherence (or smoothness) through local texture description and matching. As shown by St-Charles and Bilodeau (2014), this color/LBSP description approach also boosts change detection sensitivity (which is beneficial), but induces additional false positives in regions with dynamic textures. We discuss how we solve this problem via feedback mechanisms below.

First, to determine if a word $\omega$ from a local dictionary $B_t(x)$ matches the observation of $x$ at time $t$ (noted $I_t(x)$), we evaluate their color resemblance (via $l_1$ distance and color distortion, c.f. Kim et al., 2004) and LBSP intersection (via Hamming distance). If all three distances fall below given change detection thresholds, then $\omega$ is considered a match for $I_t(x)$. To shorten the equations presented in the following sections, we simply write $||I_t(x) - \omega|| < R_t(x)$ to refer to this matching step. We define $R_t(x)$ as a distance threshold for $x$ at time $t$, with $R_t(x) \ge 1$. In practice, color and LBSP distance thresholding is done in parallel, and their threshold values are respectively calculated from $R_t(x)$ using

$$R_{c,t}(x) = R_c \cdot \sqrt{R_t(x)} \qquad (5.3a)$$

and

$$R_{d,t}(x) = R_d + 2^{R_t(x)}, \qquad (5.3b)$$

where $R_c$ and $R_d$ are fixed baseline values. Unlike color thresholds, LBSP descriptor thresholds rely on an exponential relation which is better suited to their nature: small $R_{d,t}(x)$ values lead to discriminative texture matching, and larger $R_{d,t}(x)$ values are used for approximate gradient matching. As we will discuss in Section 5.3.3, $R_t(x)$ is automatically increased in regions exhibiting dynamic textures. A large enough $R_t(x)$ value can thus exclude LBSP descriptors from the matching process by inducing a $R_{d,t}(x)$ value larger than the maximum LBSP Hamming Distance. This leads to a desirable reduction of change detection sensitivity, and ultimately to the elimination of false positives in dynamic texture regions.

**Pixel classification.** The nature of binary segmentation methods based on change detection implies that all pixels in a video frame are considered foreground unless their description matches with the background model. As explained earlier, we do not impose a unicity constraint on words in local dictionaries. This means that finding a single match in the background model for an observation is not enough to directly proclaim a pixel as background. Our classification approach instead relies on the idea of pixel labeling via consensus, i.e. we consider all words from a local dictionary that overlap (or match) the observation of a pixel in feature space to determine its segmentation label. In classic sample consensus methods,
the number of matched background samples is the sole determinant of the classifier: if at least a given number of samples are matched, the pixel is labeled as background. This can be interpreted as one-class classification for outlier detection. In our case, rather than using a fixed match count as the background classification threshold, we calculate the persistence sum of all matched words, and compare this value with a second dynamic threshold (noted $W_t(x)$). More specifically, for a pixel $x$, we compute the local dictionary persistence sum as

$$Q_{l,t}(x) = \sum_{\omega \in B_l(x)} q_t(\omega) \quad \text{s.t.} \quad \|I_t(x) - \omega\| < R_t(x), \qquad (5.4)$$

and then classify $x$ as foreground (1) or background (0) using

$$S_t(x) = \begin{cases} 1 & \text{if } Q_{l,t}(x) < W_t(x) \\ 0 & \text{otherwise} \end{cases}, \qquad (5.5)$$

where $S_t$ is the output (raw) segmentation map. Again, we discuss how $W_t(x)$ is automatically computed in Section 5.3.3.

Since we do not rely on foreground modeling, (5.4) and (5.5) encapsulate a one-class outlier detector. Here, $R_t(x)$ dynamically controls the reachability distance in feature space, which is similar to having an adaptive $k$ in a $k$-Nearest Neighbor classifier. On the other hand, $W_t(x)$ dictates the minimum cumulative instance weight (or persistence sum) required to consider $x$ as an inlier. Note that the persistence sum $Q_{l,t}(x)$ can be seen as a general indicator of how well $I_t(x)$ is represented by the content of $B_l(x)$. We will reuse this representativeness estimation in Section 5.3.3 to evaluate model-observation similarity.

Remember that words are sorted in local dictionaries based on their persistence values; this means the summation in (5.4) can be implemented so that it stops once the accumulated persistence is greater than $W_t(x)$. The primary ensuing advantage is faster processing, as dictionaries do not need to be fully parsed for matches. This termination criterion however also has a beneficial effect on the way word persistence values fluctuate over time, which we discuss next.

**Word and dictionary updates.** As stated before, the persistence value of a word can be evaluated online using (5.2) based on its occurrence count and the time of its first/last observations. In practice, these persistence parameters are only updated when a match is found in (5.4). This means that if the summation stops before reaching a potential matching word $\omega$ because similar alternatives exist with higher persistence values, then $\omega$'s persistence will slowly decay, and it will slide down in the dictionary's word ranking. As illustrated in Figure 5.2b and 5.2c, this is actually an important update mechanism that gradually elimi-
nates background words which overlap in feature space. This mechanism is thus responsible for controlling the number of active words (i.e. words with a significant persistence value) in each local dictionary based on the complexity of its associated background region. Below, we discuss two other update mechanisms needed to make our proposed modeling approach universal.

The modeling approach described so far cannot cope with gradual background changes (e.g. the illumination variation caused by a growing cloud cover) since the background descriptions kept by words inside local dictionaries are not updated. To improve robustness in such cases, we randomly replace the color component of matched background words with observed values. This is only done when local texture variation (expressed by the distance between matched and observed LBSP descriptors) and color distortion (as presented by Kim et al., 2004) are negligible, and with probability $\rho = 1/T_t(x)$. Here, $T_t(x) \ge 1$ is a dynamic update rate further discussed in Section 5.3.3. This update mechanism is meant to only allow a small proportion of background words to be modified in response to gradual illumination changes. Therefore, words left untouched will continue modeling the previous background state when the change is only temporary. This strategy implicitly prevents incorrigible model drift and the saturation of local dictionaries by words whose descriptions differ in brightness, but not in local texture. The direct replacement of a word's color component by an observed value also helps diversify dictionary content, and it is less costly than merging them.

In order to improve the consistency between neighboring local dictionaries, our method shares an important trait with recent sample-consensus methods (e.g. Barnich and Van Droogenbroeck, 2011; Hofmann et al., 2012; St-Charles and Bilodeau, 2014; St-Charles et al., 2015a): pixel-level background information diffusion. The diffusion process increases robustness to infrequent periodic change by sharing information between afflicted regions, and helps erode tenacious false positive segmentation blobs caused by “ghosts” in the background model (see Cucchiara et al., 2003) for an exact definition). In its original form (introduced by Barnich and Van Droogenbroeck, 2011), information diffusion grants pixel models adjacent to $x$ a chance to have one of their samples randomly replaced by the description of $I_t(x)$, but only if $x$ is classified as background. To achieve similar results in our novel modeling approach, when (5.5) returns $S_t(x) = 0$, we randomly select a neighbor of $x$ and update the persistence of each word of its local dictionary that matches with $I_t(x)$. Again, the probability of doing this is $\rho = 1/T_t(x)$. Note that a beneficial effect of these updates is a persistence boost for words in static background regions, which helps detect camouflaged and immobile foreground objects. In contrast to the spatial context improvement proposed by Wu and Peng (2010), our strategy allows pixel models to resist disturbances caused by small background displacements and vibrating cameras because spatial information is shared proactively.
The three proposed update mechanisms allow our pixel models to behave like codebooks in static background regions. Once stable, each local dictionary requires only one or two highly persistent words (which are kept up to date during illumination changes) to provide good segmentation results. In dynamic background regions, our pixel models are akin to sample consensus models, where 20 to 30 different words can be active at once, all with low cohesion and persistence values. Our pixel-level modeling approach alone is however unable to recognize patterns that are too large or outside the influence of local information diffusion. For this, we introduce a frame-level modeling approach, described next.

### 5.3.2 Word consensus for frame-level modeling

Using a frame-wide or “global” dictionary (noted $B_g$) along with local dictionaries for classifications fulfills the requirement set by the final Wallflower principle (Toyama et al., 1999), i.e. background models should take into account changes at differing spatial scales. Capturing large scale background patterns is crucial when the observed scene exhibits intermittent change over large areas, or when background elements are removed from it. Besides, our pixel description approach produces highly specific words that, if tied to intermittent background patterns, may be discarded before being observed enough times to build a strong persistence value. Our proposed global dictionary model acts as a long term memory that tracks the use of common words and spreads their influence beyond the reach of the pixel-level diffusion update mechanism. Its only purpose is to provide a safeguard against false positive detections by relabeling $x$ (i.e. overruling $S_t(x) = 1$) when a “global” word with strong persistence is matched to its pixel-level observation.

The persistence definition of (5.2) becomes problematic when considering background words in a global setting, as it implies no ownership or localization concept. Moreover, the state of a dictionary shared among all pixel models would depend on the ordering of local updates. Therefore, we define the persistence of global words by using 2D maps that “localize” the importance of these words in image space. These persistence maps can be seen as heat maps over the observed frames; some examples are shown in Figure 5.3. For each pixel $x$ and each global word $\omega$, a map value (noted $\Phi_{\omega}(x)$) is directly linked to a single pixel model $B_l(x)$. This means maps can be fully updated asynchronously. Furthermore, this one-for-one mapping in image space also means that frame-wide operations (blurring, saturation, decimation) on global word persistence maps are well defined and easy to implement.

Persistence map contents are updated in two ways. First, each time a pixel $x$ is classified as background, it may be randomly elected to parse $B_g$ for a matching word $\omega$ and perform a
<figure><img src="image_25.png" /><figcaption>Figure 5.3 Snapshots of the actual global word persistence maps used in the CDnet2012 fountain02 sequence at frame 500. The top-left corners show the pixel color description of each word; texture is omitted for illustration purposes. Brighter spots indicate where matches occurred and the map was updated; those points are the “seeds” from which the persistence is diffused. In total, 24 global words were active (the 12 with highest total persistence are shown here), covering over 95% of the image space with non-zero persistence values.</figcaption></figure>

localized update of its persistence map. We define this update as

$$ \Phi_{\omega}(x) = \min(\Phi_{\omega}(x) + Q_{l,t}(x), Q_{g,t}(x)). \qquad (5.6) $$

This essentially creates a seed point in $\Phi_{\omega}$ used to propagate persistence values to neighboring pixels. Second, the propagation itself is achieved by periodically blurring the maps of all global words using a normalized box filter. To avoid obtaining homogeneous results over time, $\Phi_{\omega}(x)$ values are also decimated while filtering. These two steps create another word diffusion mechanism that has a much larger reach than the one presented in Section 5.3.1. Persistence map decimation also allows the global dictionary to “forget” words over time.

Finally, the foreground classification of a pixel $x$ can be overruled if a matching global word (with a strong localized persistence) is found. More specifically, we replace (5.5) by

$$ S_t(x) = \begin{cases} 1 & \text{if } Q_{l,t}(x) + Q_{g,t}(x) < W_t(x) \\ 0 & \text{otherwise} \end{cases}, \qquad (5.7) $$
where

$$Q_{g,t}(x) = \begin{cases} \Phi_{\omega}(x) & \text{if } \exists \omega \in B_g \text{ s.t. } \|I_t(x) - \omega\| < R_t(x) \\ 0 & \text{otherwise (i.e. no match found)} \end{cases} \qquad (5.8)$$

Since the LBSP descriptors we use are highly specific and hard to match across regions, we simplify the global word matching step in (5.8): instead of using a Hamming distance, we compare the Hamming weights of the descriptors. This is equivalent to an approximate gradient magnitude comparison. While gradient orientation information is lost, this approach preserves texture strength information, which is enough for discriminative change detection.

New words can also be inserted in global dictionaries: pixel models can be randomly selected to copy one of their highly-persistent local background words to $B_g$ and initialize its persistence map, but only if it is missing from $B_g$. Again, the maximum number of active words in $B_g$ is capped ($N$), and words with the lowest overall persistence are replaced first once full. The initialization is done by simply querying random pixel models for words and filling persistence maps until the global dictionary is full. Note that since (5.8) and the update mechanisms only target one word at a time (i.e. the first found match), and since global word descriptions do not change throughout their lifespan, feature space overlap between global words is highly unlikely. This means global dictionaries typically contain more unique words than local dictionaries.

### 5.3.3 Pixel-level feedback

Recall that the equations presented in the previous sections primarily relied on three types of pixel-independent parameters. Namely, the feature-space distance threshold used for matching in (5.4) and (5.8), $R_t(x)$; the persistence threshold used for classification in (5.5) and (5.7), $W_t(x)$; and the rate used to determine the probability of triggering all update mechanisms, $T_t(x)$. While fixed values could be used frame-wide, they would need to be determined empirically from the analyzed videos, and doing so would prevent pixel models from handling multiple segmentation challenges at once. Therefore, we dynamically adjust these internal parameters using pixel level closed-loop controllers. Subsequently, we use simple heuristics to increase the chance of triggering further model updates and parameter adjustments where needed. As stated in Section 5.1, four aspects of our method are monitored and used to control these feedback mechanisms: two of them are related to the state of the background model (model-observation similarity and illumination update propagation) and two to the output (segmentation noise and instability). These are discussed below.

Evaluating the similarity between local dictionary words and local observations captured from input frames is the first step in determining if the background is adequately modeled. We do
so for each pixel $x$ by recursively filtering the estimations of minimal matching distances between local observations and words along with the “representativeness gap” of missed matches (defined below). This provides a temporally smooth measurement of model-observation similarity, noted $\bar{d}_t(x)$, which can be used in closed-loop controllers. The proposed recurrence relation is defined as

$$ \bar{d}_t(x) = (1-\alpha) \cdot \bar{d}_{t-1}(x) + \alpha \cdot d_t(x) \qquad (5.9) $$

with

$$ d_t(x) = \max \left( \min_{\omega \in B_l(x)} \left\| I_t(x) - \omega \right\|, \frac{W_t(x) - Q_{l,t}(x)}{W_t(x)} \right), \qquad (5.10) $$

where $\alpha \in [0, 1]$ is a fixed coefficient, and $\frac{W_t(x)-Q_{l,t}(x)}{W_t(x)}$ is the “representativeness gap”. As stated earlier, this is because $Q_{l,t}(x)$ can be interpreted as an indicator of model representativeness.

In practice, since multiple distances are evaluated in $||I_t(x) - \omega||$, we find the minimum distance for each feature (color, LBSP) in $B_l(x)$ independently, normalize them to the [0, 1] range, and then only use the maximum one in (5.10). The “representativeness gap” is used to counterbalance the similarity score for models that have good matches but low persistence sums. In the end, $d_t(x)$ and $\bar{d}_t(x)$ can only take values in the [0, 1] range. The nature of the two terms compared in (5.10) makes “ideal” background modeling (reflected by $d(x) \approx 0$) very hard to achieve in practice. This forces continuous feedback that helps diversify pixel models. The recurrence relation of (5.9) essentially models the infinite impulse response of an exponentially weighted sliding window filter, but at a very low computational cost. This approach allows fast feedback responses to intermittent and irregular changes.

Since $\bar{d}_t(x)$ is updated every frame, foreground objects that pass or stay immobile over $x$ will inevitably increase its value over time. Therefore, this first indicator cannot be used by itself to control parameter adjustments as it does not always truly reflect the similarity between background models and observations. To address this, we rely on a second pixel-level indicator, noted $v_t(x)$, that monitors noise in the segmentation results. The assumption behind $v_t(x)$ is that inadequately modeled regions emit more noise (i.e. alternating segmentation labels) than other regions, which are instead constantly labeled as foreground or background. We define $v_t(x)$ as a segmentation noise accumulator, and update it using

$$ v_t(x) = \begin{cases} v_{t-1}(x) + 1 & \text{if } (S_t(x) \oplus S_{t-1}(x)) = 1 \\ v_{t-1}(x) - 0.1 & \text{otherwise} \end{cases} \qquad (5.11) $$

where $\oplus$ is the XOR operator, and $v_t(x)$ is prevented from taking negative values. This definition essentially means that only static regions will exhibit low $v_t(x)$ values.
Using $\bar{d}_t(x)$ and $v_t(x)$, we can now describe our pixel-level controllers. First, we define the adjustment mechanism for local update rates as

$$ T_t(x) = \begin{cases} T_{t-1}(x) + \frac{\lambda_T}{v_t(x) \cdot \bar{d}_t(x)} & \text{if } S_t(x) = 1 \\ T_{t-1}(x) - \frac{\lambda_T \cdot v_t(x)}{2 \cdot \bar{d}_t(x)} & \text{if } S_t(x) = 0 \end{cases} \qquad (5.12) $$

where $\lambda_T \in [0, 1]$ is a fixed scaling factor, and $T_t(x)$ is bound to the [1, 256] interval. Like all sample-consensus methods, we use an inversely proportional relation to calculate the probability $\rho$ of triggering an update mechanism from $T_t(x)$. This means that high $T(x)$ values lead to fewer updates, and that when foreground is detected in static regions with low segmentation noise, model updates will almost immediately stop. In other words, $T(x)$ will max out quickly due to $v_t(x) \approx \bar{d}_t(x) \approx 0$. However, dynamic and noisy background regions will keep allowing model updates for much longer, as in those cases, $v_t(x) \gg 0$ and $\bar{d}_t(x) \approx 1$, which results in smoother variations.

Having models that update frequently is usually not enough to eliminate all false foreground classifications caused by strong dynamic background change. Locally adjusting feature matching thresholds is often the fallback solution to avoid having to build and maintain very large background models. As stated in Section 5.3.1, we derive both color and LBSP matching distance thresholds from a common value, $R_t(x)$. The adjustment control loop behind this parameter based on our two pixel-level indicators can be described as

$$ R_t(x) = \begin{cases} R_{t-1}(x) + \lambda_R v_t(x) & \text{if } R_{t-1}(x) < (1+\bar{d}_t(x) \cdot 2)^2 \\ R_{t-1}(x) - \frac{\lambda_R}{v_t(x)} & \text{otherwise} \end{cases} \qquad (5.13) $$

where $\lambda_R \in [0, 1]$ is a fixed scaling factor. Note that $R_t(x)$ can only take values greater or equal to 1; this lower limit reflects the baseline matching distance threshold used in perfectly static regions. We control $R_t(x)$ variations via $\bar{d}_t(x)$ based on an exponential relation since it allows much easier feature matching in highly unstable regions (i.e. when $\bar{d}_t(x) \gg 0$). Here, $v_t(x)$ directly controls the variation step size of $R_t(x)$. In static regions, it prevents $R_t(x)$ from increasing too fast (which helps against camouflage problems), and in dynamic regions, it prevents it from decreasing too fast while $\bar{d}_t(x)$ fluctuates.

Feature matching distances and local persistence sums are closely related in the feedback process as both influence $\bar{d}_t(x)$ through (5.10). Therefore, we tie the adjustment mechanism
of persistence thresholds to $R_t(x)$, and define it as

$$W_t(x) = \frac{q_t(\omega_1)}{R_{t-1}(x) \cdot 2} \qquad (5.14)$$

where $\omega_1$ is the first word of $B_t(x)$, and thus its most persistent one due to sorting. The idea here is to always have at least one local word with enough persistence to classify a pixel as background. This also means that the value of $W_t(x)$ is kept in the persistence range dictated by the words of $B_t(x)$, and each pixel model can have a unique classification behavior.

While our pixel-level controllers rely on segmentation noise to provide rapid parameter adjustments, this type of noise is an inherent characteristic of pixel-based segmentation due to shot noise in the analyzed images. Segmentation noise can also be easily eliminated afterwards using post-processing or regularization techniques. In PAWCS, we ultimately clean the raw segmentation maps $S_t$ by using median blurring and morphological operations. This essentially mimics the effect of a more complex frame-level regularization approach at a low cost.

### 5.3.4 Model adaptability

The pixel-level controllers are mostly responsible for the overall flexibility of our method, but we also define three heuristics to further improve model adaptability. The first one relies on texture analysis to provoke extra updates in uniform background regions. This leads to stronger word persistence in local dictionaries, and thus better long-term word retention. In short, we cut down the value of $T_t(x)$ when the observed LBSP descriptor in $I_t(x)$ is “flat” (i.e. its Hamming weight is close to zero), which causes update mechanisms to trigger more often. The assumption here is that uniform regions are better background candidates than regions with strong gradients. Cluttered regions are largely unaffected by this criterion; this indirectly helps prevent “ghosts” from forming in highly textured background regions due to small, temporary texture displacements.

The second heuristic we use is based on segmentation instability. Large, long-term discrepancies between the “raw” output segmentation $S_t(x)$ and its post-processed equivalent are not as likely due to alternating labels than to small dynamic background regions (e.g. leaves in a tree). Our local feature description approach is very sensitive to such small variations; to help post-processing, we double the fixed $R_d$ offset in (5.3b) when discrepancies above a fixed threshold are detected for $x$. This reduces the texture change detection sensitivity in the matching process and eliminates more false positive classifications in those regions.
Our last heuristic is responsible for spreading illumination updates between neighboring pixel models and causing chain reactions that allow large background surfaces to be updated rapidly. As stated in Section 5.3.1, the color component of words can sometimes be updated to account for gradual changes in the background. To propagate these updates, we keep a 2D map of where they happen; then, for a pixel *x*, if one of its neighbors was recently updated, we halve the value of *T*<sub>*t*</sub>(*x*). This approach allows our model to respond rapidly and efficiently to frame-wide lighting variations.

## 5.4 Experiments

The state-of-the-art presented in Section 5.2 makes it clear that traditional datasets (e.g. the work of Toyama et al., 1999; Li et al., 2004) are too small and no longer challenging to modern background subtraction methods. Moreover, classic methods (e.g. Stauffer and Grimson, 1999; Elgammal et al., 2000) have long since been surpassed and no longer offer a good performance reference. To properly evaluate our method, we rely on the 2012 and 2014 versions of the ChangeDetection.net (CDnet) benchmark and dataset (Goyette et al., 2014, 2012; Wang et al., 2014a). Unlike older alternatives, the CDnet dataset offers a wide variety of real-world sequences split into eleven categories based on the challenges they contain. Totaling nearly 160,000 manually annotated frames, it is several orders of magnitude larger than other real-world datasets, and multiple times larger than those based on synthetic data. Part of the groundtruth is also withheld and kept for online testing to prevent overtuning.

In Section 5.4.1 and 5.4.2, we respectively discuss our 2012 and 2014 CDnet results, and compare them to those of 27 methods listed online<fnref n="1" /> or self-reported in prior publications (we report only the top performers). Note that not all methods tested on the 2012 dataset have been tested on the 2014 version, as the latter is much harder, and some authors prefer focusing on a smaller subset of segmentation challenges. Finally, we discuss memory footprint, processing speed and the possibility of a parallel implementation in Section 5.4.3.

We use the same PAWCS configuration to process all sequences of the 2012 and 2014 versions of the CDnet dataset. This is a disadvantage, as methods which were only tested on the 2012 version were specifically tuned for only those categories. We assume all self-reported results used for comparisons followed the tuning guidelines of the CDnet benchmark. To determine which parameters to use for LBSP feature description, we followed the approach of St-Charles et al. (2015a), which dynamically balances them based on the observed scene's gradient content. We also used the frame-level component presented by St-Charles et al.

<footnote n="1">1. http://www.changedetection.net</footnote>
(2015a) to detect drastic changes (e.g. light switch events) in the analyzed sequences, and automatically reset our model when needed. Besides, we fix the value of the metaparameters presented in the previous sections as follows:

- Word weight offset value: $t_0 = 1000$

- Maximum number of words per dictionary: $N = 50$

- Baseline color distance threshold: $R_c = 20$

- Baseline LBSP distance threshold: $R_d = 2$

- Feedback recurrence adaptation rate: $\alpha = 0.01$

- Local update rate change factor: $\lambda_T = 0.5$

- Local distance threshold change factor: $\lambda_R = 0.01$

For more details on the post-processing steps and feedback heuristics of PAWCS, the reader is invited to refer to our implementation<fnref n="2" />.

We limit the presentation of qualitative results (Figures 5.4 and 5.5) due to space constraints and because the difference between state-of-the-art methods and groundtruth is sometimes hard to perceive. Our full segmentation results can be downloaded via the CDnet evaluation platform, where more granular comparisons are also possible with most methods based on seven evaluation metrics.

### 5.4.1 CDnet 2012

We first present in Table 5.1 the average Recall (Re), Precision (Pr), F-Measure (FM) and Matthew's Correlation Coefficient (MCC) scores of PAWCS on CDnet2012. The definition of the first three metrics can be found in the work of Goyette et al. (2012). MCC is also used here since it provides a good assessment of overall performance in unbalanced binary classification problems, which background subtraction falls into. It is defined by

$$MCC = \frac{(TP \cdot TN) - (FP \cdot FN)}{\sqrt{(TP+FP) \cdot (TP+FN) \cdot (TN+FP) \cdot (TN+FN)}}, \quad (5.15)$$

where True Positives (TP), True Negatives (TN), False Positives (FP) and False Negatives (FN) are defined like in the work of Goyette et al. (2012).

Note that the description of each challenge, category and sequence is provided by Goyette et al. (2014, 2012). We can see from Table 5.1 that our method offers good balance between precision and recall in all test categories but “camera jitter” and “intermittent object motion”.

<footnote n="2">2. https://github.com/plstcharles/litiv</footnote>
<table><caption>Table 5.1 Segmentation results of PAWCS on CDnet2012</caption><thead><tr><th>Category</th><th>Re</th><th>Pr</th><th>FM</th><th>MCC</th></tr></thead><tbody><tr><td>baseline</td><td>0.941</td><td>0.939</td><td>0.940</td><td>0.938</td></tr><tr><td>camera jitter</td><td>0.784</td><td>0.866</td><td>0.814</td><td>0.812</td></tr><tr><td>dynamic background</td><td>0.887</td><td>0.904</td><td>0.894</td><td>0.894</td></tr><tr><td>interm. obj. motion</td><td>0.749</td><td>0.839</td><td>0.776</td><td>0.774</td></tr><tr><td>shadow</td><td>0.917</td><td>0.871</td><td>0.891</td><td>0.887</td></tr><tr><td>thermal</td><td>0.850</td><td>0.828</td><td>0.832</td><td>0.828</td></tr><tr><td>overall</td><td>0.855</td><td>0.875</td><td>0.858</td><td>0.855</td></tr></tbody></table>

In the former, vibrating cameras cause the entire observed scenes to be perceived as dynamic. This means that pixel model updates trigger very often and that static foreground objects become part of them very fast, which leads to lower Recall scores. The second problematic category is of particular interest here: “intermittent object motion” contains four videos focused on long-term immobile object segmentation, and two on “ghost” elimination (i.e. purging the model of background objects removed from the scene). A lower Recall score in this category indicates that some foreground objects were eventually “lost” to the background model over time. In reality, this difference is not surprising, as very little time is allowed to “learn” the empty background, therefore our words never attain “strong” persistence values. This category is also by far the hardest in CDnet 2012; we discuss it in detail later in this section. The other categories shown in Table 5.1 deal with more traditional challenges of background subtraction, and our method performs well in all of them.

Next, we present in Table 5.2 a compilation of the per-category and overall F-Measure scores of the 23 top-performing methods published and available online as of July 2015. Like Haines and Xiang (2014); St-Charles et al. (2015a), we do not use the official CDnet rankings in these results, as adding and removing methods from the comparison pool (no matter their performance) can drastically affect their final ordering. The F-Measure scores used instead were found to be closely correlated with the method rankings in all three previous CDnet evaluation reports (Goyette et al., 2014, 2012; Wang et al., 2014a). F-Measure is also the most common metric used for comparison in the literature, and thus allows us to list practically all self-reported results of methods not yet on the online benchmark.

Table 5.2 shows that PAWCS outperforms all other methods based on overall Recall, Precision, and F-Measure scores for CDnet2012. It also places first or second for F-Measure in four out of six categories, with a noticeable gap to the state-of-the-art only in “intermittent object motion”. Even in the “camera jitter” category, the results of PAWCS are only slightly worse than those of the best methods, which rely on multiple configurations (Chen et al.,
<table><caption>Table 5.2 Average per-category and overall scores on CDnet2012</caption><thead><tr><th rowspan="2">Method</th><th>Baseline</th><th>Cam. Jitt.</th><th>Dyn. Bg</th><th>Int. Mot.</th><th>Shadow</th><th>Thermal</th><th colspan="3">Overall (2012)</th></tr><tr><th>FM</th><th>FM</th><th>FM</th><th>FM</th><th>FM</th><th>FM</th><th>Re</th><th>Pr</th><th>FM↓</th></tr></thead><tbody><tr><td>PAWCS (proposed)</td><td>0.940</td><td>0.814</td><td>0.894</td><td>0.776</td><td>0.891</td><td>0.832</td><td>0.855</td><td>0.875</td><td>0.858</td></tr><tr><td>Chen et al. (2015)†*</td><td>0.935</td><td>0.817</td><td>0.867</td><td>0.798</td><td>0.813</td><td>0.825</td><td>-</td><td>-</td><td>0.842</td></tr><tr><td>Wang et al. (2014b)*</td><td>0.933</td><td>0.751</td><td>0.879</td><td>0.789</td><td>0.883</td><td>0.777</td><td>0.838</td><td>0.867</td><td>0.835</td></tr><tr><td>St-Charles et al. (2015a)*</td><td>0.950</td><td>0.815</td><td>0.818</td><td>0.657</td><td>0.899</td><td>0.817</td><td>0.828</td><td>0.858</td><td>0.826</td></tr><tr><td>Sajid and Cheung (2015)*</td><td>0.928</td><td>0.836</td><td>0.790</td><td>0.709</td><td>0.778</td><td>0.811</td><td>0.790</td><td>0.849</td><td>0.809</td></tr><tr><td>Gao et al. (2014)†</td><td>0.928</td><td>0.815</td><td>0.782</td><td>0.653</td><td>0.806</td><td>0.760</td><td>0.799</td><td>0.798</td><td>0.796</td></tr><tr><td>Wang and Dudek (2014)*</td><td>0.881</td><td>0.711</td><td>0.843</td><td>0.721</td><td>0.813</td><td>0.760</td><td>0.791</td><td>0.827</td><td>0.788</td></tr><tr><td>Gregorio and Giordano (2013)</td><td>0.908</td><td>0.781</td><td>0.809</td><td>0.567</td><td>0.841</td><td>0.762</td><td>0.818</td><td>0.774</td><td>0.778</td></tr><tr><td>Sedky et al. (2014)</td><td>0.933</td><td>0.716</td><td>0.787</td><td>0.566</td><td>0.884</td><td>0.776</td><td>0.777</td><td>0.846</td><td>0.777</td></tr><tr><td>Haines and Xiang (2014)</td><td>0.929</td><td>0.748</td><td>0.814</td><td>0.542</td><td>0.813</td><td>0.813</td><td>0.827</td><td>0.793</td><td>0.776</td></tr><tr><td>Stagliano et al. (2015)†</td><td>0.877</td><td>0.725</td><td>0.753</td><td>0.686</td><td>0.810</td><td>0.793</td><td>0.785</td><td>0.773</td><td>0.774</td></tr><tr><td>Yang et al. (2015)†</td><td>0.883</td><td>0.787</td><td>0.808</td><td>0.525</td><td>0.860</td><td>0.754</td><td>0.828</td><td>0.786</td><td>0.769</td></tr><tr><td>Dey and Kundu (2015)†</td><td>0.934</td><td>0.712</td><td>0.828</td><td>0.535</td><td>0.864</td><td>0.735</td><td>-</td><td>-</td><td>0.768<sup>b</sup></td></tr><tr><td>Evangelio et al. (2014)</td><td>0.921</td><td>0.672</td><td>0.688</td><td>0.715</td><td>0.865</td><td>0.735</td><td>0.768</td><td>0.835</td><td>0.766</td></tr><tr><td>Zhou et al. (2013)</td><td>0.923</td><td>0.778</td><td>0.708</td><td>0.595</td><td>0.832</td><td>0.708</td><td>0.801</td><td>0.727</td><td>0.757</td></tr><tr><td>Hofmann et al. (2012)</td><td>0.924</td><td>0.722</td><td>0.683</td><td>0.575</td><td>0.860</td><td>0.756</td><td>0.784</td><td>0.816</td><td>0.753</td></tr><tr><td>Allebosch et al. (2015)*</td><td>0.917</td><td>0.713</td><td>0.578</td><td>0.578</td><td>0.820</td><td>0.838</td><td>0.809</td><td>0.741</td><td>0.741</td></tr><tr><td>Schick et al. (2012)</td><td>0.929</td><td>0.750</td><td>0.696</td><td>0.565</td><td>0.791</td><td>0.693</td><td>0.804</td><td>0.751</td><td>0.737</td></tr><tr><td>Candès et al. (2011)</td><td>0.911</td><td>0.722</td><td>0.694</td><td>0.537</td><td>0.789</td><td>0.719</td><td>0.701</td><td>0.776</td><td>0.729</td></tr><tr><td>Maddalena and Petrosino (2012)</td><td>0.933</td><td>0.705</td><td>0.669</td><td>0.592</td><td>0.779</td><td>0.692</td><td>0.802</td><td>0.732</td><td>0.728</td></tr><tr><td>Hernandez-Lopez and Rivera (2014)</td><td>0.921</td><td>0.487</td><td>0.750</td><td>0.741</td><td>0.809</td><td>0.662</td><td>0.777</td><td>0.761</td><td>0.728</td></tr><tr><td>Ramírez-Alonso and Chacón-Murguía (2016)*</td><td>0.918</td><td>0.721</td><td>0.671</td><td>0.510</td><td>0.795</td><td>0.703</td><td>0.708</td><td>0.801</td><td>0.720</td></tr><tr><td>Zhao et al. (2015)†</td><td>0.927</td><td>0.634</td><td>0.675</td><td>-</td><td>-</td><td>0.793</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

a Red bold entries indicate the best result in a given column, and blue italics the second best.

b We recalculated the overall result of Dey and Kundu (2015) based on the CDnet evaluation guidelines.

* Extracted from CDnet2014 results.

† Self-reported.

2015), prior image realignment (Gao et al., 2014), or supervised training (Sajid and Cheung, 2015) to address the shaking camera challenge. This means our dictionary update and feedback mechanisms are already quite sufficient for this task. Besides, compared to others, PAWCS excels in the “shadow” category, offering performance similar to the performance of multiple methods in the less-challenging “baseline” category. In fact, as stated by Wang et al. (2014a), while “hard” shadows are still a challenge for all methods, soft shadows are no longer problematic to modern solutions. In our case, this is due to our illumination update mechanisms as well as our choice of features for word description. We can also note that overall, our “online” method outperforms all recent robust PCA-based methods (Candès et al., 2011; Zhou et al., 2013; Gao et al., 2014) despite the fact that we “stream” the data in an online fashion (as opposed to offline batch-processing and optimization).

The advantages of our novel word consensus modeling strategy can be easily outlined by comparing our results to those of SUBSENSE (St-Charles et al., 2015a) since both methods use similar features and feedback mechanisms. While the results of PAWCS are slightly worse in the “baseline” category and equivalent in “camera jitter” and “shadow”, they are
<figure><img src="image_26.png" /><figcaption>Figure 5.4 Qualitative comparison of our segmentation results with the groundtruth on various sequences of CDnet2012. Gray regions in the groundtruth are not evaluated.</figcaption></figure>

clearly superior in “dynamic background” and “intermittent object motion”. This means our dictionaries can better reflect the multimodality of dynamic regions while staying sensitive to outliers, and that persistence is an ideal way to determine which words are more important for modeling based on past observations. The difference in the “baseline” category results can be explained by a slight increase in false negative classifications due to the global dictionary acting as a “fallback” model to prevent false positives elsewhere. Comparisons of some of our segmentation results with the groundtruth are shown in Figure 5.4.

Finally, we compare the results of various methods for the “intermittent object motion” category in Table 5.3. We can note that most recent methods perform poorly when static foreground object and background ghosts are involved. The top performers, FTSG (Wang et al., 2014b) and Shared-GMM (Chen et al., 2015), both rely on foreground modeling as well as region-level or object-level processing steps and heuristics to specifically tackle this category. On the other hand, our modeling approach only relies on the analysis of word persistence based on the principles detailed in Section 5.3. Thus, we keep to low-level mechanisms without involving object shape semantics. Our design is therefore in accordance with the first Wallflower principle (Toyama et al., 1999), but at a disadvantage when faced with these challenges.
<table><caption>Table 5.3 Average recall, precision and F-Measure scores on the intermittent object motion category of CDnet2012<sup>a</sup></caption><thead><tr><th>Method</th><th>Recall</th><th>Precision</th><th>F-Measure↓</th></tr></thead><tbody><tr><td>Chen et al. (2015)<sup>†*</sup></td><td>-</td><td>-</td><td><strong>0.798</strong></td></tr><tr><td>Wang et al. (2014b)<sup>*</sup></td><td><strong>0.835</strong></td><td><strong>0.933</strong></td><td><strong>0.789</strong></td></tr><tr><td><strong>PAWCS</strong> (proposed)</td><td>0.749</td><td><strong>0.839</strong></td><td>0.776</td></tr><tr><td>Hernandez-Lopez and Rivera (2014)</td><td><strong>0.808</strong></td><td>0.762</td><td>0.741</td></tr><tr><td>Wang and Dudek (2014)<sup>*</sup></td><td>0.762</td><td>0.753</td><td>0.721</td></tr><tr><td>Evangelio et al. (2014)</td><td>0.736</td><td>0.814</td><td>0.715</td></tr><tr><td>Sajid and Cheung (2015)<sup>*</sup></td><td>0.639</td><td>0.820</td><td>0.709</td></tr><tr><td>Stagliano et al. (2015)<sup>†</sup></td><td>0.684</td><td>0.709</td><td>0.686</td></tr><tr><td>Gao et al. (2014)<sup>†</sup></td><td>0.653</td><td>0.715</td><td>0.683</td></tr><tr><td>St-Charles et al. (2015a)<sup>*</sup></td><td>0.658</td><td>0.796</td><td>0.657</td></tr><tr><td>Maddalena and Petrosino (2012)</td><td>0.724</td><td>0.590</td><td>0.592</td></tr><tr><td>Allebosch et al. (2015)<sup>*</sup></td><td>0.742</td><td>0.563</td><td>0.578</td></tr><tr><td>Hofmann et al. (2012)</td><td>0.670</td><td>0.705</td><td>0.575</td></tr><tr><td>Sedky et al. (2014)</td><td>0.595</td><td>0.719</td><td>0.566</td></tr><tr><td>Haines and Xiang (2014)</td><td>0.676</td><td>0.653</td><td>0.542</td></tr></tbody></table>

<sup>a</sup> Red bold entries indicate the best result in a given column, and blue-italics the second best.

* Extracted from CDnet2014 results.

† Self-reported.

### 5.4.2 CDnet 2014

As stated earlier, the 2014 dataset is much more complex than the original version. Its categories include videos captured outside during snowstorms, extremely low framerate videos with rapid illumination variations and color profile changes, highway surveillance videos captured at night with intense glare effects from car headlights, videos captured by pan-tilt-zoom (PTZ) cameras being operated, and thermal imaging videos of long-range surveillance in high temperature environments. Just like for the CDnet2012 dataset, we first present in Table 5.4 PAWCS's performance on CDnet2014 using average Recall (Re), Precision (Pr), F-Measure (FM) and Matthew's Correlation Coefficient (MCC) scores. Note that since MCC is not computed by the online CDnet benchmark platform, and since half of the groundtruth is withheld, the MCC scores reported here are only representative of half of the dataset.

In comparison with the metrics shown for CDnet2012, it is quite clear that the 2014 dataset is more challenging. Only the “bad weather” category has F-Measure and MCC scores above 80%, and two categories have Precision or Recall scores below 50%. These Precision and
<table><caption>Table 5.4 Segmentation results of PAWCS on CDnet2014</caption><thead><tr><th>Category</th><th>Re</th><th>Pr</th><th>FM</th><th>MCC <sup>a</sup></th></tr></thead><tbody><tr><td>bad weather</td><td>0.718</td><td>0.947</td><td>0.815</td><td>0.812</td></tr><tr><td>low framerate</td><td>0.773</td><td>0.641</td><td>0.659</td><td>0.657</td></tr><tr><td>night videos</td><td>0.361</td><td>0.654</td><td>0.415</td><td>0.432</td></tr><tr><td>pan-tilt-zoom</td><td>0.698</td><td>0.473</td><td>0.462</td><td>0.491</td></tr><tr><td>turbulence</td><td>0.812</td><td>0.681</td><td>0.645</td><td>0.786</td></tr><tr><td>overall (2014 only)</td><td>0.672</td><td>0.679</td><td>0.600</td><td>0.636</td></tr><tr><td>overall (2012+2014)</td><td>0.772</td><td>0.786</td><td>0.740</td><td>0.756</td></tr></tbody></table>

Recall scores respectively indicate that more than half of foreground classifications were false, and more than half of all true foreground classifications were missed by our method. Surprisingly, PAWCS performed better in the “pan-tilt-zoom” category (in which the basic assumption of the static camera is violated) than in “night videos”. This can be explained by two factors: first, our global dictionary allows large uniform regions (which make up the bulk of all background areas in PTZ videos) to be properly recognized as background despite important camera motion. Second, due to the use of LBSP descriptors, and since our dictionaries are kept at minimal word counts, our method is sensitive to noise and color variations in low contrast background regions (such as the ones in “night videos”). On the other hand, the “turbulence” and “bad weather” categories also mostly contain low contrast videos with dynamic background regions, making it a combination of very challenging problems. Finally, the “low framerate” category shows decent results in all but one sequence (not shown here), filmed at one frame per six seconds. This problematic sequence presents very large color variations along with dynamic background elements, making it very hard to process.

We compare in Table 5.5 the scores obtained by 14 methods which were tested thus far on CDnet2014. We omit the 2014 dataset results of Chen et al. (2015) as their published results are significantly different from those reported online. Again, the performance of PAWCS is well above the average, ranking second in overall F-Measure (by a marginal difference) to the work of St-Charles et al. (2015a), and third in overall F-Measure for the 2014 categories only. On the other hand, on the official CDnet rankings available online based on all seven evaluation metrics (not shown here) list PAWCS as the best method by a good margin.

The F-Measure scores of PAWCS are lower than those of the state-of-the-art in the “bad weather”, “night videos” and “turbulence” categories. As mentioned before, this is due to the dynamic background/low contrast combination of challenges present in those sequences, to which our low-complexity modeling approach has difficulty adapting. Still, the overall

<footnote><sup>a</sup> Approximated based on available groundtruth.</footnote>
<table><caption>Table 5.5 Average per-category and overall scores on CDnet2014</caption><thead><tr><th rowspan="2">Method</th><th colspan="2">Bad Weath.</th><th colspan="2">Night Vid.</th><th colspan="2">PTZ</th><th colspan="3">Overall (2014)</th><th colspan="3">Overall (2012+2014)</th></tr><tr><th>FM</th><th>FM</th><th>FM</th><th>FM</th><th>FM</th><th>FM</th><th>Re</th><th>Pr</th><th>FM</th><th>Re</th><th>Pr</th><th>FM↓</th></tr></thead><tbody><tr><td>St-Charles et al. (2015a)</td><td><strong>0.862</strong></td><td>0.645</td><td><strong>0.560</strong></td><td>0.415</td><td>0.348</td><td><strong>0.779</strong></td><td><strong>0.794</strong></td><td>0.623</td><td><strong>0.639</strong></td><td><strong>0.812</strong></td><td>0.751</td><td><strong>0.741</strong></td></tr><tr><td><strong>PAWCS</strong> (proposed)</td><td>0.815</td><td><strong>0.659</strong></td><td>0.415</td><td>0.462</td><td>0.645</td><td></td><td>0.672</td><td><strong>0.679</strong></td><td>0.600</td><td>0.772</td><td><strong>0.786</strong></td><td><strong>0.740</strong></td></tr><tr><td>Wang et al. (2014b)</td><td><strong>0.823</strong></td><td>0.626</td><td>0.513</td><td>0.324</td><td>0.713</td><td></td><td>0.678</td><td>0.652</td><td>0.600</td><td>0.766</td><td>0.770</td><td>0.728</td></tr><tr><td>Sajid and Cheung (2015)</td><td>0.773</td><td>0.628</td><td>0.516</td><td><strong>0.512</strong></td><td>0.570</td><td></td><td>0.635</td><td>0.617</td><td>0.599</td><td>0.719</td><td>0.744</td><td>0.714</td></tr><tr><td>Allebosch et al. (2015)</td><td>0.779</td><td><strong>0.663</strong></td><td><strong>0.655</strong></td><td><strong>0.584</strong></td><td>0.671</td><td></td><td><strong>0.758</strong></td><td><strong>0.701</strong></td><td><strong>0.670</strong></td><td><strong>0.786</strong></td><td>0.722</td><td>0.709</td></tr><tr><td>Gregorio and Giordano (2014)</td><td>0.684</td><td>0.641</td><td>0.374</td><td>0.322</td><td>0.723</td><td></td><td>0.531</td><td>0.678</td><td>0.549</td><td>0.661</td><td><strong>0.773</strong></td><td>0.681</td></tr><tr><td>Sedky et al. (2014)</td><td>0.757</td><td>0.644</td><td>0.483</td><td>0.365</td><td>0.543</td><td></td><td>0.693</td><td>0.540</td><td>0.558</td><td>0.735</td><td>0.705</td><td>0.673</td></tr><tr><td>Wang and Dudek (2014)</td><td>0.767</td><td>0.469</td><td>0.380</td><td>0.135</td><td><strong>0.755</strong></td><td></td><td>0.599</td><td>0.584</td><td>0.501</td><td>0.704</td><td>0.716</td><td>0.658</td></tr><tr><td>Ramírez-Alonso and Chacón-Murguía (2016)</td><td>0.774</td><td>0.494</td><td>0.416</td><td>0.330</td><td>0.464</td><td></td><td>0.579</td><td>0.561</td><td>0.496</td><td>0.650</td><td>0.692</td><td>0.618</td></tr><tr><td>Maddalena and Petrosino (2012)</td><td>0.662</td><td>0.546</td><td>0.450</td><td>0.041</td><td>0.488</td><td></td><td>0.715</td><td>0.462</td><td>0.437</td><td>0.762</td><td>0.609</td><td>0.596</td></tr><tr><td>Zivkovic and van der Heijden (2006)</td><td>0.759</td><td>0.549</td><td>0.420</td><td>0.213</td><td>0.520</td><td></td><td>0.658</td><td>0.547</td><td>0.492</td><td>0.665</td><td>0.679</td><td>0.594</td></tr><tr><td>Varadarajan et al. (2013)</td><td>0.683</td><td>0.531</td><td>0.427</td><td>0.247</td><td>0.458</td><td></td><td>0.582</td><td>0.543</td><td>0.469</td><td>0.594</td><td>0.697</td><td>0.574</td></tr><tr><td>Stauffer and Grimson (1999)</td><td>0.738</td><td>0.537</td><td>0.410</td><td>0.152</td><td>0.466</td><td></td><td>0.653</td><td>0.484</td><td>0.461</td><td>0.685</td><td>0.603</td><td>0.571</td></tr><tr><td>Elgammal et al. (2000)</td><td>0.757</td><td>0.548</td><td>0.436</td><td>0.037</td><td>0.448</td><td></td><td>0.729</td><td>0.457</td><td>0.445</td><td>0.738</td><td>0.581</td><td>0.569</td></tr></tbody></table>

2012+2014 F-Measure score of PAWCS demonstrates that it is very flexible, and that it tackles most challenges without compromising too much of its performance elsewhere. In terms of Recall and Precision, we can observe balanced scores that are higher than those of most methods in both dataset versions, further demonstrating the overall flexibility of our approach. We present some qualitative comparisons between the groundtruth and our segmentation results in Figure 5.5.

### 5.4.3 Processing speed and memory footprint

Our C++ implementation processes the entire CDnet2012 dataset on a third generation, quad-core Intel i5 CPU (one sequence per core) at 22 frames per second, and it processes individual QVGA sequences on a single core at 15 frames per second. This is about 50% slower than St-Charles et al. (2015a) given equal model sizes for both methods, but still much faster than most video segmentation methods. Comparing this result to others is difficult due to the lack of open-source implementations available online; we offer ours for future reference.

Out of the entire processing load for a single frame, about 75% of it is for parsing dictionaries for matches and updating them, 15% is for feedback mechanisms, 5% is for frame-wide operations on global word persistence maps, and 5% is for output regularization via morphological operations and median blurring. The complexity of PAWCS is constant with respect to the number of pixels in the input frames. Given the ample opportunities for parallelization, real-time processing of very high resolution videos appears achievable. We recently implemented a similar non-parametric sample consensus method (St-Charles and Bilodeau, 2014) on GPU, and reached a speedup of 30x over its CPU implementation (i.e. it could process several

<footnote>a Red bold entries indicate the best result in a given column, and blue italics the second best.</footnote>
<figure><img src="image_27.png" /><figcaption>Figure 5.5 Qualitative comparison of our segmentation results with the groundtruth on various sequences of CDnet2014. Gray regions in the groundtruth are not evaluated. An obvious false positive blob is visible in the last row’s segmentation map; this is a temporary “ghost” artifact caused by a van that left the scene after being parked there.</figcaption></figure>

thousand frames per second). This speed was capped only by the memory bandwidth of the hardware we used.

As for the memory footprint of our proposed method, note that a background word requires three bytes of memory per channel to store color information and LBSP binary strings (based on the 5x5 pattern of Bilodeau et al., 2013), and three integers to store its persistence parameters (four bytes each, if $t_{max} > 2^{16}$ is expected). In a worse-case scenario where all pixel models require $N = 50$ background words (and those words are never discarded), and where the target video is RGB 1080p ($\approx 2.1$ megapixels), the memory requirement set by our pixel modeling approach would be slightly over 2 GB. Global words would also add less than 2 MB each to the total, given that their persistence maps are implemented using one byte per pixel. For embedded/mobile applications, given an average of $N = 5$ active words per pixel model and a QVGA resolution, the memory requirement of PAWCS would be less than 10 MB.
5.5 Conclusion

“Word consensus”, a new non-parametric pixel-level modeling approach, has been presented. It works by capturing local image samples and evaluating their recurrence among recent observations. We showed through our experiments with PAWCS that word consensus is performant when tackling segmentation challenges involving static foreground objects and multimodal background regions. Its ability to automatically deduce which model samples (or words) are the most important background components based on temporal persistence allows it to keep a low overall memory footprint. With the addition of closed-loop controllers and other feedback mechanisms, our complete method allows each targeted image pixel to behave differently in terms of classification behavior and model complexity. A frame-level word dictionary is also considered to increase spatial coherence between pixel models and prevent false classifications due to large-scale background change patterns.

Our results showed that our method is superior to most in scenarios with traditional and
modern background subtraction challenges. There is still room for improvement however;
using a more sophisticated output regularization step (e.g. Schick et al., 2012), or explicitly
modeling the foreground appearance of objects pixel-wise are good avenues for future work.
# CHAPITRE 6 ARTICLE 3: ONLINE MULTIMODAL VIDEO REGISTRATION BASED ON SHAPE MATCHING

St-Charles, P.-L., Bilodeau, G.-A., Bergevin, R.

IEEE Conference on Computer Vision and Pattern Recognition Workshops
Boston, MA, USA, June 7-12, 2015, pp. 26-34.

(© 2015 IEEE; Reprinted with permission.)

https://doi.org/10.1109/CVPRW.2015.7301293

## Abstract

The registration of video sequences captured using different types of sensors often relies on dense feature matching methods, which are very costly. In this paper, we study the problem of “almost planar” scene registration (i.e. where the planar ground assumption is almost respected) in multimodal imagery using target shape information. We introduce a new strategy for robustly aligning scene elements based on the random sampling of shape contour correspondences and on the continuous update of our transformation model’s parameters. We evaluate our solution on a public dataset and show its superiority by comparing it to a recently published method that targets the same problem. To make comparisons between such methods easier in the future, we provide our evaluation tools along with a full implementation of our solution online.

## 6.1 Introduction

Although automatic multimodal image and video registration has been intensively studied over the years (Zitová and Flusser, 2003; Oliveira and Tavares, 2014), most methods still rely on dense feature matching through area-based similarity measures computation (Pluim et al., 2000, 2003; Krotosky and Trivedi, 2007; Bilodeau et al., 2014). While this approach has the advantage of being able to register non-planar scenes, it is generally very computationally expensive, thus making it unsuitable for emerging mobile and distributed computer vision applications where information fusion might be required. Many multimodal surveillance systems capture images at medium/long distances from their targets, meaning that in those cases, planar models can be assumed without excessively compromising registration quality. In this context, lightweight approximate registration solutions can be adopted to replace their more complex counterparts. Instead of densely searching for local correspondences between images, lightweight solutions rely on sparse correspondences taken from common salient features, which are fitted to a parametric model in order to find a frame-wide rigid or projective transformation (homography).
The main problem behind this simplified approach is finding features that are shared between the studied image modalities and that are easy to automatically identify and match. As presented by Aguilera et al. (2012), traditional keypoint detectors and invariant descriptors are not well suited to multimodal imagery, and require important tuning to achieve decent results. Specialized detection and description methods have been proposed by Aguilera et al. (2012); Mouats and Aouf (2013); Ye and Shan (2014) to address this problem, but these methods do not work for image modalities where the relation between the appearance of objects is not easily defined. These methods are also inadequate when image resolution is too low or when there is a lack of similar textural content between the images. Therefore, more robust means of finding matches between images have to be considered.

In this paper, we propose an automatic video registration method that relies on correspondences found via shape-of-interest matching. Instead of independently analyzing each video frame to extract salient features or edge maps to use for correspondences, we rely on shape contours found using continuous foreground-background video segmentation. While this restricts our approach to applications where the targets of interest can be automatically segmented, it is not affected by the difference in pixel color characteristics of the studied image modalities. This means that our method can be used with any type of sensor, as the appearance of the targets does not matter (as long as they can be segmented).

Our first contribution is a strategy to preserve good shape contour matches throughout the analyzed sequences, which makes our transformation estimation approach robust to continuously imperfect segmentation and small static targets that do not contribute useful correspondences. Instead of temporally accumulating correspondences in a first-in, first-out buffer for RANSAC-based fitting (Fischler and Bolles, 1981), we use a buffer in which correspondences that are identified as persistent outliers, based on a voting scheme, are randomly replaced. Our second contribution is a method for smoothing transitions between transformations estimated at different times based on the approximate overlap of the analyzed foreground shapes. This prevents our solution from locking on to a global registration transformation that might not adequately reflect the nature of the studied scene (e.g. when the scene is not truly planar). Under the assumption that the foreground shapes are the real targets of interest in the scene, this smoothing approach allows improved overall registration through the continuous update of the transformation model's parameters.

We evaluate our solution by comparing it to a recently proposed method using a public dataset, and show that our overall strategy is superior. To make future comparisons on this dataset and with our method easier, we have made our source code public, and we provide
the video segmentation masks and the evaluation tools we used<fnref n="1" />.

## 6.2 Related Work

As described by (Krotosky and Trivedi, 2007), a planar model can be assumed for image or video registration in two cases: 1) when the sensors are nearly collocated and the alignment targets are far from them (infinite homographic registration), or 2) when all alignment targets lie on the same plane in the scene (planar ground registration). In both cases, the parallax effects caused by the camera baseline distance are assumed to be negligible. Registration can then be achieved by having a human expert select various keypoints in one image modality and search for their equivalent in the other, and by solving the parametric transformation model using these correspondences. Manual registration is however troublesome when large datasets containing many different sensor configurations have to be processed, as it is extremely time-consuming. Automatic video registration thus has to solve the multimodal keypoint detection and matching problem, and provide a robust way to identify the best homography within a temporal window.

Target silhouette information and edge maps have been used before to find correspondences between multimodal image sets (Coiras et al., 2000; Pistarelli et al., 2013; Mouats and Aouf, 2013; Tian et al., 2015). Coiras et al. (2000) estimated transformations in outdoor urban environments by extracting straight lines from edge maps and using them to find correspondences between sets of polygons. More recently, Pistarelli et al. (2013) proposed to use Hough space as the search domain to find multimodal correspondences between segments under similar conditions. Mouats and Aouf (2013) opted to use a keypoint detector based on phase congruency instead of edge points directly, but relied on local edge histograms to describe and match them between modalities. Tian et al. (2015) also used edge maps for thermal-visible face registration, but described point sets using shape context (Belongie et al., 2002). In their case, the infrared images were very contrasted, meaning that many strong edges were easily identifiable. Strategies based on silhouettes and edge maps are not always adequate, as contours representing region boundaries are not guaranteed to be shared between all modalities. For example, when using thermal-infrared sensors, objects with uniform temperatures might not display any edges while some are identifiable in other spectra.

The advantage of video registration over image registration is that methods can rely on target motion to find correspondences more easily. Shape contours obtained via temporal foreground-background segmentation (Han and Bhanu, 2007; Bilodeau et al., 2011a; Zhao

<footnote n="1">1. http://www.polymtl.ca/litiv/vid/index.php</footnote>
and Sen-ching, 2014; Sonn et al., 2013) or shape trajectories (Caspi et al., 2002; Bilodeau
et al., 2011b; Torabi et al., 2012) are viable strategies, as long as they can properly distinguish
targets from the background. Correspondences found between shape contours or trajectories
are used to find the transformation model parameters, but their quality highly depends
on the accuracy of the segmentation algorithm. In the work of Han and Bhanu (2007), a
hierarchical genetic algorithm is adopted to quickly find an optimal transformation while
avoiding local maxima. Zhao and Sen-ching (2014) used a simplified transformation model
using calibration priors based on a 1D-scan approach. The works of Sonn et al. (2013);
Caspi et al. (2002); Torabi et al. (2012) all rely on a similar strategy: correspondences from
a temporal window are added to a global potential match buffer (or “reservoir”), which is
then analyzed using a random sample consensus (RANSAC)-based method (Fischler and
Bolles, 1981) to find the parameters which best fit the transformation model. In the work of
Caspi et al. (2002), correspondences from all frames are used at once, meaning that it cannot
estimate the registration transformation in an online fashion. In the works of Sonn et al.
(2013); Torabi et al. (2012), a small first-in, first-out (FIFO) buffer is used to accumulate and
analyze a few seconds worth of correspondences. Our own strategy presented in Section 6.3.3
uses a similar RANSAC approach for online transformation estimation, but accumulates
contour matches using a random sampling and persistence voting approach (meaning that
these matches do not have a predefined lifetime in the buffer).

The shape contour description and matching strategy that most closely resembles ours is that
of Sonn et al. (2013): they used the Discrete Curve Evolution (DCE) algorithm originally
proposed by Latecki and Lakämper (2000) to prune foreground shapes into hexadecagons
with visually similar boundary parts. We believe that more accurate registration can be
achieved by describing and matching all shape contour points without pruning, leaving the
filtering responsibility to RANSAC. Therefore, for our own contour description and matching
needs, we use shape context (Belongie et al., 2002), as detailed in Section 6.3.2.

6.3 Proposed method

Our method can be split into several parts, as shown in Fig. 6.1. First, foreground-background
segmentation is used on each video frame to obtain shape contours from targets present in
the scene. Contour points are then described and matched using the iterative shape context
approach of Belongie et al. (2002). Following that, all matches are added to a correspondence
reservoir (i.e. a temporal buffer), which itself is analyzed by a RANSAC algorithm to identify
inliers and outliers and to estimate ideal transformation parameters. Finally, the identified
inliers are used for persistence voting in the reservoir, and the estimated model parameters
<figure><img src="image_28.png" /><figcaption>Figure 6.1 Overview of our proposed method’s principal processing stages.</figcaption></figure>

are used to update the reference (or “best-so-far”) registration homography. In the following
subsections, we detail each step of this process.

**6.3.1 Shape extraction**

The initial step in our method is identifying targets of interest in each video sequence using foreground-background segmentation. Since the dataset we use in Section 6.4 only contains sequences with static cameras, we opted for an approach based on change detection via background modeling (commonly referred to as “background subtraction”). The method we use is the one of St-Charles et al. (2015b): it builds a statistical model of the observed scene using color and binary features, and uses feedback mechanisms to dynamically adapt to changing conditions. Getting shape contours from the binary image masks provided by this method is trivial, and no pruning or extra post-processing is done to simplify these foreground shapes. We chose this segmentation method due to its ease-of-use and because it provides good segmentation results in image modalities inside and outside the visible spectrum.

**6.3.2 Contour points description and matching**

We address the shape contour matching problem as the task of establishing correspondences
in a bipartite graph where the disjoint sets are composed of noisy polygon vertices taken
from different image modalities. As mentioned earlier, we follow the approach introduced by
Belongie et al. (2002) to compare foreground object contours. Our ultimate goal is to find,
for each contour point in the first image modality, the contour point in the second modality
that offers the best match given their respective position within their original shapes.

This approach is straightforward: first, contour points are all assigned a shape context de-
scriptor which expresses the relative disposition of other contour points in the same modality using a uniform log-polar histogram (as shown in Fig. 6.2). These descriptors are then exhaustively compared using a $\chi^2$ test to determine similarity scores, and the correspondence problem is solved using the Hungarian method (Kuhn, 1955). These three steps are repeated multiple times for each frame in order to eliminate outlying matches from the contours, which are identified after solving the correspondence problem based on their low similarity scores. Between each iteration, a Thin Plate Spine model (TPS, Duchon, 1977) is used to determine the optimal elastic transformation that aligns the filtered contours, and new descriptors based on the transformed shapes are generated. Given a predetermined maximum number of iterations to run, this approach helps identify which correspondences will be used to find the frame-wide registration transformation detailed in Section 6.3.3. Note that the transformation estimated by the TPS method cannot be used for frame-wide image registration, as its elastically fitted solution might cause important distortions in regions far from the analyzed contour points. Therefore, it is only used as a temporary solution, and the contour point matches later added to the correspondence buffer contain their original coordinates.

Unlike the DCE approach of Sonn et al. (2013) that directly relies on Euclidean distances between multimodal contours, our approach is completely invariant to translations and scaling since all distances in shape context descriptors are relative and normalized. Furthermore, it is not restricted to a constant number of points per contour and it does not consider boundary convexity as a shape attribute, meaning it is more robust to noisy shapes caused by inadequate segmentation. The correspondence problem is also solved optimally, which is better than using the greedy matching algorithm of Sonn et al. (2013). Besides, note that due to the unknown relation between the analyzed image modalities, we do not consider local appearance when computing the similarity scores between shape contours.

### 6.3.3 Correspondence reservoir and voting

Using contour matches from a single frame pair for scene registration would likely result in noisy transformations that disregard large planar scene areas (which might be of interest to some applications). Therefore, the homography we are looking for has to be computed using correspondences taken from multiple frames to ensure accurate scene-wide registration. To address this problem, we use a temporal buffer (or reservoir) to accumulate enough correspondences so that a robust model fitting algorithm, RANSAC (Fischler and Bolles, 1981), can estimate a proper global homography.

In the work of Sonn et al. (2013), a first-in, first-out (FIFO) circular buffer strategy was adopted to keep 100 frames worth of contour point pairs. While easy to implement, the
<figure><img src="image_29.png" /><figcaption>Figure 6.2 Example of shape context description on a human shape contour point using 5 radius bins and 8 angle bins.</figcaption></figure>

primary disadvantage of this approach is that if the targets of interest remain static (or do not move much) during those 100 frames, or if the segmentation is continuously inaccurate, the buffer will be filled with correspondences that are not representative of the sought frame-wide transformation. To solve this problem, we use an identically sized buffer, but instead of following a FIFO rule, we replace the correspondences it contains using a random policy reminiscent of conservative sample consensus models.

Simply put, given a reservoir $R = \{p_1, p_2, \dots, p_N\}$ containing $N$ previously found point pairs, for each new point pair $p$ found by multimodal contour matching, we will randomly pick one of the reservoir pairs and replace it, but only if it is considered a “persistent outlier”. These persistent outliers can be identified based on the number of times they were omitted by the RANSAC algorithm during the estimation of the homography parameters for each new frame. To keep track of this, we define a voting map, noted $V = \{c_1, c_2, \dots, c_N\}$, which accumulates the inlier/outlier counts of each point pair (following RANSAC fitting) based on this logic:

$$c_i = \begin{cases} c_i + 1 & \text{if } p_i \text{ is an inlier according to RANSAC} \\ c_i - 1 & \text{otherwise} \end{cases}$$

For a new frame, all pairs $p_i$ which have negative $c_i$ values are considered persistent outliers. In practice, we determined that with this approach, the proportion of such outliers is always around 50%, which means that the reservoir never saturates and new correspondences can
always be swapped in. We also determined that due to the presence of our reservoir, even a small shape moving across a limited portion of the sensor's field of view can provide enough contour matches to estimate a good global homography; this is discussed further in Section 6.4.

### 6.3.4 Homography smoothing

Following the planar ground assumption to simplify video registration tasks might not always faithfully reflect the reality of the observed scenes. Therefore, the goal of our method is not to simply find a good frame-wide homography for the entire analyzed sequence, but to make sure that this transformation adequately aligns the targets of interest, even when non-planar transformations are involved. Basically, we are looking for a middle ground between estimating a timeless, global homography and estimating one that only focuses on aligning currently visible targets of interest without regard to previously found homographies or to the rest of the scene. To achieve this, while processing a pair of video sequences, we continuously update the homography which results in the best registration seen thus far (determined heuristically) using the model parameters found via RANSAC for each new frame. Under the assumption that segmented foreground shapes are truly objects of interest, this allows for slightly improved contour alignment in “almost planar” scenes while minimally affecting the registration quality of other frame regions. When the analyzed scene fully respects the planar assumption, the results provided by this middle ground approach are identical to those of the global, timeless approach.

First, we describe how the registration quality of a homography is appraised at run time. The only data which can be used to assess if a transformation is appropriate are the foreground shapes obtained by the segmentation step. Thus, the appraisal metric we use is the overlap error, defined for two foreground shapes $S_i$ and $S_j$ (both in the same coordinate space) as

$$E(S_i, S_j) = 1 - \frac{\#(S_i \cap S_j)}{\#(S_i \cup S_j)}, \qquad (6.1)$$

where $\#(S)$ returns the pixel count of foreground region $S$. Given perfectly segmented targets in a truly planar scene, a null overlap error would indicate an ideal registration transformation (both shapes are perfectly aligned).

As for the smoothing step itself, given a smoothing factor $\alpha$ (by default, $\alpha=2$), a newly estimated homography $H_{new}$, its calculated foreground shape overlap error $E_{new}$, a reference (or “best-so-far”) homography $H_{ref}$, its reference (or “best-so-far”) overlap error $E_{ref}$, and finally $H_{ref}$’s current overlap error on the latest foreground shapes $E_{curr}$, we follow the
1: **if** $E_{new} < E_{curr}$
2: **if** $E_{new} < E_{ref}$ $\lor$ $E_{new} < E_{curr} \cdot 2$
3: $\alpha \leftarrow 2$
4: **else**
5: $\alpha \leftarrow \alpha + 1$
6: **end if**
7: $\beta \leftarrow \frac{\alpha - 1}{\alpha}$
8: $E_{ref} \leftarrow E_{ref} \cdot \beta + E_{new} \cdot (1 - \beta)$
9: $H_{ref} \leftarrow H_{ref} \cdot \beta + H_{new} \cdot (1 - \beta)$
10: **end if**

<caption>Figure 6.3 Homography smoothing algorithm used for each frame.</caption>

algorithm presented in Fig. 6.3 to smooth the homography transition between two frames. In summary, if the new homography $H_{new}$ produces an overlap error $E_{new}$ smaller than what the reference homography $H_{ref}$ produced on the current foreground shapes ($E_{curr}$), then the reference needs to be updated. In that case, if the disparity between the two errors is large enough, or if the new error is simply smaller than the reference error ($E_{ref}$), the reference homography ($H_{ref}$) and error value ($E_{ref}$) will be replaced by the straight average between them and their newly found counterparts. Otherwise, they will be replaced by a weighted mean which depends on the value of the smoothing factor ($\alpha$).

The role of $\alpha$ is to control the weight given to the reference homography when it is combined with a new one. It is responsible for automatically balancing our method between directly using new homographies for each frame which focus on aligning matched contour points, and converging to a global homography which fits the entire scene more adequately. The latter case can be achieved when $\alpha \to \infty$, but in practice, this is unlikely to happen; as we will see in Section 6.4, our method never truly stops adapting to newly estimated homographies. Overall, as noted earlier, this smoothing strategy allows for better alignment of contours when considering “almost planar” scenes, and it helps quickly stabilize the registration when processing the first video frames with contour matches.

## 6.4 Evaluation

Evaluating how well a method behaves in terms of registration quality for “almost planar” scenes is not trivial. In the case of real planar scenes, the sought homography can be found manually, and registration quality can be evaluated by calculating the distance between points projected using this homography and the automatically estimated one. For scenes that do not fully respect the planar assumption, results have to be qualitatively evaluated, or a criterion
<figure><img src="image_30.png" /><figcaption>Figure 6.4 Example of the polygons used for quantitative evaluation formed with manually identified keypoints in the ninth sequence pair of the LITIV dataset.</figcaption></figure>

based on the degree of overlap of manually identified scene structures has to be used. Such a criterion is proposed by Torabi et al. (2012): for their own visible-infrared registration dataset, they manually selected points throughout the frames of their sequence pairs which were easily identifiable and matchable, and connected them to create polygons sets (an example of this operation is shown in Fig. 6.4). Once a polygon set is projected into the other's coordinate space, the overlap error can be used as the criterion to judge the image registration quality. By choosing points on scene elements that do not respect the planar assumption, one can highlight part of the non-rigid transformation that needs to be modeled by the automatic approach. Using these polygons instead of the segmented foreground shapes to calculate the overlap error eliminates the uncertainty caused by inaccurate video segmentation, and it allows a better coverage of the observed scene.

For our own tests, we also use the LITIV dataset of Torabi et al. (2012). However, since the polygons they manually drew for their quantitative evaluations could not be obtained, we had to draw our own. To make future quantitative comparisons between video registration methods easier, we have made these new polygon sets, the segmentation masks we obtained from the method of St-Charles et al. (2015b) as well as our evaluation tools available online, along with a C++ implementation of our method.

In total, nine visible-infrared sequence pairs of lengths varying between 200 and 1200 frames were analyzed. These were taken with different sensor baselines at various orientations from the ground plane. Homographies found by matching manually identified points are provided in the dataset, and are used in the following figures to illustrate ground truth global registration results. Sonn et al. (2013) provided us with an implementation of their own method, which we use as our basis for comparison. For fairness, both methods rely on the same segmentation results, both are evaluated using the overlap error defined in (6.1), and both use
<figure><img src="image_31.png" /></figure>

Figure 6.5 Registration results obtained at various moments of the first, second and fourth sequence pairs of the LITIV dataset using our proposed method. The left image in each pair shows the estimated frame-wide registration, and the right shows foreground shape registration at the same moment. The red dashed polygon shows the estimated transformation applied to the infrared image boundary, and the green one shows the ground truth transformation applied to this same boundary.

a single parameter set for all sequences.

We show in Fig. 6.5 how our method performs in the first, second and fourth sequence pairs of the studied dataset. We can see that for various sensor placements, an acceptable alignment of foreground shapes is found soon after a target first becomes visible (this happens at different moments in each sequence; our earliest results are shown in the left column). Over time, this alignment is refined to make the registration of other scene elements possible. For the first sequence pair (top row), even though the detected targets only travel in a small portion of the sensor's field of view, a very good transformation is found less than 30 frames after the first appearance of foreground shapes.

For quantitative evaluation, since online video registration takes time to stabilize, it makes little sense to compare average error measures that might be affected by important aberrations present early in the analyzed sequences. Previous works (Sonn et al., 2013; Torabi et al., 2012) addressed this issue by either considering only the minimum errors achieved for each sequence pair, or by arbitrarily picking time intervals where the method is considered “stable”, and computing average metrics from those. In our case, in order to present a global view of how our method adapts to each newly estimated homography, we present error-to-time curves for
<figure><img src="image_32.png" /></figure>

Figure 6.6 Polygon overlap errors obtained using our method (solid red), the method of Sonn et al. (2013) (dashed blue), and the ground truth homography (dotted gray) for the full lengths of all sequence pairs of the LITIV dataset.

our method and compare them to those of Sonn et al. (2013) in Figs. 6.6 and 6.7. The overlap errors of Fig. 6.6 are calculated using (6.1) with the ground truth polygonal shapes, and the Euclidean distance errors of Fig. 6.7 are calculated with the vertices of these polygons. In both cases, the transformation is applied on the infrared set, and the common coordinate space is in the visible image.

From the results shown in Fig. 6.6, we can note that our method reaches lower overlap errors faster than the method of Sonn et al. (2013), stabilizes at those levels more often, and manages to outperform the ground truth homography in five out of nine sequence pairs (LITIV-4 and LITIV-6 through LITIV-9). Outperforming the ground truth is possible because its homography reflects a global transformation only ideal for a planar scene, and the manually drawn polygons, just like the rest of the scene, do not fully respect the planar assumption. Since these polygons are partially based on points found on the targets of interest, transformations that focus on the alignment of these targets are more likely to get smaller overlap errors.

Besides, our method had no trouble estimating frame-wide registrations for LITIV-7 and LITIV-8, unlike the method of Sonn et al. (2013), which was unable to find adequate ho-
<table><caption>Table 6.1 Minimum overlap errors achieved for all video sequence pairs of the LITIV dataset (bold entries indicate the best result).</caption><thead><tr><td>Sequence</td><td>Proposed</td><td>Sonn et al. (2013)</td></tr></thead><tbody><tr><td>LITIV-1</td><td><b>0.187</b></td><td>0.217</td></tr><tr><td>LITIV-2</td><td><b>0.106</b></td><td>0.214</td></tr><tr><td>LITIV-3</td><td><b>0.108</b></td><td>0.258</td></tr><tr><td>LITIV-4</td><td><b>0.118</b></td><td>0.152</td></tr><tr><td>LITIV-5</td><td>0.172</td><td><b>0.167</b></td></tr><tr><td>LITIV-6</td><td><b>0.069</b></td><td>0.289</td></tr><tr><td>LITIV-7</td><td><b>0.091</b></td><td>0.379</td></tr><tr><td>LITIV-8</td><td><b>0.137</b></td><td>1.000</td></tr><tr><td>LITIV-9</td><td><b>0.095</b></td><td>0.117</td></tr></tbody></table>

homographies through the entire lengths of these sequences. In LITIV-7, we can see a strong temporary increase in overlap error near the end of the sequence: this is due to the matching of a single small shape with a strong shadow which produces outliers for a long period of time. This error quickly fades as better homographies are estimated after the target starts moving in the following frames.

As shown in Table 6.1, our method reached much lower minimum errors than the method of Sonn et al. (2013) in all but one sequence pair (LITIV-5), where the difference between the two is very small. In all cases except LITIV-4 and LITIV-7, an homography resulting in an overlap error of less than 50% was found after processing less than 30 frames (after the first appearance of foreground) containing at least one shape visible in both fields of view.

The curves illustrating polygon vertices registration errors shown in Fig. 6.7 generally depict the behavior observed in Fig. 6.6, but with a larger gap between our method and the method of Sonn et al. (2013) for LITIV-6 through LITIV-9. In three of those cases, the curves of Sonn et al. (2013) are mostly outside the 15 pixels error range of the graphs, but ours reach 2 or 3 pixels errors by the end of each sequence pair. We can also notice in the last graph of this new figure (LITIV-9) that our smoothing approach prevents our solution from locking onto a “decent” homography, and instead continuously refines one to achieve extremely small registration errors at the end of the sequence.

As for the computation time, when operating directly on the foreground shapes provided by the video segmentation algorithm, our proposed registration method processed video sequences at speeds varying between 15 and 150 frames per second, depending on the number of targets in the scene (we used C++ code on a laptop's 4th generation Intel i7 CPU at 2.8 GHz).
<figure><img src="image_33.png" /><figcaption>Figure 6.7 Polygon vertices Euclidean distance errors (in pixels) obtained using our method (solid red), the method of Sonn et al. (2013) (dashed blue), and the ground truth homography (dotted gray) for all sequences of the LITIV dataset. Note that the Y axis has been cropped similarly for all graphs.</figcaption></figure>

## 6.5 Conclusion

In this paper, we presented an online multimodal video registration method that relies on the matching of shape contours to estimate the parameters of a planar transformation model. We showed that randomly sampling a correspondence buffer and adding temporal smoothing between estimated homographies can quickly lead to stable results, and even allow “almost planar” scenes to be registered adequately. Our solution outperforms a recently published method. It manages to align manually annotated polygon sets based on scene structures better than the ground truth homography could in the majority of sequences we tested. Given adequate target segmentation, this approach could be used to register image sequences from cameras which are slowly moving, but still have overlapping fields of view. It could also be generalized to non-planar registration if transformations were continuously estimated for each foreground shape.
# CHAPITRE 7 ARTICLE 4: ONLINE MUTUAL FOREGROUND SEGMENTATION FOR MULTISPECTRAL STEREO VIDEOS

St-Charles, P.-L., Bilodeau, G.-A., Bergevin, R.

Article submitted to IJCV in February 2018.

(Submission ID: VISI-D-18-00108)

## Abstract

The segmentation of video sequences into foreground and background regions is a low-level process commonly used in video content analysis and smart surveillance applications. Using a multispectral camera setup can improve this process by providing more diverse data to help identify objects despite adverse imaging conditions. The registration of several data sources is however not trivial if the appearance of objects produced by each sensor differs substantially. This problem is further complicated when parallax effects cannot be ignored when using close-range stereo pairs. In this work, we present a new method to simultaneously tackle multispectral segmentation and stereo registration. Using an iterative procedure, we estimate the labeling result for one problem using the provisional result of the other. Our approach is based on the alternating minimization of two energy functions that are linked through the use of dynamic priors. We rely on the integration of shape and appearance cues to find proper multispectral correspondences, and to properly segment objects in low contrast regions. We also formulate our model as a frame processing pipeline using higher order terms to improve the temporal coherence of our results. Our method is evaluated under different configurations on multiple multispectral datasets, and our implementation is available online.

## 7.1 Introduction

The detection and segmentation of objects of interest based on motion analysis in video sequences is a fundamental early vision task. In the context of video surveillance and intelligent environments, objects of interest (or “foreground” objects) are disruptors that temporarily break the natural state of the observed scene (the “background”). Several types of approaches exist to classify image regions as being “of interest” based on this criteria (see Bouwmans, 2014; Perazzi et al., 2016). While these all have different qualities, they suffer from the same fundamental drawback: if the contrast between an observed object and the background becomes too low, our ability to detect and segment it automatically deteriorates. This problem is not specific to the visible light spectrum, as this camouflaging can occur with any imaging
modality. However, interestingly, the phenomena describing the appearance of an object and
the conditions under which it becomes harder to identify are rarely shared across several
imaging modalities. This is especially true when considering for example the visible and
Long-Wavelength Infrared (LWIR) spectra, as the correlation between the temperature of
an object and its visible appearance is very weak (see Bilodeau et al., 2011b). We show an
example of this in Figure 7.1. In fact, many surveillance systems rely on the complementarity
of these two imaging modalities to detect abnormal events: the visible spectrum can easily
identify large objects near ambient temperatures (e.g. vehicles), and the LWIR spectrum can
easily identify objects that exhibit abnormal temperatures (e.g. animals, engine parts).

Integrating data captured from different spectral bands to attain benefits in recognition
tasks is however not trivial. If the optical axes of the sensors are not already aligned using a
beam splitter, a registration method has to be used to bring data points back into a common
coordinate system. The image registration problem has been thoroughly studied for identical
sensor pairs, but multispectral registration is fundamentally more challenging (c.f. Zitová and
Flusser, 2003). Since the appearance of objects cannot be directly relied upon to find local
correspondences, higher level image features such as edges have to be used instead. These
are typically harder to compute, and often result in a loss of registration accuracy at the
pixel level when parallax effects are not negligible.

Past research has focused mostly on the problems of binary (or foreground-background)
segmentation and multispectral image fusion/registration as separate issues. Yet, holistic
approaches such as the ones of Torabi et al. (2012); Zhao and Sen-ching (2014) can outperform
combinations of distinct methods on identical tasks. These holistic approaches first optimize
registration using foreground object contours or trajectories as high-level features, and then
use integrated image data to improve their segmentation. Solving both problems at once
would be more beneficial, but this goal implies a “chicken-and-egg” dilemma: the result
of one task is needed to obtain the other. An ideal holistic method should thus adopt an
iterative optimization approach to resolve this issue. In the case of video sequences, proposed
solutions should also consider the temporal redundancy of data to improve their performance.
Finally, in the context of surveillance applications, the entire process should function without
any human supervision, and allow frame pairs to be processed one at a time.

In this paper, we propose a holistic method to address both segmentation and registration
problems by inferring their solutions alternately using move-making algorithms on a set of
conditional random fields. We use self-similarity descriptors and shape cues to find proper
pixel-level matches across imaging modalities in non-planar scenes, and integrate image data
to improve foreground-background partitioning. This integration is achieved by iteratively
refining local color models and shape contour positions while continuously realigning data sources. Our two goals are formulated as distinct energy minimization problems, and we use provisional inference results as dynamic priors to converge to a global solution. We also rely on dynamic temporal connections updated via motion cues to improve segmentation coherence over long image sequences.

Our principled bottom-up approach requires no human intervention, and relies on no prior knowledge of the foreground objects' nature. Our models are formulated so that imaging modalities can be combined without assumptions about their specific characteristics, as image regions containing discriminative data are automatically identified. This power of discrimination is exploited to scale the importance of each imaging modality when registering and integrating pixel-level data. It is also used to speed up shape contour evolution in low contrast regions by reducing penalties for label discontinuities when the other view possesses strong intensity gradients in its corresponding regions. Besides, we tackle foreground-background segmentation in the general case of video surveillance, meaning we assume the scene might contain multiple foreground objects at different depths and scales, and that they might not always be moving. This differs significantly from traditional cosegmentation methods, as we make no assumption regarding the distribution of foreground and background regions in the observed scene.

Through our experiments, we show that our primary goal, mutual foreground segmentation, can be achieved efficiently despite low contrast and other adverse conditions in both visible and LWIR images. Performance evaluations show that our approach outperforms both supervised and unsupervised monocular segmentation methods in terms of $F_1$ score on the VAP dataset of Palmero et al. (2016). Compared to the recent video segmentation method of St-Charles et al. (2016a), our method improves its average $F_1$ score by 13%, from 0.766 to 0.866. To help future benchmarking on this task, we offer a new multispectral video dataset for the simultaneous evaluation of registration and segmentation performance<fnref n="1" />. Finally, we also offer our source code and testing framework online<fnref n="2" />.

Note that our method was previously introduced (St-Charles et al., 2017). Here, beyond presenting an extended description of our approach, we introduce a spatiotemporal term to our model and study its effect on segmentation accuracy, we discuss new experiments on two pre-existing datasets, and we present new evaluation results on a novel non-planar RGB-LWIR video dataset.

The paper is organized as follows. In Section 7.2, we present previous works related to our

<footnote n="1">1. http://www.polymtl.ca/litiv/vid/index.php</footnote>

<footnote n="2">2. https://github.com/plstcharles/litiv</footnote>
<figure><img src="image_34.png" /><figcaption>Figure 7.1 Examples of mutual foreground segmentation in low contrast conditions for RGB-LWIR image pairs. On the left, the person is only partly perceptible in the LWIR spectrum due to a winter coat, but is clearly perceptible in the visible spectrum. The opposite is true on the right, where legs are hard to perceive in the visible spectrum, but easy to perceive in the LWIR spectrum.</figcaption></figure>

multispectral mutual segmentation problem, and highlight major differences. In Section 7.3, we describe our dual modeling approach, inference strategies, and implementation details. In Section 7.4, we present parameter and configuration studies, and evaluation results on three publicly available datasets. Lastly, we conclude with some remarks in Section 7.5.

## 7.2 Previous Work

The problem of foreground-background segmentation in images is difficult to tackle without some assumptions or constraints. Monocular segmentation solutions typically rely on visual saliency hypotheses (e.g. single foreground object roughly focused) or human supervision to obtain good results (Arbelaez et al., 2011; Rother et al., 2004). The same problem in the temporal domain (i.e. on image sequences) is easier to address due to the additional assumptions that can be made regarding object or scene motion. Multiple families of methods exist in video segmentation; the main ones are listed here. Background subtraction methods work by building a model representing the background under the assumption that the camera is static. These methods then perform one-class pixel classification to label all outliers as foreground without supervision (Bouwmans, 2014). These methods are favored in cases where foreground objects can temporarily become immobile, as they will retain their labeling for some time. Other video object segmentation approaches instead extend the concept of visual saliency into the temporal domain using highly connected graph structures (Perazzi et al.,
2016). These approaches can usually be applied to sequences with changing viewpoints, but are computationally more demanding. Finally, motion clustering methods exist that rely on optical flow or trajectory points partitioning to identify image regions that behave differently from their surroundings (Tron and Vidal, 2007). The strong link between motion partitioning and video object segmentation has also become a focus in recent years (Jain et al., 2017; Cheng et al., 2017). Also, in semi-supervised settings, approaches based on end-to-end neural networks have also become increasingly popular for single object video segmentation (Cheng et al., 2017; Caelles et al., 2017).

Foreground-background segmentation can become easier if multiple images of the object(s) of interest are available. Two families of methods have been developed for this circumstance: cosegmentation methods and mutual segmentation methods. Cosegmentation methods typically rely on visual saliency assumptions (e.g. shared foreground appearance and low background correlation across different views), and assume a single object is targeted and shared throughout all views (Rother et al., 2006; Zhu et al., 2016). Interestingly, cosegmentation methods can also work with different object instances from the same object category (Vicente et al., 2011). On the other hand, mutual segmentation methods typically assume that the same object instance is observed from multiple viewpoints, and optimize the geometric consistency of the extracted foreground region (Djelouah et al., 2015; Jeong et al., 2017; Riklin-Raviv et al., 2008). Our work falls into this second family of methods, as we assume the use of a synchronized stereo pair for data capture.

Previous mutual segmentation methods have typically focused on single-spectrum imaging (Riklin-Raviv et al., 2008; Ju et al., 2015; Bleyer et al., 2011), or have used depth sensors to solve the registration problem and to provide a range-based solution for foreground object detection (Jeong et al., 2017; Djelouah et al., 2015; Zhang et al., 2016). Of these, our proposed method is closest to the work of Riklin-Raviv et al. (2008), who termed the idea of “mutual segmentation” for objects in visible image pairs. Their approach addresses the uncertainty of object boundary localization under occlusions and noise by iteratively optimizing active contours without supervision. Their use of a biased shape term however entails that a free parameter directly controls the elimination of ambiguous shape segments in the image pair. In our work, we avoid this parameterization issue by relying on local saliency and self-refining color models to automatically integrate multiple view data. Our object contours then expand and contract until they naturally converge. Besides, the method of Riklin-Raviv et al. (2008) considers that all images are related only by planar projective homographies, and thus it cannot handle parallax issues in 3D scenes. This latter problem was addressed by Ju et al. (2015), who also proposed a contour-based modeling approach for mutual foreground segmentation in stereo pairs. This more recent approach however relies on the assumption
that near-perfect foreground contours obtained via human supervision are available in at least one of the views. Lastly, the work of Bleyer et al. (2011) is also somewhat related to ours: they tackle disparity (or parallax) estimation for calibrated stereo pairs using a piecewise planar model based on object segmentation. However, their main goal is scene-wide data registration, which is very computationally demanding. According to Tippetts et al. (2016), processing an image pair took the method about 20 minutes. In our case, we only focus on the registration and segmentation of foreground objects classified as such in a video surveillance mindset. This makes our proposed approach much more lightweight and applicable to real data streams.

The use of multispectral data (other than RGBD) has been mostly neglected in the context of mutual segmentation or cosegmentation due to the registration problem. As stated before, this difficulty is due to the (typically) low correlation between the appearances of objects in different spectral bands (see Zitová and Flusser, 2003). Beam splitters can be used to avoid the registration problem altogether (Bienkowski et al., 2012; Hwang et al., 2015). These setups are however very delicate, and they induce color distortions. Moreover, the elimination of parallax also prevents the recovery of depth information from the scene.

In practice, if the chosen spectral bands are not too distant in terms of their imaging characteristics (e.g. visible light and near-infrared), modern image descriptors and similarity measures can be used to find local correspondences with varying degrees of success (see Pinggera et al., 2012). These “close” spectrum pairs are however less interesting to integrate in machine vision systems due to their resemblance. On the other hand, traditional appearance-based matching approaches suffer when distant spectrum pairs such as visible and Long-Wavelength Infrared (LWIR) are selected (Bilodeau et al., 2014). Multispectral registration thus has to rely on higher level features that encapsulate raw object appearance in order to find proper local correspondences. In the recent literature, some have relied on edge matching in local neighborhoods (Coiras et al., 2000; Mouats and Aouf, 2013) or in Hough space (Pistarelli et al., 2013) to resolve this problem. Edge-based approaches are however more suited to man-made environments, and underperform in more general settings (e.g. open terrain) where large intensity gradients are rarer or more weakly correlated between imaging modalities.

Other works have instead addressed the registration problem in the temporal domain by adopting motion-based cues (Torabi et al., 2012; Zhao and Sen-ching, 2014; Nguyen et al., 2016), which is more similar to our approach. In the work of Torabi et al. (2012), the trajectories of foreground objects are used for high-level registration based on the idea that position and motion are fully independent of appearance. In the works of Zhao and Sen-ching
<figure><img src="image_35.png" /><figcaption>Figure 7.2 Flowchart of the proposed method. A monocular video segmentation method is first used to initialize segmentation masks for both cameras individually. Then, the energies of the stereo and segmentation models (described in Sections 7.3.1 and 7.3.2, respectively) are alternately minimized until a proper global solution is reached. The output of our method then consists of the refined segmentation masks of the input frames, and of the reciprocal disparity labelings computed for both cameras.</figcaption></figure>

(2014) and Nguyen et al. (2016), foreground shapes obtained via background subtraction are used for contour matching. This latter strategy has been shown to be more pixel-accurate for the registration of foreground objects, but it still depends strongly on the performance of the segmentation method used. In our proposed method, we address this problem by combining contour-based registration and segmentation into a global optimization framework.

Finally, as for the combination of multispectral registration and segmentation, we can highlight the existence of a few papers. Torabi et al. (2012) propose a solution based on object-wise planar registration, and improve segmentation masks obtained via background subtraction by combining multispectral data using a sum-rule approach. Zhao and Sen-ching (2014) also rely on object-wise planar registration, and use multiple object trackers to improve the results of parallel segmentors a posteriori. In this case, the methods are run in cascade to resolve the “chicken-and-egg” optimization dilemma stated earlier. The strategies of Torabi et al. (2012) and Zhao and Sen-ching (2014) do not handle occlusions well due to their high level registration approach, and only provide a single-pass improvement to the segmentation results of a given frame pair. Palmero et al. (2016) introduced a human body segmentation method for trimodal (RGBD-LWIR) image sequences based on feature fusion using a random forest classifier. They also avoid pixel-level registration by predefining a set of homographies to use at runtime based on detected foreground object depth. Davis and Sharma (2007)
proposed a dual background subtraction model and contour extraction technique to improve RGB-LWIR foreground fusion based on local visual saliency evaluation. Similarly, Li et al. (2017) proposed a background subtraction method based on the low-rank decomposition of integrated RGB-LWIR pairs to improve foreground segmentation in a global framework. The main shortcoming of these latter two works is that they only handle planar scenes (i.e. scenes where parallax issues are negligible) using a single predefined homography. To the best of our knowledge, no method has previously been proposed to tackle multispectral non-planar registration and mutual foreground segmentation simultaneously.

## 7.3 Proposed Approach

Our approach can be described based on its two main components: the stereo matching model for disparity (or parallax) estimation on epipolar lines, described in Section 7.3.1, and the shape matching model for binary image segmentation, described in Section 7.3.2. These two models are conditional random fields formulated as discrete energy functions that tackle the multispectral registration and segmentation problems in an integrated fashion. Our energy functions are minimized alternately using move-making algorithms, as described in Section 7.3.3. The flowchart in Figure 7.2 illustrates our approach.

We begin with an introduction of the general terms and notation used in this section. Given a set of rectified images $\mathcal{I} = \{I_k\}$ (with $k = \{0, 1\}$ in the case of a stereo pair), the disparity label space $\mathcal{L}_D = \{0, \dots, d_{\max}\}$, and the background-foreground label space $\mathcal{L}_S = \{0, 1\}$, our goal is to find the optimal pixel-wise disparity and segmentation labelings $\mathcal{D} = \{\mathcal{D}_k\}$ and $\mathcal{S} = \{\mathcal{S}_k\}$ such that:

$$ \mathcal{D}_k = \underset{D_k}{\operatorname{argmin}} E_k^{\text{stereo}}(D_k), \qquad (7.1) $$

$$ \mathcal{S}_k = \underset{S_k}{\operatorname{argmin}} E_k^{\text{segm}}(S_k), \qquad (7.2) $$

where $D_k = \{d_p : p \in I_k, d_p \in \mathcal{L}_D\}$ is a disparity labeling, $S_k = \{s_p : p \in I_k, s_p \in \mathcal{L}_S\}$ is a segmentation labeling (or mask), and where the energy cost functions $E_k^{\text{stereo}}$ and $E_k^{\text{segm}}$ are described in Sections 7.3.1 and 7.3.2, respectively. For now, note that these functions are linked through their estimation results, $\mathcal{D}_k$ and $\mathcal{S}_k$, which are used as dynamic priors throughout the minimization. In other words, disparity labels $d_p$ for each pixel $p$ in $I_k$ are used in $E_k^{\text{segm}}$ for appearance data integration, and segmentation labels $s_p$ are used in $E_k^{\text{stereo}}$ to improve stereo matching. Lastly, note that we sometimes omit the $k$ subscript in the following subsections to simplify the notation, as most equations only deal with one image of the stereo pair at a time.
### 7.3.1 Stereo Registration Model

We tackle the multispectral stereo registration problem for non-planar scenes using a sliding window strategy for pixel matching. This search for correspondences is limited to an horizontal axis on the image plane due to epipolar geometry constraints. These constraints restrict the disparity (or parallax) between the 2D projections of an observed 3D object point to one dimension (see Hartley and Zisserman, 2003). In short, given the intrinsic and extrinsic parameters of the stereo pair obtained via calibration, we can rectify the input images. This forces the corresponding projection of a 2D point in one view to be located somewhere on the same horizontal line in the other view. While calibration does require human intervention, it is a one-time effort generally accepted in an unsupervised system. It could also be replaced by an automatic approach (e.g. Nguyen et al., 2016).

For a pixel-wise disparity label map $D$, we define its energy (or cost) to be minimized as

$$E^{\text{stereo}}(D) = E^{\text{appearance}}(D) + E^{\text{shape}}(D) + E^{\text{uniqueness}}(D) + E^{\text{smooth1}}(D) \quad (7.3)$$

Each term in this cost function is crafted to promote a desired property of the output disparity labeling, and is described in detail in the following paragraphs. The first three terms are unary costs summed over all pixels of the image. The appearance and shape terms evaluate the local affinity between a pixel $p$ and its corresponding pixel shifted by $d_p$ in the other view. The uniqueness term penalizes multiple matches with $p$ in the other view. The last term is a sum of pairwise smoothness costs used to penalize irregular disparities in uniform image regions. Note that in order to maximize processing speed for image pair sequences, we keep our stereo model simple. Our results would undoubtedly improve with second-order terms such as those of Woodford et al. (2009) or Kohli et al. (2009), but at an important increase in computational complexity. Moreover, since we only focus on the registration of foreground objects, higher-order surface smoothness priors are not as important here.

**Appearance and shape terms.** These two terms convey the cost of matching an image patch centered on a pixel $p \in I$ to another one in the second view which is offset according to its disparity label $d_p$. The terms are both defined as

$$E^{\{\text{appearance, shape}\}}(D) = \sum_{p \in I} \mathcal{A}(p, r(p, d_p)) \cdot W(p), \quad (7.4)$$

where $r(p, d_p)$ returns the pixel location in the other view obtained by shifting $p$ by $d_p$ on its epipolar line, $\mathcal{A}(p, q)$ encodes the affinity cost for matching descriptor patches centered at $p$
and $q$ in each image, and $W(p)$ encodes the saliency coefficient for pixel $p$ (detailed further down). For the appearance term, the affinity cost map $\mathcal{A}$ is obtained by densely computing local image descriptors over $I_0$ and $I_1$, and by matching them using L2 distance in 15x15 patches to dampen noise. As stated in Section 7.2, classic appearance-based descriptors are not ideal for wide spectrum pairs such as RGB-LWIR. To address this issue, we used DASC descriptors (Kim et al., 2015), which are based on local self-similarity measures. We also tested the LSS descriptor (Shechtman and Irani, 2007) during our preliminary experiments, and found a slight decrease in terms of overall registration performance. For the shape term, we densely compute Shape Context descriptors (Belongie et al., 2002) over $S_0$ and $S_1$, which are the provisional segmentation masks. We then match these descriptors using the same approach as for the appearance term to obtain the shape affinity cost map $\mathcal{A}$. Our hypothesis here is that the combination of these two types of descriptors can provide better matching results than either one alone. However, remember that multispectral matches are often unreliable due to non-discriminative descriptors in uniform image regions or in regions with very low multispectral correlation. To avoid increasing pixel matching penalties in such cases, we multiply the affinity cost by a local saliency coefficient. In both the appearance and shape terms, this local saliency coefficient for a given pixel $p$ is defined as

$$W(p) = \max \left\{ \mathcal{H}\left(\left[\mathcal{A}(p, r(p, d)) \ \forall d \in \mathcal{L}_D\right]\right), \mathcal{H}(K(p)) \right\}, \quad (7.5)$$

where $K(p)$ returns the matrix of local descriptors in the patch centered on pixel $p$, and $\mathcal{H}(\cdot)$ computes the sparseness metric of Hoyer (2004) over a vector or matrix. This metric returns a value $\in [0, 1]$, meaning $W(p)$ is also in that interval. In simple terms, if all affinity values are uniform (i.e. all disparity offsets have the same cost), and if the local patch's descriptor bins are all uniform, then $W(p)$ will take a low value. In turn, this will lower the cost for $d_p$ evaluated through the affinity map $\mathcal{A}$, and make local labeling depend more on neighboring decisions through the smoothness term. A simplified case of this is illustrated in Figure 7.3. Besides, note that in $E^{\text{shape}}$, we nullify the saliency outside foreground regions to avoid influencing background disparity estimation around object contours. We can assume that disparity estimation for background regions will be less accurate due to this missing term contribution, but since we focus on the registration of foreground shapes, this is inconsequential. We study the individual contributions of the appearance and shape terms to the overall performance of our approach in Section 7.4.

**Uniqueness term.** This unary term is used to penalize having multiple epipolar correspondences tied to the same pixel. This helps spread and equalize disparity labels in occluded and weakly discriminative image regions. Our formulation for this term is different from
<figure><img src="image_36.png" /><figcaption>Figure 7.3 Simplified case of saliency evaluation during a correspondence search on an epipolar line. On the left, for the “A” pair, low contrast in one image leads to roughly uniform affinity scores and matching costs, which translate into a low local saliency value. On the right, for the “B” pair, good contrast leads to varied affinity scores and matching costs, and a high local saliency value.</figcaption></figure>

the classic mutual exclusion constraint proposed by Kolmogorov and Zabih (2001), which assigns an infinite cost to all extra correspondences found for a pixel *p*. Instead, we rely on a soft constraint that permits many-to-one correspondences with gradually increasing costs. This strategy allows our stereo model to temporarily stack extra correspondences during label swaps if the extra cost is worth absorbing. This translates into faster and larger label moves in the early steps of our inference approach, and redistribution of extra correspondence costs over future iterations. Since our method only requires a rough registration of foreground shapes to start properly segmenting them, this allows us to bootstrap the segmentation model without spending too much time on disparity estimation. We define the uniqueness cost for
a pixel $p$ as

$$ \mathcal{U}(p) = \begin{cases} \sum_{n=1}^{N(p)-1} \frac{w \cdot n}{w+n-1} & \text{if } N(p) > 1 \\ 0 & \text{otherwise} \end{cases}, \qquad (7.6) $$

where $N(p)$ returns $p$'s current correspondence count with pixels in the other view, and $w$ is a small weight (we used $w=3$ in our tests). For this to work, we need to keep track of pixel correspondence counts ($N(p)$) as latent variables in our model. However, since we use a move-making strategy for model inference, many correspondences might be removed in a single iteration. This makes the total cost of a move over several pixels hard to predict with (7.6) due to its nonlinearity. To solve this problem, we define our uniqueness term as

$$ E^{\text{uniqu.}}(D) = \lambda_u \cdot \sum_{p \in I} \left( \frac{-\mathcal{U}(r(p, d'_p))}{N(r(p, d'_p))} + \frac{w \cdot N(r(p, d_p))}{w+N(r(p, d_p))-1} \right), \qquad (7.7) $$

where $d'_p$ is the previous disparity label of $p$, and $\lambda_u$ is a fixed scaling factor. Note that we specify the values used for important factors such as $\lambda_u$ in Section 7.3.3, and test their contribution to overall performance in Section 7.4.4. The formulation behind (7.7) provides a worst-case energy variation between two labeling states, and guarantees that estimated pixel move costs provided to the move-making algorithm will always be similar but greater than their real evaluated costs once the full move is complete. This is required so that computed label updates always minimize (7.3), which lets us avoid having to fall back to an older solution if the energy increases.

**Smoothness term.** Lastly, we rely on a classic truncated pairwise (first-order) smoothness term to enforce the spatial coherence of our model. This term penalizes cases where neighboring pixels have irregular disparity labels despite being located in a roughly uniform image region, as described by a weak local gradient magnitude. If the gradient detected between the two pixels is instead strong, the penalty is lowered, as object edges more likely correspond with breaks in labeling. We define this term as

$$ E^{\text{smooth1}}(D) = \lambda_{s1} \cdot \sum_{\langle p, q \rangle \in \mathcal{N}} \min \left( |d_p - d_q|, 10 \right)^2 \cdot G_I^{s}(p, q), \qquad (7.8) $$

with

$$ G_I^s(p, q) = \max \left( \exp \left( 1 - \frac{|\nabla I(p, q)|}{g} \right) - 0.5, 0 \right), \qquad (7.9) $$

where $\lambda_{s1}$ is a fixed scaling factor, $\mathcal{N}$ is the set of first order cliques in the graph model, $\nabla I(p,q)$ returns the normalized local image gradient magnitude between pixels $p$ and $q$ of image $I$, and $g$ is a constant value defining the expected object contour gradient magnitude
(also specified in Section 7.3.3). The truncation value (10 is used) allows large discontinuities to occur by capping the maximum smoothness penalty.

### 7.3.2 Segmentation Model

Our segmentation model's role is to integrate multispectral image data so that foreground objects can be properly segmented in both views, even in low contrast imaging conditions. Our model also needs to be lightweight enough so that cost updates and inference is fast, as shape priors are continuously modified. Since our goal is to build an unsupervised approach, we initialize the priors described below using the approximate masks provided by a monocular segmentation method (i.e. the one of St-Charles et al., 2016a). This method was chosen because it can detect multiple foreground objects at once, and it can keep segmenting them at least partially if they become immobile. In Section 7.4, we show that our method works even when an initialization mask is provided for only one of the two views.

We describe the energy cost of a pixel-wise segmentation proposal $S$ as

$$E^{\text{segm}}(S) = E^{\text{color}}(S) + E^{\text{contour}}(S) + E^{\text{smooth2}}(S) + E^{\text{temp}}(S) \quad (7.10)$$

Once again, the terms of this cost function are defined so that various characteristics expected of the segmentation masks can be promoted. The first two terms are unary costs summed over all pixels, and their role is to influence local segmentation decisions based on image data. The color data term maximizes the separation between the color distributions of foreground and background pixels, while the contour data term penalizes shape mismatches between the views based on distance transforms. The third term is a pairwise smoothness sum similar to (7.8), and is used to penalize labeling irregularities in uniform image regions. Lastly, the temporal term is a sum of higher order clique costs used to enforce temporal labeling coherence. These terms are all described in the following paragraphs. Note that due to the presence of the higher order temporal term in (7.10), our model is built as a multi-layer lattice, as illustrated in Figure 7.4. The top layer's nodes correspond to the pixels of the latest frame of the video sequence, and lower layers' nodes correspond to the pixels of older frames. This effectively creates a pipeline where segmentation masks can be improved over time based on new image data. We discuss the improvement achieved using this approach with various pipeline depths in Section 7.4.

**Color term.** We define the cost for this unary term using a color mixture model for each modality of the stereo pair. We employ the classic approach of Rother et al. (2004) which
relies on Gaussian mixture models to represent foreground and background regions. These models can provide us with the probability that a pixel belongs to the background or foreground based on its color value. In our implementation, we use six mixture components, and use our initial and updated segmentation masks to refine our models after each iteration, in each frame. We define the color cost of all pixels as

$$E^{\text{color}}(S) = \sum_{p \in I} \begin{cases} -\log \left( h(I_p; \beta_1, \mu_1, \Sigma_1) \right) & \text{if } s_p = 1 \\ -\log \left( h(I_p; \beta_0, \mu_0, \Sigma_0) \right) & \text{otherwise} \end{cases}, \quad (7.11)$$

where $h(x; \beta, \mu, \Sigma)$ returns the relative likelihood that the pixel color $x$ fits a Gaussian mixture model with component weights $\beta$, means $\mu$ and covariance matrices $\Sigma$. Note that the parameter subscripts in (7.11) indicate that either the foreground or background model is used based on $s_p$. These parameters are initialized using k-means, and refitted after every minimization step using the new estimated segmentation masks.

**Contour term.** Next, we define another data term that penalizes label swaps far from shape boundaries, and that combines these boundaries across the stereo pair. Its value is computed using shape distance transforms: first, we build maps in which each pixel is assigned its Euclidean distance to the closest pre-existing foreground or background pixel in the current view. We then use these maps to deduce the label update costs for each pixel in our graph, considering a mix of distances in both views at once (note the use of subscript $k$ below). More specifically, we define our contour term as

$$E_k^{\text{cont.}}(S_k) = \lambda_c \sum_{p \in I_k} \begin{cases} F_k(p) + \lambda_m \cdot F_{k'}(r(p, d_p)) & \text{if } s_p = 1 \\ B_k(p) + \lambda_m \cdot B_{k'}(r(p, d_p)) & \text{otherwise} \end{cases}, \quad (7.12)$$

where $\lambda_c$ and $\lambda_m$ are fixed scaling factors, $k'$ is the opposite index of $k$ in the stereo pair, $F_k(p)$ returns a nonlinear distance cost (described below) for pixel $p$ based on its distance to the closest foreground pixel in the previous segmentation of view $k$, and similarly for $B_k(p)$ with background pixels. Note in (7.12) that $\lambda_m$ scales the term's multispectral cost contribution. During our tests, we give it a value $\in ]0, 1[$, meaning that shape contours will prefer sticking to their own previous results. This improves the stability of the segmentation while optimizing, reducing the risk of eliminating relevant shape fragments too rapidly. For the nonlinear distance cost function behind $F_k(p)$ and $B_k(p)$, we use an exponential to increase the contrast between close range and long range contour overlaps. More specifically, we use a relation of the form

$$\text{distance-cost}(p) \propto \frac{1}{\exp(-t(p))}, \quad (7.13)$$
<figure><img src="image_37.png" /><figcaption>Figure 7.4 Illustration of the simplified frame layering used in our segmentation model for temporal labeling refinement. In green, the first-order cliques that form $E^{\text{smooth2}}$ are used to enforce spatial coherence in every layer. In blue, the higher order cliques that form $E^{\text{temp}}$ are used to enforce temporal coherence across layers. Note that due to foreground motion, these cliques would not all be linked to the same underlying nodes; in reality, the links are dictated by image realignment based on optical flow.</figcaption></figure>

where $t(p)$ returns the actual Euclidean distance between $p$ and its nearest pixel with a foreground or background label in the previous inference result, depending on the current value of $s_p$. The contour term's main responsibility is to control the evolution of object contours over several optimization passes. The multispectral contribution allows contours to be modified in regions where only one modality contributes meaningful information. The simple formulation of our contour term also avoids the needless filling of cavities, and it makes no assumption on the foreground-to-background ratio in the images.

**Smoothness term.** This pairwise term is similar to the one used in (7.8); its role is to penalize label discontinuities everywhere except for image regions where local gradients are strong. In this case, however, we reuse the multispectral contribution idea of (7.12), and apply it to the gradient scaling factor. We define this term as

$$E_k^{\text{smooth2}}(S_k) = \lambda_{s2} \sum_{\langle p, q \rangle \in \mathcal{N}_k} (s_p \oplus s_q) \cdot (G_{I_k}^s(p, q) + \lambda_m G_{I_{k'}}^s(p', q')) \quad (7.14)$$

where $\lambda_{s2}$ is a fixed scaling factor, $\oplus$ is the XOR operator, $p'$ is a shorthand for $r(p, d_p)$, and $q'$ is a shorthand for $r(q, d_q)$. In (7.14), the right-hand parentheses group returns the gradient coefficient with its multispectral contribution, and the left-hand group returns 1 or 0 based
on whether a label discontinuity is found. As before, the use of local image gradients helps “snap” these discontinuities to real object contours. However, the multispectral contribution allows shape contours to settle in uniform regions if the other view possesses a strong local gradient there. Paired with the contour term, this allows our model to properly expand and contract shape boundaries across image modalities. We study the effect of $\lambda_m$ on the performance of our method in Section 7.4.

**Temporal term.** Lastly, we present the formulation and role of our temporal term. Unlike the other terms presented so far, this term is based on higher order cliques that are composed at runtime, and updated for each frame. The role of these cliques is to enforce spatiotemporal labeling coherence despite foreground object motion. Our graph structure can be visualized as a stack of analyzed frames; this structure is shown in Figure 7.4. While the depth (or layer count) of this stack is predetermined, its temporal cliques are composed based on node realignments provided by optical flow maps. This allows cliques to remain attached to the same object part despite movement, and thus enforce labeling smoothness across frames. We compute optical flow maps using the method proposed by Kroeger et al. (2016). As for the cost term itself: given $C$, the set of all temporal cliques in our model, and using the subscript $l$ to identify different temporal layers in these cliques, we define it as

$$E^{\text{temp}}(D) = \lambda_{s2} \cdot \sum_{c \in C} \sum_{l=1}^{L-1} (s_{c,l} \oplus s_{c,(l+1)}) \cdot G^t(c, l), \quad (7.15)$$

where $\lambda_{s2}$ is the same scaling factor as in (7.14), $L$ is the pipeline’s depth in frames, $s_{c,l}$ returns the label of the $l$-th node in clique $c$, and $G^t(c, l)$ returns a scaling factor for clique $c$ at layer $l$ (described next). Overall, this term is similar to the pairwise smoothness terms described earlier, but it can link more nodes together. However, instead of scaling costs via local image gradients, we rely on temporal image gradients in $G^t(c, l)$. These new gradient values are obtained by computing the absolute color differences between pixels of consecutive frames realigned using optical flow maps. Strong color differences are indicative of uncertain regions where consistency costs should be reduced due to occlusions or bad optical flow estimation. Here, similarly to (7.9), we define the new gradient scale term as

$$G^t(c, l) = \max\left(\exp\left(1 - \frac{|i_{c,l} - i_{c,(l+1)}|}{g}\right) - 0.5, 0\right), \quad (7.16)$$

where $i_{c,l}$ returns the color value of the $l$-th node in clique $c$. We study the contribution of this new term in Section 7.4 given various layer count configurations.
### 7.3.3 Inference and Implementation Details

Simultaneously minimizing the cost functions defined in (7.3) and (7.10) is not trivial. Both functions rely on each other's provisional results as dynamic priors, and (7.10) contains a higher order term. Fortunately, recently proposed move-making algorithms can deal with these issues iteratively without having to resort to a move-and-check or rollback strategy (c.f. Lempitsky et al., 2010; Kappes et al., 2013). Such algorithms do not guarantee that a globally optimal solution will be found for either the stereo model, due to its non-binary label space, or for the segmentation model, due to its higher order term. However, in general, both labelings settle in acceptable local minima (i.e. non-degenerate cases) after some time, provided that the initialization masks used are not both completely empty. Our dual-model formulation also naturally converges to such local minima without having to use a “cooling” metaparameter to force a solution after a fixed number of iterations.

We rely on the move-making algorithms of Fix et al. (2011) and Fix et al. (2014) for the inference of our stereo and segmentation models, respectively. Both are modified for use in a dynamic graph structure. While faster inference solutions do exist, these were deemed fast enough for our experiments, even without having to parallelize label moves. In both cases, our move proposals only consist of uniform labeling maps, meaning our inference approach is similar to the α-expansion strategy of Boykov et al. (2001). We build our graphical models using OpenGM (Andres et al., 2012), and reuse the same structure for all frames in a video, updating only the composition of temporal factors in (7.15) as required.

We tackle the alternating minimization of energies (7.3) and (7.10) for each frame of a video by first minimizing the stereo model's energy using unary terms only, or by realigning its previous disparity labeling result via optical flow. Simultaneously, the segmentation model is initialized using the masks provided by an unsupervised monocular method, as stated earlier. Then, segmentation and disparity label moves are iteratively computed in small batches until no more moves in $\mathcal{L}_S$ can reduce the energy of (7.10). This typically happens after less than three passes over the disparity label space ($\mathcal{L}_D$), and less than 50 moves in the segmentation label space ($\mathcal{L}_S$), the exact number depending on the quality of the initialization. For reference, with our baseline implementation, this is equivalent to approximately 30 seconds worth of processing time on a single core of a 3.7 GHz Intel i7 processor for a VGA-sized image pair.

As for the free parameters listed earlier, we use the following configuration for our tests in the next section:

- Stereo model uniqueness term weight: $\lambda_u = 0.4$
— Stereo model smoothness term weight: $\lambda_{s1} = 0.001$

— Expected object contour gradient intensity: $g = 30$

— Segmentation model contour term weight: $\lambda_c = 7$

— Segmentation model smoothness weight: $\lambda_{s2} = 7$

— Multispectral contribution term weight: $\lambda_m = 0.5$

The values listed above have been empirically found to provide good overall segmentation performance on a small subset of our test data via grid search. As previously noted, we study the effect of several of these parameters on the overall performance of our method in the next section. For optical flow and DASC descriptors computations, we kept the default parameters provided by their original authors. For Shape Context computations, we used 50 pixel-wide descriptors with 10 angular bins and 3 radial bins. For the depth of our frame processing pipeline, we used two temporal layers (i.e. the current frame and the previous one), as adding more did not improve overall performance significantly over the extra processing cost; this is discussed in Section 7.4.4. Finally, to reduce the computational cost when using higher order terms in our segmentation model, we use a stride of two pixels when creating the temporal cliques used in (7.15). For more implementation details, we refer the reader to our source code<fnref n="3" />.

## 7.4 Experiments

In this section, we first discuss our evaluation methodology, and then present evaluation results for mutual segmentation and stereo registration. Since close-range (non-planar) multispectral video datasets are quite uncommon in the literature, we had to adapt existing datasets to our problem. For multispectral mutual segmentation, we rely on a modified version of the VAP trimodal dataset of Palmero et al. (2016); the modifications we made are detailed in Section 7.4.2. For stereo registration, we rely on the benchmark of Bilodeau et al. (2014). We follow up with an ablation study of our method in which we remove key terms from our energy functions, and then study the effect of tuning key parameters of these terms. Finally, we provide evaluation results for both segmentation and stereo registration on a newly captured and annotated RGB-LWIR dataset for future comparisons.

### 7.4.1 Evaluation Methodology

Since our primary goal is mutual foreground segmentation, we employ binary classification metrics for the first part of our evaluation. Commonly used metrics in the context of video

<footnote n="3">3. https://github.com/plstcharles/litiv</footnote>
<table><caption>Table 7.1 Evaluation results on the multispectral video segmentation dataset of Palmero et al. (2016). Bold results are the best in that category across all methods.</caption><thead><tr><th rowspan="2">Method</th><th rowspan="2">Metric</th><th colspan="2">Scene 1</th><th colspan="2">Scene 3</th><th colspan="3">Overall</th></tr><tr><th>visible</th><th>LWIR</th><th>visible</th><th>LWIR</th><th>visible</th><th>LWIR</th><th>Average</th></tr></thead><tbody><tr><td rowspan="3">St-Charles et al. (2016a)<br>(unsupervised)</td><td>Pr</td><td>0.820</td><td>0.755</td><td>0.716</td><td>0.514</td><td>0.768</td><td>0.635</td><td>0.701</td></tr><tr><td>Re</td><td>0.810</td><td><strong>0.975</strong></td><td>0.688</td><td><strong>0.969</strong></td><td>0.749</td><td><strong>0.972</strong></td><td>0.861</td></tr><tr><td>F<sub>1</sub></td><td>0.815</td><td>0.851</td><td>0.702</td><td>0.672</td><td>0.758</td><td>0.762</td><td>0.760</td></tr><tr><td rowspan="3">Rother et al. (2004)<br>(GrabCut; supervised)</td><td>Pr</td><td>0.685</td><td>0.808</td><td>0.653</td><td><strong>0.847</strong></td><td>0.669</td><td><strong>0.828</strong></td><td>0.748</td></tr><tr><td>Re</td><td>0.759</td><td>0.896</td><td><strong>0.929</strong></td><td>0.916</td><td>0.844</td><td>0.906</td><td>0.875</td></tr><tr><td>F<sub>1</sub></td><td>0.721</td><td>0.850</td><td>0.767</td><td><strong>0.880</strong></td><td>0.744</td><td><strong>0.865</strong></td><td>0.804</td></tr><tr><td rowspan="3">Proposed method<br>(unsupervised)</td><td>Pr</td><td><strong>0.894</strong></td><td><strong>0.860</strong></td><td><strong>0.788</strong></td><td>0.749</td><td><strong>0.841</strong></td><td>0.804</td><td><strong>0.821</strong></td></tr><tr><td>Re</td><td><strong>0.902</strong></td><td>0.901</td><td>0.918</td><td>0.937</td><td><strong>0.910</strong></td><td>0.919</td><td><strong>0.914</strong></td></tr><tr><td>F<sub>1</sub></td><td><strong>0.898</strong></td><td><strong>0.880</strong></td><td><strong>0.848</strong></td><td>0.833</td><td><strong>0.873</strong></td><td>0.857</td><td><strong>0.866</strong></td></tr></tbody></table>

segmentation are Precision (Pr), Recall (Re), and $F_1$ score. These are based on three types of pixel-wise classification result counts, namely True Positives (TP), False Positives (FP), and False Negatives (FN). These metrics are defined as

$$ \text{Precision} = \frac{\text{TP}}{\text{TP} + \text{FP}}, \qquad (7.17) $$

$$ \text{Recall} = \frac{\text{TP}}{\text{TP} + \text{FN}}, \qquad (7.18) $$

$$ F_1 = \frac{2 \cdot \text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}}, \qquad (7.19) $$

In all three cases, higher values indicate better performance. The $F_1$ score corresponds to the harmonic mean of the precision and recall scores. We use it as an overall indicator of binary segmentation performance, as it was shown in the work of Goyette et al. (2012) to be strongly correlated with the final ranking of methods on a large binary segmentation dataset based on numerous other metrics.

Our second goal is to evaluate stereo registration performance. For this, we employ the strategy of the Middlebury dataset (Scharstein et al., 2014), and report the percentage of pixels labeled with disparity errors larger than some fixed distance thresholds (in pixels). We also report average frame-wide pixel disparity errors, noted $\bar{d}_{\text{err}}$ below. In this case, lower values indicate better performance.
7.4.2 VAP 2016 Dataset

For this first part of our evaluation, we adapted the dataset of Palmero et al. (2016) to
our needs. This dataset was originally intended for the trimodal (RGBD-LWIR) detection
and segmentation of people in images, and it is provided as a set of videos. It consists of
5724 image triplets split into three scenes, with their associated groundtruth foreground-
background segmentation masks. We obtained the calibration data used by the original
authors to roughly register scene contents via homographies, and rectified all RGB and LWIR
image pairs using the OpenCV calibration toolbox. The depth images were left unused during
all our experiments, and the second scene was removed due to missing calibration data.
Finally, to avoid skewing the performance evaluation by continuously segmenting empty
frames or frames with purely static and/or unoccluded foreground regions, we manually
selected a subset of groundtruth masks for our experiments. These masks were picked at a
rate of roughly 2 Hz from all originally available masks while focusing on time spans with
people interacting.

We present the segmentation performance of our proposed method, as well as the performance of baseline video and image segmentation methods in Table 7.1. We could not evaluate the performance of the works listed in the last paragraph of Section 7.2 that simultaneously tackle segmentation and registration due to a lack of open-source code and datasets. Besides, comparing our results to those of other methods that assume single-spectrum data or planar scenes would also be unfair. For the video segmentation baseline, we rely on the method of St-Charles et al. (2016a), which is fully unsupervised. For the image segmentation baseline, we rely on the GrabCut method of Rother et al. (2004), and provide this method with bounding boxes for all foreground objects. We used OpenCV's GrabCut implementation, and ran five iterations per image.

We can observe that our proposed method outperforms the unsupervised video segmenta-
tion approach of St-Charles et al. (2016a) in terms of overall F₁ score by a margin of 0.1,
equal to a relative improvement of over 13%. This confirms that our approach can properly
integrate multispectral information through stereo registration in order to improve segmen-
tation performance beyond that of a state-of-the-art monocular method. Interestingly, our
proposed method even outperforms the supervised image segmentation approach of Rother
et al. (2004), which relies on manual annotations to pinpoint all foreground objects in every
frame. This can be explained by the fact that foreground objects in this dataset have bet-
ter contrast in the LWIR spectrum than in the visible spectrum, and because our approach
propagates this contrast information across the stereo pair. Finally, we show in Figure 7.5
some qualitative results for this dataset. The last row of this figure presents an interesting
case: in this frame pair, the initial foreground masks provided to our method both contain
important errors in different regions, but the output is excellent. This shows that despite
not having a proper foreground shape template, the real underlying shape can be found and
extracted correctly via our iterative process.

7.4.3 Bilodeau *et al.* 2014 Dataset

We now evaluate our proposed method’s stereo registration accuracy using the benchmark dataset of Bilodeau et al. (2014). This dataset was originally intended for the evaluation of image descriptors and similarity measures in the context of multispectral stereo matching, once again provided as a set of videos. It consists of 5390 RGB-LWIR frame pairs split into three scenes, with over 25,000 sparse correspondences annotated on visible foreground objects.

As stated before, we evaluate performance on this dataset by analyzing the accuracy of
disparity labelings. Unfortunately, previous works tackling multispectral registration have
often relied on their own foreground overlap ratios to assess their performance (e.g. Nguyen
et al., 2016), meaning comparisons here are impossible. Here, to provide a reusable evaluation
baseline, we compare our results to those obtained using a simple sliding window approach
based on the matching of image patches. In short, local disparities are assigned based on
the best match (or smallest distance) found between these patches in a winner-takes-all
fashion. To describe the similarity between image patches, we rely on descriptors, namely
LSS (Shechtman and Irani, 2007) and DASC (Kim et al., 2015), and on Mutual Information
(MI) scores (Maes et al., 1997). Finally, to highlight the issue of applying traditional stereo
registration methods on multispectral datasets, we evaluate the block matching algorithm of
K. Konolige implemented in OpenCV. These results are presented in Table 7.2.

We can note that our proposed method performs very well compared to the baseline methods. Unsurprisingly, OpenCV's block matching method fails on this dataset as it tries to compare image textures directly across the pair, despite their low correlation. The approaches based on self-similarity descriptors (LSS, DASC) and mutual information perform slightly better, but still produce highly inaccurate results. On average, above 50% of all the evaluated points are labeled with disparities at least four pixels off from the groundtruth. On the other hand, our approach manages to label 51.8% of all evaluated points within a single pixel of the groundtruth, and provides an average disparity error of only 3.21 pixels. Note however that while this performance is good enough for our primary task (mutual foreground segmentation), it is still far from the current state-of-the-art in single-spectrum stereo registration. For example, on the Middlebury dataset (Scharstein et al., 2014), top-performing methods
<table><caption>Table 7.2 Evaluation results on the multispectral video registration dataset of Bilodeau et al. (2014). Bold results are the best in that category across all methods.</caption><thead><tr><th rowspan="3">Method</th><th colspan="3">Video 1</th><th colspan="3">Video 2</th><th colspan="3">Video 3</th><th colspan="3">Overall</th></tr><tr><th colspan="2">% err.</th><th rowspan="2">d&#773;<sub>err</sub></th><th colspan="2">% err.</th><th rowspan="2">d&#773;<sub>err</sub></th><th colspan="2">% err.</th><th rowspan="2">d&#773;<sub>err</sub></th><th colspan="2">% err.</th><th rowspan="2">d&#773;<sub>err</sub></th></tr><tr><th>&gt;1px</th><th>&gt;4px</th><th>&gt;1px</th><th>&gt;4px</th><th>&gt;1px</th><th>&gt;4px</th></tr></thead><tbody><tr><td>OpenCV's Block Matcher</td><td>95.5</td><td>95.3</td><td>27.51</td><td>99.8</td><td>99.7</td><td>38.99</td><td>99.8</td><td>99.6</td><td>34.76</td><td>98.3</td><td>98.2</td><td>33.75</td></tr><tr><td>LSS Sliding Window</td><td>78.3</td><td>61.3</td><td>9.81</td><td>88.8</td><td>76.5</td><td>8.73</td><td>80.4</td><td>55.5</td><td>9.11</td><td>82.5</td><td>64.4</td><td>9.22</td></tr><tr><td>MI Sliding Window</td><td>79.2</td><td>59.5</td><td>9.81</td><td>86.8</td><td>59.8</td><td>8.62</td><td>82.6</td><td>60.9</td><td>10.81</td><td>82.9</td><td>60.1</td><td>9.74</td></tr><tr><td>DASC Sliding Window</td><td>81.1</td><td>58.3</td><td>8.96</td><td>79.3</td><td>57.1</td><td>6.55</td><td>73.6</td><td>43.5</td><td>6.94</td><td>78.0</td><td>52.0</td><td>7.48</td></tr><tr><td>Proposed method</td><td><b>47.7</b></td><td><b>17.3</b></td><td><b>3.28</b></td><td><b>55.6</b></td><td><b>25.4</b></td><td><b>3.11</b></td><td><b>52.0</b></td><td><b>17.5</b></td><td><b>3.26</b></td><td><b>51.8</b></td><td><b>20.1</b></td><td><b>3.21</b></td></tr></tbody></table>

typically label less than 20% of all points with a disparity error larger than a single pixel. This highlights the difficulty of multispectral stereo registration.

### 7.4.4 Parameters and Ablation Study

In this section, we study the behavior of our method when key terms and parameters are modified from the default configuration listed in Section 7.3.3 on the two previously introduced datasets. First, we perform an ablation study to determine which energy terms are the most important in our models; this study is presented in Table 7.3.

According to the $F_1$ scores, modifying the stereo energy formulation only has a small effect on segmentation performance. On the other hand, removing the color or contour terms from the segmentation energy has larger impacts, and the latter of the two is the most important contributor to overall performance. As for the registration performance, the shape term seems to be the most important, but all terms contribute to the overall performance of the method. The positive contribution of both appearance and shape terms thus confirms the hypothesis set in Section 7.3.1. Besides, interestingly, when our model is initialized in only one of the two modalities using approximative masks, its segmentation performance is still at least as good as GrabCut's (as reported in Table 7.1). This highlights the robustness of our approach, and shows that it can perform well even in adverse initialization conditions.

Next, we show the effect of parameter tuning. The segmentation and registration performance for our proposed method in terms of overall $F_1$ score and average disparity error ($d_{err}$, in pixels) is presented for various configurations in Figure 7.6. Note that we roughly tuned our method with segmentation performance as a priority to obtain our default configuration. Nonetheless, registration performance is usually near-optimal or stable around the same parameter values. In general, we can note that the choice of parameters does not seem to drastically alter our method's performance, as both metrics fairly remain stable over large
<table><caption>Table 7.3 Overall performance for various configurations of the proposed method on the datasets of Palmero et al. (2016); Bilodeau et al. (2014).</caption><thead><tr><th>Method Configuration</th><th>d&#773;<sub>err</sub></th><th>F<sub>1</sub></th></tr></thead><tbody><tr><td>No Shape Term (E<sup>shape</sup>)</td><td>8.71</td><td>0.860</td></tr><tr><td>No Appearance Term (E<sup>appearance</sup>)</td><td>3.69</td><td>0.851</td></tr><tr><td>No Saliency Maps (W)</td><td>3.47</td><td>0.856</td></tr><tr><td>No Uniqueness Term (E<sup>uniqueness</sup>)</td><td>3.33</td><td>0.865</td></tr><tr><td>No Color Term (E<sup>color</sup>)</td><td>3.46</td><td>0.822</td></tr><tr><td>No Contour Term (E<sup>contour</sup>)</td><td>4.16</td><td>0.624</td></tr><tr><td>No Temporal Term (E<sup>temporal</sup>)</td><td>3.29</td><td>0.855</td></tr><tr><td>No Initial LWIR Segm. Mask</td><td>10.82</td><td>0.820</td></tr><tr><td>No Initial Visible Segm. Mask</td><td>8.32</td><td>0.800</td></tr><tr><td>Default Configuration</td><td>3.21</td><td>0.866</td></tr></tbody></table>

<table><caption>Table 7.4 Overall segmentation performance for various temporal pipeline depths on the dataset of Palmero et al. (2016).</caption><thead><tr><th>Method Configuration</th><th>Pr</th><th>Re</th><th>F<sub>1</sub></th></tr></thead><tbody><tr><td>2 Layers, Real-time</td><td>0.817</td><td>0.910</td><td>0.863</td></tr><tr><td>3 Layers, Real-time</td><td>0.821</td><td>0.915</td><td>0.866</td></tr><tr><td>4 Layers, Real-time</td><td>0.825</td><td>0.918</td><td>0.867</td></tr><tr><td>5 Layers, Real-time</td><td>0.826</td><td>0.918</td><td>0.868</td></tr><tr><td>2 Layers, Deferred</td><td>0.821</td><td>0.914</td><td>0.866</td></tr><tr><td>3 Layers, Deferred</td><td>0.824</td><td>0.920</td><td>0.870</td></tr><tr><td>4 Layers, Deferred</td><td>0.827</td><td>0.921</td><td>0.870</td></tr><tr><td>5 Layers, Deferred</td><td>0.826</td><td>0.919</td><td>0.868</td></tr><tr><td>No Temporal Term</td><td>0.801</td><td>0.919</td><td>0.855</td></tr></tbody></table>

value intervals.

Finally, in Table 7.4, we evaluate our approach configured with different temporal pipeline depths, and while allowing deferred output or not. The notion of “pipeline depth” here corresponds to the number of edges in the higher order temporal terms introduced in Section 7.3.2.
Deferred segmentation outputs are masks generated by our method with the added latency of the full pipeline, meaning the results are evaluated with a delay equal to the pipeline depth. These masks are thus allowed more iterations in our graphical model, and benefit from more temporal information (i.e. past and future frame data). On the other hand, the real-time segmentation outputs are the masks generated by our method for all new image pairs, provided without delay. From these results, we can note that the difference between deferred and real-time output is surprisingly small. This means that our model's temporal inertia allows it to smooth out shape variations without having to peek at future frame data, which is useful for real-time surveillance systems. Besides, the overall improvements obtained by using more than two temporal layers is marginal, as more temporally consistent results also entail that some relevant shape fragments around non-rigid objects are discarded. Finally, note that using more layers results in an important increase in computational complexity: using four layers roughly triples the time required for model inference compared to the default configuration.

### 7.4.5 LITIV 2018 Dataset

To help others compare their work on multispectral segmentation and registration, we developed and annotated a new dataset. We recorded video sequences using a stereo pair composed of a Kinect v2 for Windows (at Full HD resolution) and a FLIR A40 LWIR camera (at QVGA resolution). The sensors were roughly aligned on a fixed baseline support (approximately 50 centimeters apart) and synchronized via software to capture frame pairs at 30 Hz. Calibration data for image rectification was obtained by capturing snapshots of a foam core checkerboard pattern heated using halogen lamps to make it visible in LWIR images. For the annotations, we simultaneously recorded depth and user segmentation masks provided by the Kinect SDK, and transformed this data into foreground-background segmentation masks, adding manual touch-ups where needed. Stereo correspondences were also manually annotated like in the work of Bilodeau et al. (2014) to allow an approximate evaluation of registration performance in foreground image regions. In total, this dataset contains over 6000 frame pairs split into three videos, and its groundtruth is composed of 866 binary segmentation masks and 14716 point correspondences roughly distributed among frames with visible foreground. As for the capture conditions, we deliberately recorded sequences with both strong and weak contrast between foreground and background regions in the two image modalities. More specifically, we used two different temperature calibrations to make individuals more or less perceptible in LWIR images, we introduced some cluttered background in part of the visible images, and we had people carry and exchange objects that modify their appearance in both spectral bands. Overall, this dataset should be more challenging than already available RGB-LWIR video
<table><caption>Table 7.5 Evaluation results for the proposed method on our newly captured multispectral video dataset.</caption><thead><tr><th rowspan="2">Evaluation Type<br>(Method)</th><th rowspan="2">Metric</th><th colspan="2">Video 1</th><th colspan="2">Video 2</th><th colspan="2">Video 3</th><th colspan="3">Overall</th></tr><tr><th>visible</th><th>LWIR</th><th>visible</th><th>LWIR</th><th>visible</th><th>LWIR</th><th>visible</th><th>LWIR</th><th>Average</th></tr></thead><tbody><tr><td rowspan="3">Segmentation<br>(St-Charles et al., 2016a)</td><td>Pr</td><td>0.933</td><td>0.716</td><td>0.938</td><td>0.763</td><td>0.935</td><td>0.821</td><td><strong>0.935</strong></td><td>0.767</td><td>0.851</td></tr><tr><td>Re</td><td>0.721</td><td>0.997</td><td>0.834</td><td>0.938</td><td>0.750</td><td>0.996</td><td>0.768</td><td><strong>0.977</strong></td><td><strong>0.872</strong></td></tr><tr><td>F<sub>1</sub></td><td>0.813</td><td>0.834</td><td>0.883</td><td>0.841</td><td>0.832</td><td>0.900</td><td>0.843</td><td>0.858</td><td>0.851</td></tr><tr><td rowspan="3">Segmentation<br>(Proposed)</td><td>Pr</td><td>0.867</td><td>0.931</td><td>0.874</td><td>0.923</td><td>0.918</td><td>0.941</td><td>0.887</td><td><strong>0.931</strong></td><td><strong>0.909</strong></td></tr><tr><td>Re</td><td>0.741</td><td>0.822</td><td>0.860</td><td>0.860</td><td>0.917</td><td>0.911</td><td><strong>0.839</strong></td><td>0.865</td><td>0.852</td></tr><tr><td>F<sub>1</sub></td><td>0.799</td><td>0.873</td><td>0.867</td><td>0.891</td><td>0.918</td><td>0.926</td><td><strong>0.861</strong></td><td><strong>0.897</strong></td><td><strong>0.879</strong></td></tr><tr><td rowspan="4">Registration<br>(DASC Sliding Window)</td><td>% err. &gt;1px</td><td>90.6</td><td>88.6</td><td>92.1</td><td>90.8</td><td>88.5</td><td>87.2</td><td>90.4</td><td>88.8</td><td>89.6</td></tr><tr><td>% err. &gt;2px</td><td>85.2</td><td>81.9</td><td>86.6</td><td>83.7</td><td>81.9</td><td>80.2</td><td>84.6</td><td>81.9</td><td>83.3</td></tr><tr><td>% err. &gt;4px</td><td>75.5</td><td>71.6</td><td>78.6</td><td>74.2</td><td>72.3</td><td>70.0</td><td>75.5</td><td>71.9</td><td>73.7</td></tr><tr><td>d̄<sub>err</sub></td><td>30.26</td><td>21.90</td><td>31.22</td><td>29.11</td><td>26.48</td><td>23.34</td><td>29.32</td><td>24.79</td><td>27.05</td></tr><tr><td rowspan="4">Registration<br>(Proposed)</td><td>% err. &gt;1px</td><td>76.3</td><td>80.5</td><td>71.3</td><td>71.6</td><td>66.5</td><td>66.9</td><td><strong>71.4</strong></td><td><strong>73.0</strong></td><td><strong>72.2</strong></td></tr><tr><td>% err. &gt;2px</td><td>63.9</td><td>70.5</td><td>55.4</td><td>55.6</td><td>48.7</td><td>48.9</td><td><strong>56.0</strong></td><td><strong>56.7</strong></td><td><strong>57.3</strong></td></tr><tr><td>% err. &gt;4px</td><td>46.8</td><td>56.2</td><td>36.4</td><td>37.1</td><td>28.9</td><td>29.5</td><td><strong>37.4</strong></td><td><strong>40.9</strong></td><td><strong>39.2</strong></td></tr><tr><td>d̄<sub>err</sub></td><td>16.76</td><td>19.99</td><td>6.68</td><td>7.63</td><td>5.17</td><td>5.47</td><td><strong>9.53</strong></td><td><strong>11.03</strong></td><td><strong>10.28</strong></td></tr></tbody></table>

datasets. The fact that it also allows the simultaneous evaluation of foreground segmentation and stereo registration also makes it quite unique in the current literature.

We have made this new dataset available online along with our modified version of the VAP dataset for other authors<fnref n="4" />. Our Kinect's raw data which includes depth images and mapping information is also provided for those interested in trimodal segmentation tasks.

We offer our proposed method's results on this new dataset as a baseline for future comparisons in Table 7.5. We can note that compared to the other two datasets, segmentation results here are still good, but registration errors are much higher. This is primarily due to the fact that our camera baseline is very large (≈ 50 cm), which leads to high disparities for close-range objects (over 150 pixels in some cases), and because our images are higher resolution than those of Bilodeau et al. (2014). Also, we can note that registration errors are higher in the first video sequence: this is caused by the loss of some small foreground segments near image borders which were annotated with correspondences. As for the segmentation results, there are cases where foreground objects are only partly detected, which results in slightly lower Recall scores in some videos. Nonetheless, these results show that our method is capable of segmentating foreground objects in difficult imaging conditions. Finally, we present qualitative segmentation results for this dataset in Figure 7.7.

<footnote n="4">4. http://www.polymtl.ca/litiv/vid/index.php</footnote>
7.5 Conclusion

We have presented a new method for simultaneous multispectral foreground segmentation and stereo registration, and validated its capabilities on several datasets. Our approach is based on the alternating minimization of two linked energy functions that integrate multispectral shape and appearance cues. We have shown that both segmentation masks and disparity maps can simultaneously converge to good local minima without any human supervision. Furthermore, with the help of higher order factors, we achieve strong temporal coherence in our segmentation results by linking consecutive video frames inside our graphical models. To make the comparison of methods tackling this problem easier in the future, we provide our full implementation online, as well as a newly created multispectral dataset for evaluation.

If supporting large stereo baselines is unnecessary, the method could use a stronger constraint on multispectral contour similarity to improve coherence between views. Besides, explicit occlusion handling in our stereo model would further improve overall performance on the current datasets. Our model could also be generalized to provide instance-level segmentation by using a separate foreground appearance model for each object. Finally, a three-way energy minimization solution tackling foreground segmentation, stereo registration, and optical flow could be designed based on our current inference approach.
<figure><img src="image_38.png" /><figcaption>Segmentation results of the proposed method</figcaption></figure>

<figure><img src="image_39.png" /></figure>

Figure 7.5 Examples of typical segmentation results from the VAP dataset of Palmero et al. (2016); the left two columns show the segmentation masks obtained via the method of St-Charles et al. (2016a) and used to initialize our method, and the right two columns show our final segmentation masks. Image regions properly classified as foreground are highlighted in green over the original images, while regions highlighted in orange and magenta show false positives and false negatives, respectively. Images have been cropped to show more details.
<figure><img src="image_40.png" /><figcaption>Figure 7.6 Overall performance for various parameter values of the proposed method on the datasets of Palmero et al. (2016); Bilodeau et al. (2014). The default configuration of each parameter is shown with the dashed line. Remember that for $F_1$, higher is better, and for $\bar{d}_{err}$, lower is better.</figcaption></figure>
<figure><img src="image_41.png" /><figcaption>Segmentation results of the proposed method</figcaption></figure>

<figure><img src="image_42.png" /></figure>

Figure 7.7 Examples of typical segmentation results from our newly captured dataset; the left two columns show the segmentation masks obtained via St-Charles et al. (2016a) and used to initialize our method, and the right two columns show our final segmentation masks. Image regions properly classified as foreground are highlighted in green over the original images, while regions highlighted in orange and magenta show false positives and false negatives, respectively. Images have been cropped to show more details.
# CHAPITRE 8 DISCUSSION GÉNÉRALE

Ce chapitre présente une synthèse de chaque volet du travail accompli. Plus spécifiquement, nous abordons les limitations identifiées a posteriori pour chacune des méthodes développées ainsi que les améliorations qui pourraient être apportées à ces méthodes. Nous discutons aussi de l'efficacité globale du pipeline de traitement bas niveau développé.

## 8.1 Segmentation vidéo par soustraction d'arrière-plan

Les deux méthodes de soustraction d'arrière-plan proposées dans les chapitres 4 et 5 offrent des solutions différentes aux défis typiquement rencontrés en segmentation vidéo monoculaire. Bien que leurs performances globales évaluées sur l'ensemble de données de Wang et al. (2014a) soient similaires, la méthode du chapitre 4 (SuBSENSE) est mieux adaptée aux conditions des scénarios plus extrêmes (e.g. surveillance de nuit, surveillance sous la pluie/neige) que la méthode du chapitre 5 (PAWCS). Par contre, PAWCS offre des résultats largement supérieurs à ceux de SuBSENSE en présence d'objets immobilisés à long terme. Puisque de tels objets sont relativement communs en vidéosurveillance, PAWCS est la méthode la plus adéquate pour effectuer un pré-traitement dans un système de surveillance réel. Au final, cette méthode répond bien aux objectifs de segmentation monoculaire énoncés dans la section 1.3 ; elle est capable de détecter et de segmenter n'importe quel type d'objet faisant irruption dans une scène tout en s'adaptant aux variations naturelles de son arrière-plan. La conception de cette méthode fait d'ailleurs complètement abstraction de la modalité d'imagerie traitée, ce qui est idéal pour effectuer l'initialisation des méthodes des chapitres 6 et 7.

Notons ici que les masques de segmentation produits par les méthodes de soustraction d'arrière-plan des chapitres 4 et 5, dans des scénarios de type "baseline", sont de qualité comparable au *groundtruth* utilisé pour leur évaluation (i.e. dans l'ordre de l'incertitude des annotations). Cela démontre que la segmentation vidéo n'est plus problématique lorsque les images ne possèdent pas d'arrière-plan dynamique, lorsque le contraste entre l'arrière-plan et l'avant-plan n'est pas faible, et lorsque les objets d'intérêt ne projettent pas d'ombres trop prononcées au sol (*hard shadows*). Dans les cas où une partie de l'arrière-plan varie légèrement et où les ombres sont adoucies par l'éclairage ambiant, la segmentation vidéo est relativement près d'être considérée comme non-problématique.

En ce qui concerne les limitations des méthodes proposées, nous pouvons identifier d'abord que celles-ci sont assez sensibles à la résolution des images traitées. Cela s'explique par le
descripteur binaire qu'elles utilisent pour la caractérisation de représentations d'images, qui est de taille fixe (5x5). La conséquence liée à cette utilisation est que des objets d'intérêt de taille inférieure à ce descripteur peuvent être considérés comme du bruit dans l'arrière-plan, tandis que les textures d'échelle plus grande ne peuvent pas être capturées dans les modèles de pixels. Une solution à ce problème consiste à utiliser une approche de description multi-échelle, telle que celle proposée par St-Charles et al. (2016b). Par ailleurs, ces méthodes de segmentation par pixel n'utilisent aucunement le concept d'*objectness* souvent exploité en segmentation vidéo afin de mieux identifier l'ensemble des pixels appartenant à un objet d'intérêt. L'utilisation de ce concept en post-traitement à travers un modèle graphique simple pourrait aider à mieux refermer les formes d'objets fragmentés.

## 8.2 Recalage de paires d'images multispectrales

Les stratégies de recalage de paires d'images proposées dans les chapitres 6 et 7 sont conçues pour être appliquées dans des scénarios très différents, c'est à dire sur des scènes planaires ou non-planaires. Ces stratégies partagent toutefois l'idée générale que les points provenant de contours d'objets détectés par segmentation peuvent fournir une quantité suffisante d'information discriminative permettant de recaler ces objets. Bien que la qualité des résultats obtenue ici est loin de celle typiquement atteignable en recalage monospectral, il est démontré au chapitre 7 que cette stratégie permet une intégration appropriée des données multispectrales, ce qui résulte en une amélioration de la qualité des masques de segmentation. Cela répond donc aussi aux exigences fixées dans la section 1.3 pour nos objectifs de recalage multispectral.

L'approche de recalage du chapitre 6 pour des scènes planaires pourrait être améliorée en considérant des segments de contours (i.e. groupes de points) plutôt que des points individuels. Cela nous permettrait de distinguer les sections de contours fiables (i.e. qui possèdent une courbure semblable dans les deux images) des sections peu fiables pour le recalage de formes. Les sections de formes peu fiables, qui sont causées par des imperfections dans les masques de segmentation, pourraient alors être recalées à partir de la mise en correspondance d'un autre type de représentation de haut niveau (e.g. les arêtes de l'image).

Pour l'approche de recalage de scènes non-planaires du chapitre 7, il serait possible d'améliorer la rectification (et ainsi le recalage) des images en perfectionnant les paramètres de calibration utilisés au temps d'exécution. En effet, les paramètres de calibration initiaux obtenus préalablement pour nos ensembles de données ne sont pas idéaux, car l'erreur de reprojection des points sur leur plan de calibration se situe au-delà d'un pixel. Ce problème induit des erreurs au niveau de la mise en correspondance des pixels sur les épipoles, ce qui
diminue la qualité des disparités estimées localement. Le peaufinage des paramètres de calibration au temps d'exécution permettrait donc d'obtenir de meilleurs résultats. Cela pourrait être réalisé en combinant les points de calibration initiaux aux points de contours tirés des résultats de segmentation afin d'estimer de nouveaux paramètres. Une approche semblable a d'ailleurs été proposée dans le chapitre 6 pour l'estimation par RANSAC des paramètres d'une transformation projective en continu.

Enfin, l'approche du chapitre 7 pourrait aussi être améliorée par la modélisation explicite des pixels en occultation dans chaque image traitée. En bref, dans les cas où la parallaxe n'est pas négligeable, la disparité (ou profondeur) réelle des pixels cachés par un objet d'avant-plan dans une des images ne peut pas être déterminée avec précision. Toutefois, cette disparité devrait être semblable à celle de ses voisins. Dans la méthode actuelle, ces pixels sont souvent assignés une valeur adéquate par lissage, mais il est possible qu'ils créent un îlot de mauvaise valeurs dans la carte de disparités générée. Une modélisation explicite des occultations permettrait de forcer leur lissage à partir d'autres pixels dans leur voisinage.

## 8.3 Segmentation mutuelle d'images multispectrales

L'approche de segmentation mutuelle d'objets d'intérêt proposée dans le chapitre 7 peut être réalisée grâce au recalage dense des images traitées et grâce à la détection *a priori* des objets d'intérêt s'y retrouvant. Cette approche n'est pas basée sur l'apprentissage des caractéristiques de chaque modalité d'imagerie ou bien de la forme des types d'objets ciblés, mais plutôt sur la combinaison et sur l'évolution de modèles d'avant-plan multispectraux. L'évolution de ces modèles par notre processus d'optimisation itératif permet d'identifier et de segmenter adéquatement les objets d'intérêt de la scène malgré une initialisation potentielle-ment imparfaite, ce qui répond bien aux deux derniers objectifs spécifiques de la section 1.3.

En rétrospective, nous pouvons noter qu'une des faiblesses de l'approche de modélisation proposée au chapitre 7 est la complexité des graphes construits. Autant au niveau du modèle de recalage que du modèle de segmentation, la quantité de nœuds utilisée pour représenter les régions de chaque image semble parfois nuire au lissage des cartes de résultats produites. Dans la méthode proposée, chaque pixel des images traitées constitue un nœud, et ces nœuds sont connectés à leurs voisins immédiats à l'aide de facteurs d'ordre un (voir l'illustration de la figure 8.1.a). Ces facteurs sont responsables du lissage final des cartes de résultats produites, mais en pratique, ils ne semblent pas être en mesure de toujours bien jumeler les changements d'étiquettes de disparités ou de segmentation aux contours des objets d'intérêt, peu importe les hyperparamètres utilisés. Une des raisons pouvant expliquer ce phénomène est qu'il existe trop d'incertitude dans les coûts associés aux facteurs unaires du graphe. Cela s'explique par
<figure><img src="image_43.png" /><figcaption>Figure 8.1 Exemple de modélisation graphique où chaque pixel d'une image constitue un nœud (a), et où les superpixels de l'image sont calculés et utilisés comme nœuds (b). La deuxième approche permet de réduire le nombre total de nœuds et de liens dans le graphe, ce qui accélère le temps de traitement, en plus d'offrir un meilleur lissage des données.</figcaption></figure>

le fait que la modélisation par pixel n'est pas appropriée pour le recalage et la segmentation d'images sur la base de représentations de haut niveau (i.e. les contours d'objets). Par conséquent, il faudrait utiliser une approche de modélisation où les nœuds du graphe sont établis à un niveau légèrement plus élevé, par exemple en se basant sur des superpixels (voir l'exemple de la figure 8.1.b). Des superpixels de différentes tailles respectant les contours des objets de la scène peuvent d'ailleurs être calculés facilement en suivant par exemple l'approche de Achanta et al. (2012). La modélisation par superpixels permettrait alors de mieux lisser les étiquettes de régions voisines dans les cartes de disparités et de segmentation produites tout en gardant une partie de la précision obtenue grâce à une approche de modélisation de bas niveau.

D'autre part, l'utilisation d'un mécanisme d'ajustement pour déterminer la valeur adéquate du facteur contrôlant la contribution multimodale ($\lambda_m$) dans la section 7.3.2 aurait aussi été bénéfique. Ce mécanisme aurait pu être basé sur l'estimation de saillance locale effectuée pour chaque image dans la section 7.3.1. L'aboutissement aurait alors permis une évolution plus rapide des contours d'objets détectés dans la paire d'images, et une diminution des chances de trouver un minimum local imparfait lors de l'évolution de ces contours.

## 8.4 Efficacité du pipeline de traitement pour usage temps-réel

Finalement, nous discutons ici de l'applicabilité de notre pipeline de traitement dans un contexte de vidéosurveillance en temps réel. Rappelons-nous d'abord que le pipeline de traitement complet est essentiellement réalisé et testé dans l'article du chapitre 7. La solution proposée dans ce chapitre utilise la méthode de segmentation vidéo du chapitre 5 pour le pré-traitement des séquences d'images brutes, et propose sa propre stratégie de recalage et
de segmentation mutuelle de paires d'images. L'implémentation des différentes composantes
de cette solution a été effectuée dans un même cadriciel, ce qui nous permet de considérer son
efficacité de façon globale. Notons toutefois que l'optimisation de cette efficacité n'a pas été
notre première priorité lors de cette phase de développement. Notre propre code ne profite
donc pas de toute la parallélisation et de toute la vectorisation d'instructions auquel il aurait
eu droit.

Tel que mentionné dans la section 7.3.3, la génération des cartes de disparités et de segmen-
tation finales, pour une paire d'images de taille 640x480, demande environ 30 secondes de
calcul sur CPU, ce qui est loin de satisfaire les exigences du “temps réel” (≈ 30 Hz). Par
contre, plus de 90% de ce temps est consacré à l’inférence des cartes de résultats à partir des
modèles graphiques construits. Les méthodes d’inférence utilisées proviennent des travaux de
Fix et al. (2011) et Fix et al. (2014), et celles-ci sont implémentées sur CPU sans aucune
parallélisation. Il est donc possible de considérer qu’une implémentation parallèle sur GPU
similaire à celle de Vineet and Narayanan (2008) pourrait grandement améliorer l’efficacité
de notre pipeline. La simplification des modèles graphiques suggérée dans la section 8.3 (fi-
gure 8.1) pourrait aussi diminuer le temps d’inférence par un facteur important (i.e. 10 ou
plus).

En ce qui concerne la méthode de pré-traitement du chapitre 5, celle-ci est déjà en mesure de
traiter des séquences d'images de manière assez rapide, c'est à dire à plus de 10 trames par
seconde sur CPU pour une résolution de 640x480. Par ailleurs, l'implémentation GPU d'une
version simplifiée de la méthode du chapitre 4 (qui est similaire à la méthode utilisée ici) a
été réalisée dans le cadre d'autres travaux. Cette implémentation parallèle peut segmenter
des images à un rythme plus rapide que le taux de versement vers le GPU, c'est à dire à
plusieurs milliers de trames par seconde. Cela est dû au fait que la modélisation et la détection
d'objets d'intérêt selon une approche par pixel sans régularisation globale est un problème
de parallélisation d'une facilité dite “embarrassante” (*embarrassingly parallel*). Nous pouvons
donc conclure que la parallélisation de notre méthode finale de soustraction d'arrière-plan
pourrait aussi profiter d'un gain d'efficacité semblable.

En résumé, l'implémentation présentement disponible en ligne de notre pipeline complet ne
permet pas de produire des résultats en temps réel. Par contre, cet objectif n'est pas hors de
portée si nous tenons compte de la capacité de calcul des GPUs présentement sur le marché
et du potentiel de parallélisation des différentes méthodes de notre solution.
# CHAPITRE 9 CONCLUSION

Dans cette thèse, nous avons présenté de nouvelles méthodes permettant de recaler et de segmenter des objets d'intérêt dans des paires d'images multispectrales provenant de séquences vidéo synchronisées. Ces méthodes sont conçues de manière à pouvoir atteindre leur objectif sans aucune intervention humaine et sans connaissance *a priori* des objets ciblés. Cela simplifie leur intégration dans une application de vidéosurveillance automatisée.

Deux méthodes de segmentation vidéo basées sur la soustraction d'arrière-plan ont d'abord été proposées. Chaque méthode utilise une approche de modélisation non-paramétrique par pixel combinant l'utilisation de descripteurs locaux binaires et d'intensités locales dans la description des représentations de l'arrière-plan. De plus, ces méthodes utilisent différents mécanismes de rétroaction permettant d'ajuster les hyperparamètres de leurs modèles afin de mieux contrôler leur adaptabilité et leur sensibilité en fonction du dynamisme observé dans la scène. Dans sa stratégie de modélisation, la deuxième méthode propose aussi un indice de persistance, qui aide à identifier les représentations récurrentes de l'arrière-plan ; cela lui permet de beaucoup mieux détecter les objets d'intérêt immobilisés dans une scène. Les deux méthodes de segmentation proposées ont été évaluées sur un vaste ensemble de données, et il a été démontré que chacune d'entre elles surpasse des dizaines de solutions modernes, selon de nombreux critères de performance, et dans différentes catégories.

Nous avons ensuite proposé une méthode de recalage de paires d'images tirées de séquences vidéo pour des scènes planaires. Cette méthode est basée sur la mise en correspondance de points de contours obtenus à partir de cartes de segmentation. Ces points sont décrits à l'aide d'un descripteur de forme et appariés à l'aide d'une approche exhaustive. Les correspondances alors obtenues sont ajoutées et maintenues dans un réservoir temporel de manière stochastique. Ce réservoir est enfin utilisé pour estimer une transformation projective permettant de recaler tout le contenu des images analysées. Cette méthode a permis de confirmer qu'il est possible de recaler des images multispectrales à partir de formes d'objets bruitées obtenues par segmentation vidéo.

Finalement, une solution double a été proposée afin de recaler et de segmenter simultanément des paires d'images multispectrales provenant de scènes non-planaires. Cette solution est basée sur la minimisation itérative de deux fonctions d'énergie axées sur l'estimation de cartes de disparités et sur la segmentation des d'objets d'intérêt. Cette approche d'optimisation permet de résoudre le paradoxe énoncé dans la section 1.2.4, c'est à dire qu'une segmentation de qualité est nécessaire pour obtenir un recalage de qualité, et vice-versa. Les fonctions
d'énergie sont exprimées à l'aide de modèles graphiques initialisés grâce aux résultats fournis par une des méthodes de segmentation vidéo monoculaire déjà proposées. Cette solution combinée représente d'ailleurs un pipeline de traitement capable de traiter des séquences multispectrales de façon complètement automatisée.

Le développement de ces différentes méthodes a mené à de nombreuses contributions au domaine scientifique, sous forme d'articles de journaux et d'actes de conférences. L'accent mis sur la reproductibilité dans le cadre de cette thèse a aussi motivé la publication de tout le code source et de toutes les bases de données utilisées lors de nos expériences.

## 9.1 Recommandations pour travaux futurs

Dans une perspective plus générale, même s'il semble aujourd'hui que la soustraction d'arrière-plan est surpassée par les approches basées sur l'apprentissage machine dans le cadre de la segmentation vidéo, il n'existe toujours pas d'alternative fiable pour résoudre les problèmes reliés à l'évolution de l'importance des objets dans un contexte de surveillance (e.g. bagages déposés versus abandonnés, voitures stationnées versus à l'arrêt). En effet, la plupart des approches déjà publiées qui utilisent l'apprentissage profond pour détecter des objets en mouvement ne considèrent aucunement leur historique de mouvement. En pratique, l'historique de mouvement est un indice aussi important que l'apparence pour effectuer la détection d'objets d'intérêt dans un contexte d'application comme le nôtre. De futurs travaux devraient donc tenter de combiner certains principes d'analyse de processus dynamiques provenant de la théorie du contrôle (*control theory*) aux techniques d'apprentissage machine afin de développer une approche capable de déterminer la durée de vie utile d'un objet d'intérêt dans une scène complexe.

Pour ce qui est du recalage stéréo multispectral, il serait intéressant de développer une méthode capable d'apprendre automatiquement quel indice de similarité donner à deux pixels provenant d'images différentes en fonction de leur voisinage local. Une telle méthode servirait alors à définir les valeurs utilisées dans les termes unaires (*data terms*) de modèles de recalage stéréo par estimation de disparités. La phase d'apprentissage pourrait se baser sur la comparaison de vecteurs de caractéristiques, incluant des descripteurs de similarités locales (e.g. DASC, Kim et al., 2015) et des cartes de distances de contours (*distance transform maps*). Les résultats de prédiction pourraient être obtenus à l'aide d'une forêt d'arbres décisionnels structurés (*structured random forest*) tel que proposé par Dollar and Zitnick (2015). Il serait aussi envisageable de considérer l'apprentissage bout à bout (*end-to-end learning*) de ces indices de similarité à l'aide d'un réseau de neurones. Un ensemble de données permettant ce type d'apprentissage a d'ailleurs récemment été proposé par Treible et al. (2017).
Enfin, notons que les résultats de segmentation que nous obtenons grâce à nos méthodes ne contiennent pas d'identifiant unique pour chaque objet (i.e. il s'agit simplement de cartes binaires indiquant la présence d'un objet d'intérêt ou non). En d'autres termes, si deux objets d'intérêt se rapprochent jusqu'au point d'entrer en contact, ceux-ci seront détectés comme étant un seul objet par nos méthodes, et ce jusqu'à ce qu'ils se séparent à nouveau. De plus, il nous est impossible d'établir avec certitude les correspondances d'identité entre les objets détectés dans deux images consécutives. Le développement d'une méthode d'identification et d'association de fragments de formes pourrait donc être considérée dans de futurs travaux afin d'améliorer l'applicabilité de notre pipeline de traitement dans un système réel. Cette méthode pourrait être basée sur une approche de segmentation sémantique par instance, e.g. Mask-RCNN (He et al., 2017).