Passer au contenu principal
Lorsque le programme effectue la mise en correspondance d’un FlexiLayout avec une image, il 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 entraîne la création de régions pour les blocs. Le programme recherche les éléments successivement, dans l’ordre où ils apparaissent dans l’arborescence du FlexiLayout, de haut en bas. Pour chaque élément, il peut trouver plusieurs objets correspondants (ou ensembles d’objets) dans la zone de recherche. Le programme formule une hypothèse pour chaque objet de la zone de recherche et en évalue la qualité : plus la correspondance est bonne, 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 du FlexiLayout. Le programme utilise chacune des hypothèses de l’élément actuel comme point de départ pour rechercher les éléments suivants situés en dessous de cet élément. Ainsi, les hypothèses des éléments se ramifient, ce qui produit un arbre d’hypothèses comportant bien plus de branches que l’arborescence des éléments. Si plusieurs éléments sont regroupés en 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 qui le composent. Le FlexiLayout entier 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, le programme 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 le plus haut à l’élément le plus bas. Une solution générique consisterait à prendre en compte toutes les combinaisons possibles d’hypothèses pour tous les éléments, à construire l’ensemble complet de toutes les branches complètes possibles et à sélectionner la branche ayant la qualité la plus élevée. Cette approche n’est pas réaliste, car elle prendrait trop de temps. De plus, si le nombre d’éléments est assez important 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. Le programme utilise plusieurs méthodes d’optimisation de la recherche pour réduire au minimum le nombre d’hypothèses.”

​
Optimisation de la recherche

Chaque élément du FlexiLayout possède un paramètre important appelé Nombre d’hypothèses retenues. L’utilisateur peut utiliser ce paramètre pour limiter le nombre d’hypothèses que le programme peut exploiter lors de la recherche de 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 le programme trouve 15 hypothèses pour un élément donné, il sélectionnera les cinq meilleures et laissera incomplètes les 10 autres chaînes d’hypothèses. En règle générale, les éléments Group sont détectés de manière plus fiable que les éléments simples. Par conséquent, la meilleure hypothèse pour un élément Group s’avère généralement être la bonne. Dans la plupart des cas, le programme dispose de plusieurs chaînes d’hypothèses incomplètes et, par conséquent, de plusieurs directions de recherche possibles. Le programme recherche la meilleure hypothèse à l’aide de l’algorithme classique de « recherche en largeur ». Avec cet algorithme, le programme essaie toujours de compléter la chaîne dont la qualité est la meilleure à l’instant considéré, quelle que soit sa longueur. Supposons que nous ayons un FlexiLayout qui décrit 30 éléments et pour lequel deux chaînes d’hypothèses ont été créées : une chaîne de 29 éléments dont la qualité estimée est de 0.89 et une chaîne de 2 éléments dont la qualité estimée est de 0.92. Le programme tentera de compléter la chaîne la plus courte, de meilleure 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, le programme utilise ce qu’on appelle une optimisation de la qualité. Lorsque le programme 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.

​
Pour en savoir plus :

Comment les hypothèses sont générées et évaluées