世界を動かす技術を、日本語で。
READMEがちょっと混乱するね。YouTubeの動画に言及してるけど、「ロスレス動画」ってのもあるし。これは、既存のH.264の動画（YouTubeからダウンロードしたような）をロスレスで再圧縮する話なのか、それともソースから新しい動画をロスレスで作る話なのかな？前者はJPEG XLが古いJPEGのDCTを再圧縮する能力を思い出させるけど、圧縮が良くなってもロスレスな画像にはならないよね。H.264は元々ロスレスであることもあるけど、YouTubeはそんなファイルを提供してないし。
著者はYouTubeのサンプルを再エンコードしてるって考えてもいいと思う。vp9/avc/av1 -> 非圧縮 -> これで圧縮、で、圧縮率は非圧縮ストリームに対してのものだと思う。そうじゃなかったら、READMEはもっと熱意がある感じになるはずだしね :)
そうだね、もし論文を書いてたら、.rawファイルをエンコードした方が説得力があったかもね。
イントロはH.264やその仲間たちの代替品ってことをかなり明確にしてるね。従来の動画コーデック、H.264やH.265は「気づかれない」視覚情報を捨てることで素晴らしい圧縮を実現してる。でも、完璧な再構築を保証しつつ、意味のある圧縮ができたらどうなる？このプロジェクトは、Bloomフィルタをロスレス動画圧縮メカニズムとして再利用するという、ちょっと変わったアプローチを探求してる。さらに下には、この仕組みがどうしてうまくいくかの説明があるよ：全動画フレームを圧縮するのではなく、フレームの差分にBloomフィルタ圧縮を適用するんだ。これが時間的なコヒーレンスを活かしてる。ほとんどのピクセルは連続するフレーム間であまり変わらないから、スパースな差分マトリックスができて、このアプローチに最適なんだ。もちろん、デルタフレーム圧縮は多くの動画コーデックで長い間使われてきたテーマで、H.264やH.265のようなものは、最終的なエントロピーコーディングの前にデルタフレームの情報をさらに減らすためにモーション推定のような追加技術を使ってる。だから、これをH.264や似たようなもののエントロピーコーディングの代替として見るのが一番いいかもね。
著者です。H.264がロスレスであることには完全に同意します。一般的にはロスィーですけどね。私のアイデア（まだ考え中ですが）は、フレームの差分を合理的なBloomフィルタを使って圧縮することです。以前、条件付きBloomフィルタを使うことについて投稿したことがありますが、それは合理的なkに依存していました。アイデアは、URLが悪意のある可能性が高いかどうかに基づいてkの異なる値を使うことでした。これにより、整数kと比較して同じフィルタサイズでの偽陽性率が低くなります。最近、ほぼ同じアプローチを説明した論文[https://arxiv.org/html/2502.02193v2]が投稿されているのを見ました（彼らのはもっと素敵です）。今のセットアップはちょっと雑なので、もっと厳密なテストをするつもりですが、アイデアを示すには役立つと思います。
圧縮率の計算方法はわかったけど、最悪のケース、平均、最高のケースの圧縮率の例はありますか？編集：あ、リポジトリに写真があるのを見ました。READMEに入れておくと助かるな。
ここに作者がいます。リポジトリはめちゃくちゃだけど、コードの中にはグラフを生成するためのコードもあるから、掘り下げる気があれば見てみて。もっと具体的に、ちゃんとしたテストをたくさんして進めるつもりだよ。まだまだごちゃごちゃした進行中の作業なんだ。
H.264を真のロスレスモードで動かすことも可能だけど、ほとんどやられないね。
うん、NVENCを使ってハードウェアアクセラレーションでも動かせたよ。ただ、再生はちょっと難しかった。ffplayでは動いたけど、他のはダメだった。
重要な洞察：バイナリ文字列に1の密度が低い（具体的にはp* ≈ 0.32453未満）場合、1の位置だけを効率的にエンコードできる。JPEGやMPEGがやっていることの多くは、ゼロの長い連続を作ることができるように問題を再配置することだ。DCTブロックがそのAC/DC成分の位置に対してスキャンされる方法は、多くの動画や画像圧縮技術の中で最も革新的な側面の一つかもしれない。
これが正しいとは思わない。DCTがやることは、色の表現変換とともに、細かいディテールを高い周波数に、核心的なディテールを低い周波数に変えることだよ。そこから、画像の質、つまり圧縮率は高周波数の表現を落とすだけで簡単になる。それに加えて、JPEGはハフマンテーブルを使って画像のサイズをさらに減らしてる。私の知る限り、ランを減らすために特別なことはしてないから、ゼロを並べることはあまり役に立たないよ。
同意。OPのアプローチは実際、動画圧縮にはひどいもので、典型的な動画に存在するピクセルの変化のローカリティを積極的に捨てちゃうからね。もっと優しく言うと、OPの技術は動画フレームに特有のものじゃないってことだ。どんな2つの同じ長さのビット列の差分を圧縮するのにも同じアイデアが使える。とはいえ、これがgzippingしたブロックの連結よりもこの問題に対して優れているとは思えない。なぜなら、圧縮を得るためには入力の分布（ここでは異なるビット位置のセット）が非常に予測可能である必要があるから、つまり非ランダムでなければならない。そして、ハッシュ関数を通すことでその特性が壊れちゃうんだよね（特に暗号的に強いハッシュの場合、出力がランダムと区別できないようにするのが目的だから）。
それじゃあ、あなたのグラフによると、この新しい圧縮はGZIPを使うよりも常に悪いってこと？
このグラフには載ってないけど、ブルームフィルターのアプローチは少なくともgzipより速いかもしれないと思う。でも、他にはパフォーマンスの指標が見当たらないね…
これはかわいいコンセプトだけど、スパースなバイナリ文字列があるなら、伝統的な方法の方が良い結果が出るかもね！
確かに、gzipとの比較が示している通りだね。
このドキュメントは、非常にシンプルなアイデアを説明するのがあまり上手くないと思う（私がよく理解していればだけど）：1. 各ビットが画像のピクセルになるビットマップを作成する。フレーム0からフレーム1にかけて特定のピクセルが変わったら、そのビットは1、そうでなければ0。2. すべての1をブルームフィルターに追加し、それらのオフセットをハッシュ化する。これで、ブルームフィルターはすべてのインデックスに対してポジティブになり、さらに一定の割合の偽陽性インデックスも含まれる。3. ブルームフィルターをクエリして、ポジティブなインデックスをすべて確認し、そういったピクセルの生データを保存する。これで次のフレームを簡単に再構築できる。これは、変わったすべてのピクセルのx,y,r,g,bの差分を保存するようなものだけど、x,yの部分をかなり圧縮して、必要以上にr,g,bを少し多めに保存する感じ。フレーム0からフレーム1に変わるピクセルは、フレーム1からフレーム2に変わるものと位置が似ていることが多いから、次のフレームで適切なフラグを設定して、前のものと同じオフセットだけをそのまま保存することで、さらに圧縮できる可能性があると思う。
このコメントがあるから、私は最初にコメント欄を見るんだ。あ、君はキロを作った人だね。いい仕事だよ。[編集] 笑、編集したね…いつも編集するよね。
動画圧縮の多くは動きに関するものだよね。同じピクセルがパンによって2ピクセル左にスライドするのはどう処理するの？
問題は、フレーム間のデルタ変化を保存すると、変わってないピクセルはただのゼロになること。ゼロのシーケンスを圧縮するのは、ロスレス圧縮にとって最も単純な作業だし、ブルームフィルターとは違って偽陽性もない。ブルームフィルターは複雑なハイブリッド戦略の圧縮器の一部として見ることができる。そういう圧縮器のツールが多ければ多いほど良いけど、平均的にはあまり改善されないと思う。
フレーム n+1 からフレーム n+2 にどうやって移行するの？
それで、ブルームフィルターはハッシュテーブルみたいなものと比べてどう役立つの？
これって実際にどれくらいの圧縮率があるんだろう… 22年前に画像圧縮のためにウェーブレットを使った実験を思い出すな。逆変換は小さなピクセル画像から始まって、同じ数の係数を使ってそれを幅か高さが2倍の画像に変換するんだ。これを何度も繰り返す。要は、データのほとんどはこれらの係数で構成されていて、そのほとんどがゼロに近いから、ゼロにしてしまえるんだよね。問題は、ゼロじゃないところをどうエンコードするかってこと。つまり、ビットマップとゼロじゃない値の配列が必要になる。ゼロじゃない値をエンコードするための異なるアルゴリズムがあったけど、これらは大体、ゼロじゃない値がかなり集まっている特性を利用していたんだ。これはブルームフィルターで使う典型的なハッシュ関数とは逆の性質だね。この方法での画像圧縮は明らかにローカリティが悪くて、変換の時点でも係数圧縮の時点でもかなり遅かったから、行き詰まりを感じたよ。
これがうまくいくのは、入力される動画（YouTube動画）がすでに圧縮されて解凍されているからだと思う。生の動画入力だと、「ほとんどのピクセルは連続するフレーム間でほとんど変わらない（または全く変わらない）ため、このアプローチに理想的なスパースな差分マトリックスが作成される」という前提が崩れると思う。非常にクリーンな信号（低ノイズセンサー、明るいシーン）ならうまくいくかもしれないけど、ほとんどの実世界の信号はノイズが1 LSBを超えるから、下位ビットは少なくとも半分の時間は変わると思う。最初に動画を圧縮して解凍するサイクルを通すことで、そのノイズが取り除かれ、前提が成り立つような人工的に静的な動画が作られるんだ。
手抜きの方法は、8K動画をダウンロードして720pにダウンサンプリングすることだね。あるいは、カメラを買って日常のシーンを生の8K映像で撮影するのもあり。
現状のままなら、アニメーションにはすごく向いてるね。
普通の人は生のデータを使わないから、あまり大きな問題にはならないかも。スマホやカメラはMP4やAV1などでファイルを保存するし、設定をオンにしてファイルサイズや処理を気にしない限り、生データや未処理の概念がもう存在しないことに気づかないかもしれない。そんなこと考えたことなかったな。
写真にPNGを使わないのと同じように、実世界の映像にロスレス動画コーデックを使うことはないと思う。ロスレス動画は、連続するフレーム間でほとんどのピクセルが変わらないという前提が成り立つスクリーン録画のようなデジタルコンテンツにはもっと意味があると思う。
計算コストは低いの？FPGAみたいなストリーム処理に向いてるのかな？現代のデータストリームでの圧縮率は許容範囲？それとも、すでに知られている圧縮のサブクラスで、何かしらの制約があるの？