Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,749

A STUDY OF THE ALGORITHM OF IDENTIFICATION OF REAL FLAT OBJECTS BASED ON DIMENSIONLESS MARKS OF THEIR CONTOURS

Sadykov S.S. 1 Kulkov Y.Y.. 1
1 The Murom institute of Vladimir State University
Article is devoted to a study of possibility of application dimensionless marks of a bitmap image contour of real object for its recognition. The purpose of work is the experimental study of possibility of application of dimensionless marks for recognition of objects in machine sight systems. The image arriving from the video sensor been binary. The single-point contour of a bitmap is calculated. On the received contour the perimeter and metric length, quantity of points of various curvature are calculated. On the basis of primary coefficients the vector of marks is formed. Are formed the set of etalons for each group of images consisting of vectors of dimensionless marks. With use of a mean square deviation degree of similarity of a vector of marks of the unknown image and vectors of marks of etalons is calculated. The minimum indicates belonging of the tested image to one of the set groups. Results of experiments on identification of objects, and also dependence of time of recognition on quantity of the used standards are given.
recognition
identification
flat object
dimensionless marks
contour
1. Andrianov D.E. Razrabotka municipalnyh geoinformacionnyh sistem / D.E. Andrianov, S.S. Sadykov, R.A. Simakov. M.: Mir, 2006, 109 p.
2. Zhiznjakov A.L. Teoreticheskie osnovy obrabotki mnogomasshtabnyh posledovatelnostej cifrovyh izobrazhenij: monografija / A.L. Zhiznjakov, S.S. Sadykov. Vladimir: Izd-vo VlGU, 2008, 121 p.
3. Issledovanie markernogo vodorazdela dlja vydelenija oblasti raka molochnoj zhelezy/S.S. Sadykov, Ju.A. Bulanova, E.A. Zaharova, V.S. Jashkov//Algoritmy, metody i sistemy obrabotki dannyh. 2013. no. 1 (23). рр. 56–64.
4. Kriterii vydelenija grupp riska iz lic trudosposobnogo vozrasta pri medicinskih issledovanijah na sisteme ASPO / O.I. Evstigneeva, S.S. Sadykov, E.E. Suslova, A.S. Beljakova // Algoritmy, metody i sistemy obrabotki dannyh. 2012. no 19. рр. 33–39.
5. Sadykov S.S. Avtomaticheskaja obektivnaja ocenka i vybor naibolee znachimyh parametrov dlja diagnostiki serdechno-sosudistyh zabolevanij / S.S. Sadykov, I.A. Safiulova, A.S. Beljakova // Avtomatizacija i sovremennye tehnologii. 2012. no. 3. рр. 27–33.
6. Sadykov, S.S. Algoritm teksturnoj segmentacii dlja vyjavlenija oblastej kisty na mammogrammah / S.S. Sadykov, Ju.A. Bulanova, A.G. Romanov // Algoritmy, metody i sistemy obrabotki dannyh. 2013. no. 1 (23). рр. 50–55.
7. Sadykov S.S. Dialogovaja sistema analiza mammograficheskih snimkov / S.S. Sadykov, Ju.A. Bulanova, E.A. Zaharova // Algoritmy, metody i sistemy obrabotki dannyh. 2012. no. 19. рр. 155–167.
8. Sadykov S.S. Identifikacija realnyh ploskih obektov na osnove edinstvennogo priznaka tochek ih vneshnih konturov / S.S. Sadykov, S.V. Savicheva // Informacionnye tehnologii. 2011. no. 8. рр. 13–16.
9. Sadykov S.S. Issledovanie nalozhennosti ploskih ob#ektov v pole zrenija sistemy tehnicheskogo zrenija / S.S. Sadykov, S.V. Savicheva // Izvestija vysshih uchebnyh zavedenij. Priborostroenie. 2012. Vol. 55. no. 2. рр. 14–18.
10. Sadykov S.S. Matematicheskie modeli nekotoryh serdechno-sosudistyh zabolevanij/S.S. Sadykov, A.S. Beljakova // Informacionnye tehnologii. 2011. no. 12. рр. 59–63.
11. Sadykov S.S. Raspoznavanie ploskih obektov pri ih nalozhenii / S.S. Sadykov, S.V. Savicheva // Informacionnye tehnologii. 2013. no. 2. рр. 43–46.
12. Sadykov S.S. Sistema formirovanija dannyh ob informacionnyh resursah kraevedcheskogo muzeja i upravlenija imi: opyt razrabotki i ispolzovanija / S.S. Sadykov, E.E. Kanunova // Informacionnye tehnologii. 2007. no. 10. рр. 59–65.
13. Sadykov S.S. Tehnologija vydelenija oblasti kisty na mammogramme / S.S. Sadykov, E.A. Zaharova, Ju.A. Bulanova // Vestnik Rjazanskogo gosudarstvennogo radiotehnicheskogo universiteta. 2013. no. 1 (43). рр. 7–12.
14. Sadykov S.S. Formirovanie bezrazmernyh kojefficientov formy zamknutogo diskretnogo kontura / S.S. Sadykov // Algoritmy, metody i sistemy obrabotki dannyh. 2014. no.4 (29). рр. 91–98.

В статье приведены результаты экспериментальных исследований по распознаванию отдельных реальных плоских объектов (ОРПО) с использованием безразмерных признаков, полученных из характеристик контуров бинарных изображений этих объектов, разработанных в [14].

Распознавание объектов по их изображениям – традиционная область цифровой обработки изображений. Распознавание имеет своей целью отнесение объекта к одному из заранее предопределенных типов. Для решения данной задачи необходимо получение определенных признаков объекта по его изображению, которые позволят идентифицировать его с минимальной ошибкой. Для установления связи между значениями признаков объекта и решения о принадлежности его к определенному классу необходимо использование обучающей совокупности известных объектов [1–13].

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

На рис. 1 приведены 10 исходных изображений ОРПО.

Эксперимент проводится на презентабельной выборке изображений каждого из 10 ОРПО. Для этого проводится генерация множества повернутых изображений.

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

Для каждого из сгенерированных изображений вычисляются центры тяжести.

Для вращения изображения на угол α используется алгоритм, приведенный в [7].

pic_52.tif

pic_53.tif

pic_54.tif

pic_55.tif

pic_56.tif

Объект 1

Объект 2

Объект 3

Объект 4

Объект 5

pic_57.tif

pic_58.tif

pic_59.tif

pic_60.tif

pic_61.tif

Объект 6

Объект 7

Объект 8

Объект 9

Объект 10

Рис. 1. Тестовые изображения

Формируется массив повернутых изображений каждого из 10 ОРПО с шагом в 1 градус. Всего 3600 изображений.

Далее реализуется имитация случайного появления объекта в поле зрения распознающей системы. С помощью генераторов случайных чисел (ГСЧ) с нормальным распределением из повернутых 360 изображений каждого из 10 ОРПО формируется 10 массивов по 2000 изображений.

С помощью второго ГСЧ получаем числа в диапазоне 0,364 до 0,720. Такое ограничение необходимо для того, чтобы свести к минимуму расположения изображений вне рабочего поля). Для 2000 реализаций каждого объекта генерируются 4000 чисел. Первое число от ГСЧ будем считать координатой центра тяжести по оси икс Хц объекта, второе число – Yц. Таким образом определяются координаты центра тяжести каждой из 2000 реализаций каждого из 10 ОРПО. Согласно этим координатам 2000 реализаций каждого из 10 ОРПО размещаются на рабочем поле.

Выполняется бинаризация полутоновых изображений с использованием алгоритма сегментации Отсу.

По полученным изображениям рассчитывается количество точек в каждой из 2000 реализаций каждого из 10 ОРПО, то есть вычисляет площадь объекта S0. Формируются одноточечные контуры бинарных изображений объектов по алгоритму в [3].

Рассчитывается количество точек P0, образующих контур каждой из 2000 реализаций каждого из 10 ОРПО. Определяется метрическая длина Lконт контура каждой из 2000 реализаций каждого из 10 ОРПО.

Определяется значение кривизны в точках каждого контура каждой из 2000 реализаций каждого из 10 ОРПО, а также маркируются опорные точки выпуклых и вогнутых участков контура по алгоритму в [8].

По полученным изображениям вычисляется количество опорных точек выпуклых, вогнутых и линейных участков контуров:

М1 – количество точек контура со значением +90;

М2 – количество точек контура со значением –90;

М3 – количество точек контура со значением +135;

М4 – количество точек контура со значением –135;

К – количество 4-х связных точек контура;

Т – количество D связных точек контура.

По формулам (1), (2) и (3) вычисляем общую длину выпуклых, вогнутых и линейных участков всего контура каждого объекта:

Lобщ.вып = 1/2[М12b + М3(а + b)]; (1)

Lобщ.вог = 1/2[М22b + М4(а + b)]; (2)

Lобщ.лин = 1/2(К2а + T2b), (3)

где a – расстояние между 4 связными точками; b – расстояние между D связными точками.

По полученным осуществляем расчет векторов безразмерных признаков каждой из 2000 реализаций всех 10 ОРПО.

К1 = Po/S0; (4)

К2 = М1/S0; (5)

К3 = М2/S0; (6)

К4 = М3/S0; (7)

К5 = М4/S0; (8)

К6 = К/S0; (9)

К7 = Т/S0; (10)

К8 = М1/P0; (11)

К9 = М2/P0; (12)

К10 = М3/P0; (13)

К11 = М4/P0; (14)

К12 = К/P0; (15)

К13 = S0/P0; (16)

К14 = Lобщ.лин/Lконт; (17)

К15 = Lобщ.вог/Lконт; (18)

К16 = Lобщ.вып/Lконт. (19)

Далее в диалоговом режиме осуществляется выбор эталонов для распознавания каждой из 2000 реализаций каждого из 10 ОРПО. По гистограмме, полученной на этапе генерации, выбирается вектор признаков самой часто использованной из 360 повернутых вариантов, например 1-го ОРПО, при формировании 2000 реализаций. Для данного вектора коэффициентов по методу среднеквадратичного отклонения (20) вычисляется Zi с каждой из 2000 реализаций.

sadykhov01.wmf (20)

где n – число признаков; l – номер распознаваемого объекта (l = 1, 2, …, 2000); Кej – значение j-го признака вектора коэффициентов К выбранного эталона; Кlj – значение j-го признака вектора коэффициентов К выбранной реализации.

Вычисляются 2000 СКО Zi. Среди них ищутся Zmin:

Zmin = min{Zi}. (21)

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

На втором шаге на основе гистограммы выбирается как эталон вектор-признак следующей часто использованной из 360 повернутых вариантов, например 1-го ОРПО, при формировании 2000 реализаций. Вычисляются 2000 СКО Zi. Среди них ищутся Zmin по формуле (21).

Найденные значения Zmin указывают номера реализаций среди 2000 изображений, вектора-признаки которых совпадают с вектором-признаком выбранной как эталон реализации и т.д. Выбор эталонов для реализаций 1-го ОРПО проводится до тех пор, пока не будут распознаны все 2000 реализаций.

Аналогично, выбор эталонов проводится для всех реализаций всех остальных 9 ОРПО.

Результаты выбора эталонов для 2000 реализаций каждого из 10 ОРПО приведены в табл. 1.

На этом обучение системы распознавания завершается.

Экзамен обученной системы осуществляется на 20000 реализациях всех 10 ОРПО на основе формул (20) и (21).

Экзамен заключается в сравнении векторов признаков всех 20000 реализаций всех 10 ОРПО с выбранными эталонами.

Производится выбор некоторого случайного объекта. Для него выполняются все описанные процедуры получения безразмерных признаков контура. Полученный вектор признаков неизвестного ОРПО сравнивается со всеми эталонными векторами-признаками в табл. 2. Определяется тип ОРПО в соответствии с min{Zmin}.

Процедура экзамена повторяется для 2-го неизвестного объекта и так далее для всех 20000 реализаций всех 10 ОРПО. Строится таблица правильного распознавания.

Таблица 1

Номер ОРПО

1

2

3

4

5

6

7

8

9

10

Кол-во эталонов

33

34

48

19

20

27

35

28

33

27

Таблица 2

Результаты правильной идентификации всех реальных объектов при количестве эталонов от 10 до 48 на каждый объект

Номер объекта

Кол-во испытаний

Количество эталонов

15

20

25

30

40

48

кол-во

проц.

расп.

кол-во

проц.

расп.

кол-во

проц.

расп.

кол-во

проц.

расп.

кол-во

проц.

расп.

кол-во

проц.

расп.

1

2000

1160

58

1480

74

1721

86.05

1941

97.05

2000

100

2000

100

2

2000

1191

59.6

1490

74.5

1764

88.2

1917

95.85

 

100

2000

100

3

2000

937

46.9

1172

58.6

1375

68.75

1565

78.25

1833

91.65

2000

100

4

2000

1797

89.9

2000

100

2000

100

2000

100

2000

100

2000

100

5

2000

1838

91.9

2000

100

2000

100

2000

100

2000

100

2000

100

6

2000

1389

69.5

1740

87

1963

98.15

2000

100

2000

100

2000

100

7

2000

1189

59.5

1431

71.55

1658

82.9

1299

64.95

2000

100

2000

100

8

2000

1417

70.9

1706

85.3

1957

97.85

2000

100

2000

100

2000

100

9

2000

1169

58.5

1568

78.4

1845

92.25

1963

98.15

2000

100

2000

100

10

2000

1462

73.1

1698

84.9

1923

96.15

2000

100

2000

100

2000

100

pic_62.wmf

Рис. 2. График зависимости времени распознавания от числа эталонов на объект

График изменения времени на распознавание при увеличении количества эталонов представлен на рис. 2.

Заключение

Объект под номером 3 имеет простой контур. Но вследствии дискретного характера значения координат точек, составляющих изображение, при вращении меняется структура контура. При некоторых углах имеет место большее количество линейных участков контура изображения данного объекта. При этом при других углах линейный характер контура изменяется, и получаем большое количество выпуклых участков с углом 135. Вследствие этого первичные коэффициенты различных повернутых экземпляров данного объекта существенно отличаются. А значит, и полученные векторы признаков будут иметь отличия. На этапе обучения одним эталоном удается распознать меньшее количество изображений. Это привело к необходимости использовать 48 эталонов для достижения 100-процентного распознавания.

Те же рассуждения справедливы и для объекта 5. При вращении полутонового изображения получаем различное соотношение линейных, выпуклых и вогнутых участков контура.

При обучении системы для распознавания объекта под номером 4 получено 19 эталонов. При всей сложности изображения исходного объекта его бинаризованное представление дало небольшое различие в векторах признаков.

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