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

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

Центральным вопросом при решении задачи представления коллекции цифровых изображений на плоскости является способ построения отображения в двумерное пространство. Естественный с точки зрения теории распознавания образов и принятый во многих работах по данной тематике [8,9,14,25,16,18,19,24] подход к отображению состоит в извлечении из изображений каких–либо признаков и размещении изображений в соответствии со значениями признаков. Так как размерность пространства признаков может в десятки и сотни раз превышать размерности пространства отображения, то для создания двумерных отображений необходимо применять методы снижения размерности.

Методы снижения размерности обычно подразделяют на линейные и нелинейные. Линейные методы используют дискретный вариант разложения Карунена – Лоэва, называемый также методом главных компонент (PCA - Principal component analysis). В этом методе осуществляется поворот системы координат в исходном пространстве признаков таким образом, чтобы в проекции на новые оси – главные компоненты – дисперсия всего множества точек была максимальна. При этом дисперсия сосредоточена большей частью в первых компонентах, что позволяет рассматривать только их, отбрасывая остальные. Метод PCA был использован при создании относительно небольшого числа систем [12, 16].

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

1N s = уУА

A d ij i< j

⁽ d ij - d * )

dij

(здесь d_ij и d_i ^* _j - расстояние между объектами i и j , соответственно, в многомерном и двумерном пространстве, N - количество объектов), ее называют ошибкой Сэммона, а соответствующий метод снижения размерности называют методом двумерного отображения Сэммона [6].

Нелинейные методы отображения применяются во многих системах, описанных в литературе [3,4,16,20-22,24].

Среди нелинейных методов, применяемых для снижения размерности, можно выделить отдельный класс алгоритмов, использующих силовые методы укладки графов. Работа этих алгоритмов основана на математических моделях механических процессов. Наиболее известными являются модели Фрух-термана - Рейнгольда [11] и Камада-Кавайи [13].

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

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

Одной из важнейших проблем при применении нелинейных методов снижения размерности является высокая вычислительная сложность таких методов. Вследствие этого исследователями в самых различных областях предпринимаются попытки построения методов, имеющих пониженную вычислительную сложность [3,4,7,15,17]. По этой же причине некоторые исследователи используют иерархические структуры, группирующие объекты в соответствии с их характеристиками (кластеризация) [8,14,16,18,19]. В некоторых работах нелинейные методы снижения размерности применяются лишь к подмножествам коллекции изображений [16].

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

1.    Описание методов, используемых в работе

В основе всех рассматриваемых в работе методов лежит алгоритм двумерного отображения, описанный, в частности, в [6] и впервые примененный Сэммоном в 1969 году. Данный алгоритм позволяет минимизировать ошибку представления многомерных данных, выражаемую в виде (1).

Работа алгоритма имеет итеративный характер, связанный со следующим рекуррентным соотношением для координат в двумерном пространстве y_jk :

• У k ⁽ t + 1) = У k ⁽ t ) +

• 2 .a NUj - d * ,

+■« S . _d* • ( y » ⁽ t ) - y , ⁽ t ) ) .

X d , j i,^d' . •

• < j

Настраиваемый параметр а влияет на скорость работы и сходимость алгоритма.

Следует отметить, что возможно использование двухэтапного метода снижения размерности пространства. В таком методе на первом этапе с помощью дискретного линейного преобразования Кару-нена-Лоэва находится грубое приближение решения. На втором этапе полученное приближение уточняется описанным выше нелинейным методом снижения размерности Сэммона. В ряде работ указывается, что такой двухэтапный метод обладает в среднем более высокой точностью и более быстрой сходимостью [3,16].

Тем не менее приведенный в настоящем разделе алгоритм нелинейного снижения размерности хорошо работает на небольших объемах данных, однако на больших объемах данных возможности применения алгоритма ограничивает вычислительная сложность. При объеме выборки N и числе итераций, сравнимом с объемом выборки, объем вычислений, требуемый для получения отображения, имеет порядок O[N3].

1.1.    Модифицированный метод снижения размерности с использованием триангуляции

Одним из распространенных способов снижения вычислительной сложности базового метода Сэм-мона является использование триангуляции [15, 17]. В данном методе сначала с использованием базового алгоритма ищется решение для некоторого количества объектов M. Затем производится последовательное добавление (N-M) объектов с использованием триангуляции. При этом для каждого объекта o_z, z' = (M +1)..N объектов выбирается два объекта o,, ok, j, k = 1..M из числа уже спроецированных с использованием базового алгоритма, а положение (y₁; y₂) объекта o на плоскости определяется, исходя из соотношений, обеспечивающих точное сохранение расстояний между рассматриваемыми объектами:

d , = d , , d k = d k .

Если выполнение соотношений невозможно, то за искомое положение объекта o берется точка ( y ₁ ; y ₂ ) на отрезке ( y_{j 1} ; y_{j 2} )( y_{k 1} ; y_{k 2} ), для которой выполняется: d j/ d k = d_z ‘/ d_z*_k . Если выполнение приведенных соотношений возможно и существует два решения ( y ¹ ₁ ; y ¹ ₂ ) и ( y ² ₁ ; y ² ₂ ) , то из числа уже спроецированных объектов берется еще один объект o s , s = 1.. M и искомое решение выбирается исходя из соотношения:

• ⁽ у 11 ; У, 2 ), если | ^d s* ^{- d} s | ^ | ^dz 2 ‘ ^{- d} s |,

• ⁽ y , 2 ; У , 22 ), если | ^ds ^{- d} s | > | ^d, ²‘ ^{- d} s |, где d ¹ _s ^* и d ² _s ^* - расстояния от точек ( y ¹ ₁ ; y ¹ ₂ ) и ( y ² ₁ ; y ² ₂ ) до точки ( y_{s 1} ; y_{s 2} ).

В противном случае решение ( y ₁ ; y ₂ ) единственно.

• 1.2.    Модифицированный метод снижения размерности с использованием линейного преобразования

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

Пусть координаты M объектов (M, проецируемых базовым методом Сэммона, образуют мат-

⁽ y, 1 ; у i 2 ) =

рицу Y = [ y k ] i = 1 _M . Матрица расстояний между ни- к = 1,2

ми D = Гdjj 1 i=1 м . Тогда матрица линейного преоб-j=1.M разования V = [vk ] i=1 м может быть определена из к=1,2

соотношения:

D ■ V = Y.

Отображение    Y' = [yk ] i=1 (N-м)    оставшихся к=1,2

(N - M) объектов можно определить, имея расстояния D' = I d„ I , ,N „, между ними и объектами, ..12« j=1.. м которые уже были спроецированы с использованием базового метода Сэммона, а также, зная матрицу линейного преобразования, следующим образом:

Y ' = D ' х V .

• 1.3.    Метод снижения размерности с использованием стохастического

алгоритма аппроксимации

Приведенные в предыдущих разделах алгоритмы нелинейного снижения размерности используют для отображения некоторой части исходного множества объектов базовый метод Сэммона, требующий для получения отображения при объеме выборки M и числе итераций, сравнимом с объемом выборки, проведения вычислений в объеме O [ M ³] . Учитывая, что экспериментальные исследования [17] показали целесообразность использования в качестве исходного множества M = ^^ N из общего числа N объектов, теоретическая оценка сложности рассмотренных методов остается высокой.

Решением проблемы высокой вычислительной сложности может быть алгоритм, использующий аппроксимации приращений координат точек на каждой итерации. При этом, если вычислительная сложность для построения аппроксимационной оценки приращений координат объекта на каждой итерации составляет О[к ], где к <<  N , то вычислительная сложность всего алгоритма может быть снижена до O [ N ² ] .

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

( ^dj ^- d j )

N e=Z

^di ² j

однако он может быть применен и при минимизации ошибки Сэммона (1) (далее будем называть этот метод методом ЧС).

1.4.    Комбинированный метод снижения размерности пространства

Еще одним методом, рассматриваемым в настоящей работе, является модифицированный комбинированный метод (МКМ) снижения размерности, предложенный автором настоящей работы [3,4]. Подход, положенный в основу метода, состоит в использовании при снижении размерности результатов иерархической кластеризации в рамках двухэтапной процедуры следующего вида. На первом этапе для всех k кластеров самого верхнего уровня строится двумерное отображение центров этих кластеров. На втором этапе строится k отображений для подкластеров и объектов второго уровня. При этом для построения отображения каждого подкластера расположение координат центров кластеров самого верхнего уровня фиксируется, а производится оптимизация положения на плоскости только объектов, находящихся в рассматриваемом подкластере. Процесс повторяется для третьего уровня иерархии и так далее, пока не будет построено отображение всех объектов.

В работе [3] было показано, что в случае сбалансированного дерева кластеров высотой L = log _к N , когда в каждом кластере оказывается k элементов,

Г 1 +-1 выражение сложности принимает вид O N ^L .

Результаты экспериментального исследования представленных в этом разделе методов приведены в разделе 2.

2.    Экспериментальные исследования

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

В системах поиска и навигации по коллекциям цифровых изображений широкого класса в качестве системы признаков хорошо зарекомендовали себя гистограммы цветов. В настоящей работе при построении цветовых гистограмм было использовано цветовое пространство CIE L*a*b* [1], основным преимуществом которого является тот факт, что рассогласование цветов, рассчитываемое как Евклидово расстояние между цветами, соответствует человеческому восприятию.

В рамках проведенных экспериментов были исследованы все методы, описанные в п. 2. При проведении исследования использовались цветные цифровые изображения из коллекции PhotoClipart 2002, содержащей цифровые фотографии различной тематики (люди, животные, техника, искусство, природа и т.п.), а также искусственные 3D сцены. Во время проведения эксперимента из исходной коллекции изображений случайным образом генерировались наборы по 500, 1000 и 2000 изображений и каждый из методов применялся к сгенерированным наборам. Для оценки качества работы алгоритмов в соответствии с критерием (1) рассчитывалось значение ошибки, а также измерялось время функционирования алгоритмов. Работа методов останавливалась, когда положение объектов на плоскости стабилизировалось либо число выполненных итераций достигало максимального значения, выбираемого в соответствии с числом объектов в соответствующей выборке. Результаты проведенных исследований приведены в таблицах 1-3.

Отметим, что время работы всех исследованных методов существенно зависит от конфигурации используемой ЭВМ (используемого процессора, объема оперативной памяти и т.д.). При проведении экспериментов использовался ПК на базе AMD Athlon 1,6 ГГц.

Таблица 1. Анализ методов на наборах по 500 изображений

Метод	Среднее значение ошибки	СКО ошибки	Среднее время работы, сек
Триангуляция	0,068	0,008	19
Линейное преобразование	0,053	0,006	19
Стохастический алгоритм аппроксимации (ЧС)	0,038	0,009	7
МКМ	0,033	0,004	6

Таблица 2. Анализ методов на наборах по 1000 изображений

Метод	Среднее значение ошибки	СКО ошибки	Среднее время работы, сек
Триангуляция	0,071	0,014	359
Линейное преобразование	0,055	0,006	360
Стохастический алгоритм аппроксимации (ЧС)	0,033	0,007	55
МКМ	0,034	0,002	13

Таблица 3. Анализ методов на наборах по 2000 изображений

Метод	Среднее значение ошибки	СКО ошибки	Среднее время работы, сек
Триангуляция	0,055	0,011	5231
Линейное преобразование	0,041	0,015	5245
Стохастический алгоритм аппроксимации (ЧС)	0,031	0,012	253
МКМ	0,032	0,002	38

Из приведенных результатов исследований видно, что наилучшими методами по качеству формируемого отображения являются метод ЧС и метод МКМ. Судя по результатам, можно говорить о приблизительно равном качестве построения отображения коллекции изображений. Указанные методы также имеют существенно меньшее среднее время работы. Кроме того, очевидно, метод МКМ требует существенно меньше времени при большем размере коллекции (1000 и 2000 изображений).

Следует отметить, что для работы метода МКМ требуется выполнение иерархической кластеризации. В качестве метода кластеризации в работе использовался вызываемый в рекурсивном порядке нейросетевой алгоритм WTA, функционирующий на базе нейронной сети Кохонена [2,5]. При этом среднее время, затрачиваемое алгоритмом WTA на кластеризацию данных объемом 500, 1000 и 2000 изображений, составляет 8 сек.,16 сек. и 28 сек., соответственно. Максимальный размер кластеров был выбран равным 23, 32 и 45 объектам в кластере, соответственно трем указанным выше объемам выборки.

Отметим также, что существенным преимуществом метода МКМ является относительно малый размер требуемой оперативной памяти. При применении данного метода требуется хранение лишь k ² расстояний, где k - максимальный размер кластера.

Пример работы метода МКМ для набора из 1000 изображений показан на рис. 1.

3.    Заключение

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

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

Рис.1. Пример представления коллекции изображений

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

Работа выполнена при поддержке российского фонда фундаментальных исследований: проекты №06-01-00616-а, 07-07-97610-р_офи, 08-07-90704-моб_ст, в рамках российско-американской программы «Фундаментальные исследования и высшее образование» (CRDF Project RUX0-014-SA-06) и гранта Президента РФ по поддержке ведущих научных школ (НШ-3086.2008.9).