文章目录
  1. 1. 摘要
  2. 2. 背景介绍
  3. 3. 算法实现
    1. 3.1. 低差异序列(Low Discrepancy sequence)简介
    2. 3.2. 旋转不变性采样点
    3. 3.3. Coarse to fine search旋转模板匹配
    4. 3.4. End

最近公司组织学习小组进行专利汇报讨论,为了避免其中一些好的想法在短期内没有实现,导致过后容易遗忘。因此开设“专利学习”系列对其中好的专利记录一二。

这是一篇NI的专利:
专利名称:Pattern matching system and method with improved template image sampling using low discrepancy sequences.
专利号:US6229921B1。

摘要

本篇专利提出了一种模板定位的方法。该方法首先使用低差异序列(Low Discrepancy sequence),也被称为拟随机序列(quasi-random sequence)来对图像进行采样,采样得到的一系列像素点用来精确描述模板。然后使用采样点来进行模板匹配过程。该方法同时对采样点进行了局部稳定性分析(a local stability analysis),以期得到更精确的结果。局部稳定性分析将采样点根据不同领域大小的稳定性分类,然后从高稳定性到低稳定性采样点进行模板匹配。同时该专利还选取根据旋转不变性采样点来进行旋转匹配,比如圆环采样。这种旋转不变性采样的模板匹配也可以使用局部稳定性进行coarse to fine搜索。

背景介绍

模板匹配的过程是为了确定在目标图像中模板的位姿,包括匹配质量,匹配位置、角度及缩放因子。一般的情况下将模板的像素与所有可能的位置进行比较,通常会使用一种归一化相关性系数的技术来计算是否匹配。这种方法在我另一篇文章:基于NCC的模板匹配介绍及实现技术细节中有详细的描述,同时注意到在那片文章中使用了图像金字塔来减少匹配的时间消耗。由于归一化相关性系数的计算极为耗时,即使有了一些快速计算的优化方法提出,但是对于在整个图像中进行搜索的话,计算量就非常大,无法将其应用在实际生产中。那么在这篇专利中提出的方法是对模板进行采样,以此来大大减少搜索的时间消耗。

算法实现

低差异序列(Low Discrepancy sequence)简介

在具体介绍算法之前,需要对拟随机序列做一下简单的介绍。先来谈下随机数的概念,真正的随机数必须使用专门的设备,比如热噪讯号、量子力学的效应、放射性元素的衰退辐射,或使用无法预测的现象,譬如用户按键盘的位置与速度、用户运动鼠标的路径坐标等来产生。在计算机中都是通过随机函数来生产随机序列,生成的随机序列称为伪随机数(Pseudo-random number),常用的算法有梅森旋转算法。在统计学、蒙特·卡罗方法上使用的伪随机数也必须挑选周期极长、随机性够高的随机函数,以确保计算结果有足够的随机性。而拟蒙特卡洛方法就是使用拟随机序列来代替伪随机序列进行计算。常用的低差异序列有Halton, Sobol, Faure和Niederreiter序列等。下图是伪随机序列和低差异序列的直观比较:




由伪随机数法(左)和低差异列(右,Sobol)法生成的256点序列(红点为第1至10点,蓝点为第11至100点,绿点为第101至256点) 直观上,低差异列的分布更为均匀


从直观上我们可以看到低差异序列能产生更为均匀的序列,同时使用更少的点就能覆盖整个区域。另外,低差异序列的产生并不复杂,感兴趣的可以自行google。回到专利中,专利就是利用了低差异序列的良好性质,可以使用较少的点作为采样点来有效覆盖模板区域,使用采样点来代替整个图像。另外,低差异序列的生成工作也可以放在前期进行,这样可以减少匹配时额外的时间消耗。

### 局部稳定性分析(Local stability analysis)
假设现在我们已经通过Halton或者Sobol方法产生了一系列样本点,我们还不能直接使用这些样本点进行模板匹配。这里还有一个重要的工作就是对这些样本点进行局部稳定性分析,进行这个步骤的目的是为了将这些像素点根据稳定性进行分类。具体是这样操作的,对每个样本点计算它和模板图像中相邻像素的相关性。相关性越高意味着稳定性越高,也就是说该样本点周围的像素值和它相似。同时,计算时可以选择不同的领域大小,比如3,5,7,9。这样就可以根据领域的大小来对不同稳定性的样本进行分类。在分类之前,可能还需要过滤掉一些稳定程度小于预设领域大小的样本点。
最后我们会得到不同领域大小稳定性的样本点。需要注意的是我们需要把领域的大小记录下来,因为在匹配的过程中需要用到这些信息。

### Coarse-to-fine模板匹配
讲完上面两个比较重要的概念后,对于匹配过程,这里就只是大概描述一下。
得到不同领域大小稳定性的采样点后,首先对稳定性最大的采样点在整幅图像中进行模板匹配。在整幅图像中匹配时,不需要一个像素一个像素的进行,而是使用计算好的稳定性领域大小,比如以9 pixel的大小进行遍历。这就是局部稳定性分析真正的作用。
当我们得到一些潜在的匹配点后,为了得到准确的匹配位置,使用稳定性次高的采样点,在匹配点一定范围内使用当前的稳定性领域大小进行进一步匹配。以此类推,直到我们遍历完所有的采样点,然后对于最后的潜在匹配点使用整个模板图像进行匹配,来得到我们最终的结果。这样就完成了整个匹配过程。

下面这张流程图是对上面描述过程的总结:




流程图

写到这里我觉得其实已经把这篇专利中最精华的部分讲了,但是还有一个问题没有解决,那就是对于旋转以及缩放的情况考虑进来。要知道,算法实现起来真正困难的地方一个是精度,另外一个就是加上旋转以及缩放的情况了。

旋转不变性采样点

专利中选用不互相重叠的圆,可以是同心圆或者是非同心圆来对模板图像进行采样。那么在匹配时如何确定旋转角度呢?通过将圆环序列的采样点逐个偏移,每次偏移都计算一次匹配结果,直到偏移又回到起始点。通过选取这个过程中最佳的匹配位置,就可以确定当前位置的旋转角度(这里还要注意一个问题,就是偏移一个像素旋转的角度是多少?这个直接影响到匹配的角度精度)。

另外,这个过程也可以推广到缩放的情况,通过对圆环序列进行缩放(根据当前圆环的中心),对每次缩放的样本点进行匹配。更具体的做法是,在所有圆环中选取固定半径的圆环来进行缩放匹配。

Coarse to fine search旋转模板匹配

3.4中讨论的只是单个位置下考虑旋转的情况,现在我们要在整幅图像中考虑旋转,平移这两个因子。

同之前的处理类似,我们需要计算每个圆环的每个采样点的局部稳定性。这里我推测应该是将采样点以圆环为单位进行稳定性分类,做法同上。然后对稳定性最高的哪些圆环进行粗匹配,粗匹配包含的意思包括位置的粗匹配以及角度的粗匹配。可以想象,稳定性比较高的圆环极有可能是那些半径比较小的圆环。半径比较小,角度的精度也会相应较小(当然,我这种以圆环为单位进行样本分类的推测有待商榷)。粗匹配后,之后的过程与3.3中的方法类似,不再赘(zhui,–!)述。

End

算法讲起来容易,实现起来还是会碰到许多问题的,就像上面说的精度问题,旋转和缩放同时考虑的情形。
But i want to say:” Although talking is cheap, but sometimes useful”.

文章目录
  1. 1. 摘要
  2. 2. 背景介绍
  3. 3. 算法实现
    1. 3.1. 低差异序列(Low Discrepancy sequence)简介
    2. 3.2. 旋转不变性采样点
    3. 3.3. Coarse to fine search旋转模板匹配
    4. 3.4. End