Аннотирование изображений из исторического цифрового альбома с помощью текстур методом моментов

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

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

• 3.    Классификация коллекции изображений, в результате которой каждому изображению будет соответствовать набор меток.

В данной работе рассматриваются методы аннотирования на основе текстурных характеристик. Анализ методов аннотирования проводился на коллекции фотографий строительства Беломорско-Балтийского канала и альбома Бродаца [2], [3], [4].

В [10] были определены текстурные характеристики, соответствующие человеческому восприятию: грубость, контраст, направленность, линейность, непрерывность и шероховатость. Множество текстурных признаков было предложено в [6]. В [9] рассматривались специальные гистограммы для классификации текстур, в [5],

• [11 ] – текстурный анализ на основе моментов. В [11] был предложен метод сегментации текстур на основе моментов и описан соответствующий математический аппарат. В [7] использовались инвариантные моменты для распознавания символов.

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

ОБЩАЯ СХЕМА АННОТИРОВАНИЯ

В данном исследовании рассматривается процесс аннотирования с учетом наличия текстур, который в общем случае включает в себя следующие шаги:

• 1.    Задается набор текстур, каждая из которых принадлежит одному из нескольких заданных классов.

• 2.    Каждому классу присваивается набор меток.

• 3.    Для каждого изображения выполняется поиск текстур из заданного набора.

• 4.    Для каждой найденной текстуры к изображению добавляется набор меток соответствующего класса.

Для выполнения текстурного поиска требуется классификатор. Мы предлагаем классификатор на основе метода моментов.

МЕТОД МОМЕНТОВ

В [11] был предложен метод сегментирования текстур на основе моментов и описан соответствующий математический аппарат. Рассмотрим прямоугольное изображение шириной W и высотой H. Пусть f (x, y) – значение изображения в точке (x, y) , нормализованное на отрезке [0; 1]. Метод моментов заключается в том, что для каждой точки изображения f (x, y) рассчитывается набор моментов и производных от них характеристик в пределах некоторого окна с центром в данной точке. Таким образом формируется набор изображений, соответствующих набору признаков.

Момент M_{p, q} с центром в точке ( i, j ) и размером окна W_M рассчитывается следующим образом:

^M p , q ⁽ i , ^j ) ⁼ S ^{f (a , Ь} ) ' x^P ' У ?- ,

(a, b )eWM где              _ a - i _ b - j xa _ WMT2’ y w/2,

W _ij ^M – окно размером W_M с центром в точке ( i, j ).

В [11] утверждалось, что набор моментов в чистом виде не годится для сегментирования, поэтому автором был предложен улучшенный набор признаков:

^F P , q ⁽ i , ^j )^_ 1 2 ^ ^lanK| ^ ^{( M} P , q ( a , ^Ь )^{- M} p,q )) ¹ . ⁽³⁾

^W F ( a,b) e W^F

F_{p, q} ( i, j ) – значение характеристики момента порядка (p, q) в точке ( , j ), где

^M P , q ⁽i ’ ^{j )_} 1 2 S ^M P , q ⁽ a , ^{b )} ,     ⁽⁴⁾

W F ( a , b) e W F

M Pp^q ( i , j ) – усредненное изображение момента M_{p , q} , W_ij^F – окно размером W_F с центром в точке ( i, j ).

Степени моментов p и q задаются таким образом, чтобы их сумма не превышала некоторого значения T_o , то есть p +q ≤ T_o . Тогда общее количество изображений моментов и характеристик моментов будет равно ^(T o ⁺ ^(T ^{+ 2)} . В данной работе 2

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

Другими параметрами для расчета характеристик являются размеры окон W_M и W_F и коэффициент σ . Авторами этого метода [11] были протестированы значения данных параметров: 9, 49 и 0,01 соответственно. Указанные значения были получены методом проб и ошибок, поэтому в нашей работе был проведен анализ влияния значений параметров W_M , W_F и σ на результат сегментации.

Для экспериментов использовался алгоритм сегментации, являющийся модификацией алгоритма, предложенного в [11] (пример результатов работы исходного алгоритма сегментации представлен на рис. 1):

• 1.    Тестовое изображение «склеивается» из нескольких текстур (см. рис. 1). Каждая текстура представлена квадратным участком. Площади участков текстур одинаковы.

• 2.    Рассчитываются характеристики, представляющие собой N изображений, где N – число характеристик.

• 3.    Случайно отбираются 6 % точек, равномерно распределенных по изображению.

• 4.    Для выбранных точек производится кластеризация методом к-средних. Число кластеров соответствует числу текстур. Авторская версия данного алгоритма предполагала использование алгоритма кластеризации CLUSTER [8].

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

• 6.    Определим точность сегментации ρ как долю правильно сегментированных пикселей. Поскольку алгоритм к-средних произвольно определяет начальные центры кластеров, к нему добавляется промежуточный шаг, на котором определяется соответствие номеру текстуры и номеру кластера. Будем считать, что кластер с номером i будет соответствовать текстуре j , если большая часть пикселей класса i будет располагаться внутри участка текстуры j .

Рис. 1. Пример сегментации составного изображения с помощью метода, предложенного в [11] (взято из [11]): (а) – составное изображение; (б) – результат сегментации составного изображения

В нашем исследовании используемый алгоритм сегментации отличается от алгоритма, предложенного в [11], выбранным алгоритмом кластеризации. Пример сегментации изображения (рис. 2а), «склеенного» из 2 текстур, выполненной по описанному выше модифицированному алгоритму, представлен на рис. 2б. Точность сегментации составила 95,3 %.

Анализ результатов сегментации заключается в сравнении значений точности для определенного набора параметров { W_M , W_F , σ }. Были выбраны следующие диапазоны значений параметров: [9;

Рис. 2. Изображения, «склеенные» из 2 текстур альбома Бродаца [4]: а) исходное; б) результат бинарной сегментации

• 49] с шагом 5 для W_M и W_F , [0,005; 0,02] с шагом 0,005 для σ . Анализ осуществлялся над изображением на рис. 2а.

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

Результаты анализа влияния параметров на точность сегментации

w WM	W F	σ	σ (%)
9	49	0,01	95,285
9	39	0,005	95,1782
9	39	0,02	95,1752
14	14	0,02	93,8416
14	14	0,005	93,7103
14	29	0,015	92,395
14	34	0,02	92,3248
24	24	0,02	87,9639
39	19	0,01	87,9639

Таким образом, экспериментально показана правильность значений параметров, предложенных в [11].

КЛАССИФИКАТОР НА ОСНОВЕ МЕТОДА МОМЕНТОВ

Для поиска текстур предлагается следующий классификатор:

• 1.    Для каждой текстуры из обучающей выборки рассчитывается центральный вектор (центр текстуры) как средний вектор среди векторов признаков всех пикселей данной текстуры.

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

• 3.    Для каждого изображения вычисляются изображения характеристик моментов F_{p, q} . Значения изображений характеристик моментов в точке (i, j) определяют вектор признаков следующим образом: { F p , q ( i , j ) I p + q ^ T o } . Порядок расположения значений признаков внутри вектора фиксируется, напри-

• мер, при То = 2 вектор признаков равен

• 5.    Точки полученной карты текстур объединяются в сегменты, которые состоят из соседних точек с одинаковым номером текстуры. Точки со значением –1 в сегменты не объединяются.

• 6.    Для каждого сегмента определяется его размер, равный количеству пикселей. Если размер сегмента равен или превышает некоторое пороговое значение, считается, что соответствующая текстура найдена на текущем изображении. В данной работе использовалось пороговое значение размера сегмента 100.

{ F 0,0 , F 0,1 , F 1,0 , F 0,2 , F 1,1 , F 2,0 }.

Для каждого изображения вычисляется карта текстур. Размер карты равен размеру изображения. Значением карты для данной точки

является номер первой соответствующей данной точке текстуры. Если данной точке не соответствует ни одна из текстур, точка карты принимает значение –1.

ОЦЕНКА КАЧЕСТВА РАБОТЫ КЛАССИФИКАТОРА

Для эксперимента было отобрано 100 изображений из коллекции фотографий строительства Беломорско-Балтийского канала. Для поиска использовались текстуры T ₁ и T ₂, представленные на рис. 3.

Рис. 3. Пример текстур, добавленных в классификатор. Изображения, использованные в эксперименте по текстурному поиску: 34 – крыша дома ( T ₁), 35 – стена дома ( T ₂)

Эксперимент заключается в выявлении вхождения каждой текстуры T_j в каждое изображение I_i . С помощью эксперта вручную отмечаются

Г 1, Tj найдено в Ii вхождения текстур Ej = i . С дру-[0, иначе гой стороны, с помощью классификатора автоматически определяются вхождения каждой текстуры Fij (аналогично Eij), после чего определяется флаг релевантности текстуры Rij (1 – текстура Tj найдена на изображении Ii и при этом обнаружена экспертом), который рассчитывается как Rij = Eij • Fij. Тогда полнота Rej и точность Rrj поиска текстуры Tj рассчитываются следующим образом [1]:

_Re . I R _Pr _1Л ' "I E/ '"I F

.

Аналогично можно рассчитать общую полноту Re и точность Rr поиска:

1 R ,     1 , R

Re "   — , Pr "

¹ _k ' E y       ¹ ,, j F

.

На рис. 4 представлены основные результаты эксперимента.

Крыша дома        Стена дома          Общее

Рис. 4. Результаты поиска текстур

ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ КЛАССИФИКАТОРА

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

Реализованный метод текстурного поиска использует набор параметров: {WM = 49, WF = 9, σ = 0,01}. Классификатор в своей работе требует наличия базы данных «помеченных» изображений текстур. При этом для каждой текстуры в соответствии с алгоритмом классификации необходимо определить пороговое значение ε. В разработанных инструментах данное значение может задаваться вручную пользователем или рассчитываться автоматически путем подбора на основе обучения. Для этого пользователю требуется выделить на нескольких изображениях участки, соответствующие искомой текстуре. Основным целевым фактором в процессе подбора параметров является суммарная ошибка, которая вычисляется как доля неправильно классифицированных пикселей среди всех пикселей помеченных пользователем изображений.

Реализованная в системе база данных текстур представляет собой множество «помеченных» классов текстур. При добавлении новой текстуры от пользователя требуется только указать изображение, параметр ε и выбрать класс, к которому изображение принадлежит. Текстовые метки относятся непосредственно к классам текстур. Для работы необходимо иметь возможность составлять различные наборы текстур для классификатора, поэтому в системе классификаторы реализованы как списки текстурных классов, которые пользователь должен определить перед началом работы. Благодаря использованию промежуточных связей с текстурами через классы, формирование альтернативных классификаторов не требует добавления уже существующих текстур. При этом классификатор точно привязывается к набору текстур. На рис. 3 представлен пример текстур классификатора. Алгоритм поиска при обнаружении соответствия какой-либо текстуре, включенной в классификатор, приписывает изображению те метки, которые относятся к классу данной текстуры.

ЗАКЛЮЧЕНИЕ

В результате исследования на основе метода сегментации, предложенного в [11], был разработан собственный классификатор, позволяющий выполнять поиск текстур на изображениях по обучающей выборке. Однако на данный момент основные показатели качества являются недостаточно высокими, что требует дополнительных исследований этого метода. С другой стороны, предлагаемый алгоритм поиска учитывает особенности вычислений моментов изображений, и его временная сложность составляет O (W ∙ H ∙ logWH) вместо O (W ∙ H ∙ M ² ), что позволяет обрабатывать большие изображения за сравнительно небольшое время. При этом объем классификатора не оказывает существенного влияния на время вычисления, поскольку при больших размерах изображения большая часть времени тратится на вычисление моментов изображения.

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

HISTORICAL IMAGE ANNOTATION WITH TEXTURES BASED ON MOMENTS