一種圖像的多邊形模型的簡化方法

2023-05-24 11:04:11 7

專利名稱：一種圖像的多邊形模型的簡化方法
技術領域：
本發明涉及一種圖像處理技術，尤其是涉及一種圖像的多邊形模型的簡化方法。
背景技術：
多邊形模型是計算機圖形中最流行、最重要，且得到最廣泛支持的模型表示方法。 但隨著技術的快速發展，圖像的多邊形模型的複雜性常常超過了系統的處理能力，為此人們提出了很多簡化圖像的多邊形模型的算法。圖像的多邊形模型的簡化也是圖像校正的關鍵環節之一(圖像的多邊形模型的簡化為圖像校正提供參考點)，高精度的圖像是保障圖像識別和圖像匹配有效進行的根本條件之一，因此圖像的多邊形模型的簡化結果的好壞將嚴重影響到後續圖像處理的圖像識別和圖像匹配的結果。目前，已有的幾何簡化算法大多應用於三角形網格模型的簡化，無法直接應用於多邊形模型的簡化。因此迫切需要一種新的方法對二維平面的多邊形模型進行簡化，以保證最終圖像處理的精度。

發明內容
本發明所要解決的技術問題是提供一種簡便快速，且能夠為圖像校正提供準確的參考點的多邊形模型的簡化方法。本發明解決上述技術問題所採用的技術方案為一種圖像的多邊形模型的簡化方法，其特徵在於包括以下步驟①獲取一幅待處理的二值化圖像，然後以自上而下、從左到右的水平掃描方式搜索二值化圖像中每一行的第一個黑色像素點，將二值化圖像中每一行的第一個黑色像素點按掃描順序構成的集合定義為左邊界像素點集，記為八(X，y)，再以自下而上、從右到左的水平掃描方式搜索二值化圖像中每一行的最後一個黑色像素點，將二值化圖像中每一行的最後一個黑色像素點按掃描順序構成的集合定義為右邊界像素點集，記為Vk(X，y)，其中， (χ，y)表示二值化圖像中的像素點的坐標位置；②根據左邊界像素點集Vjx，y)和右邊界像素點集VK(x，y)，構建凸多邊形模型， 具體過程如下②-1、將左邊界像素點集八(x，y)中的第一個像素點作為凸多邊形模型的起點，並將該起點的坐標位置保存到頂點集合V(x，y)中，將該起點作為當前頂點；②-2、將當前頂點與左邊界像素點集Vjx，y)中在當前頂點之後的各個像素點連線，然後計算每條連線與當前頂點所在的右側的水平直線之間的夾角；②-3、選取最大夾角對應的像素點，並將該像素點的坐標位置保存到頂點集合 V(x, y)中，再將該像素點作為當前頂點，返回步驟②-2繼續執行，直至左邊界像素點集 Vl(x, y)中的所有像素點處理完畢；②-4、判斷當前頂點與右邊界像素點集Vk(x，y)中的第一個像素點是否重合，如果是，則執行步驟②_5，否則，將右邊界像素點集Vk(x，y)中的第一個像素點作為當前頂點，並將該當前頂點的坐標位置保存到頂點集合V (X，y)中，然後執行步驟②-5 ；②-5、將當前頂點與右邊界像素點集Vk(X，y)中在當前頂點之後的各個像素點連線，然後計算每條連線與當前頂點所在的右側的水平直線之間的夾角；②_6、選取最小夾角對應的像素點，並將該像素點的坐標位置保存到頂點集合 V(x, y)中，再將該像素點作為當前頂點，返回步驟②-5繼續執行，直至右邊界像素點集 Ve(x, y)中的所有像素點處理完畢；②_7、判斷當前頂點與凸多邊形模型的起點是否重合，如果是，則從頂點集合 V(x,y)中刪除當前頂點的坐標位置，然後執行步驟②_8，否則，直接執行步驟②-8;②_8、順序連接頂點集合V(x，y)中的各個頂點構成凸多邊形模型，頂點之間的連線為凸多邊形模型的邊；③重複尋找凸多邊形模型中長度最短的邊，再用該長度最短的邊的兩條相鄰邊的延長線的交點的坐標位置替換頂點集合V(x，y)中該長度最短的邊對應的兩個頂點的坐標位置，直至頂點集合V(x，y)中所包含的頂點的個數為圖像校正所需的參考點的個數，獲得簡化後的多邊形模型，該簡化後的多邊形模型的頂點為圖像校正的參考點。所述的步驟①中左邊界像素點集Vjx，y)和右邊界像素點集Vk (X，y)的獲取過程為①-1、自上而下、從左到右對二值化圖像進行水平掃描，將二值化圖像中當前待水平掃描的行作為當前行；①_2、水平掃描當前行，在當前行中搜索到第一個黑色像素點時，結束當前行的水平掃描，並保存搜索到的第一個黑色像素點的坐標位置；①_3、將二值化圖像中待水平掃描的下一行作為當前行，返回步驟①-2繼續執行，直至二值化圖像中的最後一行處理完畢，結束二值化圖像的水平掃描；①_4、將二值化圖像中每一行的第一個黑色像素點按掃描順序構成的集合定義為左邊界像素點集，記為八(x，y)；①_5、自下而上、從右到左對二值化圖像進行水平掃描，將二值化圖像中當前待水平掃描的行作為當前行；①_6、水平掃描當前行，在當前行中搜索到第一個黑色像素點時，結束當前行的水平掃描，並保存搜索到的第一個黑色像素點的坐標位置；①_7、將二值化圖像中待水平掃描的下一行作為當前行，返回步驟①-6繼續執行，直至二值化圖像中的第一行處理完畢，結束二值化圖像的水平掃描；①_8、將二值化圖像中每一行的最後一個黑色像素點按掃描順序構成的集合定義為右邊界像素點集，記為Vk (X，y)。所述的步驟③的具體過程為③-1、計算凸多邊形模型中每條邊的長度，尋找長度最短的邊，將該長度最短的邊作為當前邊；③_2、延長當前邊的兩條相鄰邊，使當前邊的兩條相鄰邊的延長線相交於一點；③-3、從頂點集合V(x，y)中刪除當前邊對應的兩個頂點的坐標位置，並在刪除位置處加入當前邊的兩條相鄰邊的延長線的交點的坐標位置，構成新的頂點集合V(x，y)和新的凸多邊形模型；
③_4、判斷頂點集合中所包含的頂點的個數與圖像校正所需的參考點的個數是否相等，如果是，則結束邊的刪除，獲得簡化後的多邊形模型，該簡化後的多邊形模型的頂點為圖像校正的參考點，否則，返回步驟③-1繼續執行。所述的簡化後的多邊形模型的頂點的個數為4。與現有技術相比，本發明的優點在於通過掃描已知的二值化圖像得到左邊界像素點集和右邊界像素點集，然後搜索左邊界像素點集和右邊界像素點集獲取圖像的凸多邊形模型的所有頂點，再用凸多邊形模型中長度最短的邊的兩條相鄰邊的延長線的交點替代長度最短的邊的兩個頂點，達到刪除長度最短的邊的目的，經過多次最短邊的刪除後得到頂點數與圖像校正所需的參考點數相等的多邊形模型，該多邊形模型的頂點為圖像校正的參考點，這種多邊形模型的簡化方法不僅簡便快速，而且能夠準確地獲取圖像校正所需的參考點。此外，本發明的簡化方法可以應用於圖像識別、圖像匹配和圖像跟蹤等方面的準備工作中，以剔除環境偏移、照片偏差等因素帶來的誤差影響，為工程後續分析提供了有力的保障。


圖1為本發明的簡化方法的流程圖；圖2為一幅待處理的二值化圖像，該二值化圖像中「 X 」表示黑色像素點；圖3為從圖2所示的二值化圖像中獲取的構成左邊界像素點集八(x，y)的像素點和構成右邊界像素點集％&，》的像素點的示意圖；圖4為搜索凸多邊形模型的頂點的過程示意圖；圖5為從圖3中搜索凸多邊形模型的頂點的過程示意圖；圖6為從圖3中搜索凸多邊形模型的頂點的結果示意圖；圖7為圖6所示的各個頂點構成的凸多邊形模型的示意圖；圖8為從圖7所示的凸多邊形模型中刪除長度最短的邊的過程示意圖；圖9為簡化後的四邊形的示意圖。
具體實施例方式以下結合附圖實施例對本發明作進一步詳細描述。本發明提出的一種圖像的多邊形模型的簡化方法，其流程圖如圖1所示，其包括以下步驟①獲取一幅待處理的二值化圖像，如圖2所示，該二值化圖像中「 X，，表示黑色像素點，然後以自上而下、從左到右的水平掃描方式搜索二值化圖像中每一行的第一個黑色像素點，將二值化圖像中每一行的第一個黑色像素點按掃描順序構成的集合定義為左邊界像素點集，記為八(X，y)，再以自下而上、從右到左的水平掃描方式搜索二值化圖像中每一行的最後一個黑色像素點，將二值化圖像中每一行的最後一個黑色像素點按掃描順序構成的集合定義為右邊界像素點集，記為VK(x，y)，其中，(x,y)表示二值化圖像中的像素點的坐標位置。在二值化圖像中，像素值為1的像素點是黑色像素點，像素值為0的像素點是白色像素點。在此具體實施例中，左邊界像素點y)和右邊界像素點集VK(x，y)的獲取過程為①-1、自上而下、從左到右對二值化圖像進行水平掃描，將二值化圖像中當前待水平掃描的行作為當前行。①_2、水平掃描當前行，在當前行中搜索到第一個黑色像素點時，結束當前行的水平掃描，並保存搜索到的第一個黑色像素點的坐標位置。①_3、將二值化圖像中待水平掃描的下一行作為當前行，返回步驟①-2繼續執行，直至二值化圖像中的最後一行處理完畢，結束二值化圖像的水平掃描。①_4、將二值化圖像中每一行的第一個黑色像素點按掃描順序構成的集合定義為左邊界像素點集，記為八(x，y)。①-5、自下而上、從右到左對二值化圖像進行水平掃描，將二值化圖像中當前待水平掃描的行作為當前行。①_6、水平掃描當前行，在當前行中搜索到第一個黑色像素點時，結束當前行的水平掃描，並保存搜索到的第一個黑色像素點的坐標位置。①_7、將二值化圖像中待水平掃描的下一行作為當前行，返回步驟①-6繼續執行，直至二值化圖像中的第一行處理完畢，結束二值化圖像的水平掃描。①_8、將二值化圖像中每一行的最後一個黑色像素點按掃描順序構成的集合定義為右邊界像素點集，記為Vk (X，y)。圖3給出了從圖2所示的二值化圖像中獲取的構成左邊界像素點集八(x，y)的像素點和構成右邊界像素點集Vk (x，y)的像素點，圖3中「 (g)，，表示構成左邊界像素點集八(X， y)的像素點，「因」表示構成右邊界像素點集Vk(X，y)的像素點，「〇」表示既屬於左邊界像素點集八(x，y)又屬於右邊界像素點集％&，》的像素點，虛線表示水平掃描線。②根據左邊界像素點集Vjx，y)和右邊界像素點集VK(x，y)，構建凸多邊形模型， 具體過程如下②-1、將左邊界像素點集八(x，y)中的第一個像素點作為凸多邊形模型的起點，並將該起點的坐標位置保存到頂點集合V(x，y)中，將該起點作為當前頂點。②-2、將當前頂點與左邊界像素點集Vjx，y)中在當前頂點之後的各個像素點連線，然後計算每條連線與當前頂點所在的右側的水平直線之間的夾角。②_3、選取最大夾角對應的像素點，並將該像素點的坐標位置保存到頂點集合 V(x, y)中，再將該像素點作為當前頂點，返回步驟②-2繼續執行，直至左邊界像素點集 Vl(x, y)中的所有像素點處理完畢。②-4、判斷當前頂點與右邊界像素點集Vk(x，y)中的第一個像素點是否重合，如果是，則執行步驟②_5，否則，將右邊界像素點集Vk(x，y)中的第一個像素點作為當前頂點，並將該當前頂點的坐標位置保存到頂點集合V(x，y)中，然後執行步驟②_5。②-5、將當前頂點與右邊界像素點集Vk(X，y)中在當前頂點之後的各個像素點連線，然後計算每條連線與當前頂點所在的右側的水平直線之間的夾角。②_6、選取最小夾角對應的像素點，並將該像素點的坐標位置保存到頂點集合 V(x, y)中，再將該像素點作為當前頂點，返回步驟②-5繼續執行，直至右邊界像素點集 Ve(x, y)中的所有像素點處理完畢。②_7、判斷當前頂點與凸多邊形模型的起點是否重合，如果是，則從頂點集合V(x,y)中刪除當前頂點的坐標位置，然後執行步驟②_8，否則，直接執行步驟②-8。②_8、順序連接頂點集合V (x，y)中的各個頂點構成凸多邊形模型，頂點之間的連線為凸多邊形模型的邊。圖4給出了搜索凸多邊形模型的頂點的過程，如圖4所示，將左邊界的第一個像素點Vu作為凸多邊形模型的起點(當前頂點)，將當前頂點(Vu)與左邊界所有像素點中在其之後的各個像素點連線，計算每條連線與當前頂點(Vu)所在的右側的水平直線之間的夾角，然後選取最大夾角θu對應的像素點、作為當前頂點(U，再重複上述過程，即將當前頂點^2)與左邊界所有像素點中在其之後的各個像素點連線，計算每條連線與當前頂點(\2)所在的右側的水平直線之間的夾角，然後選取最大夾角θU對應的像素點Vu作為當前頂點(Vu)，依次類推，獲得頂點Vm和Vw ；由於當前頂點(Vw)與右邊界的第一個像素點重合，因此將當前頂點(U與右邊界所有像素點中在當前頂點(VJ之後的各個像素點連線，計算每條連線與當前頂點(U所在的右側的水平直線之間的夾角，然後選取最小夾角θ K1對應的像素點Vk2作為當前頂點(Vk2)，再重複上述過程，即將當前頂點(Vk2)與右邊界所有像素點中在其之後的各個像素點連線，計算每條連線與當前頂點(Vk2)所在的右側的水平直線之間的夾角，然後選取最小夾角θ K2對應的像素點Vk3作為當前頂點(VK3)，依次類推，獲得其他頂點。圖5給出了從圖3中搜索凸多邊形模型的頂點的過程，圖6給出了從圖3中搜索凸多邊形模型的頂點的結果，圖7給出了圖6所示的各個頂點構成的凸多邊形模型。③重複尋找凸多邊形模型中長度最短的邊，再用該長度最短的邊的兩條相鄰邊的延長線的交點的坐標位置替換頂點集合V(x，y)中該長度最短的邊對應的兩個頂點的坐標位置，直至頂點集合V(x，y)中所包含的頂點的個數為圖像校正所需的參考點的個數，獲得簡化後的多邊形模型，該簡化後的多邊形模型的頂點為圖像校正的參考點。在此具體實施例中，步驟③的具體過程為③-1、計算凸多邊形模型中每條邊的長度，尋找長度最短的邊，將該長度最短的邊作為當前邊。③_2、延長當前邊的兩條相鄰邊，使當前邊的兩條相鄰邊的延長線相交於一點。③-3、從頂點集合V(x，y)中刪除當前邊對應的兩個頂點的坐標位置，並在刪除位置處加入當前邊的兩條相鄰邊的延長線的交點的坐標位置，構成新的頂點集合V(x，y)和新的凸多邊形模型。③_4、判斷頂點集合中所包含的頂點的個數與圖像校正所需的參考點的個數是否相等，如果是，則結束邊的刪除，獲得簡化後的多邊形模型，該簡化後的多邊形模型的頂點為圖像校正的參考點，否則，返回步驟③-1繼續執行。圖8給出了從圖7所示的凸多邊形模型中刪除長度最短的邊的過程，如圖8所示， 假設圖7所示的凸多邊形模型中長度最短的邊為Eml，延長Eml的兩條相鄰邊即Emu和EmK1， 使Emu和EmK1的延長線相交於一點I ml，從頂點集合V (X，y)中刪除Eml對應的兩個頂點即Vmu 和VmK1的坐標位置，並在刪除位置處加入Emu和EmK1的延長線的交點Rml的坐標位置，構成新的頂點集合V(x，y)和新的凸多邊形模型，再重複上述過程，從新的凸多邊形模型中刪除長度最短的邊Em2，依次類推，直到頂點集合中所包含的頂點的個數為圖像校正所需的參考點的個數時，結束邊的刪除，獲得簡化後的多邊形模型，該簡化後的多邊形模型的頂點為圖像校正的參考點。圖9給出了簡化後的四邊形的示意圖，圖9所示的四邊形的四個頂點為圖像校正的參考點。
權利要求
1.一種圖像的多邊形模型的簡化方法，其特徵在於包括以下步驟①獲取一幅待處理的二值化圖像，然後以自上而下、從左到右的水平掃描方式搜索二值化圖像中每一行的第一個黑色像素點，將二值化圖像中每一行的第一個黑色像素點按掃描順序構成的集合定義為左邊界像素點集，記為\(x，y)，再以自下而上、從右到左的水平掃描方式搜索二值化圖像中每一行的最後一個黑色像素點，將二值化圖像中每一行的最後一個黑色像素點按掃描順序構成的集合定義為右邊界像素點集，記為Vk(X，y)，其中，(X，y) 表示二值化圖像中的像素點的坐標位置；②根據左邊界像素點集\(x，y)和右邊界像素點集Vk(χ，y)，構建凸多邊形模型，具體過程如下②-1、將左邊界像素點集八(x，y)中的第一個像素點作為凸多邊形模型的起點，並將該起點的坐標位置保存到頂點集合V(x，y)中，將該起點作為當前頂點；②-2、將當前頂點與左邊界像素點集Vjx，y)中在當前頂點之後的各個像素點連線，然後計算每條連線與當前頂點所在的右側的水平直線之間的夾角；②_3、選取最大夾角對應的像素點，並將該像素點的坐標位置保存到頂點集合V(x，y) 中，再將該像素點作為當前頂點，返回步驟②-2繼續執行，直至左邊界像素點集\(X，y)中的所有像素點處理完畢；②-4、判斷當前頂點與右邊界像素點集Vk (X，y)中的第一個像素點是否重合，如果是， 則執行步驟②_5，否則，將右邊界像素點集VK(x，y)中的第一個像素點作為當前頂點，並將該當前頂點的坐標位置保存到頂點集合V(x，y)中，然後執行步驟②-5;②_5、將當前頂點與右邊界像素點集％0^，7)中在當前頂點之後的各個像素點連線，然後計算每條連線與當前頂點所在的右側的水平直線之間的夾角；②_6、選取最小夾角對應的像素點，並將該像素點的坐標位置保存到頂點集合V(x，y) 中，再將該像素點作為當前頂點，返回步驟②-5繼續執行，直至右邊界像素點集VK(x，y)中的所有像素點處理完畢；②-7、判斷當前頂點與凸多邊形模型的起點是否重合，如果是，則從頂點集合V(x，y) 中刪除當前頂點的坐標位置，然後執行步驟②_8，否則，直接執行步驟②-8 ；②-8、順序連接頂點集合V(x，y)中的各個頂點構成凸多邊形模型，頂點之間的連線為凸多邊形模型的邊；③重複尋找凸多邊形模型中長度最短的邊，再用該長度最短的邊的兩條相鄰邊的延長線的交點的坐標位置替換頂點集合V(x，y)中該長度最短的邊對應的兩個頂點的坐標位置，直至頂點集合V(x，y)中所包含的頂點的個數為圖像校正所需的參考點的個數，獲得簡化後的多邊形模型，該簡化後的多邊形模型的頂點為圖像校正的參考點。
2.根據權利要求1所述的一種圖像的多邊形模型的簡化方法，其特徵在於所述的步驟 ①中左邊界像素點集Vjx，y)和右邊界像素點集Vk (x，y)的獲取過程為①-1、自上而下、從左到右對二值化圖像進行水平掃描，將二值化圖像中當前待水平掃描的行作為當前行；①-2、水平掃描當前行，在當前行中搜索到第一個黑色像素點時，結束當前行的水平掃描，並保存搜索到的第一個黑色像素點的坐標位置；①-3、將二值化圖像中待水平掃描的下一行作為當前行，返回步驟①-2繼續執行，直至二值化圖像中的最後一行處理完畢，結束二值化圖像的水平掃描；①-4、將二值化圖像中每一行的第一個黑色像素點按掃描順序構成的集合定義為左邊界像素點集，記為八(x，y)；①-5、自下而上、從右到左對二值化圖像進行水平掃描，將二值化圖像中當前待水平掃描的行作為當前行；①-6、水平掃描當前行，在當前行中搜索到第一個黑色像素點時，結束當前行的水平掃描，並保存搜索到的第一個黑色像素點的坐標位置；①-7、將二值化圖像中待水平掃描的下一行作為當前行，返回步驟①-6繼續執行，直至二值化圖像中的第一行處理完畢，結束二值化圖像的水平掃描；①-8、將二值化圖像中每一行的最後一個黑色像素點按掃描順序構成的集合定義為右邊界像素點集，記為Vk (x，y)。
3.根據權利要求1或2所述的一種圖像的多邊形模型的簡化方法，其特徵在於所述的步驟③的具體過程為③-1、計算凸多邊形模型中每條邊的長度，尋找長度最短的邊，將該長度最短的邊作為當前邊；③_2、延長當前邊的兩條相鄰邊，使當前邊的兩條相鄰邊的延長線相交於一點；③_3、從頂點集合V(x，y)中刪除當前邊對應的兩個頂點的坐標位置，並在刪除位置處加入當前邊的兩條相鄰邊的延長線的交點的坐標位置，構成新的頂點集合V(x，y)和新的凸多邊形模型；③-4、判斷頂點集合中所包含的頂點的個數與圖像校正所需的參考點的個數是否相等，如果是，則結束邊的刪除，獲得簡化後的多邊形模型，該簡化後的多邊形模型的頂點為圖像校正的參考點，否則，返回步驟③-1繼續執行。
4.根據權利要求3所述的一種圖像的多邊形模型的簡化方法，其特徵在於所述的簡化後的多邊形模型的頂點的個數為4。
全文摘要
本發明公開了一種圖像的多邊形模型的簡化方法，通過掃描已知的二值化圖像得到左邊界像素點集和右邊界像素點集，然後搜索左邊界像素點集和右邊界像素點集獲取圖像的凸多邊形模型的所有頂點，再用凸多邊形模型中長度最短的邊的兩條相鄰邊的延長線的交點替代長度最短的邊的兩個頂點，達到刪除長度最短的邊的目的，經過多次最短邊的刪除後得到頂點數與圖像校正所需的參考點數相等的多邊形模型，該多邊形模型的頂點為圖像校正的參考點，這種多邊形模型的簡化方法不僅簡便快速，而且能夠準確地獲取圖像校正所需的參考點。
文檔編號G06T5/00GK102346913SQ20111027966
公開日2012年2月8日 申請日期2011年9月20日 優先權日2011年9月20日
發明者葉慶衛, 周宇, 王丹丹, 王曉東 申請人:寧波大學