Αναγνώριση και ομαδοποίηση χρωμάτων σε φωτογραφίες

[Επισκέπτης]

Αυτό πάντως έπρεπε να το έχεις πει νωρίτερα γιατί ούτε γω καταλάβαινα τι θες μέχρι αυτή τη στιγμή.

 

Άρα λοιπόν αυτό που θες είναι αλγόριθμο για να βρίσκεις πόσα και ποιά είναι αυτά τα χρώματα, μετά η ποσόστωση είναι trivial.

 

Αυτό δεν είπα από την αρχή; «Προσπαθώ να φτιάξω ένα πρόγραμμα που να αναγνωρίζει και να ομαδοποιεί χρώματα σε μια φωτογραφία.»

 

Έχω πει ποιοι είναι οι παράμετροι της λύσης. Το LAB space και το color distance με τον αλγόριθμο CIE 2000. Αλλά αυτό είναι εξαιρετικά χρονοβόρο οπότε χρειάζομαι έναν τρόπο να το συντομεύσω, αν υπάρχει τρόπος. Τι θα γίνει αν η εικόνα έχει 20 όμοια χρώματα; Θα μου πει ότι έχει 100% μπλε/πράσινο/οτιδήποτε.

 

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

[defacer]

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

 

Τι διαφορετικό λέμε; Ότι εσύ λες "ομαδοποιεί" σα να ήταν κάτι που ορίζεται μονοσήμαντα, ενώ εγώ ζητάω να το συγκεκριμενοποιήσεις. Το ποιά θα είναι τα κριτήρια που θα χρησιμοποιεί ο αλγόριθμος το είπες. Το πώς θα τα χρησιμοποιεί δεν είπες. Ο όποιος αλγόριθμος κάπως θα πρέπει να αποφασίζει π.χ. αν είναι προτιμητέο να αυξήσει τον αριθμό των reference colors ή να αυξήσει το tolerance ομαδοποίησης. Τέτοια πράγματα δεν τα έχεις πει καθόλου, και αποτελούν 100% μέρος της διατύπωσης του προβλήματος.

[M2000]

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

 

Πες πως έχεις ένα αρχείο π.χ. φωτογραφία σε RGB  και ένα μοντέλο Ν χρωμάτων C1...CN. Προφανώς πρέπει να ορίσεις τη συνάρτηση που το RGB το κάνει σε αυτό το μοντέλο με το κάθε χρώμα C1...CN, να λέει πόσο έχει από το καθένα. Για να δεις αν δουλεύει το σύστημα θα πρέπει να φτιάξεις την ανάποδη συνάρτηση να δίνεις τα χρώματα C1... CN..Οπότε αφού έχεις και την F(r,g,b ) που δίνει τα C1...CN και την F'(C1, C2,..CN) που δίνει τα RGB έχεις κάνει το πρώτο βήμα.

Πες λοιπόν ότι υπάρχουν όλα αυτά!

Τώρα πες μου πώς θα ομαδοποιείς; Θα λες ότι όποιο χρώμα έχει περισσότερο το C1 θα πηγαίνει στα C1 χρώματα;

[Επισκέπτης]

Υπάρχει ένας αλγόριθμος που λέγεται CIE 2000 και δίνει την απόσταση δύο χρωμάτων. Όπου απόσταση ένας αριθμός με δεκαδικό. Όσο πιο μικρή η απόσταση τόσο πιο κοινά τα χρώματα. Υπάρχει επίσης το LAB space που διαχωρίζει τα χρώματα πολύ πιο αποτελεσματικά από ότι το RGB. Με βάση το LAB space βγαίνει ένα reference το οποίο αποτελεί ένα υποσύνολο των συνολικών χρωμάτων με το οποίο συγκρίνεις κάθε χρώμα για να το ομαδοποιήσεις. Το reference έχει περί τα 200.000 χρώματα ομαδοποιημένα το πολύ σε διακόσια που ανάλογα με τα γούστα του ο καθένας μπορεί να το ομαδοποιήσει κι άλλο (βάζεις ας πούμε το φούξια και το μωβ να είναι ένα χρώμα). Αλλά επειδή το reference έχει καμιά διακοσαριά χιλιάδες χρώματα και το CIE 2000 είναι ένα μακρινάρι με δεκάδες υπολογισμούς, για μισό εκατομμύριο pixels όλη αυτή η διαδικασία είναι αρκετά χρονοβόρα. Οπότε εδώ χρειάζεται ένα επιπλέον βήμα το οποίο αγνοώ.

 

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

[defacer]

Μου φαίνεται θέλεις βοήθεια αλλά δεν τη θέλεις και πολύ.

 

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

 

 

 

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

 

 

 

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

[M2000]

http://stackoverflow.com/questions/3114925/pil-convert-rgb-image-to-a-specific-8-bit-palette

 

μια άλλη προσέγγιση είναι να κάνει μετατροπή από rgb σε adaptive παλέττα!

[Επισκέπτης]

Έχω κολλήσει με το LAB και το CIE γιατί αυτό έχω υλοποιήσει ρε παλικάρι. Αν έχεις κάτι διαφορετικό να προτείνεις πολύ ευχαρίστως να το ακούσω. Έχεις; Γιατί εκτός από το να μου επιτίθεσαι χωρίς λόγο δεν έχεις προτείνει το παραμικρό τόση ώρα που μιλάμε. Δεν σ’ αρέσει η υλοποίηση μου; Κανένα πρόβλημα, πες μου τι έχεις να προτείνεις. Αλλιώς τι συζητάμε ρε παιδιά;

 

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

 

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

[defacer]

Καταλαβαίνεις ότι θα μπορούσες να αλλάξεις την υλοποίησή σου του CIE με το παρακάτω

int cie_value(....) {
    return 5;
}

και όσον αφορά τον αλγόριθμο που ψάχνεις αυτό δε θα είχε καμία σημασία;

 

Anyway, εγώ ολοκλήρωσα σ' αυτό το thread. Καλό ξεμπέρδεμα.

[kagelos]

Έστω ότι το color space έχει πεπερασμένο αριθμό χρωμάτων (που μάλλον έχει, και είναι υποσύνολο των χρωμάτων του (s)RGB)

 

Ιδέα: Υπολογίζεις την απόσταση κάθε του κάθε χρώματος από όλα τα άλλα και το κρατάς σε ένα αρχείο. Έτσι για κάθε μελλοντικό query η πολυπλοκότητα είναι O(1). Δεν ξέρω πόσο πρακτικό είναι να φτιάξεις ένα τέτοιο προεπεξεργασμένο αρχείο βέβαια. Αν υποθέσουμε ότι τα χρώματα είναι 2^24, θα καταλήξεις με ένα index που θα έχει 2^48 εγγραφές. Αν πούμε χοντρικά ότι κάθε εγγραφή είναι 8 byte, το index θα είναι 2048TB

 

"Βελτιστοποίηση" του παραπάνω θυσιάζοντας ακρίβεια θα ήταν να ορίσεις 1000 π.χ. βασικά χρώματα και να υπολογίσεις την απόσταση όλων των χρωμάτων από αυτά τα 1000. Οπότε τελικά το index θα είχε 2^24 * 1000.

[Επισκέπτης]

Ήθελα να 'ξερα τα διαβάζεις αυτά που γράφω ή απλά λες αυτά που θες να πεις μόνο και μόνο για να κάνεις εντύπωση; Το CIE σου δείχνει πόσο κοντά είναι δύο χρώματα. Το εξήγησα ξανά και ξανά, έδωσα και παραπομή. Αυτή η παπάρα που έγραψες που επιστρέφει ένα τυχαίο νούμερο τι ακριβώς δείχνει; Ότι κατά τη γνώμη σου υπάρχει κάποιος άλλος μαγικός τρόπος να βρεις τι σχέση έχουν δύο χρώματα;

 

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

[kagelos]

Άλλη ιδέα πάλι προεπεξεργασμένου αρχείου είναι να φτιάξεις ένα Octree που θα πετάξεις μέσα πάλι όλα τα χρώματα (ας πούμε ότι είναι συνολικά 2^24). Αφού κατασκευάσεις αυτό το αρχείο, μπορείς να κάνεις στη συνέχεια να κάνεις N nearest neigbours πολύ εύκολα.

Για το Octree τα components σου αντί για XYZ θα είναι Lab.

[Επισκέπτης]

Έστω ότι το color space έχει πεπερασμένο αριθμό χρωμάτων (που μάλλον έχει, και είναι υποσύνολο των χρωμάτων του (s)RGB)

 

Ιδέα: Υπολογίζεις την απόσταση κάθε του κάθε χρώματος από όλα τα άλλα και το κρατάς σε ένα αρχείο. Έτσι για κάθε μελλοντικό query η πολυπλοκότητα είναι O(1). Δεν ξέρω πόσο πρακτικό είναι να φτιάξεις ένα τέτοιο προεπεξεργασμένο αρχείο βέβαια. Αν υποθέσουμε ότι τα χρώματα είναι 2^24, θα καταλήξεις με ένα index που θα έχει 2^48 εγγραφές. Αν πούμε χοντρικά ότι κάθε εγγραφή είναι 8 byte, το index θα είναι 2048TB

 

"Βελτιστοποίηση" του παραπάνω θυσιάζοντας ακρίβεια θα ήταν να ορίσεις 1000 π.χ. βασικά χρώματα και να υπολογίσεις την απόσταση όλων των χρωμάτων από αυτά τα 1000. Οπότε τελικά το index θα είχε 2^24 * 1000.

 

Η ιδέα σου είναι πολύ κοντά σε αυτό που έχω κάνει. Το reference που χρησιμοποιώ έχει 200.000 χρώματα που αντιστοιχούν περίπου στο 1,2% του color space. Αλλά φοβάμαι ότι αν το κόψω θα αρχίσω να χάνω χρώματα. Άλλη λύση είναι να μειώσω τις διαστάσεις τις φωτογραφίας δραματικά (ας πούμε 80+%) αλλά κι εκεί μπορεί να χάσω χρώματα. Και βέβαια υπάρχει και η πάγια πρακτική όταν δεν μπορείς να βελτιώσεις τον κώδικα να αγοράζεις καλύτερο hardware

 

Τεσπά, είμαι ανοιχτός σε ιδέες.

[kagelos]

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

 

EDIT

Παρόλα τα παραπάνω, ίσως τελικά η ιδέα με το Octree να αξίζει μια δοκιμή:

 

1) Φτιάξε ένα Octree που θα βάλεις όλα τα χρώματα μέσα με components L,a,b

 

Για την αναζήτηση των κοντινότερων εντός απόστασης D από ένα χρώμα Lx,ax,bx:

2) Όρισε ένα μικρό κουτί με καρφωτές διαστάσεις Lk,ak,bk και κέντρο Lx,ax,bx

3) Βρες όλα τα χρώματα στο Octree που είναι εκεί μέσα

4) Για κάθε ένα υπολόγισε την computationally expensive απόσταση και ταξινόμησε τα με αυτήν

 

Αυτό θα δουλέψει πολύ καλά εάν υπάρχει έστω και χοντρική σχέση μεταξύ της ευκλείδειας απόστασης και της απόστασης dE2000.

 

Δηλαδή αν ισχύει το εξής παντού και πάντα (ή έστω 99% των περιπτώσεων):

Αν euclidean_distance(colorA, colorB) < euclidean_distance(colorA, colorC)

τότε και dE2000(colorA, colorB) < dE2000(colorA, colorC)

 

Αν όχι, μην το δοκιμάζεις καν.

 

Αν όντως πας σε Octree, υπάρχει και K nearest neighbours αλγόριθμος χωρίς να πρέπει να ορίσεις κουτί. Θέλει πάλι όμως ευκλείδεια απόσταση.

[Επισκέπτης]

ΟΚ καλό ακούγεται, αν και δεν το κατάλαβα πλήρως. Thanks a million

[παπι]

Γραψτο στη gpu τι το βασανιζεις. Οι επιδώσεις σε αυτό τον " τομέα" είναι χ1000-10κ