65.9K
CodeProject 正在变化。 阅读更多。
Home

C# 中的快速对象检测

Darko Jurić
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.98/5 (49投票s)

2014年10月8日

LGPL3

9分钟阅读

viewsIcon

196938

通过模板匹配进行快速对象检测。

视频图标。 - 点击观看视频
Fast hand template matching Fast traffic sign template matching
快速手部模板匹配
快速交通标志模板匹配

目录

  1. 引言
  2. 背景
  3. 模板匹配算法
  4. 使用代码
  5. 检测自定义对象
  6. 结果
  7. 结论
  8. 参考文献

引言

在计算机视觉应用中，对象检测和定位是一项常见的任务。对象检测方法可以分为三类：手工制作方法，包含一些预定义的规则和启发式方法；机器学习方法，将对象信息编码到分类器中；第三种方法是介于两者之间——模板匹配。

虽然基于机器学习的方法通常被认为是最好的，但在某些情况下它们并不理想。一个原因是训练过程通常需要大量的训练样本，而收集这些样本并不总是容易的任务。训练过程通常耗时很长，并且训练好的分类器无法立即进行调整。

模板匹配过程简单且足够鲁棒，可以处理复杂场景，并且不需要大量的训练。此外，叠加模板可以提供对象的外观，这是流行的机器学习滑动窗口方法（例如 Viola-Jones）无法做到的。这种能力可以用作独立过程或后处理技术（例如，在 Viola-Jones 技术之后）来精确地定位对象。最近，在 2012 年，Hinterstoisser 等人提出了一种新的模板匹配过程 [1]，它比标准的滑动窗口模板匹配方法快约 20 倍。这个过程（稍有改进）现在是 Accord.NET 扩展框架的一部分，本文将简要介绍它，并附带示例和用法场景。由于该过程的复杂性，详细解释被省略，但可以在 原始文章 中找到。

背景

标准的模板匹配技术将每个模板以滑动窗口的方式与图像的一部分进行比较。该过程可以与大卷积核的卷积过程相比较，这显然需要一些时间。模板可以用多种方式表示：彩色图像、梯度幅度图像、方向图像。研究表明，梯度方向对于光照变化具有相当好的鲁棒性，因此梯度方向图像表示经常被使用。2012 年出现的新颖过程 [1] 也使用梯度方向图像作为输入。不同之处在于模板匹配步骤，其中通过利用硬件和 CPU 结构来完成朴素卷积。最终结果是一个快速而鲁棒的模板匹配算法，可用于许多应用；在此：手部检测和交通标志检测。

模板匹配算法

模板匹配过程可分为五个步骤，下面将简要描述。有关该过程的完整解释，请参见 [1]。

Template matching.
模板匹配管道。 模板匹配管道。红色矩形表示扩展部分。

  1. 梯度提取

    至关重要的预处理步骤是边缘提取，其中边缘方向图像是模板匹配方法的输入图像 [1]。图像方向之所以被选择，主要原因之一是它们对广泛的光照变化和图像噪声具有鲁棒性。在具有背景杂乱的场景中，梯度幅度由于存在许多误报而表现不佳。在 [1] 中，使用了多通道 Sobel 算子，从中提取具有最大幅度的通道的像素方向。此外，方向会进行过滤，以便仅保留 3x3 邻域内的主要方向。实现的该方法支持上述方法以及从灰度图像提取的传统方向提取，以实现计算量较低的方法，其中一部分如下所示。

    short* dxPtr, dyPtr = ... //input dX and dY Sobel derivative images
int* magSqrPtr = ... //output gradient magnitude image
int* orientImagePtr = ... //output orientation image
for (int j = 0; j < imgHeight; j++)
{
    for (int i = 0; i < imgWidth; i++)
    {
        int magSqr = dxPtr[0] * dxPtr[0] + dyPtr[0] * dyPtr[0];
        if (magSqr < minValidMagSqr)
            *orientImgPtr = FeatureMap.INVALID_ORIENTATION;
        else
        {
            *orientImgPtr = MathExtensions.Atan2Aprox(*dyPtr, *dxPtr);
            *magSqrImgPtr = magSqr;
        }
        dxPtr += 1; dyPtr += 1;
        orientImgPtr += 1; magSqrImgPtr += 1;
    }
    ...
}

  2. 梯度方向量化

    每个梯度方向被量化为最多 8 个方向，以便将每个方向显示为位标志。该表示可以轻松地进行操作。下面的代码显示量化过程使用预计算的查找表进行角度量化。

    int* orientDegImgPtr = ... //orientation image pointer
int imgWidth, imgHeight = ... //image width and height
byte[] AngleQuantizationTable = ... //maps [0-360] -> [...] -> [0-7]
for (int j = 0; j < imgHeight; j++)
{
    for (int i = 0; i < imgWidth; i++)
    {
        int angle = orientDegImgPtr[i];
        qOrinetUnfilteredPtr[i] = AngleQuantizationTable[angle]; 
    }
    
    ...
}

  3. 梯度方向扩散

    由于物理特性或噪声，图像对象可能会变形，这会导致对象和相应模板之间的边缘对齐不完美。为了提高鲁棒性，方向会在局部邻域上扩散。由于每个方向都可以写成一个单独的位，因此扩散方向只是某些像素与其邻近像素之间的按位 OR 操作，如下所示。

    byte* srcImgPtr = ... //input quantized orientation image
byte* destImgPtr = ... //output spread quantized orientattion image
int neighborhood = ... //spread factor
for (int row = 0; row < neghborhood; row++)
{
    int subImageHeight = imgHeight - row;
    for (int col = 0; col < neghborhood; col++)
    {
       //get shifted image and 
       //do the bitwise OR operation for each pixel
        OrImageBits(&srcImgPtr[col], destImgPtr,
                    imgStride,
                    imgWidth - col, subImageHeight);
    }
    ...
}

  4. 构建响应图和线性内存

    模板使用等同于在输入图像上滑动模板的操作与图像中的每个位置进行匹配。与标准的模板匹配过程相反，输入图像会进行预处理，以便通过添加长数组——线性内存——来非常快速地执行匹配过程。有关详细信息，请参阅 [1]。每个线性内存单元包含 [0..n] 范围内的相似度，其中 n 是用户指定的两个量化方向之间的最大相似度。这些值受 8 位值中位数位数的限制。通过使用 SIMD 处理器体系结构，可以非常有效地进行线性内存加法，从而实现实时模板匹配。

    //calculate linear response maps
private Image<Gray<byte>>[][,] calculate(Gray<int>[,] orientationDegImg)
{
    //the number of linear memories is equal to the number of quantized orientations
    var linearMaps = new Image<Gray<byte>>[GlobalParameters.NUM_OF_QUNATIZED_ORIENTATIONS][,];

    //first create spread quantized orientation image
    Gray[,] sprededQuantizedOrient = FeatureMap.Calculate(orientationDegImg, this.NeigborhoodSize);
    //for each quantized orientation calculate pre-calculate similarity image 
    //(response map) between the orientation image and specified orientation
    for (int orient = 0; orient < GlobalParameters.NUM_OF_QUNATIZED_ORIENTATIONS; orient++)
    {
        //...and finally make linear memory for each response map 
        //by taking every Tth pixel and putting them into one array
        var responseMap = computeResponseMap(sprededQuantizedOrient, orient);
        linearMaps[orient] = linearizeResponseMap(responseMap);
    }

    return linearMaps;
}

  5. 匹配过程

    每个 模板特征（由位置和相应的量化方向组成）用于选择线性内存（8 位向量）。将选定的内存加到以零初始化的 8 位结果向量中。结果向量包含每个位置的原始模板匹配分数，范围在 [0..255] 之间。这些值被缩放到 [0..100] 的范围。对结果向量进行阈值处理，以提取最强的匹配项。有关线性内存内容和创建的详细信息，请参阅 [1]。SIMD 数组加法指令在一个单独的项目中编写，如下所示。

    SIMD in project.
    SIMD 数组指令。 SIMD 数组加法指令在单独的 C 项目中。快速内存加法是实时模板匹配过程的关键步骤。

    函数通过 P/Invoke 导出到 C#。

    //byte-to-byte array addition
[SuppressUnmanagedCodeSecurity] //add some performance by skipping some checks
[DllImport("SIMDArrayInstructions.dll", CallingConvention = CallingConvention.Cdecl, ExactSpelling = true)]
public static extern void AddByteToByteVector(byte* srcAddr, byte* dstAddr, int numOfElemsToAdd);
//byte-to-short array addition
[SuppressUnmanagedCodeSecurity]
[DllImport("SIMDArrayInstructions.dll", CallingConvention = CallingConvention.Cdecl, ExactSpelling = true)]
public static extern void AddByteToShortVector(byte* srcAddr, short* dstAddr, int numOfElemsToAdd);

    特征数量增加 - 扩展

    8 位结果向量决定了每个模板的最大特征数量，因为每个线性单元包含一个值，该值最大为两个量化方向之间的最大相似度 - n，并且相加的线性内存数量对应于模板特征的数量。因此，在原始论文中，每个模板的最大特征数量限制为 ⌊255 / n⌋。为了克服此限制，首先将线性图添加到临时缓冲区 - 8 位向量，然后在缓冲区溢出之前，将缓冲区添加到最终结果数组（16 位），其中包含模板匹配分数。此过程对每个模板特征重复执行。将值累积到结果数组后，缓冲区将被清除。有关详细信息，请参见下图。

    线性内存加法。

    结果是最大特征数量的增加 ⌊65535/n⌋。 性能比较显示了与传统模板匹配方法相比的显着加速。n 表示两个特征之间的最大相似度，F 表示特征的数量。

金字塔扩展

该方法可以扩展到使用金字塔方法，如原始论文所示。为每个金字塔级别构建线性内存表示，并为最小图像和包含候选者的较低金字塔级别的每个块执行匹配过程。这种方法可以加速和更精确地定位对象。实现的该代码支持此功能，但仅使用一个级别（原始级别）。

Pyramidal search
金字塔搜索。 模板匹配过程对每个金字塔级别执行。较高金字塔级别的图像被完整扫描。此处显示的是 5x5 像素的块。如果在较高金字塔级别的图像中找到候选者，则将块和模板一起缩放（离线完成模板构建），然后重复匹配过程，但这次是针对候选块。

Using the Code

使用该代码非常简单。该实现包括一个用于图像预处理的单个方法和一个用于模板匹配的扩展方法。默认情况下，所有参数都具有默认值，因此用户无需了解算法的工作原理。并行模板匹配默认启用，这意味着更多的 CPU 核心可以实现更快的处理。通过线性内存扩展方法可以获得更多选项。

Gray<byte>[,] grayImage = .... 
List<TemplatePyramid> templatePyramids = ... //off-line made templates

var linPyr = LinearizedMapPyramid.CreatePyramid(grayImage); //prepare linear-pyramid maps
List<Match> matches = linPyr.MatchTemplates(templPyrs); //match templates

foreach(var m in matches) //draw matches
{
   frame.Draw(m.BoundingRect, Bgr8.Blue, 3, true, Bgr8.Red);
}

linPyr.Dispose();

NuGet 包

尽管该实现使用了非托管库，但提供的 NuGet 包是平台抽象的 - 目前（x86 /x64 - Windows）。根据运行的操作系统体系结构，会加载适当的非托管库，因此开发人员无需单独处理多个操作系统体系结构。下图显示了预编译库的位置。

预编译库。 非托管库是预编译的，并根据操作系统体系结构按需加载。

检测自定义对象

为了检测自定义对象，必须创建描述对象外轮廓的二进制模板。构建自己的模板也很容易，除了创建模板本身。模板构建过程可分为三个步骤，并将在开放手部样本上进行解释。

  1. 准备模板

    每个模板都表示为二进制图像。手部模板是通过更复杂的方式获得的。每个开放手部样本都使用彩色摄像头在某些均匀背景下进行拍摄，然后应用 k=2 的 KNN 算法以去除均匀背景。可以使用某些绘图应用程序（例如 Microsoft Paint）轻松创建简单的模板。

    Template samples
    模板样本。 开放手部模板的三个样本。有几个模板变体，然后将它们缩放以实现尺度不变性。

  2. 缩放模板

    为了检测与大小无关的对象，必须缩放每个模板。必要的 MATLAB（Octave）脚本包含在示例项目中。模糊边缘有助于特征提取过程，因此建议在二进制图像模板上应用高斯平滑。

    Scripts in project.
    脚本位置。 用于模板缩放的 MATLAB（Octave）脚本包含在示例项目中。

  3. 提取特征

    特征提取过程和模板创建仅包含一个函数。

    List<TemplatePyramid> templatePyrs = new List<TemplatePyramid>()
foreach(var preparedBWImage in bwImages)
{
   var tp = TemplatePyramid.CreatePyramidFromPreparedBWImage(preparedBWImage, "OpenHand");
   templatePyrs.Add(tp);
}
    Template features samples.
    特征样本。 从模板提取的特征用绿色表示。红点表示均匀分布的特征位置。

结果

该算法的结果是与传统模板匹配方法相比的显着加速。

performance compairision
与传统匹配过程相比的加速。 传统和加速模板匹配性能比较。每个模板的特征数量为 100。所有测试均在 Intel Core i5-2500K CPU 上使用单核进行。

以下两个视频链接代表了包含在示例中的手部模板匹配演示，以及使用此方法作为基础的交通标志形状检测。

示例 视频图标。 - 点击观看视频
Fast hand template matching Fast traffic sign template matching
快速手部模板匹配
快速交通标志模板匹配

结论

本文介绍了一种可以用于快速简单对象检测的快速模板匹配方法。代码包含完整的源代码以及开放手部检测示例，该示例可针对其他对象类型进行调整。源代码和示例代码是 Accord.NET 扩展框架的一部分，该框架提供了许多高级算法，主要用于图像处理、对象检测和跟踪，所有这些都打包为流畅的扩展和简单直观的泛型，所以不要忘记一瞥一下 :）。

参考文献

[1] Hinterstoisser, S.; Cagniart, C.; Ilic, S.; Sturm, P.; Navab, N.; Fua, P.; Lepetit, V., "Gradient Response Maps for Real-Time Detection of Textureless Objects," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.34, no.5, pp.876,888, May 2012
免费访问版本

历史

  • 2014 年 10 月 5 日 - 发布第一个版本
C# 中的快速对象检测 - CodeProject - 代码之家
© . All rights reserved.