|
каждая из них имеет свою специфику, можно выделить много общего в механизмах построения описания и анализа изображения при решении этих задач. Это послужило причиной создания абстрактной модели структурного анализатора, включающей в себя три компонента: 1. расширяемую модель для представления структурных эталонов в виде дерева И/ИЛИ; 2. базовую реализацию переборного процесса сопоставления описания с изображением; 3. расширяемую модель представления данных в процессе перебора. Инструментарий абстрактного анализатора не задает конкретных типов структурных элементов или механизмов их сопоставления. Он, скорее, является базой, на основании которой строится система для решения конкретной задачи структурного распознавания. При этом, в процессе распознавания каждый элемент может сопоставляться с эталонным изображением более чем одним способом. Поэтому механизм перебора представляется в виде дерева, узлы которого соответствуют вариантам сопоставления элементов описания. Дерево имеет многослойную структуру: узлы первого уровня (считая от корня) соответствуют вариантам сопоставления первого элемента, узлы второго уровня вариантам сопоставления второго элемента и т. д. Поскольку эталон символа представляется последовательностью элементов его структурного описания, успешное сопоставление с эталоном соответствует полному (т. е. равному длине описания) пути в дереве перебора. Совокупность сопоставленных элементов должна полностью покрывать изображение. Неполное покрытие допускается со штрафом, чтобы компенсировать возможный шум на исходном изображении и дефекты векторизации. Механизм перебора работает циклически до тех пор, пока нс будет получен полный путь или не будет исчерпан лимит перебора. За один шаг к дереву добавляется один узел, /(ля выбора ребра, которое добавляется к древовидному графу на очередном 108 |
части дуги вызвана тем, что дуга может захватить существенно больше, чем это необходимо; на рис. 5.12 в результате работы алгоритма выделяется дуга АВ. Дуга отрезается до точки, ближайшей к одному из концов, причем точка может принадлежать середине исходного отрезка (точка С). В последнем случае наполовину использованный отрезок не включается в блокировку. 3.9 Сопоставление структурного эталона с изображением Абстрактный структурный анализатор Описание изображений с помощью структурного эталона применимо к двум различным задачам: распознаванию рукописного текста и анализу г ибких форм. Хотя обе задачи имеют свою специфик)', можно выделить много общего в механизмах построения описания и анализа изображения. Это послужило причиной создания абстрактной модели структурного анализатора, включающей в себя три компонента: • расширяемую модель для представления структурных эталонов в виде дерева И-ИЛИ; • базовую реализацию переборного процесса сопоставления описания с изображением; • расширяемую модель представления данных в процессе перебора. Инструментарий абстракгного анализатора не задает конкретных типов структурных элементов или механизмов их сопоставления. Он скорее является базой, на основании которой строится система для решения конкретной задачи структурного распознавания. В процессе такого распознавания каждый элемент может сопоставляться с эталонным изображением более чем одним способом. Поэтому механизм перебора представляется в виде дерева, узлы которого соответствуют вариантам сопоставления элементов описания. Дерево имеет многослойную структуру: узлы первого уровня (считая от корня) соответствуют вариантам сопоставления первого элемента, узлы второго уровня вариантам сопоставления второго элемента и т. д. Поскольку эталон символа представляется последовательностью элементов его структурного описания, успешное сопоставление с эталоном соответствует полному (т. е. равному длине описания) пути в дереве перебора. Совокупность сопоставленных элементов должна полностью покрывать изображение. Неполное покрытие допускается со штрафом, чтобы компенсировать возможный шум на исходном изображении и дефекты векторизации. 76 Механизм перебора работает циклически, до тех пор, пока не будет получен полный путь или не будет исчерпан лимит перебора. За один шаг в дерево добавляется один узел. Для выбора ребра, которое добавляется к древовидному графу на очередном шаге, используется оценка частично построенного варианта сопоставления, скорректированная с учетом априорного ожидания ухудшения финальной оценки. Порождение гипотезы о необязательном элементе Если структурный элемент помечен в эталоне как необязательный, то наряду с обычными вариантами сопоставления элемента необходимо выдвинуть гипотезу об его отсутствии. Гипотеза об отсутствии факультативного элемента порождается только тогда, когда нет ни одного варианта выделения необязательного элемента, имеющего ненулевое собственное качество узла (показатель качества элемента, умноженный на показатель качества обычных (зависимых) отношений). Это правило было введено по двум причинам. Во первых, если гипотезу об отсутствии необязательного элемента выдвигать всегда, это очень существенно увеличивает объем перебора даже при среднем количестве элементов в описании. Во вторых, даже если необязательный элемент реально присутствует на изображении, есть вероятность того, что будет выбрана гипотеза о его отсутствии. Это случается тогда, когда элемент имеет низкую оценку и штраф за остаток черного оказывается меньше, чем ухудшение оценки за счет необязательного элемента. Такое поведение системы нежелательно, так как реально присутствующий на изображении элемент должен быть оценен своими отношениями, а не с помощью "слепого" штрафа за остаток. Оценка априорного качества пути Дерево перебора достраивается в шаговом режиме, по одному узлу. Очередной достраиваемый узел определяется на основе априорной оценки качества будущего узла. Управление порядком перебора осуществляется ради увеличения эффективности работы алгоритма: во-первых, если построен полный путь с хорошей оценкой, дальнейший перебор отсекается, что приводит к экономии времени; во-вторых, при наличии ограничений на объем работы по распознаванию более раннее построение наилучшего пути означает меньшую вероятность того, что он попадет под отсечение. 77 |