一个用于破碎轮廓不变仿射匹配的图形处理单元加速遗传算法外文翻译资料

英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

一个用于破碎轮廓不变仿射匹配的图形处理单元加速遗传算法

Chi-Sing Leung，Ping-Man Lam，P. W. M. Tsang，Wuchao Situ

摘要： 过去的研究作品已经证明的零碎轮廓匹配可以依靠有效结合的遗传算法和移徙原则完成。尽管取得了成功，但是评价适应度函数时的计算量很大。为了克服这个问题，本文开发和给出了针对图形处理单元 (GPU) 的适应度评价的一种新公式。实验结果表明，提出的解决方案能够减少匹配的时间，同时保持高成功率。

关键词： 不变仿射匹配；破碎轮廓；遗传算法；移徙原则；碎片渲染器；图形处理单元；

1 介绍

近年计算机视觉技术被应用在真实世界的问题很多。其中的一些是经典问题 (如 [1，2]) 而另外一些都是有针对性的更实际和当代问题 [3-6]。尽管取得了成功，但是很难确定从不同的角度捕捉到的形状。有一个克服这一局限性的成功的办法，俗称'基于模型、的匹配'，通过将它们与已知的参考模型集合标识比较来确认未知的场景形状。如果从不同的角度捕捉到现场和引用对象，由后者引起的几何变换被认为是搜索过程，然后消除。尽管该方法是有效的（这一般近似为仿射变换），但是具有盲搜索的几何变换直接扣除需要大量的计算。解决上述问题的可行办法一直建议 [7-14] 用简单的遗传算法 (SGA) [15]。但是这些方法要求完好 （即密切和持续）的 轮廓。这项限制在[16]已缓解，并且随着与移徙原则 (MP) [17]的结合而增强。而后者在轮廓匹配的成功率几乎达到100%。然而，这种有利的结果需要约 600 染色体，从而导致长时间计的算。在本文中我们提出，通过改造 [17] 中的匹配算法使它可以集成到图形处理单元 (GPU)。GPU 是最初设计用于呈现计算机图形学一个流处理器。它允许在流的记录上并行执行函数 （内核）。在流中的每个记录是必须由同一个内核处理的一组数据。

2 背景

在本节中我们将介绍 [17] 的轮廓匹配方案大纲。我们描述分为两个部分 ︰ 一对物体轮廓之间的相似性度量，并用 SGA 完成匹配的过程。

2.1 测量的两个物体轮廓之间的相似性

首先，定义下列术语。一，参考图像O_R和未知图像O_S每个由一组下列的边缘点给定︰

(1)

(2)

其中m和n分别是O_R和O_S轮廓点的数目。边缘点位置由通过其上的两维图象平面直角坐标来表示。让 A(O_R) 和 Atilde;(O_S) 分别表示OR和OS的仿射和逆仿射变换。如果O_R和O_S相似，应该存在一种仿射变换和相应的逆变换使OR asymp; Atilde;(OS)且OS asymp; A(OR)。请注意，A 由六个参数 [a、b、c、d、e、f] 定义，并且Atilde;从A的逆得出。第二，采用加权的距离变换 (WDT) [18] 构建OR和 OS的距离映射，使：

下一步，即确定正反演的分数，使：

AS1 (AS2) 表示转化的参考（场景）轮廓和场景（参考）对象之间的距离。最后，整体匹配分数可以结合式5和6式给出，使：

匹配得分MS取值范围[0，1]，反映出参考和场景的轮廓之间的相似性。

2.2标准遗传算法在物体轮廓匹配中的应用

[17] 中搜索过程如表 1 所示。第一，随机生成N 条染色体的人口，每个染色体均匀地划分为六个表示仿射参数的基因。每个染色体的适应度由式 7推导得出。接下来，依据由父染色体的适应度得出的可能性，将父染色体选取入一个匹配池，并且一个L尺寸的子人口 PL (L lt; N) 通过对父母的交叉或突变产生。剩余的人口 PM 由M (M = N-L) 个随机生成的移徙染色体填充。重复此过程直到轮廓匹配的现况可以作出决定。

表 1形状匹配的遗传算法

步骤 操作

1. 创建初始的随机种群与 N 染色体; generated = 0；
2. 评价人口中所有染色体;的适度性；
3. FOR generation = 1: MAX_GENERATION;//L 个体的本地人口的形成；
4. 根据其适度性选择 L/2 对父母；
5. 对于每一对父母，执行突变或交叉；// 形成 M 个个体的移徙人口
6. 随机注入 M 移徙个体；
7. 评估所有染色体的适度性并记录最高的一个；
8. IF the MAX _FITNESS gt; THRESHOLD,
9. GOTO step 14.
10. END IF
11. 用更强的染色体替换最弱的染色体；
12. END FOR
13. 轮廓对来自于不同的对象。进程结束。
14. 轮廓对来自于同一个对象。进程结束。

3 匹配算法的GPU实现

基于[17]，为了识别匹配的轮廓的成功率达到100%，必需600的人口。非常费时。我们建议使用 GPU 的并行方式进行适应度评价。简而言之，式7 需要重建，以使其构成的算术运算可以分离和分发到在 GPU 中的碎片渲染器。我们方法的概述如图 1 所示。

图 1 GPU 加速适应度评价的概述

开始时设定的代表引用对象轮廓的边缘点OR和 OS 改组为一双单排纹理 t_OR 和 t_OS。接下来，两个轮廓的加权距离图像由式 3 和式 4 分别计算，然后转换成纹理 t_DR 和 t_DS。然后四个纹理预加载到图形硬件内存。表示人口中N条染色体的A 和Atilde;的参数每个分为两组。第一组，G1 和 G1~，包含参数 [a、 b、 e] 和 [a~、 b~、 e~] 如下：

第二组，G2 和 G2~，每个染色体包含参数 [c、 d、 f] 和 [c~、 d~、 f~]如下：

然后这两个群体重组为两个单排、 1 times; N 纹理由 t_A1 和 t_A2 （为前向变换），和 t_Atilde;1 和 t_Atilde;2 （为反变换） 表示。最初的纹理 t_OR、 t_OS、 t_DR 和 t_DS 上载到 GPU 内存一次。在每一子代，表在人口中的所有染色体的纹理 （t_A1，t_A2） 和 (t_Atilde;1，t_Atilde;2）的含量代，是动态地加载到内存的。正向和反向匹配分数由表 2 中列出的片段着色程序和相应的变量定义在表 3 中列出。我们应只形容为向前匹配分数，表 2 中的片段渲染器逆匹配得分是相同的除了取代 t_OR t_OS，t_DS，t_DR，由 t_Atilde;1，t_A1 和 t_A2 的 t_Atilde;2。变量的'pointlength'设置为相应的轮廓线的长度。函数 f3texRECT 执行纹理拿来检索单元格的变量 [a、 b、 e] 和 [c、 d、 f]，和组合，形成完整的仿射变换矩阵 m。随后，每个纹理 t_OR 中的轮廓点检索，并与后者转化。在距离地图 （作为 texturet_DS 在 GPU 中加载） 与变换的轮廓点对齐的像素是总结给匹配分数和存储在 rr。所有计算都与 Gpu 向量指令同时都进行。最后，将渲染纹理的内容传递给 CPU 并且为每个染色体计算匹配总分 MS。

表 2 碎片渲染器向前/逆得分

表 3 碎片渲染器中的变量的定义

affinemap[0] 纹理 t_A₁ 或 t_Atilde;₁

affinemap[1] 纹理t_A₂或t_Atilde;₂

pointmap 纹理t_O_R或t_O_S

distmap 纹理t_D_R或t_D_S

aa 保存在人口中的第y条染色体的仿射参数 [a，b，e] 的数组

bb 保存在人口中的第y条染色体的仿射参数 [c，d，f] 的数组

m 将 aa 和 bb 组合成一个 2 times; 3 数组的数组

pp 来保存第j个轮廓点的坐标 [x，y] 的数组

vv 保存第j个轮廓点的仿射变换坐标 [x，y] 的数组

pointlength 轮廓点的总数

rr 距离图像中与变换的轮廓点对齐的像素总和

4 实验结果

用六个物体的参考模型︰表 4中的长嘴钳（A）、 锤子（B），开口扳手 (C) 剪子（D），老虎钳(E)和可调扳手（F）来评价算法。

表 4 参考模型和场景的轮廓

[17] 中的方法被用于将每个模型轮廓与三个在真实的环境中捕获的它的变体 （表 4 列 2-4）进行匹配。每个批次的测试重复100次，来确保每个模型统计测量上的成功率。四个不同的人口规模采取调查及其对该方法的成功率的影响。在表 5 中列出了 SGA 的设置。在图 2 中列出了每个对象在不同的人口规模的成功率。如要所有对象的轮廓达到 100%成功率，600 人口规模是必需的。

图2在不同人口规模N的成功率

我们实验使用 英特尔 Core2Duo E6850 3.00ghz的 CPU 与 GPU (NVIDIA GeForce 8800GTX)。在600的人口规模下匹配一对对象，对是否使用 GPU的平均时间作比较的结果如图 3 和 4 所示。结果表明，与 CPU 相比，GPU 可以使速度提高 20-30 倍。

图 3人口规模为600的GPU和CPU计算时间 （以毫秒为单位）比较

图 4人口规模600的CPU与GPU轮廓线匹配的速度提高。

5 结论

SGA 和 MP 一体化在视角变化的对象轮廓匹配中是有效的。然而为了达到高成功率的适度人口规模是必需的。为了克服这个问题我们首先分析制定的匹配算法，并将过程耗时的仿射变换重组为纹理渲染。后者随后会转移到GPU以并行方式执行。我们的评估显示，匹配时间减少了20-30 倍。

参考文献

1. Bosco, G.L. (2001). A Genetic Algorithm for Image Segmentation. Proc. 11th Intrsquo;l. Conf. Img. Ana. Process., 262–266.

2. Roth, G., amp; Levine, M. D. (1994). Geometric primitive extraction using a genetic algorithm, IEEE Trans. PAMI, 16(9), 901–905.

3. Dunn, M., Billingsley, J., et al. (2003). Machine Vision Classification of Animals. Proc. 10th IEEE Intrsquo;l Conf. M2VIP, pp. 9–11.

4. Lee, C.L., amp; Chen, S.Y. (2003). Classification for Leaf Images. 16th IPPR Conf. CVGIP, pp. 355–362.

5. Lee, D.-J., Schoenberger, R. B., et al. (2004). Contour matching for a fish recognition and migration-monitoring system. Proceedings of SPIE, Two-and Three-Dimensional Vision Systems for Inspection, Control, and Metrology II, 5606, 37 –48.

6. Lee, S., Lee, M. C., et al. (2005). Effective invariant features for shape-based image retrieval. Journal of American Society of Information Science and Technology, 56(7), 729–740.

7. Toet, A., amp; Hajema, W. P. (1995). Genetic contour matching. Pattern Recognition Letters, 16, 849–856.

8. Wang, Y. K., amp; Fan, K. C. (1996). Applying genetic algorithms on patter

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[31453]，资料为PDF文档或Word文档，PDF文档可免费转换为Word