仮説と検索の最適化
FlexiLayoutと画像が合致すると、FlexiLayoutの要素に対応する画像のオブジェクトが検索されます。次に、特定のオブジェクトがその要素とどれぐらい合致するかが推定されます。推定は0～1の数字です。1の品質は、検出されたオブジェクトが100%合致する、ということです。品質が0でない場合、FlexiLayoutが合致するとブロックの区域が作成されます。
FlexiLayoutツリーで上から下に順番に要素が検索されます。各要素で、検索領域に複数の合致オブジェクト(またはオブジェクトのセット)が見つかることがあります。検索領域の各オブジェクトに対する仮説が立ち、その質が推定されます。合致が良好であるほど、仮説の質が高くなります。
検出されたオブジェクトの場所によって、FlexiLayoutツリーのオブジェクトの位置が決まります。現在の要素の各仮説が開始点として用いられ、現在の要素の下に位置する後続の要素が検索されます。従って、要素の仮説が枝わかれし、結果として、要素ツリーよりも多くの岐のある仮説ツリーになります。
複数の要素が1つのグループ要素に結合されている場合、グループ全体は複数の仮説の立つ1つの要素と見なされます。グループ要素の品質は、構成要素の仮説を乗算して算出されます。FlexiLayout全体は、すべての要素の仮説の品質を乗算して品質を算出可能なグループ要素と見なされることもあります。
FlexiLayoutを画像と合致させる場合、最善かつ完全な仮説枝が検索されなければいけません。枝に上の要素から下の要素までのすべての要素が含まれていると、枝は完全になります。包括的な解決策とすれば、完全な枝のセットを構築し、最も高い品質の枝を選択して、すべての要素に対する可能なすべての仮説の組み合せを考慮することでしょう。ですが、時間がかかりすぎるので、実用的ではありません。また、要素の数が過多でその検索領域がおおよその場合、組み合せ爆発が起こり、仮説の数が制御不能な増加をするかもしれません。
仮説の数を最小限に維持するために、検索を最適化するいくつかの方法が使用されます。
検索最適化
FlexiLayoutの各要素には重要なパラメータ生存仮説数があります。このパラメータを使用して、後続の要素の検索時に使用される仮説の数を制限することができます。デフォルトでは、このパラメータは単純要素で5、グループ要素で1に設定されています。つまり、所定の要素で15の仮説が見つかった場合、最善の5つが選択され、他の10の仮説連鎖は不完全なままになります。一般的に、グループ要素は単純要素よりも高い信頼性で検出されます。従って、グループ要素の最善の仮説は、通常、正しい仮説であることが判明します。
ほとんどの場合、複数の不完全な仮説連鎖があり、従って複数の可能な検索方向があります。クラシックな「ワイドサーチ」アルゴリズムで最善の仮説が検索されます。このアルゴリズムの意味は、その時点で最善の品質の連鎖がその長さにかかわらず、常に完了する、ということです。
仮説の2つの連鎖が作成された30の要素を記述したFlexiLayoutがあるとします: 推定品質が0.89で要素数29の連鎖と、推定品質0.92の要素数2の連鎖。品質面で優れている小さな連鎖が、すべての延長の品質が最初の連鎖よりも悪くなるまで、完了するよう試行されます。
グループ要素の場合は、品質最適化が用いられます。所定のグループ要素で理想的な完全連鎖が見つかると(すなわちこの連鎖の品質は1)、他のすべてのバリエーションは無視されます。
各要素の仮説数の合計は10,000に制限されています。
詳細：
12.04.2024 18:16:07