Scanner des codes-barres

Publié le 02 Aug 2013 dans Algorithmique.

La librairie de référence pour scanner des codes-barres de toutes sortes, qu'ils soient mono-dimensionnels comme EAN13 ou bidimensionnels comme QR-code ou Datamatrix, est ZXing (prononcer « zebra crossing »). Malheureusement, il s'agit d'un travail développé sous Android dont le portage sur iPhone n'est pas terminé : il manque toute la partie 1D. (De plus, j'ai toujours trouvé cette librairie mal « packagée » et peu commode à intégrer dans un projet, mais c'est un autre sujet !)

Ayant justement été confronté au problème de scanner depuis une application iPhone des codes-barres 1D (ceux que l'on trouve au dos des bouquins et sur la plupart des produits manufacturés), j'ai dû développer un algorithme de lecture de code-barres, en m'appuyant sur divers articles que j'ai pu trouver ici et là sur internet, ainsi que sur le code source de ZXing. Je ne vais pas en publier tout le code, qui est long et contient des parties spécifiques à mon application, mais je vous propose d'en détailler le principe de fonctionnement.

Capture de l'image

La première étape est bien sûr de capturer les frames vidéo en provenance de la caméra de l'iPhone. Ce n'est en théorie pas très complexe, mais comme j'ai un peu galéré et que la documentation des framework CoreMedia et CoreVideo est parfois assez sybilline (euphémisme), voici pour vous épargner quelques heures de recherche comment procéder :

- (void)viewDidAppear:(BOOL)animated
{
  AVCaptureVideoDataOutput  * output;
  AVCaptureDeviceInput      * input;
  NSDictionary              * settings;
  dispatch_queue_t            queue;

  // Forward the message to the parent class.

  [super viewDidAppear:animated];

  // Create the video session and configure it
  // to send 640x480 frames.

  session = [[AVCaptureSession alloc] init];
  [session beginConfiguration];
  [session setSessionPreset:AVCaptureSessionPreset640x480];

  // Add a video input device.

  input = [AVCaptureDeviceInput deviceInputWithDevice:[AVCaptureDevice defaultDeviceWithMediaType:AVMediaTypeVideo] error:nil];
  [session addInput:input];

  // Add a video capture output device.

  output = [[AVCaptureVideoDataOutput alloc] init];
  [output setAlwaysDiscardsLateVideoFrames:YES];
  [session addOutput:output];
  [output release];

  // Create a separate queue that will process
  // the video frames and set the delegate.

  queue = dispatch_queue_create("a queue", NULL);
  [output setSampleBufferDelegate:self queue:queue];
  dispatch_release(queue);

  // Configure the capture device so it sends pixels
  // in the BGRA format.

  settings = [NSDictionary dictionaryWithObject:[NSNumber numberWithUnsignedInt:kCVPixelFormatType_32BGRA] forKey:(id) kCVPixelBufferPixelFormatTypeKey];
  [output setVideoSettings:settings];

  // Create the preview layer to display the video in a
  // view of our view controller.

  if (!preview) preview = [AVCaptureVideoPreviewLayer layerWithSession:session];
  [preview setFrame:[video bounds]];
  [preview setVideoGravity:AVLayerVideoGravityResizeAspectFill];
  [[video layer] addSublayer:preview];

  // Commit the configuration and start the
  // camera.

  [session commitConfiguration];
  [session startRunning];
}

Ce code s'insère dans un view controller classique. L'ivar video est une simple UIView dans laquelle apparaitra la video et qui permettra à l'utilisateur de vérifier où il pointe le code barre. Cette view est en réalité une coquille vide, tout le boulot est fait par la couche AVCaptureVideoPreviewLayer insérée dedans (à la fin de la procédure ci-dessus).

Une fois ce view controller initialisé et affiché à l'écran, la caméra commence aussitôt à nous envoyer des frames via la fonction déléguée suivante :

- (void)captureOutput:(AVCaptureOutput *)captureOutput didOutputSampleBuffer:(CMSampleBufferRef)sampleBuffer fromConnection:(AVCaptureConnection *)connection
{
  CVImageBufferRef  image;
  void            * bits;
  int               bpr, width, height;

  // Get the current frame and lock it so data won't get
  // corrupted by the video thread while we are processing
  // them.

  image = CMSampleBufferGetImageBuffer(sampleBuffer);
  CVPixelBufferLockBaseAddress(image, 0);

  // Retrieve the image dimension and a pointer on the
  // image bits.

  bpr = CVPixelBufferGetBytesPerRow(image);
  width = CVPixelBufferGetWidth(image);
  height = CVPixelBufferGetHeight(image);
  bits = CVPixelBufferGetBaseAddress(image);

  // Pass the barcode decoder the image.

  [decoder processSamples:bits width:width height:height bytesPerRow:bpr];

  // Unlock the frame.

  CVPixelBufferUnlockBaseAddress(image, 0);
}

Le piège est ici que la caméra filme en mode portrait, c'est à dire que l'image est tournée de 90°. La variable width contient donc en réalité la hauteur de l'image et la variable height sa largeur ; de même, dans le tableau bits, les données se présentent organisées en colonnes et non en lignes, contrairement à une bitmap classique.

Enfin il faut dire un mot de la résolution optimale à utiliser. La reconnaissance ne fonctionne que si les lignes les plus minces du code-barres occupent au moins 2 ou 3 pixels dans l'image. Si la résolution est basse, cela veut dire que l'utilisateur doit filmer de près, en mode macro. L'inconvénient est que l'iPhone est alors assez lent à faire la mise au point, ce que l'utilisateur peut ressentir comme un manque de réactivité. D'un autre côté, une résolution élevée augmentera le volume de calcul et donc le temps de reconnaissance.

Il faut donc trouver un compromis entre ces deux contraintes. Pour l'instant, dans mes tests actuels, j'utilise une résolution de 640x480. Cela fonctionne bien sur les codes-barres imprimés assez gros pour occuper la majeure partie de l'image, mais les plus petits ne sont pas reconnus. Je verrai à l'usage si c'est acceptable ou non. Dans ces conditions, le temps de décodage est de l'ordre de quelques dizaines de millisecondes sur un iPhone 4.

Localisation du code barre

On part du principe que l'utilisateur doit placer le code à scanner le long d'une ligne repère tracée à l'écran en surimpression sur la preview de la vidéo. On sait donc à peu près où se trouve le code-barres dans l'image et cela nous dispense d'implémenter des algorithmes complexes de recherche de motif. Ce choix semble acceptable compte tenu de la faible puissance de calcul disponible, d'autant plus qu'aligner le code barre avec une ligne repère est naturel et intuitif pour la plupart des utilisateurs : c'est ainsi que fonctionnent les « scannettes » des supermarchés.

On se contente donc d'extraire une cinquantaine de lignes horizontales de part et d'autre du centre de l'image et d'appliquer l'algorithme de lecture successivement à chacune de ces lignes. On parie sur le fait que même en cas de code-barres endommagé, de taches, de poussières, ou de conditions d'éclairage difficiles, au moins quelques-unes de ces lignes traverseront le code-barres entièrement et seront exploitables.

D'expérience, j'ai pu constater que les erreurs de décodage sont fréquentes. Un système de checksum permet de rejeter la plupart des faux-positifs, mais des erreurs réussissent encore à passer. Pour les éviter, j'ai fini par mettre en place un système de « votes ». Pour chaque ligne horizontale donnant lieu à un décodage réussi, je stocke le résultat obtenu. À la fin, je regarde quel code a été obtenu le plus souvent. Si une majorité nette se dégage, et uniquement dans ce cas, je déclare que la lecture a réussi.

Prétraitement de l'image

Il faut plutôt parler de prétraitement de la ligne, puisque tous les algorithmes qui suivent s'appliquent successivement et indépendamment à chacune des cinquante lignes horizontales choisies à l'étape précédente.

On commence par convertir les données en noir et blanc. La couleur n'est pas significative ici, les codes-barres pouvant être imprimés sur tout type de support et de n'importe quelle couleur. Pour cela, j'utilise la formule classique qui donne la luminance Y en fonction des composantes RGB :

Y = 0.299 R + 0.587 G + 0.114 B

Bien sûr, il n'est pas question de faire le calcul en virgule flottante, performance oblige. J'utilise donc l'approximation entière suivante, les composantes R, G et B étant stockées dans des variables uint8_t dont la valeur est comprise entre 0 et 255 :

Y = (((int) R * 76) + ((int) G * 150) + ((int) B * 30)) >> 8;

On filtre ensuite les données. Dans la littérature, certains auteurs recommandent un filtre passe-haut pour accentuer les contours, d'autres un filtre passe-bas pour diminuer le bruit, d'autres enfin ne recommandent rien du tout. Actuellement j'utilise un passe-bas de matrice [1 6 1] et cela semble plutôt bien fonctionner, mais il serait intéressant de faire des tests sérieux pour voir comment évolue le taux de reconnaissance en fonction des caractéristiques de ce filtre.

Il faut enfin binariser l'image (ou plutôt la ligne), c'est à dire réduire le nombre de niveaux de gris à deux. Ceci s'obtient par seuillage : on choisit une valeur de seuil t, tous les pixels qui sont au-dessus sont considérés comme blancs tandis que tous ceux qui sont au-dessous sont considérés comme noir. Deux options sont possibles pour cela.

  • Soit utiliser le même seuil pour toute l'image. Un tel seuil est typiquement déterminé en prenant la moyenne de tous les pixels de l'image, éventuellement plus ou moins quelques pour cent, ou bien en analysant l'histogramme. C'est rapide mais cela ne fonctionne pas sur les images présentant des inégalités d'éclairage.
  • Soit utiliser un seuil adaptatif, c'est-à-dire un seuil dont la valeur est propre à chaque pixel en fonction les caractéristiques locales de l'image. C'est bien plus gourmand en calculs mais cela donne aussi de meilleurs résultats.

J'ai choisi d'implémenter la seconde option, plus précisément un seuillage adaptatif de Niblack. Pour chaque pixel de coordonnée x, on calcule la moyenne m(x) et l'écart type d(x) des 31 pixels du voisinage (soit 15 pixels à gauche et 15 pixels à droite). Le seuil à appliquer à ce pixel est alors :

t(x) = m(x) - 0.2 * d(x)

Bien sûr, un algorithme naïf qui calculerait pour chaque pixel la moyenne et l'écart type des 31 pixels autour demanderait un nombre d'opérations totalement prohibitif. Il existe heureusement des raccourcis pour précalculer les données et ramener le volume de calcul à un niveau acceptable. Pour plus d'information, cherchez image intégrale dans google.

Là encore, quelques tests seraient bienvenus pour voir comment évolue le taux de reconnaissance en fonction des paramètres de calcul de ce seuil. Notamment, si j'augmente un jour la résolution de la caméra, il faudra probablement que j'augmente en conséquence la taille de la fenêtre sur laquelle on calcule ici la moyenne et l'écart type au voisinage de chaque pixel.

À ce stade, on possède donc une cinquantaine de lignes horizontales ne contenant que des pixels à 0 (pour les zones noires) ou à 1 (pour les zones blanches). L'image ci-dessus illustre les traitements effectués jusqu'à présent : à gauche l'image originale, en haut à droite une coupe de l'image passant par la ligne rouge, en bas à droite les données binarisées. (En réalité, pour des raisons techniques, les deux coupes ont été capturées à des moments différents, ce qui explique qu'elles ne soient pas parfaitement alignées et ne correspondent pas exactement.)

Il s'agit maintenant de rechercher dans ces données le motif caractéristique d'un code-barres EAN13.

Reconnaissance du code-barres

Avant de continuer, il nous faut décrire exactement ce que l'on cherche à reconnaître. Un code-barres EAN13 est constitué d'exactement 59 bandes noires et blanches. Pas une de plus, pas une de moins. Chaque bande peut avoir 4 largeurs possibles. La largeur la plus étroite est appelée le module et une bande a forcément une largeur qui est un multiple entier de ce module. Le code-barres complet a toujours une longueur équivalente à 95 fois la taille du module. Enfin, un code comprend toujours les trois zones suivantes :

  • La guard bar gauche, constituée de trois bandes successivement noir-blanc-noir faisant chacune un module de large.
  • Le motif de séparation, en plein centre, constitué de cinq bandes successivement blanc-noir-blanc-noir-blanc faisant chacune un module de large.
  • La guard bar droite, identique à celle de gauche.

Pour reconnaitre efficacement ces motifs, il nous faut changer complètement le mode de représentation des données. Pour l'instant, nous avons une succession de pixels à 0 et à 1 le long de la ligne de scan. Ce dont nous avons besoin, c'est d'une liste de bandes noires et de bandes blanches, avec pour chacune, leur largeur en pixels.

L'algorithme pour passer à un tel mode de représentation est trivial. On part avec une liste initialement vide. Puis on parcourt entièrement la ligne de pixels de gauche à droite. À chaque fois que l'on termine de traverser une suite de 0, on ajoute une bande noire à la liste, à chaque fois que l'on termine de traverser une suite de 1, on ajoute une bande blanche. À chaque fois, bien sûr, on stocke également la largeur de ces bandes, c'est à dire le nombre de pixels traversés.

Pour simplifier la suite, il est commode d'avoir toujours une bande noire en premier. Ainsi, dans la liste obtenue, on sait que toutes les bandes dont l'index est impair sont noires et que toutes celles dont l'index est pair sont blanches (ou l'inverse si le tableau commence à zéro comme en C…). C'est facile à obtenir, il suffit de sauter les premiers pixels de la ligne si ceux-ci sont blancs. De toute façon, il est peu probable que des informations intéressantes se cachent dans ces premiers pixels.

Nous avons maintenant une liste de bandes alternativement noires et blanches. L'idée consiste à passer dessus un « masque glissant » de 59 bandes de larges (rappelez-vous qu'un code EAN13 comprend toujours 59 bandes), afin de voir si ce qui se trouve sous le masque a une chance d'être un code-barres valide. Bien sûr, si à ce stade on n'a pas au moins 59 bandes, il est inutile d'aller plus loin. Si en revanche on a reconnu par exemple 70 bandes, alors il y aura 70 - 59 + 1 = 12 positions possibles à tester pour le masque. En réalité, il n'y en a même que 6 puisque l'on sait qu'un code-barres commence toujours par une bande noire. Un masque en position paire correspondrait à un code-barres commençant par une bande blanche, ce qui est impossible. Il est donc inutile de tester ce cas.

Le test qui va permettre de discriminer les bons et les mauvais candidats porte donc sur la couleur et sur la largeur des bandes. Pour savoir si ce qui se trouve sous le masque peut être ou non un code-barres valide, on vérifie que les bandes 1, 2 et 3 forment le motif noir-blanc-noir, que les bandes 28, 29, 30, 31 et 32 forment le motif blanc-noir-blanc-noir-blanc, que les bandes 57, 58 et 59 forment le motif noir-blanc-noir, et enfin que toutes ces bandes ont une largeur égale (à plus ou moins 25%, soyons tolérants) à 1/95ème de la distance entre les bandes 1 et 59. Voici le code qui effectue ce test :

// Try to find a 59-strip wide pattern that could match
// an EAN13 barcode. Bars at even index are known to be black
// and bars at odd index are known to be white.

cx = count - 59 + 1;
for (i = 0; i < cx; i += 2)
{
  // First, supposing this position matches a barcode, compute
  // the corresponding module size. Then, determine acceptable
  // min and max bounds for the size of a one-module bar.

  tmp = bars + i;

  module = (float) (tmp[58].position + tmp[58].width - tmp[0].position) / 95.0f;
  minwidth = (int) floorf(module * 0.75f);
  maxwidth = (int) ceilf(module * 1.25f);

  // Check the presence of the guard bars. The first guard bar should be
  // BWB at the leftmost position, the seconde one should be WBWBW at the
  // center of the barcode, and the last one should be BWB at the rightmost
  // position.

  if (tmp[ 0].width >= minwidth && tmp[ 0].width <= maxwidth &&
      tmp[ 1].width >= minwidth && tmp[ 1].width <= maxwidth &&
      tmp[ 2].width >= minwidth && tmp[ 2].width <= maxwidth &&
      tmp[27].width >= minwidth && tmp[27].width <= maxwidth &&
      tmp[28].width >= minwidth && tmp[28].width <= maxwidth &&
      tmp[29].width >= minwidth && tmp[29].width <= maxwidth &&
      tmp[30].width >= minwidth && tmp[30].width <= maxwidth &&
      tmp[31].width >= minwidth && tmp[31].width <= maxwidth &&
      tmp[58].width >= minwidth && tmp[58].width <= maxwidth &&
      tmp[57].width >= minwidth && tmp[57].width <= maxwidth &&
      tmp[56].width >= minwidth && tmp[56].width <= maxwidth)
      {
        if ([self decode:tmp module:module line:theLine])
        {
          // Successful decoding. Save time by aborting the
          // loop now.

          break;
        }
      }

  // If we get here, this position was not recognized as a possible
  // candidate. Increment by 2 (so bars[i] is always a black bar) and
  // try again.
}

Je choisis de sortir de la boucle dès qu'un décodage a réussi. Il est en effet peu probable qu'une autre position du masque donne également lieu à un décodage valide. Là encore, comme pour plusieurs autres paramètres de l'algorithme, des tests sérieux seraient à faire pour vérifier le bien-fondé de cette option.

Décodage de l'information

Le test du masque glissant nous fournit donc une liste de candidats potentiels au statut de code-barres. Il s'agit maintenant d'esssayer de les décoder pour savoir si l'on obtient quelque chose de pertinent et de cohérent.

L'encodage de l'information à l'intérieur d'un code EAN13 est particulièrement complexe et je vous renvoie à la page wikipédia correspondante pour plus de détails. Il sera suffisant ici de savoir que chaque symbole est toujours représenté par 4 bandes (2 noires et 2 blanches). Ce sont les largeurs relatives de ces bandes les unes par rapport aux autres qui encodent l'information, selon 30 motifs possibles. Étant donné qu'il y a 30 motifs possibles pour représenter seulement 10 symboles différents (les chiffres de 0 à 9), cela veut dire que chaque chiffre peut être encodé de 3 façons différentes ; le choix de la façon d'encoder chaque chiffre encodant en lui-même de l'information supplémentaire.

La difficulté est que le code-barres peut être endommagé, légèrement flou (surtout s'il est photographié de trop près) ou encore déformé (s'il est imprimé sur un objet cylindrique par exemple). Une bande qui doit faire en théorie 3 modules de large pourra donc faire parfois un peu plus, parfois un peu moins. Par ailleurs, la physique à l'œuvre dans une caméra CCD et les traitements que le hardware fait subir à l'image avant de la passer à notre application font que la largeur des bandes peut être altérée par leur luminosité. Par exemple, la largeur des bandes sombres peut être systématiquement sous-évaluée et celle des bandes claires systématiquement sur-évaluée. Un algorithme naïf qui consisterait à prendre chaque groupe de 4 bandes un par un pour essayer de le mettre en correspondance avec chacun des 30 motifs possibles ne fonctionnera donc pas. Il faut un peu plus de souplesse et de tolérance.

Après avoir testé quelques algorithmes, j'ai choisi d'utiliser un classificateur basé sur une mesure de distance. On génère l'aspect que les 30 motifs possibles devraient théoriquement avoir, compte tenu des paramètres que l'on connait sur notre code-barres en cours de décodage : largeur moyenne des bandes blanches et des bandes noires dans les guard bars, notamment. Puis on mesure le degré de ressemblance entre le motif réel à reconnaitre et chacun des 30 motifs théoriques. Le motif le plus ressemblant, autrement dit celui dont la distance est la plus faible, est considéré comme reconnu. Cette distance est calculée de la façon suivante :

d = (th1 - bar1)² + (th2 - bar2)² + (th3 - bar3)² + (th4 - bar4)²

Où th1 à th4 sont les tailles théoriques des 4 bandes noires et blanches, tandis que bar1 à bar4 sont les tailles réelles des 4 bandes dans la portion du code-barres en cours de décodage. (En réalité cette formule donne le carré de la distance, mais on peut économiser l'appel à la fonction racine carrée puisqu'on ne cherche qu'à comparer les valeurs entre elles et non une valeur absolue.)

En répétant cet algorithme de la « distance minimale » à chacun des groupes de 4 bandes du code-barres (hormis bien sûr les guard bars et le motif central de séparation), on décode l'ensemble des douze symboles présents. On peut alors déduire le treizième symbole (le chiffre le plus à gauche, souvent écrit un peu à l'écart sous le code-barres). Ce dernier symbole n'est pas encodé directement, mais déduit implicitement de la façon dont les douze autres symboles sont encodés. Encore une fois, je vous renvoie à wikipédia pour plus d'information.

Calcul du checksum

À ce stade, les erreurs de décodage sont encore nombreuses. On pourrait probablement les réduire en plaçant un seuil minimal de ressemblance entre les motifs réels et les motifs théoriques lorsque l'algorithme de classification décode les symboles à l'étape précédente. En pratique, je n'ai pas trouvé de bonne valeur pour ce seuil. Trop bas, il empêche la reconnaissance des codes-barres endommagés ou déformés ; trop haut, il ne sert à rien. J'ai donc préféré ne pas en mettre et m'appuyer sur le checksum pour lever les dernières ambiguïtés.

Le code EAN13, tout comme les numéros de carte bancaire ou les numéros de Sécurité Sociale, contient en effet un checksum qui permet de vérifier la validité et la cohérence des informations. Dans le cas qui nous intéresse, ce checksum est calculé de la façon suivante :

S13 = 10 - (S1 + 3*S2 + S3 + 3*S4 + S5 + 3*S6 + S7 + 3*S8 + S9 + 3*S10 + S11 + 3*S12) % 10

Où les valeurs S1 à S13 correspondent à chacun des 13 chiffres encodés dans le code-barres, S1 étant le plus à gauche et S13 le plus à droite. Il suffit donc de s'assurer que le code que nous avons obtenu à l'étape précédente vérifie cette équation pour éliminer les faux positifs.

En pratique, ce n'est pas infaillible. Il arrive que par malchance le checksum tombe juste alors que le code-barres est mal décodé. Ces derniers cas sont alors rejetés par le système de « votes » décrit au début de cet article.