«национальный исследовательский томский политехнический университет»

5.3.Алгоритм разрастания регионов

Алгоритм разрастания регионов (“region growing”) является методом автоматической сегментации и учитывает пространственное расположение точек напрямую.

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

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

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

Простейшая стратегия заключается в сканировании изображения сверху вниз, слева направо. На i-м шаге этого алгоритма рассматривается точка A, и сформированы регионы B и C слева и выше от пикселя A (Рис. 5.).



Рис. 5.. i шаг алгоритма разрастания регионов

Определим I(A) как яркость пикселя A, а Cl_avg(B) и Cl_avg(C) как средние яркости областей, которым принадлежат точки B и C соответственно. Обозначим через δ пороговое значение, которое задает чувствительность метода при создании нового сегмента.

На i-м шаге алгоритма проверяются следующие условия и выполняются соответствующие действия:

1. 
   Если |I(A) – Cl_avg(B)| > δ & |I(A) – Cl_avg(C)| > δ, то создаем новую область и присоединяем к ней пиксель A.
   
2. 
   Если |I(A) – Cl_avg(B)| ≤ δ xor¹ |I(A) – Cl_avg(C)| ≤ δ, то создаем новую область и присоединяем к ней пиксель A.
   
3. 
   Если |I(A) – Cl_avg(B)| ≤ δ & |I(A) – Cl_avg(C)| ≤ δ, то проверяем:
   
   1. 
      Если | Cl_avg(B) – Cl_avg(C)| ≤ δ, то сливаем области B и C.
      
   2. 
      Если | Cl_avg(B) – Cl_avg(C)| > δ, то добавляем пиксель A к тому классу, отклонение от которого минимально.
      

Недостатком описанного алгоритма является высокие вычислительные затраты.

6.Компьютерная геометрия

6.1.Двумерные преобразования

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

Преобразования, как и компьютерную геометрию, разделяют на двумерные (или преобразования на плоскости) и трехмерные (или пространственные). Вначале рассмотрим преобразования на плоскости.

Для начала заметим, что точки на плоскости задаются с помощью двух ее координат. Таким образом, геометрически каждая точка задается значениями координат вектора относительно выбранной системы координат. Координаты точек можно рассматривать как элементы матрицы [x,y], т. е. в виде вектор-строки или вектор-столбца. Положением этих точек управляют путем преобразования матрицы.

Точки на плоскости xy можно перенести в новые позиции путем добавления к координатам этих точек констант переноса:

.

Таким образом, для перемещения точки на плоскости надо к матрице ее координат прибавить матрицу коэффициентов преобразования.

Рассмотрим результаты матричного умножения матрицы [x,y], определяющей точку Р, и матрицы преобразований 22 общего вида:

.

Проведем анализ полученных результатов, рассматривая x^* и y^* как преобразованные координаты. Для этого исследуем несколько частных случаев.

Рассмотрим случай, когда a = d = 1 и c = b = 0. Матрица преобразований приводит к матрице, идентичной исходной:

.

При этом изменений координат точки Р не происходит.

Если теперь d = 1, b = c = 0, a = const, то:

.

Как видно, это приводит к изменению масштаба в направлении х, так как х^*=ах. Следовательно, данное матричное преобразование эквивалентно перемещению исходной точки в направлении х.

Теперь положим b = c = 0, т. е.

.

В результате получаем изменение масштабов в направлениях x и y. Если a ≠ d, то перемещения вдоль осей неодинаковы. Если a = d >1, то имеет место увеличение масштаба координат точки Р. Если 0 < a=d <1, то будет иметь место уменьшение масштаба координат точки Р.

Если a или (и) d отрицательны, то происходит отображение координат точек. Рассмотрим это, положив b = c = 0; d = 1 и а = -1, тогда

.

Произошло отображение точки относительно оси у. В случае b = c = 0, a  = 1, d = -1, отображение происходит относительно оси х. Если b = c = 0, a = d < 0, то отображение будет происходить относительно начала координат.

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

Теперь рассмотрим случай, когда a = d = 1, а с = 0, т. е.

.

Координата х точки Р не изменяется, в то время как у^* линейно зависит от начальных координат. Этот эффект называется сдвигом. Аналогично, когда a = d = 1, b = 0, преобразование осуществляет сдвиг пропорционально координате у.

Заметим, что преобразование общего вида, примененное к началу координат, не приведет к изменению координат точки (0,0). Следовательно, начало координат инвариантно при общем преобразовании. Это ограничение преодолевается за счет использования однородных координат.

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

Преобразование единичного квадрата

Четыре вектора положения точек единичного квадрата с одним углом в начале координат записываются в виде



Применение общего матричного преобразования к единичному квадрату приводит к следующему:

.


Рис. 6.. Преобразования единичного квадрата

6.1.1.Однородные координаты

6.1.2.Двумерное вращение вокруг произвольной оси

6.2.Трехмерные преобразования

6.3.Проекции

6.4.Математическое описание плоских геометрических проекций

6.5.Изображение трехмерных объектов

7.Представление пространственных форм

7.1.Полигональные сетки

7.1.1.Явное задание многоугольников

7.1.2.Задание многоугольников с помощью указателей в список вершин

7.1.3.Явное задание ребер

8.Удаление невидимых линий и поверхностей

8.1.Классификация методов удаления невидимых линий и поверхностей

8.2.Алгоритм плавающего горизонта

8.3.Алгоритм Робертса

8.3.1.Определение нелицевых граней

8.3.2.Удаление невидимых ребер

8.4.Алгоритм, использующий z–буфер

8.5.Методы трассировки лучей

8.6.Алгоритмы, использующие список приоритетов

8.7.Алгоритм Ньюэла-Ньюэла-Санча для случая многоугольников

8.8.Алгоритм Варнока (Warnock)

8.9.Алгоритм Вейлера-Азертона (Weiler-Atherton)

9.Методы закраски

9.1.Диффузное отражение и рассеянный свет

9.2.Зеркальное отражение

9.3.Однотонная закраска полигональной сетки

9.4.Метод Гуро

9.5.Метод Фонга

9.6.Тени

9.7.Поверхности, пропускающие свет

9.8.Детализация поверхностей

9.8.1.Детализация цветом

9.8.2.Детализация фактурой

10.Библиотека OpenGL

10.1.Особенности использования OpenGL в Windows

10.2.Основные типы данных

10.3.Рисование геометрических объектов

10.3.1.Работа с буферами и задание цвета объектов

10.3.2.Задание графических примитивов

10.3.3.Рисование точек, линий и многоугольников

10.4.Преобразование объектов в пространстве

10.4.1.Преобразования в пространстве

10.4.2.Получение проекций

10.5.Задание моделей закрашивания

10.6.Освещение

10.7.Полупрозрачность. Использование α-канала

10.8.Наложение текстуры

11.Аппаратные средства машинной графики

11.1.Устройства ввода

11.2.Сканеры

11.3.Дигитайзеры

11.4.Цифровые фотокамеры

Литература

1. 
   Божко А. Н. Компьютерная графика : [учебное пособие для вузов] / А. Н. Божко, Д. М. Жук, В. Б. Маничев. – М: Изд-во МГТУ им. Н. Э. Баумана, 2007. – 392 с.
   
2. 
   Гринченко В.Т., Мацыпура В.Т., Снарский А.А. Введение в нелинейную динамику. Хаос и фракталы. - 2-е изд. Издательство: ЛКИ, 2007 г. — 264 с.
   
3. 
   Дегтярев В. М. Компьютерная геометрия и графика. – М: Академия 2010 г. 192 с.
   
4. 
   Краснов М. В. OpenGL. Графика в проектах Delphi. — СПб.: БХВ-Петербург, 2001. — 352 с.
   
5. 
   М. Домасев, С. Гнатюк. Цвет. Управление цветом, цветовые расчеты и измерения. – СПб: Питер 2009 г. 224 с.
   
6. 
   Никулин Е. А. Компьютерная геометрия и алгоритмы машинной графики. — СПб: БХВ-Петербург, 2003. — 560 с.
   
7. 
   Роджерс Д. Алгоритмические основы машинной графики: Пер. с англ. - М.: Мир, 1989. – 512 с.
   
8. 
   Роджерс Д., Адамс Дж. Математические основы машинной графики: Пер. с англ. – М.: Мир, 2001. – 604 с.
   
9. 
   Тихомиров Ю. Программирование трехмерной графики. – СПб: BHV – Санкт-Петербург, 1998. – 256 с.
   
10. 
    Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики: В 2-х кн., Кн. 1. / Пер. с англ. – М.: Мир, 1985 – 368 с.
    
11. 
    Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики: В 2-х кн., Кн. 2. / Пер. с англ. – М.: Мир, 1985 – 368 с.
    
12. 
    Шикин Е. В., Боресков А. В. Компьютерная графика. Полигональные модели. – М.: ДИАЛОГ-МИФИ, 2000. – 464 с.
    

Оглавление

Учебное издание
ДЁМИН Антон Юрьевич
К О М П Ь Ю Т Е Р Н А Я Г Р А Ф И К А

Учебное пособие
Научный редактор

доктор технических наук,

профессор В.К. Погребной
Редактор И.О. Фамилия
Верстка Л.А. Егорова
Отпечатано в Издательстве ТПУ в полном соответствии
с качеством предоставленного оригинал-макета

Подписано к печати Формат 60×84/16. Бумага «Снегурочка». Печать Xerox. Усл. печ. л. 3,02. Уч.-изд. л. 2,74. Заказ . Тираж экз.
	Национальный исследовательский Томский политехнический университет Система менеджмента качества Издательства Томского политехнического университета сертифицирована NATIONAL QUALITY ASSURANCE по стандарту BS EN ISO 9001:2008
. 634050, г. Томск, пр. Ленина, 30. Тел./факс: 8(3822)56-35-35, www.tpu.ru