И.М.Журавель "Краткий курс теории обработки изображений"

В оглавление книги\ К следующему разделу \ К предыдущему разделу

Оптимизация палитры изображений

Одной из наиболее удобных форм представления информации, которая возникает при разного рода исследованиях, является изображение. Все изображения можно условно разделить на четыре типа - бинарные, полутоновые, палитровые и полноцветные. Бинарные и полутоновые представляют собой двумерные массивы чисел, которые являются эквивалентами яркостей. Полноцветные изображения хранятся в виде трехмерных массивов. Для доступа к значениям интенсивностей, составляющих цвета пикселя, необходимо указать координаты (k, l) и номер составляющей: 1 - для R, 2 - для G и 3 - для B. Палитровые изображения хранятся в виде двумерных массивов, в трех столбцах которых размещены значения интенсивностей R, G, B.

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

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

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

Это привело к необходимости создания в некоторой степени универсального метода преобразования палитры цветных изображений. Анализ известных подходов подтолкнул к использованию кластерного анализа гистограммы изображений. Рассмотрим методы кластерного анализа более детально.

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

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

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

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

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

Классификация по ближайшему соседу

Предположим, что имеются образцы, полученные для каждого класса. Пусть x_i,j - вектор признаков для j-го образца i-го класса. Один из возможных путей для классификации неизвестного вектора х заключается в нахождении образца, ближайшего к неизвестному, и определении класса, к которому он относится. Для некоторых k и l это означает, что если |x_k,l -x|<|х_i,j - x| для всех i и j, то неизвестный х принадлежит классу k.

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

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

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

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

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

Классификация по ближайшей центроиде

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

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

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

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

Автоматическое формирование кластера

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

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

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

Литература

1. Duda R. O., Hart P.E., Pattern Classification and Scene Analysis, john Wiley & Sons, New York, 1973.
2. Хорн Б.К.П. Зрение роботов: Пер. с.англ. - М.: Мир, 1989. - 487 с., ил.

В оглавление книги \ К следующему разделу \ К предыдущему разделу