Towards Formal, Graph-Based Spatial Data Processing: The Case of Lighting Segments for Pedestrian Crossings

Abstract

The paper proposes a graph formalism for flexible and efficient manipulation of geospatial data. Its main practical application is preparation of data for lighting optimisation projects in conformance with regulations. The formalism is based on the extended Semantic Environment Graph, already proposed in our previous work. A simple example of a one-way street with a pedestrian crossing is used to illustrate each step of the proposed procedure. The process involves executing a series of graph productions, which introduce the new shapes into the data. Implementation is not the main focus of the paper, but results of conducted studies are provided to present the practical implications of the proposed method, compared to the traditional approach used by lighting designers.

This research was supported by the AGH University of Science and Technology grant number 11.11.120.859 and co-financed by the Polish National Centre for Research and Development grant number POIR.01.01.01-00-0037/17 funded from European Funds and granted to GRADIS Ltd.

1 Introduction

As the technology used for street lighting becomes more precise and efficient, with LED fixtures available for a vast spectrum of lighting situations and requirements, the quality of photometric designs becomes ever more important.

The new regulations reflect this trend. Taking the European EN 13201 standard [6,7,8,9, 11] as example, one can see a wide spectrum of lighting classes along with precise rules when they should be applied. They define the guidelines aimed at maintaining the safety of the road users while making the system as energy efficient as possible. The latter is usually obtained by decreasing the unnecessarily high light intensity, which lowers both the operational (energy) costs and the investment expenditure, by allowing the purchase of less powerful luminaires. It also contributes to the reduction of light pollution, which is a very important hazard, both to human health and to other species [19].

LED fixtures can be dimmed with a virtually linear power-to-intensity ratio, and can be matched to fulfil virtually any lighting class on a road of any shape with greater precision than older HPS (high pressure sodium) devices. This gives designers the possibility to vary the illumination of even small parts of streets to reflect fine-grained requirements.

The general requirements specified by the EN 13201 standard are commonly supplemented with those forced by specific local regulations. One notable example is the approach to illuminating pedestrian crossings. Local regulations in this regard have been defined, among otheres, by Belgium [2, 21], Czech Republic [14], Germany [4], Italy [5], Norway [10], Poland [20], Sweden [12, 13], Switzerland [15] and the U.K. [3].

Such fine-grained regulations increase the complexity of the design process for street lighting, for instance by defining the need to assign different lighting levels for crossings themselves, as well as transition zones located in front of and behind them, in order to avoid sudden changes in lighting for drivers.

The optimisation of photometric calculations is a very intensively researched field [18, 22, 23]. However, the aforementioned requirements also require the designers to do more ‘pre-processing’ work, analysing the area of the investment and defining the individual lighting segments¹ in all relevant streets.

The goal of the presented approach is to provide a formal background to automate this process. The benefits are two-fold. First, the automatic procedure will require little or no human interaction, thus reducing the designers’ workload. Second, the results will be consistent, which is important especially for large projects, which often get divided among many designers. Practical experience has shown that their interpretation may vary slightly for virtually identical road fragments.

Spatial data processing systems, such as GIS (Geographic Information System) solutions, provide tools for processing of geographic shapes. However, trying to express the complex procedures as code (either in a programming language or a data query language, such as SQL [16]) obscures the intentions, making the process error-prone and verification difficult or impossible. The task is also not trivial, given the multitude of possible spatial layouts of road segments. The goal of this paper is to define a formalism able to express the spatial analysis and transformations needed to generate precise shapes for lighting segments.

2 Problem Statement

To illustrate the mechanism used to define lighting segment transformations in a formal way, we will use the example referred to in Sect. 1, which entails generation of lighting segments for pedestrian crossings.

While the procedure may vary in different local regulations, the general concept remains unchanged. It involves:

• 1. significantly increasing the luminance level of the crossing itself,

• 2. increasing the luminance level of so-called transition zones: parts of the road located in front of (run-in) and behind the crossing (run-out).

The length of the transition zones may differ, depending on the location and road parameters. Sometimes, the run-in is omitted, only leaving the run-out to maintain a negative contrast of pedestrians crossing the road [20].

The increase itself is performed by assigning a different lighting class to these segments. The shape of the transition zones is therefore a function of the applied regulations and the structure of the road.

For this paper, we will use an example of a one-way street with three different lighting segments with distinct lighting classes (and, therefore, requirements). This simple example will allow for a clear description of the mechanism.

However, please note that in real life, the input data will rarely be as simple – in fact, it is almost always more complex. Therefore, the rules used to process it will also be more complicated.

3 Formal Model

The proposed approach tries to combine the semantic information about lighting segments and their spatial properties in a graph structure. Spatial relationships obtained using dedicated tools, such as the PostGIS spatial database [1], are transformed into semantic annotations in the graph itself.

The proposed structure must be able to store all data about the relevant area and support the required transformations. It takes the form of a graph, and since it contains a semantic description of the environment (including pre-interpreted spatial relations), it is called the Semantic Environment Graph (SEG).

The SEG is generated by a graph grammar, denoted as $\varOmega$. A detailed definition of a graph grammar is provided e.g. in [17]; therefore, here we will only focus on the actual mechanism for the application of productions.

Productions (denoted as $\pi$) are transformation rules, which transform the graph from one coherent state to another. Productions are provided in the form of two graphs, called lhs (left-hand side) and rhs (right-hand side). Application of $\pi$ on a graph G involves the following steps:

• 1. the lhs graph is removed from G, creating $G'$;

• 2. the lhs graph is added to $G'$ (however, at this moment these graphs are separated);

• 3. all edges in G containing one of the nodes belonging to $V_{lhs} \cap V_{rhs}$ and the second to $V_G \setminus V_{lhs}$ are restored in $G' \cup rhs$;

• 4. all edges in G containing removed nodes ($V_{lhs} \setminus V_{rhs}$) are also removed.

The Semantic Environment Graph was first introduced in [17]; its extended and revised definition is presented below.

Definition 1

SEG$_\varOmega$ is defined as an attributed graph over the set of node labels $\varSigma _\varOmega$ and the set of edge labels $\varGamma _\varOmega$ such that:

$$ SEG _\varOmega =(V_\varOmega , E_\varOmega , lab^{V}_\varOmega , lab^{E}_\varOmega , \varSigma _\varOmega , \varGamma _\varOmega , \varDelta _\varOmega , att^{V}_\varOmega , att^{E}_\varOmega , A^{V}_\varOmega , A^{E}_\varOmega )$$

where:

• $V_\varOmega$ is the set of nodes,

• $E_\varOmega$ is the set of edges,

• $lab^V_\varOmega : V_\varOmega \rightarrow \varSigma _\varOmega$ is the node labelling function,

• $lab^E_\varOmega : E_\varOmega \rightarrow \varGamma _\varOmega$ is the edge labelling function,

• $\varSigma _\varOmega =\{T,S,F,P,O\}$ is the set of node label groups, where:

  • T represents streets,

  • S represents road lighting segments located on streets,

  • F represents freeform lighting segments, which are not located on streets (e.g. to represent a parking lot),

  • P represents pedestrian crossings, located on road segments,

  • O represents other objects, such as buildings, points of interest, etc.

• $\varGamma _\varOmega =\{on,part\_of,spatial\_rel,eq\}$ is the set of edge labels, where:

  • on denotes that a point object (e.g. pedestrian crossing) is located at a given line object (e.g. road segment),

  • $part\_of$ denotes that a line object is part of another line object,

  • $spatial\_rel$ denotes that there is a spatial relationship between two objects,

  • eq denotes that an object is equivalent to another object.

• $\varDelta _\varOmega =\{\alpha ,\beta \}$ is the set of nonterminal nodes,

• $att^V_\varOmega : V_\varOmega \times \varSigma _\varOmega \rightarrow 2^{A^V_\varOmega }$ is the node attributing function, such that for $x \in V_\varOmega ,l \in \varSigma _\varOmega , a\in A^{V}_\varOmega$ $att^{V}_\varOmega (x,l)(a)$ is a value of the attribute a,

• $att^E_\varOmega : E_\varOmega \times \varGamma _\varOmega \rightarrow 2^{A^{E}_\varOmega }$ is the edge attributing function, such that for $x \in E_\varOmega , l \in \varGamma _\varOmega , a\in A^{E}_\varOmega$ $att^{E}_\varOmega (x,l)(a)$ is a value of the attribute a,

• $A^{V}_\varOmega$ is the set of node attributes, where:

  • type denotes the type of an object (e.g., the type of building for O nodes),

  • geometry denotes the shape of an object and its geographic location; this can be expressed e.g. as a Well-Known Text (WKT) string,

  • name is the name of an object, e.g. the street name or segment label,

  • $lighting\_class$ is the lighting class assigned to a road or freeform segment,

• $A^{E}_\varOmega$ is the set of edge attributes, where:

  • position denotes the metre within a line object on which a given point is located,

  • from and to mark the metres within a line object where another line object begins and ends,

  • distance denotes the distance (in metres) between two objects,

  • intersects (yes, no) indicates that two objects spatially intersect.

4 The Segment Generation Procedure

As mentioned in Sect. 2, we will present the mechanism using the example of a one-way street with three lighting segments and a pedestrian crossing.

Let us assume that a street $T_1$, $L_{T1}$ metres long, is divided into three lighting segments:

• $S_1$, occupying the initial $L_1$ metres of the street length, with lighting class M4,

• $S_2$, occupying the following $L_2$ metres, with lighting class M3,

• $S_3$, occupying the final $L_3$ metres, with lighting class M4.

Additionally, on $S_2$, there is a pedestrian crossing $C_1$, with its centre located at the $P_{C1}$-th metre of the segment. This initial situation has been presented in Fig. 1. For clarity of presentation, attributes denoting the lighting classes are not shown in the graph.

Fig. 1.

Initial state of segments

Let us consider the task of defining lighting segments for a street with a pedestrian crossing, along with transition zones recommended by regulations. Then, a series of graph productions is applied, bringing the graph to the desired state. Their description follows.

4.1 Initial Production

Production $P_1$. The first production consists in generating non-terminal nodes which trigger the generation of the nodes representing the actual lighting segments.

The non-terminal nodes, labelled $\alpha$ and $\beta$, are later used to trigger subsequent operations leading to generation of terminal symbols representing new segments (Fig. 2).

Fig. 2.

Production $P_1$

The state of the example graph after applying $P_1$ is presented in Fig. 3.

Fig. 3.

Example graph after applying $P_1$

4.2 Generation of the Run-In

This production is triggered by the non-terminal symbol $\beta$, generated by $P_1$. It generates the transition zone in front of the pedestrian crossing. The size of the run-in segment is designated by the function $RIL(\ldots )$ (run-in length). The parameters for this function are the lighting class associated with the S and $\alpha$ nodes, because the run-in segment’s size should be longer with greater differences of illumination levels, due to eye accommodation.

Depending on the geometry of the segments, it can take one of three variants:

• 1. if the entire transition zone fits in the segment which contains the crossing and a part of the segment is left (i.e. it is shorter than part of the segment which lies before the crossing), production $P_{2a}$ is used;

• 2. if the transition zone does not fit in the segment with the crossing, but the segment is preceded by other segments in the same street, it will cover it and needs to be further propagated to preceding segments – production $P_{2b}$ is used;

• 3. if the transition zone does not fit in the segment with the crossing, the preceding segment must be shortened – production $P_{2c}$ is used;

We assume priority of application of the mentioned productions, i.e. we will apply production $P_{2a}$ before $P_{2b}$ and $P_{2c}$, and $P_{2b}$ before $P_{2c}$. A detailed description of the productions follows.

Production $P_{2a}$. In this case (described by item 1 above), the non-terminal symbol $\beta$ is replaced with two segments:

• $S_1$, which represents the run-in segment in front of the crossing,

• $S_2$, which represents the remaining part of the segment which originally contained the crossing (Fig. 4).

Fig. 4.

Production $P_{2a}$

The applicability predicate is defined as:

$$\begin{aligned} \varPi _{2a} : \mid S_1.to - \alpha _2.from \mid > RIL(...) \end{aligned}$$

The attributes of the right hand side of the production are defined as follows:

$$\begin{aligned} S_5.from&= S_1.to\\ S_4.from&=S_5.to=\alpha _2.from+RIL(\ldots )\\ S_4.to&=\alpha _2.from \end{aligned}$$

Production $P_{2b}$. This production is similar to $P_{2a}$, but differs in that no part of the original segment is left before it (see item 2 above), hence only one new segment $S_1$ is created, representing the run-in segment. The applicability predicate is defined as (Fig. 5):

Fig. 5.

Production $P_{2b}$

$$\begin{aligned} \varPi _{2b} : \mid S_1.to - \alpha _2.from \mid =< RIL(...) < \mid S_1.from - \alpha _2.from \mid \end{aligned}$$

The attributes of the right hand side of the production are defined as follows:

$$\begin{aligned} S_1.to&=S_4.from=\alpha _2.from+RIL(\ldots )\\ S_4.to&=\alpha _2.from \end{aligned}$$

Production $P_{2c}$. In this case (item 3), the run-in covers its part of the original segment and must be further propagated to the preceding segment.

The preceding segment (S) is ‘consumed’ by $\alpha$, and the non-terminal symbol $\beta$ remains in the graph to force its further processing by one of the other productions. The attributes of $\beta$ representing the current length of the run-in and the remaining length to be assigned must be updated accordingly. The predicate of applicability is as follows:

$$\begin{aligned} RIL(...) >= \mid S_1.from - \alpha _2.from \mid \end{aligned}$$

The attributes of the right hand side of the production are defined as follows:

$$\begin{aligned} S_2.to=S_1.to \end{aligned}$$

4.3 Generation of the Run-Out

The procedure for run-out generation is analogous to that described in Sect. 4.2, but takes the segment located behind the crossing into consideration (Fig. 6).

Fig. 6.

Production $P_{2c}$

5 Results and Practical Implications

The presented approach provides means for flexible, formal definition of spatial data transformation rules using a graph formalism. Obviously, the performance of the transformations depends on the implementation, which is not relevant since the paper focuses on the formal aspects of the method.

The lhs and rhs graphs in production definitions can be arbitrarily complex. This means that the expressive power of the proposed formalism is limited only by the assumed graph model (SEG), which can be freely extended. Therefore, the main contribution of this approach lies in the ability to define virtually any procedure to modify the map data and apply it accordingly, in a consistent manner.

However, it is important to stress the practical implications of using the describe method for execution of lighting modernisation projects. To demonstrate the outcome, let us refer to a lighting modernisation project carried out by AGH University of Science and Technology in cooperation with the City of Kraków. The project involved replacing almost 4,000 old fixtures with LED-based ones, along with introduction of an innovative, real-time control system. Simulations using a prototype system showed that a simpler version of the proposed method yields over 20 times more lighting segments that the traditional approach executed by a professional lighting designer [17]. The obtained results are presented in Fig. 7.

Fig. 7.

Number for segments defined in the area of the pilot project [17]

Finally, to provide a view on real-life applicability of the proposed approach, a few remarks will be provided. It must be stressed that the transformation rules need to be defined manually at the moment. This means that processing of other objects, such as intersections, will require precise definition of appropriate productions, and may also require extension of the SEG with regard to labels and attributes. However, the contents of the graph can be automatically generated from map data, e.g. using OpenStreetMap² data. If the transformation rules are detailed enough, further processing of the graphs is completely automatic.

6 Conclusions and Future Work

The paper extends the formal methods first proposed in [17] by providing a detailed study of a spatial transformation procedure applied in real-world lighting modernisation projects.

It provides a formal definition of all steps necessary to describe a transformation procedure, using an example of a one-way street with one pedestrian crossing for clarity. The implementation is not the main focus of the paper, but practical implications of the proposed method have been outlined.

The method has been verified using a software prototype built for this purpose. Future work involves migrating other transformations currently used in the prototype system to the graph formalism and fully integrating the graph processing engine with the database used for the production system.