|
шаге, используется оценка частично построенного варианта сопоставления, скорректированная с учетом априорного ожидания ухудшения финальной оценки. Порождение гипотезы о необязательном элементе Если структурный элемент помечен в эталоне как необязательный, то, наряду с обычными вариантами сопоставления элемента, необходимо выдвинуть гипотезу о его отсутствии. Гипотеза об отсутствии факультативного элемента порождается только тогда, когда нет ни одного варианта выделения необязательного элемента, имеющего ненулевое собственное качество узла (показатель качества элемента, умноженный на показатель качества обычных (зависимых) отношений). Это правило было введено по двум причинам. Во первых, если гипотезу об отсутствии необязательного элемента выдвигать всегда, то это может очень существенно увеличить объем перебора даже при среднем количестве элементов в описании. Во вторых, даже если необязательный элемент реально присутствует на изображении, существует вероятность того, что будет выбрана гипотеза о его отсутствии. Это может случиться в том случае, если необязательный элемент имеет низкую собственную оценку, а штраф за остаток черного меньше, чем ухудшение оценки за счет его присутствия. Такое поведение системы нежелательно, так как реально присутствующий на изображении элемент должен быть оценен на основании его отношений, а не «слепым» способом за счет штрафа за остаток. Штраф за остаток В идеале сопоставленные структурные элементы должны полностью покрывать исходное изображение. Но, из-за мелкого шума и дефектов, эго не всегда достижимо. Непокрытый остаток изображения допускается со штрафом, чтобы избежать ситуаций, когда эталон отбрасывает существенные части изображения. Например, на изображении буквы «П» лег ко можно найти букву «Г», если не обращать внимания на то, что правый вертикальный штрих остался непокрытым. Штраф состоит из двух множителей: штрафа за длину неиспользованного векторного изображения и штрафа за несоответствие описывающих рамок исходного изображения найденному варианту сопоставления. При расчете длины неиспользованного векторного изображения, делается поправка для маленьких отростков из их длины вычитается 2 пикселя для 109 |
Механизм перебора работает циклически, до тех пор, пока не будет получен полный путь или не будет исчерпан лимит перебора. За один шаг в дерево добавляется один узел. Для выбора ребра, которое добавляется к древовидному графу на очередном шаге, используется оценка частично построенного варианта сопоставления, скорректированная с учетом априорного ожидания ухудшения финальной оценки. Порождение гипотезы о необязательном элементе Если структурный элемент помечен в эталоне как необязательный, то наряду с обычными вариантами сопоставления элемента необходимо выдвинуть гипотезу об его отсутствии. Гипотеза об отсутствии факультативного элемента порождается только тогда, когда нет ни одного варианта выделения необязательного элемента, имеющего ненулевое собственное качество узла (показатель качества элемента, умноженный на показатель качества обычных (зависимых) отношений). Это правило было введено по двум причинам. Во первых, если гипотезу об отсутствии необязательного элемента выдвигать всегда, это очень существенно увеличивает объем перебора даже при среднем количестве элементов в описании. Во вторых, даже если необязательный элемент реально присутствует на изображении, есть вероятность того, что будет выбрана гипотеза о его отсутствии. Это случается тогда, когда элемент имеет низкую оценку и штраф за остаток черного оказывается меньше, чем ухудшение оценки за счет необязательного элемента. Такое поведение системы нежелательно, так как реально присутствующий на изображении элемент должен быть оценен своими отношениями, а не с помощью "слепого" штрафа за остаток. Оценка априорного качества пути Дерево перебора достраивается в шаговом режиме, по одному узлу. Очередной достраиваемый узел определяется на основе априорной оценки качества будущего узла. Управление порядком перебора осуществляется ради увеличения эффективности работы алгоритма: во-первых, если построен полный путь с хорошей оценкой, дальнейший перебор отсекается, что приводит к экономии времени; во-вторых, при наличии ограничений на объем работы по распознаванию более раннее построение наилучшего пути означает меньшую вероятность того, что он попадет под отсечение. 77 По умолчанию абстрактный структурный анализатор в качестве априорной берет оценку сверху качества узла, умноженную на коэффициент, зависящий от уровня дерева. Коэффициент меняется линейно от 0.8 для первого уровня дерева до 1 для последнего. Назначение его состоит в том, чтобы при сопоставимых оценках продолжалась более длинная ветвь перебора. В результате получается некоторая промежуточная стратегия между перебором вглубь и перебором вширь. В случае распознавания символов есть еще один важный источник информации, который используется для вычисления априорного качества. Существует эвристическая функция сравнения, упорядочивающая варианты сопоставления одного структурного элемента. В большинстве случаев правильный вариант оказывается на первом месте. Поэтому путь, состоящий из локально лучших вариантов, имеет высокую вероятность быть правильным. С целью учета результатов локальной сортировки в схему формирования априорной оценки был добавлен еще один множитель; для пути, состоящего из локально лучших вариантов, он равен единице, а для всех остальных небольшой (существенно меньше единицы) константе. В результате локально лучший путь строится первым, потому что он получает значительно более высокие априорные оценки. После того как он построен, начинается обычный перебор, поскольку • дополнительный множитель имеет одинаковое значение для всех остальных путей и уже не влияет на порядок перебора. Вариант структурного элемента является локально лучшим, если он оказывается первым в списке вариантов, выданных выделителем или если все стоящие над ним варианты имеют нулевое качество отношений. В случае альтернации структурных элементов локально лучший элемент определяется каждым выделителем независимо. При этом получается, что лучший путь разветвляется по количеству альтернирующих элементов. Штраф за остаток В идеале сопоставленные структурные элементы должны покрывать полностью исходное изображение. Но из-за мелкого шума и дефектов это не всегда достижимо. Непокрытый остаток изображения допускается со штрафом, чтобы избежать ситуаций, ког да эталон отбрасывает существенные части изображения. Например на изображении бу квы ТГ легко можно найти букву "Г", если не обращать внимания на то, что правый вертикальный штрих остался непокрытый. Штраф состоит из двух множителей: штрафа 78 за длину неиспользованного векторного изображения и штрафа за несоответствие описывающих рамок исходного изображения и найденного варианта сопоставления. При расчете длины неиспользованного векторного изображения делается поправка для маленьких отростков из их длины вычитается 2 пиксела для компенсации погрешностей векторизации. Возможно, после улучшения векторизации эту поправку можно будет откинуть. Зависимость штрафа от длины остатка представляет из себя монотонно убывающую функцию, форма которой определялась экспериментально (рис. 3.14). оценка 1/4 3/4 полной диагонали длины изображения Рис. 3.14. Штраф за остаток черного. Ограничение на объем проделанной работы Процесс сопоставления структурного эталона с изображением может легко породить комбинаторный взрыв. Чтобы этого не происходило, имеется ограничение на объем проделанной работы. Работа измеряется в количестве исходных отрезков, пройденных выделителями. Ограничение устанавливается на сопоставление одного эталона. Максимальное число проходимых отрезков зависит от эталона; этот параметр можно изменять в тексте описания эталона, что крайне необходимо случае отдельных особо сложных символов, для которых стандартный порог слишком мал. Ограничение на число пройденных отрезков ослабляется для выделителей, продолжающих локально лучший путь. Такие выделители имеют возможность пройти какое-то небольшое число 79 |