基於行程編碼的任意連通域的水平內接矩形算法及裝置的製作方法
2023-06-12 19:33:17 1
本發明涉及圖像處理技術領域，尤其涉及對目標區域求取最大內接矩形的算法及裝置。
背景技術：
在機器視覺中，對目標區域求取最大內接矩形在工業上有越來越廣泛的應用，開發出一種適用性廣，準確率高的求最大水平內接矩形圖像處理算法對於工業應用意義重大。
現有的算法中，主要針對規則形狀求感興趣區域最大水平內接矩，或針對非規則形狀求感興趣區域最大水平內接矩。
對於規則形狀求水平內接矩形比較簡單，通常有數學公式可循，如圓形、十字形等。對於非規則的感興趣區域或者任意形狀感興趣區域求內接矩形則一直是視覺領域一大研究難點，現有算法主要針對的是凸多邊形求內接矩形，對於凹多邊形並含有孔洞狀態下的任意多邊形求內接矩形算法在國內還很罕見。而工業應用中，對有孔狀態下任意多邊形求最大內接矩形是十分常見的應用，如材料切割等領域。
現有常用的算法包括遍曆法及中心擴散法，其中，遍曆法雖然對噪聲具有很強的魯棒性，但其適用範圍比較窄，對於凹多邊形以及帶有孔洞的多邊形無法正確求出最大內接矩形；中心擴散法與遍曆法相比，雖然適用範圍更廣，但其準確率不高，穩定性比較差，同時，這種算法無法針對所有的凹凸多邊形，以及帶孔洞的多邊形正確求出最大內接矩形。因此研發針對有孔狀態下的任意多邊形求最大水平內接矩形算法是非常有必要的。
技術實現要素：
針對現有技術的上述缺陷，本發明提供一種基於行程編碼的任意連通域的水平內接矩形算法及裝置，能夠求解帶孔洞的任意多邊形的最大水平內接矩形。
本發明所提供基於行程編碼的任意連通域的水平內接矩形算法包括：
獲取圖像的感興趣區域；
對圖像感興趣區域進行行程編碼；
求取編碼後感興趣區域的最大水平內接矩形。
進一步地，所述行程為同一行或同一列中連續像素點組成的一段區域，包括行行程及列行程，所述行行程以行程所在行號、行程內連續像素點的起始列及終止列標示，所述列行程以行程所在列號、行程內連續像素點的起始行及終止行標示。
進一步地，所述對圖像感興趣區域進行行程編碼的步驟包括：自感興趣區域的最小行最小列像素點開始，逐行逐列取區域內各行程的行號、起始列及終止列，並對其進行記錄，所述行程按照行順序依次進行記錄，每行按照列順序依次進行記錄；
或者，自感興趣區域的最小行最小列像素點開始，逐列逐行取區域內各行程的列號、起始行及終止行，並對其進行記錄，所述行程按照列順序依次進行記錄，每列按照行順序依次進行記錄。
進一步地，所述遍歷行程，求取編碼後感興趣區域的最大水平內接矩形的步驟包括：
取任意兩個行行程組成行程對，在列方向求交，獲得列方向的交集為候選矩形的寬，兩行行程的行差為候選矩形的高；
遍歷該行程對之間的所有行行程，若候選矩形中間存在孔洞，則修正候選矩形的寬使其避開孔洞，保持候選矩形的高不變，求得修正後候選矩形的面積並保存；
窮盡所有行程對，對所獲得候選矩形的面積進行對比，取其中面積最大的一個為感興趣區域的最大水平內接矩形；
或者：
取任意兩個列行程組成行程對，在行方向求交，獲得行方向的交集為候選矩形的高，兩列行程的列差為候選矩形的寬；
遍歷該行程對之間的所有列行程，若候選矩形中間存在孔洞，則修正候選矩形的高使其避開孔洞，保持候選矩形的寬不變，求得修正後候選矩形的面積並保存；
窮盡所有行程對，對所獲得候選矩形的面積進行對比，取其中面積最大的一個為感興趣區域的最大水平內接矩形。
進一步地，該算法還包括步驟：
在計算機中開闢一段內存用於對各行程進行記錄；
若記錄過程中，所述內存容量不夠，則重新開闢一段大於原容量的內存；
將原有內存中的數據複製至此段內存中，釋放原有內存。
本發明所提供的基於行程編碼的任意連通域的水平內接矩形裝置，包括：
區域分割模塊，用於獲取圖像的感興趣區域；
行程編碼模塊，用於對圖像感興趣區域進行行程編碼；
內接矩形求取模塊，用於遍歷行程，求取編碼後感興趣區域的最大水平內接矩形。
進一步地，所述行程為同一行或同一列中連續像素點組成的一段區域，包括行行程及列行程，所述行行程以行程所在行號、行程內連續像素點的起始列及終止列標示，所述列行程以行程所在列號、行程內連續像素點的起始行及終止行標示。
進一步地，所述行程編碼模塊自感興趣區域的最小行最小列像素點開始，逐行逐列取區域內各行程的行號、起始列及終止列，並對其進行記錄，所述行程按照行順序依次進行記錄，每行按照列順序依次進行記錄；或者，所述行程編碼模塊自感興趣區域的最小行最小列像素點開始，逐列逐行取區域內各行程的列號、起始行及終止行，並對其進行記錄，所述行程按照列順序依次進行記錄，每列按照行順序依次進行記錄。
進一步地，所述內接矩形求取模塊包括候選矩形求取模塊、候選矩形修復模塊及候選矩形對比模塊，其中：
所述候選矩形求取模塊，用於取任意兩個行行程組成行程對，在列方向求交，獲得列方向的交集為候選矩形的寬，兩行行程的行差為候選矩形的高；
所述候選矩形修復模塊，用於遍歷該行程對之間的所有行行程，若候選矩形中間存在孔洞，則修正候選矩形的寬使其避開孔洞，保持候選矩形的高不變，求得修正後候選矩形的面積並保存；
所述候選矩形對比模塊，用於窮盡所有行程對，對所獲得候選矩形的面積進行對比，取其中面積最大的一個為感興趣區域的最大水平內接矩形；
或者：
所述候選矩形求取模塊，用於取任意兩個列行程組成行程對，在行方向求交，獲得行方向的交集為候選矩形的高，兩列行程的列差為候選矩形的寬；
所述候選矩形修復模塊，用於遍歷該行程對之間的所有列行程，若候選矩形中間存在孔洞，則修正候選矩形的高使其避開孔洞，保持候選矩形的寬不變，求得修正後候選矩形的面積並保存；
所述候選矩形對比模塊，用於窮盡所有行程對，對所獲得候選矩形的面積進行對比，取其中面積最大的一個為感興趣區域的最大水平內接矩形。
進一步地，所述用於對行程進行記錄的存儲空間為計算機的內存。
本發明通過對圖像的感興趣區域採用行程編碼數據結構，減少了對計算機內存的佔用量、加快了程序運行速度；通過對感興趣區域取行程對求交集、並根據感興趣區域內部是否存在孔洞修正該交集的方式，可以獲取具有凹、凸邊或帶有孔洞的感興趣區域內所有可能存在的內接矩形，通過對上述內接矩形的對比即可獲得感興趣區域的最大內接矩形，在工業應用中更具有實際意義。
附圖說明
圖1是本發明對感興趣區域進行行程編碼示意圖；
圖2(a)是本發明求取候選矩形示意圖；
圖2(b)是本發明修正候選矩形示意圖；
圖3是本發明算法流程圖；
圖4是本發明裝置示意圖。
具體實施方式
以下結合附圖及實施例，對本發明進行詳細說明。
本發明基於行程編碼的任意連通域的水平內接矩形算法包括以下步驟：
獲取圖像的感興趣區域；
對圖像感興趣區域進行行程編碼；
遍歷行程，求取編碼後感興趣區域的最大水平內接矩形。
不同灰度值的像素點組合在一起構成圖像，由於像素點灰度值的不同使得圖像呈現出不同的圖案。圖像處理中一般先採用閾值分割等方法對圖像進行分割以獲得其感興趣區域，再對感興趣區域進行描述。現有算法中對感興趣區域通常直接用像素點表示，如開源庫OpenCV的ROI，以8位深度的灰度圖來說，若一片感興趣區域含30萬個像素點，則其內存佔用量為300000byte，約292KB，因此用像素點表示感興趣區域存在內存佔用大的弊端。而採用行程編碼方式，內存佔用量可能低至3KB，二者相差近一百倍，可見行程編碼圖像對減少程序資源的佔用是非常有效的。
為了減少內存的佔用量，本發明採用行程編碼的方式來表示感興趣區域。如圖1所示，圖中每一個方格代表一個像素點，感興趣區域100的每一行或每一列中連續像素點組成的一段區域為一個行程，每一行或每一列均可能包含若干個行程，行程分為行行程與列行程，例如圖中的111、112分別為第一行行程、第二行行程，121為第一列行程。行行程結構包含行程所在行號、行程內連續像素點的起始列與終止列；列行程包含行程所在列號、行程內連續像素點的起始行與終止行。唯一標示一個行程需提供其行號、起始列與終止列，或列號、起始行與終止行。一個行程內所包含像素的點數沒有限制，若上述行號、列號等每個分量分別用兩個字節表示，則一個行程佔用6個字節，每一片感興趣區域由有限個行程組成，行程數量遠小於像素點數，因此，採用行程編碼的方式表示圖像感興趣區域所佔用的內存要遠低於用像素點表示的方式。
對圖像感興趣區域進行行程編碼的過程，就是將感興趣區域劃分為多個行程、並對各行程予以記錄的過程，感興趣區域可以劃分為多個行行程，也可以劃分為多個列行程。參考圖3，以其劃分為多個行行程為例，該過程具體包括以下步驟：
在計算機中開闢一片內存用以對各行程進行記錄；
自感興趣區域的最小行最小列像素點開始，逐行逐列取區域內各行程的行號、起始列及終止列，並將其保存在所開闢的內存中；
記錄過程中，若所開闢內存容量不夠，則重新開闢一段大於原容量的內存，將原有內存中的數據複製至此段內存中，釋放原有內存。
其中，所有行程按照行順序依次進行記錄，每行的所有行程又按照列順序依次進行記錄。
當感興趣區域劃分為多個列行程時，則自感興趣區域的最小行最小列像素點開始，逐列逐行取區域內各行程的列號、起始行及終止行，並對其進行記錄。其中，所有行程按照列順序依次進行記錄，每列行程又按照行順序依次進行記錄。
經過上述步驟，圖像感興趣區域被編碼為行程表示方式，接下來就要通過遍歷行程的方式，對經過行程編碼後的感興趣區域求取最大內接矩形。以感興趣區域被劃分為多個行行程為例，求取其最大水平內接矩形的步驟包括：
如圖2(a)所示，取任意兩個行行程113、114組成行程對，對兩行行程在列方向求交，獲得列方向的交集為候選矩形的寬W1，兩行行程的行差為候選矩形的高H；
遍歷該行程對之間的所有行行程，若候選矩形中間存在孔洞，則修正候選矩形的寬為W2，如圖2(b)所示，使候選矩形避開孔洞，保持候選矩形的高不變，求得修正後候選矩形的面積並保存；
窮盡所有行程對，獲得所有可能存在的候選矩形，對比其面積，取其中面積最大的一個即為感興趣區域的最大水平內接矩形。
當感興趣區域劃分為多個列行程時，則取任意兩個列行程組成行程對，對兩列行程在行方向求交，獲得行方向的交集為候選矩形的高，兩列行程的列差為候選矩形的寬；
遍歷該行程對之間的所有列行程，若候選矩形中間存在孔洞，則修正候選矩形的高，使候選矩形避開孔洞，保持候選矩形的寬不變，求得修正後候選矩形的面積並保存。
窮盡候選矩形，對其其面積，最終獲得最大水平內接矩形。
如圖4所示，本發明基於行程編碼的任意連通域的水平內接矩形裝置，包括：
區域分割模塊，用於獲取圖像的感興趣區域；
行程編碼模塊，用於對圖像感興趣區域進行行程編碼；
內接矩形求取模塊，用於遍歷行程，求取編碼後感興趣區域的最大水平內接矩形。
其中，行程編碼模塊自感興趣區域的最小行最小列像素點開始，逐行逐列取區域內各行程的行號、起始列及終止列，並對其進行記錄，行程按照行順序依次進行記錄，每行按照列順序依次進行記錄；或者，行程編碼模塊自感興趣區域的最小行最小列像素點開始，逐列逐行取區域內各行程的列號、起始行及終止行，並對其進行記錄，行程按照列順序依次進行記錄，每列按照行順序依次進行記錄。
其中，用於對行程進行記錄的存儲空間為計算機的內存。
內接矩形求取模塊包括候選矩形求取模塊、候選矩形修復模塊及候選矩形對比模塊，其中：
候選矩形求取模塊，用於取任意兩個行行程組成行程對，對兩行行程在列方向求交，獲得列方向的交集為候選矩形的寬，兩行行程的行差為候選矩形的高；
候選矩形修復模塊，用於遍歷該行程對之間的所有行行程，若候選矩形中間存在孔洞，則修正候選矩形的寬，使候選矩形避開孔洞，保持候選矩形的高不變，求得修正後候選矩形的面積並保存；
候選矩形對比模塊，用於窮盡所有行程對，獲得所有可能存在的候選矩形，對比其面積，取其中面積最大的一個為感興趣區域的最大水平內接矩形。
或者：
候選矩形求取模塊，用於取任意兩個列行程組成行程對，對兩列行程在行方向求交，獲得行方向交集為候選矩形的高，兩列行程的列差為候選矩形的寬；
候選矩形修復模塊，用於遍歷該行程對之間的所有列行程，若候選矩形中間存在孔洞，則修正候選矩形的高，使候選矩形避開孔洞，保持候選矩形的寬不變，求得修正後候選矩形的面積並保存；
候選矩形對比模塊，用於窮盡所有行程對，獲得所有可能存在的候選矩形，對比其面積，取其中面積最大的一個為感興趣區域的最大水平內接矩形。
本發明中圖像感興趣區域經行程編碼後，表示圖像的最小單位為行程，每個行程可包含的像素點數無限制，因此感興趣區域的行程數必然比像素點數目少，與現有技術通過遍歷所有像素點獲得其最大水平內接矩形相比，遍歷行程則變得更簡單，執行算法耗時也將減少。同時，如前所述，進行行程編碼後，內存佔用少，使得該算法更適用於對資源有一定限制的嵌入式平臺。
本發明通過對感興趣區域取行程對求交集、並根據感興趣區域內部是否存在孔洞修正該交集、最終獲得感興趣區域內所有可能存在的內接矩形，並對比得出感興趣區域的最大水平內接矩形，對於規則、凸、凹、存在孔洞等任意多邊形均能夠準確求取最大水平內接矩，解決了現有算法無法適用於存在孔洞的任意多邊形內接矩形求取，應用單一的問題，穩定性高，能夠滿足工業現場的各種需求，促進相關工業領域的智能化發展。