《學(xué)習(xí)OpenCV》第8章輪廓分析

1、第8章 輪廓雖然Canny之類(lèi)的邊緣檢測(cè)算法可以根據(jù)像素間的差異檢測(cè)出輪廓邊界的像素，但是它并沒(méi)有將輪廓作為一個(gè)整體。下一步是要把這些邊緣像素組裝成輪廓。現(xiàn)在你也許希望OpenCV中有一個(gè)方便的函數(shù)能實(shí)現(xiàn)這一步，事實(shí)上這個(gè)函數(shù)就是cvFindContours()。為了演示如何使用這些函數(shù)，本章從一些基本的問(wèn)題入手。具體說(shuō)來(lái)，我們會(huì)詳細(xì)介紹內(nèi)存存儲(chǔ)器（memory storage）的概念，這是OpenCV在創(chuàng)建動(dòng)態(tài)對(duì)象時(shí)存取內(nèi)存的技術(shù)；然后是序列（sequence）基本介紹，在處理輪廓的時(shí)候通常需要使用序列。了解這些基本的概念后，我們就可以深入討論輪廓檢測(cè)的某些細(xì)節(jié)。最后我們將討論輪廓檢測(cè)的一些

2、實(shí)際應(yīng)用。目錄 內(nèi)存 序列 查找輪廓 Freeman鏈碼 輪廓例子 另一個(gè)輪廓例子 深入分析輪廓 輪廓的匹配 練習(xí)內(nèi)存OpenCV使用內(nèi)存存儲(chǔ)器（memory storage）來(lái)統(tǒng)一管理各種動(dòng)態(tài)對(duì)象的內(nèi)存。內(nèi)存存儲(chǔ)器在底層被實(shí)現(xiàn)為一個(gè)有許多相同大小的內(nèi)存塊組成的雙向鏈表，通過(guò)這種結(jié)構(gòu)，OpenCV可以從內(nèi)存存儲(chǔ)器中快速地分配內(nèi)存或?qū)?nèi)存返回給內(nèi)存存儲(chǔ)器。OpenCV中基于內(nèi)存存儲(chǔ)器實(shí)現(xiàn)的函數(shù)，經(jīng)常需要向內(nèi)存存儲(chǔ)器申請(qǐng)內(nèi)存空間（特別是那些返回動(dòng)態(tài)結(jié)果的函數(shù)）。內(nèi)存存儲(chǔ)器可以通過(guò)以下四個(gè)函數(shù)訪問(wèn)：CvMemStorage* cvCreateMemStorage( int block_size =

3、0);void cvReleaseMemStorage( CvMemStorage* storage);void cvClearMemStorage( CvMemStorage* storage);void* cvMemStorageAlloc( CvMemStorage* storage);cvCreateMemStorage用于創(chuàng)建一個(gè)內(nèi)存存儲(chǔ)器。參數(shù)block_size對(duì)應(yīng)內(nèi)存存儲(chǔ)器中每個(gè)內(nèi)存塊的大小。如果block_size為0，則表示內(nèi)存塊采用默認(rèn)的大小，內(nèi)存塊默認(rèn)的大小為64KB。該函數(shù)返回一個(gè)新創(chuàng)建的內(nèi)存存儲(chǔ)器指針。cvReleaseMemStorage函數(shù)通過(guò)storage獲取

4、有效的內(nèi)存存儲(chǔ)器的地址，然后釋放該內(nèi)存存儲(chǔ)器的所有空間。該函數(shù)的用法和OpenCV中釋放圖像、釋放矩陣或者釋放其他結(jié)構(gòu)的函數(shù)方法類(lèi)似。cvClearMemStorage函數(shù)則用于清空內(nèi)存存儲(chǔ)器。注意，該函數(shù)是僅有的一種釋放內(nèi)存存儲(chǔ)器中分配的內(nèi)存的方法。該函數(shù)和通常釋放內(nèi)存的函數(shù)區(qū)別是，它只是將釋放的內(nèi)存返還給內(nèi)存存儲(chǔ)器，而并不返還給系統(tǒng)。實(shí)際上，通過(guò)cvClearMemStorage，我們可以很方便地重復(fù)使用內(nèi)存存儲(chǔ)器中內(nèi)存空間。注意，刪除任何動(dòng)態(tài)對(duì)象（如CvSeq、CvSet等）并不會(huì)將內(nèi)存返還給內(nèi)存存儲(chǔ)器（這些結(jié)構(gòu)通過(guò)在內(nèi)部創(chuàng)建一個(gè)內(nèi)存存儲(chǔ)器以達(dá)到內(nèi)存重復(fù)利用的目的）。就像malloc()

5、可以從堆中分配空間一樣，OpenCV中的cvMemStorageAlloc也可以從一個(gè)內(nèi)存存儲(chǔ)器中申請(qǐng)空間。只需要向cvMemStorageAlloc指定一個(gè)內(nèi)存存儲(chǔ)器和要申請(qǐng)的內(nèi)存空間大小，然后返回分配內(nèi)存的地址（返回值和malloc一樣為void指針）。序列序列是內(nèi)存存儲(chǔ)器中可以存儲(chǔ)的一種對(duì)象。序列是某種結(jié)構(gòu)的鏈表。OpenCV中，序列可以存儲(chǔ)多種不同的結(jié)構(gòu)。你可以將序列想象為許多編程語(yǔ)言中都存在的容器類(lèi)或者容器類(lèi)模板（如C+中的vector）。序列在內(nèi)存被實(shí)現(xiàn)為一個(gè)雙端隊(duì)列（deque）。因此序列可以實(shí)現(xiàn)快速的隨機(jī)訪問(wèn)，以及快速刪除頂端的元素，但是從中間刪除元素則稍慢些。序列中有一些重要

6、的屬性（參考例8-1）需要了解。首先，最常用到的是total成員，total存儲(chǔ)序列中保存的數(shù)據(jù)的個(gè)數(shù)。其次是h_prev，h_next，v_prev，和v_next，它們是CV_TREE_NODE_FIELDS的一部分，指向其他的序列（分別為上下左右四個(gè)方向）。這4個(gè)指針不是用來(lái)訪問(wèn)序列中的元素，而是用來(lái)鏈接不同的序列。OpenCV中也有其他的結(jié)構(gòu)包括CV_TREE_NODE_FIELDS，我們可以使用包含CV_TREE_NODE_FIELDS的結(jié)構(gòu)構(gòu)造出更復(fù)雜的結(jié)構(gòu)，例如隊(duì)列、樹(shù)、圖等。僅僅使用變量h_prev和h_next，可實(shí)現(xiàn)一個(gè)簡(jiǎn)單的鏈表。另外兩個(gè)變量v_prev和v_next可以

7、用于創(chuàng)建那些比較密切的復(fù)雜的拓?fù)浣Y(jié)構(gòu)。通過(guò)這四個(gè)變量，函數(shù)cvFindContours可以將圖像中的復(fù)雜的輪廓構(gòu)造為輪廓樹(shù)。例例8-1：結(jié)構(gòu)CvSeq的定義 創(chuàng)建序列創(chuàng)建序列前面已經(jīng)介紹了序列的結(jié)構(gòu)。實(shí)際上，很多OpenCV函數(shù)可以返回序列。當(dāng)然，我們也可以自己用cvCreateSeq函數(shù)手工創(chuàng)建序列。跟OpenCV中的許多對(duì)象一樣，有一個(gè)分配函數(shù)能夠創(chuàng)建一個(gè)序列，并返回指向所創(chuàng)建數(shù)據(jù)結(jié)構(gòu)的指針。這個(gè)函數(shù)是cvCreateSeq()。CvSeq* cvCreateSeq( int seq_flags, int header_size, int elem_size, CvMemStorage*

8、storage);調(diào)用這個(gè)函數(shù)首先需要知道一些信息，這些信息用于控制創(chuàng)建的序列采用何種方式來(lái)組織數(shù)據(jù)。還需要序列的頭大小（通常為sizeof(CvSeq)），以及序列要存儲(chǔ)的元素的大小。最后，還需要為序列指定一個(gè)內(nèi)存存儲(chǔ)器，這樣當(dāng)序列要添加元素時(shí)，便會(huì)從內(nèi)存存儲(chǔ)器申請(qǐng)空間。flags變量可由3個(gè)類(lèi)值組成，不同類(lèi)之間的標(biāo)志可以用或運(yùn)算來(lái)組合。第一類(lèi)確定序列中元素的類(lèi)型，多數(shù)類(lèi)型用戶(hù)可能不熟悉，另外一些類(lèi)型則為OpenCV的內(nèi)部函數(shù)使用。還有一些標(biāo)志僅僅用于特定的元素類(lèi)型，例如CV_SEQ_FLAG_CLOSED通常用于表示一個(gè)閉合的多邊形。 CV_SEQ_ELTYPE_POINT 點(diǎn)坐標(biāo)：(x,

9、 y) CV_SEQ_ELTYPE_CODE Freeman：0.7 CV_SEQ_ELTYPE_PPOINT 指向一個(gè)點(diǎn)的指針： &(x, y) CV_SEQ_ELTYPE_GRAPH_EDGE &next_o,&next_d, &vtx_o, &vtx_d CV_SEQ_ELTYPE_GRAPH_VERTEX first_edge, &(x, y) CV_SEQ_ELTYPE_TRIAN_ATR 二叉樹(shù)的節(jié)點(diǎn) CV_SEQ_ELTYPE_CONNECTED_COMP 聯(lián)通的區(qū)域 CV_SEQ_ELTYPE_POINT3D 三維的點(diǎn)坐標(biāo)：(x,

10、 y, z)第二類(lèi)表示序列本身的性質(zhì)，它可以是下面任意一個(gè)。 CV_SEQ_KIND_SET 元素的集合 CV_SEQ_KIND_CURVE 元素所定義的曲線 CV_SEQ_KIND_BIN_TREE 二叉樹(shù) CV_SEQ_KIND_GRAPH 圖，其節(jié)點(diǎn)為序列內(nèi)元素第三類(lèi)表示序列的其他屬性。 CV_SEQ_FLAG_CLOSED 序列是閉合的（多邊形） CV_SEQ_FLAG_SIMPLE 序列是簡(jiǎn)單的（多邊形） CV_SEQ_FLAG_CONVEX 序列是凸的（多邊形） CV_SEQ_FLAG_HOLE 序列是一個(gè)嵌套的（多邊形）刪除序列刪除序列void cvClearSeq( CvSeq

11、* seq);cvClearSeq可以清空序列中的所有元素。不過(guò)該函數(shù)不會(huì)將不再使用的內(nèi)存返回到內(nèi)存存儲(chǔ)器中，也不會(huì)釋放給系統(tǒng)。但是當(dāng)重新向序列中添加元素時(shí)，可以重復(fù)使用這里面的內(nèi)存塊。如果你想回收序列中的內(nèi)存塊，必須使用cvClearMemStore來(lái)實(shí)現(xiàn)。直接訪問(wèn)序列中的元素直接訪問(wèn)序列中的元素有時(shí)候常常需要訪問(wèn)序列中的某個(gè)元素，這里有幾種訪問(wèn)的方法。最常用同時(shí)也比較正確的方法是通過(guò)cvGetSeqElem()函數(shù)來(lái)隨機(jī)訪問(wèn)某個(gè)元素。char* cvGetSeqElem(seq, index);當(dāng)然還需要將cvGetSeqElem返回的指針轉(zhuǎn)換為序列中實(shí)際存儲(chǔ)的元素的類(lèi)型。下面例子是將一個(gè)

12、保存CvPoint序列中所有的點(diǎn)元素打印出來(lái)（序列可能是cvFindContours返回的輪廓）：for(int i=0; itotal; +i) CvPoint* p = (CvPoint*)cvGetSeqElem(seq, i); printf(“(%d, %d)n”, p-x, p-y);同樣可以檢測(cè)一個(gè)元素是否在序列中，cvSeqElemIdx函數(shù)可以實(shí)現(xiàn)該功能：int cvSeqElemIdx( const CvSeq* seq, const void* element, CvSeqBlock* block = NULL);cvSeqElemIdx函數(shù)是一個(gè)相對(duì)耗時(shí)的操作，因此使用

13、的時(shí)候需要慎重（所花的時(shí)候跟序列的大小成正比）。參數(shù)分別為序列的指針和元素的指針。另外，還有一個(gè)可選的參數(shù)block，如果block不為空則存放包含所指元素的塊的地址。切片、復(fù)制和移動(dòng)序列中的數(shù)據(jù)切片、復(fù)制和移動(dòng)序列中的數(shù)據(jù)cvCloneSeq深度復(fù)制一個(gè)序列，并創(chuàng)建一個(gè)完全獨(dú)立的序列結(jié)構(gòu)。CvSeq* cvCloneSeq( const CvSeq* seq, CvMemStorage* storage = NULL);該函數(shù)是對(duì)cvSeqSlice()進(jìn)行簡(jiǎn)單的包裝。cvSeqSlice()函數(shù)可以為序列中的子序列生成一個(gè)新的序列（深度復(fù)制）；也可以?xún)H僅為子序列創(chuàng)建一個(gè)頭，和原來(lái)序列共用元

14、素空間。CvSeq* cvSeqSlice( const CvSeq* seq, CvSlice slice, CvMemStorage* storage = NULL, int copy_data = 0);cvSeqSlice中有一個(gè)CvSlice類(lèi)型的參數(shù)，對(duì)應(yīng)一個(gè)切片。我們可以用cvSlice(a, b)函數(shù)，或CV_WHOLE_SEQ宏來(lái)定義切片，其中a對(duì)應(yīng)開(kāi)始，b對(duì)應(yīng)結(jié)尾。在創(chuàng)建子序列的時(shí)候，只有切片之間的元素才會(huì)被復(fù)制（b如果為CV_WHOLE_SEQ_END_INDEX則表示序列在a位置后面的所有元素）。參數(shù)copy_data表示是否進(jìn)行深度復(fù)制，如果進(jìn)行深度復(fù)制則要復(fù)制每個(gè)元

15、素。切片同樣可以用來(lái)定義要?jiǎng)h除或添加的序列，分別對(duì)應(yīng)cvSeqRemoveSlice和cvSeqInsertSlice函數(shù)（參數(shù)一致）。void cvSeqRemoveSlice( CvSeq* seq, CvSlice slice);void cvSeqInsertSlice( CvSeq* seq, int before_index, const CvArr* from_arr);使用指定的比較函數(shù)，我們可以對(duì)序列中的元素進(jìn)行排序，或者搜索一個(gè)（排序過(guò)的）序列。元素間的比較函數(shù)需要有以下函數(shù)原型：typedef int (*CvCmpFunc)(const void* a, const v

16、oid* b, void* userdata);a和b為兩個(gè)要排序的元素的指針，userdata對(duì)應(yīng)一個(gè)擴(kuò)展數(shù)據(jù)，可以用來(lái)定義排序或查找的條件。當(dāng)a小于b時(shí)比較函數(shù)返回-1，大于b時(shí)返回1，相等則返回0。定義了比較函數(shù)之后，就可以用cvSeqSort對(duì)序列進(jìn)行排序，也可以用cvSeqSearch來(lái)搜查序列中的元素。如果序列已經(jīng)排序的話，搜索一個(gè)元素的時(shí)間復(fù)雜度為O(log n)。如果序列沒(méi)有排序，則搜索元素的時(shí)間復(fù)雜度為O(n)。如果元素搜索成功，*elem_idx將保存元素在序列中的索引，然后返回對(duì)應(yīng)元素的指針。如果沒(méi)有找到相同的元素則返回NULL。void cvSeqSort( CvSeq

17、* seq, CvCmpFunc func, void* userdata = NULL);char* cvSeqSearch( CvSeq* seq, const void* elem, CvCmpFunc func, int is_sorted, int* elem_idx, void* userdata = NULL);cvSeqInvert可以用于將序列進(jìn)行逆序操作。該函數(shù)不會(huì)修改元素的內(nèi)容，但是會(huì)將序列中的元素重新組織，改為逆序。void cvSeqInvert( CvSeq* seq);根據(jù)用戶(hù)設(shè)定的標(biāo)準(zhǔn)，OpenCV可以通過(guò)cvSeqPartition()函數(shù)拆分序列。該函數(shù)使用

18、類(lèi)似于前面提到比較函數(shù)，但是不同的是如果兩個(gè)參數(shù)相同，則返回非0值；如果不同則返回0（例如用于搜索和排序的函數(shù)的求反）。int cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq* labels, CvCmpFunc is_equal, void* userdata);拆分操作需要申請(qǐng)新的內(nèi)存用于存儲(chǔ)結(jié)果。參數(shù)labels是指向序列指針的指針。當(dāng)cvSeqPartition調(diào)用結(jié)束時(shí)，參數(shù)labels中是一個(gè)整數(shù)序列，序列中元素是跟序列seq中的元素一一對(duì)應(yīng)。這些整數(shù)的值從0開(kāi)始遞增，是拆分后的元素的類(lèi)別標(biāo)志。參數(shù)is_

19、equal對(duì)應(yīng)比較函數(shù)，userdata對(duì)應(yīng)比較函數(shù)的userdata參數(shù)。圖8-1為在一個(gè)100100畫(huà)板上隨機(jī)生成的100個(gè)點(diǎn)。調(diào)用cvSeqPartition對(duì)這些點(diǎn)進(jìn)行處理，比較函數(shù)為2個(gè)點(diǎn)之間的歐幾里得距離，當(dāng)2個(gè)點(diǎn)之間的距離小于5時(shí)返回1，否則返回0。聚類(lèi)結(jié)果以參數(shù)lables中的值作為名字標(biāo)出。圖8-1:100100畫(huà)布上由100個(gè)點(diǎn)組成的序列在距離小于5時(shí)的劃分將序列作為棧來(lái)使用將序列作為棧來(lái)使用如前所述，序列在內(nèi)部其實(shí)對(duì)應(yīng)一個(gè)雙端序列。因此，我們可以高效地從序列的任意一段（開(kāi)頭和結(jié)尾）訪問(wèn)序列。這樣我們可以很自然地將序列當(dāng)成一個(gè)棧使用。與CvSeq結(jié)構(gòu)一起使用，下面的六個(gè)函數(shù)

20、可將序列封裝成一個(gè)棧（準(zhǔn)確地說(shuō)，是雙端隊(duì)列，因此它們可從兩端操作元素）。char* cvSeqPush( CvSeq* seq, void* element = NULL);char* cvSeqPushFront( CvSeq* seq, void* element = NULL);void cvSeqPop( CvSeq* seq, void* element = NULL);void cvSeqPopFront( CvSeq* seq, void* element = NULL);void cvSeqPushMulti( CvSeq* seq, void* elements, int c

21、ount, int in_front = 0);void cvSeqPopMulti( CvSeq* seq, void* elements, int count, int in_front = 0);主要的操作函數(shù)是cvSeqPush()，cvSeqPushFront()，cvSeqPop()和cvSeqPopFront()。因?yàn)樗鼈儾僮餍蛄袃啥?，可以在O(1)時(shí)間完成操作（和序列大小沒(méi)有關(guān)系）。Push函數(shù)返回壓棧的元素指針。Pop函數(shù)彈出棧頂元素，并且可以選擇是否保存彈出的棧頂元素（element不為NULL則保存彈出的元素）。cvSeqPushMulti和cvSeqPopMulti用于

22、一次將多個(gè)元素壓棧和出棧，還有一個(gè)參數(shù)用于指定對(duì)應(yīng)序列的開(kāi)頭還是結(jié)尾。可以用宏來(lái)表示開(kāi)頭和結(jié)尾：CV_FRONT(1)對(duì)應(yīng)開(kāi)頭；CV_BACK(0)對(duì)應(yīng)結(jié)尾。插入和刪除元素插入和刪除元素char* cvSeqInsert( CvSeq* seq, int before_index, void* element = NULL);void cvSeqRemove( CvSeq* seq, int index);可以用cvSeqInsert()和cvSeqRemove()在序列的中間添加和刪除元素。但是請(qǐng)注意，它們的執(zhí)行效率不是很高，具體的時(shí)間依賴(lài)序列中元素的數(shù)目。序列中塊的大小序列中塊的大小當(dāng)剛開(kāi)

23、始看文檔時(shí)，cvSetSeqBlockSize()函數(shù)的作用可能不是很明顯。它的參數(shù)為序列和新內(nèi)存塊的大小，當(dāng)序列中內(nèi)存空間不足要分配新的塊時(shí)，將按照參數(shù)分配塊的大小。塊越大，序列中出現(xiàn)內(nèi)存碎片的可能性就越小，但是內(nèi)存中更多的內(nèi)存可能被浪費(fèi)。默認(rèn)的內(nèi)存塊大小為1K字節(jié)，不過(guò)我們可以隨時(shí)改變塊的大小。void cvSetSeqBlockSize( CvSeq* seq, Int delta_elems);序列的讀取和寫(xiě)入序列的讀取和寫(xiě)入當(dāng)你使用序列時(shí)，如果你需要最高的性能，你可以使用一些特殊的函數(shù)修改序列（使用時(shí)需要特別小心）。這些函數(shù)通過(guò)專(zhuān)門(mén)的結(jié)構(gòu)來(lái)保存序列的當(dāng)前狀態(tài)，這樣使得很多后續(xù)操作可以

24、在更短的時(shí)間內(nèi)完成。保存序列寫(xiě)狀態(tài)的結(jié)構(gòu)為CvSeqWriter。CvSeqWriter結(jié)構(gòu)通過(guò)cvStartWriteSeq函數(shù)初始化，然后由cvEndWriteSeq關(guān)閉寫(xiě)狀態(tài)。當(dāng)序列寫(xiě)狀態(tài)被打開(kāi)的時(shí)候，可以通過(guò)CV_WRITE_SEQ()宏向序列寫(xiě)入元素。通過(guò)CV_WRITE_SEQ()宏寫(xiě)元素比cvSeqPush添加元素的效率更高，但是序列頭中的一些信息并沒(méi)有被即時(shí)刷新。換言之，剛寫(xiě)入的元素對(duì)用戶(hù)來(lái)說(shuō)可能并不能訪問(wèn)。寫(xiě)操作只有在執(zhí)行cvEndWriteSeq函數(shù)后，才會(huì)真正的寫(xiě)到序列中（可以認(rèn)為之前是在緩沖中）。如果必要，用戶(hù)也可以通過(guò)cvFlushSeqWriter()函數(shù)來(lái)顯式刷新

25、寫(xiě)操作，而不需要關(guān)閉寫(xiě)狀態(tài)。void cvStartWriteSeq( int seq_flags, int header_size, int elem_size, CvMemStorage* storage, CvSeqWriter* writer);void cvStartAppendToSeq( CvSeq* seq, CvSeqWriter* writer);CvSeq* cvEndWriteSeq( CvSeqWriter* writer);void cvFlushSeqWriter( CvSeqWriter* writer);CV_WRITE_SEQ_ELEM(elem, writ

26、er);CV_WRITE_SEQ_ELEM_VAR(elem_ptr, writer)這些函數(shù)參數(shù)的含義都是比較明了的。cvStartWriteSeq函數(shù)中的seq_flags，header_size和elem_size參數(shù)和cvCreateSeq函數(shù)的參數(shù)含義相同。cvStartAppendToSeq初始化寫(xiě)狀態(tài)結(jié)構(gòu)到序列的末尾。CV_WRITE_SEQ_ELEM宏則需要一個(gè)要寫(xiě)入的元素（如一個(gè)CvPoint元素）和對(duì)應(yīng)的寫(xiě)狀態(tài)結(jié)構(gòu)指針；該宏首先添加一個(gè)新元素到序列，并將參數(shù)指定的元素復(fù)制到新創(chuàng)建的元素。為了演示上面相關(guān)函數(shù)的用法，我們創(chuàng)建一個(gè)序列，并寫(xiě)入100個(gè)320240矩形區(qū)域中隨機(jī)點(diǎn)

27、：CvSeqWriter writer;cvStartWriteSeq(CV_32SC2, sizeof(CvSeq), sizeof(CvPoint), storage, &writer);for(i=0; ih_next)cvCvtColor(img_8uc1, img_8uc3, CV_GRAY2BGR);cvDrawContours( img_8uc3, c, CVX_RED, CVX_BLUE, 2, /Try different values of max_level, and see what happens 2, 8);printf(Contour #%dn, n);c

28、vShowImage(argv0, img_8uc3);printf(%d elements:n, c-total);for(int i = 0; itotal; +i)CvPoint* p = CV_GET_SEQ_ELEM(CvPoint, c, i);printf(%d, %d)n, p-x, p-y);cvWaitKey(0);n+;printf(Finished all contours.n);cvCvtColor(img_8uc1, img_8uc3, CV_GRAY2BGR);cvShowImage(argv0, img_8uc3);cvWaitKey(0);cvDestroyW

29、indow(argv0);cvReleaseImage(&img_8uc1);cvReleaseImage(&img_8uc3);cvReleaseImage(&img_8uc3);cvReleaseImage(&img_edge);return 0;01深入分析輪廓當(dāng)分析一個(gè)圖像的時(shí)候，針對(duì)輪廓我們也許有很多事情要做。我們對(duì)輪廓常用的操作有識(shí)別和處理，另外相關(guān)的還有多種對(duì)輪廓的處理，如簡(jiǎn)化或擬合輪廓，匹配輪廓到模板，等等。在這一節(jié)中，我們將介紹一些OpenCV函數(shù)，這些函數(shù)或者可以完成我們的任務(wù)，或者可以使得工作變得容易。多邊形逼近多邊形逼近當(dāng)我們繪制一個(gè)多邊

30、形或者進(jìn)行形狀分析的時(shí)候，通常需要使用多邊形逼近一個(gè)輪廓，使得頂點(diǎn)數(shù)目變少。有多種方法可以實(shí)現(xiàn)這個(gè)功能，OpenCV實(shí)現(xiàn)了其中的一種逼近算法。函數(shù)cvApproxPoly是該算法的一種實(shí)現(xiàn)，可以處理輪廓序列。CvSeq* cvApproxPoly( const void* src_seq, int header_size, CvMemStorage* storage, int method, double parameter, int recursive = 0);我們可以傳遞一個(gè)列表或數(shù)狀序列給cvApproxPoly，然后對(duì)其表示的輪廓進(jìn)行處理。函數(shù)的返回值對(duì)應(yīng)第一個(gè)輪廓，同樣我們也可用通

31、過(guò)h_next(以及v_next)來(lái)訪問(wèn)返回的其他的輪廓。因?yàn)閏vApproxPoly在返回結(jié)果的時(shí)候需要?jiǎng)?chuàng)建新的對(duì)象，因此需要指定一個(gè)內(nèi)存存儲(chǔ)器以及頭結(jié)構(gòu)大?。ㄒ话銥閟izeof(CvContour)）。逼近的算法目前只可使用CV_POLY_APPROX_DP(如果其他算法也被實(shí)現(xiàn)的話，可以選擇其他算法)。另外兩個(gè)參數(shù)為逼近算法參數(shù)（目前只用到第一個(gè)）。parameter參數(shù)指定逼近的精度。如果想了這個(gè)參數(shù)如何起作用的，必須仔細(xì)了解具體的算法。最后一個(gè)參數(shù)指定是否針對(duì)全部的輪廓（通過(guò)h_next和v_next可達(dá)的）進(jìn)行逼近。如果為0，則表示只處理src_seq指向輪廓。下面簡(jiǎn)要介紹一下算法

32、的工作原理。參考圖8-5，算法先從輪廓（圖b）選擇2個(gè)最遠(yuǎn)的點(diǎn)，然后將2個(gè)連成一個(gè)線段（圖c），然后再查找輪廓上到線段距離最遠(yuǎn)的點(diǎn)，添加到逼近后的新輪廓（圖d）。算法反復(fù)迭代，不斷將最遠(yuǎn)的點(diǎn)添加到結(jié)果中。直到所有的點(diǎn)到多邊形的最短距離小于parameter參數(shù)指定的精度（圖圖8-5：cvApproxPoly實(shí)現(xiàn)的DP算法的示意圖。（a）為原始圖像，（b）為提取的輪廓，從2個(gè)距離最遠(yuǎn)的點(diǎn)開(kāi)始（c），其他的點(diǎn)的選擇過(guò)程如（d）-（f）所示f）。從這里可以看出，精度和輪廓的周長(zhǎng)，或者外包矩形周長(zhǎng)的幾分之一比較合適。曲線逼近的過(guò)程和尋找關(guān)鍵點(diǎn)（dominant points）的過(guò)程密切相關(guān)。跟曲線上的

33、其他點(diǎn)相比，關(guān)鍵點(diǎn)是那些包含曲線信息比較多的點(diǎn)。關(guān)鍵點(diǎn)在逼近算法以及其他應(yīng)用中都會(huì)涉及。函數(shù)cvFindDominantPoints()實(shí)現(xiàn)了被稱(chēng)為IPAN*Chetverikov99的算法。CvSeq* cvFindDominantPoints( CvSeq* contour, CvMemStorage* storage, int method = CV_DOMINANT_IPAN, double parameter1 = 0, double parameter2 = 0, double parameter3 = 0, double parameter4 = 0);本質(zhì)上，IPAN算法通過(guò)掃

34、描輪廓上并在曲線內(nèi)部使用可能頂點(diǎn)構(gòu)造三角形來(lái)實(shí)現(xiàn)。對(duì)于三角形的大小和張角有特殊要求（圖8-6）。在比某一特定的全局閾值和它的相鄰點(diǎn)的張角小的情況下，具有大張角的點(diǎn)被保留。函數(shù)cvFindDominantPoints()按照慣例使用參數(shù)CvSeq*和CvMemStorage*。并且要求指定一個(gè)方法，和圖8-6：IPAN算法使用三角形abp來(lái)描述點(diǎn)pcvApproxPoly()相同，目前可供選擇的方法只有一個(gè)，就是CV_DOMINANT_IPAN。接下來(lái)的四個(gè)參數(shù)是：最短距離dmin，最長(zhǎng)距離dmax，相鄰距離dn和最大角度max。如圖8-6所示，算法首先把所有兩邊距離rpa和rpb在dmin和d

35、max之間， ab max的三角形找出來(lái)。然后保留對(duì)于距離dn(dn的大小不得超過(guò)dmax)有最小夾角ab的所有點(diǎn)p。dmin, dmax, dn和max的典型值可以是7, 9, 9, 150(最后一個(gè)參數(shù)是以度數(shù)為單位的角的大小)。特性概況特性概況輪廓處理中經(jīng)常遇到的另一個(gè)任務(wù)是計(jì)算一些輪廓變化的概況特性。這可能包括長(zhǎng)度或其他一些反映輪廓整體大小的量度。另一個(gè)有用的特性是輪廓矩（contour moment），可以用來(lái)概括輪廓的總形狀特性（我們下一節(jié)討論）。長(zhǎng)度長(zhǎng)度函數(shù)cvContourPerimeter()作用于一個(gè)輪廓并返回其長(zhǎng)度。事實(shí)上，此函數(shù)是一個(gè)調(diào)用函數(shù)cvArcLength()的

36、宏。double cvArcLength( const void* curve, CvSlice slice = CV_WHOLE_SEQ, int is_closed = -1);#define cvContourPerimeter(contour)cvArcLength(contour, CV_WHOLE_SEQ, 1)cvArcLength(, 的第一個(gè)參數(shù)是輪廓，其形式可以是點(diǎn)的序列（CvContour*或CvSeg*)或任一n2的點(diǎn)的數(shù)組。后邊的參數(shù)是slice，以及表明是否將輪廓視為閉合的一個(gè)布爾類(lèi)型（例如，是否將輪廓的最后一個(gè)點(diǎn)視為和第一個(gè)點(diǎn)有連接）。slice可以讓我們只選擇曲

37、線（curve）上的點(diǎn)的部分集合。一個(gè)和cvArcLength()有緊密關(guān)系的函數(shù)是cvContourArea()，如其名稱(chēng)所示，這個(gè)函數(shù)同于計(jì)算輪廓的面積。函數(shù)的參數(shù)contour和slice和cvArcLength()一樣。double cvContourArea( const CvArr* contour, CvSlice slice = CV_WHOLE_SEQ);邊界框邊界框當(dāng)然長(zhǎng)度和面積只是輪廓的簡(jiǎn)單特性，更復(fù)雜一些的特性描述應(yīng)該是矩形邊界框、圓形邊界框或橢圓形邊界框。有兩種方式可以得到矩形邊界框，圓形與橢圓形邊界框各只有一種方法。CvRect cvBoundingRect( Cv

38、Arr* points, int update = 0);CvBox2D cvMinAreaRect2( const CvArr* points, CvMemStorage* storage = NULL);最簡(jiǎn)單的方法是調(diào)用函數(shù)cvBoundingRect(); 它將返回一個(gè)包圍輪廓的CvRect。第一個(gè)參數(shù)points可以是由點(diǎn)組成的序列，一個(gè)輪廓（CvContour*）或者一個(gè)，n1雙通道的矩陣（CvMat*）。為了理解第二個(gè)參數(shù)update，我們需要想想前面的描述。當(dāng)時(shí)說(shuō)CvContour并不完全等于CvSeq；CvSeq能實(shí)現(xiàn)的CvContour都可以實(shí)現(xiàn)，CvContour甚至能做

39、的更多一點(diǎn)。其中一個(gè)附加功能就是CvRect成員可以記載輪廓自己的邊界框。如果調(diào)用函數(shù)cvBoundingRech()時(shí)參數(shù)update設(shè)置為0，便可以直接從CvContour的成員中獲取邊界框；如果將update設(shè)置為1，邊界框會(huì)被計(jì)算出（CvContour成員的內(nèi)容也會(huì)被更新）。cvBoundingRect()得到的長(zhǎng)方形的一個(gè)問(wèn)題是，CvRect只能表現(xiàn)一個(gè)四邊水平和豎直的長(zhǎng)方形。然而函數(shù)cvMinAreaRect2()可以返回一個(gè)包圍輪廓最小的長(zhǎng)方形，這個(gè)長(zhǎng)方形很可能是傾斜的；請(qǐng)看圖8-7，該函數(shù)的參數(shù)和cvBoundingRect()的相似。OpenCV的數(shù)據(jù)類(lèi)型CvBox2D就是用

40、來(lái)表述這樣的長(zhǎng)方形的。typedef struct CvBox2D CvPoint2D32f center; CvSize2D32f size; float angle;CvBox2D;圖8-7：CvRect只能表示一個(gè)方正的正方形，但CvBox2D可以表示任何傾斜度的正方形圓形和橢圓形邊界圓形和橢圓形邊界接著我們來(lái)看函數(shù)cvMinEnclosingCircle()。該函數(shù)和矩形邊界框的作用基本相同，輸入同樣很靈活，可以是點(diǎn)的序列，也可是二維點(diǎn)的數(shù)組。int cvMinEnclosingCircle( const CvArr* points, CvPoint2D32f* center, flo

41、at* radius);OpenCV里沒(méi)有專(zhuān)門(mén)用來(lái)表示圓的結(jié)構(gòu)，因此需要給函數(shù)cvMinEnclosing-Circle()傳遞中心和浮點(diǎn)型半徑的兩個(gè)指針來(lái)獲取計(jì)算結(jié)果。與最小包圍圓一樣，OpenCV提供一函數(shù)來(lái)擬合一組點(diǎn)，以獲取最佳擬合橢圓。CvBox2D cvFitEllipse2( const CvArr* points);cvMinEnclosingCircle()和cvFitEllipse2()的細(xì)微差別在于，前者只簡(jiǎn)單計(jì)算完全包圍已有輪廓的最小圓，而后者使用擬合函數(shù)返回一個(gè)與輪廓最近似的橢圓。這意味著并不是輪廓中所有的點(diǎn)都會(huì)被包在cvFitEllipse2()返回的橢圓中。該擬合由

42、最小二乘擬合方法算出。橢圓的擬合的結(jié)果由CvBox2D結(jié)構(gòu)體返回，給出的矩形正好完全包圍橢圓，如圖8-8所示。圖8-8：a）10個(gè)點(diǎn)的輪廓與最小包圍圓；b）與最佳擬合橢圓；c）OpenCV給出的表示該橢圓的矩形幾何幾何在處理CvBox2D或多邊形邊界的時(shí)候，經(jīng)常需要進(jìn)行多邊形以及邊界框的重疊判斷。OpenCV提供了一組方便的小函數(shù)用于此類(lèi)幾何測(cè)試。CvRect cvMaxRect( const CvRect* rect1, const CvRect* rect2);void cvBoxPoints( CvBox2D box, CvPoint2D32f pt4);CvSeq* cvPointSe

43、qFromMat( int seq_kind, const CvArr* mat, CvContour* contour_header, CvSeqBlock* block);double cvPointPolygonTest( const CvArr* contour, CvPoint2D32f pt, int measure_dist);第一個(gè)函數(shù)cvMaxRect()根據(jù)輸入的2個(gè)矩形計(jì)算，它們的最小外包矩形。下一個(gè)實(shí)用函數(shù)cvBoxPoints()用于計(jì)算CvBox2D結(jié)構(gòu)表示矩形的4個(gè)頂點(diǎn)。當(dāng)然你也可以自己通過(guò)三角函數(shù)計(jì)算，不過(guò)這很令人頭大，而簡(jiǎn)單調(diào)用一下這個(gè)函數(shù)則可求出。第三個(gè)實(shí)用

44、函數(shù)cvPointSeqFromMat從mat中初始化序列。這在你需要使用輪廓相關(guān)的函數(shù)，但是函數(shù)又不支持矩陣參數(shù)的時(shí)候使用。第一個(gè)參數(shù)用于指定點(diǎn)序列的類(lèi)型，seq_kind可以為以下類(lèi)型：點(diǎn)集為0；曲線為CV_SEQ_KIND_CURVE；封閉曲線為CV_SEQ_KIND_CURVE|CV_SEQ_FLAG_CLOSED。第二參數(shù)是輸入的矩陣，該參數(shù)是連續(xù)的1維向量。矩陣的類(lèi)型必須為CV_32SC2或CV_32FC2。下面的兩個(gè)參數(shù)是指針，指針指向的內(nèi)容通過(guò)該函數(shù)來(lái)填充。contour_header參數(shù)對(duì)應(yīng)輪廓結(jié)構(gòu)，一般需要事先創(chuàng)建，不過(guò)由該函數(shù)負(fù)責(zé)初始化。block參數(shù)同樣如此，也是由該函

45、數(shù)負(fù)責(zé)初始化。最后，該函數(shù)返回一個(gè)類(lèi)型為CvSeq*的序列指針，指向你輸入的序列頭*contour_header。返回值跟輸入?yún)?shù)相同只是為了使用該函數(shù)時(shí)更方便，因?yàn)檫@樣你就可以將該函數(shù)當(dāng)作某個(gè)輪廓函數(shù)的參數(shù)使用，代碼寫(xiě)入同一行。最后一個(gè)平面幾何相關(guān)的函數(shù)是cvPointPolygonTest()，用于測(cè)試一個(gè)點(diǎn)是否在多邊形的內(nèi)部。如果參數(shù)measure_dist非零，函數(shù)返回值是點(diǎn)到多邊形的最近距離。如果measure_dist為0，函數(shù)返回+1、-1、0，分別表示在內(nèi)部、外部、在多邊形邊上。參數(shù)contour可以是序列，也可以是2通道矩陣向量。輪廓的匹配前面介紹了輪廓的一些基礎(chǔ)知識(shí)，并且演

46、示了如果在OpenCV中操作輪廓對(duì)象?，F(xiàn)在我們來(lái)研究一下如何在實(shí)際應(yīng)用中使用輪廓。一個(gè)跟輪廓相關(guān)的最常用到的功能是匹配兩個(gè)輪廓。如果有兩個(gè)輪廓，如何比較它們；或者如何比較一個(gè)輪廓和一個(gè)抽象模板。這兩種情況隨后都會(huì)討論。矩矩比較兩個(gè)輪廓最簡(jiǎn)潔的方式是比較它們的輪廓矩。這里先簡(jiǎn)短介紹一下矩的含義。簡(jiǎn)單地說(shuō)，矩是通過(guò)對(duì)輪廓上所有點(diǎn)進(jìn)行積分運(yùn)算（或者認(rèn)為是求和運(yùn)算）而得到的一個(gè)粗略特征。通常，我們?nèi)缦露x一個(gè)輪廓的（p, q）矩：在公式中p對(duì)應(yīng)x維度上的矩，q對(duì)應(yīng)y維度上的矩，階數(shù)表示對(duì)應(yīng)的部分的指數(shù)。該計(jì)算是對(duì)輪廓邊界上所有像素（數(shù)目為n）進(jìn)行求和。如果p和q全部為0，那么m00實(shí)際上對(duì)應(yīng)輪廓邊界上

47、點(diǎn)的數(shù)目。下面的函數(shù)用于計(jì)算這些輪廓矩：void cvContoursMoments( CvSeq* contour, CvMoments* moments)第一個(gè)參數(shù)是我們要處理的輪廓，第二個(gè)參數(shù)指向一個(gè)結(jié)構(gòu)，該結(jié)構(gòu)用于保存生成的結(jié)果。CvMoments結(jié)構(gòu)定義如下：typedef struct CvMoments /spatial moments double m00, m10, m01, m20, m11, m02, m30, m21, m12, m03; /central moments double mu20, mu11, mu02, mu30, mu21, mu12, mu03;

48、/m00!=0?1/sqrtm00:0 double inv_sqrt_m00;CvMoments;在cvContoursMoments()函數(shù)中，只用到了m00, m01, , m03幾個(gè)參數(shù)；以mu開(kāi)頭的參數(shù)在其他函數(shù)中使用。在使用CvMoments結(jié)構(gòu)的時(shí)候，我們可以使用以下的函數(shù)來(lái)方便地獲取一個(gè)特定的矩：double cvGetSpatialMoment CvMoments* moments, int x_order, int y_order;調(diào)用cvContoursMoments()函數(shù)會(huì)計(jì)算所有3階的矩（m21和m12會(huì)被計(jì)算，但是m22不會(huì)被計(jì)算）。再論矩再論矩剛剛描述的矩計(jì)算給

49、出了一些輪廓的簡(jiǎn)單屬性，可以用來(lái)比較兩個(gè)輪廓。但是在很多實(shí)際應(yīng)用中，剛才的計(jì)算方法得到的矩并不是做比較時(shí)最好的參數(shù)。具體說(shuō)來(lái)，經(jīng)常會(huì)用到歸一化的矩（因此，不同大小但是形狀相同的物體會(huì)有相同的值）。同樣，剛才的小節(jié)中的簡(jiǎn)單的矩依賴(lài)于所選坐標(biāo)系，這意味著物體旋轉(zhuǎn)后就無(wú)法正確匹配。OpenCV提供了計(jì)算Hu不變矩Hu62以及其他歸一化矩的函數(shù)。CvMoments結(jié)構(gòu)可以用cvMoments或者cvContourMoments計(jì)算。并且，cvContourMoments現(xiàn)在只是cvMoments的一個(gè)別名。一個(gè)有用的小技巧是用cvDrawContour()描繪一幅輪廓的圖像后，調(diào)用一個(gè)矩的函數(shù)處理該圖

50、像。使用無(wú)論輪廓填充與否，你都能用同一個(gè)函數(shù)處理。以下是4個(gè)相關(guān)函數(shù)的定義：void cvMoments( const CvArr* image, CvMoments* moments, int isBinary = 0);double cvGetCentralMoment( CvMoments* moments, int x_order, int y_order)double cvGetNormalizedCentralMoment( CvMoments* moments, int x_order, int y_order);void cvGetHuMoments( CvMoments* m

51、oments, CvHuMoments* HuMoments);第一個(gè)函數(shù)除了使用的是圖像（而不是輪廓）作為參數(shù)，其他方面和cvContoursMoments()函數(shù)相同，另外還增加了一個(gè)參數(shù)。增加的參數(shù)isBinary如果為CV_TRUE，cvMoments將把圖像當(dāng)作二值圖像處理，所有的非0像素都當(dāng)作1。當(dāng)函數(shù)被調(diào)用的時(shí)候，所有的矩被計(jì)算（包含中心矩，請(qǐng)看下一段）。除了x和y的值被歸一化到以0為均值，中心距本質(zhì)上跟剛才描述的矩一樣。這兒xavg=m10/m00且yavg=m10/m00歸一化矩和中心矩也基本相同，除了每個(gè)矩都要除以m00的某個(gè)冪：最后來(lái)介紹Hu矩，Hu矩是歸一化中心距的線性

52、組合。之所以這樣做是為了能夠獲取代表圖像某個(gè)特征的矩函數(shù)，這些矩函數(shù)對(duì)某些變化如縮放、旋轉(zhuǎn)和鏡像映射（除了h1）具有不變性。Hu矩是從中心距中計(jì)算得到，其計(jì)算公式如下所示：參考圖8-9和表8-1，我們可以直觀地看到每個(gè)圖像對(duì)應(yīng)的7個(gè)Hu矩。通過(guò)觀察可以發(fā)現(xiàn)當(dāng)階數(shù)變高時(shí)，Hu矩一般會(huì)變小。對(duì)于這一點(diǎn)不必感到奇怪，因?yàn)楦鶕?jù)定義，高階Hu矩由多個(gè)歸一化矩的高階冪計(jì)算得到，而歸一化矩都是小于1的，所以指數(shù)越大，計(jì)算所得的值越小。圖8-9：五個(gè)字符的圖像；觀察它們的Hu矩可以獲取跟字符相關(guān)的一些直觀理解表8-1：在圖8-9中所示的五個(gè)字符的Hu矩的值需要特別注意的是“I”，它對(duì)于180度旋轉(zhuǎn)和鏡面反射都

53、是對(duì)稱(chēng)的，它的h3到h7矩都是0；而“O”具有同樣的對(duì)稱(chēng)特性，所有的Hu矩都是非零的。對(duì)于這個(gè)問(wèn)題，我們留給讀者去思考。您可以仔細(xì)查看字符圖像，比較不同的Hu矩，以獲得這些矩到底如何表達(dá)的直觀感受。使用使用Hu矩進(jìn)行匹配矩進(jìn)行匹配double cvMatchShape( const void* object1, const void* object2, int method, double parameter = 0);很自然，使用Hu矩我們想要比較兩個(gè)物體并且判明它們是否相似。當(dāng)然，可能有很多“相似”的定義。為了使比較過(guò)程變得簡(jiǎn)單，OpenCV的函數(shù)cvMatchShapes()允許我們簡(jiǎn)單

54、地提供兩個(gè)物體，然后計(jì)算它們的矩并根據(jù)我們提供的標(biāo)準(zhǔn)進(jìn)行比較。這些物體可以是灰度圖圖像或者輪廓。如果你提供了圖像，cvMatchShape()會(huì)在對(duì)比的進(jìn)程之前為你計(jì)算矩。cvMatchShapes()使用的方法是表8-2中列出的三種中的一種。表8-2：cvMatchShapes()使用的匹配方法在表中 和 被定義為在這里 和 分別是A和B的Hu矩。對(duì)于對(duì)比度量標(biāo)準(zhǔn)（metric）是如何被計(jì)算的，表8-2中的三個(gè)常量每個(gè)都用了不同的方法。這個(gè)度量標(biāo)準(zhǔn)最終決定了cvMatchShapes()的返回值。最后一個(gè)參數(shù)變量現(xiàn)在不能使用，因此我們可以把它設(shè)成默認(rèn)值0。等級(jí)匹配等級(jí)匹配我們經(jīng)常想要匹配兩個(gè)

55、輪廓，然后用一個(gè)相似度量度來(lái)計(jì)算輪廓所有匹配的部分。使用概況參數(shù)的方法（比如矩）是相當(dāng)快的，但是它們能夠表達(dá)的信息卻不是很多。為了找一個(gè)更精確的相似度量度，首先考慮一下輪廓樹(shù)的結(jié)構(gòu)應(yīng)該會(huì)有幫助。請(qǐng)注意，此處的輪廓樹(shù)（contour tree）不是cvFindContour()函數(shù)返回的多個(gè)輪廓的繼承描述；此處輪廓樹(shù)是用來(lái)描述一個(gè)特定形狀（不是多個(gè)特定形狀）內(nèi)各部分的等級(jí)關(guān)系。類(lèi)似于cvFindContours()這樣的函數(shù)返回多個(gè)輪廓，輪廓樹(shù)（contour tree）并不會(huì)把這些等級(jí)關(guān)系搞混，事實(shí)上，它正是對(duì)于某個(gè)特定輪廓形狀的等級(jí)描述。理解了輪廓樹(shù)的創(chuàng)建會(huì)比較容易理解輪廓樹(shù)。從一個(gè)輪廓?jiǎng)?chuàng)建

56、一個(gè)輪廓樹(shù)是從底端（葉節(jié)點(diǎn)）到頂端（根節(jié)點(diǎn)）的。首先搜索三角形突出或凹陷的形狀的周邊（輪廓上的每一個(gè)點(diǎn)都不是完全和它的相鄰點(diǎn)共線的）。每個(gè)這樣的三角形被一條線段代替，這條線段通過(guò)連接非相鄰點(diǎn)的兩點(diǎn)得到；因此，實(shí)際上三角形或者被削平（例如，圖8-10的三角形D）或者被填滿（三角形C）。每個(gè)這樣的替換把輪廓的頂點(diǎn)減少1，并且給輪廓樹(shù)創(chuàng)建一個(gè)新節(jié)點(diǎn)。如果這樣一個(gè)三角形圖8-10：建立一個(gè)輪廓樹(shù)：第一個(gè)回合，車(chē)的外圍輪廓產(chǎn)生葉節(jié)點(diǎn)A,B,C和D；第二個(gè)回合，產(chǎn)生X和Y（X是A和B的父節(jié)點(diǎn)，Y是C和D的父節(jié)點(diǎn)）的兩側(cè)有原始的邊，那么它就是得到的輪廓樹(shù)的葉子；如果一側(cè)是已存在三角形，那么它就是那個(gè)三角形的

57、父節(jié)點(diǎn)。這個(gè)過(guò)程的迭代最終把物體的外形減成一個(gè)四邊形，這個(gè)四邊形也被剖開(kāi)；得到的兩個(gè)三角形是根節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)。結(jié)果的二分樹(shù)（圖8-11）最終將原始輪廓的形狀信息編碼。每個(gè)節(jié)點(diǎn)被它所對(duì)應(yīng)的三角形的信息（比如三角形的大小，它的生成是被切出來(lái)還是被填進(jìn)去的，這樣的信息）所注釋。這些樹(shù)一旦被建立，就可以很有效的對(duì)比兩大輪廓。這個(gè)過(guò)程開(kāi)始于定義兩個(gè)樹(shù)節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系，然后比較對(duì)應(yīng)節(jié)點(diǎn)的特性。最后的結(jié)果就是兩個(gè)樹(shù)的相似度。事實(shí)上，我們基本不需要理解這個(gè)過(guò)程。OpenCV提供一個(gè)函數(shù)從普通的CvContour對(duì)象自動(dòng)生成輪廓樹(shù)并轉(zhuǎn)化返回；還提供一個(gè)函數(shù)用來(lái)對(duì)比兩個(gè)樹(shù)。不幸的是，建立的輪廓樹(shù)并不太魯棒（例如，

58、輪廓上很小的改變可能會(huì)徹底改變結(jié)果的樹(shù)）。同時(shí)，最初的三角形（樹(shù)的根節(jié)點(diǎn)）是隨意選取的。因此，為了得到較好的描述需要首先使用函數(shù)cvApproxPoly()之后將輪廓排列（運(yùn)用循環(huán)移動(dòng)）成最初的三角形不怎么受到旋轉(zhuǎn)影響的狀態(tài)。CvContourTree* cvCreateContourTree( const CvSeq* contour, CvMemStorage* storage, double threshold);CvSeq* cvContourFromContourTree( const CvContourTree* tree, CvMemStorage* storage, CvTer

59、mCriteria criteria);double cvMatchContourTrees( const CvContourTree* tree1, const CvContourTree* tree2, int method, double threshold);這個(gè)代碼提到了CvTermCriteria()，該函數(shù)的細(xì)節(jié)將在第9章給出?，F(xiàn)在你可以用下面的默認(rèn)值（或相似的）使用cvTermCriteria()簡(jiǎn)單建立一個(gè)結(jié)構(gòu)體。CvTermCriteria termcrit = cvTermCriteria( CV_TERMCRIT_ITER|CV_TERMCRIT_EPS, 5, 1);

60、 圖8-11：二分樹(shù)描述的是像圖8-10那樣的輪廓輪廓的凸包和凸缺陷輪廓的凸包和凸缺陷另一個(gè)理解物體形狀或輪廓的有用的方法是計(jì)算一個(gè)物體的凸包（convex hull）然后計(jì)算其凸缺陷（convexity defects）Homma85。很多復(fù)雜物體的特性能很好的被這種缺陷表現(xiàn)出來(lái)。圖8-12用人手圖舉例說(shuō)明了凸缺陷這一概念。手周?chē)钌木€描畫(huà)出了凸包，A到H被標(biāo)出的區(qū)域是凸包的各個(gè)“缺陷”。正如所看到的，這些凸度缺陷提供了手以及手狀態(tài)的特征表現(xiàn)的方法。#define CV_CLOCKWISE 1#define CV_COUNTER_CLOCKWISE 2CvSeq* cvConvexHull2( const CvArr* input, void* hull_storag