SVD: Singular Vector Decomposition에 대해 다룬다. 각 수식이 어떤 의미를 가지고, 이미지 압축에 어떻게 사용되는지 설명한다. 본 글을 이해하기 위해 아래 개념을 이해하고 있어야 한다.
Vector: 크기와 방향을 가지는 양으로, 2차원 공간의 벡터는 $\vec{v}=\begin{bmatrix}u_1 & u_2\end{bmatrix}$와 같이 표현한다. 본문에서는 $v$ 형태로 표기한다.
Inversed matrix: $A$에 대한 역행렬로 $A^{-1}$로 표기하며, $A^{-1}A=I$라는 특징을 가진다.
Orthogonal matrix: 모든 column 벡터가 직교하는 행렬로, $AA^T=A^TA=I$라는 특징을 가진다. 동시에 $A^T=A^{-1}$이다.
Diagonal matrix: 주대각 성분을 제외한 모든 값이 0으로 $diag(u_1,u_2)=\begin{bmatrix}u_1 & 0 \\ 0 & u_2 \end{bmatrix}$와 같은 형태를 가진다.
선형 변환: $s\cdot \vec{v}$를 통해 벡터의 크기를 왜곡할 수 있다. 이미지 변환 중 "크기 변환" 참고.
Eigenvector의 특징
eigenvector는 고윳값으로 불리며, 선형 변환이 발생해도 방향을 유지하는 벡터를 말한다. eigenvector를 검색하면 다음과 같은 식이 나온다.
$$Av=\lambda v$$
식만 봐서는 모르겠으니, 한 단계씩 해석해 보자. $Av$는 벡터 $v$에 행렬 $A$를 곱해 선형 변환을 했다. 이 과정에서 대부분의 벡터는 왜곡된다.
$$Av=\begin{bmatrix}2 & 1 \\ 1 & 3 \end{bmatrix}v$$
하지만 같은 방향을 유지하는 벡터도 존재한다. 이 벡터를 eigenvector라고 부른다. 방향은 유지하고 있지만 크기는 바뀌었다. 따라서, 변형된 벡터를 $\lambda v$로 표현할 수 있다. $\lambda$는 크기를 조절하는 scaling factor 역할을 한다. eigenvector의 크기를 결정하는 $\lambda$를 eigenvalue라고 한다.
>>> eigenvalues, eigenvectors = np.linalg.eig(transformation_matrix)
>>> eigenvectors
[[-0.85065081 -0.52573111]
[ 0.52573111 -0.85065081]]
>>> eigenvalues
[1.38196601 3.61803399]다시 처음으로 돌아와 $Av=\lambda v$는 벡터 $v$에 $A$를 통해 선형 변환을 해도 여전히 $v$인 0이 아닌 벡터를 eigenvector라고 한다. 이때 eigenvector에 곱해진 scaling factor를 eigenvalue라고 한다.
행렬 재구성
eigenvector와 eigenvalue를 알면, 변환 행렬 $A$를 찾을 수 있다.
$$A=V\Sigma V^{-1}$$
$V$는 각 열이 eigenvector인 행렬이다. $\Sigma =diag(...eigenvalue)$로 eigenvalue를 담고 있는 diagonal matrix이다.
다시 말해, 행렬 A는 eigenvector와 eigenvalue로 분해할 수 있고, 이 값들을 통해 재구성할 수 있다. 이 개념이 이미지를 압축하고 재구성하는 과정에도 적용된다. 하지만 eigenvector는 n x n의 square matrix에만 적용 가능하다. 따라서 eigenvector 대신 singular vector가 등장한다.
SVD
orthogonal matrix $U$와 $V$에 대해 아래 식이 성립한다.
$$A=U\Sigma V^T$$
$A$는 m x n 크기의 행렬이며, $\Sigma$는 diagonal matrix이다. 식을 정리해 보면 다음과 같다.
$$AV=U\Sigma$$
이번에는 orthogonal matrix $V$와 선형 변환해도 여전히 orthogonal 한 $U$를 찾는 문제다.
식을 조금 더 정리해보면,
$$AA^T=U\Sigma V^T (V\Sigma^T U^T) $$
$$AA^T=U(\Sigma^T\Sigma)U^T$$
글 초반에 소개했던 행렬의 특성을 이용해 정리한 식이다. 위 식을 행렬로 시각화하면 다음과 같다.
눈치챘다시피 $U$는 eigenvector와 동일하다. $\Sigma^T\Sigma$는 diagonal matrix로 eigenvalue와 동일하다.
식을 $V$에 대해 정리하면,
$$A^TA=V(\Sigma^T\Sigma)V^T$$
따라서 $V$도 eigenvector와 같은 성질을 가진다.
용어 정리
$U$와 $V$는 singular vector로 eigenvector와 같은 의미를 가진다. $\Sigma$는 singular value로 eigenvalue와 동일하다.
$$A=U\Sigma V^T$$
- $U$: Left Singular Vector
- $V$: Right Singular Vector
- $\Sigma$: Singular Value
정리하면, $A$는 singular vector $U$와 $V$로 분해되며, $\Sigma$는 scaling 정도를 나타내는 singular value이다.
A = np.array([[1, 2], [3, 4], [5, 6]])
# Perform SVD (A = U * Σ * V^T)
U, sigma, Vt = np.linalg.svd(A)이미지 분해
이미지 가로 길이가 $w$, 세로 길이가 $h$일 때, 2차원 이미지는 $h\times w$ 행렬로 표현할 수 있다. 이미지 행렬을 $M$라고 할 때, 이미지는 다음과 같이 분해할 수 있다.
$$M=U\Sigma V^T$$
$$U=[u_1, u_2 ... u_h]$$
$$V=[v_1, v_2 ... v_w]$$
$$\Sigma=diag(\sigma_1, \sigma_2, ... \sigma_n)$$
SVD에 재밌는 특징이 있는데 singular value가 큰 값부터 내림차순으로 나열되어 있다는 점이다.
$\sigma$ 중 $\sigma_1$이 가장 큰 값을 갖는다. 즉, 첫 번째 값부터 순서대로 중요한 정보를 담고 있다.
이미지 행렬 $M$은 $\sum_{n=1} \sigma_n u_n v_n^T$으로 표현할 수 있다. 그런데 만약 정보를 전부 사용하지 않고, 중요한 정보 몇 가지만 사용하면 어떨까?
가로 500, 세로 600의 600 x 500 행렬에 대해 실험을 해보았다.
당연히 벡터를 많이 사용할수록 이미지가 선명해진다.
singular value를 시각화해보면 n = 184에서 이미 singular value 총합의 80%를 넘어간다. 184개의 singular vector만으로도 이미지의 80%를 복원할 수 있다.
만약 600 x 500 행렬을 모두 사용하면 총 300,000개의 정보가 필요하다. 하지만, n = 200이라면 600 * n + n + n * 500으로 총 220,200개의 정보만 있으면 된다.
따라서, SVD를 이용해 정보를 압축할 수 있다.
SVD 관련 코드
SVD는 np.linalg.svd를 통해 계산한다. full_matrices 옵션은 불필요한 벡터를 저장할지 결정한다.
"""이미지 분해 및 재구성"""
import numpy as np
from PIL import Image
import os
image_path = "object4.jpg"
output_dir = "svd_images"
image = Image.open(image_path).convert("L")
image = np.array(image, dtype=np.float64)
# Singular Vector Decomposition (SVD)
# Image: (600, 500), S: (500,), Vt: (500, 500)
# U: (600, 500) when full_matrices=False
# U: (600, 600) when full_matrices=True
U, S, Vt = np.linalg.svd(image, full_matrices=False)
# 이미지 재구성
for n in range(1, len(S) + 1):
singular_values = np.zeros((U.shape[1], Vt.shape[0]))
np.fill_diagonal(singular_values, S[:n])
reconstructed = np.dot(
U[:, :n],
np.dot(singular_values[:n, :n], Vt[:n, :]),
)
output_image = np.clip(reconstructed, 0, 255).astype(np.uint8)
# 단계별 이미지 저장
if n % 10 == 0:
output_path = os.path.join(output_dir, f"{n}.png")
Image.fromarray(output_image).save(output_path)"""Singular value 시각화"""
from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
image = Image.open("object4.jpg").convert("L")
image = np.array(image, dtype=np.float64)
U, S, Vt = np.linalg.svd(image, full_matrices=False)
cumulative_sum = np.cumsum(S)
total_sum = np.sum(S)
threshold_percentage_1 = 0.5
threshold_percentage_2 = 0.8
threshold_1 = total_sum * threshold_percentage_1
threshold_2 = total_sum * threshold_percentage_2
threshold_index_1 = np.argmax(cumulative_sum >= threshold_1)
threshold_index_2 = np.argmax(cumulative_sum >= threshold_2)
plt.figure(figsize=(14, 6))
plt.plot(range(len(S)), S, label="Values")
plt.axvline(
x=threshold_index_1,
color="lightcoral",
linestyle="--",
label=f"{threshold_percentage_1 * 100}% Threshold (Index: {threshold_index_1})",
)
plt.axvline(
x=threshold_index_2,
color="red",
linestyle="--",
label=f"{threshold_percentage_2 * 100}% Threshold (Index: {threshold_index_2})",
)
plt.xlabel("Index")
plt.ylabel("Singular value")
plt.ylim(0, S[0] + 1)
plt.legend()
plt.grid(True)
plt.show()참고자료