МОДИФИКАЦИЯ АЛГОРИТМА РАСТЕРИЗАЦИИ ВУ ДЛЯ СИСТЕМ ВИЗУАЛИЗАЦИИ ГРАФИЧЕСКИХ ОБЪЕКТОВ

В.М. Лебедев­1, Д.В. Домашова1, С.В. Горелов1, Н.А. Евстифеева2

1 Финансовый университет при Правительстве Российской Федерации, Москва, Россия

2 Национальный исследовательский ядерный университет «МИФИ», Москва, Россия

stud_leb@mail.ru, janedom@mail.ru

 

Содержание

Введение

1. Алгоритм Ву для растеризации отрезка

1.1. Описание алгоритма Ву

1.2. Анализ скорости и качества растеризации алгоритма Ву

1.2.1. Анализ «скорости» алгоритма

1.2.2. Анализ показателя «качество»

2. Модифицированный алгоритм Ву

2.1. Описание модифицированного алгоритма Ву

2.2. Сравнение модифицированного и стандартного алгоритмов Ву

3. Апробация алгоритмов Ву

Выводы

Список литературы

 

Аннотация

В статье проведен анализ и предложена модификация алгоритма Ву для использования в автоматизированных системах визуализации изображений при совмещении графических объектов разных форматов. Проводится сравнительный анализ скорости и качества растеризации стандартного и модифицированного алгоритмов Ву. Формулируются рекомендации по их использованию при отображении для различных масштабов карт.

 

Ключевые слова:  алгоритм Ву, растеризация, перспективная трансформация, коэффициент искажения, векторный графический формат, растровые изображения

 

Введение

 

Для многих крупных архитектурных и строительных компаний важной проблемой является автоматизация визуализации расположения в окружающем ландшафте их будущих построек. Многие используемые системы автоматизированного проектирования, такие как AutoCAD и IntelliCAD, сохраняют результаты своей работы в виде документов векторного формата DWG или DXF. В этих форматах изображения хранятся в виде геометрических примитивов, таких как точки, линии, сплайны и многоугольники. Большинство же доступных снимков или карт ландшафтов представлены в растровых форматах.

Для совмещения графического изображения в  векторном формате с графическим изображением в растровом формате необходимо преобразовывать векторное изображение в растровое. Процесс преобразования изображений из векторного формата в растровый будем называть растеризацией.

В данной работе рассматриваются  вопросы анализа и модификации алгоритма Ву [2] с точки зрения его использования в автоматизированных системах визуализации изображений для совмещения графических изображений разных форматов.

 

1. Алгоритм Ву для растеризации отрезка

1.1. Описание алгоритма Ву

 

Несложно заметить, что существует множество способов перевести векторный отрезок в растровый формат изображения. В настоящее время задача растеризации решается с помощью алгоритмов Брезенхема и Ву [1-5].  

Джек  Е.  Брезенхэм  в  1962  году  предложил  способ  определения принадлежности каждого из пикселов двумерного растра отрезку с использованием лишь целочисленной арифметики. К его методам относятся алгоритмы Брезенхема генерации 4-х связной и 8-ми связной разверток отрезка [1], общим недостатком которых является то, что они «рисуют» отрезки с неровными, резкими краями.

Для преодоления указанного недостатка Wu Xiaolin создал алгоритм, рисующий "сглаженный" отрезок [2]. Это достигается за счет закрашивания разных участков отрезка в разные цвета, что позволяет "сглаживать" неровности (см. рисунок 1). Алгоритм Wu (алгоритм Ву) является одним из методов антиалиасинга [3-5]. В дальнейшем этот алгоритм будем еще называть стандартным алгоритмом Ву.

Для того чтобы определить, какие пикселы двумерного растра  необходимо  отнести  к  изображению  отрезка,  требуется  анализировать  их  расположение относительно  этого  отрезка. Основная идея алгоритма состоит в том, что работа осуществляется с парами пикселей, между центрами которых проходит отрезок. Здесь пиксели - это квадраты со стороной 1 и центрами, расположенными в узлах целочисленной решетки. Говоря  "пиксель с координатами (x, y)", имеют в виду, что его центр расположен в этой точке.

 

wuline

Рис. 1.  Растеризация отрезка с помощью алгоритма Ву

 

На рисунках 2 и 3 показано как выбираются закрашиваемые пары из множества пикселей. В данном  случае, прямая лежит ближе к оси OX, чем к OY, поэтому пары состоят из соседних по вертикали элементов. Если бы прямая была ближе к оси OY, то пары бы выбирались из соседей по горизонтали.

 

wuline_2

Рис. 2. Пиксели, выбираемые алгоритмом Ву для закрашивания

 

wuline_1

Рис. 3. Пиксели, закрашиваемые алгоритмом Ву

 

Суммарная яркость пары пикселей, соединенных красными линиями (рисунок 2), равна единице. Пропорция, в которой эта яркость распределяется внутри пары, зависит от близости отрезка к центру пикселя (рисунок 3).

При всей своей простоте метод Ву быстр и позволяет строить очень качественно сглаженные отрезки [2].

При изменении координат отрезок, нарисованный по алгоритму Ву, будет перемещаться непрерывно. За счет этого можно обеспечивать плавную анимацию при рисовании движущихся изображений.

 

1.2. Анализ скорости и качества растеризации алгоритма Ву

 

Рассмотрим использование  стандартного алгоритма Ву для решения задачи растеризации векторных изображений. Анализ его характеристик проведем для нормальных изображений по двум критериям (показателям): скорость и качество растеризации.

 

1.2.1. Анализ «скорости» алгоритма

 

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

Заметим, что самым «сложным» для растеризации является рисование отрезка под углом 45 градусов. Тогда оценку алгоритма Ву по скорости будем осуществлять при рисовании отрезка с координатами ({0;0};{n;n}).

Рассматриваемый алгоритм линейный, т.е. скорость зависит от количества растеризуемых точек. Поэтому для рисования отрезка с координатами ({0;0};{n;n}) потребуется n итераций. Результаты анализа  приведены в таблице 1, из которой следует, что алгоритм Ву является довольно  быстрым.

В таблице 1, под сложностью итерации понимается как количество операций на закрашивание одного пикселя, так и расчет яркости на один пиксель.

 

Таблица 1. Скорость и трудоемкость алгоритмов растеризации

Название алгоритма

Количество итераций

Сложность итерации

Ву (Wu)

n

2 + o(2)

 

1.2.2. Анализ показателя «качество»

 

Под качеством алгоритма, в данном случае, будем понимать степень совпадения изображения на фотографии и полученного растеризованного изображения. Для количественной оценки качества алгоритма введем понятие коэффициента искажения, который показывает, насколько полученное изображение не соответствует ожидаемому.

Коэффициент искажения вычисляется как отношение несовпадающих пикселей к общему количеству пикселей и измеряется в процентах (0% - полное совпадение, 100% - полное не совпадение).

Приведем пример вычисления коэффициента искажения.

Случай 1. Пусть ожидается изображение, приведенное на рисунке 4, а получается  изображение, приведенное на рисунке 5. Коэффициент искажения в данном случае равен 30% (3 пикселя из 10 имеют полное несовпадение).

Случай 2. Пусть ожидается изображение, приведенное на рисунке 4, а получается изображение, приведенное на рисунке 6. В данном случае коэффициент искажения равен 10%  (2 пикселя из 10 имеют частичное несовпадение)

 

k1

Рис. 4. Ожидаемое растеризованное изображение

k2

Рис. 5. Растеризованное изображение (случай 1)

k3

Рис. 6. Растеризованное изображение (случай 2)

 

Введем понятие ошибок первого и второго рода. Под ошибкой первого рода будем понимать следующее: линия должна быть, а ее нет. Под ошибкой второго рода понимается то, что линия есть, а ее быть не должно.

Проведем анализ алгоритма по качеству растеризации. Заметим, что наихудшее качество достигается при рисовании отрезков под углом 45 градусов. На рисунке 7 приведено ожидаемое идеальное растеризованное изображение, а на рисунке 8 - растеризованное изображение, полученное с помощью алгоритма Ву. В результате работы алгоритма Ву получается отрезок со сглаженными краями (рисунок 8), коэффициент искажения не превосходит 25%. Присутствуют ошибки первого и второго рода.

 

k_ideal 

Рис. 7. Идеальное растеризованное изображение

k_wu

Рис. 8. Растеризованное  изображение, полученное алгоритмом Ву

 

К сожалению, представленный алгоритм  не дает удовлетворительного качества при наложении растеризованных изображений на электронные карты. Это происходит потому, что большинство фотографий сделано не вертикально, а под углом. Поэтому алгоритм Ву рекомендуется использовать для растеризации изображений в случае их большого и  среднего масштабов, где важна скорость отображения.

 

2. Модифицированный алгоритм Ву

2.1. Описание модифицированного алгоритма Ву

 

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

За основу нового алгоритма был взят стандартный алгоритм Ву, который работает на первом этапе растеризации. На втором этапе производится его искажение с учетом угла фотографирования. Это «искажение» достигается с помощью алгоритма перспективной трансформации, который можно формализовать следующим образом.

Пусть:

          - матрица, описывающая исходный объект;

 - матрица вращения  объекта вокруг оси OX;

 

 - матрица вращения объекта вокруг оси OY;

 - матрица вращения объекта вокруг оси OZ.

Тогда  - матрица преобразования исходного объекта,

где   .

Пусть:

 - матрица положения камеры;

 - матрица вращения  камеры вокруг оси OX;

 - матрица вращения камеры вокруг оси OY;

 - матрица вращения камеры вокруг оси OZ.

 

Тогда   – матрица преобразования камеры, где  .

Пусть  - матрица перспективного преобразования,

где

μ - угол между линией, указывающей из камеры в направлении оси z и плоскости, проходящей через камеру,  и  правым краем экрана;

ν - угол между той же линией и плоскости, проходящей через камеру и верхним краем  экрана;

F - положительное число, представляющее расстояние от наблюдателя до передней плоскости отсечения объекта при его перспективной проекции на экран;

B - положительное число, представляющее расстояние до задней плоскости отсечения объекта. При этом значение величины B может быть бесконечным. Тогда при    выполняются следующие условия:

  (B + F) / (B - F) = 1;

.

Данные условия становятся справедливыми при , т.к., в этом случае, можно считать, что величина F пренебрежительно мала по сравнению с B, и  тогда

, а .

Следовательно, итоговое преобразование координат пикселя можно записать в следующем виде:

,

где

  - вектор столбец исходных координат пикселя,

 - вектор столбец преобразованных координат пикселя.

 

Описанный алгоритм будем в дальнейшем называть модифицированным алгоритмом Ву.

 

2.2. Сравнение модифицированного и стандартного алгоритмов Ву

 

Сравнение стандартного и модифицированного алгоритмов Ву проведем для нормальных изображений по двум критериям (показателям): скорость и качество растеризации.

Заметим, что самым «сложным» является рисование отрезка под углом 45 градусов. Тогда оценку скорости алгоритма будем осуществлять при рисовании отрезка с координатами ({0;0};{n;n}).

Рассматриваемый модифицированный алгоритм Ву линейный, т.е. скорость зависит от количества растеризуемых точек. При этом для отрисовки каждой точки отрезка используется два прогона. Поэтому для рисования отрезка с координатами ({0;0};{n;n}) потребуется 2n итераций. Результаты анализа  приведены в таблице 2. Здесь  под сложностью итерации понимается как количество операций на закрашивание одного пикселя, так и расчет яркости на один пиксель.

 

Таблица 2. Скорость и трудоемкость алгоритма модифицированного алгоритма Ву

Название алгоритма

Количество итераций

Сложность итерации

модифицированный алгоритм Ву

2n

2+о(2)

 

Из таблиц 1 и 2 видно, что модернизированный алгоритм Ву проигрывает оригиналу в скорости.

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

 

Рис. 9. Диаграмма сравнения качества модернизированного и стандартного алгоритмов Ву

 

3. Апробация алгоритмов Ву

 

Рассматриваемые алгоритмы Ву реализованы в разработанном прототипе программного  комплекса сопровождения строительства крупных объектов RastWuCAD.

Этот комплекс представляет собой набор веб-сервисов, к которым относятся: файловый навигатор,   проигрыватель фотографий строящихся объектов, обозреватель географических изображений.

RastWuCAD является «клиент-серверным» приложением.  Серверная  часть реализована по технологии REST на языке программирования Java, клиентская часть – на HTML+CSS+JavaScript и Flex (ActionScript). Взаимодействие между серверной и клиентской частью осуществляется по технологии AJAX.

Файловый навигатор поддерживает стандартные функции ведения файлового пространства: просмотр и создание папок, загрузка и копирование файлов, поиск файлов и папок по файловому пространству. Файловое пространство системы содержит, в основном, изображения строительных объектов в векторном формате, набор электронных географических карт ресурса Google maps в растровом формате.

Проигрыватель фотографий позволяет осуществлять масштабирование изображений; просмотр фотографий строящихся объектов в динамике и разных ракурсах.

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

На рисунке 10 приведен скриншот окна обозревателя приложения с наложенным на карту изображением строительного объекта. Данный объект представляет собой план   коттеджного поселка с проложенными дорожными коммуникациями. Векторное изображение получено с помощью системы автоматизированного проектирования AutoCAD и наложено на рельеф местности c помощью комплекса RastWuCAD.

 

VO_settings

Рис. 10 Обозреватель географических объектов после наложения объекта на карту

 

Апробация модифицированного  алгоритма Ву при растеризации векторных изображений строительных объектов также показала, что коэффициент искажения изображений лежит в диапазоне от 3% до 17%, что по экспертным оценкам является хорошим результатом.

 

Выводы

 

Таким образом, можно сделать следующие выводы.

1.      Для решения задачи растеризации был выбран и исследован алгоритм Ву. Анализ показателей результатов его растеризации показал, что он быстр и позволяет строить качественные сглаженные отрезки.

Исследования также показали, что этот алгоритм не дает должного качества в случае использования карт мелкого масштаба. Поэтому стандартный алгоритм Ву рекомендуется  использовать в случае растеризации на картах крупных масштабов, где важна скорость отображения.

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

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

 

Список литературы

 

1.       Bresenham  J.  E.  Algorithm  for  computer  control  of  a  digital  plotter  //  IBM  Systems  Journal.  – 1965. – V. 4. – P. 25–30.

2.      Y. 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

3.      Иванов Д.,  Карпов А.,  Кузьмин Е. Алгоритмические основы растровой графики  [Электронный ресурс]  // Официальный сайт Интернет университета информационных технологий (www.intuit.ru). 23.04.2007.  URL:  http://www.intuit.ru/studies/courses/993/163/info, свободный. – Загл. с экрана. – Яз. Рус.

4.      Куликов А.,   Овчинникова Т. Алгоритмические основы современной компьютерной графики [Электронный ресурс]  // Официальный сайт Интернет университета информационных технологий (www.intuit.ru).  20.10.2007. URL:     http://www.intuit.ru/studies/courses/70/70/info, свободный. – Загл. с экрана. – Яз. Рус.

5.      Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир, 1989. — 512 с.



MODIFICATION OF WU’S RASTERIZATION ALGORITHM FOR SYSTEMS OF GRAPHIC OBJECT VISUALIZATION

V.M.Lebedev1, D.V. Domashova1, S.V. Gorelov1, N.A. Evstifeeva2

1Financial University under the Government of the Russian Federation, Moscow, Russian Federation

2National Research Nuclear University MEPhI (Moscow Engineering Physics Institute), Moscow, Russian Federation

stud_leb@mail.ru, janedom@mail.ru

 

Annotation

The article presents analysis and modification of Wu’s algorithm for automated visualization systems, in respect to overlaying graphic objects of different formats. Comparative analysis of the rasterization speed and quality of the standard and modified Wu’s algorithms as well as recommendations on the use of the algorithms for various map scales are also provided.

 

Keywords: Wu’s algorithm, rasterization, perspective transformation, distortion factor, vector-based format, raster image

 

References

 

1.      Bresenham  J.  E.  Algorithm  for  computer  control  of  a  digital  plotter  //  IBM  Systems  Journal.  – 1965. – V. 4. – P. 25–30.

2.      Y. 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

3.      Ivanov D., Karpov A., Kuzmin E. Algoritmicheskie osnovy rastrovoj grafiki [Algorithmic fundamentals of raster graphics] [Electronic resource].Official site of Internet university of information technologies (www.intuit.ru). 23.04.2007. URL: http://www .intuit.ru/studies/courses/993/163/info, free. – The title from the screen. [in Russian].

4.      Kulikov A., Ovchinnikova T. Algoritmicheskie osnovy sovremennoj komp'juternoj grafiki [Algorithmic fundamentals of modern computer graphics] [Electronic resource]. Official site of Internet university of information technologies (www.intuit.ru). 20.10.2007. URL: http://www .intuit.ru/studies/courses/70/70/info, free. – The title from the screen. [in Russian].

5.      Rogers D. Algoritmicheskie osnovy mashinnoj grafiki [Algorithmic basics of machine graphics]. M.: World, 1989. 512 p.