QOI - O(n) 무손실 이미지 압축
(phoboslab.org)"Quite OK Image"
- PNG와 비슷한 크기로 RGB/RGBA 압축을 실행
ㅤ→ 압축은 20x-50x 빠르고, 해제는 3~4x 빠름
ㅤ→ 300 라인짜리 싱글 헤더 파일 C 코드 오픈소스
ㅤ→ SIMD 사용하지 않는 심플한 싱글쓰레드 구현체
- 기술 세부
ㅤ→ 단일 패스로 이미지 인코드/디코드
ㅤ→ 모든 픽셀을 한번만 건드리며, 각 픽셀은 4가지 방법중 하나로 인코딩
ㅤㅤ⇨ 바로 앞의 픽셀과 같다면 앞 픽셀의 run-length를 증가, 다르다면 새 픽셀을 뒤의 3가지 방법중 하나로 패킹
ㅤㅤ⇨ 기존에 처리했던 픽셀과 같다면 그 픽셀의 인덱스. 이를 위해 최근 64개 픽셀에 대한 배열을 가지고 있음
ㅤㅤ⇨ 이전 픽셀과 많이 차이가 없다면 그 RGBA 차이값을 저장
ㅤㅤ⇨ 앞의 3가지 방법이 실패하면 픽셀의 RGBA값을 저장. 단 앞의 픽셀과 다른 부분만 저장
약간 과장해서 표현하면 QOI는 PNG에서 zlib을 떼어내고 필터링만 남긴 뒤 개선한 것입니다.
PNG도 사용하는 zlib/gzip/DEFLATE 압축 알고리즘이 널리 쓰이긴 하지만 너무 오래 되어서 효율이 떨어지는 것도 있는데다, zlib을 비롯한 LZ77 류의 알고리즘은 "최근 바이트 중에 연속된 바이트가 똑같은 경우가 여럿 나온다"는 기본 가정을 가지고 있습니다(예: 입력이 "to be or not to be"일 때 "to be" 부분이 두 번 나온다는 걸 사용하는 것). 그런데 이미지는 이런 가정이 잘 먹히지 않는 데이터이기 때문에, PNG는 zlib을 사실상 엔트로피 코딩(다른 추가 맥락 없이 다음 바이트가 나올 확률을 토대로 압축하는 접근)용으로만 쓰고, 전처리 단계로 간단한 필터링을 써서 zlib에 들어갈 데이터를 가정에 최대한 맞추려고 합니다만 사실 그렇게 효율적이라 할 수는 없습니다.
현대적인 비손실 이미지 포맷에서는 크게 두 가지 방법으로 이를 개선하는데, PNG의 필터링에 대응하는 픽셀 예측을 개선하는 접근이 있고(필터링 종류를 크게 늘린다거나, 이미지의 다른 부분에 서로 다른 필터링을 적용한다거나), PNG의 zlib에 대응하는 엔트로피 코딩을 개선하는 접근이 있습니다. QOI의 접근도 유사하지만 단순성을 위해 픽셀 예측에 현재 위치 윗쪽에 있는 픽셀을 전혀 사용하지 않는다는 점과, 엔트로피 코딩을 포기하고 경험에 기반한 차이(delta) 코딩을 여러 개 마련했다는 점이 특징입니다. 특히 첫번째 특징 때문에 압축/해제 성능과는 별개로 PNG보다도 압축률이 떨어지는 편인데 이는 단순성을 조금 희생해서 개선이 가능할 것으로 보입니다.
다른 포맷을 대체할 용도로 쓰이긴 어렵겠지만, 코드가 심플하고 구현도 잘 설명해놔서 읽기 재미난 코드 인듯 합니다.
https://github.com/phoboslab/qoi/blob/master/qoi.h