|
Выделение кольца Алгоритм выделения кольца базируется на алгоритме выделения дуги. Для выделения колец применяется слегка модифицированный механизм прослеживания дуг. При этом, используются только два критерия останова по невозможности продолжить выделение и по изолированному концу. В В ходе работы алгоритма делается попытка из каждого полученного варианта дуги сформировать кольцо. Для этого отсекается по очереди начальная и конечная часть дуги. На полученном остатке проверяются условия принадлежности к кольцу строгость, кривизна, размер общей части и т. д. При выполнении всех условий, эта часть дуги рассматривается как кольцо. Целесообразность этой процедуры обоснована тем, что дуга может захватить существенно больше, чем это необходимо. На рис. 5.5. в результате работы алгоритма выделяется дуга А В. Дуга отрезается до точки, ближайшей к одному из концов, причем точка может принадлежать середине исходного отрезка (точка С). В последнем случае наполовину использованный отрезок не включается в блокировку. 5.4 Сопоставление структурного эталона с изображением Абстрактный структурный анализатор Описание изображений с помощью структурного эталона применимо к двум различным задачам: распознаванию рукописного текста и анализу гибких форм. Хотя 107 |
Шаг 3. Если при проходе по дуге от первой точки (начала координат) ко второй точке дута загибается по часовой езрелке, то берется максимальный полярный угол, в противном случаем минимальный. (Под полярным углом вершины подразумевается угол, описываемый вектором, движу щимся вдоль кривой от текущего начала координат до рассматриваемой точки.) Если вектор описывает полный круг, полярный угол может стать больше 360 градусов. В этом случае текущие точки меняются местами и процедура повторяется. Алгоритм заканчивает работу' тогда, когда положение точек перестает изменяться. Для случая, приведенного на рис. 5.11, последовательность приближений к касательной имеет вид: [А, И], [Э, С], [С, Е]. Выделение кольца Выделение кольца базируется на алгоритме выделения дуги. Для выделения колец запускается слегка модифицированный механизм прослеживания дуг. При этом используются только два критерия останова по невозможности продолжить выделение и по изолированному концу. Рис. 3.13. Замыкание кольца. В ходе работы алгоритма делается попытка из каждого полученного варианта дуги сформировать кольцо. Для этого у дуги по очереди отсекается начальная и конечная часть. Для полученного остатка проверяются условия принадлежности к кольцу строгость, кривизна, размер общей части и т. д. Необходимость вырезания кольца из 75 части дуги вызвана тем, что дуга может захватить существенно больше, чем это необходимо; на рис. 5.12 в результате работы алгоритма выделяется дуга АВ. Дуга отрезается до точки, ближайшей к одному из концов, причем точка может принадлежать середине исходного отрезка (точка С). В последнем случае наполовину использованный отрезок не включается в блокировку. 3.9 Сопоставление структурного эталона с изображением Абстрактный структурный анализатор Описание изображений с помощью структурного эталона применимо к двум различным задачам: распознаванию рукописного текста и анализу г ибких форм. Хотя обе задачи имеют свою специфик)', можно выделить много общего в механизмах построения описания и анализа изображения. Это послужило причиной создания абстрактной модели структурного анализатора, включающей в себя три компонента: • расширяемую модель для представления структурных эталонов в виде дерева И-ИЛИ; • базовую реализацию переборного процесса сопоставления описания с изображением; • расширяемую модель представления данных в процессе перебора. Инструментарий абстракгного анализатора не задает конкретных типов структурных элементов или механизмов их сопоставления. Он скорее является базой, на основании которой строится система для решения конкретной задачи структурного распознавания. В процессе такого распознавания каждый элемент может сопоставляться с эталонным изображением более чем одним способом. Поэтому механизм перебора представляется в виде дерева, узлы которого соответствуют вариантам сопоставления элементов описания. Дерево имеет многослойную структуру: узлы первого уровня (считая от корня) соответствуют вариантам сопоставления первого элемента, узлы второго уровня вариантам сопоставления второго элемента и т. д. Поскольку эталон символа представляется последовательностью элементов его структурного описания, успешное сопоставление с эталоном соответствует полному (т. е. равному длине описания) пути в дереве перебора. Совокупность сопоставленных элементов должна полностью покрывать изображение. Неполное покрытие допускается со штрафом, чтобы компенсировать возможный шум на исходном изображении и дефекты векторизации. 76 |