UNIVERSITY OF CALIFORNIA SAN DIEGO Automatic Optimization of System Design for 3D Mapping of Archaeological Sites A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Computer Science by Quentin K. Gautier Committee in charge: Professor Ryan Kastner, Chair Professor Manmohan Chandraker Professor Kamalika Chaudhuri Professor Truong Nguyen Professor Laurel Riek 2019 Copyright Quentin K. Gautier, 2019 All rights reserved. The Dissertation of Quentin K.
Gautier is approved and is acceptable in quality and form for publication on microfilm and electronically: Chair University of California San Diego 2019 iii DEDICATION This work is dedicated to my parents who have always pushed me on a path to education, and supported me during my Ph. despite being so far from home. To all of my family and my friends. iv EPIGRAPH When you have eliminated the impossible, whatever remains, however improbable, must be the truth.
Sir Arthur Conan Doyle v TABLE OF CONTENTS Signature Page. v Table of Contents. vi List of Figures. ix List of Tables.
xvii Abstract of the Dissertation. 1 Chapter 1 Low-Cost 3D Scanning Systems for Cultural Heritage Documentation .3 Simultaneous Localization And Mapping .1 Data Collection Sites .1 Measuring point cloud difference .1 Arroyo Tapiado Mud Caves .2 El Zotz Archaeological Site .7 Analysis and Discussion. 29 Chapter 2 FPGA Architectures for Real-Time Dense SLAM .3 FPGA Architectures for Kinect Fusion .1 Dense SLAM Overview .2 Iterative Closest Point (ICP) on FPGA .3 Depth Fusion and Ray Casting .4 Kinect Fusion Running Time .4 FPGA Architectures for InfiniTAM .4 Combining Depth Fusion and Ray Casting .5 Iterative Closest Point (ICP) .5 Experimental Results And Analysis .2 FPGA SoC Design .3 PCIe FPGA Design .4 Real-Time Experiments. 58 Chapter 3 Spector: An OpenCL FPGA Benchmark Suite .1 Breadth-First Search (BFS) .2 Discrete Cosine Transform (DCT) .3 Finite Impulse Response (FIR) Filter .9 Sparse Matrix-Vector Multiplication (SPMV) .5 Design Space Analysis .1 The Least Absolute Shrinkage and Selection Operator (LASSO).
82 Chapter 4 FPGA Design Space Exploration With Hint Data .2 Design Space Exploration (DSE) for FPGAs .4 Hint Data Overview .5 Exploiting Hint Data .1 Directly Using Hint Data .3 Improving Elimination With Hint Data .1 Directly using hint data .4 ATNE with low alpha. 115 Chapter 5 Sherlock: A Multi-Objective Design Space Exploration Framework .3 The Sherlock Algorithm .1 Scope and Definitions .3 Active Learning Results .4 Model Selection Results. 141 viii LIST OF FIGURES Figure 1. Scanning backpack prototype.
On top is the handheld device, containing a light panel, a sensor mount, and a tablet for visualization. On the bottom left is the backpack containing a laptop and a metal frame for better cooling. The bottom right picture illustrate the use of the backpack inside the excavation. From top to bottom: The LiDAR scan of the mud cave, the SLAM scan using RTAB-MAP and Kinect v2, and the same SLAM scan with point-to- point error with the LiDAR scan highlighted (darker shade of red = larger error).
RMSE of the cloud-to-cloud difference between SLAM algorithm results and the LiDAR cloud, for the mud caves site. Trajectory comparison between RTAB-MAP with Kinect v1 and the recov- ered ground truth. The position error is plotted on the SLAM trajectory in meters. Comparison of trajectories with and without loop closure using RTAB- MAP with Kinect v1.
Point-to-point difference between the point cloud from ORB-SLAM with Kinect v1 and the LiDAR point cloud. We show the SLAM cloud with the difference colored on each point. Darker red corresponds to a larger error, which happens in areas with concentrated sensor noise, and areas where the two models differ in geometry. RMSE of the cloud-to-cloud difference between SLAM algorithm results and the LiDAR cloud, for the M7-1 excavation site.
Top view of the trajectory comparison between SLAM results and the re- covered ground truth. The position error is plotted on the SLAM trajectory in meters. 3D model reconstructed in real-time on a DE1 FPGA SoC with the data transmitted from a Google Tango tablet. Each iteration of the algorithm takes the depth map from the RGB-D camera as input, then goes through three steps: ICP, Depth Fusion, and Ray Casting.
The overall process is the same on Kinect Fusion and InfiniTAM. The pre-processing steps only exist in InfiniTAM. Running time of 1 iteration of ICP at full resolution for the major modifi- cations made to the baseline GPU implementation. The modifications are cumulative.
The search kernel is the part of the algorithm that compares every vertex to find corresponding points. The reduction kernel sums the equation matrices for all the points. Design spaces of InfiniTAM running on the DE1 board with the Room benchmark. (a) plots the throughput of the entire application when running the selected algorithm on FPGA; (b) plots the throughput of individual algorithms.
The y axis shows the logic utilization of individual algorithms. Comparison of the average total frame rate between different versions of the application running on the DE1: running on ARM only, or the best versions accelerated on the FPGA. We present the results for different benchmarks. Design spaces of InfiniTAM running on the DE5 board with the Room benchmark.
Comparison of the best frame rate for individual algorithms and the entire application. We compare the best results on both DE1 and DE5 hard- ware setups, including the processor and FPGA results. On the DE5, we use bitstreams implementing either multiple algorithms (ICP+DF+RC / ICP+Combined) or only one (indiv. Our workflow to generate each benchmark and the design space results.
Normalized design space for each benchmark. We plot the inverse logic utilization against the throughput such that higher values are better. The Pareto designs are shown in red triangles. Estimating 3D normals from 3D vertices organized on a 2D map.
The top of the figure shows how the sliding window works in the algorithm. The bottom illustrates how the sliding window can be tuned. In the above figure we have sorted the ground truth designs and plotted them alongside the LASSO model predictions. The worst designs begin on the left and progress toward the best designs on the right.
The Histogram model predicts performance very poorly, and while the logic utilization model appears to follow rather closely for mediocre designs, the most efficient designs are poorly modeled. The opposite is true for Normal estimation: Near-Pareto designs are modeled more accurately than the remainder of the space. Illustration of the concepts of input space and output space that both form a design space. Overview of the original ATNE sampling framework.
ATNE is composed of an initial sampling step performed by the TED algorithm, followed by an iterative active learning process. Overview of our proposed methods to improve the sampling results. We propose to improve the initial sampling with information from the hint data, and we design a hint elimination algorithm to further help the elimination step of ATNE. Example of directly using the hint data to find the Pareto-optimal points.
On the left is the hint space from pre-PnR resource data and GPU performance data. On the right is the ground truth FPGA design space. Strict optimal designs (crosses) and optimal design with a 1% margin (squares) from the hint space are plotted in the FPGA space. They are very different from the true optimal set (triangles).
Directly using the hint Pareto-optimal designs on a different benchmark, using the pre-PnR throughput estimations. Selecting optimal designs from the hint space with a margin of 1% leads to sampling 90 designs. Our hint elimination method. 1) Calculate matrix of design order (pairwise differences between designs on one objective) for known FPGA designs and hint designs.
2) Calculate a simplified correlation between the two. 3) Cluster the hint design order. 4) Apply these clusters to the correlation data. 5) Find clusters containing only the same values and propagate that value to the unknown FPGA data.
Prediction errors (ADRS) for different approaches: using ATNE without hint data, directly using Pareto hint data with GPU performance / pre-PnR estimations / CPU performance. Comparison of the sampling/ADRS tradeoff between the baseline algo- rithm and the method selecting Pareto designs from hint data with various margins. All the results are averaged across all benchmarks. Improvement of modified versions of TED over the original TED in terms of ADRS for 15 and 40 samples.
The results are averaged over all the benchmarks. TEDhpar uses normal TED plus the Pareto hint data, TEDout uses TED on the output hint space, and TEDall uses TED on all the output hint spaces. Improvement of various methods over the baseline ATNE algorithm in terms of ADRS, sampling complexity, and the combined difficulty metric. Here we use α = 0.
(a) uses 40 initial samples and (b) uses 15 initial samples. The results are averaged over all the benchmarks. We test the three modified version of TED and the original, combined or not with the hint elimination algorithm (Elim. Each method is tested with the hint design spaces from GPU, Estimation Throughput, and CPU.
Curves showing the change in ADRS in function of the number of sampled designs, in average over all benchmarks. Each curve is a different algorithm, with α = 0.999 and 40 initial samples. The curves are grouped by hint data type, with the addition of TEDall which uses all hint types. Note that because each curve is an average, and not all runs of the algorithm converge to the same value, the curve can sometimes go up.
Curves showing the change in ADRS in function of the number of sampled designs, in average over all benchmarks, with α = 0.999 and 15 initial samples. Improvement of hint data methods over the baseline ATNE algorithm for α = 0.2, with (a) 40 initial samples and (b) 15 initial samples. Illustration of the difference of performance using Sherlock with two regression models on two benchmarks. Average performance of several algorithms on all the FPGA benchmarks.
We plot the error (ADRS - lower is better) against the percentage of design space sampled. We test Sherlock with multiple regression models. Performance of several algorithms on individual benchmarks. We compute the area under the ADRS curve as a measure of convergence, over the first 30% of design space sampled.
A lower value means that the algorithm reaches a better solution faster. We compare Sherlock with different regres- sion models to other state-of-the-art algorithms. We also compare with our proposed model selection algorithm. Average area under the curve for the benchmarks presented in Figure 5.
We present the arithmetic mean, and the geometric mean to take into account the variability of the results. The values are scaled by 1000 for readability. Performance of the model selection algorithm on two simulated datasets. Calculated mean of the Beta distributions of the two models for the two simulated datasets.
Comparison of the ADRS curves for multiple algorithms on all the FPGA benchmarks. Comparison of the ADRS curves for multiple algorithms on the SLAM benchmarks. Area under the ADRS curve for the first 30% of the design space sampled. 137 xiii LIST OF TABLES Table 1.
RGB-D cameras used in our experiments. Absolute Trajectory Error (APE) and Relative Position Error (RPE) on different combinations of sensors and algorithms. ATE compares the trajec- tories aligned on the first pose only. ATE (aligned) compares trajectories globally aligned.
RPE measures the relative error per 1 meter segments. All values are expressed in meters and averaged over the entire trajectory. ATE and RPE in meters, on the M7-1 excavation. Summary of the knobs for all four algorithms, along with their names used in Section 2.
Comparison of the lowest running times of different kernels running on the DE1 SoC board. Each row compares the algorithm running on the ARM processor of the DE1 (top, in ms) and on the FPGA (bottom, in ms). LASSO analysis of throughput on the DE1 SoC board for the Room bench- mark.
