(57)【要約】【課題】より少ない数の物体候補領域を精度よく抽出することができる。【解決手段】グラフ構築部３２が、入力画像を領域分割して得られた部分領域の各々をノードとするグラフを構築する。シードノード洗濯部３４が、グラフを構成するノード集合から、シードノードとなるノードを一つ以上選択する。部分領域ランキング部３６が、シードノードの各々について、シードノードからの遷移のしやすさに応じて、グラフを構成するノード集合に対応する部分領域集合をランキングする。クラスタ抽出部３８が、部分領域集合のランキングに基づいて、部分領域集合に含まれる部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、部分領域からなるクラスタを抽出する。クラスタ洗濯部４０が、シードノードの各々について得られたクラスタから、クラスタらしさのスコアに基づいてクラスタを選択し、物体候補領域として出力する。【選択図】図2
2018088093.tif 000002
【特許請求の範囲】
【請求項１】
入力画像から一つ以上の物体候補領域を抽出する物体候補領域抽出装置であって、
前記入力画像を領域分割して得られた部分領域の各々をノードとするグラフを構築するグラフ構築部と、
前記グラフ構築部で得られた前記グラフを構成するノード集合から、シードノードとなるノードを一つ以上選択するシードノード選択部と、
前記シードノード選択部で得られたシードノードの各々について、前記シードノードからの遷移のしやすさに応じて、前記グラフを構成するノード集合に対応する部分領域集合をランキングする部分領域ランキング部と、
前記シードノードの各々について、前記部分領域ランキング部で前記シードノードについて得られた前記部分領域集合のランキングに基づいて、前記部分領域集合に含まれる前記部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、前記部分領域からなるクラスタを抽出するクラスタ抽出部と、
前記クラスタ抽出部で前記シードノードの各々について得られた前記クラスタから、前記クラスタらしさのスコアに基づいて一つ以上のクラスタを選択し、一つ以上の物体候補領域として出力するクラスタ選択部と、
を含む物体候補領域抽出装置。
【請求項２】
前記シードノード選択部は、前記クラスタ抽出部で得られた前記クラスタに含まれない部分領域に対応するシードノードを選択する請求項１に記載の物体候補領域抽出装置。
【請求項３】
複数パターンの部分領域粒度毎に、前記入力画像を領域分割して部分領域を得る部分領域分割部を更に含み、
前記複数パターンの部分領域粒度毎に、前記グラフ構築部、前記シードノード選択部、前記部分領域ランキング部、及び前記クラスタ抽出部の各処理を行う請求項１又は請求項２に記載の物体候補領域抽出装置。
【請求項４】
入力画像から一つ以上の物体候補領域を抽出する物体候補領域抽出装置における物体候補領域抽出方法であって、
グラフ構築部が、前記入力画像を領域分割して得られた部分領域の各々をノードとするグラフを構築するステップと、
シードノード選択部が、前記グラフ構築部で得られた前記グラフを構成するノード集合から、シードノードとなるノードを一つ以上選択するステップと、
部分領域ランキング部が、前記シードノード選択部で得られたシードノードの各々について、前記シードノードからの遷移のしやすさに応じて、前記グラフを構成するノード集合に対応する部分領域集合をランキングするステップと、
クラスタ抽出部が、前記シードノードの各々について、前記部分領域ランキング部で前記シードノードについて得られた前記部分領域集合のランキングに基づいて、前記部分領域集合に含まれる前記部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、前記部分領域からなるクラスタを抽出するステップと、
クラスタ選択部が、前記クラスタ抽出部で前記シードノードの各々について得られた前記クラスタから、前記クラスタらしさのスコアに基づいて一つ以上のクラスタを選択し、一つ以上の物体候補領域として出力するステップと、
を含む物体候補領域抽出方法。
【請求項５】
前記シードノード選択部が選択するステップは、前記クラスタ抽出部で得られた前記クラスタに含まれない部分領域に対応するシードノードを選択する請求項４に記載の物体候補領域抽出方法。
【請求項６】
部分領域分割部が、複数パターンの部分領域粒度毎に、前記入力画像を領域分割して部分領域を得るステップを更に含み、
前記複数パターンの部分領域粒度毎に、前記グラフ構築部が構築するステップ、前記シードノード選択部が選択するステップ、前記部分領域ランキング部がランキングするステップ、及び前記クラスタ抽出部が抽出するステップの各ステップを実行する請求項４又は請求項５に記載の物体候補領域抽出方法。
【請求項７】
コンピュータを、請求項１〜請求項３のいずれか１項に記載の物体候補領域抽出装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物体候補領域抽出装置、方法、及びプログラムに係り、特に、物体候補領域を抽出するための物体候補領域抽出装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
画像中に写る物体をその領域とともに認識し、認識結果に応じた付加情報を提示するサービスは、スマートフォンやタブレットといったデバイスの普及や無線通信の高速化を背景に今後更なる利用拡大が見込まれている。画像中に写る物体とその領域を自動で認識する機能を実現する最も基本的なアプローチは、（ｉ）認識対象の物体に関するモデルを事前に用意しておき、（ｉｉ）複数サイズ／アスペクトの矩形を画像上で走査することで得られる領域から画像特徴量を抽出し、モデルとの比較を行うことで、各領域について対象物体が含まれているか否かを判定するというものである。上記アプローチのうち特に（ｉｉ）について、物体は任意のサイズ／アスペクトで写り込む可能性があるため、画像中の物体を正確かつ網羅的に認識するためには、多様なパターンのサイズ／アスペクトの矩形領域を、非常に細かい走査間隔でスキャンする必要がある。結果１枚の画像から、例えば１０万から１００万といった膨大な数の検査領域が発生することになり、これら全てについて対象物体を含むか否かを判定する処理のコストは非常に高いという問題が生じる。
【０００３】
入力画像中から物体候補領域を１つ以上抽出する公知の技術はいくつか存在する。代表的なアプローチは、画像を見た目に一貫性のある複数の部分領域にあらかじめ分割しておき、分割された部分領域を周囲の部分領域と比較しながら順次マージし、その経過で得られる領域を物体の候補領域として出力するというものである。例えば非特許文献１では、スーパーピクセルセグメンテーションによって得られた画像内の各部分領域をノード、隣接部分領域間の見た目の類似度をエッジとするグラフを構築し、最も類似した部分領域を順次マージし物体候補領域として出力する方法が開示されている。また非特許文献２では、非特許文献１同様のグラフを構築し、グラフ上の最小全域木を求めるプリムのアルゴリズムをベースに、エッジの重みに基づいて確率的にマージする部分領域を決定し、得られた領域を物体候補領域として出力する方法が開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】J. R. R. Uijlings et al., Selective Search for Object Recognition, in IJCV, 2013. URL(http://koen.me/research/selectivesearch/)
【非特許文献２】S. Manen et al., Prime Object Proposal with Randomized Prim’s Algorithm, in ICCV, 2013. URL(http://www.vision.ee.ethz.ch/~smanenfr/rp/index.html)
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１及び非特許文献２のような公知の物体候補領域抽出技術は、上記（ｉｉ）の方法に比べより少ない数の候補領域で画像中の物体を網羅することができるため、処理の高速化および誤認識の抑制に寄与する。しかしながら公知の技術が出力する候補領域の数は、一般的に１枚の画像中に含まれる物体の数に比べると依然として圧倒的に多い。例えば非特許文献１の技術で出力される候補領域の数は、画像を分割する部分領域の数に比例するため、仮に画像を１０００の部分領域に分割した場合、少なくとも１０００の物体候補領域が出力される。通常１枚の画像に含まれる物体は１〜１０程度であることを考えると、候補領域の数は実際に写る物体数のおよそ１００倍にのぼることになる。当然この数は、部分領域分割を粗い粒度で実施することで減らすことは可能である。しかしこの場合、画像中に小さく写り込んだ物体がそもそも候補領域として出力されないという別の問題を生じさせる可能性がある。
【０００６】
非特許文献１や非特許文献２で得られる候補領域を更に絞り込むためには、所定の指標に基づき各候補領域の「物体を正しく捉えている度合」を評価し、評価値が高い候補領域のみを続く処理にかけるという方法が考えられる。例えば非特許文献３では、あらかじめ用意しておいた膨大な正解画像データ（物体を正確に囲う領域が与えられたデータ）から抽出した画像特徴量から「物体らしさ」を事前に学習し、得られたモデルを用いてテスト画像中の物体候補領域を出力する方法が開示されている。
【０００７】
非特許文献３：B. Alexe et al., Measuring the Objectness of Image Windows, TPAMI, 2012. URL(http://groups.inf.ed.ac.uk/calvin/objectness/)
【０００８】
しかし、非特許文献３で得られた「物体らしさ」のモデルは、あくまで学習データに含まれる物体から獲得されたものであり、学習データに含まれない物体の特定は困難であるという問題がある。加えて、候補領域の「物体らしさ」を評価する処理コストも無視できるものではなく、対象物体の判別を行う処理の計算コストによっては、かえって処理に時間がかかってしまう可能性もある。
【０００９】
以上のように、入力画像から物体候補領域を抽出する公知の方法には、画像中の物体を網羅するには多くの候補領域を出力する必要があり、また事前知識を用いることなく候補領域を評価・選択する手段が提供されていないという課題があった。
【００１０】
本発明は、上記問題点を解決するために成されたものであり、より少ない数の物体候補領域を精度よく抽出することができる物体候補領域抽出装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、第１の発明に係る物体候補領域抽出装置は、入力画像から一つ以上の物体候補領域を抽出する物体候補領域抽出装置であって、前記入力画像を領域分割して得られた部分領域の各々をノードとするグラフを構築するグラフ構築部と、前記グラフ構築部で得られた前記グラフを構成するノード集合から、シードノードとなるノードを一つ以上選択するシードノード選択部と、前記シードノード選択部で得られたシードノードの各々について、前記シードノードからの遷移のしやすさに応じて、前記グラフを構成するノード集合に対応する部分領域集合をランキングする部分領域ランキング部と、前記シードノードの各々について、前記部分領域ランキング部で前記シードノードについて得られた前記部分領域集合のランキングに基づいて、前記部分領域集合に含まれる前記部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、前記部分領域からなるクラスタを抽出するクラスタ抽出部と、前記クラスタ抽出部で前記シードノードの各々について得られた前記クラスタから、前記クラスタらしさのスコアに基づいて一つ以上のクラスタを選択し、一つ以上の物体候補領域として出力するクラスタ選択部と、を含んで構成されている。
【００１２】
また、第１の発明に係る物体候補領域抽出装置において、前記シードノード選択部は、前記クラスタ抽出部で得られた前記クラスタに含まれない部分領域に対応するシードノードを選択するようにしてもよい。
【００１３】
また、第１の発明に係る物体候補領域抽出装置において、複数パターンの部分領域粒度毎に、前記入力画像を領域分割して部分領域を得る部分領域分割部を更に含み、前記複数パターンの部分領域粒度毎に、前記グラフ構築部、前記シードノード選択部、前記部分領域ランキング部、及び前記クラスタ抽出部の各処理を行うようにしてもよい。
【００１４】
第２の発明に係る物体候補領域抽出方法は、入力画像から一つ以上の物体候補領域を抽出する物体候補領域抽出装置における物体候補領域抽出方法であって、グラフ構築部が、前記入力画像を領域分割して得られた部分領域の各々をノードとするグラフを構築するステップと、シードノード選択部が、前記グラフ構築部で得られた前記グラフを構成するノード集合から、シードノードとなるノードを一つ以上選択するステップと、部分領域ランキング部が、前記シードノード選択部で得られたシードノードの各々について、前記シードノードからの遷移のしやすさに応じて、前記グラフを構成するノード集合に対応する部分領域集合をランキングするステップと、クラスタ抽出部が、前記シードノードの各々について、前記部分領域ランキング部で前記シードノードについて得られた前記部分領域集合のランキングに基づいて、前記部分領域集合に含まれる前記部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、前記部分領域からなるクラスタを抽出するステップと、クラスタ選択部が、前記クラスタ抽出部で前記シードノードの各々について得られた前記クラスタから、前記クラスタらしさのスコアに基づいて一つ以上のクラスタを選択し、一つ以上の物体候補領域として出力するステップと、を含んで実行することを特徴とする。
【００１５】
また、第２の発明に係る物体候補領域抽出方法において、前記シードノード選択部が選択するステップは、前記クラスタ抽出部で得られた前記クラスタに含まれない部分領域に対応するシードノードを選択するようにしてもよい。
【００１６】
また、第２の発明に係る物体候補領域抽出方法において、部分領域分割部が、複数パターンの部分領域粒度毎に、前記入力画像を領域分割して部分領域を得るステップを更に含み、前記複数パターンの部分領域粒度毎に、前記グラフ構築部が構築するステップ、前記シードノード選択部が選択するステップ、前記部分領域ランキング部がランキングするステップ、及び前記クラスタ抽出部が抽出するステップの各ステップを実行するようにしてもよい。
【００１７】
また、第３の発明に係るプログラムは、コンピュータを、第１の発明に係る物体候補領域抽出装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１８】
本発明の物体候補領域抽出装置、方法、及びプログラムによれば、入力画像を領域分割して得られた部分領域の各々をノードとするグラフを構築し、グラフを構成するノード集合から、シードノードとなるノードを一つ以上選択し、シードノードの各々について、シードノードからの遷移のしやすさに応じて、グラフを構成するノード集合に対応する部分領域集合をランキングし、部分領域集合のランキングに基づいて、部分領域集合に含まれる部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、部分領域からなるクラスタを抽出し、シードノードの各々について得られたクラスタから、クラスタらしさのスコアに基づいて一つ以上のクラスタを選択し、一つ以上の物体候補領域として出力することにより、より少ない数の物体候補領域を精度よく抽出することができる、という効果が得られる。
【図面の簡単な説明】
【００１９】
【図１】従来のスライディングウィンドウ方式、及び本実施の形態で提案する物体候補領域抽出の一例を示す図である。
【図２】本発明の第１の実施の形態に係る物体候補領域抽出装置の構成を示すブロック図である。
【図３】クラスタ抽出の一例を示す図である。
【図４】本発明の第１及び第２の実施の形態に係る物体候補領域抽出装置における物体候補領域抽出処理ルーチンを示すフローチャートである。
【図５】本発明の第２の実施の形態に係る物体候補領域抽出装置の構成を示すブロック図である。
【図６】本発明の第３の実施の形態に係る物体候補領域抽出装置の構成を示すブロック図である。
【図７】複数パターンの部分領域粒度で領域分割した場合の一例を示す図である。
【図８】本発明の第３の実施の形態に係る物体候補領域抽出装置における物体候補領域抽出処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２１】
＜本発明の実施の形態に係る概要＞
【００２２】
まず、本発明の実施の形態における概要を説明する。
【００２３】
本発明の実施の形態に係る手法は上記の課題を鑑みてなされたものである。本発明の実施の形態に係る手法では、まず、ある特定の領域の「物体らしさ」を事前知識なしで評価するための指標として、その領域を構成する部分領域をノードとして構築されたグラフにおける、領域に含まれる部分領域集合の「クラスタらしさ」を評価する。ここで言う「クラスタらしさ」とは、領域に含まれる部分領域集合とノード間のエッジ強度（すなわち、部分領域間の見た目の類似度）に基づいて定義される指標であり、例えば、領域に含まれる候補領域集合と含まれない領域集合の間を接続するエッジの重みの和を、領域に含まれる各部分領域に接続されるエッジの重みの和で割った値として算出することができる。多くの場合、画像に写る物体の見えは背景と大きく異なっており、物体領域と背景領域との境界の見えの変化は、物体領域内や背景領域内での見えの変化に比べ相対的に大きい。したがって、領域が正しく物体を捉えているほどに、その領域に含まれる各部分領域間はエッジで密に結合しつつ、また領域外の残りの部分領域集合とは疎に結合していると考えられ、よりクラスタらしいと評価される領域であると考えられる。本発明の実施の形態に係る手法では、以上のような着眼点のもと、得られる物体候補領域の物体らしさを、その領域に含まれる部分領域集合のクラスタらしさによって評価し、特にクラスタらしい物体候補領域を選択する。上記のクラスタらしさの算出には何らの事前知識を必要としないため、本発明によって、より少ない数の候補領域で入力画像中の物体を特定することが可能となる。
【００２４】
以上のように本発明の実施の形態では、上記の課題を解決するアプローチの一つとして、上記（ｉｉ）の処理よりも少ない数の候補領域から物体候補領域を抽出する手法を提案する。このような物体候補領域の抽出手法は、従来のスライディングウィンドウ方式に比べ、画像中の物体認識を高速かつ高精度に実現する要素技術としてその産業利用上の価値は非常に高い。図１に従来のスライディングウィンドウ方式、及び本実施の形態で提案する物体候補領域抽出の一例を示す。
【００２５】
＜本発明の第１の実施の形態に係る物体候補領域抽出装置の構成＞
【００２６】
次に、本発明の実施の形態に係る物体候補領域抽出装置の構成について説明する。図２に示すように、本発明の実施の形態に係る物体候補領域抽出装置１００は、ＣＰＵと、ＲＡＭと、後述する物体候補領域抽出処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この物体候補領域抽出装置１００は、機能的には図２に示すように、入力部１０と、演算部２０と、を備えている。
【００２７】
入力部１０は、物体候補領域の抽出対象となる入力画像の入力を受け付ける。
【００２８】
演算部２０は、記憶部２８と、部分領域分割部３０と、グラフ構築部３２と、シードノード選択部３４と、部分領域ランキング部３６と、クラスタ抽出部３８と、クラスタ選択部４０とを含んで構成されている。
【００２９】
記憶部２８には、物体候補領域の抽出対象となる入力画像が格納されている。また、クラスタ選択部４０で選択された物体候補領域が格納される。
【００３０】
部分領域分割部３０は、記憶部２８に格納されている入力画像を、複数の部分領域に領域分割する。
【００３１】
１枚の画像を部分領域に分割する方法は任意の方法を用いることが可能である。例えば、最も簡単な方法の一つとして、画像をグリッド状に分割し、得られた各矩形領域を部分領域として定義するといった方法を用いることができる。あるいは、例えば参考文献１、参考文献２、及び参考文献３に開示されているスーパーピクセルセグメンテーションを用いて得られる各セグメントを部分領域と定義してもよい。スーパーピクセルセグメンテーションは、空間的に近くかつ見た目の類似したピクセルを自動でグルーピングする手法であり、各部分領域内で見た目の一貫性が保たれるという点で好適である。
【００３２】
参考文献１：R. Achanta et al., SLIC Superpixels Compared to State-of-the-art Superpixel Methods, TPAMI, 2011.
【００３３】
参考文献２：C. Y. Ren et al., gSLICr: SLIC superpixels at over 250Hz, arXiv preprint, 2015. 
【００３４】
参考文献３：P. F. Felzenszwalb et al., Graph-Based Image Segmentation, IJCV, 2004.
【００３５】
グラフ構築部３２は、以下に説明するように、部分領域分割部３０で領域分割して得られた部分領域の各々をノードとするグラフを、エッジを定義及び算出することで構築する。
【００３６】
エッジを定義するノードペアを決定する方法は任意であり、例えば空間的に隣接するノードペア間にエッジを定義する方法や、空間的距離が一定の値以内のノードペア間に定義する方法、全てのノードペア間に定義する方法などを用いることができる。また定義した各エッジには、エッジが接続する部分領域間の類似度に基づいて重みを定義することもできる。例えば、ノードペアｖｉ、ｖｊから抽出される画像特徴量を表すベクトルをｆｉ、ｆｊとして、ノードペアｖｉ、ｖｊ間のエッジの重みｗｉｊは以下の（１）式で計算することができる。
【００３７】
【数１】
2018088093.tif 000003
・・・（１）
【００３８】
ここで、ｄ１はパラメータである。あるいは、ノードペアｖｉ、ｖｊの空間的な近さも考慮して以下の（２）式のようにエッジの重みｗｉｊを計算してもよい。
【００３９】
【数２】
2018088093.tif 000004
・・・（２）
【００４０】
ここで、ｘｉ、ｘｊはｖｉ、ｖｊの空間座標を表すベクトルであり、ｄ２はパラメータである。
【００４１】
シードノード選択部３４は、グラフ構築部３２で得られたグラフを構成するノード集合から、シードノードとなるノードを一つ以上選択する。シードノードを選択する方法は任意の方法を用いることができる。例えば各ノードの次数（ノードに接続されたエッジの重みの和）を考え、次数の大きいものから順にエッジを選択する方法を用いることができる。
【００４２】
部分領域ランキング部３６は、以下に説明するように、シードノード選択部３４で得られたシードノードの各々について、当該シードノードからの遷移のしやすさに応じて、グラフを構成するノード集合に対応する部分領域集合をランキングする。
【００４３】
ここでは、シードノードを基点として、シードノード周辺のノードをランキングする。ここでノードのランキングは、シードノードを基点としたときの各ノードへの遷移しやすさを評価したものであるとする。例えば、以下の(３)式に示すPageRankの式を満たすような遷移確率ベクトルｐを算出し、その値に基づいてノードをランキングすることができる。
【００４４】
【数３】
2018088093.tif 000005
・・・（３）
【００４５】
要素ｐｉ∈ｐはノードｖｉへの遷移しやすさ、Ｗはグラフに対応する類似度行列であり、Ｗｉｊは、ノード間のエッジの重みｗｉｊである。ＤはＷの次数行列（すなわち、Ｄｉｉ＝（ΣｊＷｉｊ）−１）、βはパラメータ（［０，１］）を表す。ｐｋはシードノード定義ベクトルであり、ノードｖｋをシードノードとして、要素ｐｉｋはｉ＝ｋのときのみ１をとるベクトルとして定義される。（３）式は、参考文献４に開示されているPoor man'sアルゴリズムや、参考文献５に開示されているPageRank nibbleアルゴリズムを用いて解くことができる。
【００４６】
参考文献４：P. Berkhin, A Survey on PageRank Computing, Internet Mathematics, 2005.
【００４７】
参考文献５：R. Andersen et al., Local Graph Partitioning using PageRank Vectors, in FOCS, 2006.
【００４８】
クラスタ抽出部３８は、以下に説明するように、シードノードの各々について、部分領域ランキング部３６で当該シードノードについて得られた部分領域集合のランキングに基づいて、部分領域集合に含まれる部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、部分領域からなるクラスタを抽出する。
【００４９】
ここでは、ランキングされた部分領域を、そのランキングの高い順に順次マージしていき、得られた部分領域集合のクラスタらしさを各々評価する。そして、各マージによって得られた集合のクラスタらしさの変化度合いを評価することで、候補領域として抽出すべき部分領域集合であるか否かを判定する。
【００５０】
具体的には、例えば以下のような手順となる。まず、部分領域ランキング部３６でランキングされた部分領域を、そのランキングの高い順にｔ回マージした結果得られる部分領域集合をＳｔとして、ＳｔのクラスタらしさΦ（Ｓｔ）を以下（４）式で算出する。
【００５１】
【数４】
2018088093.tif 000006
・・・（４）
【００５２】
ここで、｜δ（Ｓｔ）｜はＳｔとＳｔの補集合を接続するエッジの重み和、ｖ（Ｓｔ）はＳｔに含まれるノードの次数和である。クラスタらしさΦ（Ｓｔ）はコンダクタンスと呼ばれ、その値が小さいほどにクラスタらしさが高いことを示す指標である。次に、Φ（Ｓｔ）を、Ｓｔに含まれるノードの次数和ｖ（Ｓｔ）で微分し、微分した値が事前に定めた規定値以上となったとき、直前の部分領域集合Ｓｔ−１を、クラスタらしさの高いクラスタとして出力する。微分した値が規定値以上となることは、クラスタらしさのスコアに関する条件である。規定値のパラメータとしては、例えば０．０１といった値を事前に設定しておくものとする。ここでは、候補領域集合が正しく物体を捉えているほどに、よりクラスタらしいと評価されると考えられるが、その仮定が成立しないとき、すなわち、マージされた部分領域が物体に属さないとき、直前の部分領域集合のクラスタらしさに比べ、現在の部分領域集合のクラスタらしさは損なわれると考えられる。そこで、マージに対するコンダクタンスの変化に着目し、マージによってクラスタらしさが損なわれるタイミングを検出し、その直前の候補領域集合Ｓｔ−１を抽出することで、物体を捉えていると考えられる部分領域集合を効率的に抽出することができる。図３にクラスタ抽出の一例を示す。
【００５３】
クラスタ選択部４０は、クラスタ抽出部３８でシードノードの各々について得られたクラスタから、クラスタらしさのスコアに基づいてＮ個のクラスタを選択し、Ｎ個の物体候補領域として出力する。上記(４)式で定義されるコンダクタンスはその値が小さいほどクラスタらしさが高いことを示すため、コンダクタンスの小さな値のクラスタから順にＮ個選択すればよい。選択されたクラスタ集合を、物体候補領域集合として記憶部２８に格納する。
【００５４】
＜本発明の第１の実施の形態に係る物体候補領域抽出装置の作用＞
【００５５】
次に、本発明の第１の実施の形態に係る物体候補領域抽出装置１００の作用について説明する。入力部１０が、入力画像を受け付けると、記憶部２８に記憶される。そして、物体候補領域抽出装置１００は、図４に示す物体候補領域抽出処理ルーチンを実行する。
【００５６】
まず、ステップＳ１００では、部分領域分割部３０が、記憶部２８に格納されている入力画像を、複数の部分領域に領域分割する。
【００５７】
次に、ステップＳ１０２では、グラフ構築部３２が、ステップＳ１００で領域分割して得られた部分領域の各々をノードとするグラフを、エッジを定義及び算出することで構築する。
【００５８】
ステップＳ１０４では、シードノード選択部３４が、ステップＳ１０２で得られたグラフを構成するノード集合から、シードノードとなるノードを一つ以上選択する。
【００５９】
ステップＳ１０６では、ステップＳ１０４で選択されたノードからシードノードを一つ選択する。
【００６０】
ステップＳ１０８では、部分領域ランキング部３６が、ステップＳ１０６で選択されたシードノードについて、上記（３）式に従って、当該シードノードからの遷移のしやすさに応じて、グラフを構成するノード集合に対応する部分領域集合をランキングする。
【００６１】
ステップＳ１１０では、クラスタ抽出部３８が、ステップＳ１０６で選択されたシードノードについて、ステップＳ１０８で当該シードノードについて得られた部分領域集合のランキングに基づいて、部分領域集合に含まれる部分領域を順次マージしていき、上記（４）式に従って、クラスタらしさのスコアを算出し、クラスタらしさのスコアに関する予め定められた条件を満たす、部分領域からなるクラスタを抽出する。
【００６２】
ステップＳ１１２では、全てのシードノードについて処理を終了したかを判定し、処理を終了していればステップＳ１１４へ移行し、処理を終了していなければステップＳ１０６に戻って次のシードノードを選択し処理を繰り返す。
【００６３】
ステップＳ１１４では、クラスタ選択部４０が、シードノードの各々について得られたクラスタから、クラスタらしさのスコアに基づいてＮ個のクラスタを選択し、Ｎ個の物体候補領域として記憶部２８に出力する。
【００６４】
以上説明したように、本発明の第１の実施の形態に係る物体候補領域抽出装置によれば、入力画像を領域分割して得られた部分領域の各々をノードとするグラフを構築し、グラフを構成するノード集合から、シードノードとなるノードを一つ以上選択し、シードノードの各々について、シードノードからの遷移のしやすさに応じて、グラフを構成するノード集合に対応する部分領域集合をランキングし、部分領域集合のランキングに基づいて、部分領域集合に含まれる部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、部分領域からなるクラスタを抽出し、シードノードの各々について得られたクラスタから、クラスタらしさのスコアに基づいて一つ以上のクラスタを選択し、一つ以上の物体候補領域として出力することにより、より少ない数の物体候補領域を精度よく抽出することができる。
【００６５】
＜本発明の第２の実施の形態に係る物体候補領域抽出装置の構成＞
【００６６】
次に、本発明の第２の実施の形態に係る物体候補領域抽出装置の構成について説明する。第２の実施の形態では、クラスタ抽出において得られたクラスタに含まれない部分領域に対応するシードノードを選択する点が異なっている。なお、第１の実施の形態と同様の構成となる箇所については、同一符号を付して説明を省略する。
【００６７】
図５に示すように、本発明の第２の実施の形態に係る物体候補領域抽出装置２００は、ＣＰＵと、ＲＡＭと、後述する物体候補領域抽出処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この物体候補領域抽出装置２００は、機能的には図５に示すように入力部１０と、演算部２２０と、を備えている。
【００６８】
演算部２２０は、記憶部２８と、部分領域分割部３０と、グラフ構築部３２と、シードノード選択部２３４と、部分領域ランキング部３６と、クラスタ抽出部２３８と、クラスタ選択部４０とを含んで構成されている。
【００６９】
シードノード選択部２３４は、グラフ構築部３２で得られたグラフを構成するノード集合から、シードノードとなるノードを一つ以上選択する。ここでは、クラスタ抽出部２３８で既に得られたクラスタに含まれない部分領域に対応するシードノードを選択する。このように、クラスタ抽出部２３８で得られたクラスタに対し適応的にシードノードの選択を実施する。これは、例えば、似たような部分領域集合が複数抽出されることを避けるために、あるシードノードから生成されたクラスタに含まれる部分領域以外から、次のシードノードを選択するという方法を採るものである。
【００７０】
クラスタ抽出部２３８は、シードノードの各々について、部分領域ランキング部３６で当該シードノードについて得られた部分領域集合のランキングに基づいて、部分領域集合に含まれる部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、部分領域からなるクラスタを抽出し、シードノード選択部２３４及びクラスタ選択部４０に出力する。
【００７１】
第２の実施の形態の物体候補領域抽出装置の他の構成については、第１の実施の形態と同様であるため説明を省略する。
【００７２】
＜本発明の第２の実施の形態に係る物体候補領域抽出装置の作用＞
【００７３】
次に、本発明の第２の実施の形態に係る物体候補領域抽出装置２００の作用について説明する。なお、第１の実施の形態と同様の作用となる箇所については同一符号を付して説明を省略する。
【００７４】
物体候補領域抽出装置２００は、上記図４に示す物体候補領域抽出処理ルーチンにおいて、ステップＳ１０４では、シードノード選択部３４が、ステップＳ１０２で得られたグラフを構成するノード集合から、ステップＳ１１０で得られたクラスタに含まれない部分領域に対応するシードノードを選択する。ステップＳ１１０では、クラスタ抽出部２３８が、ステップＳ１０６で選択されたシードノードについて、ステップＳ１０８で当該シードノードについて得られた部分領域集合のランキングに基づいて、部分領域集合に含まれる部分領域を順次マージしていき、上記（４）式に従って、クラスタらしさのスコアを算出し、クラスタらしさのスコアに関する予め定められた条件を満たす、部分領域からなるクラスタを抽出し、シードノード選択部２３４及びクラスタ選択部４０に出力する。
【００７５】
以上説明したように、本発明の第２の実施の形態に係る物体候補領域抽出装置によれば、入力画像を領域分割して得られた部分領域の各々をノードとするグラフを構築し、グラフを構成するノード集合から、既に得られたクラスタに含まれない部分領域に対応するシードノードを選択し、シードノードの各々について、シードノードからの遷移のしやすさに応じて、グラフを構成するノード集合に対応する部分領域集合をランキングし、部分領域集合のランキングに基づいて、部分領域集合に含まれる部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、部分領域からなるクラスタを抽出し、シードノードの各々について得られたクラスタから、クラスタらしさのスコアに基づいて一つ以上のクラスタを選択し、一つ以上の物体候補領域として出力することにより、より少ない数の物体候補領域を精度よく抽出することができる。
【００７６】
＜本発明の第３の実施の形態に係る物体候補領域抽出装置の構成＞
【００７７】
次に、本発明の第３の実施の形態に係る物体候補領域抽出装置の構成について説明する。第３の実施の形態では、複数パターンの部分領域粒度毎に、入力画像を領域分割して部分領域を得る点が異なっている。なお、第２の実施の形態と同様の構成となる箇所については、同一符号を付して説明を省略する。
【００７８】
図６に示すように、本発明の第３の実施の形態に係る物体候補領域抽出装置３００は、ＣＰＵと、ＲＡＭと、後述する物体候補領域抽出処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この物体候補領域抽出装置３００は、機能的には図６に示すように入力部１０と、演算部３２０とを備えている。
【００７９】
演算部３２０は、記憶部２８と、部分領域分割部３３０と、グラフ構築部３２と、シードノード選択部２３４と、部分領域ランキング部３６と、クラスタ抽出部２３８と、クラスタ選択部４０とを含んで構成されている。
【００８０】
部分領域分割部３３０は、複数パターンの部分領域粒度毎に、記憶部２８に格納されている入力画像を領域分割して部分領域を得る。画像をどの程度細かく部分領域に分割するか（部分領域粒度）は、最終的に出力される物体候補領域の質に大きな影響を与える。具体的には、部分領域粒度を高めるほどに小さな物体が捉えられるようになり、逆に粒度を下げると大きく写り込んでいる物体が捉えやすくなる。与えられた画像中の物体のスケールは一般に未知であるため、本実施の形態では、複数の部分領域粒度で領域分割を行うものとする。図７に複数パターンの部分領域粒度で領域分割した場合の一例を示す。
【００８１】
そして、物体候補領域抽出装置３００では、複数パターンの部分領域粒度毎に、グラフ構築部３２、シードノード選択部２３４、部分領域ランキング部３６、及びクラスタ抽出部２３８の各処理を行う。
【００８２】
クラスタ選択部４０は、クラスタ抽出部２３８により複数パターンの部分領域粒度毎にシードノードの各々について得られたクラスタから、クラスタらしさのスコアに基づいてＮ個のクラスタを選択し、Ｎ個の物体候補領域として出力する。
【００８３】
＜本発明の第３の実施の形態に係る物体候補領域抽出装置の作用＞
【００８４】
次に、本発明の第３の実施の形態に係る物体候補領域抽出装置３００の作用について説明する。なお、第２の実施の形態と同様の作用となる箇所については同一符号を付して説明を省略する。
【００８５】
物体候補領域抽出装置３００は、図８に示す物体候補領域抽出処理ルーチンを実行する。
【００８６】
ステップＳ３００では、部分領域粒度を選択する。そして、選択された部分領域粒度におけるステップＳ１００〜Ｓ１１２の処理を行う。
【００８７】
ステップＳ３０２では、全ての部分領域粒度について処理を終了したかを判定し、処理を終了していればステップＳ１１４へ移行し、処理を終了していなければステップＳ３００に戻って次の部分領域粒度を選択し処理を繰り返す。
【００８８】
ステップＳ１１４では、ステップＳ１１０で、部分領域粒度毎に、シードノードの各々について得られたクラスタから、クラスタらしさのスコアに基づいてＮ個のクラスタを選択し、Ｎ個の物体候補領域として記憶部２８に出力する。
【００８９】
以上説明したように、本発明の第３の実施の形態に係る物体候補領域抽出装置によれば、複数パターンの部分領域粒度毎に、入力画像を領域分割して得られた部分領域の各々をノードとするグラフを構築し、グラフを構成するノード集合から、既に得られたクラスタに含まれない部分領域に対応するシードノードを選択し、シードノードの各々について、シードノードからの遷移のしやすさに応じて、グラフを構成するノード集合に対応する部分領域集合をランキングし、部分領域集合のランキングに基づいて、部分領域集合に含まれる部分領域を順次マージしていき、クラスタらしさのスコアに関する予め定められた条件を満たす、部分領域からなるクラスタを抽出し、複数パターンの部分領域粒度毎にシードノードの各々について得られたクラスタから、クラスタらしさのスコアに基づいて一つ以上のクラスタを選択し、一つ以上の物体候補領域として出力することにより、より少ない数の物体候補領域を精度よく抽出することができる。
【００９０】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【００９１】
１０   入力部
２０、２２０、３２０ 演算部
２８   記憶部
３０、３３０  部分領域分割部
３２   グラフ構築部
３４、２３４  シードノード選択部
３６   部分領域ランキング部
３８、２３８  クラスタ抽出部
４０   クラスタ選択部
１００、２００、３００      物体候補領域抽出装置
【図１】
2018088093.tif 000007
【図２】
2018088093.tif 000008
【図３】
2018088093.tif 000009
【図４】
2018088093.tif 000010
【図５】
2018088093.tif 000011
【図６】
2018088093.tif 000012
【図７】
2018088093.tif 000013
【図８】
2018088093.tif 000014