有限域上基于拉格朗日插值多項式漸進圖像傳輸

劉易麟

（中國石油天然氣股份有限公司四川銷售分公司科研設(shè)計所，成都 610000）

0 引言

通過一個低速信道傳輸高分辨率圖片或者視頻，例如電話線，通常遇到的是長時間交互的問題。因此，對認知圖片內(nèi)容有高需求的用戶，甚至在一個早的階段就中止傳輸過程[1]。漸進圖像傳輸就是一個可以解決上述問題的技術(shù)。

通常來說，我們定義漸進式圖像傳輸是一種在接收設(shè)備上通過遠程傳輸逐漸顯示近似圖像技術(shù)。一種長時間等待高清圖片替代方式，遠程用戶可以迅速地掌握一個粗略的圖像，然后，不停地，圖片將會一點一點地清晰起來。因此，對于遠程用戶，尤其是在低速網(wǎng)絡(luò)通道上管理大量圖像，這是重要且實用的。最近幾年，有許多漸進圖像傳輸方法發(fā)表發(fā)明。這些方法中大部分使用的離散小波變換技術(shù)，將圖像分成一個較為重要的部分和許多不是很重要的部分，然后首先傳輸較為重要的部分到目標[6-9]。另外，也有許多漸進圖像傳輸方法使用的其他的技術(shù)。如：基于分水嶺的方法，Caron和Rivest也發(fā)表了用于漸進圖像傳輸?shù)姆指罹幋a方法[3]。在1997年，Chang提出了一種基于主成分分析的有效漸進圖像傳輸方法[2]。后來，Jordan提出了用于二進制的漸進圖像傳輸?shù)亩噙呅谓扑惴╗4]。在2001年，Chung和Tseng發(fā)表了另一種基于四叉樹和具有分辨率控制的陰影處理的漸進圖像傳輸方法[5]。

然而，這些方法大部分是針對黑白圖像，通常兩部分是能夠恢復(fù)原始圖片的最小信息，換句話說，用戶不能確定原始圖片最小信息的最少片段數(shù)量。本文提出一個新的基于拉格朗日插值多項式的漸進圖像傳輸方法。通過這個新的方法，我們可以通過任何的漸進形式傳輸圖像，可以通過設(shè)置任意的最小的片段得到大致的信息，還有，因為它是基于拉格朗日插值多項式的特征，所以從信息安全的各個角度來看這是一個安全的方法。另外，這個新的方法可以輕松的擴展到音頻和視頻領(lǐng)域。

1 理論基礎(chǔ)

在這個方法中，我們使用了有限域上的拉格朗日插值多項式從而把原始圖像分割成N個片段然后通過接收N個片段的部分恢復(fù)原始圖像。因此，一些關(guān)于有限域上的拉格朗日插值多項式信息需要簡要的說明。

拉格朗日插值多項式P（x）是多項式的復(fù)雜度≤（n-1）通過 n 個點（（x1，y1=f（x1）），（x2，y2=f（x2））…，（xn，yn=f（xn））），然后由得到下式：

對于n=3個點：

請注意，函數(shù)P（x）通過特定的點（xi，yi），可以看出n=3如下：

推廣到任意的n：

通過上述的公式，如果這里有n+1個點（（x1，f（x1）），（x2，f（x2））…，（xn+1，f（xn+1）））以及xi≠xj，（1≤i，j≤n+1），一個獨一無二n階的多項式可能被確定[10-11]。我們需要解釋的是所有的計算針對數(shù)字圖像，所以所有的系數(shù)和結(jié)果在上述的方程式中應(yīng)該是相同有限域的元素。

靜態(tài)的圖像Z被看作是在平面域中一個二進制連續(xù)函數(shù)：Z=f（x，y），0≤x≤m，0≤y≤n。在定律中，對于圖像Z，m和n分別意味著寬和高，（x，y）是圖像中任意的點坐標，f（x，y）是點的像素值。圖像數(shù)字化后，矩陣中行和列的位置Z=f（x，y）是相對圖像坐標中每個點的位置對應(yīng)。元素的值相當于像素的值，另外在f（x，y）中參數(shù) x和 y需要滿足條件 0≤x≤m，0≤y≤n，其中 m和n均為整數(shù)。下面的等式意味：f（x，y）=Zx，y其中Zx，y表示xth行和yth列的像素值。

所有的像素值在任何的數(shù)字圖像中都是有限整數(shù)，作為一個彩色圖像，f（x，y）∈[0，224）；作為一個原始的256階灰度圖像，像素值對應(yīng)了它的灰度值，當然灰度值也是有限的，f（x，y）∈[0，28），所以，任何關(guān)于圖像的計算需要被限定于一個有限域中。即任何關(guān)于數(shù)字圖像的計算結(jié)果必在這些圖像的像素值相同的有限域中。

有限域也稱為伽羅華域，是代數(shù)的基本話題。有限域GF（n）是一組在加法和乘法封閉的n個元素，對其中每個元素都有一個加法和乘法逆（除了對0元素沒有乘法逆）[12]。例如，有限域 GF（2）可以被表達在｛0，1｝上的加法和乘法都模2的操作（即加法是“或”，乘法是位之間的“與”操作）。類似的，如果n是一個素數(shù)，那么我們可以表示有限域GF（n）為集合{0，1，…，n-1}，在其上的加法和乘法同樣執(zhí)行模n。然而，假設(shè)n＞1不是素數(shù)，那么{0，1，…，n-1}使得加法和乘法都執(zhí)行模n不是一個有限域。例如，n為4時，有限域{0，1，2，3}關(guān)于加法和乘法模4是封閉的，然而，元素2已經(jīng)沒有逆乘法。因此，我們不能使用加法和乘法模2w來執(zhí)行w＞1的二進制字編碼。不管怎樣，由于數(shù)字信號的特點，有限域GF（2w）正是所需要的。為了構(gòu)造有限域GF（2w），我們使用參考文獻附錄A中的方法[13]。

2 提出方法

在這節(jié)，詳細介紹一種新的基于拉格朗日插值多項式的漸進圖像傳輸方法。

關(guān)于這種方法所有步驟的細節(jié)描述如下所示：

步驟1：根據(jù)需要逐步傳輸圖像的類型確定的有限域。

假設(shè)2w位可以表達圖片像素的任何值，然后我們表示有限域為GF（2w），從0到2w-1每個整數(shù)可以用GF（2w）中的一個元素唯一地表示。例如，在二進制圖像中每個像素值被定義為0或者1，因此，計算域為有限域GF（21）。由于同樣的原因，當圖像為256階灰度圖像或者彩色圖像時，計算域應(yīng)該為GF（28）及GF（224）。

步驟2：識別由原始圖像劃分出來的N個片段的數(shù)量。

我們把原始圖片劃分為N個小信息部分，N可根據(jù)應(yīng)用環(huán)境或者實際需求來確定。

步驟3：確定最小數(shù)MIN，通過對MIN最少片段計算，我們能獲得原始圖像的一些信息。

步驟4：確定最大數(shù)MAX，我們能完整地恢復(fù)原始圖像（MAX≤N）。然而，這一步不是必須的，如果我們不選擇MAX的值，這個數(shù)字等于N。

步驟5：根據(jù)下述公式獲得V的值：

步驟6：通過原始圖像有序地獲得V像素，將這些像素排列成列，并將每個像素值表示為二進制格式，得到一個二進制矩陣，我們將它標記為A。所有的處理如圖1所示。

圖1

步驟7：創(chuàng)建一個矩陣A具有相同大小的新矩陣A’，A’中每一個元素可以通過下述的公式得到：

然后，我們可以根據(jù)下述公式從矩陣A’獲得一個集合S：

步驟8：劃分集合S為（MAX-MIN+1）個子集，第i個子集有集合S中的MIN+i-1個元素，我們表示第i子集 SUBi。

步驟 9：制作 SUBi多項式系數(shù)，（MAX-MIN+1）不同多項式fi（x）可以被定義。然后，我們通過令x={1，2，…，N}計算每一個多項式獲得N值。然后把每一個Mi的值放入第i個片段。

步驟10：重復(fù)第9步直到原始圖像的所有像素都被計算。

通過以上這些步驟我們可以把原始圖像分割為N個片段。根據(jù)第1節(jié)拉格朗日插值多項式公式的描述，如果接收端接收多于最小的片段，我們可以獲得一些關(guān)于原始圖像的信息；如果接收最大片段或者更多，我們可以獲得無損的原始圖像。

3 實驗結(jié)果

在第2節(jié)已經(jīng)介紹了我們提出的可用于任何類型的圖像處理方法。這一節(jié)竟會列出2個典型灰度圖和彩色圖的例子，以說明這個新的漸進圖像傳輸方法的效果。

例1：

在圖2中圖像（a）是一個我們想通過漸進傳輸?shù)脑紙D像，并且這是一個256階灰度圖。首先，根據(jù)原始圖像的類型，我們設(shè)定有限域GF（28）來執(zhí)行計算。然后我們確定其它的參數(shù)如下：MIN=3、MAX=5和V=12。接下來，根據(jù)步驟6到10的描述，我們把原始圖像分為 5個部分。圖像（b），圖像（c）和圖像（d）分別是在接收端由3個、4個和5個部分重建的圖像。這里我們需要說明的是在圖2中圖像（d）等同于圖像（a）。

圖2 灰度圖

例2：

圖像（a）是一個原始的彩色像，如圖3所示。我們設(shè)定有限域GF（224）來執(zhí)行計算，其他參數(shù)值與例1相同。然后執(zhí)行第2節(jié)中步驟6到步驟10的操作，我們?nèi)匀话言紙D像分為5個部分。圖像（b），圖像（c）和圖像（d）分別是在接收端由3個、4個和5個部分重建的圖像，圖像（d）等同于圖像（a）。

圖3 彩色圖

4 結(jié)語

本文提出了一個新的漸進圖像傳輸方法，這個方法是基于在有限域上的拉格朗日插值多項式。新的方法可以應(yīng)用于所有的圖像類型，獲得原始圖像信息的最少部分數(shù)量可根據(jù)實際需要來確定。由于上述所有特征，本方法是一種優(yōu)秀的漸進圖像傳輸方法。另外，這種新的方法可以輕易地擴展到音頻和視頻領(lǐng)域，所以，我們認為這個方法將會有一個很好的前景。