(57)【要約】    【課題】  ２次元格子点列からなる曲線を、アファイン変換に対して近似的に不変な図形の同一性判定により分類することが可能な曲線の分類方法、該分類方法を実現するためのプログラムおよび曲線分類装置を提供する。    【解決手段】  初期化（ステップＳ１）後、ドットデータから区分的線分データ化を行い（ステップＳ２）、この区分的線分を、端から弧長に沿って等分割し（ステップＳ３）、接角分布の計算を行う（ステップＳ４）。次に、計算された接角分布に対して離散フーリエ変換を行い（ステップＳ５）、この離散フーリエ変換後のデータの内、必要でないものを除く処理、すなわちフィルタ処理を施し（ステップＳ６）、フーリエ変換後のデータのパターンマッチを行う（ステップＳ７）。ここで、パターンマッチは、基準パターンのフーリエ変換データと対象となるフーリエ変換データとを比較することによって行い、このパターンマッチの結果に基づいて、ドットデータで表された曲線の分類を行う（ステップＳ８）。【選択図】    図５
2005189929.tif 000002
【特許請求の範囲】
【請求項１】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法において、
前記曲線に沿った弧長を等間隔に有限個に等分し、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、
該接角の離散フーリエ成分を算出し、
該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とする曲線の分類方法。
【請求項２】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法において、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、
該接角の離散フーリエ成分を算出し、
該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とする曲線の分類方法。
【請求項３】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法において、
前記曲線に沿った弧長を等間隔に有限個に等分し、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、
隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とし、
該離散曲率分布の離散フーリエ成分を算出し、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とする曲線の分類方法。
【請求項４】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法において、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、
隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とし、
該離散曲率分布の離散フーリエ成分を算出し、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とする曲線の分類方法。
【請求項５】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法において、
前記曲線に沿った弧長を等間隔に有限個に等分し、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、
隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とし、
該離散曲率分布の離散フーリエ成分を算出し、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とする曲線の分類方法。
【請求項６】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法において、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、
隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とし、
該離散曲率分布の離散フーリエ成分を算出し、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とする曲線の分類方法。
【請求項７】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法において、
前記曲線に沿った弧長を等間隔に有限個に等分し、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、
前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正し、
該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行う
ことを特徴とする曲線の分類方法。
【請求項８】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法において、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、
前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正し、
該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行う
ことを特徴とする曲線の分類方法。
【請求項９】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、
前記曲線の分類方法は、
前記曲線に沿った弧長を等間隔に有限個に等分し、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、
該接角の離散フーリエ成分を算出し、
該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とするプログラム。
【請求項１０】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、
前記曲線の分類方法は、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、
該接角の離散フーリエ成分を算出し、
該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とするプログラム。
【請求項１１】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、
前記曲線の分類方法は、
前記曲線に沿った弧長を等間隔に有限個に等分し、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、
隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とし、
該離散曲率分布の離散フーリエ成分を算出し、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とするプログラム。
【請求項１２】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、
前記曲線の分類方法は、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、
隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とし、
該離散曲率分布の離散フーリエ成分を算出し、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とするプログラム。
【請求項１３】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、
前記曲線の分類方法は、
前記曲線に沿った弧長を等間隔に有限個に等分し、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、
隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とし、
該離散曲率分布の離散フーリエ成分を算出し、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とするプログラム。
【請求項１４】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、
前記曲線の分類方法は、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、
隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とし、
該離散曲率分布の離散フーリエ成分を算出し、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う
ことを特徴とするプログラム。
【請求項１５】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、
前記曲線の分類方法は、
前記曲線に沿った弧長を等間隔に有限個に等分し、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、
前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正し、
該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行う
ことを特徴とするプログラム。
【請求項１６】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、
前記曲線の分類方法は、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、
前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正し、
該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行う
ことを特徴とするプログラム。
【請求項１７】
請求項９〜１６のいずれかのプログラムを格納したことを特徴とする記憶媒体。
【請求項１８】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類装置において、
前記曲線に沿った弧長を等間隔に有限個に等分する等分手段と、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現する表現手段と、
該接角の離散フーリエ成分を算出する算出手段と、
該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段と
を有することを特徴とする曲線の分類装置。
【請求項１９】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類装置において、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換する変換手段と、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分する等分手段と、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現する表現手段と、
該接角の離散フーリエ成分を算出する算出手段と、
該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段と
を有することを特徴とする曲線の分類装置。
【請求項２０】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類装置において、
前記曲線に沿った弧長を等間隔に有限個に等分する等分手段と、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現する表現手段と、
隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とする第１の算出手段と、
該算出された離散曲率分布の離散フーリエ成分を算出する第２の算出手段と、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段と
を有することを特徴とする曲線の分類装置。
【請求項２１】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類装置において、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換する変換手段と、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分する等分手段と、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現する表現手段と、
隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とする第１の算出手段と、
該算出された離散曲率分布の離散フーリエ成分を算出する第２の算出手段と、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段と
を有することを特徴とする曲線の分類装置。
【請求項２２】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類装置において、
前記曲線に沿った弧長を等間隔に有限個に等分する等分手段と、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現する表現手段と、
隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とする第１の算出手段と、
該算出された離散曲率分布の離散フーリエ成分を算出する第２の算出手段と、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段と
を有することを特徴とする曲線の分類装置。
【請求項２３】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類装置において、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換する変換手段と、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分する等分手段と、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現する表現手段と、
隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とする第１の算出手段と、
該算出された離散曲率分布の離散フーリエ成分を算出する第２の算出手段と、
該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段と
を有することを特徴とする曲線の分類装置。
【請求項２４】
２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類装置において、
前記曲線に沿った弧長を等間隔に有限個に等分する等分手段と、
該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現する表現手段と、
前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正する補正手段と、
該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行う分類手段と
を有することを特徴とする曲線の分類装置。
【請求項２５】
２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類装置において、
前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換する変換手段と、
該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分する等分手段と、
該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現する表現手段と、
前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正する補正手段と、
該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行う分類手段と
を有することを特徴とする曲線の分類装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２次元格子点列からなる曲線を分類する曲線の分類方法、該曲線の分類方法を実現するためのプログラムおよび曲線の分類装置に関する。
【背景技術】
【０００２】
従来、曲線の形状を分類する曲線分類方法として、図形形状学習認識方式が知られている（例えば、特許文献１〜３参照）。
【０００３】
以下、この図形形状学習認識方式について説明する。
【０００４】
ドット列は、｛d[i]| i=1,…,N｝として与えられているとする。但し、d[i]は、整数値の２次元ベクトル量で、ドット列は、d[i]＝(x[i] ,y[i])の２次元格子座標列となっている。説明を簡単にするために、上記公報と同様にドット列は図１７のように閉じており、それに応じて、番号ｉも、Nを法（modulo）として与えられているものとする。したがって、d[ｉ法Ｎ]となっているとする。また、ドット列は、曲線の連結性に沿って、順番が付けられているものとし、すなわち所謂、細線化された曲線とし、図４（ａ）に示すようなひげ、同図（ｂ）に示すような解像度以上の折れ曲がり、同図（ｃ）に示すような二重線、同図（ｄ）に示すような交差点は、それぞれ存在しないと仮定する。
【０００５】
次に、上記各特許文献において「曲率」と呼んでいるものを定義する。特許文献２で明言しているように、当該発明者が呼んでいる「曲率」は数学的な意味の曲率ではない。（実際、この定義が図形の合同性の議論と矛盾するために、正しい情報を与え得ないことは、「発明が解決しようとする課題」欄において後述する。）よって、以下、これを「擬似曲率」と呼ぶことにする。
【０００６】
図１８は、この擬似曲率の定義を説明するための図である。
【０００７】
同図（ａ）において、画素d[i]に対して、（d[i-k],d[i+k]）のドット（２次元ベクトル）のペアを考える。（d[i-k],d[i+k]）で決まる線分に対して、d[i]から垂線を描き、その高さをＢ[k]と記す。また、（d[i-k],d[i+k]）で決まる線分の長さをL[i,k]と記す。kは、自然数１，２，３…を刻み、その度にＢ[k]の計算を行う。予め与えられたパラメータＥに対して、Ｂ[k]が値Ｅを越えない範囲で、最大のｋを探す。
【０００８】
このとき、擬似曲率を次のように２種類定義する。
【０００９】
１．第１擬似曲率（特開平５−１９７８１２号公報）：ベクトル（d[i+k],d[i]）とベクトル（d[i-k],d[i]）との角度θ[i]を第１擬似曲率とする（図１８（ｂ）参照）。また、各画素数ｉの分布関数としての｛（i,θ[i]）| i=1,…,N｝を第１擬似曲率関数と呼ぶ。
【００１０】
２．第２擬似曲率（特開平６−３０９４６５号公報および特開平７−３７０９５号公報）：曲線上の３点（d[i+k],d[i],d[i-k]）によって決まる円を決め、その円の半径をＲ[i]としたときに、1/Ｒ[i]を第２擬似曲率とする（図１８（ｃ）参照）。また、各画素数ｉの分布関数としての｛（i,1/Ｒ[i]）｜ i=1,…,N｝を第２擬似曲率関数と呼ぶ。
【００１１】
このように定義された２種類の擬似曲率は、以下に示すように、それぞれ、アファイン（合同）変換に対して近似的にも不変でなく、画素解像度をゼロに持ってゆく極限においても極限が存在しない場合が発生する。つまり、数学的に巧く定義（well-defined）されていない。
【００１２】
そのため、得られた図形は、アファイン変換等に対して近似的にも不変とならず、あいまいな量となっている。
【００１３】
上記各公報に記載された発明は、この数学的欠陥をニューラルネットを使って補う方法を提供している。
【００１４】
この方法のアルゴリズムを、図１９に従って説明する。
【００１５】
図１９において、まず、ステップＳ１０１では、初期化を行う。初期化は、例えば、曲線図形を細線化データとして、前記図４に示したようなパターンがないようにする。
【００１６】
次に、ステップＳ１０２では、曲線に対して、上記第１または第２擬似曲率を計算し、擬似曲率関数を算出する。
【００１７】
最後に、ステップＳ１０３では、得られた擬似曲率関数をニューラルネットを使って処理し、曲線を分類する。
【００１８】
後述するように、擬似曲率は数学的に不安定なものであり、そのために、ニューラルネット等の学習能力のある処理を行うようにしている。
【特許文献１】特開平５−１９７８１２号公報
【特許文献２】特開平６−３０９４６５号公報
【特許文献３】特開平７−３７０９５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１９】
曲線の分類において、曲線に微分幾何学的な操作が加えられるか否かの問題が生じる。つまり、曲線に長さとか曲率というものが存在するかという問題である。これらは、ある量の極限操作によって定義されるものであるが、極限操作が巧く働かない例として、図２０に示すコッホ曲線のようなフラクタル曲線が挙げられる（例えば、「フラクタル幾何学」Ｂ．マンデルボロ著、広中平祐監訳  １９８５年を参照）。
【００２０】
はじめに、このような極限操作を行えない曲線は除いて考察を始める。
【００２１】
フラクタル曲線のように、ワイルドな位相を持たない微分可能曲線に対する曲率は、フレネ・セレの関係式によって定義される（例えば、A Treatise on the Differential Geometry of Curves and Surfaces，L．P．Eisenhart 著 Ginn and Company 1909を参照）。図２１のように、曲線に対してその接角をφとし、２次元平面の自然な測度から決まる曲線の長さ（弧長）をｓとすると、次の関係式が定義できる。
【００２２】
【数１】
2005189929.tif 000003
【００２３】
ここで、κ＝dφ/dsは曲率であり、1/κは曲率半径と呼ばれるものである。この関係式をフレネ・セレの関係式と呼び、この関係式によって、曲線の局所的な性質が完全に決定されるというのが古典微分幾何学の教えるところである。
【００２４】
注意すべき点として、古典微分幾何学での曲線論における曲率κは、現代微分幾何学の用語に従えば、接続（コネクション）と呼ばれるものの一種で、曲率テンソルと呼ばれる内的な曲率とは無縁のものである（現代微分幾何学の用語は、例えば、Geometry Topology and Physics，M．Nakahara 著、Institute of Physics出版1990を参照）。そのため、座標によらない表示を採用すると、古典微分幾何学での曲率は、κ＝κdsとなる。これは、現代微分幾何学の用語でいう「一形式」の量である。
【００２５】
一形式（分布関数）と関数（スカラー関数）の関係は、良く知られているように、座標変換に対する変換性によって決定される。つまり、弧長ｓをｓに単調増加な関数ｇ(ｓ)に座標変換するとき、（スカラー）関数は、f(s)=f(g(s))となる一方、一形式（または分布関数）は、f(s)ds=f(g(s))(ds/dg)dgと変換される。ここで、(ds/dg)はヤコビアンを意味する。
【００２６】
したがって、曲率は、座標変換に対して、ヤコビアンを考慮しなければならない分布関数であり、弧長ｓをｓに単調増加な関数g(s)に座標変換する際には、曲率κ(s)は(κ(g(s))(ds/dg))に変換されなければ、数学的に有意義な結果が得られない。
【００２７】
ところが、上記各公報で定義された擬似曲率は、弧長から画素数への座標変換について、考慮していない。実際、線分を２次元画像データに変換する際に任意性を持っており、図２２（ａ）および（ｂ）に示すように、同一の線分を表現する際にドット数は線分の長さに対して一定ではない。つまり、ドット数は弧長の関数として見なすことができ、古典微分幾何学の曲率のような分布関数をドット数で表現する場合には、弧長からの座標変換として見なさなければならない。特に、２次元画像データには回転の自由度が一般になく、画素サイズ以下の平行移動の自由度がなくなっている。つまり、ドット数は、弧に沿った座標である弧長ｓについて変化する関数であり、一形式（分布関数）である曲率を表現する場合には、ヤコビアンによって、どのような、離散化した整数値の座標系を選んでいるかの情報を与えることが重要である。
【００２８】
しかしながら、上記各公報に記載の擬似曲率には、そのような考慮がなされていない。
【００２９】
次に、ワイルドなトポロジーを持つ曲線について考察する。
【００３０】
前述したように、曲率が定義されるためには、測度が巧く定義されなければならない。しかし、コッホ曲線のような曲線の場合には、曲線の長さと呼ばれるものすら巧く定義できないことがある。
【００３１】
一方、物理的に構成された図形においては、必ず、カットオフと呼ばれる（これ以上小さいものは意味をなさないという意味で）微小線分要素が存在する。
【００３２】
例えば、１）電子顕微鏡写真から得られた画像であれば、原子サイズであったり、２）光学的な解像度から決まるものであったり、３）図形を描く鉛筆の太さであったり、４）物理的要請から粗視化する際の微小量であったりする。
【００３３】
上記４）の場合としては、リアス式海岸のフラクタル的様相を、ある粗視化長によって粗視化し、地図として記述するような場合である。実際、リアス式海岸を地図に記すことは可能であるし、リアス式海岸に沿った有限の長さを持つ道路を作ることも可能である。これは、フラクタル曲線と呼ばれる、一般に測度が定義されないという対象に対しても、日常的な意味で長さが定義できる場合があることを意味している。
【００３４】
多くの場合、人間が図形を認識する際には、このようなカットオフを適当に選んで認識を行っていると思われる。
【００３５】
したがって、物理的な対象の図形を分類するときには、そのアルゴリズムの中に、測度あるいは微小線分要素、すなわちカットオフを巧く定義できるための構造が内在されていなければならない。
【００３６】
この要請に対して、擬似曲率の定義においてその役割を果たすのは、前記パラメータＥであるが、擬似曲率は、ドット列の番号によって定義されているために、不確定であり、よい定義となっていない。すなわち、前記図２２に示したように、線図形に対して、ドットの番号は、その表現の仕方、傾き具合によって、大きく変化するため、画素d[i]に対して、（d[i-k],d[i+k]）のドット（２次元ベクトル）のペアを考えるようなアルゴリズムでは、ｋが弧長に対して単調増加関数以上の特徴を持ったものと言えないので、不確定であり、曲率のような量的な特徴を算出するのに適さない。したがって、パラメータＥは、解像度を特定するものになっていない。
【００３７】
例えば、この従来例の擬似曲率を、前記図２０のコッホ曲線に対して定義することを試みる。理想化されたコッホ曲線を、倍率をパラメータとして画像化し、線図形（ドット列）に置き換えた後に、前記図１９を用いて説明したアルゴリズムで、擬似曲率を定義する。このとき、パラメータＥの物理的な長さが一定になるように、倍率に連動して値Ｅを変化させたとしても、画像データ化の際の画素数のあいまいさのために、画像化の際の倍率に対して、当該曲率関数は収束しない。
【００３８】
換言すると、２次元画像データ化する際のノイズに対して、従来の擬似曲率は、不安定な量となっている。
【００３９】
次に、アファイン変換について述べる。
【００４０】
数学の分野において、合同変換は、アファイン幾何学という分野で研究されており、純粋には、２次元平面上に定義された、２つの図形間の合同条件は、当該両図形がアファイン変換（平行移動と回転）後に完全に重なり合うことである。また、相似性は、このアファイン変換に拡大／縮小の変換を取り入れたものである。
【００４１】
したがって、図形の純粋な意味での合同性は、アファイン変換との無矛盾性が最も重要となる。
【００４２】
しかし、２つの曲線図形に対して、アファイン変換の自由度を除いて一致させる要請は、現実に絵として記述された図形については非常に困難である。「線」は太さを持っているため、数学的に厳密とはならない。また、前記図２２のように、２次元画像データとして、曲線図形を表現した場合には、図形は、量子化誤差のために、その表現方法に任意性がある。
【００４３】
しかしながら、この任意性は、画像データの画素の大きさに比較して曲線図形が非常に大きい場合には、人間の目で見ると厳密な図形を表しているように見られる程度のものである。この錯覚の上に、我々は画像データを一般に取り扱っている。とは言え、このような感覚を安易に数学的な量（例えば、今の場合には曲率）に適応させて、数学的厳密性を欠いたまま、定義を行ったとすれば、論理性や合理性を失うことになる。
【００４４】
数学において、ある対象ＡとＢに対して、ＡとＢがどれほど近いかを定義するためには位相（トポロジー）を導入する。現在の問題においても、ある種の位相（トポロジー）を導入して、比較を行わなければならない。このとき、現実の「線」が太さを持つ問題や、曲がり具合など、量子化誤差および離散化誤差等の問題を解決するような位相（トポロジー）でなければならない。
【００４５】
また、最終的に図形の同一性（合同性）を判定するならば、そのアルゴリズムは、アファイン変換に対して不変あるいは近似的に不変でなければならない。
【００４６】
このような要求を、従来の擬似曲率は全く満たしていない。例えば図２３に示すように、従来の擬似曲率は、アファイン変換、特に回転に対して不変ではないことが直ぐに分かる。図２３（ａ）に示すように、線図形を構成する直線が画素の格子と整合している場合には、ドット数と弧長は、その対応が倍率倍の線型変換で結びついている。これに対し、図２３（ｂ）に示すように、直線を斜めにすると、それを表現するための画素はギザギザになり、その表現に必要な画素数と長さとが倍率倍ではない対応となる場合がある。図２３（ｂ）に示すように、実際、４５度弱の角度にすると、長さが√2の直線を表現するために、３画素必要となってしまい、画素数と長さとに２倍程度の違いが現れる場合がある。
【００４７】
これを反映して、従来の擬似曲率（分布）関数のグラフ（第１または第２の擬似曲率のいずれを採っても）は、図２３の線図形に対して、図２４のようになる。図２４中、横軸は画素数を示し、縦軸は擬似曲率を示している。そして、太い線が、図２３（ａ）の、画素方向と整合した線図形の場合であり、細い曲線が、図２３（ｂ）の、斜め方向に向いた線図形の場合である。回転という変換に対して、擬似曲率（分布）関数は大きくその様相を変化させている。
【００４８】
逆に言えば、同一の画素数と擬似曲率のグラフに対しても、その回転方向等を変化させることにより、全く異なる図形が同一図形と認識されてしまうことになる。
【００４９】
これらの矛盾性を補正するために、上記従来の発明では、ニューラルネットを使用した補正方法を採るようにしているが、一般に、数学的に巧く定義されていないものから数学的に合理的な情報を再現することは困難である。
【００５０】
本発明は、この点に着目してなされたものであり、２次元格子点列からなる曲線を、アファイン変換に対して近似的に不変な図形の同一性判定により分類することが可能な曲線の分類方法、該分類方法を実現するためのプログラムおよび曲線分類装置を提供することを目的とする。
【課題を解決するための手段】
【００５１】
上記目的を達成するため、請求項１に記載の曲線の分類方法は、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法において、前記曲線に沿った弧長を等間隔に有限個に等分し、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、該接角の離散フーリエ成分を算出し、該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００５２】
上記目的を達成するため、請求項２に記載の曲線の分類方法は、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法において、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、該接角の離散フーリエ成分を算出し、該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００５３】
上記目的を達成するため、請求項３に記載の曲線の分類方法は、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法において、前記曲線に沿った弧長を等間隔に有限個に等分し、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とし、該離散曲率分布の離散フーリエ成分を算出し、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００５４】
上記目的を達成するため、請求項４に記載の曲線の分類方法は、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法において、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とし、該離散曲率分布の離散フーリエ成分を算出し、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００５５】
上記目的を達成するため、請求項５に記載の曲線の分類方法は、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法において、前記曲線に沿った弧長を等間隔に有限個に等分し、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とし、該離散曲率分布の離散フーリエ成分を算出し、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００５６】
上記目的を達成するため、請求項６に記載の曲線の分類方法は、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法において、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とし、該離散曲率分布の離散フーリエ成分を算出し、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００５７】
上記目的を達成するため、請求項７に記載の曲線の分類方法は、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法において、前記曲線に沿った弧長を等間隔に有限個に等分し、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正し、該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行うことを特徴とする。
【００５８】
上記目的を達成するため、請求項８に記載の曲線の分類方法は、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法において、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正し、該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行うことを特徴とする。
【００５９】
上記目的を達成するため、請求項９に記載のプログラムは、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、前記曲線の分類方法は、前記曲線に沿った弧長を等間隔に有限個に等分し、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、該接角の離散フーリエ成分を算出し、該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００６０】
上記目的を達成するため、請求項１０に記載のプログラムは、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、前記曲線の分類方法は、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、該接角の離散フーリエ成分を算出し、該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００６１】
上記目的を達成するため、請求項１１に記載のプログラムは、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、前記曲線の分類方法は、前記曲線に沿った弧長を等間隔に有限個に等分し、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とし、該離散曲率分布の離散フーリエ成分を算出し、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００６２】
上記目的を達成するため、請求項１２に記載のプログラムは、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、前記曲線の分類方法は、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とし、該離散曲率分布の離散フーリエ成分を算出し、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００６３】
上記目的を達成するため、請求項１３に記載のプログラムは、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、前記曲線の分類方法は、前記曲線に沿った弧長を等間隔に有限個に等分し、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とし、該離散曲率分布の離散フーリエ成分を算出し、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００６４】
上記目的を達成するため、請求項１４に記載のプログラムは、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、前記曲線の分類方法は、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とし、該離散曲率分布の離散フーリエ成分を算出し、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行うことを特徴とする。
【００６５】
上記目的を達成するため、請求項１５に記載のプログラムは、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、前記曲線の分類方法は、前記曲線に沿った弧長を等間隔に有限個に等分し、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現し、前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正し、該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行うことを特徴とする。
【００６６】
上記目的を達成するため、請求項１６に記載のプログラムは、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類方法を、コンピュータに実現させるためのプログラムであって、前記曲線の分類方法は、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換し、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分し、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現し、前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正し、該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行うことを特徴とする。
【００６７】
上記目的を達成するため、請求項１７に記載の記憶媒体は、請求項９〜１６のいずれかのプログラムを格納したことを特徴とする。
【００６８】
上記目的を達成するため、請求項１８に記載の曲線の分類装置は、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類装置において、前記曲線に沿った弧長を等間隔に有限個に等分する等分手段と、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現する表現手段と、該接角の離散フーリエ成分を算出する算出手段と、該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段とを有することを特徴とする。
【００６９】
上記目的を達成するため、請求項１９に記載の曲線の分類装置は、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類装置において、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換する変換手段と、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分する等分手段と、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現する表現手段と、該接角の離散フーリエ成分を算出する算出手段と、該算出されたフーリエ成分中、直流成分を除く低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段とを有することを特徴とする。
【００７０】
上記目的を達成するため、請求項２０に記載の曲線の分類装置は、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類装置において、前記曲線に沿った弧長を等間隔に有限個に等分する等分手段と、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現する表現手段と、隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とする第１の算出手段と、該算出された離散曲率分布の離散フーリエ成分を算出する第２の算出手段と、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段とを有することを特徴とする。
【００７１】
上記目的を達成するため、請求項２１に記載の曲線の分類装置は、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類装置において、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換する変換手段と、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分する等分手段と、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現する表現手段と、隣接する等分点上の前記接角の差φに対して、tan(φ/2)またはそれに比例した量を離散曲率として算出して、等分化された弧長点列上の分布とする第１の算出手段と、該算出された離散曲率分布の離散フーリエ成分を算出する第２の算出手段と、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段とを有することを特徴とする。
【００７２】
上記目的を達成するため、請求項２２に記載の曲線の分類装置は、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類装置において、前記曲線に沿った弧長を等間隔に有限個に等分する等分手段と、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現する表現手段と、隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とする第１の算出手段と、該算出された離散曲率分布の離散フーリエ成分を算出する第２の算出手段と、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段とを有することを特徴とする。
【００７３】
上記目的を達成するため、請求項２３に記載の曲線の分類装置は、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類装置において、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換する変換手段と、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分する等分手段と、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現する表現手段と、隣接する等分点上の前記接角の差を離散曲率として算出して、等分化された弧長点列上の分布とする第１の算出手段と、該算出された離散曲率分布の離散フーリエ成分を算出する第２の算出手段と、該算出されたフーリエ成分中の低周波成分と、所定の基準パターンのフーリエ成分中の所定成分とを比較することにより曲線の分類を行う分類手段とを有することを特徴とする。
【００７４】
上記目的を達成するため、請求項２４に記載の曲線の分類装置は、２次元整数格子内の区分的に線分として与えられた曲線を分類する曲線の分類装置において、前記曲線に沿った弧長を等間隔に有限個に等分する等分手段と、該等分された曲線に沿った１次元格子点での接角を、弧長の関数として表現する表現手段と、前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正する補正手段と、該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行う分類手段とを有することを特徴とする。
【００７５】
上記目的を達成するため、請求項２５に記載の曲線の分類装置は、２次元整数格子内の細線化されたドット列として与えられた曲線を分類する曲線の分類装置において、前記ドット列から構成される図形を、画素解像度より十分大きな解像度で区分的に線分列になるように変換する変換手段と、該変換によって得られた区分的線分曲線に沿った弧長を等間隔に有限個に等分する等分手段と、該等分された区分的線分曲線の１次元格子点での接角を、弧長の関数として表現する表現手段と、前記弧長と前記接角の作る面積をゼロにするように、当該接角の原点を補正する補正手段と、該補正後の接角および弧長と所定の基準パターンとを比較することにより、曲線の分類を行う分類手段とを有することを特徴とする。
【発明の効果】
【００７６】
以上説明したように、本発明によれば、アファイン変換に近似的に不変で、離散化誤差の影響の低い曲線分類を行うことができる。
【発明を実施するための最良の形態】
【００７７】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。
【００７８】
図１は、本発明の一実施の形態に係る曲線の分類方法を実現するパーソナルコンピュータ（ＰＣ）０の概略構成を示すブロック図である。
【００７９】
同図に示すように、ＰＣ０は、汎用のコンピュータであり、ＣＰＵ１、ＲＡＭ２、ＲＯＭ３、フレキシブル・ディスク（ＦＤ）ドライブ４、ＣＤ−ＲＯＭドライブ５、ハードディスク装置（ＨＤ）６、キーボード７、マウス８およびモニタ９によって構成されている。
【００８０】
そして、同図には、記憶媒体である、フレキシブル・ディスク（ＦＤ）１０およびＣＤ−ＲＯＭ１１も図示されている。
【００８１】
なお、各構成要素１〜９の一般的な作用については、十分周知されているため、その説明は省略する。
【００８２】
図２は、図１のＰＣ０の外観を示す図であり、図２から分かるように、ＰＣ０は、通常のデスクトップ型のパーソナルコンピュータである。
【００８３】
なお、図２中、図１と同一の構成要素には同一符号が付されている。
【００８４】
図３は、２次元整数格子内のＮ個の頂点列Ａ=｛（x[i],y[i]）|i=1,…,N｝からなる線分列の一例を示す図であり、この座標点列は、ＲＡＭ２の所定領域に格納されている。
【００８５】
本実施の形態では、このように格納された（与えられた）座標点列の形状を分類する。
【００８６】
説明を簡単にするために、点列は、開いた曲線からなり、点列には、曲線の連結性に従って、順番が付けられているものとし、すなわち、所謂、細線化された曲線とし、図４（ａ）〜（ｄ）にそれぞれ示すような、ひげ、解像度以上の折れ曲がり、二重線および交差点は、存在しないものと仮定する。
【００８７】
２次元画像データは、それが表現される時点で、量子化、離散化の誤差によって劣化していると判断すべきである。したがって、２次元画像データに表現される対象の分類を行う場合、それが表現によって劣化する以前の姿を推定して、分類を行わなければならない。例えば、着目する線図形が画素程度より大きなサイズの図形であり、画素サイズの数倍程度にはスムースな曲線によって構成されているという仮定に立てば、上述の回復は可能である。つまり、この仮定を受け入れると、２次元画像データとして得られた図形から、アファイン変換に不変な原図形の回復という推定操作がある程度可能となる。
【００８８】
原図形と２次元画素で表現された図形は、法（modulo）画素解像度で一致することを考慮に入れた変換として、図６（ａ）に示すように、区分的線分図形で画素解像度以下の情報を無視し、原図形を回復するようにする。その際、どの程度の解像度までを取り込むかを示すカットオフパラメータを導入して、図８に示すように、区分的線分図形への変換を行う。原図形は、点列によって定義されているため、近似的にアファイン変換に不変な図形として定義できる。
【００８９】
また、区分的線分図形においては、弧長が巧く定義できるので、弧長sに対する接角の角度関数φ(s)等が巧く定義できる。
【００９０】
図６（ｂ）に示すように、横軸を弧長とし、縦軸を相当する部分の角度とすると、ステップ（ヘビサイド）関数によって図形の特徴を表現することができる。このとき、法２πで、接角φには平行移動の自由度が存在する。これは、接角の角度を計る際に、何処を角度０とするかという自由度を意味し、アファイン変換における回転の自由度に相当する。
【００９１】
図６（ｂ）には、対応を連続なものとして表現したが、ＰＣ０上では、図形を弧長に沿って、１画素長程度あるいはそれ以上の長さで等分に区分けし、弧上の区分けされた１次元格子点上の角度分布を算出して、対応を見る。図６（ｃ）は、このようにして算出された角度分布のグラフである。この角度分布をフーリエ変換ししてグラフ表示したものが、図６（ｄ）および（ｅ）であり、（ｄ）が、フーリエ変換後のスペクトラル成分V[i]を表し、（ｅ）が、フーリエ変換後の位相（フェーズ）成分U[i]を表している。ここで、ＤＣ成分は、アファイン変換の一部である回転の自由度を意味しているので、この部分をマスクして、採用しないものとする。また、高周波側は、２次元画像データに量子化あるいは離散化した際の誤差を含んでいる。
【００９２】
つまり、ＤＣ成分を含まない低周波成分は、アファイン変換に不変であり、かつ、量子化誤差等も取り除かれていることを意味する。具体的には、例えば、図６（ｄ）および（ｅ）中の斜線部のような部分を考えている。
【００９３】
本実施の形態では、これらの情報に対して、例えばsupノルム（パターンマッチング法）を用いることで、２つの形状の同等性を評価するようにしている。
【００９４】
図５は、ＰＣ０のＣＰＵ１が実行する曲線分類処理１の手順を示すフローチャートである。
【００９５】
同図において、まず、ステップＳ１では、初期化を行い、必要であれば、細線化等の処理を行う。
【００９６】
次に、ステップＳ２では、ドットデータから区分的線分データ化を行う線分化処理サブルーチン（その詳細な処理は、図７を用いて後述する）を実行する。つまり、図３の点列に対して、図６（ａ）のような線分列のデータに変換する。これにより、２次元画像データに変換した際の誤差を軽減させるとともに、原図形のもつアファイン性を近似的に復元する。また、線分化により、２次元面の持つ自然な測度から誘導される測度が線分上に定義でき、「本発明が解決しようとする課題」欄で前述したヤコビアンの問題から解放される。
【００９７】
次に、ステップＳ３では、線分を、端から弧長に沿って等分割する。分割する長さは、適当なパラメータΔによって与えられているとする。合同性より相似性を要求する場合には、このとき、分割する数を一定にすれば、以下同様な処理で合同条件ではなく相似図形の問題を解くことができる。
【００９８】
そして、ステップＳ４では、接角分布の計算を行う。どちらか一方の端を“０”として、正方向に弧長をパラメータ化する。また、弧長が“０”での接角を“０”として、角度の原点を定める。接角φは、曲率dφ/dsの弧長による積分量であるので、微分不可能な曲線においても定義できる。少なくとも、超関数論の意味で定義できる。このようにして得られた接角φ[i]をグラフ化すると、図６（ｃ）のようなものとなる。
【００９９】
次に、ステップＳ５では、接角φ[i]に対して離散フーリエ変換を行う。前述のように、図６（ｄ）が、フーリエ変換後のスペクトラル成分V[i]を表し、図６（ｅ）が、フーリエ変換後の位相U[i]を表している。
【０１００】
さらに、ステップＳ６では、ステップＳ５で得られた離散フーリエ変換後のデータの内、必要でないものを除く処理、すなわちフィルタ処理を行う。具体的には、図６（ｄ）および（ｅ）中、斜線部で示した部分のみを、次のパターンマッチング処理（ステップＳ７）を行う領域として採用する。これにより、アファイン変換の自由度を保持しながら、離散化誤差等から近似的に解放することができる。
【０１０１】
ステップＳ７では、フーリエ変換後のデータのパターンマッチを行う。本実施の形態では、分類すべき対象となる曲線として、開いた曲線を採用しているので、弧長の原点を曲線の端とすると、位相成分（図６（ｅ））における任意性は符号の違いのみとなる。
【０１０２】
基準パターンのフーリエ変換データを（X[i],Y[i]）とする。但し、Ｘはスペクトル、Ｙは位相で、ｉはフィルタを通した後に残った領域であるとする。
【０１０３】
対象となるフーリエ変換データは（V[i],U[i]）である。ｉは、フィルタを通した後に残った領域であるとする。パターンマッチングする際には、それらの領域の違いを考慮に入れて比較する。つまり
【０１０４】
【数２】
2005189929.tif 000004
【０１０５】
とし、和の領域としては、図６（ｄ）および（ｅ）に斜線部で示した領域と基準パターンのフィルタ後の領域の小さい方を採る。
【０１０６】
そして、ステップＳ８では、Ｓ１，Ｓ２あるいはＳ１×Ｓ２の大きさで、標準パターンと同じものであるか否かを判断する。必要であれば、いくつかの標準パターンを用意しておき、そのどれに最も近いかを判定して形状を分類する。
【０１０７】
このようにして、曲線の分類が可能となる。
【０１０８】
次に、前記ステップＳ２の線分化処理サブルーチンでなされる線分化処理について説明する。なお、本実施の形態では、線分化処理として、特開平１−２９５３７６号公報に記載のものを採用している。
【０１０９】
線分列の頂点は、座標点列Ａの部分集合Ｂ＝｛（Vx[i],Vy[i]）|ｉ＝１，…，Ｒ｝として表される。数学的には、Ｂに余分な一点＊を加えＢ∪｛＊｝としたとき、集合ＡからＢ∪｛＊｝への射影（上への写像）を意味する。つまり、Ｂの点以外のＡ点は＊へ写像されるとし、Ｂの点となるＡの点は自分自身へ写像されるとすれば、写像が巧く定義される。
【０１１０】
このような写像を具体的にどのように決定するかが、点列の線分化問題である。予め、所定の閾値vtxth0を選定しておく。
【０１１１】
上述の仮定から、座標点列Ａの対応する曲線の両端は、既に判明しているとしてよい。
【０１１２】
図７は、この線分化処理サブルーチンの詳細な手順を示すフローチャートである。このフローチャートに従って線分化処理の手順を順次説明する前に、まず、その具体例である図８に従って説明する。
【０１１３】
まず、図８（ａ）のように、両端を線分で結ぶ。これを階層１の線分と呼ぶ。この線分の両端で挟まれた領域における座標点（図示例では、すべて）に対して、該線分との距離r[i]（ｉ＝１，…，Ｎ）を求める。この距離r[i]のうち、最大のものが、閾値vtxth0より小さい場合には、この階層１の線分を求める線分列とする。
【０１１４】
図８（ａ）は、最大距離が、閾値vtxth0より大きい場合を図示しており、点Ｐが最大距離の点である。この場合、点Ｐを新たな頂点列の一つとし、図８（ｂ）のようにする。これにより、一つ階層を上げ、得られた点列を階層２の頂点列とする。
【０１１５】
このような操作を、各線分上で、次のように繰り返す。すなわち、現在の階層をＫ（＞１）とする。階層Ｋの線分列の内の１つの線分に着目する。該線分の両端で挟まれた領域での座標点列Ａの部分列の該線分からの距離をr[i]（ｉ＝ｊ１，…，ｊ２）とし、r[i]（ｉ＝ｊ１，…，ｊ２）を求める。この求めた距離の最大のもの（最大距離ｄ）が、閾値vtxth0より小さい場合には、該線分を求める線分列の一部とする。このとき、対応する線分は、階層Ｋについて収束したとし、階層をＫからＫ＋１に増やした場合も、線分列の対応する部分は変化しないものとする。
【０１１６】
一方、最大距離ｄが、閾値vtxth0より大きい場合には、最大値を持つ点を次の階層Ｋ＋１での頂点列の一つとする。この操作を、同じ階層内の、すべての収束していない線分に対して行い、階層Ｋ上ですべての線分について操作を行った後に、階層をＫからＫ+１に上げる。
【０１１７】
このような操作を繰り返すことにより、階層を十分深くすると、座標点は有限個であるので、最終的にすべての線分が収束し、つまり、すべての点列が、対応する線分から閾値vtxth0よりも小さい距離にあるように、線分列を構成することができる。
【０１１８】
このようにして、図８（ａ）の階層１の線分に対して、図８（ｄ）のより階層の深い線分が得られる。
【０１１９】
図７のフローチャートは、上記手順をフローチャートの形式で表現したものである。図７に従って、一般的な場合の線分化方法について説明する。
【０１２０】
同図において、まず、ステップＳ１１では、初期化を行う。つまり、階層Ｋを“１”にするとともに、曲線の両端を階層１の線分の両端とする。
【０１２１】
次に、ステップＳ１２では、着目するｉ番目の線分が、階層Ｋの線分列の最終線分を超えたか否かをチェックする。
【０１２２】
ｉ番目の線分が階層Ｋの線分列の最終線分でなければ、ステップＳ１３で、線分内の対応する座標点の線分からの距離の最大値を計算する。
【０１２３】
次に、ステップＳ１４で、線分の最大距離ｄが閾値vtxth0より大きければ、ステップＳ１５へ移行し、ｉ番目の線分を、最大距離ｄを持つところで分割して、二つの線分に分割する。
【０１２４】
一方、ステップＳ１４で、線分の最大距離ｄが閾値vtxth0より小さければ、その線分は収束したとする。
【０１２５】
そして、ステップＳ１６では、同じ階層Ｋ内での線分列の次の線分に移る。
【０１２６】
ここで、再びステップＳ１２で、着目するｉ番目の線分が、階層Ｋの線分列の最終線分か否かをチェックする。
【０１２７】
ステップＳ１３〜Ｓ１６の処理を繰り返し、階層Ｋの線分列の最終線分まで繰り返す。
【０１２８】
ステップＳ１７で、すべての線分において、その最大距離が閾値vtxth0より小さければ、ステップＳ１８で、順番を入れ替えて、本線分化処理を終了する。
【０１２９】
一方、ステップＳ１７で、すべて線分が収束していなければ、ステップＳ１９で、階層を一つ上げて、ステップＳ１２に戻る。
【０１３０】
以上の処理を繰り返し、最終的にはすべてが収束して、本線分化処理を終了する。
【０１３１】
このような線分化処理によれば、コッホ曲線のようなものに対しても、物理的な意味のカットオフを与え、測度が巧く定義できる線分列に変換できる。また、解像度を決めるパラメータとして、閾値vtxth0を持っており、合理的に解像度を変更できる。
【０１３２】
また、このようにして得られた線分列は、原図形を近似的に表現していると考えられ、２次元画像データに置き換えた際に失ったアファイン自由度を再び近似的に再現している。
【０１３３】
実際、図９（ａ）に示すように、直線が画素の格子と整合している場合も、図９（ｂ）に示すように、直線を斜めにした場合も、ほぼ同一の接角分布をもっている。つまり、図１０のように、近似的にアファイン性を回復していることが分かる。図１０中、横軸が弧長を表し、縦軸が接角を表し、太い線が図９（ａ）の画素方向と整合した場合であり、細い曲線が図９（ｂ）の斜め方向に向いた場合である。回転という変換に対して、前記図２４の擬似曲率分布関数と異なり、接角と弧長の関係は、ほぼ同一の分布を与えている。
【０１３４】
本実施の形態では、開いた曲線を例に挙げて説明したが、閉じた曲線の場合には、弧長の原点をどこに取るかの任意性がある。
【０１３５】
そのため、フーリエ変換データ（V[i],U[i]）の内、スペクトルＶは、弧長の原点の取り方に依存しないが、位相Ｕは、弧長の原点の取り方に依存する。したがって、パターンマッチングの際、
【０１３６】
【数３】
2005189929.tif 000005
【０１３７】
を先に比較して、ある閾値より小さければ、位相成分のパターンマッチングを行うようにすればよい。この場合、各位相成分を原点のずれに応じて変更してもよい。つまり、位相成分の各波長に応じて法（modulo）周波数で位相の変換をすればよい。現在の弧長の原点を“０”として、対応する位相成分をU[0,i]:=U[i]とする。
このとき、
【０１３８】
【数４】
2005189929.tif 000006
【０１３９】
がパターンマッチングの評価量となる。
【０１４０】
これにより、閉じた曲線に対しても、例えばＳ１×Ｓ２を評価することにより、分類を行うことができる。
【０１４１】
但し、閉じた場合の線分化については、上述したものに加え工夫が必要であるが、それについても、前記特開平１−２９５３７６号公報に記載されているので、それを使用すればよい。
【０１４２】
次に、ＰＣ０のＣＰＵ１が実行する曲線分類処理２について説明する。
【０１４３】
図１１は、この曲線分類処理２の手順を示すフローチャートであり、前記図５の曲線分類処理１に対して、ステップＳ１１の離散曲率の計算を追加した点のみが異なっている。このため、図１１中、図５と同様の処理を行うステップには同一符号を付し、その説明を省略する。
【０１４４】
図１２は、曲線分類処理２のアルゴリズムを説明するための図であり、図１２（ａ）〜（ｃ）は、図６（ａ）〜（ｃ）と同じ図である。
【０１４５】
さて、図１２（ｃ）に示す、離散化された角度分布をφ（si）として、離散曲率κを次式で定義する。
【０１４６】
【数５】
2005189929.tif 000007
【０１４７】
ここで、δsは１次元格子点の格子間隔である。図１２（ｄ）は、この定義から得られた離散曲率分布のグラフを示している。κは、φの差として定義されるため、φ＝０となる角度を平面内のどの方向にするかに依存しない。
【０１４８】
κ(si)をフーリエ変換すると、図１２（ｅ）および（ｆ）のようになる。（ｅ）が、フーリエ変換後のスペクトラル成分V[i]を表し、（ｆ）が、フーリエ変換後の位相（フェーズ）U[i]を表している。ここで、ＤＣ成分は、曲線の両端での接角の差を意味しているので、ＤＣ成分も有用な情報を持っている。他方、高周波側は、２次元画像データに量子化あるいは離散化した際の誤差を含んでいる。
【０１４９】
つまり、低周波成分は、アファイン変換に不変であり、かつ、量子化誤差等も取り除かれていることを意味する。具体的には、例えば、図１２（ｅ）および（ｆ）中の斜線部のような部分を考えている。
【０１５０】
本曲線分類処理２では、これらの情報に対して、例えばsupノルム（パターンマッチング法）を用いることで、２つの形状の同等性を評価するようにしている。
【０１５１】
図１１のステップＳ４では、図５のステップＳ４と同様にして、接角分布の計算を行う。このステップＳ４で得られた接角φ[i]は、図１２（ｃ）のようなものとなる。これにより、離散曲率
【０１５２】
【数６】
2005189929.tif 000008
【０１５３】
を計算し、前記ＲＡＭ２の所定領域に格納する。必要であれば、ＨＤ６やＦＤ１０に書き込んで格納してもよい。
【０１５４】
図１２（ｄ）は、前述のように、離散曲率分布を示している。
【０１５５】
ステップＳ５では、離散曲率分布に対して離散フーリエ変換を行い、ＲＡＭ２の所定領域に格納する。必要であれば、ＨＤ６やＦＤ１０に書き込んで格納してもよい。
【０１５６】
図１２（ｅ）が、フーリエ変換後のスペクトラル成分V[i]を表し、図１２（ｆ）が、フーリエ変換後の位相U[i]を表している。
【０１５７】
これ以降のステップＳ６〜Ｓ８の各処理は、それぞれ図５のステップＳ６〜Ｓ８の各処理と同様であるため、その説明は省略する。
【０１５８】
次に、ＰＣ０のＣＰＵ１が実行する曲線分類処理３について説明する。
【０１５９】
図１３は、この曲線分類処理３の手順を示すフローチャートであり、前記図１１の曲線分類処理２に対して、ステップＳ１１′の離散曲率の計算で計算する離散曲率の定義のみが異なっている。このため、図１３中、図１１と同様の処理を行うステップには同一符号を付し、その説明を省略する。
【０１６０】
ここで、離散曲率を次式で定義する。
【０１６１】
【数７】
2005189929.tif 000009
【０１６２】
但し、δsは１次元格子点の格子間隔である。この離散曲率の意味について、図１４に従って説明する。
【０１６３】
図１４は、１次元格子点の一部分を図示したものである。同図のように、格子点は、必ずしも折れ線図の頂点と重なってはいない。図中、Δθiは、φ（si）−φ（si-1）を意味している。図１４において、特徴的な長さは格子間隔δsである。連続極限（δs→０）で、離散曲率は、通常の曲率に一致することが自然である。そこで、図に示すように、δs/2を長辺とする直角三角形の短辺を半径とする内接円を考え、その短辺を離散曲率半径とすることは合理的である。また、連続の場合、曲率は曲率半径の逆数となることが知られているので、離散曲率を離散曲率半径の逆数として定義した。この定義において、δs/2を比較すべき図形全体に対して、固定すれば、それを“１”に規格化することによって、tan((φ(si)−φ(si-1))/2)を離散曲率とするやり方もある。また、図形の相似性を議論する場合は、積極的にこの規格化を利用してもよい。本実施の形態では、図形の合同性を取り扱っているのでδsを含めて定義した。
【０１６４】
このようにして定義された離散曲率は、前提として前記図４の（ａ）または（ｂ）のような状況を排除しているために発散しないので、うまく取り扱うことができる。また、幾何学的な意味がはっきりしているために、離散化の大きさに強く依存しないことになり、離散曲率を
【０１６５】
【数８】
2005189929.tif 000010
【０１６６】
とする算術的な単純差分に比較して安定である。
【０１６７】
図１３のステップＳ４では、図１１のステップＳ４と同様にして、接角分布の計算を行う。このステップＳ４で得られた接角φ[i]は、前記図１２（ｃ）のようなものとなる。これにより、離散曲率
【０１６８】
【数９】
2005189929.tif 000011
【０１６９】
を計算し、前記ＲＡＭ２の所定領域に格納する。ここで、｜φ[i]−φ[i−1]｜が十分小さい場合には、そのままκ[i]＝０とし、また、δsがある一定値より小さい場合には、計算を止めてエラーを返し、オーバーフローが起こらないようにする。さらに、必要であれば、ＨＤ６やＦＤ１０に書き込んで格納してもよい。離散曲率分布は、前記図１２（ｄ）と同様である。
【０１７０】
ステップＳ５では、離散曲率分布の離散フーリエ変換を行い、ＲＡＭ２の所定領域に格納する。必要であれば、ＨＤ６やＦＤ１０に書き込んで格納してもよい。
【０１７１】
これ以降のステップＳ６〜Ｓ８の各処理は、それぞれ図５のステップＳ６〜Ｓ８の各処理と同様であるため、その説明は省略する。
【０１７２】
次に、ＰＣ０のＣＰＵ１が実行する曲線分類処理４について説明する。
【０１７３】
図１５は、この曲線分類処理４の手順を示すフローチャートであり、前記図５の曲線分類処理１に対して、離散フーリエ変換およびフィルタ操作の各処理を削除するとともに、補正処理を追加した点のみが異なっている。このため、図１５中、図５と同様の処理を行うステップには同一符号を付し、その説明を省略する。
【０１７４】
図１６は、曲線分類処理４のアルゴリズムを説明するための図であり、図１６（ａ）〜（ｃ）は、図６（ａ）〜（ｃ）と同じ図である。
【０１７５】
接角の原点は、アファイン変換における回転の自由度に相当して、任意性が生じるので、これを一定にするため、図１６（ｃ）の点列の囲む面積を“０”とするように接角の原点を取り直す。
【０１７６】
つまり、平均接角を引いておけばよい。このような処理を施したのが、図１６（ｄ）である。
【０１７７】
本曲線分類処理４では、これらの情報に対して、例えばsupノルム（パターンマッチング法）を用いることで、２つの形状の同等性を評価するようにしている。
【０１７８】
図１５のステップＳ４では、図５のステップＳ４と同様にして、接角分布の計算を行う。このステップＳ４で得られた接角φ[i]は、図１６（ｃ）のようなものとなる。
【０１７９】
次に、ステップＳ２１では、接角の平均値を計算し、それを各接角から減算する。このような補正処理を施したものをY[i]とする。図１６（ｄ）は、この補正処理を施した接角分布を示している。
【０１８０】
そして、ステップＳ７では、ステップＳ６で補正した弧長と接角に対して、パターンマッチを行う。
【０１８１】
今、対象としているのが、開いた曲線であるので、接角の任意性は符号の違いのみである。
【０１８２】
基準パターンの弧長接角データをX[i]とする。Ｘの全平均接角が“０”となるように原点を取っている。
【０１８３】
【数１０】
2005189929.tif 000012
【０１８４】
とし、評価量を計算する。
【０１８５】
次のステップＳ７の処理は、図５のステップＳ７の処理と同様であるため、その説明は省略する。
【０１８６】
なお、図３に示すような連結した画素の点列が与えられているのではなく、図６（ａ）のような線分列が与えられている場合には、図５、図１１、図１３および図１５の各ステップＳ２の線分化処理を行わず、その次のステップＳ３より始めれば、同様に、線分列に対する曲線の分類が可能である。
【０１８７】
以上説明した曲線の分類方法は、種々の画像処理に応用が可能である。例えば、画像処理のハードウェアおよびソフトウェアとあわせて、指紋や網膜の特徴抽出等による身体的鍵照合の技術分野、筆跡鑑定の技術、それを応用した複写機、ファクシミリにおける付加画像処理機能にも有用である。また、計算機シミュレーションやゲーム機等において、計算結果を分類する場合等にも効果を発揮する。
【０１８８】
なお、上述した実施の形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムまたは装置に供給し、そのシステムまたは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行することによっても、本発明の目的が達成されることは言うまでもない。
【０１８９】
この場合、記憶媒体から読出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【０１９０】
プログラムコードを供給するための記憶媒体としては、たとえば、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることができる。また、通信ネットワークを介してサーバコンピュータからプログラムコードが供給されるようにしてもよい。
【０１９１】
また、コンピュータが読出したプログラムコードを実行することにより、上述した実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳなどが実際の処理の一部または全部を行い、その処理によって上述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【０１９２】
さらに、記憶媒体から読出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって上述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【０１９３】
【図１】本発明の一実施の形態に係る曲線の分類方法を実現するパーソナルコンピュータの概略構成を示すブロック図である。
【図２】図１のパーソナルコンピュータの外観を示す図である。
【図３】本実施の形態において分類の対象としたドット列の一例を示す図である。
【図４】本実施の形態の曲線の分類方法で前提としないドット列の例を示す図である。
【図５】図１のパーソナルコンピュータが実行する曲線分類処理１の手順を示すフローチャートである。
【図６】図５の曲線分類処理１のアルゴリズムを説明するための図である。
【図７】図５の線分化処理サブルーチンの詳細な手順を示すフローチャートである。
【図８】図７の線分化処理サブルーチンのアルゴリズムを説明するための図である。
【図９】線図形を構成する直線が画素の格子と整合している場合と整合していない場合の各一例を示す図である。
【図１０】図９の各線図形に対して、それぞれ図５の曲線分類処理１を用いて算出した各接角分布を示す図である。
【図１１】図１のパーソナルコンピュータが実行する曲線分類処理２の手順を示すフローチャートである。
【図１２】図１１の曲線分類処理２のアルゴリズムを説明するための図である。
【図１３】図１のパーソナルコンピュータが実行する曲線分類処理３の手順を示すフローチャートである。
【図１４】１次元格子点の一部分を示す図である。
【図１５】図１のパーソナルコンピュータが実行する曲線分類処理４の手順を示すフローチャートである。
【図１６】図１５の曲線分類処理４のアルゴリズムを説明するための図である。
【図１７】従来の技術を説明するために用いるドット列の一例を示す図である。
【図１８】擬似曲率の定義を説明するための図である。
【図１９】従来の曲線分類処理の手順を示すフローチャートである。
【図２０】フラクタル曲線の一例としてのコッホ曲線を示す図である。
【図２１】曲線に対して定義される接角を示す図である。
【図２２】同一の線分を表現する際に、そのドット数は線分の長さに対して一定ではないことを示す図である。
【図２３】線図形を構成する直線が画素の格子と整合している場合と整合していない場合の各一例を示す図である。
【図２４】図２３の各線図形に対して、それぞれ算出した各擬似曲率分布関数のグラフを示す図である。
【符号の説明】
【０１９４】
０  パーソナルコンピュータ本体
１  ＣＰＵ
２  ＲＡＭ
３  ＲＯＭ
４  フレキシブルディスクドライブ
５  ＣＤ−ＲＯＭドライブ
６  ハードディスク装置
７  キーボード
８  マウス
９  モニタ
１０  フレキシブルディスク
１１  ＣＤ−ＲＯＭ
【図１】
2005189929.tif 000013
【図２】
2005189929.tif 000014
【図３】
2005189929.tif 000015
【図４】
2005189929.tif 000016
【図５】
2005189929.tif 000017
【図６】
2005189929.tif 000018
【図７】
2005189929.tif 000019
【図８】
2005189929.tif 000020
【図９】
2005189929.tif 000021
【図１０】
2005189929.tif 000022
【図１１】
2005189929.tif 000023
【図１２】
2005189929.tif 000024
【図１３】
2005189929.tif 000025
【図１４】
2005189929.tif 000026
【図１５】
2005189929.tif 000027
【図１６】
2005189929.tif 000028
【図１７】
2005189929.tif 000029
【図１８】
2005189929.tif 000030
【図１９】
2005189929.tif 000031
【図２０】
2005189929.tif 000032
【図２１】
2005189929.tif 000033
【図２２】
2005189929.tif 000034
【図２３】
2005189929.tif 000035
【図２４】
2005189929.tif 000036