Tintin et les 18'068 Cases

PUBLISHED ON JUL 16, 2020

Préambule

Il y a plusieurs mois de cela, j’ai commencé à travailler dans mon temps libre sur un projet de grande envergure : un système complet de création et de correction de QCM “papier” (questionnaires à choix multiple), avec mélange automatique des questions et des réponses. Je caressais l’espoir de le proposer ensuite à mon employeur, l’Université de Genève (qui ne m’avait rien demandé et aurait très probablement refusé, ne serait-ce que parce qu’il aurait fallu procéder par un appel d’offres), en remplacement du système (laborieux et antique) actuellement utilisé par elle.

Le COVID-19 a signé l’arrêt de mort du projet. Il était évident que la pandémie allait précipiter la migration de l’Université vers des examens entièrement informatisés, s’affranchissant de l’étape intermédiaire du papier. Certes, l’on aurait pu penser qu’une fois la première (ou seconde, ou troisième) vague passée, l’on reviendrait à des documents imprimés et distribués en auditoire (ce qui présente l’avantage notable d’un risque de fraude assez faible), et à ce jour rien n’a été décidé quant à la forme que suivraient à l’avenir les examens de la Faculté, mais je ne voulais pas prendre le risque de persister dans mon hubris face au risque grandissant de travailler dans le vide.

Toujours est-il que les quelques mois que j’ai consacrés au projet (qui était pratiquement utilisable) n’ont pas servi à rien, puisqu’ils furent entre autres l’occasion de me familiariser avec une bibliothèque logicielle bien pratique, OpenCV. J’ai donc décidé d’utiliser les connaissances acquises à des fins plus ludiques, à savoir, évidemment, extraire les 18'096 cases des 1'424 planches des 23 albums de Tintin.

Pour des raisons évidentes de droit d’auteur, je ne peux pas partager le résultat final, mais je tâcherai d’illustrer cet article avec modération, en espérant bénéficier de la clémence du léviathan Moulinsart SA.

Note : j’utilise le portage python de la bibliothèque OpenCV, mais les principes sont applicables mutatis mutandis à la version originale.

But et limites

Le but est de transformer une image en entrée (un scan d’une planche de Tintin) en une série d’images en sortie (une image par case).

La forme de ces petites images doit reprendre la forme exacte de la case. En effet, toutes les cases ne sont pas rectangulaires, il arrive par exemple qu’un phylactère dépasse des limites de la case, ce qui donne à l’un de ses bords un aspect irrégulier. Dans un tel cas, l’image doit représenter la case, entourée d’un fond transparent. En d’autres termes, tout ce qui correspond à du blanc “de fond de page” doit être transparent.

Une case bien détourée, telle qu'affichée dans une visionneuse d'images

En outre, les images doivent être numérotées dans l’ordre de leur lecture par un humain, ce qui n’est pas aussi intuitif qu’il y paraît.

Il s’est rapidement avéré qu’il serait très difficile de paramétrer le programme de façon à obtenir un résultat parfait, systématiquement. En particulier, certaines cases ne correspondent pas à la “grammaire visuelle” habituellement suivie par Hergé.

Cela peut être dû à un effet de style, comme les phylactères des vocalises de la Castafiore qui courent sur le strip entier et rendent donc impossible la délimitation “naïve” des cases en fonction de leur totale séparation par du blanc :

Cela peut être dû aussi au manque d’expérience d’Hergé, qui (dans les Soviets uniquement) se lançait dans le dessin d’une case sans calculer à l’avance l’espace dont il aurait besoin pour son contenu, si bien que les cases finissent par se toucher  :

Le fin espace entre les phylactères, s’il peut sembler blanc, est en fait plutôt gris, et ne serait considéré comme blanc qu’au prix d’une modification topique des paramètres du programme.

Le fin espace entre les phylactères, s’il peut sembler blanc, est en fait plutôt gris, et ne serait considéré comme blanc qu’au prix d’une modification topique des paramètres du programme.

Cela peut être dû enfin à une mauvaise impression et/ou un mauvais scan. Si des petits trous peuvent être “bouchés” automatiquement au moyen des opérations morphologiques fournies par OpenCV, ça n’est pas le cas de fossés béants :

Une case dont la bordure supérieure est trouée.

Une case dont la bordure supérieure est trouée.

Pour toutes ces raisons, il a fallu opter pour un système semi-automatique. Une bonne partie du travail s’appuie donc sur le visionnage “humain” du résultat prévu, et sur son éventuel affinage au moyen de corrections topiques (qui varient d’une planche à l’autre). Dans quelques rares cas, et toujours afin d’éviter que le code ne se spécialise au point de devenir incompréhensible, il a même fallu modifier les images originales “à la main”, par exemple pour procéder à la diérèse de deux cases siamoises au moyen d’une ligne de pixels blancs, ou au contraire pour appliquer une prothèse de pixels noirs sur une bordure (trop) discontinue.

Traitement de la planche

L’image est tout d’abord chargée, en faisant abstraction d’un éventuel canal de transparence (IMREAD_COLOR), qui n’aurait pas de sens à ce stade (plus tard, au moment de la “découpe” finale de la case, je forcerai l’ajout d’un canal de transparence) :

original = cv2.imread(file, cv2.IMREAD_COLOR)

À titre liminaire, l’image est redimensionnée vers une taille standard, afin de pouvoir au besoin recourir à des mesures en pixels, qui n’auraient pas de sens si l’image était de taille variable. Cela ne fonctionne qu’à la condition que toutes les images traitées aient (à peu près) le même ratio hauteur/largeur, comme c’est le cas en l’espèce, les planches étant toutes des documents A4 (dont la taille précise dépend de la densité utilisée pour leur scan).

resized = cv2.resize(original, (1200, 1800))

Les premières étapes du traitement d’une image avec OpenCV sont bien souvent les mêmes : il s’agit de simplifier l’image afin de rendre possible son traitement.

En particulier, les couleurs ne sont en l’espèce d’aucune utilité, l’image peut donc être convertie en nuances de gris :

gray = cv2.cvtColor(resized, cv2.COLOR_BGR2GRAY)

Cette étape ne se contente pas d’appliquer une sorte de “filtre”, comme le ferait un logiciel de retouche photo. Elle simplifie la structure même de l’image afin que chaque pixel soit représenté par un unique canal, qui pourra prendre une valeur comprise entre 0 et 255. L’on passe donc de 3 canaux d’un octet (mode forcé par l’argument cv2.IMREAD_COLOR lors de la lecture de l’image) à 1 canal d’un octet.

J’en profite au passage pour créer une autre version de l’image, qui me servira au monitoring du résultat, c’est-à-dire au contrôle visuel de l’exactitude de la détection des bordures des cases d’une part, et de l’ordre de numérotation des cases d’autre part. Dans cette version de l’image, la planche en elle-même sera en nuances de gris, et les marqueurs temporaires (bordures des cases et numéros) seront en couleur, afin de ressortir le plus nettement possible. C’est pour cette raison qu’il convient de transformer à nouveau l’image vers une image en couleurs (cette étape ne recrée évidemment pas les couleurs, mais à son terme chaque pixel est à nouveau représenté par 3 canaux d’un octet, ce qui permettra à terme de venir y “peindre” avec de la couleur) :

monitor = cv2.cvtColor(gray, cv2.COLOR_GRAY2BGR)

Note : utiliser un tableau numpy n’a rien d’artificiel, le portage python d’OpenCV utilise nativement des tableaux numpy pour stocker les images, ce qui rendra triviale l’opération consistant à combiner ce canal et les trois autres canaux pour obtenir l’image finale.

C’est tout, s’agissant de l’image de monitoring.

L’opération suivante consiste à simplifier encore davantage l’image principale (actuellement en nuances de gris), afin d’en faire une image binaire, c’est-à-dire une image réduite à sa forme la plus simple possible : chaque pixel est soit noir, soit blanc :

threshold, binary = cv2.threshold(gray, 220, 255, cv2.THRESH_BINARY)

L’argument fondamental ici est thresh, fixé en l’espèce (et de façon empirique) à 220. La valeur exacte n’a pas une grande importance, 210 ou 230 fonctionneraient probablement. Tout pixel (de l’image en nuances de gris) d’une valeur strictement supérieure à ce seuil vaudra maxval, en l’espèce 255 (blanc pur). Tout pixel inférieur ou égal au seuil vaudra 0. La bande dessinée étant imprimée sur du papier blanc, on peut se permettre d’opter pour un seuil très proche du blanc, ici 220. Cela pourrait cependant poser problème en cas de papier “sale”, avec des taches légèrement plus foncées, mais ça n’était pas un problème en l’espèce.

Note : l’algorithme d’Otsu peut être employé à cette étape, en indiquant cv2.THRESH_BINARY+cv2.THRESH_OTSU comme dernier argument ; la fonction threshold trouve alors toute seule le seuil qui minimise la variance intra-classe, autrement dit qui fait faire le moins de “chemin” possible aux pixels entre leur valeur initiale et leur nouvelle valeur, bref le seuil le plus naturel et le plus “central” possible. Cela peut sembler parfait, mais dans un cas où le contenu intéressant est de toute façon nettement séparé du fond de page, comme c’est le cas avec des documents papier, des formulaires, etc., il est plus simple (et moins coûteux en termes de calculs) d’opter pour un seuil fixe et élevé (proche du blanc pur).

Cette simplification rend possibles les étapes subséquentes, qui agissent “pixel par pixel” : détection de bords, fermeture des petits trous, etc.

L’étape suivante consistera en l’application éventuelle d’une opération de transformation morphologique sur l’image. Cela requiert tout d’abord d’inverser l’image, car ces opérations exigent que le trait soit blanc sur un fond noir (cela peut sembler “inversé” par rapport à un document papier, mais c’est en réalité davantage correct s’agissant de manipulations d’images : le noir correspondant à une valeur de zéro, il est logique que le fond, absence de contenu, soit noir, et que le trait, présence “accidentelle” de contenu, soit blanc) :

inverted = cv2.bitwise_not(binary)

Un paramètre global, morph, qu’il est possible de faire varier en fonction des spécificités de chaque planche, décidera de la transformation morphologique à appliquer : l’ouverture (opening) ou la fermeture (closing). Il décidera également de l’importance de ladite transformation :

if morph > 0:
    morphed = cv2.morphologyEx(binary, cv2.MORPH_OPEN, cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (morph, morph)))
elif morph < 0:
    morphed = cv2.morphologyEx(binary, cv2.MORPH_CLOSE, cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (abs(morph), abs(morph))))
else:
    morphed = binary

Ces opérations servent, en gros, à réduire le bruit dans l’image binarisée, autrement dit les petits trous ou les petites taches qui viendraient perturber la régularité des contours.

L’opération de dilatation permet de grossir les traits. Le crible est appliqué partout, et pour peu qu’un de ses pixels soit positif, alors le pixel central, l’ancre du crible, deviendra positif aussi. À la périphérie des traits, cela a pour effet de “convertir” le voisinage proche, de “contaminer” les pixels voisins, bref d’élargir les traits.

L’opération d’érosion fonctionne dans le sens inverse, et “tue” les pixels dont les voisins (selon le crible) ne sont pas tous vivants.

L’opération de fermeture n’est qu’une dilatation suivie d’une érosion. En cas de petit trou dans le trait, l’opération de fermeture va venir le combler. L’idée est simple : le trait est d’abord épaissi (ce qui peut conduire les morceaux disjoints du traits à se toucher), puis uniformément “amaigri” (ce qui ne recrée pas le trou anciennement présent). On peut imaginer deux bulles sphériques proches qui grossissent jusqu’à se toucher, deviennent alors une sorte de “blob” ovale, blob qui peut ensuite rapetisser sans que cela ne recrée les deux bulles. En images :

La bordure est disjointe en bas, cela posera problème.

La bordure est disjointe en bas, cela posera problème.

Après une fermeture, la bordure est &ldquo;réparée&rdquo;.

Après une fermeture, la bordure est “réparée”.

À l’inverse, l’opération d’ouverture est une érosion suivie d’une dilatation. L’érosion peut briser un petit lien de pixels qui viendrait connecter deux zones (typiquement, une saleté sur la page qui conduirait à ce que deux cases soient considérées comme jointes par un petit pont de pixels), lien qui ne sera pas forcément recréé par une dilatation subséquente. Cette opération est beaucoup plus rarement nécessaire, j’ai d’ailleurs du mal à trouver un exemple.

Outre l’opération à effectuer, la fonction morphologyEx prend en argument un tableau de valeurs, le kernel, qui agit comme un filtre, comme un “crible”. Il glisse sur l’image et modifie chaque pixel en plaçant le crible sur ce pixel, en observant les caractéristiques des autres pixels du crible, et en modifiant le pixel traité en fonction de ces autres pixels, un peu à la façon d’un automate cellulaire. Le pixel potentiellement modifié est toujours au centre exact du crible, raison pour laquelle un crible dont la hauteur ou la largeur ne serait pas un nombre impair n’aurait pas vraiment de sens. Le crible peut être un simple rectangle, mais il peut aussi consister en n’importe quelle forme plus subtile. Pour les formes les plus spéciales, on peut créer manuellement un tableau numpy, mais pour simplifier les choses, OpenCV dispose d’une fonction (getStructuringElement) qui permet de créer facilement les kernels les plus élémentaires : le rectangle, la croix, ou l’ellipse. En l’espèce, j’utilise une ellipse, car j’ai déterminé empiriquement que cela me donnait les meilleurs résultats.

La taille du crible (ici, de l’ellipse) va varier en fonction de l’importance de la “réparation” à effectuer, nous verrons plus tard comment je procède pour faire varier cette taille grâce à un raccourci clavier.

Détection des cases

L’opération suivante consiste à détecter les contours présents dans l’image :

contours, hierarchy = cv2.findContours(morphed, cv2.RETR_EXTERNAL , cv2.CHAIN_APPROX_NONE)

cv2.RETR_EXTERNAL permet de se limiter aux bordures les plus externes. En l’espèce, une fois les bordures des cases détectées, aucune bordure à l’intérieur des cases ne sera prise en compte. cv2.CHAIN_APPROX_NONE permet d’éviter que les bordures soient “simplifiées”, autrement dit que seuls les coins soient stockés.

La ligne suivante ignore les contours dont l’aire est inférieure à 6250 pixels, une valeur là encore déterminée de façon empirique mais qui n’a pas à être 6250 exactement :

contours = [c for c in contours if cv2.contourArea(c) > 6250]

Note : à la base, je travaillais avec des images dont les dimensions verticales et horizontales étaient 4 fois supérieures. Lorsque j’ai décidé de diviser ces dimensions par 4, les aires ont été divisées par 4², soit 16. Comme je m’étais arrêté initialement sur une aire minimale de 100'000, j’ai divisé celle-ci par 16, ce qui m’a donné 6250.

Pour faciliter l’étape suivante, je crée une classe Cell simple qui a pour but de stocker quelques informations au sujet de chaque case :

cells = []
for contour in contours:
    left = contour[contour[:,&nbsp;:, 0].argmin()][0][0]
    right = contour[contour[:,&nbsp;:, 0].argmax()][0][0]
    top = contour[contour[:,&nbsp;:, 1].argmin()][0][1]
    bottom = contour[contour[:,&nbsp;:, 1].argmax()][0][1]
    cell = Cell(contour, left, right, top, bottom)
    cells.append(cell)

Ces lignes font appel au slicing numpy pour déterminer les 4 extrémités de chaque case. Note : argmin et argmax renvoient un index, et non la valeur directement.

Dernière étape concernant la détection des cases : dessiner, sur l’image de monitoring, les bordures des cases trouvées durant cette étape. Plus tard, l’image de monitoring sera affichée, et le résultat pourra être validé (ce qui entraînera l’extraction concrète des cases et leur enregistrement en autant de fichiers), corrigé (afin de modifier la taille du crible des opérations morphologiques, voire la nature de ces opérations), ou ignoré (ce qui passera à la planche suivante). Le dessin des contours fait appel à la fonction drawContours :

cv2.drawContours(monitor, [cell.contour for cell in cells], -1, (0,0,255), 3) 

La valeur -1 indique simplement que, parmi les contours passés en second argument, l’on souhaite tous les dessiner. Le trait sera rouge (OpenCV fonctionne en mode BGR, et pas RGB), l’épaisseur de 3 pixels.

Il est à noter que certaines planches particulières entraînent des dysfonctionnements, généralement bénins : les premières planches des albums commencent souvent par le titre de l’album, en grosses lettres noires. Ces lettres sont parfois considérées à tort comme des cases. Il en va de même s’agissant de certains “motifs” qui ornent la première ou la dernière page, comme le motif inca sur la dernière page du Temple du Soleil. Il arrive que ces motifs soient dans la continuité de l’histoire, auquel cas je les considère comme des cases ; c’est le cas de la dernière case d’Objectif Lune, que j’ai prise en compte lors même qu’elle est de forme ronde. Dans le cas du Temple du Soleil cependant, il ne s’agit pas d’une case s’inscrivant dans la chronologie de la page, raison pour laquelle je ne le considère pas comme une case.

Certaines cases sont si petites qu’elles font à peu près la même taille que le numéro de page et sont donc en principe ignorées, ce qui m’a obligé à les traiter manuellement : cf. dans la section “Trivia”, lorsque je parle des plus petites cases de l’œuvre.

Enfin, certaines cases sont plus embêtantes : elles présentent des phylactères qui couvrent plusieurs cases, comme les vocalises de la Castafiore (p. 19 des Bijoux de la Castafiore), la vision de Foudre Bénie (p. 44 de Tintin au Tibet), ou encore la transmission radio de Tournesol à la terre (p. 48 d’On a marché sur la Lune). Ces cases ont dû être séparées manuellement.

Numérotation des cases

Cette étape fut un peu plus complexe que prévu, car il s’agit d’un cas typique de mécanisme très naturel pour le lecteur, mais pas anodin à représenter sous forme de règles. Évidemment, si les cases étaient agencées selon une simple grille, l’exercice serait facile ; c’est globalement le cas pour les premiers albums. Rapidement cependant, Hergé s’octroie des libertés avec le modèle de la grille, qui finissent par devenir monnaie courante dans les derniers albums. On observe alors des cases qui ne font pas toute la hauteur d’un strip, mais seulement une fraction de celle-ci (typiquement la moitié). Il arrive même qu’une de ces cases partielles soit encore subdivisée horizontalement, ce qui peut donner des choses comme ça :

Il convient à titre liminaire de préciser que les cases ne doivent pas être référencées par le coin supérieur gauche (ou supérieur droit), pas plus que par leur “centre de gravité” : ces valeurs varient en effet souvent, même entre plusieurs cases qui occupent toute la hauteur d’un strip, car il suffit qu’un phylactère dépasse du haut de la case pour fausser la mesure. Les coins inférieurs de la case n’ont (globalement) pas ce problème, raison pour laquelle j’ai choisi de toujours me baser sur le coin inférieur gauche des cases pour considérer leur position.

La première étape de la numérotation des cases consiste à éclater la planche en strips, c’est à dire en bandes horizontales superposées. Heureusement, Hergé ne s’est jamais écarté de cette logique des strips, si bien qu’il est toujours possible de diviser une planche de cette manière. Cela simplifie les opérations, car un strip est toujours entièrement terminé avant que ne débute le suivant, autrement dit, une case d’un strip A viendra toujours avant une case d’un strip B, si le strip A vient lui-même avant le strip B (autrement dit “plus haut”).

Pour diviser la planche en strips, il faut tout d’abord trouver tous les “bas de cases”, ce que j’ai appelé baseline dans mon code. Seulement, il est probable que deux cases pourtant clairement sur le même strip aient des extrémités inférieurs qui diffèrent de quelques pixels, en raison des aléas du dessin, de l’impression et/ou du scan. Il faut donc normaliser ces valeurs. Autrement dit, pour chaque case, si une baseline a déjà été trouvée (pour une précédente case) qui est suffisamment proche du bas de la case, c’est cette baseline qui sera utilisée pour la case analysée, et pas son extrémité inférieure :

for cell in cells:
    try:
        baseline = next(cell2.baseline for cell2 in cells if abs(cell2.baseline - cell.bottom) < 100)
        cell.baseline = baseline
    except StopIteration:
        cell.baseline = cell.bottom

Cela conduit à une uniformisation des baselines, si bien que pour un strip donné, il n’y aura qu’une seule baseline.

Il reste que cette étape comptabilise également les baselines des cases “partielles”. Dans l’image ci-dessus, la case en haut à droite (“Les voilà !…"). On ne peut donc pas considérer que chaque baseline “uniformisée” correspond à un strip, il faut encore éliminer les baselines des cases partielles. C’est en fait assez simple : si on prolonge ces “mauvaises” baselines, arrive forcément un moment où elles viennent “heurter” une autre case. Autrement dit, il existe au moins une case pour laquelle la baseline se situe entre le haut de la case et le bas de la case.

La baseline de la case en haut à droite, en vert, se situe entre le haut et le bas de la case de gauche, marqués en bleu. Il faut donc l&rsquo;éliminer. La baseline de la case de gauche, pas dessinée ici, ne vient heurter aucune autre case, on peut donc la conserver.

La baseline de la case en haut à droite, en vert, se situe entre le haut et le bas de la case de gauche, marqués en bleu. Il faut donc l’éliminer. La baseline de la case de gauche, pas dessinée ici, ne vient heurter aucune autre case, on peut donc la conserver.

roads = set(cell.baseline for cell in cells)
highways = []
for road in roads:
    if any(cell for cell in cells if cell.top < road < cell.baseline):
        pass
    else:
        highways.append(road)
highways = sorted(highways)

Dans mon code, j’ai choisi d’appeler roads l’ensemble des baselines (deux baselines identiques comptent comme une même route, d’où l’emploi d’un set), et highways les baselines qui correspondent au bas d’un strip. C’est une nomenclature un peu étrange, mais il est parfois difficile de raisonner sans des termes un peu imagés.

Note : là encore, je prends comme limite inférieure d’une case sa baseline, autrement dit la version uniformisée de son bord inférieur, afin d’éviter les erreurs dues au fait qu’une case est très légèrement plus basse qu’une autre pourtant située sur le même strip. À ce stade, on peut se demander l’intérêt de conserver la valeur bottom de chaque case : elle nous servira à procéder à un découpage plus exact de la case, lequel devra se baser sur les pixels exacts de la case et non sur l’approximation que représente la baseline de celle-ci.

La suite du code s’applique “highway par highway”, autrement dit strip par strip (cf. le code complet pour une vue d’ensemble).

strip_cells = [cell for cell in cells if cell.baseline <= highway and cell.main_index == -1]
strip_height = max(cell.height for cell in strip_cells)

Les cases du strip en cours sont celles dont la baseline est inférieure ou égale au highway (bas de strip) en cours (autrement dit plus haut), et dont l’index principal n’a pas encore été déterminé (et vaut donc -1, valeur initialisée par le constructeur de la classe Cell). Je me sers en d’autres termes de l’index principal comme d’un marqueur pour vérifier si la case a été traitée ou non, puisque cette valeur sera forcément paramétrée au cours du traitement du strip contenant la case.

La hauteur du strip entier est définie comme la hauteur de la plus haute des cases du strip. Pour la suite, j’appellerai “grande case” une case dont la hauteur est (à peu près) égale à la hauteur du strip, “petite case” une case qui ne remplit pas cette condition.

Note : si le strip est composé uniquement de petites cases (qui ne sont pas en pleine hauteur), cette méthode ne permet pas de déterminer la hauteur du strip. Heureusement, ça n’arrive jamais.

for cell in strip_cells:
    if abs(cell.height - strip_height) < 100:
        cell.full = True
    else:
        cell.full = False

    cell.row = row

Les cases se voient également attribuer un entier qui identifie le strip dont elle fait partie.

L’étape suivante consiste à donner à chaque case du strip un index principal (main_index) :

for cell in strip_cells:
    if cell.full:
        cell.main_index = cell.left
    else:
        try:
            cell.main_index = max(cell2.left for cell2 in strip_cells if cell2.full and cell2.left < cell.left) + 1
        except ValueError:
            cell.main_index = 0

Cet index principal est en fait l’index du groupe de cases auquel appartient la case :

Les cases 7 et 8 appartiennent au même groupe de cases, les cases 10 et 11 au même groupe de cases, les cases 9 et 12 sont chacune seule dans leur groupe. Il y a donc 4 groupes.

Les cases 7 et 8 appartiennent au même groupe de cases, les cases 10 et 11 au même groupe de cases, les cases 9 et 12 sont chacune seule dans leur groupe. Il y a donc 4 groupes.

Toutes les cases d’un même groupe doivent se voir attribuer le même index principal, et les index principaux doivent aller strictement croissant (représenter des groupes ordonnés de gauche à droite).

Si la case est une grande case, son index principal est simplement son extrémité gauche. En revanche, si la case est une petite case, et fait donc partie d’une groupe de petites cases intercalées “entre” plusieurs grandes cases (ou encore tout à droite, ou tout à gauche du strip), elle se voit attribuer un index principal “artificiel” qui vaut 1 de plus que l’extrémité gauche de la grande case située le plus près possible à sa gauche, ou 0 si une telle grande case n’existe pas.

Pour clarifier un peu les choses, on peut reprendre le strip ci-dessus. Les cases 9 et 12 sont des grandes cases et ont pour index principal 204 et 806, respectivement (leur extrémité gauche respective). Les cases 10 et 11 sont des petites cases, autrement dit elles ne sont pas hautes comme le strip entier. Dès lors, leur index principal est calculé sur la base de la grande case la plus proche, vers la gauche. Il s’agit de la case 9, dont l’index principal est 204, on l’a dit. L’index principal des cases 10 et 11 est donc 205, l’important étant simplement qu’il soit strictement supérieur à 204. Quant aux cases 7 et 8, elles sont dans la même situation, mais elles n’ont pas de voisine “grande” vers la gauche. Leur index principal est donc de 0.

Il en irait de même en cas de groupe de petites cases agencées horizontalement entre elles. Exemple :

Les cases 7, 8, 9 et 10 sont toutes partielles, elles ont donc toutes le même index principal, en l&rsquo;espèce 1 de plus que l&rsquo;extrémité gauche de la case 6, soit 309.

Les cases 7, 8, 9 et 10 sont toutes partielles, elles ont donc toutes le même index principal, en l’espèce 1 de plus que l’extrémité gauche de la case 6, soit 309.

L’étape suivante consiste à remplacer ces index principaux “chaotiques” par des entiers successifs à partir de 1 :

temporary_indices = sorted(set(cell.main_index for cell in strip_cells))
for cell in strip_cells:
    cell.main_index = temporary_indices.index(cell.main_index) + 1

Chaque index principal est donc remplacé par sa “position” au sein de l’ensemble (ordonné croissant) des index principaux possibles, augmenté de 1 (pour commencer à 1 et non à 0). C’est utile si l’on souhaite utiliser une numérotation semblable à celle suivie par la page Wikipédia consacrée au vocabulaire du capitaine Haddock, autrement dit cibler le groupe de cases, puis la position de la petite case au sein de ce groupe (par exemple : CES.49B3h pour Coke en Stock, page 49, strip B, groupe de cases 3, case du haut ; la valeur 3 serait déterminée à cette étape). Ce n’est pas la nomenclature que j’ai décidé de suivre, comme indiqué plus loin, raison pour laquelle ces quelques lignes de code pourraient être ignorées.

L’étape suivante, qui ne vaut que pour les petites cases, consiste à donner à celles-ci un “sous-index”, qui indiquera leur rang au sein de leur groupe de petites cases :

partial_indices = set(cell.main_index for cell in strip_cells if not cell.full)
for partial_index in partial_indices:
    partial_cells = [cell for cell in strip_cells if cell.main_index == partial_index]
    partial_cells = sorted(partial_cells, key=lambda x:(x.baseline, x.left))
    for sub_index, partial_cell in enumerate(partial_cells, start=1):
        partial_cell.sub_index = sub_index

Note : dans ce code, “partial” s’oppose à “full” ; ces termes désignent respectivement les “petites cases” et les “grandes cases”.

Ce tri se fait de façon beaucoup plus naturelle : les petites cases d’un même groupe sont ordonnées selon deux critères, le second s’appliquant uniquement lorsque le premier conduit à une égalité (d’où le 2-tuple retourné par la lambda) : tout d’abord la baseline de la case, et en cas d’égalité (petites cases alignées horizontalement) selon l’extrémité gauche de la case. Les sous-index sont ensuite attribués aux cases, en commençant là encore à (start=1).

Le gros du travail de numérotation est fait, et la boucle sur chaque strip est d’ailleurs terminée. L’étape suivante consiste simplement à donner à chaque case un index “absolu”, qui n’est jamais que son ordre au sein de la liste des cases, une fois celle-ci ordonnée d’après deux critères : en priorité l’index principal (main_index), et en cas d’égalité sur ce critère (donc en cas de petites cases, les seules qui peuvent partager entre elles le même index principal) le sous-index :

cells = sorted(cells, key=lambda x:(x.row, x.main_index, x.sub_index))
for absolute_index, cell in enumerate(cells, start=1):
    cell.absolute_index = absolute_index

L’index absolu correspond à l’ordre naturel de lecture.

On peut enfin dessiner, sur l’image de monitoring, les index absolus, en vert cette fois-ci pour bien les distinguer des bordures rouges :

for cell in cells:
    cv2.putText(monitor, str(cell.absolute_index), 
        (cell.left, cell.bottom), 
        cv2.FONT_HERSHEY_SIMPLEX, 
        3,
        (0,255,0),
        10)

Note : dans les illustrations utilisées plus haut, les chiffres sont plus proches du centre des cases ; cela ne fonctionne pas bien en cas de case très petite, raison pour laquelle j’ai préféré ici placer les chiffres en bas à gauche de chaque case.

Pour être tout à fait complet et par honnêteté, il convient de signaler que 4 planches (sur un total de 1'424) posent problème pour des raisons diverses. J’ai décidé qu’elles ne légitimaient pas à elles seules une refonte de mon système de numérotation, et j’ai renuméroté manuellement les cases concernées. Les strips concernés sont les suivants :

Tintin au pays de l&rsquo;or noir, p. 59 : les 4 &ldquo;petites cases&rdquo; semblent faire partie du même groupe, mais les deux de gauche se lisent avant les deux de droite.

Tintin au pays de l’or noir, p. 59 : les 4 “petites cases” semblent faire partie du même groupe, mais les deux de gauche se lisent avant les deux de droite.

Objectif Lune, p. 54 : une case de forme coudée qui en &ldquo;contient&rdquo; une autre.

Objectif Lune, p. 54 : une case de forme coudée qui en “contient” une autre.

On a marché sur la Lune, p. 4 : le strip du haut &ldquo;déborde&rdquo; sur celui du bas.

On a marché sur la Lune, p. 4 : le strip du haut “déborde” sur celui du bas.

On a marché sur la Lune, p. 60 : à nouveau une case coudée.

On a marché sur la Lune, p. 60 : à nouveau une case coudée.

Vérification humaine et prise de décision

L’étape finale consiste à afficher l’image de monitoring, et prendre une décision sur la base du résultat observé (bordures et numérotation).

while True:
    cv2.imshow("tintin", monitor)
    key = cv2.waitKey(0)
    if key == ord("v"):
        print("Planche validée...")
        blue, green, red = cv2.split(resized)
        for cell in cells:
            empty = np.zeros((1800, 1200, 1), dtype=np.uint8)
            mask = cv2.drawContours(empty, [cell.contour], -1, 255, -1)
            bgra = cv2.merge((blue, green, red, mask))
            t, r, b, l = cell.top, cell.right, cell.bottom, cell.left
            cookie = bgra[t:b, l:r]
            cell_name = f"{code}{str(page).zfill(2)}{ascii_uppercase[cell.absolute_index-1]}"
            cv2.imwrite(os.path.join(output_dir, f"{cell_name}.png"), cookie)
        print(f"OK ! Nombre de cases écrites&nbsp;: {len(cells)}.")
        page += 1
        break
    elif key == ord("o"):
        morph += 1
        print("Plus ouvert...")
        break
    elif key == ord("c"):
        morph -= 1
        print("Plus fermé...")
        break
    elif key == ord("i"):
        print("Ignore cette image.")
        page += 1
        break
    elif key == ord("q"):
        print("Quitte.")
        sys.exit()

imshow affiche l’image de monitoring, et lui donne comme titre “tintin” (je me sers de ce titre pour demander à i3, mon gestionnaire de fenêtres, de placer systématiquement ces fenêtres de visualisation sur un workspace précis de mon moniteur secondaire : workspace 10 output HDMI-0 et assign [title="tintin"] 10).

La fenêtre de visualisation attend ensuite qu’une touche soit pressée (key).

La touche “v” permet de valider la planche. L’image en couleurs est à nouveau utilisée (elle avait été laissée tranquille durant toute l’exécution du code), éclatée en ses trois canaux bleu, vert et rouge (rappel : OpenCV fonctionne en BGR, pas en RGB). Pour chaque cellule, un masque est ensuite créé. La première étape consiste à préparer un “calque” entièrement vide, ce que numpy fait très bien (rappel : les images, dans le portage python d’OpenCV, ne sont jamais que des tableaux numpy). On “peint” ensuite sur ce calque les contours de la case qui nous occupe, avec une épaisseur de trait de -1 cette fois-ci. Cette “épaisseur spéciale” revient en fait à dire que l’on souhaite peindre tout l’intérieur du contour (bref, remplir la case de blanc). On a alors une image prête à être greffée, en guise de canal alpha, avec les 3 canaux de couleur, c’est ce que fait merge.

On découpe ensuite un “cookie” à l’emporte-pièce, en d’autres termes on se sert du slicing numpy pour découper l’image créée et ne prendre que ce qui est compris dans les limites de la case.

On prépare ensuite un nom de fichier, basé sur une nomenclature de mon invention (que je ne suis sûrement pas le premier à utiliser), et qui diffère (par exemple) de celle employée par Wikipédia sur la page consacrée au vocabulaire du capitaine Haddock (cf. plus haut) : d’abord un code à 3 lettres (les 3 premières lettres du premier nom, propre ou commun, du titre de l’album, le nom “Tintin” étant ignoré, avec une exception pour Tintin au pays des Soviets qui prend le code SOV afin de laisser le code PAY libre pour Tintin au pays de l’or noir), ensuite le numéro de page précédé au besoin d’un zéro, enfin une lettre indiquant la position de la case dans l’ordre naturel de lecture (aucune planche ne comporte plus de 24 cases, cf. la section “Trivia” ci-dessous).

Enfin, on écrit le fichier (imwrite).

La touche “o” permet d’augmenter la variable (utilisée comme variable globale) morph. Si cette valeur est positive, une transformation morphologique d’ouverture (open) sera appliquée, et la taille du crible (en l’espèce circulaire) dépendra de morph.

À l’inverse, la touche “c” permet de réduire la valeur morph. Si elle est négative, une opération morphologique de fermeture (close) sera appliquée (même remarque concernant la taille du crible, qui sera basé sur la valeur absolue de morph, puisque sa taille doit être positive).

La touche “i” permet d’ignorer l’image, et de passer à la planche suivante sans rien faire.

La touche “q” enfin permet de quitter la visualisation (et le programme).

Le reste du code (cf. version complète) contient encore quelques éléments simples (une gestion extrêmement simpliste des arguments passés en ligne de commande et une boucle sur les différentes planches).

Trivia

Quelques infos amusantes apprises lors de ce projet :

La planche comprenant le plus de cases est la page 45 de l’Affaire Tournesol, qui en comprend 24 (c’est la fameuse scène où Haddock se débat avec un morceau de sparadrap).

Les plus petites cases (si l’on peut considérer ça des cases) apparaissent à la page 7 d’Objectif Lune : il s’agit des 5 petites cases en bas à gauche qui représentent chacune un état successif de l’indicateur d’étage de l’ascenseur. Dans la mesure où elles sont clairement entourées chacune d’une bordure noire, et où elles représentent des instants temporels différents, je les considère comme des cases, et des cases séparées entre elles.

Quant aux 9 plus grandes “cases”, elles sont plus célèbres et font la taille d’une planche entière :

  • Le Sceptre d’Ottokar, p. 19 : une page de la brochure sur la Syldavie que Tintin lit dans l’avion
  • Le Sceptre d’Ottokar, p. 20 : une autre page de la brochure (représentant la bataille de Zileheroum)
  • Le Sceptre d’Ottokar, p. 21 : une autre page de la brochure
  • Le Crabe aux pinces d’or, p. 21 : un hydravion survole Tintin et Haddock, naufragés
  • Le Crabe aux pinces d’or, p. 29 : Tintin et Haddock marchant dans le désert, assoiffés
  • Le Crabe aux pinces d’or, p. 40 : Tintin et Haddock courent dans une ruelle de Bagghar
  • Le Crabe aux pinces d’or, p. 49 : Omar Ben Salaad chevauche une mule dans une ruelle de Bagghar
  • Objectif Lune, p. 35 : un blueprint de la fusée lunaire
  • Objectif Lune, p. 42 : la fusée lunaire et le pas de tir

Code complet

Mon dépôt git concernant ce projet est rempli de fichiers qui n’ont rien à y faire ; je dois le mettre au propre avant de le rendre public. En attendant, voici le code complet, agrémentés de quelques commentaires en anglais :

import cv2
import numpy as np
import sys
import os
from string import ascii_uppercase

albums = {"COK":"Coke en stock", #
"AFF":"L'Affaire Tournesol",
"CRA":"Le Crabe aux pinces d'or", #
"LOT":"Le Lotus bleu", #
"BIJ":"Les Bijoux de la Castafiore", #
"SCE":"Le Sceptre d'Ottokar", #
"CIG":"Les Cigares du pharaon", #
"SEC":"Le Secret de La Licorne", #
"BOU":"Les Sept Boules de cristal", #
"TEM":"Le Temple du Soleil", #
"ETO":"L'Étoile mystérieuse", #
"TRE":"Le Trésor de Rackham le Rouge", #
"ILE":"L'Île Noire", #
"ORE":"L'Oreille cassée", #
"OBJ":"Objectif Lune",
"LUN":"On a marché sur la Lune",
"CON":"Tintin au Congo", #
"PAY":"Tintin au pays de l'or noir", #
"SOV":"Tintin au pays des Soviets", #
"TIB":"Tintin au Tibet", #
"AME":"Tintin en Amérique", #
"PIC":"Tintin et les Picaros", #
"VOL":"Vol 714 pour Sydney"} #

input_dir = "/home/biganon/planches"
output_dir = "/home/biganon/cases"

class Cell:
    def __init__(self, contour, left, right, top, bottom):
        self.contour = contour
        self.left = left
        self.right = right
        self.top = top
        self.bottom = bottom
        self.baseline = -1
        self.full = None
        self.row = -1
        self.main_index = -1
        self.sub_index = -1
        self.absolute_index = -1

    @property
    def height(self):
        return self.bottom - self.top

    def __repr__(self):
        return f"<Cell, [{self.top}, {self.right}, {self.bottom}, {self.left}]>"

def process(file):
    global morph
    global page
    print(f"Commence la page {page}, morph {morph}, fichier {file}...")

    # Extracting cells:
    original = cv2.imread(file, cv2.IMREAD_COLOR)
    resized = cv2.resize(original, (1200, 1800))
    gray = cv2.cvtColor(resized, cv2.COLOR_BGR2GRAY)
    monitor = cv2.cvtColor(gray, cv2.COLOR_GRAY2BGR)
    threshold, binary = cv2.threshold(gray, 220, 255, cv2.THRESH_BINARY)

    inverted = cv2.bitwise_not(binary)

    if morph > 0:
        morphed = cv2.morphologyEx(inverted, cv2.MORPH_OPEN, cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (morph, morph)))
    elif morph < 0:
        morphed = cv2.morphologyEx(inverted, cv2.MORPH_CLOSE, cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (abs(morph), abs(morph))))
    else:
        morphed = inverted

    contours, hierarchy = cv2.findContours(morphed, cv2.RETR_EXTERNAL , cv2.CHAIN_APPROX_NONE)
    contours = [c for c in contours if cv2.contourArea(c) > 6250]
    cells = []
    for contour in contours:
        left = contour[contour[:,&nbsp;:, 0].argmin()][0][0]
        right = contour[contour[:,&nbsp;:, 0].argmax()][0][0]
        top = contour[contour[:,&nbsp;:, 1].argmin()][0][1]
        bottom = contour[contour[:,&nbsp;:, 1].argmax()][0][1]
        cell = Cell(contour, left, right, top, bottom)
        cells.append(cell)
    #####

    # Creating the contoured monitor (test output):
    cv2.drawContours(monitor, [cell.contour for cell in cells], -1, (0,0,255), 3)        
    #####

    # Standardizing the bottom edge of cells:
    for cell in cells:
        try:
            baseline = next(cell2.baseline for cell2 in cells if abs(cell2.baseline - cell.bottom) < 100)
            cell.baseline = baseline
        except StopIteration:
            cell.baseline = cell.bottom
    #####

    # Fiding roads and highways:
    roads = set(cell.baseline for cell in cells)
    highways = []
    for road in roads:
        if any(cell for cell in cells if cell.top < road < cell.baseline):
            pass
        else:
            highways.append(road)
    highways = sorted(highways)
    #####

    # Giving each cell its row, its horizontal index and its sub-index:
    for row, highway in enumerate(highways, start=1):
        # Finding basic info about the strip:
        strip_cells = [cell for cell in cells if cell.baseline <= highway and cell.main_index == -1]
        strip_height = max(cell.height for cell in strip_cells)
        
        for cell in strip_cells:
            # Setting various info about the cell:
            if abs(cell.height - strip_height) < 100:
                cell.full = True
            else:
                cell.full = False

            cell.row = row

        # Setting temporary (main) indices, that will be standardized:
        for cell in strip_cells:
            if cell.full:
                cell.main_index = cell.left
            else:
                try:
                    cell.main_index = max(cell2.left for cell2 in strip_cells if cell2.full and cell2.left < cell.left) + 1
                except ValueError:
                    cell.main_index = 0

        # Standardizing (main) indices:
        temporary_indices = sorted(set(cell.main_index for cell in strip_cells))
        for cell in strip_cells:
            cell.main_index = temporary_indices.index(cell.main_index) + 1

        # Setting secondary indices where needed:
        partial_indices = set(cell.main_index for cell in strip_cells if not cell.full)
        for partial_index in partial_indices:
            partial_cells = [cell for cell in strip_cells if cell.main_index == partial_index]
            partial_cells = sorted(partial_cells, key=lambda x:(x.baseline, x.left))
            for sub_index, partial_cell in enumerate(partial_cells, start=1):
                partial_cell.sub_index = sub_index

    #####

    # Giving each cell its absolute index:
    cells = sorted(cells, key=lambda x:(x.row, x.main_index, x.sub_index))
    for absolute_index, cell in enumerate(cells, start=1):
        cell.absolute_index = absolute_index

    # Drawing indices:
    for cell in cells:
        cv2.putText(monitor, str(cell.absolute_index), 
            (cell.left, cell.bottom), 
            cv2.FONT_HERSHEY_SIMPLEX, 
            3,
            (0,255,0),
            10)
    #####

    # Rendering the result:
    while True:
        cv2.imshow("tintin", monitor)
        key = cv2.waitKey(0)
        if key == ord("v"):
            print("Planche validée...")
            blue, green, red = cv2.split(resized)
            for cell in cells:
                empty = np.zeros((1800, 1200, 1), dtype=np.uint8)
                mask = cv2.drawContours(empty, [cell.contour], -1, 255, -1)
                bgra = cv2.merge((blue, green, red, mask))
                t, r, b, l = cell.top, cell.right, cell.bottom, cell.left
                cookie = bgra[t:b, l:r]
                cell_name = f"{code}{str(page).zfill(2)}{ascii_uppercase[cell.absolute_index-1]}"
                cv2.imwrite(os.path.join(output_dir, f"{cell_name}.png"), cookie)
            print(f"OK ! Nombre de cases écrites&nbsp;: {len(cells)}.")
            page += 1
            break
        elif key == ord("o"):
            morph += 1
            print("Plus ouvert...")
            break
        elif key == ord("c"):
            morph -= 1
            print("Plus fermé...")
            break
        elif key == ord("i"):
            print("Ignore cette image.")
            page += 1
            break
        elif key == ord("q"):
            print("Quitte.")
            sys.exit()
    #####


if __name__ == "__main__":
    code = sys.argv[1]
    title = albums[code]
    files = os.listdir(input_dir)
    files = sorted(f for f in files if title in f)

    if len(sys.argv) >= 3:
        start = int(sys.argv[2])
    else:
        start = 1

    if len(sys.argv) >= 4:
        morph = int(sys.argv[3])
    else:
        morph = 0

    page = 1
    while True:
        if page < start:
            page += 1
            continue
        file = files[page-1]
        process(os.path.join(input_dir, file))
comments powered by Disqus