(57)【特許請求の範囲】
【請求項１】
データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法において、
前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、当該線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、
該算出された各距離のうち最大のものを選択し、
該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶部に格納された頂点列に当該新たな頂点を追加する
ことを特徴とする線分近似方法。
【請求項２】
前記選択された最大距離が前記所定の閾値を越えなかった線分については、該線分の両端の２頂点間にそれ以降に生じる線分に対して予め設定される前記確率の値を小さくすることを特徴とする請求項１に記載の線分近似方法。
【請求項３】
前記選択された最大距離が前記所定の閾値を越えなかった線分の両端の２頂点間に、前記新たな頂点が発生した場合には、該頂点によって増えた新たな近似線分の両端の２頂点間にそれ以降生じる線分に対して予め設定される前記確率の値を小さくすることを特徴とする請求項１に記載の線分近似方法。
【請求項４】
前記選択された最大距離が前記所定の閾値を越えた線分については、該線分の両端の２頂点間にそれ以降生じる線分に対して予め設定される前記確率を所定の値に戻すことを特徴とする請求項２または３に記載の線分近似方法。
【請求項５】
前記確率は、当該線分の両端で挟まれる、前記部分点列の各点までの距離が大きいほど大きい値になるように設定されることを特徴とする請求項１に記載の線分近似方法。
【請求項６】
前記確率は、一様に発生する乱数と、当該線分の両端で挟まれる、前記部分点列の各点までの距離および揺らぎの大きさを決めるパラメタで決まる関数との大小関係に応じて設定されることを特徴とする請求項５に記載の線分近似方法。
【請求項７】
前記関数は、前記距離および揺らぎの大きさを決めるパラメタ各々に関して単調変化することを特徴とする請求項６に記載の線分近似方法。
【請求項８】
前記揺らぎの大きさを決めるパラメタは前記各線分毎に設定されることを特徴とする請求項６に記載の線分近似方法。
【請求項９】
前記選択された最大距離が前記所定の閾値を越えなかった線分については、該線分に対して設定される前記揺らぎの大きさを決めるパラメタの値を減少させることを特徴とする請求項８に記載の線分近似方法。
【請求項１０】
データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法において、
前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、
該算出された各距離のうち最大のものを選択し、
該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶部に格納された頂点列に当該新たな頂点を追加する
ことを特徴とする線分近似方法。
【請求項１１】
連続した階層に亘って、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えないときには、前記確率の値を小さくすることを特徴とする請求項１０に記載の線分近似方法。
【請求項１２】
連続した階層に亘って、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えず、かつ、前の階層で新たな頂点が発生したときには、前記確率の値を小さくすることを特徴とする請求項１０に記載の線分近似方法。
【請求項１３】
次の階層で、前記選択された、前記各線分毎の最大距離のうちいずれかが前記所定の閾値を越えたときには、前記確率を所定の値に戻すことを特徴とする請求項１１または１２に記載の線分近似方法。
【請求項１４】
前記所定の値は、当該線分近似を開始するときに設定した初期値であることを特徴とする請求項１３に記載の線分近似方法。
【請求項１５】
次の階層で、前記選択された、前記各線分毎の最大距離のうちいずれかが前記所定の閾値を越えたときには、前記確率の値を近似線分本数が増加するに従って小さくすることを特徴とする請求項１１または１２に記載の線分近似方法。
【請求項１６】
前記確率は、前記選択された、前記各線分毎の最大距離のうちの最大値が大きいほど大きい値に設定されることを特徴とする請求項１０に記載の線分近似方法。
【請求項１７】
前記確率は、一様に発生する乱数と、前記選択された、前記各線分毎の最大距離のうちの最大値および揺らぎの大きさを決めるパラメタで決まる関数との大小関係に基づいて決定されることを特徴とする請求項１０に記載の線分近似方法。
【請求項１８】
前記関数は、前記最大値および前記揺らぎの大きさを決めるパラメタ各々に関して単調変化し、
連続した階層に亘って、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えないときには、前記揺らぎの大きさを決めるパラメタの値を変化させることにより、前記確率の値を変化させることを特徴とする請求項１７に記載の線分近似方法。
【請求項１９】
データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法を実行するプログラムであって、
前記線分近似方法は、
前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、当該線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、
該算出された各距離のうち最大のものを選択し、
該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶部に格納された頂点列に当該新たな頂点を追加する
ことを特徴とするプログラム。
【請求項２０】
データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法を実行するプログラムであって、
前記線分近似方法は、
前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、
該算出された各距離のうち最大のものを選択し、
該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶部に格納された頂点列に当該新たな頂点を追加する
ことを特徴とするプログラム。
【請求項２１】
データ記憶手段を備え、該データ記憶手段に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似し、当該頂点列を前記データ記憶手段に格納する線分近似装置において、
前記データ記憶手段に格納された頂点列に対応する線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出する算出手段と、
該算出手段によって算出された各距離のうち最大のものを選択する選択手段と、
該選択手段によって選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶手段に格納された頂点列に追加する一方、前記選択手段によって選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶手段に格納された頂点列に当該新たな頂点を追加するように制御する制御手段と
を有することを特徴とする線分近似装置。
【請求項２２】
データ記憶手段を備え、該データ記憶手段に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似し、当該頂点列を前記データ記憶手段に格納する線分近似装置において、
前記データ記憶手段に格納された頂点列に対応する線分列の、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列Ａ内の部分点列の各点までの各距離を算出する算出手段と、
該算出手段によって算出された各距離のうち最大のものを選択する選択手段と、
該選択手段によって選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶手段に格納された頂点列に追加する一方、前記選択手段によって選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶手段に格納された頂点列に当該新たな頂点を追加するように制御する制御手段と
を有することを特徴とする線分近似装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一意的に１次元鎖と見なし得る、２次元整数格子内の連結した複数個の座標点列を線分列によって近似する図形の線分近似方法、該図形の線分近似方法を実現するためのプログラムおよび図形の線分近似装置に関する。
【０００２】
【従来の技術】
従来、計算機シミュレーション、画像評価、計測機において、計算機上に図形の形状を取り込み、その図形の判定、認識あるいは加工を行うため、線図を複数の連続した線分の列で近似することがなされる。また、単に線図を扱うのみではなく、図形の形状を用いるために、その輪郭線を抽出したり、細線化後の線図形に対して処理を施すこともある。
【０００３】
通常、図形を計算機上で扱う場合には、２次元に展開した点の集合として扱うが、元図形を構成する点の数が多いときには、膨大な点データを直接扱うのは計算資源の負荷が大きく、計算時間も多大なものとなる。このとき、曲線の線図や文字を細線化したり、輪郭線を抽出した後、複数の連続した線分の列、すなわち折れ線で近似し、この近似線分列を用いて以降の処理を行えば、一般に、近似後の線分列を構成する線分や頂点の数は、はじめの点データの数より大幅に少ないものとなるので、この線分近似後の線分や頂点について、図形の判定、認識あるいは加工を行うことが望ましい。特に、予め定められた線分数の線分列（折れ線）で曲線を近似し、この線分列に対して、図形判別や図形処理がなされる。
【０００４】
したがって、曲線等の線図を、予め定められた本数の複数の連続した線分の列、すなわち折れ線で近似することは、図形の特徴を抽出し、図形の概略を用いて処理することにより処理時間を短縮したり、メモリなどの計算資源の節約を図る意味で重要な技術課題である。
【０００５】
このような複数の連続した線分の列、すなわち折れ線で近似する従来の方法として、例えば特開平１−２９５３７６号公報には、線図形の線分近似処理方式が記載されている。
【０００６】
以下、この線図形の線分近似処理方式について説明する。
【０００７】
まず、２次元整数格子内の一意的に１次元鎖と見なし得る、連結したＮ個の座標点列Ａ＝[(ｘ[ｉ],ｙ[ｉ])|ｉ＝１,…,Ｎ]を初期値として考える。ここで、連結しているとは、図８のように座標点を微小面積要素と見なして、その領域が境界の点あるいは境界線で連結していることを意味する。このようなパターンは、鉛筆等で書かれた曲線をデジタル化するときに現れる。
【０００８】
また、簡単のため、点列は開いた曲線に対応しており、点列には曲線の連結性に沿って、順番がついているとし、所謂、細線化された曲線とし、図９（ａ）に示すようなひげ、同図（ｂ）に示すような解像度以上の折れ曲がり、同図（ｃ）に示すような二重線、同図（ｄ）に示すような交差点は、それぞれ存在しないと仮定する。
【０００９】
図８（ａ）の点列に対して、同図（ｂ）の線分を対応させることが、この線図形の線分近似処理方式の課題であり、以下のような方法を提案している。
【００１０】
線分列の頂点は、座標点列Ａの部分集合Ｂ＝[(Ｖx[ｉ],Ｖy[ｉ])|ｉ＝１,…,Ｒ｝として表される。数学的には、Ｂに余分な一点＊を加えＢ∪｛＊｝としたとき、集合ＡからＢ∪｛＊｝への射影（上への写像）を意味する。つまり、Ｂの点以外のＡ点は＊へ写像されるとし、Ｂの点となるＡの点は自分自身へ写像されるとすれば、写像が巧く定義される。
【００１１】
このような写像を具体的にどのように決定するかが、点列の線分化問題である。
【００１２】
予め閾値vtxth0を、対応する線分の長さに対する関数として決めておく。例えば、これを対応表（ルックアップテーブル）に書き込んでおき、線分の長さに応じてそれを変更させてもよい。ここでは、説明を簡単化するために、閾値vtxth0は一定値に固定しておく。
【００１３】
前記仮定から、座標点列Ａの対応する曲線の両端は、既に判明しているとしてよい。
【００１４】
図１１は、この従来の線分近似処理の手順を示すフローチャートである。このフローチャートに従って線分近似処理の手順を順次説明する前に、まず、その具体例である図１０に従って説明する。
【００１５】
まず、図１０（ａ）のように、両端を線分で結ぶ。これを階層１の線分と呼ぶ。この線分の両端で挟まれた領域における座標点（図示例では、すべて）に対して、該線分との距離ｄｄ[ｉ]（ｉ＝１，…，Ｎ）を求める。この距離ｄｄ[ｉ]は、通常用いられる、点から直線までの定義に従って、図１０（ｅ）のように、点からこの線分を延長してできる直線へ下ろした垂線の長さである。この直線を、以降「基準線」と呼ぶことがある。また、以降、簡単のために、「線分からの距離」とも称するが、図１０（ｆ）のように、垂線が線分より外れるときにも、直線への距離の意味をとるものとする。この距離ｄｄ[ｉ]のうち、最大のものが、閾値vtxth0より小さい場合には、この階層１の線分を求める線分列とする。
【００１６】
図１０（ａ）は、最大距離が閾値vtxth0より大きい場合を図示しており、点Ｐが最大距離の点である。この場合、点Ｐを新たな頂点列の一つとし、図１０（ｂ）のように、この頂点により２本の線分Ｌ１とＬ２を作る。これにより、１つ階層を上げ、得られた点列を階層２の頂点列とする。
【００１７】
次に、図１０（ｂ）の線分Ｌ１に対して、この両端を端点とする線分列の各点から線分Ｌ１までの距離を求め、その最大値ｄ2を与える点Ｐ２を新たな頂点として、図１０（ｃ）のように、新たな２線分を作る。
【００１８】
この動作を、得られる最大距離が閾値vtxth0を越えなくなるまで繰り返し、図１０（ｄ）の線分列を得る。
【００１９】
すなわち、現在の階層をＫ（＞１）とする。階層Ｋの線分列の内の１つの線分に着目する。該線分の両端で挟まれた領域での座標点列Ａの部分列の該線分からの距離をｄｄ[ｉ]（ｉ＝ｊ１，…，ｊ２）とし、ｄｄ[ｉ]（ｉ＝ｊ１，…，ｊ２）を求める。この求めた距離の最大のもの（最大距離ｄ）が、閾値vtxth0より小さい場合には、該線分を求める線分列の一部とする。このとき、対応する線分は、階層Ｋについて収束したとし、階層をＫからＫ＋１に増やした場合も、線分列の対応する部分は変化しないものとする。
【００２０】
一方、最大距離ｄが、閾値vtxth0より大きい場合には、最大値を持つ点を次の階層Ｋ＋１での頂点列の一つとする。この操作を、同じ階層内の、すべての収束していない線分に対して行い、階層Ｋ上ですべての線分について操作を行った後に、階層をＫからＫ＋１に上げる。
【００２１】
このような操作を繰り返すことにより、階層を十分深くすると、座標点は有限個であるので、最終的にすべての線分が収束し、つまり、すべての点列が、対応する線分から閾値vtxth0よりも小さい距離にあるように、線分列を構成することができる。
【００２２】
このようにして、図１０（ａ）の階層１の線分に対して、図１０（ｄ）のより階層の深い線分が得られる。
【００２３】
図１１のフローチャートは、上記手順をフローチャートの形式で表現したものである。図１１に従って、一般的な場合の線分化方法について説明する。
【００２４】
同図において、まず、ステップＳ１０１では、初期化を行う。つまり、階層Ｋを“１”にするとともに、曲線の両端を階層１の線分の両端とする。
【００２５】
次に、ステップＳ１０２では、着目するｉ番目の線分が、階層Ｋの線分列の最終線分を超えたか否かをチェックする。
【００２６】
ｉ番目の線分が階層Ｋの線分列の最終線分でなければ、ステップＳ１０３で、線分内の対応する座標点の線分からの距離の最大値を計算する。
【００２７】
次に、ステップＳ１０４で、線分の最大距離ｄが閾値vtxth0より大きければ、ステップＳ１０５へ移行し、ｉ番目の線分を、最大距離ｄを持つところで分割して、二つの線分に分割する。
【００２８】
一方、ステップＳ１０４で、線分の最大距離ｄが閾値vtxth0より小さければ、その線分は収束したとする。
【００２９】
そして、ステップＳ１０６では、同じ階層Ｋ内での線分列の次の線分に移る。
【００３０】
ここで、再びステップＳ１０２で、着目するｉ番目の線分が、階層Ｋの線分列の最終線分か否かをチェックする。
【００３１】
ステップＳ１０３〜Ｓ１０６の処理を繰り返し、階層Ｋの線分列の最終線分まで繰り返す。
【００３２】
ステップＳ１０７で、すべての線分において、その最大距離が閾値vtxth0より小さければ、ステップＳ１０８で、順番を入れ替えて、本線分化処理を終了する。
【００３３】
一方、ステップＳ１０７で、すべて線分が収束していなければ、ステップＳ１０９で、階層を一つ上げて、ステップＳ１０２に戻る。
【００３４】
以上の処理を繰り返し、最終的にはすべてが収束して、本線分化処理を終了する。
【００３５】
この他にも、上記特開平１−２９５３７６号公報の従来技術の欄で述べられている方法等、いくつかの方法が提案されている。
【００３６】
【発明が解決しようとする課題】
図形の特徴を抽出し、図形の概略を用いて処理を行うことにより処理時間を短縮したり、メモリなどの計算資源の節約を図る図形処理において、曲線等の線図を複数の連続した線分の列、すなわち折れ線で近似するために、上記従来の線分近似方法を用いるには、以下のような問題があった。
【００３７】
すなわち、これらの処理においては、処理の目的に応じて、できる得る限りデータ数、すなわち線分数を少なくし、処理を高速に行い、かつ使用する計算資源が少ない計算を行うことが望ましい。線分近似を線図の概略判定に用いる際には、図形の特徴が判断できる最小の線分数で近似することにより、その後の処理や判定を簡素に高速に行えることになる。そのため、線図の概略判定に必要とされる、予め定められた本数の線分列への線分近似が必要となる。ここで云う概略判定とは、線図の長さや曲率などの定量的な性質は無視して、線が特徴的な形状、例えば巻いているか否か、あるいは巻いている回数等を調べるものである。
【００３８】
このような処理に従来の方法を応用する場合、線分近似の終了を決める閾値vtxth0をどのように決定するかが重要な問題となる。
【００３９】
特に、判定の誤動作を防ぐために、線分近似の精度を高め、閾値vtxth0を小さくとる必要がある。この様子を図１２に示す。
【００４０】
図１２（ａ）は、判定すべき線図を構成する点列を表している。
【００４１】
同図（ａ）において、点Ｐ３およびＰ４は、それぞれ点列の始点および終点である。この始点Ｐ３および終点Ｐ４から上記従来の線分近似を行う場合、図１２（ｂ）のように、基準線を引き、点列の各点から基準線間での距離を計算して行くため、閾値vtxth0を大きく取ると、図１２（ｃ）のような線分と判定される。このような場合、大きな閾値vtxth0は、線図の微小部分の形状に対して近似精度を落とすのみではなく、近似後の線分列は、線図の概略形状も大きく変えてしまい、判定誤差を生じせしめてしまう。ここで云う誤動作とは、図形の微小形状あるいは微小部分から決まる定量的な特性は無視し、線図の概略を判定する観点からいう。
【００４２】
この誤動作の意味をより具体的に説明すれば、図１２（ｄ）のような図形入力があったときには、同じく図１２（ｃ）のような近似線分を与え、入力の図１２（ａ）と図１２（ｄ）の近似後の差異がなくなってしまう。図１２（ａ）と図１２（ｄ）は、図形の概略判断の意味からは大きく異なり、特に図１２（ａ）における点Ｐ３より左側の図形の特徴が全く失われてしまう。
【００４３】
以上の説明では、閾値vtxth0のみを判断する場合について説明を加えたが、これは、上記特開平１−２９５３７６号公報に開示されているような、閾値vtxth0のみでなく、線分の長さを判断に入れた線分列近似方法においても生じる問題点である。すなわち、図１２（ａ）と図１２（ｄ）では、近似法の当初に着目する線分に関し、線分の長さおよび基準直線よりの距離の最大値とも同じ値を与えるため、線分長により閾値vtxth0を変化させる方法でも、両者は同じ判定基準を与えてしまう。
【００４４】
このような問題に対処するために、線図の概略判定用の線分列近似では、閾値vtxth0を十分に細かく、例えば図１２に関しては１ピクセル以下の精度に設定する必要がある。このように、誤動作を防ぐには、場合によって解像度のピクセル程度まで閾値vtxth0を細かくしなければならない。
【００４５】
一方で、このような細かな閾値vtxth0を用いた線分列近似を用いて図１２のような線図を判定すれば、概略形状判定の観点からは無視してもかまわないような微小区間での線図の変動に従って細かな線分化（線分分割）を行うため、近似後の線分数は当初の点列の点数と大差がなくなってしまい、線図の概略判定の計算時間、計算資源の節約を目的になされた、本来の線分列近似の効果が極端に少なくなる。
【００４６】
このように、必要とされる閾値vtxth0は、局所的な近似精度のみでなく、元線図の大略的な形状によって大きく異なる。入力図形の形状が、例えばその始点および終点が図形全体の外接多角形上にある場合等のように、ある特定の傾向をもった図形に限られる場合には、このような誤動作は生じ難いが、図１２（ａ）のような図形に対しては、閾値vtxth0を小さく設定しなければならない。
【００４７】
このように、上記従来の線分近似方法では、閾値vtxth0の値により近似後の線分の大略的な形状までも大きく影響を受けていた。このため、線分近似法としては非常に扱いにくい近似方法となっていた。
【００４８】
すなわち、入力図形の傾向によって図形を分類し、それに応じて閾値vtxth0を決定すれば、このような誤動作は生じ難くなるが、このような図形を好適に判断する処理は複雑になり、その分の処理が必要となって、線図の概略の判定処理の計算時間、計算資源の面から好ましくない。また、入力図形の形状に予め制限を加えたり、図形判定処理内に線分列近似以外の処理を組み合わせることは図形判定処理の適用範囲を狭めたり、処理の複雑化を招き好ましくない。
【００４９】
一方、判定の誤動作を防ぐために、線分近似の局所的な近似精度の必要性以上に細かな閾値vtxth0を設定すれば、図形により、本来の線分列近似の目的であった線図の概略判定に対して、計算時間の短縮および計算資源の節約の効果が得られ難く、その後の処理に多量のメモリ領域と長い処理時間を必要とする線分列を作成していた。さらに、このような細かな閾値vtxth0を設定することが必要なため、図形により、線分列近似自体の処理も多量のメモリ領域と長い処理時間を必要としていた。
【００５０】
特に、閾値vtxth0を設定する、上記従来の線分近似方法では、指定された近似線分本数に線分近似するには、扱う図形の傾向に応じて経験的に定めた閾値vtxth0を用いるか、あるいは閾値vtxth0を変更しながら上記従来の線分近似処理を行い、得られた近似線分数が所望のものに近くなるまで線分近似を繰り返す必要があった。
【００５１】
前者は、取り扱う図形の適応範囲を狭めるものであり、後者は、実行時間を大きく増加させるものであった。
【００５２】
このような問題は、以下の原因に起因する。
【００５３】
点列上の各点が頂点となるか、頂点にならずに頂点の間に挟まれているかを、その「点の状態」と呼ぶことにする。また、点列の各点状態の配列を「点列の状態」と呼ぶことにする。元図形を構成する全点からなる点列の状態が分かれば、どの点が頂点をなすかが分かり、隣接する頂点を結ぶことで、近似線分列（折れ線）が表現できる。元図形の１つの線分近似に対して１つの点列の状態が対応し、この状態に対し評価関数を決めることでこの線分近似の評価値が決まり、評価値を目安に線分近似の良さを判定できる。評価値を最適（最大あるいは最小）にする方向に各点の状態を変えて行けば、最良の近似線分が得られる。このような評価関数を設定すれば、線分近似方法は、点列の状態に対する評価函数の最適化問題と見ることができる。近似の良さを表す評価値として、近似が良いほどその値が小さく、あるいは大きくとるようにすればよい。以降説明の簡単のため近似が良いほど評価値が小さいものを取った場合について話しを進める。
【００５４】
従来例に関して云えば、評価値は、点列の各点と近似線分との距離の最大値である。従来例では、近似の各段階で得られる線分列の各線分に対して、その線分の両端となる頂点の間で挟まれた点列の各点からこの線分までの距離の最大値と、その最大値をもたらす点を求め、この点を新たな頂点とする。このようにして、評価値である、点列の各点と近似線分との距離の最大値が、全線分列に対して、閾値vtxth0より小さくなるまで線分の分割を続け、近似線分列を得るようにしていた。
【００５５】
しかしながら、従来例では、線分近似を行う各段階で得られる線分列のある線分に対して、その線分の両端となる頂点の間で挟まれた点列の各点からこの線分までの距離の最大値をもたらす点を新たな頂点とし、その値が閾値vtxth0以下になるまで順次頂点を作って行くときに、新たな頂点を用いて新たな２線分を作ると、この新たな２線分に関しては、線分の両端で挟まれる点列の各点と線分との距離の最大値が必ずしもその前の線分に関する点と線分の距離の最大値より小さくなっておらず、通常の最適化のように順次評価関数の値を減らす方向に最適化を行うものとは異なっている。これは、例えば図１０の（ａ）と（ｂ）を比較すれば明らかであるが、（ａ）から（ｂ）へ線分近似処理を進めて行くなかで、（ｂ）での最大距離ｄ2 は（ａ）での最大距離ｄ1より大きくなって行く。このように、従来の線分近似では、過程の中での評価関数の値の変化には無頓着に、過程中に現れる線分から点列までの最大値を生ずる点の状態を変化させて行き、最終的に評価関数の値が規定閾値vtxth0以下になるようにしている。最適化手法として見た場合、このような方法は、もっとも原始的な方法であり、一般に、評価関数の値を減少させるように状態を変化させて行く最適化方法に比べ、効率が悪く、誤動作が生じ易い。すなわち、最適化の最中で評価関数を順次小さくするように状態を変化させていく訳ではないので、最適化の観点からは、状態変化に無駄が多く、効率が悪い。また、最適化の最中の状態変化に対して、評価関数の変化に規則性がないため、偶発的に動作が停止してしまう誤動作を起こしやすく、停止した状態がどの程度真の最適状態に近づいているのかが分からない。
【００５６】
このことを従来例に即して言えば、以下のようになる。
【００５７】
すなわち、図１２（ａ）と図１２（ｄ）の各図形に対して、従来例に基づく線分近似を施した場合、最終的な評価関数の値が同じく閾値vtxth0以下のものとなった状態では、ともに図１２（ｃ）の線分列が得られる。しかしながら、線分近似の観点からは、図１２（ｄ）の方がより近似後の線分列に近い配置であるのに対し、図１２（ａ）の元図は、近似後の図１２（ｃ）と比較すれば明らかなように、元図の特徴を失った線分近似として好ましくない配置を与えてしまう。図１２（ａ）を出発点とした従来例の線分近似では、近似動作の途中で最適化の誤動作を生じている。すなわち、線分近似の近似動作の途中で、評価関数である、点列から線分までの最大距離が全て偶然に閾値vtxth0を下回った場合には、動作が中断して、目的とする状態まで最適化が進まない。
【００５８】
今仮に、以下のような線分近似を考えてみる。図２（ａ）は、図１２（ａ）と同様に、元図形、つまり評価関数最小化の出発点の図形である。図２（ｂ）は、図１２（ｂ）と同様に、線分近似のある過程である。ここで、従来例にある方法とは異なり、仮に図２（ｃ）のように、点２ａを頂点に取って線分を引き、線分よりの距離を算出してみる。線分からの最大距離、すなわち評価関数の値は、図２（ｂ）の場合より図２（ｃ）の場合の方が高く、図２（ｃ）は、評価関数の極小より離れた配置であるが、この配置から再度従来例に従った近似を行っていくと、図２（ｄ）に達する。このとき、評価関数は、図２（ｂ）の場合より小さくなり、また、線分近似の意味でも、図２（ｃ）より好ましい配置となっている。
【００５９】
ここで、改めて最適化された図２（ｄ）を見てみると、従来例の点列の各点と近似線分の距離の最大値を評価関数として見た場合にも、この配置は評価関数の最小を与えるものとなっているが、この最小値へ最適化が進む途中で、図１２（ｂ）のような評価関数が閾値vtxth0を偶然下回る状態で最適化がトラップされてしまっていることが分かる。
【００６０】
さらには、このとき、従来例の線分近似では、最適化の最中に評価関数の値を順次小さくしていく一般的な最適化手法をとっていないために、どの程度最適状態に近づいているのかが判定できない。
【００６１】
評価関数を順次小さくするように状態を変化させて行く方法では、動作打ち切り収束閾値を小さくすることで、最適状態の評価関数が小さくなり、より好適な近似となり得るのに対して、従来例では、近似動作が評価関数の値を単調に減少させて行かないために、偶然に評価関数が閾値vtxth0を下回る可能性が多く、動作打ち切りの閾値vtxth0を変えることで全く異なる結果を生じせしめることがある。このため、閾値vtxth0の決め方が、結果の精度のみでなく、動作の安定性に本質的にかかわるものとなり、また、閾値vtxth0の決め方に系統的な指針を与えられない、すなわち至極経験的なものとなる。
【００６２】
これらが原因となり、従来例の前記問題点が生じていた。
【００６３】
本発明は、以上のような問題点の分析に鑑み、近似動作の中で図２（ｃ）に示したような「揺らぎ」を発生させ、偶発的に評価値が動作の閾値vtxth0を下回った場合にも動作を停止することなく安定に動作する図形の線分近似方法、該図形の線分近似方法を実現するためのプログラムおよび図形の線分近似装置を提供することを目的とする。
【００６４】
このように、「揺らぎ」を発生し、それを利用する最適化探索方法として、シミュレーテッドアニーリング法が知られている。
【００６５】
以下、シミュレーテッドアニーリング法について説明する。
【００６６】
シミュレーテッドアニーリング法では、配置ｘ1,ｘ2,…,ｘnに対して、評価関数Ｖ(ｘ1,ｘ2,…,ｘn)が与えられている場合、配置の１つ要素ｘiに変動を加えてｘ'iとしたとき、その評価関数の変動ΔＶ ＝Ｖ(ｘ1,ｘ2,…,ｘ'i,…,ｘn)−Ｖ(ｘ1,ｘ2,…,ｘi,…,ｘn)を計算する。
【００６７】
この変動ΔＶが負のときには、配置の１つ要素ｘiに変動を加えたｘ'iが、より好ましい配置であるとする。
【００６８】
従来例に基づく線分近似は、最適化の観点からは、変動ΔＶが負のときにはこのようにして配置を変形し、変動ΔＶが正のときには何もしないようにして探索を続けて行くことに対応する。
【００６９】
シミュレーテッドアニーリング法では、変動ΔＶが正のときには、以下の動作を行う。
【００７０】
まず、正のΔＶに対して、次の判定量
【００７１】
【数１】
0004164286.tif 000002
【００７２】
を算出する。ここで、“Ｔ”は、揺らぎを与える定数で、「温度」と呼ばれることがあるが、この用語は統計的な意味であり、物理的な温度とは無関係である。また、“Ｄ”は、０と１の間の値をとる。
【００７３】
これに対して、０と１の間の値をとる乱数Ｒを発生し、Ｄ ＞ Ｒならば、配置の１つ要素ｘiに変動を加えたｘ'iがより好ましい配置であるとする。
【００７４】
一方、Ｄ ＜ Ｒ ならば、もとの配置が好ましい配置であるとして、配置の変動を行わない。
【００７５】
このようにして、全ての配置要素ｘi,(ｉ＝１,２,…,ｎ)について好ましい変動を判定し、それに応じて配置の変更を行う。但し、全ての配置要素ｘi,(ｉ＝１,２,…,ｎ)の判定を終了するまで、実際の配置の変動は行わない。すなわち、上記のある線分についての判定の計算の最中では、配置要素ｘi以外の要素は、その前の配置の値をとっているとする。
【００７６】
このようにして、配置を変化させて行くと、配置の各要素は揺らぎながら値を変えて行くが、温度Ｔを有限値から０に近づけて行くに従って、揺らぎは小さくなり、Ｔ ＝ ０である配置に収束する。
【００７７】
このように、配置が揺らぎながら変動し、アニーリングして行くことで、局所的な極小点へとらえられることなく、最小の評価関数値へ最適化探索が進められる。
【００７８】
しかしながら、シミュレーテッドアニーリング法は、通常評価関数を順次減少させて行く一般の最適化方法に利用されるため、上述のように、対応する状態の変化に対して、評価関数の変動分を計算する必要があり、これを線分近似に直接適用する場合は、状態変化前後の評価関数の計算が必要となり、このため、処理が煩雑になり時間がかかる。さらに、一般に、シミュレーテッドアニーリング法はアニーリング動作を伴うため、何度も最適化動作を反復するので、動作が煩雑になり実行時間の増加を招く。
【００７９】
本発明では、「揺らぎ」の発生を、判定が必要な部分にのみ限定して使用し、アニーリング動作を線分近似の過程に組み込み、処理時間の大幅な増加を招くことなく、最適化動作において「揺らぎ」を発生させ、局所的な極小値にトラップされることなく、真の最適状態へ線分列近似するようにしている。
【００８０】
本発明では、図２（ｃ）のように、近似の各段階で得られる線分列の各線分に対して、その線分の両端となる頂点の間で挟まれた点列の各点からこの線分までの距離を求め、これが閾値vtxth0を越えることがなかった場合に、「揺らぎ」を生じせしめる頂点を、ある確率で生成する。
【００８１】
本発明では、線分までの距離が閾値vtxth0を越えることがなかった場合には、以下の判定によって新たな頂点となるかどうかを確率的に判定する。「揺らぎ」の大きさを表すパラメタＴと各点から近似線分までの距離ｄの関数として、Ｄ(ｄ,Ｔ)を設ける。０から１までの乱数Ｒを発生させ、Ｒと関数Ｄ(ｄ,Ｔ)との大小関係から、確率的に頂点かどうかの判定を行う。以下では、説明の簡便のため、Ｒ ＞ Ｄ(ｄ,Ｔ)のときに頂点であると判定する場合について説明する。
【００８２】
Ｄ(ｄ,Ｔ)は、発生する乱数に対応して、０から１までの値をとる関数であり、「揺らぎ」の大きさを表すパラメタＴの値がある値、例えば０を取るときに、０から閾値vtxth0までのｄの値に対して、０を与えるものであり、ｄを固定したときに、Ｔの減少に関しては、非増加の関数となっている。このＴは、その値が大きいときに「揺らぎ」が大きくなるようにとり、その最小値は一般には何でもかまわず、後述のアニーリング動作でＴを減少した際に変動させるＴの最終値であればよいが、ここでは説明の簡便のために、０とする。このＴは、その値が大きいときに「揺らぎ」を小さくするようなパラメタとしてとり、アニーリング動作でＴを増加させて行き、その最大値を決めることもできる。基本的には、本発明ではアニーリング時に「揺らぎ」を単調（非増加）に小さくして行く動作であり、固定したｄの値に対して、関数Ｄ(ｄ,Ｔ)が単調（非増加）に小さくなり、最終的には、発生する乱数Ｒの最小値以下となるように、パラメタをＴを変化させる。また、Ｄ(ｄ,Ｔ)の取り得る値は、発生する乱数Ｒに対応した値であればよい。
【００８３】
また、Ｔを固定したときに、関数Ｄ(ｄ,Ｔ)は、ｄの関数として単調増加（非減少）関数であり、距離ｄが大きくなるに従って、発生する乱数Ｒに対して大きくなる確率が高いものになるとする。
【００８４】
特に、本発明に好適には、判定する元図形の分解限界であるピクセルサイズｄ0として非０のＴのときに ｄ ＞ ｄ0 でＤ(ｄ,Ｔ)が有限の値をもつものである。
【００８５】
例えば、図３に示すような関数を取ることができる。図３中、横軸は距離ｄを表し、縦軸はＤを表し、Ｔ ＝ ０，Ｔ1，Ｔ2，Ｔ3（但しＴ1 ＜ Ｔ2 ＜ Ｔ3）の値に対するＤとｄの関係を示す。Ｔ＝０では、ｄが０より大きく、vtxth0より小さい範囲で、Ｄは“０”であり、ＴがＴ1，Ｔ2，Ｔ3と大きくなるつれてＤの値が非減少に変化する。この関数Ｄの値が、ランダムに発生したＲの値より小さいときに、新たな頂点を作成する。
【００８６】
このようにして新たな頂点が作られた次の階層からでは、上記従来例のような線分近似方法を継続することができる。そこで、線分近似の過程において連続する階層で「揺らぎ」を生じせしめるときには、温度Ｔにアニーリングを行うことで動作を収束させることができる。すなわち、ある階層の線分列の各線分に対して、その線分の両端となる頂点の間で挟まれた点列の各点からこの線分までの最大距離を求め、これが閾値vtxth0を越えないときは、「揺らぎ」を生じせしめて確率的に次の階層の頂点を生成する。このように、「揺らぎ」を生じせしめた線分に関しては、そこから派生して生成される線分列に関して、次の階層でも線分列の各線分に対して、その線分の両端となる頂点の間で挟まれた点列の各点からの距離が閾値vtxth0を越えなかった場合には、発生する「揺らぎ」の大きさを小さくして前の階層より小さい確率で頂点を生成する。例えば、ある階層で１つの線分に対して、その線分の両端となる頂点の間で挟まれた点列の各点からこの線分までの距離を求め、これが閾値vtxth0を越えなかったとする。このとき、「揺らぎ」を生じせしめて、確率的に次の階層の頂点を生成し、新たな２線分が得られたとする。この線分は元の線分より派生されたもので、これを子線分と呼ぶと、次の階層で、この２つの子線分各々について線分の両端となる頂点の間で挟まれた点列の各点からこの線分までの距離を求め、これが閾値vtxth0を越えなかった場合、「揺らぎ」の大きさを決める温度Ｔを小さくして、前の階層より小さい確率で頂点を生成する。このとき、子線分からさらに新たな線分が得られたとすると、これを孫線分と呼べば、さらに次の階層でこの孫線分各々について線分の両端となる頂点の間で挟まれた点列の各点からこの線分までの距離を求め、これが閾値vtxth0を越えなかった場合には、温度Ｔの大きさを子線分のときよりさらに小さくして子線分のときより小さい確率で頂点を生成する。近似線分までの距離が閾値vtxth0を越えない限り、これを順次繰り返す。
【００８７】
一方、近似線分までの距離が閾値vtxth0を越えた場合には、「揺らぎ」の大きさは当初の大きさに戻す。
【００８８】
このように、階層を進めて行く中で、ある線分から派生した線分列に対して各階層で点列の各点からの距離が閾値vtxth0を越えない場合が続く限り、温度Ｔを小さくするアニール動作を行い、最終的に「揺らぎ」の大きさを０に収束させる。これにより、最終的には「揺らぎ」を生じない状態で、各点列から近似線分までの距離が閾値vtxth0より小さくなった場合には、目標近似精度に達したとして処理を終了する。これにより、各点列から近似線分までの距離が閾値vtxth0より小さくなった後、数回のアニール動作で処理が終了する。
【００８９】
このようにして、新たな頂点が作られた次の階層からでは、上記従来例のような線分近似方法を継続することができる。そこで、線分近似の過程において連続する階層で「揺らぎ」を生じせしめるときには温度Ｔにアニーリングを行うことで動作を収束させることができる。すなわち、ある階層で線分列の各線分に対して、その線分の両端となる頂点の間で挟まれた点列の各点からこの線分までの距離を求め、すべての線分に対して各線分の最大距離がいずれも閾値vtxth0を越えないときは、この最大距離の線分についての最大値を与えるものに対して「揺らぎ」を生じせしめて、次の階層の頂点を確率的に生成し、次の階層でも線分列の各線分に対して、その線分の両端となる頂点の間で挟まれた点列の各点からの最大距離がいずれも閾値vtxth0を越えなかった場合には、発生する「揺らぎ」の大きさを小さくして、前の階層より小さい確率で頂点を生成する。一方、このとき近似線分までの距離が閾値vtxth0を越えた場合には、「揺らぎ」の大きさを当初の大きさに戻す。このように、階層を進めて行くなかで、点列の各点からの距離が閾値vtxth0を越えない場合が続く限り、「揺らぎ」を小さくするアニール動作を行い、最終的に「揺らぎ」の大きさを“０”に収束させる。これにより、最終的には「揺らぎ」を生じない状態で、各点列から近似線分までの距離が閾値vtxth0より小さくなった場合には、目標近似精度に達したとして、処理を終了する。これにより、各点列から近似線分までの距離が閾値vtxth0より小さくなった後、数回のアニール動作で処理が終了する。
【００９０】
本発明の線分近似では、一般のシミュレーテッドアニーリング法のように通常評価関数を順次減少させて行く最適化方法になっていないため、一度「揺らぎ」を生じせしめた場合、評価関数は大きく変化してしまい、多くはトラップの原因を大きくはずれる。その場合には、それ以降の線分近似の過程で、線分列の線分に対しての点列の距離は閾値vtxth0を越えて、従来例のような線分近似を行うことができるため、「揺らぎ」を発生することなく旧来と同様の動作で線分近似を行うことができる。一方、トラップの原因を大きくはずれないときには、次の階層においても線分に対しての点列の距離は閾値vtxth0以下となるが、このときにだけ発生する「揺らぎ」の大きさを小さくするアニール動作を行い、「揺らぎ」に対して動作を収束させて行く。このように、本発明は、必要な部分にのみアニール動作を適用するため、一般のシミュレーテッドアニーリングに比べ、処理量が少なく高速な処理が行える。
【００９１】
特に、本発明では、近似のある階層で現れる線分列の各線分について同一の「揺らぎ」の大きさを与えるのではなく、各線分毎にその「経歴」に応じた「揺らぎ」の大きさを与えるものとなっている。すなわち、ある階層で点列までの距離が閾値vtxth0を越えなかった、ある線分より派生した線分列は、その線分が何階層連続して点列までの距離が閾値vtxth0を越えなかったかにより異なる「揺らぎ」の大きさをあたえて動作する。これにより、細かな屈曲部などが点在するような複雑な元図形に対しても、その部分部分に応じて個別のアニーリング動作を行うため、細かなアニーリングを必要とする部分に対してのみ、それに応じたアニーリング動作を行い、他の部分の線分近似動作に余分な処理をもたらさない。これにより、図１２に示したような誤差に対して、安定性を持ったまま処理の簡略化を図ることができる。
【００９２】
さらに、本発明では、線分近似で新たな頂点を作成し、線分を分割して行く動作中に、アニーリング動作を組み込むようにしているため、一般のシミュレーテッドアニーリング法のように、アニーリング動作中に線分を分割していく動作を重複して行う頻度が少なく、より処理量が少なく、高速な処理が行える。
【００９３】
特に、本発明では、すべての線分に対して、各線分の最大距離がいずれも閾値vtxth0を越えないときに、最大距離の線分中の最大値を与える線分に対してのみ「揺らぎ」を与えた判定を加えるために、線分を分割して行く動作を重複して行う頻度がより少なく、高速な処理が行える。
【００９４】
さらに加えて、本発明の線分近似では、一般のシミュレーテッドアニーリング法のように通常評価関数を順次減少させて行く最適化方法になっていないため、一度「揺らぎ」を生じせしめた場合、評価関数は大きく変化してしまい、多くはトラップの原因を大きくはずれるため、アニールにおける「揺らぎ」の大きさの減少ステップを大きくとることができる。図２に示した例では、１回の「揺らぎ」動作後は、従来の「揺らぎ」を伴わない線分近似を用いても十分な近似線分が得られ、連続する２階層目では、「揺らぎ」を“０”と取るようなアニールをとることで、十分動作を行うことができる。
【００９５】
また、本発明では、状態変化前後の評価関数値の比較を行う必要がないため、一般のシミュレーテッドアニーリング法に比べ、計算量が少なくてすむため、従来例に比べ極端に処理量を増加させる必要もなく、図１２に示したような、近似動作のトラップを受けることなく、好適な線分近似が行える。
【００９６】
【課題を解決するための手段】
上記目的を達成するため、請求項１に記載の線分近似方法は、データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法において、前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、当該線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、該算出された各距離のうち最大のものを選択し、該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶部に格納された頂点列に当該新たな頂点を追加することを特徴とする。
【００９７】
請求項２に記載の線分近似方法は、請求項１の線分近似方法において、前記選択された最大距離が前記所定の閾値を越えなかった線分については、該線分の両端の２頂点間にそれ以降に生じる線分に対して予め設定される前記確率の値を小さくすることを特徴とする。
【００９８】
請求項３に記載の線分近似方法は、請求項１の線分近似方法において、前記選択された最大距離が前記所定の閾値を越えなかった線分の両端の２頂点間に、前記新たな頂点が発生した場合には、該頂点によって増えた新たな近似線分の両端の２頂点間にそれ以降生じる線分に対して予め設定される前記確率の値を小さくすることを特徴とする。
【００９９】
請求項４に記載の線分近似方法は、請求項２または３の線分近似方法において、前記選択された最大距離が前記所定の閾値を越えた線分については、該線分の両端の２頂点間にそれ以降生じる線分に対して予め設定される前記確率を所定の値に戻すことを特徴とする。
【０１００】
請求項５に記載の線分近似方法は、請求項１の線分近似方法において、前記確率は、当該線分の両端で挟まれる、前記部分点列の各点までの距離が大きいほど大きい値になるように設定されることを特徴とする。
【０１０１】
請求項６に記載の線分近似方法は、請求項５の線分近似方法において、前記確率は、一様に発生する乱数と、当該線分の両端で挟まれる、前記部分点列の各点までの距離および揺らぎの大きさを決めるパラメタで決まる関数との大小関係に応じて設定されることを特徴とする。
【０１０２】
請求項７に記載の線分近似方法は、請求項６の線分近似方法において、前記関数は、前記距離および揺らぎの大きさを決めるパラメタ各々に関して単調変化することを特徴とする。
【０１０３】
請求項８に記載の線分近似方法は、請求項６の線分近似方法において、前記揺らぎの大きさを決めるパラメタは前記各線分毎に設定されることを特徴とする。
【０１０４】
請求項９に記載の線分近似方法は、請求項８の線分近似方法において、前記選択された最大距離が前記所定の閾値を越えなかった線分については、該線分に対して設定される前記揺らぎの大きさを決めるパラメタの値を減少させることを特徴とする。
【０１０５】
上記目的を達成するため、請求項１０に記載の線分近似方法は、データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法において、前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、該算出された各距離のうち最大のものを選択し、該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶部に格納された頂点列に当該新たな頂点を追加することを特徴とする。
【０１０６】
請求項１１に記載の線分近似方法は、請求項１０の線分近似方法において、連続した階層に亘って、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えないときには、前記確率の値を小さくすることを特徴とする。
【０１０７】
請求項１２に記載の線分近似方法は、請求項１０の線分近似方法において、連続した階層に亘って、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えず、かつ、前の階層で新たな頂点が発生したときには、前記確率の値を小さくすることを特徴とする。
【０１０８】
請求項１３に記載の線分近似方法は、請求項１１または１２の線分近似方法において、次の階層で、前記選択された、前記各線分毎の最大距離のうちいずれかが前記所定の閾値を越えたときには、前記確率を所定の値に戻すことを特徴とする。
【０１０９】
請求項１４に記載の線分近似方法は、請求項１３の線分近似方法において、前記所定の値は、当該線分近似を開始するときに設定した初期値であることを特徴とする。
【０１１０】
請求項１５に記載の線分近似方法は、請求項１１または１２の線分近似方法において、次の階層で、前記選択された、前記各線分毎の最大距離のうちいずれかが前記所定の閾値を越えたときには、前記確率の値を近似線分本数が増加するに従って小さくすることを特徴とする。
【０１１１】
請求項１６に記載の線分近似方法は、請求項１０の線分近似方法において、前記確率は、前記選択された、前記各線分毎の最大距離のうちの最大距離の各線分についての最大値が大きいほど大きい値に設定されることを特徴とする。
【０１１２】
請求項１７に記載の線分近似方法は、請求項１０の線分近似方法において、前記確率は、一様に発生する乱数と、前記選択された、前記各線分毎の最大距離のうちの最大値および揺らぎの大きさを決めるパラメタで決まる関数との大小関係に基づいて決定されることを特徴とする。
【０１１３】
請求項１８に記載の線分近似方法は、請求項１７の線分近似方法において、前記関数は、前記最大値および前記揺らぎの大きさを決めるパラメタ各々に関して単調変化し、連続した階層に亘って、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えないときには、前記揺らぎの大きさを決めるパラメタの値を変化させることにより、前記確率の値を変化させることを特徴とする。
【０１１４】
上記目的を達成するため、請求項１９に記載のプログラムは、データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法を実行するプログラムであって、前記線分近似方法は、前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、当該線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、該算出された各距離のうち最大のものを選択し、該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶部に格納された頂点列に当該新たな頂点を追加することを特徴とする。
【０１１５】
上記目的を達成するため、請求項２０に記載のプログラムは、データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法を実行するプログラムであって、前記線分近似方法は、前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、該算出された各距離のうち最大のものを選択し、該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶部に格納された頂点列に当該新たな頂点を追加することを特徴とする。
【０１１６】
上記目的を達成するため、請求項２１に記載の線分近似装置は、データ記憶手段を備え、該データ記憶手段に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似し、当該頂点列を前記データ記憶手段に格納する線分近似装置において、前記データ記憶手段に格納された頂点列に対応する線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出する算出手段と、該算出手段によって算出された各距離のうち最大のものを選択する選択手段と、該選択手段によって選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶手段に格納された頂点列に追加する一方、前記選択手段によって選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶手段に格納された頂点列に当該新たな頂点を追加するように制御する制御手段とを有することを特徴とする。
【０１１７】
上記目的を達成するため、請求項２２に記載の線分近似装置は、データ記憶手段を備え、該データ記憶手段に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似し、当該頂点列を前記データ記憶手段に格納する線分近似装置において、前記データ記憶手段に格納された頂点列に対応する線分列の、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列Ａ内の部分点列の各点までの各距離を算出する算出手段と、該算出手段によって算出された各距離のうち最大のものを選択する選択手段と、該選択手段によって選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶手段に格納された頂点列に追加する一方、前記選択手段によって選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶手段に格納された頂点列に当該新たな頂点を追加するように制御する制御手段とを有することを特徴とする。
【０１１８】
【発明の実施の形態】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。
【０１１９】
（第１の実施の形態）
図１は、本発明の第１の実施の形態に係る図形の線分近似方法を実現するためのパーソナルコンピュータ（ＰＣ）０の概略構成を示すブロック図である。
【０１２０】
同図に示すように、ＰＣ０は、図形の線分近似処理を行う演算処理装置１と、データ入力または処理制御入力を行うための入力デバイス２と、結果を出力するための出力デバイス３と、出力結果を表示するための表示器４と、データを記憶するための外部記憶装置５とによって構成されている。
【０１２１】
図１から分かるように、ＰＣ０は、汎用型計算機によって構成されているが、これに限らず、専用の装置上に本実施の形態の図形の線分近似方法を実現するようにしてもよい。
【０１２２】
入力デバイス２は、データや処理の制御を行うための情報を演算処理装置１へ入力するためのもので、キーイン入力を行うためのタイプライタ型のキーボード装置、またはカード入力装置、あるいは光学式入力装置（ＯＣＲ）、マウス等のポインタ入力装置、イメージスキャナ、ビデオ入力装置等の画像入力装置によって構成される。あるいは端末装置、ネットワークを通したリモート端末装置を流用することも可能である。
【０１２３】
処理用のデータ、および処理の実行の開始、終了、停止、中断、出力等の処理制御入力が、入力デバイス２から演算処理装置１に入力される。データ入力に関しては、事前に入力したデータを、後述の外部記憶装置５に格納しておいてもよく、入力デバイス２以外の入力デバイスによって入力し、図示しないネットワーク等を通して直接外部記憶装置５に格納するようにしてもよい。
【０１２４】
さらに、外部記憶装置５を、後述の可搬性記憶装置で構成することにより、入力デバイス２以外の入力デバイスによって入力したデータを使用することも可能である。
【０１２５】
演算処理装置１は、さらに、入力部１ｄ、中間データ記憶部１ｃ、演算手順記憶部１ｂ、演算部１ａ、出力部１ｅおよびバス部１ｆによって構成されている。入力デバイス２から送信されたデータは、入力部１ｄおよびバス部１ｆを介して、中間データ記憶部３０ｃあるいは外部記憶装置５に格納される。
【０１２６】
入力部１ｄは、入力デバイス２からの入力を、その後の演算処理やデータ格納に好適な形式に加工する機能を備えている。また、データ入力のために入力デバイス２を制御する機能を備えるようにしてもよい。例えば、入力デバイス２として、タイプライタ型のキーボード装置を採用した場合には、入力デバイス２からのキーイン信号を演算処理装置１用の内部表現形式の信号に変換し、適当な単位に区切ってバス部１ｆへ転送するようにする。また、入力デバイス２として、光学式入力装置（ＯＣＲ）を採用した場合には、データの読み取り開始／終了等の、光学式入力装置（ＯＣＲ）に対する処理制御信号を発生する機能を備えるようにしてもよい。さらに、入力デバイス２として、マウスやデジタイザ等のポインタ入力装置を採用した場合には、ポインタ入力装置がポイントした位置を数値（座標値）に変換し、これを入力データとして生成する機能を備えるようにしてもよい。またさらに、ネットワーク通信機能を備えるようにし、ＰＣ０以外の処理装置から転送されて来たデータを、中間データ記憶部１ｃあるいは外部記憶装置５に格納するようにしてもよい。
【０１２７】
中間データ記憶部１ｃは、例えば半導体電荷蓄積型のランダムアクセスできる記録再生可能なＲＡＭ装置等によって構成され、処理の初期データや処理中に生成される中間データを一時的に格納する。
【０１２８】
初期データは、処理を開始するに際し必要なデータであり、処理直後に入力デバイス２から入力されたもの、あるいは、処理開始以前または処理開始直後に外部記憶装置５に格納されたものを、バス部１ｆを介して読み取り、中間データ記憶部１ｃに一時的に格納する。これらは、後述の演算手順に従い、必要とされたときに、バス部１ｆを介して演算部１ａに送信され、演算処理に使用される。
【０１２９】
中間データとは、演算部１ａにおいて後述の処理手続きに従って処理を行う過程で新たに算出または定義された変数の数値、または、演算処理を行うに際し必要な一時記憶領域の内容である。
【０１３０】
中間データ記憶部１ｃは、演算手順に従って発生する、これらのデータを、演算部１ａからバス部１ｆを介して受け取り、必要とする時点まで一時的に格納しておく。中間データ記憶部１ｃに一時的に格納された中間データは、演算手順に従って必要とされる際に、バス部１ｆを介して演算部１ａへ送信され、演算部１ａで演算に利用される。その際、以降の処理に不必要なデータは、演算部１ａへ転送後、破棄して、その部分の記憶領域を、後のデータの格納に再利用するようにしてもよい。あるいは、処理の履歴データとして処理終了まで格納し、最終結果として出力するようにしてもよい。
【０１３１】
中間データ記憶部１ｃには、通常、転送（書き込み、再生速度）やアクセス速度が速い揮発性のＤＲＡＭ装置が用いられ、処理の開始とともに動作を開始し、処理の終了とともに動作を終了する。処理の開始時に必要とされる初期データは、処理の開始直後に、バス部１ｆを介して外部記憶装置５から読み取り、処理の終了後も保持すべき最終データは、バス部１ｆを介して外部記憶装置５へ格納するようにしてもよい。
【０１３２】
また、中間データ記憶部１ｃの一部、特に演算処理を行うに際し必要な一時記憶領域は、演算部１ａ内にキャッシュメモリとして設けるようにしてもよい。さらに、中間データ記憶部１ｃの一部（あるいは全て）は、外部記憶装置５内に設けるようにしてもよい。
【０１３３】
また、後述の処理手続きに従って処理を行う過程で発生する中間データの一部は、外部記憶装置５へ格納するようにしてもよい。
【０１３４】
さらに、中間データ記憶部１ｃから、必要に応じてバス部１ｆを介して外部記憶装置５へ転送し、外部記憶装置５に格納した後、必要時に中間データ記憶部１ｃへ出力して利用するようにしてもよい。
【０１３５】
処理実行時には、後述の演算手順は、演算手順記憶部１ｂに格納されている。演算部１ａは、演算手順記憶部１ｂに格納された演算手順を読み出し、それに従って後述の演算処理を行う。特に、本実施の形態のように、図形の線分近似方法を汎用のＰＣ０上に構築する場合には、演算手順は、当該技術分野で周知な高級プログラム言語からなるプログラムの形式、あるいはそれから生成された実行コードの形式で格納される。プログラムは、実行に先立って、実行コードに変換（コンパイル）されるようにしてもよいし、または実行時に逐次用意されたインタプリタで実行コードに変換されるようにしてもよい。
【０１３６】
また、演算手順は、演算部１ａを構成する処理装置に固有な機械語で直接作成されたコードの形式で格納するようにしてもよい。
【０１３７】
このように、汎用のＰＣ０上に図形の線分近似方法を構築する場合には、演算手順を表現するコードあるいはプログラムは、処理の開始時以前に外部記憶装置５内に格納しておくようにする。この場合には、処理の開始に先立って、あるいは処理の開始直後に、演算手順を表現するプログラムあるいはコードの一部または全部を、バス部１ｆを介して、外部記憶装置５から読み出して、演算手順記憶部１ｂに格納する。
【０１３８】
また、処理の開始時以前に外部記憶装置５内に格納しておいたプログラム形式の演算手順を、処理前に実行コードに変換し、この実行コードを、演算手順記憶部１ｂに格納するように構成してもよい。このような構成では、演算手順記憶部１ｂは、物理的には中間データ記憶部１ｃと同様のＲＡＭ装置を用いればよい。さらに、ＲＡＭ装置の記憶領域を区分けして付けた番地を用いて、記憶領域を管理し、論理的に区分けされた中間データ記憶部１ｃと演算手順記憶部１ｂを形成するようにしてもよい。このように、同一のＲＡＭ装置上に種類の異なる記憶部１ｂおよび１ｃを形成するようにすれば、汎用のＰＣ０上で計算手段を有効に用いて、本実施の形態の図形の線分近似方法を実現できる。なお、演算手順記憶部１ｂへの演算手順コードの読み込みは、処理実行のはじめに、１度に最後の処理までのコードを読み込んでもよいし、処理の実行に伴って、順次読み込んで行ってもよい。さらに、演算手順記憶部１ｂを設けずに、外部記憶装置５より直接演算部１ａへ演算手順コードを読み込むようにしてもよい。このような構成をとっても、本発明の特徴は変わらないが、一般にＲＡＭ装置の読み出しは高速であるため、本実施の形態のように、本発明を汎用のＰＣ０上に構築した場合には、演算手順記憶部１ｂを設けることが望ましい。
【０１３９】
本実施の形態の図形の線分近似方法を最適化専用処理装置上に実現する場合には、演算手順記憶部１ｂを半導体ＲＯＭ装置上に形成するようにすればよい。この場合には、処理前、処理中および処理後を問わず、演算手順は演算手順記憶部１ｂに格納されており、この演算手順に従って演算が実行される。このような構成では、演算手順コードを外部記憶装置５から演算手順記憶部１ｂに読み込む動作が不要なため、処理の立ち上がりの速い装置を実現できる。
【０１４０】
さらに、入力部１ｄにネットワーク通信装置を設け、処理の開始以前または開始直後に、処理手続きコードをＰＣ０以外からネットワークを介して中間データ記憶部１ｃへ格納するようにしてもよい。
【０１４１】
演算部１ａは、演算手順記憶部１ｂに格納された演算手順に従って、後述の演算処理を行う。そのときに、一時的に生成される変数値は、バス部１ｆを介して中間データ記憶部１ｃに格納され、また必要に応じて中間データ記憶部１ｃからバス部１ｆを介して読み取られ、演算に使用される。
【０１４２】
出力部１ｅは、後述の処理終了後に、演算部１ａによって算出された値、または中間データ記憶部１ｃに格納された結果データを読み出して、出力デバイス３に出力する。また、処理中に使用者が処理の履歴を確認するために、データの一部を出力するようにしてもよい。
【０１４３】
バス部１ｆは、演算処理装置１を構成する入力部１ｄ、中間データ記憶部１ｃ、演算手順記憶部１ｂ、演算部１ａおよび出力部１ｅ間のデータ転送を円滑に行うため、各部１ａ〜１ｅ間からのデータを授受し所定部へデータを引き渡す。バス部１ｆは、本発明に必須のものではないが、バス部１ｆを設けることで、各部１ａ〜１ｅの処理が効率的に行われる。
【０１４４】
演算処理装置１からの出力データは、出力デバイス３へ送信されて出力される。出力デバイス３は、プリンタやプロッタ等の印刷出力装置、あるいは出力データに応じてＣＲＴ等の表示器４へビデオ信号を生成出力するビデオ信号出力装置からなる。また、出力デバイス３を、ネットワーク通信機能を有する通信装置によって構成し、出力データを他の装置の出力手段や処理手段へ、ネットワークを通じて出力するようにしてもよい。
【０１４５】
表示器４は、ＣＲＴや液晶表示装置等によって構成され、出力デバイス３からのビデオ信号に応じて出力データを表示する。また、使用者の確認のため、入力データ、処理制御入力および処理状況等を出力するようにしてもよい。
【０１４６】
外部記憶装置５は、磁気テープ装置、磁気ディスク装置または光磁気ディスク装置等の固定／可搬性記録装置、あるいはそれらの組み合わせからなる。外部記憶装置５は、処理の開始に先立って、演算手順コード、プログラムまたは初期データを格納しておくことができる。
【０１４７】
外部記憶装置５として、磁気テープ記録装置、フレキシブル磁気ディスク装置、光磁気ディスク装置等の可搬性記録可能な記録装置を採用し、予め初期データ、処理手続きコードまたはプログラムをＰＣ０あるいはＰＣ０以外の処理装置で該当装置の記録媒体に記録し、これをＰＣ０による処理に先立ってＰＣ０に実装することで、本実施の形態の図形の線分近似方法を実行することができる。
【０１４８】
さらに、外部記憶装置５として、ＣＤ−ＲＯＭ装置等の可搬性読み取り専用記録装置を採用し、処理手続きコードまたはプログラムを該当装置の記録媒体等に記録しておき、これをＰＣ０による処理に先立ってＰＣ０に実装することで、本実施の形態の図形の線分近似方法を実行することができる。特に、このような処理手続きコードまたはプログラムを格納した可搬性の記録媒体は、本発明に従った処理を、図示した構成上で実現すると云う意味で本発明による線分近似を実現する物理的な対象としての重要な実施形態である。
【０１４９】
あるいは、外部記憶装置５として、固定式磁気ディスク装置を採用すると、処理の実行前後にわたり演算手順コードまたはプログラム並びに初期データをＰＣ０内に格納・保持しておくことができる。
【０１５０】
外部記憶装置５は、処理中に生じる中間データを一時格納する記憶領域として利用することができる。特に、処理中に多量の中間データが生じる場合や、中間データ記憶部１ｃの記憶容量を小さくして演算処理装置３の構成を軽便にしたい場合に、外部記憶装置５に中間データ記憶部１ｃ内のデータを一時待避させ、必要時に再度中間データ記憶部１ｃに読み込むことで、中間データ記憶部１ｃの記憶領域を有効に利用できる。
【０１５１】
また、使用者に対する処理履歴を残す意味で、外部記憶装置５に中間データの一部を格納し、処理後に使用者にデータ表示をすることもできる。
【０１５２】
さらに、処理結果を外部記憶装置５に格納し、処理後に使用者にデータ表示を行ったり、可搬性記録媒体に記録し、これをＰＣ０以外の処理装置上で利用したりするようにしてもよい。
【０１５３】
以下、以上のように構成されたＰＣ０が実行する制御動作を説明する。
【０１５４】
まず、入力デバイス２から処理の開始が入力されると、外部記憶装置５内から、あるいはネットワークを介した他の処理装置から入力部１ｄのネットワーク通信装置を介して、後述の演算手順を表したコードが演算手順記憶部１ｂに送信されて格納される。この演算手順を表すコードは、予め外部記憶装置５に格納されていてもよいし、またプログラムの形式で記述された手順を処理の事前に演算部１ａを構成する処理装置に解釈可能な実行コードに変換されたものであってもよい。説明の簡便のため、以下、これらを総称して演算手順コードという。演算手順コードを可搬性記録媒体に格納している場合には、この記録媒体を外部記憶装置５に実装しておく。演算手順記憶部１ｂとしてＲＯＭ装置を採用し、事前に演算手順コードを格納しておく場合には、この動作は省略される。また、演算手順コードの演算手順記憶部１ｂへの格納は、処理開始に先立って行うようにしてもよい。
【０１５５】
次に、入力デバイス２から処理に必要な初期入力データを入力する。入力データは、中間データ記憶部１ｃに格納され、演算手順記憶部１ｂに格納された演算手順コードに表された演算手順に従って、演算部１ａで演算が開始される。演算手順に従って新たな入力データが必要になったときには、順次入力デバイス２から入力するようにしてもよいが、入力デバイス２から処理に必要な初期入力データを入力する際に一連の必要データを一括に入力し、これを中間データ記憶部１ｃ、さらにデータ量が多いときには外部記憶装置５に格納し、演算手順に従ってデータが必要になったときに、中間データ記憶部１ｃまたは外部記憶装置５より参照されるようにしてもよい。さらには、必要な入力データを予め中間データ記憶部１ｃまたは演算手順記憶部１ｂに格納しておくようにしてもよい。この場合には、入力デバイス２からの入力動作は省略される。
【０１５６】
演算部１ａは、演算手順記憶部１ｂに格納された演算手順コードを参照し、後述の演算手順に従って演算を進め、新たに算出された変数値等は中間データとして中間データ記憶部１ｃに一時的に格納され、また必要に応じて中間データ記憶部１ｃのデータが参照、更新される。
【０１５７】
後述の演算手続きによって全ての演算が終了した際に、中間データ記憶部１ｃ、あるいは外部記憶装置５に格納されている結果の最終データは、出力部１ｅから出力デバイス３へ送信される。あるいは、外部記憶装置５に全ての最終データを格納しておき、後からこれを出力データとして利用するようにしてもよい。出力データの利用は、本実施の形態を汎用計算機上で実現したときには、同一計算機上で本発明に関係する処理以外の処理を行うようにしてもよい。例えば、本実施の形態の図形の線分近似方法によって得られた近似線分データを用いて、線図の判定、選別、図形の輪郭抽出等を図１に示す構成で行うことができる。すなわち、ＰＣ０は、ＣＡＤ等の図形加工装置または図形判定装置の構成の一部となり、その機能の一部分、特に入力時のフィルタの機能を担うことができる。あるいは、外部記憶装置５をフレキシブル磁気ディスク装置等の可搬性記録装置で構成し、この可搬性記録媒体上に格納した後、本記録媒体を搬送して他の処理装置上で、本発明に関係する処理以外の処理に利用してもよい。例えば、本実施の形態の図形の線分近似方法によって作成された出力データを、他のＣＡＤ等の図形加工装置または図形判定装置への入力として利用することが可能である。
【０１５８】
出力デバイス３へ送信された出力データは、プリンタ装置等による印刷出力、あるいはこの出力データに基づいたビデオ信号に変換される。あるいはネットワーク通信装置を介して接続されたネットワーク上の他の処理装置に転送されるようにしてもよい。
【０１５９】
出力デバイス３で作成されたビデオ信号は、表示器４へ送信され、表示器４上で出力データを使用者に表示する。
【０１６０】
以上のように構成されたＰＣ０は、以下のような演算手順により線分近似を実行する。
【０１６１】
２次元整数格子内の一意的に１次元鎖と見なし得る、連結したＮ個の座標点列Ａ＝[(ｘ[ｉ],ｙ[ｉ])|ｉ＝１,…,Ｎ]が、初期入力データとして図１の構成内の演算処理装置１の中間データ記憶部１ｃに格納されているものとする。初期入力データは、前述のように、入力デバイス２より読み込まれ、入力部１ｄを介して、中間データ記憶部１ｃに格納される。また、外部記憶装置５より中間データ記憶部１ｃに読み込まれるようにしてもよい。
【０１６２】
ここで、連結しているとは、従来例の説明において述べたように、図８のように座標点を微小面積要素と見なして、その領域が点あるいは線で連結していることを意味する。このようなパターンは、鉛筆等で書かれた曲線をデジタル化したときに現れる。
【０１６３】
また、簡単のため、点列は開いた曲線に対応しており、点列には曲線の連結性に沿って、順番がついているとし、所謂、細線化された曲線とし、図９（ａ）のひげ、同図（ｂ）の解像度以上の折れ曲がり、同図（ｃ）の二重線、同図（ｄ）の交差点はないと仮定する。
【０１６４】
近似すべき元図形は、上述のように、デジタル化された点（ピクセル）の座標値の形で格納され、１組の座標値データ列をなしている。このデータ列は、中間データ記憶部１ｃに格納される。これを「点座標列データ」と云うことにする。いま、このデータ列の数をＮとする。このデータ列上の座標値を計算機上で扱うために、各座標値に対して計算機上で判別できる値を付与する。例えば、これは座標値列上での順番に従って付けられた番号でよい。この番号値は、元図形上で上記のようにデジタル化された点の名称であり、対応する座標値を参照できるようにした上で計算機上でこの点を表すものとして使用される。これを、以降「点データ」と称する。
【０１６５】
例えば、本実施の形態による演算手順を高級言語プログラムで表現した場合、「点座標列データ」は、配列型の変数として表現でき、「点データ」は、配列番号として表現できる。また、例えば、演算手順を演算コードとして表現した場合、「点データ」は、「点座標列データ」のおのおのを格納した、中間データ記憶部１ｃを構成するメモリ装置の番地として表現できる。このようにすれば、元図形の点の並びは「点データ」の並び、あるいは「点座標列データ」によって表現できる。この元図形を表す「点データ」の並び、あるいは「点座標列データ」を「点列データ」と云うことにする。「点列データ」は、「点データ」またはその座標値を単位とするデータ値の列である。計算機上で「点データ」からその座標値を知ることができるため、以下の説明ではこの両者を同一視して説明する。
【０１６６】
本実施の形態では、これら元図形を構成する点列の各点について、頂点となるか否かにより状態が決まり、点列全体の状態を変化させながら、これによって得られる評価関数の最小化を行っていく。この点列の状態を計算機上で表すには、例えば以下のようにすればよい。
【０１６７】
近似線分は、その頂点を指定することで表せるので、頂点となる点の点データを順次格納した「頂点列データ」を用いて、図１の構成上に表現できる。この「頂点列データ」を格納する領域を、中間データ記憶部１ｃ上に用意する。
【０１６８】
さらに、本実施の形態では、線分列の各線分に対して、後述するように、「揺らぎ」の大きさを表す温度パラメタＴのデータ列「温度列データ」を使用する。「温度列データ」を構成する温度Ｔは、「頂点列データ」内の連続する２頂点で作られる各線分に対して、１つずつ与えられ、中間データ記憶部１ｃ上に、この「温度列データ」を格納する領域を用意する。この「温度列データ」内の各値と、「頂点列データ」内の連続する２頂点間の線分とは、例えばデータ列内の値の格納順や中間データ記憶部１ｃでの格納アドレス値などにより互いに対応が取れるようになっている。
【０１６９】
以下の表記では、線分近似のある階層で線分本数をｍ本とする。このとき、頂点はｍ＋１個で、その頂点列の「頂点列データ」をＱ0,Ｑ1,…,Ｑmと表す。ここで、Ｑiはｉ番目の頂点を表すか、またはｉ番目の頂点となる点の値（名称、点データ）を表す。特に、表式中などでは、後者の使い方をする。最初の頂点Ｑ0および最後の頂点Ｑmは、それぞれ元図形を構成する点列の始点および終点と一致する（またはその点の値をとる）とする。
【０１７０】
「頂点列データ」の順に従って、連続する２頂点間で決まる線分から、その２頂点を両端とする点列の各点までの距離の最大値を算出する。最初に格納された点列Ａ＝[(ｘ[ｉ],ｙ[ｉ])|ｉ＝１,…,Ｎ]の順に従って、Ｑ0の点データの次点からＱ1の点データの１つ前の点まで、各々の座標値データを基に、線分Ｑ0Ｑ1までの距離を計算する。
【０１７１】
「頂点データ列」のｉ番目の頂点の点データＱiとｉ＋１番目の頂点の点データＱi+1とで決まる線分と、この２頂点を両端とする点列内の１点の点データＰとの距離は、以下のように算出できる。
【０１７２】
【数２】
0004164286.tif 000003
【０１７３】
但し、ここでは平面ベクトル間の演算で表記した。ｒQi,ｒQi+1 ,ｒPは、それぞれ、点データＱi、点データＱi+1、点データＰの各平面ベクトルを表し、×は、ベクトルの外積演算を、|  |は、ベクトルの絶対値を表す数学記号である。この演算は、中間データ記憶部１ｃに格納してある点データＱi、点データＱi+1、点データＰの座標値データを基に、演算部１ａにより、通常の四則演算および平方根の開平演算を行うことで求めることができる。
【０１７４】
「頂点データ列」のうちｉ番目の頂点の点データＱiと、ｉ＋１番目の頂点の点データＱi+1との間にある（但し、Ｑi 、Ｑi+1を含まず）すべての点データについて、順次上記距離を算出し、その最大値をｉ番目の線分の最大距離ｄiとする。同時に、その最大距離ｄiを与える点データの値を頂点候補点データとする。この最大距離ｄiと閾値vtxth0とを比較し、最大距離ｄiの値が閾値vtxth0以上のときには、頂点候補点データを新たな点として、「頂点列データ」内のｉ番目の頂点の点データＱi とｉ＋１番目の頂点の点データＱi+1間に挿入した、新たな「頂点列データ」を作成し、これを改めて中間データ記憶部１ｃに格納し直す。
【０１７５】
さらに、「頂点列データ」内のｉ番目の頂点とｉ＋１番目の頂点とを結んだ、ｉ番目の線分に対する温度Ｔiの値を所定の初期値にリセットし、この値をコピーして、新たな線分に対応する温度として、「温度列データ」内のｉ番目の線分に対する温度Ｔiの後に挿入した、新たな「温度列データ」を作成し、これを改めて中間データ記憶部１ｃに格納し直す。
【０１７６】
このようにして、ｉ番目の線分に関して最大距離ｄiの値が閾値vtxth0以上のときには、ｉ番目の線分から派生した、新たなｉ番目と新たなｉ＋１番目の線分が生成され、それに対応した新たなｉ＋１番目の頂点の頂点が、「頂点列データ」内の対応した位置に作られる。同時に、新たなｉ番目およびｉ＋１番目の各線分にそれぞれ対応した温度ＴiおよびＴi+1が「頂点列データ」内の各々対応する頂点と同じ順序で含まれる「温度列データ」が作成される。
【０１７７】
これにより、「頂点列データ」と「温度列データ」は、新たな線分の生成に対しても、対応関係を保ったまま新たなものに置き換わる。
【０１７８】
また、最大距離ｄiの値が閾値vtxth0以上のときには、もとのｉ番目の線分より派生した２線分の温度は、同じく所定の初期値にリセットされる。
【０１７９】
一方、最大距離ｄiの値が閾値vtxth0より小さいときには、以下のようにｉ番目の線分の最大距離ｄiと温度パラメタＴiとを用いて、判定用の関数Ｄ(ｄi,Ｔi)の値を算出する。
【０１８０】
関数Ｄ(ｄ,Ｔ)は、以下で発生する乱数に対応して、０から１までの値をとる関数であり、「揺らぎ」の大きさを表すパラメタＴの値がある値、例えば０を取るときに、０から閾値vtxth0までのｄの値に対して、０を与えるものであり、ｄを固定したときに、Ｔの減少に関しては非増加の関数となっている。このＴは、その値が大きいときに「揺らぎ」が大きくなるようにとり、その最小値は、一般には何でもかまわず、後述のアニーリング動作でＴを減少していく際に変動させるＴの最終値であればよいが、ここでは説明の簡便のために０とする。基本的には、本実施の形態では、アニーリング時に「揺らぎ」を単調（非増加）に小さくしていく動作であり、固定したｄの値に対して、関数Ｄ(ｄ,Ｔ)が単調（非増加）に小さくなり、最終的には、発生する乱数Ｒの最小値以下となるように、パラメタをＴを変化させる。また、Ｄ(ｄ,Ｔ)の取り得る値は、発生する乱数Ｒに対応した値であればよい。
【０１８１】
また、Ｔを固定したときに、関数Ｄ(ｄ,Ｔ)は、ｄの関数として単調増加（非減少）関数であり、距離ｄが大きくなるに従って、発生する乱数Ｒに対して大きくなる確率が高いものになるとする。
【０１８２】
特に、本発明に好適には、判定する元図形の分解限界であるピクセルサイズｄ0として非０のＴのときに ｄ ＞ ｄ0  でＤ(ｄ,Ｔ)が有限の値をもつものである。
【０１８３】
このようなＤ(ｄ,Ｔ)として、次のような関数を計算すればよい。
【０１８４】
【数３】
0004164286.tif 000004
【０１８５】
例えば、図３に示すような関数を取ることができる。図３中、横軸は距離ｄを表し、縦軸はＤを表し、Ｔ ＝ ０，Ｔ1，Ｔ2，Ｔ3（但しＴ1 ＜ Ｔ2 ＜ Ｔ3）の値に対するＤとｄの関係を示す。Ｔ＝０では、ｄが０より大きく、vtxth0より小さい範囲で、Ｄは“０”であり、ＴがＴ1，Ｔ2，Ｔ3と大きくなるにつれてＤの値が非減少に変化する。この関数Ｄの値がランダムに発生したＲの値より小さいときに、新たな頂点を作成する。
【０１８６】
この関数を計算によって算出するのではなく、ｄ，Ｔの値とＤ(ｄ,Ｔ)の値の関係をテーブルに記載したものを用いてもよい。このテーブルは、外部記憶装置５あるいは中間データ記憶部１ｃに格納されており、必要に応じてテーブルの該当部分を参照することで、Ｄ(ｄ,Ｔ)の値を得ることができる。一般に記憶領域の参照は、上記式（３）の数値計算より早く実行されるので、このような構成では実行速度を速くすることができる。また、この関数をｄの区間を定めた線形関係、あるいはｄ，Ｔについての多項式で近似して表現してもよい。
【０１８７】
この関数Ｄ(ｄ,Ｔ)、あるいはテーブルを用いて、ｉ番目の線分についてのＤ(ｄi,Ｔi)の値を求め、この値に対して、０から１までの乱数を発生して、Ｒ＞Ｄ(ｄi,Ｔi)のときには新たな頂点を発生すると判定する。
【０１８８】
同時に温度パラメタＴiをより小さな値に変更する。
【０１８９】
例えば、
【０１９０】
【数４】
0004164286.tif 000005
【０１９１】
の第一式の右辺のＴに、ｉ番目の線分の温度Ｔiを代入して、右辺の温度Ｔを新たなｉ番目の線分の温度Ｔiとする。ここで、Ｔ0は、温度パラメタの初期値であり、ｎは、アニーリングの規定回数である。
【０１９２】
新たな頂点を発生すると判定されたときは、次のようにして新たな頂点を作成する。新たな頂点は、最大距離ｄiが閾値vtxth0を越えなかったときと同様に、最大距離ｄiを与える頂点候補点データが「頂点列データ」内のｉ番目の頂点の点データＱiとｉ＋１番目の頂点の点データＱi+1との間に挿入され、これにより、新たな「頂点列データ」を作成し、これを改めて中間データ記憶部１ｃに格納し直す。
【０１９３】
さらに、「頂点列データ」内のｉ番目の頂点とｉ＋１番目の頂点を結んだｉ番目の線分の対する温度Ｔiの値を、上記のようなより小さい値に変えて、この値をコピーして、新たな線分に対応する温度として、「温度列データ」内のｉ番目の線分の対する温度Ｔiの後に挿入し、新たな「温度列データ」を作成し、これを改めて中間データ記憶部１ｃに格納し直す。
【０１９４】
また、ｉ番目の線分について求めたＤ(ｄi,Ｔi)の値に対して発生した乱数Ｒが、Ｒ ＞ Ｄ(ｄi,Ｔi)でないときには、新たな頂点を発生せずに上記のように温度Ｔiを小さなものに変える。このときには新たな線分も作られないので、「温度列データ」内温度パラメタの数も変動しないため、「温度列データ」内の温度Ｔiの値を前記式（４）に従ってより小さい値に変えればよい。
【０１９５】
このようにして、ｉ番目の線分についての処理を行った後、同様にｉ＋１番目の線分について処理を行う。ｉ番目の線分についての処理で使用した頂点の点データＱiと点データＱi+1のうち点データＱi+1と、「頂点列データ」内で点データＱi+1の後にある頂点の点データＱi+2を新たな２頂点として、頂点Ｑiと頂点Ｑi+1について行った処理と同じ処理を行う。このようにして、連続する２頂点の後ろの頂点を指標に、次の線分へ処理を進めて行けば、ｉ番目の線分について、頂点Ｑiおよび頂点Ｑi+1間に新たな頂点が発生するか否かによらず、当初の線分列に対して順次処理を行うことができる。これを「頂点列データ」の最後の頂点に達するまで続ける。
【０１９６】
ここでは、新たに発生する頂点を処理の途中で順次「頂点列データ」に挟み込み、「頂点列データ」をその都度更新して行く処理について説明したが、これに限らず、中間データ記憶部１ｃ内に「新頂点候補列データ」を格納する領域を設ける構成を取ることもできる。この場合は、はじめの「頂点列データ」に沿って順次連続する２頂点に関して処理を行っていく上で、新たな頂点が発生した場合に、それを挟み込んだ頂点列をこの「新頂点候補列データ」に書き込んで行く。上記例では、処理がｉ番目の頂点の点データＱiとｉ＋１番目の頂点の点データＱi+1に及んで、この間に新たな頂点Ｐが生じたときには、「新頂点候補列データ」にＱi，ＰおよびＱi+1を順次追加して行く。これにより、「新頂点候補列データ」には、この時点でＱiからＱi+1までの新たな頂点の配置が書き込まれて行く。これを、「頂点列データ」の最後の頂点に達するまで続け、最後の線分についての処理が終わった後に、「新頂点候補列データ」を新たな「頂点列データ」として、中間データ記憶部１ｃ内に格納し直し、「頂点列データ」の更新を行う。「新頂点候補列データ」は、この時点か、または「頂点列データ」に沿って処理を始める時点で初期化すればよい。
【０１９７】
このようにして得られた新たな「頂点列データ」内の隣接する２頂点には、各々線分が１つ対応し、また、この各々の線分には、「温度列データ」内の各温度パラメタが１つ対応している。線分列の各線分に対する温度パラメタは、この線分について、次回の処理で線分から点列までの最大距離が閾値vtxth0より小さいときに、新たな頂点を発生するかどうかの判定を行う「揺らぎ」の大きさを決める指標となる。また、この温度パラメタは、この線分がどのように派生したかの履歴によって大きさが異なっている。すなわち、線分処理のはじめからある線分、または線分から点列までの最大距離が閾値vtxth0以上になることで発生した線分では、温度パラメタの値は所定の初期値になっている。一方、線分から点列までの最大距離が閾値vtxth0より小さいときに「揺らぎ」を発生して確率的に線分を発生して得られた線分、または線分から点列までの最大距離が閾値vtxth0より小さいときに「揺らぎ」を発生しても新たな線分を発生しなかった線分では、その「揺らぎ」を発生した確率的な新線分の発生の判定を行う度に温度パラメタが小さくなるために、その判定の回数によって温度パラメタの大きさが異なっている。
【０１９８】
「頂点列データ」に沿って連続する２頂点からなる線分に関しての上記処理を繰り返して行けば、線分から点列までの最大距離が閾値vtxth0より小さいものは「揺らぎ」を発生して確率的に新たな線分を発生するかどうかを判定するが、線分から点列までの最大距離が閾値vtxth0より小さい状況が続く限り、その「揺らぎ」の大きさは小さくなり、新たな線分を発生する確率は同じ最大距離に対しても小さくなる。これがアニーリングの指定回数ｎを越えると、温度パラメタＴは０となり、線分から点列までの最大距離が閾値vtxth0より小さい場合には、確率的にも新たな線分は発生しなくなる。この処理は、シュミレーテッドアニーリングのアニーリングの処理に対応している。一方、線分から点列までの最大距離が閾値vtxth0以上になることで生成された線分は、温度パラメタＴが所定の初期値になっており、以降この線分に関して線分から点列までの最大距離が閾値vtxth0より小さくなったときに、新たな線分を発生する確率も所定の初期値となる。
【０１９９】
温度パラメタＴの減少は、所定の回数ｎでＴを０にするような単調な減少であればどのようなものでもよく、特に、線分近似を行う元図形の傾向がある程度決まっているときには、その元図形の特徴に応じて、前記式（４）以外の解析式によって算出したり、減少率を細かく規定したテーブルを中間データ記憶部１ｃに格納したりしてもよいが、前記式（４）による算出は、計算処理も少なく、中間データ記憶部１ｃに余分な記憶領域を設ける必要もないため、一般の線分近似に対しては望ましい構成である。
【０２００】
本実施の形態の線分近似では、一般のシミュレーテッドアニーリング法のように、通常評価関数を順次減少させて行く最適化方法になっていないため、一度「揺らぎ」を生じせしめた場合、評価関数は大きく変化してしまい、トラップの原因を大きくはずれる。そのため、一般のシミュレーテッドアニーリング法に比べ、アニールにおける「揺らぎ」の大きさの減少具合を大きくとることができ、アニーリングの規定回数ｎは、１〜１０回程度で十分に動作を行うことができる。特に、処理の速度を向上させたいときには、ｎを１〜２に、精度を向上させたいときには、ｎを８〜１０に取ることが望ましい。
【０２０１】
このように、本実施の形態では、線分近似において、線分から点列までの最大距離が閾値vtxth0より小さい場合のみ「揺らぎ」を生じた確率的な判定を行う。さらに、近似した各線分からその線分の両端で挟まれる点列内の部分点列の各点までの最大距離を基に「揺らぎ」を生じて、確率的に新たな頂点を発生し、線分を増やすことで、線分近似を行っていく過程の中に「揺らぎ」のアニーリング動作を組み込んでいる。このように、必要な部分にのみ確率的な判定を行い、そのアニーリング動作を線分近似の動作の組み込むため、一般のシミュレーテッドアニーリング法に比べ、アニーリングの反復動作に要する処理および反復動作も少ない構成をとっている。
【０２０２】
さらに、本実施の形態では、線分列の各線分毎に温度Ｔをもち、これを減じていくアニーリング動作も各線分毎に異なる様子で行われる。そのため、線分毎の様相に応じて、アニーリング動作での温度パラメタＴの減少の仕方が異なり、より効果的なアニーリング動作を提供できる。
【０２０３】
上記動作を繰り返して行くことで、線分列を構成する各線分で、線分より対応する部分点列の各点まで最大距離が減少して行き、またアニーリングによって温度パラメタが小さくなって行くため、新たな線分が生成し難くなる。最終的に、各線分で温度パラメタＴが０になると、閾値vtxth0以下の最大距離では線分は発生し難くなり、動作を続けても線分列に新たな変化は生じなくなる。そのため、すべての線分の温度パラメタＴが０になった時点で処理を終了する。
【０２０４】
この処理終了判定は、「温度列データ」内の各温度より判定することができる。あるいは、線分近似で線分が発生する度に「線分本数」を加算し、各線分で温度パラメタＴが０になる度に「０温度線分本数」を加算する。この「線分本数」と「０温度線分本数」が一致したときに処理を終了すればよい。
【０２０５】
また、線分近似過程中で、温度Ｔが０になった線分に関しては、以降新たな線分を生成することがなく、以降この線分についての判定は不要であるので、処理の過程で、温度Ｔが０となった線分については判定を行わない構成をとることが可能である。この構成をとることで、不要な処理を行わないより効率的な線分近似を行うことができる。
【０２０６】
次に、図４に従って、本実施の形態のＰＣ０の演算部１ａが実行する線分近似の動作を説明する。
【０２０７】
ステップＳ１は、初期化動作であり、中間データ記憶部１ｃの各領域にある諸値をクリアする。次に、初期温度の大きさＴ0、並びにアニーリングの規定回数ｎを設定し、点列各点の初期状態を設定する。初期温度の大きさ Ｔ0、並びにアニーリングの規定回数ｎの値は、初期データとして入力デバイス２より与えられるか、その他の操作により中間データ記憶部１ｃに格納される。元図形の点列は、前述のように、「点列データ」として中間データ記憶部１ｃ等に格納されているとする。また、「頂点列データ」の初期値として、元図形を構成する点列の始点と終点の２点「点データ」からなるデータを中間データ記憶部１ｃに格納しておく。また、「温度列データ」として、元図形を構成する点列の始点と終点の２点を結ぶ線分に対応した１つの温度の値を、初期温度の大きさＴ0とともに中間データ記憶部１ｃに格納する。
【０２０８】
ステップＳ２からステップＳ１２までは、ある階層にある線分列の各線分について線分近似の動作を行う。具体的には、線分列を表す「頂点列データ」内の連続する２頂点を指定することで線分が指定されるので、「頂点列データ」より順次、連続する２頂点を読み込んで行く。ステップＳ２では、線分がその階層の最終線分を越えるかどうかを判定し、最終線分を越えたときにはステップＳ１４へ、最終線分を越えないうちはステップＳ３以降の動作へ進む。
【０２０９】
ステップＳ３では、「温度列データ」から、その線分に対応する温度パラメタＴiの値を読み込み、それが“０”かどうか判定する。Ｔiの値が０のときには、この線分はすでにアニールが終わっているとして、ステップＳ１３の次の線分に対する動作へ移る。Ｔiの値が０でないときにはステップＳ４へ移る。
【０２１０】
ステップＳ４では、その線分の両端の２頂点で挟まれた点列に対して、「点列データ」より順次その点データを読み込んで、両端の２頂点の点データと点列の点データより、前記式（２）を用いて点列の点から線分までの距離を算出し、その最大値を最大距離ｄiとして求める。同時に、その最大距離ｄiを与える点の点データを「新頂点データ」として保持する。
【０２１１】
ステップＳ５では、最大距離ｄiと閾値vtxth0とを比較し、最大距離ｄiが閾値vtxth0より大きければステップＳ６へ進む。一方、最大距離ｄiが閾値vtxth0以下であればステップＳ７へ進む。
【０２１２】
ステップＳ６では、温度パラメタＴiの値を初期温度の大きさＴ0にリセットする。
【０２１３】
ステップ７では、最大距離ｄiと温度パラメタＴiの値を基に、前記式（３）や中間データ記憶部１ｃに格納されたテーブル等を用いて「揺らぎ」の判定量Ｄ(ｄi, Ｔi)を求める。
【０２１４】
ステップＳ８では、０から１までの乱数Ｒを発生する。
【０２１５】
同時に、ステップＳ９で、次回以降の判定でこの線分についての温度をアニールするために、温度Ｔiの値が０になるまで、前記式（４）に従って温度パラメタＴiの値を変更する。その後、「揺らぎ」による判定ステップＳ１０へ進む。
【０２１６】
ステップＳ１０では、ステップＳ７で求めた判定量Ｄ(ｄi, Ｔi)とステップＳ８で求めた乱数Ｒを用いて、「揺らぎ」による判定を行う。Ｒ ＞ Ｄ(ｄi, Ｔi)のときには、揺らぎにより新たな頂点が発生するとして、ステップＳ１１へ進む。そうでないときには、次の線分について動作を行うために、ステップＳ１３を通ってステップＳ２へ進む。
【０２１７】
ステップＳ１１では、新たな頂点を発生する。ステップＳ４で保持して「新頂点データ」の点データを今読み込んだ「頂点列データ」内の連続する２頂点の点データ間にはさんだ、新たな「頂点列データ」を作成し、これを中間データ記憶部１ｃに格納し直す。
【０２１８】
同時に、ステップＳ１２では、新たに生成した線分に対応した温度パラメタを含むように、「温度列データ」を更新する。ステップＳ６またはステップＳ９で設定した温度パラメタＴiの値と同じ値の新たな温度パラメタを、「温度列データ」内のＴiの後ろへ挿入して、新たな「温度列データ」を作成し、これを中間データ記憶部１ｃに格納し直す。
【０２１９】
その後、ステップＳ１３を通って、ステップＳ２へ戻り、次の線分に動作を進める。
【０２２０】
ステップＳ２で、線分がその階層の最終線分を越えているときには、ステップＳ１４へ動作が移る。ステップＳ１４では、「温度列データ」内のすべての温度パラメタの値が“０”になったとき、線分近似の終了を判定する。このとき、ステップＳ１５で結果を出力した後、動作を終了する。
【０２２１】
ステップＳ１４で、未だ「温度列データ」内に“０”以外の温度パラメタがあると判定されたときには、ステップＳ１６を通ってステップＳ２へ戻り、再度「頂点データ」の始めから、連続する２頂点で表される線分に関しての処理を繰り返す。
【０２２２】
（第２の実施の形態）
本発明の第２の実施の形態では、線分から部分点列の各点までの最大距離が閾値vtxth0より小さいときに、判定に使用する距離と「揺らぎ」のアニーリング動作において第１の実施の形態と異なる。
【０２２３】
第１の実施の形態では、線分から部分点列の各点までの最大距離が閾値vtxth0より小さいときに、線分とその線分の両端の頂点で挟まれた部分点列との距離を表すのに、線分から部分点列の各点までの最大距離ｄiを代表として使用し、Ｄ(ｄi,Ｔi)を計算し、これと発生する乱数Ｒとの大小関係より新たな頂点を生成するか否かの判定を行っていた。
【０２２４】
ところで、従来例の問題点である図１２において、図１２（ｂ）のように、基準線を引いて各点列に対する距離を計算すると、どの点も同じ距離になり、すべての点が最大距離を与える点となっている。このような場合に、最大距離の大きさのみでなく、その最大距離を与える点の現れる頻度も考慮することで、より誤動作が少ない処理が提供できる。すなわち、このような最大距離を与える点が多数存在するときには、部分点列に対する最大距離ではなく、部分点列内のすべての点について「揺らぎ」を生じて新たな頂点が生じるか否かの判定を行うことで、１点、１点においては「揺らぎ」により新たな頂点を発生する確率が小さくても、部分点列全体では新たな頂点が生じ易くなり、ひいては元図形の全体の特徴を抽出し易くなる。第１の実施の形態では、最大距離を代表として使用することで処理数が少ない高速処理に好適な構成となっているが、本実施の形態を適用すれば、むしろ誤動作に対する安定性と精度を重んじた処理を行う構成とすることができる。
【０２２５】
さらに、第１の実施の形態では、線分から部分点列の各点までの最大距離が閾値vtxth0より小さい場合が続く限り、温度に対してアニールを行ったが、本実施の形態では線分から部分点列の各点までの最大距離が閾値vtxth0より小さいときに「揺らぎ」により新たな頂点が生じた場合にのみ温度の値を小さくするアニールを行う。
【０２２６】
このようにすることで、頂点が増加しない限りは「揺らぎ」の大きさが変化せず、同じ確率で線分より距離が離れた点を新たな頂点候補として検出できるため、図１２のような誤動作を防ぐ意味での精度がさらに向上し、効果的なアニーリングを与えることができる。
【０２２７】
本実施の形態を実現するためのハードウェア構成は、第１の実施の形態で示したと同様に、図１のようなハードウェア構成を採ることができ、その詳細は、第１の実施の形態で詳しく述べているため、ここでは省略する。
【０２２８】
次に、図５に従って、本実施の形態の線分近似の動作を説明する。
【０２２９】
ステップＳ２１は初期化動作であり、中間データ記憶部１ｃの各領域にある諸値をクリアする。次に、初期温度の大きさＴ0、並びにアニーリングの規定回数ｎを設定し、点列各点の初期状態を設定する。初期温度の大きさ Ｔ0、並びにアニーリングの規定回数ｎの値は、初期データとして入力デバイス２より与えられるか、その他の操作により中間データ記憶部１ｃに格納される。元図形の点列は、前述のように、「点列データ」として中間データ記憶部１ｃ等に格納されているとする。また、「頂点列データ」の初期値として、元図形を構成する点列の始点と終点の２点「点データ」からなるデータを中間データ記憶部１ｃに格納しておく。また、「温度列データ」として、元図形を構成する点列の始点と終点の２点を結ぶ線分に対応した１つの温度の値を、初期温度の大きさＴ0と中間データ記憶部１ｃに格納する。
【０２３０】
ステップＳ２２からステップＳ４１までは、ある階層にある線分列の各線分について線分近似の動作を行う。具体的には、線分列を表す「頂点列データ」内の連続する２頂点を指定することで線分が指定されるので、「頂点列データ」より順次、連続する２頂点を読み込んで行く。このとき同時に「温度列データ」より順次温度パラメタＴiも読み込んで行く。ステップＳ２２では、線分がその階層の最終線分を越えるかどうかを判定し、最終線分を越えたときにはステップＳ４３へ、最終線分を越えないうちはステップＳ２３以降の動作へ進む。
【０２３１】
ステップＳ２３では、「温度列データ」から、その線分に対応する温度パラメタＴiの値を読み込み、それが“０”かどうかを判定する。Ｔiの値が０のときには、この線分はすでにアニールが終わっているとして、ステップＳ４２の次の線分に対する動作へ移る一方、Ｔiの値が０でないときには、ステップＳ２４へ移る。
【０２３２】
ステップＳ２４からステップＳ３８までは、ある線分に対して、この線分の両端の２頂点で挟まれる「点列データ」内の各点についての処理を行う。「点列データ」内で、線分の２頂点の第１の頂点の点データの後に続く点データから第２の頂点の点データの直前の点データまでの点データを順次読み込みながら、ステップＳ２５からステップＳ３８の動作を繰り返す。
【０２３３】
ステップＳ２４では、点列操作のための初期化を行う。
【０２３４】
まず、閾値フラグをＯＦＦ（＝０）に初期化する。閾値フラグは、該当線分に関する部分点列内の各点について順次処理を行っていく過程で、それまでの点において該当線分からその点までの距離が閾値vtxth0以上となったことがあるかどうかを判定するフラグである。閾値フラグは、本実施の形態に必須のものではないが、このフラグを用いることにより処理が簡略化され、高速処理が行えるため、このフラグを設けることが好ましい。すなわち、線分列のある線分に関する処理中に１度でも、後述のステップＳ２７で距離が閾値vtxth0を越えたと判定されると、後述のステップＳ２８でこのフラグをＯＮ（＝１）に設定する。この場合は、該当線分に関して少なくとも１つは線分からの距離が閾値vtxth0以上となる点が存在するため、その線分の最大距離は閾値vtxth0以上となり、「揺らぎ」による判定は行わなくてもよい。このため、部分点列内の各点についての処理を行っていく途中でも、一度この閾値フラグがＯＮに設定されれば、それ以降の処理は、後述のステップＳ２５で算出された距離について最大となる点を求めて行けばよい。
【０２３５】
次に、頂点発生フラグの初期化をＯＦＦに初期化する。この頂点発生フラグは、該当線分に関する部分点列内の各点について順次処理を行っていく過程で、それまでの点において「揺らぎ」により頂点が発生したことがあるかどうかを判定するフラグである。後述のステップＳ３１以降の「揺らぎ」による頂点の発生の処理において、「揺らぎ」による該当線分の頂点が一度発生してあれば、最大距離が閾値vtxth0より小さくなったときにはその頂点を利用すればよく、複数の頂点発生の処理を行う必要がないため、本フラグを用いて不要な処理を省略することができる。
【０２３６】
また、このとき、後述のステップＳ３０で最大距離を求めるための「仮最大値データ」と「頂点候補点データ」の初期化を行う。
【０２３７】
ステップＳ２４は、線分列の各線分について、この部分点列の各点についての処理に先立ち、これらの値を初期化するものである。その後、処理をステップＳ２５へ進める。
【０２３８】
ステップＳ２５では、該当線分について、その線分の両端の頂点で挟まれる部分点列内のある点からその線分までの距離を前記式（２）を用いて算出する。例えばｉ番目の線分について、対応する部分点列内のj番目の点に関して、「頂点データ」内のｉ番目の頂点とｉ＋１番目の頂点の点データおよび「点列データ」内のｉ番目の頂点とｉ＋１番目の頂点の間にあるj番目の点の点データを前記式（２）に代入して距離ｄ(i)jを算出すればよい。
【０２３９】
ステップＳ２６では、閾値フラグを判定する。閾値フラグがＯＮになっていれば、それまでの部分点列内の点に線分までの距離が閾値vtxth0以上のものがあり、この線分に関しては最大距離は閾値vtxth0以上となるため、「揺らぎ」による判定を行う必要はなく、この線分についての温度パラメタＴiを初期温度の値Ｔ0にリセットして最大距離とそれを与える点を求める処理を行えばよい。これらの処理を行うため、ステップＳ２９以降へ処理を進める。閾値フラグがＯＮになっていないときは、距離と閾値vtxth0の比較をするため、ステップＳ２７へ進む。
【０２４０】
ステップＳ２７では、ステップＳ２５で求めた距離ｄ(i)jと閾値vtxth0とを比較し、ｄ(i)j が vtxth0以上であれば、この線分の最大距離は閾値vtxth0以上になるとして、ステップＳ２８で閾値フラグをＯＮに設定して、ステップＳ２９へ処理を進める。
【０２４１】
ステップＳ２８では、閾値フラグをＯＮに設定する。閾値フラグは、例えば中間データ記憶部１ｃに領域を設けられた整数値データであってよく、値０をＯＦＦに値１あるいは値０以外の整数値をＯＮに対応させればよい。閾値フラグをＯＮに設定後、ステップＳ２９へ進む。
【０２４２】
ステップＳ２９では、該当線分に対応する温度パラメタＴiを初期温度の値Ｔ0にリセットする。温度パラメタＴiは、例えば予め線分列に沿って線分を変えて行くために、「頂点列データ」から頂点を順次読み出す際に、同時に「温度列データ」から読み込まれ、別途格納されていてもよいし、直接「温度列データ」内の指定箇所の値を変更してもよい。温度パラメタＴiのリセット後、ステップＳ３０へ進む。
【０２４３】
ステップＳ３０では、最大距離とそれを与える点データとを求める。ここでは、「仮最大値データ」と「頂点候補点データ」を用いる。これらを格納する領域を中間データ記憶部１ｃに確保しておく。「仮最大値データ」と「頂点候補点データ」の各点についての処理に先立ち、初期化される。これは、例えばステップＳ２４の点列操作の初期化時に行われる。「仮最大値データ」の初期値は“０”に、「頂点候補点データ」の初期値は該当線分の両端をなす頂点のいずれかの点データをとればよい。該当線分に対応する部分点列の各点の処理を進める過程で、ステップＳ２５で求まった距離ｄ(i)jと「仮最大値データ」の値とを比較し距離ｄ(i)jの方が大きいときには、「仮最大値データ」の値を距離ｄ(i)jの値とし、同時に、「頂点候補点データ」の値をそのときの部分点列の点の点データとする。これを部分点列の各点について行えば、部分点列の終点まで来たときには、距離ｄ(i)jの最大値とそれを与える点の点データが各々「仮最大値データ」および「頂点候補点データ」の値となっている。ステップＳ３０では、この判定と代入を行う。この後、点列の終わりを判定するステップＳ３８へ進む。
【０２４４】
一方、ステップＳ２７で、ｄ(i)j が vtxth0より小さいと判定された場合には、処理はステップＳ３１以降の「揺らぎ」による新たな頂点発生の処理へ進む。
【０２４５】
ステップＳ３１では、頂点発生フラグがＯＮに設定されているかどうかを判定する。頂点発生フラグは、ステップＳ２４では線分列の各線分について、この部分点列の各点についての処理に先立ちＯＦＦに初期化されている。後述のステップＳ３４で、新たな頂点が発生すると判定された場合に、後述のステップＳ３７でＯＮに設定される。頂点発生フラグがＯＮに設定されている場合は、既に「揺らぎ」により発生する頂点の候補が求められており、処理が部分点列の最後まで到達したときに、求まっている最大距離が閾値vtxth0より小さいときには、この頂点候補を用いて頂点を発生すればよい。このため、頂点発生フラグがＯＮのときにはステップＳ３２以降の「揺らぎ」による処理を省略して、点列の終わりを判定するステップＳ３８へ進む。頂点発生フラグがＯＮに設定されていないときには、ステップＳ３２以降の「揺らぎ」による処理を行う。
【０２４６】
ステップＳ３２では、ステップＳ２５で求めた距離ｄ(i)j と温度パラメタＴiの値を基に前記式（３）や中間データ記憶部１ｃに格納されたテーブル等を用いて「揺らぎ」の判定量Ｄ(ｄ(i)j, Ｔi)を求める。
【０２４７】
続くステップＳ３３では、０から１までの乱数Ｒを発生する。
【０２４８】
ステップＳ３４では、ステップＳ３２で求めた判定量Ｄ(ｄ(i)j, Ｔi)とステップＳ３３で求めた乱数Ｒを用いて「揺らぎ」による判定を行う。Ｒ ＞ Ｄ(ｄ(i)j, Ｔi)のときには、揺らぎにより新たな頂点が発生するとしてステップＳ３５へ進む。そうでないときには、点列の終わりを判定するステップＳ３８へ進む。
【０２４９】
ステップＳ３５では、このときの点の点データを頂点候補として格納する。
【０２５０】
次のステップＳ３６では、次回以降の判定でこの線分についての温度をアニールするために、温度Ｔiの値が０になるまで前記式（４）に従って温度パラメタＴiの値を変更する。その後、頂点発生フラグを設定するステップＳ３７へ進む。
【０２５１】
ステップＳ３７では、頂点発生フラグをＯＮに設定し、その後、点列の終わりを判定するステップＳ３８へ進む。
【０２５２】
ステップＳ３８では、点列の終わりを判定し、点列の最終点まで処理が到達していたときには、ステップＳ４０の頂点列の更新へ進む一方、そうでないときには、ステップＳ３９を通ってステップＳ２５へ処理が戻り、部分点列内の次の点について処理を移して行く。
【０２５３】
このようにすることで、ステップＳ２５からステップＳ３８までの動作で、線分列内の該当線分に対する部分点列の各点について順次処理を行っていくうちに閾値vtxth0より小さい距離をもつ点に対しては、判定量Ｄ(ｄ(i)j, Ｔi)と乱数Ｒを用いた「揺らぎ」による判定が行われ、頂点が発生しないときには、温度パラメタＴiの値を変更することなく、次々の点に対して処理が行われる。一方、一旦頂点が発生した場合には、その線分に関してはその頂点を新たな頂点とし、以降の点に関しては「揺らぎ」による判定処理は行われない。
【０２５４】
ステップＳ４０では、「頂点列データ」の更新を行う。閾値フラグと頂点発生フラグの判定を行い、閾値フラグがＯＮであれば、最大距離が閾値vtxth0以上になっているとして、ステップＳ３０で格納した「頂点候補点データ」を新たな頂点として、頂点発生フラグがＯＮであれば「揺らぎ」により頂点が発生したとして、ステップＳ３５で格納した頂点候補の点データを用いて「頂点列データ」の更新を行う。閾値フラグおよび頂点発生フラグの双方ともＯＦＦの場合には、元の「頂点列データ」のまま更新を行わない。
【０２５５】
あるいは、ステップＳ３０で格納する「頂点候補点データ」とステップＳ３５で格納する頂点候補の格納場所は、中間データ記憶部１ｃの同じ記憶領域とし、閾値フラグまたは発生フラグの何れかがＯＮとなったときに、この中間データ記憶部１ｃの領域の値を用いて「頂点列データ」の更新を行うこともできる。線分列内の該当線分に対応する部分点列の各点について、次処理を行っていくうちに、距離が閾値vtxth0以上になった時点で、ステップＳ３０でその点の点データが「頂点候補点データ」として上書きされ、距離が閾値vtxth0以上になることなく部分点列の終点まで達したときに、ステップＳ３４により頂点生成の判定がなされていれば、ステップＳ３５により頂点候補が検出され、その値が「揺らぎ」によって生じた頂点となっている。
【０２５６】
「頂点列データ」の更新は、該当する線分に対する頂点の間に上記いずれかの頂点候補の点データを挿入した、新たな「頂点列データ」を作成し、中間データ記憶部１ｃに再度格納することで行われる。
【０２５７】
その後、ステップＳ４１で、「温度列データ」の更新を行う。
【０２５８】
ステップＳ４１では、閾値フラグと頂点発生フラグの判定を行い、いずれかのフラグがＯＮとなったときには、ステップＳ２９またはステップＳ３６で設定した温度パラメタＴiの値と同じ値の新たな温度パラメタを、「温度列データ」内のＴiの後ろへ挿入して、新たな「温度列データ」を作成し、これを中間データ記憶部１ｃに格納し直す。温度パラメタＴiの値については、線分列内の該当線分に対応する部分点列の各点について、次処理を行っていくうちに距離が閾値vtxth0以上になった時点で、ステップＳ２９で初期温度Ｔ0が温度Ｔiの値として上書きされ、距離が閾値vtxth0以上になることなく部分点列の終点まで到達したときに、ステップＳ３４により頂点生成の判定がなされていれば、ステップＳ３５によりアニールされた温度が温度Ｔiの値として格納されている。
【０２５９】
また、温度パラメタＴiの値は、各線分に関して対応する部分点列の各点について、次処理を行っていくうちに、距離が閾値vtxth0以上になった時点で、初期温度Ｔ0の値にリセットされ、距離が閾値vtxth0以上になることなく部分点列の終点まで到達したときに、ステップＳ３４により頂点生成の判定がなされていれば、ステップＳ３５によりその値がアニールされ、ステップＳ３４により頂点が生成しないとされたときには前回の値のまま変わらない。
【０２６０】
ステップＳ２２で、線分がその階層の最終線分を越えているときには、ステップＳ４３へ動作が移る。ステップＳ４３では、「温度列データ」内のすべての温度パラメタが０になったときに線分近似の終了を判定する。このとき、ステップＳ３４で結果を出力した後、動作を終了する。
【０２６１】
ステップＳ４３で、未だ「温度列データ」内に０以外の温度パラメタがあると判定されたときには、ステップＳ４５を通ってステップＳ２へ戻り、再度「頂点列データ」の始めから、連続する２頂点で表される線分に関しての処理を繰り返して行う。
【０２６２】
本実施の形態では、線分から部分点列の各点までの距離を最大距離を代表としてとることがなく、また、温度のアニーリングは「揺らぎ」により頂点を発生したときのみ行うため、第１の実施の形態よりも誤動作を防ぐ意味での精度がさらに向上し、効果的なアニーリングを与えることができる。
【０２６３】
（第３の実施の形態）
本実施の形態を実現するためのハードウェア構成は、前記第１の実施の形態と同様に、図１のようなハードウェア構成を採ることができ、その詳細は、前記第１の実施の形態で詳しく述べているため、ここでは省略する。
【０２６４】
本実施の形態のＰＣ０は、以下のような演算手順により線分近似を実行する。
【０２６５】
２次元整数格子内の一意的に１次元鎖と見なし得る、連結したＮ個の座標点列Ａ＝[(ｘ[ｉ],ｙ[ｉ])|ｉ＝１,…,Ｎ]が、初期入力データとして図１の構成内の演算処理装置１の中間データ記憶部１ｃに格納されているものとする。初期入力データは、前述のように、入力デバイス２より読み込まれ、入力部１ｄを介して、中間データ記憶部１ｃに格納される。また、外部記憶装置５より中間データ記憶部１ｃに読み込まれるようにしてもよい。
【０２６６】
ここで、連結しているとは、従来例の説明において述べたように、図８のように座標点を微小面積要素と見なして、その領域が点あるいは線で連結していることを意味する。このようなパターンは、鉛筆等で書かれた曲線をデジタル化したときに現れる。
【０２６７】
また、簡単のため、点列は開いた曲線に対応しており、点列には曲線の連結性に沿って、順番がついているとし、所謂、細線化された曲線とし、図９（ａ）のひげ、同図（ｂ）の解像度以上の折れ曲がり、同図（ｃ）の二重線、同図（ｄ）の交差点はないと仮定する。
【０２６８】
近似すべき元図形は、上述のように、デジタル化された点（ピクセル）の座標値の形で格納され、１組の座標値データ列をなしている。このデータ列は、中間データ記憶部１ｃに格納される。これを「点座標列データ」と云うことにする。いま、このデータ列の数をＮとする。このデータ列上の座標値を計算機上で扱うために、各座標値に対して計算機上で判別できる値を付与する。例えば、これは座標値列上での順番に従って付けられた番号でよい。この番号値は、元図形上で上記のようにデジタル化された点の名称であり、対応する座標値を参照できるようにした上で計算機上でこの点を表すものとして使用される。これを、以降「点データ」と称する。
【０２６９】
例えば、本実施の形態による演算手順を高級言語プログラムで表現した場合、「点座標列データ」は、配列型の変数として表現でき、「点データ」は、配列番号として表現できる。また、例えば、演算手順を演算コードとして表現した場合、「点データ」は、「点座標列データ」のおのおのを格納した、中間データ記憶部１ｃを構成するメモリ装置の番地として表現できる。このようにすれば、元図形の点の並びは「点データ」の並び、あるいは「点座標列データ」によって表現できる。この元図形を表す「点データ」の並び、あるいは「点座標列データ」を「点列データ」と云うことにする。「点列データ」は、「点データ」またはその座標値を単位とするデータ値の列である。計算機上で「点データ」からその座標値を知ることができるため、以下の説明ではこの両者を同一視して説明する。
【０２７０】
本実施の形態では、これら元図形を構成する点列の各点について、頂点となるか否かにより状態が決まり、点列全体の状態を変化させながら、これによって得られる評価関数の最小化を行っていく。この点列の状態を計算機上で表すには、例えば以下のようにすればよい。
【０２７１】
近似線分は、その頂点を指定することで表せるので、頂点となる点の点データを順次格納した「頂点列データ」を用いて、図１の構成上に表現できる。この「頂点列データ」を格納する領域を、中間データ記憶部１ｃ上に用意する。
【０２７２】
さらに、本実施の形態では、線分列の各線分とその各線分を両端とする点列内の各点から当該線分までの距離の最大値の列「最大距離列データ」と、その最大値を与える点の点データ列「頂点候補点列データ」とを格納する領域を、中間データ記憶部１ｃ上に用意する。この「最大距離列データ」と「頂点候補点列データ」内の各値は、「頂点列データ」内の連続する２頂点間を結ぶ線分からの最大距離と、その最大距離を与える点データであり、例えば値の格納順などにより互いに対応が取れるようになっている。
【０２７３】
以下の表記では、線分近似のある階層で線分本数をｍ本とする。このとき、頂点はｍ＋１個で、その頂点列の「頂点列データ」をＱ0,Ｑ1,…,Ｑmと表す。ここで、Ｑiはｉ番目の頂点を表すか、またはｉ番目の頂点となる点の値（名称、点データ）を表す。特に、表式中などでは、後者の使い方をする。最初の頂点Ｑ0および最後の頂点Ｑmは、それぞれ元図形を構成する点列の始点および終点と一致する（またはその点の値をとる）とする。
【０２７４】
「頂点列データ」の順に従って、連続する２頂点間で決まる線分から、その２頂点を両端とする点列の各点までの距離の最大値を算出する。最初に格納された点列Ａ＝[(ｘ[ｉ],ｙ[ｉ])|ｉ＝１,…,Ｎ]の順に従って、Ｑ0の点データの次の点からＱ1の点データの１つ前の点まで、各々の座標値データを基に、線分Ｑ0Ｑ1までの距離を計算する。
【０２７５】
「頂点データ列」のｉ番目の頂点の点データＱiとｉ＋１番目の頂点の点データＱi+1とで決まる線分と、この２頂点を両端とする点列内の１点の点データＰとの距離は、前記式（２）で算出できる。
【０２７６】
「頂点データ列」のうちｉ番目の頂点の点データＱiとｉ＋１番目の頂点の点データＱi+1との間にある（但しＱi、Ｑi+1を含まず）各点データについて、順次上記距離を算出して行き、その最大値を「最大距離列データ」、その距離を与える点データを「頂点候補点列データ」のｉ番目の位置とする。ｉ番目の頂点の点データＱiとｉ＋１番目の頂点の点データＱi+1との間にあるすべての点データについて計算後、ｉ＋１番目の頂点の点データＱi+1とｉ＋２番目の頂点の点データＱi+2との間にある（但し、Ｑi+1 、Ｑi+2を含まず）各点データについて、同様の処理を行う。これを「頂点データ列」の最後の頂点に達するまで行う。
【０２７７】
次に、今格納された「最大距離列データ」の各値を、最初から順次閾値vtxth0と比較し、最大距離の値が閾値vtxth0より大きいときに、対応する「頂点候補点列データ」内の点データを「頂点データ列」の対応する位置に挿入する。例えば、中間データ記憶部１ｃに仮格納領域を確保し、「最大距離列データ」、「頂点候補点列データ」および「頂点データ列」それぞれを列データの順に従って、順次読み込んで行く。このとき、最大距離が閾値vtxth0より小さいときには、そのままの順番で頂点データを仮格納領域に格納して行く。最大距離が閾値vtxth0より大きいときには、現在読み込んだ頂点候補点列データの点データを挟む頂点データを仮格納領域に格納していく。最終頂点までの処理終了後、仮格納領域には、閾値vtxth0より大きい最大距離を持つ新たな頂点を対応する位置に加えた、新たな「頂点列データ」が生成される。これを「頂点データ列」として、中間データ記憶部１ｃに格納し直せばよい。
【０２７８】
このとき、「頂点列データ」のデータの個数が増加していれば、後述の「揺らぎ」パラメタＴを初期値Ｔ0に戻して次の階層へ処理を進める。
【０２７９】
「頂点列データ」のデータの個数が変化しなければ、閾値vtxth0を越える最大距離が検出されなかったものとして、「揺らぎ」を発生して、新たな頂点を検出する動作に入る。
【０２８０】
なお、この判定は、閾値vtxth0を越える最大距離が検出されるか否かの判定であるから、上記「最大距離列データ」と閾値vtxth0の比較を行う動作中に、閾値vtxth0を越える最大距離が検出された場合に、フラグを立てる等の判別動作を設けることで行うこともできる。
【０２８１】
始めに、「最大距離データ」内の最大値ｄを検出する。これは、上記「最大距離列データ」と閾値vtxth0の比較を行う動作中に併せて行ってもよい。このとき同時に、この最大値ｄを与える「頂点候補点列データ」内の点データと、この頂点候補が挟まれる２頂点を「頂点列データ」内から検出し、後に、この間に新たな頂点となる点データを挿入できるようにしておく。この最大距離の最大値ｄを与える、「頂点候補点列データ」内の点データの検出は、例えば「最大距離列データ」内の最大値ｄを検出すると同時に、順次「最大距離列データ」と「頂点候補点列データ」を同時に読み込みながら最大の値を検出した時点で読み込んだ頂点候補点データを検出すればよい。また、頂点候補が挟まれる２頂点の検出は、例えばこの時検出された「最大距離列データ」内の最大値ｄの「最大距離列データ」内での順番を基に、対応する「頂点列データ」での挿入候補位置の順番を記憶しておき、後述の判定により新たな頂点が発生する際に、この位置に発生する頂点の点データを挿入する。
【０２８２】
このような「最大距離列データ」、「頂点候補点列データ」および「頂点列データ」の順番の対応付けは、単純にこれらのデータ列を中間データ記憶部１ｃに格納した論理的、物理的格納順の順番を利用してもよく、あるいは中間データ記憶部１ｃでの格納アドレスなどを利用してもよい。
【０２８３】
この値ｄと「揺らぎ」の大きさを表すパラメタＴを用いて、判定用の関数Ｄ(ｄ,Ｔ)の値を算出する。
【０２８４】
関数Ｄ(ｄ,Ｔ)は、以下で発生する乱数に対応して、０から１までの値をとる関数であり、「揺らぎ」の大きさを表すパラメタＴの値がある値、例えば０を取るときに、０から閾値vtxth0までのｄの値に対して、０を与えるものであり、ｄを固定したときに、Ｔの減少に関しては非増加の関数となっている。このＴは、その値が大きいときに「揺らぎ」が大きくなるようにとり、その最小値は、一般には何でもかまわず、後述のアニーリング動作でＴを減少していく際に変動させるＴの最終値であればよいが、ここでは説明の簡便のために０とする。基本的には、本実施の形態では、アニーリング時に「揺らぎ」を単調（非増加）に小さくしていく動作であり、固定したｄの値に対して、関数Ｄ(ｄ,Ｔ)が単調（非増加）に小さくなり、最終的には、発生する乱数Ｒの最小値以下となるように、パラメタをＴを変化させる。また、Ｄ(ｄ,Ｔ)の取り得る値は、発生する乱数Ｒに対応した値であればよい。
【０２８５】
また、Ｔを固定したときに、関数Ｄ(ｄ,Ｔ)は、ｄの関数として単調増加（非減少）関数であり、距離ｄが大きくなるに従って、発生する乱数Ｒに対して大きくなる確率が高いものになるとする。
【０２８６】
特に、本発明に好適には、判定する元図形の分解限界であるピクセルサイズｄ0として非０のＴのときに ｄ ＞ ｄ0  でＤ(ｄ,Ｔ)が有限の値をもつものである。
【０２８７】
このようなＤ(ｄ,Ｔ)として、前記式（３）のような関数を計算すればよい。
【０２８８】
例えば、図３に示すような関数を取ることができる。図３中、横軸は距離ｄを表し、縦軸はＤを表し、Ｔ ＝ ０，Ｔ1，Ｔ2，Ｔ3（但しＴ1 ＜ Ｔ2 ＜ Ｔ3）の値に対するＤとｄの関係を示す。Ｔ＝０では、ｄが０より大きく、vtxth0より小さい範囲で、Ｄは“０”であり、ＴがＴ1，Ｔ2，Ｔ3と大きくなるにつれてＤの値が非減少に変化する。この関数Ｄの値がランダムに発生したＲの値より小さいときに、新たな頂点を作成する。
【０２８９】
この関数を計算によって算出するのではなく、ｄ，Ｔの値とＤ(ｄ,Ｔ)の値の関係をテーブルに記載したものを用いてもよい。このテーブルは、外部記憶装置５あるいは中間データ記憶部１ｃに格納されており、必要に応じてテーブルの該当部分を参照することで、Ｄ(ｄ,Ｔ)の値を得ることができる。一般に記憶領域の参照は、前記式（３）の数値計算より早く実行されるので、このような構成では実行速度を速くすることができる。また、この関数をｄの区間を定めた線形関係、あるいはｄ，Ｔについての多項式で近似して表現してもよい。
【０２９０】
このＤ(ｄ,Ｔ)の値に対して、０から１までの乱数を発生して、Ｒ ＞ Ｄ(ｄ,Ｔ)のときには新たな頂点を発生すると判定する。
【０２９１】
「最大距離列データ」内でのこの最大の値ｄの順番に対応する、「頂点候補点列データ」内の点データを、「頂点列データ」の対応部分に挿入して新たな「頂点列データ」を作成し、中間データ記憶部１ｃに格納し直す。
【０２９２】
同時に、「揺らぎ」パラメタＴを、例えば前記式（４）のようにして、より小さな値に変更する。
【０２９３】
本実施の形態の線分近似では、一般のシミュレーテッドアニーリング法のように、通常評価関数を順次減少させて行く最適化方法になっていないため、一度「揺らぎ」を生じせしめた場合、評価関数は大きく変化してしまい、トラップの原因を大きくはずれる。そのため、一般のシミュレーテッドアニーリング法に比べ、アニールにおける「揺らぎ」の大きさの減少具合を大きくとることができ、アニーリングの規定回数ｎは１〜１０回程度で十分に動作を行うことができる。特に、処理の速度を向上させたいときには、ｎを１〜２に、精度を向上させたいときには、ｎを８〜１０に採ることが望ましい。
【０２９４】
「揺らぎ」パラメタＴの減少は、所定の回数ｎでＴを０にするような単調な減少であればどのようなものでもよく、特に、線分近似を行う元図形の傾向がある程度決まっているときには、その元図形の特徴に応じて、前記式（４）以外の解析式によって算出したり、減少率を細かく規定したテーブルを中間データ記憶部１ｃに格納してもよいが、前記式（４）による算出は計算処理も少なく、中間データ記憶部１ｃに余分な記憶領域を設ける必要もないため、一般の線分近似に対しては望ましい。
【０２９５】
このような判定により、「揺らぎ」により新たな頂点が発生すると判定された場合には、新たな「頂点列データ」を格納し、「揺らぎ」パラメタを小さくした後、次の階層へ線分近似を進める。
【０２９６】
このようにして、ある階層で各線分についての最大距離が閾値vtxth0より小さいときには、「揺らぎ」発生により頂点発生の判定を行い、これが連続する階層で行われるときには「揺らぎ」を順次小さくして行く。これが、アニーリングの規定回数ｎに対して、連続したｎ＋１階層に亘ったときには、「揺らぎ」パラメタＴ＝０で「揺らぎ」なしとの判定となる。
【０２９７】
判定により、「揺らぎ」により新たな頂点が発生しないと判定された場合、「揺らぎ」による判定がアニーリングの規定回数ｎに対して連続したｎ＋１階層に亘りＴ＝０となっているときには、線分近似の動作を終了し、その時点で中間データ記憶部１ｃに格納されている「頂点列データ」を線分近似の結果の頂点列として出力する。一方、Ｔ＝０に達していないときには、新たな頂点を作成することなしに、次の階層へ近似を進める。
【０２９８】
このようにして、本実施の形態では、連続した「揺らぎ」発生による頂点の生成判定がアニーリングの規定回数ｎに対して連続したｎ＋１階層まで達したとき、規定精度までの近似精度が得られたとして線分近似動作を終了する。
【０２９９】
次に、図６に従って、本実施の形態の線分近似の動作を説明する。
【０３００】
ステップＳ５１は、初期化動作であり、中間データ記憶部１ｃの各領域にある諸値をクリアする。次に、初期の「揺らぎ」の大きさＴ0、並びにアニーリングの規定回数ｎを設定し、点列各点の初期状態を設定する。初期の「揺らぎ」の大きさＴ0、並びにアニーリングの規定回数ｎの値は、初期データとして入力デバイス２より与えられるか、その他の操作により中間データ記憶部１ｃに格納される。元図形の点列は、前述のように、「点列データ」として中間データ記憶部１ｃ等に格納されているとする。また、「頂点列データ」の初期値として、元図形を構成する点列の始点と終点の２点「点データ」からなるデータを中間データ記憶部１ｃに格納しておく。
【０３０１】
ステップＳ５２からステップＳ５５までは、ある階層にある線分列の各線分について線分近似の動作を行う。具体的には、線分列を表す「頂点列データ」内の連続する２頂点を指定することで線分が指定されるので、「頂点列データ」より順次、連続する２頂点を読み込んで行く。ステップＳ５２では、線分がその階層の最終線分を超えたかどうかを判定し、最終線分を超えていないときにはステップＳ５３へ、最終線分を超えたときにはステップＳ５７以降の動作へ進む。
【０３０２】
ステップＳ５３では、その線分の両端の２頂点で挟まれた点列の「点列データ」より、順次点データを読み込んで、両端の２頂点の点データと点列の点データより、前記式（２）を用いて点列の点から線分までの距離を求め、その最大距離と最大距離を与える点を各々「最大距離列データ」および「頂点候補点列データ」として保持する。
【０３０３】
ステップＳ５４では、最大距離が閾値vtxth0を越えるかどうかを判定し、越えないときにはステップＳ５６を通ってステップＳ５２へ戻り、次の線分へ動作を進める。一方、最大距離が閾値vtxth0を越えるときにはステップＳ５５へ進む。
【０３０４】
ステップＳ５５では、その線分に対し、ステップＳ５３で求めた最大距離を与える点を新たな頂点として線分分割を行う。線分を指定している２頂点の点データの間に、最大距離を与える点の点データを挟んで、新たな「頂点列データ」を作成して、格納し直す。
【０３０５】
ステップＳ５２〜ステップＳ５５の処理をその階層の最終線分まで繰り返す。
【０３０６】
その階層の最終線分まで処理が到達すると、ステップＳ５７で、線分の本数が増加したかどうかを判定する。増加していない場合には、この階層の判定で、閾値vtxth0を越える新たな頂点が見つからなかったとして、ステップＳ５８以降の「揺らぎ」を発生した頂点の判定に進む。ステップＳ５５までで新たな頂点が発生していれば、ステップＳ６６で「揺らぎ」パラメタＴの大きさを初期値Ｔ0へ戻し、ステップＳ６７で次の階層へ処理を進める。
【０３０７】
ステップＳ５８では、ステップＳ５３で作成した「最大距離列データ」および「頂点候補点列データ」を用いて最大距離の最大値ｄを求め、ステップＳ５９へ進む。
【０３０８】
ステップＳ５９では、このｄと「揺らぎ」パラメタの大きさＴを基に、前記式（３）や中間データ記憶部１ｃに格納されたテーブル等を用いて「揺らぎ」の判定量Ｄ(ｄ,Ｔ)を求める。
【０３０９】
ステップＳ６０では、０から１までの乱数Ｒを発生し、「揺らぎ」による判定ステップＳ６１へ進む。
【０３１０】
ステップＳ６１では、ステップＳ５９で求めた判定量Ｄ(ｄ,Ｔ)とステップＳ６０で求めた乱数Ｒを用いて「揺らぎ」による判定を行う。Ｒ＞Ｄ(ｄ,Ｔ)のときには、揺らぎにより新たな頂点が発生するとして、ステップＳ６２へ進む一方、そうでないときには、ステップＳ６３へ進む。
【０３１１】
ステップＳ６１で、Ｒ＞Ｄ(ｄ,Ｔ)のときには、ステップＳ６２で新たな頂点を発生する。「最大距離列データ」内の最大距離の最大値ｄに対応する、「頂点候補点列データ」内の頂点を対応する位置に挟んだ、新たな「頂点列データ」を作成し、中間データ記憶部１ｃに格納する。その後、ステップＳ６３へ進む。
【０３１２】
ステップＳ６３では、「揺らぎ」パラメタＴの大きさを、例えば前記式（４）に従って、より小さな値に置き換え、終了判定ステップＳ６４へ進む。
【０３１３】
ステップＳ６４では、現在の「揺らぎ」パラメタＴが０になっているかどうかを判定し、Ｔが０になっていれば、「揺らぎ」のアニーリングが終了しているとして、結果出力ステップＳ６５へ進む。一方、Ｔが０になっていなければ、未だアニーリングが終了してないとして、ステップＳ６７に進み、次の階層へ処理を進める。
【０３１４】
ステップＳ６５では、中間データ記憶部１ｃに格納された「頂点列データ」を線分近似の結果の線分列を表すものとして出力する。
【０３１５】
その後、処理終了へ動作が移り、所定の終了処理を行って処理を終了する。
【０３１６】
（第４の実施の形態）
本発明の第４の実施の形態では、「揺らぎ」のアニーリング動作において、上記第３の実施の形態と異なる動作を行う。より詳しくは、「揺らぎ」を用いた頂点の判定時にＲ＞Ｄ(ｄ,Ｔ)とならずに頂点の生成を行わないとしたときに対する「揺らぎ」パラメタＴの変更に関して、第３の実施の形態と異なる動作を行う。
【０３１７】
第３の実施の形態では、階層において各線分についての点列からの最大距離が閾値vtxth0より小さい状態が続く限り、「揺らぎ」によって新たな頂点が生成するか否かに拘わらず、「揺らぎ」パラメタＴを小さくするアニーリングを行っている。
【０３１８】
ところで、線分近似の動作を進め、近似線分の本数が増加するに従って、元図形の点列は近似線分に全体的に近づいて行くために、図１２のような誤動作を生じる確率が減少してくる。そのため、新たな頂点を検出する「揺らぎ」を小さくできる。このように、効果的な「揺らぎ」のアニーリングとしては、階層が増加し、かつ頂点が増えた場合に、「揺らぎ」パラメタＴを小さくとることが好ましい。
【０３１９】
本実施の形態では、階層において各線分についての点列からの最大距離が閾値vtxth0より小さい状態が続くときに、「揺らぎ」によって新たな頂点が生成した場合、「揺らぎ」パラメタＴを小さくし、頂点を生成しないときには、「揺らぎ」パラメタＴの値を変化させない。一方、各線分についての点列からの最大距離が閾値vtxth0を越えた場合には、新たな頂点を作成し、「揺らぎ」パラメタＴの値を初期値Ｔ0に戻す。そして、Ｔが０に達するか、Ｔ0以外の値で連続して指定回数以上の動作を行った場合に、動作を終了する。
【０３２０】
このように構成することで、頂点が増加しない限りは「揺らぎ」の大きさが変化せず、同じ確率で、線分より距離が離れた点を新たな頂点候補として検出できるため、図１２のような誤動作を防ぐ意味での精度が向上し、この意味で効果的なアニーリングを与えることができる。
【０３２１】
さらに、線分についての点列からの最大距離が閾値vtxth0より大きく、新たな頂点を生成する度に、アニールの指定回数を小さく設定するとともに、「揺らぎ」パラメタＴのアニール初期値Ｔ0を小さく設定することで、線分近似の近似線分数が多くなるにつれて、「揺らぎ」のアニールの収束を速くして行くことができ、実行速度の速い、効果的なアニールができる。
【０３２２】
本実施の形態を実現するためのハードウェア構成は、前記第１の実施の形態と同様に、図１のようなハードウェア構成を採ることができ、その詳細は、前記第１の実施の形態で詳しく述べているため、ここでは省略する。
【０３２３】
次に、図７に従って、本実施の形態の線分近似の動作を説明する。
【０３２４】
ステップＳ７１は、初期化動作であり、中間データ記憶部１ｃの各領域にある諸値をクリアする。次に、当初のアニーリング初期「揺らぎ」Ｔ0、並びに当初のアニーリングの規定回数ｎを設定し、点列各点の初期状態を設定する。アニーリング初期「揺らぎ」Ｔ0、並びにアニーリングの規定回数ｎは、中間データ記憶部１ｃに格納領域を持つが、その当初の値は初期データとして入力デバイス２より与えられるか、その他の操作により中間データ記憶部１ｃに格納される。元図形の点列は、前述のように、「点列データ」として中間データ記憶部１ｃ等に格納されているとする。また、「頂点列データ」の初期値として、元図形を構成する点列の始点と終点の２点「点データ」からなるデータを中間データ記憶部１ｃに格納しておく。
【０３２５】
ステップＳ７２は、アニール条件を設定する処理であり、アニール初期「揺らぎ」Ｔ0およびアニーリング規定回数ｎを設定する。アニール初期「揺らぎ」Ｔ0およびアニーリング規定回数ｎは、後述するように、線分についての点列からの最大距離が閾値vtxth0より大きくなり、新たな頂点を生成した場合には、その値を減少するようにする。後述のステップＳ８８より帰還する度に、アニールの「揺らぎ」Ｔ0または／並びにアニーリング規定回数ｎを減じて行き、最終値のアニール初期「揺らぎ」Ｔ0-end、アニーリング規定回数ｎendとなるまで減少させる。それ以降は、この値をアニール初期「揺らぎ」Ｔ0およびアニーリング規定回数ｎとする。
【０３２６】
ステップＳ７３よりステップＳ７６までは、ある階層にある線分列の各線分について線分近似の動作を行う。具体的には、「頂点列データ」内の連続する２頂点を指定することで、線分が指定されるので、「頂点列データ」より順次、連続する２頂点を読み込んで行く。ステップＳ７３では、線分がその階層の最終線分を越えたかどうかを判定し、最終線分を越えていないときはステップＳ７４へ、最終線分を越えたときにはステップＳ７８以降の動作へ進む。
【０３２７】
ステップＳ７４では、その線分の両端の２頂点で挟まれた点列の「点列データ」より、順次点データを読み込んで、両端の２頂点の点データと点列の点データより、前記式（２）を用いて点列の点から線分までの距離を求め、その最大距離と最大距離を与える点を各々「最大距離列データ」および「頂点候補点列データ」として保持する。
【０３２８】
ステップＳ７５では、最大距離が閾値vtxth0を越えるかどうかを判定し、越えないときには、ステップＳ７７を通ってステップＳ７３へ戻り、次の線分へ動作を進める。一方、最大距離が閾値vtxth0を越えるときにはステップＳ７６へ進む。
【０３２９】
ステップＳ７６では、その線分に対し、ステップＳ７４で求めた最大距離を与える点を新たな頂点として線分分割を行う。線分を指定している２頂点の点データの間に、最大距離を与える点の点データを挟んで、新たな「頂点列データ」を作成して、格納し直す。
【０３３０】
ステップＳ７３〜ステップＳ７６の処理をその階層の最終線分まで繰り返す。
【０３３１】
その階層の最終線分まで処理が到達すると、ステップＳ７８で、線分の本数が増加したかどうかを判定する。増加していない場合には、この階層の判定で、閾値vtxth0を越える新たな頂点が見つからなかったとして、ステップＳ７９以降の「揺らぎ」を発生した頂点の判定に進む。ステップＳ７６までで新たな頂点が発生していれば、ステップＳ８７で「揺らぎ」の大きさをアニーリング初期値Ｔ0へ戻し、ステップＳ８８で次の階層へ処理を進める。この後、ステップＳ７２では、前述のような「揺らぎ」の大きさの初期値Ｔ0を減少させながら動作を繰り返す。
【０３３２】
ステップＳ７９では、ステップＳ７４で作成した「最大距離列データ」および「頂点候補点列データ」を用いて最大距離の最大値ｄを求め、ステップＳ８０へ進む。
【０３３３】
ステップＳ８０では、このｄと「揺らぎ」の大きさＴを基に、前記式（３）や中間データ記憶部１ｃに格納されたテーブル等を用いて「揺らぎ」の判定量Ｄ(ｄ,Ｔ)を求める。
【０３３４】
ステップＳ８１では、０から１までの乱数Ｒを発生し、「揺らぎ」による判定ステップＳ８２へ進む。
【０３３５】
ステップＳ８２では、ステップＳ８０で求めた判定量Ｄ(ｄ,Ｔ)とステップＳ８１で求めた乱数Ｒを用いて「揺らぎ」による判定を行う。Ｒ ＞ Ｄ(ｄ,Ｔ)のときには、揺らぎにより新たな頂点が発生するとして、ステップＳ８３へ進む一方、そうでないときには、「揺らぎ」の大きさＴを変更せずに、ステップＳ８５へ進む。
【０３３６】
ステップＳ８２で、Ｒ ＞ Ｄ(ｄ,Ｔ)のときには、ステップＳ８３で新たな頂点を発生する。「最大距離列データ」内の最大距離の最大値ｄに対応する、「頂点候補点列データ」内の頂点を対応する位置に挟んだ、新たな「頂点列データ」を作成し、中間データ記憶部１ｃに格納する。その後、ステップＳ８４へ進む。
【０３３７】
ステップＳ８４では、「揺らぎ」の大きさを、例えば前記式（４）に従って、より小さな値に置き換え、終了判定ステップＳ８５へ進む。
【０３３８】
ステップＳ８５では、アニール終了の判定を行う。終了の判定は、現在のＴが０になったか、あるいはアニール回数が規定回数ｎに達したかどうかを判定する。アニールが終了していると判定されれば、結果出力ステップＳ８６へ進む。そうでないときには、ステップＳ８９でＴの値を変動させずに、ステップＳ７３に戻り、ステップＳ７３以降の動作を繰り返す。
【０３３９】
これにより、各点列から線分への最大距離が閾値vtxth0を越えずに、「揺らぎ」による新たな頂点探索を続けるときにも、新たな頂点が作成されない限り「揺らぎ」の大きさＴを変更することなしに動作を繰り返すこととなる。
【０３４０】
アニール終了が判定されれば、ステップＳ８６で、中間データ記憶部１ｃに格納された「頂点列データ」を線分近似の結果の線分列の表すものとして出力する。
【０３４１】
本実施の形態では、階層において各線分についての点列からの最大距離が閾値vtxth0より小さい状態が続くときに、「揺らぎ」によって新たな頂点が生成されると、「揺らぎ」パラメタＴを小さくし、頂点が生成されないと、Ｔの値を変化させない。また、各線分についての点列からの最大距離が閾値vtxth0を越えた場合には、新たな頂点を作成し、Ｔの値を初期値Ｔ0に戻す。そして、Ｔが０に達するか、Ｔ0以外の値で連続して指定回数以上の動作を行った場合に動作を終了することで、線分近似の動作を進め、近似線分の本数が増加するに従って、「揺らぎ」の大きさを小さくして行く、効果的なアニーリングを行うことができる。
【０３４２】
なお、上述した各実施の形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムまたは装置に供給し、そのシステムまたは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても、本発明の目的が達成されることは言うまでもない。
【０３４３】
この場合、記憶媒体から読出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【０３４４】
プログラムコードを供給するための記憶媒体としては、たとえば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。また、通信ネットワークを介してサーバコンピュータからプログラムコードが供給されるようにしてもよい。
【０３４５】
また、コンピュータが読出したプログラムコードを実行することにより、上述した各実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳなどが実際の処理の一部または全部を行い、その処理によって上述した各実施の形態の機能が実現される場合も含まれることは言うまでもない。
【０３４６】
さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって上述した各実施の形態の機能が実現される場合も含まれることは言うまでもない。
【０３４７】
【発明の効果】
以上説明したように、本発明によれば、線分近似動作のなかで「揺らぎ」を発生させ、この「揺らぎ」に応じて近似線分を追加するようにしたので、線分近似を行うときに用いる評価値が偶発的に動作の閾値を下回った場合にも、動作を停止することなく安定に動作させることができる。
【０３４８】
また、本発明によれば、「揺らぎ」のアニーリング動作を線分近似の頂点を探索する過程に組み込むようにしたので、実行効率の良い、安定な線分近似を行うことができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態に係る図形の線分近似方法を実現するためのパーソナルコンピュータの概略構成を示すブロック図である。
【図２】本発明の第１の実施の形態の図形の線分近似方法を適用して線分近似を行う元図形の一例を示す図である。
【図３】本発明の第１の実施の形態の図形の線分近似方法で用いる評価関数の具体例を示す図である。
【図４】本発明の第１の実施の形態の図形の線分近似方法の手順を示すフローチャートである。
【図５】本発明の第２の実施の形態の図形の線分近似方法の手順を示すフローチャートである。
【図６】本発明の第３の実施の形態の図形の線分近似方法の手順を示すフローチャートである。
【図７】本発明の第４の実施の形態の図形の線分近似方法の手順を示すフローチャートである。
【図８】本発明で前提とするドット列の一例を示す図である。
【図９】本発明で前提としないドット列の一例を示す図である。
【図１０】従来の線分近似処理を説明するための図である。
【図１１】従来の線分近似処理の手順を示すフローチャートである。
【図１２】線分近似すべき線図の一例およびこの線図に従来の線分近似処理を適用して得られる線分近似結果を示す図である。
【符号の説明】
０  パーソナルコンピュータ
１  演算処理装置
１ａ  演算部
１ｂ  演算手順記憶部
１ｃ  中間データ記憶部
１ｄ  入力部
１ｅ  出力部
１ｆ  バス部
２  入力デバイス
３  出力デバイス
４  表示器
５  外部記憶装置
【図１】
0004164286.tif 000006
【図２】
0004164286.tif 000007
【図３】
0004164286.tif 000008
【図４】
0004164286.tif 000009
【図５】
0004164286.tif 000010
【図６】
0004164286.tif 000011
【図７】
0004164286.tif 000012
【図８】
0004164286.tif 000013
【図９】
0004164286.tif 000014
【図１０】
0004164286.tif 000015
【図１１】
0004164286.tif 000016
【図１２】
0004164286.tif 000017