 Nous sommes toujours dans l'étape qui consiste à analyser les polices de caractères présentes dans un fichier PDF.
Comme le format "Adobe Type 1C", le format "Adobe Type 1" utilise un interpréteur PostScript pour dessiner les formes de caractères. La différence entre les deux formats est que le "Adobe Type 1C" est compacté, le "Adobe Type 1", est au format texte, non compacté. Par contre, le format "Adobe Type 1" est encrypté (certaines polices peuvent être protégées). Heureusement, l'algorithme d'encryptage/décryptage est public. Après quelques tatonnements et fausses pistes, le format "Adobe Type 1" est décodé. Nous écrivons alors un interpréteur PostScript rudimentaire pour tracer les caractères. Le résultat semble correct et utilisable.
Maintenant, il va falloir analyser un autre type de police : le type 3, c'est un format où les caractères sont dessinés avec des commandes PDF. L'intention générale est d'uniformiser tout ceci et de convertir "Type 1", "Type 1C", "Type 3" en un format de description commun et homogène qui permettra un tracé plus uniformisé.
Parallèlement à ceci, Olivier a essayé d'autres voies que le réseau neuronal pour la reconnaissance et obtient des résultats prometteurs... |
|
|
| by Didier Guillion |  |
| |
|
 Le cerveau humain, à partir des informations visuelles qui lui sont transmises, distingue assez facilement (après un petit apprentissage), une clé de sol d'une clé de fa, un "M" d'un "T", etc.
L'idée de simuler le fonctionnement des neurones dans un programme coulait donc de source.
Concrètement, un réseau de neurones "informatique" se présente en couches, comme un plat de lasagnes:
- Une série de neurones dits "d'entrée", chacun d'entre eux recevant une valeur quantifiable dépendant de l'objet à analyser. Ce peut être la luminosité d'un point, mais aussi un rapport largeur/hauteur du caractère, l'épaisseur moyenne de ses traits, en fait tout paramètre pouvant avoir une utilité dans la discrimination.
- Une série de neurones dits "de sortie", chaque neurone correspondant à une valeur possible à déterminer. Par exemple, si on veut que le réseau de neurones soit capable de trouver à quelle lettre (A-Z) correspond le caractère analysé, il faudra 26 neurones de sortie, un par lettre possible
- Entre l'entrée et la sortie, une ou plusieurs couches de neurones dits "cachés".
Chaque neurone de chaque couche est relié à chaque neurone de la couche suivante, par une liaison plus ou moins "forte". Au départ, la force de chacune des liaisons est choisie au hasard, et le réseau est incapable de reconnaître quoi que ce soit.
Ensuite, on présente au réseau des exemples de caractères à déterminer. Il essaie (et échoue). Il faut alors lui enseigner de quoi il s'agissait. Cet apprentissage affaiblit les liaisons qui ont conduit à l'erreur et renforce celles qui favorisent un résultat correct.
Si les valeurs alimentant la couche d'entrée sont bien choisies, si le réseau est correctement dimensionné, et si l'apprentissage est bien réglé, le réseau, petit à petit, apprend, et au bout de quelques milliers d'expérimentations et d'apprentissages, devient capable de distinguer quelque chose. Après 50 à 100000 apprentissages, il se débrouille pas mal.
Nous avons écrit un prototype d'un tel réseau en MyrScript, et l'avons fait travailler sur des exemples de caractères (comme les lettres de A à Z écrites en différentes tailles et différentes fontes). Une dizaine de milliers d'apprentissages plus tard, le réseau obtient un taux de fiabilité de 99% sur les exemples qui lui ont déjà été fournis, et plus de 90% sur des exemples issus d'autres fontes proches mais pas identiques.
Globalement, les résultats sont donc encourageants. Seul petit bémol : la masse de calculs devient assez conséquente. Pour un tout petit réseau de neurones de 3 couches de 26 neurones, il faut effectuer 1352 opérations pour obtenir un résultat. Si on passe le nombre de neurones par couche à 120, il en faut 28800.
MyrScript commence à peiner un peu, et nous nous apercevons que le réglage du "taux d'apprentissage" s'avère crucial. Il détermine si le réseau apprend vite ou lentement de ses erreurs.
Trop vite, et une correction d'une de ses erreurs lui fait "oublier" ses apprentissages précédents, et trop lentement, il commet inlassablement la même faute, sans apprendre à se corriger.
Enfin, si on désire réduire le nombre de paramètres d'entrée pour simplifier le réseau, il faut choisir des critères quantifiables facilement extractibles du dessin du caractère. Quels qu'ils soient, leur choix sera dicté seulement par notre propre intuition, et risque de s'avérer moins performant qu'attendu.
Cette méthode fonctionne donc, mais avant de passer à l'étape suivante de l'analyse, nous préférons explorer d'autres voies similaires, basées sur les statistiques de répartition des pixels dans chaque forme de caractère. Cela permettrait d'alléger les calculs et d'obtenir un apprentissage plus rapide qu'avec un réseau neuronal classique... |
|
|
| by Olivier Guillion |  |
|
| |
|
Nous sommes dans l'étape qui consiste à analyser les polices de caractères présentes dans un fichier PDF.
Le format de police "Adobe Type 1C" (C pour compacté) est public. A partir de cette documentation, un extracteur et interpréteur de commande graphique a été écrit pour pouvoir dessiner grossièrement les caractères. En effet, nous avons progressé dans la reflexion sur l'association "numéro de caractère" vers "signification du caractère". Une solution serait de procéder en deux étapes :
1- Rechercher des données similaires dans une base de données, pour savoir si le caractère à déjà été rencontré.
2- Si le caractère est nouveau, tracé du caractère et reconnaissance automatique de celui-ci. S'il est reconnu, alors nous alimenterons la base de donnée utilisée en étape 1.
La reconnaissance de caractère passera peut-être par des réseaux neuronaux. Un réseau neuronal a été écrit (en MyrScript, c'est un excellent langage pour faire rapidement des maquettes) et donne des résultats intéressants...
Entretemps un nouveau type de police est rencontré, le format "Adobe Type 1". La prochaine étape sera l'analyse de ce format. |
|
|
| by Didier Guillion | |
|
| |
|
 Dans le cadre du projet "PDFToMusic" (voir les autres articles), nous avons été amenés à étudier les divers moyens d'effectuer une reconnaissance simple de caractères. Ceci permettrait, lorsqu'on trouve dans un fichier PDF un caractère dessinant par exemple une clé de sol, de savoir qu'il s'agit bien d'une clé de sol et pas d'autre chose.
Dans ce projet, contrairement à une véritable reconnaissance de textes scannés, nous avons seulement besoin de différencier les caractères individuels au sein d'une fonte, ce qui supprime d'un coup plusieurs problèmes inhérents aux reconnaissances optiques conventionnelles :
1- Les caractères sont "propres", c'est-à-dire que tous les pixels sont à leur place, qu'il n'y a pas de possibilité de poussière, ou défaut de numérisation qui pourraient perturber la reconnaissance
2- Les caractères sont isolés. On connait exactement la taille et la position du caractère à analyser. Impossible d'avoir malencontreusement deux caractères consécutifs confondus avec un seul (notamment avec des paires commes "ff" ou "ft" dont les constituants se touchent graphiquement), ou un caractère coupé en morceaux comme par exemple avec les deux points de la clé de fa.
Une première étape, de pré-analyse, consiste à voir s'il n'y aurait pas des valeurs et paramètres quantifiables, indiscutables, permettant de se passer d'intelligence artificielle ou de calculs statistiques complexes pour identifier le caractère.
Une première maquette est écrite en MyrScript.
 Le caractère est affiché, puis le nombre de pixels "noirs" sur chaque ligne et sur chaque colonne est calculé. Un double histogramme est alors tracé, avec des couleurs dépendant du nombre de "trous" détectés lors du balayage de la ligne ou de la colonne.
Ensuite, divers traitements sont essayés.
 Le premier combine les histogrammes horizontaux et verticaux afin d'obtenir une "empreinte" du caractère. Nous la calculons avec le même caractère dans diverses fontes musicales, mais malgré d'assez importantes similitudes, cela ne semble pas être suffisamment "stable" pour permettre une reconnaissance.
 Deuxième essai. L'aspect du caractère est analysé, et les "directions" des tracés sont extraites. Le graphe obtenu montre en rouge les lignes "plutôt verticales", en vert les lignes "plutôt horizontales" et en bleu les lignes "plutôt diagonales". Une comparaison directe de ces paramètres à un jeu-type semble difficile, mais les résultats sont suffisamment significatifs pour garder ceci dans un coin et ne pas le jeter tout de suite.
 Troisième essai. Afin de s'abstraire de l'épaisseur des traits constituant le caractère, le script tente de le "fildefériser", de réduire tous les traits à un seul pixel d'épaisseur. Si cela ne permet pas de déterminer ce qu'est le caractère, cela pourrait au moins être utilisé pour simplifier une comparaison ultérieure.
Beaucoup des programmes que nous écrivons sont seulement des tests destinés à finir à la corbeille. C'est probablement le cas de ce petit outil d'analyse, qui nous a permis d'expérimenter quelques techniques, et d'essayer d'extraire des paramètres quantifiables du graphisme d'un caractère.
La reconnaissance du caractère s'avère cependant complexe (nous nous y attendions), et doit probablement passer par des algorithmes de discrimination un peu plus évolués qu'une simple série de comparaisons.
Nous nous penchons donc sur les réseaux de neurones, qui semblent souvent employés dans les programmes d'OCR (Optical Character Recognition)... |
|
|
| by Olivier Guillion | |
|
| |
|
Nous sommes dans l'étape qui consiste à analyser les polices de caractères présentes dans un fichier PDF.
Cette étape de l'étude vise à extraire les données graphiques d'une police au format TrueType. Heureusement, la documentation est disponible. En première analyse, le format a l'air très complet et complexe. Mais avons-nous besoin de toutes ces informations ? Nous nous intéressons en premier lieu à la manière dont les glyphes (rendu graphique d'un caractère d'une police) sont encodés. Après quelques tatonnements, nous arrivons à extraire les données des glyphes et à tracer les caractères pour vérification. Cette phase est donc validée, même si nous laissons plusieurs problèmes dans l'ombre : rencontrerons-nous des polices non TrueType ? Des polices qui encoderaient les formes en passant par le bytecode TrueType ?
Maintenant que nous avons les données qui définissent la forme des caractères, il faut associer le caractère mémorisé dans le document PDF au numéro de glyphe. En effet le format PDF ne stocke pas toute la police mais uniquement les caractères présents dans le document. Ceci passe par les "Cmaps" du fichier TrueType.
Quelques recherches sur l'Internet nous font découvrir un site présentant des centaines de partitions au format PDF. Il apparaît qu'une bonne proportion de ces fichiers utilisent une police de type "Adobe Type1C". La prochaine étape sera l'analyse de ce format. |
|
|
| by Didier Guillion | |
| |
|
L'étude du PDF a débuté (voir le billet "On échange ?"), une première ébauche du parseur (analyseur ou butineur qui balaye un fichier pour en extraire les informations) a été écrite et l'on commence à extraire les différents éléments des fichiers PDF. Il apparaît que, du point de vue de l'utilisation que nous voulons en faire, trois catégories de documents se dégagent.
La catégorie 0 (zéro): Ce sont les PDF n'incluant qu'une seule image de la partition par page du document. Ils ont vraisemblablement été générées directement depuis un scanner. La seule chose que l'on pourrait faire de ces documents serait d'exporter les images de manière séparée et de les faire traiter par OMeR.
La catégorie 1 : Ce sont les PDF, incluant des objets graphiques (lignes, rectangles, etc), et les objets musicaux (tête de note, nuance, etc) dessinés à partir d'une police de caractère. Ce sont des fichiers issus de l'exportation directe depuis un logiciel de musique, comme ce que l'on obtient depuis Harmony Assistant par exemple. L'interprétation des objets semble possible. Le problème est que la police incluse dans le document PDF est "remappé" (seuls les caractères utilisés dans le document sont présents) et ne semble pas utilisable directement.
La catégorie 2 : Ce sont les PDF n'incluant que des objets graphiques : les objets musicaux sont dessinés avec des primitives graphiques simples et non avec des polices. Je n'ai aucune idée de la façon dont ces fichiers ont été générés. Il va falloir isoler ces objets et construire un système expert de reconnaissance de forme ? Probablement.
La catégorie 1 semble la plus répandue. La catégorie 2 vient ensuite nettement moins souvent. La catégorie 0 est très rare à ma connaissance. La pierre d'achoppement de la catégorie 1 va être l'extraction des données brutes des fichiers de polices inclus dans le document et leur analyse. Apparemment, la plupart de ces fichiers sont des polices au format TrueType qui est un format public. Bon point. Cela va être la prochaine étape de l'analyse : serons-nous capables d'extraire ces données et de reconnaître la forme que ces données dessinent ?
|
|
|
| by Didier Guillion | |
|
| |
|
 Si vous êtes utilisateurs de nos produits sur PC, vous avez peut-être eu la malchance de voir apparaître un jour, avant que le programme ne se ferme inopinément, une petite boîte d'alerte vous demandant de nous renvoyer un fichier appelé "crash.log".
De quoi s'agit-il exactement, et quels renseignements peut-il nous apporter?
Je vais tenter d'y répondre, sans trop entrer dans les détails techniques.
Le microprocesseur de votre ordinateur, lorsqu'il est en train d'exécuter une application, utilise, pour stocker les valeurs intermédiaires de ses opérations, une série de mémoires internes appelées "registres".
Il sait à tout moment, grâce à ces registres, à quel endroit il est dans le programme (donc quelle sera la prochaine instruction à effectuer), quelles sont les zones de mémoire auxquelles il va accéder, en un mot tout ce qui définit son état à un instant donné.
Lorsqu'une erreur survient (division par zéro, tentative d'exécuter une instruction inconnue pour ce microprocesseur, tentative de lire ou d'écrire dans une zone de mémoire non valide), le programme s'arrête et génère une "exception".
Ces exceptions, donc la plus connue est numérotée "C0000005" (justement, lecture ou écriture dans une zone de mémoire non valide) sont traitées par défaut par Windows, et provoquent l'apparition d'une boîte disant qu'un problème a été rencontré, et qu'un rapport d'erreur peut être envoyé à Microsoft.
Aux dernières nouvelles, ces rapports d'erreur, à leur arrivée chez Bill, s'ils ne concernent pas des produits Microsoft (et même!), sont envoyés directement dans un dossier spécial, appelé poubelle, corbeille, ou classement vertical selon les jours. Ils ne sont donc d'aucun intérêt pour nous, ni pour personne d'autre, d'ailleurs.
Dans nos produits, nous avons donc remplacé ce traitement inutile par la génération d'un fichier "crash.log", qui contient tous les renseignements nous permettant de savoir ce qui s'est passé:
- Nom et version de l'application
- Date de création de l'application
- Version de Windows de l'utilisateur
- Date et heure du crash (GMT)
- Type d'erreur rencontrée
- Liste des registres du microprocesseur
- Instructions en cours d'exécution lors du crash
- Et enfin, contenu de la "pile", zone mémoire permettant de connaître le sous-programme ayant appelé la fonction en cause, ainsi que le sous-programme ayant appelé ce sous-programme, etc.
A partir de cela, nous pouvons généralement savoir:
- l'application ayant subi le crash, ainsi que sa version,
- la version de Windows,
- approximativement quelle était l'opération effectuée lorsque le crash est survenu (mais pas toujours).
En aucun cas nous ne pouvons connaître le détail de ce que faisait l'utilisateur à ce moment-là, sur quel fichier il travaillait, ce qu'il voyait à l'écran, quelle tête il a fait en voyant apparaître la fenêtre d'erreur (quoique, s'il avait sa webcam branchée...), donc une explication, même succinte, des conditions dans lesquelles cela s'est produit, le fichier en cause, bref tout ce qui nous permet de reproduire le problème chez nous, est absolument indispensable.
Dès que nous pouvons reproduire une erreur à volonté, 99% (ou même plus) du travail est déjà fait, et c'est donc l'assurance d'une correction rapide.
Alors, en pensant à nous, vous pensez aussi à vous... |
|
|
| by Olivier Guillion | |
| |
|
 Les échanges de document musicaux ont toujours été une de nos préoccupations. Chaque logiciel de musique utilise son propre format de fichier, et il est difficile de partager des documents quand on travaille sur des logiciels différents.
En général, le format le plus reconnu est le MIDI. Mais, c'est un format maintenant ancien, que l'on peut qualifier de spartiate et plus destiné aux synthétiseurs qu'aux ordinateurs. Par exemple, le format MIDI ne comporte aucune information de mise en page et l'on se retrouve vite limité car un export puis un import ne redonne pas le même aspect de la partition.
Grâce à MyrScript, le langage intégré à Harmony Assistant, il est possible d'importer des documents musicaux provenant de toutes sortes de logiciels : Finale, Noteworthy, Encore, GuitarPro, Tabledit, etc. Depuis deux ans, une bonne partie de notre temps a été passée à écrire des scripts d'importation, mais il y a tellement de logiciels différents que je ne pense pas que nous en verrons un jour la fin. Il faut en effet, pour chaque logiciel, concevoir un script spécifique, parfois même avec des variantes car les formats ont évolués dans le temps.
Nous réfléchissons depuis quelque temps à une autre approche du problème. L'idéal serait d'avoir un format de fichier qui soit commun à tous les logiciels. Il y a bien l'initiative très intéressante du MusicXML mais cela suppose qu'un exporteur MusicXML existe pour le logiciel. Or, très souvent, les nouveaux utilisateurs de Melody/Harmony utilisaient un programme dont le développement a été arrété, et voudraient bien récupérer les partitions créées avec celui-ci. Ils se retrouvent bloqués.
C'est alors que nous est venue une idée. Un format d'échange existe : c'est le PDF. Que ce soit sur Mac OS X, où l'exportateur en PDF est intégré au système, sur Mac OS 9 où des pseudo pilotes d'impression existent, ou sur Windows avec des programmes gratuits comme PDFCreator, il est aisé de créer un document PDF à partir de n'importe quel logiciel. De plus on trouve une grande quantité de partitions en PDF sur l'Internet notamment sur Choral Public Domain Library.
Si l'on pouvait lire ces fichiers PDF avec Harmony/Melody nous disposerions alors d'un format d'importation universel. La description du format a été publiée par son créateur, Adobe. Une pré-étude a été lancée cette semaine pour voir si ce format est lisible et si l'on peut faire quelque chose de ces données.
Dès que la nouvelle version d'Harmony et de Melody sera publiée (normalement Mardi prochain 9 Mai) nous approfondirons la question. |
|
|
| by Didier Guillion | |
|
| |
|
|
