(57)【要約】【課題】効率的に、かつ、精度よく、繰り返しパターンを発見することができる。【解決手段】対応算出部３２が、抽出された局所特徴の各々を比較し、類似した局所特徴点のペアの各々を対応の各々として出力する。グラフ構築部３４が、対応の各々をノードとし、ノード間の類似度をエッジの重みとするグラフを構築する。クラスタ抽出部３６が、構築されたグラフに基づいて、互いに類似し、かつ同一の局所特徴点を含まない対応の集合を表すノードの集合で構成されるクラスタを一つ以上抽出する。ラベリング部４０が、クラスタ集合を出力し、クラスタ集合のクラスタの各々に対し、クラスタのノードの集合が表す対応の集合を構成する局所特徴点の各々を、繰り返しパターンのいずれに属するかをラベリングする。繰り返しパターン出力部５０が、ラベリング結果に基づいて、繰り返しパターンの集合を出力する。【選択図】図２
2018160160.tif 000002
【特許請求の範囲】
【請求項１】
入力画像中に繰り返し写り込む繰り返しパターンを発見する繰り返しパターン発見装置であって、
入力画像から局所特徴点の各々の検出し、前記局所特徴点の各々の局所特徴の抽出を行う局所特徴抽出部と、
前記局所特徴抽出部で抽出された前記局所特徴の各々を比較し、類似した前記局所特徴点のペアの各々を対応の各々として出力する対応算出部と、
前記対応算出部で得られた対応の各々をノードとし、前記ノード間の類似度をエッジの重みとするグラフを構築するグラフ構築部と、
前記グラフ構築部で構築された前記グラフに基づいて、互いに類似し、かつ同一の局所特徴点を含まない前記対応の集合を表すノードの集合で構成されるクラスタを一つ以上抽出し、クラスタ集合を出力するクラスタ抽出部と、
前記クラスタ集合のクラスタの各々に対し、前記クラスタのノードの集合が表す対応の集合を構成する前記局所特徴点の各々を、前記繰り返しパターンのいずれに属するかをラベリングするラベリング部と、
前記ラベリング部によるラベリング結果に基づいて、繰り返しパターンの集合を出力する繰り返しパターン出力部と、
を含む繰り返しパターン発見装置。
【請求項２】
前記局所特徴抽出部は、更に、前記局所特徴点の各々の属性情報を抽出し、
前記グラフ構築部は、前記局所特徴抽出部で抽出された前記局所特徴点の各々の属性情報を更に用いて前記ノード間の類似度を算出する請求項１に記載の繰り返しパターン発見装置。
【請求項３】
前記クラスタ抽出部で抽出されたクラスタ集合を修正するクラスタ修正部を更に含み、
前記クラスタ修正部は、
前記クラスタ集合に含まれる前記クラスタ間の前記対応の重複度に基づいて、前記クラスタ集合に含まれる前記クラスタをマージするクラスタマージ部と、
前記クラスタ集合の前記クラスタの各々について、前記クラスタを構成する前記ノードのうち、外れ値に該当する前記ノードを除去する外れ値除去部と、
前記クラスタ集合に含まれる前記クラスタのうち、予め定められた条件を満たさない不適当なクラスタを除去するクラスタ除去部とを１つ以上含んで構成される請求項１又は請求項２に記載の繰り返しパターン発見装置。
【請求項４】
前記繰り返しパターン出力部は、
前記ラベリング部によるラベリング結果に基づいて得られる各繰り返しパターンについて、繰り返しパターン領域を推定する繰り返しパターン領域推定部と、
前記繰り返しパターン領域推定部で得られた繰り返しパターン領域の重複度に基づいて、同一とみなせる繰り返しパターンの集合を出力する同一繰り返しパターン推定部と、を含む請求項１〜請求項３の何れか１項記載の繰り返しパターン発見装置。
【請求項５】
入力画像中に繰り返し写り込む繰り返しパターンを発見する繰り返しパターン発見装置における繰り返しパターン発見方法であって、
局所特徴抽出部が、入力画像から局所特徴点の各々の検出し、前記局所特徴点の各々の局所特徴の抽出を行うステップと、
対応算出部が、前記局所特徴抽出部で抽出された前記局所特徴の各々を比較し、類似した前記局所特徴点のペアの各々を対応の各々として出力するステップと、
グラフ構築部が、前記対応算出部で得られた対応の各々をノードとし、前記ノード間の類似度をエッジの重みとするグラフを構築するステップと、
クラスタ抽出部が、前記グラフ構築部で構築された前記グラフに基づいて、互いに類似し、かつ同一の局所特徴点を含まない前記対応の集合を表すノードの集合で構成されるクラスタを一つ以上抽出し、クラスタ集合を出力するステップと、
ラベリング部が、前記クラスタ集合のクラスタの各々に対し、前記クラスタのノードの集合が表す対応の集合を構成する前記局所特徴点の各々を、前記繰り返しパターンのいずれに属するかをラベリングするステップと、
繰り返しパターン出力部が、前記ラベリング部によるラベリング結果に基づいて、繰り返しパターンの集合を出力するステップと、
を含む繰り返しパターン発見方法。
【請求項６】
コンピュータを、請求項１〜請求項４のいずれか１項に記載の繰り返しパターン発見装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、繰り返しパターン発見装置、方法、及びプログラムに係り、特に、入力画像の繰り返しパターンを自動で発見するための繰り返しパターン発見装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
特定の物体にフォーカスすることなく空間を広く捉えた画像を撮影したとき、得られた画像の中に複数の物体が写り込み、かつそれらが互いに類似していることは多く発生する。例えば店舗の商品棚を撮影して得られる画像には、陳列された同一の商品が複数写り込むと考えられるし、車道を撮影した画像には、複数の車が写り込むことが多い。ビル等の人工物を撮影した場合には、形が同一ないしは類似した窓が複数写り込んでいることも少なくない。ここでは、このような、同一画像に複数写り込む同一ないしは類似した見えのパターンを繰り返しパターンと定義する。入力画像中の繰り返しパターンを自動で発見することができれば、何らの事前知識を用いずに入力画像中の繰り返しパターンの数を自動で数えることができる。また発見されたパターンの領域を切り出すことで、物体認識のための学習データを低コストに構築できる。更には、多数の物体が写り込む画像中の個々の物体を機械で精度よく認識するための前処理としても用いることができる。以上の例から、入力画像中の繰り返しパターンを自動で発見することの産業応用性は極めて高いと考えられる。
【０００３】
入力画像中の繰り返しパターンを自動で発見する公知の技術として、非特許文献１、及び非特許文献２があげられる。非特許文献１では、まず画像からＳＩＦＴ等の局所特徴を複数抽出し、各特徴の類似度を比較することで特に類似した特徴点ペア（以下、対応（ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ）と呼称）を算出し、得られた対応間の幾何的な関係性に基づいて類似した対応集合をクラスタリングすることで、繰り返しパターンのペアを発見する方法が開示されている。非特許文献１において、クラスタリングは、事後確率最大化の枠組みで定式化された離散最適化問題を、ＭＣＭＣ等のサンプリングアルゴリズムで近似的に解くことで得られる。非特許文献２では、非特許文献１同様抽出した局所特徴のうち、特に類似したものをＶｉｓｕａｌ Ｗｏｒｄとしてまとめ、各Ｖｉｓｕａｌ Ｗｏｒｄは繰り返しパターンあたり高々一つであるという仮定のもと、各繰り返しパターンを構成するＶｉｓｕａｌ Ｗｏｒｄの割当と、繰り返しパターンを構成するＶｉｓｕａｌ Ｗｏｒｄの割当を同時に最適化する組合せ最適化問題を、確率的なメタヒューリスティクスアルゴリズムで解く方法が開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】M. Cho et al., Unsupervised Detection and Segmentation of Identical Objects, in CVPR, 2010.
【非特許文献２】J. Liu et al., GRASP Recurring Patterns from a Single View, in CVPR, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の公知の技術にはいくつか問題がある。まず非特許文献１について、一般的に、サンプリングアルゴリズムの近似精度と計算時間はトレードオフの関係にあるため、精度よく解を得るためには膨大な計算コストを要する。また、非特許文献１では対応を構成する特徴点の空間的距離がごく近いもの同士の類似度しか考慮していないため，最適化の目的関数は、対応集合のクラスタらしさを十分に表現できていない。その結果、得られるクラスタから得られる結果は、繰り返しパターンの全貌を正確に捉えられてないという問題がある。非特許文献２では、空間的に離れた対応ペア間の類似度も考慮しているものの、繰り返しパターンあたりに同一のＶｉｓｕａｌ Ｗｏｒｄは複数含まれないという仮定を置く必要性から、繰り返しパターンを定義する特徴点の数が少なくなる。特徴点の数が少なくなると、発見される繰り返しパターンが小さくなったり、繰り返しパターンを含む物体領域のごく一部しか捉えられなくなったりするという問題が生じる。
【０００６】
以上から、画像中の繰り返しパターンを発見する公知の方法は、定義された最適化問題を解くための計算コストが高く、また得られる結果が繰り返しパターンの全貌を捉えられないという問題があった。
【０００７】
本発明は、上記問題点を解決するために成されたものであり、効率的に、かつ、精度よく、繰り返しパターンを発見することができる繰り返しパターン発見装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、第１の発明に係る繰り返しパターン発見装置は、入力画像中に繰り返し写り込む繰り返しパターンを発見する繰り返しパターン発見装置であって、入力画像から局所特徴点の各々の検出し、局所特徴点の各々の局所特徴の抽出を行う局所特徴抽出部と、局所特徴抽出部で抽出された局所特徴の各々を比較し、類似した局所特徴点のペアの各々を対応の各々として出力する対応算出部と、対応算出部で得られた対応の各々をノードとし、ノード間の類似度をエッジの重みとするグラフを構築するグラフ構築部と、グラフ構築部で構築されたグラフに基づいて、互いに類似し、かつ同一の局所特徴点を含まない対応の集合を表すノードの集合で構成されるクラスタを一つ以上抽出し、クラスタ集合を出力するクラスタ抽出部と、クラスタ集合のクラスタの各々に対し、クラスタのノードの集合が表す対応の集合を構成する局所特徴点の各々を、繰り返しパターンのいずれに属するかをラベリングするラベリング部と、ラベリング部によるラベリング結果に基づいて、繰り返しパターンの集合を出力する繰り返しパターン出力部と、を含んで構成されている。
【０００９】
また、第１の発明に係る繰り返しパターン発見装置において、前記局所特徴抽出部は、更に、前記局所特徴点の各々の属性情報を抽出し、前記グラフ構築部は、前記局所特徴抽出部で抽出された前記局所特徴点の各々の属性情報を更に用いて前記ノード間の類似度を算出するようにしてもよい。
【００１０】
また、第１の発明に係る繰り返しパターン発見装置において、前記クラスタ抽出部で抽出されたクラスタ集合を修正するクラスタ修正部を更に含み、前記クラスタ修正部は、前記クラスタ集合に含まれる前記クラスタ間の前記対応の重複度に基づいて、前記クラスタ集合に含まれる前記クラスタをマージするクラスタマージ部と、前記クラスタ集合の前記クラスタの各々について、前記クラスタを構成する前記ノードのうち、外れ値に該当する前記ノードを除去する外れ値除去部と、前記クラスタ集合に含まれる前記クラスタのうち、予め定められた条件を満たさない不適当なクラスタを除去するクラスタ除去部とを１つ以上含んで構成されるようにしてもよい。
【００１１】
また、第１の発明に係る繰り返しパターン発見装置において、前記繰り返しパターン出力部は、前記ラベリング部によるラベリング結果に基づいて得られる各繰り返しパターンについて、繰り返しパターン領域を推定する繰り返しパターン領域推定部と、前記繰り返しパターン領域推定部で得られた繰り返しパターン領域の重複度に基づいて、同一とみなせる繰り返しパターンの集合を出力する同一繰り返しパターン推定部と、を含むようにしてもよい。
【００１２】
第２の発明に係る繰り返しパターン発見方法は、入力画像中に繰り返し写り込む繰り返しパターンを発見する繰り返しパターン発見装置における繰り返しパターン発見方法であって、局所特徴抽出部が、入力画像から局所特徴点の各々の検出し、前記局所特徴点の各々の局所特徴の抽出を行うステップと、対応算出部が、前記局所特徴抽出部で抽出された前記局所特徴の各々を比較し、類似した前記局所特徴点のペアの各々を対応の各々として出力するステップと、グラフ構築部が、前記対応算出部で得られた対応の各々をノードとし、前記ノード間の類似度をエッジの重みとするグラフを構築するステップと、クラスタ抽出部が、前記グラフ構築部で構築された前記グラフに基づいて、互いに類似し、かつ同一の局所特徴点を含まない前記対応の集合を表すノードの集合で構成されるクラスタを一つ以上抽出し、クラスタ集合を出力するステップと、ラベリング部が、前記クラスタ集合のクラスタの各々に対し、前記クラスタのノードの集合が表す対応の集合を構成する前記局所特徴点の各々を、前記繰り返しパターンのいずれに属するかをラベリングするステップと、繰り返しパターン出力部が、前記ラベリング部によるラベリング結果に基づいて、繰り返しパターンの集合を出力するステップと、を含んで実行することを特徴とする。
【００１３】
また、第３の発明に係るプログラムは、コンピュータを、第１の発明に係る繰り返しパターン発見装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１４】
本発明の繰り返しパターン発見装置、方法、及びプログラムによれば、入力画像から局所特徴点の各々の検出し、局所特徴点の各々の局所特徴の抽出し、抽出された局所特徴の各々を比較し、類似した局所特徴点のペアの各々を対応の各々として出力し、対応の各々をノードとし、ノード間の類似度をエッジの重みとするグラフを構築し、構築されたグラフに基づいて、互いに類似し、かつ同一の局所特徴点を含まない対応の集合を表すノードの集合で構成されるクラスタを一つ以上抽出し、クラスタ集合を出力し、クラスタ集合のクラスタの各々に対し、クラスタのノードの集合が表す対応の集合を構成する局所特徴点の各々を、繰り返しパターンのいずれに属するかをラベリングし、ラベリング結果に基づいて、繰り返しパターンの集合を出力することにより、効率的に、かつ、精度よく、繰り返しパターンを発見することができる、という効果が得られる。
【図面の簡単な説明】
【００１５】
【図１】特徴点ペア（対応）をノードとするグラフの一例を示す図である。
【図２】本発明の実施の形態に係る繰り返しパターン発見装置の構成を示すブロック図である。
【図３】クラスタ修正部３８の構成を示すブロック図である。
【図４】繰り返しパターン出力部５０の構成を示すブロック図である。
【図５】各ノードがエッジで接続されたグラフの一例を示す図である。
【図６】グラフに基づくクラスタ抽出の一例を示す図である。
【図７】クラスタをマージする処理の一例を示す図である。
【図８】クラスタの外れ値に該当するノードを除去する処理の一例を示す図である。
【図９】クラスタ集合から条件を満たさない不適当なクラスタを除去する処理の一例を示す図である。
【図１０】繰り返しパターンのラベリングの一例を示す図である。
【図１１】繰り返しパターン領域を推定する処理の一例を示す図である。
【図１２】同一とみなせる繰り返しパターンの集合の一例を示す図である。
【図１３】本発明の実施の形態に係る繰り返しパターン発見装置における繰り返しパターン発見処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１７】
＜本発明の実施の形態に係る概要＞
【００１８】
本発明の実施の形態に係る手法は上記の課題を鑑みてなされたものである。本実施の形態ではまず、局所特徴抽出部で局所特徴量を複数抽出し、対応算出部で類似した特徴点ペアで構成される対応（ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ）集合を算出する。得られた対応集合を入力として、グラフ構築部では、各対応をノード、対応間の類似度をノード間のエッジ重みとするグラフを構築する。図１に特徴点ペア（対応）をノードとするグラフを示す。構築されたグラフの中で、繰り返しパターンを構成する局所特徴点の対応、すなわちグラフにおけるノードは、互いに類似しており、クラスタを構成していると考えられる。また、繰り返しパターンのペアにおいて、一方の繰り返しパターンに属する局所特徴点は、他方の繰り返しパターンを構成する局所特徴点のうち高々１点のみにしか対応付かないことを考慮すると、上記クラスタ内部の対応は、同一の局所特徴点を共有することはないと考えられる。そこで、クラスタリング部では、グラフ構築部で得られたグラフから、互いに類似した対応集合を、クラスタに含まれる対応間で対応を構成する特徴点が重複しないように複数クラスタリングする。クラスタ修正部では、クラスタリング部で得られたクラスタのうち、互いに類似したもののマージや外れ値に該当する対応の除去、クラスタの削除を行う。残った各クラスタについて、特徴点ラベリング部で、クラスタを構成する対応に含まれる特徴点を、その空間的な関係性に基づいて、どちらの繰り返しパターンに含まれる特徴点かをラベリングする。最後に、これまでの処理で得られたクラスタおよびラベリング結果から、繰り返しパターン出力で所望の繰り返しパターンを出力する。
【００１９】
グラフ構築部のように各対応ペアの類似度を評価してグラフを構築することによって、空間的に離れた対応ペアの類似度も評価することが可能となり、非特許文献１に比べより正確に対応集合のクラスタらしさを評価することが可能となる。一般的に、ある繰り返しパターン中の特徴点は他の繰り返しパターン中の特徴点のうちいずれか１点のみと対応付く。すなわち、対応集合（繰り返しパターンのペアを示す）を構成する各対応は、同一の特徴点を含むことはない。クラスタリング部は、クラスタに含まれる対応間で対応を構成する特徴点が重複しないようなクラスタリングを、サンプリング処理を経ずに実現することができるため、非特許文献１のような精度と処理コストのトレードオフが生じることはない。更には、本実施の形態では、非特許文献２のような、繰り返しパターンを構成する局所特徴間に対する制約がないため、より正確に画像中の繰り返しパターンの全貌を捉えることができる。
【００２０】
＜本発明の実施の形態に係る繰り返しパターン発見装置の構成＞
【００２１】
次に、本発明の実施の形態に係る繰り返しパターン発見装置の構成について説明する。図２に示すように、本発明の実施の形態に係る繰り返しパターン発見装置１００は、ＣＰＵと、ＲＡＭと、後述する繰り返しパターン発見処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この繰り返しパターン発見装置１００は、機能的には図２に示すように入力部１０と、演算部２０と、出力部６０とを備えている。
【００２２】
入力部１０は、繰り返しパターンの抽出対象となる入力画像を受け付ける。
【００２３】
演算部２０は、局所特徴抽出部３０と、対応算出部３２と、グラフ構築部３４と、クラスタ抽出部３６と、クラスタ修正部３８と、ラベリング部４０と、繰り返しパターン出力部５０とを含んで構成されている。
【００２４】
図３に示すように、クラスタ修正部３８は、クラスタマージ部４２と、外れ値除去部４４と、クラスタ除去部４６とを含んで構成されている。
【００２５】
図４に示すように、繰り返しパターン出力部５０は、繰り返しパターン領域推定部５２と、同一繰り返しパターン推定部５４とを含んで構成されている。
【００２６】
局所特徴抽出部３０は、入力部１０で受け付けた入力画像から局所特徴点の各々の検出し、局所特徴点の各々の局所特徴量、及び属性情報の抽出を行う。局所特徴点の抽出及び局所特徴量の記述方法は任意の公知の技術を用いることができる。局所特徴点の検出方法としては、例えば参考文献１で開示されているＤｏＧや参考文献２に記載されているＨａｒｒｉｓ Ｌａｐｌａｃｅ，Ｈｅｓｓｉａｎ検出器を用いればよい。局所特徴量の記述方法としては、例えばＳＩＦＴやＬＩＯＰ、ＳＵＲＦ、ＢＥＩＥＦ、ＢＲＩＳＫ、ＯＲＢ、ＦＲＥＡＫ、ＡＫＡＺＥを用いればよい。上記の技術は事前に学習処理等を必要としないものであるが、例えば参考文献３で開示されているＬＩＦＴのような、事前に大規模データで学習された特徴検出方法、方法記述方法を用いてもよい。本実施の形態では、入力画像からＮ個の局所特徴量
【００２７】
【数１】
2018160160.tif 000003
を抽出し、各局所特徴量に対応する属性情報として、局所特徴点の位置
【００２８】
【数２】
2018160160.tif 000004
、スケール｛ｓｉ｝ｉ＝１Ｎ、オリエンテーション｛θｉ｝ｉ＝１Ｎを得るものとする。
【００２９】
［参考文献１］D. G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, IJCV, 2004.
［参考文献２］K. Mikolajczyk et al., A Comparison of Affine Region Detectors, in IJCV, 2005.
［参考文献３］K. M. Yi et al., LIFT: Learned Invariant Feature Transform, in Proc. ECCV, 2016.
【００３０】
対応算出部３２は、局所特徴抽出部３０で抽出された局所特徴量の各々を比較し、類似した局所特徴点のペアの各々を対応の各々として出力する。局所特徴点の比較を実現する最も簡単な方法は、全ての局所特徴点のペアについて距離や類似度を算出し、その中から特に類似したものを選択するというものである。局所特徴点間の距離、類似度を算出する方法は任意であり、例えばＬ２ノルムやコサイン類似度を用いることができる。また特に類似した局所特徴点のペアを選択する方法も任意で、例えば局所特徴点のペアの距離、類似度に対する閾値をあらかじめ設定する方法や、出力する対応の個数をあらかじめ設定する方法を用いることができる。上記のような全ての局所特徴点のペアを比較する方法は、局所特徴の数が増えた場合計算コストが高くなるという問題がある。このような場合には、例えば、参考文献４に開示されているような近似最近傍探索の手法を用いて高速化を図ってもよい。本実施の形態では上記処理によりＭ≦ＮＣ２個の対応｛ｃｎ＝(ｉ,ｊ）｝ｎ＝１Ｍを算出する。ｉ,ｊは局所特徴点のインデクスである。
【００３１】
［参考文献４］：M. Muja et al., Fast Approximate Nearest Neighbors with Automatic Algorithmic Configuration, in Proc. VISAPP, 2009.
【００３２】
グラフ構築部３４は、対応算出部３２で得られた対応の各々をノードとし、ノード間の類似度をエッジの重みとするグラフを構築する。ノード間の類似度は、局所特徴点の各々の位置及び属性情報を用いて算出する。図５に示すように、対応算出部３２で得られた各対応｛ｃｎ＝（ｉ,ｊ）｝ｎ＝１Ｍをノードとし、各ノードがエッジで接続されたグラフを構築する。エッジの重みは対応ペア間の類似度に相当する。グラフ構築部３４において、対応ペアの類似度は、対応ペアを構成する局所特徴点の位置及び属性情報を用いて算出するものとする。局所特徴点の属性情報を用いて対応ペアの類似度を求める方法を以下に説明する。属性情報のうちの局所特徴点のスケール属性｛ｓｉ｝ｉ＝１Ｎ、及び各局所特徴点の位置
【００３３】
【数３】
2018160160.tif 000005
を用いて、対応ペアｃｎ＝（ｉ,ｊ）とｃｍ＝（ｉ′,ｊ′）について、以下のような類似度ｗｎｍを定義する。
【００３４】
【数４】
2018160160.tif 000006
・・・（１）
2018160160.tif 000007
・・・（２）
2018160160.tif 000008
・・・（３）
【００３５】
ここで、
【００３６】
【数５】
2018160160.tif 000009
【００３７】
は特徴点ｉとｉ′の距離、σｓはパラメータである。あるいは、属性情報のうちの局所特徴点のオリエンテーション属性｛θｉ｝ｉ＝１Ｎを用いると、以下のような類似度を定義することもできる。
【００３８】
【数６】
2018160160.tif 000010
・・・（４）
2018160160.tif 000011
・・・（５）
2018160160.tif 000012
・・・（６）
【００３９】
ここで、
【００４０】
【数７】
2018160160.tif 000013
【００４１】
は基準線に対しベクトルｉｉ′がなす角度、σθはパラメータである。あるいは以下（７）式のように、スケールとオリエンテーションを同時に考慮して類似度を定義してもよい。
【００４２】
【数８】
2018160160.tif 000014
・・・（７）
【００４３】
クラスタ抽出部３６は、グラフ構築部３４で構築されたグラフに基づいて、互いに類似し、かつ同一の局所特徴点を含まない対応の集合を表すノードの集合で構成されるクラスタを一つ以上抽出し、クラスタ集合を出力する。図６にクラスタ抽出の一例を示す。クラスタを抽出するときは、抽出されるクラスタに含まれる任意の２つのノード、すなわち２つの対応が、同一の局所特徴点を含まないようにする。同一の局所特徴点から構成されず、かつ互いに類似した対応集合Ｓをグラフから抽出する方法として、本実施の形態では、以下（８）式の目的関数を考える。
【００４４】
【数９】
2018160160.tif 000015
・・・（８）
【００４５】
δＳはＳとその補集合を接続するエッジの重み和、ｖｏｌ（Ｓ）はＳに含まれるノードの次数の和（エッジの重み和）である。δＳ／ｖｏｌ(Ｓ)はｃｏｎｄｕｃｔａｎｃｅと呼ばれ、その値が小さいほどノード集合Ｓがよりクラスタらしいことを表す指標である。（８）式を満たすノード集合を発見するアルゴリズムとしては、以下の処理を適用する。
【００４６】
［１］グラフ中の任意のノードを選択する。
［２］選択したノードを開始ノードとして、ページランクアルゴリズム等を用いて周辺ノードをランキングする。参考文献５で開示されている近似ページランクアルゴリズムを用いることで、グラフのサイズに依存しない計算コストで周辺ノードをランキングすることができる。
［３］［２］で得られたランキング順に、ノードをクラスタＳに挿入する。挿入されるたびに、δＳ／ｖｏｌ（Ｓ）を計算し記憶しておく。このとき、新たに挿入対象となっているノード(=対応)を構成する特徴点が、既に選択されたノード（＝対応）を構成する特徴点として使用されていた場合はそのノードはクラスタに含めない。
［４］［３］で得られたδＳ／ｖｏｌ(Ｓ)が最小となるときまでにクラスタSに挿入されていたノード集合を、［１］で選択された開始ノードに対応するクラスタとして記憶する。
［５］［１］〜［４］の処理を、グラフ中の複数ノードについて実施する。ノードは、全ノードを対象としてもよいし、あるいは一部を選択してもよい。ランダムに選択、ノードの次数(重み和)が高いもののみを選択等してもよい。
【００４７】
［参考文献５］：R. Andersen et al., Local Graph Partitioning using PageRank Vectors, in FOCS, 2006.
【００４８】
以下では、抽出されたクラスタ集合を
【００４９】
【数１０】
2018160160.tif 000016
【００５０】
とする。
【００５１】
クラスタ修正部３８は、クラスタマージ部４２、外れ値除去部４４、及びクラスタ除去部４６の各処理により、クラスタ抽出部３６で抽出されたクラスタ集合を修正する。
【００５２】
クラスタマージ部４２は、クラスタ集合に含まれるクラスタ間の対応の重複度に基づいて、クラスタ集合に含まれるクラスタをマージする。図７に示すように、クラスタ間の重複度をＪａｃｃａｒｄ類似度で評価し、類似度があらかじめ決められた閾値以上のものについては、Ｓ′＝Ｓｎ｜Ｓｍとしてマージする処理を、該当するクラスタペアがなくなるまで繰り返せばよい。
【００５３】
外れ値除去部４４は、クラスタ集合の前記クラスタの各々について、クラスタを構成するノードのうち、外れ値に該当するノードを除去する。図８に示すように、各クラスタ内の各ノードについて、クラスタ内部のノード間の重み和を算出し、重み和が事前に設定された閾値以下のものを外れ値と判定して除去するとった方法を用いることができる。
【００５４】
クラスタ除去部４６は、修正されたクラスタ集合に含まれるクラスタのうち、予め定められた条件を満たさない不適当なクラスタを除去する。図９に示すように、クラスタを構成するノードの数が事前に設定した閾値より少ないものや、クラスタ内の局所特徴で定義される領域が、事前に設定した閾値より小さいものを除去するといった方法を用いることができる。
【００５５】
ラベリング部４０は、クラスタ集合のクラスタの各々に対し、クラスタのノードの集合が表す対応の集合を構成する局所特徴点の各々について、繰り返しパターンのいずれに属するかをラベリングする。図１０に繰り返しパターンａと繰り返しパターンｂとのいずれに属するかラベリングした場合の一例を示す。ここで、ラベリングにあたり、ある対応を構成する２つの局所特徴点は、同一の繰り返しパターンに属することはないものとする。上記を満たすラベリングは任意の方法で実現することが可能である。本実施の形態では、クラスタから基準となるノード（＝対応）ｉｖを一つ選択し、残りのノード（＝対応）について、基準ノードとの類似度およびノード間の類似度を考慮してラベリングを行う。具体的には、クラスタＳについて、以下の（９）式に示す目的関数を最小化するようなラベル
【００５６】
【数１１】
2018160160.tif 000017
【００５７】
を求める。
【００５８】
【数１２】
2018160160.tif 000018
・・・（９）
2018160160.tif 000019
・・・（１０）
2018160160.tif 000020
・・・（１１）
【００５９】
ここで、λｓ、λθはパラメータ、ｃｎ＝(ｉ,ｊ)、ｃｍ＝(ｉ′,ｊ′)である。（９）式は、参考文献６で開示されているＬｏｏｐｙ Ｂｅｌｉｅｆ Ｐｒｏｐａｇｔｉｏｎといったアルゴリズムで解くことができる。クラスタＳおよびラベル
【００６０】
【数１３】
2018160160.tif 000021
【００６１】
を用いることで、繰り返しパターンを抽出することができる。例えば、クラスタＳ＝{(１,２),(３,４),(５,６),(７,８)}、ラベルｂｓ＝(０,１,０,１)のとき、得られる繰り返しパターン（局所特徴のインデクスの集合）は{１,４,５,８}、{２,３,６,７}となる。
【００６２】
［参考文献６］：P. F. Felzenszwalb et al., Efficient Belief Propagation for Early Vision, in IJCV, 2006.
【００６３】
繰り返しパターン出力部５０は、ラベリング部４０によるラベリング結果に基づいて、繰り返しパターン領域推定部５２及び同一繰り返しパターン推定部５４の各処理により、繰り返しパターンの集合を出力する。
【００６４】
繰り返しパターン領域推定部５２は、ラベリング部４０によるラベリング結果に基づいて得られる各繰り返しパターンについて、繰り返しパターン領域を推定する。例えば図１１に示すように、ラベリングされた繰り返しパターンを構成する局所特徴点をもれなく囲うような最小の矩形として定義する。あるいは各局所特徴で定義される領域を事前知識として、画像セグメンテーションを実施しても良い。
【００６５】
同一繰り返しパターン推定部５４は、繰り返しパターン領域推定部５２で得られた繰り返しパターン領域の重複度に基づいて、同一とみなせる繰り返しパターンの集合を出力部６０に出力する。これは、得られた繰り返しパターン領域が、予め決められた値以上に重複している場合、重複した繰り返しパターンは同一のものであり、また重複したものと各々ペアになっている繰り返しパターンもまた同一の繰り返しパターンであると考えられるためである。よって、図１２に示すように、これらの繰り返しパターンをまとめることで最終的な出力を得る。
【００６６】
＜本発明の実施の形態に係る繰り返しパターン発見装置の作用＞
【００６７】
次に、本発明の実施の形態に係る繰り返しパターン発見装置１００の作用について説明する。入力部１０において入力画像を受け付けると、繰り返しパターン発見装置１００は、図１３に示す繰り返しパターン発見処理ルーチンを実行する。
【００６８】
まず、ステップＳ１００では、局所特徴抽出部３０は、入力部１０で受け付けた入力画像から局所特徴点の各々の検出し、局所特徴点の各々の局所特徴量、及び属性情報の抽出を行う。
【００６９】
次に、ステップＳ１０２では、対応算出部３２は、ステップＳ１００で抽出された局所特徴量の各々を比較し、類似した局所特徴点のペアの各々を対応の各々として出力する。
【００７０】
ステップＳ１０４では、グラフ構築部３４は、ステップＳ１０２で得られた対応の各々をノードとし、ノード間の類似度をエッジの重みとするグラフを構築する。
【００７１】
ステップＳ１０６では、クラスタ抽出部３６は、ステップＳ１０４で構築されたグラフに基づいて、互いに類似し、かつ同一の局所特徴点を含まない対応の集合を表すノードの集合で構成されるクラスタを一つ以上抽出し、クラスタ集合を出力する。
【００７２】
ステップＳ１０８では、クラスタ修正部３８は、ステップＳ１０８で抽出されたクラスタ集合を修正する。具体的には、クラスタマージ部４２により、クラスタ集合に含まれるクラスタ間の対応の重複度に基づいて、クラスタ集合に含まれるクラスタをマージする。また、外れ値除去部４４により、クラスタ集合の前記クラスタの各々について、クラスタを構成するノードのうち、外れ値に該当するノードを除去する。クラスタ除去部４６により、クラスタ集合に含まれるクラスタのうち、予め定められた条件を満たさない不適当なクラスタを除去する。
【００７３】
ステップＳ１１０では、ラベリング部４０は、クラスタ集合のクラスタの各々に対し、クラスタのノードの集合が表す対応の集合を構成する局所特徴点の各々を、繰り返しパターンのいずれに属するかをラベリングする。
【００７４】
ステップＳ１１２では、繰り返しパターン領域推定部５２は、ステップＳ１１０のラベリング結果に基づいて得られる各繰り返しパターンについて、繰り返しパターン領域を推定する。
【００７５】
ステップＳ１１４では、同一繰り返しパターン推定部５４は、ステップＳ１１２で得られた繰り返しパターン領域の重複度に基づいて、同一とみなせる繰り返しパターンの集合を出力部６０に出力し、処理を終了する。
【００７６】
以上説明したように、本発明の実施の形態に係る繰り返しパターン発見装置によれば、入力画像から局所特徴点の各々の検出し、局所特徴点の各々の局所特徴の抽出し、抽出された局所特徴の各々を比較し、類似した局所特徴点のペアの各々を対応の各々として出力し、対応の各々をノードとし、ノード間の類似度をエッジの重みとするグラフを構築し、構築されたグラフに基づいて、互いに類似し、かつ同一の局所特徴点を含まない対応の集合を表すノードの集合で構成されるクラスタを一つ以上抽出し、クラスタ集合を出力し、クラスタ集合のクラスタの各々に対し、クラスタのノードの集合が表す対応の集合を構成する局所特徴点の各々を、繰り返しパターンのいずれに属するかをラベリングし、ラベリング結果に基づいて、繰り返しパターンの集合を出力することにより、効率的に、かつ、精度よく、繰り返しパターンを発見することができる。
【００７７】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００７８】
例えば、上述した実施の形態では、局所特徴抽出部３０により抽出した局所特徴点の局所特徴量を用いて、対応を求め、対応の各々をノードとし、ノード間の類似度をエッジの重みとするグラフを構築する場合を例に説明したが、これに限定されるものではなく、局所特徴量からＶｉｓｕａｌ Ｗｏｒｄを作成し、Ｖｉｓｕａｌ Ｗｏｒｄを用いて対応を求め、対応の各々をノードとし、ノード間の類似度をエッジの重みとするグラフを構築するようにしてもよい。
【００７９】
また、上述した実施の形態では、クラスタ修正部３８は、クラスタマージ部４２と、外れ値除去部４４と、クラスタ除去部４６とを含んで構成されており、これらの処理部の各々の処理を行う場合を例に説明したが、これに限定されるものではなく、これらの処理部の処理を任意に行うようにしてもよい。
【符号の説明】
【００８０】
３０   局所特徴抽出部
３２   対応算出部
３４   グラフ構築部
３６   クラスタ抽出部
３８   クラスタ修正部
４０   ラベリング部
４２   クラスタマージ部
４４   外れ値除去部
４６   クラスタ除去部
５０   繰り返しパターン出力部
５２   繰り返しパターン領域推定部
５４   同一繰り返しパターン推定部
６０   出力部
１００ 繰り返しパターン発見装置
【図１】
2018160160.tif 000022
【図２】
2018160160.tif 000023
【図３】
2018160160.tif 000024
【図４】
2018160160.tif 000025
【図５】
2018160160.tif 000026
【図６】
2018160160.tif 000027
【図７】
2018160160.tif 000028
【図８】
2018160160.tif 000029
【図９】
2018160160.tif 000030
【図１０】
2018160160.tif 000031
【図１１】
2018160160.tif 000032
【図１２】
2018160160.tif 000033
【図１３】
2018160160.tif 000034