[ Linear Algebra ] Data Compression With Low-Rank Approximation

해당 데이터 압축 방법은 제가 프로젝트 도중 학습 목적으로 직접 구현하기 위해서 사용한 방법이므로, 가장 효율적인 방법은 아닙니다.

대부분의 경우에 Singular Value Decomposition을 이용한 Low-Rank Approximation을 적용하시기를 권장드리지만, 그래도 혹시나 도움이 될 분들이 있을까 

정리 해놓으려고 합니다.

본글 시작하기 전에 해당 본문에 인용된 대부분의 사진과 개념은 edx에서 진행하는 Linear Algebra - Foundation to Frontier 강좌의 내용에서 발췌한 내용을 제

나름대로 이해해서 재구성한 글임을 밝히고 저작권 문제가 생길시 바로 삭제하겠습니다. 

< 사진 출처 : http://www.cs.utexas.edu/users/flame/LAFF/Notes/Week11.pdf >

원리는 아주 간단 합니다. 

바로 윗 사진에서 빨강컬럼 벡터와 멀리 떨어진 초록색 컬럼벡터, 두 컬럼벡터의 화소값은 차이가 크지만 빨강과 근접한 파랑, 검정은 비교적 비슷하다.

그러면 K개의 가장 거리가 먼 컬럼벡터를 이미지로 부터 추출하고 그 벡터들로 구성된 행렬 A를 가지고 원본 이미지와 비슷한 이미지를 

근사할 수 있지 않을까?( 해당 벡터들은 그 주변 컬럼벡터의 픽셀을 대표한다고 볼 수 있으므로 ) 에서부터 이야기가 시작됩니다.

자, 그러면 이제 본론으로 들어가볼까요?

원본 이미지 B가 512 x 512 행렬이고 K = 2 라고 가정했을때, 원본 이미지 행렬 B = {b0 | b1 | b2 |...| b511 }로 표현할 수 있고 B로부터 2(K값 만큼)개의 컬럼을 

추출해서 행렬 A = { a0 | a1}로 표현하되 사진에서와 같이 a0는 B의 첫번째 컬럼 b0, a1은 중간번째 컬럼 b256 이라고 생각 해봅시다.

A의 컬럼스페이스 C(A) 안에서  원본이미지 B의 제일 첫번째 컬럼벡터 b0와 제일 유사한 b0' 를 구하려면 C(A)안에서 벡터 b0에 제일 가까운 점을 찾기 위해서

벡터 b0를 C(A)에 투영(Projection) 하게 되는데, 이때 b0는 이미 C(A)안에 있으므로 b0를 C(A)에 투영한 결과는 a0 또는 그 자신이 됩니다. 이를 식으로 표현하면

가 됩니다. B에서 그 다음컬럼인 b1을 C(A)에 투영 시키면 b1은 C(A)의 요소인 a0 = b0와 유사하기 때문에

라고 할 수 있고 이런 식으로 B의 각 요소를 우항처럼 만들어서 치환하면 원본 이미지의 근사 이미지 B'는

가 됩니다. 여기서  를 꺼내면  가 되고 이는 결국 B를 C(A)에 투영시킨 결과가 됩니다.

여기에서 저희의 원래 목적인 데이터량이 어떤식으로 줄어드는지에 초점을 맞춰보면... 결국 일 때,

 B' = AW 이므로  B' 가 A와 W로 분해 되는데. 계산해보면 A는 512 x 2( 두개의 컬럼을 B에서 추출했으므로) , W 는 2 x 512 행렬이고,

원래의 요소 512 x 512 = 262,144개 에서 

(512 x 2) + (2 x 512) = 2,048개로 데이터가 줄었음을 알 수 있습니다. 물론 K 값이 2밖에 안된다면 B'는 B와 상당히 다른 영상이 되겠죠 !

마치

에서 보이는 것 처럼요! 마지막으로 ImageHandler에서 512 x 512 컬러이미지를 K = 100으로 근사한 이미지를 첨부합니다.

< 원본>

<근사 이미지 K = 100>

화질 차이가 보이시나요?

이상으로 포스팅을 마치겠습니다..! 혹시 질문이나 제가 틀린부분 있으면 댓글 달아주세요~

< 참고자료 : http://www.cs.utexas.edu/users/flame/LAFF/Notes/Week11.pdf >