変更されたJPEGデコーダのための8ポイント1d DCTの高速実装

Question

私はWebで使用するためのカスタムビデオコーデックを開発してきました。カスタムコーデックは、javascriptとhtml5 Canvas要素によって提供されます。

私はこの質問の一番下にリストしたい理由がいくつかありますが、最初に私がこれまで行ってきたことと、なぜ私が高速DCT変換を探しているのかを説明したいと思います。

すべてのビデオ圧縮の背後にある主要なアイデアは、お互いに次のフレームは類似点を大量に共有することです。だから私がやっていることは、最初のフレームをjpgとして圧縮して送ることです。それから最初のフレームとその次の8フレームの "差"を保持している最初のフレームの幅の8倍の別のJpegイメージを送ります。

それだけの違いがあるので、「違い」を開催この大きなJPEG画像を圧縮する方がはるかに簡単です。

私はこの大きなjpegを使って多くの実験を行いました。YCbCrカラースペースに変換したとき、「クロマ」チャンネルはほぼ完全に平坦であることがわかりました。換言すれば、彩度チャンネルではビデオの変化が少ない部分がほとんどありますが、変化する部分はかなり重要です。この知識を用いて

私はJPEG圧縮がどのように機能するかを見上げると、とりわけそれが各8×8ブロックを圧縮するためにDCTを使用していることを見ました。これは本当に興味がありました。私はこれを修正して "各" 8x8ブロックを圧縮するだけでなく、 "次の" 8x8ブロックが最初のブロックに似ているかどうかを確認する方法を考えたからです。それが十分に近い場合は、最初のブロックを送信し、両方のブロックに同じデータを使用してください。

これにより、デコード速度が向上し、動作するデータが少なくなるため、ビットレート転送が向上します。

これは簡単な作業であると思いました。だから私は自分の "変更" jpegエンコーダ/デコーダを構築しようとしました。 RGBからYCbCrへのコンバーターを構築しました。私はhuffmanエンコーディングを行うために "gzip"圧縮を残しました。そして、私が残した主な部分はDCT変換を行うことだけです。

しかし、これは私が立ち往生しています。私は速い8ポイント1d dct変換を見つけることができません。私はいくつかの1x8のIDの変換に分割することができます2Dの8×8変換を読む多くの記事によると、私はこの特定の変換を探しています。これは、処理が速いためにjpegを使用する多くの実装方法です。

だから私は、JPEGは、このような古いよく知られている標準的なもので、高速8ポイントの1次元DCTは、私だけで飛び出す必要がありますが、検索の数週間後に私は1つを見つけるためにまだ持っていることを考え出しました。

O（N^2）複雑さのアプローチを使用する多くのアルゴリズムが見つかりました。しかし、それは驚くほど遅いです。私はまた、高速フーリエ変換を使用するアルゴリズムを見つけました。そして、それらを変更してDCTを計算しました。このような下のリンクで一つとして：理論的には

https://www.nayuki.io/page/free-small-fft-in-multiple-languages

これはO（Nlog2（N））の「高速」の複雑さを持っている必要がありますが、私はそれを実行したときには、約12秒に私のi7のコンピュータを取ります"変更された" jpegをエンコード/デコードします。

なぜそれほど遅いのですか？はるかに速く行うことができる他のjavascript jpegデコーダがありますが、ソースコードを見てみると、どの部分がDCT/IDCT変換を行っているのかわかりません。

https://github.com/notmasteryet/jpgjs

私は考えることができる唯一のことは、多分DCTの背後にある数学はすでに事前計算されていて、ルックアップテーブルか何かに格納されています。しかし、私はgoogleで懸命に見えて、私はこれについて話しているものは何も見つけられません。

私の質問は、この「変更された」jpegエンコーダ/デコーダの8点1d dct変換を計算するための速い方法を見つける方法です。これに関する助けがあれば大いに感謝します。

私がこれをやりたい理由は、主な理由は自分のウェブサイトで携帯電話用の「インタラクティブ」なビデオを作りたいということです。これは、iOSがビデオを再生するたびに「ネイティブ」のクイックタイムプレーヤーをロードするなどの理由で実行できません。また、特にモバイルデバイスでビデオがどのようにレンダリングされるかをあまり制御していない場合、ビデオが別の時点に切り替わるのを「滑らか」に見せるのは難しいです。

誰もが提供できるヘルプをありがとうございます。

Answer 1

だから私の質問は、どこでどのように私は、このJPEGエンコーダ/デコーダ「修正」のための変換8ポイント1D DCTを計算するための高速な方法を構築することができます/見つけることができます。これに関する助けがあれば大いに感謝します。 （それはエンジンにinegrated前）

は、フラッシュの世界とそこにJPEGエンコーダに見てみましょう。
http://www.bytearray.org/?p=1089（ソースが提供されています）このコードには、 fDCTQuant()という名前のDCTを実行する関数が含まれています。

は、だから私はやっている私はJPGとして圧縮最初のフレームを送信します。次に、別のJpeg画像を送信します。

プログレッシブJPEGをご覧ください。私はこれがどのように動作するか、物事のいくつかを考え、どのようにデータ・ストリームが構築されていることは一種のこの記述に精通鳴ります（ない同じ、しかし、彼らの両方が、関連の方向に行く。IMO）

何これを修正して「各8x8ブロック」を圧縮するだけでなく、「次の」8x8ブロックが最初のブロックに似ているかどうかを確認することもできます。それが十分に近い場合は、最初のブロックを送信し、両方のブロックに同じデータを使用してください。

「類似」と「十分に近い」という表現が私の注目を集めています。通常使用される量子化テーブルを見てください。値が1だけ変化すると、8×8ブロックの位置、したがって適用される量指定子に応じて、その点の輝度の15％（通常は彩度チャネルの場合）の値が簡単に変化する可能性があります。

calculation with quantifier 40 
(may be included in the set even at the lowest compression rates 
at lower compression rates some quantifier can go up to 100 and beyond) 

change the input by 1 changes the output by 40. 
since we are working on 1byte value-range it's a change of 40/255 
that is about 15% of the total possible range 

だからあなたはあなたが「十分近い」と呼ぶもの本当に思いやりにする必要があります。

---

これをまとめてみましょう：データ量を減らすためにフレーム間の差異を利用するjpegに基づくビデオコーデック。それは私にはおなじみのものでもあります。

はそれを手に入れた：MPEG https://github.com/phoboslab/jsmpeg
*参照コードとの接続がありませんかコーダ

Answer 2

この本はDCT行列がガウス正規形に因数分解することができる方法を示しています。これがDCTを行う最速の方法でしょう。

http://www.amazon.com/Compressed-Image-File-Formats-JPEG/dp/0201604434/ref=pd_sim_14_1?ie=UTF8&dpID=41XJBED6RCL&dpSrc=sims&preST=_AC_UL160_SR127%2C160_&refRID=1Q0G2H5EFYCQW2TJCCJN

Answer 3

私はここで、様々なサイズの分離可能な整数2DのDCT（並びに他の変換）を実装：https://github.com/flanglet/kanzi/tree/master/java/src/kanzi/transformを。コードはJavaにありますが、実際にはこの種のアルゴリズムのために、どの言語でもほとんど同じです。最も興味深いのは、IMOは各方向を計算した後に行うリスケーリングです。目標（最大精度、16ビット計算、スケーリングなし...）に応じて、各ステップのスケーリング係数を変更することができます。イメージが非常に均一な領域に大きなブロックを使用すると、ビットが節約されます。