Instagram Engineering Challenge: The Unshredder

[GKNSB]

Πριν κάποιο καιρό το instagram, μια από τις πιο γνωστές υπηρεσίες για photo sharing σε iphone ειδικά, κοινοποίησε το παρακάτω challenge.

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

 

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

Οι συμμετοχές είναι ακόμα ανοιχτές αν κάποιος θέλει να λάβει και μέρος.

 

http://instagram-eng...ing.tumblr.com/

 

Για πάμε ιδέες

[Directx]

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

[gallaki]

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

 

Αλλά δεν νομίζω έτσι να μπορείς να τα βάλεις σε σειρά :/ Έχετε καμια ιδέα πως λύνεται?

[GKNSB]

Το δικό μου σκεπτικό είναι κάπως έτσι:

 

Παίρνεις την αρχική εικόνα και την τεμαχίζεις σε εικονες/λωρίδες ανά όσα pixels ξέρεις πως είναι η κάθε λωρίδα. 32 λέει ότι είναι στην προκειμένη.

Για κάθε λωρίδα, τσεκάρεις τα pixels της 32ης στήλης, να ταιριάζουν με τα pixels της 1ης κάποιας άλλη λωρίδας.

Κάθε φορά που βρίσκεις match, τις φέρνεις δίπλα δίπλα.

Κάποιας λωρίδας, τα pixels της πρώτης στήλης δε θα ταιριάζουν με κανένα γιατί θα είναι η τέρμα αριστερά, το ίδιο και για την 32η στήλη κάποιας άλλης λωρίδας που θα είναι η τέρμα δεξιά

Αφού έχεις βάλεις τις εικόνες λωρίδες σε μία σειρά τις ενώνεις σε μία.

 

 

Για το extra challenge:

 

Το έξτρα είναι αν δεν ξέρεις το πλάτος των λωρίδων.

Σε αυτή την περίπτωση σκέφτηκα να πιάνεις την εικόνα του input (την μπερδεμένη) και να την κόβεις

πρώτα σε 2 μετά σε 3, σε 4 κλπ λωρίδες, και για κάθε μία περίπτωση να κάνεις τους ελέγχους του αρχικού challenge.

Προφανώς, θα έχεις τον σωστό αριθμό λωρίδων όταν ικανοποιηθεί η συνθήκη - τα pixel πρώτης στήλης μίας λωρίδας και της τελευταίας στήλης μιας άλλης είναι τα μόνα που δεν ταιριάζουν και όλα τα υπόλοιπα ταιριάζουν. Δεδομένου πάντα ότι οι λωρίδες έχουν το ίδιο πλάτος απλά δεν ξέρεις πόσο είναι αυτό, δηλαδή σε πόσα κομμάτια διαιρείται το αρχικό πλάτος της εικόνας, απλά δοκιμάζεις για πολλά διαφορετικά από 1 μέχρι το συνολικό πλάτος της εικόνας πχ 1280 pixels.

 

Πως σας ακούγονται?

[xlomo]

Υποθέτω πως το πρόβλημα είναι να ανακτήσεις την αρχική εικόνα, αν την έχεις ήδη τότε γιατί να παιδέυεσαι για να την καταστρέψεις και να την ξανακολήσεις ?

[gallaki]

Το δικό μου σκεπτικό είναι κάπως έτσι:

 

Παίρνεις την αρχική εικόνα και την τεμαχίζεις σε εικονες/λωρίδες ανά όσα pixels ξέρεις πως είναι η κάθε λωρίδα. 32 λέει ότι είναι στην προκειμένη.

Για κάθε λωρίδα, τσεκάρεις τα pixels της 32ης στήλης, να ταιριάζουν με τα pixels της 1ης κάποιας άλλη λωρίδας.

Κάθε φορά που βρίσκεις match, τις φέρνεις δίπλα δίπλα.

Κάποιας λωρίδας, τα pixels της πρώτης στήλης δε θα ταιριάζουν με κανένα γιατί θα είναι η τέρμα αριστερά, το ίδιο και για την 32η στήλη κάποιας άλλης λωρίδας που θα είναι η τέρμα δεξιά

Αφού έχεις βάλεις τις εικόνες λωρίδες σε μία σειρά τις ενώνεις σε μία.

 

 

Για το extra challenge:

 

Το έξτρα είναι αν δεν ξέρεις το πλάτος των λωρίδων.

Σε αυτή την περίπτωση σκέφτηκα να πιάνεις την εικόνα του input (την μπερδεμένη) και να την κόβεις

πρώτα σε 2 μετά σε 3, σε 4 κλπ λωρίδες, και για κάθε μία περίπτωση να κάνεις τους ελέγχους του αρχικού challenge.

Προφανώς, θα έχεις τον σωστό αριθμό λωρίδων όταν ικανοποιηθεί η συνθήκη - τα pixel πρώτης στήλης μίας λωρίδας και της τελευταίας στήλης μιας άλλης είναι τα μόνα που δεν ταιριάζουν και όλα τα υπόλοιπα ταιριάζουν. Δεδομένου πάντα ότι οι λωρίδες έχουν το ίδιο πλάτος απλά δεν ξέρεις πόσο είναι αυτό, δηλαδή σε πόσα κομμάτια διαιρείται το αρχικό πλάτος της εικόνας, απλά δοκιμάζεις για πολλά διαφορετικά από 1 μέχρι το συνολικό πλάτος της εικόνας πχ 1280 pixels.

 

Πως σας ακούγονται?

 

Τι ορίζεις οτι μοιάζουνε, αν δεις στον ουρανό οι περισσότερες είναι ίδιες, και αν πχ τύχει να κόψεις ένα κτήριο στο τέλος του, το τέλος της λωρίδας δεν θα μοιάζει με την αρχή του επόμενου, μπορείς πχ να τις ενώνεις μόνο εάν πάνω απο 80% των πιξελ μοιάζουν , αλλά πως θα ορίσουμε το μοιάζουν?

Εάν έχουν το ίδιο rgb? ή αν τα χρώματα είναι κοντινά? Γιατί μου φαίνεται λίγο απίθανο δύο διπλανά pixel να είναι ίδια.

 

Μπορείς ίσως απο τα pixel να βρίσκεις εναν μέσο όρο απο το rgb πχ 3 χ 3 και να το συγκρίνεις με τον απέναντι μεσο όρο 3χ3 πίξελ. δηλαδή να παίρνεισ 30 - 31 - 32 στήλη και 1 - 2 - 3 σειρά να βρίσκεις έναν μέσο όρο και μετά στην επόμενη λωρίδα 1 - 2 - 3 στήλη και 1 - 2 - 3 σειρά και να τα συγκρίνεις.

 

Δεν ξέρω κατα πόσο θα δώσει καλό αποτέλεσμα αυτό αλλα νομίζω οτι θα έχεις μια πιό γενική εικόνα απότι αν συγκρίνεις πιξελ - πιξελ.

[migf1]

...

Για κάθε λωρίδα, τσεκάρεις τα pixels της 32ης στήλης, να ταιριάζουν με τα pixels της 1ης κάποιας άλλη λωρίδας.

Κάθε φορά που βρίσκεις match, τις φέρνεις δίπλα δίπλα.

...

 

Αυτό είναι το βασικό challenge και προσωπικά δεν γνωρίζω κάποιον trivial τρόπο για αυτό το "ταίριασμα". Ούτε non-trivial ξέρω, αλλά υποθέτω όσοι εξειδικεύονται στο image processing θα το έχουν λυμένο το θέμα. Ένα πρόχειρο googling με οδήγησε εδώ: http://mklab.iti.gr/...pdf/sspit04.pdf

[GKNSB]

@migf1

Ε δεν νομίζω ότι περιμένουν μια τόσο εξειδικευμένη λύση.

Κάπου αναφέρουν μάλιστα ότι δεν τους νοιάζει κιόλας αν δεν δουλεύει σε όλες τις περιπτώσεις.

Ότι η λύση δεν θα δουλεύει για όλες τι περιπτώσεις είναι το μόνο σίγουρο γι'αυτό και δίνουν πολύ συγκεκριμένο input.

 

@gallaki

κάτι τέτοιο σκεφτόμουν κι εγώ να ελέγχεις και όταν βρεις ένα match να βλέπεις αν ισχύει για το 80 - 90%

 

@xlomo

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

η λογική μου βασίζεται στο "κάνε δοκιμαστικά κοψίματα στην μπερδεμένη μέχρι να προκύψουν τα σωστά κομμάτια"

 

 

Κανείς που να μη βαριέται να υλοποιήσει μια λύση? Προσωπικά βαριέμαι αρκετά να γράψω κώδικα τώρα και δεν ξέρω και από image processing libraries

[migf1]

...

Προσωπικά βαριέμαι αρκετά να γράψω κώδικα τώρα και δεν ξέρω και από image processing libraries

Ομοίως κι εγώ

 

ΥΓ. Σας έχω όμως άλλο θέμα αν θέλετε να ασχοληθείτε (το σκεφτόμουν την Κυριακή, αλλά δεν έβγαλα ακόμα άκρη.. το υποτίμησα... έχει να κάνει με την brute force υλοποίηση της τρίλιζας, θα ανοίξω νέο νήμα )

[παπι]

haha γαματο. Για να δουμε, θα τα καταφερω ;

[GKNSB]

haha γαματο. Για να δουμε, θα τα καταφερω ;

 

Ωραίος, δοκίμασε και περιμένουμε το source.

Θα την δοκιμάσω κι εγώ κάποια στιγμή τη λύση και θα την ποστάρω.

 

 

PS. σε τι γλώσσα λες να το δουλέψεις?

[παπι]

Σε c++/winapi. Τωρα εχω κολλησει με το χωρισμα, κοντα μεν αλλα δεν.

http://www.youtube.com/watch?v=_wa8K05yyeY

 

[migf1]

Ωραίος!

 

Πως επιχειρείς να ταιριάξεις τα pixels τελικά;

[παπι]

Ωραίος!

 

Πως επιχειρείς να ταιριάξεις τα pixels τελικά;

 

Κατσε να το χωρισω πρωτα και μετα βλεπουμε

[GKNSB]

Ωραίος! Καλύτερα άσε αυτό το κομμάτι. Να δούμε το ταίριασμα.

Το κόψιμο χωρίς να ξέρεις το μέγεθος είναι extra challenge

 

Επίσης και στο κόψιμο, κάθε λωρίδα θα έχει έτσι κι αλλιώς το ίδιο πλάτος με όλες τις άλλες

απλά δεν θα το ξέρουμε εμείς και καλά.