(57)【特許請求の範囲】
【請求項１】
テンプレート画像の集合を少なくとも含む画像領域分割ルールデータを蓄積する画像領域分割ルールデータベースと、与えられた制約充足問題に対応する充足解を探索する制約ソルバと、画像領域分割エンジンとを少なくとも備え、対象画像データを領域分割し、その領域分割した分割矩形データを出力する画像領域分割装置であって、
前記画像領域分割エンジンは、
テンプレート画像の対象画像上でのマッチング位置が複数存在する場合に、それら位置を全て列挙して得られる画像マッチ位置候補のいずれを選択するかと、当該テンプレート画像の座標値がいずれになるか、が整合するよう関係を拘束する制約条件を与えるとともに、制約モデルデータ上の当該部分と同じ構造の部分が複数存在する場合に、それらのマッチ位置候補の選択を互いに重複して行わないよう関係を拘束する制約条件を与える手段を具備した
ことを特徴とする画像領域分割装置。
【請求項２】
請求項１に記載の画像領域分割装置において、
前記に加え、
画像断片オブジェクトに対して、画像領域分割ルールデータ内のテンプレート画像のいずれを割り当てるかと、当該テンプレート画像のマッチ位置候補及び座標値がいずれになるかが整合するよう関係を拘束する制約条件を与えるとともに、制約モデル上の当該部分と同じ構造の部分が複数存在する場合に、それらのテンプレート画像候補の選択を互いに重複して行わないよう関係を拘束する制約条件を与える手段を具備した
ことを特徴とする画像領域分割装置。
【請求項３】
請求項２に記載の画像領域分割装置において、
前記に加え、
画像領域分割ルールの一部が、画像マッチング箇所を含む同種の構造が可変個数現れる形になっている場合に、当該構造の個数が実際にいくつ存在するかを含め制約ソルバで計算可能とする目的で、所定の個数の制約モデルパーツを生成し、それら各々の内部の制約条件の集合に対して有効、無効を切り替え可能となるようメタ制約条件を与え、これらを制約モデルデータとして追加する手段を具備した
ことを特徴とする画像領域分割装置。
【請求項４】
テンプレート画像の集合を少なくとも含む画像領域分割ルールデータを蓄積する画像領域分割ルールデータベースと、与えられた制約充足問題に対応する充足解を探索する制約ソルバと、画像領域分割エンジンとを少なくとも備え、対象画像データを領域分割し、その領域分割した分割矩形データを出力する画像領域分割方法であって、
前記画像領域分割エンジンにより、
対象画像データに対応する画像領域分割ルールデータを画像領域分割ルールデータベースから取り出し、当該画像領域分割ルールデータを制約モデルデータに変換し、当該制約モデルデータを制約充足問題として制約ソルバに渡し、制約ソルバから返却された前記制約モデルデータに対応する制約充足解データを分割矩形データに変換する場合において、
制約ソルバに所定の評価値が最小となる解の探索を依頼するステップと、
制約ソルバの探索終了を待機するステップと、
探索終了を契機に解を領域の分割矩形データに変換するステップと、
上位機能に返却する、あるいは上位機能を通してユーザに表示するステップと、
さらに他の解を得ることを意図した継続の探索処理の命令が、上位機能から自動的に発行されたのを契機に、あるいはユーザから上位機能を通して明示的に指示したのを契機に、直前の解の評価値よりも大きい解を許容し小さい解を禁止する新たな制約条件を制約モデルデータに追加するステップと、
再び制約ソルバへの解の探索を依頼するステップとを含む
ことを特徴とする画像領域分割方法。
【請求項５】
テンプレート画像の集合を少なくとも含む画像領域分割ルールデータを蓄積する画像領域分割ルールデータベースと、与えられた制約充足問題に対応する充足解を探索する制約ソルバと、画像領域分割エンジンとを少なくとも備え、対象画像データを領域分割し、その領域分割した分割矩形データを出力する画像領域分割方法であって、
前記画像領域分割エンジンにより、
対象画像データに対応する画像領域分割ルールデータを画像領域分割ルールデータベースから取り出し、当該画像領域分割ルールデータを制約モデルデータに変換し、当該制約モデルデータを制約充足問題として制約ソルバに渡し、制約ソルバから返却された前記制約モデルデータに対応する制約充足解データを分割矩形データに変換する場合において、
制約ソルバに所定の評価値が最小となる解の探索を依頼するステップと、
ソルバの探索終了を待機するステップと、
探索終了を契機に、得られた制約充足解データにおいて制約モデルパーツが有効な個数が予め制約モデルデータに組み込まれた制約モデルパーツの個数より小さい場合はそれを分割結果として出力するステップと、
得られた制約充足解データにおいて制約モデルパーツの有効な個数が前記個数と同じ場合はさらに同じ制約モデルパーツを所定個数生成し、前記制約モデルデータに追加するステップと、
再び制約ソルバに前記制約モデルデータを渡して探索を依頼するステップとを含む
ことを特徴とする画像領域分割方法。
【請求項６】
コンピュータを、請求項１乃至３のいずれかに記載の画像領域分割装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データ処理、特に画像データ中から所定の領域を判別して分割する技術に関する。
【背景技術】
【０００２】
＜技術分野の詳細＞
画像マスクツールは、指定された複数の画像データファイルに対して、所定の部分領域を黒色で塗りつぶすなどのマスク処理を施し、変換後のファイルとして出力するアプリケーションプログラム（以下、単にアプリケーション）である。処理対象ファイルの指定、マスクする領域の指定などを対話的に行うアプリケーションも考えられるが、ここでは大量の画像ファイル、多種類の画像内容を扱う最も単純な形態としてバッチツールを想定する。
【０００３】
ここで扱う画像データファイルは、主にＧＵＩ端末上でのユーザの操作の履歴として、蓄積された大量のファイルである。当該ファイルは、別途用意・実行されるプログラム、例えば当該ＧＵＩ端末の常駐サービスやバックグランドアプリケーションとして実行されるエージェントプログラム（以下、単にエージェント）によって生成されることを想定している。エージェントは、ユーザが実施する操作のタイミングごとに、ＧＵＩ端末の画面上の表示内容についてオペレーティングシステム（ＯＳ）を介して画像データとして取得し、ＢＭＰやＰＮＧなどの形式の画像データファイルとして保存していく。
【０００４】
このとき、ＧＵＩ端末の画面上でアクティブなウィンドウの境界枠内の画像内容だけが記録されることを前提としているため、蓄積される画像データの縦横の長さ（画像矩形サイズ）はウィンドウごとに異なり、まちまちである。さらに、ウィンドウがリサイズされた場合は、同じウィンドウに対しても縦横の長さがその前後で異なることとなる。ウィンドウ内のＧＵＩ要素に表示される個人情報を読み取れないようにするためには、テーブル（表形式のＧＵＩ要素）コントロール上の適切な領域をマスクする必要があるが、ウィンドウ左上からの相対座標による矩形を指定しても、リサイズによりずれてしまう場合がある。
【０００５】
また、ここで扱う画像データファイルは、そこに表示されている内容の種類を識別する情報として、所定のファイル名が付与される。当該ファイル名は、画像データの取得時にエージェントがＯＳを介して得られる当該ウィンドウに関する基本的なデータ、例えば当該のウィンドウの属性（ウィンドウタイトル、スタイル、クラス名など）や、それを所有するプロセスの起動ファイル名（プログラム名）によって生成されることを前提としている。エージェントは、取得した属性値をそれぞれ文字列化した上で、所定の順序でハイフン「−」を挟んで連結するなどにより、得られた文字列をそのファイル名として画像データを保存していく。
【０００６】
このとき、記録対象のウィンドウの種類やアプリケーションの種類によって画像内容が異なったり、ユーザの操作（リサイズによるウィンドウ矩形サイズ変化やボタン押下によるアプリケーション内部の状態変化）に伴って表示内容が変化したような場合でも、それらに依存した個別的な情報は記録されないことを前提としている。即ち、蓄積される画像ファイルの識別の手がかりは、全てウィンドウ共通のものしかない。
【０００７】
さらに、アプリケーションの種類によっては、これらの情報を用いた識別では、十分に対処できない場合もある。表計算アプリケーションや文書編集アプリケーションなどのドキュメントデータを扱うウィンドウや、Ｗｅｂブラウザなどのコンテンツ情報を扱うウィンドウは、ウィンドウタイトルが異なっても表示内容がアプリケーションごとに共通的な部分がある一方で、ウィンドウタイトルが同じでも表示内容がドキュメントやコンテンツごとに異なる部分がある（異なるフォルダの同名ドキュメントや異なるサイトの同名コンテンツの場合が存在し得るため）。
【０００８】
本発明の技術背景は、画像マスクツール内部の以下の機能についてである。
【０００９】
１つは入力された画像内容に応じて、マスクをかける領域の位置を決定する機能である。前述した通り、対象とする画像矩形サイズは同一とは限らないため、 相対座標のような単純な指定方法ではずれてしまう場合がある。画像内容に応じて領域の位置を調整・計算する必要がある。
【００１０】
また、１つは入力された画像内容に応じて、マスクをかける領域の有無やマスクパターンの種別を判定する機能である。前述した通り、対象とする画像内容の種類はウィンドウ共通の識別情報と直接的な関連性がないため、ウィンドウタイトルを基にマスクすべき領域の有無とマスクパターンの種別を決定するのでは間違ってしまう場合がある。画像内容そのものの特徴を基にマスクをかける領域の有無やマスクパターンの種別を判定する必要がある。
【００１１】
なお、ここでマスクパターンの種別とは、どのような位置関係にしたがってマスク領域を設定すべきかといった位置調整方法の種類を指すものとする。
【００１２】
≪従来技術≫
＜画像パターン認識についての従来技術＞
〈画像マッチングを使う方法のメリットと課題〉
マスクすべき領域の近傍の画像断片を位置計算のための情報として指定しておき、画像マスクツールの実行時に画像テンプレートマッチングアルゴリズムを使用して、ウィンドウ領域内の相対位置の座標を調整する方法がある。マスク領域の特定に、この画像テンプレートマッチングを応用する方法が容易に創出可能である。
【００１３】
また同様に、ウィンドウ上の特徴的な画像断片をマスク領域の有無やマスクパターンの種別を識別するための情報として指定しておき、画像マスクツールの実行時に画像テンプレートマッチングアルゴリズムを使用して、処理対象の画像内容に画像断片が存在するか否かを閾値判定する方法がある。ウィンドウが画像内容からみて、ある観点で求めているものに該当するか否かの判定に、この画像テンプレートマッチングを応用する方法が容易に創出可能である。
【００１４】
しかし、画像テンプレートマッチングを応用した方法は、画像内容、及びＧＵＩ要素のレイアウトに依存するという課題がある。特定する対象そのものの画像内容についての課題は、サイズ可変（事例：ボタンの認識）に関係する。特定するＧＵＩ要素のレイアウト依存性についての課題は、ＧＵＩレイアウトにおける周辺構造（事例：表の認識）、並びに内部構造（事例：フォームの認識）に関係する。以下ではそれぞれについて事例をあげて具体的に述べる。
【００１５】
〈任意のレイアウトに対応する従来の方法と課題〉
文字領域抽出に制約充足を用いた従来の方法として、非特許文献１に記載の方法がある。当該方法では「文字配置特徴として、文字の近接性、サイズの一致、文字配置の直線性、文字の等間隔配置等が挙げられる。本手法では、これらの特徴の参照を制約充足問題としてとらえ、各特徴を反映した関数を用い」ており、多項式時間では解き難い問題に対して良く用いられる近傍探索法の一般化手法であるシミュレーテッドアニーリング法を用いている。しかしながら、当該文献においては１５要素程度のレイアウトを処理する事例に対しても、多くの計算時間を要するとだけ述べられており、その具体的評価は行われていない。本発明の技術分野で実際に扱う規模のレイアウトを対象とした場合、想定するようなツールとして成立しない程度に計算時間が増大することが課題である。
【００１６】
≪従来技術の課題≫
＜特定する対象自身の課題（その１：サイズ可変）＞
〈サイズ可変に対する容易に創出可能な方法〉
テンプレートマッチングによる方法の課題の１つは、特定したい操作対象のサイズが可変であると、ウィンドウのリサイズに従って矩形領域が変化してしまう場合に対応できないという課題である。
【００１７】
＜相対位置関係の課題（その１：周辺要素との相対位置関係による位置特定）＞
認識させたい領域が、表の内部のセルのように、表示内容が実行時ごとに変わる場合は、水平方向の位置をカラムヘッダのセルの画像断片のマッチングによって得て、その位置を基準として垂直方向の位置をカラムヘッダからの相対位置の座標によって得ることにより、２つの位置を総合して目的とするセルの位置を得る方法が容易に創出可能である。
【００１８】
しかし、従来の技術では、識別させようとするセルを含む表のカラムのサイズ、順序、内容が変化してしまう場合に対応できないという課題がある。
【００１９】
＜相対位置関係の課題（その２：内部要素同士の相対位置関係による識別）＞
識別させたいウィンドウが占める領域のサイズやそこに表示される情報の種類や量によって内部レイアウトが変わる場合は、それによって影響を受けないウィンドウ画像内部に存在する特徴的な画像断片の存在有無を基に、マスク対象のウィンドウを識別する方法が容易に創出可能である。しかしながら、本来、異なる個体あるいは異なる種類として認識させたいウィンドウが、たまたま同じ画像断片を含んでいた場合にそれを誤認する可能性がある。これに対しては、複数の異なる画像断片の相対的な位置関係を含めた組み合わせによって指定する方法も容易に創出可能である。
【００２０】
しかし、従来の技術では、識別させようとするフォームのアイテムのサイズ、順序、内容ごとにハードコーディングしなければ対応できないという課題がある。なおここで、フォームのアイテムとは、フォームを構成するＧＵＩ要素を指し、例えばラベル、テキストフィールド、コンボボックスなどが該当する。
【００２１】
＜上記課題の解決方法とそれを実現する場合のアーキテクチャの課題＞
この課題を具体的かつ詳細に分析すると、大きく３つのレベルに分けられる。
【００２２】
〈詳細１：ハードコーディングを不要にできない（構造ごとに実装が必要）〉
従来の技術では、上記で挙げた変化に対しては適用対象アプリケーションのＧＵＩレイアウトの仕様に依存した処理が個々に必要であり、共通化する方法は提供されていないという課題があった。
【００２３】
〈詳細２：実装をシンプルにできない（エンジンの仕様が簡潔ではない）〉
上記課題に対する望ましいアプローチとしては、設定パラメータやルールベースの処理エンジンを実現することが考えられる。しかし、一般的に言えることとして、このようなアプローチをとろうとすると、設定やルールの形式が多様になる傾向がある。
【００２４】
従来の技術では、それを処理するエンジンの仕様が複雑化するため、エンジンの開発コストや保守コストが増大するという課題があった。
【００２５】
〈詳細３：一般ユーザ向けにできない（ルール定義の作業が簡単ではない）〉
上記課題に対する望ましいアプローチとしては、特定や識別のためのルールを定義（作成・編集）する場合に、様々な入力画像の様々な相対位置変化に対して、本来意図した結果を得られるように複雑なルール形式を採用することが考えられる。しかし、一般的に言えることとして、このようなアプローチをとろうとすると、ルールの入力方法の習得が必要になるため、使用できるユーザが限定されてしまう課題があった。
【発明の概要】
【発明が解決しようとする課題】
【００２６】
上述した課題を解決するため、出願人は、平成２４年７月４日に「画像領域分割装置、その方法及びプログラム」に係る発明の特許出願（特願２０１２−１５０４５９）（以下、先願と呼ぶ。）を行った。しかし、先願には、以下の実用上の課題が４つ存在した。
【００２７】
〈画像マッチ位置が複数の場合に対応できない〉
（マッチ位置の複数の候補を扱えない）
先願では、その明細書の段落［０１１２］〜［０１１６］の記載及びその図１１、図１１−１〜１１−３から分かるように、画像マッチ位置が複数存在する場合を考慮していない。
【００２８】
例えば、図１に示す画像断片、すなわちテンプレート画像0101〜0105の集合を含む画像領域分割ルール（マッチパターン）を、図２の画像マッチ位置候補0201〜0205及び0211〜0214を含む画像事例に適用した場合、画像マッチングアルゴリズムから出力された１つのマッチ位置に対してルール評価が行われ、解として出力される。詳細には、１つのテンプレート画像に対して複数のマッチ位置が算出される場合でも、アルゴリズムの実装の都合で適当に１つのマッチ位置が選択され、その選択は本来の画像領域分割の基準とは無関係である。そのため、たまたま選択されたマッチ位置で制約が充足されれば、解として画像領域分割結果として出力されるが、その成否は偶然性に依存する。
【００２９】
例えば、図３では、太い破線のマッチ位置が選択され、細い破線のマッチ位置は選択されず、前者が制約充足エンジンの制約モデルとしてソルバが起動され、後者は破棄されたとすると、一点鎖線の画像領域が出力され、意図した分割が行われた場合となっている。しかし、図４のようにマッチ位置の選択が行われると、「Button1」に相当するキャプション文字列のテンプレート画像がマッチパターンの矩形内ではないため、制約を充足する解が存在しないという結果がソルバから通知され、意図した分割が行われない（分割に失敗する）場合となっている。また、図５のように、マッチパターンの右上隅の位置としてボタン「Button2」の右上隅の位置が選択されてしまうと、左上隅の位置との関係で制約を充足することができず、同様の結果がソルバから通知される。
【００３０】
すなわち、たまたま選択されたマッチ位置が制約を充足しないとしても、当該画像領域分割ルールが全く解をもたないとは限らない。
【００３１】
また、仮に解が出力がされたとしても、当該解が制約を充足する唯一の解である保証はなく、他にも制約を充足する別の解が存在する可能性がある。
【００３２】
例えば、図１のルールを図６の画像事例に適用した場合、図７のように意図した画像分割結果が得られる場合も、図８のように画像分割結果が得られない場合もある。この点では図２の画像事例と同じである。しかし、図６の画像事例では図７の結果がたまたま出力されたことをもって、それが唯一の解であるとは限らず、実際、この他に図９のように制約を充足するが、意図した結果とは異なる画像分割結果が出力される場合がある。
【００３３】
〈複数の解が存在する場合に対応できない〉
先願では、制約を充足する以外に、所定のスコアが最小となるような最適解を求める構成となっている。前記課題のように複数の候補から選択組み合わせを行う場合、制約を充足する解を列挙すると、多数の組み合わせが出力される。一方で最適解だけを求めると、その中でスコアが最小となる組み合わせが出力されるが、それが本来求めたい解であるとは限らない。
【００３４】
この場合、最小だけではなく、２番目、３番目というようにスコアの小さい順に列挙していくことで、求める解に近い結果を得ることができる。また、これらの中に本来求める解がない場合でも、順に出力される解の内容を把握することで、スコア算定の基準や方法を修正し、当該の分割モデルで本来意図した結果が出力されるように改善する作業が効率良く行える。
【００３５】
しかしながら、上記のような対話的な解出力を、既存の制約ソルバを呼び出す方式で実現するには、ソルバの実装に依存したＡＰＩを利用する必要があった。このようにソルバのつくりに頼らずに、呼び出す側の方式で実現することができていなかった。
【００３６】
〈テンプレート画像が異なるだけの同種のルールをまとめて定義できない〉
（矩形領域パターンが同じでテンプレート画像が異なるルールを共通化できない）
（テンプレート画像の複数の候補を扱えない）
図１０のようなマッチ箇所の候補、ここではボタンを多数種類含む画像事例を扱う場合、全てのボタンに対するルールを逐一定義するのは多くの手数を要する。多くの場合、ボタンの四隅のテンプレート画像は全てのボタンで共通であり、その内部に領域を占めるキャプション文字列のテンプレート画像だけがボタンごとに異なる。そこで、図１１のように、四隅のテンプレート画像でルールを１つ定義し、その内部にキャプション文字列のテンプレート画像を複数候補として関連付けることが考えられる。
【００３７】
これによって、多数のルールインスタンスの共通部分を１つの定義で記述でき、モデルの作成や管理が効率化できる。例えば、図１０の画像事例においては２７種類のボタンを識別するためのルールを、１つのパターンと２７個のテンプレート画像を関連付けることによって、まとめて記述することが考えられる。図１２は制約を充足するが、意図した結果とは異なる画像分割結果が出力される場合の例を示す。また、図１３は共通のルールを適用できる異なるＧＵＩの画像事例を示すもので、同図（ａ）（ｂ）中の1301〜1303は同じ画像領域を示す。
【００３８】
〈上記の同種ルールのマッチ箇所が可変個数の場合に対応できない〉
図１４のルールを図１５の画像事例に適用する場合、マッチ箇所の個数が可変数になることを考慮する必要がある。つまり、１月、３月…の場合は１〜３１日、４月、６月、９月…の場合は１〜３０日、がカレンダー上に存在する。また２月は、１〜２８日の場合と、１〜２９日の場合の両方を考慮する必要がある。月ごとの日数や閏年を考慮して場合ごとにルールを生成する方法も考えられるが、手作業で行うには手間が多く管理が煩雑になる。ルールエディタの機能として自動生成するには、特定のドメインに特化しており、類似の要件に対して汎用的に対応することができない。
【課題を解決するための手段】
【００３９】
本発明では、上記課題を解決するために、分割ルールから制約モデルを生成する処理を拡張し、これまでの制約モデルに、画像マッチ位置の複数の候補と、テンプレート画像の複数の候補と、テンプレートパターンの複数の候補と、からの組み合わせ制約問題を含んだ制約モデルを生成可能とする。
【００４０】
詳細には、本発明は、
テンプレート画像の集合を少なくとも含む画像領域分割ルールデータを蓄積する画像領域分割ルールデータベースと、与えられた制約充足問題に対応する充足解を探索する制約ソルバと、画像領域分割エンジンとを少なくとも備え、対象画像データを領域分割し、その領域分割した分割矩形データを出力する画像領域分割装置であって、
前記画像領域分割エンジンは、
テンプレート画像の対象画像上でのマッチング位置が複数存在する場合に、それら位置を全て列挙して得られる画像マッチ位置候補のいずれを選択するかと、当該テンプレート画像の座標値がいずれになるか、が整合するよう関係を拘束する制約条件を与えるとともに、制約モデルデータ上の当該部分と同じ構造の部分が複数存在する場合に、それらのマッチ位置候補の選択を互いに重複して行わないよう関係を拘束する制約条件を与える手段を具備したことを特徴とする。
【００４１】
また、本発明は、前記画像領域分割装置において、
前記に加え、
画像断片オブジェクトに対して、画像領域分割ルールデータ内のテンプレート画像のいずれを割り当てるかと、当該テンプレート画像のマッチ位置候補及び座標値がいずれになるかが整合するよう関係を拘束する制約条件を与えるとともに、制約モデル上の当該部分と同じ構造の部分が複数存在する場合に、それらのテンプレート画像候補の選択を互いに重複して行わないよう関係を拘束する制約条件を与える手段を具備したことを特徴とする。
【００４２】
また、本発明は、前記画像領域分割装置において、
前記に加え、
画像領域分割ルールの一部が、画像マッチング箇所を含む同種の構造が可変個数現れる形になっている場合に、当該構造の個数が実際にいくつ存在するかを含め制約ソルバで計算可能とする目的で、所定の個数の制約モデルパーツを生成し、それら各々の内部の制約条件の集合に対して有効、無効を切り替え可能となるようメタ制約条件を与え、これらを制約モデルデータとして追加する手段を具備したことを特徴とする。
【００４３】
また、本発明は、
テンプレート画像の集合を少なくとも含む画像領域分割ルールデータを蓄積する画像領域分割ルールデータベースと、与えられた制約充足問題に対応する充足解を探索する制約ソルバと、画像領域分割エンジンとを少なくとも備え、対象画像データを領域分割し、その領域分割した分割矩形データを出力する画像領域分割方法であって、
前記画像領域分割エンジンにより、
対象画像データに対応する画像領域分割ルールデータを画像領域分割ルールデータベースから取り出し、当該画像領域分割ルールデータを制約モデルデータに変換し、当該制約モデルデータを制約充足問題として制約ソルバに渡し、制約ソルバから返却された前記制約モデルデータに対応する制約充足解データを分割矩形データに変換する場合において、
制約ソルバに所定の評価値が最小となる解の探索を依頼するステップと、
制約ソルバの探索終了を待機するステップと、
探索終了を契機に解を領域の分割矩形データに変換するステップと、
上位機能に返却する、あるいは上位機能を通してユーザに表示するステップと、
さらに他の解を得ることを意図した継続の探索処理の命令が、上位機能から自動的に発行されたのを契機に、あるいはユーザから上位機能を通して明示的に指示したのを契機に、直前の解の評価値よりも大きい解を許容し小さい解を禁止する新たな制約条件を制約モデルデータに追加するステップと、
再び制約ソルバへの解の探索を依頼するステップとを含むことを特徴とする。
【００４４】
さらに、本発明は、
テンプレート画像の集合を少なくとも含む画像領域分割ルールデータを蓄積する画像領域分割ルールデータベースと、与えられた制約充足問題に対応する充足解を探索する制約ソルバと、画像領域分割エンジンとを少なくとも備え、対象画像データを領域分割し、その領域分割した分割矩形データを出力する画像領域分割方法であって、
前記画像領域分割エンジンにより、
対象画像データに対応する画像領域分割ルールデータを画像領域分割ルールデータベースから取り出し、当該画像領域分割ルールデータを制約モデルデータに変換し、当該制約モデルデータを制約充足問題として制約ソルバに渡し、制約ソルバから返却された前記制約モデルデータに対応する制約充足解データを分割矩形データに変換する場合において、
制約ソルバに所定の評価値が最小となる解の探索を依頼するステップと、
ソルバの探索終了を待機するステップと、
探索終了を契機に、得られた制約充足解データにおいて制約モデルパーツが有効な個数が予め制約モデルデータに組み込まれた制約モデルパーツの個数より小さい場合はそれを分割結果として出力するステップと、
得られた制約充足解データにおいて制約モデルパーツの有効な個数が前記個数と同じ場合はさらに同じ制約モデルパーツを所定個数生成し、前記制約モデルデータに追加するステップと、
再び制約ソルバに前記制約モデルデータを渡して探索を依頼するステップとを含むことを特徴とする。
【発明の効果】
【００４５】
本発明によれば、画像領域分割パターンごとにハードコーディングすることなく、多様な適用画像や多様な利用目的に共通化された処理で対応することが可能となるとともに、画像マッチ位置が複数存在する場合やテンプレート画像が複数存在する場合であっても適切な解を得ることができ、また、テンプレート画像のマッチ箇所の個数が変化する場合であっても対応でき、さらにまた、複数の解が存在する場合でも制約条件を追加するのみで最適解とは異なる、ユーザの希望する解を得ることができる。
【図面の簡単な説明】
【００４６】
【図１】画像領域分割ルールの一例を示す説明図
【図２】複数のマッチ位置候補を含む第１の画像事例を示す説明図
【図３】解として期待される分割領域の例を示す説明図
【図４】解として制約を充足しない分割領域の一例を示す説明図
【図５】解として制約を充足しない分割領域の他の例を示す説明図
【図６】複数のマッチ位置候補を含む第２の画像事例を示す説明図
【図７】解として期待される分割領域の例を示す説明図
【図８】解として制約を充足しない分割領域の一例を示す説明図
【図９】解として制約を充足するが期待されない分割領域の一例を示す説明図
【図１０】マッチ位置候補を多数種類含む画像事例の一例を示す説明図
【図１１】画像領域分割ルールの第２の例を示す説明図
【図１２】解として制約を充足するが期待されない分割領域の一例を示す説明図
【図１３】共通のルールを適用できる異なるＧＵＩの画像事例を示す説明図
【図１４】画像領域分割ルールの第３の例を示す説明図
【図１５】マッチ位置候補が可変個数の画像事例を示す説明図
【図１６】先願の画像領域分割装置の機能構成図
【図１７】先願の画像領域分割エンジンの動作フローチャート
【図１８】先願の画像領域分割エンジンの機能構成図
【図１９】画像領域分割エンジンの内部の動作フローチャート
【図２０】画像領域分割エンジンの内部の動作フローチャート
【図２１】画像領域分割エンジンの内部の動作フローチャート
【図２２】画像領域分割エンジンの内部の動作フローチャート
【図２３】矩形に関する呼称の定義を示す説明図
【図２４】作業データ蓄積部のデータスキーマを示す説明図
【図２５】作業データ蓄積部のデータスキーマを示す説明図
【図２６】本発明の画像領域分割装置の機能構成図
【図２７】本発明の画像領域分割エンジンの機能構成図
【図２８】本発明の画像領域分割エンジンの動作フローチャート
【図２９】複数のマッチ位置候補に対する選択制約を示す説明図
【図３０】複数のマッチ位置候補から１つ選択する制約モデルを示す説明図
【図３１】複数のマッチ位置候補から複数選択する制約モデルを示す説明図
【図３２】マッチ位置とテンプレート画像を同時に候補選択する制約モデルを示す説明図
【図３３】可変個数の候補選択を行う制約モデルを示す説明図
【発明を実施するための形態】
【００４７】
≪先願発明≫
まず、本発明の説明のため、本発明と共通する先願部分について説明する。
【００４８】
＜画像領域分割エンジンの使用形態＞
図１６は先願の画像領域分割エンジン（以下、単に「分割エンジン」）を含む先願の画像領域分割装置の実施の形態の機能構成を示すもので、先願の画像領域分割装置は、分割エンジン１とともに、作業データ蓄積部２、制約ソルバ３及び上位機能制御部４を含んで構成される。
【００４９】
ここで、作業データ蓄積部２は、上位装置から上位機能制御部４を通じて入力された画像領域分割ルールデータ（以下、単に「分割ルールデータ」）２１及び分割対象画像データ２２を一時的に蓄積するとともに、分割エンジン１からの分割成否データ２３及び分割結果データ２４を一時的に蓄積し、この際、請求項でいう画像領域分割ルールデータベースを構成する。制約ソルバ３は、与えられた制約充足問題に対応する充足解を探索する周知のもので、分割エンジン１から制約モデルデータ３１を受け取って充足解を探索し、その実行結果を制約充足解データ（得られた場合のみ）３２とともに分割エンジン１へ返却する。上位機能制御部４は、上位装置との間のデータのやり取りを制御するとともに、上位装置からの命令に従って画像領域分割処理を制御する。なお、図示しないが、ユーザの操作に基づき分割ルールデータを作成・編集するルールエディタが上位機能制御部４を通じて接続されているものとする。
【００５０】
分割エンジン１は、上位機能制御部４の制御により画像領域分割の開始時の手続呼び出し及び画像領域分割の終了後の返却値受け取りを実行する。また、分割エンジン１はその内部処理で制約ソルバ３の手続呼び出し及び返却値受け取りを実行する。
【００５１】
また、分割エンジン１は、作業データ蓄積部２に蓄積された分割ルールデータ２１及び分割対象画像データ２２を基に、制約ソルバ３に入力する制約モデルデータ３１を生成する制約モデル生成部機能（制約モデル生成部）１１と、制約ソルバ３から返却された解探索の実行結果及び／又は制約充足解データ３２を基に、分割成否データ２３及び／又は分割結果データ２４を生成する充足結果解釈機能（充足結果解釈部）１２とを備えて構成されている。
【００５２】
図１７に分割エンジン１を主体とした本画像領域分割装置の動作フローを示す。
【００５３】
分割エンジン１は上位機能制御部４から呼び出されると、まず、作業データ蓄積部２の分割ルールデータ２１及び画像データ２２を基に制約モデルデータ３１を生成する（ｓ１）。次に制約ソルバ３に制約モデルデータ３１を渡し（ｓ２）、最小解探索を依頼して待機する（ｓ３）。探索終了後、分割エンジン１は制約ソルバ３の解探索の実行結果を取得し（ｓ４）、当該解探索の実行結果を基に分割成否データ２３を生成して作業データ蓄積部２に保持する（ｓ５）。そして、解が得られたか否か（ｓ６）により条件分岐を行い、Ｎｏの場合はそのまま終了する。一方、Ｙｅｓの場合は、まず、制約ソルバ３から制約充足解データ３２を取り出し（ｓ７）、次に制約充足解データ３２を基に分割結果データ２４を生成して作業データ蓄積部２に保持する（ｓ８）。
【００５４】
＜画像領域分割エンジンの内部動作＞
分割エンジン１の詳細な機能構成を図１８に示す。分割エンジン１は、前述した制約モデル生成部１１及び充足結果解釈部１２とともに、制約モデル生成部１１で生成された制約モデルデータを制約ソルバ３に渡し、制約ソルバ３から返却される解探索の実行結果及び／又は制約充足解データを受け取り、充足結果解釈部１２へ渡す制約ソルバ制御部１３を備えて構成されている。さらに、制約モデル生成部１１は、画像マッチング部１１１と、矩形間制約生成部１１２と、矩形内制約生成部１１３と、評価関数制約生成部１１４とからなり、また、充足結果解釈部１２は、分割成否情報生成部１２１と、分割結果データ生成部１２２とからなる。
【００５５】
分割エンジン１の詳細な内部の動作フローを図１９〜図２２に示す。
【００５６】
分割エンジン１は、外部から分割ルールデータ２１及び分割対象画像データ２２を入力として受け取る（ｓ１１）。
【００５７】
まず、分割対象画像データ２２に対し、分割ルールデータ２１に含まれる画像断片オブジェクト２１３についてテンプレートマッチング処理を実行し、画像断片の座標位置を計算し、当該画像断片と関連付けられた目標位置Ｘ1t，Ｘ2t，Ｙ1t，Ｙ2tとして記憶する。これは画像マッチング部１１１で行われる（ｓ１２）。
【００５８】
次に、分割ルールデータ２１を基に制約モデルデータ３１を以下の手順で生成する。
【００５９】
まず、制約モデルデータ３１のコンテナオブジェクトを生成する（ｓ１３）。以下ではこの制約モデルデータのコンテナオブジェクトを単に「モデルオブジェクト」と呼ぶ。
【００６０】
次に、矩形間制約生成部１１２を呼び出して以下の処理を行う（ｓ１４）（図２０）。
【００６１】
各分割矩形ｒ(n)に対応して、その四隅の座標位置Ｘ(2n+0)，Ｘ(2n+1)，Ｙ(2n+0)，Ｙ(2n+1)の制約変数オブジェクト３１１を生成し、前記モデルオブジェクトに登録する（ｓ３１）。そして各レイヤに対応して、それに属する分割矩形の全ての座標位置をＸ軸方向、Ｙ軸方向それぞれについて初期値でソートし（ｓ３２）、それらの順序が保存されるような不等号制約を与える制約条件オブジェクト３１２を生成し、モデルオブジェクトに登録する（ｓ３３，ｓ３４）。
【００６２】
Ｘ軸方向についていえば、あるレイヤＬに属する分割矩形ｒ(1)，ｒ(2)，…，ｒ(n)について、制約変数オブジェクト３１１の集合｛Ｘ(0)，Ｘ(1)，…，Ｘ(2n+1)｝が得られる。各要素の初期値Ｖをソートした数列Ｖ(f(0))，Ｖ(f(1))，…，Ｖ(f(2n+1))の順序が保存されるような不等号制約
Ｘ(f(0))＜Ｘ(f(1))＜…＜Ｘ(f(2n+1))
の制約条件オブジェクト３１２を生成する。ここで、Ｘ(i)の初期値はＶ(i)であり、ソート後のインデックスの順序が保存されるように、下記の疑似コードの要領で制約オブジェクトを生成すれば良い。
for(i＝0;i＜2n+1;i++)｛
makeconstraint "Ｘ(f(i))＜Ｘ(f(i+1))"
｝
但し、Ｖ(f(i))＝Ｖ(f(i+1))の場合は、上記擬似コードの処理の前に予め変数Ｘ(f(i+1))を不等号制約の生成対象から除外し、代わりにＸ(f(i))＝Ｘ(f(i+1))の制約条件オブジェクト３１２を生成するものとする。
【００６３】
なおこのとき、個々の分割矩形の内部での辺の位置関係についての条件Ｘ1＜Ｘ2，Ｙ1＜Ｙ2を満たすように、予め初期値が与えられることを保証すれば、辺の位置関係についての条件が制約条件として含まれることになる。初期値に対するこの保証は、ルールエディタにおける入力値チェックにより担保される。また、ここではＸ方向のみについて記載したが、同様の内容をＹ方向についても処理する（ｓ３５〜ｓ３７）。
【００６４】
次に、矩形内制約生成部１１３を呼び出して以下の処理を行う（ｓ１５）（図２１）。
【００６５】
各分割矩形内部での制約条件を生成する。制約モデルデータの生成は、
１．最大サイズのフラグが有効であれば、Ｘmax＞Ｘ2−Ｘ1を生成（ｓ４１，ｓ５１）
２．最小サイズのフラグが有効であれば、Ｘmin＜Ｘ2−Ｘ1を生成（ｓ４２，ｓ５２）
３．推奨サイズのフラグが有効であれば、Ｘpre＝Ｘ2−Ｘ1−Ｄxppを生成（ｓ４３，ｓ５３）
４．推奨位置のフラグが有効であれば、Ｘ1＝Ｘ1p−Ｄx1p，Ｘ2＝Ｘ2p−Ｄx2pを生成（ｓ４４，ｓ５４）
５．当該の分割矩形が画像断片と関連付けられている場合は、Ｘ1＝Ｘ1t，Ｘ2＝Ｘ2tを生成（ｓ４９，ｓ５９）
について行えば良い。
【００６６】
ここで、Ｄxpp，Ｄx1p，Ｄx2pは目的変数であり、これらは制約変数のリストＤlistを作成して追加しておき、制約モデル生成の最後に解全体の最適度を表す目的関数の定義に用いる。また、Ｘ1t，Ｘ2tは先に記憶した目的位置である。これらはテンプレートマッチングの結果、固定的に指定される位置として制約条件オブジェクトとして生成される。また、ここではＸ方向のみについて記載したが、同様の内容をＹ方向についても処理する（ｓ４５，ｓ５５），（ｓ４６，ｓ５６），（ｓ４７，ｓ５７），（ｓ４８，ｓ５８），（ｓ４９，ｓ５９）。
【００６７】
次に、評価関数制約生成部１１４を呼び出して以下の処理を行う（ｓ１６）（図２２）。
【００６８】
前述した制約変数のリストＤlist内の各要素Ｄx1p，Ｄx2p，Ｄxpp，Ｄy1p，Ｄy2p，Ｄyppについてそれぞれ、重みＷdx1，Ｗdx2，Ｗdxpp，Ｗdy1，Ｗdy2，Ｗdypp付きの新たな制約変数を作成し、制約変数のリストＤlist2に追加して（ｓ６１〜ｓ６６，ｓ７１〜ｓ７６）、これらの総和で表される、解全体の最適度を表す目的関数の評価値としての制約変数（制約条件オブジェクト）Ｄallを生成する（ｓ７７）。
Ｄall＝Ｗdx1Σ｜Ｄx1p｜＋Ｗdx2Σ｜Ｄx2p｜＋ＷdxppΣ｜Ｄxpp｜
＋Ｗdy1Σ｜Ｄy1p｜＋Ｗdy2Σ｜Ｄy2p｜＋ＷdyppΣ｜Ｄypp｜
なお、上記において重みＷdx1とＷdx2，Ｗdy1とＷdy2は通常、同じ値である。また、Ｗdx1とＷdy1は、ＸＹ方向について推奨位置の強制力が同じであれば同じ値とすれば良い。さらに、推奨サイズと推奨位置の強制力の比が同じであれば同じ値とすれば良い。以上は評価関数制約生成部１１４で行われる。
【００６９】
これらの各処理部は、制約モデル生成部１１として統括されている。
【００７０】
さらに、分割エンジン１は、制約モデル生成部１１で生成した制約モデルデータ３１を制約ソルバ３に入力し、制約ソルバ３を起動するが、このとき、Ｄallが最小となる解を探索するようオプション指定を行う（ｓ１７，ｓ１８）。探索が終了し、制約ソルバ３から探索で解が得られたかどうかの成否（実行結果）及び当該の充足解データ３２を取り出したら、作業データ蓄積部２に設定するためのデータを生成する（ｓ１９）。以上の全体的処理の流れは、制約ソルバ制御部１３で行われる。
【００７１】
分割エンジン１は、分割成否情報生成部１２１を呼び出し、解が得られたかどうかの成否から分割成否データ２３を生成し、作業データ蓄積部２に登録する（ｓ２０）。そして、分割に成功した場合は、分割結果データ生成部１２２を呼び出し、当該の解（制約を充足するよう割り当てられた各変数の値）を基に、分割矩形データ（分割結果データ）２４を生成し、作業データ蓄積部２に登録する（ｓ２１）。
【００７２】
これらの各処理部は、充足結果解釈部１２として統括されている。
【００７３】
＜ルール記述と実行方式＞
〈説明上の用語定義と概念の説明〉
上記＜画像領域分割エンジンの使用形態＞、＜「画像領域分割エンジンの内部動作＞では先願を具体的に実行する方法を説明したが、先願の目的である画像領域の分割がこの方法の上で不足なく十分に達成されることを次に説明する。ポイントは、幾何制約条件をシンプルな種類に限定し、制約モデルデータ上の図形要素を単一に限定することによって、ユーザが求める、多様な画像領域分割の方法を制限することなく、同時に制約充足処理の負荷を効果的に低減する点である。
【００７４】
まず、画像領域分割の方法をユーザが指定する場合の考え方の基本要素となる、分割矩形の概念を定義する。図２３は矩形に関する呼称の定義を示すもので、同図（ａ）に示すように分割矩形の各頂点のＸ，Ｙ座標を
（Ｘ1，Ｙ1）左上，（Ｘ1，Ｙ2）左下，
（Ｘ2，Ｙ2）右下，（Ｘ2，Ｙ1）右上
のように表す。
【００７５】
また、同図（ｂ）に示すように矩形の四辺を左辺、右辺、上辺、下辺と呼び、左辺と右辺のことを垂直辺、上辺と下辺のことを水平辺と呼ぶこととする。垂直辺の両端の頂点は共通のＸ座標値を有する。同様に水平辺の両端の頂点は共通のＹ座標値を有する。即ち、同図（ｃ）に示すように
Ｘ1：左辺のＸ座標上の位置
Ｘ2：右辺のＸ座標上の位置
Ｙ1：上辺のＹ座標上の位置
Ｙ2：下辺のＹ座標上の位置
ということがいえる。
【００７６】
分割矩形は初期状態における相互の位置関係について、以下の条件を満足する範囲で座標値を移動できると考え（矩形間制約生成部１１２で扱われる）、後述するその他の制約条件を考慮しながら（矩形内制約生成部１１３で扱われる）、最も評価値の高い（即ちＤallが小さい）位置関係を計算し（評価関数制約生成部１１４で扱われる）、これを画像領域分割の結果として出力する。
【００７７】
まず、矩形間制約生成部１１２では、分割矩形の相互の座標値によって以下の条件を満足するものとする。
【００７８】
分割矩形の左辺と右辺は初期状態の順序関係から入れ替わらないものとする。同様に上辺と下辺は入れ替わらないものとする。即ち、１つの矩形において相対する辺の間には、
Ｘ1＜Ｘ2，Ｙ1＜Ｙ2
の関係が常に成り立つものとする。
【００７９】
同じレイヤに所属する分割矩形間には以下の関係がある。
【００８０】
矩形Ａの垂直辺と矩形Ｂの垂直辺は初期状態の順序関係から入れ替わらないものとする。同様に矩形Ａの水平辺と矩形Ｂの水平辺は入れ替わらないものとする。即ち、矩形Ａの垂直辺の座標位置をＸａ、矩形Ｂの垂直辺の座標位置をＸｂとすると、
Ｘａ＜Ｘｂ
の関係が常に成り立つものとする。
【００８１】
なおここで、垂直辺とは、Ｘa1，Ｘa2，Ｘb1，Ｘb2の４辺の全てをさし、初期状態の順序関係が例えば、Ｘa1＜Ｘb1＜Ｘb2＜Ｘa2の場合は、領域分割結果においてもこの関係を維持するように位置を調整する。２矩形間の位置関係としては、外にＸa1＜Ｘb1＜Ｘa2＜Ｘb2，Ｘa1＜Ｘa2＜Ｘb1＜Ｘb2，Ｘb1＜Ｘa1＜Ｘa2＜Ｘb2，Ｘb1＜Ｘa1＜Ｘb2＜Ｘa2，Ｘb1＜Ｘb2＜Ｘa1＜Ｘa2があり、全部で６通りとなる。
【００８２】
任意数の矩形間の位置制約は、上記と同様の考え方で位置を調整する。実際の分割矩形をユーザが意図したように位置調整させるには、単純に上記を適用するのでは制約が強すぎ、単純な領域パターンしか扱うことができない。そこで、上記をユーザが指定した矩形グループに対して適用するようにしたのがレイヤの考え方である。各矩形は任意数のレイヤに所属できるようにすることで、複雑な相互位置制約を定義することができる。
【００８３】
以上は、後述の〈位置前後関係制約〉に対応する。
【００８４】
一方、矩形内制約生成部１１３では、
１．矩形のサイズの最大最小．〈サイズ制限制約〉に対応
２．矩形のサイズの推奨値．〈サイズ推奨制約〉に対応
３．矩形の位置の推奨値（初期位置からの移動量）．〈位置推奨制約〉に対応
４．矩形の位置の固定値
の調整要素が扱われる。
【００８５】
これら、矩形間制約と矩形内制約は、一見アドホックな制約を選択したように見えるが、分割矩形の考え方を制約モデルとして表現する上で必要な条件を網羅している。これは次のように考えると明らかである。矩形については、位置とサイズの２つの観点がある。各観点について、固定値指定、最大最小指定、推奨値指定の３種類のカテゴリが考えられ、以下に示すように漏れなく対応している。
【００８６】
位置―固定値指定：
「４．矩形の位置の固定値」
位置―最大最小指定：
矩形同士の位置関係指定により同等の指定が可能
位置―推奨値指定：
「３．矩形の位置の推奨値」
サイズ―固定値指定：
「１．矩形のサイズの最大最小」で最大＝最小の指定が可能
サイズ―最大最小指定：
「１．矩形のサイズの最大最小」
サイズ―推奨値指定：
「２．矩形のサイズの推奨値」
また、各観点、各指定カテゴリには、有効・無効の切り替えの概念があることで、ユーザの指定方法の自由度が高くなる。それぞれについては、以下に示すように漏れなく対応している。
【００８７】
位置―固定値指定の有効無効：
分割矩形と画像断片の対応の有無により指定が可能
位置―最大最小指定の有効無効：
矩形同士の位置関係とレイヤの帰属関係により同等の指定が可能
位置―推奨値指定の有効無効：
位置推奨値フラグにより指定が可能
サイズ―固定値指定の有効無効：
サイズ―最大最小を最大＝最小とするか否かで指定が可能
サイズ―最大最小指定の有効無効：
サイズ最大最小フラグにより指定が可能
サイズ―推奨値指定の有効無効：
サイズ推奨値フラグにより指定が可能
幾何制約で一般的に指定可能な方法については、上記を組み合わせて代用可能である。事例を以下に示す。
【００８８】
位置の固定値を絶対座標で指定する：ウィンドウ４隅の画像断片を作成し、これと外接する矩形を定義する。左上を原点とするのであれば、この左上隅に内接する別の矩形を作成し、サイズの固定指定をすれば、右下隅の位置が当該の指定に相当する。なお、これらが所属する新たなレイヤを作成し、この中で矩形間制約が働くようにすれば、他の矩形の制約に影響を及ぼすことはない。一般的な幾何制約では絶対座標系や相対座標系を導入し、専用の制約指定を行うが、その必要がない。
【００８９】
２矩形間の横方向の距離の推奨値を指定する：矩形Ａ，Ｂの互いに近い側の垂直辺に接する別の矩形Ｃを作成し、Ｘ方向のサイズの推奨指定をすれば、矩形Ａ，Ｂに働く制約が当該の指定に相当する。なお、矩形Ａ，Ｂ，Ｃが所属する新たなレイヤを作成し、この中で矩形間制約が働くようにすれば、Ａ，Ｂが関係する他の矩形との制約に影響を及ぼすことはない。一般的な幾何制約では寸法や距離の要素を導入し、この要素のためのルールデータ形式の拡張やルール入力手段の提供を行うが、その必要がない。
【００９０】
以下では、上記の考え方を基に、具体的な分割ルールデータの定義形式（データ定義）、分割ルールデータの定義方法（作成・編集手段）を説明する。
【００９１】
＜画像領域分割ルールデータの概要＞
分割ルールデータ２１は、分割矩形情報（オブジェクト）２１１、分割レイヤ情報（オブジェクト）２１２及び画像断片情報（オブジェクト）２１３を要素とする。
【００９２】
分割ルールデータ２１上で中心的役割をはたすのは、分割矩形情報２１１である。分割矩形情報２１１は、
・分割矩形は外形（四隅の座標位置）について初期座標を指定する、
・分割矩形は外形（四隅の座標位置）について推奨座標を指定できる、
・各推奨座標については、有効フラグが設けられ有効無効を指定する、
・分割矩形はサイズ（縦と横の寸法値）について長さの最大値、最小値、推奨値を指定できる、
・各長さの最大値、最小値、推奨値については、それぞれ有効フラグが設けられ有効無効を指定する、
という属性値を有し、ユーザが指定する。
【００９３】
また、分割ルールデータ２１の要素の種類間は、
・分割矩形情報は１つ以上の分割レイヤ情報と対応づけられる、
・分割矩形情報は０又は１つの画像断片情報と対応づけられる、
という関係を有し、ユーザが指定する。
【００９４】
≪本発明≫
以下、本発明の実施の形態について、主として先願との相違部分について説明する。なお、先願と同一構成部分は同一符号をもって表すものとする。
【００９５】
図２６は本発明の画像領域分割エンジン（以下、単に「分割エンジン」）を含む本発明の画像領域分割装置の実施の形態の機能構成を示すもので、本発明の画像領域分割装置は、分割エンジン１ｂとともに、作業データ蓄積部２、制約ソルバ３及び上位機能制御部４を含んで構成される。
【００９６】
分割エンジン１ｂは、作業データ蓄積部２に蓄積された分割ルールデータ２１及び分割対象画像データ２２を基に、制約ソルバ３に入力する制約モデルデータ３１を生成する制約モデル生成部機能（制約モデル生成部）１１ｂと、制約ソルバ３から返却された解探索の実行結果及び／又は制約充足解データ３２を基に、分割成否データ２３及び／又は分割結果データ２４を生成する充足結果解釈機能（充足結果解釈部）１２とを備えて構成されている。
【００９７】
図２７は本発明の分割エンジン１ｂの詳細な機能構成を示すもので、分割エンジン１ｂは、前述した制約モデル生成部１１ｂ及び充足結果解釈部１２とともに、制約モデル生成部１１ｂで生成された制約モデルデータを制約ソルバ３に渡し、制約ソルバ３から返却される解探索の実行結果及び／又は制約充足解データを受け取り、充足結果解釈部１２へ渡す制約ソルバ制御部１３ｂを備えて構成されている。
【００９８】
さらに、制約モデル生成部１１ｂは、画像マッチング部１１１、矩形間制約生成部１１２、矩形内制約生成部１１３及び評価関数制約生成部１１４とともに、画像マッチ位置候補生成部１１５、マッチ位置選択制約生成部１１６、テンプレート画像選択制約生成部１１７及び可変個候補選択制約生成部１１８を具備している。
【００９９】
画像マッチ位置候補生成部１１５は、テンプレート画像をもとに分割対象画像上でのマッチング位置を全て列挙し、画像マッチ位置オブジェクトを生成する。
【０１００】
マッチ位置選択制約生成部１１６は、前記画像マッチ位置オブジェクトが保有する座標値により候補座標値配列を生成し、その配列上のどのインデックスの値を選択するかを、マッチ位置候補選択変数により指定させる候補選択制約条件を与え、制約モデルデータ上の当該部分と同じ構造の部分が複数存在する場合に、それらのマッチ位置候補選択変数の集合に非同値制約条件を与え、これらを制約モデルデータとして追加する。
【０１０１】
前記画像マッチ位置候補生成部１１５及びマッチ位置選択制約生成部１１６は、複数の画像マッチ位置の候補から適宜選択を行いながら制約モデルデータを解くことを目的として設けられたもので、テンプレート画像の対象画像上でのマッチング位置が複数存在する場合に、それら位置を全て列挙して得られる画像マッチ位置候補のいずれを選択するかと、当該テンプレート画像の座標値がいずれになるか、が整合するよう関係を拘束する制約条件を与えるとともに、制約モデルデータ上の当該部分と同じ構造の部分が複数存在する場合に、それらのマッチ位置候補の選択を互いに重複して行わないよう関係を拘束する制約条件を与えることにより、当該制約モデルデータを制約ソルバに解かせ、制約モデルデータを候補からの選択内容に応じて逐一生成する必要なく、制約モデルデータそのものの中で同選択に関わる制約を同時に扱うことにより、ソルバの処理時間の短縮やルール作成稼働の削減を実現し、適用対象画像やルール記述の幅を広げて最適解探索のスコア算定の基準・方法を簡単かつ安全に修正可能とする効果を有するものである。
【０１０２】
テンプレート画像選択制約生成部１１７は、分割ルールデータ内のテンプレート画像の数と同じ要素数のテンプレート画像ＩＤ配列を生成し、テンプレート画像ごとに割り当てられたユニークなＩＤ値を格納し、候補座標値配列と同じ要素数の算出元テンプレート画像配列を生成し、当該算出元テンプレート画像配列の要素ごとに候補座標値配列の同じインデックスの要素に格納された座標値を算出するもととなったテンプレート画像ＩＤ値を格納し、既存の矩形位置変数に関連付けて、当該位置の算出元として採用するテンプレート画像ＩＤ値を保持する対応テンプレート画像ＩＤ変数を生成し、当該位置の矩形がどのテンプレート画像を選択しているかを表すテンプレート画像候補選択変数を生成し、前記対応テンプレート画像ＩＤ変数との間に選択制約条件を与えるととともに、制約モデルデータ上の当該部分と同じ構造の部分が複数存在する場合に、それらのテンプレート画像候補選択変数の集合に非同値制約条件を与え、これらを制約モデルデータとして追加する。
【０１０３】
前記テンプレート画像選択制約生成部１１７は、複数のテンプレート画像の候補から適宜選択を行いながら制約モデルデータを解くことを目的として設けられたもので、画像断片オブジェクトに対して、画像領域分割ルールデータ内のテンプレート画像のいずれを割り当てるかと、当該テンプレート画像のマッチ位置候補及び座標値がいずれになるかが整合するよう関係を拘束する制約条件を与えるとともに、制約モデル上の当該部分と同じ構造の部分が複数存在する場合に、それらのテンプレート画像候補の選択を互いに重複して行わないよう関係を拘束する制約条件を与えることにより、当該制約モデルデータを制約ソルバに解かせ、制約モデルデータを候補からの選択内容に応じて逐一生成する必要なく、制約モデルデータそのものの中で同選択に関わる制約を同時に扱うことにより、ソルバの処理時間の短縮やルール作成稼働の削減を実現し、適用対象画像やルール記述の幅を広げて最適解探索のスコア算定の基準・方法を簡単かつ安全に修正可能とする効果を有するものである。
【０１０４】
可変個候補選択制約生成部１１８は、所定の個数の制約モデルパーツを生成し、これら制約モデルパーツの有効無効を制御するパーツ選択制御変数を生成し、制約モデルパーツごとにその内部の制約条件の集合を、パーツ選択制御変数の値が所定の固定数値以下であるかどうかの判定条件が成立するときに有効となるようメタ制約条件を与え、これらを制約モデルデータとして追加する。
【０１０５】
前記可変個候補選択制約生成部１１８は、複数のサブテンプレートの候補から適宜選択を行いながら制約モデルデータを解くことを目的として設けられたもので、画像領域分割ルールの一部が、画像マッチング箇所を含む同種の構造が可変個数現れる形になっている場合に、当該構造の個数が実際にいくつ存在するかを含め制約ソルバで計算可能とする目的で、所定の個数の制約モデルパーツを生成し、それら各々の内部の制約条件の集合に対して有効、無効を切り替え可能となるようメタ制約条件を与え、これらを制約モデルデータとして追加することにより、当該制約モデルデータを制約ソルバに解かせ、制約モデルデータを候補からの選択内容に応じて逐一生成する必要なく、制約モデルデータそのものの中で同選択に関わる制約を同時に扱うことにより、ソルバの処理時間の短縮やルール作成稼働の削減を実現し、適用対象画像やルール記述の幅を広げて最適解探索のスコア算定の基準・方法を簡単かつ安全に修正可能とする効果を有するものである。
【０１０６】
図２８は分割エンジン１ｂを主体とした本画像領域分割装置の動作フローを示す。
【０１０７】
分割エンジン１ｂは上位機能制御部４から呼び出されると、まず、その制約モデル生成部１１ｂにおいて、作業データ蓄積部２の分割ルールデータ２１及び画像データ２２を基に制約モデルデータ３１を生成する。この際、画像マッチング部１１１、矩形間制約生成部１１２、矩形内制約生成部１１３及び評価関数制約生成部１１４による制約モデルデータ３１の生成に加え、前述した画像マッチ位置候補生成部１１５及びマッチ位置選択制約生成部１１６による複数の画像マッチ位置の選択組み合わせを可能とする制約モデルデータ３１、及び／又は前述したテンプレート画像選択制約生成部１１７による複数のテンプレート画像の選択組み合わせを可能とする制約モデルデータ３１、及び／又は前述した可変個候補選択制約生成部１１８によるサブテンプレートの定義及び選択組み合わせを可能とする制約モデルデータ３１の生成を行う（ｓ１０１）。
【０１０８】
次に、分割エンジン１ｂは制約ソルバ制御部１３ｂにより、制約ソルバ３に制約モデルデータ３１を渡し（ｓ２）、最小解探索を依頼して待機する（ｓ３）。探索終了後、分割エンジン１ｂは制約ソルバ制御部１３ｂにより、制約ソルバ３の解探索の実行結果を取得し（ｓ４）、充足結果解釈部１２により、当該解探索の実行結果を基に分割成否データ２３を生成して作業データ蓄積部２に保持する（ｓ５）。そして、解が得られたか否か（ｓ６）により条件分岐を行い、Ｎｏの場合はそのまま終了する。一方、Ｙｅｓの場合は、まず、制約ソルバ制御部１３ｂにより、制約ソルバ３から制約充足解データ３２を取り出す（ｓ７）。
【０１０９】
ここで、前述した可変個候補選択制約生成部１１８によるサブテンプレートの定義及び選択組み合わせを可能とする制約モデルデータ３１を生成した場合において、得られた制約充足解データにおける制約モデルパーツの有効な個数が前記個数と同じ場合（ｓ１０２：Ｙｅｓ）は、制約モデル生成部１１ｂにより、さらに同じ制約モデルパーツを所定個数生成して前記制約モデルデータに追加し（ｓ１０３）、ｓ２以降の処理を繰り返す。
【０１１０】
また、得られた制約充足解データにおいて制約モデルパーツが有効な個数が予め制約モデルデータに組み込まれた制約モデルパーツの個数より小さい場合（ｓ１０２：Ｎｏ）は、充足結果解釈部１２により、制約充足解データ３２を基に分割結果データ２４を生成して作業データ蓄積部２に保持する（ｓ８）。
【０１１１】
さらにまた、前述した画像マッチ位置候補生成部１１５及びマッチ位置選択制約生成部１１６による複数の画像マッチ位置の選択組み合わせを可能とする制約モデルデータ３１を生成した場合、又はテンプレート画像選択制約生成部１１７による複数のテンプレート画像の選択組み合わせを可能とする制約モデルデータ３１を生成した場合において、上位機能から自動的に発行されたのを契機とし、あるいはユーザから上位機能を通して明示的に指示したのを契機とする、他の制約充足解データを得ることを意図した継続の探索処理の命令がなければ（ｓ１０４：Ｎｏ）、そのまま終了し、当該命令があれば（ｓ１０４：Ｙｅｓ）、制約モデル生成部１１ｂにより、直前の解の評価値よりも大きい解を許容し、小さい解を禁止する新たな追加した制約モデルデータを生成し（ｓ１０５）、ｓ２以降の処理を繰り返す。
【０１１２】
≪実施例≫
＜画像マッチ位置の選択組み合わせを可能とする＞
１番目の課題（マッチ位置の複数の候補を扱えない）に対しては、画像マッチ位置候補生成部１１５及びマッチ位置選択制約生成部１１６において、図２９に示す記述方法により"nth"制約を制約モデルデータに追加することで対処できる。これは具体的には制約ソルバchocoの場合の制約条件の与え方であるが、他のソルバについても同様の機能が提供されているか、又はこれに相当する制約条件を他の制約条件から作り出すことができる。
【０１１３】
図３０に示すように、矩形領域の四隅の位置座標を表す制約変数（矩形位置変数）に対し、その値候補のベクトル変数（候補座標値配列）と、その中からどれを候補選択するかのインデックスを表す制約変数（マッチ位置候補選択変数）を与える。これにより、画像マッチ位置の複数の候補から１つを選択するという制約モデルデータを構成できる。
【０１１４】
図２及び図６の画像事例で１つのボタンの領域を特定するには、上記構成をソルバに入力することで、目的を達成できる。さらに他のボタン（例えば、Button2について）も分割パターンを定義し領域を特定しようとすると、２つの矩形位置を２つの画像マッチ位置の複数候補から選択する必要がある。これは、図３０の構成を各ボタンごとに生成し、さらに２つの候補選択変数が同じ値をとらないように、"neq"（等しくない）制約をモデルに追加することで、目的を達成できる。
【０１１５】
図７及び図８のように、特定したい矩形領域が複数の場合も、これと同様にｎ個のマッチ候補選択変数が同じ値をとらないよう、図３１に示すように、"allDifferent"（全て異なる）制約を制約モデルデータに追加することで、目的を達成できる。
【０１１６】
＜分割結果として最適性の高い順での解出力を可能とする＞
スコア算定を伴う最適解探索については、先願において説明されている。これによって求められる解はスコアを最小化する最適解１つだけである。ユーザとの対話的処理により、準最適解を順に列挙する機能を制約ソルバで扱うために、ソルバ実装に依存したＡＰＩを利用するのでは、特定のライブラリに依存した機能となってしまう。またユーザが望む解を得るよう制御するためには、当該機能が提供する範囲の制御しかできない。
【０１１７】
そこで、最初に得られた最適解において、制約変数とそれが保持している値の組の集合の中で、ユーザが望む解に関係ない値を、禁止制約として新たに制約モデルデータに追加する。この制約モデルデータのもとで再度、最適解を最初からソルバで計算することで、上記目的を実現することができる（図２８中のｓ１０４〜ｓ１０５の処理）。
【０１１８】
禁止制約とは、単に指定した制約変数がある値をとった場合、制約が充足されないように「≠」の制約条件を追加することである。これは１つ１つの制約変数に個別に追加するのではなく、当該の最適解を構成する制約変数の所定の部分集合が、当該最適解での値の組み合わせを取った場合のみを禁止するために「≠」を「ＡＮＤ」で結合した制約条件を１つ追加する点に注意する必要がある。
【０１１９】
本発明においては、幾何的な配置をユーザの希望に近いものにするための、サイズや位置座標に関するスコア算定に関わる制約変数は、禁止制約の対象とはしない。画像マッチ位置の複数候補からいずれを選択するかを表す制約変数、テンプレート画像の複数候補選択の制約変数、サブテンプレートの複数候補選択の制約変数、を対象とする。これにより、解として出力される領域分割パターンの矩形の数やそれらの間の関係構成について、制御を行う。なお、前提として、矩形の数やそれらの間の関係構成についても、幾何的配置と同じくスコア算定のロジックが指定され、それらが制約モデルに含まれていることに注意する必要がある。
【０１２０】
＜テンプレート画像の選択組み合わせを可能とする＞
３番目の課題（同種ルールをまとめて定義）に対しては、対応すべき画像が図１１の画像事例だけであれば、単にルールエディタの機能を拡張して、１つのルールからバリエーションを生成することが考えられる。すなわち、四隅のテンプレート画像でメタルールを定義し、それを２７種類のテンプレート画像との組み合わせによって２７個のルールインスタンスを自動生成する方法である。しかしこの方法は、バリエーションの数が可変個数の場合に対応できない、という課題を有する。
【０１２１】
上記方法とは別に、候補選択変数を使った構成を２つ並列で形成することにより、テンプレート画像の選択組み合わせを行った結果に、前記の画像マッチ位置の選択組み合わせを行う制約充足モデルを作成する。具体的には、テンプレート画像選択制約生成部１１７において、図３２に示す構成の制約モデルを作成する。これは複数のテンプレート画像から１つを選択する場合であるが、図３０に対する図３１の拡張と同様に、拡張を行うことにより、複数を選択する場合を構成することができる。
【０１２２】
＜サブテンプレートの定義と選択組み合わせを可能とする＞
４番目の課題（マッチ箇所が可変個数）に対しては、可変個候補選択制約生成部１１８において、複数個現れるテンプレートルールを、サブテンプレート（制約モデルパーツ）を十分な一定個数含むテンプレートを構成し、その中でサブテンプレートの有効無効を制約変数（パーツ選択制御変数）で制御することにより扱うことができる。ここではまず、マッチ箇所が８個以下の場合を想定して説明する。
【０１２３】
図３３に示す構成により、最大８個の候補選択を行うことができる。８個のサブテンプレートは、マッチ位置候補選択変数、矩形位置変数、テンプレート画像候補選択変数の間に働く制約条件集合ＣＭ１〜８としてここでは記載されている。ＣＭ１〜８はそれぞれ、implies制約で参照されている。implies制約では、各サブモデルに有効無効を制御するeffect n変数との比較により、１〜８個の範囲で制約条件集合をモデル内で働かせるかどうかを変化させられる。例えば、effect nが２の場合、ＣＭ１とＣＭ２だけが有効となり、他は解に関係なくなるため、サブテンプレート２つを用いたマッチングの解が得られる。Effect nの値自体をソルバに解かせることにより、全ての解を列挙することができる。
【０１２４】
上記においては、一般に候補選択組み合わせの探索空間が非常に大きい。全体として制約の効きが強いモデルでは、ソルバで解を得るのに膨大な時間を要し、また全体として制約の効きが弱いモデルでは、多くの解を出力することとなり、ユーザの利便性・実用性が損なわれる。そこで、制約として充足するか否かの充足条件だけではなく、所定の算定基準・算定方法によるスコアの大きいものから順に、解探索による出力を行う方法が重要となる。
【０１２５】
これらは、先願と同じスコア算定に、さらに複数候補選択に関するスコア算定を追加併用したものである。スコア算定の基準・方法を調整することにより、ソルバ処理の外部処理として、制約モデルを何度も新規に選択組み合わせを変えながら生成し、ソルバによる解出力を試みる方法よりも、短時間での探索処理が可能であり、また望みの解を得るための調整も柔軟かつ安全に行うことができる、という特徴がある。
【０１２６】
なお、本発明の装置はコンピュータとプログラムによっても実現でき、当該プログラムは記録媒体に記録して提供することも、ネットワークを通じて提供することも可能である。
【符号の説明】
【０１２７】
１ｂ：画像領域分割エンジン（分割エンジン）、２：作業データ蓄積部（画像領域分割ルールデータベース）、３：制約ソルバ、４：上位機能制御部、
１１ｂ：制約モデル生成部、１１１：画像マッチング部、１１２：矩形間制約生成部、１１３：矩形内制約生成部、１１４：評価関数制約生成部、１１５：画像マッチ位置候補生成部、１１６：マッチ位置選択制約生成部、１１７：テンプレート画像選択制約生成部、１１８：可変個候補選択制約生成部、
１２：充足結果解釈部、１２１：分割成否情報生成部、１２２：分割結果データ生成部、
１３ｂ：制約ソルバ制御部、
２１：分割ルールデータ、２２：分割対象画像データ、２３：分割成否データ、２４：分割結果データ、
３１：制約モデルデータ、３２：制約充足解データ。
【先行技術文献】
【非特許文献】
【０１２８】
【非特許文献１】行天  啓二、馬場口  登「制約充足型文字領域抽出の基礎検討」、電子情報通信学会技術報告、第９２巻、第４３４号、社団法人電子情報通信学会、１９９３年、第９〜１６頁
【図１】
0005950309.tif 000002
【図２】
0005950309.tif 000003
【図３】
0005950309.tif 000004
【図４】
0005950309.tif 000005
【図５】
0005950309.tif 000006
【図６】
0005950309.tif 000007
【図７】
0005950309.tif 000008
【図８】
0005950309.tif 000009
【図９】
0005950309.tif 000010
【図１０】
0005950309.tif 000011
【図１１】
0005950309.tif 000012
【図１２】
0005950309.tif 000013
【図１３】
0005950309.tif 000014
【図１４】
0005950309.tif 000015
【図１５】
0005950309.tif 000016
【図１６】
0005950309.tif 000017
【図１７】
0005950309.tif 000018
【図１８】
0005950309.tif 000019
【図１９】
0005950309.tif 000020
【図２０】
0005950309.tif 000021
【図２１】
0005950309.tif 000022
【図２２】
0005950309.tif 000023
【図２３】
0005950309.tif 000024
【図２４】
0005950309.tif 000025
【図２５】
0005950309.tif 000026
【図２６】
0005950309.tif 000027
【図２７】
0005950309.tif 000028
【図２８】
0005950309.tif 000029
【図２９】
0005950309.tif 000030
【図３０】
0005950309.tif 000031
【図３１】
0005950309.tif 000032
【図３２】
0005950309.tif 000033
【図３３】
0005950309.tif 000034