압축

이 글은 Crash Course의 Computer Science를 보고 정리한 글입니다.

  기본적인 텍스트, 소리, 그림의 파일 형식은 오늘날에도 여전히 사용될 정도로 완벽하지만, 동시에 이러한 형식의 단순함은 매우 비효율적이다. 이상적으로는 파일 크기를 가능한 작게 해서 하드 드라이브를 가득 채우지 않고도 파일을 많이 저장하고 빨리 전송하기를 원한다. 이러한 이상을 가능하게 해주는 것이 바로 데이터를 더 작은 크기로 바짝 붙이는 압축(Compression)이다. 이렇게 하려면, 원래 표현보다 더 적은 수의 비트를 사용하여 데이터를 인코딩해야 한다.

 

  이미지는 전형적으로 픽셀 값 목록으로 저장된다. 그리고 이미지 파일은 행의 끝을 알기 위해 이미지 파일은 차원과 같은 속성을 메타 데이터로 갖고 있으며, 파일의 실제 이미지 데이터에서 각 픽셀의 색상은 빨강, 녹색, 파랑 세 가지의 조합이다. 색상별로 0에서 255까지의 범위를 제공하고, 각 값을 1바이트로 저장한다. 전체(빨강, 녹색, 파랑) 강도를 255로 가장 높은 값으로 섞으면 흰색을 얻을 수 있고, 강도를 0으로 가낭 낮은 값으로 섞으면 검은색을 얻는다.

  만약 4X4 = 16픽셀의 그림을 표현한다면 각각 3바이트의 컬러 테이터가 필요하므로, 이 이미지의 데이터는 48바이트의 저장 공간을 소모하게 된다. 그러나 데이터를 꾸려서 압축하면 48보다 작은 숫자로 만들 수 있다. 데이터를 압축하는 한 가지 방법은 중복된 정보를 줄이는 것이다. 가장 간단한 방법은 RLE(Run-length Encoding)라고 불리는 방법이다. 이것은 파일 안에 종종 동일한 값이 있다는 사실을 이용한다.

  위와 같은 이미지를 예시로 든다면 4번째부터 10번째까지의 데이터가 노란색으로 연속되어있다. 이러한 중복된 데이터를 연속해서 인코딩하는 대신 실행 길이를 지정하는 여분의 바이트를 삽입함으로써 단순히 "7개 노란색의 연속"이라고 할 수 있다. 그다음에 뒤에 있는 중복된 데이터를 제거한다. 컴퓨터가 어떤 바이트가 실행 길이나 색상을 나타내는지 헷갈리지 않게 하려면 이 구조를 적용하는 방법이 일관적이어야 한다. 따라서 모든 픽셀의 실행 길이를 정해야 한다. 위의 그림은 RLE방법으로 표현한다면 아래와 같이 24바이트로 표현할 수 있고, bmp방식으로 표현했을 때(48바이트) 보다 훨씬 적은 저장 공간을 차지하게 된다.

또한 데이터가 손실되지 않았다. 어떠한 저하 없이 다시 원래대로 이미지를 표현할 수 있다. 이러한 특성을 지닌 압축 기술을 무손실 압축(Lossless Compression)이라고 한다. 왜냐하면 아무것도 잃지 않았기 때문이다. 압축 해제된 데이터는 압축하기 전의 비트들의 원본으로 돌아갈 수 있다.

 

  데이터 블록이 더 작은 표현으로 대체되는 무손실 압축의 다른 유형을 살펴보자. 이것은 "Don't Forget To Be Awesome"이 DFTBA로 대체된 방식과 비슷하다. 이렇게 하려면, 코드에서 데이터로 매핑하여 저장하는 사전이 필요하다. 예제를 통하여 좀 더 자세히 살펴보자.

  이미지를 개별 픽셀의 문자열이 아니라 데이터의 작은 블록으로 볼 수 있다. 단순하게, 6바이트 길이의 어떤 크기의 블록이든 될 수 있는 픽셀 쌍을 사용해 보겠다. 위의 4X4 이미지에서는 흰색-노랑, 검정-노랑, 노랑-노랑, 흰색-흰색 이렇게 4개의 쌍이 있다. 이것들은 사전에 있는 콤팩트 코드를 생성하고자 하는 데이터 블록이다. 여기서 블록들은 다른 빈도로 발생한다. 노랑-노랑의 쌍 4개, 흰색-노랑의 쌍 2개, 검정-노랑과 흰색-흰색 각각 1개가 있다. 노랑-노랑의 쌍이 가장 많은 블록이기 때문에, 가장 많은 콤팩트한 표현으로 대체하려고 한다. 반면에, 검정-노랑과 흰색-흰색은 드물기 때문에 더 길게 대체될 수 있다.

  이것을 효율적인 코드로 바꾸는 한 가지 방법은 David Huffman이 고안한 Huffman Tree이다. 1950년대에 그가 MIT의 학생이었을 때 만들어졌다. 이 알고리즘은 다음과 같다.

  먼저 모든 가능한 블록들과 빈도를 배치한다. 매 차례마다 최저 빈도 두 가지를 선택한다. 예제에서는 검정-노랑과 흰색-흰색으로, 각 빈도는 1이다. 이걸 합쳐서 작은 나무에 결합하면 빈도가 2가 되는데 이것을 기록한다. 이제 알고리즘의 한 단계가 완료되었다.

이제 위의 과정을 반복한다. 전과 마찬가지로, 가장 낮은 빈도 두 개를 골라 작은 나무에 넣고 모든 하위 항목의 새로운 총빈도를 기록한다.

다시 반복하여 Tree에 합친다.

  Tree는 빈도를 바탕으로 위와 같이 배열되었다.

  이제 빈도로 정렬된 Tree를 사용해서 각각의 가지에 0 또는 1 라벨을 붙여 필요한 코드를 생성한다. 이것으로 다음과 같이 코드 사전을 작성할 수 있다.

  이 코드 단어에는 부딪히는 코드가 없다. 왜냐하면 나무 아래에 있는 각 경로는 유일하기 때문이다. 즉, 이 코드는 접두사가 없고, 다른 완전한 코드로 시작하는 코드가 없다.(예시에서 보면 0 또는 10으로 시작하는 코드가 없다.)

  이제 이미지 데이터로 돌아가 이미지를 압축해 보겠다. 첫 번째 픽셀 쌍인 흰색-노랑은 비트"10"으로 대체된다. 다음 쌍은 거정-황색으로, "110"으로 바뀐다. 다음은 매우 콤팩트한 0으로 대체된 노랑-노랑이다. 이 과정을 반복하면 다음과 같다.

  이제 48 바이트의 이미지 데이터를 Huffman Tree를 이용한 코드 사전을 통하여 14비트로 인코딩하였다. 2바이트 미만으로 압축된 것이다. 하지만 이 데이터는 코드 사전을 저장하지 않으면 의미가 없다. 그래서, 이미지 데이터 앞에 이것을 첨부해야 한다.

  위와 같이 사전을 포함한 이미지 데이터를 보면 30바이트이다.

 

  위에서 논의한 두 가지 접근법(중복을 제거하고 보다 콤팩트한 표현을 사용하는 것)은 종종 같이 사용되어 무손실 압축 파일 형식의 기초가 된다.(ex - gif, png, zip 등) RLE와 사전 인코딩 모두 무손실 압축 기술이다. 이것은 압축을 풀 때, 정보의 손실 없이 원본 파일을 얻는다. 이것은 많은 유형의 파일에서 매우 중요하다.

 

  그러나 내용을 거의 변화하지 않고 압축할 수 있는 다른 유형의 파일 형식이 있다. 불필요하거나 덜 중요한, 특히 사람의 인식으로 탐지할 수 없는 것과 같은 정보들을 지워버리는 트릭이다. 그리고 이 트릭은 대부분의 손실 압축 기법(Lossy Compression Techniques)의 기초이다. 이것들은 꽤 복잡하기 때문에 개념적으로만 설명하려 한다.

 

  한 가지 예로 소리를 살펴보자. 사람의 청력은 완벽하지 않다. 사람은 소리의 일부 주파수를 더 잘 들을 수 있다. 그리고 초음파와 같이 전혀 들을 수 없는 것들도 있다. 기본적으로 음악을 녹음하고 초음파 주파수의 범위에 데이터가 있으면 사람들이 그것을 들을 수 없다는 걸 알고 있기 때문에 우리는 그것을 버릴 수 있다.

  반면에, 사람이 노래하는 것과 같은 보컬 범위의 주파수에 민감하기 때문에 가능한 한 최고의 품질을 유지하는 것이 가장 좋다. 저음은 중간쯤에 해당한다. 사람은 저음을 들을 수 있지만 덜 민감하다. 손실이 많은 오디오 압축기는 이를 이용하여 서로 다른 주파수 대역을 서로 다른 정밀도로 인코딩한다. 결과가 대충 만들어진다 해도, 사람은 그 차이를 인식하지 못할 것이다. 적어도 경험에 큰 영향을 미치진 않는다. (오디오 마니아라면 항의할 것이다.)

  이러한 유형의 오디오 압축은 흔하다. 핸드폰에서 통화할 때 직접 대화하는 것과 다르게 들리는 이유 중 하나다. 오디오 데이터가 압축되어, 한 번에 더 많은 사람들이 전화를 받는다. 신호 품질 또는 대역폭이 악화됨에 따라, 압축 알고리즘은 더 많은 데이터를 제거함으로 인해 Skype 통화에서 때로는 로봇이 말하는 것처럼 정밀도를 떨어트린다. WAV 또는 FLAC과 같은 비 압축 오디오 형식과 비교할 때 MP3와 같은 압축 오디오 파일은 10배 정도 더 작다.

 

  인간의 인식과 일치하는 방식으로 정밀도를 버리거나 줄일 수 있는 이 아이디어는 지각적 코딩(Perceptual Coding)이라고 하며, 인간의 인지 모델에 의존한다. 심리 물리학(Psychophysics)이라는 연구 분야에서 나온 것이다.

 

  이 같은 생각은 jpeg 파일 같은 손실 압축 이미지 포맷의 기초이다. 청력과 마찬가지로 인간의 시각 시스템도 불완전하다. 우리는 사물의 가장자리처럼 선명한 대조를 감지하는 데 정말 능숙하다. 그러나 우리의 인식 시스템은 미묘한 색상 변화를 잘 알아채진 못한다. JPEG는 이미지를 8X8 픽셀 블록으로 분할한 다음 고빈도 공간 데이터를 버리는 식으로 이점을 얻는다.

  예를 들어 왼쪽 아래 사진에서 8X8 픽셀 부분을 살펴보면 오른쪽 아래 사진과 같다.

  거의 모든 이웃한 픽셀이 다르기 때문에 손실이 적은 기술로 압축하기가 힘들다. 많은 작은 세부사항들이 존재하기 때문이다. 그러나 인간의 인식은 모든 세부사항을 기억하진 않는다. 그래서 그 세부사항을 많이 버려서 다음과 같이 단순한 조각으로 대체한다.

  이것은 시각적 본질을 유지하지만, 데이터의 10%만 사용한다. 이미지의 모든 부분에 이것을 적용하면 다음과 같은 결과를 얻을 수 있다.

  이미지가 거칠지만 여전히 개를 알아볼 수 있다. 이것은 약간 압축된 jpeg에서 원본 파일 크기의 1/8로 압축된 극단적인 예이다. 원본과 극단적인 압축의 중간 어딘가에서 질적으로 큰 차이가 나지 않는 어딘가가 존재할 것이다. 그리고 지각적으로는 기본적인 원본과 동일하다. 다음은 원본과 1/3로 압축한 사진이다.

 

  비디오 압축에서도 같은 방법이 존재한다. 비디오는 단지 긴 연속의 이미지로, 이전에 설명한 이미지 압축에 대한 많은 것들이 여기에도 적용된다. 그러나 비디오는 프레임 사이에서 많은 픽셀이 같을 수 있기 때문에 약간 더 영리한 방법을 사용할 수 있다. 이를 시간적 중복(Temporal Redundancy)이라고 한다.

  비디오의 모든 프레임마다 모든 픽셀을 다시 전송할 필요가 없다. 단지 데이터 조각을 복사하기만 하면 된다. 대부분의 비디오 포맷은 패치 간의 차이만 인코딩하는 데이터를 전송한다. 모든 픽셀을 다시 전송하는 것보다 효율적이다. 이것은 프레임 간 유사성(Inter-frame Similarity)의 이점을 이용한다.

  이것보다 더 효율적인 비디오 압축 포맷은 한 걸음 더 나아간다. 이 포맷은 프레임 사이의 유사한 패치를 발견하고, 차이 유무에 관계없이 앞으로 복사할 뿐만 아니라 교대 또는 회전과 같은 단순한 효과를 적용할 수도 있다. 또한 프레임 사이의 패치를 밝게 하거나 어둡게 할 수도 있다. 만약 사람이 손을 옆으로 움직이는 비디오를 이 포맷을 적용하여 압축한다면 비디오 압축기는 유사성을 식별하여, 하나 이상의 패치로 손을 잡은 다음 이 패치를 프레임 사이로 이동한다. 따라서 데이터를 훨씬 적게 사용한다.

  일반적인 표준인 MPEG-4 비디오는 종종 원본 파일보다 20~200배 작아진다. 그러나 이전 프레임들로부터 패치의 번역이나 회전을 인코딩하는 것은 심하게 압축하면 끔찍하게 잘못될 수 있다. 패치 내부에 픽셀 데이터를 업데이트할 공간이 충분하지 않다. 비디오 플레이어는 패치 데이터가 틀린 경우에도 올바른 동작을 적용하여 재생될 것이다. 그리고 다음과 같은 들썩거리는 trippy 한 효과를 보게 될 것이다.

 

  사용자가 사진과 음악, 비디오를 효율적으로 저장할 수 있기 때문에, 압축에 대해 아는 것은 중요하다. 압축이 없다면 좋아하는 BJ를 스트리밍으로 보는 것이 거의 불가능하다. 또한 대역폭과 무료로 대량의 데이터를 전송하므로 경제적이다.