基于离散点的图形识别(手势图形识别)

最近研究了一下离散点图形的识别(识别圈,直线和点),用来在Android/iOS上实现一个手势加密锁功能,类似的功能其实早在Windows 8上面就已经有了(这里贴一个传送门)。

下面大致介绍下算法的实现

首先,假设有一系列的离散点P1(x1, y1), P2(x2,y2), P3(x3,y3) … Pn(xn,yn)

第一步先从点的数量进行初步筛选,要拟合直线至少需要2个点,拟合圆至少需要3个点

1. 只有一个点P1

那就是点了。。。

2. 有两个点

先作直线P1P2,求出直线长度,这里使用了一个阈值 TH-L ,直线长度小于这个阈值则不认为是直线,而认为是点,取这两点的中间点坐标作为点坐标

3. 大于等于3个点,这种情况详细讨论一下:

使用到了直线和圆的拟合算法,参考了网上的文章:
利用最小二乘法进行线性拟合(作者lichengyu)
最小二乘法拟合圆(作者Ivan)

还有一个多边形内部判断算法,稍后会用到:
判断点是否在多边形内部(作者阿凡卢)

使用拟合算法得出圆C和直线L,首先对圆进行判断,定义两个阈值,圆最小半径 TH-C1 ,最大半径 TH-C2 ,如果圆C的半径不在 TH-C1TH-C2 之间,则作为直线判断,求出直线L长度,同上面第2步来作后续判断;如果圆C的半径在规定范围之内,进入下一步判断。

最小二乘法拟合圆 这篇里介绍的算法得出的圆,会有两种情况:

显然第一种情况应该排除,还是作为直线处理,走上面第2步。

这两种的区别就是圆心是否被离散点所形成的多边形包围(图中橙色覆盖部分),这里就用到了上面的多边形内部判断算法。

至此,圆,直线和点就判断出来了。