Pierre-Jean Lapray

Barthélémy Heyrman

Dominique Ginhac
email: dginhac@u-bourgogne.fr

HDR-ARtiSt: An Adaptive Real-time Smart camera for High Dynamic Range imaging

This paper describes a complete FPGA-based smart camera architecture named HDR-ARtiSt (High Dynamic Range Adaptive Real-time Smart camera) which produces a realtime High Dynamic Range (HDR) live video stream from multiple captures. A specific memory management unit has been defined to adjust the number of acquisitions to improve HDR quality. This smart camera is built around a standard B&W CMOS image sensor and a Xilinx FPGA. It embeds multiple captures, HDR processing, data display and transfer, which is an original contribution compared to the state of the art. The proposed architecture enables a real-time HDR video flow for a full sensor resolution (1.3 Mega pixels) at 60 frames per second.

Introduction

Standard cameras capture only a fraction of the information that is visible to the human eye. This is specifically true for natural scenes including areas of low and high illumination due to transitions between sunlit and shaded areas. When capturing such a scene, many cameras are unable to store the full Dynamic Range (DR) resulting in low quality video where details are concealed in shadows or washed out by sunlight. High Dynamic Range (HDR) imaging techniques appear as a solution to overcome this issue by encoding digital video with higher than standard 24-bit RGB format, and then increasing the range of luminance that can be stored. Reinhard et al [START_REF] Ward | High Dynamic Range Imaging: Acquisition, Display, and Image-based Lighting[END_REF] provide an exhaustive review, highlighting various fields of applications of HDR cameras. For example, HDR capturing techniques are essential for outdoor security applications in which unpredictable illumination changes may affect performance algorithms [5,[START_REF] Mangiat | Inexpensive high dynamic range video for large scale security and surveillance[END_REF].

Similarly, HDR techniques should facilitate object tracking or automotive applications [START_REF] Schanz | A high-dynamic-range cmos image sensor for automotive applications. Solid-State Circuits[END_REF][START_REF] Sérot | Fast prototyping of parallel-vision applications using functional skeletons[END_REF][START_REF] Lee | Global illumination invariant object detection with level set based bimodal segmentation[END_REF] under uncontrolled illumination. Recent research programs on machine vision have clearly demonstrated the benefits of real-time HDR vision [START_REF] Hrabar | High dynamic range stereo vision for outdoor mobile robotics[END_REF][START_REF] Ruedi | An SoC combining a 132dB QVGA pixel array and a 32b DSP/MCU processor for vision applications[END_REF]. Finally, medical applications require high precision images and HDR lighting techniques to improve the rendering quality of imaging systems [START_REF] Leflar | Use of high dynamic range images for improved medical simulations[END_REF][START_REF] Graf | High dynamic range cmos imager technologies for biomedical applications[END_REF].

There are two major approaches to create HDR content: to develop new HDR sensors or to combine multiple exposure frames captured by conventional Low Dynamic Range (LDR) sensors. First, several HDR sensors have been designed with techniques such as well-capacity adjusting, timeto-saturation, or self-reset (see [22] for a comparative analysis). Most of these sensors are tailor-made and provide dedicated processing units to extend DR [START_REF] Acosta-Serafini | A 1/3" VGA linear wide dynamic range CMOS image sensor implementing a predictive multiple sampling algorithm with overlapping integration intervals[END_REF][START_REF] Sakakibara | A highsensitivity CMOS image sensor with gain-adaptative column amplifiers[END_REF][START_REF] Cembrano | A 1000 fps at 128 × 128 vision processor with 8-bit digitized I/O[END_REF][START_REF] Lindgren | A multiresolution 100-GOPS 4-Gpixels/s programmable smart vision sensor for multisense imaging[END_REF][START_REF] Morfu | Nonlinear systems for image processing[END_REF][START_REF] Dubois | A 10 000 fps CMOS sensor with massively parallel image processing[END_REF].

The second method relies on conventional off-the-shelf LDR sensors to capture the HDR data by recording multiple acquisitions of the same scene while varying the exposure time [START_REF] Debevec | Recovering high dynamic range radiance maps from photographs[END_REF][START_REF] Mitsunaga | Radiometric self calibration[END_REF][START_REF] Robertson | Estimation-theoretic approach to dynamic range enhancement using multiple exposures[END_REF][START_REF] Kang | High dynamic range video[END_REF]. By limiting the exposure time, the image loses low-light detail in exchange for improved detail in bright areas. By increasing the exposure time, the image is only detailed in the dark areas because of the pixel saturation in bright areas. Each pixel is at least properly exposed in one image and is under or overexposed in other images of the sequence. The images are then combined into a single HDR frame (i.e. a radiance map). Finally, since current display technology has a limited DR, HDR images need to be compressed by tone mapping operators [START_REF] Devlin | Tone reproduction and physically based spectral rendering[END_REF][START_REF] Reinhard | Dynamic range reduction inspired by photoreceptor physiology[END_REF][START_REF] Čadík | Evaluation of HDR tone mapping methods using essential perceptual attributes[END_REF][START_REF] Akil | Real-time dynamic tone-mapping operator on gpu[END_REF][START_REF] Akyuz | High dynamic range imaging pipeline on the gpu[END_REF][START_REF] Liu | A study of hardwarefriendly methods for gradient domain tone mapping of high dynamic range images[END_REF] in such a way that the visual sensation of the real scene is faithfully reproduced, as depicted in Fig. 1.

This paper presents a complete FPGA-based smart camera architecture named HDR-ARtiSt (High Dynamic Range Adaptive Real-time Smart camera). This smart camera is able to provide a real-time HDR live video from multiple exposure capturing to display, through radiance maps and tone mapping. The main contribution of this work is the generation of a new FPGA embedded architecture producing an uncompressed B&W 1280 × 1024-pixel HDR live video at 60 fps. An embedded DVI controller is also provided to display this HDR live video on a standard LCD monitor. The HDR-ARtiSt camera could obviously embed some complex im- age processing applications onto the FPGA or could be connected to a more standard PC managing the video stream.

The remainder of the paper is as follows: in Section 2, we briefly review the literature on existing HDR systems. Section 3 describes our proposed hardware architecture, highlighting the multi-streaming memory management unit designed to address the computation capacity and memory bandwidth limitations. A first implementation using a two-frame acquisition is presented in Section 4. Based on a detailed study of the visual quality of this implementation, an improved three-frame solution is described in Section 5. Finally, Section 6 concludes this paper and outlines directions for future work.

Related work

The problems of capturing the complete dynamic range of a real scene and reducing this dynamic range to a viewable range have drawn the attention of many authors. However, the main part of the proposed algorithms have been developed without taking into account the specifications and the difficulties inherent to hardware implementations. Unfortunately, these works are not generally suitable for efficient real-time implementation on smart cameras. As a consequence, generating real-time HDR live video remains an interesting challenge.

Existing hardware architectures

In 2007, Hassan and Carletta [START_REF] Hassan | A real-time FPGAbased architecture for a Reinhard-like tone mapping operator[END_REF] described an FPGA-based architecture for local tone mapping of gray scale HDR images, able to generate 1, 024 × 768-pixel image at 60 frames per second. The architecture is based on a modification of the nine-scale [START_REF] Reinhard | Photographic tone reproduction for digital images[END_REF] operator. Several limitations can be noticed. Firstly, this work focuses only on the tone-mapping process and does not care about the HDR capture, using a set of high dynamic range still images from the Debevec library [START_REF] Debevec | Recovering high dynamic range radiance maps from photographs[END_REF]. Secondly, the tone mapping operator requires to store a full image before evaluating the logarithmic average of the image, leading to a video latency. This limitation can be overcome by using the logarithmic average of the previous image to normalize the current image. Finally, using the Gaussian pyramid requires a lot of bits per pixel, increasing the amount of onboard memory. Another real-time hardware implementation of tone mapping has been recently proposed by Vytla et al [START_REF] Vytla | A real-time implementation of gradient domain high dynamic range compression using a local poisson solver[END_REF]. They use the Fattal et al [START_REF] Fattal | Gradient domain high dynamic range compression[END_REF] local algorithm. This operator is less complex than the Reinhard's operator, then requiring less onboard memory. The key point of this work is the inexpensive hardware implementation of a simplified Poisson solver for Fattal's operator. It gives a realtime tone mapping implementation on a Stratix II FPGA operating at 100 frames per second with one megapixel image resolution.

Chiu et al [START_REF] Chiu | Real-time tonemapping processor with integrated photographic and gradient compression using 0.13µm technology on an ARM SoC platform[END_REF] describe a methodology for the development of a tone-mapping processor of optimized architecture using an ARM SOC platform, and illustrate the use of this novel HDR tone-mapping processor for both photographic and gradient compression. Based on this methodology, they develop an integrated photographic and gradient tone-mapping processor that can be configured for different applications. This newly-developed processor can process 1, 024 × 768-pixel images at 60 fps, runs at 100 MHz clock and consumes a core area of 8.1 mm 2 under a TSMC 0.13µm technology.

Kang et al [START_REF] Kang | High dynamic range video[END_REF] describe an algorithmic solution computing both video capture and HDR synthesis, and able to generate HDR video from an image sequence of a dynamic scene captured while varying the exposure at each frame (alternating light and dark exposures). For this purpose, the approach consists of three main parts: automatic exposure control during capture, HDR stitching across neighbouring frames, and tone mapping for viewing. The implemented technique produces video with increased dynamic range while handling moving parts in the scene. However, the implementation on a 2 GHz Pentium 4 machine does not reach the real-time constraint because the processing time for each 1, 024 × 768-pixel video frame is about 10 seconds (8 seconds for the radiance mapping and 2 seconds for the tone mapping). Based on Kang's algorithms, Youm et al [START_REF] Youm | High dynamic range video through fusion of exposured-controlled frames[END_REF] create an HDR video by merging two images from different exposures acquired by a stationary video camera system. Their methodology mainly relies on the simple tactic of automatically controlling exposure times and effectively combines bright and dark areas in short and long exposure frames.

Unfortunately, they do not reach real-time processing with about 2.5 seconds for each 640 × 480-pixel frame on a 1.53 GHz AMD Athlon machine.

Finally, Ke et al [START_REF] Ke | Hardware-efficient virtual high dynamic range image reproduction[END_REF] propose an innovative method to generate HDR video. This method differs drastically with the above-mentioned state-of-the-art works because only one LDR image is enough to generate HDR-like images, with fine details and uniformly-distributed intensity. To obtain such a result, they implement a hardware-efficient virtual HDR image synthesizer that includes virtual photography and local contrast enhancement. Under a UMC 90-nm CMOS technology, it achieves real-time for 720×480-pixel video frames at 60 fps.

Efficient algorithms for HDR video

Generating an HDR live video stream as well as HDR still images consists of automatically determining the optimal exposures for multiple frames capture, computing radiance maps, and local/global tone mapping for viewing on a standard LCD monitor.

Table 1 is the list of common terms and variables used in the equations of the following sections. Three popular algorithms for recovering this camera transfer function can be extracted from literature: Debevec and Malik [START_REF] Debevec | Recovering high dynamic range radiance maps from photographs[END_REF], Mitsunaga and Nayar [START_REF] Mitsunaga | Radiometric self calibration[END_REF], and Robertson et al [START_REF] Robertson | Estimation-theoretic approach to dynamic range enhancement using multiple exposures[END_REF]. According to the detailed description of these methodologies and the comparison of their real-time software implementations, we decided to use the Debevec's method. The main advantage of this approach is that there is very little constraint about the response function (other than its invertability). Moreover, the proposed algorithm has proved to be quite robust and easy to use, due to the simplicity of equations [START_REF] Granados | Optimal HDR reconstruction with linear digital cameras[END_REF][START_REF] Yourganov | Acquiring high dynamic range video at video rates[END_REF]. The CTF function is evaluated from the film reciprocity equation f :

Z p i j = f (E i j ∆t p ) (1)
The CTF function g is defined as g = ln f -1 and can be obtained by minimizing the following function:

O = M ∑ i=1 N ∑ j=1 P ∑ p=1 [g(Z p i j ) -ln E i j -ln ∆t p ] 2 + λ Z max -1 ∑ z=Z min +1 g (z) 2 (2)
Where λ is a weighting scalar depending on the amount of noise expected on g, Z min and Z max are respectively the lowest and the greatest pixel values. The evaluation of g only requires the evaluation of a finite number of values between Z min and Z max (typically 1,024 values for a 10-bit precision sensor). These values can be preliminary evaluated from a sequence of several images, then stored in the camera, and reused further to convert pixel values. For recovering the HDR radiance value of a particular pixel, all the available exposures of this pixel are combined using the following equation [START_REF] Schubert | A handson approach to high-dynamic-range and superresolution fusion[END_REF]:

ln E i j = ∑ P p=1 ω(Z p i j )[g(Z p i j ) -ln ∆t p ] ∑ P p=1 ω(Z p i j ) (3)
Where ω(z) is a weighting function giving higher weight to values closer to the middle of the function:

ω(z) = z -Z min for z ≤ 1 2 (Z min + Z max ) Z max -z for z > 1 2 (Z min + Z max ) (4)
Originally, the Debevec's method has been developed for photography but according to G. Yourganov [START_REF] Yourganov | Acquiring high dynamic range video at video rates[END_REF], this method can be easily applied to digital video, both for static and dynamic scenes, if captures are fast enough that light changes can be safely ignored. Consequently, such a method is widely used to produce HDR video, by capturing frames with alternating bright and dark exposures, as pointed by Tocci et al [START_REF] Tocci | A versatile hdr video production system[END_REF].

Step 2: Tone mapping

The HDR pixels are represented by a high bit-depth conflicting with the standard display devices, requiring a high to low bit-depth tone mapping. Čadík et al [START_REF] Čadík | Evaluation of HDR tone mapping methods using essential perceptual attributes[END_REF] show that the global part of a tone mapping operator is essential to obtain goods results. A psychophysical experiment by Yoshida et al [START_REF] Yoshida | Perceptual evaluation of tone mapping operators with real-world scenes[END_REF], based on a direct comparison among the appearances of real-world HDR images shows that global methods like F. Drago and Chiba [START_REF] Drago | Adaptive logarithmic mapping for displaying high contrast scenes[END_REF] or Reinhard et al [START_REF] Reinhard | Photographic tone reproduction for digital images[END_REF] are perceived as the most natural ones. Moreover, a global tone mapper is the easiest way to reach real-time constraints because local operators require more complex computations. The choice of a candidate tone mapping operator has been done after comparing and intensively testing several C++ global algorithms applied to a radiance map constructed from two or three images. Results are provided in Table 2. According to our temporal and hardware constraints, the best compromise is the global tone mapper from Duan et al [START_REF] Duan | Tonemapping high dynamic range images by novel histogram adjustment[END_REF]. As an illustration, the HDR image depicted on the Fig. 1 has been obtained with this algorithm. This tone mapper compresses the luminance of the HDR pixel E i j to a displayable luminance D i j with the equation:

D i j = C * (D max -D min ) + D min with C = ln(E i j + τ) -ln(E i j(min) + τ) ln(E i j(max) + τ) -ln(E i j(min) + τ) (5)
where E i j(min) and E i j(max) are the minimum and maximum luminance of the scene and τ is inversely linked to the brightness of the mapped image. Increasing τ makes darker images while lower values give brighter images.

Architecture of the HDR-ARtiSt platform

To compute real-time HDR algorithms, a dedicated FPGAbased smart camera architecture was designed to address the computation capacity and memory bandwidth requirement (see Fig. 2 for an overview). This architecture does not put any restriction on the number of frames used for HDR creating. In the remainder of this paper, this generic architecture will be shortly called HDR-P, where P is the number of frames.

Fig. 2 Overview of the HDR-P video system architecture.

Global hardware architecture

The HDR-ARtiSt platform is a smart camera built around a Xilinx ML507 board, equipped with a Xilinx Virtex-5 XC5-VFX70T FPGA (see Fig. 3). The motherboard includes a 256 MB DDR2 SDRAM memory used to buffer the multiple frames captured by the sensor. Several industry-standard peripheral interfaces are also provided to connect the system to the external world. Among these interfaces, our vision system implements a DVI controller to display the HDR video on a LCD monitor. It also implements an Ethernet controller to store frames on a host computer. A custom-made PCB extension board has been designed and plugged into the FPGA board to support the Ev76c560 image sensor, a 1, 280×1, 024-pixel CMOS sensor from e2v [START_REF]Ev76c560 BW and colour CMOS sensor[END_REF]. It offers a 10-bit digital readout speed at 60 fps in full resolution. It also embeds some basic image processing functions such as image histograms, evaluation of the number of low and high saturated pixels. Each frame can be delivered with results of these functions encoded in the video data stream header.

Multi-streaming Memory Management Unit

Standard HDR techniques require two sequential steps: 1) P single frames must be captured and stored into memory, and 2) the HDR frame can be computed. The main drawback is the limited output framerate. As illustrated on Fig. 4, with P = 3 single frames (low, middle and high exposures) captured at 60 fps, the resulting HDR video is dramatically limited to 20 fps: the first HDR frame H 1 is computed from the frames I 1 , I 2 , and I 3 , the second HDR frame H 2 from I 4 , I 5 , and I 6 . To overcome this limitation, we propose a specific Memory Management Unit (MMU) able to continuously build a new HDR frame at the sensor framerate from the P previous frames. As seen on Fig. 4, the HDR frame H 2 is built from the frames I 2 , I 3 , and I 4 ; the HDR frame H 3 from I 3 , I 4 , and I 5 , etc. This multi-streaming MMU (called MMU-P, with P the number of frames) continuously manages the storage of P -1 frames, the oldest frame being systematically replaced with the new acquired frame. Simultaneously, the MMU-P manages the reading of these P -1 frames with the sensor output in order to feed the HDR creating process. For this purpose, a time sharing strategy is used to store and read back the different video streams into the DDR2 memory. Small size buffers implemented in FPGA embedded Block RAMs (BRAMs) are required to store temporary data and to handle the sharing of SDRAM data bus. To meet the challenge of real-time constraints and to minimize the buffer sizes, the MMU-P performs row-by-row read/write operations to transfer the different streams.

Before any HDR computation, the memory unit needs to be set up (see Fig. 5). Indeed, when the vision system has just been turned on, an initialization step captures and stores row-by-row P -1 frames into the SDRAM (W L m I p with 0 < m ≤ M and 0 < p < P). After receiving the last row L M of the frame I P-1 , the first rows L 1 of each previously stored frame (RL 1 I p with 0 < p < P) are read between frames and buffered into BRAMs to be quickly available for the HDR creating process. The second step is managed by the MMU-P core and starts at the beginning of the pth capture. During each row interval, the current row L m is written to the SDRAM memory while rows L m+1 of the P -1 previous frames are read and buffered into BRAMs as depicted in Fig. 6. With such a technique, when the sensor delivers a new row, the HDR creating process has a simultaneous and easy access to the current row and the corresponding rows of the previous frames. Then, the first HDR frame is obtained at the end of the capture of the frame I p at t = t HDR 1 (see Fig. 6). This process is then reiterated with the frame I p+1 and the computation of the second HDR frame from I 2 , I 3 , ..., I p+1 at t = t HDR 2 , etc.

To summarize, the MMU-P is able to capture and store the current stream of pixels from the sensor, and delivers simultaneous P -1 pixel streams previously stored to the HDR creating process. With such a memory management, we avoid waiting for the capturing of new P frames before computing any new HDR data. Once the initialization is done, our system is synchronized with the sensor framerate (i.e. 60 fps) and is able to produce a new HDR frame for each new capture. Moreover, in terms of memory, the MMU-P requires to store only P -1 frames, because the oldest captured frame is read and overwritten by the current frame acquired by the sensor. For reasons of efficiency, the MMU-P reads and stores lines of pixels. The computation of an HDR line requires P memory accesses: one write operation for the current line captured by the sensor and P -1 read operations for the P -1 lines previously stored in memory during the row interval. On the opposite, the traditional technique requires to store P frames in memory. It requires at least P + 1 memory accesses (one write and P read operations). Finally, to generate an HDR image, the MMU-P saves M writing memory access operations (with M, the line number of each frame).

Implementation of the HDR-2 video system

The HDR-P has been first prototyped on the HDR-ARtiST platform with the limitation P = 2, using only 2 frames to generate each HDR frame.

Multiple Exposure Control

The auto exposure bracketing system implemented in digital cameras is a very useful technique to automatically capture multiple exposures at fixed multiples around an optimum exposure. Our Multiple Exposure Control (MEC) for low and high exposure images is slightly different because our objective is rather to evaluate each individual exposure to get the maximum of well-exposed pixels. Our work is relatively close to the Kang's exposure control [START_REF] Kang | High dynamic range video[END_REF] and the Alston's double-exposure system [START_REF] Alston | Exposure control system for an electronic imaging camera having increased dynamic range[END_REF]. In our case, the exposure settings alternate between two different values that are continuously adapted to reflect the scene changes. Following Gelfand et al [START_REF] Gelfand | Multiexposure imaging on mobile devices[END_REF], we require that fewer than 10% of the pixels are saturated at high-level for the short exposure frame. If too many pixels are bright, the exposure time is decreased for the subsequent short exposure captures. Similarly, we require that fewer than 10% pixels are saturated at low-level for the long exposure. If too many pixels are dark, the exposure time is increased. Gelfand et al. stop this iterative process when the two exposures are stable, and use these values for the capture of the full resolution photography. Such an approach is optimal to capture a single HDR image but can not be considered for an HDR video.

In our approach, we decide to continuously update the set of exposure times from frame to frame in order to minimize the number of saturated pixels by instantaneously handling any change of the light conditions. The estimation of the best exposure times is computed from the 64-level histogram (q) provided automatically by the sensor in the datastream header of each frame. For each low exposure frame (I L ) and each high exposure (I H ), we evaluate Q L and Q H that are respectively the ratio of pixels in the four lower levels and the four higher levels of the histogram:

Q L = ∑ h=4 h=1 q(h) N Q H = ∑ h=64 h=60 q(h) N (6)
where q(h) is the amount of pixels in each histogram category h and N the total number of pixels. A series of decisions can be performed in order to evaluate the low exposure time (∆t L,t+1 ) and the high exposure time (∆t H,t+1 ) at the next iteration (t + 1) of the acquisition process.

∆t L,t+1 =          ∆t L,t + 10x if Q L > Q L,req + thr Lp ∆t L,t -10x if Q L < Q L,req -thr Lp ∆t L,t + 1x if Q L > Q L,req + thr Lm ∆t L,t -1x if Q L < Q L,req -thr Lm (7) ∆t H,t+1 =          ∆t H,t -10x if Q H > Q H,req + thr H p ∆t H,t + 10x if Q H < Q H,req -thr H p ∆t H,t -1x if Q H > Q H,req + thr Hm ∆t H,t + 1x if Q H < Q H,req -thr Hm (8)
Where x is the integration time of one sensor row. Q L,req and Q H,req are respectively the required number of pixels for the low levels and the high levels of the histogram. In order to converge to the best exposure times as fast as possible, we decide to use two different thresholds for each exposure time: thr Lm and thr Lp are thresholds for the low exposure time whereas thr Hm and thr H p are for the high exposure time. In our design, values of Q L,req and Q H,req are fixed to 10% pixels of the sensor. Values of thr Lm and thr Hm are fixed to 1% whereas thr Lp and thr H p are fixed to 8%.

Memory interface implementation

The HDR-ARtiST platform embeds a 256 MB memory with a 128-bit wide interface. Memory access operations are managed by a custom SDRAM controller specifically generated by the Xilinx Memory Interface Generator. The operation frequency of the SDRAM has been fixed to 125MHz. The e2v sensor captures 60 fps with an inter-frame time of 236µs and a row time of 14.1µs (10µs for the 1,280 pixels and an inter-row time of 4.1µs). BRAMs are used on input and output of the SDRAM, and act as data row buffers to support DDR read and write burst operations. A set of P different BRAMs is required: one BRAM used to feed the SDRAM with the incoming sensor data and a set of P -1 BRAMs supplied with the parallel streams of the previously captured frames. These block memories manage independent clocks and support non-symmetric aspect ratios for IO operations. Each BRAM is 2048 deep and 10-bit wide, in order to manage a full 1,280-pixel row. A full row of 1,280 pixels captured by the sensor is written into the memory in 1,280×10 128×125•10 6 = 0.8µs. Similarly, the time needed for reading a 1,280-pixel row from the SDRAM is identical. These two operations are low time-consuming and take place during the inter-row interval.

Algorithm simplifications for an efficient hardware implementation

In order to meet both the temporal constraints and platform requirements, some simplifications of the algorithms described in Section 2.2 are proposed.

HDR creating module

The evaluation of the CTF function g has not been implemented on the platform because it needs to be computed only once. So, the parameters of the CTF are preliminary evaluated by a dedicated PC software from a sequence of images, and then stored into a Look-Up Table (LUT, 1024word memory) on the FPGA. Moreover, in order to reduce the computation complexity and to optimize the hardware resources, some other mathematical operations, such as neperian logarithms, are also pre-calculated and registered in LUTs. Finally, the hardware cost of the implementation of the HDR creating described in Eq. 3 only depends of the number of bracketed frames used to create one HDR video frame. (see Fig. 8 for HDR-2). Each frame requires two 32-bit arithmetic operators (1 subtractor, 1 multiplier) and one transition from 10-bit to IEEE754 32-bit wide (Fixed-to-Float). Other hardware resources (a 10-bit adder, a 32-bit adder, a 32-bit divider and a Fixed-to-Float operator) are also required, independently of the number of frames. A pipeline structure is implemented to speed-up the processing.

Table 3 compares the hardware resources required for the arithmetic operators used in the HDR pipeline. It reveals that a 32-bit floating-point format requires significantly less resource, specifically for complex operations such as division, square root and even multiplication. Only addition and subtraction are better in fixed-point format. Since division and multiplication are common operations in our design, we decided to use floating-point format. Table 3 Comparison of resource estimations for arithmetic operators (Xilinx IPs) in fixed-point and floating-point format.

Tone mapping module

The hardware implementation of the Eq. 5 requires the preliminary estimation of the terms E i j(min) and E i j(max) relative to the HDR frame before any tone mapping operation. However, as our hardware pipeline computes HDR imaging and tone mapping on the incoming pixels stream, such an approach is inconceivable. We make the assumption that the light conditions do not vary significantly between two consecutive frames captured at 60 fps. So, these two terms are computed from the current HDR frame (CMP Min and CMP Max operators), stored in registers (Reg) and then used as the Min/Max values for the tone mapping of the next HDR frame, as seen in Fig. 9. τ controls the overall brightness of the mapped frame. According to Duan et al [START_REF] Duan | Tonemapping high dynamic range images by novel histogram adjustment[END_REF], a larger τ makes the mapped frame darker and smaller τ makes the mapped frame brighter. Several values have been tested in simulation and we decide to set τ = 0 because it simplifies the hardware implementation. We also set D max = 255 and D min = 0 since standard monitors use a 8-bit format for each channel. The multiplication by 255 is easily done by adding 8 to the exponent in floating point. This may change in the future due to successful efforts in building higher resolution displays. Our design will be able to follow this evolution because tone mapped frames with higher resolutions could be easily produced by increasing D max and changing the final Float-to-Fixed operator.

Results

Simulation and validation phases of the HDR-2 architecture have been made using Modelsim. Then, it has been implemented on the HDR-ARtiST platform. Table 4 is a summary of the whole design and Table 5 describes details of the synthesis report. Usually, FPGA-based image processing requires many specific devices such as SRAM memory, multi-port memory, video direct memory access, dedicated processors, and consequently, consumes many DSP blocks.

There is no DSP blocks in our implementation because some functions are performed with LUTs and others are floating point operators. It can been seen in Table 5 that the implementation results in a relatively low hardware complexity since the number of slice LUTs is 12,859 (about 29% of the device) and the number of slice flip-flops is 13,612 (i.e. 30% of the device) for the HDR-2 configuration. A significant part of the complexity is due to the MMU-P managing the fine synchronization of the pixel streams between external SDRAM memory and internal BRAMs (about 5% of the LUTs and 6% of the flip flops). Only 15.5% of FIFO / BRAMs are used: BRAMs are mainly used to store the P lines of pixels required by the HDR creating process while FIFO are dedicated to the data synchronization be-tween the different steps of the HDR pipeline. The HDR creating and the tone mapping processes consume respectively 9.4% and 7.7% of the LUTs and 11.4% and 9% of the flip flops due to the implementation of IEEE754 32-bit floating-point arithmetic operators (specifically dividers and multipliers). The entire HDR pipeline process has a global latency of 136 clock rising-edges (i.e. 1.2µs for a 114MHz system clock). Such a low latency is not perceived by human eye and then, the pipeline process is able to deliver a full HDR video stream at a framerate of 60 fps. The post processing step is also a significant consuming task (7% of the LUTs and 4% of the flips flops). This task embeds a dedicated DVI controller designed to display camera data on a LCD monitor. Both live video streams, LDR unprocessed pixel streams and computed HDR video can be displayed without latency noticeable for the viewer. For this purpose, the horizontal and vertical synchronization signals (H sync and V sync in Fig. 5) are regenerated from the output tone mapped data and used to synchronize pixels by the DVI encoder. Even if this DVI controller consumes significant resources, it can not be considered as a real built-in part of the application. It is only used to stream output data into a LCD monitor where the frames from different stages of the logic (typically, LDR frames after pre-processing and HDR fames after post-processing) can be visually inspected. Thus, ignoring the DVI controller resources, our implementation of the HDR application on the HDR-ARtiSt platform results in a relatively low hardware complexity. This opens the interesting possibility to implement other image processing applications on the FPGA. One of the best candidate applications should be motion analysis and artifacts correction in order to provide a higher quality HDR live video platform.

5 The HDR-3 video system

HDR-2 limitations

The HDR-2 system has been evaluated both on images from the Debevec's database (Fig. 10), and on real-scene frames captured by the HDR-ARtiSt platform (Fig. 11). Firstly, the classical database set to test HDR techniques is the Stanford Memorial Church sequence provided by Debevec. It includes a series of images captured with exposure times ranging from 1/1,024 to 32s. Sets of two images have been selected to evaluate our hardware implementation. Fig. 10 depicts an example of an HDR image built by the HDR-2 architecture from a low exposure (∆t p = 0.5s) and a high exposure (∆t p = 16s). It should be noted that the exposures are relatively high, due to low-level light conditions inside the church. The tone mapped image reproduces both details in dark and bright areas without noticeable visual artifact.

Secondly, the HDR-2 implementation has been also evaluated with real-world scenes captured by the HDR-ARtiSt platform. The experimental scene is a poorly illuminated desk on which we can find a cup of coffee and some toys (a toy car, a Toy Story figurine, a R2-D2 robot inside the cup of coffee). A bright lamp has been placed behind this scene to significantly enhance the dynamic range (see Fig. 11 and Fig. 12). Obviously, the main difficulty for any HDR technique is to simultaneously render the bright area near the light bulb and the dark area inside the cup of coffee, while preserving accuracy on intermediate levels. Note that the exposures are here very low (respectively 0.15 ms and 1.9 ms for the low and high exposures) because of the blinding source of light. A first visual analysis shows that the results are similar to those obtained previously with the memorial church giving a high-quality reproduction of fine details in dark and bright areas. As examples, the R2D2 figure can be detected even the area inside the cup is particularly dark. On the other side, the word "HDR" written in the lampshade can be read 1 . However, a deeper analysis reveals a lack of details on the medium lightened areas, highlighting some limitations of the HDR-2 implementation. Four different areas have been selected to highlight possible artifacts. These areas are zoomed in and displayed in the bottom part of Fig. 11, revealing some discontinuities along edges in the cup of coffee (area 1), in the hood of the car (area 2), in the shade of the car (area 3), and in the lampshade (area 4). These observable phenomena are mainly due to the wide dynamic range of the scene exceeding 100, 000:1. In such extreme lighting conditions, it seems almost impossible to capture simultaneously information on the light bulb that illuminates the scene, information on the dark part of the scene, and all the intermediate levels with only two frames. Practically, for capturing details in the upper part of the radiance histogram (lamp), the exposure time of the first frame needs to be decreased severely. On the other side, for very dark areas, the exposure time of the second frame is increased drastically. So, with only two captures, it is not possible to capture the whole scene in details. Since the two captures focus on the extreme parts of the illuminance, this implies inevitably a lack of information in the middle area of the histogram, leading to the above-mentioned artifacts.

HDR-3 implementation

To overcome this limitation, the most natural solution is to increase the number of frames. With a complementary middle exposure, the HDR-3 is able to capture the missing data in the median area of the illuminance. However, we limit ourselves to a 3-frame acquisition process because too many artifacts appear when four or more exposures are used in the case of real scenes with highly moving objects. The HDR-3 appears as the optimal solution able to satisfy the trade-off between high dynamic range with a capture of about 120 dB dynamic range, low artifacts and high quality.

The middle exposure time ∆t M is computed from the equation of the exposure value EV M :

EV M = log 2 f-number 2 ∆t M with EV M = EV L + EV H 2 (9)
where f-number is the aperture. Considering f-number = 1, ∆t M can be computed using the following equation:

∆t M = 1 2 EV M = 1 2 EV L +EV H 2 = 1 √ 2 EV L × 2 EV H = ∆t L × ∆t H . (10)
The tone mapped frame of the experimental scene using this new implementation is shown in Fig. 12. It is seen that the various artifacts present in Fig. 11 are now widely reduced in this new frame. In Table 6, a summary of the hardware complexity of the different blocks is given. The HDR-3 implementation obviously results in a slightly higher complexity than the HDR-2 implementation (+11.7%). Among the submodules listed in Table 6, the amount of the logic resources consumed by the MMU (+31.6% in terms of LUTs) and the HDR creating (+35.9% of LUTs and +11.2% if flip flops) are increased. Moreover, when the number of frames raises from 2 to 3, there is a significant rise in the usage of block RAMs (+30.4%), mainly used by the MMU. In contrast to these significant increases, the tone mapping module does not undergo any change and consumes the same resources. The other modules of the system are relatively less affected, except the number of flip flops used by the post processing submodule. Indeed, this module embeds some additional resources (registers, multiplexers for example) to manage the 3 LDR and the HDR streams and route them to the DVI output.

Extending the architecture to color data

The current B&W HDR-ARtiSt platform could be easily enhanced with a color sensor. In a traditional HDR workflow, HDR creating, tone mapping and other rendering steps are applied after demosaicing. However, as explained in Tamburrino et al [START_REF] Tamburrino | Digital camera workflow for high dynamic range images using a model of retinal processing[END_REF], the retinal processing of the human visual system (HVS) performs most of adaptation operations on the cone mosaic before demosaicing. According to this principle, Tamburrino et al. [START_REF] Tamburrino | Digital camera workflow for high dynamic range images using a model of retinal processing[END_REF] proposes a new HDR workflow in which the tone mapping are applied directly on the color filter array (CFA) image, instead of the already demosaiced image. Demosaicing is then the last step of the HDR workflow. Such an approach is then directly compatible with the HDR pipeline implemented on the HDR-ARtiSt platform. Indeed, the HDR creating and the tone mapping operation can be applied on the pixels of the mosaiced image using the three different response curves of the sensor (for the red, green and blue channels), before applying demosaicing. In terms of computation, it does not increase computational complexity because there is only one RAW data stream to process and not three RGB streams. The demosaicing step, which converts the RAW to RGB data, is handled by a specific hardware block (named "Color Filter Array Interpolation") provided by Xilinx. This block generates the missing color components associated with the commonly used Bayer pattern in digital camera systems. Additionally, a white balance algorithm IP provided by Xilinx can also be implemented in our platform in order to render colors as natural as possible. In terms of hardware resources on the HDR-ARtiSt platform, it only requires two more LUTs to store the response curves and the demosaicing/white balance operators provided by Xilinx. According to Debevec and Malik [START_REF] Debevec | Recovering high dynamic range radiance maps from photographs[END_REF], we can also, for simplicity, use an identical single curve for both R and G components because these two response curves are very consistent. Fig. 13 Comparison of the proposed system output with different real-time tone mapping methods.

Comparison with state-of-the-art existing architectures

In addition to performance results, a comparison of the HDR-3 architecture with three other systems has been conducted. Two of them are on a FPGA-based architecture [START_REF] Hassan | A real-time FPGAbased architecture for a Reinhard-like tone mapping operator[END_REF][START_REF] Vytla | A real-time implementation of gradient domain high dynamic range compression using a local poisson solver[END_REF] and the last one on a GPU platform [START_REF] Slomp | Real-time photographic local tone reproduction using summed-area tables[END_REF]. However, they implement only the tone mapping, using standard HDR images as inputs. Indeed, hardware vision systems for capturing and rendering HDR live video are at a adolescence stage [START_REF] Gallo | Artifact-free high dynamic range imaging[END_REF] and we failed to find in the literature a full HDR system implementing all the steps from capturing to rendering. The HDR-3 architecture, on the other hand, is an innovative camera prototype implementing the full HDR pipeline. From this purely algorithmic point of view, our real-time implementation outstrips the computational capabilities of the three other implementations.

Table 7 summarizes the comparison results in terms of processing performance (fps, resolution). From a raw performance point of view, our architecture runs at 60 fps on a 1.280 × 1.024-pixel resolution, giving an overall throughput of 78.6 megapixels per second. This performance is significantly higher than the two other FPGA-based architectures and lower than the GPU implementation. Nevertheless, the Nvidia 8800 GTX processor used in this GPU alternative is not well suited to low-power embedded systems such as smart cameras.

We have also compared the image quality of the tonemapped images produced by the different architectures using five metrics: Mean Square Error (MSE), Normalized Root Mean Square Error (NRMSE), Peak Signal-to-Noise Ratio (PSNR), Universal Quality Index (UQI [START_REF] Wang | A universal image quality index[END_REF]), and the Structural SIMilarity (SSIM [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF]). UQI roughly corresponds to the human perception of distance among images. The value Our gold standard is the tone-mapped image of the Stanford memorial church with the method by F. Drago and Chiba [START_REF] Drago | Adaptive logarithmic mapping for displaying high contrast scenes[END_REF]. This technique is described as the most natural method and also the most detailed method in dark region [START_REF] Yoshida | Perceptual evaluation of tone mapping operators with real-world scenes[END_REF]. Considering the gold standard to be the reference signal, and the difference between this reference and the images processed by the other architectures to be the noise, the MSE, the PSNR and the UQI have been calculated for each architecture. The set of images is shown in Fig. 13. The method from Hassan and Carletta [START_REF] Hassan | A real-time FPGAbased architecture for a Reinhard-like tone mapping operator[END_REF] seems to provide more contrast and image details than our proposed method. This is mainly due to the fact they use as inputs HDR images with 28 bits per pixel, obtained off-line from a set of 16 multiple exposures of the same scene. However, the visual evaluation of the different images reveals that the HDR-3 system gives comparable results to the gold standard. This visual feeling is reinforced by different quality metrics. The HDR-3 architecture has the lowest MSE, the lowest NRMSE and the highest PSNR. Moreover, with an UQI value of 0.90 and a SSIM of 0.93, this indicates that the HDR images provided by our architecture are the closest from the gold standard and then, that the visual rendering of these images can be considered as the most natural one.

Conclusion

In this paper, we present a complete hardware vision system called HDR-ARtiSt based on a standard image sensor associated with a FPGA development board. This smart camera dedicated to real-time HDR live video fulfils drastic realtime constraints while satisfying image quality requirements. It embeds a full HDR pipeline, doing successively multiple captures, HDR creating, tone mapping, and streaming of the HDR live video to a LCD monitor.

The HDR-ARtist system has been built as an adaptive platform. From a purely hardware point of view, our HDR pipeline can be easily adapted to many conventional CMOS sensors. Using a new sensor only requires the design of a specific sensor board to be plugged onto the FPGA motherboard and the offline evaluation of the camera transfer function for the new sensor. From an application point of view, the HDR pipeline can be parametrized in terms of number of frames, depending on the scene dynamic range. In this paper, two different real-time implementations, using respectively 2 and 3 frames have been discussed. For each implementation, we obtain high-performance results due to a finely tuned implementation of the original Debevec's algorithm and a global tone mapping from Duan. The comparison with other state-of-the-art architectures highlights a high visual quality, close to Drago's algorithm, known as one of the best tone mappers. Moreover, to achieve high temporal performance, the HDR-ARtiSt platform embeds a dedicated memory management unit. This memory unit has been specifically designed for managing multiple parallel video streams to feed the HDR creating process. It significantly contributes to the whole performance of the system. Indeed, the HDR pipeline is synchronized on the image sensor framerate. It builds a new HDR frame for each new sensor capture and delivers a live stream of displayable content with a bandwidth of 629 Mbits/s. Such a memory unit also limits motion blur and ghosting artifacts in the HDR frames because of the continuous acquisition process.

All these results open interesting avenues for future exploration both on hardware and software issues. New releases of the HDR-ARtist platform embedding FPGA from Xilinx Virtex-6 and Virtex-7 families are currently in development. They will give us opportunity to implement the most recent algorithms for computing radiance maps, and for local/global tone mapping. We also plan to automatically evaluate the real dynamic range of the scene and then to dynamically adapt the number of required captures to build the best HDR frame.

Finally, HDR video is prone to ghosting artifacts, which can appear with motion in the scene during the multiple captures. So, we intend to study and implement onto the FPGA dedicated ghost detection techniques in order to provide a real-time ghost-free HDR live video. A hw/sw approach based on reprogrammable Zynq architecture is under construction, which will simplify certain operations, and help to add some patches as the correction of local movements.

  Fig.1HDR frame of a real scene captured with 3 different exposure times (sequences by Fattal et al[START_REF] Fattal | Gradient domain high dynamic range compression[END_REF]).

Fig. 3

 3 Fig. 3 HDR-P video hardware is prototyped on a Xilinx Virtex-5 ML507 FPGA board and a daughter card with the EV76C560 1.3-Mpixel sensor.

Fig. 4

 4 Fig. 4 Framerates of the HDR standard technique and our technique.

Fig. 5

 5 Fig. 5 Initialization of the Memory Management Unit with storage of the first P -1th frames.

Fig. 6

 6 Fig. 6 Memory Management Unit with parallel acquisition of new lines of pixels and reading of previously stored lines.

Fig. 7

 7 illustrates how the MEC algorithm automatically estimates the new exposure times while rapidly varying illumination in the scene. When switching on the lamp, the number of white saturated pixels significantly increases (15.3 % for Fig.7.a). So, the MEC rapidly decreases the exposure time to get less than 10% saturated pixels for the high exposure time ∆t 3 (5.4 % for Fig.7.a). A similar approach is used in order to estimate the low exposure time ∆t 1 .(a) Before MEC.(b) After MEC.

Fig. 7

 7 Fig. 7 Figure (a) has 15.3% of white saturated pixels when the lamp is switched on. After MEC, Figure (b) has 5.4% of white pixels.

Fig. 8

 8 Fig.8HDR creating pipeline for HDR-2 video, using LUTs tree.

Fig. 9

 9 Fig. 9 Tone mapping computation.

Fig. 10

 10 Fig. 10 Visual evaluation of the HDR-2 application.

  (a) HDR-2 video system limitations in extreme lighting conditions (b) Zoom on different areas

Fig. 11

 11 Fig. 11 HDR-2 system limitations in extreme light conditions.

  (a) HDR-3 video system improvements in extreme lighting conditions (b) Zoom on different areas

Fig. 12

 12 Fig.12HDR-3 video system improvements in extreme lighting conditions.

  (a) Gold standard. (b) Our system. (c) Hassan et al. [19](d) Vytla et al.[START_REF] Vytla | A real-time implementation of gradient domain high dynamic range compression using a local poisson solver[END_REF] (e) Slomp et al.[START_REF] Slomp | Real-time photographic local tone reproduction using summed-area tables[END_REF]

Table 1

 1 List of commonly used terms and variables.

	P	Number of frames to create one HDR frame
	I p	pth frame in the sequence of P frames
	M	Frame height (i.e. row number)
	N	Frame width (i.e. column number)
	Z p i j	Luminance of the pixel (i, j) in the pth frame
	E i j	Luminance (or radiance) of the HDR pixel (i, j)
	g	Camera transfer function (CTF)
	∆t p	Exposure time of the pth frame
	D i j	Tone mapped pixel
	D min , D max Minimum and maximum values of the display devices
	τ	Overall brightness of the mapped frame
	L m	Line index
	W & R	Memory Write and Read operations
	2.2.1 Step 1: HDR creating
	Digital cameras have limited dynamic range since they can
	only capture from 8-bit to 14-bit images, mainly due to the
	limitations of the analog to digital converters in terms of
	noise levels. The most common method to generate HDR
	content is to capture multiple images of a same scene with
	different exposure times. If the camera has a linear response,
	we can easily recover the HDR luminance E i j from each lu-minance Z p i j and exposure times ∆t p stored in each frame p.
	Unfortunately, cameras do not have a linear response (i.e. Z p i j is not proportional to E i j and ∆t p ), and we have to esti-
	mate the non-linear camera transfer function (CTF) called g
	to combine properly the different exposures.

Table 2

 2

	Drago [13]	34.93 0.54	0.58	0.1	5.43
	Duan [11]	42.34 0.97	0.91	0.01	5.71
	Reinhard [35]	29.11 0.89	0.8	0.32	5.52
	Schlick [41]	40.71 0.43	0.56	0.03	5.50
	Tumblin [32]	42.01 0.14	0.29	0.02	5.59

TMO

PSNR UQI SSIM NRMSE Time(s) Comparison metrics for TMOs algorithms applied to a common HDR image (memorial by Debevec) constructed from three images. Exposure times used are 32s, 1s and 31, 25ms.

Table 4

 4 Design summary.

		Clock Domains
	Sensor	SDRAM	HDR processing	DVI
	114Mhz	125Mhz	114Mhz	25Mhz
		System Parameters
	P	Resolution	Throughput	Framerate
	2	1, 280 × 1, 024	78.6 Mpixels/sec	60

Table 5

 5 HDR-2: Summary of hardware synthesis report.

		Used Available Utilization
	Logic utilization
	Number of Occupied Slices	5,272	11,200	47.1%
	Complexity distribution
	Number of Slice LUTs	12,859	44,800	28.7%
	Memory management	2,149		4.8%
	HDR creating	4,211		9.4%
	Tone mapping	3,433		7.7%
	Post processing	3,066		6.8%
	Number of Slice Flip Flops 13,612	44,800	30.4%
	Memory management	2,682		6%
	HDR creating	5,107		11.4%
	Tone mapping	4,045		9%
	Post processing	1,778		4%
	Number of FIFO/BRAM	23	148	15.5%

Table 6

 6 HDR-3: Summary of hardware synthesis report.

		Used Utilization	Variation
				with HDR-2
	Logic utilization
	Number of Occupied Slices	5,891	52.6%	+11.7%
	Complexity distribution
	Number of Slice LUTs	15,281	34.11%	+18.8%
	Memory management	2,829	6.3%	+31.6%
	HDR creating	5,722	12.8%	+35.9%
	Tone mapping	3,433	7.7%	0%
	Post processing	3,297	7.4%	+7.5%
	Number of Slice Flip Flops	15,134	33.8%	+11.2%
	Memory management	2,682	6%	+0.1%
	HDR creating	6,071	13.5%	+18.9%
	Tone mapping	4,045	9%	0%
	Post processing	2,333	5.2%	+31.2%
	Number of FIFO/BRAMs	30	20.3%	+30.4%

Table 7

 7 Performance comparison with existing real-time tone mapping implementations. SSIM) index is a method for measuring the similarity between two images. The SSIM index can be viewed as a quality measure of one of the images being compared, provided the other image is regarded as of perfect quality. It is an improved version of the UQI index.

		This work	FPGA	FPGA	GPU
			[19]	[48]	[44]
	Device	Virtex 5	Stratix II	Stratix II	Nvidia GeForce
			EP2S130F780	EP2S15F484	8800 GTX
	Frame rate 60	60	60	100
	Frame	1, 280 × 1, 024	1, 024 × 768	1, 024 × 1, 024	1, 024 × 1, 024
	size
	(pixels)
	MSE	2.8695 × 10 2 6.6801 × 10 2 3.8646 × 10 2 5.8607 × 10 2
	NRMSE 1.7 × 10 -1	3.8 × 10 -1	1.3 × 10 -1	1.9 × 10 -1
	PSNR	2.355 × 10 1 1.988 × 10 1 2.226 × 10 1 2.045 × 10 1
	(dB)
	SSIM	9.3 × 10 -1	6.9 × 10 -1	5.5 × 10 -1	7.0 × 10 -1
	UQI	0.90	0.71	0.67	0.70
	of the UQI between two images is in the [-1, 1] range, and
	is 1 for identical images, 0 for uncorrelated images, and -1
	for completely anticorrelated images. The Structural SIMi-
	larity (

The R2D2 figure and the word "HDR " are only visible in electronic version of the paper and are almost hidden in the print version.

Acknowledgements This work was supported by the DGCIS (French Ministry for Industry) within the framework of the European HiDRaLoN project and by grants from the Conseil Regional de Bourgogne.


Benjamin Harbelot
email: benjamin.harbelot@checksem.fr

Helbert Arenas
email: helbert.arenas@checksem.fr

Christophe Cruz
email: christophe.cruz@u-bourgogne.fr

Using Semantic Web Technologies to Follow the Evolution of Entities in Time and Space

Keywords: spatio-temporal, semantics, GIS, perdurantism

In this paper we present the "continuum model". Our work follows a "perdurantism" approach and is designed to handle dynamic phenomena extending the 4D-fluent with the use of semantic web technologies. In our approach we represent dynamic entities as constituted by timeslices each with semantic, geometric, temporal and identity components. Our model is able to link the diverse representations of an entity and allows the inference of qualitative information from quantitative one. The inference results are later added to the ontology in order to improve knowledge about the phenomenon. The model has been implemented using OWL and SWRL. Our preliminary results are promising and we plan to further develop the model in the near future to increase the suitable data sources.

I. INTRODUCTION

For the design of a spatio-temporal knowledge system, it is necessary to consider the three components of an entity representation: 1) Spatial: consisting in the geometry, 2) Temporal: which defines the interval of existence of the geometries and finally 3) Semantic: which defines a meaning for the entity beyond the purely geographic one [START_REF] Harbelot | The spatio-temporal semantics from a perdurantism perspective[END_REF] [START_REF] Yuan | Use of a three-domain representation to enhance GIS support for complex spatial-temporal queries[END_REF]. Most of the current GIS tools focus on analysis and presentation of geographic data. However, nowadays due to the increasing availability of spatial/temporal data, it is necessary to have tools with inference capabilities, capable of assisting researchers in analysing large datasets. This new kind of tools should be able to identify patterns and perform reasoning with datasets corresponding to dynamic phenomena.

Modeling a real dynamic phenomenon can be seen as tracking the transition of phenomenon composing entities from one state to another. This transition is called: filiation relationship. Along time, entities with spatial components, can maintain different spatial and semantic relations with other entities. A natural way to model dynamic phenomena is to represent the evolution as a graph, in which entities and their states are represented as vertices and relations between entities as edges. A phenomenon would then generate a complex graph composed by different types of relations such as: temporal, semantic, spatial or filiation.

An alternative to classic GIS tools are Semantic Web technologies. Using these technologies it is possible to develop data models called ontologies specifically designed for reasoning and inference with software mechanisms. Ontologies allow for any given domain, the representation of relevant high level concepts as well as their properties and the relationships between concepts and entities. In this research we use Semantic Web technologies to develop the "continuum model", an ontology that allows us to represent diverse dynamic entities and analyse their relationships along time. Traditionally ontologies are static in the sense that the information represented in them does not change in time or space. In this paper we introduce the continuum model, an ontology that extends the 4D-fluent. Our ontology provides the mechanisms required to keep track of spatial and semantic evolution of entities along time.

In Section II, we discuss related work in the field of spatio-temporal knowledge representation. In Section III, we introduce the continuum model. In Section IV, we present the model specification using description logics. In Section V, we show some examples of GeoSPARQL used to implement the model. In Section VI, we describe how the model operates using an urban growth example and later we indicate our conclusions and future work.

II. RELATED WORK

The development of a spatial-temporal knowledge system involves two aspects, first the representation of the knowledge and second, the necessary mechanisms to perform analysis and querying.

A. Representing temporal data

The two main philosophical theories concerning the representation of object persistence over time are: endurantism and perdurantism. The first one, endurantism, considers objects as three dimensional entities that exist wholly at any given point of their life. On the other hand, perdurantism, also known as the four dimensional view, considers that entities have temporal parts, "timeslices" [START_REF] Welty | A reusable ontology for fluents in OWL[END_REF]. From a perdurantism point of view the temporal dimension of an entity is composed by all its timeslices. Therefore, it represents the different properties of an entity over time as fluent. A fluent is a property valid only during certain intervals or moments in time. From a designer point of view, the perdurantism approach offers advantages over the endurantism one, allowing richer representations of real world phenomena [START_REF] Al-Debei | Conceptual modelling and the quality of ontologies: Endurantism vs. perdurantism[END_REF].

The implementation of a perdurantism approach within an ontology, requires the conversion of static properties into dynamic ones. The two primary Semantic Web languages are OWL and RDF, unfortunately both of them provide limited support for temporal dynamics [START_REF] O'connor | A method for representation and querying temporal information in OWL[END_REF]. The OWL-Time ontology describes the temporal content of web pages and temporal properties of web services. Moreover, this ontology provides good support for expressing topological relationships between times or time intervals, as well as times or dates [START_REF] Hobbs | Time ontology in OWL[END_REF]. However, OWL allows only binary relations between individuals. In order to overcome this limitation several methodologies have been proposed for the representation of dynamic objects and their properties. Among the most well known are: temporal RDF, versioning, reification, Nary relationships and the 4D-fluent approach.

Temporal RDF [START_REF] Gutierrez | Introducing time into RDF[END_REF] proposes an extension of the standard RDF for naming properties with the corresponding time interval. This allows an explicit management of time in RDF. However, temporal RDF uses only RDF triples; therefore, it does not have all the expressiveness of OWL for instance, it is not possible to employ qualitative relations. Reification is a technique used to represent n-ary relations, extending languages such as OWL that allow only binary relations [START_REF] Hayes | RDF semantics, W3C Recomendation, 10 february 2004[END_REF]. In [START_REF] O'connor | A method for representation and querying temporal information in OWL[END_REF], the authors developed a lightweight model using Reification. The model is designed to be deployed on top of existing OWL ontologies extending their temporal capabilities. The model also implements a set of SWRL (Semantic Web Rule Language) operators to query the ontology. Reification allows the use of a triple as object or subject of a property. But this method has also its limitations, for instance the transformation from a static property into a dynamic one increases substantially the complexity of the ontology, reducing the querying and inference capabilities. Additionally reification is prone to redundant objects which reduces its effectiveness. Versioning is described as the ability to handle changes in ontologies by creating and managing multiple variants of them [START_REF] Klein | Ontology versioning on the Semantic Web[END_REF]. However, the major drawback of Versioning, is the redundancy generated by the slightest change of an attribute. In addition, any information requests must be performed on multiple versions of the ontology affecting its performance.

An alternative to the previously mentioned approaches is the 4D-fluent, which is an approach based on the perdurantism philosophical theory. It considers that the existence of an entity can be expressed with multiple representations, each corresponding to a defined time interval. In the literature, 4D-fluent is the most well known method to handle dynamic properties in an ontology. It has a simple structure allowing to easily transform a static ontology into a dynamic one [START_REF] Batsakis | SOWL: Spatio-temporal representation reasoning and querying over the semantic web[END_REF]. Unfortunately, the 4D fluent approach has also some limitations; although it allows the recording of frequent timeslices, it can not handle explicit semantics. This fact causes two problems: 1) It is difficult to maintain a close relationship between geometry and semantics; and 2) It increases the complexity for querying the temporal dynamics and understanding the modelled knowledge. Furthermore, this approach does not define qualitative relations to describe the type of change that has occurred or to describe the temporal relationships between objects. Then we can not know which entities have undergone a change and what entities might be the result of that change. Regardless of its limitations the 4D-fluent approach offers a solid starting point for the representation of temporal information in OWL. An interesting previous work using this approach is [START_REF]SOWL: a framework for handling spatio-temporal information in OWL2.0[END_REF].

Here the authors developed SOWL, which uses 4D-fluent to extend the ontology OWL-time making it able to handle qualitative relations between intervals, such as "before" or "after" even with intervals with vague ending points.

B. Querying the ontology

In [START_REF] Ryu | Application of moving objects and spatiotemporal reasoning[END_REF], the authors introduce a model in which spatialtemporal information contained in a database and a spatialtemporal inference system work together. However, no information is given on the Semantic Web technologies, only the Java language is quoted as a component of the inference engine; therefore, the universality and effectiveness of the inference system can be questioned. Another work is [START_REF] Karmacharya | Integration of spatial processing and knowledge processing through the semantic web stack[END_REF] in which the authors propose a reasoning system that combines the topological calculus capabilities of a GIS and the inference capabilities of the semantic web field. However, the notion of time is not incorporated in this model.

The capability of switching from quantitative to qualitative data is only possible with a reasoning system. In the case of SOWL this is possible thanks to the implementation of SWRL built-in. In SOWL, the built-ins allow the system to infer topological, directional and metric relations between entities. Qualitative information can be inferred from quantitative one and can be used as an alternative in case of missing quantitative data. In order to query the ontology the developers of SOWL implemented a language similar in syntax to SQL. This language performs simple spatialtemporal querying for both static and dynamic data [START_REF]SOWL: a framework for handling spatio-temporal information in OWL2.0[END_REF]. However, the work does not support identity relationships. It does not provide mechanisms to follow the changes an entity might experience by analysing its different representations.

Due to the nature of spatial-temporal datasets, we need a system able to handle large datasets. Traditionally, SPARQL has been the most common language to query an ontology. SPARQL is a W3C recommendation that operates at the level of RDF graphs. There are extensions, such as st-SPARQL and geoSPARQL that have been developed in order to allow SPARQL to operate on spatial entities [START_REF] Koubarakis | Modeling and querying metadata in the semantic sensor web: The model stRDF and the query language stSPARQL[END_REF].

2013, © Copyright by authors, Published under agreement with IARIA -www.iaria.org These extensions define datatypes, functions and operations allowing spatial analysis, however, there is limited temporal support. St-SPARQL is based on an extension of RDF called st-RDF that integrates contact geometries and incorporates time in RDF. GeoSPARQL offers similar capabilities, however, it has the advantage of being an OGC supported standard.

Our previous work [START_REF] Harbelot | The spatio-temporal semantics from a perdurantism perspective[END_REF] introduced the Continuum model using Java and SWRL rules to implement it. The rules were executed via a graphical interface using the Jena API to connect to the ontology and JDBC to access a database. The application automatically detects the presence of spatial built-ins in SWRL rules and performs the necessary calculations in the database. The system can automatically rewrite SWRL rules containing spatial built-ins. On one hand, this prevents repeating calculations that have already been done. On the other hand, it also generates SWRL rules without spatial built-ins but rather based on qualitative relationships expressed through properties defined in the ontology. However, we note three limitations to this model: 1) The treatment of a query containing a spatial built-ins can be very long depending on the number of geometries involved in spatial analysis, 2) The execution of SWRL rules containing spatial built-ins currently depends on our application and cannot be executed from other sources, for instance the traditional plugin SQWRL Tab Query of the Protégé tool, 3) There are limitations in the size of the datasets that can be managed by the application.

Although SWRL is a potent inference tool, it is not fully supported in current available triplestores. A triplestore is a software mechanism able to store large datasets with semantic annotations, providing query and retrieval capabilities. Some of the available triplestores support GeoSPARQL allowing users to perform complex spatial queries [15] [16].

In order to overcome this limitations identified in [START_REF] Harbelot | The spatio-temporal semantics from a perdurantism perspective[END_REF], we decided to modify the system architecture and implement a new version using a triplestore with spatial capabilities for spatial calculations and data storage. After evaluating the available options we opted for Parliament. In this paper we present a further development of the model first presented in [START_REF] Harbelot | The spatio-temporal semantics from a perdurantism perspective[END_REF], using in this case GeoSPARQL/SPARQL. In the next section we will describe how we implemented this approach in the continuum model.

III. THE CONTINUUM MODEL

The spatial evolution of an object involves movement or a change of shape [START_REF] Brisaboa | Constraints in spatiotemporal databases: A proposal for classification[END_REF]. In the case of a movement, it is easy to identify and locate the entity before and after the event. However, when an entity suffers a succession of changes a key question arises: how much can it change before its identity is modified? And if there is a semantic change, then how do we know that this is the same entity at different times? The 4D-fluent approach does not allow an entity to change its nature, only allows the change of the value of some of its properties. However, the semantics associated with a geometry may change. For example, a land parcel may change from being forest into being urban. In this example the geometry has not changed, however, a semantic change has occurred (see Figure 1A). It is equally possible that the semantics might not change while the geometry evolves. For instance, a given urban land parcel might expand by purchasing neighbouring parcels (see Figure 1B).

In order to represent a dynamic entity in the continuum model we create a set of timeslices, each corresponding to a representation of the entity during a determined period of time. Each timeslice is constituted by four components as depicted in Figure 2: 1) Semantic: To describe the knowledge associated with the entity, 2) Spatial: It is the graphical representation, 3) Temporal: It represents the interval or time instant that describe the temporal existence, and 4) The identity component, that allows us to group timeslices belonging to the same entity.

The goal of the continuum model is to follow the evolution of entities through time. To achieve this goal the model records the changes that entities might go through in their semantic or spatial components along time. For this purpose the model creates a new representation every time a change occurs (spatial, semantic or identity).There is a parent-child relationship between the resulting timeslices. A resulting child timeslice retains all the unchanged characteristics from the original parent timeslice. Figure 3 depicts how we can represent the evolution of an object in which only the semantic part has changed. Figure 4 depicts the evolution of an object in which the spatial component varies, while the rest of the components remain constant. Each change adds to the genealogy of the spatio-temporal components. The parent-child relation is recorded in the system, allowing The continuum groups related timeslices, which have a valid time interval of existence. The model links individual timeslices to their context. For instance, a timeslice can have a child that corresponds to a new object, then the identity component might be different between parent and child. Our system allows the definition of qualitative relations between timeslices, even when the timeslices belong to different objects. Figure 5 depicts the evolution of objects and how the continuum model is used to study them.

In our model we have implemented qualitative temporal relations based on binary and mutually exclusive relations as proposed by Allen [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] (see Figure 6). The addition of Allen relations increase the expressive power of the system by adding qualitative information in addition to the quantitative one. By using defined Allen relations between intervals we can obtain qualitative information even from intervals with vague endpoints in a similar fashion to [START_REF] Batsakis | SOWL: Spatio-temporal representation reasoning and querying over the semantic web[END_REF]. For example, Figure 7 depicts intervals "I1", "I2" and "I3". While we know the start and ending points of "I1", we do not know the ending point of "I2", and we do not know the starting point of "I3'. However, we know that "I1" meets "I2" and that "I2" contains "I3". Then we can infer that because "I2" contains "I3",then "I3" must be after "I1", even if the information about start and ending points is incomplete. Lack of knowledge caused by semi closed intervals is largely filled by the integration of Allen relations to the model (see Figure 7).

In GIS, objects or regions are represented by points, lines, polygons or other more complex geometries based on these primitives. All these geometries are defined using the coordinates of points which are quantitative information. There are mainly three types of relationships between geometries: directional, metric, and topological relationships. The topological analysis between two objects is done using the models: Dimensionally Extended Nine-Intersection Model (DE-9IM) or Region Connection Calculus (RCC8)

Topological Predicate Meaning Equals

The Geometries are topologically equal.

Disjoint

The Geometries have no point in common.

Intersects

The Geometries have at least one point in common (the inverse of Disjoint).

Touches

The Geometries have at least one boundary point in common, but no interior points.

Crosses

The Geometries share some but not all interior points, and the dimension of the intersection is less than that of at least one of the Geometries.

Overlaps

The Geometries share some but not all points in common, and the intersection has the same dimension as the Geometries themselves. Within Geometry A lies in the interior of Geometry B Contains Geometry B lies in the interior of Geometry A (the inverse of Within) [START_REF] Strobl | Dimensionality Extended Nine-Intersection Model (DE-9IM)[END_REF]. In both cases, we obtain an equivalent set of topological relationships for specific regions. To calculate the spatial relationships between two geometries the DE-9IM model takes into account the inside, the outside, and the contour of the geometries leading to the analysis of nine intersections as described in [START_REF] Strobl | Dimensionality Extended Nine-Intersection Model (DE-9IM)[END_REF]. There are eight possible spatial relationships of the resulting analysis-9IM (see Table I).

IV. MODEL SPECIFICATION

The relationships based on quantitative information can be translated later into qualitative data [START_REF] Brisaboa | Constraints in spatiotemporal databases: A proposal for classification[END_REF]. By analysing the relationships between temporal, spatial and identity components of timeslices it is possible to deduce qualitative topological relationships between them. The results of the analysis can be used to specify more semantically complex constructions. In this section we use Tarski-style formalisms to specify the components of our model.

A. Temporal components

To represent time intervals we follow the semantics suggested by [START_REF] Artale | A temporal description logic for reasoning about actions and plans[END_REF]. We can think of the temporal domain as a linear structure T composed by a set of temporal points P. The components of P follow a strict order <, which forces all points between two temporal points t 1 and t 2 to be ordered. By selecting a pair [t 1 , t 2 ] we can limit a closed interval of ordered points. The set of interval structures in T is represented by T ⋆ < [START_REF] Artale | A temporal description logic for reasoning about actions and plans[END_REF]. Temporal Points (P):

P I ⊆ ∆ I (1) Time Intervals (T ⋆ < ): [to, tf ] . = {x ∈ P|to ≤ x ≤ tf, to = tf }inT (2)
where to and tf are the initial and ending points of the interval respectively.

To define the relations identified by Allen [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] (see Figure 6) we first define two intervals i1 and i2: T ⋆ < (i1) , T ⋆ < (i2), being i to the starting point and i tf the ending point of the intervals:

Bef ore(i1, i2) → (i1 tf < i2 to ) (3) M eets(i1, i2) → (i1 tf = i2 to ) (4) Overlaps(i1, i2) → (i1 tf > i2 to ) ∧ (i1 tf < i2 tf ) (5) Starts(i1, i2) → (i1 to = i2 to ) ∧ (i1 tf < i2 tf ) (6) During(i1, i2) → (i1 to > i2 to ) ∧ (i1 tf < i2 tf ) (7) F inishes(i1, i2) → (i1 to > i2 to ) ∧ (i1 tf = i2 tf ) (8) Equals(i1, i2) → (i1 to = i2 to ) ∧ (i1 tf = i2 tf ) (9)

B. Spatial Components

The spatial representation of an object is given by the coordinates representing its geometry and characteristics associated to it (Spatial reference system, accuracy, precision, format, etc). It is represented by G. The spatial topological relations between geometries are defined by the Extended Nine-Intersection model (DE-9IM) (see Table I [START_REF] Strobl | Dimensionality Extended Nine-Intersection Model (DE-9IM)[END_REF]).

Additionally, we can implement the operation Union valid for geometries:

[x g , y g , z g ] ∈ G|Equals(z g , U nion(x g , y g )) (10)
In this case, the combination of geometries x g and y g will result in a new geometry z g .

C. Semantic Component

The semantic component of the objects describes the nature of the entities and can be composed by one or more alphanumeric properties.

D. Timeslices

An object representation in time is composed by a set of timeslices. Each timeslice T S in the model has four components: 1) A time interval T ⋆ < 2) A geometry G, 3) An identity O and 4) A semantic component representing all other potential alphanumeric properties associated to a timeslice. We represent all these properties as T S, as suggested in [START_REF] Baader | The description logic handbook[END_REF]. T S represents all the qualities that distinguish the class timeslice from other classes,.

T S ≡ ∀hasGeometry.G ⊓ ∀hasT ime.T * < ⊓T S ⊓ ∀isT imeSliceOf.O (11)

E. Filiation relationships between timeslices

In the continuum model the existence of an object is defined by a set of timeslices representing the state of the object during a defined period of time. In the model, a new timeslice is generated when a original timeslice suffers a change in any of its components. The relation between the original and the new timeslice follows a parent -child, filiation pattern. For this relation to exist the interval of the parent timeslice must meets the interval of the child 2013, © Copyright by authors, Published under agreement with IARIA -www.iaria.org timeslice (see Figure 6). In order to exist the filiation parentchild relationship between timeslices at least one of the components (geometry, semantics or identity) must remain constant. The filiation relationship is specified as: where: {ts 1 , ts 2 } ∈ T S , {ts 1g , ts 2g } ∈ G, {ts 1s , ts 2s } ∈ T S and {ts 1i , ts 2i } ∈ I

2) Derivation relationship: In this case, there is a difference between the identity component of parent and child, while there is at least one component (geometry or semantic) that remains constant. ∀hasDerivation.T S {ts 1 ∈ T S I |∀ts 2 .(ts 1 , ts 2 ) ∈ hasDerivation I → ts 2 ∈ T S I ∧ ∃((ts 1g = ts 2g ) ∨ (ts 1s = ts 2s ))∧ (ts 1o = ts 2o ) ∧ (meets(ts 1i , ts 2i ))} (14) where: {ts 1 , ts 2 } ∈ T S , {ts 1g , ts 2g } ∈ G, {ts 1s , ts 2s } ∈ T S and {ts 1i , ts 2i } ∈ I

F. Topological filiation relationships

By identifying the topological relationships between the geometric component of the timeslices we can define specific filiation relationships in which the spatial components evolve (see Figure 8).

1) Expansion: In this case, the geometric component of the child timeslice contains the geometry of the parent timeslice. There is no change in the identity component of the timeslice, both parent and child timeslices belong to the same object (see Figure 8). where: {ts 1 , ts 2 } ∈ T S , {ts 1g , ts 2g } ∈ G and {ts 1i , ts 2i } ∈ I

∀hasExpansion.T S {ts

1 ∈ T S I |∀ts 2 .(ts 1 , ts 2 ) ∈ hasExpansion I → ts 2 ∈ T S I ∧ (ts 1g = ts 2g ) ∧ (ts 1o = ts 2o )∧ meets(ts 1i , ts 2i ) ∧ hasW ithin((ts 1g , ts 2g )} (15)
2) Contraction: This process is the opposite to expansion (see Figure 8).

∀hasContraction.T S {ts

1 ∈ T S I |∀ts 2 .(ts 1 , ts 2 ) ∈ hasContraction I → ts 2 ∈ T S I ∧ (ts 1g = ts 2g ) ∧ (ts 1o = ts 2o )∧ meets(ts 1i , ts 2i ) ∧ hasContains((ts 1g , ts 2g )} (16)
where: {ts 1 , ts 2 } ∈ T S , {ts 1g , ts 2g } ∈ G and {ts 1i , ts 2i } ∈ I

3) Splits: In this relationship, the object identified as the parent timeslice identity (O) ceases to exist. The geometry of the parent timeslice is then the origin of two new geometries corresponding to timeslices whose identity is new. The union of the geometries of the resulting children timeslices is equal to the geometry of the parent timeslice (see Figure 8). ∀hasSplits.T S {ts 1 ∈ T S I |∀(ts 2 , ts 3 ).(ts 1 , (ts 2 , ts 3 )) ∈ hasSplits I → (ts 2 , ts 3 ) ∈ T S I ∧ (ts 1g = ts 2g ) ∧ (ts 1g = ts 3g ) ∧ (ts 2g = ts 3g )∧ (ts 1o = ts 2o ) ∧ (ts 1o = ts 3o )∧ meets(ts 1i , ts 2i ) ∧ meets(ts 1i , ts 3i )∧ equals(ts 1g , U nion(ts 2g , ts 3g ))} (17) where: {ts 1 , ts 2 , ts 3 } ∈ T S , {ts 1g , ts 2g , ts 3g } ∈ G and {ts 1i , ts 2i , ts 3i } ∈ I 4) Separation: In this case, the parent entity continues existing, however, its geometry originates a new geometry corresponding to a new entity. A hasSeparation relationship is similar to a hasSplits relationship with the difference that in hasSeparation at least one of the children timeslices must have the same entity as the parent timeslice (see Figure 8).

2013, ©

Copyright by authors, Published under agreement with IARIA -www.iaria.org ∀hasSeparation.T S {ts 1 ∈ T S I |∀(ts 2 , ts 3 ).(ts 1 , (ts 2 , ts 3 ) ∈ hasSeparation I → (ts 2 , ts 3 ) ∈ T S I ∧ (ts 1g = ts 2g ) ∧ (ts 1g = ts 3g ) ∧ (ts 2g = ts 3g )∧ ∃ =1 ((ts 1o = ts 2o ) ∨ (ts 1o = ts 3o ))∧ meets(ts 1i , ts 2i ) ∧ meets(ts 1i , ts 3i )∧ equals(ts 1g , U nion(ts 2g , ts 3g ))} (18) where: {ts 1 , ts 2 , ts 3 } ∈ T S , {ts 1g , ts 2g , ts 3g } ∈ G and {ts 1i , ts 2i , ts 3i } ∈ I 5) Fusion: In this relationship, the two parent entities merged and cease to exist to give rise to a new geometry corresponding to a new entity. Inverse to a hasSplits relationship. The resulting geometry is equal to the union of the former geometries. ∀hasF usion.T S {ts 1 ∈ T S I |∀(ts 2 , ts 3 ).(ts 1 , (ts 2 , ts 3 ) ∈ hasF usion I → (ts 2 , ts 3 ) ∈ T S I ∧ (ts 1g = ts 2g ) ∧ (ts 1g = ts 3g ) ∧ (ts 2g = ts 3g )∧ (ts 1o = ts 2o ) ∧ (ts 1o = ts 3o ) ∧ (ts 2o = ts 3o )∧ meets(ts 1i , ts 3i ) ∧ meets(ts 2i , ts 3i )∧ equals(U nion(ts 1g , ts 2g ), ts 3g )} (19) where: {ts 1 , ts 2 , ts 3 } ∈ T S , {ts 1g , ts 2g , ts 3g } ∈ G and {ts 1i , ts 2i , ts 3i } ∈ I 6) Annexation: In this case, the two parent entities merge but the resulting entity keeps the identity of one of its parents.

∀hasAnnexation.T S {ts 1 ∈ T S I |∀(ts 2 , ts 3 ).(ts 1 , (ts 2 , ts 3 ) ∈ hasAnnexation I → (ts 2 , ts 3 ) ∈ T S I ∧ (ts 1g = ts 2g ) ∧ (ts 1g = ts 3g ) ∧ (ts 2g = ts 3g )∧ ((ts 1o = ts 3o ) ∨ (ts 2o = ts 3o )) ∧ (ts 1o = ts 2o )∧ meets(ts 1i , ts 3i ) ∧ meets(ts 2i , ts 3i )∧ equals(U nion(ts 1g , ts 2g ), ts 3g )} (20) where: {ts 1 , ts 2 , ts 3 } ∈ T S , {ts 1g , ts 2g , ts 3g } ∈ G and {ts 1i , ts 2i , ts 3i } ∈ I V. IMPLEMENTATION This is an evolving work, continuously we are adding new capabilities to the continuum model. In our latest implementation we have deployed our ontology in a Parliament triplestore. In order to populate our ontology we have developed customized tools able to read information stored in shapefiles, GML, WFS and postgreSQL/postGIS data repositories and upload it into our triplestore. The harvesting tools have been developed using Java with Jena and Geotools libraries.

In this section we show how we can identify some of the filiation relationships between timeslices using GeoSPARQL.

2013, © Copyright by authors, Published under agreement with IARIA -www.iaria.org } Topological filiation relationships: Splits: SELECT ?ts1 ?ts2 ?ts3 WHERE{ ?ts1 a abc:TimeSlice. ?ts2 a abc:TimeSlice. ?ts3 a abc:TimeSlice. ?o1 a abc:Object. ?o2 a abc:Object. ?o3 a abc:Object. ?ts1 abc:isTimeSliceOf ?o1. ?ts2 abc:isTimeSliceOf ?o2. ?ts3 abc:isTimeSliceOf ?o3. ?ts1 abc:hasInterval ?i1. ?ts2 abc:hasInterval ?i2. ?ts3 abc:hasInterval ?i3. ?ts1 geo:hasGeometry ?geo1. ?ts2 geo:hasGeometry ?geo2. ?ts3 geo:hasGeometry ?geo3. ?geo1 geo:asWKT ?geo1wkt. ?geo2 geo:asWKT ?geo2wkt. ?geo3 geo:asWKT ?geo3wkt. FILTER ( (?s1!=?s2)&& (?o1!=?o3) && (?o2!=?o3) && (temporal:meets(i1,i2)) && (temporal:meets(i1,i3)) && (!geof:sfEquals (?geo1wkt,geof:union(?geo2wkt,?geo3wkt)))) }

VI. EXAMPLE CONTINUUM

The continuum model is flexible enough to be adapted in multiple fields. In this example, we use it to represent the urban evolution of the city of New Orleans. This city is the largest in Louisiana. It is located between the Mississippi river and the lake Pontchatrain. The oldest part of the city is placed on the banks of the Mississippi river, on the natural levees of the river. Since its beginning it was the main settlement in the area, however, New Orleans was not the only one. In the vicinity, other cities such as Jefferson, Lafayette or Greenville were established. These cities were absorbed into New Orleans in the XIXth. century. From 1718 to 1900 the urban growth was only into areas that were by nature high and dry. However, after 1900, technical developments allowed municipal authorities to drain the swamps located between the river and the lake Pontchatrain, creating artificially dry land for urban development. The final result is a city that occupies an area that resembles a bowl, with large neighborhoods lying on the bottom, in areas with low elevation, some of them even below sea Figure 10. Time frame or urban evolution level, which make them vulnerable to floods. If we add to this, the subsiding soil phenomenon occurring in the area, and the erosion of the coast line, we end up with a city in a particularly vulnerable location [START_REF] Campanella | Geographies of New Orleans: Urban fabrics before the storm[END_REF]. Figure 9 depicts different stages of the urban evolution of New Orleans. Figure 9D depicts the extension of the city around 2005, when it was flooded by Hurricane Katrina.

In order to use the continuum model to represent the urban evolution, first we define the class Human Settlement (HS) which represents cities that evolve through time. The temporal existence of each of the entities belonging to this class is represented by a set of timeslices which have the four components: 1) Semantic: representing properties associated with the entity, valid for the specific time interval, 2) Spatial: It is the graphical representation, in this case, the footprint of the human settlement, 3) Temporal: It represents the valid interval of existence for this timeslice, and 4) The identity component, that allow us to group timeslices belonging to the same human settlement.

By using the continuum model we are able to identify processes such as conurbation. The conurbation process involves two cities merging. Using the model we can represent the process as: Using the continuum model it is also possible to combine timeslices of objects of different nature. For instance, we can model the process urban growth in risk area. In order to represent the risk area we will use the footprint of the flood caused by Hurricane Katrina in 2005 (see Figure 9D). We create a new class risk areas as RA. Then we can identify the process growth in risk area as: U rbanGrowthInRiskArea(hs 1 , hs 2 , ra 1 ) ≡ hasExpansion(hs 1 , hs 2 )∧ ¬Overlaps(hs 1 , ra 1 ) ∧ Overlaps(hs 2 , ra 1 ) [START_REF] Mondo | A graph model for spatio-temporal evolution[END_REF] where: {hs 1 , hs 2 } ∈ HS and ra 1 ∈ RA

VII. CONCLUSION

In Figures 11 and12 we represent the relationships between geometries and intervals used in our analysis. By using these relations we can detect complex transitions between timeslices. Understanding data semantics is at the core of our work providing an easier way to manage data and reduce queries complexity. When using reasoning capabilities specific to the Semantic Web, the system may increase the knowledge stored in the ontology.

The continuum model is based on the 4D-fluent representation and develops the continuum concept in the context of a spatial-temporal GIS in order to preserve best understandable semantics for the objects represented. The continuum model handles time and space independently for each object allowing the inclusion or not of time and space in queries of spatial, temporal or spatial-temporal nature. Currently, the system is capable of tracking the evolution of objects along time. This model introduces a novel approach for the handling of properties and attributes for each object. The semantic management of the properties and attributes for each object will be part of further research in order to develop a complete system for the semantics of spatialtemporal information.

Our model offers explicit semantic and flexibility for semantics interoperability between information systems and data sharing. Currently, we are doing research in the field of smart queries, a term coined by [START_REF] Goodwin | What have ontologies ever done for uspotential applications at a national mapping agency[END_REF]. The term refers to the combination of heterogeneous datasources in order to solve complex proplems. Using the continuum model we will be able to integrate vector data sources available on the web [START_REF] Arenas | A Semantic Web Approach for Geodata Discovery[END_REF]. We plan to apply these capabilities to complex modelling scenarios such as Land Use/Land Cover change.

Figure 1 .

 1 Figure 1. Evolution examples: A)Two different semantic objects for the same geometry. B)Two related geometries for the same semantic object.

Figure 2 .

 2 Figure 2. The four components of a timeslice within the continuum model.

Figure 3 .

 3 Figure 3. Evolution example: A semantic change with the same geometry.

Figure 4 .

 4 Figure 4. Evolution example: A spatial change with the same semantic

Figure 5 .

 5 Figure 5. Using the continuum model to represent the evolution of an entity.

Figure 6 .

 6 Figure 6. Allen temporal relations.

Figure 7 .

 7 Figure 7. Using Allen temporal relations to infer new knowledge.

  ∀hasF iliation.T S {ts 1 ∈ T S I |∀ts 2 .(ts 1 , ts 2 ) ∈ hasF iliation I → ts 2 ∈ T S I ∧ ∃ ≤2 ((ts 1g = ts 2g ) ∨ (ts 1s = ts 2s )∨ (ts 1o = ts 2o )) ∧ (meets(ts 1i , ts 2i ))} (12) where: {ts 1 , ts 2 } ∈ T S , {ts 1g , ts 2g } ∈ G, {ts 1s , ts 2s } ∈ T S and {ts 1i , ts 2i } ∈ I The filiation relationship can be further specialized by setting or not constraints in the identity (O) component, then we have two possible filiation relationships: hasContinuation and hasDerivation [22] [23]. 1) Continuation relationship: In this case, the identity component of parent and child timeslices is the same. ∀hasContinuation.T S {ts 1 ∈ T S I |∀ts 2 .(ts 1 , ts 2 ) ∈ hasContinuation I → ts 2 ∈ T S I ∧ ((ts 1g = ts 2g ) ∨ (ts 1s = ts 2s ))∧ (ts 1o = ts 2o ) ∧ (meets(ts 1i , ts 2i ))} (13)

Figure 8 .

 8 Figure 8. Topological filiation relationships.

Figure 9 .

 9 Figure 9. City of New Orleans along time.

  2013, © Copyright by authors, Published under agreement with IARIA -www.iaria.org

Figure 11 .

 11 Figure 11. Representation of a conurbation process using the continuum model

Figure 12 .

 12 Figure 12. Representation urban growth in risk areas using the continuum model

Table I TOPOLOGICAL

 I PREDICATES AND THEIR CORRESPONDING MEANINGS.

Continuation:

SELECT ?ts1 ?ts2 WHERE{ ?ts1 a abc:TimeSlice. ?ts2 a abc:TimeSlice. ?o1 a abc:Object. ?ts1 abc:isTimeSliceOf ?o1. ?ts2 abc:isTimeSliceOf ?o1. ?ts1 abc:hasInterval ?i1. ?ts2 abc:hasInterval ?i2. ?ts1 geo:hasGeometry ?geo1. ?ts2 geo:hasGeometry ?geo2. ?geo1 geo:asWKT ?geo1wkt. ?geo2 geo:asWKT ?geo2wkt. ?ts1 abc:hasSemantic ?s1. ?ts2 abc:hasSemantic ?s2. FILTER ( ((!geof:sfEquals(?geo1wkt,?geo2wkt)) && (?s1=?s2))) || ((geof:sfEquals(?geo1wkt,?geo2wkt)) && (?s1!=?s2))) && (temporal:meets(i1,i2)) ) } Derivation: SELECT ?ts1 ?ts2 WHERE{ ?ts1 a abc:TimeSlice. ?ts2 a abc:TimeSlice. ?o1 a abc:Object. ?o2 a abc:Object. ?ts1 abc:isTimeSliceOf ?o1. ?ts2 abc:isTimeSliceOf ?o2. ?ts1 abc:hasInterval ?i1. ?ts2 abc:hasInterval ?i2. ?ts1 geo:hasGeometry ?geo1. ?ts2 geo:hasGeometry ?geo2. ?geo1 geo:asWKT ?geo1wkt. ?geo2 geo:asWKT ?geo2wkt. ?ts1 abc:hasSemantic ?s1. ?ts2 abc:hasSemantic ?s2. FILTER ( ((!geof:sfEquals(?geo1wkt,?geo2wkt)) && (?s1=?s2))) || ((geof:sfEquals(?geo1wkt,?geo2wkt)) && (?s1!=?s2))) && (temporal:meets(i1,i2)) && (?o1!=?o2) )