dimensions (height, width, depth) and (3) there is always a certain one-to-one
correspondence between the the points that allows for a skew-less
transformation. In our test cases, the probability of the algorithm choosing a
correspondence that contains skewing is almost 5%. That is because the
parameters $T$ and $\lambda$ have been carefully chosen. However, even a 95%
success rate is unacceptable in an application whose main objective is to
reduce time and effort in labeling data sets. Henceforth, we need to find a
solution that not only provides an almost perfect accuracy but also does it
without losing the tool’s “real-time" property.
Since the user always choses four points, then at most there are $4!=24$
possible one-to-one correspondences between the points. Therefore, in the case
of the algorithm choosing wrong correspondences, we can start by exploring the
23 other possible correspondences to find the one that minimizes the skew
parameter. Hence, after the execution of the normal algorithm, we extract the
skew parameter from the calculated $4\times 4$ transformation matrix and test
if it is significant or not. In our testing we found that testing if it is
larger than 0.1 is the best option. If this condition is met then we have to
calculate the transformation at each of the 23 correspondences and choose
which one minimizes the standardized euclidean distance, $c_{d}ist$, between
the result and the target chosen by the user to calculate the result we simply
apply Equation 6.1. Therefore, we need to keep track of the smallest
$c_{d}ist$ achieved; let’s call the variable that does this bookkeeping
$min_{d}$. For each correspondence, we test the new found $c_{d}ist$ value to
the smallest one calculated to date and replace it in the case it is smaller,
otherwise we keep it the same. When the algorithm is completed, the
transformation resulting from the correspondence that had the smallest
$c_{d}ist$ is the one returned. Keep in mind that for any transformation’s
$c_{d}ist$ to be eligible of being compared to $min_{d}$, its skew has to be
lower than 0.1.

##### Improvements

The first improvement we can add is setting a breaking condition where, we no
longer try the rest of the possible correspondences. After checking that the
skew is lower than 0.1, if the $c_{d}ist$ is lower than a certain threshold.
Testing cases showed that a decent value of the error threshold is 0.15.
The second improvement is parallelizing the full process. By parallelizing we
mean launch a separate thread that evaluates each correspondence separately.
One thing we have to keep in mind is for the variable $min_{d}$ that keeps
track of the smallest $c_{d}ist$, concurrency should be handled as it is
checked and possibly changed by each thread. We protect this concurrency by
applying a fundamental concept in parallel computing, the Semaphore. We use a
simple semaphore that we initialize to the value 1; it is acquired by each
thread to check the condition on $min_{d}$: if the condition is true $min_{d}$
is updated and then the semaphore is released, otherwise the semaphore is
directly released. In the next section, we will provide the pseudo-code
explaining the proposed solution and its improvements.

####  6.5.5 Algorithm Pseudo-Code

Result: $4\times 4$ Transformation Matrix

Initialize parameters $T$ , $\lambda_{1}$, $\lambda_{2}$ and $M$;

Initialize parameters $d$ and $w$;

Begin A: Deterministic Annealing:

Begin B: Alternating Update:

Update transformation parameters $(d,w)$ using 6.16.;

End $B$;

Decrease $T$ , $k_{1}$; and $k_{2}$.;

End $A$;

Acquire mutex;

if  _skew $\textless$ 0.1_ then

if  _$c_{d}ist$ $\textless$ $mean_{d}$_ then

$mean_{d}$ = $c_{d}ist$

optimal_trans = calculated_trans;

end if

end if

Release mutex;

Algorithm 1 TPS-RPM assuming given correspondences (launched in threads)

Result: $4\times 4$ Transformation Matrix

Initialize parameters $T$ , $\lambda_{1}$ and $\lambda_{2}$;

Initialize parameters $M$, $d$, and $w$;

Begin A: Deterministic Annealing:

Begin B: Alternating Update:

Step I: Update correspondence matrix $M$ using (3)–(5).;

Step II: Update transformation parameters $(d,w)$ using Equation 6.16.;

End B;

Decrease $T$ , $k_{1}$ and $k_{2}$.;

End A;

if  _skew >0.1_ then

Initialize global parameters $mean_{d}$, mutex, optimal_trans;

for  _$i\leftarrow 0$ to $23$_ do

LaunchThread(Algorithm1(correspondance($i$)));

if  _$mean_{d}$ <0.15_ then

return optimal_trans

end if

end for

end if

return optimal_trans

Algorithm 2 Original TPS-RPM algorithm without outlier calculation in M

##### Analysis

The authors claim that TPS-RPM has a worst case runtime complexity of
O($n^{3}$). After our modifications, in the worst case, we will call a
simplified (given correspondence) TPS-RPM at most 23 more times. Thus, on a
single threaded machine or if the loop is not broken by any thread, the worst
case time complexity is O($24*n^{3}$), which is rendered asymptotically to
O($n^{3}$). As a result, even in the most unlikely of cases, our modifications
preserve the asymptotic run time complexity of the original algorithm is
preserved. Consequently, we have preserved the speed of TPS-RPM while
increasing our registration accuracy to 100%.

####  6.5.6 Implementation

Everything regarding the registration calculation was done on the Python
server side. The point sets are provided by Unity through websockets. Upon
retrieval the Python server executes Algorithm 2 and returns its output to
Unity. The latter applies it on the labeling object to transform it to the
correct position. We implemented TPS-RPM from scratch and modified it with the
aforementioned improvements.
The returned transformation matrix has the following form:

$\begin{pmatrix}s_{x}*r_{11}&s_{y}*r_{12}&s_{z}*r_{13}&t_{x}\\\
s_{x}*r_{21}&s_{y}*r_{22}&s_{z}*r_{23}&t_{y}\\\
s_{x}*r_{31}&s_{y}*r_{32}&s_{z}*r_{33}&t_{z}\\\ 0&0&0&1\ \end{pmatrix}$ (6.22)

where $s_{x},s_{y}$ and $s_{z}$ are the values of $S$ in the $x,y$ and $z$
axes respectively, $t_{x},t_{y}$ and $t_{z}$ are the values of $T$ in the
$x,y$ and $z$ axes respectively and $r_{ij}$/i,j$\in$$[1,3]$ are the values of
$R$.

###  6.6 Colliders in Unity3D

The points that are being selected are primitive objects of type spheres. To
be able to add the point on the desired object, the concept of colliders
should be introduced so that the point (sphere object) can collide with the
corresponding object and be attached to it.
In Unity3D, there’s a possibility to add a “Collider” component on an object,
that defines the shape of the object for the purpose of physical collisions,
the collider is invisible and should be the exact same shape as the object to
produce accurate collisions with other objects. There are multiple types of
colliders already implemented whether for 3D or 2D use. In this application,
three types were used:

  1. 1.

Box Colliders: This component was added to the labeling objects.

  2. 2.

Sphere Colliders: It was attached to the spheres that are eventually added as
a set of points on the labeling object.

  3. 3.

Mesh Colliders: This type was only attached to complex meshes, including
labeling object imported as CAD objects.

Figure 6.5: Box and Sphere Colliders

As a result, the points can now be attached to the labeling objects as shown
in Figure 6.5. Note that, in this figure the objects are not rendered, only
for the purpose of showing the sphere and box colliders (in green color).
After the points are attached to the labeling object, they are assigned as
children of this object; therefore, their coordinate system is now referenced
to the object and not Unity’s world coordinate system. That being said, the
coordinates of these points can now be sent to the server and the algorithm
can work efficiently to return the transformation of this labeling object.
Furthermore, to select the points on the target object, a mesh collider should
be attached to the imported mesh. In Unity3d, the mesh collider component
takes a mesh as an input and builds the collider based around that mesh.
However, to a add a collider on a specific mesh, that latter must contain a
number of vertices which is less than or equal to $65536$.
Two solutions were proposed, either adding multiple primitive colliders to the
mesh or simplifying the mesh so that each time it is loaded the number of
vertices is simplified to the desired amount that Unity3D accepts. However,
the first solution was somehow impossible, hence the complexity of the mesh
and the fact that it is loaded as one object that is not segmented into sub-
meshes. The second solution was feasible, but with the condition of keeping
the imported rendered mesh with the same high number of vertices and only
simplify the mesh that has to be taken as an input for the collider. In
addition to the two solutions already mentioned, mesh colliders in Unity3D
possess a convex property that could be enabled or disabled depending on
whether the developer wants to add the option of colliding with other mesh
colliders. However, one of the drawback of using this option is that it only
supports up to 255 triangles and it is obviously not suitable for this mode’s
use case. Figure 6.6 displays a convex mesh collider attached to one of the
test meshes that have been used. In fact, it is clear that this property
limits the details of the collider and thus provides a poor experience for the
user trying to set the points on a specific part of the mesh. For example: the
green trash bin showing in Figure 6.6. Therefore, applying a simplification
algorithm on the mesh and feeding it to the collider for maximum collision
accuracy, was the chosen solution to tackle the given problem.

Figure 6.6: Convex Mesh Collider

####  6.6.1 Mesh Simplification

##### Background

In recent years, the problem of surface simplification has received a lot of
attention. Many algorithms have been formulated to solve this problem and they
can be categorized into 3 classes:

  1. 1.

Vertex Decimation: It is based on iteratively selecting a vertex to be
removed, removing the adjacent faces and re-triangulating the resulting hole.

  2. 2.

Vertex Clustering: This algorithm is based on creating a bounding box around
the mesh and dividing it into a grid containing different cell. Within each
cell, the vertices are clustered together into one vertex and the faces are
updated accordingly. This method could be very fast but it provides a quality
that is often quite low. A solution for this problem was later on introduced,
explaining that this method could be generalized to use an octree555An octree
is a tree data structure in which each internal node has exactly eight
children..

  3. 3.

Iterative Edge Contraction: This method consists of simplifying the model by
choosing an edge and collapsing it (see Figure 6.7). Many algorithms
implemented this idea and the real difference between them is the way that
they chose the edge that is going to be contracted.

Figure 6.7: Edge Collapse

Micheal Garland and Paul S.Heckbert [73] discuss the limitations of the
algorithms already mentioned, by saying that these 3 classes of algorithms
don’t provide a high quality approximation (Vertex Clustering), nor general
(Vertex Decimation) nor supports aggregation. However, they developed an
algorithm that supports all these 3 properties at the same time. This method
is based on decimation via pair contraction which is a general form of edge
contraction. Nevertheless, since the algorithm uses edge collapse, a criterion
should be added to select an edge. Given two vertices, $v1$ and$v2$, a pair
$(v1,v2)$ is a valid pair for collapsing if:

  * •

$(v1,v2)$ is an edge (see Figure 6.7), or

  * •

$|v1-v2|<\epsilon$, where $\epsilon$ is a user defined constant that should be
carefully set. High threshold could enable vertices that are far from each
other to collapse which will ruin the topology of the model. (see Figure 6.8)

Figure 6.8: Non-Edge Collapse

In addition, to select the appropriate contraction at a given iteration, this
algorithm introduces a notion of cost of a contraction. This cost is defined
as the error at each vertex $\Delta(v)=v^{T}Qv$, where $Q$ is a $4\times 4$
symmetric matrix assigned to each vertex. Note that, since $Q_{v}$, is
$4\times 4$ matrix $\Delta V=\delta$, is the set of all points whose error
with respect to $Q$ is $\delta$ which is a surface of second degree in $v$
(quadric surface). Hence, this error is referred to as the quadric error
metric. In fact, $Q_{v}=\sum{M_{P}(v)}$ where $P=<a,b,c,d>$ is a plane that
contains an incident triangle of $v$ and $M_{P}$ is equal to the following
matrix:

$\centering M_{P}=PP^{T}=\quad\begin{bmatrix}a^{2}&ab&ac&ad\\\
ab&b^{2}&bc&bd\\\ ac&bc&c^{2}&cd\\\
ad&bd&cd&d^{2}\end{bmatrix}\quad\@add@centering$ (6.23)

Furthermore, after the pair of vertices is chosen, a simple way to collapse is
to move $v1$ to $v2$ or vice versa, or to $(v1+v2)/2$. However, this algorithm
introduces a better way to collapse the vertices by moving to a new point $v$
that minimizes the error
$\Delta(v)=(v^{T}Q_{v1}v+v^{T}Q_{v2}v)/2=(v^{T}(Q_{v1}+Q_{v2})v)/2$. After $v$
is computed, (v1,v2) is collapsed into $v$ with the error value $\Delta(v)$
and an error metric matrix of $Q_{v1}+Q_{v2}$. Moreover, finding the minimum
of a quadratic function is a linear problem and to find the new vertex $v$ we
need to solve the following equation:

$\centering\delta\Delta/\delta x_{v}=\delta\Delta/\delta
y_{v}=\delta\Delta/\delta z_{v}=0.\@add@centering$ (6.24)

##### Algorithm

Compute the error value and error matrix for each vertex of the mesh;

Select all valid edges $(v1,v2)$ such that $|v1-v2|<\epsilon$ ;

while  _an edge $(v1,v2)$ exists_ do

Minimize $\Delta(v)=(v^{T}(Q_{v1}+Q_{v2})v)/2$ to find v;

Let $\Delta(v)=(\Delta(v1)+\Delta(v2))/2$ and $Q_{v}=Q_{v1}+Q_{v2}$ ;

Place all selected edges in a heap using $\Delta(v)$ as a key;

end while

while  _Heap contains edges_ do

Remove the top edge $(v1,v2)$;

Collapse it to the computed v;

Update the mesh and the keys;

end while

Algorithm 3 Mesh Simplification Using Quadric Error Metrics

##### Implementation in Unity

This algorithm is already implemented by Mattias Edlund [74] and configured to
be able to work in Unity projects. It introduces two functions that simplify
the mesh, one with a quality parameter and the other without one. In our
implementation, we used the function that gave the opportunity to change the
target quality of the mesh, because it makes the target vertex count more
controllable than the one with no parameter. Moreover, this parameter is a
number between 0 and 1 that is multiplied by the number of triangles to
provide a threshold for the main iterations. The function returns the
simplified mesh when the original number of triangles subtracted by the number
of deleted triangles is less than or equal to the threshold.

Figure 6.9: Loading Collider Flowchart

However, after integrating this method into the tool and testing it, we
started changing the quality by trial and error and deduced the resulting
number of vertices by making sure that the vertex count is always less than or
equal to $65536$. After the testing phase, we concluded that the mesh vertices
are always varying and could lead to a simplified mesh that could not be
loaded as a collider in Unity. As a pre-processing method before loading the
data into the tool, the mesh is simplified so the vertex count is $\sim$ 1
million.

Figure 6.10: Concave Mesh Collider

Furthermore, to optimize the workflow of loading the collider when entering
Phantom Mode, we serialize the simplified mesh into a JSON file saved in the
same folder of the input mesh. Hence, the mesh will be simplified once, and
then it will be de-serialized and loaded much faster. The example in Figure
6.10 shows the same mesh of Figure 6.6 but after using the mesh simplifier and
adding the concave mesh collider. It shows the high level of details that
could be reached in the mesh in case of trying to collide with it. In
conclusion, this workflow (see Figure 6.9) added the possibility to apply
Phantom Mode on any loaded mesh, leading to a faster labeling action.

###  6.7 Websockets

WebSocket is a standardized communication protocol which produces a
communication over a TCP connection. It is a way to communicate in an
asynchronous way between a client which is the Unity software in our case and
the server which can be on the same machine or even on another machine.
Communication can be done using a secure protocol and can be used by any
client or server application.
The connection is bidirectional which means the data flows in both ways. The
WebSocket API lets the server and the client to push messages to each other at
any given time. This is be achieved without having the need to establish a new
connection, which allows a real time data flow.

####  6.7.1 Server Implementation

Before implementing the server side of our application, many technologies were
considered to enable a bi-directional communication between the Unity
application and the server, that is responsible to compute the main algorithm
and send the results back to the client. The first technology that we came
across is Sofi, a framework that was developed to provide a “pythonic” GUI by
packaging HTML5 libraries, in a way that all the processing is done using web
sockets within Python. However, this framework does not suit the use case of
our project, knowing that, it doesn’t include any interactions with the web,
for the meantime. The same issue was encountered when using the SocketIO
technology. SocketIO is a protocol that enables a real time connection between
clients and a server, but the client in this case is a web application or
mobile application, which leads to multiple complications when implementing a
SocketIO server, using the SocketIO Python library, and issuing a connection
to the Unity application.
Therefore, websockets Python library was used on top of asyncio [75] to
implement the server and ensure a real-time communication with the Unity
client. Nevertheless, the asyncio library provides the ability to write
asynchronous programs using the async/awaits syntax. With asyncio programming
there is no parallelism, the program is running on a single thread. However,
when the functions’ execution is pending, Python can run other functions and
proceed when they all have what they need to continue their execution. These
functions are called Coroutines, they are declared with async/await syntax
placed before the function, for example: “async def main():”. When a coroutine
runs, it generates a task that executes till the end, except if it encounters
an await, then it gets suspended and runs the other coroutine. The
asyncio.get_event_loop() will return the suspended task to continue its
execution. The websockets library provides the program with the server’s send
and receive functions, using the websockets.server module that defines the
WebSocket server API. This module includes a serve function that takes as
parameters: the coroutine to be executed, the host and the port on which the
server is listening, and returns an awaitable object that is handled by the
asyncio library using the asyncio.get_event_loop().run_until_complete (the
awaitable object).
The server implemented in Python, listens on port 4444 and returns an
awaitable that executes the coroutine. In this function, the server awaits
data from the connected client using the coroutine websocket.recv(), handles
the data and then sends it back to the client using the coroutine
websocket.send(). To keep the server on and listening at all times, the
asyncio.get_event_loop().run_forever() function that runs the main coroutine
indefinitely was used.
The client sends two $Nx3$ matrixes, one for the source points and the other
for the target points, where $N$ signifies the number of points selected. At
first, the client sends the source and target matrixes separately as a chain
of characters where the points are separated by a “/”, and the coordinates by
a comma. On the server side, each sent matrix was handled by splitting the
points and the coordinates to be able to create the arrays and pass them to
the main algorithm. The main registration algorithm returns a $4\times 4$
matrix, this latter is also transformed into a chain of characters and sent to
the client.
Moreover, to ensure that the computations done by the server are fast and
reliable, the server code was implemented on another machine. The client is
connected to the same network on which the server is on, and for the
websockets.server.serve function, the argument “None” that maps to the host
was passed. By that, the server was capable of receiving and sending data to
the client on the port 4444.

####  6.7.2 Message Structure

JSON is a lightweight data-structure that is easy to read and to parse by the
machines, this data structure is written in key/value pairs. The format used
to represent the data is seen in Figure 6.11.

Figure 6.11: Message Structure

On the server side, the json Python library provided functions to parse the
JSON sent by the client. The json.loads() function is used to convert the
chain of characters taken as an argument, into a JSON object that could be
easily manipulated by calling the keys of the JSON format (see Figure 6.12).

Figure 6.12: Python JSON handling

####  6.7.3 Client Implementation

In our project, multiple data must be sent to the server, so it can do the
calculations on the backend. Then, the client will receive back the $4\times
4$ matrix containing necessary information for the translation and rotation.
There are two cases, either the client wishes to perform a rotation and
translation normally, or they wish to only perform a rotation using the normal
of the points.
In the first case, the user can choose as much points as they wisheon the
source and target objects. Then, these points will be sent to the server in
the corresponding order using the WebSocket in a JSON format, specifying the
type of transformation requested by the user, along with the source and target
points, so it can easily be interpreted by the server. In the second case, the
user should choose three points on two objects, the source and target. The
program will calculate the normal of each object using the chosen points and
send these two vectors with the type of task to the server.
Moreover, the client should establish a connection using the server’s IP and
port number. Then, after clicking on an execution button to activate one of
the two transformation methods, the source and target points can each be sent
separately using only one connection. Nevertheless, JSON englobes the data in
one block, thus, the content of the data is easily extracted using JSON’s
functions. For futures tasks, JSON increases the scalability: if more types of
transformations or variables are to be added, it could be simply included as a
JSON key/value.
For the client’s implementation, WebSocketSharp library [76] was used, which
is a subset of the Socket.IO library. This latter can be found in the Unity
asset store for free which also contains a library to handle JSON objects. It
also works on most platform focusing equally on reliability and speed. For the
WebSocket implementation, some basic event handlers should be defined: “On
Open”, “On Close”, and “On Message”.

  * •

“On Open” event will be activated when the connection between the client and
the server is established.

  * •

“On Message” event will be called when receiving data to the client socket.
After receiving a message, the connection will automatically close, but this
can be modified in the library.

  * •

“On Close” event will run when the connection to the server ends.

To send a message, the send() function already implemented in the imported
WebSocketSharp library has to be called, followed by the message of type
String which will be the JSON message to be sent.
Moreover, a JSON object from the received message is created to access its
data, but a problem occurred when using the JSON library’s constructor: the
accuracy of the data went down from numbers in 62 bits to 32 bits. A solution
had to be found since the accuracy plays a major role in moving objects. Since
only double types were needed, some unnecessary functions using or converting
to float type were removed. After creating the object, the program will access
each data in the received message, add them to a $4\times 4$ matrix and
finally lunch a block of code to run, which will be the start of the
transformation.

###  6.8 The Labeling Element Transformation

After selecting the points on the source and target objects in the right spots
with the help of the accurate colliders, the points are sent to the Python
server through websockets in a custom format. Then, the server returns a
transformation matrix, responsible for the change of position, rotation and
scale of the source object onto the target mesh.
Knowing that the points were relative to the source object origin, the
transformation should be done accordingly. To be able to do that in Unity, we
dissected the returned transformation matrix to extract the position, rotation
and scale, then we applied each one on the source object so it can be finally
transformed to the desired location.

###  6.9 User Interface

For the user interface of this mode, we added a button labeled Phantom Mode,
takes the user into another panel (see Figure 6.13). In this window, we notice
that the source points are already been selected on the source object, the
user needs only to add the points on the mesh and click on Run Transformation
in the footer to launch the process.

Figure 6.13: Phantom Mode User Interface

However, the user can still select the custom points on the source target if
they click on Rest Selection button. In addition, if a point is wrongly added
the user can still click on the escape key to revert the last point added. As
a result, the user experience became more intuitive. When the user is done
using this mode, they can click on Normal Mode to go back to the standard
labeling process.

##  Chapter 7 Labeling Without a Mesh

###  7.1 Problem Statement

We have already covered the process of using a 3D reconstructed mesh from RGBD
images to label said images. However, in certain cases, where we only have
access to the RGB images and the camera positions, we cannot reconstruct the
mesh. In this chapter, we tackle the case where we label the images without
the presence of the mesh.

###  7.2 Assumption

To render this problem feasible, we make a prior assumption that we already
know the size of the object we want to label. For instance, if we have a CAD
object that represents the object we want to label.

###  7.3 Theory

####  7.3.1 Definition

Let’s define a rectangular cuboid $B$ (Represented in Figure 7.1) with
specific known dimensions (height, width, depth). Let’s take three points on
this object (${p_{1},p_{2},p_{3}}$). We also define $O$ as a point in space.
We can solve the problem in Section 7.1 by reducing it to the following
problem:
Given three lines ($l_{1},l_{2},l_{3}$) created by connecting $O$ and
($c_{1},c_{2},c_{3}$) respectively, we need to find the position of three
points ($f_{1},f_{2},f_{3}$) on ($l_{1},l_{2},l_{3}$) respectively while
keeping the distances ($p_{1}p_{2},p_{2}p_{3},p_{1}p_{3}$) equal to
($f_{1}f_{2},f_{2}f_{3},f_{1}f_{3}$).

Figure 7.1: Rectangular Cuboid $B$ Figure 7.2: Problem Representation

A geometrical representation of the problem can be found in figure 7.2.

####  7.3.2 Problem Breakdown

The first thing to consider is that $f_{1}$, $f_{2}$ and $f_{3}$ should each
be on $l_{1}$, $l_{2}$ and $l_{3}$ respectively, thus defining the following
three constraints: (1) $f_{1}\in l_{1}$, (2) $f_{2}\in l_{2}$ and (3)
$f_{3}\in l_{3}$.
The equation (in vector form) of a line in 3D space passing through the point
$(x_{0},y_{0},z_{0})$ and traveling in the direction $(a,b,c)$ is:

$(x,y,z)=(x_{0},y_{0},z_{0})+t(a,b,c)$ (7.1)

where $t$ is a parameter describing a particular point on the line. We can
calculate $t$ for the points ($c_{1},c_{2},c_{3}$) for each line:

$\begin{cases}t_{c_{1}}=c_{1}-O\\\ t_{c_{2}}=c_{2}-O\\\
t_{c_{3}}=c_{3}-O\end{cases}$ (7.2)

Thus the coordinates of $p_{1},p_{2}$ and $p_{3}$ are :

$\begin{cases}f_{1}=O+t_{c_{1}}*u_{1}\\\ f_{2}=O+t_{c_{2}}*u_{2}\\\
f_{3}=O+t_{c_{3}}*u_{3}\end{cases}$ (7.3)

where $u_{1},u_{2}$ and $u_{3}$ are the unknowns we need to determine.
Second we define three equations that represent the distance constraint
mentioned in section 7.3.1:

$p_{1}p_{2}=f_{1}f_{2}$ (7.4) $p_{2}p_{3}=f_{2}f_{3}$ (7.5)
$p_{1}p_{3}=f_{1}f_{3}$ (7.6)

The distance between two points in 3D space can be calculated using the
following equation:

$dist=\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}+(z_{1}-z_{2})^{2}}$ (7.7)

If we replace Equation 7.7 & 7.3 in Equations 7.4, 7.5 & 7.6 we get the
following non-linear system of equations:

$\begin{cases}dist(p_{1},p_{2})=dist(O+t_{c_{1}}*u_{1},O+t_{c_{2}}*u_{2})\\\
dist(p_{2},p_{3})=dist(O+t_{c_{2}}*u_{2},O+t_{c_{3}}*u_{3})\\\
dist(p_{1},p_{3})=dist(O+t_{c_{1}}*u_{1},O+t_{c_{3}}*u_{3})\end{cases}$ (7.8)

####  7.3.3 Solving the Equation

We can clearly see that equation 7.8 is a system of three equations with three
unknowns($u_{1},u_{2},u_{3}$). We can also deduce that it is a non linear
system since if we square both sides of the equations we obtain a sum of
squares. We will solve for the three unknowns using a numerical method.

##### Newton-Raphson

The Newton-Raphson method is the first in the class of Householder’s methods,
it is defined by the following equation:

$x_{n+1}=x_{n}-\frac{f(x_{n})}{f^{\prime}(x_{n})}$ (7.9)

It can be generalized to solve systems of $k$ nonlinear equations by left
multiplying with the inverse of the $k\times k$ Jacobian matrix $J_{F}(x_{n})$
instead of dividing by $f^{\prime}(x_{n})$:

$x_{n+1}=x_{n}-J_{F}(x_{n})^{-1}F(x_{n})$ (7.10)

Newton-Raphson is a method of quadratic convergence and hence rapid. However,
global convergence is not guaranteed for all initial estimates and for example
fails for the two following cases:

###### Stationary Iteration point:

Consider the function $f(x)=1-x^{2}$, if we start at $x_{0}=0$ then $x_{1}$
will be undefined since the tangent to a point on the $X$ axis (0,1) is
parallel to the $X$ axis:
$x_{1}=x_{0}-\frac{f(x_{0}}{f^{\prime}(x_{0})}=0-\frac{1}{0}$

###### Starting point enters a cycle:

Consider the function $f(x)=x^{3}-2x+2$, for a starting point of 0, the
algorithm will alternate between 1 and 0 and will never converge.
As we can see we cannot rely on this method directly. We decided to use a
method that supports constrained solution searching and use its result as an
input to the Newton-Raphson method.

##### DOG_BOX

The DOG_BOX method [77] is a trust region method for solving bound constrained
nonlinear optimization problems. Unlike other popular methods that use
ellipsoid trust regions, this procedure uses a rectangular shape which is much
simpler due to the constraints being linear. It uses a modification of Powel’s
dogleg technique [78] to find the solutions.
The advantage of this method is that it supports bounds on the unknown
variables, which means we can constrain the depth value of the unknowns to be
superior to the depth value of $O$. This is done because in our problem the
box $B$ can fit either in front of $O$ or behind it, please refer to Figure
7.3 for a visual representation.

Figure 7.3: Bounded Problem $B$

After we solve the system of non linear equations 7.8 using the DOX_BOX
method. We input the approximated ($u_{1},u_{2},u_{3}$) as a starting estimate
to the generalized Newton-Raphson method and use its output as the final
solution.

##### Calculating ($f_{1},f_{2},f_{3}$)

We replace the final values of ($u_{1},u_{2},u_{3}$) in equation 7.3 and get
the coordinates of the three points ($f_{1},f_{2},f_{3}$).

####  7.3.4 Rigid Registration

Now that we have the three points ($f_{1},f_{2},f_{3}$) on the lines
($l_{1},l_{2},l_{3}$), and we already have the three points
($p_{1},p_{2},p_{3}$) on the box $B$, we calculate the optimal rigid
transformation matrix (6 DoF) that transforms ($p_{1},p_{2},p_{3}$) to
($f_{1},f_{2},f_{3}$).
For the same reasons discussed before, we need a global deterministic rigid
registration method. We used [79] in the the first part of our final year
project, it assumes correspondence are given and always finds the optimal
rigid transformation matrix while avoiding any reflection. The returned
transformation matrix has the following form:

$\begin{pmatrix}r_{11}&r_{12}&r_{13}&t_{x}\\\ r_{21}&r_{22}&r_{23}&t_{y}\\\
r_{31}&r_{32}&r_{33}&t_{z}\\\ 0&0&0&1\ \end{pmatrix}$ (7.11)

###  7.4 Problem Reduction

To solve the problem described in Section 7.1, we have to reduce it the the
problem in Section 7.3. In consequence, solving the first problem is done by
simply solving the second one. By performing the following reductions:

  * •

$B$ is the labeling object.

  * •

$O$ is the center of the camera that took a 2D image in which and object we
want to label exists.

  * •

($p_{1},p_{2},p_{3}$) are the points selected by the user on $B$

  * •

($c_{1},c_{2},c_{3}$) are the points selected on the 2D image that together
with $O$ will create the lines.

  * •

($f_{1},f_{2},f_{3}$) are the 3D points we wish to find, they represent where
$B$ should be placed (in other words, where ($p_{1},p_{2},p_{3}$) should be
transformed to)

We successfully reduce our original problem into one we can solve. In the next
section we will present a detailed walk-through of how we implemented this
solution.

###  7.5 Implementation in Unity

In this section, we will talk about how this idea is translated into Unity
along with the implementation of the user interface and all of the necessary
functionalities.

####  7.5.1 CAD Objects as Labeling Elements

To be able to apply this method in the tool, the user must acquire the CAD
models of the objects that the user wants to label, knowing that this method
is used as a rigid transformation and the source object must have the same
size of the target object. For that matter a "Run Time Importer" was
integrated to the tool from Unity’s assets store. This package loads an ".obj"
file and creates a game object in the scene that contains the mesh of this
imported 3D model (see Figure 7.4).

Figure 7.4: CAD Object Example in Scene

##### Inventory Panel

To be able to get the most out of this asset to complement the user experience
in the tool, an inventory panel was implemented to encapsulate all the CAD
models that the user imports. In this case the user does not have to import
the model each time he wants to add it to the scene, the user can check the
inventory and load the CAD object from it. Nevertheless, we used Unity’s
"Streaming Assets" to store the objects in it after they gets imported. When a
project is built in Unity, most of the assets are encapsulated into one
package except the "Streaming Assets" folder which is a normal file system
accessible via a path name: “Application.dataPath + "/StreamingAssets"".
Furthermore, the inventory was created as a panel on the right hand side of
the tool where the user can toggle it on or off. In this panel there’s a "+"
button to import the desired CAD objects into the inventory. Note that if
there is an image of the CAD model in its path, it also get imported and shown
in the inventory. Finally, the user clicks on the image to load the CAD object
to the scene (see Figure 7.5).

Figure 7.5: Inventory Panel

##### CAD Objects in Phantom Mode

When the user enters “Phantom Mode", all of the added labeling objects (CAD or
primitive objects) are shown in a preview window in the bottom right corner,
where the user clicks on the object to add the points that needs to be
registered using the Python server. However, the preview window is a camera
that renders only objects that the user wants to apply the transformations to.
Moreover, because it is hard to know the exact size of the CAD objects, so
there is a possibility that they wont fit into the preview window. We added a
camera control script for the preview window camera, and as a result, the user
could navigate in the preview window while adding the source points.
In contrast, when the CAD models are imported into the scene, we made sure
that if they contained sub-meshes, they would be combined into one mesh, hence
one object. This is done to make the transformation straightforward for one
object, without thinking about how to transform the child objects in case the
point is selected on that specific child object; in other terms, after the
transformation is applied, the object will be decomposed.

####  7.5.2 Point Selection

To activate this mode, the user must toggle on the “2D" text on the down left
panel (see Figure 7.6). As a result, the user can now select points on the CAD
object in the same fashion as the normal mode and the RGB images (top-right
side of the main panel) are now interactive and the user can click on them to
select the target points. In addition, if the mesh isn’t loaded and the user
clicks on “Phantom Mode", the “2D" mode is directly activated.
Note that in this mode, the points correspondence is mandatory, that is why
the user should keep track of the color sequence on the source and target
objects and ensure that the order and placement of the points is convenient.

Figure 7.6: “2D" Toggle

##### Source Point Selection

As already discussed in the “Phantom Mode" chapter on colliders and
specifically mesh colliders, in this mode we apply the mesh collider on the
CAD model to be able to select the points (spheres) on it because of the
collision between the two game objects. Nevertheless, to perform the problem
reduction in our application, the object shown in Figure 7.7 represents the
labeling object $B$ and the points that are selected on it represent the set
($p_{1},p_{2},p_{3}$) that are finally added to an array to be sent to the
Python server.

Figure 7.7: Source Point Selection Example

##### Point Selection on the Image

Furthermore, after selecting the points on the source labeling object, the
user can now click on the image and add the three points on the target object
with the same color correspondence of the source set of points.
First, the image that the user clicks on is the render texture of the shot
view camera that we talked about in the bounding box chapter. In other terms,
it is a scaled version of the camera’s image frame. For that matter, in this
application, the origin of the camera is the origin of the shot view camera.
Second, when the user clicks on the image, they are actually activating a ray
to be generated from the shot view camera to the image frame on the same
position of his cursor. This is done using the “ScreenPointToRay" function in
Unity that is responsible to return a ray object from the camera through a
screen point given as an argument to the function. Nevertheless, the challenge
was to calculate the cursor’s position that should be given to this function.
Knowing that the camera’s raycast in Unity is equivalent to where the mouse
position hits, helped us to form a logic of the workflow that should be done
to produce the results that we needed. First of all, we calculated the $x$ and
$y$ coordinates of the cursor’s position relative to the texture of the raw
image on which the user clicks on (top-right image of Figure 7.5). To do that,
we used Unity’s “ScreenPointToLocalPointInRectangle" function that transforms
the cursor’s position to the rectangle’s (raw image) local space. Then,
knowing that the resolution of the showing rectangle is different than the
texture’s resolution, we had to find the coordinates of the point in the
texture’s coordinate system by multiplying the cursor position by the ratio of
the texture’s and the rectangle’s resolutions, then limiting the value between
0 and the texture’s width or height. This can simply be translated into the
following equation that calculates the $x$ coordinate of the point to be added
on the image frame (same equation for the $Y$ axis using the height):

$Imageframe.x=Localcursor.x\frac{Texture.width}{Rectangle.width}$ (7.12)

####  7.5.3 Sending the Points

As a result, on each ray hit, a sphere is created on the image frame (that
contains a collider) and then rendered and shown directly onto the raw image
on which the user clicked (see Figure 7.8). These spheres corresponds to the
set ($c_{1},c_{2},c_{3}$), they are added to an array along with the camera’s
position (origin).
Finally, the source and target points are sent to the server along with a key
that says "2D" (to notify the server of the transformation to be done) through
websockets.

Figure 7.8: Selecting Points on Image Example

###  7.6 Implementation in Python Server

After receiving the two arrays of points from the Unity side, we unpack the
target array and get the 4 points (origin and 3 points selected by the user on
the image). We then basically follow the same steps described in Section 7.3
to build the system of non linear Equation 7.8. Once that is done, we use the
pyneqsys [80] to apply the DOX_BOX method with the only bound given on the
depth value to be larger than the origin’s depth. We then use the result of
DOG_BOX as an initial estimate to the Newton-Raphson method (also implemented
in the pyneqsys library). Then, we get the target points from the unknowns we
calculated. Finally, call the Umeyama method[79] passing the source and the
calculated target points. We will receive the optimal rigid transformation
matrix that transforms the source points onto the target points. We send that
matrix back to the Unity side through the same websockets connection.

###  7.7 Results

When the server finishes all the calculations, it sends back a transformation
matrix describing how the labeling object should be translated and rotated. On
the Unity side, this transformation is applied and the results are shown in
the following Figures 7.9 and 7.10. Note that, these results are produced from
a data set where the mesh was not imported. Hence, this translates the use
case of this functionality in the tool in case the data set does not include a
mesh.
In contrast, this method has a drawback concerning the user experience in
terms of labeling, because the object can cover the whole image and that
prevents the user to continue labeling other objects behind it, as showing in
Figure 7.10. As a solution, we recommend the user to change the transparency
of the labeling object to be able to see behind it (see Figure 7.11).

Figure 7.9: Results - 1 Figure 7.10: Results - 2 Figure 7.11: Results - 3

##  Chapter 8 Labeling Large Point Clouds

###  8.1 Motivation

We have already described the usual way to create data for the tool. That is
using a camera equipped with a depth sensor and then reconstructing the mesh
from the RGBD images taken by it. However, at BMW Group, the majority of the
plants possess laser scanned point clouds of their plants; see Figure 8.2.
These scans are usually taken by a scanner named FARO. They would like to
label objects in these scans but labeling point clouds directly is still an
unexplored field, moreover all of the object recognition models learn on
labeled 2D images. Therefore, we need to create a workflow that can take these
large pointclouds and transform them into data that can be labeled by our
tool. In other words, (1) extract a triangular mesh (Section 8.2) and (2)
extract RGB images (taken at specific camera positions) of that mesh (Section
8.3).

###  8.2 Surface Reconstruction

A blossoming subfield of computer graphics is perfect candidate to solve our
first problem. In essence, it is the process of inferring (reconstructing) a
3D object from a set of unorganized discrete points that represent its shape.
New advancements in data acquisition are the reason in the spark of interest
in surface reconstruction. From optical laser-based range scanners, LiDAR
scanners, structured light scanners, multi-view stereo to now inexpensive
commodities like the Microsoft Kinect, point cloud extraction has become more
accessible as time passes. Although the plethora of acquisition methods are
great advancements in computer graphics, they also pose significant problems
since each scanner produces point clouds with certain properties and certain
imperfections. To cope with this variety, different classes of surface
reconstruction algorithms were created each solving for a certain set of prior
assumptions and robust against a certain type of imperfection. From methods
that make little to no assumption on the quality of the point cloud and output
non-mesh based reconstructions, to methods that assume a well sampled point
cloud and produce a water tight triangular mesh.
In this section, we will present an overview on reconstruction methods
comparing their different characteristics and explaining different prior
assumptions they pose in the inputted point cloud. We will then delve deeper
into the algorithms that we tried and compare their pros and cons. Finally, we
will present a workflow that takes an unorganized point cloud and outputs a
watertight mesh.

####  8.2.1 Point Cloud Imperfections

The five main imperfections that can plague a certain point clouds are: (1)
noise, (2) sampling density, (3) misalignment, (4) outliers and (5) missing
data. Refer to Figure 8.1 for a visual representation.

Figure 8.1: 2D representation of point cloud imperfections Figure 8.2: Example
of Point Cloud received from BMW plants

##### Noise

Traditionally, points that are spread randomly close to the surface are
regarded as noise. Noise can be introduced in different ways such as depth
quantization, sensor noise and orientation or distance of the surface in
relation to the scanner. The now conventional way of dealing with noise in
surface reconstruction algorithms is to to produce a surface that passes near
the points as much as possible but without over-fitting the noise. [81] that
imposes smoothness on the output and [82] which uses robust statistics are two
algorithms very robust agains noise.

##### Sampling Density

Sampling density is one of the most import artifacts for point clouds. It
describes the distribution of the points that sample the surface. It is
critical because it defines a neighborhood which in turn defines the local
geometry of the surface. The neighborhood should be small enough to capture
small details in the mesh, yet large enough to describe the local geometry.
The problem is that usually, scanners produce non-uniform sampling on the
surface. A good practice we adopted is using poisson disk sampling [83] and
keep point samples given a specific distance between them. Thus the point
cloud becomes uniformly sampled.

##### Misalignment

The biggest cause of misalignment is the flawed registration of range scans.
Contrarily to what one might think, handling misalignment is not the same as
handling noise. For example, by assuming a prior of Manhattan world [84], a
scene consists of planar primitives aligned by three orthogonal axes, so
planar primitives from mistakenly rotated scans can be robustly "snapped" onto
one of these axes.

##### Outliers

Points that are very far from the surface are outliers. Unlike noise, outliers
should not be taken into account when reconstructing the point cloud. In most
cases, outliers can be handled implicitly using robust surface reconstruction
methods [85], but in some cases where the outliers are more structured (high
density clusters of points exist far from the surface) like in multi-view
stereo acquisition (where view-dependent specularities can results in false
correspondences) it’s better to handle them explicitly through outlier
detection.

##### Missing Data

Missing data is a motivating factor behind many reconstruction techniques.
Missing data is due to variables such as restricted sensor range, elevated
light absorption, and occlusions in the scanning method that do not sample big
parts of the form. Despite continuous improvement of the aforementioned
artifacts, missing data tends to persist due to the device’s physical
limitations. We notice that missing data differs from non-uniform sampling,
since the sampling density in these areas is zero. Most methods deal with
missing data by assuming that the scanned point cloud is watertight. Other
approaches seek to reconstruct higher-level information such as shape
primitives, canonical regularities, skeleton and symmetry relationships for
significant missing data.

####  8.2.2 Input

Different inputs are required by different reconstructions algorithms. The
base input however is the position of each point in 3D space. That may suffice
for some simple reconstructions but most of the time other inputs are added to
make reconstruction simpler, especially for very challenging point clouds. We
detail the different possible inputs in this section.

##### Surface Normals

Surface normals are defined at every point and represent the direction
perpendicular to the points tangent space. In other words, its the direction
perpendicular to the surface that surrounds a certain point. Normals can be
oriented where a normal is consistently pointing inside or outside the
surface, or unorientated in the opposite case.

###### Unoriented Normals:

When a surface normal is either pointing on the outside or the inside then the
normal is unoriented. According to our research they are used in one of three
ways: (1) Constructing an unsigned distance field [86], (2) Projecting a point
onto an approximation of the surface [87] and (3) determining planar regions
in a point cloud [88].
Unoriented Normals can be estimated from a raw point cloud. The best known way
is using principal component analysis of the neighborhood of a point and use
the smallest principal component from the calculated covariance matrix [89].
However, since it uses the neighborhoods of the points it can be sensitive to
imperfections such as noise and sampling density. As a result, reconstruction
methods used after estimation of these sometimes “noisy" normals should be
robust to them.

###### Oriented Normals:

Oriented normals also either point to outside or the inside, but the
difference is when an oriented normal is pointing on the inside we know the
point is on the interior of the surface and when it is pointing to the outside
then the point is on the exterior of the surface. At first, it was used to
construct a signed distance field over the ambient space, where the field
either takes a positve value indicating that the point is on the exterior and
a negative values in the opposite case. We can then extract the surface by
performing a zero crossing on the calculated signed distance field. More
recently, this concept was generalized to implicit fields and indicator
functions, but the basic idea still holds true [90, 81, 91].
Similarly to unoriented normals, oriented normals can also be estimated. As an
example in [89], a graph is constructed of the point cloud and weights each
edge $w_{ij}$ for points $p_{i}$ and $p_{j}$ based on the similarity between
the respective points’ unoriented normals $n_{i}$ and $n_{j}$ as
$w_{ij}=1-|n_{i}·n_{j}|$. A minimal spanning tree is then built, where upon
fixing a normal orientation at a single point serving as the root, normal
orientation is propagated over the tree. Comparatively to unoriented normals,
these methods are sensitive to imperfections in the point clouds and thus can
orient normals in the opposite direction.

##### Scanner information

The scanner that obtained the point cloud can provide helpful surface
reconstruction data. Its 2D grid design makes it possible to estimate the
sampling density that can be used to identify certain types of outliers–points
whose lattice neighbors are at a much higher range than the sampling density
are probable outliers. Caution must be taken to distinguish outliers from
sharp features, however.
Scanner data can also be used to define a point’s confidence, which is helpful
to manage noise. Some scanners (e.g. LiDAR) provide measurements of confidence
in the form of reflectivity measured at each point. One can also derive trust
through information on the line of sight. Line of sight is the collection of
line segments between each point in the point cloud and the position of the
scanner head from which the point was obtained. If the angle between the line
of sight and the normal is big in active scanning systems, i.e. laser-based
scanners, this can lead to a noisy depth estimate, i.e. bad laser peak
estimate [92], which implies low confidence.
Note that the line of sight also defines the regions that are lying outside of
the shape. The combination of line of sight from multiple scans refines the
boundary area in which the surface is located, this is called the visual hull.

##### RGB Images

Different methods of acquisition that complement the acquisition of depth can
be of excellent help. RGB image acquisition is a very popular method that goes
hand in hand with countless sensors, like the Microsoft Kinect. In the case of
the Kinect, the RGB camera is co-located with the IR camera, so if we assume
the two are calibrated, the identification of corresponding depth and RGB
values at a pixel level is straightforward.
RGB images are most helpful for reconstruction in complementing depth
information that is either not as descriptive as their visual appearance, or
simply not measured by the data. For example, if a color image and 3D scan are
at a wide baseline with very different views, then segmented parts of the
image can be used in the original scan to infer 3D geometry [93].

####  8.2.3 Priors

Priors’ growth is mainly influenced by emerging technologies for data
acquisition. Acquisition techniques set expectations for the class of objects
that can be obtained and the type of artifacts connected with the information
obtained, also informing the sort of output generated by reconstruction
algorithms and the fidelity of reconstruction. In this section we will lay out
an overview of available priors, discussing their produced outputs and
expected inputs, additionally characterizing these scenarios by the typical
shape classes and procurement techniques. We will end by analyzing and
choosing the best prior for our case to narrow our search for the optimal
reconstruction algorithm.

##### Surface Smoothness

There are three types of surface smoothness priors. First, local smoothness
seeks smoothness in close proximity to the data. The output of these methods
are usually robust to noise and nonuniform sampling but they struggle to
preserve fine detail in the reconstruction [89, 87]. Second, global smoothness
strives for large-scale smoothness, higher order smoothness or both. Large-
scale herein relates to the spatial scale where smoothness is enforced not
just near the input. It is common for these methods to focus on reconstructing
individual objects, producing watertight surfaces [90, 81]. High order
smoothness relates to the variation of differential properties of the surface:
area, tangent plane, curvature, etc. As a consequence, this confines the shape
class to objects that can be captured as fully as possible from various
perspectives. Desktop scans capable of scanning tiny objects (i.e. 1 inch) to
medium-sized objects (i.e. several feet) are frequently used to create such
point clouds. Ideal devices for such scenarios are laser-based optical
triangulation scanners, time-of-flight (TOF) scanners, and IR-based structured
lighting scanners.In addition, due to the close proximity of the sensor to an
object and its high resolution capabilities, the reconstruction of very fine-
grained detail is commonly emphasized.

##### Visibility

The previous visibility makes assumptions about the rebuilt scene’s exterior
space, and how this can provide clues to combat noise, non-uniform sampling,
and missing information. Visibility of scanners is a powerful precedent as
discussed in Section 8.2.2, as it can provide for an acquisition-dependent
noise model and be used to infer empty space areas [92]. This allows the
filtering of powerful, organized noise for water-tight reconstruction of
individual objects [94], a common feature of multi-view stereo inputs. More
recently, some scanners expanded the visibility prior to scene reconstruction
like for example The Microsoft Kinect and the Intel Real Sense(Already seen in
Chapter 3).

##### Volume Smoothness

Similarly to surface smoothness, volume smoothness imposes smoothness on the
shape’s volume. This prior mainly solves for point clouds with significant
missing data [95]. In fact, they assume that the scanners capturing the point
cloud have limited range and mobility and therefore cannot extract a well
sampled point cloud. Other methods extract the skeleton structure of the shape
from significant missing data.

##### Primitives

The geometric primitives prior assumes that a compact set of easy geometric
forms, i.e. cylinders, boxes, spheres, planes, etc., can explain the scene’s
geometry. In instances where watertight reconstruction of individual objects
is concerned, the detection of primitives [96] may subsequently be used for
primitive reconstruction extrapolation when confronted with big quantities of
missing information [96]. Some examples that benefit from this type of prior
are CAD objects(usually modeled through simple geometry shapes) and indoor
environments(can be summarized as a collection of boxes and planes)

##### GLobal Regularity

Many shapes such as man-made shapes, CAD models and architectural shapes,
contain a certain level of regularity in their higher level composition. The
global regularity prior takes advantage of this fact combat missing data.
Regularity in a shape can take many forms, such as a building made up of
façade components, building interiors made up of periodic shape arrangements,
or a mechanical component made up of recurrent orientation relationships
between sub-parts [97].

##### Data Driven

The data driven prior takes advantage of the large-scale availability of 3D
data acquired or modeled, mainly in scenarios where the input point cloud is
highly incomplete. In these scenarios we are mainly concentrated on the
reconstruction of individual objects, or a collection of objects, as 3D
databases tend to be populated with well-defined classes of semantic objects.
For example, we may be concerned with acquiring a watertight reconstruction of
an individual object from just one or more depth scans. An object database may
be used to best match the unfinished point cloud to a full model, or to
compose components from various designs [98]. In other cases, the
reconstruction of the scene and the use of the database to complement the
objects detected in the scene [99] may be implicated. Because of its
generality, the data driven prior’s reconstruction is only as good as the
provided data.

##### User Driven

The user guided prior includes the user into the reconstruction phase of the
surface, enabling them to provide intuitive and helpful signals for
reconstruction. The specific form of interaction is mainly motivated by the
type of shape being reconstructed and how it was obtained. Often the focus is
on topology recovery owing to incomplete sampling from the sensor. Some
methods therefore concentrate on the reconstruction of arbitrary forms, while
others acknowledge interactions with the skeletal model of a shape, relying on
volumetric smoothness before guiding reconstruction. Scanning in outdoor
environments can cause large gaps in acquisition in the reconstruction of
architectural buildings, similar to the case of façades mentioned in Section
8.2.3. User interaction can therefore assist discover global regularity, as
well as how the identified regularity can be applied to the remainder of the
point cloud [100]. If fine grained reconstruction control is required, the
user may indicate primitive geometry to model the construction, guided by the
interactions found in the input [101].

####  8.2.4 Analysis

##### Imperfections

The point clouds we receive are captured using FARO laser scanner. After
analyzing these point clouds we realized that Missing data, misalignment of
scans and outliers were rare occurrences. On the other hand, noisy data and
nonuniform sampling were very prominent. Therefore, we should first use
poisson disk sampling to sample the points in a uniform manner as seen in
Section 8.2.1. Moreover we should choose a surface reconstruction algorithm
that is very robust against noise.

##### Point Cloud inputs

As we have previously discussed, the base requirement of any surface
reconstruction algorithm is the coordinates of the points. The more inputs we
use the easier it is to deal with imperfections and the better accuracy we
will achieve. In the scans we receive, we are provided with oriented normals
which as we have discussed in Section 8.2.2 provide extremely useful cues for
reconstruction algorithms – see [90, 81]. Unfortunately, scanner information
and RGB images are not provided.

##### Priors

To choose the best prior we should use we have to recapitulate the nature of
our received point clouds. The point clouds we receive are very large scans of
the indoors of a warehouse. It is full of pallets, boxes, robots and dolleys
among other objects. Since we will use this mesh to extract rgb images that we
label in the tool and train the machine learning model with, we require the
reconstruction of this point cloud with the highest possible accuracy. The
finest details should be preserved. Priors like visibility and primitives are
not beneficial since they are mainly robust against reconstructing single
objects like in the case of CAD Models. Data-driven priors rely on available
databases of objects which we don’t poses. User-driven priors requires input
from the user that might be useful but for very large meshes it would be
extremely time consuming and difficult for the user to provide good enough
feedback that would justify the compromise of time. Global Regularity is more
focused on reconstructing objects that contain pattern in them, however again,
the size of the mesh and therefore its diversity will make it nearly
impossible to extract good patterns, additionally it usually fails to preserve
fine detail. Volume smoothness solves for the very specific problem of the
abundance of missing data, a problem which we do not face thanks to the
mobility of the FARO laser scanner. Finally, surface smoothness comes three-
fold, local smoothness does not preserve sharp details so it’s not the best
candidate. Lastly, Global smoothness targets large scale reconstructions and
are usually very robust against noise, they require point clouds without
missing data which we possess and reconstruct with emphasis on preserving the
smallest details. Forthwith, we will explore reconstruction algorithms based
on the global smoothness prior and requiring only oriented normals as inputs.

####  8.2.5 Global Surface Smoothness Prior

##### Radial Basis Functions

RBFs are a well-known interpolation technique for scattered information.
Because of a collection of points with prescribed function values, RBFs
reproduce features that maintain a large degree of smoothness through a linear
combination of features that are radially symmetric. For surface
reconstruction, the [90] method builds the surface by finding a signed scalar
field defined by RBFs whose zero level set represents the surface. According
to Table 1 from [102], The aformentioned method is very weak when dealing with
noise therefore we will not develop it further.

##### Indicator Functions

These methods approach the reconstruction of the surface by estimating a soft
labeling that discriminates the inside of a solid shape from the outside.
Indicator function methods are an instance of gradient-domain techniques
[103]. Such a gradient-domain formulation results in robustness to non-uniform
sampling, noise, and outliers and missing information to some extent for
surface reconstruction. This is achieved by finding an implicit function
$\chi$ which best reflects the indicator function. In this class of
techniques, the main observation is that, assuming a point cloud with oriented
normals, $\chi$ can be calculated by making sure that the gradient of the
indicator function measured at the point cloud $P$ is aligned with normals
$N$; see Figure 8.3

Figure 8.3: Taking the gradient of the indicator function $\chi$ reveals its
connection to the point cloud normals. Poisson reconstruction [81] optimizes
for an indicator function whose gradient at $P$ is aligned to $N$.

The indicator function thus minimizes the following quadratic energy:

$\underset{\chi}{\operatorname{argmin}}\int\|\nabla\chi(\mathbf{x})-\mathcal{N}(\mathbf{x})\|_{2}^{2}d\mathbf{x}$
(8.1)

The differential equation that describes the solution to this problem is a
Poisson problem; it can be derived by applying variational calculus as
$\Updelta\chi=\nabla\mathcal{N}$. Once a solution of this equation is
discovered, a suitable surface-specific iso-value is chosen as the average (or
median) of the indicator function assessed at P. The implicit function’s
gradient being well-constrained at the data points enforces smoothness and a
quality fit for the data, and since the gradient is assigned zero away from
the point cloud, in such regions $\chi$ is smooth and well-behaved.
[104]’s strategy solves the Poisson problem by transforming it into the
frequency domain where the Fourier transforms of $\Updelta\chi$ and
$\nabla\mathcal{N}$ result in a straightforward algebraic shape to obtain the
Fourier representation of $\chi$. However, by working in the frequency domain,
a regular grid must be used to apply the FFT, thus restricting the output’s
spatial resolution. For the purpose of scaling to larger resolutions, the [81]
technique solves for $\chi$ directly in the spatial domain through a multi-
grid strategy, hierarchically resolving $\chi$ in a coarse-to-fine resolution
way. An extension of this method for streaming surface reconstruction, where
the reconstruction is done on a subset of the data at a time, has also been
proposed [105]. It represents the wavelet-based indicator function, and
calculates the base coefficients efficiently using simple local sums over an
adjusted octree.
A known problem with [81]’s strategy is that fitting directly to the $\chi$
gradient can result in data being over-smoothed[ [106], Fig. 4(a)]. To tackle
this, the [106] technique directly utilizes the point cloud’s positional
limitations in the optimization , leading to the screened Poisson problem:

$\underset{\chi}{\operatorname{argmin}}\int\|\nabla\chi(\mathbf{x})-\mathcal{N}(\mathbf{x})\|_{2}^{2}d\mathbf{x}+\lambda\sum_{\mathbf{p}_{i}\in
P}\chi^{2}\left(\mathbf{p}_{i}\right)$ (8.2)

Setting a big value for $\lambda$ ensures that the zero-crossing input of
$\chi$ will be a closer fit to the input samples $P$. While this may reduce
over-smoothing, it may also result, similarily to terpolatory methods, to
over-fitting. The [107] technique also incorporates limitations on position
and gradient, but also involves a third term, an indicator function constraint
on the Hessian:

$\displaystyle\underset{\chi}{\operatorname{argmin}}$
$\displaystyle\sum_{\mathbf{p}_{i}\in
P}\left\|\nabla\chi\left(\mathbf{p}_{i}\right)-\mathbf{n}_{i}\right\|_{2}^{2}+\lambda_{1}\sum_{\mathbf{p}\in
P}\chi^{2}\left(\mathbf{p}_{i}\right)$ (8.3)
$\displaystyle+\lambda_{2}\int\left\|H_{\chi}(\mathbf{x})\right\|_{F}^{2}d\mathbf{x}$

Which may improve surface extrapolation in missing data regions[ KH13, Fig.
6(a)]. The primary distinction between these two methods is that [106] solves
the issue through a multi-grid finite-element formulation, whereas [107] uses
finite-differences, due to the complexity of discretizing the Hessian word; in
specific, the Poisson formulation [106] is up to two orders of magnitude
quicker than [107], see[ [106], Table 1].

####  8.2.6 Comparison

In this section we compare the four most prominent global smoothness surface
reconstruction algorithms together: (1) Screened Poisson Reconstruction, (2)
Original Poisson Reconstruction, (3) Wavelet reconstruction and (4) Smooth
Signed Distance reconstruction. For all of these methods we use the
recommended parameter settings as defined by the authors. For both of the
Poisson methods, we used the publicly available code made available by the
authors on GitHub [108]. For the SSD reconstruction, we used an improvement
that uses a hash octree data structure based on Morton codes which is observed
to allow much more efficient access to leaf cells and their neighbors, also
available on GitHub [109]. Finally, for the wavelet reconstruction we modified
the authors original implementation [110] to adapt to the new specifications
of the OBJ file format.

##### Accuracy

To evaluate the accuracy of these methods, we used an assortment of real world
data scanned from laser scanners. These include: (1) The Stanford Bunny (0.2M
points), (2) the Lucy (1.0M points), (3) the David (11M points), (4) the
Awakening (10M points) and (5) the Neptune (2.4M points). We randomly divided
the points into two subsets of the same size for each dataset: input points
for the reconstruction algorithms, and validation points for measuring point-
to-reconstruction distances.

Figure 8.4: Depth 10 reconstructions of Neptune with a close up on the beard
using: original Poisson, Wavelet, SSD and Screened Poisson (left to right)
Figure 8.5: Depth 10 reconstructions of David with a close up on the eye
using: original Poisson, Wavelet, SSD and Screened Poisson (left to right)

We visualize the reconstructions of Neptune and David in Figures 8.4 & 8.5
respectively. We can observe that the Wavelet reconstruction has apparent
derivative discontinuities. Additionally, the original Poisson and SSD
reconstructions are to a certain extent over-smoothing the resulted mesh.
Conversely, the screened Poisson method offers a reconstruction that fits the
samples faithfully without causing any noise.
Moreover, Figure 4b displays quantitative outcomes across all datasets,
measured using distances from the validation points to the reconstructed
surface in the form of RMS errors.

Figure 8.6: For all models, plots of one-sided RMS errors, measured from the
evaluation points to the reconstructed surface, as a function of the
resolution depth (8, 9, and 10)

We can deduce that SSD and screened Poisson produce comparable results and
greatly surpass the other two.

##### Computational Complexity

To evaluate the computational complexity, we compared the running time and
memory usage of the four algorithms for depths 8, 9, 10 and 11 on the point
clouds of Neptune and David. All of these experiments were run on the same
machine provided in the Lab.

Model | Depth | Poisson | Wavelet | SSD | Screened
---|---|---|---|---|---
Neptune | 8 | 10 | 3 | 275 | 14
9 | 25 | 4 | 547 | 20
| 10 | 89 | 6 | 3302 | 44
| 11 | 320 | 9 | 15441 | 126
David | 8 | 41 | 9 | 492 | 48
9 | 108 | 12 | 2355 | 73
| 10 | 412 | 20 | 19158 | 182
| 11 | 1710 | 43 | 119119 | 609
Table 8.1: Comparison of runtime in seconds between the four models for depths 8,9,10 and 11 on Neptune and David point clouds Model | Depth | Poisson | Wavelet | SSD | Screened
---|---|---|---|---|---
Neptune | 8 | 113 | 4 | 238 | 133
9 | 149 | 11 | 455 | 269
| 10 | 422 | 35 | 1247 | 604
| 11 | 1387 | 118 | 3495 | 1622
David | 8 | 427 | 11 | 863 | 454
9 | 510 | 38 | 1724 | 932
| 10 | 1498 | 151 | 4895 | 2194
| 11 | 5318 | 545 | >8192 | 6188
Table 8.2: Comparison of memory usage in MB between the four models for depths
8,9,10 and 11 on Neptune and David point clouds

###### Time Complexity:

Table 8.1 compares the four reconstruction algorithms in terms of time in
seconds. We vary the octree depth from 8 to 11 and the results are shown for
both David and Neptune models. Wavelet reconstruction is quick ; its use of
compactly supported, orthogonal baseline functions allows the reconstruction
algorithm to calculate the coefficients of the implicit function through
integration; never needing an explicit linear system solution. On the other
hand, the others use non-orthogonal basis functions, thus requiring a global
system solution. For the Poisson algorithms, the multigrid solver performs a
constant number of conjugate gradient iterations at each level, giving linear
complexity in the number N of octree nodes. Increasing the depth by one
therefore quadruples the time of computation. Whereas the SSD reconstruction
utilizes conjugate gradients to solve simultaneously for all coefficients,
which has an O(N1.5) complexity, resulting in significantly slower performance
at greater resolutions.

###### Space Complexity:

The memory usage of the various reconstruction algorithms further highlights
the expense of formulating the reconstruction problem in terms of a linear
system solution. Because the Poisson and SSD reconstructions use the two-ring
neighbors to define a linear system, the scheme matrix can have as many as 125
entries per row, leading in a significant overhead to store the matrix. By
contrast, a linear system does not need to be solved by the Wavelet
reconstruction algorithm and therefore avoids the associated memory overhead.

##### Algorithm decision

It is evident to rule out SSD as a candidate since its time & memory consuming
and it’s reconstruction results are similar to the screened Poisson
reconstruction algorithm. Moreover, we can rule out the original poisson
reconstruction since the screened version surpassed it in every aspect of our
comparison. Finally, even though the wavelet reconstruction is fast and memory
efficient, its reconstruction results are visually the worst when compared to
the others. Therefore, we will solve this problem using the screened Poisson
reconstruction algorithm.

####  8.2.7 Point Cloud Size

All point clouds we receive for reconstruction are usually huge in size.
Containing around 300 Million points each. This led the screened Poisson
reconstruction algorithm to fail due to memory overload. To deal with this, we
modified the algorithms tree node indexes. In the authors’ implementation,
they use integers to keep track of the tree nodes’ indexes. This limits the
number of nodes to $2^{31}=2,147,483,648$ possible nodes. After performing
this improvement, the algorithm could finish successfully but the maximum
possible octree depth we could reconstruct at was 13. According to the poisson
paper, the number of nodes at the maximum depth d in an octree is $4^{d}$.
Which means that for a depth of 13, the number of nodes is
$4^{13}=67,108,864$. It gave good results but if we compare that number to the
number of input points (300 million), we can clearly see that there is room
for improvement. We decided to cut up the point cloud into smaller pieces that
we reconstruct independently and once we finish we stitch them all back
together. We know that if we cut the mesh into 4 pieces then a reconstruction
of depth 12 on each piece would yield the same overall resolution as
reconstructing the whole point cloud using depth 13 ($4*4^{12}=4^{13}$).
Following the same logic, if we cut the point cloud into 8 pieces and
reconstruct each one at depth 12 then it would be equaivalent to
reconstructing the original at depth 14 which was impossible to use before. Of
course, we could also reconstruct four pieces with depth 13 and that would
lead to a depth 14 overall reconstruction. Thus, there are two key parameters
to keep in mind: (1) the depth of the octree when upon reconstruction and (2)
the number of pieces we cut the original point cloud to. We can take as an
example one of the point clouds we received of the Brazil Plant which had
$370,038,992$ points. We can deduce that this number of points fits between a
depth 14 (268,435,456 nodes) and a depth 15 (1,073,741,824 nodes) octree. We
need to choose the best compromise between time and accuracy, as achieving
each incremental depth will quadruple the runtime complexity. If we choose to
achieve a reconstruction of depth 14 then we can do it in multiple ways: (1)
reconstructing 4 pieces at depth 13, (2) reconstructing 8 pieces at depth 12
or (3) reconstructing 12 pieces at depth 11 and so on.. In the next section we
will provide our implemented workflow for reconstructing any point cloud and
reaching any desired resolution no matter the machine’s hardware capabilities,
of course, at the expense of time.

####  8.2.8 Workflow

The point clouds we receive are multiple .ptx scans of the same plant,
therefore we have to merge all of the these scans and reconstruct the merged
point cloud. As we have already said, given a certain point cloud we will
provide two ways of reconstructing it.

##### Meshlab

Meshlab [111] is an open source system for processing and editing 3D
triangular meshes and point clouds. It provides a set of tools for editing,
merging, converting, cleaning, healing, inspecting, rendering, texturing and
converting meshes. In this section, we will use its merging and conversion
features. Meshlab also installs a local server which you can communicate with
through the command prompt and execute Meshlab commands without opening the
GUI version.

##### ChunkPLY

To perform the mesh cutting, we use an open source script written in C++
available on Github [108]. It is a simple script for breaking up geometry
looking at which cell of a regular grid it falls into. For points, the cell is
determined by the point’s position.

##### Approach 1

  1. 1.

Merge all .ptx point clouds into one large .ptx point cloud using Meshlab.

  2. 2.

Convert the large .ptx point cloud into a .ply point cloud using Meshlab.

  3. 3.

Reconstruct the .ply point cloud using the modified screened Poisson
reconstruction at an octree depth chosen by the user.

As we have already mentioned, for the large point clouds we are
reconstructing, the maximum octree depth our machine can handle is 13.

##### Approach 2

  1. 1.

Merge all .ptx point clouds into one large .ptx point cloud using Meshlab.

  2. 2.

Convert the large .ptx point cloud into a .ply point cloud using Meshlab.

  3. 3.

Cut .ply into chunks depending on the users input

  4. 4.

Reconstruct each chunk using the modified screened Poisson reconstruction at
an octree depth chosen by the user.

  5. 5.

Merge the reconstructed chunks into one large triangular mesh

In this approach, even though the individual octree depth limit is 13, when
they are combined they can produce even higher resolutions.

####  8.2.9 Implementation

Each approach is implemented in a separate Python script. Because these
approaches heavily rely on external application and scripts we decided to
create a containerized environment that already has all these required
applications installed.

##### Docker

###### Definition:

As per Docker’s own definition [112]: Docker is “an open source project to
pack, ship, and run any application as a lightweight container.” In layman
terms a Docker “allows you to package your application along with all of its
dependencies and configurations, making sure that the application can run on
any infrastructure with almost no configuration changes on the customer
premises”.

###### Docker Container Vs Virtual-machine:

Figure 8.7: Difference between virtual machine and docker architectures

  * •

Footprint: VMs are inherently heavyweights. They need to run a complete OS to
be able to run a packaged application. This is needed because the system calls
made by the Apps are made to the underlying Guest OS. The Guest OS sends the
system calls to the Host OS, via Hypervisor, and then relays the return value
of the call back to the App. In the case of containers, the Docker engine does
not need a Host OS. All System calls are intercepted by the Docker Engine and
are relayed back to the Host OS. Hence, the Docker containers are extremely
lightweight.

  * •

Resources: VMs should be allocated a defined amount of resources, which cannot
be shared between multiple VMs. If you share X amount of RAM to a particular
VM, then this X amount of RAM would be dedicatedly allocated to the VM. In the
case of containers though, they utilize the resources as per the need. If a
container is running a very lightweight application, it will utilize just the
right amount of RAM

  * •

Automation: It is possible to create Docker containers on the fly by writing a
couple of lines of configuration.

  * •

Instantiation: Instantiating a VM instance is a time taking process, sometimes
taking tens of minutes. But Docker containers can be started within seconds.

  * •

Collaboration: It is very easy to share your Docker images (and containers)
with other users. A Docker provides you with Registries which can store and
share your images, publicly or privately. VMs are not that easy to share.

###### Docker Architecture:

  * •

Docker Images: A Docker image is a read-only template with instructions for
creating a Docker container. For example, an image might contain an Ubuntu
operating system with an Apache web server and your web application installed.
You can build or update images from scratch or download and use images created
by others. An image may be based on or may extend, one or more of the other
images. A Docker image is described in a text file known as a Docker file,
which has a simple, well-defined syntax.

  * •

Docker Container: A Docker container is a runnable instance of a Docker image.
You can run, start, stop, move, or delete a container using the Docker API or
CLI commands. When you run a container, you can provide configuration metadata
such as networking information or environment variables. Each container is an
isolated and secure application platform but can be given access to resources
running on a different host or container, as well as persistent storages or
databases.

##### Creating Docker Image

First, we started with a pre-built docker image that runs Ubuntu and has
Meshlab and its server installed. For ChunkPLY we clone the Github Repository
where its code exists and compile it using the g++ compiler of Linux. For the
modified screened Poisson reconstruction, we forked the authors’ original
repository, made the modifications and use our own forked repository in the
docker. We also compile its code using g++. Finally, we install Python 3.7 and
all of the required libraries to run our script.

##### Python Script

To run the approaches, we create two separate scripts. We will first talk
about what is common between the two scripts. Both scripts take multiple
arguments:

  * •

data path: the path where the multiple ptx scans lie.

  * •

output path: the path where the reconstructed mesh will be created.

  * •

octree depth: the upper bound octree depth used for reconstruction (max is 13)

The difference is that the second script also takes the number of chunks
required by the user. The scripts execute both approaches in the order
described in the previous section. To execute Meshlab, ChunkPLY and the
screened Poisson reconstruction we call Linux terminal commands from the
python script using the library subprocess.
Until now the way we would run reconstructions is we launch a container from
our image that has access to the folder from the Host OS that contains the ptx
point clouds. We then run the python script we want providing our desired
arguments and destroy the container upon reconstruction completion. In the
next section, we will automate the step of creating and destroying the
container using yet another Python script.

##### Automation

Our final level of abstraction is creating a Python script that starts the
docker container that has access to the ptx point clouds and the two scripts,
runs the desired script (desired approach) and kills the container upon
completion.
This is easily achievable by using the Python library docker. It allows to
automate any docker commands in Python. Naturally, the user has to give the
arguments they wish to execute in the docker scripts to this script. This
script will then pass these arguments to the scripts inside the docker. Please
see Figure 8.8 for a visualization of the full process and Figure 8.9 for a
reconstruction results of the example layed out in Figure 8.2.

Figure 8.8: Top Level View of Surface Reconstruction Workflow Figure 8.9:
Example of a Reconstructed Mesh of the Point Cloud in Figure 8.2

###  8.3 Data Sampler

When the surface reconstruction is done and we have a fully constructed mesh,
we can feed it to the data sampler tool that we have developed for the purpose
of generating the IRIS format data set that will finally be imported into the
3D Labeling tool.
The data sampler tool is built also in Unity3D. The idea behind it is to
import a mesh and then the user can start recording what the camera is seeing
and generating rgb and depth images while going through the mesh. In other
words, it is a mimic of how the data for the 3D labeling tool is usually
collected in real environments.

####  8.3.1 Recording and Generating the RGBD Data

When the mesh is imported to the data sampler tool, the user can navigate
around it using the arrow keys and the mouse that basically changes the
positions and rotations of the main camera. Before doing so, to start
recording and capturing the RGB images from the mesh, they click on the
start/stop recording button (see Figure 8.10). When the recording is on, the
camera’s transform (position and rotation) is saved on each frame (fps can be
set by the user) in a list.
When the user clicks on the generate datasets button, a screenshot is taken on
each camera position that has been recorded. However, to capture what the
camera is seeing we had to add a target render texture on the camera with a
resolution that is set by the user (The top left values in Figure 8.10). Then,
using Unity’s ReadPixels function, everything that is read by the main screen
is projected into the texture that is finally an RGB image stored on the disk
to form the first part of the IRIS format.
In addition, for the depth images, we used Unity’s depth shader script and
applied a post processing effect on the rendered texture to obtain a depth map
which is a depth image stored in IRIS format. Note that taking the depth image
is done with the same method as of the RGB images but using another camera
that is created as a child of the main camera to preserve the main camera’s
position and rotation for the purpose of having for the same RGB image the
corresponding depth image.

Figure 8.10: Data Sampler UI Example

####  8.3.2 Generating the Camera Information

To complete the IRIS format creation, we still need the camera’s extrinsic
list that defines all the positions of the camera in the world and the
direction that is pointing at. Along with the camera’s extrinsic we also need
the intrinsic that represent the camera’s calibration and how the 3D camera
coordinates are transformed to a 2D image coordinates.
First, the camera extrinsic are the positions stored when the user is
recording. Hence, using these positions and transforming them into world space
with Unity’s transform.localToWorldMatrix function, we obtain a 4x4
transformation matrix that is added to a list which is finally JSON serialized
and stored in the “extrinsic.json" file of the IRIS format.
Second, to generate the camera’s calibration we had to calculate the Unity
camera’s focal length. Knowing the camera’s field of view, we used the
following equation to extract the focal length:

$focallength=\dfrac{resolution.height}{2*\tan(fieldofview*(\pi/360))}$ (8.4)

In addition to the focal length, we added to the intrinsic matrix the
resolution’s width and height divided by 2. Finally, we got the following
intrinsic matrix serialized into JSON and written on a file called
“intrinsic.json" in the IRIS format directory:

$\centering\quad\begin{bmatrix}focallength&0&width/2\\\
0&focallength&height/2\\\ 0&0&1\\\ \end{bmatrix}\quad\@add@centering$

Figure 8.11: Sampler Generated Data Imported in 3DLT

In summary, the generated data set from this tool is stored as an IRIS format
which later on can be imported to the 3D labeling tool (see Figure 8.11).
That, gives the user the ability to label any data set, whether it is only
coming from a large point cloud or a standard IRIS format data set.

##  Chapter 9 Snapping

###  9.1 Introduction

In the previous chapters we showed the various features that the user can
benefit from to ensure an intuitive labeling experience. However, in some
cases, the placement of the labeling elements on the mesh in the right
position and rotation can be time consuming.
As a result, we introduced a new feature that snaps the labeling element in
its convenient place if it is more or less close to it and the labeling object
has the same size as the object to be labeled.
This functionality is based on the concept of registering the labeling element
onto its correct place in the mesh. Before applying the registration
algorithm, two depth images should be sent to the server along with the tool’s
main camera intrinsic and extrinsic. We will begin by examining how the depth
images are captured and what do they represent. Then, we will present the
server side of this feature and finally we will highlight the results of this
enhancement.

###  9.2 Data Pre-Processing

The snapping is launched when the user selects a certain labeling element in
the scene and clicks on the button "S" on the keyboard. Before the snapping is
applied, the data is prepared in the Unity side by forming a message that
contains two encoded depth images and the main camera’s intrinsic and
extrinsic. This message is sent to the server through websockets to ensure the
corresponding computations and to produce a rigid transformation that is
applied on the labeling element.

####  9.2.1 Depth Camera Setup

First, a camera is added as a child of the main camera’s game object to ensure
that both have the same transformation. This camera is going to play the role
of a depth camera that takes a screenshot of what it is rendering the moment
the snapping is applied (Same concept as mentioned in Chapter 8). Moreover,
the depth property is given to this camera by enabling the
“DepthTextureMode.Depth" that generates a depth texture. To calculate the
depth map in values and encoding it into an RGBA format, we used the “Shader"
language in Unity and applied it as a post rendering effect on the camera.
This is done using Unity’s OnRenderImage and Graphics.Blit that is given the
source and destination textures along with the material that will affect the
destination texture. It is the texture to encode and send to the server.
Furthermore, in the shader calculations, the depth is received from the Depth
Texture of the camera that is already enabled. However, the depth value
returned from this texture is not linear; therefore, we used the Linear01Depth
function to set the depth value between $0$ and $1$, in the case where $1$ is
the maximum value corresponding to the far clipping plane that is set to $65$
meters in our case. Note that the far clipping plane is the farthest point
that the camera can render.
Finally, the linear depth value is encoded on $4$ channels R, G, B and A on a
scale of $[0,1]$ in the “Shader" script. Knowing that there’s $256$ color in
each channel, we multiply the depth value by $256^{i}$ (i ranging between $1$
and $4$, representing the values of R, G, B and A) while limiting its value to
256 using modulo. In addition, to enclose the values between the range $[0,1]$
we divide each one by $255$. As a result, we obtain a vector of $4$ values
(RGBA) representing the encoded depth value.

####  9.2.2 Capturing the Depth Images

To apply the “Shader" script mentioned above, we have to attach it to a
material on which the camera should render the texture to ensure the post
processing effect and generate the depth map. To differ between the labeling
element and the mesh, we assigned a culling layer for each one, then we added
a culling mask to the depth camera for each layer. As a result, the camera
captures one image that contains the labeling element and then changes its
culling mask and captures another image containing only the mesh.
The images in Unity are 2D textures where we specified the resolution to
$256\times 144$ for the purpose of decreasing the number of pixels and by that
optimizing the time complexity of the registration algorithm. Finally, to
capture the images, we used the ReadPixels function in Unity that reads the
pixels from the screen into the saved texture with the corresponding
resolution (see Figure 9.1). Then, we encode the following texture into an
array of bytes using Unity’s EncodeToPNG function. Note that, this is done
twice, once for the image that contains only the labeling element and the
other for the image that contains the mesh; however, when we encode to PNG,
the RGBA values are then transformed from the range $[0,1]$ to a range
$[0,255]$.

Figure 9.1: Depth Images Example

####  9.2.3 Generating the Camera Intrinsic and Extrinsic

As part of the data preparation, we generated the depth camera’s intrinsic and
extrinsic in the same way we did in Chapter 8 in which we formed the camera’s
extrinsic using Unity’s transform.localToWorldMatrix property that returns a
transformation matrix in the world space of the game object. On the other
hand, the intrinsic matrix was constructed after calculating the camera’s
focal length and the texture’s resolution.

####  9.2.4 Sending the Data

In order to send the data to the Python server, we created a class that
contains two byte arrays one for each image and two matrices for the camera’s
intrinsic and extrinsic. This class is serialized into a JSON message and sent
to the server through websockets.

###  9.3 Server Side

The Python server receives a total of four inputs: (1) Encoded depth image
containing the labeling object, (2) Encoded depth image containing the mesh,
(3) Intrinsics of the camera and (4) Extrinsics of the camera. In this section
we will describe how we calculate the optimal transformation matrix that
transforms the labeling object onto its correct spot on the mesh.

####  9.3.1 Extracting depth values

Decoding the received images is simply performing the reverse steps that were
used to encode them on the Unity side. First, to extract the RGBA values from
the byte array sent from Unity, we use the Python library Pillow’s Open
function. Evidently, we will get a 3-dimensional array of shape
heightxwidthx4. In other words, it is essentially a heightxwidth matrix with
each entry being a 4 element vector representing the four values red, green,
blue and alpha on a scale of [0, 255]. We divide all of the values by 255
reducing the range to [0,1]. Second, we perform the inner product of each
entry with the vector $[1,\frac{1}{256},\frac{1}{256^{2}},\frac{1}{256^{3}}]$
which will result in the z value of each pixel on a scale from 0 to 1. Third,
we multiply this matrix by $65$ (because we know the max depth that the Unity
camera can calculate is 65) to receive the actual z value in world
coordinates. Finally, we construct a $(width*height)X3$ matrix in which the
first two columns are the $(u,v)$ coordinates of each pixel on the image
starting from the top left and row by row, see Figure 9.2. The third column is
the depth(z in meters) value of each pixel in world coordinates, see Figure
9.3.

Figure 9.2: u,v image coordinate axes Figure 9.3: Resulting matrix containing
three columns, [u, v, z]

####  9.3.2 Calculating World Space Coordinates

Since we know the depth coordinate of each pixel, we can use single view
geometry to calculate each pixels’ position in world space. The projection
matrix, formed by multiplying the intrinsics by the extrinsics; see Equation
5.3, is used to transform points in world space into points in image space;
see Equation 5.4. What we require is the opposite of the latter equation, we
need to find the point’s coordinates in world space knowing both it’s
coordinates in image space and its depth in world space. By left multiplying
equation 5.4 by the inverse of P we will get the following equation:

$X=P^{-1}x$ (9.1)

We apply this equation on all of the points in the matrix we calculated in
section 9.3.1, then we will get the world coordinates of each pixel in the
original images.

####  9.3.3 Reducing Mesh Points

Since the mesh will contain a lot more pixels than the labeling object, we
should remove points that are very far from the object so as to increase the
accuracy and speed of the registration algorithm. To do this, we first
calculate the minimum and maximum coordinate of the labeling object on each
axis. That would leave us with 6 values (3 minimums and 3 maximums). Each pair
will serve as a bound on a certain axis. Because the labeling object will be
in an awkward position, the bounds we choose should not be very strict.
Therefore, we add/subtract a certain offset from the maximums/minimums.
Choosing the correct offset value for all cases is impossible, with our
testing we found that 0.15 (15 cm) yielded the best results. We then simply
remove any points in the mesh that lie outside the bounds we created on each
axis.

####  9.3.4 Registration

We have already covered registration extensively in a previous chapter. Our
needs in this problem are different from the previous one though. In this
problem there is a lot of outliers and noise. As we have previously said, the
registration algorithms that are the most robust against these two artifacts
are the stochastic registration methods. We have reviewed 4 state of the art
stochastic methods.

##### Choosing the Best Algorithm

Even though it would seem like CPPSR [63] would be the obvious choice since it
leverages the possibility of using the pixel’s colors to stregthen
registration accuracy. Unfortunately, the reconstructions usually lose color
accuracy while CAD objects retain a very accurate real world estimate of the
colors. Henceforth, we in our case colors would be a detriment rather than a
benefit. Additionally, we will not use IPDA [62] since its main focus is
registering a dense point cloud to a sparse one. However, since we are
capturing the same resolution from the same camera, then the pixels will be
uniformly distributed on both point sets and hence both would have the same
denseness. Although VBPSM [61] achieves promising results, it’s cubic time
complexity prevents it from being used in any real time application. Finally,
SVR [64] presents itself as the best candidate as it is the best compromise
between registration accuracy and computational complexity(O(mn)/where m and n
are the number of components in GX and GY respectively).

##### Modification

We have used a modified version of SVR in which we use fast Gauss Transform to
approximate the trained SVMs to a Gaussian Mixture Model instead of the one
implemented by the authors, thus reducing the computational complexity to
O(n+m).

##### Output

We provide the algorithm with the labeling object points as the source point
set and the reduced mesh points as the target point set. As for the
algorithm’s hyperparameters, according to the authors changing them will
barely affect the registration result and therefore we left the ones the
authors used in their paper. Naturally, the algorithm will output the optimal
rigid transformation matrix (containing only rotation and translation) that
transforms the labeling object onto the mesh. This transformation matrix is
sent to Unity via the same websockets connection to be applied on the labeling
object.

###  9.4 Results

On the unity side, a transformation matrix is received that defines the
translation and rotation that will be applied on the labeling element to
ensure the snapping into the correct position on the mesh. However, if we
apply the transformation on the labeling object directly it will lead to wrong
results because of the difference in the coordinate system. In other words,
the center of rotation will be the center of the labeling element and not the
center of the world. The transformation that should be applied is relative to
the world space, to fix this issue we added an empty game object on the zero
position (Unity’s world space position) and made the labeling object a child
of the created game object. Therefore, when applying the transformation on the
new center of rotation, the labeling element will move accordingly to its
parent (see Figure 9.4).

Figure 9.4: Snapping Example

##  Chapter 10 Labeling in Virtual Reality

###  10.1 Introduction

In this chapter we introduce the concept of labeling in virtual reality as an
added feature to the tool. The idea is to place the user in front of the mesh
and allow labeling using VR controllers. This feature provides an immersive
experience and exploits the 3D aspect of the tool to its maximum limits.

###  10.2 First Integration into Unity

The first objective of this integration was to install the SteamVR module and
add the OpenVR SDK to Unity. SteamVR is the software that will pair the VR
headset and the controllers to the user’s machine. Hence, the user must setup
his platform and download SteamVR as a prerequisite for the application to run
in virtual reality mode. Note that during the development of this feature we
used the HTC Vive Pro hardware package (see Figure 10.1).

Figure 10.1: HTC Vive Pro

####  10.2.1 Teleportation in VR

To start developing the VR application, we imported demo scenes from the
SteamVR asset that got us familiar with the capabilities of the virtual
reality features in Unity. One of these features is the teleportation that
allows the user to change its position in the scene by clicking the
corresponding button. It is represented by a line and a target spot on the
floor that indicates the final position of the user (see Figure 10.2). This
functionality is useful because the headset is linked using a cable which
limits the movement of the user.

Figure 10.2: Teleportation Example

####  10.2.2 Switching from 2D to VR

When the user clicks on the “VR" button in the main window of the tool, all of
the 2D user interface panels are switched off and a floor (plane) is added on
the origin of the world (it is the grid shown in Figure 10.2). However, if the
user does not have the “SteamVR" module then the virtual reality functionality
is not activated.

####  10.2.3 Basic Object Manipulations Using SteamVR

After setting up the mesh and the VR environment, we started to test simple
object creation, deletion and manipulation that are included in the SteamVR
library.

##### Simple Object Creation

This simple object creation is based on adding a cube in the middle of both
controllers when the user clicks on their trigger button (see Figure 10.3 for
the HTC VIVE controllers’ key bindings terminology). Knowing the controllers’
distance to each other in the scene, we calculated the center and added the
object in that position.

Figure 10.3: HTC VIVE Controllers

##### Grabbing Objects

SteamVR library provides also a useful functionality that could be added to
any game object so it can be grabable whenever the controller and the object
are colliding and the ‘Grab" button is clicked. The grabbed object becomes a
child of the controller’s game object and it will move relatively to the
parent game object (see Figure 10.4). This is an essential feature in the use
case of this tool because the user can now create the 3D object, grab it and
place it on the mesh to label a certain object.

Figure 10.4: Grabbed Object Example

###  10.3 Collaboration with Logitech

During the development of this feature in the tool, Logitech contacted our
supervisor at BMW Group and suggested to collaborate with them in the virtual
reality part of the tool. They were launching a new product called VR Ink
stylus pen and they were willing to integrate it in the 3D labeling tool.

####  10.3.1 Logitech’s Stylus Pen

This pen is an input device for VR that allows the creation of controlled
lines and drawing on virtual and physical surfaces. It has the same key
bindings as the normal HTC Vive controller but with an added analog tip that
could be used with the analog button. For example, it could be used to adjust
the thickness of a line when drawing (see Figure 10.5).

Figure 10.5: Logitech Stylus Pen

####  10.3.2 Integration into the 3D Labeling Tool

With the help of Logitech’s team, we managed to integrate the corresponding
game objects in our project that are responsible to enable the camera (The HTC
VIVE headset view) along with the model of both controllers (one of them is
the HTC VIVE controller and the other one is a model of the stylus as showing
in Figure 10.6). They also developed some functionalities for cube creations
that we later on upgraded to a 3D aspect that can be useful for the tool
(Section 10.4.2).
Nevertheless, the user does not have to acquire this stylus pen to be able to
use the VR option in the tool. The key bindings and the pairing mechanism is
the same as a normal HTC VIVE controller.

Figure 10.6: Stylus And HTC Models in VR

###  10.4 Added Features

In this section we are going to discuss in details the added features to
Logitech’s already implemented API that can benefit the user experience of the
labeling process in VR.

####  10.4.1 User Interface

The user has to continuously check if the labeling objects that they are
placing on the mesh are well projected to the images. Therefore, we added a
user interface that consists of a series of panels that pops up on the non-
dominant controller (see Figure 10.7). To implement this canvas, we have added
it as a child game object on the controller after aligning it in a way that is
convenient for the user (size and location).
Moreover, this canvas includes the RGB images to be labeled along with the
slider filter to go through the images, the CAD model inventory and a settings
menu to enable or disable world scale (Section 10.4.4). In addition, for the
user to enable this panel, they have to click on the "Menu Button" on the non-
dominant hand, which is also the same button to switch between menus.
Logitech already implemented a raycaster program that generates a ray from the
pen to a UI Element in the scene. Thus, it can be used to trigger the buttons
or the images from a distance without having the need to make the pen touch
the user interface elements.

Figure 10.7: VR User Interface

####  10.4.2 Labeling Objects Creation

We gave the user 3 options to create a 3D object in the world:

##### Drawing a Cuboid

For the user to draw a cuboid using the tracker, they have to choose 2 points
and draw a line, then drag the controller to create a rectangle and finally
drag again to add depth for the rectangle so it becomes a cuboid (see Figure
10.9).
The idea behind this process is to project the position of the controller on
the planes created by the first two points and their normal vectors passing by
these points. As a result of these 2 projections, we obtain 2 points that will
finish drawing the rectangle as shown in the second photo in Figure 10.9.
Moreover, adding the depth was based on the same idea of projecting to a plane
but we had to do it twice. For example, in Figure 10.8 we have the rectangle
already drawn and we want to add the depth based on the trackers position
which is the point E. First, we project E to the plane formed by A and the
vector AB, then the result of this projection is then projected to the plane
formed by B and the vector BC. To complete the drawing, this process is done 4
times for the remaining planes and points.
To create the labeling object we used the first 3 points calculated using the
projection to the plane and a fourth point that represents the depth of the
cuboid. Furthermore, using the vectors composed by these 4 points, we managed
to calculate the position, rotation and scale of the cuboid.
In conclusion, this method enhances the user experience by giving the user the
opportunity to draw a custom cuboid that suits the object that they want to
label in the mesh.

Figure 10.8: Plane Projection to Add Depth Example Figure 10.9: Drawing a
Cuboid Example

##### Convex Hull to Cuboid

In this method, the user presses a button on the controller and starts
painting a line as if they were scratching on the mesh the object to be
labeled. As a result, they obtain the minimum box that envelopes the created
line (see Figure 10.10).
This feature is based on the concept of Convex Hull which is an approach in
mathematics used to envelope a set of points in the Euclidean space in the
smallest convex shape (see Figure 10.11). To implement it in Unity we used
[113] that already has implemented the method to produce a convex hull game
object from an array of points.
For the user experience to be intuitive we decided to let the user draw a line
and not place points in the scene. We used the Line Renderer Unity class to
show the line on the screen yet extract the points from it and assign it to
the convex hull algorithm.
To transform the convex shape obtained from the previous step to a cuboid, we
decided to take advantage of Unity’s box collider properties. When this
collider is assigned to a game object, it automatically creates the minimum
bounding box around it. Therefore, the next step was to add the box collider
on the convex hull object and retrieve its vertices that will help produce the
cuboid using the “Mesh" class in unity.
Finally, after creating the box and rendering it to the scene (using the Mesh
Renderer component), we made sure that it has the same transformation as the
box collider that encapsulates the convex hull. Then, we delete the convex
hull game object and keep the box as a labeling element.

Figure 10.10: Convex Hull to Cuboid Example Figure 10.11: Convex Hull Example

##### CAD Model Importer

This feature is based on the same one that is used in the 2D mode of the tool.
However, we added a CAD model inventory panel in the user interface part of
this mode to give the user the option to load a CAD object into the
environment when labeling in VR (see Figure 10.12).

Figure 10.12: Cad Objects in VR

####  10.4.3 Objects Manipulation

After creating the labeling element, the user wants to manipulate it: change
its position, copy, delete and scale. As already mentioned, Logitech uses the
same grabbing mechanism as the one of SteamVR which is responsible for
changing the position and rotation of the labeling element in relative to the
movement of the dominant controller.
To copy the labeling element, we duplicate the object that the controller is
colliding with by instantiating the collided game object. In addition, to
delete a labeling element, the user must be pointing or colliding with the
object and press the Trigger button. Note that when deleting the object it
does not mean to only destroy the game object but also we had to remove it
from the list that contains all the other labeling objects.
Furthermore, we added the feature of grabbing the object from afar using a
raycaster program that is issued from the dominant hand controller in case it
is pointing at a labeling element. This implementation caused some issues when
trying to use it with the user interface raycaster program (see Section
10.4.1). Hence, to solve that problem, we managed to synchronize both of the
raycaster programs using boolean variables and giving the priority for the
user interface raycaster program in case there’s an object behind the panel.
Finally, the user has the ability scale the labeling element if they are
colliding with it and pressing on the non dominant hand trigger button. The
object will be scaled along the distance between the two controllers. In other
words, the idea behind this type of scaling is to transform the controllers
game object along with the labeling object to the camera’s coordinate system.
Then, we calculate the difference (Vector) between both of the controllers and
transform it to the object’s coordinate system. This allows the user to scale
the object on its axis regardless of its rotation relative to the user’s view.
In addition, to be able to determine the axis on which the object has to
scale, we calculate the dominant axis; in other terms, we check the position
of the controllers and see if it is dominant on the x, y or z axis. For
example: if the user’s controllers are on top of each other than the dominant
axis is the y axis and the object should be scaled on that axis while taking
into account the distance between the controllers.

Figure 10.13: World Scale Setting in UI

####  10.4.4 World Scale

The last functionality that we implemented in VR was the ability to scale the
entire scene/world. This came as a solution for an issue that we faced when we
were trying to label meshes that are too high or too large for the user to
physically reach.
This solution consists of toggling the World Scale setting in the user
interface panel ( 10.13), which adds an empty game object that parents all the
labeling objects available along with the mesh. Therefore, when the Grab
Button is triggered on the controllers, the World game object is transformed
along them. Then, the mesh and the labeling objects are transformed
accordingly. Note that the scaling in this case is uniform and it differs from
the scaling that was discussed in Section 10.4.3. In addition, when the world
scale option is enabled, we made sure that the copy and object creation is
done according to the world game object. In other words, these objects are
added directly as children of the world object. Nevertheless, this will not
disrupt the labeling process, because when the world scale option is off or
the user turns off VR mode and gets back to the 2D mode, all of the features
of that option are reverted and the labeling objects will preserve their
alignment with respect to the mesh.

##  Chapter 11 Experimental Results

In the final phase of this project, we conducted a series of experiments to
test the run time efficiency of the tool, compared to the other state of the
art labeling tools presented in Chapter 2.
These tests were performed on Windows 10 Home Edition running on a personal
computer hosting an NVIDIA GTX 1060 GPU, 16GB of RAM and a 6 cores 2.2 GHz i7
CPU.
The experiments were performed in two different ways. First, we compare the
labeling tools (see Chapter 2) on three distinct data sets: (1) shots taken by
a robotic arm of a box containing door handles (92 images), (2) shots of a
kitchen (98 images) and (3) images of pallets, trollies and boxes in a factory
(184 images). Second, we compared the methods based on the number of objects
to be labeled in a data set. Note that the timer starts when the labeling
process begins and stops when the annotations are exported.

###  11.1 Experiment 1

The first chosen labeling tool is an offline application called LabelImg [6].
It achieves 2D labeling by drawing a rectangle on each imported image and
generates the annotations in XML format. As shown in Figure 11.1, the data set
that contains 92 images took more time to label than the one with 98 images.
This is correlated with the position of the object in the images when drawing
the bounding box around it (object on the image’s edges or behind other
objects). Also, when the number of images increased to 184, the time to finish
the labeling almost doubled from 12.25 to 22.08 minutes.
The second tool that was chosen is the LabelBox [7] web application on which
the 2D labeling process is done in the same fashion as LabelImg but online
rather than on premise. Figure 11.1 displays how this method struggles in run
time comparing to the previously mentioned tool. It is caused by the delays in
the server’s response time when the annotations are drawn on the image.
Therefore, this method is not reliable because its performance depends on the
user’s activity and the network’s congestion when annotating the images.
The third and final tool that was mentioned in Chapter 2 is the Semi-Auto
Annotation Tool [8] that basically enhances the idea of the previous 2D
labeling tools. It adds the ability to detect the object before drawing the 2D
bounding box on it accordingly. However, as shown in Figure 11.1, this method
only shows its best performance on the kitchen data set because it is already
trained to detect a fridge which is present in this data set. As a result, the
fridge in each image is detected and annotated directly by a bounding box,
which made the labeling faster (3.26 minutes). However, the other two data
sets do not hold any object that is present in the pre-trained model of this
tool, hence resolving to approximately the same run-time as the previous tools
by drawing the rectangle on the objects manually for each image.

Figure 11.1: Comparison on Different Data Sets

###  11.2 Experiment 2

This experiment is performed on the robot arm data set in which we compared
the 3DLT with the LabelImg tool. As you can see in Figure 11.2, the same data
set is imported 3 times, where we increased the number of objects to be
labeled in an image at each distinct import. The 2D labeling tool’s time to
label showed an exponential increase in time when expanding the number of
objects because the user has to draw a 2D bounding box on each one in every
image.

Figure 11.2: Comparison on Different Number of Objects

###  11.3 Discussion

When comparing any labeling tool mentioned in Chapter 2 to our tool, we notice
that in the first experiment, the time taken to label any of the three
different data sets in the 3DLT is the same constant time for each data set,
and is highly faster than any of the others (see Figure 11.1) in each of the
tests. It is mainly because the act of placing one object on the mesh is not
affected by the number of images in the data set. In contrast, the run time of
the other tools depends on the number of images because the user annotates
each image to generate the ground truth labels.
In the second experiment, the act of placing multiple objects in our 3D
labeling tool and generating the annotations is almost 34 times faster than a
2D annotation software (see Figure 11.2). As a result, this shows how time
consuming the 2D labeling process is, and how the 3D Labeling tool that we
developed is much more efficient for any data set or any type of objects to be
labeled.

##  Chapter 12 Conclusion

In this report we introduced a novel labeling tool, the 3D Labeling Tool
(3DLT), that greatly reduces time spent on preparing training data for object
detection machine learning models. The tool’s user interface is easy to use
and intuitive. It is a cross platform tool that can run on Windows, MacOS and
Linux that has a client-server architecture with a Unity Client and a Python
server.
We used the recorded RGBD images in ORB-SLAM to compute the camera trajectory
and in Open3D to extract a 3D triangular mesh. We also defined a special data
format to standardize our data preparation process, the IRIS format. Moreover,
we showed how any raw point cloud can be labeled using 3DLT. We compared many
state of the art surface reconstruction techniques and selected the Screened
Poisson Reconstruction. We surpassed hardware limitations set on
reconstruction resolution by creating a workflow that splits the point cloud
into multiple pieces, reconstructs each piece separately and merges them all
back together. We containerized the aforementioned reconstruction workflow in
Docker to make it portable and devoid of requirements. The reconstructed mesh
can then be imported into a Unity application that we developed, Surface
Sampler (SS). This application allows the user to sample data from the mesh by
navigating around it and taking RGBD images. The collected data is exported
into the IRIS format and can therefore be loaded in 3DLT.
To calculate the 2D bounding rectangle, we projected the 3D labeling object to
its equivalent position on the 2D images using the camera’s projection
matrices. We then used Python to calculate the smallest possible axis-aligned
bounding rectangle that contains the projected labeling object. In the cases
where a certain part of the labeling object was blocked by another, we
carefully selected the unsupervised outlier detection algorithm, rPCA, to
allow for the computation of smarter bounding rectangles. This algorithm has
linear time complexity allowing it to preserve the tool’s “real-time"
property.
Since manually defining the position of a labeling object in 3D is non
trivial, we simplified the process by allowing the user to select
corresponding points on the labeling object and the mesh. Then the tool
calculates the optimal transformation parameters that map the former point set
to the latter. We compared and categorized many nonrigid registration
algorithms, ultimately selecting TPS-RPM. Additionally, we parallelized it to
perfect correspondence calculation and restrict its transformation parameters
to 9 degrees of freedom.
In the cases where the user knew the size of the object to be labeled, we
introduced two ways to simplify the process. First, we gave the user the
ability to select the labeling object’s corresponding points on the 2D image
instead of the mesh. We do this by reducing the computation of the desired
labeling object position to a system of non linear equations. We solve it by
using the DOG_BOX method’s output as a starting estimate to the Newton-Raphson
method. Allowing the user to label using the images broadens the tools
capabilities and removes the requirement of a mesh in the input data. Second,
we implemented a feature that allows the user to snap the labeling object onto
the desired object as long as it is relatively close to it. We use Unity’s
shader program to apply post-processing effects on the camera’s renders in
order to retrieve their depth map as a 2D texture and decrease the frequency
of outliers. The rendered texture is encoded and sent as point sets to the
Python server. After that, we use Support Vector Registration to find the
optimal rigid registration between these point sets.
Moreover, we introduced Virtual Reality as a practical add-on to the 3D
labeling tool. It allows the user to label any importable data set in VR using
the appropriate controllers with intuitive mechanisms for creating and
manipulating labeling elements using Convex Hulls and simple geometry
concepts.
Finally, we performed a series of experiments to compare our tool against
current state of the art methods. The experiments were performed in order to
highlight how tedious it is to label thousands of images by drawing 2D
bounding boxes. The performance of the tools was benchmarked based on both the
number of images in each data set and the number of objects to be labeled in a
single data set. The 3D labeling tool excelled in all experiments displaying
superior results compared to the 2D labeling tools.
Even though the tool can be built on the most popular operating systems, we
think developing a WebGL version and abstracting all heavy computation to the
server level is the next logical step. Even though this is possible in Unity,
we need to redesign the architecture of the tool to handle importing data from
the user’s machine onto the WebGL application in an efficient manner.
Additionally, another area of possible improvement is taking cues from Anno-
Mage and allowing the tool to predict bounding boxes for pre-trained object
classes. Contrastingly to Anno-Mage, our tool would predict 3D bounding cubes
instead of 2D rectangles. Therefore we cannot use the established RetinaNet as
a suggestion engine. However, PointNet [114] has recently revolutionized deep
learning on point sets for 3D classification and we think it is worth
exploring as a potential suggestion engine.

## References

  * [1] Yixin Chen and James Z. Wang  “Image Categorization by Learning and Reasoning with Regions”  In _J. Mach. Learn. Res._ 5 JMLR.org, 2004, pp. 913–939
  * [2] J.. Wang, Jia Li and G. Wiederhold  “SIMPLIcity: semantics-sensitive integrated matching for picture libraries”  In _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 23.9, 2001, pp. 947–963
  * [3] Gabriela Csurka et al.  “Visual categorization with bags of keypoints”  In _Work Stat Learn Comput Vision, ECCV_ Vol. 1, 2004
  * [4] Collins, Wright and Greenway  “The Sowerby Image Database”  In _Image Processing And Its Applications, 1999. Seventh International Conference on (Conf. Publ. No. 465)_ 1, 1999, pp. 306–310 vol.1
  * [5] Kobus Barnard et al.  “Evaluation of Localized Semantics: Data, Methodology, and Experiments”  In _International Journal of Computer Vision_ 77, 2008, pp. 199–217
  * [6] tzutalin  “LabelImg”  URL: https://github.com/tzutalin/labelImg
  * [7] labelbox  “Labelbox”  URL: https://github.com/Labelbox/Labelbox
  * [8] virajmavani  “semi-auto-image-annotation-tool”  URL: https://github.com/%5C%5Cvirajmavani/semi-auto-image-annotation-tool
  * [9] Tsung-Yi Lin et al.  “Microsoft COCO: Common Objects in Context”  In _CoRR_ abs/1405.0312, 2014  arXiv:1405.0312
  * [10] Mark Everingham et al.  “The Pascal Visual Object Classes (VOC) challenge”  In _International Journal of Computer Vision_ 88, 2010, pp. 303–338
  * [11] Bryan C., Antonio Torralba, Kevin Murphy and William T.  “LabelMe: A Database and Web-Based Tool for Image Annotation”  In _International Journal of Computer Vision_ 77, 2008
  * [12] IntelRealSense  “librealsense”  URL: https://github.com/IntelRealSense/librealsense/tree/master/wrappers/python
  * [13] raulmur  “ORB_SLAM${2}$”  URL: https://github.com/raulmur/ORB%5C_SLAM2
  * [14] open3d  “Reconstruction System”  URL: http://www.open3d.org/docs/release/tutorial/ReconstructionSystem/index.html
  * [15] Keijiro Takahashi  “Pcx”  In _GitHub Repositry_ URL: https://github.com/keijiro/Pcx
  * [16] HiddenMonk  “Unity3DRuntimeTransformGizmo”  URL: https://github.com/HiddenMonk/Unity3DRuntimeTransformGizmo
  * [17] judah  “HSVColorPickerUnity”  URL: https://github.com/judah4/HSV-Color%5C-Picker%5C-Unity/tree/master/Assets/HSVPicker
  * [18] J. Quinlan  “C4.5: Programs for Machine Learning”  San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1993
  * [19] Bernhard Scholkopf and Alexander J. Smola  “Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond”  Cambridge, MA, USA: MIT Press, 2001
  * [20] Kishan Mehrotra, Chilukuri K. Mohan and Sanjay Ranka  “Elements of Artificial Neural Networks”  Cambridge, MA, USA: MIT Press, 1997
  * [21] Mary M. Moya and Don R. Hush  “Network Constraints and Multi-objective Optimization for One-class Classification”  In _Neural Netw._ 9.3 Oxford, UK, UK: Elsevier Science Ltd., 1996, pp. 463–474
  * [22] Bernhard Scholkopf et al.  “Estimating the Support of a High-Dimensional Distribution”  In _Neural Comput._ 13.7 Cambridge, MA, USA: MIT Press, 2001, pp. 1443–1471
  * [23] Simon Hawkins, Hongxing He, Graham J. Williams and Rohan A. Baxter  “Outlier Detection Using Replicator Neural Networks”  In _Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery_ , DaWaK 2000  London, UK, UK: Springer-Verlag, 2002, pp. 170–180
  * [24] Bruce G. Lindsay  “Mixture Models: Theory, Geometry and Applications”  In _NSF-CBMS Regional Conference Series in Probability and Statistics_ 5 Institute of Mathematical Statistics, 1995, pp. i–163