12.5. АППРОКСИМАЦИИ, ОСНОВАННЫЕ НА ИСПОЛЬЗОВАНИИ МНОГОУГОЛЬНИКОВ

Строго говоря, все кривые, воспроизводимые в большинстве систем обработки графической информации, представляют собой многоугольники, поскольку строятся они посредством соединения смежных пикселов линиями, для чего используется какая-либо

команда типа разд. 1.7, табл. 1.1). (Устройство обеспечивающее отображение только точек, представляет единственное существенное исключение.) Хорошо известный математический результат гласит, что всякую кривую можно аппроксимировать с произвольно заданной точностью некоторым многоугольником (ломаной) и, следовательно, соответствующая аппроксимация может выглядеть очень гладкой. Если задано математическое описание кривой С вида

то можно поставить задачу отыскания многоугольника, аппроксимирующего кривую С с высокой точностью и имеющего минимально возможное число вершин. Естественно, в случае, когда положение вершин можно изменять, удается находить более эффективные представления. Аналогичная задача возникает в распознавании образов с тем отличием, что С задается не уравнением, а множеством экспериментальных точек. Построение многоугольника по таким точкам способствует определению признаков, существенных для описания формы объекта Это проиллюстрировано на рис. 12.1: для зашумленных контуров с помощью алгоритма, описанного ниже, построены аппроксимирующие многоугольники.

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

Рис. 12.1 Примеры аппроксимации с помощью многоугольников, проведенной посредством алгоритма 12 1: вверху — исходные контуры рисунка, внизу — аппроксимирующие многоугольники

заданная группа точек делится до тех пор, пока условие коллинеарности не оказывается выполненным. С другой стороны, группы объединяются, если в результате слияния возникает группа приближенно коллинеарных пикселов. Итак, используется процедура расщепления — слияния, результат которой обладает одним специфическим свойством, раскрываемым в следующем утверждении.

Утверждение 12.2. Число сегментов, получаемых в результате применения процедуры расщепления — слияния, всегда меньше удвоенного значения минимального числа таких сегментов.

Доказательство. Пусть — сегменты минимального разбиения и — сегменты, выделенные в результате применения процедуры расщепления — слияния. Ни один из сегментов не может содержать двух сегментов за исключением случая слияния последних. Любой сегмент однако, может покрывать такой сегмент что сегменты перекрываются с сегментами и соответственно (рис. 12.2). Таким образом, сегментов могут полностью покрываться сегментами, принадлежащими оптимальному разбиению, и, кроме того, имеются еще сегменты, число которых равно числу точек разбиения, т. е. общее число сегментов равно Следовательно,

Рис. 12.2 Структура сегмснтоп, используемая при доказательстве утверждения 12.2

Оказывается, что полученная оценка очень сильно завышена: в реальных условиях принимает значения, много меньше Пример, дающий значение предусматривает довольно вычурное взаимное расположение оптимальных точек склеивания и концевых точек групп пикселов, проверяемых на коллинеарность. Общий принцип организации алгоритма расщепления — слияния можно реализовывать различными способами и в подразд. 12.5.2 будет изложен один из простейших. (Сведения о более совершенных алгоритмах можно найти в разд. 12.7.)