QRコードの検出のAPIを振り返る(2回目)

• この記事はOpenCV アドベントカレンダー 24日目の記事です19日目の記事です。空きが出たので前倒しにしました
• クリスマスイブですね

TL;DR

• 丸め誤差を本気でFIXするのは割りに合わない
• 私は諦めました

はじまりのものがたり

• 3年前に前に書いたOpenCVでQRコードを読み取る方法を書いたときに、多少のbug fixをしたのでそのノウハウを公開しました
• また、当時 x86_64 ではPASSするのに、Aarch64だとFAILするテストがありました
• 当時は結局画像差し替えで対応しました
• 現在でも、公式のArm向けビルドマシンでは、このテストが明示的にスキップされている
  • この記事執筆で初めて知ったが2021年12月12日時点でArm向けビルドJenkinsサーバが沈黙している
  • 2021年初頭から稼働していたのだが、そのうち復活するのだろうか

それから

• 手元のビルドファームで、QRコードのテストが再度FAILUREするようになったのを確認しました
• 経験から、「多分丸め誤差だろうな」となんとなく感じていたのですが、丸め誤差のテストを直すのは調査の労力の割に合わないと思っていたので、しばらく放置してました
• ただ、喉に刺さった魚の骨が如く気持ち悪かったので、時間が空いたときに、テストの中身を覗いてみた

エラーメッセージ

[ RUN      ] Objdetect_QRCode_Close.regression/0, where GetParam() = "close_1.png"
/opencv-fork/modules/objdetect/test/test_qrcode.cpp:320: Failure
Value of: corners.empty()
  Actual: true
Expected: false
[  FAILED  ] Objdetect_QRCode_Close.regression/0, where GetParam() = "close_1.png" (270 ms)

テストコード

• ちなみに当該テストコードはこちら

objdetect/test/test_qrcode.cpp

typedef testing::TestWithParam< std::string > Objdetect_QRCode_Close;
TEST_P(Objdetect_QRCode_Close, regression)
{
    const std::string name_current_image = GetParam();
    const std::string root = "qrcode/close/";
    const int pixels_error = 3;

    std::string image_path = findDataFile(root + name_current_image);
    Mat src = imread(image_path, IMREAD_GRAYSCALE), barcode, straight_barcode;
    ASSERT_FALSE(src.empty()) << "Can't read image: " << image_path;
    const double min_side = std::min(src.size().width, src.size().height);
    double coeff_expansion = 1024.0 / min_side;
    const int width  = cvRound(src.size().width  * coeff_expansion);
    const int height = cvRound(src.size().height  * coeff_expansion);
    Size new_size(width, height);
    resize(src, barcode, new_size, 0, 0, INTER_LINEAR);
    std::vector<Point> corners;
    std::string decoded_info;
    QRCodeDetector qrcode;
#ifdef HAVE_QUIRC
    decoded_info = qrcode.detectAndDecode(barcode, corners, straight_barcode);
    ASSERT_FALSE(corners.empty());

• テスト用の画像が読めなかった場合の処理とかもあるので、一部省略すると、こんな感じのコードになる

    Mat src = imread(image_path, IMREAD_GRAYSCALE), barcode, straight_barcode;
    resize(src, barcode, new_size, 0, 0, INTER_LINEAR);
    QRCodeDetector qrcode;
    decoded_info = qrcode.detectAndDecode(barcode, corners, straight_barcode);
    ASSERT_FALSE(corners.empty());

• テストコードを掻い摘んで解説すると画像を読み込んで、QRCodeDetectorに渡したら結果であるcornersが空っぽだったということである。
• 前回の解説記事に書いたように、このcornersにはQRコードの四隅のうち3箇所にある大きい四角の座標が入って返ってくる。

デバッグ開始

• もうちょっと深入りしてみる
• 今度はライブラリ内部のソースコードを覗いてみる

cv::String QRCodeDetector::detectAndDecode(InputArray in,
                                           OutputArray points_,
                                           OutputArray straight_qrcode)
{
    Mat inarr;
    if (!checkQRInputImage(in, inarr))
    {
        points_.release();
        return std::string();
    }

    vector<Point2f> points;
    bool ok = detect(inarr, points); // ここで false が返ってくるのが確認できる
    if (!ok)
    {
        points_.release();
        return std::string();
    }

• QRコードのdetect処理はステップごとに勧められており、途中で失敗すると空文字が返る。
• このとき、points_は空っぽにされてから返されるので、points_が空っぽということは検出で処理が失敗したことを意味する。
• では、detect関数内では何が起きているのか。我々探検隊はアマゾンの奥地へと進まずにコードを読み進めた

x86_64版

• ここから先はプラットフォームで結果に差異が出るのでプラットフォームごとに結果を書いていくことにする
• x86_64版、いわゆる64bit版Windowsでの結果

qrcode.cpp

bool QRCodeDetector::detect(InputArray in, OutputArray points) const
{
    Mat inarr;
    if (!checkQRInputImage(in, inarr))
        return false;

    QRDetect qrdet;
    qrdet.init(inarr, p->epsX, p->epsY);
    if (!qrdet.localization()) { return false; }

• 最初のcheckQRInputImageは画像のサイズ、フォーマット、チャンネル数のチェックなどが行われる¹
• このチェックにパスすると、次はQRDetectのlocalizationに突入する。

qrcode.cpp

bool QRDetect::localization()
{
    CV_TRACE_FUNCTION();
    Point2f begin, end;
    vector<Vec3d> list_lines_x = searchHorizontalLines();
    if( list_lines_x.empty() ) { return false; }
    vector<Point2f> list_lines_y = separateVerticalLines(list_lines_x);
    if( list_lines_y.empty() ) { return false; }

• localization関数では、前回説明した通り隅にある四角いマーカっぽい場所をまず水平スキャンで探し、その後候補点を垂直方向に検証する
  • 詳しくは前回の記事参照
• で、見つからないと空っぽの候補が返ってくるので、list_lines_xもしくはlist_lines_yが空っぽだと検出に失敗となる
• x86_64、Windows 10 Pro 10.0.19042 、Visual Studio 2017 (15.9.13)で試したところ、
  • list_lines_xは91個
  • list_lines_yは5個検出された

Aarch64 版

• Aarch64版、要は64bit版Armと銘打ったが、Armv7(32bit版Arm)でも状況は変わらない
• 検出されない原因はlist_lines_xとlist_lines_yにある
• GCCで計算した結果
  • list_lines_xは93個
  • list_lines_yは空っぽで返ってきた
• どうやら原因はここにあるらしい

separateVerticalLine

qrcode.cpp

vector<Point2f> QRDetect::separateVerticalLines(const vector<Vec3d> &list_lines)
{
    CV_TRACE_FUNCTION();
    const double min_dist_between_points = 10.0;
    const double max_ratio = 1.0;
    for (int coeff_epsilon_i = 1; coeff_epsilon_i < 101; ++coeff_epsilon_i)
    {
        const float coeff_epsilon = coeff_epsilon_i * 0.1f;
        vector<Point2f> point2f_result = extractVerticalLines(list_lines, eps_horizontal * coeff_epsilon);
        if (!point2f_result.empty())
        {
            vector<Point2f> centers;
            Mat labels;
            double compactness = kmeans(
                    point2f_result, 3, labels,
                    TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 10, 0.1),
                    3, KMEANS_PP_CENTERS, centers);
            double min_dist = std::numeric_limits<double>::max();
            for (size_t i = 0; i < centers.size(); i++)
            {
                double dist = norm(centers[i] - centers[(i+1) % centers.size()]);
                if (dist < min_dist)
                {
                    min_dist = dist;
                }
            }
            if (min_dist < min_dist_between_points)
            {
                continue;
            }
            double mean_compactness = compactness / point2f_result.size();
            double ratio = mean_compactness / min_dist;

            if (ratio < max_ratio)
            {
                return point2f_result;
            }
        }
    }
    return vector<Point2f>();  // nothing
}

• この関数を紹介するのは3年ぶり2度目であるが、前回紹介したときは白黒の画素数とその比率を計算していた。
  • 3年の間に同様の実装は extractVerticalLinesに移り、本関数内ではしきい値を調整しながらextractVerticalLinesを繰り返し呼んでいる

一部抜粋

    for (int coeff_epsilon_i = 1; coeff_epsilon_i < 101; ++coeff_epsilon_i)
    {
        const float coeff_epsilon = coeff_epsilon_i * 0.1f;
        vector<Point2f> point2f_result = extractVerticalLines(list_lines, eps_horizontal * coeff_epsilon);
        if (!point2f_result.empty())
        {

• extractVerticalLinesの第2引数はしきい値を意味しており、値が小さいほどしきい値は厳しい。
  • この閾値を100段階に緩めながら四角いマーカを探していく
  • 以前の記事ではこのしきい値がハードコードされていたのだが、柔軟にしきい値調整しながら探索する模様である。
• 丸め誤差でどこで挙動が変わるのか確認するために、大まかにコードの内容を解説する

解説

qrcode.cpp

            vector<Point2f> centers;
            Mat labels;
            double compactness = kmeans(
                    point2f_result, 3, labels,
                    TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 10, 0.1),
                    3, KMEANS_PP_CENTERS, centers);
            double min_dist = std::numeric_limits<double>::max();

• キーポイントになるのはここで呼んでいるkmeans関数である
• k-means法とはクラスタリングの方法で、複数の点を近いもの同士グループに分けて、それぞれの中心座標を返す。
  • ここでは固定で3グループに分けるように設定してある(第2引数の3が期待するグループ数を表す。第5引数の3は反復回数を意味する)
• 理由を察するに、四角いマーカの中央近辺では、複数の候補点が見つかる可能性があるから、だと思う。
• 繰り返しになるがQRコードは以下のように、四隅のうち3箇所に特徴的なマーカが付いている（仕様で策定されている）

• searchHorizontalLinesとseparateVerticalLinesの両方をパスした点は、この3箇所の座標を表していることが期待される
• 一方で、多少のノイス、撮影位置などにより、1ピクセルだけ検出されるより複数候補が発見される可能性がある
  • つまり、3箇所にあるマーカを検出するのに、ピクセルごとに判定を行っているため、複数のピクセルが見つかってしまう可能性が十分にありうる

• そのため、複数のピクセルが見つかった場合でもk-means法で3クラスに分類して、「3つの座標」に落とし込んでいる
• このとき、適切に「3つの座標」に落とし込まれたか、各クラスタ間の距離と、各クラスタが小さくまとまっているか、min_distとcompactnessで計算が行われる

qrcode.cpp

            double compactness = kmeans(

            for (size_t i = 0; i < centers.size(); i++)
            {
                // クラスタ中心が3つ返ってくるので各クラス間の距離の最小値を探す
                double dist = norm(centers[i] - centers[(i+1) % centers.size()]);
                if (dist < min_dist)
                {
                    min_dist = dist;
                }
            }

            if (min_dist < min_dist_between_points)
            {
                // あまりにも min_dist が小さすぎる場合、3点検出されてない可能性が高いので、やり直す
                continue;
            }

            // compactness は各クラス内でのまとまり具合を表す
            double mean_compactness = compactness / point2f_result.size();
            double ratio = mean_compactness / min_dist;

            if (ratio < max_ratio)
            {
                // ratio は小さければ小さいほどただしく3点検出されているのことを表すでしきい値以下だったら成功として返す
                return point2f_result;
            }

• 「クラス内分散」と「クラス間分散」って言葉を使えばまんま「判別分析法」、いわゆる「大津の手法」を流用した形ですね。

分水嶺

• x86_64では、候補点が3点正しく検出されるため、min_distのチェックもratioのチェックもパスする
• Aarch64では、ratioのチェックをパスできないため、「検出できず」という結果になる
• ここが分水嶺であることがわかります。
• というわけでやはり「丸め誤差」が原因でしたね。ではここにておしまいです。

本当に？

最終回じゃないぞよ　もうちっとだけ続くんじゃ

• じつは、ここで思考停止していたのですが、入力画像を見て驚きました

• 実際にOpenCVのテストデータリポジトリから引っ張ってきたデータです。
• 画像サイズは1280x1024で、歪もノイズもほとんどありません。
• 丸め誤差でギリギリのところでコケるならともかく、こんな好条件な画像が丸め誤差の境界に立っているとは思えません
• どうやら、分水嶺より手前のところで何かがおかしいようです。

実際の画像を覗いてみると

• ソースコードの、searchHorizontalLinesおよびextractVerticalLines内ではbin_barcodeという名前で保持されている画像にアクセスしています

一部抜粋

vector<Vec3d> QRDetect::searchHorizontalLines()
{
    :
    const int height_bin_barcode = bin_barcode.rows;
    const int width_bin_barcode  = bin_barcode.cols;

    for (int y = 0; y < height_bin_barcode; y++)
    {
        const uint8_t *bin_barcode_row = bin_barcode.ptr<uint8_t>(y);
        :
    }

}

vector<Point2f> QRDetect::extractVerticalLines(const vector<Vec3d> &list_lines, double eps)
{
    :
    for (size_t pnt = 0; pnt < list_lines.size(); pnt++)
    {
        :
        for (int j = y; j < bin_barcode.rows - 1; j++)
        {
            uint8_t next_pixel = bin_barcode.ptr<uint8_t>(j + 1)[x];
            :
        }
    }
}

• この、bin_barcodeを覗き込んだときに、がっくりと膝をつきました
• このbin_barcodeがこの通りです

• ポイントは、隅に配置されてるマーカが白く塗りつぶされています

• まじで意味不明な白いノイズが発生しております。
• この画像はAarch64でも発生するのですが、x86_64 でも発生しているのです。
• 合わせて、この画像に検出された場所を突っ込んでみると、こんな結果が出てきます

• 驚きすぎてHG明朝体を使ってしまうほどです。
• 見づらいのですが、x86_64版では一応3箇所に合計5点検出されており、クラスタリングの結果きれいに3箇所に分けられていますが、そもそも検出されてる箇所が隅のマーカでもない上に、隅のマーカがそもそも白く塗りつぶされています。
  • 参考までに、Aarch64だと、無関係なところにもう1点候補が検出され、4箇所から合計6点検出されます
• 通常、テストがFAILするときはPASSした状況を基準に直すのが正しいアプローチですが、今回はそもそもPASSしてる状況が正しくない（誤ってPASSしている）のです。

本当の原因

• 本当の原因とも言うべき箇所はここにありました

void QRDetect::init(const Mat& src, double eps_vertical_, double eps_horizontal_)
{
    barcode = src.clone();
    if (!barcode.empty())
        adaptiveThreshold(barcode, bin_barcode, 255, ADAPTIVE_THRESH_GAUSSIAN_C, THRESH_BINARY, 83, 2);
        //  何故かここに「83」がハードコードされている----------------------------------------------^^

• このadaptiveThreshold関数はしきい値処理する関数の一種ですが、2値化する際のしきい値を近傍の画素から動的に変化させる関数です
• その際、どれほどの近傍を計算に含めるか、というパラメータが第6引数の83です。
• この83という大きさが先程の画像中の隅のマーカより小さい数字のため、
  • 黒いマーカ内でも黒い画素同士の比較が行われる
  • しきい値が黒い画素の分布内で選択される
  • 結果黒い画素が白画素に2値化される
  • という現象が発生しています
• そしてなぜかx86_64だとたまたま誤検出された候補位置がチェックをすり抜けてしまい、無事「検出」と通ってしまいます。
• では、誤検出した座標で何故正しく復号化できるのかというと、もう少しあとのところにミソがありました

    if ((square_flag || local_points_flag) && purpose == SHRINKING)
    {
        localization_points.clear();
        bin_barcode = resized_bin_barcode.clone();
        list_lines_x = searchHorizontalLines();

• 条件が揃っているので、このif文内が実行されます
• if文内ではbin_barcodeにはresized_bin_barcodeがcloneされます
• で、このresized_bin_barcodeがどんなものか見てみましょう

• 何ということでしょう ² あの汚く塗りつぶされた隅のマーカがきれいではないですか
• resized_bin_barcodeは画像サイズを縦512ピクセルに揃えるため、事前にリサイズしてあります
• その上で再度隅のマーカを探し直します

        // 以下前述のコードと全く同じ手順で
        // searchHorizontalLines, separateVerticalLines, kmeansと順番にコールされている
        bin_barcode = resized_bin_barcode.clone();
        list_lines_x = searchHorizontalLines();
        if( list_lines_x.empty() ) { return false; }
        list_lines_y = separateVerticalLines(list_lines_x);
        if( list_lines_y.empty() ) { return false; }

        kmeans(list_lines_y, 3, labels,
               TermCriteria( TermCriteria::EPS + TermCriteria::COUNT, 10, 0.1),
               3, KMEANS_PP_CENTERS, localization_points);

• なので、先程のテストが誤検出したにも関わらず、ここでは正しい2値画像を使ってマーカの検出が安定して行われるのです

今回のテストのまとめ

• 今回、単純な丸め誤差でFAILしてるかと思ったが、調べたら結構手が混んでいる失敗だった
  1. adaptiveThreshold 関数で2値化が行われる
     • この時点で丸め誤差の影響³で、Aarch64と x86_64ではbit-exactな2値画像にはならない
     • ハードコードされてる83というパラメータのせいで隅のマーカに白い画素が、無視できないほど発生する
  2. extractVerticalLinesの結果、丸め誤差で発生した2値画像の微妙な差異のせいで
     • Aarch64では、4箇所候補が発生する
     • x86_64では、3箇所候補が発生 する
     • Aarch64版はこの時点でチェックをパスできずテストがFAILする
  3. x86_64版では縮小した画像に対し、再度検出プロセスが走る
     • 2値化してから縮小でなく、縮小してから2値化した画像が使われるため、今度は白い画素の量が無視できる程度に少ない
     • 結果安定して隅のマーカが検出されテストがPASSする
• 見た目にはx86_64ではPASSして、Aarch64ではFAILするように見えるテストができる（←イマココ）

補足

• 実装をボロクソに批判した記事になってしまいましたが、実のところこの問題は難しいチャレンジを抱えています
• というのも、adaptiveThreshold関数に適切なパラメータ (≠83というハードコードパラメータ) を渡すためには画面中にどれぐらい大きなマーカが写っているか事前にわかる必要があります
• しかし画像中に写ってる物体の大きさがわからないためにマーカを使って位置を特定している訳で、結果として「卵が先か鶏が先か」という問題を抱えている訳です。
• もちろん、83という数字の代わりにステップで増やしながら探すアプローチもありますが、それに対して今までうまく行っていた検出に対して膨大な計算量が発生することになります
• つまり原因は特定できたものの、そこを直すための実装は一筋縄では行かないわけです。
• ちなみに私はこのテストを直すことを諦め、 GTEST_FILTER環境変数にこのテストを突っ込みました ⁴
• OpenCVのバージョン
  • 3.4.15、3.4.16、4.5.3、4.5.4で確認しています
• コンパイラのバージョン
  • GCCの5系から9系までどのコンパイラ⁵でもまんべんなく発生しております
  • MSVCは2015、2017で確認しました

---

1. 具体的にはグレースケールでないと弾かれる ↩

2. なんということでしょう ↩

3. 丸め誤差か、丸め方法の影響か、はたまたFused-Multiply-and-Add (積和演算)が原因か、とにかくbit-exactな結果にはならない ↩

4. OpenCVのテストフレームgtestは、実行時の環境変数GTEST_FILTERを参照し、名前をもとに特定のテストをスキップしたり、特定のテストだけを実行したりできる。今回追加した文字列はObjdetect_QRCode_Close.regression/0で、本日の記事で解説したテストをスキップすることを意味する ↩

5. GCC 5.4.0、6.3.0、7.5.0、8.3.0、9.3.0 ↩