Поиск оптимального положения при сравнении оцифрованных образов

В статье описывается задача сравнения оцифрованных (отсканированных) образов.

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

Введение

Во многих алгоритмах распознавания производится сравнение двух бинарных образов с помощью некоторой функции близости, чтобы понять, являются ли они образами двух «одинаковых» объектов. Функция близости выбирается так, чтобы удовлетворять требованиям алгоритма распознавания и учитывать особенности образов, получаемых из заданного источника.

Мы рассматриваем пространство образов U, представленных в виде матриц R=||r_ij|| одинакового размера 0 ≤ i ≤ m, 0 ≤ j ≤ n. Размеры реального образа существенно меньше размеров матрицы mn. Размещение образа с размерами m₁n₁ (m₁<m, n₁<n) в матрице с размерами mn назовем центрированием. Если реальный образ представлен матрицей m₁n₁, то можно, например, центрировать этот образ так, чтобы центры матриц m₁n₁ и mn совпадали. Можно придумать и применять другие способы центрирования, для нас важно, что способ центрирования един для всех образов.

При кластеризации образов и их распознавании используется неотрицательная функция близости d, которая сравнивает два образа A=||a_ij|| и B=||b_ij||, AU, BU. Условно мы будем называть образ A эталонным, а B — тестируемым. При получении образов с помощью цифровых устройств (сканеры, фото- и видеокамеры) возникает ряд эффектов оцифровки. Простейший из этих эффектов состоит в том, что из одного прообраза могут получаться образы, различающиеся как между собой, так и с прообразом. Это объясняется случайностью совмещения прообраза и цифровой сетки (например, сетки сканера) и иллюстрируется рисунком 1, в котором показано как из одного исходного прообраза (серой полосы) получаются два различных оцифрованных бинарных образа (черные полосы).

Рисунок 1 – Примеры оцифровки образа при различном наложении на сетку сканера
(серые полосы – прообразы, черные – бинарные образы)

К функции близости d, используемой в кластеризации и распознавании, предъявляются два требования:

• аксиома тождества — d(A, B) = 0 A=B;
• аксиома симметрии — d(A, B) = d(B,A) A,B.

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

.

При сравнении образов A и B из пространства U будем производить всевозможные сдвиги образа A=||a_ij|| в разных направлениях и рассматривать функцию близости между получившимся образом и B. Определим сдвиг матрицы A на величину (h,w) как



Другими словами, A(h,w) получается из A в результате переноса на вектор (h,w) на торе, являющимся замыканием области прямоугольника с размерами mn (см. рисунок 2)

Рисунок 2 – Примеры переноса образа символа «m» на различные векторы на торе

Теперь мы можем определить «расстояние» d₀ между образами A и B.

    (1)

Матрицу, A(h,w) на которой достигается минимум, мы будем называть оптимальным положением образа A относительно B, а вектор (h,w) — оптимальным сдвигом.

Существуют различные способы определения d₀(A,B) и оптимального сдвига (h,w).
Один из простейших – вычислять функцию близости d(h,w)=(A(h,w),B)), ограничив значения h и w: h ≤ n₀, w ≤ n₀.

Вообще говоря, наименьшее значение n₀, гарантирующее достижения реального минимума d(h,w), заранее неизвестно, верхняя граница n₀ определяется величиной сдвига, при котором образы A и B не пересекаются, то есть a_ij b_ij = 0 i и j. Для таких n₀ способ определения d₀(h,w) является точным. При значениях n₀, которые не гарантируют достижения реального минимума d(h,w), способ определения оптимального положения является приближенным и позволяет вычислять d₀(A,B) с некоторой погрешностью.

Мы полагаем, однако, что исходное положение образа A, которое выбирается обычно отнюдь не случайно, не должно быть слишком далеко от оптимального. Чуть точнее, если наугад взятое положение удачно, т.е. если несовпадение эталонного и тестируемого изображений (A,B), составляет малую часть эталонного изображения, то параллельный перенос (h,w), максимизирующий совпадение изображений, мал (т.е. по длине составляет малую часть диаметра эталонного изображения).

Собственно, именно этот эффект и является обоснованием для ограничения рассматриваемых векторов (h,w).
Ясно, что чем меньше n₀, тем меньше времени будет занимать вычисление d = min_h,w d(h,w), но хотелось бы иметь какие-то оценки влияния сдвига при сравнении двух образов и, тем самым, оценки близости положения некоторого образа к оптимальному.Получению таких оценок посвящена настоящая работа.

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

1. Исследование влияния сдвигов при сравнении образов

1.1. Описание задачи

Ниже приводится математическая модель, объясняющая приведенный выше эффект на качественном уровне. При этом мы существенно расширим исходные постановки. В модели изображение рассматривается как пара, состоящая из множества I (ненулевые точки изображения), и плотности φ:I → R (распределение весов точек изображения). Степень совпадения изображения с плотностями φ₁ и φ₂ моделируется интегралом .

Пусть – пространство с мерой dσ и X – множество пар x=(I,σ), где I — измеримое подмножество и φ:I → R интегрируемая неотрицательная функция, называемая плотностью. На множестве X определена метрика , где

Пусть γ: → взаимнооднозначное отображение, сохраняющее меру, т.е. γ*dσ = dσ. Отображение γ индуцирует изометрию , переводящую точку x=(I,φ) в точку . По подмножеству и числу определим подмножество YX, состоящее из точек (I,φ) таких, что:

1. I
2. 

Задача 1. Для функциинайти (наилучшую) оценку снизу.

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

Расширим множество X и определим множество , состоящее из пар , в которых плотность φ может концентрироваться в точках. Точнее, в множестве в качестве плотностей рассматриваются обобщенные плотности φ, являющиеся суммами интегрируемых функций и конечных линейных комбинаций δ-функций в точках q (мы будем обозначать их символом δ_q), т.е. . На пространство автоматически переносятся определения расстояния, отображения и функции ε, которые мы будем обозначать, соответственно, , и . Пусть даны отображение γ: →, подмножество и число . Пусть подмножество , состоит из точек , где , таких, что:

1. I,
2. φ ≥ 0, ≥ 0, носитель функции φ лежит в I и q_kI,
3. ;

Задача 1'. Для функции найти (наилучшую) оценку снизу.

1.2. Частичное решение задачи 1

Справедлива следующая теорема.

Теорема 1. Если для некоторого целого n множество γⁿ() не пересекается с множеством , то .

Доказательство. С точкой yY свяжем последовательность y₀, y₁, …, y_n точек в X, определенных соотношениями

Пусть y=(I,φ). Поскольку yY, то .

Поэтому
.

Так как отображение является изометрией, то для любого k имеем .

По аксиоме треугольника т.е. . Что и требовалось доказать.

Покажем, что при выполнении некоторых дополнительных условий оцен¬ку из теоремы 1 нельзя улучшить. Главное из них — следующее условие.

Условие : Существует точка q, такая, что точки q, γ(q), … γⁿ(q) различны и все они, за исключением точки γⁿ(q), лежат в множестве .

Предположим дополнительно, что множество снабжено топологией, в которой множество открыто и отображение γ непрерывно.

Теорема 2. Пусть выполнены перечисленные выше условия и . Тогда .

Доказательство. Выберем точку q, удовлетворяющую условию , и возьмем ее окрестность E положительной меры, столь малую, что для каждого k=0, 1, …, n окрестности γⁿ(E) не пересекаются друг с другом и все они, за исключением окрестности γⁿ(q), лежат в множестве . Пусть φ₀ – неотрицательная функция на , носитель которой лежит в области E, такая, что .

Пусть x=(I,φ) точка из , определенная следующими соотношениями:



Тогда

.

Имеем

.

Легко видеть, что

.

Поэтому ε ≤ 2a/n. По теореме 1 ε ≥ 2a/n. Теорема 2 доказана.

Частичное решение задачи 1'. Теорема 1 дословно обобщается на случай задачи 1'. Мы не будем останавливаться на формулировке и доказательстве этого обобщения. Теорема 2 для случая задачи 1' допускает усиление: не нужно дополнительно требовать, чтобы множество было снабжено топологией, в которой множество открыто и отображение γ непрерывно.

Теорема 2'. Пусть выполнено условие и . Тогда .

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

1.3. Случай евклидова пространства

Пусть пространство с мерой dσ – это пространство Rⁿ с евклидовой мерой, отображение γ – это сдвиг на фиксированный вектор aRⁿ (т.е. γ(x)=x+а), а множество это любое n-мерное выпуклое подмножество в Rⁿ. Рассмотрим совокупность неотрицательных интегрируемых функций φ в Rⁿ, тождественно равных нулю вне выпуклого множества и удовлетворяющих соотношению:



Задача 1 для евклидова пространства. Найти (наилучшую) оценку снизу функции ε(, , a), заданной формулой:



Задача 1' в рассматриваемом случае формулируется аналогично.

Вектор aRⁿ мы будем записывать в виде a=|a|ν, где ν – вектор единичной длины и |a| – длина вектора a. Для вектора ν единичной длины назовем ν-диаметром d_v() выпуклой фигуры точную верхнюю грань множества длин отрезков, являющихся сечениями области прямыми, параллельными вектору ν. Для ненулевого вектора a=|a|ν назовем a-диаметром d_a() выпуклой фигуры отношение d_v()/|a| ее ν-диаметра к длине |a| вектора a.
Приведем решение задач 1 и 1' для вектора a=|a|ν в случае, когда a-диаметр фигуры не является натуральным числом.

Теорема 3. Если для некоторого целого n ≥ 0 справедливы неравенства n|a| < d_v()<(n+1)|a, то ε=2/(n+1).

Доказательство. В условиях теоремы 3 имеем . Поэтому согласно теореме 1 выполняется неравенство ε ≥ 2/(n+1). Так как точная верхняя грань длин сечений области прямыми, параллельными вектору ν, больше числа n|a|, то существует точка y, лежащая строго внутри области , такая, что все точки y,y+a, …, y+na лежат строго внутри . По теореме 2 имеем ε ≤ 2/(n+1), откуда и вытекает теорема 3.

Приведем решение задачи 1' для вектора a=|a|ν в случае, когда a-диаметр фигуры является натуральным числом.

Теорема 4. Если для некоторого целого n ≥ 0 справедливо равенство n|a| < d_v(), тo .

Доказательство теоремы 4 аналогично доказательству теоремы 3. Если выполняется равенство n|a| < d_v(), то минимум в задаче не достигается на обычных функциях. Однако минимум достигается на линейной комбинации δ-функций, и он равен 2/(n+1).

1.4. Следствия найденных оценок

Формула для функции ε(, , a), достаточно громоздка. В следствии 1 приводится неточная, но достаточно хорошая оценка этой функции, которая вполне обозрима. В следствии 2 приводится оценка этой функции, которая для фиксированного вектора ν при малых значениях длины |a| линейна по длине |a|, т.е. равна λ|a| с явно выписанной константой λ.

Следствие 1. Справедлива оценка



Эта оценка точна при |a|=d_v(), d_v()/2, d_v()/3, … и при |a|→∞ (т.е., образно говоря, точна при |a|= d_v()/0).

Если ε(, , a)<2, то это неравенство можно переписать в виде:



Следствие 2. Для любого y₀ ≥ 0 при 0 ≤ |a| ≤ y₀ имеем



при |a| ≥ y₀ имеем



В частности, для y0 = d_v() получаем следующее: при 0 ≤ |a| ≤ d_v() имеем



при |a| > d_v() имеем ε(, , a) ≥ (отметим, что на самом деле, при |a| > d_v() справедливо равенство ε(, , a))=2).

Доказательство. Следствие 1 автоматически вытекает из теорем 3 и 4. Следствие 2 вытекает из следствия 1.

1.5. Качественное объяснение рассматриваемого эффекта

Пусть φ(x) неотрицательная интегрируемая функция на Rⁿ, равная нулю вне выпуклого множества . Пусть



Пусть g(x) другая неотрицательная интегрируемая функция на Rⁿ. Пусть

    (2)

Допустим, что интеграл значительно меньше, чем .

Задача 2. Меняя параметр aRⁿ, добиться, чтобы интеграл

принял возможно меньшее значение.

Наша цель – показать, что если >>, то для минимизации числа ψ(a) интересны лишь малые по длине вектора a=|a|ν, которые значительно короче, чем ν-диаметр d_v() области .

Определим функцию ε(a) как

, где минимум берется по всем неотрицательным функциям φ, удовлетворяющим соотношению (2) и имеющим носитель в области .
Мы можем применять найденные выше оценки функции ε(a).

Теорема 5. Зафиксируем вектор ν единичной длины. Пусть d(ν) — минимальное число, такое, что для вектора a=|a|ν, при |a| > d(ν) выполнено неравенство ε(a) > 2.
Тогда при |a| > d(ν) справедливо неравенство

.
В частности, для минимизации ψ(a) достаточно рассматривать лишь векторы a=|a|ν, для которых |a |< d(ν).

Доказательство. Вытекает из аксиомы треугольника. Действительно, имеем


Откуда при |a|>d(ν)

, что и требовалось доказать.

Следствие 3. Для минимизации интеграла ψ(a) на прямой a=|a|ν, натянутой на вектор ν, достаточно рассматривать лишь векторы a, для которых выполнено неравенство

    (3)

При справедливо неравенство

.

Доказательство. Вытекает из теоремы 5 и следствия 1.

Следствие 3 доставляет качественное объяснение обсуждаемого эффекта. Действительно, если >>, то число / (-) мало. Поэтому минимум ψ(a) достигается при длине вектора a, значительно меньшей, чем диаметр d_v() фигуры в направлении вектора ν. Тем самым доказано, что для достижения «оптимального» положения двух фигур достаточно малых сдвигов в том случае, когда мера несовпадения при малых сдвигах незначительна.

2. Эксперименты

2.1. Исходные объекты, параметры и алгоритмы

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

Итак, исходный материал – тестовое множество, состоящее из 1770 образов букв русского языка. Рассматриваются различные пары знаков, всего 1770 (1770–1)/2=1565565 пар.

Мы будем использовать для установки начального (нулевого) положения двух изображений A₁ и A₂ относительно друг друга некоторый алгоритм AL₁. Значение функции близости, основанной на метрике Хэмминга, в этом положении будем обозначать (A₁,A₂). Кроме того, мы будем рассматривать оптимизационный алгоритм AL₀. Этот алгоритм перебирает различные параллельные переносы одного из изображений на всевозможные вектора (h,w) относительно начального положения и выбирает тот, при котором метрика Хэмминга принимает минимальное значение. Это (оптимальное) значение мы будем обозначать через d₀(A₁,A₂) а оптимизирующий вектор (h,w) через a(A₁,A₂)=|a|ν, где ν — единичный вектор направления. Обычно мы будем рассматривать величину n(A₁,A₂) = [a(A₁,A₂)], характеризующую расстояние между нулевым и оптимальным положением в пикселях.

Количество ненулевых пикселей изображения A будем обозначать . Как показано в предыдущем разделе, важную роль играет отношение /. При этом, поскольку во всех случаях, когда речь идет о паре изображений A₁ и A₂, величины /₁ и /₂ выступают симметрично, мы будем рассматривать величину t(A₁,A₂)=min(/₁,/₂).

Это, в частности, «симметризует» формулы п. 1.5, относящиеся к функциям φ(x) и g(x).
Это же избавляет нас от необходимости рассматривать большие значения /, так как всегда t ≤ 2. Соответствующую величину в оптимальном положении будем обозначать t₀:

t₀(A₁,A₂) = min(d₀/₁, d₀/₂).

Отметим, наконец, что в статистических таблицах, а также там, где это не ведет к путанице, мы будем опускать аргументы A₁ и A₂ и писать просто , d₀, t, t₀, n.

2.2. Общие характеристики

Среди рассматриваемых 1770 образов символов русского алфавита некоторые являются одноименными (например, буквами "в"). Ясно, что многие характеристики для таких пар могут сильно отличаться от соответствующих характеристик «разноименных» пар. Поэтому иногда мы будем рассматривать статистики по таким парам отдельно.

В тех случаях, когда в графике по одной из осей откладывается количество пар, обладающих каким-то свойством, максимальные значения могут быть велики, но для нас важно видеть и малые значения. В таких случаях мы будем пользоваться логарифмическим масштабом: n → log₂(n+1).

Обратимся к статистике. Прежде всего, покажем общее распределение количества пар по различным значениям t₀ и t. На рисунке 3 дана гистограмма зависимости n(t₀) и n(t) для всех пар символов.

a)

б)

Рисунок 3 – Общее количество пар в зависимости от а) t₀, б) t

Добавим, что среднее значение t₀ для всех пар равно 0,6, среднее значение t равно 0,66.

Рассмотрим на рисунке 4 аналогичную гистограмму для одноименных пар.

a)

б)

Рисунок 4 – Количество пар одноименных символов в зависимости от а) t₀, б) t

Здесь среднее значение t₀ для всех пар равно 0,17, среднее значение t равно 0,23.

В среднем алгоритм AL₁ — дает значения не очень далекие от оптимальных. Для одноименных пар, в правой части графика значения n(t) гораздо менее круто спадают к нулю, чем n(t₀). Это означает, что большие значения t отнюдь не всегда указывают на то, что соответствующее оптимальное значение t₀ велико. Однако для небольших значений t₀ и t оба графика ведут себя примерно одинаково.

Заметим, что, как с точки зрения применения теоремы 5, так и в контексте распознавания пары с большим t₀ (например, t₀>0,5) мало интересуют нас, поэтому для них качество алгоритма AL₁ и поиск оптимального сдвига не слишком важны.

Дополнительно рассмотрим на рисунке 5 гистограмму количества пар в зависимости от величины t₀/t.

Рисунок 5 – Зависимость n(t₀/t)

Как мы видим, более 15% всех рассмотренных пар получают при использовании алгоритма AL₁ значение, отличающиеся от наилучшего из возможных (идеального) не более чем на 1%, а затем их число монотонно уменьшается вместе с t₀/t.

Таким образом, можно считать, что статистики сдвигов, полученные при сравнении положения, определенного алгоритмом AL₁ с оптимальным положением (алгоритм AL₀) будут достаточно представительными.

2.3. Анализ отклонений начального положения от идеального

Рассмотрим отклонение от идеального положения в зависимости от t более детально. На рисунке 6 приведено количество пар n_i, отклоняющихся при нулевом положении от идеального положения на i=0, 1, 2, 3, 4 и i > 4, как функцию от t.

Рисунок 6 – Количество пар n_i(t) отклоняющихся от идеального положения на i пикселей, как функция t (n₅(t) – количество пар при i > 4)

Из графика видно, что для t < 0,13 все пары символов расположены идеально, но уже при t > 0,22 количество пар, требующих сдвига на 1 пиксель, превышает количество расположенных идеально. И только при t > 0,3 появляются пары, требующие сдвига на 2 пикселя.

Отклонение в пикселях / t	0	1	2	3
0,0 – 0,12	4344	0	0	0
0,12 – 0,31	32158	34271	0	0
0,31 – 0,38	42	8809	38	0
0,38 – 0,49	0	3328	522	0
0,49 – 0,66	0	241	463	0
0,66 – 0,85	0	0	31	7

Таблица 1 – Распределение количеств одноименных пар с различными отклонениями начального положения от идеального

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

В ней дано количество пар, в которых отклонение начального положения от идеального равно i=0, 1, 2 и i > 2 для одноименных символов. Мы видим, что даже здесь имеется не уж мало случаев, когда начальное положение далеко не идеально, но все они относятся к достаточно большим значениям t.

До сих пор мы использовали для сравнения с идеалом конкретный алгоритм AL₁. Теперь рассмотрим, как работает в нашем эксперименте теория «в чистом виде». Именно, каждую пару символов сдвинем относительно идеального положения по всем направлениям сначала на 1 пиксель, затем на 2, 3 и 4 и в каждом случае рассмотрим минимальное отклонение по всем направлениям. Таким образом, мы увидим, каково минимальное значение / при отклонении от идеала на величину |а| (|а| = 1, 2, 3 и более четырех пикселей) по всем 1565565 имеющимся парам символов. Кроме того, для каждого |а| вычислим минимальное значение S_v по формуле (3).

При |а|=1 для t₀ > 0,12 всегда находится пара, для которой сдвиг на один пиксель в каком-либо направлении не меняет значения t. Как ни странно, для других значений |а| такие примеры также находятся, но лишь при t₀>0,5, выходящих за пределы теоретических оценок (напомним предположение следствия 3:<<). Результаты эксперимента приведены в таблице 2.

|а|	min /	min Sv
1	0,12	2,32
2	0,28	5,81
3	0,44	8,94
4	0,51	11,18

Таблица 2 – Минимальные значения β/α и S_v при отклонении от оптимального положения на 1, 2, 3, 4 и более пикселей

Данные таблицы 2 хорошо подтверждают основанной теоретический вывод. Получив значение t < 0,28 можно уверенно утверждать, что оптимальное положение находится не более чем в двух пикселях. И даже при t=0,43 (расстояние приблизительно равное половине площади символа) взаимное положение отличается от идеального не более чем на три пикселя.

В то же время видно, что теоретическая оценка |а| < S_v является слабой. Величина S_v всюду в несколько раз превышает реальный сдвиг от оптимального положения

Выводы

Мы рассматривали сравнение бинарных растровых изображений, приняв в качестве меры близости – Хэммингово расстояние между ними. Было доказано, что если достаточно мало, то параллельный перенос a=(h,v) одного из объектов, минимизирующий значение , также не может быть большим. Получена конструктивная оценка S_v для |а|.

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

Полный текст статьи опубликован в «Арлазаров В.Л., Славин О.А., Фарсобина В.В., Хованский А.Г. Поиск оптимального положения при сравнении оцифрованных образов символов // Искусственный интеллект и принятие решений, Т.3. М.: Полипринт Сервис, 2013. С. 48-59»

Литература

1. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2005. – С. 176. ISBN 5-7036-0108-8.
2. Арлазаров В.Л., Котович Н.В., Славин О.А. Адаптивное распознавание // Информационные технологии и вычислительные системы. – 2002, № 4. – С. 11-22. ISSN: 2071-8632.
3. Арлазаров В.Л., Славин О.А., Хованский А.Г. Оценка расстояния между изображениями при параллельном переносе // Доклады академии наук. – 2011, Т. 437, № 3. – С. 313-315. ISSN: 0869-5652