QRコード検出APIの解説

# はじめに
  - これは、OpenCV Advent Calendar 2018 20日目の記事です。
  - 関連記事は[目次](http://qiita.com/advent-calendar/2018/opencv)にまとめられています。
  - なお、本記事は筆者個人の意見であり、筆者の所属組織とは無関係です。

# TL;DR
  - OpenCV 4.0 から QRコード用のAPIが追加された
  - 本記事では検出して正面に補正するまでのコードを読み解く

# APIを使うために
  - APIはOpenCV 4.0から追加されました
  - objdetectモジュールのAPIとして提供されます
  - 画像を与えれば、検出、デコードまでよしなにやってくれます
  - デコードはQRコードの仕様から、黒と白を読み解くことでデータを取り出せます
  - ただし、よっぽど難しいのは適当な画像からバーコードの位置と向きを検出し、正面に補正するところまででは無いでしょうか。
  - cv::QRCodeDetector クラスが担当します

# QRCodeDetectorクラスの解説
  - QRCodeDetectorクラス内には
    - detectメソッド
    - decodeメソッド
    - detectAndDecodeメソッド
    - の3つがあります
  - 読んでお察しの通り、detectAndDecodeメソッド内ではdetectメソッドとdecodeメソッドをそれぞれ呼んでいます。

```cpp:qrcode.cpp
    bool ok = detect(inarr, points);  // ここでdetect
    <中略>
    std::string decoded_info;
    if( ok )
        decoded_info = decode(inarr, points, straight_qrcode);
```

## detectメソッド
 - detectメソッド内では2値化した後、QRコードの四隅のうち、3箇所にあるマーカの位置を検出します
 - まず、入力画像をcv::thresholdAdaptive関数で2値化します。

```cpp:qrcode.cpp,70
    adaptiveThreshold(barcode, bin_barcode, 255, ADAPTIVE_THRESH_GAUSSIAN_C, THRESH_BINARY, 83, 2);
```
![qrcode0.png](https://qiita-image-store.s3.amazonaws.com/0/12162/82b2ad38-63e2-739d-bd16-818c373b8350.png)

### QRDetect::searchHorizontalLines()
  - 次に、QRDetect::searchHorizontalLines()関数で白黒のパターンを繰り返し検出します。
  - この時、QRコードは仕様により、四隅のうち3箇所に配置されている黒い四角は以下のような配置になることが決まっています。

![qrcode2.png](https://qiita-image-store.s3.amazonaws.com/0/12162/6ed46a47-7b9a-5b06-a905-a27ffe2643df.png)


```
■■■■■■■■■
■□□□□□□□■
■□■■■■■□■
■□■□□□■□■
■□■□□□■□■
■□■□□□■□■
■□■□□□■□■
■□■■■■■□■
■□□□□□□□■
■■■■■■■■■
```
 - 水平に真ん中の部分を引っこ抜くと、こんな感じ

```
■□■□□□■□■
```

 - という訳で、撮影された画像でも、黒：白：黒：白：黒が```1:1:3:1:1```という割合になることが期待されます。

![qrcode1.png](https://qiita-image-store.s3.amazonaws.com/0/12162/66e7a8a3-a79a-0719-1402-6e57ef03cce5.png)
![horizontal2.png](https://qiita-image-store.s3.amazonaws.com/0/12162/df40ac74-7e40-f37f-3999-9166f50c190c.png)


 - QRDetect::searchHorizontalLines()内では、まず水平スキャンして、白黒が反転する座標を探します

```cpp:qrcode.cpp,97
        uint8_t future_pixel = 255;
        for (int x = pos; x < width_bin_barcode; x++)![qrcode0.png](https://qiita-image-store.s3.amazonaws.com/0/12162/a0118dfb-37dc-7a0f-265b-f29d94802217.png)

        {
            if (bin_barcode_row[x] == future_pixel)
            {
                future_pixel = 255 - future_pixel;
                pixels_position.push_back(x);
            }
        }
```

 - 次にそれぞれの黒と白の長さ(ピクセル)を計算します

```cpp:qrcode.cpp,109
            test_lines[0] = static_cast<double>(pixels_position[i - 1] - pixels_position[i - 2]);
            test_lines[1] = static_cast<double>(pixels_position[i    ] - pixels_position[i - 1]);
            test_lines[2] = static_cast<double>(pixels_position[i + 1] - pixels_position[i    ]);
            test_lines[3] = static_cast<double>(pixels_position[i + 2] - pixels_position[i + 1]);
            test_lines[4] = static_cast<double>(pixels_position[i + 3] - pixels_position[i + 2]);
```
 - 最後に、黒、白それぞれのピクセルの長さが、全体の長さの1/7、もしくは3/7になってるか計算します。

```cpp:qrcode.cpp,120
            for (size_t j = 0; j < test_lines_size; j++)
            {
                if (j != 2) { weight += fabs((test_lines[j] / length) - 1.0/7.0); }
                else        { weight += fabs((test_lines[j] / length) - 3.0/7.0); }
            }
```

 - 上の計算で求められたweightは、比率からのズレを表し、このズレがしきい値より小さければマーカの位置の候補として```result```に登録されます。

 ```cpp:qrcode.cpp,126
            if (weight < eps_vertical)
            {
                Vec3d line;
                line[0] = static_cast<double>(pixels_position[i - 2]);
                line[1] = y;
                line[2] = length;
                result.push_back(line);
            }
 ```

### separateVerticalLines()
 - 前述のhorizontalLinesで得られた結果をもとに、今度はverticalLinesを探します。
 - ~~先程と同様、白黒の比率が1:1:3:1:1になる部分を探します。~~
 - 縦方向での探索は、中央画素から上下それぞれに探索します

![vertical1.png](https://qiita-image-store.s3.amazonaws.com/0/12162/752a3667-9a72-5bb3-659f-119bbcf9f72d.png)
![vertical2.png](https://qiita-image-store.s3.amazonaws.com/0/12162/845c0dae-2919-3858-0f58-042992900065.png)


 ```cpp:qrcode.cpp,139
            for (size_t i = 0; i < test_lines.size(); i++)
            {
                if (i % 3 != 0) { weight += fabs((test_lines[i] / length) - 1.0/ 7.0); }
                else            { weight += fabs((test_lines[i] / length) - 3.0/14.0); }
            }

            if(weight < eps_horizontal)
            {
                result.push_back(list_lines[pnt]);
            }
 ```

 - ~~何故か今度は3/7じゃなくて3/14を使ってますね（バグ？PRチャンス？）~~
 - これはバグでなく、正しい挙動です。中心から上下にそれぞれ3:2:2の比率で黒と白が存在するかどうかチェックしています。
 - この組み合わせを通すことで、3箇所のマーカが求まります。

### fixationPoints
 - ここまでで3箇所のマーカが得られました
 - この後は検出された結果を検証して誤検出をはじきます。
 - まずはk-meansクラスタリングして3つのクラスタに分けます

```cpp:qrcode.cpp,323
    kmeans(list_lines_y, 3, labels,
           TermCriteria( TermCriteria::EPS + TermCriteria::COUNT, 10, 0.1),
           3, KMEANS_PP_CENTERS, localization_points);
```

 - これ、誤検出があった場合にその座標に正しい検出結果も引っ張られることになってかなり危ない気がしますが、まあ、そういう実装になっています。
 - つづいて出てきた3点の座標の、並び順を調べます。現実装ではcosの値を利用して、一番直角に近い座標を基準として抽出し、右、下の座標をそれぞれ特定します。

## computeTransformationPoints
 - つづいては4つ目の点の位置を推定します。
 - 現状の実装では、既にある3点で構成される平行四辺形の頂点を利用しています

```cpp:qrcode.cpp
    transformation_points.push_back(down_left_edge_point);
    transformation_points.push_back(up_left_edge_point);
    transformation_points.push_back(up_right_edge_point);
    transformation_points.push_back(
        intersectionLines(down_left_edge_point, down_max_delta_point,
                          up_right_edge_point, up_max_delta_point));
```

 - 他にも関数callがあるのですが、大まかにはこのあたりの処理がポイントだと思います。
 - 最後にdecode関数内でwarpPerspectiveを呼んで、正面画像に変換します。

```cpp:qrcode.cpp
    Mat H = findHomography(pts, perspective_points);
    Mat bin_original;
    adaptiveThreshold(original, bin_original, 255, ADAPTIVE_THRESH_GAUSSIAN_C, THRESH_BINARY, 83, 2);
    Mat temp_intermediate;
    warpPerspective(bin_original, temp_intermediate, H, temporary_size, INTER_NEAREST);
    no_border_intermediate = temp_intermediate(Range(1, temp_intermediate.rows), Range(1,  temp_intermediate.cols));
```


# おわりに
 - OpenCV 4.0リリース間近に、[QRコードがAarch64で検出に失敗する](https://github.com/opencv/opencv/issues/12926)という問題があったので、急遽issueを立てました。
 - その時に読んだコードを中心にQRコード検出/デコードの挙動を解説しました
 - 正直、マジックナンバーが多数埋め込んであったり、コードのコピペがあったり、```vecotr<Point2f>```を値渡ししていたりと、まだまだ粗削りな部分が見えるコードですが、是非皆さん使って見て使い方をフィードバックしてみましょう。
 - 明日は@ymaeda61さんの記事で、「[本気だしたバイラテラルフィルタ](https://qiita.com/ymaeda61/items/d437b1f741abd805d13a)」です。楽しみです！