python实现汉字的拐点计算

文章目录

一、线段曲率计算原理

一般的曲率计算方法，如玄长比例法、三次B样条表达、线性多边形逼近和局部对称等方法。今天主要介绍 弯曲值算法（Bending value） 算法。其表达式为：

      b
     
     
      
       i
      
      
       k
      
     
    
    
     =
    
    
     m
    
    
     a
    
    
     x
    
    
     (
    
    
     ∣
    
    
     (
    
    
     
      x
     
     
      
       i
      
      
       −
      
      
       k
      
     
    
    
     −
    
    
     
      x
     
     
      i
     
    
    
     )
    
    
     +
    
    
     (
    
    
     
      x
     
     
      
       i
      
      
       +
      
      
       k
      
     
    
    
     −
    
    
     
      x
     
     
      i
     
    
    
     )
    
    
     )
    
    
     ∣
    
    
     ,
    
    
     ∣
    
    
     (
    
    
     
      y
     
     
      
       i
      
      
       −
      
      
       k
      
     
    
    
     −
    
    
     
      y
     
     
      i
     
    
    
     )
    
    
     +
    
    
     (
    
    
     
      y
     
     
      
       i
      
      
       +
      
      
       k
      
     
    
    
     −
    
    
     
      y
     
     
      i
     
    
    
     )
    
    
     ∣
    
    
     )
    
   
   
     b_{ik}=max(|(x_{i-k}-x_{i})+(x_{i+k}-x_{i}))|,|(y_{i-k}-y_{i})+(y_{i+k}-y_{i})|) 
   
  
 bik​=max(∣(xi−k​−xi​)+(xi+k​−xi​))∣,∣(yi−k​−yi​)+(yi+k​−yi​)∣)

计算Bending Value的示意图如下：

参考链接：

手写体汉字的书写质量评价

二、线段拐点提取流程

• 计算线段上每一点的Bending Value，记作 B v ( i ) Bv(i) Bv(i),这里需要初始化阈值delta=1.1和搜索范围k=1
• 当 B v ( i ) > d e l t a Bv(i)>delta Bv(i)>delta,且对于所有 i − k < = j < = i + k i-k<=j<=i+k i−k<=j<=i+k,均有 B v ( i ) > = B v ( j ) Bv(i)>=Bv(j) Bv(i)>=Bv(j),则该点符合局部曲率最大的性质，作为候选拐点。
• 筛选条件一：判断候选拐点相邻三点 p i − 1 p_{i-1} pi−1​、 p i p_{i} pi​、 p i + 1 p_{i+1} pi+1​是否位于同一条直线上，如果在则排除该点
• 筛选条件二：计算自适应弯曲值（Bending Value）。算法流程如下：计算候选点的搜索范围k从1开始增加，用 b i k b_{ik} bik​表示当前Bending Value。如果 b i k > = b i k + 1 b_{ik}>=b_{ik+1} bik​>=bik+1​，k增加1，否则停止增加。求得连续的Bending Value值后，需要再进行求平均值，作为最终该点的弯曲值，计算公式如下： b v i = 1 k i ∑ j = 1 k i b i j b_{v_{i}}=\frac{1}{k_{i}}\sum^{k_{i}}{j=1}b{ij} bvi​​=ki​1​j=1∑ki​​bij​ 根据计算的自适应拐点，还需要满足以下条件：- 条件一： b v i < t h e t a b_{v_{i}}<theta bvi​​<theta- 条件二： b v i < b v j b_{v_{i}}<b_{v_{j}} bvi​​<bvj​​,对于 j = i − 1 j=i-1 j=i−1或 j = i + 1 j=i+1 j=i+1- 条件三： b v i = b v i − 1 b_{v_{i}}=b_{v_{i-1}} bvi​​=bvi−1​​,并且 k i < k i − 1 k_{i}<k_{i-1} ki​<ki−1​- 条件四： b v i = b v i + 1 b_{v_{i}}=b_{v_{i+1}} bvi​​=bvi+1​​，并且 k i < = k i + 1 k_{i}<=k_{i+1} ki​<=ki+1​条件一表示Bending Value值应大于阈值，条件二、三、四表示拐点必须为局部最大值

三、python实现拐点的提取

3.1、曲线的点的平滑

当获取曲线的点整后点与点之间可能存在较大的间隔，需要我们对这些点进行一个采样来增加其连续性。一般采样方法有DDA、一次贝塞尔曲线拟合、二次贝塞尔曲线拟合或三次贝塞尔曲线离合。其中DDA和一次贝塞尔曲线拟合类似。都是通过两点之间直线的斜率来进行一个采样，当然使用更高阶的方法，采样曲线也更加平滑。

3.1.1、一次贝塞尔曲线拟合

如上图所示，对于平面上的两个点 P0 和 P1，假设另一点 B 匀速地从 P0 点运动到 P1 点，则有 B 点在 t 时刻的坐标公式：

将 B 点在各个时刻的坐标依次连接起来所形成的线，就是所谓的贝塞尔曲线。此公式表示的是一次贝塞尔曲线，也称为线性贝塞尔曲线。

python实现如下：

defgetFirstBezierPointByT(start,end,t):'''
    根据一次贝尔曲线的的计算公式计算各个时刻的坐标值
    :param start:
    :param end:
    :param t:
    :return:
    '''
    x=(1-t)*start[0]+t*end[0]
    y=(1-t)*start[1]+t*end[1]return[x,y]defcalculateFirstBezierPoints(start,end):'''
    计算两点之间的塞尔曲线点集
    :param start:
    :param handle:
    :param end:
    :return:
    '''
    bx=start[0]
    by=start[1]
    ex=end[0]
    ey=end[1]

    beDis=math.sqrt(math.pow((bx-ex),2)+math.pow((by-ey),2))

    count=int(beDis//1)if count<2:return[start]

    step =1.0/ count
    points=[]
    t =0.0for i inrange(count):
        points.append(getFirstBezierPointByT(start, end, t))
        t += step

    return points

deffirstBezierCurveFitting(pts):'''
    一次贝塞尔曲线拟合
    :param pts:
    :return:
    '''
    new_pts =[]for pt in pts:
        new_pt =[]for i inrange(0,(len(pt)-1)):
            pp=calculateFirstBezierPoints(pt[i], pt[i +1])
            new_pt += pp

        new_pt.append(pt[len(pt)-1])
        new_pts.append(new_pt)return new_pts

3.1.2、二次贝塞尔曲线拟合

同样地，对于平面上的三个点 P0、P1 和 P2 ，假设 P0P1 之间有个点 B1 匀速地从 P0 运动到 P1 ，P1P2 之间有个点 B2 匀速地从 P1 运动到 P2，则有：

假设另一点 B 匀速地从 B1 运动到 B2，则有 B 点的坐标公式：

将 B1 和 B2 的坐标公式代入上面的表达式，整理后得到 B 点的坐标公式：

B 点在各个时刻的坐标所连成的曲线即为二次贝塞尔曲线，其中 P0 和 P2 称为 数据点，P1 称为 控制点 。
具体python实现可以参考如下链接实现。

参考链接：

一种简单的贝塞尔拟合算法

3.2、拐点的计算

3.2.1、Bending value的计算

defcomputeBendingValue(p1,p2,p3):'''
    计算弯曲值
    :param p1:
    :param p2:
    :param p3:
    :return:
    '''returnmax(abs(p1[0]+p3[0]-2*p2[0]),abs(p1[1]+p3[1]-2*p2[1]))

3.2.2、判断三点是否在同一条直线上

defisSameGradient(p1,p2,p3):'''
    判断相邻三点是否在同一条直线上
    :param p1:
    :param p2:
    :param p3:
    :return:
    '''
    g1=(p1[1]-p2[1])/(p1[0]-p2[0]+0.00001)
    g2=(p2[1]-p3[1])/(p2[0]-p3[0]+0.00001)return g1==g2

3.2.3、计算拐点

计算拐点时，需要有些核心注意点：

• 计算笔迹端点的Bending value，需要进行一些预处理，我的处理如下：#当位于左端点的时候if i-k<0: p1=pt[i]else: p1=pt[i-k]#当位于右端点的时候if i+k>=len(pt): p3=pt[i]else: p3=pt[i+k]
• 如何计算自适应Bending value k0=1 bv0=0 bv_list=[]# 计算候选拐点所有的Bending Value曲率，直到最大值为止while k0+i<len(pt)and i-k0>0: bv0=computeBendingValue(pt[i-k0],pt[i],pt[i+k0])if bv0>=bv: bv_list.append(bv0) bv=bv0 k0+=1if bv0<bv:break k_list[i]=k0 # 计算所有曲率的平均值，作为最终的候选点的曲率iflen(bv_list)==0: avg_bv=bv else: avg_bv=sum(bv_list)/len(bv_list)
• 进一步筛选拐点的实现# 条件一：bv<theta.theta=1.1# 条件二：bvi<bvj and j=i-1 or j=i+1,表示# 条件三：bvi==bvi-1 and ki<ki-1# 条件四：bvi==bvi+1 and ki<=ki+1# 条件一表示Bending Value应该大于theta；条件二~四表示Bending Value应该为局部最大值if avg_bv<1.1or \ (curvs[i]< curvs[i -1]or curvs[i]< curvs[i +1])or \ (curvs[i]==curvs[i-1]and k_list[i]<k_list[i-1])or \ (curvs[i]==curvs[i+1]and k_list[i]<=k_list[i+1]):continueelse: result.append(i)
• 最后还需要进一步合并相邻的拐点 merge_result=[] i=0 tmp=[]while i+1<len(result_1):if result_1[i+1]-result_1[i]<5: tmp.append(result_1[i])if i+1==len(result_1)-1: tmp.append(result_1[i+1]) merge_result.append(tmp) tmp=[]else: tmp.append(result_1[i]) merge_result.append(tmp) tmp=[]if i +1==len(result_1)-1: merge_result.append([result_1[i+1]]) i=i+1# 合并最终的结果 new_result=[]for res in merge_result: avg_res=sum(res)//len(res) new_result.append(avg_res)

因为项目原因，不方便提供完整代码，但核心点已经给出，方便大家参考。最终结果如下：