Semantic Analysis for Crowded Scenes Based on Non-Parametric Tracklet Clustering

1 Introduction

Due to the increase of the population and diversity of human's activities and behaviors, crowded scenes have been more frequent in the real world than ever. Adding to this the escalating world-wide concerns about security, automatic crowded scene analysis has become one of the most attractive topics in computer vision and pattern recognition. The major goal of such research is extracting some kind of information from the scene about the moving objects' behaviors in order to serve multiple applications, such as, visual surveillance, crowd management, safety analysis of public places or sports arenas, etc.

Two main analysis levels for crowded scenes are introduced: macroscopic and microscopic [Li et al., 2015]. At the macroscopic level , we deal with crowd motions as global motion pattern(s) of a mass of objects, without being concerned with the movements of the individual objects [Hu et al., 2008]. On the other hand, the microscopic level is concerned with the movements of individual moving objects as well as the interactions among them [Zhou et al., 2012].

To serve the aforementioned levels of analysis, two major approaches for the computational modeling of crowd behavior are introduced. The first is the continuum-based approach (holistic), which works better at the macroscopic level for medium and high density crowds [Ali and Shah, 2007]. Such kind of techniques usually try to obtain global information about the scene regardless of any local activities, such as the identification of global active regions which have high traffic as well as the main directions of flows. The second approach is agent-based, which is more suitable for low-density crowds at the microscopic level, where the movement of each individual moving object is taken into account [Zhou et al., 2012; Zhao et al., 2011].

Both continuum-based and agent-based approaches rely on some form of motion representation in order to conduct their analyses. In this regard, three main levels of motion representation have been introduced. The first is flow-based representation, which extracts motion features at the pixel level [Wang et al., 2014]. The second is local spatio-temporal representation, which represents the scene in terms of local information extracted from 2D patches [Kratz and Nishino, 2012]. The third level is the trajectory/tracklet representation, which represents motion information at a higher level dealing with individual tracks as a basic unit [Zhou et al., 2011; Topkaya et al., 2015].

The trajectories/tracklets representation is more semantically-rich than the other representations because it incorporates information about a semantically meaningful moving entity (e.g. a feature point or an object) for a period of time. A tracklet is defined as a fragment of a trajectory obtained by the tracker within a short period of time. It may terminate when occlusions or scene clutters occur [Li et al., 2015]. Thus, tracklets are more conservative and less likely to drift compared to complete trajectories.

In this paper, we introduce a new macroscopic-level approach for crowded scenes analysis that relies on tracklets as the basic motion representation. Particularly, we are interested in grouping motion patterns in a way that enables the discovery of the underlying scene structure, namely, the common pathways of moving objects and the sources/sinks of the scene, which we collectively call as semantic regions. On doing so, we do not assume prior information about the numbers or the spatial extents of such scene structural elements.

Our proposed approach first extracts tracklets of detected interest points in the foreground (motion) areas of the scene. Then, tracklets are clustered hierarchically over two levels such that the resulting clusters correspond to common pathways in the scene. To accomplish this goal, a novel and flexible tracklet similarity measure, which is based on line geometry, is introduced. The discovered pathways are then analyzed to find the common sources and sinks of the scene. In order to achieve these goals, we adopted a non-parametric clustering algorithm that is based on the Distance Dependent Chinese Restaurant Processes (DD-CRP) [Blei and Frazier, 2011].

The main contributions of this work can be summarized as follows: (i) a novel tracklet similarity measure based on line geometry, (ii) an adaptation of DD-CRP to the problem of grouping tracklets into common pathways using a twolevel hierarchical clustering, (iii) a method for discovering the scene structure and its sources and sinks from the resulting clustering, and (iv) a novel evaluation framework for the resulting scene analysis that takes into account both the detected scene structural elements and their geometric extents.

The rest of the paper is organized as follows. Section 2 outlines the most related work. In Section 3, a detailed explanation of our proposed tracklet similarity measure is provided. The adaptation of DD-CRP model to serve our tracklet clustering problem, and the discovery of the scene's semantic regions are provided in Section 4. Experiments are included in Section 5. Finally, Section 6 concludes the paper.

2 RelatedWork

Similar to our approach, many crowded scene analysis approaches in the literature are based on tracklets. In [Zhou et al., 2011], a Random Field Topic (RFT) model is proposed to learn semantic region analysis in crowded scenes from tracklets. The RFT model is an advancement of the existing Latent Dirichlet Allocation (LDA) topic model [Blei et al., 2003], where a Markov Random Field (MRF) is integrated as a prior to impose spatial and temporal coherence between tracklets during the inference process. To improve the inference of semantic regions and clustering of tracklets, sources and sinks are included as a high-level semantic prior. Our approach also identifies semantic regions; however, it does not require sources and sinks to be a priori known. In [Wang et al., 2013], an approach is proposed to analyze motion patterns in dynamical crowded scenes based on hybrid generativediscriminative feature maps, which are in turn based on the collected tracklets. Automatic hierarchical clustering algorithm is used to analyze motion patterns. These motion patterns are analogous to the common pathways identified by our work. However, our approach is simpler and also produces sources and sinks.

Tracklets are frequently used as building blocks to enhance tracking in crowded scenes. For instance, in [Zhao and Medioni, 2011], an unsupervised manifold learning framework is proposed to infer motion patterns in videos. Tracklet points are embedded into a 3D space (x,y,✓) that represents the image space and motion direction. In this space, points automatically form intrinsic manifold structures, each of which corresponds to a motion pattern. The extracted motion patterns can be used as a prior to improve the performance of object tracking techniques. Also, in [Kuo et al., 2010], an algorithm is proposed for Online Learning of Discriminative Appearance (OLDA) models for different targets in crowded scenes based on collected tracklets. Spatialtemporal relations between tracklets in a time window are examined to discriminate between targets. OLDA models are integrated into a hierarchical association framework to improve the tracking system's accuracy.

DD-CRPs are adopted in language modeling, computer vision problems, and mixture modeling for clustering applications. For example, DD-CRP is examined in [Ghosh et al., 2011] in the spatial domain for image segmentation, where a novel hierarchical extension, better suited for efficient image segmentation, is proposed. A tracklets-clustering approach based on DD-CRP is proposed in [Topkaya et al., 2015] for the purpose of tracking enhancement. In this work, twolevel robust object tracking is employed to generate tracklets, which are then clustered based on their color, spatial, and temporal similarities. In our work, we adopted a similar model; however, the application is different. In their work, a cluster is supposed to contain a single whole trajectory of one object. In contrast, in our work, a cluster is supposed to contain a group of tracklets in a common pathway. Therefore, the similarity measure and cluster probability functions are totally different.

3 The Tracklet SimilarityMeasure

The purpose of clustering tracklets in our approach is to identify semantic regions in the scene, which are, namely, the common pathways, the sources, and the sinks. In this section, we focus on the tracklet similarity measure, variants of which are used in multiple levels of non-parametric clustering.

We would like tracklets to be clustered together when they belong to the same common pathway. For two tracklets to belong to a common pathway, they have to belong to a single object, or two objects that are originating from the same source and moving towards the same sink. In this case, the two tracklets are expected to bear similarity to one another in terms of their spatial layouts and their global orientations. However, encoding this similarity in a single measure is not trivial due to the many cases that can be encountered in practice.

Figure 1a shows a hypothetical scene having one source (A) and two sinks (B and C), with four overlaid tracklets. Consider the two tracklets T1 and T2. Although both of them originate from the same source and are spatially close to each other, perceptually, they do not seem to belong to a common pathway. This can be interpreted by inspecting the geometric relationship between the two tracklets: If they belonged to the same common pathway, they would have been in the same stage (the beginning here) of that pathway, which means they should have been almost parallel. However, because of their divergence in orientation, they are not perceived to be in the same pathway. Now, consider the two tracklets T1 and T3. The difference in orientation between them is higher than that between T1 and T2. Nevertheless, perceptually, tracklet T3 seems to be a continuation of T1, i.e. the two tracklets can be in the same pathway but in two different stages.

From the discussion above, the way we interpret the geometric relationship between two tracklets depends on the degree to which they are perceived to be in the same stage of a common pathway. In our approach, we estimate this by the degree of overlap between the two tracklets. The intuition is that the higher the overlap between two tracklets, the more likely they belong to the same stage of a common pathway, and vice versa. Our similarity measure incorporates both the spatial and orientation similarities between tracklets while taking into account the overlap between them. Now, we will explain each of these components.

Spatial similarity between two tracklets is estimated using two different distance functions: the Hausdorff distance and the minimum point-to-point distance. Let Ti = (pi1↪ pi2↪ ▷▷▷↪ pin), and Tj = (pj1↪ pj2↪ ▷▷▷↪ pjn) be two different tracklets such that each tracklet is identified by n points, and each point is identified by its x - y coordinates in the image's frame. The Hausdorff distance dH(Ti↪ Tj) between the two tracklets can be computed as

where d(pik↪ pjl) is the Euclidean distance between the kth point of Ti and the lth point of Tj. On the other hand, the minimum point-to-point distance can be expressed as

In the following, we refer to the distance between two tracklets Ti and Tj by δij, regardless of the type. In the following section, we will explain when we apply each type.

To estimate the orientation similarity between a pair of tracklets, we approximate each tracklet as a directed line segment that extends from its starting to its ending points, as shown in Figure 1a. Note that since tracklets are typically constructed over short time periods, approximating them by directed line segments should be acceptable for most cases.

For two tracklets Ti and Tj, the angle between them, ✓ij, is estimated as the angle between their two associated directed line segments.

The overall similarity measure between a pair of tracklets Ti and Tj is defined as

where the two variables σ✓ij and σδij represent the tolerance values in the orientation and spatial dimensions. The higher the tolerance value, the less sensitive the similarity function to the changes in the associated variable. The similarity measure takes values in the range [0↪ 1].

As the notation in Equation 4 indicates, the tolerance values are associated with the two particular tracklets for which the similarity is computed. These tolerance values are computed as follows.

where Oij indicates the degree of overlap between the two tracklets Ti and Tj, which is takes a value in the interval [0↪ 1] (as explained below). Each tolerance value is chosen from an interval, i.e. σ✓ij 2 [σ✓min↪ σ✓max] and σδij 2 [σδmin↪ σδmax]. We linearly choose a value in the interval based on the overlap between the two tracklets such that the higher the overlap between them, the more tolerance we give to the spatial dissimilarity and less tolerance we give to orientation dissimilarity.

To estimate the degree of overlap between two tracklets, we resort again to the directed line segment approximation. Particularly, we estimate the overlap between tracklets Ti and Tj as the overlap ratio between the two associated directed line segments, Li and Lj , when projected on an intermediate line, called the virtual line, V Lij. We adopted the idea of the virtual line from [Etemadi et al., 1991]. The computation is illustrated in Figure 1b.

4 Tracklet Clustering and Semantic Scene Analysis

In this section, we first provide a brief background about DDCRP. Then, we introduce the adaptation of DD-CRP to our tracklet clustering problem. Finally, we explain how the semantic regions are discovered from the resulting clustering.

4.1 Distance Dependent CRP

The main issue in high dimensional data clustering problems is finding a flexible clustering algorithm. One of the recent valuable models is the Dirichlet Process Mixture Models (DPMMs). DPMMs provide an efficient way to model a set of data points O as a mixture of unknown number of distributions sampled from the same base distribution G0 [Antoniak, 1974]. The clustering problem in a DPMM is represented as a distribution over an infinite number of mixture components (i.e., clusters). One of DPMMs representations is the Chinese Restaurant Process (CRP). In the CRP analogy, a sequence of customers are going to be seated at an infinite number of tables in a restaurant. The first comer will gain a probability one to sit at a given table. Any subsequent customer sits at a previously occupied table with probability proportional to the number of people already seated at the table, and sits at a new table with probability proportional to a scaling parameter ↵. Based on the Gibbs sampling method, CRP iteratively sample every table assignment zi from the following probability:

where zi is the table assignment of the ith customer, Nj is the number of customers sitting at table j, tables 1↪ ▷ ▷ ▷ ↪K are occupied, and z-i is all table assignment except for the assignment of customer i.

In infinite clustering models, the data points to be clustered may be ordered in time (such as time-stamped articles) or in space (such as pixels in an image) which reflect dependencies among them, and violate the exchangeability property of the basic Dirichlet process. So, the DD-CRP model is developed in order to handle these dependencies [Blei and Frazier, 2011]. DD-CRP model represents the data partitioning through customer assignments rather than table assignments, and the customer's assignments depend only on the distance among customers. Furthermore, customers are assigned to tables by considering customers reachability to each other through their assignments. According to this analogy, customer assignments will be conditioned on the distances between customers and drawn independently according to the following scheme.

where dij is the distance between customers i and j, D denotes the distance matrix between all customers, ↵ is the scaling parameter, and f is the decay function (for decay function details see [Blei and Frazier, 2011]). Additionally, the posterior inference for DD-CRP, based on Gibbs sampling, is implemented by iteratively sampling the customer assignments from the conditional distribution for each new customer (latent one) given the previous already seated customers c-i and all customers O. So, the posterior probability looks like the following:

Note that P (ci♣D↪ ↵) represents the DD-CRP prior term from Equation (8) and P(O♣W(c-i [ cnew i )↪G0) is the likelihood of the data points under the partitioning given by W(c-i [ cnew i ).

4.2 Tracklet Clustering Based on DD-CRP

We adapted DD-CRP by using our similarity measure between tracklets rather than the distance between them. Within the DD-CRP clustering framework, tracklets correspond to observations, whereas pathways are the output clusters. Let S denote the similarity matrix among all tracklets, so Equation (8) is modified as follows.

where sij is the pairwise similarity between tracklets i and j. We represent the likelihood term as the factorization of maximal pairwise similarities among a group of directly/indirectly connected tracklets (i.e. cluster).

Note that P(tn♣tj↪G0) is chosen to be proportional to the pairwise similarity between tracklet tn and tracklet tj.

4.3 Identifying Semantic Regions

Semantic regions (i.e. pathways) correspond to spatial regions of the scene that have high degrees of local similarities. We define the pathway as a series of spatially coherent linked groups of tracklets. Each pathway has its preferred source and sink, and the motion flow is from the source to the sink. The collected tracklets are clustered hierarchically over two levels. In both levels, the adapted DD-CRP is deployed.

At the first level of clustering, the collected tracklets are clustered using DD-CRP based on a parallelism criteria, which tries to group only parallel tracklets together. This criteria is incorporated into our clustering framework by adjusting the limits on the tolerance values in the similarity measure σ✓min◁max, and σδmin◁max, and using the Hausdorff distance function (Equation 1). As an output of this level, each resulting cluster is represented by a single directed representative line segment which is obtained from the associated cluster's tracklets. The representative line segment of a cluster of tracklets has the average orientation of tracklets in the clusters and passes through the center of mass of the union of all tracklets points. Its terminal points are identified by projecting all tracklets on it and taking the extreme projected points. Figure 2a shows the clusters of parallel tracklets and Figure 2b shows the associated representative line segments for the clusters correspondances.

At the second level of clustering, all of the resulting representative lines are clustered based on DD-CRP again using the same similarity function. However, in this case, the similarity function is adjusted to group line segments continuing after one another, by adjusting the limits of the tolerance again and by deploying the minimum point-to-point distance function (Equation 3). The output clusters from this level correspond to the common pathways in the scene as shown in Figure 2c.

We choose the Hausdorff distance for the spatial similarity in the first level of clustering because it captures the separation between parallel tracklets whether they are parallel or intersecting, while the minimum point-to-point distance becomes zero if the two tracklets intersect. On the other hand, for the second level clustering, the Hausdorff distance can become too large for tracklets continuing one another.

Once a pathway is identified, it is represented again as a single directed representative line segment, estimated from all corresponding pathway's tracklets (Figure 2c). The two terminals points of each such line segment represent the detected pathway's source and sink regions, respectively. To determine the spatial extents of a pathway's source and sink regions, we consider the convex hulls of the tracklet terminal points lying within a small distance 1 from the representative line segment's terminal points. The x-y coordinates of all the points within the convex hulls are then clustered using DDCRP to identify the scene's sources and sinks (gates).

5 Experimental Evaluation

In our implementation, to obtain tracklets in a given crowded scene, we first detect interest points using the minimum eigen features method [Shi and Tomasi, 1994] in foreground regions, which are identified using background subtraction via Gaussian Mixture Models [Stauffer and Grimson, 1999], learned from the first five frames. Then, the detected points are tracked using the standard Kanade-Locus-Tomasi (KLT) tracker [Tomasi and Kanade, 1991].

Experiments are conducted on multiple datasets. However, most of our analysis is performed on the challenging New York's Grand Central station video [Zhou et al., 2011], which is a 33-minute video with 540⇥960 resolution and a frame rate of 25 FPS. More than 20,000 tracklets are extracted from this scene (Figure 3a). All tracklets are stopped, collected, and tracking is restarted every 25 frames, which makes all our tracklets having the same fixed length. In the following, we first present our experiments on the Grand Central Station's scene, then, on other datasets. More detailed results and resources associated with this work can be found online 2 .

5.1 The Grand Central Station Scene

We compare our approach against the Meta-Tracking (MT) approach [Jodoin et al., 2013] in terms of pathway detection, pathway spatial layout coverage, and source/sink detection.

1 60 pixels in our implementation.

2 http://www.cps.ejust.edu.eg/index_files/ijcai_2016.htm

Common Pathway Detection

To quantitatively evaluate the detection of common pathways, we used a recently released large scale annotation for the Grand Central video dataset [Yi et al., 2015]. In this annotation, all pedestrians are manually tracked and the complete path for each pedestrian is labeled from the time of entering to the time of leaving the scene. We manually labeled eleven gates (pathway sources/sinks) in the scene, which are shown in Figure 3b. For each pair of gates, we extracted from the ground truth (GT) all pedestrian trajectories originating from the first and terminating in the second. If such trajectories exist, the pathway is considered existing in the ground truth. In this way, 108 GT pathways were found. The richness of these pathways (i.e. count of trajectories) ranges from 1 to 1338, with up to 57% of them having less than 40 trajectories.

To evaluate the detection of pathways, we sort the resulting pathways from the proposed approach and the MT approach based on their richness, which is measured by the number of tracklets in our approach and by the number of trajectories in the MT approach. Then, we take the richest 40 pathways of each approach and match them to the GT pathways 3 . The results of this experiment are presented in Table 1, which show that out of the richest 40 pathways, 14 are matched to true pathways in our proposed approach compared to only 10 in MT. It is worth noting that the MT approach can produce multiple pathways corresponding to the same GT pathway. We only count one match to a GT pathway as a true detection and the rest as false detections.

Common Pathway Spatial Layout Coverage

To our knowledge, all prior work evaluated only the count of identified pathways compared to GT. We introduce a new evaluation criteria based on measuring the similarity between the spatial layouts of a retrieved pathway and the corresponding GT pathway.

For each GT pathway, its trajectories are overlaid and accumulated on top of one another to construct a spatial probability map to represent the pathway's spatial extent in the scene and the level of activity at each point within it. Similarly, another probability map is constructed for each resulting pathway from the evaluated algorithm. From both probability maps, pixel-wise Precision and Recall are calculated, considering only the pixels with positive probability values, which we call active pixels.

3 The matching is done semi-automatically using bipartite graph matching followed by human inspection. Details are removed for space limitation.

Table 2 shows the results of this experiment for our approach compared to MT. The scores are computed for the correctly detected pathways from the richest 7 GT pathways. Note that our approach detects more from these pathways than the MT approach. It also yields slightly better precision than the MT approach. However, for both of them the recall is lower than the precision. This can be explained by inspecting a sample of the scores as illustrated in Figure 4. As evident in the figure, GT pathways are sometimes very wide, either in the middle due to midway pedestrian diversion to avoid an obstacle, or at terminals due to the perspective effect which makes distances close to the camera appear much larger. This makes it hard for a detection algorithm to cover most of the spatial layout of the GT pathway. This is particularly true for our approach, which tends to produce coherent clusters. Sometimes, this results in distributing tracklets belonging to one GT pathway over multiple clusters, only one of them is matched with the corresponding GT pathway. We believe that the ignored clusters account for the recall loss.

Source/Sink Region Detection

The detected source/sink regions (as explained in Section 4.3) are semi-automatically matched with the manually annotated Ground Truth source/sink regions (Figure 3b). Quantitative results are presented in Table 1. The results show that our approach detects 9 of the 11 GT gates, vs. only 6 detected by MT. On the other hand, the two approaches produce high count of false gates. This happens when a detected pathway starts from or terminates at an intermediate point that is not close to any GT gate.

5.2 Other Datasets

Qualitative results for other datasets are shown in Figure 5. These results are comparable to the results obtained by other approaches in the literature on the same scenes [Ali and Shah, 2007; Jodoin et al., 2013].

6 Conclusion

In this paper, we propose a new approach for semantic region analysis of crowded scenes based on tracklet clustering. DD-CRP is adopted as a non-parametric clustering approach. Inspired by line geometry, a novel similarity measure is formulated, which effectively captures the spatial and directional similarity between tracklets during the clustering process. The proposed approach is evaluated against ground truth pathways from a recently released annotation for a challenging dataset. Pathways' spatial probability maps are constructed and active pixels of both identified pathway and ground truth are matched. Pixel-wise Precision/Recall measures are utilized to evaluate the spatial coverage of pathways. Our proposed work demonstrates state of the art performance both in pathways detection, their associated gates and spatial layout coverage. The proposed approach is also tested on different crowd scene datasets and demonstrates good qualitative performance.

Acknowledgment

This work is partially supported by the Information Technology Industry Development Agency (ITIDA) under the ITAC Program Grant no. PRP2015.R19.4-Automatic Crowd Scene Analysis and Anomaly Detection From Video Surveillance Cameras. It also has been supported by the Ministry of Higher Education (MoHE) of Egypt through a Ph.D. scholarship.