(57)【要約】  ２D形状を分類する方法は、類似形状群及び非類似形状群を備えた、対象形状の訓練データセットを作成する工程と、類似形状群から平均形状を計算する工程と、データベース内の形状全てを平均形状にアラインさせる工程と、その距離に基づいて２つのクラスタに形状を分類する工程とを備える。
2008528949.tif 000002
【特許請求の範囲】
【請求項１】
2次元形状を分類する方法であって、
類似形状群及び非類似形状群から成る訓練形状データセットを作成する工程と、前記類似形状群から平均形状を計算する工程と、
前記訓練形状データセット内の各形状を前記平均形状にアラインさせる工程と、
前記訓練形状データセット内の形状毎に類似度距離を生成する工程と、
類似度距離に基づいて前記類似形状群又は前記非類似形状群に前記訓練形状データセット内の各形状を分類する工程とを備える方法。
【請求項２】
請求項１記載の方法であって、平均形状を計算する工程は、
前記類似形状群からの一形状をテンプレート形状として識別する工程と、
前記類似形状群内の形状を前記テンプレート形状にアラインさせる工程と、
平均形状を生成する工程と、
前記平均形状と、前記類似形状群内の形状との間の合計距離を判定する工程と、
前記合計距離が最小の場合に前記平均形状を出力する工程とを備える方法。
【請求項３】
請求項２記載の方法であって、出力する工程が、
前記平均形状を前記テンプレート形状として識別する工程、並びに、
前記合計距離が最小になるまで、アラインさせる工程、生成する工程及び判定する工程を繰り返す工程
によって達成される方法。
【請求項４】
請求項1記載の方法であって、前記訓練形状データセット内の各形状を前記平均形状にアラインさせる工程が、
形状の多角形近似を生成する工程と、
回転関数を用いて、前記多角形近似を前記平均形状にアラインさせる工程とを備える方法。
【請求項５】
請求項1記載の方法であって、前記訓練形状データセット内の各形状を分類する工程が、
前記訓練データセット内の形状の類似度距離を用いて距離分布を生成する工程と、
前記形状を分類する距離分布から分類閾値を識別する工程とを備える方法。
【請求項６】
請求項5記載の方法であって、
新たな形状にアクセスする工程と、
前記新たな形状を分類する工程と、
前記平均形状及び前記分類閾値を前記新たな形状を用いて更新する工程とを更に備える方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に形状解析の手法に関し、特に画像内の２D形状を自動的に分類する手法に関する。
【背景技術】
【０００２】
２次元（２D）形状をその位置、サイズ及び向きにかかわらず分類することは、コンピュータ視覚及びパターン認識において重要な課題である。その適用分野は、多くの分野（血球、癌及び染色体の分類、産業用検査、目標認識、医療画像認識、シーン解析や、生体系のモデリングなど）に広がっている。一般に、形状分類は、形状の境界の情報を解析することによって形状を比較し、認識する処理である。これは人間にとっては簡単な作業であるが、コンピュータにとっては、特に、対象がスケーリングされ、回転させられ、かつ／又は平行移動させられた後は、極めて困難な作業である。よって、汎用的な対象の分類、認識又は取り出しの目的で形状を対象とすることは、現在の研究の活発な分野である。
【０００３】
最近の文献はこの話題に対処しており、種々の画像処理手法が施されている。前述の手法は基本的に２つの手法に分類することが可能である。
【０００４】
第１の手法は、形状インスタンスを共通空間に投影し、次いで、投影空間上で分類を実現することを必要とする。例えば、フ―リエ記述子（E.  Persoonらによる「shape  discrimination  using  Fourier  descriptors,  IEEE  Trans.  Syst.  Man.  Cybern,  vol.  7,  p170-179,  1977」）、不変モーメント（F.  Zakariaらによる「Fast  algorithm  for  computation  of  moment  invariants,  Pattern  Recognition,  vol.  20,  p639-643,  1987」）、自己回帰モデル（S.R.  Duboisらによる「An  autoregressive  model  approach  to  two-dimensional  shape  classification,  IEEE  Trans.  Pattern  Analysis  and  Machine  Intelligence,  vol.8  pp55-66,  1986」）、及び主成分解析（「METHOD  FOR  CHARACTERISING  SHAPES  IN  MEDICAL  IMAGES」と題する米国特許出願公報第2002／0164060号明細書）。
【０００５】
前述の投影ベースの手法は、利点として、平行移動及び回転とは無関係であることがある。しかし、欠点は、投影変換が1対１の対応関係でないので、固有の情報損失を表すことである。すなわち、投影空間内の一点が、視覚的な外観がかなり異なり得るいくつかの形状に対応し得る。したがって、前述の手法に基づいた形状分類は、誤った結果をもたらし得る。
【０００６】
第２の手法は、形状境界に沿った一組の目印点を位置特定する工程と、対応する目印間の距離尺度を規定する工程と、距離ベースのクラスタリングを行う工程とを備えている。そういうものとして、形状分類は、数多くの解決策が提案されている汎用的なクラスタリング問題に変えられる。例えば、M.  Dutaらは、平均アラインメント・エラー（MAE）を距離として用いて、形状の差を測定し、MAEに基づいて形状を分類する方法を提示している（M.  Dutaらによる「Automatic  Construction  of  2D  Shape  Models,  IEEE  Trans.  on  Pattern  Analysis  and  Machine  Intelligence,  vol.  23,  no.  5,  p433-446,  2001」）。「METHOD  AND  APPARATUS  FOR  AUTOMATIC  SHAPE  CHARACTERIZATION」と題する米国特許第6,611,630号明細書、及び「METHOD  AND  APPARATUS  FOR  IMAGE  REGISTRATION」と題する米国特許第6,009,212号明細書は、特徴付ける母集団の平均形状に対する最良のマッチ確率に基づいて形状を分類するための方法に関する。この手法の制約は、雑音、及び構成員間のばらつきが理由で形状の目印間の対単位の対応関係を実際には達成することが難しいことである。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来技術の欠点及び制約を前提とすれば、形状分類の、単純で効率的で高精度の手法を求める方法に対する必要性が存在している。
【０００８】
本発明の目的は、2D形状分類の自動化方法を提供することである。
【課題を解決するための手段】
【０００９】
本発明の一局面によれば、この目的は、２D形状を分類する自動化方法を提供することによって達成される。方法は、いくつかの工程を含む。訓練データセットが、対象形状について作成される。訓練セットは、２つのデータ群（類似形状群及び非類似形状群）を含む。訓練データセット内の形状毎の多角形近似が生成され、類似形状群から平均形状が計算される。データベース内の形状が、平均形状に合わせられ、その類似度距離が出力される。類似度距離の分布が得られ、その距離に基づいて形状が２つのクラスタに分類される。
【００１０】
本発明は、いくつかの利点を有するものとみなされる。例えば、方法は、平均形状、及び類似度距離に関連した閾値によって対象形状を特徴付ける。計算量がO（mnlog（mn））の下で制御されるため、形状分類は効率的である。ここで、mは平均形状上の目印の数であり、nは形状インスタンス上の目印の数である。形状分類はロバストである。形状アライメント中に、目印の対単位の対応関係が何ら必要でなく、目印の数も異なり得るからである。更に、平均形状に対する形状インスタンスの回転角を形状アラインメント後に設けることが可能なため、向きの補正が簡単になる。
【発明を実施するための最良の形態】
【００１１】
本発明の前述並びに他の目的、特徴及び利点は、添付図面に示す、本発明の実施例の以下のより具体的な説明から明らかであろう。添付図面の構成要素は、必ずしも相互に縮尺通りでない。
【実施例】
【００１２】
以下は、本発明の好ましい実施例の詳細な説明であり、いくつかの添付図面のそれぞれにおいて同じ参照符号が同じ構造要素を識別する添付図面を参照する。
【００１３】
本発明は、画像内の2次元（２D）形状を自動的に分類する方法を開示している。本発明による方法のフローチャートを全体的に図１Aに示す。図１Aに示すように、方法は４つの工程を含む。まず、２つの群データ（類似形状群及び非類似形状群）を含む、対象形状の訓練データセット／データベースが作成される（工程１０）。次いで、類似形状群を特徴付けるための平均形状が計算される（工程１１）。次に、データベース内の形状が、平均形状に合わせられ、その類似度距離が算出される（工程１２）。最後に、形状を２つのクラスタ（類似及び非類似）に分類するために類似度距離の分布を得て、用いる（工程１３）。
【００１４】
図１Bのフローチャートに示す更なる実施例では、平均形状の計算に先行して更なる工程を施すことが可能である（工程１１）。更なる工程（工程１４）は、訓練データセットにおける形状毎の多角形近似の生成であり、以下により具体的に説明する。
【００１５】
図２は、対象形状（すなわち、目標形状）が、脳画像から抽出された槽形状である例示的な訓練セットを示す。訓練データセットは、２つの形状タイプ（類似形状及び非類似形状）を手作業で選択することによって作成される。類似形状は、同じ対象タイプを表し、よって、高い類似度を有するようにみえる。この例では、類似群からの形状は全て、図２A乃至図２Kに示すような、脳画像内の槽から抽出される。しかし、雑音、ポーズ、及び分割エラー、並びに、構成員間の性質のばらつきのために形状のばらつきがそれらのうちで存在し得る。類似形状と比較すれば、非類似形状は図2L乃至2Uに示すように、全く異なる対象タイプ（例えば、心室、足、頭蓋骨、手や同様なもの）から抽出される。したがって、それらは、多種の形状を表す。訓練データセットにおいて2つの形状群を有することの動機づけは、対象形状の特徴、及び他の形状との区別に焦点を当てることによって分類の課題を単純にすることである。頑健な形状分類を促進するために、データセット内の形状は、変動する向き、位置及びスケールによって生起し得る。
【００１６】
工程１４では、境界の多角形近似が、形状を表すよう生成される。多角形によって形状を解釈することの利点は、情報損失を削減しながら、形状の単純な記述を提供することである。本発明の一実施例によれば、多角形近似は、形状から抽出される、サイン点、及びサンプリングされた点の組を接続することによって生成することが可能である。サイン点は、形状の顕著な特徴を表す点（高い曲率を備える点や、特定の位置にある点など）である。サンプリングされた点は、特定の基準によって、サイン点間にある点である。
【００１７】
1つの基準は、形状の重心を求め、重心から形状境界まで任意の半径を描き、次いで、時計回りに360/n度の等間隔で半径を移動させることによって境界に沿って一組のサンプリング点を配置することである。結果として生じる形状は、
【００１８】
【数１】
2008528949.tif 000003
として表すことが可能である。ここで、rθi（I＜i＜n）は、i番目の半径と形状境界との間の交差によって得られるサンプリングされた点である。pjはサイン点である。図３Aは、この基準によって生成される多角形近似を表す。
【００１９】
別の基準は、サイン点間のいくつかの等距離点（vdi）を埋めることによって、サンプリングされた点を選択することである。形状は、
【００２０】
【数２】
2008528949.tif 000004
によって表すことが可能である。図３Bは、結果の多角形近似を表す。
【００２１】
形状境界の多角形近似を生成するために、本発明は、上記手法を用いることに限定されない。顕著な情報を失うことなく、結果多角形が形状を正しく近似する他の既知のアルゴリズムを用いることが可能である。
【００２２】
形状類似度を測定するために、２つの形状をできる限り厳密にアラインさせる。本発明の実施例によれば、形状の類似度尺度のベースとして回転関数を用いる方法が提供される。２つの形状の多角形近似を前提とすれば、それらの距離は、２つの多角形の回転関数θ(s)から計算される。回転関数、又は累積角度関数は、形状近似上の基準点Oからのアーク長sの関数として、反時計回りのタンジェントの角度を測定することによって多角形を表す。それは、行われる回転をトラッキングする（例えば、反時計回りの回転によって増加し、時計回りの回転によって減少する）。一般性を確実にするために、各多角形の周囲長は、1に再スケーリングすることが可能である。よって、単純な閉輪郭の場合、θ（s）はθ（0）から始まり（輪郭に沿った特徴的な点(differential  point)に基準点0が配置されるものとする）、θ（1）=θ（0）+2πに増加する。
【００２３】
回転関数を形状類似度測定に特に適したものにする特性がいくつか存在している。第１に、それは、多角形の区分単位で一定であり、それによって、計算が特に簡単で高速になる。第２に、関数θ（s）は、定義に従って、多角形の平行移動及びスケーリングの下で不変である。第３に、角度θにわたる多角形の回転は、量θを有する、関数の垂直シフトに対応する一方で、多角形の周囲に沿って量t∈［0,1］だけ基準点0の位置を変えることは、関数θ（s）の巡回シフトをもたらす。
【００２４】
Tp及びSpを、テンプレート形状T及び形状インスタンスSの多角形近似とする。図４B及び図４Dは、図４A及び図４Cそれぞれに示す２つの形状の回転関数を示す。X軸は形状の周囲に対応し、Y軸は回転角を表す。Tp及びSpの類似度は、
【００２５】
【数３】
2008528949.tif 000005
によって定義されるような、回転関数θTp(s)と回転関数θSp(s)との間の最小L2距離を求めることによって測定することが可能である。ここで、tは、多角形に沿った基準点の位置を表し、θは多角形の回転に対応する。Arkinら(E.  M.  Arkin,  L.  P.  Chew,  D.  P.  Huttenlocher,  K.  Kedem及びJ.  S.  Mitcheel  による「An  efficiently  computable  Metric  for  Computing  Polygonal  shapes,  IEEE  Trans.  On  Pattern  Analysis  and  Machine  Intelligence.  Vol.  13  No.  3  1991  pp  209-215」)によって示されるように、この問題は、
【００２６】
【数４】
2008528949.tif 000006
によって解くことが可能であり、ここでθ*は、何れかの固定のtに対して最適な向きであり、
【００２７】
【数５】
2008528949.tif 000007
によって表される。
【００２８】
前述の２つの式から、２つの行列が得られる。一方は式２からのD2行列であり、他方は式３からのθ行列である。形状インスタンスの正確な（すなわち、最良のマッチの）向きは、D2行列における最小のL2距離、及びθc行列におけるその対応する要素をサーチすることによって求めることが可能である。図４E及び図４Fは、前述の２つの形状、及びそれらの最良マッチ回転関数のアラインメント結果を表す。
【００２９】
回転関数を用いる利点はいくつか存在している。例えば、最良マッチ回転関数からの回転角θ*は、２つの形状間の向きの差を表し、必要な場合、向きの補正に用いることが可能である。更に、２つの回転関数をアラインする計算量はO(mnlog(mn))である。ここで、mはテンプレート形状上の目印の数であり、nは形状インスタンス上の目印の数である。これは、形状分類処理全体の計算量でもある。形状アラインメントは、後述するように多角形近似生成および距離分類と比較して、形状分類に必要な時間の大半を要するからである。よって、適切な数の目印を選ぶことによって、形状分類を効率的にすることが可能である。（例えば、対応する目印点間の距離よりもむしろ）回転関数を用いることの別の利点は、1対１の対応関係の要件がもう必要でなくなることであり、目印数も異なり得る。これは、形状分類のロバスト性を促進することが可能である。
【００３０】
類似形状群における各形状は、対象形状の特徴を特徴付ける平均形状に寄与する。図５は、このことを達成するのに適した方法を示す。この方法はまず、類似形状群から形状をランダムに選択することによってテンプレート形状を作成する（工程５０）。次に、類似形状群における形状を、最良マッチ回転関数を備えたテンプレート形状にアラインさせる（工程５１）。図6kは例証を提供する。
【００３１】
次に、アラインさせられた回転関数は、形状の周囲長に対応するX軸に沿ってn個の等距離セグメントに分割される。各セグメントでは、平均点が、回転関数上の最初の点から求められる。このことは図6Bに示す。平均点を互いに接続することによって、平均形状を構成することが可能である（工程５２）。しかし、この平均形状は、類似形状群の形状特性を最良に表すことができないことがあり得る。テンプレート形状の選択によって大きく変わってくるからである。前述の依存性を弱め、類似形状群において最も多くの相互情報を平均形状がキャプチャすることを確実にするために、平均形状が次いでテンプレート形状として設定され、平均形状が、
【００３２】
【数６】
2008528949.tif 000008
によって表されるような、群の形状全てにわたる最小距離に達するまで上記処理が繰り返される（工程５３）。処理のいくつかのサイクルが、平均形状の収束のために必要であり得る。最終平均形状が次いで、類似形状群を特徴付ける平均形状として出力される（工程５４）。図６Cは、図６A及び図６Bの類似形状群から計算された平均形状を示す。
【００３３】
平均形状が得られると（工程５４／工程１１）、訓練データセット内の形状がそれにアラインさせられ、その類似度距離D2が計算される（工程１２）。距離を一緒に合成することによって、図７に示すように訓練データセットの類似度距離の分布が構成される。図７のX軸は距離値を表し、Y軸は距離の頻度を表す。座標の原点は、平均形状と関連付けられる。分布をみれば、類似形状群と非類似形状群との差が分かる。類似形状群における形状の場合、その距離（８５）は一般に小さく、互いに近い。同じタイプの対象を表し、平均形状に比較的類似しているようにみえるからである。対照的に、非類似形状群における形状の距離（８４）は、大きなばらつきを示す。一部は、平均形状とはかなり異なることによって原点からかなり離れている。
【００３４】
工程１３では、形状は、その距離に基づいて２つの群に分類される。距離分布は1次元であるので、分類問題は、距離の「良好な」区別を得るうえで適切な閾値を求めることとして単純化することが可能である。閾値が分類エラーを最小にすることが可能な、画像ヒストグラム形状解析に基づいた既知の閾値方法を用いることが可能である。類似形状群の距離分布は、正規分布であるとみなし得る。分布の平均はゼロに設定される。これは、平均形状に対応する。分布の分散σは、類似形状群内の形状のばらつきの原因である。１つの特定のアプリケーションでは、本願の出願人は、図7に示すように、当初閾値（81）を3*σとして設定する。次いで、分類エラーを最小にする最良フィットの閾値（８２）が求められるまで近傍領域（８３）内で行われる。
【００３５】
本発明によれば、対象形状の分類は、平均形状、及び、訓練データセットから抽出されたその分類閾値によって変わってくる。新たな形状は、入力されるにつれ、対象形状の平均形状と比較される。マッチが求められ、その距離が閾値よりも少ない場合、新たな形状が、類似形状群の構成員として分類される。分類の一貫性及び正確性を助長するために、特徴的な平均形状及び分類閾値が、新たな構成員の追加を反映するよう精緻化される。これは、新たな形状が特定量に蓄積する時点（都度）に、平均形状及び分類閾値を更新することによって達成することが可能である。
【００３６】
前述の方法は１つの形状タイプに焦点を当てており、分類結果は、YES又はNO（例えば、１又は0）である。データベース内でいくつかの別々の形状タイプを分類するうえでより複雑なシステムが必要な場合、前述の方法は、形状タイプ毎に訓練データセットを作成し、タイプ毎に平均形状及び分類閾値を対象とし、最小の類似度距離を有する形状タイプを求めることによって分類を最後に行うことによって拡張することが可能である。
【００３７】
本発明は、例えば、コンピュータ・プログラムにおいて実現することが可能である。コンピュータ・プログラムは、1つ又は複数の記憶媒体、例えば、本発明による方法を実施するよう1つ又は複数のコンピュータを制御する命令を有するコンピュータ・プログラムを記憶するよう用いる磁気記憶媒体（磁気ディスク（フロッピー（登録商標）・ディスクなど）や磁気テープなど）、光記憶媒体（光ディスク、光テープやマシン読み取り可能バーコードなど）、ソリッドステート電子記憶素子（ランダム・アクセス・メモリ（RAM）やリード・オンリー・メモリ（ROM）など）、又は何れかの他の物理素子若しくは媒体を含み得る。
【００３８】
本発明のシステムは、マイクロプロセッサ、コンピュータ・メモリ、及び、方法の工程を行うためにコンピュータ・メモリに記憶されたコンピュータ・プログラムを有するプログラム可能なコンピュータを含み得る。コンピュータは、動作するようマイクロプロセッサに接続されたメモリ・インタフェースを有する。これは、取り外し可能なメモリを受け入れるドライブ上、又はカメラ・メモリへのアクセスを可能にする特定の他の装置上のポート（ＵＳＢポートなど）であり得る。システムは、メモリ・インタフェースと互換のメモリを有するディジタル・カメラを含む。必要に応じて、写真フィルム・カメラ及びスキャナをディジタル・カメラの代わりに用いることが可能である。グラフィカル・ユーザ・インタフェース（GUI）及びユーザ入力装置（マウスやキーボードなど）をコンピュータの一部として備えることが可能である。
【００３９】
本発明は、本願の好ましい実施例を特に参照して詳細に説明したが、変形及び修正を本発明の趣旨及び範囲内で行うことが可能であることが理解されるであろう。本願に開示した実施例はよって、全ての点で限定的でなく例証的であるものとする。本発明の範囲は特許請求の範囲によって示し、その均等物の意義及び範囲内に収まる変更は全て、その中に包含されることが意図されている。
【図面の簡単な説明】
【００４０】
【図１Ａ】形状分類の自動化手法を示すフローチャートである。
【図１Ｂ】形状分類の自動化手法を示すフローチャートである。
【図２】槽形状の訓練データベースから抽出される例示的な形状を示す線図である（A乃至Kは、類似形状群に属する形状を表し、L乃至Uは、非類似形状群からの形状を表す）。
【図３Ａ】等角サンプリングによって生成される、形状境界の多角形近似を表すグラフ図である。
【図３Ｂ】いくつかの等距離点を埋めることによって作成される、等角サンプリングによって生成される多角形近似を示す図である。
【図４Ａ】テンプレート形状の回転関数を表示する、回転関数を用いることによる形状アラインメントを示す線図である。
【図４Ｂ】テンプレート形状の回転関数を表示する、回転関数を用いることによる形状アラインメントを示す線図である。
【図４Ｃ】形状インスタンスの回転関数を示す、回転関数を用いることによる形状アラインメントを示す線図である。
【図４Ｄ】形状インスタンスの回転関数を示す、回転関数を用いることによる形状アラインメントを示す線図である。
【図４Ｅ】前述の２つの形状、及びそれらの最良マッチ回転関数のアラインメント結果を表す、回転関数を用いることによる形状アラインメントを示す線図である。
【図４Ｆ】前述の２つの形状、及びそれらの最良マッチ回転関数のアラインメント結果を表す、回転関数を用いることによる形状アラインメントを示す線図である。
【図５】類似形状群から平均形状を計算するやり方を示すフローチャートである。
【図６Ａ】アラインされた回転関数の各セグメントからの平均点を得るための方法の、アラインされた回転関数を示すグラフ図である。
【図６Ｂ】アラインされた回転関数の各セグメントからの平均点を得るための方法の、セグメントからの平均点を計算するための例を示す図である。
【図６Ｃ】アラインされた回転関数の各セグメントからの平均点を得るための方法の、類似形状群から計算される平均形状を示す図である。
【図７】対象形状の訓練データセットの距離分布を示し、閾値を求めるためのやり方を示す線図である。
【図１Ａ】
2008528949.tif 000009
【図１Ｂ】
2008528949.tif 000010
【図２】
2008528949.tif 000011
【図３Ａ】
2008528949.tif 000012
【図３Ｂ】
2008528949.tif 000013
【図４Ａ】
2008528949.tif 000014
【図４Ｂ】
2008528949.tif 000015
【図４Ｃ】
2008528949.tif 000016
【図４Ｄ】
2008528949.tif 000017
【図４Ｅ】
2008528949.tif 000018
【図４Ｆ】
2008528949.tif 000019
【図５】
2008528949.tif 000020
【図６Ａ】
2008528949.tif 000021
【図６Ｂ】
2008528949.tif 000022
【図６Ｃ】
2008528949.tif 000023
【図７】
2008528949.tif 000024
【国際調査報告】
2008528949.tif 000025
2008528949.tif 000026
2008528949.tif 000027