Формування об’ємних зображень на основі фотографій (стр. 2 из 5)
Отже, для використання полігональних моделей зв’язність повинна бути введена штучно на етапі препроцесуванні. Таким чином, полігональні моделі не призначені для прямої роботи з від сканованими даними, тому що вимагають відновлення поверхні, що в загальному випадку є нетривіальним завданням і сильно залежить від класу оброблюваних об'єктів. При цьому відновлена поверхня не обов'язково буде використовуватися на етапі візуалізації (наприклад, якщо модель такої складності, що проекція трикутника на екран при типовій проекції перегляду близька по площі з одним пікселем).
З іншого боку, створена велика кількість методів, що дозволяють досить ефективно перетворювати дискретні від скановані дані в полігональні сітки. Більше того, сучасне устаткування високого класу дозволяє виконувати перетворення в сітку апаратно [1].
Набагато складніше ситуація з поданням великих обсягів даних і підтримкою різних рівнів деталізації. Структура полігональних сіток лінійна й вони не забезпечують «природної» підтримки багатомасштабності. Тому робота з великими сітками ускладнена і потребує різних, найчастіше обчислювально складних методів спрощення. Було створено безліч алгоритмів для створення багатомасштабних подань на основі сіток, що мають безпосереднє відношення до поставленого завдання.
Практично всі технології спрощення сіток використовують деякі варіації або комбінації наступних механізмів: семплюваня (sampling), проріджування (decimation), адаптивної розбивки (adaptive subdivision) і злиття вершин (vertex merging) [2].
Алгоритми семплюваня спрощують первісну геометрію моделі, використовуючи або підмножину вихідних точок, або перетинання вокселів з моделлю на тривимірній сітці. Такі алгоритми найкраще працюють на гладких поверхнях без гострих кутів.
Алгоритми, що використовують адаптивну розбивку, знаходять просту базову (base) сітку, що потім рекурсивно розбивається для апроксимації первісної моделі. Такий підхід працює добре, коли знайти базову модель відносно просто. Наприклад, базова модель для ділянки ландшафту звичайно прямокутник. Для досягнення гарних результатів на довільних моделях потрібне створення базової моделі, що відбиває важливі властивості вихідної, що може бути нетривіально.
Проріджуючи алгоритм, ітеративно видаляє вершини або грані з полігональної сітки, роблячи тріангуляцію після кожного кроку. Більшість із них використають тільки локальні зміни, що дозволяє виконувати спрощення досить швидко (рис. 2.1).
Рис.2.1. Об’єднання ребер (процес тріангуляції)
Схеми зі злиттям вершин працюють за допомогою об’єднання двох або більше вершин деталізованої моделі в одну, котра у свою чергу може бути сполучена з іншими вершинами. Злиття вершин трикутника знищує його, зменшуючи загальне число трикутників моделі. Звичайно алгоритми використовують складні методи визначення, які вершини потрібно об’єднати разом і у якому порядку. Методи, що використовують злиття ребер (edge collapse), завжди зливають вершини, що розділяють одну грань. Такі методи зберігають локальну топологію і, крім того, при деяких умовах можуть працювати в реальному часі.
Складність обчислень у цих методах висока і їхнє використання не завжди виправдане при роботі з дискретними даними, оскільки складність з'являється насамперед через необхідність підтримувати зв’язаність моделі. Іншою причиною високої складності методів є лінійна структура сітки, яку необхідно відновлювати для візуалізації за допомогою графічних API.
Переваги даного алгоритму: розповсюджене представлення; апаратна підтримка.
Недоліки алгоритму: неефективні для роботи з дискретними даними через штучну підтримку зв’язності, складного препроцесінга; неефективні для більших моделей через труднощі з організацією багатомасштабності.
Класичні воксельні (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-х секунд.