????????因產品需求，我們打造了自主的畫筆組件InkCanvas，在我們的項目紙筆課堂、曉課堂中得到了很好的應用。同時我們也通過技術輸出，在直播云項目中集成了組件的核心算法，升級了其涂鴉功能中的筆跡展示效果，在多類終端（Windows、Mac、Iphone/IPad、Android Phone/Pad）中，都有不錯的表現。

????????我們今天就來分享一下畫筆組件的核心算法之一 —— 手寫筆跡還原算法。

????????手寫筆跡還原是將一系列有序的坐標采樣點，轉換為連續的筆劃線條曲線的過程。

????????比如我們用直線線段將這些點逐個連接起來，就實現了一個最簡單的筆跡還原算法。但是這種算法效果肯定不會太好，比如不夠光滑（當輸入點比較稀疏時），連接點周邊的曲線不連續。

????????所以我們需要一個更強大的算法，針對筆跡采樣點做更進一步的特征提取，做更細致的處理，用更好的方案去定義、計算其幾何輪廓，這樣才能夠還原出一些“原汁原味”的效果，也就是我們常說的體現書寫風格。

1、筆跡輸入設備

????????在討論具體的還原算法之前，我們先要介紹一下筆跡點輸入相關一些知識。

????????畫筆筆跡輸入來源于各種各樣的設備，比如手寫板，觸摸屏，甚至于普通的鼠標也可以作為筆跡的輸入設備。不管什么設備，其輸出的都是一系列帶元數據的坐標點，有些設備能夠感知手寫壓力（比如通過電感線圈），還有些設備能夠識別筆尖的粗細（接觸面積）。設備的采樣率也會不同，每秒10~200個點都有。

????????因此一個坐標點，其元數據可能包含：壓力、接觸面積、時間戳等。我們的畫筆組件主要處理壓力值，根據壓力改變筆跡的粗細。

2、筆跡還原算法結構

????????通過嘗試我們發現，手寫筆跡還原最關鍵的兩個效果是平滑和筆鋒，有了這兩個效果，差不多能夠很好的體現書寫風格。

????????要做到平滑，我們需要對輸入的筆跡進行一些整理，我們會合并一些點，也會補充一些點，其中最關鍵的是?Bezier 插值算法的應用。

????????要還原筆鋒，主要是對壓力值做細致的處理，能夠還原出筆劃的粗細變化，同時讓這種粗細變化盡量平滑。

????????當然，性能要求也是很關鍵的，畢竟實時書寫的場景是在教學中是最常見的，所以算法本身也不能太過復雜，輸出的圖形不能對渲染模塊有太高的要求和太大的壓力。

????????最終，我們的筆跡還原方案使用的下面這樣的算法結構。整個算法主要分為“路徑整理”和“路徑轉換”兩部分，每個部分又分別包含一些小的步驟，下面我們逐個介紹。

3、路徑整理

????????針對輸入的原始路徑，我們需要做兩方面的整理。

????????一方面，如果輸入某一段路徑的筆跡點比較稠密，并且路徑也比較連續，那么我們可以用簡化的路徑來代替這部分路徑，這樣能夠提升計算及渲染的性能，也減少了采樣噪聲（局部的輕微凸出點）、采樣精度帶來的影響。

????????另一方面，如果某一段路徑的筆跡點比較稀疏，我們就需要在該路徑上補充一些點，以達到減少曲率，增加圓滑度的效果。

????????需要說明的是，這里的算法需要在物理尺寸的分辨率下進行，這樣還原出來的筆跡更貼近自然效果。實際上，所有經驗參數都是基于物理尺寸實驗確定的。

????????下面的對比圖可以看出路徑整理的效果。

? ?

?????????這組數據來源于某個型號的手寫板。左圖是原始輸入路徑，右圖是處理后的筆跡路徑，通過插值補充了一些點，使得曲線變得更平滑。

????????下面我們詳細介紹其中的算法過程。

3.1、預處理

????????在預處理階段，需要做下列工作：

• 去除掉一些重復點

????????當相鄰兩個點的距離很小時，可以認為是重復點，去除其中一個。去重后的點保存于點數組 P 中。

• 轉換為物理尺寸

????????將點的坐標轉換到以Himetric（緹）為單位的值上，Himetric=0.001cm，采用常見的96dpi屏幕密度，這個轉換就是乘以（2540/96）。

????????P[i] = P[i] *?(2540.0 / 96.0)

• 計算路徑累計長度 N

????????n[0] = 0；n[i]= n[i - 1] + length(P[i] - P[i - 1])；其中 length 為二維矢量長度，整個路徑累計長度我們記為 l。

3.2、關鍵點分析（岐點）

????????岐點是筆跡路徑上不連續的點，也是路徑上關鍵特征點，在路徑整理過程中，岐點是保留不做變動的。

????????首先我們計算所有點的包圍矩形 R

?????????R 的半周長為 d，結合之前計算的路徑累計長度 l，點的總個數 c，我們計算出一個關鍵參數 s：

????????這個 s 怎么理解呢？首先 l / c 是相鄰兩點之間的平均距離， l / d 是可以看作是圖形的分形維數。所以 s 描述的是最小可分辨路徑長度，小于該長度的路徑作為一個整體處理，不再還原其內部細節。

????????在上面的例子里面，這些數值為：

????????c = 36

????????d=1983.813 (約2cm）

????????l = 3582.698（約3.6cm）

????????s = 134.796 （約1.35mm）

????????在有了 s 之后，我們接下來尋找岐點。

????????首先需要計算路徑上每一點的曲率，方法如下：對路徑的每一個點，分別找出前后兩個到該點的累計距離不小于 s 的第一個點，然后計算三點夾角的曲率（1 - 余弦cos）。

????????當三點在一條直線上，且方向一致時，曲率為0，三點形成直角時，曲率為1，但方向相反時，曲率為2。所以曲率越大，說明在該點的路徑方向變化越大。

????????當曲率大于 0.8 時 （78°），再找出附近所有點中曲率最大的點，這個點就是一個岐點。

????????為了加快計算，當曲率小于 0.035 時 （15°）時，直接跳過附近（距離小于s）的點。

?????????在上面的例子中，我們找到了6各岐點（包括兩個端點，分別為第0，7，16，22，29，35個點）。

3.3、路徑分段及方向計算

????????在這一步，我們對兩個相鄰岐點之間的路徑切割為小段，并計算出路徑在分段起點和終點的方向，為下一步的曲線擬合做準備。

????????分段的依據如下：

????????1、至少包含4個點（包含端點），除非碰到了岐點，有可能小于3

????????2、可以包含更多的點，只要這些點的方差小于某個值。

????????方差的計算方法如下：

????????取這些點中的5個點（包括兩個端口，其他點均勻發布）p[i]，i=0,1,2,3,4,5

????????令矢量 ，其中?

????????則方差

????????因為路徑累計距離n是有方向性的，所以c[1]、c[3]是負數。

????????當這5個點中所有相鄰點的距離都相等時，c=[32/3, -128/3, 64, -128/3, 32/3]，如果進一步這5個點在一條直線上，那么 c = 0。

????????完成分段后，還需要計算分段起點和終點的方向（切線）。

????????對于一個點P的切線方向，其切線 T 的計算方法如下：

• 如果該點是岐點：考慮后續（對于終點，則是前面）兩個點：A、B，
• 如果是中間點，考慮前面兩個點 A、B 及后續一個點 C， ，并且下一個分段起點的切線與上一個分段終點的切線相反。

????????這里的方向都是指向內部的，所以在同一個點，前后兩個分段的方向是相反的。

3.4、曲線擬合

????????曲線擬合就是用樣條曲線來替代原先的分段路徑。采用3階 Bezier 擬合，每個曲線除了兩個端點，還需要計算兩個控制點。根據分段點的個數不同，計算的方式也不一樣，具體為：

• 2個點：實際上退化為直線，控制點為連線的兩個3等分點
• 3個點：退化為二次拋物線，假設二級 Bezier 的三個控制點為 A、B、C，且參數為 t 時，對應到中間點 P，即：

????????，其中

????????那么：

????????

????????提升為3階，則：

????????

????????

• 超過3個點：通過最小方差擬合為3階曲線，同時還需要結合端點的切線，具體算法略過。

3.5、曲線展開

????????曲線展開就是將3階Bezier曲線離散化，這里關鍵的問題是要離散到多少個點。

????????計算點的個數，取決于兩個參數：t 和 c。

????????t 與筆跡粗細對數級相關，粗細為一個像素時，t 大概在3.98 緹（0.03mm）；

????????c 與曲線的曲率有關，它是 Bezier 4個控制點組成的 2 組相鄰三角形的中線長度中的較大者。

?????????但 時，只展開為一個點（終點），否則展開為 sqrt(c / t) + 3 個點。可以看出，筆跡越粗，曲線越平直，展開的點越少。

????????最后將點的坐標轉換為像素單位乘以（96/2540），就完成了我們整個筆跡點整理的過程。

4、路徑轉換

????????在這個階段，我們將筆跡點的路徑轉換為可渲染的路徑。過程中需要處理壓力值，還有考慮各節點連接的平滑性。在生成渲染路徑后，就可以交由渲染模塊去展示了。

????????路徑渲染通常有“輪廓”和“填充”兩種模式，我們采用填充模式，因為“輪廓”渲染會涉及到各種線形樣式配置，且各個渲染實現也不一致；相反“填充”模式就顯得簡單、明確，這也是文字字體系統使用的渲染方式。

????????渲染路徑通常是有一系列作圖命令組成，命令有下列類型：

• MoveTo(A)，移動當前點P，開始一段新路徑
• LineTo(A)，畫線到指定點A，連接P和A，完成作圖后，當前點 P 變為 A
• ArcTo(R, A)，以指定半徑畫橢圓弧到指定點 A，當前點 P 也在弧上，完成作圖后，當前點 P 變為 A
• QuadraticBezierTo(A, B)，以控制點 A 和端點 B，畫一段二級 Bezier 曲線，當前點 P 是曲線的起點，完成作圖后，當前點 P 變為 A
• BezierTo(A, B, C)，以控制點 A、B 和端點 C，畫一段三級 Bezier 曲線，當前點 P 是曲線的起點，完成作圖后，當前點 P 變為 A

????????所以我們最終生成的渲染路徑是一個長條包圍區域，如下圖：左邊是輪廓示意圖，右邊是最終渲染效果。

???

4.1、壓力插值

????????因為整理后的點，很多都不是原始點了，所以沒有附加壓力信息。這就需要我們恢復出每個點的壓力信息，這樣后續生成的渲染路徑才能夠反應出原始的壓力變化。

????????這里我們通過路徑累計長度來近似計算每個Bezier點的壓力值，依據的是一個假設：即路徑整理后，路徑的長度沒有變化。

????????將路徑拉直后，每一個Bezier點 P （位置l(P)）一定在兩個相鄰的原始點 A、B 之間，通過A、B的壓力值p(A)、p(B)及路徑位置l(A)、l(B)，可以線形擬合出 P 點的壓力值 p(P)：

????????

????????有了壓力信息，下面可以正式進入路徑生成的環節了。

4.2、節點合并

????????所謂節點，就是Bezier路徑上的點，但是節點上還記錄著與它連接的前序點。因為可能合并節點，所以前序點不一定是Bezier路徑的前一個點，有可能是更前一個點。

????????在討論合并之前，還需要說明一下點的形狀。點的形狀一般是正方形（長方形）或者圓形（橢圓型），其尺寸與壓力值成比例。另外，每個點有其包圍矩形，即包圍其形狀的最小矩形，包圍矩形是計算節點合并的依據。

????????兩個矩形之間存在包含關系，這里包括不是絕對的，只要相交區域大于一定比例（比如95%），就認為是包含的，而且規定面積大的矩形包含面積小的矩形。

????????我們在合并時要考察當前2個或者3個相鄰節點的包含關系（即包圍矩形包含關系），當節點有包含關系時，合并或者丟棄節點。如下圖：

?????????合并與丟棄有一點區別。如果當前節點包含前序節點，則合并，后續節點的前序節點是當前節點對應的點。如果當前節點被前序節點包含，則丟棄當前節點，后續節點的前序節點是前序節點對應的點。

????????當我們有了3個連續節點，就可以進入下一個處理階段。

4.2、節點分段

????????此時我們有3個連續節點PP、P、C，分段從 PP 開始，然后不停的用 C 點連接 P 點，并滑動 PP < P < C，補充新的 C 點，當分段結束時，在當前 P 點結束。

????????分段結束時，仍然滑動?PP < P < C，下個分段從當前的 P 點開始。

????????什么情況下應該結束分段呢？

????????總的來說，我們考慮前后節點的方向變化、包圍矩形面積變化，以及 PP、C的包圍矩形是否相交。當方向、大小變化超過閾值時，就需要重新開始分段。

????????從之前的渲染路徑輪廓圖（下圖），可以看出整個渲染路徑有多個分段，且一般在方向變化時開始新的分段。新分段的起點與上一個分段終點重疊。

4.3.、節點連接

????????節點連接是將節點對應的點與節點的上一個點連接（不一定是Bezier路徑的上一個點），以及端點的閉合連線。

????????因為最終生成的是一個包圍路徑，所以需要用兩個路徑序列分別表示從起點到終點和從終點到起點的路徑輪廓。這兩個序列分別稱為 AB 序列，DC序列。

????????在生成包圍路徑時，需要考慮點的形狀（矩形，橢圓型），針對不同的點的形狀，有不同的處理方式。

4.3.1、矩形風格

????????對于矩形，兩個矩形的連接有四根線（頂點連線，如下圖），哪根連線應該加入 AB 序列，哪根連線應該加入 DC 序列呢？

????????其實有這樣一個規則，當通過某個頂點的兩個邊的方向與該點的連線方向都一致時，則該點為 A 點；都不一致時，該點為 C 點；分別對應另一個矩形的兩個的頂點 B、D 。AB連線加入AB序列，DC連線（反向）加入DC序列。

????????對于起點，順著矩形邊的方向從 C 到 A 的連線也加入AB序列；對于終點，從 B 到 D 的連線也加入AB 序列。

?????????下列圖描述了渲染路徑輪廓構建的過程，圓圈是起點，紅色線是AB序列的線，藍色線是DC序列的線，但是DC序列中的線的加入順序是反過來的。

4.3.2、橢圓風格

????????對于橢圓，有兩個連接公切線，同樣依據方向一致性原則，指定為AB、DC線。分別加入AB 、DC序列。但是與矩形有幾不同點：

• 在起點、終點處，有一段橢圓弧連接線
• 在中間點，根據節點方向變化，在內外側有一些特殊處理
  • 內側需要計算前后兩段連線（如下圖兩段DC線）的交點，在交點處連接
  • 外側需要在兩個切點（同一個橢圓上）之間增加一段橢圓弧，以閉合路徑，并保持路徑的平滑性

????????計算橢圓公切線，是一個比較復雜的工程，實現中我們用圓（短半徑）的切點代替，然后拉伸到橢圓半徑上。

?

5、后記

????????至此，我們完成了手寫筆跡還原算法的介紹，歡迎大家留言討論。

????????核心算法基于C++及stl庫實現（開源地址），通過API對接，可以移植到大部分平臺。不過 Web JS 平臺好像無法集成 native 庫。

????????除了API對接，我們還準備通過SVG格式對接，讓組件能夠輸出SVG圖片。

總結

以上是生活随笔為你收集整理的手写笔迹还原算法（InkCanvas）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。