Analysis of clusters and movement patterns during emergency scenarios has the potential to provide vital information to key decision stakeholders. This paper presents a method using Voronoi Diagrams for de ning both clusters and movement patterns in terms of voronoi cell properties: size, elongation, orientation and neighbourhood. Initial experimentation and testing against baseline methods using an evacuation trajectory dataset show promising results.
Previous research used data from tracking devices on people (e.g., in
A Voronoi Diagram is a data structure that partitions space around a set of points (generators) such that
each generator is the nearest object to any point inside its corresponding partition
The method presented here is based on previous work on point pattern analysis, where VDs are used for
pattern detection. Similarly to work described in
Before describing how VDs are used to de ne and analyse movement patterns, a visual inspection of the
evacuation data is performed. Observed patterns are de ned in terms of Voronoi cell properties inspired by the work of
The data used for exploratory analysis are taken from the VAST 2008 Challenge
The area A(Vp), number of sides S(Vp), and distance D(Vp; Vq) to neighbours are standard geometrical measures. In contrast, the elongation E(Vp) and orientation O(Vp) of a polygon are not standard and the methods for computing them described above are empirically tested heuristics. Comparing or using other methods of computation are out of the scope of this paper, but are brie y discussed in future work (Section 5). 3.2
During the visual analysis of the data, two types of patterns emerged in the VD structure: clusters and movement.
The clusters are de ned at corridors people use when exiting the building, especially when two such corridors
meet. Accordingly, the movement pattern we focus on is the transition from one corridor cluster to the next.
Both of these patterns are recurrently analysed in disaster evacuation related research
While clusters formed by people queuing at an exit are visually easy to spot, to formally de ne them can be challenging. In particular, we want to de ne the two corridor clusters shown in Figure 2: the vertical (in brown) and horizontal (in purple). We refer to these as VC and HC, respectively. As observed, cells belonging to one of these clusters are elongated, have a certain orientation, and their generator points are close together. These Voronoi cell properties are used to formally describe the clusters.
We de ne as corridor cluster the group of three or more neighbouring cells (cells that share an edge) that satifsy the following condition: Given any pair of neighbouring cells Vp and Vq, their score(Vp; Vq) is less than a threshold . That is, a generator p is part of the same cluster as q, i score(Vp; Vq) < . This score is the weighted average of the elongation E(Vp), the normalised angle between orientations O(Vp) and O(Vq), and the normalised distance between the generator points D(Vp; Vq): score(Vp; Vq) =
WE
E(Vp) + WO
O(Vp; Vq) + WD d(Vp; Vq) WE + WO + WD (1) where O(Vp; Vq) = jO(Vp)#O(Vq)j is the normalised angle di erence, and d(Vp; Vq) = D(Vp;Vq) is the normalised distance. As the maximum possible angle between two cells (in the current experiment) is 90°, it is used as the value # for normalisation. Likewise, the maximum distance in the provided dataset between two points is 90, and is the value used as for normalisation. Having a single score that combines the three cluster de ning properties allows for some cluster membership exibility. For instance, a cell that is not so elongated, but has the same orientation and is very close to other members, can be in the same cluster. Likewise, an elongated cell with the same orientation as the cluster, even if a little distant (due to the underlying environment perhaps), can still belong to the cluster. An additional restriction is placed such that WE + WO + WD = 1, so that the weights represent a trade-o between the properties.
The value of roughly represents the property values of an 'ideal' cluster member cell. It is important, therefore, to de ne appropriately. The ideal (trivial to identify both visually and computationally) corridor cluster would have members perfectly aligned one after the other, and as close as possible. In that case, cells are elongated, have the exact same orientation, and are minimally separated. Numerically, it would be: • E(Vp) = 0:35. Mildly elongated. This is the 80 percentile of elongation in the dataset used. It is equivalent to a rectangle of sides 7 and 1. • jO(Vp)
O(Vq)j = 0°, same orientation • D(Vp; Vq) = 1, minimum distance
Plugging these values to Equation (1) then results in = 0:12, when all weights WE , WO and WD are equal. As stated before, the uni ed score allows trade-o s to be made. For instance, if a cell were to have a slight rotation (jO(Vp) O(Vq)j = 5°) and be further apart (D(Vp; Vq) = 3), but is more elongated (E(Vp) = 0:26), it would still be a member (score(Vp; Vq) = 0:118 < 0:12). 3.2.2
The second pattern de ned and analysed is a movement behaviour during the merging of two corridor clusters, particularly when the clusters are orthogonal to each other. Analysing other con gurations is out of the current scope, but is discussed brie y in future work. Whenever there is an intersection between two ows of people, there is a transitioning cell at the intersection of the two clusters. Using the same case shown in Figure 2, the transitioning cell goes through a speci c set of states, outlined below: 1. State 1. The cell is elongated, it has a horizontal orientation, and has more than three sides 2. State 2. The cell becomes a triangle 3. State 3. The cell returns to being elongated with a vertical orientation, and having more than three sides (a) Person 14 in VC
(b) Person 14 transitioning (c) Person 14 in HC
These states are shown in Figure 3. In general, we call a set of transitioning states a movement pattern and de ne it as a set of n sequential states M = S1(Vp); : : : ; Sn(Vp). Each state Si is a set of conditions a Voronoi cell should meet to be in said state. We formally de ne the transition movement pattern as a movement pattern of n = 3, where each state has the following conditions (the threshold values for elongation (0.7) and orientation ( 20°) allow for exibility in the membership of the vertical and horizontal corridor clusters): 20° < O(Vp) < 20°, and (iii) has more than • State 1 (S1): (i) Is elongated: E(Vp) < 0:7, (ii) is horizontal:
three sides: S(Vp) > 3 • State 2 (S2): Is a triangle: S(Vp) = 3 • State 3 (S3): (i) Is elongated, E(Vp) < 0:7, (ii) is vertical, 70° < O(Vp) < 110°, and (iii) has more than three sides, S(Vp) > 3 In order to ascertain the veracity of the pattern detection methods described previously, two sets of experiments are performed using the data described in Section 3.1. For each set, manual pattern identi cation is used as ground truth. Then we apply the Voronoi cell properties method and measure its ability to identify the patterns and compare its performance to a baseline. During the manual identi cation of the clusters, at time step i the members of each cluster Ci are recorded and named M (Ci). The corridor cluster method (Section 3.2.1), retrieves a cluster CCi with members M (CCi). These values are computed for clusters VC and HC, and are used to calculate the precision, recall and F1 score as explained in Section 4.1. The same is done with a baseline for comparison. The baseline used is distance-based clustering, where all points within distance are clustered together.
This experiment was run with a number of di erent weight combinations using insights learned from the visual analysis. The most relevant combinations are summarised in Table 1. Experiments 1 and 2 are the baselines with two di erent values. Experiment 3 shows the method using equal weights, that is, using cell properties for the 'ideal' corridor cluster. As observed in the visualisation, the most important predictor of a cluster is still the distance between the generator points. Therefore, the distance weight WD is assigned a higher value in both Experiments 4 and 5. Deciding for WE and WO proved more challenging as they seem equally important for the clustering. Orientation seems to prevail at times; therefore, two cases are tested: one with a higher weight for orientation (Experiment 4), and another with equal orientation and elongation weights (Experiment 5). The number of points behaving in the way de ned in Section 3.2.2 is rst manually recorded for each time step, and used as ground truth. The set of manually collected points is named T P (transitioning points). Then, the described method to identify the movement pattern is applied , and a set of points AP (attempted points) is retrieved. These values are calculated for obtaining the precision, recall and F1 scores, as described in Section 4.2. The same data is collected for the baselines, de ned as follows: For every moving point, check if the point performed a vertical movement followed by a horizontal movement. For generator p at time step i, these movements are de ned as: verticalpmove = ypi 1 ypi > (xpi 1
xpi ) horizontalpmove = xpi 1 xpi > (ypi 1 ypi ) (2) (3) where is a user-de ned constant that represents how "straight" the movement is. The higher is, the more "straight" the movement. Four experiments are realised. Experiments 1-3 are baselines and involve setting di erent values for , namely 2, 4 and 10. Experiment 4 uses the suggested method and is contrasted to the other three in the results analysis.
Precision and recall values are frequently used for measuring the performance of pattern recognition methods and are, here, also compared to the values of the baseline methods. Additionally, we compute the F-measure, or F1, as a way to represent the overall accuracy of precision and recall together. Precision, recall and F1 values for the Voronoi cell properties method, as well as the baseline, are calculated using Equations 4, 5 and 6 and summarized in Table 2 for di erent weights and constant values. Experiments 1 and 2 are done using the baselines and, thus, a xed distance metric . Experiments 3, 4 and 5 use the Voronoi cell properties method with di erent values for the weights WE , WO, and WD.
precision = recall =
Pn i=1 jM (Ci) \ M (CCi)j
Pn
i=1 jM (CCi)j Pn i=1 jM (Ci) \ M (CCi)j
Pn
i=1 jM (Ci)j
The baseline methods have surprisingly acceptable precision and recall. The recall is high because, as they do not have additional conditions, the distance metric picks up everything nearby. Thus, members of both clusters are frequently considered as a single larger cluster, which is precisely what we sought to di erentiate with the suggested method.
Experiment 3 ranks the highest in precision but has very low recall scores, much lower than the baselines. This con rms that the ideal de nition of the corridor cluster is not achieved in practice and, therefore, variations in the weights are needed as proved by the next two experiments. Experiment 4 shows much better results for recall. Weights used in Experiment 5 prove to be superior to the baselines and the rest of the runs, with the highest F1 scores for all VC and HC experiments. These two experiments demonstrate three points: 1. Distance remains the best predictor for cluster membership as shown by higher values of WD 2. Combination of distance, cell elongation and cell orientation improves the performance, as shown by the consistent higher scores than the baselines. 3. Voronoi cell properties can in fact be used to e ectively identify the corridor cluster pattern. Precision, recall and F1 scores are used to measure the performance of this method as well. They are calculated using Equations 7, 8 and 9. Table 3 shows the results from the transition movement pattern experiment. Experiments 1, 2, and 3 are the baselines with di erent values for (Section 3.3.2). Experiment 4 implements the suggested movement pattern detection method, as described in Section 3.2.2.
precision = jT P \ AP j jAP j (4) (5) (6) (7) recall = jT P \ AP j
jT P j
In the baselines, as the value for increases, the number of retrieved patterns decreases (recall). Accordingly, Experiment 1 has a perfect recall but a very low precision. When increasing , the precision improves, but the recall drastically drops. In contrast, the suggested method (Experiment 4) proves superior and acceptable overall, in both precision and recall, even if recall is lower than the highest observed. The method's better performance is also summarized with the highest F1 score. This research shows how elements of the VD structure can be used to determine and analyse two types of ne-grained spatio-temporal patterns: clusters and movements. The suggested methods allow for the exible de nition of these patterns by the combination of Voronoi cell properties | namely elongation, orientation, and distance to neighbours. These properties were selected as the most relevant for the testing dataset scenarios: elongation and orientation were paramount to the identi cation of corridor clusters, for example. The exibility of the method, however, allows the use of di erent Voronoi cell properties that may be more appropriate for di erent datasets and environments. With consistently high scores in precision and improving recall scores, the suggested method proved better than baseline methods that are only considering distance factors for the formation of clusters.
The suggested method has advantages over previous approaches. Until now, there has not been a standard
movement pattern de nition and they are, thus, mostly analysed using general measures such as distance traveled
This preliminary work shows some of the bene ts of using the VD structure properties for the detection
and analysis of various patterns, which can aid in emergency response and evacuation operations. The method's
exibility allows for the use of di erent or additional cell properties. For instance, eccentricity is another clustering
indicator that has been used in digital image processing applications and could be considered in future research.
In addition, patterns that use non-standard properties of a polygon such as elongation and orientation can bene t
from di erent computing methods. For example,
In the analysis of movement patterns, the conditions of each cell transition state can also be more exibly de ned to allow for the detection of more and varied patterns. For example, state S1 in the transition movement pattern could be something close to, rather than an exact triangle (i.e., S(Vp) = 3), such as having 4 sides with one of them being much smaller than the rest. This generalisation is especially important when aiming at identifying other corridor con gurations. Finally, when dealing with large amounts of data, it is important to also consider time complexity for comparing with other methods. Building a VD has a time complexity of O(n log n) in the worst case scenario, and O(n) in the average case. Therefore, any additional analysis would have to consider this as a base cost. The authors wish to thank Dr Egemen Tanin for his valuable comments during initial discussions on this work.