VFX Project 2: Image Stitching

B95902001 資工四 黃昱翔
B95902006 資工四 屠 愚

[Feature Detection]  [Feature Matching]  [Warping]  [Image Matching]  [Image Alignment and Blending]  [Refinement]  [Recognizing Panoramas]  [Artifacts]  [Downloads]  [References]


Our best artifact!




Part 0: Taking Photos

我們用的照相機是普通的數位相機,另外有使用腳架以固定拍攝角度,並確保每一組的每一張照片投影到圓柱上後,其圓心可以盡量保持在同一點。


Part 1: Feature Detection

這個部份就是要找到一張照片中有哪些點可以做為feature,並且分別算出可以描述他們的descriptor。我們實作的取feature方式為Multi-Scale Oriented Patches(MSOP),主要參考的paper為[2]。在實作上面我們幾乎是按照paper上所描述的方法去做,所以就不詳細敘述實作內容了。以下是和paper稍微不一樣的四個部分。

第一點就是我們的金字塔只有建3~5層,因為我們發現再比較高層的金字塔中,多半沒有太多有效的feature。然而在n-1、n-2層(第n層為原來大小圖片)中的feature可以提供一些有用的訊息。所以在我們的artifact主要是用3層去做。

再來是在做sub-pixel accuracy的時候,因為用二次的泰勒展開式去逼近找到的offset常常會爆表(超過0.5很多很多)。而且我們實驗的結果發現如果讓需要移動的點一直重新算新sample點的話,常會有來回跳動的情況。所以我們實作時只讓所有的feature最多被修正一次sample的位置。

在non-maximal suppression的部分,根據我們測試大多數照片的結果,我們初始的suppression半徑為8,且每個回合增加1,另外將最後剩下的feature數訂在500。因為常會有將半徑增加時,feature一下子就砍掉太多,所以我們給予一個容忍值10%,也就是說當半徑縮減到某個程度使得feature剩下小於550個我們就停止suppression。

第四,當我們在取descriptor sample window時,如果該feature的window在根據其orientation旋轉過後超出所在金字塔某層的範圍(每一層都是取40x40,所以高層的金字塔常常不會有feature剩下,也是我們只用3層的原因之一),就會將之去除,因為若不去除其window中必定會有空白處,我們認為補0很怪所以不如就捨棄它。

由左至右分別為:原圖、將金字塔每一層的feature都投影到原圖、去掉太靠近邊界的feature、作non-maximal suppression、加上oriented descriptor window。顏色愈深表示是從愈高層的金字塔取出來的。


Part 2: Feature Matching

這裡的目的是利用part 1的descriptor去找到feature之間的對應關係,以取得如何把照片兩兩接合的線索。為了要實作recognizing panorama,我們不能限定好順序input照片的順序,所以某一張照片的features也就不能只對它下一張照片的features去match,而是要對所有照片的features做matching。

最簡單的想法就是每一張照片的每一個feature都對其他每一張照片的每一張feature暴搜。但我們試過實在非常慢,所以就使用了老師推薦的k-d tree library,ANN[5]。首先對每一張照片的feature descriptors分別做出一棵k-d tree。再來就用每一張照片的每一個feature去對其他照片的用k-d tree做k-nearest neighbor searching。因為對某一個feature來說,在每一張照片裡應該只會有一個最像的,所以我們取k = 2,也就是對每一張照片只去最好和次好的matching,並且要求最好的matching的error必須比次好matching error還要小0.6倍,也就是e1-NN / e2-NN < 0.6。

現在我們有對一張照片的每個feature都有對其他每一張照片的feature matching了(如果符合上述條件的話),但我們認為所謂matching應該要是"你愛我,我也愛你"的關係,所以我們再做進一步的篩選,只留下互相都是best matching的組合。會不會太嚴格呢?以我們的結果來說,做到這裡通常每張照片都還有一百多個features有match其他照片的feature,而且幾乎都會是高品質的matching,也不會多花多少時間,所以應該是可以接受的篩選條件。

     

由左至右分別為:兩張part結果、feature matching的結果。紅色表示該feature在這另一張沒有找到best matching,綠色則是有。可以發現只有少數明顯的outlier(兩點間白線的斜率明顯不一樣者)。


Part 3: Warping

此步驟將照片都投影到一個圓柱上,使得照片之間比較能夠接合。首先,我們先使用了AutoStitch[6]這個軟體幫我們算出每張input的大概焦距。再來我們就使用inverse warping,代入投影片上的公式去得到warp成圓柱座標的input照片。此外feature也必須是在圓柱座標上,但為了避免要對彩色和灰階(取feature用)都做warping,比較費時,所以我們只對彩色的input做warping,而feature則是在part 1在平面座標上取得後,再投影到圓柱上並修改原本紀錄的座標,如此一來每張照片只要投影最多500多個點就好,投影的座標誤差也不會太嚴重。

由左至右分別為:原圖、作完warping之後的原圖、將feature也投影到圓柱上的結果


Part 4: Image Matching

這個步驟我們就可以知道哪些照片應該是要被接在一起,以及兩兩之間的相對位移應該要是多少才能接合。首先,對於每一張照片i,我們都去對其他每一張照片j去確定兩者之間feature match的個數,若是大於6個(也是我們RANSAC需要曲的sample數)則把此照片j納入照片i的可能相連照片。第二步我們將可能相連的候選照片排序,並留下最多前面6個候選照片,其他都捨棄不管。

再來就是最重要的RANSAC,我們每個回合取六個sample,並假設我們的feature有60%的正確性,另外希望最後成功率有99%,依照公式可得總共需要RANSAC回合約數為96次。此外規定如果某feature match套上sample得到的model的error平方小於9就算inlier。我們使用的motion model為簡單的translation model。然後我們就可以得到上一步的候選人分別的最好的model及inlier數。

接下來我們套用[1]中提到的判斷候選人是否為正確應該與照片i相連之照片的方法,就是檢查是否符合n_i > 5.9 + 0.22 * n_f,其中n_i為inlier feature match數,n_f為兩者feature的總match數。然後就對每一張照片紀錄與其相連的照片和相對的translation。

     

綠色是best matching且也是RANSAC算出的motion model的inlier,藍色則是outlier,紅色的定義和part 2的一樣。


Part 5: Image Alignment and Blending

最後,我們必須把計算出應該相連的照片都接合起來。我們假設每張照片都分別屬於一組panorama,然後我們使用遞回的方式把所有相連的一組照片接合,直到所有可以相連的一組組照片都被接合完了就結束。

主要的概念就是把新加入的照片轉換到已經接好的部分Panorama的座標上,並且找到minX、minY、maxX、maxY來找到一個bounding box來包住先前接好的部分panorama和現在正要加入的圖,即可得到新的panorama的長寬。然後把舊結果A和新接上的照片B貼到剛剛得到的新座標位置上,然後在接縫處使用linear blending,也就是用兩者重疊到的位置比例做為權重再相加(靠近A的部分就A的pixel權重較重,B的權重較輕,反之亦然),而不是直接加起來除以2。

在這邊比較困難的是我們因為我們為了做到Recognizing Panoramas的功能,所以必須記錄每一張照片現在在panoroma的哪個位置(左上角的座標),才能知道現在要新接上來的照片該怎麼接。若是新加入的照片會使整張照片往上或往左擴大,則需要更新所有已被接上去的照片的位置。而且因為能夠有不同的接合順序,就必須考慮可能已經有別的以接合的照片和AB接合處重疊,使得找bounding box的判斷比較複雜一些。


Part 6: Refinement

我們沒有實作出bundle adjustment,但我們有做簡單的修正drift和crop上下左右的黑邊。

在修正drift部分,我們做了簡單的修正drift的refinement,只適用於往右下方drift且接合方式沒有明顯的y方向錯動的panorama。方法就是用已知的單張image高度和part 5得到的panorama高度和寬度得到drift的斜率m,再用inverse warping的方式把每個pixel用y'=y+mx去對應即可得到不錯的結果。

另外在去黑邊部分,我們把修正drift的結果去掉左右各15% input寬度、上下各5% input高度的區域。我們的程式在最後會詢問是否要進行修正drift,輸入y或Y就可以進行修復,並輸出檔名帶有_refined的panorama到output資料夾。



上下兩張分別是有refine過和沒有refine過的結果


BONUS: Recognizing Panoramas

我們主要就是參考[1]的方法,只是把feature的部分從SIFT改成使用MSOP,並加上自己的feature matching標準。關鍵應該就是每個feature都要對所有的feature去match,而不是只對一張。如此一來image matching就能根據n_f, n_i的條件找到最可能的matching。在我們的實驗結果下幾乎都有正確的結果,但我們有做了一個簡單假設,就是input不管是不是同一組都必須是同一大小。在照片的壓縮檔裡有個bio_foest_denny的資料夾,裡面就是測試Recognizing Panorama用的一組input,結果如下圖所示。也可以更改組合並修改info.txt做其他測試,只要保持大小一樣就好。

input

output






Artifacts

Test Data:





Our Photos:






Downloads

在Windows環境下開發,使用Dev C++ IDE,並且使用gil2、ANN、OpenCV 2.0(畫output用)等library。

使用時須在執行檔的同個資料夾下開一個名叫data的資料夾,裡面必須有input、feature、warped、match、output等資料夾。

input中放相同大小之input照片,另外必須包含一個名叫info.txt的文件檔,內容是長寬、照片數N、以及N行的相對於執行檔的照片檔案路徑及該照片的焦距,可參考壓縮檔內的data資料夾下的配置。另外一份壓縮檔有數個底線開頭的資料夾分別為測資及我們照幾組的照片,可把它們分別複製出來切換成不同的input。

我們的程式會在feature裡面存descriptor_iN.txt和features_iN.jpg。前者是存第N張照片的feature的x、y、從第幾層金字塔取出來、orientation、以及64D的desriptor。後者是把feature印到照片上,就像Part 1的圖那樣。

warped裡面是存放part 3的結果,也就是投影到圓柱座標之後的的圖片,第N張照片的檔名是N.jpg,另外也會有存放投影成圓柱之後再把feature印到照片上的結果,檔名是feature_iN_cyl.jpg。

match有存三類結果。第一類是兩兩照片的feature matching結果,也就是我們part 2的結果,檔名為match_iN_iM.jpg。第二種是RANSAC之後的結果,只保留夠好的image match,也就是part 4的結果,檔名為ransac_iN_iM.jpg。再來還有一個文字檔img_match.txt,裡面是放每一張input照片分別和哪些照片match,格式是[編號]\n[N個match]\n[N行與之match的照片編號]。

最後是output資料夾,裡面會放pano.jpg(如果判定只有一組),或者是pano_N.jpg(如果有兩組以上)。單張成一組的也會被輸出。若執行refinement會有檔名帶有_refined的最後結果。


References

  1. M. Brown, D. G. Lowe, Recognising Panoramas, ICCV 2003
  2. Matthew Brown, Richard Szeliski, Simon Winder, Multi-Image Matching using Multi-Scale Oriented Patches, CVPR 2005
  3. Peter Burt, Edward Adelson, A Multiresolution Spline with Application to Image Mosaics, ACM Transactions on Graphics, Vol. 2, No. 4, 1983, pp217-236
  4. Richard Szeliski, Image Alignment and Stitching, unpublished draft, 2005
  5. ANN: A Library forApproximate Nearest Neighbor Searching
  6. AutoStitch :: a new dimension in automatic image stitching