(57)【特許請求の範囲】
【請求項１】
２次元座標に分布可能な複数の点を示すデータを記憶する記憶部と、
前記記憶部に記憶された複数の点の集合を含む処理対象領域から、前記点の評価値に基づいて算出されるスコアが最も高いもしくは低い矩形領域を解の候補である解候補として抽出する抽出部と、
前記抽出部により抽出された解候補と、他の解候補のうち複数の処理対象領域と重複する解候補とが交差するか否かを判定し、交差する場合には、当該解候補及び当該他の解候補のうち前記スコアが低いもしくは高い解候補を解候補から除外するとともに前記スコアが高いもしくは低い解候補を解候補として確定し、交差しない場合には、当該解候補を解候補として確定する確定部と、
前記確定部により確定された解候補のうち、前記スコアが最も高いもしくは低い解候補を解領域として選択する選択部と、
前記選択部により選択された解領域が抽出された前記処理対象領域のうち当該解領域を除いた領域、および、前記確定部により除外された解候補が抽出された前記処理対象領域のうち当該解候補を除いた領域から、一つ又は複数の矩形領域を処理対象領域として生成する生成部と、
前記選択部により所定数の解領域が選択されるまで、前記生成部により生成された処理対象領域から前記抽出部により解候補を抽出させ、前記確定部により解候補を確定させ、前記選択部により解領域を選択させる制御部と
を備えたことを特徴とする領域発見装置。
【請求項２】
前記複数の処理対象領域と重複する解候補を一時記憶する一時記憶部をさらに備え、
前記確定部は、前記抽出部により抽出された解候補と、前記一時記憶部により一時記憶された解候補とが交差するか否かを判定し、交差する場合には、当該抽出された解候補及び当該一時記憶された解候補のうち前記スコアが低いもしくは高い解候補を解候補から除外するとともに前記スコアが高いもしくは低い解候補を解候補として確定し、交差しない場合には、当該解候補を解候補として確定することを特徴とする請求項１に記載の領域発見装置。
【請求項３】
コンピュータに、
２次元座標に分布可能な複数の点を示すデータを記憶する記憶部に記憶された複数の点の集合を含む処理対象領域から、前記点の評価値に基づいて算出されるスコアが最も高いもしくは低い矩形領域を解の候補である解候補として抽出し、
前記解候補を抽出する処理により抽出された解候補と、他の解候補のうち複数の処理対象領域と重複する解候補とが交差するか否かを判定し、交差する場合には、当該解候補及び当該他の解候補のうち前記スコアが低いもしくは高い解候補を解候補から除外するとともに前記スコアが高いもしくは低い解候補を解候補として確定し、交差しない場合には、当該解候補を解候補として確定し、
前記解候補を確定する処理により確定された解候補のうち、前記スコアが最も高いもしくは低い解候補を解領域として選択し、
前記解領域を選択する処理により選択された解領域が抽出された前記処理対象領域のうち当該解領域を除いた領域、および、前記解候補を確定する処理により除外された解候補が抽出された前記処理対象領域のうち当該解候補を除いた領域から、一つ又は複数の矩形領域を処理対象領域として生成し、
前記解領域を選択する処理により所定数の解領域が選択されるまで、前記処理対象領域を生成する処理により生成された処理対象領域から前記解候補を抽出する処理により解候補を抽出させ、前記解候補を確定する処理により解候補を確定させ、前記解領域を選択する処理により解領域を選択させる
ことを特徴とする領域発見プログラム。
【請求項４】
コンピュータが実行する領域発見方法であって、
２次元座標に分布可能な複数の点を示すデータを記憶する記憶部に記憶された複数の点の集合を含む処理対象領域から、前記点の評価値に基づいて算出されるスコアが最も高いもしくは低い矩形領域を解領域として抽出し、
前記処理対象領域のうち前記解領域を除いた領域から一つ又は複数の矩形領域を処理対象領域として生成し、
前記処理対象領域を生成する処理により生成された処理対象領域から、当該処理対象領域ごとに、前記スコアが最も高いもしくは低い矩形領域を解候補として抽出し、
前記解候補を抽出する処理により抽出された解候補が複数の処理対象領域と重複する場合には、当該解候補を一時記憶部に一時記憶し、
前記解候補を抽出する処理により抽出された解候補と、前記一時記憶部に一時記憶された解候補とが交差するか否かを判定し、交差する場合には、当該抽出された解候補及び当該一時記憶された解候補のうち前記スコアが低いもしくは高い解候補を解候補から除外するとともに前記スコアが高いもしくは低い解候補を解候補として確定し、交差しない場合には、当該抽出された解候補を解候補として確定し、
前記解候補を確定する処理により確定された解候補のうち、前記スコアが最も高いもしくは低い解候補を解領域として選択し、
前記解領域を選択する処理により選択された解領域が抽出された前記処理対象領域のうち当該解領域を除いた領域、および、前記解候補を確定する処理により除外された解候補が抽出された前記処理対象領域のうち当該解候補を除いた領域から、一つ又は複数の矩形領域を処理対象領域として生成する
ことを特徴とする領域発見方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、領域発見装置、領域発見プログラム及び領域発見方法に関する。
【背景技術】
【０００２】
従来、例えば、電力使用量が最も高い地域を地図上で発見したり、車両が密集している地域を地図上で発見したりすることなどに利用される最適領域発見という技術が存在する。この技術は、「２次元座標と評価値とを有する点データの集合に対して、評価値から算出されるスコアを定義したとき、このスコアが最大となる領域を出力せよ」という最適領域発見問題を解くことで実現される。
【０００３】
ここで、最適領域発見問題を解く従来技術の一例を説明する。図３１は、従来技術を説明するための図である。図３１に示す２次元座標は、水平方向をｘ軸とし、垂直方向をｙ軸とする座標系である。この２次元座標上に分布する各点は、評価値ｖを有する。つまり、点データは、（ｘ，ｙ，ｖ）により表される。図３１に示す例では、白点（open  circle）はｖ＝１の点であり、黒点（filled  circle）はｖ＝−１の点である。
【０００４】
図３１に示す例では、点の集合を含む領域Ｒに対して、各点の評価値ｖの総和が最大となる領域を発見する場合を説明する。例えば、従来技術では、各点を通るｘ軸に平行な線分と、各点を通るｙ軸に平行な線分とをそれぞれ２つずつ選択する。そして、これら４つの線分で囲まれる矩形領域を列挙し、矩形領域ごとのスコア、つまり各点の評価値ｖの総和を算出する。そして、算出したスコアが最大となる矩形領域を選択することで、領域Ｒから最適領域ｒを発見する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】David  P.  Dobkin,  Dimitrios  Gunopulos,  Wolfgang  Maass:  Computing  the  Maximum  Bichromatic  Discrepancy  with  Applications  to  Computer  Graphics  and  Machine  Learning.  J.  Comput.  Syst.  Sci.  52(3):  453-470  (1996)
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、最適領域を発見するだけでなく、スコアが高い上位ｋ件の領域を発見することができれば有用であると考えられる。例えば、電力使用量が高い地域のうち上位３件を発見することで、電力使用量が高い地域についての特徴や傾向といった新たな知見を見出すことが可能になるものと考えられる。なお、ｋは、自然数である。
【０００７】
ここで、従来技術において算出される領域ごとのスコアを用いて、スコアが高い上位ｋ件の領域を単純に選択すると、似通った領域ばかりが選択されてしまい、得られる知見が少ない。例えば、図３２に示すように、領域Ｒから領域ｒ１，ｒ２，ｒ３を発見しても、得られる知見が少なかった。このため、各領域が交差しないように上位ｋ件の領域を発見することが要求される。例えば、図３３に示すように、領域Ｒから互いに交差しない領域ｒ１，ｒ２，ｒ３を発見すること、つまり交差なし上位ｋ件領域発見問題を解くことが望まれる。これは、「２次元座標と評価値とを有する点データの集合に対して、評価値から算出されるスコアを定義したとき、このスコアの上位ｋ件の領域を交差なく出力せよ」という問題である。この問題を解くことにより、図３４に示すように、領域Ｒから互いに交差しない領域ｒｉの集合が発見できる。なお、ｉは、「１≦ｉ≦ｋ」を満たす自然数である。また、図３２〜３５は、従来技術の問題点を説明するための図である。
【０００８】
しかしながら、交差なし上位ｋ件領域発見問題を効率良く解くことができる技術は存在しなかった。
【０００９】
例えば、従来技術を用いて、図３５に示すような領域の発見方法が考えられる。図３５は、従来技術の問題点を説明するための図である。図３５の網掛け部分は、選択された領域を示す。図３５（１）に示すように、この方法では、従来技術と同様に、４つの線分で囲まれる領域ｒｋを列挙し、領域ごとにスコアを算出する。そして、図３５（２）に示すように、これらの領域から上位１件目の領域として領域ｒ５を選択する。そして、図３５（３）に示すように、上位２件目の候補として領域ｒ２を選択し、領域ｒ５と交差するか否か判定する。この場合、領域ｒ２は領域ｒ５と交差するため、領域ｒ２は候補から除外される。そして、次にスコアが高い領域ｒ６を上位２件目の候補として選択し、領域ｒ５との交差判定を行う。この場合、領域ｒ６は領域ｒ５と交差しないため、領域ｒ６が上位２件目の領域となる。以降、この方法では、上位ｉ件目の候補を選択するごとに、既に選択された上位ｉ−１件目までの領域と交差判定を行い、交差しない領域のみを選択するという処理を繰り返すことで、交差なし上位ｋ件領域発見問題を解く。しかし、この方法では、候補となる領域を選択するごとに、既に選択された領域のそれぞれと交差判定を行うため、処理効率が低くなるおそれがある。
【００１０】
開示の技術は、上記に鑑みてなされたものであって、交差なし上位ｋ件領域発見問題を効率良く解くことができる領域発見装置、領域発見プログラム及び領域発見方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本願の開示する技術は、一つの態様において、記憶部と、抽出部と、確定部と、選択部と、生成部と、制御部とを備える。記憶部は、２次元座標に分布可能な複数の点を示すデータを記憶する。抽出部は、記憶部に記憶された複数の点の集合を含む処理対象領域から、点の評価値に基づいて算出されるスコアが最も高いもしくは低い矩形領域を解の候補である解候補として抽出する。確定部は、抽出部により抽出された解候補と、他の解候補のうち複数の処理対象領域と重複する解候補とが交差するか否かを判定する。確定部は、交差する場合には、抽出された解候補及び他の解候補のうちスコアが低いもしくは高い解候補を解候補から除外するとともにスコアが高いもしくは低い解候補を解候補として確定し、交差しない場合には、抽出された解候補を解候補として確定する。選択部は、確定部により確定された解候補のうち、スコアが最も高いもしくは低い解候補を解領域として選択する。生成部は、選択部により選択された解領域が抽出された処理対象領域のうち解領域を除いた領域、および、確定部により除外された解候補が抽出された処理対象領域のうち除外された解候補を除いた領域から、一つ又は複数の矩形領域を処理対象領域として生成する。制御部は、選択部により所定数の解領域が選択されるまで、生成部により生成された処理対象領域から抽出部により解候補を抽出させ、確定部により解候補を確定させ、選択部により解領域を選択させる。
【発明の効果】
【００１２】
本願の開示する技術の一つの態様によれば、交差なし上位ｋ件領域発見問題を効率良く解くことができるという効果を奏する。
【図面の簡単な説明】
【００１３】
【図１】図１は、実施例１に係る領域発見装置の構成の一例を示す図である。
【図２】図２は、入力データの一例を示す図である。
【図３】図３は、処理対象集合のデータ構造の一例を示す図である。
【図４】図４は、解集合のデータ構造の一例を示す図である。
【図５】図５は、対応テーブルのデータ構造の一例を示す図である。
【図６】図６は、出力データの一例を示す図である。
【図７】図７は、処理対象領域を分割する処理について説明するための図である。
【図８】図８は、発見部の処理を詳細に説明するための図である。
【図９】図９は、発見部の処理を詳細に説明するための図である。
【図１０】図１０は、発見部の処理を詳細に説明するための図である。
【図１１】図１１は、発見部の処理を詳細に説明するための図である。
【図１２】図１２は、発見部の処理を詳細に説明するための図である。
【図１３】図１３は、発見部の処理を詳細に説明するための図である。
【図１４】図１４は、発見部の処理を詳細に説明するための図である。
【図１５】図１５は、発見部の処理を詳細に説明するための図である。
【図１６】図１６は、発見部の処理を詳細に説明するための図である。
【図１７】図１７は、発見部の処理を詳細に説明するための図である。
【図１８】図１８は、発見部の処理を詳細に説明するための図である。
【図１９】図１９は、発見部の処理を詳細に説明するための図である。
【図２０】図２０は、発見部の処理を詳細に説明するための図である。
【図２１】図２１は、発見部の処理を詳細に説明するための図である。
【図２２】図２２は、発見部の処理を詳細に説明するための図である。
【図２３】図２３は、発見部の処理を詳細に説明するための図である。
【図２４】図２４は、発見部の処理を詳細に説明するための図である。
【図２５】図２５は、実施例１に係る領域発見装置の処理手順を示すフローチャートである。
【図２６】図２６は、領域発見処理の処理手順を示すフローチャートである。
【図２７】図２７は、候補確定処理の処理手順を示すフローチャートである。
【図２８】図２８は、分割処理の処理手順を示すフローチャートである。
【図２９】図２９は、実施例１に係る領域発見装置の構成の一例を示す図である。
【図３０】図３０は、領域発見プログラムを実行するコンピュータの一例を示す図である。
【図３１】図３１は、従来技術を説明するための図である。
【図３２】図３２は、従来技術の問題点を説明するための図である。
【図３３】図３３は、従来技術の問題点を説明するための図である。
【図３４】図３４は、従来技術の問題点を説明するための図である。
【図３５】図３５は、従来技術の問題点を説明するための図である。
【発明を実施するための形態】
【００１４】
以下に、本願の開示する領域発見装置、領域発見プログラム及び領域発見方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１５】
実施例１に係る領域発見装置の構成の一例について説明する。図１は、実施例１に係る領域発見装置の構成の一例を示す図である。図１に示すように、この領域発見装置１００は、記憶部１１０と、制御部１２０とを有する。また、領域発見装置１００は、入力装置１０１と、出力装置１０２とに接続される。
【００１６】
入力装置１０１は、各種情報の入力を受け付ける。例えば、入力装置１０１は、２次元座標に分布する点データの集合を含む情報の入力を受け付ける。また、例えば、入力装置１０１は、点データの評価値に基づいて算出されるスコアの定義を示す情報の入力を受け付ける。このスコアの定義は、例えば、各点データの評価値の総和である。例えば、入力装置１０１は、キーボードやマウス、媒体読取装置などに対応する。なお、スコアの定義は、上記の例に限定されるものではない。例えば、スコアの定義は、各領域の面積当たりの各点データの評価値の総和としても良い。
【００１７】
出力装置１０２は、各種情報を出力する。例えば、出力装置１０２は、スコアが高い上位ｋ件の領域を示す情報を出力する。例えば、出力装置１０２は、ディスプレイやモニタ、スピーカなどに対応する。
【００１８】
記憶部１１０は、入力データ１１１と、処理対象集合１１２と、解集合１１３と、候補集合１１４と、分割集合１１５と、交差集合１１６と、対応テーブル１１７と、出力データ１１８とを有する。記憶部１１０は、例えば、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、磁気ディスク装置、光ディスク装置又は光磁気ディスク装置等の記憶装置に対応する。
【００１９】
入力データ１１１は、点データの集合を含む情報である。この点データは、例えば、２次元座標に分布し、評価値を有する点の情報である。図２は、入力データの一例を示す図である。図２に示すように、入力データ１１１は、例えば、水平方向の座標「ｘ」と、垂直方向の座標「ｙ」と、評価値「ｖ」とを対応付けた情報である。なお、入力データ１１１は、記憶部の一例である。
【００２０】
図２に示すように、例えば、入力データ１１１は、ｘ「０．２」と、ｙ「０．９」と、ｖ「９．０」とを対応付けた情報を含む。つまり、入力データ１１１は、座標「（０．２，０．９）」に評価値「９．０」を有する点「（０．２，０．９，９．０）」が存在することを示す。また、入力データ１１１は、他の点についても同様の情報を含む。なお、評価値ｖは、１次元のデータに限定されるものではなく、例えば、多次元のデータであっても良い。また、点データは、２次元座標に分布するデータに限定されるものではなく、例えば、数値データなど多次元座標系に含まれる領域に分布可能なデータを有していれば良い。
【００２１】
処理対象集合１１２は、後述する発見部１２２の処理対象となる領域の集合である。例えば、処理対象集合１１２は、２次元座標に分布する複数の点データを含む任意の大きさの処理対象領域の集合である。この処理対象領域は、例えば、４つの線分で囲まれた矩形領域である。図３は、処理対象集合のデータ構造の一例を示す図である。図３に示すように、処理対象集合１１２は、例えば、処理対象領域ごとに「ＩＤ」と、「ｌｅｆｔＬｏｗ」と、「ｒｉｇｈｔＵｐ」と、「ｐｏｉｎｔＬｉｓｔ」とを対応付けた情報を含む。このうち、ＩＤは、処理対象領域を一意に識別する識別情報を示す。ｌｅｆｔＬｏｗは、矩形の左下の座標を示す。ｒｉｇｈｔＵｐは、矩形の右上の座標を示す。ｐｏｉｎｔＬｉｓｔは、処理対象領域に含まれる複数の点データを示す。なお、処理対象集合１１２は、Ｔａｒｇｅｔとも称する。
【００２２】
図３に示すように、例えば、処理対象集合１１２は、ＩＤ「Ｒ−１」と、ｌｅｆｔＬｏｗ「（０．２，０．２）」と、ｒｉｇｈｔＵｐ「（０．８，０．６）」とを対応付けた情報を含む。また、処理対象集合１１２は、ＩＤ「Ｒ−１」と、ｐｏｉｎｔＬｉｓｔ「（０．５，０．３，５．３），（０．７，０．４，−３．２）・・・」とを対応付けた情報を含む。つまり、処理対象集合１１２は、処理対象領域Ｒ−１がｘ＝０．２、ｙ＝０．２、ｘ＝０．８、ｙ＝０．６の４つの線分で囲まれた矩形領域であり、点（０．５，０．３，５．３）や点（０．７，０．４，−３．２）など複数の点を含むことを示す。また、処理対象集合１１２は、他の処理対象領域についても同様の情報を含む。なお、矩形領域の表現方法は、左下の座標と右上の座標とで表現する方法を説明したが、これに限定されるものではない。例えば、矩形領域の表現方法は、矩形を形成する４つの線分の式で表現されても良い。以下の説明では、矩形領域の表現方法は、左下の座標と右上の座標とで表現する方法を用いることとする。
【００２３】
解集合１１３は、解となる領域の集合である。例えば、解集合１１３は、発見部１２２により求められた上位１件目から上位ｋ件目までの解領域の集合である。図４は、解集合のデータ構造の一例を示す図である。図４に示すように、解集合１１３は、例えば、解領域ごとに「ＩＤ」と、「ｌｅｆｔＬｏｗ」と、「ｒｉｇｈｔＵｐ」と、「ｓｃｏｒｅ」とを対応付けた情報を含む。このうち、ＩＤは、解領域を一意に識別する識別情報を示す。ｓｃｏｒｅは、解領域に含まれる複数の点データの評価値ｖに基づいて算出されるスコアを示す。なお、解集合１１３は、Ｏｕｔｐｕｔとも称する。
【００２４】
図４に示すように、例えば、解集合１１３は、ＩＤ「ｒ−１」と、ｌｅｆｔＬｏｗ「（０．２，０．３）」と、ｒｉｇｈｔＵｐ「（０．４，０．５）」と、ｓｃｏｒｅ「２５」とを対応付けた情報を含む。つまり、解集合１１３は、解領域ｒ−１がｘ＝０．２、ｙ＝０．３、ｘ＝０．４、ｙ＝０．５の４つの線分で囲まれた矩形領域であり、解領域ｒ−１のスコアが２５であることを示す。また、解集合１１３は、他の解領域についても同様の情報を含む。
【００２５】
候補集合１１４は、解領域の候補となる領域の集合である。例えば、候補集合１１４は、処理対象領域から抽出された候補領域の集合である。候補集合１１４は、図４に示した解集合１１３と同様のデータ構造を有する。図４に示すように、候補集合１１４は、例えば、候補領域ごとに「ＩＤ」と、「ｌｅｆｔＬｏｗ」と、「ｒｉｇｈｔＵｐ」と、「ｓｃｏｒｅ」とを対応付けた情報を含む。このうち、ＩＤは、候補領域を一意に識別する識別情報を示す。なお、候補領域のＩＤは、解領域のＩＤと同一のＩＤを用いても良い。なお、候補領域は、解候補の一例である。また、候補集合１１４は、Ｃａｎｄｉｄａｔｅとも称する。
【００２６】
分割集合１１５は、発見部１２２における分割処理の対象となる処理対象領域の集合である。例えば、分割集合１１５は、発見部１２２により解領域が抽出された処理対象領域の集合である。分割集合１１５は、図３に示した処理対象集合１１２と同様のデータ構造を有する。図３に示すように、分割集合１１５は、例えば、処理対象領域ごとに「ＩＤ」と、「ｌｅｆｔＬｏｗ」と、「ｒｉｇｈｔＵｐ」と、「ｐｏｉｎｔＬｉｓｔ」とを対応付けた情報を含む。なお、分割集合１１５は、Ｓｐｌｉｔとも称する。
【００２７】
交差集合１１６は、発見部１２２における交差判定の対象となる候補領域の集合である。例えば、交差集合１１６は、候補領域のうち、複数の処理対象領域と重複する候補領域の集合である。交差集合１１６は、図４に示した解集合１１３と同様のデータ構造を有する。図４に示すように、交差集合１１６は、例えば、候補領域ごとに「ＩＤ」と、「ｌｅｆｔＬｏｗ」と、「ｒｉｇｈｔＵｐ」と、「ｓｃｏｒｅ」とを対応付けた情報を含む。なお、交差集合１１６は、一時記憶部の一例である。また、交差集合１１６は、Ｉｎｔｅｒｓｅｃｔｉｏｎとも称する。
【００２８】
対応テーブル１１７は、処理対象領域と、処理対象領域から抽出された候補領域とを対応付けて記憶する。図５は、対応テーブルのデータ構造の一例を示す図である。図５に示すように、対応テーブル１１７は、例えば、「ＴａｒｇｅｔＩＤ」と、「ＲｅｓｕｌｔＩＤ」とを対応付けて記憶する。このうち、ＴａｒｇｅｔＩＤは、処理対象領域のＩＤを示す。ＲｅｓｕｌｔＩＤは、候補領域のＩＤを示す。
【００２９】
図５に示すように、例えば、対応テーブル１１７は、ＴａｒｇｅｔＩＤ「Ｒ−１」と、ＲｅｓｕｌｔＩＤ「ｒ−１」とを対応付けて記憶する。つまり、対応テーブル１１７は、処理対象領域Ｒ−１から候補領域ｒ−１が抽出されたことを示す。また、対応テーブル１１７は、他の処理対象領域についても同様の情報を含む。
【００３０】
出力データ１１８は、スコアが高い上位ｋ件の領域を含む情報である。例えば、出力データ１１８は、点データの集合のうちスコアが高い上位３件の領域を含む。図６は、出力データの一例を示す図である。図６に示すように、例えば、出力データ１１８は、「Ｔｏｐ１＝＝＞（０．５，０．１）−（０．９，０．７）ｓｃｏｒｅ：２０．０」を含む。つまり、出力データ１１８は、上位１件目の領域がｘ＝０．５、ｙ＝０．１、ｘ＝０．９、ｙ＝０．７の４つの線分で囲まれた矩形領域であり、上位１件目の領域のスコアが２０．０であることを示す。また、出力データ１１８は、他の順位の領域についても同様の情報を含む。
【００３１】
制御部１２０は、受付部１２１と、発見部１２２と、出力制御部１２３とを有する。制御部１２０は、例えば、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積装置に対応する。また、制御部１２０は、例えば、ＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路に対応する。
【００３２】
受付部１２１は、入力装置１０１から各種情報を受け付ける。例えば、受付部１２１は、２次元座標に分布する点データの集合を含む情報を入力装置１０１から受け付けて、受け付けた情報を入力データ１１１として記憶部１１０に格納する。また、受付部１２１は、点データの評価値に基づいて算出されるスコアの定義を示す情報を入力装置１０１から受け付けて、受け付けた情報を発見部１２２に出力する。
【００３３】
発見部１２２は、点データの集合からスコアが高い上位ｋ件の領域を発見する。例えば、発見部１２２は、処理対象となる領域のうち発見済みの解領域を除いた領域から次の順位の解領域を発見する処理と、複数の処理対象領域と重複する候補領域のみと交差するか否かを判定する処理とを繰り返し実行することで、上位ｋ件の領域を発見する。なお、発見部１２２は、記憶部、抽出部、確定部、選択部、生成部及び制御部の一例である。
【００３４】
以下において、発見部１２２の処理を説明する。発見部１２２は、入力データ１１１から処理対象領域を生成する。例えば、発見部１２２は、入力データ１１１の全ての点を含む最も小さい矩形領域を処理対象領域として生成する。
【００３５】
例えば、発見部１２２は、入力データに含まれる全ての点のｘ座標のうち、最も小さい座標ｘｍｉｎと最も大きい座標ｘｍａｘとを取得する。また、発見部１２２は、入力データに含まれる全ての点のｙ座標のうち、最も小さい座標ｙｍｉｎと最も大きい座標ｙｍａｘとを取得する。発見部１２２は、取得した座標を用いて、矩形領域の左下の座標（ｘｍｉｎ，ｙｍｉｎ）と右上の座標（ｘｍａｘ，ｙｍａｘ）とを決定する。発見部１２２は、決定した座標によって表現される矩形領域を処理対象領域Ｒとして生成し、生成した処理対象領域Ｒを処理対象集合１１２に格納する。
【００３６】
また、発見部１２２は、処理対象領域のうちスコアが最大の領域を候補領域として抽出する。例えば、発見部１２２は、処理対象領域Ｒに含まれる全ての点について、各点を通る水平方向の線分と、各点を通る垂直方向の線分とをそれぞれ２つずつ選択する。そして、発見部１２２は、これら４つの線分で囲まれる領域ｒを列挙し、領域ｒごとのスコアを算出する。そして、発見部１２２は、算出した領域ｒごとのスコアが最大となる領域を候補領域ｒとして抽出する。また、発見部１２２は、抽出した候補領域ｒと、候補領域ｒを抽出した処理対象領域Ｒとを対応付けて対応テーブル１１７に格納する。
【００３７】
また、発見部１２２は、抽出した候補領域ｒを確定する。例えば、発見部１２２は、抽出した候補領域ｒｉと交差集合１１６に含まれる領域ｒｊと交差するか否かを判定する。なお、この判定する処理は、交差判定とも称する。
【００３８】
ここで、発見部１２２が実行する交差判定について説明する。ここでは一例として、領域Ａと領域Ｂとが交差するか否かを判定する場合を説明する。なお、領域Ａ及び領域Ｂは、下記のように表現される領域である。
Ａ：（Ａｘｍｉｎ，Ａｙｍｉｎ）−（Ａｘｍａｘ，Ａｙｍａｘ）
Ｂ：（Ｂｘｍｉｎ，Ｂｙｍｉｎ）−（Ｂｘｍａｘ，Ｂｙｍａｘ）
【００３９】
例えば、発見部１２２は、領域Ａの四隅の座標のいずれかが領域Ｂに含まれるか否かを判定することで、交差判定を実行する。例えば、発見部１２２は、左下の座標（Ａｘｍｉｎ，Ａｙｍｉｎ）、左上の座標（Ａｘｍｉｎ，Ａｙｍａｘ）、右下の座標（Ａｘｍａｘ，Ａｙｍｉｎ）及び右上の座標（Ａｘｍａｘ，Ａｙｍａｘ）をそれぞれ算出する。そして、発見部１２２は、算出した４つの座標のうち、１つ以上の座標が下記の式（１）及び式（２）を満たす場合に、領域Ａと領域Ｂとが交差するものと判定する。
【００４０】
Ｂｘｍｉｎ＜ｘ＜Ｂｘｍａｘ・・・（１）
【００４１】
Ｂｙｍｉｎ＜ｙ＜Ｂｙｍａｘ・・・（２）
【００４２】
一方、発見部１２２は、算出した４つの座標のうち、全ての座標が下記の式（１）又は式（２）を満たさない場合に、領域Ａと領域Ｂとが交差しないものと判定する。なお、交差判定の方法は、上記の方法に限定されるものではない。例えば、発見部１２２は、領域Ｂの四隅の座標のいずれかが領域Ａに含まれるか否かを判定することで、交差判定を実行してもよい。
【００４３】
候補領域ｒｉと候補領域ｒｊとが交差する場合には、発見部１２２は、候補領域ｒｉのスコアと候補領域ｒｊのスコアとを比較し、候補領域ｒｉのスコアが候補領域ｒｊのスコアより高いか否かを判定する。候補領域ｒｉのスコアが候補領域ｒｊのスコアより高い場合には、発見部１２２は、スコアが高い方の候補領域ｒｉを候補領域として確定し、候補領域ｒｉが複数の処理対象領域と重複するか否かを判定する。この判定方法は、例えば、上述した交差判定と同様の方法を用いる。具体的には、例えば、発見部１２２は、候補領域ｒｉの四隅の座標のいずれかが処理対象領域Ｒｉ以外の処理対象領域に含まれる場合に、候補領域ｒｉが複数の処理対象領域と重複するものと判定する。一方、発見部１２２は、候補領域ｒｉの四隅の座標のいずれもが処理対象領域Ｒｉ以外の処理対象領域に含まれない場合に、候補領域ｒｉが複数の処理対象領域と重複しないものと判定する。
【００４４】
候補領域ｒｉが複数の処理対象領域と重複する場合には、発見部１２２は、候補領域ｒｉを候補集合１１４と交差集合１１６とに格納する。一方、候補領域ｒｉが複数の処理対象領域と重複しない場合には、発見部１２２は、候補領域ｒｉを候補集合１１４に格納する。また、発見部１２２は、スコアが低い方の候補領域ｒｊを候補集合１１４と交差集合１１６とから除外する。そして、発見部１２２は、対応テーブル１１７を参照し、候補領域ｒｊに対応する処理対象領域Ｒｊを分割集合１１５に格納する。発見部１２２は、対応テーブル１１７より候補領域ｒｊと対応する処理対象領域Ｒｊの組を除外する。
【００４５】
一方、候補領域ｒｉのスコアが候補領域ｒｊのスコアより低い場合には、発見部１２２は、対応テーブル１１７を参照し、候補領域ｒｉに対応する処理対象領域Ｒｉを分割集合１１５に格納する。発見部１２２は、対応テーブル１１７より候補領域ｒｉと対応する処理対象領域Ｒｉの組を除外する。
【００４６】
一方、候補領域ｒｉと候補領域ｒｊとが交差しない場合には、候補領域ｒｉを候補領域として確定し、候補領域ｒｉが複数の処理対象領域と重複するか否かを判定する。候補領域ｒｉが複数の処理対象領域と重複する場合には、発見部１２２は、候補領域ｒｉを候補集合１１４と交差集合１１６とに格納する。一方、候補領域ｒｉが複数の処理対象領域と重複しない場合には、発見部１２２は、候補領域ｒｉを候補集合１１４に格納する。
【００４７】
また、発見部１２２は、確定した候補領域のうち、スコアが最も高い候補領域を解領域として選択する。例えば、発見部１２２は、候補集合１１４に含まれる各候補領域のスコアを比較し、スコアが最大の候補領域ｒｉを解領域ｒｉとして選択する。そして、発見部１２２は、選択した解領域ｒｉを解集合１１３に格納する。また、発見部１２２は、対応テーブル１１７を参照し、解領域ｒｉに対応する処理対象領域Ｒｉを分割集合１１５に格納する。
【００４８】
また、発見部１２２は、分割集合１１５に含まれる処理対象領域のうち、候補領域が抽出された領域を除いた領域から、一つ又は複数の処理対象領域を生成する。例えば、発見部１２２は、分割集合１１５から処理対象領域Ｒ−ｉを取得する。発見部１２２は、取得した処理対象領域Ｒ−ｉのうち候補領域ｒ−ｉを除いた領域を分割し、新たな処理対象領域Ｒ−１，Ｒ−２，Ｒ−３，Ｒ−４を生成する。そして、発見部１２２は、生成した処理対象領域Ｒ−１，Ｒ−２，Ｒ−３，Ｒ−４を処理対象集合１１２に格納する。
【００４９】
ここで、図７を用いて、処理対象領域を分割する処理について説明する。図７は、処理対象領域を分割する処理について説明するための図である。図７では、処理対象領域Ｒ−ｉのうち候補領域ｒ−ｉを除いた領域を、４つの処理対象領域Ｒ−１，Ｒ−２，Ｒ−３，Ｒ−４に分割する場合を説明する。なお、処理対象領域Ｒ−ｉ、候補領域ｒ−ｉ、処理対象領域Ｒ−１〜Ｒ−４は、水平方向の座標（ｘｍｉｎ，ｘｌｏｗｅｒ，ｘｕｐｐｅｒ，ｘｍａｘ）と垂直方向の座標（ｙｍｉｎ，ｙｌｏｗｅｒ，ｙｕｐｐｅｒ，ｙｍａｘ）とを用いると、下記のように表現される。
Ｒ−ｉ：（ｘｍｉｎ，ｙｍｉｎ）−（ｘｍａｘ，ｙｍａｘ）
ｒ−ｉ：（ｘｌｏｗｅｒ，ｙｌｏｗｅｒ）−（ｘｕｐｐｅｒ，ｙｕｐｐｅｒ）
Ｒ−１：（ｘｍｉｎ，ｙｍｉｎ）−（ｘｌｏｗｅｒ，ｙｍａｘ）
Ｒ−２：（ｘｍｉｎ，ｙｍｉｎ）−（ｘｍａｘ，ｙｌｏｗｅｒ）
Ｒ−３：（ｘｕｐｐｅｒ，ｙｍｉｎ）−（ｘｍａｘ，ｙｍａｘ）
Ｒ−４：（ｘｍｉｎ，ｙｕｐｐｅｒ）−（ｘｍａｘ，ｙｍａｘ）
【００５０】
図７に示すように、例えば、発見部１２２は、分割集合１１５から処理対象領域Ｒ−ｉを取得する。発見部１２２は、対応テーブル１１７を参照し、取得した処理対象領域Ｒ−ｉに対応する候補領域ｒ−ｉを取得する。発見部１２２は、処理対象領域Ｒ−ｉを候補領域ｒ−ｉの左辺を通る直線で分割し、処理対象領域Ｒ−ｉの左辺と候補領域ｒ−ｉの左辺とで囲まれる矩形領域を処理対象領域Ｒ−１として生成する。また、発見部１２２は、処理対象領域Ｒ−ｉを候補領域ｒ−ｉの下辺を通る直線で分割し、処理対象領域Ｒ−ｉの下辺と候補領域ｒ−ｉの下辺とで囲まれる矩形領域を処理対象領域Ｒ−２として生成する。また、発見部１２２は、処理対象領域Ｒ−ｉを候補領域ｒ−ｉの右辺を通る直線で分割し、処理対象領域Ｒ−ｉの右辺と候補領域ｒ−ｉの右辺とで囲まれる矩形領域を処理対象領域Ｒ−３として生成する。また、発見部１２２は、処理対象領域Ｒ−ｉを候補領域ｒ−ｉの上辺を通る直線で分割し、処理対象領域Ｒ−ｉの上辺と候補領域ｒ−ｉの上辺とで囲まれる矩形領域を処理対象領域Ｒ−４として生成する。そして、発見部１２２は、生成した処理対象領域Ｒ−１，Ｒ−２，Ｒ−３，Ｒ−４を新たな処理対象領域Ｒ−１，Ｒ−２，Ｒ−３，Ｒ−４として処理対象集合１１２に格納する。
【００５１】
また、発見部１２２は、出力データ１１８を生成する。例えば、発見部１２２は、解集合１１３に格納した解領域の数が所定数に到達するまで、新たに生成した処理対象領域から候補領域を抽出し、候補領域を確定し、候補集合１１４から解領域を選択する処理を繰り返す。そして、解領域の数が所定数に到達した場合に、発見部１２２は、解集合１１３に含まれる領域の情報に基づいて、出力データ１１８を生成する。例えば、発見部１２２は、上位１件目の領域から順に、各領域の順位と、座標と、スコアとを対応付けて、出力データ１１８を生成する。
【００５２】
次に、図８〜２４を用いて、発見部１２２の処理を詳細に説明する。図８〜２４は、発見部の処理を詳細に説明するための図である。図８〜２４に示す例では、発見部１２２が入力データ１１１からスコアが高い上位３件の領域を発見する場合を説明する。
【００５３】
図８について説明する。発見部１２２は、入力データ１１１から処理対象領域Ｒｉｎｉｔ生成する（ステップＳ１０）。例えば、発見部１２２は、入力データ１１１の全ての点を含む最も小さい矩形領域を処理対象領域Ｒｉｎｉｔとして生成する。そして、発見部１２２は、生成した処理対象領域Ｒｉｎｉｔを処理対象集合１１２に格納する。なお、処理対象領域Ｒｉｎｉｔは、水平方向の座標（ｘ０，ｘ１）と垂直方向の座標（ｙ０，ｙ１）とを用いると、下記のように表現される。
Ｒｉｎｉｔ：（ｘ０，ｙ０）−（ｘ１，ｙ１）
【００５４】
図９の説明に移行する。発見部１２２は、処理対象集合１１２に含まれる処理対象領域Ｒｉｎｉｔのうち、スコアが最大の領域であるｔｏｐ−１を抽出し、抽出したｔｏｐ−１を解集合１１３に格納する（ステップＳ１１）。発見部１２２は、ｔｏｐ−１を抽出した処理対象領域Ｒｉｎｉｔを分割集合１１５に格納する。ここで、処理対象領域Ｒｉｎｉｔを分割集合１１５に格納するのは、処理対象領域Ｒｉｎｉｔのうちｔｏｐ−１を除いた領域にｔｏｐ−２以降の領域が含まれるからである。なお、ｔｏｐ−１は、水平方向の座標（ｘ２，ｘ３）と垂直方向の座標（ｙ２，ｙ３）とを用いると、下記のように表現される。
ｔｏｐ−１：（ｘ２，ｙ２）−（ｘ３，ｙ３）
【００５５】
図１０の説明に移行する。発見部１２２は、分割集合１１５から処理対象領域Ｒｉｎｉｔを取得する。そして、発見部１２２は、処理対象領域Ｒｉｎｉｔから処理対象領域Ｒ１〜Ｒ４を生成し、生成した処理対象領域Ｒ１〜Ｒ４を処理対象集合１１２に格納する（ステップＳ１２）。なお、処理対象領域Ｒ１〜Ｒ４は、水平方向の座標（ｘ０〜ｘ３）と垂直方向の座標（ｙ０〜ｙ３）とを用いると、下記のように表現される。
Ｒ１：（ｘ０，ｙ０）−（ｘ２，ｙ１）
Ｒ２：（ｘ０，ｙ０）−（ｘ１，ｙ２）
Ｒ３：（ｘ３，ｙ０）−（ｘ１，ｙ１）
Ｒ４：（ｘ０，ｙ３）−（ｘ１，ｙ１）
【００５６】
図１１の説明に移行する。発見部１２２は、処理対象集合１１２から処理対象領域Ｒ１を取得する。そして、発見部１２２は、処理対象領域Ｒ１のうちスコアが最大の領域ｒ１を抽出し、抽出した領域ｒ１を候補領域として候補集合１１４に格納する（ステップＳ１３）。発見部１２２は、他の処理対象領域Ｒ２〜Ｒ４についても同様に、スコアが最大の領域ｒ２〜ｒ４を抽出し、抽出した領域ｒ２〜ｒ４を候補領域として候補集合１１４に格納する。また、発見部１２２は、抽出した候補領域ｒ１〜ｒ４と、候補領域ｒ１〜ｒ４を抽出した処理対象領域Ｒ１〜Ｒ４とをそれぞれ対応付けて対応テーブル１１７に格納する。また、候補領域ｒ４は複数の処理対象領域と重複するので、発見部１２２は、候補領域ｒ４を交差集合１１６に格納する。ここで、候補領域ｒ４を交差集合１１６に格納するのは、以後の処理において抽出される候補領域と候補領域ｒ４とが交差する可能性があるからである。これに対して候補領域ｒ１〜ｒ３は、以後の処理において抽出される候補領域と交差する可能性はない。なお、候補領域ｒ１〜ｒ４は、水平方向の座標（ｘ４〜ｘ１１）と垂直方向の座標（ｙ４〜ｙ１１）とを用いると、下記のように表現される。
ｒ１：（ｘ４，ｙ４）−（ｘ５，ｙ５）
ｒ２：（ｘ６，ｙ６）−（ｘ７，ｙ７）
ｒ３：（ｘ８，ｙ８）−（ｘ９，ｙ９）
ｒ４：（ｘ１０，ｙ１０）−（ｘ１１，ｙ１１）
【００５７】
図１２の説明に移行する。ここでは、候補領域ｒ１〜ｒ４のうちスコアが最大の候補領域が候補領域ｒ１である場合を説明する。この場合、発見部１２２は、候補集合１１４からスコアが最大の候補領域ｒ１をｔｏｐ−２として選択し、選択したｔｏｐ−２を解集合１１３に格納する（ステップＳ１４）。また、発見部１２２は、候補領域ｒ１を候補集合１１４から除外するとともに、対応テーブルを参照し、候補領域ｒ１に対応する処理対象領域Ｒ１を分割集合１１５に格納する。発見部１２２は、対応テーブル１１７より候補領域ｒ１と対応する処理対象領域Ｒ１の組を除外する。ここで、処理対象領域Ｒ１を分割集合１１５に格納するのは、処理対象領域Ｒ１のうちｔｏｐ−２を除いた領域にｔｏｐ−３以降の領域が含まれる可能性があるからである。
【００５８】
図１３の説明に移行する。発見部１２２は、分割集合１１５から処理対象領域Ｒ１を取得する。そして、発見部１２２は、処理対象領域Ｒ１から処理対象領域Ｒ１＿１〜Ｒ１＿４を生成し、生成した処理対象領域Ｒ１＿１〜Ｒ１＿４を処理対象集合１１２に格納する（ステップＳ１５）。なお、ここで生成された処理対象領域Ｒ１＿１〜Ｒ１＿４は、水平方向の座標（ｘ０〜ｘ５）と垂直方向の座標（ｙ０〜ｙ５）とを用いると、下記のように表現される。
Ｒ１＿１：（ｘ０，ｙ０）−（ｘ４，ｙ１）
Ｒ１＿２：（ｘ０，ｙ０）−（ｘ２，ｙ４）
Ｒ１＿３：（ｘ５，ｙ０）−（ｘ２，ｙ１）
Ｒ１＿４：（ｘ０，ｙ５）−（ｘ２，ｙ１）
【００５９】
図１４及び図１５の説明に移行する。発見部１２２は、処理対象集合１１２から処理対象領域Ｒ１＿１を取得し、取得した処理対象領域Ｒ１＿１のうちスコアが最大の領域ｒ１＿１を抽出する（ステップＳ１６）。発見部１２２は、抽出した候補領域ｒ１＿１と、候補領域ｒ１＿１を抽出した処理対象領域Ｒ１＿１とを対応付けて対応テーブル１１７に格納する。なお、領域ｒ１＿１は、水平方向の座標（ｘ１２，ｘ１３）と垂直方向の座標（ｙ１２，ｙ１３）とを用いると、下記のように表現される。
ｒ１＿１：（ｘ１２，ｙ１２）−（ｘ１３，ｙ１３）
【００６０】
発見部１２２は、抽出した領域ｒ１＿１が交差集合１１６に含まれる候補領域ｒ４と交差するか否かを判定する。図１４では、領域ｒ１＿１と候補領域ｒ４とが交差しないので、領域ｒ１＿１を候補領域ｒ１＿１として候補集合１１４に格納する（ステップＳ１７）。また、候補領域ｒ１＿１は複数の処理対象領域と重複するので、発見部１２２は、候補領域ｒ１＿１を交差集合１１６に格納する。ここで、候補領域ｒ１＿１を交差集合１１６に格納するのは、以後の処理において抽出される候補領域と候補領域ｒ１＿１とが交差する可能性があるからである。
【００６１】
図１６及び図１７の説明に移行する。発見部１２２は、処理対象集合１１２から処理対象領域Ｒ１＿２を取得し、取得した処理対象領域Ｒ１＿２のうちスコアが最大の領域ｒ１＿２を抽出する（ステップＳ１８）。発見部１２２は、抽出した候補領域ｒ１＿２と、候補領域ｒ１＿２を抽出した処理対象領域Ｒ１＿２とを対応付けて対応テーブル１１７に格納する。なお、領域ｒ１＿２は、水平方向の座標（ｘ１４，ｘ１５）と垂直方向の座標（ｙ１４，ｙ１５）とを用いると、下記のように表現される。
ｒ１＿２：（ｘ１４，ｙ１４）−（ｘ１５，ｙ１５）
【００６２】
発見部１２２は、抽出した領域ｒ１＿２が交差集合１１６に含まれる候補領域ｒ４又はｒ１＿１と交差するか否かを判定する。図１６では、領域ｒ１＿２と候補領域ｒ１＿１とが交差するので、発見部１２２は、領域ｒ１＿２のスコアと候補領域ｒ１＿１のスコアとを比較する。図１７では、領域ｒ１＿２のスコアが候補領域ｒ１＿１のスコアより低い場合を説明する。この場合、発見部１２２は、対応テーブルを参照し、領域ｒ１＿２に対応する処理対象領域Ｒ１＿２を分割集合１１５に格納する（ステップＳ１９）。発見部１２２は、対応テーブル１１７より候補領域ｒ１＿２と対応する処理対象領域Ｒ１＿２の組を除外する。ここで、処理対象領域Ｒ１＿２を分割集合１１５に格納するのは、処理対象領域Ｒ１＿２のうち領域ｒ１＿２を除いた領域にｔｏｐ−４以降の領域が含まれる可能性があるからである。
【００６３】
図１８の説明に移行する。発見部１２２は、処理対象集合１１２から処理対象領域Ｒ１＿３を取得し、取得した処理対象領域Ｒ１＿３のうちスコアが最大の領域ｒ１＿３を抽出する（ステップＳ２０）。発見部１２２は、抽出した候補領域ｒ１＿３と、候補領域ｒ１＿３を抽出した処理対象領域Ｒ１＿３とを対応付けて対応テーブル１１７に格納する。なお、領域ｒ１＿３は、水平方向の座標（ｘ１６，ｘ１７）と垂直方向の座標（ｙ１６，ｙ１７）とを用いると、下記のように表現される。
ｒ１＿３：（ｘ１６，ｙ１６）−（ｘ１７，ｙ１７）
【００６４】
発見部１２２は、抽出した領域ｒ１＿２が交差集合１１６に含まれる候補領域ｒ４又はｒ１＿１と交差するか否かを判定する。図１８では、領域ｒ１＿３はいずれの候補領域とも交差しないので、発見部１２２は、領域ｒ１＿３を候補領域ｒ１＿３として候補集合１１４に格納する。
【００６５】
図１９及び図２０の説明に移行する。発見部１２２は、処理対象集合１１２から処理対象領域Ｒ１＿４を取得し、取得した処理対象領域Ｒ１＿４のうちスコアが最大の領域ｒ１＿４を抽出する（ステップＳ２１）。発見部１２２は、抽出した候補領域ｒ１＿４と、候補領域ｒ１＿４を抽出した処理対象領域Ｒ１＿４とを対応付けて対応テーブル１１７に格納する。なお、領域ｒ１＿４は、水平方向の座標（ｘ１８，ｘ１９）と垂直方向の座標（ｙ１８，ｙ１９）とを用いると、下記のように表現される。
ｒ１＿４：（ｘ１８，ｙ１８）−（ｘ１９，ｙ１９）
【００６６】
発見部１２２は、抽出した領域ｒ１＿４が交差集合１１６に含まれる候補領域ｒ４及びｒ１＿１と交差するか否かをそれぞれ判定する。図１９では、領域ｒ１＿４と候補領域ｒ４とが交差するので、発見部１２２は、領域ｒ１＿４のスコアと候補領域ｒ４のスコアとを比較する。図２０では、候補領域ｒ１＿４のスコアが候補領域ｒ４のスコアより高い場合を説明する。この場合、発見部１２２は、スコアが高い領域ｒ１＿４を候補領域ｒ１＿４として候補集合１１４に格納する（ステップＳ２２）。また、候補領域ｒ１＿４は複数の処理対象領域と重複するので、発見部１２２は、候補領域ｒ１＿４を交差集合１１６に格納する。一方、発見部１２２は、スコアが低い候補領域ｒ４を候補集合１１４及び交差集合１１６から除外する。また、発見部１２２は、対応テーブルを参照し、領域ｒ４に対応する処理対象領域Ｒ４を分割集合１１５に格納する。発見部１２２は、対応テーブル１１７より候補領域ｒ４と対応する処理対象領域Ｒ４の組を除外する。
【００６７】
図２１の説明に移行する。ここでは、候補集合１１４のうちスコアが最大の候補領域が候補領域ｒ１＿４である場合を説明する。この場合、発見部１２２は、候補集合１１４からスコアが最大の候補領域ｒ１＿４をｔｏｐ−３として選択し、選択したｔｏｐ−３を解集合１１３に格納する（ステップＳ２３）。また、発見部１２２は、候補領域ｒ１＿４を候補集合１１４から除外するとともに、対応テーブルを参照し、候補領域ｒ１＿４に対応する処理対象領域Ｒ１＿４を分割集合１１５に格納する。発見部１２２は、対応テーブル１１７より候補領域ｒ１＿４と対応する処理対象領域Ｒ１＿４の組を除外する。
【００６８】
図２２の説明に移行する。発見部１２２は、分割集合１１５から処理対象領域Ｒ１＿２を取得する。そして、発見部１２２は、処理対象領域Ｒ１＿２から処理対象領域Ｒ１＿２＿１〜Ｒ１＿２＿３を生成し、生成した処理対象領域Ｒ１＿２＿１〜Ｒ１＿２＿３を処理対象集合１１２に格納する（ステップＳ２４）。なお、処理対象領域Ｒ１＿２＿１〜Ｒ１＿２＿３は、水平方向の座標（ｘ０〜ｘ１３）と垂直方向の座標（ｙ０〜ｙ１２）とを用いると、下記のように表現される。
Ｒ１＿２＿１：（ｘ０，ｙ０）−（ｘ１２，ｙ４）
Ｒ１＿２＿２：（ｘ０，ｙ０）−（ｘ２，ｙ１２）
Ｒ１＿２＿３：（ｘ１３，ｙ０）−（ｘ２，ｙ４）
【００６９】
図２３の説明に移行する。発見部１２２は、分割集合１１５から処理対象領域Ｒ４を取得する。そして、発見部１２２は、処理対象領域Ｒ４から処理対象領域Ｒ４＿１〜Ｒ４＿３を生成し、生成した処理対象領域Ｒ４＿１〜Ｒ４＿３を処理対象集合１１２に格納する（ステップＳ２５）。なお、処理対象領域Ｒ４＿１〜Ｒ４＿３は、水平方向の座標（ｘ０〜ｘ１９）と垂直方向の座標（ｙ１〜ｙ１９）とを用いると、下記のように表現される。
Ｒ４＿１：（ｘ０，ｙ３）−（ｘ１８，ｙ１）
Ｒ４＿２：（ｘ１９，ｙ３）−（ｘ１，ｙ１）
Ｒ４＿３：（ｘ０，ｙ１９）−（ｘ１，ｙ１）
【００７０】
図２４の説明に移行する。発見部１２２は、分割集合１１５から処理対象領域Ｒ１＿４を取得する。そして、発見部１２２は、処理対象領域Ｒ１＿４から処理対象領域Ｒ１＿４＿１〜Ｒ１＿４＿４を生成し、生成した処理対象領域Ｒ１＿４＿１〜Ｒ１＿４＿４を処理対象集合１１２に格納する（ステップＳ２６）。なお、処理対象領域Ｒ１＿４＿１〜Ｒ１＿４＿４は、水平方向の座標（ｘ０〜ｘ１９）と垂直方向の座標（ｙ１〜ｙ１９）とを用いると、下記のように表現される。
Ｒ１＿４＿１：（ｘ０，ｙ５）−（ｘ１８，ｙ１）
Ｒ１＿４＿２：（ｘ０，ｙ５）−（ｘ２，ｙ１８）
Ｒ１＿４＿３：（ｘ１９，ｙ５）−（ｘ２，ｙ１）
Ｒ１＿４＿４：（ｘ０，ｙ１９）−（ｘ２，ｙ１）
【００７１】
このように、発見部１２２は、入力データ１１１からスコアが高い上位３件の領域ｔｏｐ−１〜ｔｏｐ−３を発見する。なお、上位４件目以降の領域をさらに発見する場合には、発見部１２２は、同様の処理を繰り返し実行する。
【００７２】
このように、発見部１２２は、処理対象となる領域のうち発見済みの解領域を除いた領域から次の順位の解領域を発見する処理と、複数の処理対象領域に跨る候補領域のみと交差するか否かを判定する処理とを繰り返し実行することで、上位ｋ件の領域を発見する。
【００７３】
図１の説明に戻る。出力制御部１２３は、出力装置１０２に各種情報を出力する。例えば、出力制御部１２３は、記憶部１１０から出力データ１１８を取得し、取得した出力データ１１８を出力装置１０２に出力する。
【００７４】
次に、実施例１に係る領域発見装置１００の処理手順について説明する。図２５は、実施例１に係る領域発見装置の処理手順を示すフローチャートである。図２５に示す処理は、例えば、受付部１２１がスコアの定義を受け付けたことを契機として実行される。
【００７５】
図２５に示すように、処理タイミングになると（ステップＳ１０１Ｙｅｓ）、発見部１２２は、処理対象集合１１２と、解集合１１３と、候補集合１１４と、分割集合１１５と、交差集合１１６とを空集合に初期化する（ステップＳ１０２）。そして、発見部１２２は、入力データ１１１から処理対象領域Ｒを生成し、処理対象集合１１２に格納する（ステップＳ１０３）。そして、発見部１２２は、領域発見処理を実行する（ステップＳ１０４）。
【００７６】
ここで、図２６を用いて、図２５のステップＳ１０４に示した領域発見処理の処理手順について説明する。図２６は、領域発見処理の処理手順を示すフローチャートである。
【００７７】
図２６に示すように、発見部１２２は、処理対象集合１１２から処理対象領域Ｒｉを一つ取得する（ステップＳ２０１）。発見部１２２は、処理対象領域Ｒｉのうちスコアが最大の候補領域ｒｉを抽出する（ステップＳ２０２）。そして、発見部１２２は、候補確定処理を実行する（ステップＳ２０３）。
【００７８】
ここで、図２７を用いて、図２６のステップＳ２０３に示した候補確定処理の処理手順について説明する。図２７は、候補確定処理の処理手順を示すフローチャートである。
【００７９】
図２７に示すように、発見部１２２は、ステップＳ２０２の処理により抽出した候補領域ｒｉと交差集合１１６に含まれる候補領域ｒｊとが交差するか否かを判定する（ステップＳ３０１）。候補領域ｒｉと候補領域ｒｊとが交差する場合には（ステップＳ３０１Ｙｅｓ）、発見部１２２は、候補領域ｒｉのスコアが候補領域ｒｊのスコアより高いか否かを判定する（ステップＳ３０２）。
【００８０】
候補領域ｒｉのスコアが候補領域ｒｊのスコアより高い場合には（ステップＳ３０２Ｙｅｓ）、発見部１２２は、候補領域ｒｊを候補集合１１４と交差集合１１６とから除外する（ステップＳ３０３）。そして、発見部１２２は、対応テーブル１１７を参照し、候補領域ｒｊに対応する処理対象領域Ｒｊを分割集合１１５に格納する（ステップＳ３０４）。また、発見部１２２は、対応テーブル１１７より候補領域ｒｊと対応する処理対象領域Ｒｊの組を除外する。
【００８１】
発見部１２２は、候補領域ｒｉを候補領域として確定し、候補集合１１４に格納する（ステップＳ３０５）。発見部１２２は、候補領域ｒｉが複数の処理対象領域と重複するか否かを判定する（ステップＳ３０６）。候補領域ｒｉが複数の処理対象領域と重複する場合には（ステップＳ３０６Ｙｅｓ）、発見部１２２は、候補領域ｒｉを交差集合１１６に格納し（ステップＳ３０７）、候補確定処理を終了する。
【００８２】
一方、候補領域ｒｉが複数の処理対象領域と重複しない場合には（ステップＳ３０６Ｎｏ）、発見部１２２は、候補確定処理を終了する。
【００８３】
一方、候補領域ｒｉのスコアが候補領域ｒｊのスコアより低い場合には（ステップＳ３０２Ｎｏ）、発見部１２２は、対応テーブル１１７を参照し、候補領域ｒｉに対応する処理対象領域Ｒｉを分割集合１１５に格納する（ステップＳ３０８）。また、発見部１２２は、対応テーブル１１７より候補領域ｒｉと対応する処理対象領域Ｒｉの組を除外する。
【００８４】
一方、候補領域ｒｉと候補領域ｒｊとが交差しない場合には（ステップＳ３０１Ｎｏ）、ステップＳ３０５の処理に移行する。
【００８５】
図２６の説明に戻る。発見部１２２は、処理対象集合１１２が空集合であるか否かを判定する（ステップＳ２０４）。処理対象集合１１２が空集合でない場合には（ステップＳ２０４Ｎｏ）、発見部１２２は、ステップＳ２０１の処理に移行し、ステップＳ２０１からステップＳ２０４までの処理を処理対象集合１１２が空集合になるまで繰り返す。
【００８６】
一方、処理対象集合１１２が空集合である場合には（ステップＳ２０４Ｙｅｓ）、発見部１２２は、候補集合１１４のうちスコアが最大の候補領域ｒｉを解領域ｒｉとして選択し、解集合１１３に格納する（ステップＳ２０５）。発見部１２２は、対応テーブル１１７を参照し、解領域ｒｉに対応する処理対象領域Ｒｉを分割集合１１５に格納する（ステップＳ２０６）。また、発見部１２２は、対応テーブル１１７より候補領域ｒｉと対応する処理対象領域Ｒｉの組を除外する。そして、発見部１２２は、分割処理を実行する（ステップＳ２０７）。
【００８７】
ここで、図２８を用いて、図２６のステップＳ２０７に示した分割処理の処理手順について説明する。図２８は、分割処理の処理手順を示すフローチャートである。
【００８８】
図２８に示すように、発見部１２２は、分割集合１１５から処理対象領域Ｒｉを一つ取得する（ステップＳ４０１）。発見部１２２は、処理対象領域Ｒｉから一つ又は複数の矩形領域を生成する（ステップＳ４０２）。
【００８９】
発見部１２２は、生成した矩形領域を処理対象領域として処理対象集合１１２に格納する（ステップＳ４０３）。発見部１２２は、分割集合１１５が空集合であるか否かを判定する（ステップＳ４０４）。分割集合１１５が空集合である場合には（ステップＳ４０４Ｙｅｓ）、発見部１２２は、分割処理を終了する。
【００９０】
一方、分割集合１１５が空集合でない場合には（ステップＳ４０４Ｎｏ）、発見部１２２は、ステップＳ４０１の処理に移行し、ステップＳ４０１からステップＳ４０４までの処理を分割集合１１５が空集合になるまで繰り返す。
【００９１】
図２５の説明に戻る。発見部１２２は、ステップＳ１０４の領域発見処理により発見された解領域の数が所定数に到達したか否かを判定する（ステップＳ１０５）。解領域の数が所定数に到達した場合には（ステップＳ１０５Ｙｅｓ）、発見部１２２は、解集合１１３に含まれる領域の情報に基づいて、出力データ１１８を生成する（ステップＳ１０６）。
【００９２】
一方、解領域の数が所定数に到達していない場合には（ステップＳ１０５Ｎｏ）、発見部１２２は、ステップＳ１０４の領域発見処理に移行し、ステップＳ１０４及びステップＳ１０５の処理を解領域の数が所定数に到達するまで繰り返す。
【００９３】
なお、上記の処理手順は、上記の順番に限定されるものではなく、処理内容を矛盾させない範囲で適宜変更されても良い。例えば、ステップＳ２０７において説明した分割処理は、必ずしもステップＳ２０６の処理の後に実行されなくても良く、ステップＳ１０５の処理において否定判定された後に実行されても良い。
【００９４】
次に、実施例１に係る領域発見装置１００の効果について説明する。領域発見装置１００は、２次元座標に分布可能な複数の点を示すデータを記憶する。領域発見装置１００は、記憶した複数の点の集合を含む処理対象領域から、点の評価値に基づいて算出されるスコアが最も高い矩形領域を解の候補である候補領域として抽出する。領域発見装置１００は、抽出した候補領域と、他の候補領域のうち複数の処理対象領域と重複する候補領域とが交差するか否かを判定する。領域発見装置１００は、交差する場合には、抽出した候補領域及び他の候補領域のうちスコアが低い候補領域を候補から除外するとともにスコアが高い候補領域を確定し、交差しない場合には、抽出した候補領域を確定する。領域発見装置１００は、確定した候補領域のうち、スコアが最も高い候補領域を解領域として選択する。領域発見装置１００は、選択した解領域が抽出された処理対象領域のうち解領域を除いた領域、および、除外した候補領域が抽出された処理対象領域のうち除外した候補領域を除いた領域から、一つ又は複数の矩形領域を処理対象領域として生成する。領域発見装置１００は、所定数の解領域を選択するまで、生成した処理対象領域から候補領域を抽出し、候補領域を確定し、解領域を選択する。このように、領域発見装置１００は、処理対象領域のうち発見済みの解領域を除いた領域から次の順位の候補領域を抽出するので、抽出した候補領域と解領域との交差判定を不要とすることができ、交差なし上位ｋ件領域発見問題を効率よく解くことができる。
【００９５】
また、領域発見装置１００は、複数の処理対象領域と重複する候補領域を一時記憶しておき、抽出した候補領域と一時記憶した候補領域とを交差判定するので、交差判定の回数を減らすことができ、交差なし上位ｋ件領域発見問題を効率よく解くことができる。
【００９６】
具体的には、例えば、１００個の点データを含む集合から上位３件の領域を発見するまでに要する時間は、従来技術では約１時間強（４３００秒）であるのに対して、領域発見装置１００では約１．０３秒である。また、例えば、２００個の点データを含む集合から上位３件の領域を発見するまでに要する時間は、従来技術では約２０時間であるのに対して、領域発見装置１００では約５．７４秒である。また、例えば、１０００個の点データを含む集合から上位３件の領域を発見するまでに要する時間は、従来技術では計測不能であるのに対して、領域発見装置１００では約４４５秒である。このように、従来技術が実用に耐えうるものではないのに対して、領域発見装置１００は、交差なし上位ｋ件領域発見問題を効率よく解くことができる。
【００９７】
ところで、図１に示した領域発見装置１００の構成は一例であり、領域発見装置１００は、必ずしも図１に示した各処理部を有していなくても良い。例えば、図２９に示すように、領域発見装置２００は、記憶部２１０と、抽出部２２０と、確定部２３０と、選択部２４０と、生成部２５０と、制御部２６０とを有する。なお、図２９に示す記憶部２１０は、図１に示した入力データ１１１に対応する。また、図２９に示す抽出部２２０、確定部２３０、選択部２４０、生成部２５０及び制御部２６０は、図１に示した発見部１２２に対応する。また、図２９は、実施例１に係る領域発見装置の構成の一例を示す図である。
【００９８】
すなわち、記憶部２１０は、２次元座標に分布可能な複数の点を示すデータを記憶する。抽出部２２０は、記憶部２１０に記憶された複数の点の集合を含む処理対象領域から、点の評価値に基づいて算出されるスコアが最も高い矩形領域を解の候補である解候補として抽出する。確定部２３０は、抽出部２２０により抽出された解候補と、他の解候補のうち複数の処理対象領域と重複する解候補とが交差するか否かを判定する。確定部２３０は、交差する場合には、抽出された解候補及び他の解候補のうちスコアが低い解候補を解候補から除外するとともにスコアが高い解候補を解候補として確定し、交差しない場合には、抽出された解候補を解候補として確定する。選択部２４０は、確定部２３０により確定された解候補のうち、スコアが最も高い解候補を解領域として選択する。生成部２５０は、選択部２４０により選択された解領域が抽出された処理対象領域のうち解領域を除いた領域から、一つ又は複数の矩形領域を処理対象領域として生成する。また、生成部２５０は、確定部２３０により除外された解候補が抽出された処理対象領域のうち除外された解候補を除いた領域から、一つ又は複数の矩形領域を処理対象領域として生成する。制御部２６０は、選択部２４０により所定数の解領域が選択されるまで、生成部２５０により生成された処理対象領域から抽出部２２０により解候補を抽出させ、確定部２３０により解候補を確定させ、選択部２４０により解領域を選択させる。
【実施例２】
【００９９】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、その他の実施例にて実施されても良い。そこで、以下では、その他の実施例について説明する。
【０１００】
例えば、上述した実施例１では、スコアが高い順に領域を発見する場合を説明したが、本発明はこれに限定されるものではない。例えば、領域発見装置１００，２００は、スコアが低い順に領域を発見するようにしても良い。つまり、領域発見装置２００が有する抽出部２２０は、記憶部２１０に記憶された複数の点の集合を含む処理対象領域から、点の評価値に基づいて算出されるスコアが最も低い矩形領域を解の候補である解候補として抽出する。確定部２３０は、抽出部２２０により抽出された解候補と、他の解候補のうち複数の処理対象領域と重複する解候補とが交差するか否かを判定する。確定部２３０は、交差する場合には、抽出された解候補及び他の解候補のうちスコアが高い解候補を解候補から除外するとともにスコアが低い解候補を解候補として確定し、交差しない場合には、抽出された解候補を解候補として確定する。選択部２４０は、確定部２３０により確定された解候補のうち、スコアが最も低い解候補を解領域として選択する。
【０１０１】
また、例えば、上述した実施例１では、スコアの定義が各点データの評価値の総和である場合を説明したが、本発明はこれに限定されるものではない。例えば、スコアの定義は、特定の評価値を有する点データの数の総和としても良い。つまり、領域発見装置１００は、各点データが評価値として「１」、「２」及び「３」のうちいずれかの値を有する場合に、例えば、評価値「２」を有する点データの数の総和をスコアとして算出するようにしても良い。
【０１０２】
また、例えば、実施例１において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。例えば、図２５に示した処理は、スコアの定義を受け付けたことを契機として実行されると説明したが、領域発見装置１００を利用する利用者が手動的に任意のタイミングで実行しても良い。この他、上述文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。図３に示す例では、処理対象集合１１２は、「ｌｅｆｔＬｏｗ」と、「ｒｉｇｈｔＵｐ」とを対応付けた情報を含むと説明したが、「ｌｅｆｔＵｐ」と、「ｒｉｇｈｔＬｏｗ」とを対応付けた情報を含むものとしても良い。つまり、矩形領域の表現方法は、左上の座標と右下の座標とで表現されても良い。
【０１０３】
また、図１，２９に示した領域発見装置１００，２００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、領域発見装置１００，２００の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、図１に示した処理対象集合１１２、解集合１１３、候補集合１１４、分割集合１１５、交差集合１１６及び対応テーブル１１７を記憶部１１０が有している必要は無い。制御部１２０の内部メモリが、処理対象集合１１２、解集合１１３、候補集合１１４、分割集合１１５、交差集合１１６及び対応テーブル１１７をそれぞれ有していても良い。
【０１０４】
また、領域発見装置１００，２００は、領域発見装置１００，２００の各機能を既知の情報処理装置に搭載することによって実現することもできる。既知の情報処理装置は、例えば、パーソナルコンピュータ、ワークステーション、携帯電話、Personal  Handy-phone  System（ＰＨＳ）端末、移動体通信端末またはPersonal  Digital  Assistant（ＰＤＡ）などの装置に対応する。
【０１０５】
図３０は、領域発見プログラムを実行するコンピュータの一例を示す図である。図３０に示すように、コンピュータ３００は、各種演算処理を実行するＣＰＵ３０１と、ユーザからデータの入力を受け付ける入力装置３０２と、モニタ３０３とを有する。また、コンピュータ３００は、記憶媒体からプログラム等を読み取る媒体読み取り装置３０４と、他の装置とデータの授受を行うネットワークインターフェース装置３０５とを有する。また、コンピュータ３００は、各種情報を一時記憶するＲＡＭ（Random  Access  Memory）３０６と、ハードディスク装置３０７を有する。また、各装置３０１〜３０７は、バス３０８に接続される。
【０１０６】
ハードディスク装置３０７は、図１に示した発見部１２２、図２９に示した抽出部２２０、確定部２３０、選択部２４０、生成部２５０及び制御部２６０の各処理部と同様の機能を有する領域発見プログラム３０７ａを記憶する。また、ハードディスク装置３０７は、領域発見プログラム３０７ａを実現するための各種データ３０７ｂを記憶する。この各種データ３０７ｂは、例えば、２次元座標に分布可能な複数の点を示すデータを含む。
【０１０７】
ＣＰＵ３０１が領域発見プログラム３０７ａをハードディスク装置３０７から読み出してＲＡＭ３０６に展開して実行することにより、領域発見プログラム３０７ａは、領域発見プロセス３０６ａとして機能する。すなわち、領域発見プログラム３０７ａは、図１に示した発見部１２２、図２９に示した抽出部２２０、確定部２３０、選択部２４０、生成部２５０及び制御部２６０の各処理部と同様のプロセスとして機能する。
【０１０８】
なお、上記の領域発見プログラム３０７ａは、必ずしもハードディスク装置３０７に記憶されている必要はない。例えば、コンピュータが読み取り可能な記録媒体に記憶されたプログラムを、コンピュータ３００が読み出して実行するようにしても良い。コンピュータが読み取り可能な記録媒体は、例えば、ＣＤ−ＲＯＭやＤＶＤディスク、ＵＳＢメモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリ、ハードディスクドライブ等が対応する。また、公衆回線、インターネット、ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等に接続された装置にこのプログラムを記憶させておき、コンピュータ３００がこれらからプログラムを読み出して実行するようにしても良い。
【０１０９】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１１０】
（付記１）２次元座標に分布可能な複数の点を示すデータを記憶する記憶部と、
前記記憶部に記憶された複数の点の集合を含む処理対象領域から、前記点の評価値に基づいて算出されるスコアが最も高いもしくは低い矩形領域を解の候補である解候補として抽出する抽出部と、
前記抽出部により抽出された解候補と、他の解候補のうち複数の処理対象領域と重複する解候補とが交差するか否かを判定し、交差する場合には、当該解候補及び当該他の解候補のうち前記スコアが低いもしくは高い解候補を解候補から除外するとともに前記スコアが高いもしくは低い解候補を解候補として確定し、交差しない場合には、当該解候補を解候補として確定する確定部と、
前記確定部により確定された解候補のうち、前記スコアが最も高いもしくは低い解候補を解領域として選択する選択部と、
前記選択部により選択された解領域が抽出された前記処理対象領域のうち当該解領域を除いた領域、および、前記確定部により除外された解候補が抽出された前記処理対象領域のうち当該解候補を除いた領域から、一つ又は複数の矩形領域を処理対象領域として生成する生成部と、
前記選択部により所定数の解領域が選択されるまで、前記生成部により生成された処理対象領域から前記抽出部により解候補を抽出させ、前記確定部により解候補を確定させ、前記選択部により解領域を選択させる制御部と
を備えたことを特徴とする領域発見装置。
【０１１１】
（付記２）前記複数の処理対象領域と重複する解候補を一時記憶する一時記憶部をさらに備え、
前記確定部は、前記抽出部により抽出された解候補と、前記一時記憶部により一時記憶された解候補とが交差するか否かを判定し、交差する場合には、当該抽出された解候補及び当該一時記憶された解候補のうち前記スコアが低いもしくは高い解候補を解候補から除外するとともに前記スコアが高いもしくは低い解候補を解候補として確定し、交差しない場合には、当該解候補を解候補として確定することを特徴とする付記１に記載の領域発見装置。
【０１１２】
（付記３）コンピュータに、
２次元座標に分布可能な複数の点を示すデータを記憶する記憶部に記憶された複数の点の集合を含む処理対象領域から、前記点の評価値に基づいて算出されるスコアが最も高いもしくは低い矩形領域を解の候補である解候補として抽出し、
前記解候補を抽出する処理により抽出された解候補と、他の解候補のうち複数の処理対象領域と重複する解候補とが交差するか否かを判定し、交差する場合には、当該解候補及び当該他の解候補のうち前記スコアが低いもしくは高い解候補を解候補から除外するとともに前記スコアが高いもしくは低い解候補を解候補として確定し、交差しない場合には、当該解候補を解候補として確定し、
前記解候補を確定する処理により確定された解候補のうち、前記スコアが最も高いもしくは低い解候補を解領域として選択し、
前記解領域を選択する処理により選択された解領域が抽出された前記処理対象領域のうち当該解領域を除いた領域、および、前記解候補を確定する処理により除外された解候補が抽出された前記処理対象領域のうち当該解候補を除いた領域から、一つ又は複数の矩形領域を処理対象領域として生成し、
前記解領域を選択する処理により所定数の解領域が選択されるまで、前記処理対象領域を生成する処理により生成された処理対象領域から前記解候補を抽出する処理により解候補を抽出させ、前記解候補を確定する処理により解候補を確定させ、前記解領域を選択する処理により解領域を選択させる
ことを特徴とする領域発見プログラム。
【０１１３】
（付記４）前記解候補を抽出する処理により抽出された解候補が複数の処理対象領域と重複する場合には、当該解候補を一時記憶部に一時記憶し、
前記解候補を確定する処理は、前記解候補を抽出する処理により抽出された解候補と、前記一時記憶部に一時記憶された解候補とが交差するか否かを判定し、交差する場合には、当該抽出された解候補及び当該一時記憶された解候補のうち前記スコアが低いもしくは高い解候補を解候補から除外するとともに前記スコアが高いもしくは低い解候補を解候補として確定し、交差しない場合には、当該抽出された解候補を解候補として確定することを特徴とする付記３に記載の領域発見プログラム。
【０１１４】
（付記５）コンピュータが実行する領域発見方法であって、
２次元座標に分布可能な複数の点を示すデータを記憶する記憶部に記憶された複数の点の集合を含む処理対象領域から、前記点の評価値に基づいて算出されるスコアが最も高いもしくは低い矩形領域を解領域として抽出し、
前記処理対象領域のうち前記解領域を除いた領域から一つ又は複数の矩形領域を処理対象領域として生成し、
前記処理対象領域を生成する処理により生成された処理対象領域から、当該処理対象領域ごとに、前記スコアが最も高いもしくは低い矩形領域を解候補として抽出し、
前記解候補を抽出する処理により抽出された解候補が複数の処理対象領域と重複する場合には、当該解候補を一時記憶部に一時記憶し、
前記解候補を抽出する処理により抽出された解候補と、前記一時記憶された解候補とが交差するか否かを判定し、交差する場合には、当該抽出された解候補及び当該一時記憶された解候補のうち前記スコアが低いもしくは高い解候補を解候補から除外するとともに前記スコアが高いもしくは低い解候補を解候補として確定し、交差しない場合には、当該抽出された解候補を解候補として確定し、
前記解候補を確定する処理により確定された解候補のうち、前記スコアが最も高いもしくは低い解候補を解領域として選択し、
前記解領域を選択する処理により選択された解領域が抽出された前記処理対象領域のうち当該解領域を除いた領域、および、前記解候補を確定する処理により除外された解候補が抽出された前記処理対象領域のうち当該解候補を除いた領域から、一つ又は複数の矩形領域を処理対象領域として生成する
ことを特徴とする領域発見方法。
【符号の説明】
【０１１５】
１００      領域発見装置
１０１      入力装置
１０２      出力装置
１１０      記憶部
１１１      入力データ
１１２      処理対象集合
１１３      解集合
１１４      候補集合
１１５      分割集合
１１６      交差集合
１１７      対応テーブル
１１８      出力データ
１２０      制御部
１２１      受付部
１２２      発見部
１２３      出力制御部
２００      領域発見装置
２１０      記憶部
２２０      抽出部
２３０      確定部
２４０      選択部
２５０      生成部
２６０      制御部
３００      コンピュータ
３０１      ＣＰＵ
３０２      入力装置
３０３      モニタ
３０４      媒体読み取り装置
３０５      ネットワークインターフェース装置
３０６      ＲＡＭ
３０６ａ      領域発見プロセス
３０７      ハードディスク装置
３０７ａ      領域発見プログラム
３０７ｂ      各種データ
３０８      バス
【図１】
0005510341.tif 000002
【図２】
0005510341.tif 000003
【図３】
0005510341.tif 000004
【図４】
0005510341.tif 000005
【図５】
0005510341.tif 000006
【図６】
0005510341.tif 000007
【図７】
0005510341.tif 000008
【図８】
0005510341.tif 000009
【図９】
0005510341.tif 000010
【図１０】
0005510341.tif 000011
【図１１】
0005510341.tif 000012
【図１２】
0005510341.tif 000013
【図１３】
0005510341.tif 000014
【図１４】
0005510341.tif 000015
【図１５】
0005510341.tif 000016
【図１６】
0005510341.tif 000017
【図１７】
0005510341.tif 000018
【図１８】
0005510341.tif 000019
【図１９】
0005510341.tif 000020
【図２０】
0005510341.tif 000021
【図２１】
0005510341.tif 000022
【図２２】
0005510341.tif 000023
【図２３】
0005510341.tif 000024
【図２４】
0005510341.tif 000025
【図２５】
0005510341.tif 000026
【図２６】
0005510341.tif 000027
【図２７】
0005510341.tif 000028
【図２８】
0005510341.tif 000029
【図２９】
0005510341.tif 000030
【図３０】
0005510341.tif 000031
【図３１】
0005510341.tif 000032
【図３２】
0005510341.tif 000033
【図３３】
0005510341.tif 000034
【図３４】
0005510341.tif 000035
【図３５】
0005510341.tif 000036