Passer au contenu principal
Lorsque le programme fait correspondre un FlexiLayout à une image, il tente de trouver sur l’image les objets qui correspondent aux éléments du FlexiLayout. Le programme é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.

​
Comment l’arbre d’hypothèses est construit

Le programme recherche les éléments successivement, dans l’ordre où ils apparaissent dans l’arborescence FlexiLayout, de haut en bas. Pour chaque élément, le programme 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. La position de l’objet détecté détermine la position des objets situés plus bas dans l’arborescence 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 donne un arbre d’hypothèses comportant beaucoup plus de branches que l’arbre des éléments. Si plusieurs éléments sont réunis 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 hypothèses des éléments qui le composent. 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.

​
La meilleure branche complète d’hypothèses

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 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. Le programme utilise plusieurs méthodes pour optimiser la recherche et 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. Utilisez ce paramètre pour limiter le nombre d’hypothèses que le programme 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 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. Les éléments Group sont généralement 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 est généralement 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. Il recherche la meilleure hypothèse à l’aide de l’algorithme classique de « wide search ». Cet algorithme consiste à toujours tenter de compléter la chaîne dont la qualité est la meilleure à l’instant considéré, 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. Le programme tentera de compléter la chaîne la plus courte, dont la qualité est meilleure, 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 une optimisation de 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 égale à 1), il ignore toutes les autres variantes. Le nombre total d’hypothèses pour chaque élément est limité à 10 000.