3. Корреляционные методы и алгоритмы распознавания.

Корреляционный метод широко используется в различных задачах распознавания образов. Рассмотрим конкретику и наработанные методики на реальных примерах.

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

Корреляционный метод при распознавании движения основан на нахождении смещения между двумя изображениями одного объекта. Смещение определяется по максимуму функции взаимной корреляции. В качестве опоры принимается характерные признаки объекта. Чтобы найти характерную особенность из первого изображения во втором, первое изображение g₁(t)=g₁ сравнивается со вторым g₂(t)=g₂ в пределах определенного диапазона поиска. Измерение схожести должно “пропускать” изменения в освещении. Т.е. мы считаем, что два образца одинаковы, если они отличаются на константу по яркости, которая отражает изменение освещения и частично по форме.

На языке скалярного произведения, это означает то, что g₁ и g₂ параллельны. Это возможно тогда и только тогда, когда будет равенство в неравенстве Коши-Шварца

Иными словами, требуется максимизировать коэффициент взаимной корреляции

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

Таким образом, коэффициент взаимной корреляции является функцией в 4-хмерном пространстве, зависящей от положения x и смещения s. Для ускорения данного процесса вначале осуществляют поиск позиции максимума. Разложим коэффициент корреляции в ряд Тейлора второго порядка в точке максимума

где H матрица Гессе.

Не зная положение максимума предположим, что вторые производные постоянны в достаточной близости к максимуму и вычисляем его в позиции предыдущей итерации s⁽ⁱ⁾. Если нет другой информации, то устанавливаем значение первой итерации в ноль s⁽⁰⁾=0. Пока не достигнуто максимальное значение коэффициента, будет присутствовать остаточный сдвиг. Его можно вычислить, если взять производную от

Учитывая, что матрица Гессе инвертируемая, получим следующую итерацию

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

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

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

Рис. 10.1. Пары выборок сигналов через постоянные интервалы времени

На рис. 10.1 приведены выбранные сигналы с большим масштабом по оси , чем на рис. 70. Благодаря увеличению отчетливо видны неоднородности в зонах фотоприемников с номерами 200...300. В финишные сигналы подлежащие корреляционному анализу нецелесообразно включать составляющие не изменяющиеся во время движения, к ним относится общий профиль сигнала. Введем интегрирование в скользящей зоне размером в 40 отсчетов. Результат обработки массива приведен на рисунке 10.2.

Рис. 10.1. Сдвинутые в пространстве сигналы

Рис. 10.2. Результат низкочастотной фильтрации одного из исходных сигналов

Рис. 10.3. Разностные сигналы

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

Рис. 10.4. Вид одного из сечений корреляционной функции

Рис. 10.5. Вид корреляционной функции с достоверной зоной наличия неоднородности

Рис. 10.6. Вид корреляционной функции при отсутствии неоднородности

Рассчитываем смещение полотна как положение максимума корреляционной функции для отобранных зон и по полученным данным распознаем факт движения стеклянного полотна (рис. 10.4). Внутри основной операции вложена задача распознавания наличия неоднородности на контролируемом участке и выбор зоны, в которой будет определено смещение. На рис. 10.5 виден локальный участок в котором можно достоверно определить смещение полотна. На рис. 10.6 такой участок отсутствует (для анализа взята пара с координатами 5200, 6000 рис. 10.2).

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

В рассматриваемой реализации база данных эталонных образов составляет 524288 вариантов 120 байтных описаний Изображение сегмента базы размером 152 образа приведено на рис. 10.8. На рабочем изображении формируется движущийся сегмент вырезающей маски (на рис. 10.7 его текущее положение отмечено маркой с координатами 50 по и 30 по ). Результаты компрессии и декомпрессии представлены на рис. 10.10. Исходные изображения приведены на рис. 10.9.

Коэффициент корреляции вычисляется после подготовки сегментов по формуле:

, где - описание - го образа, - описание рабочего сегмента.

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

Увеличено в 1,5 раза
Рис. 10.7. Маска	Рис. 10.8. Эталонны	Рис. 10.9. Исходное	Рис. 10.10. Результат

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

Рис. 10.11. Идентификатор рабочего сегмента

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

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

Качество изображений удовлетворительное, это видно из фрагментов пейзажа полученных в результате компрессии и декомпрессии (рис. 10.10).

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

• назначьте распознаваемые классы (обычно число классов равно числу распознаваемых типов символов + число типов служебных сообщений);

• сформируйте эталонные образы (каждый образ целесообразно представить 2...4 эталонами);

• сформируйте бегущий сегмент рабочего образа;

• пронормируйте данные рабочего сегмента;

• вычислите корреляционное соотношение между признаковым описанием рабочего и эталонных сегмента;

• задав рабочий уровень доверия dr, примите решение о принадлежности рассматриваемого сегмента к одному из классов;

• если уровень доверия не превышен определите тип служебного сообщения и соответствующего действия.

На рис. 10.12 приведен выбранный с общего изображения фрагмент текста и выбранные классы символов рис. 10.13. Каждый класс представлен пикселями по размеру сегмента. При работе над эталонным образом используют два алгоритма:

• эталонный образ формируется в полуавтоматическом режиме с ручной корректировкой описаний символов;

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

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

Ниже приведены рекомендуемые формулы расчета bn - нормированного массива признаков:

; где - новый промежуточный массив с устранением среднего, а - значение автокорреляционной функции, вычисленной с учетом диапазона задания описания пикселя. Учитывая неравенство Коши-Шварца выполните нормировку рабочего сегмента.

Рис. 10.12. Фрагмент текста	Рис. 10.13. Эталонные символы

Операции при нормировке рабочего сегмента рекомендуется проводить аналогично расчетам по эталонному образу.

; где r - рабочий движущийся сегмент.

Рис. 10.14. Метки найденных положений символа с	Рис. 10.15. Вид корреляционной функции на различных участках текста

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

.

На рис. 10.14 приведены результаты поиска символа “c” на изображении в виде изображения указателей. Реально близкие по форме символы так же дают значительную величину корреляционного отклика (рис. 10.15). Много вопросов вызывает масштабирование символов и их разворот. Все эти вопросы находятся в своем развитии, изменяя конкретику эталонных образов.

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

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

Поступили новые сведения , например, мнение очередного эксперта, или отсчет сигнала с оценкой неопределенности по среднеквадратичному отклонению . Будем считать и не коррелированными.

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

где - отношение среднеквадратичных отклонений. Вид графика приведен на рис. 10.16. Видно, что во всем реальном диапазоне изменения имеется в наличии оптимальное значение минимизирующее величину . Например при 3, 0,11 (рис. 10.17).

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

Рис. 10.16. Вид зависимости от и

Рис. 10.17. Экстремум среднеквадратичного отклонения при =3