(57)【特許請求の範囲】
【請求項１】
フィードバックが発生する処理とフィードバックが発生しない処理のうちいずれかを入力データから選択して当該入力データに対して処理を行う情報処理装置において、前記フィードバックが発生する処理をフィードバックが発生したときに取り得る値のすべてについて前記入力データに対して並列にパイプライン処理する演算手段と、前記入力データにより前記フィードバックが発生する処理と前記フィードバックが発生しない処理のうちいずれかを選択する判断手段と、該判断手段による処理の選択結果により一方の処理を打ち切る打ち切り手段を有することを特徴とする情報処理装置。
【請求項２】
前記演算手段は、前記判断手段による処理の選択と並行してパイプライン処理を開始することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記判断手段は、処理済のデータを含む１つ以上のデータと前記入力データとを比較することにより処理を選択することを特徴とする請求項１または請求項２に記載の情報処理装置。
【請求項４】
前記判断手段は、前記入力データと処理済のデータとの演算の結果により処理を選択することを特徴とする請求項１または請求項２に記載の情報処理装置。
【請求項５】
前記打ち切り手段は、前記判断手段により前記フィードバックが発生しない処理が選択されたときに当該入力データに対する前記演算手段によるパイプライン処理を打ち切ることを特徴とする請求項１ないし請求項４のいずれか１項に記載の情報処理装置。
【請求項６】
さらに、前記判断手段の結果により前記入力データを入力するタイミングを制御する入力制御手段を有し、該入力制御手段は、前記判断手段により前記フィードバックが発生する処理が選択された場合には、前記入力データを入力する間隔を長くするように制御することを特徴とする請求項１ないし請求項５のいずれか１項に記載の情報処理装置。
【請求項７】
前記入力データは画像データであり、前記フィードバックが発生する処理は誤差拡散法を用いた画素値変更処理であることを特徴とする請求項１ないし請求項６のいずれか１項に記載の情報処理装置。
【請求項８】
前記入力データは画像データであり、前記フィードバックが発生する処理は平均誤差法を用いた画素値変更処理であることを特徴とする請求項１ないし請求項６のいずれか１項に記載の情報処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、フィードバックが発生する処理と発生しない処理のうちいずれかを入力データから選択して実行する情報処理装置に関するものである。
【０００２】
【従来の技術】
入力データをもとに判断して、フィードバックが発生する処理と発生しない処理のいずれかに分岐するような処理を高速に実行したい場合がある。図６は、フィードバックが発生する処理と発生しない処理を切り替えて実行する処理の一例を示すフローチャートである。図６では、１つの入力データに対する処理を示している。Ｓ３１において、入力データをもとにフィードバックが発生するか否かを判断し、フィードバックが発生しない場合には、この例ではＳ３６においてそのまま出力されて、当該入力データに対する処理を終了する。
【０００３】
Ｓ３１でフィードバックが発生すると判断された場合は、Ｓ３２〜Ｓ３５における処理Ａ〜処理Ｄによって構成されるフィードバックループを実行する。この実行結果は、Ｓ３６において出力されるとともに、次の入力データの判断処理を行うためにフィードバックされる。
【０００４】
この例では、次の入力データに対して直前の入力データに対応する処理結果が適用され、Ｓ３１における判断が行われる。従って、直前の入力データについてフィードバックが発生すると判断された場合には、当該直前の入力データに対する処理Ｄ間での処理が終了しないと、次の入力データについての判断を行うことができない。そのため、このような処理をハードウェアで扱う場合、通常は逐次処理が用いられる。
【０００５】
図７は、図６に示す処理を逐次処理で行う場合の概念図、図８は、同じくタイミングチャートである。図６に示したフローチャートの処理を逐次処理する場合、図７に示すように、まず判断処理を行って、フィードバックが発生すると判断された場合、処理Ａ、処理Ｂ、処理Ｃ、処理Ｄと順に処理を行って出力する。また、次の入力データに対する判断を行う際に、処理Ｄの結果を考慮して判断を行う。逆にフィードバックが発生しないと判断された場合、判断処理が終了すると、判断時のデータをそのまま出力とし、その結果は次のデータに対する判断には利用しない。
【０００６】
この処理をタイミングチャートで示すと、図８に示すようになる。図８では、図６のフィードバックループ内の処理（Ｓ３２〜Ｓ３５における処理Ａ〜処理Ｄ）がそれぞれ１サイクルで終了するものとして描かれている。図８の入力データのうち、ハッチングが施されている入力データについてはフィードバックが発生せず、ハッチングが施されていない入力データについてはフィードバックが発生するものとして示している。
【０００７】
フィードバックが発生しない場合は、出力を次の入力データの判断処理で必要としないため、データ出力と次のデータの入力を同時に行うことができる。一方、フィードバックが発生する場合は、出力を次の入力データの判断処理で必要とするため、データ出力の次のサイクルでデータを入力することになる。また、入力データを出力するまでに４サイクル必要とする。従って、フィードバックが発生する場合には、５サイクル間隔でデータの入力を行うことになる。
【０００８】
よって、逐次処理では、フィードバックが発生しないデータが入力された場合は１サイクル１出力で処理ができるのに対し、フィードバックが発生するデータでは１出力に対し５サイクル必要になる。つまり、逐次処理ではフィードバックが発生するデータが多い場合にスループットが著しく低下するという問題があることがわかる。
【０００９】
上述のように、逐次処理ではフィードバックが発生するデータが多い場合にスループットが低下するという問題に対し、例えば特開２０００−１５２００５号公報に記載されているような処理方法を応用することによって、フィードバック発生時のスループットを向上させることが可能となる。この特開２０００−１５２００５号公報に記載されている処理方法では、常にフィードバックが発生する誤差拡散を用いた２値化処理において、出力データが取りうるすべての値、つまり０または１、について誤差の計算を先に行うことによってフィードバックループを小さくしている。このような予測処理を応用することによって、処理をパイプライン化することができる。
【００１０】
図９は、図６に示す処理をパイプライン処理で行う場合の概念図、図１０は、同じくタイミングチャートである。図６に示したフローチャートの処理をパイプライン処理によって実行する場合には、入力されたデータがフィードバックの発生するデータであった場合に、出力データが取りうるすべての値について、あらかじめ演算を行っておく。従って図９に示すように、複数の場合について並行して処理Ａ、処理Ｂ、処理Ｃ、処理Ｄを実行しておく。そして、直前に入力されたデータの出力値によって、複数の処理結果のうちのいずれかを選択すればよい。
【００１１】
これによって、次のデータに対する演算をフィードバックループの外に出すことができる。この結果、出力データがフィードバックされるのを待つ必要がなくなるため、フィードバックが発生するデータでのスループットの向上が期待できる。
【００１２】
しかし、この特開２０００−１５２００５号公報に記載されている技術を応用した手法では、直前のデータに関する予測を行って次のデータの処理に必要な演算を行う構成であるため、少なくとも２つ前のデータについての演算が終了していなければ、当該入力データの処理を開始することができない。このことは逆に、２サイクルで全ての処理を終えなければパイプラインが構成できないということになる。このため、図６に示した処理を実行するパイプラインを構成するには、４つの処理を２サイクルで実行させるように２つの処理ステップを１サイクルで動作させなければいけない。
【００１３】
従って、特開２０００−１５２００５号公報に記載された手法を応用した手法で図６に示した処理をパイプラインで構成した場合には、図１０に示したタイミングチャートのように、２つの処理ステップを１単位として実行することになる。なお、図１０において、各処理ステップが動作する動作周波数は図８の場合と同様である。従って、１単位を実行する時間は、２処理ステップの実行時間となる。
【００１４】
図１０からわかるように、パイプライン構成にすれば、フィードバックの発生の有無にかかわらず、１単位（２処理ステップ）毎に出力が得られる。従って、ハッチングを施さずに示したフィードバックが発生する入力データに関しては、図８に示した逐次処理に比べて約半分の処理時間で出力データを得ることができる。しかし、ハッチングを施して示した、フィードバックが発生しない入力データについても２処理ステップ分の処理時間を要するため、図８に示した逐次処理に比べて２倍の処理時間がかかってしまう。つまり、パイプライン構成では、逐次処理と比較してフィードバックの発生しないデータでのスループットが低下してしまう。
【００１５】
図１１は、逐次処理及び並列パイプライン処理による処理時間の一例の説明図である。ここでは、図６に示した処理を図７に示すように逐次処理によって実行した場合と図９に示したように並列パイプライン処理によって実行した場合について、全てフィードバックが発生するデータあるいは全てフィードバックが発生しないデータを入力した場合の処理時間の一例を示している。入力したデータは、それぞれ３千万個である。また、各処理における動作周波数を１００ＭＨｚとしている。従って、並列パイプライン処理の場合の１単位毎の動作周波数は５０ＭＨｚとなる。
【００１６】
図１１に示したように、逐次処理の場合、フィードバックが発生しない場合には０．３秒で処理が終了するものの、フィードバックが発生する場合には５倍の１．５秒を要している。また並列パイプライン処理では、フィードバックが発生するか否かに関わらず、０．６秒で処理を行うことができる。従って、フィードバックが発生しないデータでは逐次処理が、フィードバックが発生するデータでは並列パイプライン処理が適していることがわかる。このため、どちらか一方の処理方式を選択してしまうと、入力データによりスループットが低下してしまうという問題があることがわかる。
【００１７】
なお、上述の並列パイプライン処理では４段のパイプライン構成の場合について示したが、例えばより多くの段数のパイプラインの場合でも、直前のデータのみを予測するためには全段数の半分を１単位として動作させることになる。従って、より段数が多い場合、フィードバックが発生しないデータにおいては、処理時間の差はさらに大きくなる。
【００１８】
直前だけでなく、その前のデータについても予測することによって、パイプラインを動作させる１単位の段数を減少させ、高速化することが考えられる。しかし、フィードバックされる出力が取り得る値がＭ個の場合、Ｎ個前の予測にはＭ×Ｎ−（Ｎ−１）の予測データが必要である。例えば直前のデータから予測されるデータの数が１０個であれば、予測されるデータの数は９Ｎ＋１で増大する。そのため、１つ前のデータまで予測する場合には１０個の予測データについて並列的に演算を行えばよいが、２つ前のデータまで予測すると１９個、３つ前のデータまで予測すると２８個の予測データについて並列的に演算を行わなければならない。例えば上述のような４段のパイプライン構成においてそれぞれの処理サイクルにおいてデータを入力するように構成すると、３つ前のデータまで予測することになるため、２８個の予測データについて並列的に演算してゆかねばならない。２サイクルを１単位とした場合には１０個の予測データを並列的に演算すればよいので、この場合に比べて約３倍の回路が必要となる。
【００１９】
このように直前のデータよりも前のデータについてまで予測して並列演算を行うには、ハードウェア量が膨大となり、現実的でない回路規模となってしまう。そのため、直前よりも前のデータまで予測するようなパイプラインを構成することによる問題の解決は、実際には不可能に近い。
【００２０】
【発明が解決しようとする課題】
本発明は、上述した事情に鑑みてなされたもので、フィードバックが発生する処理と発生しない処理のうちいずれかを入力データから選択して実行する場合に、フィードバックが発生するデータが入力された場合でも、フィードバックが発生しないデータが入力された場合でも、ともに高速に処理を行うことができる情報処理装置を提供することを目的とするものである。
【００２１】
【課題を解決するための手段】
本発明は、フィードバックが発生する処理とフィードバックが発生しない処理のうちいずれかを入力データから選択して当該入力データに対して処理を行う情報処理装置において、フィードバックが発生する処理をフィードバックが発生したときに取り得る値のすべてについて入力データに対して並列にパイプライン処理する演算手段と、入力データによりフィードバックが発生する処理とフィードバックが発生しない処理のうちいずれかを選択する判断手段と、判断手段による処理の選択結果により一方の処理を打ち切る打ち切り手段を有している。データが入力されると、判断手段によって処理の選択を行い、その選択結果に従って打ち切り手段がいずれか一方の処理を打ち切る。
【００２２】
例えばフィードバックが発生しない場合には、演算手段において行われている当該入力データに対するパイプライン処理を打ち切って、フィードバックが発生しないときの処理を行う。これによって、フィードバックが発生しないデータの場合には、パイプライン処理による遅延が生じないので高速に実行することができる。また、フィードバックが生じる場合には演算手段において並列にパイプライン処理を行うことによって、逐次処理を行う場合に比べて高速に実行することができる。
【００２３】
従って、フィードバックが発生しないデータが入力された場合でも、フィードバックが発生するデータが入力された場合でも、入力データによって選択された処理内容に適した処理方式が適用されるため、高速に処理を実行することができる。
【００２４】
【発明の実施の形態】
図１は、本発明の情報処理装置の実施の一形態を含む画像符号化装置の一例を示すブロック図、図２は、画像符号化処理の一例を示すフローチャート、図３は、誤差拡散法あるいは平均誤差法における誤差分配の一例の説明図である。図中、１は画素値変更部、２は符号化部、３は誤差分配部、４は入力画素、５は出力画素、６は符号データ、７は誤差、８は分配誤差、１１は入力制御部、１２は判断部、１３は打ち切り部、１４は並列演算部、１５はセレクタ、１６は決定信号である。図１に示す例では、例えば特願２００１−１８２９５５号の実施例１として示されている画像符号化装置の構成に本発明の情報処理装置を適用した場合の一例を示している。
【００２５】
この画像符号化装置では、本発明の情報処理装置を用いて入力画素４を変更する画素値変更部１と、画素値変更部１から出力される出力画素５を入力とし符号データ６を出力する符号化部２と、画素値変更部１のもう一つの出力である誤差７を入力として分配誤差８を出力する誤差分配部３から構成されている。符号化部２は、任意の可逆符号化あるいは非可逆符号化手法によって出力画素５を符号化する。また、誤差分配部３は、入力された誤差７を周囲の画素に対して分配する。実際には例えば図３に示すように、注目画素をｘとしたとき、その周囲の処理済の画素、例えば画素ａ〜ｅなどから誤差が注目画素ｘに繰り込まれる。従って誤差分配部３は、画素値変更部１において注目画素ｘに繰り込む誤差を分配誤差８として出力する。このとき、画素ａは注目画素ｘの直前の画素であり、画素ａの値が決まらないと画素ａから注目画素ｘへ分配される誤差は決まらないが、後述するようにこの誤差を予測して画素値変更部１において演算を行う。この予測のためには画素ａの変更値は決定されるか予測しなければならない。後述するように並列演算部１４のパイプラインの段数の半分のサイクルを１単位として動作させるので、誤差分配部３は画素ａの前の画素値が決定して画素ａの変更値が決定してから、その画素ａの変更値とその他の周囲画素から注目画素ｘへ分配される誤差を分配誤差８として出力することができる。
【００２６】
画素値変更部１は、入力制御部１１、判断部１２、打ち切り部１３、並列演算部１４を有している。入力制御部１１は、入力画素４を受け取って判断部１２及び並列演算部１４に渡す。このとき、判断部１２から送られてくる決定信号１６に従って、フィードバックが発生しないと判断部１２が判断した場合には連続して入力画素４を転送し、フィードバックが発生すると判断部１２が判断した場合には１サイクルおきに入力画素４の転送を行うように、入力タイミングを制御する。
【００２７】
判断部１２は、入力制御部１１から転送されてくる入力画素４から、フィードバックが発生する場合の処理とフィードバックが発生しない場合の処理のいずれを行うかを決定する。この例では、判断部１２は入力画素４の値（あるいは誤差配分を受けた後の画素値）が周囲のいずれかの画素と値が一致するか否かを判断し、一致する場合にフィードバックが発生しないと判断する。また、一致する画素が存在しない場合に、フィードバックが発生すると判断する。なお、この例ではフィードバックが発生しない場合には、入力画素４をそのまま、あるいは所定の処理を施して、出力画素５として出力する。あるいは、一致した画素位置を特定する情報などを出力画素５として出力する場合もある。また、誤差分配部３には、誤差として０が渡される。さらに、この判断部１２の判断結果は決定信号１６として入力制御部１１に渡される。また、判断結果は打ち切り部１３に渡される。
【００２８】
打ち切り部１３は、判断部１２の判断結果に従って、例えばフィードバックが発生しないと判断された場合に、並列演算部１４における当該入力画素４に対するパイプライン処理を停止させる。
【００２９】
並列演算部１４は、フィードバックが発生する場合の処理を、並列パイプライン構成によって実行する。すなわち、入力制御部１１から入力画素４が入力されると、誤差分配部３から渡される分配誤差８をもとに、フィードバックが発生する場合にその入力画素４が処理後に取り得る値を予測し、その取り得る値毎に並列して以下に説明するような処理を行う。ここでは一例として４段のパイプラインを構成しており、それぞれ、処理Ａ、処理Ｂ、処理Ｃ、処理Ｄを実行する。また、並列して処理された結果は、直前の出力画素５の値によってセレクタ１５で選択して、出力画素５として出力する。なお、打ち切り部１３から処理の打ち切りの処理が行われた場合には、打ち切られた入力画素４に対するそれ以後の処理は行われない。
【００３０】
図１に示した構成によって実行される画像符号化処理の一例を図２に示している。この図２に示した処理は、上述のように特願２００１−１８２９５５号に記載されている画像符号化技術を応用したものである。入力画素４（あるいは入力画素４に分配誤差を加えた値）は、Ｓ２１において複数の符号化予測データ（具体的には図３に示す注目画素ｘの周囲の画素ａ〜ｅなど）と比較され、一致する符号化予測データの有無を判断する。一致する符号化予測データが一つでもあれば、フィードバックを行わないものと判断し、入力画素４を出力画素５として符号化部２に出力し、また誤差分配部３に対して誤差として０を出力する。そしてＳ２６において、符号化部２で出力画素５を符号化処理し、符号データ６として出力する。
【００３１】
Ｓ２１で一致する符号化予測データがないと判断された場合、Ｓ２２において入力画素４に対して分配誤差を加算する。分配誤差は、画素値変更部１が生成した誤差を入力として誤差分配部３で生成されたものであり、例えば誤差拡散法や平均誤差法に従い、図３に示すように周囲の画素からの誤差に重み行列を乗算して算出されたものである。
【００３２】
Ｓ２３では、Ｓ２２で分配誤差を加算した画素と符号化予測データの差分を算出する。Ｓ２４では、Ｓ２３で算出された差分のうち最小となるものを探索する。Ｓ２５では、Ｓ２４で探索した最小となる差分と規定値を大小比較し、差分が規定値以下であれば、最小となる差分のもととなった符号化予測データを出力画素５として符号化部２に出力し、誤差として最小となる差分を出力する。逆に最小となる差分が規定値より大きい場合は、分配誤差を加算した画素を出力画素５として符号化部２に出力し、誤差として０を出力する。いずれの場合も、Ｓ２６において、符号化部２で出力画素５を符号化し、符号データ６を出力する。
【００３３】
この図２に示した処理自体は、逐次処理でも実行可能であるが、Ｓ２２における分配誤差の加算時に直前の画素の処理結果を予測し、直前の画素においてフィードバックが発生した場合に取り得る１ないし複数通りの場合についてそれぞれ並列して演算を行うことによって並列パイプライン構成を実現する。上述のように、直前の入力画素についてフィードバックが発生すると判定されている場合、直前の画素からの分配誤差は決定されていない。そのため、直接的にはＳ２２において分配誤差の加算を行うことができない。しかし、その前までの画素値が決定され、直前の入力画素値がわかれば、直前の入力画素に対応する出力画素値及び誤差を１ないし複数通りに絞ることができる。この１ないし複数通りについて予測し、それぞれについて並行して演算を行えばよい。
【００３４】
上述の説明を踏まえた上で、図１に示した構成について、動作の一例を説明する。入力画素４は、入力制御部１１を介して判断部１２、並列演算部１４に入力され、判断部１２において各符号化予測データと入力画素４が一致するか否かを判断する。この判断部１２における判断処理と並行して、並列演算部１４での演算を開始する。この並列演算部１４では、まずパイプラインの初段である処理Ａにおいて、次に処理される画素が予測データと一致しなかった場合に行う分配誤差加算（図２におけるＳ２２の処理のうち誤差部分の加算処理）を、当該入力画素４の出力結果が決定する前に行う。例えば図３に示すような周囲画素からの誤差分配を行う場合、この時点で行う処理は、画素ａ〜ｅから注目画素ｘに分配される誤差部分の計算である。画素ａが符号化予測データと一致していない場合、すなわちフィードバックが発生する場合には、この時点では画素ａの出力値は計算されていない。そのため、この画素ａが取り得るすべての値を予測して、それぞれの予測値について並列に演算する。この画素ａが取り得る値とは、入力画素４に対する出力画素５が取り得る値のことであり、画素ａに対する分配誤差と、入力画素４（すなわち画素ａの処理前の値）と、画素ａに対する符号化予測データとから演算することができる。なお、画素ａに対する分配誤差は、画素ａの直前の画素まで処理が終了していれば確定する。そして、画素ａが取り得る値と、その他の周囲の画素ｂ〜ｅから分配される誤差とを加算することによって、注目画素ｘに対して分配される誤差の総量を計算することができる。なお、この時点では次に処理される画素（注目画素ｘ）については、まだ入力されていない。
【００３５】
判断部１２において入力画素４と一致する符号化予測データが存在すると判断されると、入力画素４がそのまま出力画素５として出力され、誤差７として０が出力される。同時に、判断部１２における判断結果が打ち切り部１３に伝えられ、打ち切り部１３によって、並列演算部１４における当該入力画素４についての処理を停止させる。
【００３６】
逆に判断部１２において入力画素４と一致する符号化予測データが存在しないと判断されると、打ち切り部１３は並列演算部１４の処理をそのまま続行させる。並列演算部１４は、上述のようにパイプラインの初段において上述のように図２におけるＳ２２の処理を予測値によって進めている。そして、２段目において図２におけるＳ２３の処理、３段目において図２におけるＳ２４の処理、最終段において図２におけるＳ２５の処理を実行する。すなわち、２段目においては、初段で計算された分配誤差を、新たに入力された入力画素４に対して加算した上で、符号化予測データとの差分値をそれぞれ計算する。さらに３段目において、２段目で計算された差分値のうちから最小値を探索する。そして最終段において、３段目において探索された差分値の最小値と既定値を比較し、差分が規定値以下であれば、最小となる差分のもととなった符号化予測データを出力画素５として出力し、誤差として最小となる差分を出力する。逆に最小となる差分が規定値より大きい場合は、分配誤差を加算した画素を出力画素５として符号化部２に出力し、誤差として０を出力する。
【００３７】
このようなパイプライン処理を、初段と２段目を１単位とし、３段目と最終段を１単位とした２単位を、それぞれ並行して処理を行う。すなわち、初段と３段目、２段目と最終段を並行して実行する。そのため、この並列演算部１４の動作は以下のようになる。まずフィードバックが発生しない場合の処理について示す。なお、Ｎ番目の画素が入力される前のＮ−１番目の画素については符号化予測データと一致しており、フィードバックが発生しないものとする。この場合、入力制御部１１は連続して入力画像４を判断部１２及び並列演算部１４に転送する。
【００３８】
Ｎ番目の画素が入力されると、その入力画素４の入力と同じサイクルで、判断部１２と並列演算部１４の初段で同時に処理が実行される。次のサイクルでＮ＋１番目の画素が入力されると、この入力画素は判断部１２と並列演算部１４の初段で同時に処理され、並列演算部１４の初段で処理されたＮ番目の画素は並列演算部１４の２段目で処理される。ここで、Ｎ＋１番目の入力画素が判断部１２で予測データと一致すると判断されれば、Ｎ＋１番目の入力画素の画素値変更はおこなわれないため、並列演算部１４の２段目で処理されたＮ回目のデータについての演算は必要がないので３段目以降の処理は打ち切られる。このようにして、入力画素４が符号化予測データと一致し、フィードバックが発生しない場合には、パイプライン処理は途中で打ち切られ、１サイクル毎に、入力画素４が入力されて出力画素５が出力されることになる。
【００３９】
次に、フィードバックが発生する場合について説明する。フィードバックが発生する場合には、入力制御部１１は２サイクルを１単位とする動作により、１サイクルおきに入力画素４を判断部１２及び並列演算部１４に転送するように制御する。なお、Ｎ−１番目の画素が符号化予測データと一致していないものとして動作するものとして説明する。この場合、Ｎ番目の画素に対する分配誤差の演算はＮ番目の画素が入力される前に並列演算部１４の初段ですでに終了している。Ｎ番目の画素が入力されると、並列演算部１４の２段目でＮ番目の画素への分配誤差とＮ番目の画素との和が演算されるとともに各符号化予測データとの差分が計算される。
【００４０】
次のサイクル（これが１単位の前半のサイクルとなる）でＮ番目の画素が判断部１２と並列演算部１４の初段で同時に処理が実行される。並列演算部１４の初段では、Ｎ＋１番目の画素への分配誤差の演算が行われる。また、並列演算部１４の３段目においてＮ番目の画素について差分の最小値が探索される。このサイクルでの入力画素４の転送は行われない。ここでは判断部１２はフィードバックが発生すると判断したものとする。
【００４１】
次のサイクル（１単位の後半のサイクル）でＮ＋１番目の画素が入力されると、並列演算部１４の初段における処理結果が２段目に送られ、入力されたＮ＋１番目の入力画素４を用いて２段目において差分値算出処理が行われる。また、並列演算部１４の４段目においてＮ番目の画素について既定値との比較処理が行われる。
【００４２】
そして次のサイクル（１単位の前半のサイクル）において、演算が終了したＮ番目の画素に対応する出力画素５及び誤差７が出力される。このとき、Ｎ番目の画素の処理結果は並列に複数計算されているが、Ｎ−１番目の画素の処理結果によってセレクタ１５によりいずれかが選択され、出力画素５及び誤差７として出力される。また、Ｎ番目の画素の演算結果である出力画素５及び誤差７が決まったことによって、Ｎ＋１番目の画素への分配誤差が決定する。誤差分配部３は、誤差７を用いて、Ｎ＋１番目の画素の出力値が決定しない段階で、Ｎ＋１番目の画素からＮ＋２番目の画素への分配誤差を予測計算し、並列演算部１４の初段に入力される。このとき、直前のサイクルで入力されたＮ＋１番目の画素とともにＮ＋２番目の画素へ分配される誤差を計算する。また、直前のサイクルで入力されたＮ＋１番目の画素については、判断部１２における判断処理が並行して実行される。さらに、並列演算部１４の２段目で演算していたＮ＋１番目の画素については、並列演算部１４の３段目に送られて演算が続けられる。
【００４３】
このように、１単位の前半のサイクルでは、Ｎ番目の画素について演算結果として出力画素５及び誤差７の出力と、Ｎ＋１番目の画素について並列演算部１４の３段目における演算と、入力されたＮ＋１番目の画素に対する判断部１２による判断処理と、同じく入力されたＮ＋１番目の画素と誤差分配部３からの分配誤差８を用いた並列演算部１４の初段におけるＮ＋２番目の画素への分配誤差の計算が行われる。また１単位の後半のサイクルでは、Ｎ＋２番目の画素の入力によるＮ＋２番目の画素の符号化予測データとの差分演算を並列演算部１４の２段目で行うとともに、Ｎ＋１番目の画素について既定値との比較処理を並列演算部１４の４段目で行う。フィードバックが発生する場合には、このような２サイクルを１単位とした並列パイプライン処理を繰り返して行う。
【００４４】
なお、直前の入力画素に対する判断結果がフィードバックが発生しない判断であり、当該入力画素に対する判断結果がフィードバックが発生する判断であった場合には、その判断直後から入力制御部１１は２サイクル毎の入力画素の転送処理に移行するとともに、並列演算部１４の処理についても動作の調整を行う。また逆に、直前の入力画素に対する判断結果がフィードバックが発生する判断であり、当該入力画素に対する判断結果がフィードバックが発生しない判断であった場合には、次の入力画素以降について、入力制御部１１は連続した入力画素の転送を行うとともに、打ち切り部１３は当該入力画素について先行して実行している並列演算部１４における処理を打ち切り、以後、フィードバックが発生しない場合の処理を行う。
【００４５】
図４は、本発明の情報処理装置の実施の一形態における動作の一例を示すタイミングチャートである。上述の動作の一例を、図４に示すタイミングチャートを用いてさらに説明する。図４において、ハッチングを施した入力画素は符号化予測データと一致する画素、すなわちフィードバックが発生しない画素を示し、ハッチングを施していない入力画素は符号化予測データと一致しない画素、すなわちフィードバックが発生する画素を示している。また、パイプライン処理においては図２に示した処理ステップをそれぞれ示している。さらに、矢印で示された点線の処理は、打ち切られたことを示している。なお、図４においては、画素１の前に入力された画素が符号化予測データと一致していたものとして図示している。
【００４６】
画素１が入力される前に、すでに並列演算部１４の初段において、画素１に分配される誤差を算出するための演算（Ｓ２２）は終了している。処理サイクルＡにおいて、画素１が入力される。入力された画素１は、判断部１２及び並列演算部１４に入力される。判断部１２において画素１の判断処理を行う時、この判断処理と並行して、並列演算部１４の２段目において画素１における差分値の演算（Ｓ２３）と、初段において画素２に分配される誤差を算出するための演算（Ｓ２２）を行う。この例では、画素１は符号化予測データと一致する画素であるので、判断部１２はフィードバックは発生しないと判断する。
【００４７】
処理サイクルＢでは、処理サイクルＡにおける判断部１２の判断結果、すなわちフィードバックが発生しないとの判断結果が打ち切り部１３に通知され、打ち切り部１３は画素１に対する処理（並列演算部１４の３段目以降の処理）を打ち切る。また、画素１に対応する出力画素が出力されるとともに誤差として０が出力される。この処理サイクルＢでは、画素２が入力され、並列演算部１４の２段目において画素２における差分値の演算（Ｓ２３）と、初段において次に入力される画素３に分配される誤差の算出（Ｓ２２）が並行して実行される。
【００４８】
処理サイクルＣでは、処理サイクルＢにおける判断部１２の判断結果、すなわちフィードバックが発生しないとの判断結果が打ち切り部１３に通知され、打ち切り部１３は画素２に対する処理（並列演算部１４の３段目以降の処理）を打ち切る。また、画素２に対応する出力画素が出力されるとともに誤差として０が出力される。この処理サイクルＣでは、画素３が入力され、並列演算部１４の２段目において画素３における差分値の演算（Ｓ２３）と、初段において次に入力される画素４に分配される誤差の算出（Ｓ２２）が並行して実行される。このようにして、フィードバックが発生しない画素が連続して入力される場合には、このような処理が連続して実行されることになる。
【００４９】
画素３は、符号化予測データと一致せず、フィードバックが発生する。そのため、これ以後の処理サイクルでは、フィードバックが発生したときの２サイクルを１単位とした動作に切り替わる。
【００５０】
処理サイクルＤでは、画素３に対する処理が継続され、並列演算部１４の３段目において画素３における最小値の探索処理（Ｓ２４）が行われる。また、未入力の画素４に対する処理も継続されるが、ここではタイミング調整のため、並列演算部１４の初段の処理を再度実行する。あるいは１サイクル分、処理を休止してもよい。
【００５１】
処理サイクルＥでは、画素３に対する処理が継続され、並列演算部１４の最終段において画素３における規定値との比較処理（Ｓ２５）が行われる。また、画素４が入力され、並列演算部１４の２段目において画素４に対する符号化予測データとの差分値の算出処理（Ｓ２３）が行われる。この時点ではまだ画素３の値が確定していないので、画素４に対する判断部１２における判断処理及び並列演算部１４の初段における分配誤差の算出処理は行わない。
【００５２】
処理サイクルＦでは、画素３に対する処理が終了し、出力画素及び誤差が出力される。これを受けて、画素４に対する判断部１２における判断処理、及び、並列演算部１４の初段における画素５に対する分配誤差の算出処理（Ｓ２２）が行われる。なお、画素４はフィードバックが発生すると判断されるので、打ち切り部１３による処理の打ち切りは行われない。また処理サイクルＦでは、並列演算部１４の３段目における画素４に対する最小値の探索処理（Ｓ２４）が行われる。この最小値の探索処理では、画素３が確定したことによって、確定した画素３の値に対応する組み合わせのみについて探索処理を行えばよく、処理すべきデータ量を減少させることが可能である。
【００５３】
処理サイクルＧは処理サイクルＥと同様であり、並列演算部１４の最終段において画素４における規定値との比較処理（Ｓ２５）が行われ、また、画素５が入力されて、並列演算部１４の２段目において画素５に対する符号化予測データとの差分値の算出処理（Ｓ２３）が行われる。フィードバックが発生する場合には、この処理サイクルＦ、Ｇに示すような２サイクルの処理を１単位として繰り返すことによって処理が進められる。
【００５４】
処理サイクルＨも処理サイクルＦと同様であり、画素４に対する処理が終了し、出力画素及び誤差が出力される。これを受けて、画素５に対する判断部１２における判断処理、及び、並列演算部１４の初段における画素６に対する分配誤差の算出処理（Ｓ２２）が行われる。また、並列演算部１４の３段目における画素５に対する最小値の探索処理（Ｓ２４）が行われる。
【００５５】
処理サイクルＩでは、並列演算部１４の最終段において画素５における規定値との比較処理（Ｓ２５）が行われ、また、画素６が入力されて、並列演算部１４の２段目において画素６に対する符号化予測データとの差分値の算出処理（Ｓ２３）が行われる。入力された画素６は、符号化予測データと一致し、フィードバックが発生しない画素であるが、この時点ではまだ画素５の値が確定していないので、画素６に対する判断部１２における判断処理及び並列演算部１４の初段における分配誤差の算出処理は行わない。
【００５６】
処理サイクルＪでは、画素５に対する処理が終了し、出力画素及び誤差が出力される。これを受けて、画素６に対する判断部１２における判断処理、及び、並列演算部１４の初段における画素７に対する分配誤差の算出処理（Ｓ２２）が行われる。なお、画素６に対する判断部１２における判断処理によって、画素６は符号化予測データと一致し、フィードバックが発生しないと判断される。また処理サイクルＪでは、並列演算部１４の３段目における画素６に対する最小値の探索処理（Ｓ２４）が行われる。
【００５７】
処理サイクルＫでは、処理サイクルＪにおける判断部１２の判断結果、すなわちフィードバックが発生しないとの判断結果が打ち切り部１３に通知され、打ち切り部１３は画素６に対する処理（並列演算部１４の最終段の処理）を打ち切る。また、この判断結果が入力制御部１１に通知され、以後、フィードバックが発生しないときの処理タイミング、すなわち連続して入力画素の転送を行う。また、この処理サイクルＫにおいて、画素６に対応する出力画素が出力されるとともに誤差として０が出力される。さらに、画素７が入力され、並列演算部１４の２段目において画素７における差分値の演算（Ｓ２３）と、図示していないが、初段において次に入力される画素８に分配される誤差の算出が並行して実行される。また、入力された画素７に対する判断部１２における判断処理も並行して行われる。画素７も符号化予測データと一致するため、処理サイクルＬにおいて打ち切り部１３は画素７に対する処理（並列演算部１４の３段目以降の処理）を打ち切り、画素７に対応する出力画素及び誤差が出力される。
【００５８】
このようにして、入力画素に適した処理方式で演算を行うように切り替えることによって、符号化予測データと一致した場合は１サイクルで、不一致であった場合は平均して２サイクルで出力を得ることができる。
【００５９】
図５は、本発明による処理時間と従来の逐次処理及び並列パイプライン処理による処理時間の比較例の説明図である。ここでは、図２に示した処理を、従来の図７に示すように逐次処理によって実行した場合と、同じく従来の図９に示したように並列パイプライン処理によって実行した場合、及び、上述の本発明によって実行した場合を示している。いずれも、全てフィードバックが発生するデータあるいは全てフィードバックが発生しないデータを入力した場合の処理時間の一例を示している。入力したデータは、６００ｄｐｉ、Ａ４フルカラーのデータ（３０Ｍｐｉｘｅｌ）である。また、各処理サイクルにおける動作周波数を１００ＭＨｚとしている。
【００６０】
本発明では、フィードバックが発生する場合には並列処理の場合と同様に動作し、フィードバックが発生しない場合には並列処理を打ち切ることによって逐次処理と同様に動作する。従って、図５に示したように、フィードバックが発生する場合も、またフィードバックが発生しない場合についても、いずれの場合も高速に処理を行うことができる。
【００６１】
上述の説明では、判断部１２における判断方法として、入力画素（あるいは入力画素に誤差を分配した後の値）と符号化予測データとの比較を行うものとしたが、これに限られるものではない。その他の判断方法として、入力画素と１つ前のサイクルでの処理結果を用いた演算から、画素変更すべきか否かを判定し、処理方式を選択することも可能である。また、誤差拡散法あるいは平均誤差法において参照される周囲画素は図３に示した画素に限られるものではなく、任意の位置及び個数の周囲画素を用いることができる。
【００６２】
また、並列演算部１４におけるパイプラインの段数は４段に限られるものではなく、フィードバックが発生する場合に行う処理に応じて段数を設計すればよい。その場合、直前の画素のみについて出力画素値の予測を行うためには段数の半分のサイクルを１単位として、単位毎に動作させる必要がある。もちろん、直前の画素とともにそれより前の画素についても予測するように構成することもでき、その場合には１単位のサイクル数を減少させてパイプラインでより高速に演算を行うことができる。しかしその場合には予測される値の場合分けが多数となることが予想されるので、並列して実行するための回路規模とのトレードオフとなる。
【００６３】
さらに、上述の構成ではフィードバックが発生しない場合にはそのまま出力されているが、フィードバックが発生しない場合のみについて行われる処理が存在していてもよい。このような処理が付加されている場合、判断部１２においてフィードバックが発生すると判断されたときには、打ち切り部１３によってこのフィードバックが発生しない場合の処理が打ち切られることになる。
【００６４】
上述の実施の形態では、本発明を画像符号化装置に適用する例を示したが、本発明はこれに限られるものではなく、フィードバックが発生する場合の処理とフィードバックが発生しない場合の処理とを切り替えて実行するようなあらゆる処理に対して適用可能である。もちろん、処理対象となるデータも画像データに限られるものではなく、種々のデータに対して適用可能である。
【００６５】
【発明の効果】
以上の説明から明らかなように、本発明によれば、入力データによって、フィードバックが発生する処理と発生しない処理のうちいずれかを選択して実行する場合に、選択した処理内容に適した処理方式を選択して実行するので、フィードバックが発生する処理と発生しない処理のいずれを実行した場合でも、ともに高速に処理を行うことができるという効果がある。
【図面の簡単な説明】
【図１】  本発明の情報処理装置の実施の一形態を含む画像符号化装置の一例を示すブロック図である。
【図２】  画像符号化処理の一例を示すフローチャートである。
【図３】  誤差拡散法あるいは平均誤差法における誤差分配の一例の説明図である。
【図４】  本発明の情報処理装置の実施の一形態における動作の一例を示すタイミングチャートである。
【図５】  本発明による処理時間と従来の逐次処理及び並列パイプライン処理による処理時間の比較例の説明図である。
【図６】  フィードバックが発生する処理と発生しない処理を切り替えて実行する処理の一例を示すフローチャートである。
【図７】  図６に示す処理を逐次処理で行う場合の概念図である。
【図８】  図６に示す処理を逐次処理で行う場合のタイミングチャートである。
【図９】  図６に示す処理をパイプライン処理で行う場合の概念図である。
【図１０】  図６に示す処理をパイプライン処理で行う場合のタイミングチャートである。
【図１１】  逐次処理及び並列パイプライン処理による処理時間の一例の説明図である。
【符号の説明】
１…画素値変更部、２…符号化部、３…誤差分配部、４…入力画素、５…出力画素、６…符号データ、７…誤差、８…分配誤差、１１…入力制御部、１２…判断部、１３…打ち切り部、１４…並列演算部、１５…セレクタ、１６…決定信号。
【図１】
0003666586.tif 000002
【図２】
0003666586.tif 000003
【図３】
0003666586.tif 000004
【図４】
0003666586.tif 000005
【図５】
0003666586.tif 000006
【図６】
0003666586.tif 000007
【図７】
0003666586.tif 000008
【図８】
0003666586.tif 000009
【図９】
0003666586.tif 000010
【図１０】
0003666586.tif 000011
【図１１】
0003666586.tif 000012