- 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+
- 必要なパッケージは次のとおり
numpyopencv-pythonmatplotlibpandastqdmrequestsxxhashPillowscikit-imagepyexr: 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
圧縮方式の動作フロー
- 圧縮スキームは次の段階で動作する
- 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 implementationverify_true_lossless.py: ロスレス復元を検証するスクリプトbenchmark_compression.py: 複数の圧縮方式を比較するベンチマークシステムdownload_*.py: テストデータセットのダウンロードスクリプトresults.md: 詳細なベンチマーク結果と分析
ライセンスと引用
- ライセンスは MIT License で、詳細は
LICENSEファイルで確認できる
- 研究でコードを使用する場合は、READMEに含まれるBibTeX形式のcitationを使うよう案内している
1件のコメント
Hacker News の意見
文書は、とても単純なアイデアをうまく説明できていないように思う。理解が正しければ、まず各ビットを画像のピクセルと見なすビットマップを作り、フレーム 0 からフレーム 1 に進むときに変わったピクセルを 1、そうでなければ 0 にする。
次に、1 になっている位置のオフセットをハッシュ化して Bloom filter に入れる。すると該当するインデックスと、一定割合の偽陽性インデックスが陽性として返る。
その後 Bloom filter に問い合わせて陽性のインデックスをすべて見つけ、そのピクセルについて変化後の生ピクセルデータを保存すれば、次のフレームを簡単に再構成できる。
2 つのフレーム間のデルタを、変化した全ピクセルの x,y,r,g,b として保存しつつ、x,y の部分を大きく圧縮し、必要以上に r,g,b を少し余計に保存する方式だと見ることができる。
0→1 フレームで変化したピクセル位置は、1→2 フレームで変化する位置と似ている場合が多いので、次のフレームで適切なフラグを立て、前回から追加で異なったオフセットだけをそのまま保存すれば、さらに圧縮できる余地もありそうだ。
逆変換は小さなピクセル画像から始め、幅または高さが 2 倍の画像へ変換するのに同じ数の係数を使い、これを繰り返す。
重要なのは、データの大半が係数であり、その大半が 0 に近く、0 に丸め込める点だった。そうすると問題は 0 でない位置をどうエンコードするかになり、ビットマップと 0 でない値の配列のような構造になる。
0 でない値をエンコードするアルゴリズムは保守性の度合いがさまざまだったが、たいていはそうした値がかなり固まっている性質を利用していた。これは Bloom filter で使う一般的なハッシュ関数とは正反対だ。
この種の画像圧縮は、変換そのものでも係数圧縮でも局所性が非常に悪く遅かったので、行き止まりのように感じられた。
Bloom filter は複雑なハイブリッド圧縮戦略の一部としてなら使えると思う。そういう圧縮器は道具が多いほどよいが、平均的に大きく改善するとは思えない。
入力動画がすでに YouTube で圧縮後に復元された映像なので、よりうまく動作しているように思う。
元の映像を入力するなら、「連続フレーム間で大半のピクセルが少しだけ、あるいはまったく変化せず、疎な差分行列が生じる」という仮定は崩れそうだ。
非常にきれいな信号、たとえば低ノイズセンサーと明るいシーンなら可能かもしれないが、現実の大半の信号はノイズが 1 LSB より大きいため、下位ビットの少なくとも半分ほどは変わると予想する。
動画に圧縮と復元の過程を一度通させると、そうしたノイズは取り除かれる傾向があり、この仮定が成り立つ人工的に静的な映像が作られる。
r,g,b 値の平均変化が 10 未満のピクセルは差分を保存しないように見える。そうすると、あるピクセルが連続フレームで純粋な青 (#00ff00) から純粋な赤 (#ff0000) に変わっても、両フレームとも純粋な青として復元される可能性がある。
ロスレス動画は画面録画のようなデジタルコンテンツにはるかに向いている。連続フレーム間で変化するピクセルが少ないという仮定も、そちらのほうが妥当だ。
自分で有効にしてファイルサイズと処理負荷を引き受けない限り、元データや未加工データという概念がまだ存在することすら知らないかもしれない。
これまでこう考えたことはなかった。
あるいはカメラを買って、日常シーンの元の 8K 映像を自分で撮ってもよい。
グラフ [1] によると、この新しい圧縮方式は単に GZIP を使うより常に厳密に悪いのではないか？
[1] https://github.com/ross39/new_bloom_filter_repo/blob/main/co...
「核心的な洞察：バイナリ文字列で 1 の密度が低い場合、特に p* ≈ 0.32453 未満なら、生の文字列を保存するよりも 1 の位置だけをエンコードするほうが効率的だ。」
JPEG/MPEG がやっていることのかなりの部分は、長い 0 の連続を作れるように問題を並べ替えること。DCT ブロックを AC/DC 成分の位置に合わせてスキャンするやり方は、多くの動画・画像圧縮手法の中でも最も革新的な部分の一つかもしれない
より正確に言えば、この手法には動画フレームに特化した点がない。同じ長さの 2 つのビット列の差分を圧縮するのにも同じアイデアを使える
だからといって、この問題が既存の圧縮方式、たとえば 2 つのブロックを連結して 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 のようなコーデックも本物のロスレスモードで実行できる。ほとんど誰もそう使っていないだけ
かわいいコンセプトではあるが、疎なバイナリ文字列があるなら、従来の方法でもっと上手くできる可能性が高い
リポジトリを追うのは難しいが、圧縮率はどれだけ多くのピクセル差分を捨てられたかを見て計算しているように見える
興味深くはあるが、より重要な比較対象は、圧縮済みの YouTube 動画における各フレームの平均バイトサイズだと思う。この比較がないと、現行方式より改善しているのか判断しにくい
アルゴリズムが非可逆方式、つまり小さな差分を 0 に潰してしまうものなら、ロスレスではなく他の非可逆アルゴリズムと比較すべきだと思う