무손실 압축은 원상태로 회복이 가능한 압축 방법
코드 워드란 - 캐릭터를 특정 비트 패턴으로 바꾼 것으로 예를 들어 1byte짜리 캐릭터를 매칭 테이블을 통해 010과 같은 3bit 형태로 변환한 것을 코드 워드라고 한다.
RLE도 무손실 압축 방법의 하나로 반복되는 데이터(run이라고 함)를 압축하는 방법이다. text의 경우 별로 효과가 없지만 멀티미디어(예를 들어 a4스캔하면 흰 바탕이 쭉 연속되어있어서)에는 효과가 좋다.
RLE와 일반 데이터를 섞어서 표현하는 압축방법도 있음. RLE가 사용된 부분엔 +기호를 붙여서 +4abcd+6e 이런식
여기까지는 유명한 허프만 코딩 알고리즘에 대해 다루고 있다.
간단히 요약하면 단 단어들의 빈도수를 센다. 가장 적게 사용된 빈도의 합을 부모노드로 하는 2진트리를 만든다. 반복한다. 모든 트리를 만들고 나서 왼쪽경로로 가면 0 오른쪽 경로로 가면 1 (반대도 가능) 이렇게 코드를 만든다.
허프만 코딩은 prefix property를 만족한다. prefix property란 하나의 코드가 어떤 단어의 코드를 접두어로 사용하지 않는 특성을 말한다. 이 특징의 장점은 비트를 쭉 읽기만 해도 바로 단어와 연결이 된다는 것이다.
허프만 코딩을 위해선 전체 데이터를 쭉 읽은 뒤 갯수를 하나하나 세야하는 단점이 있었다. 그래서 실제론 허프만 코드북을 사용한다. 코드북에는 미리 정의가 되어있다.
팩스의 한 줄을 허프만 코딩을 이용해 압축하는 예제.
jpeg 특징 : high frequency data를 필터링해서 압축을 한다. 아래 그림이 그 과정.
Q값을 통해서 손실률을 결정할 수 있다.
jpeg 인코딩의 모드들 sequential은 하드웨어 속도가 느린경우 좋다. hierarchical 은 하나의 이미지에 여러 해상도를 갖고 있다.
rgb보다 YCbCr 모델이 표현 비트수가 작다(8bit*3 에서 4bit*3 으로 변환) 사람 눈은 색상보다 명도에 더 예민하기 때문에 이 모델을 사용해도 차이를 별로 느끼지 못한다. jpeg는 rgb 모델에서 YCbCr 모델로 바꾼다. 전환하는 공식이 있으며 이를 통해 압축률을 높인다.
jpeg 압축 과정 - 색상모델을 전환해 크기를 줄인다. Y화면, Cb화면, Cr화면 각각에 대해서(한 픽셀에 3개의 components가 있다) 가로세로 8*8 pixels인 블록들로 묶고 각 픽셀에서 128을 뺀다.
high frequency data를 제거하는 DCT과정을 거친 뒤 변형 허프만 코딩(코드북 이용)을 이용해 압축한다.
하나의 블록에서 제일 처음 픽셀이 DC component가 되고 나머지가 AC component가 된다. 각 픽셀 값들은 아래의 forward transform 공식에 따라 변환된다.(디코딩에서는 inverse) 이 값을 DCT 계수라고 부른다.
DCT 계수 - DC요소의 변화에는 민감하지만 AC요소의 변화에는 둔감하다는 인간 시각 시스템의 특징을 압축에 이용한다.
Y에는 luminance table CbCr에는 chrominance table을 이용, DCT 계수들을 이로 나누어 반올림한 몫을 저장한다. 여기서 많은 AC요소(high frequency)들이 0으로 변한다. 이를 Quantization이라고 한다.
압축 과정 예제.
한 블록은 위와 같은 순서로 파일에 저장되는데 이 때 허프만 코딩이 이용된다. 제일 첫번째인 DC계수는 이전 블록의 DC계수값과의 차이로 저장되고 나머지 AC계수들은 (0의 run length + 그 뒤에 오는 non zero의 값)을 이용해 허프만 코딩북을 참고해서 저장된다.
이 압축 예제와 밑에 나오는 DC, AC코딩북을 참조하면 알기 쉽다. 0 -2만 설명하면,
0의 run length+ -2가 속한 카테고리를 통해 (1/2)를 만들고 AC 코딩북에서 이를 찾으면 11011이다. 거기에 -2의 additional bit는 01 이므로 둘을 합쳐 1101101이 된다.
댓글
댓글 쓰기