图像处理(8) : 模板匹配

模板匹配指的是通过模板图像与测试图像之间的比较，找到测试图像上与模板图像相似的部分，这是通过计算模板图像与测试图像中目标的相似度来实现的，可以快速地在测试图像中定位出预定义的目标。匹配的主要思路是使用一个目标原型，根据它创建一个模板，在测试图像中搜索与该模板图像最相似的目标，并寻找与该模板的均值或方差最接近的区域。

通过模板匹配可以得到目标的相似度，旋转角度，行列坐标，缩放大小等。

针对不同的图像特征和检测环境，有多种模板匹配算法。如何选择合适的模板匹配算法，取决于具体的图像数据和匹配任务。只有理解这些算法的原理和适用场景后，才能根据项目的需要选择合适的算法。

一、基于灰度值的模板匹配

基于灰度值的模板匹配是最经典的模板匹配算法，也是最早提出来的模板匹配算法。这种算法的根本思想是，计算模板图像与检测图像之间的像素灰度差值的绝对值总和（SAD方法）或者平方差总和（SSD方法）。

其原理是：首先选择一块ROI（感兴趣区域）作为模板图像，生成基于灰度值的模板。然后将检测图像与模板图像进行粗匹配，在检测图像与模板图像中任选一点，采取隔点搜索的方式计算二者灰度的相似性，这样粗匹配一遍得到粗相关点。接下来进行精匹配，将得到的粗相关点作为中心点，用最小二乘法寻找二者之间的最优匹配点。

由于这种方法是利用模板图像的所有灰度值进行匹配，但在光照发生变化的情况下灰度值会产生强烈的变化，因此该方法不能适应光照发生变化的情况，也不能用于多通道图像的匹配，一般只用于简单图像的匹配。

灰度匹配算子原型如下：

create_template(Template : : FirstError, NumLevel, Optimize,                 GrayValues : TemplateID)

以下是一个实例：

dev_clear_window ()read_image (Image, 'C:/Users/Administrator/Desktop/test22.png')rgb1_to_gray (Image, GrayImage)gen_circle (ROI_0, 84, 180, 20)reduce_domain (GrayImage, ROI_0, ImageReduced)create_template (ImageReduced, 5, 4, 'sort', 'original', TemplateID)threshold (GrayImage, Region, 128, 255)connection (Region, ConnectedRegions)select_shape (ConnectedRegions, SelectedRegions, 'area', 'and', 1000, 50000)add_channels (SelectedRegions, GrayImage, GrayRegions)best_match (GrayRegions, TemplateID, 40, 'false', Row, Column, Error1)tuple_gen_const (|Row|, 20, Radius)dev_set_line_width (3)gen_circle_contour_xld (Circles, Row, Column, Radius, 0, 6.28318, 'positive', 1)dev_display(GrayImage)dev_display(Circles)

这种方法适用于目标图像光照比较稳定的情况，多数情况下还是优先考虑基于相关性的匹配和基于形状的匹配。只有针对极少数的简单图像，才会考虑基于灰度值的匹配。

二、基于相关性的模板匹配

基于相关性的模板匹配其实是另一种基于灰度值的匹配，不过它的特点是使用一种归一化的互相关匹配(Normalized Cross Correlation，NCC）来衡量模板图像和检测图像之间的关系，因此，在光照方面受的影响比较小。与经典的基于灰度值的匹配算法不同的是，它的速度要快很多。与基于形状模板的匹配算法相比，它的优势是对一些形状有细微变化的、纹理复杂的或者是聚焦模糊的检测图像都能检索得到。

其原理是：把模板图像中的所有像素按列顺序组成一个行向量a，即模板的特征向量，然后在检测图像上寻找与模板最匹配的区域b，通过计算两个向量的夹角，来衡量匹配的概率，如下面所示：

以下是一个实例：

read_image (Image, 'cap_exposure/cap_exposure_03')dev_close_window ()dev_open_window_fit_image (Image, 0, 0, -1, -1, WindowHandle)set_display_font (WindowHandle, 16, 'mono', 'true', 'false')dev_update_off ()gen_circle (Circle, 246, 336, 150)area_center (Circle, Area, RowRef, ColumnRef)reduce_domain (Image, Circle, ImageReduced)create_ncc_model (ImageReduced, 'auto', 0, 0, 'auto', 'use_polarity', ModelID)dev_set_draw ('margin')dev_display (Image)dev_set_color ('yellow')dev_display (Circle)disp_message (WindowHandle, 'Trained NCC model', 'window', 12, 12, 'black', 'true')disp_continue_message (WindowHandle, 'black', 'true')stop ()Rows := []Cols := []for J := 1 to 10 by 1    read_image (Image, 'cap_exposure/cap_exposure_' + J$'02')    find_ncc_model (Image, ModelID, 0, 0, 0.5, 1, 0.5, 'true', 0, Row, Column, Angle, Score)    Rows := [Rows,Row]    Cols := [Cols,Column]    dev_display (Image)    dev_display_ncc_matching_results (ModelID, 'green', Row, Column, Angle, 0)    disp_message (WindowHandle, 'Found NCC model', 'window', 12, 12, 'black', 'true')    if (J < 10)        disp_continue_message (WindowHandle, 'black', 'true')    endif    stop ()endfor

选取一块圆形区域作为模板图像，并根据其灰度值创建模板。当检测图像亮度和形状变化很大还是能够匹配得到。

该方法不但能适应光照变化，对小范围的遮挡和缺失也同样适用，同时还适用于聚焦不清的图像和形状变形，因此在实际应用中比较广泛。但是，该方法也有其局限性，如果与参考图像相比，检测图像的位移、旋转或者缩放比较大，可能会导致匹配失败。

三、基于形状的模板匹配

基于形状的模板匹配，也称为基于边缘方向梯度的匹配，是一种最常用也最前沿的模板匹配算法。该算法以物体边缘的梯度相关性作为匹配标准，原理是提取ROI中的边缘特征，结合灰度信息创建模板，并根据模板的大小和清晰度的要求生成多层级的图像金字塔模型。接着在图像金字塔层中自上而下逐层搜索模板图像，直到搜索到最底层或得到确定的匹配结果为止。

以下是一个实例：

dev_update_pc ('off')dev_update_window ('off')dev_update_var ('off')read_image (Image, 'green-dot')get_image_size (Image, Width, Height)dev_close_window ()dev_open_window (0, 0, Width, Height, 'black', WindowHandle)dev_set_color ('red')dev_display (Image)threshold (Image, Region, 0, 128)connection (Region, ConnectedRegions)select_shape (ConnectedRegions, SelectedRegions, 'area', 'and', 10000, 20000)fill_up (SelectedRegions, RegionFillUp)dilation_circle (RegionFillUp, RegionDilation, 5.5)reduce_domain (Image, RegionDilation, ImageReduced)create_scaled_shape_model (ImageReduced, 5, rad(-45), rad(90), 'auto', 0.8, 1.0, 'auto', 'none', 'ignore_global_polarity', 40, 10, ModelID)get_shape_model_contours (Model, ModelID, 1)area_center (RegionFillUp, Area, RowRef, ColumnRef)vector_angle_to_rigid (0, 0, 0, RowRef, ColumnRef, 0, HomMat2D)affine_trans_contour_xld (Model, ModelTrans, HomMat2D)dev_display (Image)dev_display (ModelTrans)read_image (ImageSearch, 'green-dots')dev_display (ImageSearch)dev_set_line_width (3)find_scaled_shape_model (ImageSearch, ModelID, rad(-45), rad(90), 0.8, 1.0, 0.5, 0, 0.5, 'least_squares', 5, 0.8, Row, Column, Angle, Scale, Score)for I := 0 to |Score| - 1 by 1    hom_mat2d_identity (HomMat2DIdentity)    hom_mat2d_translate (HomMat2DIdentity, Row[I], Column[I], HomMat2DTranslate)    hom_mat2d_rotate (HomMat2DTranslate, Angle[I], Row[I], Column[I], HomMat2DRotate)    hom_mat2d_scale (HomMat2DRotate, Scale[I], Scale[I], Row[I], Column[I], HomMat2DScale)    affine_trans_contour_xld (Model, ModelTrans, HomMat2DScale)    dev_display (ModelTrans)endfor

该方法使用边缘特征定位物体，对于很多干扰因素不敏感，如光照和图像的灰度变化，甚至可以支持局部边缘缺失、杂乱场景、噪声、失焦和轻微形变的模型。更进一步说，它甚至可以支持多个模板同步进行搜索。但是，在搜索过程中，如果目标图像发生大的旋转或缩放，则会影响搜索的结果，因此不适用于旋转和缩放比较大的情况。

四、基于组件的模板匹配

基于组件的模板匹配可以说是基于形状的模板匹配的加强版，加强的地方在于，这种方法允许模板中包含多个目标，并且允许目标之间存在相对运动（位移和旋转)。这决定了这种方式不适用于尺寸缩放的情况。由于有多个ROI，且需要检测多个ROI之间的相对运动关系，因此这种方法与基于形状的模板匹配相比要稍微复杂一点，且不适用于失焦图像和轻微形变的目标。

以下是一个实例：

dev_update_off ()dev_close_window ()read_image (ModelImage, 'modules/modules_model')dev_open_window_fit_image (ModelImage, 0, 0, -1, -1, WindowHandle)dev_display (ModelImage)set_display_font (WindowHandle, 16, 'mono', 'true', 'false')Message := 'This program shows how to use the'Message[1] := 'component-based matching'Message[2] := 'to locate a compound object'disp_message (WindowHandle, Message, 'window', 12, 12, 'black', 'true')disp_continue_message (WindowHandle, 'black', 'true')stop ()* * Define the regions for the componentsgen_rectangle2 (ComponentRegions, 318, 109, -1.62, 34, 19)gen_rectangle2 (Rectangle2, 342, 238, -1.63, 32, 17)gen_rectangle2 (Rectangle3, 355, 505, 1.41, 25, 17)gen_rectangle2 (Rectangle4, 247, 448, 0, 14, 8)gen_rectangle2 (Rectangle5, 237, 537, -1.57, 13, 10)concat_obj (ComponentRegions, Rectangle2, ComponentRegions)concat_obj (ComponentRegions, Rectangle3, ComponentRegions)concat_obj (ComponentRegions, Rectangle4, ComponentRegions)concat_obj (ComponentRegions, Rectangle5, ComponentRegions)dev_set_colored (12)dev_set_draw ('margin')dev_set_line_width (2)dev_display (ModelImage)dev_display (ComponentRegions)set_display_font (WindowHandle, 16, 'mono', 'true', 'false')disp_message (WindowHandle, 'Regions of the components', 'window', 12, 12, 'black', 'true')disp_continue_message (WindowHandle, 'black', 'true')stop ()* * Create the component model by explicitly specifying the relationscreate_component_model (ModelImage, ComponentRegions, 20, 20, rad(25), 0, rad(360), 15, 40, 15, 10, 0.8, [4,3,3,3,3], 0, 'none', 'use_polarity', 'true', ComponentModelID, RootRanking)* * Find the component model in a run-time imageImageName := 'modules/modules_'for I := 1 to 12 by 1    read_image (SearchImage, ImageName + I$'.2d')    find_component_model (SearchImage, ComponentModelID, RootRanking, 0, rad(360), 0.5, 0, 0.5, 'stop_search', 'search_from_best', 'none', 0.8, 'interpolation', 0, 0.8, ModelStart, ModelEnd, Score, RowComp, ColumnComp, AngleComp, ScoreComp, ModelComp)    dev_display (SearchImage)    * Display the found component models    for Match := 0 to |ModelStart| - 1 by 1        dev_set_line_width (1)        get_found_component_model (FoundComponents, ComponentModelID, ModelStart, ModelEnd, RowComp, ColumnComp, AngleComp, ScoreComp, ModelComp, Match, 'false', RowCompInst, ColumnCompInst, AngleCompInst, ScoreCompInst)        dev_display (FoundComponents)    endfor    disp_message (WindowHandle, 'Found component models', 'window', 12, 12, 'black', 'true')    * If the program shall stop after every image, the following lines    * must be activated    if (I < 12)        disp_continue_message (WindowHandle, 'black', 'true')    endif    stop ()endfor

本例在图中选取了几个元器组件作为模板图像，并根据其形状和相对关系创建了模板，图像在旋转的情况下仍得到了理想的匹配结果。

基于组件的模板匹配适用于组成部件之间有相对运动的物体，使用边缘特征定位物体，对于很多干扰因素不敏感，如光照变化、混乱无序等。其适用于多通道图像，不适用于纹理图像、聚焦不清的图像和形状变形的图像。

五、基于形变的模板匹配

形变分为两种，一种是基于目标局部的形变，另一种是由于透视关系而产生的形变。基于形变的模板匹配也是一种基于形状的匹配方法，但不同的是，其返回结果中不仅包括轻微形变的形状、形变的位置和参数，还有描述形变的参数，如旋转角度、缩放倍数等。

基于透视的形变可以返回一个二维投影变换矩阵。如果是在相机标定的情况下，通过相机参数，还可以计算出目标的三维位姿。

以下是一个实例：

dev_update_off ()dev_close_window ()read_image (ModelImage, 'food/peanut_chocolate_candies_model')dev_open_window_fit_image (ModelImage, 0, 0, -1, -1, WindowHandle)set_display_font (WindowHandle, 16, 'mono', 'true', 'false')* * 创建一个模板create_local_deformable_model (ModelImage, 'auto', [], [], 'auto', 1, [], 'auto', 1, [], 'auto', 'none', 'use_polarity', 65, 25, [], [], ModelID)get_deformable_model_contours (ModelContours, ModelID, 1)area_center (ModelImage, Area, Row, Column)hom_mat2d_identity (HomMat2DIdentity)hom_mat2d_translate (HomMat2DIdentity, Row, Column, HomMat2DTranslate)affine_trans_contour_xld (ModelContours, ContoursAffineTrans, HomMat2DTranslate)dev_set_line_width (2)dev_set_color ('yellow')dev_display (ModelImage)dev_display (ContoursAffineTrans)disp_message (WindowHandle, 'Model image and contours', 'window', 12, 12, 'black', 'true')disp_continue_message (WindowHandle, 'black', 'true')stop ()Smoothness := 19NumImages := 12for Index := 1 to NumImages by 1    read_image (Image, 'food/peanut_chocolate_candies_' + Index$'02')    dev_resize_window_fit_image (Image, 0, 0, -1, -1)    dev_display (Image)    disp_message (WindowHandle, 'Search ...', 'window', 12, 12, 'black', 'true')    count_seconds (S1)    * 查找    find_local_deformable_model (Image, ImageRectified, VectorField, DeformedContours, ModelID, rad(-120), rad(60), 1, 1, 1, 1, 0.3, 0, 0.7, 0, 0.1, ['vector_field','deformed_contours'], ['deformation_smoothness','expand_border','subpixel'], [Smoothness,0,0], Score, Row, Column)    count_seconds (S2)    Time := S2 - S1      * 显示结果    gen_warped_mesh (VectorField, WarpedMesh, Smoothness)    dev_set_line_width (1)    dev_set_color ('yellow')    dev_display (WarpedMesh)    Found[Index] := |Score|    dev_set_line_width (2)    dev_set_color ('green')    dev_display (DeformedContours)    disp_message (WindowHandle, |Score| + ' matches found in ' + Time$'1.2f' + ' s', 'window', 12, 12, 'black', 'true')    disp_message (WindowHandle, 'Score: ' + Score$'.2f', 'image', 350, Column - 80, 'black', 'true')    if (Index < NumImages)        disp_continue_message (WindowHandle, 'black', 'true')        stop ()    endifendfor

六、基于描述符的模板匹配

与基于透视形变的模板匹配类似，基于描述符的模板匹配能够在物体处于透视形变的状态下进行匹配，并且已标定和未标定的相机图像都适用。与透视形变不同的是，它的模板不是根据边缘轮廓创建的，而是根据特征点创建的。

点的位置或相邻像素的灰度信息等都可以作为描述符。有纹理的平面图形非常适用于这种方法，尤其是对于旋转倾斜等场景中的匹配可以得到非常理想的结果。

以下是一个实例：

dev_close_window ()*读取参考图像，这里的参考图像应只包含识别的关键区域，用于创建模板read_image (ImageLabel, 'data/labelShape-0')*设置窗口参数用于显示图像get_image_size (ImageLabel, Width, Height)dev_open_window (0, 0, Width, Height, 'black', WindowHandle1)dev_set_draw ('margin')dev_display (ImageLabel)*设置用于存储特征点和感兴趣区域的变量NumPoints := []RowRoi := [10,10,Height - 10,Height - 10]ColRoi := [10,Width - 10,Width - 10,10]*将参考图像中的除边缘外的区域都设为感兴趣区域。因为参考图像已经近似于匹配的纹理样本gen_rectangle1 (Rectangle, 10, 10, Height - 10, Width - 10)*显示参考图像上选择的ROI区域dev_set_line_width (4)dev_display (Rectangle)stop ()*将感兴趣区域剪裁为模板图像reduce_domain (ImageLabel, Rectangle, ImageReduced)dev_clear_window ()dev_display (ImageLabel)*创建基于描述符的模板create_uncalib_descriptor_model (ImageReduced, 'harris_binomial', [], [], ['min_rot','max_rot','min_scale','max_scale'], [-90,90,0.2,1.1], 42, ModelID)*设置模型的原点，为了后面获取坐标作参照set_descriptor_model_origin (ModelID, -Height / 2, -Width / 2)*获取模型中特征点的位置get_descriptor_model_points (ModelID, 'model', 'all', Row_D, Col_D)*将模型中计算出的特征点存入NumPoints变量中NumPoints := [NumPoints,|Row_D|]*读取测试图像，这里读取的是单通道灰度图像，因此省略了通道转化的步骤read_image (ImageGray, 'data/labelShape-1')dev_resize_window_fit_image (ImageGray, 0, 0, -1, -1)dev_display (ImageGray)*对描述符特征点进行匹配find_uncalib_descriptor_model (ImageGray, ModelID, 'threshold', 800, ['min_score_descr','guided_matching'], [0.003,'on'], 0.25, 1, 'num_points', HomMat2D, Score)*显示匹配结果，将特征点用不同的颜色绘制出来if ((|HomMat2D| > 0) and (Score > NumPoints[0] / 4))    get_descriptor_model_points (ModelID, 'search', 0, Row, Col)  *创建十字标识符    gen_cross_contour_xld (Cross, Row, Col, 6, 0.785398)    projective_trans_region (Rectangle, TransRegion, HomMat2D, 'bilinear')    projective_trans_pixel (HomMat2D, RowRoi, ColRoi, RowTrans, ColTrans)    angle_ll (RowTrans[2], ColTrans[2], RowTrans[1], ColTrans[1], RowTrans[1], ColTrans[1], RowTrans[0], ColTrans[0], Angle)    Angle := deg(Angle)    if (Angle > 70 and Angle < 110)        area_center (TransRegion, Area, Row, Column)        dev_set_color ('green')        dev_set_line_width (4)        dev_display (TransRegion)        dev_set_colored (6)        dev_display (Cross)                   endifendifstop ()*匹配结束，释放模板资源clear_descriptor_model (ModelID)

图中五颜六色的点就是特征点，基于描述符的模板匹配只能用于有纹理的图像。

七、基于点的模板匹配

基于点的模板匹配主要是用在三维匹配中，通过寻找图像中对应的特征点，进行两幅重叠图像的拼接等操作，在相机标定的情况下被广泛应用。其主要原理是通过提取两幅图像之间的重要特征点实现匹配。把这些特征点作为匹配的输入，输出部分则是两幅图像之间的映射关系，支持图像的位移、旋转、缩放和透视形变。

同时，也可以把两幅图中的一幅作为模板，另一幅看作检测图像的一个实例。该方法在透视形变的情况下无须标定就能完成匹配，但是运行时间会增加，增加的时间主要来自特征点的提取。

八、模板匹配方法总结

选择适合的模板匹配方法可以事半功倍。

（1）基于灰度值的模板匹配

适用于目标区域灰度值比较稳定，检测图像与模板图像相似度高，且具有相同的外界条件的场景。不适用于杂乱场景、遮挡、光照变化、尺寸缩放及多通道图像。

（2）基于相关性的模板匹配

适用于失焦图像、轻微形变、线性光照变化及轮廓模糊的图像，对纹理图像尤为支持。不适用于杂乱场景、遮挡、非线性光线变化、大幅的旋转、尺寸缩放和多通道图像。

（3）基于形状的模板匹配

适用于目标轮廓比较清晰的场景。适用于杂乱场景、遮挡、非线性光照变化、尺寸缩放、失焦和轻微形变的图像，以及多通道图像和多个模板的同步匹配，不适用于纹理复杂的图像。

（4）基于组件的模板匹配

适用于多个目标的匹配场景。适用于杂乱场景、遮挡、非线性光照变化的图像，以及多通道图像和多个模板的同步匹配。不适用于纹理复杂的图像，以及失焦和形变的图像。

（5）基于局部形变的模板匹配

适用于杂乱场景、遮挡、非线性光照变化、尺寸缩放和轻微局部形变的图像，以及多通道图像.

（6）基于透视形变的模板匹配

适用于杂乱场景、遮挡、非线性光照变化、尺寸缩放、失焦和透视形变的图像，以及多通道图像。但是对于纹理图像的支持不够好。

（7）基于描述符的模板匹配

适用于杂乱场景、遮挡、非线性光照变化、尺寸缩放、轻微局部形变、透视形变的图像，以及有纹理的图像，不适用于失焦和多通道图像。

（8）基于点的模板匹配

用于在多幅部分重合的图像之间建立对应的关系。

Original: https://blog.51cto.com/u_13267193/5392821
Author: QtHalcon
Title: 图像处理(8) : 模板匹配