Затверджено
482.362.70915-2881 59-3 ЛЗ
МІНІСТЕРСТВООСВІТИ ТА НАУКИ УКРАЇНИ
ЧЕРНІВЕЦЬКИЙНАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
ІМЕНІЮРІЯ ФЕДЬКОВИЧА
Факультеткомп’ютерних наук
Кафедракомп’ютерних систем та мереж
ФОРМУВАННЯОБ’ЄМНИХ ЗОБРАЖЕНЬ НА ОСНОВІ ФОТОГРАФІЙ
(курсоваробота)
482.362.70915-28 81 59-3
Сторінок28
2008
Анотація
Пояснювальназаписка складається з основних розділів, які пов’язані з аналізом йобґрунтуванням теми дипломного проекту, призначенням і областю застосування,описом функціональних можливостей програми, вибором технічних і програмнихзасобів, організації вхідних та вихідних результатів, розглядом очікуванихтехніко – економічних показників та списком використаних джереллітератури при розробці програмного продукту.
Текст документускладається з 28 сторінок друкованого тексту та 6 рисунків.
Зміст
Вступ
1. Призначення та область застосування
2. Технічні характеристики
2.1. Постановка задачі на розробку програми
2.1.1 Класифікація моделей і методів візуалізації
2.1.2 Полігональні сітки
2.1.3 Воксельні моделі
2.1.4 Моделі, засновані на зображеннях
2.1.5 Точкове подання
2.1.6 Ієрархічні подання
2.2. Опис алгоритму і функціонування програми
2.3. Опис організації вхідних та вихідних даних
2.4. Опис організації вибору технічних і програмних засобів
3. Очікувані техніко – економічні показники
Список використаних джерел
Вступ
Назва: Формуванняоб’ємних зображень на основі фотографій.
Призначення:Дипломний проект затверджено на Вченій Раді факультету комп’ютерних наук Чернівецького національного університету імені Юрія Федьковича від 13 листопада2007 року протоколом №3 і призначений для формування об’ємних зображень наоснові фотографій. Дипломний проект полягає у написанні програмного продукту,що реалізує перетворення двомірного зображення у тривимірне.
/>/>1.Призначення та область застосування
В даний часпризначень та областей застосування програм, які орієнтовані на перетвореннязображень з плоского в об’ємне дуже багато. Їх застосовують:
— припроектуванні будівель (створення моделі будинку до його зведення);
— припроектуванні літаків та космічних апаратів (дозволяє виявити неполадки на етапірозробки та дає можливість випробувати розроблену модель);
— припроектуванні друкованих плат;
— при проведенніархеологічних розкопок (дає можливість видворити модель об’єкта по їїчастинам);
— при роботі занімацією (створення об’ємних зображень з малюнків);
— при створеннікомп’ютерних ігор.
Для перетвореннязображень існують такі програми:
1. 3D Studio Max– компоненти цієї програми дозволяють проводити візуалізацію зображення.
До перевагпрограми можна віднести: якість створеного об’ємного зображення; дозволяютьвикористовувати фільтри покращення зображення.
До недоліківпрограми можна віднести: потребує додаткового знання програми; велика ціна запрограму; низька швидкість обробки зображення; складність реалізації алгоритмупрограми; потребує встановлення на комп’ютер додаткових компонентів;ресурсозалежна (потребує комп’ютер з великими обчислювальними можливостями).
2. Maya – ця програмає аналогом попереднього продукту.
Переваги танедоліки програми такі, як і в попередній.
3. AutoCAD –компоненти цієї програми дозволяють створювати об’ємні зображення з креслень.
До перевагпрограми можна віднести: точність створеного зображення; швидкість створення;не являється ресурсозалежною.
До недоліківпрограми можна віднести: потребує додаткового вивчення програми; ціна запрограму, наявність малої кількості текстур; необхідність встановлення вопераційну систему; складність реалізації алгоритму програми.
4. RealvizImageModeler – ця програма орієнтована на створення об’ємних зображень зфотографії.
До перевагпрограми можна віднести: можливість відтворення з фотографії складних об’єктів,не являється ресурсозалежною.
До недоліківпрограми можна віднести: потребує додаткового знання програми; велика вартістьпрограмного продукту; швидкість аналізу зображення; складність реалізаціїалгоритму програми, якість отриманого зображення посередня.
5. StitcherUnlimited – ця програма є аналогом попередньої.
Переваги танедоліки даної програми такі, як і в попередній.
6. ImageSkulpturer — ця програма орієнтована на створення об’ємних зображень зфотографії.
До перевагпрограми можна віднести: простота інтерфейсу; відтворює складні зображення;потребує невелику кількість вхідних параметрів фотографії; якість відтвореногозображення; ресурсонезалежна.
До недоліківпрограми можна віднести: ціна за програму; складний алгоритм програми.
Розробленийпрограмний продукт, що орієнтований на перетворення двомірного зображення утривимірне має великий спектр призначення, а саме:
1. Пришвидшитиперетворення плоского зображення у об’ємне.
2. Перетворюватиструктури зображення разом з її текстурою.
3. Призначаєтьсядля огляду зображення під різними кутами.
4. Призначенийдля огляду об’єкту з різних відстаней.
4. Програмнийпродукт може зберігати зображення під час огляду його з різних сторін.
Перевагиствореної програми: безкоштовність; інтуїтивно простий інтерфейс; швидкістьобробки зображення; простота реалізації.
Недолікиствореної програми: обмеженість вихідних форматів зображення (тільки bmp);неможливість відтворення складних об’єктів, потреба у правильному освітленнімалюнку.
/>/>2.Технічні характеристики
2.1 Постановка задачі на розробку програми
В дипломномупроекті поставлена задача створити програмний продукт, який орієнтовано нароботу з зображенням. А саме, перетворення двомірного зображення у тривимірне,можливість його огляду з різних сторін та збереження зображення під іншим кутомогляду. Також задача програми демонструвати студентам стадії формуваннятривимірного зображення
2.1.1 Класифікація моделей і методів візуалізації
На даний часвідоме досить велике кількість різних методів подання тривимірних об'єктів іпов'язаних з ними методів візуалізації, у тому числі багатомасштабних. Всіподання можна розділити на кілька класів, що володіють характернимивластивостями:
Поверхневі /об'ємні.
Зв'язані /дискретні.
Явні /параметричні.
Поверхневі моделіописують тільки поверхню об’єкта в тривимірному просторі. На противагу їм,об'ємні (воксельні) структури дозволяють задавати моделі, як частинутривимірного простору, розбитого деяким чином на осередки, які вважаютьсязаповненими, якщо вони містять частину об’єкта, і порожніми – у противномувипадку.
Зв'язані моделіявно або неявно містять інформацію про безперервні ділянки поверхонь моделей,тоді як дискретні подання описують тільки наближення поверхні об’єкта.
Явне завданнямоделей припускає, що опис моделі об’єкта в даному поданні доступно в явнійформі, а параметричне – що для його одержання необхідно додатково обчислюватидеяку функцію, яка залежить від параметру.
Методи візуалізаціїможна умовно розділити на проекційні методи й методи трасування променів.
Проекційні методи- це методи, у яких синтез зображення виконується за допомогою афіннихперетворень і перетворень проекції. Тривимірна сцена як набір примітивіввізуалізації (звичайно, багатокутників, точок, ліній тощо) трансформується удвомірний масив, що і відображається на екрані монітора.
Методи трасуванняпроменів працюють на рівні пікселів вихідного зображення, розраховуючи їхнікольори на основі даних про геометрію сцени і положення віртуальної камери.
Сьогодніінтерактивну швидкість синтезу зображень надають тільки проекційні методи,часто за підтримкою апаратного забезпечення. Надалі в роботі розглядаютьсятільки такі методи, які в свою чергу накладають деякі обмеження на можливіподання об'єктів. Характерною рисою поставленого завдання є робота з реальнимиданим, тобто даними, введеними в комп'ютер за допомогою пристроїв дистанційногосканування. Такі дані, в більшості випадків, дискретні й задані явно, звичайноу вигляді набору точок або набору карт глибини. Крім того, за виняткомтомографів (цей випадок у роботі не розглядається), що одержують внутрішнюструктуру об’єкта, всі сканери працюють тільки з поверхнею об’єкта. Такимчином, подання повинне гарно описувати явно задані дискретні поверхні.
Проведемо аналізрізних подань із метою виявлення придатності їхнього використання для рішенняпоставленого завдання. У тексті не розглядаються різні параметричні йпроцедурні подання тому, що їх особливості (складність обчислень, відсутністьапаратної підтримки) роблять складним використання цих подань для моделюванняреальних об'єктів.
2.1.2 Полігональні сітки
Полігональнісітки є на даний момент найпоширенішим поданням, для якого створене велика кількістьпрограмного забезпечення, що дозволяє редагувати, передавати по мережі йвідображати моделі з використанням апаратної підтримки.
Характерною рисоюполігональних сіток є підтримка зв’язності моделі. У силу цього полігональніподання добре пристосовані для опису великої кількості синтетичних поверхонь.
Однак,відскановані дані, споконвічно не містять інформації про зв’язність йбезперервність поверхонь, а являють собою набір близько розташованих часток(sample). Такі обмеження випливають із пристрою скануючого механізму, що маєдискретний крок кінцевого розширення.
Отже, длявикористання полігональних моделей зв’язність повинна бути введена штучно наетапі препроцесуванні. Таким чином, полігональні моделі не призначені дляпрямої роботи з від сканованими даними, тому що вимагають відновлення поверхні,що в загальному випадку є нетривіальним завданням і сильно залежить від класуоброблюваних об'єктів. При цьому відновлена поверхня не обов'язково будевикористовуватися на етапі візуалізації (наприклад, якщо модель такоїскладності, що проекція трикутника на екран при типовій проекції перегляду близькапо площі з одним пікселем).
З іншого боку,створена велика кількість методів, що дозволяють досить ефективно перетворюватидискретні від скановані дані в полігональні сітки. Більше того, сучаснеустаткування високого класу дозволяє виконувати перетворення в сітку апаратно[1].
Набагатоскладніше ситуація з поданням великих обсягів даних і підтримкою різних рівнівдеталізації. Структура полігональних сіток лінійна й вони не забезпечують «природної»підтримки багатомасштабності. Тому робота з великими сітками ускладнена іпотребує різних, найчастіше обчислювально складних методів спрощення. Булостворено безліч алгоритмів для створення багатомасштабних подань на основісіток, що мають безпосереднє відношення до поставленого завдання.
Практично всітехнології спрощення сіток використовують деякі варіації або комбінаціїнаступних механізмів: семплюваня (sampling), проріджування (decimation),адаптивної розбивки (adaptive subdivision) і злиття вершин (vertex merging)[2].
Алгоритми семплюваняспрощують первісну геометрію моделі, використовуючи або підмножину вихіднихточок, або перетинання вокселів з моделлю на тривимірній сітці. Такі алгоритминайкраще працюють на гладких поверхнях без гострих кутів.
Алгоритми, щовикористовують адаптивну розбивку, знаходять просту базову (base) сітку, щопотім рекурсивно розбивається для апроксимації первісної моделі. Такий підхідпрацює добре, коли знайти базову модель відносно просто. Наприклад, базовамодель для ділянки ландшафту звичайно прямокутник. Для досягнення гарнихрезультатів на довільних моделях потрібне створення базової моделі, що відбиваєважливі властивості вихідної, що може бути нетривіально.
Проріджуючиалгоритм, ітеративно видаляє вершини або грані з полігональної сітки, роблячитріангуляцію після кожного кроку. Більшість із них використають тільки локальнізміни, що дозволяє виконувати спрощення досить швидко (рис. 2.1).
/>
Рис.2.1. Об’єднанняребер (процес тріангуляції)
Схеми зі злиттямвершин працюють за допомогою об’єднання двох або більше вершин деталізованоїмоделі в одну, котра у свою чергу може бути сполучена з іншими вершинами.Злиття вершин трикутника знищує його, зменшуючи загальне число трикутниківмоделі. Звичайно алгоритми використовують складні методи визначення, яківершини потрібно об’єднати разом і у якому порядку. Методи, що використовуютьзлиття ребер (edge collapse), завжди зливають вершини, що розділяють однугрань. Такі методи зберігають локальну топологію і, крім того, при деякихумовах можуть працювати в реальному часі.
Складністьобчислень у цих методах висока і їхнє використання не завжди виправдане прироботі з дискретними даними, оскільки складність з'являється насамперед черезнеобхідність підтримувати зв’язаність моделі. Іншою причиною високої складностіметодів є лінійна структура сітки, яку необхідно відновлювати для візуалізаціїза допомогою графічних API.
Переваги даногоалгоритму: розповсюджене представлення; апаратна підтримка.
Недолікиалгоритму: неефективні для роботи з дискретними даними через штучну підтримкузв’язності, складного препроцесінга; неефективні для більших моделей черезтруднощі з організацією багатомасштабності.
2.1.3 Воксельні моделі
Класичнівоксельні (voxel) моделі являють собою тривимірний масив, кожному елементуякого зіставлений колір й коефіцієнт прозорості. Такий масив задає наближенняоб’єкта з точністю, обумовленої обмеженням масиву.
Воксельні (абооб'ємними) методами візуалізації називаються методи візуалізації тривимірнихфункцій, у дискретному випадку заданих, наприклад, за допомогою описаного вищемасиву.
Типові методивоксельної візуалізації обробляють масив, і формують проекцію кожного йогоелемента на видову площину. Вихідний масив являє собою регулярну структуруданих, що істотно використовується в методах візуалізації. Звичайно елементмасиву з’являється на екрані у вигляді деякого примітиву, так званого відбитку(footprint) або сплату (splat). Різні методи відрізняються способами обчисленьформи й розмірів зображення[3].
Обсяги даних увоксельних поданнях значні, навіть для невеликих моделей. Єдиною реальноюможливістю працювати зі складними об'єктами є використання деревоподібнихієрархій. У роботі Лаур Д. та Ханрахана П. на основі вихідного масиву будуєтьсябагатомасштабне подання у вигляді восьмеричного дерева. Кожен вузол деревамістить усереднене значення кольорів і прозорості всіх своїх нащадків. Крімтого, кожен вузол дерева містить змінну, що показує середню помилку,асоційовану з даним вузлом. Ця змінна показує помилку, що виникає при замініоригінального набору вокселів в даній області простору на константну функцію,рівну середньому значенню кольорів всіх нащадків даного вузла. Надалі цезначення використовується для керування якістю візуалізації й рівнем деталей.
Незважаючи на те,що воксельні методи орієнтовані в першу чергу на наукову візуалізацію, багатоідей, що використовується в цих методах, знаходять своє застосування в іншихобластях. Наприклад, ідея решітки використається при роботі із точковимиподаннями, а також з поданнями, заснованими на зображеннях.
Переваги даногоалгоритму: простота регулярної структури; апаратна підтримка.
Недоліки даногоалгоритму: великий обсяг даних, тому необхідно використовувати спеціальнібагатомаштабні структури для роботи зі складними об'єктами; використовуваніструктури даних зберігають внутрішньої, невидимі, частини об’єкта, тоді як дляпоставленого завдання достатній опис поверхні.
2.1.4 Моделі, засновані на зображеннях
Моделювання йвізуалізація, засновані на зображеннях (Image-Based Modeling and Rendering,далі IBMR) являють собою альтернативний підхід до рішення завдань синтезузображення [4].
Такі методи невикористовують проміжні структури даних, і синтезують підсумкову картинку,ґрунтуючись на вихідних даних — як правило, зображеннях або зображеннях зглибиною. Більш формально метод візуалізації, заснований на зображеннях, можнавизначити як алгоритм, що визначає, як по кінцевому наборі вихідних (reference)зображень сцени одержати нове, результуюче (resulting) зображення для заданоїточки спостереження й заданих параметрів віртуальної камери.
Структури даних,використовувані для такого алгоритму візуалізації, можуть сильно відрізнятися,незмінним залишається орієнтація методів на безпосередню роботу з вихіднимиданими, що робить методи IBMR концептуально близькими до поставленого завдання.
Зображення з картами глибини
Однієї знайпростіших структур даних, використовуваних в IBMR є набори зображень ізкартами глибини. Визначимо пари зображення плюс карта глибини як кольоровезображення, якій зіставлене напівтонові зображення відповідного розміру,інтенсивність у кожній точці якого відповідає відстані від камери до поверхніоб’єкта.
Примітноювластивістю подання є те, що сучасні дистанційні сканери дозволяють прямо одержуватидані у вигляді карт глибини, а найбільш дорогі моделі одержують і колірнуінформацію про об'єкт. Отже, таке подання максимально підходить для роботи зіскладними реальними даними, а завдання полягає в розробці методу візуалізації.
Варто помітити,що пари зображення плюс карта глибини однозначно визначає дискретне наближенняповерхні в тривимірному просторі, при цьому якість наближення залежить відроздільної здатності зображення й обраного положення камери.
Одна картаглибини зберігає тільки видиму частину об’єкта, тому для відновлення повногооб’єкта необхідно використати набір з декількох карт глибини, залежно від складностісцени (рис. 2.2).
/>
Рис. 2.2.Створення карти глибин по пікселям
Булозапропоновано досить багато методів візуалізації й використання подібнихструктур даних. Наприклад, Леонардо-Макмиллан використовує систему обробкизображень для деформації (warping) вихідного зображення з обліком вихідної йрезультуючої (поточної) камер таким чином, щоб результат, відображений наекрані, створював ілюзію тривимірності [5].
У роботі МартінаОлів’єрі також використовується деформація зображень, однак результатом роботиалгоритму є текстури створені з карт глибини для поточного положеннявіртуальної камери й накладені на просту (плоску) полігональну сітку — такназивані рельєфні текстури (relief textures) [6].
Однак ці методимають серйозні недоліки. З одного боку, в умовах недостатньої точності вихіднихданих й або великому відхиленні віртуальної камери від вихідної, урезультуючому зображенні можлива поява дірок (holes), тобто погіршення якостівізуалізації. З іншого боку, результатом роботи дистанційних сканерів часто єнабори даних з 50-70 карт глибини, які в описаних вище алгоритмах будутьоброблятися сепаратно, створюючи додаткові погрішності візуалізації. Крім того,час візуалізації однієї карти глибини розміром 512x512 по методу Олів’єрі накомп'ютері із процесором Pentium III 866 і відео картою NVidia GeForce2 Proстановить близько 70 мс. Обробка 50-ти зображень займе біля 4-х секунд.
Іншим можливимваріантом є пряме відновлення тривимірних координат семплів (sample) і їхнявізуалізація прямо за допомогою проекції на видову площину віртуальної камери.Такий підхід дозволяє використати апаратне прискорення тому, що пікселівихідних зображень у просторі можуть бути представлені крапками абобагатокутниками. Однак, на практиці такий метод працює тільки для доситьневеликих наборів даних.
Головноюперешкодою для створення багатошарових методів візуалізації карт глибини євідсутність чіткої просторової структури пари зображення плюс карта глибини.
Багатошарові зображення із глибиною
Останнім часомбуло почато кілька спроб використання багатомасштабних методів разом іззаснованими на зображеннях поданнями. Одна з них описана в роботі Чанга й Бішопай як базове подання використовує багатошарові зображення із глибиною (LayeredDepth Images — LDI), у перше описані в статі Гортлера С. Солена М. (Візуалізаціябагатошарових глибин зображення
Багатошаровізображення із глибиною зберігають для кожного пікселя карти кольорів всіперетинання відповідного променя з моделлю. Одного багатошарового зображеннядосить для опису повного об’єкта (рис. 2.3).
/>
Рис. 2.3.Багатошарове зображення
Відмінністьбагатошарових зображень із глибиною від простих полягає в тім, що однезображення дозволяє зберігати інформацію не тільки про видиму з даної вихідноїкамери частини поверхні об’єкта, а повну інформацію про об'єкт. По суті, LDI –це тривимірна структура даних, що представляє собою прямокутну матрицю, кожнимелементом якої є список крапок. Кожна крапка містить глибину (відстань доопорної площини) і атрибути, у найпростішому випадку – кольори. Для поданнявсього об’єкта можна використати єдине багатошарове зображення, що використовуєшість перспективних LDI з єдиним центром проекції (3).
Така структурадозволяє проводити візуалізацію як описаними вище методами Макмілана й Олів’єрі,так і просто використати збережену інформацію як скупчення точок і відображатийого прямо за допомогою одного із графічних API (наприклад, OpenGL).
З використаннямLDI-подібних структур зв'язані деякі обмеження на візуалізацію, обумовлені тим,що всі крапки в зображенні орієнтовані на одну базову площину. Крім того, LDIне можуть бути прямо отримані із пристроїв введення й для створення такоїструктури необхідне використання додаткових алгоритмів, наприклад, деформуючизображення із глибиною по методу Макмілана таким чином, щоб площинарезультуючого зображення збігалася з базовою площиною LDI. Відзначимо, щопроцес формування LDI відбувається до безпосередньої візуалізації, і тому йогоефективність не відбивається на швидкості візуалізації.
Однак LDI недозволяє прямо відображати об'єкт із різними ступенями деталізації. Але булапочата спроба створити багатосштабне подання на основі LDI з використанням такназиваного дерева LDI (LDI tree).
Сутність методуполягає в наступному: замість одного LDI формується восьмеричне дерево, укожному вузлі якого перебуває свій LDI і посилання на інші вузли, у якихперебуває LDI меншого розміру (в одиницях сцени), але того ж дозволу. Також длякожного вузла є обмежуючий паралелепіпед.
Всі LDI у деревімають однаковий дозвіл. Висота дерева залежить від дозволу LDI. Чим меншедозвіл LDI, тим більше висота дерева. Кожен LDI у дереві містить інформаціютільки про ту частину сцени, що втримується в його обмежуючому паралелепіпеді.Обмежуючі паралелепіпеди вузлів наступного рівня дерева виходять дробленнямобмежуючого паралелепіпеда поточного рівня на вісім рівних частин (рис. 2.4).
/>
Рис. 2.4. Деревоіз LDI
Дерево LDIдозволяє вирішувати проблему візуалізації дуже великих структур даних,використовуючи наступну ідею: при візуалізації немає необхідності оброблятинащадків вузла, якщо сам вузол забезпечує достатній ступінь деталізації. Авторивикористають наступний критерій ступеня деталізації: вважається, що LDIзабезпечує достатній рівень деталізації, якщо «відбиток» (footprint,splat) його пікселя на результуючому зображенні покриває не більше одногопікселя екрана.
З іншого боку,використання того ж підходу дозволяє доповнити дані низької роздільноїздатності штучно відновленими додатковими рівнями дерева, створюючи ефектфільтрації одержуваного зображення.
Візуалізаціявиробляється за допомогою обходу дерева від кореня до листів і малювання LDIметодом Макмілана. При цьому обробка всіх вузлів дерева не потрібно, і обхідвітки дерева завершується на першому LDI, що забезпечує достатню точність.
Алгоритм маєвисоку якість візуалізації, можливість прогресивної передачі даних. Однак йогоефективність, як за часом, так і по пам'яті, досить низька. Час одержаннязображення в дозволі 512х512 для LDI середньої складності на графічній станціїSGI Onyx2 (16Гбайт оперативної пам'яті, 32 процесора MIPS R1000 250Mhz) зайнялобільше трьох секунд.
Переваги данихалгоритмів: орієнтація на проблемну область; легкість одержання й моделювання.
Недоліки данихалгоритмів: складні, не завжди якісні методи візуалізації; труднощі зпідтримкою багатомасштабності; робота тільки з дифузійними поверхнями.
2.1.5 Точкове подання
Класичні подання,засновані на зображеннях, спрямовані на використання зображень як примітививізуалізації. Підвищення ефективності візуалізації досягається за рахунок того,що час візуалізації в них пропорційно не складності геометрії, як у традиційнихсистемах, заснованих на полігональних сітках, а числу пікселів у вихіднихзображеннях. Хоча такі підходи досить добре працюють для візуалізації складнихоб'єктів, вони, як правило, вимагають значних обсягів пам'яті, візуалізаціястраждає від появи артефактів у результуючому зображенні, а також віднеможливості роботи з динамічним освітленням. Крім того, на сьогодні нерозроблено ефективних багатомасштабних алгоритмів.
Клас точкових(point sample) алгоритмів компенсують недоліки IBМ при частковому збереженніописаних вище переваг [7].
Об'єктимоделюються, як щільний набір точок поверхні, які відновлюються з вихіднихзображень і зберігаються разом з кольорами, глибиною й інформацією про нормалі,уможливлюючи використання Z-буфера для видалення невидимих поверхонь, затіненняпо Фонгу, і інші ефекти, наприклад, тіні (рис.2.5).
/>
Рис.2.5.Дірки при візуалізації крапкових моделей
Методвізуалізації таких даних нагадує класичні методи деформацій (warping), але з тимрозходженням, що точки містять додаткову інформацію про геометрію, і вонивидонезалежні (view independent), тобто кольори точки не залежить від напрямку,з якого вона була відновлена. Подібний підхід використався для реалістичноївізуалізації дерев [2].
Основноюпроблемою візуалізації моделей у таких поданнях є відновлення безперервнихповерхонь, тобто гарантія відсутності дірок після того, як положення кожноїкрапки буде наведено до віконних координат. Одним з можливих практичних рішеньє решітка (splatting), тобто обчислення форми «відбитка» точки на площиніекрана. Решітка також часто використається в методах, заснованих назображеннях. Можливі також інші підходи, наприклад комбінація ресемплінгу йієрархічного z-буфера, недоліками яких є недостатнє використання сучаснихапаратних прискорювачів, що виражається в часі візуалізації близько 3-5 секундна кадр для нескладних сцен.
Головнимнедоліком точкових подань, як і багатьох інших, є складність із поданнямвеликих обсягів даних. Використання неструктурованого набору крапок дозволяєдосягти певної гнучкості при візуалізації, але при збільшенні обсягу на першийплан виходять методи відео залежного спрощення, використати які в реальномучасі не представляється можливим без введення додаткових структур даних.
Переваги даногоалгоритму: орієнтація на проблемну область; легкість одержання й моделювання;значна гнучкість у методах візуалізації.
Недоліки даногоалгоритму: труднощі з підтримкою багатомасштабності; неякісна або повільнавізуалізація.
2.1.6 Ієрархічні подання
Як правило,ієрархічні подання будуються на базі одного з подань, розглянутих вище. Упереважній більшості випадків для побудови ієрархій використовуютьсядеревоподібні структури, наприклад, восьмеричні дерева, або kd-дерева. Такожвикористаються загальні види тривимірних дерев на основі ієрархій що описуютьсфери та куби. Властивості ієрархій можуть сильно розрізнятися залежно відбазового подання, однак загальні принципи побудови й візуалізації ієрархічнихструктур подібні між собою.
Нижній рівеньдерева, тобто сукупність листових вершин, являє собою максимально деталізованумодель. Далі, піднімаючись до кореня, атрибути усередняться, структураспрощується до виродження в один примітив на вершині дерева. Візуалізація,навпаки, виробляється за допомогою рекурсивного обходу дерева від вершини долистів.
Ієрархічніструктури на базі полігональних сіток використаються для динамічного контролюза рівнем деталізації й складністю моделі. У методі злиття вершин з вузломдерева асоційована вершина сітки, і перехід до вище поставленого вузла дереваздійснюється за допомогою злиття вершин.
Точкові семпли — це точки, що володіють кінцевим розміром і положенням у просторі, тобто вони єаналогом нерівномірно розподілених у просторі вокселів. На їхній основібудується ієрархія сфер, таких що, сфера, асоційована із внутрішнім вузломдерева, містить безліч своїх нащадків.
Переваги даногоалгоритму: підтримка багатомасштабності; можливість прогресивної обробки йпередачі по мережі; можливість динамічного контролю над рівнем деталізації.
Недоліки даногоалгоритму: необхідність у попередній обробці, або перетворенні з іншогоподання; у загальному випадку більша вартість обробки примітива, чим у лінійнихподаннях; часте збільшення обсягу через необхідність підтримки багатомасштабності(для зберігання показників тощо).
2.2 Опис алгоритму і функціонування програми
Згідно оглянутихвище методів та алгоритмів, ми в даному проекті будемо розглядати перетвореннязображення по карті глибин. Оскільки даний алгоритм надає нам простіший спосібреалізації та добрі часові показники. Процес побудови карти глибин розраховуєтьсянаступним чином:
визначаєтьсяколір пікселя (в процесі беруть участь три основні коліра червони, зелений тасиній);
потімвизначається середнє значення серед цих трьох кольорів (шумується значеннякольорів Ч + З + С та ділиться на кількість кольорів);
у наступномуетапі задається значення відносно якого буде підніматися піксель (це значеннязалишається однаковим для всіх пікселів зображення);
такі дії будутьпроводитись відносно кожного пікселя зображення.
Загальнийалгоритм роботи програми по перетворенню двомірного зображення в об’ємневиглядає наступним чином. Алгоритм програми зображено на блок-схемі(рис. 2.6).
/>
Рис. 2.6. Роботаалгоритму перетворення зображення по карті висот
2.3 Опис організації вхідних та вихідних даних
Програма даєможливість використовувати зображення різного типу, а саме: від скановані,фотографії та малюнки. В якості вхідних даних можливо використовувати лишезображення формату bmp.
Результатперетворення зображення можливо обертати під різними кутами, віддаляти танаближати. Отримане зображення після перетворення можливо зберегти. Форматзбереження отриманого файлу bmp.
2.4 Опис організації вибору технічних і програмнихзасобів
Розробленийпрограмний продукт орієнтований на роботу в ОС Windows /XP/Vista, тому длякоректної роботи програми необхідне стабільне функціонування ОС. Під часвиконання, програма не звертається до інших
програмнихпродуктів, таких як Microsoft Office та ін., але звертається до реєстру ОС.
Мінімальнимивимогами, за яких програма працюватиме та буде видавати достовірні результати,до апаратної частини ПК, можна вважати:
/>• процесор 6-го покоління IntelCeleron 1.1 ГГц;
• об’ємоперативної пам’яті 128 Мб.;
• графічнийадаптер S3 Savage 64 Мб.;
• жорсткий дискємністю 10 Гб.;
• привід гнучкихдисків (дисковод).
3. Очікувані техніко-економічні показники
Проведемо оцінкувитрат праці на розробку програмного забезпечення для комплексу, при цьомувиходимо з того, що розмір вихідного тексту запису алгоритму і даних восновному визначає затрати праці /> та часрозробки /> програмного продукту:
/> (1)
де /> — кількість вихіднихкоманд в тисячах.
У якості вихідноїкоманди приймаємо рядок програми.
Загальний об'ємвихідного тексту програм складає приблизно 900 рядків. Тоді:
/>
Продуктивністьпраці розробників програмного забезпечення визначається наступним чином:
/> (2)
Тоді миотримуємо, що продуктивність праці розробника:
/>
Час необхіднийдля розробки програмного продукту, можна визначити за формулою (3):
/> (3)
де /> — строк розробкипрограмного продукту;
/> — коефіцієнт вірностіпостановки завдання;
/> — час розробки алгоритму;
/> — час настройки татестування;
/> — час на підготовку тексту;
/> — час на розробкудокументації.
Останні величиниобчислюються за наступними формулами:
/> (4)
/> (5)
/> (6)
/> (7)
/> (8)
/> (9)
де К — залежитьвід ступеня підготовки програміста;
/> —кількість рядків програми (в тис.).
Підставляємозначення у формули (4-9) враховуючи, що К=0,8 (стаж роботи до 2-х років).
/>
/>
/>
/>
/>
/>
Тоді час, якийнеобхідний для розробки програмного продукту дорівнює
/>
Визначимособівартість години роботи ПК.
Для цьогорозраховуються поточні витрати на експлуатацію комп'ютера.
До їх складувключаються витрати на електроенергію і амортизаційні відрахування на реноваціювід вартості комп'ютера та інше.
Витрати наелектроенергію визначають множенням витрати електроенергії за одну годину навартість 1 кВт/год електроенергії і на час роботи комп'ютера за рік. Час роботикомп'ютера за рік визначається множенням кількості робочих днів у рік на часроботи комп'ютера за день:
/> (10)
де /> — середня кількістьробочих днів у рік.
Середня кількістьробочих днів у рік буде рівна:
/>
Тоді, час роботиПК за рік дорівнює:
/>
Витрати енергіївизначаються за формулою:
/> (11)
де /> — витрати електроенергіїза одну годину; /> — вартість 1кВт/год електроенергії; /> — часроботи комп’ютера за рік.
Тоді витратиенергії складають:
/>
Амортизаційні відрахуваннявизначаються множенням вартості комплексу на норму амортизаційних відрахувань10%:
/>
Приблизна річназаробітна плата обслуговуючого персоналу складає:
/>
Відрахування насоціальне страхування, складають 3% від загальної заробітної плати за рік:
/>
Вартістьвитрачених матеріалів складає 2% від вартості обчислювальної техніки:
/>
Утримання наремонт приміщень, в яких знаходяться засоби обчислювальної техніки, складає 3%від вартості обчислювальної техніки:
/>
Кількістькомплексів, що реалізовують зв’язок:
/>
Собівартістьгодини роботи на комп'ютері визначається наступним співвідношенням:
/> (12)
Підставляємозначення в останню формулу й отримаємо:
/>
Рахуємо прямівитрати на виконання курсової роботи, які визначаються наступним добутком:
/> (13)
де /> — собівартість годинироботи на комп’ютері; />— час необхіднийдля розробки програмного продукту. Підставляємо значення й одержуємо:
/>
Накладні витрати,що включають витрати на освітлення, опалення та ін. приймаються в розмірі40-50% від суми прямих витрат:
/>
Загальні витратина виконання курсової роботи:
/> (14)
Підставляємо даній одержуємо:
/>
Ціна напрограмний продукт визначається наступним співвідношенням:
/> (15)
де В — витратина виконання курсового проекту;
P — рівеньрентабельності, в нашому випадку P = 30;
K — коефіцієнт,що залежить від науково-технічного рівня К = 0,9.
Підставляємо цізначення й отримаємо ціну програмного продукту, яка дорівнює:
/>
Список використаних джерел
1. Turk, G., Levoy, M., Zippered PolygonMeshes from Range Images. Proc. SIGGRAPH '94.
2. Luebke, David P. A Developer's Surveyof Polygonal Simplification Algorithms. IEEE Computer Graphics &Applications, 2001.
3. Роджерс Д., Адаме Дж. Математическиеосновы машинной графики: Пер. с англ. — М.: Мир, 2001. —604 с.
4. Curless, B., Levoy, M., VolumetricMethod for Building Complex Models from Range Images. Proc. SIGGRAPH '96.
5. McMillan, L. An Image-Based Approach toThree-Dimensional Computer Graphics. Ph.D. Dissertation. UNC Computer ScienceTechnical Report TR97-013, University of North Carolina, 1997
6. Bishop, G., Oliveira M.M., «ReliefTextures» Proc. SIGGRAPH'2000
7. Роджерс Д. Алгоритмические основымашинной графики: Пер. с англ. — М.: Мир, 1989. – 512 с.
8. Божко А, Жук Д.М., Маничев В.Б. Комп’ютернаграфіка. — М.: МГТУ им. Баумана, 2007. — 392 с.