Алгоритм конденсации

Алгоритм конденсации ( Conditional Density алгоритм Propagation компьютерного ) — это зрения . Основное применение — обнаружение и отслеживание контуров объектов, движущихся в загроможденной среде. Отслеживание объектов является одним из наиболее основных и сложных аспектов компьютерного зрения и, как правило, является необходимым условием для распознавания объектов . Возможность определить, какие пиксели изображения составляют контур объекта, является нетривиальной задачей. Конденсация — это вероятностный алгоритм , который пытается решить эту проблему.

Сам алгоритм подробно описан Айсардом и Блейком в публикации в Международном журнале компьютерного зрения в 1998 году. ^[1] Одним из наиболее интересных аспектов алгоритма является то, что он не выполняет вычисления для каждого пикселя изображения. Скорее, пиксели для обработки выбираются случайным образом, и в конечном итоге обрабатывается только подмножество пикселей. Множественные гипотезы о том, что движется, естественным образом подкрепляются вероятностным характером подхода. Функции оценки во многом основаны на предыдущей работе в этой области и включают множество стандартных статистических подходов. Оригинальной частью этой работы является применение методов оценки фильтров частиц.

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

Обзор алгоритма

Алгоритм конденсации пытается решить задачу оценки конформации объекта, описываемого вектор $\mathbf {x_{t}}$ во время $t$ , учитывая наблюдения $\mathbf {z_{1},...,z_{t}}$ обнаруженных особенностей на изображениях до текущего времени включительно. Алгоритм выводит оценку состояния условная плотность вероятности $p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )$ путем применения нелинейного фильтра, основанного на факторизованной выборке, и его можно рассматривать как развитие метода Монте-Карло . ^[1] $p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )$ представляет собой представление вероятности возможных конформаций объектов на основе предыдущих конформаций и измерений. Алгоритм конденсации представляет собой генеративную модель. ^[2] поскольку он моделирует совместное распределение объекта и наблюдателя.

Условная плотность объекта в текущий момент времени $p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )$ оценивается как взвешенный, индексированный по времени набор выборок $\{s_{t}^{(n)},n=1,...,N\}$ с гирями $\pi _{t}^{(n)}$ . N — параметр, определяющий количество выбранных наборов выборок. Реализация $p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )$ получается выборкой с заменой из множества $s_{t}$ с вероятностью, равной соответствующему элементу $\pi _{t}$ . ^[1]

Предположения о том, что динамика объектов образует временную цепь Маркова и что наблюдения независимые друг от друга и динамики облегчают реализацию алгоритма конденсации. Первое предположение позволяет полностью определять динамику объекта условной плотностью $p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )$ . Модель динамики системы, определяемая $p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )$ также должен быть выбран для алгоритма и обычно включает как детерминистическую , так и стохастическую динамику.

Алгоритм можно обобщить путем инициализации во времени. $t=0$ и три шага в каждый момент времени t :

Инициализация

Сформируйте исходный набор выборок и веса путем выборки в соответствии с предыдущим распределением. Например, укажите Гауссово и установите равные веса.

Итерационная процедура

Образец с заменой $N$ раз из набора $\{s_{0}^{(n)},n=1,...,N\}$ с вероятностью $\{\pi _{0}^{(n)},n=1,...,N\}$ генерировать реализацию $p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )$ .
Примените изученную динамику $p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )$ к каждому элементу этого нового набора, чтобы создать новый набор $\{s_{t}^{(n)}\}$ .
Чтобы принять во внимание текущее наблюдение $\mathbf {z_{t}}$ , набор $\pi _{t}^{(n)}={\frac {p(\mathbf {z_{t}} |s^{(n)})}{\sum _{j=1}^{N}p(\mathbf {z_{t}} |s^{(j)})}}$ для каждого элемента $\{s_{t}^{(n)}\}$ .

Этот алгоритм выводит распределение вероятностей $p(\mathbf {x_{t}} |\mathbf {z_{1},...,z_{t}} )$ который можно напрямую использовать для расчета среднего положения отслеживаемого объекта, а также других моментов отслеживаемого объекта.

Вместо этого можно использовать кумулятивные веса для достижения более эффективной выборки. ^[1]

Рекомендации по реализации

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

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

Айсард и Блейк моделируют динамику объекта. $p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )$ второго порядка как разностное уравнение с детерминированной и стохастической компонентами: $p(\mathbf {x_{t}} |\mathbf {x_{t-1}} )\propto e^{-{\frac {1}{2}}||B^{-1}((\mathbf {x_{t}} -\mathbf {\bar {x}} )-A(\mathbf {x_{t-1}} -\mathbf {\bar {x}} ))||^{2})}$

где $\mathbf {\bar {x}}$ является средней стоимостью состояния, и $A$ , $B$ являются матрицами, представляющими детерминистическую и стохастические компоненты динамической модели соответственно. $A$ , $B$ , и $\mathbf {\bar {x}}$ оцениваются с помощью оценки максимального правдоподобия , когда объект выполняет типичные движения. ^[1]^[3]

Модель наблюдения $p(\mathbf {z} |\mathbf {x} )$ не может быть непосредственно оценено на основе данных, поэтому для его оценки необходимо делать предположения. Айсард 1998 предполагает, что беспорядок, который может сделать объект невидимым, представляет собой случайный процесс Пуассона с пространственной плотностью. $\lambda$ и что любое истинное целевое измерение является несмещенным и нормально распределяется со стандартным отклонением. $\sigma$ .

Базовый алгоритм конденсации используется для отслеживания одного объекта во времени. Алгоритм конденсации можно расширить, используя единое распределение вероятностей, чтобы описать вероятные состояния нескольких объектов и одновременно отслеживать несколько объектов в сцене. ^[4]

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

Приложения

Алгоритм можно использовать для визуальной локализации мобильных роботов. ^[6] Однако вместо отслеживания положения объекта в сцене отслеживается положение платформы камеры. Это позволяет глобально локализовать платформу камеры с учетом визуальной карты окружающей среды.

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

Алгоритм конденсации также использовался для распознавания лиц в видеоряде. ^[9]

Ресурсы

Реализацию алгоритма конденсации на языке C можно найти на сайте Майкла Айсарда .

Реализацию в MATLAB можно найти на Mathworks File Exchange .

Пример реализации с использованием библиотеки OpenCV можно найти на форумах OpenCV .

См. также

Фильтр частиц . Конденсация — это применение оценки важности выборки (SIR) для отслеживания контуров.

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и Айсард, М.; Блейк, А. (август 1998 г.). «КОНДЕНСАЦИЯ — распространение визуального слежения с условной плотностью». Международный журнал компьютерного зрения . 29 (1): 5–28. дои : 10.1023/A:1008078328650 . S2CID 6821810 .
^ Сминчишеску, К.; Канауджа, А.; Метаксас, Д.Н. (ноябрь 2007 г.). «BM3E: Дискриминативное распространение плотности для визуального отслеживания». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 29 (11): 2030–2044. CiteSeerX 10.1.1.78.1751 . дои : 10.1109/tpami.2007.1111 . ПМИД 17848782 . S2CID 1949783 .
^ Блейк, Андреа; Айсард, Майкл; Рейнард, Дэвид (октябрь 1995 г.). «Учимся отслеживать зрительное движение контуров» . Искусственный интеллект . 78 (1–2): 179–212. дои : 10.1016/0004-3702(95)00032-1 .
^ Коллер-Мейер, Эстер Б.; Аде, Франк (28 февраля 2001 г.). «Отслеживание нескольких объектов с использованием алгоритма конденсации». Робототехника и автономные системы . 34 (2–3): 93–105. дои : 10.1016/s0921-8890(00)00114-7 .
^ Айсард, Майкл; Блейк, Эндрю (28 мая 2006 г.). «Сглаживающий фильтр для конденсации». Компьютерное зрение — ECCV'98 . Конспекты лекций по информатике. Том. 1406. стр. 767–781. дои : 10.1007/BFb0055703 . ISBN 978-3-540-64569-6 .
^ Делларт, Ф.; Бургард, В.; Фокс, Д.; Трун, С. (1999). «Использование алгоритма КОНДЕНСАЦИИ для надежной локализации мобильных роботов на основе зрения». Слушания. 1999 г. Конференция IEEE Computer Society по компьютерному зрению и распознаванию образов (кат. номер PR00149) . Том. 2. С. 588–594. дои : 10.1109/CVPR.1999.784976 . hdl : 1853/21565 . ISBN 0-7695-0149-4 . S2CID 16130780 . {{cite book}}: |journal= игнорируется ( помогите )
^ Блэк, МД; Джепсон, AD (14 апреля 1998 г.). «Распознавание временных траекторий с использованием алгоритма конденсации». Материалы Третьей международной конференции IEEE по автоматическому распознаванию лиц и жестов . стр. 16–21. CiteSeerX 10.1.1.154.1402 . дои : 10.1109/AFGR.1998.670919 . ISBN 0-8186-8344-9 . S2CID 5159845 . {{cite book}}: |journal= игнорируется ( помогите )
^ Мейер, Э.Б.; Аде, Фрэнк (1999). «Отслеживание автомобилей на дальних изображениях с использованием алгоритма КОНДЕНСАЦИИ». Материалы 199 Международная конференция IEEE/IEEJ/JSAI по интеллектуальным транспортным системам (кат. № 99TH8383) . стр. 129–134. дои : 10.1109/ITSC.1999.821040 . ISBN 0-7803-4975-Х . S2CID 12548469 . {{cite book}}: |journal= игнорируется ( помогите )
^ Чжоу, Шаохуа; Крюгер, В.; Челлаппа, Р. (21 мая 2002 г.). «Распознавание лиц по видео: подход КОНДЕНСАЦИИ». Материалы пятой международной конференции IEEE по автоматическому распознаванию жестов лица . стр. 221–226. дои : 10.1109/AFGR.2002.1004158 . ISBN 0-7695-1602-5 . S2CID 8505547 . {{cite book}}: |journal= игнорируется ( помогите )

[Isard1998-1] Перейти обратно: ^а ^б ^с ^д ^и Айсард, М.; Блейк, А. (август 1998 г.). «КОНДЕНСАЦИЯ — распространение визуального слежения с условной плотностью». Международный журнал компьютерного зрения . 29 (1): 5–28. дои : 10.1023/A:1008078328650 . S2CID 6821810 .

[2] Сминчишеску, К.; Канауджа, А.; Метаксас, Д.Н. (ноябрь 2007 г.). «BM3E: Дискриминативное распространение плотности для визуального отслеживания». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 29 (11): 2030–2044. CiteSeerX 10.1.1.78.1751 . дои : 10.1109/tpami.2007.1111 . ПМИД 17848782 . S2CID 1949783 .

[3] Блейк, Андреа; Айсард, Майкл; Рейнард, Дэвид (октябрь 1995 г.). «Учимся отслеживать зрительное движение контуров» . Искусственный интеллект . 78 (1–2): 179–212. дои : 10.1016/0004-3702(95)00032-1 .

[4] Коллер-Мейер, Эстер Б.; Аде, Франк (28 февраля 2001 г.). «Отслеживание нескольких объектов с использованием алгоритма конденсации». Робототехника и автономные системы . 34 (2–3): 93–105. дои : 10.1016/s0921-8890(00)00114-7 .

[5] Айсард, Майкл; Блейк, Эндрю (28 мая 2006 г.). «Сглаживающий фильтр для конденсации». Компьютерное зрение — ECCV'98 . Конспекты лекций по информатике. Том. 1406. стр. 767–781. дои : 10.1007/BFb0055703 . ISBN 978-3-540-64569-6 .

[6] Делларт, Ф.; Бургард, В.; Фокс, Д.; Трун, С. (1999). «Использование алгоритма КОНДЕНСАЦИИ для надежной локализации мобильных роботов на основе зрения». Слушания. 1999 г. Конференция IEEE Computer Society по компьютерному зрению и распознаванию образов (кат. номер PR00149) . Том. 2. С. 588–594. дои : 10.1109/CVPR.1999.784976 . hdl : 1853/21565 . ISBN 0-7695-0149-4 . S2CID 16130780 . {{cite book}}: |journal= игнорируется ( помогите )

[7] Блэк, МД; Джепсон, AD (14 апреля 1998 г.). «Распознавание временных траекторий с использованием алгоритма конденсации». Материалы Третьей международной конференции IEEE по автоматическому распознаванию лиц и жестов . стр. 16–21. CiteSeerX 10.1.1.154.1402 . дои : 10.1109/AFGR.1998.670919 . ISBN 0-8186-8344-9 . S2CID 5159845 . {{cite book}}: |journal= игнорируется ( помогите )

[8] Мейер, Э.Б.; Аде, Фрэнк (1999). «Отслеживание автомобилей на дальних изображениях с использованием алгоритма КОНДЕНСАЦИИ». Материалы 199 Международная конференция IEEE/IEEJ/JSAI по интеллектуальным транспортным системам (кат. № 99TH8383) . стр. 129–134. дои : 10.1109/ITSC.1999.821040 . ISBN 0-7803-4975-Х . S2CID 12548469 . {{cite book}}: |journal= игнорируется ( помогите )

[9] Чжоу, Шаохуа; Крюгер, В.; Челлаппа, Р. (21 мая 2002 г.). «Распознавание лиц по видео: подход КОНДЕНСАЦИИ». Материалы пятой международной конференции IEEE по автоматическому распознаванию жестов лица . стр. 221–226. дои : 10.1109/AFGR.2002.1004158 . ISBN 0-7695-1602-5 . S2CID 8505547 . {{cite book}}: |journal= игнорируется ( помогите )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]