Диссертация (1149346), страница 10
Текст из файла (страница 10)
снятие с очереди Q и обработка очередной единицы укрупнения ι; укрупнение осуществляется только в том случае, если погрешность построенной наукрупненной триангуляции аппроксимации не превышает априори заданнойверхней границы погрешности ε;3. поиск и постановка в очередь Q единиц укрупнения, являющихся соседнимидля ι;4. проверка очереди Q: если очередь не пуста, то идем к пункту 2, иначе —завершение алгоритма.На рисунках 3.8 - 3.13 проиллюстрированны описанные выше этапы работы.1.
Нарисунке 3.7 показана исходная сетка.Рис. 3.7 – Получение исходной сетки.842. На рисунке 3.8 демонстрируется выборка из очереди Q следующей единицыe ее центральную вершину, как иукрупнения триангуляции; обозначим ее Λ;eпрежде, обозначим символом Λ. Барицентрические звезды, составляющие Λ,e угловыми,обозначим символами Υ, Φ, Ψ и Ω. Вершины, являющиеся для Λобозначены символами α, β, γ и δ.Рис. 3.8 – Выборка первой единицы укрупнения.3. На рисунке 3.9 показано объединение треугольников, составляющих Υ; приэтом объединяется пара треугольников, инцидентных центральной вершинеединицы укрупнения Λ, и пара треугольников, инцидентных общей угловойвершине β.
β — вершина второго класса — является центральной для соседe посредством общейней единицы укрупнения триангуляции (обозначим ее β)барицентрической звезды Υ; поставим βe в очередь Q.85Рис. 3.9 – Укрупнение треугольников, составляющих барицетрическую звездуΥ.4. Объединение треугольников в остальных трех барицентрических звездах осуществляется по тому же правилу: объединяется пара треугольников, инцидентных общей вершине Λ, и пара треугольников, инцидентных общей угловой вершине. После обработки каждой звезды в очередь Q ставится соседняяединица укрупнения, определяемая соответствующей угловой вершиной (γe, δee для соответственно γ, δ и α).
На рисунке 3.10 показан результат обработкииαбарицентрических звезд рассматриваемой единицы укрупнения.Рис. 3.10 – Укрупнение треугольников для барицентрических звезд Φ, Ψ и Ω.После завершения обработки рассматриваемая на данной итерации единицаукрупнения помечается как обработанная.865. На последующих итерациях алгоритма обрабатываются единицы укрупнения,e γe, δe и αe. На рисунке 3.11поставленные в очередь Q на предыдущих шагах: β,показан результат обработки всех представленных единиц укрупнения.Рис. 3.11 – Результат обработки всех представленных единиц укрупнения.6. Алгоритм завершается, как только в очереди Q не остается элементов дляобработки.Шаг 4: о результатахРезультатомработыпрограммыявляютсятаблицыинциденцийукрупненных триангуляций для красной, зеленой и синей компонент цвета.
Такжебыла реализована возможность вывода результата в графический файл, построенный на аппроксимированных на значениях компонент цвета.При запуске все файлы, находящиеся в директории out_path удаляются. В процессе работы программы для каждого обрабатываемого файла создается поддиректория с названием обрабатываемого файла, в которой создаются текстовыефайлы с первоначальными и результирующими данными таблиц инциденций вершин и треугольников для каждой из компонент цвета обрабатываемого изображения. Кроме того, результат выводится в графический файл, который визуализируется на видеотерминале. Данные о колличестве вершин и треугольников дляисходной и укрупненной триангуляций всех файлов записываются в общий для87всех тестовых данных текстовый файл summary.txt.Исходный код функций, выполняющих укрупнения триангуляции, прелставленв листингах 1, 2 и 3 в приложении.3.7.Результаты работы программы на модельныхпримерахРазработанная программа была протестирована на множестве модельных примеров, здесь будут приведены результаты нескольких из них.
В каждом тесте выполняется многократное локально-адаптивное укрупнения триангуляции. Укрупнения выполняются до тех пор, пока погрешность аппроксимации исходных данных, построенных на укрупненной сетке узлов не превысит априори заданногопредельного значения погрешности ε0 . На основе полученной аппроксимации выполняется построение модели исходного объекта.В таблице 4.1 в первой колонке показано название теста, во второй — исходное изображение, в третьей — его аппроксимация, построенная на укрупненнойтриангуляции.
Для определения погрешности вычисляется абсолютная величинаразности между исходными значениями яркостей пикселей и построенным приближением к ним, а затем берется максимум по всем вершинам исходной триангуляции. В рассматриваемых тестах значение априори заданной верхней гранипогрешности ε равно 20.88Название тестаИсходное изображениеАппроксимацияManetLenaForest_augustТаблица 3.4 – Аппроксимации тестовых данных при ε = 20Таблица 18 характеризует степень уменьшения объема данных в различныхтестовых примерах (а именно, для примеров Manet, Forest, Lena).НазваниевходногофайлаManetForest_augustLenaРазмерсеткиИсходноекол-во вершинВершин послеукрупнения (%%)Исходноекол-во тр-вТр-в послеукрупнения (%%)300 x 220400 x 300400 x 225660001200009000011%99%34%13096223860217875210%99%33%Таблица 3.5 – Результаты тестов89Как следует из представленных в таблице 18 результатов, лучше всего поддаются обработке данные, имеющие наиболее плавные цветовые переходы 2 .В таблице 4.2 приведены аппроксимации теста Lena для различных значенийуказанной априори границы погрешности ε.ВерхняяграницапогрешностиεАппроксимация0402 Очевидно, что количество вершин связано с количеством треугольников триангуляции; в результатах мы приводим оба значениядля наглядности.90ВерхняяграницапогрешностиεАппроксимация80120Таблица 3.6 – Аппроксимации набора данных Lena для различных значенийпогрешности εВ таблице 3.7 показано относительное уменьшение объема информации для примеров, приведенных в таблицах 4.3.91Погрешностьε204080120Исходноекол-во вершин90000900009000090000Вершин послеукрупнения (%%)58%29%7%4%Исходноекол-во тр-в37490178752178752178752Тр-в послеукрупнения (%%)57%28%6%3%Таблица 3.7 – Числовые характеристики аппроксимаций для различных значений ε в примере LenaВ таблицах 3.6 и 3.7 имеется две графы: в первой графе представлено максимальное числовое уклонение аппроксимирующего файла от исходного, а во второйграфе представлено изображение, индуцированное аппроксимацией (при этом нулевому уклонению соответствует исходное изображение).
Представленные в этихтаблицах результаты демонстрируют, что в рассмотреном примере предлагаемыйалгоритм позволяет исключить из рассмотрения до 29% процентов узлов при сохранении достаточного визуального качества аппроксимированных данных (дляслучая ε = 40). Задание большего ε приводит к существенной потере качестваполучаемой аппроксимации. Необходимо отметить, что область применения рассматриваемого алгоритма не ограничивается обработкой компьютерной графики;значения ε должны выбираться в соответствии с условиями решаемых задачь.На рисунке 3.12 приводится набор тестовых данных, в котором при обработкеобразовались 2 независимых области с укрупнениями триангуляции; рассматриваемый набор имеет размеры 16 × 16.
На рисунке 3.13 приведена карта укрупнениятриангуляции: красным отмечены области набора данных (см. рисунок 3.12), подвергшиеся укрупнению; области, где укрупнение не проведено, отмечены черным.Числа на этой картинке показывают значение синей компонеты цвета в соответствующем пикселе; -“показывает, что узел был исключен из сетки при проведении”укрупнения триангуляции.
Обработке подвергаются только те области, в которыхпогрешность аппроксимированных на укрупненной триангуляции данных не превышает априори заданной верхней грани погрешности ε. Для простоты в данномтесте проводилось только одно укрупнение. Как показано на рисунке 3.13, при92укрупнении образовалось две изолированных области, подвергшихся укрупнениютриангуляции. В таблице 19 в приложении показаны значения аппроксимации синей компонеты цвета для рассматриваемого примера.Рис. 3.12 – Набор данных cutSampleРис. 3.13 – Области укрупнения триангуляции набора данных cutSample длясиней компоненты цветаРезультаты теста cutSample, представленные на рисунке 3.13, показывают, чторассмотренный алгоритм позволяет проводить локальные адаптивные укрупнениясеток узлов на двумерной плоскости; при этом в каждой изолированной областиадаптивное разрежение сетки проводится независимо от остальных областей.93ЗаключениеВ данной главе дано описание выполненной автором компьютерной реализацииалгоритма, предложенного в предыдущей главе.
Приведены результаты тестирования программы на модельных примерах.94ЗаключениеВ работе построена правильная триангуляция двумерной плоскости, допускающая проведение рекуррентных локальных укрупнений, а также рассмотрены вопросы построения сплайн-всплесковых разложений входного набора данных, заданного в вершинах триангуляции. На исходной триангуляции и на ее укрупнениивыполняется построение пространств курантова типа3 ; доказывается вложенностьпространства, соответствующего укрупненной триангуляции, в пространство, соответствующее исходной триангуляции, и строится всплесковое разложение.
Приводятся формулы реконструкции и декомпозиции; выводятся калибровочные соотношения для функций курантова типа. Рассматриваемый алгоритм применим нетолько к плоской области, но и к некоторым двумерным поверхностям: его можноиспользовать для аппроксимаций курантова типа в случае цилиндрической поверхности, тора и сферы.Некоторые из существующих алгоритмов сжатия двумерных наборов данных(например, jpeg) используют преобразование Фурье; в этих алгоритмах реализуется сжатие с потерями. Сплайн-вэйвлетные алгоритмы, позволяющие организовать сжатие без потерь, используются в относительно новых алгоритмах сжатияграфических данных, таких, например, как jpeg2000 и ICER.Заметим, однако, что при обработке данных с помощью этих алгоритмов данныеподвергаются чередующимся последовательностям вертикальных и горизонтальных одномерных вэйвлет-преобразований: сначала преобразуются все строки, азатем все столбцы (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
