Deckard es un replicante

J’ai participé il y a deux semaines de cela à un petit challenge d’algorithmie lancé par Instagram, mais si vous savez, le réseau social aux teintes polaroids. Pour ceux qui ont la flemme d’aller sur leur blog, voici visuellement en quoi le challenge consiste.

Le but du jeu était à partir d’une image découpée en segments et réarrangée aléatoirement, de retrouver l’ordre original en régénérant l’image. L’analogie était faite avec un broyeur de documents qui découpe les feuilles de papier en des lamelles de tailles égales.

On voit bien les lamelles ici.

Après un peu de sang et de larmes, on arrive à cela.

Il se trouve que j’ai été sélectionné dans le groupe A (le groupe des winners mesdames et monsieurs). Je vais donc recevoir un superbe t-shirt, et pour la peine ça mérite un article.

Voici comment je m’y suis pris.

Je choisis une lamelle de l’image (dans les faits, la première à gauche mais cela n’a pas d’impact sur l’algorithme). Je cherche la lamelle à sa droite parmi toutes les autres. Pour ce faire je compare le bord droit de ma première lamelle avec le bord gauche de l’autre. Comparer un bord veut dire comparer pour une même hauteur le pixel de gauche et de droite.

for y in range(self.source_image.size[1]):
    # compare left pixel and right pixel with tolerance
    pixel_left = shred_left.get_right_pixels(y)
    pixel_right = shred_right.get_left_pixels(y)

    # score is a flat number (clarity)
    score += abs(pixel_left[0] - pixel_right[0])
    + abs(pixel_left[1] - pixel_right[1])
    + abs(pixel_left[2] - pixel_right[2])
    + abs(pixel_left[3] - pixel_right[3])

Dans les deux premières lignes, je récupère les pixels des bords. Je lis mon image en RGBA (Red, Green, Blue, Alpha). Ceci veut dire que chaque pixel est représenté par 4 valeurs, les 3 couleurs et sa transparence.

Ainsi, si deux pixels sont semblables, la soustraction de l’un avec l’autre devrait tendre vers 0.

Pour chaque pixel comparé, j’en retire un score (soustrayant chaque composante ensemble et en les sommant pour passer d’un vecteur à un scalaire).  Je n’oublie pas d’en tirer à chaque fois la valeur absolue pour ne pas fausser le résultat.

Ainsi, si deux pixels sont proches, leur soustraction tend vers 0, donc leur score sera petit. Ayant comparé toutes les lamelles entre elles, la bonne voisine est celle qui a le score le plus bas. Et ainsi de suite.

Cette approche m’a permis de réunifier avec quelques erreurs le dessin du dessus. Lorsque dans le commentaire du code je précise “with tolerance”, cela veut dire que je n’ai pas réellement comparé deux pixels entre eux. Et oui j’ai menti. Regardons le code des “get_left_pixels” (le code pour le pixel de droite est identique).

def get_left_pixels(self, y):
    """
    Given a height, get the average left pixel.

    """

    pixels = []

    for i in range(0, self.magic_average):
       pixels.append(self.get_pixel_value(self.x + i, y))

    average_pixel = reduce(self.get_average_pixel, pixels)

    return average_pixel

Au lieu de récupérer un seul pixel, je moyenne un nombre de pixels donné sur la même ligne (le nombre de pixels étant symbolisé par magic_average). La moyenne est effectuée par “get_average_pixel” et aidée d’un reduce parce que moi aussi je connais la programmation fonctionnelle, non mais. J’ai déterminé ce magic number de manière très empirique et sa valeur est trois. Point. Plus, vous augmentez les erreurs, moins, ce n’est pas assez. Tout simplement.

Vous vous dites, tu es sympa coco, ton article bien long, il commence à me fatiguer (ou bien tu t’es déjà arrêté de lire mais tu programmes surement en Java). Et bien ce serait dommage de s’arrêter de lire maintenant car l’algorithme ne résout pas encore le problème. Paradoxalement c’est la partie sur laquelle j’ai passé le plus de temps.

Pour l’instant, nous sommes incapables de déterminer la première lamelle de la dernière !

Et oui, le début n’est pas au début et la fin n’est pas à la fin, comme si l’image avait été coupée en deux. Naïvement je pensais qu’en conservant tous les scores et en choisissant comme début et fin les deux lamelles qui avaient eu le score le plus improbable (donc le plus haut) seraient les deux bords. A priori, les bords n’ayant pas de voisin par définition, le côté trouvé doit vraiment avoir un score haut. Et bien pas du tout. Et oui j’étais aussi déçu que vous.

J’ai donc fait ça.

while(len(self.shred_ordered) < len(self.shred_list) and loop):
    # search neighbor while all shred are not ordered
    current_shred = local_find(shred)

    # must not be possible
    assert(current_shred not in self.shred_ordered)

    if seek_right:
        # check if it is a good fit with its left side
        left_shred = self.find_left(current_shred)

        if left_shred.x != shred.x:
             # it is the right border
             loop = False

Je lance l’algorithme pour rechercher tous les voisins de droite successifs des lamelles. Pour m’assurer que ce n’est pas un bord, je cherche aussi à voir si le voisin de gauche de la lamelle potentiellement voisine de droite (vous suivez ?) est bien la même. Sinon, c’est un bord. Dans le code cela se caractérise par la dernière condition où je compare les abscisses des deux lamelles (j’identifie les lamelles par leurs abscisses du point en haut à gauche). “local_find” est dans l’exemple un pointeur de fonction sur “find_right”, ceci m’a permis de factoriser le code pour permettre la recherche à gauche et à droite dans la même fonction (symbolisé par le booléen seek_right).

Juste pour la beauté du geste, j’utilise une liste pour stocker les lamelles ordonnées (“shred_ordered”). Voici l’algorithme à son plus haut niveau d’abstraction.

# peek the first shred to start
self.shred_ordered.append(self.shred_list[VAR_START_WITH])
# order from left to right
self.order_shred(True, self.shred_ordered[-1])
# reverse to order from right to left
self.shred_ordered.reverse()
self.order_shred(False, self.shred_ordered[-1])
# reverse again to get the original order
self.shred_ordered.reverse()

Je renverse juste l’ordre de la liste avant de changer le sens de la recherche. Finalement je renverse une dernière fois cette liste afin qu’elle soit correctement lue par la fonction de sauvegarde de l’image ordonnée (sinon l’image aurait eu un effet miroir assez dérangeant).

Voilà, je me suis bien amusé et vous ?

Le code source de la chose est disponible sur mon github -> c’est par là et ça s’appelle Shreddator !