Zum Hauptinhalt springen
Wenn das Programm ein FlexiLayout mit einem Bild abgleicht, versucht es, die Objekte im Bild zu finden, die den Elementen im FlexiLayout entsprechen. Anschließend bewertet das Programm, wie gut ein bestimmtes Objekt zu seinem Element passt. Diese Bewertung ist eine Zahl zwischen 0 und 1. Eine Qualität von 1 bedeutet, dass das erkannte Objekt zu 100 % übereinstimmt. Ist die Qualität ungleich 0, führt das Matching des FlexiLayout zur Erstellung von Regionen für die Blöcke. Das Programm sucht nacheinander nach Elementen, und zwar in der Reihenfolge, in der sie im FlexiLayout-Baum von oben nach unten angeordnet sind. Für jedes Element kann das Programm mehrere passende Objekte (oder Objektgruppen) im Suchbereich finden. Für jedes Objekt im Suchbereich formuliert das Programm eine Hypothese und bewertet deren Qualität – je besser die Übereinstimmung, desto höher die Qualität der Hypothese. Die Position des erkannten Objekts bestimmt die Position der Objekte weiter unten im FlexiLayout-Baum. Das Programm verwendet jede Hypothese des aktuellen Elements als Ausgangspunkt, um nach den nachfolgenden Elementen zu suchen, die sich unterhalb des aktuellen Elements befinden. Dadurch verzweigen sich die Hypothesen für die Elemente, sodass ein Hypothesenbaum entsteht, der deutlich mehr Verzweigungen enthält als der Elementbaum. Wenn mehrere Elemente zu einem Gruppenelement zusammengefasst werden, wird die gesamte Gruppe als ein Element behandelt, für das mehrere Hypothesen formuliert werden. Die Qualität eines Gruppenelements wird berechnet, indem die Hypothesen für die enthaltenen Elemente multipliziert werden. Das gesamte FlexiLayout kann als ein Gruppenelement betrachtet werden, dessen Qualität durch Multiplikation der Qualitäten der Hypothesen für alle seine Elemente berechnet werden kann. Beim Matching eines FlexiLayout mit Bildern muss das Programm den besten vollständigen Hypothesenzweig finden. Ein Zweig ist vollständig, wenn er alle Elemente umfasst, vom obersten bis zum untersten Element. Eine allgemeine Lösung bestünde darin, alle möglichen Kombinationen von Hypothesen für alle Elemente zu betrachten, die vollständige Menge aller möglichen vollständigen Zweige zu bilden und den Zweig mit der höchsten Qualität auszuwählen. Dies ist jedoch nicht praktikabel, da es zu viel Zeit in Anspruch nehmen würde. Außerdem kann es bei einer relativ großen Anzahl von Elementen und nur näherungsweise definierten Suchbereichen zu einer kombinatorischen Explosion kommen, was zu einem unkontrollierbaren Anwachsen der Anzahl von Hypothesen führt. Das Programm verwendet mehrere Methoden zur Optimierung der Suche, um die Anzahl der Hypothesen auf ein Minimum zu beschränken.”

​
Suchoptimierung

Jedes Element im FlexiLayout hat einen wichtigen Parameter namens Number of surviving hypotheses. Mit diesem Parameter kann der Benutzer die Anzahl der Hypothesen begrenzen, die das Programm bei der Suche nach dem nachfolgenden Element verwenden darf. Standardmäßig ist dieser Parameter für einfache Elemente auf 5 und für Gruppenelemente auf 1 gesetzt. Das bedeutet: Wenn das Programm für ein bestimmtes Element 15 Hypothesen findet, wählt es die fünf besten aus, während die übrigen 10 Hypothesenketten unvollständig bleiben. Gruppenelemente werden in der Regel zuverlässiger erkannt als einfache Elemente. Daher erweist sich die beste Hypothese für ein Gruppenelement normalerweise als die richtige. In den meisten Fällen verfügt das Programm über mehrere unvollständige Hypothesenketten und folglich über mehrere mögliche Suchrichtungen. Das Programm sucht mithilfe des klassischen „Breitensuche“-Algorithmus nach der besten Hypothese. Das bedeutet, dass das Programm immer versucht, die Kette zu vervollständigen, die im jeweiligen Moment die beste Qualität aufweist, unabhängig von ihrer Länge. Angenommen, wir haben ein FlexiLayout, das 30 Elemente beschreibt und für das zwei Hypothesenketten erstellt wurden: eine Kette aus 29 Elementen mit einer geschätzten Qualität von 0,89 und eine Kette aus 2 Elementen mit einer geschätzten Qualität von 0,92. Das Programm wird versuchen, die kürzere Kette zu vervollständigen, die qualitativ besser ist, bis die Qualität all ihrer Erweiterungen schlechter wird als die der ersten Kette. Im Fall eines Gruppenelements verwendet das Programm die sogenannte Qualitätsoptimierung. Wenn das Programm für ein bestimmtes Gruppenelement eine ideale vollständige Hypothesenkette findet (d. h. die Qualität dieser Kette beträgt 1), ignoriert es alle anderen Varianten. Die Gesamtzahl der Hypothesen für jedes Element ist auf 10.000 begrenzt.

​
Weitere Informationen:

Wie Hypothesen erzeugt und bewertet werden