Содержание к диссертации
Введение 5
Глава 1 Цифровая обработка и сжатие дискретных изображений без потерь 13
1.1 Графические форматы 13
-
Файлы BMP 13
-
Структура файла BMP 15
-
Файлы PCX 16
-
Файлы TIFF 16
-
Файлы GIF 17
-
Файлы PNG 17
-
Файлы JPEG 18
1.2 Алгоритмы сжатия изображений без потерь 18
L2.1 Алгоритм RLE 18
-
Алгоритм LZ 19
-
Алгоритм LZW 20
-
Классический алгоритм Хаффмана 23
-
Алгоритм Lossless JPEG 24
1.3 Эффективность сжатия дискретных изображений существующими 24
архиваторами
1.4 Выводы 25
Глава 2 Методы спектрального сжатия дискретных изображений 29
-
Основные подходы к реализации сжатия дискретных изображений 29
-
Модель дискретного изображения 30
-
Квантование 32
-
Кодирование изображений 35
-
Фрактальное сжатие изображений 36
-
Метод волновых всплесков 38
-
Сжатие изображений на основе их представлений в виде полевой 39 структуры
-
Стандарт сжатия цифровых изображений JPEG 43
2.9 Выводы 48
Глава 3 Требования к цифровой обработке и передаче видеоинформации по 50
каналам связи
-
Стандарт MPEG-4 50
-
Кодированное представление медийных объектов 52
-
Основные функции в MPEG-4 версия 1 53
-
Видео-система 55
-
Кодирование формы и Alpha-представление 56
-
Кодирование 2-D сеток с нечетко выраженной структурой 57
-
Натуральное видео 5 8
-
Визуальная секции MPEG-4 59
-
Декодирование 65
3.10 Выводы 66
Глава 4 Методы цветового сжатия дискретных изображений 67
4.1 Метод цифровой фильтрации изображения 69
-
Метод дискретной спиральной развертки (МДСР) 72
-
Метод цветовой фильтрации изображения без потерь (МЦФБП) 75
-
Декомпрессия сжатых изображений 79
-
Метод цветовой фильтрации изображения с потерями (МЦФСП) 79
-
Экспериментальная проверка и сравнение МЦФ с WinRar и JPEG 82
4.2 Методы описаний моделей цветовых объектов 102
-
Рецепторная матрица 103
-
Описание точками 10 5
-
Описание полигонами 105
-
Описание сплайнами 109
-
Аналитическое описание 121
-
Алгебраическая модель цветового объекта 122
-
Сравнение моделей 139 4.3 Выводы 140
Заключение 141
Литература 142
Приложение 1 Программы цветовой фильтрации 156
Приложение 2 Таблица перекодировки с наибольшим числом нулей в коде 174
Приложение 3 Тестовые изображения 181
Введение к работе
Основной поток информации из окружающего мира человек получает через зрение. Создание, сохранение, обработка и передача зрительных образов (изображений), является постоянной заботой человечества на протяжении всей его истории. Наскальные рисунки, художественные полотна, фотографии, кино, телевидение, компьютерные информационные системы — этапы развития возможностей человека создания, передачи и получения изображений. Развитие науки и техники позволило человеку изучить собственное зрение и создавать на его подобии технические средства записи изображений и передачи их на большие расстояния. Получив возможность передавать информацию с помощью электромагнитных колебаний, человек изобрел радио и телевидение. В своем развитии радио и телевидение прошли путь от аналоговых систем до дискретных, начиная с передачи весьма простых сообщений (азбука Морзе) до видео конференций в цвете и реальном времени. Появление телевидения напрямую связало задачи обработки изображений с задачами обработки электрических сигналов, а необыкновенный подъем в последние десятилетия цифровой электроники привело к тому, что повсеместный переход от аналоговых форм представления сигналов к цифровым стал характерной чертой современных электронных систем. В этой связи вопросы цифровой обработки изображений (ЦОИ) приобретают сегодня особую актуальность.
Если вернуться к человеку, то он получает видео информацию [1] в области световых частот (700-300 нм) в дискретном виде. Сетчатка глаза содержит около 127 млн. рецепторов (120 млн. палочек и 7 млн. колбочек с тремя выступами для приема лучей красного, зеленого и синего цвета). Плотность размещения рецепторов 160 тыс. на 1 кв. мм. Глаз обладает глубокой адаптацией по отношению к интенсивности света, то есть он может различать огромное количество порогов яркости. Современные технические устройства строят изображения на экране по подобному принципу, однако, по своей разрешающей способности и пороговой чувствительности они намного уступают человеческому глазу.
Существует проблема, связанная с передачей изображений. Области частот, в которой работают современные передатчики, намного ниже светового диапазона и здесь возникает проблема адекватной модуляции изображения.
Есть еще одна проблема, которая существует при передаче изображений, это последовательное считывание элементов изображения при записи и последовательная развертка при воспроизведении. Такая же проблема существует и в вычислительной технике, когда обработка данных осуществляется последовательно. В вопросах параллельной обработки изображений результаты в вычислительной технике по сравнению с человеком весьма скромные. Известно, что в области слепого пятна глаза информация сжимается от 127 млн. рецепторов и передается в мозг в виде импульсов по 1 млн. нервных волокон. Пока нет ясного представления механизма такого сжатия.
Мечта человечества создать устройства, которые позволяли бы им общаться на удаленном расстоянии, например, на разных концах земного шара (а в последствии и в космосе) в одно и тоже время с реакцией восприятия человека (реальное время).
В технических устройствах для решения задачи передачи изображений в реальном времени можно пойти следующими путями. Фиксировать изображение с помощью матриц определенного разрешения и значение каждого элемента матрицы передавать по отдельному каналу. Число таких каналов будет равно числу элементов матрицы. Если изображение имеет миллион элементов, то и каналов нужно будет столько же. Разворачивать такое изображение не будет необходимости, так как все элементы будут приходить одновременно и выводиться сразу же в определенной точке изображения. Такая реализация, по-видимому, будет возможна на уровне нанотехнологий и использования для каналов очень высоких частот, проникающих на большие расстояния (например, гравитация). Пока это не достижимо. Следующий путь заключается в сжатии информации после получения с устройств фиксации изображения до минимальных размеров, передача сжатой
7 информации по каналам связи и восстановления этой информации в виде изображения. Время суммы всех трех этапов обработки видеоинформации определит время общения. Задача перед исследователями и разработчиками заключается в снижении временных показателей на всех этапах обработки информации. При этом необходимо учитывать разрешающую способность видеоинформации (градаций яркости и цветности), искажения ее в результате передачи по каналам связи и потерь качества и цветности в результате ее воспроизведения. Видеоинформация проходит процесс преобразования ее в двоичную форму и обратно и понятно, что при этом возможны потери информации.
Во-первых, преобразования используются для выделения характерных признаков изображения. Например, постоянная составляющая спектра Фурье пропорциональна средней яркости изображения, а высокочастотные составляющие характеризуют ориентацию и резкость контуров.
Другой областью применения преобразований является кодирование изображений, когда оцифровке (квантованию с конечным числом уровней) подвергается не само дискретное изображение, а его спектр, что во многих случаях позволяет добиться заметного сокращения длины получаемого кода.
Третья область приложений - это сокращение размерности при выполнении вычислений; иначе говоря, в процессе спектральной обработки (например, фильтрации) малые по величине коэффициенты преобразования можно отбросить без заметного ухудшения качества обработки. И вторая, и третья области применения преобразований в классификации Прэтта это, по сути, один и тот же круг задач сжатия информации при обработке изображений, или просто сжатия изображений.
Под термином сжатие изображений понимается сокращение, насколько возможно, затрат бит для кодирования дискретных изображений при сохранении требуемого уровня качества их последующего воспроизведения. Другими словами, сжатие изображений - это их эффективное, в смысле экономии бит, представление в виде двоичного кода.
8 Современные вычислительные средства пока что не в полной мере удовлетворяют характеристикам, требуемым для передачи цифровых изображений с нужным разрешением в реальном масштабе времени [2]. Цифровые системы требуют огромных ресурсов памяти для записи качественных цифровые изображений и для демонстрации цифрового видеофильма в реальном масштабе времени необходима передача данных со скоростью 160 мегабит/с [2]. Сказанное объясняет тот громадный интерес, который проявляется во всем мире к поискам путей эффективного кодирования изображений.
Наибольшие усилия исследователей в области сжатия изображений были направлены на разработку методов дискретных преобразований. В 1965 году появилась работа Кули и Тьюки [3], содержавшей описание алгоритма быстрого вычисления дискретного преобразования Фурье. Идея замены одноцветного изображения как непосредственного объекта кодирования отсчетами его двумерного спектра дискретного преобразования Фурье (ДПФ) была выдвинута в 1968 году [4,5]. Кодирование посредством использования ДПФ основано на том, что для большинства изображений естественного происхождения значения многих коэффициентов ДПФ сравнительно малы. Такие коэффициенты можно часто вообще отбросить, или отвести на их кодирование малое число бит, без риска внести какие-либо значимые искажения. В 1969 году Прэтт, Эндрюс и Кэйн предложили использовать для кодирования изображений вместо преобразования Фурье преобразование Адамара [6-8], что во многих практических случаях позволяет значительно уменьшить объем необходимых вычислений. После этого были предприняты исследования по применению для кодирования изображений дискретных преобразований Карунена-Лоэва [9] и Хаара [10,11]. Преобразование Карунена-Лоэва является оптимальным в том смысле, что обеспечивает минимальную среднеквад-ратическую ошибку кодирования, однако требует, к сожалению, знания статистических характеристик обрабатываемых изображений и не имеет быстрого алгоритма вычисления [I]; преобразование Хаара, напротив, характеризуется в вые- шей степени эффективным алгоритмом вычисления, но дает, как правило, сравнительно большую погрешность кодирования [1]. В 1971 году Шибата и Эномото [12] предложили специально для использования в кодировании изображений так называемое наклонное преобразование векторов из или 8 компонент. Вскоре после этого Прэтт, Чени Уилч разработали обобщенный алгоритм наклонного преобразования векторов большой длины и двумерных массивов [13]. Все преимущества кодирования одноцветных изображений с использованием преобразований вытекают, в конечном счете, из особенностей распределения энергии среди элементов дискретного спектра - благодаря этому двумерный спектр более удобен для кодирования, чем изображение в исходном представлении [14-16]. Вследствие значительных корреляционных связей между элементами изображения естественной природы основная энергия в дискретном спектре имеет тенденцию концентрироваться в относительно небольшом числе отсчетов, соответствующих медленно осциллирующим базисным функциям. Поэтому, без существенного ущерба для последующего восстановления изображения, малые по величине спектральные коэффициенты можно вообще обнулить, а оставшиеся элементы спектра оцифровать (проквантовать и закодировать). Как показано Ахмедом и др. [17], в применении к кодированию изображений, для которых подходит Марковская статистическая модель, дискретное косинусное преобразование (ДКП), имеющее быстрый алгоритм вычислений, приближается по эффективности к преобразованию Карунена-Лоэва [15,18,19]. Данный факт явился причиной того, что именно ДКП послужило основой при разработке стандарта сжатия неподвижных изображений JPEG [20-24]. Указанный стандарт явился плодом многолетних усилий коллектива специалистов, образованного в 1987 году из представителей двух авторитетных международных организаций: МОС и МККТТ. Появление объединенной группы JPEG было вызвано ростом числа разработчиков и пользователей различных систем ЦОИ и вытекавшей из этого необходимостью унификации формата сжатого представления цифровых изображений. Выработанная в итоге спецификация
10 [23,24] явилась документом, которого сегодня придерживаются практически все разработчики программных систем ЦОИ общего назначения. Уже производятся специализированные микросхемы, реализующие сжатие и восстановление по JPEG аппаратно и обеспечивающие обработку цветных изображений в реальном масштабе времени (480x640 точек, 30 кадров/с [25]).С точки зрения достижимого уровня сжатия, стандарт JPEG не является лучшим среди существующих ныне методов эффективного кодирования изображений. Так, методы, базирующиеся на использовании векторного квантования [26-39,49] (в пространственной или спектральной областях), субполосного кодирования [36-43], преобразований на основе волновых импульсов ("всплесков") [44-50], а также фрактальные методы [51-54] -могут обеспечить значительно более высокие уровни сжатия по сравнению с JPEG. Однако пока во многих случаях внедрение новых перспективных методов упирается в проблемы сложности их реализации, которая часто объясняется отсутствием четких алгоритмов. В этом свете метод JPEG предстает как компромиссный вариант, обеспечивающий, с одной 10 стороны, достаточно высокое сжатие (10-50 раз для цветных изображений [22]), а с другой стороны - приемлемую для самого широкого применения сложность реализации. Именно-компромисс между качеством, универсальностью обработки и ее вычислительной сложностью был положен группой JPEG в основу первоначального выбора метода сжатия для последующей доработки и стандартизации [22]. Как уже отмечено выше, для кодирования изображений помимо ДКП можно использовать и другие унитарные преобразования. Например, применение для сжатия информации в ЦОИ дискретного преобразования Виленкина-Крестенсона (ДПВК) [55,56]. Система функций Виленкина-Крестенсона является частным случаем более общих мультипликативных систем [57] и была получена в результате обобщения на комплексную плоскость хорошо известной системы функций Уолша [58,59]. Дискретное преобразование Уолша прочно занимает свое место в ряду других унитарных преобразований, применяемых для обработки изображений [60-63]. Гораздо более скудную информацию можно почерпнуть в литературе по поводу практического использования ДПВК. Как наиболее полный и системный труд, в котором рассматривается не только теория, но и приложения теории, здесь нужно выделить монографию [56]; следует отметить также работы [64,65]. В некоторых источниках [56,66-68] нашли освещение и отдельные приложения ДПВК к обработке изображений. Косвенные данные позволяют предположить, что предложенные методы сжатия изображений на основе ДПВК [66,67], позволяют проводить обработку достаточно быстро (поскольку вычисление ДПВК в ряде случаев может быть сведено только к операциям типа сложения и вычитания [56]), однако, уступают по эффективности спектральным методам на основе ДКП (поскольку среди преобразований, имеющих быстрые алгоритмы, ДКП традиционно считается наилучшим для кодирования изображений [1,2,69]).
Необходимо отметить, что в случае кодирования многоцветных дискретных изображений выше представленные методы дискретных спектральных преобразований вносят значительные искажения и в ряде случаев не достигают требуемых результатов. Особенно это проявляется для изображений, имеющих множество различных небольших объектов изображения с богатой цветовой гаммой.
Повышение требований к качеству дискретного многоцветного изображения заставило искать другие методы сжатия изображения. Анализ цветовой составляющей изображения, получаемой непосредственно с цифрового устройства записи изображения, определение минимального цифрового кода записи этого изображения дает возможность определить пути сжатия цветовой информации и коррекции потерь для различного рода задач, выделения объектов, распознавания образов и т.п.
Таким образом, задача диссертационной работы была определена как исследование возможности эффективного кодирования изображений и объектов с использованием цветового анализа и разработка соответствующих методов (алгоритмов) сжатия, пригодного для практического применения. Новизна поставлен-
12 ной задачи вытекает из того, что применение цветового анализа для кодирования дискретных изображений и объектов изучено мало, актуальность обусловлена исключительной важностью проблем цифровой обработки видеоинформации, сжатия изображений и объемных сцен для передачи их по каналам связи и архивации.
В первой главе диссертации проводится краткий обзор и классификация основных подходов к реализации эффективного сжатия и обработки дискретных изображений, отмечается, что существует целый ряд методов, которые могут быть использованы для сжатия изображений с целью передачи их по каналам связи. Рассмотрены различные форматы и алгоритмы сжатия записи дискретных изображений без потерь информации. Дано сравнение эффективности существующих архиваторов для сжатия различных видов изображений.
Во второй главе рассмотрены методы дискретных преобразований изображений, их квантование и кодирования для достижения наивысших коэффициентов сжатия дискретных изображений при учете возможных потерь информации. Наибольшее внимание здесь уделено стандарту JPEG, который был выбран в качестве прототипа при сравнении с различными методами сжатия дискретных изображений.
В третьей главе рассмотрены современные требования к сжатию, обработке и передаче дискретных естественных и искусственных изображений, объектов и пространственных сцен по каналам связи. Проведен анализ стандартов передачи изображений на основе стандарта MPEG-4.
В четвертой главе рассмотрены методы описания пространственных цветных объектов, предложены методы сжатия дискретных изображений на основе цветового анализа и аналитический метод описания цветовых объектов. Дано сравнение методов описания объектов и сцен.
В приложении приведены исходные тексты программ обработки дискретных изображений и объектов на алгоритмическом языке C++ и изображения, используемые в вычислительном эксперименте.
