2.1.6 Основные виды признаков изображения
Результат работы детектора это множество из особых точек, для которых требуется построить математическое описание. В настоящем разделе делается обзор некоторых существующих дескрипторов [13].
Дескриптор принимает на вход в качестве данных изображение а так же набор из особых точек, которые должны быть выделены на заданном входном изображении. В качестве выхода для дескриптора становится множество из векторов признаков для исходного набора из особых точек. Так же следует отметить, что некоторые дескрипторы осуществляют решение одновременно двух задач таких как – поиск особых точек, а также построение описателей для найденных особых точек [19].
Построение признаков (описателей) будет осуществляться на основании полученной информации об интенсивности, о цвете, а также о текстуре особой точки. Так же особые точки могут представляться как углами, ребрами или даже контуром объекта, поэтому, обычно, вычисления выполняются только для некой окрестности. В идеальном варианте хорошие признаки должны обладать такими свойствами как [16]:
Повторяемость. Если данные изображениях с одного и того же объекта или сцены, которые, в свою очередь, могут быть сделаны с различных точек зрения и при разной освещенности, наибольшее количество признаков должно быть продетектировано.
Локальность. Для снижения вероятности перекрытий все признаки должны быть максимально локальными.
Репрезентативность. Численность признаков должна быть достаточна, для того чтобы наиболее разумное число признаков детектировалось даже в случае небольшого изображения объекта.
Точность. Признаки должны быть наиболее точно продетектированными по отношению к масштабу и форме объекта.
Эффективность. Для приложений реального времени критично, если процедуры вычисления признаков будут требовать значительных вычислительных затрат. Поэтому требуется оптимизировать сеть в пользу их уменьшения.
2.1.7 Методы извлечения точечных признаков
2.1.7.1 Метод SIFT
Для формирования дескриптора SIFT (Scale Invariant Feature Transform) [4, 16] изначально вычисляют значения магнитуды и ориентации градиента в каждом пикселе, который принадлежит окрестности особой точки размером пикселей. При этом магнитуды градиентов учитываются с весами, пропорционально значению функции плотности нормального распределения с математическим ожиданием в рассматриваемой особой точке и стандартным отклонением, равным половине ширины окрестности (веса Гауссова распределения используются для того, чтобы уменьшить влияние на итоговый дескриптор градиентов, вычисленных в пикселях, находящихся дальше от особой точки).
В каждом квадрате размером пикселя вычисляется гистограмма ориентированных градиентов путем добавления взвешенного значения магнитуды градиента к одному из 8 бинов гистограммы. Чтобы уменьшить различные «граничные» эффекты, связанные с отнесением похожих градиентов к разным квадратам (что может возникнуть вследствие небольшого сдвига расположения особой точки) используют билинейную интерполяцию: значение магнитуды каждого градиента добавляется не только в гистограмму, соответствующую квадрату, к которому данный пиксель относится, но и к гистограммам, соответствующим соседним квадратам. При этом значение магнитуды добавляется с весом, пропорциональным расстоянию от пикселя, в котором вычислен данный градиент, до центра соответствующего квадрата. Все вычисленные гистограммы объединяются в один вектор, размером, равным 64(число бинов) 128(число квадратов)[19].
Полученный дескриптор следует преобразовать, что уменьшит возможные эффекты при изменении освещенности. Изменение контраста изображения (значение интенсивности каждого пикселя умножается на некоторую константу) приводит к такому же изменению в значениях магнитуд градиентов. Поэтому очевидно, что данный эффект может быть нивелирован путем нормализации дескриптора таким образом, чтобы его длина стала равна единице. Изменения яркости изображения (к значению интенсивности каждого пикселя прибавляется некоторая константа) на значения магнитуд градиентов не влияют. Таким образом, SIFT-дескриптор инвариантен по отношению к аффинным изменениям освещенности. Тем не менее возможно возникновение нелинейных изменений в освещенности вследствие, например, различной ориентации источника света по отношению к поверхностям трехмерного объекта. Данные эффекты могут вызвать большое изменение в отношении магнитуд некоторых градиентов (при этом оказывают незначительное влияние на ориентацию вектора градиента). Для того что бы этого избежать, используют отсечение по некоторому порогу (результаты экспериментов показывают, что наиболее оптимальным является значение 0.2), которое применяется к компонентам нормализованного дескриптора. После применения порога дескриптор вновь нормализуется. Таким образом, значение больших магнитуд градиентов уменьшается и значение распределения ориентаций данных градиентов в окрестности особой точки увеличивается.
2.1.7.2 Метод SURF
Отличие вышеописанных методов от метода Surf заключается в следующем: метод использует точечные особенности изображения, а не все имеющиеся точки (метод гистограмм и усреднённых цветов).
Алгоритм SURF решает такие задачи как: поиск особых точек изображения и создание их дескрипторов, инвариантных к масштабу и вращению. Это означает, что описание ключевой точки не поменяется, даже при изменении размера образца или его повороте. Кроме того, сам поиск ключевых точек так же должен обладать инвариантностью. Так, чтобы повернутый объект сцены имел тот же набор ключевых точек, что и образец.
Метод осуществляет поиск особых точек с помощью матрицы Гессе. Детерминант матрицы Гессе (т.н. гессиан) достигает экстремума в точках максимального изменения градиента яркости. Он хорошо детектирует пятна, углы и края линий.
Гессиан инвариантен относительно вращения. Но так он не инвариантен к масштабу. Из-за чего SURF для нахождения гессианов использует разномасштабные фильтры.
Для каждой ключевой точки подсчитывается направление максимального изменения яркости (градиент) и масштаб, взятый из масштабного коэффициента матрицы Гессе.
Градиент в точке вычисляют при помощи фильтров Хаара.
После нахождения ключевых точек, SURF формирует их дескрипторы. Дескриптор — это набор из 64 (или 128) чисел для каждой ключевой точки. Эти числа отображают флуктуации градиента вокруг ключевой точки (определение флуктуации будет приведено далее). Поскольку ключевая точка представляет собой максимум гессиана, то это гарантирует, что в окрестности точки должны быть участки с разными градиентами. Таким образом, обеспечивается дисперсия (различие) дескрипторов для разных ключевых точек.
Флуктуации градиента окрестностей ключевой точки считаются относительно направления градиента вокруг точки в целом (по всей окрестности ключевой точки). Таким образом, достигается инвариантность дескриптора относительно вращения. Размер же области, на которой считается дескриптор, определяется масштабом матрицы Гессе, что обеспечивает инвариантность относительно масштаба.
Флуктуации градиента можно рассчитать при помощи фильтра Хаара.
Во многих задачах обработки изображений требуется рассчитать яркость прямоугольного участка изображения. Как пример, фильтры Хаара, SURF и многие другие алгоритмы. Суммарную яркость произвольного прямоугольника позволяет быстро рассчитывать интегральное представление, причем время расчета не зависит от площади прямоугольника.
Интегральное представление изображения — это матрица, размерность которой совпадает с размерностью исходного изображения.
Каждый элемент матрицы представляет собой сумму пикселей в прямоугольнике от до . Расчёт матрицы занимает линейное время, пропорциональное числу пикселей в изображении.
У интегрального представления имеется интересная особенность. При помощи интегральной матрицы можно достаточно быстро вычислять сумму яркости пикселей произвольного прямоугольника и произвольной площади.
Пример
Пусть ABCD — интересующий нас прямоугольник:
Исходя из (рисунок 1) можно понять, что сумму внутри прямоугольни-ка возможно выразить через суммы и разности смежных прямоугольников по следующей формуле:
Все компоненты нужные для вычисления хранятся в интегральной матрице, вычисление занимает четыре обращения к массиву и три арифметических действия.
Обнаружение особых точек в SURF основывается на вычислении детерминанта матрицы Гессе (гессиана).
Матрица Гессе для двумерной функции и ее детерминант определяется следующим образом:
Значение гессиана используют при поиске локального минимума или максимума яркости изображения. В данных точках значение гессиана достигает экстремума.
Теоретически, вычисление матрицы Гессе сводится к нахождению Лапласиана Гауссиан. По сути, элементы матрицы Гессе вычисляются как свертка (сумма произведений) пикселей изображения на фильтры (Рисунок 2).
На рисунке 3 изображены дискретизированные фильтры которые используются для нахождения четырех элементов матрицы Гессе (поскольку матрица Гессе симметрична то четвертый – совпадает с третьим). Фильтры имеют пространственный масштаб 9×9 пикселей. Темные участки соответствуют отрицательным значениям фильтра, светлые – положительным.
Однако SURF не использует лапласиан гауссианы в том виде, который изображен на рисунке. Во-первых, по утверждению авторов, дискретизированный лапласиан гауссианы имеет довольно большой разброс значения детерминанта, при вращении образца. А во-вторых, и это главное, фильтр для лапласиана гауссианы имеет непрерывный характер. Почти все пиксели фильтра имеют разные величины яркости. А это не позволяет эффективно использовать такой мощный механизм расчёта, как интегральную матрицу изображения.
На рисунке 3 изображены фильтры, используемые для нахождения матрицы Гессе в SURF. Белые области соответствуют значению +1, черные -2 (на третьем фильтре -1), серые – нулевые. Пространственный масштаб – 9×9 пикселов.
Этот фильтр более устойчив к вращению, и его можно эффективно вычислить с помощью интегральной матрицы.
Таким образом, в SURF, гессиан вычисляется так:
Для нахождения особых точек, SURF пробегается по пикселям изображения и ищет максимум гессиана. Способ нахождения локального максимума гессиана будет рассмотрен позднее. В методе задается пороговое значение гессиана. Если вычисленное значение для пикселя выше порога – пиксель рассматривается как кандидат на ключевую точку.
Исходя из перечисленного, октава содержит не один фильтр, а четыре фильтра, которые хорошо покрывают характерный масштаб октавы (Рисунок 4).
На рисунке 4 показаны первые три октавы метода SURF. Цифры в прямоугольниках показывают размер фильтра Fast-Hessian. Логарифмическая шкала снизу – показывает масштабы, покрываемые октавами.
Октавы значительно перекрываются друг другом. Это увеличивает надежность нахождения локальных максимумов. Почему в октаве именно четыре фильтра станет ясно из следующей главы.
Для нахождения локального максимума гессиана, используется так называемый метод соседних точек 3x3x3. Его смысл понятен из рисунка 5.
Пиксель, помеченный крестиком, считается локальным максимумом, если его гессиан больше чем у любого его соседа в его масштабе, а также больше любого из соседей масштабом меньше и масштабом больше (всего 26 соседей).
Итак, после нахождения максимального гессиана методом соседних точек 3x3x3, были найдены пиксели, в котором этот максимум достигается. Однако, поскольку, октава перебирает не все точки изображения, то истинный максимум может не совпадать с найденным пикселем, а лежать где-то рядом, в соседних пикселях.
Для вычисления градиента, используется фильтр Хаара. Размер фильтра берется равным 4*s , где s – масштаб особой точки.
Фильтры Хаара создают точечное значение для перепада яркости по оси и соответственно. И поскольку фильтры Хаара обладают прямоугольной формой и их значения легко можно рассчитать при помощи интегральной матрицы. Для того чтобы произвести расчет одного фильтра произвольного размера требуется всего лишь 6 операций.
Исходя из алгоритма, значения фильтров Хаара для каждой точки перемножаются с весом и затем они сохраняются в массив. Вес определяем как значение гауссианы имеющей центр в особой точке и сигмой равной 2s. Взвешивание на гауссиану необходимо для отсечения случайных помех на далеких от особой точки расстояниях.
Далее, все найденные значения , условно наносятся в виде точек на плоскость (Рисунок 7).
После условного нанесения точек на плоскость (Рисунок 9) берется угловое окно (показано серым на рисунке) размером , и вращается вокруг центра координат. Выбирается такое положение окна, при котором длина суммарного вектора для попавших в окно точек – максимальна. Вычисленный таким образом вектор нормируется и принимается как приоритетное направление в области особой точки.
Манипуляции с окном нужны для уменьшения влияния шумовых точек. На рисунке 8 приведен пример градиента при идеальном крае, и при крае с шумом.
Из рисунка 8 следует, что в направлениях, не совпадающих с направлением основного градиента шум дает дополнительные градиенты. Для отсечения шумовых точек следует использовать окно и более точно вычислить истинный градиент.
Дескриптор считается как описание градиента для 16 квадрантов вокруг особой точки.
Далее, квадрат разбивается на 16 более маленьких квадрантов, как видно на рисунке. А в каждом квадранте берется регулярная сетка 5×5 и для точки сетки,с помощью фильтра Хаара, ищется градиент. Размер фильтра Хаара принимается равным и для первой октавы составляет 4×4.
После нахождения 25 точечных градиента квадранта, вычисляются четыре величины, которые собственно и являются компонентами дескриптора:
Две из них есть просто суммарный градиент по квадранту, а две других – сумма модулей точечных градиентов.
На Рисунке 12 показано поведение дескриптора на разных изображениях. Где для равномерных областей – все значения близятся к нулю. Для повторяющихся вертикальных полосок – все величины, кроме второй близки к нулю. При увеличении яркости в направлении оси X, две первые компоненты имеют большие значения.
2.2 Способы представления изображения
2.2.1 Общие положения
В настоящее время, несмотря на то, что различного рода изображения все чаще используются для представления и обработки входной, промежуточной и выходной информации во многих прикладных задачах распознавания образов, слабо развиты средства выбора алгоритма обработки изображения в зависимости от его синтаксического и семантического содержания[18]. Наибольшее количество алгоритмов для распознавания изображений, которые обладают вычислительной эффективностью, предназначаются для работы с признаковыми описаниями или моделями изображений. При построении такого описания существенная часть информации, содержащейся в изображении, теряется. Для того, чтобы максимально использовать при анализе изображений содержащуюся в них информацию, необходимо разработать эффективные методы описания изображений и построения моделей изображений. Для решения фундаментальной задачи построения эффективных формальных описаний изображений необходимо провести классификацию и сравнительный анализ средств, позволяющих адекватно описывать изображения и представлять всю информацию, содержащуюся в изображении и необходимую для решения поставленных задач. Решение этой задачи открывает широкие перспективы повышения эффективности выбора алгоритмов анализа изображений и автоматизации (частичной либо полной) обработки изображений.
Моделью изображения называется представление его и/или его характеристик в виде некоторой специальной формальной конструкции, удобной для дальнейшей обработки, распознавания. Для построения модели изображения используются различные математические объекты, в том числе признаки и дескрипторы изображений, логические функции, графы, последовательности преобразований изображений и др. Наиболее часто используются числовые признаки. Числовым признаком изображения называется переменная, представляющая числовую характеристику свойств изображения, например, геометрических, яркостных, структурных или пространственных. Формальным описанием изображения с помощью числовых признаков называется набор математических объектов (например, чисел, векторов, матриц), содержащих некоторую информацию об изображении, представленную в форме числа и/или набора чисел, и допускаемых алгоритмом распознавания, используемым для решения задачи. Следует отметить, что формальное описание изображения может содержать как полную информацию об изображении (такую, по которой можно восстановить исходное изображение), так и частичную (в случае, когда информации недостаточно для восстановления исходного изображения из его описания).
Свойства признака изображения определяются как свойствами изображения, так и способом извлечения признаков изображения. Признак модели является параметром модели изображения, поэтому тип допустимого пространства признаков, разброс значений признака и методы сравнения значений признаков существенным образом зависят от выбранной модели изображения, в то же время типы алгоритмов распознавания связаны с используемыми типами признаков, поскольку признаки составляют входную информацию алгоритмов распознавания. Отсюда следует, что допустимость применяемых методов распознавания изображений напрямую связана с построенной моделью изображения.
Необходимо отметить, что элементами модели изображения могут быть не только признаки, но и непроизводные элементы, отношения между ними, процедуры и проч.
2.2.2 Низкоуровневое представление
В рамках увеличивающегося объема мультимедиа коллекций особое внимание исследователей направлено на алгоритмы поиска изображений по содержанию (Content Based Image Retrieval, CBIR), которые могут полностью автоматизировать процесс создания индекса. В рамках отсутствия каких-либо других данных об изображении для создания индекса применяются низкоуровневые характеристики исходного изображения: яркость, цвет, текстура. За последние несколько лет предлагалось огромное количество разнообразных моделей описания подобных характеристик, функций расстояния и определенных с их помощью оценок схожести изображений. Но качество работы систем нахождения изображений по содержанию все же нельзя называть удовлетворительным. Человек, выбирая изображения, сравнивает их семантику, смысловую оценку схожести изображений на базе низкоуровневых характеристик. Главным направлением проводимых в этой области работ становится создание алгоритмов, необходимых для уменьшения «семантического разрыва» между данными анализа изображений системой и восприятием самого пользователя.
Проблемам индексирования и поиска изображений по содержанию отведено большое количество работ, что может говорить о высокой активности исследователей в данной области.
Системы поиска изображений по содержанию применяют разнообразные алгоритмы обработки цифрового сигнала для построения сигнатур — представлений изображения в рамках конкретного набора параметров. Почти во всех предлагаемых подходах одна сигнатура может описать одну из характеристик изображения (цвет, текстура, и т.п.). Т.е. одному и тому же изображению может соответствовать сразу несколько сигнатур, которые описывают каждую из характеристик.
В процессе поиска в рамках запроса зачастую выступает изображение-образец. Итогом такого поиска становится комбинация изображений, близких к изображению-запросу по впечатлениям человека. Различные системы позволяют пользователю создать эскиз того изображения, которое он желает найти. Но оба этих подхода заставляют пользователя как-то конкретизировать свой запрос на языке, понимаемом системой, но не удобном для пользователя. Применение изображения образца для запроса обязывает пользователя иметь такой образец, что часто просто невозможно. Разработка эскиза нужного изображения заставляет пользователя формулировать запрос на языке форм и цвета. А ведь пользователю всегда удобнее составлять свой запрос на естественном языке, указывая на словах то, что он хочет найти на требуемом изображении. Но сейчас нет системы, позволяющей сгенерировать индекс автоматически в рамках содержания изображения и умеющей понимать запрос на естественном языке.
Большинство исследователей различают сразу несколько уровней содержания изображений. Цвет и яркость принадлежит к низкоуровневому содержанию, находящиеся физические объекты (машина, человек, дом) — к содержанию высокого уровня, а текстура часто принадлежит к среднему уровню. В литературе можно найти огромное количество подходов к моделированию низкоуровневых характеристик изображения и почти все CBIR построены на алгоритмах обработки низкоуровневого содержания. Вот уже несколько лет исследователи понимают нехватку алгоритмов. Важно принять во внимание особенности визуального восприятия человека, его ориентированность на семантику.
Популярным подходом, призванным минимизировать разрыв между представлением изображения системой и человеком становится система обратной связи (relevance feedback). Базирующиеся на итеративном процессе поиска, подобные системы накапливают статистику по реакции пользователя, которая затем может быть учитываться при формировании ответа системы. Примером практической использования подобной системы будет комплекс, созданный в лаборатории CLIPS. Вопросам интерфейса уделяется особое внимание в данной работе, для построения грамотного и полноценного диалога с пользователем.
В работе [1] предоставлен ряд экспериментов, которые показывают возможности использования слов английского языка в качестве основы индекса изображений. Такой индекс может хорошо согласовываться с семантикой изображения.
2.2.3 Контурное представление
Контурными признаками называют такие признаки, вычисление которых производится на контуре (замкнутом или незамкнутом). Следует отметить, что вычисление контурных признаков происходит в два этапа: 1) выделение пикселов, принадлежащих контуру объекта па изображении; и 2) вычисление собственно признака с использованием выделенных пикселов контура. Как правило, выделяемый контур является бинарным изображением, что существенно уменьшает время работы алгоритмов. Контурные признаки часто используются в задачах распознавания машинописного и рукописного текстов. В [14] для каждого распознаваемого символа выделяются внешний и внутренний контуры, на них вычисляются: признаки, полученные с помощью операции разделения на зоны, коэффициенты сплайна, аппроксимирующего контур, и коэффициенты Фурье для описания эллиптических замкнутых контуров и функции от них[17].
В качестве добавочного признака для распознавания рукописных цифр используется расстояние (по вертикали и по горизонтали) между точками контура цифры и точками выпуклой фигуры, описанной вокруг цифры. В для аппроксимации контуров объектов при распознавании лиц используются коэффициенты, описывающие кривые: коэффициенты прямой — для аппроксимации линии щеки, параболы — для аппроксимации линии подбородка и губ. В [7] контуры объектов используются для вычисления характеристик Эйлера, отражающих топологию описываемого объекта па изображении.
Контурные признаки также часто используются при анализе и классификации изображений отпечатков пальцев [15, 19]. В связи со спецификой таких изображений, на них выделяются контуры яркостных переходов, характеризующие собственно отпечаток, а затем вычисляются признаки полученных контурных изображений.
2.2.4 Структурное представление
Данный класс содержит модели, представленные символически, или структурные описания. Последние представляют собой структуру данных: набор утверждений, аргументы которых соответствуют частям объекта или сцены (непроизводным элементам) и предикаты которых соответствуют свойствам частей и пространственным взаимоотношениям между ними. Часто структурное описание представляется в виде графа, вершины которого соответствуют частям объекта (или сцепы) и их свойствам, а ребра, связывающие вершины, соответствуют пространственным отношениям.
К сожалению, сегодня науки, связанные с изучением информационных процессов головного мозга человека, восприятия и переработки зрительной информации живыми организмами, не располагают необходимыми данными для создания алгоритма распознавания, успешно моделирующего процессы зрительного восприятия. Поэтому алгоритмы распознавания изображений необходимо основывать на некоторых формальных описаниях.
2.2.5 Признаковое представление
Обозреваемая модель представляет из себя как описание геометрических особенностей изображения с использованием вектора признаков, которые характеризуются особенностями входного изображения. Признаками изображения могут быть как вертикальные, так и горизонтальные линии, кривые или соединения вида «Т», «Y» и др. Были разработаны специализированные методы для выделения каждого отдельного признака во входящем изображении вне зависимости от его расположения. После того как все методы будут применены создается вектор признаков, значениями которого являются величины, которые характеризуют как часто встречается каждый признак на исходном изображении. Дальше в памяти сохраняется список всех возможных признаков, поиск которых ведется на изображении, и вектор признаков, соответствующий исходному изображению. Каждому признаку можно поставить в соответствие некоторый вес с тем, чтобы признаки, инвариантные относительно функций преобразования изображения, оказывали существенное влияние на сопоставление моделей изображений.
При прохождении процесса сопоставления получающийся вектор признаков сравнивается с векторами, что сохраняются в памяти в, с учетом весов, приписанных каждому признаку. Определить меру близости можно с помощью различных способов, например, количество совпадающих признаков, квадратичная разность между элементами векторов и др. Модель, самая ближайшая к исходной модели в смысле заданной меры близости, ставится ей в соответствие.