中文 4440 字 畢業(yè)設計 /論文 外 文 文 獻 翻 譯 系 別 計算機與電子系 專 業(yè) 班 級 計算機科學與技術 姓 名 原 文 出 處 Digital Image Processing 2/E 評 分 指 導 教 師 2012 年 3 月 1 圖像分割 前一章的資料使我們所研究的圖像處理方法開始發(fā)生了轉變。從輸人輸出均為圖像的處理方法轉變?yōu)檩斎藶閳D像而輸出為從這些圖像中提取出來的屬性的處理方法這方面在 1.1節(jié)中定義過 )。圖像分割是這一方向的另一主要步驟。 分割將圖像細分為構成它的子區(qū)域或對象。分割的程度取決于要解決的問題。就是說當感興趣的對象已經(jīng)被分離出來時就停止分割。例如，在電子元件的自動檢測方面，我們關注的是分析產(chǎn)品的圖像，檢測是否存在特定的異常狀態(tài)，比如，缺失的元件或斷裂的連接線路。超過識別這此元件所需的 分割是沒有意義的。 異常圖像的分割是圖像處理中最困難的任務之一。精確的分割決定著計算分析過程的成敗。因此，應該特別的關注分割的穩(wěn)定性。在某些情況下，比如工業(yè)檢測應用，至少有可能對環(huán)境進行適度控制的檢測。有經(jīng)驗的圖像處理系統(tǒng)設計師總是將相當大的注意力放在這類可能性上。在其他應用方面，比如自動目標采集，系統(tǒng)設計者無法對環(huán)境進行控制。所以，通常的方法是將注意力集中于傳感器類型的選擇上，這樣可以增強獲取所關注對象的能力，從而減少圖像無關細節(jié)的影響。一個很好的例子就是，軍方利用紅外線圖像發(fā)現(xiàn)有很強熱信號的目標 ，比如移動中的裝備和部隊。 圖像分割算法一般是基于亮度值的不連續(xù)性和相似性兩個基本特性之一。第一類性質(zhì)的應用途徑是基于亮度的不連續(xù)變化分割圖像，比如圖像的邊緣。第二類的主要應用途徑是依據(jù)事先制定的準則將圖像分割為相似的區(qū)域，門限處理、區(qū)域生長、區(qū)域分離和聚合都是這類方法的實例。 本章中，我們將對剛剛提到的兩類特性各討論一些方法。我們先從適合于檢測灰度級的不連續(xù)性的方法展開，如點、線和邊緣。特別是邊緣檢測近年來已經(jīng)成為分割算法的主題。除了邊緣檢測本身，我們還會討論一些連接邊緣線段和把邊緣“組裝 ”為邊界的方法。關于邊緣檢測的討論將在介紹了各種門限處理技術之后進行。門限處理也是一種人們普遍關注的用于分割處理的基礎性方法，特別是在速度因素占重要地位的應用中。關于門限處理的討論將在幾種面向區(qū)域的分割方法展開的討論之后進行。之后，我們將討論一種稱為分水嶺分割法的形態(tài)學 2 圖像分割方法。這種方法特別具有吸引力，因為它將本章第一部分提到的幾種分割屬性技術結合起來了。我們將以圖像分割的應用方面進行討論來結束本章。 10.1 間斷檢測 在本節(jié)中，我們介紹幾種用于檢測數(shù)字圖像中三種基本的灰度級間斷技術 :點、線和邊緣。尋找 間斷最一般的方法是以 3.5節(jié)中描述的方式對整幅圖像使用一個模板進行檢測。圖 10-1 所示的 3x3 模板，這一過程包括計算模板所包圍區(qū)域內(nèi)灰度級與模板系數(shù)的乘積之和。就是說，關于式 (3.5.3)，在圖像中任意點的模板響應由下列公式給出： 9199.2211iw iz izwzwzwR（ 10.1.1） 1W 2W 3W 4W 5W 6W 7W 8W 9W 圖 10-1 一個一般的 3*3 模板 這里 Zi是與模板系數(shù) Wi相聯(lián)系的像素的灰度級。照例，模板響應是它的中心位置。有關執(zhí)行模板操作的細節(jié)在 3.5節(jié)中討論。 10.1.1 點檢測 在一幅圖像中，孤立點的檢測在理論上是簡單的。使用如圖 10-2(a)所示的模板，如果 |R| T (10.1.2) 我們說在模板中心的位置上已經(jīng)檢測到一個點。這里 T是一個非負門限， R由式(10.1.1)給出。基本上，這個公式是測量中心點和它的相鄰點之間加權的差值?；舅枷刖褪?:如果一個孤立的點 (此點的灰度級與其背景的差異相當大并且它所在的位置是一個均勻的或近似均勻的區(qū)域 )與它周圍的點很不相同，則很容易被這類模板檢測到。注意，圖 10-2(a)中的模板同圖 3.39(d)中給出的模板在拉 3 普拉斯操作方而是相同的。嚴格地講，這里強調(diào)的是點的檢測。即我們著重考慮的差別是那些足以識別為孤立點的差異 (由 T決定 )。注意， 模板系數(shù)之和為零表示在灰度級為常數(shù)的區(qū)域，模板響應為零。 -1 -1 -1 -1 8 -1 -1 -1 -1 （ a） （ b） （ c） （ d） 圖 10-2 （ a）點檢測模板，（ b）帶有通孔的渦輪葉片的 X 射線，（ c）點檢測的 結果，（ d）使用式（ 10.1.2）得到的結果（原圖由 X-TEK 系統(tǒng)公司提供） 例 10.1圖像中孤立點的檢瀏 我們以圖 10-2(b)功為輔助說 明如何從一幅圖中將孤立點分割出來 .這幅 X射線圖顯示了一個帶有通孔的噴氣發(fā)動抓渦槍葉片，通孔位于圈像的右上象限。在孔中只嵌有一個黑色像素。圖 10-2(c)是將點檢測模板應用于 X射線圖像后得到的結果 .圖 10-2(d)顯示了當 T取圖 10-2(c)中像素最高絕襯值的 90%時，應用式 (10.1.2)所得的結果 (門限選擇將在 10.3 節(jié)中詳細討論 )。圖中的這個單一的像素清晰可見 (這個像素被人為放大以便印刷后可以看到 )。由于這類檢測是基于單像素間斷，并且檢測器模板的區(qū)域有一個均勻的背景，所以這個檢測過程是相當有專用性的當這 一條件不能滿足時，本章中計論的其他方法會更適合檢測灰度級間斷 10.1.2 線檢測 復雜程度更高一級的檢測是線檢測，考慮圖 10-3 中顯示的模板。如果第 l個模板在圖像中移動，這個模板將對水平方向的線條 (一個像素寬度 )有更強的響 4 應。在一個不變的背景上，當線條經(jīng)過模板的中間一行時會產(chǎn)生響應的最大值。畫一個元素為 1的簡單陣列，并且使具有不同灰度級 (如 5)的一行水平穿過陣列，可以很容易驗證這一點。同樣的實驗可以顯示出圖 10-3中的第 2個模板對于 45方向線有最佳響應 ;第 3個模板對于垂直線有最佳響應 ;第 4個模板對于 -45方向線有最佳響應 ;這些方向也可以通過注釋每個模板的優(yōu)選方向來設置，即在這些方向上用比別的方向更大的系數(shù) (為 2)設置權值。注意每個模板系數(shù)相加的總和為零，表示在灰度級恒定的區(qū)域來自模板的響應為零。 Horizontal +45 Vertical -45 圖 10-3 線模板 令 R1， R2， R3 和 R4。從左到右代表圖 10-3中模板的響應，這里 R的值由式(10.1.1)給出。 假設 4個模板分別應用于一幅圖像，在圖像中心的點，如果 |Ri|Rj| , j i，則此點被認為與在模板 i方向上的線更相關。例如，如果在圖中的一點有|Ri|Rj| ,j=2,3,4，我們說此特定點與水平線有更大的聯(lián)系。 換句話說，我們可能對檢測特定方向上的線感興趣。在這種情況下，我們應使用與這一方向有關的模板，并設置該模板的輸出門限，如式 (10.1.2)所示。換句話說，如果我們對檢測圖像中由給定模板定義的方向上的所有線感興趣 .只需要簡單地通過整幅圖像運行模板，并對 得到的結果的絕對值設置門限即可。留下的點是有最強響應的點。對于一個像素寬度的線，這些響應最靠近模板定義的對應方向。下列例子說明了這一過程。 例 10.2特定方向上的線檢測 圖 10-4(a)顯示了一幅電路接線模板的數(shù)字化 (二值的 )圖像。假設我們要找到一個像素寬度的并且方向為 -45的線條?；谶@個假設，使用圖 10-3中最后一個模板。圖 10-4(b)顯示了得到的結果的絕對值。注意，圖像中所有水平和垂直的部分都被除去了。并且在圖 10-4(b)中所有原圖中接近 -45方向的部分產(chǎn)生了最強響應。 -1 2 -1 2 2 -1 -1 -1 -1 -1 2 -1 2 -1 2 -1 2 -1 -1 2 -1 -1 -1 -1 2 -1 -1 -1 2 -1 2 -1 -1 2 -1 -1 2 （ a） （ b） （ c） 圖 10-4 線檢測的說明。（ a）二進制電路接線模板，（ b）使用 -45線檢測器 處理后得到的絕對值，（ c）對圖像（ b）設置門限得到的結果 為了決定哪一條線擬合模板最好，只需要簡單地對圖像設置門限。圖 10-4(c)顯示了使門限等于圖像中最大值后得到的結果。對于與這個例子類似的應用，讓門限等于最大值是一個好的選擇，因為輸入圖像是二值的，并且我們要尋找的是最強響應。圖 10-4(c)顯示了在白色區(qū)所有通 過門限檢測的點。此時，這一過程只提取了一個像素寬且方向為 -45的線段 (圖像中在左上象限中也有此方向上的圖像部分，但寬度不是一個像素 )。圖 10-4(c)中顯示的孤立點是對于模板也有相同強度響應的點。在原圖中，這些點和與它們緊接著的相鄰點，是用模板在這些孤立位置上生成最大響應的方法來定向的。這些孤立點也可以使用圖10-2(a)中的模板進行檢測，然后刪除，或者使用下一章中討論的形態(tài)學腐蝕法刪除。 10.1.3 邊緣檢側 盡管在任何關于分割的討論中，點和線檢測都是很重要的，但是邊緣檢測對 3 于灰度級間斷的檢測是 最為普遍的檢測方法。本節(jié)中，我們討論實現(xiàn)一階和二階數(shù)字導數(shù)檢測一幅圖像中邊緣的方法。在 3.7 節(jié)介紹圖像增強的內(nèi)容中介紹過這些導數(shù)。本節(jié)的重點將放在邊緣檢測的特性上。某些前面介紹的概念在這里為了敘述的連續(xù)性將進行簡要的重述。 基本說明 在 3.7.1節(jié)中我們非正式地介紹過邊緣。本節(jié)中我們更進一步地了解數(shù)字化邊緣的概念。直觀上，一條邊緣是一組相連的像素集合。這些像素位于兩個區(qū)域的邊界上。然而，我們已經(jīng)在 2.5.2節(jié)中用一定的篇幅解釋了一條邊緣和一條邊界的區(qū)別。從根本上講，如我們將要看到的，一條邊緣是一個“ 局部”概念，而由于其定義的方式，一個區(qū)域的邊界是一個更具有整體性的概念。給邊緣下一個更合理的定義需要具有以某種有意義的方式測量灰度級躍變的能力。 我們先從直觀上對邊緣建模開始。這樣做可以將我們引領至一個能測量灰度級有意義的躍變的形式體系中。從感覺上說，一條理想的邊緣具有如圖 10-5(a)所示模型的特性。依據(jù)這個模型生成的完美邊緣是一組相連的像素的集合 (此處為在垂直方向上 )，每個像素都處在灰度級躍變的一個垂直的臺階上 (如圖形中所示的水平剖面圖 )。 實際上，光學系統(tǒng)、取樣和其他圖像采集的不完善性使得到的 邊緣是模糊的，模糊的程度取決于諸如圖像采集系統(tǒng)的性能、取樣率和獲得圖像的照明條件等因素。結果，邊緣被更精確地模擬成具有“類斜面”的剖面，如圖 10-5(b)所示。斜坡部分與邊緣的模糊程度成比例。在這個模型中，不再有細線 (一個像素寬的線條 )。相反，現(xiàn)在邊緣的點是包含于斜坡中的任意點，并且邊緣成為一組彼此相連接的點集。邊緣的“寬度 ” 取決于從初始灰度級躍變到最終灰度級的斜坡的長度。這個長度又取決于斜度，斜度又取決于模糊程度。這使我們明白 :模糊的邊緣使其變粗而清晰的邊緣使其變得較細。 圖 10-6(a)顯示的圖 像是從圖 10-5(b)的放大特寫中提取出來的。圖 10-6(b)顯示了兩個區(qū)域之間邊緣的一條水平的灰度級剖面線。這個圖形也顯示出灰度級剖面線的一階和二階導數(shù)。當我們沿著剖面線從左到右經(jīng)過時，在進人和離開斜面的變化點，一階導數(shù)為正。在灰度級不變的區(qū)域一階導數(shù)為零。在邊緣與黑色一邊相關的躍變點二階導數(shù)為正，在邊緣與亮色一邊相關的躍變點二階導數(shù)為負，沿著斜坡和灰度為常數(shù)的區(qū)域為零。在圖 10-6(b)中導數(shù)的符號在從亮到暗 4 的躍變邊緣處取反。 （ a） （ b） 圖 10-5 （ a）理想的數(shù)字邊緣模型，（ b）斜坡數(shù)字邊緣模型。 斜坡部分與邊緣的模糊程度成正比 圖 10-6 (a)由一條垂直邊緣分開的兩個不同區(qū)域 ,(b)邊界附近的細 節(jié)顯示了一個灰度級剖面圖和一階與二階導數(shù)的剖面圖 由這些現(xiàn)象我們可以得到的結論是 :一階導數(shù)可以用于檢測圖像中的一個點是否是邊緣的點 (也就是判斷一個點是否在斜坡上 )。同樣，二階導數(shù)的符號可以用于判斷一個邊緣像素是在邊緣亮的一邊還是暗的一邊。我們注意到圍繞一條邊緣，二階導數(shù)的兩條附加性質(zhì) (1)對圖像中的每 條邊緣二階導數(shù)生成兩個值 (一個 5 不希望得到的特點 );(2)一條連接二階導數(shù)正極值和負極值的虛構直線將在邊緣中點附近穿過零點。將在本節(jié)后面說明，二階導數(shù)的這個過零點的性質(zhì)對于確定粗邊線的中心非常有用。 最后，注意到某些邊緣模型利用了在進人和離開斜坡地方的平滑過渡 (習題10.5)。然而，我們在接下來的討論中將得出同樣的結論。而且，這一點從我們使用局部檢測進行處理就可以很明顯地看出 (因此， 2.5.2 節(jié)中對于邊緣的局部性質(zhì)進行了說明 )。 盡管到此為止我們的注意力被限制在一維水平剖面線范圍內(nèi)，但同樣的結 論可以應用于圖像中的任何方向上。我們僅僅定義了一條與任何需要考察的點所在的邊緣方向相垂直的剖面線，并如前面討論的那樣，對結果進行了解釋。 注：出自 Digital Image Processing 2nd Edition . Prentice Hall 1 Image Segmentation The material in the previous chapter began a transition from image processing methods whose input and output are images, to methods in which the inputs are images, but the outputs are attributes extracted from those images (in the sense defined is Section 1.1). Segmentation is another major step in that direction. Segmentation subdivides an image into its constituent regions or objects. The level to which the subdivision is carried depends on the problem being solved. That is, segmentation should stop when the objects of interest in an application have been isolated. For example, in the automated inspection of electronic assemblies, interest lies in analyzing images of the products with the objective of determining the presence or absence of specific anomalies, such as missing components or broken connection paths. There is no point in carrying segmentation past the level of detail required to identify those elements. Segmentation of nontrivial images is one of the most difficult tasks in image processing. Segmentation accuracy determines the eventual success or failure of computerized analysis procedures. For this reason, considerable care should be taken to improve the probability of rugged segmentation. In some situations , such as industrial inspection applications, at least some measure of control over the environment is possible at times. The experienced image processing system designer invariably pays considerable attention to such opportunities. In other applications, such as autonomous target acquisition, the system designer has no control of the environment. Then the usual approach is to focus on selecting the types of sensors most likely to enhance the objects of interest while diminishing the contribution of irrelevant image detail. A good example is the use of infrared imaging by the military to detect objects with strong heat signatures , such as equipment and troops in motion. Image segmentation algorithms generally are based on one of two basic properties of intensity values: discontinuity and similarity. In the first category, the approach is to partition an image based on abrupt changes in intensity, such as edges in an image. The principal approaches in the second category are based on 2 partitioning an image into regions that are similar according to a set of predefined criteria. Thresholding, region growing, and region splitting and merging are examples of methods in this category. In this chapter we discuss a number of approaches in the two categories just mentioned. We begin the development with methods suitable for detecting gray level discontinuities such as points, lines, and edges. Edge detection in particular has been a staple of segmentation algorithms for many years. In addition to edge detection per se, we also discuss methods for connecting edge segments and for assembling edges into region boundaries. The discussion on edge detection is followed by the introduction of various thresholding techniques . Thresholding also is a fundamental approach to segmentation that enjoys a significant degree of popularity, especially in applications where speed is an important factor. The discussion on thresholding is followed by the development of several region-oriented segmentation approaches. We then discuss a morphological approach to segmentation called watershed segmentation. This approach is particularly attractive because it combines several of the positive attributes of segmentation based on the techniques presented in the first part of the chapter. We conclude the chapter with a discussion on the use of motion cues for image segmentation. 10.1Detection of Discontinuities In this section we present several techniques for detecting the three basic types of gray-level discontinuities in a digital image: points, lines, and edges. The most common way to look for discontinuities is to run a mask through the image in the manner described in Section 3.5. For the 3 x 3 mask shown in Fig. 10.1, this procedure involves computing the sum of products of the coefficients with the gray levels contained in the region encompassed by the mask. That is. with reference to Eq. (3.5-3). the response of the mask at anv point in the image is given by 3 9199.2211iw iz izwzwzwR（ 10.1.1） 1W 2W 3W 4W 5W 6W 7W 8W 9W FIGURE 10.1 A general 3 x 3 mask. where z; is the gray level of the pixel associated with mask coefficient Wi. As usual, the response of the mask is defined with respect to its center location. The details for implementing mask operations are discussed in Section 3.5. 10.1.1 Point Detection The detection of isolated points in an image. is straightforward in principle. Using the mask shown in Fig. 10.2(a), we say that a point has been detected at the location on which the mask is centered if |R| T (10.1.2) where T is a nonnegative threshold and R is given by Eq. (10.1-1). Basically,this formulation measures the weighted differences between the center point and its neighbors. The idea is that an isolated point (a point whose gray level is significantly different from its background and which is located in a homogeneous or nearly homogeneous area) will be quite different from its surroundings, and thus be easily detectable by this type of mask. Note that the mask in Fig. 10.2(a) is the same as the mask shown in Fig. 3.39(d) in connection with Laplacian operations. However, the emphasis here is strictly on the detection of points. That is, the only differences that are considered of interest are those large enough (as determined by T, to be considered isolated points. Note that the mask coefficients sum to zero, indicating that the mask response will be zero in areas of constant gray level. 4 -1 -1 -1 -1 8 -1 -1 -1 -1 （ a） （ b） （ c） （ d） FIGURE 10.2(a) Pointdetection mask. (b) X-ray image of a turbine blade with a porosity. (c) Result of point detection. (d) Result of using Eq. (10.1-2).(Original image courtesy of X-TEK Systems Ltd.) EXAMPLE 10.1:Detection of isolated points in an image. We illustrate segmentation of isolated points from an image with the aid of Fig. 10.2(6), which shows an X-ray image of a jet-engine turbine blade with a porosity in the upper, right quadrant of the image. There is a single black pixel embedded within the porosity. Figure 10.2(c) is the result of applying the point detector mask to the X-ray image, and Fig. 10.2(d) shows the result of using Eq. (10.1.2) with T equal to 90% of the highest absolute pixel value of the image in Fig. 10.2(c). (Threshold selection is discussed in detail in Section 10.3) The single pixel is clearly visible in this image (the pixel was enlarged manually so that it would be visible after printing). This -type of detection process is rather specialized because it is based on single-pixel discontinuities that have a homogeneous background in the area of the detector mask. When this condition is not satisfied, other methods discussed in this chapter are more suitable for detecting gray-level discontinuities. 5 10.1.2 Line Detection The next level of complexity is line detection. Consider the masks shown in Fig. 10.3. If the first mask were moved around an image, it would respond more strongly to lines (one pixel thick) oriented horizontally. With a constant background, the maximum response would result when the line passed through the middle row of the mask. This is easily verified by sketching a simple array of 1s with a line of a different gray level (say, 5s) running horizontally through the array. A similar experiment would reveal that the second mask in Fig. 10.3 responds best to lines oriented at +450; the third mask to vertical lines; and the fourth mask to lines in the -450 direction . These directions can be established also by noting that the preferred direction of each mask is weighted with a larger coefficient (i.e., 2) than other possible directions. Note that the coefficients in each mask sum to zero, indicating a zero response from the masks in areas of constant gray level. Horizontal +45 Vertical -45 FIGURE 10.3 Line masks. Let R1, R2, R3, and R4 denote the responses of the masks in Fig. 10.3, from left to right, where the Rs are given by Eq. (10.1-1). Suppose that the four masks are run individually through an image. If, at a certain point in the image, |Ri| |Rj|, for all j i, that point is said to be more likely associated with a line in the direction of mask i. For example, if at a point in the image, |Ri|Rj|, for j = 2, 3. 4, that particular point is said to be more likely associated with a horizontal line. Alternatively, we may be interested in detecting lines in a specified direction. In this case, we would use the mask associated with that direction and threshold its output, as in Eq . (10.1.2). In other words, if we are interested in detecting all the lines in an image in the direction defined by a given mask, we simply run the mask through the image and threshold the absolute value of the result. The points that are left are the strongest responses, which, -1 2 -1 -1 2 2 -1 -1 -1 -1 2 -1 2 -1 -1 2 -1 -1 -1 -1 -1 2 -1 2 -1 2 -1 2 -1 -1 2 -1 -1 -1 -1 2 6 for lines one pixel thick, correspond closest to the direction defined by the mask. The following example illustrates this procedure. EXAMPLE 10.2:Detection of lines in a specified direction Figure 10.4(a) shows a digitized (binary) portion of a wire-bond mask for an electronic circuit. Suppose that we are interested in finding all the lines that are one pixel thick and are oriented at-45. For this purpose, we use the last mask shown in Fig. 10.3.The absolute value of the result is shown in Fig. 10.4(b). Note that all vertical and horizontal components of the image were eliminated, and that the components of the original image that tend toward a -45 direction （ a） （ b） （ c） FIGURE 10.4 Illustration of line detection (a) Binary wirebond mask. (b) Absolute value of result after processing with -45 line detector. (c) Result of thresholding image. (b) produced the strongest responses in Fig. 10.4(b). In order to determine which lines best fit the mask, we simply threshold this image. The result of using a threshold equal to the maximum value in the image is 7 shown in Fig. 10.4(c).The maximum value is a good choice for a threshold in applications such as this because the input image is binary and we are looking for the strongest responses. Figure 10.4(c) shows in white all points that passed the threshold test. In this case, the procedure extracted the only line segment that was one pixel thick and oriented at -450 (the other component of the image oriented in this direction in the top, left quadrant is not one pixel thick). The isolated points shown in Fig. 10.4(c) are points that also had similarly strong responses to the mask. In the original image, these points and their immediate neighbors are oriented in such as way that the mask produced a maximum response at those isolated locations. These isolated points can be detected using the mask in Fig. 10.2(a) and then deleted, or they could be deleted using morphological erosion, as discussed in the last chapter. 10.1.3 Edge Detection Although point and line detection certainly are important in any discussion on segmentation, edge detection is by far the most common approach for detecting meaningful discontinuities in gray level. In this section we discuss approaches for implementing first- and second-order digital derivatives for the detection of edges in an image. We introduced these derivatives in Section 3.7 in the context of image enhancement. The focus in this section is on their properties for edge detection. Some of the concepts previously introduced are restated briefly here for the sake continuity in the discussion. Basic formulation Edges were introduced informally in Section 3.7.1. In this section we look at the concept of a digital edge a little closer. Intuitively, an edge is a set of connected pixels that lie on the boundary between two regions. However, we already went through some length in Section 2