[發明專利]字形剖分方法及字形剖分裝置

有效

• 申請號: 201710197665.X
• 申請日: 2017-03-29
• 公開（公告）號: CN108665514B
• 公開（公告）日: 2021-02-09
• 發明（設計）人: 賈雪莎
• 申請（專利權）人: 北大方正集團有限公司;北京北大方正電子有限公司
• 主分類號: G06T11/60
• 分類號: G06T11/60
• 代理公司: 北京友聯知識產權代理事務所(普通合伙) 11343
• 代理人: 尚志峰;汪海屏

本發明提供了一種字形剖分方法和一種字形剖分裝置，其中，所述字形剖分方法包括：獲取待剖分字形中的字形輪廓，以確定其內輪廓和外輪廓；確定與每個內輪廓對應的外輪廓，以根據每對對應的內輪廓和外輪廓得到所述待剖分字形的至少一個連通區域；按照預設Delaunay算法對所述至少一個連通區域中的每個連通區域進行三角剖分，得到至少一個預設Delaunay三角形；按照預設貪心算法對所述至少一個預設Delaunay三角形進行合并，得到所述待剖分字形的至少一個凸多邊形。通過本發明的技術方案，可以達到最大凸剖分的目的，而且還解決了二維字形中存在孔的字形剖分問題和部分區域未剖分的問題。

技術領域

本發明涉及圖形處理技術領域，具體而言，涉及一種字形剖分方法和一種字形剖分裝置。

背景技術

字形剖分屬于一種圖形處理技術，對圖形學來說，是極為重要的一項預處理技術，被廣泛應用于文字變形、字體漸變等領域。對字形進行三角剖分以及凸剖分，可以很好地解決不同構字體的映射問題。

由于三角形是平面域的單純形，與其他類型的多邊形相比，它具有許多特性和優點，例如可以更好地貼近擬合復雜邊界等。比如，在計算機圖形處理，圖形顯示及模式識別等許多領域中都涉及三角剖分問題，三角剖分對數值分析以及圖形學等來說，都是極為重要的一項預處理技術，可以說任意多邊形的三角剖分算法是計算機圖形學的一個重要理論基礎。

目前，相關技術中公開了多種對任意多邊形進行三角剖分的方法，但是由于字形的復雜性，尤其是手寫字體，字形更復雜多變，使得當前一些三角剖分方法對字形剖分效果不佳，容易出現對字形的空白部分(包括內部的孔和外部的凹處)進行了剖分和部分區域沒有剖分的問題，而這嚴重影響了進一步的圖像處理，例如不能準確地重現或者表示字形等等。目前常用的方法是Delaunay三角剖分方法(Delaunay triangulation algorithm)，因為它具有“三角剖分最小內角最大化”的特性，能盡可能地避免病態三角形出現，剖分效果有所提高，但在一定程度上還是存在上述兩個問題。

因此，為了解決上述問題，需要一種新的字形剖分方案，生成較好的三角形，以確保字形剖分的效果和質量。

發明內容

本發明正是基于上述技術問題，提出了一種新的技術方案，通過讀取待剖分字形的字形輪廓，利用改進的Delaunay算法對字形進行三角剖分，并結合貪心算法對剖分得到的三角形進行合并的方式，不僅可以達到最大凸剖分的目的，而且還解決了二維字形中存在孔的字形剖分問題和部分區域未剖分的問題，使得進一步的字形處理變得更加方便，有效地提高了字形剖分的質量。

有鑒于此，根據本發明的第一方面，提出了一種字形剖分方法，包括：獲取待剖分字形中的字形輪廓，以確定其內輪廓和外輪廓；確定與每個內輪廓對應的外輪廓，以根據每對對應的內輪廓和外輪廓得到所述待剖分字形的至少一個連通區域；按照預設Delaunay算法對所述至少一個連通區域中的每個連通區域進行三角剖分，得到至少一個預設Delaunay三角形；按照預設貪心算法對所述至少一個預設Delaunay三角形進行合并，得到所述待剖分字形的至少一個凸多邊形。

在該技術方案中，當獲取到待剖分字形中的每一個內輪廓以及與其對應的外輪廓后，其中，待剖分字形的內輪廓呈順時針方向，外輪廓呈逆時針方向，可以根據每對對應的內輪廓和外輪廓得到該待剖分字形的一個或多個連通區域，進而通過對每一個連通區域應用預設Delaunay算法(即改進的Delaunay算法)進行三角剖分，然后對得到的一個或多個預設Delaunay三角形應用預設貪心算法進行合并，以將該待剖分字形剖分為至少一個凸多邊形，達到最大凸剖分的目的的同時，可以解決二維字形中存在孔(即空白區域)不利于字形剖分的問題和字形的部分區域無法剖分的問題，使得進一步的字形處理變得更加方便，有效地提高了字形剖分的質量。