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