[發明專利]一種閉合路徑的搜索方法

有效

• 申請號: 201110216333.4
• 申請日: 2011-07-29
• 公開（公告）號: CN102279975A
• 公開（公告）日: 2011-12-14
• 發明（設計）人: 安凱;辛明瑞
• 申請（專利權）人: 中國航天科技集團公司第五研究院第五一三研究所
• 主分類號: G06T7/00
• 分類號: G06T7/00
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 李愛英;付雷杰

技術領域

本發明涉及一種路徑規劃方法，具體涉及一種閉合路徑的搜索方法。

背景技術

自動光學檢測技術是用光學成像技術獲取被檢測物的數字圖像，然后通過數字圖像處理技術實現對被檢測物的檢驗、分析和判斷。為了保證空間電子設備電路模塊的長壽命和高可靠性，工業界現已廣泛采用自動光學檢測技術對電路板進行質量檢測。為了提高檢測效率，減少器件損耗，縮短檢測的取像時間，需要對自動光學檢測的取像路徑進行規劃，確定一條恰經過每個被檢測物一次的閉合路徑。這種路徑規劃問題屬于典型的TSP(旅行商)問題，目的是為旅行者尋求一條由起點城市出發，經過所有給定城市，最后回到原出發城市的最短路徑。TSP路徑最小化問題可應用于許多領域，如車輛路由，計算機配線，通信網絡頻率分配以及電網布線等。

常用的TSP路徑最小化的方法有最近鄰方法、插入法和隨機搜索算法。最近鄰方法為隨機選取一個城市作為路徑起點，在路徑的末端總是選擇未光顧城市中與末端城市距離最近的加入路徑中，重復這種模式，直至將所有城市都納入路徑中。插入法以任意一個城市作為路徑起點，在選擇下一城市時，使插入代價最小。隨著計算機運算速度的提高，解決TSP問題可利用隨機搜索算法，如模擬退火算法、遺傳算法、蟻群算法以及這些算法的結合和/或改進。但是，隨機搜索算法不考慮目標點的幾何分布特征，缺乏“對癥下藥”的處理措施，僅靠運算快而窮追猛打，在遇到大樣本的情形下往往收斂速度不佳，甚至常常面臨連一條Hamilton回路都找不到的尷尬?？梢?，現有的閉合路徑規劃方法都沒有將目標點作為一個整體來看待，都未考慮各個目標點之間的關聯，具有很強的盲目性，效率低下且效果不佳。

發明內容

鑒于此，本發明提出一種全新的閉合路徑的搜索方法，能夠消除搜索過程中的盲目性，提高搜索效率。

本發明的閉合路徑的搜索方法包含：

步驟一、將被檢測物構成的點集確定為目標點集；

步驟二、搜索目標點集的最外層凸包和次外層凸包；

步驟三、合并最外層凸包和次外層凸包，以得到最終的最外層閉合路徑，具體包含：

a)搜索一點P以得到最外層閉合路徑和重新確定的次外層凸包：在最外層凸包上搜索一邊t₁t₂，在次外層凸包上搜索一點P，其中點P位于兩條分別經過點t₁和點t₂且垂直于邊t₁t₂的平行線之間，且與最外層凸包上的其余邊以及次外層凸包上的其余點相比，點P到邊t₁t₂的距離最短；如果點P到邊t₁t₂的距離小于邊t₁t₂的長度的一半，則將點P納入邊t₁t₂，得到一最外層閉合路徑；以得到的最外層閉合路徑所包圍的點為搜索范圍進行凸包搜索，將搜索到的凸包作為重新確定的次外層凸包；

b)對得到的最外層閉合路徑和重新確定的次外層凸包執行步驟a)，并重復同樣的過程，直至在重新確定的次外層凸包上搜索不到符合條件的點P或無法形成次外層凸包為止，得到最終的最外層閉合路徑；

步驟四、將最終的最外層閉合路徑所包圍的點確定為目標點集，執行步驟一～二，得到最終的次外層閉合路徑；重復同樣的過程，得到一組最終的閉合路徑，且該組最終的閉合路徑由外到內依次嵌套；

步驟五、將該組最終的閉合路徑連成一條閉合路徑；

其中，在搜索目標點集的最外層凸包和次外層凸包時，當目標點集中的點的個數小于3時，根據距離最短原則將目標點集中的點納入與其相鄰的閉合路徑，以形成最終的最內層閉合路徑，并執行步驟五；其中距離最短原則為判斷一點到包圍該點的多邊形的各條邊的距離，將該點納入使該距離最短的邊。

本發明提供的閉合路徑的搜索方法引入了圖論中的凸包理論，依據目標點的幾何分布特征，體現了各個目標點之間的關聯，提高了搜索效率，降低了搜索成本，顯著地消除了搜索過程中的盲目性。

附圖說明

圖1為被檢測物構成的點集及其最外層凸包和第二層凸包。

圖2為將第二層凸包上的點納入最外層凸包。

圖3為搜索過程中形成的最外層閉合路徑和新的第二層凸包。

圖4為由外至內層層嵌套的閉合路徑組。

圖5為將相鄰的兩層閉合路徑打通。

圖6為根據本發明的方法搜索得到的閉合路徑。

具體實施方式