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

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

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

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

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

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

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

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

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

9、 y) CV_SEQ_ELTYPE_CODE Freeman：0.7 CV_SEQ_ELTYPE_PPOINT 指向一個點的指針： &(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 二叉樹的節(jié)點 CV_SEQ_ELTYPE_CONNECTED_COMP 聯(lián)通的區(qū)域 CV_SEQ_ELTYPE_POINT3D 三維的點坐標(biāo)：(x,

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

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

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

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

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

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

16、oid* b, void* userdata);a和b為兩個要排序的元素的指針，userdata對應(yīng)一個擴(kuò)展數(shù)據(jù)，可以用來定義排序或查找的條件。當(dāng)a小于b時比較函數(shù)返回-1，大于b時返回1，相等則返回0。定義了比較函數(shù)之后，就可以用cvSeqSort對序列進(jìn)行排序，也可以用cvSeqSearch來搜查序列中的元素。如果序列已經(jīng)排序的話，搜索一個元素的時間復(fù)雜度為O(log n)。如果序列沒有排序，則搜索元素的時間復(fù)雜度為O(n)。如果元素搜索成功，*elem_idx將保存元素在序列中的索引，然后返回對應(yīng)元素的指針。如果沒有找到相同的元素則返回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ù)不會修改元素的內(nèi)容，但是會將序列中的元素重新組織，改為逆序。void cvSeqInvert( CvSeq* seq);根據(jù)用戶設(shè)定的標(biāo)準(zhǔn)，OpenCV可以通過cvSeqPartition()函數(shù)拆分序列。該函數(shù)使用

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

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

20、可將序列封裝成一個棧（準(zhǔn)確地說，是雙端隊列，因此它們可從兩端操作元素）。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()。因為它們操作序列兩端，可以在O(1)時間完成操作（和序列大小沒有關(guān)系）。Push函數(shù)返回壓棧的元素指針。Pop函數(shù)彈出棧頂元素，并且可以選擇是否保存彈出的棧頂元素（element不為NULL則保存彈出的元素）。cvSeqPushMulti和cvSeqPopMulti用于

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

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

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

25、寫操作，而不需要關(guān)閉寫狀態(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初始化寫狀態(tài)結(jié)構(gòu)到序列的末尾。CV_WRITE_SEQ_ELEM宏則需要一個要寫入的元素（如一個CvPoint元素）和對應(yīng)的寫狀態(tài)結(jié)構(gòu)指針；該宏首先添加一個新元素到序列，并將參數(shù)指定的元素復(fù)制到新創(chuàng)建的元素。為了演示上面相關(guān)函數(shù)的用法，我們創(chuàng)建一個序列，并寫入100個320240矩形區(qū)域中隨機點

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)分析一個圖像的時候，針對輪廓我們也許有很多事情要做。我們對輪廓常用的操作有識別和處理，另外相關(guān)的還有多種對輪廓的處理，如簡化或擬合輪廓，匹配輪廓到模板，等等。在這一節(jié)中，我們將介紹一些OpenCV函數(shù)，這些函數(shù)或者可以完成我們的任務(wù)，或者可以使得工作變得容易。多邊形逼近多邊形逼近當(dāng)我們繪制一個多邊

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

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

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

33、其他點相比，關(guān)鍵點是那些包含曲線信息比較多的點。關(guān)鍵點在逼近算法以及其他應(yīng)用中都會涉及。函數(shù)cvFindDominantPoints()實現(xiàn)了被稱為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算法通過掃

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

35、max之間， ab max的三角形找出來。然后保留對于距離dn(dn的大小不得超過dmax)有最小夾角ab的所有點p。dmin, dmax, dn和max的典型值可以是7, 9, 9, 150(最后一個參數(shù)是以度數(shù)為單位的角的大小)。特性概況特性概況輪廓處理中經(jīng)常遇到的另一個任務(wù)是計算一些輪廓變化的概況特性。這可能包括長度或其他一些反映輪廓整體大小的量度。另一個有用的特性是輪廓矩（contour moment），可以用來概括輪廓的總形狀特性（我們下一節(jié)討論）。長度長度函數(shù)cvContourPerimeter()作用于一個輪廓并返回其長度。事實上，此函數(shù)是一個調(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(, 的第一個參數(shù)是輪廓，其形式可以是點的序列（CvContour*或CvSeg*)或任一n2的點的數(shù)組。后邊的參數(shù)是slice，以及表明是否將輪廓視為閉合的一個布爾類型（例如，是否將輪廓的最后一個點視為和第一個點有連接）。slice可以讓我們只選擇曲

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

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

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

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

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

42、最小二乘擬合方法算出。橢圓的擬合的結(jié)果由CvBox2D結(jié)構(gòu)體返回，給出的矩形正好完全包圍橢圓，如圖8-8所示。圖8-8：a）10個點的輪廓與最小包圍圓；b）與最佳擬合橢圓；c）OpenCV給出的表示該橢圓的矩形幾何幾何在處理CvBox2D或多邊形邊界的時候，經(jīng)常需要進(jìn)行多邊形以及邊界框的重疊判斷。OpenCV提供了一組方便的小函數(shù)用于此類幾何測試。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);第一個函數(shù)cvMaxRect()根據(jù)輸入的2個矩形計算，它們的最小外包矩形。下一個實用函數(shù)cvBoxPoints()用于計算CvBox2D結(jié)構(gòu)表示矩形的4個頂點。當(dāng)然你也可以自己通過三角函數(shù)計算，不過這很令人頭大，而簡單調(diào)用一下這個函數(shù)則可求出。第三個實用

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

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

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

47、點的數(shù)目。下面的函數(shù)用于計算這些輪廓矩：void cvContoursMoments( CvSeq* contour, CvMoments* moments)第一個參數(shù)是我們要處理的輪廓，第二個參數(shù)指向一個結(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幾個參數(shù)；以mu開頭的參數(shù)在其他函數(shù)中使用。在使用CvMoments結(jié)構(gòu)的時候，我們可以使用以下的函數(shù)來方便地獲取一個特定的矩：double cvGetSpatialMoment CvMoments* moments, int x_order, int y_order;調(diào)用cvContoursMoments()函數(shù)會計算所有3階的矩（m21和m12會被計算，但是m22不會被計算）。再論矩再論矩剛剛描述的矩計算給

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

50、像。使用無論輪廓填充與否，你都能用同一個函數(shù)處理。以下是4個相關(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);第一個函數(shù)除了使用的是圖像（而不是輪廓）作為參數(shù)，其他方面和cvContoursMoments()函數(shù)相同，另外還增加了一個參數(shù)。增加的參數(shù)isBinary如果為CV_TRUE，cvMoments將把圖像當(dāng)作二值圖像處理，所有的非0像素都當(dāng)作1。當(dāng)函數(shù)被調(diào)用的時候，所有的矩被計算（包含中心矩，請看下一段）。除了x和y的值被歸一化到以0為均值，中心距本質(zhì)上跟剛才描述的矩一樣。這兒xavg=m10/m00且yavg=m10/m00歸一化矩和中心矩也基本相同，除了每個矩都要除以m00的某個冪：最后來介紹Hu矩，Hu矩是歸一化中心距的線性

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

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

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

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

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

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

58、輪廓上很小的改變可能會徹底改變結(jié)果的樹）。同時，最初的三角形（樹的根節(jié)點）是隨意選取的。因此，為了得到較好的描述需要首先使用函數(shù)cvApproxPoly()之后將輪廓排列（運用循環(huán)移動）成最初的三角形不怎么受到旋轉(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);這個代碼提到了CvTermCriteria()，該函數(shù)的細(xì)節(jié)將在第9章給出?，F(xiàn)在你可以用下面的默認(rèn)值（或相似的）使用cvTermCriteria()簡單建立一個結(jié)構(gòu)體。CvTermCriteria termcrit = cvTermCriteria( CV_TERMCRIT_ITER|CV_TERMCRIT_EPS, 5, 1);

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