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

　

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。
　

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。
　

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 )
　

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

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
　

Detecting LSB Steganography in Color and Gray-Scale Images (RS steganalysis)

Detecting LSB Steganography in Color and Gray-Scale Images
Jessica Fridrich, Miroslav Goljan, Rui Du
Magazine of IEEE Multimedia, Special Issue on Security,
October-November 2001, pp. 22-28.

這篇論文將一張影像中的連續像素切割成一個一個的 pixel group G = (x1, x2, ... xn)。
假設每一個 pixel group 的大小為 2*2, 那麼一張 384*256 大小的影像, 就會有 (384/2)*(256/2) = 24576 個 pixel groups。

針對每個 group, 根據其特性將會被分成 Regular, Singular, Unusable 等三類。用來分類的特性由兩個因素決定:

1. discrimination function f

discrimination function 的目的是評量一個 pixel group 的平坦性(smoothness) 或規則性(regularity)。一般來說, 如果 group 所包含的 noise 愈多, f(G) 就會越大。論文中舉了一個例子, 用相鄰兩個像素值差的總和, 當作 discrimination function 所得到值。

2. flipping: invertible operation F。

flipping 基本上是針對灰階值的一種排列方式(permutation), 且連坐兩次就會回復成原來的灰階值(2-cycles), 即 F(F(x)) = x。論文中定義了三種 flipping operation, 分別為 F1, F-1 及 F0。
The permutation F1: 0←→1, 2←→3, 4←→5, ..., 254 ←→ 255。
The permutation F-1: -1←→0, 1←→2, 3←→4, ..., 255←→256。
　F-1(x) = F1(x+1) -1 , for all x
The identity permutation F0:
　F0(x) = x, for all x

針對每一個 pixel group G, 首先計算 discrimination function f(G) 的值, 然後對 G 做 flipping operation F, 得到 F(G), 然後計算 f(F(G)), 藉由比較 f(G) 與 f(F(G)) 的大小關係, 就可以對 G 進行分類。

　Regular groups:　G 屬於 R <=> f(F(G)) > f(G)
　Singular groups:　G 屬於 R <=> f(F(G)) < f(G)　
　Unusable groups:　G 屬於 U <=> f(F(G)) = f(G)

F(G) 所代表的意思是針對 pixel group G = (x1, x2, ... xn) 中的每一個 xi, 都分別使用相同的 flipping operation F。要針對不同的 xi, 使用不同的 flipping operation F, 必須再提供一個 mask M 來指明。M 是一個 n-tuple 的向量, 每個值都由 -1, 0, 1 所組成。假設 n=4, M=( 0, 1, -1, 0),

FM(G) 所代表的意思就是:
對 x1 做 F0 的 flipping operation;
對 x2 做 F1 的 flipping operation;
對 x3 做 F-1 的 flipping operation;
對 x4 做 F0 的 flipping operation。

使用 FM 的用意是模擬不可逆雜訊干擾行為(invertible noise adding) 對 pixel values 的影響。

RM 表示在針對 FM , 影像中 regular group 數量所佔的百分比 (percent of all group);
SM 則是 singular group 數量所佔的百分比。因此,

　RM + SM ≤ 1　and　R-M + S-M ≤ 1 ( -M: negative mask )

針對作者所提出的方法, 有一個統計假設前提(statistical hypothesis)是:

　RM ~= R-M　and　SM ~= S-M









(未完待續)

News: 興大生化所教授張OO論文 國科會證實部分造假

新聞原文連結
(中時電子報 2007/06/29 04:39 記者 李宗祐 台北報導)

中興大學生物化學研究所教授張OO，去年十月在國際頂尖學術期刊《細胞》（Cell）發表論文，被檢舉涉嫌變造實驗數據及圖片，引發違反學術倫理風波。國科會歷經半年調查後，確認張OO發表的論文有部分實驗數據造假，裁定停權三年處分；由國科會補助經費正在執行中的研究計畫，也必須全面停止。

掛名學生 追回博士學位

張OO原是我國第一位在《細胞》發表論文的學者，但遭大陸學者質疑，也成為第一個被迫在國際知名期刊撤除論文的學者。

國科會日前召開學術倫理委員會，做成決議，張OO的停權處分追溯自今年元月生效，直至九十八年十二月卅一日為止。期間不得向國科會申請研究計畫補助，連同執行中的卓越計畫也必須全面停止；已審查通過、尚未申請經費補助的研究計畫，不得提出申請。

中興大學也完成內部懲處報告，限制張OO三年內不能升等，不能申請各項獎助。掛名論文第一作者的博士生助理（已畢業，正服役中），追回其博士學位，取消博士學歷資格。

張OO專注生化研究十多年，去年十月與他指導的博士生助理共同掛名，在《細胞》雜誌發表〈發現細菌基因轉錄起始因子作用〉論文，引起國際生物學界高度重視。沒想到，一個多月後，有大陸學者向另一國際知名期刊《科學》（Science）投書，質疑他的實驗數據和圖片經過變造、研究涉及造假。

重做實驗 數據果然不同

面對外界質疑，張OO否認造假，強調是負責實驗操作的博士生助理求好心切，做了些「美化圖片」。但他主動向《細胞》雜誌撤回論文，並要求國科會和中興大學給他三到六個月，重做實驗，提出數據證實研究未造假。

國科會高層官員證實，張OO日前完成重新實驗，把實驗報告交由中興大學五人專案小組審查。該校最近把調查報告呈報國科會學術論理委員會審查。官員表示，張OO重新實驗得出的數據，跟先前在《細胞》雜誌發表的論文不一樣，但還是可以推論出相同結論。但中興大學五人小組及國科會學術倫理委員會均認為，張OO先前發表的論文，確實有部分數據造假。

停權三年 張應不會申覆

官員表示，張OO的博士生助理接受調查時坦承，有些數據是他「自己弄上去的」，這種做法不是張OO說的「美化圖片」而已，而是更嚴重的造假。因此，國科會決定給予停權三年處分。據了解，張OO應該不會提出申覆。

相關新聞: 中興大學知名生化教授張OO撤銷 Cell 雜誌論文

關於 QIM 的點點滴滴(二): G. Wornell

Quantization Index Modulation: A Class of Provably Good Methods for Digital Watermarking and Information Embedding
IEEE Trans. on Information Theory, Vol. 47, No. 4, May 2001
Brian Chen, Gregory W. Wornell

這篇論文從 2001 年 5 月發表迄今(2007/6/29) , 總共被引用了 428 次 ( 在 Google 的學術搜尋上查到的數據 ), 顯示了此篇論文的重要性。

關於 QIM 的點點滴滴(一): H. Noda

High-performance JPEG steganography using quantization index modulation in DCT domain
Pattern Recognition Letters, Vol. 27 , Iss. 5 (April 2006)
Hideki Noda (野田 秀樹), Michiharu Niimi (新見 道治), Eiji Kawaguchi (河口 英二)


Hideki Noda 野田 秀樹

這篇 paper 的 Section 2 大致介紹了 Chen and Wornell 在 2001年 5 月在 IEEE Trans. on Information Theory 所提出的 QIM 嵌入技術。

QIM embedding 使用 2 個 quantizers 來取代原先用於 JPEG 壓縮程序的 1 個 quantizer, 分別用來嵌入 0 與 1。

假設某個 frequency 的 quantization step size 為 8, 那麼用來嵌入 0 的 quantizer 的 codebook C0 就是 2j*8 所形成的集合, j 屬於整數 Z = {... -2, -1, 0, 1, 2 ... }
C0 = { ... -32, -16, 0, 16, 32, ...}
而另一個用來嵌入 1 的 codebook C1 就是 (2j+1)*8 所形成的集合
C1 = { ... -40, -24, -8, 8, 24, 40, ...}

給定一個 DCT 係數 x, 如果要嵌入 0, DCT 係數就會被量化成 2q, 而 q 被定義成 C0 中最接近 x 的那個 code 所使用的 j 值。同樣地, 如果要嵌入 1, DCT 係數就會被量化成 2q+1。

我們用例子說明, 假設 x 為 19, 要嵌入的訊息為 0, 由於 codebook 中最接近 x 的 code 為 16, 而 16 所用的 j 值為 1, 因此 19 就被量化成 2。如果要嵌入的訊息為 1, 在 C1 中最接近的 code 為 24, 24 = (2j+1)*8, j=1=q , 所以 19 會被量化成 2q+1 = 3。

假設嵌入的二元資料中, 0 與 1 的個數是一樣多的, 使用 QIM embedding 嵌入資料前後, DCT 係數 histogram 的變化情況, 則是接下來的討論重點。

令 hi 表示範圍屬於 i-0.5 < x < i+0.5 的 DCT 係數的個數,
　 hi- 表示範圍屬於 i-0.5 < x < i 的 DCT 係數的個數,
　 hi+ 表示範圍屬於 i < x < i+0.5 的 DCT 係數的個數。

因此, hi = hi- + hi+

使用 QIM embedding 後, 令 hi' 為量化還原後 DCT 係數的個數, 原來的 hi 有一半並不會遭到嵌入更改原來的值, 而屬於 h(i-1)+ 的係數則是有一半會被嵌入更改變成屬於 hi 的範圍, 同理 h(i+1)- 也有一半變成 hi 的範圍。

因此, hi' = hi / 2 + ( h(i-1)+ + (h(i+1)- ) / 2
　
　

Null Cipher in Chinese Medicine History

From StegoRN

上個星期逛台北捷運的地下書街, 看到了這本《中醫藥典故與傳說》, 第七章的醫家軼聞, 我首先閱讀了我較為熟悉的醫聖張仲景部份, 其中有一個故事就是張仲景利用 Null Cipher 這樣的技術巧戲庸官, 故事中的方子如下:

柏子仁三錢
木瓜二錢
官桂二錢
柴胡三錢
益智二錢
附子二錢
八角二錢
人蔘一錢
台烏三錢
上党三錢
山藥二錢

S-Tools

Author: Andy Brown
Ver. 1.0 (1994), Ver. 2.0 (1994), Ver. 3.0 (1995), Ver. 4.0 (1996)

最早接觸到 S-Tools 這個隱藏軟體是從 Neil F. Johnson 1998 February 發表在 IEEE Computer 的文章 "Steganography: Seeing the Unseen", 文章中所使用的例子是將 CORONA 偵查衛星於1966/08/20 所拍攝的前蘇聯哈薩克戰略轟炸機基地空照圖 (Soviet strategic bomber base) 隱藏到印象派大師 Pierre-Auguste Renoir (1841-1919) 的畫作 Le Moulin de la Galette (1876) 之中, 讓我印象深刻。

Book: INFORMATION HIDING techniques for steganography and digital watermarking

From StegoRN

Editors: Stefan Katzenbeisser & Fabien A. P. Petitcolas
ARTECH HOUSE, Computer Security Series
ISBN 1-58053-035-4
(Available on Amazon.com)

This book surveys recent research results in the fields of watermarking and steganography, two disciplines generally referred to as information hiding. Included are chapters about the following topics:

* Chapter 1: Introduction to information hiding
(Fabien A. P. Petitcolas) gives an introduction to the field of information hiding, thereby discussing the history of steganography and watermarking and possible applications to modern communication systems.
* Chapter 2: Principles of steganography
(Stefan Katzenbeisser) introduces a model for steganographic communication (the ‘prisoners problem") and discusses various steganographic protocols (such as pure steganography, secret key steganography, public key steganography and supraliminal channels).
* Chapter 3: A survey of steganographic techniques
(Neil F. Johnson and Stefan Katzenbeisser) discusses several information hiding methods useable for steganographic communication, among them substitution systems, hiding methods in two-colour images, transform domain techniques, statistical steganography, distortion and cover generation techniques.
* Chapter 4: Steganalysis
(Neil F. Johnson) introduces the concepts of steganalysis – the task of detecting and possibly removing steganographic information. Included is also an analysis of common steganographic tools.
* Chapter 5: Introduction to watermarking techniques
(Martin Kutter and Frank Hartung) introduces the requirements and design issues for watermarking software. The authors also present possible applications for watermarks and discuss methods for evaluating watermarking systems.
* Chapter 6: A survey of current watermarking techniques
(Jean-Luc Dugelay and Stéphane Roche) presents several design principles for watermarking systems, among them the choice of host locations, psychovisual aspects, the choice of a workspace (DFT, DCT, wavelet), the format of the watermark bits (spread spectrum, low-frequency watermark design), the watermark insertion operator and optimizations of the watermark receiver.
* Chapter 7: Robustness of copyright marking systems
(Scott Craver, Adrian Perrig and Fabien A. P. Petitcolas) discusses the crucial issue of watermark robustness to intentional attacks. The chapter includes a taxonomy of possible attacks against watermarking systems, among them protocol attacks like inversion, oracle attacks, limitations of WWW spiders and system architecture issues.
* Chapter 8: Fingerprinting
(Jong-Hyeon Lee) discusses principles and applications of fingerprinting to the traitor tracing problem, among them statistical fingerprinting, asymmetric fingerprinting and anonymous fingerprinting.
* Chapter 9: Copyright on the Internet and watermarking
(Stanley Lai and Fabrizio Marongiu Buonaiuti) finally discusses watermarking systems from a legal point of view and addresses various other aspects of copyright law on the Internet.

IIH-MSP 2007

The third International Conference on Intelligent Information Hiding and Multimedia Signal Processing

November 26-28, 2007
Kaohsiung City, Taiwan
http://bit.kuas.edu.tw/~iihmsp07/

SCOPE: Topics of interest include, but are not limited to:
Track I: Information Hiding and Security
- Watermarking: techniques, attacks, protocols, applications
- Steganography and steganalysis: techniques, protocols, applications
- Cryptography and cryptanalysis: techniques, protocols, applications
- Data authentication issues and access control themes
- Broadcast and public-key encryption
- Forensic analysis and tracing traitors
- Digital rights management and legal aspect
- RFID security and home network privacy
- Platform integrity and trusted computing
- Systems engineering and development for information hiding & security
- VLSI/ASIC/FPGA/SOC design and implementation for information hiding & security
- Enabling technologies and emerging standards for information hiding & security

Track II: Multimedia Signal Processing and Networking
- Multimedia sensing and sensory systems Steganog
- Multimedia source coding and channel coding
- Multimedia signal analysis and visualization
- Multimedia signal mining and data fusion
- Multimedia networking and communication techniques (wired & wireless)
- Multimedia/multimodal signals interpretation and automatic recognition
- Multimedia databases and retrievals
- Multimedia hyperlink techniques and applications
- Advances in multimedia content description interface (e.g. MEPG-7)
- Advances in multimedia framework: (e.g. MPEG-21)
- Advances in multimedia framework: (e.g. MPEG-21)
- Systems engineering and development for multimedia systems
- VLSI/ASIC/FPGA/SOC design and implementations for multimedia systems
- Enabling technologies and emerging standards for multimedia applications

Track III: Bio-Inspired Multimedia Technologies and Systems
- Artificial neural networks for multimedia processing: models, learning paradigms, architectures, and implementations
- Fuzzy systems and evolutionary computing for intelligent multimedia processing
- Human-machine multimodal interaction: e.g. face/speech recognition, facial expression and emotion categorization, gesture analysis and recognition, etc.

Important Dates
The deadline for paper submission May 1, 2007
The date for notification July 1, 2007
The date for camera-ready paper submission August 1, 2007

Call For Papers

ICICIC 2007

昨天幾個同事和熟悉歐洲旅遊的蕭桂芳老師(英國曼徹斯特大學畢業)談過後, 覺得 CAIP 2007 所在地奧地利維也納並不是英語系國家, 對我們來說, 要找到配合會議的旅行團, 還有自助旅行都不是件容易的事。因此, 就決定把目標改成 ICICIC 2007 了,...

ICICIC 2007
The Second International Conference on
Innovative Computing, Information and Control
September 5 - 7, 2007
Kumamoto City International Center, Kumamoto, Japan
熊本 . 九州 . 日本

Innovative Computing and Information
* Signal and Image Processing
* Speech and Audio Processing
* Image and Video Coding and Transmission
* Video Processing and Analysis
* Image Video Storage
* Retrieval and Multimedia
* Digital Watermarking and DRM
* Artificial Intelligence
* Computing and Intelligent Systems
* Machine Learning
* Biometric and Biomedical Applications
* Sensor and Neural Networks
* Knowledge Discovery and Data Mining
* Others

Intelligent System and Control
* Fuzzy Mathematics and Applications
* Fuzzy Systems Modeling and Analysis
* Knowledge-based Systems
* Hybrid Systems Modeling and Design
* Fault Detection and Identification
* Optimization and Decision Making
* Control Systems and Applications
* Systems Identification
* Risk Analysis and Management
* Modeling and Simulation Techniques
* Others

Important Dates
Deadline for paper submission ------ March 10, 2007
Notification of acceptance ------ April 10, 2007
Camera-ready manuscript Submission ------ April 30, 2007

Call For Papers

　

CAIP 2007

今天下午和實驗室老師討論的結果, 決定今年暑假要參加的學術研討會鎖定為由 IAPR 所主辦的 CAIP 2007。
現在目標已經設定了, 接下來就要衝了...


The 12th International Conference on Computer Analysis of Images and Patterns
August 27th - August 29th, 2007
Vienna, Austria

Paper submission deadline:	March 30th, 2007
Notification of Acceptance:	May 14th, 2007
Camera ready paper:	June 4th, 2007

Call For Papers

News: 中興大學知名生化教授張OO撤銷 Cell 雜誌論文

（自由時報 2006/12/16 記者蘇孟娟 台中報導）
新聞原文連結

中國留美學生檢舉

中興大學生化所教授張OO一篇「發現細菌基因轉錄起始因子作用」的研究論文，十月獲世界頂尖生物學雜誌Cell刊登；日前一名留美中國學生舉發，其中圖片有人為修改痕跡。興大組成跨校專業委員會審理後，認定張OO須為不當圖片操作負責；張OO十五日指出，所有研究均是真實結果，但為回歸實驗室平靜，已向Cell雜誌提出撤銷申請。

被指修改圖片

張OO強調，相關研究內容均是真實實驗的情況，他未曾加油添醋，圖片是研究所學生為讓人更清楚了解，準備圖檔時直接在原始數據檔中進行標示，造成部分研究數據的原始檔案不齊全，但並不影響研究論點與結論，而且實驗結果可以重複驗證，他雖撤回論文，但「研究歷史絕對會證明我的清白」。

張OO的研究論文獲Cell雜誌刊登，是台灣第一次登上該雜誌的學術研究，興大在十月廿六日特地向外界傳達這項傑出成就，但興大指出，日前有人舉發，該論文部分圖片有人為修改痕跡。

興大十二月八日組成包括台大、中研院及興大專家等跨校專業處理委員會，興大指出，委員會認定張OO必須為不當的圖片操作負責，目前張OO已同意撤回該論文。委員會將徵詢校內外客觀的實驗室重複進行該項實驗，以驗證其結果，做為日後總結懲處的參考。

張：圖片不影響結果

張OO昨日指出，該研究論文是他費時五年才完成的心血，他沒有剪接處理的必要，該圖片並未影響研究結果，以Cell雜誌集合各國頂尖專業人才的嚴格審核標準，若有問題，他的論文根本不可能獲選刊登。

張OO並指出，據他所知，提出質疑者是留美的中國學生，並非該領域專家，只是為回歸研究平靜，本月十二日已向Cell雜誌提出撤銷論文申請，該雜誌迄今未有相關回應。

小瑕疵影響學術嚴謹

中興大學專長植物病毒分子生物學的植病系教授葉OO，也參與了這一次委員會議，他指出，張OO的研究共有七項大圖，每張圖另有小分解圖示，其中的一小張分解圖有剪接現象；他個人認為，應不至於影響整個實驗結構與結果，但學術界畢竟要講究嚴謹，更須嚴肅以對。

中興大學處理張OO教授撤回發表在細胞(Cell)雜誌文章之聲明啟事

後續相關新聞

Hide and Seek: An Introduction to Steganography

OutGusee 的作者 Niels Provos 和他的指導教授 Peter Honeyman 在 2003 年 May/June 的 IEEE Security & Privacy 雜誌發表了一篇隱藏學的介紹性文章 "Hide and Seek: An Introduction to Steganography"。




這篇文章分成三大主軸:

1. The basics of embedding
　a. capacity, security, robustness
　b. steganography & watermarking
　c. Kerckhoffs' Principle
　d. Alice & Bob

2. Hide and seek
　a. Discrete Cosine Transform (DCT)
　b. Sequential
　c. Pseudo random
　d. Subtraction
　e. Statistics-aware embedding
　f. Comparison

3. Steganography detection on the Internet
　a. Steganographic systems in use
　b. Detection framework
　c. Finding images
　d. Verifying hidden content
　e. Distributed dictionary attack
　

Attacking the OutGuess

Jessica Fridrich, Miroslav Goljan & Dorin Hogea
"Attacking the OutGuess,"
ACM Workshop on Multimedia and Security 2002,
Juan-les-Pins, France, December 6, 2002





Abstract
In this paper, we describe new methodology for developing steganalytic methods for JPEG images. The proposed framework can be applied to virtually all current methods for JPEGs including OutGuess, F5, and J-Steg. It also enables accurate estimation of the length of the embedded secret message. The methodology is demonstrated on OutGuess 0.2.

這篇論文針對 OutGuess 0.2 隱藏工具提出一套攻擊方法。所提的分析架構, 不但可以運用到不同的JPEG影像隱藏工具, 亦可以正確地估算嵌入訊息的長度。

在這篇論文的第三節中提到 OutGuess 的特點, 與解釋為什麼 Chi-square attack 無法破解 OutGuess。

p2. left column
The OutGuess steganographic algorithm was proposed by Neils Provos to counter the statistical chi-square attack. In the first pass, similar to J-Steg, OutGuess embeds message bits along a random walk into the LSBs of coefficients while skipping 0’s and 1’s. After embedding, the image is processed again using a second pass. This time, corrections are made to the coefficients to make the stego image histogram match the cover image histogram. Because the chi-square attack is based on analyzing first-order statistics of the stego image, it cannot detect messages embedded using OutGuess. Provos also reports that the corrections are made in such a manner to avoid detection using his generalized chi-square attack.

本篇論文的核心觀念描述在底下這段文字:

P.2 right column
Because OutGuess introduces random changes into the quantized coefficients, the spatial discontinuities at the boundaries of all 8×8 blocks will increase. We will measure the discontinuity using the blockiness measure. For detection, we will inspect the increase of this blockiness measure after embedding a 100% message again using OutGuess. This increase will be smaller for the stego image than for the cover image because of the partial cancellation of changes. This difference will form the basis of our message length estimation.

由於 OutGuess 隨機改變量化後 DCT 係數的 LSBs, 增加了還原後 8*8 區塊的不連續性。J. Fridrich用一個 blockiness formula 來估算區塊不連續性。使用 OutGuess 藏入100% 的資料量後, 檢驗區塊不連續性的增加量。如果這張影像是偽裝影像(stego image), 區塊不連續性增加量是比原始掩護影像 (cover image) 來得小。這個差距就是用來估算嵌入資料量的基礎。

而論文中的 blockiness formula, 其實就是不同區塊間的相鄰像素間的色彩差距絕對值的總和。再求取嵌入資料量大小的過程中, 必須知道原始掩護影像的區塊不連續性, S(0)。J. Fridrich 經由實驗證明, 將偽裝影像裁去四列像素後所得的區塊不連續性和原始掩護影像的區塊不連續性值是相近的, 因此可以用來代替所需的 S(0)。