計算視覺常用技術和相關技術

1、計算視覺常用技術和相關技術1、圖形的相似變換由一個圖形到另一個圖形，在改變的過程中保持形狀不變（大小可變），這樣的 圖形改變叫做圖形的相似變換（similarty transformation）o圖形相似變換的性質(zhì)： 圖形的相似變換不改變圖形中每一個角的大?。粓D形中的每條線段都擴大（或縮 ?。┫嗤谋稊?shù)。相似變換：設M是方陣，P是一個同階可逆矩陣（即行列式 不為零，也稱非奇異矩陣），N=PA（-1）MP稱為M的相似變換。相似變換面積： 相似變換的實質(zhì)就是圖形形狀不變，圖形上的任意兩點之間的距離都放大或縮小 相同的倍數(shù)，因此，經(jīng)相似變換的像與原圖對應的線段和周長比等于相比，經(jīng)相 似變換的像與原圖

2、的面積等于相似比的平方。2、SIFT特征是圖像的局部特征，其對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性， 對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。Sift特征匹配算法可以 處理兩幅圖像之間發(fā)生平移、旋轉(zhuǎn)、仿射變換情況下的匹配問題，具有很強的匹 配能力。SURF算法是SIFT算法的加速版，opencv的SURF算法在適中的條件下完成兩 幅圖像中物體的匹配基本實現(xiàn)了實時處理，其快速的基礎實際上只有一個積 分圖像haar求導，對于它們其他方面的不同可以參考本blog的另外一篇關于 SIFT的文章。不論科研還是應用上都希望可以和人類的視覺一樣通過程序自動 找出兩幅圖像里面相同的景物，并且建立它們之

3、間的對應，前幾年才被提出的 SIFT （尺度不變特征）算法提供了一種解決方法，通過這個算法可以使得滿足一 定條件下兩幅圖像中相同景物的某些點（后面提到的關鍵點）可以匹配起來，為 什么不是每一點都匹配呢？下面的論述將會提到。SIFT算法實現(xiàn)物體識別主要 有三大工序，1、提取關鍵點；2、對關鍵點附加詳細的信息（局部特征）也就是 所謂的描述器；3、通過兩方特征點（附帶上特征向量的關鍵點）的兩兩比較找 出相互匹配的若干對特征點，也就建立了景物間的對應關系。日常的應用中， 多數(shù)情況是給出一幅包含物體的參考圖像，然后在另外一幅同樣含有該物體的圖 像中實現(xiàn)它們的匹配。兩幅圖像中的物體一般只是旋轉(zhuǎn)和縮放的關

4、系，加上圖 像的亮度及對比度的不同，這些就是最常見的情形?；谶@些條件下要實現(xiàn)物體 之間的匹配，SIFT算法的先驅(qū)及其發(fā)明者想到只要找到多于三對物體 間的匹配 點就可以通過射影幾何的理論建立它們的一一對應。首先在形狀上物體既有旋轉(zhuǎn) 又有縮小放大的變化，如何找到這樣的對應點呢？于是他們的想法是首先找到 圖像中的一些“穩(wěn)定點”，這些點是一些十分突出的點不會因光照條件的改變而消 失，比如角點、邊緣點、暗區(qū)域的亮點以及亮區(qū)域的暗點，既然兩幅圖像中有相 同的景物，那么使用某種方法分別提取各自的穩(wěn)定點，這些點之間會有相互對應 的匹配點，正是基于這樣合理的假設，SIFT算法的基礎是穩(wěn)定點。SIFT算法找 穩(wěn)

5、定點的方法是找灰度圖的局部最值，由于數(shù)字圖像是離散的，想求導和求最值 這些操作都是使用濾波器，而濾波器是有尺寸大小的，使用同一尺寸的濾波器對 兩幅包含有不同尺寸的同一物體的圖像求局部最值將有可能出現(xiàn)一方求得最值 而另一方卻沒有的情況，但是容易知道假如物體的尺寸都一致的話它們的局部最 值將會相同。SIFT的精妙之處在于采用圖像金字塔的方法解決這一問題，我們 可以把兩幅圖像想象成是連續(xù)的，分別以它們作為底面作四棱錐，就像金字塔， 那么每一個 截面與原圖像相似，那么兩個金字塔中必然會有包含大小一致的物 體的無窮個截面，但應用只能是離散的，所以我們只能構(gòu)造有限層，層數(shù)越多當 然越好，但處理時間會相應增

6、加，層數(shù)太少不行，因為向下采樣的截面中可能 找不到尺寸大小一致的兩個物體的圖像。有了圖像金字塔就可以對每一層求出局 部最值，但是這樣的穩(wěn)定點數(shù)目將會十分可觀，所以需要使用某種方法抑制去 除一部分點，但又使得同一尺度下的穩(wěn)定點得以保存。有了穩(wěn)定點之后如何去讓 程序明白它們之間是物體的同一位置？研究者想到以該點為中心挖出一小塊區(qū) 域，然后找出區(qū)域內(nèi)的某些特征，讓這些特征附件在穩(wěn)定點上，SIFT的又一個 精妙之處在于穩(wěn)定點附加上特征向量之后就像一個根系發(fā)達的樹根一樣牢牢的 抓住它的“土地”，使之成為更穩(wěn)固的特征點，但是問題又來了，遇到旋轉(zhuǎn)的情況 怎么辦？發(fā)明者的解決方法是找一個“主方向”然后以它看齊

7、，就可以知道兩個 物體的旋轉(zhuǎn)夾角了。下面就討論一下SIFT算法的缺陷。SIFT/SURT采用henssian矩陣獲取圖像局部最值還是十分穩(wěn)定的，但是在求主方 向階段太過于依賴局部區(qū)域像素的梯度方向，有可能使得找到的主方向不準確， 后面的特征向量提取以及匹配都嚴重依賴于主方向，即使不大偏差角度也可以造 成后面特征匹配的放大誤差，從而匹配不成功；另外圖像金字塔的層取得不足 夠緊密也會使得尺度有誤差，后面的特征向量提取同樣依賴相應的尺度，發(fā)明者 在這個問題上的折中解決方法是取適量的層然后進行插值。SIFT是一種只 利用 到灰度性質(zhì)的算法，忽略了色彩信息，后面又出現(xiàn)了幾種據(jù)說比SIFT更穩(wěn)定的 描述器

8、其中一些利用到了色彩信息，讓我們拭目以待。最后要提一下，我們知道同樣的景物在不同的照片中可能出現(xiàn)不同的形狀、大小、 角度、亮度，甚至扭曲；計算機視覺的知識表明通過光學鏡頭獲取的圖像，對于 平面形狀的兩個物體它們之間可以建立射影對應，對于像人臉這種曲面物體在不 同角度距離不同相機參數(shù)下獲取的兩幅圖像，它們之間不是一個線性對應關系， 就是說我們即使獲得兩張圖像中的臉上若干匹配好的點對，還是無法從中推導出 其他點的對應。3、仿射變換幾何上，兩個向量空間之間的一個仿射變換或者仿射映射（來自拉丁語，affinis， “和相關”）由一個線性變換接上一個平移組成。在有限維的情況，每個仿射 變換可以由一個矩陣

9、A和一個向量b給出，它可以寫作A和一個附加的列b。 一個仿射變換對應于一個矩陣和一個向量的乘法，而仿射變換的復合對應于普通 的矩陣乘法，只要加入一個額外的行到矩陣的底下，這一行全部是0除了最右邊 是一個1，而列向量的底下要加上一個1。霍夫變換（Hough Transform）霍夫變換是圖像處理中從圖像中識別幾何形狀的基本方法之一，應用很廣泛，也 有很多改進算法。最基本的霍夫變換是從黑白圖像中檢測直線（線段）。我們先看 這樣一個問題:設已知一黑白圖像上畫了一條直線，要求出這條直線所在的位置。 我們知道，直線的方程可以用y=k*x+b來表示，其中k和b是參數(shù)，分別是斜 率和截距。過某一點(x0,y

10、0)的所有直線的參數(shù)都會滿足方程y0=kx0+b。即點 (x0,y0)確定了一族直線。方程y0=kx0+b在參數(shù)k-b平面上是一條直線，(你也可 以是方程b=-x0*k+y0對應的直線)。這樣，圖像x-y平面上的一個前景像素點就 對應到參數(shù)平面上的一條直線。我們舉個例子說明解決前面那個問題的原理。設 圖像上的直線是y=x,我們先取上面的三個點：A(0,0), B(1,1), C(22)。可以求出， 過A點的直線的參數(shù)要滿足方程b=0,過B點的直線的參數(shù)要滿足方程1=k+b, 過C點的直線的參數(shù)要滿足方程2=2k+b,這三個方程就對應著參數(shù)平面上的三條直線，而這三條直線會相交于一 點(k=1,b

11、=0)。 同理，原圖像上直線y=x上的其它點(如(3,3),(4,4)等)對應參數(shù) 平面上的直線也會通過點(k=1,b=0)。這個性質(zhì)就為我們解決問題提供了方法：首 先，我們初始化一塊緩沖區(qū)，對應于參數(shù)平面，將其所有數(shù)據(jù)置為0.對于圖像上 每一前景點，求出參數(shù)平面對應的直線，把這直線上的所有點的值都加1。最后， 找到參數(shù)平面上最大點的位置，這個位置就是原圖像上直線的參數(shù)。上面就是霍夫變換的基本思想。就是把圖像平面上的點對應到參數(shù)平面上的線， 最后通過統(tǒng)計特性來解決問題。假如圖像平面上有兩條直線，那么最終在參數(shù)平 面上就會看到兩個峰值點，依此類推。在實際應用中，y=k*x+b形式的直線方程 沒有

12、辦法表示x=c形式的直線(這時候，直線的斜率為無窮大)。所以實際應用中， 是采用參數(shù)方程p=x*cos(theta)+y*sin(theta)。這樣，圖像平面上的一個點就對應 到參數(shù)p-theta平面上的一條曲線上。其它的還是一樣。在看下面一個問題：我 們要從一副圖像中檢測出半徑以知的圓形來。這個問題比前一個還要直觀。我們 可以取和圖像平面一樣的參數(shù)平面，以圖像上每一個前景點為圓心，以已知的半 徑在參數(shù)平面上畫圓，并把結(jié)果進行累加。最后找出參數(shù)平面上的峰值點，這個 位置就對應了圖像上的圓心。在這個問題里，圖像平面上的每一點對應到參數(shù)平 面上的一個圓。把上面的問題改一下，假如我們不知道半徑的值，

13、而要找出圖像 上的圓來。這樣，一個辦法是把參數(shù)平面擴大稱為三維空間。就是說，參數(shù)空間 變?yōu)閤-y-R三維，對應圓的圓心和半徑。圖像平面上的每一點就對應于參數(shù)空間中每個半徑下的一個圓，這實際上是一個 圓錐。最后當然還是找參數(shù)空間中的峰值點。不過，這個方法顯然需要大量的內(nèi) 存，運行速度也會是很大問題。有什么更好的方法么？我們前面假定的圖像都是 黑白圖像(2值圖像)，實際上這些2值圖像多是彩色或灰度圖像通過邊緣提取來 的。我們前面提到過，圖像邊緣除了位置信息，還有方向信息也很重要，這里就 用上了。根據(jù)圓的性質(zhì)，圓的半徑一定在垂直于圓的切線的直線上，也就是說， 在圓上任意一點的法線上。這樣，解決上面的

14、問題，我們?nèi)圆捎?維的參數(shù)空間， 對于圖像上的每一前景點，加上它的方向信息，都可以確定出一條直線，圓的圓心就在這條直線 上。這樣一來，問題就會簡單了許多。接下來還有許多類似的問題，如檢測出橢 圓，正方形，長方形，圓弧等等。這些方法大都類似，關鍵就是需要熟悉這些幾 何形狀的數(shù)學性質(zhì)?；舴蜃儞Q的應用是很廣泛的，比如我們要做一個支票識別的 任務，假設支票上肯定有一個紅顏色的方形印章，我們可以通過霍夫變換來對這 個印章進行快速定位，在配合其它手段進行其它處理?；舴蜃儞Q由于不受圖像旋 轉(zhuǎn)的影響，所以很容易的可以用來進行定位?；舴蜃儞Q有許多改進方法，一個比 較重要的概念是廣義霍夫變換，它是針對所有曲線的，

15、用處也很大。就是針對直 線的霍夫變換也有很多改進算法，比如前面的方法我們沒有考慮圖像上的 這一直線上的點是否連續(xù)的問題，這些都要隨著應用的不同而有優(yōu)化的方法。5、消失點兩條平行的鐵軌活兩排樹木連線交與很遠很遠的某一點，這點在透視圖中叫做消 失點。凡是平行的直線都消失于無窮遠處的同一個點，消失于視平線上的點的 直線都是水平直線。6、GMSAC一種魯棒的基于高斯混合模型的基礎矩陣估計算法基礎矩陣的魯棒性估計是計算機視覺領域的一個基本問題。為了提高基礎矩陣的 估計精度，首先指出了現(xiàn)有的魯棒性算法RANSAC和MLESAC理論上的缺 陷和實際應用中的問題;然后通過詳細分析局外點復雜的成因，同時運用混合

16、高斯 分布代替均勻分布分別對不同成因的局外點進行了有針對性的建模，并提出了一 種魯棒性更強的算法GMSAC。實驗結(jié)果表明，相比于MLESAC算法,GMSAC 算法提供了更高的模型似然度和計算精度。7、AAM的思想最早可以追溯到1987年kass等人提出的snake方法，主要用于 邊界檢定與圖像分割。該方法用一條由n個控制點組成的連續(xù)閉合曲線作為 snake模型，再用一個能量函數(shù)作為匹配度的評價函數(shù)，首先將模型設定在目標 對象預估位置的周圍，再通過不斷迭代使能量函數(shù)最小化，當內(nèi)外能量達到平衡 時即得到目標對象的邊界與特征。1989年yuille等人此提出使用參數(shù)化的可變 形模板來代替snake模

17、型，可變形模板概念的提出為aam的產(chǎn)生奠定了理論基礎。 1995年cootes等人提出的asm算法是aam的直接前身，asm采用參數(shù)化的采樣 形狀來構(gòu)成對象形狀模型，并利用pca方法建立描述形狀的控制點的運動模型， 最后利用一組參數(shù)租來控制形狀控制點的位置變化從而逼近當前對象的形狀，該 方法只單純利用對象的形狀，因此準確率不高.1998年，cootes等人在asm算法 的基礎上首先提出aam，與asm的不同之處是他不僅利用了對象的形狀信息而且 利用了對象的紋理信息。8、奇異值分解是線性代數(shù)中一種重要的矩陣分解，在信號處理、統(tǒng)計學等領域有 重要應用。奇異值分解在某些方面與對稱矩陣或Hermite

18、矩陣基于特征向量的對 角化類似。然而這兩種矩陣分解盡管有其相關性，但還是有明顯的不同。對稱陣 特征向量分解的基礎是譜分析，而奇異值分解則是譜分析理論在任意矩陣上的推 廣。說明：1、奇異值分解非常有用，對于矩陣A(m*n)，存在U(m*m)，V(n*n)， S(m*n)，滿足A = U*S*V。U和V中分別是A的奇異向量，而S是A的奇異值。 AA的正交單位特征向量組成U，特征值組成SS，AA的正交單位特征向量組成 V，特征值(與AA相同)組成SS。因此，奇異值分解和特征值問題緊密聯(lián)系。 2、奇異值分解提供了一些關于A的信息，例如非零奇異值的數(shù)目3的階數(shù)) 和A的秩相同，一旦秩r確定，那么U的前r

19、列構(gòu)成了 A的列向量空間的正交 基。關于奇異值分解中當考慮的對象是實矩陣時：S對角元的平方恰為AA特征值的 說明.(對復矩陣類似可得)從上面我們知道矩陣的奇異值分解為：A=USV,其中 U,V是正交陣(所謂B為正交陣是指B=B-1,即BB=I), S為對角 陣.AA=VSUUSV=VSSV=V-1S2V上式中，一方面因為S是對角陣,SS=S2,且 S2對角元就是S的對角元的平方.另一方面注意到AA是相似與S2的，因此與 S2有相同特征值.綜上即得命題。9、最小二乘法測量工作和科學實驗中常用的一種數(shù)據(jù)處理方法，由A.-M.勒讓德和C.F.高斯于 19世紀初分別獨立提出。例如，根據(jù)實驗觀測得到的自

20、變量x和因變量y之間 的一組對應關系(x1，y1)，(x2，y2)，(xm，ym),找出一個給定類型的函數(shù) y=F(x)(如線性函數(shù)y=ax+b)或二次函數(shù)y=ax2+b)x+c等)，使它在觀測點x1， x2，xm處所取的值F(x1)，F(xiàn)(x2)，F(xiàn)(xm)與觀測值y1，y2，ym在 某種尺度下最接近。常用的一種尺度和處理方法是：確定函數(shù)F(x)中的參數(shù)(如 前述例子中的參數(shù)a和b)或a、b)和c)，使在各點處偏差的平方和達到最小。 如果?(x)是所有待定參數(shù)的線性函數(shù)(譬如F(x)是多項式或其他已知函數(shù)的線性 組合)，相應的問題稱為線性最小二乘問題。工程技術和科學實驗中有大量利用 最小二乘法建立的經(jīng)驗公式。從幾何意義上講，上述問題等價于確定一平面曲線(類型先給定)，使它和實驗 數(shù)據(jù)點“最接近”，故又稱為曲線擬合問題。它和插值法不同，并不要求曲線嚴格 通過已知點。由于實驗數(shù)據(jù)常帶有觀測誤差和其他隨機因素，所以與實驗數(shù)據(jù)保 持一致的插值法往往反倒不如最小二乘法得到的曲線更符合客觀實際。10、廣義逆矩陣是對逆矩陣的推廣若A為非奇異矩陣,則線性方程組Ax=b的解為x=AA(-1)b，其中A的A的逆矩 陣AA(-1)滿足AA(-1)A=AAA(-1)=I(I為單位矩陣)。若A是奇異陣或長方陣,Ax=b 可能無解或有很多解。若有解,則解為x=Xb+(