TWI233751B - Method of filling exposed areas in digital images - Google Patents

Description

1233751

相關申清的叉5? 本申請案從名為，•以編碼方式充填，，之臨時申請案，案號 60/257,844於2_年12月2()3 _請，獲得優先權。 有關通訊、資訊與㈣的世界科技，正逐漸而#定地數 位化。在此趨勢中’靜止的圖片以數位方式儲存和傳送， 影像也以數位化的型式傳送和儲存，數位影像和影片一起 構成現代通訊和資訊基礎要素中非常重要的一部分。處理 多=空間的訊號，如數位影片和影像，高效率的方法都具 有木入的技術意義。一般應用範圍中絕對是需要複雜微妙 的處理之實例，包括影像和影片壓縮以便有效率地儲存和 傳送影片，巧妙地操控數位影像和影片框，以便能夠產生 虛擬景象、影像或影片復原等等。 影片壓縮的本質，是由於數個相同的物體在一旋轉影片 框的一背景中移動，吾人希望創造捷徑以描述一將要編碼 或被壓縮的目前影像框，為相關於其他已經傳送至或儲存 在該位元序列中的影像框，經由先前已傳送框的其他部分 ，以指認目前框的部分之處理步驟。此處理步驟就是熟知 的移動壓縮。如圖1A所顯示，技術中如一 MPEG 1，2和4 ’將該影像框分割成正方形的塊狀物，然後將其正方塊吻 合一先前的編碼框，而且將一位移向量，也稱為移動向量 ，放置於該位元序列中以顯示有問題的正方塊，應該以先 前的編碼框中對應之方塊所取代。 這種以方塊為基礎的移動補償，缺點是受限於大部八& 、3刀尽多 _ 4 _

1233751 A7 B7 五、發明説明（2~) " —

像的物體不是以方塊組成，如此的方式導致不良的吻合與 移動補償。在橫跨兩個方塊邊界的特定方塊容易比其他方 塊產生更差的吻合情形，圖1 B即呈現這種情況，其中方 塊102是與一先前框的i〇2f吻合，但在兩個物體邊界上的 方塊104就沒辦法吻合方塊1 〇4’ 了。因此就想要能夠直接 地操控在任何給定影片框中原有的構成要素，其為該物體 或是部分的該物體，任意形狀的區段（如MPEG4中所容許 的，或揭示於”用於數位影像分割的方法和裝置”，國際出 版號為WO 00/77735，申請者為Pulsent公司，發明者為A

Prakash, Ε· Ratner，J.S· Chen ’ 以及 D.L· Cook，於 2000 年 12月21日出版），為用於移動補償的基本單元。任何形式 以方塊或物體為基礎的移動補償會出現另外的缺點，就是 當物體在一影片景致中移動時，構成新訊息的先前封閉區 域會出現在該影像框中。這些區域内的新訊息是先前所封 閉但現在卻顯現，此後稱為曝光區或曝光區域，即構成現 存影片壓縮技術中該已編碼的訊息或位元序列内非常大的 一部分。還有，應用在像是操控物體、區域移動、放置該 物體或區段於新位置以產生的虛擬景象，也就在這些曝光 區的結果。應用於影像或影片回復，其中一影像的某些部 分可能不是現成的’是遺失或損壞，這些區域都可以當作 是未知區域或曝光區。 明簡述 在此揭示一種充填一影片影像的曝光區之方法。於目前 的具體實施例中，本方法包括從鄰近區段次集合的顏色值 本紙張尺度適用中國國家標準(CNS) Α4ϋΙΐΟ X 297公嫠）------- 1233751 A7 _____ B7 五、發明説明（3—y * ——— 中’將像素的顏色值取其近似值。該多重部分方法的重點 在於辨識該鄰近區域，其為最接近相似於該曝光區的局部 顏色值。如此區段辨識的選擇和傳送至一範例解碼器，使 得該解碼器能夠有效率地重建該曝光區。接著辨識_曝光 區之後，與該曝光區連接的區段即被辨識並指定為邊界區 段。接下來進行一參考充填例行處理，包括將每一個像素 的估計值與該像素的真實值比較，而且若該估計值並不很 接近近似值，就捨去該估計值。此方法產生一個良好的曝 光區像素重建，具有真實的顏色值。下一個步驟包括決定 那一個邊界區段是用來充填該曝光區，並且指定其為充填 區段。然後，僅利用指定為充填區段的區段來執行一預估 充填的例行處理，該結果與參考充填例行處理比較，以確 定該預估充填例行處理產生一接近該參考充填的近似值， 以及遠曝光區域像素的真實顏色值。如果該參考充填和該 預估充填結果的差距大於某一臨界值，即利用一較小組的 邊界像素重新計算充填例行處理，之後就決定了最終的一 組充填區段。一具體實施例中，將該充填區段的訊息傳送 到一範例的解碼器。 圖式之簡述 圖1A至B顯示MPEG壓縮圖形。 圖2 A顯示一數位影像框的4的區段。 圖2B顯示一第二影像框，其中該區段相對於彼此移動。 圖2C顯示一第二影像框，其中該區段相對於彼此移動 而且可以見到一曝光區。 -6- 本紙張尺度適用中國國家標準(CNS) A4規格(21〇 X 297公董)-- 1233751 A7 B7 五、發明説明（4 ) 圖2D顯示充填的結果，其產生一不良的曝光區重建。 圖2E顯示充填的結果，其產生一良好的曝光區重建。 圖3顯示一參考充填例行處理的步驟。 圖4A至L顯示參考充填。 圖5顯示改變一曝光區像素其該參考充填值與該真實值 的差距之該臨界值方法。 圖6顯示決定一試驗性的充填區段之步驟。 圖7A顯示從一試驗組的充填區段中決定一組充填區段 之步驟β 圖7Β顯示一充填區段的像素，其相鄰於一曝光區的邊 界。 圖7 C顯示一參考充填例行處理的最終結果。 圖8顯示一預估的充填例行處理之步驟。 圖9 Α至I顯示預估充填的步驟，其利用一組沒有產生該 曝光區一正確重建之充填區段。 圖10A至I顯示預估充填步驟，其利用一組產生該曝光區 的一較佳重建之充填區段。 圖11顯示一重新計算的充填區段之步驟。 圖12顯示決定最終組的充填區段之步驟。 圖13A至B顯示具有多重次區域的曝光區。 特定具體實施例々私；；^ 此在本發明是屬於將曝光區内訊息取近似值之非常有效 的方法。相較於現存技術的成本，本發明的應用可以使得 多重更間的訊號’像疋數位影片和影像，傳送和儲存的成 本紙張尺度適用中國國家揉準(CNS) A4規格(210 X 297公釐） 1233751 A7 B7 五、發明説明（5 ) 本大幅地降低。本發明也改善了數位影片和影像回復的品 質以及成本。 苋介 當一物體在一連串的數位影像框内改變位置時，需要曝 光一未顯現的新區域。為了有效率地將這個未顯現的新區 域編碼，就想藉由延伸該未顯現的新區域附近之特徵，取 其顏色的近似值。本近似方法用於大量的影片數據，必須 從窄小的傳送頻道，如電話線的情況下會特別有價值。本 万法於儲存碟片的空間受限時，對儲存數位影片數據也很 有用。較佳具體實施例是把本發明當為之於一剩餘邊碼的 一前置端，因為本方法會形成一較好的影像近似。 在此揭示的本發明運用該區隔專利應用中的一影像區隔 方式，該影像區隔方法是以該影像框内物體的自然邊界為 基礎，將一數位影像分隔成區段。圖2A顯示這類的一個 影像框’其中該影像是分隔成3個區段2〇2，204，和206。 如圖2B中所顯示’當該物體相對於彼此移動時，即將一 先前封閉的區域曝光，圖2C中指定該區域為2〇8。因為該 影像框是沿著該物體的自然邊界來區隔的，其中該曝光區 208的顏色大致與該一個或一個以上的周圍區段顏色相似 ’所以利用該周圍區段，即一個，，聰明”的編碼方法，就能 利用僅接收現存影片壓縮方式所需要之一小部分的訊息， 來決定區域208的一種或多種相似顏色。圖2D顯示一不良 的近似曝光區，是如果利用周圍區段的訊息，但沒有決定 那些區段是最相似曝光區的顏色值來充填，即會產生此一 -8 - 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐) 1233751

不良的結果。圖2E顯示利用來自一次組的邊界區段訊息， 即此例中區段2〇2，丨充填而得一較好的近似|光區。由 此可乂看到本發明能夠應用在相較曝光區之周圍區段相當 小的曝光區，以面積或是其方面比值，或者當曝光區的真 實顏色值，和至少一個邊界區段之間的對比很低的時候。 簡短回顧 本發明使用一多重步騾的方法，以決定新曝光影像區的 顏色訊息，其步驟如下： 得到一第一影像框和一第二影像框。 決定在該第二影像框内未顯現的新影像區段。 決定連接於該未顯現的新影像區段之區段，並且指定其 為邊界區段。 執行一參考充填例行處理。 決定用來充填曝光區的邊界區段，並且指定其為充填區 段。 執行一預估充填例行處理，並將其結果與該參考例行處 理之結果比較。 當該啟始充填和該第二充填的差距結果比某一臨界值大 時，重新計算該充填例行處理。 決定該最終組的充填區段。 有效率地傳送該充填區段訊息至一範例的解碼器。 得到區段_ 從本說明的目的了解，一區_段為該影像的一部分，其中 的顏色是均勻一致或接近一致，此說明與如何得到該區段 -9- 本纸張尺度適用中國國家搮準(CNS) A4規格(210 X 297公釐) 1233751 A7 ______ Β7 五、發明説明（7 ) 並沒有密切的關係。 區段移動 一具體實施例中，該區段從框1移動至框2是以移動向量 來編碼，且用於重建該第二框。為本說明的目的，如何決 定該移動向量是不重要的。 決定新發現1¾诚 從該先前框與關於該區段移動的訊號來重建一第二框之 過私中’在該第二框内有的區域是缺乏影片訊息，正如圖 2C中區域208的實例顯示。 決定邊界區蔚 為本說明的目的，如何決定該周圍區段並不重要。一具 體實施例中於周圍邊界的每一個點，都要檢查最接近附近 的點’並且考慮任何包含這個點的區段為一周圍區段。另 外一具體實施例中，只要是一區段充分地接觸到該曝光區 ，該區段就包括在一邊界區段内。在第三具體實施例中， 重叠於該曝光區附近一環狀區域的區段，可以用來決定該 邊界區段。 參考充埴 接著辨識該邊界區段之後，即執行一利用所有邊界區段 的顏色值來充填該曝光區的例行處理，然後將此充填例行 處理的結果與該曝光區内像素的真實顏色值比較^用來比 較的該真實顏色值是從該真實的第二框得到的，以及該.充 填動作疋在從该先前框所要重建的第二框上進行。 具有一曝光區的一影像框，是在從該先前框重建一影像 -10-

1233751 A7 B7 五、發明説明（8 ) 框之方法的一中間步驟。此情況是發生於一影像區段已經 移動，但是並沒有關於該曝光區顏色值可用的訊息。重要 的是注意這種情況通常發生在影片壓縮，其中一範例的編 碼器已經將關於一區段移動的訊息傳送至一解碼器，但卻 沒有傳送曝光區的顏色值。與一解碼器不同的是，一範例 的編碼器將曝光區的真實顏色值準備好，因此一編竭器就 能利用從該邊界區段現成的顏色值來充填曝光區，並且以 其結果與曝光區内像素的真實值比較。對照之下，一解碼 器就能夠以幾何形狀為基礎來進行充填。此部分在下一節 中會敘述。 圖3顯示參考充填的方法。該例行處理從設定一顏色差 距的臨界值開始，也稱為顏色轉變（302)。然後該例行處 理考慮母一個取接近曝光區邊緣的像素，並且考慮其周圍 的一適當大小之核心部分（304，306)。為決定可接受之該 核心部分的大小和形狀，可以曝光區的幾何形狀或該邊界 區段的顏色值為基礎，或是兩者均列入考慮。圖4C即顯 不這類的曝光區’其中要充填曝光區410的像素499以及404 ，406，和40 8，正是圍繞著曝光區410的邊界區段。圖4D 顯示像素499周圍的一核心部分412(灰色陰影的區域）。重 要的是注意雖然該核心部分412顯示為一正方形，實際上 該核心部分可以是任何形狀。然後，該例行處理為每一個 邊界區段決定該核心部分内所有像素的顏色之一柱狀圖 (3 08)。再參考圖4D，該核心部分與兩個邊界區段404和406 重疊，因此像素499將會有兩組柱狀圖的顏色分佈。每一 -11 - 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐） 1233751 A7 B7 五、發明説明（9 ) 個區段將會有一每一顏色分量Y，U，V的顏色分佈柱狀圖 。其他的具體實施例中，可以有一組不同的柱狀圖，是該 影片影像框的其他光譜分量。然後，該例行處理決定那些 邊界區段是連接到已選定的像素，並且對應每_個連接的 區段計算該顏色值的一統計參數（310)。圖代中該邊界區 段404連接到像素499，因此該例行處理對落在該核心部分 412内區段404中的所有像素計算一統計參數。一具體實施 例中，所計算的統計參數是中間值。然而，其他的具^實 施例可以使用計量，如平均值、模組、加權平均、或其他 任何關於分佈的統計要素，但不限於此。之後，該例^于處 理計算那個像素的真實顏色值與計算的統計參數值之差距 (3 12)。如果選定的像素是連接到一個以上的邊界區段， 就決定選取最接近該選定像素之真實顏色值的區段。如果 此差值小於該臨界值，就將該像素分配為所計算的統計參 數之顏色值，而且也分配該連接區段的區段辨識指標（314 ，316)。如果該差值大於該臨界值，該像素就空著不要充 填（3 1 8)。對該曝光區邊界的每一個曝光區像素，均重複 該例行處理。一旦位於一環狀内的所有像素，不論是分配 一顏色和區段辨識、或是空著不充填，都利用上述的方法 充填該曝光區邊界的下一組像素。 圖4顯示參考充填的方法。圖4A是包括3個區段4〇4，4〇6 ，408之一影像的第一框。圖4B顯示一第二影像框，其中 該區段408已經移動並且曝光一先前的封閉區域，其中大 部分的像素共享區段404的顏色值，而有一個像素則分享 -12- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐) 1233751 A7

發明説明 像素406的顏色值。圖4C顯示圖4B的影像框，但沒有以任 何顏色值充填該曝光區410。如前所述，圖40顯示在曝光 區邊緣像素499附近中心一實例核心部分4 12的範圍。圖4E 顯示標示為1的曝光區4 1 0邊緣處第一環狀的像素。這些該 第一環狀的像素是使用前一段中敘述方法來充填，並呈現 於圖3中。圖4F顯示充填該第一環狀的結果。標示為i的像 素是以灰色為充填顏色，或以長條圖樣充填。而標示為1 且為白色的像素是空下來沒有充填，因為這些像素連接到 與其真實顏色值非常不同的一區段。此處非常不同的意思 是’其估計的顏色轉變要比某一臨界值大，因此當估計顏 色值其顏色轉變要比該可接受的臨界值大的時候，這些像 素就空著不充填。圖4G顯示該曝光區邊界之第二環狀的 像素。值得注意的是，在圖4 F所顯示環狀1中該未充填的 像素，還有標示為1和白色的，現在都是該第二環狀的一 部分。而這些屬於該第二環狀的像素即標示為2。圖4H顯 示充填該第二環狀的結果。如同之前，屬於環狀2的一些 空著沒有充填的像素，是因為該顏色轉變是要比可接受的 臨界值大。圖41顯示第三環狀的像素標示為3。圖4 J顯示 充填該第三環狀的結果。圖4K顯示第四環狀，圖4L顯示 參考充填的最終結果。值得注意的是，參考充填能夠以高 度的準確性來重建曝光區410内像素的真實顏色值，因為 本方法將每一個像素的計算值與真實值做一比較，而只有 在一臨界值内才被接受。 圖5顯示本方法改變該像素的真實值和計算值之差距的 -13- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公藿) 1233751 A7 B7 五、發明説明（12 ) 獻的充填區域要比事先決定的臨界值小，就不接受該區段 為一充填區段（614)。另一具體實施例中，一不同的統計 參數可以當作選取該試驗性充填區段的標準。 圖7呈現從上述所決定的該組試驗性充填區段中選擇一 組充填區段的步驟。本發明的一具體實施例中，該例行處 理選取與曝光區共享之每一個試驗性充填區段，計算其邊 界長度平方的正規化（normalized)比值。參考圖7B，該邊 界長度疋圍繞著曝光區之像素的長度。例如：區段604連 接到曝光區610邊界之像素704a，704b，704c，704d，704e ，704f ’ 704g，704h，704i，704j的總長度，為區段 704與 710共享的該邊界長度◊假設^個試驗性充填區段中每一個 邊界長度是以（L〖，L2，L3.......Ln)表示，其對應的比值是 以小寫1表示，該平方的正規化比值即為 (li2 ： 122 · Is2 : ······ : V)，其中 (ll2 + l22 + l32 + ······ ： In2) = 1 然後，該例行處理計算由每一個邊界區段貢獻的充填區 域面積之正規化比值。參考圖7C，以區段704充填的曝光 區710區域為灰色陰影，並以數字1，2，3，或4標示。以 區段706充填的區域為長條形陰影，並標示為數字1。假設 η個試驗性充填區段中，每一個所贡獻的面積以（S卜S2, S3......，Sn)代表，其對應的比值是以小寫’sf表示，面積的 正規化比值是 (S i · S2 · S3 · ...... · Sn)其中 (Si + s^sd......+ sn) = 1 15 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 1233751 A7 I----^___ 五、發明説明（13 ) 接著，該例行處理計算一量值或是一分數，其中該分數 為該正規化比值間差距之絕對值的總和

Score = Σ，| (Sn — ln2) | 下一步’該例行處理去除從正規化長度平方中減去正規 化面積，即On2 - Sn)得到最大數值所在的區段。去除該區 段後，將剩餘的比值重新正規化，並且重新計算該分數。 如果重新計算的分數是比先前的分數小，該例行處理再次 去除其中（ln2 - sn)最大值所在的區段，然後重新計算。重 複此步驟直到該重新計算的分數要比先前的分數大，而用 來計算最低分數的區段即被選為充填區段。 其他的具體實施例可以由每一個區段所貢獻的邊界長度 和面積為不同的函數，來決定該充填區。 Μ估的充埴： 使用該組的充填區段，接著執行一預估充填例行處理預 估充填，以一解碼器所執行充填動作之相同方式進行該充 填步驟。預估充填與參考充填之間一重要的差別，在於預 估充填中並沒有把預估的像素值與該對應像素的真實值作 一比較。運用的時候，一影像解碼器將有曝光區内充填的 最終步驟，而並沒有關於此區域内該像素真實值的訊息。 因此必須以現成可用的訊息、或是編碼器傳送的訊息為基 I 礎來執行充填該曝光區的最終步驟。所以，執行本例行 處理的目的是使一編碼器能夠估算其結果，就是利用單從 孩充填區段來的訊息充填曝光區時，一範例的解碼器所產 生的結果。該預估充填例行處理的最終目的，是要決定選 -16- 本紙張尺度適用中國國家標準(CNS) Α4規格(210X297公复） - 1233751

為充填區段的區段，是否能夠合理地取其上述像素真實顏 色值的近似值。 圖8呈現預估充填的步驟。此例行處理從取得最接近該 曝光區邊緣的每一個像素開始（802)，並考慮其附近尺寸 適合的一核心部分（8 0 4)。這樣一個核心部分9丨2的範圍於 圖9C中所示，為該曝光區邊緣像素999附近。接著，該例 行處理為每一個充填區段創造一個該核心部分内所有像素 的顏色值之柱狀圖（806)。每一個區段將有一個顏色分佈 的柱狀圖，為每一種顏色分量γ，U和V。其他的具體實施 例也可以得見影片影像框由其他光譜分量所形成的不同組 之柱狀圖。該例行處理辨識連接該像素的區段（8〇8)。如 果有一個以上的區段連接到該像素，該例行處理就決定那 一個區段貢獻較多的像素給該核心部分（8丨〇)。之後，該 例行處理為該連接的充填區段計算該顏色值的一統計參數 (812)。一具體實施例中，所計算的該統計參數是其中間 值’然而其他具體實施例也可以使用計量，像是中間值、 模組，加權中間值，或任何該分佈的其他統計的參數。然 後’以所計算的統計參數值充填該像素，並且以連接區段 的區域辨識指標分配該像素（814)。例如：圖9(：中用與核 心部分912重疊之區段904内，像素計算所得的顏色值充填 像素999。 ' 圖9A至91以及圖i〇A至ι〇Ι顯示預估充填的步驟。特別 是圖9顯示利用區段904和906為充填區段的充填結果。對 比之下，圖10顯示只從區域1004(圖9中的9〇4)的充填步驟 -17-

1233751 A7 ____ B7 五、發明説明（15 ) 。如這些實例顯示，呈現單從區段904充填要比從區段904 和906兩個充填的結果，創造一較好的曝光區之真實顏色 近似方式。此結果證實了選擇正確區段來充填一曝光區的 重要性。 圖9A顯示第一影像框，其包括3個區段904，906和908 。圖9B顯示該區段908移動之後的框2，其中即可見一曝 光區910。這裡重要的是注意此框並不是真實影像框，而 是在該區段9 0 8移動後重建影像框之方法的一個中間步驟 。接下來的步驟，該例行處理將要藉由預估曝光區内像素 的顏色值來重建該真實影像框。如前所述，圖9C顯示像 素999附近的'核心部分912。圖9D顯示要充填的曝光區内 第一環狀像素，其中曝光區邊界該第一環狀的像素是以！ 代表。圖9E顯示利用圖8所敘述之方法，以每一個在邊界 的像素來充填該第一 •環狀的結果。重要的是注意此處因為 區段904和906已經被選為充填區段，連接到區段9〇8的像 素就空著不充填。如圖9F可見，充填下一個環狀的過程中 ，這些未充填的像素會變成環狀2的部分。圖9F顯示在曝 光區910内屬於該第二環狀的像素，並以數字2標示。圖9G 顯示填充環狀2之結果。曾經標示為2的兩個未充填白色像 素將變成第三環狀的部分，如圖9H所示。圖9H顯示在曝 光區910内標示為3之該第三環狀的像素，圖91顯示預估充 填的最終結果。將此結果與如圖4Β呈現的真實影像框比 較時，可以看到從區段904和906來充填產生圖91曝光區之 真實顏色值之一不良的近似。_ 實際上，選取充填區段的步驟基於標題為”決定充填區 -18 - 本紙張尺度適用中g國家標準(CNS) Α4規格(21G χ 297公爱) ：-~： — 1233751

段”部分，以及圖6和圖7所敘述的標準，去除區段9〇6為一 充填區段。簡單地說，此區段沒有被選取是因為該區域沒 有充填該曝光區之一最小百分比的像素。本實例中決定的 條件只留下唯一區段904為充填區段。 圖10A至圖1〇1顯示只以區段1004(圖9中9〇4)來充填的步 驟。圖10A顯示4個區段1004，1006，1〇〇8以及曝光區1〇1〇 ，（與圖9A相同）。圖10B顯示該曝光區的第一環狀，其中 該第一環狀的像素以1標示。圖10C顯示只利用區段1〇〇4 為該充填區段來充填該第一環狀的結果。值得注意的是連 接區段906標示1的3個像素仍空著未充填，因為904是唯一 的充填區段，並且該例行處理只容許以連接的充填區段來 充填。圖10D和圖10E分別顯示第二環狀以及充填該第二 %狀的結果’其中屬於該第二環狀的像素標示為2。圖i〇f 和10 G分別顯示弟二環狀以及充填該第三環狀的結果。圖 10H顯示第四環狀，圖1〇1顯示以區段來充填曝光區 1010的最終結果。將此結果與圖4B中曝光區的真實顏色 值做一比較時，可以看到圖101是比圖91為一良好許多的 的重建曝光區。因此如上所述之選擇一組充填區段的方法 ，產生一優良的重建曝光區。 重新計篡： 本發明的一具體實施例中，可以重新計算該組的充填區 段。在某些情況下，所選取的該組充填區段可能不會產生 最佳的結果，而是利用較小的一組能夠有較好之曝光區真 實顏色值的近似。本方法包括將該預估充填的結果與該參 -19- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 裝 訂

k 1233751 A7 B7 五、發明説明（π 考充填的結果比較，在此情形下使用該預估充填值、該參 考充填值、該真實值的函數，為該曝光區像素的預估充填 結果與真實值的接近程度之測量。如果這個函數要比以任 何一個或許多區段來充填該像素之一臨界值大，就要去除 該一個或多個區段，並且在沒有已去除充填區段的情況下 ’重新計算該參考充填值和預估充填值。 圖11顯示一種方法，為該例行處理利用其目前的具體實 施例來決定以預估充填所完成的結果品質。接著預估充填 之後’該例行處理決定以每一個充填區段所充填區域的該 真實值與該參考充填值之差距絕對值的平均（1102，1104) ’並以數學式表示。如果一充填區域所貢獻的像素之數目 為N ’假设任何一個像素丨的真實值是a，該像素的預估充 填值是以Pi代表，而且該像素的參考充填值是以q代表， 那麼由一充填區段貢獻的每一個區域該平均值表示為 Σ\αι-η\ / — Ν 孩例行處理也要決定以每一個充填區段所充填區域的該 真實值與該參考充填值之差距絕對值的平均（1106)。此品 質可以表示為 Ν Σκ-Ρ/ΐ

I Ν 然後該例行處理從該真實值與該預估充填值之差距絕對 -20-

1233751 A7 B7 五、發明説明（18 ) 值的平均，減去該真實值與該參考充填值之差距絕對值的 平均（1 108)，對以每一個充填區段所充填的區域重複處理 步驟（11 10，1112)。如果在任何區段中此值超過一臨界值 ，該例行處理就決定要進行一重新計算（1114 , 111 8)，否 則就接受目前一組的充填區段當作最終組（1 116)。以數學 法表示，如果由一充填區段貢獻的任何區域，該量值

^ pi I Σι~r, I 是比一臨界值大，那麼要啟動一重新計算。另一具體實 施例中，該真實值、該參考充填值、該預估充填值之任何 其他函數，可以用來決定是否應該進行一重新計算。 在重新計算該充填區段之前，要從該組可能的邊界區段 中去除任何沒能滿足上述條件的一個或多個充填區段。再 利用此減少的一組邊界區段，該例行處理就進行參考充填 ，並且決定一組的充填區段，以及執行預估充填（112〇)。 此具體實施例中’如果需要可進行一重新計算，然而其 他的具體實施例中，可以進行多重的重新計算。 選擇最終的充填區段： 如圖12所呈現若進行一重新計算，那麼該例行處理就決 定是否在該第一次計算後所決定的該組之充填區段或是 在重新計算後決定的該組充填區段比較好（12〇2，12〇4)。 該例行處理首先計算曝光區中所有像素的[預估充填值 -21 ^

1233751

與該真實值間差距絕對值的平均（12〇6，i208)。重要的是 >王意上述的差別，不是為每一個充填區段所貢獻區域來計 ^ 而疋在一曝光區内所有像素來計算一整體差距。接著 該例行處理計算該曝光區，其中所有像素的重新預估充填 值與該真實值間差距絕對值的平均（丨2丨〇，12 12)。如果一 像素η’的該真實充填值是以％代表，該第一預估充填值是 以Pfn代表’以及重新計算的預估充填值是以Pm代表。然 後以數學式表示上述的兩個差值為 Μ

Έ\αη-Ρβι I η Μ 以及， Μ T}an-Pm\ η ' αΓ~ 其中在一曝光區内像素的總數是以Μ表示。 如果該第一預估充填值與該真實值間之差距絕對值的平 均’是大於該重新計算預估充填值與該真實值間之差距絕 對值的平均，該例行處理即選取重新計算過程中決定的該 組充填區段，當作最終的充填區段（丨2 14，12 16)。以數學 式表示，如果 ^ Μ

- P/h I Xl an ^ Prn I —--—> --

Μ M -22- 本紙張尺度適用中國國家樣準(CNS) A4規格(210 x 297公釐) 1233751 A7 B7

則選取該重新計算組的充填區段。 然而，如果該第一預估充填值與該真實值間之差距絕對 值的平均’是小於該重新計算預估充填值與該真實值間之 差距絕對值的平均，該例行處理即選取該第一次計算過程 中所決足的該組充填區段，當作最終的充填區段（12 1 §)。 若以數學式表示 Μ Μ

^Pjn ! Σΐ^ ^Prn I n < n

Μ M 即選取該重新計算組的充填區段。 如果該重新計算預估充填值與該真實值之間差距絕對值 的平均，是大於該第一預估充填值與該真實值之間差距絕 對值的平均時，該例行處理就選擇在第一次計算過程所決 定的該組充填區段當作最終的充填區段（丨2丨4，12丨6)。如 果該重新計算預估充填值與該真實值之間差距絕對值的平 均，疋小於該第一預估充填值與該真實值之間差距絕對值 的平均時，該例行處理就選擇在重新計算過程中決定的該 組充填區段當作最終的充填區段（丨2 1 。 充填包括多言個次分區嫿的曝光區： 當Μ曝光區非常大或者有一非常複雜的幾何形狀的時候 ，要以預估充填來精準地重建就變得比較困難。在這情況 下，比較有利的方式是將一個大的曝光區分割成較小的次 區域，正如圖13績呈現。本發明的另_個具體實施例中 ，這類的分割方法也可以應用於相當複雜的幾何形狀之曝 -23-

1233751 A7 B7 五、發明説明（21 光區’如圖13b所顯示的曝光區。圖丨3b中此分割次區域之 方法的目的，是分解該曝光區為數個具有較簡單幾何形狀 的曝光區。為本說明的目的，如何分割該曝光區為次區域 並沒有關係，有關係的是假若分割該曝光區，那要使充填 曝光區變得比較準確。 該上述充填單一曝光區的方式，可以容易地擴展到充填 包括多重個次分割區域的曝光區。此情沉下，充填動作從 最外部的次區域開始，並向較内部的次區域進行。例如： 圖13a中該最外部的次分割區為13〇2，n〇4，13〇6，13〇8 ’ 1310’ 1312，1314，和1316，（只有1318是該内部次分 割區），以及圖13b中所有的次分割區都已經是外部的次分 割區。對於被認定為該外部次區域的每一個次區域，需要 以上述相同的方式來決定一組的充填區段。完成選取最終 組的充填區段，對每一個外部次分割區選取充填區域進行 另預估充填。接著對所有的外部次分割區，相對於該真 實影像來計算預估充填的一整體誤差。一具體實施例中， 此誤差是對每一個次區域來計算該預估充填值與該真實像 素值之間差距絕對值的平均。與該預估充填相似，只有該 個或夕個次分割區，其誤差小於該事先決定臨界值，是 最後被容許可以充填的。而這些誤差小於該事先決定臨界 值的次分割區填滿之後，即辨識一組新的外部次分割區。 於先前動作中沒有充填的外部次分割區，會再一次地被辨 識為外部次分割區。然後於目前動作所容許充填之該新辨 識的外部次分割區中一組次分割^，是以上述相同的方式 -24 -

1233751 A7 B7 五、發明説明（22 ) 來決定。此處於先前動作中已經充填的次分割區也會被容 許。充填目前的外部次分割區之後，就一再重複這樣的步 驟直到該曝光區内所有的次分割區都填滿了。 傳送： 一旦該組的充填區段都以上述的方式完成，就將相關於 區域要用來當作充填區段的訊息，傳送到一範例解碼器， 以便有效率地重建該曝光區。該充填區段的訊息也可以與 一剩餘編碼器耦合，來改善該局部的影像品質。 對於將曝光區細分成多數個次區域之後，而要充填的曝 光區來說’充填所有的次分割區後，並且該組的充填區段 以及充填次區域的順序都已完成。關於充填次區域的訊息 —那一個次區域已經完成充填、充填的次序、經由那一個 充填區段所充填的，都傳送到該範例解碼器。 以上的敘述在於呈現而不是限制，所以本發明的範圍不 能參考上面的敘述決定，而是應該參考以下所附的申請專 利範圍決定，並以其相等範圍之充分考量。 -25- 本纸張尺度適用中國國家標準(CNS) A4规格(210 X 297公釐)

Claims (1)

1. 、申請專利範園 1·:種有效地將一數位影像框的一部分編碼之方法，該數 位影像框是由具有任意形狀的影像區段所組成，其中每 -個影像區段有一邊界，並且每一個影像區段是以具有 數值的像素組成，該方法包括·· 、 得到一第一影像框和一第二影像框； 決定該第二影像框内新的未顯現影像區段； /決定該第一影像框内那些區段是連接到該新的未顯現 影像區段，·並且指定其為邊界區段； 執行一參考充填例行處理； 決疋那些邊界區段是要用來充填一曝光區，並且指定 其等為充填區段； 執行一預估充填例行處理； 如果需要的話’重新計算並且決定最終组的充埴區段。 2. 如申請專利範圍第i項之方法’其中執行—參考充填例行 處理之步驟，包括下列步驟： 一在該曝光區邊界的每一個未充填像素附近，考慮一適 ^大小的區域； 對屬於每一個邊界區段之該區域内所有的像素，決定 其顏色的統計分佈。 3. 如申請專利範圍第2項之方法，進—步地包括決定每一個 像素疋連接到那一個區段。 4. :申請專利範圍第2項之方法，進一步地包括對該顏色的 、.’无:f为佈所決疋之每一個連接區段’計算該顏色值的一 統計參數。 本紙張尺歧财_家標準規格(21GX297公贊） 1233751

   5·如=凊專利冑圍第4項之方法，進一步地包括對每一個邊 界區段’計算像素的真f顏色值與計算的料參數值之 間的差值’並且辨識一最小的差值，以及提供該最小差 值的區段。 申μ專利範圍第5項之方法，進一步地包括以該區段計 算=統計參數之數值來充填該像素，該區段是連接到具 有最小差值而選取的像素，如果該最小差值是小於一第 一臨界值的-。 7.如申請專利範圍第5項之方法，進_步地包括將該區段的 辨識指標分配至該像素，該區段是連接到由最小差值所 選=的像素’而該最小差值是該像素的真實顏色值與該 计算的統計參數間之差值，而且此差值是小於一第二臨 界值的。 8·，申請專利第5項之方法，進—步地包括空著不充填 孩像素，如果該像素的|實顏色值與該#算的統計參數 間之差值是大於一第三臨界值的。 9.如申請專利範圍第2項之方法，進一步地包括增加臨界值 ，如果現有的臨界值只能容許充填某一百分比或小於該 百分比的像素。 Λ 瓜如申請專利範圍第8項之方法，其中該像素的百分比是〇。 11·如申請專利範圍第2項之方法’進一步地包括對該曝光區 邊界上每一個未充填的像素，重複申請專利範圍第2至7 項的步驟，直到填滿整個該曝光區。 12·如申請專利範圍第2項之方法，其中決定三種顏色分量γ 本紙張尺度適财®目家標準(CNS) Α4規格(210X297公董） '— -—--- 1233751 六 申請專利範圍

   ，U，V的統計分佈。 13·如申睛專利範圍第2項之方法，其中決定一多重光譜影像 中每一分量的統計分佈。 14·如申清專利範圍第4項之方法，其中該統計參數是該統計 分佈的顏色中間值。 15·如申睛專利Ιέ m第4项之方法，丨中該統計參數是該顏色 值分佈的任何統計量。 16.如申m專利範圍第1項之方法，其中決定要用|充填區段 之步騾，包括下列步驟： 计异在孩曝光區内像素的百分比，該曝光區域是以每 一個邊界區段所充填的； 計算一參數代表該曝光區的幾何形狀，該曝光區是以 每一個邊界區段所充填的。 17·如申請專利範圍第卿之方法，其中代表該幾何形狀的 參數是一周圍長度的函數、或該曝光區的一函數。 18•如申請專利範圍第16項之方法，其中代表該幾何形狀的 參數是一周圍長度與該曝光區兩者的一函數。 19.如申請專利範圍第16項之方法，進一步地包括選擇一組 試驗性的充填區段，其步驟包括·· 選擇一區段為一試驗性充填區段，如果其所貢獻的充 填區域是大於所有該邊界區段之一事先決定的貢獻量； 選擇一區段為一試驗性充填區段，如果其貢獻是小於 該事先決定的貢獻量但大於某一臨界值，以及由此區段 充填之區域的一幾何參數是在一臨界範圍内； -3- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 1233751 产..麗Wp|g L—J /；! m D8 ^_ 六 、申請專利範圍 去除一區段為一充填區段，如果不能滿足上述兩個之 一的條件。 20·如申請專利範圍第19項之方法，其中該事先決定的貢獻 量是所有區段的平均貢獻。 21·如申請專利範圍第19項之方法，其中該事先決定的貢獻 量是所有區段的任何統計參數。 22·如申請專利範圍第1 6項之方法，進一步地計算周圍長度 的一函數，·為每一個試驗性充填區段所貢獻該曝光區的 周圍長度。 23·如申請專利範圍第22項之方法，其中該周圍長度的函數 是該周圍長度平方的正規化比值。 24.如申請專利範圍第1 9項之方法，進一步地包括計算由每 一個該試驗性充填區段所貢獻之曝光區的一函數。 25_如申請專利範圍第24項之方法，其中該曝光區的函數是 該曝光區的正規化比值。 26·如申請專利範圍第2 5項之方法，進一步地包括計算該比 值之間差值的一函數。 27·如申請專利範圍第26項之方法，其中該比值之間差值的 函數是該比值之間差距絕對值的總和。 28·如申請專利範圍第1 6項之方法，進一步地包括： 於去除該區段之後重複申請專利範圍第16至26項的步 驟，該去除區段為從該正規化的長度平方減去該正規化 的面積得到最大值所在； 決定在此步驟中重新計异之該差距絕對值的總和，是 -4 - 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐)

   1233751 否小於相同參數先前計算的結果。 29·如申凊專利範圍第丨6項之方法，進一步地包括重複申請 專利知圍第1 6項之步驟，直到差距之絕對值的總和大於 該先前重新計算所得的結果。 30·如申請專利範圍第丨6項之方法，進一步地包括選擇用來 计异差距的絕對值之最小總和的區段為該充填區段。 扎如申請專利範圍第”員之方法，其中執行一預估充填例行 處理之步驟·，包括下列的步驟·· 在該曝光區邊界的每一個未充填像素附近，考慮一適 當大小的區域； 對屬於每一個邊界區段之該區域内所有的像素，決定 其顏色的統計分佈。 32. 如申請專利範圍第2〇項之方法，進一步地包括決定每一 個像素是連接到那一個區段。 33. 如申請專利範圍第2〇項之方法，進一步地包括對每一個 由顏色的統計分佈所決定之連接區段，計算該顏色值的 一統計參數。 34. 如申請專利範圍第2〇項之方法，進一步地包括將該區段 的區段辨識指標分配至該像素，該區段為貢獻最多數目 的像素給該像素附近之一適當大小的區域。 35. 如申請專利範圍第3 3項之方法，進一步地包括以該區段 的統計參數值來充填該像素，該區段貢獻最大數目的像 素至該像素附近之一適當大小的區域。 36. 如申凊專利範圍第2 〇項之方法，進一步地包括對在該曝 -5- 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公釐) 1233751 -------------------------------- 体. ψ .ΓΓ ^ ja 一 r ……........一，—"、一一 '·. v、 --*：—、1 ::、;八：貝 | A8 j 曰S 六、申請專利範圍

   光區邊界上每一個未充填的像素，重複申請專利範圍第 18至22項的步.驟，直到填滿整個該曝光區。 37_如申請專利範圍第2〇項之方法，其中決定三種顏色分量 Y，"U，V的統計分佈。 里 38.如申請專利範圍第2〇項之方法，其中決定一多重光譜影 像中每一分量的統計分佈。 39·如申請專利範圍第33項之方法，其中該統計參數是該統 計分佈之顏'色中間值。 4〇·如申請專利範圍第33項之方法，其中該統計參數是該顏 色值分佈的任何統計量。 41·如申請專利範圍第19項之方法，尚包括下列的步驟： 對每一個該充填區段所充填的區域，計算真實值與參 考充填值之一函數值； 對每一個該充填區段所充填的區域，計算真實值與預 估充填值之一函數值； 對任何一區段，決定從該真實值與該預估充填值之函 數’減去該真實值與該參考充填值之函數所得數值，是 否大於一臨界值。 42. 如申請專利範圍第41項之方法，其中該真實值與該參考 充填值之函數，是該真實值和該參考充填值之間顏色差 距絕對值的平均。 43. 如申請專利範圍第41項之方法，其中該真實值與該預估 充填值之函數’是該真實值和該預估充填值之間顏色差 距絕對值的平均。 -6 - 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公爱)

   44. -種決定要執行—重新計算之方法，若對任何—個或多 個區段’從真實值與預估充填值之函數，減去該真實值 與一參考充填值之函數所得數值，要大於—臨界值而決 定。 45. 如申請專利範圍第44項之方法，其中該真實值與該參考 充填值之函數，是該真實值和該參考充填值之間顏色差 距絕對值的平均。 46. 如申請專利.範圍第44項之方法，其中該真實值與該預估 充填值之函數，是該真實值和該預估充填值之間顏色差 距絕對值的平均。 47·-種重新計算充填區段且重新充填之方法，包括下列的 步驟： 去除一個或多個區段，對任何區段如果從真實值與預 估充填值之函數，減去真實值與參考充填值之函數所得 數值，是大於一臨界值； 排除該去除的一個或多個區段之後，重複申請專利範 圍第2至2 9項方法所敘述的步驟。 狀如中請專利範圍第47項之方法，其中該真實值與該參考 充填值之函數，是該真實值和該參考充填值之間顏色差 距絕對值的平均。 49.如申請專利範圍第47項之方法，其中該真實值與該預估 无填值之函數，是該真實值和該預估充填值之間顏色差 距絕對值的平均。 5〇·如申請專利範圍第29項之方法，其中執行重新計算多次。 I紙張尺度咖t g 0家鮮(CNS) A4規格(2iGx29p_ --

   1233751 51- —種決定最終組的充填區段之方法，如果沒有進行重新 冲异’其步银包括指定當作預估充填的組充填區段為最 終組充填區段。 ^ 52· —種決定最終組的充填區段之方法，如果進行一重新計 算，包括下列的步騾： 計算一曝光區内所有像素的第一預估充填值與真實值 之函數值； 计异該曝光區内所有像素的重新計算預估充填值與真 實值之函數值； 指定當作該第一預估充填的組充填區段為最終充填區 段’如果該重新計算預估充填值與該真實值之函數，大 於該第一預估充填值與該真實值之函數； 指定當作該重新計算預估充填的組充填區段為該最終 充填區段，如果重新計算預估充填值與該真實值之函數 ，小於第一預估充填值與真實值之函數。 53·如申請專利範圍第52項之方法，其中該第一預估充填值 與该真貫值之函數，是該第一預估充填值和該真實值之 間顏色差距絕對值的平均。 54·如申請專利範圍第52項之方法，其中該重新計算預估充 填值與該真實值之函數，是該重新計算預估充填值和該 真實值之間顏色差距絕對值的平均。 55· —種有效地將具有多重次區域的曝光區編碼之方法，包 括下列的步驟： 決定每一個外部的次區域之最終充填區段； -8 - 本紙張尺度適用中國國家標準(CNS) A4規格(210X297公釐)

   1233751 六、申請專利範圍 對每一個外部的次區域，計算一函數值以來代表預估 充填的誤差； 如果代表誤差的函數是小於一臨界值，則充填外部的 次區域； 再次決定該外部的次區域之辨識指標，外部的次區域 包括在第一次通過時未充填的次區域，以及先前在曝光 區内部的區域和先前沒有邊界區段的區域； 利用充填區段來充填該外部的次區域，充填區段可能 包含先前步驟中已經充填的次區域。 56. 如申請專利範圍第55項之方法，進一步地包括重複申請 專利範圍第44項的步騾，直到所有的次區域都充填完畢。 57. 却申請專利範圍第55項之方法，其中代表該預估充填誤 差的函數，是預估充填值與真實像素顏色值之間差距絕 對值的平均。 -9 -

   -56-