1. 서론

정보통신기술의 발전과 스마트 기기의 높은 보급률로 인하여 사진 및 동영상 등과 같은 멀티미디어 기술에 대한 관심이 폭발적으로 증가하고 있다. 이러한 관심의 증대로 인하여 디지털 이미지 처리 기술 또한 발전하고 있으며 이에 관한 연구가 활발히 진행되고 있다. 그 중 여러 가지 빛깔의 작은 조각 또는 타일들을 붙여 무늬나 영상을 만드는 포토 모자이크 기법에 관한 연구가 진행되고 있다. 이러한 모자이크 작업은 예술가에 의해 주로 진행되어왔으나 최근 스마트기기의 높은 보급률 등으로 인하여 일반 사용자들도 손쉽게 접근할 수 있는 영역으로 확장되고 있다. 또한 개인의 개성을 중시하는 최근 트렌드와 결합되어 자신이 좋아하는 연예인을 모자이크로 만드는 등의 다양한 엔터테인먼트적인 사례들이 늘고 있다. 이러한 관심 증대로 인하여 모자이크 타일들의 크기 및 위치 모양 따라 다양한 형태의 모자이크를 생성하는 방법이 활발히 연구되고 있다[1, 2].

하지만 기존의 모자이크 생성기법들은 이미지의 특성과는 관계없이 균일한 크기의 지역을 사용하는 등의 제한이 존재한다. 따라서 본 논문에서는 효율적으로 모자이크 이미지 생성을 위하여 DCT(Discrete Cosine Transform) 해쉬[3] 기반의 모자이크 생성기법을 제안한다.

2. 관련연구

2.1 모자이크 이미지 생성 기법

모자이크 이미지를 생성하는 가장 단순한 기법으로는 그림 1과 같이 입력 이미지를 균일한 크기의 사각형으로 분할한 뒤 이미지 데이터베이스에서 가장 유사한 이미지를 찾아 모자이크를 생성하는 기법이다[4].

Fig. 1. Photo Mosaic Image Generation

하지만 이러한 방식은 모자이크를 만들기 위해서는 오랜 시간동안 많은 이미지 자료를 수집해야하며 이미지의 특성과는 관계없이 균일한 지역 크기를 사용하며 이미지의 크기에 따른 모자이크 표현에 제한이 있다.

이보다 조금 더 발전한 형태는 보로노이 다이어그램(Voronoi Diagram)을 이용하는 기법이다. 이 기법은 그림 2와 같이 입력이미지의 외각선에 모자이크 지역을 배치시키고 각 지역 간의 적당한 모양을 갖게 하여 모자이크 이미지를 생성하는 방식이다[5, 6].

Fig. 2. Mosaic Image using Voronoi Diagram

하지만 이 기법은 색인을 구축하는데 상당한 시간이 필요하며 선형으로 모든 이미지를 비교하기 때문에 계산 복잡도가 크다는 단점이 존재한다.

2.2 DCT 해쉬 함수

DCT 해쉬 함수는 코사인 측정(cosine measure)에 기반을 둔 함수이다. DCT 함수는 코사인을 유사도 측정지표로 사용할 때 모든 벡터로부터 모평균을 추출하는 장점이 존재한다. DCT 해쉬 함수는 이미지의 특징 표현을 위한 인덱스 구조를 생성하는데 사용된다. 이렇게 생성된 인덱스 구조는 원본이미지와 데이터베이스 이미지간의 유사도 측정을 위해 사용한다. 유사도 계산에 있어서는 다수의 이미지 지역이 존재하기 때문에 계산 복잡도가 상당히 크다. 하지만  DCT 해쉬 함수를 사용하게 되면 BNT(Bivariate Normal Tail) 해쉬 함수[7]보다 계산 복잡도면에서의 성능이 우수할 뿐만 아니라, 이미지의 특징 추출 및 검색 능력도 우수한 것으로 알려져 있다. DCT 해쉬 함수를 이용하여 해쉬 셋을 생성하기 위해 1...U까지의 U의 값을 정한다. 여기서 U는 매우 큰 정수이다.

이미지 각 블록에서 추출되는 각각의 특징 벡터는 H길이로 해쉬하여 사용한다. 먼저 해쉬 함수를 이용하여 입력벡터 A를 N차원의 입력벡터로 만들고, 해당 입력벡터에 대하여 DCT 해쉬를 수행함으로써 데이터베이스 이미지에 대한 해쉬 셋을 생성할 수 있다. 이렇게 만들어진 해쉬 셋은 가장 유사한 이미지를 검출하기 위해 사용된다.

데이터베이스 이미지 리스트 L은 식 1과 같이 표현할 수 있다.

                  (1)

유사한 이미지 검출 과정은 다음과 같다. 먼저 데이터베이스 이미지 리스트에 대해 해쉬 압축을 수행한 뒤 원본 이미지와의 비교를 통해 검색 히스토그램을 생성한다. 다음으로 생성된 히스토그램을 이용하여 랭킹을 산정하고 가장 랭킹이 높은 이미지를 최종적으로 가장 유사한 이미지로 결정한다.

3. DCT 해싱을 이용한 모자이크 기법

본 논문에서 제안하는 모자이크 생성 알고리즘은 DCT 해싱을 이용한 이미지 해쉬 셋 생성 단계와 유사도 계산을 통한 모자이크 생성 단계로 구성된다. 

Fig. 3. DCT Hash Algorithm

3.1 DCT 해싱을 이용한 해쉬 셋 생성

유사한 이미지를 검출하기 위한 기존의 방식[8, 9]은 원본 이미지에서 추출한 특징벡터(Feature vector)를 데이터베이스 이미지의 특징벡터와 하나씩 비교해보는 방식으로 동작한다. 즉, 선형검색(Linear search)을 통하여 유사도가 가장 큰 이미지가 검출되는 방식이다. 그러나 이러한 기존의 방식은 모든 이미지를 선형적으로 비교해야하기 때문에 이미지수의 증가에 따라 계산복잡도가 커지는 문제점이 발생한다. 이와 같은 복잡도 문제를 줄이기 위해 본 논문에서는 이미지의 특징벡터를 효과적으로 비교하기 위한 방법으로 DCT 기반의 DCT 해쉬를 도입하여 사용하고자 한다[10, 11, 12].

그림 3은 DCT 해쉬 알고리즘을 보여준다. 먼저 DCT 해쉬 연산을 위한 입력벡터(V’)를 생성하기 위하여, 해쉬의 전체 크기(U), 입력 벡터의 길이(N), 입력벡터(V)가 반복되는 횟수(d), 0을 채워넣는 길이(r) 등을 식(2)와 같이 결정한다.

                   (2)

이러한 연산을 통해 입력벡터는 DCT 해쉬를 위한 일정한 크기의 벡터로 만들어진다. 여기서 DCT 연산을 수행하기 전에 계산 복잡도를 줄이기 위하여 입력벡터는 으로 스케일되고, 스케일된 입력벡터는 DCT 연산을 통해 해쉬 값을 생성한다. 연산을 통해 해쉬 값을 갖게 되는 입력벡터들은 가장 작은 해쉬 멤버부터 오름차순으로 인덱싱되어 저장된다. 최종적으로 입력벡터의 인덱스들이 해쉬 셋을 구성하게 되며 모자이크를 만들기 위한 이미지 검색에 사용된다[8, 9].

3.2 DCT 해쉬를 이용한 모자이크 생성

Fig. 4. An example of over-sampling regions

모자이크 이미지 생성을 위해서 데이터베이스 내의 이미지와 원본 이미지의 해쉬 셋을 만드는 과정이 필요하다. 데이터베이스 및 원본 이미지의 해쉬 셋을 만들기 위해 본 논문에서는 그림 4와 같이 각각의 이미지를 중복 없는 영역으로 분할한다. 먼저 원본 이미지를 분할하여 각 영역에 DCT 해쉬를 통해 해쉬 셋을 생성한다. 데이터베이스의 이미지들은 사전 작업으로 DCT 해쉬를 통해 해쉬 셋을 생성하였고 저장되어 있다. 원본 이미지의 각 분할 영역과 유사한 이미지를 검색하기 위하여, 원본 이미지의 각 분할 영역에 대한 해쉬 결과와 사전에 구축된 데이터베이스의 해쉬 셋을 비교한다. 이 때,  해쉬 셋의 각 인덱스에 적중되는 적중률을 기반으로 나열한 뒤 가장 많이 일치하는 인덱스를 갖는 이미지가 가장 유사한 이미지로 선택된다. 검색된 이미지는 원본 이미지의 해당 분할 영역의 크기에 맞도록 조절되고 원본 이미지를 대체함으로써 모자이크 이미지가 생성된다. 그림 5는 위와 같은 과정을 거쳐 생성된 모자이크의 예이다.

Fig. 5. Examples of DCT hashing based mosaic images

4. 실험결과

본 논문에서 제안한 DCT 해쉬를 이용한 모자이크 생성 알고리즘의 성능을 평가하기 위하여 데이터베이스를 구성하는 이미지의 갯수, 데이터베이스 내 이미지의 분할 크기, 원본 이미지의 분할 크기 등을 변화시키면서 생성되는 모자이크 이미지를 비교하였다. 또한 이미지의 특성에 따른 결과를 확인하기 위하여 단조로운 이미지와 복잡한 이미지 두 가지 경우의 원본이미지 대비 생성되는 모자이크 이미지를 비교 분석하였다. 데이터베이스 이미지는 총 100장으로 구성하였고, 원본이미지의 크기는 900*900으로 고정하였다. 데이터베이스로 사용되는 이미지의 크기는 500*500으로 설정하였다.  

4.1 데이터베이스 이미지 수에 따른 결과

그림 6과 7는 데이터베이스 이미지 수를 변화시키면서 모자이크를 생성한 실험 결과이다. 본 실험을 위해 데이터베이스의 이미지 개수를 25개, 50개, 100개로 변화시키면서 순서대로 실험을 진행하였다.

데이터베이스의 이미지 수가 증가함에 따라 비교 가능한 해쉬 셋이 많아지기 때문에 원본 이미지의 특징에 더욱 유사한 이미지를 찾아낼 수 있다. 이로 인해 데이터가 많이 질수록 선명하게 향상된 모자이크 이미지가 생성됨을 확인 할 수 있다. 또한 단조로운 이미지와 복잡한 이미지 두 가지의 경우에서도 모자이크가 생성되지만 단조로운 이미지에서 더욱 좋은 결과를 보임을 알 수 있다.

Fig. 6. Results of simple image with varying number of database images.

Fig. 7. Results of complex image with varying number of database images.

4.2 데이터베이스 이미지 분할에 따른 결과

그림 8과 9는 데이터베이스 이미지의 지역 분할 수에 따른 모자이크 생성 결과이다. 데이터베이스의 이미지 수는 100개로 고정하고 이미지의 분할 영역의 수를 4개, 16개, 64개, 100개로 변화시키면서 모자이크를 생성하였다.

Fig. 8. Results of simple image with varying number of regions in the database images.

Fig. 9. Results of complex image with varying number of regions in the database images.

데이터베이스 이미지의 영역 분할의 수가 많은 경우 원본 이미지의 분할 영역의 크기보다 데이터베이스의 분할 영역의 크기가 더 작게 분할되는 경우가 발생하여 모자이크 생성 능력에 영향을 미친다. 또한 복잡한 이미지일수록 이미지 특징 정보가 더욱 부족하여 모자이크 생성 능력이 단조로운 이미지에 비해 나빠지는 결과를 확인할 수 있다.

4.3 원본 이미지 분할에 따른 결과

그림 10과 11는 원본 이미지 영역 분할 수에 따른 모자이크 생성 결과를 나타낸다. 본 실험을 위해 데이터베이스의 이미지를 100장으로 설정하였고 원본이미지 분할 영역을 900개(30x30), 3600개(60x60), 8100개(90*90)로 변화시키면서 실험을 진행하였다.

원본 이미지 분할이 많은 경우 적은 면적의 지역 특징을 추출하기 때문에 원본 이미지에 유사도가 높은 모자이크가 생성된다. 즉, 비교해야할 이미지가 좁은 지역의 특징을 잘 표현할 수 있기 때문에 원본 이미지에 가까운 모자이크를 생성해 낼 수 있는 것이다. 또한 영역의 수가 일정 수치 이하일 때, 단조로운 이미지인 경우가 복잡한 이미지인 경우에 비해 모자이크 생성 능력이 월등히 좋지만 지역의 수가 많아지면 단조로운 이미지 및 복잡한 이미지 모두 원본에 가깝게 모자이크가 생성되는 것을 확인 할 수 있다. 원본이미지의 분할 지역의수가 증가하면 원본 이미지와 비슷한 좋은 성능의 모자이크를 생성하지만 각각의 지역에 대해 수많은 비교를 행해야하므로 연산복잡도가 올라가 수행시간은 상대적으로 길어진다.

Fig. 10. Results of simple image with varying number of regions of original image.

Fig. 11. Results of complex image with varying number of regions of original image.

5. 결론

본 논문에서는 DCT 해쉬를 이용한 모자이크 생성 기법을 제안하였다. 제안한 알고리즘의 성능을 평가하기 위하여 이미지의 복잡도 및 이미지 분할 영역의 갯수, 데이터베이스를 구성하는 이미지의 수 등을 변화시켜 모자이크 이미지를 성생하였고, 각 설정에 따라 생성되는 모자이크 이미지를 비교 분석하였다. 실험을 통해 원본 이미지의 분할 영역의 개수가 증가함에 따라 원본이미지와 매우 유사한 모자이크 이미지가 생성되는 것을 확인하였으며 데이터베이스의 이미지 개수가 증가함에 따라 생성되는 모자이크 이미지도 역시 향상됨을 확인하였다. 또한 실험결과를 통해서 확인할 수  있듯이 데이터베이스의 이미지 영역의 크기가 원본 이미지의 영역 크기보다 작을 경우 원본의 특징을 효과적으로 표현하지 못하기 때문에 모자이크 생성 결과가 좋지 않음을 확인할 수 있다. 따라서 효과적으로 모자이크를 생성하기 위해서는 원본 이미지의 영역의 크기보다 데이터베이스 이미지의 영역의 크기가 작아지지 않도록 영역 분할에 대한 제한이 필요하다.

본 논문에서 제안한 방식은 해쉬 셋을 이용하여 유사도를 계산하기 때문에 기존의 순차 검색을 사용하는 방식보다 빠른 수행 속도를 갖지만 데이터베이스의 이미지 갯수 및 분할 영역의 수가 많아질 경우에는 연산복잡도가 증가하여 모자이크를 구성하는데 많은 시간이 필요하다는 것을 확인하였다. 향후 연구로는 이미지의 수 및 지역의 수가 증가했을 경우의 유사 이미지 검색 방법 등의 추가적인 연구가 진행되어야 할 것이다.

References

 [1] J. l. Baek, K. T. Song, W. K. Choi, K. U. Yu, P. W.  Lee, H. J. In, Cheoljung Kim, K. S. Yeo, S. S. Kim, "Study for the Pseudonymization Technique of Medical Image Data," Asia-pacific Journal of Multimedia Services Convergent with Art, Humanities, and Sociology, vol. 6, no. 6, pp. 103-110, June 2016.

   DOI: http://dx.doi.org/10.14257/AJMAHS.2016.06.28

 [2] J.-H. Lee, D.-H. Cho, “Palm Lines Extraction on a High Resolution Image using Mosaic-like Method,” Asia-pacific Journal of Multimedia Services Convergent with Art, Humanities, and Sociology, vol. 6, no. 3, pp. 9-17, Mar. 2016.

   DOI: http://dx.doi.org/10.14257/AJMAHS.2016.03.07

 [3] M. Kafai, L. An, B. Bhanu, “Reference Face Graph for Face Recognition,” IEEE Transactions on Information Forensics and Security, IEEE, vol. 9, no. 12, pp. 2132-2143, Dec. 2014.

   DOI: http://dx.doi.org/10.1109/TIFS.2014.2359548

 [4] A. Hausner, “Simulating decorative mosaics,” In Proc. of the 28th annual conference on Computer graphics and interactive techniques, ACM, pp. 573-580, 2001.

   DOI: http://dx.doi.org/10.1145/383259.383327

 [5] D. Blasi, Gianpiero, G. Gallo, Maria P. Petralia, “Smart Ideas for Photomosaic Rendering,” Eurographics Italian Chapter Conference, vol. 2006, pp. 267-272, 2006.

 [6] D. Kang, Y.-S. Park, S.-H. Seo, K.-H. Yoon, “Two Layer Image Tile Mosaics,” In Proc. of EURO GRAPHICS, pp. 145-148, 2006.

 [7] A. Jain, B. Klare, U. Park, “Face matching and retrieval in forensics applications,” IEEE Transactions on Multimedia, IEEE, vol. 19, no. 1, Jan. 2012.

   DOI: http://dx.doi.org/10.1109/MMUL.2012.4

 [8] D. Huang, C. Shan, M. Ardabilian, Y. Wang, L. Chen, “Local binary patterns and its application to facial image analysis: A survey,” IEEE Transaction on Systems, IEEE, vol. 41, no. 6, pp. 765-781, Nov. 2011.

   DOI: http://dx.doi.org/10.1109/tsmcc.2011.2118750

 [9] T. Ojala, M. Pietikinen, T. Maenpaa, "Multi resolution gray-scale and rotation invariant texture classification with local binary patterns", IEEE Transaction on Pattern Analaysis and Machine Intelligence, IEEE, vol. 24, no. 7, pp. 971-987, July 2002.

   DOI: http://dx.doi.org/10.1109/TPAMI.2002.1017623

[10] Y.-S. Im, E.-Y. Kang, J.-P. Park, Improvement of DCT-based Watermarking Scheme using Quantized Coefficients of Image, The Journal of The Institute of Internet, Broadcasting and Communication (IIBC), vol. 14, no. 2, pp. 17-22, Apr. 2014.
DOI: http://dx.doi.org/10.7236/JIIBC.2014.14.2.17

[11] Y. M. Kwon, K. H. Kim, H. J. Kwon, “Digital Halftoning using DCT,” The Journal of The Institute of Internet, Broadcasting and Communication, vol. 13, no. 6, Dec. 2013.
DOI: http://dx.doi.org/10.7236/JIIBC.2013.13.6.79

[12] S.-B. Jang, I.-H. Jee, “Embedded Image Coding using Multiplierless DCT with Lifting Scheme,” The Journal of The Institute of Webcasting, Internet Television and Telecommunication vol. 6, no. 4, pp. 31-37, 2006.

이 주 용(Ju-Yong Lee)                   [정회원]
	•2016년 2월 : 상명대학교 정보통신공학과 (공학석사) •2016년 3월 ~ 현재 : 상명대학교 정보통신공학과 박사과정
<관심분야> CCN, 미래인터넷, 네트워크 보안

정 승 도(Seungdo Jeong)                [종신회원]
	•2001년 2월 : 한양대학교 전자통신전파공학과 (공학석사) •2007년 8월 : 한양대학교 전자통신전파학과 (공학박사) •2012년 3월 ~ 2015년 2월 : 한양사이버대학교 조교수 •2015년 3월 ~ 현재 : 상명대학교 정보통신공학과 조교수
<관심분야> 멀티미디어 색인, 정보검색, 패턴인식, Tensor 응용

이 지 훈(Ji-Hoon Lee)                   [정회원]
	•1998년 3월 ~ 2001년 8월 : 고려대학교 대학원 전자공학과 (공학 박사) •2001년 9월 ~ 2002년 3월 : 고려대학교 차세대인터넷 센터 Research fellow •2002년 4월 ~ 2012년 2월 : 삼성전자 종합기술원 전문 연구원
•2012년 3월 ~ 현재 : 상명대학교 정보통신공학과 조교수   <관심분야> 미래인터넷, CCN, M2M, 네트워크 보안, Electric Vehicle