はじめに

※この記事はRICORA Advent Calendar 12/2 の記事になります。

本記事ではPharmacodeというバーコードの認識アルゴリズムの実装について解説します。

Pharmacodeを認識できるプログラムは今の所一般には公開されていないので、こちらが唯一の公開されている実装になります。もちろんライセンスはフリーなのでアプリケーションに利用したい方がいたら是非利用してください！

また、私自身バーコード認識にそこまで詳しくないのでアルゴリズムが最適でない可能性が高いです。バーコード認識などに詳しい方がいましたら是非アルゴリズムなどに助言をいただきたいです。

Pharmacodeとは？

概要

Pharmacodeはドイツの製薬会社が開発した医薬品パッケージ用のバーコードです。現在も医療業界ではかなり使われているそうです。バーコードはシンプルな設計になっていて様々な色の組み合わせに対応ができます。*1

Pharmacodeは通常のバーコードと違ってアルファベットを含まない正の整数を表します。
規定だとPharmacodeは3~131070の数値を表すものとされていますが、理論上無限の値を表現することができます。

Pharmacodeのデコード

Pharmacodeのデコードは非常にシンプルで手計算でも簡単に値を求めることができます。*2

Pharmacodeは「空白」「黒い太線」「黒い細線」の3種類の区間で構成されます。
細線と太線に右から0,1,2...と番号を付けて次のように計算を行います。

i番目の線が太ければ$2^{i+1}$を加算する
i番目の線が細ければ$2^i$を加算する

2の塁上を用いて計算を行うというわけです。これに従って計算を行うと、上記のPharmacodeは以下のようにデコードできます。

$2^0 + 2^1 + 2^3 + 2^4 + 2^5 + 2^5 = 1 + 2 + 8 + 16 + 32 + 32 = 91$

Pharmacodeは簡単に生成できるサービスがあるので計算や生成を行ってみたい人は試してみてください。

認識アルゴリズムの実装

上述した仕様を踏まえてPharmacodeを認識するアルゴリズムを実装してみましょう。

サンプルに使用した画像です⇣

画像の前処理

画像を解析していく前にバーコードの性質が利用しやすいように画像を変換します。
具体的にはバイナリ化を行って画像全体を白黒の2値に変換します。

バイナリ化の前にはグレイスケール化を行う必要があります。RGBの3チャンネルだった画像を1チャンネルに変換します。

グレイスケール化された画像⇣ (画像に写っている物体の関係で違いがわかりにくいです)

画像がグレイスケール化できたらバイナリ化を行います。OpenCVではcv2.thresholdという関数で簡単に2値画像に変換できます。

バイナリ化された画像⇣

他にもグレイスケール画像に対してブレに対応するためにガンマ補正と鮮鋭化という画像処理を行っています。ここでは説明を省略するので興味がある人は詳しく解説がされているサイトを参考にしてください。*3 *4

水平ラインごとの解析

バーコードが通常の向きで置かれていることと、バーコードが含む黒線の本数が一定(今回は9本)であるという仮定をしてアルゴリズムを構築していきます。

バーコードの特徴量といえば周波数成分です。バーコードが存在している画像中の水平ラインを抽出してみましょう。

画像上の緑色のラインをグラフ化⇣

ここでは白が1黒が0となっています。
グラフからバーコードの領域に特定のパターンが発生していることがわかります。この部分を発見＆デコードできればPharmacodeを検出することができそうです。

この区間の発見にはPharmacodeの「空白」が必ず同じ間隔で並んでいるという条件が効いてきます。

具体的には以下のようなアルゴリズムで水平ラインが解析できます。

同じ長さの「空白」が一定区間連続している部分をバーコード領域の候補として検出
検出された領域の「黒線」が「空白」よりも太いか細いかを判定
右の黒線から順にデコード計算を行う

これだけだとノイズもかなり検出されてしまうので条件は多少厳しくしておきます⇣

1は「空白」の長さの平均分散を使って外れ値がないかチェック
2は黒線が太すぎたり細すぎたりしていないかチェック

アルゴリズムは書き出すときれいにまとまっていますが実装は思ったより大変です。（汗）

これで水平ライン上のバーコードを検出することができるようになりました、後は結果を画像全体の結果をまとめましょう。

解析結果の結合

先程の検出を画像全体にかけるとバーコードのある区間は連続して同じ値が検出されているはずです。

バーコード領域の範囲は緑先の内側⇣

上記の画像の緑線の範囲は755が検出されています。他の領域はバーコードらしきものがないので結果を0としています。

バーコードがある画像には同じ数値が連続した区間が存在するはずなので、一定より長く同じ数値が続いたらバーコードと認識することにします。
何らかのノイズで区間の途中で0が検出されてしまう可能性もあるので周りの数値も考慮した補完を行っておきます。

これでPharmacodeを画像から検出することができました！次に複数の検出が行えるようにします。

検出結果⇣

複数検出の実装

複数の検出を行うアルゴリズムを考えるのは大変です。今回は単体の検出が十分速くできていたので複数検出はシンプルなアプローチで行ってみたいと思います。

方法は簡単でPharmacodeを1つずつ検出していきます。検出されたPharmacode領域の上を黒く塗りつぶして次の検出を行います。
検出の優先順位は左上が優先になるようにしておきます。

塗りつぶしを行った画像⇣

これで複数のPharmacodeが検出できるようになりました。検出アルゴリズムは以上になります。

複数Pharmacodeの検出結果⇣

高速化の工夫

検出の高速化を行うためにいくつか工夫した点があります。

実装をPythonからC++に移植
各ラインの解析を並列化
ラインの解析を一定区間スキップできるように(3行に1回だけ解析を行う)

Forループをたくさん使っているのでPythonからC++に愚直に移植することで100倍近く高速化されました。
バーコード領域は複数ラインにまたがっているのでn行に1回だけ解析を行うようにしても十分検出することができます。処理が大幅に削減できるので大幅な高速化に繋がりました。

パフォーマンス計測

条件

画像の読み込みからスタートしてバーコード認識の結果を受け取るところまでを100回繰り返して平均パフォーマンスを計測しました。
またロバストに認識ができる設定と高速に認識ができる設定の2種類を用意してみました⇣

画像の前処理を行って毎行解析を行う
画像の前処理を行わず3行に1回解析を行う

デバイスはメインPCとエッジデバイスの代表としてラズパイ3Bを比較しました。

画像は3つのPharmacodeが含まれているものを使用しました⇣

結果

設定	Core i7-10700K	Raspberry-pi 3B
ロバスト	5.4 ms (185 fps)	104 ms (9.6 fps)
高速	3.1 ms (322 fps)	35 ms (28.5 fps)

IntelのCPUではかなり高速に動作していることがわかります。
ラズパイでも高速な設定を使用すれば十分リアルタイムで動作させることができることがわかりました！

最後に

ここまで記事を読んでいただきありがとうございます。
冒頭にも書きましたがバーコードの認識のアルゴリズムに詳しい方がいましたら是非アルゴリズムの改善に協力していただきたいです。また、これから画像処理を勉強しようとしている方の手助けになったら幸いです。バーコードやQRコードの認識は画像処理の入門としてちょうどいいタスクな気がしたので積極的に取り組んでアウトプットをしてみてください！

実装については最初にPythonで大枠のアルゴリズムを書いてからC++に実装を移行するという形で行いました。OpenCVを使うプログラムは書き換えがとても簡単なので画像系の開発を行っている人はこの順番で実装をしてみると意外とスムーズに実装できると思います。可視化が得意なPythonでは画像処理のデバックなどが非常に簡単に行うことができます。

このバーコード認識は学園祭のサークル活動紹介展示用に作成しました。
この記事もサークルのAdventカレンダー用にアウトプットの一環として作成しています。

今回の開発のアウトプットについて紹介します。

学園祭での展示

11月下旬に行われた学園祭でサークルの活動紹介として展示させていただきました⇣

少し見辛いですがRaspberry-pi 3Bにウェブカメラを接続して実行しています。(ノートPCは自動でスライドショーを実行)
親子で来ていて熱心にアルゴリズムを聞いてくれた方もいました。質問してくれた子供が少しでもプログラミングに興味を持ってくれたら展示者としてとても嬉しいです。

説明用スライドの作成

展示の説明用にスライドも作成しました。お時間があれば見ていだだけると幸いです。

Barcode Recognition / pharmacode-decoder- - Speaker Deck

実装

GitHub上で実装を公開しています。
C++で実装したので高速に動作します。アプリケーションに利用してみたい方は是非使ってみてください。

参考文献

1 - Pharmacodeについて

2 - Pharmacodeのデコード

3 - ガンマ補正について

4 - 鮮鋭化について