Для многих крупных архитектурных и строительных компаний важной проблемой является автоматизация визуализации расположения в окружающем ландшафте их будущих построек. Многие используемые системы автоматизированного проектирования, такие как AutoCAD и IntelliCAD, сохраняют результаты своей работы в виде документов векторного формата DWG или DXF. В этих форматах изображения хранятся в виде геометрических примитивов, таких как точки, линии, сплайны и многоугольники. Большинство же доступных снимков или карт ландшафтов представлены в растровых форматах.
Для совмещения графических изображенийразных форматовчасто возникает необходимость в преобразованиивекторногоизображения в растровое. Процесс преобразования изображений из векторного формата в растровый будем называть растеризацией.
В данной работе рассматриваются вопросы анализаи модификации алгоритма Ву[2] с точки зрения его использования в автоматизированных системах визуализации изображений для совмещения графических изображений разных форматов.
- Алгоритм Ву для растеризации отрезка
В настоящее время задача растеризации решается с помощью алгоритмов Брезенхема и Ву [1-4].Алгоритмы Брезенхема генерации 4-х связной и 8-ми связнойразверток отрезка [1] обладают общим недостатком, которыйзаключается в том, что они «рисуют» отрезки с неровными, резкими краями.
Для преодоления указанногонесовершенства Wu Xiaolin создал алгоритм, рисующий «сглаженный» отрезок [2]. Это достигается за счет закрашивания разных участков отрезка в разные цвета, что позволяет «сглаживать» неровности. Алгоритм Wu (алгоритм Ву) является одним из методов антиалиасинга [3-4]. В дальнейшем этот алгоритм будем еще называть стандартным алгоритмом Ву.
Для того чтобы определить, какие пикселы двумерного растра необходимо отнести к изображению отрезка, требуется анализировать их расположение относительно этого отрезка. Основная идея алгоритма состоит в том, что работа осуществляется с парами пикселей, между центрами которых проходит отрезок. Здесь пиксели — это квадраты со стороной 1 и центрами, расположенными в узлах целочисленной решетки. Говоря «пиксель с координатами (x,y)», имеют в виду, что его центр расположен в этой точке.
На рисунках 1 и 2 показано как выбираются закрашиваемые пары из множества пикселей. В данном случае, прямая лежит ближе к оси OX, чем к OY, поэтому пары состоят из соседних по вертикали элементов. Если бы прямая была ближе к оси OY, то пары бы выбирались из соседей по горизонтали.
Рисунок1.Пиксели, выбираемые алгоритмом Ву для закрашивания
Рисунок2.Пиксели, закрашиваемые алгоритмом Ву
Суммарная яркость пары пикселей, соединенных красными линиями (рисунок 1), равна единице. Пропорция, в которой эта яркость распределяется внутри пары, зависит от близости отрезка к центру пикселя(рисунок 2).
При всей своей простоте метод Ву быстр и позволяет строить очень качественно сглаженные отрезки [2].
При изменении координат отрезок, нарисованный по алгоритму Ву, будет перемещаться непрерывно. За счет этого можно обеспечивать плавную анимацию при рисовании движущихся изображений.
- Модифицированный алгоритм Ву
Проведенный авторами анализ показал, что стандартный алгоритм Ву дает плохое качество растеризованных изображений для карт мелкого и очень мелкого масштаба. Поэтому возникает необходимость в разработке нового алгоритма или модификации существующего.
За основу нового алгоритма был взят стандартный алгоритм Ву, который работает на первом этапе растеризации. На втором этапе производится его искажение с учетом угла фотографирования. Это «искажение» достигается с помощью алгоритма перспективной трансформации, который можно формализовать следующим образом.
Пусть:
μ — угол между линией, указывающей из камеры в направлении оси z и плоскости, проходящей через камеру, и правым краем экрана;
ν — угол между той же линией и плоскости, проходящей через камеру и верхним краем экрана;
F— положительное число, представляющее расстояние от наблюдателя до передней плоскости отсечения объекта при его перспективной проекции на экран;
B— положительное число, представляющее расстояние до задней плоскости отсечения объекта. При этом значение величины B может быть бесконечным.
Описанный алгоритм будем в дальнейшем называть модифицированным алгоритмом Ву.
- Сравнение модифицированного и стандартного алгоритмов Ву
Рассмотрим использование стандартногои модифицированногоалгоритмов Ву для решения задачи растеризации векторных изображений. Анализ их характеристик проведем для нормальных изображений по двум критериям (показателям): скорость и качество растеризации.
3.1. Анализ «скорости» алгоритмов
Скорость растеризации можно оценивать разными способами, например, по времени или количестве итераций, необходимых для получения растеризованного изображения. В качестве меры скорости выберем количество итераций.
Заметим, что самым «сложным» для растеризации является рисование отрезка под углом 45 градусов. Тогда оценку обоих алгоритмов Ву по скорости будем осуществлять при рисовании отрезка с координатами ({0;0};{n;n}).
Рассматриваемые алгоритмы линейные, т.е. скорость зависит от количества растеризуемых точек. В стандартном алгоритме Ву для рисования указанного отрезка потребуется n итераций. В модифицированном алгоритме Ву для отрисовки каждой точки отрезка используется два прогона. Поэтому для рисования отрезка с координатами ({0;0};{n;n}) потребуется 2n итераций. Результаты анализа приведены в таблице 1. Здесь под сложностью итерации понимается как количество операций на закрашивание одного пикселя, так и расчет яркости на один пиксель.
Таблица 1.
Скорость и трудоемкость алгоритмов растеризации Ву (Wu)
| Название алгоритма | Количество итераций | Сложность итерации |
| стандартный алгоритм Ву | n | 2 + o(2) |
| модифицированный алгоритм | 2n | 2+о(2) |
Из таблицы 1 видно, что алгоритм Ву является довольно быстрым, а модернизированный алгоритм Ву проигрывает оригиналу в скорости.
3.2. Анализ показателя «качество»
Под качеством алгоритма, в данном случае, будем понимать степень совпадения изображения на фотографии и полученного растеризованного изображения. Для количественной оценки качества алгоритма введем понятие коэффициента искажения, который показывает, насколько полученное изображение не соответствует ожидаемому.
Коэффициент искажения вычисляется как отношение несовпадающих пикселей к общему количеству пикселей и измеряется в процентах (0% — полное совпадение, 100% — полное не совпадение).
Приведем пример вычисления коэффициента искажения. Пусть ожидается изображение, приведенное на рисунке 3, а получается изображение, приведенное на рисунке 4. Коэффициент искажения в данном случае равен 30% (3 пикселя из 10 имеют полное несовпадение).
Введем понятие ошибок первого и второго рода. Под ошибкой первого рода будем понимать следующее: линия должна быть, а ее нет. Под ошибкой второго рода понимается то, что линия есть, а ее быть не должно.
Проведем анализ стандартного алгоритмаВу по качеству растеризации. Заметим, что наихудшее качество достигается при рисовании отрезков под углом 45 градусов. На рисунке 5 приведено ожидаемое идеальное растеризованное изображение, а на рисунке 6 растеризованное изображение, полученное с помощью стандартногоалгоритма Ву. В результате работы алгоритма Ву получается отрезок со сглаженными краями (рисунок 6), коэффициент искажения не превосходит 25%. Присутствуют ошибки первого и второго рода.
К сожалению, стандартный алгоритм Ву не дает удовлетворительного качества при наложении растеризованных изображений на электронные карты. Это происходит потому, что большинство фотографий сделано не вертикально, а под углом. Поэтому стандартныйалгоритм Ву рекомендуется использовать для растеризации изображений в случае их большого и среднего масштабов, где важна скорость отображения.
Практические исследования показали, чтомодифицированный алгоритм Ву превосходит оригинал по качеству в случаях, когда фотографиигеографических карт сделаны под большим углом отклонения от нормали. Данные результаты приведены на рисунке 7.
Апробация модифицированного алгоритма Ву при растеризации векторных изображений строительных объектов также показала, что коэффициент искажения изображений лежит в диапазоне от 3% до 17%, что по экспертным оценкам является хорошим результатом.
Рисунок7. Диаграмма сравнения качества модернизированного и стандартного алгоритмов Ву
Список литературы
- E. Algorithmforcomputercontrolofadigital plotter // IBM Systems Journal. – 1965. – V. 4. – P. 25–30.
- Wu, «Raster, Vector, and Automated Raster-to-Vector Conversion», inMoving Theory into Practice: Digital Imaging for Libraries and Archives, Book Eds. by A.R. Kenney and O.Y. Rieger, 2000, Research Libraries Group
- Иванов Д., Карпов А., Кузьмин Е. Алгоритмические основы растровой графики [Электронный ресурс] // Официальный сайт Интернет университета информационных технологий (www.intuit.ru). 23.04.2007. URL: https://www.intuit.ru/studies/courses/993/163/info, свободный. – Загл. с экрана. – Яз. Рус.
- Роджерс Д.Алгоритмические основы машинной графики. — М.: Мир, 1989. — 512с.[schema type=»book» name=»ИССЛЕДОВАНИЕ И МОДИФИКАЦИЯ АЛГОРИТМА ВУ ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАСТЕРИЗАЦИИ» description=»Рассматриваются вопросы исследования и модификации алгоритма Ву для использования в автоматизированных системах визуализации изображений при совмещении графических объектов разных форматов. Проводится сравнительный анализ скорости и качества растеризации стандартного и модифицированного алгоритмов Ву.» author=»Лебедев Виктор Михайлович, Кольцов Андрей Владимирович» publisher=»БАСАРАНОВИЧ ЕКАТЕРИНА» pubdate=»2017-03-03″ edition=»ЕВРАЗИЙСКИЙ СОЮЗ УЧЕНЫХ_27.06.2015_06(15)» ebook=»yes» ]