1 Introduction

The video surveillance systems became widespread in the urban space, but beside the increase of the number of installed cameras a development in automatic video processing also occurred. In the distributed video surveillance systems there are areas which are not supervised with any camera, but objects can move between the cameras’ FOVs (Fields of View/Vision). Therefore, methods for tracking objects between non-overlapping FOVs need to be developed. Because there is no possibility to observe the same object in more than one camera simultaneously, the goal is to find connections between two observations of the one object from different cameras and different periods of time. During the observations matching process a connection between two observations is created as a probability that a given pair of observations is related to the single real object. In order to obtain such a matched pair of observations few clues are used. Each observation contains data related to appearance of the object and information about the time and the location of the observation. Additionally, the area (observed with cameras) in which a given object is moving can be also described. This description contains two main parts: a topology and a behaviour model. The topology can be presented in the form of bidirectional weighted graph in which vertices depict cameras (their FOVs) of a video surveillance system, each edge describes possibility of transition between pair of cameras and a weight of the edge describes time of given transition between cameras. The behaviour model contains a knowledge about how objects typically move through the observed area. In other words the behaviour model is a set of object movement patterns. Thus, comparison of the observations and matching them into pairs is based on the following clues: appearance of object, spatio-temporal dependencies and behaviour model. In order to build a behaviour model, the idea of Pawlak’s flowgraphs is used as a basic structure to store a knowledge about behaviour of objects. However, some extensions and modifications must be made, in order to adapt this idea to behaviour modelling in video surveillance system. These modifications are related to the way of using input data – paths of objects observed in the supervised area. The analysis contained in this article is aimed to determine how space and time efficient is the FG as a tool prediction of object movement

This article is structured in the following way. In the Section 2 the background of the article’s topic is introduced. The Section 3 shortly present the idea of flowgraphs (hereinafter called as FG) and describe methods of the behaviour model creation and using it for route reconstruction. Next, in the Section 4 issues related to ways to store the graph in the computer memory. The Section 5 is devoted to presentation of FG implementation issues. Memory complexity and time complexity of the FG are analysed in the Section 6. In order to calculate complexities, the worst cases were assumed. Thus, the upper-bounds of complexities (notes as “big-O” – O(.)) were obtained. The next section (see Section 7) contains empirical measurements of used memory for storing FG and time of analysed (in the Section 6) operations on the FG. The article ends up with conclusions and future plans (see Section 8).

2 Related work

The re-identification underlies methods of tracking objects in non-overlapping video surveillance system. The literature presents many approaches to this problem, but all these methods have the same general characteristic. Re-identification algorithms use various kind of data to succeed, that are appearance (visual features), spatio-temporal dependencies (determination of the possibility given transitions in reality and description of a probable time of the transition) and behaviour model (in general related to determining more and less frequently used routes through the area observed with cameras).

Descriptors of visual features (broadly understood just as an appearance of object) are often used as a starting point to perform the re-identication task [4, 7, 11]. However, the only appearance of the object (physical features) are not enough to re-identify the object efficiently, because illumination conditions tend to change and technical parameters (or settings) of cameras also may differ.

Therefore, additional data, which are related to spatio-temporal dependencies between pairs of the cameras and a behaviour model, need to be obtained. These types of data can be derived from statistic data which are related to time of transition between particular pairs of cameras and a set of paths (sequences of visited locations by given object).

Analysis of the transition times as a result provides description of expected period between the moment of disappearing of object in a certain camera and the moment of appearing in another adjacent one. In simple way the expected transition time description can be realized as mean value [10], but it can be determined also as probability distribution function based on GMM (Gaussian Mixture Model) [15].

Additionally, on the basis of the set of object paths the certain paths can be distinguished as more frequent than others and also patterns of objects behaviour can be found. Various methods of behaviour modelling for video surveillance systems are presented in the literature. These methods are based on various approaches and algorithms like: particle filters [11], Bayesian networks [6], Markov chains [8], a dispersion function [10] etc. The idea of FG [5](after some modifications and extensions proposed by authors in previous works [2, 3]) can be applied as a container for knowledge about the behaviour of objects, on the area supervised with multi-camera system.

Details of creation and usage of the behaviour model incorporating the FG idea[3] and the method for adaptation of the FG to changing conditions [2] are also described in the literature.

As it was mentioned in previous research works [2, 3] authors introduced extension to the basic idea of the Pawlak’s FGs. The extension was in fact adaptation of the FG to behaviour modelling on the basis of data from the video surveillance system. In this article an analysis of the complexity of the modified FG, which is a further development of authors’ research, is contained.

3 Using flowgraph for route reconstruction

The idea of FG was introduced by Pawlak [12]. It is based on the rough set theory [13]. Moreover, the FG idea is also consistent with the Bayes theorem. In this section a method of using FG for reconstruction of object route through the area observed with a multicamera surveillance system is elaborated. In order to use FG to reconstruct object path within the supervised area some modifications have to be introduced. At the beginning the input form the video surveillance system needs to be prepared. Every object that enter the supervised area creates a path which is understood as a sequence of places observed with the consecutive cameras. An each such-determined path is a one sample (record or row) in a database (called also a set of paths) used as the input for building the FG.

Cameras of surveillance system correspond to real locations between which the objects can move. The example possible transitions are presented in form of the graph in Fig. 1. The cameras X and Y are considered as entrance or exit form the observed area. Moreover, transition between each pair of the cameras is possible. Thus, in general whole multi-camera system can be consider as a set of locations related to the particular cameras:

$$ C = { c_{1}, ..., c_{N} } $$
(1)

where c i is camera with i index and N is a number of the cameras (1 ≤ i ≤ N). Next, a path also can be defined:

$$ p = \{ (c_{id_{1}},1 ), ..., (c_{id_{L}},L ) \} $$
(2)

where \(c_{id_{1}}\) and \(c_{id_{L}}\) defines the the camera which is visited by the object on the entrance to observed area and on the exit respectively, values from i d 1 to i d L defines consecutive values of the index i from (1). Thus, the set of paths can be described as the following formula presents:

$$ P = \{ p1, ..., p_{M} \} $$
(3)

where M is the number of paths in the set. Having such prepared input data next steps of creating behaviour model can be carried out. Methods and mechanisms contained in the rough set theory are used to create a set of rules. These rules can be schematically describe as: I F (c o n d i t i o n s – one or more), T H E N (d e c i s i o n). In the rough set terminology the c o n d i t i o n s as well as the d e c i s i o n are called as attributes.

The mentioned modifications of the FG idea consist of changing elements of paths, stored in the set of paths P (the input), into sequences of attributes and combining all obtained rules into one data structure (that is the FG). Thus, attribute used in the FG contains two parts:

  • the index (number) that describes an order of this element in its path,

  • the label of camera in which an object appeared.

Thus, the attribute X 1 means that the given object was observed the first time (on entrance to the observed area) in the camera c 2 = ‘X’. When the definition of the attributes is made, the process of building the FG can be carried out. The methods for this purpose are described elaborately in the authors’ previous works (See [3] and [2]). Due to a limited size of this article details of used algorithms can be found in the quoted publications. An example FG is presented in the Fig. 2.

Fig. 1
figure 1

The example of the graph which presents possible transitions between cameras and determines entrance/exit cameras. According to (1): c 1 =‘W’, c 2 = ‘X’, c 3 = ‘Y’, c = ‘Z’

Full size image
Fig. 2
figure 2

The example of the FG for the video surveillance system containing four cameras. Labels W, X, Y, Z describes the cameras of the video surveillance system and vertical layers determines the consecutive steps of the path in time. The vertices labelled with O correspond to the end of path (exit from the observed area). Because each edge describes one rule (related to rough sets), the parameters of each rule can be assign to appropriate edge

Full size image

Every single edge in this graph corresponds to a certain rule (with a one condition attribute) in terms of the rough sets theory. For each rule parameters like strength, certainty and coverage can be calculated basing on the input data. Hence, the strength describes how often a given transition between the pair of cameras appeared in the whole set of paths, the certainty estimates the probability of transition to the next camera and the coverage measures the probability of transition to the given camera from previous one. Formulae (4) presenting the way of obtaining values of these parameters are shown below.

$$ \begin{array}{c c c} \sigma(x_{i}, y_{i+1}) = \frac{\varphi(x_{i}, y_{i+1})}{\varphi(G)} & & \sigma(x_{i}) = \frac{\varphi(x_{i})}{\varphi(G)} \\ \\ cer(x_{i}, y_{i+1}) = \frac{\sigma(x_{i}, y_{i+1})}{\sigma(x_{i})} & & cov(x_{j-1}, y_{j}) = \frac{\sigma(x_{j-1}, y_{j})}{\sigma(y_{j})} \end{array} $$
(4)

where x i , y i + 1, x j − 1, y j are the attributes and σ(x i , y i + 1) defines the rate of objects passing from camera x in step i of the path to camera y in consecutive step i + 1 of the path, φ(x i , y i + 1) determines the number of paths (in the input database) containing transition from x i to y i + 1, the total number of paths in the database is denoted as φ(G), and φ(x i ) is the number of paths in the input containing the step (vertex) x i . Additionally, the certainty (cer) estimates the probability that the object which left camera x in step i of the path will appear in camera y in the consecutive step i + 1 and the coverage (cov) determines estimation of probability that an object which appears in camera y in step j of the path was seen before in camera x in the previous step j − 1 of the path. These parameters (that are cer and cov) are used to determine which transition between the pairs of cameras are more probable. The certainty cer is used to predict future movements of the object and the coverage cov is useful in re-identification method. The cov is utilized during decision making related to identity of the object observed in two different cameras.

Moreover, a path (in the FG) that contains more than a two of vertices also describe a rule which contains more than one condition attribute. Such situation occurs, for instance, if prediction of object movement is related to more than one camera ahead. In order to carry out this information, a probability tree must be build. The formula used for creation of the probability tree and an example of such tree are presented in the (5) and Fig. 3, respectively.

$$ cer\left[x_{root},\ldots,z_{end}\right] = \prod\limits^{i=end}_{i=root} cer\left( x_{i}, y_{i+1}\right) $$
(5)

where the root of probability tree is denoted as x r o o t , the probability of the path from the vertex x r o o t to z e n d is calculated as a product of probabilities of subsequent steps in the given path. For more details about employing FG for re-identification method please look into the article [3].

Fig. 3
figure 3

The probability tree, which has a root in the vertex X 1, based on the FG from the Fig. 2

Full size image

3.1 Using flowgraph in re-identification

In order to make decision about the identity of the single real object which was observed in two adjacent cameras, what is the essence of the re-identification method, tree types of premises can be used. The appearance of the object can be presented as a vector of visual feature descriptors. The area observed with multi-camera surveillance system can be described with spatio-temporal dependencies which are contained in the form of graph (called a tolopogy graph). The last of premises is related to behaviour model. The behaviour model provides the information about probability of using the particular path while passing through the supervised area. Combining all these premises in a single formula gives the measure of the probability of identity of the single object observed in two places. The idea and formula are presented in Fig. 4 and (6).

$$ P(I) = w_{v}\cdot P(I_{v}) + w_{t}\cdot P(I_{t}) + w_{b}\cdot P(I_{b}) $$
(6)

where P(I) is the probability of object identity, P(I v ), P(I t ) and P(I b ) are probabilities of object identity based on visual features, the time of transition and the behaviour model, respectively, w v , w t , w b are weights of importance for the particular types of premises (visual, spatio-temporal, behavioural).

Fig. 4
figure 4

Combination of the three types of the premises as the essence of the re-identification algorithm

Full size image

4 Representation of graph in the computer memory

A graph as data structure can be represented in the computer memory in a few ways. Each form of representation has its advantages and drawbacks. Choice of the representation depends on the way of utilization and structure of a graph. In graph theory clear rational rules suggest which form of representation is the most suitable one. Thus, various types of graph representation are discussed in the following subsections. In order to present those types the sample graph, which is shown in Fig. 5, is taken into consideration.

Fig. 5
figure 5

Example undirected graph

Full size image

4.1 Adjacency matrix

Representation of the graph with the adjacency matrix A consist in marking the adjacency within the n × n matrix, where n is the number of vertices. The matrix A contains 0 (what means no adjacency) or 1 (means that the adjacency exists) values. Thus, taking into consideration the undirected graph G with n vertices, an element a i j , which is not placed on diagonal of matrix A (that is i ≠ j), determines if the vertex i is adjacent to the vertex j. An each diagonal element a i i describes the existence of a loop (form vertex i to itself) in the graph G. In order to clarify this conception, the example of adjacency matrix for the graph is presented as (7).

(7)

4.2 Adjacency list

In this type of the graph representation an each vertex has the one row of the list. Moreover, in every row the particular vertex is associated with its neighbourhood. There is no explicit representation of graph edges. Basing on the associations consisted in the consecutive rows of the list a whole graph (including edges) can be re-created. The example graph presented in the Fig. 5 can be represented in the computer memory as the Table 1 shows.

Table 1 The example graph represented with the adjacency list
Full size table

This representation type is intended for obtaining a list of the neighbourhood of the given vertex. An adjacency list allows for performing constant time of access to each neighbour, so access to the whole neighbourhood of particular vertex depends on the degree of it. All descriptions of the graph representations is prepared in reference to the literature [1, 9, 14].

4.3 Incidence matrix

The third way of representation of a graph in the computer memory is called incidence matrix. It is similar to adjacency matrix B (rows correspond to the vertices in which edges start or end), but in this case columns are related to the edges. The incidence matrix for the example graph (see the Fig. 5) is shown in the (8).

(8)

For undirected graphs each row determines if particular edge start or end in the given vertex (what is marked with a number 1). According to this in each column (b e 1 , b e 2 , b e 3 ,...) there should be two elements equal to one. Only in case of loops in the graph there is only one element equal to one. In the considered example (See Fig. 5 and (8)) such situation appears in relation to the vertex 1 and the edge e1 which is reflected in the element b 1, e 1 .

4.4 Justification of using the adjacency list for the flowgraph storage

The following (see Table 2) memory and computational complexities for the aforementioned representations of the graph can be found in the literature[1].

Table 2 Complexities of various types of graph representation
Full size table

Let’s consider a certain number of cameras C and a number of steps in the longest object path L. It is worth remarking that the number of vertical layers in the FG (see Fig. 5) corresponds to the value of L. Assuming that transitions between all pairs of vertices (cameras) appear in the FG. In other words the object can move between any pair of cameras and in the FG are all possible edges according to rules of building the FG (see [3]). Hereinafter a such FG will be called as a full FG. In practice full FG are few and far between, but the worst case (the most complicated FG) are considered in this article. In this case there will be N = (C + 1) ⋅ L vertices and E = C 2 ⋅ (L − 1) + C edges. The next assumption (which will simplify the calculations) consists in granting that the longest path contains each of cameras just one time. Thus, in the considered FG will be N = (C + 1) ⋅ C vertices and E = C 3 − C 2 + C. In the literature a distinction on sparse and dense graphs can be found [1, 9]. The dense graphs have almost the maximum number of edges (determined as O(n 2)) and sparse graphs are described as having significantly less edges. Therefore, in case of the thought-out FG there is the following situation:

$$ \begin{array}{c} E = C^{3} - C^{2} + C \\ N^{2} = \left( C^{2}+C\right)^{2} = C^{4} + 2 \cdot C^{3} + C^{2}\\ \\ E \ll N^{2} \end{array} $$
(9)

Thus, the number of edges E is much lower than the squared number of vertices N 2. Consequently, the flowgraphs can be considered as sparse graphs. Therefore, the most suitable representation in the computer memory is the adjacency list (according to [1, 14]).

5 Flowgraph Implementation

In order to implement FGs an application (developed in C ++) based on BGL (Boost Graph Library) was created [14]. According to guidelines presented in the Section 4.4 the adjacency list was used for representation of FG in the computer memory. The adjacency_list class allows for implementation of the graph interface available in the BGL for more sophisticated purpose. The template parameters makes this class well-configurable and adjustable to various implementations with regard to computational or memory efficiency. Utilized data structures is descripted with the following pseudocode. Additionally, it is presented in Fig. 6.

Fig. 6
figure 6

Data structure of the modified flowgraph

Full size image

Node

{

string name;

int layer;

double strength;

double counter;

};

Path

{

double cer;

double cov;

double strength;

double counter;

pair<int> edge;

};

Flowgraph

{

vector <Node> vertices;

list<Path> edges;

map <string, int> vertex_labels;

// used for storing labels of the vertices

map <int, vector<int>> verex_layers;

// used for easy searching for vertices of one layer

int countAccumulator;

};

6 Complexity analysis

The first stage of the experiment was preparation of the full FGs for the various numbers of cameras. The consecutive letters of the alphabet are labels for the cameras. The exception is the notation ‘o_{number}’ which determines that the object end its path and left the supervised area.

6.1 Memory complexity of the flowgraph

As it was mentioned before the space efficiency depends on the utilized representation of the graph in the computer memory and a density of edges in the graph. Using the adjacency list entails O(|V| + |E|) space complexity. Thus, in order to estimate the memory complexity that depends on the number of cameras C, the following formula (see (10)) has to be considered.

$$ O(|V|+|E|) = O(C^{2} + C + C^{3} - C^{2} + C) = O(C^{3} + 2C) = O(C^{3}) $$
(10)

Consequently, the memory complexity depending on the number of cameras is O(C 3).

6.2 Computational complexity of operations on the flowgraphs

A computational efficiency strongly depends on a graph representation used to store the FG in the computer memory and actual structure of the flowgraph. Moreover, the choice of containers (from STL) also has impact on the complexity. In the below considerations “full FG” will be used to determine the upper bound of the computational complexity. Few (mostly used) operations on the FG and them complexities will be presented.

6.2.1 Updating of the flowgraph

While adding a new path to the FG only counters (that are Node::counter, Path::counter and Flowgraph::countAccumulator) are increased. Because of that adding even the one path has impact on the whole FG, so the properties (certainty, strength and coverage) updating of all edges and vertices has to be carried out. The update operation consist in the calculation of new values of (certainty, strength and coverage) parameters basing on updated values of counters. Thus the complexity of this operation can be determined as the (11) shows.

(11)

Since looking through the whole data structure is needed, the computational complexity is similar to the memory complexity (also in accordance to the number of cameras C).

6.2.2 Adding a new path to the flowgraph

This operation operation depends on the number K of steps in the new path p as well as on the number of vertices |V| and edges |E| in the FG. The first stage of this operation is finding vertices for all elements in the path p and incrementation of Node::counter and Path::counter properties of them. The next one is changing counters of the edges between these vertices. Because using of std::vector as a container for storing of the vertices, access to each of vertex is direct (that means in constant time – O(1)). The time complexity for finding edge (as std::list is used for storing edges) can be describe with \(O\left (\frac {|E|}{|V|}\right )\). The formula \(\frac {|E|}{|V|}\) is used to express how long is an out-edge list. It means a general average number of edges for a vertex. For dense graphs (|E| ≅ |V|2) this value will be near the number of vertices |V|, but for sparse graphs (like FGs) it will be much smaller. In case of full FG the maximum number of out-edges for one vertex is the number of cameras in the video surveillance system C. The worst case happens when the length of path K will be equal to the number of cameras C. The formula presented below (See (12)) describes the time complexity of adding a new path to the FG.

(12)

6.2.3 Obtaining the values of the flowgraph parameters

Using the FG in re-identification methods consists mostly in getting values of certainty, coverage or strength from the FG. In order to predict future movement of the object, the values of certainty parameter for all out-edges of given vertex must be obtained. As the label of the vertex is known the time of finding it in the FG is constant (O(1)), however the time of finding all out-edges is \(O\left (\frac {|E|}{|V|}\right )\). Making the same assumptions like in the previous subsection the time complexity of obtaining the certainty parameter for all out-edges of the given vertex is expressed with the (13)

$$ O\left( \frac{|E|}{|V|}\right) = O(C) $$
(13)

6.2.4 Creating the probability tree based on the flowgraph

In this subsection it is worth to notice that the FG can be classified as a directed acyclic graph. It implies that the FG has its start and its end. Moreover, as it was mentioned, consecutive vertical (see Fig. 2) layers can be distinguished in the FG. These layers are related to the particular steps of the paths (from the input database) on which building of the FG was based. Thus, in the first layer all vertices have only out-edges and in the last layer there is one vertex having only in-edges.

Creation of the probability tree consists in cutting a part of the FG. In order to preform this operation, one of the vertices in the FG must be chosen as a root of the tree. Then, all internal vertices are leafs. A leaf and an internal vertex are vertices of degree 1 and degree at least 2, respectively. An example probability tree is presented in the Fig. 3. The time complexity of creating the probability tree depends not only on the number of cameras C, but also on the layer R in which the root vertex is placed and the number of layers L in whole FG. In these considerations the worst case is taken into account (usage of the full FG), hence the layers after the root one (layer R + 1) contains number of vertices equals to the number of cameras C. Choosing the root from the first layer (R=0) results in the longest path that can be predicted. The elements of predicted path is known while obtaining the probability. Therefore, the formula which describes this time complexity of obtaining the single path certainity is given in (14).

(14)

7 Complexity measurements

In this section complexities of operations on the FGs empirically measured, in order to validate theoretical analysis presented in the Section 6.

Memory complexity of the FG was determined as O(C 3). Results of measuring the space needed to store FG are shown in the Fig. 7. This figure presents also the trend line which can be approximated with a third-degree polynomial.

Fig. 7
figure 7

Amount of space needed to store FG in the computer memory depending on the number of cameras in the surveillance system (blue markers), with the orange dotted line approximated trend is presented

Full size image

All measures related to the time complexity were obtained as summed time of 1000 iterations of the same operation. In each iteration input parameters for the particular operations were generated randomly.

Refreshing of the FG is important operation while adding a new path to the FG. It needs to access and update all vertices and all edges, so it’s a quite time-consuming method. In practice refreshing of the FG can be performed for a group of added paths. The time complexity of refreshing of the FG was determined as O(C 3). Beside times needded to perform 1000 iterations of the refreshing operation, the trend line approximated with a third-degree polynomial is also presented in the Fig. 8.

Fig. 8
figure 8

Time efficiency of the FG refresh operation (blue markers). The trend line is also presented with the orange dotted line

Full size image

In the Section 6.2.2 the computational complexity of the operation of new path adding was determined as O(C 2). As it is shown in the Fig. 9 the time efficiency of this operation can be approximated with a second degree polynomial.

Fig. 9
figure 9

Measures of time needed to perform 1000 iteration of adding a new path to the FG (blue markers). The orange dotted line presents the trend

Full size image

Building the probability tree is the first step of prediction of the future movement of given object. The computational complexity of getting probability of the whole path from the FG was determined as O(C 3). Measures presented in the Fig. 10 verify that time of obtaining probability of the whole path can be approximated with a third-degree polynomial.

Fig. 10
figure 10

Time measurement of getting a probabilities of the whole paths (as most important part of building the probability tree). Approximation of the (orange dotted) line trend is also included

Full size image

In the end, the most frequent operation performed in relation to re-identification methods is obtaining the probability of single transition between two cameras. The flowgraph represented with an adjacency list (in the computer memory) provides the access time to the parameters (like certainty and cover) which is linearly dependent on the number of cameras. It was confirmed by the measurements presented in the Fig. 11.

Fig. 11
figure 11

Measures of time needed to perform 1000 iteration of obtaining the certainty parameter from the FG (blue markers). The orange dotted line presents the trend

Full size image

8 Conclusions

The FG represented in the computer memory as the adjacency list allows for time efficient operations of this data structure. The time efficiency of the most important operations for re-identification algorithms was empirically tested. The complexities obtained theoretically were validated with these experiments. The adjacency list is proper form of the FG representation, because it provide very fast access to data contained within the weighted directed graph. Even the full FG is still a sparse graph and it is worth to store it as the adjacency list from the point of view of the memory and computational complexity. In case when the number of cameras C is not changing the complexities presented in this article are constant (O(1)).

The future works related to the topic of the article will be focused on the computational analysis of the adaptation method proposed in the previous authors’ work [2]. Moreover, a parallelization of the operations on the FGs is considered.