(57)【特許請求の範囲】
【請求項１】
複数の座標軸のいずれかにそれぞれ平行な複数の線分で構成されるデジタル曲線のフラクタル次元を変換する方法であって、
（ａ）ＣＰＵが、前記デジタル曲線を表わすデジタル曲線データを、右折、直進、および左折の３つの符号語で構成されるチェーン符号に符号化してメモリに格納する工程と、
（ｂ）ＣＰＵが、メモリから前記チェーン符号を読み出し、前記チェーン符号に含まれる各符号語を処理対象として、所定の変換規則に従って前記処理対象の符号語を複数の符号語で構成される符号語列に変換し、この際、前記処理対象の符号語で表わされるベクトル対の前半ベクトルと後半ベクトルのうちの所定の一方が、前記変換された符号語列で表わされるベクトル列の先頭ベクトルと後端ベクトルのうちの所定の一方と少なくとも部分的に重なるように前記変換を実行し、これによって、変換チェーン符号を生成してメモリに格納する工程と、
（ｃ）ＣＰＵが、メモリから前記変換チェーン符号を読み出し、前記変換チェーン符号を復号化することによって、前記デジタル曲線よりも高いフラクタル次元を有する変換デジタル曲線を表わす変換デジタル曲線データを生成する工程と、
を備えるデジタル曲線のフラクタル次元変換方法。
【請求項２】
請求項１記載のデジタル曲線のフラクタル次元変換方法であって、
前記変換規則は、チェーン符号に使用される３つの符号語のそれぞれを、右折、直進、および左折の３つの境界条件に応じて複数の符号語にそれぞれ置換する規則を含み、
前記工程（ｂ）は、
（１）前記処理対象の符号語に関して前記３つの境界条件の１つを選択する工程と、
（２）前記選択された境界条件の下で、前記変換規則に従って前記処理対象の符号語を１つの符号語列に変換する工程と、を含む、
デジタル曲線のフラクタル次元変換方法。
【請求項３】
請求項２記載のデジタル曲線のフラクタル次元変換方法であって、さらに、
前記３つの境界条件の１つを選択するための第１の選択確率をそれぞれ設定する工程を含み、
前記工程（２）は、
（ｉ）前記第１の選択確率に応じて前記３つの境界条件の１つを選択する工程を含む、
デジタル曲線のフラクタル次元変換方法。
【請求項４】
請求項３記載のデジタル曲線のフラクタル次元変換方法であって、
前記変換規則は、１つの境界条件に応じて１つの符号語から複数の符号語列に置換される規則を含み、
前記方法は、さらに、前記変換規則に従って１つの符号語が複数の符号語列に変換され得る場合に、前記複数の符号語列の１つを選択するための第２の選択確率を設定する工程を含むとともに、
前記工程（ｉ）は、前記処理対象の符号語が、前記選択された境界条件に応じて複数の符号語列に変換され得る場合には、前記第２の選択確率に応じて前記複数の符号語列の１つを選択する工程を含む、
デジタル曲線のフラクタル次元変換方法。
【請求項５】
請求項１ないし４のいずれかに記載のデジタル曲線のフラクタル次元変換方法であって、
前記工程（ｂ）は、
前記チェーン符号の先頭の符号語を無変換に保つ工程と、
前記変換チェーン符号列の後端に所定の符号語を付加する工程と、
を含むデジタル曲線のフラクタル次元変換方法。
【請求項６】
請求項１ないし５のいずれかに記載のデジタル曲線のフラクタル次元変換方法であって、さらに、
前記工程（ｂ）を所望の回数再帰的に繰返す工程を備える、
デジタル曲線のフラクタル次元変換方法。
【請求項７】
請求項４記載のデジタル曲線のフラクタル次元変換方法であって、さらに、
前記工程（ｂ）を所望の回数再帰的に繰返す工程と、
前記工程（ｂ）の繰り返し回数と、前記第１の選択確率と、前記第２の選択確率との組み合わせに応じて、所定の基本曲線に関して得られるフラクタル次元を予め測定し、前記繰り返し回数と前記第１と第２の選択確率と前記フラクタル次元との関係を記憶する工程と、
前記工程（ｂ）の前に、前記繰り返し回数と所望のフラクタル次元とを指定する工程と、
前記工程（ｂ）の前に、前記繰り返し回数と前記第１と第２の選択確率と前記フラクタル次元との関係に従って、指定された繰り返し回数で前記所望のフラクタル次元が得られるように前記第１と第２の選択確率を設定する工程と、
を備える、デジタル曲線のフラクタル次元変換方法。
【請求項８】
複数の座標軸のいずれかにそれぞれ平行な複数の線分で構成されるデジタル曲線のフラクタル次元を変換する装置であって、
前記デジタル曲線を表わすデジタル曲線データを、右折、直進、および左折の３つの符号語で構成されるチェーン符号に符号化する符号化手段と、
前記チェーン符号に含まれる各符号語を処理対象として、所定の変換規則に従って前記処理対象の符号語を複数の符号語で構成される符号語列に変換し、この際、前記処理対象の符号語で表わされるベクトル対の前半ベクトルと後半ベクトルのうちの所定の一方が、前記変換された符号語列で表わされるベクトル列の先頭ベクトルと後端ベクトルのうちの所定の一方と少なくとも部分的に重なるように前記変換を実行し、これによって、変換チェーン符号を生成する変換手段と、
前記変換チェーン符号を復号化することによって、前記デジタル曲線よりも高いフラクタル次元を有する変換デジタル曲線を表わす変換デジタル曲線データを生成する復号化手段と、
を備えるデジタル曲線のフラクタル次元変換装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、複数の座標軸のいずれかにそれぞれ平行な複数の線分で構成されるデジタル曲線のフラクタル次元を変換する方法および装置に関する。
【０００２】
【従来の技術】
曲線の複雑さを定量的に決定する指標として、フラクタル次元が使用される。図２４は、フラクタル次元を測定するためのボックスカウンティング法と呼ばれる方法を示す説明図である。図２４（Ａ）のような任意の曲線Ｌに関するフラクタル次元を求める際には、まず、一辺の幅ｄの正方形を始点Ｙ０に配置する。そして、この正方形と曲線Ｌとの交点Ｙ１を求める。次に、この交点Ｙ１を正方形の中心に再設定して、正方形と曲線Ｌとの交点Ｙ２を再度求める。こうして、曲線Ｌを正方形によって順次覆って行くと、曲線Ｌの全体を覆うために必要な正方形の個数Ｎ（ｄ）が得られる。この個数Ｎ（ｄ）は、正方形の一辺の幅ｄの関数である。そして、一辺の幅ｄを変化させて、曲線Ｌを覆うために必要な正方形の個数Ｎ（ｄ）をそれぞれ求める。図２４（Ｂ）は、正方形の個数Ｎ（ｄ）と一辺の幅ｄの関係を両対数にプロットしたものである。図２４（Ｂ）に示されているように、フラクタル次元Ｆｄｉｍ  はこのグラフの傾きで定義される。
【０００３】
なお、フラクタル次元は、曲線Ｌのサイズに依存しない。例えば、曲線Ｌを単純にＭ倍に拡大すれば、図２４（Ｂ）の曲線が、ｌｎＭだけ上にシフトするだけである。従って、単純な拡大／縮小によってはフラクタル次元は変化しない。このように、フラクタル次元は、曲線のサイズに依存せずに、その複雑さを示す指標である。
【０００４】
なお、「フラクタル」という言葉は、曲線（図形）の一部を拡大してもその内部に同種の構造が埋め込まれているような状態を意味する。しかし、「フラクタル次元」は、図２４で説明したように、上述のようなフラクタルな曲線のみに関する指標ではなく、あらゆる曲線に関してフラクタル次元を測定することができる。
【０００５】
一般に、曲線のフラクタル次元を増大させれば、曲線を拡大したり、曲線の解像度を増大させたりする場合に、自然なゆらぎを与えることができる。
【０００６】
曲線のフラクタル次元を増大させる方法としては、例えば中点変位法が知られている。図２５は、中点変位法の概要を示す説明図である。ここでは、２つの点Ｖ１，Ｖ２の間の直線Ｌ１２をフラクタル化する場合について説明する。図２５（Ａ）に示す１回目の変換では、直線Ｌ１２の中点ＭＶから、直線Ｌ１２に垂直な方向に点Ｖ３を取る。中点ＭＶと点Ｖ３との間の距離は、指定されたフラクタル次元に依存して決定される。すなわち、指定されたフラクタル次元が大きいほど、中点ＭＶと点Ｖ３との間の距離も大きくなる。
【０００７】
図２５（Ｂ）に示す２回目の変換では、点Ｖ１と点Ｖ３との間の直線、および、点Ｖ３と点Ｖ２との間の直線がそれぞれフラクタル化される。すなわち、点Ｖ１と点Ｖ３との間に新たな点Ｖ４が設定され、点Ｖ３と点Ｖ２との間に新たな点Ｖ５が設定される。但し、点Ｖ４と点Ｖ５の位置は、３つの点Ｖ１，Ｖ３，Ｖ２を通る直線列の進行方向（例えば点Ｖ１から点Ｖ２に向かう方向）にそって逆向きになるように設定される。図２５（Ｃ）は、３回目の変換を示している。このように、再帰的に中点変位法によるフラクタル化を実行することによって、フラクタル次元を増大させることができる。すなわち、比較的単純な曲線を、より複雑な曲線に変換することができる。なお、この明細書では、「曲線」という言葉は、直線も含む広義の用語として使用されている。
【０００８】
図２５（Ａ）から図２５（Ｃ）に示すように、曲線の複雑さを増加させることは、曲線の解像度を増加させることとも考えることができる。例えば、図２５（Ａ）において３つの点Ｖ１，Ｖ３，Ｖ２で構成される曲線は、元の直線Ｌ１２の解像度を２倍に増加させたものと見ることができる。このように、曲線の全体的なサイズを同一に保ったままで曲線のフラクタル次元を増加させる処理は、曲線の解像度を増大させることに対応する。一方、隣接する座標格子点同士の距離を同一に保ったままで曲線のフラクタル次元を増加させると、曲線が拡大される。このように、曲線のフラクタル次元の増大は、曲線に自然なゆらぎを与えつつ曲線の解像度を増大したり、曲線を拡大したりする場合に利用することができる。
【０００９】
【発明が解決しようとする課題】
しかし、中点変位法は、デジタル曲線に適用することが困難であるという問題がある。ここで、「デジタル曲線」とは、２つの座標軸のいずれかにそれぞれ平行な複数の線分で構成される曲線を言う。例えば、通常使用される直交ｘ−ｙ座標系においては、デジタル曲線はｘ軸に平行な線分と、ｙ軸に平行な線分とによって構成される。中点変位法では、図２５に示すように、新たに設定される点の位置が、座標格子の格子点に一致しない場合が多い。従って、中点変位法を適用して、デジタル曲線のフラクタル次元を変換することは困難である。
【００１０】
この発明は、従来技術における上述の課題を解決するためになされたものであり、デジタル曲線のフラクタル次元を変換することを目的とする。
【００１１】
【課題を解決するための手段およびその作用・効果】
上述の課題の少なくとも一部を解決するため、第１の発明は、複数の座標軸のいずれかにそれぞれ平行な複数の線分で構成されるデジタル曲線のフラクタル次元を変換する方法であって、
（ａ）ＣＰＵが、前記デジタル曲線を表わすデジタル曲線データを、右折、直進、および左折の３つの符号語で構成されるチェーン符号に符号化してメモリに格納する工程と、
（ｂ）ＣＰＵが、メモリから前記チェーン符号を読み出し、前記チェーン符号に含まれる各符号語を処理対象として、所定の変換規則に従って前記処理対象の符号語を複数の符号語で構成される符号語列に変換し、この際、前記処理対象の符号語で表わされるベクトル対の前半ベクトルと後半ベクトルのうちの所定の一方が、前記変換された符号語列で表わされるベクトル列の先頭ベクトルと後端ベクトルのうちの所定の一方と少なくとも部分的に重なるように前記変換を実行し、これによって、変換チェーン符号を生成してメモリに格納する工程と、
（ｃ）ＣＰＵが、メモリから前記変換チェーン符号を読み出し、前記変換チェーン符号を復号化することによって、前記デジタル曲線よりも高いフラクタル次元を有する変換デジタル曲線を表わす変換デジタル曲線データを生成する工程と、
を備える。
【００１２】
第１の発明によれば、デジタル曲線をチェーン符号に置き換え、チェーン符号の各符号語を符号語列に変換えることによって、フラクタル次元を増大させている。チェーン符号は、右折、直進、および左折の３つの符号語で構成されているので、チェーン符号で表わされる曲線はデジタル曲線である。従って、こうして変換された変換チェーン符号を復号化することによって、より高いフラクタル次元を有するデジタル曲線を得ることができる。
【００１３】
前記第１の発明において、前記変換規則は、チェーン符号に使用される３つの符号語のそれぞれを、右折、直進、および左折の３つの境界条件に応じて複数の符号語にそれぞれ置換する規則を含み、
前記工程（ｂ）は、
（１）前記処理対象の符号語に関して前記３つの境界条件の１つを選択する工程と、
（２）前記選択された境界条件の下で、前記変換規則に従って前記処理対象の符号語を１つの符号語列に変換する工程と、を含む、ことが好ましい。
【００１４】
こうすれば、３つの境界条件に応じて各符号語が符号語列に変換されるので、１つの符号語から種々の符号語列に容易に変換することができる。
【００１５】
上記第１の発明は、さらに、前記３つの境界条件の１つを選択するための第１の選択確率をそれぞれ設定する工程を含み、
前記工程（２）は、
（ｉ）前記第１の選択確率に応じて前記３つの境界条件の１つを選択する工程を含む、ことが好ましい。
【００１６】
こうすれば、３つの境界条件が確率的に選択されるので、デジタル曲線のランダムな複雑さを増大させることができる。
【００１７】
上記第１の発明において、前記変換規則は、１つの境界条件に応じて１つの符号語から複数の符号語列に置換される規則を含み、
前記方法は、さらに、前記変換規則に従って１つの符号語が複数の符号語列に変換され得る場合に、前記複数の符号語列の１つを選択するための第２の選択確率を設定する工程を含むとともに、
前記工程（ｉ）は、前記処理対象の符号語が、前記選択された境界条件に応じて複数の符号語列に変換され得る場合には、前記第２の選択確率に応じて前記複数の符号語列の１つを選択する工程を含む、ことが好ましい。
【００１８】
こうすれば、変換の候補となる符号語列が複数存在する場合に、その中の１つを確率的に選択できる。従って、デジタル曲線のランダムな複雑さをさらに増大させることができる。
【００１９】
上記第１の発明において、前記工程（ｂ）は、
前記チェーン符号の先頭の符号語を無変換に保つ工程と、
前記変換チェーン符号列の後端に所定の符号語を付加する工程と、
を含むことが好ましい。
【００２０】
こうすれば、元のデジタル曲線を構成する輪郭点を通るように変換デジタル曲線を作成することができる。
【００２１】
上記第１の発明は、さらに、
前記工程（ｂ）を所望の回数再帰的に繰返す工程を備える、ことが好ましい。
【００２２】
工程（ｂ）における変換を再帰的に繰返すことによって、フラクタル次元を所望の値の付近にまで増大させることができる。
【００２３】
上記第１の発明は、さらに、
前記工程（ｂ）を所望の回数再帰的に繰返す工程と、
前記工程（ｂ）の繰り返し回数と、前記第１の選択確率と、前記第２の選択確率との組み合わせに応じて、所定の基本曲線に関して得られるフラクタル次元を予め測定し、前記繰り返し回数と前記第１と第２の選択確率と前記フラクタル次元との関係を記憶する工程と、
前記工程（ｂ）の前に、前記繰り返し回数と所望のフラクタル次元とを指定する工程と、
前記工程（ｂ）の前に、前記繰り返し回数と前記第１と第２の選択確率と前記フラクタル次元との関係に従って、指定された繰り返し回数で前記所望のフラクタル次元が得られるように前記第１と第２の選択確率を設定する工程と、
を備えることが好ましい。
【００２４】
こうすれば、所望のフラクタル次元を有するデジタル曲線を作成することができる。
【００２５】
第２の発明は、２つの座標軸のいずれかにそれぞれ平行な複数の線分で構成されるデジタル曲線のフラクタル次元を変換する装置であって、
前記デジタル曲線を表わすデジタル曲線データを、右折、直進、および左折の３つの符号語で構成されるチェーン符号に符号化する符号化手段と、
前記チェーン符号に含まれる各符号語を処理対象として、所定の変換規則に従って前記処理対象の符号語を複数の符号語で構成される符号語列に変換し、この際、前記処理対象の符号語で表わされるベクトル対の前半ベクトルと後半ベクトルのうちの所定の一方が、前記変換された符号語列で表わされるベクトル列の先頭ベクトルと後端ベクトルのうちの所定の一方と少なくとも部分的に重なるように前記変換を実行し、これによって、変換チェーン符号を生成する変換手段と、
前記変換チェーン符号を復号化することによって、前記デジタル曲線よりも高いフラクタル次元を有する変換デジタル曲線を表わす変換デジタル曲線データを生成する復号化手段と、を備える。
【００２６】
第２の発明によれば、上記第１の発明と同様に、より高いフラクタル次元を有するデジタル曲線を得ることができる。
【００２７】
【発明の他の態様】
この発明は、以下のような他の態様も含んでいる。第１の態様は、上述した第１の発明の各態様において記述した各工程を達成するための手段を、第２の発明に備えるようにしたものである。
【００２８】
第２の態様は、コンピュータシステムのマイクロプロセッサによって実行されることによって、上記の発明の各工程または各手段を実現するソフトウェアプログラムを格納した携帯型記憶媒体である。
【００２９】
第３の態様は、コンピュータシステムのマイクロプロセッサによって実行されることによって、上記の発明の各工程または各手段を実現するソフトウェアプログラムを通信回線を介して供給するプログラム供給装置である。
【００３０】
【発明の実施の形態】
Ａ．装置の構成：
次に、本発明の実施の形態を実施例に基づき説明する。図１は、この発明の実施例を適用する画像処理装置の構成を示すブロック図である。この画像処理装置は、演算部４０と、操作部４２と、画像出力部４４とを備える汎用コンピュータシステムとして構成されている。
【００３１】
演算部４０は、ＣＰＵ５０と、メインメモリとしてのＲＯＭ５２およびＲＡＭ５４と、外部記憶装置としてのハードディスク装置５６とを備えている。操作部４２は、キーボード６０と、マウス６２と、ディジタイザ６４とを備えている。また、画像出力部４４は、カラーＣＲＴ７０と、フルカラープリンタ７２とを備えている。
【００３２】
図２は、演算部４０によって実現される種々の機能を示す機能ブロック図である。すなわち、演算部４０は、デジタル曲線記憶部８０と、チェーン符号化部８２と、符号メモリ８４と、チェーン符号拡大部８６と、コードブック記憶部８８と、復号化部９０と、処理済デジタル曲線記憶部９２と、の機能をそれぞれ実現する。
【００３３】
デジタル曲線記憶部８０は、処理前のデジタル曲線を表わすデジタル曲線データを記憶する。チェーン符号化部８２は、デジタル曲線データを、３つの符号語「ｒ」，「ｓ」，「ｌ」で構成されるチェーン符号に変換する。第１の符号語「ｒ」は右折を表わし、第２の符号語「ｓ」は直進を、また、第３の符号語「ｌ」は左折を表わす。なお、チェーン符号の符号語と符号化方法の詳細については後述する。符号メモリ８４は、チェーン符号を記憶する。
【００３４】
チェーン符号拡大部８６は、チェーン符号に含まれる各符号語を、複数の符号語を含む符号語列にそれぞれ変換することによって、デジタル曲線のフラクタル次元を増大させる。チェーン符号拡大部８６の機能の詳細については後述する。コードブック記憶部８８は、チェーン符号拡大部８６に使用されるコードブック（後述する）を記憶する。
【００３５】
復号化部９０は、変換後のチェーン符号を復号化することによって、高フラクタル次元のデジタル曲線データ（変換デジタル曲線データ）を生成する。処理済デジタル曲線記憶部９２は、変換デジタル曲線データを記憶する。
【００３６】
なお、チェーン符号化部８２は、本発明における符号化手段に相当する。また、チェーン符号拡大部８６は本発明における変換手段に相当し、復号化部９０は復号化手段に相当する。また、コードブック記憶部８８に記憶されているコードブックは、本発明における変換規則に相当する。
【００３７】
図２の各部の機能を実現するソフトウェアプログラム（アプリケーションプログラム）は、フロッピディスクやＣＤ−ＲＯＭ等の携帯型記憶媒体（可搬型記憶媒体）からコンピュータシステムのメインメモリ（すなわちＲＡＭ５４）または外部記憶装置（すなわちハードディスク装置５６）に転送される。あるいは、通信回線を介してプログラム供給装置からコンピュータシステムに供給するようにしてもよい。
【００３８】
Ｂ．処理の全体手順と処理内容：
図３は、実施例における処理の全体手順を示すフローチャートである。ステップＳ３１では、チェーン符号化部８２がデジタル曲線のチェーン符号化を行なう。
【００３９】
図４は、チェーン符号の符号語ｒ，ｓ，ｌの意味を示す説明図である。デジタル曲線（以下、「線図形」とも呼ぶ）は単位長さのベクトルが順次連結されたベクトル列であると考えることができる。図４（ａ）に示すように、ある入力ベクトルの次の単位ベクトルは、入力ベクトルから右折、左折、直進のいずれかの方向を有している。チェーン符号は、隣接する２つの単位ベクトルの関係を、右折「ｒ」、直進「ｓ」、および、左折「ｌ」の３つの符号語で符号化したものである。なお、チェーン符号は、ｒｌｓ符号とも呼ばれる。図４（Ｂ）に示されているように、デジタル曲線を符号化する際には、始点Ｐ０の座標と、始点Ｐ０に向かうダミー初期ベクトルＤＩＶが設定される。チェーン符号は、このダミー初期ベクトルＤＩＶに続く単位ベクトル列を表わす符号語で構成される。
【００４０】
図５は、デジタル曲線を構成する単位ベクトルの向きと方向値との関係、および、方向値の変化とチェーン符号の符号語との関係を示す説明図である。「方向値」とは、デジタル曲線の方向を示すために使用している値である。この実施例では、図５（Ａ）に示すように、左手系の直交ｘ−ｙ座標系において、ｘ方向に方向値「０」を、ｙ方向に方向値「１」を、−ｘ方向に方向値「２」を、−ｙ方向に方向値「３」をそれぞれ割り当てている。図５（Ｂ）に示すように、右折ｒは、方向値に１を加算する演算に対応する（キャリは無視する）。また、直進ｓは方向値が変化しない演算に対応し、左折は方向値から１を減算する演算に対応する（ボローは無視する）。なお、図５（Ｂ）の右側において、「ｍｏｄ４」と記載されているのは、整数を４で割った余りである０〜３の値のみを採用すること、すなわち、２ビットの演算においてキャリーやボローを無視することを意味している。
【００４１】
図６は、チェーン符号化の例を示している。始点Ｐ０は、デジタル曲線の端部に存在する輪郭点である。デジタル曲線が閉曲線である場合には、任意の輪郭点を始点Ｐ０として指定することができる。ダミー初期ベクトルＤＩＶは、予め決定された一定の向きを有している。図６（Ａ）の例では、ダミー初期ベクトルＤＩＶは右向きであるが、任意の向きを取ることが可能である。図６（Ｂ）の中央の２つの欄には、各点Ｐ０〜Ｐ７における入力ベクトルと出力ベクトルの向きが方向値で表わされている。各点における入力ベクトルと出力ベクトルの方向値の変化は、図５（Ｂ）に示す規則に従ってチェーン符号の符号語に変換される。変換されたチェーン符号は、符号メモリ８４に記憶される。なお、チェーン符号化の詳細な手順については後述する。
【００４２】
こうして、図３のステップＳ３１において、デジタル曲線がチェーン符号化されると、ステップＳ３２において、フラクタル次元変換の処理回数（「変換回数」とも呼ぶ）をユーザが指定する。ステップＳ３３では、フラクタル次元変換に使用する２つの制御パラメータＰｓ，Ｐｆをユーザが指定する。これらのパラメータＰｓ，Ｐｆについては後述する。
【００４３】
ステップＳ３４では、チェーン符号拡大部８６がフラクタル次元変換を１回実行する。このフラクタル次元変換は、チェーン符号の各符号語を、ほぼ等価な符号語列にそれぞれ置換することによって、デジタル曲線のフラクタル次元を増大させる処理である。
【００４４】
図７は、フラクタル次元を増大させた時の座標格子の格子点の増加と、チェーン符号に対応する入力ベクトルおよび出力ベクトルの変化とを示す説明図である。図７の例では、フラクタル次元の増大に伴って、隣接する座標格子点の間隔を１／２に縮小している。この場合には、フラクタル次元の増大は解像度の増大を意味する。
【００４５】
図７（Ａ１）の９つの黒丸は元の格子点を示しており、図７（Ａ２）の８つの白丸は解像度を増大させた時に図７（Ａ１）の中央の格子点Ｐｃｅｎｔの周囲に設けられる新たな格子点を示している。この８つの新たな格子点と元の格子点Ｐｃｅｎｔで構成される矩形を「セルＣＬ」と呼ぶ。
【００４６】
図７に示すフラクタル次元の増大では、元の各格子点の間に新たな格子点が追加されるので、解像度は２倍に増大する。なお、このように解像度を２倍に増大することは、１つの格子点Ｐｃｅｎｔを、１つのセルＣＬに変換することと等価である。
【００４７】
解像度の増大に伴って、各符号語で表わされる入力ベクトルと出力ベクトルも変換される。図７（Ａ１）に示すように、元の格子点Ｐｃｅｎｔを通るような右折を示す符号語ｒは、格子点Ｐｃｅｎｔに入る入力ベクトルＶｉｎと、格子点Ｐｃｅｎｔから出る出力ベクトルＶｏｕｔ  の向きの変化を表わしている。この符号語ｒの解像度を増大して得られる符号語列は、図７（Ａ２）に示すように、セルＣＬに入る入力ベクトルＶｉｎ’  と、セルＣＬの中心の格子点Ｐｃｅｎｔからセル端部の格子点に至る出力ベクトルＶｏｕｔ’とを含むベクトル列を表わす。但し、新たな入力ベクトルＶｉｎ’  と出力ベクトルＶｏｕｔ’の間を連結するベクトルについては任意性があるので、図７では図示を省略している。この実施例では、ベクトル列がセルＣＬに入る始点Ｑｉｎと、ベクトル列がセルＣＬから出る終点Ｑｏｕｔ  の位置は、セルＣＬのいずれかの辺の中央に限定される。
【００４８】
なお、セルＣＬへの入力ベクトルＶｉｎ’  は、１つ手前のセルの出力ベクトルと同じなので、１つ手前のセルの符号語列によって規定されている。従って、変換後の符号語列で表わされるベクトル列は、この入力ベクトルＶｉｎ’  から順次連結されて行き、出力ベクトルＶｏｕｔ’まで至るベクトル列である。セルＣＬ内におけるベクトル列にはある程度の任意性があり、以下で説明するコードブックに含まれているものの中から選択される。
【００４９】
図７で注意すべきことは、変換後の出力ベクトルＶｏｕｔ’が、セルＣＬの中心の格子点Ｐｃｅｎｔを通り、かつ、変換前の出力ベクトルＶｏｕｔ  と同じ方向を有するように設定されている点である。換言すれば、変換後の出力ベクトルＶｏｕｔ’は、変換前の出力ベクトルＶｏｕｔ  に部分的に（厳密には１／２だけ）重なるように決められている。こうすることによって、セルＣＬ内のベクトル列の連なり方に係わらず、解像度変換前のベクトル列と解像度変換後のベクトル列とがほぼ等価なものになる。換言すれば、曲線の通り方を大きく変えること無く、その解像度を向上させるようにすることができる。
【００５０】
図８は、フラクタル次元の増大によって曲線を拡大した時の座標格子の格子点を示す説明図であり、図７（Ａ１），（Ａ２）に対応するものである。図７（Ａ１），（Ａ２）と、図８（Ａ１），（Ａ２）とを比較すれば解るように、解像度の増大は、黒丸で示される元の格子点のピッチをそのまま保ち、白丸で示す格子点をそれらの中間に追加することによって、格子点のピッチを元の１／２にしつつ格子点数を増加させる処理である。一方、曲線の拡大は、黒丸で示される元の格子点のピッチを２倍にし、白丸で示す格子点をそれらの中間に追加することによって、格子点のピッチを元と同じに保ちつつ曲線のサイズを２倍にする処理である。このように、解像度の増大と曲線の拡大は、処理語の格子点のピッチ（すなわち画素ピッチ）を元の１／２にするか、元と同じに保つかの違いだけであり、フラクタル次元の増大としては実質的に等価な処理である。
【００５１】
図８に示される曲線の拡大処理においても、変換後の出力ベクトルＶｏｕｔ’が、セルＣＬの中心の格子点Ｐｃｅｎｔを通り、かつ、変換前の出力ベクトルＶｏｕｔ  と同じ方向を有するように設定されている点に注意すべきである。換言すれば、変換後の出力ベクトルＶｏｕｔ’は、変換前の出力ベクトルＶｏｕｔ  に重なるように（一致するように）決められている。
【００５２】
図９は、セルＣＬ内のベクトル列の通り方の例を示す説明図である。図９は、直進を示す符号語ｓの場合を示している。セルＣＬの始点Ｑｉｎから、セルＣＬの終点Ｑｏｕｔ  までを順次接続するベクトル列としては、図９（Ａ）〜（Ｃ）に示すものの他にも多数のものが考えられる。そこで、この実施例では、セルＣＬ内のベクトル列の連結の仕方に、以下のような制限を設けることによって、いくつかのベクトル列のみを許容している。
【００５３】
［制限１］：セルの終点Ｑｏｕｔ  に至る出力ベクトルＶｏｕｔ’が、セル中心の格子点Ｐｃｅｎｔを通り、かつ、その向きが変換前の出力ベクトルＶｏｕｔ  の向きに等しいこと。
［制限２］：セル内のベクトル列がセルの始点Ｑｉｎを通るような自己交差を起こさないこと。
【００５４】
上記制限１は、図７においてすでに説明した事項である。この制限１から、図９（Ｂ），（Ｃ）のベクトル列は許容されないことになる。なお、この制限１は、「変換後の出力ベクトルＶｏｕｔ’が、変換前の出力ベクトルＶｏｕｔ  と少なくとも部分的に重なること」と言い換えることもできる。
【００５５】
制限２の「自己交差」とは、図９（Ｂ）の左下の部分に示すように、ベクトル列がループを描くことを意味している。制限２は、「セルの始点Ｑｉｎを通るような自己交差」を禁止しているので、セルの始点Ｑｉｎを通らないような自己交差は許される。図９（Ｂ）に示すベクトル列は、「セルの始点Ｑｉｎを通るような自己交差」を含んでいるので、制限１のみでなく、制限２からも禁止される。
【００５６】
自己交差を禁止する理由は、自己交差を有するように曲線を変換してしまうと、元のベクトル列で定義されていた塗りつぶし領域に間違い生じてしまう、などの不具合が発生する可能性があるからである。この意味では、上記制限２の代わりに、「セル内のベクトル列が自己交差を起こさないこと」という制限を使用することが好ましい場合もある。なお、自己交差を起こしても不具合が生じない場合には、自己交差に関する制限を省略することも可能である。
【００５７】
また、上記制限１の代わりに、セルの始点におけるベクトルを制限事項とすることも可能である。このような制限は、「セルの始点Ｑｉｎから出る入力ベクトルＶｉｎ’  が、セル中心の格子点Ｐｃｅｎｔを通り、かつ、その向きが変換前の入力ベクトルＶｉｎの向きに等しいこと」、または、「変換後の入力ベクトルＶｉｎ’  が、変換前の入力ベクトルＶｉｎと少なくとも部分的に重なること」となる。
【００５８】
この実施例では、上記の制限１，２によって許容されるセル内のベクトル列を予めコードブックとして作成し、コードブック記憶部８８（図２）に登録しておく。図１０〜図１２は、フラクタル次元変換における変換規則を記述したコードブックの登録内容を示す説明図である。例えば、図１０の左端の欄は変換前の符号語（右折の符号語ｒ）を示し、２番目の欄は境界条件を、３番目の欄は変換後の符号語列（「置換符号語列」とも呼ぶ）を、４番目の欄は置換符号語列で表わされるベクトル列を、５番目の欄はその置換符号語列の採否をそれぞれ示している。図１１，図１２も同様である。
【００５９】
境界条件は、置換符号語列の最初の符号語として右折、直進、左折のいずれを使用するかを示す条件である。すなわち、境界条件には、右折「Ｒ」、直進「Ｓ」、左折「Ｌ」の３つの境界条件がある。ここで、大文字のＲ，Ｓ，Ｌを用いているのは、符号語と区別するための便宜のためである。採否の欄において「○」が付されている置換符号語列はコードブックに含まれるもの（すなわち許容されるもの）を示しており、「×」が付されている置換符号語列はコードブックに含まれないもの（すなわち許容されないもの）を示している。
【００６０】
３つの境界条件Ｒ，Ｓ，Ｌのいずれを選択するかは、後述するように、境界条件を選択する際の選択確率を表わす制御パラメータＰｓに従って決定される。また、同じ元の符号語から同じ境界条件で複数の符号語列に変換し得る場合もある（例えば図１０の境界条件「Ｓ」の場合）。このような場合には、これらの複数の候補の中から１つを選択する際の選択確率を表わす制御パラメータＰｆに従って選択が行なわれる。この処理についても後述する。
【００６１】
図１３は、図１０〜図１２に示すコードブックを用いて各符号語を符号語列に変換した例を示す説明図である。図１３（Ａ）に示すように、変換前の符号語列は［ｓｌｒｌ］である。図１３（Ｂ）は、変換後の符号語列の一例と、変換前の各符号語との対応を示している。図１３（Ｂ）の下部に示す符号語の変換は、図１０〜図１２に示すコードブックにおいて許容されているものである。
【００６２】
図１４は、図３のステップＳ３４におけるチェーン符号のフラクタル次元変換の詳細手順を示すフローチャートである。ステップＳ４１では、元の符号語列から処理対象となる符号語を１つ取出す。ステップＳ４２では、３つの境界条件から１つを選択するための乱数を発生させる。図１５（Ａ）は、境界条件の選択方法を示している。図３のステップＳ３において設定された第１の制御パラメータＰｓは、３つの境界条件Ｓ，Ｒ，Ｌの中から直進を示す境界条件Ｓを選択する選択確率を示している。この実施例では、右折を示す境界条件Ｒと左折を示す境界条件Ｌの選択確率は、（１−Ｐｓ）／２で互い等しく設定されている。従って、３つの境界条件Ｓ，Ｒ，Ｌの選択確率の合計は１である。図１４のステップＳ４２においては、０〜１の範囲の乱数を発生させる。その乱数の値に応じて図１５（Ａ）に示すように境界条件が１つ選択される。
【００６３】
ステップＳ４３では、同じ境界条件の下で選択の候補となる複数の符号語列から１つを選択する際に使用する選別用乱数を発生させる。図１５（Ｂ）は、同じ境界条件の下で選択の候補となる２つの符号語列の選択方法を示している。図３のステップＳ３において設定された第２の制御パラメータＰｆは、候補となる２つの符号語列（長符号語列と短符号語列）の中から長符号語列を選択する選択確率を示している。２つの符号語列の選択確率の合計は１である。なお図１５（Ｂ）おように、選択の候補となる符号語列を２つにしているのは、図１０ないし図１２に示されているコードブックにおいて、処理対象の符号語から同じ境界条件の下で選択の候補となる符号語列が２つ以下だからである。図１４のステップＳ４３においては、０〜１の範囲の乱数を発生させる。その乱数の値に応じて図１５（Ｂ）に示すように長符号語列と短符号語列のいずれかを選択するかが決定される。なお、選択の候補となる複数の符号語列のいずれを選択するか、を以下では「符号語列選別条件」と呼ぶ。
【００６４】
なお、コードブックにおいて、処理対象の符号語から同じ境界条件の下で選択の候補となる符号語列が３つ以上存在する場合には、その個数の選択確率を設定するようにすればよい。
【００６５】
図１４のステップＳ４４は、処理対象の符号語と、ステップＳ４２で決定された境界条件と、ステップＳ４３で決定された符号語列選別条件とに応じて、図１０〜図１２に示すコードブックを参照し、符号語列を１つ選択する。なお、ステップＳ４２において選択された境界条件に対応する置換符号語列がコードブック中に存在しない場合（例えば図１０の境界条件Ｒの場合）には、ステップＳ４４において再度乱数を発生させて、許容される置換符号語列が存在するまでステップＳ４２と同じ処理を実行する。
【００６６】
ここで、ステップＳ４２〜Ｓ４４において使用された２つの制御パラメータＰｓ，Ｐｆの役割を考察する。図１５（Ａ），（Ｂ）に示したように、処理対象の符号語を置換符号語列に変換する際には、乱数を用いてある程度確率的に変換を行なっている。この際、２つの制御パラメータＰｓ，Ｐｆを用いることによって、変換後の曲線のフラクタル次元を所望の値に制御することができる。フラクタル次元とは、前述のように、曲線の複雑さを表わす指標である。すなわち、フラクタル次元が高いと曲線に微妙な凹凸が多く、フラクタル次元が低いと微妙な凹凸が少ない。２つの制御パラメータＰｓ，Ｐｆがフラクタル次元を制御するパラメータとなることは、以下の考察から理解できる。第１の制御パラメータＰｓは、図１５（Ａ）に示すように、直進の境界条件Ｓを選択する確率である。従って、第１の制御パラメータＰｓは直進性を示すことになり、直進性の制御パラメータＰｓが大きいとフラクタル次元が低くなり、逆に、直進性の制御パラメータＰｓが小さいとフラクタル次元が高くなる。第２の制御パラメータＰｆは、図１５（Ｂ）に示すように、複数の候補符号語列から、より複雑な符号語列を選択する確率である。従って、第２のパラメータＰｆは複雑性を示すことになり、複雑性の制御パラメータＰｆが大きいとフラクタル次元が高くなり、逆に、複雑性の制御パラメータＰｆが小さいとフラクタル次元が低くなる。
【００６７】
図１６は、直進性の制御パラメータＰｓを１に設定し、複雑性の制御パラメータＰｆを０に設定した場合の処理結果を示す説明図である。Ｐｓ＝１では境界条件として常に直進Ｓが選択される。また、Ｐｆ＝０では２つの候補符号語列の内の短い方が常に選択される。このような場合には、図１０〜図１２に示されるコードブックを参照すれば理解できるように、解像度を増大しても元の曲線のままであり（図１６（Ａ））、また、曲線を拡大すると元の形状のまま単純に２倍に拡大される（図１６（Ｂ））。
【００６８】
このように、直進性の制御パラメータＰｓと複雑性の制御パラメータＰｆとの値を調整することによって、曲線の複雑さ、すなわちフラクタル次元を制御することができる。なお、直進性のパラメータＰｓで規定される３つの境界条件Ｒ，Ｓ，Ｌの選択確率（図１５（Ａ））は、本発明における第１の選択確率に相当する。また、複雑性のパラメータＰｆで規定される選択確率（図１５（Ｂ））は、本発明における第２の選択確率に相当する。但し、第１の選択確率としては、直進性を示す１つの制御パラメータＰｓの代わりに、３つの境界条件Ｒ，Ｓ，Ｌのそれぞれの選択確率を設定するようにすることも可能である。同様に、第２の選択確率としては、３つ以上の符号語列から１つを選択する際の選択確率をそれぞれ設定することも可能である。但し、直進性を示す１つの制御パラメータＰｓと複雑性を示す１つの制御パラメータＰｆとを用いれば、フラクタル次元変換後のデジタル曲線のフラクタル次元を、２つの制御パラメータＰｓ，Ｐｆで容易に制御することができるという利点がある。
【００６９】
こうして処理対象の符号語が符号語列に変換されると、図１４のステップＳ４５において、選択された置換符号語列を拡大符号語列に追加する。ここで、「拡大符号語列」とは、フラクタル次元変換の結果として得られるチェーン符号を意味しており、本発明における変換チェーン符号に相当する。拡大符号語列は、符号メモリ８４に格納される。
【００７０】
ステップＳ４６では、元の符号語列に含まれている各符号語についての変換処理がすべて終了したか否かが判断される。終了していなければ、ステップＳ４１に戻り、上述したステップＳ４１〜Ｓ４５の処理を繰返す。この結果、元のチェーン符号で表わされるデジタル曲線のフラクタル次元を増大した高フラクタル次元チェーン符号が生成される。
【００７１】
こうして、図１４に示すステップＳ３４の処理が終了すると、図３のステップＳ３５において、指定された変換回数Ｎの処理が終了したか否かが判断される。すなわち、ステップＳ３４の処理は、指定された変換回数Ｎだけ繰り返し実行する。この結果、元のデジタル曲線のフラクタル次元を増大した高フラクタル次元デジタル曲線を表わすような変換チェーン符号が得られる。例えば、フラクタル次元の増大によって解像度を増大させた場合には、元のデジタル曲線の解像度を２のＮ乗倍した解像度を有する高解像度デジタル曲線を表わすような変換チェーン符号が得られる。
【００７２】
ステップＳ３６では、変換チェーン符号を復号化することによって、高フラクタル次元デジタル曲線を表わすデジタル曲線データを生成する。図１７は、チェーン符号の復号化の例を示す説明図である。ここでは、説明の便宜上、図６に示したデジタル曲線のチェーン符号［ｓｌｒｌｒｓｒ］を復号化することを考える。図１７（Ａ）の左端から１番目の欄の点番号Ｐ０〜Ｐ６と、２番目の欄の符号語は、図６に示すものと同じである。チェーン符号の復号化には、もちろん、図５（Ｂ）に示したもとの同じチェーン符号化／復号化規則が使用される（図１７（Ｂ））。ところで、図６（Ａ）に示したように、チェーン符号化を行なう際には、始点Ｐ０の座標を設定するとともに、始点Ｐ０に至るダミー初期ベクトルＤＩＶを初期条件として設定していた。従って、復号化においても、始点Ｐ０の座標と、始点Ｐ０に至るダミー初期ベクトルＤＩＶ’を初期条件として設定する（図１７（Ｃ））。
【００７３】
この初期条件から、図１７（Ｂ）に示すチェーン符号化／復号化規則に従ってチェーン符号を復号化する。この結果、図１７（Ａ）に示すように、各符号語が入力ベクトルと出力ベクトルに変換される。入力ベクトルと出力ベクトルは単位ベクトルなので、これらのベクトルに従って始点Ｐ０の座標（１，５）から各点Ｐ１〜Ｐ６の座標を順次求めることができる。例えば、最初の符号語ｓからは、始点（１，５）への入力ベクトル（ダミー初期ベクトルＤＩＶ’）と同じ方向（方向値０）に単位長さだけ直進する出力ベクトルが得られるので、座標（２，５）が２番目の点Ｐ１の座標値として出力される（図１７（Ａ）の右端の欄）。２番目の点Ｐ１への入力ベクトルは、始点Ｐ０の出力ベクトルと同じである。従って、点Ｐ１から点Ｐ２に向かう出力ベクトルの向きは、点Ｐ１に関する符号語ｌで決定できる。こうして、符号語列に従って、図１７（Ｃ）に示すように、各点の座標値を順次決定していくことができる。
【００７４】
なお、図１７（Ｃ）の例では、連続する３つの点Ｐ４〜Ｐ６が一直線上に並んでいる。このような場合には、その両端の点Ｐ４，Ｐ６のみをデジタル曲線を構成する輪郭点として出力するようにしてもよい。
【００７５】
ところで、元のデジタル曲線が閉曲線である場合に、復号化された高フラクタル次元デジタル曲線が閉曲線にならない可能性もある。このような場合には、復号化された高フラクタル次元デジタル曲線の始点と終点を連結するように、曲線を修正すればよい。
【００７６】
あるいは、チェーン符号のフラクタル次元変換を以下のように工夫すれば、復号化された高フラクタル次元デジタル曲線の始点と終点を一致させることもできる。図１８は、このようなフラクタル次元変換の他の実施例を示す説明図であり、前述した図１３に対応するものである。図１８は、フラクタル次元変換によって解像度を増大した例である。
【００７７】
図１８（Ａ）に示す元の符号語列は図１３（Ａ）に示すものと同じである。図１８（Ｂ）に示す変換後の符号語列では、元の符号語列の最初の符号語ｓは無変換でそのままに保たれており、また、変換後の符号語列の後端には、直進を表わす符号語ｓが付加されている。なお、無変換に保たれる最初の符号語は直進を表わす符号語ｓでなくてもよく、任意であるが、最後に付加される符号語は直進を表わす符号語ｓが使用される。図１８（Ｂ）に示すように、このようにして変換された符号語列で表わされるベクトル列は、必ず元の点Ｐ０〜Ｐ４を通過する。従って、復号化の際に、変換前と同じダミー初期ベクトルＤＩＶ’と始点Ｐ０の座標とを設定すれば、デジタル曲線の始点Ｐ０と終点Ｐ４が元の位置に保たれる。元のデジタル曲線が閉曲線の場合には、変換された高フラクタル次元デジタル曲線も閉曲線となる。
【００７８】
図１９は、図１８のフラクタル次元変換方法に従ってデジタル曲線を拡大した場合の例を示す説明図である。図１９（Ａ）に示す元のデジタル曲線を表わすチェーン符号は［ｓｒｒｒ］である。これを１回拡大すると、図１９（Ｂ）に示すデジタル曲線を表わすチェーン符号が得られる。この時、先頭の符号語ｓは無変換であり、また、符号列の後端には直進を表わす符号語ｓが付加されている。図１９（Ｂ）の曲線を再度拡大すると、図１９（Ｃ）に示すデジタル曲線を表わすチェーン符号が得られる。この際にも、先頭の符号語が無変換に保たれており、また、符号列の後端には直進を表わす符号語ｓが付加される。このように、１回の拡大処理（フラクタル次元変換処理）のたびに、符号列の先頭の符号語を無変換に保つとともに、符号列の後端に直進を表わす符号語ｓを付加することによって、閉曲線のフラクタル次元を変換した後にも閉曲線を保つことができる。
【００７９】
なお、図１９（Ｃ）のベクトル列には、同じ線分上を逆向きのベクトルが通っている部分ＦＰ１，ＦＰ２（「重複ベクトル部」と呼ぶ）が存在する。チェーン符号の復号化の際には、このような重複ベクトル部ＦＰ１，ＦＰ２を削除（省略）するとともに、各重複ベクトル部ＦＰ１，ＦＰ２に付属している閉曲線（「局所閉曲線」と呼ぶ）を削除するようにしてもよい。すなわち、第１の重複ベクトル部ＦＰ１の削除に伴って、図１９（Ｄ）に示す第１の局所閉曲線ＬＣ１を削除し、第２の重複ベクトル部ＦＰ２の削除に伴って、第２の局所閉曲線ＬＣ２を削除する。こうして得られる曲線には、過度に入り組んだ曲線部分が無くなるので、好ましい場合がある。もちろん、図１９（Ｄ）のように重複ベクトル部とその局所閉曲線とを削除せずに、図１９（Ｃ）に示すデジタル曲線を使用することも可能である。また、局所閉曲線を残し、重複ベクトル部のみ削除してもよい。
【００８０】
図３のステップＳ３７では、こうして得られた処理済みのデジタル曲線が、処理済デジタル曲線記憶部９２（図２）から出力される。デジタル曲線の出力の形態としては、カラーＣＲＴ７０による表示や、フルカラープリンタ７２によるプリントアウト等がある。
【００８１】
図２０は、実施例でフラクタル次元変換を行なって得られた各種の図形のフラクタル次元を測定した結果を示している。なお、フラクタル次元の測定は、前述の図２４で説明したボックスカウンティング法を用いた。また、各図形のフラクタル次元変換としては、複雑性の制御パラメータＰｆの値を０．９一定に設定するとともに、変換回数Ｎをそれぞれ３回に固定し、直進性の制御パラメータＰｓを変えた８種類の変換を各図形について行なった。図２０（Ａ）の左端の欄は、直進性のパラメータＰｓの設定値を示し、左端から２番目の欄は水平直線についてフラクタル次元変換を行なった場合のフラクタル次元を示している。また、左端から３番目の欄は正方形、右端の欄は斜め４５°の直線ついてそれぞれフラクタル次元変換を行なった場合のフラクタル次元を示している。図２０（Ｂ）は、図２０（Ａ）の結果を示すグラフである。
【００８２】
図２０（Ｂ）から容易に解るように、直進性の制御パラメータＰｓと、フラクタル次元との間には、ほぼ直線的な強い負の相関があることが解る。複雑性の制御パラメータＰｆは、逆に、フラクタル次元との間にほぼ直線的な強い正の相関がある。従って、２つの制御パラメータＰｓ，Ｐｆによって、フラクタル次元を制御できることが解る。また、こうして得られるフラクタル次元の値としては１．０〜１．８程度のかなり高い値が得られる。平面上の２次元曲線におけるフラクタル次元の理論的な限界値は２．０である。従って、上記のフラクタル次元の測定値は、理論的な限界値に近く、かなり高いことがわかる。すなわち、この実施例では、デジタル曲線のフラクタル次元をかなり高い値に設定できるという利点がある。
【００８３】
ところで、フラクタル次元変換の変換回数Ｎ（すなわち変換処理の再帰的な繰り返し回数）と２つの制御パラメータＰｓ，Ｐｆの値の組み合わせ毎に、典型的な曲線に関してフラクタル次元を測定しておくことができる。この測定データに基づき、変換回数Ｎと２つの制御パラメータＰｓ，Ｐｆとに従って、変換後の曲線のフラクタル次元がどの程度になるかを予測することができる。例えば、変換回数を決めれば、図２０（Ｂ）に示すような関係（２つの制御パラメータＰｓ，Ｐｆとフラクタル次元との関係）から、所望のフラクタル次元を達成するような２つの制御パラメータＰｓ，Ｐｆの値を決定することができる。
【００８４】
フラクタル次元を測定する対象となる典型的な曲線（基本曲線）としては、方向が異なる２種類の直線を少なくとも採用すればよい。例えば、水平直線と斜め４５°の直線の２種類を典型的な曲線として採用することができる。こうすれば、任意のデジタル曲線を、これらの典型的な曲線の組み合わせと考えて、その変換後のフラクタル次元を予測することができる。
【００８５】
図２１は、フラクタル次元の予測結果の例を示す説明図である。元のデジタル曲線としては、斜め４５°に傾けた正方形を用いている。図２１（Ｂ１）〜（Ｂ３）に示すデジタル曲線は、それぞれ直進性の制御パラメータＰｓを０．８８５，０．６３５，０．３７５に設定した場合に得られる図形である。図２１（Ａ）の下部には、フラクタル次元Ｆｄｉｍ  の予想値と実測値とが示されている。これから解るように、この実施例で得られたフラクタル次元Ｆｄｉｍ  の予想値と実測値は極めてよく一致する。
【００８６】
以上のように、この実施例においては、デジタル曲線をｒｌｓ符号化した後に、その各符号語をこれとほぼ等価な符号語列に変換することによって、デジタル曲線のフラクタル次元を高める。従って、デジタル曲線の解像度増大やデジタル曲線の拡大を行なう際に、自然なゆらぎを与えることができる。特に、各符号語を符号語列に変換する際に、予め準備されたコードブックを利用するようにしたので、複雑な演算を行なうことなく高速に変換を行なうことができるという利点がある。また、２つの制御パラメータＰｓ，Ｐｆを調整することによって、所望のフラクタル次元を有するデジタル曲線を作成することができるという利点もある。
【００８７】
Ｃ．曲線のチェーン符号化の詳細手順：
図２２は、図３のステップＳ３１におけるデジタル曲線のチェーン符号化の詳細手順を示すフローチャートである。なお、以下の説明では、デジタル曲線を構成する点列の点数をｎとし、点列の個々の点を「角点」と呼ぶ。図２２で使用されている記号は、それぞれ以下の意味を有している。
【００８８】
ｋｐ［ｉ］（ｉ＝０〜ｎ−１）：デジタル曲線を構成するｎ個の角点の座標。
ｐ＿ｎｏｗ：現在の点の座標。
ｐ＿ｎｅｘｔ  ：現在の点ｐ＿ｎｏｗから単位長だけ進んだ次の点の座標。
ｐｒｅｖ＿ｄｉｒ  ：現在の点に入る入力ベクトルの向きを示す方向値。
ｎｅｘｔ＿ｄｉｒ  ：現在の点から出る出力ベクトルの向きを示す方向値。
【００８９】
なお、辺の向きと方向値ｐｒｅｖ＿ｄｉｒ，ｎｅｘｔ＿ｄｉｒとの関係は、前述した図５（Ａ）に示されているものを使用する。
【００９０】
ステップＳ５１では、初期の符号語として直進を示す符号語ｓに設定し、また、角点を示す添字ｉを１に設定する。ステップＳ５２では、始点座標ｋｐ［０］  と次の点の座標ｋｐ［１］  から、方向値ｐｒｅｖ＿ｄｉｒを算出する。これは、座標の差分（ｋｐ［１］−ｋｐ［０］  ）＝（△ｘ，△ｙ）のｘ成分△ｘとｙ成分△ｙの値から判断できる。デジタル曲線では、各線分がｘ軸またはｙ軸に平行なので、△ｘと△ｙの一方は０である。従って、座標値の差分△ｘ，△ｙの中で０でない方の値の正負の符号によって、始点から次の点に向かう方向の方向値ｐｒｅｖ＿ｄｉｒが決定される。例えば、△ｘ＝０，△０＜ｙの場合にはｐｒｅｖ＿ｄｉｒ＝１  、△ｘ＝０，０＞△ｙの場合にはｐｒｅｖ＿ｄｉｒ＝３  となる。
【００９１】
ステップＳ５３では、始点座標ｋｐ［０］  から方向値ｐｒｅｖ＿ｄｉｒの方向に単位長さだけ進んだ点の座標を現在の点座標ｐ＿ｎｏｗ  とする。ステップＳ５４では、現在の点の座標ｐ＿ｎｏｗ  が、２番目の角点の座標ｋｐ［１］  と等しいか否かを判断し、等しい場合には角点を示す添字ｉを２に設定しておく。これは、以下の示す処理では、現在の点ｐ＿ｎｏｗ  と次の角点ｋｐ［ｉ］  とを利用して演算を行なうからである。
【００９２】
ステップＳ５６では、現在の点ｐ＿ｎｏｗ  が、終点ｋｐ［ｎ−１］  と一致しているか否かを判断し、一致していれば処理を終了する。なお、処理対象の元のデジタル曲線が閉曲線の場合には、終点と始点が同じなので、ステップＳ５６において現在の点ｐ＿ｎｏｗ  が始点ｋｐ［０］  と一致しているか否かを判断する。
【００９３】
ステップＳ５６において、現在の点が終点に一致していなければ、ステップＳ５７において、現在の点ｐ＿ｎｏｗ  と次の角点ｋｐ［ｉ］  とに基づいて、現在の点ｐ＿ｎｏｗ  から次の角点ｋｐ［ｉ］  の方向に単位長だけ進んだ次の点ｐ＿ｎｅｘｔを求める。図２３は、現在の点ｐ＿ｎｏｗ  から次の点ｐ＿ｎｅｘｔを求める様子を示す説明図である。角点ｋｐ［ｉ］  はデジタル曲線の輪郭点なので、角点ｋｐ［ｉ］  同士を結ぶ線分は水平方向または垂直方向を向いている。現在の点ｐ＿ｎｏｗ  と次の点ｐ＿ｎｅｘｔは、２つの隣接する角点ｋｐ［ｉ−１］，ｋｐ［ｉ］を結ぶ線分上に取られるので、これらは水平方向または垂直方向に並んでいる。
【００９４】
ステップＳ５８では、現在の点ｐ＿ｎｏｗ  から次の点ｐ＿ｎｅｘｔに向かう出力ベクトルの向き（すなわち方向値）ｎｅｘｔ＿ｄｉｒを算出する。この方向値ｎｅｘｔ＿ｄｉｒは、次の点の座標値ｐ＿ｎｅｘｔと現在の点の座標値ｐ＿ｎｏｗ  との差分から、前述したステップＳ５２の処理と同様にして決定される。ステップＳ５９では、現在の点ｐ＿ｎｏｗ  に向かう入力ベクトルの方向値ｐｒｅｖ＿ｄｉｒと、現在の点ｐ＿ｎｏｗ  から出る出力ベクトルの方向値ｎｅｘｔ＿ｄｉｒから、図５（Ｂ）に示す規則に従ってチェーン符号を求め、これを符号メモリ８４に格納する。
【００９５】
ステップＳ６０では、次の点ｐ＿ｎｅｘｔが次の角点ｋｐ［ｉ］  と一致しているか否かを調べる。一致していれば、ステップＳ６１で角点の順番を示す添字ｉを１つ増加する。ステップＳ６２では、現在の点ｐ＿ｎｏｗ  の座標値を次の点ｐ＿ｎｅｘｔの座標値で置換するとともに、現在の点に向かう入力ベクトルの方向値ｐｒｅｖ＿ｄｉｒを現在の点から出る出力ベクトルの方向値ｎｅｘｔ＿ｄｉｒで置き換える。これによって、処理対象の点が１つ進められる。この後、ステップＳ６２からステップＳ５６に戻り、ステップＳ５６〜Ｓ６２の処理を最後の角点ｋｐ［ｎ−１］  まで繰返す。この結果、角点ｋｐ［ｉ］  で構成されていたデジタル曲線が、チェーン符号に符号化される。
【００９６】
なお、この発明は上記の実施例や実施形態に限られるものではなく、その要旨を逸脱しない範囲において種々の態様において実施することが可能である。
【図面の簡単な説明】
【図１】この発明の実施例を適用する画像処理装置の構成を示すブロック図。
【図２】演算部４０によって実現される種々の機能を示す機能ブロック図。
【図３】実施例における処理の全体手順を示すフローチャート。
【図４】チェーン符号の各符号語ｒ，ｓ，ｌの意味を示す説明図。
【図５】デジタル曲線を構成する単位ベクトルの向きと、チェーン符号の符号語との関係を示す説明図。
【図６】チェーン符号化の例を示す説明図。
【図７】フラクタル次元変換によってに解像度を増大させた時の座標格子の格子点の増加と、チェーン符号に対応する入力ベクトルおよび出力ベクトルの変化とを示す説明図。
【図８】フラクタル次元変換によって曲線を拡大した時の座標格子の格子点を示す説明図。
【図９】セルＣＬ内のベクトル列の通り方の例を示す説明図。
【図１０】フラクタル次元変換の変換規則を記述したコードブックの登録内容を示す説明図。
【図１１】フラクタル次元変換の変換規則を記述したコードブックの登録内容を示す説明図。
【図１２】フラクタル次元変換の変換規則を記述したコードブックの登録内容を示す説明図。
【図１３】コードブックを用いて各符号語を解像度変換した例を示す説明図。
【図１４】図３のステップＳ３４におけるチェーン符号のフラクタル次元変換の詳細手順を示すフローチャート。
【図１５】境界条件の選択方法および複数の符号語列から１つを選択する方法を示す説明図。
【図１６】直進性のパラメータＰｓを１に設定し、複雑性のパラメータＰｆを０に設定した場合の処理結果を示す説明図。
【図１７】チェーン符号の復号化の例を示す説明図。
【図１８】符号語の解像度変換の他の実施例を示す説明図。
【図１９】図１８の方法に従ってデジタル曲線を拡大した場合の例を示す説明図。
【図２０】実施例で処理された各種の図形のフラクタル次元を測定した結果を示す説明図。
【図２１】フラクタル次元の予測結果の例を示す説明図。
【図２２】図３のステップＳ３１におけるデジタル曲線のチェーン符号化の詳細手順を示すフローチャート。
【図２３】現在の点ｐ＿ｎｏｗ  から次の点ｐ＿ｎｅｘｔを求める様子を示す説明図。
【図２４】フラクタル次元の測定方法を示す説明図。
【図２５】中点変位法の概要を示す説明図。
【符号の説明】
４０…演算部
４２…操作部
４４…画像出力部
５０…ＣＰＵ
５２…ＲＯＭ
５４…ＲＡＭ
５６…ハードディスク装置
６０…キーボード
６２…マウス
６４…ディジタイザ
７０…カラーＣＲＴ
７２…フルカラープリンタ
８０…デジタル曲線記憶部
８２…チェーン符号化部
８４…符号メモリ
８６…チェーン符号拡大部
８８…コードブック記憶部
９０…復号化部
９２…処理済デジタル曲線記憶部
【図１】
0003561368.tif 000002
【図２】
0003561368.tif 000003
【図３】
0003561368.tif 000004
【図４】
0003561368.tif 000005
【図５】
0003561368.tif 000006
【図６】
0003561368.tif 000007
【図７】
0003561368.tif 000008
【図８】
0003561368.tif 000009
【図９】
0003561368.tif 000010
【図１０】
0003561368.tif 000011
【図１１】
0003561368.tif 000012
【図１２】
0003561368.tif 000013
【図１３】
0003561368.tif 000014
【図１４】
0003561368.tif 000015
【図１５】
0003561368.tif 000016
【図１６】
0003561368.tif 000017
【図１７】
0003561368.tif 000018
【図１８】
0003561368.tif 000019
【図１９】
0003561368.tif 000020
【図２０】
0003561368.tif 000021
【図２１】
0003561368.tif 000022
【図２２】
0003561368.tif 000023
【図２３】
0003561368.tif 000024
【図２４】
0003561368.tif 000025
【図２５】
0003561368.tif 000026