International Construction Specialty Conference of the Canadian Society for Civil Engineering (ICSC) (5th : 2015)

A divide-and-conquer algorithm for 3D imaging planning in dynamic construction environments Zhang, Cheng; Tang, Pingbo Jun 30, 2015

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
52660-Zhang_C_et_al_ICSC15_196_Divide_And_Conquer.pdf [ 2.21MB ]
52660-Zhang_C_et_al_ICSC15_196_Divide_And_Conquer_slides.pdf [ 933.13kB ]
Metadata
JSON: 52660-1.0076422.json
JSON-LD: 52660-1.0076422-ld.json
RDF/XML (Pretty): 52660-1.0076422-rdf.xml
RDF/JSON: 52660-1.0076422-rdf.json
Turtle: 52660-1.0076422-turtle.txt
N-Triples: 52660-1.0076422-rdf-ntriples.txt
Original Record: 52660-1.0076422-source.json
Full Text
52660-1.0076422-fulltext.txt
Citation
52660-1.0076422.ris

Full Text

5th International/11th Construction Specialty Conference 5e International/11e Conférence spécialisée sur la construction    Vancouver, British Columbia June 8 to June 10, 2015 / 8 juin au 10 juin 2015   A DIVIDE-AND-CONQUER ALGORITHM FOR 3D IMAGING PLANNING IN DYNAMIC CONSTRUCTION ENVIRONMENTS Cheng Zhang1,3, and Pingbo Tang2 1 School of Sustainable Engineering and the Built Environment, Arizona State University, United States 2 School of Sustainable Engineering and the Built Environment, Arizona State University, United States 3 czhan139@asu.edu Abstract: On construction sites, engineers need real-time geometries of workspaces for reducing spatial conflicts between construction activities, monitoring construction progress, and controlling construction quality. The dynamic nature of construction environments, however, poses challenges to collecting sufficient and high-quality geometric data to support such needs. Effective uses of advanced 3D-imaging technologies also rely on engineers’ experiences. Manual imagery data collection often results in missing or low-quality data or unnecessary over-detailed inspection and exponentially long computation time, which may bring extra cost to construction project. To overcome these challenges of 3D data collection, the study presented in this paper proposes a new automatic 3D imaging planning method for guiding efficient and effective 3D imagery (e.g., LiDAR) data collection in dynamic environments. This method first establishes a sensor model of laser scanners, and then establishes a divide-and-conquer algorithm for achieving rapid and precise 3D imaging planning for dynamic construction site. For a given jobsite, this algorithm creates a graph that represent objects or features having specific data quality requirements (e.g., level of accuracy, and level of detail) as nodes, and spatial relationships between these objects as edges (e.g., distance, line-of-sight). A graph-coloring algorithm decomposes such a graph into sub-graphs for finding their “local” optimal 3D imaging plans. A solution aggregation algorithm then combines those “local” optimal data collection plans into a complete 3D imaging plan for the complete graph representing the scene. Testing results indicate that the divide-and-conquer algorithm can improve the performance and computational efficiency of 3D imaging planning and producing better results than the conventional 3D imaging planning methods. 1 INTRODUCTION In construction projects, failing to acquire timely, detailed, and accurate spatial information for decision-making may cause low quality, low productivity, and accidents. On construction jobsites, one key reason of deficient 3D imaging data collection is the dynamic nature of construction projects. Different tasks involve different construction environments, facilities, construction activities, and objects. Moreover, the specific requirement of field data will be changing even in the same task in different environments during different stages of construction. This dynamic nature of construction projects not only requires a variety of 3D data, but also brings difficulty of efficient and effective spatial data collection. The problem becomes more serious when the users of technologies have limited experiences of using imaging systems in changing workspaces. Bad data collection will cause low quality (missing, inaccurate, or less detailed) data, or unnecessary interference of jobsite activities. Reliable sensing method and timely, comprehensive data collection of spatial data is necessary in dynamic construction projects. 196-1 Compared to traditional inspection methods (e.g. tapes, laser tapes, Global Navigation Satellite System), 3D imaging technologies, such as laser scanning and structure from motion (SFM), is able to provide fast and comprehensive 3D imageries of construction jobsite. However, currently, construction engineers can only manually plan 3D-imaging process based on their intuition or experiences. This experience-based data collection may not effective or efficient, because 3D imaging data collection is a complicated process that involves 3D space domain and time domain configuration, as well as multiple scanner parameters. On one hand, low quality 3D imaging data may impede effective decision making on the site. On the other hand, redundant data collection is wasting time and causing frequent interferences with construction operations during data collection. In addition, hiring an experienced professional for data collection can be very expensive (thousands of dollars per day). An automatic laser-scanning planning method is thus necessary to configure the parameters of laser-scan data collection (e.g. scan position, parameters on the scanner) systematically according to the dynamic construction information needs in a changing environment while maximizing data collection efficiency. The proposed algorithm will help to reduce the cost caused by decision-making error that result in inaccurate inspection, interruption of construction processes by data collection, and training or hiring laser-scanning professionals. 2 BACKGROUND RESEARCH 3D imagery data quality has great influence on the results of data processing (e.g. more precise result of BIM model). One research  provided a sensor model describing how various data collection parameters will influence data quality metrics, e.g. level of detail (TANG and ALASWAD. 2012). Another research proposes a model for estimating edge loss in laser scanned data by considering the impacts of various factors, such as scanning distance, density of data and incidence angle on the edge loss (Tang, Akinci, and Huber 2009). Researchers studied 3D imagery sensor planning problem in order to capture high quality 3D imagery data. Traditional 3D imagery sensor (e.g. LIDAR) planning focuses on fixed sphere planning about a single object(Latimer et al. 2004; Pito 1996; Son, Park, and Lee 2002; Lee, Park, and Son 2001). In mechanics engineering domain, researchers produced an automatic process planning system based on visibility analysis dealing with free form surface (Fernández et al. 2007). On the other hand, fewer researchers focus on sensor planning problem in construction background. One planning algorithm chose sensing locations based on clustered construction information goals and then generated paths to minimize the transit cost between clusters (Latimer et al. 2004). However, this approach did not clearly show the inspection goal and did not take the data quality requirement into consideration (e.g. LOD, LOA). In another sensor planning approach, researchers used 1m3 cubes to represent the construction to obtain the visibility of any cube, and then next-best-view (NBV) scan planning approach could generate the scan positions (Blaer and Allen 2009). This algorithm also ignored data quality and scan efficiency. A third sensor planning research  proposed a scan planning algorithm using the next-best-view idea (Song, Shen, and Tang 2014). The major limitation of directly using next-best-view scan planner was the scan resolution was constant for all the scan positions, which might lead to longer calculation time and redundant data collection in areas where the resolution requirement is low. Therefore, the potential of improving the performance of sensor planning problem in construction area is huge. 3 PROBLEM DESCRIPTION AND TERM DEFINITION OF LASER-SCANNING PLANNING 3.1 Problem Description The goal of 3D imaging planning is to determine positions and scanner parameters of each scan to ensure the collected 3D image meets inspection requirements with optimal time consumption. We can describe the scan planning problem using the following IDEF0 process model, showing in fig.1. The input includes the inspection goals, i.e. specific areas in the jobsite that field engineers need inspect with certain accuracy. The constraints are sensing model of laser scanner, time, cost, and space limits of the dynamic jobsite. The outputs are the scan positions and scan parameters.  196-2 3.4 Feasible Area In our approach, we use the concept “feasible area” to show the relationship between sensor model of laser scanner and the LOD requirement of a feature point. For any given feature point we need to know where to put the laser scanner to acquire point cloud with a required LOD. Thus, the set of qualified scan position is the feasible area of this feature point. To ensure the LOD of every feature point, we need at least one scan position in each feasible area (obviously, we can utilize the overlapping of feasible areas). The definition of feasible area is the area on the ground where to put the laser scanner with given laser scanning resolution 𝛿𝛿𝑣𝑣  & 𝛿𝛿ℎ  so that the collected data of certain feature point will satisfy the LOD requirement. For certain feature point, it is obvious that the higher the laser scanner resolution is, the larger the feasible area is.  Without losing generality, we set the coordinate of a feature point as (0,0,a) while the x-z plane represents the wall. If we put the laser scanner at the point(x,y,h), for vertical LOD requirement we have: [1] 𝑠𝑠𝑣𝑣 =𝛿𝛿𝑣𝑣�𝑥𝑥2+𝑦𝑦2+(𝑎𝑎−ℎ)2��𝑥𝑥2+𝑦𝑦2≤ 𝐿𝐿𝐿𝐿𝐿𝐿 So 2|𝑎𝑎 − ℎ| ∙ 𝛿𝛿𝑣𝑣 is the minimum 𝑠𝑠𝑣𝑣 that we can obtain at this feature point, which comes from the nature of inequality. For horizontal LOD requirement, we have: [2] 𝑠𝑠ℎ =𝛿𝛿ℎ�𝑥𝑥2+𝑦𝑦2+(𝑎𝑎−ℎ)2��𝑦𝑦2+(𝑎𝑎−ℎ)2≤ 𝐿𝐿𝐿𝐿𝐿𝐿 So |𝑎𝑎 − ℎ| ∙ 𝛿𝛿ℎ is the minimum 𝑠𝑠ℎ that we can obtain at this feature point. Fig.4 shows the shape of feasible area of the vertical and horizontal LOD requirement at height=5m, LOD=0.013m (1/2 inch), resolution=1/4:   (a)  (b)  (c) Figure 4: Feasible area of a feature point. (a) feasible area for horizontal LOD; (b) feasible area for vertical LOD; (c) obtaining feasible area of a feature point by intersection (a) and (b) 4 DIVIDE-AND-CONQUER ALGORITHM OF 3D IMAGING PLANNING 4.1 Overview Using the terms defined in previous chapter, we can rephrase the goal of scan planning in dynamic construction site as follows: to determine optimal scan positions and corresponding scan resolution, so that the scans will cover all the feature point with a required LOD.  Previous approaches consider the jobsite as a whole, so the scan resolutions for all scan positions are fixed. In this case, the search area of possible scan positions maybe quadratically larger, leading to longer calculation time. Moreover, applying high scan resolution for less important area may be redundant -5 0 5 105101520-20 -10 0 10 2005101520-5 0 5 1051015196-5 smallest number of colors needed to color the whole graph, which called the 'chromatic number' of the graph, means the least groups to partition the feature point set into without visual confliction. 'Chromatic number' is a heavily discussed topic in modern graph theory and there is multiple coloring algorithm available. Fig.6 shows the idea of grouping feature points according to visibility confliction. Different colors indicate different groups. 4.3 Conquer: Scanning Position Detection and Resolution Configuration in Each Group 4.3.1 Framework The scan position and resolution detection in each group consists of four steps: 1. Determine the sparsest resolution that can scan all the feature points with required LOD. Because we treat the feature points in different group individually, we need to determine the sparsest resolution in current group. Therefore, we can guarantee sensing all feature points in this group. The sparsest resolution is the initial value of the scanning resolution in this group. Due to page limit, we will show the calculation of sparsest resolution for one group in future papers. 2. Use next-best-view (NBV) algorithm to calculate the scan position and resolution. The input of NBV algorithm is the feature point information in this group and the initial resolution. The output of this algorithm is the scan position(s) in this group; the feature points that remain un-scanned in this group (called “garbage”). Section 4.3.2 will discuss next-best-view algorithm in detail. 3. Use higher resolution and check scanning time. The 3D-imaging time of a single scan is the function of resolution. The higher scan resolution means longer scanning time. After calculating scan position(s) with the lowest scan-able resolution, we try higher resolution and process the next-best-view algorithm again check the total scanning time in order to optimize the scan resolution for short scanning time. If we use a higher resolution, we may apply fewer scans and the total scanning time may be shorter than having more scans but using lower resolution. Therefore, if the total scanning time is shortened we repeat this process, until the total scanning time stops shortening.  4. After we process all groups, restore all feature points remain un-scanned as a new group (garbage collection). After generating scan positions in each group, there may be some feature point(s) remain un-scanned called garbage. The reason why we leave some feature points un-scanned is for higher efficiency. For instance, we have 10 feature points in a group. The first scan covers five feature points and the second scan covers four feature points. So there is one feature point remain un-scanned. If we take one more scan just for this feature point, this scan is inefficient. Instead of doing so we consider this remaining feature point as “garbage” and we combine garbage from every group as a new group. Then we can deal with the “garbage” group using next-best-view algorithm.  4.3.2 Next-best-view Algorithm The next-best-view algorithm will generate scanning position according to the resolution needs of feature points. 1. For each feature point, this algorithm will generate feasible area represented by many small squares of 0.5 by 0.5 meter. Every square is a potential scan position. 2. Then we define the temperature of one square as number of feasible areas that overlapping at this square. The heat map visualizes such temperature across all squares of the whole site. The algorithm first chooses the area consisting of squares with the highest temperature as a scan position. If more than one areas have the equally highest temperature, the algorithm will randomly select one. The algorithm then deletes all the feasible spaces that covers the selected area and update the heat map.  196-7 3. After that, the algorithm repeats step 2 in the updated heat map until no more than 7% (empirical) of all feature points left. The positions chosen by such a progressive process will be a scan plan that covers all feature points with satisfied LODs. 4.4 Combine: “Garbage Processing” and Finalizing Scan Configurations Garbage processing deals with a group of feature points consisting of all the remaining feature points from each group using next-best-view algorithm. The framework is the same with section 4.3; however, there are some technical details in difference. “Garbage processing” consists of the following seven steps: 1. Combine feature points remaining un-scanned as a new group 2. Examine whether previous scans has already cover any of the feature points. If so, delete these feature points from the “garbage” group, because the scans in Group A may cover the “garbage” feature points in Group B. 3. Determine the lowest scan-able resolution in “garbage” group. 4. Use the next-best-view algorithm to calculate the scan positions for “garbage” group. If a scan will only cover 2% of total number of feature points, we consider it inefficient and discard this scan. This is a trade-off between data quality and scanning efficiency. In addition, doing this improves the robustness to outlier feature points due to inaccurate data or model. 5. Repeat step 2-3 and process all remaining feature point (either scanned or discarded). 5 CASE STUDY AND DISCUSSION To validate the proposed 3D imaging planning algorithm, we conducted the data collection using the proposed automatic planning method, and compared the quality of the collected data against data collected by an experienced user of laser scanners. This experiment focused on a campus building, ASU McCord Hall. Fig.7 shows the front view photo and google map photo of Arizona State University (ASU) McCord Hall.  (a)  (b) Figure 7: Photos of Arizona State University (ASU) McCord Hall: (a) front view photo, (b) google map photo. 5.1 Feature Point Information Collection The researchers obtained the building information model of ASU McCord Hall and then picked feature points as follows: corner of the walls, corner of the windows and doors because these points contain important geometry information. Knowing the coordinates of these feature point we will know the layout of 196-8 the whole building. Then we manually extract the coordinates of these defined feature points shown in fig.8. Feature point information consists of the 3D coordinates, normal vector, and LOD requirement of each feature point. We set the LOD requirement of each feature point as 25mm (one inch).   (a)  (b) Figure 8: (a) Building information model. (b) Feature points extracted from building information model. 5.2 3D Imaging Planning According to feature point information, the 3D-imaging planning algorithm generated the scan positions and corresponding scan resolutions as shown in fig. 9(a).   (a)  (b) Figure 9: Scan planning result generated by proposed algorithm. In (a) we need to choose one scan position in each colored block, while in (b) we use brown stars to show the chosen scan positions.  In fig.9, red circle means the XY coordinates of all feature points, indicating the layout of the jobsite. Color blocks consisting of colored dots are applicable scan positions. We need to take one scan for each separated color block and the scan positions can be any dots in the block. For saving transportation time, we chose the points that close the building. Considering actual environment, brown stars are the actual scan positions, as shown in fig.9 (b). According to the scan planning algorithm, resolution for all scans are the same, being ½. At last, we scanned the building following the scan plan generated by the algorithm. 196-9 5.3 Comparing the Automatic Laser Scan Planning against Manual Planning  We acquired the point cloud of ASU McCord Hall through data collection and registration. After manually checking the data quality we found: the LOD of 100% of the feature points are under 0.025m (1 inch). Fig.10(a) shows the overall 3D-imaging point cloud of ASU McCord Hall. Fig.10 (b)~(d) show the neighbourhood of four random feature points. We can see from fig.10 that the data quality satisfied both the horizontal and vertical level of detail. On the other hand, in the 3D imaging data following manual planning, we found only 60% feature points are with required LOD. This result shows that automatic 3D imaging planning algorithm will guarantee the collected data quality.  6 CONCLUSION AND FUTURE STUDY This paper propose a 3D imaging planning method, output all scan position and resolution that field engineers can follow to accomplish efficient and effective 3D-imaging data collection. Compared to previous data collection planning method, the new 3D imaging planning algorithm not only satisfy the completeness of data collection, but also focus on guarantee the collected data quality. Evaluation results on a campus building show the effectiveness of the proposed algorithm. The 3D imaging plan generated by the algorithm will lead to high quality data collection without time and labor waste. On the other hand, this paper identified several challenges for the further developments of this scan planning approach: 1) the feature point information generation relies on manual work; also the registration of scanned point clouds is also a manual process, which is time consuming; 2) the algorithm didn’t consider the environment of the jobsite; sometimes the given scan position may not be accessible; 3) we can also integrate the time domain (schedule, or work flow) in to the scanning plan so that the proposed data collection plan will better inform the construction productivity analysis and real-time control. The authors will address these challenges in future studies.  (a)  (b)  (c)  (d) Figure 10: 3D imaging result of ASU McCord Hall. (a) point cloud; (b), (c), and (d) are neighbourhood of three random feature points, showing that the collected data satisfy the LOD requirement (0.025m). 7 ACKNOWLEDGEMENT This material is based upon work supported by the National Science Foundation under Grant No. 1443069 and Grant No.  1454654. NSF's support is gratefully acknowledged. Any opinions, findings, conclusions or recommendations presented in this publication are those of authors and do not necessarily reflect the views of the National Science Foundation. References Blaer, Paul S, and Peter K Allen. 2009. “View Planning and Automated Data Acquisition for of Complex Sites” 26: 865–91.  196-10 Dai, Fei, Aff M Asce, Abbas Rashidi, S M Asce, Ioannis Brilakis, A M Asce, and Patricio Vela. 2013. “Comparison of Image-Based and Time-of-Flight-Based Technologies for Three-Dimensional Reconstruction of Infrastructure,” no. January: 69–79.  Fernández, Pedro, J. Carlos Rico, Braulio J. Álvarez, Gonzalo Valiño, and Sabino Mateos. 2007. “Laser Scan Planning Based on Visibility Analysis and Space Partitioning Techniques.” The International Journal of Advanced Manufacturing Technology 39 (7-8): 699–715. Latimer, Edward, Dewitt Latimer Iv, Rajiv Saxena, Catherine Lyons, Lisa Michaux-smith, and Scott Thayer. 2004. “With Applications to Construction Environments,” no. April: 4454–60. Lee, K.H., H. Park, and S. Son. 2001. “A Framework for Laser Scan Planning of Freeform Surfaces.” The International Journal of Advanced Manufacturing Technology 17 (3): 171–80.  MacKinnon, David, J. Angelo Beraldin, Luc Cournoyer, and Francois Blais. 2009. “Evaluating Laser Range Scanner Lateral Resolution in 3D Metrology.” In , edited by J. Angelo Beraldin, Geraldine S. Cheok, Michael McCarthy, and Ulrich Neuschaefer-Rube, 7239:72390P – 72390P – 11.  Pito, R. 1996. “A Sensor-Based Solution to the ‘next Best View’ Problem.” Proceedings of 13th International Conference on Pattern Recognition. Ieee, 941–45 vol.1. Son, Seokbae, Hyunpung Park, and Kwan H Lee. 2002. “Automated Laser Scanning System for Reverse Engineering and Inspection.” International Journal of Machine Tools and Manufacture 42: 889–97. Song, Mingming, Zhenglai Shen, and Pingbo Tang. 2014. “Data Quality-Oriented 3D Laser Scan Planning.” In Construction Research Congress 2014@ sConstruction in a Global Network. ASCE. Tang, Pingbo, Burcu Akinci, and Daniel Huber. 2009. “Quantification of Edge Loss of Laser Scanned Data at Spatial Discontinuities.” Automation in Construction 18 (8): 1070–83. TANG, Pingbo, and Fahd Saleh ALASWAD. 2012. “Sensor Modeling of Laser Scanners for Automated Scan Planning on Construction Jobsites.” In , 1021–31. 196-11  5th International/11th Construction Specialty Conference 5e International/11e Conférence spécialisée sur la construction    Vancouver, British Columbia June 8 to June 10, 2015 / 8 juin au 10 juin 2015   A DIVIDE-AND-CONQUER ALGORITHM FOR 3D IMAGING PLANNING IN DYNAMIC CONSTRUCTION ENVIRONMENTS Cheng Zhang1,3, and Pingbo Tang2 1 School of Sustainable Engineering and the Built Environment, Arizona State University, United States 2 School of Sustainable Engineering and the Built Environment, Arizona State University, United States 3 czhan139@asu.edu Abstract: On construction sites, engineers need real-time geometries of workspaces for reducing spatial conflicts between construction activities, monitoring construction progress, and controlling construction quality. The dynamic nature of construction environments, however, poses challenges to collecting sufficient and high-quality geometric data to support such needs. Effective uses of advanced 3D-imaging technologies also rely on engineers’ experiences. Manual imagery data collection often results in missing or low-quality data or unnecessary over-detailed inspection and exponentially long computation time, which may bring extra cost to construction project. To overcome these challenges of 3D data collection, the study presented in this paper proposes a new automatic 3D imaging planning method for guiding efficient and effective 3D imagery (e.g., LiDAR) data collection in dynamic environments. This method first establishes a sensor model of laser scanners, and then establishes a divide-and-conquer algorithm for achieving rapid and precise 3D imaging planning for dynamic construction site. For a given jobsite, this algorithm creates a graph that represent objects or features having specific data quality requirements (e.g., level of accuracy, and level of detail) as nodes, and spatial relationships between these objects as edges (e.g., distance, line-of-sight). A graph-coloring algorithm decomposes such a graph into sub-graphs for finding their “local” optimal 3D imaging plans. A solution aggregation algorithm then combines those “local” optimal data collection plans into a complete 3D imaging plan for the complete graph representing the scene. Testing results indicate that the divide-and-conquer algorithm can improve the performance and computational efficiency of 3D imaging planning and producing better results than the conventional 3D imaging planning methods. 1 INTRODUCTION In construction projects, failing to acquire timely, detailed, and accurate spatial information for decision-making may cause low quality, low productivity, and accidents. On construction jobsites, one key reason of deficient 3D imaging data collection is the dynamic nature of construction projects. Different tasks involve different construction environments, facilities, construction activities, and objects. Moreover, the specific requirement of field data will be changing even in the same task in different environments during different stages of construction. This dynamic nature of construction projects not only requires a variety of 3D data, but also brings difficulty of efficient and effective spatial data collection. The problem becomes more serious when the users of technologies have limited experiences of using imaging systems in changing workspaces. Bad data collection will cause low quality (missing, inaccurate, or less detailed) data, or unnecessary interference of jobsite activities. Reliable sensing method and timely, comprehensive data collection of spatial data is necessary in dynamic construction projects. 196-1 Compared to traditional inspection methods (e.g. tapes, laser tapes, Global Navigation Satellite System), 3D imaging technologies, such as laser scanning and structure from motion (SFM), is able to provide fast and comprehensive 3D imageries of construction jobsite. However, currently, construction engineers can only manually plan 3D-imaging process based on their intuition or experiences. This experience-based data collection may not effective or efficient, because 3D imaging data collection is a complicated process that involves 3D space domain and time domain configuration, as well as multiple scanner parameters. On one hand, low quality 3D imaging data may impede effective decision making on the site. On the other hand, redundant data collection is wasting time and causing frequent interferences with construction operations during data collection. In addition, hiring an experienced professional for data collection can be very expensive (thousands of dollars per day). An automatic laser-scanning planning method is thus necessary to configure the parameters of laser-scan data collection (e.g. scan position, parameters on the scanner) systematically according to the dynamic construction information needs in a changing environment while maximizing data collection efficiency. The proposed algorithm will help to reduce the cost caused by decision-making error that result in inaccurate inspection, interruption of construction processes by data collection, and training or hiring laser-scanning professionals. 2 BACKGROUND RESEARCH 3D imagery data quality has great influence on the results of data processing (e.g. more precise result of BIM model). One research  provided a sensor model describing how various data collection parameters will influence data quality metrics, e.g. level of detail (TANG and ALASWAD. 2012). Another research proposes a model for estimating edge loss in laser scanned data by considering the impacts of various factors, such as scanning distance, density of data and incidence angle on the edge loss (Tang, Akinci, and Huber 2009). Researchers studied 3D imagery sensor planning problem in order to capture high quality 3D imagery data. Traditional 3D imagery sensor (e.g. LIDAR) planning focuses on fixed sphere planning about a single object(Latimer et al. 2004; Pito 1996; Son, Park, and Lee 2002; Lee, Park, and Son 2001). In mechanics engineering domain, researchers produced an automatic process planning system based on visibility analysis dealing with free form surface (Fernández et al. 2007). On the other hand, fewer researchers focus on sensor planning problem in construction background. One planning algorithm chose sensing locations based on clustered construction information goals and then generated paths to minimize the transit cost between clusters (Latimer et al. 2004). However, this approach did not clearly show the inspection goal and did not take the data quality requirement into consideration (e.g. LOD, LOA). In another sensor planning approach, researchers used 1m3 cubes to represent the construction to obtain the visibility of any cube, and then next-best-view (NBV) scan planning approach could generate the scan positions (Blaer and Allen 2009). This algorithm also ignored data quality and scan efficiency. A third sensor planning research  proposed a scan planning algorithm using the next-best-view idea (Song, Shen, and Tang 2014). The major limitation of directly using next-best-view scan planner was the scan resolution was constant for all the scan positions, which might lead to longer calculation time and redundant data collection in areas where the resolution requirement is low. Therefore, the potential of improving the performance of sensor planning problem in construction area is huge. 3 PROBLEM DESCRIPTION AND TERM DEFINITION OF LASER-SCANNING PLANNING 3.1 Problem Description The goal of 3D imaging planning is to determine positions and scanner parameters of each scan to ensure the collected 3D image meets inspection requirements with optimal time consumption. We can describe the scan planning problem using the following IDEF0 process model, showing in fig.1. The input includes the inspection goals, i.e. specific areas in the jobsite that field engineers need inspect with certain accuracy. The constraints are sensing model of laser scanner, time, cost, and space limits of the dynamic jobsite. The outputs are the scan positions and scan parameters.  196-2 3.4 Feasible Area In our approach, we use the concept “feasible area” to show the relationship between sensor model of laser scanner and the LOD requirement of a feature point. For any given feature point we need to know where to put the laser scanner to acquire point cloud with a required LOD. Thus, the set of qualified scan position is the feasible area of this feature point. To ensure the LOD of every feature point, we need at least one scan position in each feasible area (obviously, we can utilize the overlapping of feasible areas). The definition of feasible area is the area on the ground where to put the laser scanner with given laser scanning resolution 𝛿𝛿𝑣𝑣  & 𝛿𝛿ℎ  so that the collected data of certain feature point will satisfy the LOD requirement. For certain feature point, it is obvious that the higher the laser scanner resolution is, the larger the feasible area is.  Without losing generality, we set the coordinate of a feature point as (0,0,a) while the x-z plane represents the wall. If we put the laser scanner at the point(x,y,h), for vertical LOD requirement we have: [1] 𝑠𝑠𝑣𝑣 =𝛿𝛿𝑣𝑣�𝑥𝑥2+𝑦𝑦2+(𝑎𝑎−ℎ)2��𝑥𝑥2+𝑦𝑦2≤ 𝐿𝐿𝐿𝐿𝐿𝐿 So 2|𝑎𝑎 − ℎ| ∙ 𝛿𝛿𝑣𝑣 is the minimum 𝑠𝑠𝑣𝑣 that we can obtain at this feature point, which comes from the nature of inequality. For horizontal LOD requirement, we have: [2] 𝑠𝑠ℎ =𝛿𝛿ℎ�𝑥𝑥2+𝑦𝑦2+(𝑎𝑎−ℎ)2��𝑦𝑦2+(𝑎𝑎−ℎ)2≤ 𝐿𝐿𝐿𝐿𝐿𝐿 So |𝑎𝑎 − ℎ| ∙ 𝛿𝛿ℎ is the minimum 𝑠𝑠ℎ that we can obtain at this feature point. Fig.4 shows the shape of feasible area of the vertical and horizontal LOD requirement at height=5m, LOD=0.013m (1/2 inch), resolution=1/4:   (a)  (b)  (c) Figure 4: Feasible area of a feature point. (a) feasible area for horizontal LOD; (b) feasible area for vertical LOD; (c) obtaining feasible area of a feature point by intersection (a) and (b) 4 DIVIDE-AND-CONQUER ALGORITHM OF 3D IMAGING PLANNING 4.1 Overview Using the terms defined in previous chapter, we can rephrase the goal of scan planning in dynamic construction site as follows: to determine optimal scan positions and corresponding scan resolution, so that the scans will cover all the feature point with a required LOD.  Previous approaches consider the jobsite as a whole, so the scan resolutions for all scan positions are fixed. In this case, the search area of possible scan positions maybe quadratically larger, leading to longer calculation time. Moreover, applying high scan resolution for less important area may be redundant -5 0 5 105101520-20 -10 0 10 2005101520-5 0 5 1051015196-5 smallest number of colors needed to color the whole graph, which called the 'chromatic number' of the graph, means the least groups to partition the feature point set into without visual confliction. 'Chromatic number' is a heavily discussed topic in modern graph theory and there is multiple coloring algorithm available. Fig.6 shows the idea of grouping feature points according to visibility confliction. Different colors indicate different groups. 4.3 Conquer: Scanning Position Detection and Resolution Configuration in Each Group 4.3.1 Framework The scan position and resolution detection in each group consists of four steps: 1. Determine the sparsest resolution that can scan all the feature points with required LOD. Because we treat the feature points in different group individually, we need to determine the sparsest resolution in current group. Therefore, we can guarantee sensing all feature points in this group. The sparsest resolution is the initial value of the scanning resolution in this group. Due to page limit, we will show the calculation of sparsest resolution for one group in future papers. 2. Use next-best-view (NBV) algorithm to calculate the scan position and resolution. The input of NBV algorithm is the feature point information in this group and the initial resolution. The output of this algorithm is the scan position(s) in this group; the feature points that remain un-scanned in this group (called “garbage”). Section 4.3.2 will discuss next-best-view algorithm in detail. 3. Use higher resolution and check scanning time. The 3D-imaging time of a single scan is the function of resolution. The higher scan resolution means longer scanning time. After calculating scan position(s) with the lowest scan-able resolution, we try higher resolution and process the next-best-view algorithm again check the total scanning time in order to optimize the scan resolution for short scanning time. If we use a higher resolution, we may apply fewer scans and the total scanning time may be shorter than having more scans but using lower resolution. Therefore, if the total scanning time is shortened we repeat this process, until the total scanning time stops shortening.  4. After we process all groups, restore all feature points remain un-scanned as a new group (garbage collection). After generating scan positions in each group, there may be some feature point(s) remain un-scanned called garbage. The reason why we leave some feature points un-scanned is for higher efficiency. For instance, we have 10 feature points in a group. The first scan covers five feature points and the second scan covers four feature points. So there is one feature point remain un-scanned. If we take one more scan just for this feature point, this scan is inefficient. Instead of doing so we consider this remaining feature point as “garbage” and we combine garbage from every group as a new group. Then we can deal with the “garbage” group using next-best-view algorithm.  4.3.2 Next-best-view Algorithm The next-best-view algorithm will generate scanning position according to the resolution needs of feature points. 1. For each feature point, this algorithm will generate feasible area represented by many small squares of 0.5 by 0.5 meter. Every square is a potential scan position. 2. Then we define the temperature of one square as number of feasible areas that overlapping at this square. The heat map visualizes such temperature across all squares of the whole site. The algorithm first chooses the area consisting of squares with the highest temperature as a scan position. If more than one areas have the equally highest temperature, the algorithm will randomly select one. The algorithm then deletes all the feasible spaces that covers the selected area and update the heat map.  196-7 3. After that, the algorithm repeats step 2 in the updated heat map until no more than 7% (empirical) of all feature points left. The positions chosen by such a progressive process will be a scan plan that covers all feature points with satisfied LODs. 4.4 Combine: “Garbage Processing” and Finalizing Scan Configurations Garbage processing deals with a group of feature points consisting of all the remaining feature points from each group using next-best-view algorithm. The framework is the same with section 4.3; however, there are some technical details in difference. “Garbage processing” consists of the following seven steps: 1. Combine feature points remaining un-scanned as a new group 2. Examine whether previous scans has already cover any of the feature points. If so, delete these feature points from the “garbage” group, because the scans in Group A may cover the “garbage” feature points in Group B. 3. Determine the lowest scan-able resolution in “garbage” group. 4. Use the next-best-view algorithm to calculate the scan positions for “garbage” group. If a scan will only cover 2% of total number of feature points, we consider it inefficient and discard this scan. This is a trade-off between data quality and scanning efficiency. In addition, doing this improves the robustness to outlier feature points due to inaccurate data or model. 5. Repeat step 2-3 and process all remaining feature point (either scanned or discarded). 5 CASE STUDY AND DISCUSSION To validate the proposed 3D imaging planning algorithm, we conducted the data collection using the proposed automatic planning method, and compared the quality of the collected data against data collected by an experienced user of laser scanners. This experiment focused on a campus building, ASU McCord Hall. Fig.7 shows the front view photo and google map photo of Arizona State University (ASU) McCord Hall.  (a)  (b) Figure 7: Photos of Arizona State University (ASU) McCord Hall: (a) front view photo, (b) google map photo. 5.1 Feature Point Information Collection The researchers obtained the building information model of ASU McCord Hall and then picked feature points as follows: corner of the walls, corner of the windows and doors because these points contain important geometry information. Knowing the coordinates of these feature point we will know the layout of 196-8 the whole building. Then we manually extract the coordinates of these defined feature points shown in fig.8. Feature point information consists of the 3D coordinates, normal vector, and LOD requirement of each feature point. We set the LOD requirement of each feature point as 25mm (one inch).   (a)  (b) Figure 8: (a) Building information model. (b) Feature points extracted from building information model. 5.2 3D Imaging Planning According to feature point information, the 3D-imaging planning algorithm generated the scan positions and corresponding scan resolutions as shown in fig. 9(a).   (a)  (b) Figure 9: Scan planning result generated by proposed algorithm. In (a) we need to choose one scan position in each colored block, while in (b) we use brown stars to show the chosen scan positions.  In fig.9, red circle means the XY coordinates of all feature points, indicating the layout of the jobsite. Color blocks consisting of colored dots are applicable scan positions. We need to take one scan for each separated color block and the scan positions can be any dots in the block. For saving transportation time, we chose the points that close the building. Considering actual environment, brown stars are the actual scan positions, as shown in fig.9 (b). According to the scan planning algorithm, resolution for all scans are the same, being ½. At last, we scanned the building following the scan plan generated by the algorithm. 196-9 5.3 Comparing the Automatic Laser Scan Planning against Manual Planning  We acquired the point cloud of ASU McCord Hall through data collection and registration. After manually checking the data quality we found: the LOD of 100% of the feature points are under 0.025m (1 inch). Fig.10(a) shows the overall 3D-imaging point cloud of ASU McCord Hall. Fig.10 (b)~(d) show the neighbourhood of four random feature points. We can see from fig.10 that the data quality satisfied both the horizontal and vertical level of detail. On the other hand, in the 3D imaging data following manual planning, we found only 60% feature points are with required LOD. This result shows that automatic 3D imaging planning algorithm will guarantee the collected data quality.  6 CONCLUSION AND FUTURE STUDY This paper propose a 3D imaging planning method, output all scan position and resolution that field engineers can follow to accomplish efficient and effective 3D-imaging data collection. Compared to previous data collection planning method, the new 3D imaging planning algorithm not only satisfy the completeness of data collection, but also focus on guarantee the collected data quality. Evaluation results on a campus building show the effectiveness of the proposed algorithm. The 3D imaging plan generated by the algorithm will lead to high quality data collection without time and labor waste. On the other hand, this paper identified several challenges for the further developments of this scan planning approach: 1) the feature point information generation relies on manual work; also the registration of scanned point clouds is also a manual process, which is time consuming; 2) the algorithm didn’t consider the environment of the jobsite; sometimes the given scan position may not be accessible; 3) we can also integrate the time domain (schedule, or work flow) in to the scanning plan so that the proposed data collection plan will better inform the construction productivity analysis and real-time control. The authors will address these challenges in future studies.  (a)  (b)  (c)  (d) Figure 10: 3D imaging result of ASU McCord Hall. (a) point cloud; (b), (c), and (d) are neighbourhood of three random feature points, showing that the collected data satisfy the LOD requirement (0.025m). 7 ACKNOWLEDGEMENT This material is based upon work supported by the National Science Foundation under Grant No. 1443069 and Grant No.  1454654. NSF's support is gratefully acknowledged. Any opinions, findings, conclusions or recommendations presented in this publication are those of authors and do not necessarily reflect the views of the National Science Foundation. References Blaer, Paul S, and Peter K Allen. 2009. “View Planning and Automated Data Acquisition for of Complex Sites” 26: 865–91.  196-10 Dai, Fei, Aff M Asce, Abbas Rashidi, S M Asce, Ioannis Brilakis, A M Asce, and Patricio Vela. 2013. “Comparison of Image-Based and Time-of-Flight-Based Technologies for Three-Dimensional Reconstruction of Infrastructure,” no. January: 69–79.  Fernández, Pedro, J. Carlos Rico, Braulio J. Álvarez, Gonzalo Valiño, and Sabino Mateos. 2007. “Laser Scan Planning Based on Visibility Analysis and Space Partitioning Techniques.” The International Journal of Advanced Manufacturing Technology 39 (7-8): 699–715. Latimer, Edward, Dewitt Latimer Iv, Rajiv Saxena, Catherine Lyons, Lisa Michaux-smith, and Scott Thayer. 2004. “With Applications to Construction Environments,” no. April: 4454–60. Lee, K.H., H. Park, and S. Son. 2001. “A Framework for Laser Scan Planning of Freeform Surfaces.” The International Journal of Advanced Manufacturing Technology 17 (3): 171–80.  MacKinnon, David, J. Angelo Beraldin, Luc Cournoyer, and Francois Blais. 2009. “Evaluating Laser Range Scanner Lateral Resolution in 3D Metrology.” In , edited by J. Angelo Beraldin, Geraldine S. Cheok, Michael McCarthy, and Ulrich Neuschaefer-Rube, 7239:72390P – 72390P – 11.  Pito, R. 1996. “A Sensor-Based Solution to the ‘next Best View’ Problem.” Proceedings of 13th International Conference on Pattern Recognition. Ieee, 941–45 vol.1. Son, Seokbae, Hyunpung Park, and Kwan H Lee. 2002. “Automated Laser Scanning System for Reverse Engineering and Inspection.” International Journal of Machine Tools and Manufacture 42: 889–97. Song, Mingming, Zhenglai Shen, and Pingbo Tang. 2014. “Data Quality-Oriented 3D Laser Scan Planning.” In Construction Research Congress 2014@ sConstruction in a Global Network. ASCE. Tang, Pingbo, Burcu Akinci, and Daniel Huber. 2009. “Quantification of Edge Loss of Laser Scanned Data at Spatial Discontinuities.” Automation in Construction 18 (8): 1070–83. TANG, Pingbo, and Fahd Saleh ALASWAD. 2012. “Sensor Modeling of Laser Scanners for Automated Scan Planning on Construction Jobsites.” In , 1021–31. 196-11  3D Imaging Planning for Dynamic Construction JobsiteCheng Zhang & Dr. Pingbo Tang SWARM Lab, Arizona State UniversitySensing, Workflow, Algorithm, Recognition, and Modeling of the Construction SystemsMotivationChallenges of 3D inspection on jobsite:• Interferences of construction workflows• Data quality insurance• Workforce development problem2Reduce cost in three aspects:• Poor decision making • Interruption of construction processes • Laser-scanning professionalsResearch Goal3Analytical data quality model• Multiple factors influence the data qualityHigh computation burden• E.g. 𝐶𝐶10000∗8𝑛𝑛Solution: 2-level simplificationChallenges43D Imaging PlanningInspection targets Data quality requirement Constraints of site and resources Scan positions Scan parameters“Divide and Conquer” algorithmOverview5Data Quality Requirement: Level of DetailHigh LOD Low LOD 6Two metrics • Horizontal LOD • Vertical LODLevel of Detail for Point Cloud7Input: Feature PointsFeature points• Targets of construction inspection• Contain spatial information Two elements • Coordinates of feature points • Normal vector of the surface8Visibility Confliction:• Coverage by a single scan• Multiple rules to check visibility confliction Divide: Visibility Confliction of Feature Points9Feature point clustering: • Follow the visibility confliction relationship• “Vertices coloring” in graph theoryDivide: Feature Point Clustering10In each group:• Overlapping of feasible areas• Determine scanning positions• Delete scanned feature points • Repeat until all feature points scannedConquer: Next-best-view Algorithm11Building information modelASU McCord Hall3D imaging planning • ASU McCord Hall• LOD=1 inchValidation12Generated 3D imaging plan:• Scanning position:• Scanning resolution: 1/2Validation13Data quality checking: LOD of feature points1 inch 1 inch 1 inchValidation14100% feature points with required LODCompare:• Automatic data collection planning results (left) • Manual data collection planning results (right) 60% feature points with required LODValidation15Thank you!Cheng Zhang & Dr. Pingbo Tang SWARM Lab, Arizona State UniversitySensing, Workflow, Algorithm, Recognition, and Modeling of the Construction Systems

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.52660.1-0076422/manifest

Comment

Related Items