(57)【要約】【課題】拡大画像に細かな歪を生じさせることなく入力画像を拡大して拡大画像を生成する。【解決手段】入力画像を拡大して拡大画像を生成する画像処理装置であって、前記入力画像を分割した複数のブロックの各々を所定の拡大率で拡大した画像に相当する拡大ブロックを求める拡大部と、前記拡大ブロックの各々について前記入力画像内での相関が所定の条件より高い相似領域を探索する探索部と、前記拡大画像内で前記ブロックに対応する位置にある領域の画素情報を当該ブロックに対応する前記相似領域の画素情報に基づいて設定する設定部とを有する。【選択図】図４１
2005339576.tif 000002
【特許請求の範囲】
【請求項１】
入力画像を拡大して拡大画像を生成する画像処理装置であって、
前記入力画像を分割した複数のブロックの各々を所定の拡大率で拡大した画像に相当する拡大ブロックを求める拡大部と、
前記拡大ブロックの各々について、前記入力画像内での相関が所定の条件より高い相似領域を探索する探索部と、
前記拡大画像内で前記ブロックに対応する位置にある領域の画素情報を、当該ブロックに対応する前記相似領域の画素情報に基づいて設定する設定部と、
を有する画像処理装置。
【請求項２】
前記探索部は、前記入力画像内で前記拡大ブロックとの誤差が最小になる領域を前記相似領域として求める、
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記探索部は、前記入力画像内から異なる回転変換を施した複数の相似領域候補を生成し、前記相似領域候補のうち前記拡大ブロックとの誤差が最小になるものを前記相似領域として求める、
ことを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記探索部は、前記入力画像内から異なる画素値の変換を施した複数の相似領域候補を生成し、前記相似領域候補のうち前記拡大ブロックとの誤差が最小になるものを前記相似領域として求める、
ことを特徴とする請求項１から請求項３までのいずれか一項に記載の画像処理装置。
【請求項５】
前記設定部は、前記拡大画像内で前記ブロックに対応する位置にある領域の画素情報を、前記相似領域の画素情報で置き換える、
ことを特徴とする請求項１から請求項５までのいずれか一項に記載の画像処理装置。
【請求項６】
入力画像を拡大して拡大画像を生成する画像処理方法であって、
前記入力画像を分割した複数のブロックの各々を所定の拡大率で拡大した画像に相当する、拡大ブロックを求める拡大ステップと、
前記拡大ブロックの各々について、前記入力画像内での相関が所定の条件より高い相似領域を探索する探索ステップと、
前記拡大画像内で前記ブロックに対応する位置にある領域の画素情報を、当該ブロックに対応する前記相似領域の画素情報に基づいて設定する設定ステップと、
を有する画像処理方法。
【請求項７】
前記探索ステップでは、前記入力画像内で前記拡大ブロックとの誤差が最小になる領域を前記相似領域として求める、
ことを特徴とする請求項６に記載の画像処理方法。
【請求項８】
前記探索ステップでは、前記入力画像内から異なる回転変換を施した複数の相似領域候補を生成し、前記相似領域候補のうち前記拡大ブロックとの誤差が最小になるものを前記相似領域として求める、
ことを特徴とする請求項６に記載の画像処理方法。
【請求項９】
前記探索ステップでは、前記入力画像内から異なる画素値の変換を施した複数の相似領域候補を生成し、前記相似領域候補のうち前記拡大ブロックとの誤差が最小になるものを前記相似領域として求める、
ことを特徴とする請求項６から請求項８までのいずれか一項に記載の画像処理方法。
【請求項１０】
前記設定ステップでは、前記拡大画像内で前記ブロックに対応する位置にある領域の画素情報を、前記相似領域の画素情報で置き換える、
ことを特徴とする請求項６から請求項９までのいずれか一項に記載の画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、入力画像を拡大して拡大画像を生成する画像処理装置及び画像処理方法に関する。
【背景技術】
【０００２】
（１）濃淡画像の新しい圧縮符号化方式として、フラクタル符号化の検討が進めらている（例えば、文献１：“Fractal Image Coding：A Review”，A. E. Jacquin ，Proceedings of the IEEE ，VOL.81, No.10，October, 1993など）。この方式では図１４に示すように符号化対象の１画面の原画像を正方形の複数のブロックに分割し、符号化器ではブロック毎に同じ画像の他の部分から相似領域を決定する。ここで、相似とは画面内の線形な縮小変換、９０°単位の回転や鏡像反転などの簡単な画素配置の変換、および画素値の線形変換（これらの線形変換を相似変換という）によって、画像パターンをほぼ等しくできるもの同士の関係をいう。ディジタル画像は離散的な画素で構成されているので、画面内の縮小変換とは画素のサブサンプリングのことである。
【０００３】
今、図１５に示すように、ブロック１５１に対して縦横２倍の大きさの相似領域１５２があり、ブロック１５１は４×４画素、相似領域１５２２は８×８画素で構成されているとする。ブロック１５１の左上の画素１５３は例えば画素配置の変換がない時、白丸１５５の位置にくるが、ここには画素はない。そこで、白丸１５５の周囲にある４つの画素１５４の平均値を画素１５３の値とする。この様にして、８×８のデータから４×４のデータをサブサンプリングによって求めるのが画面内の縮小変換である。
【０００４】
フラクタル符号化器からは、(a) ブロック毎の相似領域の位置と大きさ、(b) 画素配置の変換方法、(c) 画素値の変換方法の情報が符号として出力され、伝送あるいは蓄積される。画面内の縮小変換の方法は、相似領域の大きさと、予め決めておくブロックの大きさによって一意に決まるので、伝送・蓄積する必要はない。
【０００５】
図１６に、このようなフラクタル符号器から伝送される符号から元の画像を復号化する従来のフラクタル復号化器のブロック図を示す。入力される符号５０１は変換部５０２に入力される。また、フレームメモリ５０３には予め初期画像を設定しておく。初期画像はどのような画像でもかまわない。そして、符号５０１に含まれている情報に従って、各ブロックの相似領域のデータ５０４がフレームメモリ５０２から読み出される。相似領域のデータ５０４は、やはり符号５０１に含まれている情報に従って画面内縮小、画素配置の変換、画素値の変換が施され、変換データ５０５はフレームメモリ５０３に送られる。変換データ５０５はフレームメモリ５０３の該当ブロックの部分に上書きされる。この画素値の置き換えを全ブロックについて行い、第１置き換え画像が得られる。次に、この第１置き換え画像を用いて再度１回目と同じ置き換えを行い、第２置き換え画像が得られる。この様な置き換えを幾度か繰り返すと、フレームメモリ５０３内の画像は原画像とほぼ等しい画像に収束するので、それを再生画像５０６として外部に出力する。この再生画像５０６は、もはや置き換えをいくらしても変化がない。つまり、再生画像をＡ、置き換え変換をＦとして、
Ｆ（Ａ）＝Ａ
である。フラクタル符号化／復号化で画像を再生することは、上の式を満たす画像Ａを求めることと等しい。従来は、Ｆが縮小変換の場合はＦを繰り返すことにより、どの様な画像でも次第にＡに近づいていく性質を利用していた。
【０００６】
ところで、フラクタル符号は画像の幾何構造を符号に有するので、その符号に含まれているブロックと相似領域の情報を用いて、画像信号の各部分の属性を判定できると考えられる。画像内のある画素がどの領域に属しているかを判定することは、画像の領域分割に有効と考えられる。画像の領域分割には様々な応用がある。例えば、複数の被写体が含まれている画像を被写体別に複数の領域に分割した後、それらの領域を所望の配置で合成したり、領域の形状から被写体が何であるかを認識することができる。また、画像信号の圧縮符号化においては、視覚的に重要な領域により多くビットを配分して主観画質を向上させたりすることができる。これらの基本技術として、領域分割は重要である。しかしながら、フラクタル符号から元の画像信号などの情報信号の属性を検出する方法、および検出された属性から領域分割を行う方法は未だ提案されていない。
【０００７】
また、上述した従来の方法ではフラクタル復号化器において１画面分の画素値を保持するために、図１６に示したようにフレームメモリが必要であり、装置規模およびコストが大きくなってしまう。また、画像の一部分のみを再生したい時に、従来は一度画像全体を再生した後に所望の部分を切り出し、残りの不要部分は捨てるという方法しかなかったが、これでは不要部分の再生に無駄な演算を行うことになり、処理効率の点で好ましくない。
【０００８】
（２）濃淡画像の新しい圧縮符号化方式として、フラクタル符号化の検討が進められている（例えば、文献１：“Fractal Image Coding：A Review”，A.E. Jacquin ，Proceedings of the IEEE ，VOL.81, No.10，October, 1993など）。この方式では符号化対象の１画面の原画像を正方形の複数のブロックに分割し、符号化器ではブロック毎に同じ画像の他の部分から相似領域を決定する。ここで、相似とは画面内の線形な縮小変換、９０°単位の回転や鏡像反転などの簡単な画素配置の変換、および画素値の線形変換（これらの線形変換を相似変換という）によって、画像パターンをほぼ等しくできるもの同士の関係をいう。
【０００９】
フラクタル符号化においては、画像の再生を保証するために相似領域からブロックへの変換は縮小変換に限定される。符号化器ではブロック毎に試行錯誤的に縮小の線形変換を施し、変換されたデータとブロックの画像データとの誤差が小さくなるものを相似変換として決定する。そして、相似変換の情報として画素値変換符号（画素値方向の縮小係数、加減算値など）と位置変換符号（相似領域の位置と形・大きさ、回転角など）の２種類の符号が出力され、該原画像の圧縮データとして伝送されたり蓄積されたりする。
【００１０】
図４２に、従来のフラクタル符号化器のブロック図を示す。原画像３０１はフレームメモリ３０２に保持される。制御部３０３からのある線形変換を指定する信号３０４により、フレームメモリ３０２からその指定された領域の画像データ３０５が読み出され、サイズ縮小変換部３０６に入力される。サイズ縮小変換部３０６では領域の画像データ３０５がブロックと同じサイズ、つまり同じ画素数に縮小され、その縮小されたデータ３０７は変換部３０８に送られる。変換部３０８ではサイズ縮小変換以外の上述した線形変換が施され、変換されたデータ３０９として差分器３１１に入力さる。一方、ブロックデータ３１０もフレームメモリ３０２から差分器３１１に入力される。差分器３１１ではブロックデータ３１０と変換されたデータ３０９の誤差が計算され、その誤差３１２は制御部３０３に送られる。この様にして制御部３０３は幾種類かの線形変換を指定し、その内で誤差３１２が小さかった線形変換を該ブロックの相似変換として決定し、その情報を符号３１３として外部に出力する。
【００１１】
図４３に、従来のフラクタル復号化器のブロック図を示す。初めに任意の画像を画像メモリ４０１に用意する。一般に、この初期画像は原画像とは異なる。入力の符号４０２は、例えば蓄積媒体４０３から読み出される。そして、画像メモリ４０１から第１のブロックの相似領域のデータが読み出される。画像メモリ４０１から読み出されたデータ４０５は、第１のブロックの位置変換符号４０６に指示される変換が位置変換部４０４において施され、画素値変換部４０７に送られる。画素値変換部４０７においても第１のブロックの画素値変換符号４０８に指示される変換が施され、変換されたデータ４０９は画像メモリ４０１に戻される。画像メモリ４０１では、変換されたデータで第１のブロックの画素を置き換える。この様な相似変換による画素の置き換え変換を第２のブロック以降についても同様に行い、第１変換画像を得る。この画像も原画像とは一般に異なる。
【００１２】
次に、画像メモリ４０１に保持されている第１変換画像を用いて同様に各ブロックの置き換え変換を行い、第２変換画像を得る。この置き換え変換を繰り返していくことにより、画像メモリ４０１内の画像は次第に原画像とほぼ等しい画像に収束する。この収束画像を再生画像として出力し、例えばディスプレイ４１０によって表示する。
【００１３】
ところで、多数の画像をフラクタル符号化された符号データの形で格納した画像データベースが存在し、このデータベースについて検索を行う場合を考える。所望の画像を見つけたいとき、通常は、データベースから画像の符号を読み出して原画像を再生し、ディスプレイに表示させることを一つ一つの画像について行う。しかし、検索においては必ずしも原画像そのものを見なくても、画像の大まかな形や輝度、画像の印象などが反映された簡易的な画像で用が足りることが多い。簡易的な画像を生成する方が原画像を生成するよりも少ない演算量、回路規模で行うことができれば、検索時間を節約でき、検索装置も安価に提供できると考えられる。特に、簡易的な画像として２値画像を生成できれば、高価な多階調ディスプレイを用いずに済む。
【００１４】
また、原画像にモーフィングなどの加工を施す場合、通常は圧縮データから原画像を再生し、濃淡画像のレベルで従来からある手法で加工を施し、できた加工画像を蓄積や伝送のために再び圧縮する。しかし、このように圧縮と再生を繰り返すと、画像がぼけたり歪が現れたりして画質が次第に劣化してしまう問題があり、また符号化器と復号化器の両方を用意しなければならず、ハードウェア規模が大きくなってしまう。
【非特許文献１】“Fractal Image Coding：A Review”，A.E. Jacquin ，Proceedings of the IEEE ，VOL.81, No.10，October, 1993
【発明の開示】
【発明が解決しようとする課題】
【００１５】
本発明の目的は、拡大画像に細かな歪を生じさせることなく入力画像を拡大して拡大画像を生成する画像処理装置及び画像処理方法を提供することにある。
【課題を解決するための手段】
【００１６】
本発明は、入力画像を拡大して拡大画像を生成する画像処理装置において、前記入力画像を分割した複数のブロックの各々を所定の拡大率で拡大した画像に相当する拡大ブロックを求める拡大部と、前記拡大ブロックの各々について、前記入力画像内での相関が所定の条件より高い相似領域を探索する探索部と、前記拡大画像内で前記ブロックに対応する位置にある領域の画素情報を、当該ブロックに対応する前記相似領域の画素情報に基づいて設定する設定部とを有する。
【００１７】
また、本発明は入力画像を拡大して拡大画像を生成する画像処理方法において、前記入力画像を分割した複数のブロックの各々を所定の拡大率で拡大した画像に相当する、拡大ブロックを求める拡大ステップと、前記拡大ブロックの各々について、前記入力画像内での相関が所定の条件より高い相似領域を探索する探索ステップと、前記拡大画像内で前記ブロックに対応する位置にある領域の画素情報を、当該ブロックに対応する前記相似領域の画素情報に基づいて設定する設定ステップとを有する。
【発明の効果】
【００１８】
本発明によれば、拡大画像に細かな歪を生じさせることなく入力画像を拡大して拡大画像を生成することができる。
【００１９】
例えば、相似変換を決定する際に、符号化単位領域の画像データを拡大変換したものと、相似領域の画像データの誤差が小さくなるような拡大変換の逆変換が相似変換として決定される。この符号を用いて拡大された画像を生成する時は、相似変換情報に含まれる位置変換情報のうち、相似領域の位置と大きさに関する符号を定数倍する。
【００２０】
ここで、通常の符号化器の様に縮小変換した画像を用いて決定された符号を用いると、拡大画像に細かな歪が生じる。これに対し、本発明では事実上拡大した画像のレベルで誤差比較をしているので、原画にない細かな歪は発生しない。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施形態を図面を用いて説明する。  
（第１の実施形態）  
図１は、本発明の第１の実施形態に係る属性検出装置の構成を示すブロック図である。図１においては、入力として符号１１が与えられる。この符号１１は各ブロックに対応する相似領域の位置、大きさ、信号配列や信号値の変換方法の情報を持つ符号であり、例えばフラクタル符号化器によって生成されたものである。ここで、符号１１の元となる情報信号は例えば図２に示すような１次元信号（音声信号など）または２次元信号（画像信号など）であり、１次元信号の場合は点線で示すように時間軸方向に複数のブロックに分割され、また２次元信号の場合は空間方向に複数のブロックに分割されている。そして、それぞれのブロックに対応した相似領域が符号１１に示されている。
【００２２】
符号１１は、写像部１２に入力される。写像部１２では、まず属性検出位置に初期点が設定される。次に、その初期点がどのブロックに属するかが判別され、そのブロックから相似領域へ点（被写像点）が写像される。写像部１２から出力される被写像点の位置情報１３は、メモリ１４に一時的に保持される。以上が第１回目の写像である。
【００２３】
第２回目の写像は、メモリ１４から点の位置情報１５が読み出され、以後は第１回目と同様にして写像が施されて、第２回目の被写像点の位置情報１３がメモリ１４に書き込まれる。この様な写像が数回〜数十回行われる。
【００２４】
被写像点の位置情報１３は、属性決定部１６にも逐次送られる。属性決定部１６では例えば、被写像点がある１点に収束するか否か、収束する場合はどの点に収束するか、あるいは周期軌道に収束するか否か、収束する場合はどの様な周期軌道か、あるいは、カオス的な動きをするか否か、そのような動きをする場合はどういう領域を動いているか、どういう形を形成しているかなどを検出し、その結果によって属性検出位置の属性を決定して属性情報１７を外部に出力する。
【００２５】
ここで、属性とは例えば(a) 情報信号の再生値、(b) 情報信号がどの程度ばらついているか、(c) 情報信号がどういう周期の信号パターンであるか、(d) 急峻な変化があるか否か、(e) 信号のパターンによって情報信号を幾つかの部分に分類した時にどの部分に属するか、といった情報である。そして、信号が急峻に変化する部分では、相似領域は信号内で比較的離れた部分にある。従って、被写像点も広い範囲を往来するので、逆に被写像点が広い範囲を行ったり来たりする場合には、その初期点の近くに信号が急峻に変化する部分があると決定できる。また、被写像点が周期的に運動する場合は、信号にも周期的なパターンがあると推定され、写像がある範囲のみを往来する場合は、その範囲で同じ様な信号パターンが続いていると推定できる。
【００２６】
次に、図３〜図５を用いてフラクタル符号を用いた写像の特徴を説明する。図３が入力画像であり、ここでは星型、三角形、四角形、そして背景の４つの領域１，２，３，４がある。図３〜図５では各領域１〜４の画像を簡易的に線画像で描いているが、実際は濃淡画像でも構わない。各領域１〜４は互いに画素値あるいはテクスチャ等が異なり、少なくとも人間が見れば区別して認識できるものとする。また、図３のフラクタル符号、即ちブロック毎の相似領域の情報を元に決まる点の写像をＰとする。
【００２７】
ここで、新たに画面を用意し、適当にランダムに初期点を配置したものが図４（ａ）である。そして、図４（ａ）に示す全ての初期点に写像Ｐを繰り返し施していくと、図４（ｂ）に示すように点の配置に粗密が生じ、さらに写像を繰り返すと図４（ｃ）に示すように塊になってくる。ここでは、４つの塊５，６，７，８ができる例を示している。
【００２８】
そして、これらの塊５，６，７，８がそれぞれ領域１，２，３，４に対応しているのが本写像の特徴である。例えば、図４（ａ）の初期点のうち塊６に至ったものだけを残し、他の点を除去すると、図５のように星型の領域１が浮かび上がる。同様に、塊７と領域２、塊８と領域３、塊５と領域４（背景）が対応する。図３のままでは、領域分割をするのが困難な場合でも、図４（ｃ）のように点の配置の偏りが大きければ、そのクラスタリングは容易であり、これに基づく領域分割も容易である。
【００２９】
このような写像の特徴を利用し、写像される点の動き方によって属性検出位置が属する領域を決定する処理の流れを図６に示すフローチャートを参照して説明する。
【００３０】
まず、ステップＳ１０で画面内の位置ベクトルｘに属性検出位置のベクトルｘ０を代入し、ステップＳ１１で写像回数ｎに０を代入する。そしてステップＳ１２でｘの被写像点を求め、ｘを更新する。それと前後して、ステップＳ１３でｎにｎ＋１を代入する。次に、ステップＳ１４で写像回数ｎが予め設定する所定の回数Ｎに達したか否かを判定する。ここでｎがＮに達していない場合は、ステップＳ１２に戻る。ｎがＮに達した場合は、ステップＳ１５でｘを用いた所定の判定条件によりｘ０に関する判定が下される。
【００３１】
このステップＳ１５での判定条件は、例えば図４（ｃ）に示した点の集合９を用いて、「ｘは集合９に属するか否か」というものになる。この場合、Ｙｅｓなら「ｘ０は領域１に属する」と判定され、Ｎｏなら「ｘ０は領域１に属さない」と判定される。
【００３２】
また、領域分割からは離れるが、後述する第３の実施形態のように属性として特に画像信号などの再生値を求める場合には、ｘは画面＋画素値の３次元のベクトルであり、写像Ｐでは位置のみでなく画素値も写像される。そして、ステップＳ１５での判定条件は、「ｘの画素値は所定値の範囲にあるか」というものになる。その場合、Ｙｅｓであれば「ｘ０の再生値は最初に設定した画素値である」と言えるし、Ｎｏであれば「ｘ０の再生値は最初に設定した画素値ではない」と言える。
【００３３】
一般に、判定条件に対するＹｅｓ／Ｎｏによって、「ｘ０はａである」／「ｘ０はａではない」という形の出力が得られる。
【００３４】
図７は、属性検出位置が属する領域を決定する処理の別の流れを示すフローチャートである。図６と異なるのは、ｘをＰ（ｘ）に置き換える毎にステップＳ１６で判定処理が施される点である。ここで、Ｙｅｓであれば直ちに「ｘ０はａである」と判定される。Ｎｏの時は、ステップＳ１７で写像回数ｎがＮに達したか否かが判定され、Ｙｅｓの場合は「ｘ０はａではない」と判定され、Ｎｏの時はステップＳ１２に戻る。
【００３５】
（第２の実施形態）  
図８は、図１における属性決定部１６を周期検出部２５に置き換えた実施形態である。周期検出部２５は、情報信号が周期的か否かを判定するものである。写像を何回か施した後の被写像点の位置情報１３は、メモリ２１に保持される。そして、写像はさらに続行され、写像を行う度にメモリ２１に保持されている被写像点の位置情報２２と現在の被写像点の位置情報１３が差分器２３に入力される。差分器２３では両者の差２４が検出され、周期検出部２５に送られる。周期検出部２５では、差２４が所定値以下になったら情報信号が周期的であり、軌道が閉じたと判定する。逆に、所定の回数写像を繰り返しても差２４が小さくならなかった場合は、情報信号が周期的でないと判定する。そして周期的であるか否かに対応する属性情報２６を出力する。また、軌道が閉じるまでの写像の回数や軌道の経路を参照する様にすれば、さらに多様な分類ができる。
【００３６】
（第３の実施形態）  
図９は、本発明を画像の復号化に適用した実施形態のブロック図である。画像は図１４に示したように正方形のブロックに分割されている。
【００３７】
符号１１は各ブロックに対応する相似領域の位置と大きさ、画素配置や画素値の変換方法の情報を持つ符号であり、例えばフラクタル符号化器によって生成されたものである。この符号１１は写像部１２に入力される。画素値決定部３１からは、画面内の位置成分２つと画素値成分１つの合計３成分を有する初期点情報３２が選択部３３に送られる。初期点情報３２の位置成分は再生したい画素の位置座標、画素値成分は仮に定める画素値とする。この初期画素値は、後で試行錯誤的に切り換えられる。
【００３８】
選択部３３は入力される２つの信号のうち１つを選択して出力するもので、この時は予め初期点情報３２が出力されるように設定される。これにより、初期点情報３２がそのままメモリ１４に入力され保持される。次に、メモリ１４から初期点が被写像点の位置情報３４として読み出され、写像部１２に入力される。
【００３９】
写像部１２では、図１０に示すように被写像点１０１が属するブロック１０２を求め、このブロック１０２に対応する相似領域１０３の情報を符号１１から知ることにより、被写像点１０１を写像点１０４に写像する。具体的には、被写像点１０１と相似領域１０３の情報から写像点１０４の位置座標を計算する。これは、従来の技術の項で図１５を用いて説明した画素サンプリングと逆向きの変換となる。写像点１０４は一般には画素が存在する位置には来ないが、そのままの座標を求める。同時に、被写像点１０１の画素値もブロックから相似領域の向きに変換して写像点１０４の画素値を得る。
【００４０】
すなわち、画素値をｖ，変換係数をａ、ｂとして、従来の相似領域１０３からブロック１０２への画素値の変換ｇ（ｖ）が、  
ｇ（ｖ）＝ａ・ｖ＋ｂ  
で表されるとすると、写像部１２ではｇの逆変換ｈ  
ｈ（ｖ）＝（ｖ−ｂ）／ａ
により写像点１０４の画素値が計算される。ここで、ａ，ｂの値はブロックによって異なる。
【００４１】
図９に説明を戻すと、写像部１２からの写像点１０４の位置情報１３は、選択部３３に送られる。選択部３３は、予め写像点１０４の位置情報１３を出力するように切り換えられており、この位置情報１３がメモリ１４に入力され保持される。以後は、前回の写像点の位置情報が新たな被写像点の位置情報としてメモリ１４から読み出され、同様な写像が繰り返される。
【００４２】
すなわち、図１１に示すように今度は前回得られた写像点１０４が被写像点として、それが属するブロック１０５が求められ、このブロック１０５からその相似領域への写像が施され、新しい写像点１０６が得られる。画素値についても新しい写像点の画素値が計算される。この様に写像が何回か繰り返される。
【００４３】
写像を繰り返した時の写像点の画素値の変化を初期点の画素値を様々に設定した場合について示したのが図１２である。横軸が写像回数、縦軸が写像点の画素値であり、元々の画像の画素値は“０”から“２５５”の間にある。
【００４４】
写像回数０回、つまり初期点の画素値がちょうど再生値と一致した場合を太線で示してある。従来の技術の項で説明した様に、再生画Ａは変換Ｆによって変化しない。このことから再生画像Ａにちょうど乗った点を初期点とした場合は、本実施形態のようにＦを画素毎に逆に辿る写像をしても、被写像点もまたＡに乗ることが分かる。従って、この場合は写像を繰り返しても、写像されていく先々でＡに乗るので、画素値は発散せず常に“０”から“２５５”の間にある。
【００４５】
しかし、復号化器では当然、初期点の再生値は未知であるので、初期点の仮の画素値は正しい再生値とは異なる。図１２では、初期点の画素値が再生値と異なる場合を細線で示してある。初期点での仮りの画素値と再生値の差をｅ０とし、写像したところでの再生値との差をｅｉ（ｉ＝１，２，３…）とすると、  
ｅｋ＝｜１／ａｋ｜・ｅｋ−１  （ｋ＝１，２，３…）
である。ここで、ａｋはその用いた画素値変換ｈ（ｖ）の係数ａである。変換Ｆを縮小変換にするため、ほとんどの場合ａの絶対値は１より小さく設定されるので、その逆数は１よりも大きくなる。従って、ｅｉは指数関数的に大きくなり、被写像点は発散する。そしてａｋが常に正の場合は、写像によって再生値と被写像点の画素値の大小関係は入れ替わらないので、初期値が再生値よりも大きい場合は正に発散し、小さい場合は負に発散する。従って、初期点の画素値を様々に切り換えて正に発散する初期値と負に発散する初期値の境界をみつければ、再生値が分かる。また、ａｋが負の場合はその写像によって再生値と被写像点の画素値の大小関係は逆転するので、それまでの写像に現れた負のａｋの個数が偶数の場合は被写像点の画素値は大きな正の値になり、奇数の場合は絶対値が大きな負の値になる。
【００４６】
図９において、写像の発散は次のように判定される。写像部１２から得られる写像点の位置情報１３で指定される写像点の画素値は、二つの比較部３５，３６に入力される。比較部３５では、“２５５”という値と位置情報１３で指定される写像点の画素値の大小比較を行い、その比較結果３７を画素値決定部３１に送る。また同時に、比較部３６では“０”という値と写像点の画素値の大小比較を行い、その比較結果３８を画素値決定部３１に送る。
【００４７】
画素値決定部３１は、写像の繰り返しによって写像点の画素値が“２５５”より大きくなった場合は写像を打ち切る。そして、その写像の繰り返しで出てきた負のａｋの個数がゼロまたは偶数の時は、初期点３２の画素値を前回より小さくして再度写像を行い、奇数の時は大きくする。また、写像点の画素値が“０”より小さくなった場合は、負のａｋの個数がゼロまたは偶数の時は初期点情報３２で指定される初期点の画素値は前回より大きくし、ａｋの個数が奇数の時は小さくする。この様にして、再生値があると推定される区間の上端と下端を次第に絞って、最終的に再生値を得る。
【００４８】
また、所定の回数写像を繰り返しても“０”と“２５５”の間にとどまる場合は、その時の初期値を再生値とする。また、写像の過程で点がちょうどブロックの境界に来てしまった場合は、その境界を挟むいずれのブロックを選択してもかまわない。
【００４９】
また、前記文献１にも記載されているように、ブロックによっては相似領域を定義せず、画素値を直接符号に持っている場合がある。写像の過程でこのようなブロックに至った場合は、ａが常に正の時はブロックに与えられている画素値より写像点の画素値が大きい場合は初期値も再生値より大きかったと判定でき、逆に小さい場合は初期値も再生値より小さかったと判定できる。ａが負になる時も上と同様なアルゴリズムで判定できる。
【００５０】
本実施形態によれば、フレームメモリを必要としない分、従来よりも装置規模を小さくできる。また、画像の一部分例えば左上１／４だけを再生したい場合は、その範囲の画素についてのみ再生値を求めれば良いので演算量が減少し、処理効率が向上する。また、画像の必要な部分だけを再生するので、再生に要する時間を短縮することができる。
【００５１】
（第４の実施形態）  
図１３は、写像の正変換と逆変換を用いる第４の実施形態を示すブロック図である。第３の実施形態と同様に、符号１１に基づいて写像部１２で点の写像が反復的に施される。但し、写像部１２では位置の写像のみが行われ、画素値の写像は行わない。従って、メモリ１４には初めに再生値を求めたい画素の位置のみが設定され、その後も写像点の位置のみが保持される。また、写像は予め決めた回数Ｎ回だけ行う。そして、写像部１２からは被写像点がどのブロックに属するかのブロック特定情報４１が逐次出力され、Ｎ個のブロック特定情報４１がメモリ４２に保持される。例えば図１１の例では、ブロック１０２→ブロック１０５→ブロック１０７の順で、そのブロック特定情報４１が保持される。この場合はＮ＝３である。
【００５２】
次に、メモリ４４に例えば“１２８”という画素値を設定する。そして、メモリ４２からは一番最後に書き込まれたブロック特定情報４３が読み出され、そのブロックの相似領域からブロックの向きへの画素値の変換がメモリ４４から読み出された画素値４５に対して施される。つまり、上述の表記にならえば、
ｇ（ｖ）＝ａ・ｖ＋ｂ
を計算して、画素値変換部４６で画素値４７が得られる。ここで、ａとｂは該当ブロック毎に異なる値であり、これらは画素値変換部４６によって符号１１から読み出される。この画素値の変換をメモリ４４からブロック特定情報を逆順に読み出しながらＮ回施した結果を再生値４８として外部に出力する。
【００５３】
この様にして再生値が得られる理由を説明する。先に示した図１１では、初期点の誤差が写像回数によって指数関数的に拡大している。この事は写像を右から左に辿ることを考えると、右端である程度の誤差でスタートしても写像を逆に辿ることで誤差はどんどん小さくなり、やがて再生値とほぼ等しくなる。但し、写像を逆に辿るためには、Ｎ回目でちょうど所望の画素に点が写像される必要があるので、上述した様に位置の写像を予めメモリ４２に蓄え、それから逆順に読み出すという操作が必要になる。この時、画素値の変換はブロック毎に決まっているので、画素の位置という詳細な情報は必要ではなく、その画素がどのブロックに属するかの情報で十分である。Ｎ回目の誤差ｅＮは、ｋ回目の写像の係数ａをａｋとして  
ｅＮ＝ｅ０／｜ａ１・ａ２・…・ａＮ｜
となる。再生画像は“０”から“２５５”の画素値の間にあることを考え合わせると、再生値の誤差をＥ以下に抑えたい場合は、  
Ｅ／｜ａｌ・ａ２・…・ａＮ｜＞２５５
を満たすようにＮを設定すれば、画素値４５が“０”から“２５５”の間のどの値からスタートしても、誤差がＥ以下になることが補償される。例えば  
ａ１＝ａ２＝…＝ａＮ＝１／２  
Ｅ＝１  
の時は、Ｎ＝８以上とすればよい。
【００５４】
本実施形態は第３の実施形態と比較して、メモリ量は多少増加するが、試行錯誤的に発散状況を調べる必要がないので、演算量を削減することができる。
【００５５】
次に、第２の発明について説明する。  
（第１の実施形態）  
図１７は、第２の発明の一実施形態を示すブロック図である。位置変換情報を表す符号５１が外部から入力され、位置変換符号メモリ５２に保持される。この位置変換符号メモリ５２から読み出された位置変換符号５３は、エッジ検出部５４に送られる。エッジ検出部５４では、画像内の物体の輪郭つまりエッジの位置が検出され、エッジの位置情報５５がエッジ画像生成部５６に送られる。エッジ画像生成部５６では、エッジの位置情報５５で指定されるエッジ部を例えば黒、それ以外を白というように輝度や色で区別したエッジ画像５７を生成して外部に出力する。
【００５６】
（第２の実施形態）
図１８は、図１７をより具体化した実施形態であり、図１７のエッジ検出部５４を固定点検出部５８により実現している。固定点検出部５８では、ブロック毎に位置変換の固定点の位置を求め、その固定点の位置情報５９をエッジ画像生成部５６に送る。エッジ画像生成部５６では、固定点の位置情報５９で指定される点を他と異なる色や輝度で区別したエッジ画像５７（この場合は点の集まり）を生成して外部に出力する。
【００５７】
今、例えば図１９に示すようなエッジ２０２を含む画像２０１に対して、ブロック２０３の相似領域として領域２０４が求まっているとする。同様に、図２０に示すようにブロック２０５には領域２０６が相似領域として求まっているとする。図２１に、ブロック２０３の相似変換の固定点２０７を、図２２にブロック２０５の相似変換の固定点２０８を示す。この様に固定点２０７や２０８はエッジ２０２の上に乗るので、これらの固定点をブロック毎に求めて画像に表示すれば、物体の概形を認識することができる。
【００５８】
（第３の実施形態）  
図２３は、図１８の固定点検出部５８とエッジ画像生成部５６との間に固定点接続部６０を挿入し、ここで固定点を結ぶことにより点の情報を線の情報に変えてエッジ画像生成部５６に送るようにした例である。固定点接続部６０では全ての固定点同士を結ぶのではなく、同一のエッジ上にあると思われるもの同士、例えば図２４に示す様に隣合う図２１のブロック２０３と図２２のブロック２０５の固定点２０７と２０８を結ぶ。
【００５９】
また、位置変換がこの例と多少異なり、隣合うブロック２０３，２０５の固定点が図２５に示す点２１１と２１０というように非常に離れる場合は、点２１０と２１１を結ぶ直線２１２のうち、ブロック２０３，２０５や領域２０４，２０６の周辺では直線がエッジと重なるものの、遠く離れるとエッジからずれることがある。従って、直線２１２のうちブロック２０３と２０５に入る実線で示す部分２１３のみをエッジとする。
【００６０】
（第４の実施形態）  
図２６は、図１８および図１８中の固定点検出部５８の具体例を示したものであり、位置変換を次式で示すアフィン変換ｗで表現できる場合の例である。
【数１】
2005339576.tif 000003
【００６１】
ここで、ｘ，ｙは画像の横座標と縦座標の値、ａ，ｂ，ｃ，ｄ，ｅ，ｆはアフィン変換係数である。また、
【数２】
2005339576.tif 000004
【００６２】
とすると、（１）式は
【数３】
2005339576.tif 000005
【００６３】
と書ける。ここでｘ′はｘが変換される点である。
【００６４】
変換係数決定部６１では、Ａとｂ即ちａ〜ｆが決定される。そのために、まず領域内にｘ１  （＝（ｘ１  ，ｙ１  ）），ｘ２  ，ｘ３  の３点を設定する。例えば、領域の左上角、右上角、左下角の３点をｘ１  ，ｘ２  ，ｘ３  とする。そして、これら３点に各々位置変換を施してｘ１  ′，ｘ２  ′，ｘ３  ′を得る。これらはいずれも（２）式を満たすので、次の連立方程式が成り立つ。
【数４】
2005339576.tif 000006
【００６５】
これは６元連立１次方程式であるので、ａ〜ｆの６つの未知数が求まる。変換係数決定部６１でこうして求められたａ〜ｆの値６２が固定点決定部６３に送られる。
【００６６】
固定点決定部６３では、
【数５】
2005339576.tif 000007
【００６７】
という２元連立一次方程式を解き、ｘ０  ＝（ｘ０  ，ｙ０  ）という固定点５９を求める。
【００６８】
（第５の実施形態）  
次に、フローベクトルを用いてエッジを求める実施形態を説明する。図２７に示す様に、フローベクトル２２０は相似領域内の各点がどの向きに変換されていくかを表したものである。実際には各点の変換点を求め、変換の前後の点を結ぶ線の傾きを各点のフローベクトルとする。ベクトルの大きさは予め決めておくものとする。
【００６９】
図２８に、ブロック２０５の位置変換に対するフローベクトル２２１を示す。なお、図２７は既に説明した図１９の場合に、図２８は図２０の場合にそれぞれ対応する。また、図２９に示すようにエッジ２３１が曲線の場合は、一般に相似変換の位置変換に回転変換が加わる。この例では、領域２３０からブロック２３１へは時計回りの変換が施される。図３０に、この場合のフローベクトル２３２を示す。この様に回転を伴う場合は、うずを巻くようなフローベクトルになる。これらのフローベクトル２２０，２２１，２３２は、エッジ部分においてはエッジと同じ方向になる性質がある。従って、図３２に示すように、フローベクトル２２０とフローベクトル２２１を重ね、２つのベクトルが与えられる点についてはエッジ部分２２２でそのベクトルの方向が揃う。従って、ベクトルの内積の絶対値が所定値以上の部分をエッジと判定できる。
【００７０】
図３１に、フローベクトルを用いてエッジを求める実施形態を示す。フローベクトル検出部７１でフローベクトル７２を検出し、方向比較部７３でフローベクトル７２の内積の絶対値を計算することにより、エッジ７４を検出する。
【００７１】
なお、本実施形態では主に図１９と図２０を基に２つのブロックの相似変換のみを用いて説明してきたが、ブロックの数を増やせばより広い範囲でエッジを検出できる。
【００７２】
（第６の実施形態）  
次に、乱数により位置変換符号を発生する実施形態を図３３に示す。従来の技術で説明した図４３の復号化器とは、位置変換部４０４に入力される位置変換符号４１２が異なる。この位置変換符号４１２は、乱数発生部４１１によってブロック毎にランダムに設定される。例えば、位置変換符号に含まれる相似領域の位置や大きさについて、予め設定される複数の領域を等確率でランダムに設定する。回転角についても同様にランダムに設定する。この様にして作った位置変換符号４１２を用いると、もはや原画像に含まれる物体の形は再生されない。しかし、画素値変換符号４０８は原画像のものが与えられるので、再生画像の明部、暗部の比や大まかな明暗のパターンなどは再現される。従って、この再生画像でも原画像の印象や画質の感じは掴める。しかも、符号４０２としては原画像の位置変換符号は必要ないので、例えば検索対象のデータベースは位置変換符号の量だけ容量を節約でき、また符号の通信量も節約できる。
【００７３】
（第７の実施形態）  
図３４に示す実施形態は、従来の技術で説明した図４３の復号化器の位置変換部４０４と画素値変換部４０７に、符号設定部４１５からの位置変換符号４１４と画素値変換符号４１３をそれぞれ入力するようにしたものである。ここで符号設定部４１５には、既に求められているある画像の符号４０２と符号入力部４１７からの信号４１６が入力されている。符号入力部４１７には、人間が操作しやすい様にテンキーやマウス、タッチセンサ、ペンなどが付属している。
【００７４】
本実施形態は、符号入力部４１７を人間が用いて、符号４０２の一部を変更することにより、再生画像４０５を変化させる装置である。
【００７５】
図３５と図３６に、符号４０２のうちの位置変換を変化させる例を示す。図３５のように、ブロック２４０とその相似領域２４１が符号４０２によって与えられていたとする。図では煩雑になるので省略しているが、他のブロックについてもそれぞれ相似領域が与えられている。この時の再生画像には、物体２４２が図のような形で再生される。ここで、領域２４１を図３６の様に点２４３を中心に時計回りに少し回転させる。すると、ブロック２４０の内部の物体２４２の下の部分が少し伸びる。ブロック２４４についても同様な操作をすることにより、物体を細長く変形できる。
【００７６】
この様に位置変換符号を徐々に変化させると、物体の形状も図３７に示す様に徐々に変形できる。従って、本実施形態によると例えば人間の顔画像の顔の輪郭を徐々に変化させたりするモーフィング加工も、符号レベルで可能となる。
【００７７】
また、画素値変換符号を変化させる場合を図３８と図３９に示す。画素値の加減算値が小さいと、図３８の背景部の様に比較的平坦な例えば青空のようなテクスチャになる。そこで、その加減算値をブロック毎にばらつくように変更すると図３９に示すように凸凹した、例えば曇空のようなテクスチャにすることができる。この場合も、やはり符号レベルでの画像加工が可能になる。
【００７８】
図４０に、図３４における符号４０２を用いず全ての符号を符号入力部４１７を用いて入力する例を示す。これはフラクタル符号化の一種である平均値分離型フラクタル符号化（「反復変換符号化による画像圧縮」井田、駄竹、第５回、回路とシステム軽井沢ワークショップ論文集、１９９２年４月）の例であり、この方式では画素値変換符号の加減算値の代わりにブロック平均値が用いられる。図４０（ａ）がブロック単位に輝度を大まかに設定した図である。図４０（ｂ）が玉子型のエッジを生成するように位置変換を設定した図である。例えばブロック２５１については領域２５２を設定する。他のブロックについても同様である。図４０（ａ）（ｂ）のように設定された画素値変換と位置変換を用いて生成した画像が図４０（ｃ）である。このように輝度の大まかな分布とエッジを与えることにより、所望の画像を生成できる。
【００７９】
（第８の実施形態）  
図４１は、画像を拡大再生するための符号を得る実施形態を示すブロック図であり、従来の技術で図４２を用いて説明した符号化器とは領域の画像データ３０５とブロック画像データ３１０の処理が異なる。領域の画像データ３０５はもとのサイズのまま変換部３２１で回転変換や、画素値方向の縮小、加減算が施され、変換された領域データ３２２として差分器３１１に入力される。一方、ブロック画像データ３１０はサイズ拡大部３２３で領域と同じサイズ、つまり同じ画素数に拡大され、得られた拡大ブロックデータ３２４はメモリ３２５に保持される。そして、変換部３２１で変換された領域データ３２２が差分器３１１に入力されるタイミングに合わせて、メモリ３２５から拡大ブロックデータ３２６が読み出され、差分器３１１に入力される。以後、差分器３１１から得られる誤差３１２が小さくなる変換を見つけて符号として出力する点は、図４２の従来の場合と同じである。
【００８０】
変換部３２１で幾種類かの変換、例えば９０°単位の４通りの回転変換が逐次的に行われ、その誤差が評価されるが、その度に同じブロックについてサイズ拡大変換をすると演算量が多大になる。そこで、本実施形態ではメモリ３２５にサイズ拡大部３２３で１回サイズ拡大変換されたデータを保持し、同一ブロックのデータを繰り返し読み出すことにより、演算量を低減している。なお、演算量が問題にならない場合はメモリ３２５を省略することができる。
【００８１】
このように第２の発明によれば、画像の符号から簡易画像を生成することが可能となり、また符号レベルでの画像加工が可能となる。
【図面の簡単な説明】
【００８２】
【図１】第１の発明に係る一実施形態を示すブロック図
【図２】１次元信号をブロック分割した図
【図３】フラクタル符号を用いた写像の特徴を説明するための入力画像の図
【図４】フラクタル符号を用いた写像の特徴を説明するための写像過程を示す図
【図５】フラクタル符号を用いた写像の特徴を説明するための最終過程を示す図
【図６】第１の発明の一実施形態に係る属性検出方法の手順を示すフローチャート
【図７】第１の発明の他の実施形態に係る属性検出方法の手順を示すフローチャート
【図８】第１の発明に係る他の実施形態を示すブロック図
【図９】第１の発明に係る他の実施形態をブロック図
【図１０】ブロックから相似領域への写像を示す図
【図１１】写像を繰り返す様子を示す図
【図１２】画素値が発散する様子を示す図
【図１３】第１の発明に係る他の実施形態を示すブロック図
【図１４】画像をブロック分割した図
【図１５】従来のサブサンプリングを示す図
【図１６】従来のフラクタル復号化器を示すブロック図
【図１７】第２の発明に係る一実施形態を示すブロック図
【図１８】第２の発明に係る他の実施形態を示すブロック図
【図１９】相似領域を表す図
【図２０】相似領域を表す図
【図２１】固定点を表す図
【図２２】固定点を表す図
【図２３】第２の発明に係る他の実施形態を示すブロック図
【図２４】エッジを表す図
【図２５】エッジを表す図
【図２６】第２の発明に係る他の実施形態を示すブロック図
【図２７】フローベクトルを表す図
【図２８】フローベクトルを表す図
【図２９】相似領域を表す図
【図３０】フローベクトルを表す図
【図３１】第２の発明に係る他の実施形態を示すブロック図
【図３２】フローベクトルを重ねた図
【図３３】第２の発明に係る他の実施形態を示すブロック図
【図３４】第２の発明に係る他の実施形態を示すブロック図
【図３５】変更前の位置変換を示す図
【図３６】変更後の位置変換を示す図
【図３７】図形が次第に変化する様子を示す図
【図３８】画素値変換の変更前の生成画像を示す図
【図３９】画素値変換の変更後の生成画像を示す図
【図４０】ブロック平均値を与えた図とエッジを与えた図および生成画像を示す図
【図４１】第２の発明に係る他の実施形態を示すブロック図
【図４２】従来のフラクタル符号化器を示すブロック図
【図４３】従来のフラクタル復号化器を示すブロック図
【符号の説明】
【００８３】
１１…入力符号
１２…写像部
１３…写像点位置
１４…写像点位置情報格納メモリ
１５…被写像点の位置情報
１６…属性決定部
１７…属性情報
２１…写像点位置情報格納メモリ
２２…写像点の位置情報
２３…差分器
２４…写像点位置情報の差
２５…周期検出部
２６…属性情報
３１…画素値決定部
３２…初期点
３３…選択部
３４…被写像点情報
３５，３６…比較部
３７，３８…比較結果
４１…ブロック特定情報
４２…ブロック特定情報格納メモリ
４３…ブロック特定情報
４４…画素値格納メモリ
４５…画素値
４６…画素値変換部
４７…画素値
４８…再生値
【図１】
2005339576.tif 000008
【図２】
2005339576.tif 000009
【図３】
2005339576.tif 000010
【図４】
2005339576.tif 000011
【図５】
2005339576.tif 000012
【図６】
2005339576.tif 000013
【図７】
2005339576.tif 000014
【図８】
2005339576.tif 000015
【図９】
2005339576.tif 000016
【図１０】
2005339576.tif 000017
【図１１】
2005339576.tif 000018
【図１２】
2005339576.tif 000019
【図１３】
2005339576.tif 000020
【図１４】
2005339576.tif 000021
【図１５】
2005339576.tif 000022
【図１６】
2005339576.tif 000023
【図１７】
2005339576.tif 000024
【図１８】
2005339576.tif 000025
【図１９】
2005339576.tif 000026
【図２０】
2005339576.tif 000027
【図２１】
2005339576.tif 000028
【図２２】
2005339576.tif 000029
【図２３】
2005339576.tif 000030
【図２４】
2005339576.tif 000031
【図２５】
2005339576.tif 000032
【図２６】
2005339576.tif 000033
【図２７】
2005339576.tif 000034
【図２８】
2005339576.tif 000035
【図２９】
2005339576.tif 000036
【図３０】
2005339576.tif 000037
【図３１】
2005339576.tif 000038
【図３２】
2005339576.tif 000039
【図３３】
2005339576.tif 000040
【図３４】
2005339576.tif 000041
【図３５】
2005339576.tif 000042
【図３６】
2005339576.tif 000043
【図３７】
2005339576.tif 000044
【図３８】
2005339576.tif 000045
【図３９】
2005339576.tif 000046
【図４０】
2005339576.tif 000047
【図４１】
2005339576.tif 000048
【図４２】
2005339576.tif 000049
【図４３】
2005339576.tif 000050