(57)【要約】  データ長の最適化に係るステップ数を削減し、データ長の最適化処理を高速化する。量子化装置は、複数のデータ長について、画像の圧縮による画質の劣化と圧縮率とを加味したコストを計算する処理部を含む。コストを計算する処理は、複数のデータ長の間で、部分的に共通である。処理部は、複数のデータ長の間で共通な処理を、分散しつつ並列に実行することにより、複数のデータ長の中で、コストが最小となる１つのデータ長を、最適なデータ長として求める。
2018135520.tif 000002
【特許請求の範囲】
【請求項１】
画像に対する量子化処理を行う量子化装置であって、
複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味したコストを計算する処理手段を含み、
前記コストを計算する処理は、前記複数のデータ長の間で、部分的に共通な処理であって、
前記処理手段は、
前記複数のデータ長に関して並列に動作し、
前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行するコスト計算手段と、
前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として求める判定手段とを有する
ことを特徴とする量子化装置。
【請求項２】
前記コスト計算手段は、
各データを量子化しない際のコストの量子化順方向部分和と、各データを量子化する際のコストの量子化逆方向部分和とを求め、前記量子化順方向部分和と前記量子化逆方向部分和とを足し合わせることで、前記複数のデータ長についての前記コストを並列に計算する請求項１に記載の量子化装置。
【請求項３】
前記判定手段は、
前記複数のデータ長についての前記コストを階層的かつ並列に比較することによって、前記コストが最小値となるデータ長を判定することを特徴とする請求項１又は２に記載の量子化装置。
【請求項４】
前記複数のデータ長について、特定の条件を満たす画素が存在することを示すフラグをそれぞれ求め、前記フラグに対して並列処理を実行することによって、前記コストを計算するために必要な、前記画像の圧縮率を計算するレート計算手段をさらに含むことを特徴とする請求項１から３のいずれか１つに記載の量子化装置。
【請求項５】
前記レート計算手段は、前記フラグの部分和を並列に計算することを特徴とする請求項４に記載の量子化装置。
【請求項６】
前記量子化処理は、動画像符号化におけるRDOQ（Rate Distortion Optimized Quantization）処理であって、
前記コスト計算手段は、各データ長のコストとして、入力された係数のうち最後に符号化される最終係数位置のコストを計算し、
前記判定手段は、計算された複数の最終係数位置の中から、コストが最小となる最終係数位置を、前記最適なデータ長として決定し、
前記処理手段は、前記複数の最終係数位置に関して並列動作することを特徴とする請求項１から５のいずれか１つに記載の量子化装置。
【請求項７】
画像に対する量子化処理を量子化装置で実施する量子化方法であって、
複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味した量子化のコストを計算し、
前記コスト計算は、前記複数のデータ長の間で、部分的に共通な処理を含み、
前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行し、
前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として出力する、
量子化方法。
【請求項８】
各データを量子化しない際のコストの量子化順方向部分和と、各データを量子化する際のコストの量子化逆方向部分和とを求め、前記量子化順方向部分和と前記量子化逆方向部分和とを足し合わせることで、前記複数のデータ長についての前記コストを並列に計算する、請求項７に記載の量子化方法。
【請求項９】
前記複数のデータ長のコストを階層的かつ並列に比較することによって、コストが最小値となるデータ長を並列に判定する、請求項７又は８に記載の量子化方法。
【請求項１０】
前記複数のデータ長の各々について、特定の条件を満たす画素が存在することを示すフラグを求め、前記フラグに対して並列処理を実行することによって、前記画像の圧縮率を計算することを特徴とする請求項７または８に記載の量子化方法。
【請求項１１】
前記フラグの部分和を並列に計算することを特徴とする請求項１０に記載の量子化方法。
【請求項１２】
前記量子化処理は、動画像符号化におけるRDOQ（Rate Distortion Optimized Quantization）処理であって、
入力された係数のうち最後に符号化される最終係数位置のコストを並列に計算し、
前記複数の最終係数位置の中から、前記コストが最小となる最終係数位置を、前記最適なデータ長として決定することを特徴とする請求項７から１１のいずれか１項に記載の量子化方法。
【請求項１３】
コンピュータに、画像に対する量子化処理を行わせる量子化プログラムであって、前記量子化プログラムは、前記コンピュータに、
複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味したコストを計算する処理を実行させるものであり、
前記コストを計算する処理は、前記複数のデータ長の間で、部分的に共通な処理を含み、
前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行するコスト計算処理と、
前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として求める判定処理と、
を実行させる量子化プログラムを記録した、一時的でない記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は量子化装置、量子化方法および記録媒体に関する。
【背景技術】
【０００２】
動画像を圧縮する規格としてH.264/AVC(Advanced Video Codec)が広く用いられている。また、4K/8Kといった高解像度動画像圧縮向けの次世代動画像圧縮規格としてH.265/HEVC(High Efficiency Video Codec)が知られている。【０００３】
これら動画像圧縮技術は、予測処理と、変換量子化処理と、エントロピー符号化とから成る。予測処理では、フレーム間またはフレーム内の冗長度を下げる処理を行う。変換量子化処理では、予測残差信号の空間成分を周波数成分に変換し量子化することで、空間的冗長度を下げる処理を行う。エントロピー符号化では、データの発生頻度に応じて、可変長符号化を動的に割り当てる処理を行う。【０００４】
変換量子化処理においては、直交変換され周波数成分に変換された変換係数を量子化することで、エントロピー符号化に入力する情報量を削減することができる。一方で、変換量子化処理の際に量子化誤差が発生するので、復号化装置において、圧縮符号化された画像を復号して再生する際の復号画像に画質劣化が生じる。HEVCでは、こうした画質劣化とビットレート削減とのトレードオフ関係を考慮した選択をする際に、レート歪み最適化(RDO: Rate Distortion Optimization)が用いられる。【０００５】
RDOでは、先ず、各選択において画質劣化(D)とビットレート(R)とを導出する。そして、RDOでは、これら画質劣化DおよびビットレートRと、ラグランジュ乗数λとを用いて、RDコストを得る。RDコストJは以下の式(1)で示される。【０００６】
【数１】
2018135520.tif 000003
【０００７】
このように、RDOでは、RDコストのより小さい選択肢を採用することで、より高い符号化効率を実現できる。【０００８】
量子化処理においては、量子化後の係数を最適化する技術として、レート歪み最適量子化（RDOQ: Rate Distortion Optimized Quantization）が知られている。【０００９】
例えば、非特許文献１は、HEVC規格に基づいたリファレンスソフトウェアHM(HEVC Test Model)を記載しており、量子化丸め誤差最適化、係数グループ(CG: Coefficient Group)最適化、最終係数位置最適化の３つの処理から構成されるRDOQを開示している。【００１０】
量子化丸め誤差最適化では、量子化によって除算された係数値を切り上げた場合と、切り下げた場合とのRDコストを比較し、最適な係数値を採用する。【００１１】
係数グループ(CG: Coefficient Group)最適化では、量子化された係数を係数グループごとに評価する。具体的には、係数グループ最適化では、各係数グループ内の係数値が全て0であった場合に、RDコストが改善するか評価し、改善する場合には採用する。ここで、係数グループとは後段の符号化処理における処理単位である。一方で、変換および量子化では、処理単位は変換ブロックとなる。【００１２】
図２は、変換ブロックと係数グループとの関係を示す図である。後段の符号化処理では、係数グループ単位で各係数値が符号化される。したがって、係数グループ内の係数値を全て0にすることで、符号化される情報量を大きく削減することができる。【００１３】
最終係数位置最適化では、最初に符号化される最も高周波な係数（以下、「最終係数」と示す）を選択する。【００１４】
図３は後段の符号化処理における二値化処理の様子を示す図である。量子化された各係数は、係数グループごとにシンタックスに従って二値化される。ここで、係数は、図２に示されるように、例えば斜め右上がりスキャン順（以下、スキャン順または符号化順とも呼ぶ）で処理される。ここで、最終係数とは、スキャン順で最初に非ゼロな係数となる。
また、シンタックスには最終係数の位置情報が含まれ、スキャン順で最終係数以降の各係数値が符号化される。したがって、最終係数位置をスキャン順で後ろにずらすことによって、ビットレートを削減することができる。【００１５】
RDOQでは、一連の最適化処理によって符号化効率は大きく改善する。一方で、RDOQでは、各選択候補に関してRDコストを毎回計算する必要があり、その計算量が大きく増加する。また、動画像符号化では、並列処理によって高速化を実現する手法が一般的であるが、RDOQでは、各選択肢のRDコストを計算する際にレートを計算する必要がある。レート計算では、各係数値を直列に並べ、シンタックスに従って処理する必要があるため、並列処理が困難である。【００１６】
特許文献１は、このような課題を解決する技術を記載している。特許文献１に記載の係数絶対値決定部では、レート計算において係数間で依存関係のあるシンタックスにかかるbin数を近似する。ここでbin数とは、符号化において入力を二値化した後のbit数を表す。bin数は、RDO簡略化においてビットレートの近似として一般的に使われる指標である。bin数を用い、さらに係数間に依存関係のある係数を近似することで、量子化丸め誤差の最適化と係数グループの最適化とを並列処理できる。一方で、最終係数位置の最適化は、近似を用いたとしても各最終係数位置候補のRDコストを並列に計算することが難しく、並列処理が困難である。【００１７】
同様に、特許文献２は、量子化丸め誤差を係数単位で並列処理する技術を記載している。特許文献２に記載の量子化装置では、係数グループごとに自分よりも高周波な係数グループ、つまりスキャン順で前にある係数グループを非有意であると仮定し、レートおよびRDコスト計算を行う。このような仮定を置くことで、係数丸め誤差最適化、係数グループの最適化、最終係数位置の最適化を1passで実行可能である。また、係数最適化部では、係数絶対値決定部と同様にレート計算を近似する。係数間の依存関係をなくすことで、係数ごとの並列処理が可能である。一方で、特許文献２に記載の技術を用いても、最終係数位置の最適化の係数単位での並列処理は困難である。このような場合、例えばGPU（Graphic Processing Unit）のような高並列プロセッサを用いたGPGPU(General Purpose Computing on Graphic Processing Unit)のような超高並列計算を用途とした場合に、変換係数の量子化を効率よく処理ができない。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２０１５−５０６０８号公報
【特許文献２】特開２０１６−１３４８６０号公報
【非特許文献】
【００１９】
【非特許文献１】K. McCann, C. Rosewarne, B. Bross, M. Naccari, K. Sharman, G. Sullivan, JCTVC-S1002, “High efficiency video coding (HEVC) test model 16 (HM16) improved encoder description”, October 2014
【非特許文献２】M.Harris, S.Sengupta, J.D.Owens, “GPU Gems 3”, Chapter.39, “https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_pref01.html”
【非特許文献３】D. Horn, “GPU Gems 2”, Chapter. 36, “https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_inside_front_cover.html”
【発明の概要】
【発明が解決しようとする課題】
【００２０】
上述したように、先行技術の量子化装置の問題点は、RDOQ処理において最終係数位置の最適化を並列処理できない点である。先行技術の最終係数位置の最適化では、逆スキャン順に最終係数位置候補を更新し、RDコストを順次計算する必要がある。このため、GPUのような高並列なアーキテクチャでは、変換係数の量子化を効率的に処理できない。【００２１】
本発明の目的は、上述した課題を解決する、量子化装置、量子化方法および量子化プログラムを提供することにある。
【課題を解決するための手段】
【００２２】
本発明による量子化装置は、画像に対する量子化処理を行う量子化装置であって、複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味したコストを計算する処理手段を含み、前記コストを計算する処理は、前記複数のデータ長の間で、部分的に共通な処理であって、前記処理手段は、前記複数のデータ長に関して並列に動作し、前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行するコスト計算手段と、前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として求める判定手段とを有することを特徴とする。【００２３】
本発明の量子化方法は、画像に対する量子化処理を量子化装置で実施する量子化方法であって、複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味した量子化のコストを計算し、前記コスト計算は、前記複数のデータ長の間で、部分的に共通な処理を含み、前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行し、前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として出力する。【００２４】
本発明の記録媒体は、コンピュータに、画像を量子化する量子化処理を行わせる量子化プログラムを記録した、一時的でない記録媒体であって、前記量子化プログラムは、前記コンピュータに、複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味したコストを計算する処理を実行させるものであり、前記コストを計算する処理は、前記複数のデータ長の間で、部分的に共通な処理を含み、前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行するコスト計算処理と、前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として求める判定処理と、を実行させる。
【発明の効果】
【００２５】
本発明によれば、データ長の最適化に係るステップ数を削減し、データ長の最適化処理を高速化することができる。
【図面の簡単な説明】
【００２６】
【図１】非特許文献１に記載の量子化装置１０００を示すブロック図である。
【図２】変換ブロックと係数グループの関係とその処理順を示す説明図である。
【図３】HEVCにおける二値化の様子を示す説明図である。
【図４】特許文献１に記載の量子化装置２００を示すブロック図である。
【図５】特許文献２に記載の量子化装置３００を示すブロック図である。
【図６】非特許文献１に記載の最終係数位置最適化部１４００を示すブロック図である。
【図７】非特許文献１に記載の最終係数位置最適化処理を示すフローチャートである。
【図８】本発明の第１の実施形態の量子化装置１０００Ａの構成を示すブロック図である。
【図９】図８に示した量子化装置１０００Ａに用いられる最終係数位置最適化部１５００の構成を示すブロック図である。
【図１０】本発明の第１の実施形態の最終係数位置最適化部１５００の動作を示すフローチャートである。
【図１１】本発明による最終係数位置のコスト計算の様子を示す説明図である。
【図１２】Parallel Scanの様子を示す説明図である。
【図１３】本発明の第２の実施形態の量子化装置１０００Ｂの構成を示すブロック図である。
【図１４】図１３に示した量子化装置１０００Ｂに用いられる最終係数位置最適化部１６００の構成を示すブロック図である。
【図１５】本発明の第２の実施形態の最終係数位置最適化部１６００の動作を示すフローチャートである。
【図１６】本発明の第２の実施形態によるレート計算の一例を示す説明図である。
【図１７】本発明の実施例による量子化装置の機能を実現可能な情報処理装置の構成例を示すブロック図である。
【発明を実施するための形態】
【００２７】
［関連技術］
本発明の理解を容易にするために、最初に、関連技術について説明する。
【００２８】
図１は、非特許文献１に開示されている量子化装置１０００の構成を示すブロック図である。量子化装置１０００は、画像または画像の画素値を変換した変換係数を量子化する量子化処理を行う。
【００２９】
量子化装置１０００は、量子化部１１００と、量子化丸め誤差最適化部１２００と、係数グループ最適化部１３００と、最終係数位置最適化部１４００とから成る。
【００３０】
量子化部１１００では、動画像を圧縮する規格に沿って、変換係数に対して量子化を実施する。例えば、HEVCでは、量子化処理は次式(2)で表すことができる。
【００３１】
【数２】
2018135520.tif 000004
【００３２】
ここでｑｉはi番目の係数を表し、ｃｉはi番目の量子化後の係数を表す。またｍｉは量子化重み付け係数を表し、qPは量子化パラメータを表し、BitDepthは入力信号の画素ビット精度を表し、Nは変換ブロック（TB: Transform Block）のサイズを表す。記号「％」は除算を表す。ここで変換ブロックは変換および量子化の処理単位である。
【００３３】
量子化丸め誤差最適化部１２００では、前述の量子化丸め誤差最適化を実施する。
【００３４】
係数グループ(CG: Coefficient Group)最適化部１３００では、前述の係数グループ最適化を実施する。
【００３５】
最終係数位置最適化部１４００では、前述の最終係数位置最適化を実施する。以下では最終係数位置最適化部１４００の動作を説明する。
【００３６】
最終係数位置最適化部１４００は、スキャン順で非ゼロな係数値を順番に最終係数位置候補として選択し、RDコストを求める。この際に、最終係数より前の係数は符号化されないため、最終係数位置最適化部１４００は、スキャン順で最終係数位置候補より前にある係数を全てゼロとして扱う。最終係数位置最適化部１４００は、各最終係数位置候補のRDコストを比較し、最適な最終係数位置を選択する。
【００３７】
すなわち、最終係数位置最適化部１４００は、圧縮による画質の劣化と圧縮率とをコスト計算によって最適化し、最適なデータ長を決める処理部として働く。
【００３８】
RDOQでは、このような一連の最適化処理によって、符号化効率を大きく改善することができる。一方で、RDOQでは、各選択候補に関してRDコストを毎回計算する必要があり、計算量が大きく増加してしまう。また、動画像符号化では、並列処理によって高速化を実現する手法が一般的であるが、RDOQでは、各選択肢のRDコストを計算する際にレートを計算する必要がある。レート計算では、各係数値を直列に並べ、シンタックスに従って処理する必要があるため、並列処理が困難である。
【００３９】
図４は、特許文献１に記載の技術を用いた量子化装置２００の構成を示すブロック図である。
【００４０】
量子化装置２００は、スケーリング部２１０と、係数絶対値決定部２２０と、最終係数位置決定部２３０と、から成る。
【００４１】
スケーリング部２１０は、第１乃至第Ｎのスケーリング部分２１１、２１２、・・・、２１Ｎを有し、それぞれ、対象ブロックの第１乃至第Ｎの変換係数Ｃ１〜ＣＮに対してスケーリングを行う。ここで、Ｎは２以上の整数である。ここで、対象ブロックとは、入力画像と予測画像との差分である予測残差信号に対して直交変換を行う処理単位である。入力画像は、動画像を構成する画像である。予測画像は、イントラ予測や動き補償予測等によって生成される画像である。
【００４２】
係数絶対値決定部２２０は、第１乃至第Ｎの係数絶対値決定部分２２１、２２２、・・・、２２Ｎを有し、それぞれ、第１乃至第Ｎの変換係数Ｃ１〜ＣＮのスケーリング結果を量子化した、第１乃至第Ｎの量子化係数Ｐ１〜ＰＮの係数絶対値を決定する。
【００４３】
最終係数位置決定部２３０は、係数絶対値決定部２２０によって決定された第１乃至第Ｎの量子化係数Ｐ１〜ＰＮの係数絶対値に基づいて、対象ブロックの最終係数位置を決定する。
【００４４】
係数絶対値決定部２２０では、レート計算において係数間で依存関係のあるシンタックスにかかるbin数を近似する。ここで、bin数とは、符号化において入力を二値化した後のbit数を表す。bin数は、RDO簡略化においてビットレートの近似として一般的に使われる指標である。bin数を用い、さらに係数間に依存関係のある係数を近似することで、量子化丸め誤差の最適化と係数グループの最適化とを並列処理できる。
【００４５】
一方で、最終係数位置決定部２３０での最終係数位置の最適化は、近似を用いたとしても各最終係数位置候補のRDコストを並列に計算することが難しく、並列処理が困難である。
【００４６】
図５は、特許文献２に記載の技術を用いた量子化装置３００の構成を示すブロック図である。
【００４７】
量子化装置３００は、制御部３１０と、スケーリング部３２０と、係数最適化部３３０と、記憶部３４０と、係数グループ最適化部３５０と、最終係数位置判定部３６０と、補正値算出部３７０と、判定部３８０とを有する。
【００４８】
制御部３１０は、分割部の一例であり、直交変換係数が算出されたTU(Transform Unit)が入力されるごとに、そのTUを係数グループ単位で分割する。なお、TUは、直交変換の単位となるブロックである。制御部３１０は、低周波数側の係数グループから順に、スケーリング部３２０へ渡す。
【００４９】
スケーリング部３２０は、係数グループが入力される度に、その係数グループに含まれる直交変換係数ごとに、その直交変換係数を量子化した値である量子化係数の候補のリストを作成する。スケーリング部３２０は、係数グループに含まれる各直交変換係数についての量子化係数の候補を係数最適化部３３０へ渡す。
【００５０】
係数最適化部３３０は、係数グループごとに、係数グループに含まれる各直交変換係数について、対応する量子化係数の候補の中から、RDコストが最小となる候補を特定し、その候補を、その直交変換係数に対する量子化係数とする。
【００５１】
係数最適化部３３０は、求めた各量子化係数を記憶部３４０に保存するとともに、係数グループ最適化部３５０、補正値算出部３７０及び最終係数位置判定部３６０へ渡す。係数最適化部３３０は、各直交変換係数について、量子化係数の候補の一つである0について算出した符号化誤差も記憶部３４０に保存する。
【００５２】
係数グループ最適化部３５０は、低周波数側から順に、係数グループごとに、その係数グループに含まれる量子化係数を0にするか否かを判定する。
【００５３】
最終係数が含まれる係数グループについては、係数グループ最適化の対象外であるため、係数グループ最適化部３５０は、着目する係数グループよりも高周波数側に最終係数が存在すると仮定する。そして係数グループ最適化部３５０は、着目する係数グループ内の量子化係数を維持した場合のその係数グループ全体のRDコストCGCost(m)と、着目する係数グループ内の全ての量子化係数を0に置換した場合のその係数グループ全体のRDコストCGCost0(m)を算出する。
【００５４】
係数グループ最適化部３５０は、着目する係数グループについて、CGCost0(m)がCGCost(m)よりも小さい場合、その係数グループに含まれる量子化係数を0に置換することを決定する。一方、係数グループ最適化部３５０は、CGCost0(m)がCGCost(m)以上である場合、その係数グループに含まれる量子化係数を維持することを決定する。そして係数グループ最適化部３５０は、その判定結果を表すフラグを記憶部３４０に保存するとともに、判定部３８０へ通知する。
【００５５】
補正値算出部３７０は、係数グループ間でのRDコストの比較に利用する、RDコストの補正値を、係数グループごとに算出する。
【００５６】
補正値算出部３７０は、着目する係数グループについての補正値を算出し、算出した補正値を最終係数位置判定部３６０へわたす。
【００５７】
最終係数位置判定部３６０は、低周波数側から順に、係数グループごとに、その係数グループに最終係数が含まれると仮定して、最終係数の候補を求める。
【００５８】
最終係数位置判定部３６０は、最終係数の位置及びその最終係数の位置に対応するTU全体のRDコストを判定部３８０へ通知する。
【００５９】
判定部３８０は、最終係数位置判定部３６０により求められた最終係数の位置に対応する、TU全体のRDコストと、TUに含まれる全ての量子化係数を0に置換するときのRDコストとを比較する。
【００６０】
特許文献２に記載の量子化装置３００では、係数グループごとに自分よりも高周波な係数グループ、つまりスキャン順で前にある係数グループを非有意であると仮定し、レートおよびRDコスト計算を行っている。このような仮定を置くことで、係数丸め誤差最適化、係数グループの最適化、最終係数位置の最適化を1passで実行することが可能である。
【００６１】
また係数最適化部３３０では、図４に図示した係数絶対値決定部２２０と同様に、レート計算を近似する。係数間の依存関係をなくすことで、係数ごとの並列処理が可能である。
【００６２】
一方で、特許文献２に記載の技術を用いても、最終係数位置の最適化を係数単位での並列処理で行うのは困難である。このような場合、例えばGPU（Graphic Processing Unit）のような高並列プロセッサを用いたGPGPU(General Purpose Computing on Graphic Processing Unit)のような超高並列計算を用途とした場合に、変換係数の量子化を効率よく処理ができない。
【００６３】
図６は、非特許文献１に記載の最終係数位置最適化部１４００の構成を示すブロック図である。
【００６４】
最終係数位置最適化部１４００は、量子化処理された量子化後変換係数を入力として、最終係数位置に関して最適化された最適化後変換係数を出力する。
【００６５】
最終係数位置最適化部１４００は、係数コスト計算部１４１０と、最終係数コスト計算部１４２０と、最終係数コスト判定部１４３０とから成る。
【００６６】
係数コスト計算部１４１０は、量子化後変換係数を入力として、各変換係数を符号化した際のコストと符号化しない際のコストとを計算する。尚、各変換係数を符号化した際のRDコストと符号化しない際のRDコストとは、量子化丸め誤差最適化部１２００（図１）で算出することもできる。この場合には、係数コスト計算部１４１０を省略できる。
【００６７】
次いで、最終係数コスト計算部１４２０では、現在の最終係数位置候補のRDコストを計算する。ここで、最終係数位置候補は、スキャン順で各係数が順次設定される。
【００６８】
なお、最終係数位置候補は、データ長候補とも呼ばれる。従って、係数コスト計算部１４１０と最終係数コスト計算部１４２０との組み合わせは、各データ長候補のコストを順次に（一つずつ）計算するコスト計算部として働く。
【００６９】
最終係数コスト判定部１４３０は、最適な最終係数位置を保持する機能を有する。最終係数コスト判定部１４３０は、現在保持する最適な最終係数位置候補のRDコストと、最終係数コスト計算部１４２０で計算した最終係数位置候補のRDコストとを比較し、RDコストが低い方を最適な最終係数位置として選択する。
【００７０】
したがって、最終係数コスト判定部１４３０は、複数のデータ長候補の中からコストが最小となるデータ長候補を順次に（一つずつ）判定して、最適なデータ長を求める判定部として働く。
【００７１】
以下では、最終係数位置候補のRDコスト計算方法について説明する。
【００７２】
最終係数位置をlとしたときのRDコストＪｌａｓｔ=ｌは、TBの大きさをN、任意の係数位置iの係数を符号化したときのRDコストをＪｉ，ｃｏｄｅ、0にしたときのRDコストをＪｉ，ｃｕｔとすると、以下の式(3)で表される。
【００７３】
【数３】
2018135520.tif 000005
【００７４】
また、Ｊｌａｓｔ=ｌとＪｌａｓｔ=ｌ＋１との間の関係は、以下の式(4)で表すことができる。
【００７５】
【数４】
2018135520.tif 000006
【００７６】
(4)式より、最終係数位置l+1のRDコストは、最終係数位置lのRDコストＪｌａｓｔ＝ｌにＪｉ，ｃｕｔを足し合わせ、Ｊｉ，ｃｏｄｅを引けば良いことがわかる。このように、最終係数位置候補のRDコストから最終係数位置候補の係数値を符号化したときのRDコストと符号化しないときのRDコストを足し算または引き算することで、スキャン順で次の最終係数位置候補のRDコストを求めることができる。
【００７７】
図７は、非特許文献1に記載の最終係数位置最適化処理の流れを示すフローチャートである。
【００７８】
はじめに、係数コスト計算部１４１０において、各係数を符号化した際のRDコスト（図７中では、Ｊｉ，ｃｏｄｅと示す）と、符号化しない際のRDコスト（図７中では、Ｊｉ，ｃｕｔと示す）とを計算する。
【００７９】
最終係数位置最適化部１４００は、現在のRDコスト（図７中では、Ｊｃｕｒと示す）を現在のＴＢのコスト、すなわち最終係数位置最適化前のRDコストで初期化する（ステップＳ１０１）。
【００８０】
以下では、最終係数位置最適化部１４００は、スキャン順で最初の係数ブロックから順次処理する。また、最終係数位置最適化部１４００は、係数ブロック内の係数に関してもスキャン順に順次処理する。
【００８１】
まず、最終係数位置最適化部１４００は、現在着目する最終係数（図７中では、Levelｃｕｒと示す）が非ゼロか否かチェックする（ステップＳ１０２）。現在着目する最終係数位置が非ゼロだった場合、ステップＳ１０３に進み、ゼロだった場合には、次の最終係数位置候補に関する処理に進む。
【００８２】
現在着目する最終係数位置が非ゼロだった場合、最終係数コスト計算部１４２０は、現在のRDコスト（図７中では、Ｊｃｕｒと示す）に、レートのコスト（図７中では、RATEｃｕｒと示す）を足し合わせる（ステップＳ１０３）。
【００８３】
レートは、例えば非特許文献１記載の技術ではCABAC(Context-Adaptive Binary Arithmetic Coding)の出力ビット数が有りうるが、特許文献１や特許文献２に記載の技術のように、CABAC入力前のbin数を用いて近似しても良い。近似をする際には、CABACの出力ビット数を用いる際と比較して、得られるレートの精度が落ち、画質またはビットレートの劣化が生じる。
【００８４】
次いで、最終係数コスト判定部１４３０は、現在のRDコスト（図７中では、Ｊｃｕｒと示す）が最適な最終係数位置候補のRDコスト（図７中では、Ｊｂｅｓｔと示す）よりも改善するか否かをチェックする（ステップＳ１０４）。改善する場合、ステップＳ１０５に進み、改善しない場合には、ステップＳ１０６に進む。
【００８５】
次いで、現在のRDコストが最適な最終係数位置候補のRDコストよりも改善する場合（ステップＳ１０４のｙｅｓ）、最終係数コスト判定部１４３０は、最適な最終係数位置候補を更新する（ステップＳ１０５）。
【００８６】
次いで、最終係数コスト判定部１４３０は、次の最終係数位置候補に着目する前に、現在着目している係数をゼロにカットする。具体的には、最終係数コスト判定部１４３０は、式（４）のように、現在のコスト（図７中では、Ｊｃｕｒと示す）からＪｉ，ｃｕｔを足し、Ｊｉ，ｃｏｄｅを引く（ステップＳ１０６）。
【００８７】
以下同様に、最終係数位置最適化部１４００は、全ての変換係数、係数グループに関して処理する。
【００８８】
このようにl=0から開始し、順次lを更新することで、各最終係数位置候補のRDコスト計算を省略でき、最終係数位置候補の探索をより小さい計算量で実現することができる。
【００８９】
一方で、このような逐次的なアルゴリズムは、並列処理が困難である。
【００９０】
上述したように、関連技術の量子化装置１０００、２００、３００の問題点は、RDOQ処理において、最終係数位置の最適化を並列処理できない点である。関連技術の最終係数位置最適化部１４００、最終係数位置決定部２３０、最終係数位置判定部３６０では、逆スキャン順に最終係数位置候補を更新し、RDコストを順次計算する必要がある。このため、GPUのような高並列なアーキテクチャでは、変換係数の量子化を効率的に処理できない。
【００９１】
以下、本発明を実施する形態について図面を参照して詳細に説明する。以下の各実施形態に記載されている構成は単なる例示であり、本発明の技術的範囲はそれらには限定されない。
【００９２】
[第1の実施形態] 
[構成の説明]
図８は、本発明の第１の実施形態による量子化装置１０００Ａの構成例を示すブロック図である。量子化装置１０００Ａは、画像を量子化する量子化処理を行う装置である。
【００９３】
図示の量子化装置１０００Ａは、最終係数位置最適化部１４００の代わりに最終係数位置最適化部１５００を用いた点を除いて、図１に示された量子化装置１０００と同様の構成を有する。
【００９４】
図９は、図８に示された最終係数位置最適化部１５００の構成例を示すブロック図である。最終係数位置最適化部１５００は、後述するように、圧縮による画質の劣化と圧縮率とを加味したコストを最小化する出力データ長の候補を求めることで、出力する最適なデータ長を決める処理部として動作する。なお、上記コストを計算する処理は複数のデータ長候補で部分的に共通な処理である。
【００９５】
図９に示すように、本第１の実施形態の最終係数位置最適化部１５００は、係数コスト計算部１５１０と、最終係数コスト計算部１５２０と、最終係数コスト判定部１５３０とから成る。
【００９６】
本第１の実施形態の最終係数位置最適化部１５００は、量子化後変換係数を入力として、レート歪み最適量子化処理された変換係数（以下、「最適化後変換係数」と表記する）を出力する。
【００９７】
また、本第１の実施形態の最終係数位置最適化部１５００は、関連技術の最終係数位置最適化部１４００（図６）と異なり、各係数単位で並列処理可能な点が異なる。ここで、「係数単位での並列処理」とは、各処理部にはＮ（Ｎは２以上の整数）個の付随する処理部が備わっており、Ｎが最大で変換ブロック内係数の総数となることを表す。すなわち、変換ブロック内の各係数が、各処理部１〜Ｎで並列に処理される。また、ここでは並列数が最大となる例を示すが、並列数を下げて複数の係数をまとめて一つの処理部で処理しても良い。
【００９８】
係数コスト計算部１５１０は、第１乃至第Ｎの係数コスト計算部分１５１１、１５１２、・・・、１５１Ｎから成る。係数コスト計算部１５１０は、Ｎ個の量子化後変換係数を入力として、各係数を符号化した場合のRDコストＪｉ，ｃｏｄｅと、符号化しない場合のRDコストＪｉ，ｃｕｔとを計算し、出力する。ここで、レート計算では、近似によって係数間の依存関係はないものとする。例えば、特許文献１または特許文献２に記載の、bin数を用いて簡略したものがありうる。
【００９９】
また、係数コスト計算部１５１０は、係数コスト計算部１４１０（図６参照）と同様に、量子化丸め誤差最適化部１２００（図８参照）でＪｉ，ｃｏｄｅとＪｉ，ｃｕｔとを算出した場合には、省略可能である。
【０１００】
最終係数コスト計算部１５２０は、第１乃至第Ｎの最終係数コスト計算部分１５２１、１５２２、・・・、１５２Ｎから成る。最終係数コスト計算部１５２０は、係数コスト計算部１５１０で求めた各係数を符号化した場合のRDコストＪｉ，ｃｏｄｅと、符号化しない場合のRDコストＪｉ，ｃｕｔとを入力して、各係数を最終係数位置としたときのRDコストを並列に計算し、出力する。
【０１０１】
すなわち、係数コスト計算部１５１０と最終係数コスト計算部１５２０との組み合わせは、複数のデータ長候補のコストを共通の計算は分散しつつ並列に計算するコスト計算部として働く。
【０１０２】
最終係数コスト判定部１５３０は、第１乃至第Ｎの最終係数コスト判定部分１５３１、１５３２、・・・、１５３Ｎから成る。最終係数コスト判定部１５３０は、最終係数コスト計算部１５２０で求めた各係数を最終係数位置としたときのRDコストを入力して、その最小値、すなわち最適な最終係数位置を並列に判定する。また、最終係数コスト判定部１５３０は、最終係数位置がスキャン順で担当する係数よりも手前だった場合には、担当する係数をゼロにし、最終係数位置に関して最適化された量子化後変換係数を出力する。
【０１０３】
すなわち、最終係数コスト判定部１５３０は、複数のデータ長候補の中でコストが最小となる１つのデータ長候補を並列に判定して、最適なデータ長を求める判定部として働く。
【０１０４】
したがって、最終係数位置最適化部１５００は、複数のデータ長候補に関して並列に動作する。
【０１０５】
[動作の説明]
次に、図１０のフローチャートと図１１の説明図とを参照して、本第１の実施形態の最終係数位置最適化部１５００の動作について詳細に説明する。
【０１０６】
まず、係数コスト計算部１５１０は、各係数を符号化した際のRDコストＪｉ，ｃｏｄｅと、符号化しない際のRDコストＪｉ，ｃｕｔとを計算する（ステップＳ２０１、図１１の説明図では(a)に相当）。
【０１０７】
尚、Ｊｉ，ｃｏｄｅとＪｉ，ｃｕｔとは、係数間での依存関係がないように、例えばbin数を近似したものであるとする。近似を用いない場合、係数間で依存関係があるシンタックスの符号化に係るレートを別途計算し、足し合わせる必要がある。近似方法としては、例えば特許文献１や特許文献2に記載の技術がありうる。近似によって、係数ごとの並列処理が実現できる。
【０１０８】
次いで、最終係数コスト計算部１５２０は、各最終係数位置候補のコストを計算する。
具体的には、まず、最終係数コスト計算部１５２０は、係数コスト計算部１５１０で求めた、Ｊｉ，ｃｕｔとＪｉ，ｃｏｄｅとを、それぞれ、順方向exclusiveスキャンおよび、逆方向inclusiveスキャンする（ステップＳ２０２、図１１の説明図では(b)に相当）。
【０１０９】
ここで、スキャンとは、部分和を求める処理であり、効率的な並列処理方法が知られている。スキャンの並列処理方法としては、例えば、非特許文献２に記載のParallel Scanがありうる。Parallel Scanでは、図１２に示すように、各データを隣接するデータに対し並列に足し合わせる。そして、Parallel Scanでは、足し合わされたデータを、次のステップで、さらに隣のデータに足し合わせる。これにより、部分和の並列計算における冗長な演算を削減し、並列計算に係るステップ数を削減できる。
【０１１０】
ここで、順方向スキャンとは、スキャン順に従った部分和計算を示し、逆方向スキャンは、スキャン順とは逆順の部分和を示す。
【０１１１】
また、要素xに関するinclusiveスキャンｘｉ，ｉｎｃｌｕｓｉｖｅは、次式(5)で表される。
【０１１２】
【数５】
2018135520.tif 000007
【０１１３】
要素xに関するexclusiveスキャンｘｉ，ｅｘｃｌｕｓｉｖｅは、次式(6)で表される。
【０１１４】
【数６】
2018135520.tif 000008
【０１１５】
次いで、最終係数コスト計算部１５２０は、ステップＳ２０２で求めた、Ｊｉ，ｃｕｔの順方向部分和と、Ｊｉ，ｃｏｄｅの逆方向部分和とを足し合わせる（ステップＳ２０３、図１１の説明図では(c)に相当）。ここで、図１１の(c)に注目すると、足し合わされた結果が式(3)と等しいことがわかる。このように順方向スキャンと逆方向スキャンとを用いることで、並列にそれぞれの最終係数位置候補のRDコストを求めることができる。
【０１１６】
このように、最終係数コスト計算部１５２０は、各データを量子化しない際のコストの量子化順方向部分和と、各データを量子化する際のコストの量子化逆方向部分和とを求め、量子化順方向部分和と量子化逆方向部分和とを足し合わせることで、複数の最終係数位置候補に関する並列処理を、各最終係数位置候補間で共通な処理を分散しつつ実現している。
【０１１７】
最後に、最終係数コスト判定部１５３０は、最適な最終係数位置を求める。
【０１１８】
具体的には、最終係数コスト判定部１５３０において、まず最終係数コスト計算部１５２０で求めた各最終係数位置候補のRDコストのうち最小値を求める（ステップＳ２０４、図１１の説明図では(d)に相当）。RDコストが最小値となる最終係数位置候補が、最適な最終係数位置となる。
【０１１９】
ここで、最小値計算も同様に、並列処理方法が知られている。例えば、非特許文献３に記載のParallel Reduction処理が有りうる。Parallel Scanと同様に、Parallel Reductionでも隣接するデータを交換し合うことで、並列処理に係るステップ数を削減することが可能である。
【０１２０】
次いで、最終係数コスト判定部１５３０は、求まった最適な最終係数位置に対し、各係数位置がスキャン順で前である場合にはステップＳ２０６に進み、スキャン順で後ろである場合にはステップＳ２０７に進む（ステップＳ２０５）。
【０１２１】
係数位置がスキャン順で最終係数位置よりも前である場合、最終係数コスト判定部１５３０は、係数値を0にする（ステップＳ２０６）。
【０１２２】
係数位置がスキャン順で最終係数位置よりも後ろである場合、最終係数コスト判定部１５３０は、係数値をそのまま出力する（ステップＳ２０７）。
【０１２３】
このように、最終係数コスト判定部１５３０は、各データ長候補のコストを階層的かつ並列に比較することによって、コストが最小値となるデータ長候補を並列に判定している。
【０１２４】
[効果の説明] 
次に、本第１の実施形態の効果について説明する。
【０１２５】
本第１の実施形態の最終係数位置最適化部１５００は、処理に係るステップ数をO(N)ステップからO(logN)ステップに削減でき、最終計数位置の最適化処理を高速化できる。その理由は、順方向スキャン、逆方向スキャン、最小値のReductionといった効率的な並列処理を実現可能な方法を用いることで、各係数に関して効率的に並列処理できるように構成されているからである。
【０１２６】
[第２の実施形態] 
[構成の説明]
図１３は、本発明の第２の実施形態による量子化装置１０００Ｂの構成例を示すブロック図である。
【０１２７】
図示の量子化装置１０００Ｂは、最終係数位置最適化部１４００の代わりに最終係数位置最適化部１６００を用いた点を除いて、図１に示された量子化装置１０００と同様の構成を有する。
【０１２８】
図１４は、図１３に示された最終係数位置最適化部１６００の構成例を示すブロック図である。
【０１２９】
図１４に示すように、本第２の実施形態の最終係数位置最適化部１６００は、レート計算部１６１０と、係数コスト計算部１６２０と、最終係数コスト計算部１６３０と、最終係数コスト判定部１６４０とから成る。
【０１３０】
本第２の実施形態の最終係数位置最適化部１６００は、上記第１の実施形態の最終係数位置最適化部１５００とは、レート計算部１６１０が含まれる点が異なる。
【０１３１】
レート計算部１６１０は、第１乃至第Ｎのレート計算部分１６１１、１６１２、・・・、１６１Ｎから成る。
【０１３２】
レート計算部１６１０は、各最終係数位置候補のRDコストに必要なレートの計算において、係数間の依存関係を考慮しつつ、より正確なレートを並列に計算する機能を有する。
また、レート計算部１６１０で求めた、各最終係数位置候補のレートは、最終係数コスト計算部１６３０に入力される。ここで、第１の実施形態よりレートが正確であるとは、最終係数位置最適化部１５００のレート計算では係数間の依存関係をなくすために、近似を用いていたことによる。
【０１３３】
また、本第２の実施形態の最終係数位置最適化部１６００は、上記第１の実施形態の最終係数位置最適化部１５００とは、最終係数コスト計算部１６３０において、レート計算部１６１０で求めたより正確なレートを、各最終係数位置候補のRDコストに足し合わせる機能を有する点が異なる。
【０１３４】
その他の最終係数位置最適化部１６００の構成は、第１の実施形態の最終係数位置最適化部１５００と同様である。
【０１３５】
すなわち、係数コスト計算部１６２０は、第１乃至第Ｎの係数コスト計算部分１６２１、１６２２、・・・、１６２Ｎから成る。最終係数コスト計算部１６３０は、第１乃至第Ｎの最終係数コスト計算部分１６３１、１６３２、・・・、１６３Ｎから成る。
【０１３６】
したがって、レート計算部１６１０と係数コスト計算部１６２０と最終係数コスト計算部１６３０との組み合わせは、複数のデータ長候補のコストを共通の計算は分散しつつ並列に計算するコスト計算部として働く。
【０１３７】
最終係数コスト判定部１６４０は、第１乃至第Ｎの最終係数コスト判定部分１６４１、１６４２、・・・、１６４Ｎから成る。
【０１３８】
最終係数コスト判定部１６４０は、複数のデータ長候補の中でコストが最小となる１つのデータ長候補を並列に判定して、最適なデータ長を求める判定部として働く。
【０１３９】
したがって、最終係数位置最適化部１６００は、複数のデータ長候補に関して並列に動作する。
【０１４０】
[動作の説明] 
以下では、本第２の実施形態の最終係数位置最適化部１６００の動作について説明する。
【０１４１】
図１５は、第２の実施形態の最終係数位置最適化部１６００の動作を示すフローチャートである。
【０１４２】
図１５において、ステップＳ３０１とステップＳ３０４以外のステップＳ３０２、Ｓ３０３、Ｓ３０５〜Ｓ３０８の処理は、それぞれ、図１０に示すステップＳ２０１、Ｓ２０２、Ｓ２０４〜Ｓ２０７の処理と同様である。
【０１４３】
説明を簡略化する（重複した説明を避ける）ために、以下では図９からの相違点についてのみ説明する。
【０１４４】
レート計算部１６１０は、係数間の依存関係を考慮して、各最終係数位置候補のレートを並列に計算する（ステップＳ３０１）。
【０１４５】
ここで、レートとしては、例えば第１の実施形態と同様に、CABACに入力される前のbit数を表すbin数がありうる。一方で、第１の実施形態と異なり、第２の実施形態では、係数間で依存のあるシンタックスのbin数計算において、近似を行わない点が異なる。bin数計算の並列処理方法に関しては、後述する。
【０１４６】
最終係数コスト計算部１６３０は、係数コスト計算部１６２０で求めた各係数を符号化するRDコストと、符号化しないRDコストと、レート計算部１６１０で求めた最終係数位置候補のレートとを足し合わせる（ステップＳ３０４）。
【０１４７】
以下では、図１６を参照して、HEVCの変換係数符号化に関するシンタックスの１つであるcoeff_abs_level_greater1_flagを例に、レート計算の並列処理方法を説明する。
【０１４８】
coeff_abs_level_greater1_flagは係数グループごとに必要となるシンタックスである。また、coeff_abs_level_greater1_flagは、係数グループ内の係数に関して、係数の絶対値が１より大きい場合は”１”、小さい場合は”０”となる。加えて、coeff_abs_level_greater1_flagはスキャン順に非ゼロな係数を最大８個分格納できる。したがって、最終係数位置によってcoeff_abs_level_greater1_flagを格納できる係数が異なるため、並列処理が困難である。
【０１４９】
本実施形態のレート計算部１６１０では、例えばこのようなcoeff_abs_level_greater1_flagに対し、以下のように並列処理する。
【０１５０】
まず、入力された係数に対し、その絶対値が１より大きければフラグを立てる（図１６中(a)に相当）。
【０１５１】
次いで、絶対値が１より大きいフラグに関してスキャン順（符号化順）に対して逆方向inclusiveスキャンを実施する（図１６中(b)に相当）。
【０１５２】
最後に、各逆方向部分和に対して、その値と８とで小さいほうの値で更新する（図１６中(c)に相当）。
【０１５３】
このように絶対値が１より大きいことを示すフラグに対し、逆方向スキャンを実施することで、各最終位置候補のcoeff_abs_level_greater1_flagの符号化に係るbin数を並列計算できる。
【０１５４】
尚、ここではcoeff_abs_level_greater1_flagのみに関して説明したが、その他のシンタックスのbin数に関しても同様の方法で並列処理可能である。
【０１５５】
このように、レート計算部１６１０は、圧縮率コスト計算において各データ長候補における特定の条件を満たす係数の情報が必要な処理であって、上記特定の条件を満たす係数が存在することを示すフラグを求める。コスト計算部（１６２０，１６３０）は、上記フラグに対して並列処理する。
【０１５６】
換言すれば、レート計算部１６１０は、上記フラグに対して部分和を計算するが、これは、圧縮率コスト計算において各データ長候補における特定の条件を満たす係数の数が必要な処理である。このように、上記フラグに対して部分和を計算することで、コスト計算部（１６２０，１６３０）は並列処理を実現している。
【０１５７】
[効果の説明] 
本第２の実施形態の最終係数位置最適化部１６００は、並列処理効率を落とすことなく、より正確なレートを計算でき、より高い画質または圧縮率を実現できる。その理由は、Parallel Scanのような並列処理方法を用いることで、レート計算において係数間の依存関係を保持しつつ、各最終係数位置候補に関して並列処理できるように構成しているからである。
【実施例】
【０１５８】
次に、具体的な実施例を用いて、本発明を実施するための形態の動作を説明する。【０１５９】
図１７に示す情報処理装置は、制御装置１０、並列処理装置２０、画像データを格納するための記憶媒体３０、およびプログラムメモリ４０を備える。【０１６０】
並列処理装置２０は、複数個のプロセシングユニット（ＰＵ）２１から成る。図示の例では、並列処理装置２０は、１６個のプロセッシングユニット２１から成る。しかしながら、プロセッシングユニット２１の個数は、これに限定されないのは勿論である。【０１６１】
図１７に示された情報処理装置において、プログラムメモリ４０には図８や図１３に示された各ブロックの機能を実現するためのプログラムが格納される。そして、並列処理装置２０は制御装置１０によって実行指示され、プログラムメモリ４０に格納されているプログラムにしたがって、各プロセッシングユニット２１で処理を並列実行することで、図８や図１３に示された量子化装置１０００Ａ、１０００Ｂの機能を実現する。【０１６２】
ここで、制御装置１０は、例えば、ＣＰＵ（Central Processing Unit）であってよく、並列処理装置２０としてはＧＰＵ（Graphic Processing Unit）を用いることができるが、これらに限定されないのは勿論である。【０１６３】
次に、図１７に示された情報処理装置が「処理を並列に実行する」ことに関して、図９に示した第１の実施形態の最終係数位置最適化部１５００が実行する場合を例に挙げて説明する。【０１６４】
まず、制御装置１０が、並列処理装置２０の動作を制御することにより、係数コスト計算部１５１０が実行する第１の工程を実現する。この第１の工程の実行に際して、制御装置１０は、１つ以上のＰＵ２１を用いて、第ｎの係数コスト計算部分１５１ｎで実施される処理を実行する。ここで、１≦ｎ≦Ｎである。並列処理装置２０の複数のＰＵ２１を用いてこの動作を実行することにより、第１乃至第Ｎの係数コスト計算部分１５１１〜１５１Ｎの各ブロックの並列動作が実現され得る。【０１６５】
係数コスト計算部１５１０の実行（第１の工程）が完了したら、制御装置１０は、次の第２の工程では、最終係数コスト計算部１５２０の動作を、並列処理装置２０を同様に制御することにより実現する。すなわち、この第２の工程の実行に際して、制御装置１０は、１つ以上のＰＵ２１を用いて、第ｎの最終係数コスト計算部分１５２ｎで実施させる処理を実行させる。並列処理装置２０の複数のＰＵ２１を用いてこの動作を実行することにより、第１乃至第Ｎの最終係数コスト計算部分１５２１〜１５２Ｎの各ブロックの並列動作が実現され得る。【０１６６】
最終係数コスト計算部１５２０の実行（第２の工程）が完了したら、制御装置１０は、次の第３の工程では、最終係数コスト判定部１５３０を、並列処理装置２０を同様に制御することより実現する。すなわち、この第３の工程の実行に際して、制御装置１０は、１つ以上のＰＵ２１を用いて、第ｎの最終係数コスト判定部分１５３ｎで実施される処理を実行させる。並列処理装置２０の複数のＰＵ２１を用いてこの動作を実行することにより、第１乃至第Ｎの最終係数コスト判定部分１５３１〜１５３Ｎの各ブロックの並列動作が実現され得る。【０１６７】
また、上記では第１、第２、第３の各工程において、制御装置１０が並列処理装置２０を制御する例を示したが、その限りではなく、制御装置１０が事前に全工程をまとめて並列処理装置２０に指示しても良い。【０１６８】
このときのＰＵ２１への処理の配置や、ＰＵ２１間の通信などは、本実施例において、一般的な技術を用いることができる。なお、ＰＵ２１間の通信とは、例えば、上流の計算部（上流の計算を実行するＰＵ）から工程を跨いで次工程の複数の計算部（次工程の計算を実行する複数のＰＵ）への通信を指す。【０１６９】
尚、上記実施形態では、最終係数位置最適化部１５００、１６００を、非特許文献１の最終係数位置最適化部１４００と対応させて説明したが、本発明はこの限りではない。例えば、本発明の最終係数位置最適化部は、特許文献１の最終係数位置決定部２３０や、特許文献２の最終係数位置判定部３６０とも対応可能である。【０１７０】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、複数の構成要素の適宜な組合せにより種々の発明を形成できる。【０１７１】
尚、データ処理装置の各部は、ハードウェアとソフトウェアとの組み合わせを用いて実現すればよい。ハードウェアとソフトウェアとを組み合わせた形態では、ＲＡＭ（random access memory）に量子化プログラムが展開され、該量子化プログラムに基づいて、ＣＰＵ（central processing unit）等の制御装置１０が、演算処理部（ＧＰＵ（Graphic Processing Unit））等の並列処理装置２０のハードウェアを動作させることによって、各部を各種手段として実現する。また、該量子化プログラムは、記録媒体に記録されて頒布されても良い。当該記録媒体に記録された量子化プログラムは、有線、無線、又は記録媒体そのものを介して、メモリに読込まれ、制御部（制御装置１０、並列処理装置２０）等を動作させる。尚、記録媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリ装置、ハードディスクなどが挙げられる。【０１７２】
上記実施形態を別の表現で説明すれば、データ処理装置として動作させるコンピュータを、ＲＡＭに展開された量子化プログラムに基づき、係数コスト計算部１５１０、最終係数コスト計算部１５２０、および最終係数コスト判定部１５３０の組み合わせとして動作させることで、或いは、レート計算部１６１０、係数コスト計算部１６２０、最終係数コスト計算部１６３０、および最終係数コスト判定部１６４０の組み合わせとして動作させることで、実現することが可能である。【０１７３】
また、本発明の具体的な構成は前述の実施の形態に限られるものではなく、この発明の要旨を逸脱しない範囲の変更があってもこの発明に含まれる。【０１７４】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１７５】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。【０１７６】
（付記１）
画像に対する量子化処理を行う量子化装置であって、
複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味したコストを計算する処理手段を含み、
前記コストを計算する処理は、前記複数のデータ長の間で、部分的に共通な処理であって、
前記処理手段は、
前記複数のデータ長に関して並列に動作し、
前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行するコスト計算手段と、
前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として求める判定手段とを有することを特徴とする量子化装置。【０１７７】
（付記２）
前記コスト計算手段は、
各データを量子化しない際のコストの量子化順方向部分和と、各データを量子化する際のコストの量子化逆方向部分和とを求め、前記量子化順方向部分和と前記量子化逆方向部分和とを足し合わせることで、前記複数のデータ長についての前記コストを並列に計算する付記１に記載の量子化装置。【０１７８】
（付記３）
前記判定手段は、
前記複数のデータ長についての前記コストを階層的かつ並列に比較することによって、前記コストが最小値となるデータ長を判定することを特徴とする付記１又は２に記載の量子化装置。【０１７９】
（付記４）
前記複数のデータ長について、特定の条件を満たす画素が存在することを示すフラグをそれぞれ求め、前記フラグに対して並列処理を実行することによって、前記コストを計算するために必要な、前記画像の圧縮率を計算するレート計算手段をさらに含むことを特徴とする付記１から３のいずれか１つに記載の量子化装置。【０１８０】
（付記５）
前記レート計算手段は、前記フラグの部分和を並列に計算することを特徴とする付記４に記載の量子化装置。【０１８１】
（付記６）
前記量子化処理は、動画像符号化におけるRDOQ（Rate Distortion Optimized Quantization）処理であって、
前記コスト計算手段は、各データ長のコストとして、入力された係数のうち最後に符号化される最終係数位置のコストを計算し、
前記判定手段は、計算された複数の最終係数位置の中から、コストが最小となる最終係数位置を、前記最適なデータ長として決定し、
前記処理手段は、前記複数の最終係数位置に関して並列動作することを特徴とする付記１から５のいずれか１つに記載の量子化装置。【０１８２】
（付記７）
画像に対する量子化処理を量子化装置で実施する量子化方法であって、
複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味した量子化のコストを計算し、
前記コスト計算は、前記複数のデータ長の間で、部分的に共通な処理を含み、
前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行し、
前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として出力する、
量子化方法。【０１８３】
（付記８）
各データを量子化しない際のコストの量子化順方向部分和と、各データを量子化する際のコストの量子化逆方向部分和とを求め、前記量子化順方向部分和と前記量子化逆方向部分和とを足し合わせることで、前記複数のデータ長についての前記コストを並列に計算する、付記７に記載の量子化方法。【０１８４】
（付記９）
前記複数のデータ長のコストを階層的かつ並列に比較することによって、コストが最小値となるデータ長を並列に判定する、付記７又は８に記載の量子化方法。【０１８５】
（付記１０）
前記複数のデータ長の各々について、特定の条件を満たす画素が存在することを示すフラグを求め、前記フラグに対して並列処理を実行することによって、前記画像の圧縮率を計算することを特徴とする付記７から８のいずれか１つに記載の量子化方法。【０１８６】
（付記１１）
前記フラグの部分和を並列に計算することを特徴とする付記１０に記載の量子化方法。【０１８７】
（付記１２）
前記量子化処理は、動画像符号化におけるRDOQ（Rate Distortion Optimized Quantization）処理であって、
入力された係数のうち最後に符号化される最終係数位置のコストを並列に計算し、
前記複数の最終係数位置の中から、前記コストが最小となる最終係数位置を、前記最適なデータ長として決定することを特徴とする付記７から１１のいずれか１つに記載の量子化方法。【０１８８】
（付記１３）
コンピュータに、画像に対する量子化処理を行わせる量子化プログラムであって、前記量子化プログラムは、前記コンピュータに、
複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味したコストを計算する処理を実行させるものであり、
前記コストを計算する処理は、前記複数のデータ長の間で、部分的に共通な処理を含み、
前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行するコスト計算処理と、
前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として求める判定処理と、
を実行させる量子化プログラムを記録した、一時的でない記録媒体。【０１８９】
以上、上述した実施形態を模範的な例として本発明を説明した。しかしながら、本発明は、上述した実施形態には限定されない。即ち、本発明は、本発明のスコープ内において、当業者が理解し得る様々な態様を適用することができる。
この出願は、２０１７年１月２０日に出願された日本出願特願２０１７−００８３０３を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１９０】
１０    制御装置
２０    並列処理装置
２１    プロセッシングユニット（ＰＵ）
３０    記憶媒体
４０    プログラムメモリ
２００    量子化装置
２１０    スケーリング部
２１１    第１のスケーリング部分
２１２    第２のスケーリング部分
２１Ｎ    第Ｎのスケーリング部分
２２０    係数絶対値決定部
２２１    第１の係数絶対値決定部分
２２２    第２の係数絶対値決定部分
２２Ｎ    第Ｎの係数絶対値決定部分
２３０    最終係数位置決定部
３００    量子化装置
３１０    制御部
３２０    スケーリング部
３３０    係数最適化部
３４０    記憶部
３５０    係数グループ最適化部
３６０    最終係数位置判定部
３７０    補正値算出部
３８０    判定部
１０００、１０００Ａ、１０００Ｂ    量子化装置
１１００    量子化部
１２００    量子化丸め誤差最適化部
１３００    係数グループ最適化部
１４００    最終係数位置最適化部
１４１０    係数コスト計算部
１４２０    最終係数コスト計算部
１４３０    最終係数コスト判定部
１５００    最終係数位置最適化部
１５１０    係数コスト計算部
１５１１    第１の係数コスト計算部分
１５１２    第２の係数コスト計算部分
１５１Ｎ    第Ｎの係数コスト計算部分
１５２０    最終係数コスト計算部
１５２１    第１の最終係数コスト計算部分
１５２２    第２の最終係数コスト計算部分
１５２Ｎ    第Ｎの最終係数コスト計算部分
１５３０    最終係数コスト判定部
１５３１    第１の最終係数コスト判定部分
１５３２    第２の最終係数コスト判定部分
１５３Ｎ    第Ｎの最終係数コスト判定部分
１６００    最終係数位置最適化部
１６１０    レート計算部
１６１１    第１のレート計算部分
１６１２    第２のレート計算部分
１６１Ｎ    第Ｎのレート計算部分
１６２０    係数コスト計算部
１６２１    第１の係数コスト計算部分
１６２２    第２の係数コスト計算部分
１６２Ｎ    第Ｎの係数コスト計算部分
１６３０    最終係数コスト計算部
１６３１    第１の最終係数コスト計算部分
１６３２    第２の最終係数コスト計算部分
１６３Ｎ    第Ｎの最終係数コスト計算部分
１６４０    最終係数コスト判定部
１６４１    第１の最終係数コスト判定部分
１６４２    第２の最終係数コスト判定部分
１６４Ｎ    第Ｎの最終係数コスト判定部分
【図１】
2018135520.tif 000009
【図２】
2018135520.tif 000010
【図３】
2018135520.tif 000011
【図４】
2018135520.tif 000012
【図５】
2018135520.tif 000013
【図６】
2018135520.tif 000014
【図７】
2018135520.tif 000015
【図８】
2018135520.tif 000016
【図９】
2018135520.tif 000017
【図１０】
2018135520.tif 000018
【図１１】
2018135520.tif 000019
【図１２】
2018135520.tif 000020
【図１３】
2018135520.tif 000021
【図１４】
2018135520.tif 000022
【図１５】
2018135520.tif 000023
【図１６】
2018135520.tif 000024
【図１７】
2018135520.tif 000025
【手続補正書】
【提出日】令和1年6月21日(2019.6.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画像に対する量子化処理を行う量子化装置であって、
複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味したコストを計算する処理手段を含み、
前記コストを計算する処理は、前記複数のデータ長の間で、部分的に共通な処理であって、
前記処理手段は、
前記複数のデータ長に関して並列に動作し、
前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行するコスト計算手段と、
前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として求める判定手段とを有する
ことを特徴とする量子化装置。
【請求項２】
前記コスト計算手段は、
各データを量子化しない際のコストの量子化順方向部分和と、各データを量子化する際のコストの量子化逆方向部分和とを求め、前記量子化順方向部分和と前記量子化逆方向部分和とを足し合わせることで、前記複数のデータ長についての前記コストを並列に計算する請求項１に記載の量子化装置。
【請求項３】
前記判定手段は、
前記複数のデータ長についての前記コストを階層的かつ並列に比較することによって、前記コストが最小値となるデータ長を判定することを特徴とする請求項１又は２に記載の量子化装置。
【請求項４】
前記複数のデータ長について、特定の条件を満たす画素が存在することを示すフラグをそれぞれ求め、前記フラグに対して並列処理を実行することによって、前記コストを計算するために必要な、前記画像の圧縮率を計算するレート計算手段をさらに含むことを特徴とする請求項１から３のいずれか１つに記載の量子化装置。
【請求項５】
前記レート計算手段は、前記フラグの部分和を並列に計算することを特徴とする請求項４に記載の量子化装置。
【請求項６】
前記量子化処理は、動画像符号化におけるRDOQ（Rate DistortionOptimized Quantization）処理であって、
前記コスト計算手段は、各データ長のコストとして、入力された係数のうち最後に符号化される最終係数位置のコストを計算し、
前記判定手段は、計算された複数の最終係数位置の中から、コストが最小となる最終係数位置を、前記最適なデータ長として決定し、
前記処理手段は、前記複数の最終係数位置に関して並列動作することを特徴とする請求項１から５のいずれか１つに記載の量子化装置。
【請求項７】
画像に対する量子化処理を量子化装置で実施する量子化方法であって、
複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味した量子化のコストを計算し、
前記コスト計算は、前記複数のデータ長の間で、部分的に共通な処理を含み、
前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行し、
前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として出力する、
量子化方法。
【請求項８】
各データを量子化しない際のコストの量子化順方向部分和と、各データを量子化する際のコストの量子化逆方向部分和とを求め、前記量子化順方向部分和と前記量子化逆方向部分和とを足し合わせることで、前記複数のデータ長についての前記コストを並列に計算する、請求項７に記載の量子化方法。
【請求項９】
前記複数のデータ長のコストを階層的かつ並列に比較することによって、コストが最小値となるデータ長を並列に判定する、請求項７又は８に記載の量子化方法。
【請求項１０】
コンピュータに、画像に対する量子化処理を行わせる量子化プログラムであって、前記量子化プログラムは、前記コンピュータに、
複数のデータ長について、前記画像の圧縮による画質の劣化と圧縮率とを加味したコストを計算する処理を実行させるものであり、
前記コストを計算する処理は、前記複数のデータ長の間で、部分的に共通な処理を含み、
前記複数のデータ長の間で共通な処理を、分散しつつ並列に実行するコスト計算処理と、
前記複数のデータ長の中で、前記コストが最小となる１つのデータ長を、最適なデータ長として求める判定処理と、
を実行させる量子化プログラム。
【国際調査報告】
2018135520.tif 000026
2018135520.tif 000027
2018135520.tif 000028
2018135520.tif 000029