축소된 특이값 분해와 자료압축원리

도입

유튜브에서 화질 선택을 한번쯤 해본 경험이 있을 것이다.

이건 어떻게 작동하는 것이고 왜 화질을 낮추면 로딩 속도가 빨라지는 걸까?

선형대수학의 자료 압축 원리를 통해 알아보자

배경지식

기본

이전 포스팅 참고

고윳값 분해

\(n*n\) 행렬에 대해 다음 조건을 만족하는 행렬이 가능하다.

이러한 행렬 \(A\)에 대해

를 대각화 혹은 고윳값 분해라 한다.

이때 행렬\(D\)는 대각행렬로 \(A\)의 고윳값들을 크기순으로 나열한 것과 같고, 행렬\(P\)는 각각의 고윳값들을 크기순으로 열벡터로 나열한 벡터이다.

예를 들어 \(A = \begin{pmatrix} 2 & 1\\ 1& 2\\ \end{pmatrix}\) 라 하면, \(A\)의 고윳값은 3, -1이고, 고유벡터는 각각 \(\begin{pmatrix}1 \\ 1\end{pmatrix}\begin{pmatrix} 3 \\ 1\end{pmatrix}\) 이다.

이때의 \(D = \begin{pmatrix} 3 & 0 \\ 0 & 1 \end{pmatrix} \, \, P = \begin{pmatrix} 3 & 1 \\ 1 & -1 \end{pmatrix}\) 이다.

이 고윳값 분해는 여러 계산상의 이점과 기하적 의미가 있는데 자세한 내용은 해당 영상 참고

특잇값 분해

특잇값 분해는 고윳값 분해의 일반화된 버전이다.

임의의 \(m*n\)행렬 A에 대해 성립하며, 다음 형태를 말한다.

이때 \(U\)와 \(V\)는 Orthogonal Matrix (\(U^{T} = U^{-1}\))이고, \(AA^{T},\,A^{T}A\) 는 대칭행렬이다.

따라서 \(AA^{T}, \, A^{T}A\)는 전치대각화가 가능하므로 \(U, \, \Sigma,\, V\)의 값을 구할 수 있다.

이를 통해 \(\Sigma\)의 원소들은 행렬 \(A\)의 고윳값들에 제곱근을 씌워 내림차순으로 정리한 것임을 알 수 있다.

자료 압축 원리

여기서 자료라 함은 보통 이미지 한장을 말한다.

이미지 한장은 \(m*n\)로 나타낼 수 있으므로 항상 특잇값 분해가 가능하다!

이때 다음과 같은 축소된 특잇값 분해를 함으로써 이미지가 차지하는 메모리를 줄여 처리속도를 키울 수 있다.

특히, 마지막 과정은 특잇값 중 가장 작은 값들을 줄이면서 이미지의 화질을 줄이지만, 처리할때 차지하는 용량을 매우 효과적으로 줄일 수 있다.

$ m*n $ 흑백 이미지에 대해, 컴퓨터에서 계산할 때 차지하는 양은 다음과 같다. (바이트 기준)

이때 \(k\)값 앞에 4가 붙는 이유는 자료 저장 방식 (float32) 때문이다.

아래의 왼쪽 이미지는 실제 SVD를 통해 특잇값 벡터를 \(\frac{1}{6}\)로 축소한 이미지이다.

계산량은 절반으로 줄었지만, 시각적으론 큰 차이가 없어보인다!

Python Code

압축 함수

def img_com(image: NDArray) -> tuple[NDArray, NDArray, NDArray, bool]:
    """이미지를 RAM 덜 차지하는 행렬, 벡터, 행렬, bool(흑백 여부)로 반환하는 함수(선형대수학 이미지 압축 원리 참고)
    Args:
        image (NDArray): cv2로 읽어온 이미지
    
    Return: 
        tuple(행렬, 벡터, 행렬, 참/거짓(흑백 여부))

    Usage example:
        tu = img_com(dodo)

    Note:
        화질이 조금 나빠지나, 변수들을 다룰때 공간을 덜 차지함(저장된 사진의 크기는 동일함).
        이상.
    """
    if len(image.shape) == 2:
        U, S, VT = np.linalg.svd(image, full_matrices=False)

        S = S[:int(len(S)/6)]
        U = U[:, :len(S)]
        VT = VT[:len(S), :]

        return U, S, VT, True
    
    else:
        blu, gre, red = cv2.split(image)
        image1 = [blu, gre, red]

        U_list, S_list, VT_list = [], [], []

        for channel in image1:
            U, S, VT = np.linalg.svd(channel, full_matrices=False)

            S = S[:int(len(S)/6)]
            U = U[:, :len(S)]
            VT = VT[:len(S), :]

            U_list.append(U)
            S_list.append(S)
            VT_list.append(VT)

        return np.array(U_list), np.array(S_list), np.array(VT_list), False

되돌리는 함수

def img_cons(li: tuple[NDArray, NDArray, NDArray, bool]) -> NDArray:
    """img_com으로 변형한 이미지를 원리대로 되돌려놓는 함수.

    Args:
        li (tuple): img_com 함수로부터 나온 튜플
            - U (NDArray): U 행렬들
            - S (NDArray): S 벡터들
            - VT (NDArray): VT 행렬들
            - bool: 이미지의 흑백 여부

    Returns:
        NDArray: 복원된 이미지 행렬, cv2로 이미지화 가능

    Usage example:
        cv2.imwrite('image.jpg', img_cons(li))
    """
    U_list, S_list, VT_list, is_grayscale = li

    if is_grayscale:
        S_diag = np.diag(S_list)
        restored_image = np.dot(U_list, np.dot(S_diag, VT_list))
    else:
        restored_channels = []
        for U, S, VT in zip(U_list, S_list, VT_list):
            S_diag = np.diag(S)

            # 복원된 채널 계산
            restored_channel = np.dot(U, np.dot(S_diag, VT))

            # 추가: 데이터 유형 및 범위 설정
            restored_channel = np.clip(restored_channel, 0, 255)
            restored_channels.append(restored_channel.astype(np.uint8))

        restored_image = cv2.merge(restored_channels)

    return restored_image

설명은 주석으로 대신함.

느낀점

‘프로그래머를 위한 선형 대수’라는 책을 읽으며 수학 시간에 학습한 ‘벡터’의 추가적인 응용 및 정확한 정의와 이미지와 동영상 데이터를 행렬로 표현할 수 있다는 점을 깨달음.

특히 책을 읽고서 이미지와 동영상의 화질 조정이 어떻게 이루어지는지에 대한 궁금증이 생겨 다음과 같은 탐구활동을 진행함. 동영상은 이미지의 연속으로, 이미지는 행렬로 표현되며, 이를 특잇값 분해를 활용하여 크기를 효과적으로 줄일 수 있음을 알게 되었음.

특잇값 분해는 원본 행렬을 두 개의 행렬과 하나의 벡터로 분해하고, 주요 정보를 유지하면서 파일 크기를 줄이는 데 도움을 준다는 것인데, 이를 통해 압축 후 화질과 메모리 사용량 간의 균형을 맞추는 것이 가장 중요하다는 것을 깨달음.

특히, 축소된 특잇값 분해를 적용하면 이미지의 화질은 약간 줄어들지만, 메모리 사용량을 크게 줄일 수 있다는 것을 깨닫고 이미지를 압축해도 시각적으로 큰 차이가 없으면서 저장 공간과 처리 속도를 개선하기 위해선 특잇값 벡터를 1/6배로 짧게 하는 것이 가장 좋음을 파이썬 코드를 짜보면서 확인하였음.

해당 내용을 보고서로 작성하는 과정을 통해 책의 내용을 되짚어볼 뿐 아니라, 색상 이미지 또한 위의 과정을 거쳐보며 좀 더 보편적인 파이썬 이미지 압축 함수를 제작함.

해당 과정을 통해 자신이 희망하는 데이터, 인공지능 분야와 수학과의 긴밀한 유기성을 느끼고 또 이에 큰 흥미를 느껴 더 많은 응용 분야를 탐구하고자 하는 의지를 다지고, 보고서 내용을 학생들과 공유하며 코드를 최적화할 방안에 대해 서로 의견을 나눔.

추가로 특잇값 분해를 이해하기 위해 학습했던 고윳값과 고유벡터가 어떻게 활용되는지 좀 더 탐구해 보고자 하는 추가활동 또한 계획함.

이상.