Hypotheses and trees of hypotheses
Hypothèses et optimisation de la recherche
La mise en correspondance d’un FlexiLayout construit un arbre ramifié d’hypothèses. Découvrez comment la recherche en largeur et le paramètre Nombre d’hypothèses retenues permettent de maintenir une mise en correspondance rapide.
Lors de la mise en correspondance d’un FlexiLayout avec une image, FlexiLayout Studio tente de trouver sur l’image les objets qui correspondent aux éléments du FlexiLayout. Il évalue ensuite dans quelle mesure un objet donné correspond à son élément.
Cette évaluation est un nombre compris entre 0 et 1. Une qualité de 1 signifie que l’objet détecté correspond à 100 %. Si la qualité n’est pas nulle, la mise en correspondance du FlexiLayout crée des régions pour les blocs.
FlexiLayout Studio recherche les éléments successivement, dans l’ordre où ils apparaissent dans l’arborescence FlexiLayout, de haut en bas. Pour chaque élément, il peut trouver plusieurs objets correspondants (ou ensembles d’objets) dans la zone de recherche.
FlexiLayout Studio formule une hypothèse pour chaque objet de la zone de recherche et en évalue la qualité : meilleure est la correspondance, plus la qualité de l’hypothèse est élevée.
L’emplacement de l’objet détecté détermine l’emplacement des objets situés plus bas dans l’arborescence FlexiLayout. FlexiLayout Studio utilise chacune des hypothèses de l’élément courant comme point de départ pour rechercher les éléments suivants, situés plus bas dans l’arborescence.
Ainsi, les hypothèses des éléments se ramifient, ce qui produit un arbre d’hypothèses contenant bien plus de branches que l’arborescence des éléments.
Si plusieurs éléments sont regroupés dans un seul élément Group, l’ensemble du groupe est considéré comme un seul élément pour lequel plusieurs hypothèses sont formulées. La qualité d’un élément Group est calculée en multipliant les qualités des hypothèses des éléments constitutifs.
L’ensemble du FlexiLayout peut être considéré comme un élément Group dont la qualité peut être calculée en multipliant les qualités des hypothèses de tous ses éléments.
Lors de la mise en correspondance d’un FlexiLayout avec des images, FlexiLayout Studio doit trouver la meilleure branche complète d’hypothèses. Une branche est complète si elle inclut tous les éléments, de l’élément du haut à l’élément du bas.
Une solution générale consisterait à examiner toutes les combinaisons possibles d’hypothèses pour tous les éléments, à constituer l’ensemble complet de toutes les branches complètes possibles, puis à sélectionner la branche présentant la qualité la plus élevée. Ce n’est pas pratique, car cela prendrait trop de temps.
De plus, si le nombre d’éléments est assez élevé et que leurs zones de recherche ne sont qu’approximatives, une explosion combinatoire peut se produire, entraînant une augmentation incontrôlable du nombre d’hypothèses.
FlexiLayout Studio utilise plusieurs méthodes pour optimiser la recherche et réduire au minimum le nombre d’hypothèses.
Chaque élément du FlexiLayout possède un paramètre important appelé Nombre d’hypothèses retenues. Utilisez ce paramètre pour limiter le nombre d’hypothèses que FlexiLayout Studio peut utiliser pour rechercher l’élément suivant.
Par défaut, ce paramètre est défini sur 5 pour les éléments simples et sur 1 pour les éléments Group. Cela signifie que si FlexiLayout Studio trouve 15 hypothèses pour un élément donné, il sélectionne les cinq meilleures et laisse incomplètes les 10 autres chaînes d’hypothèses.
Les éléments Group sont généralement détectés plus fiablement que les éléments simples. Par conséquent, la meilleure hypothèse pour un élément Group est généralement la bonne.
Dans la plupart des cas, FlexiLayout Studio dispose de plusieurs chaînes d’hypothèses incomplètes et, par conséquent, de plusieurs directions de recherche possibles. Il recherche la meilleure hypothèse à l’aide de l’algorithme classique de « recherche en largeur ». Cela signifie que FlexiLayout Studio essaie toujours de compléter la chaîne qui présente, à un instant donné, la meilleure qualité, quelle que soit sa longueur.
Supposons qu’un FlexiLayout décrive 30 éléments pour lesquels deux chaînes d’hypothèses ont été créées : une chaîne de 29 éléments avec une qualité estimée à 0.89 et une chaîne de 2 éléments avec une qualité estimée à 0.92.
FlexiLayout Studio tente de compléter la chaîne la plus courte, meilleure du point de vue de la qualité, jusqu’à ce que la qualité de toutes ses extensions devienne inférieure à celle de la première chaîne.
Dans le cas d’un élément Group, FlexiLayout Studio utilise une optimisation par la qualité. Lorsqu’il trouve une chaîne d’hypothèses complète idéale pour un élément Group donné (c’est-à-dire lorsque la qualité de cette chaîne est de 1), il ignore toutes les autres variantes.
Le nombre total d’hypothèses pour chaque élément est limité à 10 000.