[선형대수학] Change of Basis

Vaughan·2022년 8월 28일
DWTHaar Wavelet Transform기저변환
3

선형대수학

목록 보기
14/14
post-thumbnail

Image Compression idea

Basis의 특징

  • Basis는 하나의 동일한 subspace에 대하여 여러개 존재할 수 있다. 이때, subspace안의 벡터를 표현할 때 어떤 basis를 사용하여 표현하는지에 따라서 필요한 정보의 양이 달라질 수 있다. [이미지 압축의 아이디어]
  • Basis들은 subspace안의 모든 벡터들을 linear combination으로 표현할 수 있다.

→ 이런 basis의 특징들을 이용하여 어떤 벡터나 값을 아주 단순하게 표현하게 하는 basis를 찾을 수 있고, 현재의 복잡한 basis 대신에 단순한 basis를 이용하여 subspace를 표현하는 것이 바로 Change of Basis이다.

Example

R4\mathbb R^4상에 존재하는 벡터 v\bold v의 간단한 표현

  • standard basis 표현
    v=[2−22−2]=2[1000]−2[0100]+2[0010]−2[0001]\bold v = \begin{bmatrix} 2 \\ -2 \\ 2 \\ -2 \end{bmatrix} = 2 \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} -2 \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} + 2 \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} - 2 \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}
    → 이렇게 표현하면 컴퓨터는 각 standard vector에 곱해지는 상수값 2, -2, 2, -2 (4개)와 사용하는 basis의 벡터와 그 순사를 모두 저장해야한다.
  • 동일한 공간을 나타내는 다른 basis를 사용한 표현

    • basis

      {[1111],[1−1−11],[11−1−1],[1−11−1]}\left\{ \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix},\begin{bmatrix} 1\\ -1 \\ -1 \\ 1 \end{bmatrix},\begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \end{bmatrix},\begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix} \right\}

    • 표현

      v=0[1111]+0[1−1−11]+0[11−1−1]+2[1−11−1]\bold v = 0\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}+0 \begin{bmatrix} 1\\ -1 \\ -1 \\ 1 \end{bmatrix}+0 \begin{bmatrix} 1 \\ 1 \\ -1 \\ -1 \end{bmatrix}+2\begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix}

      → 이렇게 표현하면 사용하는 벡터가 1개 뿐이므로, 사용되는 벡터와 거기에 곱해지는 상수값 2만 저장하면 된다.

      ⇒ standard basis를 이용하여 표현 했던 것보다 훨씬 간단하게(=저장용량을 적게 사용하도록) 표현할 수 있다!


Image Compression Idea

1024×10241024\times 1024 pixel의 gray image(255255)를 나타내는 벡터 x∈R10242\bold x ∈ \mathbb R^{1024^2}. 이때 벡터 x\bold x의 각각의 픽셀 xix_i는 0−2550 -255 사이의 값(=11byte로 표현가능)을 가진다.

  • 각각의 픽셀 값을 모두 저장하려면 102421024^2개의 픽셀 값을 저장하기 위한 공간이 필요하다. → 102421024^2 byte 필요
  • Image Compression
    • 각각의 픽셀이 모두 검은색인 어떤 imgae를 저장한다고 가정해보자.
    • 아무런 처리과정을 거치지 않고 저장한다면 102421024^2개 픽셀값에 모두 255255(=black)값이 저장되어 102421024^2 byte를 이미지 표현에 사용하게된다.
      255[10⋮0]+255[01⋮0]+⋯+255[00⋮1]255\begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}+255 \begin{bmatrix} 0\\ 1 \\ \vdots \\ 0\end{bmatrix}+\cdots +255\begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{bmatrix}
    • 만약, 앞에서 보인 예시처럼 standard basis를 이용하여 이미지를 표현하지 않고 다른 basis를 사용하면 어떻게 될까?
    • 벡터[1,1,...,1]T[1,1,...,1]^T를 가지는 어떤 basis를 사용하여 이미지를 표현하면 다음과 같이 나타낼 수 있다.
      255[11⋮1]+0[1−1⋮−1]+⋯+0[−1−1⋮−1]255\begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix}+0 \begin{bmatrix} 1\\ -1 \\ \vdots \\ -1\end{bmatrix}+\cdots +0\begin{bmatrix} -1 \\ -1 \\ \vdots \\ -1 \end{bmatrix}
    • 0 이 곱해지는 의미없는 벡터는 무시하고, 의미있는 상수값 255가 곱해지는 벡터만을 컴퓨터가 저장하면 훨씬 작은 저장공간을 사용하면서 같은 이미지를 저장할 수 있게 된다.

→ standard basis의 결합으로 이미지를 표현하지 말고 다른 basis로 표현하면 저장공간을 아낄 수 있다.

*JPEG?

표준 이미지 형식 JPEG는 이미지를 각각의 8×88\times 8 block으로 나눈다.

(이미지 전체를 계산하기에는 계산양이 너무 많기 때문에 고안한 방식)


Discrete Wavelet Transform; DWT

Discrete Wavelet Transform

  • 아래의 Othogonal basis는 실제로 JPEG2000에서 사용하는 basis이다.
  • 영벡터가 아닌 직교벡터 8개는 서로 독립이므로 아래의 벡터들은 R8\mathbb R^8의 basis이다.
    [11111111],[1111−1−1−1−1],[11−1−10000],[000011−1−1],[1−1000000],[001−10000],[00001−100],[0000001−1]\begin{bmatrix} 1 \\1 \\1\\1\\1\\1\\1\\1 \end{bmatrix},\begin{bmatrix} 1 \\1 \\1\\1\\-1\\-1\\-1\\-1 \end{bmatrix},\begin{bmatrix} 1 \\1 \\-1\\-1\\0\\0\\0\\0 \end{bmatrix},\begin{bmatrix} 0 \\0 \\0\\0\\1\\1\\-1\\-1 \end{bmatrix},\begin{bmatrix} 1 \\-1 \\0\\0\\0\\0\\0\\0 \end{bmatrix},\begin{bmatrix} 0 \\0 \\1\\-1\\0\\0\\0\\0 \end{bmatrix},\begin{bmatrix} 0 \\0 \\0\\0\\1\\-1\\0\\0 \end{bmatrix},\begin{bmatrix} 0 \\0 \\0\\0\\0\\0\\1\\-1 \end{bmatrix}

💡 이처럼, orthogonal basis를 basis로 고르는 것이 가장 좋은 방법이다. (why?)


Interpretation of Harar Wavelet Basis

R4\mathbb R^4으로 생각해보기 - Harar Matrix 이해하기

  • R4\mathbb R^4의 Othogonal basis는 다음과 같다.
    [1111],[11−1−1],[1−100],[001−1]\begin{bmatrix} 1 \\ 1\\ 1\\ 1 \end{bmatrix} , \begin{bmatrix} 1 \\ 1\\ -1\\ -1 \end{bmatrix} ,\begin{bmatrix} 1 \\ -1\\ 0\\ 0 \end{bmatrix} ,\begin{bmatrix} 0 \\ 0\\ 1\\ -1 \end{bmatrix}
  • 다음 vector x\bold x를 Othogonal basis로 표현 해보자.
    x=[100100101101]\bold x =\begin{bmatrix} 100 \\ 100\\ 101\\ 101 \end{bmatrix}
    =[100100101101]=100.5×[1111]+(−0.5)×[11−1−1]+0×[1−100]+0×[001−1]=\begin{bmatrix} 100 \\ 100\\ 101\\ 101 \end{bmatrix} = 100.5 \times \begin{bmatrix} 1 \\ 1 \\ 1\\ 1 \end{bmatrix} + (-0.5) \times \begin{bmatrix} 1 \\ 1 \\ -1\\ -1 \end{bmatrix} + 0 \times \begin{bmatrix} 1 \\ -1 \\ 0\\ 0 \end{bmatrix} + 0 \times \begin{bmatrix} 0 \\ 0 \\ 1\\ -1 \end{bmatrix}

    • 첫번째 basis 벡터에는 벡터 x\bold x 요소들의 평균값을 곱한다.

      ∑i=14xi4=(x1+x2+x3+x4)−04\frac{\sum_{i=1}^4 x_i}{4} = \frac{(x_1 + x_2 + x_3 + x_4) - 0}{4}

    • 두번째 basis 벡터는 x\bold x를 반으로 나눴을 때(x1,x2x_1, x_2 / x3,x4x_3, x_4)위 요소의 합과 아래요소 합의 차이의 평균을 곱한다.

      (이때 나누는 기준은 vector의 값이 1 → -1로 변하는 위치이다)

      (x1+x2)−(x3+x4)4\frac{(x_1 + x_2) - (x_3 + x_4)}{4}

    • 세번째 basis 벡터는 첫번째 요소와 두번째 요소 차이의 평균을 곱한다.

      x1−x22\frac{x_1 - x_2}{2}

    • 네번째 basis 벡터는 세번째 요소와 네번째 요소 차이의 평균을 곱한다.

      x3−x42\frac{x_3 - x_4}{2}

      → basis 벡터에서 0이 아닌 요소만을 고려했을 때, 값이 음수인 부분과 양수인 부분 각각의 합의 차이의 평균값이 각 basis 벡터에 곱해지는 상수 값이 된다.

      양수인 요소들의 합 - 음수인 요소들의 합0이아닌 요소의 개수\frac{\text{양수인 요소들의 합 - 음수인 요소들의 합}}{\text{0이아닌 요소의 개수}}

  • 벡터 x\bold x를 압축시킬 수 있는 벡터 c\bold c 구하기

    • 벡터 c\bold c는 x\bold x를 압축시키기 위해 basis에 곱해지는 상수값들의 집합

    • WW는 wi\bold w_i를 column vector로 갖는 basis를 의미한다.

      x=c1w1+...+c4w4=[w1⋯w4][c1⋮c4]=Wc\bold x= c_1\bold w_1 + ... + c_4 \bold w_4 = [\bold w_1 \cdots \bold w_4] \begin{bmatrix} c_1 \\ \vdots \\ c_4 \end{bmatrix} = W\bold c

    • 따라서 위 수식을 다르게 표현하면 다음과 같이 벡터 c\bold c를 나타낼 수 있다.

      (WW는 서로 independence한 column vector로 이루어져 있기에, 역행렬을 갖는다.)

      c=W−1x\bold c = W^{-1}\bold x

    • c\bold c의 의미

      x\bold x를 WWbasis를 이용한 좌표계상의 좌표로 표현한 것이 바로 c\bold c이다.

      이렇게 표현한 c\bold c에서는 데이터를 저장할 때 사용되는 용량을 줄이기 위해서 정보량이 가장 위쪽으로 쏠리도록 구성하는 것이 일반적이다. (0은 저장하지 않기 때문)


loseless압축과 lossy압축

  • loseless 손실없는 압축이라는 의미

    • 0을 제외한 c\bold c의 값들을 그대로 저장한다.

    • 압축된 이미지를 클릭하는 순간 압축파일 c\bold c 왼쪽에 basis WW를 곱해지면서 원본이미지를 그대로 복원할 수 있다.

      Wc=WW−1x=xW\bold c = WW^{-1}\bold x = \bold x
  • lossy
    • 0을 제외한 c\bold c의 값 중에서 특히 0과 가까운 값은 근사하여 0으로 취급하여 저장한다. → 0으로 근사된 값은 저장하지 않음
    • 이렇게 압축을 했다가 복원하면 미세한 색의 차이가 1가지 색으로 뭉뚱그러지기때문에 약간의 손실이 발생한다.

Conditions for Good Basis

좋은 basis 선택의 조건

  • 빠른 계산이 가능해야한다. → DWT에서는 역행렬을 W−1=WTW^{-1} = W^T로 표현할 수 있기 때문에 빠른 계산이 가능하다.
  • 압축시 메모리 공간을 적게 차지하게 하는 basis를 선택해야한다.

응용

이미지는 기본적으로 2-D matrix형태이므로, 행렬에 대해서 압축을 하기 위해서는 Haar matrix가 필요하다.


Haar Wavelet Transform

최초의 DWT 변환 (변환방법의 한 종류임)

Kronecker Product

  • m×nm\times n 행렬 AA와 p×qp\times q 행렬 BB에 대하여 AA의 각각의 요소에 모두 행렬 BB를 곱하는 연산자.
  • 연산결과는 mp×nqmp\times nq 행렬이 된다.
  • A⊗BA\otimes B
    A⊗B=[a11Ba12B⋯a1na21Ba22B⋯a2n⋮⋮⋱⋮am1Bam2B⋯amnB]A \otimes B = \begin{bmatrix} a_{11}B & a_{12}B & \cdots & a_{1n} \\a_{21}B & a_{22}B & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}B & a_{m2}B & \cdots & a_{mn}B \end{bmatrix}
  • AA와 BB가 둘다 벡터라면, 이 연산은 외적과 동일하다.

Haar Matrix

n=2t(t=0,1,2,...)n=2^t (t=0,1,2,...)인 n×nn\times n행렬 HnH_n은 다음과 같이 정의된다.

(ImI_m은 m×mm\times m identity matrix를 의미한다.)

Hn={[Hm⊗[11]  Im⊗[1−1]]if n=2m[1]if n=1H_n = \begin{cases} \left[ H_m \otimes \begin{bmatrix} 1 \\ 1 \end{bmatrix} \ \ I_m \otimes \begin{bmatrix} 1 \\ -1 \end{bmatrix} \right] & \text{if } n=2m\\ \left[ 1 \right ] & \text{if }n=1 \end{cases}

→ 이렇게 정의된 Haar Matrix에서 각각의 column vector를 column vector의 크기로 나누어 정규화:normalize 해서 사용한다.

Example of Haar Matrix

H2=[111−1]H_2 = \begin{bmatrix}1 & 1 \\ 1 & -1 \end{bmatrix}
H4=[111011−101−1011−10−1]H_4 = \begin{bmatrix}1 & 1 & 1 & 0\\ 1 & 1 & -1 & 0 \\ 1 & -1 & 0 & 1 \\ 1 & -1 & 0 & -1 \end{bmatrix}
H8=[111010001110−100011−10010011−100−1001−10100101−10100−101−10−100011−10−1000−1]H_8 = \begin{bmatrix}1 & 1 & 1 & 0 & 1 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & -1 & 0 & 0 & 0 \\ 1 & 1 &-1 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 &-1 & 0 & 0 & -1 & 0 & 0 \\ 1 & -1 &0 & 1 & 0 & 0 & 1 & 0 \\ 1 & -1 &0 & 1 & 0 & 0 & -1 & 0 \\ 1 & -1 &0 & -1 & 0 & 0 & 0 & 1 \\ 1 & -1 &0 & -1 & 0 & 0 & 0 & -1 \end{bmatrix}

Haar Wavelet Transforms : 2-D DWT

  • n×nn\times n matrix AA가 n×nn \times n pixel의 gray image를 나타낸다. (n=2tn = 2^t)

  • HnH_n이 정규화된 Harr Matrix라고 하자.

    • 정규화된 Harr Matrix는 Orthogonomal matrix이다.
    • hi\bold h_i 는 HnH_n의 ii번째 column vector

  • HnTHn=InH_n^TH_n = I_n 임을 Orthogonal 행렬의 성질으로부터 알아낼 수 있고 이를 활용하여 나타낼 수 있다.

    → Orthogonal matrix는 역행렬이 전치행렬과 동일하다.

  • 이미지 파일을 압축하기 위해서는 original image matrix AA의 왼쪽에는 HnTH_n^T를 오른쪽에는 HnH_n을 곱해줘서 압축한다.

B=HnTAHn=[h1TAh1h1TAh2⋯h1TAhnh2TAh1h2TAh2⋯h2TAhn⋮⋮⋱⋮hnTAh1hnTAh2⋯hnTAhn]B = {H_n}^T A H_n = \begin{bmatrix} \bold {h_1}^TA\bold h_1 & \bold {h_1}^TA\bold h_2 & \cdots & \bold {h_1}^TA\bold h_n \\ \bold {h_2}^TA\bold h_1 & \bold {h_2}^TA\bold h_2 & \cdots & \bold {h_2}^TA\bold h_n \\ \vdots & \vdots & \ddots & \vdots \\ \bold {h_n}^TA\bold h_1 & \bold {h_n}^TA\bold h_2 & \cdots & \bold {h_n}^TA\bold h_n\end{bmatrix}

Haar Wavelet Transforms의 특징

  • 정보량이 Left-Top으로 모인다. (아래쪽에는 0)

    • 전체 pixel의 평균값을 나타내는 성분 h1TAh1\bold {h_1}^TA\bold h_1이 B11B_{11}에 위치한다.
    • 또한 BnnB_{nn}으로 갈수록 적은 픽셀간의 차이만 나타내기 때문에 0에 가까운 값을 가지게 된다.

  • 이 특징을 이용해서 압축 matrix BB에서 데이터가 많이 모여있는 부분만 저장하고 다시 압축을 풀면, 차이는 있겠지만 여전히 AA와 비슷한 이미지를 띈다.

    A^=HnB^HnT\hat A = H_n \hat B {H_n}^T

Orthonomal matrix

Orthogonal + nomalize

Orthonomal matrix

n×nn\times n matirx Q=[q1, q2,⋯ , qn]Q = [\bold q_1,\ \bold q_2, \cdots , \ \bold q_n] 에서 각 column 벡터가 다음 성질을 만족하면 Orthonomal matrix이다.

qiTqj={1(i=j)0(i≠j)\bold{q_i}^T\bold{q_j} = \begin{cases} 1 & (i=j) \\ 0 & (i \neq j)\end{cases}
  • i=ji=j 일 때, 11 → 각 열벡터들의 자기자신의 내적이 11이므로 이는 column vector가 길이가 1인 nomal vector라는 것을 의미한다.
  • i≠ji≠j 일 때, 00 → 각 열벡터들간의 내적이 00이므로 서로 직교(Orthogonal)관계라는 것을 의미한다.

💡 따라서 행렬 QQ는 각 열벡터의 길이가 1이고 서로 직교인 열벡터들로 이루어져 있다.


Orthogonomal 행렬의 역행렬이 전치행렬과 같은 이유

Orthogonomal matrix QQ에 대하여,

QTQQ^TQ를 계산하면 Orthogonomal 행렬의 정의에 의해 항등행렬이 결과로 나타나게 된다.

qiTqj={1(i=j)0(i≠j)\bold{q_i}^T\bold{q_j} = \begin{cases} 1 & (i=j) \\ 0 & (i \neq j)\end{cases}
QTQ=[q1T⋮qnT][q1⋯qn] =[q1TAq1q1Tq2⋯q1Tqnq2Tq1q2Tq2⋯q2TAqn⋮⋮⋱⋮qnTq1qnTq2⋯qnTqn]Q^TQ = \begin{bmatrix} \bold{q_1}^T \\ \vdots \\ \bold{q_n}^T\end{bmatrix} \begin{bmatrix} \bold{q_1} & \cdots & \bold{q_n}\end{bmatrix}\\\ \\ = \begin{bmatrix} \bold {q_1}^TA\bold q_1 & \bold {q_1}^T\bold q_2 & \cdots & \bold {q_1}^T\bold q_n \\ \bold {q_2}^T\bold q_1 & \bold {q_2}^T\bold q_2 & \cdots & \bold {q_2}^TA\bold q_n \\ \vdots & \vdots & \ddots & \vdots \\ \bold {q_n}^T\bold q_1 & \bold {q_n}^T\bold q_2 & \cdots & \bold {q_n}^T\bold q_n\end{bmatrix}
QTQ=IQ^TQ = I

→ 따라서 Q−1=QTQ^{-1} = Q^T 이다.

profile
Vaughan
우주의 아름다움도 다양한 지식을 접하며 스스로의 생각이 짜여나갈 때 불현듯 나를 덮쳐오리라.
이전 포스트

[선형대수학] Orthogonality

0개의 댓글