Загальні вказівки

Методичні вказівки розроблені на базі курсів «Основи поліграфії» та «Інформатика». В основу тематики лабораторних робіт покладені сучасні науково-технічні та практичні досягнення в галузі цифрової обробки зображень.

Лабораторні роботи студенти виконують самостійно під керівництвом викладача та майстра виробничого навчання. За результатами виконання роботи студенти повинні підготувати письмовий звіт, який під час усного опитування необхідно захистити. Після виконання всіх лабораторних робіт та їх захисту студент отримує допуск до екзамену.

Кожна лабораторна робота складається з наступних етапів:

1. Ознайомлення з правилами техніки безпеки та промислової санітарії.

2. Підготовка робочого місця, устаткування, матеріалів та контрольно-вимірювальних приладів до роботи.

3. Виконання роботи у відповідності з методичними вказівками та вказівками викладача.

4. Обробка отриманих результатів та оформлення письмового звіту.

5. Захист лабораторної роботи.

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

1. Ющик О. Основи цифрової обробки зображень: Навчальний посібник. — Львів: УАД, 2005. — 180 С.

2. Прэтт У. К. Цифровая обработка изображений: В 2-х кн. / Пер. с англ. под ред. Д. С. Лебедева.— М.: Мир, 1982. — Кн. 1, Кн. 2. — 790 с.

3. Бабак В. П. та ін. Обробка сигналів: Підручник / В. П. Бабак, В. С. Хандецький, Е. Шрюфер. — К.: Либідь, 1996. 392 с.

4. Шлезингер М. И. Математические средства обработки изо­бражений. Киев, 1989.

5. Очин Е. Ф. Вычислительные системы обработки изображений. Л.: 1989.

6. Ярославский Л. П. Введение в цифровую обработку изображений. М.: 1979.

7. Роджерс Д. Ф., Адамс Дж. А. Математические основы машинной графики. М.: 1980.

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

Лабораторна робота № 1 Ознайомлення з алгоритмічними основами побудови елементарних зображень Основні положення

Цифрова обробка зображень (ЦОЗ) на сьогоднішній день є цілком сформованим самостійним науковим напрямком. Існує апаратне та програмне забезпечення для отримання різноманітних зображень від звичайних креслень до реалістичних обра­зів природних об’єктів.

В ході занять ми розглянемо деякі з питань програмного та алгоритмічного забезпечення ЦОЗ. Для розуміння матеріалу необхідні знання деяких розділів вищої математики та знайомство з будь-якою мовою програмування високого рівня.

Існує два способи представлення алгоритмів: перший з них — це детальний опис алгоритму в словесній формі, а другий — більш формальний — базується на алгоритмічній мові. Вибір мови викликає певні труднощі.

Будемо розглядати детальний опис алгоритмів на так званому псевдокоді, який легко перекладається на будь-яку конкретну мову програмування.

Елементи псевдокоду взяті з декількох відомих мов програмування. Коментарі оформляються у вигляді окремих абзаців.

Всі константи вважаються десятковими числами. Наприклад, 9, 3, 6.732, 1109, 5.83 є константами.

Змінна — це ім’я, яке використовується для зберігання значення, яке може змінюватись. Довгі імена змінних починаються з великої букви, решта букв в імені малі. Однолітерні імена можуть бути як малими так і великими буквами. Для більшої наочності можуть використовуватись літери з індексами, наприклад, Flag, P₂, x, y.

Масиви — це ім’я для індексованої сукупності величин. Для імен масивів діють ті ж домовленості, що і для змінних. Звернення до всього масиву здійснюється по його імені, а до індивідуальних елементів по імені масиву, за яким в дужках іде список індексів. Наприклад: Window, Window (1, 3).

Знак := використовується для присвоєння змінній, розташованій в лівій частині оператора, значення виразу з правої частини.

Звичайні арифметичні операції: множення, ділення, додавання і віднімання позначаються знаками «», «/», «+», «-».

Логічні операції and та or необхідно виділяти. Операції співвідношення дорівнює, не дорівнює, менше, більше, менше або дорівнює, більше або дорівнює позначаються знаками =, ≠, <, >, ≤, і ≥ відповідно. Ці операції використовуються для перевіряння умов. Результатом перевіряння є логічне значення «істина» або «фальш».

Оператор finish використовується для позначення кінця роботи алгоритму.

Оператори, розташовані всередині блоку while-endwhile, циклічно виконуються доти, доки істинною є деяка умова. Значення умови перевіряється на початку блоку. Коли умова перестає бути істинною, виконання програми продовжується з оператора, наступного за endwhile.

Загальна форма оператора:

while (умова)

[оператори]

endwhile

Наприклад:

while

endwhile

finish

Оператор if-then використовується для вибору в залежності від істинності деякої умови для зміни послідовності виконання програми або для присвоєння змінній іншого значення.

Якщо аргументом then є номер оператора і умова є істинною, то управління передається на оператор з цим номером. В іншому випадку виконується наступний за порядком оператор. Номери операторів є їхніми мітками.

Якщо аргументом then служить оператор присвоювання і умова є істинною, то присвоювання виконується. В іншому випадку присвоювання не виконується, а управління передається відразу на наступний оператор. Загальна форма оператора наступна:

if (умова) then (номер оператора)

if (умова) then оператор присвоювання

Наприклад:

if then 3

if then

Оператор if-then-else використовується для вибору в залежності від істинності деякої умови одного з двох блоків операторів. Для позначення кінця блоку оператора if-then-else використовується оператор endif. В цьому операторі не виконується ніякого повторення, а виконується один з двох блоків. Після цього виконання програми продовжується з оператора, який іде за endif. Загальна форма оператора:

if (умова) then

[оператори, які виконуються, якщо умова є істинною]

else

[оператори, які виконуються, якщо умова є фальшивою]

endif

Наприклад:

if then

x := x + 1

else

x := x - 1

endif

Якщо оператор if-then-else записується на одному рядку, то оператор endif опускається.

Якщо else опускається разом з групою операторів, то отримуємо блочний оператор.

Циклічне управління можна реалізувати за допомогою оператора for-next аналогічно оператору while. Циклічне виконання операторів, розташованих всередині тіла циклу for-next, здійснюється доти, доки значення змінної циклу знаходиться в заданих межах.

Загальна форма оператора:

for (зм_циклу) = (поч_знач) to (кінц_знач) step (крок_циклу)

[оператори, які необхідно виконати]

next (зм_циклу)

Якщо крок_циклу відсутній, то він дорівнює одиниці. Допускається від’ємне значення кроку. Початковим, кінцевим значенням та кроком циклу можуть бути змінні.

Наприклад:

for to n step a

next x

Оператор go to викликає безумовний перехід на оператор, який задається аргументом. Загальна форма оператора така:

go to (номер оператора)

Номери операторів є мітками.

Підпрограма — це окремий програмний модуль, який викликається за допомогою оператора call. Початок підпрограми визначається оператором subroutine. Вихід з підпрограмного модуля позначається оператором return. Після виходу з підпрограми управління передається на наступний за оператором call оператор викликаючої програми. Оператор subroutine містить список вхідних та вихідних змінних. Зв’язок між викликаючою програмою та підпрограмою здійснюється тільки через ці змінні, всі інші змінні в підпрограмному модулі є локальними. Загальна форма операторів call, subroutine та return така:

call ім’я (вх. змінні; вих. змінні)

subroutine ім’я (вх. змінні; вих. змінні)

return

Списки вхідних і вихідних змінних для операторів call і subroutine розділяються крапкою з комою і повинні відповідати один одному. Перша буква імені підпрограми — велика, всі інші — малі.

В алгоритмах визначаються різноманітні функції. Всі функції починаються з малої букви. Наприклад: max (x₁, y₁).

В ЦОЗ фундаментальною зв’язуючою ланкою є зображення; отже ми розглянемо, як:

1. зображення представляються в комп’ютері;

2. зображення готуються для візуалізації;

3. попередньо підготовлені зображення малюються;

4. здійснюється взаємодія з зображенням.

В багатьох алгоритмах геометричними даними, які описують зображення, є багатокутники та ребра. Але кожен багатокутник або ребро в свою чергу може бути представлений своїми вершинами, Отже, точки є фундаментальними будівельними блоками для представлення геометричних даних. Тому заслуговує уваги алгоритм, який показує, як організувати точки.

Розглянемо для ілюстрації одиничний квадрат в першому квадранті (рис. 1.1). Він може бути представлений своїми вершинами

Рис.1.1. Зображення одиничного квадрату в першому квадранті

Відповідний алгоритмічний опис буде виглядати наступним чином:

З’єднати послідовно

Одиничний квадрат можна отримати за допомогою чотирьох ребер

Тоді алгоритмічний опис буде таким

Зобразити послідовно ребра

А для опису одиничного квадрату як багатокутника можна використати або точки, або ребра. Наприклад:

або або

Основні будівельні блоки (точки) в залежності від розмірності простору можна представляти або як пари, або як трійки чисел. Таким чином, або представили би точку в двовимірному або тривимірному просторі. Дві точки представили б відрізок або ребро, а сукупність з трьох або більше точок багатокутник. Ці точки, ребра, багатокутники накопичуються в базі даних.

Дані, з яких отримують малюнок, рідко співпадають з даними, які служать безпосередньо для малювання, бо над ними проводять трансформування (поворот), перенос, масштабування і т.п. Дані, які використовують для виводу зображення, називаються дисплейним файлом.

Порядок виконання роботи

Устаткування, матеріали та програмне забезпечення

Контрольні запитання

Література:

Лабораторна робота № 2

Алгоритми креслення відрізків растровими графічними пристроями

Основні положення

Для роботи з пристроями растрової графіки потрібні спеці­альні методи генерації зображення, викреслювання прямих та кривих ліній, замальовування багатокутників, яке створює враження суцільних об’єктів. Розглянемо алгоритми викреслю­вання відрізків.

Оскільки екран растрового дисплею є матрицею дискретних елементів (пікселів), кожен з яких може бути підсвіченим, то неможливо безпосередньо провести відрізок з однієї точки в іншу.

Процес визначення пікселів, які найкращим чином апроксимують заданий відрізок, називається розкладанням в растр.

У поєднанні з процесом порядкової візуалізації зображення він є відомим як перетворення растрової розгортки.

Для горизонтальних, вертикальних і нахилених під кутом 45 відрізків вибір растрових елементів є очевидним. При будь-якій іншій орієнтації вибрати потрібні піксели складніше, що показано на рис. 2.1.

Рис. 2.1. Розкладення в растр відрізків прямих

Перш ніж розглядати конкретні алгоритми малювання відрізків, розглянемо загальні вимоги до таких алгоритмів:

1. відрізки повинні виглядати прямими і закінчуватись в заданих точках;

2. яскравість вздовж відрізка повинна бути постійною і не залежати від довжини та нахилу;

3. малювати потрібно з максимально можливою швидкістю.

Не всі вимоги можуть бути повністю задоволеними, оскільки растровий дисплей виключає генерування абсолютно прямих ліній та точне співпадіння початку та кінця відрізка з заданими точками. Але при достатньо високій роздільній здатності мож­на отримати прийнятну апроксимацію.

Постійна яскравість вздовж відрізка досягається лише при проведенні горизонтальних, вертикальних та нахилених під кутом 45 прямих. Для інших орієнтацій розклад в растр приве­де до нерівномірної яскравості і вертикальні та горизонтальні відрізки будуть яскравішими за нахилені. Забезпечення однакової яскравості вздовж відрізків різних довжин та орієнтацій вимагає обчислення кореня квадратного, що сповільнює обчи­слення. Компромісом є знаходження наближеної довжини від­різка, скорочення обчислень до мінімуму, використання ціло­чисельної арифметики або реалізація алгоритмів на апаратному або мікропрограмному рівні.

В більшості випадків для викреслювання відрізків для спрощення обчислень використовується покроковий метод. Наведемо приклад подібного алгоритму:

Простий покроковий алгоритм

1 if точність then 4

if then 2

if then 3

2

go to 1

3

go to 1

4 finish

Застосуємо такий покроковий метод в простому алгоритмі розкладення відрізка в растр на основі цифрового диференційного аналізатора.

Один з методів розкладу відрізка в растр полягає в розв’язанні диференційного рівняння, яке описує цей процес. Для прямої лінії маємо

або

Розв’язком його буде

де та  — кінці відрізку, який підлягає розкладу, а — початкове значення для наступного кроку вздовж відрізку.

Фактично рівняння є рекурентним співвідношенням для послідовних значень y вздовж потрібного відрізку. Цей метод називається цифровим диференційним аналізатором (ЦДА). В простому ЦДА або , або (більше з приростів) вибирається за одиницю растру. Припускаємо також, що кінці відрізку та не співпадають. Нижче представимо простий алгоритм, який працює у всіх квадрантах:

Будемо використовувати також такі функції:

integer — функція перетворення дійсного числа в ціле, наприклад Integer (–8, 5) = –9, а не –8.

sign — функція, яка приймає значення –1, 0, 1 для від’ємного, нульового та додатного аргументу відповідно.

Процедура розкладу в растр відрізку по методу цифрового диференційного аналізатора

апроксимуємо довжину відрізку

if then

Довжина :=

else

Довжина :=

endif

вважаємо більший з приростів або рівним одиниці растру

заокруглюємо величини, а не відкидаємо дробову частину

використання знакової функції робить алгоритм придатним для всіх квадрантів

початок основного циклу

while

Plot (integer (x), integer (y))

end while

finish

Наведемо приклад, який ілюструє роботу алгоритму.

Розглянемо відрізок з точки (0, 0) в точку (5, 5).

Результати роботи алгоритму такі:

початкові установки

результати покрокового виконання основного циклу

i	Plot	x	y
		0,5	0,5
1	(0, 0)
		1,5	1,5
2	(1, 1)
		2,5	2,5
3	(2, 2)
		3,5	3,5
4	(3, 3)
		4,5	4,5
5	(4, 4)
		5,5	5,5

Отримане растрове представлення відрізка виглядатиме наступним чином (рис. 2.2):

Рис. 2.2. Результати роботи простого ЦДА в першому квадранті

Зазначимо, що кінцеві точки визначені точно і вибрані пікселі рівномірно розподілені вздовж відрізка. Зовнішній вигляд прямої є задовільним. Але якщо початкове значення змінної i зробити 0 замість 1, то буде активованим піксель з координатами (5, 5), що є небажаним. Якщо адрес пікселя задано цілими координатами лівого нижнього кута, то активація цього пікселя дасть неправильну кінцеву точку відрізку.

Крім цього, при викреслюванні серії послідовних відрізків, піксель (5, 5) буде активованим двічі: в кінці даного відрізку і на початку наступного. Такий піксель може виглядати як більш яскравий або мати інший колір.

Розглянемо ще один приклад:

Розглянемо відрізок з точки (0, 0) в точку (-8, -4)

Результати роботи алгоритму такі:

початкові установки

результати покрокового виконання основного циклу, враховуючи припущення, що використовується функція заокруглення, є наступними:

i	Plot	x	y
		–0,5	–0,5
1	(–1, –1)
		–1,5	–1
2	(–2, –1)
		–2,5	–1,5
3	(–3, –2)
		–3,5	–2
4	(–4, –2)
		–4,5	–2,5
5	(–5, –3)
		–5,5	–3
6	(–6, –3)
		–6,5	–3,5
7	(–7, –4)
		–7,5	–4
8	(–8, –4)
		–8,5	–4,5

Отримане растрове представлення відрізка виглядатиме на­ступним чином:

Порядок виконання роботи

Устаткування, матеріали та програмне забезпечення

Контрольні запитання

Література:

Лабораторна робота № 3

Алгоритми БРЕЗЕНХЕМА креслення відрізків растровими графічними пристроями

Основні положення

Попередньо розглянуті алгоритми дають розклад в растр відрізку який лежить по один бік від реального і на одному з кінців відрізку з’являється зайва точка, тобто результат роботи алгоритмів залежить від орієнтації. Крім цього вони використовують дійсну арифметику, що суттєво сповільнює роботу.

Тому американським вченим Брезенхемом був розроблений алгоритм розкладу відрізків в растр позбавлений цих недоліків.

Початково він розроблявся для цифрових плоттерів, а потім він був розповсюджений і на більшість РСП. Алгоритм вибирає оптимальні растрові координати для представлення відрізка. В процесі роботи 1 з координат — або х, або у (залежно від кутового коефіцієнту) змінити на 1. Зміна 2-ї координати (або на 0 або на 1) залежить від відстані між дійсним положенням відрізку і найближчими координатами сітки. Таку відстань будемо називати похибкою.

Алгоритм побудовано так, що необхідно перевіряти лише знак цієї похибки. На рис. 3.1 це проілюстровано для відрізка в першому октанті, тобто для відрізку з кутовим коефіцієнтом, який лежить в діапазоні від 0 до 1. З рисунка можна зауважити, що якщо кутовий коефіцієнт відрізка з точки (0, 0) більший за 1/2, то його перетин з прямою буде розташованим ближче до прямої , ніж до прямої . Отже, точка растру (1, 1) краще апроксимує хід відрізку ніж точка (1, 0). Якщо кутовий коефіцієнт менший 1/2, то справедливим є обернене. Для кутового коефіцієнту рівного 1/2 немає якогось переважаючого вибору. В даному випадку алгоритм вибирає точку (1, 1).

Не всі відрізки проходять через точки растру. Така ситуація ілюструється рисунком 3.2, де відрізок з тангенсом меншим нахилу 3/8 спочатку проходить через точку растру (0,0) і послідовно перетинає 3 піксели. На нижньому графіку представлено обчислення похибки при представленні відрізку дискретними пікселями. Оскільки бажано перевіряти тільки знак похибки, то вона початково встановлюється рівною –1/2.

Ініціалізувати похибку в –
Рис. 3.1. Основна ідея алгоритму Брезенхема

Рис. 3.2. Графік похибки в алгоритмі Брезенхема.

Таким чином, якщо кутовий коефіцієнт відрізка більший або рівний 1/2, то величина похибки в наступній точці растру з координатами (1, 0) може бути обчислена, як

де m — кутовий коефіцієнт. В нашому випадку при початковому значенні похибки –1/2

Оскільки е від’ємне, відрізок пройде нижче середини піксела. Отже, піксель на тому ж горизонтальному рівні краще апроксимує положення відрізку, тому y не збільшується. Аналогічно обчислюємо похибку

в наступній точці растру (2, 0). Тепер е додатне, а значить відрізок пройде вище середньої точки. Растровий елемент (2, 1) з наступною по величині координатою y краще апроксимує положення відрізка. Отже, y збільшується на 1. Перш ніж роз­глядати наступний піксель, необхідно відкоригувати похибку відніманням з неї одиниці. Маємо

Зазначимо, що перетин вертикальної прямої з заданим відрізком лежить на 1/4 нижче прямої . Якщо ж перенести відрізок 1/2 вниз, то ми отримаємо якраз величину –3/4. Продовження обчислень для наступного піксела дає

Оскільки е від’ємне, то y не збільшиться. З усього вищесказаного випливає, що похибка — це інтервал, який відтинається по осі y, відрізком, що розглядається в кожному растровому елементі (відносно –1/2).

Наведемо алгоритм Брезенхема для 1-го октанту, тобто для випадку :

Алгоритм Брезенхема розкладу в растр відрізка для першого октанту

припускаємо, що кінці відрізка та не співпадають

integer — функція перетворення в ціле

— цілі

e — дійсне

ініціалізація змінних

ініціалізація е з поправкою на половину піксела

початок основного циклу

for i = 1 to x

Plot (x, y)

while (e  0)

endwhile

next i

finish

Блок-схема алгоритму наведена на рис. 3.3.

Рис. 3.3. Блок-схема алгоритму Брезенхема

Приклад 1

Розглянемо відрізок, проведений з точки (0, 0) в точку (5, 5). Розкладання відрізка в растр по алгоритму Брезенхема приводить до наступного результату:

початкові установки

Результати покрокового виконання основного циклу

i	Plot	e	x	y
			0	0
1	(0, 0)
			0	1
			1	1
2	(1, 1)
			1	2
			2	2
3	(2, 2)
			2	3
			3	3
4	(3, 3)
			3	4
			4	4
5	(4, 4)
			4	5
			5	5

Результат показано на рис. 3.4 і він співпадає з очікуваним.

Рис.3.4. Результат роботи алгоритму Брезенхема в першому октанті

Зазначимо, що точка растру з координатами (5, 5) не активована. Її можна активувати зміною умов циклу for-next на 0 to x. Активацію точки (0, 0) можна ліквідувати, якщо поставити оператор Plot безпосередньо перед рядком next i.

Алгоритм Брезенхема розглянутий нами вимагає використання арифметики з плаваючою точкою і ділення (для обґрунтування кутового коефіцієнту і оцінки похибки). Швидкодію алгоритму можна збільшити, якщо використовувати тільки ці­лочисельну арифметику і виключити ділення. Оскільки важливим є тільки знак похибки, то просте перетворення

перетворить попередній алгоритм в цілочисельний і дозволить реалізувати його на апаратному та мікропрограмному рівнях. Модифікований цілочисельний алгоритм для першого октанту, тобто для , виглядає наступним чином

Цілочисельний алгоритм Брезенхема розкладу в растр відрізка для першого октанту

передбачається, що кінці відрізку і не співпадають і всі змінні — цілі

ініціалізуємо з поправкою на половину піксела

початок основного циклу

for i = 1 to x

Plot (x, y)

while

end while

Щоб реалізація алгоритму Брезенхема була повною, необхідно обробляти відрізки у всіх октантах. Модифікацію легко зро­бити, враховуючи в алгоритмі номер квадранту, в якому лежить відрізок і його кутовий коефіцієнт. Коли абсолютна величина кутового коефіцієнту більша 1, y постійно змінюється на 1, а критерій похибки Брезенхема використовується для прийняття рішення про зміну величини x. Вибір постійно змінюваної (на 1 або -1) координати залежить від квадранту (рис. 3.5).

Рис. 3.5. Розгляд випадків для узагальненого алгоритму Брезенхема

Загальний цілочисельний алгоритм Брезенхема для всіх квадрантів виглядає наступним чином:

передбачається, що кінці відрізку і не співпадають і всі змінні вважаються цілими

функція sign повертає –1, 0, 1 для від’ємного, нульового і додатного аргументу відповідно

ініціалізація змінних

обмін значень x і y залежить від кутового коефіцієнту нахилу відрізку

if then

else

end if

ініціалізація з поправкою на половину піксела

основний цикл

for to x

Plot (x, y)

while

if then

else

end if

end while

if then

else

end if

next i

finish

Приклад 2

Розглянемо відрізок з точки (0, 0) в точку (–8, –4).

початкові установки

покрокове виконання основного циклу

Блок-схема алгоритму наведена на рис. 3.6.

Рис. 3.3. Блок-схема цілочисельного алгоритму Брезенхема для всіх квадрантів

i	Plot	e	x	y
		0	0	0
1	(0, 0)
		–16	0	–1
		–8	–1	–1
2	(–1, –1)
		0	–2	–1
3	(–2, –1)
		–16	–2	–2
		–8	–3	–2
4	(–3, –2)
		0	–4	–2
5	(–4, –2)
		–16	–4	–3
		–8	–5	–3
6	(–5, –3)
		0	–6	–3
7	(–6, –3)
		–16	–6	–4
		–8	–7	–4
8	(–7, –4)
		0	–8	–4

На рис.3.7 продемонстровано результат. Порівняння з останнім рисунком попередньої лабораторної роботи показує, що результати роботи двох алгоритмів відрізняються.

Рис.3.7. Результат роботи узагальненого алгоритму Брезенхема в третьому квадранті

Порядок виконання роботи

Устаткування, матеріали та програмне забезпечення

Контрольні запитання

Література:

Лабораторна робота № 4

Алгоритм Брезенхема для генерування растрового кола

Основні положення

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

Для початку відзначимо, що необхідно згенерувати тільки 1/8 частину кола. Решта його частин можуть бути отримані послідовними відображеннями, як це показано на рис.4.1.

Рис. 4.1. Генерування повного кола з дуги в першому октанті

Зобразимо генерування повного кола з дуги в першому октанті графічно.

Якщо згенерувати перший октант (від 0 до 45 проти годинни­кової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої , що дає в цілому перший квадрант.

Перший квадрант відображається відносно прямої для отримання відповідної частини кола в другому квадранті. Верхнє напівколо відображається відносно прямої y=x для закінчення побудови. На рисунку 4.1 зображені двовимірні матриці відповідних перетворень.

Для виводу алгоритму розглянемо першу чверть кола з центром в початку координат. Відзначимо, що якщо робота алгоритму починається в точці , , то при генеруванні кола за годинниковою стрілкою в першому квадранті y є монотонно спадаючою функцією аргументу x (рис. 4.2).

Рис.4.2. Коло в першому квадранті	Рис. 4.3. Вибір пікселів в першому квадранті

Аналогічно, якщо початковою точкою є , , то при генеруванні кола проти годинникової стрілки x буде монотонно спадаючою функцією аргументу y. Вибираємо генерування за годинниковою стрілкою з початком в точці , . Передбачається, що центр кола і початкова точка знаходяться точно в точках растру. Для будь-якої заданої точки на колі при генеруванні за годинниковою стрілкою існує тільки три можливості вибрати наступний піксель, який найкращим чином наближається до кола: горизонтальний направо, по діагоналі вниз і вправо, вертикальний вниз.

На рис. 4.3 ці напрями позначаються відповідно , та . Алгоритм вибирає піксель, для котрого мінімальним є квадрат відстані між одним з цих пікселів та колом, тобто мінімум з¹

Обчислення можна спростити, якщо зауважити, що в околиці точки можливі тільки п’ять типів перетинів кола та сітки растру, які наведені на рис. 4.4.

Рис. 4.4. Перетин кола та сітки растру

Різниця між квадратами відстаней від центру кола до діагоналей піксела та від центру до точки на колі дорівнює

Як і в алгоритмі Брезенхема для відрізка, для вибору відповідного піксела бажано використовувати тільки знак похибки, а не її величину.

При діагональна точка знаходиться в середині реального кола, тобто це випадки 1 або 2 на рис. 4.4. Ясно, що в цій ситуації треба вибрати або піксель , тобто , або піксель , тобто . Для цього спочатку розглянемо випадок 1 і перевіримо різницю квадратів відстаней від кола до пікселів в горизонтальному і діагональному напрямках:

При відстань від кола до діагонального піксела є більшою, ніж до горизонтального . Навпаки, якщо , то відстань до горизонтального піксела є більшою. Таким чином

при вибираємо в

при вибираємо в

При , коли відстань від кола до обох пікселів однакова, вибираємо горизонтальний крок.

Кількість обчислень, яка необхідна для оцінки величини , можна скоротити, якщо зауважити, що у випадку 1

оскільки діагональний піксель завжди лежить всередині кола, а горизонтальний  — поза ним. Отже, можна обчислити за формулою

Доповнення до повного квадрату члена за допомогою додавання та віднімання дає

В квадратних дужках стоїть за означенням і його підставляння

суттєво спрощує вираз.

Розглянемо випадок 2 на рис. 4.4 і зауважимо, що тут повинен бути вибраний горизонтальний піксель , оскільки y є монотонно спадаючою функцією. Перевіряння компонентів показує, що

оскільки у випадку 2 горизонтальний та діагональний піксели лежать всередині кола. Отже, , і при використанні того самого критерію, що і у випадку 1, вибирається піксель .

Якщо , то діагональна точка знаходиться поза колом, тобто це випадки 3 і 4 на рис. 4.4. В даній ситуації ясно, що повинен бути вибраний або піксель , тобто , або , тобто . Аналогічно розгляду попереднього випадку критерій вибору можна отримати, розглядаючи спочатку випадок 3 та перевіряючи різницю між квадратами відстаней від кола до діагонального та вертикального пікселів, тобто

При відстань від кола до вертикального піксела є більшою і необхідно вибрати діагональний крок , до піксела . Навпаки у випадку відстань від кола до діагонального піксела є більшою і необхідно вибрати вертикальний рух до піксела . Таким чином,

при вибираємо в

при вибираємо в

Тут у випадку , тобто коли відстані є рівними, вибирається діагональний крок.

Перевірка компонент показує, що

оскільки для випадку 3 діагональний піксель знаходиться поза колом, тоді як вертикальний піксель лежить всередині нього. Це дозволяє записати у вигляді

Доповнення до повного квадрату члена з допомогою додавання і віднімання дає

Використання визначення приводить вираз до вигляду

Тепер, розглядаючи випадок 4 знову зауважимо, що необхідно вибрати вертикальний піксель , оскільки y є монотонно спадаючою функцією при зростанні x.

Перевірка компонент для випадку 4 показує, що

оскільки обидва піксели знаходяться поза колом. Отже, і при використанні критерію, розробленого для випадку 3, відбувається правильний вибір .

Залишилось перевірити тільки випадок 5 на рис. 4.4, який зустрічається коли діагональний піксел лежить на колі, тобто . Перевірка компонент показує, що

Отже, і вибирається діагональний піксель . Аналогічним чином оцінюємо компоненти:

і , що є умовою вибору правильного діагонального кроку до . Таким чином, випадок підпадає під той же критерій, що і випадок або .

Підведемо підсумок отриманих результатів:

вибираємо піксель

вибираємо піксель

вибираємо піксель

вибираємо піксель

вибираємо піксель

Легко розробити прості рекурентні співвідношення для реалізації покрокового алгоритму. Спочатку розглянемо горизонтальний крок до піксела . Позначимо це нове положення піксель як . Тоді координати нового піксела і значення дорівнюють

Аналогічно координати нового піксела і значення для кроку до піксела є наступними:

Те саме для кроку до

Реалізація алгоритму Брезенхема на псевдокоді для кола наведена нижче.

Покроковий алгоритм Брезенхема для генерування кола в першому квадранті

всі змінні — цілі

ініціалізація змінних

Рис. 4.5. Блок-схема покрокового алгоритму Брезенхема генерування кола в першому квадранті

Змінна межі встановлюється на нуль для закінчення роботи алгоритму на горизонтальній осі, в результаті генерується коло в першому квадранті. Якщо потрібен лише один з октантів, то другий октант можна отримати за допомогою встановлення , а перший — за допомогою відображення другого октанту відносно прямої (рис.4.1). Блок-схема алгоритму наведена на рис.4.5.

Приклад 4.1. Алгоритм Брезенхема для кола

Для ілюстрації роботи алгоритму генерування кола розглянемо коло радіусом 8 з центром в початку координат. Генерується тільки перший квадрант.

початкові установки

покрокове виконання основного циклу



Результати всіх послідовних проходів алгоритму зведені в таблицю. Список пікселів, вибраних алгоритмом, складається з (0, 8), (1, 8), (2, 8), (3, 7), (4, 7), (5, 6), (6, 5), (7, 4), (7, 3), (8, 2), (8, 1), (8, 0).

Plot				x	y
	-14			0	8
(0, 8)
	-11	-13		1	8
(1, 8)
	-6	-7		2	8
(2, 8)
	-12	3		3	7
(3, 7)
	-3	-11		4	7
(4, 7)
	-3	7		5	6
(5, 6)
	1	5		6	5
(6, 5)
	9		-11	7	4
(7, 4)
	4		3	7	3
(7, 3)
	18		-7	8	2
(8, 2)
	17		19	8	1
(8, 1)
	18		17	8	0
(8, 0)
	алгоритм завершено

Результати показано на рис.4.6 разом з реальним колом. Алгоритм легко узагальнюється для інших квадрантів або дуг кіл.

Радіус кола дорівнює 8 Підсвічені піксели 0 8 1 8 2 8 3 7 4 7 5 6 6 5 7 4 7 3 8 2 8 1 8 0

Рис. 4.6. Результати роботи покрокового алгоритму Брезенхема для генерування кола

Порядок виконання роботи

Устаткування, матеріали та програмне забезпечення

Контрольні запитання

Література:

Лабораторна робота № 5

РАСТРОВА РОЗГОРТКА ЯК СПОСІБ ГЕНЕРУВАННЯ ЗОБРАЖЕННЯ

Основні положення

Для виводу на відеомонітор розкладений у растр образ необхідно представити у вигляді того шаблона, який вимагає дисплей. Це перетворення називається растровим розгорненням. На відміну від дисплейного списку для векторного дисплея, що містить інформацію тільки про чи відрізки літерах, у даному випадку дисплейний список повинен містити інформацію про кожен піксель на екрані. Необхідно, крім того, щоб ця інформація організовувалася і виводилася зі швидкістю відеогенерації в порядку сканування рядків, тобто зверху вниз і ліворуч праворуч. Існує чотири способи досягнення такого результату — растрова розгортка в реальному часі, групове кодування, клітинна організація і пам’ять буфера кадру.