H.264の秘密 | POSTD
(編注：2020/08/18、いただいたフィードバックをもとに記事を修正いたしました。) (2016/12/11、いただきましたフィードバックをもとに翻訳を修正いたしました。) H.264は、動画圧縮コーデックの標準規格です。ネット上の動画、Blu-ray、スマホ、セキュリティカメラ、ドローンなどなど、今やあらゆるところでH.264が使われています。 H.264は注目すべき技術のひとつです。たったひとつの目標、つまりフルモーションビデオの送信に要するネットワーク帯域を削減することを目指した30年以上の努力の結晶なのです。 技術的な面でも、H.264はとても興味深い規格です。この記事では、その一部について概要レベルでの知識を得られることでしょう。あまり複雑だと感じさせないようにするつもりです。今回おはなしする概念の多くは動画圧縮全般にあてはまるものであり、H.264に限ったものではありません
DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
LZ法再び - DO++
可逆データ圧縮としてはgzipやlha, pngなどダントツで使われているLZ法（Lemple Ziv法）ですが、他のデータ圧縮法（BWT法、PPM法、CM法）に比べ圧縮率が低いということで研究の対象としてはあまり注目をあびていませんでした。ところが次の論文で真面目にやれば圧縮率は非常に高くなる可能性があり、BWT法とかそれを超える可能性があることが示されています。。 "On the bit-complexity of Lempel-Ziv compression", SODA 2009, P. Ferragina, et. al. [pdf] まず、LZ法についておさらいですが、基本的にはデータを前から順番に見ていったときに、既に出現した文字列がもう一度出現（マッチング）したら、その文字列を前回出現した（相対）位置と長さのペア(pos, len)で置き換えることで圧縮する方法です。データ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
