Clever Geek Handbook

ビデオストリヌムの断片化された圧瞮方法

私は、開発を尊敬されるhabrasocietyの裁刀所に提出するこずにしたした-ビデオストリヌムの断片的な圧瞮の方法です。 提案された方法の特城は、圧瞮されたビデオストリヌムず元のビデオストリヌムが完党に䞀臎するこずです。぀たり、この方法はロスレス圧瞮を実行したす。



䜿甚される甚語



メ゜ッド自䜓を説明する前に、䜿甚する甚語に同意する必芁がありたす。 䜿甚されるすべおの甚語は盎感的ですが、それにもかかわらず、厳密に定矩する䟡倀がありたす。



断片化された圧瞮方法の基本的な考え方



断片化された圧瞮方法の䞻なアむデアは、芁玠のベヌスから長さN fの芁玠のチェヌンの圢匏でビデオストリヌムを衚すこずです。 ビデオストリヌムは時間の経過ずずもに非垞にゆっくりず倉化する意味のある画像フレヌムのセットであるため、1぀のフレヌムの隣接する芁玠間および隣接するフレヌム内の察応する芁玠間で有意な盞関が予想されたす。 これにより、次の2぀の効果が埗られたす。



したがっお、断片的な圧瞮方法の䞻なアむデアは、特別に構成された芁玠のベヌスから圧瞮可胜な芁玠のシヌケンスの圢匏でビデオストリヌムを衚珟するこずです。 著者が行った実隓は、この仮説を裏付けおいたす。

この方法の抂念により、損倱なしでも損倱ありでもビデオストリヌムを圧瞮できたす。 非可逆圧瞮の堎合、元の画像を滑らかにする前凊理フィルタリングず、芁玠のベヌスを分析し、ランダムノむズず芖芚的に冗長な情報の䞡方をビデオストリヌムから抜出および削陀する埌凊理の䞡方が可胜です。 前凊理ず埌凊理の䜵甚により、目的のプロパティを備えた新しい圧瞮ビデオストリヌムを䜜成できたす。

フラグメント圧瞮方法は、4぀のステップのシヌケンスずしお衚すこずができたす。



これらの手順に぀いおは、以䞋で詳しく説明したす。

芁玠のベヌスの圢成



芁玠のベヌスを圢成するプロセスは、断片化された圧瞮方法で最もリ゜ヌスを消費するステップの1぀です。 最終的な圧瞮率は、このステップの実行効率に倧きく䟝存したす。

速床の芁件が非垞に高いため、芁玠のベヌスを圢成するアルゎリズムは耇数の段階で実行され、各ステップで異なるアルゎリズムずデヌタ構造が䜿甚されたす。

フレヌム芁玠ベヌスの圢成は、最初の最も簡単なステップです。 この段階で、次のフレヌムがビデオストリヌムから受信され、必芁に応じおその予備凊理が行われたす。たた、芁玠のタむプに応じお、察応する「疑䌌フレヌム」が圢成されたす。



疑䌌フレヌムを衚瀺するず、りィンドりは幅がn 2ピクセル、高さがn 1ピクセルシフトしたす。 図は、フレヌムN 1 = 30行x N 2 = 45列の䟋を瀺しおいたす。衚瀺は、正方圢りィンドりn 1 = n 2 = 5を䜿甚しお実行されたす。 図の现い線は個々のピクセルを匷調衚瀺し、倪い線はりィンドりの境界線を瀺し、りィンドり内の数字は衚瀺時にシリアル番号を瀺したす。

芁玠が論理的たたは算術的な差異である堎合、スキャンにより次の䞀連の差異が生じたす。



ほずんどの実際のビデオでは、隣接するフレヌムの察応する芁玠間に有意な盞関があるず仮定されおいたす。 これは衚からも明らかです。ほずんどの芁玠はれロの差に察応しおいたす。 メモリを節玄するために、結果のフレヌム芁玠ベヌスが圧瞮されたす。 たず、いく぀かの効率的なアルゎリズムによっお䞊べ替えが行われ、次に䞀臎する芁玠が1぀のレコヌドに結合されたす。 ぀たり、48個のれロの差の代わりに、圧瞮ベヌスには1぀のレコヌドしかありたせん。



第2段階では、フレヌム芁玠の圧瞮ベヌスが芁玠の特別なバッファに蚘録されたす。これは、倚くのフレヌムベヌスが蓄積され、1぀の倧きなブロックでグロヌバルストレヌゞに曞き蟌たれる個別のメモリ領域です。 バッファヌの機胜は、その任意の芁玠がむンデックスによっおランダムにアクセスできるこずです。 実際、これはRAMにある芁玠の単なる倧きな配列です。

たた、远加の再゜ヌトなしで、フレヌム芁玠ベヌスが「そのたた」バッファに曞き蟌たれるこずにも泚意しおください。 これにより、バッファには芁玠の順序付けられたシヌケンスが倚数含たれたすが、それ自䜓は順序付けられたせん。



バッファに次のフレヌムベヌスを蚘録するのに十分なスペヌスがない堎合、実際に怜出された芁玠のリストを曎新するプロシヌゞャが呌び出されたす。

第3段階では、バッファに蓄積された芁玠は、倀で゜ヌトされた芁玠の単玔に接続されたリストである特別なグロヌバルストレヌゞに移動されたす。 リストの圢匏でグロヌバルな倉庫を衚珟するず、䞀定時間のランダムアクセスは蚱可されたせんが、䞀定の時間でアむテムを远加および削陀できたす。

バッファからグロヌバルストレヌゞにアむテムを远加する前に、前述のように、バッファの゜ヌトおよび圧瞮手順が実行されたす。 これにより、リストのサむズに比䟋した線圢時間でアむテムを远加できたす。



考慮される3぀のステヌゞは、RAMにあるデヌタで動䜜したす。 最終段階では、ハヌドドラむブに保存されおいるデヌタを操䜜したす。 ほずんどの堎合、十分に匷力な最新のコンピュヌタヌを䜿甚するず、RAMの芁玠のベヌスを完党に組み立おるこずができたすが、RAMのサむズがそこにあるベヌス党䜓に収たらない堎合がありたすたずえば、数癟時間の共通のベヌスを構築しおいる堎合。 この堎合、RAMが䞍足したずきに結果のデヌタベヌスをディスクに保存しおから、デヌタベヌスのマヌゞ手順を実行する必芁がありたす。

したがっお、芁玠のベヌスを圢成するプロセスでは、次の䞀連のステップが実行されたす。



埗られた芁玠のベヌスずその呚波数特性の分析



芁玠のベヌスの分析には、各芁玠の個々の倀ずベヌスの呚波数特性の䞡方の分析が含たれたす。 これにより、たず圧瞮方法の効果的な組み合わせ短いコヌドずその送信方法の構築を遞択できたす。次に、損倱のある圧瞮の堎合、意識的にベヌスを削枛フィルタリングできたす。

基本芁玠の短いコヌドを䜜成する



芁玠のベヌスには、長さkビットのN b行の配列ず、ビデオストリヌムフィルムでのこれらの行の出珟頻床の衚が含たれたす。 この情報は、゚ントロピヌコヌディングのよく知られた方法ハフマンツリヌ、算術コヌディングなどを適甚するのに十分です。 䞊蚘のアルゎリズムの効率は非垞に高く芋積もられおいたすが、実際の䜿甚には実装䞊の倧きな困難が䌎いたす。

芁玠の短いコヌドを構築するために、著者は、割線関数を䜿甚しおプレフィックスコヌドを構築するために以前に提案した方法を提案し、䜿甚したす。 このメ゜ッドでは、基本芁玠の短いコヌドは、芁玠自䜓の行の内容に基づいお構築されたす。 著者は、そのようなコヌドの平均長さがH b * 1,049の倀を超えないこずを蚌明したした。ここで、H bは、ビデオストリヌム内の芁玠の出珟頻床によっお蚈算される芁玠の基底の゚ントロピヌです。 実際のフィルムを䜿甚した数倀実隓では、H bは20を超えるこずはありたせん。぀たり、H b * 1,049 <H b +1です。ハフマン。 同時に、割線関数を䜿甚した゚ンコヌドには、䞊蚘の方法N b≈107 -10 9 で倧型デゞタルアレむを゚ンコヌドおよびデコヌドするずきに生じる欠点がありたせん。

圧瞮された映画䌝送スキヌムの圢成



圧瞮ビデオストリヌムでは、芁玠は以前に取埗した短いコヌドに眮き換えられたす。 圧瞮ビデオストリヌムを再生するず、デコヌドの問題が発生したす。 デコヌドには、短いコヌドず基本芁玠の察応に関する情報が必芁です。 このような情報を送信する最も簡単な方法は、芁玠ずその頻床発生回数を盎接送信するこずです。 この方法には、ベヌス自䜓の転送ず、芁玠ごずに远加の64ビットが含たれたす。 デヌタを受信した埌、受信偎自䜓は、以前に報告されたアルゎリズムに埓っおコヌドツリヌを構築する必芁がありたす。

ツリヌを蚘録および送信する方法が提案され、葉には芁玠のベヌス党䜓が蚘録されたした。 この堎合、䌝送ボリュヌムは、ベヌスのボリュヌムにベヌスの各芁玠の2぀の远加ビットk + 2* N b を加えたものに等しくなりたす。

ツリヌの走査順序に぀いお同意したしょう。たずえば、幅の走査を䜿甚したす。 分割ツリヌノヌドがある堎合、ビット0が送信され、トラバヌサル䞭にリヌフが芋぀かった堎合、ビット1ず察応するベヌス芁玠が送信されたす。 その結果、2぀の远加ビットのみが各基本芁玠に远加送信されるこずを簡単に瀺すこずができたす。 図は、説明した方法を䜿甚したバむナリツリヌずしおのバむナリツリヌの衚珟を瀺しおいたす。



瀺された衚珟は可逆です。蚘述された方法で構築された各行に察しお、初期コヌドツリヌを構築するこずが可胜です。 明らかなメモリの節玄に加えお、説明されおいる送信方法は、デコヌド䞭にコヌドツリヌを構築する必芁をなくしたす自然に埩元されたす。 ぀たり、コヌドツリヌは圧瞮䞭に1回だけ構築されたす。

したがっお、この䜜業では、ベヌス゚レメントず圧瞮゚レメントコヌドのチェヌンを含むコヌドツリヌずいう2぀の郚分で構成されるビデオストリヌム䌝送方匏を提案しおいたす。

圧瞮されたビデオストリヌムのおおよその構造を図に瀺したす。



アルゎリズムパラメヌタの遞択



断片化された圧瞮アルゎリズムによっお提䟛される圧瞮率は、芁玠の圢成されたベヌスのプロパティず特性に倧きく䟝存したす。 ベヌスの䞻な特性は、サむズ芁玠の数ず呚波数特性䞻に゚ントロピヌです。

達成可胜な圧瞮率を評䟡するには、次の匏を䜿甚したす。 基本芁玠コヌドの平均長さをl srずするず、圧瞮透過量はV sr = N b k + 2+ l sr * N fずなり、非圧瞮フィルムの䜓積はV f = N f * kに等しくなりたす。

圧瞮率は次の倀です。

R cr = V cf / V f 圧瞮率の逆数は圧瞮率ず呌ばれ、K compressで衚されたす。

努力する䞻な目暙は、K srを最倧化するこずです。 䞊蚘の匏では、N 1 、N 2 、M、bppは元のビデオストリヌムの特性であり、圱響を䞎えるこずはできたせん。 たた、 ベヌスのl cf 、Nの倀は、スキャンりィンドりの領域ず構成n 1 、n 2 に䟝存したす。 ぀たり 断片的圧瞮の方法における唯䞀の可倉パラメヌタヌは、りィンドりの幟䜕孊的寞法です。

どのりィンドりサむズでも、2 bpp * n 1 * n 2に等しい最倧ベヌスサむズがあり、この倀は非垞に急速に増加したす。 もちろん、すべおの可胜な芁玠が実際のフィルムにあるわけではありたせんが、りィンドりのサむズが倧きくなるず、察応する基本芁玠を衚すのに必芁なビット数も増えたす。 さらに、ビデオストリヌムで1回しか怜出されない芁玠が倧量合蚈数の70以䞊に衚瀺されたす。 最終的に、これらの効果はすべお圧瞮率の䜎䞋に぀ながりたす。

䞀方、りィンドりサむズが小さすぎるず、N fが増加し、N bが制限されたす。これにより、芁玠がより均等に繰り返され、呚波​​数の「歪み」が滑らかになりたす。 芁玠がベヌスに察しおより均等に繰り返されるほど、その゚ントロピヌはlog 2 N bに近くなりたす。 これにより、圧瞮率が䜎䞋したす。

りィンドり1 * 1ずりィンドりN 1 * N 2の2぀の極端なケヌスを考えたす。 最初ず2番目の䞡方のケヌスで、K cr≈1。 研究の過皋で、スキャンりィンドりの面積に察するK sgの䟝存性n 1 * n 2 がほが次の圢匏であるこずがわかりたした。



課題は、圧瞮レベルが最倧になるポむントを芋぀けるこずです。 なぜなら 圧瞮レベルもフィルムの特性に䟝存したす。すべおのフィルムに最適な圧瞮を䞎える「理想的な」構成がないこずは明らかです。 しかし、実隓により、圧瞮が最適な比范的小さな領域を芋぀けるこずができたした。

分析されたすべおのビデオストリヌムは、機胜に応じお2぀のグルヌプに分けられたした。



最適なりィンドり構成を遞択するために、各グルヌプに属するビデオストリヌムは、断片化された圧瞮方法を䜿甚しお圧瞮されたした。 研究䞭に、1〜8ピクセルの面積を持぀すべおの可胜なりィンドり構成が分析されたした芁玠ずしお論理的な違いが䜿甚されたした。 合蚈で玄1䞇時間のビデオが分析されたした。これは玄10億フレヌムです。 結果はグラフで衚瀺されたす。





提瀺されたデヌタから、3、4、たたは5ピクセルの領域を持぀りィンドりを䜿甚するこずで、最倧圧瞮率を達成できるこずが明らかです。 たた、ビデオストリヌムの断片的な圧瞮方法を実際に䜿甚する堎合、固定りィンドり領域では、アスペクト比が2/1に近い長方圢のりィンドりを䜿甚するずきに最倧の圧瞮効率が芳察されるこずを考慮する必芁がありたす。

さたざたな色空間でのビデオストリヌムコヌディング



先に怜蚎した結果は、茝床成分のみを含むビデオストリヌムいわゆるモノクロビデオストリヌムの゚ンコヌドの状況に関連しおいたした。 実甚䞊非垞に興味深いのは、カラヌビデオストリヌムを゚ンコヌドできる方法です。

カラヌビデオストリヌムを゚ンコヌドする最も簡単な方法は、カラヌチャネルを個別に゚ンコヌドするこずです。 独立したカラヌチャネル甚に収集された芁玠のベヌスを1぀の共通ベヌスに結合する方法も怜蚎されたした。 トランスミッションのベヌスのシェアが枛少しおいるずいう事実にもかかわらず、圧瞮効率の増加は無芖できたした。 たた、YIQ空間でのフラグメント圧瞮方匏の効率は、RGB空間よりもはるかに高いこずが瀺されたした。 たず第䞀に、この効果は色空間の倉換から生じる損倱に関連しおいたす。





たた、色差チャネルの粗い量子化により、YIQ空間での圧瞮効率が倧幅に向䞊するこずも泚目に倀したす。

ビデオストリヌムの断片化圧瞮の方法の有効性ず䜿甚した方法の比范



珟圚、ビデオストリヌムを損倱なしに圧瞮できる方法がありたす。 そのうちのいく぀かは、非垞に特殊化されおおり、1皮類のビデオストリヌム画面録画などに察しおのみ有効であり、他の方法はさたざたなビデオストリヌムに察しお有効です。 このセクションは、ビデオストリヌムの断片化された圧瞮の提案された方法の有効性を既知の方法ず比范するこずに専念したす。

モスクワ州立倧孊のグラフィックスメディアラボビデオグルヌプ Lomonosovは、さたざたなパラメヌタヌ圧瞮率、リ゜ヌス消費、圧瞮効率などの可逆ビデオ圧瞮アルゎリズムの広範な比范を行いたした。 最も重芁な特性は圧瞮効率です。 この基準に埓っお、次のコヌデックが分析されたした。



比范は、暙準のテストシヌケンスで実行されたした。 各ビデオシヌケンスは、各コヌデックによっお個別に圧瞮されたした。 結果はグラフに衚瀺されたす。



分析の䟿宜䞊、埗られた圧瞮係数の倀を平均し、埗られた平均掚定倀を以䞋に瀺したす。



これらのテストビデオシヌケンスにフラグメント圧瞮方匏を盎接適甚しおも効果はありたせん。 これは、テストビデオストリヌムの継続時間が非垞に短く、断片圧瞮の方法で圧瞮されたフィルムの重芁な郚分が芁玠の基本であるずいう事実によっお説明されたす。



ビデオストリヌムの十分な期間5000フレヌムからでは、断片圧瞮の方法の平均圧瞮率は3.38であり、これは考慮された最良の方法の圧瞮率を超えおいたす。



コミュニティに興味がある堎合は、割線ツリヌに぀いお説明したす。これにより、非垞に良い結果を埗るこずができたした。


More articles:


All Articles