Способ классификации объектов по -признакам"

 

Союз Советсккн

Социал мстииеских

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ (;ВИДЕТЕЛЬСТВУ (l 586979 (6!) Дополнительное к авт. свил-ву (51) М. Кл. (22) Заявлено 12. 06.7 4 (21)207 3833/18-24

Су 06 К 9/00 с присоединением заявки Че

Гасударственный какнтет

Совета тйнннстрав СССР аа делам иэабретений н аткрытнй (23) Приоритет (43) Опубликовано 05.03.78. Бюллетень №9 (45) Дата опубликования описания10.02.73 (53) УДК 621.391.19 (088,8) (72) Автор изобретения

В, В. Чавчанидзе

Институт кибернетики AH Грузинской CCP (71) Заявитель (S4) СПОСОБ КЛАССИФИКАЦИИ ОБЪЕКТОВ ПО т(— ПРИЗНАКАМ

20

Изобретение относится к распоэнавани о образов, в частности к cnoñoáàì кпассификации объектов по тт признакам, и может использоваться в многочиспенных областях техники и науки, где необходимо оцредепить при помощи машины принадпежность к тому ипи иному классу предъявпенных объектов, отличающихся рядом признаков, которые могут быть, отнесены к тт классам.

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

Однако вышеуказанный спосоо обпадает малым быстродействием и небольшой надежностью кпассификации.

Белью изобретения является повышени быстродействия и надежности кпассификации.

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

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

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

Порог устанавливается на заданном уровне. Уровни могут меняться, число вариантов может, достигать десятков тысяч и все-таки

596979 где О; дает информацию о состоянии "наличия в g -й "точке" следов поступивших. сиги .лов

1Д

Л; есть элемент отсутствия" сигналов

35 в1 J -Й ячейке.

Поспе проведения такой анапогово-логической операции накапливается информация в каждой tj — и ячейке. При таком способе параллельной обработки чиспо "ячеек" может достигать миллионов.

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

О Ф.....+О ° ° = О;

t3 Д °

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

Концепт образа образуется путем раздепения матрицы Ф. ° на две части — на rrt,, ЗД эКонцептуально-сушественную часть — "яда 1 С3 ро концептуального образа } и Hartt . (концептуально-,несущественную часть}.

60 это никогда не поиведет к трудностям перебора.

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

Существенными можно считать точки, если число О>75% или < 25 o, несущественные точки те, дпя которых р в интервале

25-7 57, Выявление существенных характеристик точек класса накладываемых образцов проис- 0 ходит почти по аналогово-погической опе 4I и рации дпя каждой эпементарной точки от.— дельно ("принцип атомарности ). а;.++A -a"

t 3 ФД (Д (Д !Д. 4Д

1Д

И первой части g ядро концептуального образа ) ые пусты голько те точки" ячейки (топосы ) (j, в которых А; ) д;. >ц ° или A- ° 6 8 "ot фД 1Д 0 где И 0" — некие nopot говые значения (например, 0,75 и 0,25, соответственно от общего числа, предъявленных образцов), а во второй части те, для которых - "Д ° ° g tfQ . ° С Д Я

4Д

При вырабогке концепта можно поступить трояким образом: а с первое — отбросить rff и хранить ttf; (яд1Д ро концепта-образа ); второе — хранитья Д в булевой форме, т. е.

Д юу превратить все топосы (ячейки), где А; > И О;, просто в топосы", где Д ð (погическое

Ц 1Д присутствие без указания количестваа появпений) . Такое ttf обозс с ФД . начим через ttf- (LI концепт1Д образ-логический; а а третье - вместо щ; хранить rrf; (Н} где каждйи элемент, неудовпетворяюший услоВиям А- П с(; ипи

4 43

А;Д 4 rf О;Д . заменяется на неойределенйый (точнее статистически ипи материально нефиксируемый элемент) Ь; °, который можетпотенциапьно превратиться яибо в а;д>пибс в о с весом(э 0,75, или p 0,25.

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

Распознавание образца по нашему способу дается прямым сравнением матрицы-номина-с ла образе с матрицей образца. я н е (ядро образа ), где операция - означает переход от картины" с уровнем пор рога Я к л)овню 1- Я = Я с последующим "стиранием" или "нестиранием всех точек выше Р . В таком случае матрица К будет в точках с минимальным порогом просвечиваться ипи "затемняться попностью только тогда, когда образец имеет отношение к классу образа (при заданном уровне сравниваемых масштабов). Установив интегральный уровень для затемнения ипи " просветления, можно с наперед заданной точностью и .надежностьк относить образец к образу-концепту (например, степень вероятности достоверного распознавания К 0,9999. Эта степень легко достижима, так как число точек бывает порядка миллиона) .

Для пояснения способа ниже приводится пример обнаружения заданного образа.

Наложение образов представлено на .фиг. 1, 2, Э. На фиг. 1, 2 показано наложе59697 9 нве на матрицу двух различных вариантов написания русской буквы "0, на фиг, 3— наложение этих двух букв друг на друга, на фиг. 4 концепт-результат наложения

250 вариантов написания буквы О .

Пусть требуется составить концепт дпя русской буквы 0 . Берут 250 вариантов написания буквы О из слитных рукописных текстов различных почерков.

Порог устанавливают на уровне 200, т. е. считают те точки, которые совпали нне менее 200 раз.

Первый шаг, На матрицу из 256 ячеек помешают первый вариант фотоизображения рукописной буквы

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

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

Третий шаг. Составляют концепт руконисной буквы "0". Устанавливают порог 200 и стирают изображения в тех ячейках, в которых совпадение произошло менее

200 раз.

Оставшуюся часть называют концептом рукописной буквы 0" и обозначают, б

На полученном концепте автоматически выделяют все характеоные сушественные точки буквы "О, т. е. число фиксированных ячеек на матрице иэ

«!56 ячеек равно 30, Четвертый шаг Классифицируют буквы координаты сушественных точек ° кон пента <",, логически сравнивают с соответсвуюшими точкамн разпоэнаваемой буквы « О . Совпало 90% точек, распознаваемую букву относят к классу буквы О .

Формула изобретения

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

Источники информации, принятые во внимание при экспертизе:

1. Патент СССР ¹ 38967 1, N. кп. Я 06 1(9/00, 02.06.69.

59697 9

XX

Рис. Ф

Составитель А. Карпов

Редактор Л, Бабич Техреа Н. Еабурка Корректор Л. Небола

Заказ 1145/49 Тираж 826 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 1/5Фипиап ППП "Патент» г . Ужгород, уп. Проектная, 4