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

Московский государственный университет имени М. В. Ломоносова Механико-математический факультет

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

Шокуров Антон Вячеславович

Метод адаптивного интерактивного анализа растровых изображений изменяемой детализации

Специальность 05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 ЗЯНВ2011

Москва - 2010

004618903

Работа выполнена на кафедре вычислительной математики Механико-математического факультета Московского государственного университета имени М. В. Ломоносова

Научный руководитель: доктор физико-математических наук,

профессор Михалев Александр Васильевич-,

Официальные оппоненты: доктор физико-математических наук,

профессор Соколов Сергей Михайлович",

доктор технических наук, профессор Назиров Равилъ Равилъевич.

Ведущая организация: Учреждение Российской Академии Наук Геофизический центр РАН.

Защита состоится 29 декабря 2010 г. в 16 часов 45 минут на заседании диссертационного совета Д.501.002.16 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы д. 1, МГУ, Главное здание, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ имени М. В. Ломоносова (14 этаж, Главное здание).

Автореферат разослан 29 ноября 2010 г.

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

А. А. Корнев

Общая характеристика работы

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

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

следнее подчеркивает важность разработки метода фильтрации неактуальной визуальной информации.

С учетом представленных соображений тема диссертации является актуальной и соответствует областям исследований в сфере теоретической информатики, а именно - к исследованию и разработке методов и алгоритмов анализа, распознавания и синтеза растровых изображений, что отражено в п.п. 5, 7 Паспорта специальности 05.13.17 "Теоретические основы информатики".

Задача интерактивного анализа растровых изображений в той или иной степени решается путем применения программных средств, реализующих метод (стандарт) JPEG, который основан на дискретном косинусном преобразовании (ДКП). Однако, большинство методов, основанных на ДКП имеют существенные недостатки. Альтернативный подход к кодированию растровых изображений основан на теории вейвлет-преобразований, который устраняет большинство имеющихся у ДКП недостатков, а именно - устраняется избыточность кодированного потока данных и объем передаваемой клиенту данных.

Можно выделить два способа при кодировании вейвлет-преобразованного растрового изображения, а именно — внутриподдиапазонный и межподдиапа-зонный. Внутриподдиапазонные методы (например, ЕВСОТ, SPECK и SWEET) основаны на устранении корреляции между соседними вейвлет-коэффициента-ми в каждом из поддиапапазонов по отдельности. К недостатку метода ЕВСОТ можно отнести сложный характер его преобразования. К недостаткам самого метода JPEG2000 следует отнести существенное время, затрачиваемое на извлечение фрагментов, и несоответствие объема данных при извлечении небольших фрагментов. Межподдиапазонные методы основаны на устранении корреляции между вейвлет-коэффициентами, принадлежащими к разным вейвлет-поддиапазонам. Метод SPIHT является ключевым в данной категории и его можно использовать при произвольном вейвлет-преобразовании. Данный метод очень часто применяется при сравнительном тестировании новых методов кодирования растровых изображений.

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

Все изложенное выше позволяет сделать вывод, что проблема кодирова-

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

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

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

К числу новых научных положений, представленных в диссертации, можно отнести следующие.

• Представление растрового изображения изменяемой детализации, основанное на его вейвлет-представлении.

• Метод кодирования, основанный на методе БРИТ, данного представления, допускающий интерактивный анализ изображения. Доказана независимость объема используемой алгоритмами кодирования/декодирования оперативной памяти от размера данного изображения.

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

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

• Алгоритм адаптивного извлечения фрагментов изображения, который позво-

ляет существенно снизить (доказаны оценки) степень загрузки вычислительной системы при извлечении больших фрагментов из кодированного потока данных сформированного под извлечение небольших фрагментов. • Программная реализация разработанного метода и результаты её тестовых испытаний.

Методы исследований. В работе использованы методы вейвлет-анализа, кодирования информации, топологии, компьютерной графики и системного программирования.

Теоретическая значимость работы. Применение методов на базе метода 8Р1НТ не ограничивается исключительно двумерным пространством, использованием вейвлет-преобразования и кодированием визуальных данных. Существует большое число статей, посвященных альтернативному применению метода БРШТ, в частности, применительно к трехмерному пространству, к совместному с ДКП и ЕВСОТ кодированию и к кодированию аудио данных. По этой причине задачу, решение которой представлено в диссертации, можно рассматривать как заявку на решение аналогичной задачи при альтернативных применениях метода ЭРШТ.

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

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

Апробация работы. Результаты работы были представлены на "Ломоносовских чтениях—2007" на кафедре вычислительной математики мех-мат факультета МГУ им. М.В. Ломоносова в 2007 г.; на специальном семинаре "Машинная графика" на мех-мат факультете МГУ им. М.В. Ломоносова в 2008 г.; на семинаре "Машинная графика и обработка изображений" на факультете ВМиК МГУ им. М.В. Ломоносова в 2008/2010 г.; на объединённом семинаре по робототехническим системам ИПМ им. М.В. Келдыша РАН, МГУ им. М.В. Ломоносова, МГТУ им. Н.Э. Баумана, ИНОТиИ РГТУ в 2010 г.; на семинаре "Проблемы современных информационно-вычислительных систем" на мех-мат факультете МГУ им. М.В. Ломоносова в 2010 г.; на совместном семинаре Геофизического центра РАН и Института космических исследований РАН в 2010 г.

1 Пиковое отношение сигнала к шуму (в англоязычной литературе РБКЯ) является стандартной метрикой (измеряется в децибелах) измерения схожести между двумя растровыми изображениями.

Публикации. По теме диссертации опубликованы 3 статьи (см. [Al, А2, A3]) в журналах из перечня, рекомендованного ВАК Минобрнауки России.

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

Структура и объем диссертации. Диссертационная работа объемом 129 страниц состоит из введения, краткого обзора истории исследований, пяти глав, заключения, списка публикаций и цитированной литературы. Работа содержит 34 рисунка, 7 таблиц и 46 алгоритмов. Список литературы включает 155 наименования. Приложения к диссертационной работе составляют 13 страниц.

Содержание работы

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

В главе 1 дано авторское определение обобщенного растрового изображения, в главе 2 представлена авторская схема его кодирования, а в главе 3, соответственно, схема извлечения фрагмента. В главе 4 автором доказана основная теорема. В главе 5 приведены сравнительные результаты практической работы программной реализации представленного в работе метода, в приложении А изложены основы теории дискретного вейвлет-анализа, а в приложении Б обоснована корректность проводимого тестового испытания путем сравнительного анализа различных программных реализаций метода JPEG2000.

Краткий обзор истории исследований, предшествующих работе, позволяет лучше понять её истоки и побудительные мотивы к её выполнению. Задача интерактивного анализа растровых изображений в той или иной степени решается путем применения программных средств, реализующих метод (стандарт) JPEG, который основан на дискретном косинусном преобразовании (ДКП). Однако, большинство методов, основанных на ДКП, имеют существенные недостатки. Во-первых, ДКП фиксировано и, как следствие, не может быть адаптировано в зависимости от входного растрового изображения. Во-вторых, мно-гомасштабность, необходимая при интерактивном анализе, добавляется искусственным образом. Этот факт означает, что по растровому изображению вначале строится пирамида его масштабов (методом отличным от ДКП), а потом к каждому уровню пирамиды применяется метод, основанный на ДКП. Кроме того, при больших степенях сжатия визуально заметна блочность кодирования. Основным преимуществом существующих методов, основанных на методе ДКП, является их скорость кодирования/декодирования. Отметим, что реше-

ние задачи интерактивного анализа достигается только за счет использования существенно большого по объему кодированного потока данных.

Альтернативный подход к кодированию растровых изображений основан на теории вейвлет-преобразований. К преимуществам данного подхода можно отнести возможность адаптирования вейвлет-преобразования под входное изображение, что позволяет существенно повысить степень сжатия методов кодирования для определенных (специальных) классов растровых изображений. К тому же, масштабируемость достигается естественным образом, так как вей-влет-преобразование, используемое для декорреляции данных растрового изображения, автоматически строит и его масштабы. Благодаря свойству компакти-зации энергии и её более точному соответствию зрительной системе человека, большинство методов, основанных на вейвлет-преобразовании, превосходят метод JPEG по качеству восстановления растрового изображения как объективно (согласно метрике ПОСШ), так и субъективно (согласно средней оценке мнения группы экспертов). Следует также отметить, что при использовании небольшой начальной части потока данных, методам, основанным на вейвлет-преобразовании, присущи более благоприятные визуальные погрешности в сравнении с методом JPEG. В частности, алгоритмы распознавания образов (лица, отпечатки пальцев и тому подобные) в среднем работают лучше на изображениях, которые были закодированы с использованием методов SPIHT и JPEG2000, основанные на вейвлет-преобразовании, чем закодированные с использованием метода JPEG.

Можно выделить два способа при кодировании вейвлет-преобразованного растрового изображения, а именно — внутриподдиапазонный и межподдиапа-зонный.

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

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

ственным образом задать иерархическую древовидную структуру) тоже меньше. Метод SPIHT (который можно использовать при произвольном вейвлет-пре-образовании) является ключевым в данной категории и часто используется при сравнительном тестировании новых методов кодирования изображений.

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

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

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

В главе 1 дано определение растрового изображения и введено авторское определение обобщенного растрового изображения.

В разделе 1.1 в случае кодирования изображений большого размера обоснована несодержательность понятия растрового изображения. Затем, учитывая представленные недостатки растрового изображения, формализовано понятие растрового изображения с областями изменяемой детализации. Последний факт означает, что введено понятие фильтра т, который для каждой области задает её степень детализации detail и положение, заданное в координатной системе растрового изображения. Причем, степень детализации равная 0 соответствует самому высокому разрешению, а с увеличением числа detail разрешение области понижается в 2de,ai1 раз.

Вейвлет-представление, будучи многомасштабным, естественным образом использовано для задания на нем структуры, учитывающей степени детализации областей. Учитывая это обстоятельство, обозначим через См матрицу N-кас-кадного вейвлет-преобразования изображения I, где N := max^f detail;. В работе предложено использовать фильтр т для фильтрации вейвлет-коэффи-циентов. Последний факт означает, что те вейвлет-коэффициенты, которым не соответствуют области необходимой степени детализации, полагаются равными оо. Вейвлет-коэффициенты не равные сю считаются активными и только они кодируются.

Определение 1. Обобщенное растровое изображение, отвечающее растровому изображению I и числу N £ N, есть пара: В := (N. Сдг).

В разделе 1.2 приведены примеры задания обобщенного изображения. На рис. 1 показан пример растрового изображения с областями изменяемой детализации. Фильтр г для данного изображения задан как

т := {512. 512.1Zegion„mo, 7^.едгопфОН},

где область 71едгоплто соответствует лицу и имеет степень детализации равной 0, а область Т1едгоПфон задает фон и имеет степень детализации, например, равную 3.

Рис. 1. Пример фотографии с областями изменяемой детализации. Топология т состоит из двух областей, разделенных ломаной, которая задана как последовательность вершин: (390.0), (390,310), (412,330), (427,410), (395,410), (352,380). (277,470), (170,480), (112,400), (110,290), (58,220).

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

В разделе 1.3 приведены выводы, а именно - понятие растровое изображение несодержательно на практике. По этой причине автором разработана новая модель, которая учитывает заданные пользователем степени детализации областей в изображении.

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

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

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

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

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

В разделе 2.3 автором представлено расширение дискретного вейвлет-пре-образования на случай обобщенного растрового изображения и приведен алгоритм его вычисления.

Вейвлет-преобразование обобщенного растрового изображения 0 определено как соответствующее вейвлет-преобразование поддиапазона IX (в работе показано, что поддиапазон IX обобщенного растрового изображения В состоит только из активных узлов, по этой причине он суть растровое изображение). Из определения следует, что вейвлет-преобразование обобщенного растрового изображения есть суть обобщенное растровое изображение. В частности, уУ-каскадное вейвлет-преобразование растрового изображения есть обобщенное растровое изображение. По этой причине, при представлении схемы кодирования считается, что все необходимые (в рамках метода кодирования изображений) вейвлет-преобразования к изображению уже применены.

В работе автором предложен алгоритм вычисления дискретного вейвлет-преобразования, который основан на "оконном" подходе. Последний факт означает, что сначала вычисляется дискретное вейвлет-преобразование (поддиапазоны IX, ЬН, НЬ и НН) некой окрестности (зависящей от типа вейвлет-преобразования) четверки блоков (2 х 2) исходного растрового изображения. Затем, из соответствующих вычисленных поддиапазонов IX, ЬН, НЬ и НН вырезаются блоки, которые являются искомыми блоками соответствующих поддиапазонов вейвлет-представления растрового изображения. Дискретное вейвлет-преобразование всего растрового изображения вычисляется путем обеспечения выполнения данного процесса для всех четверок блоков. Данный алгоритм использует первичное представление обобщенного растрового изображения, что позволяет ему реализовывать качественные преимущества первичного представления. Отметим, что данный алгоритм обеспечивает порядок вычисления блоков поддиапазонов согласованный с кривой Гильберта. Последний факт означает, что как при каскадном применении данного алгоритма (именно таким образом в работе предложено вычислять /У-каскадное вейвлет-преобразование), так и при кодировании вычисленных вейвлет-коэффициентов эффективность первичного представления сохраняется.

В разделе 2.4 описана третья стадия — метод кодирования вейвлет-коэф-фициентов обобщенного растрового изображения.

В ходе решения автором задачи кодирования обобщенного растрового изображения сначала напоминается метод БРИТ кодирования растровых изображений. Метод БРШТ основан на том, что вейвлет-коэффициенты кодируются побитно в порядке их вклада в ПОСШ характеристику. Последовательность,

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

Первоначально имеется некое разбиение множества узлов вейвлет-преоб-разованного растрового изображения Лч^ь.ь^^-

Далее выполняется проверка значимости каждого из этих подмножеств:

max (|су|) > 2",

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

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

В традиционном методе SPIHT используются три глобальных списка для хранения множеств различных типов (для каждого из которых существуют свои правила разбиения): список незначимых множеств (Clis ~ list of insignificant sets), список незначимых пикселей (Clip - list of insignificant pixels), список значимых пикселей (Cisp - list of significant pixels). Данные списки обрабатываются схемами кодирования/декодирования в одинаковом порядке.

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

m

SPIHT. Последний факт означает, что для каждого из блоков вейвлет-преобра-

t*l.TC nl.TC М.гс

зования вводятся свои три локальные списка, а именно - L-l[p, и C£sp, где I это номер вейвлет-уровня, а гс индекс блока в данном уровне.

Помимо данной модификации, автором значительно изменен алгоритм добавления элемента в список. В случае метода SPIHT элементы добавляются в глобальные списки. В отличие от традиционного алгоритма в работе автором предложен алгоритм, который сначала вычисляет индекс [I. кг) того блока в список которого необходимо добавить элемент. Далее рассматриваемый алгоритмом элемент добавляется в список того блока, индекс (I, кг) которого ранее был вычислен.

Предложенный автором метод SS-SPIHT позволяет локализовать кодированные данные (биты) относительно масштаба и положения. Последний факт означает, что биты, выводимые при обработке каждого из блоков, обосабливаются в пакеты данных. Кодированный поток данных (метода SPIHT) фактически разбивается на пакеты данных. Благодаря разбиению потока на пакеты, представленный (далее) метод декодирования SS-SPIHT позволяет восстановить произвольные фрагменты растрового изображения при требуемых масштабах. Последнее достигается путем извлечения пакетов данных (из кодированного потока), которых достаточно для декодирования требуемого фрагмента.

Далее в этом разделе описывается авторское расширение GI-SS-SPIHT (General Image SS-SPIHT) метода SS-SPIHT на случай обобщенных растровых изображений. Отличительной особенностью расширенного алгоритма является то, что при кодировании учитывается активность узлов (соответствующих вейвлет-коэффициентов). Последний факт означает, что кодируются только активные вейвлет-коэффициенты, в то время как известные методы (например, подход основанный на понятие региона интереса) кодируют все вейвлет-коэффициенты (в том числе и неактивные). Заметим, что в работе множество активных узлов ActiveGriid строится таким образом, что если родитель неактивен, то и его дети неактивны. Такой подход гарантирует корректность работы метода GI-SS-SPIHT, а именно - все активные вейвлет-коэффициенты будут обработаны (закодированы).

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

БРШТ использовать объем оперативной памяти, который не зависит от размера обобщенного растрового изображения (но зависит, например, от количества вейвлет-уровней).

В разделе 2.5 сначала дополнены исходные положения. В частности, введено понятие байтовый (например, 8-битный) поток, а на его основе определено понятие степень сжатия применительно к алгоритму кодирования.

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

Затем, представлена авторская вероятностная модель (процесса вывода битов) метода 01-33-5РЩТ, которая основана на том, что при инициализации вероятностной модели текущего блока используется соответствующая модель блока-родителя. Благодаря представленной модели сохраняется эффективность использования метода арифметического кодирования даже при использовании блоков маленького размера (например, 8x8 пикселей). Заметим, что с уменьшением размера блока у известных алгоритмов (например, у алгоритма №ЕС2000) существенно снижается степень сжатия, причем в наибольшей степени из-за снижения эффективности метода арифметического кодирования.

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

дима только при формировании ответа на запрос клиента.

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

Обработка пакетов согласно кривой Гильберта осуществляется путем рекурсивного спуска по соответствующим квадрантам данного вейвлет-уровня. Построим квадро-дерево Т„.;, соответствующее сумме длин пакетов данных, относящихся к обрабатываемым квадрантам. Тогда корневой узел квадро-дере-ва Тп,; будет равен сумме длин всех пакетов битовой плоскости п и вейвлет-уровня I, а его дети будут равны сумме длин пакетов соответствующих квадрантов. Заметим, что в квадро-дереве достаточно сохранить длину трех из четырех квадрантов, так как сумма длин пакетов, которые соответствуют последнему квадранту, вычисляется как сумма длин всех пакетов данных (значение родителя) за вычетом суммы длин пакетов, которые соответствуют трем первым квадрантам. По дереву Тп ; строится вектор длин, который и кодируется.

Далее дан алгоритм кодирования длин (вложенных) пакетов, который совпадает с алгоритмом, используемом в методе 1РЕй2000.

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

В главе 3 представлен способ декодирования фрагмента изображения.

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

В разделе 3.2 представлена схема декодирования фрагмента изображения: алгоритм извлечения данных из потока и алгоритм восстановления фрагмента по этим данным.

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

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

Непрерывные части потока данных

11 \'/АА/АА 1 1 УАА/А 1 1 УАААААЛ 11 AAAAAAi |

1 ftm^ 1 • • • 1 Y/////A %%УА/АА% | УА/АА, 1

1 У//У///УА 1 1 У///Л 11 AY/AA/AAA II У/, '//А 11

///■У///Л1

Восстановление запрошенного фрагмента изображения

Рис. 2. На верхней части рисунка показаны непрерывные части (соответствующие последовательно идущим пакетам данных) кодированного потока по которым на нижней части рисунка ' изображен восстановленный фрагмент растрового изображения.

' клиенту пакета, то рекурсивного спуска не производится. Аналогично, если все пакеты данных клиенту необходимы, то все данные, соответствующие квадранту, передаются (для этого используется Тп ;) клиенту целиком и рекурсивного спуска не производится. Рекурсивный спуск производится только в том случае, когда квадранту соответствуют пакеты как отмеченные, так и не отмеченные на передачу. Представленный способ хранения пакетов позволяет существен-j но сократить количество обрабатываемых пакетов при извлечении данных, относящихся к фрагменту растрового изображения, что позволяет существенно снизить нагрузку вычислителя. В работе показано, что вычислительная сложность извлечения равна * log(-g)), где D = max(width. height) - линейный | размер изображения, В - размер блока используемого при кодировании и w -

ширина вырезаемого квадратного фрагмента. I В работе автором далее представлен алгоритм активной адаптации к разме-

ру растра извлекаемого фрагмента. При извлечении фрагмента размера 1000 х ' 1000 нет смысла в ответ клиенту пересылать пакеты, относящиеся к блокам размера 16 х 16. В данном случае целесообразнее дать ответ пакетами, соот-j ветствующим блокам (квадрантам) размера 64 х 64 (что естественно увеличит общий объем передаваемых данных). При вырезании фрагмента растрового изображения, во-первых, удается сократить количество рекурсивных вызовов, что уменьшает степень загрузки вычислительной системы, и, во-вторых, пакеты данных удается объединять в непрерывные фрагменты кодированного потока, что уменьшает общее количество сессий доступа к хранилищу данных. Все вме-

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

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

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

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

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

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

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

В разделе 4.1 автором рассмотрен вопрос инвариантности объема кодированного потока данных. Представленный в диссертационной работе метод СКЯЗ-ЗРШТ базируется на основных положениях метода БРШТ. В связи с тем, что данные методы построены на схожих положениях, метод СЬЗБ-ЗРШТ по существу переупорядочивает выводимые методом 8Р1НТ биты.

Сначала автором доказана инвариантность объема кодированного потока данных, а именно - доказано, что количество значимых бит г, выводимых в кодированный поток данных методом ет-БЗ-ЭРШТ, не зависит от выбранного при кодировании размера блока. Затем показано, что при кодировании растрового

изображения количество значимых бит, выводимых в кодированный поток данных методом кодирования ББ-ЗРШТ (частный случай метода С1-55-8Р1НТ для случая растровых изображений), совпадает с количеством бит, выводимых в поток методом кодирования ЯРШТ. Более того, количество выводимых битов 1 и О по отдельности также будет совпадать. Для этого в работе показано, что в методе 55-5Р1НТ изменен только порядок обработки элементов и, следовательно, факт вывода битов сохранится.

Помимо выводимых методом С1-88-8Р1НТ значимых бит, целевой кодированный поток данных содержит заголовок, длины вложенных пакетов и биты, используемые для выравнивания пакетов на естественные байтовые границы. Во втором подразделе дана оценка накладных расходов на выравнивание пакетов данных в случае массива байтов (например, из 8-чисел), а именно - оценка вклада (процентная) влияния процесса выравнивания пакетов данных на общий объем потока.

При описании механизма организации потока данных решено использовать оставшиеся биты текущего пакета данных при формировании следующего пакета, который относится к тому-же блоку. Последний факт означает, что количество битов, необходимых для выравнивания, зависит только от количества используемых блоков и не зависит от количества битовых плоскостей. По этой причине далее в работе вычисляется оценка общего количество блоков 5, на которое разбито вейвлет-преобразованное изображение. При выводе оценки считается, что ю, 1г 2> /V, где ы и /г это размер изображения, а N - количество используемых вейвлет-уровней. На практике более содержательна оценка относительной избыточности: е% = ^ < ^р-. Для блока размера 8x8 пикселей получаем оценку 0,5%, которая является незначительной. Следовательно, размер целевого потока в наибольшей степени зависит от способа хранения длин пакетов.

В разделе 4.2 сначала показывается, что количество значимых бит (¡, по которым можно восстановить фрагмент обобщенного растрового изображения, не зависит от выбранного при кодировании размера блока. Затем доказывается основная теорема диссертационной работы.

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

Далее в работе следует доказательство основной Теоремы.

Теорема 1. С уменьшением размера блока при кодировании общий объем дан-

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

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

В главе 5 сначала (в разделе 5.1) представлена программная реализация метода С;1-5>8-8Р1НТ, а также уточнены принятые соглашения.

Далее (в разделе 5.2) приведены практические результаты работы метода С1-88-8Р1НТ кодирования. Из результатов проведенных тестовых испытаний метода следует, что метод С1-88-8Р1НТ имеет явное преимущество в сравнении с методом 1РЕС2000 по степени сжатия растровых изображений, в том числе - и с областями изменяемой детализации. Причем, с уменьшением размера блока при кодировании преимущество метода СТ-ЗЭ^РШТ становится все более существенным. В сравнении с 1РЕС-Ь3 предложенный метод показывает несколько худшие результаты. Однако отметим, что метод 1РЕО-Ь8 не обладает никакими другими важными свойствами (ПОСШ-характеристика и возможность извлечения фрагментов) кроме превосходящей степени сжатия.

Использование понятия обобщенного растрового изображения (см. рис. 3) действительно позволяет существенно сокращать объем данных (с контролируемой пользователем степенью качества во всем изображении), необходимых для хранения растровых изображений. Отметим, что преимущество использования обобщенного растрового изображения сохраняется в том числе и при использовании других методов кодирования (например, 1РЕС2000). При этом заметим, что с уменьшением размера блока при кодировании преимущество метода С;Г-88-8РП1Т становится все более значимым.

по по

б) агшйшнк**'

Рис. 3. Две фотографии с размеченными областями детализации: а)изображение построено изображению зоопарка, где областями выделены группы домов; б)изображение построено изображению космического челнока, где областью выделена взлетная площадка.

Далее приведен анализ процесса извлечения фрагмента изображения из потока. Предложенный метод С1-88-8Р1НТ имеет существенное преимущество в сравнении с методом ,ГРЕ02000. Скорость извлечения фрагмента у метода 01-88-8Р1НТ существенно выше (см. рис. 4), чем у метода 1РЕС2000, а именно - средняя скорость извлечения выше как минимум на порядок. Например, на извлечение квадратного фрагмента размера 1000 х 1000 пикселей предложенный метод С1-88-8Р1НТ потратит 5 мс, а 1РЕ02000 — более 100 мс.

Рис. 4. Сравнение среднего времени, затраченного методами 01-55-5Р1НТ и ,1РЕ02000 на извлечение фрагмента из большого растрового изображения.

Объем извлекаемых данных методом СТ-ЗЗ-ЭРШТ в сравнении с методом 1РЕС2000 в среднем ниже и он действительно уменьшается с уменьшением размера блока (согласуется с основной теоремой, притом, что используется энтропийное кодирование). Более того, представленный в настоящей работе метод СГ-88-8РГНТ обладает возможностью адаптации под размер извлекаемого фрагмента. Последний факт означает, что за счет объединения соседних блоков существенно повышается скорость извлечения. Например, на извлечение фрагмента размера 1000 х 1000 пикселей время извлечения понизится с 8 мс. до 2 мс. Процесс восстановления фрагмента метода С1-88-8Р1НТ имеет сравнимое с методом 1РЕС2000 качество, а использование небольших блоков заметно повышает качество. На рис. 5 приведен пример восстановления фрагмента, наглядно показывающий результат сравнения.

В настоящее время задача интерактивного анализа растровых изображений решена при определенных (существенных) ограничениях. По результатам тестовых испытаний можно сделать вывод о том, что представленный в настоящей работе метод 01-88-8Р1НТ решает задачу интерактивного анализа изображений без ограничений на размеры используемых отображающих устройств и в режиме последовательной передачи данных.

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

Рис. 5. Сравнение восстановленного методами 1РЕС2000 (слева, 25.21 дб.) и С1-35-ЗРЩТ (справа, 26.71 дб.) соответственно фрагмента изображения 3.2.25 при 0.3 бит на пиксель. Хорошо видно, что визуальное качество правого изображения превосходит левое.

декодирования растрового изображения, использующие основные положения метода 8Р1НГГ.

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

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

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

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

Список публикаций

А1. Шокуров А. В. Кодирование изображений с последующим возможным оптимальным декодированием // Фундамент, и прикл. матем. 2007. Т. 13. С.225-255.

А2. Шокуров А. В., Михалев А. В. Оптимальное использование вейвлет-ком-понент // Успехи матем. наук. 2007. Т. 62. С. 171-172.

АЗ. Шокуров А. В. Оптимальное использование компонент двоичного вейвлет-представления // Вестн. Моск. ун-та. 2009. Т. 5. С. 3-6.

Подписано в печать 25.11.2010 Формат 60x88 1/16. Объем 1.0 п.л. Тираж 100 экз. Заказ № 1059 Отпечатано в ООО «Соцветие красок» 119991 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. А-102

Введение.

Обзор истории исследований.

Глава 1. Обобщенное растровое изображение.

1.1. Модель.

1.2. Примеры.

1.3. Выводы.

Глава 2. Схема кодирования

2.1. Исходные положения.

2.2. Первичное представление

2.3. Вейвлет-преобразование.

2.4. Вейвлет-коэффициенты . . . :.

2.5. Пакеты данных

2.6. Формирование целевого кодированного потока данных.

2.7. Выводы.

Глава 3. Схема декодирования.

3.1. Прообраз обратного вейвлет-преобразования.

3.2. Алгоритмы декодирования.

3.3. Выводы.

Глава 4. Основная Теорема.

4.1. Инвариантность объема кодированных данных.

4.2. Теорема.

4.3. Выводы.

Глава 5. Программная реализация и тестовые испытания.

5.1. Программная реализация метода GI-SS-SPIHT.

5.2. Тестовые испытания метода GI-SS-SPIHT.

5.3. Выводы.

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

Важной характеристикой растровых изображений является степень детализации, определяющая выбор оптимального разрешения, при котором не будут потеряны существенные детали растрового изображения. Во многих растровых изображениях степень детализации варьируется, то есть растровые изображения имеют области с изменяемыми степенями детализации. Фотографии, например, содержат как попавшие, так и не попавшие в ГРИП (глубина резко изображаемого пространства) области. Соответственно, попавшие в ГРИП области обычно имеют более высокую степень детализации, чем не попавшие в нее. Использование информации о вариациях степени детализации позволило бы существенно увеличить степень сжатия алгоритма кодирования и существенно уменьшить объем извлекаемых данных соответствующего алгоритма декодирования. Существующий способ (основанный на понятии региона интереса) в недостаточной степени (только на стадии квантования) использует информацию об областях изменяемой детализации, что отрицательно влияет на объем кодированного потока данных и на процесс извлечения фрагмента. Последнее подчеркивает важность разработки метода фильтрации неактуальной визуальной информации.

С учетом представленных соображений тема диссертации является актуальной и соответствует областям исследований в сфере теоретической информатики, а именно - к исследованию и разработке методов и алгоритмов анализа, распознавания и синтеза растровых изображений, что отражено в п.п. 5, 7 Паспорта специальности 05.13.17 "Теоретические основы информатики".

Задача интерактивного анализа растровых изображений в той или иной степени решается путем применения программных средств, реализующих метод (стандарт) JPEG ([1]), который основан на дискретном косинусном преобразовании (ДКП). Однако, большинство методов, основанных на ДКП имеют существенные недостатки. Альтернативный подход к кодированию растровых изображений основан на теории вейвлет-преобразований, который устраняет большинство имеющихся у ДКП недостатков, а именно - устраняется избыточность кодированного потока данных и объем передаваемой клиенту данных.

Можно выделить два способа при кодировании вейвлет-преобразованного растрового изображения, а именно — внутриподдиапазонный и межподдиапазонный. Внутриподдиапазонные методы (например, ЕВСОТ ([2]), SPECK ([3]) и SWEET ([4])) основаны на устранении корреляции между соседними вейвлет-коэффициентами в каждом из поддиапапазонов по отдельности. К недостатку метода ЕВСОТ можно отнести сложный характер его преобразования. К недостаткам самого метода JPEG2000 следует отнести существенное время, затрачиваемое на извлечение фрагментов, и несоответствие объема данных при извлечении небольших фрагментов. Межподдиапазонные методы основаны на устранении корреляции между вейвлет-коэффициен-тами, принадлежащими к разным вейвлет-поддиапазонам. Метод SPIHT является ключевым в данной категории и его можно использовать при произвольном вейвлет-преобразовании. Данный метод очень часто применяется при сравнительном тестировании новых методов кодирования растровых изображений.

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

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

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

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

К числу новых научных положений, представленных в диссертации, можно отнести следующие.

• Представление растрового изображения изменяемой детализации, основанное на его вейвлет-представлении.

• Метод кодирования, основанный на методе БРШТ, данного представления, допускающий интерактивный анализ изображения. Доказана независимость объема используемой алгоритмами кодирования/декодирования оперативной памяти от размера данного изображения.

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

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

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

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

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

1. Разработан новый метод кодирования и адаптивного интерактивного анализа растрового изображения изменяемой детализации, который включает эффективные модели, алгоритмы и программные механизмы кодирования/декодирования растрового изображения, использующие основные положения метода БРИТТ.

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

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

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

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

Методы исследований. В работе использованы методы вейвлет-анализа, кодирования информации, топологии, компьютерной графики и системного программирования.

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

Апробация работы. Результаты работы были представлены на "Ломоносовских чтениях — 2007" на кафедре вычислительной математики мех-мат факультета МГУ им. М.В. Ломоносова в 2007 г.; на специальном семинаре "Машинная графика" на мех-мат факультете МГУ

1 Пиковое отношение сигнала к шуму (в англоязычной литературе РБЫЯ) является стандартной метрикой (измеряется в децибелах) измерения схожести между двумя растровыми изображениями. им. М.В. Ломоносова в 2008 г.; на семинаре "Машинная графика и обработка изображений" на факультете ВМиК МГУ им. М.В. Ломоносова в 2008/2010 г.; на объединённом семинаре по ро-бототехническим системам ИПМ им. М.В. Келдыша РАН, МГУ им. М.В. Ломоносова, МГТУ им. Н.Э. Баумана, ИНОТиИ РГГУ в 2010 г.; на семинаре "Проблемы современных информационно-вычислительных систем" на мех-мат факультете МГУ им. М.В. Ломоносова в 2010 г.; на совместном семинаре Геофизического центра РАН и Института космических исследований РАН в 2010 г.

Публикации. По теме диссертации опубликованы 3 статьи (см. [5-7]) в журналах из перечня, рекомендованного ВАК Минобрнауки России.

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

Структура и объем диссертации. Диссертационная работа объемом 129 страниц состоит из введения, краткого обзора истории исследований, пяти глав, заключения, списка публикаций и цитированной литературы. Работа содержит 34 рисунка, 7 таблиц и 46 алгоритмов. Список литературы включает 155 наименования. Приложения к диссертационной работе составляют 13 страниц.

5.3. Выводы

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

Количество, бит/пиксель

Рис. 5.22. Сравнение алгоритмов восстановления фрагмента растрового изображения 3.2.25 при различных размерах блока. Используются алгоритмы восстановления методов С1-88-8Р1НТ и 1РЕС2000

Рис. 5.23. Сравнение восстановленного методами 1РЕ02000 (левое, 25.21 дб.) и С1-88-8Р1НТ (правое, 26.71 дб.) фрагмента растрового изображения 3.2.25 при 0.3 бит на пиксель. размера блока объем передаваемых клиенту данных не увеличивается (удается добиться оптимизации кодированного потока данных под извлечение небольших фрагментов растрового изображения). Последнее обстоятельство позволяет при выборе размера блока ориентироваться исключительно на требования прикладной задачи к предполагаемым размерам извлекаемых фрагментов, а не на их степень сжатия.

Из результатов проведенных тестовых испытаний метода следует, что метод GI-SS-SPIHT имеет явное преимущество в сравнении с методом JPEG2000 по степени сжатия растровых изображений, в том числе — и с областями изменяемой детализации. Причем, с уменьшением размера блока при кодировании преимущество метода GI-SS-SPIHT становится все более существенным. В сравнении с JPEG-LS предложенный метод показывает несколько худшие результаты. Однако отметим, что метод JPEG-LS не обладает никакими другими важными свойствами (ПОСШ-характеристика и возможность извлечения фрагментов) кроме превосходящей (другие традиционные методы) степени сжатия.

Скорость извлечения фрагмента у метода GI-SS-SPIHT существенно выше, чем у программной реализации метода JPEG2000, а именно - средняя скорость извлечения выше как минимум на порядок. Объем извлекаемых данных методом GI-SS-SPIHT в сравнении с методом JPEG2000 в среднем ниже. Более того, представленный в настоящей работе метод GI-SS-SPIHT обладает возможностью адаптации под размер извлекаемого фрагмента. Последний факт означает, что за счет объединения соседних блоков существенно повышается скорость извлечения. Процесс восстановления фрагмента метода GI-SS-SPIHT имеет сравнимое с методом JPEG2000 качество. Использование небольших блоков заметно повышает ПОСШ-характеристику.

В настоящее время задача интерактивного анализа растровых изображений в той или иной степени решена. Последний факт означает, что если при решении данной задачи ограничиваться фиксированным размером отображающего устройства и отсутствием необходимости в постепенном (по ходу приема данных) восстановлении фрагментов (подразумевается использование каналов связи высокой пропускной способности), то целесообразно использовать известное традиционное (кодирование пирамиды изображений методом JPEG) решение данной задачи. Заметим, что при необходимости снятия ограничения на размер отображаемого устройства необходимо наличие большого объема постоянной памяти. По результатам тестовых испытаний можно сделать вывод о том, что представленный в работе метод GI-SS-SPIHT может быть использован при эффективном решение задачи интерактивного анализа изображения. Последний факт означает, что представленный в настоящей работе метод GI-SS-SPIHT решает задачу интерактивного анализа изображений без ограничений на размеры используемых отображающих устройств и в режиме последовательной передачи данных.

Заключение

К числу основных результатов, полученных в диссертационной работе, можно отнести следующие:

1. Разработан новый метод кодирования и адаптивного интерактивного анализа растрового изображения изменяемой детализации, который включает эффективные модели, алгоритмы и программные механизмы кодирования/декодирования растрового изображения, использующие основные положения метода БРШТ.

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

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

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

Список условных обозначений

Множества В работе используются следующие обозначения множеств:

N — множество натуральных чисел (без 0);

Ъ — множество целых чисел;

М — множество действительных чисел; г\г>0,геЖ};

М+ = {г|г > 0, г £ М};

1-3 = [г, з] П 1, где г, ] 6 Z;

Е2 = множество дискретных сигналов: {/|/ : Ъ —V М}; е К21конечной энергии : £Г=-оо№]Р < +оо}.

Методы кодирования изображений В работе используются следующие сокращения при упоминании методов: SPIHT

FS-SPIHT

SB-SPIHT —

JPEG2000

JPEG

JPEG-LS —

SS-SPIHT —

GI-SS-SPIHT

Set Partitioning in Hierarchial Trees (см. [34]), эффективный метод кодирования вейвлет-коэффициентов;

Fully Spatial and SNR Scalable, SPIHT-Based (см. [94]), метод, построенный на положениях лежащих в основе метода SPIHT, допускающий эффективное восстановление всего изображения при различных масштабах;

Spatial Blocks Spiht (см. [66]), метод, построенный на положениях лежащих в основе метода SPIHT, допускающий эффективное восстановление фрагментов изображения, но при максимальном масштабе;

Стандарт декодирования изображений (см. [28]), допускает эффективное восстановление фрагментов изображения; Широкоизвестный стандарт декодирования изображений (см. [1]), на его основе разработан метод извлечения фрагментов изображения;

Стандарт кодирования изображений (см. [150]), обладает высокой степенью сжатия;

Представленный в диссертации пространственно многомасштабный метод кодирования растровых изображений; Представленный в диссертации пространственно многомасштабный метод кодирования обобщенных растровых изображений.

Обозначения В представленных в работе алгоритмах используются следующие обозначения:

Vabcd Va Vb Vn&lVb V„| Vb

Однобуквенная переменная; Переменная abed;

Присвоить переменной Va значение переменной V&; Побитное "и" значений двух переменных; Побитное "или" значений двух переменных.

1. 1.U-T. Recommendation T.81 - Digital compression and coding of continuous-tone still images. 1992.—September.

2. Taubman D. High Performance Scalable Image Compression with Ebcot // ICIP (3). 1999. Pp.344-348.

3. Islam A., Pearlman W. A. An Embedded and Efficient Low-Complexity Hierarchical Image Coder // Visual Communications and Image Processing '99, San Jose, CA. 1999. — April. Vol. 3653. Pp. 294-305.

4. Andrew J. A Simple and Efficient Hierarchical Image Coder // Proc. of the International Conf. on Image Processing. 1997. Vol. 3. Pp. 658-661.

5. Шокуров А. В. Кодирование изображений с последующим возможным оптимальным декодированием//Фундамент. иприкл. матем. 2007. Т. 13. С. 225-255.

6. Шокуров А. В., Михалев А. В. Оптимальное использование вейвлет-компонент // Успехи матем. наук. 2007. Т. 62. С. 171-172.

7. Шокуров А. В. Оптимальное использование компонент двоичного вейвлет-представле-ния // Вестн. Моск. ун-та. 2009. Т. 5. С. 3-6.

8. Knowlton К. С. Progressive image transmission // USA Patent. 1980. — September, no. 4222076.

9. Tanimoto S. L. Image transmission with gross information first // Computer Graphics and Image Processing. 1979. — January. Vol. 9, no. 1. Pp. 72-76.

10. Knowlton K. Progressive transmission of grey-scale and binary pictures by simple, efficient, and lossless encoding schemes // Proceedings of the IEEE. 1980. — July. Vol. 68, no. 7. Pp. 885-896.

11. Vitter J. S., Howard P., Howard P. G. et al. Fast Progressive Lossless Image Compression // In Image and Video Compression. 1994. Pp. 98-109.

12. Rauschenbach U. Progressive Image Transmission Using Levels Of Detail And Regions Of Interest // Proceedings of IASTED Conference on Computer Graphics and Imaging CGIM'98, Halifax, Nova Scotia, Canada. 1998. —June.

13. Burt P. J., Adelson E. H. Image Data Compression With The Laplacian Pyramid // In Proceedings of the conference on pattern recognition and image processing. 1981. Pp. 218-223.

14. Burt P. J., Adelson E. H. The Laplacian pyramid as a compact image code // Morgan Kaufmann Readings Series. 1987. Pp. 671-679.

15. Burt P. J. Fast filter transform for image processing // Computer Graphics and Image Processing. 1981, —May. Vol. 16, no. 1. Pp. 20-51.

16. Mallat S. G. A Theory for Multiresolution Signal Decomposition: The Wavelet Representation // EEE Trans. PAMI I. 1989. Vol. 11, no. 7. Pp. 674-693.

17. Saffor A., Ramli A. R., Ng К. H., Rahman R. A. A Comparative Study of Image Compression Between JPEG and Wavelet. // Malaysian Journal of Computer Science. 2001. Vol. 14. Pp. 39-45.

18. Iqbal M. A., Javed M. Y., Qayyum U. Curvelet-Based Image Compression with SPIHT // Convergence Information Technology, International Conference on. 2007. Vol. 0. Pp. 961-965.

19. Shipeng L., Weiping L. Shape-adaptive discrete wavelet transforms for arbitrarily shaped visual object coding // Circuits and Systems for Video Technology, IEEE Transactions on. 2000. Vol. 10(5). Pp. 725-743.

20. S. M. Ramesh A. S. Medical Image Compression using Wavelet Decomposition for Prediction Method // International Journal of Computer Science and Information Security. 2010. Vol. 7, no. 1. Pp. 262-265.

21. Vetterli M., Kovacevic J. Wavelets and Subband Coding. Москва, Россия: МИР, 2005.

22. Lewis A., Knowles G. Image compression using the 2-D wavelet transform // Image Processing, IEEE Transactions on. 1992. Vol. 1(2). Pp. 244-250.

23. Sudhakar R., Karthiga R., Jayaraman S. Image Compression Using Coding of Wavelet Coefficients: A Survey // Graphics, Vision and Image Processing. 2005. Vol. 5, no. 6. Pp. 25-38.

24. Brower B. Low-bit rate image compression evaluations // Proc. SPIE. 1994. — April.

25. Asamwar R. S., Bhurchandi К. M., Gandhi A. S. Piecewise Lifting Scheme Based DWT to Model Human Vision Interpolation Phenomenon // Proceedings of the World Congress on Engineering. 2009. Vol. 1.

26. Volkmer H. On the regularity of wavelets // IEEE Trans, on Information Theory. 1992. Vol. 38. Pp. 872-876.

27. Tian-Hu Y., Zhihai H., Mitra S. K. Simple and efficient wavelet image compression // Image Processing. 2000. Vol. 3. Pp. 174-177.

28. ISO/IEC. JPEG2000 image coding system, vl.O edition, 2000. — March.

29. ISO/IEC. JPEG2000 image coding system, v9.0 edition, 2005. — November.

30. Chrysafis C., Said A., Drukarev A. et al. SBHP A Low Complexity Wavelet Coder // In IEEE Int. Conf. Acoust., Speech and Sig. Proc. (ICASSP2000. 2000. Pp. 2035-2038.

31. Swaminathan A., Agarwal G. A comparative study of image compression methods // Study. 2004.

32. Bradley A. P., Bradley A. P. JPEG 2000 and Region of Interest Coding // Digital Image Computing Techniques and Applications. 1999.

33. Pearlman W. A., Said A. A Survey Of The State-Of-The-Art And Utilization Of Embedded, Tree-Based Coding // Circuits and Systems, 1998. ISCAS '98. Proceedings of the 1998 IEEE International Symposium on. 1998. — April. Vol.5. Pp. 114—117.

34. Said A., Pearlman W. A. A New, Fast, and Efficient Image CODEC Based on Set Partitioning in Hierarchical Trees // IEEE Trans. Circuits and Systems for Video Technology. 1996. — June. Vol. 6, no. 3. Pp. 243-250.

35. Shapiro J. M. Embedded image coding using zerotrees of wavelet coefficients // ieeeassp. 1993. Vol. 41, no. 12. Pp. 3445-3462.

36. Reddy R. V., Reddy T. S., Sharma G. Efficient Coding of Image Subbands using Blockbased Modified SPIHT // International Journal of Recent Trends in Engineering. 2009. — november. Vol. 2. Pp. 145-149.

37. Wheeler F. W., Pearlman W. A. Combined Spatial and Subband Block Coding of Images // In International Conference on Image Processing, ICIP'00. 2000. Pp. 861-864.

38. Hsin H.-C., Lien J.-J., Sung T.-Y. A Hybrid SPIHT-EBC Image Coder // IMECS. 2007. Pp. 1854-1857.

39. Alani D., Averbuch A., Dekel S. Image Coding With Geometric Wavelets // IEEE Transactions on Image Processing. 2007. Vol. 16, no. 1. Pp. 69-77.

40. Oliver J., Malumbres M. P. A Fast Run-Length Algorithm for Wavelet Image Coding with Reduced Memory Usage // Pattern Recognition and Image Analysis. 2005. Vol. 3522. Pp. 435-442.

41. Biswas S. Segmentation based compression for graylevel images // Pattern Recognition. 2003. Vol. 36, no. 7. Pp. 1501-1517.

42. Krause P. K. Texture Compression // Signal Processing Institute Technical Report. 2007. — November.

43. Inada T., McCool M. D. Compressed lossless texture representation and caching // In GH '06: Proceedings of the 21st ACM SIGGRAPH/Eurographics symposium on Graphics hardware. 2006. Pp. 111-120.

44. Stamm C. PGF A New Progressive File Format for Lossy and Lossless Image Compression // WSCG. 2002. Pp. 421-428.

45. Pearlman W. A., Islam A., Nagaraj N., Said A. Efficient, Low-Complexity Image Coding with a Set-Partitioning Embedded Block Coder // IEEE Trans. Circuits Systems Video Technology. 2004. Vol. 14. Pp. 1219-1235.

46. Na W., Li Z., Xiao'an Z. et al. Spatially scalable resolution image coding method with memory optimization based on wavelet transform // Journal of Electronics. 2005. Vol. 22, no. 1. Pp. 94-97.

47. Sodagar I., ju Lee H., Hatrack P., qin Zhang Y. Scalable Wavelet Coding for Synthetic/Natural Hybrid Images // IEEE Transactions on Circuits and Systems for Video Technology. 1999. Vol. 9. Pp. 244-254.

48. Servetto S. D., Ramchandran K., Orchard M. T. Image Coding Based on a Morphological Representation of Wavelet Data // Image Processing, IEEE Transactions on. 1999. Vol. 8, no. 9. Pp. 1161-1174.

49. Krause P. K. Ftc floating precision texture compression // In Proc. Vision, Modeling, and Visualization. 2009.

50. Fry T. W„ Hauck S. SPIHT Image Compression on FPGAs // IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY. 2005. Pp. 1138-1147.

51. GASTI W„ LOUYS M., LEFORT T. Implementation of data compression S/W on a space qualified DSP board//European signal processing conference. 2000. Vol. 10. Pp. 1189-1192.

52. Bayazit U., , Bayazit U., Pearlman W. A. Algorithmic Modifications To Spiht // in Proc. IEEE Int. Conf. Image Processing (ICIP'2001), Thessaloniki. 2001. Pp. 800-803.

53. Kassiml A. A., SeeTohl C.-W. Improving SPIHT Using Virtual Encapsulation // Circuits, Systems, and Signal Processing. 2004. Vol. 23. Pp. 507-516.

54. Ramos M., Hemami S. S. Activity selective SPIHT coding // SPIE Visual Communications and Image Processing. 1999. Pp. 315-326.

55. Ramos M. G., Hemami S. S. Perceptually based scalable image coding for packet networks // Journal of Electronic Imaging. 1998. — July. Vol. 7, no. 3. Pp. 453^163.

56. Wang M., rui Han Q. An Improved Algorithm of SPIHT based on the Human Visual Characteristics//World Academy of Science, Engineering and Technology. 2006. Vol. 17. Pp. 119-122.

57. Lu T.-T., Wen K.-W., Chang P.-C. Block Reordering Wavelet Packet SPIHT Image Coding // Lecture Notes in Computer Science. 2001. Vol. 2195. Pp. 442-^149.

58. Wang K., Wu C., Kong F., Zhang L. An improved partial SPIHT with classified weighted rate-distortion optimization for interferential multispectral image compression // Chinese Optics Letters. 2008. Vol. 6. Pp. 331-333.

59. Yewy T. J. Detail Preserving Image Compression using Wavelet Transform // IEEE. 1995.

60. Creusere C. D. Spatially partitioned lossless image compression in an embedded framework // In Proc. of the 31st Asimolar Conf. on Signals, Systems and Computers. 1997.

61. Sprljan N., Grgic S., Grgic M. Modified SPIHT algorithm for wavelet packet image coding // Real-Time Imaging. 2005. — October. Vol. 11, no. 5-6. Pp. 378-388.

62. Liang J. Highly scalable image coding for multimedia applications // Proceedings of the fifth ACM international conference on Multimedia. 1997. Pp. 11-19.

63. Yen W.-C., Chen Y.-Y. Natural Image Compression Based on Modified SPIHT // Computer and Information Science, 2005. Fourth Annual ACIS International Conference on. 2005. Pp. 100-104.

64. Wheeler F. W., Pearlman W. A. Low-Memory Packetized SPIHT Image Compression // Conf. Record of The Thirty-Third Asilomar Conf. on Signals, Systems & Computers (M. B. Matthews, ed.). 1999. — October. Vol. 2, no. 22. Pp. 1193-1197.

65. Lafruit G., Nachtergaele L., Vanhoof B., Catthoor F. The Local Wavelet Transform: a memory-efficient, high-speed architecture optimized to a region-oriented Zero-Tree coder // Integrated Comuter-aided Engineering. 2000. Vol. 7. Pp. 89-103.

66. Andreopoulos Y., Schelkens P., Zervas N. D. et al. A Wavelet-Tree Image Coding System With Efficient Memory Utilization // Proceedings of the Acoustics, Speech, and Signal Processing. 2001. — September. Vol. 3. Pp. 1709-1712.

67. Chew L. W., Chia W. C., minn Ang L., Seng K. P. Very Low-Memory Wavelet Compression Architecture Using Strip-Based Processing for Implementation in Wireless Sensor Networks // EURASIP Journal on Embedded Systems. 2009.

68. Nandi A. V., Banakar R. M. Throughput Efficient Parallel Implementation of SPIHT Algorithm // VLSI Design, 2008. VLSID 2008. 21st International Conference on. 2008. Pp. 718-725.

69. Creusere C. D. A new method of robust image compression based on the embedded zerotree wavelet algorithm //IEEE Trans, on Image Processing. 1997. Vol. 6, no. 10. P. 1436-1442.

70. Iren S., Amer P. D. SPIHT-NC: Network-Conscious Zerotree Encoding // DCC: Data Compression Conference, IEEE Computer Society TCC. 2000.

71. Iren S., Amer P., Conrad P. Network-conscious compressed images over wireless networks // Lecture Notes in Computer Science: Interactive Distributed Multimedia Systems and Telecommunication Services. 1998. no. 1483. Pp. 149-158.

72. Clark D., Tennenhouse D. Architectural considerations for a new generation of protocols // In ACM SIGCOMM. 1990. Pp. 200—208.

73. Choa S., Pearlmana W. A. Error Resilient Compression and Transmission of Scalable Video. 2001.

74. Yang S. H., Cheng P. F. Robust Transmission of SPIHT-Coded Images Over Packet Networks // IEEE Trans. Circuits and Systems for Video Technology. 2007. — May. Vol. 17, no. 5. Pp. 558-567.

75. Wen-Jyi H., Wen-Lian H. Scalable and robust image transmission using block-based layered set partitioning in hierarchical trees // Optical engineering. 2003. Pp. 1397-1404.

76. Mohr A. E., Riskin E. A., Ladner R. E. Generalized Multiple Description Coding through Unequal Loss Protection // IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOG. 1999. no. 42. Pp. 411 -^-15.

77. Liu J.-C., Hwang W.-L., Hwang W.-J., Chen M.-S. Robust Block-Based EZW Image Compression with Channel Noise Optimized Rate-Distortion Functions // ICIP (2). 1999. Pp. 560-564.

78. Kassim A. A., Lee W. S. Embedded color image coding using SPIHT with partially linked spatial orientation trees // IEEE Trans. Circuits and Systems for Video Technology. 2003. —February. Vol. 13, no. 2. Pp. 203-206.

79. Kesavamurthy T., Rani S. Dicom Color Medical Image Compression using 3D-SPIHT for Pacs Application // JIVP. 2008. Vol. 4, no. 2. Pp. 113-119.

80. Yang C.-L., Po L.-M., Cheung C.-H., Cheung K.-W. A novel ordered-SPIHT for embedded color image coding // Neural Networks and Signal Processing, 2003. Proceedings of the 2003 International Conference on. 2003.—December, no. 2. Pp. 1087-1090.

81. Cho S., Pearlman W. A. Region-Based Spiht Coding And Multiresolution Decoding Of Image Sequences. 2002. — February.

82. Kim B.-J., Pearlman W. A. An Embedded Wavelet Video Coder Using Three-Dimensional Set Partitioning in Hierarchical Trees (SPIHT) // Data Compression Conference. 1997. Pp. 251-260.

83. Kim B. J., Xiong Z., Pearlman W. A. Low Bit-Rate Scalable Video Coding with 3-D Set Partitioning in Hierarchical Trees (3-D SPIHT) // IEEE Trans. Circuits and Systems for Video Technology. 2000, — december. Vol. 10, no. 8. Pp. 1374-1387.

84. Kassim A. A., Siong L. W. Performance of the color set partitioning in hierarchical tree scheme (CSPIHT) in video coding // Circuits, Systems, and Signal Processing. 2001. Vol. 20, no. 2. Pp. 253-270.

85. Khan E., Ghanbari M. An efficient and scalable low bit-rate video coding with virtual SPIHT // SP:IC. 2004, —March. Vol. 19, no. 3. Pp. 267-283.

86. Ding J.-R., Yang J.-F. A Simplified SPIHT algorithm // Journal of the Chinese Institute of Engineers. 2008. Vol. 31, no. 4. Pp. 715-719.

87. Creusere C. D. Image coding using parallel implementations of the embedded zerotree wavelet algorithm // In Proc. of the IS&T/SPIE Symposium on Electronic Imaging. 1996. Vol. 2668.

88. Wheeler F. W., Pearlman W. A. Spiht Image Compression Without Lists // In Proceedings of the IEEE ICASSP 2000. 2000. Pp. 2047-2050.

89. Cicala L., Poggi G. A generalization of zerotree coding algorithms // Picture Coding Symposium. 2007.

90. Cho Y., Pearlman W. Quantifying the Coding Performance of Zerotrees of Wavelet Coefficients: Degree-k Zerotree // Signal Processing, IEEE Transactions on. 2007. Vol. 55, no. 1. Pp. 2425-2431.

91. Cicala L. Performance Analysis of Generalized Zerotree Coders Varying the Maximum Zerotree Degree//Advanced Concepts for Intelligent Vision Systems. 2008. Vol. 5259. Pp. 1-12.

92. Danyali H„ Mertins A. Fully Spatial and SNR Scalable, SPIHT-Based Image Coding for Transmission Over Heterogeneous Networks // Journal of Telecommunications and Information Technology. 2003. Vol. 2. Pp. 92-98.

93. Danyali H., Mertins A. Highly scalable image compression based on SPIHT for network applications // ICIP (1). 2002. Pp. 217-220.

94. Hwang W., Wu C., Li K. Layered set partitioning in hierarchical tree for image coding // SP. 2002. — February. Vol. 82, no. 2. Pp. 149-156.

95. Christophe E., Mailhes C., Duhamel P. Hyperspectral Image Compression: Adapting SPIHT and EZW to Anisotropic 3-D Wavelet Coding // IP. 2008.— December. Vol. 17, no. 12. Pp. 2334-2346.

96. Christophe E., Pearlman W. Three-Dimensional SPIHT Coding of Volume Images with Random Access and Resolution Scalability // JIVP. 2008.

97. Martin K., Lukac R., Plataniotis K. N. SPIHT-Based Coding of the Shape and Texture of Arbitrarily Shaped Visual Objects // IEEE Trans. Circuits and Systems for Video Technology.2006, —octover. Vol. 16, no. 10. Pp. 1196-1208.

98. Danyali H., Mertins A. Flexible, highly scalable, object-based wavelet image compression algorithm for network applications // VISP. 2004. — December. Vol. 151, no. 6. Pp. 498-510.

99. Danyali H., Mertins A. An Object-Based Highly Scalable Image Coding for Efficient Multimedia Distribution // Signal Processing for Telecommunications and Multimedia. 2006. — January. Vol. 27, no. 6. Pp. 57-69.

100. Pratt W. K. Digital Image Processing: PIKS Scientific Inside. 3-rd edition. Wiley-Interscience, 2001.

101. Котельников В. А. О пропускной способности эфира и проволоки в электросвязи — Всесоюзный энергетический комитет // Материалы к I Всесоюзному съезду по вопросам технической реконструкции дела связи и развития слаботочной промышленности. 1933.

102. Prokop Н. Cache-Oblivious Algorithms, thesis, 1999.

103. Hilbert D. Uber die stetige Abbildung einer Linie auf ein Flachenstiick // Math. Ann. 1891. Vol. 38. P. 459^60.

104. Ill J. J. В., Goldsman P. Vertex-labeling algorithms for the Hilbert spacefilling curve // Software—Practice & Experience. 2001. —May. Vol. 31, no. 5. Pp. 395-408.

105. Breinholt G., Schierz C. Algorithm 781: generating Hilbert's space-filling curve by recursion // ACM Transactions on Mathematical Software (TOMS) archive. 1998. Vol. 24, no. 2. Pp. 184-189.

106. Jin G., Mellor-Crummey J. Using Space-filling Curves for Computation Reordering // Proceedings of the Los Alamos Computer Science Institute Sixth Annual Symposium. 2005.

107. Chen C.-S., Lin S.-Y., Fan M.-H., Huang C.-H. A Closed-Form Algorithm for Converting Hilbert Space-Filling Curve Indices // IAENG International Journal of Computer Science. 2010. —February. Vol. 37, no. 1.

108. Wirth N. Algorithms and Data Structures. Prentice Hall, 1985.

109. Zhang J., ichiro Kamata S., Ueshige Y. A Pseudo-hilbert Scan Algorithm for Arbitrarily-Sized Rectangle Region // Advances in Machine Vision, Image Processing, and Pattern Analysis. 2006. Vol. 4153. Pp. 290-299.

110. Hamiltona С. H., Rau-Chaplin A. Compact Hilbert indices: Space-filling curves for domains with unequal side lengths // Information Processing Letters. 2008. — February. Vol. 105, no. 5. Pp.155-163.

111. Chung K.-L., Huang Y.-L., Liu Y.-W. Efficient algorithms for coding Hilbert curve of arbitrary-sized image and application to window query // Information Sciences: an International Journal.2007. Vol. 177, no. 10. Pp. 2130-2151.

112. Dennis J. M. Partitioning with Space-Filling Curves on the Cubed-Sphere // Parallel and Distributed Processing Symposium, International. 2003. — April. Vol. 0. P. 269a.

113. Chu Y., Sao-Jie C. An improved pyramid algorithm for synthesizing 2-D discrete wavelet transforms // Signal Processing Systems. 1999. Pp. 75-80.

114. Salehil S. A., Sadril S. Investigation of Lifting-Based Hardware Architectures for Discrete Wavelet Transform // Circuits, Systems, and Signal Processing. 2009. Vol. 28, no. 1. Pp. 1-16.

115. Chaitali K. A., Chakrabarti C., Acharya T. Efficient Implementation Of A Set Of Lifting Based Wavelet Filters//Appears in proceedings of ICASSP 2001. 2001. Pp. 1101-1104.

116. Urriza I., Garcia J., Barragan L. A. et al. Locality Improvement of the Pyramid Algorithm to Compute the Discrete Wavelet Transform // Procc. DCIS'98. 1998. Pp. 30-35.

117. Chakrabarti C., Vishwanath M. Efficient realizations of the discrete and continuous wavelet transforms: from single chip implementations to mappings on SIMD array computers // Signal Processing, IEEE Transactions on. 1995. Vol. 43, no. 3. Pp. 759-771.

118. WENQING J., ORTEGA A. Parallel architecture for the Discrete Wavelet transform based on the lifting factorization // SPIE proceedings series. 1999. Vol. 3817. Pp. 2-13.

119. Sumanth S., Kutty K. VLSI Implementation of Discrete Wavelet Transform using Systolic Array Architecture // Advances in Computer and Information Sciences and Engineering. 2008. Pp. 467^172.

120. Chakrabarti C., Mumford C. Efficient realizations of encoders and decoders based on the 2-D discrete wavelet transform // IEEE Transactions on Very Large Scale Integration (VLSI) Systems archive. 1999. Vol. 7, no. 3. Pp. 289-298.

121. Chrysafis C., Ortega A. Line-based, reduced memory, wavelet image compression // IEEE Trans, on Image Processing. 2000. Vol. 9, no. 3. Pp. 378-389.

122. Barua S., Carletta J. E., Kotteri K. A., Bell A. E. An efficient architecture for lifting-based two-dimensional discrete wavelet transforms // Integration, the VLSI Journal archive. 2005. Vol. 38, no. 3. Pp. 341-352.

123. Jain R., P P. R. A Power Efficient Architecture for 2-D Discrete Wavelet Transform // 10 th IEEE Symposium on VLSI Design and Testing, Goa, Aug 2006 Conference Proceedings: 20th VLSI Design 6th Embedded Systems. 2006.

124. Pan S. B., Park R.-H. Systolic array architectures for computation of the discrete wavelet transform // Journal of Visual Communication and Image Representation. 2003. Vol. 14, no. 3. Pp. 217-231.

125. Chakrabarti C., Mumford C. Efficient realizations of analysis and synthesis filters based on the 2-D discrete wavelet transform // Proceedings of the Acoustics, Speech, and Signal Processing. 1996. Vol. 6. Pp. 3256-3259.

126. Chrysafis C., Ortega A. An Algorithm for Low Memory Wavelet Image Compression // Proc. IEEE Int. Conference on Image Processing (ICIP). 1999. Pp. 24-28.

127. Singh V. K. Discrete wavelet transform based image compression // International Journal of Remote Sensing. 1999. Vol. 20, no. 17. Pp. 3399-3405.

128. Witten I., Neal R., Cleary J. Arithmetic coding for data compression // CACM. 1987. — June. Vol. 30, no. 6. Pp. 520-540.

129. Markl V. MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Ph.D. Thesis. // Technical University München. 1999.

130. Gaede V., Günther O. Multidimensional access methods // ACM Computing Surveys (CSUR). 1998. Vol. 30, no. 2. Pp. 170-231.

131. Tropf H., Herzog H. Multidimensional range search in dynamically balanced trees // Angewandte Informatik (Applied Informatics). 1981. Vol. 2. Pp. 71-77.

132. Aref W. G., Samet H. Efficient processing of window queries in the pyramid data structure // Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. 1990. Pp. 265-272.

133. Fenk R. The BUB-Tree // Proc. of VLDB Conf. 2002.

134. Skopal T., Kratky M., Pokorny J., Snâsel V. A new range query algorithm for universal B-trees // Information Systems. 2006. Vol. 31, no. 6. Pp. 489-511.

135. Beckmann N., peter Begel H., Schneider R., Seeger B. The R*-tree: an Efficient and Robust Access Method for Points and Rectangles // ACM SIGMOD Record. 1990. Vol. 19, no. 2. Pp. 322-331.

136. Kothuri R. K. V., Ravada S., Abugov D. Quadtree and r-tree indexes in oracle spatial: a comparison using gis data // Proceedings of ACM SIGMOD Conference. 2002. Pp. 546-557.

137. C. T., Shekhar S. Comparing Z-order B-tree and R-tree Family for Spatial Query Processing. 2000.

138. Song Z., Roussopoulos N. A New Method to Store and Retrieve Images // Technical Report CS-TR-3991. University of Maryland. 1999.

139. Song Z., Roussopoulos N. Using Hilbert curve in image storing and retrieving // Information Systems. 2002. Vol. 27, no. 8. Pp. 523-536.

140. Chung К., Tsai Y., Hu F. Space-Filling Approach for Fast Window Query on Compressed Images //IP. 2000. — December. Vol. 9, no. 12. Pp. 2109-2116.

141. Малла С. Вэйвлеты в Обработке Сигналов. Москва, Россия: МИР, 2005.

142. Proietti G. An optimal algorithm for decomposing a window into maximal quadtree blocks // Acta Informática. 1999. Vol. 36, no. 4. Pp. 257-266.

143. Moon В., Jagadish H. V., Faloutsos C., Saltz J. H. Analysis of the Clustering Properties of the Hilbert Space-Filling Curve // IEEE Trans. Knowl. Data Eng. 2001. Vol. 13, no. 1. Pp. 124-141.

144. Weinberger M., Seroussi G., Sapiro G. The LOCO-I Lossless Image Compression Algorithm: Principles and Standardization into JPEG-LS. // IEEE Trans. Image Processing. 2000. — August. Vol. 9. Pp. 1309-1324.

145. University of South California. The USC-SIPI Image Database, http : / / S ipi . US С . edu/database/.

146. Yale University. Yale Faces Database, http : / /cvc . yale . edu/pro j ects / yalefaces/yalefaces.html.

147. Deans M. GoldenTemple GigaPan panorama.

148. Sayood K. Introduction to Data Compression. 3-rd edition. Morgan Kaufmann, 2006.

149. Taubman D. S., Marcellin M. W. JPEG2000 Image Compression Fundamentals, Standards and Practice. 3-rd edition. Morgan Kaufmann, 2006.