автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Представление и эффективное кодирование трехмерных пространственных объектов и связанных с ними растровых графических изображений

УДК 681.3.01 + 539.22 + 528.854 + 519.218

СЕНИЛОВА Елена Михайловна

ПРЕДСТАВЛЕНИЕ И ЭФФЕКТИВНОЕ КОДИРОВАНИЕ ТРЕХМЕРНЫХ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ И СВЯЗАННЫХ С НИМИ РАСТРОВЫХ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ

Специальность:

05.13.01 - Системный анализ, управление и обработка инфо^м^Щф 2012 (в науке и технике)

»12 ЯНВ 2012

Автореферат диссертации на соискание ученой степени кандидата технических наук

Ижевск-2012

005008676

Работа выполнена на кафедре «Программное обеспечение» ФГБОУ ВПО «Ижевский государственный технический университет» (ИжГТУ).

Научный руководитель:

доктор технических наук, профессор Мурынов А.И.

Официальные оппоненты:

доктор технических наук, профессор Малцпа О.В. (ИжГТУ, г. Ижевск);

доктор технических наук, профессор Петров Е.П.

(ФГБОУ ВПО «Вятский государственный университет», г. Киров).

Ведущая организация: ФГБОУ ВПО «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» {г. Санкт-Петербург).

Защита состоится 26 января 2012 г. в 14.00 часов на заседании диссертационного совета Д 212.065.06 в ИжГТУ по адресу: 426069, г. Ижевск, ул. Студенческая, д. 7.

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

С диссертацией можно ознакомиться в библиотеке ИжГТУ, ,с авторефератом - на официальном сайте ИжГТУ: www.istu.ru.

Автореферат разослан 19 декабря 2011 г.

Ученый секретарь диссертационного совета, кандидат технических наук, доцент

В.Н. Сяктерев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность ^смы. Визуализация является самым лучшим и надежным способом просмотра и оценки уже конечного результата проекта перед самым началом работ на самом объекте. Именно визуализация расширяет возможности и максимально удовлетворяет представление об объекте. Архитектурная визуализация - это графическое трехмерное (3D) моделирование на компьютере в сфере архитектурного дизайна

Архитектурное 3D моделирование позволяет увидеть, как будет выглядеть готовое здание еще на стадии проектирования, без чего в наше время невозможно представить разработку и сдачу того или иного проекта. Визуализация архитектурного сооружения необходима для того, чтобы еще до самого строительства на объекте дизайнер-архитектор мог увидеть внешний вид конструкции, учитывая при этом окружающую обстановку и будущие изменения в ней. Кроме этого, 3D визуализация и моделирование необходимо и для заказчика, чтобы было сразу видно, как примерно будет выглядеть еще даже не достроенный комплекс.

Существует много различных графических программ для 3D моделирования, например, такие как Maya, Houdini, Blender, 3ds Max. Последняя программа является лидером 3D моделирования, по крайней мере, в России. Доминирующую роль в цифровом представлении пространственных 3D объектов этих программ играет т.н. TIN-модель - модель триангуляционной нерегулярной сета (Triangulated Irregular Network). Однао TIN-модель является ресурсозатратной, как в смысле объема памяти, так и в смысле времени вычислений, затрачиваемого на создание индексных массивов и последующее вычисление по этим массивам взаимосвязей элементов. Поэтому актуальной является задача более эффективного кодирования пространственных 3D объектов.

Современный дизайн интерьеров также не обходится без 3D моделирования. Используя новейшие технологии в области 3D графики, удается добиваться реалистичных сцен, мало чем, отличимых от реальных фотографий. После того как буду г спроекшро-ваны нужные формы и заданы объемы в виртуальном пространстве, следующим этапом 3D моделирования является наполнение предметов текстурами. Текстуры требуются стенам, полу, потолку, мебели, занавескам и т.д. Материалы для интерьер! 1ых (и не только) сцен можно получить тремя способами. Первый - это библиотеки текстур, создаваемые специально для этих целей различными фирмами и постоянно пополняющиеся. Второй источник получения текстур - это сканер. Его использование особенно актуально для получения текстур обоев и различных видов ткани. Когда же по некоторым причинам невозможно получить образец материала для сканирования, то тут поможет третий источник получения текстуры - цифровой фотоаппарат.

Использование текстурных карт является одним из основных способов получения фотореалистичного изображения и в то же время наиболее ресурсоемкой операцией по отношению к оперативной памяти компьютера. Это связано с тем, что наилучшего качества изображения можно добиться, применяя растровые карты большого разрешения, а это как раз и ведет к максимальному потреблению оперативной памяти. При непродуманном применении большого количества растровых карт ресурсы компьютера будут исчерпаны очень быстро. Кроме того, нельзя не принимать во внимание рост доли аутсорсинговых услуг, предлагаемых архитектурными студиями. Обеспечение возможности интенсивного обмена подобного рода информацией между

внешними исполнителями (аутсорсерами) ставит следующую актуальную задачу: снижение нагрузки на сетевую инфраструктуру таких предприятий за счет более эффективного кодирования и сжатия растровых графических изображений (ГИ).

Решению вышеуказанных задач и посвящена данная диссертационная работа.

Область исследования. Диссертационная работа выполнена в соответствии с пунктами 4 - «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации» и 12 - «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации» паспорта специальности 05.13.01 -«Системный анализ, управление и обработка информации (в науке и технике)».

Объектом исследования являются компьютерная графика; ГИ, их свойства и характеристики, формы представления и кодирования; модели данных пространственных 30 объектов и составляемых ими 30 сцен, их свойства и характеристики; моделирование процессов формообразования, анимации и проецирования 30 объектов.

Предметом исследования являются методы моделирования, анализа, синтеза и кодирования ГИ; адаптивное цветотоновое преобразование (АЦТП) ГИ; центроидное преобразование ГИ; структурно-цветовой анализ (СЦА) ГИ; тетрагональная регулярная сетевая (ТКЫ) модель пространственных 30 объектов; методы проецирования, визуализации и рендеринга пространственных 30 объектов.

Цель работы состоит в проведении комплексных исследований для получения научно-обоснованных методических решений по разработке эффективных дискретных представлений и методов кодирования ГИ и пространственных ЗО объектов, что будет способствовать реализации более высокопроизводительных алгоритмов обработки растровой и 30 график.

Для реализации поставленной цели необходимо решить следующие задачи:

- создать ТШЧ-модель 30 объектов на основе использования полей деформаций пространства (ГТДП), учета отношений смежности между узлами регулярной сети и инциденций между смежными ее связями;

- исследовать возможность оперирования 30 объектами на основе использования непространственных операций склейки узлов и замыкания ТГШ;

- построить единый способ описания процессов формообразования и деформаций ЗБ объектов, как результат действия ПДП на узлы ТЯЫ;

- разработать алгоритм АЦТП для выделения кластеров в цветовом пространстве графического изображения, также провести анализ, выбор и реализацию оптимальной разделяющей функции критерия Байеса для АЦТП;

- оценить влияние стохастических искажений на характеристики кластеров цветовых компонент (ЦК) в процессе АЦТП;

- предложить методику СЦА изображений на основе их АЦТП и центро-идного преобразования;

- провести экспериментальные исследования по оценке эффективности разработанных средств и методов в сравнении с существующими подходами.

Методы исследовании. В работе применялись теоретические и экспериментальные методы исследования.

Теоретические исследования основаны на использовании функционального анализа, теории вероятностей и математической статистики, методов ма-

шинной графики, методов современной геометрии и топологии, методов обработки, анализа и кодирования изображений и других пространственных структур различной размерности, методов распознавания образов.

В экспериментальных исследованиях разработанных моделей и алгоритмов использовались методы моделирования пространственных структур, методы цифровой обработки ГИ, методы анализа, проектирования, кодирования и тестирования программного кода.

Достоверность и обоснованность полученных в работе результатов и выводов подтверждается результатами практического использования разработанных алгоритмов и программных средств, методик и технологий обработки ГИ, методик и технологий обработки пространственной информации, научными трудами и апробациями созданного научно-технического продукта на представительных научных форумах. Достоверность и обоснованность полученных в работе результатов и выводов подтверждена сопоставительным анализом разработанных и существующих математических моделей и методов.

Теоретические положения, выведенные в работе, обосновываются строгостью исходных посылок и корректным применением использованного математического аппарата при выводах аналитических выражений.

Достоверность экспериментальных результатов обеспечена их хорошей согласованностью с теоретически предсказанными характеристиками, а также выбором надежных критериев при построении алгоритмов обработки информации. Исходные данные при выполнении вычислительного эксперимента были тщательно верифицированы и дали хорошую воспроизводимость результатов на больших объемах экспериментального материала.

На защиту выносятся результаты разработки методики СЦА изображений на основе их АЦТП и центроидного преобразования, а также ТЯЫ-моделей данных 30 объектов и составляемых ими ЗЭ сцен, в том числе:

- ТЛЫ-модель для описания структуры поверхности пространственного 30 объекта с учетом ее топологических свойств: гладкости и возможных нерегулярных образований различного порядка;

- результаты исследования возможностей оперирования 30 объектами на основе использования непространственных операций склейки узлов и замыкания

- способ унифицированного описания процессов формообразования и деформаций ЗО объектов, как результата действия ПДП на узлы ТГШ;

- метод анимационных преобразований 30 объектов, построенный на основе комбинирования пространственных операций трансляции и ротации ТЯИ.

- алгоритм АЦТП, предполагающий обработку изображения фильтром, кластеризующим значения ЦК, выделение кластеров этих компонент, распознавание цвета пикселей изображения по выделенным кластерам;

- методика СЦА изображения, включающая его предварительное АЦТП с последующим формированием слоев (стратификацией) и распознаванием в этих слоях структурных элементов (СЭ) изображения на базе центроидного преобразования;

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

- разработана ТЯЫ-модель данных 30 объектов, которая позволяет избежать многих принципиальных трудностей, возникающих при использовании

других моделей пространственных структур, а также является менее ресурсо-затратной и обеспечивает возможность получения более высокоуровневого иерархического представления пространственных объектов;

- предложен метод анимационных преобразований, основанный на использовании двух сопряженных координатных систем с комбинированием пространственных операций трансляции, ротации и масштабирования

- обнаружено, что путем установления прямого соответствия «тетроид-пиксель» ТПЫ может рассматриваться как гибкий растр, образующий гибкую поверхность (Пех-поверхность), благодаря которой получается качественное реалистичное изображение шероховатой тексгурировапной поверхности (аппликативной текстуры).

- построен алгоритм АЦТП, как эффективная информационная технология, позволяющий за приемлемое время автоматически выделять кластеры в цветовом пространстве изображения посредством проекционного кластерного анализа ЦК изображений;

- предложено для предварительной обработки ГИ использовать центроид-ную фильтрацию для эффективного стягивания цветовых кластеров изображения; установлены границы применимости такого фильтра путем оценки влияния стохастических искажений на характеристики кластеров ЦК;

- разработана методика СЦА изображений на основе их АЦТП и центроидного преобразования, обеспечивающая высокую достоверность предварительной обработки ГИ с целью локализации и оценки их СЭ и высокую степень сжатия данных;

Практическая полезность работы. Предложенная методика обработки ГИ алгоритмом АЦТП позволяет снизить количество используемых цветов до минимума при сохранении цвегоразличения, что обеспечивает редукцию тоно-цветовой шкалы без потерь. Кроме того, АЦТП позволяет вести подготовку цветных изображений для их дальнейшего СЦА с целью выделения различных компонент изображений. Посредством АЦТП удается значительно понизить уровень шумов и искажений в изображении, повысить его цветовые и тоновые контрасты, а также помимо улучшения качества удается значительно сжимать объем изображения. Возможность эффективного сжатия растровых ГИ будет способствовать более высокому быстродействию передачи их по сети, что позволит в наибольшей мере удовлетворять коммуникативным потребностям современных архитектурных студий либо в форме виртуальных предприятий, либо при реализации ими аутсорсинговых услуг.

Разработано программное обеспечение терминальной обработки данных о пространственных объектах, реализующее высокопроизводительные алгоритмы оперирования моделями данных пространственных 30 объектов, их представления и кодирования для повышения эффективности архитектурного моделирования. Разработанный программный комплекс поддерживаег форматы данных интерактивных ЗЭ моделей, применяемых в распространенных и используемых в настоящее время системах, обеспечивая тем самым совместимость с ними. Получены оценки эффективности разработанных средств и методов, подтверждающие целесообразность их использования для существенного повышения возможностей архитектурного ЗО моделирования.

Реализация работы в производственных условиях. Полученные результаты использованы при реализации ряда проектов в ОАО «Ижмашпроект».

Созданные программные средства обработки ГИ и эффективного представления ЗО-моделей обеспечили существенное снижение уровня помех и искажений в ис-

пользуемых при визуализации фасадов текстурных каргах, а также быструю загрузку и удобный просмотр в окне браузера интерактивных архитектурных ЗО-моделей.

Апробация работы. Результаты работы докладывались на: 33-й, 34-й и Зб-й международных конференциях «Информационные технологии в науке, социологии, экономике и бизнесе» (Украина, Крым, Ялта-Гурзуф, 2006, 2007 и 2009); X международной конференции по мягким вычислениям и измерениям (Санкт-Петербург, 2007); научной конференции-семинаре «Теория управления и математическое моделирование» (Ижевск, 2008); международном симпозиуме «Надежность и качество» (Пенза, 2009); международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (Дивноморское, Краснодарский край, 2009); молодежной научно-технической конференции «Интеллектуальные системы - 2009» в рамках конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09» (Геленджик-Дивноморское, 2009); 36-й и 37-й международных конференциях «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» (Украина, Крым, Ялта-Гурзуф, 2009 и 2010).

Публикации. Основные научные результаты по теме диссертации опубликованы в 17 научных работах общим объемом 4,4 п.л., авторский вклад -2,2 п.л. Автор имеет 3 научных труда в издании, выпускаемом в РФ и рекомендуемом ВАКом для публикации основных результатов диссертаций.

Структура и объем работы. Диссертация содержит введение, 3 главы, заключение и акт об использовании результатов работы, изложенные на 184 стр. машинописного текста. В работу включены 80 рис., 12 табл., список литературы из 155 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Введение содержит обоснование актуальности темы, формулировку цели и задач работы, основные положения, выносимые на защиту, и определяет содержание и методы выполнения работы.

В первой главе описаны возможности архитектурного моделирования на текущей стадии развития цифровых технологий, рассмотрены основные этапы процесса создания архитектурного проекта, приведен обзор современных программных пакетов для компьютерного проектирования в архитектуре.

Кроме того, проведен анализ представления, кодирования и технологий обработки ГИ, рассмотрены структурно-графические свойства изображений, приведен обзор основных цветовых моделей и цветовых координатных систем.

В главе также рассмотрены задачи эффективного представления и кодирования пространственных 3D объектов, отмечены недостатки TIN-модели при ее расчете и визуализации (рендеринге), приведен обзор методов визуализации 3D объектов.

Во второй главе рассматривается хроматическая TRN-модель пространственных 3D объектов.

В основе построения модели TRN используется понятие тетроида. Тетроидом называется упорядоченная четверка точек t2, ti, t4) (произвольная точка пространства обозначается t = (х, у, z)). Точки 12, /3, называются вершинами тетроида, пространственная замкнутая ломаная линия t^tjjt, - его контуром, отрезки прямых txt2,

¡2 .

Рас. I. Тстронд

/2/3, /3/4. /4/, - его ребрами, а отрезки прямых и /2/4 - его диагоналями (см. рис. 1).

Поскольку прямые и /,г4 в общем случае скрещиваются, то существуют две параллельные плоскости, в одной из которых лежит прямая , а в другой - прямая /2/4. Расстояние между этими плоскостями И называется толщиной тетроида, а параллельная ортогональная проекция контура тетроида на любую из этих плоскостей - его тенью (обозначается 5й(/р /2, /,, Очевидно, что тень тетроида является плоским четырехугольником - тетрагоном. Выпуклая оболочка точек /3, /4 представляет собой в общем случае пространственный

многогранник - тетраэдр, вершинами которого являются вершины тетроида, ребрами - ребра и диагонали тетроида. а грани образуются треугольниками, одной из сторон которых является диагональ тетроида, а две другие стороны - его ребра.

В частном случае, когда точки ?2, !}, /4 лежат в одной плоскости тетроид называется плоским и его толщина /з равна нулю, а сам тетроид совпадает со своей тенью и является плоским четырехугольником - тетрагоном. Допускается также вырожденный тетроид, для которого две вершины одного ребра, совпадают. В этом случае тетроид определяется тремя точками и представляет собой плоскую фигуру - треугольник, а одно из ребер тетроида интерпретируется как скрытое ребро.

Сеть таЫ представляет собой упорядоченный массив от х и точек со связями, образующими прямоугольную решетку (рис. 2). При этом каждая четверка точек, образующих ячейку сети, интерпретируется как тетроид, а упорядочение точек в ячейке происходит так, как показано на рис. 2. Таким образом, сеть ТГШ представляет собой совокупность (т- 1)х(«-1) тетроидов, стыкующихся друг с другом своими ребрами и вершинами и образующих единую связную пространственную конфигурацию.

При моделировании поверхности пространственного объекта сетью Т1Ш точки сети должны лежать на поверхности объекта и близкие по связям сети точки должны также быть пространственно близкими. Конфигурация точек сети на поверхности объекта должна быть достаточно плотной, чтобы воспроизвести все особенности формы поверхности. В общем случае ребра тетроидов не лежат на поверхности объекта, и возникает необходимость определения координат точек поверхности, отличных от точек сети. В отличие от интерполяционных методов аппроксимации поверхностей, использование сети Т1Ш предполагает построение ее из «достаточно малых» (по размерам ребер) и «почти плоских» тетроидов.

Указанные нечеткие критерии формализуются на основании теоремы Эйлера, согласно которой для любой точки гладкой поверхности существуют две ортогональные касательные, такие, что кривизна поверхности по проведенным через них сечениям достигает экстремальных значений (главные значения кривизны), а по всем остальным направлениям кривизна выражается линейной комбинацией главных значений кривизны (формула Эйлера). При этом в окрестности каждой точки гладкой поверхности может наблюдаться одна из следующих четырех ситуаций: оба главные значения кривизны

Рис. 2. Сеть

равны нулю, только одно из главных значений кривизны равно нулю, главные значения кривизны ненулевые и одного знака и главные значения кривизны ненулевые и противоположного знака. В первом случае поверхность в окрестности точки плоская, во втором случае возможно ее цилиндрическое приближение, в третьем - эллипсоидальное приближение, а в четвертом точка является седповой. В первых двух случаях окрестность точки может быть аппроксимирована плоским прямоугольником (во втором случае - ориентированным по направлению ненулевой главной кривизны), во вторых двух случаях - плоской равнобедренной трапецией (подобно ячейкам на сетке параллелей и меридианов на поверхности сферы). Таким образом, окрестность каждой точки может быть точно аппроксимирована малым по размерам ребер тетроидом, размеры которого определяются обратной зависимостью от максимальных значений кривизны таким образом, чтобы его толщина И была на порядок меньше размеров ребер. В этом случае тетроид является «достаточно малым» и «почти плоским» и в определенном смысле подобен своей тени 57г(/,, /2, /3, г4), которая может быть использована в операциях формообразования поверхности объектов и ее трансформациях.

Однако локальная аппроксимация поверхности тетроидом не решает задачи укладки тетроидов по произвольной поверхности и описания ее сингулярных элементов, таких как вершины, ребра и края незамкнутых поверхностей. Для этого вводятся в рассмотрение сингулярные а) выделение б) разрыв в) склейка элементы сети ТШЧ - выделения, разрывы Рис-1 Сингулярные элементы сети и склейки (рис. 3). Выделение вершин и ребер тетроидов позволяет определить вершины и ребра поверхности, соответственно, разрывы связей сети - образовать края незамкнутых поверхностей, а склейки - обеспечить корректную укладку тетроидов.

Все сингулярности сети описываются бинарными индикаторными матрицами узлов и связей, единичные значения которых определяют выделения, разрывы и склейки.

Кроме того, с помощью склеек производится замыкание поверхностей. В зависимости от топологического типа тела, представляющего объект, могут быть построены различные глобальные замыкания сети ТЯЫ (рис. 4). Так, все простые тела являются топологически подобными шару. Поэтому их поверхность может быть представлена как сфероидальное двухполюсное замыкание сети ТЛЫ (сетка параллелей и меридианов; см. рис. 4а). Образование полюсных точек обеспечивает корректное решение задачи укладки тетроидов по моделируемой поверхности. При этом примыкающие к полюсам тетроиды являются вырожденными, а их скрытые ребра подвергаются

Ж

а) сфероидальное двухполюсное

б)тороидальное безполюсное

Рис. 4. Глобальные замыкания сети

склейке. Другой тип глобального замыкания сети характерен для тел, топологически подобных тору (см. рис. 46). В этом случае укладка тетроидов может быть произведена без образования полюсных точек. Таким образом, по типу глобального замыкания сети определяется топологический тип представляющего объект тела.

Упорядоченный характер тетроидов в сети обеспечивает возможность их неявной индексации, что позволяет избежать включения в модель данных громоздких вспомогательных индексных структур, в отличие от других полигональных моделей. За счет этого существенно сокращается объем потребляемой памяти (в 5 раз) и сокращается время доступа к элементам данных в процессе их обработки (минимум в 1,5 раза). При этом обеспечивается также возможность прямого «видения» элементами сети своих соседей, что в еще большей степени сокращает время вычислений, затрачиваемое на оперирование моделями пространственных объектов.

В главе рассматриваются также вопросы, связанные с образованием формы ЗБ объектов, формированием их проекций на плоскость наблюдения, а также обеспечением динамики ЗО-сцен: заданием законов движения тел и формированием анимиро-ванных изображений проекций, основанных на использовании ТЯМ-модели. __

Лцр яЩЦу ф ¡¡¡1 © О

а) формообразование сфе эы в проекции произвольного наблюдателя

ш л 1г с * ■

б) формообразование сферы в проекции г-наблгодателя

-г

в) формообразование тора в проекции произвольного наблюдателя

я- * От 8

г) формообразование тора в проекции г-наблюдателя Рис. 5. Процессы формообразования объектов в различных проекциях Свойство аддитивности ПДП позволяет единообразно описывать процессы формообразования тел, пластичного изменения их формы и последовательного изменения

их положения в пространстве при различных видах движения. В этом случае закон движения определяется последовательностью операторов деформации сети, соответствующих малым приращениям координат. Проецирование полученных состояний деформированной сети обеспечивает получение серии последовательных изображений и, тем самым, позволяет анимировать объекты ЗО-сцен. Если у пользователя есть возможность управления деформациями поверхности тела, его перемещения и движения, то полученная динамическая 30 модель приобретает интерактивный характер.

Различные стадии процесса формообразования объектов показаны на рис. 5.

Реализация динами-

////

////

¿¿/А

'////

«з

ч

W

р

а) трансляция б) масштабирование в) ротация (а=30° Рис. 6. ПДП различных видов движений

ческих процессов (анимация движений), связанных с пространственными 30 телами также производится на основе использования ТЯ1М-модели. При этом любое движение оп-

ределяется комбинацией соответствующих ПДП (см. рис. 6).

Полный набор таких ПДП включает в себя: трансляции Т(а,Ь); ротации Ях(сх), Ях(ос), Ях(а) (нижний индекс определяет ось вращения); масштабирование Э(к); компрессии Сх(ц) (нижний индекс определяет ось компрессии).

деформация 2

у деформация I У

Ж.

ячеики сети

б) вид координатных осей с позиции наблюдателя Рис. 8. Позиции стандартного наблюдателя

а) направление на наблюдателя

Рис. 7 Композиция деформаций сети

Воздействие ПДП на сеть TRN сводится к соответствующему перемещению ее узлов (см. рис. 7). При этом также могут иметь место новые склейки узлов. Формально перемещение узлов сводится к аддитивному преобразованию сети: D\DX = X + DX + DIjc, DXDY = Y + Dy + Dly, DtDZ = Z + D: + Dlz.

Промежуточные состояния сети в этом случае определятся номерами кадров к в последовательности из заданного количества K + I кадров: к ( к к о , к ( к о\ к о к (к о) ,

-Уи+jvu-y)jb 4 =4-41где к=0'К-

Для получения проекций пространственных 3D объектов необходимо определить пространственное положение наблюдателя, которое определяется направлением на него с углом поворота ср в горизонтальной плоскости хОу и уг-

хк. =х°+~(х'!-х°) ' 1 К J J

лом возвышения у/ в вертикальной плоскости, проходящей через ось Ог. Вид координатных осей с позиции наблюдателя на рис. 8.

При формировании проекций пространственных ЗО объектов следует учитывать, что изменение положения наблюдателя эквивалентно противоположному изменению положения объектов, т.е. вполне определенному их перемещению. Поэтому формирование новой проекции также можно представить в виде оператора деформации О,, соответствующего перемещению объекта в пространстве. Это допускает возможность использования единственной базовой проекции, в качестве которой можно выбрать проекцию на плоскость, параллельную плоскости ХУ с направлением наблюдения, противоположным направлению оси 2 (положение г-наблюдателя). В этом случае базовая проекция полностью определяется компонентами 01ОХ = Х + Ох + Ои и О^ВУ - У + £>,.. + .

Решение задачи экранирования ячеек тетрагональной регулярной сети при проецировании выпуклых тел заключается в вычислении индикационной матрицы, которая определяет для каждой ячейки направление порядка обхода узлов ее проекции. Индикационная матрица размера (/и-1)х(я-1) имеет вид: К = [гу ], где элемент матрицы Гц принимает значение 1 при направлении обхода ячейки по часовой стрелке, либо значение 0 - при обратном направлении обхода. С помощью индикационной матрицы отбираются только видимые со стороны наблюдателя ячейки деформированной сети с единичным значением элемента матрицы. Для невыпуклых тел решение

а) каркасный 6} цветовой в) текстурный

Рис. 9. Различные виды рендеринга Малые размеры тетроидов, соизмеримые с величиной пространственного разрешения, и упорядоченный (матричный) характер их размещения в сети позволяют построить простую и эффективную схему хроматизации поверхностей объектов, взаимоувязанную с их пространственным описанием (в отличие от часто используемых схем, основанных на раздельном решении задач описания пространственной модели объекта и описания оптических свойств его поверхности и использования этих свойств при рендеринге в процессе визуализации изображений их проекций; см. рис. 9а).

Здесь следует различать собственный цвет поверхности в заданной точке и цвет в точке изображения проекции объекта на плоскость наблюдения, определяемый процедурами рендеринга, результат которых, в свою очередь, зависит от ориентировки поверхности относительно плоскости наблюдения и параметров проекции. Для одноцветной поверхности при нормализованном рассеянном освещении

объектов и при представлении ее «достаточно малыми» и «почти плоскими» тет-роидами цвет в точке поверхности -может быть определен путем взвешивания собственного цвета поверхности с коэффициентом (меньшим 1), определяемым прямой зависимостью от отношения площади проекции гетроида к его собственной площади в соответствии с заданной шкалой затемнения (см. рис. 96).

■Я-;.

б) Аех-поверхность (каркасный рендеринг) Рис. 10. Гибкий растр

в) йех-поверхность (аппликативный рендеринг)

б) Аех-поверхности (каркасный рендеринг)

а) исходный растр

Различение внешней и внутренней сторон поверхностей производится путем определения порядка обхода (по часовой стрелке или против) проекций вершин гет-роидов. Если порядок обхода в проекции изменился на противоположный, то видимой для наблюдателя является внутренняя сторона поверхности; в противном случае видимой является внешняя сторона. Задача взаимного экранирования поверхностей для ТЯМ-модели решается за счет упорядочения узлов сети по глубине (подобно 2-буферу, только для узлов сети) и последующей последовательной (в направлении к наблюдателю) отри-совке проекций тетроидов.

Для текстурных поверхностей матричный характер сети в сочетании с малыми размерами тетроидов, позволяет произвести хроматизацию поверхностей объектов с помощью растров путем установления прямого соответствия «тетроид-пиксель» после чего, при проецировании также может быть произведена коррекция цвета по заданной шкапе затемнения в зависимости от указанного выше отношения площадей (см. рис. 9в).

В том случае, если ячейки сети, помимо указанных выше условий «достаточно малых» и «почти плоских» тетроидов, имеют форму «достаточно близкую к квадратной», хроматическая модель ТЯЫ может рассматриваться как

в) Яех-поверхности (тоновый рендеринг)

г) Яех-поверхности (аппликативный рендеринг) Рис. 11. Формирование аипликативных текстур из раст ровых текстурных изображении

гибкий растр - деформированная в пространстве плоскость с нанесенным на нее растровым изображением. Понятие гибкого растра позволяет рассматривать модель ТИ/Ы с другой точки зрения, исходя из взаимных отношений между поверхностями объектов и наложенными на них растрами, порождаемых, соответственно, взаимно однозначным соответствием «тетроид-пиксель».

В этом случае, сами растры можно использовать для формирования поверхностей (см. рис. 10). Для этого необходимо создать сеть ТГШ с квадратными ячейками, соответствующими пикселям взятого за исходный растра. Эта сеть должна быть расположена в плоскости абсциссы и ординаты таким образом, чтобы узел с нулевыми значениями индексов находился в начале координат, а связи узлов были бы параллельны абсциссе и ординате, соответственно. Если затем подвергнуть эту сеть деформации, заключающейся в перемещении каждого ее узла в направлении аппликаты на величину, пропорциональную яркости соответствующего пикселя, то образуется гибкая поверхность (Яех-поверхность; см. рис. 106). Эту поверхность можно затем подвергнуть хроматизации тем же исходным растром. В результате образованный гибкий растр будет реапизовывать ап-пликативный рендеринг Яех-поверхности, полученной из исходного растра (см. рис. 1 Ов). 1(0),

Текстура

Цвет

• Каркас

В общем случае получаемые flex-поверхности являются пространственными объектами размерности 2,5; поэтому их использование наиболее целесообразно дня формирования текстуры шероховатых поверхностей (которые, в свою очередь, могут быть подвергнуты последующему деформированию для наложения на поверхность объекта).

Аппликативный рендеринг таких поверхностей исходным растром текстуры позволяет получить качественное реалистичное изображение шероховатой тексту-Рис. 12. Производительность „ь,числе- рированной поверхности (см. рис. 11). По-1шй при визуализации объектов в зави- следующее деформирование этой поверх-симоети от количества узлов сети ности до расположения ее узлов на поверхности моделируемого объекта завершает процесс его формообразования.

С 3 Тем самь|м>за счет хроматизации

j-- , Jr^^-'W? TRN-сети реализуется простая и эффек-

Ш Ж v I i тивная схема высококачественного рен-

к aJI Й Га Ж ''/■ ^ 1 ДеРинга. обеспечивающего высокое ка-

I ** М .' '■: ; . И . |Г чество изображений проекций при ви-

\ 'SyL'f '' Ч - flE г зуализации пространственных 3D объек-

ЩШв^ тов. Достигаемые показатели производи-

тельности вычислительного процесса при рендеринге показаны на рис. 12, а качество изображений проекции объекта с текстурированной поверхностью в сравнении с качеством, обеспечиваемым браузером VRML, показано на рис. 13.

а) TRN-модель б) TIN-модель (VRML) Рис. 13. Качество визуализации объектов при текстурном рендеринге

В третьей главе предложена эффективная информационная технология для обработки цветных ГИ, в том числе описана система АЦТП, разработаны проекционный кластерный анализ ЦК изображений, алгоритмы преобразования и коррекции ГИ, а также показаны возможности их структурного анализа.

АЦТП - непосредственное изменение каждой точки исходного изображения, согласно полученным статистическим характеристикам цветовых кластеров. Посредством АЦТП удается значительно понизить количество шумов и искажений в исходном растре, что, помимо улучшения качества, приводит к заметному уменьшению объема изображения при сжатии. При реализации алгоритма АЦТП используется массив информации, включающий растр размера N хМ исходного цветного изображения, представленный в виде трех матриц Л, С и В, содержащих, соответственно, красную, зеленую и синюю компоненты каждого пикселя, и статистические характеристики, получаемые в результате обработки. Результатами решения является преобразованный растр того же размера, представленный в виде одной матрицы, содержащей значение тоно-цветовой шкалы для каждого пикселя.

АЦТП является, по сути, классификацией цветов исходного изображения по статистическим классам, для чего необходимо уточнить вид разделяющей функции. Независимо от разнообразия ее форм записи, решающие правила остаются эквивалентными. Действие любого из решающих правил сводится к отнесению каждого пикселя изображения определенной области решений, после чего со значением цвета этого пикселя сопоставляется цветовой кластер.

_____у Распределение цветов точек исход' . А | I / /■ ■ ] 1Ы1ГПСЭКЯ ного изображения по цветовым кластерам '/ - носит нормальный характер. Простейшим

приближением разделяющей функции для # _ нормального распределения случайных ве-

^ ч 4 личин является расстояние по Манхеттену.

'\Ч>,„Х Оно определяется как сумма абсолютных

Рис 14 Тестовое ГИ 1 ..

. . «..ит« величин отклонении по всем измерениям в

масштабе среднеквадратических отклонений. В случае использования данной разделяющей функции для исходного изображения (рис. 14) границы областей решений представляют собой прямые линии, как это показано на рис. 15.

Рис. 15. Сечение цветового пространства при использовании метрики по Манхеттену

Рис. 16. Сечение цветового пространства при использовании метрики квадратичного махалонобисового расстояния без учета ковариаций

Рис. 17. Сечение цветового пространства при использовании метрики квадратичного махалонобисового расстояния с учетом ковариаций

При использовании в качестве разделяющей функции метрики квадратичного махалонобисового расстояния без учета ковариаций границы областей решений представляют собой участки эллипсоидов (рис. 16). В случае использования в качестве разделяющей функции метрики квадратичного махалонобисового расстояния с учетом ковариаций границы областей решений представляют собой квадрики и могут принимать любую из общих форм: плоскостей, сфер, эллипсоидов, параболоидов или разного вида гиперболоидов (рис. 17).

Рис. 18. Тестовое ГИ 2 кластеров ГИ 2

АЦТП позволяет снизить количество используемых цветов до того минимума, который был обозначен в процессе анализа цветового пространства изображений, без потери цветоразличения, т.е. происходит редукция тоно-цветовой шкалы без потерь. АЦТП применяется для подготовки цветных изображений к их дальнейшему структурному анализу.

На рис. 18 приведено изображение до проведения АЦТП. Отображение эллипсов рассеяния на уровнях 1а, 2сг и 3 о представлено на рис. 19.

„ „ ........ г-11-> Рис. 21. Результат АЦТП тестового ГИ 2

Рис. 20. Результат АЦ1П тестового ГИ 2 „ ..,„

с коррекциеи ЦК

Сравнение исходного (рис. 18) и изображения, полученного после АЦТП (рис. 20), наглядно показывает улучшение качества восстановленного цветного изображения по сравнению с исходным. Это происходит за счет того, что пикселям изображений придаются значения «чистых» цветов без шумов и помех.

Из полученных после обработки изображений следует, что АЦТП не только сохраняет информацию о цветовых различиях, но и само по себе улучшает качество изображения. Кроме того, результаты АЦТП легко подвергаются любым нелинейным преобразованиям цветотоновой шкалы, выполняемые с це-

лью коррекции имеющихся искажений, повышения цветовой и тоновой контрастности изображения, эквализации текстур, колориметрического регулирования цветов для подавления остаточных шумов и помех и т.д.

На рис. 21 представлен результат работы АЦТП с цветокоррекцией. По сравнению с результатом преобразования на рис. 20, цветовые и тоновые контрасты изображения существенно усилились. Оно, в целом, стало восприниматься как более яркое.

На основе рассмотрения методов представления, анализа, синтеза и кодирования изображений, базирующихся на использовании структурных моделей, была предложена методика СЦА изображений, основанная на использовании двух преобразований: АЦТП и центроидного преобразования, объединяемых кластерным анализом результатов преобразований. Сугь этой методики заключается в том, что для каждого изображения производится статистический анализ распределения значений ЦК в пространстве RGB или ином. При этом выявляются кластеры значений ЦК, которые в дальнейшем используются для распознавания значений ЦК каждого пикселя изображения. В результате, формируется набор слоев двухградационных изображений, соответствующих одному из выявленных кластеров. Этот набор может быть эффективно закодирован, а само изображение легко восстанавливается с помощью простой процедуры декодирования. При этом наблюдается эффект улучшения качества изображения, поскольку выявленные кластеры описывают искажения, имеющие характер помех и шумов. Максимально этот эффект проявляется для ГИ, характеризующихся использованием дискретных цветотоновых шкал в процессах их формирования.

Поскольку полученные бинарные слои выделяют ЦК СЭ изображений, упрощаются процедуры анализа их пространственной структуры, поскольку в каждом слое СЭ обнаруживаются и распознаются с достаточно высокой надежностью. Оверлейные операции «сшивки» слоев при восстановлении изображения не снижают достигнутые показатели надежности, что особенно характерно для ГИ, формируемых с использованием различных легенд или систем условных знаков. Ограниченность набора используемых графических форм позволяет даже повысить вероятность распознавания СЭ при оверлейных операциях.

Рис. 22. Тестовое ГИ 3 Рис. 23. Результат действия рис 24. Результат работы кластеризующего фильтра АЦТП тестового ГИ 3 На рис. 22 показано ГИ, для которого на рис. 25 приведены проекции распрбде-

лений значений его ЦК на плоскости RG, RB и GB. Для данного ГИ отчетливо проявляется эффект кластеризации значений ЦК. Кроме того, из рисунка видно, что для значительной области пространства RGB характерен низкий уровень плотности значений ЦК. Визуально это воспринимается как своеобразный диффузный «межкластерный газ». Этот эффект может снизить надежность выявления кластеров, поскольку нет четкой границы между кластерами и окружающей их межкластерной диффузной средой.

Методика предполагает обработку изображения фильтром, кластеризующим значения ЦК. Фильтр вычисляет средние значения ЦК в окрестности каждого пикселя: , + 1 ¿+1 _ 1 + 1 ./+1 ¿+1 Л!1

R,

I I

Л,.,.

G „

X С

' j

в„

= I

где /,_/' - индексы пикселя на растре; , С,у, лученные значения сравниваются с исходными в этой же окрестности:

' j

= I S В,

/* = ;-1 ./ * = - 1

его RGB-компоненты. По-

Л,.,. -Я,|<р, |С(,

-G, <

где - заданный порог сравнения.

Если все указанные условия соблюдаются, то значениям текущего пикселя преобразованного изображения присваиваются полученные средние значе-

ния Ry = R;j ,

G*j = Gy, В* = By (области выравнивания цветов); в обратном

В'=ВГ

случае сохраняются исходные значения И*

Эффект действия кластеризующего фильтра показан на рис. 23. При сравнении проекций распределений значений ЦК исходного изображения (рис. 25) и тех же распределений после обработки связно-кластерным фильтром (рис. 26) можно отметить, что если до обработки кластеры ЦК слабо выделяются на фоне межкластерной диффузной среды, то после обработки наблюдается более отчетливое выделение кластеров этих компонент.

Для выявленных *ь

кластеров определяются их центры (средние) Як, Ск, Вк и габаритные размеры (среднеквадра-тические отклонения)

°м» где к ~

номер выделенного кластера, которому соответствует определенный цвет из значений дискретной тоноцветовой

шкалы. Эти данные позволяют произвести распознавание цвета пикселей изображения по выделенным кластерам, используя следующее решающее правило:

Рис. 25. Проекции цветовых Рис. 26. Проекции цветовых

кластеров в пространст ве RGB тестового ГИ 3

кластеров в пространстве RGB ГИ на рис. 23

R к =argminmax

R, - &

СТ..,

\в„-вк\

Воспроизводимое после применения АЦТП изображение (рис. 24) отличается от исходного (рис. 22) тем, что шумы и помехи, приводящие к образованию кластеров ЦК из исходной дискретной цветотоновой шкалы, практически, полностью подавлены, а при воспроизведении цветов и тонов этой шкалы произведена цветокоррекция, которая обеспечивает максимальные цветовые контрасты изображения.

Экспериментальные зависимости количества пикселей от величины порога при обработке размытых и зашумленных изображений приведены на рис. 27 и 28. Из них следует, что результаты обработки кластеризующим фильтром исходного ГИ 2 с нанесенным на него гауссовским размытием с варьируемым радиусом апертуры фильтра и того же изображения с нанесенными на него гауссовскими шумом и размытиями, принимаемыми различные значения, обладают выраженным сходством.

Этот же эффект наблюдается при сравнении результатов, полученных в ходе обработки зашумленных изображений, с изображениями, к которым сначала применялась гаус-совская фильтрация и только после наносился шум.

Наложение гауссов-ского шума на исходное изображение придает ему некоторую зернистость, т.е. шум в изображении представляет собой пиксели со случайными цветовыми значениями. С увеличением уровня зашумленности работа центроидного фильтра по обнаружению цветовых кластеров становится малоэффективной. В ходе проведения анализа данных, полученных при обработке кластеризующим фильтром исходного изображения и изображений с нанесенными размытием (его проекции на рис. 29а), шумом (его проекции на рис. 296) и их вариациями, были получены коэффициенты детерминации, отражающие степень адекватности найденных зависимостей изменения объема экстентов кластеров от величины порога реальным процессам.

1 . 6 _ 11 .. г1 "ч М .. П6 _ 41 N.11/11

П-нсхеднмП Ц-рашшн-МО Ц - рлчмыпк I 5 Ц-ртмшие 21> Ц-рпэмшие.*о

Рис. 27. Гистограммы изменения количества кластеризованных пикселей в процессе обработки кластеризующим фильтром Г'И в зависимости от величины порога при изменении радиуса апертуры гауссовского фильтра

3506000

Ш- 1ГПМЫ I >'

§11

Рис. 28. Гистограммы изменения количества кластеризованных пикселей в процессе обработки кластеризующим фильтром в зависимости от величины порога при изменении доли гауссовского шума на исходном ГИ

Методика СЦА предполагает для обеспечения совместимости АЦТП с центроидным преобразованием формирование слоев (стратификацию) изображения, соответствующих выделенным кластерам. При этом Moiyr быть получены бинарные (двух градационные) изображения - каж- Рис. 29. Проекции цветовых кластеров в пространстве дый слой окрашивается в RGB ги с гяуссовским размытием (а) и шумом (б) определенный цвет (черный) на фоне подложки изображения (белого цвета).

Последующая обработка данных заключается в применении центроидного преобразования для каждого выделенного слоя изображения. Центроидное преобразование строится на основе моментов, вычисляемых на скользящем (сканирующем) интервале заданной длины п по строкам и по столбцам растра: 1

2 п +1

где 1У1к - момент А-го порядка на интервале длины 2л+ 1 с центром в I -ой точке строки (столбца) растра; - значение

¡-го пикселя.

По значениям моментов вычисляются текущие значения производных характеристик: массы центроида С1=Щ]/М1,

диссипации Н: =()^2/А/,)-С/,

экстента И, = ф 2Я, .

Кроме того, по текущим значениям центроида вычисляются интегральные значения центроида С*(у). Используется рекуррентная схема вычислений:

Рис. 30. Центроидное преобразование

С*(о) = 0, С*(у +1) = С*(у) +1, если выполняется условие г = у + Су.

Эффект действия центроидного преобразования показан на рис. 30. Как видно из рисунка, при прохождении скользящим интервалом линейного элемента изображения образуется отчетливо выраженный пик значений интегрального центроида, а при прохождении интервалом контура планарного элемента имеет место эффект переноса значений центроида из области, примыкающей к элементу, во внутреннюю область, примыкающую к его контуру. На этом основано обнаружение СЭ. Распознавание и оценка характеристик СЭ производится на основании соотношений между значениями массы и экстента. Ширина линейного элемента совпадает со значением экстента к, а значение пикселя определяется отношением М/И . Из рисунка видно, что наибольшую чувствительность центроидный фильтр проявляет по отношению к двухградационным изображениям, что обеспечивает взаимную согласованность АЦТП и центроидного преобразования в методике СЦА за счет стратификации изображений (рис. 31).

_ _ _

4§£

и^вва

.'кГ.^Д

а) контурная часть изображения

ШШш!

-От

т-

\

1 ..

й

ш

б) слой к = 1

■43

ШвшШ

в) слой к = 2

."Л;

г) слой к = 3

е) слой к = 5

д) слой к = 4

Рис. 31. Цветовая стратификация тестового ГИ 2

Бинаризованные изображения на рис. 31 показывают, что и линейные, и планарные элементы структуры выделяются достаточно отчетливо, что обеспечивает высокое качество работы центроидного фильтра. Более того, восстановленное после распознавания ГИ в его послойном представлении (за исключением отдельных одиночных пикселей) не отличается от набора слоев на рис. 31.

ЗАКЛЮЧЕНИЕ

1. Исследованы возможности оперирования пространственными 30 объектами на основе использования непространственных операций склейки узлов и замыкания ТЯИ и пространственных операций трансляции, ротации, масштабирования, компрессии и пластичной деформации сетей. Установлено, что указанный набор операций обладает необходимой полнотой для реализации всех необходимых преобразований пространственных ЗЭ объектов.

2. В том случае, если ячейки сети имеют форму «достаточно близкую к квадратной», хроматическая модель может рассматриваться как гибкий

растр - деформированная в пространстве плоскость с нанесенным на нее растровым изображением. Если затем подвергнуть эту сеть деформации пропорциональную яркости соответствующего пикселя, то образуется гибкая поверхность (Аех-ловерхность), которую можно затем подвергнуть хроматизации тем же исходным растром. В результате, образованный гибкий растр будет реапи-зовывать аппликативный рендеринг Аех-поверхности. Его использование наиболее целесообразно для формирования текстуры шероховатых поверхностей.

3. Разработаны алгоритмы оперирования моделями данных пространственных 30 объектов, обеспечивающие высокую производительность вычислительного процесса и снижение используемых ресурсов памяти, в частности, разработаны быстрые алгоритмы проецирования и визуализации 30 объектов на основе исследования проекционных пространственных преобразований трансляции, ротации, масштабирования и компрессии ТЯМ

4. По сравнению с ручным выделением цветовых кластеров по ключевым участкам исходного изображения разработанный автором алгоритм АЦТП в значительной степени дает выигрыш в скорости и удобстве обработки изображений. Получаемые статистические характеристики цветовых кластеров достаточно полно описывают изображение и позволяют провести АЦТП.

5. Установлено, что в результате обработки изображений кластеризующим фильтром при увеличении радиуса апертуры гауссовского фильтра наблюдается эффект расплывания кластеров ЦК изображения с повышением порога, поскольку в процессе гауссовского размытия цвет каждого пикселя распространяется среди соседних, что приводит к размытию границ кластеров цветового пространства и делает практически труднореализуемой задачу выделения ЦК.

6. Обнаружен новый эффект работы центроидного фильтра: при обработке исходного изображения и помещении результатов на чистый белый растр происходит выделение только тех точек изображения, которые удовлетворяют некоему порогу. Порог - это величина, на которую необходимо превышение хотя бы одной из компонент (Я, О, В) среднего значения кодовых слов сканирующего окна (3x3) по растру цветного изображения значения кодового слова любого из 8 пикселей, расположенных по периметру этого окна. В результате, выделяются непрерывные цветовые зоны.

НАУЧНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Статьи в журналах, рекомендованных ВАК РФ

1. Мурынов А.И., Сенилова Е.М. Структурно-цветовой анализ изображений на основе адаптивного цветотонового и центроидного преобразований // Вестник Ижевского государственного технического университета. - Ижевск: Изд-во ИжГТУ, 2009. - № 3 (43). - С. 144-150.

2. Сенилова Е.М. Формирование Аех-поверхностей из растровых текстурных изображений на базе тетроидной регулярной модели трехмерных пространственных объектов // Вестник Ижевского государственного технического университета. - Ижевск: Изд-во ИжГТУ, 2011. - № 1 (49). - С. 141-143.

3. Мурынов А.И., Сенилова Е.М. Моделирование трехмерных объектов на основе тетрагональной регулярной пространственно деформируемой сети // Вестник Ижевского государственного технического университета. - Ижевск:

Изд-во ИжГТУ, 2011. - № 2 (50). - С. 158-163.

11. Материалы международных и всероссийских конференций

4. Макарова OJL, Мурьшов А.И., Сенилова Е.М. Тетроидная регулярная сеть как модель пространственных объектов размерности 3 // Информационные технологии в науке, социологии, экономике и бизнесе. Материалы 33-й междунар. конф. - Украина, Крым, Ялта-Гурзуф: прилож. к журн. «Открытое образование», 2006. - С. 181 -182.

5. Мурынов А.И., Сенилова Е.М. Хроматическая TRN-модель пространственных объектов // Информационные технологии в науке, социологии, экономике и бизнесе. Материалы 33-й междунар. конф. - Украина, Крым, Ялта-Гурзуф: прилож. к журн. «Открытое образование», 2006. - С. 186-187.

6. Мурынов А.И., Сенилова Е.М. Тетроидная регулярная сетевая модель трехмерных пространственных объектов и сцен // Сборник докладов X международной конференции по мягким вычислениям и измерениям. - Т. 1. - СПб • Изд-во СПбГЭТУ «ЛЭТИ», 2007.-С. 162-165.

7. Сенилова Е.М. Гибкие растры и аппликативные текстуры для моделирования трехмерных пространственных объектов // Информационные технологии в науке, социологии, экономике и бизнесе. Материалы 34-й междунар. конф. - Украина, Крым, Ялта-Гурзуф: прилож. к журн. «Открытое образование», 2007. - С. 192-194.

8. Сенилова Е.М. Модели гибкого растра и flex-поверхностей // Теория управления и математическое моделирование. Труды научной конференции-семинара. - Ижевск: Изд-во ИжГТУ, 2008. - С. 59.

9. Лялин В.Е., Сенилова Е.М. Интеллектуальная информационная технология для создания единой информационной системы обработки результатов фотосъемок архитектурных студий как виртуальных предприятий // Надежность и качество. Труды международного симпозиума. В 2-х томах / Под ред. Н.К. Юркова. - Пенза: Изд-во Пенз. гос. ун-та, 2009. - Т. 1. - С. 44-49.

10.Сенилова Е,М. Обработка результатов архитектурной и интерьерной фотосъемок на основе адаптивного цветотонового преобразования II Информационные технологии в науке, образовании, телекоммуникации и бизнесе. Материалы 36-й междунар. конф. - Украина, Крым, Ялта-Гурзуф: прилож. к журн. «Открытое образование», 2009. - С. 106-109.

П.Лялин В.Е., Сенилова Е.М. Способ классификации точек изображения по кластерам в системе адаптивного цветотонового преобразования // Многопроцессорные вычислительные и управляющие системы. Материалы международной научно-технической конференции. В 2-х томах. - Таганрог: Изд-во ТТИ ЮФУ, 2009. - Т. 2.-С. 190-193.

12. Сенилова Е.М. Алгоритм выделения габаритных контейнеров цветовых кластеров по их проекциям // Многопроцессорные вычислительные и управляющие системы. Материалы международной научно-технической конференции. В 2-х томах. - Таганрог: Изд-во ТТИ ЮФУ, 2009. - Т. 2. - С. 222-225.

13.Лялин В.Е., Сенилова Е.М. Варианты систем разделяющих функций байесовского классификатора цветов для адаптивного цветотонового преобразования изображений // AIS-IT'09. Труды конгресса по интеллектуальным системам и информационным технологиям. Научное издание в 4-х томах. - М.: Физматлит, 2009. - Т. 3. - С. 238-245.

14.Сенилова Е.М. Стягивание цветовых кластеров изображения с помощью центроидного фильтра при структурном анализе изображений // А18-1Т'09. Труды конгресса по интеллектуальным системам и информационным технологиям. Научное издание в 4-х томах. -М.: Физматлит, 2009.-Т. 3. - С. 315-321.

15. Пивоваров И.В., Сенилова Е.М. Исследование влияния стохастических искажений на характеристики кластеров цветовых компонент в процессе структурного анализа изображений // Информационные технологии в науке, социологии, экономике и бизнесе. Материалы 36-й междунар. конф. - Украина, Крым, Ялта-Гурзуф: прилож. к журн. «Открытое образование», 2009. - С. 119-122.

16.Мурынов А.И., Сенилова Е.М. Процессы формообразования, анимации и проецирования трехмерных пространственных объектов с использованием тетрагональной регулярной сетевой модели // Информационные технологии в науке, социологии, экономике и бизнесе. Материалы 36-й междунар. конф. - Украина, Крым, Ялта-Гурзуф: прилож. к журн. «Открытое образование», 2009. - С. 117-119.

17. Сенилова Е.М. Трехмерное представление геометрико-топологических пространственных объектов с помощью тетрагональной регулярной пространственной сети // Информационные технологии в науке, образовании, телекоммуникации и бизнесе. Материалы 37-й междунар. конф. - Украина, Крым, Ялта-Гурзуф: прилож. к журн. «Открытое образование», 2010. - С. 309-311.

Е.М. Сенилова

В авторской редакции

Подписано в печать 19. 12.11. Усл. печ. л. 1,4. Заказ N»410. Тираж 100 экз.

Издательство Ижевского государственного технического университета Отпечатано в типографии Издательства ИжГТУ. 426069, Ижевск, Студенческая, 7

61 12-5/1617

ФГБОУ ВПО «ИЖЕВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

На правах рукописи

СЕНИЛОВА Елена Михайловна

УДК 681.3.01 + 539.22 + 528.854 + 519.218

ПРЕДСТАВЛЕНИЕ И ЭФФЕКТИВНОЕ КОДИРОВАНИЕ ТРЕХМЕРНЫХ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ И СВЯЗАННЫХ С НИМИ РАСТРОВЫХ ГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ

Специальность:

05.13.01 - Системный анализ, управление и обработка информации

(в науке и технике)

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

доктор технических наук, профессор МУРЫНОВ А.И.

Ижевск-2012

ОГЛАВЛЕНИЕ

Стр.

Введение....................................................................................................................5

1. Анализ методов компьютерной графики в архитектурном моделировании и визуализации....................................................................................13

1.1. Современные возможности компьютерного проектирования и трехмерной визуализации в архитектуре..................................................13

1.1.1. Процесс создания архитектурного проекта..........................13

1.1.2. Обзор современных программных пакетов для архитектурного моделирования и визуализации........................................20

1.2. Задачи представления и эффективного кодирования трехмерных пространственных объектов.......................................................................23

1.2.1. Цифровые представления и модели трехмерных пространственных объектов...................................................................23

1.2.2. Методы визуализации трехмерных пространственных объектов.............................................................................................27

1.2.3. Сетевые решения в интерактивном трехмерном моделировании...............................................................................................29

1.3. Представление, кодирование и технологии обработки графических изображений........................................................................................32

1.3.1. Структурно-графические свойства изображений................32

1.3.2. Основные цветовые модели и цветовые координатные системы..............................................................................................36

1.3.3. Компьютерное представление графической информации . 52

1.3.4. Методы обработки цифровых изображений........................61

1.4. Постановка цели и задач исследований.............................................65

2. Процессы формообразования, анимации и проецирования тетрагональной регулярной сетевой модели трехмерных пространственных

объектов.................................................................................................................67

2.1. Поля деформаций пространства.........................................................67

2.2. Тетрагональная регулярная сеть.........................................................69

2.3. Характеристики сетей..........................................................................72

2.4. Непространственные операции над сетями.......................................74

2.4.1. Локальные склейки узлов.......................................................76

2.4.2. Замыкания сети.......................................................................78

2.4.3. Операции форматирования сетей..........................................82

2.5. Пространственные операции над сетями...........................................84

2.6. Формообразование и деформации объектов.....................................86

2.7. Пространственные трансформации трехмерных сцен.....................95

2.8. Проецирование, визуализация и рендеринг трехмерных пространственных объектов.............................................................................100

2.9. Экспериментальные данные и результаты........................................108

2.10. Полученные результаты и выводы...................................................117

3. Разработка эффективной информационной технологии обработки цветных графических изображений................................................................120

3.1. Описание системы адаптивного цветотонового преобразования изображений.................................................................................................120

3.2. Проекционный кластерный анализ цветовых компонент изображений ............................................................................................................124

3.2.1. Математическое описание кластеров...................................125

3.2.2. Классификация точек изображения по кластерам...............127

3.2.3. Выделение габаритных контейнеров цветовых кластеров по их проекциям................................................................................130

3.3. Преобразование и цветокоррекция графических изображений......134

3.4. Возможности структурного анализа изображений...........................143

3.4.1. Стягивание цветовых кластеров изображения с помощью центроидного фильтра......................................................................145

3.4.2. Влияние стохастических искажений на характеристики

кластеров цветовых компонент.......................................................148

3.4.3. Возможности структурного анализа изображений.............160

3.5. Полученные результаты и выводы.....................................................164

Заключение...........................................................................................................167

Список литературы.............................................................................................169

Приложение. Акт об использовании результатов работы..........................183

ВВЕДЕНИЕ

Актуальность темы. Визуализация является самым лучшим и надежным способом просмотра и оценки уже конечного результата проекта перед самым началом работ на самом объекте. Именно визуализация расширяет возможности и максимально удовлетворяет представление об объекте. Архитектурная визуализация - это графическое трехмерное (3D) моделирование на компьютере в сфере архитектурного дизайна.

Архитектурное 3D моделирование позволяет увидеть, как будет выглядеть готовое здание еще на стадии проектирования, без чего в наше время невозможно представить разработку и сдачу того или иного проекта. Визуализация архитектурного сооружения необходима для того, чтобы еще до самого строительства на объекте дизайнер-архитектор мог увидеть внешний вид конструкции, учитывая при этом окружающую обстановку и будущие изменения в ней. Кроме этого, 3D визуализация и моделирование необходимо и для заказчика, чтобы было сразу видно, как примерно будет выглядеть еще даже не достроенный комплекс.

Существует много различных графических программ для 3D моделирования, например, такие как Maya, Houdini, Blender, 3ds Max. Последняя программа является лидером 3D моделирования, по крайней мере, в России. Доминирующую роль в цифровом представлении пространственных 3D объектов этих программ играет т.н. TIN-модель - модель триангуляционной нерегулярной сети (Triangulated Irregular Network). Однао TIN-модель является ресурсо-затратной, как в смысле объема памяти, так и в смысле времени вычислений, затрачиваемого на создание индексных массивов и последующее вычисление по этим массивам взаимосвязей элементов. Поэтому актуальной является задача более эффективного кодирования пространственных 3D объектов.

Современный дизайн интерьеров также не обходится без 3D моделирования. Используя новейшие технологии в области 3D графики, удается добивать-

ся реалистичных сцен, мало чем, отличимых от реальных фотографий. После того как будут спроектированы нужные формы и заданы объемы в виртуальном пространстве, следующим этапом ЗБ моделирования является наполнение предметов текстурами. Текстуры требуются стенам, полу, потолку, мебели, занавескам и т.д. Материалы для интерьерных (и не только) сцен можно получить тремя способами. Первый - это библиотеки текстур, создаваемые специально для этих целей различными фирмами и постоянно пополняющиеся. Второй источник получения текстур - это сканер. Его использование особенно актуально для получения текстур обоев и различных видов ткани. Когда же по некоторым причинам невозможно получить образец материала для сканирования, то тут поможет третий источник получения текстуры - цифровой фотоаппарат.

Использование текстурных карт является одним из основных способов получения фотореалистичного изображения и в то же время наиболее ресурсоемкой операцией по отношению к оперативной памяти компьютера. Это связано с тем, что наилучшего качества изображения можно добиться, применяя растровые карты большого разрешения, а это как раз и ведет к максимальному потреблению оперативной памяти. При непродуманном применении большого количества растровых карт ресурсы компьютера будут исчерпаны очень быстро. Кроме того, нельзя не принимать во внимание рост доли аутсорсинговых услуг, предлагаемых архитектурными студиями. Обеспечение возможности интенсивного обмена подобного рода информацией между внешними исполнителями (аутсорсерами) ставит следующую актуальную задачу: снижение нагрузки на сетевую инфраструктуру таких предприятий за счет более эффективного кодирования и сжатия растровых графических изображений (ГИ).

Решению вышеуказанных задач и посвящена данная диссертационная работа.

Область исследования. Диссертационная работа выполнена в соответствии с пунктами 4 - «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки инфор-

мации» и 12 - «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации» паспорта специальности 05.13.01 - «Системный анализ, управление и обработка информации (в науке и технике)».

Объектом исследования являются компьютерная графика; ГИ, их свойства и характеристики, формы представления и кодирования; модели данных пространственных ЗВ объектов и составляемых ими ЗВ сцен, их свойства и характеристики; моделирование процессов формообразования, анимации и проецирования ЗВ объектов.

Предметом исследования являются методы моделирования, анализа, синтеза и кодирования ГИ; адаптивное цветотоновое преобразование (АЦТП) ГИ; центроидное преобразование ГИ; структурно-цветовой анализ (СЦА) ГИ; тетрагональная регулярная сетевая (ТК!Ч) модель пространственных ЗВ объектов; методы проецирования, визуализации и рендеринга пространственных ЗВ объектов.

Цель работы состоит в проведении комплексных исследований для получения научно-обоснованных методических решений по разработке эффективных дискретных представлений и методов кодирования ГИ и пространственных ЗВ объектов, что будет способствовать реализации более высокопроизводительных алгоритмов обработки растровой и ЗВ график.

Для реализации поставленной цели необходимо решить следующие задачи:

- создать ТЮЧ-модель ЗВ объектов на основе использования полей деформаций пространства (ПДП), учета отношений смежности между узлами регулярной сети и инциденций между смежными ее связями;

- исследовать возможность оперирования ЗВ объектами на основе использования непространственных операций склейки узлов и замыкания ТИЧ;

- построить единый способ описания процессов формообразования и деформаций ЗВ объектов, как результат действия ПДП на узлы Т1Ш;

- разработать алгоритм АЦТП для выделения кластеров в цветовом пространстве графического изображения, также провести анализ, выбор и реализацию оптимальной разделяющей функции критерия Байеса для АЦТП;

- оценить влияние стохастических искажений на характеристики кластеров цветовых компонент (ЦК) в процессе АЦТП;

- предложить методику СЦА изображений на основе их АЦТП и центро-идного преобразования;

- провести экспериментальные исследования по оценке эффективности разработанных средств и методов в сравнении с существующими подходами.

Методы исследования. В работе применялись теоретические и экспериментальные методы исследования.

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

В экспериментальных исследованиях разработанных моделей и алгоритмов использовались методы моделирования пространственных структур, методы цифровой обработки ГИ, методы анализа, проектирования, кодирования и тестирования программного кода.

Достоверность и обоснованность полученных в работе результатов и выводов подтверждается результатами практического использования разработанных алгоритмов и программных средств, методик и технологий обработки ГИ, методик и технологий обработки пространственной информации, научными трудами и апробациями созданного научно-технического продукта на представительных научных форумах. Достоверность и обоснованность полученных в работе результатов и выводов подтверждена сопоставительным анализом разработанных и существующих математических моделей и методов.

Теоретические положения, выведенные в работе, обосновываются стро-

гостью исходных посылок и корректным применением использованного математического аппарата при выводах аналитических выражений.

Достоверность экспериментальных результатов обеспечена их хорошей согласованностью с теоретически предсказанными характеристиками, а также выбором надежных критериев при построении алгоритмов обработки информации. Исходные данные при выполнении вычислительного эксперимента были тщательно верифицированы и дали хорошую воспроизводимость результатов на больших объемах экспериментального материала.

На защиту выносятся результаты разработки методики СЦА изображений на основе их АЦТП и центроидного преобразования, а также ТКИ-моделей данных ЗЭ объектов и составляемых ими ЗБ сцен, в том числе:

- ТЮЧ-модель для описания структуры поверхности пространственного ЗБ объекта с учетом ее топологических свойств: гладкости и возможных нерегулярных образований различного порядка;

- результаты исследования возможностей оперирования ЗО объектами на основе использования непространственных операций склейки узлов и замыкания ТИЧ;

- способ унифицированного описания процессов формообразования и деформаций ЗЭ объектов, как результата действия ПДП на узлы ТИМ;

- метод анимационных преобразований ЗБ объектов, построенный на основе комбинирования пространственных операций трансляции и ротации Т11К.

- алгоритм АЦТП, предполагающий обработку изображения фильтром, кластеризующим значения ЦК, выделение кластеров этих компонент, распознавание цвета пикселей изображения по выделенным кластерам;

- методика СЦА изображения, включающая его предварительное АЦТП с последующим формированием слоев (стратификацией) и распознаванием в этих слоях структурных элементов (СЭ) изображения на базе центроидного преобразования.

Научная новизна результатов диссертационного исследования, полу-

ченных лично автором, заключается в следующем:

- разработана ТЮ4-модель данных ЗБ объектов, которая позволяет избежать многих принципиальных трудностей, возникающих при использовании других моделей пространственных структур, а также является менее ресурсо-затратной и обеспечивает возможность получения более высокоуровневого иерархического представления пространственных объектов;

- предложен метод анимационных преобразований, основанный на использовании двух сопряженных координатных систем с комбинированием пространственных операций трансляции, ротации и масштабирования ТШЧ;

- обнаружено, что путем установления прямого соответствия «тетроид-пиксель» может рассматриваться как гибкий растр, образующий гибкую поверхность (йех-поверхность), благодаря которой получается качественное реалистичное изображение шероховатой текстурированной поверхности (ап-пликативной текстуры);

- построен алгоритм АЦТП, как эффективная информационная технология, позволяющий за приемлемое время автоматически выделять кластеры в цветовом пространстве изображения посредством проекционного кластерного анализа ЦК изображений;

- предложено для предварительной обработки ГИ использовать центро-идную фильтрацию для эффективного стягивания цветовых кластеров изображения; установлены границы применимости такого фильтра путем оценки влияния стохастических искажений на характеристики кластеров ЦК;

- разработана методика СЦА изображений на основе их АЦТП и центро-идного преобразования, обеспечивающая высокую достоверность предварительной обработки ГИ с целью локализации и оценки их СЭ и высокую степень сжатия данных.

Практическая полезность работы. Предложенная методика обработки ГИ алгоритмом АЦТП позволяет снизить количество используемых цветов до минимума при сохранении цветоразличения, что обеспечивает редукцию тоно-

и

цветовой шкалы без потерь. Кроме того, АЦТП позволяет вести подготовку цветных изображений для их дальнейшего СЦА с целью выделения различных компонент изображений. Посредством АЦТП удается значительно понизить уровень шумов и искажений в изображении, повысить его цветовые и тоновые контрасты, а также помимо улучшения качества удается значительно сжимать объем изображения. Возможность эффективного сжатия растровых ГИ будет способствовать более высокому быстродействию передачи их по сети, что позволит в наибольшей мере удовлетворять коммуникативным потребностям современных архитектурных студий либо в форме виртуальных предприятий, либо при реализации ими аутсорсинговых услуг.

Разработано программное обеспечение терминальной