Καταμέτρηση κουτιών

Εικόνα 1. Ένα τετραγωνικό φράκταλ 32 τμημάτων που προβάλλεται μέσα από "κουτιά" διαφορετικών μεγεθών. Το μοτίβο απεικονίζει την αυτοομοιότητα.

Η καταμέτρηση κουτιών είναι μια μέθοδος συλλογής δεδομένων για την ανάλυση σύνθετων μοτίβων με το σπάσιμο ενός συνόλου δεδομένων, αντικειμένου, εικόνας κ.λπ. σε όλο και μικρότερα κομμάτια, συνήθως σε σχήμα "κουτιού", και την ανάλυση των κομματιών σε κάθε μικρότερη κλίμακα. Η ουσία της διαδικασίας έχει συγκριθεί με τη μεγέθυνση ή σμίκρυνση με τη χρήση οπτικών ή υπολογιστικών μεθόδων για την εξέταση του τρόπου με τον οποίο οι παρατηρήσεις των λεπτομερειών αλλάζουν με την κλίμακα. Στην καταμέτρηση με κουτιά, ωστόσο, αντί να αλλάζει η μεγέθυνση ή η ανάλυση ενός φακού, ο ερευνητής αλλάζει το μέγεθος του στοιχείου που χρησιμοποιείται για την επιθεώρηση του αντικειμένου ή του μοτίβου (βλ. Εικόνα 1). Οι αλγόριθμοι καταμέτρησης κουτιών που βασίζονται σε υπολογιστή έχουν εφαρμοστεί σε μοτίβα σε 1-, 2- και 3-διάστατους χώρους. Η τεχνική υλοποιείται συνήθως σε λογισμικό για χρήση σε μοτίβα που εξάγονται από ψηφιακά μέσα, αν και η θεμελιώδης μέθοδος μπορεί να χρησιμοποιηθεί για τη φυσική διερεύνηση ορισμένων μοτίβων. Η τεχνική προέκυψε και χρησιμοποιείται στην μορφοκλασματική ανάλυση. Έχει επίσης εφαρμογή σε συναφείς τομείς όπως η λακκογραφία και η πολυκλασματική ανάλυση.

Η μέθοδος

Θεωρητικά, ο σκοπός της καταμέτρησης κουτιών είναι να ποσοτικοποιηθεί η Φράκταλ κλιμάκωση, αλλά από πρακτική άποψη αυτό θα απαιτούσε να είναι γνωστή η κλιμάκωση εκ των προτέρων. Αυτό φαίνεται στο Σχήμα 1, όπου η επιλογή κουτιών με τα κατάλληλα σχετικά μεγέθη δείχνει εύκολα πώς το μοτίβο επαναλαμβάνεται σε μικρότερες κλίμακες. Στην ανάλυση φράκταλ, ωστόσο, ο παράγοντας κλιμάκωσης δεν είναι πάντα γνωστός εκ των προτέρων, οπότε οι αλγόριθμοι μέτρησης κουτιών προσπαθούν να βρουν έναν βελτιστοποιημένο τρόπο κοπής ενός μοτίβου που θα αποκαλύψει τον παράγοντα κλιμάκωσης. Η θεμελιώδης μέθοδος για να γίνει αυτό ξεκινά με ένα σύνολο στοιχείων μέτρησης -κουτιά - που αποτελείται από έναν αυθαίρετο αριθμό, που εδώ για ευκολία ονομάζεται $\mathrm{E}$, μεγεθών ή διαμετρημάτων, τα οποία θα ονομάσουμε σύνολο $\mathrm{E}$s. Στη συνέχεια, αυτά τα κουτιά μεγέθους $ϵ$ εφαρμόζονται στο μοτίβο και καταμετρώνται. Για να γίνει αυτό, για κάθε $ϵ$ στο $\mathrm{E}$, ένα στοιχείο μέτρησης που είναι συνήθως ένα δισδιάστατο τετράγωνο ή τρισδιάστατο κουτί με μήκος πλευράς που αντιστοιχεί στο $ϵ$ χρησιμοποιείται για να σαρώσει ένα μοτίβο ή ένα σύνολο δεδομένων (π.χ., μια εικόνα ή ένα αντικείμενο) σύμφωνα με ένα προκαθορισμένο σχέδιο σάρωσης για να καλύψει το σχετικό τμήμα του συνόλου δεδομένων, καταγράφοντας, δηλαδή μετρώντας, για κάθε βήμα της σάρωσης τα στοιχεία που συλλαμβάνονται εντός του στοιχείου μέτρησης.

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

Τα δεδομένα

Τα σχετικά χαρακτηριστικά που συλλέγονται κατά τη διάρκεια της καταμέτρησης των κουτιών εξαρτώνται από το θέμα που ερευνάται και τον τύπο της ανάλυσης που γίνεται. Δύο καλά μελετημένα θέματα καταμέτρησης κουτιών, για παράδειγμα, είναι τα δυαδικά (που σημαίνει ότι έχουν μόνο δύο χρώματα, συνήθως μαύρο και άσπρο) και η κλίμακα του γκρι ψηφιακές εικόνες (π.χ. jpegs, tiffs κ.λπ.). Η καταμέτρηση κουτιών γίνεται γενικά σε μοτίβα που εξάγονται από τέτοιες ακίνητες εικόνες, οπότε οι ακατέργαστες πληροφορίες που καταγράφονται βασίζονται συνήθως σε χαρακτηριστικά των εικονοστοιχείων, όπως μια προκαθορισμένη τιμή χρώματος ή ένα εύρος χρωμάτων ή εντάσεων. Όταν η καταμέτρηση κουτιών γίνεται για τον προσδιορισμό μιας διάστασης φράκταλ, γνωστής ως διάσταση καταμέτρησης κουτιών, οι πληροφορίες που καταγράφονται είναι συνήθως είτε ναι είτε όχι ως προς το αν το κουτί περιείχε ή όχι εικονοστοιχεία του προκαθορισμένου χρώματος ή εύρους (δηλαδή, μετράται ο αριθμός των κουτιών που περιέχουν σχετικά εικονοστοιχεία σε κάθε $ϵ$). Για άλλους τύπους ανάλυσης, τα δεδομένα που αναζητούνται μπορεί να είναι ο αριθμός των εικονοστοιχείων που εμπίπτουν στο κουτί μέτρησης, το εύρος ή οι μέσες τιμές των χρωμάτων ή των εντάσεων, η χωρική διάταξη μεταξύ των εικονοστοιχείων σε κάθε κουτί, ή ιδιότητες όπως η μέση ταχύτητα (π.χ. από τη ροή σωματιδίων).

Εικόνα 2a. Κουτιά τοποθετημένα πάνω σε μια εικόνα ως σταθερό πλέγμα.

Εικόνα 3. Ανάλυση των αγγείων του αμφιβληστροειδούς που αποκαλύφθηκε μέσω της ανάλυσης καταμέτρησης των κουτιών- χρωματικά κωδικοποιημένη ανάλυση των τοπικών συνδεδεμένων διαστάσεων φράκταλ που έγινε με το ελεύθερο λογισμικό FracLac για την ανάλυση βιολογικών εικόνων.

Τύποι σάρωσης

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

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

Εικόνα 2b. Πλαίσια που ολισθαίνουν πάνω σε μια εικόνα με αλληλοεπικαλυπτόμενο μοτίβο.

Εικόνα 2c. Κουτιά τοποθετημένα πάνω σε μια εικόνα συγκεντρωτικά εστιασμένα σε κάθε εικονοστοιχείο ενδιαφέροντος.

Σταθερές σαρώσεις πλέγματος

Η κλασική προσέγγιση είναι η σάρωση σε ένα μη επικαλυπτόμενο κανονικό πλέγμα ή μοτίβο πλέγματος. Ενδεικτικά, στην Εικόνα 2 α παρουσιάζεται το τυπικό μοτίβο που χρησιμοποιείται σε λογισμικό που υπολογίζει τις διαστάσεις καταμέτρησης κουτιών από μοτίβα που εξάγονται σε δυαδικές ψηφιακές εικόνες περιγραμμάτων, όπως το περιγράμμα φράκταλ που απεικονίζεται στην Εικόνα 1 ή το κλασικό παράδειγμα της ακτογραμμής της Βρετανίας που χρησιμοποιείται συχνά για να εξηγήσει τη μέθοδο εύρεσης μιας διάστασης καταμέτρησης κουτιών. Η στρατηγική προσομοιώνει την επανειλημμένη τοποθέτηση ενός τετραγωνικού κουτιού σαν να ήταν μέρος ενός πλέγματος που επικαλύπτεται στην εικόνα, έτσι ώστε το κουτί για κάθε $ϵ$ να μην επικαλύπτει ποτέ το σημείο στο οποίο βρισκόταν προηγουμένως (βλ. Εικόνα 4). Αυτό γίνεται έως ότου σαρωθεί ολόκληρη η περιοχή ενδιαφέροντος με κάθε $ϵ$ και καταγραφούν οι σχετικές πληροφορίες. Όταν χρησιμοποιείται για την εύρεση μιας διάστασης αριθμού κουτιών, η μέθοδος τροποποιείται για την εύρεση της βέλτιστης κάλυψης.

Σάρωση συρόμενου κουτιού

Μια άλλη προσέγγιση που έχει χρησιμοποιηθεί είναι ένας αλγόριθμος ολισθαίνοντος κουτιού, στον οποίο κάθε κουτί ολισθαίνει πάνω στην εικόνα επικαλύπτοντας την προηγούμενη τοποθέτηση. Το σχήμα 2 β απεικονίζει το βασικό μοτίβο σάρωσης με χρήση συρόμενου κουτιού. Η προσέγγιση του σταθερού πλέγματος μπορεί να θεωρηθεί ως αλγόριθμος συρόμενου κουτιού με τις προσαυξήσεις οριζόντια και κάθετα ίσες με $ϵ$. Οι αλγόριθμοι ολισθαίνοντος κουτιού χρησιμοποιούνται συχνά για την ανάλυση υφών στην ανάλυση λακωνικότητας και έχουν επίσης εφαρμοστεί στην πολυκλασματική ανάλυση.

Υποδειγματοληψία και τοπικές διαστάσεις

Η καταμέτρηση σε κουτιά μπορεί επίσης να χρησιμοποιηθεί για τον προσδιορισμό της τοπικής διακύμανσης σε αντίθεση με τα συνολικά μέτρα που περιγράφουν ένα ολόκληρο μοτίβο. Η τοπική διακύμανση μπορεί να εκτιμηθεί μετά τη συλλογή και την ανάλυση των δεδομένων (π.χ., ορισμένα λογισμικά κωδικοποιούν χρωματικά τις περιοχές σύμφωνα με τη διάσταση φράκταλ για κάθε υποδείγμα), αλλά μια τρίτη προσέγγιση της καταμέτρησης κουτιών είναι η μετακίνηση του κουτιού σύμφωνα με κάποιο χαρακτηριστικό που σχετίζεται με τα εικονοστοιχεία ενδιαφέροντος. Στους αλγορίθμους καταμέτρησης κουτιών τοπικής συνδεόμενης διάστασης, για παράδειγμα, το κουτί για κάθε $ϵ$ κεντράρεται σε κάθε εικονοστοιχείο ενδιαφέροντος, όπως απεικονίζεται στο Σχήμα 2 c.

Μεθοδολογικές εκτιμήσεις

Η εφαρμογή οποιουδήποτε αλγορίθμου καταμέτρησης κουτιών πρέπει να καθορίζει ορισμένες λεπτομέρειες, όπως τον τρόπο προσδιορισμού των πραγματικών τιμών στο $\mathrm{E}$, συμπεριλαμβανομένων των ελάχιστων και μέγιστων μεγεθών που θα χρησιμοποιηθούν και της μεθόδου αύξησης μεταξύ των μεγεθών. Πολλές τέτοιες λεπτομέρειες αντικατοπτρίζουν πρακτικά ζητήματα, όπως το μέγεθος μιας ψηφιακής εικόνας, αλλά και τεχνικά ζητήματα που σχετίζονται με τη συγκεκριμένη ανάλυση που θα πραγματοποιηθεί στα δεδομένα. Ένα άλλο ζήτημα που απασχόλησε έντονα είναι ο τρόπος προσέγγισης της λεγόμενης "βέλτιστης κάλυψης" για τον προσδιορισμό των διαστάσεων καταμέτρησης κουτιών και την αξιολόγηση της πολυκλασματικής κλιμάκωσης.

Εφέ άκρων

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

Μεγέθυνση μεγέθους κουτιού

Ο αλγόριθμος πρέπει να καθορίσει τον τύπο της αύξησης που θα χρησιμοποιηθεί μεταξύ των μεγεθών των κουτιών (π.χ. γραμμική έναντι εκθετικής), γεγονός που μπορεί να έχει βαθιά επίδραση στα αποτελέσματα μιας σάρωσης.

Προσανατολισμός πλέγματος

Όπως φαίνεται στο Εικόνα 4, η συνολική τοποθέτηση των κουτιών επηρεάζει επίσης τα αποτελέσματα της καταμέτρησης των κουτιών. Μια προσέγγιση από αυτή την άποψη είναι η σάρωση από πολλαπλούς προσανατολισμούς και η χρήση μέσων ή βελτιστοποιημένων δεδομένων.

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

Δείτε επίσης

• Αλγόριθμος διαμαντιού τετραγώνου
• Καμπύλη που γεμίζει το χώρο
• Νιφάδα του Κοχ
• Καμπύλη Χίλμπερτ
• Καμπύλη του δράκου
• Σπόγγος του Μένγκερ

• Σύνολο Μάντελμπροτ
• Σύνολο Julia
• Σύνολο Κάντορ
• Οικοδομήσιμο Σύμπαν