Algorithms and tools for deriving editable models from cross-sectional data sets

Abstract

In this thesis, we present a novel method for reconstructing the surface of a 3D object using as input only a point cloud of its surface scan. The objective is to obtain an editable CAD model that is manufacturable and describes accurately the structure and topology of the point cloud. This model will provide a high level representation of the actual object, which can also be modified with the use of a set of editing operators we have defined. The entire method is performed in three phases: the segmentation of the point cloud, the reconstruction of the model and the editing process.In the segmentation phase, the point cloud is sliced into cross sections, which are later on treated as 2D point sets. Several parameters of the slicing procedure influence the resulting model, and have to be set properly to ensure high quality output. One essential parameter is the slicing direction. It has to correspond to the principal axis of the point cloud, either locally or globally, so that the basic features of the point cloud are properly distributed across the cross sections. Another key parameter in the segmentation process is the thickness of the cross sections. The cross sections should contain sufficient information about the features of the point cloud, so their thickness cannot be very slim. But it should not be very thick either, as we do not want to have many features tangled together in the same cross section.The reconstruction phase includes several procedures that take as input the cloud points of the cross sections and provide as output a model of the 3D object, with high level features and properties that can be used for further processing. First, the boundary of each cross section is represented as a set of line segments called the feature poly-line. This poly-line is computed with the use of computational geometry methods, i.e. the convex hull and the Voronoi diagram. The feature poly-line of each cross section is then recomputed as an interpolating B-Spline curve, providing a smooth continuous representation of the model. The curves of the neighboring cross sections are combined with each other to form the surface of the final 3D model. To reconstruct the surface between two adjacent cross sections, a new set of feature points is computed on the B-Spline curves, using arc length parameterization, and a contour triangulation method provides the surface of the model. The resulting model can be subject to high level modifications that provide variations of the initial object with additional user specified properties.For the editing process, we have implemented a set of editing operators, which can be applied either to the entire model, or on a part of it, to deform its surface in various ways. As a point of reference for these editing operators, a given point may be used on the interpolating curve computed from the centroids of the cross sections. We call it the curve of centroids and it is a form of skeleton curve for the model. The editing operators vary from general purpose transformations to high level editing operators addressed to cross sectional data sets used in medical research. The general purpose transformations can be used to modify free form models arbitrarily, and can be applied to parts of the model according to user specified parameters. The high level editing operators allow modifications such as bending or stretching the model of an artery, allowing medical experts to study and control the behavior of tissues during a simulation of a surgical operation such as angioplasty or stent insertion.The novelty of this study includes: (a) the introduction of an efficient method for computing a boundary representations of cross-sectional point sets, using the convex hull and the Voronoi diagram of the points, (b) the use of a technique for inserting artificial cross sections between existing slices, to improve the rendering quality of the model, and (c) the definition of a set of editing operators that may be used in everyday examples, varying from purely aesthetic purposes to simulation of surgical operations in medical data sets.

Στη διατριβή αυτή παρουσιάζουμε μια καινοτόμα προσέγγιση για την ανακατασκευή της επιφάνειας ενός 3-διάστατου αντικειμένου, χρησιμοποιώντας ως είσοδο ένα νέφος σημείων της σαρωμένης επιφάνειάς του. Στόχος είναι να αποκτήσουμε ένα μοντέλο CAD με δυνατότητα επεξεργασίας, που να μπορεί να κατασκευαστεί και το οποίο θα περιγράφει με ακρίβεια τη δομή και την τοπολογία του νέφους σημείων. Το μοντέλο αυτό θα παρέχει μια υψηλού επιπέδου αναπαράσταση του αντικειμένου, που θα μπορεί να τροποποιηθεί με τη χρήση ενός συνόλου από τελεστές τους οποίους έχουμε σχεδιάσει. Η όλη μέθοδος διενεργείται σε τρεις φάσεις: την κατάτμηση του νέφους σημείων, την ανακατασκευή της επιφάνειας του μοντέλου και την επεξεργασία/τροποποίηση του μοντέλου.Κατά την φάση της κατάτμησης, το νέφος σημείων χωρίζεται σε εγκάρσιες τομές, οι οποίες κατά την μετέπειτα επεξεργασία αντιμετωπίζονται ως 2-διάστατα σύνολα σημείων. Σε αυτή τη φάση υπάρχουν κάποιες παράμετροι που επηρεάζουν το τελικό μοντέλο, και θα πρέπει να καθοριστούν κατάλληλα ώστε να εξασφαλιστεί το καλύτερο δυνατό αποτέλεσμα. Μια βασική παράμετρος είναι η κατεύθυνση της κατάτμησης, που θα πρέπει να συμφωνεί με τον κύριο άξονα του νέφους σημείων, είτε σε καθολικό επίπεδο είτε τοπικά, ώστε τα βασικά χαρακτηριστικά του νέφους σημείων να αποτυπωθούν επαρκώς στις εγκάρσιες τομές. Μια άλλη βασική παράμετρος στη φάση της κατάτμησης είναι το πάχος που θα έχουν οι τομές. Οι τομές θα πρέπει να περιέχουν επαρκή πληροφορία για τα χαρακτηριστικά του νέφους σημείων, οπότε δεν θα πρέπει να είναι υπερβολικά λεπτές. Όμως δεν θα πρέπει να είναι ούτε και πολύ παχιές, για να μην εμπλέκονται στην ίδια τομή πολλά χαρακτηριστικά μεταξύ τους ιδιαίτερα όταν αυτά εντοπίζονται σε γειτονικές περιοχές.Η φάση της ανακατασκευής του μοντέλου περιλαμβάνει αρκετές διαδικασίες, οι οποίες παίρνουν ως είσοδο τα σημεία των εγκάρσιων τομών και παράγουν ως έξοδο ένα μοντέλο του 3-διάστατου αντικειμένου, που διαθέτει υψηλού επιπέδου ιδιότητες και χαρακτηριστικά, και μπορεί να χρησιμοποιηθεί για περαιτέρω επεξεργασία. Αρχικά τα όρια της κάθε τομής αναπαρίστανται με μια κλειστή πολυγωνική γραμμή, η οποία υπολογίζεται με τη βοήθεια μεθόδων υπολογιστικής γεωμετρίας, όπως το κυρτό περίβλημα και το διάγραμμα Voronoi. Στη συνέχεια, η πολυγωνική γραμμή κάθε τομής επαναπροσδιορίζεται ως μια καμπύλη B-Spline που θα παρέχει μια συνεχή και ομαλή αναπαράσταση του μοντέλου. Οι καμπύλες των γειτονικών τομών συνδυάζονται για να συνθέσουν την επιφάνεια του τελικού 3-διάστατου μοντέλου. Για την ανακατασκευή της επιφάνειας μεταξύ δυο γειτονικών τομών, υπολογίζουμε ένα νέο σύνολο σημείων επάνω στις καμπύλες, χρησιμοποιώντας παραμετροποίηση μήκους τόξου, και η επιφάνεια του μοντέλου προκύπτει από την τριγωνοποίηση των περιγραμμάτων. Το μοντέλο που προκύπτει μπορεί να υπόκειται σε υψηλού επιπέδου μετασχηματισμούς που παρέχουν παραλλαγές του αρχικού αντικειμένου με επιπλέον ιδιότητες καθορισμένες από το χρήστη.Στη φάση της επεξεργασίας, υλοποιήσαμε μια σειρά από τελεστές που μπορούν να εφαρμοστούν στο μοντέλο είτε καθολικά είτε τμηματικά, για να μετασχηματίσουν την επιφάνειά του με διάφορους τρόπους. Το σημείο αναφοράς για τους μετασχηματισμούς αυτούς τοποθετείται πάνω στην καμπύλη που ορίζεται από τα κέντρα βάρους των τομών και η οποία αποτελεί ένα είδος σκελετού του αντικειμένου. Οι τελεστές ποικίλουν από μετασχηματισμούς γενικού ενδιαφέροντος μέχρι υψηλού επιπέδου μετασχηματισμούς ειδικά σχεδιασμένους για δεδομένα προερχόμενα από τομογραφίες που χρησιμοποιούνται στην ιατρική έρευνα. Οι απλοί μετασχηματισμοί χρησιμοποιούνται για την ελεύθερη τροποποίηση ενός μοντέλου, και μπορούν να εφαρμοστούν σε τμήματα του μοντέλου σύμφωνα με τις παραμέτρους που ορίζει ο χρήστης. Οι τελεστές υψηλού επιπέδου αφορούν τροποποιήσεις όπως πχ το τέντωμα ή το λύγισμα του μοντέλου μιας αρτηρίας, επιτρέποντας στους ειδικούς να μελετήσουν και να ελέγξουν τη συμπεριφορά των ιστών κατά τη διάρκεια μιας εγχείρησης, όπως πχ στην αγγειοπλαστική ή στην τοποθέτηση stent.H συνεισφορά της έρευνας αυτής περιλαμβάνει: (α) τη σύσταση μιας μεθόδου για τον αποτελεσματικό υπολογισμό της αναπαράστασης των ορίων ενός συνόλου σημείων οργανωμένων σε τομές, (β) τη χρήση μιας καινοτόμου τεχνικής για την εισαγωγή τεχνητών τομών ανάμεσα σε υπάρχουσες τομές για τη βελτίωση αναπαράστασης του μοντέλου, και (γ) τον ορισμό ενός συνόλου από τελεστές μετασχηματισμού που μπορούν να εφαρμοστούν σε γενικά παραδείγματα, που ποικίλουν από αισθητικές παρεμβάσεις μέχρι την προσομοίωση χειρουργικών επεμβάσεων σε ιατρικές εφαρμογές.