1 摘要

盡管如Canny邊緣檢測器等算法能夠用于尋找圖像中分割不同區(qū)域的邊緣像素，但是這些算法并未將這些邊緣像素看作為一個整體，從而揭露更多的信息。通常下一步需要將這些邊緣像素組裝成為輪廓阵赠，OpneCV中實現(xiàn)該功能的函數(shù)是cv::findCountours()。在本章開始我們將先介紹一些在使用該函數(shù)之前需要知道的基本知識肌稻，然后再介紹該函數(shù)的使用方法豌注，最后介紹通過計算出的輪廓能夠實現(xiàn)的更復雜的計算機視覺任務。

2 輪廓查找

輪廓是一系列點點合集灯萍，它以某種方式表示圖像中的一條曲線。在不同環(huán)境下其表示方式也不同每聪，在OpenCV中使用標準模版庫的向量容器vector<>表示旦棉，向量中的每個元素都包含曲線中下一個點的位置信息。盡管2維點坐標組成的序列(vector<cv::Point>, vector<cv::Point2f>)是最常見的表示方法药薯，但是還有其他方法可以表示輪廓绑洛。如在Freeman Chain中，每個點表示的就是相對于前一個點在某個特定方向上的位移童本，在后文遇到這些方法的時候還會詳細介紹≌嫱停現(xiàn)在只需要知道輪廓幾乎總是以標準模版庫的向量容器表示的，但是其中的元素不一定是最常用的cv::Point穷娱。

函數(shù)cv::findCountours()可以處理由Canny邊緣檢測器得到的結果绑蔫，也可以處理通過閾值函數(shù)cv::threshold()和cv::adaptiveThreshold()得到的二值圖运沦，對于后者情況而言得到的輪廓將是1值和非0值的邊界，處理邊緣圖像和二值圖像是有一定差異的配深，詳細信息將在下文介紹携添。

2.1 輪廓層次

在介紹如何提取輪廓之前還是有必須先了解輪廓是什么，以及輪廓組之間的是如何關聯(lián)的篓叶。尤其值得關注的是輪廓樹(Contour Tree)的概念烈掠，它對理解函數(shù)cv::findCountours()很重要。在下圖中缸托，左側是一副測試圖像左敌，它由幾塊通過A-E表示的顏色的區(qū)域和白色背景組成。右上角是通過函數(shù)cv::findCountours()找到的輪廓俐镐，這些輪廓通過cX或者hX的標簽表示矫限。其中C表示的是輪廓Countour(這里先理解為顏色區(qū)域的外輪廓)，它表示邊緣圍成的區(qū)域外部是白色京革。而H表示Hole(這里先理解為顏色區(qū)域的內輪廓)奇唤，它表示邊緣圍城的區(qū)域外部是暗色部分。

包含的概念在很多應用中都很重要匹摇，因此OpenCV可以支持輸出輸出如上圖右下角表示的輪廓樹咬扇，該結構包含了輪廓之間的包含關系。在該輪廓樹中廊勃，c0輪廓為根節(jié)點懈贺，它直接包含的輪廓h00和h01是它的子節(jié)點，然后依次表示出測試圖中的所有輪廓坡垫。當然輪廓層次的組織方式處理輪廓樹外還有其他的方式梭灿，將在下文介紹。

表示樹結構的方式有很多冰悠，在OpenCV中是使用由向量元素組成的向量來表示堡妒，每個向量元素的類型為cv::Vec4i。每個向量元素的子元素都有特殊的含義溉卓，都表示與當前索引對應的輪廓有某種關系的輪廓的索引皮迟。如果子元素對應的特殊關系的輪廓不存在，則該子元素的值為-1桑寨。例如在上圖的輪廓樹結構中伏尼，根節(jié)點即索引值為0的節(jié)點是沒有父節(jié)點的，即沒有包含該輪廓的輪廓尉尾，因此該向量元素表示父節(jié)點的子元素將被設置為1爆阶。

向量不同索引位置的子元素表示的映射關系如下。

此時再看上圖中右下角的輪廓樹辨图，節(jié)點之間的連線都表示在輪廓樹輸出向量中班套，向量內每個元素的對應索引位置子元素值指向的節(jié)點。

需要注意的是使用函數(shù)cv::findCountours()處理通過函數(shù)cv::canny()等邊緣檢測函數(shù)得到的結果徒役，與處理如上圖中的二值測試圖像不同的是孽尽，輪廓查找函數(shù)并不能將邊緣圖像中的白色的曲線識別為輪廓，而是識別成狹小的色塊忧勿，因此在得到每條外部輪廓時幾乎總能同時得到一條內部輪廓杉女，你可以將它看作是白色到黑色區(qū)域到過度，標識著邊緣的外部邊界鸳吸。

2.2 提取輪廓

OpenCV中提供的構建輪廓的函數(shù)原型如下熏挎，需要注意構建輪廓的同時允許生成輪廓結構，輪廓結構的表示方式不限于輪廓樹晌砾。

// image：待提取輪廓的圖像坎拐，8位單通道圖像
// contours：檢測到的輪廓，包含STL向量元素的STL向量养匈，其中每個向量元素包含一個輪廓的所有點哼勇，
//           具體點的組織方式和method相關，下文介紹
// hierarchy：輪廓的層級信息呕乎，具體含義和mode相關积担，下文介紹
// mode：輪廓層級構建的方法，下文介紹
// method：輪廓表達的方法猬仁，下文介紹
// offset：檢測到的輪廓沒個點上施加的位移量
void cv::findContours(cv::InputOutputArray image,
                      cv::OutputArrayOfArrays contours, cv::OutputArray hierarchy,
                      int mode, int method, cv::Point offset = cv::Point());

void cv::findContours(cv::InputOutputArray image,
                      cv::OutputArrayOfArrays contours,
                      int mode, int method, cv::Point offset = cv::Point());

輸入圖像image必須是單通道帝璧，數(shù)據(jù)類型為8U，它會被處理成二值圖像湿刽，即所有非零像素含義都相同的烁。函數(shù)運行后會修改該圖像的數(shù)據(jù)，因此如果你還需要使用該圖像诈闺，請拷貝一份圖像作為函數(shù)參數(shù)渴庆。

參數(shù)hierarchy為檢測到的輪廓構建出的層級關系，他是一個STL的向量雅镊，其中的每個元素都是vec4i數(shù)據(jù)把曼，hierarchy[i]表示與contours[i]表示的輪廓直接連接的輪廓信息蝌借，每個vec4i數(shù)據(jù)的子元素都表示了對應關系連接到的輪廓的索引。每個子元素表示的映射關系在上文的表中已經(jīng)描述悼沿。

參數(shù)mode指定了輪廓提取的方式凫岖，可選的值有如下4種。當指定為cv::RETR_EXTERNAL表示只提取最外層的輪廓浮声，因此對于測試圖像而言只有一個最外層輪廓怨咪，因此在下圖的輪廓層級關系中該輪廓也沒有任何相連的輪廓拭荤。

當指定為cv::RETR_LIST時表示提取所有輪廓并以列表的方式組織僚饭，如在下圖中將上圖測試圖像中的輪廓所有層都壓縮為單一層震叮，并且輪廓依序連接，參數(shù)hierarchy中的每個元素的vec4i數(shù)據(jù)的第1個和第2個子元素被用于表示相互連接的節(jié)點鳍鸵。需要注意在新版本的OpenCV中不推薦使用該方法苇瓣，因為contours參數(shù)包含的數(shù)據(jù)是通過向量組織的，本身就可以看作是一個列表偿乖。

當指定為cv::RETR_CCOMP時击罪，輪廓將被分為兩層，其中所有外輪廓依序排列在上層贪薪，內輪廓在下層媳禁。外輪廓包含的第一個直屬輪廓使用vec4i數(shù)據(jù)的第3和第4個子元素表示，同層的內輪廓或外輪廓之間使用vec4i數(shù)據(jù)的第1和第2個子元素表示画切。

當指定為cv::RETR_TREE時表示使用輪廓樹組織所有的輪廓竣稽，此時最外層的輪廓在第一層，向下包含其內部的內輪廓或者外輪廓霍弹，并使用vec4i數(shù)據(jù)的第3和第4個子元素表示連接關系毫别。某個外輪廓包含的直屬內輪廓之間使用vec4i數(shù)據(jù)的第1和第2個子元素表示，如下圖中的1號和2號內輪廓都時0號外輪廓的直屬內輪廓典格。

參數(shù)method決定了參數(shù)contours返回的輪廓點是如何組織的岛宦，其可選值如下。當設置為cv::CHAIN_APPROX_NONE時會返回輪廓的所有點钝计，設置為該選項時將會得到大量的頂點恋博。當設置為cv::CHAIN_APPROX_SIMPLE時只包含線段的端點，在大多數(shù)情況下這種方式都能減少返回的頂點樹私恬，在輪廓為矩形的極端場景下债沮，設置改選項后只會返回矩陣的四個頂點。當設置為cv::CHAIN_APPROX_TC89_L1或者cv::CHAIN_APPROX_TC89_KC05時表示使用對應的Teh-Chin鏈逼近算法本鸣。如果感興趣算法的具體實現(xiàn)可以閱讀論文《On the Dectation of Dominant Points on Digital Curve》疫衩，由于該算法的實現(xiàn)不受參數(shù)影響因此這里不詳細介紹。該算法更復雜并且計算量更大荣德，但是對于通用的曲線它可以有效的降低返回的頂點數(shù)量闷煤。

參數(shù)offset用于平移最終計算得到的頂點坐標，當你在一副圖像的局部提取到輪廓后涮瞻，想將結果轉換到整幅圖片的坐標系中鲤拿，或者相反情況下你想將全局坐標轉換到局部坐標系下時，可以使用該參數(shù)署咽。

2.3 繪制輪廓

當?shù)玫捷喞獢?shù)據(jù)后可能最想做的事情就是繪制出這些輪廓近顷，OpenCV中繪制輪廓的函數(shù)原型如下生音。

// image：輪廓繪制的背景圖片
// contours：輪廓數(shù)據(jù)，包含多組輪廓點的STL向量的STL向量
// contourIdx：需要繪制的輪廓索引窒升，設置為-1時繪制所有輪廓缀遍，但是還是會受參數(shù)maxLevel的限制
// color：輪廓繪制的顏色
// thickness：輪廓繪制的線寬，設置為-1時會填充輪廓
// lineType：線段鏈接類型饱须，4鄰域或者8鄰域或者抗拒值cv:AA
// hierarchy：輪廓層級信息域醇，通過函數(shù)findContours獲取
// maxLevel：繪制的最大輪廓層級，下文介紹
// offset：輪廓點的偏移量
void cv::drawContours(cv::InputOutputArray image,
                      cv::InputArrayOfArrays contours, int contourIdx,
                      const cv::Scalar& color, int thickness = 1, int lineType = 8,
                      cv::InputArray hierarchy = noArray(), int maxLevel = INT_MAX,
                      cv::Point offset = cv::Point())

參數(shù)hierarchy提供了輪廓的層級信息蓉媳，而maxLevel可以指定繪制的輪廓層級譬挚，即從contourIdx指定的層向下再繪制maxLevel層。當你使用cv::RETR_TREE表示輪廓層級信息時使用這兩個參數(shù)組合能夠繪制出你想要的輪廓督怜。另外在使用cv::RETR_CCOMP組織輪廓層級時殴瘦，使用這兩個參數(shù)組合也能很容易的繪制出外輪廓而忽略內輪廓。

示例程序TrackBarContour通過一個滑動條設置一個簡單閾值号杠，然后從閾值處理后的圖像中提取輪廓蚪腋，其核心代碼如下。

// 原圖灰度圖
cv::Mat g_gray;
// 閾值處理后的二值圖姨蟋，用于查詢輪廓
cv::Mat g_binary;
// 閾值處理使用的閾值
int g_thresh = 100;

// 滾動條的事件回調函數(shù)
void on_trackbar(int, void *) {
    // 生成二值圖
    cv::threshold(g_gray, g_binary, g_thresh, 255, cv::THRESH_BINARY);
    cv::imshow("Binary", g_binary);

    // 獲取輪廓
    std::vector<std::vector<cv::Point>> contours;
    cv::findContours(g_binary, contours, cv::noArray(), cv::RETR_LIST, 
                     cv::CHAIN_APPROX_SIMPLE);
    
    // 清空二值圖
    g_binary = cv::Scalar::all(0);
    // 繪制輪廓
    cv::drawContours(g_binary, contours, -1, cv::Scalar::all(255));
    cv::imshow("Contours", g_binary);
}

int main(int argc, const char * argv[]) {
    // 讀取原始圖像
    g_gray = cv::imread(argv[1], cv::IMREAD_GRAYSCALE);
    cv::imshow("Original", g_gray);
    
    // 創(chuàng)建UI控件
    cv::namedWindow("Contours", 1);
    cv::createTrackbar("Threshold", "Contours", &g_thresh, 255, on_trackbar);
    // 手動調用滑動條觸發(fā)函數(shù)
    on_trackbar(g_thresh, nullptr);
    // 掛起程序屉凯，等待用戶輸入事件
    cv::waitKey();
    
    return 0;
}

該程序使用默認閾值運行后顯示的原圖、二值圖和輪廓圖分別如下眼溶。

示例程序ContourPer首先查找了圖像中的所有輪廓悠砚，并計算每個輪廓的面積并根據(jù)面積排序，通過用戶鍵盤輸入事件控制每次只繪制一條輪廓堂飞。在該示例程序中可以通過修改查找輪廓函數(shù)cv::findContours()的參數(shù)mode控制輪廓層級的組織方式灌旧，輪廓繪制函數(shù)cv::drawContours()的參數(shù)maxLevel控制輪廓繪制的層級來更好理解這兩個參數(shù)的組合效果。程序的核心代碼如下绰筛。

// 用于比較兩個輪廓的結構體
struct AreaCmp {
public:
    // 構造函數(shù)
    AreaCmp(const std::vector<float>& _areas) : areas(&_areas) {}
    // 重載std::sort()函數(shù)需要使用到的運算符
    bool operator()(int a, int b) const {
        return (*areas)[a] > (*areas)[b];
    }
private:
    // 保存所有輪廓的區(qū)域
    const std::vector<float>* areas;
};

int main(int argc, const char * argv[]) {
    // 加載圖片
    cv::Mat img = cv::imread(argv[1], cv::IMREAD_GRAYSCALE);
    // 得到閾值圖像
    cv::Mat img_edge;
    cv::threshold(img, img_edge, 128, 255, cv::THRESH_BINARY);
    cv::imshow("Image after threshold", img_edge);
    
    // 查找輪廓
    std::vector<std::vector<cv::Point>> contours;
    std::vector<cv::Vec4i> hierarchy;
    cv::findContours(img_edge, contours, hierarchy, cv::RETR_LIST, 
                     cv::CHAIN_APPROX_SIMPLE);

    // 根據(jù)輪廓的面積降序排序
    std::vector<int> sortIdx(contours.size());
    std::vector<float> areas(contours.size());
    for (int n = 0; n < (int)contours.size(); n++) {
        sortIdx[n] = n;
        areas[n] = cv::contourArea(contours[n], false);
    }
    std::sort(sortIdx.begin(), sortIdx.end(), AreaCmp(areas));
    
    // 繪制單條輪廓
    cv::Mat img_color;
    for (int n = 0; n < (int)sortIdx.size(); n++) {
        int idx = sortIdx[n];
        cv::cvtColor(img, img_color, cv::COLOR_GRAY2BGR);
        // Try different values of max_level, and see what happens
        cv::drawContours(img_color, contours, idx,
                         cv::Scalar(0,0,255), 2, 8, hierarchy, 0);
        cv::imshow(argv[0], img_color);
        int key = cv::waitKey();
        // 如果輸入ESC鍵枢泰，則退出循環(huán)
        if ((key & 255) == 27) {
            break;
        }
    }

    return 0;
}

示例程序的運行結果如下圖，分別是原圖铝噩、閾值圖和繪制的輪廓圖衡蚂。

2.4 快速連通區(qū)域分析

與輪廓區(qū)域緊密相關的另一個方法是聯(lián)通區(qū)域分析(Connected Component Analysis)。使用某些方法特別是閾值法分割圖像后骏庸，可以使用聯(lián)通區(qū)域分析方法處理和分離生成圖像中的區(qū)域毛甲。OpenCV提供的連通區(qū)域分析法的輸入是一張二值圖像，輸出帶標記的像素圖具被，其中同一個連通區(qū)域內的非零向量會分配到相同的唯一標記玻募。例如在本章開始的例子給出的附圖中共存在5個連通區(qū)域，其中最大的一個區(qū)域包含兩個孔一姿，次大的兩個區(qū)域各包含一個孔七咧，最小的兩個區(qū)域不包含孔改执。連通區(qū)域分析發(fā)在背景分割算法中常作為后處理濾鏡，用于移除小的噪聲塊(即大輪廓中的微小閉合輪廓可以被認為是噪聲塊坑雅，它們可以都被處理成為背景)。另外在一些已知待提取前景區(qū)域的算法如OCR中衬横，連通區(qū)域分析算法中也常被使用裹粤。

當然除了使用OpenCV提供的連通區(qū)域分析函數(shù)外，可以使用函數(shù)cv::findContours()并將輪廓組織方式設置為設置cv::RETR_CCOMP提取輪廓(一條外輪廓扣除掉內部的輪廓包圍區(qū)域后就是一個連通區(qū)域)蜂林，然后在得到的連通區(qū)域上循環(huán)調用函數(shù)cv::drawContours()并設置填充顏色為連通區(qū)域的標記遥诉，并將線寬設置為-1。這種方式效率更低噪叙，主要包含以下幾個原因矮锈。

• 函數(shù)cv::findContours()需要為每個輪廓創(chuàng)建一個標準庫向量，而一副圖片中包含的輪廓可以是幾百條睁蕾、甚至幾千條苞笨。
• 當想要填充一個非凸區(qū)域時，函數(shù)cv::drawContorus()的效率也很低子眶，需要根據(jù)輪廓構建并排序圍繞該區(qū)域 的所有細小線段瀑凝。
• 收集連通區(qū)域的一些如面積和圍繞矩形等基本信息也需要額外的，有時甚至是昂貴的函數(shù)調用臭杰。

OpenCV提供的連通區(qū)域分析函數(shù)能夠快速的幫助我們快速的實現(xiàn)上述冗長復雜的邏輯粤咪，其函數(shù)原型如下渴杆。

// 返回值：連通區(qū)域的數(shù)量
// image：待分析的二值圖像寥枝，單通道，數(shù)據(jù)類型為8U
// labels：連通區(qū)域分析的結果
// connectivity：連通性判定的方法磁奖，4鄰域或者8鄰域
// ltype：分析結果矩陣的元素基本數(shù)據(jù)類型囊拜，可以是CV_32S或者CV_16U
int cv::connectedComponents(cv::InputArrayn image, cv::OutputArray labels,
                            int connectivity = 8, int ltype = CV_32S);

// stats：統(tǒng)計結果，N??5矩陣点寥，N和連通區(qū)域數(shù)量相同艾疟，5列分別表示包圍連通區(qū)域的最小矩形
//        的（頂點坐標x，y敢辩，寬蔽莱，高，面積）
// centroids：質心統(tǒng)計結果戚长，N??2矩陣盗冷，基本數(shù)據(jù)類型為CV_64F，2列分別表示質心坐標x同廉，y
//            如果不需要返回質心仪糖，傳入cv::noArray()
int cv::connectedComponentsWithStats(cv::InputArrayn image, cv::OutputArray labels,
                                     cv::OutputArray stats,
                                     cv::OutputArray centroids,
                                     int connectivity = 8, int ltype = CV_32S);

該函數(shù)內部不會調用函數(shù)cv::findContours()和cv::drawContorus()柑司，而是使用一種高效算法直接分析連通區(qū)域，該算法發(fā)表在論文《Two Strategies to Speed Up Connected Component Labeling Algorithms》中锅劝。

示例ConnectedComponents繪制了帶標記的連通區(qū)域攒驰，并移除了其中面積較小的元素，其核心代碼如下故爵。

int main(int argc, const char * argv[]) {
    // 加載原始圖片
    cv::Mat img = cv::imread(argv[1], cv::IMREAD_GRAYSCALE);
    cv::imshow("Source Image", img);
    
    // 生成閾值圖
    cv::Mat img_edge;
    cv::threshold(img, img_edge, 128, 255, cv::THRESH_BINARY);
    cv::imshow("Image after threshold", img_edge);
    
    // 分析連通區(qū)域
    cv::Mat labels, stats, centroids;
    int nccomps = cv::connectedComponentsWithStats(img_edge, labels, 
                                                   stats, centroids);
    std::cout << "Total Connected Components Detected: " << nccomps << std::endl;

    // 為每個連通區(qū)域分配一個隨機顏色玻粪，labels中的標記對應為顏色表內的索引
    std::vector<cv::Vec3b> colors(nccomps + 1);
    // label為0的連通區(qū)域是背景區(qū)域（即在待分析圖像中就是黑色部分），設置為黑色
    colors[0] = cv::Vec3b(0,0,0);
    for (int i = 1; i <= nccomps; i++) {
        // 面積如果小于100诬垂，則設置為黑色
        if (stats.at<int>(i-1, cv::CC_STAT_AREA) < 100) {
            colors[i] = cv::Vec3b(0,0,0);
        } else {
            colors[i] = cv::Vec3b(rand()%256, rand()%256, rand()%256);
        }
    }

    // 繪制連通區(qū)域分析結果圖像
    cv::Mat img_color = cv::Mat::zeros(img.size(), CV_8UC3);
    for (int y = 0; y < img_color.rows; y++) {
        for (int x = 0; x < img_color.cols; x++) {
            int label = labels.at<int>(y, x);
            CV_Assert(0 <= label && label <= nccomps);
            img_color.at<cv::Vec3b>(y, x) = colors[label];
        }
    }

    // 展示連通區(qū)域分析結果
    cv::imshow("Labeled map", img_color);

    return 0;
}

該示例程序的運行結果如下圖劲室，從坐至右分別是原始圖像，閾值處理后的圖像结窘，連通區(qū)域分析后的著色圖像很洋。

3 深入輪廓

圖像的輪廓數(shù)據(jù)分析出來后，我們可能對其中的部分輪廓感興趣隧枫。想要簡化它們喉磁，或者計算它們的近似幾何形狀，將其與模版圖形進行匹配悠垛，以及做一些其他操作线定。本小節(jié)會介紹一些和圖像輪廓相關的復雜計算機視覺任務，并介紹一些OpenCV提供的函數(shù)确买，這些函數(shù)有的直接實現(xiàn)了這些圖像處理任務斤讥，其他的可以簡化些圖像處理任務。

3.1 近似多邊形

通常在處理某條輪廓的時候會計算其對應的包含更少頂點的近似多邊形湾趾，OpenCV提供兩種方式實現(xiàn)該任務芭商，其中函數(shù)cv::approxPolyDP()原型如下。該函數(shù)是Douglas-Peucker(DP)逼近算法的實現(xiàn)搀缠。與之對應的常用算法還有Rosenfeld-Johnson和Teh-Chin算法铛楣。這兩種算法中，Teh-Chin算法在OpenCV中不能用于縮減頂點艺普，但是可以在提取輪廓時使用簸州，詳情可以參考前文函數(shù)cv::findContours()的介紹。

// curve：待處理的輪廓歧譬，2維坐標集合岸浑，可以使用N??1的雙通道矩陣對象，或者包含cv:Point
//        元素的標準向量
// approxCurve：近似多邊形的輪廓瑰步，可以使用矩陣或者向量矢洲，但是需要和參數(shù)curve一致
// epsilon：原始輪廓到近似多邊形輪廓允許的最大位移
// closed：是否需要閉合輪廓，即從輪廓的最后一個頂點鏈接到第一個頂點形成閉合曲線
void cv::approxPolyDP(cv::InputArray curve, cv::OutputArray approxCurve,
                      double epsilon, bool closed);

更好的理解Douglas-Peucker算法可以加深對函數(shù)cv::approxPolyDP()的理解缩焦，也能幫助我們選擇合適的epsilon參數(shù)读虏。該算法原理如下圖所示责静，對于b圖中給定的輪廓，選擇最遠的兩個點連接相連的到c圖中的一條直線盖桥，然后再從原來的輪廓點里選擇離該線最遠點并更新輪廓得到d圖灾螃，隨后算法繼續(xù)迭代得到e圖，最后當原始輪廓中的所有頂點到近似多邊形的某條邊的距離都小于參數(shù)epsilon值的時候算法停止迭代揩徊，輸出最終得到的近似多邊形睦焕。

因此epsilon建議設置為輪廓的軸長，或者輪廓外包矩形周長或者其他能夠表示輪廓整體大小的一個分量靴拱。

3.2 特征計算

在處理輪廓時通常需要計算其各種特征，如邊長猾普，輪廓矩(Contour Moments)等袜炕，輪廓矩可以用于概括輪廓的大致形狀特征。OpenCV提供了一些列函數(shù)用于計算這些特征初家，它們不僅適用于表示曲線的點集偎窘，如計算邊長，也可以用于無任何含義的點集溜在，如計算最小包含矩形陌知。

3.2.1 輪廓長度

OpenCV計算輪廓長度的函數(shù)原型如下，需要注意該函數(shù)只對表示輪廓的點集才有意義掖肋。

// 返回值：輪廓的長度
// points：待分析的輪廓仆葡，N??1的雙通道矩陣，或者STL向量
// closed：輪廓是否閉合志笼，即是否需要將輪廓的首尾頂點相連
double cv::arcLength(cv::InputArray points, bool closed);

3.2.2 最小直立包圍矩形

計算點集的最小直立包圍矩形(即矩形的邊一定水平或者豎直)函數(shù)原型如下沿盅，該函數(shù)適用于表示任何含義的頂點集合。

// 返回值：點集的最小包圍矩形
// points：頂點幾何纫溃，N??1的雙通道矩陣腰涧，或者STL向量
cv::Rect cv::boundingRect(cv::InputArray points);

3.2.3 最小旋轉包圍矩形

OpenCV還支持查找包含點集的最小旋轉矩形，即其邊不需要一定水平和垂直紊浩。如在下圖中左側是尋找到的最小直立包圍矩形窖铡，而右側是尋找到到最小旋轉包圍矩形，該矩形到面積更小坊谁。圖中cv::RotatedRect是專用于表示旋轉矩形的數(shù)據(jù)結構费彼。

本系列文章最初將數(shù)據(jù)結構時已經(jīng)介紹過cv::RotatedRect，這里列出該類的定義如下呜袁，幫助我們回憶該數(shù)據(jù)結構敌买。

class cv::RotatedRect {
    // 矩形中心點，也是矩形的旋轉點
    cv::Point2f center;
    // 矩形的大小阶界，相對于旋轉中心的寬和高
    cv::Size2f size;
    // 矩形旋轉的角度
    float angle;
};

計算最小旋轉矩形的函數(shù)原型如下虹钮，該函數(shù)適用于表示任何含義的頂點集合聋庵。

// 返回值：技術得到的最小旋轉矩形
// points：待分析的點集，可以是N??1的雙通道矩陣芙粱，或者是STL向量
cv::RotatedRect cv::minAreaRect(cv::InputArray points);

3.2.4 最小包圍圓

計算最小包圍圓的函數(shù)原型如下祭玉，該函數(shù)適用于表示任何含義的頂點集合。

// points：待分析的點集春畔，可以是N??1的雙通道矩陣脱货，或者是STL向量
// center：計算得到的圓心
// radius：計算得到的半徑
void cv::minEnclosingCircle(cv::InputArray points,
                            cv::Point2f & center, float & radius);

3.2.5 最佳包圍橢圓

需要注意這里的的最佳包圍橢圓和前文的集中最小包圍框不同，最佳包圍橢圓不需要必須包含所有的點集律姨。計算該橢圓的函數(shù)原型如下振峻，該函數(shù)適用于表示任何含義的頂點集合。

// 返回值：表示橢圓的旋轉矩形
// points：待分析的點集择份，可以是N??1的雙通道矩陣扣孟，或者是STL向量
cv::RotatedRect cv::fitEllipse(cv::InputArray points);

計算最佳包圍橢圓使用到了最小平方擬合函數(shù)(least-squares function)，這里不對該函數(shù)詳細介紹荣赶。函數(shù)的返回值是cv::RotatedRect的實例凤价，它表示橢圓的最小矩形。例如在下圖中從左至右分別是點集的最小包圍圓拔创，最佳包圍橢圓利诺，表示最佳包圍橢圓的旋轉矩形。

3.2.6 最佳擬合曲線

在很多時候剩燥，得到的輪廓是一條近似直線的點集慢逾，或者說是對直線的帶噪聲的采樣∶鸷欤基于很多原因我們可能想要擬合出這條直線氛改，因此也出現(xiàn)了很多擬合方法。OpenCV中通過使得成本函數(shù)(Cost Function)取得最小值來完成該任務比伏，該函數(shù)定義如下胜卤。

其中θ表示的是定義直線的一系列參數(shù)，而xi表示的是第i個點赁项，ri表示的是該點到由參數(shù)集合θ定義到直線之間的距離葛躏，而p(ri)則是定義單個點的距離成本，計算單個點距離成本的方式有很多悠菜。其中OpenCV提供的選項cv::DIST_L2就是了解基礎統(tǒng)計學讀者最屬性的最小平方擬合法舰攒。當需要更精確的擬合結果時，如需要很好的處理異常數(shù)據(jù)點時悔醋，可以使用更復雜的成本計算方法摩窃。下表列出了OpenCV支持的成本計算方法及其數(shù)學公式，其中給出的C值為建議的參數(shù)。

擬合最佳去想的函數(shù)原型如下猾愿，該函數(shù)適用于表示任何含義的頂點集合鹦聪。

// points：待分析的點集，可以是N??1的雙通道/三通道矩陣蒂秘，或者是STL向量
// line：擬合得到的直線端點泽本，處理2D點集時使用Vec4f，處理3D點集時使用Vec6f姻僧，
//规丽。     前半部分表示直線的方向，后半部分是直線上的一個點
// distType：成本計算方法撇贺，見上表
// param：成本計算公式中需要用到的參數(shù)C赌莺，見上表，設置為0時將會使用上表中的建議值
// reps：擬合曲線的點精度松嘶，常用1e-2
// aeps：擬合曲線的角度精度雄嚣，常用1e-2
void cv::fitLine(cv::InputArray points, cv::OutputArray line,
                 int distType, double param, double reps, double aeps);

3.2.7 輪廓突包

突包指的是特殊的突出多邊形，如下圖C圖多邊形喘蟆，其中任意三個相鄰頂點組成的兩個向量的內角都必須小于180度。而輪廓突包指的是從輪廓中提取的這種多邊形鼓鲁，多邊形的所以頂點都應該來自于表示輪廓的點集蕴轨。如下圖中的B圖是從A圖人像中提取的輪廓，而C圖是根據(jù)B圖計算的輪廓突包骇吭。

計算輪廓突包的原因可能有很多橙弱，其中一個就是當判斷一個點是否位于復雜多邊形內部時，先判斷其是否位于從該復雜多邊形提取的輪廓突包內部燥狰，這樣能極大的加快程序整體效率棘脐。計算輪廓突包的函數(shù)原型如下，改函數(shù)只對表示輪廓的點集有意義龙致。

// points：待分析的點集蛀缝，可以是N??1的雙通道矩陣，或者是STL向量
// hull：計算出的輪廓突包
// clockwise：輸出頂點的方向目代，fase時為逆時針屈梁，ture為順時針
// returnPoints：返回頂點坐標，還是在point中的索引
//              當參數(shù)hull類型為向量時榛了，該參數(shù)被忽略在讶，因為根據(jù)向量的數(shù)據(jù)類型為int或者是
//              cv::Point能夠判斷出你想要返回的是索引還是點坐標，當參數(shù)hull類型為
//              cv::Mat時霜大，該參數(shù)必須正確設置
void cv::convexHull(cv::InputArray points, cv::OutputArray hull,
                    bool clockwise = false, bool returnPoints = true);

3.3 幾何學測試

在處理圍繞矩形以及其他表示輪廓整體形狀的多邊形時构哺，通常需要執(zhí)行一些如多邊形重疊或者快速圍繞矩形重疊檢測，OpenCV提供了一些函數(shù)來處理這些任務战坤。大多數(shù)和矩形相關的幾何學測試功能都是通過矩形的數(shù)據(jù)結構類來提供的曙强，如cv::Rect提供函數(shù)contains()用于測試某個點是否在矩形內部残拐。

包含兩個矩形的最小矩形可以通過代碼rect1 | rect2計算，兩個矩形的重疊矩形可以通過rect1 & rect2計算旗扑。但是對于旋轉矩形cv::RotatedRect而言蹦骑，OpenCV并沒有提供相應的成員函數(shù)，但是OpenCV額外提供了一些函數(shù)來處理任意多邊形臀防。

3.3.1 測試點是否位于多邊形內

測試點是否位于多邊形內的函數(shù)原型如下眠菇。

// 返回值：點距離多邊形邊的最短距離，點位于多邊形外時返回值為正袱衷，剛好位于多邊形邊上時返回值為0捎废，
//       在多邊形內部返回值為負
// contour：表示多邊形的輪廓，二維點組成的N??1雙通道矩陣或者是向量
// pt：測試點
// measureDist：是否需要精確返回距離致燥，當其為ture時會返回精確的距離登疗，否則返回1表示在多邊形外，
//              0表示在多邊形邊上嫌蚤，-1表示在多邊形內
double cv::pointPolygonTest(cv::InputArray contour, cv::Point2f pt,
                            bool measureDist);

3.3.2 測試輪廓是否為凸多邊形

確定一個多邊形是否為凸多邊形是一個很常見的操作辐益，這樣做的原因可能有很多，但是最典型的一個原因就是OpenCV中的一些算法只能用于凸多邊形脱吱，或者有些算法在處理凸多邊形時可以極大簡化算法邏輯智政，提升算法效率。處理該任務的函數(shù)原型如下箱蝠，需要注意算法默認傳入的多邊形是閉合的续捂，并且多邊形的邊不能相交。

// 返回值：待測試的多邊形是否為凸多邊形
// contour：表示多邊形的輪廓宦搬，二維點組成的N??1雙通道矩陣或者是向量
bool cv::isContourConvex(cv::InputArray contour);

4 匹配輪廓與圖像

目前你應該已經(jīng)了解了輪廓是什么以及如何使用OpneCV定義的輪廓對象牙瓢，接下來將會介紹一些在實際工作中輪廓的使用示例。最常見的計算機視覺任務就是比較兩個輪廓间校，或者是使用計算出的輪廓匹配模版矾克。

4.1 矩

比較兩個輪廓的最簡單方式就是計算輪廓矩(Contour Moments)，輪廓矩是表示一個輪廓憔足、一副圖像或者一個點集(為了方便下文統(tǒng)稱對象)的某種高層次特征聂渊，其定義公式如下。

在上述公式中四瘫，矩mpq是對象中所有“像素值”的總和汉嗽，每個像素的值都是其像素強度和系數(shù)xp和yq的乘積。在計算矩m00時找蜜，如果處理的是二值圖像饼暑，則m00計算的就是圖像中非零像素的個數(shù)，如果處理的是輪廓，則它計算的就是輪廓的長度弓叛，如果處理的是點集彰居，則它計算的是點點數(shù)量。需要注意在處理輪廓時撰筷，如果先對輪廓進行光柵化處理陈惰，如使用函數(shù)cv::drawContours()繪制輪廓，然后再計算輪廓的矩毕籽，則得到的長度和直接計算輪廓矩得到的長度并不完全相同抬闯，當然在分辨率無限的情況下它們是相同的。

如果理解了m00关筒，則很方便理解對于二值圖像而言溶握，m10/m00和m01/m00分別計算了非零像素的平均x值以及平均y值。術語矩與統(tǒng)計學相關蒸播，而更高階的矩與統(tǒng)計學分布有關睡榆，如面積、均值和方差等袍榆。在這個背景下你可以將非二值圖像的矩看作是二值圖像矩的特殊形式胀屿，其每個像素包含多個值。

計算矩等函數(shù)原型如下包雀。

// 返回值：待處理對象的矩
// points：待處理對象宿崭，可以是二維點集合(N??1或者1??N矩陣，或者STL向量)馏艾，也可以是圖像(M??N矩陣)
// binaryImage：是否為二值圖像，選擇false時像素強度會被看作是像素點“質量”
cv::Moments cv::moments(cv::InputArray points, bool binaryImage = false);

該函數(shù)在處理二維點集點時候不會將參數(shù)points包含點數(shù)據(jù)看做是離散點點奴愉，而是輪廓點頂點琅摩，這以為著如果你想只處理這些點時朝氓，需要使用這些點創(chuàng)建一張圖像虫埂，再將其作為該函數(shù)點輸入。參數(shù)binaryImage設置為YES時忍些，所有非零值都將被識別為1檀头，這對于處理應用閾值操作后的圖像很有幫助轰异，因為在這些圖像中非零值可能會被設置為255或者其他值。cv::Moments是OpenCV表示矩的數(shù)據(jù)結構暑始，其定義如下搭独。

class Moments {
public:
double m00;                       // 0階矩(x1)
double m10, m01;                  // 1階矩(x2)
double m20, m11, m02;             // 2階矩(x3)
double m30, m21, m12, m03;        // 3階矩(x4)
double mu20, mu11, mu02;          // 2階中心矩(central moments)(x3)下文介紹
double mu30, mu21, mu12, mu03;    // 3階中心矩(x4)
double nu20, nu11, nu02;          // 2階標準化中心矩(Hu invariant moments)(x3)下文介紹
double nu30, nu21, nu12, nu03;    // 3階標準化中心矩(x4)

// 構造函數(shù)
Moments();
Moments(
double m00,
double m10, double m01,
double m20, double m11, double m02,
double m30, double m21, double m12, double m03
);

// 將老版本的CvMoments轉換為新的C++對象
Moments( const CvMoments& moments );
// 重載運算符，將C++對象轉換為老版本的老版本的CvMoments
operator CvMoments() const;
}

函數(shù)cv::moments()調用一次會計算到三階(p + q <= 3)矩廊镜，并且會同時計算中心矩和標準化中心矩牙肝。

4.2 深入理解矩

矩能夠描述輪廓的基本特征，也能作為參考比較兩個輪廓。但是在實際場景中普通的矩配椭，即在類Moments的定義中大部分以m和數(shù)字組合的屬性并不是最好的比較標準虫溜。即對于兩個相同的但是相互之間有位移，或者是有縮放股缸，或者是發(fā)時旋轉的兩個對象而言衡楞，其普通矩計算結果并不相同。

4.2.1 中心矩平移不變性

對于形狀相同但是發(fā)生位移的兩個輪廓和圖像敦姻，其m00矩的計算結果是相同的瘾境，但是高階普通矩就不相同了√媾考慮m10矩計算的是對象包含像素的x坐標分量平均值寄雀，很明顯如果對象發(fā)生位移這個值將會隨之變化。顯然這不是我們想要的結果陨献，我們想要的是比較不同位置的對象能夠得到相同對值盒犹，即判斷標準具有平移不變性(Invariant Under Translation)，計算結果不隨對象的相對位置改變而改變眨业。

為了處理平移的場景需要使用到中心矩(Central Moments)急膀，其計算公式如下。

顯然中心矩mu00(矩數(shù)據(jù)結構屬性以mu開頭龄捡，等同于上述公式的μ)等于普通矩m00卓嫂，因為任何數(shù)的0次冪都等于1，另外中心矩陣mu10和mu01都等于0聘殖。由于中心矩的計算都是相對均值的變化晨雳，因此對象的平移不會改變中心矩的計算結果。

另外mu00等用m00奸腺，mu10=mu01=0餐禁，nu00=1，nu10=nu01=0突照，由于它們是固定值或者和其他值相等帮非，因此在Moments的定義中為了節(jié)省內存空間不包含這些屬性。

4.2.2 標準化中心矩縮放不變性

使用相機拍攝同一個物體時讹蘑，相機的遠近會導致獲取的圖像中目標對象的大小不一致末盔，因此通常我們需要一個不受縮放影響的比較標準，而標準化中心矩(Normalized Central Moments)就滿足這個條件座慰，它具有縮放不變性陨舱。在調用函數(shù)cv::moments()會同時計算普通矩，中心矩和標準化中心矩版仔。標準化中心矩計算時會使用中心距除以目標整體大小的一個指數(shù)冪隅忿，其計算公式如下心剥。

4.2.3 Hu不變矩旋轉不變性

Hu不變矩(Hu invariant moments)是標準化中心矩的線性組合，Hu不變矩處理同個目標對象的縮放背桐、旋轉优烧、鏡像(除h1矩外)對象時都能得到相同的計算結果。Hu不變矩的定義如下链峭。

為了更形象的體驗hu不變矩的實際意義畦娄，我們分別計算下圖的5個不同對象的多階hu不變矩。

計算結果如下表弊仪。

從上表中可以明顯看出隨著hu矩的階數(shù)不斷增加熙卡，得到的值越小。這并不奇怪励饵，因為根據(jù)前文提到的hu矩定義驳癌，高階Hu矩陣是一系列標準因子的高階冪，由于這些標準因子的值都小于1役听，因此指數(shù)越高其計算得到的值越小颓鲜。

值得關注的是對象I，它具有180度旋轉和鏡像對稱性典予，其3到7階hu矩值都等于0甜滨，對象O也具有類似的對稱性，盡管其所有hu矩都不為0瘤袖，但是其中兩個已經(jīng)接近于0了衣摩。

計算Hu矩有單獨的函數(shù)，它需要使用普通矩的計算結果作為輸入捂敌，即函數(shù)cv::moments()的計算結果作為輸入艾扮，其函數(shù)原型如下。

// moments：對象的普通矩占婉，即函數(shù)cv::moments()的計算結果
// hu：計算得到的Hu矩泡嘴，C風格的數(shù)組，共包含1-7階矩锐涯，共7個元素
void cv::HuMoments(const cv::Moments& moments, double * hu);

4.3 使用Hu矩進行匹配

計算對象的矩的目的顯然是需要比較兩個程度等相似度磕诊，OpenCV專門提供了函數(shù)直接根據(jù)指定的方法比較兩個對象的相似程度填物，其函數(shù)原型如下纹腌。

// object1：第一個待比較的對象，可以是二維點集滞磺，也可以是元素類型為cv:U8C1的矩陣
// object1：第二個待比較的對象升薯，可以是二維點集，也可以是元素類型為cv:U8C1的矩陣
// method：比較方法下文介紹
// parameter：保留參數(shù)击困，暫時不會使用
double cv::MatchShapes(cv::InputArray object1, cv::InputArray object2,
                       int method, double parameter = 0);

該函數(shù)內部會計算對象的矩涎劈，然后再進行比較广凸，并將計算結果返回。參數(shù)method的可選值及對應的函數(shù)返回值的計算公式如下蛛枚。其中A和B分別對應函數(shù)的輸入對象object1和object2谅海。

4.4 使用形狀場景方法比較形狀

使用矩來比較形狀是一個經(jīng)典的技術，最早可以追溯到上個世紀80年代蹦浦，OpenCV同樣提供更好的現(xiàn)代算法用于形狀比較扭吁。在OpenCV3中有單獨的模塊Shape負責處理這些任務，其中最典型的就是形狀場景算法(Shape Context)盲镶。該模塊尚在開發(fā)中侥袜，因此這里只簡略介紹其高層抽象結構以及部分非常有用的函數(shù)和數(shù)據(jù)結構。

4.4.1 形狀模塊的基本結構

形狀模塊的核心是形狀距離提取器類cv::ShapeDistanceExtractor溉贿，該抽象類型適用于任何用于比較兩個或者更多形狀并返回能夠量化這兩種形狀差異的距離度量的函數(shù)子(Functor)枫吧。這里使用距離這個詞來衡量不相似性是因為在很多場景下，距離和差異性具有相同的屬性宇色，如對于兩個完全相同的對象而言九杂，它們的距離為0。

在繼續(xù)介紹該類之前代兵，先要熟悉另外兩個基本的數(shù)據(jù)結構尼酿，其中ShapeTransformer的定義如下。

class ShapeTransformer : public Algorithm {
public:
  virtual void estimateTransformation(
    cv::InputArray      transformingShape,
    cv::InputArray      targetShape,
    vector<cv::DMatch>& matches
  ) = 0;

  virtual float applyTransformation(
    cv::InputArray      input,
    cv::OutputArray     output      = noArray()
  ) = 0;

  virtual void warpImage(
    cv::InputArray      transformingImage,
    cv::OutputArray     output,
    int                 flags       = INTER_LINEAR,
    int                 borderMode  = BORDER_CONSTANT,
    const cv::Scalar&   borderValue = cv::Scalar()
  ) const = 0;
};

類ShapeTransformer廣泛用于表示一類將一個點集重映射到另外一個點集的算法植影，更一般化的場景就是將一副圖片映射成為一張新的圖片裳擎。本系列文章前面章節(jié)講到的仿射和投影變換也能夠通過定義形狀轉換器實現(xiàn)。其中的一個重要例子就是薄板樣條轉換器(Thine Plate Spline Transform)思币，該轉換器得名于金屬薄板物理模型鹿响，并且它從根本上解決了金屬薄板上的部分控制點移動到其他位置而產(chǎn)生的映射問題。當控制點移動后金屬薄板會隨之變性谷饿，這樣其內部稠密點的映射變換就是算法要解決的問題惶我。事實證明這是一個廣泛適用的數(shù)據(jù)結構，在圖像對其和形狀匹配中也有很多應用博投。在OpenCV中該算法被定義為函數(shù)子cv::ThinPlateSplineShapeTransformer绸贡。

HistogramCostExtractor的定義如下。

class HistogramCostExtractor : public Algorithm {
public:
  virtual void  buildCostMatrix(
    cv::InputArray      descriptors1,
    cv::InputArray      descriptors2,
    cv::OutputArray     costMatrix
  )                                                 = 0;

  virtual void  setNDummies( int nDummies )         = 0;
  virtual int   getNDummies() const                 = 0;

  virtual void  setDefaultCost( float defaultCost ) = 0;
  virtual float getDefaultCost() const              = 0;
};

直方圖成本提取器推廣可以得到在前面章節(jié)技術地球移動距離(Earth Mover Distance, EMD)時使用到的數(shù)據(jù)結構毅哗，在計算EMD距離時我們計算的是從一個直方圖分組移動“數(shù)據(jù)”到另外一個分組的成本听怕。有時這個成本是常量或者是與移動距離線性相關，但是有時成本與移動的”數(shù)據(jù)量“相關虑绵。計算EMD距離有單獨的函數(shù)可以調用尿瞭，而基類cv::HistogramCostExractor和其派生類可以用于處理更一般化的問題。下表列出了該類的派生類及其處理的任務類型翅睛。

對于上表中的每個類型的成本提取器声搁，OpenCV都提供了一個類似createX()的函數(shù)用于生成對應的實例黑竞，例如cv::createChiHistogramCostExtractor()。

4.4.2 形狀場景距離提取器

本小節(jié)的開頭就介紹過形狀模塊的核心是形狀距離提取器類cv::ShapeDistanceExtractor疏旨，現(xiàn)在介紹它的一些派生類很魂。首先介紹的是形狀場景距離提取器ShapeContextDistanceExtractor，它的內部實現(xiàn)使用了一個形狀轉換器和一個直方圖成本提取器檐涝，其定義如下莫换。

namespace cv {
// 形狀場景距離提取器的定義
  class ShapeContextDistanceExtractor : public ShapeDistanceExtractor {
    public:
    ...
    virtual float computeDistance(InputArray contour1, InputArray contour2) = 0;
  };

// 構建形狀場景距離提取器的函數(shù)
  Ptr<ShapeContextDistanceExtractor> createShapeContextDistanceExtractor(
    int nAngularBins = 12,
    int nRadialBins = 4,
    float innerRadius = 0.2f,
    float outerRadius = 2,
    int iterations = 3,
    const Ptr<HistogramCostExtractor> &comparer = 
              createChiHistogramCostExtractor(),
    const Ptr<ShapeTransformer> &transformer = 
              createThinPlateSplineShapeTransformer()
  );
}

實質上形狀背景距離算法計算了多個待比較形狀的某種特征表示，其中每個特征都是形狀邊界點的子集計算骤铃，對于該子集中的每個采樣點拉岁，該算法都會以該點為觀察點創(chuàng)建一個能夠在極坐標系中反應輪廓特征的直方圖。所有的直方圖大小相同惰爬，都為nAngularBins??nRadialBins喊暖。從形狀contour1中的點pi和形狀contour2中的點qj計算出的直方圖使用經(jīng)典的卡方距離比較(Chi-squared Distance)。然后算法計算形狀contour1中采樣子集p和形狀contour2中的采樣子集q中點點最優(yōu)關聯(lián)撕瞧，使得整體卡方距離最小陵叽。該算法并不是最快的，甚至計算成本矩陣的復雜度為N??N??nAngularBins??nRadialBins(對于每個p中的點q都需要計算所有的點從而找到最小的卡方距離丛版，而每次尋找咖啡距離會遍歷直方圖所有元素)巩掺，其中N是形狀邊界點采樣子集的數(shù)量。但是這個算法仍然能夠給出不錯的結果页畦。

示例程序SCDE使用形狀背景提取器比較了兩個形狀胖替，其核心代碼如下。

/// 提取圖片輪廓豫缨，并隨機采樣頂點
/// - Parameters:
///   - image: 待采樣的圖片
///   - n: 采樣頂點數(shù)
static std::vector<cv::Point> sampleContour(const cv::Mat& image, int n = 300) {
    // 查找所有的輪廓
    std::vector<std::vector<cv::Point>> contours;
    cv::findContours(image, contours, cv::RETR_LIST, cv::CHAIN_APPROX_NONE);
    
    // 這里提取出第一條輪廓的所有頂點独令，由于準備的圖片只能提取出一張輪廓，
    // 因此得到的就是想要尋找的輪廓
    std::vector<cv::Point> all_points;
    for (size_t j = 0; j < contours[0].size(); j++) {
        all_points.push_back(contours[0][j]);
    }

    // 如果單條輪廓的頂點數(shù)量小于n好芭，則重復該條輪廓已有的頂點燃箭，直至輪廓數(shù)量等于N
    int dummy = 0;
    for (int add = (int)all_points.size(); add < n; add++) {
        all_points.push_back(all_points[dummy++]);
    }

    // 使用隨機順序排列所有的頂點
    unsigned seed = 
        (unsigned)std::chrono::system_clock::now().time_since_epoch().count();
    std::shuffle(all_points.begin(), all_points.end(),
                 std::default_random_engine (seed));
    
    // 隨機采樣輪廓的n個頂點
    std::vector<cv::Point> sampled;
    for (int i = 0; i < n; i++) {
        sampled.push_back(all_points[I]);
    }
    return sampled;
}

int main(int argc, const char * argv[]) {
    // 讀取待比較的兩個圖片
    cv::Mat img1 = imread(argv[1], cv::IMREAD_GRAYSCALE);
    cv::Mat img2 = imread(argv[2], cv::IMREAD_GRAYSCALE);
    // 分別計算兩個圖片的隨機采樣輪廓頂點
    std::vector<cv::Point> c1 = sampleContour(img1);
    std::vector<cv::Point> c2 = sampleContour(img2);
    
    // 比較兩個形狀的距離
    cv::Ptr<cv::ShapeContextDistanceExtractor> mysc = 
        cv::createShapeContextDistanceExtractor();
    // 可能是由于XCode使用的編譯器是Clang + LLVM，使得程序運行時報動態(tài)庫符號綁定
    // 錯誤：Symbol not found: ___emutls_get_address
    float dis = mysc->computeDistance(c1, c2);
    std::cout << "shape context distance between "
              << argv[1] << " and " << argv[2] << " is: " << dis << std::endl;
    
    // 顯示兩個形狀
    cv::imshow("SHAPE #1", img1);
    cv::imshow("SHAPE #2", img2);
    
    // 掛起程序等待用戶輸入
    cv::waitKey();

    return 0;
}

更復雜的使用示例請參考OpenCV3的官方文檔中的示例程序…samples/cpp/shape_example.cpp舍败。

4.4.3 Hausdorff距離提取器

和形狀背景距離提取器一樣招狸，Hausdorff距離提取器也繼承自類ShapeDistanceExtractor，它同樣可以用于比較形狀的差異邻薯。其定義如下裙戏。

class CV_EXPORTS_W HausdorffDistanceExtractor : public ShapeDistanceExtractor {
public:
    CV_WRAP virtual void setDistanceFlag(int distanceFlag) = 0;
    CV_WRAP virtual int getDistanceFlag() const = 0;

    CV_WRAP virtual void setRankProportion(float rankProportion) = 0;
    CV_WRAP virtual float getRankProportion() const = 0;
};

算法計算公式如下(推測第一個公式的h(BA)誤寫為h(Ba))。首先獲取了圖片中的所有點弛说，對于每個點挽懦，找到最近與它最近點的距離翰意，這些距離里面的最大值定義為直接Hausdorff距離(Directed Hausdorff Distance)木人，使用符號h表示信柿。兩個直接Hausdorff距離中的大值就是Hausdorff距離(Hoausdorff Distance)，使用符號H表示醒第。需要注意直接Hausdorff距離是非對稱的渔嚷，即交換括號內AB順序會影響計算結果，而Hausdorff距離是對稱的稠曼。公式中的|| X ||表示某種范數(shù)形病，常用的是歐式距離。本質上該算法計算的是兩個形狀中距離最遠的一組點霞幅。

構建Hausdorff距離提取器的函數(shù)原型如下漠吻。

// distanceFlag：距離計算方式
cv::Ptr<cv::HausdorffDistanceExtractor> cv::createHausdorffDistanceExtractor(
    int distanceFlag = cv::NORM_L2, float rankProp = 0.6);

5 小結

本章是圍繞輪廓和二維空間點集展開的，它們可以使用包含如cv::Vec2f等點對象的STL向量表示司恳，也可以使用N??1的雙通道矩陣或者N??2的單通道矩陣表示途乃。輪廓也可以表示為二維點集，OpenCV提供了一系列函數(shù)來提取和處理輪廓扔傅。

輪廓在表示圖片的分區(qū)時非常有用耍共，OpenCV也提供了很多工具函數(shù)來比較輪廓對象以及計算它們的一些特征屬性，如輪廓凸包猎塞，矩以及任意點和輪廓的關系试读。最后OpenCV提供了很多方式匹配輪廓和形狀，文中介紹了經(jīng)典的基于矩的比較方法荠耽，也介紹了基于形狀距離提取器的新特性钩骇。