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

РГБ ОД

- 3 ИЮП 1995

На правах рукописи

Иванюгин Виктор Михайлович

ИССЛЕДОВАНИЕ МЕТОДОВ И РАЗРАБОТКА АЛГОРИТМОВ ДЛЯ МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ СТЕРЕОТЕЛЕВИЗИОННОЙ СИСТЕМЫ ТЕХНИЧЕСКОГО ЗРЕНИЯ РОБОТА

Специальность 05.13.16 Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат диссертации на соискание ученой степени кандидата технических наук

Соискатель С&я^-^ В.М.Иванюгин

Москва 1995

Работа выполнена в Государственном Институте, физико-технических проблем.

Научный руководитель: кандидат технических наук,

заведующий сектором ПЕТУХОВ C.B.

Официальные оппоненты: доктор технических наук, профессор, заведующий лабораторией ИПМ РАН ГРАДЕЦКИЙ В.Г. доктор физико-математических наук,профессор, вед. научный сотрудник ВЦ РАН ' ДИКУСЛР В.В.

Ведущее предприятие: НПО "СПЕКТР"

Защита диссертации состоится " "_ 1995 г.

в_час. на заседании диссертационного совета ССД-

109.02.01 при ГосИФТП, 119034, Москва, ул.Пречистенка, д. 13/7, зал заседаний. С диссертацией можно ознакомиться в библиотеке ГосЯФТП.

Автореферат разослан " " _ 1995 г.

Ученый секретарь диссертационного совета кандидат технических наук Ь/Л. Лридорогин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Системы технического зрения (СТЗ), как прикладные реализации методов машинного зрения, находят широкое применение в робототехнических комплексах различного назначения. Дальномерные СТЗ позволяют измерить пространственные координаты поверхности и обнаружить препятствия. Подобные системы предназначены в первую очередь для транспортных роботов (ТР), имеющих самостоятельное значение в робототехнике. ТР могут иметь широкий спектр применения, особенно в экстремальных, опасных для человека условиях.

К далыюмерным системам относится и стереотелевизионная СТЗ (стерео-СТЗ), которая позволяет определить геометрические характеристики окружающих объектов. В настоящее время стерео-СТЗ находят все более широкое применение помимо робототехники, например при обра-

ботке аэрофотоснимков, для навигации, в медицине и сте-реомикроскопии.

Цель работы:

• рассмотреть современное состояние машинного сте-реозрения и выделить наиболее важные условия, влияющие на его эффективность;

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

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

Методы исследования. В реферируемой работе использованы методы динамического программирования, ди<| ференциального исчисления, методы регуляризации для решения некорректно поставленных задач, методы функциональной аппроксимации.

Научная новизна реферируемой работы состоит в следующем:

• Предложен метод обработки СТИ, сочетающий одномерный оператор для обнаружения контурных признаков, (далее просто признаков), и двумерный оператор пространственной аппроксимации для определения параметров найденного контура.

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

• Разработан метод отождествления найденных признаков на полном СТИ. Он основан на предложенном выше алгоритме и заключается в описании изображений стереопары деревьями, с их последующим согласованием для определения изоморфного поддерева соответствующих признаков.

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

Практическая ценность реферируемой работы состоит в следующем.

• Разработанный метод обработки СТИ, учитывает особенности его формирования и прост в реализации.

• Разработанные алгоритмы отождествления признаков на СТИ от существующих отличает высокая вычислительная эффективность, благодаря подходу с использованием оптимального покрытия списков признаков.

• Использование априорном информации о геометрии внешней среды значительно повышает надежность решения,

• Разработана грубо-точная процедура юстировки сте-рео-СТЗ для использования в естественных условиях. При этом значительные отклонения ориентации телекамер устраняются механически, а оставшиеся, неустранимые, учитываются программным путем.

Реализация результатов работы. Выполненные в диссертации исследования явились частью плановых работ, ведущихся в Государственный институте физико-технических проблем. Предложенные автором методы и алгоритмы обработки и анализа СТИ применены в разработках ГосИФТП и одного из институтов Министерства обороны России, а также использованы при создании пакета программ для ввода СТИ, юстировки стерео-СТЗ, обработки и анализа СТИ с получением модели внешней среды (МВС) и возможностью ее последующей визуализации. Практическое применение результатов работы подтверждено соответствующими документами.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на конференциях молодых ученых и специалистов ИФТП, на научных семинарах в ИФТП, а также прошли апробацию на IV и V Всесоюзных совещаниях по робототехническим системам (1987,1990), на Всесоюзной конференции по искусствен ному интеллекту (1988), на IV Всесоюзной конференцт "Математические методы распознавания образов" (1989) на Всероссийском семинаре "Механика и управление дви жением роботов с элементами искусственного интеллекта.' (1994, МГУ).

Публикации. По теме диссертации опубликовано 1' печатных работ, из них 3 работы без соавторов, имеете: изобретение. Список приведен в автореферате.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и двух приложений. Работа содержит 80 страниц текста, 36 страниц рисунков, список литературы включает 91 наименование работ.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Во введении обоснована актуальность проблемы машинного стереозрения и ее приложения для робототехники; отмечены особенности задачи для, транспортных роботов; сформулированы цели работы и исходные определения, основные положения, представляемые к защите, отражены вопросы практического использования полученных результатов и их апробации.

Первая глава- обзорная, в разделе 1.1 содержит постановку задач диссертационной работы. ,

Раздел 1.2 анализирует состояние проблемы и вклад отдельных составляющих машинного стереозрения в повышение его эффективности. Эффективное решение задачи определяется несколькими главными требованиями,-

это скорость, точность, надежность (объективность), вычислительные затраты, простота использования.

Подраздел 1.2.1 описывает способы получения СТй, а также ключевые параметры стерео-СТЗ и тип сцены при этом учитываемые. Также рассмотрены математические модели описания стереосистем. Описаны этапы процесса калибровки. Следующие критерии являются важными при проведении калибровки: точность; автономность, т.е. независимость от вмешательства оператора; требуемое время, определяемое размерностью решаемой задачи; многогранность, т.е. возможность использования для большого числа приложений; наличие специальных требований к камерам.

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

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

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

В подразделе 1.2.3 проанализированы основные подходы к согласованию стереоизображений.

Показано, что применение корреляционного метода связано со следующими основными трудностями: 1. Функция корреляции может иметь довольно размытый максимум, что затрудняет его обнаружение. 2. Шум на изображении может скрыть максимум корреляции. 3. Значительные вычислительные затраты.

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

Для повышения надежности отождествления целесообразно принять следующие меры: использование дополнительной информации о сцене; увеличение размерности пространства признаков, например использование цвета, выделение на изображении особых точек; использование последовательности СТЙ; интерактивное управление отождествлением; увеличение количества телекамер и много-стереопарные стерео-СТЗ.

В подразделе 1.2.4 рассмотрены определение декартовых координат отождествленных точек и восстановление по ним поверхности с помощью методов интерполяции, и вопрос представления результатов. Большой практический интерес имеет связь между параметрами стерео-СТЗ и точностью измерения координат. Показано, что повышение точности измерения координат может быть получено несколькими путями: попиксельная оценка параллак-

са, уменьшение интервала дискретизации при аналого-цифровом преобразовании сигнала телекамеры, увеличение базы стерео-СТЗ, увеличение фокусного расстояния телекамер, уменьшение расстояния до анализируемой сцены. увеличение числа точек, используемых при калибровке, проведение нескольких калибровочных измерений.

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

Во второй главе описан разработанный в [7] метод нахождения контурных признаков, учитывающий особенности формирования СТИ.

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

В разделе 2.1 рассмотрена проблема, связанная с воз-

действием помех на процесс получения изображений. В результате функция интенсивности /(ь.?) (дискретный аналог /(х, у)) есть сумма двух функций: идеального изображения д{{и шума г{ъ,])

/(»',» = + *(»',.?)• (1)

Обычно предполагается, что г есть гауссовский шум с нулевым средним значением и среднеквадратическим отклонением (Тг: г(0,аг) и для его сглаживания применяют локальное усреднение в окрестности точки.

В разделе 2.2 рассмотрено выделение одномерных признаков- контрастных перепадов интенсивности на строке.

Вычисление производной двумерной функции интенсивности на полосе шириной т элементов сводится к одномерному случаю, если предварительно произвести суммирование значений пиксел в поперечном направлении к базисной линии и определить функцию

1 »+т—1

Ш) = - £ Г(Р> Л (2)

р=»

Свертка, полученной функции /¿0) с функцией

<р(д) = <

-1 ,~l<q< 0

1 ,0<д<1 (S)

0 ,<7 < ~l,q > I

дает желаемый результат- разностную функцию d(j), представляющую собой производную для дискретного случая.

Критерий принятия решения о наличии перепада заключается в следующем:

| d(j) |> Т, sign d'(j) = -sign d'(j + 1), (4)

где в!{э)- производная функции

В разделе 2.3 рассмотрено применение методов функциональной аппроксимации при выделении пространственных признаков- контуров на двумерных областях.

В подразделе 2.3.1 дана общая постановка задачи для методов этого класса (оператор Хюккеля). Для реализации такого подхода, предложено использовать упрощенный оператор хюккелевского типа, основанный на аппроксимации в пространственной области N размером 2 х 2 [6]. Используется канонический базис

При вводе изображения использовалась прогрессивная развертка телевизионного растра, поэтому исходное изображение имеет прямоугольную форму 512 х 256 элементов. Для учета возникающих при этом геометрических искажений использовалась прямоугольная окрестность с соотношением сторон 2:1, обозначим составляющие ее элементы через Л, Ву С, Б. Решение задачи позволяет получить выражения

Область

0 < в < агс.1ап 2

агс(ап 2 < в < П

| < 0 < II - агЫап 2 П - агаап 2 < в < П

Решение

1 Цпв _ 1 2 ~ А-О

2со10-1 = |^ (5)

-(2со4 0+1) =

1 —

2 В-О '

которые можно решить относительно угла наклона контура в. Кроме того, перепад интенсивности в окне равен

, / А- Д 0 < 6? < "

В подразделе 2.3.2 рассмотрена локализация перепада функции интенсивности, чтобы повысить точность определения координат элемента контура,

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

В разделе 3.1 рассматривается отождествление признаков на соответственных фрагментах изображений, образующих стереопару [7]. В результате обработки полосы изображения рассмотренными выше алгоритмами получается последовательность (список) признаков. Каждый признак описывае тся вектором параметров 3; = (зм , • • •, 5,,).

Обозначим списки признаков, полученные с соответствующих друг другу полос изображения стереопары через з^ и Пусть список является эталонным и состоит из I элементов, а 8^- из 3 элементов. Задачей согласования является анализ этих списков с целью поиска соответствующих друг другу признаков по векторному критерию.

Пусть есть допустимое покрытие / первых: признаков списка г первыми признаками спискаДопустимое покрытие П есть любой разрешенный вариант установления соответствия между признаками на соответствующих полосах изображения. Правила установления соответствия между элементами изображений стереопары сформулированы Марром (1982). Так как не каждому признаку списка может быть найден соответствующий в списке то в процессе отождествления возможно отбрасывание какого-либо признака из эталонного списка. Таким обра-

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

Для конструктивного решения задачи многокритериального отождествления воспользуемся скалярным критерием- суммой нормированных частных критериев

I ТУ Г _ V""» Лтпь ]тп ~ 2_ А > * = 1 Лк

где /тп -обобщенный критерий несоответствия т-го признака списка п-му признаку списка, з^; НтПк — | — з^ | к-ый частный критерий; Аь = А'™Х—А™1П -амплитуда к-то частного критерия.

Поставим в соответствие каждому допустимому покрытию П^ (в дальнейшем просто покрытию) числовую меру образованную суммированием частных невязок /тп отождествленных признаков

= Лтт, т < г, п <

т,п

Так как г признаков в1-1^ имеют целое множество И покрытий на У признаках й^2', то возникает задача поиска оптимального покрытия П^ ' £ П, такого что

Здесь минимум ищется по всем допустимым покрытиям.

Оптимальное покрытие элементов одного списка признаков на другом, ищется на двумерной плоскости, для которой определяются матрицы оптимальных оценок Г =

(F°jPt) (далее просто Fu) и соответствия Т = (TtJ). Горизонтальные и вертикальные оси на плоскости образованы признаками, полученными с двух соответственных полос изображения стереопары. Пересечение вертикальных и горизонтальных линий образует узел, соответствующий текущему оптимальному покрытию, а также определенной стадии в процессе вычислений.

Для определения Fl} на каждом шаге решается функциональное уравнение

F,} = min(/fj + F,_ 1 i, /,о + Fi-1 j). (7)

при следующих начальных условиях

i

F0} - 0, Fi о = £/l0> r=T7,j = 1,J,

i=i

где Fij- минимальный суммарный критерий "несоответствия"; приращение суммарного критерия при отождествлении г-го признака списка s-1' с j-ым признаком списка s<~S'i /«о- приращение суммарного критерия при отбрасывании г-го признака списка s^ (штраф). Поэлементное соответствие между признаками, составляющими списки s^ и s(2), может быть получено путем обратного просмотра матрицы соответствия, начиная с элемента Tjj.

Вычислительные затраты для определения матрицы F ограничены выражением 0(1 х J), что значительно меньше, чем в методе, предложенном Охтой и Канаде (1985), где они оцениваются выражением 0{I2 х J2). Это присхо-дит потому, что для той же области поиска производится проверка только трех меньших покрытий, а не проверяются (I х J) возможных траекторий, ведущих в каждый узел.

В разделе 3.2 рассматривается задача согласования стереоизображения, ословыванная на. изложенном выше методе отождествления признаков с соответствующих полос. В результате обработки стереоизображения в направлении базиса съемки по ряду полос, каждое изображение стереопары может быть представлено двухярусным деревом [3]. Узлы нижнего яруса дерева соответствуют обрабатываемым полосам изображения, любой такой узел вместе с терминальными узлами представляет найденные контуры на текущей полосе изображения. Вершина дерева, вместе с ребрами, исходящими к узлам нижнего яруса, завершает описание всего изображения.

Обозначим деревья описаний, полученные после обработки изображения стереопары, через Б1^ и Пусть поддерево Б*-1'"^ образовано путем анализа п-ой полосы

первого изображения стереопары, п = 1, А\ и имеет /п тер-(х.п) --5—г~

минальных узлов 8> , г = 1 ,/Л) ооразующих список признаков, найденных на полосе. Соответственно, второе изображение, описываемое деревом имеет М поддеревьев

(3,т)

нижнего яруса, Sj - терминальные узлы т поддерева, 3 — 1, т = 1, М. Каждый из терминальных узлов »•1'п) и 8] ' имеет I листьев, соответствующих вектору па раметров признака.: й-, = , • • • , ) и =

Так как оба дерева описывают одну и ту же сцену представленную на изображениях стереопары, то возникает ¿-критериальная задача согласования деревьев с целые поиска соответствующих друг другу признаков. Предположим, что дерево Б1-1' выбрано в качестве эталон а, а дерево в^2) согласуется с ним. От алгоритма согласовали*

требуется устойчивость к вариациям структуры деревьев и искажениям параметров.

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

1. Отождествление узлов нижнего яруса и

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

2. Отождествление терминальных узлов (признаков)

(|,п) (2,ш) - лгцт

е- и в] определяется невязкой .

3. Отбрасывание терминального узла Любой терминальный узел может быть отброшен, что соответствует увеличению критерия на

Теперь определим меру отличия одного дерева от другого, для чего каждое из возможных наложений дерева Б1-1) на дереве

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

Дерево БО согласуется с Б1^ в определенной последовательности. Сначала согласуются поддеревья З^1'"^ и дС2.**1) нижних ярусов, что соответствует отождествлению контуров с полосы одного изображения на полосе другого изображения. Таблица согласования поддеревьев и Б1-2'1"1 создается с помощью рассмотренного выше ал-

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

Далее согласуются между собой поддеревья верхнего яруса. При этом заполняется только одна таблица согласования размером N х М. На каждом шаге решается следующее функциональное уравнение

Сат = + СЛ_! (8)

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

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

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

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

Сформулируем геометрическую модель на верхнем уровне обработки. При косоугольной сьемке, характерной для СТЗ транспортного робота, можно ввести гипотезу о подстилающей поверхности наблюдаемой сцены, в соответствии с которой на плоскости изображения (я, у) с уменьшением координаты у растет дальность до соответствующего элемента [5]. Для стереосистемы с вертикально ориентированным базисом это означает, что с увеличением координаты изображения у параллакс р(у) соответственных элементов, как правило, должен возрастать, т.е. р(у) общем случае можно считать неубывающей функцией:

dp/dy > 0. (9)

Для нижнего уровня обработки СТИ в качестве условия установления соответствия выбирается непрерывность параллакса. Это условие означает, что параллакс изменяется гладко почти везде, за исключением границ объектов, которые как раз и были определены на верхнем уровне обработки. Условие непрерывности можно формализовать как

I dp/dy |< const. (10)

Оно применяется при отождествлении отдельных пиксел, принадлежащих соответственным областям на СТИ.

В основе алгоритма лежит поиск оптимального покрытия элементов одного списка признаков на другом списке П^/, такого что доставляет минимум интегрального обобщенного критерия и одновременно удовлетворяет выбранной геометрической модели. Для этого вводится дополнительное измерение - текущий параллакс I, I = l,i, и для

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

Использование модели Я позволяет определить наиболее характерные особенности наблюдаемой сиены: ямы, возвышения, крупные препятствия. Такие данные особенно необходимы для навигации транспортного робота и управления его движением с обходом препятствий. Координаты. отождествленных контуров используются для определения координат точек рельефа. Образуемый этими точками профиль соответствует выбранной модели 12.

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

В четвертой главе рассмотрено автоматическое восприятие окружающей обстановки стереотелевизионной системой технического зрения транспортного робота.

В разделе 4.1 описана экспериментальная стерео-СТЗ на борту разведывательной машины. Приведены состав аппаратных средств и программа испытаний.

В разделе 4.2 описана юстировка стереотелевизионной системы технического зрения. Наличие линейных и угловых смещений оптической системы одной камеры относительно другой приводит к относительному сдвигу и повороту СТИ.

Использование упрощенного варианта метода согласования СТИ, позволяет осуществить автоматическую

- юстировку в направлении, ортогональном базису стерео-СТЗ, и определить значение поправки А (б1). Относительный сдвиг СТИ вдоль строк Д(■ф) (из-за конвергенции) приводит к необходимости введения постоянной поправки на параллакс соответствующих точек. Для определения Д(т/>) используется одна реперная точка.

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

В разделе 4.3 описан алгоритм обработки стереотелевизионных изображений. Положение контрастных перепадов на строке изображения определяется в точке изменения знака второй производной функции интенсивности, т.е. в точке ее нуль-перехода. Для их надежного выделения используется "беспороговый"дифференциальный обнаружитель контура [12], основанный на сравнении результатов обработки строк макропикселами разных размеров. В качестве параметров перепадов функции интенсивности <Дг, используются средние значения интенсивности а и 6 с разных сторон перепада.

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

рования для согласования найденных перепадов.

Координаты перепадов, найденных на соответственных полосах СТИ, и их параметры заносятся в списки 8(!) и 8(г). Каждый элемент з; из полученных списков, помимо его координат, описывается двумя параметрами интенсивности- а, и 6, - с одной и другой сторон от перепада. Из-за различия оптико-электронных характеристик телекамер и базового расстояния между ними, элементы списков и 31-2) необходимо скорректировать путем выравнивания средних значений интенсивности и контраста на изображениях стереопары [8].

Критерий несоответствия признаков /¿у получается суммированием частных критериев- невязок

и =141' - аТ I +1 ь'1' - ьТ I

Для каждого признака г из списка з^ и для каждого допустимого значения параллакса проверяются кандидаты иг списка признаков э^ не нарушающие выдвинутой гипотезы (9). При этом заполняется массив оптимальных оценок Г и массив соответствия Т, размерностью / X Ь х 7 Элементы которого характеризуют оптимальное покрытие подмножества г первых элементов списка на ; первых элементах при условии, что допустимая глу бина параллакса составляет I.

Для заполнения Г применяется аппарат динамическоп программирования, и на каждом шаге решается функцио нальное уравнение

Рц3 ~ 1тп(/ч + /¿,1^-15 /.о + С11

Pij=^

где Гц,- минимальный суммарный критерий "несоответ ствия" при условии, что проверяемые пары перепадов и

противоречат ранее рассмотренным парам, а глубина параллакса непревышает 1\ р^- параллакс между 1-ым и .7-ым перепадами, скорректированный на величину ртш.

Поэлементное соответствие между признаками, составляющими списки и может быть получено путем обратного просмотра матрицы соответствия, начиная с элемента Т\и. Вычислительная сложность алгоритма можно оценить выражением 0(1 X 3 X Ь).

В разделе 4.5 рассмотрен дихотомический алгоритм отождествления признаков, позволяющий существенно снизить вычислительные затраты. Допустим, что мы ставим своей задачей не получение сразу оптимального решения Г, а только разделение списка признаков на два подсписка, находящиеся на подстилающей поверхности ближе или дальше относительно какой-то точки р\, принадлежащей интервалу параллаксов Ь. Полученное решение является субоптимальным и служит основой для последующих вычислений. Таким образом, можно организовать дихотомический алгоритм согласования изображений на основе разделения списка признаков по принципу "ближе" или "дальше" выбранной точки на интервале параллаксов. Точки разбиения удобно выбирать посередине интервала параллаксов, на котором идет согласование. В результате вычислительная сложность понижается в ¿/4 раз.

В разделе 4.6 рассмотрен вопрос построение модели внешней среды. Вычисленные на предыдущем этапе параллаксы р отождествленных признаков, используются для определения координат точек рельефа X, К, Z:

л/ й „ В „ . В X = Хх—,У = г/1—, X = /р—,

где В- база стерео-СТЗ, /р-приведенное фокусное расстояние телекамеры, Х\, у\- координаты отождествленного признака в плоскости первого изображения. Полученные координаты точек рельефа используются для построения МВС в виде матрицы высот. После обработки изображений по всем заданным сечениям в матрицу будут занесены опорные значения высот, являющиеся исходными данными для интерполяции.

В разделе 4.7 приведена оценка точности измерения координат. Показано, что ошибка по дальности растет пропорционально ее квадрату и точность определения дальности (3%) обеспечивается только на расстояниях до 10-12 баз.

В разделе 4.8 описан пакет программ РОЬ200 для обработки и анализа стереотелевизионных изображений.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

Основные результаты и выводы состоят в следующем.

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

2) На этапе анализа СТИ отказ от поточечного отождествления и переход к отождествлению выделенных при знаков на. основе метода динамического программирова ния позволяет значительно снизить размерность и повы сить надежность решения. За счет применения подхода

основанного на получении оптимального покрытия при согласовании списков признаков, удалось также значительно снизить вычислительные затраты. Используя описание изображений стереопары в виде деревьев, был разработан алгоритм их согласования, что позволило отождествить признаки на всем СТИ. Данный алгоритм служит основой для процедуры юстировки стерео-СТЗ в направлении ортогональном базису. Компактная схема построения алгоритма позволяет при необходимости учитывать априорную информацию о геометрии внешней среды, что значительно повышает надежность отождествления.

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

4) Испытания стерео-СТЗ в условиях полигона показали удовлетворительное качество воспроизведения релье-

фа и полноту МВС. Стерео-СТЗ испытывалась также в качестве подсистемы в составе комплексной СТЗ. На относительно ровной поверхности с достаточной точностью и надежностью определялись расположение препятствий и их габариты (например, встречный автомобиль на дороге).

Результаты проведенных теоретических и экспериментальных исследований показали возможность создания стерео-СТЗ для различных научно-технических приложений. Испытания стерео-СТЗ для TP показали возможность его функционирования в условиях естественной среды при наличии препятствий.

Основные результаты диссертации опубликованы в следующих работых:

1. Иванюгин В.М. Ускоренный алгоритм обработки стереопарных изображений // Конф. мол. уч. и спец. ИФТП, депонент N-4004 от 29.10.87, "ИНФОРМПРИБОР".

2. Васильев В.Ф.,Иванюгин В.М.,Петухов C.B. Автоматический анализ изображений в стереотелевизионной системе транспортного робота// IV Всесоюзное совещание по робототехническим системам, г.Киев: Тез.докл.-Киев, 1987,4.2,С. 13-14.

3. Иванюгин В.М..Петухов C.B. Автоматическое отождествление контурных данных в стереотелевизионной системе технического зрения// Всесоюз. конф. по искусст. интел., тез. докл. М.,1988, Т.2,С. 155-160.

4. Васильев В.Ф.,Иванюгин В.М., Петухов C.B., Шаманов И.В. Определение параметров контуров в системе технического зрения// Научно-техн. конф. Разработка систем технич. зрения и их прим. в Промыш.- Тез.докл., Ижевск, 1988, С.31-32.

5. Иванюгин В.М.,Петухов C.B. Анализ стереотелеви-.

зионных изображений с использованием априорной информации о геометрии внешней среды //IV Всесоюзн. конференция Математические методы распознавания образов,-Тез. докл,- Рига,1989, Ч.4..-С.86-88.

6. Иванюгин В.М.,Петухов C.B. Использование оператора хюккелевского типа для определения параметров контуров в системе технического зрения // Сб.научн.тр. Исследование динамических свойств распределенных сред, М.:ИФТП,1989,С.145-153.

7. Васильев В.Ф.,Иванюгин В.М., Петухов C.B., Шаманов И.В. Автоматическое восстановление рельефа по результатам обработки стереотелевизионных изображений //Сб.научн.тр. Управление движением и техническое зрение автономных транспортных средств,- М.:ИФТП,1989,-С.121-149.

8. Васильев В.Ф.Дванюгин В.М.,Петухов C.B., Шаманов И.В. Быстрый алгоритм анализа СТИ для систем технического зрения// II Республик, семин. Проблемы создания систем обработки, анализа и распознавания изображений: Тез. докл.- Ташкент, 1989, Ч.-С.127-128.

9. Иванюгин В.М.,Петухов C.B. Проблемы реализации машинного стереозрения/Y Сб.науч.тр. Автономное управление и машинное зрение транспортных роботов.-М.:ИФТП,1990,-С.75-85.

10. Васильев В.Ф.,Иванюгин В.М.,Петухов C.B., Программное обеспечение для юстировки стереотелевизионной системы технического зрения// V Всесоюзное совещание по робототехническим системам, г.Геленджик, Тез.докл.-М.,1990,4.1,0.184-185.

11. Иванюгин В.М. Моделирование стереотелевизионной системы технического зрения // Сб.научн.тр. При-

кладные проблемы искусственного интеллекта, М.:ИФТП, 1991,0.48-55.

12. Иванюгин В.М. Беспороговый дифференциальный обнаружитель контура// Сб.научн.тр. Обработка динамической информации в интеллектуальных системах,-М.-.ИФТП,1992,-0.44-51.

13. Иванюгин В.М., Петухов C.B. Машинное стереозре-ние //Зарубежная радиоэлектроника, М.: Радио и связь, N-7,8,9, 1993, С.56-64.

14. Иванюгин В.М., Петухов C.B. Применение внутренней модели мира при анализе изображений в стереотелевизионной системе машинного зрения // Сб. научн. тр. Проблемы обработки информации в робототехнических системах.- М.: ИФТП. 1993, С.57-62.

Личный вклад автора. В работах [3,5,7,8,9,10] диссертанту принадлежит разработка методов отождествления признаков и юстировки стерео-СТЗ, в работах [2,4,6] имеет место неразделенное соавторство.