This thesis work deals with the most actual topic in Computer Vision field which is scene understanding and this using matching of 3D feature point images. The objective is to make use of Saab’s latest breakthrough in extraction of 3D feature points, to identify the best alignment of at least two 3D feature point images. The thesis gives a theoretical overview of the latest algorithms used for feature detection, description and matching. The work continues with a brief description of the simultaneous localization and mapping (SLAM) technique, ending with a case study on evaluation of the newly developed software solution for SLAM, called slam6d. Slam6d is a tool that registers point clouds into a common coordinate system. It does an automatic high-accurate registration of the laser scans. In the case study the use of slam6d is extended in registering 3D feature point images extracted from a stereo camera and the results of registration are analyzed. In the case study we start with registration of one single 3D feature point image captured from stationary image sensor continuing with registration of multiple images following a trail. Finally the conclusion from the case study results is that slam6d can register non-laser scan extracted feature point images with high-accuracy in case of single image but it introduces some overlapping results in the case of multiple images following a trail.

This thesis addresses the problem of registering one point set with respect to another. This problem arises in the context of the use of CMM/Scanners to inspect objects especially with freeform surfaces. The tolerance verification process now requires the comparison of measured points with the nominal geometry. This entails placement of the measured point set in the same reference frame as the nominal model. This problem is referred to as the registration or localization problem. In the most general form the tolerance verification task involves registering multiple point sets corresponding to multi-step scan of an object with respect to the nominal CAD model. This problem is addressed in three phases. This thesis presents a novel approach to automated inspection by matching point sets based on the Iterative Closest Point (ICP) algorithm. The Modified ICP (MICP) algorithm presented in the thesis improves upon the existing methods through the use of a localized region based triangulation technique to obtain correspondences for all the inspection points and achieves dramatic reduction in computational effort. The use of point sets to represent the nominal surface and shapes enables handling different systems and formats. Next, the thesis addresses the important problem of establishing registration between point sets in different reference frames when the initial relative pose between them is significantly large. A novel initial pose invariant methodology has been developed. Finally, the above approach is extended to registration of multiview inspection data sets based on acquisition of transformation information of each inspection view using the virtual gauging concept. This thesis describes implementation to address each of these problems in the area of automated registration and verification leading towards automatic inspection.

Maintaining an inventory of transportation infrastructure assets is vital for effective management and maintenance. LiDAR (Light Detection and Ranging) can be a useful resource for this purpose by collecting detailed 3D information. Mobile Mapping Systems (MMS) refers to collecting geospatial data by mounting laser scanners on top of a moving vehicle, e.g. a car. The LiDAR collects XYZ-coordinates of the environment by emitting laser pulses toward the surveyed objects. This enables an effective way to store and survey built-up urban areas that otherwise would need an on-site presence. WSP uses Mobile Mapping (MM) to capture and visualize infrastructure, primarily for inventory purposes. Currently, the point cloud registration in the MM-process is labor-intensive, so the company is looking to automate it. This thesis aims to investigate methods to automate the process of point cloud registration that eliminates manual labor. The proposed method was evaluated with regards to its accuracy, advantages and disadvantages. The study area of the thesis was a light rail facility with surrounding residential buildings and vegetation. The proposed method was implemented in Python and utilizes open source libraries. The registration uses Fast Global Registration (FGR) for coarse alignment with Iterative Closest Point (ICP) for fine refinement. The FGR algorithm finds a rigid transformation between a pair of point clouds by establishing a feature correspondence set between the point clouds. The algorithm utilizes Fast Point Feature Histograms (FPFH) that simplifies the description of 3D point relationships as the feature descriptors. The object used for registration is the general area around catenary poles. The segments between poles is adjusted by linear interpolation of the obtained transformation matrices from the registration. The results of this thesis show that automatic point cloud registration is feasible. However, while the proposed method improves registration over raw data, it does not fully replace WSP's current procedure.  The advantages of the proposed method are that it does not require classified data and is open source. The main source of error in the method is the presence of vegetation, and an experiment was conducted to support this hypothesis. The experiment shows that dense vegetation skews the registration, and generates an incorrect transformation matrix. Furthermore, the proposed method is only semi-automated, as it still needs manual post-processing. Accuracy assessment showed that removing outlier, presumably caused by vegetation, improved the planar offsets. Further studies to improve the result could utilize machine learning which could identify and extract poles for registration or remove surrounding vegetation. / Att upprätthålla inventering av tillgångar av transportinfrastruktur är avgörande för effektiv förvaltning och underhåll samt för att tillhandahålla korrekta data och underlätta beslutsfattande. LiDAR-data (Light Detection and Ranging) kan vara ett användbart verktyg för detta ändamål genom att samla in detaljerad 3D-information. Mobile Mapping Systems (MMS) refererar till att samla geospatial data genom att montera laserskannrar ovanpå taket på ett rörligt fordon, exempelvis en bil. LiDAR samlar XYZ-koordinater av kringliggande miljö genom att sända ut laserpulser mot de undersökta objekten. Detta möjliggör ett effektivt sätt att förvara och undersöka bebyggda stadsmiljöer som annars skulle behöva fysisk närvaro. WSP använder Mobile Mapping (MM) för att samla och visualisera infrastruktur, främst för inventeringsändamål. För närvarande är punktmolnregistreringen i MM-processen manuellt arbetskrävande, och därför vill WSP se en automatisering av processen. Detta examensarbete syftar till att undersöka metoder för att automatisera processen för registrering av punktmoln som eliminerar manuellt arbete. Den utvecklade metoden kommer att utvärderas med avseende på dess noggrannhet, för- och nackdelar. Arbetets studieområde är en järnvägsanläggninng med omgivande av bostadshus och vegetation. Den föreslagna metoden implementerades i Python och använder sig av open source-bibliotek. Registeringen tillämpar Fast Global Registration (FGR) för grov justering av punktmolnen, och Iterative Closest Point (ICP) för finjustering. FGR-algoritmen hittar en stel transformation mellan två punktmoln genom att etablera ett set av korresponderande attribut. Algoritmen använder Fast Point Feature Histograms (FPFH) som förenklar euklidiska förhållanden till attributbaserade förhållanden. Objekt som används för registrering är det generella området kring kontaktledningsstolpar. Segmenten mellan stolpar justeras genom linjär interpolation av de erhållna transformationsmatriserna från registreringen. Resultaten av detta arbete visar att automatisk registrering av punktmoln är genomförbar, och att metoden förbättrar registreringen jämfört med den råa datan. Den är dock inte tillräckligt bra för att helt ersätta den nuvarande proceduren som används av WSP. Fördelarna med den föreslagna metoden är att den inte kräver klassificerad data och är open source. Den huvudsakliga felkällan i metoden är förekomsten av vegetation, och ett experiment utfördes för att stödja denna hypotes. Experimentet visar att tät vegetation snedvrider registreringen och genererar en felaktig transformationsmatris. Vidare, är den föreslagna metoden endast semi-automatiserad, eftersom den fortfarande kräver manuell efterbearbetning. Noggrannhetsbedömningn visade att borttagningen av avvikande värden, förmodligen orsakade av vegetation, förbättrade den plana förskjutningen. Vidare studier för att ge ett mer tillfredsställande resultatet kan möjligen vara att använda maskininlärning för att identifiera och extrahera stolpar för matching, samtidigt som växtligheten kan elimineras.

Modern 3D printing technology is becoming a more viable option for use in industrial manufacturing. As the speed and precision of rapid prototyping technology improves, so too must the 3D scanning and verification technology. Current 3D scanning technology (such as CT Scanners) produce the resolution needed for micron precision inspection. However, the method lacks in speed. Some scans can be multiple gigabytes in size taking several minutes to acquire and process. Especially in high volume manufacturing of 3D printed parts, such delays prohibit the widespread adaptation of 3D scanning technology for quality control. The limiting factors of current technology boil down to computational and processing power along with available sensor resolution and operational frequency. Realizing a 3D scanning system that produces micron precision results within a single minute promises to revolutionize the quality control industry. The specific 3D scanning method considered in this thesis utilizes a line profile triangulation sensor with high operational frequency, and a high-precision mechanical actuation apparatus for controlling the scan. By syncing the operational frequency of the sensor to the actuation velocity of the apparatus, a 3D point cloud is rapidly acquired. Processing of the data is then performed using MATLAB on contemporary computing hardware, which includes proper point cloud formatting and implementation of the Iterative Closest Point (ICP) algorithm for point cloud stitching. Theoretical and physical experiments are performed to demonstrate the validity of the method. The prototyped system is shown to produce multiple loosely-registered micron precision point clouds of a 3D printed object that are then stitched together to form a full point cloud representative of the original part. This prototype produces micron precision results in approximately 130 seconds, but the experiments illuminate upon the additional investments by which this time could be further reduced to approach the revolutionizing one-minute milestone.

In wireless networks, reliable communication is a challenging issue due to many attenuation factors such as receiver noise, channel fading, interference and asynchronous delays. Lattice coding and decoding provide efficient solutions to many problems in wireless communications and multiuser information theory. The capability in achieving the fundamental limits, together with simple and efficient transmitter and receiver structures, make the lattice strategy a promising approach. This work deals with problems of lattice detection over fading channels and time asynchronism over the lattice-based compute-and-forward protocol. In multiple-input multiple-output (MIMO) systems, the use of lattice reduction significantly improves the performance of approximate detection techniques. In the first part of this thesis, by taking advantage of the temporal correlation of a Rayleigh fading channel, low complexity lattice reduction methods are investigated. We show that updating the reduced lattice basis adaptively with a careful use of previous channel realizations yields a significant saving in complexity with a minimal degradation in performance. Considering high data rate MIMO systems, we then investigate soft-output detection methods. Using the list sphere decoder (LSD) algorithm, an adaptive method is proposed to reduce the complexity of generating the list for evaluating the log-likelihood ratio (LLR) values. In the second part, by applying the lattice coding and decoding schemes over asynchronous networks, we study the impact of asynchronism on the compute-and-forward strategy. While the key idea in compute-and-forward is to decode a linear synchronous combination of transmitted codewords, the distributed relays receive random asynchronous versions of the combinations. Assuming different asynchronous models, we design the receiver structure prior to the decoder of compute-and-forward so that the achievable rates are maximized at any signal-to-noise-ratio (SNR). Finally, we consider symbol-asynchronous X networks with single antenna nodes over time-invariant channels. We exploit the asynchronism among the received signals in order to design the interference alignment scheme. It is shown that the asynchronism provides correlated channel variations which are proved to be sufficient to implement the vector interference alignment over the constant X network.

In wireless networks, reliable communication is a challenging issue due to many attenuation factors such as receiver noise, channel fading, interference and asynchronous delays. Lattice coding and decoding provide efficient solutions to many problems in wireless communications and multiuser information theory. The capability in achieving the fundamental limits, together with simple and efficient transmitter and receiver structures, make the lattice strategy a promising approach. This work deals with problems of lattice detection over fading channels and time asynchronism over the lattice-based compute-and-forward protocol. In multiple-input multiple-output (MIMO) systems, the use of lattice reduction significantly improves the performance of approximate detection techniques. In the first part of this thesis, by taking advantage of the temporal correlation of a Rayleigh fading channel, low complexity lattice reduction methods are investigated. We show that updating the reduced lattice basis adaptively with a careful use of previous channel realizations yields a significant saving in complexity with a minimal degradation in performance. Considering high data rate MIMO systems, we then investigate soft-output detection methods. Using the list sphere decoder (LSD) algorithm, an adaptive method is proposed to reduce the complexity of generating the list for evaluating the log-likelihood ratio (LLR) values. In the second part, by applying the lattice coding and decoding schemes over asynchronous networks, we study the impact of asynchronism on the compute-and-forward strategy. While the key idea in compute-and-forward is to decode a linear synchronous combination of transmitted codewords, the distributed relays receive random asynchronous versions of the combinations. Assuming different asynchronous models, we design the receiver structure prior to the decoder of compute-and-forward so that the achievable rates are maximized at any signal-to-noise-ratio (SNR). Finally, we consider symbol-asynchronous X networks with single antenna nodes over time-invariant channels. We exploit the asynchronism among the received signals in order to design the interference alignment scheme. It is shown that the asynchronism provides correlated channel variations which are proved to be sufficient to implement the vector interference alignment over the constant X network.

In this dissertation, we investigate a number of geometric problems in different settings. We present lower bounds and approximation algorithms for geometric problems in sequential and distributed settings. For the sequential setting, we prove the first hardness of approximation results for the following problems: \begin{itemize} \item Red-Blue Geometric Set Cover is APX-hard when the objects are axis-aligned rectangles. \item Red-Blue Geometric Set Cover cannot be approximated to within $2^{\log^{1-1/{(\log\log m)^c}}m}$ in polynomial time for any constant $c < 1/2$, unless $P=NP$, when the given objects are $m$ triangles or convex objects. This shows that Red-Blue Geometric Set Cover is a harder problem than Geometric Set Cover for some class of objects. \item Boxes Class Cover is APX-hard. \end{itemize} We also define MaxRM-3SAT, a restricted version of Max3SAT, and we prove that this problem is APX-hard. This problem might be interesting in its own right.\\ In the distributed setting, we define a new model, the fixed-link model, where each processor has a position on the plane and processors can communicate to each other if and only if there is an edge between them. We motivate the model and study a number of geometric problems in this model. We prove lower bounds on the communication complexity of the problems in the fixed-link model and present approximation algorithms for them. We prove lower bounds on the number of expected bits required for any randomized algorithm in the fixed-link model with $n$ nodes to solve the following problems, when the communication is in the asynchronous KT1 model: \begin{itemize} \item $\Omega(n^2/\log n)$ expected bits of communication are required for solving Diameter, Convex Hull, or Closest Pair, even if the graph has only a linear number of edges. \item $\Omega( min\{n^2,1/\epsilon\})$ expected bits of communications are required for approximating Diameter within a $1-\epsilon$ factor of optimal, even if the graph is planar. \item $\Omega(n^2)$ bits of communications is required for approximating Closest Pair in a graph on an $[n^c] \times [n^c]$ grid, for any constant $c>1+1/(2\lg n)$, within $\frac{n^{c-1/2}}{4}-\epsilon$ factor of optimal, even if the graph is planar. \end{itemize} We also present approximation algorithms in geometric communication networks with $n$ nodes, when the communication is in the asynchronous CONGEST KT1 model: \begin{itemize} \item An $\epsilon$-kernel, and consequently $(1-\epsilon)$-\diamapprox~ and \ep -Approximate Hull with $O(\frac{n}{\sqrt{\epsilon}})$ messages plus the costs of constructing a spanning tree. \item An $\frac{n^c}{\sqrt{\frac{k}{2}}}$-Approximate Closest Pair on an $[n^c] \times [n^c]$ grid , for a constant $c>1/2$, plus the cost of computing a spanning tree, for any $k\leq {n-1}$. \end{itemize} We also define a new version of the two-party communication problem, Path Computation, where two parties communicate through a path. We prove a lower bound on the communication complexity of this problem. / Graduate

A key component for automated driving is 360◦ environment detection. The recognition capabilities of mod- ern sensors are always limited to their direct field of view. In urban areas a lot of objects occlude important areas of in- terest. The information captured by another sensor from an- other perspective could solve such occluded situations. Fur- thermore, the capabilities to detect and classify various ob- jects in the surrounding can be improved by taking multiple views into account. In order to combine the data of two sensors into one co- ordinate system, a rigid transformation matrix has to be de- rived. The accuracy of modern e.g. satellite based relative pose estimation systems is not sufficient to guarantee a suit- able alignment. Therefore, a registration based approach is used in this work which aligns the captured environment data of two sensors from different positions. Thus their relative pose estimation obtained by traditional methods is improved and the data can be fused. To support this we present an approach which utilizes the uncertainty information of modern tracking systems to de- termine the possible field of view of the other sensor. Fur- thermore, it is estimated which parts of the captured data is directly visible to both, taking occlusion and shadowing ef- fects into account. Afterwards a registration method, based on the iterative closest point (ICP) algorithm, is applied to that data in order to get an accurate alignment. The contribution of the presented approch to the achiev- able accuracy is shown with the help of ground truth data from a LiDAR simulation within a 3-D crossroad model. Re- sults show that a two dimensional position and heading esti- mation is sufficient to initialize a successful 3-D registration process. Furthermore it is shown which initial spatial align- ment is necessary to obtain suitable registration results.

In this thesis, the expression variation problem in two-dimensional (2D) and three-dimensional (3D) face recognition is tackled. While discriminant analysis (DA) methods are effective solutions for recognizing expression-variant 2D face images, they are not directly applicable when only a single sample image per subject is available. This problem is addressed in this thesis by introducing expression subspaces which can be used for synthesizing new expression images from subjects with only one sample image. It is proposed that by augmenting a generic training set with the gallery and their synthesized new expression images, and then training DA methods using this new set, the face recognition performance can be significantly improved. An important advantage of the proposed method is its simplicity; the expression of an image is transformed simply by projecting it into another subspace. The above proposed solution can also be used in general pattern recognition applications. The above method can also be used in 3D face recognition where expression variation is a more serious issue. However, DA methods cannot be readily applied to 3D faces because of the lack of a proper alignment method for 3D faces. To solve this issue, a method is proposed for sampling the points of the face that correspond to the same facial features across all faces, denoted as the closest-normal points (CNPs). It is shown that the performance of the linear discriminant analysis (LDA) method, applied to such an aligned representation of 3D faces, is significantly better than the performance of the state-of-the-art methods which, rely on one-by-one registration of the probe faces to every gallery face. Furthermore, as an important finding, it is shown that the surface normal vectors of the face provide a higher level of discriminatory information rather than the coordinates of the points. In addition, the expression subspace approach is used for the recognition of 3D faces from single sample. By constructing expression subspaces from the surface normal vectors at the CNPs, the surface normal vectors of a 3D face with single sample can be synthesized under other expressions. As a result, by improving the estimation of the within-class scatter matrix using the synthesized samples, a significant improvement in the recognition performance is achieved.

In this thesis, the expression variation problem in two-dimensional (2D) and three-dimensional (3D) face recognition is tackled. While discriminant analysis (DA) methods are effective solutions for recognizing expression-variant 2D face images, they are not directly applicable when only a single sample image per subject is available. This problem is addressed in this thesis by introducing expression subspaces which can be used for synthesizing new expression images from subjects with only one sample image. It is proposed that by augmenting a generic training set with the gallery and their synthesized new expression images, and then training DA methods using this new set, the face recognition performance can be significantly improved. An important advantage of the proposed method is its simplicity; the expression of an image is transformed simply by projecting it into another subspace. The above proposed solution can also be used in general pattern recognition applications. The above method can also be used in 3D face recognition where expression variation is a more serious issue. However, DA methods cannot be readily applied to 3D faces because of the lack of a proper alignment method for 3D faces. To solve this issue, a method is proposed for sampling the points of the face that correspond to the same facial features across all faces, denoted as the closest-normal points (CNPs). It is shown that the performance of the linear discriminant analysis (LDA) method, applied to such an aligned representation of 3D faces, is significantly better than the performance of the state-of-the-art methods which, rely on one-by-one registration of the probe faces to every gallery face. Furthermore, as an important finding, it is shown that the surface normal vectors of the face provide a higher level of discriminatory information rather than the coordinates of the points. In addition, the expression subspace approach is used for the recognition of 3D faces from single sample. By constructing expression subspaces from the surface normal vectors at the CNPs, the surface normal vectors of a 3D face with single sample can be synthesized under other expressions. As a result, by improving the estimation of the within-class scatter matrix using the synthesized samples, a significant improvement in the recognition performance is achieved.