Die Skelettextraktion ist besonders in der Formanalyse ein wichtiges Werkzeug. Im Rahmen des Forschungsprojektes ’Extraktion fertigungsrelevanter Merkmale aus 3D-Daten umformtechnischer Bauteile zur featurebasierten Fertigungsprozessgestaltung’ als Kooperationsprojekt zwischen der Professur Graphische Datenverarbeitung und Visualisierung an der Technischen Universität Chemnitz und des Fraunhofer-Institut für Werkzeugmaschinen und Umformtechnik Chemnitz wurde diese zur Featureerkennung umgesetzt. Dieses Dokument gibt zunächst Einblick in grundlegende Verfahren und Problemstellungen einer solchen Extraktion. Die Ergebnisse mehrerer Forschungsschwerpunkte, die sich aus den zu untersuchenden Massivumformteilen ergaben, werden vorgestellt. Hierbei besonders interessant ist die robuste Extraktion von Kurvenskeletten bei Bauteilen mit nicht-zylindrischer Hauptform, sowie bei Bauteilen mit Nebenformelementen. Desweiteren werden Nachverarbeitung und Auswertung des Kurvenskeletts, sowie verwandte Forschungsarbeiten und -ergebnisse diskutiert.:1. Einleitung 1.1. Bezug zum Forschungsprojekt 1.2. Zielstellung und Organisation 2. Entwicklung von Grundlagenalgorithmen 2.1. Voxelisierung 2.1.1. Algorithmische Grundidee 2.1.2. Qualität und Laufzeit der Voxelisierung 2.1.3. Anforderungen an die Geometrie 2.2. Euklidische Distanztransformation 2.3. Vektor-/ Potentialfelder im Voxelgitter 2.4. Divergenz 2.5. Visualisierung 2.6. Filterung 2.7. Skelettierung 2.7.1. Sequentielles Ausdünnen 2.7.2. Paralleles Ausdünnen 2.8. Invarianz gegenüber Rotation und Rauschen 3. Forschungsschwerpunkte 3.1. Problemdefinition 3.2. Verwandte Arbeiten 3.3. Lösungsansätze im Rahmen der Skelettextraktion 3.4. Lösungsansätze im Rahmen der Geometrieverarbeitung 3.5. Zusammenfassung 4. Skelettverarbeitung 4.1. Grapherzeugung 4.2. Nachverarbeitungsschritte 4.3. Objektanalyse auf Basis des Kurvenskeletts 4.3.1. Profilschnitt 4.3.2. Krümmungsberechnung 4.3.3. Euklidische Distanz zum Rand 4.3.4. Massebestimmung 4.4. Schnittstellendefinition 5. Sonstige Forschungsergebnisse und Betrachtungen 5.1. Beschleunigung 5.2. Größeres Kernel 5.3. Untersuchung verwandter Forschungsarbeiten : Level Set Graph 5.4. Untersuchung verwandter Forschungsarbeiten : Formabstraktion 5.5. Ausrichtung der Geometrie 5.6. Analyse der Geometrie Anhänge A. Formverstehen, Ligature Instability B. Hierarchische Raumunterteilung und Featuregröße C. 2D/3D Untersuchungen zum GVF D. Erhaltung von Flächen E. Beispiele automatisch skelettierter Objekte

Représenter un objet géométrique complexe par un ensemble de primitives simples est une tâche souvent fondamentale, que ce soit pour la reconstruction et la réparation de données, ou encore pour faciliter la visualisation ou la manipulation des données. Le choix de la ou les primitives, ainsi que celui de la méthode d'approximation, impactent fortement les propriétés de la représentation de forme qui sera obtenue.Dans cette thèse, nous utilisons les boules comme seule primitive. Nous prenons ainsi un grand soin à décrire les unions finies de boules et leur structure. Pour cela, nous nous reposons sur les faisceaux de boules. En particulier, nous aboutissons à une description valide en toute dimension, sans hypothèse de position générale. En chemin, nous obtenons également plusieurs résultats portant sur les tests d'inclusion locale et globale dans une union de boules.Nous proposons également une nouvelle méthode d'approximation par union finie de boules, l'approximation par boules à (delta,epsilon)-près. Cette approche contraint l'union de boules à couvrir un sous-ensemble de la forme d'origine (précisément, un epsilon-érodé), tout en étant contenu dans un sur-ensemble de la forme (un delta-dilaté). En nous appuyant sur nos précédents résultats portant sur les unions de boules, nous démontrons plusieurs propriétés de ces approximations. Nous verrons ainsi que calculer une approximation par boules à (delta,epsilon)-près qui soit de cardinal minimum est un problème NP-complet. Pour des formes simples dans le plan, nous présentons un algorithme polynomial en temps et en espace qui permet de calculer ces approximations de cardinal minimum. Nous concluons par une généralisation de notre méthode d'approximation pour une plus large variété de sous-ensembles et sur-ensembles. / Describing a complex geometric shape with a set of simple primitives is often a fundamental task for shape reconstruction, visualization, analysis and manipulation. The type of primitives, as well as the choice of approximation scheme, both greatly impact the properties of the resulting shape representation.In this PhD, we focus on balls as primitives. Using pencils of balls, we carefully describe finite unions of balls and their structure. In particular, our description holds in all dimension without assuming general position. On our way, we also establish various results and tools to test local and global inclusions within these unions.We also propose a new approximation scheme by union of balls, the (delta,epsilon)-ball approximation. This scheme constrains the approximation to cover a core subset of the original shape (specifically, an epsilon-erosion), while being contained within a superset of the shape (a delta-dilation). Using our earlier results regarding finite unions of balls, we prove several properties of these approximations. We show that computing a cardinal minimum (delta,epsilon)-ball approximation is an NP-complete problem. For simple planar shapes however, we present a polynomial time and space algorithm that outputs a cardinal minimum approximation. We then conclude by generalizing the approximation scheme to a wider range of core subsets and bounding supersets.

During the course of this thesis, two scenarios are considered. In the first one, we contribute to feature extraction algorithms. In the second one, we use features to improve object detection solutions and localization. The two scenarios give rise to into four thesis sub-goals. First, we present a new shape skeleton pruning algorithm based on contour approximation and the integer medial axis. The algorithm effectively removes unwanted branches, conserves the connectivity of the skeleton and respects the topological properties of the shape. The algorithm is robust to significant boundary noise and to rigid shape transformations. It is fast and easy to implement. While shape-based solutions via boundary and skeleton analysis are viable solutions to object detection, keypoint features are important for textured object detection. Therefore, we present a keypoint featurebased planar object detection framework for vision-based localization. We demonstrate that our framework is robust against illumination changes, perspective distortion, motion blur, and occlusions. We increase robustness of the localization scheme in cluttered environments and decrease false detection of targets. We present an off-line target evaluation strategy and a scheme to improve pose. Third, we extend planar object detection to a real-time approach for 3D object detection using a mobile and uncalibrated camera. We develop our algorithm based on two novel naive Bayes classifiers for viewpoint and feature matching that improve performance and decrease memory usage. Our algorithm exploits the specific structure of various binary descriptors in order to boost feature matching by conserving descriptor properties. Our novel naive classifiers require a database with a small memory footprint because we only store efficiently encoded features. We improve the feature-indexing scheme to speed up the matching process creating a highly efficient database for objects. Finally, we present a model-free long-term tracking algorithm based on the Kernelized Correlation Filter. The proposed solution improves the correlation tracker based on precision, success, accuracy and robustness while increasing frame rates. We integrate adjustable Gaussian window and sparse features for robust scale estimation creating a better separation of the target and the background. Furthermore, we include fast descriptors and Fourier spectrum packed format to boost performance while decreasing the memory footprint. We compare our algorithm with state-of-the-art techniques to validate the results.

Dans cette thèse, nous proposons l'utilisation de représentations de niveau intermédiaire, et en particulier i) d'axes médians, ii) de parties d'objets, et iii) des caractéristiques convolutionnels, pour modéliser des objets.La première partie de la thèse traite de détecter les axes médians dans des images naturelles en couleur. Nous adoptons une approche d'apprentissage, en utilisant la couleur, la texture et les caractéristiques de regroupement spectral pour construire un classificateur qui produit une carte de probabilité dense pour la symétrie. Le Multiple Instance Learning (MIL) nous permet de traiter l'échelle et l'orientation comme des variables latentes pendant l'entraînement, tandis qu'une variante fondée sur les forêts aléatoires offre des gains significatifs en termes de temps de calcul.Dans la deuxième partie de la thèse, nous traitons de la modélisation des objets, utilisant des modèles de parties déformables (DPM). Nous développons une approche « coarse-to-fine » hiérarchique, qui utilise des bornes probabilistes pour diminuer le coût de calcul dans les modèles à grand nombre de composants basés sur HOGs. Ces bornes probabilistes, calculés de manière efficace, nous permettent d'écarter rapidement de grandes parties de l'image, et d'évaluer précisément les filtres convolutionnels seulement à des endroits prometteurs. Notre approche permet d'obtenir une accélération de 4-5 fois sur l'approche naïve, avec une perte minimale en performance.Nous employons aussi des réseaux de neurones convolutionnels (CNN) pour améliorer la détection d'objets. Nous utilisons une architecture CNN communément utilisée pour extraire les réponses de la dernière couche de convolution. Nous intégrons ces réponses dans l'architecture DPM classique, remplaçant les descripteurs HOG fabriqués à la main, et nous observons une augmentation significative de la performance de détection (~14.5% de mAP).Dans la dernière partie de la thèse nous expérimentons avec des réseaux de neurones entièrement convolutionnels pous la segmentation de parties d'objets.Nous réadaptons un CNN utilisé à l'état de l'art pour effectuer une segmentation sémantique fine de parties d'objets et nous utilisons un CRF entièrement connecté comme étape de post-traitement pour obtenir des bords fins.Nous introduirons aussi un à priori sur les formes à l'aide d'une Restricted Boltzmann Machine (RBM), à partir des segmentations de vérité terrain.Enfin, nous concevons une nouvelle architecture entièrement convolutionnel, et l'entraînons sur des données d'image à résonance magnétique du cerveau, afin de segmenter les différentes parties du cerveau humain.Notre approche permet d'atteindre des résultats à l'état de l'art sur les deux types de données. / In this thesis we propose the use of mid-level representations, and in particular i) medial axes, ii) object parts, and iii)convolutional features, for modelling objects.The first part of the thesis deals with detecting medial axes in natural RGB images. We adopt a learning approach, utilizing colour, texture and spectral clustering features, to build a classifier that produces a dense probability map for symmetry. Multiple Instance Learning (MIL) allows us to treat scale and orientation as latent variables during training, while a variation based on random forests offers significant gains in terms of running time.In the second part of the thesis we focus on object part modeling using both hand-crafted and learned feature representations. We develop a coarse-to-fine, hierarchical approach that uses probabilistic bounds for part scores to decrease the computational cost of mixture models with a large number of HOG-based templates. These efficiently computed probabilistic bounds allow us to quickly discard large parts of the image, and evaluate the exact convolution scores only at promising locations. Our approach achieves a $4times-5times$ speedup over the naive approach with minimal loss in performance.We also employ convolutional features to improve object detection. We use a popular CNN architecture to extract responses from an intermediate convolutional layer. We integrate these responses in the classic DPM pipeline, replacing hand-crafted HOG features, and observe a significant boost in detection performance (~14.5% increase in mAP).In the last part of the thesis we experiment with fully convolutional neural networks for the segmentation of object parts.We re-purpose a state-of-the-art CNN to perform fine-grained semantic segmentation of object parts and use a fully-connected CRF as a post-processing step to obtain sharp boundaries.We also inject prior shape information in our model through a Restricted Boltzmann Machine, trained on ground-truth segmentations.Finally, we train a new fully-convolutional architecture from a random initialization, to segment different parts of the human brain in magnetic resonance image data.Our methods achieve state-of-the-art results on both types of data.

Dans cette thèse, nous étudions les problèmes de reconstruction statique et dynamique à partir de vues multiples et texturation, en s'appuyant sur des applications réelles et pratiques. Nous proposons trois méthodes de reconstruction destinées à l'estimation d'une représentation d'une scène statique/dynamique à partir d'un ensemble d'images/vidéos. Nous considérons ensuite le problème de texturation multi-vues en se concentrant sur la qualité visuelle de rendu..