Russian (Русский) - Change language

Выдвижение гипотез

Наложение гибкого описания - это попытка программы найти на изображении объекты, соответствующие элементам гибкого описания, с последующим выставлением оценки соответствия результата поиска заданному описанию. В качестве оценки используется десятичное число от 0 до 1. Значение, равное 1, означает стопроцентное соответствие найденного результата описанию. Если оценка отлична от нуля, то наложение гибкого описания также включает в себя этап формирования регионов блоков гибкого описания FlexiLayout.

При наложении гибкого описания на изображение элементы ищутся последовательно в том порядке, в котором они описаны в гибком описании, сверху вниз по ветке элементов. Для каждого элемента в заданной области поиска может быть найдено несколько объектов изображения (или наборов объектов), подходящих под описание элемента. Программа рассматривает найденные различные варианты в качестве гипотез расположения элемента на изображении. Каждому такому варианту, называемому «гипотезой», программа выставляет оценку соответствия описанию элемента, которая называется оценкой качества гипотезы.

От найденного расположения элемента зависит расположение элементов, описанных после него. Поэтому поиск следующего элемента осуществляется независимо для каждой найденной гипотезы текущего элемента. Таким образом, гипотезы элементов гибкого описания образуют дерево, существенно более разветвленное, чем дерево элементов.

Если элементы объединены в группу с помощью составного элемента, то вся группа тоже представляет собой элемент, для которого формируется несколько возможных гипотез, по числу завершенных цепочек подэлементов группы. Оценка качества гипотезы составного элемента Group вычисляется перемножением качеств гипотез элементов, входящих в составной элемент. Все гибкое описание FlexiLayout целиком само по себе является составным элементом, так что качество наложения гибкого описания определяется перемножением качества всех его элементов.

Задача наложения гибкого описания заключается в поиске наилучшей завершенной ветки всего дерева гипотез, т.е. включающей все элементы от первого до последнего. Общее решение такой задачи подразумевает рассмотрение всех возможных комбинаций гипотез всех элементов между собой, построение полного множества завершенных веток и выбор лучшей из них. Однако на практике такое решение заняло бы слишком много времени. К тому же при увеличении числа элементов и недостаточно строгом ограничении области поиска и параметров элементов возможен комбинаторный взрыв, т.е. резкое увеличение числа рассматриваемых вариантов.

С целью ограничения времени перебора вариантов программа использует несколько принципов оптимизации поиска.

Принципы оптимизации поиска

Каждый элемент имеет свойство Number of surviving hypotheses , которое ограничивает число гипотез данного элемента, которые будут использоваться в дальнейшем поиске, т.е. при поиске следующего элемента. По умолчанию значение этого свойства равно 5 для простых элементов и 1 для составных элементов. Это означает, что, найдя в заданной области поиска 15 гипотез для простого элемента, программа выберет из них 5 лучших. Остальные 10 цепочек гипотез останутся незавершенными. Поскольку составной элемент ищется с большей степенью надежности, чем простой, то его лучшая гипотеза, как правило, оказывается верной.

В процессе поиска объектов, соответствующих элементам, программа практически всегда имеет несколько незавершенных цепочек гипотез для найденных объектов, а, следовательно, и несколько возможностей для продолжения поиска. Поиск наилучшей гипотезы производится с помощью классического алгоритма "поиска в ширину" – то есть программа всегда ищет продолжение цепочки гипотез, которая является наилучшей по качеству на данном этапе поиска, независимо от длины этой цепочки. Например, если для гибкого описания из 30 элементов в процессе поиска существуют 2 цепочки: одна из 29 элементов с качеством 0.89, другая из 2-х элементов с качеством 0.92, то будет развиваться вторая цепочка до тех пор, пока все ее продолжения не станут хуже, чем первая.

Для составного элемента применяется правило оптимизации по качеству: если найдена идеальная завершенная цепочка этого элемента, т.е. качество найденной цепочки равно 1, то другие варианты подэлементов данной группы программой не рассматриваются.

Для каждого элемента программа ограничивает общее число гипотез элемента на всех ветках дерева гипотез числом 10000.

Подробнее:

Построение и оценка гипотез для типов элементов

10.11.2020 12:08:08


Please leave your feedback about this article