邊緣搜尋

邊緣搜尋是按最左搜尋進行的,即:先找到物體的一個邊緣點,然後按順時針方向搜尋它的8個鄰點得到下一個邊緣點,如此搜尋下去,得到一個閉合的點序列,即物體的邊緣。在搜尋的過程中,還要判斷一個前景顏色的點是物體的邊緣點還是內點,這可以通過分析邊緣點的特徵來實現。

基本介紹

• 中文名：邊緣搜尋
• 外文名：edge searching
• 搜尋方法：按最左搜尋進行
• 判斷邊緣極點：通過分析邊緣點的特徵實現
• 套用領域：圖像處理和計算機視覺
• 套用學科：計算機科學、通信工程、儀器科學

簡介

邊緣搜尋

在數字圖象處理和分析中，經常涉及到圖象中物體邊緣的提取。一般情況下均假設圖象為二值圖象，即背景的顏色標號0，前景(物體)的顏色標號為1。

傳統的圖象邊緣搜尋是按最左搜尋進行的，即:先找到物體的一個邊緣點，然後按順時針方向搜尋它的8個鄰點得到下一個邊緣點，如此搜尋下去，得到一個閉合的點序列，即物體的邊緣。在搜尋的過程中，還要判斷一個前景顏色的點是物體的邊緣點還是內點，這可以通過分析邊緣點的特徵來實現。

邊緣極點的判斷

在邊緣搜尋的過程中，對於前景顏色的點，需要判斷它是某個物體的內點還是另一個物體的邊緣點。可以通過區分物體邊緣點的類型來判斷。

如圖所示，其中的虛線為兩個掃描線，P₀，P₁，P₂，P₃為掃描到的物體邊緣點。其中，P₀為真正的邊緣點，掃描時經過這樣的點則進入或離開物體:P₃為邊緣極點，掃描時經過這樣的點可以跳過不作處理:對於P₁和P₂，情況要複雜一些。如果忽略水平方向上P₁和P₂之間的點，使P₁和P₂相重合則可以表示一個邊緣點:故可以認為P₁以及P₁到P₂之間的點為邊緣極點，而P₂為邊緣點。

在圖4中，P₁和P₂以及P₁和P₂之間的點都是邊緣極點。總之，聲遇到這種情況時，要將其中水平線段上的邊緣點標記為邊緣極點，再根據兩個端點的情況標記端點;主要是根據其周圍同色的點的方向標號進行判斷。

邊緣搜尋算法

圖象的拓寬

在對二維數字圖象進行逐點處理時，經常需要判斷某個點是否為此幅圖象的邊界點。由於圖象邊界點的鄰點的個數與內部點是不同的，所以在邊緣搜尋算法中，往往還要進行一些特殊的處理。為了避免這一點，我們將圖象的邊界各展寬一個象素，新的邊界點的顏色設為背景色。假設原圖象的大小為Widhth*Height，拓寬後的大小為（Widhth+2)*(Height+2)，新的邊界點顏色設為0，如圖所示。

圖像的拓寬

這樣，在遍歷圖象時，就不必對原圖象的邊界點進行特殊的判斷和處理。

算法描述

下面給出圖象邊緣搜尋算法的描述:

0)置當前顏色Color為背景色0，將Color壓入堆疊:

1)從上到下，從左到右遍歷圖象(包括拓寬後的邊界);

2)若當前點P是未搜尋過的前景點，則:

2.1)若P點的顏色等於當前顏色Color，則跳過;

2.2)否則以P點為起始點，搜尋並標記一個物體的邊緣;

3)若當前點P為己搜尋過的前景點，且不是邊緣極點，則:

3.1)若P點的顏色和棧頂的顏色相同，則彈出棧頂的顏色:然後再彈出棧頂的顏色到Color中:

3.2)若P點的顏色和棧頂的顏色不同，則將P點的顏色壓入堆疊，並置當前顏色Color為P點的顏色:

4)若當前點P為已搜尋過的前景點，且是孤立點，則跳過;

5)若當前點P為己搜尋過的前景點，且是邊緣極點，則跳過:

6)若當前點P為背景點，則跳過。

其中，步驟2.2)的算法為:

2.1)以當前點P作為起始點，根據方向標號為0，1，2，3的4個鄰點的顏色確定P點的類型並做標記:取和P點同色的下一個邊緣點作為當前點，其方向記為Dir:

2.2)掃描方向標號Dir2為6+Dir，7+Dir，Dir，Dir+1，Dir+2(mod8)的點，尋找下一個邊緣點:根據Dir和Dir2標記當前點的類型:置Dir為Dir2;

2.3)重複2.2)直到當前點的坐標Pos等於起始點P的坐標。

小角度邊緣搜尋

固然，在運動自適應的去隔行算法中，正確的區分靜止和運動很重要。但是，對於運動圖像中邊緣信息的準確檢測，並在空間插值濾波器中合理套用邊緣信息對提高圖像質量也相當關鍵。

基於邊緣的行平均(ELA)算法在去隔行中得到廣泛套用，但是，它的致命缺陷是對水平邊緣的檢測能力很弱，只能檢測45°、90°和135°邊緣，對於小角度邊緣則無能為力。為提高水平邊緣的檢測能力，小角度邊緣搜尋改進算法主要包括兩個方面:(1)增大搜尋範圍(半徑)，左右最大各搜尋8個點，並且採用自適應搜尋的設計方法，從而減小硬體的複雜度;(2)增加對邊緣方向上相鄰像素的考慮，實現半像素精度，提高邊緣檢測的精度。

小角度邊緣搜尋

邊緣搜尋示意如圖所示，其中黑點代表待插補的像素x(i，j)，上下兩行的像素點的對角線方向代表可能的邊緣方向。

其基本原理是:通過比較對角線上的像素絕對差值判斷對角線對應像素與待插補像素的相關性，絕對差值越小相關性越大，最小差值對應的方向就是邊緣方向。在計算中採用並行處理架構，將上下行的對角像素分為3部分:

(1)中間部分，只有90°一個方向的兩個像素x(i，j-1)，x(i，j+1);

(2)向左搜尋部分，包括j-1行上x(i，j-1)右邊的像素和j+1行上x(i，j+1)左邊的像素;

(3)向右搜尋部分，包括j-1行上x(i，j-1)左邊的像素和j+1行上x(i，j+1)右邊的像素.同時計算這三部分對角像素的絕對差值，分別得到中間部分絕對差值D_m、左邊部分絕對差值L₁，L₂，…，L₈和右邊部分絕對差值R₁，R₂，…，R₈。即

其中，Y(i，j)表示像素x(i，j)的亮度分量值，其它同義。

在小角度邊緣搜尋中，為減少計算量和硬體資源的消耗，採取自適應搜尋半徑的檢測方法，在進行向左或向右順序搜尋的過程中每一級計算結束後都要將差值與上一級進行比較(第一級的差值與Dm進行比較)，如果絕對差值一直保持減小趨勢則繼續進行搜尋，直到tap=8，如果出現相反的變化趨勢，則停止搜尋.然後比較這些差值選擇出最小的絕對差值D，此最小差值對應的對角方向就是大致的邊緣方向.D=min(D_m，L₁，…，L_n，R₁，…，R_n)。