Курсовая работа: Формування об’ємних зображень на основі фотографій
Структури даних, використовувані для такого алгоритму візуалізації, можуть сильно відрізнятися, незмінним залишається орієнтація методів на безпосередню роботу з вихідними даними, що робить методи 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) і їхня візуалізація прямо за допомогою проекції на видову площину віртуальної камери. Такий підхід дозволяє використати апаратне прискорення тому, що піксел вихідних зображень у просторі можуть бути представлені крапками або багатокутниками. Однак, на практиці такий метод працює тільки для досить невеликих наборів даних.
Головною перешкодою для створення багатошарових методів візуалізації карт глибини відсутність чіткої просторової структури пари зображення плюс карта глибини.
Багатошарові зображення із глибиною
Останнім часом було почато кілька спроб використання багатомасштабних методів разом із заснованими на зображеннях поданнями. Одна з них описана в роботі Чанга й Бішопа й як базове подання використовує багатошарові зображення із глибиною (Layered Depth 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) зайняло більше трьох секунд.
Переваги даних алгоритмів: орієнтація на проблемну область; легкість одержання й моделювання.
Недоліки даних алгоритмів: складні, не завжди якісні методи візуалізації; труднощі з підтримкою багатомасштабності; робота тільки з дифузійними поверхнями.
Класичні подання, засновані на зображеннях, спрямовані на використання зображень як примітиви візуалізації. Підвищення ефективності візуалізації досягається за рахунок того, що час візуалізації в них пропорційно не складності геометрії, як у традиційних системах, заснованих на полігональних сітках, а числу пікселів у вихідних зображеннях. Хоча такі підходи досить добре працюють для візуалізації складних об'єктів, вони, як правило, вимагають значних обсягів пам'яті, візуалізація страждає від появи артефактів у результуючому зображенні, а також від неможливості роботи з динамічним освітленням. Крім того, на сьогодні не розроблено ефективних багатомасштабних алгоритмів.
Клас точкових (point sample) алгоритмів компенсують недоліки IBМ при частковому збереженн описаних вище переваг [7].
Об'єкти моделюються, як щільний набір точок поверхні, які відновлюються з вихідних зображень і зберігаються разом з кольорами, глибиною й інформацією про нормалі, уможливлюючи використання Z-буфера для видалення невидимих поверхонь, затінення по Фонгу, і інші ефекти, наприклад, тіні (рис. 2.5).
Рис. 2.5. Дірки при візуалізації крапкових моделей
Метод візуалізації таких даних нагадує класичні методи деформацій (warping), але з тим розходженням, що точки містять додаткову інформацію про геометрію, і вони видонезалежні (view independent), тобто кольори точки не залежить від напрямку, з якого вона була відновлена. Подібний підхід використався для реалістично візуалізації дерев [2].
Основною проблемою візуалізації моделей у таких поданнях є відновлення безперервних поверхонь, тобто гарантія відсутності дірок після того, як положення кожно крапки буде наведено до віконних координат. Одним з можливих практичних рішень решітка (splatting), тобто обчислення форми «відбитка» точки на площин екрана. Решітка також часто використається в методах, заснованих на зображеннях. Можливі також інші підходи, наприклад комбінація ресемплінгу й рархічного z-буфера, недоліками яких є недостатнє використання сучасних апаратних прискорювачів, що виражається в часі візуалізації близько 3-5 секунд на кадр для нескладних сцен.
Головним недоліком точкових подань, як і багатьох інших, є складність із поданням великих обсягів даних. Використання неструктурованого набору крапок дозволя досягти певної гнучкості при візуалізації, але при збільшенні обсягу на перший план виходять методи відео залежного спрощення, використати які в реальному часі не представляється можливим без введення додаткових структур даних.
Переваги даного алгоритму: орієнтація на проблемну область; легкість одержання й моделювання; значна гнучкість у методах візуалізації.
Недоліки даного алгоритму: труднощі з підтримкою багатомасштабності; неякісна або повільна візуалізація.
Як правило, рархічні подання будуються на базі одного з подань, розглянутих вище. У переважній більшості випадків для побудови ієрархій використовуються деревоподібні структури, наприклад, восьмеричні дерева, або kd-дерева. Також використаються загальні види тривимірних дерев на основі ієрархій що описують сфери та куби. Властивості ієрархій можуть сильно розрізнятися залежно від базового подання, однак загальні принципи побудови й візуалізації ієрархічних структур подібні між собою.
Нижній рівень дерева, тобто сукупність листових вершин, являє собою максимально деталізовану модель. Далі, піднімаючись до кореня, атрибути усередняться, структура спрощується до виродження в один примітив на вершині дерева. Візуалізація, навпаки, виробляється за допомогою рекурсивного обходу дерева від вершини до листів.
Ієрархічн структури на базі полігональних сіток використаються для динамічного контролю за рівнем деталізації й складністю моделі. У методі злиття вершин з вузлом дерева асоційована вершина сітки, і перехід до вище поставленого вузла дерева здійснюється за допомогою злиття вершин.
Точкові семпли - це точки, що володіють кінцевим розміром і положенням у просторі, тобто вони аналогом нерівномірно розподілених у просторі вокселів. На їхній основ будується ієрархія сфер, таких що, сфера, асоційована із внутрішнім вузлом дерева, містить безліч своїх нащадків.
Переваги даного алгоритму: підтримка багатомасштабності; можливість прогресивної обробки й передачі по мережі; можливість динамічного контролю над рівнем деталізації.
Недоліки даного алгоритму: необхідність у попередній обробці, або перетворенні з іншого подання; у загальному випадку більша вартість обробки примітива, чим у лінійних поданнях; часте збільшення обсягу через необхідність підтримки багатомасштабност (для зберігання показників тощо).
2.2 Опис алгоритму і функціонування програми
Згідно оглянутих вище методів та алгоритмів, ми в даному проекті будемо розглядати перетворення зображення по карті глибин. Оскільки даний алгоритм надає нам простіший спосіб реалізації та добрі часові показники. Процес побудови карти глибин розраховується наступним чином:
визначається колір пікселя (в процесі беруть участь три основні коліра червони, зелений та синій);
потім визначається середнє значення серед цих трьох кольорів (шумується значення кольорів Ч + З + С та ділиться на кількість кольорів);
у наступному етапі задається значення відносно якого буде підніматися піксель (це значення залишається однаковим для всіх пікселів зображення);
такі дії будуть проводитись відносно кожного пікселя зображення.
Загальний алгоритм роботи програми по перетворенню двомірного зображення в об’ємне виглядає наступним чином. Алгоритм програми зображено на блок-схемі(рис. 2.6).
Рис. 2.6. Робота алгоритму перетворення зображення по карті висот
2.3 Опис організації вхідних та вихідних даних
Програма да можливість використовувати зображення різного типу, а саме: від скановані, фотографії та малюнки. В якості вхідних даних можливо використовувати лише зображення формату bmp.
Результат перетворення зображення можливо обертати під різними кутами, віддаляти та наближати. Отримане зображення після перетворення можливо зберегти. Формат збереження отриманого файлу bmp.
2.4 Опис організації вибору технічних і програмних засобів
Розроблений програмний продукт орієнтований на роботу в ОС Windows /XP/Vista, тому для коректної роботи програми необхідне стабільне функціонування ОС. Під час виконання, програма не звертається до інших
програмних продуктів, таких як Microsoft Office та ін., але звертається до реєстру ОС.
Мінімальними вимогами, за яких програма працюватиме та буде видавати достовірні результати, до апаратної частини ПК, можна вважати:
• процесор 6-го покоління Intel Celeron 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 Polygon Meshes from Range Images. Proc. SIGGRAPH '94.
2. Luebke, David P. A Developer's Survey of Polygonal Simplification Algorithms. IEEE Computer Graphics & Applications, 2001.
3. Роджерс Д., Адаме Дж. Математические основы машинной графики: Пер. с англ. — М.: Мир, 2001. —604 с.
4. Curless, B., Levoy, M., Volumetric Method for Building Complex Models from Range Images. Proc. SIGGRAPH '96.
5. McMillan, L. An Image-Based Approach to Three-Dimensional Computer Graphics. Ph.D. Dissertation. UNC Computer Science Technical Report TR97-013, University of North Carolina, 1997
6. Bishop, G., Oliveira M.M., "Relief Textures" Proc. SIGGRAPH'2000
7. Роджерс Д. Алгоритмические основы машинной графики: Пер. с англ. - М.: Мир, 1989. – 512 с.
8. Божко А, Жук Д.М., Маничев В.Б. Комп’ютерна графіка. - М.: МГТУ им. Баумана, 2007. - 392 с.
