Hypotheses and trees of hypotheses
仮説と検索の最適化
FlexiLayout のマッチングでは分岐する仮説ツリーが構築されます。幅優先探索 と Number of surviving hypotheses の設定により、マッチングを高速に保つ方法を学びます。
プログラムが画像に対して FlexiLayout のマッチングを行うと、FlexiLayout 内の要素に対応する画像上のオブジェクトを見つけようとします。次にプログラムは、各オブジェクトがその要素にどの程度適合しているかを評価します。評価値は 0 から 1 までの数値です。品質が 1 の場合は、検出されたオブジェクトが 100% 一致していることを意味します。品質が 0 でない場合、FlexiLayout のマッチングによってブロックの Region が作成されます。
プログラムは、FlexiLayout ツリー内の並び順に従って、上から下へ順に要素を探します。各要素について、プログラムは検索領域内で一致する複数のオブジェクト (またはオブジェクトの集合) を見つけることがあります。プログラムは検索領域内の各オブジェクトに対して仮説を立て、その品質を評価します。適合度が高いほど、仮説の品質も高くなります。
検出されたオブジェクトの位置によって、FlexiLayout ツリー内でその下にあるオブジェクトの位置が決まります。プログラムは、現在の要素に対する各仮説を出発点として使用し、現在の要素の下にある後続の要素を探します。こうして要素の仮説は分岐していき、要素ツリーよりもはるかに多くの分岐を含む仮説ツリーが生成されます。
複数の要素が 1 つの Group 要素にまとめられている場合、グループ全体が 1 つの要素として扱われ、その要素に対して複数の仮説が作成されます。Group 要素の品質は、構成要素の仮説を掛け合わせて計算されます。FlexiLayout 全体も、すべての要素の仮説の品質を掛け合わせることで品質を計算できる Group 要素と見なすことができます。
FlexiLayout を画像に対してマッチングする際、プログラムは最良の完全な仮説分岐を見つける必要があります。分岐は、最上位の要素から最下位の要素まで、すべての要素を含んでいれば完全です。一般的な方法としては、すべての要素について考えられる仮説の組み合わせをすべて検討し、可能な完全分岐の集合全体を構築したうえで、最も品質の高い分岐を選択することになります。しかし、これでは時間がかかりすぎるため、現実的ではありません。さらに、要素数がかなり多く、検索領域も概略的にしか定義されていない場合は、組合せ爆発が発生し、仮説の数が制御不能なほど増大するおそれがあります。
プログラムは、仮説の数を最小限に抑えるために、検索を最適化する複数のメソッドを使用します。
FlexiLayout の各要素には、Number of surviving hypotheses という重要なパラメーターがあります。ユーザーはこのパラメーターを使って、後続の要素を検索するときにプログラムが使用する仮説の数を制限できます。既定では、このパラメーターは単純要素で 5、Group 要素で 1 に設定されています。つまり、プログラムがある要素について 15 個の仮説を見つけた場合、最良の 5 個を選択し、残り 10 個の仮説チェーンは未完成のままになります。一般に、Group 要素は単純要素よりも高い精度で検出されます。そのため、Group 要素では、最良の仮説がそのまま正解であることが通常です。
多くの場合、プログラムには複数の未完成の仮説チェーンがあり、その結果、検索方向の候補も複数存在します。プログラムは、古典的な「幅優先探索」アルゴリズムを使って最良の仮説を探します。このアルゴリズムでは、長さに関係なく、その時点で品質が最も高いチェーンを常に優先して完成させようとします。
30 個の要素を記述する FlexiLayout があり、そこから 2 つの仮説チェーンが生成されたとします。1 つは 29 要素から成り、推定品質が 0.89 のチェーン、もう 1 つは 2 要素から成り、推定品質が 0.92 のチェーンです。プログラムは、品質の点で優れている短い方のチェーンについて、そのすべての拡張の品質が最初のチェーンより低くなるまで完成を試みます。
Group 要素の場合、プログラムは、いわゆる品質最適化を使用します。プログラムが特定の Group 要素について理想的な完全な仮説チェーン (つまり、そのチェーンの品質が 1) を見つけると、他のすべての候補は無視されます。
各要素の仮説の総数は 10,000 に制限されています。
仮説の生成と評価の仕組み