Scene wireframes sketching for Unmanned Aerial Vehicles

Scene wireframes sketching for Unmanned Aerial Vehicles Roi Santos, Xose M. Pardo, Xose R. Fdez-Vidal CiTIUS, University of Santiago de Compostela. Galicia, Spain Emails: {roi.santos,xose.pardo,xose.vidal}@usc.es Abstract This paper introduces novel insights to improve the state-of-the-art line-based unsupervised observation and abstraction models of man-made environments. The increasing use of autonomous UAVs inside buildings and around humanmade structures demands new accurate and comprehensive representation of their operation environments. Most of the 3D scene abstraction methods use invariant feature point matching, nevertheless some sparse 3D point clouds do not concisely represent the structure of the environment. The presented approach is based on observation and representation models using the straight line segments. The goal of the work is a complete method based on the matching of lines, that provides a complementary approach to state-of-the-art methods when facing 3D scene representation of poor texture environments for future autonomous UAV. Oppositely to other recently published methods obtaining 3D line abstractions, the proposed method features 3D segment abstraction in the absence of a previously generated point based reconstruction. Another advantage is the ability to group the resulting 3D lines according to dierent planes, for exploiting coplanar line intersections. These intersections are used like feature points in the reconstruction process. It has been proved that this method exclusively based on lines can obtain spatial information in the adverse situations when a SIFT-like SfM pipeline fails to generate a dense point cloud. Keywords: 3D abstraction, reconstruction, line-based sketching, UAV. 1. Introduction Modern unmanned aerial vehicles (UAV), commonly known as drones, feature on-board video cameras that stream real time visual information about their environment. These frames captured by UAVs need to be processed to allow a feasible understanding of the environment in real time. Fetching an usable 5 representation of the scene is crucial, and the result compromises the success of ongoing mission specic analysis. A proper representation of the environment eases the programming of autonomous movement routines, by identifying its location in space, nding obstacle-free trajectories, or learning movement routines. In this work, we consider the rst stage of computing structural 3D 10 information for an autonomous drone from its own video captures or, in general, for multiple views of an environment of interest. The vast majority of the current approaches for 3D scene reconstruction are based on point clouds [1]. Commonly, points are matched between pairs of views based on their descriptors, then triangulated [2] to make an initial 15 estimation of their location in 3D space, and nally their poses are adjusted by least squares minimization [3]. We can distinguish three common stages of a reconstruction process: The rst stage is the estimation of camera poses by Structure-from-Motion (SfM), which outputs the estimated camera poses and reconstructed features. The second step is the computationally more ex- 20 pensive Multi-View Stereo (MVS) [4] [5] that can add up to millions of points into a dense cloud. The third stage is intended for post processing, and based on tting more complex 3D elements to the estimated point clouds, including planes [6] [7] or lines [8] [9]. However, these approaches are heavily dependent on the dense point clouds, and will not permit a feasible solution when a dense 25 point cloud is not available. That applies in the case of UAVs, when an on-ight real time reconstruction is required, because expensive adjustments can not be delivered on time, when the video stream lacks high denition, the digital noise is persistent, or the received images have to be converted from an analog video source. Even with the appropriate setup, conditions related to poor texture of 30 2 the surrounding objects, a poor environment illumination, blurring or the lack of sucient available high denition pictures of the scene when the vehicle is moving fast, might compromise the building of a dense cloud. The logical evolution of the environment abstraction from multiple views is to incorporate line-based pipelines that do not require a detailed point-based de- 35 scription of the areas of interest, and are resilient to diculties on the point cloud creation. Point based 3D reconstructions may be accurate when created from high denition frames and after expensive bundle adjustments. Nevertheless, in addition to provide geometrical information richer than interest points, lines and planes do summarize the limits of man-made structures. Besides, coplanar 40 line primitives can be intersected to further reveal spatial information. These advantages make lines a good candidate to team with point feature detectors and descriptors [10] [8] [11]. They oer the possibility of combining individual similarities of pairs of segments, related to strong constraints of parallelism and orthogonality [12, 13], and specially coplanarity constraints [14]. This pa- 45 per exploits the latter ones, and the inlier groups are determined based on the homography between dierent views. The constraint that can be exploited is that the intersection of a pair of coplanar lines, even if it might not resemble a physical point, is still geometrically invariant under perspective projection. Our approach is rooted on line based abstraction in the absence of high 50 density point clouds [15], and it takes advantage of the robustness of a state- of-the-art line matching algorithm that works among pairs of images [16]. The inputs are both the images and the camera intrinsic parameters, and the outputs are both the camera extrinsics and the line based 3D sketch. Line detection and matching algorithms are prone to errors, so the system is designed for out- 55 liers rejection, is robust to changes in illumination conditions, blurring due fast camera movements, and also capable to real-time reconstruction from streamed video. 3 1.1. Problem formulation and our approach A 3D reconstruction, abstraction or spatial sketch is the estimation of the 60 position of singular primitives captured in several images, by using geometrical relationships and minimization adjustments. The rst problem is to lter the geometrical features that have been detected and put them in correspondence among views, and segment them into clusters. The second task is to apply geometrical projection of line endpoints with just two views by assuming a Gaussian 65 noise model for perturbation of their location [2]. The third objective involves adjustment algorithms to fetch all the camera poses and estimate the whole environment abstraction. The forth and last stage is to use the adjusted spatial conguration to improve the abstraction itself, attending to structural properties. The main hypothesis of this work is that straight segments resemble a 70 source of geometrical information that can be employed, independently of dense point clouds, for creating spatial 3D reconstructions. The premise was to use line matchings as the cross-view relationship to develop the abstraction on, oppositely to tting these primitives to described feature points [10]. Our method does not assume any Manhattan conguration, this means that no alignment is 75 performed according to any preferred direction. The model is engineered considering the most common case for UAV of unknown camera poses. Therefore, camera extrinsics are not provided for the line matching process, neither any parameter or limitation for the degrees of freedom that could ease their estimation. Camera pose must also be recovered through an SfM process. On the 80 other hand, just the camera intrinsic parameters and the target images are required for the abstraction. The main result of this work is a set of improvements for the complete sequence of algorithms required for 3D abstraction using lines, mainly focused on extracting the most information from the images. The goal of this work is to obtain a real-time three dimensional representa- 85 tion of a scene by using a limited number of matched straight segments. The optimal abstraction the authors look for is built by meaningful descriptive lines whose resemble the limits of the 3D planes of the scene, avoiding representations of several redundant atomic short segments. In order to assure that 4 we improved the state-of-the-art scene abstraction based on lines, we need to 90 prove: Firstly, the implemented multi-scale line detection, and the structure based matching algorithms are protable in poorly illumined environments and low texture scenes. Secondly, the proposed exploitation of intersections brings valuable information into the least-squares adjustment. For the rst task, the observed lines are rstly detected in frames, and then put in correspondence, 95 dragging outliers during the matching process. Our approach takes advantage of multi-scale line detection and matching [16] to increase the accuracy of the line endpoints triangulation among pairs of line-matched frames. Secondly, our method goes one step ahead in the least squares adjustment of cameras and lines by exploiting geometrical relationships of the coplanar lines. After classifying 100 the spatial lines according to their co-planarity, the intersection of the observed lines are brought into a second run of the least squares adjustment of cameras and lines. 1.2. Related work based on lines Lines need to be detected, and optionally, junctions [17]. Segments can be 105 put in correspondence by characterizing their appearance and structure [18, 19]. Sparse Bundle Adjustment (SBA) is a method for simultaneously optimizing a set of camera poses and visible points, based on minimization of an objective function. The input in the case of lines can be the endpoints of the matched lines or the probability distribution of their location shen2000uncertainty. [20] 110 goes an step forward and brings up the Plücker coordinates 4-parameter representation of lines, for the will of a more suitable least-squares based optimization SBA. They also include the trifocal tensor [21] because they just use lines as inputs. Same as did in [8], where in addition avoided enforcing Plücker constraints to improve the SBA eciency, by employing the Cayley representation of the 115 Plücker coordinates. Their cost function computes the squared re-projection error from the sum of the squared shortest distance from each observed endpoint to the reprojected innite line. Several approaches base the line reconstruction on previous results of a feature point based SfM pipeline. In this group, [22] 5 match these segments to other images according to the distances from their 120 back-projected endpoints to neighboring observed line endpoints. This is also the case of the stereo line reconstruction introduced in [23], based on block matching. This work is able to deal with both lines and feature points, and uses RANSAC for outliers rejection. [10] teamed the accurate feature point detector and descriptor SIFT with a line detection based on LSD [24], and 125 matching based on the mentioned previously run point-based SfM. Camera extrinsics are an input to the algorithm, and are obtained from the third-party feature-point based reconstruction before matching the lines [10]. The limitation is the requirement of a dense SfM reconstruction as a base for the spatial lines abstraction and the camera extrinsics given as inputs. They dene a line 130 cluster as a group of spatial lines discriminated by spatial proximity in the reconstruction, and the segmentation is done by projecting from the input camera poses. They also implemented a cost function for the SBA optimization similar to that presented in [8]. On the other hand there are other approaches based on geometric relationships on the structure of the lines proposing to locate dis- 135 crete point counterparts on a line over dierent views [25]. The present work is framed in the group of studies that are not dependant of feature point based SfM pipelines, and uses 4 parameters for updating the line representation during the non-linear optimization. 1.3. Main contributions 140 We propose a method with a set of improvements over state-of-the-art algorithms for automatic 3D scene abstraction based on lines: 1. The proposed method does not require a dense point cloud. It makes feasible a reconstruction based exclusively on line matchings, performed independently over pairs of images. Our approach estimates camera extrinsics, but does not 145 root the line matching on these spatial projections, preventing the uncertainty from SfM to propagate and merge with the uncertainty related to 2D line detection and matching. Previous reconstruction methods rely on a third party 6 SfM pipeline [23] [10], providing the camera poses and dense point clouds, to base line matching and 3D reconstruction on. 150 2. We propose to segment the set of spatial lines by tting them to dierent planes through RANSAC. The observed intersections of 2D co-planar lines are therefore described according to the observed matched lines. These segmented group of intersections are projected from every camera plane. They are nally included into the cost function for a second SBA run, taking advantage of this 155 accurate source of observed points in correspondence. Most of the published methods are intended for urban environments, where many lines are coplanar. Nevertheless, they do not retrieve additional information from the images according to the spatial structure. Hence, the projected lines use to be the sole primitive input to the cost function for a least-squares minimization. 160 3. Our proposed Line Observation is built by merging independent line matchings over pairs of scale-space images. These groups of matched 2D lines dene unique global entities before the 3D stages of reconstruction, in order to avoid the problem of redundant lines and to reduce the number of matching outliers when dealing with multiple views. On the other hand, some recent methods ver- 165 ify the matching candidates based on their support on neighboring views [10], for later clustering them based on their spatial proximity, instead of performing a global matching of the observed lines individually. This is a source of uncertainty, as the matching criteria is tied to the accuracy of every camera pose that was adjusted with point-based SfM, and used as input. 170 The current implementation include the following dierences compared to the previous methods: 1. The whole set of algorithms is implemented into a ROS node that includes capturing the streamed video from a commercial drone. This allows experimental testing without the requirement of external image processing pipelines. To 175 our knowledge, there are no other line based reconstruction pipelines completely integrated in ROS. It runs on real-time up to approximately 800 × 600 resolution, 7 depending on how many images are stored in the buer for the reconstruction. The illumination conditions and number of edges on the image are also crucial for the processing times. 180 2. The complete sequence of algorithms runs without a human in the loop, and the process goes from the detection of lines to the output of the scene abstraction described by a set of 3D line segments. It can also run in real-time if image resolutions are not big. It must be stressed that several published works employ human assistance, mainly during the line matching stage [26], or need the input 185 of camera poses and an external point feature based SfM pipeline, avoiding the feasibility of a real-time execution [10, 8]. The rest of the paper is structured as follows. A high level overview of our method along with the denitions and problems to solve are presented in Section II. Section III goes through the low level details of the method, explanation of 190 algorithms and the implications. In Section IV, the embedding of intersections of coplanar lines and their contribution to the improvement of the 3D abstraction is described. Experimental results are presented and discussed in Section V. Finally, Section VI presents the main conclusions of this work. 2. High level overview 195 The architecture of the line sketching model comprises three layers as shown in Fig. 1. i) The 2D layer extracts and unies the observed projections of edges from the set of views of a scene, where in general there might be large camera translations and rotations among the dierent views. ii) The 3D abstraction layer builds stereo subsystems for every possible pair of views, which are fed into 200 a rst SBA, that outputs a 3D wireframe-based sketch and the camera poses, valid up to scale. iii) Finally, the optimization layer detects the intersections of the coplanar lines in the sourced images and add them to the least squares optimization for the sake of a more accurate reconstruction. Line detection and matching between pairs of views are performed in the 205 2D layer as described in [16]. Segments that remain unmatched are denitely 8 Figure 1: Flow for the proposed method. discarded. Scene abstraction will be based on these initial pair-wise correspondences of line segments. Given an unordered set of images, related to a set of unknown camera extrinsics Υ ={ Υ1 , Υ2 , Υ3 ,..., ΥM }, the 3D abstraction layer computes the initial 210 estimations for each 3D line segment in the set Γ ={ Γ1 , Γ2 , Γ3 ,..., ΓN }. These are estimated from two or more observed projections, this is why Γi may rstly embed one or more estimations of the 3D line before they are unied into a single estimation. The set of line projections observed in Υ is represented as l ={ l1 1 , l1 2 , ..., l1 N , ..., lM N }. A Line Observation is dened as a subgroup of the set 215 of line observations l that are the projections of the same 3D line Γi . Therefore, Li={l1 i, l2 i, ..., lM i} . The set of Line Observations is denoted by L ={ L1 , L2 , ..., LN }. The 3D line estimations Γ are obtained by linear triangulation of the end- 9 of two curved edges resembling a real straight line. Likewise, some line endpoints are neither well dened in an image, when resembling the edges of shadows, or over-exposed photos. Even with these non optimal conditions, edge segments 365 might be correctly matched on several pairs of view. While this kind of inlier matchings would be welcome in a comparison of matching algorithms, they introduce uncertainty in the location of endpoints set used for the spatial abstraction. The application of the SBA returns the optimized poses of cameras and line segments in 3D, but further improvement can be achieved by exploiting 370 coplanarity constraints. The goal of the optimization layer is to extract structural information from groups of coplanar lines and exploit them to improve the accuracy of camera poses and the placement of 3D lines. This is a novelty of this work, and its main contribution. This approach is rooted on the hypothesis that coplanar 375 line intersections encode accurate geometric information for the reconstruction. The points we are looking for are not just joints of segments touching each other, but also more relevant intersections of the extensions of long structural segments. The point of intersection of coplanar lines is computed on the original 2D 380 input frames, once we have computed the rst 3D line based abstraction as followed in Section 3. The 3D estimations for the lines Γ are tted to a set planes P={P1,P2, ..., Pp} , being p the total number of planes. Two spatial lines Γ1 and Γ2 in Plucker coordinates are coplanar if and only if the reciprocal product of their Plucker coordinates is zero: 385 (ˆ u 1,t1)∗(ˆ u 2,t2) = ˆ u 1·t2+ˆ u 2·t1= 0. (11) The group of coplanar Line Observations Ft , tted to the plane t , contains all their counterparts on all the camera planes extended and intersected. The intersection of the observations lj i and lj ii is denoted as Tj i,ii ={lj i∩lj ii} . The complete group of observed intersections of Ft is Tt . This is expressed right after the rst loop in Algorithm 1. 390 Each element in the set of observed coplanar intersections T is dealt as a 16 point feature described by the pair of Line Observations that originate it, and put in correspondence on all images with counterparts for both original Line Observations. The rst 3D estimations for the intersection points on all images T are obtained by linear triangulation, and denoted with Z . This is done 395 analogously as would be computed with described feature points, as followed in Algorithm 1 inside the second cluster of loops. For this method, every 2D line intersection is eligible to enter the spatial abstraction if and only if it matches a proximity rule and an structural threshold. The rst rule limits the sum of the distances from the intersection to the segments to be less than 1.5 times the sum 400 of lengths of both lines, in order to avoid short segments with inaccurate slope to intersect far from them and with high uncertainty. The second threshold is for the angle drawn by both lines, required to be more than red15 º deg for the sake of accuracy. Finally these estimations are used as input for the SBA. 4.1. SBA with lines and planes 405 The second run of the SBA employs a cost function that inputs the 3D estimations for the line intersections Z , in addition to the previously optimized camera extrinsic parameters and lines. The squared cost that will be used to compute the residuals is expressed in the last cluster of loops in Algorithm 1. For this optimization process, the residuals are computed for each iteration by 410 using the squared cost like a simple problem of feature point reprojection error: {ϵj k}2=d( proj Υj{Zk},Tj k)2, (12) where proj Υj{Zk} is the reprojection of the 3D intersection Zk over the camera plane Υj , and Tj k is the location of the detected intersection in frame j . d(·,·) denotes the 2D Euclidean distance. An estimation of the location of a reconstructed intersections Zk has been experimentally proven to be accurate 415 enough, when verifying the following conditions: 1. Both lines are not parallel, which can be guaranteed using a threshold of θ > π/8 for the intersection angle. In Plucker coordinates, Γa and Γb being 17 Algorithm 1: Line based sketching Data: L , Camera intrinsics Result: Υ , Γ , and T initialization; Pairwise Linear Triangulation for L→Γ for Υj∈Υ do for Γi∈Γ do Add cost function with: {ϵj i}2=d( proj ΥjΓi, Aj i)2+d( proj ΥjΓi, Bj i)2 , with {Aj i, Bj i} ∈ Li observed endpoints of Li on Υj end if j >= 2 then Solve SBA for Υ , Γ end end Fit Γ to several planes P → F for Υj∈Υ do for Ph∈ P do for {lj i,lj ii}h∈ Fh do if {Th={lj i∩lj ii} ∈ T , lj i∥ lj ii, θ(lj i,lj ii)> π/8 } then Add Th for Linear Triangulation end end end end Pairwise Linear Triangulation for T → Z for Υj∈Υ do for Zk∈ Z do Add cost function with: {ϵj k}2=d( proj Υj{Zk},Tk)2 end end Solve SBA for Υ , Z Forward-project L from Υ→ optimized Γ 18 parallel implies: ˆ Γa=±ˆ Γb. (13) 2. The perpendicular distance from a plane to each intersection is not greater 420 than the average perpendicular distance from the planar surface to the lines associated to it: d⊥(Pp,Zk)<1/NpX k d⊥(Pp,Γk), (14) being Γk a 3D line tted to the plane Pp , and Np the number of lines associated to plane Pp . After the convergence of the optimization process, the lines Γ are forward 425 projected from the newly optimized camera planes Υ . The 3D intersections Z can be represented alongside the lines Γ . The implementation has been done in ROS by using C++ and the CERES library 1 for bundle adjustment, and holds real-time performance with a compressed video stream of 640 × 368. 430 5. Experimental results The experimental section of this work is willing to test the proposed line based reconstruction method and compare it against other methods under the same conditions. Our fully automatic approach performs all the processes from image datasets or video frames capture, through line detection and matching, 435 to camera pose estimation and 3D abstraction. This section is willing to prove the following facts: 1. The proposed method, if based exclusively on lines, returns the pose of the cameras and a line-based reconstruction of the scene up to scale. An analysis compares the number of 3D segments against the number of 3D points obtained 440 with a SIFT-based SfM [29]. Based on this point cloud it is computed the result for the method Line3D++ [10], and this line based abstraction is also 1 http://ceres-solver.org 19 compared with the result of the proposed method. In these test cases the proposed method is not using any point-based SfM pipeline, but instead it just employs self detection and matching of lines. These are described in Sec. 5.1. 445 2. The proposed method improves the results of feature point based SfM pipelines in various scenarios. For proving this fact, the presented method is teamed with SfM pipelines based on KAZE. Our results are compared against Ground Truth, and the results obtained by [10]. These tests are followed in Sec. 5.2. 3. The current implementation is able to extract a reconstruction by its own, 450 just requiring the images and the camera extrinsics as input. In this study we have used a set of well known public image datasets [22], [30], [15] . These datasets feature a balanced compromise of line structure combined with large textured elements, it is intended to allow a fair comparison with feature point based reconstruction methods. 455 Camera intrinsics are provided as inputs for each set of views, and every method has to estimate the extrinsic parameters of all the cameras, the location of feature points or the poses of the principal lines dening the structure of the region of interest, and the planes adjusted to these lines, when applicable. We distinguish two kinds of experiments depending on whether the objective 460 is to validate both the camera poses and the 3D line sketch against the ground truth, or just to validate the 3D line sketch. In the rst case the camera poses are estimated altogether with the set of 3D lines, as explained in this paper. Nevertheless, in the second case the employed camera extrinsics are primarly estimated from point-based SfM. The 3D lines obtained with our model are 465 densely discretized into a set of 3D points laying on the line. Then the Hausdor distance is computed from these points to the surface of the ground truth polygonal model. The RMSE of this distance is computed and provided as a measure of the error of the prediction compared against the ground truth. The gures referred from this section show the complete result returned by the algo- 470 rithm, no alteration has been performed by human, and all the lines are shown, including outliers and wrongly posed lines. 20 Method Line detection and matching Depends on cloud First 3D estimation Final result Proposed Appearance and structure [16] NO Linear triangulation SBA Line3D++ [10] LSD and SfM pipeline YES Depends on point cloud SBA Table 1: Overview of evaluated methods In Table 1 the main high level dierences between the proposed method and the method Line3D++ [10] used for the evaluations are overviewed. 5.1. Experiments estimating camera poses and 3D lines 475 In this subsection we are evaluating the implementation of the model strictly as explained in this paper, meaning that the camera extrinsics are estimated right from the matched lines on the images and a solution obtained without using feature points at all. Therefore the images showing a common region of interest are selected from the datasets. The pictures showing just a fraction of 480 this region were also avoided. The selected subsets comprise picture numbers {3-6} from the dataset CUBE [15] , and {0,2,4,5,7} from HALLWAY [15]. The result against the rst subset is presented in Fig. 3. This set is characterized by low resolution and poor illumination. In order to compare this result, the same subset has been used with the VisualSfM [29] SIFT-based SfM pipeline teamed 485 with Line3D++ [10], nevertheless no usable line based result has been obtained with this subset comprised of just 4 low resolution pictures. This is an example of test case for which the proposed method is superior to the competence. Being the line matching based on 2D appearance features, it can still reconstruct the scene on the absence of a thick point cloud. The gure shows 4 estimated camera 490 poses and the line sketch formed by 50 spatial segments. The good tting to the mesh of a cube proves that the proportions are fairly well represented with the proposed method. For the dataset "HALLWAY" [15] the images showing the whole region of interest were selected. The 3D reconstruction is presented in Fig. 4, showing 495 the spatial lines and the estimated cameras. Although a result with more lines are obtained in the original paper [15], this study relies on ground truth line 21 matching among all views. Oppositely, our approach starts with the sole set of pictures and generates geometric data exclusively from the results of line detection and matching algorithms. 500 (a) (b) (c) Figure 3: Comparative results using the proposed method of line-based reconstruction exclusively based on lines. The selected subset from the dataset "BOX" [15] comprises the picture numbers {3-6}.a) Sample from the dataset. b) Result obtained with the proposed method. c) A SIFT-based reconstruction performed with VisualSfM [29] returned an sparse cloud, and therefore this result of Line3D++ [10] presents just 26 unconnected 3D lines, and it is not understandable. Figure 4: Selection of 5 pictures within the dataset "HALLWAY" [15] for the line based reconstruction: It comprises the picture numbers {0,2,4,5,7}. The second picture shows the line based 3D sketch and the 5 cameras estimated exclusively using the output from the line matching algorithm. 5.2. Experiments teaming with feature point descriptors The most dicult scenario for line matching are sets of images featuring a large number of lines embed in an structure of repetitive pattern. Also, most of the ground-truth public datasets we found in the literature are intended for feature point based SfM pipelines. These sets feature wide baselines, large rela- 505 tive distances between pictures, and not all the structural elements are framed on each picture. The ideal dataset for line based reconstruction should include most of the structural elements on every picture, and minimize the number of 22 occlusions. A solution we took for creating the test cases was to pick subsets from these sequences of images that can fairly serve for evaluation and compar- 510 ison. Secondly, matching outliers make dicult the convergence of the SBA of a large datasets. This happens also in the case of employing line intersections, because a single line mismatch can trigger the mis location of multiple intersections. For these cases it is unavoidable to team the pose estimator based on line correspondences with a point-based descriptor. In this study KAZE [31] 515 point feature detector and descriptor is teamed with the proposed method and executed after the line detection and matching stages, and right before the triangulation among views. The addition of this SfM pipeline gives an initial estimation for the cameras, avoiding the increased uncertainty of obtaining it from triangulation of the line endpoints. 520 Having an initial estimation of the cameras allows to set a maximum distance between the cameras for the pairwise line matching to be performed among the respective images. In the implementation, this solution translates into setting a distance threshold between the camera centers for the line matching algorithm to be executed over the respective images. This prevents that the algorithm 525 spend time on the search for line correspondences between two images showing opposite faces of an object, and avoids potential matching outliers due to similar sides of the same man-made object. Additionally, limiting the line matching to close neighboring views drops the total processing time dramatically. The quantitative evaluation of the precision of the method is employing the 530 synthetic dataset Timber-Frame-House [22], for performing two dierent comparative evaluations with the methods Line3D++ [10] and Jain [22]. Results are shown on Table 2, Fig. 5 and Fig. 6. The proposed method returns a 3D line based sketch of the model from as low as 6 images, whereas Line3D++ [10] requires 12 or more images to draw an abstraction that includes the main long 535 structures of the house. Moreover, the number of images required for the model to output all or mostly all the edges visible in the original 3D representation, with fair accuracy, this is represented on Fig. 7. In order to consider a valid reconstruction for this comparison it was also required that most of the 3D seg- 23 ments extend to the whole length of their Ground Truth counterparts, oppositely 540 to feature sequences of atomic short 3D segments. For a resulting sketch, the number of 3D segments correctly represented as an unique entity resembling the whole edge is denoted as P . Quantitative measurements have been performed on the results. Every 3D line is discretized into points, and the measure used to evaluate the precision of a resulting abstraction is the distance between these 545 points and the Ground Truth mesh. The level of subdivisions of the octrees at which this Cloud-To-Mesh distance computation was performed is 3 [32]. The test cases are created looking for the minimum number of images that resulted in a reconstruction comprising most of the lines shown in the Ground Truth dataset. These include both the edges of the polygonal model and the lines 550 present in the texture. In order to capture all the segments of the representation, each test case comprise two groups of pictures, one for the front and the second one capturing the opposite side of the house. The test cases are labeled as S6 , comprising image numbers {6,9,86,46,49,126}, S8 further add two more images {89,129} to the list, S10 includes {8,10,12,88,90,48,50,52,128,130}, and 555 S12 further adds images {92,132} to the latter. The resulting 3D line sketches from both sides of the house are aligned by using common lines. This completed sketch is nally aligned to the Ground Truth in order to measure the precision. The time employed by the proposed method is clearly outperformed by Line3D++ [10]. One of the reasons is the lower number of lines included in 560 the results of the latter one. In the case of Line3D++ [10], the time taken by the required SfM pipeline[29] is added to the amount. The quantitative comparison and Ground Truth evaluation is performed rstly using a low number of images, and then more images are incrementally added. The comparisons performed against S6 and S8 , are shown in Fig. 5. The 565 result proves that the proposed method is able to obtain a number of structures of the house from as low as 6 images, and still holding a decent accuracy. On the other hand, the method Line3D++ [10] returns sparse short segments for both cases. This sparsity complicates the understanding of what the spatial line cloud is resembling, and dicult the alignment to the Ground Truth mesh. 570 24 Note that this method also fails to retrieve any long segment of the house for these test cases. The results for a larger number of images of 10 and 12, using S10 and S12 , are shown in Fig.6. S10 turns out to be the minimal test case to return a complete line-based reconstruction from the original synthetic images by using 575 the proposed model. It is the subset with the minimum number of images required for the method to generate a complete abstraction, meaning that it includes most of the segments resembling the main edges and lines on the original 3D model and texture. It is proved that the proposed method is able to return a greater number of complete segments that resemble the original representation, 580 while holding a level of precision equivalent to the one achieved by the method Line3D++ [10] in this case. For S12 the point cloud obtained by VisualSfM pipeline[29] is dense enough for Line3D++ [10] to generate a fair abstraction, showing completeness and continuity between the segments. The obtained mean values, and the Ground Truth segment count for the 585 mentioned test cases against the two methods are displayed on Table 2. The mean distance to GT mesh is lower for Line3D++ [10] than for the proposed method, mainly because their line poses are estimated based on SIFT-originated point clouds. Nevertheless, the number of 3D segments represented as a whole for the rst three subsets is much lower than in the proposed method, as clearly 590 seen on the images of Fig. 5 and Fig. 6. Fig.8 is included in this subsection for reference, as the result provided by [22]. It is based on Ground Truth camera poses, instead of estimating these from the lines or SfM pipelines. The actual code neither the executables are provided by the authors, so it could not be tested against the proposed method. 595 Nevertheless the shown result gives an idea of the precision achieved by the method, as reference. This result is provided by the authors, altogether with the complete dataset and the used subset, with 72 images. Fig. 7 shows a comparison of the proposed method and [10] based on the same dataset [22], but including a larger number of cameras facing the same 600 region of interest. For this test case we want to put in value that the proposed 25 poses with the observed lines and their coplanar intersections. During the experimental testing we proved that the proposed method performs better than 655 the competition for reconstructing scenarios captured on a reduced number of pictures, with low texture, poor illumination, low resolution or blurring. It was obtained better results than the competition against public datasets with a reduced number of images. This low number of views limited the thickness of the point cloud generated by the SfM pipelines. The competition models 660 were outperformed because they required a point cloud dense enough for a feasible line matching outlier detection, and in order to obtain an accurate estimation for the camera extrinsics. Oppositely, the proposed method was able to reconstruct simple line-based sketches with equivalent precision and number of lines featured in the results of the competition when using larger sets. We can con- 665 clude that our method requires less number of images for obtaining equivalent results than the competition, in terms of quantity of lines and precision of the abstraction. Additional future work might include a more advanced use of the planes in the line based reconstruction of man-made environments. For the implementa- 670 tion in a desktop or laptop computers, all the code is parallelized for CPU, but in the future, some algorithms will benet of the use of GPU implementation. On the other hand, an implementation on a Raspberry Pi is a feasible solution for onboard line based 3D reconstruction during UAV ight. Acknowledgment 675 This work has received nancial support from the Xunta de Galicia through grant ED431C 2017/69 and Xunta the Galicia (Centro singular de investigación de Galicia accreditation 2016-2019) and the European Union (European Regional Development Fund - ERDF) through grant ED431G/08. 32 References 680 References [1] S. Yang, S. Scherer, Direct monocular odometry using points and lines, in: ICRA, 2017, IEEE, 2017, pp. 38713877. [2] R. I. Hartley, P. Sturm, Triangulation, CVIU 68 (2) (1997) 146157. [3] B. Triggs, P. F. McLauchlan, R. I. Hartley, A. W. Fitzgibbon, Bundle 685 adjustmenta modern synthesis (1999) 298372. [4] Y. Furukawa, J. Ponce, Accurate, dense, and robust multiview stereopsis, IEEE PAMI 32 (8) (2010) 13621376. [5] M. Rothermel, K. Wenzel, D. Fritsch, N. Haala, Sure: Photogrammetric surface reconstruction from imagery, in: Proceedings LC3D Workshop, 690 Berlin, 2012, pp. 19. [6] C. Kim, R. Manduchi, Planar structures from line correspondences in a manhattan world, in: ACCV, Springer, 2014, pp. 509524. [7] C. Raposo, M. Antunes, J. P. Barreto, Piecewise-planar stereoscan: structure and motion from plane primitives, in: ECCV, Springer, 2014, pp. 695 4863. [8] L. Zhang, R. Koch, Structure and motion from line correspondences: representation, projection, initialization and sparse bundle adjustment, Journal of Visual Communication and Image Representation 25 (5) (2014) 904915. [9] B. Micusik, H. Wildenauer, Structure from motion with line segments under 700 relaxed endpoint constraints, Int. J. Comput. Vis. 124 (1) (2017) 6579. [10] M. Hofer, M. Maurer, H. Bischof, Ecient 3d scene abstraction using line segments, CVIU 157 (2017) 167178. [11] X. Zuo, X. Xie, Y. Liu, G. Huang, Robust visual slam with point and line features, arXiv preprint arXiv:1711.08654. 705 33 [12] B. Micusik, J. Kosecka, Piecewise planar city 3d modeling from street view panoramic sequences, in: CVPR 2009. IEEE Conference on, IEEE, 2009, pp. 29062912. [13] A. Criminisi, I. Reid, A. Zisserman, A plane measuring device, Image and Vision Computing 17 (8) (1999) 625634. 710 [14] H. Kim, S. Lee, Simultaneous line matching and epipolar geometry estimation based on the intersection context of coplanar line pairs, Pattern Recognit. Lett. 33 (10) (2012) 13491363. [15] C. J. Taylor, D. J. Kriegman, Structure and motion from line segments in multiple images, IEEE Trans. Pattern Anal. Mach. Intell. 17 (11) (1995) 715 10211032. [16] J. López, R. Santos, X. R. Fdez-Vidal, X. M. Pardo, Two-view line matching algorithm based on context and appearance in low-textured images, Pattern Recognit. 48 (7) (2015) 21642184. [17] G.-S. Xia, J. Delon, Y. Gousseau, Accurate junction detection and charac- 720 terization in natural images, Int. J. Comput. Vis. 106 (1) (2014) 3156. [18] B. Fan, F. Wu, Z. Hu, Robust line matching through linepoint invariants, Pattern Recognit. 45 (2) (2012) 794805. [19] N. Xue, G.-S. Xia, X. Bai, L. Zhang, W. Shen, Anisotropic-scale junction detection and matching for indoor images, IEEE Trans. Image Process. 725 27 (1) (2018) 7891. [20] A. Bartoli, P. Sturm, Structure-from-motion using lines: Representation, triangulation, and bundle adjustment, CVIU 100 (3) (2005) 416441. [21] R. I. Hartley, A. Zisserman, Multiple View Geometry in Computer Vision, 2nd Edition, Cambridge University Press, ISBN: 0521540518, 2004. 730 34 [22] A. Jain, C. Kurz, T. Thormählen, H.-P. Seidel, Exploiting global connectivity constraints for reconstruction of 3d line segments from images, in: CVPR, 2010 IEEE Conference on, IEEE, 2010, pp. 15861593. [23] T. Koletschka, L. Puig, K. Daniilidis, Mevo: Multi-environment stereo visual odometry, in: IROS 2014 IEEE/RSJ International Conference on, 735 IEEE, 2014, pp. 49814988. [24] R. G. Von Gioi, J. Jakubowicz, J.-M. Morel, G. Randall, Lsd: A fast line segment detector with a false detection control, IEEE Trans. Pattern Anal. Mach. Intell. 32 (4) (2010) 722732. [25] S. Ramalingam, M. Antunes, D. Snow, G. Hee Lee, S. Pillai, Line-sweep: 740 Cross-ratio for wide-baseline matching and 3d reconstruction, in: Proceedings of the IEEE Conference on CVPR, 2015, pp. 12381246. [26] M. Hofer, M. Maurer, H. Bischof, Line3d: Ecient 3d scene abstraction for the built environment, in: German Conference on Pattern Recognition, Springer, 2015, pp. 237248. 745 [27] D. Nistér, An ecient solution to the ve-point relative pose problem, IEEE transactions on pattern analysis and machine intelligence 26 (6) (2004) 756 770. [28] N. Snavely, S. M. Seitz, R. Szeliski, Photo tourism: exploring photo collections in 3d, in: ACM transactions on graphics (TOG), Vol. 25, ACM, 750 2006, pp. 835846. [29] C. Wu, et al., Visualsfm: A visual structure from motion system. [30] T. Werner, A. Zisserman, Model selection for automated architectural reconstruction from multiple views, BMVC, 2002, pp. 5362. [31] P. F. Alcantarilla, A. Bartoli, A. J. Davison, Kaze features, in: ECCV, 755 Springer, 2012, pp. 214227. [32] DGM, http://www.cloudcompare.org (2015). 35