Оригинал статьи находится по адрессу
Представлено описание простого алгоритма распознавания трехмерных предметов, описан алгоритм оконтуривания проекций предметов и их частей на изобразительную плоскость, предложены методы распознавания трехмерных предметов по части контура в случаях простого и сложного фона, представлены результаты демонстрационных расчетов.
В ряде технических приложений весьма актуальной является задача распознавания техногенных трехмерных объектов, находящихся под разными ракурсами относительно устройства распознавания. Так, например, для ориентирования роботизированного мобильного комплекса на пересеченной, заранее неизвестной местности, актуальной является задача анализа ситуации с помощью бортового вычислителя, исходя из информации, поставляемой системой технического зрения в реальном времени. Необходимо оперативно определять скорости объектов и расстояния до них, распознавать объекты, информация о которых имеется в базе данных бортового вычислителя, определять их положение в пространстве относительно мировой и бортовой систем координат.
В основу решения поставленной задачи был выбран метод анализа геометрических характеристик контурных линий, окаймляющих распознаваемый предмет на изобразительной плоскости, на которую они проецируются. Был предложен и испытан эффективный метод распознавания трехмерных объектов, ориентированных произвольным образом.
С использованием разработанной на основе этого метода вычислительной программы DETERMINATOR, осуществляется сравнение предъявляемого к распознаванию контура с эталонными контурами некоторого числа заранее заданных предметов в разных ракурсах, сжатая информация о которых размещена в базе данных. При применении в системах технического зрения метод, кроме определения геометрического положения распознанного предмета в пространстве, позволяет определять также и расстояние до него.
На первом этапе испытания эффективности предлагаемого метода считается, что распознаваемый предмет располагается изолированно от других на однотонном фоне и на изобразительную плоскость проецируется только его внешний контур, причем на стадии создания базы данных он проецируется в полную величину, без каких-либо искажений.
В основу метода положено простое представление контура в виде набора некоторого небольшого количества цифр, инвариантного относительно трансляций, ротации и изменения масштаба. На первом этапе производится выбор характерных точек контура.
Первой характерной точкой, как и в литературе [L.Gupta and M.R.Sayeh. Neural networks for planar shape classification. IEEE. 1988. P.936], является наиболее удаленная точка от центра тяжести контура, второй характерной точкой является точка контура, наиболее далеко отстоящая от первой. Третья точка и последующие определяются как наиболее удаленные от двух точек, между которыми они находятся. Процесс нахождения характерных точек продолжается до тех пор, пока отношение расстояния от искомой точки до прямой, соединяющей эти две точки, к длине отрезка между ними не станет меньше некоторой, заранее заданной величины EPS. Эта величина является одним из немногих настроечных параметров программы, она подбирается экспериментально таким образом, чтобы программа различала два наиболее близких друг к другу контура двух разных предметов из всей группы. Результат нахождения характерных точек для некоторого частного примера проекции трехмерного предмета на плоскость представлен на рисунке 1.
- Recognition3D1.gif (4.19 КиБ) Просмотров: 14986
Рис.1. Нахождение характерных точек контура.
Достоинством данного метода поиска характерных точек контура является то, что этот процесс инвариантен относительно поворотов, трансляций и изменения масштаба. Можно показать, что данный метод слабо чувствителен и к искажениям части контура: положение характерных точек в частях, не подвергшихся искажениям, остается прежним.
Каждому полученному по приведенному выше алгоритму линеаризации контура отрезку ставится в соответствие два некоторых числа n1 и n2, равных отношениям длины данного отрезка к длинам сторон треугольников, прилегающих к нему (причем выбирается сторона, не являющаяся отрезком контура).
Дополнительно к этим двум числам данному отрезку присваивается признак z=1, если соседние отрезки прилегают к данному с одной стороны, как на правой части рисунка, или z=-1, если они находятся с разных сторон.
Путем простейших математических преобразований можно показать, что полученный таким образом набор групп чисел для отрезков всего контура позволяет однозначно определить относительные координаты всех характерных точек и, следовательно, в этом наборе содержится информация не только об относительных длинах отрезков контура, но и об углах между ними, и данный набор чисел является сжатым представлением линеаризованного контура. Данное представление контура после простого преобразования позволяет организовать простую и занимающую мало места базу данных или применять нейросетевое распознавание.
Очевидно, что полученное таким образом двоичное число для данного контура будет инвариантно относительно трансляций, ротации и изменения масштаба контура.
В настоящей работе распознавание предметов по части контура или по всему контуру осуществлялось с использованием специально устроенной базы данных, содержащей наборы двоичных чисел, характеризующих контуры, и соответствующие им названия трехмерных предметов и параметры их ориентации в пространстве.
Заполнение базы данных осуществлялось так: запоминаемый предмет случайным образом ориентируется относительно изобразительной плоскости и по алгоритму, описанному выше, определяется характеристическое двоичное число для данного контура и заносится в базу данных совместно с названием этого предмета, параметрами его ориентации в пространстве и последовательно расположенными по обходу контура тройками чисел n1, n2 и z, однозначно описывающими его.
Исходя из этой информации определяется, был ли уже занесен данный контур в базу данных, - и если он уже есть, то генерируется следующее случайное положение предмета. В противном случае информация о предмете и его ориентации заносится в базу данных. Этот процесс продолжается до тех пор, пока не будет получено подряд k отказов в занесении информации в базу данных. Величина k является третьим настроечным параметром программы (второй параметр - это масштабный коэффициент m) и в настоящей работе получены оценки, что при k=10 происходит надежное распознавание предъявляемых предметов с вероятностью, превышающей 0.99. Также оценки показывают, что для набора из семи предметов, использованного при тестировании данной программы, при значениях настроечных параметров, приведенных в настоящей работе, достаточно занести примерно 3000 различных ракурсов каждого предмета. При использовании в качестве носителя базы данных современный компакт-диск можно разместить порядка тысячи предметов. Следует отметить также, что предлагаемый метод распознавания является универсальным и может применяться в более простых задачах - распознавании символов, иероглифов, отпечатков пальцев и других плоских изображений.
При распознавании неизвестного предмета программа работает следующим образом. После предварительной обработки контура или его части получается характеристическое число x, как это описано выше. Далее из базы данных выбирается наиболее близкое по набору единиц число или несколько таких чисел и проводится окончательная проверка на соответствие контура или его части контуру, описанному в базе данных наборами из троек чисел, однозначно описывающих контур. Заключительная проверка особенно актуальна, когда появляется одновременно несколько равноценных "кандидатов".
В базу данных заносятся также габаритные геометрические размеры каждого предмета. Эта информация может быть использована для определения расстояния от устройства распознавания до данного предмета. Расчет расстояния производится по простейшим формулам геометрической оптики. Как это было описано выше, при наличии двух последовательных изображений предмета простыми вычислениями определяется скорость предмета, а поскольку программа позволяет определить пространственную ориентацию распознанного предмета, то становится возможным и определение вектора направления скорости.
Получаемая таким образом информация позволит решать такие сложные задачи, как анализ ситуации, формирование и накопление базы знаний о среде, планирование оптимальной безопасной траектории движения к цели, принятие управленческих решений об очередном движении. Простота используемых алгоритмов для решения таких задач позволяет надеяться, что при применении данного метода станут возможными обработка информации в реальном времени и увеличение скорости роботизированного мобильного комплекса при движении по неизвестной местности до технически достижимых величин.
При распознавании трехмерного предмета по части его контура на сложном фоне программа работает следующим образом. При заполнении базы данных характеристические числа x определяются для всей совокупности контуров, принадлежащих трехмерных предмету, как внешних, так и внутренних. Контуры в данном случае образуются границами раздела областей различных цветов и интенсивностей на изображении предмета в проецирующей плоскости так, как это представлено, например, на четвертой части рисунка 2.
Распознавание предмета на сложном фоне осуществляется после предварительной обработки плоского цветного изображения. Вначале цветное изображение конвертируется в черно-белое со ступенчатой градацией яркости (смотрите первую часть рисунка 2). Далее программа определяет границы между областями разной интенсивности и внутренние части областей, расположенных между этими границами, заливает черным цветом (смотрите вторую часть рисунка 2). Области, площади которых меньше некоторого критического размера, подбираемого заранее экспериментально, из рассмотрения исключаются (заливаются белым цветом). После этого включается в работу подпрограмма оконтуривания, которая обрабатывает каждую черную область, как это было описано выше. Результат выполнения данной операции приведен на третьей части рисунка 2. Далее по алгоритму, описанному выше, для каждого замкнутого контура определяются характеристическое число x и из базы данных выбираются списки наиболее близких по составу набора единиц ракурсов трехмерных предметов. Поскольку в данном случае по сравнению с оконтуриванием по внешнему контуру частичные контуры предмета проще по составу и в числе x меньшее число единиц, то, как правило, каждому простому внутреннему контуру программа находит из базы данных десятки возможных кандидатов.
После составления списков возможных кандидатов на распознавание для каждого замкнутого контура производится пространственный анализ оконтуренного рисунка. Он заключается в следующем. Сопоставляются списки возможных кандидатов каждого рассматриваемого замкнутого контура и всех его ближайших соседних и тот кандидат на распознавание, который встречается в большинстве этих списков и является наиболее вероятным.
На четвертой части рисунка 2 представлен окончательный результат распознавания - на нем отображены все замкнутые, расположенные по соседству контуры ракурса единственного совпадающего предмета во всей базе данных. Естественно, если бы на картинке на сложном фоне были бы расположены разные предметы, то они после подобной фильтрации все были бы выявлены. Исходя из анализа представленного здесь описания метода распознавания трехмерного предмета на сложном фоне, очевидна его потенциальная работоспособность и в случае, когда на рисунке изображена только часть контура или трехмерные предметы частично заслоняют друг друга. Экспериментальная проверка распознавания различных случаев такого перекрытия или расположения части предмета на рисунке показала уверенное распознавание предметов, если на рисунке присутствует больше половины изображения предмета. В случаях, когда на рисунке присутствует меньшая часть изображаемого предмета, появляется тем большое число кандидатов на распознавание, чем меньшая часть предмета изображена на рисунке.
Рис.2. Результат распознавания объекта на сложном фоне.
Тестирование программы в "стерильном" случае, когда предмет распознавался по его внешней проекции на чистом фоне, осуществлялось на наборе из семи предметов с использованием специальной программы генерации трехмерных объектов в 3D-геометрии. На рисунке 3 представлены изображения этих предметов в фиксированный момент времени. С помощью этой программы выделяется одиночный предмет, и его изображение запоминается в графическом файле. Далее осуществляется вход в программу DETERMINATOR в режим РАСПОЗНАВАНИЕ. На экране появляется силуэт запомненного на предыдущем этапе предмета и производится поиск этого контура в базе данных по алгоритму, описанному выше. Результат распознавания предмета по части контура представлен на рисунке 4.
- Recognition3D3.gif (2.28 КиБ) Просмотров: 14974
Рис.3. Библиотека объектов.
Рис.4. Результат распознавания объекта по части контура.
Проверка программы на тестовых наборах предметов при проведении статистических испытаний по методике, близкой к описанной в литературе [А.П.Горелик, В.А.Скрипкин. Методы распознавания. М. "Высшая школа". 1989. С.216], показала устойчивую работу при различных искажениях частей контуров, достигающих до 50 процентов контура.
Была осуществляется проверка метода при работе программы DETERMINATOR на сложном фоне, когда распознаваемый предмет расположен среди контурных линий, обрамляющих разнообразные предметы, их тени и прочее (смотрите рисунок 2). Получены удовлетворительные результаты, что позволяет надеяться на применение предлагаемого метода в реальной обстановке при распознавании предметов на фотоснимках и телеизображениях.
кандидат физико-математических наук Протасов Владислав Иванович, 11 февраля 2003 года protonus@yandex.ru
В заключение автор благодарит И. Каляева, инициировавшего данную работу и В. Шаповала, любезно предоставившего программный генератор движущихся трехмерных объектов. Данная статья была опубликована в 2001 году в журнале “Нейрокомпьютеры. Разработка и применение” в 7 и 8 выпусках.
Список литературы
1. L.Gupta and M.R.Sayeh. Neural networks for planar shape classification. IEEE. 1988. P.936.
2. А.П. Горелик, В.А. Скрипкин. Методы распознавания. М. "Высшая школа". 1989. С.216.
Я бы даже не подумал про вирус. Пусть Касперский думает! 
Для распознавания или позиционирования вполне подходит
