二值線形圖像移動圓矢量化方法

2023-08-11 12:40:11

專利名稱：二值線形圖像移動圓矢量化方法
二值線形圖像移動圓矢量化方法
技術領域：
本發明屬於計算機數字圖像處理技術領域，具體是一種二值線形圖像的矢量化方法。
背景技術：
二值線形圖像是工程上常見的圖像，如掃面的地形圖、林業調查區劃線形圖等，為 了在地理信息系統等計算機專門軟體系統中進一步分析處理，必須進行矢量化。常見的矢 量化方法有1、基於細化的矢量化方法。該類方法的優點是算法簡單、比較容易實現，缺點 是丟失了線寬信息、抗噪聲能力比較差、不利於人機互動操作。2、基於鄰接圖的矢量化方 法。該類方法不經細化直接對圖形進行識別，抗噪性能明顯加強，鄰接圖結構可節省存儲空 間，利用其鄰接關係能有效進行線段的特徵提取和識別。缺點是難以處理實際圖紙中的復 雜情況，這類方法對行程編碼掃描方向的依賴性導致斜線矢量化的質量較差。3、正交方向 搜索法。該算法的優點是不經細化，將搜索範圍集中於黑像素域，從單像素的判別轉為對區 域的搜索。缺點是不適合圖像的細線和細微結構的識別處理，特別在線條交叉區域的判斷 算法複雜。

發明內容
本發明需要解決的技術問題是針對現有技術中，二值線形圖像矢量化方法的上述
不足，提出一個精度高、抗邊緣噪聲能力強、無需細化、不必遍歷所有像素、矢量化過程中自
動測量線寬因而對於線寬差別大的圖像有很好的自適應性、具有線寬信息、矢量化過程中
自動識別輪廓、交叉點判別能力強、既適合全圖自動操作也適合進行人機互動操作的二值
線形圖像移動圓矢量化方法。 解決上述技術問題的技術方案是 (1)用常規方法打開一個二值圖像文件； (2)確定矢量化起始點通過滑鼠點擊圖像確定或計算機 自動掃描二值圖像確定，若採用後一方法確定，則從圖像左上角開始，逐行掃描， 遇到的首個圖像像素點作為起始點； (3)通過起始點確定起始圓心a :通過起始點作垂直於橫軸的直線，取該直線通過 圖像部分的線段中點，過此中點作垂直於縱軸的直線，取縱橫兩線段中的較短者的中點為 起始圓心，並將縱橫兩線段中較短的線段長度稱為"線段長"；
(4)取一大於1的實數K和一大於1的實數入； (5)以線段長的K倍為直徑D，以步驟(3)確定的圓心a為圓心畫移動圓；畫移動 圓時先到圓周坐標查找表中查找直徑為D的圓周像素坐標，若查到則將查到的圓周像素坐 標加上移動圓圓心a的像素坐標，得到移動圓的圓周像素坐標；若查不到則用Bresenham算 法生成圓心在原點、直徑為D的圓周像素坐標，加上移動圓圓心a的像素坐標，得到移動圓 的圓周像素坐標，同時將直徑D和圓心在原點的圓周像素坐標添加到圓周坐標查找表中；
(6)確定前進方向對起始圓，設此圓與圖像相交有兩個弧段，任取其中一個弧段 所在的方向為前進方向，將另一個方向記錄進分叉記錄表，記錄下起始圓心a的坐標和線 段長，獲取前進方向弧段的弦；對非起始圓，則兩個弧段中有一個與已矢量化部分相交，另 一個不相交，取不相交弧段所在方向為前進方向； (7)連接心弦線確定弦的中點，記錄弦中點坐標作為矢量化的節點，連接圓心與 弦中點，得"心弦線"線段； (8)K值調整與否的確定若心弦線跑出圖像，則移動圓太大，縮小K值，令K二 k/ 入，按步驟(5)處理；若圖像噪聲枝嚴重，則增大K值，令K二k *入，亦按步驟(5)處理； 無需調整K值的則按下一步驟(9)處理； (9)檢查是否有分叉若在前進方向有多個相交弧段，則線形圖像分叉，應選擇其 中一個為前進方向，其餘分叉方向記錄進分叉記錄表，記錄各自的弦長作為線段長和弦中 點作為圓心，待處理； (10)線條是否到頭或是否遇到已處理部分的檢查若沒有到頭也沒有遇到已處 理部分則按步驟(5)處理，否則按步驟(11)處理； (11)若是線條到頭，則按步驟(12)處理，若是遇到已處理部分，則前進方向的最 後一條弦和已處理部分相交於一點，在最後一個移動圓內必有一個分叉點a，找出分叉點 a，連接該分叉點和最後一個弦中點；尋找分叉點的方法是設最後一個移動圓圓心坐標為 (xd， yd)，分叉記錄表中的圓心坐標為(x， y)，滿足
min[(x-xd)2+(y-yd)2] 的(x， y)即為所求的分叉點坐標(xa， yj，將分叉點a從分叉記錄表中刪除，再按 步驟(12)處理; (12)檢查分叉記錄表是否為空若非空，則在分叉記錄表中讀取一個分叉點獲得 圓心和線段長，並將取中的分叉點在分叉記錄表中刪除，按步驟(5)處理；否則按下一步驟
(13)處理; (13)用滑鼠手工點擊圖像或計算機自動掃描查找新的起始點； (14)若找到新的起始點，按步驟(5)處理，否則按下一步驟(15)處理； (15)根據由所有弦中點組成的節點進行矢量化，消除冗餘節點；算法如下對相
鄰三節點ki，kw，ki+2，用Bresenham畫線算法畫節點kt和節點ki+2之間的連線，若ki+1剛好
在此連線上則刪除該節點，否則保留；反覆掃描所有節點，直至無節點刪除為止； (16)輸出結果。 本發明的有益效果在於一、精度高。當線形圖像為直線時，移動圓和線形圖像相 交弧段的弦和線形圖像的中心線垂直，這時矢量化結果嚴格通過中心線，不存在誤差。當線 形圖像為非直線時，相交弧段的弦和中心線接近垂直，也具有很高的精度。二、抗邊緣噪聲 能力強。當移動圓直徑適當大，就能避免邊緣枝、毛剌的幹擾。三、無需細化。矢量化過程 中中心線直接提取，無細化過程，不必遍歷所有像素。四、對線寬變化具有自適應性。矢量 化過程中通過測定相交弦的長度自動測量線寬因而對於線寬差別大的圖像有很好的自適 應性，同時具有線寬信息。五、自動識別輪廓和分叉點。矢量化過程中通過相交弧段的數量 可以自動識別輪廓和分叉點。六、本方法既適合全圖自動操作，也適合人機互動操作。

圖1為本方法的流程圖。 圖2為本方法實施例中矢量化開始時選擇起始點示意圖。 圖3為本方法中通過起始點確定起始圓心的示意圖。 圖4為本方法中確定線段長、前進方向、弦中點、心弦線示意圖。 圖5為本方法中心弦線跑出圖像落入背景，移動圓直徑過大示意圖。 圖6為本方法中噪聲枝存在，增大移動圓直徑示意圖。 圖7為本方法中矢量化前進過程中出現分叉情況示意圖。 圖8為本方法中一條線矢量化到頭的示意圖。 圖9為本方法中遇到已處理情況示意圖。 圖10為本方法實施例輸出結果。
具體實施方式
下面本發明結合實施例並參照附圖作進一步詳述 需說明的是，本申請材料中簡稱二值圖像上的線形物體為圖像，其他部分為背景， 而整個圖像稱為二值圖像；矢量化過程中的圓稱為移動圓；所有長度單位為像素。
本方法的流程參見圖l。 步驟l，用常規方法打開一個二值圖像文件； 步驟2，確定矢量化起始點按如下兩種方法中的一種確定起始點一是通過滑鼠 點擊確定，圖2中A點所示為用滑鼠點擊圖像確定的起始點，選定的起始點儘量靠近圖像的 中心線。二是計算機自動掃描二值圖像確定一個起始點，從圖像左上角開始，逐行掃描，遇 到的首個圖像像素點作為起始點。圖2中B點所示為計算機自動掃描二值圖像確定的一個 起始點，圖中左上部直線為掃描路線，都落在背景上，B點為掃描遇到的第一個圖像像素；
步驟3，通過起始點確定起始圓心通過起始點作垂直於橫軸的直線，取該直線通 過圖像部分線段的中點，過此中點作垂直於縱軸的直線，取縱橫兩線段中的較短者的中點 為起始圓心。如圖3中過A點(白色像素)作垂直於橫軸的直線，通過圖像部分的線段長 為19個像素，過其中點，即從上往下數的第IO個像素(圖中交叉處的黑色像素)作垂直於 縱軸的直線，通過圖像部分的線段長為12個像素。橫向線段(12個像素)比縱向線段(19 個像素)短，所以選擇橫向線段的中點作為起始圓心a，即從左往右第6或第7個像素作為 起始圓心，圖中所示為第6個像素(深灰色像素)。若以B點作為起始點，則起始圓心在像 素b處。本發明將縱橫兩線段中較短的線段長稱為"線段長"；
步驟4，取一大於1的實數K和一大於1的實數入； 步驟5，以線段長的K倍為直徑D，以步驟3確定的圓心a為圓心畫移動圓，見圖 4 ;畫圓採用Bresenham算法(見孫家廣等《計算機圖形學》第三版，清華大學出版社，1999 年)。畫移動圓時先到圓周坐標查找表中查找直徑為D的圓周像素坐標，若查到則將查到的 圓周像素坐標加上移動圓圓心a的像素坐標，得到移動圓的圓周像素坐標；若查不到則用 Bresenham算法生成圓心在原點、直徑為D的圓周像素坐標，加上移動圓圓心a的像素坐標， 得到移動圓的圓周像素坐標，同時將直徑D和圓心在原點的圓周像素坐標添加到圓周坐標 查找表中；
步驟6，確定前進方向對起始圓，設此圓與圖像相交有2個弧段，任取其中一個弧 段所在的方向為前進方向，將另一個方向記錄進分叉記錄表，即記錄起始圓心a的坐標和 線段長。獲取前進方向弧段的弦，如圖4中的線段CD。對非起始圓，則兩個弧段中有一個與 已矢量化部分相交，另一個不相交，取不相交弧段所在方向為前進方向，如圖8從A到B所 示； 步驟7，連接心弦線確定線段CD中點，稱為弦中點，如圖4中的白色像素b。記錄 弦中點坐標作為矢量化的節點。連接圓心與弦中點，此線段稱為"心弦線"，如圖4中的ab， a—> b方向為矢量化前進方向； 步驟8，K值調整與否的確定若心弦線跑出圖像，如圖5所示，則說明移動圓太大， 縮小K值，令K = k/ "轉步驟5 ;若圖像噪聲枝嚴重，如圖6所示，則增大K值，令K = k * 入，轉步驟5 ;無需調整K值則轉步驟9 ; 步驟9，檢查是否有分叉若在前進方向碰到多個相交弧段，則出現了線形圖像分 叉的情況，如圖7中以A點為圓心的圓，有2個弦中點。此時選擇其中一個為前進方向，將 其餘的分叉方向記錄進分叉記錄表，記錄各自的弦長作為線段長和弦中點作為圓心，待處 理； 步驟IO，線條是否到頭或是否遇到已處理部分的檢查若沒有到頭也沒有遇到已 處理部分則轉步驟(5)，否則轉步驟(11); 步驟ll，處理線條到頭或遇到已處理部分情況圖8所示為線條到頭的情形，轉步 驟12。如果是碰到已處理部分，如圖9所示，從A到B的白色線條是剛矢量化的矢量線條， 前進方向的最後一條弦和已處理部分相交於c點，則在最後一個移動圓內必有一個分叉點 a，找出分叉點a，連接該分叉點和最後一個弦中點d。尋找分叉點的方法設最後一個移動 圓圓心坐標為(Xd，yd)，分叉記錄表中的圓心坐標為(x，y)，滿足
min [ (x_xd) 2+ (y-yd) 2] 的(x，y)即為所求的分叉點坐標(xa，ya)。將分叉點a從分叉記錄表中刪除，轉步 驟12 ; 步驟12，檢查分叉記錄表是否為空若非空，則在分叉記錄表中讀取一個分叉點
獲得圓心和線段長，並將取中的分叉點在分叉記錄表中刪除，轉步驟5 ;否則轉步驟13 ; 步驟13，用滑鼠手工點擊圖像或計算機自動掃描查找新的起始點；
步驟14，如找到新的起始點，轉步驟5，否則轉步驟15 ; 步驟15，根據由所有弦中點組成的節點進行矢量化，消除冗餘節點；算法如下對 相鄰三節點ki，kw，ki+2，用Bresenham畫線算法畫節點和節點ki+2之間的連線，若ki+1剛 好在此連線上則刪除該節點，否則保留；反覆掃描所有節點，直至無節點可以刪除；
步驟16，輸出結果。其矢量化結果如圖10中的深色線條所示。
權利要求
一種二值線形圖像移動圓矢量化方法，其特徵在於按如下步驟進行(1)用常規方法打開一個二值圖像文件；(2)確定矢量化起始點通過滑鼠點擊圖像確定或計算機自動掃描二值圖像確定，若採用後一方法確定，則從圖像左上角開始，逐行掃描，遇到的首個圖像像素點作為起始點；(3)通過起始點確定起始圓心a通過起始點作垂直於橫軸的直線，取該直線通過圖像部分的線段中點，過此中點作垂直於縱軸的直線，取縱橫兩線段中的較短者的中點為起始圓心，並將縱橫兩線段中較短的線段長度稱為「線段長」；(4)取一大於1的實數K和一大於1的實數λ；(5)以線段長的K倍為直徑D，以步驟(3)確定的圓心a為圓心畫移動圓；畫移動圓時先到圓周坐標查找表中查找直徑為D的圓周像素坐標，若查到則將查到的圓周像素坐標加上移動圓圓心a的像素坐標，得到移動圓的圓周像素坐標；若查不到則用Bresenham算法生成圓心在原點、直徑為D的圓周像素坐標，加上移動圓圓心a的像素坐標，得到移動圓的圓周像素坐標，同時將直徑D和圓心在原點的圓周像素坐標添加到圓周坐標查找表中；(6)確定前進方向對起始圓，設此圓與圖像相交有兩個弧段，任取其中一個弧段所在的方向為前進方向，將另一個方向記錄進分叉記錄表，記錄下起始圓心a的坐標和線段長，獲取前進方向弧段的弦；對非起始圓，則兩個弧段中有一個與已矢量化部分相交，另一個不相交，取不相交弧段所在方向為前進方向；(7)連接心弦線確定弦的中點，記錄弦中點坐標作為矢量化的節點，連接圓心與弦中點，得「心弦線」線段；(8)K值調整與否的確定若心弦線跑出圖像，則移動圓太大，縮小K值，令K＝k/λ，按步驟(5)處理；若圖像噪聲枝嚴重，則增大K值，令K＝k＊λ，亦按步驟(5)處理；無需調整K值的則按下一步驟(9)處理；(9)檢查是否有分叉若在前進方向有多個相交弧段，則線形圖像分叉，應選擇其中一個為前進方向，其餘分叉方向記錄進分叉記錄表，記錄各自的弦長作為線段長和弦中點作為圓心，待處理；(10)線條是否到頭或是否遇到已處理部分的檢查若沒有到頭也沒有遇到已處理部分則按步驟(5)處理，否則按步驟(11)處理；(11)若是線條到頭，則按步驟(12)處理，若是遇到已處理部分，則前進方向的最後一條弦和已處理部分相交於一點，在最後一個移動圓內必有一個分叉點a，找出分叉點a，連接該分叉點和最後一個弦中點；尋找分叉點的方法是設最後一個移動圓圓心坐標為(xd，yd)，分叉記錄表中的圓心坐標為(x，y)，滿足min[(x-xd)2+(y-yd)2]的(x，y)即為所求的分叉點坐標(xa，ya)，將分叉點a從分叉記錄表中刪除，再按步驟(12)處理；(12)檢查分叉記錄表是否為空若非空，則在分叉記錄表中讀取一個分叉點獲得圓心和線段長，並將取中的分叉點在分叉記錄表中刪除，按步驟(5)處理；否則按下一步驟(13)處理；(13)用滑鼠手工點擊圖像或計算機自動掃描查找新的起始點；(14)若找到新的起始點，按步驟(5)處理，否則按下一步驟(15)處理；(15)根據由所有弦中點組成的節點進行矢量化，消除冗餘節點；算法如下對相鄰三節點ki，ki+1，ki+2，用Bresenham畫線算法畫節點ki和節點ki+2之間的連線，若ki+1剛好在此連線上則刪除該節點，否則保留；反覆掃描所有節點，直至無節點刪除為止；(16)輸出結果。
全文摘要
一種二值線形圖像移動圓矢量化方法，屬計算機數字圖像處理技術領域。在線形物圖像上畫一個圓，在沒有分叉的情況下，圓和圖像有兩條弧相交。連接相交弧的弦並確定弦的中點。讓圓心移動到弦的中點，產生新的圓、弦和弦中點，如此重複，形成一系列的弦中點，這些弦中點的連線就是圖像中心線。取圓的直徑等於弦長乘上一個常數，圓的大小根據局部性質自動調整，考慮線寬、精度、圖像邊緣噪聲枝等3個因素。如果在前進方向碰到多個相交弧段，則出現了線形圖像分叉的情況。此時選擇其中一個為前進方向，將其餘的分叉方向記錄進分叉記錄表，待處理。本發明具有精度高、抗噪聲能力強、線寬自適應、保留線寬信息、無需細化、交叉點識別能力強等特點。
文檔編號G06T9/00GK101794452SQ20101003979
公開日2010年8月4日 申請日期2010年1月18日 優先權日2010年1月18日
發明者葛宏立 申請人:浙江林學院