C# 中的图像识别轮廓分析

• 下载源代码 - 2.76 MB
• 下载演示 - 2.74 MB

源代码和演示包含所有必需的OpenCV库。项目需要.NET Framework 4。

引言

本文介绍了轮廓分析的理论基础及其在图像识别中的实际应用方面。本文还包括用于轮廓分析操作的库和一个演示示例。

文章的第一部分包含轮廓分析的主要定义和定理。我试图选择主要的关键点，以便足够快地理解轮廓分析的本质，并开始在实践中应用它。此外，我还添加了一些自己的观点。核心内容涉及理论的某些方面以及轮廓分析算法的优化问题。文章的第二部分专门讨论了这些问题。同时，还介绍了算法的工作结果，并描述了该方法的缺点和不足。

第三部分描述了 C# 库 ContourAnalysis。

第一部分：轮廓分析（CA）的基础

轮廓分析（CA）的必要性

CA 允许描述、存储、比较和查找以外部轮廓形式呈现的对象。

轮廓被认为包含对象形状的必要信息。对象的内部点不予考虑。这限制了 CA 算法的适用范围，但仅审查轮廓允许从图像的二维空间过渡到轮廓空间，从而降低计算和算法的复杂性。

CA 能够有效地解决模式识别的主要问题——对象的图像的平移、旋转和缩放。CA 方法对这些变换具有不变性。

主要概念

首先，我们定义对象轮廓。轮廓是对象的边界，是区分对象和背景的点（像素）的集合。

在计算机视觉系统中，使用一些轮廓编码格式——Freeman码、二维编码、多边形编码最为知名。但所有这些编码格式都不用于CA。

相反，在 CA 中，轮廓由一系列复数编码。在轮廓上，固定一个称为起始点的点。然后，扫描轮廓（允许顺时针），每个偏移向量由复数 a+ib 表示。其中 a - x 轴上的点偏移，b - y 轴上的偏移。偏移是相对于前一个点而言的。

由于三维物体的物理性质，它们的轮廓总是封闭的，不能有自相交。这允许明确定义轮廓的遍历方式（方向——顺时针或逆时针）。轮廓的最后一个向量总是指向起始点。

我们将轮廓的每个向量称为基本向量（EV）。将复数值序列称为向量轮廓（VC）。

我们将用希腊大写字母表示向量轮廓，用希腊小写字母表示它们的基本向量。

因此，长度为 k 的向量轮廓 Γ 可以表示为

为什么在CA中要使用复数编码？因为与其他的编码方式相比，将轮廓视为复数向量进行操作，具有卓越的数学特性。

基本上，复数编码与二维编码接近，其中轮廓被定义为以二维坐标表示的EV集合。但是向量的标量积和复数的标量积的运算有所不同。这种情况也使CA方法具有优先权。

轮廓的性质

1. 闭合轮廓的EV之和等于零。这是显而易见的——由于基本向量最终回到起点，它们的和等于零向量。
2. 轮廓向量不依赖于源图像的平行平移。由于轮廓是相对于起始点编码的，这种编码模式对初始轮廓的平移具有不变性。
3. 图像旋转一定角度相当于轮廓的每个EV旋转相同的角度。
4. 起始点修改导致VC循环移位。由于EV是相对于前一个点编码的，因此很明显，在修改起始点时，EV序列将相同，但第一个EV将是起始点处的EV。
5. 源图像的重新缩放可以看作是轮廓的每个 EV 乘以比例因子。

轮廓的标量积

轮廓 Γ 和 N 的标量积被称作这样的复数

其中 k - VC 的维度，γ_n - 轮廓 Γ 的第 n 个基本向量，ν_n - 轮廓 N 的第 n 个 EV。(γ_n, ν_n) - 复数的标量积，计算方式为

我们要注意，在CA中，标量积只假定相同维度的VC。也就是说，轮廓中基本向量的数量应该一致。

普通向量的标量积和复数的标量积是不同的。如果我们将 EV 简单地作为向量相乘，它们的标量积将是这样

比较此公式和公式（2），你会发现

• 向量的标量积结果是实数。而复数积的结果是复数。
• 复数标量积的实部与相应向量的标量积一致。也就是说，复数积包含向量标量积。

现在让我们回忆一下线性代数。确切地说，是标量积的物理意义和性质。在线性代数中，标量积等于向量长度乘以它们之间夹角的余弦。这意味着两个垂直向量的标量积始终为零，共线向量（反向）将给出标量积的最大值。

这些积的性质使其可以作为向量之间接近程度的某种度量。如果它越大——向量之间的夹角越小，它们就越“接近”。对于垂直向量——它降为零，并且对于方向相反的向量——它变为负值。似乎标量积（1）也具有相似的性质。

让我们再引入一个概念——归一化标量积（NSP）

其中 |Γ| 和 |N| - 轮廓的范数（长度），计算方式为

复数空间中的 NSP 也是一个复数。

因此，1 是 NSP 范数的最大可能值（由柯西-布尼亚科夫斯基-施瓦茨不等式得出：|ab| <= |a||b|），它仅在...时达到

……其中 μ 是任意复数。

这在实践中意味着什么？我们回顾复数乘法的物理意义。在复数乘法中，它们的长度相乘，而辐角（角度）相加。轮廓 μN 意味着它是相同的轮廓 N，但经过了旋转和缩放。缩放和旋转由复数 μ 定义。

因此，NSP 的范数仅当轮廓 Γ 与轮廓 N 相同，但经过某个角度旋转和某个系数缩放时，才达到最大值 - 1。

举例来说，我们考虑轮廓自身与其旋转一定角度后的标量乘法。

因此，如果计算向量自身与自身的 NSP，我们得到 NSP=1；如果将轮廓旋转 90 度，我们得到 NSP=0+i；旋转 180 度得到 NSP=-1。因此，NSP 的实部将给出轮廓之间角度的余弦，而 NSP 的范数将始终等于 1。

类似地，如果我们通过某个实系数（比例）增加一个 VC，我们也会得到 NSP=1（从公式（4）很容易看出）。

注意：NSP 的范数对轮廓的平移、旋转和缩放是不变的。

因此，轮廓的归一化标量积的范数仅当这两个轮廓在旋转和比例上相等时才为1。否则，NSP的范数将严格小于1。

这是 CA 的核心结论。实际上，NSP 的范数在轮廓的平移、旋转和缩放方面是一个不变量。如果存在两个相同的轮廓，它们的 NSP 总是为 1，这与轮廓的位置、旋转角度和比例无关。同样，如果轮廓不同，它们的 NSP 将严格小于 1，并且也与位置、旋转和比例无关。

注意：NSP 的范数是轮廓接近程度的度量。

范数给出了轮廓相似度的度量，而NSP的幅角（等于atan(b/a)）给出了轮廓之间相对旋转的角度。

轮廓的互相关函数

在上一章中，我们确定NSP对于寻找彼此相似的轮廓是一个非常有用的公式。不幸的是，有一个情况不允许直接使用它。而这种情况就是起始点的选择。

问题在于等式（6）仅在轮廓的起始点重合时才能达到。如果轮廓相同，但 EV 参考从其他起始点开始，则此类轮廓的 NSP 范数将不等于 1。

问题在于等式（6）仅在轮廓的起始点重合时才能达到。如果轮廓相同，但 EV 参考从其他起始点开始，则此类轮廓的 NSP 范数将不等于 1。

让我们引入两个轮廓的互相关函数（ICF）的概念。

其中 N^(m) - 从 N 获得的轮廓，通过其 EV 循环移位 m 个元素。

例如，如果 N = (n1, n2, n3, n4)，则 N⁽¹⁾ = (n2, n3, n4, n1)，N⁽²⁾ = (n3, n4, n1, n2)，依此类推。

互相关函数显示什么？此函数的值表示轮廓 Γ 和 N 在将起始点 N 移动 m 个位置后有多相似。

ICF 在所有整数集上定义，但由于对 k 的循环移位将我们带回初始轮廓，ICF 是周期性的，周期为 k。因此，我们只对函数在 0 到 k-1 范围内的值感兴趣。

让我们找出在 ICF 值中具有最大范数的值。

从NSP和ICF的定义可以清楚地看出，τ_max是衡量两个轮廓相似度的量度，它对平移、缩放、旋转和起始点位移是不变的。

因此，范数 |τ_max| 表示轮廓的相似度水平，对于相同的轮廓达到单位，而参数 arg(τ_max) 给出了一个轮廓相对于另一个轮廓的旋转角度。

注意：ICF 范数的最大值是两个轮廓相似度的度量。

注意：ICF 范数的最大值对平移、缩放、旋转和起始点偏移是不变的。

我们再引入一个概念——自相关函数（ACF）。自相关函数是 ICF，其中 N=Γ。实际上，它是一个轮廓在不同起始点偏移下自身与其自身的标量积。

让我们考虑ACF的一些性质

1. ACF 不依赖于轮廓起始点的选择。确实，我们看一下标量积的定义（1）。正如我们所看到的，起始点修改只会导致可加元素的顺序修改，而不会导致总和修改。这个结论不那么明显，但如果思考 ACF 的意义，它就很清楚了。
2. ACF的范数关于中心参考点k/2对称。由于ACF是轮廓EV的成对乘积之和，每对在0到k的区间内出现两次。

   例如，设 N = (n1, n2, n3, n4)，我们写出不同 m 值的 ACF

   ACF(0)=(n1,n1)+(n2,n2)+(n3,n3)+(n4,n4)
   ACF(1)=(n1,n2)+(n2,n3)+(n3,n4)+(n4,n1)
   ACF(2)=(n1,n3)+(n2,n4)+(n3,n1)+(n4,n2)
   ACF(3)=(n1,n4)+(n2,n1)+(n3,n2)+(n4,n3)
   ACF(4)=(n1,n1)+(n2,n2)+(n3,n3)+(n4,n4)

   我们注意到ACF(1)中的项与ACF(3)中的项相同，只是因子顺序不同。回想复数(a, b) = (b, a)*我们得到一个ACF(1) = ACF(3)*，其中 * - 共轭复数符号。

   正如|a*| = |a|结果是 ACF(1) 和 ACF(3) 的范数重合。

   同样，ACF(0) 和 ACF(4) 的范数重合。

   此外，此后我们只将ACF理解为在0到k/2区间上的函数部分，因为函数的其余部分与第一部分对称。

3. 如果轮廓具有旋转对称性，其 ACF 也会有相似的对称性。例如，我们展示一些轮廓的 ACF 图形。

   在图片中，ACF 的范数用深蓝色表示（ACF 仅在 0 到 k/2 的区间表示）。

   正如我们所看到的，除最后一个轮廓外，所有轮廓都具有旋转对称性，这导致了 ACF 的对称性。最后一个轮廓没有这种对称性，其 ACF 图形也不对称。

4. 在某种意义上，可以将轮廓 ACF 视为轮廓形状的特征。因此，接近圆形的形状具有均匀的 ACF 范数值（参见圆形的图片）。在一个方向上强烈拉长的形状在 ACF 的中心部分有一个凹陷（参见矩形的图片）。在旋转时经过的形状在适当位置具有 ACF 的最大值（参见方形 ACF）。
5. 归一化后的ACF不依赖于轮廓的比例、位置、旋转和起始点选择。这源于第1点和NSP的性质。

   显示此事实的视频

至此，我们结束了CA的理论部分。在本部分中，我只介绍了主要概念和理论计算，我将在第二部分立即将其应用于模式识别。

第二部分：轮廓分析的实际应用

识别的通用算法

因此，我们将解决图像上的模式识别任务。

识别操作的一般顺序如下：

1. 图像的预处理——平滑、噪声过滤、对比度提升
2. 图像二值化和对象轮廓选择
3. 根据周长、面积、波峰因子、分形度等对轮廓进行初步过滤
4. 强制轮廓统一长度，平滑
5. 搜索所有发现的轮廓，寻找与给定轮廓最相似的模板

我们不会考虑第1点和第3点，它们是特定于应用领域的，与CA的关系不大。

接下来我们考虑算法主体——轮廓与模板的搜索和比较。然后——我们稍作停留，讨论轮廓的二值化、强制统一长度和平滑。

CA中算法性能评估

我们立即对基于CA的算法的高速性能进行评估。

假设图像已二值化并在其上选择了轮廓。

由于我们接下来只处理轮廓点，因此我们估计图像上它们的总数量。

为此，我们取一个大小为 n*n 像素的图像。然后以步长 s 繁殖其均匀网格。所有网格线的总长度为

结果表明，从平面二维图像到轮廓的过渡并没有降低任务的维度。我们仍然在 O(n²) 复杂度下工作。

但是，这里可以做一些备注

1. 所给出的估计是极端的。在真实图像中，并非所有轮廓都具有最小尺寸，它们也没有覆盖图像的所有区域。因此，轮廓的数量及其总周长可能远小于 2n²/s。理想情况下——如果图像包含一个对象，没有噪声，CA 将只处理一个轮廓，其像素数量不是平方，而是 n 的线性关联。在将图像作为二维像素数组进行操作的情况下（例如，应用 Haar 级联滤波器）——我们总是处理图像的所有像素，而不管图像上有多少对象。
2. 由于以轮廓形式的图像已经具有自然分割——被分割成轮廓，因此可以根据简单的指示对图像的各个部分进行过滤。其中包括——轮廓面积、周长、周长平方与面积之比。因此，存在一个足够简单有效的图像部分初步过滤机制。
3. 二维方法的基本算法，通常对尺度（SURF、SIFT）或旋转（Haar）不具有不变性。因此，实际上，它们在三维空间中工作，由于需要筛选尺度或旋转角度，因此又出现了一个维度。由于CA方法对尺度和旋转是不变的，因此不存在此类问题（排除——对起始点的不变性，但下面我们考虑了有效的方法来解决这种复杂性）。
4. CA 允许以渐进模式处理图像。这意味着我们可以根据任何指示（例如，按面积或边界梯度，或亮度等）对轮廓进行排序。然后处理第一个轮廓，并生成结果。剩余的轮廓在后台模式下处理。这意味着第一个结果（在许多面向应用的任务中这是必要的）可以在 O(n) 的时间内获得，这对于模式识别算法来说是一个极好的估计。
5. 由于轮廓彼此独立，识别算法很容易并行化。此外，算法非常简单，可以在图形处理器上执行。

以上所有推测仅涉及轮廓的处理。当然，获取轮廓的阶段不会消失，它至少需要 O(n²)。然而，在实践中，这个阶段占总处理时间的比例不超过 10-20%。

这些因素的集合大大降低了计算复杂度的常数，随着计算机的现代发展，CA 完全可以作为实时算法使用。

让我们解释 O(n²) 复杂度的原因。轮廓实际上是一个一维对象。它是一个复数值向量。然而，轮廓的数量与图像大小的平方成比例增长。因此也存在 O(n²) 的复杂度。由此可以得出结论，提高性能最有效的方法是通过初步过滤减少轮廓的数量。

现在我们分别估计已获取轮廓的处理复杂度。

在上一部分中，我们清楚地知道，为了比较轮廓，需要找出ICF的最大值（公式7、8）。我们估计评估的复杂性。标量积需要O(k)次运算，其中k是轮廓的长度。而ICF需要进行k次标量积的评估。这意味着ICF需要O(k²)数量级的评估。此外，考虑到比较不是与一个模板，而是与一组模板进行的，因此轮廓模板搜索的总时间可以估计为

其中 k - 轮廓的长度，t - 模板轮廓的数量。

这并不是一个很好的估计。在下一章中，我们将努力解决这个问题，我们将能够大幅降低此估计的常数。

总的来说，图像所有轮廓的识别复杂度为

其中 n - 图像的线性尺寸，k - 轮廓的长度，t - 模板的数量。

第一个轮廓的识别复杂度（渐进模式下）

轮廓描述符

如前一章所示，ICF 的评估复杂度为 O(k²)。尽管 k 是一个常数（我们稍后将考虑将轮廓强制为统一长度的过程），但 ICF 的评估仍然是一个劳动密集型过程。当 k=30 时，评估 ICF 需要 900 次复数乘法运算。如果存在 t=1000 个模板，则为轮廓搜索模板需要大约一百万次复数乘法。

为了快速搜索模板，需要引入一个描述轮廓形状的特定描述符。因此，彼此接近的轮廓应该具有接近的描述符。这将使我们免去对每个模板计算轮廓 ICF 的过程。只需要比较描述符，如果它们接近——只有在这种情况下才足够——计算 ICF。描述符的比较应该很快。理想情况下，一个数字应该是一个描述符。

不幸的是，在文献中我没有发现适合描述轮廓形状的明确描述符。然而，这样的描述符是存在的。

在第一部分，我们明确地考虑了自相关函数的性质。在同一部分，我们指出 ACF 对平移、旋转、缩放和起始点选择是不变的。此外，ACF 是一个轮廓的函数，而不是像 ICF 那样是两个轮廓的函数。

基于此，ACF 可以作为轮廓形状的描述符。接近的轮廓将始终具有接近的 ACF 值。

注意：ACF 是轮廓的形状描述符。

比较两个ACF的复杂度是O(k)，这已经比ICF的O(k²)好得多。此外，正如我们所记得的，ACF由于对称性，只在0到k/2的区间内定义，这又将评估时间减少了一半。

如果模板库存储了它们的ACF，那么通过比较ACF来搜索轮廓的模板，其复杂度为O(kt)。这已经是一个很好的估计。但我们还需要进一步细化。

为了减少比较 ACF 的时间，我采用了 ACF 的小波卷积。我将省略对这个过程的描述，可以在源代码中查看。

我们注意到以下几点

1. 一般来说，比较ACF并不能使我们免除评估ICF的必要性。只有ICF才能给出轮廓接近程度的精确估计。ACF一般来说对于不同的轮廓可能会重合。但是，通过ACF对模板进行初步选择，可以大大缩小ICF比较的候选数量。
2. 在某些情况下，比较 ACF 足以识别轮廓。如果图像上正在搜索具有简单几何形状的标记，并且识别失败的概率不重要，则可以省略比较 ICF 的过程，仅限于比较 ACF 的卷积。这种算法提供了最大的系统性能。

轮廓的均衡

如第一部分所述，CA 方法假定轮廓的长度相同。在实际图像中，轮廓的长度是任意的。

因此，为了搜索和比较轮廓，所有轮廓都应该被标准化为统一的长度。这个过程称为均衡。

首先，我们固定将在识别系统中使用VC的长度。我们将其指定为k。

然后，对于每个初始轮廓 A，我们创建一个长度为 k 的向量轮廓 N。接下来可能有两种情况——初始轮廓的 EV 数量大于 k，或者小于 k。

如果初始轮廓大于所需，则会遍历其所有 EV，我们将 N 的元素视为所有 EV 的总和，如下所示 (C#)

Complex[] newPoint = new Complex[newCount];

for (int i = 0; i < Count; i++)
    newPoint[i * newCount / Count] += this[i];

图片显示了均衡的含义。

 

 

这种算法足够粗糙，特别是对于长度稍大于 k 的情况，但它完全可以付诸实践。如果初始轮廓小于 k，我们进行插值，并进行近似计算。

Complex[] newPoint = new Complex[newCount];

for (int i = 0; i < newCount; i++)
{
    double index = 1d * i * Count / newCount;
    int j = (int)index;
    double k = index - j;
    newPoint[i] = this[j] * (1 - k) + this[j + 1] * k;
}

有一个问题需要选择 k 值，哪个值是最佳的？这个问题的答案完全取决于应用领域的特殊性。一方面，大长度 k 意味着巨大的评估开销。另一方面，小值 k 携带的信息较少，识别精度会降低，噪声识别会增加。

识别系统主要参数图，取决于所选VC的长度

此图表是根据 ICDAR 测试 ICDAR 的拉丁字母识别系统构建的。

正如我们所看到的，当轮廓长度值较大（80 及以上）时，系统参数趋于稳定且变化很小（除了处理时间，这自然会增加）。

在k值较小（小于30）时，噪声识别的数量（将噪声或其他非字符图像元素识别为字母）会减少，成功识别的数量会下降，而错误识别（失败识别）的数量会增加。

因此，对于给定的识别系统，k=30 是最佳值。

请注意，轮廓长度增加到一定水平（25 及以上）后，并不能改善识别质量。这是因为在所描述的方法中，均衡是与轮廓平滑同时进行的。当长度值较大时，平滑变得越来越精细，轮廓变得过于详细，因此与模板轮廓的差异更大（在所进行的测试中，学习样本的数字与测试图像没有完全匹配）。

CA的局限性

CA有两组对识别结果产生负面影响的因素。

第一组因素与图像上轮廓的选择问题有关。轮廓是严格确定的离散结构。然而，在环境背景中微弱表达的物体有大量的真实图像。物体可能没有清晰的边界，它可能在亮度上和颜色上与背景相同，它可能被噪声干扰等等。所有这些因素导致轮廓可能根本无法选择，或者选择不正确，并且不符合物体的边界。

右图显示了二值化图像。数字图像和环境背景之间的小“桥梁”使得数字轮廓无法通过 CA 方法识别。

这种案例对CA来说非常严重。毕竟，CA只有在对象轮廓在所有点上都明确正确定义时才有意义。

第二组使 CA 复杂化的因素与轮廓分析的原理有关。CA 方法假定轮廓完整地描述了整个对象，并且不容许与其他对象的任何交叉或对象的不完全可见性。

右图为二值化图像。可以看出，横向的光斑使得字母对于CA来说难以辨认。

因此，CA 对杂质的稳定性较弱，不容许交叉或部分可见的对象。

方法测试结果

尽管存在局限性，CA 方法因其简洁性和高速性能而具有吸引力。在对比度背景下存在清晰表达的对象且无干扰的情况下，CA 能够很好地完成识别任务。

对ICDAR测试的CA方法测试结果显示，识别字符的成功率为48%。考虑到这个测试非常困难，并且包含大量难以辨认的字母图像，这是一个相当不错的结果。因此，CA在30秒内处理了249张不同大小（从400x400到1280x960）的图像。

除了识别静止图像外，CA 的高速性能还允许以实时模式处理视频。此视频展示了 CA 的可能性。

第三部分：ContourAnalysis 库

该库包含两个项目。第一个项目 ContourAnalysis - 实现了轮廓分析的基本功能 - 轮廓创建、轮廓标量积、均衡化、ICF 和 ACF 评估、模板比较和搜索。

Contour 类 - 创建并存储轮廓。它包含轮廓的基本操作 - 标量积、缩放、均衡化、归一化、频谱评估、ACF 和 ICF 评估。

Template 类用于创建模板库。此类别存储轮廓、其 ACF、ACF 描述符、初始轮廓的线性参数（面积）、轮廓范数。此外，模板还具有用作识别值的 name。

TemplateFinder 类实现了给定轮廓的快速模板搜索。此类的操作结果是 FoundTemplateDesc，其中包含初始轮廓和为给定轮廓发现的模板。此外，FoundTemplateDesc 还包含相似度、旋转角度和轮廓相对于模板的比例。

第二个项目 - ContourAnalysisProcessing - 包含图像预处理、轮廓选择、过滤和识别的方法。此外，它还包含用于自动生成印刷符号识别模板的工具。

项目 ContourAnalysisProcessing 使用 OpenCV 库（EmguCV .NET 包装器）进行图像操作。

ImageProcessor 类用于图像处理。它也存储模板库。

方法 ImageProcessor.ProcessImage() 接收图像作为输入。操作结果是发现的轮廓列表（ImageProcessor.samples）和识别出的轮廓列表（ImageProcessor.foundTemplates）。

ImageProcessor 类还包含轮廓搜索设置。

ImageProcessor 的工作方式如下：

1. 首先，图像将被转换为灰度图像。

   

2. 然后通过 AdaptiveThreshold 进行二值化。

   

3. 提取轮廓

   

4. 根据线性参数（长度、面积等）对轮廓进行过滤

   

5. 轮廓被均衡化，计算 ACF 和 ACF 描述符

   

6. 然后找到最合适的模板

   

静态类 TemplateGenerator 用于自动生成特定字体的数字模板。

除了两个库项目之外，还有一个演示示例，展示了库与网络摄像头的操作。该演示包含创建和编辑模板、识别调整的工具，并允许从网络摄像头进行轮廓识别，还可以创建增强现实。

如何“训练”CA

历史

• 2011年5月14日 - 首次发布
• 2011年5月18日 - 改进了噪声过滤，提高了性能，修复了一些错误