2014年第11届计算机图形学，成像与可视化国际会议
一种用于指尖检测的混合凸壳算法
Bo Shen Woun1, Guat Yew Tan2, Miin Huey Ang3，马来西亚理科大学数学科学学院，马来西亚槟城
wounboshen@hotmail.com1, gytan@cs.usm.my2, mathamh@cs.usm.my3
Ya Ping Wong，多媒体大学计算机与信息学院，Cyberjaya，马来西亚
摘要：在实际凸壳算法应用于图像之前，从二进制图像中提取凸壳顶点以检测指尖总是涉及多步预处理算法，如边缘检测算法。预处理步骤通常占用大量计算资源。在本文中，我们通过引入混合凸包算法来努力减少计算资源，该算法能够直接从二进制图像提取凸包顶点，而无需经过边缘检测过程。Bresenham算法嵌入在Jarvis March中，以取代边缘检测过程中所需的大部分工作。在这方面，我们的预处理步骤很简单，只检测四个全局极值点的提取。新算法产生O（N2）的时间复杂度。
关键词：Bresenham算法; 凸壳; Jarvis March
一 导言
一组有限平面点S的凸壳被定义为包围S [6]的最小凸多边形P。它是一种常见的结构，广泛应用于许多应用[10]。已经开发了各种凸包算法，并且Bass和Shubert在1967年提出了第一种算法[11]。1972年晚些时候，Graham率先引入了O（n log n）凸包算法，被认为是精度和效率的重要算法[5,6]。Graham对点使用径向排序，并反复检查沿多边形周长的每三个后续点的凸度。同年，Sklansky通过8连接凹面树技术[1]介绍了O（n）凸壳算法。该算法虽然简单，却在一些自相交的多边形上失败[2]。 1983年，Sklansky引入了一个修改版本[3]，增加了一个额外的过程，在凹面树技术之前在水平和垂直方向上单调创建多边形，就像在他之前的算法中一样。然而，这种改进的算法并不总是有效，有时甚至会产生非简单的多边形[4]。尽管有这些弱点，OpenCV是一种广泛使用的图像处理工具，由于其简单性，使用Sklansky算法[7]。 1973年，Jarvis引入了一个带有O（nh）的简单礼品包装算法（Jarvis March），其中h是凸包边缘的数量。该算法测量围绕脚踝极点旋转的线的角度，并且将形成最小角度的点作为另一个极点[16]。1985年，引入了具有O（n log n）复杂度的Quickhull算法。它基于快速排序方法，通过按照左右两个极点划分点来处理平面点集，并在递归上严格丢弃上下船体内的点[8]。1977年，Preparata和Hong引入了分而治之的凸包，复杂度为O（n log n）[9]。该算法使用分而治之技术将x排序的点重复分成两个几乎相等的半部，然后找到每个边的下切线，将两边合并在一起形成一个多边形。
在二进制图像处理中，例如指尖检测，在对提取的点执行凸包算法之前，总是需要在关键/特征点提取方面进行预处理。在[12]中，预处理顺时针扫描2D图像以检查极值点以形成多边形，然后在提取的多边形上执行所提出的凸包算法以检查多边形的凸性并进行必要的调整。在[13]中，在使用视点不变傅里叶描述符计算三维平面物体识别的不变量集之前，提取物体的特征点以生成凸包。在[14]中，预处理扫描图像8个极值点，然后将极值点内的区域划分为5个区域，在每个区域上进行进一步扫描以找到凸包的边界像素。在其他项目中，典型的方法是在凸包算法之前对图像应用边缘检测。通常，边缘检测涉及过滤技术，如拉普拉斯或梯度，这需要大量的处理工作[17]。
我们的项目旨在绕过边缘检测过程并直接在二值图像上应用混合凸包算法来提取指尖顶点。 在本文中，我们提出了一种混合算法，通过在Jarvis March中嵌入Bresenham算法直接在具有最少预处理的图像上形成凸包（图1）。 在应用分区方法后，我们使用的二进制图像被认为没有噪声[15]。
本文的其余部分安排如下。 第2节描述了预处理和凸壳形成的方法。 时间复杂度分析在第3节中进行，结论在第4节中进行。
图1.凸包算法的理论框架
二 方法
我们的算法采用[15]中产生的二值图像，其中已经应用了去噪程序。 我们的预处理仅涉及基于四个全局极值和检测到的手图像的全局最大点来定义边界框。 为了找到凸包，全局最大点用作第一个凸包顶点。 然后从边界框的第一个顶点到右边缘绘制Bresenham线，目的是寻找与手的交点。 通过使用Jarvis March，交点是找到的第二个凸包顶点，并且重复该过程，直到处理完所有四个边界框边。 以下部分描述了涉及的两个主要步骤：预处理和凸壳检测。
说明
存在的方法
我们的方法
凸壳算法
边缘检测
二值图像
新凸壳算法(Bresenham 算法 Jarvis March)
A 预处理步骤：定义边界框
在此步骤中，扫描图像的白色像素一次，以找到四个全局极值mx，Mx，my，My和全局最大值（handx，My），mxlt;=handxlt;=Mx
物体的凸壳
令
mxlt;=xlt;=Mx, mylt;=ylt;=My
其中mx和Mx分别是全局最小和最大水平值，my和My分别是全局最小和最大垂直值，H（x，y）是坐标（x，y）处像素的亮度。
因此，H是由限制在mx，Mx，my和My内的矩形区域定义的图像的边界框; 和H（handx，My）= 255（图2）。
B 前置词
前置词1：设H是含有一组点S的边界框。S内的点p位于边界框边缘的是S的凸壳顶点。
证明： 有限点S的凸包由包围S [6]的最小凸多边形定义。 边界框H受到极值S的限制，由mx，Mx，my，My给出。因此对于S内的点p（ px属于{mx, Mx} 或者 py属于{my, My} ），p是S的凸壳的顶点。
前置词2：选择凸包顶点，将其命名为p0，并绘制直线L，将p0连接到r处边界框的一个边。 确保L是凸多边形的外线，即L不与凸多边形相交。 通过使用p0作为枢轴点，顺时针方向移动L，线的另一端r始终接触边界框边缘。 L遇到的第一个交叉点是凸壳顶点（图3）。
图2：极值，mx，Mx，my，My; 全局最大点，（handx，My）; 和边界框
证明：将橡皮筋的一端固定在顶点p0上，将橡皮筋的另一端r拉到边界框的一边，并确保橡皮筋保持在外部。这可以从介词1中选择凸壳的最右上顶点为p0，当mxlt;=p0xlt;=Mx。令（rx,ry）=（Mx,My）, 橡皮筋会形成一条连接p0和r的直线L，令p0为最右侧的凸包顶点，令l是L上一个点，对于任意的L上的一点l，l不与p0点重合，p0xlt;lxlt;=rx和ly=My，l不是S上的点。因此L是凸多边形的外边线。
当p0被固定时，r沿着Mx向下移动，即rx停留在Mx上，并且ry减小，L顺时针旋转p0直到它与一个点p1（S内）相交。换句话说，换句话说，L相对于其原始位置旋转角度theta;，其中theta;是在遇到第一个点p1（S内）之前的最小角度。很明显，p1是凸壳的顶点，如Jarvis March算法[16]中所述。
图3：p0是凸包顶点并用作枢轴点，r是Mx上的一个点，其中L连接p0和r。 p1是L顺时针旋转时遇到的第一个交点，p1是凸壳顶点。
从介词1开始，由于p0 =（handx，My）是全局最大点，它也是凸包的顶点。 要搜索后续顶点，请参阅以下步骤。
1）以p0为起始枢轴点，r =（Mx，My）作为L的终点，
2）检查从p0到r的点的亮度，
3）如果点p pL，那么H （p）= 255，该点将是凸包（Preposition 2）的顶点，亮度检查停止。
4）p变为新的p0并且（rx，ry-1）变为r，L将新的p0连接到r。
5）使用Bresenham算法计算从新p0到r的点作为L不等于0的斜率。
6）重复步骤2直到ry = my。
7）当ry = my时，r沿着我的线向左移动，即（rx-1，my）成为新r，并重复步骤2。
8）该过程继续，直到检查了H的所有四个边缘。
图4显示了凸壳形成中上述步骤的算法框架。 在图像的点检测中，将发现许多凸壳顶点。 正如我们期待手部图像一样，顶点集中度高的区域是指尖区域。 因此，可以使用顶点组内的任何点。 为简单起见，我们使用组的最后一点作为指尖点。
三、时间复杂度
在预处理步骤中，我们正在寻找NxN图像的全局极值。 它扫描整个图像一次以找到四个极值，因此具有O（N2）的复杂度。 扫描活动包括检查每个像素的亮度值。
对于凸包形成，仅检查一些黑色像素，即不检查手指之间的黑色像素。 因此，仅检查凸包外部但在边界框内的黑色像素。 我们已经捕获了一些手部图像作为示例，如下所示。
表1 时间复杂度
|
数据 |
凸壳外部的黑色像素数（B） |
总边界框像素（A） |
边界框中凸包外的黑色像素百分比（A中的％B） |
|
5 |
23834 |
69325 |
34.38 |
|
6 |
26413 |
74418 |
35.49 |
|
7 |
25072 |
74181 |
33.80 |
|
8 |
25337 |
69090 |
36.67 |
|
9 |
58901 |
125476 |
46.94 |
|
10 |
12582 |
28014 |
44.91 |
|
11 |
11096 |
23153 |
47.92 |
|
12 |
8452 |
21608 |
39.12 |
从表1可以看出，所有八幅图像中边界框中凸包外的总黑色像素的最大百分比为46.58％。 我们得出一个合理的结论，对于任何伸出的手形图像，边界框中凸包外的总黑色像素总是小于50％。 因此，在最坏的情况下，要处理的黑色像素的数量是1/2*N2。 时间复杂度为O（1/2*N2）。 但是，我们必须考虑到Bresenham中的检查算法只涉及整数和#39; #39;运算符，因此处理时间会快得多。
图5：示例图像
图6：示例图像
图7：示例图像
图8：示例图像
图9：示例图像
图10：示例图像
图11：示例图像
图12：示例图像
四、结论
利用嵌入Jarvis March的Bresenham算法开发了一种混合凸包算法。 期望新算法减少分配用于边缘检测的资源，并且使用最少的处理将凸包算法直接应用于二进制图像中的像素。 虽然我们的算法的时间复杂度是预处理器的O（N2）和凸壳检测的O（1/2*N2），但我们的算法只使用整数和#39; #39;运算符，因此就计算机处理而言，预期是有效的。
致谢
这项工作得到RU-PRGS（1001 / PMATHS / 836026）和短期资助马来西亚大学（304 / PMATHS / 6312096）的支持。
参考文献
[1] J. Sklansky, 'Measuring Concavity on a Rectangular Moasic,' Proceedings of the IEEE transactions On Computer, Vol. c-21, No. 12, pp.1355, 1972.
[2] A. Bykat, 'Convex hull of a finite set of points in two dimensions,' Info. Proe. Lett.,pp. 296-298,1972
[3] J. Sklansky, 'Finding the convex hull of a sim
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
