*

# Applications of a Graph Theoretic Based Clustering Framework in Computer
Vision and Pattern Recognition

Yonatan Tariku Tesfaye

## Abstract

Recently , several clustering algorithms have been used to solve variety of
problems from different discipline. This dissertation aims to address
different challenging tasks in computer vision and pattern recognition by
casting the problems as a clustering problem. We proposed novel approaches to
solve multi-target tracking, visual geo-localization and outlier detection
problems using a unified underlining clustering framework, i.e., dominant set
clustering and its extensions, and presented a superior result over several
state-of-the-art approaches.

Firstly, this dissertation will present a new framework for multi-target
tracking in a single camera. We proposed a novel data association technique
using Dominant set clustering (DCS) framework. We formulate the tracking task
as finding dominant sets on the constructed undirected edge weighted graph.
Unlike most techniques which are limited in temporal locality (i.e. few frames
are considered), we utilized a pairwise relationships (in appearance and
position) between different detections across the whole temporal span of the
video for data association in a global manner. Meanwhile, temporal sliding
window technique is utilized to find tracklets and perform further merging on
them. Our robust tracklet merging step renders our tracker to long term
occlusions with more robustness. DSC leads us to a more accurate approach to
multi-object tracking by considering all the pairwise relationships in a batch
of frames; however, it has some limitations. Firstly, it finds target
trajectories(clusters) one-by-one (peel off strategy), causing change in the
scale of the problem. Secondly, the algorithm used to enumerate dominant sets,
i.e., replicator dynamics, have quadratic computational complexity, which
makes it impractical on larger graphs.

To address these problems and extend tracking problem to multiple non-
overlapping cameras, we proposed a novel and unified three-layer hierarchical
approach. Given a video and a set of detections (obtained by any person
detector), we first solve within-camera tracking employing the first two
layers of our framework and, then, in the third layer, we solve across-camera
tracking by merging tracks of the same person in all cameras in a simultaneous
fashion. To best serve our purpose, a constrained dominant set clustering
(CDSC) technique, a parametrized version of standard quadratic optimization,
is employed to solve both tracking tasks. The tracking problem is caste as
finding constrained dominant sets from a graph. That is, given a constraint
set and a graph, CDSC generates cluster (or clique), which forms a compact and
coherent set that contains a subset of the constraint set. The approach is
based on a parametrized family of quadratic programs that generalizes the
standard quadratic optimization problem. In addition to having a unified
framework that simultaneously solves within- and across-camera tracking, the
third layer helps link broken tracks of the same person occurring during
within-camera tracking. A standard algorithm to extract constrained dominant
set from a graph is given by the so-called replicator dynamics whose
computational complexity is quadratic per step which makes it handicapped for
large-scale applications. In this work, we propose a fast algorithm, based on
dynamics from evolutionary game theory, which is efficient and salable to
large-scale real-world applications. In test against several tracking
datasets, we show that the proposed method outperforms competitive methods.

Another challenging task in computer vision is image geo-localization, here as
well, we proposed a novel approach which cast geo-localization as a clustering
problem of local image features. Akin to existing approaches to the problem,
our framework builds on low-level features which allow local matching between
images. We cluster features from reference images using Dominant Set
clustering, which affords several advantages over existing approaches. First,
it permits variable number of nodes in the cluster, which we use to
dynamically select the number of nearest neighbors for each query feature
based on its discrimination value. Second, this approach is several orders of
magnitude faster than existing approaches. Thus, we use multiple weak
solutions through constrained Dominant Set clustering on global image
features, where we enforce the constraint that the query image must be
included in the cluster. This second level of clustering also bypasses
heuristic approaches to voting and selecting the reference image that matches
to the query. We evaluated the proposed framework on an existing and new
dataset and showed that it outperforms the state-of-the-art approaches by a
large margin.

Finally, we present a unified approach for simultaneous clustering and outlier
detection in data. We utilize some properties of a family of quadratic
optimization problems related to dominant sets. Unlike most (all) of the
previous techniques, in our framework the number of clusters arises
intuitively and outliers are obliterated automatically. The resulting
algorithm discovers both parameters (number of clusters and outliers) from the
data. Experiments on real and large scale synthetic dataset demonstrate the
effectiveness of our approach and the utility of carrying out both clustering
and outlier detection in a concurrent manner.

## Acknowledgments

First and for most, I thank Jehovah God for everything he has done for me.

I would like to express my gratitude to my supervisor Prof. Andrea Prati, for
his scientific guidance and support during my Ph.D. studies.

My sincere thanks also goes to my co-authors Prof. Marcello Pelillo for his
insightful comments and Dr. Mubarak Shah who provided me an opportunity to
join his team, CRCV at University of Central Florida, as a research scholar
for more than a year, without his precious support, great advice, and fruitful
discussion it would not be possible to conduct most of my researches.

I thank my external reviewers: Prof. Lamberto Ballan, and Prof. Christian
Micheloni for the time they spent on carefully reading the thesis and for
their insightful comments and suggestions.

Also I thank my friends Josh, Leul, Sure, Tedo, Tinsu, Siyum … for all the fun
time we had and the moments we spent at ’BAUM’, Campo, coffee break and so on.
In particular, I am grateful to Josh for stimulating discussions, for the
sleepless nights we were working together before deadlines, and for all the
fun we have had on the trips we had.

Last but not least, I would like to thank my families: my parents (Seni and
Tare), my brother (Beck), and my aunty (Tiz) for supporting me spiritually
throughout my Ph.D study and my life in general. This is the fruit of your
love, support, guidance and prayers.

## Preface

This dissertation presents applications of a graph theoretic clustering
framework, namely dominant sets and its variants, in solving problems in
computer vision and pattern recognition. Chapter 3 presents the first
application of dominant sets to solve tracking problem in a single camera.
This led to the first publication [151]. Chapter 4 introduces a new multi-
target tracking approach in a multiple non-overlapping camera using
constrained dominant sets. This work is under review at Transactions on
Pattern Analysis and Machine Intelligence (TPAMI) [the arXiv version is in
[152]] and has been developed in the last year of my PhD course, during my
second visit to the Center for Research in Computer Vision (CRCV) at
University of Central Florida, under the supervision of Dr. Mubarak Shah.
Chapter 5 presents a Nobel approach to solve another yet very challenging
computer vision problem, i.e., large scale image geo-localization using
(constrained) dominant set clustering framework. The result has been published
in TPAMI [184]. This work is done during my first visit to CRCV at UCF.
Finally, the last chapter of the thesis is devoted to outlier detections, we
used some properties of dominant sets to simultaneously solve clustering and
outlier detections from data. This work has been presented in [185].

## Introduction

The clustering problem has been formulated in many contexts and by researchers
in many disciplines; this reflects its broad appeal and usefulness as one of
the steps in exploratory data analysis. Clustering has found applications in
such diverse disciplines as biology, psychology, archaeology, geology,
engineering, information retrieval, and remote sensing.

Some interesting applications of clustering include clustering of job analytic
data [194], grouping homogenous industrial companies [28], seventh and eighth
centuries A.D. sculptures clustering [144], clustering of collinear line
segments in digital images [138], clustering is used to study mixture of human
populations race [126], clustering for document classification and indexing
[58, 134] and clustering for investment portfolio performance comparison [37].

Cluster analysis is used in numerous applications involving unsupervised
learning, where there is no category label assigned to training patterns. As
can be seen from the huge amount of literature several problems from different
discipline used clustering approach. The use of clustering in computer science
and engineering applications has been relatively recent. Cluster analysis
plays an important role in solving many problems in natural language
processing, pattern recognition and image processing. Recently, its use in the
computer vision and pattern recognition community is growing exponentially.
Clustering is used in speech and speaker recognition [122], clustering in
multi-target tracking is used to solve data association problem [43, 176, 149,
30, 99], group detection in a video is also casted as a clustering problem in
[158, 69, 2], [146] used clustering to track group, in image geo-localization
clustering is used to solve matching between query and reference images [178],
image retrieval has been effectively casted as a clustering problem [180],
outlier detection [185], image registration [148], and image segmentation is
one of the most studied application of clustering in computer vision [181,
183, 166, 36, 140, 109, 17].

The availability of a vast collection of clustering algorithms in the
literature can easily confound a user attempting to select an algorithm
suitable for the problem at hand [72]. A list of admissibility criteria has
been suggested by [106] to make a comparison between clustering algorithms.
The criteria used in [106] are mainly based on how the cluster is formed,
sensitivity of the clustering technique to changes that do not affect the
structure of data, and the way the data was structured.

As there does not exist a universal clustering approach which can be applied
for all kinds of modalities of problems, we need to find the right clustering
approach based of the problem at hand. The focus of this dissertation is to
propose a unified, novel and robust approaches for problems in multi-target
tracking, geo-localization and outlier detection. In all the proposed
frameworks, we used the same graph theoretic clustering approach, namely,
dominant set clustering (DSC), and its extension, constrained dominant set
clustering framework. The intrinsic properties of these approaches make them
very suitable for the above-mentioned problems.

Dominant set clustering framework is first introduced by Pavan and Pelillo
[110, 112], and showed its effectiveness in the areas of segmentation, image
retrieval and group detection. Dominant set clustering is a graph-theoretic
approach for pairwise data clustering which is motivated by the analogies
between the intuitive concept of a cluster and that of a dominant set of
vertices. It generalizes a maximal clique problem to an edge-weighted graphs.
Its correspondence with a linearly constrained quadratic optimization program
under the standard simplex, allowed us to use of straightforward and easily
implementable continuous optimization techniques from evolutionary game
theory. We follow a pill-off strategy to enumerate all possible clusters, that
is, at each iteration we remove the cluster from the graph. Even though, it
has several advantages over other clustering approaches, the iterative
approach we follow to extract clusters cause change in the scale of the
problem. Meaning, we do not have a theoretical guaranty that clusters found at
the consecutive iterations are the local solutions of the original graph.

Constrained dominant set clustering framework is first proposed in [183]. It
is a parametrized version of standard quadratic optimization. By properly
controlling a regularization parameter which determines the structure and the
scale of the underlying problem, we are able to extract groups of dominant-set
clusters which are constrained to contain user-selected elements. A standard
algorithm to extract constrained dominant sets from a graph is given by the
so-called replicator dynamics, whose computational complexity is quadratic per
step which makes it handicapped for large-scale applications. In this work, we
propose noble fast algorithm, based on dynamics from evolutionary game theory,
which is efficient and salable to large-scale real-world applications.

In this thesis, we aim to address problems in multi-target tracking in single
and multiple cameras, large scale image geo-localization, and outlier
detections by proposing several new algorithms, which utilize the above-
mentioned clustering frameworks.

Firstly, we proposed a novel and efficient single camera multi-target tracking
approach, which formulates the tracking task as finding dominant sets in an
auxiliary undirected edge-weighted graph. The nodes in the graph represent
detection responses from consecutive frames and edge weights depict the
similarity between detection responses. In this formulation, the extracted
cluster (dominant set) represents a trajectory of a target across consecutive
frames. Unlike most techniques, which are limited in temporal locality (i.e.
few frames are considered), we utilized a pairwise relationships (in
appearance and position) between different detections across the whole
temporal span of the video for data association in a global manner. Meanwhile,
temporal sliding window technique is utilized to find tracklets and perform
further merging on them. Our robust tracklet merging step renders our tracker
to long term occlusions with more robustness.

Even though, the approach showed competitive result against several state-of-
the-art approaches, it suffers the short comings of the underlined clustering
framework, i.e. dominant sets. To solve the limitations of the above approach
and extend multi-target tracking across multiple non-overlapping cameras, we
proposed a robust and unified three-layered hierarchical approach. We first
determine tracks within each camera, by solving data association, and later we
associate tracks of the same person in different cameras in a unified
approach, hence solving the across-camera tracking. Since appearance and
motion cues of a target tend to be consistent in a short temporal window in a
single camera tracking, tracklets are generated within short temporal window
first and later they are merged to form full tracks (or trajectories). To best
serve our purpose, a constrained dominant set clustering (CDSC) technique is
employed to solve both tracking tasks. The tracking problem is caste as
finding constrained dominant sets from a graph. That is, given a constraint
set and a graph, CDSC generates cluster (or clique), which forms a compact and
coherent set that contains all or part of the constraint set. Clusters
represent tracklets and tracks in the first and second layers, respectively.
The proposed within-camera tracker can robustly handle long-term occlusions,
does not change the scale of original problem as it does not remove nodes from
the graph during the extraction of compact clusters and is several orders of
magnitude faster (close to real time) than existing methods. Also, the
proposed across-camera tracking method using CDSC and later followed by
refinement step offers several advantages. More specifically, CDSC not only
considers the affinity (relationship) between tracks, observed in different
cameras, but also considers the affinity among tracks from the same camera.
Consequently, the proposed approach not only accurately associates tracks from
different cameras but also makes it possible to link multiple short broken
tracks obtained during within-camera tracking, which may belong to a single
target track.

Next, we present a novel approach for a challenging problem of large scale
image geo-localization using image matching, in a structured database of city-
wide reference images with known GPS coordinates. This is done by finding
correspondences between local features of the query and reference images. We
first introduce automatic Nearest Neighbors (NN) selection into our framework,
by exploiting the discriminative power of each NN feature and employing
different number of NN for each query feature. That is, if the distance
between query and reference NNs is similar, then we use several NNs since they
are ambiguous, and the optimization is afforded with more choices to select
the correct match. On the other hand, if a query feature has very few low-
distance reference NNs, then we use fewer NNs to save the computation cost.
Thus, for some cases we use fewer NNs, while for others we use more requiring
on the average approximately the same amount of computation power, but
improving the performance, nonetheless. This also bypasses the manual tuning
of the number of NNs to be considered, which can vary between datasets and is
not straightforward. Next, we cluster features from reference images using
Dominant Set clustering, which possesses several advantages over existing
approaches. First, it permits variable number of nodes in the cluster. Second,
this approach is several orders of magnitude faster than existing approaches.
Finally, we use multiple weak solutions through constrained Dominant Set
clustering on global image features, where we enforce the constraint that the
query image must be included in the cluster. This second level of clustering
also bypasses heuristic approaches to voting and selecting the reference image
that matches to the query.

Finally, we present a modified dominant set clustering approach for
simultaneous clustering and outlier detection from data (SCOD). Unlike most
approaches our method requires no prior knowledge on both the number of
clusters and outliers, which makes our approach more convenient for real
applications. A naive approach to apply dominant set clustering is to set a
threshold, say cluster size, and label clusters with smaller cluster size than
the threshold as outliers. However, in the presence of many cluttered noises
(outliers) with a uniformly distributed similarity (with very small internal
coherency), the dominant set framework extracts the set as one big cluster.
That is, cluster size threshold approaches are handicapped in dealing with
such cases. Thus, what is required is a more robust technique that can
gracefully handle outlier clusters of different size and cohesiveness.
Dominant set framework naturally provides a principled measure of a cluster’s
cohesiveness as well as a measure of vertex participation to each group
(cluster). On the virtue of this nice feature of the framework, we propose a
technique which simultaneously discover clusters and outlier in a
computationally efficient manner.

In summary, this dissertation makes the following important contributions:

  * •

In the proposed Dominant set clustering based single camera multi-target
tracker, we formalize the tracking problem as finding DSC from the graph and
each cluster represent a trajectory of a single target in different
consecutive frames and we extract clusters one-by-one iteratively, which cause
change in the scale of the problem.

  * •

To improve the limitations of the above approach and extend the approach to a
multiple non-overlapping cameras we proposed a new technique which is based on
Constrained Dominant Set Clustering, this approach not only address the
limitations of our previous approach but also handles tracking in a multiple
non-overlapping cameras in a unified manner.

  * •

The dissertation also included a novel approach to solve another very
challenging task in computer vision, large scale image geo-localization, in
this framework we proposed a new approach, which is also based on Dominant Set
clustering and its extensions, the approach is based on image matching, we
first collect candidate matches based of their local feature matching and
later we use Constrained Dominant Set Clustering to decide the best match from
the short listed candidates, Unlike most previous approach which use a simple
voting scheme.

  * •

Finally, the dissertation proposed a novel approach using some properties of
dominant sets clustering approach, for simultaneous clustering and outlier
detection. Unlike most (all) previous approaches the proposed method does not
require any prior knowledge of neither the number of clusters nor outliers.

The rest of the dissertation is structured as follows: In chapter 1, we
briefly introduce dominant set and constrained dominant set clustering
frameworks and present the newly proposed fast approach to extract constrained
dominant sets. In chapter 2, we present new approach for multi-target tracking
using Dominant Sets in a single camera scenario. In Chapter 3, we present a
robust multi-target multi-camera tracking approach using constrained dominant
sets. A new approach for large scale image geo-localization is presented in
chapter 4. Finally, in chapter 5, a novel method is proposed for detecting
outliers while extracting compact clusters.

###### Contents

  1. 1 Graph Theoretic Based Clustering Framework
    1. 1.1 Dominant set clusters and their properties
    2. 1.2 Constrained Dominant Set clustering.
    3. 1.3 Fast Approach for Solving Constrained Dominant Set Clustering
    4. 1.4 Summary
  2. 2 Multi-Object Tracking Using Dominant Sets
    1. 2.1 Introduction
    2. 2.2 Related Work
    3. 2.3 Multi-object Tracking through Dominant Set Clusters
      1. 2.3.1 Tracklet Generation in a Single Window
      2. 2.3.2 Tracklet Merging using DSC
    4. 2.4 Experiments
      1. 2.4.1 Experimental setup
      2. 2.4.2 Results on Static Camera Videos
      3. 2.4.3 Results on Moving Camera Videos
    5. 2.5 Summary
  3. 3 Multi-target tracking in multiple nonoverlapping cameras using constrained dominant sets
    1. 3.1 Introduction
    2. 3.2 Related Work
    3. 3.3 Overall Approach
      1. 3.3.1 Within-Camera Tracking
      2. 3.3.2 Across-Camera Tracking
      3. 3.3.3 Track Refinement
    4. 3.4 Experimental Results
      1. 3.4.1 Evaluation on DukeMTMC dataset:
      2. 3.4.2 Evaluation on MARS dataset:
      3. 3.4.3 Computational Time.
    5. 3.5 Summary
  4. 4 Large-scale Image Geo-Localization  Using Dominant Sets
    1. 4.1 Introduction
    2. 4.2 Related Work
    3. 4.3 Image Matching Based Geo-Localization
      1. 4.3.1 Dynamic Nearest Neighbor Selection and Query Feature Pruning
      2. 4.3.2 Multiple Feature Matching Using Dominant Sets
    4. 4.4 Post processing using constrained dominant sets
    5. 4.5 Experimental Results
      1. 4.5.1 Dataset Description
      2. 4.5.2 Quantitative Comparison With Other Methods
      3. 4.5.3 Analysis
    6. 4.6 Summary
  5. 5 Simultaneous Clustering and Outlier Detection using Dominant sets
    1. 5.1 Introduction
    2. 5.2 Enumerate Dominant Sets Obliterating Outliers
    3. 5.3 Experiments
      1. 5.3.1 Synthetic data
      2. 5.3.2 Real datasets
    4. 5.4 Summary
  6. 6 Conlusion

###### List of Figures

  1. 1.1 Dominant set example: (a) shows a compact set (dominant set), (b) node 4 is added which is highly similar to the set {1,2,3} forming a new compact set. (c) Node 5 is added to the set which has very low similarity with the rest of the nodes and this is reflected in the value $W_{\\{1,2,3,4,5\\}}(5)$.
  2. 2.1 Overview of the proposed approach
  3. 2.2 Toy example of sliding window approach. Bounding boxes denote detection responses, and the different colors represent different targets. The sliding window moves one frame per step. This figure is best viewed in color.
  4. 2.3 Illustration of tracklet generation in one temporal window;(a) shows the possible detection responses in the window; (b) shows the graph built between the detection responses; (c) shows the tracking result from one iteration, containing dominant sets of one target as a subgraph; (d) shows the obtained trajectory. This figure is best viewed in color.
  5. 2.4 Tracking result on PETS2009-S2L1 and TUD-Stadtmitte datasets. First two rows refer to PETS2009-S2L1 (first row represents our results, while second row represents the ground truth), wherease the last two rows refers to TUD-Stadtmitte (with third row showing our results, while fourth showing the ground truth). This figure is best viewed in color.
  6. 2.5 Sample Tracking result on ETH-Sunny day sequence (first row represents our results, while second row represents the ground truth). This figure is best viewed in color.
  7. 3.1 A general idea of the proposed framework. (a) First, tracks are determined within each camera, then (b) tracks of the same person from different non-overlapping cameras are associated, solving the across-camera tracking. Nodes in (a) represent tracklets and nodes in (b) represent tracks. The $i^{th}$ track of camera $j$, $T^{i}_{j}$, is a set of tracklets that form a clique. In (b) each clique in different colors represent tracks of the same person in non-overlapping cameras. Similar color represents the same person. (Best viewed in color)
  8. 3.2 The figure shows within-camera tracking where short-tracklets from different segments are used as input to our first layer of tracking. The resulting tracklets from the first layer are inputs to the second layer, which determine a tracks for each person. The three dark green short-tracklets ($s_{1}^{2},s_{1}^{10},s_{1}^{7}$), shown by dotted ellipse in the first layer, form a cluster resulting in tracklet ($t_{1}^{2}$) in the second layer, as shown with the black arrow. In the second layer, each cluster, shown in purple, green and dark red colors, form tracks of different targets, as can be seen on the top row. tracklets and tracks with the same color indicate same target. The two green cliques (with two tracklets and three tracklets) represent tracks of the person going in and out of the building (tracks $T^{p}_{1}$ and $T^{2}_{1}$ respectively)
  9. 3.3 Exemplar graph of tracks from three cameras. $T^{i}_{j}$ represents the $i^{th}$ track of camera $j$. Black and colored edges, respectively, represent within- and across-camera relations of tracks. Colours of the nodes depict track IDs, nodes with similar colour represent tracks of the same person, and the thick lines show both within- and across-camera association.
  10. 3.4  Camera topology for DukeMTMC dataset. Detections from the overlapping fields of view are not considered. More specifically, intersection occurred between camera (8 & 2) and camera (5 & 3).
  11. 3.5 Sample qualitative results of the proposed approach on DukeMTMC dataset. Bounding boxes and lines with the same color indicate the same target (Best viewed in color).
  12. 3.6 The results show the performance of our algorithm on MARS (both using CNN + XQDA) when the final ranking is done using membership score (left) and using pairwise euclidean distance (right).
  13. 3.7 CPU time taken for each track association using our proposed fast approach (FCDSC - fast CDSC) and CDSC.
  14. 3.8 The ratio of CPU time taken between CDSC and proposed fast approach (FCDSC), computed as CPU time for CDSC/CPU time for FCDSC.
  15. 4.1 Overview of the proposed method.
  16. 4.2 Exemplar output of the dominant set framework: Left: query, Right: each row shows corresponding reference images from the first, second and third local solutions (dominant sets), respectively, from top to bottom. The number under each image shows the frequency of the matched reference image, while those on the right side of each image show the min-max normalized scores of HSV, CNN6, CNN7 and GIST global features, respectively. The filled colors circles on the upper right corner of the images are used as reference IDs of the images.
  17. 4.3 Exemplar output of the dominant set framework: Left: query, Right: each row shows corresponding reference images of the first, second and third local solutions (dominant sets), respectively, from top to bottom. The number under each image shows the mode of the matched reference image, while those on the right of each image show the min-max normalized scores of HSV, CNN6, CNN7 and GIST global features, respectively.
  18. 4.4 Exemplar graph for post processing. Top left: reduced graph for Fig. 4.2 which contains unique matched reference images. Bottom left: Part of the full graph which contains the gray circled nodes of the reduced graph and the query. Top right: corresponding affinity of the reduced graph. Bottom right: The outputs of nearest neighbor approach, consider only the node’s pairwise similarity, (KNN($\mathcal{Q}$)=node 3 which is the dark red node) and constrained dominant sets approach ($\mathcal{CDS(Q)}$ = node 2 which is the yellow node).
  19. 4.5 The top four rows are sample street view images from eight different places of WorldCities dataset. The bottom two rows are sample user uploaded images from the test set.
  20. 4.6 Comparison of our baseline (without post processing) and final method, on overall geo-localization results, with state-of-the-art approaches on the first dataset (102K Google street view images).
  21. 4.7 The ratio of CPU time taken between GMCP based geo-localization [178] and our approach, computed as CPU time for GMCP/CPU time for DSC.
  22. 4.8 Comparison of overall geo-localization results using DSC with and without post processing and state-of-the-art approaches on the WorldCities dataset.
  23. 4.9 Sample qualitative results taken from Pittsburgh area. The green ones are the ground truth while yellow locations indicate our localization results.
  24. 4.10 Geo-localization results using different number of NN
  25. 4.11 The effectiveness of constrained dominant set based post processing step over simple voting scheme.
  26. 4.12 Comparison of geo-localization results using different global features for our post processing step.
  27. 5.1  Examplar plots: Left: Original data points with different colors which show possible clusters. Right: Extracted clusters and their cohesiveness measures, $\mathcal{C}$ with affinity $(\mathcal{A})$ and $(\mathcal{CL})$ with the learned affinity $(\mathcal{S})$
  28. 5.2 Results of the algorithm on synthetic datasets with respect to increasing number of outliers ($l$). While fixing parameters as $k$ = 10, $m$ = 100, $d$ = 32, and $\sigma$ = 0.2
  29. 5.3 Results of the algorithm on synthetic datasets with respect to increasing dimension ($d$). While fixing parameters as $k$ = 10, $m$ = 100, $l$ = 100, and $\sigma$ = 0.1
  30. 5.4 Results of the algorithm on synthetic datasets with respect to the standard deviation used to generate the data ($\sigma$). While fixing parameters as $k$ = 10, $m$ = 100, $l$ = 100, and $d$ = 32

###### List of Tables

  1. 2.1 Tracking results on PETS2009-S2L1 sequence. For all approaches the number of ground truth (GT) trajectories is the same (19).
  2. 2.2 Tracking results on TUD-Stadtmitte sequence. For all approaches the number of ground truth (GT) trajectories is the same (10).
  3. 2.3 Tracking results on ETH-Sunny day sequence. For all approaches the number of ground truth (GT) trajectories is the same (30).
  4. 3.1 The results show detailed (for each camera C1 to C8) and average performance (Av) of our and state-of-the-art approach [128] on the Test-Easy sequence of DukeMTMC dataset.
  5. 3.2 The results show detailed (for each camera) and average performance of our and state-of-the-art approach [128] on the Test-Hard sequence of DukeMTMC dataset.
  6. 3.3 Multi-camera performance of our and state-of-the-art approach [128] on the Test-Easy sequence of DukeMTMC dataset.
  7. 3.4 Multi-Camera performance of our and state-of-the-art approach [128] on the Test-Hard sequence of DukeMTMC dataset.
  8. 3.5 The table shows the comparison (based on rank-1 accuracy) of our approach with the state-of-the-art approaches: SDALF [50], HLBP [168], BoW [190], BCov [97], LOMO [90], HOG3D [82] on MARS dataset.
  9. 3.6 The results show performance of our(using pairwise distance and membership score) and state-of-the-art approach [189] in solving within- and across-camera ReID using average precision on MARS dataset using CNN feature and different distance metrics.
  10. 4.1 Results of the experiment, done on the 102k Google street view images (Dts1) and WorldCities (Dts2) datasets, to see the impact of the post-processing step when the candidates of reference images are obtained by other image retrieval algorithms
  11. 5.1 Results on SHUTTLE dataset with fixed $l$ and varying $K$
  12. 5.2 Results on SHUTTLE dataset with fixed $k$ varying $l$
  13. 5.3 Results on KDD-CUP dataset with fixed number of outliers while varying cluster number

##  Chapter 1 Graph Theoretic Based Clustering Framework

The problem of clustering consists in organizing a set of objects into
clusters (groups, subsets, or categories), in a way that objects in the same
cluster should be similar (internal homogeneity), and dissimilar ones
organized into different cluster (external Inhomogeneity).

In particular clustering algorithms are distinguished in two main classes:
feature and similarity (pairwise) -based clustering. In feature-based
clustering, objects are represented as points in a metric space with distances
reflecting the dissimilarity relations. While in similarity-based clustering,
objects are described indirectly by their respective similarity relations. In
numerous real-world application domains, it is not possible to find
satisfactory features, but it is more natural to provide a measure of
similarity. For example, when features consist of both continuous and
categorical variables or when the objects to be classified are represented in
terms of graphs or structural representations.

A classical approach to pairwise clustering uses concepts and algorithms from
graph theory [71, 46]. Certainly, it is natural to map the data to be
clustered to the nodes of a weighted graph with edge weights representing
similarity relations. These methods are of significant interest since they
cast clustering as pure graph-theoretic problems for which a solid theory and
powerful algorithms have been developed.

Graph-theoretic algorithms basically consist of searching for certain
combinatorial structures in the similarity graph, such as a minimum spanning
tree [175] or a minimum cut [166] and, a complete subgraph (clique) [71].
Authors in [7, 124], argue that the maximal clique is the strictest definition
of a cluster. Authors in [110, 112], proposed dominant set clustering
framework which generalizes the maximal clique problem to an edge weighted
graphs and later authors in [183], proposed an approach which generalizes
dominant set framework.

In this dissertation, we used Dominant set clustering and its extension,
Constrained dominant set clustering, approach to solve different problems in
computer vision and patter recognition. In the rest of this chapter, we will
briefly introduce these clustering frameworks and present newly proposed
faster approach to extract constrained dominant sets from the graph, which is
linear in complexity.

### 1.1 Dominant set clusters and their properties

The theoretical formulation of dominant set clustering has been introduced in
[110, 112]. It is a combinatorial concept in graph theory that generalizes the
notion of the maximal clique to edge-weighted graphs. We can represent the
data to be clustered as an undirected edge-weighted graph $G=(V,E,\omega)$
with no self-loops, where $V=\\{1,...,n\\}$ is the set of vertex which
corresponds to data points, $E\subseteq V\times V$ is the edge set
representing neighborhood relationships, and
$\omega:E\rightarrow\mathbb{R}_{+}^{*}$ is the (positive) weight function
which quantifies the similarity of the linked objects. As customary, we
represent the graph $G$ with the corresponding weighted adjacency (or
similarity) matrix, which is the $n\times n$ nonnegative, symmetric matrix

$\mathtt{A}=(a_{ij})$ (1.1)

where:

$a_{ij}=\begin{cases}\omega(i,j),&\text{ if }i\neq j\text{ and }(i,j)\in E\\\
0,&\text{ if }i=j\end{cases}$

Since there are no self-loop in graph $G$, all entries on the main diagonal of
$\mathtt{A}$ are zero. In an attempt to formally capture this notion, we need
some notations and definitions.

Let $S\subseteq V$ be a non-empty subset of vertices and $i\in V$. The
(average) weighted degree of $i$ w.r.t. $S$ is defined as:

$AWDeg_{S}(i)=\frac{1}{|S|}\sum\limits_{j\in S}a_{i,j}$ (1.2)

Moreover, when $j\notin S$, we can measure similarity between nodes $j$ and
$i$, with respect to the average similarity between node $i$ and its neighbors
in $S$ as:

$\phi_{S}(i,j)=a_{i,j}-AWDeg_{S}(i).$ (1.3)

We can compute the weight of $i\in S$ w.r.t. $S$ as:

$w_{S}(i)=\begin{cases}1&\text{if $|S|=1$}\\\ \sum\limits_{j\in
S\backslash\\{i\\}}\phi_{S\backslash\\{i\\}}(j,i)w_{S\backslash\\{i\\}}(j)&\text{$otherwise$}\end{cases}$
(1.4)

Here, we can compute the total weight of the set $S$, $W(S)$, by summing up
each weights $w_{s}(i)$. From this recursive characterization of the weights
we can obtain a measure of the overall similarity between a vertex $i$ and
$S\setminus\\{i\\}$ w.r.t the overall similarity among $S\setminus\\{i\\}$,
and in [110, 112] characterizes a set $S$ as dominant set if it satisfies the
following two conditions:

  1. 1.

$w_{S}(i)>0$, for all $i\in S$.

  2. 2.

$w_{S\bigcup{i}}(i)<0$, for all $i\notin S$.

It is evident from the definition that a dominant set satisfies the two basic
properties of a cluster: internal coherence and external incoherence.
Condition 1 indicates that a dominant set is internally coherent, while
condition 2 implies that this coherence will be destroyed by the addition of
any vertex from outside. In other words, a dominant set is a maximally
coherent set of data.

Example: Let us consider a graph with nodes $\\{1,2,3\\}$, which forms a
coherent group (dominant set) with edge weights 20, 21 and 22 as shown in Fig.
1.1(a). Now, let us try to add a node $\\{4\\}$ to the graph which is highly
similar to the set {1,2,3} with edge weights of 30, 35 and 41 (see Fig.
1.1(b)). Here, we can see that adding node {4} to the set increases the
overall similarity of the new set {1,2,3,4}, that can be seen from the fact
that the weight associated to the node {4} with respect to the set {1,2,3,4}
is positive, $(W_{\\{1,2,3,4\\}}(4)>0)$. On the contrary, when adding node {5}
which is less similar to the set {1,2,3,4} (edge weight of 1 - Fig. 1.1(c))
the overall similarity of the new set {1,2,3,4,5} decreases, since we are
adding to the set something less similar with respect to the internal
similarity. This is reflected by the fact that the weight associated to node
{5} with respect to the set {1,2,3,4,5} is less than zero
$(W_{\\{1,2,3,4,5\\}}(5)<0)$.

From the definition of a dominant set the set {1,2,3,4} (Fig. 1.1 (b)) forms a
dominant set, as it satisfies both criteria (internal coherence and external
incoherence). While the weight associated to the node out side of the set
(dominant set) is less than zero, $W_{\\{1,2,3,4,5\\}}(5)<0$.

Figure 1.1: Dominant set example: (a) shows a compact set (dominant set), (b)
node 4 is added which is highly similar to the set {1,2,3} forming a new
compact set. (c) Node 5 is added to the set which has very low similarity with
the rest of the nodes and this is reflected in the value
$W_{\\{1,2,3,4,5\\}}(5)$.

The main result presented in [110, 112] establishes an intriguing one-to-one
correspondence between dominant sets and strict local maximizers of the
problem:

$\text{max}\quad\mathbf{x}^{T}\mathtt{A}\mathbf{x}\quad\text{s.t.}\quad\mathbf{x}\in\Delta$
(1.5)

where $\Delta=\\{\mathbf{x}\in\mathbb{R}^{n}\leavevmode\nobreak\
:\leavevmode\nobreak\ \sum_{i}\mathbf{x}_{i}=1,\text{ and }\mathbf{x}_{i}\geq
0\text{ for all }i=1\ldots n\\}$ is the standard simplex of $\mathbb{R}^{n}$.
Moreover, in [110, 112] it is proven that if $S$ is a dominant set, then its
weighted characteristic vector $X^{S}$, defined below, is a strict local
solution of the problem (1.5):

$\mathbf{x}_{i}^{S}=\begin{cases}\frac{w_{S}(i)}{W(S)},&\text{if\quad$i\in
S$},\\\ 0,&\text{otherwise}\end{cases}$

Conversely, under mild conditions, it turns out that if $\mathbf{x}$ is a
strict local solution of problem (1.5), then its ”support” $S=\\{i\in
V\leavevmode\nobreak\ :\leavevmode\nobreak\ x_{i}>0\\}$ is a dominant set. By
virtue of this result, we can find a dominant set by first localizing a
solution of problem (1.5) with an appropriate continuous optimization
technique, and then picking up the support set of the found solution. In this
sense, we indirectly perform combinatorial optimization via continuous
optimization.

The standard approach for finding the local maxima of problem (1.5), as used
in [112], is to use replicator dynamics a well-known family of algorithms from
evolutionary game theory inspired by Darwinian selection processes. Let
$\mathtt{A}$ be a non-negative real-valued $n\times n$ matrix, the discrete
version of the dynamics is defined as follows:

$\mathbf{x}_{i}^{(t+1)}=\mathbf{x}_{i}^{(t)}\frac{(\mathtt{A}\mathbf{x}^{(t)})_{i}}{\mathbf{x}^{(t)^{\prime}}\mathtt{A}\mathbf{x}^{(t)}}$
(1.6)

for $i=1,\ldots,n$.

Variety of StQP applications [12, 105, 112, 113, 153] have proven the
effectiveness of replicator dynamics. However, its computational complexity,
which is $O(n^{2})$ for problems involving $n$ variables, prevents it from
being used in large-scale applications. Its exponential variant, though it
reduces the number of iterations needed for the algorithm to find a solution,
suffers from a per-step quadratic complexity.

In this work, we adopt a new class of evolutionary game dynamics called
infection-immunization dynamics (InImDyn), which have been shown to have a
linear time/space complexity for solving standard quadratic programs. In
[132], it has been shown that InImDyn is orders of magnitude faster but as
accurate as the replicator dynamics.

Algorithm 1 Find Equilibrium($\mathtt{B}$,$\mathbf{x}$,$\tau$)

Input: $n\times n$ payoff matrix $\mathtt{B}$, initial distribution
$\mathbf{x}\in\Delta$ and tolerance $\tau$.
Output: Fixed point $\mathbf{x}$

1:while $\epsilon(\mathbf{x})>\tau$ do

2:$\mathbf{y}\leftarrow\mathcal{S}(\mathbf{x})$

3:$\delta\leftarrow 1$

4: if ${(\mathbf{y}-\mathbf{x})^{\top}\mathtt{B}(\mathbf{y}-\mathbf{x})}<0$
then

5:
$\delta\leftarrow\min\left\\{\frac{(\mathbf{x}-\mathbf{y})^{\top}\mathtt{B}\mathbf{x}}{{(\mathbf{y}-\mathbf{x})^{\top}\mathtt{B}(\mathbf{y}-\mathbf{x})}},1\right\\}$

6: end if

7: $\mathbf{x}\leftarrow\delta(\mathbf{y}-\mathbf{x})+\mathbf{x}$

8:end while

9:return $\mathbf{x}$

The dynamics, inspired by infection and immunization processes summarized in
Algorithm (1), finds the optimal solution by iteratively refining an initial
distribution $\mathbf{x}\in\Delta$. The process allows for invasion of an
infective distribution $\mathbf{y}\in\Delta$ that satisfies the inequality
$(\mathbf{y}-\mathbf{x})^{\top}\mathtt{A}\mathbf{x}>0$, and combines linearly
$\mathbf{x}$ and $\mathbf{y}$ (line 7 of Algorithm (1)), thereby engendering a
new population $\mathbf{z}$ which is immune to $\mathbf{y}$ and guarantees a
maximum increase in the expected payoff.

A selective function, $\mathcal{S}(\mathbf{x})$, returns an infective strategy
for distribution $\mathbf{x}$ if it exists, or $\mathbf{x}$ otherwise (line 2
of Algorithm (1)). Selecting a strategy $\mathbf{y}$ which is infective for
the current population $\mathbf{x}$, the extent of the infection,
$\delta_{\mathbf{y}}(\mathbf{x})$, is then computed in lines 3 to 6 of
Algorithm (1).

By reiterating this process of infection and immunization the dynamics drives
the population to a state that cannot be infected by any other strategy. If
this is the case then $\mathbf{x}$ is an equilibrium or fixed point under the
dynamics. The refinement loop of Algorithm (1) controls the number of
iterations allowing them to continue until $\mathbf{x}$ is with in the range
of the tolerance $\tau$ and we emperically set $\tau$ to $10^{-7}$. The range
$\epsilon(\mathbf{x})$ is computed as $\epsilon(\mathbf{x})$ =
$\sum\limits_{i\in
J}\textrm{min}\left\\{x_{i},(\mathtt{A}\mathbf{x})_{i}-\mathbf{x}^{\top}\mathtt{A}\mathbf{x}\right\\}^{2}$.

### 1.2 Constrained Dominant Set clustering.

As introduced in [183], constrained dominant set clustering, a constrained
quadratic optimization program, is an efficient and accurate approach, which
has been applied for interactive image segmentation, image geo-localization
[184] and multi-target tracking problems [152, 151, 150]. The approach
generalizes dominant set framework [112], which is a well known generalization
of the maximal clique problem to edge weighted graphs.

Given an edge weighted graph $G(V,E,\omega)$ and a constraint set
$\mathcal{Q}\subseteq V$, where $V,E$ and $\omega$, respectively, denote the
set of nodes (of cardinality $n$), edges and edge weights. The objective is to
find the sub-graph that contains all or some of elements of the constraint
set, which forms a coherent and compact set.

Consider a graph, $G$, with $n$ vertices (set $V$), and its weighted adjacency
matrix $\mathtt{A}$. Given a parameter $\alpha>0$, let us define the following
parametrized quadratic program:

$\begin{array}[]{ll}\text{maximize }&f_{\mathcal{Q}}^{\alpha}({\bf x})={\bf
x}^{\top}({\mathtt{A}}-\alpha I_{\mathcal{Q}}){\bf x},\\\ \text{subject
to}&\mathbf{x}\in\Delta,\end{array}$ (1.7)

where $\Delta=\\{{\bf x}\in\mathbb{R}^{n}:\sum_{i}x_{i}=1,\text{ and
}x_{i}\geq 0\text{ for all }i=1\ldots n\\}$, $\mathbf{x}$ contains a
membership score for each node and $I_{\mathcal{Q}}$ is the $n\times n$
diagonal matrix whose diagonal elements are set to 1 in correspondence to the
vertices contained in $V\setminus\mathcal{Q}$ (a set $V$ without the element
$\mathcal{Q}$) and to zero otherwise.

Let $\mathcal{Q}\subseteq V$, with $\mathcal{Q}\neq\emptyset$ and let
$\alpha>\lambda_{\max}({\mathtt{A}}_{V\setminus\mathcal{Q}})$, where
$\lambda_{\max}({\mathtt{A}}_{V\setminus\mathcal{Q}})$ is the largest
eigenvalue of the principal submatrix of ${\mathtt{A}}$ indexed by the
elements of $V\setminus\mathcal{Q}$. If ${\bf x}$ is a local maximizer of
$f_{\mathcal{Q}}^{\alpha}$ in $\Delta$, then $\sigma({\bf
x})\cap\mathcal{Q}\neq\emptyset$, where, $\sigma({\bf x})=\\{i\in
V\leavevmode\nobreak\ :\leavevmode\nobreak\ x_{i}>0\\}$ .

The above result provides us with a simple technique to determine dominant set
clusters containing user-specified query vertices, $\mathcal{Q}$. Indeed, if
$\mathcal{Q}$ is a vertex selected by the user, by setting

$\alpha>\lambda_{\max}({\mathtt{A}}_{V\setminus\mathcal{Q}}),$ (1.8)

we are guaranteed that all local solutions of (1.7) will have a support that
necessarily contains elements of $\mathcal{Q}$.

### 1.3 Fast Approach for Solving Constrained Dominant Set Clustering

Constrained quadratic optimization program (1.7), can be solved using dynamics
from evolutionary game theory. The well-known standard game dynamics to
equilibrium selection, replicator dynamics, though efficient, poses serious
efficiency problems, since the time complexity for each iteration of the
replicator dynamics is $\mathcal{O}(n^{2})$, which makes it not efficient for
large scale data sets [183]. Rota Bulò et al. [132] proposed a new class of
evolutionary game dynamics, called Infection and Immunization Dynamics
(InfImDyn). InfImDyn solves the problem in linear time. However, it needs the
whole affinity matrix to extract a dominant set which, more often than not,
exists in local range of the whole graph. Dominant Set Clustering (DSC) [112]
is an iterative method which, at each iteration, peels off a cluster by
performing a replicator dynamics until its convergence. Efficient out-of-
sample [111], extension of dominant sets, is the other approach which is used
to reduce the computational cost by sampling the nodes of the graph using some
given sampling rate that affects the framework efficacy. Liu et al. [93]
proposed an iterative clustering algorithm, which operates in two steps:
Shrink and Expansion. These steps help reduce the runtime of replicator
dynamics on the whole data, which might be slow. The approach has many
limitations such as its preference of sparse graph with many small clusters
and the results are sensitive to some additional parameters. Another approach
which tries to reduce the computational complexity of the standard quadratic
program (StQP [14]) is proposed by [35].

All the above formulations, with their limitations, try to minimize the
computational complexity of StQP using the standard game dynamics, whose
complexity is $\mathcal{O}(n^{2})$ for each iteration.

In this work we propose a fast approach (listed in Algorithm 2), based on
InfImDyn approach which solves StQP in $\mathcal{O}(n)$, for the recently
proposed formulation, ${\bf x}^{\top}({\mathtt{A}}-\alpha I_{\mathcal{Q}}){\bf
x},$ which of-course generalizes the StQP.

InfImDyn is a game dynamics inspired by Evolutionary game theory. The dynamics
extracts a dominant set using a two-steps approach (infection and
immunization), that iteratively increases the compactness measure of the
objective function by driving the (probability) distribution with lower payoff
to extinction, by determining an ineffective distribution
$\mathbf{y}\in\Delta$, that satisfies the inequality
$(\mathbf{y}-\mathbf{x})^{\top}\mathtt{A}\mathbf{x}>0$, the dynamics combines
linearly the two distributions ($\mathbf{x}$ and $\mathbf{y}$), thereby
engendering a new population $\mathbf{z}$ which is immune to $\mathbf{y}$ and
guarantees a maximum increase in the expected payoff. In our setting, given a
set of instances (tracks, tracklets) and their affinity, we first assign all
of them an equal probability (a distribution at the centre of the simplex,
a.k.a. barycenter). The dynamics then drives the initial distribution with
lower affinity to extinction; those which have higher affinity start getting
higher, while the other get lower values. A selective function,
$\mathcal{S}(\mathbf{x})$, is then run to check if there is any infective
distribution; a distribution which contains instances with a better
association score. By iterating this process of infection and immunization the
dynamics is said to reach the equilibrium, when the population is driven to a
state that cannot be infected by any other distribution, that is there is no
distribution, whose support contains a set of instances with a better
association score. The selective function, however, needs whole affinity
matrix, which makes the InfImDyn inefficient for large graphs. We propose an
algorithm, that reduces the search space using the Karush-Kuhn-Tucker (KKT)
condition of the constrained quadratic optimization, effectively enforcing the
user constraints. In the constrained optimization framework [183], the
algorithm computes the eigenvalue of the submatrix for every extraction of the
compact sets, which contains the user constraint set. Computing eigenvalues
for large graphs is computationally intensive, which makes the whole algorithm
inefficient.

In our approach, instead of running the dynamics over the whole graph, we
localize it on the sub-matrix, selected using the dominant distribution, that
is much smaller than the original one. To alleviate the issue with the
eigenvalues, we utilize the properties of eigenvalues; a good approximation
for the parameter $\alpha$ is to use the maximum degree of the graph, which
of-course is larger than the eigenvalue of corresponding matrix. The
computational complexity, apart from eigenvalue computation, is reduced to
$\mathcal{O}(r)$ where $r$, which is much smaller than the original affinity,
is the size of the sub-matrix where the dynamics is run.

Let us summarize the KKT conditions for quadratic program reported in eq.
(1.7). By adding Lagrangian multipliers, $n$ non-negative constants
$\mu_{1},....,\mu_{n}$ and a real number $\lambda$, its Lagrangian function is
defined as follows:

$\mathcal{L}(x,\mu,\lambda)=f_{\mathcal{Q}}^{\alpha}({\bf
x})+\lambda\left(1-\sum\limits_{i+1}^{n}x_{i}\right)+\sum\limits_{i+1}^{n}\mu_{i}x_{i}.$

For a distribution $x\in\Delta$ to be a KKT-point, in order to satisfy the
first-order necessary conditions for local optimality [96], it should satisfy
the following two conditions:

$2*[(\mathtt{A}-\alpha I_{\mathcal{Q}}){\bf x}]_{i}-\lambda+\mu_{i}=0,$

for all $i=1\ldots n$, and

$\sum_{i=1}^{n}x_{i}\mu_{i}=0\leavevmode\nobreak\ .$

Since both the $x_{i}$ and the $\mu_{i}$ values are nonnegative, the latter
condition is equivalent to saying that $i\in\sigma({\bf x})$ which implies
that $\mu_{i}=0$, from which we obtain:

$[(\mathtt{A}-\alpha I_{\mathcal{Q}}){\bf x}]_{i}\leavevmode\nobreak\
\begin{cases}\leavevmode\nobreak\ =\leavevmode\nobreak\
\lambda/2,\leavevmode\nobreak\ \mbox{ if }i\in\sigma({\bf x})\\\
\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \lambda/2,\leavevmode\nobreak\
\mbox{ if }i\notin\sigma({\bf x})\end{cases}$ (1.9)

We then need to define a Dominant distribution

######  Definition 1.

A distribution ${\bf y}\in\Delta$ is said to be a dominant distribution for
${\bf x}\in\Delta$ if

$\left\\{\sum\limits_{i,j=1}^{n}x_{i}y_{j}a_{ij}-\alpha
x_{i}y_{j}\right\\}>\left\\{\sum\limits_{i,j=1}^{n}x_{i}x_{j}a_{ij}-\alpha
x_{i}x_{j}\right\\}$ (1.10)

Let the ”support” be $\sigma({\bf x})=\\{i\in V\leavevmode\nobreak\
:\leavevmode\nobreak\ x_{i}>0\\}$ and $e_{i}$ the $i^{th}$ unit vector (a zero
vector whose $i^{th}$ element is one).

######  Proposition 1.

Given an affinity $\mathtt{A}$ and a distribution ${\bf x}\in\Delta$, if
$(\mathtt{A}{\bf x})_{i}>{\bf x}^{\prime}\mathtt{A}{\bf x}-\alpha{\bf
x}^{\prime}_{\mathcal{Q}}{\bf x}_{\mathcal{Q}},\mbox{for}\;i\notin\sigma({\bf
x})$,

  1. 1.

${\bf x}$ is not the maximizer of the parametrized quadratic program of (1.7)

  2. 2.

$e_{i}$ is a dominant distribution for ${\bf x}$

###### Proof.

To show the first condition holds: Let’s assume ${\bf x}$ is a KKT point

${\bf x}^{\top}({\mathtt{A}}-\alpha I_{\mathcal{Q}}){\bf
x}=\sum\limits_{i=1}^{n}x_{i}[(\mathtt{A}-\alpha I_{\mathcal{Q}}){\bf x}]_{i}$

Since x is a KKT point

${\bf x}^{\top}({\mathtt{A}}-\alpha I_{\mathcal{Q}}){\bf
x}=\sum\limits_{i=1}^{n}x_{i}*\lambda/2=\lambda/2$

From the second condition, we have:

$[(\mathtt{A}-\alpha I_{\mathcal{Q}}){\bf x}]_{i}\leq\lambda/2={\bf
x}^{\top}({\mathtt{A}}-\alpha I_{\mathcal{Q}}){\bf x}$

Since $i\notin\sigma({\bf x})$

$(\mathtt{A}{\bf x})_{i}\leq{\bf x}^{\top}({\mathtt{A}}-\alpha
I_{\mathcal{Q}}){\bf x}$

Which concludes the proof showing that the inequality does not hold.

For the second condition, if $e_{i}$ is a dominant distribution for ${\bf x}$,
it should satisfy the inequality

$\left\\{e_{i}^{\top}({\mathtt{A}}-\alpha I_{\mathcal{Q}}){\bf
x}\right\\}>\left\\{{\bf x}^{\top}({\mathtt{A}}-\alpha I_{\mathcal{Q}}){\bf
x}\right\\}$

Since $i\notin\sigma({\bf x})$

$(\mathtt{A}x)_{i}>\left\\{{\bf x}^{\top}({\mathtt{A}}-\alpha
I_{\mathcal{Q}}){\bf x}\right\\}$

Which concludes the proof

∎

The proposition provides us with an easy-to-compute dominant distribution.

Let a function, $\mathcal{S}(\mathtt{A},x)$, returns a dominant distribution
for distribution, $x$, $\emptyset$ otherwise and
$\mathcal{G}(\mathtt{A},\mathcal{Q},x)$ returns the local maximizer of program
(1.7). We summarize the details of our proposed algorithm in Algorithm (2).

Algorithm 2 Fast CDSC

Input: Affinity $\mathtt{B}$, Constraint set $\mathcal{Q}$
Initialize ${\bf x}$ to the barycenter of $\Delta_{\mathcal{Q}}$
${\bf x}_{d}$ $\leftarrow$ ${\bf x}$, initialize dominant distribution
Output: Fixed point $\mathbf{x}$

1:while true do

2:${\bf x}_{d}$ $\leftarrow$ $\mathcal{S}(\mathtt{B},{\bf x})$, Find dominant
distribution for $x$

3: if ${\bf x}_{d}=\emptyset$ then break

4: end if

5:$\mathcal{H}$ $\leftarrow$ $\sigma({\bf x}_{d})\cup\mathcal{Q}$, subgraph
nodes

6:$\mathtt{A}\leftarrow\mathtt{B}_{\mathcal{H}}$

7:${\bf x}_{l}$ $\leftarrow$ $\mathcal{G}(\mathtt{A},\mathcal{Q},x)$

8:${\bf x}$ $\leftarrow$ ${\bf x}$*0

9:${\bf x}(\mathcal{H})$ $\leftarrow$ ${\bf x}_{l}$

10:end while

11:return $\mathbf{x}$

The selected dominant distribution always increases the value of the objective
function. Moreover, the objective function is bounded which guaranties the
convergence of the algorithm.

### 1.4 Summary

In the first part of this chapter, we briefly introduced dominant set
clustering framework, a pairwise clustering approach, based on the notion of a
dominant set, which can be seen as an edge weighted generalization of a
clique. In the second part of the chapter, we have discussed an approach,
constrained dominant-set, that finds a collection of dominant set clusters
constrained to contain user-defined elements. The approach is based on some
properties of a family of quadratic optimization problems related to dominant
sets which show that, by properly selecting a regularization parameter that
controls the structure of the underlying function, we are able to ”force” all
solutions to contain user specified elements. Finally, We have presented a
novel fast approach to extract constrained dominant sets from the graph.

##  Chapter 2 Multi-Object Tracking Using Dominant Sets

Multi-object tracking is an interesting but challenging task in the field of
computer vision. Most previous works based on data association techniques
merely take into account the relationship between detection responses in a
locally limited temporal domain, which makes them inherently prone to identity
switches and difficulties in handling long-term occlusions. In this chapter, a
dominant set clustering based tracker is presented, which formulates the
tracking task as finding dominant sets on the constructed undirected edge
weighted graph. Meanwhile, temporal sliding window technique is utilized to
find tracklets and perform further merging on them. Our robust tracklet
merging step renders our tracker to long term occlusions with more robustness.
We present results on three different challenging datasets (i.e. PETS2009-S2L1
[47], TUD-standemitte [3] and ETH dataset (“sunny day” sequence) [48]), and
show significant improvements compared with several state-of-art methods.

### 2.1 Introduction

In order to ensure security of people and places by means of intelligent video
surveillance, the current trend is to increase the number of cameras
installed, both as a deterrent and to better monitoring the surveyed area. As
a consequence, we have witnessed an exponential increase of the data to be
watched and stored, requiring inevitably the use of automatic processing of
videos for scene analysis and understanding, both for real time and
a-posterior mining. In this way, a large variety of video data provided by
installed cameras is automatically analyzed for event detection, object and
people tracking as well as behaviour analysis. These actions offer a valid
support to investigations and crime detection.

Tracking targets is a challenging task: variations in the type of camera,
lighting conditions, scene settings (e.g. crowd or occlusions), noise in
images, variable appearance of moving targets and the point of view of the
camera must be accounted. Following multiple targets while robustly
maintaining data association remains a largely open problem. In [173] a large
experimental survey of various tracking approaches is presented, evaluating
suitability of each approach in different situations and with different
constraints (e.g assumptions on the background, motion model, occlusions,
etc.).

In recent years, due to significant improvements in object detection, several
researchers have proposed tracking methods that associate detection responses
into tracks, also referred as Association Based Tracking (ABT) techniques [3,
114, 116, 167, 170, 176] . An offline trained people detector is used to
generate detection responses, then tracklets are produced by linking these
responses and further associated into longer tracks. Similarity between
tracklets (i.e., the linking probabilities) is based on the motion smoothness
and appearance similarity. A Hungarian algorithm is often used to find the
global optimum [114, 167]. As compared to generative models, ABT is powerful
in assessing the presence of objects on the scene since it uses
discriminatively trained detectors, and needs no manual initialization.
Association-based approaches are prone to handling long-term occlusions
between targets and the complexity is polynomial with the number of targets
present. In order to differentiate between different targets, speed and
distance between tracklet pairs are often used as motion descriptors, whereas
appearance descriptors are often based on global or part-based color
histograms. Nevertheless, how to deal with motion in moving cameras and how to
better distinguish nearby targets remain key issues that limit the performance
of ABT.

In most of the ABT works [114, 165], the affinity score between detection
responses is computed once and kept fixed for all the later processes.
Conversely, in this proposal we develop a more flexible approach where
associations are made at two levels and the affinity measure is iteratively
refined based on the knowledge retrieved from the previous level. Moreover,
most of the previous methods [76, 9, 15, 142] use locally-limited temporal
information by focusing only on the pairwise relationship of the tracklets,
rather than applying data association among multiple tracklets over the whole
video in a global manner. As a consequence, existing approaches are prone to
identity switches (i.e., assigning different labels/IDs to the same target) in
cases where targets with small spatial and appearance differences move
together (which are rather common cases in real security videos).

In this chapter, a dominant set clustering based tracker is proposed, which
formulates the tracking task as the problem of finding dominant set clusters
in an auxiliary undirected edge-weighted graph. Unlike the previous
approaches, the proposed method for data association combines both appearance
and position information in a global manner. Object appearance is modelled
with a $9\times 9$ covariance matrix feature descriptor [118] and the relative
position between targets which is less influenced by the camera motion (angle
of the view) is computed. Since when the camera moves all the targets shift
together, this motion feature is quite invariant to camera movements, making
it a suitable representation applicable also to videos acquired by a moving
camera. Then, a temporal sliding window technique is utilized to find
tracklets and perform further merging on them. More specifically, given
detection responses found along the temporal window, we will represent them as
a graph in which all the detections in each frame are connected to all the
other detections in the other frames, regardless of their closeness in time,
and the edge weight depicts both appearance and position similarity between
nodes.

A two-level association technique follows: first, low-level association is
performed linking detection responses of the last two consecutive frames of
the window, which helps differentiating difficult pairs of targets in a
crowded scene; then, a global association is performed to form tracklets along
the temporal window. Finally, different tracklets of the same target are
merged to obtain the final trajectory.

The main contributions presented in this chapter are:

  * •

this chapter presents the first example of the use of dominant set clustering
for data association in multi-target tracking;

  * •

the two-level association technique proposed in this chapter allows us to
consider efficiently (also thanks to the superior performance of dominant set
clustering on identifying compact structures in graphs) the temporal window at
once, performing data association in a global manner; this helps in handling
long-lasting occlusions and target disapperance/reappearance more properly;

  * •

the consensus clustering technique developed to merge tracklets of the same
target and obtain the final trajectories is firstly introduced in this work,
although it has been used in different domains;

  * •

the proposed technique outperforms state-of-the-art techniques on various
publicly-available challenging data sets.

The rest of the chapter is organized as follows: related works are discussed
in Section 2.2; while Section 2.3 details our tracking framework (DSC tracker,
hereinafter). Experimental results are shown in Section 2.4, followed by
summary in section 2.5.

### 2.2 Related Work

Target tracking has been and still is an active research area in computer
vision and the amount of related literature is huge. Here, we concentrate on
some of earlier related works on tracking-by-detection (or ABT) methods.

Recently, tracking-by-detection methods [3, 114, 116, 167, 170, 176] become
the most exploited strategy for multi-target tracking. Obtaining multiple
detection responses from different frames, it performs data association to
generate consistent trajectories of multiple targets. As the number of frames
and targets increases, the complexity of data association problem also
increases along with it. As a consequence, most approaches aim to either
approximate the problem or to find locally-optimal solutions. Early methods
for multi-target tracking includes joint probabilistic data association (JPDA)
[52] and multi-hypothesis tracker (MHT) [127]. These techniques aim to find
optimal assignment over the heuristically-pruned hypothesis tree which is
built over several frames of the video.

More recently, researchers formalize data-association task as a matching
problem, in which detections in consecutive frames with similar motion pattern
and appearance are matched. Bipartite matching is the best known example of
such methods [172]: the method is temporally local (considering only two
frames) and utilizes Hungarian algorithm to find the solution. However, their
approach suffers from the limited-temporal-locality in cases where target
motion follows complex patterns, long-lasting occlusions are present or
targets with similar spatial and appearances exist. On the other hand, other
researchers in [176, 9, 186, 117] follow a method generally termed as global:
recently this approach is becoming more popular since it allows to remove the
limited-temporal-locality assumptions and this allows them to incorporate more
global properties of a target during optimization, which helps overcoming to
problems caused by noisy detection inputs.

In [186] data association problem is mapped into a cost-flow network with a
non-overlap constraint on trajectories. The optimal solution is found by a
min-cost flow algorithm in the network. In [117] the graph was defined similar
to [186] and showed that dynamic programming can be used to find high quality
sub-optimal solutions. The paper in [9] uses a grid of potential spatial
locations of a target and solve association problem using the K-Shortest Path
algorithm. Unfortunately, their method completely ignored appearance features
into the data association process, which result unwarranted identity switches
in complex scenes. To solve this limitation, the proposal in [141]
incorporates the global appearance constraints.

The above-mentioned global methods use simplified version of the problem by
only considering the relationships of detections in consecutive frames.
Despite the good performance of these methods, they came short in identifying
targets with similar appearance and spatial positions. Conversely, in recent
approaches [3, 176], no simplifications in problem formulation are made.
However, the proposed solutions are approximate due to the complexity of the
models. More specifically, authors in [3] proposed a continuous energy
minimization based approach in which the local minimization of a non-convex
energy function is performed exploiting the conjugate gradient method and
periodic trans-dimensional jumps. Compared to the aforementioned global
methods, this approach is more suitable for real-world tracking scenarios. On
the negative side, however, the solutions found to the non-convex function can
be attracted by local minima.

Recently, in [176] tracking problem is represented in a more complete manner,
where pairwise relationships between different detections across the temporal
span of the video are considered, such that a complete K-partite graph is
built. A target track will be represented by a clique (sub graph where all the
nodes are connected to each other), and the tracking problem is formulated as
a constraint maximum weight clique problem. However, since a greedy local
neighborhood search algorithm is followed to solve the problem, also this
approach is prone to the local minima case. Moreover, due to heuristic line
fitting approach used for outlier detection, the approach is prone to identity
switches, particularly when targets with close position move together.

### 2.3 Multi-object Tracking through Dominant Set Clusters

The overall scheme of the proposed system is depicted in Figure 2.1. Our
tracking framework is composed of three phases. As a first phase, objects of
interest need to be detected in each frame. In this chapter and corresponding
experiments in Section 2.4, we will refer to people as targets/objects of
interest, but the approach described in the following can be easily adapted to
different objects, supposed that a proper detector is available. In fact, any
detection technique can be used, although in this work we will use the well-
known people detector based on HOG proposed in [42]. Once objects are detected
as candidate bounding boxes, labels must be consistently assigned to different
instances of the same person. To this aim, in the second phase we employ a
“sliding temporal window” approach that iteratively constructs tracklets using
dominant set clustering. Finally, tracklets found along the whole video will
be merged to form a trajectory over the whole course of the video. The next
subsection will detail the last two phases, while readers interested in
details about first phase can refer to [42].

Figure 2.1: Overview of the proposed approach

In order to obtain more accurate results with more efficiency (i.e., lower
latency) it is vital to use sliding temporal windows to track targets.
Moreover, in the whole video there might be many targets most of which may not
have temporal overlap. As a consequence, performing a global optimization over
the whole video frames is not only impractical, but also inefficient due to
the huge search space and long latency, and also needless as many targets only
appear for some period but not on the whole course of the video.

To generate tracklets over the sliding temporal window, we use overlapping
neighbouring windows of frames. A toy example is given in Figure 2.2 to ease
the description of the approach. Given an input video and the detection
responses found within the first sliding window, tracking is performed within
the window. Then, the window is moved with the step of one frame at a time, so
that the new window will have more than 90% overlap with the previous one, and
the detection algorithm is applied on the new frame (number 4 in Fig. 2.2) so
to generate detection responses. At this point, a low-level association
algorithm (detailed in section 2.3.1) is employed to associate the detection
responses found in the last two frames (3 and 4) which have high appearance
similarities and small spatial distances. Then, a global association algorithm
(see section 2.3.1) is applied over all the frames in the current window in
order to create consistent tracklets. As a result, we are able to associate
efficiently and accurately the new frame detection responses to the right
tracklet.

It is worth noticing that selecting the size of the sliding window is crucial.
In fact, there is a trade-off between latency and accuracy: the bigger the
size (more frames) the more accurate the association task will be since more
data are available, but at the cost of higher latency (preventing online real-
time functionality); on the other hand, the smaller the size, the quicker the
results will be available, but with lower accuracy. In our experiments
(reported in section 2.4), we select a window size between 5 and 15 frames
depending on the dynamics as well as frame rate of the video: the faster the
frame rate, the bigger will be the size.

Figure 2.2: Toy example of sliding window approach. Bounding boxes denote
detection responses, and the different colors represent different targets. The
sliding window moves one frame per step. This figure is best viewed in color.

####  2.3.1 Tracklet Generation in a Single Window

As described above, the generation of tracklets in each single window is
obtained by applying a two-level association procedure, low-level and global.

Low-level association: Low-level association is performed to connect detection
responses found in the last two frames (which have high appearance
similarities and small spatial distances) into reliable tracklets (pair of
responses). This will enable us to separate responses which have very small
temporal differences and also distinguish between targets in complex scenes
with similar appearances, since the people will not drastically change in
appearance as well as position in just two consecutive frames.

Once extracted, the detection responses from the last two frames are
represented as nodes on a graph (as described in section 1.1), where edges
define connections between them and _edge weights reflect both spatial and
appearance similarity between nodes_. Let $G_{s}=(V_{s},E_{s},\omega_{s})$ be
our graph constructed using the detection responses of the last two frames
where $V_{s}=\\{v_{1}^{a},v_{2}^{b},.....\\}$ and the vertice $v^{i}_{j}$
represents the $j^{th}$ node from the $i^{th}$ frame. We denote for the sake
of simplicity with $a$ and $b$ the second last and last frames, respectively.
The set of edges $E_{s}=\\{(v_{q}^{i},v_{r}^{j})|(i\neq j)\\}$ is composed of
edges which connect only nodes coming from diffrent frames, while $\omega_{s}$
is the positive edge weight function.

As explained in section 1.1, given $n$ nodes, we can represent the graph with
a $n\times n$ affinity matrix $A_{s}=(a_{ij})$ where $a_{ij}=\omega(i,j),$ if
$(i,j)\in E_{s}$, and $a_{i,j}=0$ otherwise. Using this representation, one
association pair of responses of person $i$ is simply a dominant set
$G_{s}^{i}=(V_{s}^{i},E_{s}^{i},\omega_{s}^{i})$ in which $V_{s}^{i}$ contains
detection responses of only target $i$. Here the task is to find a pair of
detection responses (if any) which has maximum similarity. For this task we
utilized the DSC technique described in detail in section 1.1.

Global association: Low-level association results are useful to initialize
tracklet generation based on reliable associations (based on two consecutive
frames). However, it may happen that some people are not visible in the last
two frames of the current window. As a toy example, low-level association in
Figure 2.2(c) on frame 3 and 4 fails in creating an association for the pink
person, since it is visible only in frame 4 and not frame 3. As a consequence,
a global association algorithm ought to be used over the whole window. As a
result, the tracklet generated in the previous window for the pink person
(between frames 1 and 2 in Figure 2.2(b)) can be successfully associated to
the new detection in frame 4 (see Figure 2.2(d)).

Similarly to the low-level association case, we denote the detection responses
to be tracked in one temporal window of $f$ frames as an undirected edge
weighted graph $G_{n}=(V_{n},E_{n},\omega_{n})$ with no self loop, represented
as a similarity matrix $A_{n}$. One critical point in the global association
algorithm is that the knowledge about both the previous window and the low-
level association is exploited to update the new association matrix $A_{n}$.
In particular, let $G_{o}^{k}$ be the subgraph representing tracklet of person
$k$ with $V_{o}^{k}$ vertices from the previous window. Then, the similarity
matrix $A_{n}=(a_{ij})$ is computed as

$a_{i,j}=\begin{cases}1&\text{if $(i,j)\in V_{o}^{k}$ or $(i,j)\in
V_{s}^{k}$}\\\ 0&\text{$(i,j)\notin E_{n}$}\\\
\omega_{n}(i,j)&\text{$otherwise$}\end{cases}$ (2.1)

where $V_{s}^{k}$ represents tracklet of target $k$ obtained from low-level
association, $(i,j)\in V_{o}^{k}$ or $(i,j)\in V_{s}^{k}$ means both node $i$
and $j$ belong to same tracklet of $k^{th}$ target obtained from the previous
window or low-level association, respectively.

In order to capture the individual similarities in people (patches) of the
same target and differentiate between different targets, it is compulsory that
the graph is made using a meaningful and robust similarity measure. A node
$v^{i}_{j}$ is represented with a location feature $l^{i}_{j}$ , which is the
2-dimensional spatial coordinates of the bottom center and upper left corner
of the corresponding detection.

Moreover, we decided to model people appearance using covariance matrix
feature descriptors [118]. This representation has been adopted in various
approaches [39, 40, 94, 100] thanks to its robustness in capturing information
like color, shape and location and also to its scale and rotation invariance.
Considering $d$ different selected pixel features extracted independently from
the image patch, benefiting from being a low dimensional representation, the
resulting covariance matrix $C$ is a square symmetric matrix $d\times d$ where
the diagonal entries represent the variance of each feature and the non-
diagonal entries represent the correlations.

Let us consider Im as a three-channels color image and Y be the $W\times
H\times d$ dimensional image feature extracted from Im. Let
$Y(x,y)=\rho(Im,x,y)$, where the function $\rho$ could be any mapping such as
gradients, color, filter responses, intensity, etc.. Let
$\\{t_{i}\\}_{i=1...M}$ be the d-dimensional feature points inside Y, with
$M=W\times H$. The image Im is represented with the $d\times d$ covariance
matrix of the feature points:

$C_{R}=\dfrac{1}{M-1}\sum_{i=1}^{M}(t_{i}-\mu)(t_{i}-\mu)^{T}$ (2.2)

where vector $\mu$ represents the mean of the corresponding features of each
point in a region $R$.

In our case, we decided to model each pixel within a people patch with its HSV
color values, its position $(x,y)$, $G_{x}$ and $G_{y}$ which are the first
order derivatives of the intensities calculated through Sobel operator with
respect to $x$ and $y$, the magnitude $mag(x,y)$ =
$\sqrt{G_{x}^{2}+G_{y}^{2}}$ and the angle of the first derivative
$\Theta(x,y)=arctan\left(\dfrac{G_{y}}{G_{x}}\right)$. Therefore, each pixel
of the people (patch) is mapped to a 9-dimensional feature vector:
$t_{i}=[x\>;y\>;H\>;S\>;V\>;G_{x}\>;G_{y}\>;mag(x,y)\>;\Theta(x,y)]^{T}$.
Based on this 9-dimensional feature vector representation the covariance of a
patch is $9\times 9$ matrix.

The distance between covariance matrices is computed using technique proposed
in [118, 55] which is the sum of the squared logarithms of their generalized
eigenvalues. Formally, the distance between two matrices $C_{i}^{j}$ and
$C_{m}^{n}$ is expressed as:

$\varpi(C_{i}^{j},C_{m}^{n})=\sqrt{\sum_{k=1}^{d}ln^{2}\lambda_{k}(C_{i}^{j},C_{m}^{n})}$
(2.3)

where $\lambda_{k}(C_{i}^{j},C_{m}^{n})_{k=1....d}$ are the generalized
eigenvalues of $C_{i}^{j}$ and $C_{m}^{n}$.

The weight of an edge between two nodes, $\omega:E\rightarrow\mathbb{R}^{+}$,
represents both appearance and spatial similarities (correlation) between
detection responses and the distance between two nodes is computed as :

$D(v_{j}^{i},v_{m}^{n})=\sqrt{\kappa\cdot\varpi(C_{j}^{i},C_{m}^{n})^{2}+\iota\cdot
d(l_{j}^{i},l_{m}^{n})^{2}}$ (2.4)

where $d(l_{j}^{i},l_{m}^{n})=\|l_{j}^{i}-l_{m}^{n}\|^{2}$ ($l_{j}^{i}$ and
$l_{m}^{n}$ representing the location feature vectors of the corresponding
nodes) and $\kappa$ and $\iota$ are values which are used to control
contributions of appearance and location features, respectively.

The affinity between the two nodes is defined as:

$\omega(v_{j}^{i},v_{m}^{n})=\exp(-\dfrac{D(v_{j}^{i},v_{m}^{n})}{2\gamma^{2}})$
(2.5)

where $\varpi$ is the regularization term. The smaller the sigma, less likely
are the detection responses to be associated, leading to fewer identity
switches but more fragments (interruption of the correct trajectory) and vice
versa.

Our task of finding the tracklet of one target in one temporal window requires
to identify a target in each frame and then to represent the feasible solution
as a dominant set (subgraph) $G_{f}$ in which at most one node (detection
response) is selected from each frame’s detection responses which are highly
coherent and similar to each other. Therefore, we represent the dominant set
as a subgraph $G_{f}=(V_{f},E_{f},\omega_{f})$. We ought to note that the
feasible solution (tracklet) $G_{f}$ only contains the detection responses of
one target and not all visible detections found in the temporal window. In
Figure 2.3(c) we can see one feasible solution found from current temporal
window of size 3.

By solving DSC for the graph $G_{n}$ of the global association algorithm, we
will end up with the optimal solution that is a dominant set ($\equiv$
subgraph $G_{f}$) containing detections of one target, which corresponds to
the feasible solution with the most consistent and highly coherent in both
spatial and appearance features over the whole span of temporal window.
Moreover, in order to find the tracklets of all the people found in a temporal
window, the optimization problem (1.5) needs to be solved several times.
Therefore, at each iteration, the algorithm finds the tracklet which has the
highest internal coherency. Then, vertices selected in $G_{f}$ will be removed
from $G_{n}$ and the above optimization process is repeated to find the
tracklet for the next target, and so on until zero or few nodes remains in
$G_{n}$. This approach is commonly referred as “peeling off strategy”.

Figure 2.3: Illustration of tracklet generation in one temporal window;(a)
shows the possible detection responses in the window; (b) shows the graph
built between the detection responses; (c) shows the tracking result from one
iteration, containing dominant sets of one target as a subgraph; (d) shows the
obtained trajectory. This figure is best viewed in color.

####  2.3.2 Tracklet Merging using DSC

If a person is occluded or exits from the scene for a period which is longer
than the temporal window size, the association algorithm described in the
previous subsection will not work properly, since a new label/id will be
assigned to the person when he/she reappears in the scene. As a consequence,
we need to merge those tracklets representing the same target into one single
trajectory along different windows.

For this data association problem, we once again utilized the same DSC-based
data association method. It is worth emphasizing that merging different
tracklets of one person on different windows is by far the hardest task. In
fact, it is very common that the person’s appearance is changed when he/she
reappears in the scene, for both the possible changes in illumination
conditions and the different poses with which the person re-enters in the
scene. To solve this problem, we need a robust approach accounting for
different situations which might arise like: target might appear to the scene
heavily occluded and stay occluded for the most part of the tracklet; a target
might enter in the scene with a different pose but then might get back to
his/her original pose for the rest part resulting similar tracklets in their
(average) appearances similarity; etcetera. For this reason, it turns out that
there exists no a single approach or similarity measure capable to handle all
these situations carefully. Therefore, we borrow the idea from consensus
clustering [193, 160, 119]. Consensus clustering (also known as clustering
ensemble) combines different clustering techniques and able to exploit
advantages from all of them and to handle all (or most of) the situations
above.

First of all, we consider only tracklets of length greater than 10 nodes since
very short tracklets were considered as false positives. Then, three different
approaches are used concurrently:

  1. 1.

In the first approach, each tracklet is divided in two equal parts: each
tracklet partition is represented as a node in a graph and the weight between
the nodes (tracklets) is computed as a mean distance between their appearance
features. Let $I$ and $J$ be two tracklets ($\equiv$ nodes), then the distance
between the two tracklets is formulated as:

$D_{{I},{J}}=\frac{1}{|I|}\left\\{\sum\limits_{i\in
I}\frac{1}{|J|}\left(\sum\limits_{j\in J}\varpi(C_{i},C_{j})\right)\right\\}$
(2.6)

The similarity matrix is built as $A^{\mu}=(a_{IJ}^{\mu})$ where
$a_{IJ}^{\mu}=\exp(-D_{{I},{J}})$. This approach is adequate in merging two
tracklets (of the same person) where the target appears more or less with the
same appearance in both tracklets for the most part, since it depicts the mean
distance over their appearance similarity the approach is prone to few big
changes made in appearance. But the approach fails in cases where the target
appears in a totally different pose for most of the considered frames.

  2. 2.

The second approach again divides each tracklet in two equal parts,
represented as nodes in a graph. However, in this case the weight is computed
by taking the minimum of their mean distances on their appearance features
only:

$D_{{I},{J}}=\min\limits_{i\in I}\frac{1}{|J|}\left(\sum\limits_{j\in
J}\varpi(C_{i},C_{j})\right)$ (2.7)

The similarity matrix is built as: $A^{M}=(a_{IJ}^{M})$ where
$a_{IJ}^{M}=\exp(-D_{{I},{J}})$.

Unlike the previous technique this approach works best in merging tracklets
where the target makes a big change in appearance and stayed the same for the
most part of the tracklet. In such cases, taking the minimum distance between
their appearances is the best choice, supposed that there exist at least some
frames/nodes where the appearance is similar. This approach will come short in
cases where most of the targets have high appearance similarity between each
other, causing identity switches.

  3. 3.

The third approach represents each tracklet by means of their detection with
highest weighted characteristic vector value (strict local solution of the
optimization equation 1.5). In other words, the best representative detection
of each tracklet is selected for comparing with the other tracklets. The
distance between the nodes of the new graph will be computed by taking their
difference in appearance. More specifically, let us consider a node $i$ in a
tracklet $I$, $i\in I$, to be that with highest characteristic vector value:

$C_{i}=\operatornamewithlimits{\arg\,\max}_{i}\frac{w_{I}(i)}{W(I)}$ (2.8)

The similarity matrix is built as: $A^{C}=(a_{IJ}^{C})$ where
$a_{IJ}^{C}=\exp(-\gamma(C_{i},C_{j}))$.

In cases where the two separate tracklets are created due to occlusion between
people which lasts longer than the size of the temporal window, it is less
likely that the person will make a big change on his/her new appearance.
Hence, it will be enough to represent a tracklet with two representative
detection responses with the highest characteristic vector values. But yet
again this technique fails if the selected representative detection results to
be a bad representative (e.g., it can be partially occluded), generating
multiple identity switches.

DSC is performed three times, each using one of the different approaches
listed above ($A^{\mu}$,$A^{M}$ and $A^{C}$). The clustering results are then
combined in to a single affinity matrix according to the Evidence Accumulation
Paradigm [95]. We built a matrix $B=(b_{ij})$ known as _co-association matrix_
: where $b_{ij}=0$ if $i=j$, otherwise $b_{ij}=\varphi(i,j)$, being
$\varphi(i,j)$ the fraction of times object $i$ and object $j$ were clustered
together among all $C$ clustering results in the ensemble and computed as:

$\varphi(i,j)=\frac{1}{|C|}\sum\limits_{r=1}^{|C|}\delta(C_{r}(i),C_{r}(j))$
(2.9)

where $C_{r}(i)$ is the label of $i^{th}$ object in the $r^{th}$ clustering
result and $\delta(n,m)$ is Kronecker’s delta function, that is,
$\delta(n,m)=1$ if $n=m$ and 0 otherwise.

To get the final clustering result, we run the DSC on the co-association
matrix.

### 2.4 Experiments

####  2.4.1 Experimental setup

We evaluate our approach on three publicly available data sets: sequence S2L1
from PETS2009 benchmark [47], TUD-standemitte dataset [3], and ”sunny day”
sequence from ETH mobile dataset [49], which are commonly used by previous
multi-target tracking works. To be fair and transparent on the comparison, we
used publicly available detection responses [169, 171] and ground truth [88]
in all our experiments. We also used publicly available code [101] for the
evaluation.

Brief description of the datasets: PETS2009-S2L1-View one [47] consists of 795
frames and comprised of challenges like non-linear target motion, targets in
close proximity and several occlusions in the scene. TUD-Stadtmitte [3]
consists of 179 frames recorded in a busy pedestrian street with low camera
angle, which generates frequent occlusions. Both these datasets are recorded
using static cameras. On the contrary, ETH dataset (“sunny day” sequence) [48]
is recorded with a pair of moving cameras in a busy street scene. The cameras
move forward and have a panning motion at times, which potentially makes the
exploitation of known motion models less reliable. Most targets move with a
speed of 2-4 pixels per frame, whereas the camera exhibits a motion of around
20 pixels per frame. This causes imprecise results while using linear motion
estimations. However, the relative positions of the targets do not change
between two consecutive frames since all targets move according to the same
camera motion. The sequence contains 354 frames and people size detected on
image plane varies significantly. Similar to [87], we used the sequence from
the left camera. No ground plane information is used.

Parameter analysis: There is no fixed window size which will work for all the
datasets, rather depending on the dynamics and frame rate of the video.
Therefore, we set window size of 15,10 and 5 for PETS2009-S2L1, TUD-
standemitte and ETH-sunnyday sequences, respectively. Our algorithm performs
well in a wide range of $\gamma$ (the scaling parameter in eq. 2.5) from 0.2
to 3.0. The good invariance (or low sensitivity) to $\gamma$ parameter is due
to the exploitation of results from both the previous window and the low-level
association along the current window to update our affinity matrix, which
results in the replacement of most of the values of our affinity matrix (with
the value 1, if the two nodes belong to same cluster according to results from
previous window or low-level association and with the value 0 otherwise).

For PETS2009-S2L1 and TUD-standemitte, $\kappa$ and $\iota$ in eq. 2.4 (which
are factors for controlling the contributions of appearance and position
information, respectively) are typically set to one which will give equal
weight to appearance and position features. However, based on our experiments,
the appearance features are more informative than position in our formulation.
In fact, in many cases using appearance features only is sufficient for
tracklet generation. In the case of ETH-sunny day sequence, we set $\kappa$
and $\iota$ values to 1 and 1.25 respectively to get the best result. In fact,
since this sequence is recorded with a moving camera, large changes in poses
and sizes of the people are present and this results in significant changes in
their appearance. Consequently, appearance information is less informative
than positions in this case.

Evaluation methodology: The correct and fair evaluation of multi-target
tracking systems relies mainly on two issues: the definition of proper and
agreed evaluation metrics; and the use of publicly-available ground truth on
which the evaluation can be based.

Regarding the evaluation metrics, we adopted those defined in [101] which uses
the most widely accepted protocol CLEAR MOT [11]. CLEAR MOT defined several
values:

  * •

_Multi-Object Tracking Accuracy (MOTA)_ combines all error types (false
positives (FP), false negatives/missing detections (FN) and identity switches
(IDS)) - the higher the better;

  * •

_Multi-object Tracking Precision (MOTP)_ measures the normalized distance
between tracker output and ground truth location, i.e. the precision in the
bounding box (or center of gravity) localization - the higher the better;

  * •

_Mostly Tracked (MT)_ measures how many ground truth (GT) trajectories are
successfully tracked for at least 80% of frames - the higher the better;

  * •

_Mostly Lost (ML)_ measures how many of the ground truth (GT) trajectories are
tracked for less than 20% of the whole trajectory - the lower the better;

  * •

_identity switches_ (IDS): number of times that a tracked trajectory switches
its matched ground truth identity - the lower the better.

In addition to those metrics, we also compute the following values:

  * •

_False alarm per frame (FAF)_ measures the average false alarms per frame -
the lower the better;

  * •

_Precision_ (Prcsn) is the average of correctly matched detections per total
detections in the tracking result - the higher the better;

  * •

_Recall (Rcll)_ computes the average of matched detections per total
detections in the ground truth - the higher the better.

All the reported results in Tables 2.1 and 2.2 are generated using tracking
outputs provided by the authors [101] with the same overlap threshold for
CLEAR MOT metrics. Instead, quantitative results of the compared approach
reported in Table 2.3 are taken from [87].

Regarding the ground truth, in order to provide a common ground for further
comparison, we used the publicly-available detection responses from [171] for
PETS2009 and TUD datasets and those from [87] for ETH. As ground truth, for
all the datasets we used that provided in [88]. It is worth noting that we
achieved exactly the same results even when we used modified (stricter) ground
truths, assuring that all the people have one unique ID troughout the whole
video. In fact, it often happens that when a person disappears from the scene
(due to occlusions or because he/she exits temporary from the scene), when
he/she reappears a different ID is assigned (also in the public ground truth).
The stricter ground truth, instead, assigns the same ID, which is not always
the case in [88].

####  2.4.2 Results on Static Camera Videos

Let us first introduce the results in the two most used datasets for multi-
target tracking (PETS2009-S2L1 [47] and TUD-Stadtmitte [3]) which are recorded
with static cameras.

Our quantitative results on PETS2009-S2L1 are shown in Table 2.1. Compared
with up-to-date methods, our DSC tracker attains best performance on MOTA,
precision, IDs and FAF over the majority of the approaches in Table 2.1, while
keeping recall and MT comparable.

Some visual results are presented in Fig. 2.4, first two rows (first row shows
our results, while second row reports the ground truth). Even if targets
appear quite close and similar in appearance, our approach is still able to
maintain correct IDs, as in the case of targets 3 and 7 on frame 149 or
targets 3 and 8 on frame 149 and 161. Furthermore, thanks to our robust
tracklet merging step, our approach is capable to correctly identify a target
on his/her reappearance after a long absence from the scene, as in the case of
targets 1, 3, 4, 5 and 6 on frame 716. Please note that the ground truth
(second row of Fig. 2.4) contains different IDs when the targets reapper in
the scene (see also the comment reported above about the grund truth).

Table 2.1: Tracking results on PETS2009-S2L1 sequence. For all approaches the number of ground truth (GT) trajectories is the same (19). Method | MOTA(%) | MOTP(%) | Rcll(%) | Prcsn(%) | FAF | MT | ML | IDs
---|---|---|---|---|---|---|---|---
[117] | 81.8 | 71.5 | 89.2 | 96.6 | 0.19 | 17 | 0 | 97
[53] | 53.4 | 70.9 | 72.6 | 80.3 | 1.04 | 7 | 1 | 65
[102] | 90.8 | 74.2 | 97.1 | 94.4 | 0.34 | 18 | 0 | 26
[101] | 87.9 | 64.5 | 98.6 | 90.8 | 0.59 | 19 | 0 | 29
DSC | 90.0 | 56.8 | 91.7 | 98.5 | 0.08 | 17 | 0 | 15
Figure 2.4: Tracking result on PETS2009-S2L1 and TUD-Stadtmitte datasets. First two rows refer to PETS2009-S2L1 (first row represents our results, while second row represents the ground truth), wherease the last two rows refers to TUD-Stadtmitte (with third row showing our results, while fourth showing the ground truth). This figure is best viewed in color. Table 2.2: Tracking results on TUD-Stadtmitte sequence. For all approaches the number of ground truth (GT) trajectories is the same (10). Method | MOTA(%) | MOTP(%) | Rcll(%) | Prcsn(%) | FAF | MT | ML | IDs
---|---|---|---|---|---|---|---|---
[117] | 67.6 | 72.6 | 75.0 | 92.9 | 0.37 | 5 | 0 | 96
[53] | 60.0 | 56.5 | 83.7 | 78.7 | 1.46 | 7 | 0 | 12
[102] | 53.5 | 72.4 | 79.1 | 82.0 | 1.12 | 7 | 0 | 20
[101] | 69.7 | 53.4 | 74.7 | 94.3 | 0.29 | 6 | 0 | 4
DCS | 72.4 | 52.6 | 75.1 | 99.8 | 0.01 | 6 | 0 | 10
|  |  |  |  |  |  |  |

Quantitative results on TUD-Stadtmitte dataset are provided in Table 2.2. Our
method attains superior results in MOTA, precision and FAF while remaining
comparable in ML and IDs. However, our approach obtains relatively lower
performance in recall: this is mainly because DCS tracker focuses on assigning
the right person ID to detection responses generated by the people detector,
i.e. no motion model (linear or any other) for prediction of next locations
has been used. As a result, our method generates a higher number of false
negatives.

Fig. 2.4 shows some visual tracking results on TUD-Stadtmitte sequence (third
and fourth row). Our approach is able to maintain correct IDs, as in the case
of targets 4 and 8 on frame 61 or targets 10 and 11 on frame 104, regardless
of their similarity in position and appearance and the severe occlusions.

####  2.4.3 Results on Moving Camera Videos

Table 2.3 shows the results on ETH-Sunny day sequence recorded from moving
cameras. Compared with [87], our DSC tracker achieves best performance on
precision and false alarm per frame, while having relatively higher number of
identity switches. This is mainly due to the appearance and size of targets
which highly vary along with camera movement. However, the higher precision of
our approach shows that it is able to recover the correct IDs. Fig. 2.5 shows
few visual results of our method (first row shows our results, while second
row represents the ground truth). Even if people are fully occluded for a long
time and reappear, our approach is able to correctly re-identify the person,
as in the case of target 5 on frame 79, 98 and 316. We ought to note that the
ground truth (second row of Fig. 2.5) gives different IDs when the target
reappear after a long-lasting occlusion, as in the case of targets 8 and 29 on
frame 79 and 316, respectively.

Table 2.3: Tracking results on ETH-Sunny day sequence. For all approaches the number of ground truth (GT) trajectories is the same (30). Method | MOTA(%) | MOTP(%) | Rcll(%) | Prcsn(%) | FAF | MT | ML | IDS
---|---|---|---|---|---|---|---|---
[87] | - | - | 77.9 | 86.7 | 0.65 | 22 | 3 | 1
DSC | 61.5 | 66.8 | 71.4 | 89.4 | 0.45 | 19 | 3 | 8
Figure 2.5: Sample Tracking result on ETH-Sunny day sequence (first row
represents our results, while second row represents the ground truth). This
figure is best viewed in color.

### 2.5 Summary

In this chapter, a dominant set clustering based tracker is proposed, which
formulates the tracking task as finding dominant set (cluster) on the
constructed undirected edge weighted graph. The development of a complete
multi-target tracking using dominant set clustering is the main contribution
of this work. We utilized both information (appearance and position) for data
association in a global manner, avoiding the locally-limited approach
typically present in previous works. Experimental results compared with the
state-of-the-art tracking approaches show the superiority of our tracker,
especially in terms of MOTA and precision, as well as lower identity switches
in some cases. Generally speaking, the tradeoff between precision and recall
in tracking is hard to balance, thus resulting in lower performance on one of
the two values. Our claim is that precision is more relevant for tracking
purposes and that assigning the right ID to targets (people) when they re-
appear after an occlusion or the exit from the scene should be the key
objective of tracking systems.

Regarding the efficiency of the proposed approach, for a window size of 10
frames with approximately 10 pedestrians, processing a frame using the full
proposed framework, excluding human detection, takes an average time of 1.6
and 0.003 s for affinity matrix generation and tracklet generation,
respectively. Moreover, it takes only 0.001 s for tracklet merging step. These
values are computed by running a non-optimised Matlab code on a core i5 2.5
GHz machine. Using an optimised parallel implementation in C, the algorithm is
likely to work in real time.

As future directions of research, we first would extend the methodology to
multi-camera setups. As a feeling, we believe that our approach will be
straightforward to extend multiple cameras, since no motion or temporal
information are used in it. Another possible future work consists in
evaluating different similarity measures as well as to consider different
types of targets instead of people.

##  Chapter 3 Multi-target tracking in multiple nonoverlapping cameras using
constrained dominant sets

In this chapter, we present a unified three-layer hierarchical approach for
solving tracking problems in multiple non-overlapping cameras. Given a video
and a set of detections (obtained by any person detector), we first solve
within-camera tracking employing the first two layers of our framework and,
then, in the third layer, we solve across-camera tracking by merging tracks of
the same person in all cameras in a simultaneous fashion. To best serve our
purpose, a constrained dominant sets clustering (CDSC) technique, a
parametrized version of standard quadratic optimization, is employed to solve
both tracking tasks. The tracking problem is caste as finding constrained
dominant sets from a graph. That is, given a constraint set and a graph, CDSC
generates cluster (or clique), which forms a compact and coherent set that
contains a subset of the constraint set. In addition to having a unified
framework that simultaneously solves within- and across-camera tracking, the
third layer helps link broken tracks of the same person occurring during
within-camera tracking. We have tested this approach on a very large and
challenging dataset (namely, MOTchallenge DukeMTMC [128, 145, 129]) and show
that the proposed framework outperforms the current state of the art. Even
though the main focus of this work is on multi-target tracking in non-
overlapping cameras, proposed approach can also be applied to solve re-
identification problem. Towards that end, we also have performed experiments
on MARS [189], one of the largest and challenging video-based person re-
identification dataset, and have obtained excellent results. These experiments
demonstrate the general applicability of the proposed framework for non-
overlapping across-camera tracking and person re-identification tasks.

### 3.1 Introduction

As the need for visual surveillance grow, a large number of cameras have been
deployed to cover large and wide areas like airports, shopping malls, city
blocks etc.. Since the fields of view of single cameras are limited, in most
wide area surveillance scenarios, multiple cameras are required to cover
larger areas. Using multiple cameras with overlapping fields of view is costly
from both economical and computational aspects. Therefore, camera networks
with non-overlapping fields of view are preferred and widely adopted in real
world applications.

In the work presented in this chapter, the goal is to track multiple targets
and maintain their identities as they move from one camera to the another
camera with non-overlapping fields of views. In this context, two problems
need to be solved, that is, within-camera data association (or tracking) and
across-cameras data association by employing the tracks obtained from within-
camera tracking. Although there have been significant progresses in both
problems separately, tracking multiple target jointly in both within and
across non-overlapping cameras remains a less explored topic. Most approaches,
which solve multi-target tracking in multiple non-overlapping cameras [18, 34,
73, 75, 162, 115, 80, 31], assume tracking within each camera has already been
performed and try to solve tracking problem only in non-overlapping cameras;
the results obtained from such approaches are far from been optimal [162].

Figure 3.1: A general idea of the proposed framework. (a) First, tracks are
determined within each camera, then (b) tracks of the same person from
different non-overlapping cameras are associated, solving the across-camera
tracking. Nodes in (a) represent tracklets and nodes in (b) represent tracks.
The $i^{th}$ track of camera $j$, $T^{i}_{j}$, is a set of tracklets that form
a clique. In (b) each clique in different colors represent tracks of the same
person in non-overlapping cameras. Similar color represents the same person.
(Best viewed in color)

In this work, we propose a hierarchical approach in which we first determine
tracks within each camera, (Figure 3.1(a)) by solving data association, and
later we associate tracks of the same person in different cameras in a unified
approach (Figure 3.1(b)), hence solving the across-camera tracking. Since
appearance and motion cues of a target tend to be consistent in a short
temporal window in a single camera tracking, solving tracking problem in a
hierarchical manner is common: tracklets are generated within short temporal
window first and later they are merged to form full tracks (or trajectories)
[176, 43, 151]. Often, across-camera tracking is more challenging than solving
within-camera tracking due to the fact that appearance of people may exhibit
significant differences due to illumination variations and pose changes
between cameras.

Therefore, this chapter proposes a unified three-layer framework to solve both
within- and across-camera tracking. In the first two layers, we generate
tracks within each camera and in the third layer we associate all tracks of
the same person across all cameras in a simultaneous fashion.

To best serve our purpose, a constrained dominant sets clustering (CDSC)
technique, a parametrized version of standard quadratic optimization, is
employed to solve both tracking tasks. The tracking problem is caste as
finding constrained dominant sets from a graph. That is, given a constraint
set and a graph, CDSC generates cluster (or clique), which forms a compact and
coherent set that contains all or part of the constraint set. Clusters
represent tracklets and tracks in the first and second layers, respectively.
The proposed within-camera tracker can robustly handle long-term occlusions,
does not change the scale of original problem as it does not remove nodes from
the graph during the extraction of compact clusters and is several orders of
magnitude faster (close to real time) than existing methods. Also, the
proposed across-camera tracking method using CDSC and later followed by
refinement step offers several advantages. More specifically, CDSC not only
considers the affinity (relationship) between tracks, observed in different
cameras, but also takes into account the affinity among tracks from the same
camera. As a consequence, the proposed approach not only accurately associates
tracks from different cameras but also makes it possible to link multiple
short broken tracks obtained during within-camera tracking, which may belong
to a single target track. For instance, in Figure 3.1(a) track $T_{1}^{3}$
(third track from camera 1) and $T_{1}^{4}$ (fourth track from camera 1) are
tracks of same person which were mistakenly broken from a single track.
However, during the third layer, as they are highly similar to tracks in
camera 2 ($T_{2}^{3}$) and camera 3 ($T_{3}^{3}$), they form a clique, as
shown in Figure 3.1(b). Such across-camera formulation is able to associate
these broken tracks with the rest of tracks from different cameras,
represented with the green cluster in Figure 3.1(b).

The main contributions of this chapter are summarized as follows:

  * •

We formulate multi-target tracking in multiple non-overlapping cameras as
finding constrained dominant sets from a graph. We propose a three-layer
hierarchical approach, in which we first solve within-camera tracking using
the first two layers, and using the third layer we solve the across-camera
tracking problem.

  * •

Experiments are performed on MOTchallenge DukeMTMCT dataset and MARS dataset,
and show improved effectiveness of our method with respect to the state of the
art.

The rest of the chapter is organized as follows. In Section 3.2, we review
relevant previous works. Overall proposed approach for within- and across-
cameras tracking modules is summarized in section 3.3, while sections 3.3.1
and 3.3.2 provide more in details of the two modules. In section 1.3, we
present the proposed approach to further speed up our method. Experimental
results are presented in Section 3.4. Finally, section 3.5 summarizes the
chapter.

### 3.2 Related Work

Object tracking is a challenging computer vision problem and has been one of
the most active research areas for many years. In general, it can be divided
in two broad categories: tracking in single and multiple cameras. Single
camera object tracking associates object detections across frames in a video
sequence, so as to generate the object motion trajectory over time. Multi-
camera tracking aims to solve handover problem from one camera view to another
and hence establishes target correspondences among different cameras, so as to
achieve consistent object labelling across all the camera views. Early multi-
camera target tracking research works fall in different categories as follows.
Target tracking with partially overlapping camera views has been researched
extensively during the last decade [4, 20, 44, 81, 103, 159]. Multi target
tracking across multiple cameras with disjoint views has also been researched
in [18, 34, 73, 75, 162, 115, 80, 31]. Approaches for overlapping field of
views compute spatial proximity of tracks in the overlapping area, while
approaches for tracking targets across cameras with disjoint fields of view,
leverage appearance cues together with spatio-temporal information.

Almost all early multi-camera research works try to address only across-camera
tracking problems, assuming that within-camera tracking results for all
cameras are given. Given tracks from each camera, similarity among tracks is
computed and target correspondence across cameras is solved, using the
assumption that a track of a target in one camera view can match with at most
one target track in another camera view. Hungarian algorithm [85] and
bipartite graph matching [73] formulations are usually used to solve this
problem. Very recently, however, researchers have argued that assumptions of
cameras having overlapping fields of view and the availability of intra-camera
tracks are unrealistic [162]. Therefore, the work proposed in this chapter
addresses the more realistic problem by solving both within- and across-camera
tracking in one joint framework.

In the rest of this section, we first review the most recent works for single
camera tracking, and then describe the previous related works on multi-camera
multi-view tracking.

Single camera target tracking associates target detections across frames in a
video sequence in order to generate the target motion trajectory over time.
Zamir et al. [176] formulate tracking problem as generalized maximum clique
problem (GMCP), where the relationships between all detections in a temporal
window are considered. In [176], a cost to each clique is assigned and the
selected clique maximizes a score function. Nonetheless, the approach is prone
to local optima as it uses greedy local neighbourhood search. Deghan et al.
[43] cast tracking as a generalized maximum multi clique problem (GMMCP) and
follow a joint optimization for all the tracks simultaneously. To handle
outliers and weak-detections associations they introduce dummy nodes. However,
this solution is computationally expensive. In addition, the hard constraint
in their optimization makes the approach impractical for large graphs. Tesfaye
et al. [151] consider all the pairwise relationships between detection
responses in a temporal sliding window, which is used as an input to their
optimization based on fully-connected edge-weighted graph. They formulate
tracking as finding dominant set clusters. They follow a pill-off strategy to
enumerate all possible clusters, that is, at each iteration they remove the
cluster from the graph which results in a change in scale (number of nodes in
a graph) of the original problem. In this chapter, we propose a multiple
target tracking approach, which in contrast to previous works, does not need
additional nodes to handle occlusion nor encounters change in the scale of the
problem.

Across-camera tracking aims to establish target correspondences among
trajectories from different cameras so as to achieve consistent target
labelling across all camera views. It is a challenging problem due to the
illumination and pose changes across cameras, or track discontinuities due to
the blind areas or miss detections. Existing across-camera tracking methods
try to deal with the above problems using appearance cues. The variation in
illumination of the appearance cues has been leveraged using different
techniques such as Brightness Transfer Functions (BTFs). To handle the
appearance change of a target as it moves from one camera to another, the
authors in [74] show that all brightness transfer functions from a given
camera to another camera lie in a low dimensional subspace, which is learned
by employing probabilistic principal component analysis and used for
appearance matching. Authors of [59] used an incremental learning method to
model the colour variations and [120] proposed a Cumulative Brightness
Transfer Function, which is a better use of the available colour information
from a very sparse training set. Performance comparison of different
variations of Brightness Transfer Functions can be found in [45]. Authors in
[147] tried to achieve color consistency using colorimetric principles, where
the image analysis system is modelled as an observer and camera-specific
transformations are determined, so that images of the same target appear
similar to this observer. Obviously, learning Brightness Transfer Functions or
color correction models requires large amount of training data and they may
not be robust against drastic illumination changes across different cameras.
Therefore, recent approaches have combined them with spatio-temporal cue which
improve multi-target tracking performance [33, 86, 57, 188, 19, 32]. Chen et
al. [33] utilized human part configurations for every target track from
different cameras to describe the across-camera spatio-temporal constraints
for across-camera track association, which is formulated as a multi-class
classification problem via Markov Random Fields (MRF). Kuo et al. [86] used
Multiple Instance Learning (MIL) to learn an appearance model, which
effectively combines multiple image descriptors and their corresponding
similarity measurements. The proposed appearance model combined with spatio-
temporal information improved across-camera track association solving the
”target handover” problem across cameras. Gao et al. [57] employ tracking
results of different trackers and use their spatio-temporal correlation, which
help them enforce tracking consistency and establish pairwise correlation
among multiple tracking results. Zha et al. [188] formulated tracking of
multiple interacting targets as a network flow problem, for which the solution
can be obtained by the K-shortest paths algorithm. Spatio-temporal
relationships among targets are utilized to identify group merge and split
events. In [19] spatio-temporal context is used for collecting samples for
discriminative appearance learning, where target-specific appearance models
are learned to distinguish different people from each other. And the relative
appearance context models inter-object appearance similarities for people
walking in proximity and helps disambiguate individual appearance matching
across cameras.

The problem of target tracking across multiple non-overlapping cameras is also
tackled in [128] by extending their previous single camera tracking method
[129], where they formulate the tracking task as a graph partitioning problem.
Authors in [32], learn across-camera transfer models including both spatio-
temporal and appearance cues. While a color transfer method is used to model
the changes of color across cameras for learning across-camera appearance
transfer models, the spatio-temporal model is learned using an unsupervised
topology recovering approach. Recently Chen et al. [31] argued that low-level
information (appearance model and spatio-temporal information) is unreliable
for tracking across non-overlapping cameras, and integrated contextual
information such as social grouping behaviour. They formulate tracking using
an online-learned Conditional Random Field (CRF), which favours track
associations that maintain group consistency. In this chapter, for tracks to
be associated, besides their high pairwise similarity (computed using
appearance and spatio-temporal cues), their corresponding constrained dominant
sets should also be similar.

Another recent popular research topic, video-based person re-
identification(ReID) [174, 98, 161, 38, 90, 50, 168, 190, 97], is closely
related to across-camera multi-target tracking. Both problems aim to match
tracks of the same persons across non-overlapping cameras. However, across-
camera tracking aims at 1-1 correspondence association between tracks of
different cameras. Compared to most video-based ReID approaches, in which only
pairwise similarity between the probes and gallery is exploited, our across-
camera tracking framework not only considers the relationship between probes
and gallery but it also takes in to account the relationship among tracks in
the gallery.

### 3.3 Overall Approach

In our formulation, in the first layer, each node in our graph represents a
short-tracklet along a temporal window (typically 15 frames). Applying
constrained dominant set clustering here aim at determining cliques in this
graph, which correspond to tracklets. Likewise, each node in a graph in the
second layer represents a tracklet, obtained from the first layer, and CDSC is
applied here to determine cliques, which correspond to tracks. Finally, in the
third layer, nodes in a graph correspond to tracks from different non-
overlapping cameras, obtained from the second layer, and CDSC is applied to
determine cliques, which relate tracks of the same person across non-
overlapping cameras.

####  3.3.1 Within-Camera Tracking

Figure 3.2 shows proposed within-camera tracking framework. First, we divide a
video into multiple short segments, each segment contains 15 frames, and
generate short-tracklets, where human detection bounding boxes in two
consecutive frames with 70% overlap, are connected [43]. Then, short-tracklets
from 10 different non-overlapping segments are used as input to our first
layer of tracking. Here the nodes are short-tracklets (Figure 3.2, bottom
left). Resulting tracklets from the first layer are used as an input to the
second layer, that is, a tracklet from the first layer is now represented by a
node in the second layer (Figure 3.2, bottom right). In the second layer,
tracklets of the same person from different segment are associated forming
tracks of a person within a camera.

Figure 3.2: The figure shows within-camera tracking where short-tracklets from
different segments are used as input to our first layer of tracking. The
resulting tracklets from the first layer are inputs to the second layer, which
determine a tracks for each person. The three dark green short-tracklets
($s_{1}^{2},s_{1}^{10},s_{1}^{7}$), shown by dotted ellipse in the first
layer, form a cluster resulting in tracklet ($t_{1}^{2}$) in the second layer,
as shown with the black arrow. In the second layer, each cluster, shown in
purple, green and dark red colors, form tracks of different targets, as can be
seen on the top row. tracklets and tracks with the same color indicate same
target. The two green cliques (with two tracklets and three tracklets)
represent tracks of the person going in and out of the building (tracks
$T^{p}_{1}$ and $T^{2}_{1}$ respectively)

#####  3.3.1.1 Formulation Using Constrained Dominant Sets

We build an input graph, $G(V,E,w)$, where nodes represent short-tracklet
($s_{i}^{j}$, that is, $j^{th}$ short-tracklet of camera $i$) in the case of
first layer (Figure 3.2, bottom left) and tracklet ($t_{k}^{l}$, that is,
$l^{th}$ tracklet of camera $k$), in the second layer (Figure 3.2, bottom
right). The corresponding affinity matrix
$\mathtt{A}=\left\\{a_{i,j}\right\\}$, where $a_{i,j}=w(i,j)$ is built. The
weight $w(i,j)$ is assigned to each edge, by considering both motion and
appearance similarity between the two nodes. Fine-tuned CNN features are used
to model the appearance of a node. These features are extracted from the last
fully-connected layer of Imagenet pre-trained 50-layers Residual Network
(ResNet 50) [67] fine-tuned using the trainval sequence of DukeMTMC dataset.
Similar to [176], we employ a global constant velocity model to compute motion
similarity between two nodes.

Determining cliques: In our formulation, a clique of graph $G$ represents
tracklet(track) in the first (second) layer. Using short-tracklets/tracklets
as a constraint set (in eq. 1.7), we enumerate all clusters, using game
dynamics, by utilizing intrinsic properties of constrained dominant sets. Note
that we do not use peel-off strategy to remove the nodes of found cliques from
the graph, this keeps the scale of our problem (number of nodes in a graph)
which guarantees that all the found local solutions are the local solutions of
the (original) graph. After the extraction of each cluster, the constraint set
is changed in such a way to make the extracted cluster unstable under the
dynamics. The within-camera tracking starts with all nodes as constraint set.
Let us say $\Gamma^{i}$ is the $i^{th}$ extracted cluster, $\Gamma^{1}$ is
then the first extracted cluster which contains a subset of elements from the
whole set. After our first extraction, we change the constraint set to a set
$V\backslash\Gamma^{1}$, hence rendering its associated nodes unstable (making
the dynamics not able to select sets of nodes in the interior of associated
nodes). The procedure iterates, updating the constraint set at the $i^{th}$
extraction as $V\backslash\bigcup\limits_{l=1}^{i}\Gamma^{l}$, until the
constraint set becomes empty. Since we are not removing the nodes of the graph
(after each extraction of a compact set), we may end up with a solution that
assigns a node to more than one cluster.

To find the final solution, we use the notion of centrality of constrained
dominant sets. The true class of a node $j$, which is assigned to
$\mathtt{K}>1$ cluster,
$\psi=\left\\{\Gamma^{1}\dots\Gamma^{\mathtt{K}}\right\\}$, is computed as:

$\operatornamewithlimits{\arg\,\max}_{\Gamma^{i}\in\psi}\leavevmode\nobreak\
\left(|\Gamma^{i}|*\delta^{i}_{j}\right),$

where the cardinality $|\Gamma^{i}|$ is the number of nodes that forms the
$i^{th}$ cluster and $\delta^{i}_{j}$ is the membership score of node $j$
obtained when assigned to cluster $\Gamma^{i}$. The normalization using the
cardinality is important to avoid any unnatural bias to a smaller set.

Algorithm (3), putting the number of cameras under consideration
($\mathcal{I}$) to 1 and $\mathcal{Q}$ as short-tracklets(tracklets) in the
first(second) layer, is used to determine constrained dominant sets which
correspond to tracklet(track) in the first (second) layer.

####  3.3.2 Across-Camera Tracking

#####  3.3.2.1 Graph Representation of Tracks and the Payoff Function

Given tracks ($T_{i}^{j}$, that is, the $j^{th}$ track of camera $i$) of
different cameras from previous step, we build graph
$G^{\prime}(V^{\prime},E^{\prime},w^{\prime})$, where nodes represent tracks
and their corresponding affinity matrix $\mathtt{A}$ depicts the similarity
between tracks.

Assuming we have $\mathcal{I}$ number of cameras and $\mathtt{A}^{i\times j}$
represents the similarity among tracks of camera $i$ and $j$, the final track
based affinity $\mathtt{A}$, is built as

$\mathtt{A}=\begin{pmatrix}\mathtt{A}^{1\times 1}&..&\mathtt{A}^{1\times
j}&..&\mathtt{A}^{1\times\mathcal{I}}\\\ .&\leavevmode\nobreak\
\leavevmode\nobreak\ .\leavevmode\nobreak\ \leavevmode\nobreak\ &.&.&.\\\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ &\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ &\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ &\\\
\mathtt{A}^{i\times 1}&..&\mathtt{A}^{i\times
j}&.&\mathtt{A}^{i\times\mathcal{I}}\\\ .&\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ &.&.&.\\\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ &\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ &\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \\\
\mathtt{A}^{\mathcal{I}\times 1}&..&\mathtt{A}^{\mathcal{I}\times
j}&..&\mathtt{A}^{\mathcal{I}\times\mathcal{I}}\\\ \end{pmatrix}.$

Figure 3.3 shows exemplar graph for across-camera tracking among three
cameras. $T^{i}_{j}$ represents the $i^{th}$ track of camera $j$. Black and
orange edges, respectively, represent within- and across-camera relations of
the tracks. From the affinity $\mathtt{A}$, $\mathtt{A}^{i\times j}$
represents the black edges of camera $i$ if $i=j$, which otherwise represents