(57)【要約】【課題】矩形領域検出問題において矩形領域を絞り込むための境界線候補を迅速且つ適切に選択すること【解決手段】正又は負の値である重み値が付与された二次元平面上の座標データを複数個取得して記憶手段に格納し、二次元平面上で平行な直線を複数設定し、各直線を境界線とする複数の矩形領域に対して、複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、算出した指標値を各直線について合計した値に基づいて一の直線を選択して記憶手段に格納し、格納された直線のうちいずれかを境界線とし、領域内に存在する座標に付与された重み値の合計が最大又は最小となる矩形領域を検出して出力する矩形領域検出装置。【選択図】図１１
2013011984.tif 000002
【特許請求の範囲】
【請求項１】
正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納する座標データ取得手段と、
前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納する境界線候補選択手段と、
前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力する矩形領域検出手段と、
を備える矩形領域検出装置。
【請求項２】
請求項１に記載の矩形領域検出装置であって、
前記境界線候補選択手段は、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号及び値が同一である座標データが連続する数に応じて増減する指標値を算出する手段である、
矩形領域検出装置。
【請求項３】
請求項１又は２に記載の矩形領域検出装置であって、
前記境界線候補選択手段は、前記座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数、又は前記座標成分が隣接し且つ前記重み値の符号及び値が同一である座標データが連続する数が増加するほど、また該連続する座標グループ数が少ないほど、減少する傾向の前記指標値を算出し、該算出した指標値を各直線について合計し、該合計した値が最も小さくなった直線を選択する手段である、
矩形領域検出装置。
【請求項４】
請求項３に記載の矩形領域検出装置であって、
前記指標値は、Ｎｉ×〔−Σｋ｛（ｇｉ，ｋ／Ｎｉ）×ｌｏｇ（ｇｉ，ｋ／Ｎｉ）｝〕で表され、
該式中、ｋは重み値の符号、又は符号及び値であり、ｉは矩形領域の識別子であり、Ｎｉは矩形領域内の座標データ数であり、ｇｉ，ｋは前記座標成分が隣接し且つ重み値が同一種類である座標が連続する数である、
矩形領域検出装置。
【請求項５】
請求項１ないし４のいずれか１項に記載の矩形領域検出装置であって、
前記境界線候補選択手段は、前記二次元平面における第１の座標軸に平行な直線を選択する処理と、該第１の座標軸に直交する第２の座標軸に平行な直線を選択する処理を、交互に行う手段である、
矩形領域検出装置。
【請求項６】
請求項１ないし５のいずれか１項に記載の矩形領域検出装置であって、
前記境界線候補選択手段は、前記二次元平面上で平行な直線を複数設定する際に、既に選択した直線を用いて区画される矩形領域のうち、座標データ数が最大の矩形領域内を前記平行な複数の直線が通るように、前記平行な直線を複数設定する手段である、
矩形領域検出装置。
【請求項７】
正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納するステップと、
前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納するステップと、
前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力するステップと、
をコンピュータが実行する矩形領域検出方法。
【請求項８】
正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納する処理と、
前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納する処理と、
前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力する処理と、
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の座標が存在する二次元平面から所定の特徴を有する矩形領域を検出する矩形領域検出装置、及び方法、並びにプログラムに関する。
【背景技術】
【０００２】
従来、矩形領域検出問題（Maximum  Bichromatic  Discrepancy  (MBD)  problem）という、主にコンピュータ処理の対象となる幾何的な問題（課題）が提起されている（例えば、非特許文献１参照）。矩形領域検出問題とは、二次元平面上に複数の座標が存在し、各座標に、正又は負の値をとり得る重み値が付与されているときに、「領域内に存在する座標に付与された重み値の合計が最大（又は最小；以下省略する）となる矩形領域を検出する」という問題である。
【０００３】
矩形領域問題は、例えば、需要と供給の不一致の大きい地域の抽出（人口が多いが来店客が少ない地域）を行ってマーケティング分析に用いることができる。また、矩形領域問題は、タクシー等の乗車数と降車数の食い違いの大きい地域の抽出やトラック、宅配便等の積込み地点と積下ろし地点の食い違いの大きい地域の抽出を行って、車両運用システムの構築に用いることもできる。
【０００４】
矩形領域検出問題は、次式（１）によって表現される。式中、Ｓは座標の集合であり、χはＳに対して重み値を付与する関数であり、Ｒは矩形領域の集合である。
【０００５】
【数１】
2013011984.tif 000003
【０００６】
以下、説明を簡易にするために、重み値が（＋１）と（−１）の二値をとり得るものとする。この場合、矩形領域検出問題は、「重み値が（＋１）の座標の数から重み値が（−１）の座標の数を差し引いた数が最大となる矩形領域を検出する」という問題となる。
【０００７】
図１は、矩形領域検出問題を説明するための説明図である。図中、○は重み値が（＋１）の座標であり、□は重み値が（−１）の座標である。なお、図１では、元々の二次元平面を、０＜ｘ＜１、且つ０＜ｙ＜１の領域に制限しており、異なる座標の座標成分（ｘ座標又はｙ座標）は一致せず、矩形領域の境界線は座標と重ならない（わずかに外側を通過する）といった条件が追加されている。
【０００８】
図１で示す二次元平面においては、領域Ａ１において、○の数（＝７）から□の数（＝０）を差し引いた数が７となっており、領域Ａ１が、重み値の合計が最大となる矩形領域である。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】DAVID  P.  DOBKIN  AND  DIMITRIOS  GUNOPULOS,  “Computing  the  Maximum  Bichromatic  Discrepancy,  with  Applications  to  Computer  Graphics  and  Machine  Learning”,JOURNAL  OF  COMPUTER  AND  SYSTEM  SCIENCE,52,453-470,(1996)
【発明の概要】
【発明が解決しようとする課題】
【００１０】
ところで、非特許文献１では、最適解（最適矩形）を網羅的に求める手順が示されている。網羅的に求める手順とは、座標間を通る全てのｘ方向及びｙ方向の直線を境界線として設定され得る矩形領域、すなわち、考え得る全ての矩形領域について重み値の合計を求め、合計が最大値となる矩形領域を探索する手順である。
【００１１】
しかしながら、最適解を網羅的に求める手順を採用する場合、座標の数ｎが多くなると、計算量が多くなるために迅速な処理を行うことができない可能性がある。具体的には、最適解を網羅的に求める手順では、時間計算量はＯ（ｎ２・ｌｏｇ（ｎ））、空間計算量はＯ（ｎ）というオーダーを示しており、このことから、座標の数ｎの増加に応じて特に時間計算量の増加率が大きいことが判る。
【００１２】
本発明はこのような課題を解決するためのものであり、矩形領域検出問題において矩形領域を絞り込むための境界線候補を迅速且つ適切に選択することが可能な矩形領域検出装置、矩形領域検出方法、及びプログラムを提供することを、主たる目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するための第１の態様は、
正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納する座標データ取得手段と、
前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納する境界線候補選択手段と、
前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力する矩形領域検出手段と、
を備える矩形領域検出装置である。
【発明の効果】
【００１４】
本発明によれば、矩形領域検出問題において矩形領域を絞り込むための境界線候補を迅速且つ適切に選択することが可能な矩形領域検出装置、矩形領域検出方法、及びプログラムを提供することができる。
【図面の簡単な説明】
【００１５】
【図１】矩形領域検出問題を説明するための説明図である。
【図２】本発明の一実施例に係る矩形領域検出装置１のハードウエア構成例である。
【図３】本実施例の矩形領域検出装置１の機能構成例である。
【図４】入力制御部３２によって取得され、メモリ装置１８又は補助記憶装置１６に格納された複数の座標データを示す図である。
【図５】入力制御部３２によって取得され、メモリ装置１８又は補助記憶装置１６に格納された二次元平面の外縁線座標データを示す図である。
【図６】本実施例の矩形領域検出装置１により実行される処理の概要を示すフローチャートである。
【図７】縦方向分割処理部３６Ａが直線を複数設定し、設定した直線を境界線の一つとする矩形領域群を設定する様子を簡単に示す図である。
【図８】ある入力領域内の座標データをｙ座標に関して並べ替えを行ったソートデータからｇｉ，（＋１）、及びｇｉ，（−１）が算出される様子を示す図である。
【図９】縦方向分割処理部３６Ａにより縦方向の直線が二本（Ｌ１、Ｌ２）設定された様子を示す図である。
【図１０】縦方向分割処理部３６Ａや横方向分割処理部３６Ｂによって更新される区画リストＬの一例である。
【図１１】境界線候補選択部３６により実行される境界線候補選択処理の流れを示すフローチャートである。
【図１２】矩形領域Ｄｔの上下に並ぶ全ての矩形領域を一つの矩形領域（後述する入力領域Ｄ）とみなして縦方向分割処理を行う様子を示す図である。
【図１３】矩形領域Ｄｔの左右に並ぶ全ての矩形領域を一つの矩形領域（後述する入力領域Ｄ）とみなして横方向分割処理を行う様子を示す図である。
【図１４】縦方向分割処理に係る処理の流れを示すフローチャートである。
【図１５】境界線ｂｊを座標間に設定する様子を示す図である。
【図１６】横方向分割処理に係る処理の流れを示すフローチャートである。
【図１７】本実施例の矩形領域検出装置１が図１１に示すフローを実行して、入力平面に対して縦方向分割処理と横方向分割処理を交互に行った結果、最適矩形に至る様子を示す図である。
【図１８】本実施例の矩形領域検出装置１が処理を行った結果、導出されるスコア値Ｈｊの例である。
【図１９】本実施例の矩形領域検出装置１が処理を行った結果、生成される区画リストＬの例である。
【図２０】本実施例の矩形領域検出装置１が処理を行った結果、導出されるスコア値Ｈｊの例である。
【図２１】本実施例の矩形領域検出装置１が処理を行った結果、生成される区画リストＬの例である。
【図２２】本実施例の矩形領域検出装置１が処理を行った結果、抽出される座標数最大の矩形領域Ｄ９の例である。
【図２３】最終的に得られた複数の境界線候補を示す図である。
【図２４】矩形領域検出問題の対象となる二次元平面の例である。
【図２５】与えられた座標データと、本実施例の矩形領域検出装置１が境界線候補を選択した結果を示す図である。
【図２６】与えられた座標データに対して、従来手法に基づいて境界線候補を選択した結果を示す図である。
【図２７】入力領域Ｄの中で、境界線から所定距離σ（或いは所定座標数）以内の領域のみをスコア値Ｈｊの算出対象とする様子を模式的に示す図である。
【発明を実施するための形態】
【００１６】
以下、本発明を実施するための形態について、添付図面を参照しながら実施例を挙げて説明する。
【実施例】
【００１７】
以下、図面を参照し、本発明の一実施例に係る矩形領域検出装置、矩形領域検出方法、及びプログラムについて説明する。
【００１８】
［ハードウエア構成］
図２は、本発明の一実施例に係る矩形領域検出装置１のハードウエア構成例である。
【００１９】
矩形領域検出装置１は、例えば、ＣＰＵ（Central  Processing  Unit）１０と、ドライブ装置１２と、補助記憶装置１６と、メモリ装置１８と、インタフェース装置２０と、入力装置２２と、ディスプレイ装置２４と、を備える情報処理装置である。これらの構成要素は、バスやシリアル回線等を介して接続されている。
【００２０】
ＣＰＵ１０は、例えば、プログラムカウンタや命令デコーダ、各種演算器、ＬＳＵ（Load  Store  Unit）、汎用レジスタ等を有するプロセッサである。
【００２１】
ドライブ装置１２は、記憶媒体１４からプログラムやデータを読み込み可能な装置である。プログラムを記録した記録媒体１４がドライブ装置１２に装着されると、プログラムが記録媒体１４からドライブ装置１２を介して補助記憶装置１６にインストールされる。記録媒体１４は、例えば、ＣＤ−ＲＯＭ、ＤＶＤディスク、ＵＳＢメモリ等の可搬型の記録媒体である。また、補助記憶装置１６は、例えば、ＨＤＤ（Hard  Disk  Drive）やフラッシュメモリである。
【００２２】
プログラムのインストールは、上記のように記憶媒体１４を用いる他、インタフェース装置２０がネットワークを介して他のコンピュータよりダウンロードし、補助記憶装置１６にインストールすることによって行うこともできる。ネットワークは、インターネット、ＬＡＮ（Local  Area  Network）、携帯電話の電波網等である。また、プログラムは、情報処理装置の出荷時に、予め補助記憶装置１６やＲＯＭ（Read  Only  Memory）等に格納されていてもよい。
【００２３】
このようにしてインストール又は予め格納されたプログラムをＣＰＵ１０が実行することにより、図１に示す態様の情報処理装置が、本実施例の矩形領域検出装置１として機能することができる。
【００２４】
メモリ装置１８は、例えば、ＲＡＭ（Random  Access  Memory）やＥＥＰＲＯＭ（Electrically  Erasable  and  Programmable  Read  Only  Memory）である。インタフェース装置２０は、上記ネットワークとの接続等を制御する。
【００２５】
入力装置２２は、例えば、キーボードやマウス、タッチパッド、タッチパネル、マイク等である。また、ディスプレイ装置２４は、例えば、ＬＣＤ（Liquid  Crystal  Display）やＣＲＴ（Cathode  Ray  Tube）等の表示装置である。矩形領域検出装置１は、ディスプレイ装置２４の他、プリンタ、スピーカ等の他の種類の出力装置を備えてもよい。
【００２６】
［機能構成］
図３は、本実施例の矩形領域検出装置１の機能構成例である。矩形領域検出装置１は、マスター制御部３０と、入力制御部３２と、出力制御部３４と、境界線候補選択部３６と、矩形領域検出部３８と、を備える。これらの機能ブロックは、補助記憶装置１６等に格納されたプログラム・ソフトウエアをＣＰＵ１０が実行することにより機能する。
【００２７】
マスター制御部３０は、以下に説明するような各機能ブロックの全体動作を制御する。
【００２８】
入力制御部３２は、矩形領域検出問題を規定する各種データを、ドライブ装置１２やインタフェース装置２０、入力装置２２等を介して取得し、メモリ装置１８又は補助記憶装置１６に格納する。矩形領域検出問題を規定する各種データは、重み値が付与された複数の座標データ、二次元平面の外縁線座標データ、分割数上限数ｒ等を含む。
【００２９】
出力制御部３４は、境界線候補選択部３６によって選択された境界線候補をメモリ装置１８又は補助記憶装置１６から読み出し、ドライブ装置１２やインタフェース装置２０、ディスプレイ装置２４等を介して外部に出力する。この他、境界線候補は、矩形領域検出部３８によって読み出され、矩形領域の検出に用いられる。なお、境界線候補の外部への出力を行わず、専ら矩形領域検出部３８によって用いられるものとしてもよい。
【００３０】
境界線候補選択部３６は、更に、縦方向分割処理部３６Ａと、横方向分割処理部３６Ｂと、を有する。境界線候補選択部３６は、例えば、縦方向分割処理部３６Ａと横方向分割処理部３６Ｂを交互に呼び出して機能させることによって、縦方向及び横方向に沿って延びる複数の境界線候補を選択し、メモリ装置１８又は補助記憶装置１６に格納する。
【００３１】
以下、縦方向分割処理部３６Ａ、及び横方向分割処理部３６Ｂによる分割処理（境界線候補選択処理）について説明する。
【００３２】
図４は、入力制御部３２によって取得され、メモリ装置１８又は補助記憶装置１６に格納された複数の座標データを示す図である。図示するように、各座標データは、ｘ座標とｙ座標と重み値が対応付けられており、座標一個に対して一行が割り当てられている。本実施例では、簡明のために重み値は（＋１）と（−１）の二値をとり得るものとする。
【００３３】
図５は、入力制御部３２によって取得され、メモリ装置１８又は補助記憶装置１６に格納された二次元平面の外縁線座標データを示す図である。図示するように、二次元平面の外縁線座標データは、左辺のｘ座標、右辺のｘ座標、下辺のｙ座標、上辺のｙ座標が特定されたデータである。
【００３４】
図６は、本実施例の矩形領域検出装置１により実行される処理の概要を示すフローチャートである。
【００３５】
まず、マスター制御部３０は、矩形領域検出問題を規定する各種データを取得してメモリ装置１８又は補助記憶装置１６に格納するように、入力制御部３２に指示する（Ｓ１００）。
【００３６】
次に、マスター制御部３０は、縦方向分割処理と横方向分割処理を繰り返すことにより複数の境界線候補を求めてメモリ装置１８又は補助記憶装置１６に格納するように、境界線候補選択部３６に指示する（Ｓ１０２）。
【００３７】
そして、マスター制御部３０は、メモリ装置１８又は補助記憶装置１６に格納された境界線候補を出力するように、出力制御部３４に指示する（Ｓ１０４）。
【００３８】
［分割手法］
縦方向分割処理部３６Ａは、以下に説明するような手法に基づき、二次元平面を縦方向（ｙ軸に平行な方向）の直線で分割し、当該直線を境界線候補として選択する（縦方向分割処理）。
【００３９】
縦方向分割処理部３６Ａは、まず、二次元平面上でｙ軸に平行な直線を複数設定する。この直線設定に係る詳細なルールについては後述する。そして、設定した各直線を境界線とする複数の矩形領域を設定する。
【００４０】
図７は、縦方向分割処理部３６Ａが直線を複数設定し、設定した直線を境界線の一つとする矩形領域群を設定する様子を簡単に示す図である。図中、縦方向分割処理部３６Ａが今回の分割において設定する直線をＬ１、Ｌ２とし、過去に分割に用いられた直線をＰ１、Ｐ２、Ｐ３、Ｐ４と表記した。図示するように、縦方向分割処理部３６Ａは、元の二次元平面が既に幾つかに分割されている場合には、分割に用いられた直線を新たな矩形領域の境界線として用いる。
【００４１】
更に、縦方向分割処理部３６Ａは、複数設定した直線毎に、設定した直線を境界線の一つとする矩形領域のそれぞれについて、次式（２）で示すようなスコア値Ｈｊを算出する。式中、添え字ｊは領域生成の元となった直線を識別するための識別子であり、添え字ｉは当該直線から生成された矩形領域を識別するための識別子であり、Ｎｉは矩形領域内の座標の数であり、添え字ｋは重み値の種類を識別するための識別子である。ｇｉ，ｋの内容については、以下に述べる。
【００４２】
Ｈｊ＝Σｉ［Ｎｉ×〔−Σｋ｛（ｇｉ，ｋ／Ｎｉ）×ｌｏｇ（ｇｉ，ｋ／Ｎｉ）｝〕］  …（２）
【００４３】
縦方向分割処理部３６Ａは、ｇｉ，ｋを求める際に、例えば、矩形領域内の座標データをｙ座標に関して昇順又は降順に並べ替えたソートデータを生成して行う。そして、並べ替えたソートデータにおいて、重み値が同一種類である座標が連続する数を、重み値の種類毎に全て抽出する。
【００４４】
ここで、「重み値が同一種類である」とは、（１）符号（すなわち正の値であるか、負の値であるか）が一致していることを意味するものであってもよいし、（２）符号と値の双方が一致していることを意味するものであってもよい。本実施例では、重み値は（＋１）と（−１）の二値をとるため、いずれの場合でも結果は同じである。
【００４５】
図８は、ある入力領域内の座標データと、これをｙ座標に関して並べ替えを行ったソートデータを示し、更にソートデータからｇｉ，（＋１）、及びｇｉ，（−１）が算出される様子を示す図である。このように、ｇｉ，ｋは、「分割の元となった直線に平行な座標軸（上記ではｙ軸）に関する座標成分（ｙ座標）が隣接し、且つ重み値が同一種類である座標が連続する数」である。なお、ソートデータを用いてｇｉ，ｋを導出するのはあくまで一例であり、組み込み関数、或いはｙ座標の小さい順（或いは大きい順）に座標を抽出して重み値の種類毎にカウントするアルゴリズム等を用いてｇｉ，ｋを導出しても構わない。
【００４６】
また、上式（２）の右項（ｇｉ，ｋ／Ｎｉ）×ｌｏｇ（ｇｉ，ｋ／Ｎｉ）から判るように、スコア値Ｈｊは、ｇｉ，ｋの値が大きい程又は小さい程、すなわち値のばらつきが大きい程、小さくなる傾向を有する指標値である。ｇｉ，ｋの上限はＮｉであり、［ｇｉ，ｋ／Ｎｉ→１］又は［ｇｉ，ｋ／Ｎｉ→０］ならば、［（ｇｉ，ｋ／Ｎｉ）×ｌｏｇ（ｇｉ，ｋ／Ｎｉ）→０］だからである。また、スコア値Ｈｊは、重み値が同一種類であり連続する座標グループ数（ｇｉ，ｋとしてカウントされるグループ数）が小さい程、小さくなる傾向を有する。従って、スコア値Ｈｊは、「分割の元となった直線（ｊ）に平行な座標軸に関する座標成分が隣接し、且つ重み値が同一種類である座標が連続する数が増加するほど、また重み値が同一種類であり連続する座標グループ数が少ないほど減少する傾向の指標値の合計値」である。「指標値」は、式（２）中、Σｉ以外の部分を指す。
【００４７】
そして、縦方向分割処理部３６Ａは、スコア値Ｈｊが最も小さくなった直線ｊを選択し、境界線候補としてメモリ装置１８又は補助記憶装置１６に格納する。すなわち、縦方向分割処理部３６Ａは、分割の結果、直線から生成された矩形領域において、重み値が同一種類の座標が領域内で固まって存在している傾向を示す直線を、境界線候補として選択する。これによって、選択した境界線候補が、矩形領域検出問題の最適矩形として求められるべき矩形領域の境界線に一致する可能性を高めることができる。このことの検証については、後述する。
【００４８】
縦方向分割処理部３６Ａによる縦方向分割について、図を用いて更に説明する。図９は、縦方向分割処理部３６Ａにより縦方向の直線が二本（Ｌ１、Ｌ２）設定された様子を示す図である。図中、○は重み値が（＋１）の座標であり、□は重み値が（−１）の座標である。
【００４９】
図９（Ａ）に示す直線Ｌ１の位置から算出されるスコア値Ｈ１は、次式（３）のようになる。ここで、左側の部分領域をＳ１（ｉ＝１）、右側の部分領域をＳ２（ｉ＝２）とすると、Ｎ１＝４、Ｎ２＝６である。また、重み値が同一種類の座標は、下側からカウントするものとする。
【００５０】
Ｈ１＝Ｎ１×〔−Σｋ｛（ｇ１，ｋ／Ｎ１）×ｌｏｇ（ｇ１，ｋ／Ｎ１）｝〕＋
Ｎ２×〔−Σｋ｛（ｇ２，ｋ／Ｎ２）×ｌｏｇ（ｇ２，ｋ／Ｎ２）｝〕
＝４×〔−｛（１／４）×ｌｏｇ（１／４）＋（１／４）×ｌｏｇ（１／４）＋（２／４）×ｌｏｇ（２／４）｝〕＋
６×〔−｛（１／６）×ｌｏｇ（１／６）＋（１／６）×ｌｏｇ（１／６）＋（３／６）×ｌｏｇ（３／６）＋（１／６）×ｌｏｇ（１／６）｝〕
＝１６．７５  …（３）
【００５１】
また、図９（Ｂ）に示す直線Ｌ２の位置から算出されるスコア値Ｈ２は、次式（４）のようになる。同様に、左側の部分領域をＳ１（ｉ＝１）、右側の部分領域をＳ２（ｉ＝２）とすると、Ｎ１＝５、Ｎ２＝５である。
【００５２】
Ｈ２＝Ｎ１×〔−Σｋ｛（ｇ１，ｋ／Ｎ１）×ｌｏｇ（ｇ２，ｋ／Ｎ１）｝〕＋
Ｎ２×〔−Σｋ｛（ｇ２，ｋ／Ｎ２）×ｌｏｇ（ｇ２，ｋ／Ｎ２）｝〕
＝５×〔−｛（１／５）×ｌｏｇ（１／５）＋（２／５）×ｌｏｇ（２／５）＋（２／５）×ｌｏｇ（２／５）｝〕＋
５×〔−｛（１／５）×ｌｏｇ（１／５）＋（３／５）×ｌｏｇ（３／５）＋（１／５）×ｌｏｇ（１／５）｝〕
＝１４．４６  …（４）
【００５３】
この結果、図９に示す例では、図９（Ｂ）で示す直線Ｌ２が選択されることになる。
【００５４】
以上、縦方向分割処理部３６Ａによる縦方向（ｙ軸方向）の分割について説明したが、横方向分割処理部３６Ｂによる横方向（ｘ軸方向）の分割は、縦横を入れ替えるだけで原理的には全く同じである。従って、横方向の分割手法については説明を省略する。
【００５５】
縦方向分割処理部３６Ａや横方向分割処理部３６Ｂによって選択された境界線候補は、例えば図１０に例示する区画リストの形式でメモリ装置１８又は補助記憶装置１６に格納される。図１０は、縦方向分割処理部３６Ａや横方向分割処理部３６Ｂによって更新される区画リストＬの一例である。図示するように、区画リストＬは、分割を繰り返すことによって生じた最小単位の（他の領域を含まない）矩形領域を、四辺の座標値で特定して列挙したものである。縦方向分割処理部３６Ａや横方向分割処理部３６Ｂが分割を行うと、分割された元の矩形領域は区画リストＬから除外され、分割によって生成された新たな矩形領域群が区画リストＬに追加される。
【００５６】
矩形領域検出部３８は、縦方向及び横方向の境界線候補が全てメモリ装置１８又は補助記憶装置１６に格納されると、これを読み出す。そして、例えば、縦方向及び横方向の境界線候補、並びに元の二次元平面の外縁線を用いて生成可能な全ての矩形領域について、領域内の座標の重み値を合計し、合計値が最も大きい（又は最も小さい）矩形領域を探索して、矩形領域検出問題の最適矩形とする。なお、矩形領域検出部３８の処理手法については種々の手法を採用することができ、このような網羅的な手法に限定されるものではない。
【００５７】
［処理フロー］
以下、矩形領域検出装置１により実行される、より具体的な処理の流れについて説明する。
【００５８】
図１１は、境界線候補選択部３６により実行される境界線候補選択処理の流れを示すフローチャートである。
【００５９】
まず、境界線候補選択部３６は、区画リストＬに、二次元平面全体を一個の矩形領域として設定する（Ｓ２００）。また、カウント値ｔの初期値として１を設定する（Ｓ２０２）。
【００６０】
次に、境界線候補選択部３６は、カウント値ｔが分割上限数ｒの２倍以下であるか否かを判定する（Ｓ２０４）。
【００６１】
カウント値ｔが分割上限数ｒの２倍以下である場合は、区画リストＬから把握される矩形領域の中で、領域内に存在する座標の数が最も多い矩形領域Ｄｔを取り出す（Ｓ２０６）。なお、この際に、重み値が同一種類のみである矩形領域は、矩形領域Ｄｔの探索から除外する。
【００６２】
次に、境界線候補選択部３６は、矩形領域Ｄｔ内の座標の数が（３×ｎ）／（ｒ２）未満であるか否かを判定する（Ｓ２０８）。ｎは、二次元平面全体に存在する座標の総数である。
【００６３】
次に、境界線候補選択部３６は、カウント数ｔが奇数であるか否かを判定する（Ｓ２１０）。
【００６４】
カウント数ｔが奇数である場合、矩形領域Ｄｔの上下に並ぶ全ての矩形領域を一つの矩形領域とみなして、縦方向分割処理部３６Ａを呼び出して縦方向分割処理を行い、境界線候補ｂｔを決定する（Ｓ２１２）。図１２は、矩形領域Ｄｔの上下に並ぶ全ての矩形領域を一つの矩形領域（後述する入力領域Ｄ；図中太枠）とみなして縦方向分割処理を行う様子を示す図である。
【００６５】
そして、矩形領域Ｄｔの上下に並ぶ全ての矩形領域を境界線候補ｂｔで分割し、区画リストＬにおける分割された矩形領域を、分割後の矩形領域で置き換えて更新する（Ｓ２１４）。
【００６６】
一方、カウント数ｔが偶数である場合、矩形領域Ｄｔの左右に並ぶ全ての矩形領域を一つの矩形領域とみなして、横方向分割処理部３６Ｂを呼び出して横方向分割処理を行い、境界線候補ｂｔを決定する（Ｓ２１６）。図１３は、矩形領域Ｄｔの左右に並ぶ全ての矩形領域を一つの矩形領域（後述する入力領域Ｄ；図中太枠）とみなして横方向分割処理を行う様子を示す図である。
【００６７】
そして、矩形領域Ｄｔの左右に並ぶ全ての矩形領域を境界線候補ｂｔで分割し、区画リストＬにおける分割された矩形領域を、分割後の矩形領域で置き換えて更新する（Ｓ２１８）。
【００６８】
Ｓ２１２・Ｓ２１４、又はＳ２１６・Ｓ２１８を実行すると、カウント値ｔを１増加させ（Ｓ２２０）、Ｓ２０４に戻る。そして、Ｓ２０６〜Ｓ２２０の処理を、カウント値ｔが分割上限数ｒの２倍を超えるか、或いは矩形領域Ｄｔの座標の数が（３×ｎ）／（ｒ２）を超えるまで、繰り返し実行する。Ｓ２０４、及びＳ２０８の処理は、二次元平面が過剰に分割されることを防止するための条件判定（終了条件判定）であり、一部を省略或いは変更することも可能である。
【００６９】
カウント値ｔが分割上限数ｒの２倍を超えるか、或いは矩形領域Ｄｔの座標の数が（３×ｎ）／（ｒ２）を超えると、区画リストＬに含まれる縦方向の境界線候補をまとめて縦方向の境界線候補リストを作成する。同様に、区画リストＬに含まれる横方向の境界線候補をまとめて横方向の境界線候補リストを作成する（Ｓ２２２）。縦方向及び横方向の境界線候補リストは、メモリ装置１８又は補助記憶装置１６に格納され、出力制御部３４によって外部装置に出力されるか、内部機能である矩形領域検出部３８によって読み出され、矩形領域検出に用いられる。
【００７０】
図１４は、縦方向分割処理（図１１のＳ２１２）に係る処理の流れを示すフローチャートである。
【００７１】
縦方向分割処理部３６Ａは、入力領域Ｄに含まれる座標のｘ座標値に基づいて、座標間に置くことが可能な縦方向の境界線ｂｊを全て列挙し、それらをＢ＝｛ｂ１，ｂ２，ｂ３，…ｂｍ｝とする（Ｓ３００）。入力領域Ｄは、前述のように、矩形領域Ｄｔの上下に並ぶ全ての矩形領域を一つの矩形領域とみなしたものである。入力領域Ｄに含まれる座標数がｎ*であるとすると、ｍ＝ｎ*−１となる。
【００７２】
ここで、座標間に置くことが可能な境界線ｂｊは、例えば、左右に座標が存在するとして、「右側（ｘ座標が大きい側）のｘ座標から微小値ｘ１を減算した値をｘ座標値とする境界線」と定義することができる。微小値ｘ１は、予め座標間隔の最小値が判明している場合、当該最小値未満の値とすればよい。図１５は、境界線ｂｊを座標間に設定する様子を示す図である。なお、これに限らず、左右の座標の中間に境界線ｂｊを設定してもよいし、他の境界線定義を行ってもよい。
【００７３】
次に、縦方向分割処理部３６Ａは、カウント値ｊの初期値を１とする（Ｓ３０２）。
【００７４】
次に、縦方向分割処理部３６Ａは、カウント値ｊが、境界線の総数ｍ以下であるか否かを判定する（Ｓ３０４）。
【００７５】
カウント値ｊが、境界線の総数ｍ以下である場合、境界線ｂｊの左側部分Ｓ１、及び右側部分Ｓ２において、前述したｇｉ，ｋを求め、スコア値Ｈｊを算出する（Ｓ３０６）。但し、入力領域Ｄには、既に区画リストＬに格納された横方向の境界線候補が含まれる場合があるが、この横方向の境界線候補をまたぐ座標間では、連続性が途切れるものとする。
【００７６】
そして、カウント値ｊを１増加させ（Ｓ３０８）、Ｓ３０４に戻る。
【００７７】
Ｓ３０４において、カウント値ｊが境界線の総数ｍを超えた場合、スコア値Ｈ１〜Ｈｍの中で最小値となるものを選択し、選択したスコア値に対応する境界線ｂｊを、縦方向分割の処理結果、すなわち境界線候補とする（Ｓ３１０）。
【００７８】
図１６は、横方向分割処理（図１１のＳ２１６）に係る処理の流れを示すフローチャートである。
【００７９】
横方向分割処理部３６Ｂは、入力領域Ｄに含まれる座標のｙ座標値に基づいて、座標間に置くことが可能な境界線ｂｊを全て列挙し、それらをＢ＝｛ｂ１，ｂ２，ｂ３，…ｂｍ｝とする（Ｓ４００）。入力領域Ｄは、前述のように、矩形領域Ｄｔの左右に並ぶ全ての矩形領域を一つの矩形領域とみなしたものである。入力領域Ｄに含まれる座標数がｎ*であるとすると、ｍ＝ｎ*−１となる。
【００８０】
ここで、座標間に置くことが可能な境界線ｂｊは、例えば、上下に座標が存在するとして、「上側（ｙ座標が大きい側）のｙ座標から微小値ｙ１を減算した値をｙ座標値とする境界線」と定義することができる。微小値ｙ１は、予め座標間隔の最小値が判明している場合、当該最小値未満の値とすればよい。係る手法は縦方向分割の場合と同様であるため、図示を省略する。なお、これに限らず、上下の座標の中間に境界線ｂｊを設定してもよいし、他の境界線定義を行ってもよい。
【００８１】
次に、横方向分割処理部３６Ｂは、カウント値ｊの初期値を１とする（Ｓ４０２）。
【００８２】
次に、横方向分割処理部３６Ｂは、カウント値ｊが、境界線の総数ｍ以下であるか否かを判定する（Ｓ４０４）。
【００８３】
カウント値ｊが、境界線の総数ｍ以下である場合、境界線ｂｊの上側部分Ｓ１、及びした側部分Ｓ２において、前述したｇｉ，ｋを求め、スコア値Ｈｊを算出する（Ｓ４０６）。但し、入力領域Ｄには、既に区画リストＬに格納された縦方向の境界線候補が含まれる場合があるが、この縦方向の境界線候補をまたぐ座標間では、連続性が途切れるものとする。
【００８４】
そして、カウント値ｊを１増加させ（Ｓ４０８）、Ｓ４０４に戻る。
【００８５】
Ｓ４０４において、カウント値ｊが境界線の総数ｍを超えた場合、スコア値Ｈ１〜Ｈｍの中で最小値となるものを選択し、選択したスコア値に対応する境界線ｂｊを、横方向分割の処理結果、すなわち境界線候補とする（Ｓ４１０）。
【００８６】
図１７は、矩形領域検出装置１が図１１に示すフローを実行して、入力平面に対して縦方向分割処理と横方向分割処理を交互に行った結果、最適矩形に至る様子を示す図である。図中、◇は、その時点で領域内に存在する座標の数が最も多い矩形領域Ｄｔを示している。また、最終図の太枠は、矩形領域問題における最適矩形を表している。本図で表される入力平面に対して本実施例のアルゴリズムを適用した結果、境界線８本を引いた時点で、矩形領域問題における最適矩形の境界線を発見することができる。
【００８７】
［動作例］
更に、図４に示した座標データを入力データとして図１１のフローを実行した場合の動作例について説明する。ここでは、カウント値ｔは１、２までとし、分割数上限値ｒ＝６とする。
【００８８】
まず、図１１のフローにおけるＳ２００において、最初に生成される区画リストＬは、既に図５に示したようになる。
【００８９】
次に、Ｓ２０２においてカウント値に１が設定され、Ｓ２０４においてカウント値（＝１）が分割上限数ｒ（＝６）の２倍以下であると判定される。
【００９０】
Ｓ２０６において取り出される矩形領域Ｄ１は、最初に生成される区画リストＬ、すなわち元の二次元平面である。
【００９１】
Ｓ２０８において、矩形領域Ｄ１に含まれる座標の数ｎ*は３０であるため、（３×３０）／（６２）＝２．５個以上であると判定される。Ｓ２１０においては、ｋ＝１であるため、Ｓ２１２に進む。
【００９２】
Ｓ２１２では、矩形領域Ｄ１の上下に並ぶ矩形領域、すなわち二次元平面全体を入力領域Ｄとして縦方向分割処理を行う。入力領域Ｄに含まれる座標間に設定し得る直線のｘ座標の集合Ｂは、次のように表される。直線数ｍは、ｎ*−１＝２９である。
【００９３】
Ｂ＝｛８５，１２５，２４５，２５５，２６５，２８５，３３５，３４５，３５５，３７５，４８５，５０５，５４５，５６５，５８５，６０５，６２５，６４５，６５５，６７５，７１５，７３５，７８５，８０５，８２５，８４５，８６５，８７５，９２５｝
【００９４】
これらの直線ｂ１〜ｂ２９のそれぞれについてスコア値Ｈｊを算出すると、その結果は図１８に示すようになる。図１８は、本実施例の矩形領域検出装置１が処理を行った結果、導出されるスコア値Ｈｊの例である。図から、スコア値Ｈｊの最小値はＨ２３＝８７．４であるため、縦方向の境界線候補ｂ２３のｘ座標＝７８５という結果を得る。
【００９５】
Ｓ２１４においては、矩形領域Ｄ１上下に並ぶ矩形領域（ここでは矩形領域Ｄ１そのもの）を境界線候補ｂ２３で分割し、区画リストＬにおける分割された矩形領域を、分割後の矩形領域で置き換える。この結果区画リストＬは、図１９に示すものに更新される。図１９は、本実施例の矩形領域検出装置１が処理を行った結果、生成される区画リストＬの例である。
【００９６】
Ｓ２２０においてカウント値ｔが２に変更され、Ｓ２０２に戻る。なお、上記と同様、Ｓ２０４、及びＳ２０８の終了条件は満たさないため、これについての説明を省略する。
【００９７】
Ｓ２０６において取り出される矩形領域Ｄ２は、図１９における上側（注；二次元平面においては左側）の領域である。Ｓ２１０においては、ｋ＝２であるため、Ｓ２１６に進む。
【００９８】
Ｓ２１６では、矩形領域Ｄ２の左右に並ぶ矩形領域、すなわち二次元平面全体を入力領域Ｄとして横方向分割処理を行う。入力領域Ｄに含まれる座標間に設定し得る直線のｙ座標の集合Ｂは、次のように表される。直線数ｍは、ｎ*−１＝２９である。
【００９９】
Ｂ＝｛２５，４５，７５，９５，１８５，２１５，２３５，２７５，３３５，３４５，３９５，４２５，４３５，４４５，４５５，５７５，５８５，６１５，６３５，６７５，６９５，７１５，７３５，７４５，７７５，７９５，８５５，９１５，９４５｝
【０１００】
これらの直線ｂ１〜ｂ２９のそれぞれについてスコア値Ｈｊを算出すると、その結果は図２０に示すようになる。図２０は、本実施例の矩形領域検出装置１が処理を行った結果、導出されるスコア値Ｈｊの例である。図から、スコア値Ｈｊの最小値はＨ１２＝６３．３であるため、横方向の境界線候補ｂ１２のｘ座標＝４２５という結果を得る。
【０１０１】
Ｓ２１８においては、矩形領域Ｄ２の左右に並ぶ矩形領域（ここでは矩形領域Ｄ２に右側領域を加えたもの）を境界線候補ｂ１２で分割し、区画リストＬにおける分割された矩形領域を、分割後の矩形領域で置き換える。この結果区画リストＬは、図２１に示すものに更新される。図２１は、本実施例の矩形領域検出装置１が処理を行った結果、生成される区画リストＬの例である。
【０１０２】
このようにカウント値ｔを増加させながら繰り返し処理を行い、カウント値ｔが９に至ったときの座標数最大の矩形領域Ｄ９は、図２２で表される。図２２は、本実施例の矩形領域検出装置１が処理を行った結果、抽出される座標数最大の矩形領域Ｄ９の例である。この矩形領域Ｄ９に含まれる座標の数は２個であるため、Ｓ２０８の終了条件を満たし、Ｓ２２２に進む。こうして得られた結果は、図２３で示すものとなる。図２３は、最終的に得られた複数の境界線候補を示す図である。図２３に示すデータは、メモリ装置１８又は補助記憶装置１６に格納されて用いられる。
【０１０３】
［他の手法を用いた場合との比較］
ここで、他の手法を用いて境界線候補を選択した場合との比較について述べる。既に知られた文献（J.R.QUINLAN,“Machine  Learning  1”,81-106,1986）には、メッシュ分割において、「情報ゲイン」という概念を適用することについて記載されている「情報ゲイン」とは、矩形領域内の座標の個数の不均衡さを考慮する際に利用できる概念の一つである。
【０１０４】
情報ゲインの概念に基づいて、上記のように分割された部分領域についてスコア値を算出する場合、スコア値Ｈ＃は、例えば次式（５）で表される。式中、ｇ＃ｉ，ｋは、「部分領域Ｓｉに含まれる種類ｋの座標の数」であり、本実施例のｇｉ，ｋのように、「部分領域Ｓｉに含まれる、座標成分が隣接し、且つ重み値が種類ｋである座標が連続する数」ではない。スコア値Ｈ＃の小さい直線が選択される点は、本実施例と同様であるものとする。
【０１０５】
Ｈ＃ｊ＝ΣｉＮｉ×〔−Σｋ｛（ｇ＃ｉ，ｋ／Ｎｉ）×ｌｏｇ（ｇ＃ｉ，ｋ／Ｎｉ）｝〕  …（５）
【０１０６】
上式（５）を図９で示す座標分布に適用すると、次式（６）、（７）で示す結果となる。
【０１０７】
Ｈ＃１＝Ｎ１×〔−Σｋ｛（ｇ＃１，ｋ／Ｎ１）×ｌｏｇ（ｇ＃１，ｋ／Ｎ１）｝〕＋
Ｎ２×〔−Σｋ｛（ｇ＃２，ｋ／Ｎ２）×ｌｏｇ（ｇ＃２，ｋ／Ｎ２）｝〕
＝４×〔−｛（１／４）×ｌｏｇ（１／４）＋（３／４）×ｌｏｇ（３／４）｝〕＋
６×〔−｛（４／６）×ｌｏｇ（４／６）＋（２／６）×ｌｏｇ（２／６）｝〕
＝８．７５  …（６）
【０１０８】
Ｈ＃２＝Ｎ１×〔−Σｋ｛（ｇ＃１，ｋ／Ｎ１）×ｌｏｇ（ｇ＃２，ｋ／Ｎ１）｝〕＋
Ｎ２×〔−Σｋ｛（ｇ＃２，ｋ／Ｎ２）×ｌｏｇ（ｇ＃２，ｋ／Ｎ２）｝〕
＝５×〔−｛（２／５）×ｌｏｇ（２／５）＋（３／５）×ｌｏｇ（３／５）｝〕＋
５×〔−｛（３／５）×ｌｏｇ（３／５）＋（２／５）×ｌｏｇ（２／５）｝〕
＝９．７１  …（７）
【０１０９】
この結果、より小さいＨ＃１を導出した図９（Ａ）で示す直線Ｌ１が選択されることになり、本実施例による結果とは異なることが判る。
【０１１０】
上式（５）に基づく手法（以下、便宜的に従来手法と称する）は、矩形領域内における重み値が同一種類の座標の個数の不均衡さを反映している。しかしながら、従来手法は、矩形領域内において重み値が同一種類の座標が塊をなしている（隣接し合っている）状況を反映したものとはならない。この結果、矩形領域検出問題において、できるだけ少ない境界線候補で有望なメッシュ状分割（境界線候補群）を与えることができない場合がある。
【０１１１】
矩形領域検出問題の特性から、メッシュ状分割された各矩形領域には、単一種類の座標のみが含まれていることが望ましい。図２４は、矩形領域検出問題の対象となる二次元平面の例である。一般的に、ある矩形領域内（例えば図２４の破線内）の最適矩形（局所解、すなわち○３個の矩形領域）は、その周りを□で囲まれるようになる。すなわち、与えられた領域と最適矩形との差の部分領域に□だけが含まれる（塊を成す）ようにメッシュ境界線を引くことが望ましい。二次元平面上で同一種類の座標が塊となるように区画を決めたいということは、一次元上で考えると同一種類の座標が連続的に並ぶように区切りたいということに相当する。そこで一次元上で連続するように選ぶようにすれば、二次元上で塊になるようにできるだろう、と考えられる。
【０１１２】
すなわち、境界線に沿って見ると、境界線付近に単一種類の座標が連続的に現れるような境界線が望ましいといえる。例えば、図２４の矢印で示す横境界線のすぐ上側に並ぶ矩形領域４個内に存在する座標を左から右に見ていくと、□２個、○３個、□１個、○２個の順となる。一方、下側に並ぶ矩形領域４個内に存在する座標を左から右に見ていくと、○２個、□４個、○１個の順となる。このような各矩形領域に連続的に現れる数（２個、３個等）が大きいほど、当該境界線が最適矩形の境界線となる可能性が高くなるのである。この点、従来手法は、境界線で分割される部分領域の座標の個数についての不均衡さを考慮しているが、同一種類の座標の連続性については考慮していない。
【０１１３】
これに対し、本実施例では、「座標成分が隣接し、且つ重み値が種類ｋである座標が連続する数」に基づく値を指標値として境界線候補を選択しているため、矩形領域内において重み値が同一種類の座標が塊をなしている状況を適切に反映させることができる。この結果、選択した境界線候補が、矩形領域検出問題の最適矩形として求められるべき矩形領域の境界線に一致する可能性を高めることができ、矩形領域検出問題において矩形領域を絞り込むための境界線候補を適切に選択することができる。
【０１１４】
図２５及び図２６は、与えられた座標データに対して、本実施例の矩形領域検出装置１が境界線候補を選択した場合と、従来手法に基づいて境界線候補を選択した場合とを比較するための図である。図２５（Ａ）は与えられた座標データ及び最適矩形（図中、太線矩形）を示し、図２５（Ｂ）は本実施例の矩形領域検出装置１が境界線候補を選択した結果を示している。図２５（Ｂ）に示すように（或いは、既に図１７で示したように）、本実施例の矩形領域検出装置１では、境界線候補を８本選択した時点で、最適矩形の四辺の境界線を全て選択することができた。
【０１１５】
一方、図２６（Ａ）は、従来手法に基づいて境界線候補を８本選択した結果を示し、図２６（Ｂ）は、従来手法に基づいて境界線候補を１２本選択した結果を示している。図示するように、従来手法に基づいて境界線候補を選択した場合、１２本の境界線候補を選択しても、依然として最適矩形の四辺の境界線を選択できなかった。
【０１１６】
このように、本実施例の矩形領域検出装置１では、従来手法に基づいて境界線候補を選択する場合に比して、少ない処理数で最適矩形の四辺の境界線を見つけることができる。これによって、分岐限定法等によって無駄な枝の枝切りを効率的に行うことができ、更に最適解若しくはそれに近い近似解を迅速に発見することができる。
【０１１７】
［まとめ］
以上説明した本実施例の矩形領域検出装置１、及び矩形領域検出方法、並びにこれらを実現可能なプログラムによれば、矩形領域検出問題において矩形領域を絞り込むための境界線候補を迅速且つ適切に選択することができる。
【０１１８】
［変形等］
以上、本発明を実施するための最良の形態について実施例を用いて説明したが、本発明はこうした実施例に何等限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変形及び置換を加えることができる。
【０１１９】
例えば、「分割の元となった直線に平行な座標軸に関する座標成分が隣接し、且つ重み値が同一種類である座標が連続する数」としてｇｉ，ｋを求めるものとしたが、「分割の元となった直線に直交する座標軸に関する…」と置換してもよい。
【０１２０】
また、縦方向分割処理と横方向分割処理を交互に行うものとしたが、元の二次元平面が縦又は横に長いような場合では、縦２回→横１回、或いは縦１回→横２回を繰り返す等と分割頻度を調整してもよい。
【０１２１】
また、縦方向分割処理と横方向分割処理を交互に行うものとしたが、縦方向分割処理のみ、或いは横方向分割処理のみを行うものであってもよい。
【０１２２】
また、図１１のＳ２１２において、座標数が最大の矩形領域Ｄｔの上下に並ぶ全ての矩形領域を一つの矩形領域とみなして縦方向分割処理を行うものとしたが、矩形領域Ｄｔから見て所定数上及び下の矩形領域のみを対象としてもよい。同様に、Ｓ２１６において、矩形領域Ｄｔの左右に並ぶ全ての矩形領域を一つの矩形領域とみなして横方向分割処理を行うものとしたが、矩形領域Ｄｔから見て所定数左及び右の矩形領域のみを対象としてもよい。更に、矩形領域Ｄｔのみを分割対象としてもよく、縦方向分割処理や横方法分割処理の対象となる入力領域Ｄの選び方は、種々の変更が可能である。
【０１２３】
また、入力領域Ｄの中で、境界線から所定距離σ（或いは所定座標数）以内の領域のみをスコア値Ｈｊの算出対象としてもよい。図２７は、入力領域Ｄの中で、境界線から所定距離σ（或いは所定座標数）以内の領域のみをスコア値Ｈｊの算出対象とする様子を模式的に示す図である。図中、スコア値Ｈｊの算出対象とする領域内の座標を実線で、それ以外の座標を破線で示している。
【０１２４】
以上の説明に関し、さらに以下の項を開示する。
（付記１）
正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納する座標データ取得手段と、
前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納する境界線候補選択手段と、
前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力する矩形領域検出手段と、
を備える矩形領域検出装置。
（付記２）
付記１に記載の矩形領域検出装置であって、
前記境界線候補選択手段は、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号及び値が同一である座標データが連続する数に応じて増減する指標値を算出する手段である、
矩形領域検出装置。
（付記３）
付記１又は２に記載の矩形領域検出装置であって、
前記境界線候補選択手段は、前記座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数、又は前記座標成分が隣接し且つ前記重み値の符号及び値が同一である座標データが連続する数が増加するほど、また該連続する座標グループ数が少ないほど、減少する傾向の前記指標値を算出し、該算出した指標値を各直線について合計し、該合計した値が最も小さくなった直線を選択する手段である、
矩形領域検出装置。
（付記４）
付記３に記載の矩形領域検出装置であって、
前記指標値は、Ｎｉ×〔−Σｋ｛（ｇｉ，ｋ／Ｎｉ）×ｌｏｇ（ｇｉ，ｋ／Ｎｉ）｝〕で表され、
該式中、ｋは重み値の符号、又は符号及び値であり、ｉは矩形領域の識別子であり、Ｎｉは矩形領域内の座標データ数であり、ｇｉ，ｋは前記座標成分が隣接し且つ重み値が同一種類である座標が連続する数である、
矩形領域検出装置。
（付記５）
付記１ないし４のいずれか１項に記載の矩形領域検出装置であって、
前記境界線候補選択手段は、前記二次元平面における第１の座標軸に平行な直線を選択する処理と、該第１の座標軸に直交する第２の座標軸に平行な直線を選択する処理を、交互に行う手段である、
矩形領域検出装置。
（付記６）
付記１ないし５のいずれか１項に記載の矩形領域検出装置であって、
前記境界線候補選択手段は、前記二次元平面上で平行な直線を複数設定する際に、既に選択した直線を用いて区画される矩形領域のうち、座標データ数が最大の矩形領域内を前記平行な複数の直線が通るように、前記平行な直線を複数設定する手段である、
矩形領域検出装置。
（付記７）
正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納するステップと、
前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納するステップと、
前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力するステップと、
をコンピュータが実行する矩形領域検出方法。
（付記８）
正又は負の値である重み値が付与された、二次元平面上の座標データを複数個取得して記憶手段に格納する処理と、
前記二次元平面上で平行な直線を複数設定し、該設定した各直線を境界線とする複数の矩形領域を設定し、該設定した複数の矩形領域に対して、前記記憶手段に格納された座標データを参照し、前記複数の直線に平行な又は直交する座標軸に関する座標成分が隣接し且つ前記重み値の符号が同一である座標データが連続する数に応じて増減する指標値をそれぞれ算出し、該算出した指標値を各直線について合計した値に基づいて前記複数設定した直線から一の直線を境界線候補として選択して前記記憶手段に格納する処理と、
前記記憶手段に格納された境界線候補のうちいずれかを境界線とし、領域内に存在する座標に付与された前記重み値の合計が最大又は最小となる矩形領域を検出して出力する処理と、
をコンピュータに実行させるプログラム。
【符号の説明】
【０１２５】
１      矩形領域検出装置
１０    ＣＰＵ
１２    ドライブ装置
１４    記憶媒体
１６    補助記憶装置
１８    メモリ装置
２０    インタフェース装置
２２    入力装置
２４    ディスプレイ装置
３０    マスター制御部
３２    入力制御部
３４    出力制御部
３６    境界線候補選択部
３６Ａ  縦方向分割処理部
３８    矩形領域検出部
【図１】
2013011984.tif 000004
【図２】
2013011984.tif 000005
【図３】
2013011984.tif 000006
【図４】
2013011984.tif 000007
【図５】
2013011984.tif 000008
【図６】
2013011984.tif 000009
【図７】
2013011984.tif 000010
【図８】
2013011984.tif 000011
【図９】
2013011984.tif 000012
【図１０】
2013011984.tif 000013
【図１１】
2013011984.tif 000014
【図１２】
2013011984.tif 000015
【図１３】
2013011984.tif 000016
【図１４】
2013011984.tif 000017
【図１５】
2013011984.tif 000018
【図１６】
2013011984.tif 000019
【図１７】
2013011984.tif 000020
【図１８】
2013011984.tif 000021
【図１９】
2013011984.tif 000022
【図２０】
2013011984.tif 000023
【図２１】
2013011984.tif 000024
【図２２】
2013011984.tif 000025
【図２３】
2013011984.tif 000026
【図２４】
2013011984.tif 000027
【図２５】
2013011984.tif 000028
【図２６】
2013011984.tif 000029
【図２７】
2013011984.tif 000030