(57)【特許請求の範囲】
【請求項１】
一定の領域が同一の色で描かれた画像内の均等色領域を抽出する方法であって、
ある一定の大きさの小領域の画像信号からこの小領域の特性を表す統計量を求めステップと、
前記小領域の近傍の画素のうち、前記統計量に近い値をもつ画素を均等色領域として順次領域拡大して均等色領域を抽出するステップと、
前記統計量を求めるステップと前記均等色領域を抽出するステップとを画像全体に対して行い、該画像全体を１以上の均等色領域に分割するステップと、
前記分割して得られた各均等色領域に対して、他の均等色領域との境界に近い画素を起点として、再度均等色領域の再抽出を行うステップと、
前記先の均等色領域と前記再抽出の結果得られた均等色領域の一致度をもとに、前記初期の均等色領域あるいは前記再抽出の結果得られた均等色領域を均等色領域とするかテクスチャ領域とするかを判定するステップとを有し、
前記判定するステップまでを１回以上繰り返して、均等色領域を抽出する
ことを特徴とする均等色領域抽出方法。
【請求項２】
前記判定するステップでは、
先の抽出結果と再抽出の結果を比較し、それぞれの均等色領域を対照付け、
各均等色領域において、両者に属する画素数がある閾値を越えたときに、その領域を均等色領域と判断し、該閾値以下であれば、テクスチャ領域と判断する
ことを特徴とする請求項１記載の均等色領域抽出方法。
【請求項３】
前記再度均等色領域の再抽出を行うステップでは、
既に他の均等色領域に対する再抽出の結果により抽出済みの領域との重複領域がある場合に、その重複領域を除いて均等色領域の再抽出を行う
ことを特徴とする請求項１または２記載の均等色領域抽出方法。
【請求項４】
前記統計量として、小領域の平均輝度と平均色差信号の一方または両方を用いる
ことを特徴とする請求項１，２，３のいずれか１項記載の均等色領域抽出方法。
【請求項５】
ある一定の大きさの小領域の画像信号からこの小領域の特性を表す統計量を求め、前記小領域の近傍の画素のうち、前記統計量に近い値をもつ画素を均等色領域として順次領域拡大して均等色領域を抽出し、前記統計量を求め、前記均等色領域を抽出することを画像全体に対して行い、該画像全体を１以上の均等色領域に分割する均等色領域抽出手段と、
前記抽出された均等色領域を記憶する抽出結果記憶手段と、
前記分割して得られた各均等色領域に対して、他の均等色領域との境界に近い画素を起点として、再度均等色領域の再抽出を行う均等色領域再抽出手段と、
前記再抽出の結果得られた均等色領域を記憶する再抽出結果記憶手段と、
前記記憶された先の均等色領域と再抽出の結果得られた均等色領域の一致度をもとに、前記先の均等色領域あるいは前記再抽出の結果得られた均等色領域を均等色領域とするかテクスチャ領域とするかを判定する判定手段とを、
具備することを特徴とする均等色領域抽出装置。
【請求項６】
前記判定手段は、
先の抽出結果と再抽出の結果を比較し、それぞれの均等色領域を対照付け、各均等色領域において、両者に属する画素数がある閾値を越えたときに、その領域を均等色領域と判断し、該閾値以下であれば、テクスチャ領域と判断するものである
ことを特徴とする請求項５記載の均等色領域抽出装置。
【請求項７】
前記均等色領域再抽出手段は、
既に他の均等色領域に対する再抽出の結果により抽出済みの領域との重複領域がある場合に、その重複領域を除いて均等色領域の再抽出を行うものである
ことを特徴とする請求項５または６記載の均等色領域抽出装置。
【請求項８】
均等色領域抽出手段及び均等色領域再抽出手段は、
統計量として、小領域の平均輝度と平均色差信号の一方または両方を用いるものである
ことを特徴とする請求項５，６，７のいずれか１項記載の均等色領域抽出装置。
【請求項９】
請求項１，２，３，４のいずれか１項記載の均等色領域抽出方法におけるステップをコンピュータに実行させるためのプログラムを、該コンピュータが読み取り可能な記録媒体に記録した
ことを特徴とする均等色領域抽出方法を記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、線画像等を高能率に符号化する技術に関する。
【０００２】
【従来技術】
画像をオブジェクトごとに分割して、通信や、符号化を行う技術は、ＭＰＥＧ−４などで使用されている。オブジェクトへの領域分割は、画像を単に分割するのではなく、画像の特徴的な部分を抽出して分割するというものである。
【０００３】
画像の特徴的な部分を抽出するための従来の同色領域抽出方法としては、東京大学出版会「画像解析ハンドブック」（高木幹雄・下田陽久  監修）Ｐ．６８９第２部２章“領域分割での単純領域拡張法”などがある。単純領域拡張法の処理の流れを以下に示す。
【０００４】
（イ）画像をラスター走査し、どの領域にも属していない画素を探す。
【０００５】
（ロ）その画素の濃淡レベルと、その近傍（４連結または８連結）で、どの領域にもまだ属していない画素の濃淡レベルとを比較し、その差がある閾値θ以下ならば１つの領域として統合し、ラベルを付加する。
【０００６】
（ハ）新たに統合された画素に注目して上記の（ロ）の操作を行う。
【０００７】
（ニ）上記の（ロ）及び（ハ）の操作をそれ以上領域が広げられなくなるまで反復する。
【０００８】
（ホ）上記の（イ）に戻って新たな画素を探し、処理を繰り返す。
【０００９】
線画像を均等色領域と線画像とテクスチャ領域に分解して符号化する方法は、特願平１１−４７６５１号（古角、渡辺：「画像符号化方法、復号方法、符号化装置、復号装置、及びそれらの方法を記憶した記憶媒体」）などがある。また、均等色領域を抽出する方法は、特願平１０−３０１８２１号（古角、渡辺：「画像の同色領域抽出方法及びこの方法を記録した記録媒体」）がある。
【００１０】
従来の線画像符号化方法では、ある小領域の輝度及び色差信号の分散や標準偏差などのばらつきを示す指標を求め、該指標がある閾値Ａを下回る時、該小領域を種ブロック、すなわち領域検出の基準ブロックとして決定し、該種ブロックを基準に周りの画素が該種ブロックと同色かどうかを、種ブロック内の輝度と色差信号の平均信号や信号の中央値などの基準信号を求め、該種ブロック基準信号と周りの画素の信号とのばらつき指標を求め、該ばらつき指標をある閾値Ｂで判定し、該ばらつき指標が閾値Ｂを下回る時同色とみなし、同色であれば均等色領域として拡大し、画面全休をいくつかの均等色領域に分割するという処理を１回だけ行っていた。
【００１１】
ここで均等色領域抽出方法について、図面を参照して説明する。なおアルゴリズムは、フローチャートを用いて説明する。
【００１２】
図１５のフローチャートは、均等色領域抽出全体のアルゴリズムである。図１６のフローチャートは、領域８近傍探索アルゴリズムである。
【００１３】
原画像は、それぞれの画素の位置に信号が記憶されているとする。番号領域として、原画像と同じサイズの領域を用意しておき、該番号領域における原画像の画素と同じ位置に抽出された領域の領域番号を書き込んで行く。
【００１４】
探索ブロックは、原画像と番号領域を同時に移動しているものとする。
【００１５】
本従来例の信号は、（Ｙ，Ｃｂ，Ｃｒ）系を用いるが、信号が（Ｒ，Ｇ，Ｂ）系やその他の色空間でも本従来例と同様に行える。また、本従来例では、分散を用いて判定を行っているが、標準偏差など信号のばらつきを示す指標を用いてもよい。また、種ブロックの基準信号に本従来例では、平均値を用いているが、これも中央値、最頻度の値などを基準信号として用いてもよい。
【００１６】
Ｍ番目の領域の領域番号をＮｕｍ（Ｍ）とし、Ｍ番目の領域に対して、その領域に入らない画素には、番号領域にＮｕｍ（Ｍ）に対応する番号として、Ｃｈｋ（Ｍ）をつける。例えば、Ｃｈｋ（Ｍ）＝５００＋Ｎｕｍ（Ｍ）とすると、Ｎｕｍ（Ｍ）＜５００であれば、Ｃｈｋ（Ｍ）はＮｕｍ（Ｍ）に対して一意に決定される。またＮｕｍとは、その時点で番号領域に書き込まれているすべての領域番号のことである。すなわちＮｕｍ（Ｍ）＝ｘのときＮｕｍとは、ｘ，ｘ−１，ｘ−２，…，３，２，１をあらわす。
【００１７】
本従来例では、探索ブロックを図１７、図１８のように左上からラスタスキャンして行く。本従来例で探索ブロックは、８×８の正方形ブロックであるが、探索ブロックの大きさや形は、任意である。例えば４×４ブロックで行っても良いし、ひし形ブロックで行っても良い。
【００１８】
本従来例では、探索ブロックのラスタスキャンは、左上から始まり横に１画素づつ移動し、右端まで行ったら、元に戻り一段下がって再び横に１画素づつ移動して行くが、移動量、方向、動き方も任意である。例えば、８×８ブロックの半分の４画素づつ移動しても良い。
【００１９】
まず、領域番号をＭ＝１とする（ステップ１）。左上を一番端として、図１７のように探索ブロックをとり、探索ブロックが、画像の内部であるかチェックする（ステップ２）。探索ブロックが、画面全部を移動したら、終了である（ステップ３）。次に番号領域での探索ブロック内にＮｕｍがあるかどうかをチェックする（ステップ４）。
【００２０】
もし、Ｎｕｍが存在すれば、探索ブロックは次に移動する（ステップ１１）。存在しなければ、探索ブロック内の信号（Ｙ，Ｃｂ，Ｃｒ）の平均値Ａｖｇ（Ｍ：Ｙ，Ｃｂ，Ｃｒ）を求める（ステップ５）。そして、分散Ｓ（Ｍ）を求める（ステップ６）。該分散Ｓ（Ｍ）がある閾値Ａより大きければ探索ブロックは次に移動する（ステップ７，１１）。もし、該分散Ｓ（Ｍ）が閾値Ａより小さければ、図１９のように番号領域の探索ブロックにＮｕｍ（Ｍ）を書き込み、種ブロックとする（ステップ７，８）。図２０のように種ブロック内の外側の周りを１画素づつ領域８近傍探索アルゴリズムを行う（ステップ９）。本従来例では、図２１のように左上を起点として、上から順にスキャンしていく。
【００２１】
領域８近傍探索アルゴリズムは、本従来例では中心画素の周りを図２２のような順番でスキャンしていく。本従来例では、８近傍で行うが、図２３のように４近傍などで行ってもよい。
【００２２】
まず、図２４のように、Ｎ＝１番目の画素を検索する（ステップ２１）。領域８近傍アルゴリズムは、Ｎ＝９で終了である（ステップ２２，２３）。番号領域のＮ番目の画素がＮｕｍである場合、Ｎ＋１番目の画素に移る（ステップ２４，３１）。また番号領域のＮ番目の画素が、Ｃｈｋ（Ｍ）である場合も、Ｎ＋１番目の画素に移る（ステップ２５，３１）。
【００２３】
図２４のようにＮ＝１番目の画素の（Ｙ，Ｃｂ，Ｃｒ）とＡｖｇ（Ｍ＝Ｙ，Ｃｂ，Ｃｒ）との分散Ｓを求める（ステップ２６）。ここで、Ｓ＞閾値Ｂであれば、図２５のように番号領域のＮ＝１番目の画素にＣｈｋ（Ｍ）を書き込み、Ｎ＋１番目の画素を探索する（ステップ２７，２８，３１）。もしＳ＜閾値Ｂであれば、図２６のように番号領域のＮ＝１番目の画素にＮｕｍ（Ｍ）を書き込み、図２７のようにＮ＝１番目の画素を中心として、新たに領域８近傍探索アルゴリズムを行う（再帰的）（ステップ２７，２９，３０）。新たな領域８近傍探索アルゴリズムが終了したら、現在行っている領域８近傍探索アルゴリズムは、Ｎ＋１番目の画素を探索する（ステップ３１）。
【００２４】
以下に上記領域８ブロック探索アルゴリズムを具体例を使用し説明する。
【００２５】
例１）  図２８では、Ｎ＝１番目の画素は、すでにＣｈｋ（Ｍ）が書き込まれていたので、Ｎ＝２番目の画素に移動した（ステップ２５，３１）。Ｎ＝２，３番目の画素は、すでにＮｕｍ（Ｍ）が書き込まれていたのでＮ＝４番目の画素に移動し（ステップ２４，３１）、Ｎ＝４番目の画素を探索し、Ｓ＜閾値Ｂであったので、図２９のようにＮ＝４番目の画素にＮｕｍ（Ｍ）を書き込み、Ｎ＝４の画素を中心に領域８近傍探索アルゴリズムを行っている所である。
【００２６】
例２）  図３０で、右上のマークは、Ｎｕｍ（Ｍ１）であり、Ｎ＝１，２，３番目の画素のマークは、Ｃｈｋ（Ｍ１）である（ここで、Ｍ１＜Ｍ）。Ｎ＝１番目の画素は、Ｃｈｋ（Ｍ１）≠Ｃｈｋ（Ｍ）であるので、探索を行い（ステップ２５，２６）、Ｓ＞閾値Ｂであったので、Ｃｈｋ（Ｍ）を書き込み、次のＮ＝２番目の画素に移る（ステップ２７，２８，３１）。Ｎ＝２番目の画素もＣｈｋ（Ｍ１）≠Ｃｈｋ（Ｍ）であるので、探索を行い、Ｓ＜閾値Ｂであったので、Ｎ＝２番目の画素にＮｕｍ（Ｍ）を書き込み（ステップ２７，２９）、図３１のようにＮ＝２番目の画素を中心に領域８近傍探索アルゴリズムを開始する（ステップ３０）。新しい領域８近傍探索アルゴリズムにおいて、Ｎ＝１及び２番目の画素は、Ｃｈｋ（Ｍ１）≠Ｃｈｋ（Ｍ）であるので、探索を行い、Ｓ＞閾値Ｂであったので、Ｃｈｋ（Ｍ）を書き込み、次のＮ＝３番目の画素に移った。Ｎ＝３番目の画素は、ＮｕｍであるのでＮ＝４番目の画素に移る（ステップ２４，３１）。Ｎ＝４番目の画素には、Ｃｈｋ（Ｍ）が書き込まれていたので、Ｎ＝５番目の画素に移動した所である（図３２）。
【００２７】
以上のように図２１の種ブロック１番目の画素が終了したら次の画素の領域８ブロック探索アルゴリズムを行い、図２０で示す種ブロック内の外周りすべての画素で領域８ブロック探索アルゴリズムが終了するまで行う。
【００２８】
次に、Ｍに１を加え（ステップ１０）、次の領域の種ブロックを検出する。探索ブロックが探索範囲内をすべてスキャンすれば、均等色領域分割アルゴリズムは終了である（ステップ３）。
【００２９】
【発明が解決しようとする課題】
アニメーション映像やＣＧ画像などでは、背景部は、自然画像と同じようにグラデーションのある画像であり、キャラクタ部は、肌色や服の色などの単色で、ある一定領域をべた塗りしてある映像である。このような画像をオブジェクトに分割する時は、背景部よりキャラクタ部が重要であるが、上記従来の単純領域拡張法では、特徴的なキャラクタ領域だけを抽出するために、初期の領域を１画素単位で始めているため、数画素単位の同色領域まで抽出してしまい、キャラクタ部の同色領域だけを抽出するのが困難であった。また、同色領域の判定が各画素間だけで行われているので、グラデーションがかかっているような信号の変化のなだらかな領域では、複数の領域が抽出されてしまう欠点があった。
【００３０】
また、上記従来の均等色領域抽出方法では、背景にゆるやかな輝度変化がある場合に複雑な形状の均等色領域が輝度変化にあわせて、段階的に抽出されてしまい、テクスチャ領域と判断されず、複雑な形状の符号化に多量の情報量を浪費してしまうという欠点があった。
【００３１】
図３３は、従来の均等色領域抽出方法での欠点を説明する図である。グラデーションのかかった領域の例としてＸ方向の左側ほど暗くなっている雲が示されている。その輝度値の変化を小領域毎にＸ方向に示したグラフが図３３の下側の図である。これをある閾値で均等色領域の抽出を行うと、同じテクスチャ領域である雲の領域が、閾値を越える輝度値の明るい領域（雲の右側）と、閾値以下の輝度値の暗い領域の２つの領域に別れて抽出されてしまう。
【００３２】
本発明の課題は、ゆるやかな輝度変化を持つ背景等の画像部分を、均等色領域として抽出せず、テクスチャ領域として処理できるよう区別することができる均等色領域抽出方法及び装置を提供することである。
【００３３】
【課題を解決するための手段】
上記の課題を解決するため、本発明による均等色領域抽出方法は、一定の領域が同一の色で描かれた画像内の均等色領域を抽出する方法であって、ある一定の大きさの小領域の画像信号からこの小領域の特性を表す統計量を求めステップと、前記小領域の近傍の画素のうち、前記統計量に近い値をもつ画素を均等色領域として順次領域拡大して均等色領域を抽出するステップと、前記統計量を求めるステップと前記均等色領域を抽出するステップとを画像全体に対して行い、該画像全体を１以上の均等色領域に分割するステップと、前記分割して得られた各均等色領域に対して、他の均等色領域との境界に近い画素を起点として、再度均等色領域の再抽出を行うステップと、前記先の均等色領域と前記再抽出の結果得られた均等色領域の一致度をもとに、前記初期の均等色領域あるいは前記再抽出の結果得られた均等色領域を均等色領域とするかテクスチャ領域とするかを判定するステップとを有し、前記判定するステップまでを１回以上繰り返して、均等色領域を抽出することを特徴とする。
【００３４】
あるいは、上記の均等色領域抽出方法において、前記判定するステップでは、先の抽出結果と再抽出の結果を比較し、それぞれの均等色領域を対照付け、各均等色領域において、両者に属する画素数がある閾値を越えたときに、その領域を均等色領域と判断し、該閾値以下であれば、テクスチャ領域と判断することを特徴とする。
【００３５】
あるいは、上記の均等色領域抽出方法において、前記再度均等色領域の再抽出を行うステップでは、既に他の均等色領域に対する再抽出の結果により抽出済みの領域との重複領域がある場合に、その重複領域を除いて均等色領域の再抽出を行うことを特徴とする。
【００３６】
あるいは、上記の均等色領域抽出方法において、前記統計量として、小領域の平均輝度と平均色差信号の一方または両方を用いることを特徴とする。
【００３７】
また、上記の目的を達成するため、本発明の均等色領域抽出装置は、ある一定の大きさの小領域の画像信号からこの小領域の特性を表す統計量を求め、前記小領域の近傍の画素のうち、前記統計量に近い値をもつ画素を均等色領域として順次領域拡大して均等色領域を抽出し、前記統計量を求め、前記均等色領域を抽出することを画像全体に対して行い、該画像全体を１以上の均等色領域に分割する均等色領域抽出手段と、前記抽出された均等色領域を記憶する抽出結果記憶手段と、前記分割して得られた各均等色領域に対して、他の均等色領域との境界に近い画素を起点として、再度均等色領域の再抽出を行う均等色領域再抽出手段と、前記再抽出の結果得られた均等色領域を記憶する再抽出結果記憶手段と、前記記憶された先の均等色領域と再抽出の結果得られた均等色領域の一致度をもとに、前記先の均等色領域あるいは前記再抽出の結果得られた均等色領域を均等色領域とするかテクスチャ領域とするかを判定する判定手段とを、具備することを特徴とする。
【００３８】
あるいは、上記の均等色領域抽出装置において、前記判定手段は、先の抽出結果と再抽出の結果を比較し、それぞれの均等色領域を対照付け、各均等色領域において、両者に属する画素数がある閾値を越えたときに、その領域を均等色領域と判断し、該閾値以下であれば、テクスチャ領域と判断するものであることを特徴とする。
【００３９】
あるいは、上記の均等色領域抽出装置において、前記均等色領域再抽出手段は、既に他の均等色領域に対する再抽出の結果により抽出済みの領域との重複領域がある場合に、その重複領域を除いて均等色領域の再抽出を行うものであることを特徴とする。
【００４０】
あるいは、上記の均等色領域抽出装置において、均等色領域抽出手段及び均等色領域再抽出手段は、統計量として、小領域の平均輝度と平均色差信号の一方または両方を用いるものであることを特徴とする。
【００４１】
なお、上記の均等色領域抽出方法におけるステップをコンピュータに実行させるためのプログラムを、該コンピュータが読み取り可能な記録媒体に記録して、保存したり、配布したり、提供したりすることができる。
【００４２】
本発明では、均等色領域の抽出を、開始点を変えて複数回行い、その結果、複数回とも均等色領域と判断された画素が多い領域を、均等色領域と判定し、そうでない場合にはテクスチャ領域と判定する。均等色領域の抽出を２回行う場合を例に説明すると、１回目と２回目の均等色領域抽出では、基準とする画素や起点が異なるため、なだらかに階調が変化している部分では、均等色領域の形状が１回目と２回目で大きく異なる。そのため、一致度、すなわち重なる画素数が減少し、テクスチャ領域と判定することができる。階調変化のない均等色領域では、１回目と２回目で一致度が高く、ほとんど同一領域が抽出されるため、テクスチャ領域と判定されることなく、均等色領域として処理できる。
【００４３】
【発明の実施の形態】
以下、本発明の実施の形態を図を用いて説明する。
【００４４】
始めに、本発明の原理を説明する。図１は、その原理を説明するためのブロック図である。
【００４５】
本発明では、均等色領域の抽出を、開始点を変えて複数回（以下の説明では２回とする）行い、その結果２回とも均等色領域と判断された画素が多い領域を、均等色領域とする。図７に、本発明での画素の座標の取り方を例示するが、座標の取り方は任意である。
【００４６】
まず、均等色領域初期抽出手段Ｆ１により、小領域毎に統計量、例えば輝度及び色差信号の平均値を求め、画像全体について１回目の均等色領域抽出を行い、抽出された均等色領域を抽出結果記憶手段Ｆ２に記憶しておく。
【００４７】
次に、均等色再抽出手段Ｆ３により、１回目の抽出結果をもとに均等色領域をの面積の大きい順に、該抽出均等色領域内に含まれる小領域で、該小領域内の基準点の（ｘ，ｙ）座標と該抽出均等色領域の種ブロックの基準点の（ｘ，ｙ）座標の距離が最大となる小領域を選び出し、該小領域を新しく種ブロックとして、再び均等色領域を拡大し抽出していく。この処理を１回目の均等色領域抽出で抽出された、該抽出均等色領域の面積の大きい順に、一定個数だけ行う。その後は、画像の右下から（あるいは左上から）画素を走査していき、すでに均等色領域と判定している領域に含まれていなけれぱ、まず小領域を決定し、統計量として例えば輝度及び色差信号の平均値を計算し、それをもとに２回目の均等色領域抽出を続けて行う。２回目の均等色領域の抽出結果は、再抽出結果記憶手段Ｆ４に記憶しておく。
【００４８】
次に、判定手段Ｆ５により、２回目の均等色領域の抽出が終了した時点で、抽出結果記憶手段Ｆ２に記憶された１回目の抽出結果を元に、均等色領域かテクスチャ領域かの判定を行う。１回目の抽出結果のうち、面積の大きい順に、再抽出結果記憶手段Ｆ４に記憶された２回目の均等色領域と重ね合わせ、１回目のある均等色領域に重なった２回目の均等色領域のうち、１回目の均等色領域と重なった画素数を２回目に抽出した均等色領域それぞれについて数える。重なった画素数が一番多い画素数がある閾値を超えるとき、対応する１回目の均等色領域を均等色領域と判定し、該閾値以下のときには、対応する１回目の均等色領域をテクスチャ領域と判定する。
【００４９】
ここでは、１回目に抽出した均等色領域を基準として、判定を行う手法を示したが、逆に２回目に抽出した均等色領域を基準として判定を行うこともできる。また、さらに新しい種ブロックを決定し、３回、４回と複数回、均等色領域を抽出し、画素の重なりを元に均等色領域かテクスチャ領域かの判定を行ってもよい。ただし、抽出の回数が多くなるほど処理時間が長くなってしまう。また、重なり画素数がある閾値を越えなければテクスチャ領域とする手法を示したが、重なり画素数と元の均等色領域の画素数との比率に対して、閾値を設定することもできる。
【００５０】
この手法は、ハードウェアあるいはコンピュータ上で稼働するプログラムで実現される。
【００５１】
本発明の手法を用いれば、１回目と２回目の均等色領域抽出では、基準とする種ブロックの場所が異なるため、なだらかに階調が変化している部分では、種ブロック内の平均輝度値や平均色差信号値などの基準信号が異なってくるので、均等色領域の形状が１回目と２回目で大きく異なる。そのため、重なる画素数が減少し、テクスチャ領域と判定することができる。階調変化のない均等色領域では、１回目と２回目で、ほとんど同一領域が抽出されるため、テクスチャ領域と判定されることなく、均等色領域として処理できる。
【００５２】
次に、本発明が適用される画像符号化装置について説明する。図２は、本発明が適用される一例を示す画像符号化装置のブロック図である。
【００５３】
本画像符号化装置は、領域抽出器Ａ１０１と画像符号化器Ａ１０２から構成され、領域抽出器Ａ１０１の領域抽出部Ａ２により入力画像Ａ１内から複数の領域を抽出した抽出領域Ａ３と抽出外領域Ａ４に対し、画像符号化器Ａ１０２により、符号化を行なうものである。本発明は、領域抽出器Ａ１０１に適用するものである。
【００５４】
画像符号化器Ａ１０２においては、まず、領域面積検出部Ａ５により、該抽出領域Ａ３のそれぞれの面積を求め、領域面積保存メモリＡ７に記憶しておく。次に、領域面積分並べ替え処理部Ａ９により、領域面積保存メモリＡ７に記憶された面積データＡ８を面積の大きな順に並べ替える。次に、符号化対象判定部Ａ１１により、面積順並べ替え領域Ａ１０の上位Ｎ個の抽出領域を符号化対象領域と決定し、該Ｎ個を除いた残り領域を符号化対象外領域と決定する。符号化対象領域Ａ１２は、領域画像符号化部Ａ１５により、形状と領域内信号の代表値を用いた第１の符号化方式を適用して符号化されて、領域画像符号化データＡ１８として出力される。一方、該符号化対象外領域Ａ１３は、抽出外領域合成部Ａ１４により、領域抽出部Ａ２からの抽出外領域Ａ４と合成される。合成された合成抽出外領域Ａ１６は、合成抽出外領域符号化部Ａ１７により、第１の符号化方式とは異なった第２の符号化方式を用いて符号化されて、合成抽出外領域符号化データＡ１９として出力される。
【００５５】
図３は、本発明の均等色領域複数回抽出装置の一実施形態例を示すブロック図であり、図４は、上記均等色領域複数回抽出装置の動作例とともに、本発明の均等色領域複数回抽出方法の一実施形態例を示すフローチャートである。
【００５６】
入力画像Ｐ１は、１回目均等色領域抽出部Ｐ２において、１回目の均等色領域抽出を行う（ステップ５１）。１回目均等色領域抽出部Ｐ２で抽出された１回目抽出均等色領域Ｐ３は、１回目抽出均等色領域イメージバッファＰ６に送られる。また、１回目均等色領域抽出部Ｐ２で均等色領域抽出時に検出された種ブロックの基準点の座標や、輝度、色差信号の平均値などの種ブロックデータＰ４は、種ブロックデータ保存部Ｐ５に送られる。
【００５７】
２回目均等色領域抽出制御部Ｐ１１では、１回目抽出均等色領域イメージバッファＰ６を参照して、該１回目抽出均等色領域の総数を求め、それをＲとする（ステップ５２）。次に該１回目抽出均等色領域のそれぞれの面積を求め、面積の大きい順に番号付け（１，２，…，Ｒ）をしていく。ここで、面積がＭ番目の該１回目抽出均等色領域をＲｅｇ１（Ｍ）とする（Ｍ＝１，２，…，Ｒ）（ステップ５３）。これらのデータを１回目抽出均等色領域データＰ８とする。２回目均等色領域抽出制御部Ｐ１１は、該１回目抽出均等色領域内で面積が一番大きいＭ＝１（ステップ５４）より順番に新種ブロック探索部Ｐ１３へ、２回目均等色領域抽出制御データＰ１２として、並べ替えをする前のＲｅｇ１（Ｍ）の情報を送信する。
【００５８】
新種ブロック探索部Ｐ１３では、２回目均等色領域抽出制御データＰ１２により得られたＭに対し、１回目抽出均等色領域イメージバッファＰ６よりＭに対応したＲｅｇ１（Ｍ）Ｐ９を取得する。また、種ブロックデータ保存部Ｐ５より、Ｍに対応した種ブロックデータＰ７を取得し、新種ブロック検出アルゴリズムを行う（ステップ５７）。本実施形態例では、探索ブロックを図８の様な形状と考えるが、探索ブロックの大きさ形状は任意である。また、本実施形態例での新種ブロック検出アルゴリズムでの探索ブロックを１回目の均等色領域抽出時と同じ探索ブロック（図８）を用いているが、１回目の均等色領域抽出時とは、大きさや形状の違う探索ブロックを使用してもよい。
【００５９】
図５は、新種ブロック検出アルゴリズムを示すフローチャートである。
【００６０】
まず、探索ブロックが完全に内部に入る長方形を作成する（図９）（ステップ７１）。該長方形を用いて、Ｒｅｇ１（Ｍ）を図１０のように分割する（ステップ７２）。ここで、長方形で分割するのは処理を簡単にする（処理量の削減）ためであり、必須ではない。Ｒｅｇ１（Ｍ）を分割した該長方形で、該長方形内の画素全てが、Ｒｅｇ１（Ｍ）に含まれるもののみを抽出し、左上から順に、ＮＥＷ（Ｍ，１）、ＮＥＷ（Ｍ，２），…，ＮＥＷ（Ｍ，Ｌ），…，ＮＥＷ（Ｍ，ｅｎｄＬ）とする（図１１太線内部）（ステップ７３）。
【００６１】
本実施形態例では、図１０の左上の部分に１回目の均等色領域抽出時の種ブロックが存在したとする。図８のように該種ブロック内に基準点Ｐ（０）をきめ、図８での基準点Ｐ（０）の座標を（Ｘ（０）、Ｙ（０））とする。各長方形内にも同様の位置に基準点Ｐ（Ｌ）を取り、図９でのＮＥＷ（Ｍ，Ｌ）の基準点の座標を（Ｘ（Ｌ），Ｙ（Ｌ））とする。そして、Ｄ（Ｌ）をＰ（０）とＰ（Ｌ）との距離とする。Ｄ（Ｌ）の求め方は、
Ｄ（Ｌ）＝｜Ｘ（０）−Ｘ（Ｌ））｜＋｜Ｙ（０）−Ｙ（Ｌ）｜
や、
Ｄ（Ｌ）＝（（Ｘ（０）−Ｘ（Ｌ））＾２＋（Ｙ（０）−Ｙ（Ｌ））＾２）＾（１／２）
などがあるが、Ｄ（Ｌ）の求め方は任意である。なお、本実施形態例では、
Ｄ（Ｌ）＝（（Ｘ（０）−Ｘ（Ｌ））＾２＋（Ｙ（０）−Ｙ（Ｌ））＾２）＾（１／２）
を用いる。Ｄ（Ｌ）が最大となるＮＥＷ（Ｍ，ｍａｘＬ）を検出し（図１１）（ステップ７４）、ＮＥＷ（Ｍ，ｍａｘＬ）内の探索ブロックを新種ブロックとする（図１２）（ステップ７５）。
【００６２】
また、別の実施形態例として、上記で求めた探索ブロックを該探索ブロック内の全ての画素が、Ｒｅｇ１（Ｍ）の領域内である限り、Ｘ座標、Ｙ座標が増加する方向に平行移動していき、移動できなくなった所を新種ブロックとしてもよい。
【００６３】
以上の様に検出された新種ブロックデータＰ１４を２回目均等色領域抽出部Ｐ１５に送信する。また、図１３の様にＲｅｇ１（Ｍ）内に２回目の均等色領域として抽出された領域が存在する場合には、均等色領域の重なりを回避するため図１４の様に該２回目抽出均等色領域に入らない長方形を抽出し、新種ブロックは、すでに抽出された該２回目抽出均等色領域内に入らないようにする。
【００６４】
２回目均等色領域抽出部Ｐ１５では、新種ブロックデータＰ１４と入力画像Ｐ１を参照し、新種ブロック内の画素の（Ｙ，Ｃｂ，Ｃｒ）の平均Ａｖｇ（Ｒｅｇ１（Ｍ）：Ｙ，Ｃｂ，Ｃｒ）を求め、それを元にして領域８近傍探索アルゴリズムを行う（ステップ５８）。２回目均等色領域抽出部Ｐ１５は、領域８近傍探索アルゴリズムが終了したら、２回目均等色領域抽出制御部Ｐ１１に２回目均等色領域抽出制御データＰ１７を送信する。
【００６５】
２回目均等色領域抽出制御部Ｐ１１は、Ｍに１加えて、次の領域を探索するよう２回目均等色領域抽出制御データＰ１２を送信する。（ステップ５９）。新種ブロック探索アルゴリズムは、Ｒｅｇ１（Ｍ）の個数Ｒ回繰返すが（ステップ５６）、探索する領域の個数を予めＣ個と設定しておき、Ｃ個の領域で新種ブロックを検出したら、残りの領域に対しては、右下よりラスタースキャンしていき、均等色領域抽出アルゴリズムを行う（ステップ５５，６０）。そして、２回目均等色領域抽出部Ｐ１５により２回目の均等色領域抽出で抽出された領域をＲｅｇ２（Ｎ）とする。この様に抽出された２回目抽出均等色領域Ｐ１６は、２回目抽出均等色領域イメージバッファＰ１８に送信される。
【００６６】
均等色領域・テクスチャ領域判定部Ｐ２０は、１回目抽出均等色領域イメージバッファＰ６と２回目抽出均等色領域イメージバッファＰ１８を参照し、１回目抽出均等色領域が均等色領域か、テクスチャ領域かを判定し、均等色領域ならば、出力均等色領域Ｐ２１として出力する（ステップ６１）。この時の均等色領域・テクスチャ領域判定のアルゴリズムは、以下のとおりである。
【００６７】
図６に、均等色領域・テクスチャ領域判定アルゴリズムのフローチャートを示す。
【００６８】
まず、Ｍ＝１（ステップ８１）とし、Ｒｅｇ１（Ｍ）と重なる画素を含むＲｅｇ２（Ｎ）の領域を抽出する（ステップ８３）。該Ｒｅｇ２（Ｎ）の領域それぞれに対して、Ｒｅｇ１（Ｍ）と重なっている画素数を計算し、該画素数の最大値をＭＡＸ（Ｍ）とする（ステップ８４）。該ＭＡＸ（Ｍ）がある閾値Ｃｏｎｓｔより大きい場合Ｒｅｇ１（Ｍ）を均等色領域とし（ステップ８５，８６）、小さい場合は、テクスチャ領域とする（ステップ８７）。そして、Ｍに１加えて（ステップ８８）、再びＲｅｇ１（Ｍ）と重なる画素を含むＲｅｇ２（Ｎ）の領域を抽出する。ここでＭが１回目で抽出された均等色領域より大きくなったら（ステップ８２）、終了する（ステップ６２）。
【００６９】
なお、図１、図３で示した装置各部の一部もしくは全部の機能を、コンピュータを用いて実現することができること、あるいは、図４、図５、図６で示した処理手順をコンピュータに実行させることができることは言うまでもなく、コンピュータでその各部の機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記憶媒体、例えば、ＦＤ（フロッピーディスク）や、ＭＯ、ＲＯＭ、各種メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録し、提供し、配布することが可能である。
【００７０】
【発明の効果】
本発明を用いれば、背景等の画像部分にゆるやかな輝度変化がある場合にも、段階的な均等色領域としてではなく、テクスチャ領域として判断して処理するために、領域形状の離散コサイン変換などの符号化手法を適用して効率良く符号化することができる。
【図面の簡単な説明】
【図１】本発明の原理を説明するためのブロック図である。
【図２】本発明の適用例を示す画像符号化装置のブロック図である。
【図３】本発明の一実施形態例である均等色領域複数回抽出装置のブロック図である。
【図４】本発明の一実施形態例である均等色領域抽出方法を示す均等色領域複数回抽出アルゴリズムのフローチャートである。
【図５】上記均等色領域複数回抽出アルゴリズムにおける新種ブロック検出アルゴリズムを示すフローチャートである。
【図６】上記均等色領域複数回抽出アルゴリズムにおける均等色領域・テクスチャ領域判定アルゴリズムを示すフローチャートである。
【図７】本発明での座標の取り方の一例を示す図である。
【図８】上記実施形態例における種ブロック及び種ブロック内基準点を示す図である。
【図９】上記実施形態例における種ブロックを完全に含む長方形を示す図である。
【図１０】上記実施形態例において、図９の長方形で分割した１回目均等色領域を示す図である。
【図１１】上記実施形態例において、図１０の分割した長方形内の画素全てが１回目均等色領域に含まれるもののみを抽出する様子を示す図である。
【図１２】上記実施形態例における新種ブロックを探索する様子を説明する図である。
【図１３】上記実施形態例において、１回目の均等色領域内に２回目の均等色領域として抽出された領域が存在する例を示す図である。
【図１４】上記実施形態例において、２回目抽出均等色領域に入らない長方形を抽出し、新種ブロックが既に抽出された２回目抽出均等色領域内に入らないよう新種ブロックを探索する様子を説明する図である。
【図１５】均等色領域抽出アルゴリズムのフローチャートである。
【図１６】領域８近傍探索アルゴリズムのフローチャートである。
【図１７】探索ブロックを左上からラスタースキャンして行く様子を説明する図（その１）である。
【図１８】探索ブロックを左上からラスタースキャンして行く様子を説明する図（その２）である。
【図１９】探索ブロックにＮｕｍ（Ｍ）を書き込み、種ブロックとする様子を説明する図である。
【図２０】種ブロック内で領域８近傍探索アルゴリズムを行う範囲を表す図である。
【図２１】領域８近傍探索アルゴリズムの開始位置を示した図である。
【図２２】領域８近傍の探索順を示した図である。
【図２３】領域４近傍の探索順を示した図である。
【図２４】領域８近傍探索において、１番目の画素を探索する様子を説明する図である。
【図２５】領域８近傍探索において、１番目の画素にＣｈｋ（Ｍ）を書き込み、２番目の画素を探索する様子を説明する図である。
【図２６】領域８近傍探索において、１番目の画素にＮｕｍ（Ｍ）を書き込んだ場合を示した図である。
【図２７】１番目の画素にＮｕｍ（Ｍ）が書き込まれている場合に、その１番目の画素を中心として、新たに領域８近傍探索アルゴリズムを行う様子を説明する図である。
【図２８】
領域８近傍探索アルゴリズムの具体例１を説明する図（その１）である。
【図２９】
領域８近傍探索アルゴリズムの具体例１を説明する図（その２）である。
【図３０】
領域８近傍探索アルゴリズムの具体例２を説明する図（その１）である。
【図３１】
領域８近傍探索アルゴリズムの具体例２を説明する図（その２）である。
【図３２】
領域８近傍探索アルゴリズムの具体例２を説明する図（その３）である。
【図３３】
従来の均等色領域抽出方法での欠点を説明する図である。
【符号の説明】
１〜１１…同色領域抽出アルゴリズムのフローチャートのステップ
２１〜３１…領域８近傍探索アルゴリズムのフローチャートのステップ
５１〜６２…均等色領域複数回抽出アルゴリズムのフローチャートのステップ
７１〜７５…新種ブロック検出アルゴリズムのフローチャートのステップ
８１〜８８…均等色領域・テクスチャ領域判定アルゴリズムのフローチャートのステップ
Ｆ１…均等色領域抽出手段
Ｆ２…抽出結果記憶手段
Ｆ３…均等色領域再抽出手段
Ｆ４…再抽出結果記憶手段
Ｆ５…判定手段
Ｐ１…入力画像
Ｐ２…１回目均等色領域抽出部
Ｐ３…１回目抽出均等色領域
Ｐ４…種ブロックデータ
Ｐ５…種ブロックデータ保存部
Ｐ６…１回目抽出均等色領域イメージバッファ
Ｐ７…種ブロックデータ
Ｐ８…１回目抽出均等色領域データ
Ｐ９…１回目抽出均等色領域
Ｐ１０…１回目抽出均等色領域判定データ
Ｐ１１…２回日均等色領域抽出制御部
Ｐ１２…２回目抽出均等色領域制御データ
Ｐ１３…新種ブロック探索部
Ｐ１４…新種ブロックデータ
Ｐ１５…２回目均等色領域抽出部
Ｐ１６…２回目抽出均等色領域
Ｐ１７…２回目均等色領域抽出制御データ
Ｐ１８…２回目抽出均等色領域イメージバッファ
Ｐ１９…２回目抽出均等色領域判定データ
Ｐ２０…均等色領域・テクスチャ領域判定部
Ｐ２１…出力均等色領域
【図１】
0003578947.tif 000002
【図２】
0003578947.tif 000003
【図３】
0003578947.tif 000004
【図４】
0003578947.tif 000005
【図５】
0003578947.tif 000006
【図６】
0003578947.tif 000007
【図７】
0003578947.tif 000008
【図８】
0003578947.tif 000009
【図９】
0003578947.tif 000010
【図１０】
0003578947.tif 000011
【図１１】
0003578947.tif 000012
【図１２】
0003578947.tif 000013
【図１３】
0003578947.tif 000014
【図１４】
0003578947.tif 000015
【図１５】
0003578947.tif 000016
【図１６】
0003578947.tif 000017
【図１７】
0003578947.tif 000018
【図１８】
0003578947.tif 000019
【図１９】
0003578947.tif 000020
【図２０】
0003578947.tif 000021
【図２１】
0003578947.tif 000022
【図２２】
0003578947.tif 000023
【図２３】
0003578947.tif 000024
【図２４】
0003578947.tif 000025
【図２５】
0003578947.tif 000026
【図２６】
0003578947.tif 000027
【図２７】
0003578947.tif 000028
【図２８】
0003578947.tif 000029
【図２９】
0003578947.tif 000030
【図３０】
0003578947.tif 000031
【図３１】
0003578947.tif 000032
【図３２】
0003578947.tif 000033
【図３３】
0003578947.tif 000034