Citation
Automatic range image registration using hierarchy levels and feature recondition filters

Material Information

Title:
Automatic range image registration using hierarchy levels and feature recondition filters
Creator:
Alonso, Alejandro Daniel ( author )
Place of Publication:
Denver, Colo.
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
1 electronic file (92 pages). : ;

Thesis/Dissertation Information

Degree:
Master's ( Master of Science)
Degree Grantor:
University of Colorado Denver
Degree Divisions:
Department of Computer Science and Engineering, CU Denver
Degree Disciplines:
Computer Science
Committee Chair:
Choi, Min-Hyung
Committee Members:
Alaghband, Gita
Gethner, Ellen

Subjects

Subjects / Keywords:
Image registration ( lcsh )
Multimedia systems ( lcsh )
Multilevel models (Statistics) ( lcsh )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Review:
There are numerous approaches that solve the registration problem; from the extensive exploration of the range images' degrees of freedom to the most commonly used ICP. However ICP is only able to work correctly when the images are closed enough to the correct position. Another problem is the pairwise nature of registration, meaning that each corresponding range image match must be known beforehand for a complete batch of scans. This work proposed a novel approach that is able to align a set of unordered range images without knowing the correspondence be=tween then to the point that ICP is able to succeed in its optimization. Consisting of a multilevel hierarchical structure parallel to the ones used in collision detection problems this work aims to reduce unnecessary processes in registration pipeline by simplifying the point clouds and evaluating and filtering possible matches at the different levels of hierarchy as well as filtering possible matching points by comparing surface descriptors. The results found from the experiments conducted to the proposal verify both numerically and visually that the outcomes are effectives with real and virtual range images.
Thesis:
Thesis (M.S.)--University of Colorado Denver. Computer science
Bibliography:
Includes bibliographic references.
General Note:
Department of Computer Science and Engineering
Statement of Responsibility:
by Alejandro Daniel Alonso.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
891088653 ( OCLC )
ocn891088653

Downloads

This item has the following downloads:


Full Text
AUTOMATIC RANGE IMAGE REGISTRATION USING HIERARCHY LEVELS
AND FEATURE RECOGNITION FILTERS
by
ALEJANDRO DANIEL ALONSO
B.S.Instituto Tecnologico y de Estudios Superiores de Monterrey2009
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science
2013


This thesis for the Master of Science degree by
Alejandro Daniel Alonso
has been approved for the
Computer Science Program
by
Min-Hyung Choi, Chair
Gita Alaghband
Ellen Gethner
11/13/2013


Alonso, Alejandro, Daniel (M.S., Computer Science)
Automatic Range Image Registration Using Hierarchy Levels and Feature Recognition
Filters
Thesis directed by Professor Min-Hyung Choi.
ABSTRACT
There are numerous approaches that solve the registration problem; from the extensive
exploration of the range images degrees of freedom to the most commonly used ICP.
However ICP is only able to work correctly when the images are close enough to the
correct position. Another problem is the pairwise nature of registrationmeaning that
each corresponding range image match must be known beforehand for a complete batch
of scans. This work proposes a novel approach that is able to align a set of unordered
range images without knowing the correspondence between them to the point that ICP is
able to succeed in its optimization. Consisting of a multilevel hierarchical structure
parallel to the ones used in collision detection problems this work aims to reduce
unnecessary processes in registration pipeline by simplifying the point clouds and
evaluating and filtering possible matches at the different levels of hierarchy as well as
filtering possible matching points by comparing surface descriptors. The results found
from the experiments conducted to the proposal verify both numerically and visually that
the outcomes are effective with real and virtual range images.
The form and content of this abstract are approved. I recommend its publication.
Approved: Min-Hyung Choi


DEDICATION
I dedicate this work to my parents who have given me this great
opportunity of studying abroad. And especially to Alejandra Sanchez for encouraging me
to take this opportunity and cheering me up whenever I found deadlocks in this work.
IV


ACKNOWLEDGMENTS
I would like to thank my advisor Dr. Choi who gave me numerous advices for my
thesis project and for the high level of exigency that he demanded of me which lead me
to a satisfactory result. I thank all the members of the computer graphics lab which heard
my advances and offered some advices. Finally, I thank Shane Transue who implemented
the core program which enabled me to focus completely in the main topic of my research.


TABLE OF CONTENTS
CHAPTER
L INTRODUCTION.................................................................1
3D Scanning Overview....................................................1
Range Image Overview....................................................3
Registration............................................................4
Types of Registration................................................4
Registration Types Analysis..........................................5
Objective...............................................................6
Work Outline............................................................6
II AUTOMATIC REGISTRATION LITERATURE REVIEW..................................8
Related works...........................................................8
Fast and Robust Registration of Multiple 3D Point Clouds.............8
Fully Automatic Registration of 3D Point Clouds.....................10
Robust Registration of Coarse Binary Volume Models..................14
Automatic Multiview Coarse Registration of Range Images for 3D Modeling
...................................................................16
A Novel Two-Stage Algorithm for Accurate Registration of 3-D Point Clouds
...................................................................21
Possible Related Works Shortcomings....................................23
III. HIERARCHICAL STRUCTURE..................................................26
Point Cloud Simplification.............................................26
Simplification Proposals............................................26
Point Cloud Hierarchy Structure.....................................29
Point Simplification Process.....................................31
vi


Hierarchical Structure Construction...............................34
Neighborhood Descriptors.................................................38
Ring Simplification Normal Vectors....................................38
Ring Simplification Normal Vectors Layers.............................39
Local Invariant Feature...............................................39
Local Feature Histograms..............................................41
IV. AUTOMATIC REGISTRATION.....................................................47
Pair-Wise Transformation Computation.....................................47
Transformation Computation Proposals..................................47
Ring Simplification Comparison.................................48
Ring Simplification Layered Comparison.........................49
Registration Using Hierarchy Levels and Descriptor Filters............50
Points Pairs Search............................................51
Points Pairs Filters...........................................52
Chain Search...................................................54
Possiole Registration Evaluation...............................55
Range Images Characteristics...................................58
Batch Registration.......................................................59
V. EXPERIMENTAL RESULTS.......................................................61
Experimental Objectives..................................................61
Experimental Validation..................................................61
Parameter Settings....................................................62
Algorithm Validation..................................................66
Four Step Success Metric.......................................66
Overlapping Area Percentage Test...............................67
vii


Initial Orientation and Translation Test...............68
Comparison VS ICP Test.................................72
VI CONCLUSIONS.........................................................76
Experimental Conclusions.........................................76
Limitations......................................................77
Future Work......................................................78
REFERENCES.............................................................79
viii


Table
LIST OF TABLES
111.1 Local Invariant Feature Comparison with Hierarchy Level 2.............41
V.l Array Size of Hierarchy Level1 Comparison...............................63
V.2 Histogram Minimum Similarity Comparison.................................64
V.3 Minimum Distance Threshold Comparison...................................65
V.4 Proposed Algorithm Metric with ICP......................................67
V.5 Overlapping Area Comparison.............................................68
V.6 Initial Translation Comparison..........................................69
V.7 Initial Rotation Comparison.............................................71
V.8 ICP vs. Proposed Algorithm Comparison...................................73
IX


LIST OF FIGURES
Figure
L1 Example of 3D Scan Point Cloud...................................................1
I. 2 Range Image Acquisition........................................................3
II. 1 Search Space Plot.............................................................9
11.2 Equally Spaced Grid...........................................................10
11.3 Point Cloud Orientation Result with [2].......................................12
11.4 Point Cloud False Orientation Result with [2].................................12
11.5 Constellation Image Example...................................................13
11.6 Turntable Scan Example........................................................14
11.7 Octree Example................................................................16
11.8 Tensor Example................................................................18
11.9 Registration Results for [4]..................................................20
11.10 Local Invariant Feature for [5]..............................................21
II11 Example of the Coarse Registration for [5]....................................22
111.1 Divisions Along the Transversal Axis (Horizontal)............................27
111.2 Ring Simplification Example..................................................28
111.3 Range Images with 0% Overlap and Ring Simplification Match...................28
111.4 Hierarchical Structure.......................................................29
111.5 Ordered Simplified Points Mesh...............................................33
111.6 Range Images with Level1 Hierarchy...........................................35
111.7 Range Images with Level 2 Hierarchy..........................................37
111.8 Range Images with Level 3 Hierarchy..........................................38


IV.1 Chain Creation Diagram.........................................................49
IV.2 Incremental Orientation........................................................54
IV.3 Point to Point Distance Metric.................................................57
IV. 4 Point to Point Distance Threshold Metric.....................................58
V. l Pairwise Registration (Virtual Data) a........................................62
V.2 Multiple Range Images Registration (Real Data) b...............................62
V.3 Level1 Array Size vs. Alignment Time...........................................64
V.4 Pairwise Registration (Real Data) c............................................66
V.5 Registration with Different Overlapping %( Virtual Data).......................68
V.6 Pairwise Registration (Virtual Data) d.........................................72
V.7 Full Registration Coarse and ICP (Real Data)....................................73
V.8 Full Registration Coarse and ICP (Virtual Data).................................74
V.9 Un-ordered Range Images (Real Data)............................................74
V.10 Un-ordered Range Images Coarse Registration (Real Data).......................74
V.11 Fine Registration (Real Data).................................................75
xi


LIST OF EQUATIONS
Equation
11.1 Computation of Rotation....................................................9
11.2 Angle computation for [1]..................................................9
11.3 Distance evaluation for [1]................................................10
11.4 Computation of Rotation for [2]............................................11
11.5 Computation of Transformation with SOFT for [2]............................13
11.6 ICP Error for [3]..........................................................15
11.7 Minimum Point to Point Distance [3]........................................15
11.8 Weighted Error for [3].....................................................15
11.9 Mesh Dimensions Approximation for [4]......................................17
II10 Tensor Computations Max for [4]............................................17
11.11 Tensor Computations Min for [4]...........................................17
11.12 Correlation Coefficient for [4]...........................................19
11.13 Least Square Fitting Coefficient for [5]..................................22
11.14 Proximity Constraint for [5]..............................................23
111.1 Bin Size..................................................................31
111.2 Bin Horizontal Boundaries.................................................31
111.3 Bin Vertical Boundaries...................................................32
111.4 Axis Aligned Bounding Box.................................................32
111.5 Level1 Simplified Points..................................................32
111.6 Neighboring Simplified Points.............................................33
111.7 Simplified Points Quad Normal.............................................33
xii


111.8 Simplified Points Vertex Normal..........................................33
111.9 Level 2 Bounding Sphere Initial Radius...................................36
111.10 Level 2 Bounding Sphere Center..........................................36
111.11 Level 2 Radius Rectification............................................36
111.12 Ring Simplification Normals..............................................38
111.13 Histogram Local V Axis..................................................43
111.14 Histogram Local W Axis...................................................43
111.15 Histogram a Angle........................................................43
111.16 Histogram cp Angle.......................................................43
111.17 Histogram Angle........................................................43
IV.1 Histogram Similarity.......................................................53
IV.2 Level 3 Collision..........................................................55
IV.3 Level 2 Collision..........................................................55
IV.4 QuadTree Axis Division.....................................................3b
IV.5 Level1 Distance Error......................................................3b
IV.6 Level1 Correspondence Value................................................57
xiii


CHAPTER I
INTRODUCTION
3D Scanning Overview
In the last years the number of scanning devices available in the market has been
evolving and each time the accuracy and cost competitiveness has been improved, to a
point that in a not so distant future general public might have access to this technology
for their own necessities. Although we are still not to the point where general public has
access to this technology, the current industry has a good number of varied
implementations for these devices, among them we can mention the reverse engineering
process in which engineers are able to recreate a object to interact with it in their
CAD/CAM software, they are also used to recreate sceneries in computer graphics
software for entertainment purposes as well as terrain construction for robot navigation
localization and object recognition and even in medical application like tomography
reconstruction. The great varieties of 3D scanning devicesbased on stereo cameras
infrared cameras, laser time of flight among other novel approaches, are able to measure
objects from our 3D world and transform them into sets of data points that are known as
point clouds.
Figure LI Example of 3D Scan Point Cloud.
[A point cloud result of a laser based 3D scan.]
1


The real data used in this work are point clouds that were obtained with the help
of a laser based scanner that introduced a measurement error around 0.5 to 1.5as a
result of that, it is necessary to scan objects that are big enough such that the error does
not deform the main shape of the object. However, in the recent years new low cost
methods have been developed such that it could be possible to implement these
approaches to this work. Some of the most outstanding cost effective methods available
are the RGB-D based scans, Kinect, and vision based, photographs.
Kinect uses a set of IR projector and sensor and a RGB camera to obtain the
physical characteristics of the scanned scene. The IR projector emits a characteristic
pattern to the environment, this is invisible to the human eye, and this pattern
deformation is checked by the IR sensor and later used to triangulate the corresponding
point depth. The RGB image obtained from the camera is complemented with the depth
computations giving as a result an image that has RGB-D information per pixel.
Vision based approach attempts to replicate the human vision system by obtaining
two images from different points of view. A system is constructed with two coupled
cameras emulating human eyes. Each of the cameras obtain the images from different
points of view of the same object, then with the help of the computer vision algorithms
the edges of the image are detected in each of them. After that from the edge detection
results, the characteristic points are chosen and this creates a point cloud for each image.
The point clouds so far still correspond to a 2D image, to convert to a 3D point cloud it
starts by determining the corresponding points5 pairs from both images; these pairs of
points are then used to compute the depth by finding the projection from each camera to
the point that has approximately the same depth.
2


Range Image Overview
It is found frequently cases in which the devices are not able to obtain all the
information of the complete scanned object in just one take because the scanner has a
limited field of view. To solve this problem, in cases where it is a small object that is
being scanned, an easy solution could be to place the object in a rotating turntable,
however even this might not be a good enough solution to obtain all the corresponding
information; in these cases more range images, new scans that obtain only partial views
of the object, must be performed to complete the surface of the scanned object. The result
is a set of images of the same object that hold an unknown relation between them. For the
new range images, each of them contains their own independent coordinate system and
six degrees of freedom which poses a new problem to this application, a registration.
Figure 1.2 Range Image Acquisition.
[Example of scanner range and necessity of range images]
3


Registration
Range image registration is the search of a relation or Euclidian motion
(orientation and position) between matching range images in order to reconstruct the
original object with the range images under the same coordinate system.
Types of Registration
Registration can be categorized in three types by how the correspondence
between range images is explored. The first type corresponds to the feature matching; the
algorithms that use this approach find features that are present in both range images and
find the Euclidian motion based on these features findings. The second type corresponds
to an optimal configuration of the points; this type of algorithms tries to find a minimum
value for certain criteria by modifying the Euclidian motion of the range images. The last
type corresponds to finding the camera motion; in this case, the algorithms try to find the
location of the camera for each range image to transport the range images to the same
coordinate system.
Besides the previously explained categorization system, registration algorithms
can be categorized in two levels. The first level or coarse level registration refers to the
initial guess in which no information is available between range images and a rough
approximation is sought. The second level or fine level registration refers to the
registration of range images after an initial guess has been obtained or certain information
has been given to the algorithm to find the optimal configuration of the range images.
4


Registration Types Analysis
Some solutions to the registration problem include the incorporation of electro-
mechanical or positioning devices to the scanners in order to obtain the scanner motion.
These solutions might not be the best possible solutions available, since it might limit the
working area or increment the complexity of moving the device. Other scanner motion
computation algorithms may find the transformation between range images without the
electro-mechanical devices; however they are limited by small movements between the
scans or the use of external information from the user.
Several algorithmic approaches to solve the automatic registration with optimal
configuration have been proposed in all these years. The most commonly used algorithm
is the iterative closest point algorithm (ICP), which calculates the minimum point to point
distance between two point clouds. The ICP algorithm has the disadvantage that it could
converge to a local minimum between its iterations and most importantly that a bad initial
positioning of the two clouds inflicts a major risk of finding local minima and incorrect
registrations. That inconvenient with the ICP algorithm means that it needs a prior
approximation to the original positioning of the range images. Even with the local
minima problem, this type of registration is highly effective and the most frequently used
for the fine level registration.
The coarse registration takes charge of computing an initial guess for each point
cloud motion, without any previous motion information, some approaches are based on
finding specific features in the different point clouds that could match, while others rely
on finding matching relations between points and neighbors from different clouds; in
several commercial products the coarse registration is achieved by interaction with the


user. The output from the coarse registration is taken by the fine registration algorithm
and they are further registered in detail by those algorithms, for example ICP.
Objective
Previous approaches like the feature matching algorithms have the disadvantage
that features may be altered by external noises during the scanning process and
correspondence may not be found because of that, extensive search of the degrees of
freedom approaches are expensive in computing resources and time consuming and
possible incorrect absolute minimum is still highly possible; to improve the time of
execution hierarchical approaches have also been proposed, however these proposals
have the problem that the two level simplification leaves out many details of the point
clouds that help to improve the match evaluation. Besides the pairwise registration
shortcomings, the necessity of information about the order of a range images batch
becomes a new problem for the batch registration. Taking into account these situations,
the objective of this work is to develop a process that is able to coarsely register a set of
unordered range images with no information of their orientation or translation close
enough to be refined with the final step of ICP, and that taking the advantage of the
several hierarchical levels it is able to reduce the influence of external noises present in
feature recognition algorithms and reduce the extreme computations exploration
algorithms have.
Work Outline
The remaining part of this work consists of the following points: Automatic
registration background, which summarizes a few previous related works in this field.
6


Automatic Registration, this part explains the proposed methods to obtain the coarse
registrationsome of the previously researched proposals and all the details and structures
needed to register the range images. Experimental Results explores all the experiments
that were conducted on the final version of the proposal to determine its effectiveness or
to determine the minimal requirements of the proposed solution. The conclusions section
contains the analysis of the solution outcome and compares it to other approaches
highlighting the advantages of this method.
7


CHAPTER II
AUTOMATIC REGISTRATION LITERATURE REVIEW
Related works
This section focuses on exploring the previous works related with automatic
registration that have been influential for this work. Each algorithm will be explained as
concisely and simply as possible to supplement an overview that will enable the reader to
comprehend the nature of the algorithm.
Fast and Robust Registration of Multiple 3D Point Clouds
This work by Hironobu Fukai and Gang Xu [1]is a proposed method to solve the
coarse registration problem with the application of matching exhaustive searches. We
should consider the problems related to the alignment process: every independent range
image is located in its own independent coordinate system that is defined by it location
(x, y, z) and its orientation (a, P, y), this means that each independent range image is
defined by a relation of a 6 degrees of freedom. We should also consider the original
model has its own coordinate system with its corresponding 6 degrees of freedom. If the
relation between the model and the scans coordinate system is known, then it is easy to
transform them to obtain the original model, however this is rarely the case.
To solve the correspondence between the different range images to recover the
original model the use of the point to point distance can be used to minimize the least
mean square error between them, but this often converges to local minima that are not
even close to the model, and trying to find a proper local minimum in the entire search
space is a large task to do.


Figure 11.3 Search Space Plot.
[This plot shows the error found for a certain position; it exemplifies the presence of
local minima and a global minimum which corresponds to the best guessed orientation.
The proposed solution for this coarse registration is the use of exhaustive search
that had already been proven to be effective before. The 6 degrees of freedom spaces are
explored by computing several initial alignments guided by the model shape. To reduce
the number of possible initial positions the proposed initial positions are compared with
the help of the following formulas:
Equation 11.2 Angle computation for [1].
The neighborhood is then defined by 0, when the value is a non-extremum value,
then this initial guess is suppressed from the exhaustive search. With this final list of
candidates with all the non-extremum values suppressed, the ICP alignment is applied to
each of the possible solutions, and evaluated to find the optimal solutions.
[1]]
R = RiR2
Equation 11.1 Computation of Rotation.
0 = 2cos
9


The distance evaluation uses a weighted method in which the distance threshold
determines if an element is added to the evaluator or not:
Equation 11.3 Distance evaluation for [1].
Fully Automatic Registration of 3D Point Clouds
Makadia, et al[2] propose in their work the use of extended Gaussian images
(EGI)these are later enhanced by a new method they introduce that named constellation
imageto compute the orientation between two range images.
Figure 11.4 Equally Spaced Grid.
[The point clouds are enclosed in the spherical bounding body, the body is divided in
equally spaced (angular-wise) bins. Each bin contains the points that are projected into its
space. [2]]
Using global representations for range images with EGIs, which are based on the
collection of surface normals, gives the advantage of orientation recognition without the
translation interference. By detailed feature recognition, the rotation between two point
clouds can be estimated given the requirements that there is a large enough overlap area
between both clouds and that this data is not deformed so that it is possible to find the
10


same feature in both clouds. This approach proposes to use an exploration of the rotation
range to find the fittest rotation between two clouds. This computation is proven to be
greatly reduced by the use of spherical Fourier analysis with the requirement that the
histogram bins are uniformly separated on the sphere (with respect to the angles).
The computation of the rotation between the range images has no previous
knowledge, to find this relation all the rotations R E SO (3) must be considered, to do this
a scored likelihood grid is filled with the results of the correlations strength.
This methodology is very similar to the correlation of planar functions, which can
be expressed as simple pointwise multiplication in the Fourier realm, and thanks to FFT
extended to the spherical situation, the correlation computation is drastically sped up with
SO(3) Fourier Transform (SOFT).
$mP = tjr2lp
Equation 11.4 Computation of Rotation for [2].
Where HI and H2 are the EGI points of the scans in the SOFT, G contains the
resulting Euler angles between the HI and H2 points.
This reflects the similar properties of a generalized convolution, by multiplying
point to point the individual SFT coefficients and finally retrieving the desired G(R) with
the inverse SOFT.
11


Figure 11.5 Point Cloud Orientation Result with [2].
[The program computes the EGI and later aligns them with the corresponding
dominant features. [2]]
This approach is proven to be effective, the alignment between two EGI is
successful when they have high overlap; nevertheless, in cases where the overlap space is
minimal points are disproportionately populated around and non-overlapping surface
regions the method would fail to identify the correct orientation.
Figure 11.6 Point Cloud False Orientation Result with [2].
[The found dominant features dont correspond to each other resulting in an incorrect
alignment. [2]]
A dominant peak in the EGI is helpful in the sense that it could exist in both range
images and in that case those two would align. But if the dominant peak is not included in
the overlapping surfaces or this dominant peak is not even in any of the scans, then this
would affect the process. Because of this the proposed solution to this problem is to
convert the EGI into a constellation image; this is achieved by keeping the local maxima
12


and eliminating the remaining bins. The use of constellation images might also encounter
incorrect alignments if the non-overlapping areas highly contribute with local maxima,
but it reduces the chances of collecting the majority of normals from non-overlapping
areas.
Figure 11.7 Constellation Image Example.
[Example of an image range, its corresponding EGI and the constellation image
belonging to that EGL [2]]
For the translation computation, it is assumed that the correct alignment is
achieved where the greatest correlation of the two range images is found. Using the same
correlation principles the correct translation maximized the function:
The point clouds are voxelized such that a voxel is much larger than the fine
resolution of the scanner. Since this is a convolution integral then it can be simplified
with the Fourier transform as a multiplication. Then the coefficients can be recovered
from the Fourier Transform.
e(k) = _r2(k)
Equation 11.5 Computation of Transformation with SOFT for [2].
13


The last step is a verification that consists of voxelizing the space after the
alignment and measuring the consistency by accumulating the difference for the
overlapping voxels. The difference is weighted by the voxel point population. And for
known scanner if the alignment makes one point cloud occupy the space between the
other point cloud and the scanner occluding the visibility, then this alignment is also
discarded.
Robust Registration of Coarse Binary Volume Models
In his work Wingbermiihle [3] captures objects with the help of a turntable that
allows him to obtain the complete peripheral surface of that object, but in order to obtain
the complete surface he re-orients the object to scan other points of view. These two
scans are later registered to recover the original object.
Figure 11.8 Turntable Scan Example.
[The two scans from two different orientation of the elephant sculpture. [3]]
For the coarse alignment the six parameters of both range images have to be
aligned trying to obtain the best possible initial values and prevent the local minimal
convergence of the ICP. A known technique to obtain good initial values is to align the
centers of gravity and principal axis for both clouds, but this technique is also affected by
the errors obtained in the different scans. To avoid the error influence, the initial values
are verified through the ICP error; a error threshold is determined and compared with the
14


initial values ICP error obtained, if it is greater than the error then it is discarded and a
better set of initial values is searched by rotating the second range image around the three
axes 15, finally the combination of angles around the three axes that result in the
smallest error are chosen as the definitive initial values.
Equation 11.7 Minimum Point to Point Distance [3].
Where the N is the number of points of both range images and the dividend are
the minimum distances point to point from range image 1 to 2 and vice versa.
These contributions are optimized by the use of a distance octree. Each range
image is organized in an octree that starts as the total bounding box and is recursively
divided into eight equal sized boxes when a certain limit of points is reached; the division
stops when all the cloud points have been added and all the empty leaves are eliminated.
And thanks to this structure the division edges are now used as unsigned distance
approximations to compute the contributions.
The last step is to explore the six degrees of freedom spaces and iteratively trying
to optimize the weighted error criterion:
+ D
2N
Equation 11.6 ICP Error for [3].
Equation 11.8 Weighted Error for [3].
15


Where the first part is the simplified ICP error and the second part is the weighted
correlation term, where Vs is the section volume and VI and V2 are the model respective
volumes. The second term helps to prevent the local minima convergence, although it
may still converge to these values and if during the optimization process the greater
volume contains completely the smaller volume, this second term will disappear from the
equation leaving it as a regular ICP algorithm.
Figure 11.9 Octree Example.
[Example of the octree created from the elephant scan. [3]]
Automatic Multiview Coarse Registration of Range Images for 3D Modeling
Mian et al[4] propose in their work to attack the registration problem by
registering more than two cloud points at a time, taking advantage of all the information
generated in each point cloud to point cloud comparison and eliminating the unnecessary
computations repetitions.
The different range images are converted into representations named tensors
which are 4-dimensional data structures. Each point cloud is converted into triangular
meshes and reduced after that the normals of the resulting mesh are calculated for each
16


one of the vertices. When all the normals are computed, the three approximate
dimensions of the mesh are computed like this:
D = max^iViPi) min^iViPi)
Equation 11.9 Mesh Dimensions Approximation for [4].
Where Vi is the original point cloud Pi is the rotation matrix that aligns Vi to its
principal axis and therefore max and min obtain the maximum and minimum points of
the mesh in x, y and z when it is aligned along its principal axis. This step is repeated for
every range image acquired.
The next step is to compute the corresponding tensor for each reduced mesh. To
construct the tensorsthe vertices are paired in such a way that the distance between the
pairs is within the following limits:
mean(DXfDyfDz)
Equation 11.10 Tensor Computations Max for [4].
mean(DXfDyf Dz)
d2 -----------------
4
Equation 11.11 Tensor Computations Min for [4].
Where Dx, Dy and Dz are the component in x, y and z of the mean of all the
different range images dimensions. The vertices are grouped in a maximum of 4 vertices
and from all this groups a maximum nt groups are chosen such that they are uniformly
spread over the mesh, which in this case was nt = 300. For each pair of vertices a 3D
17


coordinate basis is defined with the center of the line between the vertices as the origin,
the average of the two normals is the z axis, the cross product of the two points5 normals
makes the x axis and the cross product of the z and x axes makes the y axis. The
coordinate basis is then used to create a 3D grid at its origin, the size of this grid
determines the degree of locality and the size of the bins determines the surface
representation granularity level. For this case the grid size was determined to be 103 and
the bin size was dl/5.
The grid is then compared to the mesh with each bin in the grid computing the
area of intersection with the mesh that is stored in a third order tensor. Each element of
the third order tensor is equal to surface area of the mesh contained in the corresponding
bin. It is highly probable that the majority of the tensor5 s values are empty, with no mesh
intersection, and this helps to reduce the tensor into a sparse array that reduces memory
utilization. This step is repeated for all the vertex pairs in the reduced mesh.
Figure 11.10 Tensor Example.
[Example of the tensor created from the dinopet scan. [4]]
18


A 4D hash table is constructed with the tensors of all the point cloudsthe first
three dimensions in the hash table are for the i, j and k of the tensor and the fourth
dimension is the angle between the normals of the pair.
The registration process starts looking for the mesh that has the greater surface
area in its tensors, this mesh is used as the root node in the Multiview correspondence
spanning tree. The next step is to compare the root node tensors with the tensors of all the
remaining meshes and the matching tensors are used to register those two meshes; this
recently registered mesh is included to the spanning tree and removed from the search
space. When all the tensors of the root mesh have been compared, the next mesh in the
spanning tree is used to compare its tensors with the remaining meshes from the search
space. The tensor comparison is done by a voting sequence, the four indices of a vertex
with values different to zero vote for all the other meshes and their tensors, when a tensor
has less than half of the possible votes then this correspondence is dropped. Then the
correlation coefficient is calculated for each remaining tensor according to the following
formula:
Cc = correl coef(Tmms),Ts(Ims))
Equation 11.12 Correlation Coefficient for [4].
Where Tm are the tensors with more than half votes in the first mesh, Tm(Ims) is
the value of Tm in the region of intersection of the first mesh with the second mesh and
Ts(Ims) is the value of Ts in the region of intersection of the second mesh with the first
mesh. The results of Cc are then sorted and the values Cci < tc=0.5 are discarded. The
remaining Tm values are then used for the local verification which works like this, the
first tensor value is used to compute the motion to align with the corresponding tensor in
19


the second mesh, and then the bounding dimensions are recalculated after this
transformation to get D5ms. The original bounding dimensions D are subtracted from
D5ms if the maximum difference between these two values is less than the specified
tolerance then the range images are registered with this transformation and the points of
both images that are less than 2dres, the resolution for the mesh, apart are also turned into
correspondences. If the number of correspondences is greater than nc, then ICP is used to
detail this registration and after ICP the number of tuples that are less than dres apart are
also correspondences. Lastly if the number of correspondences is greater than 2nc, then
(D-Dms) is computed again and if it is less than 2dres it goes into the global verification
otherwise, with any rail condition, another pair of potential correspondences is explored.
The global verification consists of comparing (D-DL), where DL are the bounding
dimensions of both meshes together after the transformation, and 4dres, it it is less than
4dres then this registration is accepted, in case of false a better registration is searched
with the next tensors couple.
Figure 11.11 Registration Results for [4].
[Example of the batch registration with tensors. [4]]
20


A Novel Two-Stage Algorithm for Accurate Registration of 3-D Point Clouds
Dai and Yang [5] propose a two-stage algorithm for the registration of point
clouds; this algorithm works first at the coarse registration level and then at the fine
registration level. In their work they highlight the possibility of extracting invariants and
geometric features to find correspondences between different range images.
Figure 11.12 Local Invariant Feature for [5].
[Example of the local invariant features. [5]]
This implementation at the coarse registration level uses the proposed data
structure named local invariant feature which is based on the idea of curvature features.
To adapt that curvature features, the normal for each point is computed in each point
cloud, then for each i point with its k closest points, neighbors, the dot product between
the i point and each of its k neighbors is computed and stored in the local invariant
feature vector. This proposed data structure is then capable of describing the neighboring
characteristics for each point like a curvature would and thanks to the dot product
properties, the neighboring characteristics would be invariant even in different coordinate
systems such as the different range images.
The next step in the coarse registration is to search the corresponding local
invariant features from the different scans. For all the source image points features FP
21


search the closest values from all the destination image points features FQ, this process is
optimized with the help of a kd-tree constructed with the FQ values for the comparison.
Once the possible correspondences have been found, the motion is computed by
first eliminating the less probable correspondences. The less probable correspondences
are the point pairs that have a feature vector distance greater than the threshold and the
feature vector distance is simply the mean distance of every feature vector pairs. For the
remaining correspondence points C, the coarse registration Euclidian motion is computed
least square fitting method with the following formula:
Equation 11.13 Least Square Fitting Coefficient for [5].
After that, the source mesh is transformed with the coarse registration Euclidian
motion and it along the destination mesh are used as the input to the fine registration
algorithm.

Figure 11.13 Example of the Coarse Registration for [5].
[Example of the coarse registration. [5]]
22


The fine registration uses a modified ICP alignment to register the two different
range images. The ICP algorithm is modified by adding two new constraints to improve
its performance. The first constraint, closeness constraint, eliminates the false point
matches; to determine the false point matches it considers the distance between the points
and the distance between their local invariant features. The pairs that surpass the given
distances thresholds are eliminated from the ICP computations. The second constraint,
proximity constraint, checks the reliability of a pair of point given the fact that if a point p
in P corresponds to a point q in Q then there are some neighbors of p that correspond to
the neighbors of q. The proximity constraint is checked according to the following
formula:
IIPrP/y-IKII
Ihp/ll + ll -'II
Equation 11.14 Proximity Constraint for [5].
If tms computed value is greater than the proximity threshold then the pair is also
removed from the ICP computations.
Possible Related Works Shortcomings
In this part, the possible weak points present in the previously mentioned
approaches will be explored in order to avoid the appearance of the same in this work.
The results showed by the authors for [1]are really good, but the registration in
this case is made against the original model instead of against different range images that
means a that the range image has a hundred percent of overlapping area; the use of the
original model is a great disadvantage since, a great amount ot times, the purpose of this
application is to obtain the model data that is not previously available. More of all, there
23


also exists the problem with the utilization of the ICP alignment error and incrementing
the different values of rotation to obtain a near to correct alignment that reduces the error
found, the search range is too large and depending on the sampled points it might not find
a close orientation to satisfy the requirements.
In [2] we can see some of the best results for the coarse alignment. This approach
has the small disadvantage that their detailed feature recognition could be affected by the
sensor quality, for example some feature may be distorted in the scanning process and the
correspondence would not exist between the two range images, and that in extreme cases
with low overlapping regions from both range imageswhile constructing the
constellation image the local minima were found outside the respective overlapping
regions which could cause non-corresponding constellation point and therefore incorrect
alignments.
[3] is an approach that is simplified by using mechanical enhancements to obtain
cylindrical scans which could introduce extra noises depending from the precision of
these devices. Once the two different scans are completed, the registration is performed
with the help of the ICP algorithm with randomly selected points from the two range
images, this technique may introduce an error which is obtained by not having
corresponding points from the both range images and leading to incorrect local minima.
The final weak point of this approach is that it has to explore the complete 3 orientation
DOF range to find a near to correct approach which makes it inefficient and it may still
find smaller ICP errors in an incorrect orientation thanks to the randomness.
The algorithm presented in [4] has a weak point in the fact that it creates the
tensor grids from randomly selected points from each point cloud and when they are
24


compared there may not exist correspondence between the points being registered.
Another weak point is the verification phase that uses the bounding dimensions as a
parameter; this only parameter may not be a good enough filter since the different scans
could have a great difference in bounding measurements according to their orientation.
The last approach explored in this work [5] shows promising results by finding
the specific features of the point clouds. However it has the disadvantage that the local
invariant feature may be identical in many different points for special cases like cubic
shapes, where the different planes rotated will have a very similar local invariant feature
in each face or even in repetitive shapes which could lead to an incorrect alignment.
25


CHAPTER III
HIERARCHICAL STRUCTURE
Point Cloud Simplification
As it has been mentioned, fine level registration has a very efficient solution in
ICP for the cases in which the initial guess is close to the actual transformation. This
situation leads to the necessity of finding a proper coarse level registration. Several
previous approaches, such as the previously described in chapter II, have been able to
solve this problem, nevertheless the complexity of finding correspondence between range
images is great to say the least. To confront the complexity problem it is proposed to
simplify the point clouds in an organized structure that allows the previous knowledge of
point vicinity and a hierarchical structure that would improve the complexity for the
correspondence search. This section will be focused in the explanation of the
methodology used to create the hierarchical structure for the program.
Simplification Proposals
In the search of a simplification structureother solutions were proposed and
implemented with certain degree of success. The most successful proposal consisted of a
ring simplification in reference to the rings of Saturn.
The idea consists of dividing the range images point cloud along its horizontal
axis in segments of a predetermined length. The horizontal axis is formed by the
perpendicular of the camera or scanner point of view and the up axis orientation.
26


After all the points are divided into bins of equal length along the horizontal axis,
the points are explored to find the maximum value along the depth axis, which means it
would find the point closest to the camera.
Figure 111.1 Divisions Along the Transversal Axis (Horizontal).
[Range image divided along the camera x axis into n bins.]
All these maximum points would then be complemented with the center of the
complete range image height and the center of its corresponding bin along the horizontal
axis.
The ring simplification would represent roughly but accurately enough the
contour of the objects like seen from a top view. A group of lines would then represent
these points and the normals between them could be used to further obtain information
from the structure.
27


Figure 111.2 Ring Simplification Example.
[8 range images with their respective ring simplifications]
The ring simplification solution however is limited in the sense that the
information is extremely reduced and the details are completely lost leaving several cases
of similar representations even for completely different point clouds.
Figure 111.3 Range Images with 0% Overlap and Ring Simplification Match.
[Example of two non-corresponding range images with ring simplification match.]
28


Point Cloud Hierarchy Structure
The final structure used in this work is composed of a four level hierarchical structure.
The bottom level is the point cloud by itself which is not used in the coarse level
registration; the second level is a simplified version of the point cloud; the third level
compresses even more the second level and contains vicinity information and the fourth
level compresses the boundaries of the third level but leaves out the vicinity information.
level 3
level 2
level 1
level 0
Figure 111.4 Hierarchical Structure.
[Diagram of the proposed hierarchical structure and their relations]
The four levels hierarchical structure is chosen based on the idea that the objects
to be reconstructed have enough detail to differentiate matching surfaces and that by
obtaining the simplified version of the object, the main shapes and features of the object
would remain available for the registration.
The simplification of the point cloud has two purposes, to speed up the
computations related to registration and to decrease the effects of the surface
imperfections introduced by a low quality scanning device. However, as a result the
detail detection, like the detection of a door handle in a car or a small crease in the rabbit
29


leg, is impossible; but if we consider the presence of a measurement error in the scans,
then it is obvious that those kinds of details could be easily confused with the faulted
scans surface imperfections.
Starting from a leaf level and going up in the hierarchical structure construction
the second level works as a kind of average process in which only the main contour of
the scans are kept this process practically disappears the effect of the scanning errors, the
third level helps in creating descriptions of the surface patch features each volume is
covering so that only similar patches are matched and the fourth level works as a shortcut
in the process that when a collision is not possible at that level then in all the lower levels
it is impossible to collide.
The inclusion of a fifth or more levels of hierarchy would be practically useless
because it would only increment the number operations needed to reach the lower level
for every case, beating the purpose of speeding up the computations. That is explained by
the fact that for each higher level the hierarchy has, the surface is reduced to a smaller
number of voxels, leaving out more and more details getting closer to the point of box-
box comparisons.
All these statements would be tme for the cases in which the main shape or
contour of the object is enough to differentiate the surfaces and find approximately
correct alignments, but for cases in which the minor details are the dominating sources to
find differences between scans, for example the scans of a very wide building that have a
repetitive pattern and that only small details, like plants, are the determining factors for
correct alignments, then these 4 levels would not be enough.
30


Point Simplification Process. The main idea behind the point simplification is
that of an elastic latex mesh that is exactly large enough to cover the range image.
Imagine that the latex mesh is being pressed against the object and that it would touch
several points but certainly not the complete surface and that you can obtain the
coordinates of all the touching points in the surface.
The point simplification process starts by obtaining all the points available in the
point cloud. An axis aligned bounding box for each range image is computed. The aabb is
aligned for each independent range image coordinate system and for each point in each
range image, the maximum and minimum value of the three axes are updated. After that
the boundaries of all the range images are used to obtain the simplified points separation
size.
Size{xt yt z)
max (max(xpf ypf zp) min(xpf ypf zp))
n
Equation 111.1 Bin Size.
After that all the points from each point cloud are sorted in a binary search tree
structure which can sort the points based on the indicated axis (xy or z)in this case
along the x axis. The binary search tree is also able to return all the points that are
contained within the indicated range. Each range image is then divided in N different
point columns according to the following:
HB(ifj) = (n^Sizeix^^^Sizeix)^ + Size^x)^
Equation 111.2 Bin Horizontal Boundaries.
31


The next step is to sort each point column again with the help of another binary
search tree, in this case along the y axis. Then each column is divided in N different rows
according to the following:
= (n(57ze(3/)), n(57ze(3/)) +57ze(3/))
Equation 111.3 Bin Vertical Boundaries.
After the row division case the binary search tree computes axis aligned bounding
boxes for each of the bins. Finally the simplified points are determined like this:
aabbix^ y1(z1(x2, y2, z2) = max(xy, yjt Zj), min(xy, yjt Zj)
Equation 111.4 Axis Aligned Bounding Box.
/aabbCxi) + aabb(x2) aabbCy^ + aabb(y2) w \
SP{x,y,z) = I----------------------,--------------------.aabbCZi) I
Equation 111.5 Level1 Simplified Points.
Using the maximum value along z means that the closest value to the scanner is
the one being used. The reason for this is to emulate the behavior of the latex that would
only touch the highest point in the body.
The points are finally stored in an NxN array completely ordered according to the
bins divisions from -x to x and from -y to y axes. With this pre-computation process it is
possible to automatically know the exact neighbors for each point without the usual use
of distance computations and reduce the number of points for further computations.
32


0,0 01 0^2 ... 0.D



D,0 n
Figure 111.5 Ordered Simplified Points Mesh.
[Example of the ordered points and the determination of their positions and
neighbors]
wpay) = (ii,ji)
Equation 111.6 Neighboring Simplified Points.
The ordered points array give us a simple and easily accessible structure of
ordered quads in which it is possible to determine automatically the vertices of each of
quad, this situation greatly accelerates the computations by skipping the neighborhood
determination. To compute each point normals, first for each quad, the surface normal is
computed according to the following:
QNml(i j)=+1'J p X Pt+i'+i-Pt+1+ +i-+1'+i X -p+i
Equation 111.7 Simplifled Points Quad Normal.
Then with all the neighboring quads, the vertex normals are computed and stored
in a parallel NxN normal array for each vertex with the following formula:
,ZLo QNmls
Normal(ifj)=--------------
q
Equation 111.8 Simplified Points Vertex Normal.
Where q are all the 4 possible quads surrounding the vertex ij.
33


Hierarchical Structure Construction. The hierarchical structure is based on the
hierarchy bounding volumes structures used in the collision detection problems. These
types of structures consist of simpler volumes that contain the mesh entirely. It is
typically started with a root node volume that contains all the points and is constructed in
a top-down way; that point cloud is then volumetrically split according to the desired
criteria and each of the divisions have their points represented by a bounding volume
which are the child nodes from the previous iteration. The process is repeated iteratively
until a threshold is reached which in typical cases is the number of points in the lowest
node or the tree depth.
The bounding volume hierarchy speeds up the process in the case of the collision
detection because the intersection of the simpler volumes is done extremely fast and
following the hierarchical structure it is not necessary to search at a lower hierarchy level
unless the higher has a collision state. This can make a collision detection process as fast
as just one operation or in the worst of the cases a logarithmical case until it gets to the
leaf level.
In the case of the proposed solutionthe hierarchical structure is constructed in a
bottom-up way. The extreme level of abstraction of a root node is not needed for this
approach since the details of the range image would be completely eliminated. The
reason of the utilization of this hierarchical level is to confront the verification process as
a collision detection problem to speed it up.
In comparison of this approach with the approaches proposed in [6] and [7] the
proposed hierarchy presents more levels. The existence of more levels allows more
content in the structure and because all information is conserved for the coarse
34


registration then it results in a better metric for the evaluation of the proposed
transformations.
The leaf level is the range image with all the points contained in them, it is
basically the raw data from each scan and it is not used in the coarse registration to speed
up the computations, this level is used in the fine registration step to find the optimal
transformation with all the surface properties.
Figure 111.6 Range Images with Level1 Hierarchy.
[Example of the simplified points (blue) applied to a set of range images.]
The first level is the point cloud simplified with the NxN array. The necessity of
the level1 hierarchy corresponds to the fact that point clouds may contain hundreds of
thousands and computations for these cases are extremely expensive; besides the number
of points reductionthe simplification process averages the error from low quality
scans and the ordered nature of the level helps to determine beforehand the neighboring
points without further computations that regular feature detection algorithms need. It is
computed from the bounding boxes of a determined mesh size and to better represent the
scanned object it is simplified to the points in the frontal face of the axis aligned
35


bounding box with its corresponding normal instead of voxelizing the mesh, like it is
shown in the equation 111.5.
The reason of existence for the second level is that the simplified points from
level1 still have no surface information therefore registration related with just the level1
needs a great amount of further computations and a high complexity. To reduce these
problems a new level where surface description is available was created, this level should
also help to improve the match evaluation complexity. The second level is the most
important level since it is where the vicinity information is kept which will be used for
the feature recognition filters. The structure of this level is an ordered array of bounding
spheres. The bounding spheres were chosen because this is the most frequently accessed
level and the sphere intersection determination is the fastest of all the bounding volumes.
Each bounding sphere contains a 3x3 level1 points because it allows having an even
description of the surrounding surface around the center point and the neighboring points
are automatically found with the ordered array. To compute the bounding spheres the
following method is used:
IniRad(ifj) = maxlength {aabbXfaabbyfaabbz)
Equation 111.9 Level 2 Bounding Sphere Initial Radius.
Equation 111.10 Level 2 Bounding Sphere Center.
Rad(i,j)
dist(ps, Center) > Rad, Rad = dist(pSf Center)
else, Rad = Rad
Equation 111.11 Level 2 Radius Rectification.
36


Figure 111.7 Range Images with Level 2 Hierarchy.
[Example of the bounding spheres applied to a set of range images]
The final hierarchical level was created with the idea that several computations
still happen in the second level where the collision between range images is not
happening. Considering how collision detection algorithms solve this problem with
higher hierarchical levels that oversimplify the mesh to avoid unnecessary collision
computations, the third level encompasses level 2 bodies to reduce computations. The
third contains a 2x2 level 2 bounding spheres within a set of Axis Aligned Bounding
Boxes. The choice of bounding volume in this case is because not all the resulting
simplified points meshes are approximately squared and that causes that with certain
configurations the resulting bounding spheres are too large and offer no help with the
registration. In a previous iteration of this workthe level 3 hierarchy structure included a
descriptor of the average normals of the level 2 structures contained in each element of
the level 3, however the experiments showed that so much detail was lost in this process
that even corresponding surfaces would not have similar descriptors.
37


Figure 111.8 Range Images with Level 3 Hierarchy.
[Example of the level 3 bounding boxes applied to a set of range images]
Neighborhood Descriptors
The registration would work by aligning certain matching surface characteristics
obtained from the point simplification; several approaches were proposed to try to solve
this problem, the following part will explain the most remarkable and analyze the reasons
that leaded to the option that was chosen.
Ring Simplification Normal Vectors
Using the simplified lines obtained by the ring simplification, the normal vectors
to each pair of points succession was computed as a 2D problem with the following
formula:
RSNormal(i) = pt pl+1 x (0,0,1)
Equation 111.12 Ring Simplification Normals.
This method results in the normals that describe completely the line that
represents the range image, however during the registration process, because of the great
amount of detail lost, the results of registering any semi-planar surface would always
38


converge being them local minima that could not be differentiated from the correct
alignment, look at the example shown in figure 1113.
Ring Simplification Normal Vectors Layers
Using the level1 simplified points obtained by the point simplification, the
normal vectors to each pair of points succession was computed as a 2D problem as in the
previous description. This approach then represents the range image as a set of N lines
equally distanced along the y axis. However the shortcoming of this approach is that the
descriptors lose a great amount of vicinity description by just considering the horizontal
neighboring points at each side of each point.
Figure 111.9 Ring Simplification Layered.
[Example of a range image with its n layers of rings]
Local Invariant Feature
Using the method proposed in [5], the level 2 points were represented and stored
as level 2 structures that would represent the small patch of surface covered by the
bounding body. In this case the computations of the local invariant feature would be
extremely accelerated by first reducing the number of points to be analyzed since the
point structure to be represented is now NxNsecond by skipping the neighborhood
39


determination and distances computations since the ordered array already gives the point
neighbors for each point and lastly by reducing the neighboring points to a maximum of 8
points.
Figure 111.10 Simplification of Local Invariant Feature for Level2.
[Level 2 bounding sphere with its center point as a reference of the surface patch
curvature.]
To test the accuracy of this surface representation, two range images with more
than a 50% of overlapping area were used. All the pre-calculations up to the surface
descriptions were computed and the scalar values for the level 2 were returned as two
tables for both range images.
Unfortunately the obtained results were not satisfactory. It can be observed in the
table the values of (4,4) and (5,4) are different even when they are representations of
matching surfaces, the threshold would have to be too large for it to fit. After visually
comparing both tables and observing more similar results on non corresponding point
than on correct corresponding points it could be inferred that this filter would not be
enough for the feature matching. The more reasonable explanation for this is that with a
40


very small number of neighboring points, the absence or a great variance of values of just
one neighbor could deeply affect the average for the result even more when it is the case
of the curvature represented as a simple scalar.
Table 111.1 Local Invariant Feature Comparison with Hierarchy Level 2.
Range Image 0
0 1 2 3 4 5 6 7 8 9
0 0.0 537.2 393.9 315.7 386.0 395.3 366.7 385.1 366.5 488.5
1 0.0 0.0 364.9 151.6 211.0 72.4 86.2 84.6 131.8 178.9
2 0.0 136.2 101.6 83.7 138.0 79.1 41.8 77.4 97.9 260.6
3 453.8 104.8 71.2 111.8 151.0 66.1 103.5 56.6 84.1 0.0
4 431.4 236.5 56.1 80.5 82.0 118.7 93.5 76.6 1076.2 0.0
5 449.0 192.2 161.8 83.0 102.4 95.7 91.5 1074.3 0.0 0.0
6 378.6 132.2 99.7 0.0 0.0 0.0 0.0 0.0 0.0 0.0
7 370.7 173.4 149.5 114.9 0.0 0.0 0.0 0.0 0.0 0.0
8 0.0 102.6 3112.5 113.3 163.9 443.5 0.0 0.0 0.0 0.0
9 0.0 389.7 0.0 0.0 146.2 466.3 0.0 0.0 0.0 0.0
Range Image 1
0 1 2 3 4 5 6 7 8 9
0 0.0 534.0 388.7 392.9 374.6 397.6 361.6 369.7 376.0 0.0
1 0.0 0.0 119.8 177.0 94.0 81.9 72.2 130.1 135.1 319.2
2 0.0 199.2 118.9 137.9 55.2 56.8 41.9 130.1 206.3 0.0
3 0.0 102.6 133.4 121.5 100.6 38.6 93.7 64.1 85.6 0.0
4 0.0 132.0 91.0 82.1 113.1 105.9 38.3 83.6 1080.5 0.0
5 315.9 210.3 141.5 101.2 114.9 76.1 89.3 117.8 0.0 0.0
6 309.2 79.5 74.7 212.5 0.0 0.0 0.0 0.0 0.0 0.0
7 407.2 130.6 136.0 179.3 212.6 0.0 0.0 0.0 0.0 0.0
8 0.0 0.0 0.0 226.0 84.9 134.6 214.9 0.0 0.0 0.0
9 0.0 0.0 0.0 0.0 215.8 68.5 106.6 0.0 0.0 0.0
Local Feature Histograms
The chosen method was the local feature histograms which are capable of storing
three-dimensional surface information in a group of bins instead of a simple scalar
number like in the previously described process. Using the method proposed in [8], the
41


level1 points were represented and stored as level 2 structures that would represent the
small patch of surface covered by the bounding body. In comparison with the method
presented in [8], the method is speeded up by reducing the number of points that
represent the range image and also by obtaining the 9 possible neighboring points
automatically from the ordered level1 points structurewithout having to compute the
distances for every point to determine the neighbors and reducing the number of
calculations to a maximum of n =108, because there are 9 or less points in the level
2 hierarchical structure.
The computation of the histogram is done for every k level 2 sphere; for every
level1 point included in the bounding sphere, all the possible pairs are used to compute
the descriptor. With each pair of points, local coordinate systems are calculated using the
points normals and the vector created between them. Then with these local coordinate
systems the angles between them in each of the three axes are obtained. The process
works with any pair of points p and q each point with its corresponding vertex
normal Np and Nq. The vector that is formed between p and q is computed and this
vector is used to multiply it with a cross product by the normal of p (Np), the result is a
vector that will be used as an equivalent of a y axis which will be called V. Then the
new axis V is multiplied with a cross product by the Np to obtain an equivalent of a z
axis which will be called W. The local coordinate system is now (NpVW) and it is
used to compute the angles between the pair pq. The first angle is obtained from Np and
the vector between points p and q. The second angle is obtained from the V axis and the
normal of the point q (Nq). The third angle is obtained from the projection of the normal
of point q (Nq) to the plane formed from Np and W and the Np axis.
42


V
Figure IILllAngles of 2 Points for Feature Histogram.
[Pair of points p and q with the local coordinate system for p and the angles between the
q normal and the coordinate system.]
V = Np X
llq -pll
Equation 111.13 Histogram Local V Axis.
W = Np XV
Equation 111.14 Histogram Local W Axis.
a = aCos(V Nq)
Equation 111.15 Histogram a Angle.
=aCos (
Equation 111.16 Histogram (p Angle.
6 = aTan2(W NqfNp Nq)
Equation 111.17 Histogram 0 Angle.
The three values obtained are then stored as occurrences in a bin that contains the
value within its range. Since it is known that the result of the values obtained range from
-180 to 180 degrees or -n to 7i radians the ranges of the bins are computed as an exact
division of the range of results in s equal size bins.
43


To test the accuracy of this implementation, the histograms of known non-
corresponding surfaces in two range images were created and compared. In this special
case, the number of point in each surface was different and a direct comparison of the
histograms would return less than a 50 percent of coincidence which would meet the
wanted results.
0 1 2 3 4 5 6 7 8 9 10 1112 13 14 15
Figure 111.12 Histograms of Non-Corresponding Points (Result 40% similarity).
[Comparison of two histograms from non-corresponding surface patches. Result is not a
possible match.]
The next tests included using randomly selected pairs of patches at a time a
comparing the histograms and visually identifying if they were correct correspondences
and if that condition matched the result from the histograms comparison.
44


Figure 111.13 Histograms of Corresponding Points (Result 49% similarity).
[Comparison of two histograms from corresponding surface patches. Result is not a
possible match.]
The results obtained from this test were not the expected. For one correct match
the histograms had less than the 50 percent of coincidence. After creating the
corresponding graphics it was detected that the difference was caused because the
number of points was different and even with the great difference in the number of
occurrences in each bin, the distribution of the graphic was similar, therefore by
comparing percentages instead of the occurrences the difference obtained was minimal,
which led to the use of percentages for the comparisons from there on.
45


50
45
40
35
30
25
20
15
10
5
0
0 1 2 3 4 5 6 7 8 9 10 1112 13 14 15
C
D
Figure 111.14 Histograms of Corresponding Points with Percentages (Result 91%
similarity).
[Comparison of two histograms from corresponding surface patches with their bin
percentages. Result is possible match.]
Other results found from the tests realized were false correspondences, pairs of
points that had similar histograms but that were not actual correspondences. These results
were expected from the previous knowledge that the point simplification would eliminate
a certain level of detail and that there would be also surface patches that contain a similar
surface even when it is not the exact match.
46


CHAPTER IV
AUTOMATIC REGISTRATION
Pair-Wise Transformation Computation
As it has been mentioned, the main purpose of this approach is to find an initial
guess that is close enough to the actual transformation of the range images so that the ICP
algorithm can further refine the transformation using the point to point distance
optimization. The related works that have been explored so far in this work cover a wide
area of ideas from bmte force approaches where the degrees of freedom are exhaustively
explored to the feature detection algorithms that refine the meshes to a small number of
points that are later optimized. The proposal in this case is to take advantage of the
hierarchical structure to speed up the computation and use the feature descriptors to
reduce even further the exploration.
It should be considered that the goal of this work was not in the simple
registration of two range images but the automatic registration of a set of range images
that comprehend the complete peripheral surface of the scanned object. This means that a
metric system should also be included to compare the registrations of different pairs and
decide for the best option, which makes this problem more complex and creates the
necessity of more information available for each registration process.
Transformation Computation Proposals
Before coming up with the final solution to the coarse registration process a
couple of approaches were explored in search of an algorithm that could find the correct
or close to correct transformation, and that would then give enough information about the
47


match that could be used to determine the best option and align the batch of range images
to reconstruct completely the scanned object.
Ring Simplification Comparison. This first approach used the simplified lines
obtained from the column simplification of the point clouds. In this case the line
representing the range image would have N vertices with N-1 normal vectors that would
describe the characteristics of the line. Since it is a line along a simple plane the vectors
can be simplified to (x, z) which simplifies and speeds up the computations.
The process starts by aligning the normal vectors of a point ns in the second range
image with a point nd in the first range image and then translating the second range
image so that point ns is coincident with point nd.
The next step is the creation of a chain of coincidences. The first link is included
in the chain, in this case it is the origin point where the lines were roughly registered,
after that the chain is expanded incrementally to the next vertex in the line of the point
cloud to be registered, the closest point to that new link is found in the line of the
destination range image and the difference between the link normal and the closest point
is computed, if the difference absolute value is less than the threshold and if the distance
between the points is less than half of the line segment length then the link is accepted
and the chain continues to grow incrementally. In the case of a difference or distance
greater than the thresholds the chain will start growing decreasingly following the same
process, if the chain was growing incrementally, otherwise the chain finishes and the
chain size is stored.
48


Figure IV.1 Chain Creation Diagram.
[Example of a chain search. The compared vertices are aligned, then the neighbors are
checked, if they are within distance threshold, add to chain otherwise go to the other
direction.]
All the possible pairs of points from both range images are explored, a register of
the maximum elements in a chain of coincidences is kept and the longest chain is
evaluated as the correct rough registration.
This process would be a very fast approach however with all the details lost in the
ring simplification it could return very bad registrations for range images with simple
planes or surfaces, in several cases converging to local minima because of all the possible
line configurationssee figure 111.3.
Ring Simplification Layered Comparison. This solution is based on the
findings of the simplified lines comparison explained in the previous section. To avoid
the number loss of information the layered rings are used to describe the point cloud
instead of only one line it used N lines with N vertices and normals. In this case even
with the layered approach the normals would be treated as two-dimensional because the
49


height does not change along the same ring, this leads to a speed up of normal
computation as well as normal distances computations.
The layered solution reuses the idea of the chain of coincidences. The points to be
registered have the normals aligned and the second range image is translated so that the
points are coincident. A chain is started with the registered points and the chain starts
growing incrementally along the same ring. The next point is found as the next point in
the current ring if the resulting values are within the thresholds then the element is added
to the chain. If the resulting values are out of the boundaries, then if the chain was
growing incrementally in the ring it will start growing decreasingly in the same ring. If
the chain was growing decreasingly and the results are out of bounds it will go up to the
next ring and try to grow in that direction when it stops in that direction it will return to
try to grow going down to the next ring immediately bellow.
The process is repeated for all the possible combination of pairs from both range
images that are being registered and the maximum number of chain elements is stored to
find the best option. The point that generates the longest chain of coincidences is then
used as the correct coarse registration.
The results of this process were promising; however the exhaustive search with all
the possible pairs of points is severely time consuming even for the simplified points in
the coarse registration.
Registration Using Hierarchy Levels and Descriptor Filters
The final result of this research for the coarse registration fuses some of the
aspects of several of the related works that have been explained in previous sections. The
exhaustive exploration of the combination of points is used to find the orientation and
50


translation of the range image that is being registered. This approach is an improvement
of the solution proposed in [1]and [3] where they explore exhaustively the
transformation space indiscriminately, in this case the solution proposes to limit the range
of transformations. Considering [6]a hierarchical structure was implemented; however
instead of getting rid of all the information included, a multi-level hierarchy is used were
the level of detail keeps incrementing as it gets further in the hierarchical tree. The
hierarchy levels try to improve the process also by speeding up the registration
verification. Another contribution in this work is the use of feature filters, the proposed
algorithm takes the feature description results to filter out transformations that could not
be possible by using just similar surfaces to register pairs of points; this modification
helps to maintain all the information available to do the metrics of the registration quality
instead of limiting the number of points available for the registration where some of the
remaining points may not be part of the overlapping area between the range images. The
process starts in a pair-wise registration, where the pairs of range images are registered
and graded in order to determine the best possible registration. The following sections in
this chapter describe the methodology used for the coarse registration of the range images
pairs and then the extra steps used to register the whole range image batch.
Points Pairs Search. It works in the level 2 of the hierarchical stmcture;
therefore the problem is reduced to a maximum of N/3 x N/3 structure. The idea for the
algorithm is that for a pair of range images with overlapping areas the level1 point
simplification may be slightly altered by the point of view of the scanner but the overall
properties of the surface would not be deeply affected within a certain diameter, and
thanks to that there will exist a surface representation equivalent in both range images
51


that are being registered. That is why the surface is roughly represented with the level 2
containing all the vicinity information of the simplified point clouds. It is also assumed
that the normals computed for the level1 hierarchy points are pretty close to the original
and that the surface normals within a certain small diameter are very close in values. As a
result it is possible to deduct that for range images with overlapping areas, the
corresponding points5 normals will have a very close distribution and change rate and
thanks to that we can reduce the transformation search space to only the possible
combinations of its pairs of normals.
The process starts by choosing the central point from the level 2 bounding sphere
from the source and the destination image ranges, that we already know thanks to the
ordered arrays, then the histograms corresponding to each bounding sphere are compared
as a filter, if it passes, then it continues to the next step, if not the pair is discarded. For
the next step the normal from that central source point in the range image to be registered
is then rotated to obtain the same orientation of the central point in the destination range
image and translated to make the points coincidental. After that the orientation needs to
pass a correspondence filter; if it fails, the pair is discarded, otherwise a chain is searched
with the help of the hierarchical structure. All the possible pairs of points from level 2 are
searched and the ones that have a value above the threshold are saved for the final metric
evaluation. If no pair is found after all the tests then the algorithm determines that there is
no correspondence between the range images pair.
Points Pairs Filters. The algorithm proposes to use two filters, a filter for the
surface similarity and a filter for the correct orientation. The use of these filters intents to
52


reduce all the possible mismatches as well as the total number of deep explorations in
search of a chain of coincidences that would result time consuming and unproductive.
The surface similarity filter uses the feature recognition techniques used in [6],
the surface histogram basically stores the information of the curvature inside the level 2
bounding volume. A matching patch of surface from the source range image should be
similar to the matching patch of surface from the destination range image. Using the
histograms distribution, they are compared bin to bin and a percentage of similarity is
computed, if the percentage is greater than the 70 percent then the points are treated as
possible matches.
similarity =
bin
^ abs(Pbins% Qbins%)
5 = 0
Equation IV.1 Histogram Similarity.
The orientation filter checks that the level1 points contained in the level 2
bounding sphere have a matching orientation between the explored pair. It starts by
finding the closest point to each of the level1 points; each of them should have a distance
less than the md/2 if not the pair is rejected. Then for each point, the closest point normal
vector difference should be less than 10 degrees, if more than 3 of the points fail it is
rejected.
And finally, the incremental orientation; the central point in both range images are
incremented, if the incremented points are not the closest to each other, then the source is
rotated around the normal vector until the incremental closest points are coinciding.
53


o
8 t
O O
O C C)
o o
o o 0
Figure IV.2 Incremental Orientation.
[Two matching bounding spheres included points, tmd the immediate next point from
the center for each bounding sphere. If the closest point is not each other rotate until the
condition is met.]
Chain Search. The chain search is where the suggested solution takes advantage
from the techniques used in collision detection and the constructed 4 level hierarchy
structure.
It recycles the idea suggested in the ring layered simplification comparison. The
chain starts with the central points or the registered pair. Since it is known their location
in the hierarchical structure then it is possiDle to limit the probable closest point as the
points contained in the level 2 bounding sphere. All the points within the current level 2
volume are searched and if the distance to the current point is less than md/2, the point is
added to the chain.
The process is repeated to all the level 2 spheres that share the level 3 parent node
with the origin. It then follows with the neighboring level 3 volume from the source range
image, it finds if it is intersecting with some other level 3 volume from the destination
range image. Then it searches the intersections on the level 2 spheres and for the found
collisions it goes into the level1 points, adding the points to the cnain in the case of pairs
of points with distance less than md/2. These process works like the ring layered
simplification comparison but instead of growing in the equivalent of the level1 points it
54


tries to grow at the level 3 volumes and exploring deeper only in case of possible chains
links inside the explored branch. This process discards the non-corresponding points in
batches since the higher levels which accelerates the performance.
cx
cy
cz
CenterXa CenterXb <
Velse,
\CenterYa CenterYb < (
[else,
[else,
collision
Equation IV.2 Level 3 Collision.
\cx cy cz,
[else,
fWidtha Widthb^
{ 2 1 2
Heighta Heiqhth
'2 + 2 )
fDeptha Depthb\
\ 2 + 2 )
:z, collision =1
collision = 0
cx -
cx
cy
cy
cz -
cz
_ \Centera Centerb Radiusa + Radiusb), collision =1
[else, collision = 0
Equation IV.3 Level 2 Collision.
The chains of coincidences whose number of elements are greater than the
threshold are stored as a possible final registration and evaluated to determine the best
possiole option.
Possible Registration Evaluation. All the pairs of points that have a chain larger
than the threshold are then explored in detail to have its correctness measured. The basic
tool used for this metric is a Quadtree that contains the destination range image. This
Quadtree helps to obtain the minimum distances from all the level1 points in the source
mesh to the destination mesh level1 points. There are two possible ways of measuring
the correctness of the registration, using the average error or using the number of
coincidences.
55


The Quadtree is constructed from the root to the leaf nodes; it starts by obtaining
the aabb from all the points in the level1 array. The aabb is then split by the half along
two axes; these axes are defined by these conditions:
(aabbv > aabbzt divide y
aabbx > aabbv, divide x j ^ T ,
y l else, divide z
, , (aabby > aabb7f divide x
else, divide y ] ,
( else, divide z
Equation IV.4 QuadTree Axis Division.
All the points are divided in the 4 resulting sections of the parent node. This
process is repeated iteratively until all the leaf nodes have less than 8 points.
The Quadtree accepts any 3D point and it computes the closest leaf node to that
point. Inside the closest leaf node it computes the distances with the points inside the
node and the searched point and returns the minimum distance whicn is the minimum
distance from the point to the point cloud in a point to point manner.
The registration starts with the point p in the level1 hierarchy from the source. It
computes the minimum distance from the point to the destination in a point to point
manner with the Quadtree. The error is then affected by the minimum distance and after
Divide
repeating the process for all the points available in the source range image the error is
computed like this:
^=minDist(ps)
Error =-----------------
n
Equation IV.5 Level1 Distance Error.
The error is compared with all the possible correct registration chains and the
registration with the lowest error will be chosen as the correct coarse registration. This is
56


the typical ICP metric of error, like in ICP, the purpose is to try to optimize the error
value with the registrations found.
Figure IV.3 Point to Point Distance Metric.
[Example of the minimum point to point distance metric. Result is the average of all
minimum distances.]
The other method uses the Quadtree also to compute the minimum distance from
each point of the source image to the destination image, but in this case instead of using
the distance to compute the error, the value is compared and if it is less than the
threshold, an occurrences counter will be incremented.
C =
minDist(ps)f
else,
1
0
Correspondance =
n
5 = 0
Equation IV.6 Level1 Correspondence Value.
57


The numbers of occurrences of all the possible correct registration chains are
compared searching for the maximum value. The registration with the maximum number
of occurrences is the one that is chosen. This is the typical metric for the ICRP and the
purpose is to try to optimize the number of occurrences.
o


o

£valuatiDQ= caincidences
Figure IV.4 Point to Point Distance Threshold Metric.
[Example of the corresponding points metric. Result is the number of points that have a
point from the other cloud within the threshold.]
Range Images Characteristics. The previously described algorithm assumes that
the point clouds introduced have an overlapping surface large enough that it will always
be the greatest corresponding surface patches in each range image during the pairwise
comparison. To cover that requirement, the scans must be taken from the points of view
that guarantee that large enough area of overlap, this is dependent of the object to be
scanned in general 8 scans from approximately evenly distanced points of view around
the object are more than enough. In cases where the occlusions of different points of view
are moderated then the number of scans could be further reduced to 6 approximately
58


evenly distributed scans. In very low occlusion cases in which the scanner range is able to
cover a great area of the object, the number of scans can be extremely reduced to 4,
nevertheless, the scans must be taken from precise points such that each of them have
overlapping with the neighboring scans, some scan locations could result in 0 percent of
overlap between the range images.
It is also assumed that the resulting point clouds may include a certain level of
noise introduced by a low accuracy scanner. Even though a level of error is expected in
the point clouds, these imperfections should be small enough that they do not damage the
main shape or contour of the scanned objects; that could be translated into a simple mle
that the scanner inaccuracy error must be lower than the 5 percent of the general
dimensions of the objectin this way the scanned surfaces may be bumpybut retain
the overall object shape.
Batch Registration
The initial assumption is that the range images that are received contain no
information concerning their order or which range image is supposed to be registered
with the others. To solve this problem the approach consisted of after all the possible
pairs of range images with the first and the rest are computed, the metrics returned from
the pairwise registrations are used as reference. Depending on the metric the minimum
error or the maximum number of occurrences will determine which the corresponding
next range image is.
The process is repeated with the next range image and the remaining available.
But in order to include more details for the evaluation phase, the Quadtree is created with
all the range images that have been already registered. These steps are repeated until
59


there are no more available meshes or the remaining point clouds have been found not
coincident with the all the range images.
The result of this approach however is completely dependent of the order in
which the point clouds are explored which could lead to choose an incorrect first
alignment that would close the cycle prematurely, because some non-used point cloud
had no possible registration with the remaining range images.
Because of that, the solution was changed to a comparison between all the
possible pairs of point clouds. It starts by checking the point cloud with each other to find
the registration between them, from this possible registration the error was stored as a
metric of that match. After all the matches are computed, the point clouds are sorted
increasingly from their number of possible matches, those pairs of point clouds that have
at least 25 percent of level 2 collisions. Starting by the point cloud with the least number
of possible matches, the algorithm chooses the match that has the smaller level1 error
after the registration and then continues to the next point cloud in the sorted array. The
algorithm tries to find a route that goes through all the point clouds with no inner cycles
that has the least error possible. However, the results of this approach were not
satisfactory; this could be explained by the fact that the minimum distance average
depends of all the points and even the points outside the overlapping region account for
the error, leaving a big space for local minima.
To correct the influence of the non-corresponding area, the error metric was
substituted by the number of corresponding points between the pair. This approach
depends only of the points that are included in the found overlapping area and works as a
better judge for the correspondences.
60


CHAPTER V
EXPERIMENTAL RESULTS
Experimental Objectives
The experiments implemented to test the sets of range images were developed to
denote the first the better values needed to obtain a better performance of the hierarchical
structuresecond to understand the characteristics needed to obtain the correct
registration from the algorithm and third to find if given the correct range images set the
algorithm could perform a correct registration regardless the initial position of the
images.
Experimental Validation
To validate the correct operation of the suggested algorithm, a series of
experiments were implemented to give a metric of the solution effectiveness. The first
section describes the experiments conducted for the search of the best parameters for the
algorithms. The second section describes the experiments that were conducted to test the
effectiveness of the algorithm under different initial conditions, in this way determining
the limitations of the proposed solution. The algorithms were applied to real scans that
present a great deformation because of the external noise as well as virtual scans that
present no deformation at all.
61


Figure V.l Pairwise Registration (Virtual Data) a.
[Two range images in their original positions (left), range images coarsely registered
Parameter Settings
This section describes the experiments conducted in the search of the optimal
possible parameter settings for a general case implementation. The search comprehends
the size of the simplification structurethe histogram similarity threshold and the
minimum point to point distance.
Figure V.2 Multiple Range Images Registration (Real Data) b.
[Four range images in their original position (left), range images coarsely registered
(right)]
The first set of experiments utilized a batch of range images of both real and
virtual point clouds to define the level1 points array size. Since we know that the level 2
62


structures consists of 3 x 3 level1 points clustersthen the squared array of level1 must
be a multiple of 3 to obtain an exact division in the next hierarchical level. The level1
array sizes were set and the time of the pre-computations, the time of the coarse
alignment and the time of the fine alignment were registered for the analysis.
We can observe that for lower values of the level1 arrays, the pre-computation
time is very close. For the registration we can observe how the time increments
exponentially for every greater number of the arrays in both types of registration,
however the lower sizes return no convergence for the batch registration; the cause of this
is that the lower sizes fail to represent the level of detail needed for the feature
recognition, therefore we can determine that the optimal level1 size N=30. It is also
important to remark that the fine registration returns a very similar result after the coarse
registration with the configuration of 200 iterations and 85 percent of sampling and the
configuration of 50 iterations and 50 percent of sampling. This is because the coarse
alignment is close enough to the optimal solution of the ICP that the sampling and the
iterations can be reduced and it will still return a close fine registration.
Table V.l Array Size of Hierarchy Level1 Comparison. ______________________
Hierarchy coarse reg (s) fine reg (0.85, (oSs)
chair (18x18) 2.28559 2.26402 ( 6.85557 ( 1.32856
bunny (18x18) 14.8508 0.982171(*) 70.048 ( 50.3592H
chair (24x24) 2.31516 6.92665 (*) 8.21955(*) 1.55652 (
bunny (24x24) 15.3037 1.96898 71.7346 15.3615 (
chair (30x30) 2.10035 26.5006 6.95392 1.27321
bunny (30x30) 15.2254 8.4911 246.414 39.1164
(*) unsuccessful
63


Figure V.J Level1 Array Size vs. Alignment Time.
[Array size variation plot versus the time it takes for the coarse registration]
Table V.2 Histogram Minimum Similarity Comparison.
Percentage MeshO (s) Meshl(s) Mesh2 (s) Mesh3 (s) Mesh4 (s)
0.5 7.6253 22.8185 16.798 64.6028 7.42689
0.55 7.30578 19.65778 16.7844 59.1497 7.45987
0.6 7.21509 19.1144 16.8347 37.2055 7.42575
0.65 6.8943 18.8758 16.5256 26.5849 7.3879
0.7 6.56264 17.122 13.5719 24.3553 7.3215
0.75 5.68261 13.6497 11.9876 22.7952 7.25879
0.8 4.86804 11.8986 10.6945 20.3785 7.25806
0.85 4.12647 10.48979 9.16798 13.4889 6.9515
0.9 3.62845 8.39912 8.0273 11.3152 5.26888
0.95 2.8654 7.4798 8.51949 11.5378 6.12189
The histogram comparison works as a filter to accelerate the registration by
eliminating the pairs that could not be corresponding surface patches because of their
different surface properties. The meaning of the correct limit value means that a great
number of impossible registrations will be rejected and the time consumed analyzing
64


these incorrect solutions will be saved. The experiment took a pair of virtual range
images and the percentage of acceptance was incremented starting at 50 percent until 95
percent, the time was also registered for the analysis and the outcome of the registration.
We can observe that the registration time is reduced dramatically as the parameter
is increased, however at the point of 90 percent of similarity no correct registration is
found. The simple explanation for this is that the representations of the surface patches
are very similar but not identical because of all the information lost in the simplification
process. From these results it is possible to assume that an 80 percent of similarity will be
enough to filter the impossible registrations and to keep a safe margin of detection of
surface coincidences.
The minimum point to point distances is important to the chain of coincidences
creation and for the ICRP metric. That is why it is important to find the optimal value for
the threshold. Considering that the level 2 points are a grid that is spaced at a maximum
of md, the experiments take md as the threshold value and then a percentage of it is used
incrementally to observe the outcome of the registration.
Table V.3 Minimum Distance Threshold Comparison.____________________
md% MeshO Meshl Mesh2
0.5 ok ok ok
0.6 ok (*) ok
0.7 ok (*) (*)
0.8 e) (*) (*)
0.9 e) (*) (*)
1 e) (*) (*)
1.1 e) (*) (*)
(*) unsuccessful registration
65


The results of the experiments reflect that a 0.501nd is the optimal threshold value.
The explanation for this is that a point from the first point cloud that is correctly
registered at the second point cloud could be at maximum in the exact center between
two points in the grid. Greater values than this would account for incorrect coincidences
and the lower values would fail to account a number of correct coincidences.
Algorithm Validation
Once the optimal parameter settings were defined a series of experiments were
developed to find the effectiveness of the proposed solution. The experiments test the
needed overlapping area between the range images, the initial configuration of the range
images and as a reference point it compares the proposed algorithm with the ICP
alignment.
Figure V.4 Pairwise Registration (Real Data) c.
[Two range images in their original position (left), range images coarsely registered
Four Step Success Metric. As a point of reference of the proposed solution to
determine if a registration was correct, a four step metric was proposed. The test consist
of the ICP error before the fine registration and after the fine registration checking if the
error has indeed been optimized by the ICP algorithm after the coarse registration, then
the time it took to obtain the complete registration including the hierarchical structure
66


creation. The final step is the intervention of a person; that is because for the computer
the registration will be a success it it has found any similar surfaces large enough to pass
the threshold, even when it is an incorrect registration. Thanks to that the last metric is a
Boolean that describes if a human observes a correct registration.
This test was conducted to five pairs of corresponding point clouds. The point
clouds were chosen as two pairs of real data point clouds that included a moderate level
of noise that did not deform the overall shape of the objects (chair and car), then a pair of
virtual data point clouds with large uniform surfaces (car), and finally two pairs or high
quality real data point clouds with very unique surfaces (armadillo and dragon).
Table V.4 Proposed Algorithm Metric with ICP.
Test avg. Err visual Time (s)
Coarse Fine
1 0.00134022 0.00027788 ok 38.1657
2 0.0150338 0.00121589 ok 26.70233
3 0.00414668 0.00027621 ok 39.2548
4 0.0221134 0.01199 ok 3.931523
5 0.087418 0.0407408 ok 4.202232
Overlapping Area Percentage Test. The overlapping percentage test takes
several pairs of virtual range images that have a different percentage of overlapping
areas, the percentages will be registered as well as their outcome to find the minimum
required percentage.
67



Figure V.5 Registration with Different Overlapping %(Virtual Data).
[Range images with 91% overlap (left), 71% overlap (center) and 57% overlap
(right)]
Table V.5 Overlapping Area Comparison.
Mesh 2 Size 582
C. Points % Registration
531 91% ok
449 77% ok
412 71% ok
334 57% ok
299 51% ok
223 38% (*)
(*) unsuccessful registration
The result found in this experiment show that the minimum percentage of
overlapping area is near the 50 percent. This value could be reduced if all the threshold
values were modified, however that would beat the purpose of all the filters to speed up
the computations proposed in this work.
Initial Orientation and Translation Test. After all the possible parameters for a
correct range image registration have been defined, the reliability of the algorithm
depending on the initial orientation of the range images is tested. The two independent
experiments check first the impact of the original position in the outcome of the
68


algorithm and the second experiment checks the impact of the original orientation in the
outcome of the algorithm.
Table V.6 Initial Translation Comparison.
Test # axis Registration Time (s)
X y z
1 0 10 0 ok 2.3229
2 0 20 0 ok 2.8607
3 0 30 0 ok 2.85802
4 0 40 0 ok 2.14028
5 0 50 0 ok 2.9321
6 0 60 0 ok 2.1323
7 0 70 0 ok 2.1913
8 0 80 0 ok 2.2916
9 0 90 0 ok 2.87231
10 0 100 0 ok 2.24884
11 10 0 0 ok 2.0297
12 20 0 0 ok 2.42495
13 30 0 0 ok 2.8263
14 40 0 0 ok 2.25811
15 50 0 0 ok 2.937657
16 60 0 0 ok 2.6364
17 70 0 0 ok 2.8328
18 80 0 0 ok 2.2774
19 90 0 0 ok 2.24302
20 100 0 0 ok 2.604
21 0 0 10 ok 2.84403
22 0 0 20 ok 2.4831
23 0 0 30 ok 2.67634
24 0 0 40 ok 2.8785
25 0 0 50 ok 2.92775
26 0 0 60 ok 2.56092
27 0 0 70 ok 2.23414
28 0 0 80 ok 2.8514
29 0 0 90 ok 2.615
30 0 0 100 ok 2.51881
69


The experiments were conducted on a pair of virtual range images. The
translation test consists of moving one of the range images along the three axes, and
registering the outcome and the registration time. The measuring unit for the distance in
this case is in number of md.
The results of the experiment showed that the distance between point clouds did
not affect the outcome of the algorithm, which is an expected result because the
registration problem tries to optimize the distance between points in every proposed
solution.
The orientation test consisted in rotating one of the range images around the three
axes before registering the point clouds. The times used in the coarse registration as well
as the outcome of the registration are saved for the analysis.
The results of the experiment show that the registration algorithm works in almost
every original condition with the exceptions of the 90 and -90 degrees around the z axis,
this is because it does the rotation angle computations as a 2D planes and when a vector
is aligned with the axis it would need a division by 0 which is an error. To solve the
problem the orientation of that range image can be slightly modified to avoid the division
by 0.
70


Table V.7 Initial Rotation Comoarisoii.
Test # axis result Time (s)
X y z
1 0 120 0 ok 3.26741
2 0 105 0 ok 3.10508
3 0 90 0 ok 2.95553
4 0 60 0 ok 2.89061
5 0 45 0 ok 2.8652
6 0 30 0 ok 2.9798
7 0 15 0 ok 2.88929
8 0 0 0 ok 2.865
9 0 -15 0 ok 2.9395
10 0 -30 0 ok 2.8955
11 0 -45 0 ok 2.95787
12 0 -60 0 ok 2.8761
13 15 0 0 ok 2.55171
14 30 0 0 ok 2.2581
15 45 0 0 ok 1.446
16 60 0 0 ok 1.4493
17 75 0 0 ok 0.979754
18 90 0 0 (*) 0.5094
19 -15 0 0 ok 2.79991
20 -30 0 0 ok 1.89071
21 -60 0 0 ok 1.3987
22 -75 0 0 ok 1.23147
23 -90 0 0 (*) 0.9725
24 0 0 15 ok 2.38713
25 0 0 20 ok 2.24819
26 0 0 30 ok 2.838
27 0 0 45 ok 2.1845
28 0 0 75 ok 2.4876
29 0 0 90 ok 2.0678
30 0 0 -15 ok 2.88564
31 0 0 -30 ok 2.7849
32 0 0 -45 ok 2.55325
33 0 0 -60 ok 2.9818
34 0 0 -75 ok 2.53817
(*) unsuccessful registration


Figure V.6 Pairwise Registration (Virtual Data) d.
[Two range images in their original position (left), range images coarsely registered
(right)]
Comparison VS ICP Test. As a point of reference of the proposed solution and
other known solution this test is proposed. It uses a pair of range images with an
overlapping area of more than 90 percent; this high overlap would guarantee that the ICP
algorithm sampling would include a great number of coincidences even with low
sampling percentages. The test uses the virtual range images and positions them in very
close transformation, near to the correct orientation and translation, these settings would
not affect the proposed solution because it would still follow the same steps in the
instruction pipeline but it would be a good starting position for ICP. The experiments
used the same initial configuration for the range images and then the ICP parameters are
modified. The test registers the time it takes for the coarse registration and compares it
with the ICP outcomes.
72


Table V.8 ICP vs. Proposed Algorithm Comparison.
Sampling Iterations Time (s) Registration
0.85 200 35.5605 ok
0.6 200 26.9691 ok
0.5 200 20.5639 ok
0.85 100 9.77807 ok
0.5 100 11.799 ok
0.85 75 16.6375 ok
0.5 75 9.615 ok
0.85 50 13.0386 ok
0.5 50 7.3779 ok
0.85 25 8.41521 ok
0.5 25 5.27012 ok
Proposed Algorithm 8.78023 ok
Figure V.7 Full Registration Coarse and ICP (Real Data).
[Five range images coarsely registered from 3 different points of view]
73


Figure V.8 Full Registration Coarse and ICP (Virtual Data).
[Six range images coarsely registered (left), range images finely registered (right)]
Figure V.9 Un-ordered Range Images (Real Data).
[Ten range images in their original position]
Figure V.10 Un-ordered Range Images Coarse Registration (Real Data).
[Range images coarsely registered back and front]
74


Figure V.ll Fine Registration (Real Data).
[Range images finely registered back and front]
75


CHAPTER VI
CONCLUSIONS
Experimental Conclusions
The objective of this work was to develop an algorithm that is capable of
registering unordered range images with error induced from faulty scanning devices, to
solve this problem this work proposed an innovative method for the automatic range
image registration that combines different types of registration, the optimization of a
metric, the feature recognition and an exhaustive search of the transformation range with
a multilevel hierarchical structure that reduces the complexity of the match evaluation but
maintains level of detail enough to differentiate possible matches.
After the experimentation conducted on the algorithm, it can be observed that the
proposed hierarchical level approach helps to optimize the asymptotical time of the
registration problem. The utilization of the feature recognition filters also help to reduce
greatly the search space by eliminating all of the trivial solutions.
Compared to other proposals with hierarchical levels or feature recognition,
instead of consisting only of two levels and that are the complete point clouds or a few
points, the utilization of the multiple levels is an improvement in the sense that it can
keep valuable information for the registration at hand and be used as well as a
simplification of discarding unviable solutions.
The last point that I would like to remark is that the definition of the simplified
mesh consists of a known maximum number and that this compared to the approaches
referenced in this work will reduce all the range images independently of the number of
points in the range image. And that in real world applications like in some of the sets that
76


were used in this project the simplification would be detailed enough to find the surface
properties and neglect the error induced by the scanner noise, while the feature detection
approaches mentioned before would still recognize the noisy features.
Limitations
The proposed solution is limited to cases in which the objects shape is unique
enough to be differentiated from each different point of view. That is because spherical
shapes in general, cubic shapes, or other completely symmetrical objects would find
absolute minima in the same shapes that would not reconstruct the object but instead
would treat them as barely the same scan repeated several times.
Because of the point simplification process the algorithm is supposed to work in
cases where the contour is enough to find correspondences. If the details are absolutely
necessary to find correct correspondences, then this approach would not be able to do it
correctly, however the assumption of a noisy scan means that the level of detail is not
good enough for those cases.
The results of the experiments conducted to the different types of range images
showed that as many other previous approaches this solution still finds correspondences
for large surfaces of similar curvature even when they are not correct correspondences.
This problem can be reduced by the type of scans that are delivered to the program. With
a greater area of overlap between the range images, the greatest patch that can be found
would be the corresponding overlapping areas of each point cloud. However, the
unordered batch alignment for very uniform surfaces like chairs, cars, etc., translates into
a greater problem, since possible matches could be found in almost every pair. In these
cases the possible solution is to solve the registration in the delivered ordered cycle.
77


Future Work
The results obtained from this work leave the door open for improvement by
using some of the related works as reference. The use of the same structure configuration
to parallelize the multi-view range images registration and speed up the process used in
[2] as well as the update of the complete structured registered could be adapted to the
proposed solution. Another area of opportunity is present in the evaluation metric of the
registration; the algorithm uses the ICP or ICRP metrics, however these methods are
known to be faulty in the sense that there may exist absolute minimum values that are not
the correct solution. The research of an extra constraint to neglect the non-coincident
absolute minimum value is a matter of great importance for this and any other work
related to the registration.
Lastly, the most obvious derivation from this work is the improvement of the fine
registration process. ICP uses a randomized sampling process to select the points that will
be optimized for the fine registration, however choosing a small sample the algorithm
may receive points outside the overlapping areas of the point clouds, and therefore it
becomes necessary to use a greater sample. The use of a large sample makes a very
expensive process, but considering that the coarse registration is close enough and that
the hierarchical structure is already detecting the intersections between the point clouds
then it could be possible to pass that information so that the sampling is only to be done
in the intersecting areas.
78


REFERENCES
1.FukaiH+; XuG.Fast and Robust Registration of Multiple 3D Point
0^^, RO-MAN, 2011 IEEE, pp. 331-336, 31 Jul.-3 Aug. 2011.
2. MakadiaA.; PattersonA.; DaniilidisK.Fully Automatic Registration of 3D
Point CloudsComputer Vision and Pattern Recognition, 2006 IEEE Computer Society
Conference on, vol.1,pp.1297-1304, 17-22 Jun. 2006.
3. WingbermiihleIRobust Registration of Coarse Binary Volume Models
Pattern Recognition, 2000. Proceedings. 15th International Conference on, vol.1,pp.
4. MianA.S.; BennamounM.; OwensR.A.Automatic Multiview Coarse
Registration of Range Images for 3D Modeling^, Cybernetics and Intelligent Systems,
2004 IEEE Conference on, vol.1,pp. 158-163,1-3 Dec. 2004.
5. Jiajing Dai; Jie YangA Novel Two-Stage Algorithm for Accurate
Registration of 3-D Point Clouds^, Multimedia Technology (ICMT), 2011 International
Conference, pp. 6187-6191, 26-28 Jul.2011.
6. LiuY.et alRange Image Registration Using Hierarchical Segmentation and
ClusteringCoW+/////ce + /2009/E
International Symposium, pp 328 333, 15-18 Dec. 2009
7. KrsekP.et alRange Image Registration Driven by a Hierarchy of Surface
Differential Features^, 22nd Workshop of the Austrian Association for Pattern
Recognition 1998
8. RusuR.et alFast Point Feature Histograms (FPFH) for 3D Registration
Robotics and Automation, 2009. ICRA r09. IEEE International Conference on, pp 3212 -
3217, 12-17 May 2009
9. Smisek, J., et al,U3D with Kinect,,5 Computer Vision Workshops (ICCV
Workshops), 2011 IEEE International Conference on, pp 1154-1160, 6-13 Nov. 2011
10. Narvaez, A.; Ramirez, E., UA Simple 3D Scanner Based On Passive Vision
for Geometry Reconstructionyacrios; /^
America Latina), pp 2125-2131, Sep. 2012
79


Full Text

PAGE 1

AUTOMATIC RANGE IMAGE REGISTRATION USING HIERA R CHY LEVELS AND FEATURE RECOGNITION FILTERS by ALEJANDRO DANIEL ALONSO B.S., Instituto Tecnologico y de Estudios Superiores de Monterrey, 2009 A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Master of Science Computer Science 2013

PAGE 2

ii This thesis for the Master of Science degree by Alejandro Daniel Alonso has been approved for the Computer Science Program by Min Hyung Choi Chair Gita Alaghband Ellen Gethner 11/13 /2013

PAGE 3

iii Alonso Alejandro Daniel ( M.S. Computer Science ) Automatic Range Image Registration U sing Hierarchy Levels and Feature Recognition Filters Thesis directed by Professor Min Hyung Choi ABSTRACT There are numerous approaches that solve the registration problem; from the extensive ICP. However ICP is only able to work correctly when the images are close enough to the correct position. Another problem is the pairwise nature of r egistration, meaning that each correspond ing range image match must be known beforehand for a complete batch of scans This work proposes a novel approach that is able to align a set of unordered range images without knowing the correspondence between them to the point that ICP is able to succeed in its optimization Consisting of a multilevel hierarchical structure parallel to the ones used in collision detection problems this work aims to reduce unnecessary processes in registration pipeline by simplifyin g the point clouds and evaluating and filtering possible matches at the different levels of hierarchy as well as filtering possible matching points by comparing surface descriptors. The results found from the experiments conducted to the proposal verify bo th numerically and visually that the outcomes are effective with real and virtual range images. The form and content of this abstract are approved. I recommend its publication. Approved: Min Hyung Choi

PAGE 4

iv DEDICATION I dedicate this work to my parents who have given me th is great opportunity of studying abroad And especially to Alejandra Sanchez for encouraging me to take this opportunity and cheering me up whenever I found deadlocks in this work.

PAGE 5

v ACKNOWLEDGMENTS I would like to thank my advisor Dr. Choi who gave me numerous advices for my thesis project and for the high level of exigency that he demanded of me which lead me to a satisfactory result. I thank all the members of the computer graphics lab which heard my advances and offered some advices. Finally I thank Shane Transue who implemented the core program which enabled me to focus completely in the main topic of my research.

PAGE 6

vi TABLE OF CONTENTS CHAPTER I. INTRODUCTION ................................ ................................ ................................ ........ 1 3D Scanning Overview ................................ ................................ ........................ 1 Range Image Overview ................................ ................................ ........................ 3 Registration ................................ ................................ ................................ .......... 4 Types of Registration ................................ ................................ ..................... 4 Registration Types Analysis ................................ ................................ ........... 5 Objective ................................ ................................ ................................ ............. 6 Work Outline ................................ ................................ ................................ ....... 6 II. AUTOMATIC REGISTRATION LITERATURE REVIEW ................................ ....... 8 Related works ................................ ................................ ................................ ...... 8 Fast and Robust Registration of Multiple 3D Point Clouds ............................. 8 Fully Automatic Registration of 3D Point Clouds ................................ ......... 10 Robust Registration of Coarse Binary Volume Models ................................ 14 Automatic Multiview Coarse Registration of Range Images for 3D Modeling ................................ ................................ ................................ ..................... 16 A Novel Two Stage Algorithm for Accurate Registration of 3 D Point Clouds ................................ ................................ ................................ ..................... 21 Possible Related Works Shortcomings ................................ ............................... 23 III. HIERARCHICAL STRUCTURE ................................ ................................ ............ 26 Point Cloud Simplification ................................ ................................ ................. 26 Simplification Proposals ................................ ................................ ............... 2 6 Point Cloud Hierarchy Structure ................................ ................................ ... 29 Point Simplification Process. ................................ ................................ .. 31

PAGE 7

vii Hierarchical Structure Construction. ................................ ....................... 34 Neighborhood Descriptors ................................ ................................ ................. 38 Ring Simplification Normal Vectors ................................ ............................. 38 Ring Simplification Normal Vectors Layers ................................ ................. 39 Local Invariant Feature ................................ ................................ ................. 39 Local Feature Histograms ................................ ................................ ............. 41 IV. AUTOMATIC REGISTRATION ................................ ................................ ............ 47 Pair Wise Transformation Computation ................................ ............................. 47 Transformation Computation Proposals ................................ ........................ 47 Ring Simplification Comparison. ................................ ...................... 48 Ring Simplification Layered Comparison. ................................ ........ 49 Registration Using Hierarchy Levels and Descriptor Filters .......................... 50 Points Pairs Search. ................................ ................................ .......... 51 Points Pairs Filters. ................................ ................................ ........... 52 Chain Search. ................................ ................................ .................... 54 Possible Registration Evaluation. ................................ ...................... 55 Range Images Characteristics. ................................ .......................... 58 Batch Registration ................................ ................................ .............................. 59 V. EXPERIMENTAL RESULTS ................................ ................................ .................. 61 Experime ntal Objectives ................................ ................................ .................... 61 Experimental Validation ................................ ................................ .................... 61 Parameter Settings ................................ ................................ ........................ 62 Algorithm Validation ................................ ................................ ................... 66 Four Step Su ccess Metric. ................................ ................................ 66 Overlapping Area Percentage Test. ................................ ................... 67

PAGE 8

viii Initial Orientation and Translation Test. ................................ ............ 68 Comparison VS ICP Test. ................................ ................................ 72 VI. CONC LUSIONS ................................ ................................ ................................ ..... 76 Experimental Conclusions ................................ ................................ .................. 76 Limitations ................................ ................................ ................................ ......... 77 Future Work ................................ ................................ ................................ ....... 78 REFERENCES ................................ ................................ ................................ .............. 79

PAGE 9

ix LIST OF TABLES T able III.1 Local Invariant Feature Comparison with Hierarchy Level 2. ................................ 41 V.1 Array Size of Hierarchy Level 1 Comparison. ................................ ........................ 63 V.2 Histogram Minimum Similarity Comparison. ................................ ......................... 64 V.3 Minimum Distance Threshold Comparison. ................................ ........................... 65 V.4 Proposed Algorithm Metric with ICP. ................................ ................................ .... 67 V.5 Overlapping Area Comparison. ................................ ................................ .............. 68 V.6 Initial Translation Comparison. ................................ ................................ .............. 69 V.7 Initial Rotation Comparison. ................................ ................................ .................. 71 V.8 IC P vs. Proposed Algorithm Comparison. ................................ .............................. 73

PAGE 10

x LIST OF FIGURES Figure I.1 Example of 3D Scan Point Cloud. ................................ ................................ ............. 1 I.2 Range Image Acquisition. ................................ ................................ .......................... 3 II.1 Search Space Plot. ................................ ................................ ................................ .... 9 II.2 Equally Spaced Grid. ................................ ................................ .............................. 10 II.3 Point Cloud Orientation Result with [2]. ................................ ................................ 12 II.4 Point Cloud False Orientation Result with [2]. ................................ ........................ 12 II.5 Constellation Image Example. ................................ ................................ ................ 13 II.6 Turntable Scan Example. ................................ ................................ ........................ 14 II.7 Octree Example. ................................ ................................ ................................ ..... 16 II.8 Tensor Example. ................................ ................................ ................................ .... 18 II.9 Registration Results for [4] ................................ ................................ .................... 20 II.10 Local Invariant Feature for [5]. ................................ ................................ .............. 21 II.11 Example of the Coarse Registration for [5]. ................................ ........................... 22 III.1 Divisi ons Along the Transversal Axis (Horizontal). ................................ ............... 27 III.2 Ring Simplification Example. ................................ ................................ ................ 28 III.3 Range Images with 0% Overlap and Ring Simplification Match. ........................... 28 III.4 Hierarchical Structure. ................................ ................................ ........................... 29 III.5 Ordered Simplified Points Mesh ................................ ................................ ........... 33 III.6 Range Images with Level 1 Hierarchy. ................................ ................................ ... 35 III.7 Range Images with Level 2 Hierarchy. ................................ ................................ ... 37 III.8 Range Images with Level 3 Hierarchy. ................................ ................................ ... 38

PAGE 11

xi IV.1 Chain Creation Diagram. ................................ ................................ ....................... 49 IV.2 Incremental Orientation. ................................ ................................ ........................ 54 IV.3 Point to Point Distance Metric. ................................ ................................ .............. 57 IV.4 Point to Point Distance Threshold Metric. ................................ .............................. 58 V.1 Pairwise Registration (Virtual Data) a. ................................ ................................ .... 62 V.2 Multiple Range Images Registration (Real Data) b. ................................ ................. 62 V.3 Level 1 Array Size vs. Alignment Time. ................................ ................................ 64 V.4 Pairwise Registration (Real Data) c. ................................ ................................ ........ 66 V.5 Registration with Different Overlapping %( Virtual Data). ................................ ...... 68 V.6 Pairwise Registration (Virtual Data) d. ................................ ................................ .... 72 V.7 Full Registration Coarse and ICP (Real Data). ................................ ........................ 73 V.8 Full Registration Coarse and ICP (Virtual Data). ................................ ..................... 74 V.9 Un ordered Range Images (Real Data). ................................ ................................ ... 74 V.10 Un ordered Range Images Coarse Registration (Real Data). ................................ .. 74 V.11 Fine Registration (Real Data). ................................ ................................ ............... 75

PAGE 12

xii LIST OF EQUATIONS Equation II.1 Computation of Rotation. ................................ ................................ ......................... 9 II.2 Angle computation for [1]. ................................ ................................ ....................... 9 II.3 Distance evaluation for [1]. ................................ ................................ .................... 10 II.4 Computation of Rotation for [2]. ................................ ................................ ............ 11 II.5 Computation of Transformation with SOFT for [2]. ................................ ............... 13 II.6 ICP Error for [3]. ................................ ................................ ................................ .... 15 II.7 Minimum Po int to Point Distance [3]. ................................ ................................ .... 15 II.8 Weighted Error for [3]. ................................ ................................ ........................... 15 II.9 Mesh Dimensions Approximation for [4]. ................................ .............................. 17 II.10 Tensor Computations Max for [4]. ................................ ................................ ........ 17 II.11 Tensor Computations Min for [4]. ................................ ................................ ........ 17 II.12 Correlation Coefficient for [4]. ................................ ................................ ............. 19 II.13 Least Square Fitting Coefficient for [5]. ................................ ............................... 22 II.14 Proximity Constraint for [5]. ................................ ................................ ................ 23 III.1 Bin Size. ................................ ................................ ................................ ............... 31 III.2 Bin Horizontal Boundaries. ................................ ................................ ................... 31 III.3 Bin Vertical Boundaries. ................................ ................................ ....................... 32 III.4 Axis Aligned Bounding Box. ................................ ................................ ................ 32 III.5 Level 1 Simplified Points. ................................ ................................ ..................... 32 III.6 Neighboring Simplified Points. ................................ ................................ ............. 33 III.7 Simplified Points Quad Normal. ................................ ................................ ........... 33

PAGE 13

xiii III.8 Simplified Points Vertex Normal. ................................ ................................ ......... 33 III.9 Level 2 Bounding Sphere Initial Radius. ................................ ............................... 36 III.10 Level 2 Bounding Sphere Center. ................................ ................................ ........ 36 III.11 Level 2 Radius Rectification. ................................ ................................ .............. 36 III.12 Ring Simplification Normals. ................................ ................................ .............. 38 III.13 Histogram Local V Axis. ................................ ................................ .................... 43 III.14 Histogram Local W Axis. ................................ ................................ .................... 43 III.15 Histogram Angle. ................................ ................................ ............................. 43 III.16 Histogram Angle. ................................ ................................ ............................. 43 III.17 Histogram Angle. ................................ ................................ ............................. 43 I V 1 Histogram Similarity ................................ ................................ ............................ 53 I V 2 Level 3 Collision ................................ ................................ ................................ 55 I V 3 Level 2 Collision. ................................ ................................ ................................ 55 I V 4 QuadTree Axis Division. ................................ ................................ ...................... 56 I V 5 Level 1 Distance Error. ................................ ................................ ......................... 56 I V 6 Level 1 Correspondence Value. ................................ ................................ ............ 57

PAGE 14

1 CHAPTER I INTRODUCTION 3D Scanning Overview In the last years the number of scanning devices available in the market has been evolving and each time the accuracy and cost competitiveness has been improved, to a point that in a not so distant future general public might have access to this technology for their own necessities. Although we are still not to the point where general public has access to this technology, the current industry has a good number of varied implementations for these devices, among them we can mention the reverse engineering pro cess in which engineers are able to recreate a object to interact with it in their CAD/CAM software, they are also used to recreate sceneries in computer graphics software for entertainment purposes as well as terrain construction for robot navigation loca lization and object recognition and even in medical application like tomography reconstruction The great varieties of 3D scanning devices, based on stereo cameras, infrared cameras, laser time of flight among other novel approaches, are able to measure ob jects from our 3D world and transform them into sets of data points that are known as point clouds. Figure I 1 Example of 3D Scan Point Cloud [ A point cloud result of a laser based 3D scan .]

PAGE 15

2 The real data used in this work are point clouds that were obtained with the help of a laser based scanner that introduced a measurement error result of that it is necessary to scan objects that are big enough such that the error does not deform the m ain shape of the object However in the recent years new low cost methods have been developed such that it could be possible to implement these approaches to this work. Some of the most outstanding cost effective methods available are the RGB D based scan s, Kinect, and vision based, photographs. Kinect uses a set of IR projector and sensor and a RGB camera to obtain the physical characteristics of the scanned scene. The IR projector emits a characteristic pattern to the environment, th is is invisible to th e human eye and this pattern deformation is checked by the IR sensor and later used to triangulate the corresponding point depth. The RGB image obtained from the camera is complemented with the depth computations giving as a result an image that has RGB D information per pixel. Vision based approach attempts to replicate the human vision system by obtaining two images from different points of view. A system is constructed with two coupled cameras emulating human eyes Each of the cameras obtain the images from different points of view of the same object, then with the help of the computer vision algorithms the edges of the image are detected in each of them. After that f rom the edge detection results, the characteristic points are chosen and this creates a point cloud for each image. The point clouds so far still correspond to a 2D image, to convert to a 3D point cloud it starts by determining the corresponding points pairs from both images ; these pairs of points are then used to compute the depth by fin ding the projection from each camera to the point that has approximately the same depth.

PAGE 16

3 Range Image Overview It is found frequently cases in which the devices are not able to obtain all the information of the complete scanned object in just one take because the scanner has a limited field of view T o solve this problem, in cases where it is a small object that is being scanned an easy solution could be to place the object in a rotating turntable, however even this might not be a good enough solution to obtain all the corresponding information; in these cases more range images, new scans that obtain only partial views of the object, must be performed to complete the surface of the scanned object The result is a set of images of the same object that ho ld an unknown relation between them. For t he new range images each of them contains their own independent coordinate system and six degrees of freedom which poses a new problem to t his application, a registration. Figure I 2 Range Image Acquisition [ Example of scanner range and necessity of range images]

PAGE 17

4 Registration Range image registration is the search of a relation or Euclidian motion (orientation and position) between matching range images in order to reconstruct th e original object with the range images under the same coordinate system Types of Registration Registration can be categorized in three types by how the correspondence between range images is explored The first type corresponds to the feature matching; t he algorithms that use this approach find features that are present in both range images and find the Euclidian motion based on these features findings. The second type corresponds to an optimal configuration of the points; this type of algorithms tries to find a minimum value for certain criteria by modifying the Euclidian motion of the range images. The last type corresponds to finding the camera motion; in this case, the algorithms try to find the location of the camera for each range image to transport the range images to the same coordinate system. Besides th e previously explained categorization system, registration algorithms can be categorized in two levels. The first level or coarse level registration refers to the initial guess in which no information is available between range images and a rough approximation is sought. The second level or fine level registration refers to the registration of range images after an initial guess has been obtained or certain information has been given to the algorithm to find the optimal configuration of the range images.

PAGE 18

5 Registration Types Analysis Some solutions to the registration problem include the incorporation of electro mechanical or positioning devices to the scanners in order to obtain the scanner mo tion. These solutions might not be the best possible solutions available, since it might limit the working area or increment the complexity of moving the device. Other scanner motion computation algorithms may find the transformation between range images w ithout the electro mechanical devices; however they are limited by small movements between the scans or the use of external information from the user. Several algorithmic approaches to solve the automatic registration with optimal configuration have been p roposed in all these years. The most commonly used algorithm is the iterative closest point algorithm (ICP), which calculates the minimum point to point distance between two point clouds. The ICP algorithm has the disadvantage that it could converge to a l ocal minimum between its iterations and most importantly that a bad initial positioning of the two clouds inflict s a major risk of finding local minima and incorrect registrations That inconvenient with the ICP algorithm means that it needs a prior approx imation to the original positioning of the range images. Even with the local minima problem, this type of registration is highly effective and the most frequently used for the fine level registration. The coarse registration takes charge of computing an i nitial guess for each point cloud motion, without any previous motion information, some approaches are based on finding specific features in the different point clouds that could match, while others rely on finding matching relations between points and nei ghbors from different clouds; in several commercial products the coarse registration is achieved by interaction with the

PAGE 19

6 user. The output from the coarse registration is taken by the fine registration algorithm and they are further registered in detail by those algorithms, for example ICP. Objective Previous approaches like the feature matching algorithms have the disadvantage that features may be altered by external noises during the scanning process and correspondence may not be found because of that, extensive search of the degrees of freedom approaches are expensive in computing resources and time consuming and possible incorrect absolute minimum is still highly possible ; to improve the time of execution hierarchical approaches have also been proposed however th ese proposals have the problem that the two level simplification leaves out many details of the point clouds that help to improve the match evaluation Besides the pairwise registration shortcomings, the necessity of information about the order of a range images batch becomes a new problem for the batch registration Taking into account these situations, t he objective of this work is to develop a process that is able to coarsely register a set of unordered range images with no information of their orientation or translation close enough to be refined with the final step of ICP and that taking the advantage of the several hierarchical levels it is able to reduce the influence of external noises present in feature recognition algorithms and red uce the extreme computations exploration algorithms have Work Outline The remaining part of this work consists of the following points: Automatic registration background, which summarizes a few previ ous related works in this field.

PAGE 20

7 Automatic Registration this part explains the proposed methods to obtain the coarse registration some of the previously researched proposals and all the details and structures needed to register the range images Experime ntal Results explores all the experiments that were conducted on the final version of the proposal to determine its effectiveness or to determine the minimal requirements of the proposed solution. The c onclusions section contains the analysis of the solution outcome and compares it to other approaches highlighting the advantages of this method.

PAGE 21

8 CHAPTER II AUTOMATIC REGISTRATION LITERATURE REVIEW Related works This section focuses on exploring the previous works related with automatic registration that have been influential for this work Each algorithm will be explained as concisely and simply as possible to supplement an overview that will enable the reader to comprehend the nature of the algorithm. Fast and Robust Registration of Multiple 3D Point Cl ouds This work by Hironobu Fukai and Gang Xu [1] is a proposed method to solve the coarse registration problem with the application of matching exhaustive searches. We should consider the problems rel ated to the alignment process: e very independent range i mage is located in its own independent coordinate system that is defined by it location defined by a relation of a 6 degrees of freedom. We should also consider the or iginal model has its own coordinate system with its corresponding 6 degrees of freedom. If the relation between the model and the scans coordinate system is known, then it is easy to transform them to obtain the original model, however this is rarely the c ase. To solve the correspondence between the different range images to recover the original model the use of the point to point distance can be used to minimize the least mean square error between them, but this often converges to local minima that are not even close to the model, and trying to find a proper local minimum in the entire search space is a large task to do.

PAGE 22

9 Figure II 3 Search Space Plot [This plot shows the error found for a certain position; it exemplifies the presence of local minima and a global minimum which corresponds to the best guessed orientation [1] ] The proposed solution for this coarse registration is the use of exhaustive search that had already been proven to be effective before. The 6 degrees of freedom spaces are explored by computing several initial alignments guided by the model shape. To reduce the number of possible initial positions the proposed initial positions are compared with the help of the following formulas: Equation II 1 Computation of Rotation Equation II 2 Angle computation fo r [1] extremum value, then this initial guess is suppressed from the exhaustive search. With this final list of candidates with all the non extremum values suppressed, the ICP alignment is applied to each of the possible solutions, and evaluated to find the optimal solutions.

PAGE 23

10 The distance evaluation uses a weighted method in which the distance threshold determines if an element is added to the evaluator or not: Equation II 3 Dist ance evaluation for [1] Fully Automatic Registration of 3D Point Clouds Makadia, et al [2] propose in their work the use of extended Gaussian images compute the orientation between two range images. Figure II 4 Equally Spaced Grid [ The point clouds are enclosed in the spherical bounding body, the body is divided in equally spaced (angular wise) bins. Each bin contains the points that are projected into its space [2] ] Using global representations for range images with EGIs, which are based on the collection of surface normals, gives the advantage of orientation recognition without the translation interference. By deta iled feature recognition, the rotation between two point clouds can be estimated given the requirements that there is a large enough overlap area between both clouds and that this data is not deformed so that it is possible to find the

PAGE 24

11 same feature in both clouds. This approach proposes to use an exploration of the rotation range to find the fittest rotation between two clouds. This computation is proven to be greatly reduced by the use of spherical Fourier analysis with the requirement that the histogram b ins are uniformly separated on the sphere (with respect to the angles). The computation of the rotation between the range images has no previous knowledge, to find this relation all the rotations R SO (3) must be considered, to do this a scored likelihoo This methodology is very similar to the correlation of planar functions, which can be expressed as simple pointwise multiplication in the Fourier realm, and thanks to FFT extended to the sphe rical situation, the correlation computation is drastically sped up with SO(3) Fourier Transform (SOFT). Equation II 4 Computation of Rotation for [ 2 ] Where H1 and H2 are the EGI points of the scans in the SOFT, G contains the re sulting Euler angles between the H1 and H2 points. This reflects the similar properties of a generalized convolution, by multiplying point to point the individual SFT coefficients and finally retrieving the desired G(R) with the inverse SOFT.

PAGE 25

12 Figure II 5 Point Cloud Orientation Result with [ 2 ] [ The program computes the EGI and later aligns them with the corresponding dominant features [2] ] This approach is proven to be effective, the alignment between two EGI is successful when they have high overlap; nevertheless, in cases where the overlap space is minimal points are disproportionately populated around and non overlapping surface regions the method would fail to identify the correct orientation. Figure II 6 Point Cloud False Orientation Result with [2] [ The an incorrect alignment. [2] ] A dominant peak in the EGI is helpful in the sense that it could exist in both range images and in that case those two would align. But if the dominant peak is not included in the overlapping surfaces or this dominant peak is not even in any of the scans, then this would affect the process. Because of this the proposed solution to this problem is to convert the EGI into a constellation image; this is achieved by keeping the local maxima

PAGE 26

13 and eliminating the remaining bins. The use of constellation images mig ht also encounter incorrect alignments if the non overlapping areas highly contribute with local maxima, but it reduces the chances of collecting the majority of normals from non overlapping areas. Figure II 7 Constellation Image Example [ Example of an image range, its corresponding EGI and the constellation image belonging to that EGI [2] ] For the translation computation, it is assumed that the correct alignment is achieved where the greatest correlation of the two rang e images is found. Using the same correlation principles the correct translation maximized the function: The point clouds are voxelized such that a voxel is much larger than the fine resolution of the scanner. Since this is a convolution integral then it c an be simplified with the Fourier transform as a multiplication. Then the coefficients can be recovered from the Fourier Transform. Equation II 5 Computation of Transformation with SOFT for [2]

PAGE 27

14 The last step is a verification that consists of voxelizing the space after the alignment and measuring the consistency by accumulating the difference for the overlapping voxels. The difference is weighted by the voxel point population. And for known scanner if the alignment makes one point cloud occupy the space between the other point cloud and the scanner occluding the visibility, then this alignment is also discarded. Robust Registration of Coarse Binary Volume Models In his work Wingbermhle [3] captures objects with the help of a turntable that allows him to obtain the complete peripheral surface of that object, but in order to obtain the complete surface he re orients the object to scan other points of view. These two scans are later registered to recover the original object. Figure II 8 Turntable Scan Example [ The two scans from two different orientation of the elephant sculpture [3] ] For the coarse alignment the six parameters of both range images have to be aligned trying to obtain the best possible initial values and prevent the local minimal convergence of the ICP. A known technique to obtain good initial values is to align the centers of gravity and principal axis for both clouds, but th is technique is also affected by the errors obtained in the different scans. To avoid the error influence, the initial values are verified through the ICP error; a error threshold is determined and compared with the

PAGE 28

15 initial values ICP error obtained, if it is greater than the error then it is discarded and a better set of initial values is searched by rotating the second range image around the three axes 15, finally the combination of angles around the three axes that result in the smallest error are chose n as the definitive initial values. Equation II 6 ICP Error for [3] Equation II 7 Minimum Point to Point Distance [3] Where the N is the number of points of both range images and the dividend are the minimum distances point to point from range image 1 to 2 and vice versa. These contributions are optimized by the use of a distance octree. Each range image is organized in an octree that starts as the total bounding box and is recursively divided into eight equal sized boxes when a certain limit of points is reached; the division stops when all the cloud points have been added and all the empty leaves are eliminated. And tha nks to this structure the division edges are now used as unsigned distance approximations to compute the contributions. The last step is to explore the six degrees of freedom spaces and iteratively trying to optimize the weighted error criterion: Equation II 8 Weighted Error for [3]

PAGE 29

16 Where the first part is the simplified ICP error and the second part is the weighted correlation term, where Vs is the section volume and V1 and V2 are the model respective volumes. The second term helps to prevent the local minima convergence, although it may still converge to these values and if during the optimization process the greater volume contains completely the smaller volume, this second term will disappear from th e equation leaving it as a regular ICP algorithm. Figure II 9 Octree Example [ Example of the octree created from t he elephant scan [3] ] Automatic Multiview Coarse Registration of Range Images for 3D Modeling Mian et al [4] propose in their work to attack the registration problem by registering more than two cloud points at a time, taking advantage of all the information generated in each point cloud to point cloud comparison and eliminating the unnecessary computations r epetitions. which are 4 dimensional data structures. Each point cloud is converted into triangular meshes and reduced after that the normals of the resulting mesh are calculated for each

PAGE 30

17 one of the vertices. When all the normals are computed, the three approximate dimensions of the mesh are computed like this: Equation II 9 Mesh Dimensions Approximation for [ 4 ] Where Vi is the original point cloud Pi is the rotation matrix that aligns Vi to its principal axis and therefore max and min obtain the maximum and minimum points of the mesh in x, y and z when it is aligned along its principal axis. This step is repeated for eve ry range image acquired. The next step is to compute the corresponding tensor for each reduced mesh. To construct the tensors, the vertices are paired in such a way that the distance between the pairs is within the following limits: Equation II 10 Tensor Computations Max for [4] Equation II 11 Tensor Computations Min for [4] Where Dx, Dy and Dz are the component in x, y and z of the mean of all the different range images dimensions. The ver tices are grouped in a maximum of 4 vertices and from all this groups a maximum nt groups are chosen such that they are uniformly spread over the mesh, which in this case was nt = 300. For each pair of vertices a 3D

PAGE 31

18 coordinate basis is defined with the cen ter of the line between the vertices as the origin, makes the x axis and the cross product of the z and x axes makes the y axis. The coordinate basis is then used to create a 3D grid at its origin, the size of this grid determines the degree of locality and the size of the bins determines the surface representation granularity level. For this case the grid size was determined to be 103 and the bin size was d1/5. The g rid is then compared to the mesh with each bin in the grid computing the area of intersection with the mesh that is stored in a third order tensor. Each element of the third order tensor is equal to surface area of the mesh contained in the corresponding b intersection, and this helps to reduce the tensor into a sparse array that reduces memory utilization. This step is repeated for all the vertex pairs in the reduced mesh. Figure II 10 Tensor Example [ Example of the tensor created from t he dinopet scan [ 4 ] ]

PAGE 32

19 A 4D hash table is constructed with the tensors of all the point clouds, the first three dimensions in the hash table are for the i, j and k of the tensor and the fourth dimension is the angle between the normals of the pair. The registration process starts looking for the mesh that has the greater surface area in its tensors, this mesh is used as the root node in the Multiview c orrespondence spanning tree. The next step is to compare the root node tensors with the tensors of all the remaining meshes and the matching tensors are used to register those two meshes; this recently registered mesh is included to the spanning tree and r emoved from the search space. When all the tensors of the root mesh have been compared, the next mesh in the spanning tree is used to compare its tensors with the remaining meshes from the search space. The tensor comparison is done by a voting sequence, t he four indices of a vertex with values different to zero vote for all the other meshes and their tensors, when a tensor has less than half of the possible votes then this correspondence is dropped. Then the correlation coefficient is calculated for each r emaining tensor according to the following formula: Equation II 12 Correlation Coefficient for [4] Where Tm are the tensors with more than half votes in the first mesh, Tm(Ims) is the value of Tm in the region of intersection of the first mesh with the second mesh and Ts(Ims) is the value of Ts in the region of intersection of the second mesh with the first mesh. The results of Cc are then sorted and the values Cci < tc=0.5 are discarded. The remaining Tm values are then used for the local verification which works like this, the first tensor value is used to compute the motion to align with the corresponding tensor in

PAGE 33

20 the second mesh, and then the bounding dimensions are recalculated after this transformat from tolerance then the range images are registered with this transformation and the points of both images that are less than 2dres, the resolution for the mesh, apart are also turned into correspondences. If the number of correspondences is greater than nc, then ICP is used to detail this registration and after ICP the number of tuples that are less than dres apart are also correspondences. Lastly if the number of correspondences is greater than 2nc, then (D Dms) is computed again and if it is less than 2dres it goes into the global verification otherwise, with any fail condition, another pair of potential cor respondences is explored. The global verification consists of comparing (D DL), where DL are the bounding dimensions of both meshes together after the transformation, and 4dres, if it is less than 4dres then this registration is accepted, in case of false a better registration is searched with the next tensors couple. Figure II 11 Registration Results for [4] [ Example of the batch registration with tensors [4] ]

PAGE 34

21 A Novel Two Stage Algorithm for Accurate Registration of 3 D Point Clouds Dai and Yang [5] propose a two stage algorithm for the registration of point clouds; this algorithm works first at the coarse registration level and then at the fine registration level. In their work they highlight the possibility of extracting invariants and geometric features to find correspondences between different range images. Figure II 12 Local Invariant Feature for [5] [ Example of the local invariant features [ 5 ] ] This implementation at the c oarse registration level uses the proposed data structure named local invariant feature which is based on the idea of curvature features. To adapt that curvature features, the normal for each point is computed in each point cloud, then for each i point wit h its k closest points, neighbors, the dot product between the i point and each of its k neighbors is computed and stored in the local invariant feature vector. This proposed data structure is then capable of describing the neighboring characteristics for each point like a curvature would and thanks to the dot product properties, the neighboring characteristics would be invariant even in different coordinate systems such as the different range images. The next step in the coarse registration is to search th e corresponding local invariant features from the different scans. For all the source image points features FP

PAGE 35

22 search the closest values from all the destination image points features FQ, this process is optimized with the help of a kd tree constructed wit h the FQ values for the comparison. Once the possible correspondences have been found, the motion is computed by first eliminating the less probable correspondences. The less probable correspondences are the point pairs that have a feature vector distance greater than the threshold and the feature vector distance is simply the mean distance of every feature vector pairs. For the remaining correspondence points C, the coarse registration Euclidian motion is computed least square fitting method with the follo wing formula: Equation II 13 Least Square Fitting Coefficient for [5] After that the source mesh is transformed with the coarse registration Euclidian motion and it along the destination mesh are used as the input to the fine registration algorithm. Figure II 13 Example of the Coarse Registration for [5] [ Example of the coarse registration [5] ]

PAGE 36

23 The fine registration uses a modified ICP alignment to register the two different range images. The ICP algorithm is modified by adding two new constraints to improve its performance. The first constraint, closeness constraint, eliminates the false point matches; to determine the false point matches it considers the distance b etween the points and the distance between their local invariant features. The pairs that surpass the given distances thresholds are eliminated from the ICP computations. The second constraint, proximity constraint, checks the reliability of a pair of poin t given the fact that if a point p in P corresponds to a point q in Q then there are some neighbors of p that correspond to the neighbors of q. The proximity constraint is checked according to the following formula: Equation II 14 Proximity Constraint for [5] If this computed value is greater than the proximity threshold then the pair is also removed from the ICP computations. Possible Related Works Shortcomings In this part, the possible weak points present in the previously mentioned approaches will be explored in order to avoid the appearance of the same in this work. The results showed by the authors for [1] are really good, but the registration in this case is made against the original model instead of agai nst different range images that means a that the range image has a hundred percent of overlapping area; the use of the original model is a great disadvantage since, a great amount of times, the purpose of this application is to obtain the model data that i s not previously available. More of all, there

PAGE 37

24 also exists the problem with the utilization of the ICP alignment error and incrementing the different values of rotation to obtain a near to correct alignment that reduces the error found, the search range is too large and depending on the sampled points it might not find a close orientation to satisfy the requirements. In [2] we can see some of the best results for the coarse alignment. This approach has the small disadvantage that their detailed feature reco gnition could be affected by the sensor quality, for example some feature may be distorted in the scanning process and the correspondence would not exist between the two range images, and that in extreme cases with low overlapping regions from both range i mages, while constructing the constellation image the local minima were found outside the respective overlapping regions which could cause non corresponding constellation point and therefore incorrect alignments. [3] is an approach that is simplified by us ing mechanical enhancements to obtain cylindrical scans which could introduce extra noises depending from the precision of these devices. Once the two different scans are completed, the registration is performed with the help of the ICP algorithm with rand omly selected points from the two range images, this technique may introduce an error which is obtained by not having corresponding points from the both range images and leading to incorrect local minima. The final weak point of this approach is that it ha s to explore the complete 3 orientation DOF range to find a near to correct approach which makes it inefficient and it may still find smaller ICP errors in an incorrect orientation thanks to the randomness. The algorithm presented in [4] has a weak point i n the fact that it creates the tensor grids from randomly selected points from each point cloud and when they are

PAGE 38

25 compared there may not exist correspondence between the points being registered. Another weak point is the verification phase that uses the bo unding dimensions as a parameter; this only parameter may not be a good enough filter since the different scans could have a great difference in bounding measurements according to their orientation. The last approach explored in this work [5] shows promisi ng results by finding the specific features of the point clouds. However it has the disadvantage that the local invariant feature may be identical in many different points for special cases like cubic shapes, where the different planes rotated will have a very similar local invariant feature in each face or even in repetitive shapes which could lead to an incorrect alignment.

PAGE 39

26 CHAPTER III HIERARCHICAL STRUCTURE Point Cloud Simplification As it has been mentioned, fine level registration has a very efficient solution in ICP for the cases in which the initial guess is close to the actual transformation. This situation leads to the necessity of finding a proper coarse level registration. Several previous ap proaches, such as the previously described in chapter II, have been able to solve this problem nevertheless the complexity of finding correspondence between range images is great to say the least. To confront the complexity problem it is proposed to simpl ify the point clouds in an organized structure that allows the previous knowledge of point vicinity and a hierarchical structure that would improve the complexity for the correspondence search This section will be focused in the expla nation of the methodo logy used to create the hierarchical structure for the program. Simplification Proposals In the search of a simplification structure, other solutions were proposed and implemented with certain degree of success. The most successful proposal consisted of a axis in segments of a predetermined length The horizontal axis is formed by the perpendicular of the camera or sc anner point of view and the up axis orientation.

PAGE 40

27 After all the points are divided into bins of equal length along the horizontal axis, the points are explored to find the maximum value along the depth axis, which means it would find the point closest to th e camera. Figure III 1 Divisions Along the Transversal Axis (Horizontal) [ Range image divided along the camera x axis into n bins ] All these maximum points would then be complemented with the center of the complete range image height and the center of its corresponding bin along the horizontal axis. The ring simplification would represent roughly but accurately enough the contour of the objects like seen from a top view. A group of lines would then represent these points and the normals between them could be used to further obtain information from the structure.

PAGE 41

28 Figure III 2 Ring Simplification Example [ 8 range images with their respectiv e ring simplifications ] The ring simplification solution however is limited in the sense that the information is extremely reduced and the details are completely lost leaving several cases of similar representations even for completely different point clo uds. Figure III 3 Range Images with 0% Overlap and Ring Simplification Match [ Example of two non corresponding range images with ring simplification match ]

PAGE 42

29 Point Cloud Hierarchy Structure The final structure used in this work is composed of a four level hierarchical structure. The bottom level is the point cloud by itself which is not used in the coarse level registration; the second level is a simplified version of the point cloud ; the third level compresses even more the second level and contains vicinity information and the fourth level compresses the boundaries of the third level but leaves out the vicinity information. Figure III 4 Hierarchical Structure [ Diagram of the proposed hierarchical structure and their relations ] The four levels hierarchical structure is chosen based on the idea that the objects to be reconstructed have enough detail to differentiate matching surfaces and that by obtaining the simplified version of the object the main shapes and features of the object would remain available for the registration The simplification of the point cloud has two purposes, to speed up the computations related to registration and to decrease the effects of the surface imperfections introduced by a low quality scanning device. However, as a result the detail detection, like the detection of a door handle in a car or a small crease in the rabbit

PAGE 43

30 leg, is impossible ; but if we consider the presence of a measurement error in the scans, then it is obvious that those kinds of details could be easily confused with the faulted Starting from a leaf level and going up in the hierarchical structure construction, the the scans are kept this process practically disappears the effect of the scanning errors the third level helps in creating descriptions of the surface patch features each volume is covering so that only simil ar patches are matched and the fourth level works as a shortcut in the process that when a collision is not possible at that level then in all the lower levels it is impossible to collide. The inclusion of a fifth or more level s of hierarchy would be pract ically useless because it would only increment the number operations needed to reach the lower level for every case, beating the purpose of speeding up the computations That is explained by the fact that for each higher level the hierarchy has, the surfac e is reduced to a smaller number of voxels, leaving out more and more details getting closer to the point of box box comparisons All these statements would be true for the cases in which the main shape or contour of the object is enough to differentiate t he surfaces and find approximately correct alignments, but for cases in which the minor details are the dominating sources to find differences between scans for example the scans of a very wide building that have a repetitive pattern and that only small details like plants, are the determining factors for correct alignments then these 4 levels would not be enough.

PAGE 44

31 Point Simplification Process T he main idea behind the point simplification is that of an elastic latex mesh that is exactly large enough to cover the range image Imagine that the latex mesh is being pressed against the object and that it would touch several points but certainly not the complete surface and that you can obtain the coordinates of all the touching points in the surface T he poin t simplification process starts by obtaining all the points available in the point cloud. An axis aligned bounding box for each range image is computed. The aabb is aligned for each independent range image coordinate system and for each point in each range image, the maximum and minimum value of the three axes are updated. After that the boundaries of all the range images are used to obtain the simplified points separation size. Equation III 1 Bin Size After that a ll the points from each point cloud are sorted in a binary search tree structure which can sort the points based on the indicated axis (x, y or z) in this case along the x axis The binary search tree is also able to return all the points that are contained within the indicated range. Each range image is then divided in N different point columns according to the following: Equatio n III 2 Bin Horizontal Boundaries

PAGE 45

32 The next step is to sort each point column again with the help of another binary search tree, in this case along the y axis Then each column is divided in N different rows according to t he following: Equation III 3 Bin Vertical Boundaries After the row division case the binary search tree computes axis aligned bounding boxes for each of the bins. Finally the simplified points are determined like this: Equation III 4 Axis Aligned Bounding Box Equation III 5 Level 1 Simplified Points Using the maximum value along z means that the closest value to the scanner is the one being used The reason for this is to emulate the behavior of the latex that would only touch the highest point in the body. The point s are finally stored in an NxN array completely ordered according to the bins divisions from x to x and from y to y axes With this pre computation process it is possible to automatically know the exact neighbors for each point without the usual use of distance computations and reduce the number of points for further computations

PAGE 46

33 Figure III 5 Ordered Simplif ied Points M esh [ Example of the ordered points and the determination of their positions and neighbors ] Equation III 6 Neighboring Simplified Points The ordered points array give us a simple and easily accessible structure of ordered quads in which it is possible to determine automatically the vertices of each of quad this situation greatly accelerates the computations by skipping the neighborhood determination To compute each point normals, first for each quad, the surface normal is computed according to the following: Equation III 7 Simplified Points Quad Normal Then with all t he neighboring quads, the vertex normals are compute d and stored in a parallel NxN normal array for each vertex with the following formula: Equation III 8 Simplified Points Vertex Normal Where q are all the 4 possible quads surrounding the vertex i,j.

PAGE 47

34 Hierarchical Structure Construction T he hierarchical structure is based on the hierarchy bounding volumes structures used in the collision detection problems. These type s of structures consist of simpler volumes that contain the mesh entirely. It is typically started with a root node volume that contains all the points and is constructed in a top down way ; that point clou d is then volumetrically split according to the desi red criteria and each of the divisions have their points represented by a bounding volume which are the child nodes from the previous iteration. The process is repeated iteratively until a threshold is reached which in typical cases is the number of point s in the lowest node or the tree depth. The bounding volume hierarchy speeds up the process in the case of the collision detection because the intersection of the simpler volumes is done extremely fast and following the hierarchical structure it is not nec essary to search at a lower hierarchy level unless the higher has a collision state. This can make a collision detection process as fast as just one operation or in the worst of the cases a logarithmical case until it gets to the leaf level. In the case of the proposed solution, the hierarchical structure is constructed in a bottom up way. The extreme level of abstraction of a root node is not needed for this approach since the details of the range image would be completely eliminated. The reason of the uti lization of this hierarchical level is to confront the verification process as a collision detection problem to speed it up. In comparison of this approach with the approaches proposed in [6] and [7] the proposed hierarchy presents more levels. The existen ce of more levels allows more content in the structure and because all information is conserved for the coarse

PAGE 48

35 registration then it results in a better metric for the evaluation of the proposed transformations. The leaf level is the range image with all th e points contained in them, it is basically the raw data from each scan and it is not used in the coarse registration to speed up the computations this level is used in the fine registration step to find the optimal transformation with all the surface pro perties Figure III 6 Range Images with Level 1 Hierarchy [ Example of the simplified points (blue) applied to a set of range images ] The first level is the point cloud simplified with the NxN array. The necessity of the level 1 hierarchy corresponds to the fact that point clouds may contain hundreds of thousands and computations for these cases are extremely expensive ; besides the number error from low quality scans and the ordered nature of the level helps to determine beforehand the neighboring points without further computations that regular feature detection algorithms need. It is computed from the bounding boxes of a determined mesh s ize and to better represent the scanned object it is simplified to the points in the frontal face of the axis aligned

PAGE 49

36 bounding box with its corresponding normal instead of voxelizing the mesh like it is shown in the equation III.5 The reason of existence for the second level is that the simplified points from level 1 still have no surface information therefore registration related with just the level 1 needs a great amount of further computations and a high complexity To reduce these problems a new level where surface description is available was created this level should also help to improve the match evaluation complexity The second level is the most important level since it is where the vicinity information is kept which will be used for the feature recognition filters The structure of this level is an ordered array of bounding spheres. The bounding spheres were chosen because this is the most frequently accessed level and the sphere intersection determination is the fastest of all the bounding volum es. Each boundi ng sphere contains a 3x3 level 1 points because it allows having an even description of the surrounding surface around the center point and the neighboring points are automatically found with the ordered array. To compute the bounding spheres the following method is used: Equation III 9 Level 2 Bounding Sphere Initial Radius Equation III 10 Level 2 Bounding Sphere Center Equation III 11 Level 2 Radius Rectification

PAGE 50

37 Figure III 7 Range Images with Level 2 Hierarchy [ Example of the bounding spheres applied to a set of range images ] The final hierarchical level was created with the idea that several computations still happen in the second level where the collision between range images is not happening Considering how collision detection algorithms solve this problem with higher hiera rchical levels that oversimplify the mesh to avoid unnecessary collision computations, the third level encompasses level 2 bodies to reduce computations The third contains a 2x2 level 2 bounding spheres within a set of Axis Aligned Bounding Boxes The cho ice of bounding volume in this case is because not all the resulting simplified points meshes are approximately squared and that causes that with certain configurations the resulting bounding spheres are to o large and offer no help with the registration. I n a previous ite ration of this work, the level 3 hierarchy structure included a descriptor of the average normals of the level 2 structures containe d in each element of the level 3 however the experiments showed that so much detail was lost in this proces s that even corresponding surfaces would not have similar descriptors.

PAGE 51

38 Figure III 8 Range Images with Level 3 Hierarchy [ Example of the level 3 bounding boxes applied to a set of range images ] Neighborhood Descriptors The registration would work by aligning certain matching surface characteristics obtained from the point simplification; several approaches were proposed to try to solve this problem, the following part will explain the most remarkable and analyze the reasons that leaded to the option that was chosen. Ring Simplification Normal Vectors Using the simplified lines obtained by the ring simplification, the normal vectors to each pair of succession was computed as a 2D problem with the following formula: Equation III 12 Ring Simplification Normals This method results in the normals that describe completely the line that represents the range image, however during the registration process, because of the great amount of detail lost, the results of registering any semi planar surface would always

PAGE 52

39 converge being them local minima that could not be differenti ate d from the correct alignment, look at the example shown in figure III.3. Ring Simplification Normal Vectors Layers Using the level 1 simplified points obtained by the point simplification, the normal vectors to each pair of points succession was computed as a 2D problem as in the previous description. This approach then represents the range image as a set of N lines equally distanced along the y axis. However the shortcoming of this approach is that the descriptors lose a great amount of vicinity descripti on by just considering the horizontal neighboring points at each side of each point. Figure III 9 Ring Simplification Layered [ Example of a range image with its n layers of rings ] Local Invariant Feature Using the method proposed in [5] the level 2 points were r epresented and stored as level 2 structures that would represent the small patch of surface covered by the bounding body. In this case the computations of the local invariant feature would be extremely accelerated by first reducing the number of points to be analyzed since the point structure to be represented is now NxN second by skipping the neighborhood

PAGE 53

40 determination and distances computations since the ordered array already gives the point neighbors for each point and lastly by reducing th e neighboring points to a maximum of 8 points. Figure III 10 Simplification of Local Invariant Feature for Level2 [ Level 2 bounding sphere with its center point as a reference of the surface patch curvature ] To test the accuracy of this surface repre sentation, two range images with more than a 50% of overlapping area were used. All the pre calculations up to the surface descriptions were computed and the scalar values for the level 2 were returned as two tables for both range images. Unfortunately the obtained results were not satisfactory. It can be observed in the table the values of (4,4) and (5,4) are different even when they are representations of matching surfaces, the threshold would have to be too large for it to fit. After visually comparing b oth tables and observing more similar results on non corresponding point than on correct corresponding points it could be inferred that this filter would not be enough for the feature matching. The more reasonable explanation for this is that with a

PAGE 54

41 very s mall number of neighboring points, the absence or a great variance of values of just one neighbor could deeply affect the average for the result even more when it is the case of the curvature represented as a simple scalar. Table III 1 Local Invariant Feature Comparison with Hierarchy Level 2. Range Image 0 0 1 2 3 4 5 6 7 8 9 0 0.0 537.2 393.9 315.7 386.0 395.3 366.7 385.1 366.5 488.5 1 0.0 0.0 364.9 151.6 211.0 72.4 86.2 84.6 131.8 178.9 2 0.0 136.2 101.6 83.7 138.0 79.1 41.8 77.4 97.9 260.6 3 453.8 104.8 71.2 111.8 151.0 66.1 103.5 56.6 84.1 0.0 4 431.4 236.5 56.1 80.5 82.0 118.7 93.5 76.6 1076.2 0.0 5 449.0 192.2 161.8 83.0 102.4 95.7 97.5 1074.3 0.0 0.0 6 378.6 132.2 99.7 0.0 0.0 0.0 0.0 0.0 0.0 0.0 7 370.7 173.4 149.5 114.9 0.0 0.0 0.0 0.0 0.0 0.0 8 0.0 102.6 3112.5 113.3 163.9 443.5 0.0 0.0 0.0 0.0 9 0.0 389.7 0.0 0.0 146.2 466.3 0.0 0.0 0.0 0.0 Range Image 1 0 1 2 3 4 5 6 7 8 9 0 0.0 534.0 388.7 392.9 374.6 397.6 361.6 369.7 376.0 0.0 1 0.0 0.0 119.8 177.0 94.0 81.9 72.2 130.1 135.1 319.2 2 0.0 199.2 118.9 137.9 55.2 56.8 41.9 130.1 206.3 0.0 3 0.0 102.6 133.4 121.5 100.6 38.6 93.7 64.1 85.6 0.0 4 0.0 132.0 91.0 82.1 113.1 105.9 38.3 83.6 1080.5 0.0 5 315.9 210.3 141.5 101.2 114.9 76.1 89.3 117.8 0.0 0.0 6 309.2 79.5 74.7 212.5 0.0 0.0 0.0 0.0 0.0 0.0 7 407.2 130.6 136.0 179.3 212.6 0.0 0.0 0.0 0.0 0.0 8 0.0 0.0 0.0 226.0 84.9 134.6 214.9 0.0 0.0 0.0 9 0.0 0.0 0.0 0.0 215.8 68.5 106.6 0.0 0.0 0.0 Local Feature Histograms The chosen method was the local feature histograms which are capable of storing three dimensional surface information in a group of bins instead of a simple scalar number like in the previously described process. Using the method proposed in [ 8 ], the

PAGE 55

42 level 1 points were represented and stored as level 2 structures that would represent the small patch of surface covered by the bounding body. In comparison with the method presented in [8], the method is speeded up by reducing the number of points that represe nt the range image and also by obtaining the 9 possible neighboring points automa tically from the ordered level 1 points structure without having to compute the distances for every point to determine the neighbors and reducing the number of calculations t o a maximum of 108 because there are 9 or less points in the level 2 hierarchical structure The computation of the histogram is done for every k level 2 sphere; for every level 1 point included in the bounding sphere, all the possible pairs are used to compute the descriptor. With each pair of points, local coordinate systems are calculated using the systems the angles between them in each of the three axes are obtained. The process vector is used to multiply it with a cross product by the normal o f p (Np), the result is a new axis V is multiplied with a cross product by the Np to obtain an equivalent of a z stem is now (Np, V, W) and it is used to compute the angles between the pair pq. The first angle is obtained from Np and the vector between points p and q. The second angle is obtained from the V axis and the normal of the point q (Nq). The third angle is obtained from the projection of the normal of point q (Nq) to the plane formed from Np and W and the Np axis.

PAGE 56

43 Figure III 11 Angles of 2 Points for Feature Histogram [ Pair of points p and q with the local coordinate system for p and the angles between the q normal and the coordinate system. ] Equation III 13 Histogram Local V Axis Equation III 14 Histogram Local W Axis Equation III 15 Histogram Angle Equation III 16 Histogram Angle Equation III 17 Histogram Angle The three values obtained are then stored as occurrences in a bin that contains the value within its range. Since it is known that the result of the values obtained range from 180 to 180 degrees or to radians the ranges of the bins are computed as an exact division of the range of results in s equal size bins.

PAGE 57

44 To test the accuracy of this implementation the histograms of known non corresponding surfaces in two range images were created and compared. In this special case, the number of point in each surface was different and a direct comparison of the hist ograms would return less than a 50 percent of coincidence which would meet the wanted results. Figure III 12 Histograms of Non Corresponding Points ( Result 40% similarity) [ Comparison of two histograms from non corresponding surface patches R esult is no t a possible match. ] The next tests included using randomly selected pairs of patches at a time a comparing the histograms and visually identifying if they were correct correspondences and if that condition matched the result from the histograms compari son. 0 10 20 30 40 50 60 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B

PAGE 58

45 Figure III 13 Histograms of Corresponding Points (Result 49 % similarity) [ Comparison of two histograms from corresponding surface patches. Result is no t a possible match. ] The results obtained from this test were not the expected. For one correct match the histograms had less than the 50 percent of coincidence After creating the corresponding graphics it was detected that the difference was caused because the number of points was different and even with the great difference in the number of occurrences in each bin, the distribution of the graphic was similar, therefore by comparing percentages instead of the occurrences the difference obtained was minimal, which led to the use of percentages for the comparisons from there on. 0 10 20 30 40 50 60 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 C D

PAGE 59

46 Fig ure III 14 Histograms of Corresponding Points with Percentages (Result 91% similarity) [ Comparison of two histograms from corresponding surface patches with their bin percentages. Result is possible match. ] Other results found from the tests realized were false correspondences, pairs of points that had similar histograms but that were not actual correspondences. These result s were expected from the previous knowledge that the point simplification would eliminate a certain level of detail and that there wou ld be also surface patches that contain a similar surface even when it is not the exact match. 0 5 10 15 20 25 30 35 40 45 50 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 C D

PAGE 60

47 CHAPTER IV AUTOMATIC REGISTRATION Pair Wise Transformation Computation As it has been mentioned, the main purpose of this approach is to find an initial guess that is close enough to the actual transformation of the range images so that the ICP algorithm can further refine the transformation using the point to point distance optimization. The related works that have been explored so far in this work cover a wid e area of ideas from brute force approaches where the degrees of freedom are exhaustively explored to the feature detection algorithms that refine the meshes to a small number of points that are later optimized The proposal in this case is to take advanta ge of the hierarchical structure to speed up the computation and use the feature descriptors to reduce even further the exploration. It should be considered that the goal of this work was not in the simple registration of two range images but the automatic registration of a set of range images that comprehend the complete peripheral surface of the scanned object. This means that a metri c system should also be included to compare the registrations of different pairs and decide for the best option which makes this problem more complex and creates the necessity of more information available for each registration process. Transformation Com putation Proposals Before coming up with the final solution to the coarse registration process a couple of approaches were explored in search of an algorithm that could find the correct or close to correct transformation and that would then give enough in formation about the

PAGE 61

48 match that could be used to determine the best option and align the batch of range images to reconstruct completely the scanned object. Ring Simplification Comparison This first approach used the simplified lines obta ined from the co lumn simplification of the point clouds. In this case the line representing the range image would have N vertices with N 1 normal vectors that would describe the characteristics of the line. Since it is a line along a simple plane the vectors can be simpli fied to (x, z) which simplifies and speeds up the computations. The process starts by aligning the normal vectors of a point ns in the second range image with a point nd in the first range image and then translating the second range image so that point ns is coincident with point nd. The next step is the creation of a chain of coincidences. The first link is included in the chain, in this case it is the origin point where the lines were roughly registered, after that the chain is expanded i ncrementally to the next vertex in the line of the point cloud to be registered the closest point to that new link is found in the line of the destination range image and the difference between the link normal and the closest point is computed, if the difference absolute value is less than the threshold and if the distance between the points is less than half of the line segment length then the link is accepted and the chain continues to grow incrementally. In the case of a difference or distance greater than the threshol d s the chain will start growing decreasingly following the same process, if the chain was growing incrementally, otherwise the chain finishes and the chain size is stored.

PAGE 62

49 Figure IV 1 Chain Creation Diagram [ Example of a c hain search. The compared vertices are aligned, then the neighbors are checked, if they are within distance threshold, add to chain otherwise go to the other direction. ] All the possible pairs of points from both range images are explored, a register of t he maximum elements in a chain of coincidences is kept and the longest chain is evaluated as the correct rough registration. This process would be a very fast approach however with all the details lost in the ring simplification it could return very bad re gistrations for range images with simple planes or surfaces, in several cases converging to local minima because of all t he possible line configurations, see figure III.3. Ring Simplification Layered Comparison This solution is b ased on the findings of the simplified lines comparison explained in the previous section. To avoid the number loss of information the layered rings are used to describe the point cloud instead of only one line it used N lines with N vertices and normals. In this case even with t he layered approach the normals would be treated as two dimensional because the

PAGE 63

50 height does not change along the same ring, this leads to a speed up of normal computation as well as normal distances computations. The layered solution reuses the idea of the chain of coincidences. The points to be registered have the normals aligned and the second range image is translated so that the points are coincident. A chain is started with the registered points and the chain starts growing incrementally along the same ring. The next point is found as the next point in the current ring if the resulting values are within the thresholds then the element is added to the chain. If the resulting values are out of the boundaries, then if the chain was growing incrementally in the ring it will start growing decreasingly in the same ring. If the chain was growing decreasingly and the results are out of bounds it will go up to the next ring and try to grow in that direction when it stops in that direction it will return to try to grow going down to the next ring immediately bellow. The process is repeated for all the possible combination of pairs from both range images that are being registered and the maximum number of chain elements is stored to find the best option. The point t hat generates the longest chain of coincidences is then used as the correct coarse registration. The results of this process were promising; however the exhaustive search with all the possible pairs of points is severely time consuming even for the simplif ied points in the coarse registration. Registration Using Hierarchy Levels and Descriptor Filters The final result of this research for the coarse registration fuses some of the aspects of several of the related works that have been explained in previous s ections. The exhaustive exploration of the combination of points is used to find the orientation and

PAGE 64

51 translation of the range image that is being registered. This approach is an improvement of the solution proposed in [1] and [3] where they explore exhaustiv ely the transformation space indiscriminately in this case the solution proposes to limit the range of transformations. Considering [6] a hierarchical structure wa s implemented ; however instead of getting rid of all the info rmation included, a multi level hierarchy is used were the level of detail keeps incrementing as it gets further in the hierarchical tree The hierarchy levels try to improve the process also by speeding up the registration verification. Another contributi on in this work is the use of feature filters the proposed algorithm takes the feature description results to filter out transformations that could not be possible by using just similar surfaces to register pair s of points; this modification helps to main tain all the information available to do the metrics of the registration quality instead of limiting the number of points available for the registration where some of the remaining points may not be part of the overlapping area between the range images Th e process starts in a pair wise registration, where the pairs of range images are registered and graded in order to determine the best possible registration The following sections in this chapter describe the methodology used for the coarse registration o f the range images pairs and then the extra steps used to register the whole range image batch. Points Pairs Search It works in the level 2 of the hierarchical structure; therefore the problem is reduced to a maximum of N/3 x N/3 structure. The idea for the algorithm is that for a pair of range images wi th overlapping areas the level 1 point simplification may be slightly altered by the point of view of the scanner but the overall properties of the surface would not be deeply affected within a certain diameter and thanks to that there will exist a surface representation equivalent in both range images

PAGE 65

52 that are being registered. That is why the surface is roughly represented with the level 2 containing all the vicinity information of t he simplified point clouds. It is also assumed that the normals computed for the level 1 hierarchy points are pretty close to the original and that the surface normals within a certain small diameter are very close in values As a result it is possible to deduct that for range images with overlapping areas, the correspondin distribution and change rate and thanks to that we can reduce the transformation search space to only the possible combinations of its pairs of no rmals. The process starts by choosing th e central point from the level 2 bounding sphere from the source and the destination image ranges, that we already know thanks to the ordered arrays then the histogram s corresponding to each bounding sphere are compared as a filter, if it passes, then it continues to the next step, if not the pair is discarded For the next step t he normal from that central source point in the range image to be registered is then rotated to obtain the same orientation of the central point in the destination range image and translated to make the points coincidental After that the orientation needs to pass a correspondence filter; if it fails, the pair is discarded, otherwise a chain is s earched with the help of the hierarchical structure. All the possi ble pairs of points from level 2 are searched and the ones that have a value above the threshold are saved for the final metric evaluation If no pair is found after all the tests then the a lgorithm determines that there is no correspondence between the range images pair. Points Pairs Filters The algorithm proposes to use two filters a filter for the surface similarity and a filter for the correct orientation. The use of these filters intents to

PAGE 66

53 reduce all the possible mismatches as well as the total number of deep explorations in search of a chain of coincidences that would result t ime consuming and unproductive The surface similarity filter uses the feature recognition techniques used in [6], the surface histogram basically stores the information of the curvature inside the level 2 bounding volume A matching patch of surface from the source range image should be similar to the matching patch of surface from the destination range image. Using the histograms distribution, they are compared bin to bin and a percentage of similarity is computed, if the percentage is greater than the 70 percent then the points are treated as possible matches. Equation IV 1 Histogram Similarity The orientatio n filter checks that the level 1 points contained i n the l evel 2 bounding sphere have a matching orientation between the explored pair. It starts by finding the clos est point to each of the level 1 points; each of them should have a distance less than the md/2 if not the pair is rejected. Then for each poi nt, the closest point normal vector difference should be less than 10 degrees, if more than 3 of the points fail it is rejected. And finally, the incremental orientation; the central point in both range images are incremented, if the incremented points ar e not the closest to each other then the source is rotated around the normal vector until the incremental closest points are coinciding.

PAGE 67

54 Figure IV 2 Incremental Orientation [ T wo matching bounding spheres included points Find the immediate next point from the center for each bounding sphere. If the closest point is not each other rotate until the condition is met. ] Chain Search The chain search is where the suggested solution takes advantage from the technique s used in collision detection and the constructed 4 level hierarchy structure. It recycles the idea suggested in the ring layered simplification comparison. The chain starts with the central points or the registered pair. Since it is known their location in the hie rarchical structure then it is possible to limit the probable closest point as the points contained in the level 2 bounding sphere. All the p oints within the current level 2 volume are searched and if the distance to the current point is less than md/2, th e point is added to the chain. The process is r epeated to all the level 2 spheres that share the level 3 parent node with the origin. It then foll ows with the neighboring level 3 volume from the source range image, it finds if it is inte rsecting with some other level 3 volume from the destination range image. Then it searches the intersections on the level 2 spheres and for the found collisions it goes into the level 1 points, adding the points to the chain in the case of pairs of points with distance less than md/2. These process works like the ring layered simplification comparison but instead of growing in the equivalent of the level 1 point s it

PAGE 68

55 tries to grow at the level 3 volumes and exploring deeper only in case of possible chains links inside the exp lored branch. This process discards the non corresponding points in batches since the higher levels which accelerates the performance. Equation IV 2 Level 3 Collision Equation IV 3 Level 2 Collision The chains of coincidences whose number of elements are greater than the threshold are stored as a possible final registration and evaluated to determine the best possible option. Possible Registration Evaluation All the pairs of points that have a chain larger than the threshold are then explored in detail to have its correctness measured. The basic tool used for this metric is a Quadtree that contains the destination range image. This Quadtree helps to obtain the minimu m distances from all the level 1 p oints in the source mesh to the destination mesh level 1 points. There are two possible ways of measuring the correctness of the registration, using the average error or using the number of coincidences.

PAGE 69

56 The Quadtree is constructed from the root to the lea f nodes; it starts by obtaining the aabb fr om all the points in the level 1 array. The aabb is then split by the half along two axes; these axes are defined by these conditions: Equation IV 4 QuadTree Axis Division All the points are divided in the 4 resulting sections of the parent node. This process is repeated iteratively until all the leaf nodes have less than 8 points. The Quadtree accepts any 3D point and it computes the closest leaf node to that point. Inside the closest leaf node it computes the distances with the points inside the node and the searched point and returns the minimum distance which is the minimum dista nce from the point to the point cloud in a point to point manner. The registration starts with the point p in the level 1 hierarchy from the source. It computes the minimum distance from the point to the destination in a point to point manner with the Quad tree. The error is then affected by the minimum distance and after repeating the process for all the points available in the source range image the error is computed like this: Equation IV 5 Level 1 Distance Error The error is compared with all the possible correct registration chains and the registration with the lowest error will be chosen as the correct coarse registration. This is

PAGE 70

57 the typical ICP metric of error, like in ICP, t he purpose is to try to optimize the error value with the registrations found. Figure IV 3 Point to Point Distance Metric [ Example of the minimum point to point distance metric. Result is the average of all minimum distanc es. ] The other method uses the Quadtree also to compute the minimum distance from each point of the source image to the destination image, but in this case instead of using the distance to compute the error, the value is compared and if it is less than the threshold, an occurrences counter will be incremented. Equation IV 6 Level 1 Correspondence Value

PAGE 71

58 The numbers of occurrences of all the possible correct registration chains are compared searching for the maximum value. The registration with the maximum number of occurrences is the one that is chosen. This is the typical metric for the ICRP and the purpose is to try t o optimize the number of occurrences. Figure IV 4 Point to Point Distance Threshold Metric [ Example of the corresponding points metric Result is the number of points that have a point from the other cloud within the thres hold ] Range Image s Characteristics The previously described algorithm assumes that the point clouds introduced have an overlapping surface large enough that it will always be the greatest corresponding surface patch es in each range image during the pairwise comparison To cover that requirement, the scans must be taken from the points of view that guarantee that large enough area of overlap, this is dependent of the object to be scanned in general 8 scans from approximately evenly distanced points of view around the object are more than enough In cases where the occlusions of different points of view are moderated then the number of scans could be further reduced to 6 approximately

PAGE 72

59 evenly distributed scans. In very low occlusion cases in which the sc anner range is able to cover a great area of the object, the number of scans can be extremely reduced to 4 nevertheless, the scans must be taken from precise points such that each of them have overlapping with the neighboring scans some scan locations co uld result in 0 percent of overlap between the range images It is also assumed that the resulting point clouds may include a certain level of noise introduced by a low accuracy scanner. Even though a level of error is expected in the point clouds, the se i mperfections should be small enough that they do not damage the main shape or contour of the scanned objects ; that could be translated into a simple rule that the scanner inaccuracy error must be lower than the 5 percent of the general dimensions of the ob ject bumpy the overall object shape. Batch Registration The initial assumption is that the range images that are received contain no information concerning their order or which range image is supposed to be registered with the others. To solve this problem the approach consisted of a fter all the possible pairs of range images with the first and the rest are computed the metrics returned from the pairwise registrations are used as reference. Depending on the metric the minimum error or the maximum number of occurrences will determine which the corresponding next range image is. The process is repeated with the next range image and the remaining available. But in order to include more details for the evaluation phase, the Quadtree is created with all the range images that have been already registered. These steps are repeated until

PAGE 73

60 there are no more available meshes or the remaining point clouds have been f ound not coincident with the all the range images. The result of this approach however is completely dependent of the order in which the point clouds are explored which could lead to choose an incorrect first alignment that would close the cycle premature ly, because some non used point cloud had no possible registration with the remaining range images. Because of that, the solution was changed to a comparison between all the possible pairs of point clouds. It starts by checking the point cloud with each ot her to find the registration between them from this possible registration the error was stored as a metric of that match. After all the matches are computed, the point clouds are sorted increasingly from their number of possible matches those pairs of po int clouds that have at least 25 percent of level 2 collisions. Starting by the point cloud with the least number of possible matches, the algorithm chooses the match that has the smaller level 1 error after the registration and then continues to the next point cloud in the sorted array. The algorithm tries to find a route that goes through all the point clouds with no inner cycles that has the least error possible. However, the results of this approach were not satisfactory; this could be explained by the fact that the minimum distance average depends of all the points and even the points outside the overlapping region account for the error, leaving a big space for local minima. To correct the influence of the non corresponding area, the error metric was su bstituted by the number of corresponding points between the pair. This approach depends only of the points that are included in the found overlapping area and works as a better judge for the correspondences.

PAGE 74

61 CHAPTER V EXPERIMENT AL RESULTS Experiment al Objectives T he experiments implemented to test the sets of range images were developed to denote the first the better values needed to obtain a better performance of the hierarchical structure second to understand the characteristics needed to obtain the correct registration from the algorithm and third to find if given the correct range images set the algorithm could perform a correct registration regardless the initial position of the images. Experimental Validation To validate the correct operation of the suggested algorithm, a series of experiments were implemented to give a metric of the solution effectiveness. The first section describes the experiments conducted for the search of the best parameters for the algorithms. The second section describes the experiments that were conducted to test the effectiveness of the algorithm under different initial conditions, in this way determining the limitations of the proposed solution. The algorithms were applied to real scans that present a great deformation because of the external noise as well as virtual scans that present no deformation at all.

PAGE 75

62 Figure V 1 Pairwise Registration (Virtual Data) a [ Two range images in their original positions (left), range images coarsely registered (right)] Parameter Settings This section describes the experiments conducted in the search of the optimal possible parameter settings for a general case implementation. T he search compre he nds the size of the simplification structure, the histogram similarity threshold and the minimum point to point distance. Figure V 2 Multiple Range Images Registration ( Real Data) b [ Four range images in their original position (left), range images coarsely registere d ( right ) ] The first set of experiments utilized a batch of range images of both real and vir tual point clouds to define the level 1 points array size Since we know that the level 2

PAGE 76

63 stru ctures consists of 3 x 3 level 1 points clusters, t hen the squared array of level 1 must be a multiple of 3 to obtain an exact division in the next hierarchical level. The level 1 array sizes were set and the time of the pre computations, the time of the coarse alignment and the time of the fine alignment were registered for the analysis. We can observe that for lower values of the level 1 arrays, the pre computation time is very close. For the registration we can observe how the time increments exponentially for every greater number of the arrays in both types of registra tion however the lower sizes return no convergence for the batch registration; the cause of this is that the lower sizes fail to represent the level of detail needed for the feature recognition, therefore we can determine that the optimal level 1 size N=3 0. It is also important to remark that the fine registration returns a very similar result after the coarse registration with the configuration of 200 iterations and 85 percent of sampling and the configuration of 50 iterations and 50 percent of sampling. This is because the coarse alignment is close enough to the optimal solution of the ICP that the sampling and the iterations can be reduced and it will still return a close fine registration. Table V 1 Array Size of Hierarchy Level 1 Comparison. H ierarchy (s) coarse reg (s) fine reg (0.85, 200) (s) fine reg (0.50, 50) (s) chair (18x18) 2.28559 2.26402 (*) 6.85557 (*) 1.32856 (*) bunny (18x18) 14.8508 0.982171 (*) 70.048 (*) 50.3592(*) chair (24x24) 2.31516 6.92665 (*) 8.21955(*) 1.55652 (*) bunny (24x24) 15.3037 1.96898 (*) 71.7346 (*) 15.3615 (*) chair (30x30) 2.10035 26.5006 6.95392 1.27321 bunny (30x30) 15.2254 8.4911 246.414 39.1164 (*) unsucce s sful

PAGE 77

64 Figure V 3 Level 1 Array Size vs. Alignment Time [ Array size variation plot versus the time it takes for the coarse registration ] Table V 2 Histogram Minimum Similarity Comparison. Percentage Mesh0 (s) Mesh1 (s) Mesh2 (s) Mesh3 (s) Mesh4 (s) 0.5 7.6253 22.8185 16.798 64.6028 7.42689 0.55 7.30578 19.65778 16.7844 59.1497 7.45987 0.6 7.21509 19.1144 16.8347 37.2055 7.42575 0.65 6.8943 18.8758 16.5256 26.5849 7.3879 0.7 6.56264 17.122 13.5719 24.3553 7.3215 0.75 5.68261 13.6497 11.9876 22.7952 7.25879 0.8 4.86804 11.8986 10.6945 20.3785 7.25806 0.85 4.12647 10.48979 9.16798 13.4889 6.9515 0.9 3.62845 8.39912 8.0273 11.3152 5.26888 0.95 2.8654 7.4798 8.51949 11.5378 6.12189 The histogram comparison works as a filter to accelerate the registration by eliminating the pairs that could not be corresponding surface patches because of their different surface properties. The meaning of the correct limit value means that a great number of impossible registrations will be rejecte d and the time consumed analyzing 0 5 10 15 20 25 15 17 19 21 23 25 27 29 31 real range images virtual range images

PAGE 78

65 these incorrect solutions will be saved. The experiment took a pair of virtual range images and the percentage of acceptance was incremented starting at 50 percent until 95 percent, the time was also registered for the ana lysis and the outcome of the registration. We can observe that the registration time is reduced dramatically as the parameter is increased, however at the point of 90 percent of similarity no correct registration is found. The simple explanation for this i s that the representations of the surface patches are very similar but not identical because of all the information lost in the simplification process From these results it is possible to assume that an 80 percent of similarity will be enough to filter the impossible registrations and to keep a safe margin of detection of surface coincidences. The minimum point to point distances is important to the cha in of coincidences creation and for the ICRP metric That is why it is important to find the optimal value for the threshold. Considering that the level 2 points are a grid that is spaced at a maximum of md, the experiments take md as the threshold value a nd then a percentage of it is used incrementally to observe the outcome of the registration. Table V 3 Minimum Distance Threshold Comparison. md % Mesh0 Mesh1 Mesh2 0.5 ok ok ok 0.6 ok (*) ok 0.7 ok (*) (*) 0.8 (*) (*) (*) 0.9 (*) (*) (*) 1 (*) (*) (*) 1.1 (*) (*) (*) (*) unsuccessful registration

PAGE 79

66 The results of the experiments reflect that a 0.50md is the optimal threshold value. The explanation for this is that a point from the first point cloud that is correctly registered at the second point cloud could be at maximum in the exact center between two points in the grid. Greater values than this would account for incorrect coincidences and the lower values would fail to account a number of correct coincidences. Algorithm Validation Once the optimal parameter settings were defined a series of experim ents were developed to find the effectiveness of the proposed solution The experiments test the needed overlapping area between the range images, the initial configuration of the range images and as a reference point it compares the proposed algorithm wit h the ICP alignment. Figure V 4 Pairwise Registration (Real Data) c [ Two range images in their original position (left), range images coarsely registered (right) ] Four Step Success Metric As a point of reference of the proposed solution to determine if a registration was correct, a four step metric was proposed. The test consist of the ICP error before the fine registration and after the fine registration checking if the error has indeed been optimized by the ICP algorit hm after the coarse registration then the time it took to obtain the complete registration including the hierarchical structure

PAGE 80

67 creation. The final step is the intervention of a person; that is because for the computer the registration will be a success i f it has found any similar surfaces large enough to pass the threshold, even when it is an incorrect registration. Thanks to that the last metric is a Boolean that describes if a human observes a correct registration. This test was conducted to five pairs of corresponding point clouds. The point clouds were chosen as two pairs of real data point clouds that included a moderate level of noise that did not deform the overall shape of the objects (chair and car) then a pair of virtual data point clouds with large uniform surfaces (car), and finally two pairs of high quality real data point clouds with very unique surfaces (armadillo and dragon). Table V 4 Proposed Algorithm Metric with ICP. Test avg. Err visual Time (s) Coarse Fine 1 0.00134022 0.00027788 ok 38.1657 2 0.0150338 0.00121589 ok 26.70233 3 0.00414668 0.00027621 ok 39.2548 4 0.0221134 0.01199 ok 3.931523 5 0.087418 0.0407408 ok 4.202232 Overlapping Area Percentage Test The overlapping percentage test takes several pairs of virtual range images that have a different percentage of overlapping areas, the percentages will be registered as well as their outcome to find the minimum required percentage.

PAGE 81

68 Figure V 5 Registr ation with Different Overlapping % ( Virtual Data) [ Range images with 91% overlap (left), 71% overlap (center) and 57% overlap (right) ] Table V 5 Overlapping Area Comparison. Mesh 2 Size 582 C. Points % Registration 531 91% ok 449 77% ok 412 71% ok 334 57% ok 299 51% ok 223 38% (*) (*) unsuccessful registration The result found in this experiment show that the minimum percentage of overlapping area is near the 5 0 percent. This value could be reduced if all the threshold values were modified, however that would beat the purpose of all the filters to speed up the computations proposed in this work. Initial Orientation and Translation Test After all the possible parameter s for a correct range image registration have been defined, the reliability of the algorithm depending on the initial orientation of the range images is tested. The two independent experiments check first the impact of the original position in the outcome of the

PAGE 82

69 algorithm and the second experiment checks the impact of the original orientation in the outcome of the algorithm. Table V 6 Initial Translation Comparison. Test # axis Registration Time (s) x y z 1 0 10 0 ok 2.3229 2 0 20 0 ok 2.8607 3 0 30 0 ok 2.85802 4 0 40 0 ok 2.14028 5 0 50 0 ok 2.9321 6 0 60 0 ok 2.1323 7 0 70 0 ok 2.1913 8 0 80 0 ok 2.2916 9 0 90 0 ok 2.87231 10 0 100 0 ok 2.24884 11 10 0 0 ok 2.0297 12 20 0 0 ok 2.42495 13 30 0 0 ok 2.8263 14 40 0 0 ok 2.25811 15 50 0 0 ok 2.937657 16 60 0 0 ok 2.6364 17 70 0 0 ok 2.8328 18 80 0 0 ok 2.2774 19 90 0 0 ok 2.24302 20 100 0 0 ok 2.604 21 0 0 10 ok 2.84403 22 0 0 20 ok 2.4831 23 0 0 30 ok 2.67634 24 0 0 40 ok 2.8785 25 0 0 50 ok 2.92775 26 0 0 60 ok 2.56092 27 0 0 70 ok 2.23414 28 0 0 80 ok 2.8514 29 0 0 90 ok 2.615 30 0 0 100 ok 2.51881

PAGE 83

70 The experiment s w ere conducted on a pair of virtual range images The translation test consists of moving one of the range images along the three axes, and registering the outcome and the registration time. The measuring unit for the distance in this case is in number of md. The results of the experiment showed that the distance between point clouds did not affect the outcome of the algorithm, which is an expected result because the registration problem tries to optimize the distance between points in every proposed solution. The orientation test consisted in rotating one of the range images around the three axes before registering the point clouds. The times used in the coarse registration as well as the outcome of the registration are saved for the analysis. The results of the experiment show that the registration algorithm works in almost every original condition with the exceptions of the 90 and 90 degrees around the z axis, this is because it does the rotation angle computations as a 2D planes and when a vector is aligned with the axis it would need a division by 0 which is an error. To solve the problem the orientation of that range image can be slightly modified to avoid the division by 0.

PAGE 84

71 Table V 7 Initial Rotation Comparison. Test # axis result Time (s) x y z 1 0 120 0 ok 3.26741 2 0 105 0 ok 3.10508 3 0 90 0 ok 2.95553 4 0 60 0 ok 2.89061 5 0 45 0 ok 2.8652 6 0 30 0 ok 2.9798 7 0 15 0 ok 2.88929 8 0 0 0 ok 2.865 9 0 15 0 ok 2.9395 10 0 30 0 ok 2.8955 11 0 45 0 ok 2.95787 12 0 60 0 ok 2.8761 13 15 0 0 ok 2.55171 14 30 0 0 ok 2.2581 15 45 0 0 ok 1.446 16 60 0 0 ok 1.4493 17 75 0 0 ok 0.979754 18 90 0 0 (*) 0.5094 19 15 0 0 ok 2.79991 20 30 0 0 ok 1.89071 21 60 0 0 ok 1.3987 22 75 0 0 ok 1.23147 23 90 0 0 (*) 0.9725 24 0 0 15 ok 2.38713 25 0 0 20 ok 2.24819 26 0 0 30 ok 2.838 27 0 0 45 ok 2.1845 28 0 0 75 ok 2.4876 29 0 0 90 ok 2.0678 30 0 0 15 ok 2.88564 31 0 0 30 ok 2.7849 32 0 0 45 ok 2.55325 33 0 0 60 ok 2.9818 34 0 0 75 ok 2.53817 (*) unsuccessful registration

PAGE 85

72 Figure V 6 Pairwise Registration (Virtual Data) d [ Two range images in their original position (left), range images coarsely registered (right) ] Comparison VS ICP Test A s a point of reference of the proposed solution and other known solution this test is proposed. It uses a pair of range images with an overlapping area of more than 90 percent; this high overlap would guarantee that the ICP algorithm sampling would include a great number of coincidences even with low sampling percentages. The test uses t he virtual range images and positions them in very close transformation, near to the correct orientation and translation, these settings would not affect the proposed solution because it would still follow the same steps in the instruction pipeline but it would be a good starting position for ICP. The experiments used the same initial configuration for the range images and then the ICP parameters are modified. The test registers the time it take s for the coarse registration and compares it with the ICP outc omes.

PAGE 86

73 Table V 8 ICP vs. Proposed Algorithm Comparison. Sampling Iterations Time (s) Registration 0.85 200 35.5605 ok 0.6 200 26.9691 ok 0.5 200 20.5639 ok 0.85 100 9.77807 ok 0.5 100 11.799 ok 0.85 75 16.6375 ok 0.5 75 9.615 ok 0.85 50 13.0386 ok 0.5 50 7.3779 ok 0.85 25 8.41521 ok 0.5 25 5.27012 ok Proposed Algorithm 8.78023 ok Figure V 7 Full Registration Coarse and ICP (Real Data) [ Five range images coarsely registered from 3 different points of view ]

PAGE 87

74 Figure V 8 Full Registration Coarse and ICP (Virtual Data) [ Six range images coarsely registered (left), range images finely registered (right) ] Figure V 9 Un ordered Range Images (Real Data) [ Ten range images in their original position] Figure V 10 Un ordered Range Images Coarse Registration (Real Data) [ Range images coarsely registered back and front ]

PAGE 88

75 Figure V 11 Fine Registration (Real Data) [ Range images finely registered back and front ]

PAGE 89

76 CHAPTER V I CONCLUSIONS Experimental Conclusions The objective of this work was to develop an algorithm that is capable of registering unordered range images with error induced from faulty scanning devices, to solve this problem t his work prop o sed an innovative method for the automatic range image registration that combin es different types of registration, the optimization of a metric, th e feature recognition and an exhaustive search of the transformation range with a multilevel hierarchical structure that reduces the complexity of the match evaluation but maintains level of detail enough to differentiate possible matches After the experi mentation conducted on the algorithm it can be observed that the proposed hierarchical level approach helps to optimize the asymptotical time of the registration problem. The utilization of the feature recognition filters also help to reduce greatly the s earch space by eliminating all of the trivial solutions Compared to other proposals with hierarchical levels or feature recognition, instead of consisting only of two levels and that are the complete point clouds or a few points, the utilization of the mu ltiple levels is an improvement in the sense that it can keep valuable information for the registration at hand and be used as well as a simplification of discarding unviable solutions. The last point that I would like to remark is that the definition of t he simplified mesh consists of a known maximum number and that this compared to the approaches referenced in this work will reduce all the range images independently of the number of points in the range image. And that in real world applications like in so me of the sets that

PAGE 90

77 were used in this project the simplification would be detailed enough to find the surface properties and neglect the error induced by the scanner noise, while the feature detection approaches mentioned before would still recognize the n oisy features Limitations The proposed solution is limited to cases in which the objects shape is unique enough to be differentiated from each different point of view That is because spherical shapes in general, cubic shapes, or other completely symmetrical objects would find absolute minima in the same shapes that would not reconstruct the object but instead would treat them as barely the same scan repeated several times. Because of the point simplification process the algorithm is supposed to wo rk in cases where the contour is enough to find correspondences If the details are absolutely necessary to find correct correspondences, then this approach would not be able to do it correctly, however the assumption of a noisy scan means that the level o f detail is not good enough for those cases. The results of the experiments conducted to the different types of range images showed that as many other previous approaches this solution still finds correspondences for large surfaces of similar curvature eve n when they are not correct correspondences. This problem can be reduced by the type of scans that are delivered to the program. With a greater area of overlap between the range images, the greatest patch that can be found would be the corresponding overla pping areas of each point cloud However, the unordered batch alignment for very uniform surfaces like chairs, cars, etc., translates into a greater problem, since possible matches could be found in almost every pair. In these cases the possible solution i s to solve the registration in the delivered ordered cycle.

PAGE 91

78 Future Work The results obtained from t his work leave the door open for improvement by using some of the related works as reference. The use of the same structure configuration to parallelize the multi view range images registration and speed up the process used in [2] as well as the update of the complete structured registered could be adapted to the proposed solution Another area of opportunity is present in the evaluation metric of the registra tion; the algorithm uses the ICP or ICRP metrics, however these methods are known to be faulty in the sense that there may exist absolute minimum values that are not the correct solution. The research of an extra constraint to neglect the non coincident ab solute minimum value is a matter of great importance for this and any other work related to the registration. Lastly, the most obvious derivation from this work is the improvement of the fine registration process. ICP uses a randomized sampling process to select the points that will be optimized for the fine registration, however choosing a small sample the algorithm may receive points outside the overlapping areas of the point clouds, and therefore it becomes necessary to use a greater sample. The use of a large sample makes a very expensive process, but considering that the coarse registration is close enough and that the hierarchical structure is already detecting the intersections between the point clouds, then it could be possible to pass that informati on so that the sampling is only to be done in the intersecting areas.

PAGE 92

79 REFERENCES 1. RO MAN, 2011 IEEE pp. 331 336, 31 Jul. 3 Aug. 2011. 2. Makadia, A.; Patterson, A.; Point Clouds Conference on vol. 1, pp.1297 1304, 17 22 Jun. 2006. 3. Pattern Recognition, 2000 Proceedings. 15th International Conference on vol. 1, pp. 999 1002, 3 7 Sep. 2000. 4. Cybernetics and I ntelligent Systems, 2004 IEEE Conference on vol. 1, pp.158 163, 1 3 Dec. 2004. 5. Stage Algorithm for Accurate Registration of 3 Multimedia Technology (ICMT), 2011 International Conference pp. 6187 61 91, 26 28 Jul. 2011. 6. Computational Intelligence in Robotics and Automation (CIRA), 2009 IEEE International Symposium pp 328 333, 15 18 Dec. 2009 7 Krsek, P. 22nd Workshop of the Austrian Association for Pattern Recognition 1998 8 Rusu, R ., Fast Point Feature Histograms (FPFH) for 3D Registration Robotics and Automation, 2009. ICRA '09. IEEE International Conference on pp 3212 3217 12 17 May 2009 9 Smisek, J 3D with Kinect Computer Vision Workshops (ICCV Workshops), 2011 IEEE International Conference on pp 1154 1160, 6 13 Nov 2011 10 Narvaez, A. ; Ramirez, E. A Simple 3D Scanner Based On Passive Vision for Geometry Reconstruction Latin America Transactions, IEEE (Revista IEEE America Latina) pp 2125 2131, Sep 2012