Bloomフィルタを用いた可逆ビデオ圧縮

 (github.com/ross39)
4 ポイント 投稿者 GN⁺ 2025-05-28 | 1件のコメント | WhatsAppで共有
  • このオープンソースプロジェクトは 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% の確率で 3つ目のハッシュを使用）
  • 各要素ごとにこの確率的な決定が一貫して行われるよう設計している

この方式は圧縮時と復元時の両方で正確に動作し、圧縮の信頼性を高める

Bloomフィルタから圧縮器への拡張

中核アイデア は、1 がまれにしか現れない疎なバイナリ文字列では、1 の位置情報だけを保存すれば、元の全ビット列よりも小さな容量でデータを記録できるという点にある。

  • 圧縮段階:
    • Bloomフィルタのビットマップに 1 の位置を明示
    • Bloomフィルタとは別に、本当に必要なビット値（witness data）を別途保存
  • 理論解析により、1 の比率が 0.32453 未満のときに圧縮上の利得が生じる

中核手法の数式と最適化

  • 疎度に応じた k（ハッシュ関数数）と l（ビットマップサイズ）の式を提示
  • 入力データのビット分布に応じて自動で最適パラメータを算出できる

映像圧縮への適用方法

  • フレーム間 の変化（Δ値）だけを抽出し、大半に変化がない疎行列へ変換
  • この疎な差分行列に Bloomフィルタ圧縮手法を適用
  • フレーム全体と比べて保存効率を大幅に向上

圧縮および復元の検証手順

  • 圧縮されたビットマップ / witness data / メタデータ / 変更ピクセルなど、復元に必要なすべての項目の容量を算出する
  • フレーム単位で復元した後、元データと ビット単位で一致するか を確認
  • フレームごとの差分の可視化と定量化、パイプライン全体に対する完全な検証を実施
  • 圧縮率の計算も明確にコード化されており、誰でも再現・検証できる

完全に自己完結した圧縮構造

  • 復元に別個の辞書やルックアップテーブルは不要
  • すべてのBloomフィルタパラメータと色情報を圧縮ファイル内に保持
  • 圧縮ファイルだけで完全復元が可能

結びとオープンソース案内

このプロジェクトは、Bloomフィルタを用いてデータの疎性を最大限に活用し、完全復元が必要な課題（科学データ、医療映像など）に最適である。新しいアルゴリズム構造と検証システムを直接試し、改善意見を残すことができる。

関連記事

1件のコメント

 
GN⁺ 2025-05-28
Hacker Newsのコメント

  • この文書は、実際には単純なアイデアを複雑に説明しているように感じる

    1. 各ピクセルが変化したかどうかをビットマップにし、変化したピクセルは1、変化していないピクセルは0で示す
    2. 1で示されたピクセルのオフセットをハッシュ化してBloom filterに追加する
    3. Bloom filterで陽性になったインデックスをすべて参照し、その位置のピクセルデータだけを保存すればフレームを簡単に復元できる この方式は、2つのフレームの差分を 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) に変わる場合でもこう扱われ、2つのフレームがどちらも 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 でしか動かず、それ以外ではほとんど無理だった記憶がある

  • 良いコンセプトではあるが、疎な二進文字列なら単純に既存の伝統的な圧縮法の方がよいかもしれないと思う

  • リポジトリを見ると、ピクセル差分のうちどれだけの差分を捨てたかで圧縮率を計算しているように見える これは興味深いが、実際にもっと重要なのは YouTube 圧縮映像で各フレームの平均バイトサイズと直接比較することだ これがないと、現行方式に本当に性能上の改善があるのか判断しにくいという疑問がある もしこのアルゴリズムが非可逆圧縮方式なら、小さな差異をすべて 0 に寄せるのだから、非可逆圧縮と比較する方が適切だ