# Using Extended Raster File for Real Time Traffic Information Mining

Michal Radecký, Jan Martinovič, Dušan Fedorčák, Radek Tomis, Ivo Vondrák

► To cite this version:

Michal Radecký, Jan Martinovič, Dušan Fedorčák, Radek Tomis, Ivo Vondrák. Using Extended Raster File for Real Time Traffic Information Mining. 11th International Conference on Computer Information Systems and Industrial Management (CISIM), Sep 2012, Venice, Italy. pp.416-427, 10.1007/978-3-642-33260-9_36. hal-01551735

HAL Id: hal-01551735

https://inria.hal.science/hal-01551735

Submitted on 30 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Using Extended Raster File for Real Time Traffic Information Mining

Michal Radecký, Jan Martinovič, Dušan Fedorčák, Radek Tomis, and Ivo Vondrák

VŠB – Technical University of Ostrava, 17. listopadu 15,
IT4Innovations,
708 33 Ostrava, Czech Republic
michal.radecky@vsb.cz, jan.martinovic@vsb.cz,
dusan.fedorcak@gmail.com, ivo.vondrak@vsb.cz

**Abstract.** Gauging and analyzing the ever-growing strain on todays roadways is an issue that needs to be addressed with urgency. The rate at which technology is developing and the amount of vehicles now equipped with GPS systems are factors that ensure the potential for creating statistics to gauge this strain. When processing data gathered from monitored vehicles, it is necessary to implement procedures that identify specific roadways upon which a given vehicles movement is recorded. With respects to the volume of this data, a method for indexing these data files becomes a critical issue. Within the following text, we will present a process of collecting and processing data in the FLOREON+ Traffic system and spacial indexing using a raster index that processes queries at a much greater speed than standard indexing.

## 1 Introduction

The problem with analyzing the increasing strain on today's roadways lies within the fact that monitoring is limited to major intersections and trouble spots, where modern camera systems have become the norm. Publicizing information gathered from these areas leads to faster solutions in crisis situations and aids in the overall elimination of such crises. A great disadvantage in this approach, however, is the fact that a crisis situation needs to be identified in advance in order for it to be resolved in time. A system based on collecting and processing data derived from a vehicle in real time may contribute to the exploitation of this disadvantage - the ability to monitor only vehicles where this equipment is installed. Currently, the amount of vehicles thus equipped is too large for a system of this type to be of any significance or to even be successfully implemented.

Floreon⁺ is a science-research project aimed at building a prototype system for modeling, simulating and monitoring situations caused by unfavorable, natural phenomena using modern computer and Internet technology. The main feature of this project is its focus in the area of crisis management and support. The project has gradually expanded to cover relevant topical fields, such as flash flooding, and other factors pertinent to crisis management and general information services.

Recently, traffic problems have become a recurring issue to be dealt with on a daily basis in various forms and at several levels. Aside from the everyday traffic situations
perceived by drivers, crisis situations, management and solutions must be taken into account. This is precisely why the field of traffic information and management are intricate parts of the Floreon⁺ project. Knowledge of traffic situations and the ability to utilize sophisticated apparatus to effectively process this information are significant factors for an entire line of activities from the perspective of crisis management (e.g. which traffic lanes are clear for emergency unit passage, which areas are flood hazards, etc.). Additional benefits would obviously include the acquisition and processing of everyday traffic situations and activities (intelligent navigation systems for automobiles in metro areas, analyzing high-traffic zones, detecting problems on roadways, etc.)

The Floreon⁺ Traffic system makes calculations (in real time or for potential situations) by utilizing a complete line of information derived from various sources. Data acquired in this manner is then analyzed and adjusted to fit a format that is then usable in the aggregation of this data with connection to time and space. Currently, the main information source remains the vehicle itself. Thanks to our cooperation with companies involved in monitoring car parks, we are able to acquire surface data and individual car speeds in real time. Individual data acquired in this way is anonymous enough to fulfill its purpose. Once received, this information is combined with other data relevant to a given traffic area at a given time. The system actually works with data to determine an automobiles' speed and driving style.

## 1.1 Navigation systems

Nowadays, the modern technology, especially information technology, is one of the main parts of automotive industry. There are many new features which bring new driving experiences and encourage driver's skills, e.g. adaptive cruise control, lane assistant or traffic signs reader. However, the on-board navigation is still most common tool for daily personal transportation.

For today's drivers, it is very useful and required to know the route from the one place to another. Unfortunately, the simple knowledge of static route itinerary is not enough. There are many factors which affect the travel time and efficiency of the selected road. These factors are changed during the time and they are also depending on time. So, it is necessary to integrate dynamic models of traffic within the routing approaches to offer real-life navigation functionality. These dynamic models can cover real behaviors of traffic on macro level based on time, knowledge of statistical data related to infrastructure elements, knowledge of real traffic occupancy and utilization, etc. Based on these, it is able to develop much more sophisticated routing algorithms that bring whole new perspective on the on-board navigation systems. But of course, on-board navigation is not only one 'consumer' of such approaches and theirs results. Also the traffic management or logistics business are covetous users of that.

The crucial layer of these approaches is data layer. The ability to collect relevant data and its preprocessing are the very important parts. It is hard to develop dynamic models without suitable data related to the time and location. The information on streets capacity, its utilization, traffic restrictions and incidents, traffic jams, weather, etc. is necessary to have as a background for dynamic model development and operation. Some of these data (GPS positions with speed value) are possible to collect based on cooperation with car fleet providers, however these data are often geographically and
quantitative limited. The companies that develop and offer navigation solutions are able
to solve these problems. For example, the TomTom company offers the IQ Routes tech-
nology <fnref n="1" />, that deals with standard on-board navigation devices and theirs users which
participate on global traffic state knowledge. This solution puts, by online or offline
ways, the driving experience of millions of TomTom users into central knowledge base
and calculating routes based on current day time, actual speeds driven on roads com-
pared to speed limits.

The future of navigation and other related tools and services is covered by integra-
tion of all accessible data sources and its utilization within complex traffic model. On
this background, there is able to offer sophisticated

## 2 Floreon⁺ Traffic

We are currently receiving information on approx. 2,200 vehicles of different types (passenger cars, cargo trucks, lorries, etc.). This data is aggregated into a simple, speed fast profile in real time around the entire Czech Republic. (Coverage is only dependent upon the accessibility of vector data. Acquired data is currently limited to identifying major roadways because an application that covers all streets would not be relevant enough with respect to the amount of moving vehicles and the vastness of this network.) In the near future, we plan to carry out much more detailed analyses of this data in a way that allows us to randomly expand the grid structure of intersections. This expansion will aid in creating a necessary base of information for evaluating operations and applications of graph algorithms.

Currently, the system is receiving anonymous records from approx. 2,200 vehicles.
During rush hour, that equates to about 13 records received/second. Taking into account
the algorithm being applied, unprecise GPS readings and, specifically, relevant vehicle
data (unignited engines, etc.) the success rate for the placement of given information on
a specific location is around 30%.

This information is generally highly relevant to the value of real time situations on roadways. Nonetheless, due to the need for high quality and a large quantity of acquired data, this information must be supported with data derived from alternate sources. The most significant data acquired is, therefore, that which is acquired directly from a given infrastructure. Such data may be derived from toll stations, telematic sensors, camera systems, etc. Within the scope of their given locations, these sources may influence aggregated data derived from a specific roadway. The advantage provided by these data sources is the high level of precise information they provide (amount of vehicles passed, etc.). On the other hand, the disadvantages of using these tools as data sources are their predominately localized scope and their high investment and operational costs. However, an appropriate combination of data acquired on-line and data acquired directly from infrastructures allows for the creation of a quality image of the overall traffic situation.

An equally important data source would be that of an agenda system that provides
information on traffic accidents, road closures, weather, etc. The potential of this alter-

<footnote n="1">¹TomTom: http://www.totom.com</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. Floreon⁺ Traffic</figcaption></figure>

native as a valuable source is currently being developed in cooperation with operators of the JSDI system (A unified traffic information system in the Czech Republic).

Floreon⁺ Traffic system (scheme in Figure 1) output may be assessed and defined in different ways. Emphasis, however, is placed on its future potential. Aside from providing aggregated data for additional processing, we envision future benefits of this system in the following outputs, applications and expansions:

- Detailed statistical information for individual areas, streets, and roadways.

- Accountability for evaluating roads according to amount, quality and data source influenced by a given road.

- Visualization of entire lines of communication (camera systems, traffic accidents, data quality, etc.) in 2D and 3D imagery.

- Provision of functions and operations on data (searching for optimal roads, etc.).

- Processing and integrating data derived from various data sources (JSDI, telematic equipment, meteo. data, digital images, etc.).

- Analysis of historical data with current situational perspectives (automatic detection of problems on roadways based on comparisons of normal speeds and actual speeds on a given road).

- Application of higher level algorithms (e.g. anthill theory, flood wave algorithms) to create predictions and simulations usable in other systems, primarily from a traffic management perspective.

The applicability of this entire system lies directly in its dependence on data, its quality, quantity and heterogeneity. The advantage in using data acquired directly from vehicles is in their surface coverage and immediate accessibility, regardless of their lack of relevance. Once this approach is combined with data derived from telematic sensors, for example (limited to local placement, but highly reliable and precise) it will be possible to create a total and real traffic situation model.
## 2.1 Collecting and Processing Data

As mentioned above, the project we are dealing with is based on collecting and processing data, derived directly from automobiles equipped with GPS functions that are able to send spacial data to a distant server in real time, where it is to be processed. The process then becomes a joint attempt at identifying a roadway where a vehicle is in motion. Using this identification, we place a spacial query above the roadway network. From data prepared in this manner, it becomes possible to effectively set statistics for roadway strain and appropriately visualize their results.

Raw data derived from a vehicle is sent at an amply high rate, i.e. at an average of 1 vehicle/10sec. With an adequate set of monitored vehicles (in our case, we have calculated with 20,000 vehicles), we attain the desired speed of 2,000 recordings/sec. Data derived from vehicles obviously does not flow at a constant rate. This issue, however, may be easily resolved with an appropriately-sized memory. One question remains, however, as to whether it is at all necessary to process raw data in real time. If we perform a rough estimate of memory complexity, say for a two-month interval of a monitored traffic situation, for a recorded surface and a vehicle's speed, we quickly reach hundreds of gigabytes of stored data. With data processed from an identified roadway, upon which their is vehicular movement, we achieve a much lower volume of data (this obviously depends on the strain of traffic on the given network of roads being processed).

Another factor is the speed at which data is processed. Whether we process data in real time or in batches, identifying roadways where there is vehicular movement is both time consuming and technologically demanding. We will also need to factor in several potential difficulties that will likely arise, of which the most significant may be GPS precision. For this, it will be necessary to carefully install error intervals to aid in partially eliminating this problem.

Another issue is the actual size of the roadway data file itself. In order to provide meaningful statistics, it will be necessary to include second class roadways. A file this size for the entire Czech Republic will be quite large and it will have to be queried for every processed recording from every vehicle being monitored. If we use the PostgreSQL tool <fnref n="2" /> as a reference database, with PostGIS <fnref n="3" /> space expansion, and the commonly used GiST index, the speed a spacial query is sent to the roadway database will still be dependent upon the size of the data file itself. As described above, this data file is quite large and it is almost impossible to reach process speeds greater than 2,000 queries/sec. For this reason we have decided to develop our own method of indexing, based on scanning domains, making time complexity independent of the amount of indexed data.

## 3 Raster Indexing Spacial Data

The principle of raster indexing, in and of itself, is quite simple. In several aspects, it is very similar to bitmap index. Simply put, a spacial raster index is a very big picture

<footnote n="2">²PostgreSQL: http://www.postgresql.org</footnote>

<footnote n="3">³PostGIS: http://postgis.refractions.net</footnote>
where all indexed recordings are drawn (geometry). Instead of using colors, recordings
are "drawn" with an identifier. We can then effectively direct queries to this type of
index (we can query the "color" of a specific pixel). The complexity of this type of
query will obviously be constant. One issue with raster indexing is the limited amount
of whole-number attributes upon which the index is performed. We must be able to
clearly name all values of a given attribute in order to be able to use it for indexing.
The raster index will then contain a paired key-value, where the keys are all value
combinations of an indexed attribute and the value is the recording identifier that
answers to a combination of attribute values. The index file itself does not contain a key
because it is already possible to encode a key to a position within the index file. A raster
index defined in this way has one evident disadvantage: it is not possible to index two
recordings with identical index attribute combinations. A solution for this shortcoming
is described below.

As far as spacial data is concerned, the whole-number issue presents quite a signifi-
cant problem. This problem is, however, resolvable. We must set an area border for the
raster index we are creating and the resolution with which we will be working. Here,
we come up against one troublesome aspect of raster indexing: with resolution comes
inaccuracy. When creating an index, it is necessary to consider the application for which
the index is being used and, based on this, set the adequate resolution.

Constant complexity, for which point queries are carried out, is attained with a mas-
sively increased complex memory. For the project of measuring roadway strain, we
have chosen a spacial index resolution of 5m/pixel. Since a raster index is actually a
discretely modeled, spacial index data domain, the size of the index created surpasses
the size of the data file many times over. Aside from the amount of space used up in
the discs storage, this issue does not present any additional complications. We must,
however, factor in the disadvantage of occupied space in the discs storage. Since the
data file itself does not change, the index file does not change either. If only the data
file changes, however, it still is not necessary to go through the entire index file; just
going through the space within which the data file appeared is sufficient. The interval in
the index file which needs to be renewed is again identifiable with constant complexity.
Creating, querying and maintaining a raster index for spacial data is subject to several
other rules and conditions, to be described in a later section.

## 3.1 Raster Index Construction

As described above, we have constructed a spacial index for analyzing roadway strain
that features the following properties: the size of the indexed space has been chosen so
that the entire Czech Republic is covered and the resolution has been set at 5m/pixel.
The structure of the index file, in its basic form, is as follows: the file contains a head-
ing with a configured index (see Table 1) followed by a frame saved in the identifier
recording. Every frame contains a matrix of 1024 x 1024 identifiers (see Figure 2). The
frames are saved in the index file in rows.

The indexed data file itself is performed as follows: we gradually go through the
space defined by inputting intervals and queries as commonly done with spacial databases
(with a resolution of 5m/pixel, that equates to a square with a 5,120m edge) and we draw
(raster) the resulting object onto a tile. Tiles are gradually saved in the file.
<table><caption>**Table 1.** Header of the index file</caption><thead><tr><td>byte</td><td>Value of</td></tr></thead><tbody><tr><td>0..2</td><td>RID</td></tr><tr><td>3..6</td><td>Resolution (in meters, float)</td></tr><tr><td>7..10</td><td>Left Margin (SJTSK, float)</td></tr><tr><td>11..14</td><td>Right Margin (SJTSK, float)</td></tr><tr><td>15..18</td><td>Number of frames - width (int)</td></tr><tr><td>19..22</td><td>Number of frames - height (int)</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Structure of the index file</figcaption></figure>

The spatial point query for this type of index then simply lies in the index file based on its assigned coordinate. This results in the identifier object being located on the squares edge, measuring 5m (index resolution), despite its assigned coordinate being in the center of the queried square.

A spatial index constructed in this way, however, has several negative properties. For example, it is impossible to record more objects in one cell, which may present a big problem in the case of roadways. Another problem is the size and effectivity of the saved frame within the index file. Methods for countering these negative properties will be described in the following chapter.

## 3.2 Raster Index Optimizing

The first problem discussed, saving more files in one cell, can be easily solved by expanding cell recordings. In place of an identifier, we are going to store a paired-sign identifier. Within the one-byte field of signs, we can save information clarifying whether this position is just one object or if there are more objects present. Within the scope of a one-byte field signal, we can save information on whether this position is occupied by either one or more objects. If there is more than one object present, the object identifier is not saved here; its position is saved with the aid of a file where the situation is recorded in a query space (e.g. 3 objects with their identifiers). Another option for expanding cells saved on the frame is very closely related to indexing roadways. One valuable piece of information useful in expanding cells is the position of a queried point for a given roadway (defined as the distance from the start of the roadway, and running parallel to the entire queried point). Knowing this information enables us to effectively analyze and save data about a strained roadway without having to separate
it geometrically into smaller segments. Here, It is important to consider the fact that
every expanded cell within the recording increases the-overall index file size. If we had
an identifier saved as a 4-byte whole number, expanded by a sign byte and the road
position (4 bytes, float), our index file size increases by more than half its original size.
This is best possible option for optimizing memory complexity.

By performing simple statistical calculations on an index file, we find that in the
case of an indexed roadway (generally all LineString data types), the final index file is
more than 90% "empty". The aim of lowering memory complexity will then depend on
our ability to avoid saving empty space in the index, if possible. The solution to this
problem is to build a quadtree [6] above the matrix frame that is saved in the index
file. All nodes in the quadtree will then contain a sign informing us whether or not the
frame below it is empty. If not, every leaf contains a frame position in the index file (see
Figure 3).

<figure><img src="image_4.png" /><figcaption>Fig. 3. Quadtree - two gray leafs are pointing at frame position in the index file</figcaption></figure>

Implementing a quadtree actually increases the time complexity of a queried index,
but this complexity is dependent on the size of the queried space, not on the amount of
indexed data. If we have a raster index the size of *n* pixels, we will need log*n* layers in
order to get to only one tree root. A certain disadvantage here may be the square index
space and limitations in the size of the line value 2*n*.

We do not need go all the way down to the root of the tree, though. We can just set
an index from the matrix of the quadtree, which will allow us to partially eliminate the
aforementioned shortcoming.

The next and last optimization for the system stems from the input of monitored
traffic situations using GPS. GPS alone is able to determine a vehicles position within
approx. 5m. Using maps to identify roadways with vehicular movement is also, at times,
inaccurate; which is why the resulting overall error is added to the identification of a
roadway error. This problem is well-resolved by defining the width of a road before re-
rastering its geometries in the index file. Paralleling this example would be like drawing
a fatter line over a fine line using a bigger marker. An index created in this manner is able
to smooth out smaller errors, even though it may cause further issues, especially when
two rows lie very near one another (e.g. a highway that has directions recorded as two
differing geometries). This shortcoming may be eliminated by recording perpendicular
distances from the center of the roadway, again, at the cost of increasing the index files size.

# 4 Result from System FLOREON⁺ Traffic

We are currently receiving information on approx. 2,200 vehicles of different types (passenger cars, cargo trucks, lorries, etc.). This data is aggregated into a simple, speed-fast profile in real time around the entire Czech Republic. The overall coverage (with speed profile visualization) of the Czech Republic by floating cars used in FLOREON⁺ Traffic system is on the Figure 4.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** The overall coverage of FLOREON⁺ data with speed profile visualization</figcaption></figure>

The above mentioned approaches form a background for a whole operation of traffic data processing. It is performed by FLOREON⁺ system on the data storage layer, data mining layer, as well as visualization of results layer. It is important to note that the real traffic data from vehicles is not only source of information important for building traffic model and profiles. Also agenda data (traffic conditions and limitations, etc.), weather data, infrastructure data, live-cam data, etc. are important for that. The integration and combination of a wide set of data sources provide a real power to create effective and usable traffic model. So, this system is responsible for

- receiving the data from its providers (fleet car provider, provider of traffic infrastructure state, weather provider, etc.),

- aggregating the data based on time division and the location of a given records,

- preparing and performing the algorithms working with a wide range of data,

- concentrating all of these to the traffic model on micro, meso or macro levels and also providing simulation based on this model,

- preparing the outputs for following utilizations or integration to other systems.
The Figure 5 and Figure 6 depict a set of graphical outputs based on data processed by the FLOREON⁺ Traffic system. Also, the traffic visualization is a part of functionality of general FLOREON⁺ web interface <fnref n="4" /> which is developed with emphasis to user experiences. The Microsoft Silverlight technology <fnref n="5" /> is used for that. The next figure is a screenshot taken from this our rich internet application.

<figure><img src="image_6.png" /><figcaption>**Fig. 5.** Map visualization of speed profiles on the infrastructure (Ostrava, Czech Republic). The information on traffic conditions (roadwork, weather, etc.) is also included, as well as real-time camera view.</figcaption></figure>

The main pitfalls of this approach is the primary dependence on the floating car data [9, 10], their quality and quantity. Amount of input data can be significantly reduced during the processing. Some data has not sufficiently informative value or are geographically inaccurate. This index based approach, where the individual anonymised records are assigned to a road, is loss (some amount of data is useless due to above mentioned reasons). The elementary knowledge of the motion vector of data sources would be an important contribution to the efficiency of data processing. Thanks to this, it should be possible to process not only one single location, but also the direction of the motion. It allows more complex traffic data processing. Unfortunately, this approach is unfeasible due to law on anonymity and data protection.

# 5 Conclusion

We presented the method of fast querying to the map of the road network based on the raster index. The method was experimentally and operationally verified by running

<footnote n="4">⁴FLOREON⁺: http://www.floreon.eu</footnote>

<footnote n="5">⁵Silverlight: http://www.silverlight.net</footnote>
<figure><img src="image_7.png" /><figcaption>**Fig. 6.** A different type of floating cars data visualization is shown here. The anonymous locations and speeds are placed on the map and create basis for indexing algorithms. Not all of these 'circles' involve the speed limit of particular road due to infrastructure limitations and GPS inaccuracy.</figcaption></figure>

FLOREON⁺ for three years, receiving information about approx. 2,200 vehicles every day. Obtained and aggregated data will be used for dynamic routing, which means data for routing will be updated accordingly to average situation on a given road section during day. In future work, we will be implementing this to our own version of routing, which is the combination of Highway Hierarchies [7, 8] and heuristics [5, 4] and also to our approach of road network updating during accidents. We presented earlier in [2]. Next step is preparation of other types of indexes for routing. Currently, we are creating the index for routing algorithms based on OpenStreetMap data <fnref n="6" />, which will also be used for optimized algorithms working on these data. There are sometimes incorrectly stated speed limits in data, so it's useful to replace them with average speeds on roads received by previously described method directly from vehicles.

## Acknowledgment

This work was supported by the European Regional Development Fund in the IT4Innovations Centre of Excellence project (CZ.1.05/1.1.00/02.0070).

## References

1. Bargera, H. Evaluation of a cellular phone-based system for measurements of traffic speeds and travel times: A case study from Israel. Tramsportation Research Part C: Emerging Technologies 15, 380-391 (2007).

2. Kromer P., Martinovic J., Radecky M., Tomis R. and Snasel V. Ant Colony Inspired Algorithm for Adaptive Traffic Routing. NaBIC 2011, Salamanca, Spain, 2001.

<footnote n="6">⁶OpenStreetMap: http://www.openstreetmap.org</footnote>
3. Gajdos P., Radecky P., Jan Martinovic, et al. Floreon plus system: Web applications with 3D visualization support. NDT 2009, Ostrava, Czech Republic, 2009.

4. Goldberg A.V. and Harrelson C. Computing the shortest path: A* meets graph theory. Technical report, MSR-TR-2004-24, 2004.

5. Hart, P.E., Nilsson, N.J. and Raphael, B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions On Systems Science And Cybernetics 4, 100-107 (1968).

6. Samet, H. Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2005.

7. Sanders, P. and Schultes, D. Highway Hierarchies Hasten Exact Shortest Path Queries. In European Symposium on Algorithms 3669, 568-579 (2005).

8. Sanders, P. and Schultes, D. Engineering Highway Hierarchies. Engineering 4168, 804-816 (2006).

9. Schfer, R.-P., Thiessenhusen, K.-U. and Wagner, P. A traffic information system by means of real-time floating-car data. ITS World Congress, 1-8 (2002).

10. Sohr, A., Brockfeld, E. and Krieg, S. Quality of Floating Car Data. 12th World Conference for Transportation Research, 1-7. World Conference on Transport Research Society, Lisabon, Portugal 2010.