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

 (github.com/ross39)
4P by GN⁺ | ★ favorite | 댓글 1개
  • Rational Bloom Filter Video Compression은 원시 비디오를 압축하면서 복원 결과가 원본과 비트 단위로 동일해야 하는 무손실 워크플로를 구현함
  • 핵심은 Bloom 필터에 비정수 해시 함수 수를 적용해, 기존 방식보다 더 나은 압축률을 이론적으로 노리는 구조임
  • Y4M, YUV, HDR 같은 raw video content를 대상으로 하며, 일반적인 비디오에서 40~50% 공간 절감을 제공한다고 설명함
  • 구현은 Python 3.7+ 기반이고 numpy, opencv-python, xxhash, Pillow, scikit-image, HDR용 pyexr 등 의존성이 필요함
  • FFV1, HuffYUV, H.264 무손실 모드와 비교하는 벤치마크가 포함되어 있어, 실제 활용 전에는 results.md의 결과와 재현 절차를 확인하는 흐름임

Rational Bloom Filter Video Compression 개요

  • 이 프로젝트는 rational Bloom filter 기반의 무손실 비디오 압축 방식을 구현함
  • Bloom 필터는 이진 데이터를 효율적으로 표현하는 확률적 자료구조로 사용됨
  • 차별점은 Bloom 필터에서 정수가 아닌 rational hash function을 쓴다는 점임
  • 압축 후 복원된 결과가 원본과 bit-exact하게 일치하는 것을 목표로 함

지원 대상과 압축 기능

  • 압축 시스템은 Y4M, YUV, HDR 등 raw video content를 대상으로 함
  • 제공 기능은 다음과 같음
    • 비트 단위 동일 복원을 보장하는 true lossless compression
    • 일반적인 비디오 콘텐츠에서 40~50% 공간 절감
    • 멀티스레드 지원을 통한 인코딩·디코딩
    • RGB, BGR, YUV 등 여러 color space 지원
    • HDR 콘텐츠 처리 지원
  • HDR 처리는 “빠르고 사용 가능하게 만들려면 작업이 더 필요하다”는 제한이 있음

설치 요구사항

  • 실행 환경은 Python 3.7+ 임
  • 필요한 패키지는 다음과 같음
    • numpy
    • opencv-python
    • matplotlib
    • pandas
    • tqdm
    • requests
    • xxhash
    • Pillow
    • scikit-image
    • pyexr: HDR 지원용
  • 의존성은 다음 명령으로 설치함
pip install -r requirements.txt

기본 사용 방식

  • Python 코드에서는 ImprovedVideoCompressor를 가져와 압축기를 초기화함
  • 예시 설정에는 noise_tolerance=10.0, keyframe_interval=30, use_direct_yuv=True, verbose=True가 포함됨
  • compress_video()는 입력 비디오를 .bfvc 파일로 압축함
  • decompress_video()는 .bfvc 파일을 복원함
  • verify_lossless()로 원본 프레임과 복원 프레임의 무손실 여부를 검증함
from improved_video_compressor import ImprovedVideoCompressor

compressor = ImprovedVideoCompressor(
    noise_tolerance=10.0,
    keyframe_interval=30,
    use_direct_yuv=True,
    verbose=True
)

compressor.compress_video(
    input_file="input_video.y4m",
    output_file="compressed.bfvc"
)

compressor.decompress_video(
    input_file="compressed.bfvc",
    output_file="decompressed.mp4"
)

original_frames = compressor.extract_frames_from_video("input_video.y4m")
decompressed_frames = compressor.decompress_video("compressed.bfvc")
verification = compressor.verify_lossless(original_frames, decompressed_frames)
print(f"Lossless: {verification['lossless']}")

명령줄 사용

  • 비디오 압축은 다음처럼 실행함
python -m improved_video_compressor compress input_video.y4m output.bfvc --max-frames 30
  • raw YUV 파일은 폭, 높이, 포맷을 함께 지정해 처리함
python -m improved_video_compressor process-yuv input.yuv output.bfvc --width 1920 --height 1080 --format YUV444

벤치마크와 비교 대상

  • 프로젝트에는 Rational Bloom Filter 압축을 다른 무손실 압축 방식과 비교하는 벤치마크 시스템이 포함됨
  • 비교 대상은 FFV1, HuffYUV, H.264의 무손실 모드임
  • 전체 벤치마크 실행 명령은 다음과 같음
python benchmark_compression.py
  • 특정 데이터셋과 방식만 지정해 실행할 수도 있음
python benchmark_compression.py --datasets y4m --methods bloom ffv1 --max-frames 10
  • 상세 벤치마크 결과와 재현 방법은 results.md에 있음

압축 방식의 동작 흐름

  • 압축 스킴은 다음 단계로 동작함
    • Frame Extraction: 입력 비디오에서 프레임을 추출함
    • Keyframe Selection: 키프레임은 직접 zlib 압축된 프레임으로 저장함
    • Bloom Filter Compression: 인터 프레임은 차이 맵을 rational Bloom filter로 압축함
    • Lossless Verification: 디코딩 중 bit-exact 복원을 검증함
  • rational Bloom filter는 공간과 정확도 사이의 균형을 최적화하기 위해 비정수 해시 함수 수 k*를 사용함
  • 구현은 ⌊k*⌋개의 해시 함수를 결정적으로 사용하고, 추가 해시 함수는 k* - ⌊k*⌋ 확률로 적용함

프로젝트 파일 구성

  • improved_video_compressor.py: 압축 알고리듬의 main implementation
  • verify_true_lossless.py: 무손실 복원을 검증하는 스크립트
  • benchmark_compression.py: 여러 압축 방식을 비교하는 벤치마크 시스템
  • download_*.py: 테스트 데이터셋 다운로드 스크립트
  • results.md: 상세 벤치마크 결과와 분석

라이선스와 인용

  • 라이선스는 MIT License이며, 자세한 내용은 LICENSE 파일에서 확인할 수 있음
  • 연구에서 코드를 사용할 경우 README에 포함된 BibTeX 형식의 citation을 사용하도록 안내함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 문서가 아주 단순한 아이디어를 잘 설명하지 못한 것 같음. 이해한 게 맞다면, 먼저 각 비트를 이미지의 픽셀로 보는 비트맵을 만들고, 0번 프레임에서 1번 프레임으로 가며 바뀐 픽셀은 1, 아니면 0으로 둠
    그다음 1인 위치들의 오프셋을 해시해서 Bloom filter에 넣음. 그러면 해당 인덱스들과 일정 비율의 거짓 양성 인덱스가 양성으로 나옴
    이후 Bloom filter에 질의해 양성인 인덱스를 모두 찾고, 그 픽셀들에 대해 바뀐 원시 픽셀 데이터를 저장하면 다음 프레임을 쉽게 재구성할 수 있음
    두 프레임 사이의 델타를 바뀐 모든 픽셀의 x,y,r,g,b로 저장하되, x,y 부분을 크게 압축하고 필요 이상으로 r,g,b를 조금 더 저장하는 방식으로 볼 수 있음
    0→1 프레임에서 바뀐 픽셀의 위치는 1→2 프레임에서 바뀔 위치와 비슷한 경우가 많으니, 다음 프레임에서 적절한 플래그를 세우고 이전과 추가로 달라진 오프셋만 그대로 저장하면 더 압축할 여지도 있어 보임

    • 실제 압축률이 얼마나 좋은지 궁금함. 22년쯤 전에 이미지 압축용 웨이블릿을 실험하던 게 떠오름
      역변환은 작은 픽셀 이미지에서 시작해, 폭이나 높이가 두 배인 이미지로 바꾸는 데 같은 수의 계수를 쓰고 이를 반복함
      핵심은 데이터 대부분이 계수이고, 그 대부분이 0에 가까워 0으로 밀어버릴 수 있다는 점임. 그러면 문제는 0이 아닌 위치를 어떻게 인코딩하느냐가 되고, 비트맵과 0이 아닌 값 배열 같은 구조가 됨
      0이 아닌 값을 인코딩하는 알고리즘들은 보수성 정도가 달랐지만, 대체로 그런 값들이 꽤 뭉쳐 있다는 성질을 활용했음. 이는 Bloom filter에 쓰는 일반적인 해시 함수와는 정반대임
      이런 식의 이미지 압축은 변환 자체와 계수 압축 모두에서 지역성이 매우 나빠 느렸고, 그래서 막다른 길처럼 느껴졌음
    • 한 프레임에서 다음 프레임으로의 델타 변화를 저장한다면, 바뀌지 않은 픽셀은 그냥 0임. 0의 연속을 압축하는 건 무손실 압축에서 가장 사소한 작업이고, Bloom filter와 달리 거짓 양성도 없음
      Bloom filter가 복잡한 하이브리드 압축 전략의 일부로는 쓰일 수 있다고 봄. 그런 압축기는 도구가 많을수록 좋지만, 평균적으로 크게 개선될 것 같지는 않음
    • Bloom filter가 해시 테이블 같은 것에 비해 어떤 도움이 되는지 궁금함
    • 비디오 압축의 상당 부분은 움직임을 다루는 데 있음. 패닝 때문에 같은 픽셀이 왼쪽으로 두 픽셀 미끄러지는 경우는 어떻게 처리하는지 궁금함

  • 입력 비디오가 이미 YouTube에서 압축 후 복원된 영상이라서 더 잘 동작하는 것 같음
    원본 영상 입력이라면 “연속 프레임 사이에서 대부분의 픽셀이 조금만, 혹은 전혀 변하지 않아 희소한 차분 행렬이 생긴다”는 가정이 깨질 듯함
    아주 깨끗한 신호, 예를 들어 저잡음 센서와 밝은 장면이라면 가능하겠지만, 현실의 대부분 신호는 잡음이 1 LSB보다 커서 하위 비트가 최소 절반 정도는 바뀔 것으로 예상함
    비디오를 압축과 복원 과정을 한 번 거치게 하면 그런 잡음이 제거되는 경향이 있어, 이 가정이 성립하는 인위적으로 정적인 영상이 만들어짐

    • 보기에는 이것도 무손실이 아닌 것 같음: https://github.com/ross39/new_bloom_filter_repo/blob/main/vi...
      r,g,b 값 평균 변화가 10 미만인 픽셀은 차분을 저장하지 않는 듯함. 그러면 한 픽셀이 연속 프레임에서 순수 파랑(#00ff00)에서 순수 빨강(#ff0000)으로 바뀌어도, 두 프레임 모두 순수 파랑으로 복원될 수 있음
    • 사진에 PNG를 쓰지 않는 것처럼, 실제 촬영 영상에 무손실 비디오 코덱을 쓰지는 않을 것 같음
      무손실 비디오는 화면 녹화 같은 디지털 콘텐츠에 훨씬 더 맞음. 연속 프레임 사이에서 바뀌는 픽셀이 적다는 가정도 그쪽에서 더 타당함
    • 보통 사람들은 원본(raw)을 쓰지 않으니 큰 문제가 아닐 수도 있음. 휴대폰과 카메라는 어차피 MP4나 AV1 같은 파일로 저장함
      직접 켜서 파일 크기와 처리 부담을 감수하지 않는 한, 원본이나 미가공 데이터라는 개념이 아직 있다는 것조차 모를 수 있음
      전에는 이렇게 생각해본 적이 없었음
    • 지금 방식 그대로라면 애니메이션에는 아주 잘 맞을 듯함
    • 게으른 방법으로는 8K 비디오를 내려받아 720p 정도로 다운샘플링하면 됨
      아니면 카메라를 사서 일상 장면의 원본 8K 영상을 직접 찍어도 됨

  • 그래프 [1]에 따르면 이 새 압축 방식은 그냥 GZIP을 쓰는 것보다 항상 엄격하게 나쁜 것 아닌가?
    [1] https://github.com/ross39/new_bloom_filter_repo/blob/main/co...

    • 그래프에는 없지만, Bloom filter 방식이 gzip보다 적어도 더 빠를 수는 있을 것 같음. 다만 다른 곳에서도 성능 지표를 못 찾겠음

  • “핵심 통찰: 이진 문자열에서 1의 밀도가 낮으면, 특히 p* ≈ 0.32453 미만이면, 원시 문자열을 저장하는 것보다 1의 위치만 인코딩하는 편이 더 효율적이다.”
    JPEG/MPEG이 하는 일의 상당 부분은 긴 0의 연속을 만들 수 있도록 문제를 재배열하는 것임. DCT 블록을 AC/DC 성분의 위치에 맞춰 스캔하는 방식은 여러 비디오·이미지 압축 기법에서 가장 혁신적인 부분 중 하나일 수 있음

    • 이 방식은 실제로 비디오 압축에는 꽤 나쁨. 일반적인 비디오에 존재하는 픽셀 변화의 지역성을 적극적으로 버리기 때문임
      더 좋게 말하면, 이 기법에는 비디오 프레임에 특화된 점이 없음. 같은 길이의 두 비트열 사이 차분을 압축하는 데도 같은 아이디어를 쓸 수 있음
      그렇다고 이 문제가 기존 압축 방식, 예를 들어 두 블록을 이어 붙여 gzip하는 것보다 나을 가능성은 낮음. 압축이 되려면 입력 분포, 여기서는 서로 다른 비트 위치들의 집합이 매우 예측 가능하고 비무작위적이어야 하는데, 데이터를 해시 함수에 통과시키면 그 성질이 깨짐. 특히 암호학적으로 강한 해시는 출력이 무작위와 구별되지 않게 만드는 것이 목적임
    • 그 설명은 맞지 않는다고 봄
      DCT와 색 표현 변환이 하는 일은 미세한 디테일을 고주파로, 핵심 디테일을 저주파로 바꾸는 것임. 그다음 이미지 품질과 압축률은 고주파 표현을 얼마나 버리느냐로 단순해짐
      그 외에 JPEG는 Huffman 표를 써서 이미지 크기를 더 줄임
      아는 한, 긴 0의 연속을 줄이려고 특별한 일을 하지는 않음. 그래서 0을 일렬로 맞추는 게 크게 도움이 되지는 않음

  • 이 줄이 헷갈림: https://github.com/ross39/new_bloom_filter_repo/blob/4798d90...
    이러면 압축이 손실 압축이 되고, 예를 들어 #ffffff에서 #fffffa로 가는 전환을 버릴 것 같음. 바로 위 줄에서 픽셀 데이터의 평균을 취하는 부분도 임계값과 무관하게 #ff0000에서 #00ff00으로 가는 전환을 버릴 듯함
    해당 코드 줄의 역할을 잘못 이해한 건지 모르겠음. 결과 마스크에서 0이 된 것은 Bloom filter에 인코딩되지 않는 것처럼 보임

  • 압축률 계산법은 적혀 있는데, 최악·평균·최선 압축률 예시도 있는지 궁금함
    수정: 저장소에 이미지가 있는 걸 봤음. README에 넣어두면 도움이 될 듯함

    • 작성자임. 저장소가 완전히 엉망이긴 하지만, 코드를 뒤질 의향이 있다면 그래프 등을 생성하는 코드가 들어 있음
      제대로 된 테스트를 많이 해서 훨씬 더 구체적으로 만들 예정임. 아직은 아주 지저분한 진행 중 작업에 가까움

  • 작성자임. 좋은 피드백을 많이 받아서 당분간은 원본 비디오와 잡음 있는 영상에 대한 더 엄격한 테스트에 집중하기로 했음. 저장소는 계속 자주 업데이트할 예정임
    아직 매우 초기지만, 원본 비디오 테스트에서는 몇 가지 단서와 함께 꽤 괜찮은 결과가 나왔음. 압축률 4.8%, 즉 크기 95.2% 감소, 압축 속도 8.29fps, 압축 해제 속도 9.16fps, 키프레임은 프레임의 4%만 필요, 지각적으로 무손실인 출력(PSNR 31.10dB)임
    표준 코덱과 비교하면 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 형식으로 색상 채널을 처리해 추가 정밀도 손실을 일으킴
    앞으로는 BGR 변환 없이 직접 YUV를 처리하고, 색상 데이터를 비트 단위로 정확하게 다루며, 크로마 서브샘플링 패턴에 맞춰 Bloom filter 매개변수를 다듬고, 각 색상 채널을 독립적으로 검증하는 전용 시스템을 만들 계획임
    수학적으로 무손실임을 증명하고 싶지만 아직 갈 길이 멂. 이 무손실 압축 아이디어를 계속 파고들 계획이고, Rational Bloom Filter를 다른 영역에 활용하는 아이디어도 몇 가지 있음

  • H.264 같은 코덱도 진짜 무손실 모드로 실행할 수 있음. 거의 아무도 그렇게 쓰지 않을 뿐임

    • NVENC로 하드웨어 가속까지 되게 만든 적이 있음. 다만 재생이 어려웠고, ffplay는 됐지만 다른 건 안 됐음

  • 귀여운 개념이긴 하지만, 희소한 이진 문자열이 있다면 전통적인 방법으로 더 잘할 수 있을 가능성이 큼

  • 저장소를 따라가기가 어렵지만, 압축률은 얼마나 많은 픽셀 차분을 버릴 수 있었는지를 보고 계산하는 것처럼 보임
    흥미롭긴 하지만, 더 중요한 비교 대상은 압축된 YouTube 비디오에서 각 프레임의 평균 바이트 크기일 것임. 이 비교가 없으면 현행 방식보다 개선인지 판단하기 어려움
    알고리즘이 손실 방식이라면, 즉 작은 차분을 0으로 눌러버린다면 무손실이 아니라 다른 손실 알고리즘과 비교해야 할 것 같음

답변달기