1 摘要

上一章節(jié)介紹了OpenCV中可用的圖像變換函數(shù)，這些技術(shù)本質(zhì)上都是通過一種映射關(guān)系將圖像轉(zhuǎn)換為另一個(gè)圖像，這種轉(zhuǎn)換會(huì)保留輸入圖像的主要特征。本章將要介紹的圖像處理技術(shù)則可能得到和輸入圖像完全不一樣的結(jié)果，甚至得到的矩陣中元素的含義也會(huì)發(fā)生根本變化。如下文將會(huì)將到的離散傅立葉變換(Discrete Fourier Transform，DFT)處理圖像后的到的是像素的顏色頻域表示，而原始圖像是像素的顏色強(qiáng)度表示。某些變換得到的結(jié)果甚至已經(jīng)不再是矩陣，而是類似成分列表，如霍夫線變換(Hough Line Transform)。

在本章末尾還會(huì)介紹圖像分割技術(shù)，用于分割圖像中有意義的相連接區(qū)塊。

2 頻域-空域變換

2.1 離散傅立葉變換

傅立葉變換用于將連續(xù)的時(shí)域信號(hào)轉(zhuǎn)換為連續(xù)的頻域信號(hào)，而離散傅立葉變換用于處理離散的數(shù)據(jù)，如二維圖像中的離散像素點(diǎn)。對(duì)于一維N個(gè)復(fù)數(shù)信號(hào)x0，x1…xn-1，其離散傅立葉變換公式定義如下。完整的傅立葉變換推導(dǎo)公式請(qǐng)參考文章數(shù)字信號(hào)處理

其中

二維的離散傅立葉變換公式定義如下，對(duì)于更高維度的傅立葉變換這里暫時(shí)不討論。

從上述公式中可以看出，對(duì)于N個(gè)樣本的信號(hào)集，得到其N個(gè)頻域表示分量離散傅立葉變換需要的計(jì)算負(fù)責(zé)度為O(N2)，實(shí)際上快速傅立葉變換(Fast Fourier Trasform, FFT)能夠?qū)⑺惴◤?fù)雜度降至O(N logN)。

OpenCV提供的離散傅立葉變換函數(shù)原型如下。該函數(shù)使用了快速傅立葉變換算法，能夠處理1維和2維矩陣信號(hào)。在處理2維矩陣的時(shí)候可以選擇將矩陣的每一行都看作是一個(gè)1維信號(hào)集，分別計(jì)算它們的1維傅立葉變換，這種處理方式的效率會(huì)比多次調(diào)用該函數(shù)更高。

// src：輸入矩陣，待處理的信號(hào)
// dst：計(jì)算結(jié)果
// flags：計(jì)算策略，下文介紹
// nonzeroRows：有效的數(shù)據(jù)行，下文介紹
void cv::dft(cv::InputArray src, cv::OutputArray dst,
             int flags = 0, int nonzeroRows = 0);

輸入矩陣必須是單通道或者雙通道的浮點(diǎn)型數(shù)據(jù)。如果輸入矩陣為單通道矩陣，則輸入信號(hào)被認(rèn)為是實(shí)數(shù)，而輸出矩陣則被包裝為一種特別的節(jié)約空間的形式，稱為復(fù)數(shù)共軛對(duì)(Complex Conjugate Symmetrical, CSS)。此時(shí)輸出矩陣的尺寸和輸入矩陣的尺寸相同，因?yàn)閷?duì)于離散傅立葉變換而言，根據(jù)尼奎斯特采樣定理，得到的有效頻率數(shù)為N/2，因此這種格式正好利用了這部分空間。

而對(duì)于雙通道的輸入矩陣而言，兩個(gè)通道會(huì)分別被當(dāng)作是復(fù)數(shù)的實(shí)部和虛部，數(shù)據(jù)不會(huì)被打包成CSS格式，并且其輸出矩陣和輸入矩陣尺寸相同，但是這部分空間將會(huì)被0填充。使用雙通道矩陣處理數(shù)字圖像時(shí)，第二個(gè)通道的復(fù)數(shù)虛部必須設(shè)置為0，一個(gè)簡(jiǎn)單的方式是使用函數(shù)cv::Mat::zeros()創(chuàng)建一個(gè)全0矩陣，然后調(diào)用函數(shù)cv::merge()和已有的像素顏色強(qiáng)度矩陣合并得到完整的復(fù)數(shù)矩陣，然后再調(diào)用函數(shù)cv::dft()。

CCS格式包裝的1維信號(hào)矩陣傅立葉變換結(jié)果表示如下。

其中Re表示的是復(fù)數(shù)的實(shí)數(shù)部分，而Im表示的是復(fù)數(shù)的虛數(shù)部分。注意觀察元素下標(biāo)，特定元素缺失虛部數(shù)據(jù)，從而確保這部分?jǐn)?shù)據(jù)計(jì)算結(jié)果一定為實(shí)數(shù)。另外只有當(dāng)N為偶數(shù)時(shí)，最后一列才存在，否則將會(huì)被0填充。

2維信號(hào)矩陣傅立葉變換結(jié)果的CCS格式包裝如下圖。需要注意虛線將整個(gè)矩陣分為4個(gè)區(qū)域，左下角的行索引表示規(guī)則是處理真正的二維矩陣信號(hào)的示意圖，而右下角的行索引表示規(guī)則是處理Ny個(gè)1維矩陣信號(hào)的示意圖。同樣的對(duì)于二維信號(hào)矩陣而言，當(dāng)Nx不為偶數(shù)時(shí)，最后1列不會(huì)存在，當(dāng)Ny不為偶數(shù)時(shí)，最后1行不會(huì)存在。

參數(shù)flags可以指定函數(shù)內(nèi)部的算法策略，OpenCV提供了多個(gè)可選值，可以通過邏輯與符號(hào)組合這些選項(xiàng)。默認(rèn)情況下執(zhí)行的是離散傅立葉變換，而通過設(shè)置標(biāo)記cv::DFT_INVERSE可以執(zhí)行離散傅立葉逆變換。離散傅立葉逆變換和離散傅立葉變換的定義類似，它們的區(qū)別僅在于一個(gè)縮放系數(shù)和和指數(shù)的符號(hào)。需要注意如果想要執(zhí)行離散傅立葉逆變換，你的輸入矩陣應(yīng)當(dāng)符合前文描述的正變換輸出結(jié)果的規(guī)則。

逆變換的縮放系數(shù)可以通過cv::DFT_SCALE啟用，對(duì)于一維變換而言，這個(gè)系數(shù)為N^-1，對(duì)于二維變換而言，這個(gè)系數(shù)為(Nx Ny)^-1。如果是對(duì)一個(gè)正變換的結(jié)果應(yīng)用逆變換，這個(gè)選項(xiàng)必須開啟，否則將無法重建原始數(shù)據(jù)。由于標(biāo)記cv::DFT_INVERSE和cv::DFT_SCALE通常會(huì)合并使用，OpenCV將它們組合為一個(gè)特殊標(biāo)記cv::DFT_INVERSE_SCALE，可簡(jiǎn)寫為cv::DFT_INV_SCALE。另外該參數(shù)的可選標(biāo)記還有cv::DFT_ROWS，表示需要將二維的輸入矩陣當(dāng)作是Ny行一維矩陣處理。此外通過該標(biāo)記可以處理三維及更高維度的矩陣，這里不再詳細(xì)介紹。

前文說到過該函數(shù)在處理單通道矩陣時(shí)會(huì)使用CCS格式壓縮輸出矩陣尺寸，通過標(biāo)記cv::DFT_COMPLEX_OUTPUT可以強(qiáng)制該函數(shù)輸出復(fù)數(shù)結(jié)果。相反的，對(duì)一個(gè)復(fù)數(shù)矩陣應(yīng)用逆變換得到的結(jié)果也是復(fù)數(shù)矩陣，如果輸入矩陣具有復(fù)數(shù)對(duì)稱性(這里不是說CCS格式，而是指對(duì)稱性，如實(shí)數(shù)組的正向變換就有這種對(duì)稱性)，則可以通過設(shè)置標(biāo)記cv::DFT_REAL_OUTPUT強(qiáng)制輸出實(shí)數(shù)矩陣。

離散傅立葉變換強(qiáng)烈傾向于處理特定長度的輸入向量，在大多數(shù)DFT的算法實(shí)現(xiàn)中，希望的向量長度都是2的指數(shù)。在OpenCV中，偏好的向量長度或者矩陣維度維2、3或者5的指數(shù)，因此一個(gè)實(shí)用技巧是創(chuàng)建一個(gè)比實(shí)際數(shù)據(jù)更大的矩陣，多余的部分使用0填充。函數(shù)cv::getOptimalDFTSize()可以返回一個(gè)不小于輸入尺寸的適用于離散傅立葉變換的最佳尺寸。此時(shí)通過參數(shù)nonzero_rows顯示指明那些行是用于填充數(shù)據(jù)對(duì)其尺寸的，該函數(shù)在計(jì)算時(shí)會(huì)針對(duì)這些行進(jìn)行優(yōu)化提升運(yùn)算效率。

2.2 離散傅立葉逆變換

除了使用函數(shù)cv::dft()及特定的參數(shù)執(zhí)行離散傅立葉變換外，OpenCV還額外提供函數(shù)來執(zhí)行離散傅立葉變換，它們是等效的，其函數(shù)原型如下。

// src：輸入矩陣
// dst：輸出矩陣
// flags：算法策略
// nonzeroRows：有意義的數(shù)據(jù)行數(shù)
void cv::idft(cv::InputArray src, cv::OutputArray dst,
              int flags = 0, int nonzeroRows = 0);

2.3 頻譜乘法

在很多計(jì)算離散傅立葉變化的程序中，還需要逐元素的計(jì)算兩個(gè)矩陣的乘積。由于傅立葉變換的結(jié)果是復(fù)數(shù)，并且可以是以CCS格式打包的，因此處理這部分?jǐn)?shù)據(jù)可能比較繁瑣。OpenCV提供專門的函數(shù)用于執(zhí)行頻頻的乘法運(yùn)算，其函數(shù)原型如下。

// src1：第一個(gè)頻域信號(hào)矩陣，可以是單通道CCS格式或者雙通道復(fù)數(shù)
// src2：第二個(gè)頻域信號(hào)矩陣，可以是單通道CCS格式或者雙通道復(fù)數(shù)
// dst：計(jì)算結(jié)果
// flags：計(jì)算策略，僅支持cv::DFT_ROWS表示輸入矩陣的每一行為1維傅立葉變換的結(jié)果，
//        設(shè)置為0時(shí)表示2維傅立葉變換的結(jié)果
// conj：是否對(duì)第二個(gè)矩陣取共軛后再執(zhí)行乘法運(yùn)算，false用于卷積，而true用于計(jì)算相關(guān)性，
//       在后面的文章中會(huì)介紹
void cv::mulSpectrums(cv::InputArray src1, cv::InputArray src2,
                      cv::OutputArray dst, int flags, bool conj = false);

2.4 使用離散傅立葉變換加速卷積計(jì)算

卷積定理可以將空域上的卷積運(yùn)算轉(zhuǎn)換到頻域上的乘法運(yùn)算，從而極大的加快其算法計(jì)算效率，而函數(shù)從空域相頻域的轉(zhuǎn)換可以由傅立葉變換完成，對(duì)于離散的圖像信號(hào)可以使用離散傅立葉變換。這里不再做消息的卷積定理公式推斷，記住這個(gè)結(jié)論即可。示例DFTConvolution使用這種方式執(zhí)行卷積運(yùn)算，這部分代碼直接拷貝自O(shè)penCV的參考資料。

int main(int argc, const char * argv[]) {
    // 讀取圖像
    cv::Mat A = cv::imread(argv[1], 0);

    cv::Size patchSize(100, 100);
    cv::Point topleft(A.cols / 2, A.rows /2);
    cv::Rect roi(topleft.x, topleft.y, patchSize.width, patchSize.height);
    // 選中其中的一小塊圖像，需要注意實(shí)際的數(shù)據(jù)段仍然是共用的
    cv::Mat B = A(roi);
    
    // 獲取離散傅立葉變換的最佳向量長度
    int dft_M = cv::getOptimalDFTSize(A.rows + B.rows - 1);
    int dft_N = cv::getOptimalDFTSize(A.cols + B.cols - 1);
    // 使用最佳尺寸創(chuàng)建待處理的樣本矩陣
    cv::Mat dft_A = cv::Mat::zeros(dft_M, dft_N, CV_32F);
    cv::Mat dft_B = cv::Mat::zeros(dft_M, dft_N, CV_32F);
    // 映射內(nèi)部實(shí)際有效數(shù)據(jù)矩陣，共用數(shù)據(jù)段內(nèi)存
    cv::Mat dft_A_part = dft_A(cv::Rect(0, 0, A.cols, A.rows));
    cv::Mat dft_B_part = dft_B(cv::Rect(0, 0, B.cols, B.rows));
    // 將原圖A和選擇的區(qū)塊B映射到共用的數(shù)據(jù)段內(nèi)存，即此時(shí)dft_A和dft_B被填充對(duì)應(yīng)數(shù)據(jù)
    // 此次平移各自矩陣中的均值單位
    A.convertTo(dft_A_part, dft_A_part.type(), 1, -mean(A)[0]);
    B.convertTo(dft_B_part, dft_B_part.type(), 1, -mean(B)[0]);
    
    // 執(zhí)行傅立葉變換
    cv::dft(dft_A, dft_A, 0, A.rows);
    // 需要注意dft_B在執(zhí)行傅立葉變換之前有效的數(shù)據(jù)數(shù)為100*100，在執(zhí)行完成后整個(gè)矩陣都包含
    // 有效數(shù)據(jù)，推測(cè)內(nèi)部對(duì)原始的頻域值做了插值運(yùn)算，以便接下來方便計(jì)算卷積
    cv::dft(dft_B, dft_B, 0, B.rows);
    
    // 將最后一個(gè)參數(shù)設(shè)置偉false則計(jì)算卷積，否則計(jì)算相關(guān)性
    cv::mulSpectrums(dft_A, dft_B, dft_A, 0, true);
    // 此處卷積并未使用前文常見的任何濾波器，如高斯濾波器，暫不討論具體含義
//    cv::mulSpectrums(dft_A, dft_B, dft_A, 0, false);
    cv::idft(dft_A, dft_A, cv::DFT_SCALE, A.rows + B.rows - 1);

    // 獲取相關(guān)性矩陣的有效數(shù)據(jù)區(qū)域
    cv::Mat corr = dft_A(cv::Rect(0, 0, A.cols + B.cols - 1, A.rows + B.rows - 1));
    // 標(biāo)準(zhǔn)話矩陣原始
    cv::normalize(corr, corr, 0, 1, cv::NORM_MINMAX, corr.type());
    // 取三次冪，提高對(duì)比度便于查看
    cv::pow(corr, 3.0, corr);

    // 對(duì)分割出的小塊區(qū)域執(zhí)行異或運(yùn)算，等效于黑白反色
    B ^= cv::Scalar::all(255);
    
    // 顯示處理結(jié)果
    cv::imshow("Image", A);
    // 顯示相關(guān)性，相關(guān)性在后面章節(jié)中會(huì)詳細(xì)介紹，新增可以簡(jiǎn)單的理解為函數(shù)的相似程度，
    // 即圖像的相似程度
    cv::imshow("Correlation", corr);
    
    return 0;
}

使用傅立葉變換實(shí)現(xiàn)卷積運(yùn)算的算法中，最慢的部分是執(zhí)行變換的過程，對(duì)于一個(gè)N??N的圖像而言，傅立葉變換的算法時(shí)間復(fù)雜度為O(N²logN)。假定使用尺寸為M??M的卷積核，并且M<N，則可以使用這個(gè)值近似估計(jì)整個(gè)算法的時(shí)間復(fù)雜度。相較于直接進(jìn)行卷積運(yùn)算的時(shí)間復(fù)雜度為O(N²??M²)而言，這種策略能明顯提高算法的效率。需要注意的是如果使用的卷積核很小，則沒有必要做這種轉(zhuǎn)換。

2.5 離散余弦變換

離散余弦變換在處理數(shù)據(jù)時(shí)會(huì)將原始樣本向x軸負(fù)方向?qū)ΨQ擴(kuò)充，對(duì)于實(shí)數(shù)域而言，計(jì)算擴(kuò)充后的傅立葉離散變換根據(jù)三角函數(shù)的奇偶性質(zhì)僅僅需要計(jì)算一半的樣本即可，并且得到的頻域矩陣都是有效的。離散余弦變換的具體公式推斷這里不再詳細(xì)闡述，如感興趣可以點(diǎn)擊此處。其定義如下。

盡管此處僅展示了一維離散余弦變換的公式，但是更高維度的離散余弦變換也存在，此處暫時(shí)不詳細(xì)展開討論。離散傅立葉變換的基本思想也適用于離散余弦變換，但是需要注意此時(shí)系數(shù)都是實(shí)數(shù)。OpenCV提供的離散余弦變換函數(shù)原型如下。

// src：待處理的空域樣本數(shù)據(jù)
// dst：處理后的頻域數(shù)據(jù)
// flag：算法策略，下文詳細(xì)介紹
void cv::dct(cv::InputArray src, cv::OutputArray dst, int flags = 0);

除要求元素必須是實(shí)數(shù)，該函數(shù)的輸入矩陣規(guī)則與函數(shù)cv::dft()類似，由于計(jì)算結(jié)果都為實(shí)數(shù)，輸出矩陣也不再需要處理復(fù)數(shù)的打包。另外和函數(shù)cv::dft()不同，函數(shù)cv::dct()要求輸入矩陣的元素個(gè)數(shù)必須為偶數(shù)，不足位可以用0補(bǔ)齊。當(dāng)參數(shù)flags設(shè)置為cv::DCT_INVERSE表示執(zhí)行離散余弦逆變換，指定為cv::DCT_ROWS可以將輸入的矩陣每一行當(dāng)成是一個(gè)一維隨機(jī)變量樣本進(jìn)行處理，這兩個(gè)值可以用邏輯與符號(hào)同時(shí)選擇。另外由于正變換和逆變換都包含標(biāo)準(zhǔn)化相關(guān)操作，因此不提供類似DFT變換使用的flag參數(shù)cv::DFT_SCALE。

和函數(shù)cv::dft()一樣，函數(shù)cv::dct()的效率也取決于矩陣的尺寸，其最佳尺寸可以通過如下公式計(jì)算，這里暫時(shí)不展開討論原因，因?yàn)檫@涉及到OpenCV內(nèi)部的算法實(shí)現(xiàn)。

size_t optimal_dct_size = 2 * cv::getOptimalDFTSize((N+1) / 2);

2.6 離散余弦逆變換

同樣為了提高代碼的可讀性，OpenCV額外提供如下函數(shù)來執(zhí)行離散余弦變換。該函數(shù)的調(diào)用結(jié)果和函數(shù)cv::dct()使用cv::DCT_INVERSE作為參數(shù)flag的值的調(diào)用結(jié)果相同，當(dāng)然flags是否設(shè)置cv::DCT_ROWS也需要相同。

// src：待處理的空域樣本數(shù)據(jù)
// dst：處理后的頻域數(shù)據(jù)
// flag：算法策略，是否將二維矩陣看作多M行一維向量
void cv::idct(cv::InputArray src, cv::OutputArray dst, int flags = 0);

3 積分圖

積分圖(Integral Image)是一種用于快速計(jì)算指定區(qū)域像素強(qiáng)度和的數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)在很多場(chǎng)景中都非常有用，如Haar微波(Haar wavelets)計(jì)算，該技術(shù)用于人臉識(shí)別和類似算法。

OpenCV支持技術(shù)三種形式的積分圖，分別是和(Sum)、平方和(Square Sum)以及傾斜和(Tilted Sum)積分圖。每種積分圖的尺寸都在原始圖像尺寸的x和y軸上各擴(kuò)展1行或者1列。

標(biāo)準(zhǔn)的求和積分圖的計(jì)算公式如下。

平方和積分圖計(jì)算公式如下。

傾斜求和積分圖計(jì)算公式如下，這種方式等效于將原圖旋轉(zhuǎn)45度。

使用這三組公式可以計(jì)算任意直立或者傾斜的矩形區(qū)域的和、平均值和標(biāo)準(zhǔn)差。從而快速的執(zhí)行模糊、近似梯度等相關(guān)運(yùn)算，即使對(duì)可變窗口的情況而言，也可以快速的執(zhí)行塊相關(guān)運(yùn)算。

例如對(duì)于由頂點(diǎn)(x1, y1)、(x2, y2)，其中x2 > x1, y2 > y1定義的矩形區(qū)域，其內(nèi)部像素和可以由對(duì)應(yīng)的積分圖求出，計(jì)算公式如下。

積分圖的通過逐行逐列的方式計(jì)算，即積分圖內(nèi)的每個(gè)元素都是通過已經(jīng)計(jì)算好的元素計(jì)算得出，其計(jì)算公式如下。

例如對(duì)于一副7??5的灰度圖像而言，其像素統(tǒng)計(jì)結(jié)果如下左圖，其標(biāo)準(zhǔn)和積分圖計(jì)算結(jié)果如下右圖，你可以在下圖中驗(yàn)證上述公式。如計(jì)算原圖中由4個(gè)20強(qiáng)度像素值圍成的矩形區(qū)域內(nèi)像素強(qiáng)度和，可以通過積分圖中對(duì)應(yīng)位置的值計(jì)算，即398-9-10+1 = 380，這種求和方式對(duì)于計(jì)算任意大小的矩形區(qū)域時(shí)間復(fù)雜度都是O(1)。

3.1 標(biāo)準(zhǔn)求和積分圖

標(biāo)準(zhǔn)求和積分圖的函數(shù)原型如下。在處理基本數(shù)據(jù)類型為cv::F32的矩陣時(shí)，盡管也可以指定該格式作為計(jì)算結(jié)果，但是考慮到數(shù)據(jù)溢出的可能性，推薦使用cv::F64。

// image：待處理的圖像，尺寸為M??N
// sum：計(jì)算出的積分圖，尺寸為M+1??N+1
// sdepth：計(jì)算結(jié)果的基本數(shù)據(jù)類型，如cv::F32、cv::S32、cv::F64
void cv::integral(cv::InputArray image, cv::OutputArray sum, int sdepth = -1);

3.2 平方和積分圖

平方和積分圖的函數(shù)原型如下。

// image：待處理的圖像，尺寸為M??N
// sum：計(jì)算出的標(biāo)準(zhǔn)和積分圖，尺寸為M+1??N+1
// sqsum：計(jì)算出的平方和積分圖，尺寸為M+1??N+1
// sdepth：計(jì)算結(jié)果的基本數(shù)據(jù)類型，如cv::F32、cv::S32、cv::F64
void cv::integral(cv::InputArray image,
                 cv::OutputArray sum, cv::OutputArray sqsum,
                 int sdepth = -1);

3.3 傾斜積分圖

傾斜積分圖的函數(shù)原型如下。

// image：待處理的圖像，尺寸為M??N
// sum：計(jì)算出的標(biāo)準(zhǔn)和積分圖，尺寸為M+1??N+1
// sqsum：計(jì)算出的平方和積分圖，尺寸為M+1??N+1
// tilted：計(jì)算出的傾斜積分圖，尺寸為M+1??N+1
// sdepth：計(jì)算結(jié)果的基本數(shù)據(jù)類型，如cv::F32、cv::S32、cv::F64
void cv::integral(cv::InputArray image,
                  cv::OutputArray sum, cv::OutputArray sqsum,
                  cv::OutputArray tilted, int sdepth = -1);

4 Canny邊緣檢測(cè)器

盡管可以直接使用例如拉普拉斯濾鏡等簡(jiǎn)單的濾鏡來檢測(cè)圖像的邊緣，但是這種算法仍有提升的空間。J. Canny在1986年對(duì)這種算法進(jìn)行了優(yōu)化，發(fā)明了Canny邊緣檢測(cè)器(Canny Edge Detector)。Canny優(yōu)化的方式是將計(jì)算得到的x軸和y軸上的一階導(dǎo)數(shù)組合為4個(gè)方向上的導(dǎo)數(shù)。如果一個(gè)點(diǎn)在這四個(gè)方向上的導(dǎo)數(shù)是局部的最大值，則這些點(diǎn)就是邊緣的候選點(diǎn)。該算法的最獨(dú)特的創(chuàng)新點(diǎn)就是將單個(gè)候選邊緣像素組裝成為輪廓(Countours)。在后面的章節(jié)中會(huì)詳細(xì)的對(duì)輪廓展開敘述，目前僅需要知道Canny邊緣檢測(cè)器不會(huì)直接返回檢測(cè)目標(biāo)的輪廓類型，如果需要確定輪廓類型，還需要使用Canny邊緣檢測(cè)器返回的結(jié)果調(diào)用函數(shù)cv::findContours()。

該算法對(duì)像素應(yīng)用滯后閾值(Hysteresis Threshold)從而形成輪廓，也就是該算法使用了兩個(gè)閾值，一個(gè)較大值和一個(gè)較小值。規(guī)則A，如果一個(gè)像素包含比較大值更大的梯度，則其會(huì)被認(rèn)為是邊緣像素。規(guī)則B，如果一個(gè)像素的所有梯度值都低于較小閾值則認(rèn)為不是邊緣像素。規(guī)則C，如果一個(gè)像素不包含比較大值更大的閾值，但是有比較小值更高的閾值，此時(shí)如果它和一個(gè)通過規(guī)則 A確定的邊緣像素相鄰，則它也會(huì)被認(rèn)為是邊緣像素，否則不是。Canny建議的最大和最小閾值的比值為2:1到3:1之間。

下圖是對(duì)圖像應(yīng)用上下閾值粉筆為50和10，即比值為5:1的Canny邊緣檢測(cè)效果。

下圖是對(duì)圖像應(yīng)用上下閾值粉筆為150和100，即比值為3:2的Canny邊緣檢測(cè)效果。

OpenCV定義的Canny邊緣檢測(cè)函數(shù)原型如下。

// image：待處理的圖像矩陣
// edges：處理后的邊緣圖像
// threshold1：低梯度信號(hào)閾值
// threshold2：高梯度信號(hào)閾值
// aperturSize：函數(shù)內(nèi)部依賴的Sobel梯度運(yùn)算使用的孔徑大小
// L2gradient：計(jì)算方向梯度使用的范數(shù)類型，下文詳細(xì)介紹
void cv::Canny(cv::InputArray image, cv::OutputArray edges,
               double threshold1, double threshold2, int apertureSize = 3,
               bool L2gradient = false);

該函數(shù)的參數(shù)L2gradient可以指定計(jì)算方向梯度使用的范數(shù)類型，默認(rèn)值為False，即使用L1范數(shù)，這種方式算法的效率更高，但是得到的方向梯度精確度更低，其計(jì)算公式如下。

當(dāng)參數(shù)L2gradient設(shè)置為true時(shí)，即表示使用L2范數(shù)，其計(jì)算公式如下。

5 霍夫變換

霍夫變換(Hough Transform)可以尋找圖像中的線、圓和其他簡(jiǎn)單形狀。最初的霍夫變換是一個(gè)線性變換，能快速的尋找二值圖像中的直線，該變換經(jīng)過近一步推廣后可以用于尋找其他的簡(jiǎn)單形狀。

5.1 霍夫線變換

霍夫線變換的基本思想是對(duì)于一個(gè)二值圖像中的任意非0點(diǎn)，原圖都有可能存在各個(gè)方向的直線穿越該點(diǎn)。如果將這些線參數(shù)化表示，如使用斜率a和y軸截距b來表示這些直線，則過該點(diǎn)的這些直線在ab組成的坐標(biāo)系中將形成一條新的軌跡。對(duì)于輸入圖像xy平面上的所有非零像素點(diǎn)處理完成后，在ab坐標(biāo)系中具有局部最大值的點(diǎn)就是在原始圖像中存在的曲線，因?yàn)樵瓐D中大量的點(diǎn)都有可能被這條直線穿越。

在實(shí)際實(shí)現(xiàn)的時(shí)候并不會(huì)選擇使用斜率和截距表示一條直線，因?yàn)槭褂眯甭时硎镜闹本€分布密度是非線性的，另外斜率的取-∞到+∞，也不利于表示。因此OpenCV使用極坐標(biāo)系中的點(diǎn)來表示一條直線。如下a圖中對(duì)于原始圖像中的任意一點(diǎn)P(x0, y0)，在b圖中可能存在1、2、3、4等直線過這一點(diǎn)，對(duì)于直線1而言，可以用極坐標(biāo)系中的點(diǎn)Polor(p, θ)來表示唯一的這條直線，直線過該點(diǎn)，并且與該點(diǎn)至圓心的連線錘子。則在c圖中這些直線就可以通過一系列的點(diǎn)形成的軌跡表示。

OpenCV的霍夫算法并不會(huì)直接將這些直線返回，相反它返回了使用極坐標(biāo)表示的定義這些直線的點(diǎn)，如Line(p, θ)。OpenCV支持三種不同類型的霍夫變換，分別是標(biāo)準(zhǔn)霍夫變換(Standard Hough Transform, SHT)、多尺度霍夫變換(Multiscale Hough Transform, MHT)和漸進(jìn)概率霍夫變換(Progressive Probabilities Hough Transform, PPHT)。

標(biāo)準(zhǔn)霍夫變換就是上文所討論到的標(biāo)準(zhǔn)算法，多尺度霍夫變換是多標(biāo)準(zhǔn)霍夫變換的改進(jìn)，得到的匹配直線精確度更高，概率漸進(jìn)霍夫變換是標(biāo)準(zhǔn)霍夫變換的一個(gè)變體，它除了計(jì)算在直線參數(shù)累加平面內(nèi)計(jì)算可能的直線外，還會(huì)計(jì)算直線的長度。這種算法被稱為概率的原因是他不會(huì)在參數(shù)累加平面內(nèi)統(tǒng)計(jì)所有的點(diǎn)，而是只會(huì)計(jì)算部分。它的基本思想是如果峰值足夠高，則花更少的時(shí)間足以尋找到結(jié)果。這種方式能夠大量的減少計(jì)算時(shí)間。

5.1.1 標(biāo)準(zhǔn)霍夫變換和多尺度霍夫變換

標(biāo)準(zhǔn)霍夫變換和多尺度霍夫變換共用一個(gè)函數(shù)，區(qū)別在于最后兩個(gè)參數(shù)是否為0，如果是則為標(biāo)準(zhǔn)霍夫變換，否則為多尺度霍夫變換，其函數(shù)原型如下。

// image：待處理圖像
// lines：N??1矩陣，表示所有尋找到的直線
// rho：參數(shù)累加平面內(nèi)極坐標(biāo)的幅度分辨率，單位為像素
// theta：參數(shù)累加平面內(nèi)極坐標(biāo)的弧度分辨率，單位為弧度
// threshold：非標(biāo)準(zhǔn)化的閾值，即在參數(shù)累加平面內(nèi)某個(gè)點(diǎn)應(yīng)當(dāng)被認(rèn)為定義了原圖中的某條直線的閾值
// srn：多尺度霍夫變換對(duì)幅度分辨率的改進(jìn)
// stn：多尺度霍夫變換對(duì)弧度分辨率的改進(jìn)
void cv::HoughLines(cv::InputArray image, cv::OutputArray lines,
                    double rho, double theta, int threshold,
                    double srn = 0, double stn = 0);

該函數(shù)的輸入圖像的像素?cái)?shù)據(jù)位深度必須為8，但是內(nèi)部會(huì)將其處理為二值圖像，即對(duì)于函數(shù)而言，所有分零值將會(huì)被看作是同一種情況。返回的參數(shù)lines矩陣元素?cái)?shù)據(jù)類型為雙通道浮點(diǎn)型，兩個(gè)通道分別用于存儲(chǔ)定義原圖中直線極坐標(biāo)的幅度和弧度分量。參數(shù)rho和theta定義了直線參數(shù)累加平面的幅度和弧度分辨率，該平面可以被看成是一個(gè)尺寸為rho??theta的二維直方圖。參數(shù)threshold是一個(gè)未標(biāo)準(zhǔn)化的值，因此你需要根據(jù)實(shí)際處理圖像的尺寸來調(diào)整該值的大小，該值可以理解為元素圖像中至少應(yīng)當(dāng)有多少個(gè)像素點(diǎn)在同一條直線上，才認(rèn)為這條直線是實(shí)際存在于原圖中的。

參數(shù)srn和stn是專用于多尺度霍夫變換的，它們指定了更高的分辨率。多尺度霍夫變換先用參數(shù)rho和theta定義的平面計(jì)算原圖可能存在的線的參考點(diǎn)極坐標(biāo)，然后再使用參數(shù)src和stn縮放坐標(biāo)，即最終的直線參數(shù)累加平面的分辨率為rho/src??theta/stn。這里暫時(shí)不需要理解其內(nèi)部細(xì)節(jié)，只需要知道多尺度霍夫變換相較于標(biāo)準(zhǔn)霍夫變換具有更高的精度，但是成本更高即可。

5.1.2 漸進(jìn)概率霍夫變換

漸進(jìn)概率霍夫變換可以尋找線段，這里暫時(shí)不關(guān)注其內(nèi)部的算法實(shí)現(xiàn)，OpenCV提供的函數(shù)原型如下。

// image：待處理的圖像，單通道矩陣
// lines：N??1的4通道矩陣
// rho：參數(shù)累加平面內(nèi)極坐標(biāo)的幅度分辨率，單位為像素
// theta：參數(shù)累加平面內(nèi)極坐標(biāo)的弧度分辨率，單位為弧度
// threshold：非標(biāo)準(zhǔn)化的閾值，即在參數(shù)累加平面內(nèi)某個(gè)點(diǎn)應(yīng)當(dāng)被認(rèn)為定義了原圖中的某條直線的閾值
// minLineLength：線段的最低長度，只有大于這個(gè)長度的線段才會(huì)被通緝
// maxLineGap：線段的最低間隔，小于該間隔的共線線段將會(huì)被連接成一個(gè)線段
void cv::HoughLinesP(cv::InputArray image, cv::OutputArray lines,
                     double rho, double theta, int threshold,
                     double minLineLength = 0, double maxLineGap = 0);

該函數(shù)的輸出矩陣lines和標(biāo)準(zhǔn)霍夫變換以及多尺度霍夫變換函數(shù)不同，該函數(shù)的輸出矩陣是4通道的，分別表示線段的兩個(gè)端點(diǎn)(x0, y0)和(x1, y1)。

對(duì)一副格式圖像和實(shí)際圖像應(yīng)用漸進(jìn)概率霍夫變換的效果如下，可以明顯看到漸進(jìn)霍夫變換能夠找到圖像中的明顯線段。其中漸進(jìn)概率霍夫變換使用的參數(shù)minLineLength和maxLineGap分別是50和10，并且其使用的圖像是先使用Canny邊緣檢查函數(shù)對(duì)原圖像的處理結(jié)果，Canny邊緣檢測(cè)函數(shù)使用的兩個(gè)閾值參數(shù)分別是50和150。

5.2 霍夫圓變換

將霍夫線變換推廣到霍夫圓變換(Hough Circle Transform)，直接推廣到方法是使用三維圓參數(shù)累加空間替代霍夫線變換里使用到的二維參數(shù)累加平面，因?yàn)樵诶奂涌臻g中表示一個(gè)原圖中的唯一圓需要使用圓心的x和y坐標(biāo)分量，以及園半徑這三個(gè)參數(shù)。但是這種方式會(huì)帶來昂貴的內(nèi)存和算法計(jì)算時(shí)間成本，因此OpenCV使用霍夫梯度技術(shù)(Hough Gradient Method)來解決這個(gè)問題。

霍夫圓變換的效果如下圖，在測(cè)試圖像中找到了一個(gè)圓，在風(fēng)景照發(fā)中未發(fā)現(xiàn)圓。需要注意這里首先對(duì)元素圖像進(jìn)行了Canny邊緣檢測(cè)。

霍夫梯度法的工作流程如下，首先對(duì)原圖進(jìn)行邊緣檢測(cè)，對(duì)于上述圖像的示例使用的是Canny邊緣檢測(cè)。然后對(duì)于邊緣檢測(cè)結(jié)果中的每個(gè)非零像素找到其在原圖中對(duì)應(yīng)像素，使用Sobel梯度計(jì)算公式計(jì)算該點(diǎn)在x和y軸上的一階梯度。然后沿著這個(gè)梯度表示的斜率表示的斜率在累加器遍歷從一個(gè)最小值到最大值的點(diǎn)(這部分是直譯，從非原書講述的角度看，非零像素點(diǎn)的索貝爾梯度計(jì)算出的是器在該點(diǎn)的切線，切線的垂線應(yīng)當(dāng)經(jīng)過圓心，因此將切線的垂線在累加平面內(nèi)繪制，則對(duì)于圓心而言會(huì)存在極大值)，并將其值遞增1，同時(shí)記錄邊緣檢測(cè)結(jié)果中所有非0值像素的坐標(biāo)。

當(dāng)處理完邊緣檢測(cè)圖像中的所有非零點(diǎn)后，在累積平面內(nèi)那些比直接臨近點(diǎn)更大的超過指定閾值點(diǎn)局部最大值點(diǎn)，將會(huì)被認(rèn)為是圓心的候選點(diǎn)。這些候選點(diǎn)以值的大小降序排列，然后遍歷這些候選點(diǎn)，如果將邊緣檢測(cè)圖像中提取的非零點(diǎn)以其到候選圓心的距離進(jìn)行排序。權(quán)衡最小距離和最大半徑，選擇一個(gè)能夠囊括更多非零像素的圓的半徑。如果圓囊括了更多的非零像素，并且與之前的圓心具有足夠的距離，則保留該圓心。

這種實(shí)現(xiàn)方式加速了算法的效率，更重要的是克服了三維累加器的稀疏群體問題，這個(gè)問題會(huì)導(dǎo)致更多的噪聲并使得結(jié)果不穩(wěn)定。另外一方面，這個(gè)算法的一些缺點(diǎn)也應(yīng)當(dāng)受到重視。

首先使用Sobel導(dǎo)數(shù)計(jì)算局部梯度估計(jì)切線的方式并不是一個(gè)數(shù)值穩(wěn)定的命題，會(huì)產(chǎn)生一定的噪聲。其次每個(gè)候選中心都需要考慮邊緣檢測(cè)結(jié)果中的所有非零像素值，因此如果設(shè)置的閾值過低，算法會(huì)花很長的時(shí)間去處理這些候選圓心。再次，該算法無法檢測(cè)同心圓，只會(huì)返回其中的一個(gè)，通常返回的是半徑更大的那個(gè)。返回更大圓這種結(jié)果不是必然現(xiàn)象的原因是Sobel導(dǎo)數(shù)計(jì)算會(huì)出現(xiàn)噪聲，對(duì)于分辨率無限大的圖像而言，則必然會(huì)返回最大圓。

霍夫圓檢測(cè)的函數(shù)原型如下。

// image：待檢測(cè)的單通道圖像
// circles：檢測(cè)到的圓，N??1的三通道矩陣或者是Vec3f組成的向量
// method：只能選擇cv::HOUGH_GRADIENT
// dp：累加圖像的分辨率
// minDist：兩個(gè)圓心的最小間距，低于此值會(huì)被認(rèn)為是同一個(gè)圓
// param1：Canny邊緣檢測(cè)器使用的上閾值，下閾值將被設(shè)置為此值的1/2
// param2：未標(biāo)準(zhǔn)化的累加閾值，用于確定候選圓心
// minRadius：尋找到圓的最小搜索半徑
// maxRadius：尋找到圓的最大搜索半徑
void cv::HoughCircles(cv::InputArray image, cv::OutputArray circles,
                      int method, double dp, double minDist,
                      double param1 = 100, double param2 = 100,
                      int minRadius = 0, int maxRadius = 0);

霍夫圓檢測(cè)函數(shù)和霍夫線檢測(cè)函數(shù)的一個(gè)明顯區(qū)別是，函數(shù)cv::HoughCircles()不再限制輸入圖像是二值圖像，因?yàn)樵摵瘮?shù)會(huì)計(jì)算Sobel導(dǎo)數(shù)，因此你可以提供灰度圖像。輸出矩陣circles可能是數(shù)據(jù)類型為CV::F32C3的N??1的三通道矩陣或者是Vec3f組成的向量，每個(gè)元素的三個(gè)分量分別表示檢測(cè)到的圓的圓心以及其半徑。如果使用的是向量，則類型必須是std::vector<Vec3f>。參數(shù)dp是累加圖像的分辨率，我們可以指定使用比原圖更小的分辨率，該值必須大于等于1，最終分辨率為原始圖像分辨率/db。

示例HoughCircles使用函數(shù)cv::HoughCircles()尋找圖像中的圓，其核心代碼如下。

int main(int argc, const char * argv[]) {
    // 讀取原始圖像
    cv::Mat src = cv::imread(argv[1], cv::IMREAD_COLOR);
    
    cv::Mat image;
    // 轉(zhuǎn)換為灰度圖像
    cv::cvtColor(src, image, cv::COLOR_BGR2GRAY);
    
    // 應(yīng)用霍夫圓變換
    std::vector<cv::Vec3f> circles;
    cv::HoughCircles(image, circles, cv::HOUGH_GRADIENT, 2, image.cols/4);

    // 使用霍夫圓變換的結(jié)果在原圖中繪制圓形
    for (size_t i = 0; i < circles.size(); ++i) {
        cv::circle(src,
                   cv::Point(cvRound(circles[i][0]), cvRound(circles[i][1])),
                   cvRound(circles[i][2]),
                   cv::Scalar(0, 0, 255, 1),
                   2, cv::LINE_AA);
    }
    
    // 顯示霍夫圓變換的結(jié)果
    cv::imshow("Hough Circles", src);
    return 0;
}

該示例的運(yùn)行結(jié)果如下圖。

值的思考的是無論我們采取了什么策略，總不能繞過描述一個(gè)圓需要三個(gè)自由度(x, y, r)，描述一條線只需要兩個(gè)自由度(p, θ)的事實(shí)，因此尋找圖像中的圓總會(huì)消費(fèi)更多的內(nèi)存和時(shí)間。所以需要將半徑參數(shù)限定在合理的范圍來控制算法的開銷，實(shí)際上該算法能夠很好的找到圓心，但是并不能十分準(zhǔn)確的找到半徑。在一些特定的應(yīng)用中，如果使用其他算法來尋找準(zhǔn)確的半徑或者只需要圓心數(shù)據(jù)，可以護(hù)綠該算法返回的這部分信息。Ballard在1981年將對(duì)象看作是漸變邊緣的集合，從而將該算法推廣到尋找任意形狀。

6 距離變換

距離變換(Distance Transform)的結(jié)果是一副新的圖像，圖像中的每個(gè)點(diǎn)都等于該點(diǎn)在輸入圖像中對(duì)應(yīng)像素距離零像素點(diǎn)最近距離?？梢悦黠@看出這種變換的典型輸入圖像應(yīng)該是某一種類型的邊緣圖像。在大多數(shù)應(yīng)用中輸入圖像是諸如Canny邊緣檢測(cè)器等邊緣檢測(cè)器的輸出結(jié)果的反轉(zhuǎn)值，即0值表示邊緣，非零值表示非邊緣。

計(jì)算距離變換的方法有兩種，第一種方式使用了3??3或者5??5的矩陣蒙板。矩陣中的每個(gè)點(diǎn)的值被定義為是其到蒙板中心的距離。隨著不斷的移動(dòng)這個(gè)蒙板，直至找到非零像素就能構(gòu)建出一個(gè)當(dāng)前像素距離最近非零像素的距離了，因此使用更大的蒙板會(huì)得到更精確的距離。當(dāng)使用這種方式時(shí)，對(duì)于特定的距離計(jì)算方式，OpenCV需要選擇合適的蒙板，這也是Borgefors在1986年最初發(fā)明的算法。第二種方式計(jì)算精確的距離，由Felzenszwalb提出，這兩種算法的時(shí)間復(fù)雜度都和總像素?cái)?shù)呈線性相關(guān)，但是精確算法會(huì)更慢一點(diǎn)。

6.1 無標(biāo)記的距離變換

未標(biāo)記的距離變換函數(shù)原型如下，

// src：待處理的圖像
// dst：處理完成的圖像，矩陣數(shù)據(jù)類型為cv::F32
// distanceType：計(jì)算距離使用的策略，下文介紹
// maskSize：蒙板尺寸，3、5或者是cv::DIST_MASK_PRECISE
void cv::distanceTransform(cv::InputArray src, cv::OutputArray dst,
                           int distanceType, int maskSize);

參數(shù)distanceType的可選值及其含義如下表。

當(dāng)參數(shù)distanceType設(shè)置為cv::DIST_C和cv::DIST_L1時(shí)，參數(shù)maskSize設(shè)置為3就可以得到準(zhǔn)確的結(jié)果，但是當(dāng)參數(shù)distanceType設(shè)置為cv::DIST_L2時(shí)，Borgefors方法計(jì)算的總是近似距離，因此使用尺寸為5??5的蒙板會(huì)得到更接近實(shí)際值的歐式距離，但是計(jì)算成本會(huì)輕微增加。此外，當(dāng)參數(shù)maskSize設(shè)置為cv::DIST_MASK_PRECISE時(shí)表示需要使用Felzenszwalb算法，但是只適用于計(jì)算cv::DIST_L2類型的距離。

6.2 有標(biāo)記的距離變換

OpenCV提供的函數(shù)還可以在計(jì)算距離變換的同時(shí)，標(biāo)記出每個(gè)像素的目標(biāo)像素(即其最近零像素)。這些對(duì)象被稱為時(shí)連接組件(Connected Components)，將在后面的章節(jié)中介紹，現(xiàn)在只需要將他們理解為連續(xù)的零像素組成的結(jié)構(gòu)。其函數(shù)原型如下。

// src：待處理的圖像
// dst：處理完成的圖像
// labels：連接組件的標(biāo)識(shí)
// distanceType：計(jì)算距離使用的策略
// maskSize：蒙板尺寸，3、5或者是cv::DIST_MASK_PRECISE
// labelType：標(biāo)識(shí)策略
void cv::distanceTransform(cv::InputArray src, cv::OutputArray dst, 
                           cv::OutputArray labels,
                           int distanceType, int maskSize,
                           int labelType = cv::DIST_LABEL_CCOMP);

返回的標(biāo)識(shí)矩陣labels尺寸和輸入圖像相同，其中的每個(gè)元素表示該點(diǎn)在輸入圖像中對(duì)應(yīng)點(diǎn)的最近連接組件的標(biāo)識(shí)，或者是最近零像素的坐標(biāo)，這取決于下文將要將到的參數(shù)labelType的取值。得到的label矩陣也被稱為離散Voronoi圖，或者是泰森多邊形，或是諾圖。

參數(shù)labelType有兩個(gè)可選值，其中cv::DIST_LABEL_CCOMP表示算法會(huì)自動(dòng)將輸入圖像中的相連接的非零像素被劃分為一個(gè)連接組件，并且為每個(gè)連接組件分配不同的標(biāo)識(shí)。cv::DIST_LABEL_PIXEL表示會(huì)為輸入圖像中的每個(gè)非零像素分配不同的標(biāo)識(shí)。

連通分量或者非零像素的標(biāo)簽是由該算法自動(dòng)生成的，由于零像素的最近零像素就是自己，當(dāng)參數(shù)labelType設(shè)置為cv::DIST_LABEL_PIXEL時(shí)，輸出矩陣label中該點(diǎn)的值直接等于這個(gè)標(biāo)識(shí)。當(dāng)參數(shù)labelType設(shè)置為cv::DIST_LABEL_CCOMP時(shí)，該零像素屬于連通分量的一部分，因此它和連通分量共享同一個(gè)標(biāo)簽。所以在任何情況下，如果想要知道原圖中任意零像素的標(biāo)簽，只需要查詢函數(shù)輸出參數(shù)labels中對(duì)應(yīng)像素的標(biāo)簽即可。

7 圖像分割

圖像分割是一個(gè)很大的話題，我們已經(jīng)在多個(gè)地方接觸到它，在后面的文章中會(huì)單獨(dú)安排章節(jié)詳細(xì)探討。這里先聚焦幾個(gè)OpenCV提供的方法，這些技術(shù)要么本身就是圖像分割方法，要么它們處理的結(jié)果將會(huì)服務(wù)于后面章節(jié)將到的更復(fù)雜的圖像學(xué)技術(shù)。需要注意即使目前也沒有一個(gè)通用的絕對(duì)靈驗(yàn)的圖像分割方法，這個(gè)話題仍然是計(jì)算機(jī)視覺領(lǐng)域活躍的研究方向。盡管如果，目前仍在一些特定的領(lǐng)域發(fā)展處理可靠的技術(shù)，實(shí)際應(yīng)用中它們也能得到較好的結(jié)果。

7.1 浸水填充

浸水填充(Flood fill)在標(biāo)記或者分離圖像中的區(qū)塊場(chǎng)景中十分有用，通常使用該算法得到的結(jié)果用于進(jìn)一步的圖像處理。浸水填充也可以從輸入圖像中計(jì)算得到一個(gè)特殊的蒙板，該蒙板可以用于加速后續(xù)函數(shù)的計(jì)算速度或者限制其只處理被該蒙板標(biāo)識(shí)的區(qū)域。

相比于其他計(jì)算機(jī)繪圖程序，OpenCV中的浸水填充是一種更一般化的填充方法。這些填充算法首先都會(huì)在圖像中確定一個(gè)種子點(diǎn)(Seed Point)，然后使用同一種顏色為其以及其鄰近的相似像素點(diǎn)著色。這些填充算法的區(qū)別是，OpenCV的浸水填充算法并不嚴(yán)格要求這些鄰近像素的顏色完全相同。浸水填充的結(jié)果總會(huì)是一個(gè)連續(xù)的區(qū)域，即原圖中的單個(gè)連通區(qū)塊。如果某個(gè)像素和其相鄰像素，或者是與之前選定的種子點(diǎn)，的顏色強(qiáng)度值在指定的偏差范圍內(nèi)，則該算法會(huì)為該像素著色。通過一個(gè)額外的蒙板矩陣也可以限制浸水填充的范圍。OpenCV提供的浸水填充函數(shù)有兩個(gè)形式，它們的原型如下。

// image：待處理的輸入圖像，單通道或者三通道，8位整型或者32位浮點(diǎn)型數(shù)據(jù)
// seed：浸水填充開始的種子點(diǎn)
// newVal：填充的顏色值
// rect：輸出參數(shù)，描述重繪區(qū)域的最小矩形
// lowDiff：向下的強(qiáng)度偏差，即【當(dāng)前像素強(qiáng)度 > 參考像素強(qiáng)度 - lowDiff】時(shí)
//         并且滿足highDiff的限制，則當(dāng)前像素會(huì)被填充
// highDiff：向上的強(qiáng)度偏差，即【當(dāng)前像素強(qiáng)度 < 參考像素強(qiáng)度 + highDiff】時(shí)
//          并且滿足lowDiff的限制，則當(dāng)前像素會(huì)被填充
// flags：算法內(nèi)部計(jì)算策略，包括像素比較策略等等，下文介紹
int cv::floodFill(cv::InputOutputArray image,
                  cv::Point seed, cv::Scalar newVal, cv::Rect* rect,
                  cv::Scalar lowDiff = cv::Scalar(),
                  cv::Scalar highDiff = cv::Scalar(),
                  int flags);

// image：待處理的輸入圖像，單通道或者三通道，8位整型或者32位浮點(diǎn)型數(shù)據(jù)，尺寸為W??H
// mask：蒙板矩陣，尺寸為W+2??H+2，單通道，位深度為8，用于控制填充范圍等，下文介紹
int cv::floodFill(cv::InputOutputArray image, cv::InputOutputArray mask, 
                  cv::Point seed, cv::Scalar newVal, cv::Rect* rect,
                  cv::Scalar lowDiff = cv::Scalar(),
                  cv::Scalar highDiff = cv::Scalar(),
                  int flags);

通常情況下，該函數(shù)會(huì)修改輸入圖像矩陣image的數(shù)據(jù)。該函數(shù)首先將指定的種子點(diǎn)涂成參數(shù)newVal指定的顏色，然后向周圍擴(kuò)散處理其他的像素。如果在參數(shù)flags指定的比較策略下，像素的顏色強(qiáng)度滿足參數(shù)lowDiff和highDiff指定的條件，則當(dāng)前像素也會(huì)被涂成指定的顏色。參數(shù)newVal，loDiff和upDiff的數(shù)據(jù)類型都是cv::Scalar，也就是我們可以分別限制RGB三個(gè)顏色通道的像素強(qiáng)度偏差范圍。

參數(shù)mask的寬高都應(yīng)當(dāng)比輸入圖像的尺寸大2，可以看作是向上下左右四個(gè)方向各擴(kuò)展一個(gè)維度。另外該參數(shù)可以同時(shí)被看作是輸入和輸出參數(shù)，作為輸入?yún)?shù)而言只有mask矩陣中非0值對(duì)應(yīng)的像素才有可能被上色。作為輸出參數(shù)而言，當(dāng)算法運(yùn)行后實(shí)際被上色的像素對(duì)應(yīng)的元素將會(huì)被設(shè)置為指定的非0值。

需要注意的是蒙板矩陣的基本數(shù)據(jù)類型為8位整型，如果你直接在窗口中展示該圖，則有可能看見的是一副黑色的圖像。這可能是因?yàn)槠渲械脑刂堤?，因?yàn)閷?duì)于格式為8位整型的圖像而言，其像素強(qiáng)度的取值空間為0到255，你只需要適當(dāng)對(duì)原數(shù)據(jù)進(jìn)行縮放即可。

參數(shù)flags包含了多個(gè)含義，它是一個(gè)32位的整型數(shù)據(jù)，其中低8位(0-7)用于指定算法在考慮相鄰像素的連通策略。可選值有4和8，分別表示4連通和8連通，前者表示浸水算法應(yīng)當(dāng)考慮上下左右四個(gè)相鄰像素，后者表示在前者基礎(chǔ)上還應(yīng)當(dāng)考慮對(duì)角線上的4個(gè)共8個(gè)相鄰像素。

中間8位(8-15)用于指定滿足前文描述的相關(guān)條件時(shí)，蒙板元素應(yīng)當(dāng)被填充的值，如果設(shè)置為0或者未設(shè)置，則默認(rèn)使用1。

高8位(16-23)則用于指定像素比較的策略以及是否需要修改原圖，當(dāng)flags包含cv::FLOODFILL_FIXED_RANGE時(shí)，比較的參考像是是選定的種子像素，否則比較相鄰像素，當(dāng)flags包含cv::FLOODFILL_MASK_ONLY時(shí)，該函數(shù)只會(huì)更新蒙板矩陣mask的值，而不會(huì)修改原圖。

參數(shù)flags在3個(gè)位段段選項(xiàng)可以用邏輯與符號(hào)連接得到最終的值，例如如果需要使用8連通的相鄰像素推斷策略，并且僅和種子像素比較(原書中同時(shí)設(shè)置該策略和連通性，此時(shí)連通性的設(shè)置可能會(huì)被忽略，推測(cè)此處僅為演示flags參數(shù)的設(shè)置方法)，并且僅更新蒙板矩陣，并且使用47填充蒙板矩陣，則參數(shù)flags的設(shè)置方式如下。

flags = 8
        | cv::FLOODFILL_MASK_ONLY
        | cv::FLOODFILL_FIXED_RANGE
        | (47 << 8);

下圖展示了一個(gè)浸水算法應(yīng)用于圖像處理的結(jié)果，黑色小圓圈表示的是選定的種子像素，它們的像素強(qiáng)度偏差范圍參數(shù)都設(shè)置為7，其中上圖的填充色為灰色，下圖為白色。

下圖是對(duì)通一副圖像應(yīng)用不同參數(shù)的浸水算法對(duì)處理的結(jié)果，與上一個(gè)示例不同的是此次選擇了cv::FLOODFILL_FIXED_RANGE的比較策略，通過與種子點(diǎn)比較從而獲得更大范圍的填充效果(推斷比較相鄰點(diǎn)需要所有相鄰像素滿足限制條件，而與種子點(diǎn)比較只考慮當(dāng)前像素，因此能夠沿著細(xì)小裂隙滲透到更大的范圍)。

7.2 分水嶺算法

很多時(shí)候想要分割一副圖像，但是卻沒有可用的圖片分割背景蒙板，此時(shí)可以使用分水嶺算法(Watershed Algorithm)來解決問題。該算法通過計(jì)算圖像的像素強(qiáng)度梯度來確定邊界，并將這些邊界轉(zhuǎn)化為山脊，被這些山脊分割的區(qū)域被看作是谷地或者盆地。用戶需要預(yù)先指定一些點(diǎn)作為不同區(qū)塊的標(biāo)識(shí)點(diǎn)，算法隨后會(huì)從這些標(biāo)識(shí)點(diǎn)向這些盆地灌水直至填充滿整個(gè)圖像，并使用標(biāo)識(shí)點(diǎn)的值來標(biāo)記其被包含的區(qū)塊，從而達(dá)到分割圖像的目的。

此外你也可以在原始圖像中繪制一系列的線條，每個(gè)線條都表示你想要分割出的一塊區(qū)域，并在標(biāo)記矩陣中使用不同的值表示每個(gè)線條。在已經(jīng)通過梯度計(jì)算處理好的山脊-盆地圖中，分水嶺算法將會(huì)把這些線條跨越的以及臨近的盆地合并，并賦予其與對(duì)應(yīng)線條相同的標(biāo)記，從而達(dá)到圖像分割的目的。

下圖是一個(gè)通過線條標(biāo)識(shí)應(yīng)用分水嶺算法處理圖像的示例，左圖中每個(gè)線條都標(biāo)識(shí)了一個(gè)獨(dú)立的分區(qū)，在右圖中分水嶺算法成功將圖像分割為多個(gè)區(qū)塊。

分水嶺算法的函數(shù)原型如下。

// image：待處理的圖像，通道數(shù)為3，數(shù)據(jù)類型為8位整型
// markers：標(biāo)記矩陣，通道數(shù)為1，數(shù)據(jù)類型為32位整型，尺寸和image相同
void cv::watershed(cv::InputArray image, cv::InputOutputArray markers);

該函數(shù)傳入的參數(shù)markers矩陣中，除了認(rèn)為屬于同一個(gè)區(qū)域的像素點(diǎn)使用同一個(gè)正值表示，如上圖中每條直線對(duì)應(yīng)的點(diǎn)都使用同一個(gè)正值表示，其余元素都應(yīng)設(shè)置為0。當(dāng)算法執(zhí)行完畢后，對(duì)于markers矩陣中的所有非零像素，如果為邊界像素將會(huì)被設(shè)置為-1，否則將會(huì)被設(shè)置為其所屬區(qū)域的標(biāo)記值。理想情況下所有區(qū)域都應(yīng)該被值為-1表示的邊界分割，但是實(shí)際上并不能得到這樣的結(jié)果。很簡(jiǎn)單的一個(gè)例子就是如果傳入的標(biāo)記矩陣中兩個(gè)相鄰像素的值不為0，并且不相同，則輸出結(jié)果中它們會(huì)保持不變，并且也不會(huì)被-1標(biāo)識(shí)的邊界所分隔。

7.3 Crabcuts算法

Rother、Kolmogorov和Blake對(duì)Graphcuts算法進(jìn)行改進(jìn)得到Grabcuts算法，該算法能夠用于處理用戶主導(dǎo)的前景和背景圖像分割問題。該算法能夠得到很好的分割結(jié)果，通常不會(huì)超過待分割的前景圖的限制矩形(調(diào)用者指定的)區(qū)域。

傳統(tǒng)的Graphcuts算法使用用戶標(biāo)記的背景區(qū)域和前景區(qū)域建立分布直方圖。然后假設(shè)在理想情況下未標(biāo)記的背景和前景區(qū)域應(yīng)當(dāng)和已經(jīng)標(biāo)記的對(duì)應(yīng)區(qū)域有相似的分布，當(dāng)然理想情況下這些區(qū)域應(yīng)當(dāng)是平滑并且相連的，實(shí)際上卻可能包含很多斑點(diǎn)。這些假設(shè)最終會(huì)組合成能量函數(shù)(Energy Functional)，該能量函數(shù)會(huì)給出一個(gè)遵守這些假設(shè)的低成本解決方案，以及一個(gè)不遵守這些假設(shè)的高成本解決方案。算法通過最小化能量函數(shù)計(jì)算最終的結(jié)果，通常使用一種稱為Mincut的技術(shù)，這也是Graphcuts算法和Grabcuts命名的由來。

Grabcuts通過如下幾個(gè)重要的方式改進(jìn)了Graphcuts算法。首先它使用了高斯混合模型(Gaussian Mixture Model)替代了直方圖模型，因此能夠處理彩色圖像。另外它使用迭代的方式來解決能量函數(shù)最小化問題，因此提供更好的全局結(jié)果，并且增加了用戶提供標(biāo)記的靈活性。此外這種方式使算法能夠支持單一標(biāo)記，即用戶只需要前景圖或者背景圖，而使用Graphcuts算法需要同時(shí)標(biāo)記這兩個(gè)區(qū)域。

OpenCV提供的函數(shù)原型如下。

// img：待分割的圖像
// mask：前景背景標(biāo)識(shí)蒙板，通道數(shù)為1，數(shù)據(jù)類型為cv::U8
// rect：待分割的區(qū)域矩形，矩形外部都被認(rèn)為是背景區(qū)域
// bgdModel：背景緩存，下文介紹
// fgdModel：前景緩存，下文介紹
// iterCount：內(nèi)部Graphcuts算法的迭代次數(shù)
// mode：算法策略，下文介紹
void cv::grabCut(cv::InputArray img, cv::InputOutputArray mask, cv::Rect rect,
                 cv::InputOutputArray bgdModel, cv::InputOutputArray fgdModel,
                 int iterCount, int mode = cv::GC_EVAL);

參數(shù)mask可以同時(shí)看作是輸入矩陣和輸出矩陣，當(dāng)參數(shù)mode包含cv::GC_INIT_WITH_MASK時(shí)，該值作為輸入矩陣參與算法的計(jì)算，矩陣中的每個(gè)元素取值必須符合該函數(shù)的規(guī)定，它們可取值及其含義如下表。

此時(shí)算法會(huì)通過分析標(biāo)記的確定區(qū)域識(shí)別疑似區(qū)域?yàn)榇_定的區(qū)域。作為輸出矩陣而言，該矩陣用于保存函數(shù)識(shí)別的結(jié)果。當(dāng)不使用mask矩陣初始化原圖中的前景和背景區(qū)域時(shí)，需要提供參數(shù)rect，并且此時(shí)參數(shù)mode應(yīng)當(dāng)包含cv::GC_INIT_WITH_RECT。此時(shí)矩形的外部區(qū)域會(huì)被認(rèn)為是確定的背景區(qū)域，而矩形內(nèi)部區(qū)域會(huì)被認(rèn)為是疑似的前景區(qū)域。

參數(shù)bgdModel和fgdModel分別是前景和背景緩存，當(dāng)?shù)谝淮握{(diào)用該函數(shù)執(zhí)行iterCount次迭代時(shí)可以直接傳入空矩陣。當(dāng)因?yàn)槟硞€(gè)原因需要再次調(diào)用該函數(shù)再執(zhí)行幾次迭代時(shí)，可能是用戶提供了額外的確定前景或背景信息，除了將上一次計(jì)算的到的蒙板矩陣作為本次函數(shù)調(diào)用的輸入外，你還需要將上一次該函數(shù)調(diào)用后的返回的緩存矩陣作為參數(shù)傳入到當(dāng)前次的調(diào)用函數(shù)中。

Grabcuts算法內(nèi)部會(huì)多次調(diào)用Graphcuts算法，當(dāng)然包含前文提到的一些改進(jìn)，并且每次調(diào)用都會(huì)重新計(jì)算混合模型。參數(shù)iterCount指定了迭代的次數(shù)，通常設(shè)置為10或者12，不過它的大小也還需取決于被處理圖像的大小和性質(zhì)。

7.4 Mean-Shift分割算法

Mean-Shift圖像分割算法用于尋找顏色再空間分布上的峰值，它和Mean-Shift算法相關(guān)，后者將會(huì)在討論運(yùn)動(dòng)和追蹤時(shí)詳細(xì)聊到。它們之間的區(qū)別是前者關(guān)注的是顏色在空間上的分別，而后者通過連續(xù)的幀在時(shí)間上追蹤這些分布。

給定維度為(x, y, blue, green, red)的數(shù)據(jù)點(diǎn)集，mean-shift算法可以通過窗口掃描指定在空間找到密度最高的塊?？臻g變量(x, y)的范圍可以和顏色強(qiáng)度范圍(blue, green, red)相差較大，因此該算法需要兩個(gè)不同的窗口半徑分別計(jì)算空間和顏色變量。隨著mean-shift滑動(dòng)窗口移動(dòng)，窗口遍歷到的所有收斂于峰值的點(diǎn)都應(yīng)當(dāng)連接或擁有該峰值。這種所有權(quán)從最密集的峰值處向外輻射，從而達(dá)到了分割圖像的目的。

圖像分割實(shí)際上是在圖像金字塔中完成的，即使用道理前面章節(jié)中介紹的函數(shù)cv::pyrUp()和cv::pyrDown()。在圖像金字塔的高層圖像中的顏色聚類(Color Clusters)會(huì)在低層的圖像中有更明確的邊界。

Mean-Shift圖像分割算法的輸出是一副色調(diào)分離(Posterized)的新圖像，即其中的紋理細(xì)節(jié)被移除，顏色梯度也變得更加平坦。你可以使用合適的算法進(jìn)一步處理該算法的輸出結(jié)果，如使用函數(shù)cv::Canny()和cv::findCountours()尋找圖像中的輪廓。OpenCV提供的函數(shù)原型如下。

// src：待處理的圖像，通道數(shù)為3，數(shù)據(jù)類型為8位整型
// dst：處理完成的圖像，通道數(shù)為3，數(shù)據(jù)類型為8位整型，尺寸和src相同
// sp：滑動(dòng)窗口的空間半徑
// sr：滑動(dòng)窗口的顏色半徑
// maxLevel：圖像金字塔的最大層數(shù)
// termcrit：迭代終止條件，不設(shè)置時(shí)使用默認(rèn)值
void cv::pyrMeanShiftFiltering(cv::InputArray src, cv::OutputArray dst,
                               cv::double sp, cv::double sr, int maxLevel = 1,
                               cv::TermCriteria termcrit = TermCriteria(
                                cv::TermCriteria::MAX_ITER | cv::TermCriteria::EPS,
                                5, 1));

對(duì)于一個(gè)640??480點(diǎn)彩色圖像而言，參數(shù)sp和sr的建議值分別為2和40，參數(shù)maxLevel建議值為2或者3。該算法內(nèi)部會(huì)包含迭代邏輯，而參數(shù)termcrit可以指定迭代邏輯的終止條件，實(shí)際使用是可以將該參數(shù)留空使用默認(rèn)值。

下圖是一個(gè)Mean-Shift圖像分割示例的運(yùn)行結(jié)果，其中參數(shù)sp和sr分別設(shè)置為2和40，參數(shù)maxLevel設(shè)置為2。

8 小結(jié)

前一章節(jié)介紹了一般的圖像變換技術(shù)，而在本章中詳細(xì)討論了圖像分析技術(shù)，這些技術(shù)使我們對(duì)圖像有了更深入的了解，睡著本系列文章的不斷深入，我們將會(huì)學(xué)到更多更復(fù)雜的圖像處理技術(shù)，而本章及上一章學(xué)到的這些知識(shí)將是這些高級(jí)圖像處理技術(shù)的基礎(chǔ)。