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

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