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

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

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

2. Высокочастотные составляющие изображения. Они отвечают за цветовые перепады - контуры изображения. Улучшая их, мы повышаем резкость изображения.

3. Текстуры изображения. Описание текстуры – чаще мультиплицируемое изображение фрагмента внутри контура.

Рассмотрим фильтры в виде квадратных матриц A. Пусть исходное изображение X, а получаемое как результат фильтрации - Y. Для простоты будем использовать матрицы 3x3:

Рекурсивными фильтрами первого рода будут такие фильтры, выход Y которых формируется перемножением весовых множителей A с элементами изображения X. Для примера рассмотрим фильтры низких частот:

.

Фильтром низких частот пользуются часто для того, чтобы подавить шум в изображении, сделать его менее резким. Используя фильтр A₃ , будем получать изображение Y следующим образом:

Выход фильтра второго рода формируется аналогично первому, плюс фильтра B:

Для простоты рассмотрим одномерный фильтр вида:

:

Рассмотрим и другие фильтры:

1. Высокочастотные (для подчеркивания резкости изображения):

2. Для подчеркивания ориентации:

3. Подчеркивание без учета ориентации (фильтры Лапласа):

.

4. Корреляционный:

, где

- коэффициенты корреляции между соседними элементами по строке (столбцу). Если они равны нулю, то отфильтрованное изображение будет совпадать с исходным. Если они равны единице, то фильтр будет эквивалентен лапласиану. При обработке изображений очень часто используют последовательность фильтров: низкочастотный + Лапласа. Часто используют и нелинейную фильтрацию. Для контрастирования перепадов изображения используют градиентный фильтр:

, или его упрощенный вид:

.

Еще один часто используемый нелинейный фильтр - Собела:

A₀ ... A₇ - входы, y_i,j - результат фильтрации.

Рекурсивная версия :

где B₀ ... B₇ - выход отфильтрованного изображения.

Кодирование с использованием цветов. Пусть изображение хранится в квадратной матрице X с элементами x_i,j N строк на N столбцов. Обрабатывая матрицу, мы будем иметь временную сложность алгоритма как минимум кратной N³ . Для ее уменьшения поступают следующим образом: разбивают изображение на несколько малых размером n на n, n << N, каждое малое изображение будем обрабатывать отдельно. Тогда, вместо N³ будем иметь N²n сложность алгоритма.

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

Самый первый способ, который приходит в голову, следующий. Уменьшим количество бит для хранения одного пикселя (элемента исходной матрицы). Пусть пикселя исходного изображения имеют формат RGB Truecolor 8:8:8 (на каждую цветовую составляющую отводится по 8 бит). Перекодируем изображение в формат 5:5:5 (то есть каждая цветовая составляющая будет иметь 2⁵ =32 градации), отбрасывая младшие четыре бита изображения. Мы также можем использовать свойство глаза наиболее хорошо различать цвет в области зеленого и кодировать изображение в формат RGB 4:5:4 и каждый пиксель будет занимать два байта.

Можно пойти еще дальше: перевести исходное изображение в другую цветовую модель и отформатировать его. Например, в YIQ 6:3:3 - отводим на яркость 6 бит, на синфазный и интегрированный каналы по 3, используя то, что человеку более важна информация об интенсивности, нежели о цвете. При «жадном» кодировании, когда используем малое количество бит на пиксел, сразу после декодирования, перед выводом изображения можно провести так называемый anti-aliasing - сгладить резкие цветовые переходы, возникшие из-за малого числа градаций цветовых составляющих. Дальнейшее усовершенствование заключается в индексировании цветов. RGB Truecolor формат может поддерживать более 16 млн. цветов. Выберем n (обычно n - степень 2 ) индексных цветов c_K так, чтобы минимизировали сумму: .

Далее создаем выходной массив B N на N, элемент которого b_i,j равен k, где k= m - номер цвета такой, что выполняется . Выходная информация - массив B и собственно таблица индексных цветов c. Результаты данного подхода можно посмотреть в разделе «Форматирование и индексирование изображений».

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

.

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

. Самый оптимальный метод - Карунена-Лоэва. Строки матрицы преобразования A - нормированные собственные вектора K_x, то есть являются решением уравнения вида K_xx = _ix, K_x = E{(x- Ex)(x-Ex)^T} - ковариация, E - мат. ожидание, T - знак транспонирования. Коэффициенты преобразования y=Ax имеют матрицу преобразования вида: . Отбрасывая малые собственные значения получаем сжатие. Данный метод, хотя и дает наименьшую ошибку приближения среди аналогичных кодеров, используется редко, так как требует большого объема вычислений при своей работе. Преобразование Карунена-Лоэва называют также оптимальным кодированием. Рассмотрим другие кодеры данного семейства:

0. Фурье, , для данного преобразования существует алгоритм, с временной сложностью n²log₂n. Преобразование Фурье представляет собой разложение по спектру.

Дискретное косинусное преобразование (ДКП). .

Наиболее используемый в настоящее время метод, так как он дает результат ошибку приближения чуть больше чем разложению Карунена-Лоэва. Существует алгоритм, реализующий данный метод со сложностью 2n²log₂n-1.5n+4.

0. Симметричное преобразование Адамара. , где i_l и j_l - состояние разрядов двоичного представление чисел i и j. Для n=2 матрица будет следующей:

.

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

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

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

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

Обычно отбрасываемые коэффициенты обнуляют. Далее применяют последовательное и энтропийное сжатие. Так работает алгоритм JPEG кодирования. Все это дает снижение размера массива, при приемлемом качестве изображения, в 5-16 раз. На приведенном примере использовалось исходное изображение в разрешении 240 на 362 пикселя в RGB Truecolor и занимало 240*362*3=260640 байт. Левое сжатое изображение занимает 46000 байт и внешне не отличается от исходного. Левое нижнее изображение имеет размер 8004 байт и имеет заметные резкие цветовые переходы в области неба. Правое нижнее изображение имеет размер 5401 байт (!) и хотя изображение стало слишком мозаичным, мы вполне можем понять его содержание. При использовании разбивок на блоки иногда возникает побочный эффект: становятся заметными границы блоков. Для борьбы с ним разбивку проводят так, чтобы блоки «наезжали» на границы соседних с ним блоков.

Другой принцип лежит в основе пирамидального кодирования. Пусть x(k,l) - исходное изображение. Получим из него его низкочастотную, с частотой среза f₁, «версию» x₁(k,l) с помощью локального усреднения. С одномодовым гауссоподобным двумерным импульсным откликом. x₁(k,l) можно рассматривать как предсказание для c. e₁(k,l) = x(k,l) - x₁(k,l) - ошибка предсказания, далее повторяем для частоты среза f₂: e₂(k,l) = x₁(k,l) - x₂(k,l) - ошибка предсказания меньше чем для e₁ в f₁/f₂ раз. Получаем в итоге последовательность e₁ ,e₂ , .., e_t. На каждой итерации размерность изображения сокращается в f_i /f_i+1 раз. Данный метод уменьшает занимаемый размер в 10..20 раз при приемлемом качестве изображения. Но сложность алгоритма выше по сравнению с предыдущими методами.

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

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

1. Уменьшение числа областей. Обычно в изображении 70% созданных областей содержатся в 4% изображения. Соседние области объединяют, если они обладают близкими свойствами, также удаляют незначительные (по размеру), области. Алгоритмы создания и удаления областей - задача не простая и может быть оптимизирована по многим направлениям различными способами. Именно от нее зависит дальнейшая эффективность алгоритма.

Рассмотрим собственно кодирование. Оно состоит из двух этапов: 1 - кодирование контуров и 2 - текстур, лежащих в них. Контуры представляются в виде матрицы с битовыми элементами, который равен 1, если точка входит в границу области - контур и 0 - иначе. Данную матрицу можно энтропийно сжать с эффективностью ~1.2 .. 1.3 бита на пиксел контура. Текстура (содержимое) каждой области приближается средним уровнем свойства ее области и двумерным полиномом (линейным, квадратным или кубическим - в зависимости от реализации и требований к качеству). При декодировании прибавим зернистость в текстуру с помощью гауссова псевдослучайного фильтра с уже известной среднеквадратичной ошибкой. Данный метод позволяет добиться сжатия изображения в 20..75 раз с приемлемым качеством изображения сохраняющим возможности распознавания. Временные затраты при его реализации весьма велики. При работе данного метода мы также можем (с небольшими дополнительными вычислениями) параллельно перевести изображение в векторную форму.

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

«Глаза» технических, медицинских систем учитывают отображение контролируемых параметров в различных диапазонах длин оптических волн. Например, у спутника МЕТЕОР-3м «4 глаза» «видят» волны в диапазонах волн -260 нм, 270 нм, 360нм, 405 нм, что позволяет контролировать содержимое озона в атмосфере на высотах 34…90 км.

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

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

формируются матрицы R, G, и B в двухмерном геометрическом пространстве;

формируется новая матрица с числом столбцов равным числу уровней квантования первой цветовой составляющей и числом строк равным числу уровней квантования второй цветовой составляющей пикселя;

матрица заполняется тегом отсутствия запроса ячейки, например, - 256 (число выбирается вне зоны существования уровней квантования третьей цветовой составляющей пикселя);

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

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

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

Рис. 7.16. Кластеры объектов в RGB пространстве (однородный тон)	Рис. 7.17. Кластеры объектов в RGB пространстве (керамический корпус микросхемы)

Рис. 7.19. Кластеры объектов в RGB пространстве (цветовой “хаос”)

На рис. 7.16, 7.17 приведен вид зон существования объектов в RGB пространстве там же приведены и исследуемые изображения.

Как видно они образуют соприкасающиеся группы точек. Для сравнения, на рис. 7.19 показано отображение цветового “хаоса”.

Матрица Z на рисунках рис. 7.16, 7.17 и 7.19 заполнена по формуле: .

Для упрощения в качестве тега отсутствия запроса ячейки принято число “0”, а информация о точках с утеряна, имеет место и маскирование пикселями с предыдущих записей.

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

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

Рис. 7.20. Индикатор цвета на цветовой плоскости (однородный фон)	Рис. 7.21. Индикатор цвета на цветовой плоскости (керамический корпус микросхемы)

Рис. 7.22. Индикатор цвета на цветовой плоскости ( цветовой “хаос”)

Матрица Z на рисунках рис. 51, 52 и 53 заполнена по формуле: .

Оси цветов для представления индексов в целых числах умножены на 100.

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

Рис. 7.23. Цветовая гистограмма на цветовой плоскости ( керамический корпус микросхемы)

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

Рис. 7.24. Цветовая гистограмма на цветовой плоскости ( однородный фон)

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

Простейшие задачи распознавания решаются сечением пространства признаков плоскостями, разделяющих зоны описаний классов, например, через задание порогов по R, G, B компонентам (рис. 7.26 пороги rs, gs, bs).

Рис. 7.25. Вариант оформления работы по анализу цветовых гистограмм

Рис. 7.26. Яркостные сигналы и пороговое задание гиперконуса принятия решений

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

Сформируем прозрачную маску mask1 на распознаваемое здание (код 255 назначим прозрачным цветом, такое решение часто используется в графических редакторах):

.

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

Рис. 7.27. Выделение зон металлических корпусов

Автоматическое задание фиксированных порогов по цветовым составляющим предполагает наличие алгоритмов определения уровня освещенности объектов. Но освещенность отдельных фрагментов объекта может значительно изменятся из-за его пространственного положения. Выходом может стать переход к распознаванию объектов в нормированном цветовом пространстве. На рис. 7.28 приведены нормированные сигналы r, g, b полученные из исходных R, G, B путем их деления на сумму R+G+B, вычисляемой для каждого пикселя.

Рис. 7.28. Нормированные цветовые сигналы

Как и в первом случае сформируем прозрачную маску но с относительными соотношениями:

.

Рис. 7.29. Выделение зон металлических корпусов по цветовым сигналам

Результаты вычислений представлены на рис. 7.29. Как видно, отдельные элементы здания распознаны различными алгоритмами не однозначно.

Бесспорное преимущество второго метода в его независимости от освещенности объекта.

Первый метод косвенно использует информацию об освещенности пикселя и данный признак способствует лучшему распознаванию объектов в данном случае.

Перечислим перечень операций, часто используемый при распознавании объектов в нормированном цветовом пространстве:

вычислим сумму цветовых сигналов в точке;

определим нормированные цветовые составляющие;

назначим исключаемую из рассмотрения нормированную цветовую составляющую (обычно не учитывают цветовую составляющую в равной мере присущую всем объектам);

понизим размерность цветового пространства на единицу;

назначим новые координатные оси;

отобразим следы объектов или их гистограммы в новой системе координат;

Далее проведем решающие границы и классифицируем объекты.

Уменьшение цветового описания без потери возможности распознавания – классическая процедура в работе с пространством признаков, позволяющая получить двухбитное описание пикселя, т. е. понизить объем в 12 раз. Рис. 7.30 изменение объемов описаний (1Мпиксель) от 3Мбайта → 1 Мбайт →0,5 Мбайта. Там же для индексных цветов представлены и палитры цветов. Назначение компонентов палитры – сложная процедура и она должна выполняться как процедура распознавания. Например, поиск зрелых кистей винограда на фоне листвы и незрелых плодов. Виден на рисунке и ошибочный вариант перекодировки – ягода верхней кисти последовательно изменила окрас и стала почти не различима на фоне листвы.

Рис. 7.30. Понижение цветового описания пикселя.

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

Рис. 7.31. Гистограммы цветных сигналов.

Например: Красная составляющая представлена двумя битами в семибитном описании. Определяем концы трех из четырех участков (ниже формулы только для первого (после нулевого))

Рис. 7.32. Гистограммы нулевого и первого участков R массива.

Рис. 7.33. Гистограммы второго и четвертого участков R массива.

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

Цвета перекодированы.

Рис. 7.34. Фрагмент исходного и перекодированного изображения.

Палитра формируется как массив, в котором указаны по индексам значения RGB. Формулы только по красному.

Рис. 7.35.Вид палитры графический.

Рис. 7.36.Условное изображение палитры