Bloom 필터를 이용한 무손실 비디오 압축

(github.com/ross39)

이 오픈 소스 프로젝트는 Bloom 필터를 활용하여 무손실 비디오 압축을 실현함
Rational Bloom Filter 개념을 도입해 기존 Bloom 필터의 한계를 극복하고 효율적 압축 가능성을 탐색함
일반적인 코덱들과는 달리, 모든 데이터를 완벽하게 복원하는 무손실 압축을 보장함
프레임 전체가 아닌 프레임 간 차이에 집중하여 희소 데이터의 효율적 압축을 실현함
실험 결과와 검증 절차, 원리 설명을 통해 높은 신뢰도가 확보됨

프로젝트 개요

이 오픈 소스 프로젝트는 Bloom 필터(특정 값이 집합에 포함되어 있는지 빠르고 효율적으로 검증하는 데이터 구조)를 혁신적으로 변형하여 무손실 비디오 압축을 시도함. H.264 등 전통적인 비디오 코덱은 사람 눈에 보이지 않는 정보를 제거해 압축률을 높이지만, 이 방법은 정보 완전성을 잃음. 본 프로젝트는 완벽한 데이터 복원을 유지하면서도 파일 크기를 줄이는 방법을 시연함. 특히, Bloom 필터의 합리적(비정수) 해시 함수 개수 사용 방법과 프레임 Δ(차이) 기반 압축 구조가 기술적 특장점임.

주요 소스코드 안내

핵심 파일: youtube_bloom_compress.py
간단한 명령어 실행만으로 데모 동작 가능함
장기 영상에는 아직 속도상 한계가 있으며, 지속적인 최적화 진행 중임

Bloom 필터의 기초

Bloom 필터는 여러 해시 함수를 사용하며, 집합 안에 값이 있는지 검사하는 데 아주 적은 메모리만 필요함. 일부 오탐(false positive)는 허용하지만, 거짓 음성(false negative)은 절대 없어 신뢰성 보장에 강점이 있음.

혁신적 변화: Rational Bloom Filter

Bloom 필터의 최적 해시 함수 개수(k)는 보통 정수가 아님. 이에 Rational Bloom Filter는 실수형 k*를 활용:

항상 ⌊k*⌋개의 해시 함수 적용
남은 부분만큼 추가 해시 함수 확률적 적용(예. k* = 2.7이면 70% 확률로 세 번째 해시 사용)
각 원소마다 이 확률적 결정이 일관성 있게 이뤄지도록 설계함

이 방식이 압축 및 복원 시 모두 정확히 동작해 압축 신뢰도를 높임

Bloom 필터에서 압축기로의 확장

핵심 아이디어는 1이 드문(희소) 바이너리 스트링에서 1의 위치 정보만 저장하면 기존 전체 비트보다 더 작은 용량으로 데이터 기록이 가능함.

압축 단계:
- Bloom 필터 비트맵에 1의 위치를 명시
- Bloom 필터 외에 진짜로 필요한 비트값(증인 데이터)을 별도 저장
이론적 분석을 통해 1의 비율이 0.32453 미만일 때 압축 이득이 발생함

핵심 기법 수식 및 최적화

희소도에 따른 k(해시 함수 개수)와 l(비트맵 크기) 공식 제시
입력 데이터의 비트 분포에 따라 자동 최적 파라미터 산출 가능함

영상 압축 적용 방식

프레임 간 변화(Δ값)만 추출하여, 대부분 변화가 없는 희소 행렬로 변환
이 희소 차이 행렬에 Bloom 필터 압축 기법 적용
전체 프레임 대비 저장 효율 대폭 향상

압축 및 복원 검증 절차

압축된 비트맵/증인 데이터/메타데이터/변경 픽셀 등, 복원에 필요한 모든 항목 용량을 산출함
프레임 단위로 복원 후 원본과 비트 단위 일치 여부 체크
프레임 별 차이 시각화 및 정량화, 전체 파이프라인에 대한 완전 검증 진행
압축률 계산 명확히 코드로 기술되어, 누구나 재현 및 검증 가능함

완전 자급자족적 압축 구조

복원에 별도 사전, 룩업 테이블 필요 없음
모든 Bloom 필터 파라미터 및 색상 정보 압축 파일 내 자체 보유
압축 파일만으로 완벽 복원 가능

결어 및 오픈소스 안내

이 프로젝트는 Bloom 필터를 이용해 데이터 희소성을 최대한으로 활용하며, 완벽 복원이 필요한 과제(과학 데이터, 의료 영상 등)에 최적임. 새로운 알고리듬 구조와 검증 시스템을 직접 실험해보고, 개선 의견을 남길 수 있음.

▲

GN⁺ 10일전 [-]

Hacker News 의견

이 문서가 실제로는 단순한 아이디어를 복잡하게 설명하는 느낌이라는 생각임
1. 각 픽셀의 변화 여부를 비트맵으로 만들고, 변한 픽셀은 1, 안 변한 픽셀은 0으로 표시
2. 1로 표시된 픽셀의 오프셋을 해싱해 Bloom filter에 추가
3. Bloom filter에서 양성인 인덱스를 모두 조회해서, 그 위치의 픽셀 데이터만 저장하면 프레임을 손쉽게 복원 가능
  이 방식은 두 프레임의 변화분을 x, y, r, g, b로 저장하는 것과 유사하지만, x, y 좌표를 매우 압축하는 대신 r, g, b는 약간 더 많이 저장하는 방법임
  보통 프레임마다 변하는 픽셀 위치가 비슷하기에, 다음 프레임에서는 해당 위치 플래그만 잘 설정하고 추가로 변한 오프셋만 추가적으로 저장하면 더 압축할 수 있을 것 같은 가능성도 보임
- 바로 이런 이해도 높은 댓글을 보러 항상 댓글부터 읽는 나임
  그리고 보니까 작성자가 kilo 만든 사람이기도 하네, 정말 멋짐
  [edit] 수정하는 것까지 왠지 재미있다는 느낌
- 실제 압축률이 얼마나 나오는지 궁금함
  옛날에 wavelet 기반 이미지 압축을 실험했던 적이 있음
  역변환은 작은 이미지에서 시작해서, 계수를 사용해 점점 2배씩 키워가는 원리
  대부분의 데이터가 거의 0인 계수들이고, 이걸 0으로 날려서 압축
  핵심은 0이 아닌 부분 위치만 효율적으로 인코딩하는 것인데, 보통 이 값들이 군집되어 있어서 알고리즘들이 이 특성을 많이 이용
  Bloom filter에서 사용하는 해시함수와는 완전히 반대의 특성이 나타남
  이런 방식은 변환 자체와 계수 압축 모두 공간적 연관성이 떨어지고 느려서, 결국 한계에 부딪쳤던 기억
- Bloom filter가 해시 테이블과 비교해 어떤 점이 더 유리한지 궁금함
- 영상 압축의 많은 부분이 ‘움직임’에 관한 것임
  카메라 패닝처럼 같은 픽셀이 2픽셀 좌측으로 밀릴 때는 어떻게 처리하는지 궁금증
- 프레임간 델타 변화만 저장한다면, 변하지 않은 픽셀은 모두 0 임
  연속적인 0 시퀀스를 압축하는 건 손실 압축에서 가장 쉬운 부분인데 Bloom filter 방식에서는 false positive가 존재함
  Bloom filter도 복합 압축기의 하위 전략 중 하나로 쓸 수 있을 것 같고, 다양한 방법을 섞는 게 더 낫지만 평균적으로 Bloom filter가 기존 방식 대비 성능을 크게 높일 것 같진 않음
이 방식이 Youtube 영상 같은 이미 한 번 압축-해제된 영상에선 잘 동작하는 이유가 있다고 생각
Raw 입력에선 대부분의 픽셀이 연속 프레임에서 거의 안 바뀐다 - 이 가정이 깨질 수 있음
완전히 깔끔한 저노이즈, 밝은 장면이라면 적용 가능하겠지만, 일반적 신호는 1 LSB 이상의 노이즈가 많아서 하위 비트들이 자주 변할 것임
압축-해제 과정이 거치면 노이즈가 줄어 이 가정이 맞는 상태로 바뀌는 것
- 실제로도 이 방식은 무손실이 아님
  video_delta_compress.py 코드상, r,g,b 평균 변화량이 10 미만이면 변화를 저장하지 않게 됨
  예를 들어 pure blue(#00ff00)에서 pure red(#ff0000)로 변할 때도 이렇게 처리되어, 두 프레임 모두 pure blue로 복원되는 상황 발생
- 사진 촬영에 PNG를 쓰지 않는 것처럼, 현장 영상엔 무손실 코덱을 잘 안 씀
  무손실 영상은 화면 녹화 같은 디지털 콘텐츠에 더 어울림
  이런 경우에는 프레임 간 변화 픽셀이 적게 나타나기 때문에 이 방법의 가정이 잘 맞음
- 코드에선 비율이 32.4% 미만이면 비트 1 위치만 저장하는 전략을 사용함
  만약 하위 비트가 자주 바뀌더라도, 상위 비트가 충분히 안 바뀌면 이 방식이 여전히 작동할 수 있지 않을까? 생각
- 일반적으로 Raw 영상을 쓰는 사람은 거의 없음
  휴대폰과 카메라도 기본적으로 MP4, AV1 등으로 저장
  파일 크기와 처리 부담을 감안해서 raw 미가공 포맷 자체의 존재를 모르는 사람도 많다는 인식
- 그래서 현재 방식은 애니메이션용으론 적합함
관련 compression_comparison.png 그래프에 따르면, 새로운 압축 방식이 항상 GZIP에 비해 성능이 떨어진다는 거냐는 의문
- 그래프엔 안 나와 있지만, Bloom filter 방식이 적어도 gzip보단 속도가 빠를 수는 있을 것 같음
  다만 성능 관련 수치는 못 찾았음
본문에서 말한 “1의 밀도가 충분히 낮은 이진 문자열은 1의 위치만 저장해도 원래 데이터보다 더욱 효율적으로 압축 가능”이라는 키 인사이트 언급
JPEG, MPEG 등은 원래 문제를 0이 길게 이어지게 재배치하도록 하는데, DCT 블록 스캔 방식이 이런 영상 압축에서 매우 혁신적임
- DCT와 컬러 변환은 미세 디테일을 고주파로, 주요 내용은 저주파로 바꿔줌
  압축은 고주파 성분만 버리는 식
  JPEG는 Huffman table로도 크기 최적화
  0을 모아놓는 특별한 기법은 별로 안 쓰고, 0이 모인다고 압축 효율이 크게 오르진 않음
- 동의함
  OP 접근법의 가장 큰 문제는, 일반 비디오에서 흔히 존재하는 픽셀 변화의 공간적 연관성을 적극적으로 버린다는 점
  오히려 영상 프레임 전용이 아니라, 그냥 길이가 같은 비트열 차분 압축 일반화임
  입력 데이터가 예측 가능성(랜덤성이 낮은 구조)일 때만 효과를 보는데, 그런 데이터조차 해시 함수를 거치면 정보가 섞여버리게 됨
  특히 암호학적 해시는 결과가 완전히 랜덤하게 바뀌어서 압축에 불리함
안녕하세요 HN, 작성자임
피드백을 받아 raw 영상과 노이즈 있는 영상을 중심으로 더욱 엄밀한 테스트를 진행 중
아직 초기 단계이지만 raw 영상에서 나름 괜찮은 결과가 나옴 (단, caveat 있음)
- 압축률 4.8% (95.2% 사이즈 감소)
- 압축 속도: 초당 8.29프레임
- 복원 속도: 초당 9.16프레임
- 4%만 키프레임 필요
- 체감상 무손실(PSNR: 31.10 dB)
  표준 코덱과 비교
- Rational Bloom Filter: 4.8%
- JPEG2000 (무손실): 3.7%
- FFV1 (무손실): 36.5%
- H.265/HEVC: 9.2% (손실압축)
- H.264: 0.3% (손실압축)
현재 한계와 향후 작업

색상 처리에서 비트 단위 완전 무손실이 아니며 YUV-BGR 변환 과정에서 소수점 오차가 발생(평균 픽셀차 ~4.7), 변환 후 BGR 채널 처리시 정밀도 손실
다음 작업 계획
- 변환 없이 YUV 직접 처리
- 컬러 데이터에 대한 비트 단위 무손실 구현
- 크로마 서브샘플링 패턴에 맞춘 Bloom filter 정교화
- 각 컬러 채널별 개별 검증 시스템 구축
  완벽하게 수학적으로 무손실임을 증명해보고 싶음
  이 lossless compression 아이디어와 Rational Bloom Filter 활용 방안을 영상 외 다른 영역에서도 고민 중
video_delta_compress.py 코드 라인에 혼란스러움
이 부분 때문에 #ffffff에서 #fffffa로의 변화, 또는 #ff0000에서 #00ff00 과 같은 변화가 임계값에 따라 모두 버려지는 구조로 보임
이 코드 라인의 역할을 내가 잘못 이해한 건지, 0인 픽셀 변화는 Bloom filter에 기록 자체가 안 되는 구조 같음
압축률 계산 방법이 소개되어 있지만, 최악/평균/최고 압축률 예시가 있는지 궁금
(수정: 리포 안에 사진 예제가 있는 걸 확인했으니, README에 넣어주면 좋겠다는 의견)
- 작성자임
  리포가 많이 지저분하지만, 코드 안에 그래프 등을 생성하는 코드도 있음
  앞으로 제대로 된 테스트와 결과 정리를 해서 많이 다듬을 계획임
  아직까지 상당히 messy한 WIP 단계
H.264 같은 코덱도 실제로 무손실 모드를 쓸 수 있고, 잘 쓰진 않지만 가능함
- 맞음
  NVENC 하드웨어 가속도 활용해 무손실 모드를 동작시켰던 경험 있음
  다만 재생 쪽이 힘든데, ffplay로만 돌아가고 그 외에는 거의 안 됐던 기억
좋은 콘셉트지만, sparse한 이진 문자열은 그냥 기존 전통적 압축법이 더 나을 수 있다는 생각
- 실제로 gzip과의 비교 그래프에서도 알 수 있음
리포를 보면 픽셀 차분 중 얼마나 많은 차분을 던졌는지로 압축률을 계산하는 것으로 보임
이건 흥미로운데, 실제로 더 중요한 건 유튜브 압축 영상에서 각 프레임의 평균 바이트 크기와 직접 비교하는 것
이게 없으면 실제로 현재 방식이 성능상 개선이 있는지 알기 어렵다는 의문
만약 이 알고리즘이 손실압축 방식이라면 작은 차이는 모두 0으로 몰아가니, 손실압축과 비교하는 편이 더 적절함

답변달기