畢業(yè)設計---大規(guī)模數(shù)據(jù)驅動的陰影檢測

1、<p>　　畢業(yè)設計（論文）說明書</p><p>　　學 院 軟件學院 </p><p>　　專 業(yè) 軟件工程 </p><p>　　年 級 2007 級 </p><p>　　姓 名 </p><p>　　指導教師

2、 </p><p>　　2011年 6月 15日</p><p>　　畢業(yè)設計（論文）任務書</p><p>　　題目：大規(guī)模數(shù)據(jù)驅動的陰影檢測</p><p>　　學生姓名 </p><p>　　學院名稱 軟件學院 </p><p>

3、　　專 業(yè) 軟件工程 </p><p>　　學 號 </p><p>　　指導教師 </p><p>　　職 稱 </p><p><b>　　一、原始依據(jù)</b></p><p>　　

4、陰影作為場景光照作用下形成的最為顯著的效果之一，為發(fā)現(xiàn)場景屬性，如：物體大小、形狀和運動，提供了有利線索；但它同時也使視覺識別任務，如：特征檢測、物體識別和場景解析，變得更復雜。近些年，已經(jīng)有多個課題組提出方法消除圖片中光照的影響，也有課題組提出方法來移除圖片中的陰影。</p><p>　　本課題《大規(guī)模數(shù)據(jù)驅動的陰影檢測》旨在識別單張圖片中的陰影，其研究動機主要來自兩個方面：第一，陰影作為視覺中最普遍存在的場景

5、元素之一，能否對其進行有效識別對后續(xù)視覺任務的完成具有重要的影響，現(xiàn)階段陰影識別技術已取得長足的發(fā)展，但其作為視覺領域的一個基礎問題仍然是一個值得研究的開放的話題，有許多難題亟待解決；第二，受現(xiàn)階段大規(guī)模數(shù)據(jù)驅動技術的激勵，使用大規(guī)模數(shù)據(jù)驅動技術來解決視覺應用中難以參數(shù)化建模的復雜問題開辟了，相對于機器學習來說，一種全新的研究思路，呈現(xiàn)出廣闊的研究空間。</p><p>　　本課題需要識別的陰影來自單張日常生活中

6、的圖片，由于日常生活場景的復雜性必然導致陰影識別的復雜性，加之用戶拍攝圖片的環(huán)境、設備和方式的差異性將進一步提升陰影檢測的難度。</p><p>　　本課題的深入研究必須具備兩個條件：第一，數(shù)據(jù)資源和設備資源，數(shù)據(jù)資源就是用于大規(guī)模數(shù)據(jù)驅動的圖片，這可以從Flickr、Google、百度等圖片網(wǎng)站上獲取，這些大多是用戶上傳的隨處可得的日常生活中的照片，預計需要下載百萬張圖片。設備資源可以看成是對大規(guī)模圖片的有效存

7、儲和檢索，由于數(shù)據(jù)量較大，在實現(xiàn)過程中需要對數(shù)據(jù)進行分布式的存儲和檢索，需要使用4-6臺商品計算機；第二，識別方法，數(shù)據(jù)的獲取可能相對較容易，如何利用數(shù)據(jù)中的信息才是本課題研究的重點，必須充分利用大規(guī)模數(shù)據(jù)中冗余的的場景信息來輔助挖掘單張圖片中的場景信息，這也是大規(guī)模數(shù)據(jù)驅動數(shù)據(jù)的靈魂所在。</p><p>　　本課題主要面向學術研究，具體應用可以在陰影識別的基礎上進一步拓展，在暫不做過多的描述。</p&g

8、t;<p><b>　　二、參考文獻</b></p><p>　　[1]Jean-Francois Lalonde, Alexei A. Efros, Srinivasa G. Narasimhan: Detecting ground shadows in outdoor consumer photographs[J]. In: European Conference on C

9、omputer Vision, 2010.</p><p>　　[2]Jiejie Zhu, Kegan G.G. Samuel, Syed Z. Masood, Marshall F. Tappen: Learning to Recognize Shadows in Monochromatic NaturalImages[J]. In: International Conferenceon Pattern Re

10、cognition, 2010. </p><p>　　[3]Bryan C. Russell1 Alexei A. Efros, Josef Sivic1 William T. Freeman Andrew Zisserman: Segmenting Scenes by Matching Image Composites[J]. In: Neural InformationProcessing Systems,

11、 2009.</p><p>　　[4]Elena Salvador, Andrea Cavallaro, Touradj Ebrahimia: Cast shadow segmentation using invariant color features[J]. In: Computer Vision and Image Understanding, 2004.</p><p>　　[5

12、]Ce Liu, Jenny Yuen, Antonio Torralba: Nonparametric Scene Parsing: Label Transfer via Dense Scene Alignment[J]. In: International Conference on Pattern Recognition, 2009.</p><p>　　三、設計（研究）內容和要求</p>&

13、lt;p>　　本課題重點研究單張用戶圖片中陰影的檢測，研究方案為使用大規(guī)模數(shù)據(jù)驅動技術。</p><p>　　研究工作按畢設進度有序進行，最終研究成果必須和European Conference on Computer Vision 2010《Detecting ground shadows in outdoor consumer pho-tographs》中發(fā)表的實驗結果進行比較，要求陰影檢測的查全率和查

14、準率達到或超過其公布的實驗數(shù)據(jù)。同時，在整理畢業(yè)論文文集之前，須撰寫英文論文。</p><p><b>　　指導教師（簽字）</b></p><p><b>　　年 月 日</b></p><p>　　審題小組組長（簽字）</p><p><b>　　年 月 日</b

15、></p><p>　　天津大學本科生畢業(yè)設計（論文）開題報告</p><p><b>　　摘　　要</b></p><p>　　陰影常常會擾亂許多計算機視覺算法，如：圖片分割、物體檢測、移動物體追蹤，等。有效的圖片陰影檢測必將顯著提高這些視覺算法的性能。</p><p>　　本論文提出了一個全新的基于概率統(tǒng)計方法

16、自動檢測單張戶外圖片地面陰影的方法。不同于前人的工作，我們的方法不依賴任何幾何假設，如：相機位置、地面/物體幾何屬性；更重要的是，我們摒棄了現(xiàn)在主流的基于機器學習的陰影檢測框架。該方法基于一個重要的日常觀察：構成戶外場景地面的材料通常是相對有限的，最常見的包括瀝青、磚塊、石頭、泥土、草地、混泥土，等。同時，大規(guī)模數(shù)據(jù)驅動技術作為當前國際研究的熱點常被用來解決視覺領域難以參數(shù)化建模的相關問題，如果用于陰影檢測，則可以有效解決前人工作中遇到

17、的模型選擇、參數(shù)設置、用戶介入過多等相關難題?；谝陨蟽牲c，單張圖片中的地面陰影不會像常規(guī)陰影那樣大范圍變動，并且可以巧妙地使用大規(guī)模的無標注陰影圖片庫來有效鑒別。</p><p>　　我們的陰影檢測系統(tǒng)由四個主要步驟構成，包括: (a)從圖片分割邊周圍提取陰影敏感特征；(b)使用大規(guī)模數(shù)據(jù)驅動技術進行陰影判別；(c)使用條件隨機域最優(yōu)化方法組合檢測到的陰影邊構成連續(xù)的陰影輪廓；(d)結合現(xiàn)有的單張圖片地面檢測器

18、。實驗在許多具有不同地面材料和陰影形狀的非常有挑戰(zhàn)行的圖片上的展示了很好的陰影檢測效果。</p><p>　　由于許多視覺應用感興趣的物體(如：行人、車輛、標識)常常和地面綁連接在一起，我們相信我們提出的自動無參陰影檢測器能找到廣闊的應用空間。</p><p>　　關鍵詞：陰影檢測；數(shù)據(jù)驅動；支持度；顏色比；松弛度因子；條件隨機域</p><p><b>

19、　　ABSTRACT</b></p><p>　　Shadows often confound algorithms designed to solve computer vision tasks such as image segmentation, object detection and tracking, etc. Detecting shadows from images can signi

20、ficantly improve the performance of such vision algorithms.</p><p>　　In this paper, we present a novel statistic based algorithm to automatically detect shadows cast by objects onto the ground, from a signal

21、 consumer outdoor photograph. Unlike previous work, our approach does not rely on any geometric assumption, such as camera position, ground surface/object geometry. What's more, we abandoned the current popular machi

22、ne learning based shadow detection framework. Our key observation is that the types of materials constructing the ground in outdoor is relatively </p><p>　　Our shadow detecting system consists of a four-tier

23、 process including (a) computing shadow sensitive features around each image edge, (b) identifying shadows using large scale data-driven technology, (c) a CRF-based optimization to group detected shadow edges to generate

24、 coherent shadow contours, and (d) incorporating any existing classifier that is specifically trained to detect ground in images. Our results demonstrate good detection accuracy on many challenging images having differen

25、t ground </p><p>　　Since most objects of interest to vision applications (like pedestrians, vehicles, signs) are attached to the ground, we believe our shadow detection system can find wide applicability.<

26、;/p><p>　　Key words: shadow detection; data-driven; support ratio; color ratio; looseness factor; CRF</p><p><b>　　緒論</b></p><p><b>　　研究背景和意義</b></p>

27、<p>　　自從電子計算機問世以來，隨著硬件和軟件技術的不斷進步，人類對計算機應用的要求越來越高。在21世紀的今天，計算機已經(jīng)在我們的生活中無處不在，從衣食住行的各個方面為我們提供高效便捷的服務。特別是近二十年來隨著互聯(lián)網(wǎng)和多媒體技術的高速發(fā)展，計算機在我們的生活中占據(jù)著越來越重要的位置，我們獲得的信息量呈幾何級數(shù)的速度增長，獲取信息的方式也越來越方便，并且信息的表現(xiàn)形式也不再局限于原來的文字和靜態(tài)的圖片，而是包括聲音、視

28、頻、動畫等多種媒體形式，所以有人說:我們生活在一個信息爆炸的時代，或稱為信息時代。</p><p>　　人類接收信息的主要來源是視覺，占據(jù)了約70%的比重。我們從視覺系統(tǒng)得到的信息就是圖像，簡言之，圖像是自然界景物的客觀反映和人類視覺系統(tǒng)的主觀感受相結合的產(chǎn)物。而計算機視覺則是希望計算機能夠從圖像或圖像序列中獲取對世界的描述。這種信息的獲取是以準確的分析和處理數(shù)字圖像為基礎的，也被稱為數(shù)字圖像處理技術。</

29、p><p>　　數(shù)字圖像處理技術發(fā)展到今天，許多技術己日臻成熟。在各個領域的應用取得了巨大的成功和顯著的經(jīng)濟效益。如在工程領域、工業(yè)生產(chǎn)、軍事、醫(yī)學以及科學研究中的應用已十分普遍。通過分析資源衛(wèi)星得到的照片可以獲得地下礦藏資源的分布及埋藏量;利用紅外線、微波遙感技術可偵查到隱蔽的軍事設施;X射線CT己廣泛應用于臨床診斷，由于它可得到人體內部器官的斷層圖像，因此，可準確地確定病變的位置，為診斷和治療疾病帶來了極大的方便

30、。在安全保障及監(jiān)控方面圖像處理技術更是不可缺少的基本技術。</p><p>　　陰影是在自然界中普遍存在的一種物理現(xiàn)象，是由于光源被物體遮擋而產(chǎn)生的。圖像中陰影的存在對計算機視覺領域的相關問題有不同的影響，這種影響有有利的也有不利的。比如我們可以從陰影中得到物體的幾何信息、場景空間結構、光源方向等，對三維場景重建、空間物體運動分析有重要的作用;在虛擬現(xiàn)實、3D游戲中為物體添加陰影，可以提高場景的真實感。但是更多的

31、時候，圖像中的陰影會對計算機視覺的相關問題產(chǎn)生不利的影響，如在航空圖像中，陰影的存在會影響后繼的圖像匹配、模式識別和地物提取等多種遙感圖像處理操作;在醫(yī)學成像中，陰影會影響醫(yī)生對病變圖像的分析;在視頻監(jiān)控中，陰影和運動目標結合在一起，導致計算機對目標物體的提取和追蹤出現(xiàn)錯誤。因此，有必要對圖像中的陰影進行檢測和分析，并根據(jù)需要，進而消除或減弱陰影的影響。</p><p><b>　　國內外研究進展<

32、;/b></p><p>　　陰影可以說無處不在，人眼可以快速地識別出圖片中的陰影，計算機算法的識別效果卻不是很理想。在計算機視覺研究的早期，陰影的出現(xiàn)弱化了許多視覺應用的效果，包括分割、物體檢測、場景分析、跟蹤等。盡管現(xiàn)在存在許多標準的方法、軟件和評估數(shù)據(jù)庫來完成重要的視覺任務，包括從邊檢測到人年檢測，但在過去的40年里陰影相關的研究卻很少。</p><p>　　到目前為止，使用多

33、張圖片、標有時間的圖片序列或者用戶輸入的陰影方法已經(jīng)取得了豐碩的成果，但對單張圖片自動進行穩(wěn)定可靠的陰影檢測來說仍然是個開放的話題[]。這主要是由于戶外陰影的形狀和外貌依賴于多個隱含因素，如：顏色、光照的大小和方向、投影物體的幾何形狀、被投影物體的形狀和材料等。現(xiàn)階段單張圖片陰影檢測的大部分工作都是基于光照不變量。不幸的是，不變量的穩(wěn)定計算需要高質量的圖片（擁有較大的動態(tài)變化范圍、較高的強度分辨率，并且相機參數(shù)、顏色變化能夠準確的測量和

34、補償），這樣這些方法就不適合日常生活圖片的處理，如：來自Flickr和Google上的圖片。由于當前計算機視覺的大量研究工作都是基于日常生活中的圖片，所以提出一套新穎的高效的陰影檢測方法迫在眉睫。</p><p>　　使用大規(guī)模數(shù)據(jù)來解決計算機視覺領域難以參數(shù)化建模的相關難題已經(jīng)成為當前國際上研究的熱點。如：Carnegie Mellon University教授Alexei (Alyosha) Efros長期致

35、力于計算機視覺和計算機圖形學領域的研究工作，其當前主要研究興趣就在于利用互聯(lián)網(wǎng)上大量存儲的并且日益增長的視覺信息，如：數(shù)字相冊、網(wǎng)絡攝像頭、電影等，來學習、理解和合成周圍的視覺世界；Massachusetts Institute of Technology教授Antonio Torralba及其指導的學生正在使用隨處可得的視覺信息來幫助識別場景和物體[]。當前國內不少科研團隊，如：微軟研究院、清華大學等，在大規(guī)模圖像和視頻檢索方面進行了

36、大量的研究并在基于草圖的視覺檢索、文本視覺信息混合檢索、語義檢索方面取得了顯著的成就。然而，國內在大規(guī)模視覺檢索的基礎上，利用大規(guī)模數(shù)據(jù)驅動技術解決計算機視覺領域相關難題方面還處在初始發(fā)展階段，見諸發(fā)表的文章也相對較少。本課題可以看成是使用大規(guī)模數(shù)據(jù)驅動技術進行場景理解方面的一個新嘗試。</p><p><b>　　主要研究內容 </b></p><p>　　本文將對

37、單張圖片中的陰影檢測進行研究，在充分分析陰影屬性的基礎上，結合現(xiàn)有陰影檢測原理和大規(guī)模數(shù)據(jù)驅動技術，提出了一個全新的陰影檢測方法，并通過實驗對算法進行了檢測和分析。因此本文的主要內容有：</p><p>　　陰影形成的基本原理，給出陰影的定義，總結分析陰影的特點；</p><p>　　常用顏色模型分析和比較；</p><p>　　比較現(xiàn)有陰影特征提取方法，并提出自己

38、的陰影特征提取算法；</p><p>　　數(shù)據(jù)聚類算法分類和總結；</p><p>　　分析現(xiàn)有的陰影檢測算法的優(yōu)缺點及限制條件，并提出自己的陰影檢測算法，通過實驗進行驗證分析。</p><p>　　希望通過以上的研究，為以后從事這方面研究的同仁提供一定的啟發(fā)作用。</p><p><b>　　基礎知識</b></

39、p><p><b>　　陰影形成原理</b></p><p>　　陰影，又稱影子，是一種光學現(xiàn)象，陰影不是一個實體，只是一個投影。 </p><p>　　陰影的產(chǎn)生：是由于物體遮住了光線這一科學原理。光線在同種均勻介質中沿直線傳播，不能穿過不透明物體而形成的較暗區(qū)域，形成的投影就是我們常說的影子。（這里說的光是可見光線）。</p>&

40、lt;p>　　產(chǎn)生陰影的條件:陰影形成要光和不透明物體兩個必要條件。 </p><p>　　影子分本影和半影兩種：仔細觀察電燈光下的影子，還會發(fā)現(xiàn)影子中部特別黑暗，四周稍淺。影子中部特別黑暗的部分叫本影，四周灰暗的部分叫半影。這些現(xiàn)象的產(chǎn)生都和光的直線傳播有密切關系。假如把一個柱形茶葉筒放在桌上，旁邊點燃一支蠟燭，茶葉筒就會投下清晰的影子 。如果在茶葉筒旁點燃兩支蠟燭，就會形成兩個相疊而不重合的影子。兩影相

41、疊部分完全沒有光線射到，是全黑的，這就是本影；本影旁邊只有一支蠟燭可照到的地 方，就是半明半暗的半影。物體在電燈光下能生成由本影和半影組成的影子，也是這個道理。電燈是由一條彎曲的燈絲在發(fā)光，不只限于一點。從這一個點射來的光給物體遮住了，從另一些點射過來的光并不一定全被擋住。很顯然，發(fā)光物體的面積越大，本影就越小。如果我們在上述茶葉筒周圍點上一圈蠟燭，這時本影完全消失，半影也淡得看不見了。 科學家根據(jù)上述原理制成了手術用的無影燈。它將發(fā)光

42、強度很大的燈在燈盤上排列成圓形，合成一個大面積的光源。這樣，就能從不同角度把光線照射到手術臺上，既保證手術視野有足夠的亮度，同時又不產(chǎn)生明顯的本影，所以取名無影燈。</p><p><b>　　常用色彩模型比較</b></p><p><b>　　RGB</b></p><p>　　RGB是三個顏色紅red、綠green、

43、藍blue的縮寫，RGB屬于加性色系，因為這三個顏色混合相加可以得到青色，品紅，黃色，白色和所有其他顏色在電視機、顯示器上使用的所有顏色[]。圖2-1為RGB顏色模型示意圖，(a)加性顏色紅色、綠色、藍色可以混合出青色、紫紅色、黃色和白色；(b)減性顏色青色、紫紅色、黃色可以產(chǎn)生紅色、綠色和藍色，還有黑色。</p><p>　　圖2-1　　主顏色和次主顏色</p><p>　　在1930年

44、，CIE（國際照明委員會），通過使用紅（700.nm波長）、綠（546.1nm）、藍（435.8nm）三個主顏色進行顏色匹配實驗，標準化了RGB顏色表示。RGB（紅綠藍）是依據(jù)人眼識別的顏色定義出的空間，可表示大部分顏色。但在科學研究一般不采用RGB顏色空間，因為它的細節(jié)難以進行數(shù)字化的調整。它將 色調，亮度，飽和度三個量放在一起表示，很難分開。它是最通用的面向硬件的彩色模型。該模型主要用于彩色監(jiān)視器和一大類彩色視頻攝像。</p&

45、gt;<p><b>　　XYZ</b></p><p>　　由于混合負光相關問題的存在，CIE開發(fā)了一個叫XYZ的新顏色空間，該空間包含了正八分儀中的所有純光譜顏色（Y軸映射到關照強度，可感知的相對亮度，純白色映射到等值對角向量）。RGB到XYZ的變換公式為：</p><p>　　當我們需要分離光照強度和色度時，最方便的顏色值表示方法是XYZ（光照強度

46、加兩個最顯著的色度組件）。</p><p><b>　　L*a*b</b></p><p>　　雖然XYZ顏色空間有許多方便的屬性，這包括分離光照強度和色度，但它事實上并沒有很好地預測人類在光照和色度方面的感知差異。</p><p>　　因為人類視覺系統(tǒng)響應大致是成對數(shù)形式的（我們能感知到的相對亮度差異大約為1%），CIE定義了一個叫L*a*b

47、的顏色空間非線性重映射XYZ空間，這里光照強度和色度差異在感知上更加一致[]。（一個叫L*u*v的可選的感知激勵顏色空間在同一時間被開發(fā)和標準化。）</p><p>　　L*光照組件被定義為：</p><p>　　Yn是歸一化的白色光強值，并且：</p><p>　　是立方根的有限斜率近似，δ=6/29。同樣的方式，a*、b*組件定義為：</p>&l

48、t;p>　　本論文中陰影特征的提取正是基于不同的顏色空間，此處的關于顏色空間的簡單介紹對后文陰影特征提取的深入理解能起到很好的鋪墊作用。</p><p><b>　　特征提取</b></p><p>　　特征提取是計算機視覺和圖像處理中的一個概念。它指的是使用計算機提取圖像信息，決定每個圖像的點是否屬于一個圖像特征。特征提取的結果是把圖像上的點分為不同的子集，這

49、些子集往往屬于孤立的點、連續(xù)的曲線或者連續(xù)的區(qū)域。</p><p>　　至今為止特征沒有萬能和精確的定義。特征的精確定義往往由問題或者應 用類型決定。特征是一個數(shù)字圖像中“有趣”的部分，它是許多計算機圖像分析算法的起點[]。因此一個算法是否成功往往由它使用和定義的特征決定。因此特征提取 最重要的一個特性是“可重復性”：同一場景的不同圖像所提取的特征應該是相同的。 </p><p>　　常見

50、的特征定義有:邊、角、顏色、紋理、形狀等等。由于本文提取的陰影特征主要基于顏色和紋理，因此在這里我們主要介紹顏色和紋理特征。</p><p>　　顏色特征是一種全局特征,描述了圖像或圖像區(qū)域所對應的景物的表面性 質。一般顏色特征是基于像素點的特征，此時所有屬于圖像或圖像區(qū)域的像素都有各自的貢獻。由于顏色對圖像或圖像區(qū)域的方向、大小等變化不敏感，所以顏色特 征不能很好地捕捉圖像中對象的局部特征。另外，僅使用顏色特征

51、查詢時，如果數(shù)據(jù)庫很大，常會將許多不需要的圖像也檢索出來。顏色直方圖是最常用的表達顏色 特征的方法，其優(yōu)點是不受圖像旋轉和平移變化的影響，進一步借助歸一化還可不受圖像尺度變化的影響，基缺點是沒有表達出顏色空間分布的信息。常用的顏色特征提取與匹配方法有：顏色直方圖 、顏色集 、顏色矩、顏色聚合向量、顏色相關圖[]。 </p><p>　　紋理特征也是一種全局特征，它也描述了圖像或圖像區(qū)域所對應景物的表 面性質。但由

52、于紋理只是一種物體表面的特性，并不能完全反映出物體的本質屬性，所以僅僅利用紋理特征是無法獲得高層次圖像內容的。與顏色特征不同，紋理特 征不是基于像素點的特征，它需要在包含多個像素點的區(qū)域中進行統(tǒng)計計算。在模式匹配中，這種區(qū)域性的特征具有較大的優(yōu)越性，不會由于局部的偏差而無法匹配 成功。作為一種統(tǒng)計特征，紋理特征常具有旋轉不變性，并且對于噪聲有較強的抵抗能力。但是，紋理特征也有其缺點，一個很明顯的缺點是當圖像的分辨率變化的 時候，所計算出

53、來的紋理可能會有較大偏差。另外，由于有可能受到光照、反射情況的影響，從2-D圖像中反映出來的紋理不一定是3-D物體表面真實的紋理[]。</p><p>　　在檢索具有粗細、疏密等方面較大差別的紋理圖像時，利用紋理特征是一種有效的方法。但當紋理之間的粗細、疏密等易于分辨的信息之間相差不大的時候，通常的紋理特征很難準確地反映出人的視覺感覺不同的紋理之間的差別。 </p><p>　　常用的紋理

54、特征提取方法包括：統(tǒng)計方法、幾何法、模型法、信號處理法。</p><p><b>　　大規(guī)模數(shù)據(jù)聚類方法</b></p><p>　　聚類算法將一系列數(shù)據(jù)聚團成多個子集或簇，其目標是建立類內緊密、類間分散的多個簇。換句話說，聚類的結果要求簇內的數(shù)據(jù)之間要盡可能的相似，而簇間的數(shù)據(jù)之間要盡可能不相似。</p><p>　　聚類是無監(jiān)督學習的一種最

55、普遍的形式。無監(jiān)督也意味著不存在對文檔進行類別標注的人類專家。聚類中，數(shù)據(jù)的分布和組成結構決定最后的類別歸屬。</p><p>　　聚類算法的一個關鍵輸入是距離計算方法。在數(shù)據(jù)聚類當中，距離計算方法往往采用歐式距離。不同的距離計算方法會導致不同的聚類效果。因此，距離的計算方法是影響聚類結果的一個重要因素。</p><p>　　扁平聚類算法會給出一個扁平結構的簇，他們之間沒有任何顯式的結構來

56、表明彼此的關聯(lián)性。而層次聚類算法則會產(chǎn)生層次性的聚類結果。</p><p>　　了解硬聚類和軟聚類之間的差別也相當重要。硬聚類計算的是一個硬分配過程，即每個數(shù)據(jù)僅僅屬于一個簇。而軟聚類算法的分配過程是軟的，即一個數(shù)據(jù)的分配結果是在所有簇中的一個分配。在軟分配結果中，一個數(shù)據(jù)可能對多個簇都具有隸屬度。作為一種降維方法，隱性語義索引就是一個軟聚類算法。</p><p>　　本文將使用Kmean

57、s[]聚類方法對提取出的陰影陰影特征進行粗略地分簇,下邊簡要介紹Kmeans原理：</p><p>　　Kmeans算法接受輸入量k，然后將n個數(shù)據(jù)對象劃分為k個聚類以便使得所獲得的聚類滿足：同一個聚類中的對象高度相似，不同聚類中的對象相似度較少。聚類相似度是利用各聚類中對象的均值獲得一個“中心對象”（引力中心）來計算的。</p><p>　　Kmeans算法的工作過程說明如下：首先從n個

58、數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心，對于剩下的所有對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給其最相似的（聚類中心所代表的）聚類，然后再計算每個新聚類的聚類中心（該聚類中所有對象的均值）。不斷重復上述過程知道標準測度函數(shù)開始收斂為止。一般都采用均方差作為標準測度函數(shù)。k個聚類具有一下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。Kmeans++是對Kmeans算法的一種改進，它不同于Kmeans算法的

59、地方是初始聚類中心的選擇不是任意選擇的，而是必須符合一定的關系，這樣就使得聚類算法所得到的聚類結果相對于隨機選擇初始聚類中心來說更加合理。</p><p><b>　　陰影檢測算法研究</b></p><p>　　圖像中陰影的特點和性質</p><p>　　陰影區(qū)域和其周邊的非陰影區(qū)域具有如下特點：</p><p>　　

60、由于光線被部分遮擋，陰影區(qū)域具有較低的亮度；</p><p>　　一般來說，陰影區(qū)域和非陰影區(qū)域具有不同的色度；</p><p>　　陰影不明顯改變原有地表的紋理特征；</p><p>　　陰影與產(chǎn)生陰影的遮擋物具有相似的輪廓；</p><p>　　在計算機視覺的相關應用中，陰影在數(shù)字圖像中的存在，既有有利的方面又不利的影響。</p&g

61、t;<p><b>　　有利之處在于：</b></p><p>　　從陰影的形狀可以得到遮擋物體的幾何信息和場景的空間布局；</p><p>　　可以利用陰影來確定光源的位置、強弱和大小等信息；</p><p>　　在三維虛擬現(xiàn)實技術和計算機游戲中，加入物體模擬陰影，可以增強觀察者的立體感和空間感，進而提高場景的真實感。</

62、p><p><b>　　不利之處在于：</b></p><p>　　陰影影響圖像的可視性，例如在航空圖片中，陰影區(qū)域的地物特征會由于陰影的噪聲效應而邊模糊，進而影響圖像分析；</p><p>　　陰影的存在會降低圖像分割的準確性，從而導致視頻監(jiān)控、目標追蹤、物體識別、圖像標注等計算機視覺應用出現(xiàn)錯誤。</p><p><

63、;b>　　陰影檢測算法流程</b></p><p>　　圖3-1　　算法流程圖</p><p>　　本算法主要分兩大模塊：離線數(shù)據(jù)庫模塊和在線判別模塊。兩大模塊均包含特征提取。離線數(shù)據(jù)庫模塊對提取出陰影特征進行了特征提純。在線判別模塊利用數(shù)據(jù)庫中的特征對輸入圖片中的每個特征計算支持度，這些支持度值進一步整合進CRF模型得到連續(xù)完整的陰影輪廓。</p><

64、;p><b>　　陰影特征提取</b></p><p>　　陰影特征提出主要分兩個步驟進行：圖片過分割和特征計算。</p><p><b>　　圖片過分割</b></p><p>　　圖像分割就是把圖像分成若干個特定的、具有獨特性質的區(qū)域并提出感興趣目標的技術和過程。它是由圖像處理到圖像分析的關鍵步驟?，F(xiàn)有的圖像分割

65、方法主要分以下幾類：基于閾值的分割方法、基于區(qū)域的分割方法、基于邊緣的分割方法以及基于特定理論的分割方法等。近年來，研究人員不斷改進原有的圖像分割方法并把其它學科的一些新理論和新方法用于圖像分割，提出了不少新的分割方法。本文使用的分割算法為經(jīng)典的分水嶺分割算法[]。</p><p>　　圖3-2　　圖片過分割效果</p><p>　　分水嶺算法的概念及原理：</p><

66、p>　　分水嶺分割方法，是一種基于拓撲理論的數(shù)學形態(tài)學的分割方法，其基本思想是把圖像看作是測地學上的拓撲地貌，圖像中每一點像素的灰度值表示該點的海拔高度，每一個局部極小值及其影響區(qū)域稱為集水盆，而集水盆的邊界則形成分水嶺。分水嶺的概念和形成可以通過模擬浸水過程來說明。在每一個局部極小值表面，刺穿一個小孔，然后把整個模型慢慢浸入水中，隨著浸水的加深，每一個局部極小值的影響域慢慢向外擴展，在兩個集水盆匯合處構筑大壩，即形成分水嶺。&l

67、t;/p><p>　　分水嶺的計算過程是一個迭代標注過程。分水嶺比較經(jīng)典的計算方法是L. Vincent提出的。在該算法中，分水嶺計算分兩個步驟，一個是排序過程，一個是淹沒過程。首先對</p><p>　　每個像素的灰度級進行從低到高排序，然后在從低到高實現(xiàn)淹沒過程中，對每一個局部極小值在h階高度的影響域采用先進先出(FIFO)結構進行判斷及標注。</p><p>　　

68、分水嶺變換得到的是輸入圖像的集水盆圖像，集水盆之間的邊界點，即為分水嶺。顯然，分水嶺表示的是輸入圖像極大值點。因此，為得到圖像的邊緣信息，通常把梯度圖像作為輸入圖像，即：</p><p>　　式中，f(x,y)表示原始圖像，grad{.}表示梯度運算。</p><p>　　分水嶺算法對微弱邊緣具有良好的響應，圖像中的噪聲、物體表面細微的灰度變化，都會產(chǎn)生過度分割的現(xiàn)象。但同時應當看出，分水

69、嶺算法對微弱邊緣具有良好的響應，是得到封閉連續(xù)邊緣的保證的。另外，分水嶺算法所得到的封閉的集水盆，為分析圖像的區(qū)域特征提供了可能。</p><p>　　為消除分水嶺算法產(chǎn)生的過度分割，通?？梢圆捎脙煞N處理方法，一是利用先驗知識去除無關邊緣信息。二是修改梯度函數(shù)使得集水盆只響應想要探測的目標。</p><p>　　為降低分水嶺算法產(chǎn)生的過度分割，通常要對梯度函數(shù)進行修改，一個簡單的方法是對梯

70、度圖像進行閾值處理，以消除灰度的微小變化產(chǎn)生的過度分割。即:　　g</p><p>　　式中，gθ表示閾值。</p><p>　　程序可采用方法：用閾值限制梯度圖像以達到消除灰度值的微小變化產(chǎn)生的過度分割，獲得適量的區(qū)域，再對這些區(qū)域的邊緣點的灰度級進行從低到高排序，然后再從低到高實現(xiàn)淹沒的過程，梯度圖像用Sobel算子計算獲得。對梯度圖像進行閾值處理時，選取合適的閾值對最終分割的圖像有很

71、大影響，因此閾值的選取是圖像分割效果好壞的一個關鍵。缺點：實際圖像中可能含有微弱的邊緣，灰度變化的數(shù)值差別不是特別明顯，選取閾值過大可能會消去這些微弱邊緣。</p><p>　　分水嶺算法最終結果可以得到：分割區(qū)域、分割區(qū)域鄰接關系、分割邊界、分割區(qū)域角點等相關信息，這些信息將用于下一步的特征計算。</p><p><b>　　特征計算</b></p>

72、<p>　　為了確定圖片中的陰影像素，我們選擇確定光照、紋理和奇階導等特征。有別于使用當個像素，我們這里利用過分出來的相似區(qū)域來計算特征值。</p><p><b>　　強度差異[]：</b></p><p>　　陰影區(qū)域相對于非陰影區(qū)域較黑，我們可以從分割圖片中提取強度統(tǒng)計信息。對于相鄰像素，我們計算絕對強度差值；對于相鄰分割塊，我們計算強度直方圖之間的L

73、1范數(shù)。</p><p><b>　　局部最大值：</b></p><p>　　在局部塊中，陰影具有相對較小的強度值，因此，局部最大值也會相對較小。反過來，非陰影區(qū)域具有較高的強度值，局部最大值也會相對較大。這里，我們在每3個相鄰像素間計算局部最大值。</p><p><b>　　平滑度：</b></p>&

74、lt;p>　　陰影區(qū)域可以看作相鄰區(qū)域的平滑版本，因為陰影傾向于抑制底層表面的局部變化。為了捕獲這個特征，我們從原始圖片中減去該圖片的平滑版本，這樣對于剩余圖片，已經(jīng)平滑的區(qū)域將擁有較少的差異，高度變化的區(qū)域將擁有較大的差異。</p><p><b>　　梯度相似性:</b></p><p>　　陰影邊界處的圖片梯度值分布是恒定的。我們使用相鄰分割區(qū)域梯度直方圖

75、間的L1范數(shù)來捕獲這種相似性。</p><p><b>　　紋理相似性：</b></p><p>　　觀察顯示陰影邊界處的紋理特性很少改變。我們使用[1]中介紹的方法來度量圖片區(qū)域的紋理特性。該方法首先使用一組有8個方向、3個尺度的高斯梯度過濾器過濾圖片集，然后聚類場128個聚類中心。新圖片中的紋理則使用這些離散中心來表示。我們也使用相鄰分割區(qū)域紋理直方圖間的L1范數(shù)

76、來度量紋理相似度。</p><p><b>　　顏色比值：</b></p><p>　　描述陰影邊的另一個有效特征是顏色強度比。在自然光照條件下陰影區(qū)域內外的差異性，使得陰影邊界兩側的顏色強度會維持一個相對穩(wěn)定的比值。由于很難手工決定計算顏色比的最優(yōu)顏色空間和尺度，我們使用3個不同的顏色空間（RGB、L*a*b和[2]中提到的顏色空間）和4個不同的尺度。</p&

77、gt;<p>　　對于邊界上的一個像素，通過計算邊一側的像素加權和我們得出邊這一側（比方說，左邊）的強度值。但是選擇哪個像素點？我們可以使用分水嶺分割，但是它們并沒有延伸太遠。相反，我們使用方差為δ方的有向高斯衍生過濾器，但只保留大于0的值。我們對齊過濾器和邊界的方向，這樣過濾器的正權值位于邊界的左側，和圖片做卷積可以得到fl。把過濾器旋轉180度進行相同的操作可以獲得像素右側的像素加權平均值fr。這樣像素點p處的顏色比為

78、。這個操作在RGB、LAB、光照不變[2]顏色空間的每個顏色通道上獨立進行。為了衡量邊的敏銳程度，我們在4個尺度和大小上計算每個過濾器來獲得總共36個比值。</p><p>　　我們也利用[3]中提出的兩個特征，它們能捕捉邊界兩邊的紋理和強度分布差異。第一個特征在4個不同的尺度上計算紋理直方圖，并使用卡方距離進行比較。紋理字典從一個非重疊的圖片集中計算得到。第二個特征在相同的4個尺度上計算像素強度偏移差異。<

79、;/p><p>　　最后，我們連接從顏色通道計算得到的最小過濾器響應的絕對值來獲得每個像素點處最終的，完備的，48維特征向量。邊界特征向量取邊界上所有像素點特征向量的平均值。</p><p><b>　　特征提純</b></p><p>　　經(jīng)步驟4.1和4.2提取出來的陰影特征保留了原圖片中97%的陰影，然而數(shù)量巨大的陰影特征，使得陰影在提取出來

80、的陰影特征中所在的比例并不高，也就是說純度不夠，這將嚴重影響邊陰影支持度的計算。因此，我們對數(shù)據(jù)庫陰影特征進行了提純。</p><p>　　這里我們主要用到了一個觀察現(xiàn)象：戶外自然圖片中的陰影主要由大型物體倒影而成，陰影輪廓相對開闊。反過來，非陰影邊界成聚集態(tài)分布?；谶@點我們定義松散度因子來衡量這種松散/聚集分布趨勢，計算公式為：</p><p>　　對于數(shù)據(jù)庫中的每一張圖片，經(jīng)過分割并

81、提取陰影特征后，我們使用Kmeans對這些特征進行聚類，然后對每個聚類計算松散度因子，然后保留松散度因子較大的幾個聚類對應的陰影特征。實驗中我們取聚類數(shù)k=10，并保留松散度陰影子最大的前3個聚類。</p><p>　　圖3-3　　特征聚類示意圖</p><p>　　圖3-4　　聚類松散度示意圖，圓圈越小表示松散度越低，反之，越大</p><p><b>

82、　　支持度計算</b></p><p>　　我們收集了一個經(jīng)過提純的巨大的特征數(shù)據(jù)庫，這些特征包含了幾乎所有的地面陰影。為了對輸入圖片中的陰影邊進行有效檢測，我們把這個判斷問題轉化為一個概率問題，這里我們采用高斯窗口估計。高斯窗口估計作為模式識別中最經(jīng)典的概率估計模型，具有模型簡易、運算量少、易于結合等相關特點，因而在模式識別與概率統(tǒng)計中得到了廣泛應用。我們的陰影概率估計公式[]為：</p>

83、;<p>　　此處，N為數(shù)據(jù)庫中圖片數(shù)目，為第i張圖片中保留的提純聚類數(shù)目。f代表輸入圖片中待判定的特征邊處提取的特征；代表數(shù)據(jù)庫中第i張圖片中第j條特征邊處提取的特征；代表輸入圖片中對特征邊f(xié)加權值；是高斯窗口模型參數(shù)。實驗中我們取=1, =3。</p><p>　　這樣對輸入圖片中每一條特征邊我們獲得了一個概率值，將初始的0-1判斷問題轉化為了概率問題。</p><p>

84、<b>　　構建陰影輪廓</b></p><p>　　4.4中我們得出了輸入圖片中的每個特征邊的數(shù)據(jù)庫支持概率，由于輸入圖片中的特征邊通常有上萬條，數(shù)據(jù)庫中特征邊更是巨大無比，所以，我們假定輸入圖片中特征邊的支持概率服從正太分布，并且取3范圍內的特征邊為強陰影邊。由中心極限定理可以知道，單個獨立同分布事件隨著重復次數(shù)增長其整體將逐漸趨于正太分布，所以我們這里的假設是有理論依據(jù)的，同時我們的實

85、驗結果也驗證了這點。</p><p>　　雖然3檢測取得了較好的效果，但是它只抓住了整體分布的趨勢，并且是孤立地對待每條特征邊。然而，局部區(qū)域內陰影邊界左右的顏色比應該是一致的，因為場景局部區(qū)域內的光照情況是相似的。為此，我們引入條件隨機域來建模局部邊界之間的更高階依賴關系。</p><p>　　為了建模這些依賴關系[]，我們使用獨立的邊界作為節(jié)點構建圖，用邊連接交叉的邊界。然后我們在圖上

86、定義條件隨機域，這個圖將在給定觀察到的數(shù)據(jù)x的條件下特定標簽y（比如每個邊界的陰影/非陰影賦值）的對數(shù)似然值表示為一元式和二元式的和：</p><p>　　這里B是邊界的集合，E是邊界之間的邊集合， λ和β是模型參數(shù)。特別的，λ是控制兩個項相對重要性的重要性。是依賴于λ和β的特定函數(shù)，但不依賴y本身。</p><p>　　直觀地，我們希望一元式[]懲罰根據(jù)我們的局部分類器不大可能為陰影卻被

87、標記為“陰影”的賦值。這可以建模為：</p><p>　　我們也希望二元項[]懲罰有相似特征的臨近邊界標注不同標簽的賦值，這可以記作：</p><p>　　這里1(·)是指示函數(shù)，β是對比-正則化常量。實驗中=0.5，=16。</p><p><b>　　結合場景布局</b></p><p>　　因為我們一直考

88、慮的是檢測地面上的陰影，所以，對于地面概率較低但被標記為陰影的特征邊，我們要加大懲罰力度；當?shù)孛娓怕瘦^大時，我們讓初始的數(shù)據(jù)庫概率統(tǒng)計值決定。這里，我們可以簡單地修改CRF模型[]中的一元項得到：</p><p><b>　　實驗及結果分析</b></p><p>　　圖3-5　　實驗結果，圖片來自數(shù)據(jù)庫以外</p><p>　　圖3-6　　實

89、驗結果，圖片來自數(shù)據(jù)庫</p><p><b>　　結論</b></p><p><b>　　工作展望</b></p><p>　　陰影作為日常生活中常見的自然現(xiàn)象，其廣泛存在性使得其牽涉計算機視覺應用中的方方面面。陰影檢測作為計算視覺中的基礎問題，對其進行深入研究具有舉足輕重的意義。</p><p&g

90、t;　　本文提出一個全新陰影檢測方法，并在多數(shù)高難度圖片上表現(xiàn)出了非常好的效果，這是傳統(tǒng)方法無法企及的。但在后續(xù)工作中我們還可以在如下幾個方面進行改進和提高：</p><p>　　1、對于數(shù)據(jù)庫特征提純，我們只利用了一個相對初淺的觀察現(xiàn)象，這個現(xiàn)象具有較大的局限性，使得整個提純過程的查全率、查準率都較低。因此，我們需要提出更好的提純方法。</p><p>　　2、在由陰影概率確定強陰影邊的

91、時候，我們簡單地取了3范圍內的特征邊，這種做法缺乏較強的事實依據(jù)，并且過于絕對。因此，我們需要尋找更有效的概率陰影判別模型。</p><p><b>　　工作總結</b></p><p>　　本次畢業(yè)設計歷時近6個月，從最初的資料搜索到最終論文成型，其間過程曲折反復，現(xiàn)做如下總結：</p><p>　　科學研究和設計是一個不斷積累的傳承過程，我

92、們在做工作的時候不可能從零開始憑自己的力量完成全部工作，因為這中間某些路前人已經(jīng)實踐過并且傳承下來了。我們要做的是首先努力爬到巨人的肩膀上，然后奮力一跳摘取勝利的果實。</p><p>　　相比技術開發(fā)，學術論文研究側重研究全新的問題和未知的領域。在這個摸索的過程中，我們必然會遭遇非常強烈的不缺定境況，當前是困難的，下一步是不確定的，但再下一步就是光明，我們所要做的是克服眼前的困難、堅定不移地超前走。堅持很重要。

93、</p><p><b>　　參考文獻</b></p><p><b>　　致　　謝</b></p><p>　　從論文選題到搜集資料，從寫稿到反復修改，期間經(jīng)歷了喜悅、聒噪、痛苦和彷徨，在寫作論文的過程中心情是如此復雜。如今，伴隨著這篇畢業(yè)論文的最終成稿，復雜的心情煙消云散，自己甚至還有一點成就感。這篇畢業(yè)論文是展現(xiàn)自我

94、的舞臺，以下的言語便是有點成就感后在舞臺上發(fā)表的發(fā)自肺腑的誠摯謝意與感想： </p><p>　　我要感謝，非常感謝我的導師xx老師。他為人隨和熱情，治學嚴謹細心。在閑聊中他總是能像知心朋友一樣鼓勵你，在論文的寫作和措辭等方面他也總會以“專業(yè)標準”嚴格要求你，從選題、定題開始，一直到最后論文的反復修改、潤色，xx老師始終認真負責地給予我深刻而細致地指導，幫助我開拓研究思路，精心點撥、熱忱鼓勵。正是xx老師的無私幫

95、助與熱忱鼓勵，我的畢業(yè)論文才能夠得以順利完成，謝謝xx老師。</p><p>　　我要感謝，非常感謝xx師兄。正在撰寫學術論文的他，在百忙之中抽出時間幫助我搜集文獻資料，幫助我理清論文寫作思路，對我的論文提出了諸多寶貴的意見和建議。對師兄的幫助表示真摯的感謝。</p><p>　　我要感謝，非常感謝xx學長。他為我在論文寫作規(guī)范方面提供了寶貴的經(jīng)驗，同時，在答辯技巧方面給予很大的幫助。對學