Современные информационные технологии/1. Компьютерная инженерия

Казаков М.Г.

Алтайский государственный технический
университет им. И.И.Ползунова, Россия

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

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

Введем понятие визуального сходства классов для отображения связи между расстоянием в терминах семантического графа и визуальными отличиями между классами, представленного наборами изображений. Примеры изображений данных классов, полученных в результате работы поисковой системы, показаны на Рисунке 1. Изображения классов представлены в виде набора визуальных слов – Bag of Words [3], таким образом на первом этапе визуальные особенности всех изображений кластеризуюся [5], и конкретные визуальные особенности заменяются на порядковые номера ближайших визуальных слов (в примере ниже, исходя из малого количества классов, число различных визуальных слов было принято равным 100, как достаточное для выражения отличия между изображениями).

Рис. 1. Пример классов для вычисления визуального и семантического сходства

По аналогии с методом классификации Naive Bayesian Nearest Neighbor введем понятие визуального расстояния V(I, C) от отдельного изображения I до набора изображений C как L2 расстояние до ближайшего изображения в классе:

,

где d_i - нормированные гистограммы распределения k визуальных слов в соответствующих изображениях.

Примем расстояние D(C₁, C₂) от визуального класса С₁ до класса C₂ как сумму визуальных расстояний до этого класса от изображений, составляющих первый класс:

,

где n – количество изображений в классе C₁.

Стоит отметить, что из-за использования минимального значения расстояния между гистограммами, эта функция не будет симметрической в общем случае:

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

Полученный результат полностью соответствует интуитивному представлению об их взаимном расположении.

Таблица 1 - Визуальное расстояние между классами

	Кошка	Собака	Автомобиль	Автобус
Кошка	0.00	0.82	0.94	1.00
Собака	0.86	0.00	0.98	1.00
Автомобиль	1.00	0.99	0.00	0.87
Автобус	1.00	0.99	0.84	0.00

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

,

где E – функция сходства при переходе от одного понятия к другому – получается из словаря понятий, D – константный коэффициент демпфирования при каждом очередном удалении от изначального понятия. Таким образом, семантическое расстояние между классами представляется последовательным произведением мер близости понятий и коэффициента демпфирования:

,

где i, j – пары смежных понятий по кратчайшему пути от понятия, соответствующего классу C₁ до понятия, соответствующего классу C_2. Семантическая близость классов, рассчитанная данным способом, при коэффициенте демпфирования D=0.8, приведена в Таблице 2.

Таблица 2 - Семантическая близость классов

	Кошка	Собака	Автомобиль	Автобус
Кошка	1.00	0.56	0.45	0.31
Собака	0.56	1.00	0.42	0.31
Автомобиль	0.45	0.42	1.00	0.56
Автобус	0.31	0.31	0.56	1.00

Семантическая близость классов T находится в диапазоне [0,1], поэтому для изображения соотношения с визуальным расстоянием между классами, вводится следующее нормирование:

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

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

Таблица 3 - Соотношение визуального и семантического расстояния

	Кошка		Собака		Автомобиль		Автобус
Кошка	0.00	0.00	0.82	0.64	0.94	0.80	1.00	1.00
Собака	0.86	0.64	0.00	0.00	0.98	0.84	1.00	1.00
Автомобиль	1.00	0.80	0.99	0.84	0.00	0.00	0.87	0.64
Автобус	1.00	1.00	0.99	1.00	0.84	0.64	0.00	0.00

Литература:

1. Казаков М.Г., Крючкова Е.Н. «Адаптивность классификации изображений на основе автоматической генерации обучающей выборки» // материалы XI всероссийской научно-технической конференции студентов, аспирантов и молодых ученых “Наука и Молодежь”. – Барнаул, 2014. – С.15-18.

2. Казаков М.Г., Крючкова Е.Н. “Классификация сложных изображений на основе семантического графа понятий» // журнал “Прикладная информатика”. № 6(54). – 2014. – С.79-89.

3. Csurka, G., Dance, C., Fan, L., Willamowski, J., Bray, C. “Visual categorization with bags of keypoints” // Workshop on statistical learning in computer vision, 2004.

4. Fergus R., Fei-Fei L., Perona P., Zisserman, A. “Learning object categories from Google's image search” // Tenth IEEE International Conference on Computer Vision, V.2. - 2005. – p.1816-1823.

5. Lowe, D. G. “Object Recognition from Local Scale-Invariant Features” // The Proceedings of the Seventh IEEE International Conference on Computer Vision, 1999.

6. Szeliski, R. “Computer Vision: Algorithms and Applications”. - Springer-Verlang New York, 2010.