Introduction to Digital Watermarking

워터마킹 기술 Digital Watermarking 이흥규 KAIST 전자전산학과 hklee@casaturn.kaist.ac.kr 년 월

Your Speaker 학력 서울대학교 전자공학과 졸업(학사), 1 한국과학기술원 전산학과 졸업(석사, 박사), 11, 1 경력 U. of Michigan in Ann Arbor 연구원(1-16) 한국과학기술원 전산학과 교수(16-현재까지) 과학재단 지정 첨단정보기술연구센터 부소장(1- 현재까지) 정보통신부지원 DRM-forum 보호기술분과, SEDICA 워터마킹분과 분과위원장(-현재까지)

Contents Information Hiding History Model Requirements and Classification Application 3

What is WM? Digital watermarking 일종의 정보은닉 기술로써, 데이터(영상, 동영상, 오디 오, 텍스트 등)에 특수한 정보를 보이지 않도록 삽입하 는 기술 Digital Watermarking은 단순히 정보를 은닉하는 것 이 외에 특수한 목적을 위하여 사용되므로, 여러 형태의 공격에 의해 은닉된 정보가 사라지지 않아야 한다. Watermark Digital Watermarking에서 데이터에 삽입되는 특수한 정보를 watermark라고 한다. Watermark는 문자열, 키를 이용한 난수열, 로고 영상 등 다양한 형태로 이루어질 수 있다.

Digital Watermarking Owner s Key Owner s Watermark Owner s Key Extracted Watermark Owner s Key Multimedia Data Marked Data <Watermark embedding> <Watermark extraction>

Digital Watermarking(Example) <Original> <Watermarked Image> <Watermark> 6

Digital Watermarking vs. Encryption Hybrid system Original Data Watermark Insertion Encryption Communication Channel Decryption Watermarked Data key key key

Models for Watermarking Communication-based Model Many digital watermarking concepts derive from the previous studies in the field of Communicati ons. Geometric Model A watermarking system can be modeled in geo metric terms. We define a media space, a high dimensional s pace where each point corresponds to a given content.

Communication System Noise n Input messag e m Channel encoder x + y Channel decoder m n Output messag e The encoder maps the message m into a codeword x drawn from a set of signals that can be transmitted over the channel

Communication System Noise n Input message m Channel encoder x + y Channel decoder The signal x is sent over the channel where some noise is introduced. Usually we model as AWGN channel: the received signal y = x + n. The channel is fixed, we cannot design it. m n Output message 1

Input message Communication-based Model of WT m Noise Watermark embedder c o n c w + c wn Attacks / cover work watermar k detector m n Output message Original content Watermarked content Watermarked & attacked content 11

Geometric Models of WT : Media Space a specific image can be thought of as points in an N -dimensional media space. N, dimension of media space, is the numbe r of samples used to represent each image. In the case of a video: N = (number of frames) * (number of pixels in a frame) * (3 color bands).

Media Space Since in digital content each sample is qua ntized and bounded, the number of points i n the media space is limited. The media space is a huge but finite set of possible images, i.e. a finite grid of points. We can define: a region of acceptable fidelity a detection region.

Region of acceptable fidelity lmagine taking an image, c and altering ju st a single pixel by one unit of brightness. This new image defines a new vector in me dia space, yet it is perceptually indistinguish able from the original image. We can imagine a region around c in whic h every vector corresponds to an image that is indistinguishable from c. It is the region of acceptable fidelity for c. 1

Region of acceptable fidelity It is difficult to identify the true region of ac ceptable fidelity around a given content, be cause too little is known about human perce ption. We usually approximate the region by placi ng a threshold on some measure of percept ual distance. 1

Region of acceptable fidelity Mean squared error (MSE) as a simple perceptual distance metric. Dmse (c 1,c ) = (1/N) (c 1 [i]- c [i]) c 1,c are N-vectors in media space. lf we set a limit mse on this function, the region of acceptable fidelity becom es an N-ball of radius. N mse In practice, MSE function is not good at predicting perc eived differences between Works. Other measures: JND(Just Noticeable Difference) 16

Detection Region The detection region for a given message, m, and watermark key, k, is the set of works in media space that will be decoded by the detector as containing that message. This region is often defined by a threshold on a measure of the similarity between detect or's input and watermark, a pattern that encodes m. We refer to this measure of similarity as a detec tion measure. 1

Detection Region linear-correlator based detector scheme lc where c w N is lc r, a threshold c c w w Detection region 1

Detection Region normalized-correlator based detector v v w w r r cos 1 nc ( nc ) cos( ) nc w Detection region 1

Succesful embedding A successful embedding of a watermark re sults in a watermarked Work that lies within t he intersection of the region of acceptable fi delity and the detection region. Region of acceptable fidelity c c w Detection region

Basic watermarking model Encoding, error correction, modulation Payload (P) (n bits) Watermark (W) Watermark embedding Watermarked image (Ĩ) Cover-image (I) Key (K) Distortions due to normal use Attacks Watermark detection or extraction Possibly corrupted marked image (Ĩ ) 1 Payload (P) (n bits)

Contents Information Hiding History Terminology and Model Requirements and classification Application

Main requirements Imperceptibility (fidelity) Robustness Normal use Tamper resistance Active attacks, passive attacks, collusion attacks, forger y attacks Other properties Capacity Embedding / extracting time (complexity) Reliability False alarm Bit error rate 3

Classification Visibility 에 따른 분류 Visible visual message, logo 영상의 quality를 떨어뜨림 Invisible watermarking 된 영상과 원영상이 육안으로 구분할 수 있다. + < Visible watermarking의 예>

Visible Paper watermark Digital watermark Invisible Vatican s Library/I.B.M. Fragile watermarks tamper detection Watermarks copyright marks Fingerprints serial numbers Giovanni Battista Vanni, Head of Saint Courtesy of Musée du Louvre, Paris, France Copyright Vatican s library. Courtesy of I.B.M.

6 Classification Robustness에 따른 분류 Fragile 영상을 변화시키면 삽입된 watermark가 손상된다. 인증 및 데이터의 무결성 검사에 사용(위, 변조 방지) Semi-Fragile 일정수준 이상의 변화에 watermark가 손상되며 반드시 손상되야한다. Robust 영상의 변화에도 watermark가 그대로 추출된다. 소유권 주장, 핑거프린팅등에 사용 삽입영역에 따른 분류 Spatial Domain Watermarking 영상의 화소나 오디오의 샘플(공간영역)에 Watermark를 삽입하는 기법 Frequency Domain Watermarking DCT, DFT 등의 주파수 영역으로의 영상변환 후 변환 영역에서 watermark를 삽입하는 기법 원영상의 필요 유무에 따른 분류 Private Watermarking watermark 추출시 원 영상이 필요한 watermarking 기법 Public Watermarking watermark 추출시 원 영상이 필요없는 watermarking 기법

Classification (extraction) Type I Output is the payload Type II Output is present / not present Non-blind Semi-blind Blind I ~ I K ~ I I K ~ ~ I I K W P ~ ~ I I K W I ~ K P ~ I K W P,1,1,1

Contents Digital Watermarking Image Spatial Transform Domain Video

Basic principles Choice of the workspace Transform spaces (e.g., DCT, DFT, DWT) can b e more advantageous Choice of host locations in the cover Random selection of features in the transform s pace Impossible to find out where the information is without a k ey Spreading Any part of the cover-signal contains the hidden data Formatting of the payload Use of error correction codes Merging the watermark & the cover Masking Take explicit advantage of the properties of the human vis ual or auditory system

Spatial Domain Watermarking 원영상에 직접 WM를 삽입 (밝기세기를 직접 변화) 다양한 영상신호처리 (압축, 필터링 등) 과정 시 WM 손실 큼. 삽입되는 WM 신호의 양이 적음. 불건전한 제 3 자의 고의적 공격에 취약함. 3

Embedding 31 Statistical method : Patchwork (Bender 16) Pseudo-randomly selec t n pairs of pixels (ai, bi) Modify their luminance values a~ i ~ b Assumption n i i1 a b i i d d a i b i Detection Retrieve the same pixel s Compute: D Test n a ~ i b i i1 ~ D nd: watermarked D: not watermarked Walter Bender, Daniel Gruhl, Norishige Morimoto and Anthony Lu. Techniques for data hiding, I.B.M. Systems Journal, vol. 3, no. 3&, pp. 3 336, 16

Patchwork Watermark가 삽입됨에 따라 변화하는 n개의 화소 쌍 차이값의 분포 변화 3

Patchwork lena image 1 different watermarks d = 6 Watermarked 3 D/n 1-1 Not watermarked - 1 3 6 1 33

LSB Coding LSB coding 가장 간단한 형태의 Watermarking 기법 영상의 각 화소의 LSB(Least significant bit)에 watermark 신호를 삽입한다. LSB가 화질에 미치는 영향은 거의 없으므로 watermark 삽입으로 인한 화질 저하는 적다. 그러나, LSB는 여러 가지 데이터처리에 쉽게 손상되므 로 robustness가 떨어진다. Pixel watemark bit 1 1 1 1 6 3 1 (LSB) 3

Example 워터마크 정보 : ID, 텍스트, 로고, 농담영상 등 이진영상을 삽입하는 경우 1비트씩 삽입한다 Copy Right 그림 있는 곳은 1 그림 없는 곳은 문자를 삽입하는 경우 A 진 데이터로 변환 비트 열 1비트씩 삽입한다 watermarked Image 3

36 1 6 6 1 1 11 1 11 6 3 3 6 3 1 3 1 1 3 1 1 1 3 6 6 6 3 1 6 1 3 3 1 1 1 3 3 3 1 6 3 1 6 1 3 1 6 3 6 Watermarked Image 1 6 6 1 1 11 1 11 6 6 6 6 6 6 3 6 1 3 1 3 6 3 6 1 3 1 6 3 6 내부를 모두 홀수로 변경 여기를 변경한다 Original Image Watermark 영상에 영상을 삽입하는 방법

화소 치환형의 문제점과 대책 쉽게 해독되어 공격에 취약 y 보정 곡선 출 력 의 밝 기 P (x, y) 이 부분만큼 출력 되는 레벨이 변해 버린다. x 입력의 밝기 3 밝기 조작에 의한 디지털 워터마크의 소실

Watermarking for Image Verification (Yeung) Watermark 삽입영상과 추출된 watermark 3 변형된 영상과 추출된 watermark

Correlation-Based Watermarking Scheme Watermark Embedding Procedure: Iw(x,y)= I(x,y) + k W(x,y) I(x,y) + I w (x,y) k X 3 W(x,y): Pseudorandom pattern {-1, 1}

Correlation-Based Watermarking Scheme Watermark Detection Procedure: Correlation Response Z between Iw(x,y) and z W(x,y) 1 L1 L1 1 1 1 L L i if z > threshold, watermark is said to be present, otherwise, watermark is said to be absent. d( i) L i r(i) = I(i) + w(i) [( I( i) w~ ( i)) I( i)] w( i) + - X d(i) d(i) correlator L i w~ ( i) w( i) z I(i) w(i)

Correlation-Based Watermarking Scheme Watermark Embedding Procedure: add wm to each subimage I I 1 I I 3 I I I 6 I I(x,y) + I w (x,y)= I(x,y) + k W(x,y) I 1 k X X b b 1 b b 3 b b b 6 b b= : -1 b=1 : 1 W(x,y): Pseudorandom pattern {-1, 1} 1 b 1

Correlation-Based Watermarking Scheme Watermark Detection Procedure: I I 1 I I 3 I I I 6 I I (x,y) Test Image Correlator b b 1 b b 3 b b b 6 b I 1 b 1 b= : -1 b b 1 b b 3 b b b 6 b b=1 : 1 b 1 W(x,y): Pseudorandom pattern {-1, 1}

Correlation-Based Watermarking Scheme Watermark Generation Sequence of information bits (e.g. serial number) : a j {1, 1 } Spread sequence : b j a j, j cr i < (j+1) cr (cr=chip-rate) Pseudo-noise sequence (PN seq.) : p j {1, 1 } Watermark : w j = b j p j Watermarked image : v j = v j + b j p j a j b j cr=1 PN seq (p j ) PNb j (p j x b j ) 3

Spread-spectrum example Embedding Cover Signal s i Payload bit b=±1 Spreading sequence ri 1,1, i c Spread watermark w i rb Watermarked signal ~ s s w Assumption i r i i s & r not correlated s r i i i i Extraction Correlation r b ~ s c r i i i After thresholding b sign r c r r i s i w i

D.S.S. example x = randn(1, 1); w = randn(1, 1) / ; plot(xcov(x, w)); plot(xcov(x + w, w)); 3 3 1 1-1 -1 - - -3-3 -...6. 1 1. 1. 1.6 1. x 1 -...6. 1 1. 1. 1.6 1. x 1

Masking: host locations 6 Cécité du maître, Bernard Clarisse, 1. Courtesy of Gallery Duchoze, Rouen, France Enhanced difference between original & watermarked image

Contents Digital Watermarking Image Spatial Transform Domain Video

주파수 변환 뒤, 주파수 계수에 WM를 삽입 DCT, DFT, DWT Frequency Domain 인간의 시각특성 (저주파 민감, 고주파 둔감) WM가 삽입될 적절한 주파수 대역의 선택이 핵심. 저/고 중간대역에 WM 삽입 후, 역변환, WM가 전영 상에 분산 화질저하감소, 공격에 강함. L Frequency Transformation H H

Discrete Cosine Transform JPEG의 원리 N N 화소의 DCT : (a) DCT(Discrete Cosine Transform) F( u, v) N c( u) c( v) N 1 N 1 x 또는 u y v 일 때 (x 1) u (y 1) v f ( x, y)cos cos N N 일 때 c( u) c( v) u, v 1 F( u, v) : f ( x, y) : DCT 계수 영상신호 c( u) c( v) N 1 N 1 x y x, y : : 1 화소의 수 영상의 좌표

(b) IDCT(Inverse DCT) N v y N u x v u F N v u f N u N v 1) ( cos 1) ( )cos, ( ), ( 1 1 영상신호 DCT 계수

DCT basis functions v u 1

a)원 영상(ⅹ화소)의 일부 1 3 3 36 1 1 ⅹ화소 전 화면에 대하여 수행 g) 복호된 영상(ⅹ화소) 6 66 3 3 1 3 1 3 1 DC계수 AC계수 b) DCT 계산 후 1 1-16 - -3-6 -1 3 116 1 Q로 나눈다 양자화 테이블 (Q) 16 11 1 16 1 1 1 16 1 1 f) 역 DCT계산 후 16 11-16 - - -1-16 11 11 c) 양자화 테이블로 나눈 결과 3 16 11 3 - - - -1 6 1-1 1 d) 허프만 부호화 파일 보존 Q를 곱한다 e) 허프만 부호로부터 복호 3 16 11 3 - - - -1 6 1-1 1 3, 16, -, 6, -, 11, 3, -, 의 순서로 부호화 (지그재그 스캔) JPEG Processing

Example 3 워터마크 비트가 1 이면 DCT 계수를 홀수로 변 경 워터마크 비트가 이면 DCT 계수를 짝수로 변 경 처음부터 상기조건을 만족하는 경우 그대로 둠 위 조작에 의해 계수가 로 되는 경우 중지 또 는 정도 가감

원 영상의 DCT (지그재그 스캔 후) 1 1 계 수 6 대상영상의 DCT계수를 한열로 나열한 것 1 3 6 1 11 차수 1 1 계 수 6 비트 1 삽입 대상영상의 DCT계수를 1열로 나열한 것 1 3 6 1 11 차수 원 영상 DCT 계수를 지그재그 스캔 주 파 수 높 다 주파수 높다 1 1 계 수 6 비트 삽입 대상영상의 DCT계수를 1열로 나열한 것 1 3 6 1 11 차수 차수 6인 곳의 값이 원 영상/비트1 삽입/비트 삽입의 경우가 다름 DCT 계수에 워터마크 삽입의 원리

Seminal example Insertion DCT(I) Select n largest coeffi cients a i Select n random num bers w i (the mark) a~ i 1 w i a i IDCT( A ~ ) Test DCT(I) Select n largest coeffi cients a i DCT( ) & extract the same coefficients w i sim I ~ a~ a 1 i i W, W a ~ i W W WW I. J. Cox, J. Kilian, T. Leighton and T. Shamoon. A secure, robust watermark for multimedia, In R. J. Anderson, ed. Information hiding: first international workshop, vol. 11 of Lecture notes in computer science, Springer, pp. 13 6, Isaac Newton Institute, Cambridge, England, 16

Ingemar J. Cox, et. Al., Secure Spread Spectrum Watermarking for Multimedia, IEEE Trans. On Image Processing, Vol. 6, No., December 1, pp. 163-16 Watermark 신호를 영상 (통신 채널)이 갖고 있는 넓은 주파수 대역으로 확산하여 삽입함으로써 삽입된 신호를 감지할 수 없도록 watermark를 삽입 6

Spread Spectrum Watermarking (Cox) Watermark 삽입 1) 전체 영상을 DCT나 DFT를 통하여 영상 변환 ) 변환 영역에서 시각적으로 중요한 계수 n 개를 선 택 3) 삽입되는 watermark 신호는 정규분포(평균, 표 준편차 1)을 따르는 실수 난수열을 이용한다. ) 선택된 계수들을 watermark 신호에 따라 변화시 킨다. ) X i = Xi + XiWi = (1 + Wi)Xi 6) 전체 영상을 IDCT나 IDFT를 이용하여 공간영역으 로 변환시킨다.

Watermark의 검출 원 영상 필요 1) 원영상과 watermarking된 영상을 각각 변환(DCT, DFT) ) Watermark 삽입시와 마찬가지로 두 영상에서 시각적으로 중 요한 n개의 계수들을 선택 3) Watermarking 된 영상의 계수에서 원영상의 계수들을 뺀다. (watermark 추출) W i = (Yi Xi) / Xi ) 추출된 watermark(w )와 삽입된 watermark(w) 간의 correlation을 구한다. R WW ' W W ' W ' W ' 1) Rww > T (threshold) 이면 watermark 검출

Cox s embedding function [J, W] = Wmk(I, alpha, N, W) DCTI = dct(i); Index = FindNLargest(abs(DCTI), N); for i = 1:N DCTI(Index(1, i), Index(, i)) = DCTI(Index(1, i), Index(, i)) * (1 + alpha * W(i)); end J = idct(dcti); http://www.cl.cam.ac.uk/~fapp/software/coxwmk_..zip

Cox s detection function sim = Detect(I, J, W, alpha, N) DCTI = dct(i); DCTJ = dct(j); Index = FindNLargest(abs(DCTI), N); for i = 1:N end X(i) = (DCTJ(Index(1, i), Index(, i)) / DCTI(Index( 1, i), Index(, i)) - 1) / alpha; sim = Similar(W, X); w i a~ a 1 i i http://www.cl.cam.ac.uk/~fapp/software/coxwmk_..zip 6

61 Cox: sample

Cox: sample =.1 6

Contents Digital Watermarking Image Spatial Transform Domain Video 63

Several Schemes in Video Watermarking Raw video MPEG ENCODER Compressed bit-stream MPEG DECODER Reconstructed video Watermark Embedding 1 Watermark Embedding Watermark Embedding 3 Watermark Extraction 1 Watermark Extraction 6