Обзор современного состояния области компьютерного зрения

Состояние обнаруженных ориентиров (при условии, что они являются статическими) можно представить в виде вектора оценки их координат и ковариационной матрицы [22]:

где - количество ориентиров, обнаруженных роботом, - оценка координаты -го ориентира. По аналогии с матрицей матрица отражает меру зависимости оценки координат ориентиров друг от друга [22].

Общее состояние системы определяется вектором , отражающим оценки положения робота и ориентиров, и ковариационной матрицей :

где - ковариационная матрица размерностью , отражающая зависимость между оценкой координат робота и оценками положения ориентиров [22].

При инициализации фильтра задаются следующие значения по умолчанию [22]:

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

На следующем этапе происходит обновление оценки состояния системы на основе одометрических данных в EKF (этап предсказания), т.е. оценка состояния обновляется на основе состояния системы в предыдущий момент времени , модели движения и одометрических данных. Оценка состояния, полученная на этом шаге, будет неточна из-за ошибок одометрической системы робота и из-за его движения (например, проскальзывания колес). Используя ориентиры, можно компенсировать эту неточность. Имея две оценки состояния, полученные разным путём, можно вычислить рассогласование между ними и использовать его для уточнения параметров системы. Данный процесс повторяется для каждого ориентира в отдельности. По мере изучения местности могут быть обнаружены новые ориентиры, которые требуется добавить в систему на заключительном этапе оценки состояния системы. Эти действия также повторяются для каждого нового найденного ориентира [22].

Полную модель EKF SLAM в доступной форме можно найти в работе [22].

На этом моменте, с учётом постановке задачи выше, можно более развёрнуто пояснить проблему, возникающую в связи с большим количеством ориентиров:

«Quadratic complexity is a consequence of the Gaussian representation employed by the EKF. The uncertainty of the SLAM posterior is represented as a covariance matrix containing the correlations between all possible pairs of state variables. In a two-dimensional world, the covariance matrix contains entries, where is the total number of landmarks in the map. Thus, it is easy to see how the memory required to store this covariance matrix grows with . Moreover, since the correlations between all pairs of state variables are maintained, any sensor observation incorporated into the EKF will necessarily affect all of the other state variables. To incorporate a sensor observation, the EKF algorithm must perform an operation on every element in the covariance matrix, which requires quadratic time» [49].

Также существует и вторая проблема:

«The second problem with EKF-based SLAM approaches is related to data association, the mapping between observations and landmarks. The SLAM problem is most commonly formulated given known data association […] In the real world, the associations between observations and landmarks are hidden variables that must be determined in order to estimate the robot pose and the landmark positions» [49]

Т.е. принципиально неустраняемые систематические ошибки рано или поздно приведут к расхождению фильтра (will eventually cause the filter to diverge).

Данный алгоритм был актуален до появления FastSLAM, в последние десятилетия XX-го века.

2.2.2 FastSLAM

В 2002 году Montemerlo, Trun, Koller, и Wegbreit разработали новый подход к решению задачи SLAM. FastSLAM разделяет задачу локализации и картографии на множество подзадач, используя независимость состояния отдельных элементов модели SLAM [22, 49].

Также этот алгоритм можно встретить под названием Particle Filter SLAM, т.к. он использует в своей основе алгоритм Rao-Blackwellized Particle Filter.

Рисунок 14 иллюстрирует проблему SLAM как Байесовскую сеть Байесовская сеть (Bayesian network, belief network) - графическая вероятностная модель, представляющая собой множество переменных и их вероятностных зависимостей. Формально - это направленный ациклический граф, каждой вершине которого соответствует случайная переменная, а дуги графа кодируют отношения условной независимости между этими переменными. :

Рисунок 14 - The SLAM problem as Bayes Network [48, 49].

По отношению к EKF SLAM данный алгоритм имеет над ним два значительных преимущества [49]:

1. Эффективность и быстродействие:

«…by factoring the estimation of the map into in separate landmark estimators conditioned on the robot path posterior, FastSLAM is able to compute the full SLAM posterior in an extremely efficiently manner. The motion update, the landmark updates, and the computation of the importance weights can all be accomplished in constant time per particle. The resampling step, if implemented naively, can be implemented in linear time».

2. Снятие ограничения на количество ориентиров:

«…However, this step can be implemented in logarithmic time by organizing each particle as a binary trees of landmark estimators, instead of an array. The log(N) FastSLAM algorithm can be used to build a map with over a million landmarks using a standard desktop computer».

Робот перемещается из состояния в через ряд управляющих воздействий . В процессе движения робот наблюдает ближайшие ориентиры (landmarks) и (the positions of the landmarks are conditionally independent [49]). Измерения обозначены как . В разные моменты времени он может наблюдать одну из двух ключевых точек (прим.: в том числе и повторно).

«The SLAM problem is concerned with estimating the locations of the landmarks and the robot's path from the controls and the measurements . The gray shading illustrates a conditional independence relation» [48].

По сути, FastSLAM представляет собой реализацию Rao-Blackwellized Particle Filter (RBPF) [49, 52]. Точки окружения в данной задачи являются частицами для фильтра RBPF.

При каждом обновлении будет построено новое распределение частиц с учетом модели движения робота. Для частиц, у которых прогнозируемое фильтром RBPF значение совпадает (с определённой погрешностью) со значениями, измеренными на сенсорах, будут даны большие весовые коэффициенты. Повторный выбор частиц с созданием нового распределения основывается на весовых коэффициентах предыдущей выборки. Оценки ориентиров представлены 2х2 EKF (т.е., по сути fastSLAM базируется на EFK), но каждая частица в некоторой мере независима от других. Т.е., вместо определения относительного положения всех частиц сцены друг от друга, используется определение положения каждой частицы (из числа частиц M) относительно некоторого числа N определённых ориентиров.

Рисунок 15 показывает, как частицы (particles), обнаруженные методом будут привязаны к ориентирам (landmarks).



Рисунок 15 - There are M particles in the particle filter. Each particle contains N independent EKF's. No explicit cross-correlations are maintained between the landmark estimates [49]

Рисунок 16 показывает разницу в использовании больших (16.а) и малых (16.b) полей восприятия.

Рисунок 16 - Maps and estimated robot path, generated using sensors with (a) large and (b) small perceptual fields. The correct landmark locations are shown as dots, and the estimates as ellipses, whose sizes correspond to the residual uncertainty [48]

Среди проблем данной реализации SLAM можно отметить, что на больших расстояниях от начала координат карты серьезно возрастают ошибки (технически, решением этой проблемы может быть разбитие карты на несколько подкарт). Работа [55] иллюстрирует решение задачи ориентации робота в средах, имеющих большой масштаб (outdoor navigation): «self-localization of mobile robots in large-scale environments can be efficiently realized if a hybrid representation of the environment is used. The probabilistic approach presented here matches an incremental generalization of the traveled route with an integrated topological metric map, the route graph».

2.2.3 LSD-SLAM: Large-Scale Direct Monocular SLAM

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

«Direct methods. Direct visual odometry (VO) methods circumvent this limitation by optimizing the geometry directly on the image intensities, which enables using all information in the image. In addition to higher accuracy and robustness in particular in environments with little keypoints, this provides substantially more information about the geometry of the environment, which can be very valuable for robotics or augmented reality applications» [57].

Алгоритм (см. рисунок 17, 18) состоит из трёх основных компонент [57]:

· Отслеживание (tracking)

The tracking component continuously tracks new camera images. That is, it estimates their rigid body pose with respect to the current keyframe, using the pose of the previous frame as initialization.

· Оценка карты глубины (depth map estimation)

The depth map estimation component uses tracked frames to either refine or replace the current keyframe. Depth is refined by filtering over many per-pixel, small-baseline stereo comparisons coupled with interleaved spatial regularization […] If the camera has moved too far, a new keyframe is initialized by projecting points from existing, close-by keyframes into it.

· Оптимизация карты (map optimization)

Once a keyframe is replaced as tracking reference - and hence its depth map will not be refined further - it is incorporated into the global map by the map optimization component. To detect loop closures and scale-drift, a similarity transform to close-by existing keyframes (including its direct predecessor) is estimated using scale-aware, direct -image alignment.

В работе [11, 57, 58] ключевые кадры (keyframes) обозначаются как KF.

Рисунок 17 - LSD-SLAM. Алгоритм работы [58]

Рисунок 18 - Overview over the complete LSD-SLAM algorithm [57]

На рисунке 19 сопоставлены алгоритмы работы keypoint-based методов и direct (depth-based) метода LSD-SLAM.

Рисунок 18 - Разница между методами, основанными на поиске ключевых точек, и LSD-SLAM [58]



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

Впервые представленный в 2009-ом году, на 2015ый год [11] имеет реализацию в реальном времени на смартфоне. Также реализация LSD-SLAM имеет открытый код, представленный на сайте разработчика.

2.2.4 Техническое обеспечение для SLAM-навигации и перспективы метода

В настоящее время различные приложения SLAM-навигации могут работать с камерами 360-градусов (см. рисунок 19).

Большинство СТЗ для автономной навигации в трёхмерных сценах включают в себя множество небольших широкоугольных камер. На 2012-2015 год [20] уже достигнута калибровка и высокоточная 3D-реконструкция на основе камер типа «рыбий глаз».

Рисунок 19 - Towards real-time, dense tracking, reconstruction and scene understanding A. Davison, PCV'14 [59]

Среди перспектив SLAM можно отметить разработку object-level SLAM [20] со включением в алгоритм семантической сегментации сцены и навигации в ней на основе описания её объектного состава (рисунки 20, 21). На данный момент задача не может быть решена в реальном времени, поскольку требует больших вычислительных затрат. Текущие разработки идут в данном направлении.



Рисунок 20 - Towards real-time, dense tracking, reconstruction and scene understanding A. Davison, PCV'14 [20]

Рисунок 21 - Sliding Shapes for 3D Object Detection in Depth Images

Shuran Song, Jianxiong Xiao, ECCV'14 [20, 9]

2.3 Карты внимания (Saliency Maps, Карты Салиентности, Имитация зрительного внимания)

Большинство моделей визуального поиска (независимо от того, используют они участие явных движений глаз (overt eye movements) или смещение внимания (shifts of attention)), основаны на концепте карт зрительного внимания (saliency map, также переводится как карты салиентности) - явно заданных двумерных карт, которые кодируют салиентность Салиентность (saliency, «заметное положение», «выступающие детали») - здесь и далее будет использоваться как синоним зрительного внимания в контексте данной задачи. (saliency) или видимость (conspicuity) объектов в визуальном окружении [17].

«Visual saliency is the perceptual quality that makes an object, person, or pixel stand out relative to its neighbors and thus capture our attention» [16].

Как отмечается в работе L. Itti и C. Koch [17], ресурсы любой вычислительной системы ограничены, что ведет к эффекту «бутылочного горлышка» (bottlenecks), и зрение человека (как подобная система) не является исключением. Пропускная способность оптического нерва составляет порядка 10⁸ бит/c, что в разы превышает способность мозга полностью обработать поступающую информацию и перевести, интерпретировать её в сознательный опыт.

Как природа справляется с проблемой «бутылочного горлышка»? Наше зрение выбирает определенные порции входящей информации, которые являются более предпочтительными для обработки, смещая фокус с одной области на другую, проводя серию вычислений, вместо того, чтобы пытаться обработать всё сразу. Другими словами, несмотря на заблуждение, что мы видим всё, что нас окружает, в один момент времени наше зрение регистрирует и обрабатывает только небольшую порцию поступающей информации [17].

Краткий отчет [19] («Failure to detect changes to attended objects in motion pictures») о ряде экспериментов, проведенных Daniel T. Levin и Daniel J. Simons, является наглядной иллюстрацией этого факта.

Исследователи отмечают [19] неспособность людей обнаружить изменения объектов (или изменения в характеристиках этих объектов) в случае, когда localized retinal Retinal (ретинальный) - имеющий отношение к сетчатке. information signaling a change is masked or eliminated. Взрослые люди не замечают изменяющихся деталей (89 из 90 изменений проходят незамеченными) на видео, а в некоторых случаях не замечают изменений, которые происходят не только в случайно выбранной области (arbitrary location), но и в самом центре внимания (in a very center of attention) - например, когда актер на сцене превращается в другую персону путём мгновенной перемены угла обзора камеры (или «вырезания»).

На рисунке 22 представлены примеры карт внимания (фиксаций взгляда), полученных различными методами.

Рисунок 22 - Примеры карт внимания (фиксаций взгляда), полученных различными методами.

Карты, создаваемые большинством методов, имеют низкое разрешение [16]. Так, карты, созданные по методу Hou and Zhang (Xiaodi Hou, Liqing Zhang) [16, 13] имеют выходной размер 64x64 пикселя вне зависимости от размера входного изображения. Метод IT (Laurent Itti, Christof Koch) [16, 17] дает карту внимания размером в 1/256 от входного изображения. Одним из исключений является алгоритм Achanta, который производит карту вниманию равноценного размера, как и исходное изображение.

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

· IT-method for Saliency Maps;

· Temporal and Local Methods for Saliency Maps;

· Global Methods for Saliency Maps (SR-, PFT-, PQFT-);

· Context-Aware Saliency Detection.

2.3.1 IT-method

Проиллюстрируем построение карты салиентности (карты внимания) на основе модели (рисунок 23), впервые предложенной в 1998 году L. Itti и C. Koch (IT-method). На данном примере можно рассмотреть основные принципы создания карт, используемую в указанной области терминологию и эффективность.

Рисунок 23 - A model of Saliency-Based Visual Attention

for Rapid Scene Analysis [17, 18]

Первый уровень (visual preprocessing, предварительная визуальная обработка) модели представлен следующим образом (см. рисунок 24) [18]:

Рисунок 24 - Visual Preprocessing [18]

Intensity image (карта интенсивности) получается из значений цвета (RGB) как:

где - цветовые компоненты входного изображения.

Для каждого пикселя в пирамиде генерируется цветовой канал:

Наравне с «традиционными» (RGB) каналами генерируется «жёлтый»:

Негативные значения приравниваются к нулю.

Определим цветовую оппозицию как:

The detection of local orientation at each point in the image is achieved using overcomplete steerable filters O [18].

Следующий уровень модели [18] представлен как показано на рисунке 25:

Рис 25 - Center-surround differences [18]

Вычислим различия между «центром» и «окружением» (center-surround difference), чтобы определить контраст, следующим образом. Возьмем разницу между точной шкалой (fine scale), принимаемой за «центр» (center), и грубой шкалой (coarse scale), принимаемой за «окружение» (surround), для указанного признака (feature). Эта операция проводится путем применения интерполяции к точной шкале и последующим вычитанием точка-за-точкой (point by point subtraction) [18]:

где

Нормализация () на этом уровне будет иметь вид, показанный на рисунке 26. Карта интенсивности и карта ориентации, выраженные в произвольных единицах (arbitrary units) после нормализации будут иметь вид как в правой части рисунка.

Рисунок 26 - Normalization [18]

На этом этапе [18]:

1. Нормализуются значения в карте в фиксированном диапазоне в целях устранения модально-зависимых разниц в амплитудах (modality-dependent amplitude differences);

2. Находится местоположение глобального максимума карты (map's global maximum) и вычисляем среднее значение для всех прочих локальных максимумов (other local maxima);

3. Вся карта умножается на .

Следующий уровень [18] выглядит как показано на рисунке 27:

Рисунок 27 - Across-scale combinations and normalization

Conspicuity maps (карты заметности) строятся следующим образом [18]:

Т.е. карты признаков комбинируются в три карты заметности в масштабе 4 (at the scale 4). This is obtained through across-scale addition by reducing each map to the lowest resolution (scale 4) and point-by-point addition [18].

В конце схемы мы имеем следующий вид (рисунок 28):

Рисунок 28 - Saliency map model end [18]

Три карты заметности (полученные на предыдущем шаге) нормализуются и суммируются на финальном выходе в карту внимания (салиентности) [18]:

Иллюстрация работы модели приведена на рисунке 29.

Входное изображение приходит полноцветным в разрешении 512x384. Карты заметности (контраст интенсивности, контраст цвета, контраст ориентации) получаются в масштабе 4 (32x24), как и итоговая одиночная карта внимания. На выходе нейронный алгоритм (neural winner-take-all network Winner-take-all algorithm - принцип «Победитель получает всё». Применяется в искусственных нейросятях при осуществлении принятия решений и задач классификации. Решением считается такая альтернатива, у которой выходное значение соответствующего нейрона является максимальным. Является случаем конкурентного обучения в реккурентных нейросетях. Выходы в сети взаимно запрещают одновременную активизацию нескольких узлов посредством рефлексивных связей. После некоторого времени только один узел в слое будет активным, а именно тот, который соответствует самому сильному выходы. В ряде практических случаев принцип формируется как «k победителей получают всё».) успешно выделяет, в порядке убывающей салиентности, присутствующие локации [17].

Рисунок 29 - Example of the working model [17]

Касательно предложенной модели можно выделить следующие моменты [18]:

· Модель салиентности предоставляет полезный алгоритм сопровождения зрения в потенциально значимые части сцены;

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

· Салиентность ограничена простыми чертами;

· Внимание определяется исключительно как выбор области в пространстве (без непрямого выделения, основанного на признаках, или только с ним);

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

2.3.2 Temporal and Local Methods for Saliency Maps

Рассмотрим на примере, приведенном в работе «Weighted-MSE based on Saliency map for assessing video quality of H.264 video stream» [13].

Процесс извлечения временной карты внимания выглядит как показано на рисунке 30.

Рисунок 30 - Temporal saliency map extraction process [13]

Рассмотрим извлечение на примере обработки видеопотока в формате H.264. Исходный кадр видео показан на рисунке 31.

Рисунок 31 - Исходный кадр видео [12]

Для каждого пикселя -го кадра считается значение оптического потока (optical flow) и строится поле векторов . После этого оценивается глобальное движение (global motion) [13].

Остаточное движение (residual motion) считается по формуле:

Получившаяся карта показана на рисунке 31.

Рисунок 31 - Карта до фильтрации [12]

Известно, что человеческий глаз не успевает следить за движением, скорость которого превышает 80°/c. Визуальная салиентность достигает максимума, когда значение движения находятся в интервале 6°/c ч 30°/c. Значения ниже 6°/c также не будут нас интересовать.

Таким образом, фильтрация будет производиться следующим образом [12]:

После фильтрации временная карта будет выглядеть следующим образом (см. рисунок 32):



Рисунок 32 - Временная карта внимания после фильтрации [12]

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

Локальные методы представляют собой пространственно-временной алгоритм. Для каждого кадра строится пространственная карта. После строится временная карта. После, путем их объединения (не сложения), получается локальная карта.

Для пространственной карты суммируются 7 характеристик [13]:

· контраст насыщенности (saturation contrast)

· контраст яркости (intensity contrast)

· контраст оттенка (hue contrast)

· контраст противоположных цветов (opposite color contrast)

· контраст теплых и холодных цветов (warm and cold color contrast)

· доминирование теплых цветов (dominance of warm colors)

· доминирование яркости и оттенка (dominance of brightness and hue)

Формула выглядит следующим образом [12, 13]:

После этого [13] нормализуется между 0 и 1 в соответствии с максимальным его значением :

Получили пространственную (spatial) карту внимания (см. рисунок 33).

Рисунок 33 - Построение пространственной карты внимания [12]

«In the literature, the common fusion method is the sum of the temporal and the spatial saliency map weighted by a 2 dimensional Gaussian centered at the centre of the frame» [13]. Перемножив пространственную и временную карту внимания с двумерными гауссовскими весами [12], получаем локальную карту салиентности (рисунок 34):

Рисунок 34 - Локальная карта внимания [12]

Можно усовершенствовать этот метод: «…we propose an enhanced method to extract the temporal saliency map which takes advantage of the H.264 compressed stream and a new fusion method» [13], чтобы извлекать пространственно-временную карту внимания из частично декодированного H.264 видеопотока.

Новый метод слияния (fusion method) использует [13] следующую формулу:

где .

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

Данный метод помогает [13] устранить артефакты передачи видеоданных (video transmission artifacts) в тех зонах, где они будут наиболее раздражающими.

2.3.3 Global Methods for Saliency Maps (SR-, PFT-, PQFT-)

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

Рассмотрим некоторые из них.

1. SR-method (spectral residual approach method) [12, 14]

Метод предложен Xiaodi Hou and Liqing Zhang [14], Department of Computer Science, Shanghai Jiao Tong University, 2007 г.

Проведем следующие вычисления [12, 14]:

Где - спектр амплитуд [12] (amplitude of the averaged Fourier spectrum of the ensemble of natural images) [14];

- преобразование Фурье [12];

где - спектр фаз изображения (phase spectrum of the image, which is preserved during the process) [14].

где - логарифмический спектр изображения (log spectrum representation of an image) (рисунок 35).

Рисунок 35 - Исходное изображение и [12, 14]

Построим остаточный спектр путём следующих вычислений [12]:

где - averaged spectrum (не путать с ) (также обозначен как shape information [14])

- матрица размера , которая находится как:



Остаточный спектр находится как:

где - остаточный спектр изображения (spectral residual of an image) «…denotes the statistical singularities that is particular to the input image» (рисунок 36).

Строим карту внимания (рисунок 37):

где - гауссовский фильтр (Gaussian filter) c ;

- обратное преобразование Фурье (Inverse Fourier Transform).

Рисунок 36 - The shape information is removed from original log spectrum.

The uniform distribution of spectral residual is desirable since similar response is expected in the neural representation of images.

(left) , (right) [14]



Рисунок 37 - Карта внимания

В сравнении с IT-методом дает следующие результаты (см. таблицу 1).

Здесь: HR - Hit Rate (количество верных срабатываний), FAR - False Alarm Rate (количество ложных срабатываний).

Таблица 1 - Сравнение SR- и IT-методов [14]

	Spectral Residual (SR)	Itti's Method (IT)
HR FAR = const	0.4309 0.1433	0.2482 0.1433
HR = const FAR	0.5076 0.1688	0.5076 0.2931
Total Time	4.014s	61.621s

Таким образом, SR-метод показывает значительно большую эффективность в сравнении с IT-методом (больше число верных срабатываний, меньшее число ложных срабатываний, больше скорость обработки).

2. PFT и PQFT [12, 15]

PFT-метод использует только фазовые характеристики, работает быстрее SR и имеет временную реализацию. На рисунке 38 показана реконструкция сигнала по спектру фаз, представленная в работе [15].



Рисунок 38 - Реконструкция сигнала по спектру фаз. (left) One-dimension data examples. Original data; (right) Reconstruction only by the phase spectrum [15]

Возьмем изображение .

Следующими вычислениями для PFT мы получаем:

где и обозначают прямое и обратное преобразование Фурье, - представляет собой спектр фаз изображения [15], - 2D-гауссовский фильтр с (тот же, что и в SR-методе):

PQFT-метод позволяет более лёгким путем получить пространственно-временную карту. Вычисления для него можно найти в источнике [15].

На рисунке 40 приводится сравнение результатов различных методов. Более подробно их также можно найти в источнике [15].

Рисунок 40 - Сравнение результатов различных глобальных методов на изображениях [12, 15]

2.3.4 Context-Aware Saliency Detection

Одним из методов, основанных на правилах организации сцены, является метод Context-Aware Saliency Detection (CASD), предложенный Stas Goferman, Lihi Zelnik-Manor и Ayellet Tal [62]. На рисунке 41 - сравнение различных подходов к построению карт зрительного внимания, приведенное в работе [62].

Рисунок 41 - Comparing different approaches to saliency [62]

Здесь авторы формулируют основную проблему построения карты внимания следующим образом:

«Local-global single-scale saliency. There are two challenges in defining our saliency. The first is how to define distinctiveness both locally and globally. The second is how to incorporate positional information» [62].

Основные моменты метода можно сформулировать следующим образом [12]:

· Важны не только объекты, но и часть их окружения, передающая суть изображения;

· Салиентные пиксели должны быть сгруппированы вместе, а не разбросаны по всему изображению;

· Несалиентные области могут находиться как рядом, так и далеко друг от друга.

Авторы метода [62] выводят следующие принципы: «Our context-aware saliency follows four basic principles of human visual attention, which are supported by psychological evidence:

1. Local low-level considerations, including factors such as contrast and color;

2. Global considerations, which suppress frequently occurring features, while maintaining features that deviate from the norm;

3. Visual organization rules, which state that visual forms may possess one or several centers of gravity about which the form is organized;

4. High-level factors, such as human faces».

Рассмотрим математический аппарат CASD-метода.

Рассмотрим патч (patch) размером вокруг каждого пикселя .

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

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

Обозначим Евклидово расстояние между положениями патчей: .

Мера похожести между парой патчей будет [12]:

Для каждого патча в изображении проводится поиск самых похожих на него патчей . Значение салиентности пикселя при размере [12]:

При однородном или размытом фоне удобно использовать патчи разных размеров: «Multi-scale saliency enhancement. Background pixels (patches) are likely to have similar patches at multiple scales, e.g., in large homogeneous or blurred regions. This is in contrast to more salient pixels that could have similar patches at a few scales but not at all of them. Therefore, we incorporate multiple scales to further decrease the saliency of background pixels, improving the contrast between salient and non-salient regions» [62].

Патч сравнивается с патчами-кандидатами со всего изображения [12]:

Шаги алгоритма сравнения приведены на рисунке 42.

Рисунок 42 - The steps of saliency estimation algorithm [62]

На рисунке 43 приведены результаты сравнения CASD-метода с локальными и глобальными методами, рассмотренными ранее.

Рисунок 43 - Comparing saliency results on images of a single object over and uninteresting background [62]

2.4 Свёрточные нейронные сети (Convolution Neural Networks)

Свёрточная нейронная сеть (Convolution Neural Network, CNN) - это специальная архитектура искусственных нейронных сетей, предложенная Яном Лекуном в 1998 г. и нацеленная на эффективное распознавание изображений [37]. Данная архитектура сети также известна как LeNet.

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

В 1981 году нейробиологи Торстен Визел и Девид Хабел исследовали зрительную кору головного мозга кошки и выявили, что существуют так называемые «простые клетки», которые особенно сильно реагируют на прямые линии под разными углами, и «сложные клетки», которые реагируют на движение линий в одном направлении [38]. Ян Лекун предложил специальную архитектуру искусственных нейронных сетей, представляющую собой упрощённый аналог зрительной коры головного мозга для распознавания изображений. Название архитектура получила из-за наличия операции свёртки. Идея CNN заключается в чередовании свёрточных слоёв (convolution layers) и слоёв подвыборки (subsampling layers, также субдискретизирующих). Структура сети однонаправленная, принципиально многослойная. Функция активации нейронов выбирается исследователем. Для обучения используются стандартные методы, чаще всего метод обратного распространения ошибки Этот метод наиболее распространен, поскольку является самым простым и хорошо изученным, но для CNN с большим количеством слоев не всегда эффективен, поэтому нередко используются и другие методы, в том числе и «без учителя», когда обучение на примерах происходит только на первом слое, а последующие слои обучаются за счёт частичных выборок с предыдущих.. Хотя большинство реализаций CNN проходят обучение с учителем, также существует ряд техник (например, patch-based training) обучения без учителя [39].

Рисунок 44 демонстрирует пример архитектуры сети, используемой для распознавания рукописных знаков

Рисунок 44 - Пример архитектуры CNN [37]

CNN входит в состав технологий глубокого обучения (deep learning Глубинное обучение (Deep learning) - набор алгоритмов машинного обучения, которые пытаются моделировать высокоуровневые абстракции в данных, используя архитектуры, состоящие из множества нелинейных трансформаций. Под термином «глубина» в данном случае понимается глубина графа вычислений модели - максимальная длина между входным и выходным узлами конкретной архитектуры. Термин «deep learning» акцентирует внимание на сложности обучения внутренних (глубоких) слоев многослойной сети, которые плохо поддаются классическим методам обучения, таким как метод обратного распространения ошибки (ru.wikipedia.org/wiki/Глубинное_обучение)) и на данный момент считается одним из лучших алгоритмов распознавания и классификации изображений [37].



2.4.1 Арихитектура CNN

В CNN в операции свёртки используется ограниченная матрица весов небольшого размера - ядро свёртки, которое двигают по всему обрабатываемому слою (в самом начале - непосредственно по входному изображению). Т.е. для различных нейронов выходного слоя используются общие веса [37], в отличие от классической нейронной сети, в которой каждый нейрон выходного слоя связан с каждым нейроном входного слоя (на первом слое: с каждым пикселем изображения). Таким образом, количество настраиваемых коэффициентов уменьшается в разы, возрастает скорость обучения и работы сети. Также, это позволяет избежать попиксельного запоминания примеров, и обеспечивает инвариантность к смещению [39].

Ядро свёртки строится таким образом, чтобы графически кодировать конкретный признак - например, наличие на изображении наклонной линии под определенным углом. Следующий слой (слой свёртки), получившийся в результате операции свёртки, представляет собой карту признаков (feature map). Она показывает наличие и координаты данного типа линий в обрабатываемом слое. Таким образом, каждая карта признаков, по сути, фильтрует предыдущий слой на наличие в нём «своего» признака - различных типов линий, дуг, кругов, пятен и так далее. Ядер свёртки в CNN целая гамма, кодирующая всевозможные линии и дуги под разными углами. Эти ядра свёртки формируются самостоятельно путём обучения сети, например, классическим методом распространения ошибки. Проход каждым набором весов формирует свой собственный экземпляр карты признаков, делая нейронную сеть многомерной (на одном слое присутствует много независимых карт). При переборе слоя матрицей весов её передвигают обычно не на полный шаг (размер этой матрицы), а на небольшое расстояние, чтобы не пропустить искомый признак [37].

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

В упрощённом виде этот слой описывается как [44]:

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

Каждая операция свёртки уменьшает размер карты признаков [39]. На примере выше (см. рисунок 44) на входное изображение 32х32 первая операция свёртки дала 6 карт признаков размером 28х28. После выполнения операции свёртки сеть теряет часть информации о точном положении найденного признака, сохраняя информацию о взаимном расположении различных признаков [38].

Свёрточный слой имеет несколько ядер свёртки. Для выполнения последующих свёрточных слоёв карты признаков этого слоя суммируются [44]:

где - карта признаков (выход -го слоя), - функция активации, - коэффициент сдвига для карты признаков на -м слое, - ядро свёртки номер , - карты признаков предыдущего слоя.

Одной из особенностей слоёв свёртки является тот факт, что при сдвиге входного изображения значения карт признаков будут сдвинуты на ту же самую величину, за счёт чего свёрточные сети обладают инвариантностью к сдвигам и незначительным искажениям входного сигнала [39, 40].

Операция субдискретизации (или операция подвыборки, subsampling) выполняет уменьшение размерности сформированных карт признаков. В данной архитектуре сети считается, что информация о факте наличия искомого признака важнее точного знания его координат, поэтому из нескольких соседних нейронов карты признаков выбирается максимальный и принимается за один нейрон карты признаков меньшей размерности (подвыборка может проводиться и другими методами) [37].

Субдискретизирующие слои (подвыборки) выполняют уменьшения размера входной карты признаков (обычно в 2 раза). Это можно делать различными способами, например, методом выбора максимального элемента (max-pooling). Использование этого слоя позволяет улучшить распознавание образцов с изменённым масштабом (увеличенных или уменьшенных) [44].

Размер ядра свёртки также иногда называется рецептивным полем нейрона [39, 40]. Его ширина и высота должны быть нечётными числами, чтобы обеспечить попадание нейрона слоя свёртки в центр рецептивного поля nЧm [39]. Так, каждый нейрон карты признаков будет получать входные данные от прямоугольной области предыдущего слоя.

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

Метод выбора максимального элемента (max-pooling) - вся карта признаков разделяется на ячейки 2х2 элемента, из которых выбираются максимальные по значению. Формально слой может быть описан следующим образом [44]:

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

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

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

Представленной ниже сети достаточно для распознавания рукописных цифр.

Рисунок 45 - Структура свёрточной нейронной сети, имеющей три скрытых слоя и не имеющей субдискретизирующих слоёв [39]

CNN с тремя парами слоёв свёртки-подвыборки вполне достаточно для точного распознавания лиц людей [38, 41]. Рисунок 46 демонстрирует вид многоуровневой сети, используемой для обнаружения и распознавания выражения лиц [42].

Рисунок 46 - Face Detection by proposed convolutional NN with the results of intermediate feature detection [42]

Подбор оптимальных для решения задачи размеров «окна» (поля) является одной из проблем построения CNN. С одной стороны, небольшие значения размеров «окна» повышают разрешающую способность сети - мы можем искать небольшие признаки на изображении. С другой стороны, аналогичный признак большего масштаба будет пропущен или принят за совокупность других признаков. Таким образом, CNN плохо работает с изображениями, на которых могут присутствовать одинаковые признаки различного масштаба. Существуют различные способы решения данной проблемы. В одном из них предлагается использовать в одном слое карты признаков с разными размерами окна при одинаковом размере карты признаков. Это позволяет находить признаки разного размера одновременно в первом слое подвыборки, что повышает общее качество распознавания объектов, ускоряет обучение нейросети, способствует уменьшению количества карт признаков в последующих слоях сети, что приводит к уменьшению потребления памяти [38].

На выходе CNN часто дополнительно устанавливают классический персептрон, на вход которому подаются оконченные карты признаков [37]. В ряде источников [38, 39] он также обозначается как полная связь (full connection). Полносвязанные слои, в которых каждый нейрон текущего слоя соединен со всеми нейронами предыдущего, используются как слои классификации [39].

Последний слой - многослойный персептрон (MLP), в общем виде описывается как [44]:

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

Стоит отметить, что в некоторых случаях MLP-слой может быть расположен не только на выходе свёрточной сети, но и являться её частью (чередоваться со слоями свёртки и подвыборки) [46].

2.4.2 Достоинства и недостатки свёрточных нейронных сетей

Среди достоинств CNN можно отметить:

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

· Использование ядер свёртки также помогает избежать попиксельного запоминания, подталкивая сеть к обобщению демонстрируемой информации [37]. Локальное восприятие позволяет сохранить топологию изображения от слоя к слою при значительном сокращении вычислений. Благодаря сканированию целой области, а не отдельных точек, подход позволяет учесть свойства изображения, что увеличивает качество распознавания [45].

· Робастность алгоритмов к повороту и сдвигу [37, 39].

· Частичная инвариантность к масштабу за счёт субдискретизации [45].

· Обучается при помощи классического метода обратного распространения ошибки, при этом могут быть задействованы и другие методы обучения сети (в том числе и методы «без учителя», например, patch-based training, когда следующий слой свёртки обучается на кусочках уже обученного первого слоя). Также могут быть задействованы другие технологии глубокого обучения: свёрточный авто-ассоциатор, свёрточная версия каскадных машин Больцмана, обучающихся за счёт математического аппарата, свёрточная версия разреженного кодирования (sparce coding), также известная как развёртывающая сеть (deconvolutional networks, DNN) [37].

Недостатками CNN являются:

· Продолжительное время обучения (несколько дней и более) для нейронной сети с числом слоёв свёртки свыше двух [43]. Классификатор рукописных символов обучался более 64 часов [44].

· Необходимость в большом количестве примеров для обучения. Реализация классификатора рукописных символов использовала базу MNIST, которая содержит более 60 тысяч учебных образов с цифрами от 0 до 9 различного начертания [44].

· Пригодна, по большей части, только для распознавания изображений [37].

· Большая вероятность переобучения сети при недостаточном количестве примеров при обучении с учителем.

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



2.4.3 Deconvolutional Neural Network (DNN)

Мэттью Зайлер [46] разработал концепцию и технологию DNN для понимания и анализа свёрточных нейронных сетей. Эта технология осуществляет построение иерархических представлений изображения (см. рисунок 47) с учётом фильтров и параметров, полученных при обучении свёрточной нейросети. Эти представления могут быть использованы как для решения задач первичной обработки сигналов (таких как шумоподавление), а также могут обеспечивать низкоуровневые функции для распознавания объектов.

Рисунок 47 - Представления изображений [46]

Также может быть известная как свёрточная версия разрежённого кодирования (sparce coding) [37].

Входной сигнал представляется в виде суммы свёрток карт признаков с учётом применяемых фильтров. Для исследования CNN, DNN прикрепляется к каждому из её слоев, как показано на рисунке 48, обеспечивая непрерывный путь от выходов сети к пикселям изображения на входе [46].

Сначала над входным изображением выполняется операция свёртки и по всем слоям вычисляются карты признаков. Для дальнейшего изучения поведения CNN устанавливаются значения весов всех нейронов в слое равными нулю. Полученные карты признаков используются в качестве входных параметров прилагаемого слоя развёртки (deconvent layer).

Далее последовательно выполняются три операции [46]:

· Разъединение (Unpooling);

· Ректификация (Rectification);

· Фильтрация (Convolutional Filtering).

Операция разъединения (unpooling):

В CNN операция объединения Прим.: в источнике [46] подразумевается max pooling операция слоя подвыборки. является необратимой. Тем не менее, можно получить приближенное обратное значение путём записи местоположения максимумов в пределах каждой области. Операция разъединения использует изменения в наборе переменных, размещённых слоем выше, в соответствующих местах текущего обрабатываемого слоя [46].

Рисунок 48 - Процесс исследования CNN с использованием DNN [46]

Операция ректификации (rectification):

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

Операция фильтрации (Convolutional Filtering):

Чтобы понять, какие фильтры были применены к изображению, deconvent layer использует транспонированные версии тех же фильтров. Проектирование «спуска вниз» с более высоких уровней использует изменения параметров, полученных при обучении CNN. Поскольку эти изменения свойственны данному входному изображению, реконструкция, полученная из одной функции, напоминает кусочек начального изображения со структурами, взвешенными в соответствии с их вкладом в карту признаков (см. рисунок 49) [46].

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

Рисунок 49 - Структуры изображения [46]

Преимущества [46]:

· Концептуально простая схема обучения. Обучение DNN производится за счёт использования разъединения, ректификации и фильтрации, при этом используются карты признаков, полученные ранее при обучении CNN;

· Применяя DNN к исходным изображениям, можно получить большой набор фильтров, которые охватывают всю структуру изображения, используя примитивные представления; Таким образом, получаются фильтры, применяемые ко всему изображению, а не к каждому маленькому кусочку исходного изображения. Это является большим преимуществом, так как появляется более полное понимание процессов, происходящих при обучении CNN;

· Представления можно получить без настройки особых параметров или дополнительных модулей, таких как разъединение, ректификация и фильтрация. Они, представления, получаются в ходу обучения CNN;

· Подход с использованием DNN основан на методе поиска глобального минимума, а также использовании фильтров, полученных при обучении CNN, и предназначен для сведения к минимуму плохо обусловленных затрат, которые возникают в свёрточном подходе.

2.4.4 Применение CNN в прикладных задачах

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

Применение CNN в диагностике глазного дна

Существует решение с применением CNN для сегментации биомедицинских диагностических изображений [43]. В данном решении на изображении глазного дна с помощью CNN выделяются кровеносные сосуды.

В качестве базы изображений была использована Digital Retinal Images for Vessel Extraction (см. рисунок 50).

Рисунок 50 - Пример изображений для обучения [43]

В данном примере сеть состоит из входного (нулевого) слоя, чередующихся слоёв свёртки и подвыборки (всего 8мь) и двух полносвязных нейронных сетей на выходе (см. таблицу 2). Обучение происходит методом обратного распространения ошибки. При прохождении всех слоёв полученное значение сравнивается с заданным в обучении, и разность используется для изменения весов сети в обратном порядке. Результаты сегментации, проводимой свёрточной нейронной сетью, сравнимы с результатами сегментации, проводимой человеком-экспертом. Точность результата работы такой CNN составляет 97.67% при чувствительности 81.73% [43].

...