lecture 31. Change of Basis; Image Compression

https://www.youtube.com/watch?v=0h43aV4aH7I&list=PLE7DDD91010BC51F8&index=33 

 

이번 강의는 change of basis를 다룰 것이며 이것은 이미지 압축에서 활용된다.

 

1. image compression

이미지는 pixel로 이루어져 있다. 각 pixel은 gray-scale을 알려주며 0부터 255까지이다. 이미지가 512x512라면 pixel은 \(512^2\)만큼 있다. 이미지를 1개의 vector로 표현하면 길이는 512x512이다. 만약 컬러 이미지라면 R,G,B를 구분해야하기 때문에 길이가 3배가 된다. 이것은 거대한 정보이기 때문에 압축을 하고 표준압축은 JPEG이다. 이것은 change of basis이다.

basis를 표현하는 방법에는 여러가지가 있다.

우선 standard basis이다. basis에 적절한 계수를 곱해 이미지를 표현할 수 있다.

다음에는 이런 basis가 있을 수 있다.

왼쪽부터 순서대로 단일 grat level일때, 반은 밝고 반은 어두울 때, 체커보드 같을 때 사용하면 좋을 vectors이다. 

마지막은 fourier basis인데 이것은 JPEG에도 사용된다. 512x512은 정보가 크기 때문에 8x8 block으로 나눈다. 

여기서 주목할 것은 아직까지는 픽셀의 손실이 발생하지 않았다는 것이다. 압축을 할때는 input signal을 앞에서 했던 것처럼 여러 개의 block으로 나눈 후 threshold 미만인 것을 제거하는데 이때 손실이 발생한다. 이것은 \(\hat{c}\)이라는 coefficient를 생성하며 \(\hat{c}\)은 many zeros로 이루어져 있다. 압축 과정의 마무리에는 다시 신호를 만들어내는데

위의 식을 사용하여 복구한다. 그리고 이것이 처음 신호와 같은 개수의 coefficient를 갖을 것이라는 보장은 없다.

 

fourier basis 대신 사용할 수 있는 것으로는 wavelets가 있다.

wavelets basis는 이런 식으로 쓸 수 있다. basis를 구성하는 vector들의 linear combination으로 다른 vector들을 만들어 낼 수 있다. 만약 basis를 변경하고 싶다면 방정식을 풀면 된다.

p는 standard basis에서의 좌표이고 W는 wavelets basis의 basis가 column은 matrix이다. 그리고 c는 basis를 변경하기 위해 필요한 계수이며 이것이 wavelets basis에서의 좌표이다. 따라서 \(c=W^{-1}p\)로 다른 basis에서 구한 좌표를 구할 수 있다.

여기서 good basis를 정의할 수 있다. 우선 matrix의 곱셈과 inverse matrix 모두 빠르게 계산할 수 있어야 한다. fourier basis는 FFT라는 것이 있고 wavelets basis는 FWT라는 것이 있어 빠르게 구할 수 있다.

wavelets basis를 보면 vector가 모두 orthogonal 하다. 이것은 길이로 나누어서 orthonomal하게 만들어 줄 수 있고 그러면 inverse matrix도 편하게 구할 수 있다. 그래서 wavelets basis는 good basis의 첫번째 조건을 만족한다.

good basis의 다음 조건은 적은 basis로 이미지를 다시 만들어내기 충분해야 한다는 것이다.

 

2. change of basis

 

x라는 old basis를 사용한 좌표에서 c라는 new basis를 사용한 좌표로 바꾸고자 한다. 이때는 x=Wc로 바꿀 수 있다.

이러한 두 matrix 사이에는 어떤 관계가 있을까? 이 둘은 similar하다. 그래서 \(B=M^{-1}AM\)이다.

그래서 basis를 바꾸면 새로운 좌표를 얻고, 새로운 행렬도 얻는데 이때 행렬들은 similar 하다.

 

마지막으로 저번 시간에 했던 것을 다시 다뤄보자.

교수님이 column에 들어갈 내용을 잘못적은 것 같다.

 basis의 transformation 결과를 안다면 위와 같이 적을 수 있고 이를 활용하여 A를 구할 수 있다.

마지막 예제를 보자. 신호처리나 이미지 압축에서 원래 사용하기 좋은 basis는 eigenvector이나 계산 시간이 걸리기 때문에 fourier basis나 wavelets basis를 사용하는 것이다. 이번 예제에서는 eigenvector를 basis로 사용해 볼 것이다. 그러면 \(T(v_i)=\lambda v_i\)일 때 A를 구해보자.

그래서 A를 구해보면 diagonal matrix임을 확인할 수 있다.