이미지 압축 (Image Compression) - Haar Matrix 구현 (1)

작년 2학기 선형대수학 수업에서 교수님이 과제로 내주셨던 프로젝트이다. 이 교수님이 내주시는 과제는 구글에 검색해도 정보가 거의 없고 스스로 수업시간에 배운 개념으로 시작해서 알아서 구현해야 한다. 그 중에서도 이미지 압축 과제는 정말 많은 시간을 투자했고 결국 성공했다.. 1년 전까지만 해도 파이썬이나 매트랩등 다양한 언어로도 과제를 받아주셨다고 했는데 내가 수강했을 때는 오로지 only C언어로만 하라고 하셔서 더더욱 힘들었다.

해당 과제를 받고 구글에 검색해서 우연히 내 블로그를 발견한 학생들은 분명 어떤교수님인지 알고있을 거다. 이번 포스팅에서는 C언어로 구현했던 과제를 파이썬으로 재구현 해보려고 한다. ( 혹시 2학기에 찾다가 들어와서 C언어로 된것도 올려달라고 하면 안알려줄거임. 혼자 공부하는 맛이 있어야되고 이 과제를 날먹하게 둘 수 없지 )

Image Compression이 필요한 이유

1024 x 1024 픽셀의 gray image가 있으고 한 픽셀당 1 byte라고 하면 이 이미지를 저장하는데 드는 용량은 1024x1024 = 1,048,576 byte로 거의 1Mbyte이다. 이 예시만 놓고 보면 겨우 1메가를 압축할 필요가 있냐고 느낄수 있겠지만 이런 이미지가 수십억개가 있다고 가정한다면? 1024 x 1024가 아니라 더 큰 픽셀이라면? 이 이미지를 저장하는데 엄청난 비용이 소모된다.

하지만 (255, 1) -> 첫번째 basis에 255라는 스칼라를 곱한 값이 이미지 픽셀 값이다 / 라는 것만 저장 할 수 있게 만든다면? 반대로 엄청난 자원을 절약하는데 도움이 될것이다. 이러한 이미지 압축을 위해 사용되는 것이 Haar Matrix이다.

Discrete Wavelet Transform (DWT)

DWT는 JPEG2000 압축 방식에 사용되고 위와 같은 basis를 이용한다. 위의 basis는 서로 orthogonal하기 때문에 많은 이점이 있다. (이유는 선형대수학을 배운사람들은 알겠고 따로 포스팅 하려고 한다.). 위의 matrix가 DWT의 하나인 Haar Marix다. 실제로 사용할 때는 normalize를 함으로써 orthonormal matrix의 특성을 이용하여 계산을 좀더 용이하게 만든다.

Haar Matrix

 

 

Haar Matrix는 위와 같은 방법으로 만든다.

 

위와 같은 식으로 계산을 하게된다면 low frequency 픽셀은 좌측 상단으로, high frequency 픽셀은 우측 하단으로 몰린 matrix가 만들어진다. 만들어진 B matrix에서 high frequency 성분을 절삭하면 많은 용량을 아낄 수 있다.

위의 식의 H matrix는 orthonormal matrix기 때문에 transpose matrix를 반대로 곱해주면 압축을 해체 할 수 있다.