Содержание к диссертации
Введение
Глава 1 Анализ методов кодирования, сжатия и передачи дискретных изображений
1.1 Графические форматы BMP, TIFF, GIF, JPEG 13
1.2 Алгоритмы сжатия изображений без потерь 21
1.3 Методы спектрального сжатия дискретных изображений 40
1.4 Фрактальное сжатие изображений 51
1.5 Метод волновых всплесков 52
1.6 Сжатие изображений на основе их представлений в виде полевой структуры
1.7 Стандарт сжатия цифровых изображений JPEG 58
1.8 Требования к цифровой обработке и передаче видеоинформации по каналам связи
1.9 Сравнение существующих форматов изображений 73
1.10 Выводы 75
Глава 2 Методы и алгоритмы цветового анализа и сжатия изображений 77
2.1 Цветовой анализ изображения 78
2.2 Цветовое арифметическое сжатие 90
2.3 Сканирование изображений 94
2.4 Снижение цветовой избыточности 99
2.5 Кодирование и декодирование цветного изображения 103
2.6 Выводы 106
Глава 3 Методы и алгоритмы выделения объектов на цветном изображении 107
3.1 Разделение изображения на серую и цветовую составляющие 108
3.2 Поиск объектов на изображении 111
3.3 Локализация выделенных объектов 112
3.4 Удаление избыточной информации из изображения 112
3.5 Выводы 114
Глава 4 Экспериментальная проверка разработанных методов и алгоритмов 115
4.1 Цветовой анализ сложных изображений 116
4.2 Цветовое сжатие изображения 120
4.3 Выделение объектов на цветном изображении 124
4.4 Выводы 128
Заключение 129
Литература 130
Приложение 1 Тестовые цветные изображения, форматы, сжатие 143
Приложение 2 Тексты экспериментальных программ 151
- Стандарт сжатия цифровых изображений JPEG
- Кодирование и декодирование цветного изображения
- Удаление избыточной информации из изображения
- Выделение объектов на цветном изображении
Введение к работе
Человек в своем повседневном существовании получает из окружающего мира через органы чувств информацию, необходимую для его деятельности. 98 % этой информации приходится на зрение. Создание, сохранение, обработка и передача зрительных образов (изображений), сопровождает человечество во всей его истории. Наскальные и песчаные рисунки, графические наброски, чертежи, художественные полотна, фотографии, кино, телевидение, интернет - вот этапы использования изображений человеком в его жизни. Развитие науки и техники позволило человеку изучить собственное зрение, представить методы и алгоритмы обработки изображений человеческим мозгом, создать средства передачи изображений на большие расстояния.
Появление телевидения напрямую связало задачи обработки изображений с задачами обработки электрических сигналов, а необыкновенный подъем в последние десятилетия цифровой электроники привел к тому, что повсеместный переход от аналоговых форм представления сигналов (аналоговое телевидение) к цифровым изображениям стал характерной чертой современных электронных систем, и приобретает сегодня особую актуальность.
Если вернуться к человеку, то он получает видео информацию [1] в области световых частот (700-300 нм) в дискретном виде. Сетчатка глаза содержит около 127 млн. рецепторов (120 млн. палочек для рассматривания черно-белого изображения и 7 млн. колбочек, каждая из которых содержит три отдельных приемника для различения лучей красного, зеленого и синего цвета). Плотность размещения рецепторов 160 тыс. на 1 кв. мм. Глаз обладает глубокой адаптацией по отношению к интенсивности света, то есть он может различать огромное количество порогов яркости и соответственно огромное количество цветов при смешивании лучей красного, зеленого и синего цветов.
Информация от рецепторов в виде электронных импульсов очень малой мощности по 127 млн. нервным волокнам поступает в слепое пятно одновременно,
5 то есть имеет место параллельная передача информации. Затем в слепом пятне
происходит первичная обработка зрительной информации (фильтрация и сжатие) и далее из слепого пятна зрительная информация передается для обработки в головной мозг уже только по 1 млн. нервным волокнам. Как видим, здесь также имеет место параллельная передача зрительной информации. Мы не знаем точно, как мозг запоминает и обрабатывает зрительную информацию. Имеется ряд гипотез и этот вопрос постоянно изучается.
Ученые создали электронные устройства, которые запоминают, передают и строят изображения на экране, но это выполняется в основном последовательно (в редких случаях параллельно), а по своей разрешающей способности и пороговой чувствительности такие устройства намного уступают человеческому глазу.
В вопросах параллельной обработки изображении результаты в вычислительной технике по сравнению с человеком весьма скромные.
Просматриваются два пути ускорения обработки и передачи изображений: параллельный процесс или при последовательном процессе сжатие данных с последующим восстановлением.
В первом случае нужно фиксировать изображение с помощью матриц определенного разрешения и значение каждого элемента матрицы передавать по отдельному каналу. Число таких каналов будет равно числу элементов матрицы. Если изображение имеет миллион элементов, то и каналов нужно будет столько же. Разворачивать такое изображение не будет необходимости, так как все элементы изображения будут приходить одновременно и выводиться сразу же в определенной точке поля изображения. Такая реализация возможна на уровне нанотехноло-гий и использования для каналов очень высоких частот, проникающих на большие расстояния (например, гравитационные волны). Пока это не достижимо.
Следующий путь заключается в сжатии информации после получения с устройств фиксации изображения до минимальных размеров, передача сжатой информации по каналам связи и восстановления этой информации в виде изображе-
ния. Время суммы всех трех этапов обработки видеоинформации определит время общения. Задача перед исследователями и разработчиками заключается в снижении временных показателей на всех этапах обработки информации. При этом необходимо учитывать разрешающую способность видеоинформации (градаций яркости и цветности), искажения ее в результате передачи по каналам связи и потерь качества и цветности в результате ее воспроизведения. Видеоинформация проходит процесс преобразования ее в двоичную форму и обратно и понятно, что при этом возможны потери информации.
Повышение требований к качеству получаемого дискретного многоцветного изображения заставляет искать новые пути кодирования зрительной информации и разрабатывать эффективные методы сжатия изображения.
Одним из таких путей может быть анализ цветовой составляющей изображения, получаемой непосредственно с цифрового устройства записи изображения, определение минимального цифрового кода записи этого изображения, разработка методов сжатия цветовой информации с коррекцией потерь для решения задач передачи изображений, архивирования, выделения и распознавания объектов на изображении и т.п.
Таким образом, задача диссертационной работы была определена как исследование возможности эффективного кодирования изображений с использованием цветового анализа и разработка соответствующих методов (алгоритмов) сжатия, пригодного для практического применения.
Новизна поставленной задачи вытекает из того, что применение цветового анализа для кодирования дискретных изображений изучено мало, актуальность обусловлена исключительной важностью проблем цифровой обработки видеоинформации, сжатия изображений для передачи их по каналам связи и архивации.
В первой главе диссертации проводится анализ и классификация основных подходов к реализации эффективного сжатия и обработки дискретных изображений, отмечается, что существует целый ряд методов, которые могут быть исполь-
7 зованы для сжатия изображений с целью передачи их по каналам связи.
Рассмотрены различные форматы и алгоритмы сжатия записи дискретных изображений без потерь информации. Рассмотрены методы дискретных преобразований изображений, их квантование и кодирования для достижения наивысших коэффициентов сжатия дискретных изображений при учете возможных потерь информации. Наибольшее внимание здесь уделено стандарту JPEG, который был выбран в качестве прототипа при сравнении с различными методами сжатия дискретных изображений. Рассмотрены современные требования к сжатию, обработке и передаче дискретных естественных и искусственных изображений по каналам связи. Проведен анализ стандартов передачи изображений на основе стандарта MPEG-4.
Дано сравнение эффективности существующих архиваторов для сжатия различных видов изображений.
Во второй главе представлены разработанные методы и алгоритмы цветового сжатия изображений: цветовой анализ, сканирование изображений, арифметическое сжатие цветовых полей, снижение цветовой избыточности и восстановление цветного изображения.
В третьей главе рассмотрены разработанные методы распознавания объектов на цветном изображении: выделение цветовых контуров объектов, определение однотипных объектов, локализация выделенных объектов, удаление избыточной информации из изображения.
В четвертой главе представлены результаты экспериментальной проверки предложенных методов (алгоритмов) и сравнение их с другими методами.
В приложении приведены фотографии, используемые в вычислительном эксперименте, таблицы и графики сравнений, исходные тексты некоторых программ обработки цветных дискретных изображений на алгоритмическом языке C++.
Стандарт сжатия цифровых изображений JPEG
Вызванное революционным развитием вычислительной техники громадное увеличение сферы и объема приложений ЦОИ привело к лавинообразному росту числа групп разработчиков цифровых систем обработки и передачи изображений. Необходимость обмена данными между различными программными и аппаратными системами ЦОИ быстро обострила вопрос унификации форматов визуальных данных, представленных в сжатом виде. С целью решения задачи стандартизации сжатых форматов цифровых изображений на базе МОС и МККТТ была создана объединенная группа экспертов JPEG. Для максимально широкого круга цветных изображений разрабатывавшийся стандарт должен был удовлетворять следующим основным требованиям [58]:
- обеспечивать максимально высокое сжатие данных и точность их восстановления, причем процесс кодирования должен быть управляемым, так чтобы пользователь мог устанавливать желаемое соотношение между уровнем сжатия и качеством восстановленного изображения;
- быть применимым к практически любому кругу полутоновых изображений, вне зависимости от размерности, цветности, других свойств изображения), иметь при 59
емлемую вычислительную сложность.
Окончательно из 12 первоначально предлагавшихся методик в 1988 году был отобран один вариант, нашедший в 1991 году отражение в виде предварительного стандарта JPEG [59,60]. Разработанный стандарт, достаточно всеобъемлющий, имеет как обязательные, так и необязательные составляющие. Рассмотрим лишь основную схему кодирования (baseline sequential encoding) (рис. 1.1).
При обработке исходное цифровое изображение разбивается на квадратные фрагменты размером 8x8 пикселов, из которых и образуется входной поток данных кодера JPEG.
Второй шаг. Скалярное квантование спектра ДКП: каждый элемент спектра равномерно квантуется независимо от других с округлением до целого. Целая величина определяется по таблице (матрице) квантования (размера 8x8), задача формирования которой лежит на разработчике системы сжатия. Поскольку таблица квантования стандартом не регламентируется (хотя имеется рекомендуемый набор таблиц), она передается в заголовке выходных данных, т.к. знание таблицы квантования необходимо для последующего восстановления изображения. Диапазон возможных значений, которые могут принимать элементы спектра, после выполнения процедуры квантования существенно уменьшается, появляется большое количество нулей.
Третий шаг. Коэффициент спектра (постоянная составляющая яркости фрагмента изображения) подвергается ДИКМ. ДИКМ целесообразно применять по причине того, что средние значения яркости соседних фрагментов, как правило, имеют близкие значения. Полученный после ДИКМ двумерный набор из 64 чисел (рис.2.2) зигзагообразно считывастся в одномерную последовательность, образуя промежуточный поток данных, который является входным для 4-го шага.
Смысл такого зигзагообразного считывания заключается в том, чтобы сгруппировать основную часть нулевых элементов спектра, которые оказываются сосредоточенными в конце 64-элементного блока промежуточного потока данных.
Четвертый шаг. Удаление нулей. Нули удаляются путем преобразования промежуточного потока в два выходных потока. При появлении во входном промежуточном потоке ненулевого элемента S производится запись в выходные потоки. Первый выходной поток данных состоит из байтов-ключей: в первом полубайте записывается число нулей, встретившихся перед элементом после предыдущего появления ненулевого элемента, а во втором полубайте записывается число, которое равно числу двоичных разрядов, необходимых для представления элемента S. Во второй поток заносится число бит двоичного кода элемента S. Таким образом, первый поток данных - байтовый, второй - битовый. Битовый поток данных (с кодами ненулевых элементов) дополнительно не обрабатывается, а поток байтов-ключей кодируется статистически. В результате выполнения этих действий объем данных, подлежащих статистическому кодированию, существенно уменьшается.
Пятый шаг. Далее осуществляется энтропийное (статистическое) кодирование байтов-ключей. В базовой схеме кодирования JPEG для этой цели используется алгоритм Хаффмена [42]. Таблицы кодов Хаффмена должен строить сам разработчик системы сжатия (например, в результате статистического анализа данных обработки изображения, или исходя из каких-то априорных сведений), поэтому таблицы кодов Хаффмена необходимо помещать в заголовок выходных данных системы сжатия. Однако большей эффективности можно достичь, если вместо кодирования по Хаффмеиу использовать арифметическое кодирование [42]. В этом случае кодовые таблицы не используются и, соответственно, не заносятся в выходные данные.
Кодирование и декодирование цветного изображения
В соответствии с предложенными в данной главе методами и алгоритмами рассмотрим задачу и схемы кодирования и декодирования цветных изображений.
Исходное изображение поступает с приемной матрицы фото или видео камеры или со сканера в формате BMP. Это изображение имеет полную цветную информацию и поступает непосредственно в средства кодирования и сжатия данных. Средства обработки данных могут работать с потерей исходных данных или нет. Во многих случаях при обработке данных исходная информация теряется или искажается и задача аппаратуры, чтобы эти потери и искажения были минимальными. После архивирования или передачи дан 104 ных при восстановлении для средств обработки данных также ставится задача минимальных потерь и искажений.
При решении задачи кодирования и декодирования изображений большое значение приобретают такие параметры как:
- процент потерь информации;
- процент искажений изображений (добавление ненужной информации);
- время кодирования (сжатия) изображений;
- время декодирования (восстановления) изображений;
- размеры изображения;
- разрешение изображения;
- число используемых цветов.
Так как данная задача является многокритериальной и имеет сложные зависимости между вышеперечисленными параметрами, то при конструировании аппаратных и программных средств ряд параметров устанавливают константами и решают данную задачу.
На рис.2.10 представлена схема кодирования изображений и представления их в виде файлов сжатых изображений для архивирования и передачи по каналам связи.
На рис.2.11 представлена схема декодирования архивированных файлов сжатых изображений и представления их в виде файлов формата BMP для вывода на печать и экраны графических устройств.
Анализируя схему кодирования изображений, видим, что большое число операций с массивами данных (пикселами) приходится на анализ исходного изображения. Следовательно, и время анализа является наибольшим при кодировании изображения.
При декодировании сжатых файлов цветовой анализ отсутствует, используются только полученные при кодировании результаты, поэтому схема декодирования работает во много раз быстрее.
Количественные оценки работы схем для выбранных экспериментальных изображений приведены в 4-ой главе.
Удаление избыточной информации из изображения
Как было ранее отмечено, что полноцветные изображения содержат довольно много избыточной информации, которая может быть удалена без ущерба для качества изображения или для специальных целей.
Для передачи по каналам связи особенно важно иметь минимальные объемы передаваемой информации.
При слежении за объектом, за его изменениями, часто достаточно иметь упрощенное (контурное) изображение выделенного объекта.
Для такого случая предлагается алгоритм сжатия выделенного цветового объекта:
1. Открываем файл полного изображения выделенного объекта.
2. Читаем цвет выделенного объекта.
3. Удаляем серую составляющую из полного изображения выделенного объекта.
4. Выбираем коэффициент заполнения точками изображения выделенного объекта.
5. Формируем цветовое поле выделенного объекта.
6. Формируем уровневое битовое поле выделенного объекта
7. Выполняем двоичную битовую упаковку растрового массива.
8. Формируем заголовок файла выделенного объекта.
9. Формируем упакованный файл выделенного объекта.
10.Сжимаем полученный файл WinRar и получаем архивный файл, который может быть использован для передачи данных по каналам связи. В результате работы данного алгоритма происходит эффективное сжатие выделенного объекта с коэффициентом в десятки тысяч раз по сравнению с полным исходным изображением, из которого выделяли объект.
Данный алгоритм работает с потерей исходных цветовых данных выделенного объекта.
Алгоритм восстановления работает следующим образом:
1. Распакуем архивный файл архиватором WinRar.
2. Читаем заголовок файла.
3. Распакуем битовый растровый массив.
4. Преобразуем битовый растровый массив в байтовый массив.
5. Восстановим растр изображения выделенного объекта в формат BMP, используя спиральную развертку.
6. Запишем заголовок файла восстановленного изображения выделенного объекта.
7. Формируем файл изображения выделенного объекта в однотонном цвете в формате BMP.
При восстановлении сжатого выделенного объекта получим точечное однотонное изображение выделенного объекта.
Алгоритмы сжатия и восстановления работают очень быстро и приблизительно в отношению 1:1. 3.5 Выводы
В данной главе представлены методы и алгоритмы цветового выделения объектов из полного изображения.. Предложенные методы и алгоритмы не описываются сложными математическими выкладками, которые имеют место при установлении связи математической модели дискретного цветного изображения с математической моделью освещения (обе модели приведены во 2-ой главе настоящей диссертации).
Высказано предположение, что в фиксированных дискретных изображениях влияние интенсивности освещения на форму реального объекта незначительно для решения задач определения вида и типа объекта, в отличие от технических задач, где определение размеров объекта является крайне важным.
Для решения технических задач выделения объектов на изображении необходимо учитывать много различных параметров освещения и физических свойств поверхностей объектов, что значительно усложняет решение поставленной задачи выделения объектов и определения его размеров с высокой точностью.
В 4-ой главе предлагаемые методы и алгоритмы проверяются на различных изображениях, и будет оценена их эффективность для архивирования и передачи по каналам связи.
Выделение объектов на цветном изображении
Результаты работы программ цветового анализа GRNSPG, ANLZIMG и RSLTANLZ для всех тестовых изображений приведены в табл. 4.1. — 4.3.
Вначале с помощью программы GRNSPG из исследуемого изображения (полное) выделяется серое изображение, которое при этом очищается от цветового шума, и выделяется цветовое изображение, которое при этом очищается от избыточного освещения.
Затем программа ANLZIMG определяет все цветовые характеристики.
Анализ полных изображений показывает, что в них практически отсутствуют чистые цветовые тона, что говорит о наличии цветовых шумов, неравномерности освещения.
На сером изображении цветовой шум отсутствует, и изображение при-обретает большую четкость в черно-белом изображении.
На цветном изображении появляются полутона чистых цветов, что говорит о наличии цветовых объектов, и проявляется цветовой шум.
Показатели цветового сжатия для тестируемых изображений как результаты работы программ CDIMG, PAKIMG и CHLNCL даны в табл. 4.4 - 4.14.
Синим цветом показаны коэффициенты сжатия без потерь данных, а красным цветом показаны коэффициенты сжатия с потерями данных.
Анализ коэффициентов сжатия показывает, что наибольших результатов можно достигнуть, применяя комбинированные методы.
Наиболее эффективным методом оказался комбинированный метод «Цветовое сжатие + WinRar». 4.3 Выделение объектов на цветном изображении
Выделенные программами GRNSPG, CUTTMG и CMPRCUT объекты показаны на рис.4.1 - рис.4.11, показатели их сжатия приведены в таблице 4.15.
На каждом из тестовых изображений выделены характерные и узнаваемые объекты, хотя могут быть выделены любые цветовые объекты, имеющие характерную окраску.
