Michel Devy
email: michel.devy@laas.fr.

Jean-Louis Boizard

Diego Botero Galeano

Henry Carrillo Lindado

Mario Ibarra Manzano

Zohir Irki

Abdelelah Naoulou

Pierre Lacroix

Philippe Fillatreau

Jean-Yves Fourniols

Carlos Parra

Stereovision Algorithm to be Executed at 100Hz on a FPGA-Based Architecture

Introduction

This chapter describes the development of an integrated stereovision sensor intended to be embedded on mobile platforms like robots or intelligent vehicles. Such a sensor is required for the motion control of these platforms. Navigation can be either autonomous (e.g. for a robot executing tasks in dangerous environments), or supervised by a human driver (typically for intelligent transportation systems). Motion control of a mobile vehicle requires to integrate on the platform, a system generally structured in several levels. At the lower level, functions are encapsulated in modules directly connected to sensors and actuators; the next level, named generally the supervision level, controls the execution of these functions, recovers from internal errors or from unexpected events in the environment; finally the upper level, or decision-making level, generates tasks or adapts existing scritps with respect to missions which are generally transmitted by an operator through a communication medium. Tasks and scripts activate sequentially or in parallel several functions at the lower level. Depending on the complexity of the platform (number of sensors and actuators), of the environment (static vs dynamic, structured vs unstructured, a priori known vs unknown...) and of the missions to be executed, the system embedded on a mobile platform, is implemented on one or several processors, and could take advantage of dedicated subsystems, e.g. smart sensors equipped by its own processing unit, or smart actuators fitted with micro-controllers. Our project deals with the design and the implementation of a smart sensor that could execute complex perceptual functions, while satisfying very demanding real-time constraints. As soon as a motion must be executed by a mobile platform, perception functions provide environment modelling and monitoring, human-machine interface, sensor-based servoing, obstacle detection . . . Real time execution is required when tasks are executed in dynamic environments, i.e. when several mobile platforms act in the same area (multi-robots applications or several vehicles on roads) or when these platforms act in human environments (pedestrians in urban scenes, human operators for service robots...). Real time constraints depend on the relative speeds between mobile entities: for example, obstacle detection on an intelligent transportation system, must be executed at 100Hz, so that (1) several detections could be fused before activating an avoidance or an alarm action and (2) Time To Collision remains compatible with the system or the driver reaction time. Sensory data must be acquired on the environment, in order to feed perceptual functions devoted to detection, tracking, identification or interpretation of events, environment modelling, visual odometry or self-localization ...Vehicles or robots are equipped with cameras, telemeters (radar, laser, sonar...) or with more specific devices (RFID readers, magnetic sensors...). Vision is the more popular, not only for biologically or human inspired apriorism, but because it has many advantages: high resolution, cheap sensors, acquisition of both photometric and geometric information . . . Nevertheless, vision (especially 3D vision) is known to be very computationally demanding: it is why adapted visual algorithms and dedicated hardware subsystems must be jointly designed and evaluated for these applications. In the section 2, some works related to obstacle detection are recalled, as a justification for our hardware implementation of the stereovision algorithm. Then the classical stereovision algorithm is described in section 3, before presenting the state of the art for real time stereovision systems in section 4. The FPGA-based architecture for our hardware stereovision implementation is described in section 5. Our real time stereovision system is presented in section 6 and is evaluated in section 7. Finally, conclusions and perspectives are discussed in section 8.

Stereovision for ITS applications

Companies which make Intelligent Transportation Systems (ITS), are eager to integrate sensors and perceptual algorithms on cars, for different applications: obstacle detection on motorway or in urban traffic, lane departure detection, parking assistance, navigation, cockpit and driver monitoring. . . Different sensors have been evaluated for these applications: only vision is considered in this paper.

• monocular vision has been proposed to detect obstacles (cars or pedestrians) in urban scenes, but without assumptions on the environment (no "flat road" approximation for example). Monocular vision does not allow to cope with complex situations and is generally coupled with other kind of sensors (e.g. radar or laser devices).

• stereovision is widely used in the robotics community, typically to evaluate the terrain navigability at short distances [START_REF] Matthies | Stereo vision for planetary rovers: Stochastic modelling to near-real tim e implementation[END_REF]). Several companies (Videre Design Company (n.d.)) propose stereo rigs with a short baseline ( 10cm), well suited for indoor perception; K. [START_REF] Konolige | Small vision systems : Hardware and implementation[END_REF]) has developed the SVS library, with a real-time version of the stereo correlation algorithm (30Hz); VIDERE has also implemented this algorithm on a FPGA-based architecture.

• stereovision has been also evaluated in ITS applications for many years, but the real-time requirements, the limitations of the depth field, the lack of robustness. . . makes difficult to use stereovision in changing contexts.

In the LAAS robotics team, stereo is the main sensor used for outdoor terrestrial robot (figure 1 (top left)). It has been evaluated for several ITS applications: • detection of a free parking slot and assistance for the parking manoeuvre [START_REF] Lemonde | Obstacle detection with stereovision for parking modeling[END_REF]). Figure 3 shows the rectified image built from the left camera of the stereovision sensor (left) and the disparity image (right);

• pedestrian detection in urban scene (see figure 2, where it can be seen dense disparity information on the ground) or obstacle detection on motorway [START_REF] Lemonde | Stéréovision embarquée sur véhicule : de l'auto-calibrage Ãȃ la détection d'obstacles, Phd report[END_REF]) The next section recalls the main steps of the stereovision algorithm, on which our developments are based. Inputs are images acquired from left and right cameras; the output is the disparity image.

The stereovision algorithm

Our stereovision algorithm is classical. It requires an a priori calibration of the stereo rig. The main steps are presented on figure 5.

Initially the original right and left images I d and I g are processed independently. The distortion correction and rectification step allows to provide two aligned rectified images IR d and IR g : this step consists in applying a warping transform, using tables to transform (u, v) pixel coordinates from the original image frame to the rectified one: here u and v correspond respectively to the line number, and to the column number.

Then a preprocessing is applied on each rectified image, before looking for the best matching between a left pixel (u, v), with a right pixel (u, v -D), where D is the disparity. The pre-processing function depends on the score used in the matching function. Figure 6 shows a rectified stereo system, i.e. the two image planes are coplanar and lines are collinear. The disparity is equal to zero for two pixels corresponding to a 3D point located at an infinite distance; the maximal disparity D max is tuned according to the minimal 3D points distance that the sensor must detect, e.g. the minimal distance between a vehicle and an obstacle. Several correlation scores -SAD, SSD, ZNCC...-could be used to compare the correlation windows around the left pixel and around every right candidate (figure 7). Here the Census score [START_REF] Zabih | Non-parametric local transforms for computing visual correspondence[END_REF]) is exploited because it does not require floating-point computations and thus is better suited for an hardware implementation. Moreover it is a non-parametric technique based on the relative ordering of pixel intensities within a window W, rather than the intensity values themselves. Consequently, such a technique is robust with respect to the radiometric distortion. As mentionned here above, before computing the Census transform from the rectified images, a preprocessing, i.e. an arithmetic mean filter, is executed on both images. Let S uv be the set of coordinates in a rectangular sub image window of size m × n pixels and that is centered on the (u, v) pixel. The arithmetic mean filtering process computes the average value of the original rectified image IR (u, v) in the area defined by S uv . The value of the filtered image Î R at any point (u, v) is simply the arithmetic mean of all pixels in the region defined by S uv . The formula of this arithmetic mean is given by equation 1.

IR (i, j) (1)
This operation can be implemented without using the 1/mn scaling factor, only if the correct rank of the filtered pixels is considered. The mean filter simply smoothes local variations in an image. Also in this operation, noise is reduced as a result of blurring.

The Census score is computed from the left and right rectified and filtered images, modified by the Census transform (CT) expressed on equation 2, and illustrated on figure 8.

ÎRT(u, v)= (i,j)∈S uv ξ Î R (u, v) , Î R (i, j) (2)
In these transformed images, the intensity value on each pixel (u, v) is replaced by a bit string computed by comparing the intensity Î R(u, v) with the intensity of neighbour pixels selected in the area defined by S uv , i.e. a F c x F c correlation window centered on (u, v), where F c is a odd number. The function ξ computes the relationship between a pixel (u, v) and its nearest neighbors in D uv . This function returns a bit, that is set to one, when the intensity of the point (i, j) is lower than the intensity of the point (u, v), otherwise the bit is set to zero. The operator ⊗ denotes concatenation. Finally, ÎRT(u, v) represents the Census transform of the (u, v) pixel: it is a bit string with a length equal to F 2 c -1. The Census score between a left pixel (u, v) and a right one (u, v -D), is evaluated using the Hamming distance, i.e. the binary comparison between two bit strings provided by the Census transform applied independently on the two images. It is given by the number of equal bits between IRT g (u, v) and IRT d (u, v -D), so this score is normalized, from an integer included between 0 and F 2 c -1. Equation 3shows how this score is computed: ÎRT l and ÎRT r represent the two Census transformed images (left and right images respectively), ⊗ denotes the binary XNOR operation, applied for each bit of the bit string (index i). For every (u, v) left pixel, all scores are computed with all (u, v -D) right pixels on the same epipolar line for all D in [0, D max ]. Then, for the (u, v) left pixel, the disparity D H (u, v) corresponds to the maximum of these Census scores. How to find this maximum? Several classical tests could be used, like it is shown on figure 9 (left): a maximum is valid only if it is discriminant (i.e. high enough), not flat (i.e. sharp enough) and not ambiguous (i.e. the difference between the two first maximal scores is higher than a given threshold). If the maximal score is not valid (lack of texture, ambiguity...),the (u, v) pixel is unmatched. An error during this matching step, could create false points in the 3D image; a good verification method to avoid these errors, consists in performing pixel correlation first from the left image to the right one, then from the right image to the left one, and to select the best common matching. In the software version, this verification does not increase the computation time. Scores are computed during the left-right run, a potential disparity D is found for each left pixel, and then scores are recorded to be used again during the right-left run. The verification is performed when the left-right run has been processed for a complete line; it is controlled that the same D disparity is found when starting from the right pixel, looking for a maximal score in the left image. If not, the potential disparity D is cancelled in the disparity map.

D H (u, v) = max D∈[0,D max] 1 N N ∑ i=1 ÎRT l (u, v) i ⊗ ÎRT r (u, v -D) i (3)
Finally, the D H (u, v) disparity is an integer between 0 and D max : two improvements are possible. First a sub pixel accuracy could be obtained by an interpolation method applied on the score function; on figure 9 (right),the maximal score has been found in i + 1; the sub pixel imax value is computed from a parabolic interpolation of the score function. Secondly, a filtering function could be applied to remove potential errors in the disparity image: it consists in segmenting this image in regions, and to remove the very small regions.

Fig. 9. The disparity validation and computation

Once the Census correlation step has been completed, the 3D reconstruction is computed in the left camera reference frame, as shown in figure 6: the Z axis corresponds to the optical axis, the Y axis is parallel to the image line and oriented towards the left, while the X axis is parallel to the image column and oriented downwards. The 3D reconstruction step requires the calibration data, i.e. the baseline B (distance between the two optical centers) and similar intrinsic parameters for the rectified ilatinmages (α u , α v , u 0 , v 0 ).Ifa(u 1 , v 1 ) left pixel matched with a (u 1 , v 1 + D) right pixel (D negative), it corresponds to a (X, Y, Z) 3D point with the following coordinates:

X = α v .B.(u 1 -u 0 ) α u .D ; Y = B.(v 1 -v 0 ) D ; Z = α v .B D
These equations show that (1) the disparity is constant for pixels located at a fixed depth Z with respect to the cameras, and (2) the Z error increases as Z 2 , so that the stereo measurements are very noisy for long distances.

Depending on the available computation power, and on the optimization of the code, this algorithm could provide low resolution (320x240 or 160x120) 3D images at video rate; it could be sufficient for robotics application, with a weak robot speed. It does not satisfy real-time requirements for ITS applications or for safety issues when service robots navigate in human environments.

Real time stereovision: state of the art

In vision, the term real time is generally understood as video-rate [START_REF] Brown | Advances in computational stereo[END_REF]), i.e. 30 frames per second or higher . Our challenge is real time stereovision at more than 100Hz, for a 640x480 resolution (nb of pixels per line W = 640). Using Camera Link connections with two synchronized cameras, images are transmitted with a 40MHz pixel rate (pixel period T = 25ns), giving 130 images per second at this resolution. We aim at a 100Hz image rate, so pixels must be processed on the fly, with a possible delay between successive images if required.

It is yet beyond the possibility of the software implementation, that are generally limited to a video-rate performance with this VGA resolution; several authors proposed in the 90's, such implementations, e.g. the SVS library implemented by K. [START_REF] Konolige | Small vision systems : Hardware and implementation[END_REF]), or the stereo machine of T.Kanade [START_REF] Kanade | A stereo machine for video-rate dense depth mapping and its new applications[END_REF]).

Only an FPGA implementation can reach a 100Hz performance, and can also meet cost and size requirements. As soon as powerful enough FPGAs appeared, stereovision architectures [START_REF] Corke | Frame-rate stereopsis using non-parametric transforms and programmable logic[END_REF]) have been proposed. A variety of architectures able to provide dense disparity maps have been reported since 1995. Most of the integrated real-time stereo system, are based on Field Programmable Gate Array (FPGA) because of the flexibility given by FPGAs at the moment to realize dedicated hardware architecture, a reasonable low cost (e.g. against ASIC) and an higher processing speed (e.g. against PC). In 2001, Arias-Estrada et al. (Arias-Estrada et al. ( 2001)) reported a stereo system able to process 320x240 images at a rate of 71 FPS using SAD scores for stereo matching. The system does not perform any rectification nor distortion correction and uses a Xilinx Virtex FPGA valued at $2,000 dollars. Darabiha et al. [START_REF] Darabiha | Video-rate stereo depth measurement on programmable hardware[END_REF]) developed a four FPGA based system with an estimate cost of $10,328 dollars able to provide 256 x360 dense disparity map at 30 FPS. A complete stereo vision system with radial distortion correction, Laplacian of Gaussian Filtering and disparity map computation via SAD is proposed by Jia et al. [START_REF] Jia | A miniature stereo vision machine (msvm-iii) for dense disparity mapping[END_REF]. This system can produce 640 x 480 dense disparity maps with 64 levels of disparity at 30 FPS and has an estimated cost of $2,582 dollars. Two systems able to process more than 200 images per second, are presented by Georgoulas et al. [START_REF] Georgoulas | Real-time disparity map computation module[END_REF]) and Jin et al. [START_REF] Jin | Fpga design and implementation of a real-time stereo vision system[END_REF]) respectively. The first system used SAD and the second is based on Census for computing the disparity map, both system process 640 x 480 images and both of them have a price higher than a thousand dollars. These systems [START_REF] Chonghun | Symmetrical dense disparity estimation: algorithms and fpgas implementation[END_REF]) [START_REF] Sunghwan | Real-time stereo vision on a reconfigurable system[END_REF]) are compared with our own architecture in table 1, considering the FPGA family, the estimated cost (in $), the resolution of input and output images (Res in pixel 2 ), the frame rate (in Frame Per Second), the score used by the matching method, the maximal disparity (Max in pixels) and finally, the size of the neighbourhood used to compute scores (Win in pixels). The architecture presented in this paper can produced 640 x 480 dense disparity maps at maximum rate of 491 FPS. This stereo vision system performs rectification and distortion correction functions on images acquired from two cameras, and then the correlation function on the transformed images, with a 3 FPGAs pipeline architecture. The overall cost of the proposed hardware, is about $120, thus making this architecture a good choice for low cost system.

Author 2009)) (30hz for 320x240 images).

Real time stereovision: our architecture

Even though its software implementation requires a lot of memory, our stereo algorithm is well adapted for integration on a dedicated architecture: no floating-point computations, boolean operations on bit strings..., even if the software implementation requires a lot of memory. The FPGA implementation has been presented in [START_REF] Boizard | Fpga based architectures for real time computation of the census transform and correlation in various stereovision contexts[END_REF]) [START_REF] Naoulou | An alternative to sequential architectures to improve the processing time of passive stereovision algorithms[END_REF]) [START_REF] Naoulou | An alternative to sequential architectures to improve the processing time of passive stereovision algorithms[END_REF]). In (Ibarra-Manzano et al. (2009)) and (Ibarra-Manzano et al. ( 2009)) it is discussed how to generate such an architecture, from tools dedicated to high level synthesis from C programs. Actually, these tools have been used in order to test and evaluate several possible architectures: once these preliminary choices have been done, actual architectures have been generated using classical tools, i.e. QUARTUS for our ALTERA implementation.

Figure 10 presents the general architecture, which is made with five main modules: the acquisition of original left and right images, the rectification, the mean operator, the Census transformation and the Census correlation. Images are not stored completely; pixels are processed on the fly, with a pixel clock defined by the cameras or the communication protocol with the cameras (here CamLink). So the pixel clock is 40MHz, i.e. every module must execute its task every 25ns. •T w o Acquisition modules acquire the two left and right images, here at a 40MHz pixel clock.

A given number N bu f of lines acquired directly from the cameras, have to be memorized, before executing the next processings; this number depends on the images distortion or misalignment ranges. Cameras are synchronized, so that pixels with the same image coordinates (u, v) are received at the same clock front edge.

•T w o Rectification modules generate intensities for the rectified left and right pixels, using precomputed address tables. These tables are built offline, from calibration data. The rectified left and right pixels with coordinates (0, 0) are generated with a delay of N bu f lines with respect to the acquisition.

• Then two Mean operator modules apply a mean filter independently on the two images. This computation is based on the sum of 3x3 window centered around every pixel. Every mean module requires a working memory of 4 lines, avoiding read-write conflicts. The mean pixels are provided with a latency of 3 lines (plus 2 pixels) with respect to the input.

• Outputs from the Mean operator modules are inputs for the Census Transformation (CT) modules which compute census images; every pixel is replaced by a bitstring computed from comparisons with their neighbours, in a 7x7 window. So every CT module requires a working memory of 8 lines, and provides the result as a string of 49 bits for every pixel, with a latency of 7 lines (plus 3 pixels) with respet to the input.

• Finally from these left and right CT pixels, the correlation scores are computed and maximum scores are selected by a Census Correlation module. When starting from the left image, due to the configuration (see figure 6), the left pixel (u, v) can be matched with right pixels from (u, v -D max ) to (u, v). So scores are computed for (D max + 1) couples of pixels; if the maximum score is found for the position (u, v -D), then the output of the module is equal to the disparity D corresponding to the (u, v) coordinates in the disparity map.

• In our implementation, the disparity is directly sent to a CamLink output generator, so that the disparity map is sent at the same frequency than the original images, towards a client system, here a PC only used in order to display the stereo result.

The architecture performance depends on the way scores are computed. Figure 11 presents several options:

• at the top, a sequential architecture is shown. It is a software-like strategy, where (D max + 1) scores are computed in sequence before looking for the maximum: it does not take advantage of the potential parallelization on an hardware implementation.

• in the middle, the scores computation is parallelized only to match left pixels with right ones; it is typically a SIMD operation, so that (D max + 1) identical and synchronous processes can provide all scores in parallel. It is the simpler strategy, because when the left CT pixel (u, v) is available, its corresponding one in the right image is already computed in the right image. The search for the maximum, exploits a dichotomy strategy.

• on the bottom, a dual approach is proposed. Left-right scores are computed and the maximum score is looked for like in the previous case, but a verification is made using right-left scores and right-left matchings.

The dual approach using both the right-left and the left-right stereo matching, requires more memory and more delay. In the software implementation, verifications are applied between every line u; all scores are memorized when applying the left-right stereo matching for every (u, v) pixel on this line; so scores are stored in a (D max + 1)x640 2D table; the left-right matching for a (u, v) left pixel consists in finding the maximum score on the line v of the score table; the right-left matching for a (u′, v′) right pixel consists in finding the maximum score for a diagonal of the score table. These two maximums (on the line and the diagonal), must be the same. This approach is sequential, thus not adapted to hardware implementation; a dedicated architecture is proposed hereafter, based on parallel searching for the left-right and the right-left matchings. Results presented in the section 7 are obtained with the parallel architecture, without right-left verification. At the end, the final latency between the original acquisition and the generation of the disparity for a (u, v) pixel, can be approximated by (N bu f + 10) lines, plus 5 pixels:

• the number of lines is given both by the distortion factor of the original images, and by the window size used to compute the Mean operator and the Census Transformation;

• the extra delay of 5 pixels, is given also by the window size, and also by pipeline stage required in order to compute the maximal score.

Each module is detailed in the following subsections.

The rectification.

This function applies an homography to the two images, and correct distortions if they cannot be neglected. So, it is a simple coordinate transform, using for every image, two address tables generated off line, one for u, one for v. These tables give the correspondance between the (u, v) coordinates in the original image and the (u rect , v rect ) ones in the rectified image. Two solutions could be implemented:

• N bu f lines of the original image are recorded before activating the stereo algorithm on successive rectified pixels; first "inverse" address tables are used to transform every rectified pixel coordinates and to pick up its intensity in the buffer.

• N bu f lines of the rectified image are initialized from the pixels of the original image using "direct" address tables. Some rectified pixels could remain not initialized, creating artificial "holes" in the rectified image [START_REF] Irki | An approach for the real time correction of stereoscopic images[END_REF]).

The two solutions have been implemented; the first one is the more efficient.

The resolution of the rectified images could be reduced with respect to the original one; in our implementation, the pixel clock is 40MHz for the acquisition module of 640x480 images (25ns between two pixels of the original images). The frequency could be reduced to 10MHz (100ns between two pixels) if rectified images are generated with a 320x240 resolution. Here the same frequency is used for all modules, so that the final disparity map has the same resolution than original images. Address tables are generated especially to correct image distortions. Figure 12 presents possible configurations for the rectified images with respect to the corrected original ones. Generally wide-angle lenses are used on our robotics application, so that images are mainly warped due to barrel radial distortions. So the distortion correction deplaces every pixel of the original images on its image radius, creating a zooming effect, i.e. pixels are further from the image center. The corrected images could be selected as shown on the bottom line: on the left, the rectified cameras have a smaller view field than the original ones and the resolution is higher; on the right, the view field is the same, but keeping the same image size, the resolution is smaller.

So address tables are implemented as a 2D array; for every (u rect , v rect ) pixel of the rectified image, a 32 bits word is read in the address table. This word encodes for each rectified pixel, the position of the corresponding one in the original image. It is given as a position in the current circular buffer of N bu f lines, (U int , V int ), plus four factors (Δa, Δb, Δc, Δd) required to apply a bilinear interpolation. The intensity in the position (u rect , v rect ) of the rectified image, is computed as:

Irect(u rect , v rect )=ΔaI b u f (U int , V int )+ ΔbI b u f (U int , V int + 1)+ ΔcI b u f (U int + 1, V int )+ΔdI b u f (U int + 1, V int + 1) (4)
The size N bu f of the circular buffer filled by the Acquisition module must be selected so that the required original pixels are in the buffer when applying this interpolation. In our implementation, using wide-angle lenses, N bu f = 30.

The arithmetic mean filter.

Rectified pixels are processed on the fly, synchronously with the acquisition of the original pixels, but with a latency of N bu f * W * Tns (480μs with N bu f = 30; W = 640; T = 25ns).

Once initialized, a rectified pixel is transformed by a simple mean filter, using a 3x3 window.

The filtering process requires to record 4 lines (3 to compute the mean, one to memorize the incoming pixels of the next line). A filtered pixel is generated with a latency of (2W + 2) * Tns.

The mean computation is achieved in two steps; namely horizontal and vertical additions.

The architecture of the corresponding module is shown on Fig. 13. Three registers as shown in figure 14, are used to perform the horizontal addition. Three successive pixels are stored in three shift registers. These shift registers are connected to two parallel adders of eight bits so that the result is coded in ten bits. The result of horizontal addition is stored in a memory, which is twice as large as the image width. The vertical addition is computed by taking the current horizontal addition result plus the stored horizontal addition of the two previous lines.

The arithmetic mean of the nine pixels window is coded in 12 bits. The normalization (division by 9) is not required here, because the next function only compares pixel intensities.

The Census transform.

Pixels filtered by the mean operator are provided by the previous step at every pixel clock; they are used as inputs for the Census transform module. This transformation encodes all the intensity values contained in a F c xF c window as a function of its intensity central value. The process is very simple, but it generates long bit strings if F c is increased. After analysis on synthetic and real images, F c was set to 7, giving for every Census pixel, a string of 48 bits; fortunately only a circular buffer of D max strings computed from the left and right images, must be recorded before executing the Census Correlation module. The Census Transform requires to record F c + 1 lines, and a transformed pixel is generated with a latency of three lines plus four pixels, (4W + 4) * Tns.

The architecture of this module is decribed on Fig. 15. This module requires a circular buffer of 8 lines in order to store results of the Mean operator, that is to say 12 bits pixels. The size of the working memory is equal to the image width (W = 640) minus the width of the searching window (7 pixels in our case), because Census bitstring cannot be computed for pixels close to the image limits, so 60,8Kbits. Moreover this module requires a matrix of 7x7 shift registers, so that at every pixel clock, seven successive pixels on seven successive lines centered on a (u, v) pixel are stored synchronously. Let us note that at this same period, the (u + 4, v + 4) pixel is computed by the Rectification module.

Once pixels of the 7x7 Census window are stored in registers, then the central procedure of the Census transform is executed: the central pixel of the Census window is compared with its 48 local neighbours. It requires that all corresponding registers are connected to comparators activated in parallel as shown on Fig. 15. Finally, the Census result is coded on 48 bits, where each bit corresponds to a comparator output.

The Census correlation.

Correlation task is intended to link up right Census image with left one or vice versa, taking into account that, images contain objects that are common between them. As it is well known, correlation task serves to find the object apparent displacement, called disparity measurement. Stereo matching must compute similarity measurements (or scores), between left and right pixels that could be matched; matchings are selected maximizing the similarity scores. So the module consists of two main steps: in one hand, the computation of the similarity scores, in another hand, the maximum score search.

As shown on figure 7, the Census Correlation module has been designed at first from the left image to the right one, because it allows to minimize the latency time.

Figure 16 shows the corresponding module architecture for the left-right correlation. Firstly all D max + 1 scores are computed in parallel; the last 64 Census codes computed by the previous module in the right image, are synchronously stored in shift registers (each one is a word of 48 bits), depicted as D 0 (for (u, v)), D 1 (for (u, v -1)), D 2 (for (u, v -2))...on the left of Fig. 16. Both registers and the left Census code computed for the current processed pixel in (u, v) position, are the inputs of XNOR binary operator which delivers 48 bits as output; if a bit in the right Census code is the same than the corresponding one in the left Census code, the resulting bit given of the XNOR operation will be set to one; on the contrary, if compared bits are different, the XNOR operation returns zero. The 48 bits returned by every XNOR operator, are summed, in order to find the number of equal bits in the compared Census codes. This number add i gives the similarity score between the (u, v) left pixel with the (u, vi) right one. So scores are integer numbers from 0 (if all bits of the Census codes are different) to 48 (identical Census codes). Then these scores are compared in order to find the N i position for the add i maximum score; it is done by comparing scores for adjacent potential matches. The search for the maximum score is processed by pyramidal comparisons; for a 2 N array, it requires N cycles. Here D max = 64, so the search for the maximum score, requires 6 steps.

The left-right verification.

The Census correlation could be made in parallel from the left image to the right one and from the right image to the left one, but not synchronously. With rectified and non convergent cameras, when a left pixel is read, the matched one in the right image is already recorded amongst the D max circular buffer. On the contrary, when a right pixel is read, the matched one in the left image will be acquired during the D max next periods. This time-lag makes the architecture more complex, and adds a latency of D max periods.

Nevertheless, the result is improved using this left-right verification. Indeed, when we search for the maximum scores, several scores could be identical for different disparities. In the software version, basic verification tests on the found maximum, are made to filter bad matchings (see figure 9(left)). These tests are not implemented in the previous module. So a verification step allows to eliminate these false disparities, comparing disparities provided by the left-right and right-left Correlation processes.

Figure 17 presents the proposed architecture. Two Census Correlation modules are executed in parallel; the first one has been described in the previous section. The second one is identical, but a right Census code is compared with the D max + 1 next computed left Census codes. So this right-left search requires an extra latency (here 64 pixel periods more). All computed disparities are stored in shift registers: so this module requires 2xD max registers (here 6 bits registers, because disparity is between 0 and 63). The verification consists in comparing disparities given by the two approaches: if disparity d is given by the left-right search, a disparity D max -d must be given by the right-left search. If this test is not satisfied, the disparity is not valid. • the evaluation kit was connected to two JAI cameras, mounted on micro-actuators, so that an expert operator could manually align the two image planes.

• Images with a 640x480 resolution, are transferred to the evaluation kit at 40MHz, using CameraLink serial communication protocol.

• it was intended to study a multispectral version of this perceptual method, fusing sensory data provided by classical CMOS cameras with FIR ones (far infrared, using micro This static analysis about the resources requirements, allowed us to select what could be the most well suited FPGA in the ALTERA family, in order to implement our stereo algorithm. Due to economic requirements (low cost, low power consumption), the Cyclone family was mainly considered: the number of LEs available on the 1C20 chip (20000) could be sufficient, but not the number of EABs ( 64). The CycloneII family has been selected (1.1Mbits of embedded memory, up to 64000 LEs) to design a computing unit adapted for the stereovision algorithm. The stereovision computing box is presented on figure 22; only three FPGA boards are integrated by now, because like it will be seen in the section 7, the CycloneII resources provided by three boards are sufficient with a wide margin. As presented on figure 23, our system has a pipeline architecture; two image flows go through all FPGAs:

A multi-FPGAs computing box for stereovision

• FPGA1 receives the two original images; it performs the rectification function on the left one; outputs are the rectified left image, and the original right one.

• FPGA2 performs the rectification function on the right original image; outputs are the two rectified images.

• FPGA3 performs the correlation function; outputs can be selected, using jumpers. Generally it is the disparity map, and the left rectified image (for display purpose on the PC).

Real time stereovision: evaluations 7.1 Benchmarking on the Middlebury data set

The performance of our integrated stereo architecture has been evaluated using two methods. First, a simulation of the HDL code has been performed on images Tsukuba, Teddy, Venus and Cones extracted from the Middlebury stereo dataset [START_REF] Scharstein | A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[END_REF]). Percentages of bad pixels are computed on different regions (all, non-occluded, discontinuity) of the disparity images, according to the method proposed for benchmarking stereo algorithms in [START_REF] Scharstein | A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[END_REF]):

B = 1 N Σ (x,y) (d C (x, y) -d T (x, y) > d )
where N is the number of pixels in the disparity map, d C (x, y) is the computed disparity, d T (x, y) is the ground truth disparity, and d is the disparity error tolerance. Table 2 presents on the three first columns, these percentages for the raw disparity images; the mean percentage of bad pixels for all images is 37,5%. Then a filtering operation is applied on the raw disparity images, using a median filter on a 5x5 window, followed by a erode operation on a 5x5 structuring element. The PC can filter and display these disparity images only at 15Hz; the filtering method will be soon implemented on a fourth FPGA board which will be integrated on our system. Table 3 shows how many resources are used on the three FPGAs on which our architecture is integrated. The synthesis process is carried out thanks to Altera Quartus II v 9.0 Web Edition. Theoretically, the maximal frames per second rate of our stereo implementation, could be 490 FPS, taking 151.31 MHz as the maximal frequency for the pixel clock: N images/s = N pixels/s /size image (so 491 151310000/640x480). Our real tests are based on JAI cameras which have a 40MHz pixel clock; so now our system provides 130 disparity images/s. The CameraLink connection is sufficient in order to send this data flow to an host computer; by now, it is a PC which only displays disparity images at 15Hz. Furthermore, another relevant fact is that FPGAs 1 and 2 on which the rectification architectures are implemented, are underused according to the percentage of used logic elements (LEs), so it could be possible to use a smaller and cheaper FPGA for these tasks.

Conclusions

This paper has described the current results of a project about the design and the implementation of a smart perceptual subsystem, that could be mounted on a mobile platform in order to execute very computationnaly demanding functions, like obstacle detection. Up to now only the acquisition of 3D data from visual sensors has been considered, using the integration of a classical correlation-based stereovision algorithm on a processing unit made of connected FPGA-based boards. This processing unit is fed at 40MHz by images acquired by two or three cameras through Camera Link connections, and can provide disparity images at more than 100Hz with a 640x480 resolution on a Camera Link output connected to a client computer. By now, other perceptual functions must be executed on the client computer because either they are too complex (like image segmentation) or they require too many floating-point computations : filtering of the disparity map, 3D reconstruction, obstacle detection either directly from the disparity map or from the 3D image. . . Up to now, because of some simplifications made on the original stereovision algorithm, disparity maps acquired by our stereo sensor, are very noisy and contain too many artefacts. We are currently improving these results, by implementing on FPGA, interpolations and verifications already validated on the software version. Moreover, assuming that the ground is planar, disparity maps can be directly exploited to detect obstacles on the ground, using the v-disparity concept [START_REF] Labayrade | Real time obstacle detection in stereo vision on non flat road geometry through v-disparity representation[END_REF]), so that a probabilistic obstacle map could be provided to the client computer. It is intended to estimate also on the smart sensor, the relative speed of the detected obstacles. Finally other Fig. 26. A demonstrator for a smart multi-cameras sensor for obstacle detection.

algorithms, not directly based on stereovision, are currently studied, in order to design and implement smart sensors for obstacle detection. First a multi-cameras system, devoted to ground-obstacle segmentation [START_REF] Devy | Integrated subsystem for obstacle detection from a belt of micro-cameras[END_REF]) has been developed for service robotics: figure 26 presents our demonstrator, currently equipped with four cameras. Then we develop an heterogeneous multi-cameras system, made with a classical CMOS camera and an infrared sensor (in the 8-12μm bandwidth), devoted to obstacle detection in bad visibility conditions.

Fig. 1 .

 1 Fig. 1. Example of stereo setups, on a robot (top left) or inside a vehicle for cockpit monitoring (top right) or road perception (bottom)

Fig. 3 .

 3 Fig. 3. Obstacle detection to find a parking slot (figure4, where the road cannot be detected, due to the lack of texture). For this latter application, images have been acquired from a large baseline stereo rig presented on figure1(bottom) 2 .

Fig. 5 .

 5 Fig. 5. The description of the stereovision algorithm.

Fig. 6 .

 6 Fig. 6. 3D reconstruction from rectified images.

Fig. 7 .

 7 Fig. 7. Stereo matching on rectified images: the correlation principle

Fig. 8 .

 8 Fig. 8. The CENSUS transform.

Fig. 10 .

 10 Fig. 10. General architecture.

Fig. 11 .

 11 Fig. 11. Sequential vs parallel architectures.

Fig. 12 .

 12 Fig. 12. Possible configurations for the rectified and corrected images.Let us note (A, B, C, D) the four original image corners in pixel coordinates, so A =(0, 0); B = (0, 639); C =( 479, 0); D =( 639, 479). Let us note (A′, B′, C′, D′) the four rectified image corners. Generally wide-angle lenses are used on our robotics application, so that images are mainly warped due to barrel radial distortions. So the distortion correction deplaces every pixel of the original images on its image radius, creating a zooming effect, i.e. pixels are further from the image center. The corrected images could be selected as shown on the bottom line: on the left, the rectified cameras have a smaller view field than the original ones and the resolution is higher; on the right, the view field is the same, but keeping the same image size, the resolution is smaller.

Fig. 13 .

 13 Fig. 13. Architecture for the module Arithmetic mean filter.

Fig. 14 .

 14 Fig. 14. Shift registers in order to memorize 3 successive pixels.

Fig. 15 .

 15 Fig. 15. Architecture for the module Census transform.

Fig. 16 .

 16 Fig. 16. Architecture for the module Census correlation.

Fig. 17 .

 17 Fig. 17. Architecture for the module left-right verification.Finally, a disparity is generated for a given pixel with a latency of (N bu f * W +(2W + 2)+ (4W + 4)+2 * D m ax) * Tns with all steps. By now the filtering algorithm used in the software version, is not integrated on a FPGA.6. Real time stereovision: our FPGA-based implementation 6.1 First validations without rectificationThe stereovision algorithm has been firstly implemented in VHDL on the QUARTUS development tool (Altera Quartus reference manual (n.d.)), and then loaded and executed on the evaluation kit NIOS-DEVKIT-1S40 (Altera Stratix reference manual (n.d.)), equipped with a STRATIX 1S40 with 41250 logic elements (LEs) and 3.4Mbits of embedded RAM memory. The embedded memory was not sufficient to test the rectification function. So it was not implemented in this first implementation. Cameras were aligned thanks to mechanical devices shown with our preliminary acquisition setup on figure18 presents :

Fig. 18 .

 18 Fig. 18. Three cameras (the central FIR) connected to the computing unit. bolometers).

Fig. 19 .

 19 Fig. 19. The ressource requirements with respect to the image size and the size of the correlation window.

Fig. 20 .

 20 Fig. 20. The developed multi-FPGAs platform (right), inspired from the DTSO camera (left)A modular electronic computing board based on a CycloneII FPGA, was designed by Delta Technologies Sud Ouest (Delta Technologie Sud-Ouest Company (n.d.)), for this project about stereovision, but also, for high-speed vision applications using smart cameras. DTSO has designed an intelligent camera called ICam (figure20), made of at least 4 boards: (1) the sensor board, equipped with a 1280x1024 CMOS array, (2) the computing board, equipped with a CycloneII FPGA with only 18000 LEs, but with two 1MBytes banks of external memories (read access time: 50ns, with the possibility to read two bytes in parallel), (3) the power supplying board and (4) an interface board, allowing an USB2 connection (8MBytes/s) between the camera and a client computer. Recently a Ethernet version (Wifi or wired) has been designed, integrating in the camera a PowerPC on Linux, in order to manage the TCP/IP protocol, and to allow to use a network of communicating iCam cameras. Depending on the application, it is possible to integrate in ICam several computing boards, connected by a chained parallel bus: an algorithm could be parallelized according to a functional repartition (sequences of functions executed in pipeline) or a data distribution between the computing boards. ICam is a smart modular camera: how to convert this design in order to deal with stereovision? Depending on the sensor baseline, two configurations could be considered to implement a real-time stereovision sensor.• For applications involving small view fields, like cockpit monitoring in a car (figure1(top right)), the stereo baseline could be less than 10cm, like for on-the-shelf stereo sensors (Videre Design Company (n.d.)) (Point Grey Design Company (n.d.)). The ICam architecture

Fig. 22 .

 22 Fig. 22. An integrated version on a multi-FPGAs architecture.

Fig. 23 .

 23 Fig. 23. The hardware computing box for the stereovision algorithm.

Fig. 24 .

 24 Fig. 24. Results provided by our architecture with a Post-Processing applied to images from the Middlebury data set 7.2 Evaluation from real-time experiments Second, performances are evaluated from real-time image sequences acquired on indoor scenes with a stereo rig connected to the multi-FPGAs system presented on figure 22. A result is presented on figure 25. This figure shows the left stereo image (top) and the raw disparity image (bottom left) sent by the multi-FPGAs system on a CameraLink connection to a PC, and the filtered disparity image (bottom right) processed by software.The PC can filter and display these disparity images only at 15Hz; the filtering method will be soon implemented on a fourth FPGA board which will be integrated on our system. Table3shows how many resources are used on the three FPGAs on which our architecture is integrated. The synthesis process is carried out thanks to Altera Quartus II v 9.0 Web

Fig. 25 .

 25 Fig. 25. Results provided by our architecture implemented on a multi-fpgas configuration: (top) original image, (bottom) disparity images before and after filtering

Table 1 .

 1 Comparisons between integrated stereovision algorithms.

		FPGA family	Cost	Resolution	FPS	Score	Max	Win
	Arias Estrada	Xilinx Virtex2	2000	320 x 240	71	SAD	16	7x70
	Darabiha	4 Xilinx Virtex2	10328	256 x 360	30	LWPC	20	N/A
	Jia	Xilinx Virtex2	2582	640 x 480	30	SAD	64	9X9
	Chonghun	Xilinx Virtex2	2983	1024 x 1024	47	SAD	32	16x16
	Lee	Xilinx Virtex2	7567	640 x 480	30	SAD	64	32x32
	Georgulas	Altera Stratix2	10797	640 X 480	275	SAD	80	7X7
	Jin	Xilinx Virtex4	7261	640 x 480	230 Census	64	11x11
	Our system	3 Altera Cyclone2	120	640 x 480	491 Census	64	7x7

Some authors have used FPGA platforms only as a preliminary validation for a ASIC-based implementation: several ones have been developed, e.g. at Zurich ETH Institute (

(Kuhn et al.(n.d.)

) (50Hz for 256x192 images),

[START_REF] Hamette | Fingermouse -architecture of an asic-based mobile stereovision smart camera[END_REF]

) (pixel clock limited to 5MHz) or at Daejeon University in Korea

(Han et al. (

Table 2 .

 2 Table2presents on the three last columns, these percentages for the filtered disparity images; the mean percentage of bad pixels is decreased to 29,4%. Percentages of errors for the raw and filtered disparities, computed on the four images extracted from the Middlebury data set.

	Image name nonocc disc	all	nonocc disc	all
	Tsukuba	36.0	43.1 37.4	26.0	27.7 33.9
	Teddy	36.4	37.5 47.9	28.1	29.3 42.3
	Venus	36.6	42.8 48.5	28.2	35.3 40.5
	Cones	19.6	28.4 36.1	12.2	21.8 27.3

Table 3 .

 3 Resources required for the presented algorithm.

	Board	Used LEs Available LEs % Used LEs % Used Memory Max Frequency
	FPGA 1	868	18752	5%	31%	160 MHz
	FPGA 2	868	18752	5%	31%	160 MHz
	FPGA 3	13582	18752	72%	37%	151.31 MHz

Test vehicle of Continental in Toulouse, France

Test vehicle of the LIVIC lab in Satory, France

Acknowledgments

This work has been funded by a Midi-Pyrénées region project in France and by the ECOS Nord action C07M01 about the international scientific cooperation between France and Columbia.

• Mario Ibarra Manzano was supported by the scholarship 183807 granted by CONACYT and SEP administration in Mexico.

• Diego Botero Galeano is supported by the FUI project SART, funded by the french ministry of Industry.

• Zohir Irki is supported by the Laboratoire des Systèmes Numériques (LSN/UERAuto), Ecole Militaire Polytechnique (EMP), Alger, Algeria.

• Philippe Fillatreau is currently Assistant Professor at the Laboratoire Genie de Production (LGP) of the Ecole Nationale d'Ingénieurs de Tarbes (ENIT).


Bénédicte Lebret
email: benedicte.lebret@inrae.fr

Quality attributes of pork and processed products from fat breeds -Examples of local french breeds

    Copyright

Quality attributes of pork and processed products from fat breeds -Examples of local french breeds


Reynaud Stéphane

Anthony Dumas

Ana Roxin

Neuro-symbolic approach for querying BIM models

Keywords: Building Information Modelling (BIM), knowledge-based question answering (KBQA), ontology, artificial intelligence, neuro-symbolic

Integrating technologies like the Internet of Things (IoT) and artificial intelligence (AI) has transformed the smart building domain, enabling innovative services. The data gathered throughout a building's lifecycle, including construction and usage, create a comprehensive database for efficient management and improvement, mainly through Building Information Modelling (BIM). However, accessing and utilising these data can be challenging for users, as it often requires specialised query skills. Improving information accessibility involves intuitive and user-friendly query interfaces. Traditional approaches struggle to provide the flexibility and adaptability needed to keep up with evolving building information and user language expressions. To address these challenges, modern and scalable methods from symbolic and numeric artificial intelligence offer a solution. These systems can handle varying queries, adapt to changing data, and provide more user-friendly interactions, aligning better with user expectations in the industry.

I. INTRODUCTION

Since the arrival of technologies such as the Internet of Things (IoT) [START_REF] Jia | Adopting Internet of Things for the development of smart buildings: A review of enabling technologies and applications[END_REF] or artificial intelligence (AI) [START_REF] Rodríguez-Gracia | Review of artificial intelligence techniques in green/smart buildings[END_REF] in the field of smart building, new innovative usages have emerged, and services have been offered to users. The evolution of smart buildings requires, in particular, consideration of innovative approaches for communication between users and buildings, focusing on providing more fluid and broader access to information about buildings [START_REF] Gamboa-Rosales | Determining Technologies Trends and Evolution of Smart Building Technologies by Bibliometric Analysis from 1984 to 2020[END_REF].

Information concerning the entire life cycle of a building, starting from its design until its demolition, undergoes transformation to be recorded in databases. This information can be further enriched with data relating to the use and condition of the building, collected from various sources such as sensors and technical devices. This data aggregation helps create a rich and accurate representation of the building, providing invaluable insights for its management, maintenance and improvement [START_REF] Watson | Digital buildings -Challenges and opportunities[END_REF].

Building information modelling (BIM) is the methodology of choice to share digital representation of facilities in the architecture, engineering and construction (AEC) industry [START_REF] Kushwaha | Contribution of building information modeling (BIM) to solve problems in architecture, engineering and construction (AEC) industry and addressing barriers to implementation of BIM[END_REF]. BIM is defined as the "use of a shared digital representation of a built asset to facilitate design, construction and operation processes to form a reliable basis for decisions." [START_REF]Organization and digitization of information about buildings and civil engineering works, including building information modelling (BIM) -Information management using building information modelling -Part 1: Concepts and principles[END_REF] Using these data requires a certain skill level to formulate highly structured queries outside most building users' skills. Therefore, to make these data accessible to as many people as possible, providing users with the ability to submit requests clearly and intuitively becomes crucial to ensuring accessibility and ease of use.

Balancing the flexibility required to formulate queries in natural language with adapting to frequently changing building information poses a significant challenge [START_REF] Lin | A Natural-Language-Based Approach to Intelligent Data Retrieval and Representation for Cloud BIM[END_REF]. Conventional approaches, which rely on sets of preestablished rules, face several obstacles in this complex context.

First, the flexibility inherent in formulating queries in natural language is essential to facilitate interaction between users and building information systems. However, traditional methods based on rigid rules struggle to manage this variety of formulations and intentions. Building an exhaustive set of rules for every query becomes tedious and time-consuming. In addition, these rules must be constantly updated to follow the evolution of linguistic expressions linked to the available data.

Furthermore, the field of information related to buildings is constantly evolving. Buildings undergo regular modifications, updates, and additions, directly impacting the associated data. Rules-based approaches prove ill-suited to this dynamic, as they cannot easily adjust to new elements and changes in building characteristics. These challenges highlight traditional approaches' limitations and the need to adopt more modern and scalable methods [START_REF] Kolomiyets | A survey on question answering technology from an information retrieval perspective[END_REF]. Natural language processing (NLP) systems based on AI, such as language understanding models, can adapt to variations in query wording and learn from constantly changing data. This new approach offers superior performance in terms of accuracy and usability while better aligning with the expectations of users who seek more fluid and natural interactions with building information systems. Incorporating cutting-edge technology into building practices can effectively surmount the restrictions of conventional techniques and cater to the evolving demands of users in the industry.

II. SCIENTIFIC BACKGROUND

The need for a structured knowledge representation of the building information stems partly from the abundant laws and regulations surrounding the AEC industry and partly from the existing information systems in use throughout this industry [START_REF] Pauwels | Semantic web technologies in AEC industry: A literature overview[END_REF].

A. Semantic Web

Semantic Web is a framework aimed at improving the ability of computers to understand web content. Therefore, the main objective of the Semantic Web is to add meaning to the existing web content. This facilitates the comprehension of the relationships between different pieces of information by machines, enabling them to perform more intelligent tasks [START_REF] Berners-Lee | The Semantic Web: A new form of Web content that is meaningful to computers will unleash a revolution of new possibilities[END_REF].

Semantic web technologies provide a standardised way of describing and linking data on the Web, which allows machines to process and reason about information. These technologies include Resource Description Framework (RDF), RDF Schema (RDF-S), Web Ontology Language (OWL), and the query language SPARQL [START_REF] Patel | Present and future of semantic web technologies: a research statement[END_REF].

B. Ontology

An ontology is a formal way of representing knowledge that outlines the concepts, their properties, and the links between them in a specific domain or subject area. This is achieved notably by providing a shared vocabulary for describing and modelling a knowledge domain. The underlying goal of ontologies is to structure information in a manner understandable to humans and machines by ensuring that data are consistently organised and interpreted.

In the Semantic Web context, ontologies are commonly described employing RDF and OWL [START_REF] Gómez-Pérez | Ontology Specification Languages for the Semantic Web[END_REF]. OWL is a compelling language for creating ontologies with rich semantics.

C. Knowledge graph

A knowledge graph is a structured representation of knowledge that connects various entities (e.g., people, places, objects, concepts) through relationships. This kind of graph database stores data in a format that makes it easy to explore the connections between different pieces of information [START_REF] Fensel | Introduction: What Is a Knowledge Graph?[END_REF].

Knowledge graphs help organise and link data from multiple sources, allowing complex queries and data analysis to be performed efficiently. They are essential in many applications, such as knowledge management systems, search engines, and recommendation systems.

D. SPARQL

SPARQL is a query language for manipulating and querying data stored in RDF format. SPARQL is a key Semantic Web component that queries knowledge graphs and other RDF data sources. Indeed, SPARQL is explicitly designed for querying RDF data, a widely used format for representing structured data in the semantic Web. RDF data are made of subject-predicate-object triples, and the core of SPARQL is triple pattern matching. Variables can then be used to represent unknown parts of the triple, making it possible to retrieve data with specific patterns.

To query data from multiple RDF sources in a single query, SPARQL supports federated queries. This feature is essential to integrate data from various distributed sources seamlessly. SPARQL also defines a protocol for querying remote RDF data sources over HTTP.

III. RELATED WORK

A. Information extraction

BIM information extraction (IE) approaches can be grouped into 3 categories.

1) Manual and rule-based IE

The simplest, though most time-consuming and labourintensive, approach is to have human experts sort through BIM models to extract specific information.

BIM models often contain metadata associated with their elements, allowing the use of metadata extraction techniques to gather additional information.

By implementing systematic semantic tagging using standardised labels and classifications, like Industry Foundation Classes (IFC) [START_REF]Industry Foundation Classes (IFC) for data sharing in the construction and facility management industries -Part 1: Data schema[END_REF], tools and scripts can be used further to streamline the extraction of information from BIM models [START_REF] Ignatova | The extraction and processing of BIM data[END_REF].

The approaches in this category suffer from a common drawback: the requirement to have experts in each domain of a project readily available.

2) User interface-based IE BIM tools and software applications often propose interactive user interfaces (UIs) to select elements coupled with filters to ease the retrieval of specific class or object properties [START_REF] Ignatova | The extraction and processing of BIM data[END_REF]. This approach is convenient and efficient for a domain practitioner seeking information, but the limited capabilities inherent to UIs do not allow for fine-grained fast information extraction. Also, practitioners cannot work outside their domain efficiently, requiring the help of a domain expert.

3) Automated and query-based IE

As a step further from the first two categories mentioned above of approaches, developers can take advantage of the APIs (application programming interfaces) provided by most BIM software platforms to automate information extraction through plugins and scripts [START_REF] Ignatova | The extraction and processing of BIM data[END_REF].

Additionally, BIM domain knowledge can be represented by creating ontologies and knowledge graphs associated with BIM models. Then, querying these knowledge structures can provide the desired specific information.

While this category of approaches provides the most advanced capabilities, they require that almost all project stakeholders master the principles of query languages and have a profound understanding of the underlying knowledge and/or data schema.

4) Natural language-based approach

Using NLP systems can alleviate the limitations of all the approaches mentioned above. Indeed, a natural language interface can effectively hide the underlying mechanisms and complexity required to properly query databases and ontologies, enabling seamless access to BIM model information without needing experts. Despite the recent advances in NLP, aligning a request expressed in natural language with the concepts contained in project-dependent BIM models remains a challenge for the scientific community [START_REF] Yin | An ontology-aided, natural language-based approach for multiconstraint BIM model querying[END_REF].

B. Knowledge Base Question Answering

Knowledge Base Question Answering (KBQA) systems are a type of NLP application designed to answer questions by querying knowledge base (KB). These systems rely on structured knowledge representations, such as RDF-based knowledge graphs, to deliver precise and accurate answers to user queries. While the earliest work dates back to the 1960s and 1970s, the field of KBQA systems has significantly grown thanks to advances in NLP and the emergence of new artificial intelligence techniques. Indeed, many approaches have been developed since the 1990s and 2000s to locate and extract relevant information from unstructured texts and improve the understanding of natural language, entity recognition, query generation, and the presentation of responses [START_REF] Gomes | A study of approaches to answering complex questions over knowledge bases[END_REF]. The recent advent of neural networks and large language models has made it possible to make significant progress in the precision and robustness of KBQA systems, particularly in the understanding and processing natural language [START_REF] Gomes | A study of approaches to answering complex questions over knowledge bases[END_REF].

Interpreting a natural language request goes beyond simply identifying specific entities in text. Semantic interpretation, understanding of syntactic context and qualification concerning a KB are involved. Notably, the KBQA systems have an extremely high overall sensitivity to named entity recognition (NER) quality.

Indeed, when entities are identified in a text, understanding their semantic meaning is critical. This involves assigning a precise meaning to these entities based on the context in which they appear. Semantic interpretation helps associate the correct meaning with the entity, which is crucial for accurately understanding the text.

Additionally, each named entity is often used in a specific context in the text. Understanding this syntactic context is essential to fully grasp the entity's role in discourse, thus helping avoid ambiguities and ensure accurate analysis of information in the text.

Lastly, the retrieved entities often have specific relevance to the underlying KB. By qualifying these entities regarding the KB, a crucial link is established between the information extracted from the text and the database, thus allowing more precise exploitation of the data for subsequent tasks.

KBQA systems work on thematic entities present in their KBs, but they must meet the challenge of processing named entities extracted from natural language questions, which less rich in domain-specific information. This requires sophisticated extraction, linking and contextual understanding techniques to ensure accurate answers.

A review of the literature [START_REF] Lan | Complex Knowledge Base Question Answering: A Survey[END_REF] outlines mainly two families of approaches in KBQA systems to process natural language queries: semantic analysis (SA) and information retrieval (IR).

1) Semantic analysis

This approach usually relies on Symbolic AI elements and can be summarised in a linear process consisting of 4 steps:

1. Syntactic and semantic understanding 2. Analysis and understanding of logic 3. Instantiation in the KB of the logical form

Executing the query on the KB

The SA approach has many advantages for NLP to query a KB.

First is the explainability of reasoning, essential to understanding how a model or system makes decisions. In the context of SA, the reasoning carried out to understand the meaning of sentences and formulate queries is often more transparent. This means it is possible to trace back to the logical steps and semantic connections leading to a particular conclusion or interpretation. Unlike other more opaque approaches, SA makes it possible to follow the path of answer construction, which is crucial in areas or situations where decision-making is critical.

Second is the interpretability of results, which is a challenge rarely addressed. SA aims to produce results that are more easily understandable by human beings. This approach makes results more intuitive by using techniques that highlight semantic relationships and conceptual connections. For example, SA can provide information on the key concepts that led to a classification, thus helping to interpret the decision process and the outcome.

The third is the robustness to question disturbance, which maintains performance and pertinence even when questions are formulated differently or with deviations from what was anticipated during the design. This robustness arises from the ability of SA to capture the overall meaning and semantic relationships between words and concepts rather than relying strictly on exact keyword matches. Therefore, SA can capture the underlying intent and produce coherent answers even if a question is phrased with synonyms or variations.

However, even if the SA approach offers significant advantages in terms of explainability, interpretability and robustness, it has several significant disadvantages which limit its effectiveness in certain situations.

First, one of the significant drawbacks of this approach is its narrow generalisation capacity. This means that SA may have difficulty handling cases outside its predefined operating range. For example, if the system was designed on a limited or narrow data set, it might have difficulty understanding examples containing terms, contexts, or relationships not included. This limitation can hinder this approach's ability to handle varied data and provide accurate answers in less familiar scenarios.

Second, SA requires considerable expertise to build a solid logic for analysis and understanding. This expertise can extend to system design and semantic processing rules' definitions. To obtain reliable and accurate results, in-depth knowledge of the domain language, data structures and semantic relationships is often necessary. This requirement for expertise can make implementation and maintenance of the approach complex, as well as the need to collaborate with highly qualified specialists for any changes to the system, even minor ones.

Third, SA can face scaling problems when processing large amounts of data or responding to many queries in real time. Indeed, complex semantic operations often require intensive calculations, leading to performance issues when available computing resources are limited.

Lastly, another important drawback is the high sensitivity of the approach to the complexity of the questions asked. Queries that are ambiguous, poorly worded, or contain conflicting information can lead to irrelevant or incorrect answers. As a result, the quality of SA results can vary significantly depending on the quality and clarity of the questions asked.

2) Information Retrieval

This approach usually relies on the use of Numeric AI and can be summarised in a process of 4 steps: The IR approach has specific advantages for NLP, different from SA, to query a KB.

One of the IR approach's main advantages is the possibility of end-to-end training models. This means it is possible to train a model from raw data without requiring an intermediate step of manual data processing. This can speed up the learning process and make it easier to deploy solutions.

Unlike the SA approach, where it is necessary to build complex logic to answer questions, the IR approach avoids this step by relying on correspondence patterns between queries and documents. This can make systems development simpler and less prone to human errors in logic design.

Thanks to the reduction of the necessary reasoning space, this approach shows a low sensitivity to the questions' complexity. Even for complex questions, IR models can extract relevant information by focusing on key terms and matches in the data. However, despite these advantages of simplicity of training, management of the complexity of questions and lack of need to construct complex logic, the IR approach presents a certain number of disadvantages which can be strongly limiting.

The first major disadvantage of the IR approach lies in the opacity of the reasoning. IR models often do not clearly explain how an answer is generated. This can make understanding the model's decisions difficult, especially in situations where transparency is essential. Also, IR models may have difficulty handling unforeseen variations in the data. Minor changes in the available data or the context of the questions may result in incorrect or inconsistent answers. This limits their ability to generalise effectively about new or unknown data.

Lastly, IR models require a massive, high-quality training dataset to achieve reliable and accurate performance. This can make their development costly, time-consuming, and complex: collecting and preparing adequate data can be a significant challenge in many specialist areas.

3) Neuro Symbolic Reasoning

The 2 previous approaches, SA and IR, can be supplemented by the neuro-symbolic reasoning (NSR) approach to reduce their limitations and improve their capabilities because NSR enables combining the capacity of neural networks to capture information from unstructured data with the power of symbolic reasoning approaches to formalise and manipulate this information in a logical and structured way [START_REF] Zhang | Neural, symbolic and neural-symbolic reasoning on knowledge graphs[END_REF].

Symbolic systems are designed to manipulate symbols, logical rules, and abstract representations of knowledge. They allow information to be modelled and structured in an organised manner, which leads to a reduction in the search space when solving complex problems. Unlike purely statistical approaches which may require exhaustive exploration of all possibilities, symbolic systems take advantage of the structure of knowledge to eliminate irrelevant branches of research. This allows faster convergence to valid solutions while saving computational resources.

The structured representation of these symbolic systems captures the underlying information precisely and is organised. When solving problems or making decisions, this knowledge structure allows symbolic systems to consider relationships between elements rather than treating each element in isolation. Thus, symbolic systems exploit the rich semantics of symbols to perform more sophisticated inferences and reasoning.

Compositional generalisation is the combining of elements to form new meanings. Symbolic systems are particularly suited to this form of generalisation because they can manipulate symbols and logical rules to construct complex structures from simple elements. Using symbolic representations allows systems to understand how elements fit together to form more significant concepts. This leads to more powerful generalisation, where the system can extrapolate knowledge from limited examples and apply that knowledge to new situations using logical rules and preexisting relationships [START_REF] Lan | Complex Knowledge Base Question Answering: A Survey[END_REF].

Neural systems are designed to process unstructured and complex data. They can analyse information from different sources, such as text, images, videos and tabular data. Thanks to their architecture and ability to learn patterns from training data, these systems can answer questions that require deep understanding and complex analysis.

Heterogeneous data refers to information from various sources and formats. Neural systems are suited to processing this data type because they can integrate and analyse information from different modes. For example, they can extract textual information from documents, interpret images or videos, and combine these different forms of data to produce coherent and informed responses.

KBs are data structures that store information about entities, their attributes, and their relationships. However, these KBs may be incomplete or lack key relationships. Neural systems can help fill these gaps by extrapolating from existing information and generating responses based on their understanding of the data. They can also identify implicit relationships between different entities, improving the quality and richness of available information [START_REF] Zhang | Neural, symbolic and neural-symbolic reasoning on knowledge graphs[END_REF].

NSR represents an approach in artificial intelligence that combines elements of traditional symbolic reasoning with techniques based on neural networks. This combination aims to take advantage of the advantages of each approach to solve complex and varied problems. The generation of logical forms in SA approaches and the optimal expansion of the reasoning subgraph in IR approaches illustrate how this fusion can be applied in the context of KBQA.

SA is concerned with understanding the meaning of words, sentences, and language in general and NSR can be used to generate logical forms that represent the semantic structure of a text. This involves translating the information contained in the text into formal logical representations, such as predicates, propositions, and relationships between entities.

Neural networks can be leveraged to perform the first step in this transformation by identifying text concepts, relationships, and contexts. For example, neural networks such as recurrent neural networks or transformers can be used to extract semantic information from texts. Then, symbolic reasoning techniques, such as first-order logic or modal logic, can be applied to formalise this information into logical forms understandable by a computer [START_REF] Lan | Complex Knowledge Base Question Answering: A Survey[END_REF].

One of the challenges in the field of IR is determining how to extend a knowledge graph or set of relevant relationships to answer a given query optimally.

NSR can guide the expansion of the knowledge subgraph using symbolic information and signals from neural networks. For example, when a query is asked, a neural network can extract contextual information from the query itself and relevant documents. Then, this information can be integrated into a symbolic reasoning framework to guide the search and expansion of the knowledge graph to provide more accurate and relevant results [START_REF] Zhang | Neural, symbolic and neural-symbolic reasoning on knowledge graphs[END_REF].

C. Knowledge Base

The KB and its structure constitute the foundation for understanding and interpreting user requests.

One of the international standards for the definition and exchange of data from digital building models is the Industry Foundation Classes (IFC), the current version of which is IFC 4 ADD1. However, the most used version is the IFC 2X3 TC1 version. There are ifcOWL ontologies for the different versions of IFC made available officially using the EXPRESS-to-OWL tool [START_REF] Pauwels | EXPRESS to OWL for construction industry: Towards a recommendable and usable ifcOWL ontology[END_REF].

The ifcOWL ontology is massive and complex, mainly to meet the needs of the industry with the best coverage in breadth and depth. Thus, numerous works have led to ontologies with narrower scopes and/or simplified structures [START_REF] Pauwels | SimpleBIM: From full ifcOWL graphs to simplified building graphs[END_REF]- [START_REF] Mendes De Farias | IfcWoD, Semantically Adapting IFC Model Relations into OWL Properties[END_REF].

IV. OUR APPROACH

A. Objectives

Complying with existing and future laws and regulations supports the need to have explainability of reasoning and interpretability of results. Moreover, the targeted users, domain experts, need to be confident in the answers provided by our KBQA system. Therefore, we choose an SA approach.

An ontology-guided SA methodology allows for identifying and qualifying the entities once the target instances are imported into the domain ontologies. Accordingly, augmenting the existing industry ontologies must be done to adapt them to process natural language.

Thankfully, such work has been completed and published [START_REF] Yin | An ontology-aided, natural language-based approach for multiconstraint BIM model querying[END_REF]: the proposed IFC Natural Language Expression (INLE) ontology, based on the official IFC version 2X3 TC1, is a precious contribution from the authors.

However, SA approaches tend to have narrow generalisations outside anticipated questions and difficulties handling complex questions. To mitigate these side effects, we choose a different approach to the syntactic and semantic understanding step of SA [START_REF] Yin | An ontology-aided, natural language-based approach for multiconstraint BIM model querying[END_REF] by relying on betterperforming neural networks [START_REF] Lan | Complex Knowledge Base Question Answering: A Survey[END_REF], making our approach part of the NSR family, thus naming it NSR-BIM.

B. Design

The NER phase in [START_REF] Yin | An ontology-aided, natural language-based approach for multiconstraint BIM model querying[END_REF] is done by searching for the presence of all the entities of the ontology in the query, then filtering and disambiguating the terms thus found. We chose to reverse this part by searching only for the terms from the query in the ontology: our approach is more straightforward and faster without presenting any drop in relevance. Our entity search from the question aims to build triples between subjects and objects of the ontologies linked by a predicate. The dependency tree is thus created using an NLP neural network while guided by the ontology, ensuring syntactic and semantic cohesion associated with the explainability and interpretability of the results. This tree serves as the basis for constructing the query on the KB. This dependency tree is then traversed in depth because the entities have relationships in depth instead of in width. Then, the dependency tree stores the branches in subtrees starting on the left. Thus, when a sentence includes nodes with longer branches, the latter are stored in subtrees on the right. To capture the relationships of these sentences stored in righthand subtrees, traversing the tree in depth and to the right is preferable, as opposed to a more conventional traversal to the left. Also, our entity search is designed to traverse the tree only once, starting from the entity considered at the current iteration and going up the tree towards its root to find the best subject and predicate for this entity, which is the object of this triple. When a node is present in the sentence, our entity search also explores the transverse branches and the possibility of a subject-predicate-object triple in a top-down search, where the subject is the entity considered at this stage. These transversal branches are explored in the subtrees on the left since the tree is traversed iteratively in-depth first towards the subtrees on the right.

C. Implementation 1) Tools and applications

Protégé 1 , open-source software from Stanford University, creates, maintains, and edits ontologies. It provides a graphical interface for modelling ontologies using OWL and allows testing inferences and executing SPARQL queries.

Python is chosen as the programming language for its versatility and wide choice of libraries and frameworks (thirdparty and native) in the areas explored. The owlready22 module (GNU LGPL v3 license) is a Python module used for loading, browsing, and modifying ontologies and searching, inferencing, and executing SPARQL queries.

Conda 3 is the open-source package manager that creates isolated Python environments containing packages and dependencies specific to different tools and experiments.

The minimalist and lightweight Flask4 framework is used to develop web services in Python. It provides all the basic elements needed to create lightweight web applications.

Project management and sharing are done via GitHub, Microsoft's online platform using the Git version control system.

Microsoft's Visual Studio Code (VS Code) is the source code editor. It is light, fast, and versatile and notably offers good integration of Python, Conda and Git.

2) Natural language processing

For NLP, the main (open-source) library used is spaCy 5 . Available for Python, it is designed to perform various NLP tasks, such as tokenisation, lemmatisation, NER, parsing, or dependency tree construction. spaCy stands out for its high execution speed and precision in text processing.

NLTK 6 (Natural Language Toolkit) is another popular (open source) NLP library that offers identical functionality to spaCy. NLTK is less efficient than spaCy on many tasks but offers a broader range of functionalities, which makes it possible to test and compare other approaches and, above all, to access functionalities missing from spaCy.

Thus, spaCy allows one to carry out fewer tasks but more efficiently than NLTK, while the latter offers functionalities simply absent from spaCy. They are, therefore, an excellent complement to automatic NLP.

Lastly, the extreme sensitivity of KBQA systems to identifying and qualifying entities has been emphasised [START_REF] Lan | Complex Knowledge Base Question Answering: A Survey[END_REF]. For the very specific and precise task of constructing the dependency tree representing a question, the BeNePar7 (Berkeley Neural Parser) parser is used because it is quite simply the most efficient [START_REF] Kitaev | Constituency Parsing with a Self-Attentive Encoder[END_REF]. Initially developed by the University of Berkeley, it is designed to perform syntactic analysis of sentences using deep neural networks to improve the accuracy of this analysis. It can capture complex syntactic dependencies, allowing exact analysis in several languages. It is integrated with spaCy and NLTK.

3) Ontologies

The formal knowledge representation language used to define ontologies is OWL 2, which allows the modelling of concepts, properties, and relationships between entities. RDF/XML is the serialisation syntax used to represent data when stored as files.

The INLE ontology [START_REF] Yin | An ontology-aided, natural language-based approach for multiconstraint BIM model querying[END_REF] reduces the complexity of the IFC ontology and increases access to building elements via natural language elements. It focuses on 19 architectural and structural elements and 2 spatial elements. The geometry elements are discarded. Standard and specialised natural language elements are associated with the elements of the INLE ontology, with variations (synonyms, hyponyms, acronyms, abbreviations). Moreover, the relationships between these elements are expressed by shorter paths than with the IFC ontology, sometimes using SPIN (SPARQL Inferencing Notation) properties to maintain the correspondence with IFC without unnecessarily burdening the representation scheme. To illustrate the lightweight INLE aspect when compared to IFC, Fig. 2 shows the (rounded) number of components for both schemas, alone and incorporating objects from a duplex building.

The scripts used to populate an INLE RDF/XML file from its IFC counterpart are made publicly available on GitHub8 . SPIN is an extension of SPARQL that allows inference rules and constraints to be described on top of RDF data, thus allowing logical rules to be specified to deduce new information from existing data. As SPIN has been superseded by SHACL (Shapes Constraint Language), most SPARQL engines only support a very restricted subset of SPIN (if any), which forces SPIN rules used in the INLE ontology to be reformulated into SPARQL subqueries.

V. RESULTS

The tests were conducted on minimal questions [START_REF] Berners-Lee | The Semantic Web: A new form of Web content that is meaningful to computers will unleash a revolution of new possibilities[END_REF] like "Find external walls on the floor 2.". They show a relevance of 90%: failure appeared once when using ambiguous terms.

The programs were tested on a computer with an Intel ® i5 CPU (2.5 GHz), 16 GB RAM, and the Windows 10 64-bit system. Importantly, our KBQA system implements straightforward and limited logical relationship detection, semantic relationship extraction, and value restriction extraction, which may partly account for the low execution time when compared to [START_REF] Yin | An ontology-aided, natural language-based approach for multiconstraint BIM model querying[END_REF].

Python has great flexibility and ease of use but remains slow to execute. One solution could be to use Cython, the programming language that allows compiling Python code into C or C++. It helps improve the performance of Python programs by translating them into more efficient machine language. Cython also allows you to add static types and integrate calls to C or C++ functions directly into Python code.

VI. CONCLUSION AND FUTURE WORK

KBQA systems aim to bridge the gap between human language and structured data, allowing users to ask questions in natural language and receive accurate and relevant answers based on the information stored in the KB. These systems involve several steps, including natural language understanding, query generation, NER, relationship extraction, and answer presentation. Therefore, this type of system is ideally suited to meet our objectives.

The major challenges of KBQA systems include handling ambiguous queries, resolving entity references, dealing with incomplete or noisy data, and efficiently integrating information from different sources within the KB.

The recent advances enabled by neural networks and large language models require a complete review of most existing approaches, provoking many questions in the KBQA community and a visible and sometimes radical evolution in recent literature.

In our approach to building a KBQA system to query BIM models, we use a combination of symbolic and numeric AI techniques, with the question parsing done using neural networks and NER and entity linking done using ontologyguided algorithms.

Our approach does not process queries composed of several sentences, so implementing a method for resolving coreferences between sentences is an avenue for improvement. The resolution of constraints also remains a subject of errors: one avenue that could be explored is the construction of alternative branches when parsing the dependency tree, thus making it possible to create alternative SPARQL queries and subqueries to be executed if the previous ones were bound to fail. Besides, logical relationship detection, semantic relationship extraction, and value restriction extraction only handle straightforward use cases. In the future, these modules must be more robust and capable of handling broader use cases.

Once all these improvements have been explored and implemented, we will thoroughly test the accuracy and speed of execution of our approach.

1 .

 1 Thematic analysis for isolation of a subgraph 2. Construction of reasoning instructions by semantic parsing 3. Reasoning on the entities (and their neighbours) of the subgraph 4. Generation of the answer from the classification of candidate answer entities Some systems repeat steps 2 and 3 iteratively.

Fig. 1 .

 1 Fig. 1. Overview of our KBQA system

TABLE I

 I

	.	ONTOLOGIES' CONCEPTS & INDIVIDUALS
		IFC	INLE
		Schema	Duplex	Schema	Duplex
	Axioms	18,000	306,000 6,500	9,200
	Classes	1,100	1,100	150	150
	Predicates	1,500	1,500	60	60
	Individuals	0	80,000	0	7,000

1 https://protege.stanford.edu/

TABLE II

 II

	.	QUERY EXECUTION TIME (S)
			MOP-SP [16]	NSR-BIM (Ours)
	Data extraction to build the KB	170.33	31.90
	Loading RDF BIM data		30	8.52
	NLP preprocessing		8.67	0.01
	NER and hierarchical pairing
	Logical relationship detection Semantic relationship extraction	10.93	0.09
	Value restriction extraction
	Automatic code generation		10	0.02
	SPARQL query execution		0.6	0.55
	Total per single question		30	0.67

https://owlready2.readthedocs.io/en/latest/

https://anaconda.org/anaconda/conda

https://pypi.org/project/Flask/

https://spacy.io/

https://www.nltk.org/

https://pypi.org/project/benepar/

https://github.com/sreynaud-b27/IFC2INLE

ACKNOWLEDGEMENT

We want to thank B27-AI for providing financial and material support for this study, the Faculty of Science and Technology at the University of Burgundy for their academic support, and the anonymous reviewers for their helpful comments.


Bénédicte Lebret
email: benedicte.lebret@inrae.fr

Bénédicte Lebret Pig

published or not. The documents may come

Pig production systems and quality of pork and pork products