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

В общих чертах можно выделить три причины сложности задачи понимания изображения [1]:

1. Разнообразие яркостно-геометрических свойств изображения;

2. Изменчивость в изображениях;

3. Информационная поддержка процесса понимания сцен.

Причина 1: разнообразие яркостно-геометрических свойств изображения

В общем случае, это многообразие «…не имеет жёсткой причинной взаимосвязи, не вытекает из действия каких-либо физических законов, позволивших бы упростить модельное описание сцены наблюдения» [1].

В книге «Computer vision: models, learning and inference» приводится следующее утверждение, наглядно иллюстрирующее суть данной проблемы:

«In a camera, the three-dimensional world is projected onto the optical surface to form the image: a two-dimensional set of measurements. Our goal is to take these measurements and use them to establish the properties of the world that created them […] the relationship between world and measurements is generally many to one: there may be many real-world configurations that are compatible with the same measurements. The chance that each of these possible worlds is present can also be described using probability» [6].

Причина 2: изменчивость в изображениях

Причиной изменения могут быть освещенность, различные отклонения форм, размеров, искажения и шумы. Из-за трёхмерной природы сцены и объектов в ней возникает фактор загораживания объектов интереса. Объекты могут быть не только загорожены, но и развернуты в пространстве. Это выдвигает тяжелые требования устойчивости работы алгоритмов в трудных условиях [1].

В общем случае модель шума неизвестна.

Следующее утверждение иллюстрирует суть проблемы: «First, the measurement process is noisy; what we observe is not the amount of light that fell on the sensor, but a noisy estimate of this quantity» [6].

Также можно отметить, что:

«…Unfortunately, modeling the shape of an object is challenging; we must account for deformations of the object, the possible absence of some parts of the object and even changes in the object topology. Furthermore, the object may be partially occluded, making it difficult to relate the shape model to the observed data» [6].

Причина 3: информационная поддержка процесса понимания сцен

Для того, чтобы система технического зрения могла «понять изображение», она должна обладать соответствующей базой знаний об окружающем мире. Организация этой базы, её наполнение, актуализация - сложные задачи. Формирование подобной «базы» в сознании человека занимает годы [1].

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

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

1.3 Уровни анализа

Используются в основном медицинской радиологии и астрономических наблюдениях [1].

Рентгеновские изображения.

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

Ультрафиолетовые изображения.

Используются в производственном контроле, микроскопии, лазерной технике, медицинских и астрономических наблюдениях [1].

Инфракрасный диапазон (разбитый на тепловой ИК-диапазон и ближний ИК).

Изображения в тепловом диапазоне (8-14 мкм) позволяют пересчитывать интенсивность элементов изображения в значения температуры наблюдаемых поверхностей. Холодные объекты на таких изображениях будут более тёмными, теплыми - более яркими, горячие - «светящимися», поскольку нагревают и воздух рядом с собой. Изображения этого диапазона используются в системах промышленного и экологического мониторинга, выявляющих утечки тепла в различных технических устройствах, сетях теплотрасс и т.п.; в системах военного назначения для наведения на «горячие» объекты военной техники - двигатели, факелы ракет и т.п.; в биометрических системах, таких как системы автоматического контроля доступа на основе термограмм Термограмма - изображение в инфракрасных лучах, показывающее картину распределения температурных полей. человеческого лица, представляющих уникальные изображения, которые чрезвычайно сложно подделать. Для получений изображений в глубоком ИК-диапазоне используются специальные устройства - тепловизоры [1].

Изображения в ближнем ИК-диапазоне схожи с изображениями видимого диапазона, но съёмка в ближнем ИК позволяет снимать ночью. Т.о., сущесвтенной областью применений изображений ближнего ИК является ночное видение. Другая область применения ИК-систем - невидимая для человека ИК-подсветка, которую «видят» большинство современных видеокамер. ИК-прожекторы увеличивают общую ИК-освещенность сцены или объекта наблюдения, без создания дискомфорта для человека. ИК- и УФ-маркировка используется в системах контроля подлинности ценных бумаг [1].

Изображения видимого диапазона. Спектр видимого излучения - волны от 380 нм до 740 нм. Границы этого диапазона могут варьироваться в зависимости от индивидуальных особенностей зрения.

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

Микроволновые изображения.

Применяются в области радиолокации. Микроволновая съёмка используется в военной области, а также в области глобального мониторинга Земли из космоса и с авиа-носителей [1].

Радиоволновые изображения.

Используются в медицине и астрономии. Наиболее современный метод медицинских томографических изображений высокого разрешения ЯМР (ядерный магнитный резонанс) основан на регистрации радиволновых сигналов клетов человеческого тела, помещенных в сильное магнитное поле и возбуждаемых короткими волновыми импульсами в радиодиапазоне [1].

Акустические изображения.

Активно используются в геологии, промышленности и медицине [1].

Ультразвуковые изображения.

Применяются в промышленности и технике, а также в медицине (например, для нахождения паталогий различных внутренних органов человека). Медицинское ультразвуковое изображение содержит не только интенсивность отражённого ультразвукового сигнала, но и дальность до отражающей поверхности, вычисленную на основе расчёта скорости распространения ультразвукового сигнала в человеческих тканях [1].

Двумерные поля дальностей.

Формируются на основе анализа электромагнитных сигналов, испускаемых и принимаемых по локационной схеме. В качестве дальнометрических систем чаще всего используются лазерные локаторы, позволяющие осуществлять оптическое сканирование трёхмерных поверхностей с больших расстояний (до десятков километров), обеспечивая максимальное возможное разрешение. Локатор сканирует поверхность, испуская серии коротких волновых импульсов, отражения которых от поверхности объекта регистрируются приемником локатора, после чего рассчитывается время прохождения импульса до объекта и обратно, откуда окончательно определяется дальность до точки поверхности объекта. Получаемое изображение называется картой глубин [1].

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

Двухмерные поля скоростей.

Формируются аналогичным образом (как двумерные поля дальностей), однако их пикселы содержат уже не значения расстояний до соответствующих точек, а значения скоростей движения этих точек. Вычисление скоростей происходит на основе анализа доплеровского сдвига Доплеровский сдвиг - сдвиг частоты (и изменение длины волны) излучения, воспринимаемый приёмником, вследствие движения источника излучения и/или движения приёмника. отраженного сигнала. Данный тип изображений используется в системах различного назначения, чаще всего - в целях выделения движущихся объектов [1].

Проблема совмещения и анализа данных, полученных из разных источников, поднята в сборнике тезисов ТЗСУМО-2010 [3] и ТЗСУ-2015 [56] в работах, посвященных совмещению и анализу видеоинформации в системах комбинированного видения, а также совмещению разнородных изображений в бортовых системах.

1.5 Требования и задачи, предъявляемые к системам машинного зрения

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

· Калибровка сенсоров, самоориентация, самопозиционирование;

· Обнаружение объектов и изменений в сцене наблюдения;

· Слежение за объектами;

· Реконструкция поверхностей и обнаружение трёхмерных структур;

· Высокоточные измерения элементов сцены;

· Описание сцены и идентификация объектов;

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

Требования, предъявляемые к методам и алгоритмам машинного зрения [1]:

· Робастность

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

o Помехи и шум. Возникают как из-за внешних условий (недостаток освещения, тряска камеры, плохие погодные условий), так и из-за несовершенства сенсоров, дискретизации и пр.;

o Сложный текстурированный фон, на котором происходит обнаружение объектов;

o Эффекты загораживания одних объектов другими объектами;

o Искажающие оптические эффекты (расфокусировка, дисторсия объектива, ракурсные искажения и др.);

o Эффекты резкой смены освещения, блики, тени, динамически меняющиеся сцены;

o Разнообразие и изменчивость самих объектов. Например, это может быть переменная структура (автомобильные номера, штрихкоды, текстовые струки), дефекты, временные изменения формы (движение частей объекта) и т.п.;

o Эффекты изменения среды между сенсором и объектом наблюдения (задымление, осадки, пыль, искусственные помехи);

o Несинхронность регистрации и обработки данных в динамических задачах (в частности, вопрос быстродействия);

и т.д.

· Точность

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

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

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

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

· Вычислительная реализуемость

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

Выполнение требования реального времени является одной из основных задач области [32].

2. ОСНОВНЫЕ НАПРАВЛЕНИЯ И ПЕРСПЕКТИВНЫЕ РАЗРАБОТКИ ОБЛАСТИ КОМПЬЮТЕРНОГО ЗРЕНИЯ И СИСТЕМ ТЕХНИЧЕСКОГО ЗРЕНИЯ

2.1 Structure-From-Motion

Structure-From-Motion (SfM, построение структуры объекта по отображению движения Перевод взят из Big English-Russian Dictionary, 2012 г.) - технология реконструкции трёхмерной сцены на основе множества разноракурсных снимков и оценки положения и параметров их относительной ориентации [20].

На рисунке 2 проиллюстрирована постановка задачи SfM.

Рисунок 2 - Постановка задачи Structure-From-Motion

Одним из основных применений SfM является картография и восстановление 3D-моделей памятников культуры (cultural heritage) для последующего анализа их структуры (в том числе и для последующего их восстановления).

На рисунках 3,4 представлены результаты сшивки изображений в трёхмерную модель сцены, представленные на конференции ECCV'14 и ICCV'09 [20, 59, 9].

Рисунок 3 - Scene Chornology

Kevin Matzen, Noah Snavely. ECCV'14 [20, 9]

Рисунок 4 - Building Rome in a Day

ICCV 2009 [20, 9]

В общем случае данная задача сводится к оценке положения трёхмерных точек реальной сцены из их проекций на 2D-снимках этой сцены.

Multiple view geometry questions [21]:

· Scene geometry (structure): given 2D point matches in two or more images, where are the corresponding point in 3D?

· Correspondence (stereo matching): given a point in just one image, how does it constrain the position of the corresponding point in another image?

· Camera geometry (motion): given a set of corresponding points in two or more images, what are the camera matrices for these views?

Разберем поставленную задачу.

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

где - projection matrix, - 3D-points (см. рисунок 5).

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

Рисунок 5 - Задача нахождения соответствий между положениями реальных трёхмерных точек и их плоскими проекциями

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

2.1.1 SIFT (Scale Invariant Feature Transform)

Алгоритм в области компьютерного зрения, предназначенный для обнаружения и описания локальных признаков (характеристических точек) на изображении. Предложен в 1999 годом David Lowe. Приложения алгоритма включают в себя обнаружение объектов, построение карты и навигации роботов, сшивку изображений, распознавание жестов, отслеживание подвижных объектов и т.п.

Основной алгоритм [26] можно разделить на четыре этапа:

1. Scale-invariant feature detection Нахождение экстремумов по всем шкалам и точкам изображений. Реализуется путём вычисления разности Гауссовых функций, что позволяет находить потенциально интересные точки, которые инвариантны по отношению к растяжению и поворотам.

2. Локализация ключевых точек. В каждой точке, найденной в п.1, строится детализированная модель для уточнения положения ключевой точки и её размера.

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

4. Дескрипторы В контексте данной задачи - описательный элемент, инвариантный к изменению масштаба и поворота. ключевых точек. Локальные градиенты изображения измеряются по выбранной шкале в районе каждой ключевой точки. Эти данные преобразуются к виду, допускающему значительную степень изменения формы и изменения освещения. Для каждой ключевой точки строится дескриптор размером в 64 или 128 вещественных чисел.

В источнике [34] ключевые стадии приводятся как:

1. Scale-invariant feature detection;

2. Feature matching and indexing;

3. Cluster identification by Hough transform voting;

4. Model verification by linear least squares;

5. Outlier detection.

2.1.2 SURF (Speed Up Robust Feature)

Метод [26, 28, 29] разработан в 2008 году и является «ближайшим конкурентом» алгоритма SIFT. В алгоритме SURF для вычисления дескрипторов используются вейвлеты Вейвлет (wavelet - всплеск) - математическая функция, позволяющая анализировать различные частотные компоненты данных. График функции выглядит как волнообразные колебания с амплитудой, уменьшающейся до нуля вдали от начала координат. В общем случае анализ сигналов производится в плоскости вейвлет-коэффициентов (масштаб-время-уровень \ scale-time-amplitude). Вейвлет-коэффициенты определяются интегральным преобразованием сигнала. Полученные вейвлет-спектограммы принципиально отличаются от обычных спектров Фурье тем, что дают чёткую привязку спектра различных особенностей сигналов ко времени (материал взят с https://ru.wikipedia.org) Хаара (признаки Хаара, аналогичные используемым в простейших детекторах лиц, построенных на них, см. рисунки 6, 7).

Рисунок 6 - Признаки Хаара

(в фильтрах Хаара чёрные области имеют значения -1, белые +1)

Рисунок 7 - Вейвлеты Хаара, используемые для вычисления SURF-дескрипторов, и области, по которым они вычисляются

«Метод ищет особые точки с помощью матрицы Гессе. Гессиан В англоязычных источниках Hessian. функции - симметрическая квадратичная форма, описывающая поведение функции во втором порядке. Матрица этой квадратичной формы образована вторыми частными производными функции. Определитель матрицы Гессе называется определителем Гессе или гессианом» [26].

Если все производные существуют, то:

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

Градиент в точке вычисляется с помощью фильтров Хаара. После нахождения ключевых точек, SURF формирует их дескрипторы. Дескриптор представляет собой набор из 64 (либо 128) чисел для каждой ключевой точки. Эти числа отображают флуктуации градиента вокруг ключевой точки. Поскольку ключевая точка представляет собой максимум гессиана, то это гарантирует, что в окрестности точки должны быть участки с разными градиентами. Таким образом, обеспечивается дисперсия (различие) дескрипторов для разных ключевых точек» [26].

2.1.3 Сравнение эффективности методов SIFT и SURF

На рисунке 8 представлены результаты метода SIFT и его сравнение с результатами методом SURF. Метод SIFT дает больше характерных точек и более точную их локализацию, однако имеет более медленное исполнение.

Рисунок 8 - Сравнение результатов методов SIFT и SURF

(слева) пример фотографии, полученной при аэрофотосъёмке;

(справа) результат работы SIFT на данной фотографии;

(снизу) результат работы SURF на данной фотографии [26]

Время работы SIFT в 2.5 раза больше, чем время работы SURF, однако SIFT при этом находит больше точек [26]. Недостатки SURF проявляются на сильно размытых фотографиях [30,31], при сшивке разномасштабных фотографий и при смене угла обзора.

В общем случае алгоритм SIFT является более надежным, в то время как SURF - более быстрым.

2.1.4 Сопоставление точек интереса

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

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

В статье [34] приводится метод поиска примерного ближайшего соседа (finding fast aproximate nearest neighbors), удовлетворяющий данной задаче и условиям быстродействия (работает значительно быстрее, чем линейный поиск).

Алгоритм использует рандомизированые (randomized kd-trees) и иерархичные (hierarchical k-means tree) k-мерные деревья Также известны как рандомизированные деревья поиска. Дерево, в данном контексте, представляет собой иерархическую структуру данных, в которой каждый узел имеет не более двух потомков. Для двоичного древа поиска выполняются следующие дополнительные условия: 1. оба поддрева также являются двоичными деревьями поиска; 2. у всех узлов левого поддрева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X, а значения данных у всех узлов правого поддрева (того же узла X) больше, нежели значения ключа данных узла X.. Классический алгоритм для k-мерных деревьев [35] эффективен для малоразмерных пространств (low dimensions), но на пространствах большого размера быстро теряет в быстродействии.

Для обхода этой проблемы в 2008 году Silpha-Anan и Hartley предложили улучшенную версию этого алгоритма [36], который разбивает дерево на поддеревья, случайным образом, начиная с первых D измерений (dimensions, в работе [35] D принято равным 5) с наибольшей дисперсией.

Иногда сопоставляемые точки могут быть соотнесены некорректно, поэтому в алгоритмах SfM должна быть использована фильтрация сопоставлений (matches). Одним из алгоритмов для фильтрации точек является RANSAC [10] (Random Sample Consensus), который отсеивает «выпадающие» (outliers) из статистики точки.

2.2 SLAM (Simultaneous Localization and Mapping): метод одновременной навигации и составления карты

· EKF SLAM

· FastSLAM 1.0-2.0

· L-SLAM

· Graph-Based SLAM

· Occupancy Grid SLAM

· DP-SLAM

· PTAM (Parallel Tracking and Mapping)

· LSD-SLAM

Рассмотрим ряд из них.

2.2.1 EKF SLAM (Extended Kalman Filter SLAM)

Класс алгоритмов SLAM, использующих расширенный фильтр Калмана.

Впервые предложен в 1986 году Smith and Cheeseman [50], впервые разработан в рамках рабочей системы в 1989 году Moutarlier and Chaitila [51].

На рисунке 12 продемонстрирована упрощенная схема алгоритма EKF SLAM.

Рисунок 12 - Алгоритм SLAM с использованием EKF [24]

Процесс оценки состояния системы в контексте SLAM разбивают на [22]:

1. Обновление оценки состояния системы на основе одометрических данных;

2. Обновление оценки состояния системы на основе повторно обнаруженных ориентиров;

3. Добавление новых ориентиров в систему.

Расширенный фильтр Калмана (EKF) отличается от простого фильтра Калмана тем, что может быть использован в нелинейных процессах. Он позволяет не только уточнять оценку положения робота на карте, но и положение всех обнаруженных ориентиров. Тем не менее, EKF имеет серьезный недостаток в виде ограничения на количество обнаруженных ориентиров [22].

Как отмечается в работе Michael Monremerlo:

«While the EKF has become the dominant approach to SLAM, it suffers from two well-known problems that complicate its application in large, real-world environments: quadratic complexity and sensitivity to failures in data association» [49].

Для пояснения первой проблемы примем следующие обозначения [22]:

- оценка вектора состояния динамической системы в момент времени ;

- ковариационная матрица ошибок в момент времени .

Матрица ошибок имеет размерность , где - количество обнаруженных ориентиров. На каждом этапе обновления матрицы должен быть обновлен каждый её элемент, в связи с чем сложность алгоритма будет функцией от квадрата , т.е. [22].

«The first drawback of the EKF as a solution to the SLAM problem is computational complexity. Both the computation time and memory required by the EKF scale quadratically with the number of landmarks in the map. SLAM algorithms based on the full EKF generally do not scale beyond a few hundred landmarks. In contrast, reasonably large environment models might contain millions of features» [49].

Таким образом, EKF применим в ситуации, когда окружающая среда имеет небольшое (не более нескольких сотен) легко различимых ориентиров [22].

На рисунке 13 проиллюстрировано применение расширенного фильтра Калмана в задаче SLAM.

Рисунок 13 - EKF applied to a simulated data set [49]

Рассмотрим вкратце математически аппарат метода.

Состояние мобильного робота в произвольный момент времени можно представить с помощью вектора оценки его текущего местоположения и ковариационной матрицы [22] Прим.: рассматривается пример для 2D движения.:

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

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