C++ opencv ncc模板匹配，多角度带缩放

参考
链接: https://blog.csdn.net/qq_42722197/article/details/118688122.

链接: https://www.bilibili.com/video/BV1Lq4y1B7YC/.

NCC匹配原理公式：

1.旋转的情况使用圆投影的旋转不变性原理匹配

2.通过对图像进行降采样，从降采样的高层开始匹配筛选匹配点极大地减少了运算量

3.差分简化运算数据量（但是目前实现的差分貌似没有起到加速的效果，主要是计算src的累积和会消耗太多的时间）

4.gitee代码持续改进中gitee代码地址https://gitee.com/lzj12321/ncc_match.git，欢迎交流，最后希望可以实现一个可工业化应用的NCC匹配（1.带旋转，2.不规则模板匹配，3.实时性高）

5.微信同号，支持帮忙做付费项目（哈哈）

注意：

不支持缩放匹配，圆投影匹配目前不输出匹配角度，只是NCC匹配的初步实现，还需很多优化，目前的实现对规则矩形不旋转的匹配还是挺友好的

import math
import numpy as np
import cv2
from PyQt5.QtCore import QTime

'''
1.二维数组降维
2.圆投影匹配算法
'''


def calculate_unrotate_temp_data(temp):
    ####使用圆投影匹配算法####
    temp_mean = np.mean(temp)
    temp_sub_avg = temp - temp_mean
    temp_deviation = np.vdot(temp_sub_avg, temp_sub_avg)
    return temp_deviation, temp_sub_avg


def calculate_rotate_temp_data(temp):
    temp_column = temp.shape[1]
    temp_row = temp.shape[0]
    if temp_column < temp_row:
        diameter = temp_row
    else:
        diameter = temp_column
    max_radius = math.floor(diameter / 2)
    circle_center = (temp_row / 2, temp_column / 2)
    circle_ring_point = {}

    ###统计每个点到中心的半径，并分类###
    for i in range(temp_column):
        for j in range(temp_row):
            radius = round(np.sqrt((i - circle_center[0]) ** 2 + (j - circle_center[1]) ** 2))
            if radius > max_radius:
                continue
            if radius in circle_ring_point.keys():
                circle_ring_point[radius].append(j * temp_column + i)
            else:
                circle_ring_point[radius] = [j * temp_column + i]

    ###排序获取每个环上的点###
    circle_ring_point = sorted(circle_ring_point.items(), key=lambda item: item[0])
    circular_projection_data = []
    for item in circle_ring_point:
        circular_projection_data.append(np.array(item[1]))

    _circle_sum = []
    _temp = temp.reshape(1, -1)[0]
    for item in circular_projection_data:
        _circle_sum.append(np.sum(_temp[item]))
    _circle_sum = np.array(_circle_sum)
    _mean = np.mean(_circle_sum)
    _deviation_array = _circle_sum - _mean
    _deviation = np.dot(_deviation_array, _deviation_array)

    tempData = {'deviation': _deviation, 'deviation_array': _deviation_array,
                'circular_projection_data': circular_projection_data, 'temp_size': temp.shape}

    return tempData


def generate_temp_data(temp, downsamplingtime=0, is_rotate=False):
    ######每次从原图开始取样#############
    temp_downsampling_data = []
    temp_downsampling_img = []

    ###generate downsampling img###
    temp_downsampling_img.append(temp)
    for i in range(downsamplingtime):
        temp_downsampling_img.append(cv2.pyrDown(temp_downsampling_img[i]))

    ###generate downsampling data###
    for temp_img in temp_downsampling_img:
        if is_rotate:
            temp_downsampling_data.append(calculate_rotate_temp_data(temp_img))
        else:
            temp_downsampling_data.append(
                {'deviation': (calculate_unrotate_temp_data(temp_img))[0],
                 'sub_avg': (calculate_unrotate_temp_data(temp_img))[1]})
    return temp_downsampling_data


def ncc_unrotate_match(src, temp_data, threshold=0.5, match_region=None):
    temp_deviation, temp_sub_avg = temp_data['deviation'], temp_data['sub_avg']
    temp_row_num = temp_sub_avg.shape[0]
    temp_column_num = temp_sub_avg.shape[1]

    _line_start = 0
    _column_start = 0
    _line_range = src.shape[0] - temp_row_num + 1
    _column_range = src.shape[1] - temp_column_num + 1
    if match_region is not None:
        _line_start = match_region[1]
        _column_start = match_region[0]
        _line_range = match_region[1] + match_region[3] + 1
        _column_range = match_region[0] + match_region[2] + 1
        if _line_range > src.shape[0] - temp_row_num + 1:
            _line_range = src.shape[0] - temp_row_num + 1
        if _column_range > src.shape[1] - temp_column_num + 1:
            _column_range = src.shape[1] - temp_column_num + 1

    src_integration = cv2.integral(src)
    pixel_num = temp_sub_avg.size
    match_points = []
    for i in range(_line_start, _line_range, 1):
        for j in range(_column_start, _column_range, 1):
            src_mean = (src_integration[i + temp_row_num][j + temp_column_num] +
                        src_integration[i][j] -
                        src_integration[i][j + temp_column_num] -
                        src_integration[i + temp_row_num][
                            j]) / pixel_num
            _src_deviation = src[i:i + temp_row_num, j:j + temp_column_num] - src_mean
            src_deviation = np.vdot(_src_deviation, _src_deviation)

            ncc_numerator = np.vdot(temp_sub_avg, _src_deviation)

            ncc_denominator = np.sqrt(temp_deviation * src_deviation)
            ncc_value = ncc_numerator / ncc_denominator
            if ncc_value > threshold:
                match_point = {'match_score': ncc_value, 'point': (j, i)}
                match_points.append(match_point)
    return match_points


def ncc_rotate_match(src, tempData, threshold=0.5, angle_start=0, angle_end=360, angle_step=1, match_region=None):
    temp_deviation = tempData['deviation']
    temp_deviation_array = tempData['deviation_array']
    circular_projection_data = tempData['circular_projection_data']

    temp_row_num, temp_column_num = tempData['temp_size'][0], tempData['temp_size'][1]
    _line_start, _column_start, _line_range, _column_range = 0, 0, src.shape[0] - temp_row_num, src.shape[
        1] - temp_column_num

    if match_region is not None:
        _line_start = match_region[1]
        _column_start = match_region[0]
        _line_range = match_region[1] + match_region[3] + 1
        _column_range = match_region[0] + match_region[2] + 1
        if _line_range > src.shape[0] - temp_row_num + 1:
            _line_range = src.shape[0] - temp_row_num + 1
        if _column_range > src.shape[1] - temp_column_num + 1:
            _column_range = src.shape[1] - temp_column_num + 1

    match_points = []
    for i in range(_line_start, _line_range, 1):
        for j in range(_column_start, _column_range, 1):
            _src = src[i:i + temp_row_num, j:j + temp_column_num].reshape(1, -1)[0]
            src_sum = []
            for item in circular_projection_data:
                src_sum.append(np.sum(_src[item]))
            _src_sum = np.array(src_sum)
            src_mean = np.mean(_src_sum)
            src_deviation_array = _src_sum - src_mean

            ncc_numerator = np.vdot(src_deviation_array, temp_deviation_array)

            src_deviation = np.dot(src_deviation_array, src_deviation_array)
            ncc_denominator = np.sqrt(temp_deviation * src_deviation)
            ncc_value = ncc_numerator / ncc_denominator
            if ncc_value > threshold:
                match_point = {'match_score': ncc_value, 'point': (j, i)}
                match_points.append(match_point)
    return match_points


def ncc_match(src, temp, is_rotate=False, downsamplingtime=0, threshold=0.7, angle_start=0, angle_end=0,
              match_region=None):
    assert temp.shape[0] <= src.shape[0] and temp.shape[1] <= src.shape[1]

    temp_downsampling_data = generate_temp_data(temp, downsamplingtime, is_rotate)

    src_down_sampling_array = []
    src_down_sampling_array.append(src)
    for i in range(1, downsamplingtime + 1):
        src_down_sampling_array.append(cv2.pyrDown(src_down_sampling_array[i - 1]))

    match_points = []
    downsample_match_point = None
    for i in range(downsamplingtime, -1, -1):
        match_offset = 2 ** (i + 1)
        if i == downsamplingtime:
            match_region = [0, 0, src_down_sampling_array[i].shape[1], src_down_sampling_array[i].shape[0]]
        else:
            _x, _y, _w, _h = 0, 0, 0, 0
            if downsample_match_point[0] * 2 - match_offset >= 0:
                _x = downsample_match_point[0] * 2 - match_offset
                _w = match_offset * 2 + 1
            else:
                _x = 0
                _w = match_offset + 1
            if downsample_match_point[1] * 2 - match_offset >= 0:
                _y = downsample_match_point[1] * 2 - match_offset
                _h = match_offset * 2 + 1
            else:
                _y = 0
                _h = match_offset + 1
            match_region = [_x, _y, _w, _h]

        if not is_rotate:
            _match_points = ncc_unrotate_match(src_down_sampling_array[i],
                                               temp_downsampling_data[i], match_region=match_region,
                                               threshold=threshold)
        else:
            _match_points = ncc_rotate_match(src_down_sampling_array[i],
                                             temp_downsampling_data[i], match_region=match_region,
                                             threshold=threshold)
        if i == 0:
            match_points = _match_points
        if len(_match_points) != 0:
            ###利用上一层的最佳匹配值来作为下一层匹配的种子点###
            downsample_match_point = sorted(_match_points, key=lambda _point: _point['match_score'], reverse=True)[0][
                'point']
        else:
            break
    return match_points


def draw_result(src, temp, match_point):
    src = cv2.cvtColor(src, cv2.COLOR_GRAY2RGB)
    cv2.rectangle(src, match_point,
                  (match_point[0] + temp.shape[1], match_point[1] + temp.shape[0]),
                  (0, 255, 0), 1)
    cv2.imshow('temp', temp)
    cv2.imshow('result', src)
    cv2.waitKey()


if __name__ == '__main__':
    src = cv2.imread('img/1.jpg', cv2.IMREAD_GRAYSCALE)
    temp = cv2.imread('img/temp.png', cv2.IMREAD_GRAYSCALE)

    downsamplingtime = 4
    threshold = 0.7
    is_rotate = True

    match_points = ncc_match(src, temp, is_rotate=is_rotate, threshold=threshold, downsamplingtime=downsamplingtime)
    if len(match_points) != 0:
        best_match_point = sorted(match_points, key=lambda _point: _point['match_score'], reverse=True)[0]
        print(best_match_point)
        draw_result(src, temp, best_match_point['point'])
    else:
        print("no match point")

gitee代码地址：ncc_match: ncc opencv pythonhttps://gitee.com/lzj12321/ncc_match.git

使用Qt+OpenCV自己写了一个带旋转角度的NCC灰度模板匹配算子以及它的演示软件。算子的原理是基于NCC灰度匹配。

一、什么是NCC匹配

1、基于Normalized cross correlation(NCC：归一化互相关)用来比较两幅图像的相似程度已经是一个常见的图像处理手段。在工业生产环节检测、监控领域对对象检测与识别均有应用。NCC算法可以有效降低光照对图像比较结果的影响。而且NCC最终结果在0到1之间，所以特别容易量化比较结果，只要给出一个阈值就可以判断结果的好与坏。

2、在opencv代码中，matchTemplate函数里面有个方法是cv::TM_CCOEFF_NORMED，它实现了NCC算子。CCOEFF的英文全称是：Correlation Coefficient，中文译为相关系数；NORMED是归一化的意思。但是该函数本身是不支持旋转角度和金字塔分级的，所以需要自己实现这些功能。matchTemplate函数保存在源码文件imgproc文件夹下的templmatch.cpp中。
https://github.com/opencv/opencv/blob/4.5.5/modules/imgproc/src/templmatch.cpp

3、 matchTemplate函数各个方法的计算公式如下：请重点关注NCC算子的计算方式cv::TM_CCOEFF_NORMED。公式摘录自《学习OpenCV 3》第13章，模板匹配。

二、该演示软件实现的主要功能：（未使用商业图像处理库，而是纯粹Qt+OpenCV）

1、NCC匹配

2、金字塔

3、最大重叠率

4、旋转角度

5、匹配分数

6、不支持缩放

7、模板文件读写

8、ROI框选功能，人机交互

三、部分头文件：

创建模板，对照学习halcon的算子create_ncc_model
查找物体，对照学习halcon的算子find_ncc_model

#ifndef CNCCMATCH_H
#define CNCCMATCH_H

#include "nccmodelid.h"
#include "result.h"

class VISIONCORE_EXPORT CNccMatch
{
public:
    CNccMatch();
    virtual ~CNccMatch();

public:
    void createNccModel(const cv::Mat &imageModel, int numLevels, double angleStart, double angleExtent, double angleStep, CNCCModelID &modelID);
    void findNccModel(const cv::Mat &imageSearch, const CNCCModelID &modelID, double angleStart, double angleExtent, double minScore, int numMatches, double maxOverlap, int numLevels,
                      std::vector<int> &vtRow, std::vector<int> &vtColumn, std::vector<double> &vtAngle, std::vector<double> &vtScore);

private:
    void multipleMaxLoc(const cv::Mat &image, double minScore, int numMatches, std::vector<cv::Point> &vtLocations, std::vector<double> &vtMaxima);
    void imageRotate(cv::Mat &imageSrc, double angle, cv::Mat &imageDst, cv::Mat &mask);
    void clusterAnalyze(const std::vector<SMatchResult> &vtSrc, std::vector<SMatchResult> &vtDst, double disThreshold = 10);
    void nmsMatchesRotatedRect(const std::vector<SMatchResult> &vtSrc, const cv::Size &modelsize, std::vector<SMatchResult> &vtDst, double maxOverlap);
    void nmsMatchesRect(const std::vector<SMatchResult> &vtSrc, std::vector<SMatchResult> &vtDst, double maxOverlap);
};

#endif // CNCCMATCH_H

四、演示软件截图：（未使用商业图像处理库，而是纯粹Qt+OpenCV）

五、下一版的优化改进方向

1、模板积分图像实现预计算

2、CPU指令集的优化提速

---

引申知识点：NCC匹配与形状匹配的比较

create_ncc_model
find_ncc_model
read_ncc_model
write_ncc_model
clear_ncc_model

create_scaled_shape_model
find_scaled_shape_model
read_shape_model
write_shape_model
clear_shape_model
 

1、NCC匹配优点
纹理
对焦不清
形状轻微变形
2、形状匹配优点
精度高
支持X/Y 方向缩放
支持物体遮挡
支持多模板
支持非线性光照变化

3、他人写的git

GitHub - luosch/stereo-matching: stereo-matching using SSD, NCC and ASW