TW201237803A - Algorithm for compensating hollows generated after conversion of 2D images - Google Patents

Description

201237803 六、發明說明： 【發明所屬之技術領域】 本發明是有關於一種影像補償演算法，特別是指一種 快速補償轉換2D影像後所產生空洞的補償演算法。 【先前技術】 近年來隨著科技的進步’人們對於視訊也越來重視， 也因此造就了 3D的影像系統的蓬勃發展。然而現階段對於 3D影像系統普及化前，所面臨到的關鍵問題一部份是 系統製造成本昂貴，另一部份是如何與現有2D影像共存。 參閱圖1 ’為了解決這個問題有人便提出利用— DIBR(Depth-Image-Based Rendering)技術，將 2D 影像轉換 成3D影像，其作法主要是利用一 2D影像搭配—深度圖， 透過將2D影像中屬於該深度圖中同一深度範圍的像素朝左 方或右方位移一預定量，不同深度範圍的像素有不同的位 移I ’來轉換成不同視角的虛擬視野影像，依需求可轉換 成左視角或右視角的虛擬視野影像，上述部份一般稱為影 像變形（Image Warping)，再將原本的2D影像及轉換出的虛 擬視野影像二張組合產成一 3D影像，藉以模擬出立體影像 的效果。由於該深度圖可以由簡單的技術，例如：深度探 測器來完成，因此能有效節省3D製作成本。 然而在轉換成虛擬視野的過程中，若虛擬視野影像中 的像素點沒有原2D影像中對應的像素點可以填入，則會產 生空洞（Hole)，空洞一般均產生在前景與背景的交界處，其 中，前景為距離拍攝鏡頭較近的部分，背景則為較遠的部 201237803 分。因此空洞的補償方法，對3D影像的品質將有決定性的 影響。 習知的空洞補償技術，如Criminisi與Toyama所提出 的 Image Inpainting，發表文獻在「“Region Filling and Object Removal by Exemplar-Based Image Inpainting,55 IEEE Transactions On Image Processing, 2004 Vol. 13，No. 9」（以 第一演算法代表之），該方法對於空洞的修補是搜尋整張畫 面中最相似區塊，來對空洞做修補，因為是對整張晝面搜 尋，如此效能不是很好且容易將前景部分填補到背景部分 ，造成誤差。 另一種空洞補償技術為Depth-Aided Inpainting，發表 文獻在「“Depth-Aided Inpainting forDisocclusion Restoration of Multi-View Images Using Depth-Image-

BasedRendering”，Zhejiang Univ Sci A 2009 10(12), pp.1738- 1749·」 （以第二演 算法代表之） 所述， 空洞的修補上加入了 前景與背景的判斷，且搜尋範圍也縮小至空洞鄰近四周圍 的影像區塊以節省運算’雖然在時間的節省上有顯著的成 效，但仍然還有向上提升的空間。 【發明内容】 因此’本發明之目的，即在提供一種能夠快速補償轉 換2D影像後所產生空洞的補償演算法。 於是’本發明影像補償演算法，適用於修補一影像轉 換視野後所產生的複數空洞’該演算法包含步驟A至步驟 D等四個步驟。 4 201237803 乂驟A.偵測該虛擬視野影像中的該等空洞的位置。 修、B •在該虛擬視野影像中選定—包含有空洞的影像 上二°^用_評比方法’與分別位於該影像修補區塊 ^㈣複旦數影像搜尋區塊、下方的複數影像搜尋區塊、左 ，：：：衫像搜尋區塊，右方的複數影像搜尋區塊做比較

，將有最佳評比έ士要沾 3J ''I的一影像搜尋區塊設定為-影像候補 區塊。 步驟C:將景彡㈣㈣塊的像素值填人該料修補 的空洞。 步驟D:判斷所有的空洞是否修補完成，若 行步驟Β。 本發明之功效在於：透過只比對位在該影像修補區塊 個方向的複數|像搜尋區塊，來選擇與該影像修補區塊 =、接近的影像候補區塊，以縮小搜尋範圍與搜尋時間，節 省貝料的處理量’並且能維持良好的影像品質。 【實施方式】 有關本發明之前述及其他技術内容、特點與功效，在 以下配合參考圖式之兩個較佳實施例的詳細說 清楚的呈現。 將可

在本發明被詳細描述之前，^主意的是，在以下的說 月内谷中’類似的元件是以相同的編號來表示。 S 參閱圖2、圖3與圖4，本發明轉換2D影像後所產生 工洞之補償演算法之第—較佳實施例適用於修補由—扣影 像轉換成-虛擬視野影像所產生的複數空洞，且該等空洞 201237803 U疋由一 2D影像12搭配一深度圖13，透過一種已知的影 像變形（Image warping)技術來轉換成一虛擬視野影像μ後 ，在虛擬視野影像14中的像素點沒有原2D影像12中對應 的像素點可以填入時即會產生，其中，大部份空洞丨丨係產 生在該虛擬視野影像14的前景141與背景142的交界處等 ，且前景141與背景142的區別越明顯，也會導致生成的 空洞11的尺寸越大；值得說明的是，判斷背景142的依據 ，是透過該深度圖13之灰階值的對應關係而來，也就是說 煮景142對應至該深度圖13的灰階值，其值不大於該深度 圖13的任一灰階值，即代表為背景142。而該深度圖13是 一對應於該影像12的圖像，利用量化後的複數灰階值以代 表距離拍攝鏡頭的遠近，深度圖13顏色越亮的部分表示灰 階值越大，且離拍攝鏡頭越近，深度圖13顏色越暗的部分 表示灰階值越小’且離拍攝鏡頭越遠。 參閱圖5與圖6,該第一較佳實施例包括步驟21〜步驟 26等六個步驟： 步驟21 :檢視該虛擬視野影像，並利用公式（1)偵測出 存在於該虛擬視野内的空洞11所在位置。 ±皆|，判斷爲非空洞 .少)=仙//，判斷爲空洞 （1) 公式（1)中的變數~代表兩眼間的距離，7表示焦距， 則為深度圆13中量化後的灰階值。 其t butter(x，y)的數值若為null，則將這像素判斷為空 洞，並給予空洞的標籤。 6 201237803 步驟22··在該纽視野影像i4中選定—包含 的衫像修補區塊143及複數影像搜尋區★ Μ 〜 =補區術別位於該影像修補區塊上、下、、左、’= ，办像搜尋區塊之間有一部分像素 疊部分6X7個畫素或7χ6個。 在本貫施例中重 區塊15、15，/… 旦素，且構成的八個影像搜尋 補一影像搜尋區塊15、15,尺寸與該影像修 =^43尺寸為7Χ7像素’而該影像修補區塊143是Μ ，二：空洞為中心’其它一部份的像素可是具有影像 M mi ’而每—方向的二個影像搜尋區塊之 =部份畫素㈣，在本實施例中是6χ7個畫素或瓜個 旦。重疊。接者對該等影像搜尋區塊15、15，則—評比方 =進行比較’其比較順序順序為：先比較與該影像修補區 2⑷相鄰的四個影像搜尋區塊15，接著再比較與該影像 修補區塊143距離次近的四個影像搜尋區塊15，，並以逆時 針螺旋方向向外展出； 該評比方法是將每-影像搜尋區塊15、15，内不是前旦 141與空洞11的每-像素值，分別與該該影像候補區塊14 相對應的每-像素值計算差值，並採賴對差值合（Sum〇f abS〇lute difference )最小的影像搜尋區塊為最佳評比結果的 影像搜尋區塊；將該最佳評比結果的影像搜尋區塊設定為 一影像候補區塊。但若一影像搜尋區塊15、15，中具有部分 的前景141或部分的空洞u，則該影像搜尋區塊15不列I 該影像候補區塊。 步驟23 :判斷該影像候補區塊是否存在，若存在則執 2U1237803 行步驟24，若不存纟則執行步 步驟24 :若該候補區 驟25 塊存在 影像值填入該影像修補區塊 牧，則以該影像候補區塊的 26。 143的空洞，接著執行該步驟 步騾25 :該影像候補區 塊143的上、下、左、右 不存在，表示該影像修補區 空洞11所包圍，該影像修補1破。卩分的前景141與部分的 此時利用平均遽波器來修：=4周園無背* 142的存在’ ，接著執行該步驟26。 影像修補區塊143的空洞11 步驟26 :判斷該虛擬視 修補〜+ 野影像14所有的空洞11是否 22,但在選定一包含空 則改由上一次剛處理完的該 心’向右移動一 7個畫素後的新影 修補义成’若否，則繼續進行步驟 洞11的影像修補區塊143時， 影像修補區塊143的中 像修補區塊143。 透過上述的流程步驟，以選自The Middlebury computer vision pages (http://vision.middlebury.edu/)所提供的圖像： Interview、Orbi、Black dancer、Cg、Dog、summer Dog 等 六圖做為範圍，如圖7所示，與習知的第一演算法及第二 演算法做出計算時間及晝面品質的比較，畫面品質以 PSNR(peak signal to noise ratio)做為基準，結果如表一所示 表一 圖像 演算法 時間（sec) PSNR(dB) Interview 第一演算法 1025.17 21.02 201237803 算法

Orbi

Black dancer 第 見 多佳實施例 ，算法 巧算法 j交佳實施例 演算法

155.98 1.06 554.87 154.14 1.33 1155.87 239.15 21.23 20.87 23.36 23.36 22.72 25.89 24.17

Cg 交佳實施例

演算法 演算法 2.00 24.32 104.25 16.06 28.68 16.23

Dog 佳實施例 算法 算法 0.3 397.78 206.12 16.09 21.49 21.73

Dog summer 圭實施例 2.72 179.86 21.4 19.71 19.72 48.72 實施例 19.72 0.97 由上述表格得知，該第-較佳實施例在PSNR的表現上 ’與使用該第一、、金瞀4 & 广&〜 '、异法與該第二演算法的差別很小，然而 部能節省9〇〇/。以上沾老+ ^ 上的處理時間，故在一定的顯示品質下， 衰P嚙了運异複雜度， 確貫肖b達成本發明之目的。 值诗說明的是，/牛 的尺寸大 隹乂驟22中關於該影像修補區塊143 塊143越大時^空洞修補的時間與品質’當影像修補區 玲要計算量越多，以同樣Interview、〇咖 201237803 .、Black dancer、Cg、Dog、summer Dog 等六圖為範例’ 利用3x3像素、5x5像素、7x7像素、9x9像素、11x11像素 等尺寸的該影像修補區塊143，進行本方法空洞修補所需要 的時間，結果如表二所示： 表二： 圖像 11x11 9x9 7x7 5x5 3x3 Interview 0.79 0.83 0.4 0.31 0.25 Oribi 0.74 0.46 0.33 0.26 0.22 Black 時 1.55 1.03 0.69 0.53 0.42 dancer 間 Cg 0.32 0.24 0.22 0.21 0.19 Dog 2.90 1.60 0.82 0.41 0.24 Summer 1.14 0.69 0.41 0.27 0.22 Dog Interview 25360 19015 26555 24833 28888 Oribi 60834 48031 36067 30117 20389 Black 空 185109 182376 168563 148097 124566 dancer 洞 Cg 數 4537 3637 2545 1284 1084 Dog 517224 486559 442915 388942 303565 Summer 186279 175449 161608 138217 127055 Dog 由上述表格得知，當選該影像修補區塊143的尺寸大 小為5x5像素、7x7像素、9x9像素時，進行本方法空洞修 10 201237803 素二的時間增加較為和緩，但尺寸大小增加到Uxll像 =差=1要的時間會大幅增加，而3X3像素則因為品 補==，僅做為比較基礎，所以較適當的該影像修 鬼的尺寸大小介於5x5像素到9x9像素。 、、。在步驟22中，關於以該景》像修補區塊143為中 旦向左、右、上與下四個方向各延伸的影像搜尋區塊數 :’會直接影響計算修補的時間，當影像搜尋區塊延伸數 里越多:夺:十异所需時間越長，如果以距離該影像修補區塊 的遠近來分内外圈，每圈的影像搜尋區塊均有上、下' 左右四個影像搜尋區塊，則有不同圈數的計算結果如表 二所示： 表三

,,. ---J~~-~__ 由上述表格得知，當影像搜尋區塊的圈數在id圈時 ，計算修補的時間增加地和緩，❻4〜5圈時則所需要的時 間會大幅增加，而1圈時則因為品質較差不適合，僅做為 比較基礎，所以較適當的影像搜尋區塊的圈數在2〜3圈， 換句話說，位於該影像修補區塊143上、下、左、右方的 11 201237803 影像搜尋區塊數量各是2個或各是.3個是較佳的。 參閱圖8,該第二較佳實施例包括步驟3ι〜步驟^等7 個步驟’主要的不同在於步驟31〜步驟33 : 步驟31 :檢視該虛擬視野影像14 ’並偵測出存在於該 虛擬視野影像14 _ M u所在位置，接著將該等空洞 11個別區分為_大尺寸空洞ηι或—小尺寸㈣ιΐ2，其令 ，該小尺寸空洞112是指lxl像素或1χ2像素的空洞u， 其餘將定義為一大尺寸空洞111，如圖9所示。 步驟32 :對每一小尺寸空洞112，利用平均濾波器來做 修補，直到完成所有小尺寸空洞112的修補，大尺寸空洞 111略過不作處理。 步驟33 :本步驟除了在該虛擬視野影像14中選定一包 含大尺寸空洞111的影像修補區塊丨43及複數影像搜尋區塊 15之外’其餘與步驟22相同。 步驟34 :與步驟23相同。 步驟35 :與步驟24相同。 步驟·36 :與步驟25相同。 步驟37·與步驟26相同。 以同樣 Interview、Orbi、Black dancer、Cg、Dog、 summer Dog等六圖為範例，與該第一較佳實施例做出比較 ，晝面品質以PSNR(peak signal to noise ratio)做為基準，結 果如表四所示： 表四 圖像 演算法 時間 PSNR(dB) 12 201237803

Interview

Orbi

Black dancer 呈土j交例 第—較佳實施例 第二較佳實施例 赛佳實施例 佳實施例 ^二佳實施例 1.06 —0.4 1.33 0.32 2.00 0.69 20.87 20.86 22.72 22.69 24.32 24.3

Cg 佳實施例 0.3 16.09

Dog summer 實施例 0.97 0.42 19.72 19.71 實施例 一 -—^ ---—___19.71 由上述表格得知，若針對該等空洞u依尺寸區分為大 尺寸空洞m及小尺寸空洞112，在執行步驟33前先對 小尺寸空洞112以較為簡單的平均瀘波器進行修補能更進 -步地節省處理時間，且畫面品f鹽以乎不變，故確 能達成本發明之目的。

值付說明的是，大尺I 疋Λ尺寸空/同111及小尺寸空、洞112的修 補處理也可以依在該虛擬視野影像14中的Χ、γ軸位置: 依序處理，不必像上述步驟32巾，先對每—小尺寸*同 112做修補’直到完成所有小尺寸空洞112的修補，再：行 大尺寸空洞11的處理。 惟以上所述者’僅為本發明之較佳實施例而已，當不 能以此限定本發明實施之範圍，即大凡依本發明中請二利 13 201237803 範圍及發明説明内容所作之簡單的箄、傲^命I& j τ〜寻政變化與修飾，皆 屬本發明專利涵蓋之範圍内。 【圖式簡單說明】 圖1是一流程圖，說明習知由2D^像模擬扣效果·， 圖2是一影像圖，說明一原始的2D畫面； 圖3疋一灰階深度圖，說明該原始2D畫面的景深； 圖4是一影像圖，說明該原始2D晝面轉換成一虛擬視 野後，產生複數空洞； 圖5是一流程圖，說明本發明的第一較佳實施例； 圖6是一示意圖，說明該第一敉佳實施例向外環繞搜 尋複數搜尋區塊； 圖7是一使用圖片的說明圖； 圖8是一流程圖，說明本發明的第二較佳實施例； 圖9是一空洞尺寸的說明圖。 14 201237803 【主要元件符號說明】 11 ·...· •…空洞 142 .... •…背景 111… •…大尺寸空洞 143 ···. …影像修補區塊 112… •…小尺寸空洞 15…… •…影像搜尋區塊 12…… ••••2D影像 15,····. …·影像搜尋區塊 13…… •…深度圖 21〜26. …·步驟 14…… •…虛擬視野影像 31〜37· ----步驟 141 ··· •…前景 15

Claims (1)

1. 201237803 七、·申請專利範圍： 1. -種轉㉟2D影像後所產生空洞之補償演算法，適用於 修補由-2D影像轉換成—虛擬視野影像後所產生的複 數空洞，該演算法包含： 步驟A :偵測該虛擬視野影像中的該等空洞的位置 步驟B:在該虛擬視野影像中選定-包含有空洞的 影像修補區塊’利用-評比方法，與分別位於該影像修 補區塊上方的複數影像搜尋區塊、下方的複數影像搜尋 區塊、左方的複數影像搜尋區塊，右方的複數影像搜尋 區塊做比較’將有最佳評比結果的—影像搜尋區塊設定 為一影像候補區塊； 步驟C:將影像候補區塊的像素值填入該影像修補 區塊的空洞；及 步驟D :判斷所有的空洞是否修補完成，若否則繼 續進行步驟B » 2. 依據申請專利範圍第丨項所述之轉換2D影像後所產生空 洞之補償演算法，其中，該步驟B中的該影像修補區塊 與分別位於該影像修補區塊上、下、左、右方的影像搜 尋區塊之間有一部分像素重疊，且該等影像搜尋區塊的 大小與該影像修補區塊的大小相同。 3 ·依據申請專利範圍第2項所述之轉換2D影像後所產生空 洞之補償演算法，其中，該步驟B中位於該影像修補區 塊上、下、左、右方的影像搜尋區塊數量各是2個或各 16 201237803 是·3個’且每—方向的複數影像搜尋區塊之間有一部份 像素重疊。 4·依據申請專利範圍第3項所述之轉換2D影像後所產生空 洞之補償演算法’其中H驟B巾言平比方法比較順序 為，先比較與該影像修補區塊相鄰的四個影像搜尋區塊 接著再比較與該影像修補區塊距離次近的四個影像搜 尋區塊’之後若還有剩餘影像搜尋區塊再比較，並以順 時針螺旋方向或逆時針螺旋方向環繞比較。 5.依據申請專利範圍第2項所述之轉換2D影像後所產生 空洞之補償演算法，其中，該步驟A還包括判斷每一空 洞是否為一小尺寸空洞，該小尺寸空洞是指空洞尺寸為 1x1像素或lx2像素。 6·依據申請專利範圍第5項所述之轉換2D影像後所產生空 /同之補彳員肩算法，還包含一介於該步驟A與該步驟B之 間的步驟A1，該步驟A1是先對每一小尺寸空洞以平均 濾波斋來做修補，且修補的每一小尺寸空洞不再進行後 續步驟。 7.依據申請專利範圍第2項所述之轉換2D影像後所產生 空洞之補償演算法，該步驟B中，判斷位於該影像修補 區塊上、下、左、右方的每一影像搜尋區塊是否含有前 景或空洞，若有則該影像搜尋區塊不列入該影像候補區 塊。 8·依據申請專利範圍第7項所述之轉換2D影像後所產生 空洞之補償演算法，還包含一介於該步驟B與該步驟c 17 201237803 之間的步驟B1 ’該步驟B1是判斷該影像候補區塊是否 存在若存在則執行該步驟C，若不存在，則執行一步 驟E，該步驟E為利用平均濾波器來修填該影像修補區 塊的空洞，繼續該步驟D。 9. 依據申請專利範圍帛5項或第7項所述之轉換2D影像 後所產生空洞之補償演算法，其中，該步驟B中的評比 方法為將每一影像搜尋區塊内不是前景與空洞的每—像 素值，分別與該該影像候補區塊相對應的每一像素值計 异差值，並採用絕對差值合最小的影像搜尋區塊為最佳 評比結果的影像搜尋區塊。 10. 依據申請專利範圍第5項或第7項所述之轉換2d影像 後所產生空洞之補償演算法，其中，該步驟B中的該影 像修補區塊尺寸是介於5x5像素到9χ9像素。 18