Обзор методов распознавания и идентификации объектов
Распознавание – процесс разметки сцены, представляющей собой проекцию трёхмерного рабочего пространства ПР на плоскость объектива, регистрирующего устройства – цифровую камеру (ЦК) или ультразвуковой модуль (УЗМ). В процессе разметки происходит выделение информации относительно объектов расположенных в поле зрения УЗМ. Обычно в промышленных системах УЗМ расположен перпендикулярно рабочей поверхности рассматриваемых объектов, чем достигается уменьшение вероятности перекрытия одних объектов другими. Такое упрощение приводит к уменьшению вариации признаков в зависимости от расположения УЗМ и упрощает процесс сегментации и описания сцены в целом.
Распознавание наиболее сложный процесс, поскольку тесно связан с методами предварительной обработки изображения. Зачастую качество распознавания зависит от эффективности множества процессов, начиная от процесса ввода изображения и заканчивая формированием признаков объекта. Наиболее важной задачей при распознавании является задача описания свойств объекта – дескрипторов, для последующей идентификации объекта.
Непосредственно с задачей распознавания возникает задача идентификации объектов – процесс тесно связанный с распознаванием, заключающийся в объединении всей полученной информации от процесса распознавания в единое целое с целью классифицировать объект. Большинство известных методов не проводят чёткой границы между процессом распознавания и идентификации, поскольку выделение признаков происходит за счёт модификации исходного изображения.
Методы описания объектов
Конечной целью распознавания сцены, является процесс формирования дескрипторов для объектов сцены. Дескрипторы представляют собой структуру описания свойств объекта. Описание является основным результатом при конструировании СТЗ, поскольку дескрипторы должны влиять не только на сложность алгоритмов распознавания, но и на их работу. Существует три основные категории дескрипторов [1]: дескрипторы границы, дескрипторы области, дескрипторы для описания трёхмерных структур.
Дескрипторы границы включают в себя ряд наиболее распространённых методов: цепные коды, сигнатуры, аппроксимация многоугольниками, дескрипторы Фурье.
Цепные коды применяются для представления границы в виде последовательности отрезков прямых линий определённой длины и направления. В основе этого представления лежит 4- или 8- связная решётка. Длина каждого отрезка определяется разрешением решётки, а направления задаются выбранным кодом. Для порождения цепного кода заданной границы сначала выбирается решётка. Тогда, если площадь ячейки, расположенной внутри границы, больше определённого числа, ей присваивается значение 1; в противном случае этой ячейке присваивается значение 0. В данном методе основное место занимает процедура разбиения границы объекта на составляющие части. Недостатком метода является то, что цепной код данной границы зависит от начальной точки. Однако некоторые разработчики СТЗ применяли в этом методе нормирование, тем самым, обходя данный недостаток.
Сигнатуры представляют собой одномерное функциональное представление границы. Наиболее простым способом создания сигнатур является построение отрезка из центра к границе как функции угла. Такие сигнатуры являются зависимыми от периметра области и начальной точки отрезка. Применение такого дескриптора границы возможно только при его нормировании. Непосредственное применение сигнатур не представляется возможным, поскольку несколько сигнатур для разных объектов должны быть различимы. Для введения параметров различия наибольшее распространение получил способ описания сигнатур посредством вычисления её моментов. Целесообразность применения данного дескриптора заключается в получаемых выходных данных – одномерные функции, которые проще обрабатывать при описании объекта.
Другим видом разложения границы объекта в дескриптор является представление её в виде многоугольников – аппроксимация многоугольниками. При использовании цифровой обработки изображения границу объекта можно аппроксимировать с произвольной точностью. Для замкнутой границы аппроксимация многоугольниками является точной, тогда когда число сегментов в многоугольнике равно числу точек границы, так что каждая пара соседних точек определяет сегмент многоугольника. Целью такой аппроксимации является качественное определение формы границы с помощью минимального числа многоугольных сегментов. Долгое время практическое применение данного метода было невозможно из-за сложности задачи и ограниченности ресурсов вычислительных средств СТЗ. С появлением аппаратных средств воспроизведения графической информации данный метод был оптимизирован и реализован аппаратно. Наибольшее применение получил алгоритм построения триангуляции Делоне [2], в основе которого положен принцип аппроксимации многоугольниками множества точек границы объекта. Наряду с алгоритмом триангуляции Делоне применяются и более простые алгоритмы: наименьшего периметра, интуитивного объединения и разбиения.
При построении СТЗ основным требованием всегда является гибкость системы. Выше приведенные дескрипторы границы объекта практически сложно автоматически генерировать при обучении новому объекту. Оператор должен производить корректировку дескрипторов выборки обучения, вводимых в общую базу данных СТЗ для последующего процесса идентификации. Перенастройка СТЗ на распознавание новых объектов зачастую связана с длительным процессом вывода подобных дескрипторов отдельно для каждого нового объекта, при этом гибкость всей системы снижается.
Решение задачи автоматического формирования дескрипторов объекта, получается за счёт применения математического аппарата разложения сигнала в ряд Фурье – получение дескрипторов Фурье. Дескрипторы Фурье рассчитываются на комплексной плоскости, где каждая точка (x, y) границы соответствует комплексному числу (x+j·y). Последовательность из М точек границы представляется в виде функции, имеющей преобразование Фурье F(u), u=0, 1, 2, …, M-1. Если М является целым числом (степенью 2), F(u) вычисляется с помощью алгоритма быстрого преобразования Фурье [1, 3]. Данный метод получил широкое распространение в силу того, что для последующей идентификации существенно разных форм обычно требуется только несколько первых компонент F(u); преобразование Фурье легко нормируется для размера, поворота и начальной точки границы; для изменения размера контура достаточно умножить компоненты преобразования Фурье на константу, что вследствие линейности преобразования Фурье эквивалентно умножению границы на один и тот же множитель; поворот на угол θ осуществляется умножением элементов F(u) на exp(jθ) [4]. Данный метод реализован в большинстве промышленных СТЗ на основе оптических вычислительных средств. Следует отметить, что это дорогостоящие системы, что ограничивает область применения таких систем (системы навигации боевых ракет дальнего действия, авиационных и космических систем).
С развитием электронных вычислительных средств и средств регистрации зрительной информации всё больше исследователей и разработчиков СТЗ начали использовать информацию не только о форме объекта, но и о характеристиках ограничительной области объекта: текстура, скелет объекта и т.п. Хотя рассмотренные выше дескрипторы границы объекта представляют некоторую информацию об объекте роботизации и могут использоваться для описания области объекта, но не дают полной картины распознаваемой сцены, в отличие от дескрипторов области.
В случае если распознаваемые объекты отличаются друг от друга настолько, что для их последующей идентификации достаточно лишь нескольких основных дескрипторов, можно применить такие дескрипторы, как: площадь объекта, большая и малая оси объекта, периметр области объекта, связность отдельных областей одного объекта.
Если объекты представляют собой подобные по начертанию границы, но разные по характеру поверхности, то возможно применение дескрипторов текстуры. Дескриптор текстуры формального определения не получил – это, скорее всего, интуитивное описание поверхности (шероховатость, однородность, регулярность). На практике применяются два подхода для получения дескриптора текстуры объекта: структурный и статистический. Структурные методы позволяют установить взаимное расположение элементарных частей образа, таких как, описание текстуры, основанной на регулярном расположении параллельных линий. Статистические методы дают такие характеристики, как однородность, шероховатость, зернистость, узор и т.п.
Наиболее простой и получивший широкое применение в системах, связанных с обработкой объектов на основе текстуры, является метод, использующий моменты гистограммы интенсивности области объекта. Данный метод применяется к дискретизированному изображению, которое представляется интенсивностью отдельной точки изображения – пикселем. На первом этапе производится нахождение гистограммы интенсивности области объекта. На втором этапе производится вычисление моментов (до шестой степени) относительно среднего значения интенсивности области. Дескриптор, построенный по данному методу включает в себя: второй момент – дисперсию интенсивности области объекта, которая представляет меру контраста интенсивности и применяется в дальнейшем для описания однородности поверхности объекта; третий момент, который представляет собой меру асимметрии гистограммы, а четвёртый момент является мерой её относительной ровности. Пятые и шестые моменты представляют скорее практический интерес, поскольку их не так легко связать с формой гистограммы, но они дают определённую количественную информацию о виде текстуры объекта [4]. Данный метод нашёл практическое применение при идентификации шероховатых объектов на участках сборки деталей. При наличии в базе данных большого числа подобных объектов данный метод применяется в модифицированном виде: в процессе анализа текстуры объекта рассматривается не только распределение интенсивности, но и взаимное расположение пикселей с равными или почти равными значениями интенсивности.
Среди структурных методов получения дескрипторов области, следует отметить метод, основанный на получении описания области в виде графа – скелета области, т.е. схема области. В данном методе для получения скелета применяется большое количество алгоритмов прореживания, такие как: преобразование средних осей, алгоритм Накаши и Шингала [1], волновой метод [2, 5]. Перечисленные алгоритмы прореживания связывают свою работу с бинарным изображением, что требует в случае градационного изображения, предварительной его обработки.
Одной из наиболее быстрых и простых при реализации процедур прореживания является алгоритм, разработанный Накаши и Шингалом. Данный алгоритм основан на понятиях связности пикселей изображения; прореживание производится на основе вычисления логической функции на образе окна изображения. Выбор связывающей логической функции производится на основе интуитивно введённых функций последствий объединения и разрыва.
Волновые алгоритмы часто используются для определения минимального расстояния между объектами в пространстве (оптимизационные алгоритмы компьютерной графики), а в СТЗ они получили применение для реализации функции прореживания. Для этого, в исходной точке генерируется волна, распространяющаяся по определенным законам, помечающая пройденные точки номером шага. Процесс заканчивается по достижении целевой точки. Номер шага, которым помечена целевая точка и будет расстоянием от исходной до целевой точки. Построение скелета в данном случае сводится к выделению отрезков и мест их соединения с занесением найденных данных в результирующий граф. Выделение производится с помощью анализа пути прохождения волны, с пометкой пройденного пути (для предотвращения двойного прохождения волны по изображению). В результирующий граф скелета изображения заносятся средние точки для каждой генерации волны. С уменьшением количества точек в процессе движения волны производится анализ перемещения средней точки последней генерации волны, и в граф заносятся только точки, в которых происходит изменение направления движения средней точки. Методы скелетизации дают положительные результаты при работе с бинарными изображениями сцены, однако применение их для обработки градационных изображений ограниченно погрешностями при бинаризации области объекта. Здесь следует отметить, что скелет области непосредственно не может быть использован для последующего процесса идентификации и требует применения дополнительных алгоритмов описания полученного скелета. С появлением задач автоматического распознавания печатных текстов, данный алгоритм был модифицирован для распознавания печатных и рукописных текстов [5].
С созданием средств ввода и обработки потокового цифрового видео, применимым стал метод, основанный на получении описания объектов в виде инвариантных к преобразованиям перемещения, поворота и изменения масштаба моментов. Применение данного дескриптора в случае потокового видео более целесообразно, поскольку сокращается время на обработку отдельно взятого кадра потока видеоданных. Метод использует моменты до третьего порядка. Ограничение является экспериментальным, поскольку вычисление моментов более высокого порядка требует значительных вычислительных средств. На основе только нормированных центральных моментов 2- и 3-го порядков, выводятся наборы инвариантов моментов. Наиболее применимыми стали семь инвариантов моментов, получивших в литературе название Ху-дескрипторов (HU-descriptors)
Методы идентификации объектов
Современные методы идентификации делят на две основные категории: теоретические и структурные методы. Теоретические методы основываются на количественном описании идентифицируемых объектов сцены. Структурные методы основаны на применении символических описаний и связей между ними. Обе категории методов широко применяются для идентификации образов двумерных объектов.
Наиболее простым среди теоретических методов идентификации объектов, является метод решающих функций. Метод предполагает, что перед процессом идентификации был проведен процесс распознавания (процесс описания объекта), в результате которого был получен на этапе обучения вектор
– модели объекта с действительными компонентами, где
– i-тый дескриптор рассматриваемого объекта. Если задано М классов объектов
, то задачей идентификации является определение М решающих функций
, таковых, что для любого модельного вектора
, принадлежащего классу
, выполняются неравенства:
,
. Метод позволяет произвести робастную идентификацию объекта. Он часто применяется для объектов, которые между собой мало подобны. В случае близости объектов метод может приводить к ошибочной идентификации. В качестве неравенств, применяются различные их модификации, которые зависят от конкретной системы распознавания и имеющихся дескрипторов объектов. На основе данного метода строятся также корреляционные методы распознавания. В таких методах процедуры распознавания и идентификации объединяются в единую процедуру – нахождения подобраза на более большем образе. Нахождение подобраза производится за счёт вычисления коэффициента корреляции, который может иметь вид относительного отклонения гистограммы интенсивностей подобраза от гистограммы интенсивностей текущего подобраза изображения сцены. Данный метод чувствителен к масштабированию, повороту. Применяется зачастую в системах пассивной навигации, распознавание заданных участков местности на карте при аэрофотосъёмках, участки роботизированной сборки с точным позиционированием деталей.
Другим теоретическим методом является метод потенциальных функций. Первоначально был предложен для решения задач обучения идентификации образов, а в дальнейшем был обобщён и реализован для более широкого круга задач, связанных с восстановлением и аппроксимацией функций. Метод подобен описанному выше методу, однако имеет более высокие показатели качества идентификации объектов. В основе метода заложена геометрическая интерпретация задачи идентификации, заключающаяся в представлении изображений в виде векторов в пространстве входных сигналов. Это позволяет представить задачу идентификации как обычную аппроксимационную задачу. В процессе обучения показываются точки и сообщаются значения функции в этих точках. Требуется восстановить функцию во всём пространстве предъявляемых значений в процессе работы метода. Алгоритмы метода потенциальных функций базируются на основной гипотезе о характере функций, разделяющих множества, соответствующие различным объектам [8].
Теоретические методы идентификации основываются на количественных моделях объектов, которые пренебрегают геометрическими параметрами, присущими форме объектов. В противовес теоретическим методам, структурные методы идентификации используют эти параметры для описания идентификационной модели объекта.
В основе структурных методов распознавания образов положена декомпозиция объекта на составляющие его элементарные примитивы. В данных методах более приемлемо использование дескрипторов границы, которые, как выше отмечалось, представляют собой разбиение границы на элементарные части, которые имеют собственные свойства идентификации. Такое представление данных применяется в наиболее простом методе – методе подбора индексов границ. В данном случае граница объекта представляется цепным кодом. Данный код состоит с отрезков границы, которые имеют разные направленности. Для процесса идентификации строится дерево схожести и матрица схожести. Дерево схожести представляет собой иерархическое разбиения форм отрезков в зависимости от расположения в границе объекта. Общая база данных эталонных объектов при этом представляется в виде путей следования отрезков, составляющих границы отдельного объекта. Метод применим в системах с дискретными датчиками позиционирования для плоских объектов.
Более ресурсоёмкими методами идентификации являются синтаксические методы. Эти методы включают в себя процессы распознавания (описания) и идентификации. Простейшими элементами в методе являются описания границы объекта на уровне связей её точек. В соответствии с этими связями строятся правила восстановления границы объекта – грамматики. Для задания эталонного объекта создаются из грамматик предложения, описывающие границу данного объекта. Данный метод положительно работает при описании скелета области в базе данных эталонных объектов в виде одного или нескольких предложений.
Приведённые методы распознавания и идентификации находят своё применение в различных системах технического зрения. Они предоставляют возможности создавать гибкие перепрограммируемые или самообучаемые системы распознавания для промышленных и непромышленных систем автоматизации деятельности человека в различных областях науки и техники.
Существующие системы технического зрения
Создание собственной подсистемы распознавания и идентификации объектов рабочего пространства требует рассмотрения аналогичных систем, поскольку разработки в данной области должны быть направлены на модификацию существующих методов либо на создание совершенно новых методов работы подсистемы в целом. При рассмотрении существующих разработок выявляются характеристики классических методов обработки зрительной информации, их положительные и отрицательные стороны.
Подсистемы подобного класса разрабатываются в большинстве случаев крупными корпорациями для собственных промышленных потребностей. Такие разработки зачастую являются узкоспециализированными. Этот факт представляет собой значительную проблему при портировании подобных систем в условия средних и малых предприятий. На большинстве предприятий до сих пор используются старые модели СТЗ, зарекомендовавшие себя как надёжное средство автоматизации производства.
Одной из достаточно давно разработанной и с успехом применяющейся в робототехнике является СТЗ «Autoview» фирмы British Robotic Systems (Великобритания). Система построена на базе специализированного процессора LSI 11-13, который способен в реальном масштабе времени анализировать изображения размером 256x256 (256 градаций яркости). Алгоритмы работы заключаются на непосредственном взаимодействии захватывающего устройства ПР с распознаваемым объектом, который перемещается перед объективом статически закреплённой камеры, с целью идентификации и дальнейшей обработки объекта. Система в комплексе с СУ ПР обеспечивает позиционирование детали с погрешностью не более ±0,5о. Область применения: участки автоматической сборки изделий. Недостатком системы является статическое расположение камеры, что сказывается на требованиях, предъявляемых к рабочему пространству СТЗ.
Другим применением СТЗ, являются технологические участки сортировки проходящих по конвейеру объектов. СТЗ подобного класса является разработка фирмы Optical Recognition Systems (США). Система используется на участках сортировки пачек сигарет. В системе используется информация о цветовой гамме пачек. Информация поддаётся модифицированному алгоритму гистограммного сглаживания, за счёт которого обеспечивается скоростное выделение краёв объектов, с последующей идентификацией объектов по цветовой гамме.
Применение ПР, оснащённых СТЗ не ограничивается производственными помещениями предприятий. В институте имени Келдыша разработан экспериментальный комплекс, который в реальном времени эмулирует захват космического спутника с помощью манипулятора ПР типа РМ-01. СТЗ является аппаратно-программным комплексом на базе персонального компьютера и двух статически закрепленных видеокамер. В системе используются методы распознавания на основе особых точек объекта. К недостаткам системы следует отнести отсутствие мобильных камер и как следствие высокие технические требования к рабочему пространству ПР.
Наиболее перспективная и многообещающая область применения СТЗ – это зрительное очувствление мобильных роботов. Здесь сказываются отличия мобильных роботов от статически установленных роботов – возможность свободно перемещаться в производственном помещении. Их область применения наиболее обширная: транспортные операции в пределах цеха; подводные, космические, геологические исследовательские работы и др. В таких системах скоростные характеристики СТЗ являются критическими, поскольку она должна обеспечивать распознавание и идентификацию объектов окружающего пространства за время меньшее, чем 1/30 секунды.
|