∎

11institutetext: Maryam Sultana, Soon Ki Jung 22institutetext: School of
Computer Science and Engineering
Virtual Reality Laboratory,
Kyungpook National University,
Daegu, Republic of Korea,
22email<EMAIL_ADDRESS><EMAIL_ADDRESS>33institutetext: Arif Mahmood
44institutetext: Department of Computer Science and Engineering
Qatar University
Doha, Qatar
44email<EMAIL_ADDRESS>55institutetext: Sajid Javed 66institutetext:
Department of Computer Science
Tissue Image Analytics Laboratory
University of Warwick
United Kingdom,
66email<EMAIL_ADDRESS>
# Unsupervised Deep Context Prediction for Background Estimation and
Foreground Segmentation

Maryam Sultana  Arif Mahmood  Sajid Javed  Soon Ki Jung

(Received: date / Accepted: date)

###### Abstract

In many high level vision applications such as tracking and surveillance,
background estimation is a fundamental step. In the past, background
estimation was usually based on low level hand-crafted features such as raw
color components, gradients, or local binary patterns. These existing
algorithms observe performance degradation in the presence of various
challenges such as dynamic backgrounds, photo-metric variations, camera
jitter, and shadows. To handle these challenges for the purpose of accurate
background estimation, we propose a unified method based on Generative
Adversarial Network (GAN) and image inpainting. It is an unsupervised visual
feature learning hybrid GAN based on context prediction. It is followed by a
semantic inpainting network for texture optimization. We also propose a
solution of arbitrary region inpainting by using center region inpainting and
Poisson blending. The proposed algorithm is compared with the existing
algorithms for background estimation on SBM.net dataset and for foreground
segmentation on CDnet 2014 dataset. The proposed algorithm has outperformed
the compared methods with significant margin.

###### Keywords:

Background subtraction Foreground detection Context-prediction Generative
Adversarial Networks

##  1 Introduction

Background estimation and foreground segmentation is a fundamental step in
several computer vision applications, such as salient motion detection Gao et
al (2014), video surveillance Bouwmans and Zahzah (2014), visual object
tracking Zhang et al (2015a) and moving objects detection Viola and Jones
(2001); Ren et al (2015); Girshick et al (2016). The goal of background
modeling is to efficiently and accurately extract a model which describes the
scene in the absence of any foreground objects. Background modeling becomes
challenging in the presence of dynamic backgrounds, sudden illumination
variations, and camera jitter which is mainly induced by the sensor. A number
of techniques have been proposed in the literature that mostly address
relatively simple scenarios for scene background modeling Bouwmans et al
(2017), because complex background modeling is a challenging task itself
specifically in handling real-time environments.

Figure 1: Estimated background images from the SBM.net dataset : Sequences in
(a) are from the category ”Basic” named ”Highway”. (b) Sequence ”Sofa” from
the category ”Intermittent Object Motion” (c) Sequence ”Chuk Square” from the
category ”Very Short”. (d) Sequence ”Bus Station” from the category ”Very
Long”. (e) Sequence ”Badminton” is also from the category ”Jitter”. In almost
all of these cases, for accurate the background estimation, the average gray-
level error (AGE) is less in our proposed algorithm as mentioned in Table 1.

To solve the problem of background subtraction, Stauffer et al. Stauffer and
Grimson (1999) and Elgammal et al. Elgammal et al (2000) presented methods
based on statistical background modeling. It starts from an unreliable
background model which identify and correct initial errors during the
background updating stage by the analysis of the extracted foreground objects
from the video sequences. Other methods proposed over the past few years also
solved background initialization as an optimal labeling problem Nakashima et
al (2011); Park and Byun (2013); Xu and Huang (2008). These methods compute
label for each image region, provide the number of the best bootstrap sequence
frame such that the region contains background scene. Taking into account
spatio-temporal information, the best frame is selected by minimizing a cost
function. The background information contained in the selected frames for each
region is then combined to generate the background model. The background model
initialization methods based on missing data reconstruction have also been
proposed Sobral et al (2015). These methods work where missing data are due to
foreground objects that occlude the bootstrap sequence. Thus, robust matrix
and tensor completion algorithms Sobral and Zahzah (2017) as well as
inpainting methods Colombari et al (2005) have shown to be suitable for
background initialization. More recently, deep neural networks are introduced
for image inpainting Pathak et al (2016). In particular, Chao Yang et al. Yang
et al (2016) used a trained CNN (Context Encoder Pathak et al (2016)) with
combined reconstruction loss and adversarial loss Goodfellow et al (2014) to
directly estimate missing image regions. Then a joint optimization framework
updates the estimated inpainted region with fine texture details. This is done
by hallucinating the missing image regions via modeling two kinds of
constraints, the global context based and the local texture based, with
convolutional neural networks. This framework is able to estimate missing
image structure, and is very fast to evaluate. Although the results are
encouraging but it is unable to handle random region inpainting task with fine
details.

In this paper we propose to predict missing image structure using inpainting
method, for the purpose of scene background initialization. We name our method
as Deep Context Prediction (DCP), because it has the ability to predict
context of a missing region via deep neural networks. Few visual results of
the proposed DCP algorithm are shown in Figure 1. Given an image, fast moving
foreground objects are removed using motion information leaving behind missing
image regions (see Figure 2 Step (1)). We train a convolutional neural network
to estimate the missing pixel values via inpainting method. The CNN model
consists of an encoder capturing the context of the whole image into a latent
feature representation and a decoder which uses this representation to produce
the missing content of the image. The model is closely related to auto-
encoders Bengio et al (2009); Hinton and Salakhutdinov (2006), as it shares a
similar architecture of encoder-decoder. Our contributions in the proposed
method are summarized as follows:

  * •

We extract the temporal information in the video frames by using dense optical
flow Liu et al (2009). After mapping motion information to motion mask, we are
able to approximately identify fast moving foreground objects. We eliminate
these objects and fill the missing region using the proposed DCP algorithm by
estimating background.

  * •

In our proposed DCP method, we train a context encoder similar to Yang et al
(2016) on scene-specific data. The network is pre-trained on ImageNet dataset
Deng et al (2009). DCP is a joint optimization framework that can estimate
context of missing regions by inpainting in central shape and later transform
this predicted information to random regions by the help of Modified Poisson
Blending (MPB) Afifi and Hussain (2015) technique. The framework is based on
two constraints, a global context based which is a hybrid GAN model trained on
scene-specific data and a local texture based which is VGG-19 network Simonyan
and Zisserman (2014).

  * •

For the purpose of foreground object detection, we first estimate background
via DCP, and later we binarize the difference of the background with the
current frame, leading to more precise detection of foreground moving objects.
This binarized difference is enhanced through morphological operations to
remove false detection and noisy pixel values.

The proposed DCP algorithm is based on context prediction, therefore it can
predict homogeneous or blurry contexts more accurately compared to other
background initialization algorithms. In case of background motion, DCP can
still estimate background by calculating motion masks via optical flow, as our
target is to eliminate foreground moving objects only. DCP is also not
effected by intermittent object motion because of the same reason mentioned
previously. In challenging weather conditions (rain, snow, fog) dense optical
flow can identify foreground moving objects, so targeting only those objects
to remove and inpaint them with background pixels makes DCP a good background
estimator. For the case of difficult light conditions DCP can estimate
background accurately because of homogeneity in the context of scenes with low
illumination.

##  2 Related Work

Over the past few years, background subtraction and foreground detection has
remained the part of many key research studies Cao et al (2016); Ortego et al
(2016); Haines and Xiang (2014); Javed et al (2016, 2015) as well as scene
background initialization Bouwmans et al (2017); Bouwmans and Zahzah (2014);
Erichson and Donovan (2016); Maddalena and Petrosino (2015); Ye et al (2015).
In the problem of background subtraction, the critical step is to improve the
accuracy of the detection of foreground. On the other hand, the task of
estimating an image without any foreground is called scene background
modeling. Many comprehensive studies have been conducted to this problem
Bouwmans et al (2017); Bouwmans and Zahzah (2014); Maddalena and Petrosino
(2015). Gaussian Mixture Model (GMM) Stauffer and Grimson (1999); Zhang et al
(2013); Zivkovic (2004); Varadarajan et al (2013); Lu (2014) is a well known
technique for background modeling. It uses probability density functions as
mixture of Gaussians to model color intensity variations at pixel level.
Recent advances in GMM include minimum spanning tree Chen et al (2017) and
bidirectional analysis Shimada et al (2013). On the other hand most GMM based
methods also suffer performance degradation in complex and dynamic scenes.

In the past, particularly for the problem of background modeling many research
studies have been conducted by using Robust Principal Component Analysis
(RPCA). Wright et al. Wright et al (2009) presented the first proposal of
RPCA-based method which has the ability to handle the outliers in the input
data. Later Candes et al. Candès et al (2011) used RPCA for background
modeling and foreground detection. Beyond good performance, RPCA-based methods
are not ideal for real-time applications because these techniques possess high
computational complexity. Moreover, conventional RPCA-based methods process
data in batch manner. Batch methods are not suitable for real-time
applications and mostly work offline. Some online and hybrid RPCA based
methods have also been presented in the literature to handle the batch problem
Javed et al (2017a) while global optimization is still a challenge in these
approaches Javed et al (2015); He et al (2012); Xu et al (2013b). Xiaowei Zhou
et al. Zhou et al (2013) proposed an interesting technique known as Detecting
Contiguous Outliers in the LOw-rank Representation (DECOLOR). Limitation of no
prior knowledge in RPCA based methods on the spatial distribution of outliers
leads to develop this technique. Outliers information is modeled in this
formulation by using Markov Random Fields (MRFs).

Figure 2: Workflow of the proposed algorithm for background estimation. Step
(1) describes the motion estimation via dense optical flow, the creation of
motion masks, image to patch conversion and object masking for center region
inpainting task. Step (2) evaluates the prediction of missing region with
context prediction hybrid GAN network. In step (3), to improve the fine
texture details of the predicted context, the output of step (2) is given to
texture network. Step (4) In the previous step it can be seen that in this
case some information of road (white lines in the middle) is being missed by
texture network so, Modified Poisson Blending technique is applied to get
final results. Step (5) we threshold the difference of the estimated
background via DCP and current frame of the video sequence. Afterwards the
thresholded difference is binarized and run through extensive Morphological
Operations to extract the foreground moving object.

Another online RPCA algorithm proposed by Jun He et al. He et al (2012) is
Grassmannian Robust Adaptive Subspace Tracking Algorithm (GRASTA). It is an
online robust subspace tracking algorithm embedded with traditional RPCA. This
algorithm operates on data which is highly sub-sampled. If the observed data
matrix is corrupted by outliers as in most cases of real-time applications,
$l^{2}$-norm based objective function is best-fit to the subspace. Hybrid
Approach: use a time window to obtain sufficient context information then
process it like a small batch. Recently S. Javed et al. Javed et al (2017b)
proposed a hybrid technique named Motion-assisted Spatiotemporal Clustering of
Low-rank (MSCL) based on RPCA approach. In this method for each data matrix,
sparse coding is applied and estimation of the geodesic subspace based
Laplacian matrix is calculated. The normalized Laplacian matrices estimated
over both distances Euclidean as well as Geodesic are embedded into the basic
RPCA framework. In 2015 Liu et al. Zhou and Tao (2011) developed a technique
called Sparse Matrix Decomposition (SSGoDec), which is capable of efficiently
and robustly estimating the low-rank part $L$ of background and the sparse
part S of an input data matrix $D=L+S+G$ with a factor of noise $G$. This
technique alternatively assigns the low-rank approximation of difference
between input data matrix and sparse matrix $(D-S)$ to $L$. Similarly it also
assigns the vice verse as well which is the sparse approximation of $(D-L)$ to
$S$. To overcome the batch constraint of RPCA based methods J. Xu et al. Xu et
al (2013a) presented a method called Grassmannian Online Subspace Updates with
Structured-sparsity (GOSUS). Although this method performs well for background
estimation problem but global optimality is still the challenging issue in
this approach. Qibin Zhao et al. Zhao et al (2016) presented a method called
Bayesian Robust Tensor Factorization for Incomplete Multiway Data (BRTF). This
method is a generative model for robust tensor factorization in the presence
of missing data and outliers. X. Guo et al. Guo et al (2014) presented a
method called Robust Foreground Detection Using Smoothness and Arbitrariness
Constraints (RFSA). In this method the authors considered the smoothness and
the arbitrariness of static background, thus formulating the problem in a
unified framework from a probabilistic perspective.
Recently, Convolutional Neural Network (CNN) based methods have also shown
significant performance for foreground detection by scene background modeling
Braham and Van Droogenbroeck (2016); Wang et al (2017); Zhang et al (2015b).
For instance, Wang et al. Wang et al (2017) proposed a simple yet effective
supervised CNN based method for detecting moving objects in static background
scenes. CNN based methods perform best in many complex scenes however, our
proposed method DCP is unsupervised therefore it do not require any labelled
data for training purposes.

##  3 Proposed Method

Our proposed background foreground separation technique has five steps. 1.)
Motion masks evaluation via dense optical flow. 2.) Estimation of missing
background pixels by Context Encoder (CE). 3.) The improvement of estimated
missing pixels texture by a multi-scale neural patch synthesis. 4.) Modified
Poisson Blending technique is applied to get final results. 5.) The foreground
objects are detected by applying threshold on the difference between the
estimated background from DCP and the current frame, which is later enhanced
by morphological operations. The work flow diagram of DCP is shown in Figure
2. Detail description of the above mentioned steps is as follows:

###  3.1 Motion Masks via Optical Flow

For the purpose of background estimation from the video frames, we have to
first identify the fast moving foreground objects. These objects are
recognized by using optical flow Liu et al (2009) which is then used to create
a motion mask. Dense optical flow is calculated between each pair of
consecutive frames in the given input video sequence $S$. Motion mask $M$ is
computed by using motion information from a sequence of video frames. Let
$S_{t}$ and $S_{t-1}$ be the two consecutive frames in $S$ at time instant $t$
and $t-1$, respectively. Considering $v^{y}_{t,p}$ be the vertical component
and $u^{x}_{t,p}$ be the horizontal component of the motion vector at position
$p$ which is computed between consecutive frames. The corresponding motion
mask, $m_{t}\in\\{0,1\\}$ will be computed as :

$m_{t,p}=\begin{cases}1,~{}~{}if~{}~{}\sqrt[]{(u^{x}_{t,p})^{2}+(v^{y}_{t,p})^{2}}<t_{h},\\\
0,~{}~{}otherwise.\end{cases}$ (1)

In the above equation, $t_{h}$ is threshold of motion magnitude. It is
computed by taking the average of all pixels in the motion field. Selection of
the threshold $t_{h}$ is adapted in such a way that all pixels in $S$
consisting of motion greater than $t_{h}$ belongs to the foreground. In order
to avoid noise in the background, threshold $t_{h}$ is selected to be large
enough.

###  3.2 Background Pixels Estimation via Context Prediction

Given image patches from a video with missing regions such as foreground
object regions, we predict context via context encoder Pathak et al (2016).
The context encoder is a hybrid GAN model which is trained on the basis of
convolutional neural network to estimate the missing pixel values. It consists
of two parts: an encoder which captures the context of a given image patch
into a compact latent feature space. While the other part is a decoder which
uses encoded representation to produce missing image patch content. Overall
architecture of context encoder is a simple encoder-decoder pipeline.

The encoder is derived from the AlexNet Krizhevsky et al (2012), however the
network is not trained for classification, rather it is trained for context
prediction. Training is performed on ImageNet as well as using scene-specific
video sequences patches. In order to learn an initial context prediction
network, we train a regression network $F$ to get response $F(x_{m})$, where
$x_{m}$ is the input image patch $x$ pixel-wise multiplied by object mask
$m_{o}$: $x_{m}=x\odot m_{o}$. Since $m_{o}$ is a binary mask with fix central
region which covers the whole object in motion mask.

The patch $x_{m}$ with a missing region $H$, is input to Context Network. The
response $F(x_{m})$ of trained context network is estimated via joint loss
functions to estimate the background $x_{b}$ in the missing region $H$. We
have experimented with two joint loss functions including reconstruction loss
$L_{rec}$ and adversarial loss $L_{adv}$ Pathak et al (2016). The
reconstruction loss $L_{rec}$ is defined as:

$L_{rec}(x_{m},x_{b},H)=||F(x_{m})-C(x_{b},H)||_{2}^{2}.$ (2)

The adversarial loss is given as:

$\begin{split}L_{adv}(x_{m},x_{b},H)=\max\limits_{D}~{}E_{x_{m}\in\chi_{m}}[log(D(C(x_{b},H)))\\\
+log(1-D(F(x_{m})))],\end{split}$ (3)

where $D$ is the adversarial discriminator and $C(\cdot)$ defines the
operation of extracting a sub-image in the central region during inpainting
process. Overall loss function is a linear combination of both reconstruction
and adversarial losses.

$L=\eta L_{rec}(x_{m},x_{b},H)+(1-\eta)L_{adv}(x_{m},x_{b},H),$ (4)

where $\eta$ is a relative weight of each loss function.

###  3.3 Texture Optimization of Estimated Background

In the last section, we estimated a background patch $x_{b}$ via Context
Encoder (CE). But the estimated context still contains irregularities and
blurry texture at low resolution of the image patch. To solve this blurry
estimated context problem for high resolution inpainting with fine details, we
use texture network at three-level pyramid of image patches. This network
optimizes over three loss terms: the predicted context term initialized by CE,
the local texture optimization term, and the gradient loss term. The context
prediction term captures the semantics including global structures of the
image patches. The texture term maps the local statistics of input image patch
texture, and the gradient loss term enforces the smoothness between the
estimated context and the original context. For three-level pyramid approach
the test image patch is assumed to be always cropped to $512\times 512$ with a
$256\times 256$ hole in the center at fine level. However with step-size two,
downsizing to the coarse level as $128\times 128$ size image patch with a
$64\times 64$ missing region is initialized by CE. Afterwards context of
missing region is estimated in a coarse-to-fine manner. At each scale, the
joint optimization is performed to update the missing region and then
upsampling is done to initialize the joint optimization which sets the context
constraint for the next scale of image patch. This process repeats this until
the joint optimization is completed at the fine level of the pyramid. The
texture optimization term is computed using the $VGG-19$ Simonyan and
Zisserman (2014) which is pre-trained on ImageNet.

Once the context is initialized by CE at the coarse scale, we use the output
$F(x_{m})$ and the original image as the initial context constraint for joint
optimization. Let $x_{o}$ be the original image patch with missing region
filled with the CE. Upsampled version of $x_{o}$ are used as the
initialization for joint optimization at the fine scales.

For the input image patch $x_{o}$ we would like to estimate the fine texture
of the missing region. The region corresponding to $x_{o}$ in the feature map
of $VGG-19$ network is $\psi(x_{o})$ and $\psi(H)$ is the feature map
corresponding to the missing region. For texture optimization $C(\cdot)$ also
defines the operation of extracting a sub-feature-map in a rectangular region,
i.e. the context of $\psi(x_{o})$ within $\psi(H)$ is returned by
$C(\psi(x_{o}),H)$.

The optimal solution for accurate reconstruction of the missing content is
obtained by minimizing the following objective function at each scale
$i=1,2...,n$.

$\begin{split}\hat{x}^{i+1}=arg~{}min~{}E_{CE}(C(x_{o},H),C(x_{o}^{i},H))\\\
+\gamma E_{T}(\psi_{T}(x_{o}),\psi(H)+\delta\Pi(x_{o}),\end{split}$ (5)

where $C(x_{o}^{1},H)=F(x_{o}),~{}\psi_{T}(.)$ represents a feature maps in
the texture network $T$ at an intermediate layer, $\gamma$ and $\delta$ are
weighting reflecting parameters. Yang et al (2016). The first term $E_{CE}$ in
equation (5) is context constraint which is defined by the difference between
the previous context prediction and the optimization result:

$E_{CE}(C(x_{o},H),C(x_{o}^{i},H))=||C(x_{o},H)-C(x_{o}^{i},H)||^{2}_{2}.$ (6)

The second term $E_{T}$ in equation (5) handles the local texture constraint,
which minimizes the inconsistency of the texture appearance outside and inside
the missing region. We first select a single feature layer or a combination of
different feature layers in the texture network $T$, and then extract its
feature map $\psi_{T}$. In order to do texture optimization, for each query
local patch $P$ of size $w\times w\times c$ in the missing region $\psi(H)$,
our target is to find the most similar patch outside the missing region, and
calculate loss as mean of the query local patch and its nearest neighbor
distances.

$\begin{split}E_{T}(\psi_{T}(x_{o}),H)=\\\
\frac{1}{|\psi(H)|}\sum\limits_{i\in\psi(H)}||C(\psi_{T}(x_{o}),P_{i})-C(\psi_{T}(x_{o}),P_{np(i)})||^{2}_{2},\end{split}$
(7)

In the above equation, the local neural patch centered at location $i$ is
$P_{i}$, the number of patches sampled in the region $\psi(H)$ is given by
$|\psi(H)|$, and $np(i)$ is the calculated as:

$np_{i}=\arg\min\limits_{j\in n(i)\wedge j\notin
H^{\psi}}||C(\psi_{T}(x),P_{i})-C(\psi_{T}(x),P_{j})||^{2}_{2},$ (8)

where $n(i)$ is the set of neighboring locations of $i$ excluding the overlap
with the missing unknown region $\psi(H)$. We also add the gradient loss term
to encourage smoothness in texture optimization Yang et al (2016):

$\begin{split}\Pi(x_{o})=\sum\limits_{j,k}((x_{o}(j,k+1)-x_{o}(j,k))^{2}+\\\
(x_{o}(j+1,k)-x_{o}(j,k))^{2}),\end{split}$ (9)

###  3.4 Blending of Estimated and Original Textures

After the texture optimization, some information around the central region
during inpainting process is being missed or removed due to rectangular shaped
region as shown in figure 2. In order to change the rectangular shaped
predicted context to the irregular shaped region, Modified Poisson Blending
technique (MPB) Afifi and Hussain (2015) is used. It is based on Poisson image
editing for the purpose of seamless cloning. The MPB technique has three
steps, the first step, uses the source image which is inpainted image via DCP
as a known region and the target image which is original image containing
foreground as an unknown region. Afterwards it requires motion mask by optical
flow around the interested object in the source image for solving Poisson
equation Pérez et al (2003) under gradient field and predefined boundary
condition. MPB technique has few modifications to Poisson image editing
technique that eliminates the bleeding problems in the composite image by
using Poisson blending with fair dependency of source which is inpainted
context and target pixels which are original image pixels. In the next step,
MPB technique uses the composite image as unknown region and the target image
with foreground object as a known region. After applying Poisson blending
algorithm, we get another composite image which will be used in third step. To
reduce bleeding artifacts, MPB technique generate an alpha mask that is used
to combine both composite images from previous steps to get final image that
is free from color bleeding. In practice this method helps in discarding the
useless information which came along rectangular region inpainting process.

Figure 3: Qualitative results of the proposed method. (a) 7 images from the
input video sequences, (b) Ground truth, (c) estimated background model by the
proposed DCP method, (d) RFSA, (e) GRASTA, (f) BRTF, (g) GOSUS, (h) SSGoDec,
(i) DECOLOR. From top to bottom: each input sequence is selected from
different categories. (1)sequence ”Fall” from ”Background Motion”, (2)
”Skating” from ”Basic”, (3)”StreetCornerAtNight” from ”Basic”, (4) ”WetSnow”
from ”Basic”, (5) ”Pedestrians” from ”Very Short”, (6) ”Snowfall” from ”Very
Short”, and (7) ”SideWalk” from ”Jitter”.

###  3.5 Foreground Detection

In this work we mainly focus on the problem of background initialization.
However, in this section we extend our work to foreground detection as well.
Thus we are able to compare our work with foreground detection algorithms as
well, in addition to the work on background initialization only. For the
purpose of foreground detection, we threshold the difference of the estimated
background via DCP and the current frame of the video sequence. The difference
is threshold and binarized and processed through Morphological Operations (MO)
with suitable Structuring Elements (SE). Thus the work done in this section
may be considered as post processing.

These operations first include opening operation of an image which is erosion
followed by the dilation with the same SE:

$I\circ SE=(I\ominus SE)\oplus SE,$ (10)

where $I$ is the binarized difference, $\ominus$ and $\oplus$ denote erosion
and dilation respectively. Afterwards, closing operation is performed on this
image. It is in reverse way, that is dilation followed by erosion with same
SE, but different from SE used in the opening operation.

$I^{\prime}\bullet SE=(I^{\prime}\oplus SE)\ominus SE.$ (11)

Now here $I^{\prime}$ is the difference image from equation (10), $\oplus$ and
$\ominus$ denote dilation and erosion respectively. Successive opening and
closing of the binarized difference frame with proper SE leads us to separate
the foreground objects from the background. The choice of the SE is very
crucial in successive opening and closing of the binarized difference frame as
it may lead to false detection if not selected according to the shape of the
objects in the video frames. The MO not only fills the missing regions in
thresholded difference but also removes the unconnected pixels values of
background which are considered to be noise in foreground detection process.

##  4 Experiments

Our background estimation and foreground detection techniques are based on
inpainting model similar to Yang et al (2016). We trained the context
prediction model additionally with scene-specific data in terms of patches of
size $128\times 128$ for $3$ epoches. The texture optimization is done with
$VGG-19$ network pre-trained on ImageNet for classification. The frame
selection for inpainting the background is done by summation of pixel values
in the forward frame difference technique. If the sum of difference pixels is
small, then current frame is selected.

We evaluate our proposed approach on two difference datasets, including Scene
Background Modeling (SBM.net)111http://scenebackgroundmodeling.net/ for
background estimation and Change Detection 2014 Dataset (CDnet2014)Wang et al
(2014) for foreground detection. On both datasets our proposed algorithm has
outperformed existing state of the art algorithms with a significant margin.

###  4.1 Evaluation of Deep Context Prediction (DCP) for Background Estimation

We have selected all videos out of $7$ categories from SBM.net dataset as
shown in Table 1. Every category in SBM.net dataset has challenging video
sequences for background modeling. In this experiment, results are compared
with $6$ state-of-the-art methods, including RFSA Guo et al (2014), GRASTA He
et al (2012), BRTF Zhao et al (2016), GOSUS Xu et al (2013a), SSGoDec Zhou and
Tao (2011), and DECOLOR Zhou et al (2013) using implementations of the
original authors. Background estimation models are compared using Average
Gray-level Error (AGE), percentage of Error Pixels (pEPs), Percentage of
Clustered Error Pixels (pCEPs), Multi Scale Structural Similarity Index
(MSSSIM), Color image Quality Measure (CQM), and Peak-Signal-to-Noise-Ratio
(PSNR) Maddalena and Petrosino (2015). For best performance the aim is to
minimize AGE, pEPs, and pCEPs while maximizing MSSSIM, PSNR, and CQM (Fig. 5).
The detail description of results with respect to each category is as follows:

Category: Background Motion contains $6$ video sequences. In this category the
proposed DCP algorithm achieved best performance among all the compared
methods. The performance of DECOLOR, SSGoDec, RFSA, GRASTA and BRTF has
remained quite similar with minimal difference in AGE as shown in table 1.
GOSUS has the highest average gray level error among all the compared methods.
Targeting only foreground objects to be eliminated and filled with background
pixel values via inpainting method makes DCP to perform better in this
category as compared to all other methods. The visual results are shown in
Figure 3, 1st row.

Table 1: The AGE scores over SBM.net dataset for the six state of the art
methods compared with DCP for background subtraction. The best AGE score for
each video sequence is shown in blue, and the best average AGE scores for each
category is shown in red.

Category | Videos | AGE |  |  |  |  |  |
---|---|---|---|---|---|---|---|---
|  | DCP | RFSA Guo et al (2014) | GRASTA He et al (2012) | BRTF Zhao et al (2016) | GOSUS Xu et al (2013a) | SSGoDec Zhou and Tao (2011) | DECOLOR Zhou et al (2013)
Background Motion | Canoe: | 6.3250 | 14.8805 | 14.9438 | 14.8798 | 14.9677 | 14.9464 | 13.6732
| Advertisement Board: | 2.3378 | 3.4762 | 3.4812 | 3.4640 | 3.4733 | 3.4742 | 3.6604
| Fall: | 19.0737 | 24.3364 | 24.6026 | 24.4283 | 24.5935 | 24.5702 | 24.8117
| Fountain 01: | 9.6775 | 5.7150 | 5.7539 | 5.7383 | 5.7750 | 5.7442 | 6.2959
| Fountain 02: | 14.0579 | 7.3288 | 7.0811 | 7.3307 | 7.0867 | 7.0801 | 6.4137
| Overpass: | 6.4089 | 14.7162 | 14.7489 | 14.7183 | 14.7614 | 14.7369 | 8.6909
Average AGE: |  | 9.6468 | 11.7422 | 11.7686 | 11.7599 | 12.1183 | 11.5934 | 11.6340
Basic: | 511: | 3.5786 | 5.0972 | 6.1220 | 4.9151 | 5.2681 | 6.6025 | 7.5225
| Blurred: | 2.1041 | 4.9735 | 47.3112 | 4.9527 | 105.1528 | 51.9253 | 4.7345
| Camouflage FG Objects: | 2.5789 | 4.7951 | 5.0457 | 4.7411 | 4.3364 | 5.9418 | 4.4703
| Complex Background : | 6.3453 | 6.8593 | 6.2202 | 6.8868 | 6.1947 | 6.1828 | 5.6215
| Hybrid : | 4.2021 | 6.1795 | 6.5101 | 5.9201 | 6.4777 | 5.8003 | 6.6420
| IPPR2: | 6.8575 | 6.9256 | 6.9256 | 6.9249 | 6.9256 | 6.9256 | 6.9258
| I_SI_01: | 4.1119 | 3.2955 | 3.3333 | 3.2895 | 3.2895 | 3.3518 | 2.5187
| Intelligent Room: | 5.9152 | 3.3890 | 3.4871 | 3.3546 | 3.5144 | 3.4951 | 3.3934
| Intersection : | 2.6911 | 13.9704 | 13.9690 | 13.9752 | 13.9720 | 13.9726 | 13.1152
| MPEG4_40: | 3.9292 | 4.3346 | 5.6052 | 4.2712 | 5.5649 | 5.6711 | 3.7329
| PETS2006: | 6.5818 | 4.7506 | 5.5686 | 4.7573 | 5.4968 | 5.6115 | 5.5221
| Fluid Highway: | 4.3549 | 12.1362 | 9.3360 | 10.1921 | 9.3345 | 9.2739 | 10.1913
| Highway : | 4.8638 | 4.0454 | 4.1048 | 4.0381 | 4.0901 | 4.0941 | 4.0762
| Skating : | 5.855 | 26.0429 | 25.9610 | 26.1047 | 26.0922 | 25.9509 | 25.7092
| Street Corner at Night: | 9.5308 | 10.2057 | 10.1120 | 10.1791 | 10.0807 | 10.1170 | 12.9509
| wetSnow : | 12.3658 | 37.6461 | 37.7272 | 38.1130 | 37.7126 | 37.7054 | 38.6056
Average AGE: |  | 5.3666 | 9.6654 | 12.3337 | 9.5385 | 15.8439 | 12.6639 | 9.7332
Intermittent Motion: | AVSS2007: | 7.3008 | 21.3837 | 21.3776 | 21.3957 | 21.3896 | 21.3746 | 35.5689
| CaVignal : | 13.9885 | 1.6927 | 1.7240 | 1.7131 | 1.7379 | 1.7182 | 1.3504
| Candela m1.10: | 8.6512 | 3.8845 | 3.8889 | 3.9102 | 3.8977 | 3.9043 | 5.4697
| I_CA_01: | 16.8939 | 15.4821 | 15.4496 | 15.4985 | 15.4312 | 15.4297 | 14.6558
| I_CA_02: | 13.4803 | 9.9255 | 6.6146 | 9.8810 | 6.2029 | 7.1204 | 9.8810
| I_MB_01: | 9.2338 | 8.1882 | 7.3860 | 8.0478 | 7.1827 | 7.6550 | 11.5584
| I_MB_02: | 9.5397 | 8.6324 | 8.6360 | 8.6361 | 8.6307 | 8.6353 | 3.6324
| Teknomo: | 4.8436 | 6.7690 | 6.7382 | 6.7388 | 6.7315 | 6.7312 | 6.7310
| UCF-traffic: | 4.1126 | 33.0448 | 33.0449 | 33.0464 | 33.0426 | 33.0432 | 32.9837
| Uturn: | 7.4448 | 23.4947 | 23.5190 | 23.4939 | 23.5187 | 23.5163 | 21.2872
| Bus Station: | 8.9723 | 3.5451 | 3.5409 | 3.5513 | 3.5525 | 3.5474 | 6.5359
| Copy Machine: | 7.3156 | 8.1650 | 8.2640 | 8.1819 | 8.2836 | 8.2483 | 4.9248
| Office: | 16.6488 | 9.2656 | 9.1716 | 9.2710 | 9.1694 | 9.2024 | 3.3454
| Sofa: | 4.9927 | 4.2697 | 4.2711 | 4.2637 | 4.2708 | 4.2616 | 4.1817
| Street Corner: | 8.9535 | 7.6411 | 7.7734 | 7.6425 | 7.8462 | 7.6832 | 27.5613
| Tramstop: | 7.1293 | 2.4173 | 2.4268 | 2.4282 | 2.4483 | 2.4153 | 2.4079
Average AGE: |  | 9.3438 | 10.4876 | 10.2392 | 10.4812 | 10.2085 | 10.2804 | 12.0047
Jitter: | CMU: | 8.1714 | 7.3476 | 6.9292 | 7.3197 | 7.7878 | 7.6034 | 6.8975
| I_MC_02: | 9.0549 | 15.7418 | 13.9334 | 15.4235 | 15.4017 | 15.6302 | 15.9440
| I_SM_04: | 4.5583 | 3.3464 | 2.5355 | 3.0923 | 3.7768 | 4.3339 | 4.1406
| O_MC_02: | 12.6371 | 16.3119 | 17.3914 | 16.6375 | 16.0443 | 16.4781 | 12.3657
| O_SM_04: | 7.7459 | 12.0224 | 12.0262 | 13.2998 | 15.6505 | 13.9053 | 15.6806
| Badminton: | 14.2284 | 16.9398 | 17.1787 | 16.4044 | 16.6059 | 14.2486 | 6.6003
| Boulevard: | 11.5450 | 19.4259 | 15.4555 | 16.6356 | 20.0932 | 16.9604 | 23.8209
| Side Walk: | 14.9378 | 24.7621 | 24.1964 | 22.8313 | 16.5027 | 15.8949 | 18.4447
| Traffic: | 21.3232 | 7.5524 | 24.5624 | 8.6431 | 7.5449 | 6.7522 | 26.5434
Average AGE: |  | 11.5780 | 13.7167 | 14.9121 | 13.3652 | 13.2675 | 12.4230 | 14.4931
Very Short: | CUHK Square: | 2.8429 | 5.4994 | 4.8949 | 5.8176 | 5.2220 | 5.0429 | 6.2694
| Dynamic Background : | 13.7524 | 7.7233 | 7.8492 | 7.5747 | 7.9276 | 7.3880 | 7.3760
| MIT: | 3.5838 | 4.9527 | 5.7849 | 4.4991 | 5.8378 | 5.2764 | 4.9524
| Noisy Night : | 3.9116 | 6.1301 | 5.5040 | 6.3509 | 5.3378 | 5.6906 | 5.4483
| Toscana: | 11.5422 | 8.7331 | 6.4773 | 7.4022 | 6.8142 | 6.3869 | 7.4014
| Town Center : | 4.1427 | 4.4226 | 4.4247 | 4.2329 | 3.8596 | 3.9657 | 4.4225
| Two Leave Shop1cor: | 10.0183 | 4.0515 | 4.0172 | 4.2124 | 3.9300 | 3.8685 | 4.0503
| Pedestrians: | 5.0736 | 5.0318 | 4.9441 | 4.9996 | 4.9974 | 4.9682 | 5.0225
| People In Shade: | 6.9680 | 9.0900 | 6.5455 | 10.7783 | 3.6842 | 9.3889 | 10.7812
| SnowFall: | 5.2768 | 32.8871 | 31.0542 | 31.2511 | 31.8320 | 30.3902 | 34.2603
Average AGE: |  | 6.7112 | 8.8522 | 8.1496 | 8.7119 | 7.9443 | 8.2366 | 8.9984
Illumination Changes: | Camera Parameter: | 6.2206 | 75.1204 | 6.1471 | 6.1126 | 6.1389 | 6.1475 | 45.2837
| Dataset3 Camera1 : | 14.5708 | 23.3046 | 22.0816 | 22.5116 | 22.0816 | 22.0816 | 2.8850
| Dataset3 Camera2: | 18.7047 | 6.5041 | 5.7156 | 5.8965 | 5.7156 | 5.7156 | 3.7555
| I_IL_01: | 7.4329 | 8.3048 | 23.6585 | 23.5775 | 23.6585 | 23.6585 | 22.4594
| I_IL_02: | 19.3833 | 8.4842 | 7.5423 | 7.4007 | 7.5423 | 7.5423 | 5.1225
| Cubicle: | 11.4636 | 26.1490 | 19.4842 | 31.2116 | 19.4842 | 19.4842 | 13.0519
Average AGE: |  | 12.9627 | 24.6445 | 14.1049 | 16.1184 | 14.1035 | 14.1049 | 15.4263
Very Long: | Bus Stop Morning : | 3.1641 | 5.6652 | 5.7055 | 5.6396 | 5.6739 | 5.6794 | 5.7419
| Dataset4 Camera1: | 6.7405 | 3.1857 | 3.1886 | 3.1876 | 3.1794 | 3.1948 | 3.1661
| Ped And Storrow Drive: | 8.5110 | 5.5780 | 5.0913 | 5.4323 | 5.3057 | 5.2445 | 4.5065
| Ped And Storrow Drive3 : | 2.8661 | 3.5503 | 3.6693 | 3.5531 | 3.6100 | 3.5598 | 3.9688
| Terrace : | 6.0016 | 19.9480 | 18.9514 | 19.1109 | 19.0254 | 19.0258 | 10.2339
Average AGE: |  | 5.4567 | 7.5854 | 7.3212 | 7.3847 | 7.3589 | 7.3409 | 5.5234
Average AGE of all categories: |  | 8.7237 | 13.2359 | 11.9362 | 11.9229 | 12.1183 | 11.5934 | 11.6340

Figure 4: Performance comparison of each method on the basis of AGE according
to each category on SBM.net dataset.

Category: Basic contains $16$ video sequences (Table 1). In almost all video
sequences our proposed approach DCP performed well. DCP achieved an average
AGE of $5.367$ (visual results in Figure 4) among all the compared methods
because this category contains relatively simple scenes for background
estimation. It can be seen in the Table 1, that RFSA, BRTF and DECOLOR almost
achieved equal and second lowest score of AGE but GOSUS and GRASTA achieved a
bit bit higher values of AGE. GOSUS suffered performance degradation among all
compared methods. In terms of qualitative analysis DCP estimated better
background as compared to all the methods, results are shown in the Figure 3,
(c), (d) and (e). The reason is that the context for video sequences of ‘Wet-
snow’, ‘Skating’ and ‘Street Corner at Night’ is homogeneous in the whole
frame as background pixel values. This key aspect is favorable for our
proposed method.

Category: Intermittent Motion contains $16$ video sequences (Table 1). This
category has video sequences which contain ghosting artifacts in the detected
motion. DCP performed well in this category by achieving lowest AGE score of
$9.344$ among all compared techniques. Methods including RFSA, GRASTA, BRTF,
GOSUS and SSGoDec achieved almost equal and higher score of AGE (Figure 4 and
Table 1). DECOLOR has the highest error rate in background estimation for this
category. The ghosting artifacts pose big challenge for all algorithms as the
foreground becomes the part of background, resulting in failure of accurate
background recovery model.

Category: Jitter contains $9$ video sequences (Table 1). DCP achieved lowest
average gray level error among all the compared methods due to the fact that
camera jitter contains videos sequences with blurry context and such context
is easy to predict by our proposed method. RFSA, BRTF and GOSUS achieved
higher AGE score in this category while GRASTA and DECOLOR showed performance
degradation among all compared methods. It can be seen in Figure 1 (e) that
GRASTA was not able to recover clean background while DCP estimated it
accurately. SSGoDec is also able to recover clean background as shown in
Figure 3 (h) with low AGE score.

Category: Very Short contains $10$ video sequences each having only few frames
(Table 1). DCP achieved the lowest AGE score in this category too. GOSUS also
performed well and achieved the second lowest AGE score as shown in Table 1.
However RFSA, GRASTA, BRTF, DECOLOR and SSGoDec achieved almost equal score of
AGE among all the compared methods. In terms of qualitative analysis, it can
be seen in Figure 3 (c) that for instance, the video sequence ‘SnowFall’, DCP
achieved the lowest score of AGE. It is due to the fact that in case of bad
weather snow or rain the context of the videos gets blurry which is rather
easy for DCP to estimate.

Category: Illumination Changes contains $6$ video sequences (Table 1). This
category pose a great deal of challenge for all the methods. DCP managed to
get lowest AGE score among all the compared methods due to the fact that
context prediction in low light and with less sharp details is rather
favorable condition for our proposed method. GRASTA, GOSUS and SSGoDec also
performed well and achieved second lowest AGE score among all compared
methods. BRTF and DECOLOR almost get equal AGE score. RFSA has the highest
error rate as shown in Table 1, because of the spatiao-temporal smoothness of
foreground, and the correlation of background constraint.

Figure 5: Average performance comparison of DCP on each metric with $6$ state-
of-the-art methods on the $7$ categories of SBM.net dataset. (a) AGE (b) pCEPs
and (c) pEPs, (minimum is best). (d) CQM (e) PSNR (f) MSSSIM, (maximum is
best).

Category: Very Long contains $5$ video sequences containing thousands of
frames (Table 1). Among all the compared methods only DCP and DECOLOR
performed well with the lowest AGE score of $5.457$ and $5.524$ respectively.
However all methods except DCP and DECOLOR achieved nearly equal score of
average gray level error for background estimation (Table 1). For instance in
the case of DCP, video sequence ”Bus Stop Morning” achieved the lowest AGE
score of $3.164$ among all compared methods, its visual result is shown in
Figure 1 (d).

####  4.1.1 Overall Performance Comparison of DCP for Background Estimation

Upon averaging the results from all the 7 categories, DCP achieved an average
gray level error to be $8.724$ which is minimum among all the compared methods
as shown in Figure 5 (a). For fair comparison and evaluation other than AGE,
results of $5$ other metrics have also been calculated. In Figure 5 (b), pCEPS
which is Percentage of Clustered Error Pixels is minimum for DCP among all
compared methods. BRTF, GOSUS and SSGoDec has higher value than DCP. The other
three methods GRASTA, RFSA and DECOLOR achieved almost equal and highest score
of pCEPs. The metric pEPs which is basically Percentage of Error Pixels, is
aimed to get minimum score for accurate background estimation (Figure 5 (c)).
Among all the compared methods only DCP achieved the minimum score while all
compared methods showed minimal difference in their pEPs score. In Figure 5
(d) CQM: (Color image Quality Measure), DCP achieved the maximum (best) score
for this metric. It can also be seen in the visual results ( Figure 3 (d),
(e), (f), (g), (h) and (i)) that color quality of some background images
extracted by compared methods, is different from input images, ground truths
and backgrounds estimated by DCP. Due to this reason all compared methods have
different scores of CQM metric. In Figure 5 (e), PSNR: (Peak-Signal-to-Noise-
Ratio) and Figure 5 (f) MSSSIM: (MultiScale Structural Similarity Index)
should have a highest value for best performance and DCP achieved it
efficiently. The proposed DCP algorithm achieved best scores in all mentioned
metrics, as compared to the $6$ methods.

Table 2: Comparison of $6$ state of the art methods with the proposed DCP
algorithm by using $F$ measure on CDnet2014 dataset. The first highest and the
second highest scores for each category is shown in red and blue color
respectively.

Categories | MSSTBM Lu (2014) | GMM-Zivkovic Zivkovic (2004) | CP3-Online Liang et al (2015) | GMM-Stauffer Stauffer and Grimson (1999) | KDE-ElGammal Elgammal et al (2000) | RMOG Varadarajan et al (2013) | DCP
---|---|---|---|---|---|---|---
Baseline | 0.8450 | 0.8382 | 0.8856 | 0.8245 | 0.9092 | 0.7848 | 0.8187
Camera Jitter | 0.5073 | 0.5670 | 0.5207 | 0.5969 | 0.5720 | 0.7010 | 0.8376
Shadow | 0.8130 | 0.7232 | 0.6539 | 0.7156 | 0.7660 | 0.8073 | 0.7665
Dynamic Background | 0.5953 | 0.6328 | 0.6111 | 0.6330 | 0.5961 | 0.7352 | 0.7757
Thermal | 0.5103 | 0.6548 | 0.7917 | 0.6621 | 0.7423 | 0.4788 | 0.8212
Intermittent Object Motion | 0.4497 | 0.5325 | 0.6177 | 0.5207 | 0.4088 | 0.5431 | 0.5979
Bad Weather | 0.6371 | 0.7406 | 0.7485 | 0.7380 | 0.7571 | 0.6826 | 0.8212
Average | 0.6225 | 0.6736 | 0.7010 | 0.6771 | 0.6833 | 0.6761 | 0.7620

###  4.2 Evaluation of Deep Context Prediction (DCP) for Foreground Detection

We have selected $7$ categories from CDnet2014 Wang et al (2014) dataset. The
results are compared with $6$ state-of-the-art methods, including MSSTBM Lu
(2014), GMM-Zivkovic Zivkovic (2004), CP3-Online Liang et al (2015), GMM-
Stauffer Stauffer and Grimson (1999), KDE-Elgammal Elgammal et al (2000) and
RMoG Varadarajan et al (2013) by using implementations of the original
authors. Foreground detection is compared using Average $F$ measure across all
the video sequences within each category. The metrics to calculate $F$ measure
are as follows :

$Re=\frac{T_{p}}{T_{p}+F_{n}},$ (12) $Sp=\frac{T_{n}}{T_{n}+F_{p}},$ (13)
$FNR=\frac{F_{n}}{T_{p}+F_{n}},$ (14)
$PWC=100\times(\frac{F_{n}+F_{p}}{T_{p}+F_{n}+F_{p}+T_{n}}),$ (15)
$Pre=\frac{T_{p}}{T_{p}+F_{p}},~{}~{}and$ (16) $F=\frac{2(Pre\times
Re)}{Pre+Re},$ (17)

where $T_{p}$ is True positives, $T_{n}$ is True negatives, $F_{p}$ is False
positives, $F_{n}$ is False negatives, $Re$ is Recall, $Sp$ is Specificity,
$FNR$ is False Negative Rate, $PWC$ Percentage of Wrong Classifications, $Pre$
is Precision and $F$ is F-Measure. Following is the detailed explanation of
results on 7 categories of CDnet2014 dataset.

Category: Baseline in CDnet2014 dataset contains $4$ video sequences. The
average F measure score across all $4$ video sequences is shown in Table 2.
All the compared methods including DCP achived more than $0.8$ score for this
category (Table 2). However KDE-ElGammal successfully got the highest score
leaving CP3-Online on second position among all compared methods. Although DCP
achieved more than $0.8$ F measure score but still it was not able to beat
KDE-ElGammal method due to the fact that successive opening and closing on
noisy video frames lead to false detection. Visual results are shown in Figure
6 first row.

Category: Camera Jitter also contains $4$ video sequences. DCP achieved the
highest F measure among all the compared methods, as shown in Table 2. It is
due to the fact that blurry context because of camera jitter is easy to
predict by our proposed method for accurate background estimation. Afterwards
the binarized thresholded difference of the estimated background and current
frame erodes the noisy pixels of background in successive opening and closing
operations. This leads us to get accurate foreground detection with less
missing pixel values of foreground objects (Figure 6: $3^{rd}$ row). RMOG also
performed well in this category and achieved the second best score among all
compared methods.

Figure 6: Qualitative results of the proposed DCP method: (a) Seven images
from the input video sequences of Cdnet2014 dataset, (b) Ground truth, (c)
Foreground detected by the proposed DCP method, (d) MSSTBM, (e) GMM-Zivkovic,
(f) CP3-Online, (g) GMM-Stauffer, (h) KDE-ElGammal, (i) RMOG. From top to
bottom: each input sequence is selected from different category: (1) sequence
‘Highway’ from ‘Baseline’, (2) ‘Snowfall’ from ‘Bad Weather’, (3) ‘Boulevard’
from ‘Camera Jitter’, (4) ‘Boats’ from ‘Dynamic Background’, (5) ‘Sofa’ from
‘Intermittent Object Motion’, (6) ‘Copy Machine’ from ‘Shadow’, and (7)
‘Library’ from ‘Thermal’.

Category: Shadow contains $6$ video sequences. MSSTBM achieved the highest
score among all compared methods with RMOG as second best score. This category
posed challenge to our proposed method as sometimes shadows got replicated in
the context prediction algorithm which generates errors in background
estimation as well as foreground detection. In our proposed method the opening
and closing of the binarized thresholded difference frame successfully filled
the missing values in the foreground detection as shown in the Figure 6:
$6^{th}$ row as compared to all methods. This leads DCP to achieved $3^{rd}$
best F measure in this category.

Category: Dynamic Background also contains $6$ video sequences. DCP achieved
the highest averaged F measure among all the compared methods, see Table 2.
The homogeneous context in video sequences of this category is a favorable
condition for our proposed method. RMOG also performed well and achieved the
second best F measure score. The qualitative results are as shown in Figure 6.
It can be seen in the visual results that successive opening and closing with
a suitable SE removed the noisy pixel values of moving background.

Category: Thermal contains $5$ video sequences that have been captured by far-
infrared camera. DCP achieved highest averaged F measure score among all
compared methods, while CP3-Online is the second best. It is because of the
same reason as explained in previous category. The homogeneous context is one
of the major key for accurate background estimation of DCP, and it leads to
noise-less foreground detection. Figure 6: $7^{th}$ row shows that all methods
including DCP accurately detected foreground object except RMOG which contains
missing pixel values within detected foreground object.

Category: Intermittent Object Motion contains $6$ video sequences with
scenarios known for causing “ghosting” artifacts in the detected motion, i.e.,
objects move, then stop for a short while, after which they start moving
again. DCP achieved the highest average F measure score in this category,
while RMOG is the second best among all the compared methods. The main reason
behind this is, our proposed approach does not contain any motion-based
constraints for moving foreground objects. Since all the compared methods
contain constraints on the motion of the foreground objects, which if violated
lead to false detection and low F measure score. The visual results in Figure
6: $5^{th}$ row show that the foreground objects vanish if motion-based
constraints are violated.
Category: Bad Weather contains $4$ video sequences captured in challenging
winter weather conditions, i.e., snow storm, snow on the ground, and fog. DCP
achieved highest averaged F measure among all compared methods while KDE-
ELGammal is the second best method. This category is another example of
homogeneous context in video sequences. It can be seen in the visual results,
Figure 6: $2^{nd}$ row, DCP estimated the almost accurate foreground object
with no unconnected noisy pixels of background as compared to the other
methods.

####  4.2.1 Overall Performance Comparison of DCP for Foreground Detection

Table 2 shows that DCP achieved the highest average F measure score over all
categories. CP3-Online is the $2^{nd}$ best algorithm. GMM-Stauffer, GMM-
Zivkovic, KDE-ElGammal and RMOG achieved almost equal F measure with a minimal
difference. MSSTBM achieved the lowest score among all the compared methods
(Table 2). For better foreground detection the aim of the metrics (defined in
(12), (13), (14), (15), and (16)) is to maximize the values of Re, Sp and
Precision and minimize the values of FNR and PWC. The proposed DCP algorithm
achieved top score in Re and FNR which is $0.809$ and $0.191$ respectively
among all the compared methods. It means that more correct detection and less
incorrect detection of foreground objects by our proposed method. Moreover for
metrics like PWC, Sp and Precision, DCP achieved $2.671$ , $0.977$ and $0.773$
best scores respectively which are higher than most of the methods.

Figure 7: Estimated background examples from the CDnet2014 dataset : all
sequences are from the category ”Thermal”. (a) Sequence ”Corridor”. (b)
Sequence ”Dining Room”. (c) Sequence ”Lake Side”. (d) Sequence ”Library”. (e)
Sequence ”Park”. In all of these video sequences, DCP estimated an accurate
the background which leads to better foreground detection as well.

###  4.3 Performance of DCP on the basis of Homogeneous Context

As explained in Section 3, our proposed method estimates the background on the
basis of context prediction, so in this section we discuss the key aspects of
DCP on the type of contexts present in the video sequences containing
different scenes specifically for the application of background estimation.

Table 1 shows that for all categories, AGE score is different even for
individual videos per category for all the compared methods including DCP. The
reason behind that is, the context of every video is different with different
kinds of indoor outdoor scenes. Therefore, for compared methods including DCP
the average gray level score is different and quite challenging in some cases
as well. For convenience, we are targeting the discussion of homogeneous
context to few video sequences in SBM.net and CDnet2014 dataset. We have
selected $2$ categories from CDnet2014 dataset on the basis of their
homogeneous context in the video sequences. Category wise discussion is as
follows:

Category: Bad Weather is a similar context example from CDnet2014 dataset.
Figure 8 shows the visual result of video sequence ”blizzard” however other
three video sequences are same, ”skating”, ”wetsnow” and ”snowfall” from
category ”Basic” in SBM.net dataset. These video sequences have minimum score
of AGE and their visual result are shown in Figure 3 (c): $2^{nd},4^{th}$ and
$6^{th}$ row and Figure 8.

Category:Thermal is another challenging category in CDnet2014 which includes
videos that have been captured by far-infrared cameras. The interesting fact
about this category is it includes video sequences with thermal artifacts such
as heat stamps, heat reflection on floors, windows, camouflage effects, and a
moving object may have the same temperature as the surrounding regions
222http://jacarini.dinf.usherbrooke.ca/datasetOverview/. It is very favorable
environment for DCP for context prediction. The visual results of all $5$
video sequences for this category are shown in Figure 7.

Figure 8: Estimated background examples from the CDnet2014 dataset: sequences
in (a) are from the category ‘Bad Weather’ named ‘Blizzard’. (b) Sequence
‘Skating’. (c) Sequence ‘SnowFall’. (d) Sequence ‘WetSnow’. In all of these
video sequences, DCP estimated an accurate background which leads to better
foreground detection as well.

###  4.4 Failure Cases for DCP

Although DCP achieved good performance in most of the cases, still it has some
limitations and failure cases. Estimation of complex background structures
(Figure 9) and large scale foreground objects is quite challenging. The
limitation of the proposed method involves large sized foreground objects to
be accurately inpainted. In these cases, the network is not able to properly
fill the region in an irregular shape. We used Poisson blending technique to
transform center region inpainting context to irregular region one.

Figure 9: Estimated background example from the SBM.net dataset: (a) Sequence
$Candela~{}m1.10$ (b) Ground truth (c) Estimated background by DCP. Table 1
shows that for category ‘Intermittent Motion’ AGE of DCP is maximum than all
the compared methods.

##  5 Conclusion

In this work a unified method ‘Deep Context Prediction’ (DCP) is proposed for
background estimation and foreground segmentation using GAN and image
inpainting. The proposed method is based on an unsupervised visual feature
learning based hybrid GAN for context prediction along with semantic
inpainting network for texture optimization. Solution of random region
inpainting is also proposed by using center region inpainting and Poisson
blending. The proposed DCP algorithm is compared with six existing algorithms
for background estimation on SBM.net dataset. The proposed algorithm has
outperformed these compared methods with a significant margin. The proposed
algorithm is also compared with six foreground segmentation methods on
CDnet2014 dataset. On the average, the proposed algorithm has outperformed
these algorithms. These experiments demonstrate the effectiveness of the
proposed approach compared to the existing algorithms. The proposed algorithm
has demonstrated excellent results in bad weather and thermal imaging
categories in which most of the existing algorithms suffer from performance
degradation.

###### Acknowledgements.

This study was supported by the BK21 Plus project (SW Human Resource
Development Program for Supporting Smart Life) funded by the Ministry of
Education, School of Computer Science and Engineering, Kyungpook National
University, Korea (21A20131600005).

## References

  * Afifi and Hussain (2015) Afifi M, Hussain KF (2015) Mpb: A modified poisson blending technique. Computational Visual Media 1(4):331–341
  * Bengio et al (2009) Bengio Y, et al (2009) Learning deep architectures for ai. Foundations and trends® in Machine Learning 2(1):1–127
  * Bouwmans and Zahzah (2014) Bouwmans T, Zahzah EH (2014) Robust pca via principal component pursuit: A review for a comparative evaluation in video surveillance. Computer Vision and Image Understanding 122:22–34
  * Bouwmans et al (2017) Bouwmans T, Maddalena L, Petrosino A (2017) Scene background initialization: a taxonomy. Pattern Recognition Letters 96:3–11
  * Braham and Van Droogenbroeck (2016) Braham M, Van Droogenbroeck M (2016) Deep background subtraction with scene-specific convolutional neural networks. In: Systems, Signals and Image Processing (IWSSIP), 2016 International Conference on, IEEE, pp 1–4
  * Candès et al (2011) Candès EJ, Li X, Ma Y, Wright J (2011) Robust principal component analysis? Journal of the ACM (JACM) 58(3):11
  * Cao et al (2016) Cao X, Yang L, Guo X (2016) Total variation regularized rpca for irregularly moving object detection under dynamic background. IEEE transactions on cybernetics 46(4):1014–1027
  * Chen et al (2017) Chen M, Wei X, Yang Q, Li Q, Wang G, Yang MH (2017) Spatiotemporal gmm for background subtraction with superpixel hierarchy. IEEE transactions on pattern analysis and machine intelligence
  * Colombari et al (2005) Colombari A, Cristani M, Murino V, Fusiello A (2005) Exemplar-based background model initialization. In: Proceedings of the third ACM international workshop on Video surveillance & sensor networks, ACM, pp 29–36
  * Deng et al (2009) Deng J, Dong W, Socher R, Li LJ, Li K, Fei-Fei L (2009) ImageNet: A Large-Scale Hierarchical Image Database. In: CVPR09
  * Elgammal et al (2000) Elgammal A, Harwood D, Davis L (2000) Non-parametric model for background subtraction. In: European conference on computer vision, Springer, pp 751–767
  * Erichson and Donovan (2016) Erichson NB, Donovan C (2016) Randomized low-rank dynamic mode decomposition for motion detection. Computer Vision and Image Understanding 146:40–50
  * Gao et al (2014) Gao Z, Cheong LF, Wang YX (2014) Block-sparse RPCA for salient motion detection. IEEE T-PAMI 36(10):1975–1987
  * Girshick et al (2016) Girshick R, Donahue J, Darrell T, Malik J (2016) Region-based convolutional networks for accurate object detection and segmentation. IEEE transactions on pattern analysis and machine intelligence 38(1):142–158
  * Goodfellow et al (2014) Goodfellow I, Pouget-Abadie J, Mirza M, Xu B, Warde-Farley D, Ozair S, Courville A, Bengio Y (2014) Generative adversarial nets. In: Advances in neural information processing systems, pp 2672–2680
  * Guo et al (2014) Guo X, Wang X, Yang L, Cao X, Ma Y (2014) Robust foreground detection using smoothness and arbitrariness constraints. In: European Conference on Computer Vision, Springer, pp 535–550
  * Haines and Xiang (2014) Haines TS, Xiang T (2014) Background subtraction with dirichletprocess mixture models. IEEE transactions on pattern analysis and machine intelligence 36(4):670–683
  * He et al (2012) He J, Balzano L, Szlam A (2012) Incremental gradient on the grassmannian for online foreground and background separation in subsampled video. In: Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, IEEE, pp 1568–1575
  * Hinton and Salakhutdinov (2006) Hinton GE, Salakhutdinov RR (2006) Reducing the dimensionality of data with neural networks. science 313(5786):504–507
  * Javed et al (2015) Javed S, Oh SH, Bouwmans T, Jung SK (2015) Robust background subtraction to global illumination changes via multiple features-based online robust principal components analysis with markov random field. Journal of Electronic Imaging 24(4):043011
  * Javed et al (2016) Javed S, Jung SK, Mahmood A, Bouwmans T (2016) Motion-aware graph regularized rpca for background modeling of complex scenes. In: Pattern Recognition (ICPR), 2016 23rd International Conference on, IEEE, pp 120–125
  * Javed et al (2017a) Javed S, Mahmood A, Bouwmans T, Jung SK (2017a) Background–foreground modeling based on spatiotemporal sparse subspace clustering. IEEE Transactions on Image Processing 26(12):5840–5854
  * Javed et al (2017b) Javed S, Mahmood A, Bouwmans T, Jung SK (2017b) Background-Foreground Modeling Based on Spatiotemporal Sparse Subspace Clustering. IEEE T-IP
  * Krizhevsky et al (2012) Krizhevsky A, Sutskever I, Hinton GE (2012) Imagenet classification with deep convolutional neural networks. In: Advances in neural information processing systems, pp 1097–1105
  * Liang et al (2015) Liang D, Hashimoto M, Iwata K, Zhao X, et al (2015) Co-occurrence probability-based pixel pairs background model for robust object detection in dynamic scenes. Pattern Recognition 48(4):1374–1390
  * Liu et al (2009) Liu C, et al (2009) Beyond pixels: exploring new representations and applications for motion analysis. PhD thesis, Massachusetts Institute of Technology
  * Lu (2014) Lu X (2014) A multiscale spatio-temporal background model for motion detection. In: Image Processing (ICIP), 2014 IEEE International Conference on, IEEE, pp 3268–3271
  * Maddalena and Petrosino (2015) Maddalena L, Petrosino A (2015) Towards benchmarking scene background initialization. In: International Conference on Image Analysis and Processing, Springer, pp 469–476
  * Nakashima et al (2011) Nakashima Y, Babaguchi N, Fan J (2011) Automatic generation of privacy-protected videos using background estimation. In: Multimedia and Expo (ICME), 2011 IEEE International Conference on, IEEE, pp 1–6
  * Ortego et al (2016) Ortego D, SanMiguel JC, Martínez JM (2016) Rejection based multipath reconstruction for background estimation in video sequences with stationary objects. Computer vision and image understanding 147:23–37
  * Park and Byun (2013) Park D, Byun H (2013) A unified approach to background adaptation and initialization in public scenes. Pattern Recognition 46(7):1985–1997
  * Pathak et al (2016) Pathak D, Krahenbuhl P, Donahue J, Darrell T, Efros AA (2016) Context encoders: Feature learning by inpainting. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp 2536–2544
  * Pérez et al (2003) Pérez P, Gangnet M, Blake A (2003) Poisson image editing. ACM Transactions on graphics (TOG) 22(3):313–318
  * Ren et al (2015) Ren S, He K, Girshick R, Sun J (2015) Faster r-cnn: Towards real-time object detection with region proposal networks. In: Advances in neural information processing systems, pp 91–99
  * Shimada et al (2013) Shimada A, Nagahara H, Taniguchi Ri (2013) Background modeling based on bidirectional analysis. In: Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on, IEEE, pp 1979–1986
  * Simonyan and Zisserman (2014) Simonyan K, Zisserman A (2014) Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:14091556
  * Sobral and Zahzah (2017) Sobral A, Zahzah Eh (2017) Matrix and tensor completion algorithms for background model initialization: A comparative evaluation. Pattern Recognition Letters 96:22–33
  * Sobral et al (2015) Sobral A, Bouwmans T, Zahzah EH (2015) Comparison of matrix completion algorithms for background initialization in videos. In: International Conference on Image Analysis and Processing, Springer, pp 510–518
  * Stauffer and Grimson (1999) Stauffer C, Grimson WEL (1999) Adaptive background mixture models for real-time tracking. In: Computer Vision and Pattern Recognition, 1999. IEEE Computer Society Conference on., IEEE, vol 2, pp 246–252
  * Varadarajan et al (2013) Varadarajan S, Miller P, Zhou H (2013) Spatial mixture of gaussians for dynamic background modelling. In: Advanced Video and Signal Based Surveillance (AVSS), 2013 10th IEEE International Conference on, IEEE, pp 63–68
  * Viola and Jones (2001) Viola P, Jones M (2001) Rapid object detection using a boosted cascade of simple features. In: Computer Vision and Pattern Recognition, 2001. CVPR 2001\. Proceedings of the 2001 IEEE Computer Society Conference on, IEEE, vol 1, pp I–I
  * Wang et al (2014) Wang Y, Jodoin PM, Porikli F, Konrad J, Benezeth Y, Ishwar P (2014) Cdnet 2014: An expanded change detection benchmark dataset. In: Computer Vision and Pattern Recognition Workshops (CVPRW), 2014 IEEE Conference on, IEEE, pp 393–400
  * Wang et al (2017) Wang Y, Luo Z, Jodoin PM (2017) Interactive deep learning method for segmenting moving objects. Pattern Recognition Letters 96:66–75
  * Wright et al (2009) Wright J, Ganesh A, Rao S, Peng Y, Ma Y (2009) Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. In: Advances in neural information processing systems, pp 2080–2088
  * Xu et al (2013a) Xu J, Ithapu V, Mukherjee L, Rehg J, Singh V (2013a) Gosus: Grassmannian online subspace updates with structured-sparsity. In: ICCV
  * Xu et al (2013b) Xu J, Ithapu VK, Mukherjee L, Rehg JM, Singh V (2013b) Gosus: Grassmannian online subspace updates with structured-sparsity. In: Computer Vision (ICCV), 2013 IEEE International Conference on, IEEE, pp 3376–3383
  * Xu and Huang (2008) Xu X, Huang TS (2008) A loopy belief propagation approach for robust background estimation. In: Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, IEEE, pp 1–7
  * Yang et al (2016) Yang C, Lu X, Lin Z, Shechtman E, Wang O, Li H (2016) High-resolution image inpainting using multi-scale neural patch synthesis. arXiv preprint arXiv:161109969
  * Ye et al (2015) Ye X, Yang J, Sun X, Li K, Hou C, Wang Y (2015) Foreground–background separation from video clips via motion-assisted matrix restoration. IEEE Transactions on Circuits and Systems for Video Technology 25(11):1721–1734
  * Zhang et al (2013) Zhang T, Liu S, Xu C, Lu H (2013) Mining semantic context information for intelligent video surveillance of traffic scenes. IEEE transactions on industrial informatics 9(1):149–160
  * Zhang et al (2015a) Zhang T, Liu S, Ahuja N, Yang MH, Ghanem B (2015a) Robust visual tracking via consistent low-rank sparse learning. International Journal of Computer Vision 111(2):171–190
  * Zhang et al (2015b) Zhang Y, Li X, Zhang Z, Wu F, Zhao L (2015b) Deep learning driven blockwise moving object detection with binary scene modeling. Neurocomputing 168:454–463
  * Zhao et al (2016) Zhao Q, Zhou G, Zhang L, Cichocki A, Amari SI (2016) Bayesian robust tensor factorization for incomplete multiway data. IEEE transactions on neural networks and learning systems 27(4):736–748
  * Zhou and Tao (2011) Zhou T, Tao D (2011) Godec: Randomized low-rank and sparse matrix decomposition in noisy case. In: ICML, Omnipress
  * Zhou et al (2013) Zhou X, Yang C, Yu W (2013) Moving object detection by detecting contiguous outliers in the low-rank representation. IEEE T-PAMI 35(3):597–610
  * Zivkovic (2004) Zivkovic Z (2004) Improved adaptive gaussian mixture model for background subtraction. In: Pattern Recognition, 2004. ICPR 2004. Proceedings of the 17th International Conference on, IEEE, vol 2, pp 28–31

Maryam Sultana is a PhD student at Virtual Reality Lab, School of Computer
Science and Engineering, Kyungpook National University Republic of Korea. She
received her M.Sc. and M.Phil. degrees in electronics from Quaid-i-Azam
university Pakistan in 2013 and 2016, respectively. Her research interests
include background modeling, foreground object detection and generative
adversarial networks.

Arif Mahmood received the master’s and Ph.D. degrees in computer science from
the Lahore University of Management Sciences, Lahore, Pakistan, in 2003 and
2011, respectively. He was a Research Assistant Professor with the School of
Computer Science and Software Engineering, The University of Western Australia
(UWA), where he was involved in hyper-spectral object recognition and action
recognition using depth images. He was a Research Assistant Professor with the
School of Mathematics and Statistics, UWA, where he was involved in the
characterizing structure of complex networks using sparse subspace clustering.
He is currently a Post-Doctoral Researcher with the Department of Computer
Science and Engineering, Qatar University, Doha. He has performed research in
data clustering, classification, action, and object recognition. His major
research interests are in computer vision and pattern recognition, action
detection and person segmentation in crowded environments, and background-
foreground modeling in complex scenes.

Sajid Javed is currently a Post-doctoral research fellow in the Department of
Computer Science, University of Warwick, United Kingdom. He obtained his Bs.c
(hons) degree in Computer Science from University of Hertfordshire, UK, in
2010. He joined the Virtual Reality Laboratory of Kyungpook National
University, Republic of Korea, in 2012 where he completed his combined
Master’s and Doctoral degrees in Computer Science. His research interests
include background modeling and foreground object detection, robust principal
component analysis, matrix completion, and subspace clustering.

Soon Ki Jung is a professor in the School of Computer Science and Engineering
at Kyungpook National University, Republic of Korea. He received his MS and
PhD degrees in computer science from Korea Advanced Institute of Science and
Technology (KAIST), Korea, in 1992 and 1997, respectively. He has been a
visiting professor at University of Southern California, USA, in 2009. He has
been an active executive board member of Human Computer Interaction, Computer
Graphics, and Multimedia societies in Korea. Since 2007, he has also served as
executive board member of IDIS Inc. His research areas include a broad range
of computer vision, computer graphics, and virtual reality topics.


x\leftarrow N}\\}\|=\|\biguplus\Lbag{M\mid x\leftarrow N}\Rbag$
$\displaystyle=$ $\displaystyle\|M\|+\|N\|$ $\displaystyle\|M\
\mathbf{where}_{\mathsf{set}}\ N\|=\|M\ \mathbf{where}_{\mathsf{bag}}\ N\|$
$\displaystyle=$ $\displaystyle\|M\|+\|N\|$ $\displaystyle\|M\|$
$\displaystyle=$ $\displaystyle 0\qquad\text{otherwise}$

If the metric is zero, then the query is fully delateralized. Combining the
basic delateralization steps above with commutativity, any expression with
nonzero metric can be rewritten so as to decrease the metric (though possibly
increasing the query size). We can also undo the effects of commutativity
steps to restore the original order of generators, to preserve the query
structure as much as possible for readability.

###### Theorem 0.B.4

Given $M$ with $\|M\|>0$, there exists an equivalent $M^{\prime}$ with
$\|M^{\prime}\|<\|M\|$ that can be obtained by applying commutativity and
basic rewrites. Hence, there exists an equivalent fully-delateralized
$M^{\prime\prime}$ with $\|M^{\prime\prime}\|=0$.

###### Proof

The proof requires establishing that whenever $\|M\|>0$, there exists at least
one outermost subexpression $M_{0}$ of the form $\iota(N)$ or $N-P$ with
$\|M_{0}\|>0$. That is, $M_{0}$ should not be a subexpression of any larger
such subexpression of $M$ having the same property. Moreover, $M_{0}$ must
occur as a generator. We need to show that $M_{0}$ therefore contains at least
one free record variable bound earlier in the same comprehension. We can show
this by inspection of normal forms. Since this is the case, then (if the
generator is not already adjacent) we can commute it to be adjacent to $M_{0}$
and then apply one of the delateralization rules, decreasing $\|M_{0}\|$ and
hence $\|M\|$. ∎

##  Appendix 0.C Proofs for Section 6

###### Lemma 14

If $\Phi;\Theta\vdash M\Mapsto\breve{M}\mid\Psi$, then $\Psi\supseteq\Phi$.

###### Lemma 15

Let $M$ an $\mathcal{NRC}_{\mathcal{G}}$ term and $\Phi$ a shredding set. If
$\operatorname{FV}(M)\subseteq\operatorname{dom}(\Phi)$, then for all
$\Phi^{\prime}\supseteq\Phi$ we have $M\Phi=M\Phi^{\prime}$.

Furthermore, let $\Xi$ and $\Xi^{\prime}$ be the shredding value sets
corresponding to $\Phi$ and $\Phi^{\prime}$: then
$\llparenthesis\left\lfloor{M}\right\rfloor\rrparenthesis\Xi=\llparenthesis\left\lfloor{M}\right\rfloor\rrparenthesis\Xi^{\prime}$.

In the following proof, whenever $\Theta=\overrightarrow{x\leftarrow F}$, we
use the abbreviation:

$\left\llbracket{\Theta}\right\rrbracket\rho~{}\overrightarrow{v}=\bigwedge_{i}\left\llbracket{F_{i}}\right\rrbracket\rho[x_{1}\mapsto
v_{1},\ldots,x_{i-1}\mapsto v_{i-1}]~{}v_{i}$

####  0.C.0.1 Theorem 6.3.

_Let $\Theta$ be well-typed and $ty(\Theta)\vdash M:\sigma$. Let $\Phi$ be
well-typed, and suppose $\Phi;\Theta\vdash
M\Mapsto\breve{M}\mathbin{~{}|~{}}\Psi$. Let $\Xi$ be the result of evaluating
the flattened queries in $\Psi$ as above. Then
$\left\llbracket{\breve{M}\Psi}\right\rrbracket\rho=\left\llbracket{\llparenthesis\left\lfloor{\breve{M}}\right\rfloor:\tau\rrparenthesis\Xi}\right\rrbracket\rho$.
_

###### Proof

We proceed by induction on the shredding judgment. We comment the two key
cases:

  * •

For set comprehension:

$\begin{array}[]{rl}\Phi;\Theta\vdash&\bigcup\\{{\\{{M}\\}~{}\mathbf{where}~{}X\mid\Theta^{\prime}}\\}\Mapsto\varphi\varoast(\operatorname{dom}(\Theta))\\\
\mid&\Psi[\varphi\mapsto\mathcal{G}(\Theta;\bigcup\\{{\\{{\breve{M}}\\}~{}\mathbf{where}~{}X\mid\Theta^{\prime}}\\})]\end{array}$

where we wrote $\Theta^{\prime}=\overrightarrow{x\leftarrow F}$ for
conciseness. Let $\Xi$ be the shredding value set for $\Psi$, and
$\Xi^{\prime}$ the shredding value set for
$\Psi[\varphi\mapsto\mathcal{G}(\Theta;\bigcup\\{{\\{{\breve{M}}\\}~{}\mathbf{where}~{}X\mid\Theta^{\prime}}\\})]$.
We rewrite the rhs:

$\begin{array}[]{l}\left\llbracket{\llparenthesis\mathit{index}(\varphi,\operatorname{dom}(\Theta))\rrparenthesis\Xi^{\prime}}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\bigcup\\{{\\{{\llparenthesis
p.2\rrparenthesis\Xi^{\prime}}\\}~{}\mathbf{where}~{}p.1=\langle{\operatorname{dom}(\Theta)}\rangle\mid
p\leftarrow\Xi^{\prime}(\varphi)}\\}}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\bigcup\left\\{\begin{array}[]{l}\\{{\llparenthesis
p.2\rrparenthesis\Xi^{\prime}}\\}~{}\mathbf{where}~{}p.1=\langle{\operatorname{dom}(\Theta)}\rangle\\\
\qquad\mid
p\leftarrow\mathcal{S}(\mathit{norm}(\left\lfloor{\mathcal{G}(\Theta^{*};\bigcup\\{{\\{{\breve{M}^{*}}\\}~{}\mathbf{where}~{}X^{*}\mid\Theta^{\prime*}}\\})}\right\rfloor))\end{array}\right\\}}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\bigcup\left\\{\begin{array}[]{l}\\{{\llparenthesis
p.2\rrparenthesis\Xi^{\prime}}\\}~{}\mathbf{where}~{}p.1=\langle{\operatorname{dom}(\Theta)}\rangle\\\
\qquad\mid
p\leftarrow\bigcup\\{{\\{{\langle{\langle{\operatorname{dom}(\Theta^{*})}\rangle,\left\lfloor{\breve{M}^{*}}\right\rfloor}\rangle}\\}~{}\mathbf{where}~{}X^{*}\mid\Theta^{*},\Theta^{\prime*}}\\}\end{array}\right\\}}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\bigcup\\{{\\{{\llparenthesis\left\lfloor{\breve{M}^{*}}\right\rfloor\rrparenthesis\Xi^{\prime}}\\}~{}\mathbf{where}~{}(\langle{\operatorname{dom}(\Theta^{*})}\rangle=\langle{\operatorname{dom}(\Theta)}\rangle\land
X^{*})\mid\Theta^{*},\Theta^{\prime*}}\\}}\right\rrbracket\rho~{}u\\\
=\bigvee_{\overrightarrow{v},\overrightarrow{v^{\prime}}}(\left\llbracket{\llparenthesis\left\lfloor{\breve{M}^{*}}\right\rfloor\rrparenthesis\Xi}\right\rrbracket\rho^{\prime}=u)\land\left\llbracket{\operatorname{dom}(\Theta^{*})=\operatorname{dom}(\Theta)}\right\rrbracket\rho^{\prime}\land\left\llbracket{X^{*}}\right\rrbracket\rho^{\prime}\land\left\llbracket{\Theta^{*},\Theta^{\prime*}}\right\rrbracket\rho~{}\overrightarrow{v},\overrightarrow{v^{\prime}}\\\
=\bigvee_{\overrightarrow{v^{\prime}}}(\left\llbracket{\llparenthesis\left\lfloor{\breve{M}}\right\rfloor\rrparenthesis\Xi}\right\rrbracket\rho^{\prime\prime}=u)\land\left\llbracket{X}\right\rrbracket\rho^{\prime\prime}\land\left\llbracket{\Theta^{\prime}}\right\rrbracket\rho~{}\overrightarrow{v^{\prime}}\end{array}$

where we alpha-renamed $\operatorname{dom}(\Theta)$ to a fresh
$\operatorname{dom}(\Theta^{*})$ within $\breve{M}$, $X$ and $\Theta^{\prime}$
(yielding $\breve{M}^{*}$, $X^{*}$, and $\Theta^{\prime*}$, and we have set
$\rho^{\prime}=\rho[\operatorname{dom}(\Theta^{*})\mapsto\overrightarrow{v},\operatorname{dom}(\Theta^{\prime})\mapsto\overrightarrow{v^{\prime}}]$,
$\rho^{\prime\prime}=\rho[\operatorname{dom}(\Theta^{\prime})\mapsto\overrightarrow{v^{\prime}}]$.
Note that the renaming involving $\Theta^{*}$ is undone in the last step
through the evaluation of
$\left\llbracket{\operatorname{dom}(\Theta^{*})=\operatorname{dom}(\Theta)}\right\rrbracket\rho^{\prime}$.

We then rewrite the lhs:

$\begin{array}[]{l}\left\llbracket{(\varphi\varoast\operatorname{dom}(\Theta))\Psi^{\prime}}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\mathcal{G}(\Theta;\bigcup\\{{\\{{\breve{M}\Psi^{\prime}}\\}~{}\mathbf{where}~{}X\mid\Theta^{\prime}}\\})\varoast(\operatorname{dom}(\Theta))}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\bigcup\\{{\\{{\breve{M}\Psi^{\prime}}\\}~{}\mathbf{where}~{}X\mid\Theta^{\prime}}\\}}\right\rrbracket\rho~{}u\\\
=\bigvee_{\overrightarrow{v^{\prime}}}(\left\llbracket{\breve{M}\Psi^{\prime}}\right\rrbracket\rho^{\prime\prime}=u)\land\left\llbracket{X}\right\rrbracket\rho^{\prime\prime}\land\left\llbracket{\Theta^{\prime}}\right\rrbracket\rho~{}\overrightarrow{v^{\prime}}\end{array}$

By Lemma 15 and by induction hypotheses, we prove:

$\left\llbracket{\breve{M}\Psi^{\prime}}\right\rrbracket\rho^{\prime\prime}=\left\llbracket{\breve{M}\Psi}\right\rrbracket\rho^{\prime\prime}=\left\llbracket{\llparenthesis\left\lfloor{\breve{M}}\right\rfloor\rrparenthesis\Xi}\right\rrbracket\rho^{\prime\prime}=\left\llbracket{\llparenthesis\left\lfloor{\breve{M}}\right\rfloor\rrparenthesis\Xi^{\prime}}\right\rrbracket\rho^{\prime\prime}$

which we combine with the previous calculations to prove the thesis.

  * •

For set union:

$\varphi\notin\operatorname{dom}(\Phi_{n})$ $(\Phi_{i-1};\Theta\vdash
C_{i}\Mapsto\psi_{i}\varoast\operatorname{dom}(\Theta)\mathbin{~{}|~{}}\Phi_{i})_{i=1,\ldots,n}$
$\begin{array}[]{rl}\Phi_{0};\Theta\vdash&\bigcup\overrightarrow{C}\Mapsto\varphi\varoast\operatorname{dom}(\Theta)\\\
\mathbin{~{}|~{}}&(\Phi_{n}\setminus\overrightarrow{\psi})[\varphi\mapsto\bigcup\overrightarrow{\Phi_{n}(\psi)}]\end{array}$

Let $\Xi_{i}$ be the shredding value set for each $\Phi_{i}$, and
$\Xi^{\prime}$ the shredding value set for
$\Phi^{\prime}:=(\Phi_{n}\setminus\overrightarrow{\psi})[\varphi\mapsto\bigcup\overrightarrow{\Phi_{n}(\psi)}]$.
We rewrite the rhs:

$\begin{array}[]{l}\left\llbracket{\llparenthesis\mathit{index}(\varphi,\operatorname{dom}(\Theta))\rrparenthesis\Xi^{\prime}}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\bigcup\\{{\\{{\llparenthesis
p.2\rrparenthesis\Xi^{\prime}}\\}~{}\mathbf{where}~{}p.1=\langle{\operatorname{dom}(\Theta)}\rangle\mid
p\leftarrow\Xi^{\prime}(\varphi)}\\}}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\bigcup\\{{\\{{\llparenthesis
p.2\rrparenthesis\Xi^{\prime}}\\}~{}\mathbf{where}~{}p.1=\langle{\operatorname{dom}(\Theta)}\rangle\mid
p\leftarrow\mathcal{S}(\mathit{norm}(\left\lfloor{\bigcup\overrightarrow{\Phi_{n}(\psi)}}\right\rfloor))}\\}}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\bigcup_{i}\bigcup\\{{\\{{\llparenthesis
p.2\rrparenthesis\Xi^{\prime}}\\}~{}\mathbf{where}~{}p.1=\langle{\operatorname{dom}(\Theta)}\rangle\mid
p\leftarrow\mathcal{S}(\mathit{norm}(\Phi_{n}(\psi_{i})}\\}}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\bigcup_{i}\bigcup\\{{\\{{\llparenthesis
p.2\rrparenthesis\Xi^{\prime}}\\}~{}\mathbf{where}~{}p.1=\langle{\operatorname{dom}(\Theta)}\rangle\mid
p\leftarrow\mathcal{S}(\mathit{norm}(\Phi_{i}(\psi_{i})}\\}}\right\rrbracket\rho~{}u\\\
=\bigvee_{i}\left\llbracket{\llparenthesis\mathit{index}(\psi_{i},\operatorname{dom}(\Theta))\rrparenthesis\Xi_{i}}\right\rrbracket\rho~{}u\end{array}$

We also rewrite the lhs:

$\begin{array}[]{l}\left\llbracket{(\varphi\varoast\operatorname{dom}(\Theta))\Phi^{\prime}}\right\rrbracket\rho~{}u\\\
=\left\llbracket{(\bigcup\overrightarrow{(\Phi_{n}(\psi)\Phi^{\prime})})\varoast(\operatorname{dom}(\Theta))}\right\rrbracket\rho~{}u\\\
=\left\llbracket{\bigcup\overrightarrow{(\Phi_{n}(\psi)\Phi^{\prime})}}\right\rrbracket\rho~{}(\left\llbracket{\operatorname{dom}(\Theta)}\right\rrbracket\rho~{}u)\\\
=\bigvee_{i}\left\llbracket{(\Phi_{n}(\psi_{i})\Phi^{\prime})}\right\rrbracket\rho~{}(\left\llbracket{\operatorname{dom}(\Theta)}\right\rrbracket\rho~{}u)\\\
=\bigvee_{i}\left\llbracket{(\Phi_{i}(\psi_{i})\Phi_{i})}\right\rrbracket\rho~{}(\left\llbracket{\operatorname{dom}(\Theta)}\right\rrbracket\rho~{}u)\\\
=\bigvee_{i}\left\llbracket{\psi_{i}\Phi_{i}}\right\rrbracket\rho~{}(\left\llbracket{\operatorname{dom}(\Theta)}\right\rrbracket\rho~{}u)\\\
=\bigvee_{i}\left\llbracket{(\psi_{i}\varoast(\operatorname{dom}(\Theta)))\Phi_{i}}\right\rrbracket\rho~{}u)\end{array}$

By induction hypothesis, we prove:

$\left\llbracket{(\psi_{i}\varoast(\operatorname{dom}(\Theta)))\Phi_{i}}\right\rrbracket\rho=\left\llbracket{\llparenthesis\left\lfloor{\psi_{i}\varoast(\operatorname{dom}(\Theta))}\right\rfloor\rrparenthesis\Xi_{i}}\right\rrbracket\rho=\left\llbracket{\llparenthesis\mathit{index}(\psi_{i},\operatorname{dom}(\Theta))\rrparenthesis\Xi_{i}}\right\rrbracket\rho$

which we combine with the previous calculations to prove the thesis. ∎

Open Access This chapter is licensed under the terms of the Creative
CommonsAttribution 4.0 International License
(http://creativecommons.org/licenses/by/4.0/), which permits use, sharing,
adaptation, distribution and reproduction in any medium or format, as long as
you give appropriate credit to the original author(s) and the source, provide
a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the
chapter’s Creative Commons license, unless indicated otherwise in a credit
line to the material. If material is not included in the chapter’s Creative
Commons license and your intendeduse is not permitted by statutory regulation
or exceeds the permitted use, you will need to obtain permission directly from
the copyright holder.