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


- この記事は[OpenCV アドベントカレンダー](https://qiita.com/advent-calendar/2021/opencv) ~~24日目の記事です~~19日目の記事です。空きが出たので前倒しにしました
- ~~クリスマスイブですね~~

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

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

# それから
- 手元のビルドファームで、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());
```

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

```.cpp
    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`が空っぽだったということである。
 - [前回の解説記事](https://qiita.com/tomoaki_teshima/items/f136e51fa1da6927471b)に書いたように、この`corners`にはQRコードの四隅のうち3箇所にある大きい四角の座標が入って返ってくる。


# デバッグ開始
- もうちょっと深入りしてみる
- 今度はライブラリ内部のソースコードを覗いてみる

```cpp
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での結果

```cpp: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`は画像のサイズ、フォーマット、チャンネル数のチェックなどが行われる[^check]
 - このチェックにパスすると、次は`QRDetect`の`localization`に突入する。

[^check]: 具体的にはグレースケールでないと弾かれる

```cpp: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`関数では、[前回](https://qiita.com/tomoaki_teshima/items/f136e51fa1da6927471b)説明した通り隅にある四角いマーカっぽい場所をまず水平スキャンで探し、その後候補点を垂直方向に検証する
    - 詳しくは[前回の記事](https://qiita.com/tomoaki_teshima/items/f136e51fa1da6927471b)参照
 - で、見つからないと空っぽの候補が返ってくるので、`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`は**空っぽで返ってきた**
 - どうやら原因はここにあるらしい

![smartphone_qr_code.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12162/658c8222-a219-6f50-0ac7-bc1dd6bde03d.png)


# separateVerticalLine

```cpp: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度目であるが、[前回](https://qiita.com/tomoaki_teshima/items/f136e51fa1da6927471b)紹介したときは白黒の画素数とその比率を計算していた。
  - 3年の間に同様の実装は `extractVerticalLines`に移り、本関数内ではしきい値を調整しながら`extractVerticalLines`を繰り返し呼んでいる

```cpp:一部抜粋
    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段階に緩めながら四角いマーカを探していく
    - 以前の記事ではこのしきい値がハードコードされていたのだが、柔軟にしきい値調整しながら探索する模様である。
- 丸め誤差でどこで挙動が変わるのか確認するために、大まかにコードの内容を解説する

## 解説

```cpp: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箇所に特徴的なマーカが付いている（仕様で策定されている）

![sample_QR.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12162/cc70425b-f169-49b9-9d3b-107a2195228f.png)

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

![Clipboard02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12162/46bdcd15-4c40-a48a-8ac7-a643caef34fd.png)

- そのため、複数のピクセルが見つかった場合でも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`のチェックをパスできないため、「検出できず」という結果になる
- ここが分水嶺であることがわかります。
- というわけでやはり「丸め誤差」が原因でしたね。ではここにておしまいです。





# 本当に？
> 最終回じゃないぞよ　もうちっとだけ続くんじゃ

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

![src_grayscale.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12162/f68298d1-bf72-dcc8-b8c4-35dc219fba74.png)

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

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

```.cpp:一部抜粋
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`がこの通りです

![binarized_x86_64.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12162/0ebd84c8-2606-7c5f-398b-2f787bfb253d.png)

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

![QQQQ.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12162/d6c2a6d2-36e8-c2d4-7d9f-11a53a0c4db9.png)

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

![why.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12162/94f941b8-7ee9-3258-616d-5fb6bf5805c0.png)

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

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

```cpp
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だとたまたま**誤検出された候補位置がチェックをすり抜けてしまい、無事「検出」と通ってしまいます**。
- では、誤検出した座標で何故正しく復号化できるのかというと、もう少しあとのところにミソがありました

```cpp
    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.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/12162/d1b15320-6092-9c15-64eb-14c5bf5fbf4f.png)

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

```cpp
        // 以下前述のコードと全く同じ手順で
        // 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値化が行われる
        - この時点で丸め誤差の影響[^round]で、Aarch64と x86_64では`bit-exact`な2値画像にはならない
        - ハードコードされてる`83`というパラメータのせいで隅のマーカに白い画素が、無視できないほど発生する
    1. `extractVerticalLines`の結果、丸め誤差で発生した2値画像の微妙な差異のせいで
        - Aarch64では、4箇所候補が発生する
        - x86_64では、3箇所候補が発生 する
        - Aarch64版はこの時点でチェックをパスできずテストがFAILする
    1. x86_64版では縮小した画像に対し、再度検出プロセスが走る
        - 2値化してから縮小でなく、縮小してから2値化した画像が使われるため、今度は白い画素の量が無視できる程度に少ない
        - 結果安定して隅のマーカが検出されテストがPASSする
- 見た目にはx86_64ではPASSして、Aarch64ではFAILするように見えるテストができる（←イマココ）

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

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

[^round]: 丸め誤差か、丸め方法の影響か、はたまたFused-Multiply-and-Add (積和演算)が原因か、とにかくbit-exactな結果にはならない
[^compiler]: GCC 5.4.0、6.3.0、7.5.0、8.3.0、9.3.0