Want to save a copy of your personal file on a usb pendrive but you are worried that, in case of theft, someone will be able to access your data?
With Free File Camouflage you can hide your files inside a jpeg image!
The software can be used with the main interface or via the explorer "send to" context menu (the first time you only need to select a directory with some images).
All the files are encrypted using AES and hidden inside an image.
What happens if someone tries to open a camouflaged image? Well... nothing! He will only see the image.
Download
中文網頁介紹
Showing posts with label jpeg. Show all posts
Showing posts with label jpeg. Show all posts
Saturday, January 21, 2012
Friday, October 01, 2010
News: Google 發表影像壓縮新技術 取代過時的 JPEG
數位時代網站新聞精選 原始連結
撰文者: 戴佳慧 日期：2010/10/01
一向以完美網頁瀏覽體驗為己任的 Google 再出新招！今天 Google 在 Chromium 官方部落格上發表了一種全新影像格式 WebP，能大幅改善網頁圖檔的傳輸效能。經過 WebP 壓縮的影像，檔案大小比常見的 JPEG、GIF、PNG 格式平均減少了 39%，色調和色彩演繹相較之下也毫不遜色。
Chromium 部落格指出，今日的網頁傳輸有 65% 用在影像和照片下載。在行動網路和頻寬有限的情況下，使用者點開網頁之後，還要耐心等待圖片緩緩展開。為了提供使用者更順暢、更愉快的網頁瀏覽經驗，Google 利用全新壓縮技術 VP8 設計了一套新的影像壓縮格式 WebP，大幅減少圖檔大小，讓網頁下載更迅速。
VP8 原本是由美國上市科技公司 On2 所開發出來的視訊壓縮格式，Google 在今年年初收購了On2，接著在五月開放 VP8 技術原始碼。Google 看出 VP8 技術在圖像失真壓縮上也大有可為，足以取代過時的 JPEG、GIF 格式等早年研發成果，因此將 VP8 稍加改編之後推出了新的 WebP 影像格式。
Google 隨機在網路上找了一百萬張圖片作測試，比較 WebP 和傳統格式的壓縮效能和畫質，並分享了幾中幾張圖片讓網友們參考。Google 網站上也提供了轉換軟體，能夠將各種格式的圖片輕鬆轉換成 WebP 檔，歡迎網友們一同試用比較。
撰文者: 戴佳慧 日期：2010/10/01
一向以完美網頁瀏覽體驗為己任的 Google 再出新招！今天 Google 在 Chromium 官方部落格上發表了一種全新影像格式 WebP，能大幅改善網頁圖檔的傳輸效能。經過 WebP 壓縮的影像，檔案大小比常見的 JPEG、GIF、PNG 格式平均減少了 39%，色調和色彩演繹相較之下也毫不遜色。
Chromium 部落格指出，今日的網頁傳輸有 65% 用在影像和照片下載。在行動網路和頻寬有限的情況下，使用者點開網頁之後，還要耐心等待圖片緩緩展開。為了提供使用者更順暢、更愉快的網頁瀏覽經驗，Google 利用全新壓縮技術 VP8 設計了一套新的影像壓縮格式 WebP，大幅減少圖檔大小，讓網頁下載更迅速。
VP8 原本是由美國上市科技公司 On2 所開發出來的視訊壓縮格式，Google 在今年年初收購了On2，接著在五月開放 VP8 技術原始碼。Google 看出 VP8 技術在圖像失真壓縮上也大有可為，足以取代過時的 JPEG、GIF 格式等早年研發成果，因此將 VP8 稍加改編之後推出了新的 WebP 影像格式。
Google 隨機在網路上找了一百萬張圖片作測試，比較 WebP 和傳統格式的壓縮效能和畫質，並分享了幾中幾張圖片讓網友們參考。Google 網站上也提供了轉換軟體，能夠將各種格式的圖片輕鬆轉換成 WebP 檔，歡迎網友們一同試用比較。
Wednesday, May 06, 2009
Entropy-Coded Segment (ECS) in Rex.jpg
Rex.jpg 影像中的第一個 Entropy-coded segment (ECS) 是出現在 Rex.pdf 文件 page: 24 的 0000373eh ～ 00003826h, 從 F9 85 ... 一直到 49 7F, 一共有 233 個 Bytes.
從 page:23 00003586h 的 DRI Segment, 我們可以得知一個 ECS 中包含了 15 個 MCUs (minimum coded unit), 每一個 MCU 則分別包含一個 8*8 的 Y 亮度區塊, 一個 Cb 色差區塊, 一個 Cr 色差區塊。因此, 這個 233 位元長的 ECS 區段總共包含了 45 個 8*8 的 DCT 係數區塊。
使用 Rex-HuffmanTable.pdf 的 4 個 Huffman Tables, 我們可以將第一個 ECS 還原成 DCT 係數, 詳細的還原過程, 我們記錄在 Rex-Decoding-ECS0.pdf 檔案中, 有興趣的人可以自行下載、查驗。
接在第一個 ECS 後面的是一個 Define Restart Interval (DRI) Marker, 編號從 0 開始, 所以是 'FFD0', 然後才是接著第二個 ECS, 範圍是在文件中 page: 24 的 00003829h ～ 00003951h, 從 F9 8D ... 一直到 A4 BF, 一共有 297 個 Bytes. 後面接著第 2 個 DRI Marker - 'FFD1' , 然後就是開始第三個 ECS。
Rex.jpg 中, 一共有 15 個 ECS, 被 14 個 DRI Marker 分隔著, 編號從 0 開始增加, 最大編號是 7, 然後又從 0 開始編號, 所以最後一個 DRI Marker 編號是 'FFD5' 。最大的編號是 7 的原因很簡單, 因為 'FFD8' 之後的 Marker 都有其各自的意義。
14 個 DRI Marker 出現在 Rex.pdf 的位置分別如下:
FFD0 page: 24 00003827h
FFD1 page: 25 00003952h
FFD2 page: 25 00003ab2h
FFD3 page: 26 00003c31h
FFD4 page: 27 00003debh
FFD5 page: 27 00003f9ch
FFD6 page: 28 000041cah
FFD7 page: 29 000043cbh
FFD0 page: 30 00004624h
FFD1 page: 31 0000484ah
FFD2 page: 32 00004adch
FFD3 page: 33 00004d68h
FFD4 page: 34 00005038h
FFD5 page: 36 00005326h
Monday, April 27, 2009
Thursday, April 09, 2009
Huffman Table in the Rex.jpg
使用 UltraEdit 將 Rex.jpg 檔以 16 進位表示法開啟, 可以得到 Rex.pdf 這份文件。在文件 Page: 23 的 0000358ch 位址上, 可以找到 X'FFDC marker, 整個 DHT (Define Huffman Table(s)) Segment 一直延續到 Page:24 的 0000372f h 結束。
DHT Segment 一共存放了 4 個 Huffman Tables, 使用 Huffman Table Generating Procedure 可以將 DHT Segment 轉換成 4 個 Huffman Tables，我將其存放在 Rex-HuffmanTable.pdf 文件中供人參考。
Saturday, November 24, 2007
Structure of AC code table
在 JPEG 規格書 P. 89 談到了 AC code table 的結構。每一個非零的 AC 係數都是以一個 8-bit RS (Run/Size) 的形式來描述。
RS = binary 'RRRRSSSS'
4 個低位元 SSSS 定義非零的 AC 係數所屬的類別 (category), 分成 10 個類別, 可由 Table F.2 查到每個類別的範圍。高位元的 4 個 RRRR 則是指出非零 AC 係數之前存在多少個 0。由於有可能超過 15 個 0, 4-bit 的 RRRR 無法表示, 因此定義了 'RRRRSSSS' = X'F0' 來代表 15 個 0 外加一個值為 0 的 AC 係數, 換句話說, 共16個 0。除此, 如果在 Zigzag 序列中, 後面的 AC 係數已經全部為 0 了, 就用一個 EOB (end-of-block), 'RRRRSSSS'= '00000000' 來表示。
Table F.2 Categories assigned to coefficient values
SSSS AC coefficients
1 -1, 1
2 -3,-2, 2, 3
3 -7..-4, 4..7
4 -15..-8, 8..15
5 -31..-16, 16..31
6 -63..-32, 32..63
7 -127..-64, 64..127
8 -255..-128, 128..255
9 -511..-256, 256..511
10 -1023..-512, 512..1023
RS = binary 'RRRRSSSS'
4 個低位元 SSSS 定義非零的 AC 係數所屬的類別 (category), 分成 10 個類別, 可由 Table F.2 查到每個類別的範圍。高位元的 4 個 RRRR 則是指出非零 AC 係數之前存在多少個 0。由於有可能超過 15 個 0, 4-bit 的 RRRR 無法表示, 因此定義了 'RRRRSSSS' = X'F0' 來代表 15 個 0 外加一個值為 0 的 AC 係數, 換句話說, 共16個 0。除此, 如果在 Zigzag 序列中, 後面的 AC 係數已經全部為 0 了, 就用一個 EOB (end-of-block), 'RRRRSSSS'= '00000000' 來表示。
Table F.2 Categories assigned to coefficient values
SSSS AC coefficients
1 -1, 1
2 -3,-2, 2, 3
3 -7..-4, 4..7
4 -15..-8, 8..15
5 -31..-16, 16..31
6 -63..-32, 32..63
7 -127..-64, 64..127
8 -255..-128, 128..255
9 -511..-256, 256..511
10 -1023..-512, 512..1023
Huffman encoding procedures for DC coefficients
在 JPEG 影像壓縮標準中, 對於 DC 係數的編碼, 霍夫曼編碼程序(Huffman encoding procedures) 使用了下列 2 個擴展表格(extended tables):
1) XHUFCO
2) XHUFSI
這兩個表格都是以相鄰兩個 block 區塊的差值(DIFF) 為索引, XHUFCO 存放 DIFF 所屬類別(category) 的 Huffman code, 再接上 為了區分 DIFF 在此類別中的位置的附加位元(additional bits)。XHUFSI 則是存放 DIFF 值所對應的 XHUFCO 表格中的位元長度, 即 Huffman code 長度加上附加位元的長度。
XHUFCO 與 XHUFSI 這兩個表格則是由 Annex C, P. 52 所談到的 EHUFCO 與 EHUFSI 兩個表格加上附加位元擴展而來。
有了 XHUFCO 與 XHUFSI 兩個表格, 當我們有一個 DIFF 需要編碼時, 只要快速查表即可很快地產生 binary data。針對 DC 差值 (DIFF), 霍夫曼編碼程序如下:
SIZE = XHUFSI(DIFF)
CODE = XHUFCO(DIFF)
code SIZE bits of CODE
1) XHUFCO
2) XHUFSI
這兩個表格都是以相鄰兩個 block 區塊的差值(DIFF) 為索引, XHUFCO 存放 DIFF 所屬類別(category) 的 Huffman code, 再接上 為了區分 DIFF 在此類別中的位置的附加位元(additional bits)。XHUFSI 則是存放 DIFF 值所對應的 XHUFCO 表格中的位元長度, 即 Huffman code 長度加上附加位元的長度。
XHUFCO 與 XHUFSI 這兩個表格則是由 Annex C, P. 52 所談到的 EHUFCO 與 EHUFSI 兩個表格加上附加位元擴展而來。
有了 XHUFCO 與 XHUFSI 兩個表格, 當我們有一個 DIFF 需要編碼時, 只要快速查表即可很快地產生 binary data。針對 DC 差值 (DIFF), 霍夫曼編碼程序如下:
SIZE = XHUFSI(DIFF)
CODE = XHUFCO(DIFF)
code SIZE bits of CODE
Wednesday, November 14, 2007
Huffman decoding of DC coefficients
由於以下兩個原因:
1) DCT 的 DC 係數就是代表 8*8 區塊的像素平均值,
2) 影像中相鄰區塊的像素平均值有很大的機率是相近的
因此 JPEG 的 Huffman encoding procedure 並不是直接對 DC coefficients 編碼, 而是對兩個相鄰區塊的 DC difference 編碼。由於 difference 可能的值涵蓋太廣了, 對每一個可能值採取直接編碼的方式並不可行 (decoding tree 太大了), 因此 JPEG 採用的作法是先對所有可能值分成12個類別(category), 然後統計每一類別的機率, 有了機率後, 再依機率做 Huffman 編碼。JPEG 規格書 P.89 的 Table F.1 列出了 DC difference 是如何分類的
Table F.1 Difference magnitude categories for DC coding
SSSS DIFF values
0 0
1 -1, 1
2 -3,-2, 2, 3
3 -7..-4, 4..7
4 -15..-8, 8..15
5 -31..-16, 16..31
6 -63..-32, 32..63
7 -127..-64, 64..127
8 -255..-128, 128..255
9 -511..-256, 256..511
10 -1023..-512, 512..1023
11 -2047..-1024, 1024..2047
除了第 0 類 (SSSS=0) 之外, 每一類中, difference 的可能值並不只有一個, 因此還另外需要一些額外的位元(appended additional bits) 來標示出確切的 difference 值。所需要的額外位元總數就剛好是 SSSS 值, 原因很簡單, 第 1 類 (SSSS=1) 中有 -1, 1 兩個可能值, 因此只需要 1 個額外位元來指出真正的 difference 值是哪一個。同理, 第 2 類 (SSSS=2) 中有 -3, -2, 2, 3 共 4 個可能值, 因此需要 2 個額外位元來指出真正的 difference 值是哪一個。其餘類別的個數剛好就是 2^SSSS 個, 因此共需要 SSSS 個額外位元才夠指出真正的 difference 值為何。
如果 DIFF > 0, 額外位元就是 DIFF 的二進位表示法中的 SSSS 個低位元(low order bits), 如果 DIFF < 0, 則是用 (DIFF-1) 的 SSSS 個低位元。 我們舉例說明: a) 假設 DIFF 值為 -9, SSSS=4, 因為DIFF < 0, 因此 (DIFF-1) = -10, 用 2-complement 來表示 -10, 為 11110110, 那麼 4 個低位元就是 0110。 JPEG 解壓縮時, Huffman decoding procedure 如果使用 decoding tree 解碼得到 SSSS=4, 就會繼續取得 4 個額外位元 0110, 根據第 1 個位元判斷 DIFF<0, 然後使用後面 3 個位元計算得到 6, SSSS=4 這個類別負數區間的最小值為 -15, 將 -15 + 6 = -9 , 就可以得到 DIFF = -9。 b) 假設 DIFF 值為 6, SSSS=3, 因為 DIFF > 0, 因此用 2-complement 來表示 6 為 00000110, 那麼 3 個低位元就是 110。
使用 decoding tree 得到 SSSS=3 後, 繼續取得 3 個位元 110, 由於第 1 個位元為 1, 因此判斷 DIFF 屬於正數區間, 後面兩個位元為 10, 值為 2, 正數區間的最小值為 4, 4 + 2 =6 因此得到 DIFF=6。
1) DCT 的 DC 係數就是代表 8*8 區塊的像素平均值,
2) 影像中相鄰區塊的像素平均值有很大的機率是相近的
因此 JPEG 的 Huffman encoding procedure 並不是直接對 DC coefficients 編碼, 而是對兩個相鄰區塊的 DC difference 編碼。由於 difference 可能的值涵蓋太廣了, 對每一個可能值採取直接編碼的方式並不可行 (decoding tree 太大了), 因此 JPEG 採用的作法是先對所有可能值分成12個類別(category), 然後統計每一類別的機率, 有了機率後, 再依機率做 Huffman 編碼。JPEG 規格書 P.89 的 Table F.1 列出了 DC difference 是如何分類的
Table F.1 Difference magnitude categories for DC coding
SSSS DIFF values
0 0
1 -1, 1
2 -3,-2, 2, 3
3 -7..-4, 4..7
4 -15..-8, 8..15
5 -31..-16, 16..31
6 -63..-32, 32..63
7 -127..-64, 64..127
8 -255..-128, 128..255
9 -511..-256, 256..511
10 -1023..-512, 512..1023
11 -2047..-1024, 1024..2047
除了第 0 類 (SSSS=0) 之外, 每一類中, difference 的可能值並不只有一個, 因此還另外需要一些額外的位元(appended additional bits) 來標示出確切的 difference 值。所需要的額外位元總數就剛好是 SSSS 值, 原因很簡單, 第 1 類 (SSSS=1) 中有 -1, 1 兩個可能值, 因此只需要 1 個額外位元來指出真正的 difference 值是哪一個。同理, 第 2 類 (SSSS=2) 中有 -3, -2, 2, 3 共 4 個可能值, 因此需要 2 個額外位元來指出真正的 difference 值是哪一個。其餘類別的個數剛好就是 2^SSSS 個, 因此共需要 SSSS 個額外位元才夠指出真正的 difference 值為何。
如果 DIFF > 0, 額外位元就是 DIFF 的二進位表示法中的 SSSS 個低位元(low order bits), 如果 DIFF < 0, 則是用 (DIFF-1) 的 SSSS 個低位元。 我們舉例說明: a) 假設 DIFF 值為 -9, SSSS=4, 因為DIFF < 0, 因此 (DIFF-1) = -10, 用 2-complement 來表示 -10, 為 11110110, 那麼 4 個低位元就是 0110。 JPEG 解壓縮時, Huffman decoding procedure 如果使用 decoding tree 解碼得到 SSSS=4, 就會繼續取得 4 個額外位元 0110, 根據第 1 個位元判斷 DIFF<0, 然後使用後面 3 個位元計算得到 6, SSSS=4 這個類別負數區間的最小值為 -15, 將 -15 + 6 = -9 , 就可以得到 DIFF = -9。 b) 假設 DIFF 值為 6, SSSS=3, 因為 DIFF > 0, 因此用 2-complement 來表示 6 為 00000110, 那麼 3 個低位元就是 110。
使用 decoding tree 得到 SSSS=3 後, 繼續取得 3 個位元 110, 由於第 1 個位元為 1, 因此判斷 DIFF 屬於正數區間, 後面兩個位元為 10, 值為 2, 正數區間的最小值為 4, 4 + 2 =6 因此得到 DIFF=6。
Saturday, November 10, 2007
Y'CbCr in JPEG Standard
JPEG allows Y'CbCr where Y', Cb and Cr have the full 256 values:
JPEG-Y'CbCr (601) from "digital 8-bit R'G'B' "
===========================================
Y' = + 0.299 * R'd + 0.587 * G'd + 0.114 * B'd
Cb = 128 - 0.168736 * R'd - 0.331264 * G'd + 0.5 * B'd
Cr = 128 + 0.5 * R'd - 0.418688 * G'd - 0.081312 * B'd
===========================================
R'd, G'd, B'd in {0, 1, 2, ..., 255}
Y', Cb, Cr in {0, 1, 2, ..., 255}
from Wikipedia: YCbCr
JPEG-Y'CbCr (601) from "digital 8-bit R'G'B' "
===========================================
Y' = + 0.299 * R'd + 0.587 * G'd + 0.114 * B'd
Cb = 128 - 0.168736 * R'd - 0.331264 * G'd + 0.5 * B'd
Cr = 128 + 0.5 * R'd - 0.418688 * G'd - 0.081312 * B'd
===========================================
R'd, G'd, B'd in {0, 1, 2, ..., 255}
Y', Cb, Cr in {0, 1, 2, ..., 255}
from Wikipedia: YCbCr
Thursday, October 25, 2007
Huffman Tree in the JPEG Decoder
當我們在 JPEG 影像檔的檔頭遭遇 X'FFC4' marker, 並且將 Huffman Table 產生出來後, 必須進一步建立 Huffman Tree, 如此就可以對 MCU 中的資料進行解碼。
(宣告部份)
// 遞迴的結構體宣告, 包含一個資料與兩個指向下一個節點的指標
struct stHuffmanDecodingTreeNode
{
int iCategory;
struct stHuffmanDecodingTreeNode *ZeroSubtree;
struct stHuffmanDecodingTreeNode *OneSubtree;
};
stHuffmanDecodingTreeNode *hdtnCurrentNode, *hdtnRoot[2][2];
stHuffmanDecodingTreeNode *hdtnNewNode;
(程式碼)
for ( iTc = 0 ; i Tc< 2 ; iTc++)
for ( iTh = 0 ; iTh< 2 ; iTh++)
{
hdtnCurrentNode = (stHuffmanDecodingTreeNode *) malloc(sizeof(struct stHuffmanDecodingTreeNode));
hdtnCurrentNode->iCategory = -1;
hdtnCurrentNode->ZeroSubtree = NULL;
hdtnCurrentNode->OneSubtree = NULL;
hdtnRoot[iTc][iTh] = hdtnCurrentNode;
for ( k = 0; k< iLASTK[iTc][iTh] ; k++)
{
hdtnCurrentNode = hdtnRoot[iTc][iTh];
iCodeLength = iEHUFSI[iTc][iTh][k];
for ( i = 0; i < iCodeLength ; i++)
{
if ( iEHUFCOB[iTc][iTh][k][i] == 0 )
{
if ( hdtnCurrentNode->ZeroSubtree != NULL )
hdtnCurrentNode = hdtnCurrentNode->ZeroSubtree;
else
{
hdtnNewNode = (stHuffmanDecodingTreeNode *) malloc(sizeof(struct stHuffmanDecodingTreeNode));
hdtnNewNode->iCategory = -1;
hdtnNewNode->ZeroSubtree = NULL;
hdtnNewNode->OneSubtree = NULL;
hdtnCurrentNode->ZeroSubtree = hdtnNewNode;
hdtnCurrentNode = hdtnNewNode;
}
}
else // iEHUFCOB[iTc][iTh][k][i] == 1
{
if ( hdtnCurrentNode->OneSubtree != NULL )
hdtnCurrentNode = hdtnCurrentNode->OneSubtree;
else
{
hdtnNewNode = (stHuffmanTreeDecodingNode *) malloc(sizeof(struct stHuffmanDecodingTreeNode));
hdtnNewNode->iCategory = -1;
hdtnNewNode->ZeroSubtree = NULL;
hdtnNewNode->OneSubtree = NULL;
hdtnCurrentNode->OneSubtree = hdtnNewNode;
hdtnCurrentNode = hdtnNewNode;
}
}
}
hdtnCurrentNode->iCategory = k;
}
}
在 Rex.jpg 這張影像中, DC 係數的第 1 個 Huffman table (for luminance component) 為
Category Length HUFFCODE Code word
0 3 6 110
1 3 5 101
2 3 3 011
3 3 2 010
4 3 0 000
5 3 1 001
6 3 4 100
7 4 14 1110
8 5 30 11110
9 6 62 111110
10 7 126 1111110
11 8 254 11111110
經過上述的程式所產生的 Decoding Tree 顯示在下圖, leaf node 中的紅色數字代表 category。
下圖每一個 node 中的籃色數字則是代表各個節點的產生順序。
注意: 上述程式為了程式的可讀性, 用了全型的空白" "來控制部落格文章的內縮顯示。因此, 如果你要直接複製上述程式到 C++ Builder 執行, 請務必將全型空白" "改成半型空白" ", 否則, 編譯時發出現以下的錯誤訊息:
[C++ Error] Unit1.cpp(40): E2206 Illegal character ' ' (0xa140)
(宣告部份)
// 遞迴的結構體宣告, 包含一個資料與兩個指向下一個節點的指標
struct stHuffmanDecodingTreeNode
{
int iCategory;
struct stHuffmanDecodingTreeNode *ZeroSubtree;
struct stHuffmanDecodingTreeNode *OneSubtree;
};
stHuffmanDecodingTreeNode *hdtnCurrentNode, *hdtnRoot[2][2];
stHuffmanDecodingTreeNode *hdtnNewNode;
(程式碼)
for ( iTc = 0 ; i Tc< 2 ; iTc++)
for ( iTh = 0 ; iTh< 2 ; iTh++)
{
hdtnCurrentNode = (stHuffmanDecodingTreeNode *) malloc(sizeof(struct stHuffmanDecodingTreeNode));
hdtnCurrentNode->iCategory = -1;
hdtnCurrentNode->ZeroSubtree = NULL;
hdtnCurrentNode->OneSubtree = NULL;
hdtnRoot[iTc][iTh] = hdtnCurrentNode;
for ( k = 0; k< iLASTK[iTc][iTh] ; k++)
{
hdtnCurrentNode = hdtnRoot[iTc][iTh];
iCodeLength = iEHUFSI[iTc][iTh][k];
for ( i = 0; i < iCodeLength ; i++)
{
if ( iEHUFCOB[iTc][iTh][k][i] == 0 )
{
if ( hdtnCurrentNode->ZeroSubtree != NULL )
hdtnCurrentNode = hdtnCurrentNode->ZeroSubtree;
else
{
hdtnNewNode = (stHuffmanDecodingTreeNode *) malloc(sizeof(struct stHuffmanDecodingTreeNode));
hdtnNewNode->iCategory = -1;
hdtnNewNode->ZeroSubtree = NULL;
hdtnNewNode->OneSubtree = NULL;
hdtnCurrentNode->ZeroSubtree = hdtnNewNode;
hdtnCurrentNode = hdtnNewNode;
}
}
else // iEHUFCOB[iTc][iTh][k][i] == 1
{
if ( hdtnCurrentNode->OneSubtree != NULL )
hdtnCurrentNode = hdtnCurrentNode->OneSubtree;
else
{
hdtnNewNode = (stHuffmanTreeDecodingNode *) malloc(sizeof(struct stHuffmanDecodingTreeNode));
hdtnNewNode->iCategory = -1;
hdtnNewNode->ZeroSubtree = NULL;
hdtnNewNode->OneSubtree = NULL;
hdtnCurrentNode->OneSubtree = hdtnNewNode;
hdtnCurrentNode = hdtnNewNode;
}
}
}
hdtnCurrentNode->iCategory = k;
}
}
在 Rex.jpg 這張影像中, DC 係數的第 1 個 Huffman table (for luminance component) 為
Category Length HUFFCODE Code word
0 3 6 110
1 3 5 101
2 3 3 011
3 3 2 010
4 3 0 000
5 3 1 001
6 3 4 100
7 4 14 1110
8 5 30 11110
9 6 62 111110
10 7 126 1111110
11 8 254 11111110
經過上述的程式所產生的 Decoding Tree 顯示在下圖, leaf node 中的紅色數字代表 category。
下圖每一個 node 中的籃色數字則是代表各個節點的產生順序。
注意: 上述程式為了程式的可讀性, 用了全型的空白" "來控制部落格文章的內縮顯示。因此, 如果你要直接複製上述程式到 C++ Builder 執行, 請務必將全型空白" "改成半型空白" ", 否則, 編譯時發出現以下的錯誤訊息:
[C++ Error] Unit1.cpp(40): E2206 Illegal character ' ' (0xa140)
Saturday, September 22, 2007
Sampling in JPEG Images
(a) Source image with multiple components
規格書 P.25 的 Figure A.1 Source image characteristics, , 如果你仔細觀察, 圖 (a) 共有 Nf 個 components, 用 Ci 來辨識。每個 component 的大小是可以不相同, 分別用 xi, yi 來表示。
(b) Characteristics of an image component
圖(b) 則是說明了各個變數所代表的意義。
定義 X 為 xi 的最大值, Y 為 yi 的最大值, X, Y 的值儲存在 frame header 之中。每個component的大小不同, 代表 JPEG 可以用不同的 sampling factors 來對不同的 components 做 sampling process。Hi 代表水平取樣參數( horizontal sampling factor ), Vi 代表垂直取樣參數( vertical sampling factor ) 也是同樣儲存於 frame header 之中。
注意: xi 與 yi 並沒有儲存在 frame header 之中, JPEG Decoder 必須透過下列公式來計算出正確的 xi 與 yi :
xi = ceiling function( X × ( Hi / Hmax )) ;
yi = ceiling function( Y × ( Vi / Vmax )) ;
規格書 P. 24 有一個例子, 如下:
假設有一張具有 3 個 components的影像, 3個 components 之中, 最多的有 512 lines, 每個 line 最多具有 512 個 samples。所以
Y = 512, X = 512;
3 個 components 的 sampling factors 分別為:
Component 0 H0 = 4, V0 = 1
Component 1 H1 = 2, V1 = 2
Component 2 H2 = 1, V2 = 1
因此, Hmax = 4, Vmax = 2。所以根據上述公式計算得到
Component 0 x0 = 512, y0 = 256
Component 1 x1 = 256, y1 = 512
Component 2 x2 = 128, y2 = 256
Sunday, August 26, 2007
Marker Code Assignment in JPEG files
規格書 P. 32 的 Table B.1 列出了所有的 JPEG 可能使用到的 Marker。JPEG 的 Marker Segments 就是由一個 Marker 後面連接著一串相關的參數。
Restart Interval in JPEG files
這個圖是出現在規格書 P.43, Figure B.9 - Restart interval definition syntax。
DRI: Define restart interval marker
從規格書 Table B.1 中可以查到 DRI marker 的 code assignments 是 X'FFDD', 在 Rex.pdf 文件中, DRI marker 是出現在 P.23, address 00003586h。
Lr: Define restart interval segment length
從規格書 Table B.8 可以看到 Lr 的值永遠為 4 , 表示 DRI segment 的長度是固定為 4。
Ri: Restart interval - Specifies the number of MCU in the restart interval.
Ri 指出在這個 Restart interval 中, Entropy-coded segment (ECS) 包含多少個 MCUs。
在 Rex.pdf 文件中, P.23 的 Ri 為 X'000F', 表示 ECS 包含了 15 個 MCUs。
Thursday, August 23, 2007
Frame Header in JPEG files
Frame header 出現在 frame 資料的最前端, 主要指明:
1. the source image characteristics,
來源影像的一些特性, 如長、寬等。
2. the components in the frame,
來源影像由多少個 components 組成。
3. the sampling factors for each component,
每一個 component 的取樣因數。
4. the destination from which the quantized tables to be used with each component are retrieved.
每一個 quantization table 都有一個 destination identifier, 當我們要指明某個 component 要使用哪一個 quantization table 來作量化處理時, 就是在 frame header 中指明該 table 的 destination identifier。
這個圖是出現在規格書 P. 35 的 Figure B.3 Frame header syntax。
SOFn: Start of Frame marker,
利用 n 來指明屬於哪一種模式的壓縮方式, 詳細列表在規格書 P. 32 Table B.1 。
在 Rex.pdf 文件中, 你可以在 P. 23 , Address 00003573h 找到 X'FFC0', 換句話說, Rex.jpg 這張影像是屬於 Baseline DCT 的壓縮模式。
Lf: Frame Header Length
Frame header 的長度。在 Rex.pdf 中, Lf = 0011h, 因此共 17 Bytes。
P: Sample Precision
每一個 sample 用多少個 bits 來記錄其值。
P = 0008h, 表示每個 sample 用 8 bits 存。
Y: Number of lines
影像的高, Y = 0078h, Rex.jpg 影像高 120 pixels。
X: Number of samples per line
影像的寬, X = 0078h, Rex.jpg 影像寬 120 pixels。
Nf: Number of image component in frame
影像是由 Nf 個 components 所組成,
Rex.jpg 就是由 3 個 components 所組成的彩色影像。
在 Nf 參數之後的是 Nf 組 Component-specification parameters, 每一個 component 都有一組對應的參數來描述:
Ci: Component identifier
每一個 component 都有一個 identifier 來做識別代碼。
第 i 個 component 的 identifier 就是 Ci。
Hi: Horizontal sampling factor
第 i 個 component 的水平取樣參數。
Vi: Vertical sampling factor
第 i 個 component 的垂直取樣參數。
Tqi: Quantization table destination selector
指明第 i 個 component 是用哪一個 quantization table 來做量化處理。
在 Rex.jpg 這張影像中, 一共有 3 個 components, 因此共有 3 組的 Component-specification parameters, 分別如下:
C1 = 01, H1 = 1, V1 = 1, Tq1 = 00;
C2 = 02, H2 = 1, V2 = 1, Tq2 = 01;
C3 = 03, H3 = 1, V3 = 1, Tq3 = 01。
1. the source image characteristics,
來源影像的一些特性, 如長、寬等。
2. the components in the frame,
來源影像由多少個 components 組成。
3. the sampling factors for each component,
每一個 component 的取樣因數。
4. the destination from which the quantized tables to be used with each component are retrieved.
每一個 quantization table 都有一個 destination identifier, 當我們要指明某個 component 要使用哪一個 quantization table 來作量化處理時, 就是在 frame header 中指明該 table 的 destination identifier。
這個圖是出現在規格書 P. 35 的 Figure B.3 Frame header syntax。
SOFn: Start of Frame marker,
利用 n 來指明屬於哪一種模式的壓縮方式, 詳細列表在規格書 P. 32 Table B.1 。
在 Rex.pdf 文件中, 你可以在 P. 23 , Address 00003573h 找到 X'FFC0', 換句話說, Rex.jpg 這張影像是屬於 Baseline DCT 的壓縮模式。
Lf: Frame Header Length
Frame header 的長度。在 Rex.pdf 中, Lf = 0011h, 因此共 17 Bytes。
P: Sample Precision
每一個 sample 用多少個 bits 來記錄其值。
P = 0008h, 表示每個 sample 用 8 bits 存。
Y: Number of lines
影像的高, Y = 0078h, Rex.jpg 影像高 120 pixels。
X: Number of samples per line
影像的寬, X = 0078h, Rex.jpg 影像寬 120 pixels。
Nf: Number of image component in frame
影像是由 Nf 個 components 所組成,
Rex.jpg 就是由 3 個 components 所組成的彩色影像。
在 Nf 參數之後的是 Nf 組 Component-specification parameters, 每一個 component 都有一組對應的參數來描述:
Ci: Component identifier
每一個 component 都有一個 identifier 來做識別代碼。
第 i 個 component 的 identifier 就是 Ci。
Hi: Horizontal sampling factor
第 i 個 component 的水平取樣參數。
Vi: Vertical sampling factor
第 i 個 component 的垂直取樣參數。
Tqi: Quantization table destination selector
指明第 i 個 component 是用哪一個 quantization table 來做量化處理。
在 Rex.jpg 這張影像中, 一共有 3 個 components, 因此共有 3 組的 Component-specification parameters, 分別如下:
C1 = 01, H1 = 1, V1 = 1, Tq1 = 00;
C2 = 02, H2 = 1, V2 = 1, Tq2 = 01;
C3 = 03, H3 = 1, V3 = 1, Tq3 = 01。
Sunday, August 19, 2007
JPEG High-level Syntax
這是 JPEG 規格書 P. 34 所提供的語法圖(Figure B.2), 如果想看懂 JPEG 儲存格式, 然後寫一個 JPEG Decoder, 可以從看懂這個圖開始著手。
由上而下的第一層告訴我們: JPEG Compressed image data 最前面必須有一個 SOI marker, 最後面則是 EOI marker, 中間的資料則是 Frame, 一張影像其實就是一個 Frame。所謂的 SOI, 就是 Start of image 的縮寫, 在規格書 P. 32 Table B.1 中, 可以查到 SOI 的 Code Assignment 是 X'FFD8'。同樣地, EOI 就是 End of Image 的縮寫, Code Assignment 則是 X'FFD9'。
將左圖 Rex.jpg 用 UltraEdit 開啟, 就可以看到 Rex.pdf 這份文件中的資料。資料的最前與最後, 分別就是 X'FFD8' 與 X'FFD9'。第二層指出 Frame 的主要組成是由 frame header 和 scan 資料, frame header 之前也可以放置一些會使用到的相關表格, 如 Quantization tables, Huffman tables 或是其他相關資料, 規格書的 Figure B.5 有詳細列表。
至於一個 frame 包含多少個 scans, 則要視對影像資料的編碼次序(encoding order)而定, 編碼次序分成 interleaved 或 non-interleaved 兩種, 在規格書 P. 20 的 Figure 12 及 Figure 13 可以很清楚地看出什麼是一個 scan。
第三層指出 scan 的組成為何? 最前端同樣可以存放相關表格與資料, 接著存放的是 scan header, 然後就是一個接著一個, 中間夾著 Restart marker (RSTm) 的 Entropy-coded segments (ECS)。
第四層則是說明 Entropy-coded segment 是由多個 minimum coded unit (MCU)所組成。每一個 ECS 至少包含 Ri 個 MCU。注意: Ri 是在前面的 Define restart interval (DRI) segment 中被定義的。( Rex.jpg 影像中的 Entropy-coded segment )
Monday, August 13, 2007
Huffman Table Generating Procedures
在了解 JPEG 影像檔如何儲存 Huffman tables 之後, 接下來就是要將儲存在檔頭 (header) 的參數(paremeters) 轉換成解壓縮時能用的 Huffman tables。
JPEG 規格書 的 Annex C , 提供了一套完整的作法。
整個演算法包含三個程序:
1. Figure C.1 : generates a table of Huffman code sizes.
Goal: 讀取儲存在 JPEG 檔頭中的 BITS list, 將其轉換成儲存每個 Huffman code 的長度。
input: BITS list
output: HUFFSIZE table
以 Rex.jpg 的第 1 個 Huffman table 為例,
BITS 為 0, 0, 7, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0
HUFFSIZE 應該為 3, 3, 3, 3, 3, 3, 3, 4, 5, 6, 7, 8
Figure C.1 的對應程式碼如下:
k=0;
for (i=1 ; i<17 ; i++)
{
for (j=0 ; j<iBITS[iTc][iTh][i]; j++)
{
iHUFFSIZE[iTc][iTh][k] = i;
k++;
}
}
iHUFFSIZE[iTc][iTh][k] = 0;
iLASTK[iTc][iTh] = k;
//由於一共有 4 個 tables 需要處理, 因此我宣告三維陣列來分別儲存這些資料
2. Figure C.2 : generates the Huffman codes from the table built in the Figure C.1.
Goal: 根據 HUFFSIZE 所記錄的長度, 產生相對應的 HUFFCODE
input: table HUFFSIZE
output: table HUFFCODE
同樣以 Rex.jpg 的第 1 個 Huffman table 為例,
HUFFSIZE 為 3, 3, 3, 3, 3, 3, 3, 4, 5, 6, 7, 8
HUFFCODE 應該為 0, 1, 2, 3, 4, 5, 6, 14, 30, 62, 126, 254
Figure C.2 的對應程式碼如下:
k=0;
iCODE = 0;
iSI = iHUFFSIZE[iTc][iTh][0];
do {
do {
iHUFFCODE[iTc][iTh][k] = iCODE;
iCODE++;
k++;
}
while (iHUFFSIZE[iTc][iTh][k] == iSI);
if (iHUFFSIZE[iTc][iTh][k]!=0)
{
do {
iCODE = iCODE << 1;
iSI++;
}
while (iHUFFSIZE[iTc][iTh][k]! = iSI);
}
}
while (iHUFFSIZE[iTc][iTh][k] != 0);
3. Figure C.3 : generates the Huffman codes in symbol value order.
Goal: 將 C.2 Procedure 所產生的 HUFFCODE 依照 HUFFVAL 的次序排列。
input: HUFFCODE, HUFFSIZE, HUFFVAL
output: ordered HUFFCODE, ordered HUFFSIZE
Rex.jpg 的第 1 個 Huffman table,
HUFFCODE 為 0, 1, 2, 3, 4, 5, 6, 14, 30, 62, 126, 254
HUFFVAL 為 04, 05, 03, 02, 06, 01, 00, 07, 08, 09, 0A, 0B
因此, 排序過的 HUFFCODE 為 6, 5, 3, 2, 0, 1, 4, 14, 30, 62, 126, 254
Figure C.3 的對應程式碼如下:
for (k=0;k<iLASTK[iTc][iTh];k++)
{
i = ucHUFFVAL[k];
iEHUFCO[iTc][iTh][i]=iHUFFCODE[iTc][iTh][k];
iEHUFSI[iTc][iTh][i]=iHUFFSIZE[iTc][iTh][k];
}
除此之外, 由於在解壓縮時, 我們所接收的 input 是 binary data,
因此, 光有 HUFFCODE 是無法進行解碼的,
必須配合 HUFFSIZE 進一步將 HUFFCODE 變成二進位模式,
如同規格書 K.3.1 (P.149) 的 Code word一般。
將 HUFFCODE 轉換成二進位形式之對應程式碼如下:
for (k=0;k<256;k++)
{
iCodeLength = iEHUFSI[iTc][iTh][k];
iCodeValue = iEHUFCO[iTc][iTh][k];
for (i=iCodeLength-1;i>=0;i--)
{
iEHUFCOB[iTc][iTh][k][i] = iCodeValue % 2;
iCodeValue = iCodeValue / 2;
}
}
Rex.jpg 的第 1 個 Huffman table 為
Category Length HUFFCODE Code word
0 3 6 110
1 3 5 101
2 3 3 011
3 3 2 010
4 3 0 000
5 3 1 001
6 3 4 100
7 4 14 1110
8 5 30 11110
9 6 62 111110
10 7 126 1111110
11 8 254 11111110
Saturday, August 11, 2007
Huffman Tables in JPEG Files
在 JPEG 影像壓縮標準中, DCT係數經過量化( quantization )後, 會使用熵編碼( entropy coding )來做更進一步的資料壓縮處理。在JPEG壓縮中, 熵編碼最常使用的技術就是霍夫曼編碼技術(Huffman coding)。因此, 在每一個 JPEG 影像壓縮檔 ( *.jpg ) 的檔頭中, 都會定義 Huffman table, 而 X'FFC4' 就是 Define Huffman table(s) - DHT 的 marker。當我們在 JPEG 影像檔頭中搜尋到 X'FFC4', 這表示接下來的資料就是在解壓縮時, 會用到的 Huffman table。
Huffman Table 的儲存語法在規格書 B.2.4.2 有完整說明, 這邊我們則再進一步解釋, 讓大家更容易看懂規格書。
Lh: Huffman table definition length.
用 16 bits 來記錄整個規格書中, 所有 Huffman table 的總長度。
Tc: Table class - 0 = DC table or lossless table, 1 = AC table.
有些 table 是給 DC 係數壓縮用的, 有些則是用來壓縮 AC 係數, 因此用 4 bits 來區分。
Th: Huffman table destination identifier
影像中不同的 component 通常會使用不同的 table 來處理, 因此這邊用 4 bits 來讓這些 tables 有所區分。
Li: Number of Huffman codes of length i - Specifies the number of Huffman codes for each of the 16 possible lengths allowed by this Specification. Li’s are the elements of the list BITS.
由於 Huffman coding 所編出來的碼, 並不是固定長度的(fixed-length), JPEG 壓縮標準所使用的最長編碼為 16, 因此, L1 就是紀錄長度為 1 的碼有幾個, L2 就是紀錄長度為 2 的碼有幾個,... 每個 Li 使用 8 bits 來記錄, 一共有 16 bytes。在規格書 Annex C 中, 用一個 list BITS 來儲存 Li。將 16 個 Li 值加總起來, 就是所有 Huffman codes 的總數。
Vi,j: Value associated with each Huffman code – Specifies, for each i, the value associated with each Huffman code of length i. The meaning of each value is determined by the Huffman coding model. The Vi,j’s are the elements of the list HUFFVAL.
每一個 Huffman code 都有一個 Symbol Value 相對應, 利用這些 Value 就可以將所產生 Huffman Codes 用 Figure C.3 的演算法 做正確的排序。在 Annex C 中, 用一個 list HUFFVAL 來儲存這些 Symbol Value。
實例:
上圖是一張大小為 120*120 的 JPEG 影像, Rex.pdf 是將檔案內容以16進位的方式列印出來的結果。
我們如果在 Rex.pdf 中搜尋 "FF C4" 字串, 會分別在 address 00000215h (Page 1), 0000153ah (Page 9), 0000358ch (Page 23) 等三處找到 "FF C4" 字串。根據規格書中的 Table B.1 Marker Code Assignment 所列出來的 Marker 研判, 前面二個 FFC4 是屬於 Application Segments 的範圍, 只有第三個 "FFAC" 才是用來壓縮影像本身的 Huffman table。在這個例子中, Lh = 01A2, 一共有 418 bytes, 一共包含 4 個 Huffman tables, 前 2 個 tables 的 Tc = 0, 屬於 DC tables, 後 2 個 tables 的 Tc = 1, 屬於 AC tables。
第 1 個 table 的 Tc = 0, Th = 0,
L1 = 0, L2 = 0, L3 = 7, L4 = 1, L5 = 1, L6 = 1, L7 = 1, L8 = 1,
L9 = 0, L10 = 0, L11 = 0, L12 = 0, L13 = 0, L14 = 0, L15 = 0, L16 = 0。
一共有 7 + 1 + 1 + 1 + 1 + 1 = 12 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為 04, 05, 03, 02, 06, 01, 00, 07, 08, 09, 0A, 0B。
第 2 個 table 的 Tc = 0, Th = 1,
L1 = 0, L2 = 2, L3 = 2, L4 = 3, L5 = 1, L6 = 1, L7 = 1, L8 = 1,
L9 = 1, L10 = 0, L11 = 0, L12 = 0, L13 = 0, L14 = 0, L15 = 0, L16 = 0。
一共有 2 + 2 + 3 +1 + 1 + 1 + 1 + 1 = 12 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為 01, 00, 02, 03, 04, 05, 06, 07, 08, 09, 0A, 0B。
第 3 個 table 的 Tc = 1, Th = 0,
L1 = 0, L2 = 2, L3 = 1, L4 = 3, L5 = 3, L6 = 2, L7 = 4, L8 = 2,
L9 = 6, L10 = 7, L11 = 3, L12 = 4, L13 = 2, L14 = 6, L15 = 2, L16 = 73。
注意: L16 = 73, 是 16 進位值, 所以實際應該為 7 * 16 + 3 = 115
一共有 2 + 1 + 3 + 3 + 2 + 4 + 2 + 6 + 7 + 3 + 4 + 2 + 6 + 2 + 115 = 162 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為:
01, 02, 03, 11, 04, 00, 05, 21, 12, 31, 41, 51, 06, 13, 61, 22,
71, 81, 14, 32, 91, A1, 07, 15, B1, 42, 23, C1, 52, D1, E1, 33,
16, 62, F0, 24, 72, 82, F1, 25, 43, 34, 53, 92, A2, B2, 63, 73,
C2, 35, 44, 27, 93, A3, B3, 36, 17, 54, 64, 74, C3, D2, E2, 08,
26, 83, 09, 0A, 18, 19, 84, 94, 45, 46, A4, B4, 56, D3, 55, 28,
1A, F2, E3, F3, C4, D4, E4, F4, 65, 75, 85, 95, A5, B5, C5, D5,
E5, F5, 66, 76, 86, 96, A6, B6, C6, D6, E6, F6, 37, 47, 57, 67,
77, 87, 97, A7, B7, C7, D7, E7, F7, 38, 48, 58, 68, 78, 88, 98,
A8, B8, C8, D8, E8, F8, 29, 39, 49, 59, 69, 79, 89, 99, A9, B9,
C9, D9, E9, F9, 2A, 3A, 4A, 5A, 6A, 7A, 8A, 9A, AA, BA, CA, DA,
EA, FA。
第 4 個 table 的 Tc = 1, Th = 1,
L1 = 0, L2 = 2, L3 = 2, L4 = 1, L5 = 2, L6 = 3, L7 = 5, L8 = 5,
L9 = 4, L10 = 5, L11 = 6, L12 = 4, L13 = 8, L14 = 3, L15 = 3, L16 = 6D。
注意: L16 = 6D, 是 16 進位值, 所以實際應該為 6 * 16 + 13 = 109
一共有 2 + 2 + 1 + 2 + 3 + 4 + 5 + 4 + 5 + 6 + 4 + 8 + 3 + 3 + 109 = 162 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為:
01, 00, 02, 11, 03, 04, 21, 12, 31, 41, 05, 51, 13, 61, 22, 06,
71, 81, 91, 32, A1, B1, F0, 14, C1, D1, E1, 23, 42, 15, 52, 62,
72, F1, 33, 24, 34, 43, 82, 16, 92, 53, 25, A2, 63, B2, C2, 07,
73, D2, 35, E2, 44, 83, 17, 54, 93, 08, 09, 0A, 18, 19, 26, 36,
45, 1A, 27, 64, 74, 55, 37, F2, A3, B3, C3, 28, 29, D3, E3, F3,
84, 94, A4, B4, C4, D4, E4, F4, 65, 75, 85, 95, A5, B5, C5, D5,
E5, F5, 46, 56, 66, 76, 86, 96, A6, B6, C6, D6, E6, F6, 47, 57,
67, 77, 87, 97, A7, B7, C7, D7, E7, F7, 38, 48, 58, 68, 78, 88,
98, A8, B8, C8, D8, E8, F8, 39, 49, 59, 69, 79, 89, 99, A9, B9,
C9, D9, E9, F9, 2A, 3A, 4A, 5A, 6A, 7A, 8A, 9A, AA, BA, CA, DA,
EA, FA。
延伸閱讀:
1. Huffman Table Generating Procedures
2. Huffman Tables in the Rex.jpg
Huffman Table 的儲存語法在規格書 B.2.4.2 有完整說明, 這邊我們則再進一步解釋, 讓大家更容易看懂規格書。
Lh: Huffman table definition length.
用 16 bits 來記錄整個規格書中, 所有 Huffman table 的總長度。
Tc: Table class - 0 = DC table or lossless table, 1 = AC table.
有些 table 是給 DC 係數壓縮用的, 有些則是用來壓縮 AC 係數, 因此用 4 bits 來區分。
Th: Huffman table destination identifier
影像中不同的 component 通常會使用不同的 table 來處理, 因此這邊用 4 bits 來讓這些 tables 有所區分。
Li: Number of Huffman codes of length i - Specifies the number of Huffman codes for each of the 16 possible lengths allowed by this Specification. Li’s are the elements of the list BITS.
由於 Huffman coding 所編出來的碼, 並不是固定長度的(fixed-length), JPEG 壓縮標準所使用的最長編碼為 16, 因此, L1 就是紀錄長度為 1 的碼有幾個, L2 就是紀錄長度為 2 的碼有幾個,... 每個 Li 使用 8 bits 來記錄, 一共有 16 bytes。在規格書 Annex C 中, 用一個 list BITS 來儲存 Li。將 16 個 Li 值加總起來, 就是所有 Huffman codes 的總數。
Vi,j: Value associated with each Huffman code – Specifies, for each i, the value associated with each Huffman code of length i. The meaning of each value is determined by the Huffman coding model. The Vi,j’s are the elements of the list HUFFVAL.
每一個 Huffman code 都有一個 Symbol Value 相對應, 利用這些 Value 就可以將所產生 Huffman Codes 用 Figure C.3 的演算法 做正確的排序。在 Annex C 中, 用一個 list HUFFVAL 來儲存這些 Symbol Value。
實例:
上圖是一張大小為 120*120 的 JPEG 影像, Rex.pdf 是將檔案內容以16進位的方式列印出來的結果。
我們如果在 Rex.pdf 中搜尋 "FF C4" 字串, 會分別在 address 00000215h (Page 1), 0000153ah (Page 9), 0000358ch (Page 23) 等三處找到 "FF C4" 字串。根據規格書中的 Table B.1 Marker Code Assignment 所列出來的 Marker 研判, 前面二個 FFC4 是屬於 Application Segments 的範圍, 只有第三個 "FFAC" 才是用來壓縮影像本身的 Huffman table。在這個例子中, Lh = 01A2, 一共有 418 bytes, 一共包含 4 個 Huffman tables, 前 2 個 tables 的 Tc = 0, 屬於 DC tables, 後 2 個 tables 的 Tc = 1, 屬於 AC tables。
第 1 個 table 的 Tc = 0, Th = 0,
L1 = 0, L2 = 0, L3 = 7, L4 = 1, L5 = 1, L6 = 1, L7 = 1, L8 = 1,
L9 = 0, L10 = 0, L11 = 0, L12 = 0, L13 = 0, L14 = 0, L15 = 0, L16 = 0。
一共有 7 + 1 + 1 + 1 + 1 + 1 = 12 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為 04, 05, 03, 02, 06, 01, 00, 07, 08, 09, 0A, 0B。
第 2 個 table 的 Tc = 0, Th = 1,
L1 = 0, L2 = 2, L3 = 2, L4 = 3, L5 = 1, L6 = 1, L7 = 1, L8 = 1,
L9 = 1, L10 = 0, L11 = 0, L12 = 0, L13 = 0, L14 = 0, L15 = 0, L16 = 0。
一共有 2 + 2 + 3 +1 + 1 + 1 + 1 + 1 = 12 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為 01, 00, 02, 03, 04, 05, 06, 07, 08, 09, 0A, 0B。
第 3 個 table 的 Tc = 1, Th = 0,
L1 = 0, L2 = 2, L3 = 1, L4 = 3, L5 = 3, L6 = 2, L7 = 4, L8 = 2,
L9 = 6, L10 = 7, L11 = 3, L12 = 4, L13 = 2, L14 = 6, L15 = 2, L16 = 73。
注意: L16 = 73, 是 16 進位值, 所以實際應該為 7 * 16 + 3 = 115
一共有 2 + 1 + 3 + 3 + 2 + 4 + 2 + 6 + 7 + 3 + 4 + 2 + 6 + 2 + 115 = 162 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為:
01, 02, 03, 11, 04, 00, 05, 21, 12, 31, 41, 51, 06, 13, 61, 22,
71, 81, 14, 32, 91, A1, 07, 15, B1, 42, 23, C1, 52, D1, E1, 33,
16, 62, F0, 24, 72, 82, F1, 25, 43, 34, 53, 92, A2, B2, 63, 73,
C2, 35, 44, 27, 93, A3, B3, 36, 17, 54, 64, 74, C3, D2, E2, 08,
26, 83, 09, 0A, 18, 19, 84, 94, 45, 46, A4, B4, 56, D3, 55, 28,
1A, F2, E3, F3, C4, D4, E4, F4, 65, 75, 85, 95, A5, B5, C5, D5,
E5, F5, 66, 76, 86, 96, A6, B6, C6, D6, E6, F6, 37, 47, 57, 67,
77, 87, 97, A7, B7, C7, D7, E7, F7, 38, 48, 58, 68, 78, 88, 98,
A8, B8, C8, D8, E8, F8, 29, 39, 49, 59, 69, 79, 89, 99, A9, B9,
C9, D9, E9, F9, 2A, 3A, 4A, 5A, 6A, 7A, 8A, 9A, AA, BA, CA, DA,
EA, FA。
第 4 個 table 的 Tc = 1, Th = 1,
L1 = 0, L2 = 2, L3 = 2, L4 = 1, L5 = 2, L6 = 3, L7 = 5, L8 = 5,
L9 = 4, L10 = 5, L11 = 6, L12 = 4, L13 = 8, L14 = 3, L15 = 3, L16 = 6D。
注意: L16 = 6D, 是 16 進位值, 所以實際應該為 6 * 16 + 13 = 109
一共有 2 + 2 + 1 + 2 + 3 + 4 + 5 + 4 + 5 + 6 + 4 + 8 + 3 + 3 + 109 = 162 個 codes。
每一個 code 所對應的 HUFFVAL 依序分別為:
01, 00, 02, 11, 03, 04, 21, 12, 31, 41, 05, 51, 13, 61, 22, 06,
71, 81, 91, 32, A1, B1, F0, 14, C1, D1, E1, 23, 42, 15, 52, 62,
72, F1, 33, 24, 34, 43, 82, 16, 92, 53, 25, A2, 63, B2, C2, 07,
73, D2, 35, E2, 44, 83, 17, 54, 93, 08, 09, 0A, 18, 19, 26, 36,
45, 1A, 27, 64, 74, 55, 37, F2, A3, B3, C3, 28, 29, D3, E3, F3,
84, 94, A4, B4, C4, D4, E4, F4, 65, 75, 85, 95, A5, B5, C5, D5,
E5, F5, 46, 56, 66, 76, 86, 96, A6, B6, C6, D6, E6, F6, 47, 57,
67, 77, 87, 97, A7, B7, C7, D7, E7, F7, 38, 48, 58, 68, 78, 88,
98, A8, B8, C8, D8, E8, F8, 39, 49, 59, 69, 79, 89, 99, A9, B9,
C9, D9, E9, F9, 2A, 3A, 4A, 5A, 6A, 7A, 8A, 9A, AA, BA, CA, DA,
EA, FA。
延伸閱讀:
1. Huffman Table Generating Procedures
2. Huffman Tables in the Rex.jpg
Friday, December 01, 2006
JPEG Standard
This CCITT Recommendation | ISO/IEC International Standard was prepared by CCITT Study Group VIII and the Joint Photographic Experts Group (JPEG) of ISO/IEC JTC 1/SC 29/WG 10. This Experts Group was formed in 1986 to establish a standard for the sequential progressive encoding of continuous tone grayscale and colour images.
CCITT Rec. T.81 (1992 E)
INFORMATION TECHNOLOGY – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES
CCITT Rec. T.81 (1992 E)
INFORMATION TECHNOLOGY – DIGITAL COMPRESSION AND CODING OF CONTINUOUS-TONE STILL IMAGES – REQUIREMENTS AND GUIDELINES
Monday, October 23, 2006
JPHIDE and JPSEEK Offical Website
1999年 8 月推出的 JPHIDE and JPSEEK,
作者: Allan Latham ( alatham@flexsys-group.com ),
官方網站網址: http://linux01.gwdg.de/~alatham/stego.html。
在官網中, 作者對於這個隱藏軟體的描述如下:
1. JPHS 0.3 是 Linux 版本, Download: JPHS 0.3 & Signature
2. JPHS 0.5 則是 Window 版本, Download: JPHS 0.5
JPHS 0.5 的執行畫面如下:
作者: Allan Latham ( alatham@flexsys-group.com ),
官方網站網址: http://linux01.gwdg.de/~alatham/stego.html。
在官網中, 作者對於這個隱藏軟體的描述如下:
JPHIDE and JPSEEK are programs which allow you to hide a file in a jpeg visual image. There are lots of versions of similar programs available on the internet but JPHIDE and JPSEEK are rather special. The design objective was not simply to hide a file but rather to do this in such a way that it is impossible to prove that the host file contains a hidden file. Given a typical visual image, a low insertion rate (under 5%) and the absence of the original file, it is not possible to conclude with any worthwhile certainty that the host file contains inserted data. As the insertion percentage increases the statistical nature of the jpeg coefficients differs from "normal" to the extent that it raises suspicion. Above 15% the effects begin to become visible to the naked eye. Of course some images are much better than others when used a host file - plenty of fine detail is good. A cloudless blue sky over a snow covered ski paradise is bad. A waterfall in a forest is probably ideal.其大意是這樣的:
JPHIDE and JPSEEK 是一個可以將檔案藏進 JPEG 影像的程式。在 Internet 上, 有許多類似程式及其各種版本, 然而, JPHIDE and JPSEEK 卻相當特別！JPHIDE and JPSEEK 的設計目的並不僅是簡單地隱藏檔案, 反而是進一步要表達: 要證明某張偽裝影像嵌有檔案是不可能的。給定一個嵌有低嵌入比例 (低於 5% ) 的影像, 在沒有原始影像的情況下, 並沒有辦法去判斷這張影像嵌有訊息的。當嵌入比例增加時, JPEG 係數的統計特性偏離了原來的正常範圍, 就會引起懷疑。超過 15% 的嵌入比例時, 對於影像品質的影響是肉眼可見的。當然, 擁有較多細節的影像是比較適合用來做掩護影像 ( host ) 的。例如: 一張藍天無雲的滑雪天堂的圖片, 就不太適合用來嵌入訊息; 在森林中瀑布拍攝的圖片就是一張理想的掩護影像。JPHIDE and JPSEEK 有兩個版本:
1. JPHS 0.3 是 Linux 版本, Download: JPHS 0.3 & Signature
2. JPHS 0.5 則是 Window 版本, Download: JPHS 0.5
JPHS 0.5 的執行畫面如下:
 |
| From StegoRN |
Steganographic Tools for JPEG Images
JPEG standard 是 Internet 上使用最廣泛的影像儲存格式。因此, 網路上也有許多隱藏軟體 ( steganographic software ) 可以將訊息藏到 JPEG 影像中, 然後透過 Internet 傳送秘密訊息。
Niels Provos & Peter Honeyman 在 2002 年 ISOC NDSS'02 研討會提出 " Detecting Steganographic Content on the Internet " 這篇論文, 文中 P.4 提到了三個在 Internet 上較普及的隱藏軟體。
Niels Provos and Peter Honeyman, "Detecting Steganographic Content on the Internet,"ISOC NDSS'02, San Diego, CA, February 2002.
Niels Provos & Peter Honeyman 在 2002 年 ISOC NDSS'02 研討會提出 " Detecting Steganographic Content on the Internet " 這篇論文, 文中 P.4 提到了三個在 Internet 上較普及的隱藏軟體。
There are three popular steganographic systems available on the Internet that hide information in JPEG images:
• JSteg, JSteg-ShellAll of these systems use some form of leastsignificant bit embedding and are detectable by statistical analysis except the latest release of OutGuess. In the following, we describe the specific characteristics of these systems and show how to detect them.
Niels Provos and Peter Honeyman, "Detecting Steganographic Content on the Internet,"ISOC NDSS'02, San Diego, CA, February 2002.
Subscribe to:
Posts (Atom)