|
|
【答案】應(yīng)助回帖
★
jjdg: 金幣+1, 感謝參與 2012-10-24 10:13:25
尺度空間理論
自然界中的物體隨著觀測(cè)尺度不同有不同的表現(xiàn)形態(tài)。例如我們形容建筑物用“米”，觀測(cè)分子、原子等用“納米”。更形象的例子比如Google地圖，滑動(dòng)鼠標(biāo)輪可以改變觀測(cè)地圖的尺度，看到的地圖繪制也不同；還有電影中的拉伸鏡頭等等……
尺度空間中各尺度圖像的模糊程度逐漸變大，能夠模擬人在距離目標(biāo)由近到遠(yuǎn)時(shí)目標(biāo)在視網(wǎng)膜上的形成過程。
尺度越大圖像越模糊。
為什么要討論尺度空間？
用機(jī)器視覺系統(tǒng)分析未知場(chǎng)景時(shí)，計(jì)算機(jī)并不預(yù)先知道圖像中物體的尺度。我們需要同時(shí)考慮圖像在多尺度下的描述，獲知感興趣物體的最佳尺度。另外如果不同的尺度下都有同樣的關(guān)鍵點(diǎn)，那么在不同的尺度的輸入圖像下就都可以檢測(cè)出來關(guān)鍵點(diǎn)匹配，也就是尺度不變性。
圖像的尺度空間表達(dá)就是圖像在所有尺度下的描述。
尺度空間表達(dá)與金字塔多分辨率表達(dá)
高斯模糊
高斯核是唯一可以產(chǎn)生多尺度空間的核（《Scale-space theory: A basic tool for analysing structures at different scales》）。一個(gè)圖像的尺度空間L(x,y,σ) ,定義為原始圖像I(x,y)與一個(gè)可變尺度的2維高斯函數(shù)G(x,y,σ)卷積運(yùn)算。
二維空間高斯函數(shù)：
尺度空間：
尺度是自然客觀存在的，不是主觀創(chuàng)造的。高斯卷積只是表現(xiàn)尺度空間的一種形式。
二維空間高斯函數(shù)是等高線從中心成正太分布的同心圓：
分布不為零的點(diǎn)組成卷積陣與原始圖像做變換，即每個(gè)像素值是周圍相鄰像素值的高斯平均。一個(gè)5*5的高斯模版如下所示：
高斯模版是圓對(duì)稱的，且卷積的結(jié)果使原始像素值有最大的權(quán)重，距離中心越遠(yuǎn)的相鄰像素值權(quán)重也越小。
在實(shí)際應(yīng)用中，在計(jì)算高斯函數(shù)的離散近似時(shí)，在大概3σ距離之外的像素都可以看作不起作用，這些像素的計(jì)算也就可以忽略。所以，通常程序只計(jì)算(6σ+1)*(6σ+1)就可以保證相關(guān)像素影響。
高斯模糊另一個(gè)很厲害的性質(zhì)就是線性可分：使用二維矩陣變換的高斯模糊可以通過在水平和豎直方向各進(jìn)行一維高斯矩陣變換相加得到。
O(N^2*m*n)次乘法就縮減成了O(N*m*n)+O(N*m*n)次乘法。（N為高斯核大小，m,n為二維圖像高和寬）
其實(shí)高斯這一部分只需要簡(jiǎn)單了解就可以了，在OpenCV也只需要一句代碼：
[cpp] view plaincopy
GaussianBlur(dbl, dbl, Size(), sig_diff, sig_diff);
我這里詳寫了一下是因?yàn)檫@塊兒對(duì)分析算法效率比較有用，而且高斯模糊的算法真的很漂亮~
金字塔多分辨率
金字塔是早期圖像多尺度的表示形式。圖像金字塔化一般包括兩個(gè)步驟：使用低通濾波器平滑圖像；對(duì)平滑圖像進(jìn)行降采樣（通常是水平，豎直方向1/2），從而得到一系列尺寸縮小的圖像。
上圖中（a）是對(duì)原始信號(hào)進(jìn)行低通濾波，（b）是降采樣得到的信號(hào)。
而對(duì)于二維圖像，一個(gè)傳統(tǒng)的金字塔中，每一層圖像由上一層分辨率的長(zhǎng)、寬各一半，也就是四分之一的像素組成：
多尺度和多分辨率
尺度空間表達(dá)和金字塔多分辨率表達(dá)之間最大的不同是：
尺度空間表達(dá)是由不同高斯核平滑卷積得到，在所有尺度上有相同的分辨率；
而金字塔多分辨率表達(dá)每層分辨率減少固定比率。
所以，金字塔多分辨率生成較快，且占用存儲(chǔ)空間少；而多尺度表達(dá)隨著尺度參數(shù)的增加冗余信息也變多。
多尺度表達(dá)的優(yōu)點(diǎn)在于圖像的局部特征可以用簡(jiǎn)單的形式在不同尺度上描述；而金字塔表達(dá)沒有理論基礎(chǔ)，難以分析圖像局部特征。
DoG（Difference of Gaussian）
高斯拉普拉斯LoG金字塔
結(jié)合尺度空間表達(dá)和金字塔多分辨率表達(dá)，就是在使用尺度空間時(shí)使用金字塔表示，也就是計(jì)算機(jī)視覺中最有名的拉普拉斯金子塔（《The Laplacian pyramid as a compact image code》）。
高斯拉普拉斯LoG（Laplace of Guassian）算子就是對(duì)高斯函數(shù)進(jìn)行拉普拉斯變換：
核心思想還是高斯，這個(gè)不多敘述。
高斯差分DoG金字塔
DoG（Difference of Gaussian）其實(shí)是對(duì)高斯拉普拉斯LoG的近似，也就是對(duì)的近似。SIFT算法建議，在某一尺度上的特征檢測(cè)可以通過對(duì)兩個(gè)相鄰高斯尺度空間的圖像相減，得到DoG的響應(yīng)值圖像D(x,y,σ)。然后仿照LoG方法，通過對(duì)響應(yīng)值圖像D(x,y,σ)進(jìn)行局部最大值搜索，在空間位置和尺度空間定位局部特征點(diǎn)。其中：
k為相鄰兩個(gè)尺度空間倍數(shù)的常數(shù)。
上圖中（a）是DoG的三維圖，（b）是DoG與LoG的對(duì)比。
金字塔構(gòu)建
構(gòu)建高斯金字塔
為了得到DoG圖像，先要構(gòu)造高斯金字塔。我們回過頭來繼續(xù)說高斯金字塔~
高斯金字塔在多分辨率金字塔簡(jiǎn)單降采樣基礎(chǔ)上加了高斯濾波，也就是對(duì)金字塔每層圖像用不同參數(shù)的σ做高斯模糊，使得每層金字塔有多張高斯模糊圖像。金字塔每層多張圖像合稱為一組（Octave），每組有多張（也叫層Interval）圖像。另外，降采樣時(shí)，金字塔上邊一組圖像的第一張圖像（最底層的一張）是由前一組（金字塔下面一組）圖像的倒數(shù)第三張隔點(diǎn)采樣得到。
以下是OpenCV中構(gòu)建高斯金字塔的代碼，我加了相應(yīng)的注釋：
[cpp] view plaincopy
// 構(gòu)建nOctaves組（每組nOctaves+3層）高斯金字塔
void SIFT::buildGaussianPyramid( const Mat& base, vector& pyr, int nOctaves ) const
{
vector sig(nOctaveLayers + 3);
pyr.resize(nOctaves*(nOctaveLayers + 3));
// precompute Gaussian sigmas using the following formula:
// \sigma_{total}^2 = \sigma_{i}^2 + \sigma_{i-1}^2、
// 計(jì)算對(duì)圖像做不同尺度高斯模糊的尺度因子
sig[0] = sigma;
double k = pow( 2., 1. / nOctaveLayers );
for( int i = 1; i < nOctaveLayers + 3; i++ )
{
double sig_prev = pow(k, (double)(i-1))*sigma;
double sig_total = sig_prev*k;
sig = std::sqrt(sig_total*sig_total - sig_prev*sig_prev);
}
for( int o = 0; o < nOctaves; o++ )
{
// DoG金子塔需要nOctaveLayers+2層圖像來檢測(cè)nOctaves層尺度
// 所以高斯金字塔需要nOctaveLayers+3層圖像得到nOctaveLayers+2層DoG金字塔
for( int i = 0; i < nOctaveLayers + 3; i++ )
{
// dst為第o組（Octave）金字塔
Mat& dst = pyr[o*(nOctaveLayers + 3) + i];
// 第0組第0層為原始圖像
if( o == 0 && i == 0 )
dst = base;
// base of new octave is halved image from end of previous octave
// 每一組第0副圖像時(shí)上一組倒數(shù)第三幅圖像隔點(diǎn)采樣得到
else if( i == 0 )
{
const Mat& src = pyr[(o-1)*(nOctaveLayers + 3) + nOctaveLayers];
resize(src, dst, Size(src.cols/2, src.rows/2),
0, 0, INTER_NEAREST);
}
// 每一組第i副圖像是由第i-1副圖像進(jìn)行sig的高斯模糊得到
// 也就是本組圖像在sig的尺度空間下的圖像
else
{
const Mat& src = pyr[o*(nOctaveLayers + 3) + i-1];
GaussianBlur(src, dst, Size(), sig, sig);
}
}
}
}
高斯金字塔的組數(shù)為：
代碼10-17行是計(jì)算高斯模糊的系數(shù)σ，具體關(guān)系如下：
其中，σ為尺度空間坐標(biāo)，s為每組中層坐標(biāo)，σ0為初始尺度，S為每組層數(shù)（一般為3~5）。根據(jù)這個(gè)公式，我們可以得到金字塔組內(nèi)各層尺度以及組間各圖像尺度關(guān)系。
組內(nèi)相鄰圖像尺度關(guān)系：
相鄰組間尺度關(guān)系：
所以，相鄰兩組的同一層尺度為2倍的關(guān)系。
最終尺度序列總結(jié)為：
o為金字塔組數(shù)，n為每組金字塔層數(shù)。
構(gòu)建DoG金字塔
構(gòu)建高斯金字塔之后，就是用金字塔相鄰圖像相減構(gòu)造DoG金字塔。
下面為構(gòu)造DoG的代碼：
[cpp] view plaincopy
// 構(gòu)建nOctaves組（每組nOctaves+2層）高斯差分金字塔
void SIFT::buildDoGPyramid( const vector& gpyr, vector& dogpyr ) const
{
int nOctaves = (int)gpyr.size()/(nOctaveLayers + 3);
dogpyr.resize( nOctaves*(nOctaveLayers + 2) );
for( int o = 0; o < nOctaves; o++ )
{
for( int i = 0; i < nOctaveLayers + 2; i++ )
{
// 第o組第i副圖像為高斯金字塔中第o組第i+1和i組圖像相減得到
const Mat& src1 = gpyr[o*(nOctaveLayers + 3) + i];
const Mat& src2 = gpyr[o*(nOctaveLayers + 3) + i + 1];
Mat& dst = dogpyr[o*(nOctaveLayers + 2) + i];
subtract(src2, src1, dst, noArray(), CV_16S);
}
}
}
這個(gè)比較簡(jiǎn)單，就是一個(gè)subtract()函數(shù)。
至此，SIFT第一步就完成了。參見《SIFT原理與源碼分析》
轉(zhuǎn)載請(qǐng)注明出處：http://blog.csdn.net/xiaowei_cqu/article/details/8067881 |
|
回復(fù)此樓
