こんにちは！Mercari Advent Calendar 2020 の3日目は、メルカリWebPlatformチーム/Software Engineerの@_mkazutaka がお送りします。普段はメルカリのウェブ周りの開発をしておりGoやPHPやTypeScriptを書いています。

メルカリでは半期に一度エンジニアのためのお祭りMercari Hack Weekを開催しています。この記事では、第2回Mercari Hack Weekから筆者が取り組んでいるRust/Wasmを使ったバーコードリーダについて紹介します。

こちらプロダクションには出してるものでありません。お願いすればプロダクションへのリリースを許してもらえたと思いますが、筆者自身が出さない選択肢を取ったのでそれも含めて紹介します。

(注釈: いくつかの画像処理の話が出てきますが、筆者は画像処理の専門家でもなければ大学院で研究してたわけでもありません。画像処理はほとんど初めてです。使っている手法も古いかもしれません。お見苦しい点あったら申し訳ないですがご了承のほどお願いします。

はじめに

メルカリのアプリには商品のバーコードをスキャンすると情報を自動で読み取って記述してくれるバーコード出品という機能があります。一方でウェブにバーコード出品の機能はありません。これはウェブサービスだからできないというわけではありません。実際にeBayはウェブ上で動くバーコードリーダを開発しています(参考: WebAssembly at eBay: A Real-World Use Case)。

ウェブでもバーコード出品を実現するには、バーコードを読み取るためのバーコードリーダを実装しなければなりません。いくつか方法があります。例えば

・JavaScriptのライブラリを使う
・C系の言語で書かれているものをWasmにコンパイルして使用する

などがあります。最も短時間で実現可能な手法は前者のJavaScriptなのですが今回はWasmを使いたかったので選択肢から外します。後者のWasmはサイズが大きくなりがちです。ウェブの場合、端末にキャッシュなどをしない限り、アクセス毎にお客さまのネットワークリソースを消費してします。そのため必要以上にサイズを大きくしてしまう後者の手法も個人的に避けたいので、こちらも選択肢から外します。

というわけで、Wasmでかつなるべくサイズの小さいバーコードリーダを作ることを目標に0から開発しました。

バーコードを読み取るまでの流れ

バーコード読み取りの流れを3つにわけると以下のようになります。

1. 画像の下処理
2. バーコードの検出
3. バーコードの読み取り

流れを画像にすると下図になります。

画像の下処理

画像の下処理フェーズでは、画像の二値化を行います。二値化とはある閾値に従って画像を白か黒にわける処理をいいます。

今回は画像の分離度が最大となることを目指した判別分析法(大津の二値化)を用いて画像の二値化を行います。OpenCVといったライブラリには判別分析法が実装されているのですが、残念ながら今回の目標と合うものはなかったので自分で作ります。なお、閾値の作成にはRed値のみをみています。バーコードはほとんどの場合黒色なので単一のカラー値を見れば十分だろうという考えからです。
これを実装したコードはこちらになります。

次のバーコード検出フェーズでは画像が白の画素で囲まれていることが前提となっております。画像を白の画素で囲う処理も行います。
これを実装したコードはこちらになります。

フェーズが終了すると画像は以下のようになります。
←Before →After

バーコードの検出

次にバーコード検出を行います。
本記事で実装する処理を紹介する前に、JavaScriptで作られているバーコードリーダの一つQuaggaJSについて紹介します。

QuaggaJSは、画像を格子状に分割し、その中から複数の平行線をもつものを見つけることでバーコードを検出しています(詳しくはHow barcode-localization works in QuaggaJS)。ステップとしては以下のようになります。

1. 画像を格子上のセルに分割
2. 平行線を見つけるための画像のスケルトン化
3. スケルトン化によって作成された線をラベリング
4. ラベリングされた線の特徴からさらにセルを分類
5. 分類したセル中からバーコードグループの選択

ラベリングにはFu Changらの "A Linear-Time Component-Labeling Algorithm Using Contour Tracing Technique" の手法を参考にしています。

本記事の実装はQuaggaJSのステップを参考にしていますが、いくつかは省略しています。本記事での実装ステップとしては下記のようになります。

1. 画像全体をスケルトン化し、線をラベリング
2. ラベリングされた線を分類
3. 分類した線からバーコードグループの選択

スケルトン化とラベリングにはQuaggaJSと同様に "A Linear-Time Component-Labeling Algorithm Using Contour Tracing Technique" の実装(Code Project)を再実装しています。
これを実装したコードはこちらになります。

ラベリングの結果は下図になります。またそれぞれの線をコンポーネントと呼びます。

次にコンポーネントの分類をします。それぞれのコンポーネントの重点・角度・斜辺などを求め分類しています(学術的にはおそらくここが最も重要なのですが、時間がなかったので簡易実装で済ませています)。分類後バーコードグループを検出した結果が以下のようになります。
これを実装したコードはこちらになります。

バーコードの読み取り

バーコードグループを読み取る前に、簡単にバーコードについて説明します。

バーコードは白の隙間と黒の線幅の組み合わせで番号を示します。例えば白黒の比率が3:2:1:1の場合は0、2:2:2:1の場合は1を表します(詳しくはバーコードの仕組みと作成方法 – piyajk.com)

白黒の比率はビット列で表せます。例えば0を表現する場合、ビット列は[0, 0, 0, 1, 1, 0, 1]となります。バーコードを読み取るには、バーコードのビット列の比率とバーコードで定められている数字の比率を比べ最もマッチするものを選択します。
これを実装したコードはこちらになります。

バーコードのビット列を画像から読み取るために直線を引きます。本記事では擬似的な直線を引くためにブレゼンハムのアルゴリズムを使います。実装には expenses/line_drawing を使います。ブレゼンハムのアルゴリズムを使い直線を引くと下図のようになります。

読み取った画素列からバーコード読み取りを行えば完了です！

デモ

実際にコードを動かしたデモが下記のようになります。バーコードを読み取れることがわかります。

なぜプロダクションに出さなかったのか

メルカリはプロダクションに出したいといえば調整をしてくれる良い企業です(たぶん)。
とはいえ、作ったからという理由だけでプロダクションに出すのは会社にとっておそらく価値はないだろうと筆者が判断しました。

具体的には以下の点です。

・需要がわからない。おそらく少ない
・長くメンテナンスされているQuaggaJSやZXingといったオープンソースライブラリがすでにある
・メンテナンスコスト・学習コストが高い。Rust/Wasmの知識のみならず、バーコードに対する知識も必要

上記の理由から実装してメンテナンスしていくにはコストパフォーマンスが悪いと感じたのでブログ記事という形で落ち着かせることにしました。

とはいえ、OSSで公開しているので興味がある方はぜひ使ってみてください。

作ってみての感想

ここまで読んでいただきありがとうございました。バーコードリーダとしての形を最終的に作れて良かったです。

普段の実装以上に苦労したのはどの論文を選ぶかでした。記事中では1つしか論文について述べていないのですが、実際にはさまざまな論文を読みました。実装を進めていくうちに速度が遅い事に気づいて別の手法に書き直したりしました。

本当はもう少し小さいサイズで実現できると思っていたのですが(10KBぐらい)、蓋を開けると30KBほどになっていました。メモリアロケータ周りの設定を変えるなどすれば小さくなる気がします。
あとはJavascriptからWasmに画像ファイルを渡す際のオーバーヘッドはあるのかとかQuaggaと比較して、精度・速度はどれくらいかは考察したいですね。時間があれば追記します。

今回の内容はおそらくHack Weekという期間がなければおそらく挑戦することはなかったです。メルカリの規模の会社でゼロ知識で画像処理に挑戦できる機会はほとんどないので非常にいい機会をいただけました。今回、筆者は一人で実装に挑みましたが、Hack Weekはプロダクトマネージャとタッグ組んで参加も可能です。なによりWasmとかRustとかで自由に開発できるので最高ですよ！

おわりに

今回の記事が読んで頂いた皆様のお役に立てば幸いです。

メルカリではミッション・バリューに共感できるソフトウェアエンジニアを募集しています。Hack Weekといったエンジニアが自由に開発やオラオラできる期間もあるので楽しく働けます！

採用情報

明日のMercari Advent Calendar 2020 執筆担当は、 Engineering Office の Rafael さんです。引き続きお楽しみください。最後までお読み頂きありがとうございました。