或許很多朋友會好奇其中的神秘，比如說為什么不同角度拍攝的圖片拼接的時候可以自動對齊（略準確來講也就是如何處理圖片之間的仿射畸變和透視失 真）；如何能自動找到圖片之間可以粘連的部分并且準確無誤地拼接在一起；如何平衡圖片之間光線色調的差異等等。其實每一步的背后或多或少都有比較復雜卻又 相當精妙的技術和算法，所以這次嘗試用比較直觀的方式給大家介紹一下每一步的工作原理，逆轉對前沿科技“雖不明但覺厲”的看法。

那么先描述一下整個流程：

---圖片之間---
1. 特征點匹配：找到素材圖片中共有的圖像部分。
2. 圖片匹配：連接匹配的特征點，估算圖像間幾何方面的變換。

---全局優(yōu)化和無縫銜接---
3. 全景圖矯直：矯正拍攝圖片時相機的相對3D旋轉，主要原因是拍攝圖片時相機很可能并不在同一水平線上，并且存在不同程度的傾斜，略過這一步可能導致全景圖變成波浪形狀。
4. 圖像均衡補償：全局平衡所有圖片的光照和色調。
5. 圖像頻段融合：步驟4之后仍然會存在圖像之間銜接邊緣、暈影效果（圖像的外圍部分的亮度或飽和度比中心區(qū)域低）、視差效果（因為相機透鏡移動導致）。

----------------（一）特征點匹配----------------

合成全景圖的第一步是提取并且匹配所有素材圖片的局部特征點。

1. 什么是特征點？

普遍來講，一張圖片所包含的特征點通常就是周圍含有較大信息量的點，而僅通過這些富有特征的局部，基本就可以推測出整張圖片。比如說物體的棱角、夜景閃耀的星星，或是圖片里的圖案和花紋。

圖中框內即為判斷富有特征的部分。

實際上人在識別某個東西或是圖案的時候也是通過觀察這個物體具有哪種特征，然后與自己的經歷和記憶所匹配。舉例來說，去超市看到一個水果，假設我們觀察到這 個水果是綠色（顏色特征），球形（形狀特征），有黑色紋路（圖案特征）。于是我們可以通過經驗判斷出這是個西瓜。當然人還會通過各種其他特征來增強對物體 的判斷力，只是整個從收到信息到做出判斷的過程行云流水，甚至自己都察覺不到。這就是生物視覺的精妙之處，只可惜距離破解生物視覺系統(tǒng)目前看來似乎仍是遙不可及，所以在神經網絡破解并模擬生物大腦的運作之前就先由計算機視覺來承擔這個重擔了。

稍稍有些跑題，那么繼續(xù)之前的問題：提取何種特征？并且如何提取特征？

如前面所說，一幅圖片具有形形色色各種特征，簡單的可以是顏色、形狀或圖案，復雜的比如說可以是圖案的自相似性（是否存在類似重復性圖案）或是整個場景里其 他的物體（好比說在超市的水果架上我們可以更能確信西瓜就是西瓜，而水果架這個背景即為特征）。實際上提取這些特征在計算機視覺領域里也占有相當重要的位 置，畢竟好的特征選擇是整個識別系統(tǒng)可以成功運轉的大前提。

[理論部分]

在合成全景圖的流程里運用的是“點匹配”，也就是匹配局部圖片信息。因為局部圖片能提取的特征有限，比如說形狀特征在這種情況就不適宜，所以一般采用通過整個局部的圖案來判斷是否符合作為特征的條件。其中運用最普遍的為SIFT特征（Scale-invariant feature transform)，即尺度不變特征轉換。其應用范圍包含物體辨識、機器人地圖感知與導航、影像縫合、3D模型建立、手勢辨識、影像追蹤和動作比對。此算法由 David Lowe 在1999年所發(fā)表，在急速發(fā)展的計算機視覺領域內至今仍然被普遍認為是最好的（即State of the art）特征偵測與描述算法。

提取SIFT特征分為兩步：偵測與描述（形成特征向量）。

簡 單來講，偵測就是掃描圖片所有的尺度下的所有位置（尺度可以理解為局部縮放）。而判斷一個點作為特征點合不合格，需要計算在這個尺度下的高斯差 （DoG，Difference of Gaussians）的局部極值（Local Extrema）。如第一張圖所示，每一個尺度（Scale）下對局部影像進行不同尺度的高斯模糊（局部影像與高斯濾波器的卷積）取差值。局部極值計算方 式如第二張圖所示，將測試像素的DoG的數值與其26個鄰接像素比較取其最大最小極值，也就是測試像素的“特征度” 。

即便找到了特征點，單純匹配特征點周圍的局部影像是行不通的。首先SIFT特征本身最大的優(yōu)點就是“位置、尺度、旋轉不變量'，也就是說在一定范圍內旋轉或是拉遠拉近相機，可以檢測出相同的特征點位置（Repeatability）以及提取出相同的特征向量（Scale & Rotation Invariant）， 所以不同角度條件拍攝的圖片才可以通過SIFT特征匹配。而像素數值是不具備這些特點的。再者局部影像的像素信息量大導致匹配效率低下。假設這個局部大小 設為16*16像素大小，每一個像素值對應RGB 3個數值，那么每個特征點就對應一個786維的向量（也就是每個點要用786個數表示），考慮到尺度與旋轉不變量這個向量又需要乘上十幾倍甚至幾十倍以覆 蓋所有的變化，假設一個圖片如果包含上千個特征點，而數據庫包含上千張圖片，那么在匹配時龐大的計算量無疑是對CPU的一場災難。

為了保證提取出來的特征向量具有“旋轉不變量” 的特性，首先要做的是在每個特征點找到一個“方向”，而這個方向和局部圖像的特性應當是一致的，也就是說理想狀態(tài)下如果旋轉這個局部圖片，那么重新提取這 個'方向'也和之前相比旋轉相同角度。SIFT里選擇這個角度的方式是在高斯模糊之后的局部圖片里計算每一個像素點的'角度'與'大小'，之后進行投票選 出所有像素最多的那個角度作為主方向。下圖為計算這個角度和大小的公式，看似很長實際上只是計算橫豎相鄰像素之間的差值和(m)和角度(θ)。

于是局部圖像產生的差值和角度可以通過這種方式形成特征向量（或稱為關鍵點描述子 - Keypoint Descriptor）。

形成這個向量的方式是'量化'這些角度(比如說把360度平均分成8等分), 然后根據位置累計起來。上圖表示的是一個8x8的局部采樣計算出的2x2的特征矩陣，實際上一般使用的是16x16局部采樣形成4x4特征矩陣。所以如果 把這個矩陣拉成向量，也就是包含8*4*4 = 128個元素。

形成特征向量之后下一個問題就是如何匹配了。最基本的方式可以稱作“最鄰近搜索”（Nearest Neighbour），實際上也就是找在128維空間上直線距離最近的的特征向量，這個求直線距離的方式和2維無異，最近的特征向量也就被認為是互相匹 配。原作者使用的方式是增加了k-d tree算法來高效率地完成高維度上的最鄰近搜索。

[理論部分結束]

----------------（二）圖片匹配----------------

接 下來的目標就是找到所有匹配(也就是重疊)的圖片部分，接連所有圖片之后就可以形成一個基本的全景圖了。因為每張圖片有可能和其他每張圖片有重疊部分，所 以匹配全部圖片需要差不多匹配圖片個數的平方次。不過實際上每兩張圖片之間只需要那么幾個相對精準匹配的點就可以估算出這兩張圖像里的幾何關系。

最普遍的方式是用RANSAC（RANdom SAmple Consensus, 隨機抽樣一致），在這里的用途就是排除掉不符合大部分幾何變換的匹配。之后利用這些匹配的點來'估算單應矩陣' （Homography Estimation），也就是把其中一張通過個關聯(lián)性和另一張匹配的方法，在之后會詳細介紹。

上圖即為用RANSAC找出符合幾何約束的特征點之后，通過單應矩陣來對齊兩張圖片的內容。

【RANSAC】

[理論部分]

首先介紹一下RANSAC的 原理。RANSAC是一種迭代算法（Iteration Method）,用來從觀測數據中估算出數學模型的參數，此基礎上便可以分離內群（Inliers）與離群（Outliers）數據。簡單來說就是一般來 講觀測的數據里經常會出現很多噪音，比如說像SIFT匹配有時就會因為不同地方有類似的圖案導致匹配錯誤。而RANSAC就是通過反復取樣，也就是從整個 觀測數據中隨機抽一些數據估算模型參數之后看和所有數據誤差有多大，然后取誤差最小視為最好以及分離內群與離群數據。

下 圖這裡用一個簡單的例子來說明，在一組數據點中找到一條最適合的線。假設，此有一組集合包含了內群以及離群，其中內群為可以被擬合到線段上的點，而離群則是無法被擬合的點。如果我們用簡單的最小平方法來找此線，我們將無法 得到一條適合於內群的線，因為最小平方法會受離群影響而影響其結果。而RANSAC，可以只由內群來計算出模型，而且概率還夠高。然而，RANSAC無法保證結果一定最好，所以必須小心選擇參數,使其能有足夠的概率。

下圖是一個簡單的例子，用RANSAC來找出符合內群的直線的參數（可以看做是找y=ax+b里的a和b），以及內群數據本身。

之所以RANSAC能在有大量噪音情況仍然準確，主要原因是隨機取樣時只取一部分可以避免估算結果被離群數據影響。流程為以下：（摘自維基）

需要補充這個流程的是：判斷數據是否符合模型的閾值以及重復多少次步驟是要自行定義的，并且決定了整個流程相對的準確度與運算時間。

總結一下的話，RANSAC算法的輸入為：

1. 觀測數據 （包括內群與外群的數據）

2. 符合部分觀測數據的模型 （與內群相符的模型）

3. 最少符合模型的內群數量 

4. 判斷數據是否符合模型的閾值 （數據與模型之間的誤差容忍度）

5. 迭代運算次數 （抽取多少次隨機內群）

輸出為：

1. 最符合數據的模型參數 （如果內群數量小于輸入第三條則判斷為數據不存在此模型）2. 內群集 （符合模型的數據）

優(yōu)點：能在包含大量外群的數據中準確地找到模型參數，并且參數不受到外群影響。
缺 點：計算參數時沒有一個最大運算時間的頂限，也就是說在迭代次數被限制的情況下，得出來的參數結果有可能并不是最優(yōu)的，甚至可能不符合真實內群。所以設定 RANSAC參數的時候要根據應用考慮“準確度與效率”哪一個更重要，以此決定做多少次迭代運算。設定與模型的最大誤差閾值也是要自己調，因應用而異。還 有一點就是RANSAC只能估算一個模型。

[理論部分結束]

RANSAC應用于點匹配的效果，基于前圖：

匹配時不符合絕大多數幾何變換的判斷為匹配錯誤并排除。

【Homography Estimation】

找到兩張圖里正確的匹配之后就可以利用這些點來估算兩張圖之間的幾何變換關系。簡單來說就是：假設固定其中一張圖在桌子上，如何擺放，旋轉，拉伸另一張圖使其與第一張重合。

假設有一對匹配點, 和, 他們之間的單應矩陣便是下圖公式中的H。

本文部分內容摘自http://www./post/445059/

感謝作者Em7b5給出的總結