CIB Student Chapter
Department of Building and Real Estate
The Hong Kong Polytechnic University

A Derivative-free Optimization Approach
for Automated As-built 3D Modelling
F Xue

RAP
Dept of REC, HKU
18 August 2017

Outline
1

Background & Opportunity

2

As-built Modeling via Optimization

3

Discussion & Future Research

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

2

Section 1

BACKGROUND & OPPORTUNITY

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

3

1.1 As-built 3D modeling of civil infrastructures
 As-built models [1]
 Increasingly important for AEC/FM
o Construction management
o Facility management

o Built env. conservation

An example of photogrammetry: Kowloon Wall City
(Source: patrick-@sketchfab.com)

o Business with VR/AR, etc.

 See as-planned, as-designed, as-demolished BIM[2]

 Popular technologies (surface modeling)
 Photogrammetry (videogrammetry)

An example of point cloud: Pompei City
(Source: MAP-Gamsau lab, CNRS, France)

 Point cloud
 3D Geographic information system
 Others (statistical rules, deep learning [3], etc.)
F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

: Architecture, Engineering and
Construction/ Facilities Management

An example of GIS-based: 3D Berlin
(Open Data, source: berlin.de)

4

1.1 Final goal: Semantically rich as-built BIM
 BIM (building information model, narrow sense)[2]
 The digital representation of physical and functional

characteristics of a facility
 A shared knowledge resource for information about a facility

serving as a reliable basis for decisions making

 Two types of semantic information in BIM[2, 4-5]

A word cloud of BIM
(Source: advenser.com)

 Attributes of an individual construction component
o geometric (e.g., size, position, shape, & textures)
o non-geometric (e.g., type, material, & functions)

 Relationships between components

o E.g., dependency, topology, and joints

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

An evolution view of CAD model/BIM [6]

5

1.1 Final goal: Semantically rich as-built BIM
 Semantically rich as-built BIM
 Actual building geometries, current function, real topology, etc.
o In addition to the surface of the building envelope

 Advancing the knowledge frontiers of
o Smart city applications

o Heathy aging scenarios

o Robotics and computer vision
o Artificial intelligence, etc.

 Downward compatibility

o Methods and technologies should also work

with as-built 3D building models

Semantics and artificial intelligence (Source: artint.info)

 Relating standards

o LOD (CityGML level of details[7]), IFC[8], etc.

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

6

1.2 The (semi-)automated modeling methods
 Two categories of methods (for both)
 Data-driven: On (pre-processed) point clouds or images
o Poisson mesh surface, RANSAC planes/spheres, edge detection, image segmentation, etc.

 Model-driven: Recognizing & fitting the known (BIM) components against the data

o Evolutionary fitting of components, context-based region growing, VR of pipes/ribbons…

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

7

1.2 The limitations
 Limitations of existing methods
 Data-driven
o Unsatisfactory semantic/abstraction discovery

Huge model size

o Automation level of modeling

Tedious and error-prone manual work

o High requirement on measurement data

Expensive equipment

 Model-driven

o Ad-hoc project setting/ context

Poor reusability

 Thinking out of the box

 Exposing the modeling process to general decision science/OR study
F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

8

1.3 Derivative-free Optimization in OR
 Optimization (a.k.a. Mathematical programming)
 the selection of a best element (with regard to some criteria)

from some set of available alternatives.

𝐦𝐦𝐦𝐦𝐦𝐦 𝑓𝑓: ℝ𝑛𝑛 ⟼ ℝ
An example of optimization

 Nonlinear optimization
 When objective function or some constraints are nonlinear

 Derivative-free Optimization (DFO) [9]
 Objective function or constraints are unknown
o E.g., model selection, parameter tuning in simulations

o Especially when function is very expensive or unanalyzable

DFO: Manipulating a black-box
(Figure adapted from Wikipedia)

 Challenging (NP-hard), but achieved significant success

o In applied science and engineering such as molecular biology

and material sciences

: Operations Research

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

9

1.3 Derivative-free Optimization methods
 A long list of off-the-peg algorithms
for solving optimization problems
as a black-box:
 Surrogate methods
o CMA-ES (Covariance matrix adap-

tation with evolution strategy) [11]
and its variants are competitive

 Trust-region methods

 Metaheuristics (GA, PSO, VNS, etc.)
 Hyper-heuristics, data mining
 … and Monte Carlo
Comparison of algorithms for BBOB-2009 (Black-Box Optimization
Benchmarking, higher is better) [10]
F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

10

1.4 An opportunity
 The questions
 Can the model generation be generally solved by DFO methods?
o If true, can semantic data be discovered at the same time?

 If all true, we can

AEC/FM
As-built
model
generation

 Map between a typical problem in AEC/FM and a class of

powerful algorithms in OR
o Also expose as-built model generation to many other

nonlinear methodologies

 Discover semantic (abstraction) information

DFO

OR
F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

11

Section 2

AS-BUILT MODELING AS OPTIMIZATION

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

12

2.1 A meta-model of as-built 3D modeling
 Given a reference measurement, a set of parametric
components
 A meta-model of constrained optimization is from such
a formulation:
Tells computers:
What to change
What is good

Rules to follow

 The variables (X ) are the parameters of the components;

𝐦𝐦𝐦𝐦𝐦𝐦 𝑓𝑓 𝑋𝑋

𝐬𝐬. 𝐭𝐭. 𝐶𝐶(𝑋𝑋) ≤ 0

Meta-model of constrained
optimization & its solution space

???

 The objective function ( f ) is to maximize the similarity (or

minimize dissimilarity) between the 3D model (as combinations
of the parametric components) and the measurement; and

 The constraints (C ) over the variables are the topological

relationships between components.

 Meta-: Abstraction

 from Greek prefix μετά-, “beyond”
F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

Reference
measurements

Parametric (&
semantic)
components
13

2.1 The framework: A bird’s-eye view
 The full framework (using photo measurement as an example)
 Input 1: Reference measurements (photos)
 Input 2: Semantic and parametric components
 Process: Systematically finding the fittest model by solving meta-model with DFO methods
 Output: A semantic as-built model

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

The overall framework of optimization-based modeling

14

2.1 Formulation of the meta-model
 The variables
 Xi = <cl, l, s, rz> for each i-th component instance
o cl: class, l: location, s: scaling, rz: rotation-z

 The objective function[12] (similarity between A & Â)
 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆 = 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 · 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 · 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐 =

(

)

2
1 n ˆ
 Similarity = 1 - MSE = 1 − ∑ Ai -Ai
n i=1

(2𝜇𝜇Â 𝜇𝜇A +𝑐𝑐1 )(2𝜎𝜎ÂA +𝑐𝑐2 )

2 +𝑐𝑐 )(𝜎𝜎 2 +𝜎𝜎 2 +𝑐𝑐 )
(𝜇𝜇Â2 +𝜇𝜇A
1
2
A
Â

 The constraints

 C(X) = {CI(Xi)}∪{CR(Xi, Xj), i≠j},
o CI : about individual component Xi

o CR : the topological relationships between any (i-th, j-th)

components

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

Restructuring and formulation

15

2.1 Details of the topological relationships
 Topological relationships
 Categories
o Adjacency: ON_TOP_OF, BELOW, NEXT_TO, …
o Separation: SEPERATED

o Containment: CONTAINS_ON, CONTAINS_IN
o Intersection: INTERSECTS_WITH
o Connectivity: CONNECTS_TO

 Semantic definition

 Adding properties like scaling and topological relationships to

An example of the dictionary of
component in SketchUp

their SketchUp dictionaries
o E.g., ON_TOP_OF, BELOW, CONTAINS_ON, etc.
F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

16

2.2 A pilot: A demolished building at campus
 The pilot case
 A demolished baroque-style two-storey building
o Once occupied by School of Tropical Medicine and School of

Pathology, HKU

 Input: A photo

 Preparing parametric components

A historical photo (Source: MTR
HKU Station, re-photographed by
an Android phone)

 Only apparent (>1m) components
o 1 door portico, 1 tree (unknown type), 2 storeys of walls (…)
o 5 identical windows on 1/F, 4 on G/F (all unknown types)

 7 components were collected from 3D Warehouse of SketchUp
o With a keyword filter “baroque”

o With limited (3) pairs of conflicting components
o Adjustment: Removing extra parts, alignment

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

 Door portico
 Tree × 2
 Wall × 2
 Windows × 2

(Contributors: Mohamed EL Shahed, Richard,
KangaroOz 3D, Yoshi Productions, 3dolomouc,
Architect, Ben @ 3D Warehouse)
17

2.2 The problem
 Meta-model of as a constrained optimization problem
 Minimize the dissimilarity
o Between the projected image of model and the input photo
o Similarity metric is the SSIM

 With respect to topological constraints

min f = SSIM
s.t. Semantic constraints
of position, scaling, and
ABOVE/ BELOW/
CONTAINS_ON for each
component

 Computational functions implemented on SketchUp (2016 Pro)

Ruby API
o Objective function interface

o Variables as parameters (per component)

Manifolds (0, 1) + scaling (xyz) + location (xyz) + rotation
(αβγ) = 4 ~ 6 variables

o Constraints of topological relationships

 An invisible Ground object is placed at first
F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

18

2.2 A computational experiment
 Automated generation
 200 trials per target component
 Two phases:
o Incremental (11,000 trials)
o Refinement (3,500 trials)

 The Solver: CMA-ES (C++

code [13] in a Ruby wrapper)
 Time: 5,012.6s

 Observation
 Fully automatic
 Fault-tolerant (see the windows) The automated optimization process of the proposed method with annotated SketchUp models in
 Semantic/grammar-enhanced
F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

the test with 500 trials for fitting each component (The incremental generation phase: 1~11,000;
The fine-tuning phase: 11,001~14,500)
19

2.2 Results and post-processing
 Obtained
 The facade in the photo
 Semantic links

 Post-processing
 Manual completion
o Copy & paste

 Georeferencing and

(a) Direct result: The façade in the photo

(b) The semantic links illustrated in Stanford
Protégé (Circle denotes a component class and a
diamond stands for an instance/object)

display in 3D

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

(c) Manually completed approximate model (~15 minutes) (d) Georeferencing and illustration on Google
Earth, near MTR Exit A (~5 minutes) 20

2.2 The number of trials is critical
 When increasing the number of
trials per component 10 to 1,000
 both the similarity and overall time

cost were monotonically increasing
 Similarity
o From 0.16 to over 0.24

 Correct components

o From 4~5/13 to 12/13

 Time cost: From 100+s to 10,000+s
o Over 97% was consumed by

BIM environment

1. Manipulations
2. Projections

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

The trends of similarity, overall time cost, and correctly generated components
when changing the trails of CMA-ES for fitting each component

Used by
Functions
SketchUp Manipulating components; 3D to 2D projection
Similarity Computing the image similarity index
DFO
Optimizing the parameters of a component
System
Reading/writing of temporary image files

%time
97.67%
1.45%
0.00%
0.88%
21

3.3 COBIMG & live demonstration
 A library COBIMG (constrained optimization-based BIM
generator) is under development
 A shared computational library with specific plugins for
o SketchUp, Revit (soon), etc.

 Multiple meta-models with various
o Objective functions

o Measurement types, and
o Solving algorithms

 Multiple modeling options

One click
COBIMG

o Ontology-guided, free discovery, finetuning, etc.
o Extended the earlier pilot study

 Demo (Known sum of types for a quick demo)
F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

22

Section 3

DISCUSSION & FUTURE RESEARCH

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

23

3.1 Discussion
 Meta-modeling of as-built 3D modeling as constrained optimization
 Pros: General, simple, no explicit object recognition/segmentation (also challenging)
 Cons: A larger search space (slower), slow full projection, limited by pixels, less accurate

 Semantic definitions of components
 Pros: Realized ‘grammar’ of components, simplified optimization
 Cons: Some manual work needed, subject to redefinition from a project to another

 The framework as a whole
 Pros: High automation, linearly incremental time, reusing components and abstractions,

less requirements on equipment, tolerant to errors, (hopefully) semantically rich
 Cons: Less accurate in geometry, still in its infancy
 Answers to the question: 1) True; 2) Applicable to some relations
o Semantic recognition/segmentation is another pillar for semantic BIM

F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

24

3.2 Future research
 Effectiveness
 More domains (e.g. infrastructures, etc.)
 Advanced DFO methods
 More objective functions
 On real BIM/CIM models instead of surface models

 Efficiency

We are still on the way (Source: clipartpanda.com)

 Efficient ways of manipulating point clouds (working…)
o E.g., kd-tree, approximate kNN, convex hull, planar and object

detection

 Extensions

 Shared component libraries for reusability (e.g., IFC-compatible)
 Handling other challenging AEC/FM problems
F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

The Roman aqueduct Pont du Gard
(Source: Wikipedia/ 3Dwarehouse.com) 25

References
[1] Volk, R., Stengel, J., and Schultmann, F. (2014). Building Information Modeling (BIM) for existing buildings—Literature review and future needs.
Automation in Construction, 38: 109-127.
 [2] National Institute of Building Sciences (NIBS). (2015). National Building Information Modeling Standard. Available at:
https://www.nationalbimstandard.org/, retrieved on Mar 8, 2017.
 [3] Patraucean, V. (2016). Deep machine learning: key to the future of BIM? Cambridge: University of Cambridge, Mar 14 2016. Accessed July 15
2016. http://www-smartinfra structure.eng.cam.ac.uk/news/viorica-patraucean-featured-in-infrastructure-intelligence-.
 [4] Eastman, C. M., Teicholz, P., Sacks, R., and Liston, K. (2011). BIM handbook: A guide to building information modeling for owners, managers,
designers, engineers and contractors. John Wiley & Sons.
 [5] Belsky, M., Sacks, R., and Brilakis, I. (2016). Semantic enrichment for building information modeling. Computer‐Aided Civil and Infrastructure
Engineering, 31(4), 261-274.
 [6] Penttilä, H. (2007). Early architectural design and BIM. Computer-Aided Architectural Design Futures (CAADFutures) 2007, 291-302.
 [7] Gröger, G., and Plümer, L. (2012). CityGML–Interoperable semantic 3D city models. ISPRS Journal of Photogrammetry and Remote Sensing, 71,
12-33.
 [8] Venugopal, M., Eastman, C. M., Sacks, R., and Teizer, J. (2012). Semantics of model views for information exchanges using the industry
foundation class schema. Advanced Engineering Informatics, 26(2), 411-428.
 [9] Conn, A. R., Scheinberg, K., and Vicente, L. N. (2009). Introduction to derivative-free optimization. MPS-SIAM book series on optimization (Vol.
8). SIAM.
 [10] Auger, A., Finck, S., Hansen, N., and Ros, R. (2010). BBOB 2009: Comparison tables of all algorithms on all noisy functions (PhD thesis,
INRIA).
 [11] Hansen, N., and Ostermeier, A. (2001). Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9 (2): 159195.
 [12] Wang, Z., Bovik, A. C., Sheikh, H. R., and Simoncelli, E. P. (2004). Image quality assessment: from error visibility to structural similarity. IEEE
Transactions on Image Processing, 13 (4): 600-612.
 [13] libcmaes, an open source library, Version 0.9.5, available at: https://github.com/beniz/libcmaes


F Xue: Auto as-built 3D modeling, HK PolyU, 17 Aug 2017

26

Thank You !