數據嵌入的製作方法
2023-09-22 16:04:00
專利名稱：數據嵌入的製作方法
技術領域：
本發明涉及數值數據的處理，尤其涉及把外部數據嵌入到已有的數據欄位中。此項發明得到了政府的支持，根據美國能源部No.W-7405-ENG-36號合同執行。政府享有一定的發明權。
與本發明相關的背景技術使用數字形式的數據在全世界成為一項具有變革意義的通信形式。它們大多通過電話線、微波、和光纖進行通信。如今，數據可以在大地上，水上及衛星之間進行準確地傳送。運行在軌道上的衛星可以使地球上或是太空中的任何兩個點之間進行通信。
在許多情況下，把特殊的輔助數據與原始數據一齊傳送出去會大大收益。輔助數據包括電視節目中的解說詞，與照片有關的識別信息，或是與傳真傳輸一起發送的轉換信息。這種技術也適用於數字標記圖，用以核實原始數據的原點及真實性。
以數字形式進行傳輸的數據採用寬帶通信信道。藉助於提供絕對數據保真度的糾錯軟體和硬體協議，可使數據形式的通信變得極為便利。這些通信系統可以確保由一個站傳輸的數字位流在沒有變動的情況下被另一個站接收。
然而，大多數數字數據包含有冗餘信息及固有噪聲。例如照片掃描後生成的數字圖象、電子藝術原著、或一個數位化後的視頻信號，在這種圖象掃描或數字生成過程中，在數字重現中就產生了噪聲。此外，圖象源——如攝影圖象和身份證就包含著噪聲，這是由於膠片的顆粒結構，光像差、及物體運動所致。藝術作品中也有噪聲，這是由於畫筆移動，顏料質量、及藝術品許可證所致。
冗餘對於數字圖象數據是固有的，因為數字密度的任何特定數值存在於圖象中的許多不同位置。例如，一個已知的灰度可以出現在有樹木，天空人及其它物體的圖象中。在任何數字圖象中，相同的或相似的數字象素(或圖素)值可以代表大量的圖象內容。這就意味著具有相似數字值和在圖象中不同部位的出現頻率的象素可以自由地交換位置，而對圖象外表，或者對象素值出現的統計頻率而言都沒有改變。
只要當相同的值在代表信息的數字值流中出現不只一次，冗餘就出現在大多數類型的數字信息中。
對於一幅雙色的黑白傳真圖象，噪聲包括了黑或白象素值。掃描成黑白BITMAP格式的文件包括一連串的黑(1)和白(0)值。在這些圖象中的噪聲帶來了象素運行長度的變化。具有相同值的運行出現在黑白圖象中的不同位置和不同行中。這就使此發明可運用於傳真傳輸。
在數字數據中存在的噪聲及冗餘象素信息需要在它的噪聲部分嵌入額外的信息。由於當前數字通信系統的保真度，嵌入的信息在傳輸到接受器中是受到保護的，接受器可以抽取這些信息。以這種方式嵌入的信息不會增加傳輸過程中所需的帶寬，因為嵌入的數據位於宿主數據的噪聲分量中。所以，可以在原始數據的冗餘噪聲分量中傳送有意義的新信息，而不被未授權人發現。
本發明的目的因此，本發明的目的是提供一種向一個數字信息流中嵌入數據，以便使數字信息不會有較大改變的設備和方法。
此發明的另一個目的是提供一種為阻止未經授權而使用嵌入正常數字數據中的信息的設備和方法。
本發明的其它目的，優點及新穎特點將在其後的說明中闡明，其他內容對於熟悉這項技術的人來說，通過檢驗或使用本發明即可明白。本發明的目的及優點可藉助於所附的權利要求中特別提到的手段及工具實現和獲得。本發明的技術方案本發明提供將輔助數據嵌入宿主數據的方法，它包括幾個步驟建立含有數值及噪聲成分的元素的宿主數據的數字表示；以一系列位的形式創建輔助數據的數字表示；評價宿主數據的數字表示中的噪聲分量；比較噪聲分量與宿主數據中的元素以確定主元素對，此主元素包含小於該噪聲分量的數值；用從該元素對中取出的大體相等的值代替元素中的單個值，以便嵌入輔助數據的單一位值，此值相當於輔助數據的位系列；以及以一個文件的形式將嵌入到宿主數據中的輔助數據輸出。
根據本發明，還可進一步提供從宿主數據中抽取已嵌入的輔助數據的方法，此宿主數據包含噪聲分量，其抽取步驟為從宿主數據中抽取指示已嵌入的輔助數據的一位系列，由此可核實宿主數據，解釋宿主數據元素對，此宿主元素對小於噪聲成分值，並相當於輔助數據的位值；標識相當於對值的輔助數據位系列；以及，以一個數據文件形式將輔助數據輸出。
附圖的簡要說明作為說明書的一部分，所有
了此發明的具體實施方法，它與說明書一道共同解釋發明的原理。
圖1是框圖，說明從宿主中抽取及嵌入數據的過程；圖2是部分計算機代碼，它們用於確定有相似值的宿主數據的對數，並用於將RGB分量變成HSI分量；圖3是用於消除雙重宿主數據對的部分計算機代碼；圖4是部分計算機代碼，對於Truecolor(真彩色)圖象，它可以在宿主數據對出現頻率上引入制約，這樣可在宿主數據直方圖上將嵌入的作用減少到最低程度；圖5是用於完成將輔助數據嵌入到宿主數據的實際工作的部分計算機代碼，該代碼表包括大量的信息，這些信息對於處理首標信息中的輔助位流和宿主數據文件數據是必需的；圖6是用於分析雙色傳真宿主數據中的一排象素的運行長度的部分計算機代碼；圖7是用於確保在起始數據行中的第一個象素能在偶列數裡開始的部分計算機代碼，在該行的第一個象素位置標誌數據包的起始。
圖8是用於把數據嵌入到雙色主圖象(如傳真傳輸)的部分計算機代碼。
本發明的最佳實施例本發明可以在對傳輸或圖象的內容及含義不做任何可察覺的修改的情況下把數據嵌入到數字傳輸或圖象中去。由於採用了本發明的技術，這一切是可以實現的。根據本發明，在一組數字宿主數據中的相似圖象值可按照已嵌入的信息重新排列。宿主數據圖象實例是用微軟的BITMAP格式(.BMP)表示的，因此所得出的圖象包含了嵌入的輔助信息，同時這些信息不會被察覺。
微軟BITMAP格式是一種公共範圍的格式，它可支持Truecolor圖象，調色板，灰度級、或黑白表示。Truecolor圖象的每個象素元素有24位，每個象素元素的每個字節代表紅、綠、和藍(RGB)色分量的強度。調色板圖象包含一張RGB許可值表。在調色板圖象裡的象素值是這個表的索引。灰度級圖象給出了象素值的數字密度。黑白表示分配0或1作為兩個可能的象素值之一。本發明將在BITMAP圖象類型的範圍內進行解釋，請參考以下描述以理解本發明。
大多數傳感器接受的信息是以數字形式表示的，無論它來自視頻，照片，實驗室測量、或是傳真。這些數字數據帶有固有的噪聲和冗餘信息，它們可被操縱以攜帶額外的數據信息。使用本發明和技術，這些額外的信息也可以由授權的及可能的接受者容易地取出。
當數字密度的一個特殊數值出現在圖象的許多不同位置對就出現數字圖象數據中的冗餘。冗餘常在圖象中發現，因為給定的灰度級存在於樹木，天空，白雲，人，及其它物體的再現中。數字圖象中噪音的出現使圖素、象素在數值上有輕微的變化。對於8位數字數據，象素數值的範圍在0～255之間，由於具有相同或相似數值的象素代表著多種多樣的圖象內容，圖象中不同位置的許多值可以自由地相互改變。通過交換數值附近的象素的空間位置，就可使一個特殊象素值的統計出現頻率及圖象外表幾乎不受到影響。
首先，從原數字數據(其後稱為「宿主」數據)中，本發明在必要的情況下把宿主數據轉換成數據形式，然後生成圖象直方圖，用於說明出現在圖象中的數字圖素值的可能密度。一個特殊的象素值在圖象中出現的次數將針對其值被繪製出來。對於8位數字數據，象素值的範圍在0～255之間。當然，圖象中的噪聲級將取決於數據源。照片、原始藝術品、數字音頻、視頻、和傳真之間的噪聲級會不同。
將輔助數據實際嵌入到宿主數據中的過程涉及到三部分處理。其基本步驟如圖1所示。首先，確定宿主數據中噪聲成分的估算值，然後與宿主數據數值的直方圖分析結合在一起以標識宿主數據中的值對，宿主數據與大約相同的統計頻率出現，其值低於噪聲成分的值。其次，調整所發現的對值出現的位置以嵌入輔助信息組的位流。第三，用宿主數據中已標識的值對來生成附標，去抽取嵌入的數據。
抽取嵌入的數據的過程與上面相反，放置在圖象中的附標在嵌入階段時規定對值，它包含已嵌入的輔助信息。由於對值已知，根據附標中已給對值的象素位置重新創建輔助數據。附標數據(關鍵碼)首先用來抽取首標信息。它規定了輔助數據的長度和文件名，並使附標合法化。如果包含嵌入信息的圖象被修改過，首標信息就不會正確引出數據。然而，成功的抽取是在一個輸出文件中重新準確地創建輔助數據。
按照本發明的數據嵌入原理涉及到某種宿主數據值的重新排列，其目的是把即將加入的額外數據值進行編碼。為了便於說明本發明，假設一個宿主數據由8位二進位信息表示，對於每個宿主數據實例來說，其值的變化範圍在0和255之間。再進一步假設一個信號S的噪聲值為N，則N＝±S/N，或大約信號值的10％。對於大多數數據而言，噪聲分量可由一個不變值或百分比近似，比如上面提到的10％。宿主數據中的兩個值di和dj在噪聲值範圍內，如果｜di-dj｜＝ε≤N(10)某一值的di的出現頻率或直方圖值是F(di)。滿足方程式10的要求及以f(di)-f(dj)＜δ(這裡，δ是用於統計等式的容差)的出現頻率出現的宿主數據中的數據值即為嵌入之用的。di和dj構成一對數據值Pk.k＝0，1，2，....Np。在宿主數據裡的這些對給出每一對的嵌入位Mk的全部數量Mk=if(di)+jf(dj)]]>這裡，i和j之和運行到出現在用於表示各個數據值的數據組f(di)和f(dj)中的頻率極限處。
參見圖2，其中列出了部分列印的C語言計算機編碼。方程式10中的宿主數據象素對值(di和dj)的確定是通過圖2的編碼完成的。在圖2中，8位值譯成調色板表的索引，因此，方程式10中的比較就需要在調色板上相關顏色之間進行。調色板上的入口是紅、綠、藍顏色值，每個都在0～255範圍內。
如果以BITMAP圖象格式增加額外信息的話，需要參照以下兩份資料，一是由Levine(1994，J.wiley sons，New York)編寫的書，名為「圖形文件的編程」。另一個為技術文章，題為「BMP格式」，由M.Luse撰寫，刊登在1994年第19期P.18 Dr.Dobb′s Journal。
圖2中的分段碼從第1行開始圍繞調色板上的顏色循環。循環索引i用來把每一種調色板上的顏色用所有其它入口連續進行測試，以標識色彩入口的對數以滿足方程10規定的要求。在i循環中標識的顏色都要用另一個索引j通過第二個循環從第16行開始對調色板中的所有其它顏色進行測試。第7行提供了具有灰度級調色板而不是彩色圖象的修改方法。對於灰度級圖象，RGB分量對於每個調色板入口都是相同的，儘管有些灰級格式包含16色表。
通過將RGB彩色分量轉換成相應的Hue，Satruation和Intensity(HSI)彩色分量可完成方程式10指出的比較。第12行採用單獨的子程序rgbhsi來執行這一轉換，第20行把j循環中的RGB彩色分量轉換成HSI數據結構分量，第21行計算HSI系統中的色差，第24行完成方程10所要求的測試。如果色差小於規定的噪聲值(圖2清單中COLOR NOISE＝10)，就要做密度差試驗以確定這兩個調色板入口在小於規定的噪聲值時可否被接受。在作為備選對值接受入口前要先提出兩個額外的限制條件。首先，在測試(i-循環)值和所有其它(j-循環)值之間的最小色差應為色差。其二，所選的對數必須小於圖象象素行中列數的一半，以便對值鍵可以存在一行象素中。這是一條算法限制，而並非本發明所要求。
數據結構排列(Pair[])用來保持備選對(i，j)值和它們的全部出現頻率Mk的值。如果圖象是灰度調色板，第3行的測試就只用來對兩個調色板入口的密度進行比較。灰度圖象不需要對彩色調色板進行RGB到HSI的轉換。
本發明的嵌入過程忽略了彩色調色板入口的飽和度分量中的差別，因為飽和度在彩色圖象中一般不被注意。只有Hue和Intensity分量被限制落入確定的噪聲限度之內以確定調色板對值。
由圖2列出的編碼示出的象素對值一般包含冗餘值。同一個象素值i可以在幾個不同的對組合中發現。因為多個對不能包含相同的調色板入口(由於象素值的每對組合必須是獨一無二的)，所以有必要刪除一些對。根據方程式10的要求設置的對數是以變量而不是以對存儲在第15行。
下面看圖3，列在裡面的分段碼說明了是怎樣用單獨子程序刪除重複的對的。首先按照上面的方程式20的要求，利用圖象的直方圖計算每對中出現的全部數量。第一行說明i循環用於計算每對值Mk，其次，根據在第5行中的Pair[].Count數據結構成員的減少順序存貯這些對。在下一行的刪除重複保留了對Pk，其頻率值Mk保持最大數量。第10行和以下行用分段編碼發現的獨特的象素對計算可嵌入到宿主數據中的全部字節數。
根據值Mk的減少順序將對值分類，從而把要嵌入一個特定的輔助數據流的對數減少到最低程度。然而，如果對值按隨機順序排列，則嵌入的數據的安全性就大大地增強了。將對值順序隨機化是本發明的一部分。這可以通過重新設置對值以便通過計算具有整數索引為pts[k]，i，k＝0，1，2，…，no_pairs和pts[k]，gamma＝δ0，δ1，…δr，…δno_pairs(其中，δr為隨機值)的入口的數據結構而將順序隨機化的方法而實現。對數據結構(pts[])分類以便把隨機值放在上升順序中使索引值隨機化。隨機索引值與上面計算的對值一併使用，以便重新排列表格，從而給出隨機對值順序。
用於調色板格式圖象的算法允許在不考慮單獨的出現頻率的情況下操縱象素值。參考圖4，另一個分段編碼適用於Truecolor圖象。在這裡引入的出現頻率有限制，它可把宿主數據直方圖上的嵌入作用減少到最小。
Truecolor圖象包含3幅單獨的8位灰度圖象，分別為紅，綠，藍圖象分量。Truecolor圖象沒有調色板。三個8位分量可能的組合可給出大約1千6百萬種顏色。本發明用分別對待每幅RGB分量圖象的辦法向Truecolor圖象嵌入數據。所以在混合圖象色上嵌入的作用就保持在各個彩色密度分量的噪聲中。
圖4第2行開始的ip-循環參照彩色平面(對RGB而言，ip＝0，1，2)。每個數值的變化頻率(從0到255)在數組hist_values[]中給出，彩色平面直方圖受第7行ip256所偏置。變量fvalue[]保持彩色分量ip的浮點直方圖值。第11行開始一個循環以限制為幾乎相等的出現頻率所選擇的對。在噪聲限制範圍內的象素密度(RANGE)被選作比較統計頻率。統計一致的容差δ在17行是5％，該容差可以在特殊用途中進行調整。
當所有可能的值都受到噪聲限制及統計頻率的測試後，在27行對發現的對進行了分類，重複的就刪除，起始索引在第31行加1，搜索繼續進行。對數的最大值又一次由算法限制決定，i，j對值必須少於一個圖象行中象素的一半。對於調色板格式圖象，本發明的安全性包含使對值入口的隨機化。
採用統計限制可以將嵌入輔助數據的宿主圖象作用降低到最小程度。如果容差δ設在0，則所選的每一對就包含小於在密度分離中噪聲值的數據值，並以完全相同的統計頻率出現。設定容差δ＝5％，如圖4的分段編碼所示，就可接受在頻率上接近的象素對，並同時仍然保留大部分宿主數據的統計性能。如果有，可通過要求相同出現頻率的方式被發現的也是極少數對。
把輔助數據實際嵌入到一組宿主數據的過程包含了對冗餘數值出現順序的重新排列。由分析發現的宿主數據值對是用於把輔助數據的位流編碼進入宿主數據的象素值。重要的是要意識到用於嵌入的數值是已經出現在宿主數據中的值。本發明的嵌入過程並不會改變宿主數據中數值的數量。
在本發明的嵌入過程中，宿主數據按順序進行處理。首先是通過宿主數據檢查每個值並測試與象素-對值是否匹配。在宿主數據中的匹配值就被恢復成數據結構值，pair[k].i，k＝0，1，2，…Np。這一步驟把(圖1)宿主BITMAP圖象恢復成對值，其相當於輔助數據中的零。然後通過輔助數據檢查將被嵌入的數據的順序位，並根據將被嵌入的輔助位值把宿主數據元素的對值設為i或j。如果正在嵌入的位流是隨機的，則宿主數據對值i和j在嵌入過程完成後就會在宿主圖象裡以相同的頻率出現。
圖5解釋了完成實際嵌入工作的分段碼，其中包括用於操縱首標信息裡的數據輔助位流，和宿主數據文件所必需的大量信息。第1-12行給存儲器定位並啟動變量。即將嵌入的首標及位流數據表示「數據-圖象」，並存在數組裡，data_row[]。宿主數據就表示「圖象-數據」。
索引Ii用於始於第12行的循環，以統計數據-圖象中字節的位置。這個循環始於Li＝-512，因為首標信息在數據-圖象字節之前嵌入。14行包含用首標信息對裝入data_row[]所進行的測試。20行包含用從數據-圖象文件，磁帶5取出的字節裝入data_row[]所進行的測試。
第30行啟動一個用於數據-圖象字節內的位循環。變量，位索引＝(0，1，2，…7)統計數據-圖象字節內的位的位置，數據-行(d_inrow)，由變量d_inrow的索引。變量Ij檢索宿主圖象中的字節(象素)。變量，inrow，檢索圖象-數據緩衝器，圖象_行[inrow]。第32行是對輸出到圖象-數據文件中的嵌入數據(一個完整的象素行)進行測試，第40行對完成通過一遍圖象-數據的測試。每個象素對pair[k]，k＝0，1，2，…Np，都要進行一遍圖象-數據通過。
在第47行中，對索引被增加。一個臨時的對數據結構變量(稱為「pvalue」被用於保持正在被用做嵌入的宿主數據圖素的工作對值。第60行刷新圖象-數據緩衝器image_row。
嵌入測試在第72行完成。如果image_row(inrow)的內容與代表零的數據-圖象位的對值相等，那麼就沒有變化。圖象-數據值保持在「pvalue，i」。然而，如果位流值是1，則圖象-數據值變成同等的pvalue，j。第84行把圖象-數據值看成不等於嵌入對值，pvalue，i。在這種情況下，位索引量就減少(減1)，因為數據-圖象位還沒有被嵌入，同時圖象-數據索引在增加以檢查下一個宿主數據值。
把用於嵌入輔助數據-圖象位流的過程逆反就可把已嵌入的數據抽取出來。嵌入的圖象-數據組的直方分析將會暴露出抽取的備選對，因為只有在這種情況下，單獨的統計頻率不會被嵌入過程改變。圖2-5的編碼中，統計頻率受到嵌入過程的輕微改變。用於嵌入的對表格可利用分析原始圖象-數據重新創建，但它一般不能準確地從已嵌入的圖象-數據中發現。
此外，已如上文所描述的那樣，本發明包括對-值的順序隨機化處理，因此在事先不了解對值順序的情況下，就大大地增加了用於抽取已嵌入的數據所必需的分析量。
如前面所述，為嵌入所選擇的有序對構成了從圖象-數據裡抽取數據-圖象的「密匙(key)」。圖2-5中的編碼表說明嵌入分析怎樣把宿主數據中的噪聲成分的統計性能簡化成一張數值對表。密鑰——對在抽取嵌入的數據時是需要的，但它們不能在嵌入過程完成之後靠分析宿主數據生成。然而，「密鑰」可以從原始的，未被修改過的宿主數據中重新生成。所以，正在嵌入的數據類似於一次插入的加密器，可為已嵌入的位流提供極其安全的措施。
由於對表已知，抽取處理包括按順序測試象素值以便為首標信息和數據-圖象重新建立輸出位流。在本項發明中，在可以進行抽取處理時也可將對表插入到主圖象-數據中。可選擇地，本發現允許隨意移動對表並以單獨的文件進行存儲。一般來說，對表的大小範圍在幾個到幾百個字節。表的允許最大尺寸是象素行長度的一半。隨著對表消失，只要原始宿主圖象-數據不能獲得，嵌入的數據就是安全的。因此，嵌入法接近一次插入加密法可保證數據的安全。
另一個保護對表的方法是移動密鑰並用公共密鑰或另一個加密手法對其進行加密。本發明可使加密後的密鑰放在宿主圖象-數據中，防止未授權者抽取。
把輔助數據嵌入到宿主中會稍微改變用於編碼位流的象素值的統計出現頻率。壓縮或加密嵌入數據是絕好的偽隨機輔助位流。結果，使得具有偽隨機性能的嵌入輔助數據將嵌入對中的值的平均出現頻率的變化減少到最低限度。嵌入沒有壓縮或加密的字符數據大大降低了本發明可提供的安全性。
嵌入數據的存在不易通過分析嵌入數據的圖象-數據所察覺。當談到密碼方法時，數據的嵌入是把數據-圖象及圖象-數據卷積在一起。被嵌入的原始數據-圖象位流代表一份明文。把宿主和嵌入的數據合併起來就在宿主的噪聲分量裡插入了一份密文。然而密文的存在並不明顯，因為宿主載體信息的內容及意義受到了本發明所披露技術的保護。根據本發明進行的數據嵌入與加密不同，因為沒有生成明顯的密文。
不熟悉「明文」、「密文」術語的人可參考B.Schneier的書「應用密碼協議、算法及原碼」。此書的內容結合於此作為參照文件。
正如前面所提到的那樣，本發明在把輔助信息嵌入到傳真數據中是很有用處的。在前面有關輔助信息嵌入到圖象宿主數據的討論中，可以得知噪聲分量產生於象素數據的數值不確定性，或是在調色板的彩色值中。傳真傳輸實際是發送包含黑白BITMAP數據的圖象，也就是說，來自圖象象素的數據是分別代表黑或白的二進位(0，1)值，而噪聲的作用要麼增加象素，要麼從數據中移去象素。所以本發明以雙色BITMAP的形式處理傳真黑白BITMAP圖象。
辦公室通用的傳真機是將掃描儀和通過電話線傳輸圖象所需的數字硬體和軟體結合在一起。使用專門的數據機協議進行圖象傳輸，其特點是獲得此技術的途徑極其多。例如，在EXP Modem用戶手冊中就對膝上型計算機的傳真/數據數據機進行了描述。計算機之間的傳真傳輸是數字通訊，因此，這樣的數據適合數字嵌入。
正如以上談論的有關數據嵌入到圖象的處理，傳真嵌入過程是按兩個階段進行的分析和嵌入。在傳真雙色BITMAP時，圖象噪聲要麼增加，要麼就從圖象中去掉白象素。由於這一點，依次的相同象素的運行長度就有變化。
在雙色BITMAP圖象裡，掃描過程通過在源拷貝中由相繼的黑色象素運行來代表白色行。在該運行中的象素數量是不定的，至少±1，這是由於掃描儀的分辯率及原始材料不確定地向黑-白BITMAP格式轉換所造成的。
這裡所舉的數據嵌入到雙色BITMAP數據的例子包含分析BITMAP來確定相繼象素運行的統計出現頻率或直方圖。本發明的嵌入處理根據輔助數據-圖象中的位流內容改變象素(0，+1)運行長度。適合嵌入的宿主數據是任何一幅雙色BITMAP圖象，它的大小是按傳真傳輸設計的。傳真傳輸的硬拷貝可以被掃描生成雙色BITMAP，或是利用計算機內的傳真印表機驅動軟體生成的圖象。
傳真嵌入處理由分析象素每一行的運行長度開始。這一步驟的完成情況由圖6的分段碼解釋。程序rowstats的變量是在一行象素數據的指針，它包括每個象素一個字節，既可為零也可是1；指向統計頻率數組的指針；數據行中象素列的數量；以及用於內部程序任選的標記。任選標記是將被嵌入的輔助位流塊或包的尺寸，任選標記已在第9行被測試，程序Packet_col用於正向任選標記。此程序列在圖7的編碼表中，其目的是確保數據行中的第一個象素按偶列數開始。這行的第一個象素位置標誌數據包的起始，這一切將在下面詳細描述。
第12行是一個循環，用來檢查數據行裡的象素運行。在規定的值MINRUN和MAXRUN之間的運行由這個循環來檢查。在15行中的j-循環給象素運行定位並給運行起始索引設立變量K。21行的測試只選擇長度短於行長度的象素塊。22行裡的循環將象素運行移到數組塊[]的暫時存儲中。
24行和25行處的兩個測試拒絕有運行長度的塊，而不是i-循環的當前值所需的塊。嵌入方案選擇長度為i的塊，為了嵌入數據則增加一個象素使長度變成i+1。根據輔助嵌入數據的位流，這樣就可以保證運行包含或i或i+1的非零象素值。如果存儲在變量塊[]數組裡的運行沒有在至少兩個零裡結束，則它就不可作為i+1長度運行被接受。編碼轉移到NEXT，以檢查下一個運行。
28行開始一個循環以統計運行中的象素數量。被發現的數在第31行被增加1，使運行長度等於i+1。第33行包括一個測試，用來保證所選的運行有正確的長度。運行長度索引i的直方圖[]數組被增加以計算運行的出現頻率。用於運行的數據行字節由36行的循環作標誌，用一個字母代碼區分設址運行。這一標識技術使嵌入數據能容易地確定嵌入位流所用的運行。在這條程序的出口上，數據行字節包含用字母代碼標誌的運行以便為嵌入位流指明可使用的象素位置。返回值是位於數據行中的運行數量。零返回說明在MINRUN和MAXRUN的規定範圍內沒有運行被設址。
傳真數據機協議強調速度，因此不包括糾錯。由於這個原因，根據電話線的質量及傳輸速度，傳真傳輸容易丟失信息，產生衝擊噪聲，並且丟失數據。由於有成功的嵌入技術，本發明可以彌補圖象數據的一部分損失。為了完成這一目的，數據機塊協議中的各種各樣內容被用於嵌入首標和輔助數據。雙色圖象被當成一個傳輸媒體，數據被嵌入到塊或包中，用於包-起始標識和奇偶檢查。包起始由具有在偶列中的第一個象素的圖象行表示。當包含在塊裡的位數被抽取時，或在訛誤的軟體包中，當包-起始標識被定位在一行時，軟體包結束。奇偶檢查結果及包順序號與數據一起嵌入到包裡。使用這種方法，傳真傳輸中的錯只會導致一部分而不是全部嵌入數據的損失。
由於傳輸錯造成的數據丟失量取決於源圖象中象素的密度及丟失信息的長度。按每包20位元組算，一個標準文本在傳輸中會導致一到兩個數據包丟失。一般來說，一項成功的發明會考慮傳真宿主圖象信息的清晰度。
現在回到圖7，裡面所列的步驟是用來啟動雙色BITMAP行，以便為每個包的起始設立標誌。雙色圖象中的每行包含一個起始於偶列(包起始)或是奇列(包連續)的非零值。
在圖7中，可以看到第四行起始於一個在數據行裡運行的象素數的循環。在傳真圖象中，零象素值指黑色空間，1指白色空間。第5行把第一個黑色空間放在該行的數據中。如果變量packet_size是正的，則列索引被測試成偶數，同時圖素被強制代表白色空間。如果packet_size變量是負的，程序就會在不做任何變動的情況下返回到數據行標識的指針上。如果packet_size大於零，則第一數據行元素就表示白色空間。第11行處理是當packet_size等於零的情況，並指出連續行。在連續行中，第一數據行元素被迫表示黑色空間。由17-20行子程序返回的值說明被檢查的象素行的性質。
圖8的分段程序提供了嵌入雙色BITMAP傳真圖象的輔助數據。一行中的象素按上述辦法處理，在它被分析及用數字代碼進行標識後檢查數據行的內容，以說明運行長度。第1至49行是對雙色BITMAP圖象裡象素索引Ij做的大循環(未示出)的一部分。1-26行負責從雙色BITMAP裡讀一行象素，並在第1行變量nrow裡存儲圖象的行數。象素值位被解碼並在第12-36行中擴展成image_row[]數組。image_row[]數組包含以每節字一個值(0或1)存貯的象素值。
第28行用packet_col[]程序返回該行的包索引。如果28行的j是零，這行就是packet_start行，如果j是1，這行是連續行。29行使用roustats程序為行緩衝器內的象素指定運行-長度字母標誌。返回值i給出在圖象行設址的運行數量。常規試驗在31，37，和41行完成。索引Kp給出了一個數據包內的象素行數。如果Kp是0，這行必定是packet_start索引，如果Kp＞0，這行必定是連續行。第49行完成雙色圖象數據的讀和預處理過程。
數據-結構數組，pair[]包含(i)的運行長度，擴充運行長度(i+1)及雙色BITMAP圖象中的全部運行數。在始於51行的循環中的索引k是正被嵌入的運行長度索引。索引inrow計算在圖象行緩衝器及變量內的象素。位索引是位流字節內的位-位置索引。
57行為變量testltr中的運行長度字母代碼設定值。圖象象素值用58行的字母代碼進行測試。如果測試字母代碼標識設定位置，第60行就把這行中的索引推到正用於嵌入的象素運行之尾。62行中的測試功能是檢查位流包字節中當前位索引的值。如果此值為1，則運行中的最後一個象素就設為1，否則就設為0。
尾隨一個運行設定象素值便可完成雙色BITMAP圖象的嵌入工作，其方法是根據包數據內的偽隨機位流引入生成的噪聲。在image_row數組數據打包和寫回BMP格式文件之前，通過調用圖8的rowstats而把被寫入行緩衝器中的字母標識值重新設置成二進位單位。完成這項任務的過程雖未在圖8中描述，但對熟悉此技術的人來說是可以理解的。
根據本發明，要想把已嵌入到雙色BITMAP傳真圖象中的數據抽取出來，只有在計算機接受到傳真圖象後才能完成。圖象數據由接收計算機以文件格式存儲(很可能是傳真壓縮格式)，這就需要把圖象轉換成BITMAP格式並抽取已嵌入的數據。送到標準辦公機器上的傳真數據對所抽取的數據是不可修改的，因為列印出的圖象質量不足以靠掃描來發現被嵌入的數據。
然而，本發明的確使用了掃描/列印傳真機，它是靠計算機硬體內部處理數據。已嵌入的輔助數據在將宿主數據掃描之後，但在傳輸之前才被插入。這些數據在被接受以後，可在列印之前被抽取。
雙色圖象嵌入的密鑰可通過分析已嵌入數據的圖象找到，因為運行長度並未與原始(i，i+1)值有變。凡是被使用過的值，其順序取決於圖象中的出現頻率。以調色板圖象為例，值的密鑰及用於嵌入的對的順序插入到傳真中。然而，嚴格地講密鑰不是必不可少的，因為原則上講，規定值MINRUN和MAXRUN允許重新計算接收圖象上的運行長度統計。在實際操作中是需要密鑰的，因為在傳真數據機通信聯繫中，傳輸誤差可能引入新的運行長度，它可以改變圖象的統計性能，因為對順序是不知的。即使傳真嵌入與向調色板圖象中嵌入輔助數據相比安全性有些低，但雙色BITMAP傳真數據嵌入仍然被認為類似於一次插入加密。
以上就本發明中詳細內容所進行的描述目的是為了解釋和說明其功能，而絕非限制其用途。很明顯，許多修改和變化會依照上述解釋來做。所選的及所描述的具體內容是為了使熟悉本技術的人能更好地理解本發明的原理及實際用途，並在實際運用中使用並根據實際情況進行修改。本發明的範圍由所附權利要求書限定。
權利要求
1.一種將輔助數據嵌入到宿主數據中的方法，其特徵在於包括以下步驟生成該宿主數據的數字表示，該宿主數據以具有數值並包含噪聲分量的元素形式出現；以單獨位值的順序形式生成該輔助數據的數字表示；計算該宿主數據的所述數字表示中的噪聲分量；用該噪聲分量與該元素對進行比較以確定具有數值的該元素的對數，所述數值小於所述噪聲分量的值；從所述元素對中取出大體相等的值替換所述元素的單個值，以便把相當於該輔助數據位值順序的所述輔助數據的單個位值嵌入；以及把所述宿主數據和已嵌入宿主數據的輔助數據以一個文件形式輸出。
2.根據權利要求1所述的方法，還包括在完成該輔助數據的數位化後把該輔助數據與預先確定的信息組合在一起的步驟，其中，所述信息指示所述輔助數據、其文件名、以及文件的大小。
3.根據權利要求1所述的方法，還包括確定嵌入該輔助數據到該宿主數據的協議，它可以驗證從該宿主數據中抽取的該輔助數據。
4.從包含噪聲分量的宿主數據中抽取已嵌入的輔助數據的方法，其特徵在於包括以下步驟從所述宿主數據中抽取指示所述已嵌入的輔助數據的一個位順序，用以驗證所述宿主數據；解釋該宿主數據並確定宿主元素對，該宿主元素對小於該噪聲分量，並相當於該輔助數據的位值；利用該位順序標識該輔助數據；以及以一個文件形式抽取該輔助數據。
5.根據權利要求1所述的方法，其中所述的宿主數據包括一幅彩色照片。
6.根據權利要求1所述的方法，其中所述的宿主數據包括一幅黑白照片。
7.根據權利要求1所述的方法，其中所述的宿主數據包括電視信號。
8.根據權利要求1所述的方法，其中所述的宿主數據包括一幅畫。
9.根據權利要求1所述的方法，其中所述的宿主數據包括傳真傳輸。
10.根據權利要求1所述的方法，其中所述的宿主數據包括身份證。
11.根據權利要求1所述的方法，其中所述的宿主數據包括數字音頻信息。
全文摘要
一種將輔助數據嵌入一組宿主數據(例如照片，電視信號，傳真傳輸，或身份證)的方法。所有這類宿主數據都包括固有噪聲，允許幾乎相同並且其值小於噪聲值的宿主數據中的象素被操縱並由輔助數據置換。由於嵌入方法並未改變宿主數據的元素值，因此輔助數據基本不影響宿主數據的外形和解釋。通過實際為逆向的處理，嵌入的數據可由授權的用戶容易地檢索。
文檔編號H04N7/52GK1146817SQ96190120
公開日1997年4月2日 申請日期1996年2月22日 優先權日1995年2月23日
發明者麥克斯韋·T·桑德福特Ii, 塞歐德爾·G·韓德爾 申請人:加裡福尼亞大學董事會