"正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納する座標データ取得手段と、前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納する境界線候補選択手段と、前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力する矩形領域検出手段と、を備える矩形領域検出装置。請求項1に記載の矩形領域検出装置であって、前記境界線候補選択手段は、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号及び値が同一である座標データが連続する数に応じて増減する指標値を算出する手段である、矩形領域検出装置。請求項1又は2に記載の矩形領域検出装置であって、前記境界線候補選択手段は、前記座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数、又は前記座標成分が隣接し且つ前記重み値の符号及び値が同一である座標データが連続する数が増加するほど、また該連続する座標グループ数が少ないほど、減少する傾向の前記指標値を算出し、該算出した指標値を各直線について合計し、該合計した値が最も小さくなった直線を選択する手段である、矩形領域検出装置。請求項3に記載の矩形領域検出装置であって、前記指標値は、Ni×-Σk{gi,k/Ni×loggi,k/Ni}で表され、該式中、kは重み値の符号、又は符号及び値であり、iは矩形領域の識別子であり、Niは矩形領域内の座標データ数であり、gi,kは前記座標成分が隣接し且つ重み値が同一種類である座標が連続する数である、矩形領域検出装置。請求項1ないし4のいずれか1項に記載の矩形領域検出装置であって、前記境界線候補選択手段は、前記二次元平面における第1の座標軸に平行な直線を選択する処理と、該第1の座標軸に直交する第2の座標軸に平行な直線を選択する処理を、交互に行う手段である、矩形領域検出装置。請求項1ないし5のいずれか1項に記載の矩形領域検出装置であって、前記境界線候補選択手段は、前記二次元平面上で平行な直線を複数設定する際に、既に選択した直線を用いて区画される矩形領域のうち、座標データ数が最大の矩形領域内を前記平行な複数の直線が通るように、前記平行な直線を複数設定する手段である、矩形領域検出装置。正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納するステップと、前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納するステップと、前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力するステップと、をコンピュータが実行する矩形領域検出方法。正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納する処理と、前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納する処理と、前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力する処理と、をコンピュータに実行させるプログラム。ところで、非特許文献1では、最適解最適矩形を網羅的に求める手順が示されている。網羅的に求める手順とは、座標間を通る全てのx方向及びy方向の直線を境界線として設定され得る矩形領域、すなわち、考え得る全ての矩形領域について重み値の合計を求め、合計が最大値となる矩形領域を探索する手順である。しかしながら、最適解を網羅的に求める手順を採用する場合、座標の数nが多くなると、計算量が多くなるために迅速な処理を行うことができない可能性がある。具体的には、最適解を網羅的に求める手順では、時間計算量はOn2logn、空間計算量はOnというオーダーを示しており、このことから、座標の数nの増加に応じて特に時間計算量の増加率が大きいことが判る。本発明はこのような課題を解決するためのものであり、矩形領域検出問題において矩形領域を絞り込むための境界線候補を迅速且つ適切に選択することが可能な矩形領域検出装置、矩形領域検出方法、及びプログラムを提供することを、主たる目的とする。上記目的を達成するための第1の態様は、正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納する座標データ取得手段と、前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納する境界線候補選択手段と、前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力する矩形領域検出手段と、を備える矩形領域検出装置である。本発明によれば、矩形領域検出問題において矩形領域を絞り込むための境界線候補を迅速且つ適切に選択することが可能な矩形領域検出装置、矩形領域検出方法、及びプログラムを提供することができる。以下、本発明を実施するための形態について、添付図面を参照しながら実施例を挙げて説明する。以下、図面を参照し、本発明の一実施例に係る矩形領域検出装置、矩形領域検出方法、及びプログラムについて説明する。[ハードウエア構成]図2は、本発明の一実施例に係る矩形領域検出装置1のハードウエア構成例である。矩形領域検出装置1は、例えば、CPUCentralProcessingUnit10と、ドライブ装置12と、補助記憶装置16と、メモリ装置18と、インタフェース装置20と、入力装置22と、ディスプレイ装置24と、を備える情報処理装置である。これらの構成要素は、バスやシリアル回線等を介して接続されている。CPU10は、例えば、プログラムカウンタや命令デコーダ、各種演算器、LSULoadStoreUnit、汎用レジスタ等を有するプロセッサである。ドライブ装置12は、記憶媒体14からプログラムやデータを読み込み可能な装置である。プログラムを記録した記録媒体14がドライブ装置12に装着されると、プログラムが記録媒体14からドライブ装置12を介して補助記憶装置16にインストールされる。記録媒体14は、例えば、CD-ROM、DVDディスク、USBメモリ等の可搬型の記録媒体である。また、補助記憶装置16は、例えば、HDDHardDiskDriveやフラッシュメモリである。プログラムのインストールは、上記のように記憶媒体14を用いる他、インタフェース装置20がネットワークを介して他のコンピュータよりダウンロードし、補助記憶装置16にインストールすることによって行うこともできる。ネットワークは、インターネット、LANLocalAreaNetwork、携帯電話の電波網等である。また、プログラムは、情報処理装置の出荷時に、予め補助記憶装置16やROMReadOnlyMemory等に格納されていてもよい。このようにしてインストール又は予め格納されたプログラムをCPU10が実行することにより、図1に示す態様の情報処理装置が、本実施例の矩形領域検出装置1として機能することができる。メモリ装置18は、例えば、RAMRandomAccessMemoryやEEPROMElectricallyErasableandProgrammableReadOnlyMemoryである。インタフェース装置20は、上記ネットワークとの接続等を制御する。入力装置22は、例えば、キーボードやマウス、タッチパッド、タッチパネル、マイク等である。また、ディスプレイ装置24は、例えば、LCDLiquidCrystalDisplayやCRTCathodeRayTube等の表示装置である。矩形領域検出装置1は、ディスプレイ装置24の他、プリンタ、スピーカ等の他の種類の出力装置を備えてもよい。[機能構成]図3は、本実施例の矩形領域検出装置1の機能構成例である。矩形領域検出装置1は、マスター制御部30と、入力制御部32と、出力制御部34と、境界線候補選択部36と、矩形領域検出部38と、を備える。これらの機能ブロックは、補助記憶装置16等に格納されたプログラムソフトウエアをCPU10が実行することにより機能する。マスター制御部30は、以下に説明するような各機能ブロックの全体動作を制御する。入力制御部32は、矩形領域検出問題を規定する各種データを、ドライブ装置12やインタフェース装置20、入力装置22等を介して取得し、メモリ装置18又は補助記憶装置16に格納する。矩形領域検出問題を規定する各種データは、重み値が付与された複数の座標データ、二次元平面の外縁線座標データ、分割数上限数r等を含む。出力制御部34は、境界線候補選択部36によって選択された境界線候補をメモリ装置18又は補助記憶装置16から読み出し、ドライブ装置12やインタフェース装置20、ディスプレイ装置24等を介して外部に出力する。この他、境界線候補は、矩形領域検出部38によって読み出され、矩形領域の検出に用いられる。なお、境界線候補の外部への出力を行わず、専ら矩形領域検出部38によって用いられるものとしてもよい。境界線候補選択部36は、更に、縦方向分割処理部36Aと、横方向分割処理部36Bと、を有する。境界線候補選択部36は、例えば、縦方向分割処理部36Aと横方向分割処理部36Bを交互に呼び出して機能させることによって、縦方向及び横方向に沿って延びる複数の境界線候補を選択し、メモリ装置18又は補助記憶装置16に格納する。以下、縦方向分割処理部36A、及び横方向分割処理部36Bによる分割処理境界線候補選択処理について説明する。図4は、入力制御部32によって取得され、メモリ装置18又は補助記憶装置16に格納された複数の座標データを示す図である。図示するように、各座標データは、x座標とy座標と重み値が対応付けられており、座標一個に対して一行が割り当てられている。本実施例では、簡明のために重み値は1と-1の二値をとり得るものとする。図5は、入力制御部32によって取得され、メモリ装置18又は補助記憶装置16に格納された二次元平面の外縁線座標データを示す図である。図示するように、二次元平面の外縁線座標データは、左辺のx座標、右辺のx座標、下辺のy座標、上辺のy座標が特定されたデータである。図6は、本実施例の矩形領域検出装置1により実行される処理の概要を示すフローチャートである。まず、マスター制御部30は、矩形領域検出問題を規定する各種データを取得してメモリ装置18又は補助記憶装置16に格納するように、入力制御部32に指示するS100。次に、マスター制御部30は、縦方向分割処理と横方向分割処理を繰り返すことにより複数の境界線候補を求めてメモリ装置18又は補助記憶装置16に格納するように、境界線候補選択部36に指示するS102。そして、マスター制御部30は、メモリ装置18又は補助記憶装置16に格納された境界線候補を出力するように、出力制御部34に指示するS104。[分割手法]縦方向分割処理部36Aは、以下に説明するような手法に基づき、二次元平面を縦方向y軸に平行な方向の直線で分割し、当該直線を境界線候補として選択する縦方向分割処理。縦方向分割処理部36Aは、まず、二次元平面上でy軸に平行な直線を複数設定する。この直線設定に係る詳細なルールについては後述する。そして、設定した各直線を境界線とする複数の矩形領域を設定する。図7は、縦方向分割処理部36Aが直線を複数設定し、設定した直線を境界線の一つとする矩形領域群を設定する様子を簡単に示す図である。図中、縦方向分割処理部36Aが今回の分割において設定する直線をL1、L2とし、過去に分割に用いられた直線をP1、P2、P3、P4と表記した。図示するように、縦方向分割処理部36Aは、元の二次元平面が既に幾つかに分割されている場合には、分割に用いられた直線を新たな矩形領域の境界線として用いる。更に、縦方向分割処理部36Aは、複数設定した直線毎に、設定した直線を境界線の一つとする矩形領域のそれぞれについて、次式2で示すようなスコア値Hjを算出する。式中、添え字jは領域生成の元となった直線を識別するための識別子であり、添え字iは当該直線から生成された矩形領域を識別するための識別子であり、Niは矩形領域内の座標の数であり、添え字kは重み値の種類を識別するための識別子である。gi,kの内容については、以下に述べる。Hj=Σi[Ni×-Σk{gi,k/Ni×loggi,k/Ni}]...2縦方向分割処理部36Aは、gi,kを求める際に、例えば、矩形領域内の座標データをy座標に関して昇順又は降順に並べ替えたソートデータを生成して行う。そして、並べ替えたソートデータにおいて、重み値が同一種類である座標が連続する数を、重み値の種類毎に全て抽出する。ここで、重み値が同一種類であるとは、1符号すなわち正の値であるか、負の値であるかが一致していることを意味するものであってもよいし、2符号と値の双方が一致していることを意味するものであってもよい。本実施例では、重み値は1と-1の二値をとるため、いずれの場合でも結果は同じである。図8は、ある入力領域内の座標データと、これをy座標に関して並べ替えを行ったソートデータを示し、更にソートデータからgi,1、及びgi,-1が算出される様子を示す図である。このように、gi,kは、分割の元となった直線に平行な座標軸上記ではy軸に関する座標成分y座標が隣接し、且つ重み値が同一種類である座標が連続する数である。なお、ソートデータを用いてgi,kを導出するのはあくまで一例であり、組み込み関数、或いはy座標の小さい順或いは大きい順に座標を抽出して重み値の種類毎にカウントするアルゴリズム等を用いてgi,kを導出しても構わない。また、上式2の右項gi,k/Ni×loggi,k/Niから判るように、スコア値Hjは、gi,kの値が大きい程又は小さい程、すなわち値のばらつきが大きい程、小さくなる傾向を有する指標値である。gi,kの上限はNiであり、[gi,k/Ni→1]又は[gi,k/Ni→0]ならば、[gi,k/Ni×loggi,k/Ni→0]だからである。また、スコア値Hjは、重み値が同一種類であり連続する座標グループ数gi,kとしてカウントされるグループ数が小さい程、小さくなる傾向を有する。従って、スコア値Hjは、分割の元となった直線jに平行な座標軸に関する座標成分が隣接し、且つ重み値が同一種類である座標が連続する数が増加するほど、また重み値が同一種類であり連続する座標グループ数が少ないほど減少する傾向の指標値の合計値である。指標値は、式2中、Σi以外の部分を指す。そして、縦方向分割処理部36Aは、スコア値Hjが最も小さくなった直線jを選択し、境界線候補としてメモリ装置18又は補助記憶装置16に格納する。すなわち、縦方向分割処理部36Aは、分割の結果、直線から生成された矩形領域において、重み値が同一種類の座標が領域内で固まって存在している傾向を示す直線を、境界線候補として選択する。これによって、選択した境界線候補が、矩形領域検出問題の最適矩形として求められるべき矩形領域の境界線に一致する可能性を高めることができる。このことの検証については、後述する。縦方向分割処理部36Aによる縦方向分割について、図を用いて更に説明する。図9は、縦方向分割処理部36Aにより縦方向の直線が二本L1、L2設定された様子を示す図である。図中、○は重み値が1の座標であり、□は重み値が-1の座標である。図9Aに示す直線L1の位置から算出されるスコア値H1は、次式3のようになる。ここで、左側の部分領域をS1i=1、右側の部分領域をS2i=2とすると、N1=4、N2=6である。また、重み値が同一種類の座標は、下側からカウントするものとする。H1=N1×-Σk{g1,k/N1×logg1,k/N1}N2×-Σk{g2,k/N2×logg2,k/N2}=4×-{1/4×log1/41/4×log1/42/4×log2/4}6×-{1/6×log1/61/6×log1/63/6×log3/61/6×log1/6}=16.75...3また、図9Bに示す直線L2の位置から算出されるスコア値H2は、次式4のようになる。同様に、左側の部分領域をS1i=1、右側の部分領域をS2i=2とすると、N1=5、N2=5である。H2=N1×-Σk{g1,k/N1×logg2,k/N1}N2×-Σk{g2,k/N2×logg2,k/N2}=5×-{1/5×log1/52/5×log2/52/5×log2/5}5×-{1/5×log1/53/5×log3/51/5×log1/5}=14.46...4この結果、図9に示す例では、図9Bで示す直線L2が選択されることになる。以上、縦方向分割処理部36Aによる縦方向y軸方向の分割について説明したが、横方向分割処理部36Bによる横方向x軸方向の分割は、縦横を入れ替えるだけで原理的には全く同じである。従って、横方向の分割手法については説明を省略する。縦方向分割処理部36Aや横方向分割処理部36Bによって選択された境界線候補は、例えば図10に例示する区画リストの形式でメモリ装置18又は補助記憶装置16に格納される。図10は、縦方向分割処理部36Aや横方向分割処理部36Bによって更新される区画リストLの一例である。図示するように、区画リストLは、分割を繰り返すことによって生じた最小単位の他の領域を含まない矩形領域を、四辺の座標値で特定して列挙したものである。縦方向分割処理部36Aや横方向分割処理部36Bが分割を行うと、分割された元の矩形領域は区画リストLから除外され、分割によって生成された新たな矩形領域群が区画リストLに追加される。矩形領域検出部38は、縦方向及び横方向の境界線候補が全てメモリ装置18又は補助記憶装置16に格納されると、これを読み出す。そして、例えば、縦方向及び横方向の境界線候補、並びに元の二次元平面の外縁線を用いて生成可能な全ての矩形領域について、領域内の座標の重み値を合計し、合計値が最も大きい又は最も小さい矩形領域を探索して、矩形領域検出問題の最適矩形とする。なお、矩形領域検出部38の処理手法については種々の手法を採用することができ、このような網羅的な手法に限定されるものではない。[処理フロー]以下、矩形領域検出装置1により実行される、より具体的な処理の流れについて説明する。図11は、境界線候補選択部36により実行される境界線候補選択処理の流れを示すフローチャートである。まず、境界線候補選択部36は、区画リストLに、二次元平面全体を一個の矩形領域として設定するS200。また、カウント値tの初期値として1を設定するS202。次に、境界線候補選択部36は、カウント値tが分割上限数rの2倍以下であるか否かを判定するS204。カウント値tが分割上限数rの2倍以下である場合は、区画リストLから把握される矩形領域の中で、領域内に存在する座標の数が最も多い矩形領域Dtを取り出すS206。なお、この際に、重み値が同一種類のみである矩形領域は、矩形領域Dtの探索から除外する。次に、境界線候補選択部36は、矩形領域Dt内の座標の数が3×n/r2未満であるか否かを判定するS208。nは、二次元平面全体に存在する座標の総数である。次に、境界線候補選択部36は、カウント数tが奇数であるか否かを判定するS210。カウント数tが奇数である場合、矩形領域Dtの上下に並ぶ全ての矩形領域を一つの矩形領域とみなして、縦方向分割処理部36Aを呼び出して縦方向分割処理を行い、境界線候補btを決定するS212。図12は、矩形領域Dtの上下に並ぶ全ての矩形領域を一つの矩形領域後述する入力領域D;図中太枠とみなして縦方向分割処理を行う様子を示す図である。そして、矩形領域Dtの上下に並ぶ全ての矩形領域を境界線候補btで分割し、区画リストLにおける分割された矩形領域を、分割後の矩形領域で置き換えて更新するS214。一方、カウント数tが偶数である場合、矩形領域Dtの左右に並ぶ全ての矩形領域を一つの矩形領域とみなして、横方向分割処理部36Bを呼び出して横方向分割処理を行い、境界線候補btを決定するS216。図13は、矩形領域Dtの左右に並ぶ全ての矩形領域を一つの矩形領域後述する入力領域D;図中太枠とみなして横方向分割処理を行う様子を示す図である。そして、矩形領域Dtの左右に並ぶ全ての矩形領域を境界線候補btで分割し、区画リストLにおける分割された矩形領域を、分割後の矩形領域で置き換えて更新するS218。S212S214、又はS216S218を実行すると、カウント値tを1増加させS220、S204に戻る。そして、S206~S220の処理を、カウント値tが分割上限数rの2倍を超えるか、或いは矩形領域Dtの座標の数が3×n/r2を超えるまで、繰り返し実行する。S204、及びS208の処理は、二次元平面が過剰に分割されることを防止するための条件判定終了条件判定であり、一部を省略或いは変更することも可能である。カウント値tが分割上限数rの2倍を超えるか、或いは矩形領域Dtの座標の数が3×n/r2を超えると、区画リストLに含まれる縦方向の境界線候補をまとめて縦方向の境界線候補リストを作成する。同様に、区画リストLに含まれる横方向の境界線候補をまとめて横方向の境界線候補リストを作成するS222。縦方向及び横方向の境界線候補リストは、メモリ装置18又は補助記憶装置16に格納され、出力制御部34によって外部装置に出力されるか、内部機能である矩形領域検出部38によって読み出され、矩形領域検出に用いられる。図14は、縦方向分割処理図11のS212に係る処理の流れを示すフローチャートである。縦方向分割処理部36Aは、入力領域Dに含まれる座標のx座標値に基づいて、座標間に置くことが可能な縦方向の境界線bjを全て列挙し、それらをB={b1,b2,b3,...bm}とするS300。入力領域Dは、前述のように、矩形領域Dtの上下に並ぶ全ての矩形領域を一つの矩形領域とみなしたものである。入力領域Dに含まれる座標数がnであるとすると、m=n-1となる。ここで、座標間に置くことが可能な境界線bjは、例えば、左右に座標が存在するとして、右側x座標が大きい側のx座標から微小値x1を減算した値をx座標値とする境界線と定義することができる。微小値x1は、予め座標間隔の最小値が判明している場合、当該最小値未満の値とすればよい。図15は、境界線bjを座標間に設定する様子を示す図である。なお、これに限らず、左右の座標の中間に境界線bjを設定してもよいし、他の境界線定義を行ってもよい。次に、縦方向分割処理部36Aは、カウント値jの初期値を1とするS302。次に、縦方向分割処理部36Aは、カウント値jが、境界線の総数m以下であるか否かを判定するS304。カウント値jが、境界線の総数m以下である場合、境界線bjの左側部分S1、及び右側部分S2において、前述したgi,kを求め、スコア値Hjを算出するS306。但し、入力領域Dには、既に区画リストLに格納された横方向の境界線候補が含まれる場合があるが、この横方向の境界線候補をまたぐ座標間では、連続性が途切れるものとする。そして、カウント値jを1増加させS308、S304に戻る。S304において、カウント値jが境界線の総数mを超えた場合、スコア値H1~Hmの中で最小値となるものを選択し、選択したスコア値に対応する境界線bjを、縦方向分割の処理結果、すなわち境界線候補とするS310。図16は、横方向分割処理図11のS216に係る処理の流れを示すフローチャートである。横方向分割処理部36Bは、入力領域Dに含まれる座標のy座標値に基づいて、座標間に置くことが可能な境界線bjを全て列挙し、それらをB={b1,b2,b3,...bm}とするS400。入力領域Dは、前述のように、矩形領域Dtの左右に並ぶ全ての矩形領域を一つの矩形領域とみなしたものである。入力領域Dに含まれる座標数がnであるとすると、m=n-1となる。ここで、座標間に置くことが可能な境界線bjは、例えば、上下に座標が存在するとして、上側y座標が大きい側のy座標から微小値y1を減算した値をy座標値とする境界線と定義することができる。微小値y1は、予め座標間隔の最小値が判明している場合、当該最小値未満の値とすればよい。係る手法は縦方向分割の場合と同様であるため、図示を省略する。なお、これに限らず、上下の座標の中間に境界線bjを設定してもよいし、他の境界線定義を行ってもよい。次に、横方向分割処理部36Bは、カウント値jの初期値を1とするS402。次に、横方向分割処理部36Bは、カウント値jが、境界線の総数m以下であるか否かを判定するS404。カウント値jが、境界線の総数m以下である場合、境界線bjの上側部分S1、及びした側部分S2において、前述したgi,kを求め、スコア値Hjを算出するS406。但し、入力領域Dには、既に区画リストLに格納された縦方向の境界線候補が含まれる場合があるが、この縦方向の境界線候補をまたぐ座標間では、連続性が途切れるものとする。そして、カウント値jを1増加させS408、S404に戻る。S404において、カウント値jが境界線の総数mを超えた場合、スコア値H1~Hmの中で最小値となるものを選択し、選択したスコア値に対応する境界線bjを、横方向分割の処理結果、すなわち境界線候補とするS410。図17は、矩形領域検出装置1が図11に示すフローを実行して、入力平面に対して縦方向分割処理と横方向分割処理を交互に行った結果、最適矩形に至る様子を示す図である。図中、◇は、その時点で領域内に存在する座標の数が最も多い矩形領域Dtを示している。また、最終図の太枠は、矩形領域問題における最適矩形を表している。本図で表される入力平面に対して本実施例のアルゴリズムを適用した結果、境界線8本を引いた時点で、矩形領域問題における最適矩形の境界線を発見することができる。[動作例]更に、図4に示した座標データを入力データとして図11のフローを実行した場合の動作例について説明する。ここでは、カウント値tは1、2までとし、分割数上限値r=6とする。まず、図11のフローにおけるS200において、最初に生成される区画リストLは、既に図5に示したようになる。次に、S202においてカウント値に1が設定され、S204においてカウント値=1が分割上限数r=6の2倍以下であると判定される。S206において取り出される矩形領域D1は、最初に生成される区画リストL、すなわち元の二次元平面である。S208において、矩形領域D1に含まれる座標の数nは30であるため、3×30/62=2.5個以上であると判定される。S210においては、k=1であるため、S212に進む。S212では、矩形領域D1の上下に並ぶ矩形領域、すなわち二次元平面全体を入力領域Dとして縦方向分割処理を行う。入力領域Dに含まれる座標間に設定し得る直線のx座標の集合Bは、次のように表される。直線数mは、n-1=29である。B={85,125,245,255,265,285,335,345,355,375,485,505,545,565,585,605,625,645,655,675,715,735,785,805,825,845,865,875,925}これらの直線b1~b29のそれぞれについてスコア値Hjを算出すると、その結果は図18に示すようになる。図18は、本実施例の矩形領域検出装置1が処理を行った結果、導出されるスコア値Hjの例である。図から、スコア値Hjの最小値はH23=87.4であるため、縦方向の境界線候補b23のx座標=785という結果を得る。S214においては、矩形領域D1上下に並ぶ矩形領域ここでは矩形領域D1そのものを境界線候補b23で分割し、区画リストLにおける分割された矩形領域を、分割後の矩形領域で置き換える。この結果区画リストLは、図19に示すものに更新される。図19は、本実施例の矩形領域検出装置1が処理を行った結果、生成される区画リストLの例である。S220においてカウント値tが2に変更され、S202に戻る。なお、上記と同様、S204、及びS208の終了条件は満たさないため、これについての説明を省略する。S206において取り出される矩形領域D2は、図19における上側注;二次元平面においては左側の領域である。S210においては、k=2であるため、S216に進む。S216では、矩形領域D2の左右に並ぶ矩形領域、すなわち二次元平面全体を入力領域Dとして横方向分割処理を行う。入力領域Dに含まれる座標間に設定し得る直線のy座標の集合Bは、次のように表される。直線数mは、n-1=29である。B={25,45,75,95,185,215,235,275,335,345,395,425,435,445,455,575,585,615,635,675,695,715,735,745,775,795,855,915,945}これらの直線b1~b29のそれぞれについてスコア値Hjを算出すると、その結果は図20に示すようになる。図20は、本実施例の矩形領域検出装置1が処理を行った結果、導出されるスコア値Hjの例である。図から、スコア値Hjの最小値はH12=63.3であるため、横方向の境界線候補b12のx座標=425という結果を得る。S218においては、矩形領域D2の左右に並ぶ矩形領域ここでは矩形領域D2に右側領域を加えたものを境界線候補b12で分割し、区画リストLにおける分割された矩形領域を、分割後の矩形領域で置き換える。この結果区画リストLは、図21に示すものに更新される。図21は、本実施例の矩形領域検出装置1が処理を行った結果、生成される区画リストLの例である。このようにカウント値tを増加させながら繰り返し処理を行い、カウント値tが9に至ったときの座標数最大の矩形領域D9は、図22で表される。図22は、本実施例の矩形領域検出装置1が処理を行った結果、抽出される座標数最大の矩形領域D9の例である。この矩形領域D9に含まれる座標の数は2個であるため、S208の終了条件を満たし、S222に進む。こうして得られた結果は、図23で示すものとなる。図23は、最終的に得られた複数の境界線候補を示す図である。図23に示すデータは、メモリ装置18又は補助記憶装置16に格納されて用いられる。[他の手法を用いた場合との比較]ここで、他の手法を用いて境界線候補を選択した場合との比較について述べる。既に知られた文献JRQUINLANMachineLearning1811061986には、メッシュ分割において、情報ゲインという概念を適用することについて記載されている情報ゲインとは、矩形領域内の座標の個数の不均衡さを考慮する際に利用できる概念の一つである。情報ゲインの概念に基づいて、上記のように分割された部分領域についてスコア値を算出する場合、スコア値Hは、例えば次式5で表される。式中、gi,kは、部分領域Siに含まれる種類kの座標の数であり、本実施例のgi,kのように、部分領域Siに含まれる、座標成分が隣接し、且つ重み値が種類kである座標が連続する数ではない。スコア値Hの小さい直線が選択される点は、本実施例と同様であるものとする。Hj=ΣiNi×-Σk{gi,k/Ni×loggi,k/Ni}...5上式5を図9で示す座標分布に適用すると、次式6、7で示す結果となる。H1=N1×-Σk{g1,k/N1×logg1,k/N1}N2×-Σk{g2,k/N2×logg2,k/N2}=4×-{1/4×log1/43/4×log3/4}6×-{4/6×log4/62/6×log2/6}=8.75...6H2=N1×-Σk{g1,k/N1×logg2,k/N1}N2×-Σk{g2,k/N2×logg2,k/N2}=5×-{2/5×log2/53/5×log3/5}5×-{3/5×log3/52/5×log2/5}=9.71...7この結果、より小さいH1を導出した図9Aで示す直線L1が選択されることになり、本実施例による結果とは異なることが判る。上式5に基づく手法以下、便宜的に従来手法と称するは、矩形領域内における重み値が同一種類の座標の個数の不均衡さを反映している。しかしながら、従来手法は、矩形領域内において重み値が同一種類の座標が塊をなしている隣接し合っている状況を反映したものとはならない。この結果、矩形領域検出問題において、できるだけ少ない境界線候補で有望なメッシュ状分割境界線候補群を与えることができない場合がある。矩形領域検出問題の特性から、メッシュ状分割された各矩形領域には、単一種類の座標のみが含まれていることが望ましい。図24は、矩形領域検出問題の対象となる二次元平面の例である。一般的に、ある矩形領域内例えば図24の破線内の最適矩形局所解、すなわち○3個の矩形領域は、その周りを□で囲まれるようになる。すなわち、与えられた領域と最適矩形との差の部分領域に□だけが含まれる塊を成すようにメッシュ境界線を引くことが望ましい。二次元平面上で同一種類の座標が塊となるように区画を決めたいということは、一次元上で考えると同一種類の座標が連続的に並ぶように区切りたいということに相当する。そこで一次元上で連続するように選ぶようにすれば、二次元上で塊になるようにできるだろう、と考えられる。すなわち、境界線に沿って見ると、境界線付近に単一種類の座標が連続的に現れるような境界線が望ましいといえる。例えば、図24の矢印で示す横境界線のすぐ上側に並ぶ矩形領域4個内に存在する座標を左から右に見ていくと、□2個、○3個、□1個、○2個の順となる。一方、下側に並ぶ矩形領域4個内に存在する座標を左から右に見ていくと、○2個、□4個、○1個の順となる。このような各矩形領域に連続的に現れる数2個、3個等が大きいほど、当該境界線が最適矩形の境界線となる可能性が高くなるのである。この点、従来手法は、境界線で分割される部分領域の座標の個数についての不均衡さを考慮しているが、同一種類の座標の連続性については考慮していない。これに対し、本実施例では、座標成分が隣接し、且つ重み値が種類kである座標が連続する数に基づく値を指標値として境界線候補を選択しているため、矩形領域内において重み値が同一種類の座標が塊をなしている状況を適切に反映させることができる。この結果、選択した境界線候補が、矩形領域検出問題の最適矩形として求められるべき矩形領域の境界線に一致する可能性を高めることができ、矩形領域検出問題において矩形領域を絞り込むための境界線候補を適切に選択することができる。図25及び図26は、与えられた座標データに対して、本実施例の矩形領域検出装置1が境界線候補を選択した場合と、従来手法に基づいて境界線候補を選択した場合とを比較するための図である。図25Aは与えられた座標データ及び最適矩形図中、太線矩形を示し、図25Bは本実施例の矩形領域検出装置1が境界線候補を選択した結果を示している。図25Bに示すように或いは、既に図17で示したように、本実施例の矩形領域検出装置1では、境界線候補を8本選択した時点で、最適矩形の四辺の境界線を全て選択することができた。一方、図26Aは、従来手法に基づいて境界線候補を8本選択した結果を示し、図26Bは、従来手法に基づいて境界線候補を12本選択した結果を示している。図示するように、従来手法に基づいて境界線候補を選択した場合、12本の境界線候補を選択しても、依然として最適矩形の四辺の境界線を選択できなかった。このように、本実施例の矩形領域検出装置1では、従来手法に基づいて境界線候補を選択する場合に比して、少ない処理数で最適矩形の四辺の境界線を見つけることができる。これによって、分岐限定法等によって無駄な枝の枝切りを効率的に行うことができ、更に最適解若しくはそれに近い近似解を迅速に発見することができる。[まとめ]以上説明した本実施例の矩形領域検出装置1、及び矩形領域検出方法、並びにこれらを実現可能なプログラムによれば、矩形領域検出問題において矩形領域を絞り込むための境界線候補を迅速且つ適切に選択することができる。[変形等]以上、本発明を実施するための最良の形態について実施例を用いて説明したが、本発明はこうした実施例に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変形及び置換を加えることができる。例えば、分割の元となった直線に平行な座標軸に関する座標成分が隣接し、且つ重み値が同一種類である座標が連続する数としてgi,kを求めるものとしたが、分割の元となった直線に直交する座標軸に関する...と置換してもよい。また、縦方向分割処理と横方向分割処理を交互に行うものとしたが、元の二次元平面が縦又は横に長いような場合では、縦2回→横1回、或いは縦1回→横2回を繰り返す等と分割頻度を調整してもよい。また、縦方向分割処理と横方向分割処理を交互に行うものとしたが、縦方向分割処理のみ、或いは横方向分割処理のみを行うものであってもよい。また、図11のS212において、座標数が最大の矩形領域Dtの上下に並ぶ全ての矩形領域を一つの矩形領域とみなして縦方向分割処理を行うものとしたが、矩形領域Dtから見て所定数上及び下の矩形領域のみを対象としてもよい。同様に、S216において、矩形領域Dtの左右に並ぶ全ての矩形領域を一つの矩形領域とみなして横方向分割処理を行うものとしたが、矩形領域Dtから見て所定数左及び右の矩形領域のみを対象としてもよい。更に、矩形領域Dtのみを分割対象としてもよく、縦方向分割処理や横方法分割処理の対象となる入力領域Dの選び方は、種々の変更が可能である。また、入力領域Dの中で、境界線から所定距離σ或いは所定座標数以内の領域のみをスコア値Hjの算出対象としてもよい。図27は、入力領域Dの中で、境界線から所定距離σ或いは所定座標数以内の領域のみをスコア値Hjの算出対象とする様子を模式的に示す図である。図中、スコア値Hjの算出対象とする領域内の座標を実線で、それ以外の座標を破線で示している。以上の説明に関し、さらに以下の項を開示する。付記1正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納する座標データ取得手段と、前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納する境界線候補選択手段と、前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力する矩形領域検出手段と、を備える矩形領域検出装置。付記2付記1に記載の矩形領域検出装置であって、前記境界線候補選択手段は、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号及び値が同一である座標データが連続する数に応じて増減する指標値を算出する手段である、矩形領域検出装置。付記3付記1又は2に記載の矩形領域検出装置であって、前記境界線候補選択手段は、前記座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数、又は前記座標成分が隣接し且つ前記重み値の符号及び値が同一である座標データが連続する数が増加するほど、また該連続する座標グループ数が少ないほど、減少する傾向の前記指標値を算出し、該算出した指標値を各直線について合計し、該合計した値が最も小さくなった直線を選択する手段である、矩形領域検出装置。付記4付記3に記載の矩形領域検出装置であって、前記指標値は、Ni×-Σk{gi,k/Ni×loggi,k/Ni}で表され、該式中、kは重み値の符号、又は符号及び値であり、iは矩形領域の識別子であり、Niは矩形領域内の座標データ数であり、gi,kは前記座標成分が隣接し且つ重み値が同一種類である座標が連続する数である、矩形領域検出装置。付記5付記1ないし4のいずれか1項に記載の矩形領域検出装置であって、前記境界線候補選択手段は、前記二次元平面における第1の座標軸に平行な直線を選択する処理と、該第1の座標軸に直交する第2の座標軸に平行な直線を選択する処理を、交互に行う手段である、矩形領域検出装置。付記6付記1ないし5のいずれか1項に記載の矩形領域検出装置であって、前記境界線候補選択手段は、前記二次元平面上で平行な直線を複数設定する際に、既に選択した直線を用いて区画される矩形領域のうち、座標データ数が最大の矩形領域内を前記平行な複数の直線が通るように、前記平行な直線を複数設定する手段である、矩形領域検出装置。付記7正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納するステップと、前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納するステップと、前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力するステップと、をコンピュータが実行する矩形領域検出方法。付記8正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納する処理と、前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納する処理と、前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力する処理と、をコンピュータに実行させるプログラム。"