View on GitHub

Skeletonextraction3D

Skeleton extruction 3D using Visible Repulsive Force and animation

Download this project as a .zip file Download this project as a tar.gz file

SkeletonExtraction3D

Skeleton extruction 3D using Visible Repulsive Force and animation

Author: Jim Stanev

Περιγραφή

Σε αυτή την εργασία υλοποιείται σκελετοποίηση σε τρισδιάστατα και δισδιάστατα μοντέλα με χρήση ενός αλγορίθμου και αφού εξαχθεί ο σκελετός γίνεται κάποιο στοιχειώδες animation, όπου κινείται ο σκελετός και το δέρμα του μοντέλου ακολουθεί την κίνηση του.

Προδιαγραφές

Τα προγράμματα είναι γραμμένα σε Java και για την εκτέλεση τους απαιτείται η εγκατάσταση του jre το οποίο μπορείτε να το κατεβάσετε από το site της Oracle http://www.oracle.com/technetwork/java/javase/downloads/index.html. Όσο αφορά τις επιπρόσθετες βιβλιοθήκες που απαιτούνται έχουν συμπεριλήφθη δίπλα στο εκτελέσιμο σε φάκελο lib μέσα στο dist. Ενδεικτικά αναφέρεται ποιες βιβλιοθήκες χρησιμοποιήθηκαν:

Για το 2Δ υλοποιήθηκαν τα απαραίτητα primitives (line point vector etc). Για το 3Δ παρθήκαν έτοιμα από γεωμετρικές βιβλιοθήκες, αλλά δεν θα ήταν δύσκολη η υλοποίηση. Το project έχει την εξής δομή:

Σε περίπτωση που δεν ξεκινήσει το animation στο info screen θα εμφανισθεί σφάλμα. Πιθανόν θα ευθύνεται το γεγονός ότι στο lib φάκελο δεν περιέχεται το αντίστοιχο jar για την jogl που υποστηρίζει το λειτουργικό και συγκεκριμένα (gluegen-rt-natives-windows-i586 και jogl-all-natives-windows-i586). Σε τέτοια περίπτωση παρακαλώ κατεβάστε την jogl και αντιγράψτε το αντίστοιχο jar στο φάκελο lib. Για να μην υπάρχει πρόβλημα έχουν ενσωματωθεί τα jar για να υποστηρίξουν τις εξής διανομές:

Ανάπτυξη

Εδώ θα περιγράψουμε την διαδικασία ανάπτυξης της εφαρμογής και τα βήματα. Αρχικά δημιουργηθήκαν οι απαραίτητες κλάσεις που αφορούν το άνοιγμα του obj file, το οποίο έχει μια συγκεκριμένη δομή.

Αφού ορτώσουμε το αρχείο έχουμε στην διάθεση μας τις συντεταγμένες του μοντέλου και την σειρά με την οποία φτιάχνουν το περίβλημα. Για να μπορέσουμε να εργαστούμε δημιουργήθηκαν κλάσεις που διαχειρίζονται τα σημεία και αποτυπώνουν το μοντέλο είτε με JOGL είτε με Java Graphics.

Το επόμενο βήμα είναι να εξάγουμε τον σκελετό από το μοντέλο. Ο αλγόριθμος που υλοποιήθηκε είναι γενικός και δουλεύει με το ίδιο τρόπο και στο 2Δ και στο 3Δ.

Αφού γίνει κάποια σκελετοποίηση πρέπει να φιλτραριστεί το αποτέλεσμα και να εξαχθεί σε κάποια δομή που να μπορεί να προσπελάζεται εύκολα.

Έπειτα γίνεται η συσχέτιση του δέρματος με το σκελετό έτσι ώστε να μπορούμε να προσδίδουμε κίνηση στον σκελετό και το δέρμα να την ακολουθεί χωρίς να χιάζεται να υπολογίζονται ξεχωριστά οι καινούργιες θέσεις των σημείων.

Υλοποιήθηκαν οι κατάλληλες δομές για animation όπως είναι το keyframe και δημιουργήθηκες εύκολος τρόπος προσπέλασης των οστών του σκελετού με το πληκτρολόγιο και η περιστροφή τους σε σχέση με τον πατέρα τους. Επίσης δημιουργήθηκε η δυνατότητα της άμεσης καταγραφής ενός pose και τέλος αφού έχουν καταγραφεί κάποια pose με το πάτημα του πληκτρολογίου γίνεται το animation. Αφού τελειώσει το animation γίνεται επανεκκίνηση του αρχικού pose και η διαδικασία επαναλαμβάνεται μέχρι να διακοπεί το animation με το πληκτρολόγιο.

Σκελετοποίηση

Θεωρητικά είναι το δυσκολότερο κομμάτι του project. Με λίγα λόγιο αυτό που κάνουμε είναι:

  1. Για κάθε σημείο του δέρματος
  2. Πάρε ένα σημείο και ώθησε το προς το εσωτερικό του όγκου
  3. Υπολόγισε το Visible set
  4. Βρες την κατεύθυνση που να σε κατευθύνει προς το ελάχιστο σημείο ισορροπίας για το δεδομένο Visible set και προχώρα
  5. Ξανά στο βήμα 3 με τις καινούργιες συντεταγμένες έως βρω ολικό ελάχιστο
  6. Μαζεύω τα σημεία σε ένα μια λίστα που θα την επεξεργαστώ αργότερα και θα φιλτράρω το αποτέλεσμα

Η μέθοδος λέγεται visible repulsive force [1]. Το visible set είναι ένα set με σημεία που ανήκουν στην επιφάνεια και είναι ορατά στο σημείο που εξετάζουμε. Το διάνυσμα που μας δίνει την κατεύθυνση υπολογίζεται με τον εξής τρόπο:

Όπου vi είναι το visible set και x είναι το σημείο που εξετάζουμε. Η συνάρτηση f είναι η 1/x2 και περνάμε σαν όρισμα την δεύτερη Ευκλείδεια νόρμα. Για να καταλάβουμε πως δουλεύει πρέπει να προσέξουμε ότι το vrf είναι διάνυσμα που αθροίζει διανύσματα (vi-x) και τα πολλαπλασιάζει με μία βαθμωτή ποσότητα που παίζει το ρόλο της επιρροής αυτού του διανύσματος στην συνολική κατεύθυνση.

Αφού έχει γίνει η σκελετοποίηση έχουμε ένα σύνολο από σημεία τα οποία ακλούθησε ένα σημείο του σκελετού για να φτάσει στο σημείο ισορροπίας. Αυτό δεν μας κάνει οπότε πρέπει να γίνει κάποιο φιλτράρισμα. Παρακάτω φαίνεται το αποτέλεσμα αν δεν γίνει κάποιο φιλτράρισμα και αραίωμα των σημείων. Επίσης παρατηρούμε ότι οι αλυσίδες δεν είναι ενωμένες. Το τελευταίο θα το αντιμετωπίσουμε με την χρήση θεωρία γράφων και τον αλγόριθμο για την εύρεση minimum spanning tree.

Σχήμα 1: Αριστερά φαίνεται η δειγματοληψία του χώρου και ο υπολογισμός του vrf που δείχνει την κατεύθυνση. Δεξιά φαίνετε η σύγκληση στο σημείο ισορροπίας.

Αυτό που μπορούμε να κάνουμε για να βελτιώσουμε τον σκελετό είναι να:

Δημιουργία δομή δέντρου

Το επόμενο βήμα είναι να εξαχθεί ο σκελετός σε προσπελάσιμη δομή όπως είναι το δέντρο, όπου θα επιλέξουμε αυθαίρετα έναν από τους υποψήφιους root κόμβους και θα τον βάλουμε σαν ρίζα στο δέντρο και με διαδοχικές προσπελάσεις θα εισαχθούν τα παιδιά με τα οποία συνδέεται. Η δομή αυτή μας βοηθάει στο animation όπως θα δούμε αργότερα.

Κάθε κόμβος του δέντρου περιέχει τις εξής πληροφορίες:

Κίνηση

Ο λόγος που επιλέξαμε την δομή δέντρου είναι για να μπορούμε εύκολα αν δώσουμε κίνηση σε ένα οστό να μεταδοθεί αυτόματα και στα παιδιά του οστού. Ο τρόπος με τον οποίο δίνουμε κίνηση είναι με την χρήση των σχετικών γωνιών μεταξύ πατέρα και παιδί. Αλλάζοντας την γωνία περιστρέφουμε το κόκαλο περιστρέφεται ως προς τον πατέρα του. Επίσης θα μπορούσαμε να παίξουμε κε με το μήκος του οστού.

Για να διευκολυνθούμε δημιουργηθήκαν κάποιοι μηχανισμοί εντοπισμού ενός οστού και ο κατάλληλος χρωματισμός του για να φαίνεται ότι είναι επιλεγμένο. Η εναλλαγή των οστών γίνεται με το πληκτρολόγιο. Επίσης δόθηκε η δυνατότητα να αλλάζουμε την γωνία του οστού με αποτέλεσμα να δημιουργούμε περιστροφές.

Keyframe

Για να μπορέσουμε να δώσουμε κίνηση στο σκελετό πρέπει με κάποιον τρόπο να αποθηκεύσουμε τις σχετικές παραμέτρους όλων των οστών για δεδομένη χρονική στιγμή. Για τον σκοπό αυτό δημιουργήθηκε η keyframe κλάση η οποία αποθηκεύεται στο κόκαλο. Μια σειρά από key frames δίνει μια κίνηση.

Για να έχουμε ομαλό αποτέλεσμα αν ένα κόκαλο βρίσκεται σε μια θέση με μια γωνία α και στο επόμενο key frame βρίσκεται σε μια θέση με μια γωνία β τότε μπορούμε να δημιουργήσουμε ενδιάμεσα keyframes που δεν αποθηκεύονται κάπου αλλά αναπαριστούν την ενδιάμεση θέση του οστού μεταξύ δυο key frames και με βάση το FPS να υπολογίζουμε το βήμα που πρέπει να κουνάμε τον σκελετό για να φτάσουμε στο σημείο β μέσα στο συγκεκριμένο διάστημα.

Για να υπολογίσουμε την γωνία με την οποία μετακινούμαστε μπορούμε να κάνουμε απλή γραμμική παλινδρόμηση για παράδειγμα:

Αν έχουμε γωνία α = 0 για t = 0 και γωνία α = 180 για t = 10 και δουλεύουμε με 12fps τότε το βήμα μας είναι: (180 - 0) / (10 * 12 - 0 * 12) = 180 / 120 = 1.5° Οπότε όσο time <10 θα προσθέτουμε 1.5 στην γωνιά.

Skinning

Το skinning είναι ένα δύσκολο κομμάτι. Αυτό που κάναμε σε αυτό το project λέγετε liner blend skinning. Η διαδικασία που ακολουθήσαμε είναι να εντοπίζουμε τα πιο κοντινά οστά από το σημείο του δέρματος δίνοντας σαν είσοδο τον αριθμό εξαρτήσεων που μπορεί να έχει ένα σημείο. Αφού γίνει ο εντοπισμός πρέπει να υπολογιστούν κάποιοι παράμετροι που μετασχηματίζουν το σημείο του δέρματος στο σύστημα συντεταγμένων του κάθε οστό που συσχετίζεται και με χρήση κάποιων βαρών και τον απόλυτο πίνακα μετασχηματισμού του κάθε οστού να υπολογίζεται η καινούργια θέση του δέρματος.

Στατιστικές μελέτες έχουν δείξει πως δεν χρειάζεται να προσκολλούμε πολλά οστά σε ένα σημείο του δέρματος αλλά ο βέλτιστος αριθμός είναι γύρο στο 3.

Με βάση την θεωρία μπορούμε να υπολογίσουμε την νέα θέση του σημείου του δέρματος από τον εξής τύπο:

v^'= ∑_dependencies〖w_i*M_i*B_i^(-1)*v〗

Όπου:

Για να μην έχουμε παραμόρφωση πρέπει το άθροισμα των w να είναι 1.

Τον Μ πίνακα μπορούμε να τον υπολογίσουμε από τον διαδοχικό πολλαπλασιασμό των σχετικών πινάκων για να φτάσουμε από την ρίζα στο αντίστοιχο οστό, αλλά ευτυχώς η opengl μας δίνει την δυνατότητα να πάρουμε τον πίνακα που έχει στο stack ο οποίος κάθε στιγμή είναι ο απόλυτος πίνακας και να τον αποθηκεύσουμε στο αντίστοιχο bone. Οπότε όσο ζωγραφίζουμε το σκελετό αποθηκεύουμε και τον νέο πίνακα κάθε φορά για να ήμαστε ενήμερη για την νέα θέση.

Animation

Το animation δεν είναι τίποτα παρά να βάλουμε ένα βρόγχο στον οποίον θα ζωγραφίζουμε τα οστά και το δέρμα και για κάθε frame θα ενημερώνουμε την καινούργια θέση του δέρματος σε σχέση με την κίνηση των οστών.

Σχολία για το 2Δ

Όσο αφορά το δισδιάστατο κομμάτι η σκελετοποίηση είναι παραμετρική και γίνεται σωστά. Επίσης δίνεται η δυνατότητα να φορτωθεί απευθείας το bone system από αρχείο και το μοντέλο και να γίνει animation. Έχει γενικά δύο σημεία που χρειάζονται επιδιόρθωση. Το ένα είναι ότι αν κατά την σκελετοποίηση δεν εξαχθεί συμπαγές σκελετός (ενιαίος) τότε δεν θα μπορέσει να εξάγει την δομή δέντρου με αποτέλεσμα να κολλήσει. Αυτό δεν γίνεται στο 3Δ γιατί εξαρχής δημιουργήθηκαν οι κατάλληλες δομές για να βοηθήσουν στην εξομάλυνση του σκελετού και στην εύκολη εξαγωγή της δομής δέντρου. Το δεύτερο κομμάτι είναι ότι δεν υπολογίζονται κατάλληλα οι σχετικές γωνίες με αποτέλεσμα να αναποδογυρίζει τον σκελετό και να μην ταιριάζει στο μοντέλο. Αν αλλάξει ο τρόπος υπολογισμού των γωνιών δεν θα υπάρχει πρόβλημα. Παρόλα αυτά για να μπορεί να γίνει έλεγχος του animation και του skinning μπορεί να φορτωθεί έτοιμο μοντέλο με σκελετό.

Μέσα στο doc υπάρχει ένα index αρχείο το οποίο ανοίγει τα java docs και μπορεί κάποιος να δει πως είναι δομημένο το project τις κλάσεις που έχει και το τι κάνουν με επεξήγηση για τις μεθόδους και τα πεδία τους.

Σχολία για το 3Δ

Όσο αφορά το 3Δ στην κατασκευή του σκελετού δημιουργηθήκαν κατάλληλες δομές για να βοηθήσουν στην μεταεπεξεργασία του σκελετού. Η οργάνωση ήταν καλύτερη και η διαδικασία ήταν γνωστή. Δημιουργήθηκε χειριστής event για την camera με το ποντίκι. Όσο αφορά αυτό σε πολλά site αυτό που κάνα είναι να περιστρέφουν και να μετατοπίζουν το σύστημα συντεταγμένων της opengl με αποτέλεσμα αν ζωγραφίζεις με σχετικές συντεταγμένες να σου παραμορφώνει το μοντέλο. Αυτό διορθωτικέ με την χρήση της glu lookAt και την μετακίνηση της κάμερας και όχι του συστήματος συντεταγμένων με αποτέλεσμα να αφήνει το μοντέλο αναλλοίωτο.

Επίσης επειδή δεν μπορούμε να ξέρουμε την φορά των κάθετων διανυσμάτων των επιφανειών του μοντέλου από το obj για αυτό υλοποιήθηκε μια συνάρτηση η οποία ελέγχει αν το διάνυσμα κοιτάει προς τα έξω η προς τα μέσα.

Γενικά και εδώ υπάρχει ένα θεματάκι όσο αφορά το σκελετό. Αν το μοντέλο αποτελείται από πολλές επιφάνειες η επεξεργασία για το visible set είναι πολύ χρονοβόρα και για να βρεθεί ένα local minimum απαιτείται να προσπελαστούν πολλές φορές οι επιφανείς για να βρεθεί αν υπάρχει τομή μεταξύ ακτίνας και τριγώνου (για τις επιφανείς). Συγκεκριμένα έγινε δειγματοληψία σε 14 κατευθύνσεις για visible set κάθε μια από τις 14 απαιτεί την προσπέλαση όλων των επιφανειών του μοντέλου για να βρει αν υπάρχει τομή (είναι απαραίτητα να προσπελαστούν όλα) και αυτή η διαδικασία για ένα κόμβο επαναλαμβάνεται όσες φορές είναι τα iterations που έχουμε δώσει. Με άλλα λόγια η επιβάρυνση για τον υπολογισμό του visible set είναι:

Ο(14*n*iterations*m)

Όπου n είναι ο αριθμός των κόμβων και m είναι ο αριθμός των επιφανειών. Χωρίς να έχουμε προσθέσει την επιβάρυνση των άλλων διαδικασιών και υπολογισμών στον αλγόριθμο.

Για τον λόγο αυτό και επειδή δεν μπόρεσα να σκεφτώ κάποια κατάλληλη δομή για να βελτιώνει τον χρόνο έγινε μια μάταιη προσπαθεί να βελτιώσω τον χρόνο εκτέλεσης με την χρήση των πυρήνων του υπολογιστή. Παρατήρησα ότι το να ψάξεις ένα local minimum είναι μια εργασία που δεν εξαρτάται από άλλες, άρα μπορεί να παραλληλιστεί. Χρησιμοποίησα το pool of threads pattern και δημιούργησα ένα executor στον οποίο έδωσα ένα αριθμό από threads και κάθε thread αναπαριστά την διαδικασία για τον εντοπισμό του local minimum. Για να γλυτώσουμε το overhead της δημιουργίας των threads αν ένα νήμα τελειώσει την διαδικασία τότε είναι διαθέσιμο και μπορεί να του αναθέτει καινούργιος κόμβος. Ο χρόνος εκτέλεσης θα βελτιωθεί σε περίπτωση που ο υπολογιστής έχει πολλούς πυρήνες.

Γενικά όλα δουλεύουν στο 3Δ αλλά δεν μπόρεσα να ανοίξω μεγάλα μοντέλα λόγο της καθυστέρησης. Επίσης η κινήσεις δεν έγιναν με ομογενείς πίνακες αλλά με απλές περιστροφές και μετατοπίσεις.  

Βιβλιογραφία

  1. Fu-Che Wu, Wan-Chun Ma, Ping-Chou Liou, Rung-Huei Liang and Ming Ouhyoung Skeleton Extraction of 3D Objects with Visible Repulsive Force Eurographics Symposium on Geometry Processing 2003
  2. Skinning http://graphics.ucsd.edu/courses/cse169_w05/3-Skin.htm
  3. Ray-Triangle intersection http://www.scratchapixel.com/lessons/3d-basic-lessons/lesson-9-ray-triangle-
  4. intersection/ray-triangle-intersection-geometric-solution/
  5. Minimum spanning tree http://algs4.cs.princeton.edu/43mst/
  6. Ilya Baran, Jovan Popovi Automatic Rigging and Animation of 3D Characters Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology
  7. Mian Pan and Gisela Klette A revision of a 3D Skeletonization algorithm Department of Computer Science University of Auckland Centre of Image Technology and Robotics (CITR) Tamaki Campus, Morrin Road, Building 731, Glen Innes,Auckland New Zealand
  8. Nicu D. Cornea, Deborah Silver, Xiaosong Yuan, Raman BalasubramanianComputing hierarchical curve-skeletons of 3D objects Published online: 14 September 2005