影像拼接

影像拼接是將兩張或兩張以上、且兩兩影像之間具有相同的特征點（SIFT特征點）的影像通過特征匹配拼接在一起，手機上照相機的全景照相就是影像拼接的一個應用

特征點匹配

匹配錯誤的特征點干擾

在進行影像匹配之前都需要找出輸入的兩張圖片（或者多張）的特征點（SIFT特征點）然后再匹配上這些特征點，但是這可能會出現一個問題，如果影像的噪聲太大，就會使得特征點的匹配發生了偏差，匹配到了錯誤的點，這種不好的匹配效果，會對后面的影像拼接產生很大的影響，如下圖

消除干擾

要消除特征點的噪聲，我們可以擬合特征點，找到一個合適的擬合線，然后消除噪聲點，

下面簡單看幾種曲線的擬合

1. 直線擬合
   假設空間中有一些已知的點，要將這些點擬合出一條直線，我們不難想到最小二乘法，但是我們這里用的不是最小二乘法，我們在最開始先設定一個閾值，然后在空間中不斷找兩個隨機點，接著構造過這兩個點的直線，計算在這條線上的點的數量（inliers），如果在這條線上的點的數量達到了指定的閾值，我們就把這條直線當作是擬合的直線，
   
2. 圓擬合
   我們知道了可以不斷的隨機找兩個點去擬合直線，那如果我們要擬合圓該怎么做，兩點可以確定一條直線，那么三點就可以確定一個圓，所以我們就可以隨機找三個點，確定經過這三個點的圓，然后計算這個圓上的點的數量，達到指定閾值就可以確定要擬合的圓
3. 曲線擬合
   如果要擬合一條曲線，我們無法通過找幾個隨機的點就確定一條曲線，而是給定一個多項式（如ax^3+ bx^2+cx+d），這個多項式它是存在未知引數的（a、b、c、d），如果我們求解出了這個多項式的引數，就相當于求解出了擬合的曲線，含有4個未知引數，就需要4個可能解來求出這個多項式，有5個，就需要5個可能解來求出這個多項式，以此類推，
   

處理匹配錯誤的特征點

經過上面的曲線擬合方法的介紹后，對于匹配錯誤的特征點，我們該怎么做？
正確的做法是不斷選擇一對匹配的特征點，然后計算由這對特征點確定的數學模型的inliers，當inliers達到閾值條件，擬合出了數學模型后，便計算兩幅對應所有特征點的偏移量，求出偏移量的平均值，最后進行影像拼接，

RANSAC

1、RANSAC（RANdom SAmple Consensus，隨機抽樣一致），它是根據一組包含局外點（例外資料）的樣本資料集，計算出資料的數學模型引數，得到有效樣本資料的演算法，在這里換句話就是說，可以從一組包含例外匹配（匹配錯誤）的特征點資料集中，找到可以擬合這組資料的數學模型引數，得到正確匹配的特征點， RANSAC目的就是找到一個單應性矩陣H，使得能夠滿足這個單應性矩陣的特征點最多，

2、產生例外匹配的特征點可能是因為噪聲影響，也可能是輸入的影像不合適，影像的差異太大，

3、RANSAC回圈迭代
從RANSAC演算法的原理來看，RANSAC演算法能否找到一個合適的數學模型，其中包含運氣成分，因此RANSAC回圈需要設定一個迭代次數，使得在這個迭代次數內能夠找到一個最合適的數學模型來擬合這些特征點，顯然迭代越多得到的數學模型就越合適，但是相應的也會付出運行時間的代價，迭代少得到數學模型顯然就越不理想，因此迭代次數需要根據給定資料集的局外點和局內點數量來確定，設局內點的占比為t，則t可以由以下公式得到

通常情況我們無法事先知道 t 的值，但是個可以給定一些魯棒值，假定每次使用N個點擬合數學模型，選取的N個點中，至少有一個局外點的概率m就是 m = 1-t^N , 那么得到正確的數學模型的概率P就是：

故通過P得到的迭代次數k的公式為：

3、RANSAC演算法的步驟

1. 選擇4對匹配特征點（選擇4對特征點因為單應性矩陣有8個自由度，需要4個特征點，每個特征點都能構造2個方程，然后求解單應性矩陣，但是任意3個點或4個點不能在同一條直線上）
2. 根據直接線性變換解法DLT計算單應性矩陣H
3. 對所匹配點，計算映射誤差
4. 根據誤差閾值，確定inliers數量
5. 針對最大的inliers集合，重新計算單應性矩陣H

4、使用RANSAC圖片匹配

from numpy import *
from matplotlib.pyplot import *
from PIL import Image
import warp
import homography
from PCV.localdescriptors import sift

featname = ['img/' + str(i + 1) + '.sift' for i in range(5)]
imname = ['img/' + str(i + 1) + '.jpg' for i in range(5)]
l = {}
d = {}
for i in range(5):
    sift.process_image(imname[i], featname[i])
    l[i], d[i] = sift.read_features_from_file(featname[i])

matches = {}
for i in range(4):
    matches[i] = sift.match(d[i + 1], d[i])

# visualize the matches (Figure 3-11 in the book)
for i in range(4):
    im1 = array(Image.open(imname[i]))
    im2 = array(Image.open(imname[i + 1]))
    figure()
    sift.plot_matches(im2, im1, l[i + 1], l[i], matches[i], show_below=True)

# 將匹配轉換成齊次坐標點的函式
def convert_points(j):
    ndx = matches[j].nonzero()[0]
    fp = homography.make_homog(l[j + 1][ndx, :2].T)
    ndx2 = [int(matches[j][i]) for i in ndx]
    tp = homography.make_homog(l[j][ndx2, :2].T)

    # switch x and y - TODO this should move elsewhere
    fp = vstack([fp[1], fp[0], fp[2]])
    tp = vstack([tp[1], tp[0], tp[2]])
    return fp, tp


# 估計單應性矩陣
model = homography.RanSacModel()

fp, tp = convert_points(1)
H_12 = homography.H_from_ransac(fp, tp, model)[0]  # im 1 to 2
fp, tp = convert_points(0)
H_01 = homography.H_from_ransac(fp, tp, model)[0]  # im 0 to 1
tp, fp = convert_points(2)  # NB: reverse order
H_32 = homography.H_from_ransac(fp, tp, model)[0]  # im 3 to 2
tp, fp = convert_points(3)  # NB: reverse order
H_43 = homography.H_from_ransac(fp, tp, model)[0]  # im 4 to 3

# 扭曲影像
delta = 100  # 用于填充和平移 for padding and translation

im1 = array(Image.open(imname[1]), "uint8")
im2 = array(Image.open(imname[2]), "uint8")
im_12 = warp.panorama(H_12, im1, im2, delta, delta)
im1 = array(Image.open(imname[0]), "f")
im_02 = warp.panorama(dot(H_12, H_01), im1, im_12, delta, delta)
im1 = array(Image.open(imname[3]), "f")
im_32 = warp.panorama(H_32, im1, im_02, delta, delta)
im1 = array(Image.open(imname[4]), "f")
im_42 = warp.panorama(dot(H_32, H_43), im1, im_32, delta, 2 * delta)

figure()
imshow(array(im_42, "uint8"))
axis('off')
show()

原始圖片

運行結果

從上面的結果中看出來使用RANSAC影像拼接的效果比較理想，這是因為輸入的圖片上的景物都在同一深度上，且圖片的噪聲點比較小，但是如果對于紋理比較復雜、噪聲點比較多、物體深度不一的情況，拼接的效果就會不好，例如下面的拼接結果

從上面的結果可以看到在圖片拼接的介面處出現了斷層，并且對于地板上有紋路的這些地方它的拼接效果并不是十分的理想，最主要的問題是因為在拍攝影像的時候，讓影像中的有些物體沒有處于同一深度，導致在影像拼接的時候出現了斷層，這里猜測不是出現重影是因為，影像在拼接的時候是重疊在另一張影像上的，所以后一張影像會覆寫前一張影像，當拍攝影像較差時，就導致了這種斷層，能夠明顯的看到影像的疊加，圖中還可以看出右邊變換出現了變形，這是因為影像在拼接的時候，有進行仿射扭曲，目的是為了縮放影像中的物體，使得能夠更好的拼接在一起，

另外，在上面拼接的影像中還可以觀察出，影像的曝光程度不一樣，這也使得每一張影像拼接后，能夠清楚的看到影像是疊加在一起的，這個效果并不是我們想看到的，這個可以通過構造高斯金字塔和拉普拉斯金子塔，然后Blending進行解決

在影像拼接的時候，碰到了一個ransac.py的錯誤，如下，上網查了一下說是拍攝的影像水平落差比較大，需要重新再拍攝一組影像

ValueError: did not meet fit acceptance criteria

區域單應性變換

“鬼影”

1、通過上面RANSAC方法可以消除例外匹配的特征點的問題，但是匹配后得到的影像會出現“鬼影”問題，所謂鬼影問題就是影像疊加后出現重影，

2、產生“鬼影”的原因在于影像映射是全域的單應性變換，然后影像場景中各個物體往往具有不同的深度，如果采用處于不同深度物體的特征點進行全域單應性變換，由于此時影像中的物體無法滿足近似于同一平面的條件，計算得到的單應性矩陣會有較大的誤差，僅僅由一個全域的單應性變換無法完全描述兩幅影像之間的變換關系，

APAP

1、為了解決“鬼影”問題，便有人想到將影像分成很多個規則的小網格，每個小網格分別計算各自的單應性矩陣，也就是區域單應性變換，APAP演算法就是區域單應性變換的一個具體實作，

2、APAP在計算每個網格的單應性矩陣的時候，影像中各個特征點對網格區域單應性變換計算的的重要程度差異是通過引入權重矩陣W實作的

3、其中W_i是第 i 個網格權重的對角矩陣，W_i,k是第 i 個網格的中心像素坐標和第k個特征點之間的空間距離定義，λ是一個大于0的常數

尋找拼接影像切割線

為什么找切割線

我們解決了拼接后影像景物的“鬼影”問題后，還并沒有達到很完美的拼接影像，因為對于一些比較復雜的背景（如建筑等），它們在拼接的時候，也可能會出現重影，那產生重影的問題是什么？因為影像的重疊導致了重影，那么解決的方式就是不讓圖片重疊，具體的方式就是在影像重疊的區域中找到一條切割線，使得在切割線的左邊用圖片A，在切割線的右邊用圖片B，則就解決了影像拼接后因為重疊而導致的重影問題，

找切割線的準則

顯然這條切割線不能夠亂找，如果在兩張影像差異很大的地方切割開了重疊部分，那么得到的效果顯然很好，要找到一條好的切割線，就要在線的左右兩邊影像的像素差異比較小，這樣切割出來的效果，就沒有強烈的違和感，像下面這張圖片，找出的切割線左右兩邊的像素差異比較小，所以得到的拼接影像效果比較好，

最大流最小割

找到這么一條切割線運用的是一個最大流的方法，下面的這個圖結構，可以把它理解為影像的重疊部分，具體步驟就是：不斷的找從S到E的一條路徑，每找到一條路徑，就讓該路徑上的所有邊的權重減去這條路徑上權重值最小邊的權重，同時在這條路徑上構造一個方向的有向邊，權重值設定為減去的值，另外如果減完后權重為0，則洗掉這條邊，演算法一直回圈知道無法找到S到E的路徑借結束，最后切割那些為慷訓是流已滿的邊