PAP XX

Le crénage automatique

Élèves participants :

1 Descriptif du contexte

Le crénage est un problème aussi vieux que le monde. L'homme écrit, et écrire signifie précisement placer des lettres l'une à côté de l'autre. Et donc à une certaine distance, qui dépend de la forme des lettres : on va rapprocher deux lettres qui sont symétriques comme le A et le V, et on va éloigner d'autres paires de lettres comme le D suivi d'un O.

Les polices de caractères placent les lettres dans des boîtes rectangulaires invisibles. La composition par un logiciel de bas niveau se fait en alignant ces boîtes. Le crénage consiste à corriger les erreurs d'espacement des lettres dues à cette approche. Une police de caractères qui se respecte contient un grand nombre (plusieurs centaines) de paires de crénage c'est-à-dire de quantités de rapprochement ou d'éloignement de lettres qui font chaque paire, comme dans la figure ci-dessous où l'on a colorié les rapprochements en vert et les éloignements en bleu.

Comment obtenir ces paires de crénage, a priori indispensables pour une composition de qualité, que ce soit sur papier ou à l'écran ? Un dessinateur de police peut passer plusieurs mois sur la création manuelle de telles listes de paires de crénage. Il y a aussi quelques logiciels qui font cela automatiquement. Aucun de ces logiciels n'est dans le domaine public, et, ce qui pire, aucun de dévoile vraiment sa manière de procéder. En plus les paires ainsi générées sont souvent de mauvaise qualité. Certains logiciels (comme Adobe InDesign) prétendent faire un crénage automatique en temps réel lors de la composition. Là aussi on n'a ni contrôle ni connaissance de l'agorithme sous-jacent, et encore moins la possibilité de modifier cet algorithme.

Beaucoup d'encre a été coulée sur les algorithmes que l'on pourrait utiliser pour calculer des paires de crénage. Il y a eu des idées aussi exotiques que d'utiliser le modèle de répulsion par électricité statique, ou de calculer le centre de gravité des lettres, ou de faire une spectroscopie d'une ligne de texte... D'autres ont proposé un calcul de l'aire (éventuellement ponderée) entre les lettres. Mais la majorité des experts s'accorde comme meilleure approche celle des secteurs. L'idée est très simple : on découpe la lettre en plusieurs tranches horizontales de hauteur égale (ou inégale selon certains). Pour chaque tranche on calcule les extremités de la forme de la lettre dans la tranche et on dessine une boîte qui a les mêmes dimensions verticales et dont les parois horizontales dépassent légèrement les extremités en question. On a donc entouré chaque de telles boîtes. On rapproche les lettres jusqu'à ce que deux telles boîtes se touchent (voir figure ci-dessous).

Le nombre de secteurs, la distance entre les extremités de la lettre dans le secteur et les parois horizontales du secteur, éventuellement les hauteurs des secteurs, sont des paramètres que l'on peut varier pour avoir des meilleurs résultats. Comment savoir si les résultats obtenus sont bons ? Il faudrait pour cela une interface graphique qui afficherait des paires de crénage. Mais on peut aussi tester l'efficacité d'une méthode en l'utilisant sur une police pour laquelle on possède déjà des paires de crénage de bonne qualité et en comparant les résultats.

2 Descriptif du projet

• écrire un algorithme de crénage automatique basé sur la méthode des secteurs, avec un nombre de secteurs variable et d'autres paramètres ;
• implémenter cet algorithme dans un langage objet (par ordre de préférence : C++, Python, Java) ;
• développer un outil de comparaison de listes de paires de crénages, avec possibilité de création de graphique (par exemple, histogramme des différences) ;
• coordonner toutes ces opérations en développant une interface utilisateur simple qui permette :
  • de choisir la police à traiter ;
  • de choisir le ou les algorithme(s) de crénage à utiliser (avec possibilité de pondération) en spécifiant les valeurs de paramètres pour chaque algorithme ;
  • d'afficher un graphique de comparaison de listes de paires de crénage ;
  • de lancer (par un bouton) des scripts d'application des paires de crénage sur un échantillon et d'affichage des résultats (l'affichage peut se faire à travers TeX et PDF, on ne demande aps l'affichage direct de la police sous l'interface graphique développée !).

Cette interface va constituer un logiciel d'aide à la génération automatique de paires de crénage. On pourrait alors jauger le système en choisissant les bons paramètres et en comparant les résultats avec des paires de crénage pré-établies, et ensuite l'appliquer sur des nouvelles polices, en vérifiant à chaque fois le résultat sur un échantillon. Grâce à la technologie objets cet outil pourrait être très rapidement adapté à tout nouvel algorithme de crénage, et on pourrait alors pondérer les différents algorithmes et obtenir un outil multivariant.

3 Étapes du projet

1. étude et écriture de l'algorithme ;
2. implémentation de l'algorithme avec des tests sur des caractères bidon ;
3. écriture du code d'extraction à partir des contours des caractères des informations nécessaires pour l'algorithme ;
4. application à des exemples réels ;
5. écriture du code de comparaison des listes de paires et d'affichage graphique du résultat sous forme d'histogramme ou autre ;
6. développement de l'interface utilisateur de contrôle de toutes ces opérations ;
7. septième "jour" : repos bien mérité et entrée jubilatoire dans le Walhalla des programmeurs du logiciel libre.

4 Résultats attendus

Un logiciel dont aussi bien l'utilisation que le code source sont bien documentés, qui tourne et qui produit véritablement des listes de paires de crénage à partir d'une police donnée.

5 Autres éléments