RLE 방식은 너무(?) 단순해서 지금과 같이 컴퓨팅 파워가 넘치는 시대에는 범용 PC 프로그램에서는 거의 사용되지 않는다. 하지만 몇 년 전만 해도 2G 피처폰만 해도 컴퓨팅 파워가 약해 RLE 방식의 그래픽 이미지를 사용하곤 했다. 빠른 이미지 처리를 위해서 당시 피처폰의 MPU로는 RLE 방식 이상의 고급 압축 알고리즘을 사용할 수 없었던 것이다.

필자는 십여 년 전에 공작 기계 조작 장치의 LCD 화면에 회사 로고 화면을 뿌리고 싶다는 의견을 받고는 기계 공작 장치에 임베드된 MPU의 능력을 감안해서 PCX 방식의 그래픽 포맷을 새로 만들어 로고를 바꿀 수 있는 인터페이스까지 C 코드로 간단하게 만들어 준 적이 있다. 이와 같이 데이터 압축률은 떨어지나 압축을 해제하는 데에는 가장 빠른 방식이 RLE 방식이라고 할 수 있다. RLE 압축 방식의 대표 주자는 1980~90년대 초반까지 많이 사용되었던 PCX 라는 이미지 압축 파일 형식이 대표적이다.

PCX( Personal Computer eXchange )

PCX는 그래픽 이미지를 저장하는 형식의 하나로, ZSoft 사에 의해 개발된 페인트브러시 비트맵 파일이다. 흑백과 컬러 모두 저장할 수 있으며, 윈도우에서 제공하는 그래픽 프로그램인 페인트브러시(Paintbrush)에서 이 형식을 사용하였다. RLE(Run-Length Encoding)방식이라는 간단한 압축 방법을 통해서 그래픽 정보를 압축한다. PCX는 처음에는 16컬러( 4bit )만을 지원하다가 IBM PC의 그래픽 환경이 발전함에 따라 256컬러( 8bit )를 지원하게 되고 나중에는 팔레트 개념( R.G.B )을 도임하면서 점차 확대되어 True-color 까지 지원할 수 있게 되었다.

PaintBrush 라는 프로그램에 대해 궁금하다면 프로그램의 설명과 그 시대의 컴퓨팅 환경에 대해서 쓴 [ PaintBrush PCX ] 블로그를 방문해 보자.

RLE 압축이 사용되는 경우는 같은 데이터 ‘값’이 선형적, 반복적으로 발생하는 경우를 예상할 때에 압축으로서의 의미를 가진다. PC 환경 초기의 8bit 컴퓨터 시절에는 사진 보다는 도트 그래픽과 같은 그림이 많았으며, 사진이라도 16컬러, 256컬러의 현대의 감각으로는 조악스러운 수준의 그래픽이 대부분이었다. 현대의 경우 핸드 디바이스로 보는 웹툰이 이 경우에 해당한다. 사실 흑백 웹툰의 경우는 RLE 방식으로도 꽤 훌륭한 이미지 압축 결과물을 기대할 수 있고, 현재에도 피처폰의 경우 독자적인 RLE 방식의 이미지 포맷으로 웹툰 및 사진 앨범 서비스를 하는 곳이 있다고 한다.

최초의 PCX는 2 ~ 4bit( 4 ~ 16 컬러) 색을 지원하는 RLE 인코딩을 했다. 그 후 256 컬러로 확장하고, 12bit 컬러 + 16 레벨 투명도로 변화하고, 후에 플레인 개념과 가변 팔레트 개념까지 도입하는 등 PC 환경과 비디오 카드가 CGA, 허큘리스, EGA, VGA 16 ~256 등으로 발전하면서 PCX 포맷도 다양해지고 복잡해진다.

허큘리스 카드는 길이가 33cm 달하는 괴물이었다. 가격도 10만원을 상회할 정도의 고가 사치품이었고 꿈의 그래픽 카드였다.

Run Length Encoding의 심볼과 코드(PCX 방식)

PCX 16컬러에서의 심볼은 “색상 값”이 되며 4색일 경우 0~3, 16색일 경우 0~15의 값이다. 16색일 경우 0~15의 값을 CPU 레지스터에 저장하기 위해서는 4bit( 2^4 = 16)가 필요하다. RLE의 코드의 구성 요소는 “Symbol” + “Code Flag” + “Run Length” 이다.

위 그림은 PCX의 인코딩 코드의 형태가 아니라 일반적인 플래그를 사용하는 RLE 코드 개념을 나타낸 것이다. PCX의 경우 길이 코드가 4b 부분을 사용하나, 4bit로는 16 픽셀 길이 밖에는 지정할 수 없어 플래그에 추가로 값을 지정하고 넘치는 길이 부분에 대하여 코드를 더 추가한다. PCX에서 사용하는 인코딩 방식은 위 그림보다 더 복잡하며 RGB 플레인 개념 및 동적 팔레트, 그리고 24bits True-color 형태로 진화하면서 더욱 복잡해진다. 이 글에서는 개념만을 다루므로 이해하기 쉽게 그림을 그렸다.

‘120311111111111201’ 의 예에서 중간에 심볼 ‘1’이 반복되는 경우에 RLE는 인코딩을 통해 압축 효과를 기대할 수 있다. 총 16개의 심볼로 구성되어 있으며 각 심볼당 4bit 씩을 출력할 경우64bit: 8byte가 필요하다. 위 그림에서 RLE Code의 구성은 심볼+플래그+길이로 되어 있다. PCX에서는 플래그를 2bit를 사용한다.

위의 그림에서 중복될 경우 6bits를 길이에 할당하여 최대 64개의 중복을 12bits로 표현할 수 있는 예를 들었다. 즉, 최대 4 x 64 = 256bits 의 코드를 12bits로 표시할 수 있어 244bits 의 잉여를 줄일 수 있다. 하지만, 위의 경우 9개의 중복 36bits를 12bits로 인코딩 하여 실질적으로 출력에서 24bits가 감소하고 중복되지 않는 7개의 심볼은 추가로 2bits 의 플래그 코드가 반드시 붙어야만 해서, 14bits의 추가 bits가 발생하게 된다. 위와 같은 방식의 인코딩으로 위의 샘플 데이터는 10bits를 줄일 수 있게 된다. 원본 데이터를 인코딩하고 디코딩 하는 데에 소모되는 CPU 자원과 시간 VS 10bits의 감소에 대한 타협이 있어야 한다.

위 그림에서 6bits를 사용한 RLE 인코딩에 있어서 길이 코드는 데이터의 특성에 따라 결정된다. PCX는 초기 300x240 크기의 PC 모니터 화면에서 시작되었고, 한 코드 블록에 화면의 수평 한 줄 씩 인코딩을 했으므로 길이 코드에 8bits 이상 사용할 일이 없으며, 실제로 4bits에서 시작하여 포맷이 바뀌어 나갔다.

위의 예시에서 플래그 코드를 1bit만 사용하여 중복 여부만 코딩 한다면 총 7 + 1 = 8bit를 추가로 감소시킬 수 있으며, 최대 64가 아닌 최대 9개의 중복( 자체 심볼 + 길이 8 )을 인코딩하게 한다면 2bits를 감소 시킬 수가 있어, RLE 방식으로 최대로 압축할 수 있는 잉여는 20bits로 64bits –> 44bits의 압축이 가능하게 된다.

RLE에 있어서 심볼의 정의, 플래그 코드의 정의, 길이 코드의 정의의 변화로 대상 데이터에 대한 압축 효율이나 계산의 복잡성 등이 달라지게 된다. 위의 샘플의 경우 2개의 심볼이 중복되는 경우는 RLE로 길이까지 인코딩 하면 오히려 플래그 2bits + 길이 4bits = 6bits로서 2bits가 더 소모되게 된다. 최대 길이를 2bits = 4 심볼까지로 조정하면 2글자 8bits를 출력하는 것과 소모되는 자원은 같다.

데이터 압축은 있어서 하드디스크 또는 원격 접속 상태에서의 입출력의 효율성을 높이기 위한 것을 우선적으로 고려하지만, CPU 내부에서의 처리 과정에 대한 고려와 알고리즘 구현의 용이성도 함께 생각해야 하므로, RLE에서 플래그를 사용할 때에는 8bit, 16bit, 32bit, 64bit CPU 레지스터의 크기도 함께 고려하는 것이 좋다.

플래그 방식의 RLE를 살펴봤습니다. 다음엔 Escape Sequence 방식의 RLE를 다뤄보기로 하겠습니다.

다음 글 : Run Length Encoding( BIN )

이전 글 : 데이터 압축의 개념과 기본 유형