(57)【要約】      （修正有）【課題】画像内における自己相似領域の探索において、演算量を抑えつつ自己相似性の強い領域を検出する。【解決手段】探索部３０は、画像内において正方形状の対象領域と、探索領域との対応画素間の差分値をもとに対象領域の自己相似領域を探索する。変形部２０は、対象領域または探索領域を回転させる。変形部２０は、所定の回転角度で対象領域または探索領域を回転させる。探索部３０は、回転後における対象領域内の画素と探索領域内の画素とを対応させ、対象領域内に存在しない探索領域内の画素を演算対象から除外する。【選択図】図５
2017059026.tif 000002
【特許請求の範囲】
【請求項１】
画像内において正方形状の対象領域と、探索領域との対応画素間の差分値をもとに前記対象領域の自己相似領域を探索する探索部と、
前記対象領域または前記探索領域を回転させる変形部と、を備え、
前記変形部は、所定の回転角度で前記対象領域または前記探索領域を回転させ、
前記探索部は、回転後における前記対象領域内の画素と前記探索領域内の画素とを対応させ、前記対象領域内に存在しない前記探索領域内の画素を演算対象から除外することを特徴とする画像処理装置。
【請求項２】
前記所定の回転角度は、ｔａｎθ＝Ａ／Ｂ（Ａ及びＢは整数）を満たす回転角度θであることを特徴とする請求項１に記載の画像処理装置。
【請求項３】
画像内において正方形状の対象領域と、探索領域との対応画素間の差分値をもとに前記対象領域の自己相似領域を探索する探索ステップと、
前記対象領域または前記探索領域を回転させる変形ステップと、を備え、
前記変形ステップは、所定の回転角度で前記対象領域または前記探索領域を回転させ、
前記探索ステップは、回転後における前記対象領域内の画素と前記探索領域内の画素とを対応させ、前記対象領域内に存在しない前記探索領域内の画素を演算対象から除外することを特徴とする画像処理方法。
【請求項４】
画像内において正方形状の対象領域と、探索領域との対応画素間の差分値をもとに前記対象領域の自己相似領域を探索する探索処理と、
前記対象領域または前記探索領域を回転させる変形処理と、をコンピュータに実行させ、
前記変形処理は、所定の回転角度で前記対象領域または前記探索領域を回転させ、
前記探索処理は、回転後における前記対象領域内の画素と前記探索領域内の画素とを対応させ、前記対象領域内に存在しない前記探索領域内の画素を演算対象から除外することを特徴とする画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像のフラクタル自己相似性を利用して、対象領域と自己相似性の高い領域を画像内で探索する画像処理装置、画像処理方法、及び画像処理プログラムに関する。
【背景技術】
【０００２】
一般的に自然画には、ある画像領域と、ほぼ合同もしくは相似関係にある画像領域が存在することが知られている。このような自己相似性を利用した画像処理に、フラクタル符号化や画像拡大がある。
【０００３】
画像内における自己相似領域の探索は一般的に次のように行われる。画像内に対象とする領域（テンプレート領域）を設定し、テンプレート領域を回転、拡大、縮小、反転など変形しながら、テンプレート領域と探索範囲内の特定の画素領域（探索領域）とのマッチング処理を行う。一般的なマッチング処理は、テンプレート領域と探索領域との間で対応する画素間の輝度値などの差分を算出し、当該差分の絶対値もしくは二乗値の総和を評価関数とする。この評価関数が最小となる探索領域を自己相似領域として選択する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−３５７３９９号公報
【特許文献２】特開平７−７５１０４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
テンプレート領域の形状には、二次元画素配列からの切り出しが容易である正方形状が用いられることが多い。正方形状の場合、マッチング時の回転処理の際、９０度単位の回転以外は、テンプレート領域内の画素位置と探索領域内の画素位置にずれが発生するため、対応画素間の差分の計算が困難になる（図１参照）。
【０００６】
従来の自己相似領域の探索では、回転変形は９０度単位でのみ行っていた。しかしながら自然画の自己相似性は、９０度単位の回転に限定されている訳ではないため、この限定処理により、自己相似性の強い領域が探索対象から外れる可能性がある。結果として、本来期待できる符号化効率および画質を実現できない場合が発生していた。
【０００７】
９０度単位以外でテンプレート領域を回転させ、テンプレート領域に対してアフィン変換などの幾何変形を施して、テンプレート領域内の画素位置と探索領域内の画素位置とを対応させることも考えられる。しかしながらこの場合、アフィン変換などの幾何変形を行う必要があるため演算量が増大する。
【０００８】
本発明はこうした状況に鑑みてなされたものであり、効率よく自己相似性の強い領域を検出する技術を提供することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明のある態様の画像処理装置（１）は、画像内において正方形状の対象領域と、探索領域との対応画素間の差分値をもとに対象領域の自己相似領域を探索する探索部（３０）と、対象領域または探索領域を回転させる変形部（２０）と、を備える。変形部（２０）は、所定の回転角度で対象領域または探索領域を回転させ、探索部（３０）は、回転後における対象領域内の画素と探索領域内の画素とを対応させ、対象領域内に存在しない探索領域内の画素を演算対象から除外する。
【００１０】
本発明の別の態様は、画像処理方法である。この方法は、画像内において正方形状の対象領域と、探索領域との対応画素間の差分値をもとに対象領域の自己相似領域を探索する探索ステップと、対象領域または探索領域を回転させる変形ステップと、を備える。変形ステップは、所定の回転角度で対象領域または探索領域を回転させ、探索ステップは、回転後における対象領域内の画素と探索領域内の画素とを対応させ、対象領域内に存在しない探索領域内の画素を演算対象から除外する。
【００１１】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１２】
本発明によれば、効率よく自己相似性の強い領域を検出できる。
【図面の簡単な説明】
【００１３】
【図１】テンプレート領域の回転処理時の画素位置を説明するための図である。
【図２】自己相似性を持つドメインブロックの探索処理を説明するための図である。
【図３】図３（ａ）−（ｉ）は、８種類の等長変換ε(・)を表した図である。
【図４】レンジブロックを時計回りに０度、４５度、９０度、回転処理する場合の画素位置を説明するための図である。
【図５】本発明の実施の形態に係る画像処理装置の構成を示すブロック図である。
【図６】本発明の実施の形態に係る回転処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１４】
画像内における自己相似性を利用した画像処理としてフラクタル符号化がある。以下、本発明の実施の形態ではフラクタル符号化を例に説明する。なお本発明の実施の形態は、正方形状のテンプレートを用いた自己相似領域の探索の回転変形処理一般に適用できるものであり、フラクタル符号化に限定されるものではない。
【００１５】
図１は、テンプレート領域Ｒ１の回転処理時の画素位置を説明するための図である。図１には、３×３＝９画素で構成される正方形状のテンプレート領域Ｒ１（左側参照）を、時計回りに９０度回転させた場合のテンプレート領域Ｒ１ａ（右上側参照）と、反時計回りに３０度回転させた場合のテンプレート領域Ｒ１ｂ（右下側参照）を描いている。時計回りに９０度回転させた場合、回転前後におけるテンプレート領域Ｒ１内の全ての画素位置が探索領域内の画素位置と合致する。回転前の左上頂点画素Ｐ１は回転後は右上頂点画素となり、探索領域内の画素と合致する。
【００１６】
一方、反時計回りに３０度回転させた場合、回転前後におけるテンプレート領域Ｒ１内の画素位置が合致しない。回転前の左上頂点画素Ｐ１は回転後は、探索領域内の画素と合致しない画素となる。このように画素位置が合致しない場合、画素間の差分を算出してテンプレート領域Ｒ１と探索領域との一致度を評価することが難しくなる。以下、この課題を解決する手法を説明する。
【００１７】
まず、一般的な反復関数系を用いたフラクタル符号化アルゴリズムについて説明する。フラクタル符号化とは、上述の通り、自然画はほぼ合同もしくは相似関係にある画像領域が存在しており、画像内のある一部分は、別の一部分を縮小することによって近似できるので、この性質を利用して、画像を分割し、各部分毎に最適な近似を与える縮小変換をもとめ、その変換パラメータを符号とする手法である。
【００１８】
フラクタル符号化は、画像f(x,y)（0≦x≦Xmax，0≦y≦Ymax）を重なり合いの無い複数のレンジブロックRij（i、jは、図２の通り、画像f上のｘ軸方向とｙ軸方向におけるレンジブロックの位置を表す）に分割し、各レンジブロックRijのサイズより大きなドメインブロックDkl（k、lは、図２の通り、画像f上のｘ軸方向とｙ軸方向におけるドメインブロック端の位置を表す）を探索し、最適な近似を与える変換λij(・)を求めることにより行われる。
【００１９】
図２は、自己相似性を持つドメインブロックの探索処理を説明するための図である。左側の入力画像f(x,y)にはレンジブロックRijが示されており、右側の入力画像f(x,y)にはドメインブロックDklが示されている。対象のレンジブロックRijに対する複数のドメインブロックDklの候補の中から、当該レンジブロックRijと最も自己相似性が高いドメインブロックDklを特定する。
【００２０】
このときすべてのレンジブロックに対してドメインブロックDklの探索を行うと効率が悪い。レンジブロックRijにおいて輝度値などの変化が少なく平坦である場合、そのブロックは平均値のみで十分に近似できるため、シェードブロックとして判別される。このとき、ドメインブロックDklの探索は行わず、レンジブロックRijの平均値Raveとブロック判別ビットτijのみを符号データとして用いる。これにより、ビットレートと探索時間が削減される。シェードブロックを判別するため、レンジブロックRijの分散σ2を用いる。分散σ2が予め設定した閾値未満のブロックはシェードブロックと判別され、閾値以上のブロックはエッジブロックとして判別される。
【００２１】
エッジブロックに対しては、ドメインブロックDklと変換λij(・)の最適な組み合わせが総当り的に探索される。本実施の形態では、レンジブロックRijがテンプレート領域、ドメインブロックDklが探索領域に対応する。
【００２２】
レンジブロックRij及びドメインブロックDklに施される変換λij(・)は下記（式１）、（式２）のように記述される。
R’ij(m,n)=Rij(m,n)-Rave  …（式１）
まず、レンジブロックRijから直流成分（例えば輝度値の平均値）Raveを分離し、直流成分Raveを除くレンジブロックR’ijを作成する。なお、ｍ、ｎはレンジブロックの画素数を表しており、レンジブロック上のｘ軸方向とｙ軸方向におけるそれぞれの画素の位置を表している。
【００２３】
D’kl(m,n)=ε(s(Dkl(m’,n’))-Dave)  …（式２）
次にドメインブロックDklを抽出し、対応する画素値の算術平均化を行って縮小変換s(・)する。更に、レンジブロックRijと同様に直流成分（例えば輝度値の平均値）Daveを分離し、等長変換ε(・)を施す。ここで縮小変換は、例えば、ドメインブロックをレンジブロックと同じ大きさに縮小する変換である。なお、m’、n’はドメインブロックの画素数を表しており、ドメインブロック上のｘ軸方向とｙ軸方向におけるそれぞれの画素の位置を表している。
【００２４】
等長変換ε(・)は以下の通常８種類が用いられる。図３（ａ）−（ｉ）は、８種類の等長変換ε(・)を図で表したものである。図３（ａ）−（ｉ）のそれぞれは、下記１）−８）の各変換に対応する。
１）恒等変換
２）時計回りに９０度回転
３）時計回りに１８０度回転
４）時計回りに２７０度回転
５）図３（ｆ）で示す対角線に対する反射
６）図３（ｇ）で示す対角線に対する反射
７）水平軸に対する反射
８）垂直軸に対する反射
【００２５】
R’ij(m,n)≒D”kl(m,n)=α・D’kl(m,n)  …(式３)
最後に、グレイレベルのスケーリングαを施す。このとき、スケーリング係数αは上記（式３）の関係となるように最小二乗法（下記（式４）参照）により求められる。
α＝（ΣR’ij(m,n)・D’kl(m,n)）／（Σ(D’kl(m,n))2）  …(式４）
【００２６】
以上の操作を、ドメインブロックDklと変換λij(・)について総当り的に繰り返し、直流成分が除かれたレンジブロックR’ijと、変換されたドメインブロックD”kl間の平均二乗誤差が最も低くなるドメインブロックDklと変換λij(・)の組み合わせを求める。対象のレンジブロックRijの符号化データとして、変換パラメータ、ブロック判別ビットτij、平均値Rave、ドメインブロックの位置(k,l)、等長変換ε、スケーリング係数αが最終的に符号化される。以上が、フラクタル符号化アルゴリズムの概略である。
【００２７】
以下、本発明の実施の形態の概略を説明する。まず前提としてレンジブロックRijを、m×n=16(m=4,n=4)画素を持つ正方形状のテンプレート領域に設定する。フラクタル符号化では、ドメインブロックDklに上記（式２）のような縮小変換s(・)および等長変換ε(・)を施し、変換後のドメインブロックD’kl(m,n)と、レンジブロックRij間の平均二乗誤差（ＭＳＥ）を算出する。平均二乗誤差は各画素間の誤差の二乗を累積し、画素数で割った値である。なお平均二乗誤差（ＭＳＥ）の代わりに、平均絶対誤差（ＭＡＥ）を使用してもよい。
【００２８】
本実施の形態では回転に関する処理に注目するため等長変換εの内、回転のみを説明する。本実施の形態ではドメインブロックではなく、レンジブロックを回転する例を説明する。
【００２９】
図４は、レンジブロックＲ１を時計回りに０度、４５度、９０度、回転処理する場合の画素位置を説明するための図である。０度、９０度の回転の場合、レンジブロックＲ１とドメインブロックＤ１、Ｄ３との間で全ての画素位置が合致する。従って両ブロック間の平均二乗誤差の算出において全画素が演算対象となる。一方、４５度回転の場合、ドメインブロックＤ２内の黒色の画素は画素位置が合致するために対応画素が存在しているが、ドメインブロックＤ２内の白色の画素はレンジブロック側に対応画素が存在しない。そこで、両ブロック間の平均二乗誤差の算出において、ドメインブロックＤ２内の非対応画素を演算対象から除外する。
【００３０】
その理由としては次の通りである。対応画素が存在しない場合、対応画素が存在するように画素位置変換を行うことが考えられるが、演算量が増加する。一方で、４５度回転のレンジブロックは、本来のサイズの√２倍(面積比２倍）になっている。この４５度回転探索は、レンジブロックのサイズが変わってしまうため合同領域の探索ではなくなる。合同領域の探索を実現するには厳格な等長変換を施して、ドメインブロック側の画素を1/√2間隔に変換する必要がある。しかし、フラクタル符号化では自己相似性探索を前提としているため、相似が確保されれば探索の対象にできる。本実施の形態では以上の性質を利用して、この例の４５度回転探索では、画素位置変換を行わず、平均二乗誤差の算出において対応画素が存在する画素のみを演算対象とする。これにより演算量を増大させずに、９０度単位以外の回転探索が可能となる。即ち４５度回転の場合も９０度回転の場合と同様に、１６画素の誤差（差分値）を基礎とした演算処理になる。
【００３１】
４５度回転以外でも、tanθ=A/B(AとBは整数）を満たす角度θの回転であれば、テンプレートの全画素に合致する画素位置を持つ相似形状領域が探索領域内に存在することになるため、同様の手法で回転変換が可能である。例えば２６．５６（tanθ＝1/2）度回転させてもよい。またＡとＢを負の整数まで拡張することで、９０度以上の回転角度θへの拡張も可能である。即ち回転角度θを、直角三角形の底辺と高さの両方を整数としたときの底辺と斜辺間の角度に限定する。これにより、変形後のテンプレート内の全画素が探索領域内の画素位置に合致する。更に、テンプレート側に対応画素が存在しない探索領域内の画素は、平均二乗誤差の算出において存在しないものとして扱う。但し、AとBは整数としたが、AかBが０の場合、もしくは両方とも０の場合は、回転角が９０度の倍数に相当するため、従来の９０度回転の探索手法を用いる。
【００３２】
図５は、本発明の実施の形態に係る画像処理装置１の構成を示すブロック図である。画像処理装置１は領域設定部１０、変形部２０、探索部３０、符号化部４０を備える。探索部３０は誤差算出部３１及び評価部３２を含む。これらの構成はハードウェア資源とソフトウェア資源の協働、又はハードウェア資源のみにより実現できる。ハードウェア資源としてプロセッサ、ＲＯＭ、ＲＡＭ、その他のＬＳＩを利用できる。ソフトウェア資源としてオペレーティングシステム、アプリケーション等のプログラムを利用できる。
【００３３】
領域設定部１０は、入力された原画像内において正方形状の対象領域（上記のテンプレート領域に相当する）を設定する。また領域設定部１０は当該画像内において、当該対象領域に対する探索領域の候補を設定する。変形部２０は当該対象領域を変形させる。本実施の形態では当該対象領域を回転させる処理に注目する。変形部２０は、tanθ=A/B(AとBは整数）を満たす回転角度θで当該対象領域を回転させる。
【００３４】
探索部３０は、設定された対象領域と探索領域との対応画素間の差分値をもとに当該対象領域の自己相似領域を探索する。以下、具体的に説明する。誤差算出部３１は、設定された対象領域と探索領域との対応画素間の差分値を算出する。その際、回転された対象領域内の画素と探索領域内の画素とを対応させ、当該対象領域内に存在しない探索領域内の画素を演算対象から除外する。
【００３５】
評価部３２は、各画素間の差分値の２乗値または絶対値を累積する。この累積値をそのまま評価値として使用してもよいし、累積値を画素数で割った平均値を評価値としてもよい。評価部３２は、評価値が最も小さい探索領域および変換λij(・)の組み合わせを特定する。上述の処理により探索領域のサイズに係わらず、差分値を算出する画素数が常に一定となる。即ち差分値を算出する画素数は、常に対象領域の画素数になる。従って平均値にせず累積値のままでも評価が可能である。
【００３６】
符号化部４０は対象領域の符号化データとして、変換パラメータ、ブロック判別ビットτij、平均値Rave、探索領域の位置(k,l)、等長変換ε、スケーリング係数αを符号化する。なお回転以外の等長変換εにおける評価値のほうが小さい場合は、その回転以外の等長変換εが選択される。
【００３７】
図６は、本発明の実施の形態に係る回転処理を説明するためのフローチャートである。以下の説明では簡略化のため回転角度θを４５度単位とする。即ち０度、４５度、９０度、１３５度、１８０度、２２５度、２７０度、３１５度を探索対象となる。探索の順番は当該記載順でもよいし、０度→９０度→１８０度→２７０度→４５度→１３５度→２２５度→３１５度でもよい。
【００３８】
探索開始時に評価部３２は、最小誤差値を格納するための変数minにシステムの最大値を代入する（Ｓ１０）。変形部２０は次の回転角度θの候補を設定し（Ｓ１１）、設定した回転角度θで対象領域を回転させ、探索部３０に渡す（Ｓ１２）。
【００３９】
誤差算出部３１は回転角度θが９０度の倍数であるか否か判定する（Ｓ１３）。９０度の倍数である場合（Ｓ１３のＹ）、誤差算出部３１は対象領域と探索領域との間で全画素を対象とした平均二乗誤差errを算出する（Ｓ１４）。９０度の倍数でない場合（Ｓ１３のＮ）、誤差算出部３１は対象領域と探索領域との間で、画素位置が一致する画素のみを対象とした平均二乗誤差errを算出する（Ｓ１５）。
【００４０】
評価部３２は変数minと平均二乗誤差errを比較し（Ｓ１６）、平均二乗誤差errが変数minより小さい場合（Ｓ１６のＹ）、平均二乗誤差errを変数minに上書きする（Ｓ１７）。平均二乗誤差errが変数min以上の場合（Ｓ１６のＮ）、ステップＳ１７の処理をスキップする。以上のステップＳ１１からステップＳ１７までの処理を全探索角度が終了するまで（Ｓ１８のＹ）、繰り返し（Ｓ１８のＮ）実行する。終了時において変数min内に格納されている平均二乗誤差errを算出した探索領域が、本回転処理に係る探索領域候補の内、対象領域と自己相似性が最も高い探索領域となる。実際の画像処理では、以上の回転探索を探索範囲全てに渡って行い、探索範囲内で最も自己相似性の高い領域を選択する。
【００４１】
以上説明したように本実施の形態では、画像内における自己相似領域の探索において回転角度θを、tanθ=A/B(AとBは整数）を満たす回転角度θに限定し、対象領域と探索領域との間で画素位置が一致する画素のみを演算対象とする。これにより演算量を抑えつつ多くの回転角度変形に対応できる。従来の９０度単位に限定した回転角度変形では、探索対象から外れていた自己相似領域の抽出も可能となる。正方形状のテンプレートを用いた場合でも、自己相似性の高い領域の探索範囲が増え、符号化効率および画質が向上する。
【００４２】
またアフィン変換などの幾何変形を行わないため、演算量の増加を抑えることができる。tanθ=A/B(AとBは整数）を満たす回転角度θに限定することにより、対象領域内の全画素について、探索領域内に画素位置が一致する画素が存在する状態を常に確保できる。これに加えて、対象領域と探索領域との間で画素位置が一致する画素のみを演算対象とすることにより、誤差値を算出する画素数を一定にできる。従ってハードウェア化も容易である。
【００４３】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００４４】
上記の実施の形態では対象領域を回転させる例を説明したが、探索領域を回転させてもよい。また探索した対象領域の自己相似領域を符号化に利用するのではなく、拡大、縮小などの変形処理に利用してもよい。
【符号の説明】
【００４５】
１  画像処理装置、  １０  領域設定部、  ２０  変形部、  ３０  探索部、  ３１  誤差算出部、  ３２  評価部、  ４０  符号化部。
【図１】
2017059026.tif 000003
【図２】
2017059026.tif 000004
【図３】
2017059026.tif 000005
【図４】
2017059026.tif 000006
【図５】
2017059026.tif 000007
【図６】
2017059026.tif 000008