Change of basis example

Summary

MIT 선형대수학 강의 31은 Change of basis에 대한 내용이다. 여기에서는 강의 내용 중 소개된 wavelets basis를 이용해서 기저변환의 예제를 살펴보고, 더불어 기저변환을 통한 압축이 어떻게 이루어지는지 개념적인 부분을 확인한다.

입력 이미지는 grayscale 로 구성되어 있다. 실제 값은 아래 주소에서 0에 대한 숫자 이미지가 된다. 이 값을 행렬로 저장하고 image() 함수를 사용해서 실제 0인지 확인한다.

# source: http://scikit-learn.org/stable/auto_examples/classification/plot_digits_classification.html#sphx-glr-auto-examples-classification-plot-digits-classification-py
# input vector in standard basis, number 0
img <- matrix(c(0, 0, 5, 13, 9, 1, 0, 0,
              0, 0, 13, 15, 10, 15, 5, 0,
              0, 3, 15, 2, 0, 11, 8, 0,
              0, 4, 12, 0, 0, 8, 8, 0,
              0, 5, 8, 0, 0, 9, 8, 0,
              0, 4, 11, 0, 1, 12, 7, 0,
              0, 2, 14, 5, 10, 12, 0, 0,
              0, 0, 6, 13, 10, 0, 0, 0), nrow=8, byrow = TRUE)

# 행렬 내용을 확인한다.
img

##      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [1,]    0    0    5   13    9    1    0    0
## [2,]    0    0   13   15   10   15    5    0
## [3,]    0    3   15    2    0   11    8    0
## [4,]    0    4   12    0    0    8    8    0
## [5,]    0    5    8    0    0    9    8    0
## [6,]    0    4   11    0    1   12    7    0
## [7,]    0    2   14    5   10   12    0    0
## [8,]    0    0    6   13   10    0    0    0

# 아래처럼 heatmap을 사용할수 있다. 이때 자동정렬을 막기 위해 Rowv = NA, Colv = NA 옵션을 적용한다.
#heatmap(img, Rowv = NA, Colv = NA,col=paste("gray",1:99,sep=""))
grays = rgb(red = 0:255/255, blue = 0:255/255, green = 0:255/255)
heatmap(img, Rowv=NA, Colv=NA, col=grays, scale = "none")

# 이미지가 회전되어 있어서 행렬의 값을 뒤바꾼다.
rotate <- function(x) t(apply(x, 2, rev))
image(rotate(img))

아래와 같이 Harr wavelets basis를 정의하고, 몇 가지 특징을 살펴본다.

웨이블릿 기저 W는 8차원의 R^8 공간을 정의한다.
첫번째 컬럼 벡터 (1, 1, 1, 1, 1, 1, 1, 1) 은 constant vector 또는 average, DC term 이 된다.
두번째 컬럼 벡터 (1, -1, 1, -1, 1, -1, 1, -1) 은 고주파 high frequency 에 해당한다.
기저는 orthogonal 하다.
orthogonal matrix로 변환하면, 역행렬은 transpose만 하면 된다.
1, -1, 0으로 구성되어 있어, 계산이 단순한다. 빠르다.

# define wavelets basis: 8x8 in R^8 space
W <- matrix(c(1, 1, 1, 1, 1, 1, 1, 1,
             1, 1, 1, 1, -1, -1, -1, -1,
             1, 1, -1, -1, 0, 0, 0, 0, 
             0, 0, 0, 0, 1, 1, -1, -1,
             1, -1, 0, 0, 0, 0, 0, 0,
             0, 0, 1, -1, 0, 0, 0, 0,
             0, 0, 0, 0, 1, -1, 0, 0,
             0, 0, 0, 0, 0, 0, 1, -1), nrow = 8, byrow = FALSE)
W # orthgonal basis vector for haar wavelets

##      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
## [1,]    1    1    1    0    1    0    0    0
## [2,]    1    1    1    0   -1    0    0    0
## [3,]    1    1   -1    0    0    1    0    0
## [4,]    1    1   -1    0    0   -1    0    0
## [5,]    1   -1    0    1    0    0    1    0
## [6,]    1   -1    0    1    0    0   -1    0
## [7,]    1   -1    0   -1    0    0    0    1
## [8,]    1   -1    0   -1    0    0    0   -1

p = Wc 라는 공식을 보자.

p 는 standard basis 에서의 이미지 값이 된다. 즉, 위에서 img행렬의 각각의 요소가 된다.
W는 웨이블릿 기저이다.
c는 웨이블릿 기저 W를 사용했을 때 p를 나타내기 위한 W 기저의 계수 coefficients 정보가 된다.
즉, 표준기저에서의 이미지의 실제값은 기저를 변경해서, 웨이블릿 기저로 표현했을 때, 계수 c로 표현할 수 있다.
참고로, 위의 식은 동일 입력 공간에서의 기저의 변환(Change of basis) 에 해당한다. 따라서 강의 내용 중 변환 T에 대해서 고민할 필요가 없다.

그럼, 여기서 p와 W를 알고 있고, c를 구하고 싶다. c는 W의 역행렬을 통해서 구할 수 있다.

# find invertible matrix of W - Inverse of W
W_1 <- solve(W) # 역행렬 구하기
#W %*% W_1 # Identity 행렬이 됨을 확인함

# W의 계수를 찾는다.
# p = Wc => c = W-1 p
C = W_1 %*% img
C

##      [,1]  [,2]  [,3] [,4]  [,5]  [,6]  [,7] [,8]
## [1,]    0  2.25 10.50  6.0  5.00  8.50  4.50    0
## [2,]    0 -0.50  0.75  1.5 -0.25  0.25  0.75    0
## [3,]    0 -1.75 -2.25  6.5  4.75 -0.75 -2.75    0
## [4,]    0  1.75 -0.25 -4.5 -4.75  2.25  3.75    0
## [5,]    0  0.00 -4.00 -1.0 -0.50 -7.00 -2.50    0
## [6,]    0 -0.50  1.50  1.0  0.00  1.50  0.00    0
## [7,]    0  0.50 -1.50  0.0 -0.50 -1.50  0.50    0
## [8,]    0  1.00  4.00 -4.0  0.00  6.00  0.00    0

여기까지는 무손실 압축 lossless compression 에 해당한다. 만약 위의 계수 행렬 C에서 -2보다 크고 2보다 작은 값들을 0으로 버리면 어떻게 될까? 그리고 그렇게 작은 값들이 버려진 행렬을 C1 이라고 하면, C1을 통해 복구한 이미지는 원래 이미지와 얼마나 다를까?

# cutoff value between -2 and 2
C1 <- C
C1[C1 > -2 & C1 < 2] <- 0 # 작은 값들은 버린다. C1은 이미지에 대한 압축된 정보를 갖는다.
C1

##      [,1] [,2]  [,3] [,4]  [,5]  [,6]  [,7] [,8]
## [1,]    0 2.25 10.50  6.0  5.00  8.50  4.50    0
## [2,]    0 0.00  0.00  0.0  0.00  0.00  0.00    0
## [3,]    0 0.00 -2.25  6.5  4.75  0.00 -2.75    0
## [4,]    0 0.00  0.00 -4.5 -4.75  2.25  3.75    0
## [5,]    0 0.00 -4.00  0.0  0.00 -7.00 -2.50    0
## [6,]    0 0.00  0.00  0.0  0.00  0.00  0.00    0
## [7,]    0 0.00  0.00  0.0  0.00  0.00  0.00    0
## [8,]    0 0.00  4.00 -4.0  0.00  6.00  0.00    0

new_img <- W %*% C1  # C1에서 이미지를 복구한다.
image(rotate(new_img))

위에서 압축된 계수 정보 C1에서 복구한 이미지 new_img 는 원래 이미지 img 와 매우 유사함을 볼 수 있다. 얼마나 압축된걸까?

length(C[C != 0]) # 42

## [1] 42

length(C1[C1 != 0]) # 20

## [1] 20

0 이 아닌 갯수가 42에서 20개로 줄었다. 원본 이미지 대비 약 50% 정도 사이즈가 줄었다.

이상으로 기저변경을 통한 압축 효과를 살펴보았다.

Change of basis example

Kong, Seokkyu

2018 9 24

Summary