一種柵格圖像邊縫路徑及邊縫拓撲結構的生成方法及系統的製作方法

2023-08-11 13:23:16

專利名稱：一種柵格圖像邊縫路徑及邊縫拓撲結構的生成方法及系統的製作方法
技術領域：
本發明涉及圖像處理領域，尤其涉及一種柵格圖像邊縫路徑及邊縫拓撲結構的生成方法及系統。
背景技術：
在圖像處理中，彩色圖像邊界檢測技術有著極其廣闊的應用前景，在圖像識別、匹配、三維重建、圖像檢索、圖像分割等諸多熱點領域都有著重要的作用。
邊界檢測算法很多，但在邊界候補像素點生成後，邊界鍊表追蹤算法上效果較好的有邊縫追蹤算法(四鄰域追蹤)及八鄰域追蹤算法兩種。邊縫追蹤算法(四鄰域追蹤) 一般採用直接計算水平、豎直方向上的邊縫梯度來追蹤邊界，定位較為精確，但是由於只有四個鄰域方向，且邊縫梯度具有不穩定性，生成的邊縫邊界極易斷裂；八鄰域追蹤算法一般採用計算像素點梯度幅度，在八個方向上追蹤梯度幅度來追蹤邊界，具有較好的連續性，可是定位精度只能達到像素級，不夠精確。發明內容
本發明的目的在於針對現有技術的缺陷，提供一種柵格圖像邊縫路徑及邊縫拓撲結構的生成方法及系統，使生成的邊界具有更準確的定位精度、更好的連續性及更豐富的邊界信息。
本發明提供一種柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，該方法包括如下步驟
Sl 選定柵格圖像，通過梯度幅度圖的計算，進行邊界檢測計算，得到所述圖像的邊界點；
S2 選取步驟Sl中一個邊界點，根據像素點梯度幅度進行鄰域追蹤，得到下一個邊界點；
S 3 所述下一個邊界點結合前一個邊界點參照水平、豎直方向的邊縫梯度轉化為邊縫路徑；
S4 針對所有邊界點，重複步驟S2 S3，直至完成整幅柵格圖像的邊縫路徑。
進一步，如上所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，該方法還包括，記錄步驟S2 S4中邊縫路徑信息，以及交叉點的信息，生成邊縫拓撲結構，其中邊縫拓撲結構由邊界信息組及交叉點信息組組成。
進一步，如上所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，邊界信息組包括邊界鍊表、邊界起始交叉點位置及邊界終止交叉點位置三部分；交叉點信息組包括交叉點坐標位置及交叉點連接的邊界指針兩個部分。
進一步，如上所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，步驟(Si) 中，對柵格圖像的兩個方向梯度進行融合，得到所述圖像的梯度幅度圖，再通過非最大抑制算法和磁滯算法，得到邊界點候補圖像。
進一步，如上所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，步驟(S2) 中，在根據邊界點對照像素點梯度幅度進行鄰域追蹤時，遇到一個邊界點的四個或八個相鄰方向上存在三個或三個以上不相鄰邊界點的情況，本條邊界結束，記錄交叉點信息，在本條邊界外剩餘方向生成新的邊界繼續追蹤。
進一步，如上所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，步驟(S3) 中，轉化邊縫路徑包括
(I)邊縫起點位置的選取；
(II)邊縫路徑的轉化；
(III)重複步驟(II)直至遇到下一個交叉點，或整條邊縫路徑結束。
進一步，如上所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，步驟(I)中， 邊縫起點位置的選取包括
(a)第一個邊界點不為交叉點的邊縫起點位置為與第二邊界點不共有的最大邊縫梯度的以第一個邊界點為中心，最大邊縫梯度邊縫中心的逆時針方向上的邊縫點為邊縫起佔.^ \\\
(b)第一個邊界點為交叉點的邊縫起點位置為與第二邊界點共有的邊縫上兩個點中，除共有邊縫外另一個邊縫梯度較大的點。
進一步，如上所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，步驟(II) 中，邊縫路徑的轉化包括
(a)計算從邊縫起點圍繞像素中心沿順時針與逆時針兩個方向進行旋轉，遇到與第二邊界點共有的邊縫點就停止；
(b)尋找兩條路徑中未被標記走過的路徑，若都未標記走過，選擇路徑平均邊縫強度較大的路徑；
(c)交叉點上路徑外的走過的路徑標記為走過。
進一步，如上所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，該方法還包括，圖像邊縫路徑生成後，遍歷交叉點，修正交叉點處邊縫交點位置及邊縫路徑，交叉點會有如下兩種情況
①交叉點為孤立點時，捨棄四個邊縫梯度中最弱的一個邊界路徑，即將該點分配到與其顏色最相近的區域，不能從該邊連接邊縫路徑；
②交叉點為粘連點時，沿交叉點外輪廓連接邊縫路徑，捨棄一條最弱邊縫梯度的邊界路徑。
進一步，如上所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，交叉點為孤立點時，還包括
(a)邊縫路徑分支數為三時，按照連接時路徑不重複規則選擇其中一個分支頂點作為邊縫交點；
(b)邊縫路徑分支數為四時，選擇梯度最弱的邊縫的對邊的兩個頂點作為邊縫交點，修正交叉點位置並增加一個交叉點，按照連接時路徑不重複規則將剩餘兩條邊縫路徑各自延長到一個頂點，以兩個交叉點為起始點，增加一條連接邊縫路徑。
一種柵格圖像邊縫路徑及邊縫拓撲結構的生成系統，包括
圖像邊界點生成裝置，用於通過梯度幅度圖的計算，進行邊界檢測計算，得到所述圖像的邊界點；邊縫路徑生成裝置，用於選取一個邊界點，根據邊界點像素點梯度幅度進行鄰域追蹤，得到第二個邊界點，再結合前一個邊界點參照水平、豎直方向的邊縫梯度轉化為邊縫路徑；交叉點修正裝置，用於遍歷交叉點，修正交叉點處邊縫交點位置，；邊縫拓撲結構生成裝置，用於記錄邊縫路徑生成裝置中的邊縫路徑信息，以及交叉點修正裝置中的交叉點信息，生成邊縫拓撲結構。本發明的有益效果如下利用本發明所述的方法及系統生成的邊界具有更準確的定位精度、更好的連續性及更豐富的邊界信息，從而能夠適應目前圖像處理各熱點領域對邊界檢測越來越高的精度與越來越好的連續性上的應用要求。也就是說，通過該方法生成的邊界鍊表可以在保證邊界連續性的基礎上，將邊界精確的定位到邊縫精度；同時，所生成的邊縫拓撲結構具有豐富的邊界信息，可以在邊界與交叉點之間實現快速查詢，從而能夠實現任意位置邊界的快速跟蹤與尋找。


圖1為本發明實施例中一種柵格圖像邊縫路徑的生成方法流程圖；圖加為本發明實施例中一個彩色原圖，圖2b為圖加通過梯度幅度圖的計算進行邊界檢測計算得到的所述圖像的邊界點；圖3a為本發明實施例中像素轉邊縫示意圖，圖北為三邊交叉邊界修正圖，圖3c 為多交叉點粘連邊界修正圖；圖4為本發明實施例中一個邊縫拓撲結構；圖如為本發明實施例中的一個彩色原圖，圖恥為像素級邊界追蹤結果示意圖，圖 5c為邊界追蹤邊縫路徑結果示意圖；圖6為本發明實施例中的一幅完整柵格圖像中的邊界信息；圖7為本發明實施例中一種柵格圖像邊縫拓撲結構的生成系統結構圖。
具體實施例方式下面結合說明書附圖對本發明的具體實施方式
進行詳細說明。如圖7所示，本發明提供了一種柵格圖像邊縫路徑及邊縫拓撲結構的生成系統， 包括圖像邊界點生成裝置1，用於通過梯度幅度圖的計算，進行邊界檢測計算，得到所述圖像的邊界點；邊縫路徑生成裝置2，用於選取一個邊界點，根據邊界點像素點梯度幅度進行鄰域追蹤，得到第二個邊界點，再結合前一個邊界點參照水平、豎直方向的邊縫梯度轉化為邊縫路徑；交叉點修正裝置3，用於遍歷交叉點，修正交叉點處邊縫交點位置，；邊縫拓撲結構生成裝置4，用於記錄邊縫路徑生成裝置2中的邊縫路徑信息，以及交叉點修正裝置3中的交叉點信息，生成邊縫拓撲結構。上述系統所實現的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法如圖1所示，該方法包括如下步驟Sl 選定柵格圖像，通過梯度幅度圖的計算，進行邊界檢測計算，得到所述圖像的邊界點；本發明實施例中，對柵格圖像的兩個方向梯度進行融合，得到所述圖像的梯度幅度圖，再通過非最大抑制算法和磁滯算法，得到邊界點候補圖像。S2 選取步驟Sl中一個邊界點，根據像素點梯度幅度進行鄰域追蹤，得到下一個邊界點；本發明實施例中，在根據邊界點對照像素點梯度幅度進行鄰域追蹤時，遇到一個邊界點的四個或八個相鄰方向上存在三個或三個以上不相鄰邊界點的情況，本條邊界結束，記錄交叉點信息，在本條邊界外剩餘方向生成新的邊界繼續追蹤。S3:所述下一個邊界點結合前一個邊界點參照水平、豎直方向的邊縫梯度轉化為邊縫路徑；本發明實施例中，轉化邊縫路徑還包括(1)邊縫起點位置的選取，包括a)第一個邊界點不為交叉點的邊縫起點位置為與第二邊界點不共有的最大邊縫梯度的以第一個邊界點為中心，最大邊縫梯度邊鋒中心的逆時針方向上的邊縫點為邊縫起佔.
^ \\\ b)第一個邊界點為交叉點的邊縫起點位置為與第二邊界點共有的邊縫上兩個點中，除共有邊縫外另一個邊縫梯度較大的點。(2)邊縫路徑的轉化，包括a)計算從邊縫起點圍繞像素中心沿順時針與逆時針兩個方向進行旋轉，遇到與第二邊界點共有的邊縫點就停止；b)尋找兩條路徑中未被標記走過的路徑，若都未標記走過，選擇路徑平均邊縫強度較大的路徑；c)交叉點上路徑外的走過的路徑標記為走過。(3)重複步驟( 直至遇到下一個交叉點，或整條邊縫路徑結束。S4 重複步驟S2 S3，直至完成整幅柵格圖像的邊縫路徑。本發明實施例中，該方法還包括，記錄步驟S2 S4中邊縫路徑信息，以及交叉點的信息，生成邊縫拓撲結構，其中邊縫拓撲結構由邊界信息組及交叉點信息組組成。本發明實施例中，邊界信息組包括邊界鍊表、邊界起始交叉點位置及邊界終止交叉點位置三部分；交叉點信息組包括交叉點坐標位置及交叉點連接的邊界指針兩個部分。本發明實施例中，該方法還包括，圖像邊縫路徑生成後，遍歷交叉點，修正交叉點處邊縫交點位置及邊縫路徑，交叉點會有如下兩種情況(1)交叉點為孤立點時，捨棄四個邊縫梯度中最弱的一個邊界路徑，即將該點分配到與其顏色最相近的區域，不能從該邊連接邊縫路徑；(2)交叉點為粘連點時，沿交叉點外輪廓連接邊縫路徑，捨棄一條最弱邊縫梯度的邊界路徑。本發明實施例中，交叉點為孤立點時，還包括(a)邊縫路徑分支數為三時，按照連接時路徑不重複規則選擇其中一個分支頂點作為邊縫交點；(b)邊縫路徑分支數為四時，選擇梯度最弱的邊縫的對邊的兩個頂點作為邊縫交點，修正交叉點位置並增加一個交叉點，按照連接時路徑不重複規則將剩餘兩條邊縫路徑各自延長到一個頂點，以兩個交叉點為起始點，增加一條連接邊縫路徑。下面為本發明具體的實施例描述，以詳細說明在生成柵格圖像邊縫拓撲結構時的具體技術細節。圖加為本發明實施例中一個柵格圖像，圖2b為圖加通過梯度幅度圖的計算進行邊界檢測計算得到的所述圖像的邊界點。本實施例中的柵格圖像選用CMYK色彩模式，共有 C、M、Y、K四個色彩通道，但本發明的應用範圍並不局限於CMYK色彩模式的柵格圖像，其它色彩模式(如RGB等)的柵格圖像同樣適用於本方法。針對圖2選定的柵格圖像，分別計算各個通道的水平與垂直兩個方向梯度，採用梯度最大值融合法或多通道梯度融合法，再經過非最大抑制算法後、同向增強、細化算法和磁滯算法，得到圖像的邊界點。圖3a為本發明實施例中像素轉邊縫示意圖，圖北為三邊交叉邊界修正圖，圖3c 為多交叉點粘連邊界修正圖。邊縫邊界是指邊界點位於相鄰像素的中間位置，邊縫邊界追蹤過程為選取圖像中的一個邊界點，根據像素點梯度幅度進行鄰域追蹤，得到第二個邊界點；第二個邊界點結合第一個邊界點參照水平、豎直方向的邊縫梯度轉化為邊縫路徑。所謂像素級邊界就如圖 5b所示；邊縫邊界就如圖5c所示。在邊界進行鄰域追蹤時，遇到一個邊界點的四個或八個相鄰方向上存在三個或三個以上不相鄰邊界點時，本條邊界結束，記錄交叉點信息，將本條邊界外剩餘方向生成新的邊界繼續追蹤。本發明實施例中，轉化邊縫路徑還包括頭邊界點邊縫起點位置的選取，頭邊界點不為交叉點的邊縫起點位置為與第二邊界點不共有的最大邊縫梯度的以頭邊界點為中心，最大邊縫梯度邊縫中心的逆時針方向上的邊縫點為邊縫起點；頭邊界點為交叉點的邊縫起點位置為與第二邊界點共有的邊縫上兩個點中，除共有邊縫外另一個邊縫梯度較大的點。從追蹤到第二個邊界點時，每個點都結合前一個邊界點轉為邊縫路徑，計算從邊縫起點圍繞像素中心沿順時針與逆時針兩個方向進行旋轉，遇到與第二邊界點共有的邊縫點就停止；尋找兩條路徑中未被標記走過的路徑，若都未標記走過，選擇路徑平均邊縫強度較大的路徑；交叉點上路徑外的走過的路徑標記為走過。圖3a所示，兩個非交叉點邊界點路徑轉為邊縫點路徑的方法是遇到與下一像素點共有的邊縫點就停止，實例如下圖所示設左上角的頂點為上一邊縫點位置，XO為當前邊界點，Xl為下一邊界點位置，那麼，從左上角的邊界點到Xl點的路徑就有順時針的(0,-1)與逆時針的(-1,0),(0,1)兩種可能，在兩個路徑中，計算其邊縫幅度均值MeanMag，N為走過的邊縫個數，Mag為邊縫幅度
_4] Meanliiag = Σ'=。，7
N圖像邊縫路徑生成後，遍歷交叉點，修正交叉點處邊縫交點位置及邊縫路徑交叉點為孤立點時，捨棄四個邊縫幅度中最弱的一個邊界路徑(即將該點分配到與其顏色最相近的區域，不能從該邊連接邊縫路徑)。圖北所示，若邊縫路徑分支數為三， 按照連接時路徑不重複規則選擇其中一個分支頂點作為邊縫交點，圖北中三個分支頂點都可作為邊縫交點，所以捨棄該像素點四個邊中幅度最弱的一個邊界路徑，例如就是該像素點的上邊(虛線)，將這邊捨棄(意味著不能從該邊連接邊縫路徑)，那麼三個方向的邊縫路徑就只能聚合在該像素點的左下分支頂點了 ；若分支數為四，選擇打開邊縫對邊的兩個頂點作為邊縫交點，修正交叉點位置並增加一個交叉點，按照連接時路徑不重複規則將剩餘兩條邊縫路徑各自延長到一個頂點，以兩個交叉點為起始點，增加一條連接邊縫路徑。圖3c所示，交叉點為粘連點，五個邊縫路徑分支頂點沿交叉點外輪廓連接邊縫路徑，交叉點的內邊自動捨棄，然後計算外輪廓中幅度最弱的一個，例如就是最左邊的垂直邊，將這邊捨棄。圖4為本發明實施例中一個邊縫拓撲結構，其中包括邊界信息組和交叉點信息組。邊界信息組包括邊界鍊表、邊界起始交叉點位置及邊界終止交叉點位置三部分；交叉點信息組包括交叉點坐標位置及交叉點連接的邊界指針兩個部分。圖如為本發明實施例中的一個彩色原圖，圖恥為像素級邊界追蹤結果示意圖，圖 5c為邊界追蹤邊縫路徑結果示意圖。由圖可以看出，像素級邊界可以滿足對邊界定位精度要求不太高的需求，優點是邊界連續，缺點是定位不夠準確；邊縫邊界是指邊界點位於相鄰像素的中間位置，比像素級邊界準確，採用本發明的方法，可以兼顧像素級邊界的連續性及邊縫路徑的準確性。圖6為本發明實施例中的一幅完整柵格圖像中的邊界信息。圖中包含了 η組邊縫拓撲結構，每組邊縫拓撲結構都由邊界信息組及交叉點信息組組成。顯然，本領域的技術人員可以對本發明進行各種改動和變型而不脫離本發明的精神和範圍。這樣，倘若本發明的這些修改和變型屬於本發明權利要求及其等同技術的範圍之內，則本發明也意圖包含這些改動和變型在內。
權利要求
1.一種柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，包括如下步驟51選定柵格圖像，通過梯度幅度圖的計算，進行邊界檢測計算，得到所述圖像的邊界佔.52選取步驟Sl中一個邊界點，根據像素點梯度幅度進行鄰域追蹤，得到下一個邊界佔.53所述下一個邊界點結合前一個邊界點參照水平、豎直方向的邊縫梯度轉化為邊縫路徑；54針對所有邊界點，重複步驟S2 S3，直至完成整幅柵格圖像的邊縫路徑。
2.如權利要求1所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，其特徵在於， 該方法還包括，記錄步驟S2 S4中邊縫路徑信息，以及交叉點的信息，生成邊縫拓撲結構， 其中邊縫拓撲結構由邊界信息組及交叉點信息組組成。
3.如權利要求2所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，其特徵在於， 邊界信息組包括邊界鍊表、邊界起始交叉點位置及邊界終止交叉點位置三部分；交叉點信息組包括交叉點坐標位置及交叉點連接的邊界指針兩個部分。
4.如權利要求1所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，其特徵在於， 步驟(Si)中，對柵格圖像的兩個方向梯度進行融合，得到所述圖像的梯度幅度圖，再通過非最大抑制算法和磁滯算法，得到邊界點候補圖像。
5.如權利要求1所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，其特徵在於， 步驟(S》中，在根據邊界點對照像素點梯度幅度進行鄰域追蹤時，遇到一個邊界點的八個相鄰方向上存在三個或三個以上不相鄰邊界點的情況，本條邊界結束，記錄交叉點信息，在本條邊界外剩餘方向生成新的邊界繼續追蹤。
6.如權利要求1所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，其特徵在於， 步驟(S； )中，轉化邊縫路徑包括(I)邊縫起點位置的選取；(II)邊縫路徑的轉化；(III)重複步驟(II)直至遇到下一個交叉點，或整條邊縫路徑結束。
7.如權利要求6所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，其特徵在於， 步驟(I)中，邊縫起點位置的選取包括(a)第一個邊界點不為交叉點的邊縫起點位置為與第二邊界點不共有的最大邊縫梯度的以第一個邊界點為中心，最大邊縫梯度邊縫中心的逆時針方向上的邊縫點為邊縫起點；(b)第一個邊界點為交叉點的邊縫起點位置為與第二邊界點共有的邊縫上兩個點中， 除共有邊縫外另一個邊縫梯度較大的點。
8.如權利要求6所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，其特徵在於， 步驟(II)中，邊縫路徑的轉化包括(a)計算從邊縫起點圍繞像素中心沿順時針與逆時針兩個方向進行旋轉，遇到與第二邊界點共有的邊縫點就停止；(b)尋找兩條路徑中未被標記走過的路徑，若都未標記走過，選擇路徑平均邊縫強度較大的路徑；(c)交叉點上路徑外的走過的路徑標記為走過。
9.如權利要求1所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，其特徵在於， 該方法還包括，圖像邊縫路徑生成後，遍歷交叉點，修正交叉點處邊縫交點位置及邊縫路徑，交叉點會有如下兩種情況①交叉點為孤立點時，捨棄四個邊縫梯度中最弱的一個邊界路徑，即將該點分配到與其顏色最相近的區域，不能從該邊連接邊縫路徑；②交叉點為粘連點時，沿交叉點外輪廓連接邊縫路徑，捨棄一條最弱邊縫梯度的邊界路徑。
10.如權利要求9所述的柵格圖像邊縫路徑及邊縫拓撲結構的生成方法，其特徵在於， 交叉點為孤立點時，還包括(a)邊縫路徑分支數為三時，按照連接時路徑不重複規則選擇其中一個分支頂點作為邊縫交點；(b)邊縫路徑分支數為四時，選擇梯度最弱的邊縫的對邊的兩個頂點作為邊縫交點，修正交叉點位置並增加一個交叉點，按照連接時路徑不重複規則將剩餘兩條邊縫路徑各自延長到一個頂點，以兩個交叉點為起始點，增加一條連接邊縫路徑。
11.一種柵格圖像邊縫路徑及邊縫拓撲結構的生成系統，包括圖像邊界點生成裝置(1)，用於通過梯度幅度圖的計算，進行邊界檢測計算，得到所述圖像的邊界點；邊縫路徑生成裝置O)，用於選取一個邊界點，根據邊界點像素點梯度幅度進行鄰域追蹤，得到第二個邊界點，再結合前一個邊界點參照水平、豎直方向的邊縫梯度轉化為邊縫路徑；交叉點修正裝置(3)，用於遍歷交叉點，修正交叉點處邊縫交點位置，；邊縫拓撲結構生成裝置G)，用於記錄邊縫路徑生成裝置O)中的邊縫路徑信息，以及交叉點修正裝置(3)中的交叉點信息，生成邊縫拓撲結構。
全文摘要
本發明公開了一種柵格圖像邊縫路徑及邊縫拓撲結構的生成方法及系統，屬於圖像邊界檢測技術領域。該方法包括選定柵格圖像，通過梯度幅度圖的計算，進行邊界檢測計算，得到所述圖像的邊界點；選取步驟S1中一個邊界點，根據像素點梯度幅度進行鄰域追蹤，得到下一個邊界點；第二個邊界點結合第一個邊界點參照水平、豎直方向的邊縫梯度轉化為邊縫路徑；重複以上步驟，直至完成整幅柵格圖像的邊縫路徑；記錄邊縫路徑信息，以及交叉點的信息，生成邊縫拓撲結構。本發明生成的邊界具有更準確的定位精度、更好的連續性及更豐富的邊界信息，能夠適應目前圖像處理各熱點領域對邊界檢測的應用要求。
文檔編號G06T5/00GK102542555SQ20101060912
公開日2012年7月4日 申請日期2010年12月17日 優先權日2010年12月17日
發明者張宏志, 李平立, 薛濤, 袁夢尤 申請人:北京大學, 方正國際軟體(北京)有限公司