Github: https://github.com/opencv/opencv
版本: OpenCV 4.2

解析一下关于OpenCV4中运用的二维码识别的C++源码。
QRCodeDetector中主要包含了detect和decode函数来给外部使用，用来定位和解码二维码
这回先看下定位的部分。

主要函数

QRCodeDetector中实际去处理二维码定位部分的类是QRDetect类，
QRDetect类中主要函数有以下几种：

// 初始化
void init(const Mat& src, double eps_vertical_ = 0.2, double eps_horizontal_ = 0.1);
// 获取定位，左上·右上·左下三个定位标记的中心点
bool localization();
// 获取二维码四边形区域的四个顶点
bool computeTransformationPoints();
// 计算两条线交叉点
static Point2f intersectionLines(Point2f a1, Point2f a2, Point2f b1, Point2f b2);

原理解析

这回准备了一张稍微有些倾斜角度的二维码图片。
为了能明确识别二维码中的黑白色块，对图片进行灰度处理后进行二值化，
再从二值化图片中找出符合二维码规律的点

// QRDetect::init函数
// ...
// 二值化
adaptiveThreshold(barcode, bin_barcode, 255, ADAPTIVE_THRESH_GAUSSIAN_C, THRESH_BINARY, 83, 2);
// ...

找出定位标识的中心点

searchHorizontalLines函数

如下图所示，searchHorizontalLines函数主要做的是寻找图片中，水平线上符合1:1:3:1:1比例的色块
也就是刚好经过中心黑色方块的水平线

函数内从第一行开始逐行扫描，并保存黑白颜色反转的色块位置

// QRDetect::searchHorizontalLines函数
// ...
uint8_t future_pixel = 255;
for (int x = pos; x < width_bin_barcode; x++)
{
    if (bin_barcode_row[x] == future_pixel)
    {
        future_pixel = static_cast<uint8_t>(~future_pixel); // 8位反转运算，0 or 255
        pixels_position.push_back(x);
    }
}
// ...

再遍历此行中黑白反转了的色块的位置，找出符合1:1:3:1:1比例，且偏差在容差范围内的线段

// QRDetect::searchHorizontalLines函数
// ...
for (size_t i = 2; i < pixels_position.size() - 4; i+=2)
{
    // 五条线段的长度
    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]);

    double length = 0.0, weight = 0.0;  // TODO avoid 'double' calculations

    for (size_t j = 0; j < test_lines_size; j++) { length += test_lines[j]; }

    if (length == 0) { continue; }
    for (size_t j = 0; j < test_lines_size; j++)
    {
        // 根据1:1:3:1:1比例，中间的线段应占7分之3的比例，其余为7分之1
        // 累加线段偏移此比例的值
        if (j != 2) { weight += fabs((test_lines[j] / length) - 1.0/7.0); }
        else        { weight += fabs((test_lines[j] / length) - 3.0/7.0); }
    }

    // 偏移值在容差范围内的话保存进结果
    if (weight < eps_vertical)
    {
        Vec3d line;
        line[0] = static_cast<double>(pixels_position[i - 2]); // 水平线x值
        line[1] = y; // 水平线y值
        line[2] = length; // 水平线长度
        result.push_back(line);
    }
}
// ...

separateVerticalLines函数

接下来根据已找到的水平线，再找出垂直线上符合规律的点，
separateVerticalLines函数中的extractVerticalLines函数便是做此事的，
预设的是从垂直中心点出发，依次寻找上下两边符合比例的，
所以比例为2倍的2:2:6:2:2

与找水平线时基本一样，不过因为是基于之前找到的水平线来确定垂直线的，
所以这回可以直接确定各线段长度，一共有6条

// QRDetect::extractVerticalLines
// ...
// --------------- Search vertical up-lines --------------- //

test_lines.clear();
uint8_t future_pixel_up = 255;

int temp_length_up = 0;
for (int j = y; j < bin_barcode.rows - 1; j++)
{
    uint8_t next_pixel = bin_barcode.ptr<uint8_t>(j + 1)[x];
    temp_length_up++; // 遇到颜色反转前长度累加
    if (next_pixel == future_pixel_up)
    {
        future_pixel_up = static_cast<uint8_t>(~future_pixel_up);
        test_lines.push_back(temp_length_up);
        temp_length_up = 0;
        if (test_lines.size() == 3)
            break;
    }
}

// --------------- Search vertical down-lines --------------- //

int temp_length_down = 0;
uint8_t future_pixel_down = 255;
for (int j = y; j >= 1; j--)
{
    uint8_t next_pixel = bin_barcode.ptr<uint8_t>(j - 1)[x];
    temp_length_down++; // 遇到颜色反转前长度累加
    if (next_pixel == future_pixel_down)
    {
        future_pixel_down = static_cast<uint8_t>(~future_pixel_down);
        test_lines.push_back(temp_length_down);
        temp_length_down = 0;
        if (test_lines.size() == 6)
            break;
    }
}
// ...

判断6条线段长度的比例，并将符合容差范围内的水平线存起来
这里需要注意的是，因为中心方块被分为两条线段，所以判断的比例是14分之3

// QRDetect::extractVerticalLines
// ...
// --------------- Compute vertical lines --------------- //

if (test_lines.size() == 6)
{
    double length = 0.0, weight = 0.0;  // TODO avoid 'double' calculations

    for (size_t i = 0; i < test_lines.size(); i++)
        length += test_lines[i];

    CV_Assert(length > 0);
    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
        {
            // 中心方块被分为两段，所以比例是14分之3
            weight += fabs((test_lines[i] / length) - 3.0/14.0);
        }
    }

    if (weight < eps)
    {
        result.push_back(list_lines[pnt]);
    }
}
// ...

之后再进行了紧凑度判断后，将各线段中心点返回，此函数便结束了。

K-Means和fixationPoints函数

垂直线上符合比例的中心点，根据容差范围是会存在多个的，
利用K-Means聚类算法将所有点分为三个集合，并计算出它们的中心点，
通常这个时候就获得了定位标识的中心。

fixationPoints函数中，会接着对这三个点进行检证。

验证三点的余弦值是否在范围内：

// QRDetect::fixationPoints
// ...
double cos_angles[3], norm_triangl[3];

norm_triangl[0] = norm(local_point[1] - local_point[2]);
norm_triangl[1] = norm(local_point[0] - local_point[2]);
norm_triangl[2] = norm(local_point[1] - local_point[0]);

cos_angles[0] = (norm_triangl[1] * norm_triangl[1] + norm_triangl[2] * norm_triangl[2]
              -  norm_triangl[0] * norm_triangl[0]) / (2 * norm_triangl[1] * norm_triangl[2]);
cos_angles[1] = (norm_triangl[0] * norm_triangl[0] + norm_triangl[2] * norm_triangl[2]
              -  norm_triangl[1] * norm_triangl[1]) / (2 * norm_triangl[0] * norm_triangl[2]);
cos_angles[2] = (norm_triangl[0] * norm_triangl[0] + norm_triangl[1] * norm_triangl[1]
              -  norm_triangl[2] * norm_triangl[2]) / (2 * norm_triangl[0] * norm_triangl[1]);

const double angle_barrier = 0.85;
if (fabs(cos_angles[0]) > angle_barrier || fabs(cos_angles[1]) > angle_barrier || fabs(cos_angles[2]) > angle_barrier)
{
    local_point.clear();
    return;
}
// ...

为了确定左上角的点是哪一个，通过余弦值判断最接近90度的点，
以及判断三点相关线段与定位标识的交错点所形成的面积最大的点（文字不好描述）是否为同一个

// QRDetect::fixationPoints
// ...
size_t i_min_cos =
   (cos_angles[0] < cos_angles[1] && cos_angles[0] < cos_angles[2]) ? 0 :
   (cos_angles[1] < cos_angles[0] && cos_angles[1] < cos_angles[2]) ? 1 : 2;

size_t index_max = 0;
double max_area = std::numeric_limits<double>::min();
for (size_t i = 0; i < local_point.size(); i++)
{
    const size_t current_index = i % 3;
    const size_t left_index  = (i + 1) % 3;
    const size_t right_index = (i + 2) % 3;

    const Point2f current_point(local_point[current_index]),
        left_point(local_point[left_index]), right_point(local_point[right_index]),
        // 当前点至另外两点的中心点的线段与图像底部线段的交叉点
        central_point(intersectionLines(current_point,
                          Point2f(static_cast<float>((local_point[left_index].x + local_point[right_index].x) * 0.5),
                                  static_cast<float>((local_point[left_index].y + local_point[right_index].y) * 0.5)),
                          Point2f(0, static_cast<float>(bin_barcode.rows - 1)),
                          Point2f(static_cast<float>(bin_barcode.cols - 1),
                                  static_cast<float>(bin_barcode.rows - 1))));


    vector<Point2f> list_area_pnt;
    list_area_pnt.push_back(current_point);

    // 遍历三条线段，并找出与当前定位标识外框所交错的三个点
    vector<LineIterator> list_line_iter;
    list_line_iter.push_back(LineIterator(bin_barcode, current_point, left_point));
    list_line_iter.push_back(LineIterator(bin_barcode, current_point, central_point));
    list_line_iter.push_back(LineIterator(bin_barcode, current_point, right_point));

    for (size_t k = 0; k < list_line_iter.size(); k++)
    {
        LineIterator& li = list_line_iter[k];
        uint8_t future_pixel = 255, count_index = 0;
        for(int j = 0; j < li.count; j++, ++li)
        {
            const Point p = li.pos();
            if (p.x >= bin_barcode.cols ||
                p.y >= bin_barcode.rows)
            {
                break;
            }

            const uint8_t value = bin_barcode.at<uint8_t>(p);
            if (value == future_pixel)
            {
                future_pixel = static_cast<uint8_t>(~future_pixel);
                count_index++;
                if (count_index == 3)
                {
                    list_area_pnt.push_back(p);
                    break;
                }
            }
        }
    }

    // 计算外框交错的三点与当前点形成的四边形面积
    const double temp_check_area = contourArea(list_area_pnt);
    // 形成的面积最大的当前点即为左上角的点
    if (temp_check_area > max_area)
    {
        index_max = current_index;
        max_area = temp_check_area;
    }

}
// 第一个位置放左上角的点
if (index_max == i_min_cos) { std::swap(local_point[0], local_point[index_max]); }
else { local_point.clear(); return; }
// ...

最后再确定左下和右上的点的顺序，通过行列式判断是否反转

// QRDetect::fixationPoints
// ...
const Point2f rpt = local_point[0], bpt = local_point[1], gpt = local_point[2];
Matx22f m(rpt.x - bpt.x, rpt.y - bpt.y, gpt.x - rpt.x, gpt.y - rpt.y);
// 行列式反转判断
if( determinant(m) > 0 )
{
    std::swap(local_point[1], local_point[2]);
}
// ...

找出二维码四边形区域的顶点

floodFill和凸包计算

先通过三个定位标识的中心点分别找出定位标识的外框，
利用floodFill填充外框至蒙版中。

再对三个外框的集合进行凸包计算，得到包围的各个点

// QRDetect::computeTransformationPoints
// ...
vector<Point> locations, non_zero_elem[3], newHull;
vector<Point2f> new_non_zero_elem[3];
for (size_t i = 0; i < 3; i++)
{
    Mat mask = Mat::zeros(bin_barcode.rows + 2, bin_barcode.cols + 2, CV_8UC1);
    uint8_t next_pixel, future_pixel = 255;
    int count_test_lines = 0, index = cvRound(localization_points[i].x);
    for (; index < bin_barcode.cols - 1; index++)
    {
        next_pixel = bin_barcode.ptr<uint8_t>(cvRound(localization_points[i].y))[index + 1];
        if (next_pixel == future_pixel)
        {
            future_pixel = static_cast<uint8_t>(~future_pixel);
            count_test_lines++;
            if (count_test_lines == 2)
            {
                // 找到外框的点，进行填充
                floodFill(bin_barcode, mask,
                          Point(index + 1, cvRound(localization_points[i].y)), 255,
                          0, Scalar(), Scalar(), FLOODFILL_MASK_ONLY);
                break;
            }
        }
    }
    Mat mask_roi = mask(Range(1, bin_barcode.rows - 1), Range(1, bin_barcode.cols - 1));
    findNonZero(mask_roi, non_zero_elem[i]);
    newHull.insert(newHull.end(), non_zero_elem[i].begin(), non_zero_elem[i].end());
}
// 对三个外框的集合进行凸包计算
convexHull(newHull, locations);
// ...

包围点中，距离最远的两点即为左下和右上的两个顶点，
与左下和右上所能形成的最大面积的点，即为左上的顶点

// QRDetect::computeTransformationPoints
// ...
double pentagon_diag_norm = -1;
Point2f down_left_edge_point, up_right_edge_point, up_left_edge_point;
for (size_t i = 0; i < new_non_zero_elem[1].size(); i++)
{
    for (size_t j = 0; j < new_non_zero_elem[2].size(); j++)
    {
        double temp_norm = norm(new_non_zero_elem[1][i] - new_non_zero_elem[2][j]);
        if (temp_norm > pentagon_diag_norm)
        {
            down_left_edge_point = new_non_zero_elem[1][i];
            up_right_edge_point  = new_non_zero_elem[2][j];
            pentagon_diag_norm = temp_norm;
        }
    }
}

if (down_left_edge_point == Point2f(0, 0) ||
    up_right_edge_point  == Point2f(0, 0) ||
    new_non_zero_elem[0].size() == 0) { return false; }

double max_area = -1;
up_left_edge_point = new_non_zero_elem[0][0];

for (size_t i = 0; i < new_non_zero_elem[0].size(); i++)
{
    vector<Point2f> list_edge_points;
    list_edge_points.push_back(new_non_zero_elem[0][i]);
    list_edge_points.push_back(down_left_edge_point);
    list_edge_points.push_back(up_right_edge_point);

    double temp_area = fabs(contourArea(list_edge_points));
    if (max_area < temp_area)
    {
        up_left_edge_point = new_non_zero_elem[0][i];
        max_area = temp_area;
    }
}
// ...

右下角的第四个顶点，则是通过左下和右上外框中，延伸向右下角的交叉点来确立的

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));

透视转换

解码部分中有用detect中找出的四个顶点来做透视变换，把图片转为正面视角
用到的函数主要是findHomography和warpPerspective(单纯的坐标转换可以用perspectiveTransform)

const Point2f centerPt = QRDetect::intersectionLines(original_points[0], original_points[2],
                                                     original_points[1], original_points[3]);
if (cvIsNaN(centerPt.x) || cvIsNaN(centerPt.y))
    return false;

const Size temporary_size(cvRound(test_perspective_size), cvRound(test_perspective_size));

vector<Point2f> perspective_points;
perspective_points.push_back(Point2f(0.f, 0.f));
perspective_points.push_back(Point2f(test_perspective_size, 0.f));

perspective_points.push_back(Point2f(test_perspective_size, test_perspective_size));
perspective_points.push_back(Point2f(0.f, test_perspective_size));

perspective_points.push_back(Point2f(test_perspective_size * 0.5f, test_perspective_size * 0.5f));

vector<Point2f> pts = original_points;
pts.push_back(centerPt);
// 单应矩阵
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));

而后实际的解码功能是调用的quirc库，这里就不做说明了。

总结

整个流程下来，就是：

1. 水平垂直扫描图片，从三个定位标识中找出符合规律的点
2. 用kmeans找出三个集合的中心点，即得出三个定位标识的中心
3. floodFill填充外框，再用凸包计算得出三个外框的包围点
4. 距离最长两点为二维码四边形中左下角和右上角的顶点，与左下右上顶点能形成面积最大的点为左上角顶点
5. 通过左下和右上顶点的延伸线上的交叉点得出右下角的点
6. 利用得出的四个顶点进行透视转换，转为正面图像
7. 调用quirc库进行解码