(57)【要約】【課題】曲線の曲がり具合を精度よく符号化する。【解決手段】コンピュータを、曲線上における複数の代表点を選択する代表点選択部と、幹と、それぞれが幹の端点に対して所定の角度で取り付けられ、それぞれに対して異なる符号が割り当てられた複数の枝とをそれぞれ有する複数の基本構造のそれぞれを、端点が当該基本構造に対応する複数の代表点のそれぞれに略重なるように配置する配置部と、複数の代表点のうちの第１の代表点から曲線に沿って順番に、当該代表点に配置したそれぞれの基本構造が有する複数の枝のうち、曲線の当該代表点における傾きベクトルとより近い枝を順次選択する枝選択部と、次の基本構造の方向および回転角を調整する調整部と、複数の基本構造のそれぞれについて選択した枝に割り当てられた符号に基づいて、曲線の曲がり具合を表すデータを生成する生成部として機能させる符号化プログラムを提供する。【選択図】図１
2008015710.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、与えられた曲線の曲がり具合を符号化する符号化装置として機能させる符号化プログラムであって、
当該符号化プログラムは、前記コンピュータを、
前記曲線上における複数の代表点を選択する代表点選択部と、
幹と、それぞれが前記幹の端点に対して所定の角度で取り付けられ、それぞれに対して異なる符号が割り当てられた複数の枝とをそれぞれ有する複数の基本構造のそれぞれを、前記端点が当該基本構造に対応する前記複数の代表点のそれぞれに略重なるように配置する配置部と、
前記複数の代表点のうちの第１の代表点から前記曲線に沿って順番に、当該代表点に配置したそれぞれの前記基本構造が有する前記複数の枝のうち、前記曲線の当該代表点における傾きベクトルとより近い枝を順次選択する枝選択部と、
それぞれの前記代表点に配置された前記基本構造の枝が選択される度に、前記枝選択部が次の前記代表点に配置された前記基本構造の枝を選択するのに先立って、当該代表点の次の前記代表点に配置された前記基本構造の前記幹の方向および回転角が、選択された前記枝に対応して予め定められた指定方向および指定回転角となるように、次の前記基本構造の方向および回転角を調整する調整部と、
前記複数の基本構造のそれぞれについて選択した前記枝に割り当てられた符号に基づいて、前記曲線の曲がり具合を表すデータを生成する生成部と
して機能させる符号化プログラム。
【請求項２】
前記基本構造が有するそれぞれの前記枝の方向と、当該枝の前記指定方向とが異なる請求項１に記載の符号化プログラム。
【請求項３】
前記基本構造は、符号０が割り当てられた前記枝と符号１が割り当てられた前記枝の２本の前記枝を有しており、前記生成部は、前記曲線に沿って順番にそれぞれの前記基本構造について選択された前記枝に割り当てられた符号を連結して得られる前記データを出力する請求項１に記載の符号化プログラム。
【請求項４】
前記基本構造の前記幹および２本の前記枝のそれぞれの長さは略同一であり、前記幹と２本の前記枝のそれぞれとの間の角度は略１２０度であり、２本の前記枝の間の角度は略９０度である請求項１に記載の符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化プログラムに関する。特に本発明は、与えられた曲線の曲がり具合を符号化する符号化装置として機能させる符号化プログラムに関する。
【背景技術】
【０００２】
タンパク質の機能的性質は、当該タンパク質の３次元構造によって決まる。従って、解析者は、タンパク質の複雑な３次元構造を何らかの表現形式に変換して比較することにより、タンパク質同士の機能的性質の類似度を算出することができる。
【０００３】
３次元形状の表現方法としては、一例として、物体を基本形状（直方体、球、円筒等）の組み合わせで表す方法と、ポリゴンメッシュで表す方法が知られている。物体を基本形状の組み合わせで表す方法の一例として、特許文献１および２には、Ｎ−１次元空間（Ｎは２以上の任意の整数）の曲線を、複数のＮ面体を接続した１本の鎖により近似し、当該鎖の折れ曲がり方を二値数列で表す方法が開示されている。
【０００４】
また、タンパク質等の生体高分子のバックボーンの折り畳まれ方を表す数理的方法として、非特許文献１〜３に記載された方法が知られている。非特許文献１には、タンパク質を構成するアミノ酸のねじれ具合（Ｎ−Ｃａ結合およびＣａ−Ｃ結合の周りの回転角）を２次元チャートに表示して、αヘリクスおよびβシートの構造を大まかに特徴付けるＲａｍａｃｈａｎｄｒａｎプロット法が開示されている。非特許文献２には、タンパク質のバックボーンを空間折れ線とみなして、微分幾何学の考え方を用いて立体構造の類似性を定量化する方法が開示されている。非特許文献３には、数十個の幾何学的パラメータを用いることで、タンパク質の立体構造を分類する方法が開示されている。
【０００５】
さらに、特許文献２には、タンパク質等の生体高分子の３次元構造を、複数のＮ面体を接続した１本の鎖により近似し、当該鎖の折れ曲がり方を二値数列で表す方法が開示されている。特許文献２により開示された方法によれば、タンパク質等の生体高分子の３次元構造に対応する曲線の曲がり方が１次元の数列で表されるので、例えば、タンパク質等の生体高分子同士の３次元構造の類似度を、１次元数列同士を比較することにより算出することができる。
【０００６】
【特許文献１】国際公開第０２／１０１５９８号パンフレット
【特許文献２】国際公開第０３／０４０９６８号パンフレット
【非特許文献１】Taubin,G. and Rossignac,J. ,"Geometry Compression through Topological Surgery", ACM Transactions on Graphics, 17(2), １９９８年, P.84-115
【非特許文献２】C.Branden and J.Tooze, "Introduction to Protein Structure.", 米国, Garland Publishing Inc., １９９８年
【非特許文献３】S.Rackovsky, H.A.Scheranga, "Differential Geometry and Polymer Conformation. 1.", Macromolecules, １９７８年１１月, P.1168-1174
【非特許文献４】P.Rogen, B.Fain, "Automatic classification of protein structure by using Gauss integrals." Proc Natl Acad Sci, ２００３年, P100,P.119-124
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、タンパク質等の生体高分子の３次元構造に対応する曲線を符号化する符号化装置は、さらに精度よく、曲線の曲がり具合を符号化できることが望ましい。すなわち、当該符号化装置は、曲線同士の曲がり具合の類似度を精度よく算出することができる符号を、生成できることが望ましい。
【０００８】
そこで本発明は、上記の課題を解決することのできる符号化プログラムを提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【０００９】
本発明の第１の形態によると、コンピュータを、与えられた曲線の曲がり具合を符号化する符号化装置として機能させる符号化プログラムであって、当該符号化プログラムは、コンピュータを、曲線上における複数の代表点を選択する代表点選択部と、幹と、それぞれが幹の端点に対して所定の角度で取り付けられ、それぞれに対して異なる符号が割り当てられた複数の枝とをそれぞれ有する複数の基本構造のそれぞれを、端点が当該基本構造に対応する複数の代表点のそれぞれに略重なるように配置する配置部と、複数の代表点のうちの第１の代表点から曲線に沿って順番に、当該代表点に配置したそれぞれの基本構造が有する複数の枝のうち、曲線の当該代表点における傾きベクトルとより近い枝を順次選択する枝選択部と、それぞれの代表点に配置された基本構造の枝が選択される度に、枝選択部が次の代表点に配置された基本構造の枝を選択するのに先立って、当該代表点の次の代表点に配置された基本構造の幹の方向および回転角が、選択された枝に対応して予め定められた指定方向および指定回転角となるように、次の基本構造の方向および回転角を調整する調整部と、複数の基本構造のそれぞれについて選択した枝に割り当てられた符号に基づいて、曲線の曲がり具合を表すデータを生成する生成部として機能させる符号化プログラムを提供する。
【００１０】
符号化プログラムは、基本構造が有するそれぞれの枝の方向と、当該枝の指定方向とが異なっていてよい。基本構造は、符号０が割り当てられた枝と符号１が割り当てられた枝の２本の枝を有しており、生成部は、曲線に沿って順番にそれぞれの基本構造について選択された枝に割り当てられた符号を連結して得られるデータを出力してよい。  符号化プログラムは、基本構造の幹および２本の枝のそれぞれの長さは略同一であり、幹と２本の枝のそれぞれとの間の角度は略１２０度であり、２本の枝の間の角度は略９０度であってよい。
【００１１】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【００１２】
本発明によれば、曲線の曲がり具合を、精度よく符号化することができる。さらに、本発明によれば、曲線同士の曲がり具合の類似度を精度よく算出することができる符号を、生成することができる。
【発明を実施するための最良の形態】
【００１３】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００１４】
図１は、本実施形態に係る符号装置１０の構成を示す。符号装置１０は、入力部１２と、代表点選択部１４と、傾きベクトル生成部１６と、配置部１８と、枝選択部２０と、調整部２２と、生成部２４とを備える。符号装置１０は、与えられた曲線の曲がり具合を、例えば二値数列で表される符号列に符号化する。すなわち、符号装置１０は、曲線の曲がり方または曲線の変化を表す符号列を、生成することができる。従って、符号装置１０により生成された符号列は、他の符号列と比較することによって、曲線同士の曲がり具合の類似度を算出させることができる。例えば、符号装置１０は、タンパク質等の生体高分子の３次元構造を表す曲線を符号化して、その結果得られる符号列をタンパク質の分類および検索等に利用させることができる。
【００１５】
入力部１２は、符号化対象として与えられた曲線を入力する。入力部１２は、一例として、２次元または３次元空間座標上に表された曲線データを入力してよい。代表点選択部１４は、入力部１２により入力された曲線上における複数の代表点を選択する。代表点選択部１４は、一例として、曲線の一方の端（開始端）から他方の端（終了端）へ向かう方向に、順序付けされた複数の代表点を選択してよい。代表点選択部１４は、一例として、選択した各代表点の曲線上の位置を表すデータを、各代表点の順序を表すデータとともに記憶してよい。
【００１６】
傾きベクトル生成部１６は、選択した複数の代表点のそれぞれに対応する複数の傾きベクトルを生成する。傾きベクトル生成部１６は、一例として、延伸方向が当該代表点から次の代表点へと向かう側の傾きベクトルを生成してよい。傾きベクトル生成部１６は、一例として、代表点における曲線の接線に平行であって、当該代表点から次の代表点へと向かう側の方向を示す傾きベクトルを生成してよい。傾きベクトル生成部１６は、一例として、選択した代表点毎に傾きベクトルを表すデータを算出して、代表点と対応付けて記憶してよい。
【００１７】
配置部１８は、幹３２と、それぞれが幹３２の端点に対して所定の角度で取り付けられ、それぞれに対して異なる符号が割り当てられた複数の枝３４とをそれぞれ有する複数の基本構造３０を、複数の代表点のそれぞれに配置する。配置部１８は、一例として、幹３２の長さ、幹３２の位置、幹３２の方向および幹３２の軸周りの予め設定された位置の角度を示す回転位置指標を、基本構造３０における幹３２を表すデータとして生成して、複数の代表点のそれぞれに対応付けて記憶してよい。また、配置部１８は、複数の枝３４のそれぞれの長さ、複数の枝３４のそれぞれの幹３２に対する相対的な位置および方向、枝３４の方向とは別個に複数の枝３４のそれぞれに対応して予め設定された基本構造３０の指定方向（方向ベクトル）、複数の枝３４のそれぞれの軸周りの予め設定された位置の指定角度を示す回転位置指標、および、複数の枝３４のそれぞれに割り当てられた符号を、基本構造３０における複数の枝３４のそれぞれを表すデータとして生成して、複数の代表点のそれぞれに対応付けて記憶してよい。なお、基本構造３０が有する複数の枝３４のそれぞれ方向は、当該枝３４に対応する指定方向（方向ベクトル）と異なってよい。
【００１８】
さらに、基本構造３０を代表点に配置する場合において、配置部１８は、複数の基本構造３０のそれぞれを、端点が当該基本構造３０に対応する複数の代表点のそれぞれに略重なるように配置する。配置部１８は、一例として、生成した複数の基本構造３０を表すデータを、対応する代表点の曲線上の位置に対応付けて記憶してよい。
【００１９】
枝選択部２０は、複数の代表点のうちの第１の代表点から曲線に沿って順番に、一つずつ代表点を選択する。そして、枝選択部２０は、選択した当該代表点に配置したそれぞれの基本構造３０が有する複数の枝３４のうち、曲線の当該代表点における傾きベクトルとより近い枝３４を順次選択する。枝選択部２０は、一例として、選択した基本構造３０が有する複数の枝３４のうち、当該代表点に対応する傾きベクトルとの角度差がより小さい方向の枝３４を選択する。枝選択部２０は、一例として、選択した基本構造３０が有する複数の枝３４の方向を示すデータと、当該代表点に対応する傾きベクトルの方向を示すデータとを比較することにより、角度差がより小さい方向の枝３４を選択してよい。そして、枝選択部２０は、一例として、選択した枝３４に割り付けられた符号を、選択した当該代表点に対応する符号として記憶する。
【００２０】
調整部２２は、枝選択部２０によりそれぞれの代表点に配置された基本構造３０の枝３４が選択される度に、枝選択部２０が次の代表点に配置された基本構造３０の枝３４を選択するのに先立って、次の基本構造３０の方向および回転角を調整する。この場合において、調整部２２は、当該代表点の次の代表点に配置された基本構造３０の幹３２の方向および回転角が、枝選択部２０により選択された枝３４に対応して予め定められた指定方向および指定回転角となるように、次の基本構造３０の方向および回転角を調整する。調整部２２は、一例として、当該基本構造３０における選択された枝３４に対応して予め設定された基本構造３０の方向（方向ベクトル）を、当該基本構造３０が配置された代表点の傾きベクトルに一致させるように、当該基本構造３０を表すデータを修正する。続いて、調整部２２は、次の基本構造３０における幹３２の方向および当該幹３２の軸周りの予め設定された位置を示す基準回転角が、当該基本構造３０の選択された枝３４に対応して予め設定された指定方向および指定回転角と一致するように、次の基本構造３０を表すデータを修正してよい。
【００２１】
生成部２４は、複数の基本構造３０のそれぞれについて選択した枝３４に割り当てられた符号に基づいて、曲線の曲がり具合を表すデータを生成する。生成部２４は、一例として、複数の基本構造３０のそれぞれについて枝選択部２０により選択された枝３４に割り当てられた符号を、代表点の順序に従って並べる。そして、生成部２４は、代表点の順序に従って並べた符号列を、曲線の曲がり具合を表すデータとして出力してよい。
【００２２】
以上のような符号装置１０によれば、曲線の曲がり具合を、簡単な符号で精度よく表すことができる。これにより符号装置１０によれば、曲線の曲がり具合の類似度を比較することができる符号を生成することができる。
【００２３】
図２（Ａ）は、本実施形態に係る基本構造３０の一例を示し、図２（Ｂ）は、第１枝３４−１が選択された基本構造３０の一例を示し、図２（Ｃ）は、第２枝３４−２が選択された基本構造３０の一例を示す。
【００２４】
枝選択部２０は、２次元空間に表された曲線を符号化する場合、一例として、図２に示すような基本構造３０を用いてよい。本例に係る基本構造３０は、図２（Ａ）に示すように、２次元空間上に表された、幹３２と、２つの枝３４（第１枝３４−１、第２枝３４−２）とを有する。幹３２は、所定長の直線である。２つの枝３４は、所定長の直線（例えば幹３２と略同一の長さの直線）である。２つの枝３４は、一端が、幹３２の一端である中心端点３６と略同一の位置に配置される。第１枝３４−１は、幹３２との角度が所定の角度となる位置に配置される。第２枝３４−２は、幹３２との角度が所定の角度（例えば第１枝３４−１と幹３２との角度と略同角度）であり、第１枝３４−１とは異なる位置に配置される。例えば、第１枝３４−１と幹３２との角度および第２枝３４−２と幹３２との間の角度は、略１２０度であってよい。
【００２５】
また、本例に係る基本構造３０は、２次元空間上に表された、第１枝３４−１に対応する方向ベクトル４２（第１方向ベクトル４２−１）と、第２枝３４−２に対応する方向ベクトル４２（第２方向ベクトル４２−２）とを有する。第１方向ベクトル４２−１は、対応する第１枝３４−１が選択された場合における当該基本構造３０の指定方向を示し、第２方向ベクトル４２−２は、対応する第２枝３４−２が選択された場合における当該基本構造３０の指定方向を示す。第１方向ベクトル４２−１は、一例として、図２（Ｂ）に示すように、中心端点３６を通り、幹３２に対して所定の角度とされた位置に配置される。第２方向ベクトル４２−２は、一例として、図２（Ｃ）に示すように、中心端点３６を通り、幹３２に対して所定の角度（例えば、例えば第１方向ベクトル４２−１と幹３２との角度と略同角度）であり、第１方向ベクトル４２−１とは異なる位置に配置される。
【００２６】
さらに、本例に係る基本構造３０は、２つの枝３４のうちの一方に符号０が割り当てられ、他方に１が割り当てられる。符号装置１０は、このような基本構造３０を用いて２次元の曲線を符号化することにより、曲線の曲がり具合を０、１の２値で表した符号列を生成することができる。
【００２７】
本例に係る基本構造３０は、一例として、幹３２の長さ、幹３２の位置、幹３２の方向、２つの枝３４のそれぞれの長さ、２つの枝３４のそれぞれの幹３２に対する相対的な位置および方向、２つの方向ベクトル４２の幹３２に対する角度および方向、および、２つの枝３４のそれぞれに割り当てられた符号を含むデータにより表されてよい。符号装置１０は、本例に係る基本構造３０を表すデータを用いて、２次元座標上に表された曲線の曲がり具合を符号化してよい。
【００２８】
図３は、本実施形態に係る符号装置１０における符号化処理フローの一例を示す。図４（Ａ）はＳ１１において入力された曲線の一例（曲線５０）を示し、図４（Ｂ）はＳ１２において選択された代表点５２が追加された曲線５０を示し、図４（Ｃ）はＳ１３において生成された傾きベクトル５４が更に追加された曲線５０を示し、図４（Ｄ）はＳ１４において配置された基本構造３０が更に追加された曲線５０を示す。図５（Ａ）は基本構造３０および傾きベクトル５４の一例を示し、図５（Ｂ）はＳ１６において枝３４が選択された基本構造３０の一例を示し、図５（Ｃ）はＳ１７における方向ベクトル４２の調整処理の一例を示し、図５（Ｄ）はＳ１７の調整後の基本構造３０の一例を示し、図５（Ｅ）は調整後の当該基本構造３０および次の基本構造３０の一例を示し、図５（Ｆ）は枝３４が選択された次の基本構造３０の一例を示す。
【００２９】
まず、入力部１２は、符号化対象として与えられた曲線５０を入力する（Ｓ１１、図４（Ａ））。次に、代表点選択部１４は、曲線５０上における複数の代表点５２を選択する（Ｓ１２、図４（Ｂ））。次に、傾きベクトル生成部１６は、選択した複数の代表点５２のそれぞれに対応した複数の傾きベクトル５４を算出する（Ｓ１３、図４（Ｃ））。次に、配置部１８は、複数の代表点５２のそれぞれに対応させて、複数の基本構造３０を配置する（Ｓ１４、図４（Ｄ））。
【００３０】
次に、枝選択部２０および調整部２２は、複数の代表点５２のそれぞれに対応させて配置された複数の基本構造３０を、代表点５２の曲線５０上の並び順序に従って１ずつ選択する。そして、枝選択部２０および調整部２２は、選択した基本構造３０に対して、以下のステップＳ１６〜Ｓ１９を処理する（Ｓ１５、Ｓ２０）。
【００３１】
枝選択部２０は、選択した当該基本構造３０が有する複数の枝３４のうち、当該基本構造３０が配置された代表点５２における傾きベクトル５４との角度差が小さい１つの枝３４を選択する（Ｓ１６、図５（Ａ）、（Ｂ））。例えば、図５（Ａ）、（Ｂ）に示す例であれば、傾きベクトル５４と符号０が割り当てられた枝３４との角度よりも、傾きベクトル５４と符号１が割り当てられた枝３４との角度の方が小さいので、枝選択部２０は、符号１が割り当てられた枝３４を選択する。そして、枝選択部２０は、選択した枝３４に割り付けられた符号を記憶する。例えば、図５（Ａ）、（Ｂ）に示す例であれば、枝選択部２０は、符号１を記憶する。
【００３２】
次に、調整部２２は、ステップＳ１６において選択した枝３４に対応付けられた方向ベクトル４２が、当該基本構造３０が配置された代表点５２における傾きベクトル５４と略並行となるように、当該基本構造３０を回転させる（Ｓ１７、図５（Ｃ）、（Ｄ））。次に、調整部２２は、次に選択される基本構造３０の幹３２の方向が、当該基本構造３０におけるステップＳ１６において選択された枝３４の方向と略並行となるように、次に選択される基本構造３０の方向を調整する（Ｓ１８、図５（Ｅ））。なお、調整部２２は、１番目の代表点５２に配置された基本構造３０については、幹３２が予め定められた方向となるように配置してよい。
【００３３】
次に、調整部２２は、次に選択される基本構造３０の複数の枝３４のそれぞれに対して、符号を割り当てる（Ｓ１９）。この場合において、調整部２２は、当該基本構造３０における複数の枝３４に対する符号の割り当てと異なる対応関係となるように、符号を割り当てる。すなわち、調整部２２は、現在選択している基本構造３０において符号０が割り当てられている枝３４に対しては、次に選択される基本構造３０において符号１を割り当て、現在選択している基本構造３０において符号１が割り当てられている枝３４に対しては、次の代表点５２に配置された基本構造３０において符号０を割り当てる。なお、調整部２２は、１番目の代表点５２に配置された基本構造３０については、複数の枝３４に対して予め定められた符号を割り当ててよい。
【００３４】
そして、ステップＳ１９の処理を終えると、枝選択部２０は、次の代表点５２に配置された基本構造３０を選択して、枝選択処理（Ｓ１６）に処理を戻す（Ｓ２０、Ｓ１５、図５（Ｆ））。最後の代表点５２に配置された基本構造３０についての処理が完了すると（Ｓ２０）、次に、生成部２４は、枝選択部２０により選択された枝３４に割り付けられた符号に基づき、曲線の曲がり具合を表すデータを生成する（Ｓ２１）。生成部２４は、一例として、曲線に沿って順番にそれぞれの基本構造３０について選択された枝３４に割り当てられた符号を連結して得られるデータを出力してよい。これにより、生成部２４は、２次元の曲線の曲がり具合を、２値（０、１）で表した符号列を生成することができる。
【００３５】
以上のような符号装置１０によれば、曲線の曲がり具合を精度よく表す符号を、生成することができる。なお、符号装置１０は、複数の代表点５２について代表点選択（Ｓ１２）、傾きベクトル生成（Ｓ１３）および基本構造配置（Ｓ１４）を行った後に、ステップＳ１６〜Ｓ２０のループ処理を行っているが、これに代えて、枝３４の選択（Ｓ１６）を終了した後に、次の１つの代表点５２の選択、選択した当該次の１つの代表点５２の傾きベクトル５４の生成および選択した当該次の１つの代表点５２に対する基本構造３０の配置を行ってもよい。
【００３６】
図６は、代表点が離散的に選択された曲線５０を符号化した一例を示す。代表点選択部１４は、予め定められた規則に従い、曲線５０上の代表点を選択する。代表点選択部１４は、一例として、曲線５０における一端から予め定められた間隔毎に代表点を選択してよい。また、代表点選択部１４は、予め定められた規則に従っていれば、図６に示すように、代表点の間隔を一定としなくてよい。符号装置１０は、代表点を選択する間隔をより広くすることにより、符号量が少なく、比較的に大まかな曲がり具合を簡単に比較することができる符号を生成することができる。
【００３７】
図７（Ａ）および（Ｂ）は、幹３２および枝３４に一致しない角度の方向ベクトル４２を有する基本構造３０の一例を示し、図７（Ｃ）は、図７（Ａ）、（Ｂ）に示す基本構造３０が配置された曲線５０の一例を示し、図７（Ｄ）は、図７（Ｃ）のように配置された基本構造３０により形成される枝軌跡５６を示し、図７（Ｅ）は、図７（Ｃ）のように配置された基本構造３０により符号化された符号列を示す。
【００３８】
符号装置１０は、代表点を選択する間隔をより短くすることにより、より緻密に曲線５０の曲がり具合を表す符号を生成することができる。符号装置１０は、一例として、幹３２および枝３４の長さを略同一とし、代表点を選択する間隔を幹３２の長さと略同一または幹３２の長さ以下としてよい。この場合において、符号装置１０は、方向調整された後の基本構造３０における選択された枝３４を、代表点の順序通りに連結することにより、曲線５０を近似した枝軌跡５６を生成することができる。符号装置１０は、一例として、方向調整された後の基本構造３０における選択された枝３４の長さ、位置および方向を示すデータに基づき枝軌跡５６を表すデータを生成してよい。
【００３９】
図８（Ａ）および（Ｂ）は、枝３４に一致した角度の方向ベクトル４２を有する基本構造３０の一例を示し、図８（Ｃ）は、図８（Ａ）、（Ｂ）に示す基本構造３０が配置された曲線５０の一例を示し、図８（Ｄ）は、図８（Ｃ）のように配置された基本構造３０により形成される枝軌跡５６を示し、図８（Ｅ）は、図８（Ｃ）のように配置された基本構造３０により符号化された符号列を示す。
【００４０】
符号装置１０は、枝３４の方向と、当該枝３４に対応する方向ベクトル４２の方向とを一致させた基本構造３０を用いてもよい。この場合、方向調整された後の基本構造３０における選択された枝３４の方向は、曲線５０の方向に近づく。従って、符号装置１０は、枝３４の方向と、当該枝３４に対応する方向ベクトル４２の方向とを近づけた基本構造３０を用いることにより、曲線５０の比較的に細かい変化に応じて変化する符号を生成することができる。このことから、符号装置１０は、このような基本構造３０を用いて符号化することにより、比較的に細かい曲がり具合まで比較することができる符号を生成することができる。
【００４１】
図９（Ａ）および（Ｂ）は、幹３２に一致した角度の方向ベクトル４２を有する基本構造３０の一例を示し、図９（Ｃ）は、図９（Ａ）、（Ｂ）に示す基本構造３０が配置された曲線５０の一例を示し、図９（Ｄ）は、図９（Ｃ）のように配置された基本構造３０により形成される枝軌跡５６を示し、図９（Ｅ）は、図９（Ｃ）のように配置された基本構造３０により符号化された符号列を示す。
【００４２】
符号装置１０は、幹３２の方向と、当該枝３４に対応する方向ベクトル４２の方向とを一致させた基本構造３０を用いてもよい。この場合、方向調整された後の基本構造３０における選択された枝３４の方向は、曲線５０の方向から遠ざかる。従って、符号装置１０は、幹３２の方向と、当該枝３４に対応する方向ベクトル４２の方向とを近づけた基本構造３０を用いることにより、曲線５０の比較的に細かい変化によっては変化しない符号を生成することができる。このことから、符号装置１０は、このような基本構造３０を用いて符号化することにより、比較的に大まかな曲がり具合を簡単に比較することができる符号を生成することができる。
【００４３】
図１０（Ａ）および図１０（Ｂ）は、３次元空間に表された曲線の曲がり具合を符号化することが可能な基本構造３０の一例を示し、図１０（Ｃ）は、第１枝３４−１が選択された基本構造３０の一例を示し、図１０（Ｄ）は、第２枝３４−２が選択された基本構造３０の一例を示す。
【００４４】
本例に係る基本構造３０は、図１０（Ａ）および（Ｂ）に示すように、３次元空間上に表された、幹３２と、２つの枝３４（第１枝３４−１、第２枝３４−２）とを有する。幹３２は、所定長の棒状の物体である。幹３２は、当該幹３２の軸周りの予め定められた位置の角度を示す幹回転位置指標７２が設けられている。
【００４５】
２つの枝３４は、所定長の棒状の物体（例えば幹３２と略同一の長さの形状の物体）である。２つの枝３４は、長手方向の一端が、幹３２の一端である中心端点３６に接続される。第１枝３４−１は、幹３２との角度が所定の角度となる位置に配置される。第２枝３４−２は、幹３２との角度が第１枝３４−１と略同角度で第１枝３４−１と異なる位置に配置される。例えば、第１枝３４−１と幹３２との角度および第２枝３４−２と幹３２との間の角度は、略１２０度であってよい。また、第１枝３４−１と第２枝３４−２との角度は、略９０度であってよい。さらに、２つの枝３４は、当該枝３４の軸周りの予め定められた位置の角度を示す指定回転位置指標７４（第１指定回転位置指標７４−１、第２指定回転位置指標７４−２）が設けられている。
【００４６】
また、本例に係る基本構造３０は、３次元空間上に表された、第１枝３４−１に対応する方向ベクトル４２（第１方向ベクトル４２−１）と、第２枝３４−２に対応する方向ベクトル４２（第２方向ベクトル４２−２）とを有する。第１方向ベクトル４２−１は、図１０（Ｃ）に示すように、中心端点３６を通り、幹３２および第１枝３４−１に対してそれぞれ予め定められた角度とされた位置に配置される。第２方向ベクトル４２−２は、図１０（Ｄ）に示すように、中心端点３６を通り、幹３２および第２枝３４−２に対してそれぞれ予め定められた角度とされた位置に配置される。第１方向ベクトル４２−１は、対応する第１枝３４−１が選択された場合における当該基本構造３０の指定方向を示し、第２方向ベクトル４２−２は、対応する第２枝３４−２が選択された場合における当該基本構造３０の指定方向を示す。
【００４７】
さらに、本例に係る基本構造３０は、図１０（Ｃ）、（Ｄ）に示すように、２つの枝３４のうちの一方に符号０が割り当てられ、他方に１が割り当てられる。符号装置１０は、このような基本構造３０を用いて３次元の曲線を符号化することにより、曲線の曲がり具合を０、１の２値で表した符号列を生成することができる。
【００４８】
本例に係る基本構造３０は、一例として、幹３２の長さ、幹３２の位置、幹３２の方向、幹回転位置指標７２により指定される幹３２の軸周りの指定角度、２つの枝３４のそれぞれの長さ、２つの枝３４のそれぞれの幹３２に対する相対的な位置および方向、指定回転位置指標７４により指定されるそれぞれの枝３４の軸周りの角度、２つの方向ベクトル４２の幹３２および枝３４に対する角度および方向、および、２つの枝３４のそれぞれに割り当てられた符号を含むデータにより表されてよい。符号装置１０は、本例に係る基本構造３０を表すデータを用いて、２次元座標上に表された曲線の曲がり具合を符号化してよい。
【００４９】
図１１（Ａ）および図１１（Ｂ）は、図１０に示した基本構造３０の方向および回転角の調整の一例を示す。調整部２２は、ある代表点に配置された基本構造３０の枝３４が選択されて当該基本構造３０の位置の調整がされた後、次の代表点に配置された基本構造３０の枝３４を選択する前に、次の代表点の基本構造３０の方向および回転角を、当該ある代表点に配置された基本構造３０に合せて調整する。
【００５０】
図１０に示す基本構造３０を用いた場合、調整部２２は、次の代表点に配置された基本構造３０の幹３２の方向を、選択された枝３４と略並行となるように調整する。さらに、調整部２２は、幹回転位置指標７２により示された幹３２の軸周りの回転位置と、指定回転位置指標７４により示された選択された枝３４の軸周りの回転位置とが略一致するように、次の代表点に配置された基本構造３０における幹３２の軸周りの回転角を調整する。
【００５１】
これにより、調整部２２は、次の代表点に配置された基本構造３０の位置を、３次元空間において一意に定めることができる。従って、図１０に示す基本構造３０を用いた符号装置１０によれば、３次元の曲線の曲がり具合を、２値（０、１）の符号列に符号化することができる。
【００５２】
図１２（Ａ）および図１２（Ｂ）は、図２の基本構造３０の一例としての三角タイル８０を示し、図１２（Ｃ）は、三角タイル８０を用いて曲線５０を符号化した一例を示す。符号装置１０は、基本構造３０の一例としての三角タイル８０を用いて、２次元の曲線を符号化してよい。三角タイル８０は、底辺８２と、２つの側辺８４（第１側辺８４−１および第２側辺８４−２）とを有する正三角形である。底辺８２は、鉛直方向が幹３２の方向に略一致する。第１側辺８４−１は、鉛直方向が一方の枝３４（第１枝３４−１）の方向に略一致する。第２側辺８４−２は、鉛直方向が他方の枝３４（第２枝３４−２）の方向に略一致する。そして、三角タイル８０の中心は、幹３２および２つの枝３４の接続点に略一致してよい。
【００５３】
配置部１８は、このような三角タイル８０を、曲線５０上の複数の代表点のそれぞれに配置する。そして、枝選択部２０は、代表点における傾きベクトル５４の角度とより近い角度の一方の側辺８４を選択し、選択した側辺８４に対応する枝３４に割り付けられている符号を記憶する。これにより、符号装置１０によれば、２次元の曲線の曲がり具合を、２値（０、１）の符号列に符号化することができる。さらに、符号装置１０は、方向調整された後の三角タイル８０における選択された側辺８４の軌跡に基づき、曲線５０の近似曲線を生成してもよい。
【００５４】
図１３（Ａ）および図１３（Ｂ）は、図１０の基本構造３０の一例としての四面体ブロック９０を示し、図１３（Ｃ）は、四面体ブロック９０を用いて曲線５０を符号化した一例を示す。符号装置１０は、基本構造３０の一例として四面体ブロック９０を用いて、３次元の曲線を符号化してよい。四面体ブロック９０は、底面９２と、２つの側面９４（第１側面９４−１および第２側面９４−２）と、裏面９６とを有する四面体である。四面体ブロック９０の各面は、３辺の長さの比が２：√３：√３とされ、同一形状の三角形となっている。
【００５５】
底面９２は、鉛直方向が幹３２の方向に略一致する。第１側面９４−１は、鉛直方向が一方の枝３４（第１枝３４−１）の方向に略一致する。第２側面９４−２は、鉛直方向が他方の枝３４（第２枝３４−２）の方向に略一致する。第１側面９４−１は、２：√３：√３の３辺のうち√３に対応する１つの辺を介して底面９２と接続し、２に対応する辺を介して第２側面９４−２と接続する。第２側面９４−２は、２：√３：√３の３辺のうち√３に対応する１つの辺を介して底面９２と接続し、２に対応する辺を介して第１側面９４−１と接続する。
【００５６】
さらに、四面体ブロック９０は、２つの選択辺９８（第１選択辺９８−１および第２選択辺９８−２）を有する。第１選択辺９８−１は、第１枝３４−１に対応する辺であり、四面体ブロック９０が有する辺のうちの底面９２および第１側面９４−１に含まれない辺である。第２選択辺９８−２は、第２枝３４−２に対応する辺であり、四面体ブロック９０が有する辺のうちの底面９２および第２側面９４−２に含まれない辺である。
【００５７】
配置部１８は、このような四面体ブロック９０を、曲線５０上の複数の代表点のそれぞれに配置する。そして、枝選択部２０は、代表点における傾きベクトル５４の角度とより近い角度の一方の選択辺９８を選択し、選択した選択辺９８に対応する枝３４に割り付けられている符号を記憶する。これにより、符号装置１０によれば、３次元の曲線の曲がり具合を、２値（０、１）の符号列に符号化することができる。さらに、符号装置１０は、方向調整された後の四面体ブロック９０の軌跡により形成された形状を記憶することにより、曲線５０の近似形状を生成することができる。
【００５８】
図１４は、変形例に係る符号装置１０の構成を示す。変形例に係る符号装置１０は、分割部２０２と、符号化部２０４と、部分符号生成部２０６と、全体符号生成部２０８とを備える。分割部２０２は、符号化対象として与えられた所定の曲線を、隣接する部分曲線同士が少なくとも一部分重なるように複数の部分曲線に分割する。分割部２０２は、一例として、２次元または３次元空間座標上に表された曲線データを、隣接する部分が互いに重なる２次元または３次元空間座標上に表された部分曲線を表す複数の曲線データに、分割してよい。
【００５９】
符号化部２０４は、図１に示した符号装置１０と略同一の構成および機能を採り、分割部２０２により分割された複数の部分曲線のそれぞれを、曲がり具合を表す例えば二値数列で表される符号に符号化する。ここで、符号化部２０４は、基本構造３０における選択された枝３４と次の基本構造３０の幹３２とが重なるように複数の基本構造３０を連結して、部分曲線の曲がり具合を表すデータを生成する。さらに、符号化部２０４は、１つの部分曲線に対して、複数の曲がり具合を表すデータを生成する。符号化部２０４は、一例として、１つの部分曲線に対して、１番目の代表点の選択位置、１番目の代表点に配置される基本構造３０の角度等を変えて符号化した複数の曲がり具合を表すデータを生成してよい。
【００６０】
符号化部２０４は、部分曲線について生成された複数の曲がり具合を表すデータに基づいて、当該部分曲線を表す部分符号を生成する。符号化部２０４は、一例として、１つの部分曲線について生成された複数の曲がり具合を表すデータを、１つのグループにグループ化した部分符号を生成してよい。部分符号生成部２０６は、複数の部分曲線に対応して得られた複数の部分符号に基づいて、所定の曲線の形状を表す全体符号を生成する。部分符号生成部２０６は、一例として、所定の曲線における部分曲線の位置が対応付けられた部分符号を、全体符号として生成してよい。
【００６１】
符号化部２０４は、基本構造３０における選択された枝３４と次の基本構造３０の幹３２とが重なるように複数の基本構造３０を連結して１つの曲線の全体を符号化した場合、任意の曲線部分の曲がり具合を表す符号は、当該任意の曲線部分の前部分がどのような曲がり具合になっているかによって異なる。このため、複数の基本構造３０を連結した場合、符号装置１０は、曲線の一部分同士の類似度を算出することができる符号を生成することができない。しかしながら、本変形例に係る符号装置１０によれば、１つの曲線における各部分を複数の符号列に符号化するので、複数の基本構造３０を連結した場合であっても、曲線における一部分の類似度を算出することができる符号を生成することができる。
【００６２】
図１５は、本実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。本実施形態に係るコンピュータ１９００は、ホスト・コントローラ２０８２により相互に接続されるＣＰＵ２０００、ＲＡＭ２０２０、グラフィック・コントローラ２０７５、及び表示装置２０８０を有するＣＰＵ周辺部と、入出力コントローラ２０８４によりホスト・コントローラ２０８２に接続される通信インターフェイス２０３０、ハードディスクドライブ２０４０、及びＣＤ−ＲＯＭドライブ２０６０を有する入出力部と、入出力コントローラ２０８４に接続されるＲＯＭ２０１０、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０を有するレガシー入出力部とを備える。
【００６３】
ホスト・コントローラ２０８２は、ＲＡＭ２０２０と、高い転送レートでＲＡＭ２０２０をアクセスするＣＰＵ２０００及びグラフィック・コントローラ２０７５とを接続する。ＣＰＵ２０００は、ＲＯＭ２０１０及びＲＡＭ２０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０７５は、ＣＰＵ２０００等がＲＡＭ２０２０内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０８０上に表示させる。これに代えて、グラフィック・コントローラ２０７５は、ＣＰＵ２０００等が生成する画像データを格納するフレーム・バッファを、内部に含んでもよい。
【００６４】
入出力コントローラ２０８４は、ホスト・コントローラ２０８２と、比較的高速な入出力装置である通信インターフェイス２０３０、ハードディスクドライブ２０４０、ＣＤ−ＲＯＭドライブ２０６０を接続する。通信インターフェイス２０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ２０４０は、コンピュータ１９００内のＣＰＵ２０００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ２０６０は、ＣＤ−ＲＯＭ２０９５からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。
【００６５】
また、入出力コントローラ２０８４には、ＲＯＭ２０１０と、フレキシブルディスク・ドライブ２０５０、及び入出力チップ２０７０の比較的低速な入出力装置とが接続される。ＲＯＭ２０１０は、コンピュータ１９００が起動時に実行するブート・プログラムや、コンピュータ１９００のハードウェアに依存するプログラム等を格納する。フレキシブルディスク・ドライブ２０５０は、フレキシブルディスク２０９０からプログラム又はデータを読み取り、ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供する。入出力チップ２０７０は、フレキシブルディスク・ドライブ２０５０や、例えばパラレル・ポート、シリアル・ポート、キーボード・ポート、マウス・ポート等を介して各種の入出力装置を接続する。
【００６６】
ＲＡＭ２０２０を介してハードディスクドライブ２０４０に提供されるプログラムは、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、記録媒体から読み出され、ＲＡＭ２０２０を介してコンピュータ１９００内のハードディスクドライブ２０４０にインストールされ、ＣＰＵ２０００において実行される。
【００６７】
コンピュータ１９００にインストールされ、コンピュータ１９００を符号装置１０として機能させるプログラムは、入力モジュールと、代表点選択モジュールと、傾きベクトルモジュールと、配置モジュールと、枝選択モジュールと、調整モジュールと、生成モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、入力部１２、代表点選択部１４、傾きベクトル生成部１６、配置部１８、枝選択部２０、調整部２２および生成部２４としてそれぞれ機能させる。
【００６８】
また、コンピュータ１９００にインストールされ、コンピュータ１９００を変形例に係る符号装置１０として機能させるプログラムは、分割モジュールと、符号化モジュールと、部分符号生成モジュールと、全体符号生成モジュールとを備える。これらのプログラム又はモジュールは、ＣＰＵ２０００等に働きかけて、コンピュータ１９００を、分割部２０２、符号化部２０４、部分符号生成部２０６および全体符号生成部２０８としてそれぞれ機能させる。
【００６９】
以上に示したプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク２０９０、ＣＤ−ＲＯＭ２０９５の他に、ＤＶＤやＣＤ等の光学記録媒体、ＭＯ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ１９００に提供してもよい。
【００７０】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【００７１】
【図１】本発明の実施形態に係る符号装置１０の構成を示す。
【図２】本発明の実施形態に係る基本構造３０の一例を示す。
【図３】本発明の実施形態に係る符号装置１０における符号化処理フローの一例を示す。
【図４】図３のＳ１１〜Ｓ１４の処理の一例を示す。
【図５】図３のＳ１６〜Ｓ１９の処理の一例を示す。
【図６】代表点が離散的に選択された曲線５０を符号化した一例を示す。
【図７】幹３２および枝３４に一致しない角度の方向ベクトル４２を有する基本構造３０の一例を示す。
【図８】枝３４に一致した角度の方向ベクトル４２を有する基本構造３０の一例を示す。
【図９】幹３２に一致した角度の方向ベクトル４２を有する基本構造３０の一例を示す。
【図１０】３次元空間に表された曲線の曲がり具合を符号化することが可能な基本構造３０の一例を示す。
【図１１】（Ａ）および（Ｂ）は、図１０に示した基本構造３０の方向および回転角の調整の一例を示す。
【図１２】（Ａ）および（Ｂ）は、図２の基本構造３０の一例としての三角タイル８０を示し、（Ｃ）は、三角タイル８０を用いて曲線５０を符号化した一例を示す。
【図１３】（Ａ）および図１３（Ｂ）は、図１０の基本構造３０の一例としての四面体ブロック９０を示し、（Ｃ）は、四面体ブロック９０を用いて曲線５０を符号化した一例を示す。
【図１４】変形例に係る符号装置１０の構成を示す。
【図１５】本発明の実施形態に係るコンピュータ１９００のハードウェア構成の一例を示す。
【符号の説明】
【００７２】
１０  符号装置
１２  入力部
１４  代表点選択部
１６  傾きベクトル生成部
１８  配置部
２０  枝選択部
２２  調整部
２４  生成部
３０  基本構造
３２  幹
３４  枝
３６  中心端点
４２  方向ベクトル
５０  曲線
５２  代表点
５４  傾きベクトル
５６  枝軌跡
７２  幹回転位置指標
７４  指定回転位置指標
８０  三角タイル
８２  底辺
８４  側辺
９０  四面体ブロック
９２  底面
９４  側面
９６  裏面
９８  選択辺
２０２  分割部
２０４  符号化部
２０６  部分符号生成部
２０８  全体符号生成部
１９００  コンピュータ
２０００  ＣＰＵ
２０１０  ＲＯＭ
２０２０  ＲＡＭ
２０３０  通信インターフェイス
２０４０  ハードディスクドライブ
２０５０  フレキシブルディスク・ドライブ
２０６０  ＣＤ−ＲＯＭドライブ
２０７０  入出力チップ
２０７５  グラフィック・コントローラ
２０８０  表示装置
２０８２  ホスト・コントローラ
２０８４  入出力コントローラ
２０９０  フレキシブルディスク
２０９５  ＣＤ−ＲＯＭ
【図１】
2008015710.tif 000003
【図２】
2008015710.tif 000004
【図３】
2008015710.tif 000005
【図４】
2008015710.tif 000006
【図５】
2008015710.tif 000007
【図６】
2008015710.tif 000008
【図７】
2008015710.tif 000009
【図８】
2008015710.tif 000010
【図９】
2008015710.tif 000011
【図１０】
2008015710.tif 000012
【図１１】
2008015710.tif 000013
【図１２】
2008015710.tif 000014
【図１３】
2008015710.tif 000015
【図１４】
2008015710.tif 000016
【図１５】
2008015710.tif 000017