Распознавание образов для программистов

ВНИМАНИЕ! БЛОГ ПЕРЕЕХАЛ ПО АДРЕСУ
RECOG.RU

26 Сентябрь 2010

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

написано в рубрике: Распознавание образов — Кручинин Александр @ 3:08 ПП

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

В отдельных случаях наиболее правильным путём является игнорирование проблемы детектирования. Например, пользователь мобильного устройства делает фотографию двухмерного бар-кода с последующим распознаванием, при этом вероятно, что код содержит большую часть входного изображения. Или использование фильтра перевода в монохромное изображение позволяет отбросить ненужные элементы (Рис. 1).

r4_1 

r4_2 

 Рис. 1. Исходное изображение с DataMatrix кодом (а), переведённое в монохромное изображение с выделенным на ней кодом

 

Сегментация изображений обычно используется для выделения объектов. Однако при детектировании бинарных изображений обычные методы сегментации не подходят. На рисунке 2 показаны результаты использование двух методов сегментации, реализованных в библиотеке OpenCV: а) пирамидальный алгоритм; б) алгоритм водораздела. Оба примера не дают никакой существенной информации о наличии бинарных объектов на изображении.

r4_3 

 r4_4

 Рис. 2. Пирамидальная сегментация (а), сегментация методом водораздела (б)

 

Почитав алгоритм описанный здесь http://habrahabr.ru/blogs/algorithm/81279/, ну и оригинальную статью http://people.cs.uchicago.edu/~pff/papers/seg-ijcv.pdf, я было «воспрял духом», пока не скачал исходные коды алгоритма http://people.cs.uchicago.edu/~pff/segment/.

Перекомпилировав Visual Studio код, предварительно вставив функцию random, которой почему-то в проекте не оказалось, было обнаружено, что код работает только с ppm файлом. Кое-как найдя shareware конвертер, я попробовал протестировать алгоритм. Мало того, что алгоритм работал до ужаса медленно, что неприемлемо в системах распознавания образов реального времени, так и результаты меня не впечатлили. Результаты тестирования с различными параметрами показаны на рисунке 3.

 r4_5

 r4_6

 r4_7

  

Рис. 3. Результаты работы «эффективного алгоритма» с различными настройками

 

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

16 Сентябрь 2010

Алгоритм генерации временных рядов сигналов с заданными статистическими характеристиками на основе знаковой корреляции

написано в рубрике: Распознавание образов — Кручинин Александр @ 7:09 ПП

Материал из диссертации:

 

Кручинин Александр Юрьевич. Оптимизация режимов работы каротажных станций на основе анализа сложности идентификации состояния буровой скважины : диссертация  кандидата технических наук : 05.13.06 / Кручинин Александр Юрьевич; [Место защиты: Оренбург. гос. ун-т].- Оренбург, 2007.- 152 с.

 

Одним из основных вопросов задач технической диагностики является имитация сигналов с заданными статистическими характеристиками. Моделирование случайных процессов описано во многих работах, например, в работах [2,11,31,63,128]. Однако моделированию временных рядов с заданным линейным коэффициентом парной корреляции (K) уделено мало внимания. Основным требованием к синтезируемым рядам является обеспечение заданной степени близости по K. Необходимость в таких рядах возникает при решении задач распознавания образов. Цель данного параграфа – разработать алгоритм генерации временных рядов с заданным K лежащим в диапазоне от –1 до +1.

В задачах идентификации сигналов с использование корреляционного метода распознавания образов критерием, отличающим образы, является коэффициент парной корреляции K [31]:

r3.1              (3.2)

где Mx  и My – оценки математического ожидания для переменных x и y; Kxy – коэффициент ковариации; sx  и  sy – оценки среднего квадратичного отклонения; N – число элементов исследуемых рядов.

При моделировании первого временного ряда используется генератор случайных чисел (ГСЧ). Для языка C/C++ – это функция rand() из библиотеки stdlib.h. Второй ряд строится в том же диапазоне, что и первый. Алгоритм построения второго ряда состоит из четырех этапов.

1 этап: метод построения с использованием знаковой корреляции [27, 146]. В знаковой корреляции учитывается только знак сигнала. Для данной задачи используется знак приращения сигнала. Положительное приращение – знак плюс, отрицательное – знак минус. Коэффициент знаковой корреляции Фехнера рассчитывается по следующему выражению[27]:

r3.2,                                                     (3.3)

где Z – коэффициент знаковой корреляции, V – количество совпадений знаков, W – количество несовпадений знаков. Z изменяется в интервале от +1 до –1.

Количество совпадений знаков первого и второго рядов определяет Z. Интервалы, в которых происходит совпадения знаков, задаются ГСЧ. Первый элемент второго ряда выбирается ГСЧ. А последующие элементы генерируются из интервала, задаваемого предыдущим значением элемента и верхней или нижней границы диапазона. Верхняя граница используется при положительном приращении, нижняя граница – при отрицательном.

Устанавливая различные значения Z, можно сгенерировать второй ряд с разными значениями K. На рис. 3.1 представлен график, отображающий значения K сгенерированных рядов при задании параметра Z.

Значения K сгенерированного ряда при изменении значений Z от –1 до 1 меняется в интервале от –0,5 до 0,5, что без учета погрешности выражается:

r3.3.                                                    (3.4)

Этот метод подходит для получения ряда с K в интервале от –0,5 до 0,5. Для получения ряда с K, попадающим в интервалы от –1 до –0,5 и от 0,5 до 1, необходимо перейти на 2 этап. Если требуемое значение K лежало в интервале от –0,5 до 0,5, то перейти к 3 этапу.

 

Рис. 3.1 – Значения K сгенерированных рядов от заданного Z

Рис. 3.1 – Значения K сгенерированных рядов от заданного Z

  

2 этап: использование линейного коэффициента. Для генерирования ряда с K, лежащим в пределах значений от –1 до –0,5 и от 0,5 до 1, вводится линейный коэффициент K0:

r3_,                                                   (3.5)

где Z равно 1 для интервала от 0,5 до 1, и Z равно –1 для интервала от –1 до –0,5.

K0 характеризует ширину интервала, из которого ГСЧ выбирает значения. K0 изменяется от 0 до 1. Значение первого элемента второго ряда выбирает ГСЧ. Последующие элементы генерируются из интервала, определяемого значением K0. При K0 равном 0 ширина интервала максимальная – такая же, как на первом этапе, при этом K равно 0,5 или K равно –0,5. При изменении значений K0 от 0 к 1, интервал генерации сужается. А при значении K0 равном 1 – выбирается значение без использования ГСЧ. Это значения элемента второго ряда получается прибавлением приращения из первого ряда между соответствующими элементами к предыдущему значению элементов второго ряда. При K0 равном 1, получается второй ряд, у которого с первым рядом K равно 1 или –1.

3 этап: проверка полученных рядов на случайность. Критериев случайности ряда существует довольно много [22, 31, 52]: пиковый критерий, критерий, основанный на ранговой корреляции, спектральный критерий и др. В данной работе для определения случайности ряда выбран критерий, основанный на ранговой корреляции [22, 31].

Коэффициент ранговой корреляции Спирмена [22]:

r3.5                                    (3.6)

где r – коэффициент ранговой корреляции, n – общее количество элементов ряда, j – порядковый номер элемента ряда, а Xj – ранг, т.е. номер в упорядоченной по возрастанию цепочке элементов временного ряда. Признаком случайности является близость r к нулю. Величину этой близости определяет критическая точка [31]:

r3.6,                                                  (3.7)

где tкр – критическая точка двусторонней критической области Стьюдента, которую находят по таблице критических точек распределения Стьюдента, по уровню значимости и числу степеней свободы [31]. Если |r| меньше Tкр – нет оснований отвергнуть гипотезу о случайности временного ряда.

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

4 этап: выбор рядов с заданным K. Генерация рядов на 1 этапе имеет погрешность:

r3.7.                                           (3.8)

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

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

Для изменения значения M сгенерированного ряда происходит прибавление всех значений ряда на одну заданную величину m:

r3.8,                                               (3.9)

где Mзад – заданное, которое необходимо получить, значение математического ожидания, а Mсг – значение математического ожидания сгенерированного на первых двух этапах ряда.

Для изменения значения D сгенерированного ряда происходит умножение всех значений отклонений ряда на заданную величину d:

r3.9r3.10,                                      (3.10)

r3.11,                                (3.11)

,                                            (3.12)

где D(X)зад – заданное значение дисперсии ряда, D(X) – значение дисперсии сгенерированного ряда.

Разработанный метод моделирования двух временных рядов с заданным K позволяет получать ряды со значением K, лежащим на всем диапазоне от –1 до +1. Данный метод применим в задачах распознавания образов, например для генерации случайных сигналов, отличающихся друг от друга по K. Для разработанного алгоритма написана программа на языке C++ (см. приложение 1). Данный алгоритм использовался при моделировании сигналов для исследования модели системы многофакторной динамической оптимизации режимов регистрации и идентификации буровой скважины.

 

Программу, выполняющую этот алгоритм, можно скачать здесь http://vidikon.com/download/kpk.zip .

 

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

1-ый сигнал генерируется случайным образом и записывается в data\signal_1.dat

Сигналы с заданным коэффициентом парной корреляции записываются в data\1\

В data\kpk.dat записывается информация в 4 столбца для каждого сигнала из data\1\

1 столбец: коэффициент для получения КПК, 2 столбец: математическое ожидание, 3 столбец: дисперсия 4 столбец: полученный КПК.

Работает на WordPress