MSB 비트열의 유사도 비교 함수 분석
이윤호1,*
An Analysis of Correlation Functions for Comparing MSB Strings
Yunho Lee1*
10)
요 약
Lee 등은 원본 이미지 대신 원본 이미지의 MSB 비트열을 공개함으로써 소유권을 증명할 수 있 는 프로토콜을 제안하면서, 두 이미지의 MSB 비트열의 유사도를 측정하기 위한 새로운 함수를 사 용하였다. 하지만, 유사도의 정확성을 입증할 수 있는 실험 데이터가 충분하지 않았고, 임의의 서로 다른 두 이미지의 MSB 비트열은 유사하지 않을 것이라는 가정을 하였다. 본 논문에서는 상용 이미 지 데이터베이스에서 무작위로 1,200 개의 이미지를 선택하여 Cox의 비트열 유사도 비교 함수인 과 Lee가 제안한 를 정규화 과정을 거쳐 비교 분석하고자 한다.
Abstract
Lee et al. proposed an efficient dispute resolving method for digital images without compromising the original images. The protocol used MSB string instead of the original image itself to prove the owner's rightful ownership. Moreover, they proposed a new function to measure the similarity between two MSB strings. Although they claimed that the function was more accurate than the popular function proposed by Cox et al. However, they did not show enough experimental results and assumed that the MSB strings of two distinct and independent digital images. In this paper, we analyze two similarity functions by normalization and show the experimental results by using of 1,200 digital images randomly selected from commercial image database.
Keywords : Watermarking, Corelation, similarity, MSB, median filtering
1광주대학교 사이버보안경찰학과 (광주광역시 남구 효덕로 277) (부교수)
*Corresponding Author : [email protected] 접수일자 : 2020. 05. 26.
1차 심사 : 2020. 05. 27.
2차 심사 : 2020. 06. 01.
게재확정 : 2020. 06. 04.
DOI : http://data.doi.or.kr/10.22733/JITAE.2020.10.01.006
1. 서 론
워터마킹은, 원본 이미지 에 워터마크 를 삽입하여 생성된 이미지 ′이 있을 때, 전송 채 널 상의 잡음이나 JPEG, median filtering 등의 이미지 변형을 가정하기 때문에 워터마크 확인을 위한 이미지 ′는 와 완전히 일치하지 않으며, ′로부터 추출된 워터마크 ′은 와 완 전히 일치하지 않는다. 이로 인해, 워터마크 검 출시 ′을 검사하는 것은 무의미하며, 확률 적인 검출 함수를 이용한다. 즉, 워터마크 비트 열 와 ′사이의 유사도를 확인하게 되는데, 워 터마킹 방식에서 유사도는 표준 상관 계수 (standard correlation coefficient) 또는 Cox I. J.가 제시한 유사도 함수(similarity function)를 사용한다[3][4][7][9].
유사도를 확인하는 것은 워터마크를 검출하 는 과정에서 주로 사용되지만, 특정 이미지의 소유권 분쟁을 해결하는데도 사용된다. 소유권 분쟁이란, 임의의 이미지 I '에서 두 개 이상의 워터마크가 검출되어 I '의 소유권을 확인할 수 없는 경우를 말하며, 워터마킹을 무력화시키는 강력한 공격 방법이다. 소유권 분쟁은 Craver S.가 1996년 처음으로 제기하였고, 이후 소유 권 분쟁을 해결하기 위한 다양한 방법이 제시 되었다[1],[5]. Craver는 워터마크를 생성할 때, 임의의 워터마크를 생성하는 것이 아니라 원본으로부터 일방향 함수를 통해 생성해야 한 다고 주장하였다. 하지만, 워터마크 검출과 소 유권 증명시 원본을 공개하는 문제가 있다.
이 후 Craver와 Adelsbach 등은 암호학에 서 사용하는 증명 프로토콜인 영지식 증명 (zero-knowledge proof)을 이용하여 원본을 공개하지 않고 소유권을 증명하는 방식을 각각 제안하였다[10].[11]. 영지식 증명이란, 어떤 사실, 예를 들면, 비밀 정보 s를 소유하고 있 음을 증명함에 있어 비밀 정보 s에 대한 어떠 한 정보도 노출시키지 않는 것을 말한다. 하지 만, 영지식을 이용한 소유권 증명 과정은 연산 이 매우 복잡하며, 매 증명마다 소유권자가 직 접 증명을 해야 하는 문제가 있다. 또한, 영지 식을 이용한 소유권 증명 방식도 관련된 워터
마킹 방식에서 사용하는 워터마크 검출 함수에 의존하기 때문에 유사도 함수가 매우 중요한 역할을 한다.
2006년 Lee 등은 이미지의 MSBs(most significant bits)를 이용한 소유권 증명 방식 을 제안하였다[2]. 이 방식은 기존 영지식을 이용한 방식과 달리 연산이 복잡하지 않으며, 원본을 공개할 필요가 없고 증명시 소유권자가 반드시 개입해야 하는 번거로움이 없다. Lee의 방식에서 특이한 점은 워터마크 검출시 사용하 는 유사도 비교 함수 이외에 MSB를 비교하기 위한 유사도 비교 함수를 제안하였다는 점인데, 워터마크를 삽입하더라도 MSB가 바뀌는 경우 는 많지 않으며, 이미지가 서로 다를 경우 두 이미지의 MSB 비트열이 같을 확률은 거의 없 다는 추측에 근거하고 있다. 즉, 소유권자는 원 본 이미지 대신 원본 이미지 I의 MSB 비트열 을 신뢰할 수 있는 기관에 등록함으로써 워터 마크 w( =F(MSB(I)))를 생성받아 이미지에 삽입한다. 여기서, 함수 F는 일방향 해시함수 이거나 등록기관에서 지정한 임의의 함수이다.
이후 소유권 분쟁이 발생하였을 경우, 소유권자 가 공개한 MSB 비트열을 이용하거나, 기관에 등록된 MSB 비트열을 이용하여 워터마크 w 를 계산하고, w가 추출되는지 확인하게 된다.
여기서 중요한 가정은 MSB 비트열과 분쟁이 발생한 이미지(워터마크가 포함된 이미지)의 MSB 비트열이 상당히 유사한 관계를 가지고 있을 것이란 점이다. 이를 위해 Lee Y. 등은 두 MSB 비트열 간의 유사도 측정을 위한 별 도의 함수 SIM *를 제안하면서 기존 피어슨 적률 상관계수나 Cox I.J.의 유사도 함수보다 정확하다고 주장하였다.
본 논문에서는 다양한 상용 이미지를 대상으 로, 첫째, MSB 비트열 비교에 특화된 함수와 다른 유사도 비교 함수의 정확도를 분 석하고, 둘째, 이미지가 다를 경우, MSB 비트 열이 다를 확률이 매우 높은지를 분석하도록 한다.
본 논문의 구성은 다음과 같다. 제 2 장에서 는 관련 연구로서 소유권 분쟁 문제와 Cox의
유사도 함수에 대해 설명하고, 제 3 장에서는 Lee가 제안한 소유권 분쟁 해결 방안과 새로운 유사도 함수에 대해 설명한다. 그리고 Lee가 제안한 유사도 비교 함수 와 Cox의 유사 도 함수 SIM을 이용하여 MSB 비트열을 비교 한 결과와 분석을 제 4 장에서 제시한다. 그리 고, 마지막으로 제 5 장에서 결론을 맺는다.
2. 관련 연구
2.1 소유권 증명
일반적으로 워터마크는 저작물에 대한 소유 권을 나타내기 위해 삽입된다. 하지만, 디지털 저작물인 경우, 워터마크가 검출되었다고 해서 소유권을 인정받을 수 있는 것은 아니다. 왜냐 하면, 디지털의 특성상, 공격자가 자신의 워터 마크를 추가로 삽입할 수 있기 때문이다. 이것 을 소유권 증명 문제라고 부르며, Craver가 처 음으로 제기하였다.
강인한 워터마킹 방식의 특성상 다수의 워터 마크를 삽입해도 모두 검출되기 때문에 워터마 크 만으로는 소유권을 증명하는데 한계가 있다.
Craver는 이러한 소유권 증명 문제를 해결하 기 위해서는 원본 이미지 I와 삽입하는 워터마 크 WA는 서로 일방향성 관계를 가져야 한다고 주장하였다. 예를 들면, 안전한 해시함수 H를 이용하여, WA=H(I)와 같이 생성해야 하는 것이다. 이러한 워터마킹 방식을 비가역성 워터 마킹 방식(Non-invertible watermarking scheme)이라고 부르는데, 이 후 Craver의 해 결 방안은 Ramkumar에 의해 안전하지 않음 이 입증되면서 많은 비가역성 워터마킹 방식이 제안되었다[6][8][11][12][13].
대부분의 소유권 증명 해결을 위한 비가역성 워터마킹 방식들은 소유권을 증명함에 있어 원 본소유자로 하여금 원본을 공개할 것을 요구하 고 있다. 하지만, 원본은 소유자만 알고 있는 비밀 정보에 해당하기 때문에 이는 매우 위험 한 요구사항이다. 원본을 공개하지 않고 소유권 을 증명하는 방식으로 Craver와 Adelsbach가
제안한 방식과 함께 Lee가 제안한 MSB를 이 용한 방식이 있다.
2.2 유사도 함수
Cox는 DCT를 이용한 확산 대역 워터마킹 방 식을 제안하면서, 워터마크의 유사도 비교 함수 SIM을 제안하였다. 두 변수 과 ′
′′′
이 있을 때, 유사도 SIM(W,W ')은,SIM(W,W ') = W'∙W W'∙W'
로 계산되는데, wi와 wi'은 {-1,1} 또는 {0,1}의 값을 갖는다. 만약 W와 W'이 서로 독립적이라면 0에 근접한 값을 출력한다. 그림 1은 식 (1)의 실험 방법을 적용한 결과이다.
그림 1-(a)는 서로 독립적인 비트열의 상관 관 계 결과이고, 그림 1-(b)는 그 가운데 하나만 매우 유사한 경우의 결과이다.
(a) 서로 독립적인 비트열간의 결과.
(b) 110번째에 유사한 비트열이 있는 경우.
그림 1. Cox의 SIM 함수 결과.
Fig. 1. Results of Cox’s SIM Function.
3. 소유권 분쟁 해결
3.1 워터마킹 과정
저작권자 A는 자신의 원본 이미지 I에 삽입 할 워터마크 W를 생성하기 위해 I의 MSB 비 트열을 추출하고 이를 관리 기관에 제출한다.
관리 기관에서는 MSB 비트열로부터 일정 길 이의 워터마크 W를 생성하여 A에게 보내준 다. 이 때, 관리 기관에서는 W를 생성할 때 A가 제출한 MSB 비트열 정보 이외에 생성 시기를 나타내는 타임 스탬프 t와 A의 신원 정보 등을 함께 이용할 수 있으며, 관리 기관의 전자 서명 방식 등을 이용할 수 있다. A는 생 성된 워터마크 W를 이용하여 I W를 만들고 이 를 배포한다. 이 때 워터마킹 방식으로는 강인 한 방식을 사용해야 한다.
3.2 워터마크 검출
I W로부터 변형된 이미지 IW'에 대한 워터 마크의 검출 과정은 다음과 같다. 먼저, A는 확인자 C에게 자신이 소유한 I의 MSB 비트 열과 워터마크 W, 타임 스탬프 t 등을 제시한 다. C는 I W'의 MSB 비트열과 제시된 MSB 비트열이 유사한지 확인한다. 또한 워터마크 W 가 관리 기관의 서명을 포함하고 있는지 확인 한다. 두가지가 확인되면 실제로 워터마크를 검 출하여 W와 유사한지 확인한다. 만약 이 과정 을 모두 통과하면, A가 시간 t 이전에 IW'의 원본 이미지를 생성했음을 확인할 수 있다. 즉, 원본 이미지를 확인하지 않아도 되는 장점이 있다.
3.3 유사도 비교 함수
Lee의 방식에서는 모두 두 번의 유사도 비 교가 필요하다. 하나는 MSB 비트열의 유사도 비교이고 다른 하나는 일반적인 워터마크의 유 사도 비교이다. 두 유사도 비교는 유사한 역할 을 하지만, MSB 비트열에 대한 유사도 비교 는 워터마크를 삽입하기 전/후 이미지가 대상 이라는 점이 다르다. 또한, MSB 비트열의 특
징을 고려하면 일반적인 유사도 비교 함수보다 정확도를 크게 높일 수 있다. 즉, 어떤 이미지 의 MSB 비트열은 워터마크를 삽입하거나 이 미지 처리를 하더라도 값이 잘 바뀌지 않는 특 징이 있다. Lee는 이를 이용하여 SIM *를 제 시하였다.
⊕
단, X=x1x2⋯xn과 Y=y1y2⋯yn은 바이 트열을 나타낸다. 여기서, k는 1픽셀을 나타내 는 비트 수가 되는데, 일반적으로 워터마킹은 YUV 공간에서 Y를 대상으로 하기 때문에 k= 8이 된다. 이 때, 유사도 비교 결과는
≤ 의 범위를 갖게 되는데, 두 바이트열의 MSB 비트열이 유사할 수록 0에 가까운 결과를 보인다.
I W 이미지에 이미지 크롭(crop) 공격을 가 해 IW'을 생성한 경우라면 MSB 비트열의 길 이가 서로 다를 수 있다. 이러한 경우에는 길이 가 짧은 IW'의 MSB 비트열을 기준으로 다양 하게 유사도를 측정하여 최대값을 사용하면 된 다. 그림 2는 앞에서 설명한 두 유사도 비교 함수의 실험과 비슷한 과정을 거쳐 일반적인 결과를 추출한 그림이다. 길이가 1,000인 무작 위 두 바이트 열에 대해, 1바이트만 다른 경우 이다.
그림 2. SIM * 함수 결과.
Fig. 2. Results of SIM * Function.
4. 유사도 비교 함수 시험 및 성능 분석
4.1 시험 방법
유사도를 비교하는 세 함수는 모두 출력값의 범위가 다르기 때문에 정확도를 비교하기가 곤 란하다. 따라서, 같은 범위로 정규화시키는 것 이 필요하다. Cox의 SIM 함수는 입력 길이 n 에 대해 - n≤SIM(W,W ')≤ n 의 범위를 가 지며, 두 입력값이 서로 무관할 수록 0에 가까 운 값을 출력한다. 하지만, 의 경우, 범위 는 ≤ ′ 이고, 두 입력값의 상관 관계가 높을 수록 0에 가까운 값을 갖는다. 따 라서, 다음과 같이 정규화하는 것이 필요하다.
SIM ← SIM n
←
이 경우, 는 정규화한 후의 값이 0.5~1.0 범위를 크게 벗어나지 않는 특성이 있다. 이는 MSB 한 비트 만을 이용하는 SIM 함수와는 달리 두 MSB가 서로 다르더라도 바 이트 전체를 분석하여 가중치를 다르게 주기 때문인데, 이런 이유로 의 결과값이 0일 확률은 거의 0(1/28n)에 가깝게 된다. 참고로 SIM의 경우, 두 MSB 비트열의 유사도가 0일 확률은 1/2n이다. 따라서, 본 논문에서는 정규 화에 적합하도록 SIM *를 다음과 같이 수정하 여 사용하도록 한다.
α는 파라미터로서,
|
yi-2k- 1|
≤64일 경우-0.2, 아닐 경우 -1.8로 설정하였다. 의 출력값을 정규화할 경우, 단순히 n 으로 나 눠주면 된다.
실험은 크게 네가지로 나눠서 실시한다. 첫 번째는 완전히 일치하는 두 바이트열 X,Y로부 터, 점차적으로 Y 바이트열 값을 변형하면서 결과를 분석하는 실험이다. 실험을 위한 입력 데이터 구성 방법은 다음과 같다. 먼저, n 바
이트로 구성된 바이트열 X={x1,...,xn}를 임 의로 생성한다. 그리고, 다음 식을 이용하여 X 로부터 Y를 생성한다.
∈
단, t는 1부터 128까지 순서대로 증가시킨 다. 즉, t가 작으면 바이트 왜곡이 크지 않은 경우이며, t가 크면 바이트 왜곡이 크다는 뜻 으로, 점차적으로 Y를 X 와 무관하도록 만들 게 된다.
두 번째 실험은 특정 이미지에 대해 4×4 Median filtering 처리를 1~20회 반복 적용 하면서 원본 이미지와의 유사도 측정값을 분석 하는 실험이다. 256×256 해상도의 컬러 Lenna 이미지를 실험 대상 이미지로 사용하였다. 그리 고 마지막 세 번째 실험으로 실제 상용 이미지 데이터베이스에서 1,200개의 실험용 이미지를 무작위로 선정하고, 해당 이미지에서 추출한 MSB 비트열의 유사도를 측정해 보도록 한다.
4.2 분석 결과
먼저 첫 번째 실험 결과로 128 단계별 바이 트 값을 왜곡한 경우부터 설명한다. Cox의 SIM, 그리고 Lee의 를 128단계별로 비 교한 결과를 그림 3에 나타냈다.
그림 3. 128단계별 왜곡에 따른 유사도 측정 결과.
Fig. 3. Results of similarity caused by 128 steps distortion.
그림 3에서 볼 수 있듯이, Cox의 SIM 함수 출력값은 두 바이트열의 상관 관계가 떨어질
수록 선형 반비례하며 감소하는 것을 볼 수 있 다. 하지만, Lee의 유사도 함수 출력값은 조금 다른 특성을 보인다. SIM 함수보다 출력값이 높고, 출력값의 변화도 약간 곡선을 그리는 중 요한 특징을 갖고 있다. 일반적으로 원본 이미 지 I의 MSB 비트열과 워터마크 삽입 후 이미 지 IW의 MSB 비트열은 일치하지 않을 가능성 이 높다. 즉,
|
xi-2k- 1| 가 0에 가까울수록 xi와 yi의 MSB는 서로 다를 가능성이 높기 때문에 두 MSB 비트열의 유사도를 비교할 때 이를 고려한다는 의미이다.그림 4. 4x4 Median filtering 처리에 따른 영상의 변화.
Fig. 4. Results of visual changes caused by 4x4 Median filtering.
그림 4는 256×256 크기의 컬러 Lenna 이미 지를 대상으로 실험한 결과이다. 워터마킹 방식 으로는 Cox의 확산대역 방식을 적용하였으며, 삽입 파라미터 α= 0.8로 설정하였다.
실험 결과는 그림 5와 같다. 워터마크 삽입 직후의 이미지는 두 유사도 비교 함수 모두 매 우 높은 값을 출력하지만, 4×4 Median filtering을 10회 처리한 후 측정한 결과 Cox 의 SIM 함수는 0.60 이하로 떨어진 반면, Lee의 는 0.85 정도의 높은 값을 출력하 였고, 20회 처리한 후 측정한 결과는 각각 0.35와 0.72였다. 사실상 4×4 Median filtering을 20회 처리한 결과 영상은 왜곡이 심해 그대로 사용하기에는 무리가 있지만, 영상 의 왜곡 정도와 원본 영상과의 유사도는 서로 별개로 보아야 할 것이다. 왜냐하면, 유사도가 충분히 낮아지도록 영상을 왜곡한 후 불법 유 통시키는 경우도 있을 수 있기 때문이다. 따라 서, 완전히 별개의 영상이 아닌 이상, 유사성을 정확하게 판별하는 것은 매우 중요하다.
그림 5. 4x4 Median filtering 처리 후유사도 측정 결과.
Fig. 5. Results of similarity after 4x4 Median filtering.
256×256 해상도를 갖는 이미지 가운데, 무작 위로 1,200 개를 선택한 후, Lenna 이미지와 MSB 비트열 유사도를 비교해 보았다.
Median filtering 결과 그래프를 바탕으로 SIM은 0.35를 넘지 않아야 하며, SIM *는 0.72를 넘지 않아야 함을 알 수 있다.
먼저 평균값을 보면, SIM 함수가 0.0546, SIM * 함수가 0.3069를 보였다. 이 값과 그 림 5의 하한값의 차이는 각각 0.2954와 0.4131로 의 측정값이 보다 더 정확함을 알 수 있다. 이 같은 결과는 그림 6을 통해서 도 확인할 수 있다.
그림 6. 유사도 측정 하한선부터 하한선-0.2 범위에서 유사도 출력값.
Fig. 6. Results of similarity ranges from minimum to minimum-2.
측정 하한선에서 -0.2 범위내의 유사도를 갖 는 경우를 보면 SIM의 경우, 약 30여개의 이 미지가 포함된 반면, SIM *는 단 4개의 이미 지만 포함되었다. 이는 다른 이미지의 MSB 비 트열과 유사하다고 판단할(false positive) 확 률이 SIM *가 더 낮음을 보여주는 것이며, 유 사도 기준 하한선을 보다 여유있게 설정할 수 있음을 의미한다.
5. 결 론
두 이미지의 MSB 비트열의 유사도를 비교 하는 것은, 일반적인 비트열의 유사도를 비교하 는 것과는 다르다. 물론, Cox의 SIM을 이용하 여 유사도를 비교할 수도 있지만, 비교 대상 이 미지를 고려하면 유사도 판단의 정확도를 보다 높일 수 있다. 본 논문에서는, Lee가 이미지 MSB 비트열의 비교를 위해 제안한 SIM *를 정규화에 적합하도록 수정한 후 상용 이미지 1,200개를 대상으로 한 실험을 통해 Cox가 제 안한 SIM보다 가 더 정확하게 판단함을 알 수 있었다. 또한, 일반적인 상용 이미지의 MSB 비트열이 서로 유사할 확률은 극히 낮음 을 역시 실험을 통해 입증했다.
감사의 글
이 연구는 2020년도 광주대학교 대학 연구 비의 지원을 받아 수행되었음.
참고 문헌
[1] S. Craver, N. Memon, B. Yeo, and M.
Yeung, “Can Invisible Watermarks Resolve Rightful Ownership?”, IBM Research Division, Tech. Rep, RC20509, 1996.
[2] Yunho Lee, Heasuk Jo, Seungjoo Kim, and Dongho Won, “An Efficient Dispute Resolving Method for Digital Images”,
OTM Workshops 2006, LNCS 3823, pp.
331-341, 2006.
[3] G. Seon, A. Makeev, J. D. Schaefer, and B. Justusson, “Measurement of Interlaminar Tensile Strength and Elastic Properties of Composites Using Open-Hole Compression Testing and Digital Image Correlation”, Applied Sciences, Vol. 9, No. 13, 2019.
[4] I. J. Cox, J. Kilian, F. T. Leighton, and T. Shamoon, “Secure Spread Spectrum Watermarking for Multimedia”, IEEE Transactions on Image Processing, Vol.
6, pp. 1673-1687, 1997.
[5] S. Craver, N. Memon, B. Yeo, and M.
Yeung, “Resolving Rightful Ownerships with Invisible Watermarking Techniques:
Limitations, Attacks and Implications”, IEEE Journal on Selected Areas of Communications, Vol. 16, No. 4, pp.
573-586, 1998.
[6] L. T. Qiao, and K. Nahrstedt, “Watermarking Schemes and Protocols for Protecting Rightful Ownership and Customer's Rights”, Journal of Visual Communication and Image Representation, Vol. 9, No. 3, pp. 194-210, 1998.
[7] T. Marcin, D. S. Stefano, D. F. Gianmarco, K. Arkadiusz, and R. Francesca, “Application of Digital Image Correlation to composite reinforcements testing”, Composite Structures, Vol. 160, No. 15, pp. 670-688, 2017.
[8] M. Ramkumar, and A. N. Akansu, “Image Watermarks and Counterfeit Attacks:
Some Problems and Solutions”, Proceedings of Content Security and Data Hiding in Digital Media, pp. 102-112, 1999.
[9] P. Bing, “Digital image correlation for surface deformation measurement: historical developments, recent advances and future goals”, Measurement Science and Technology, Vol. 29, No. 8, 2018.
[10] S. Craver, “Zero Knowledge Watermark Detection”, Proceedings of Information Hiding 99, LNCS 1768, pp. 101-116, 2000.
[11] A. Adelsbach, S. Katzenbeisser, and A.
R. Sadeghi, “Watermark Detection with Zero-Knowledge Disclosure”, ACM Multimedia Systems Journal, Special Issue on Multimedia Security, Vol. 9, No. 3, pp.
266-278, 2003.
[12] Q. Li, and E. C. Chang, “On the Possibility of Non-Invertible Watermarking Schemes”, Information Hiding 2004, LNCS 3200, pp.13-24, 2004.
[13] A. Adelsbach, S. Katzenbeisser, and A.
R. Sadeghi, “On the insecurity of noninvertible watermarking schemes for dispute resolving”, Proceedings of International Workshop on Digital Watermarking 2003, LNCS 2939, pp. 355-369, 2003.
