Алгоритм Текномо – Фернандеса

Алгоритм Текномо -Фернандеса (алгоритм TF) — это эффективный алгоритм для создания фонового изображения заданной видеопоследовательности.

Предполагая, что фоновое изображение отображается в большей части видео, алгоритм может генерировать хорошее фоновое изображение для видео. $O(R)$ -time, используя лишь небольшое количество двоичных операций и логических битовых операций, которые требуют небольшого объема памяти и имеют встроенные операторы, встречающиеся во многих языках программирования, таких как C , C++ и Java . ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}

История

Отслеживание людей по видео обычно включает в себя некоторую форму вычитания фона , чтобы отделить передний план от фона. После извлечения изображений переднего плана желаемые алгоритмы (например, алгоритмы отслеживания движения , отслеживания объектов и распознавания лиц ). с использованием этих изображений могут быть выполнены ^{[ 1 ]}^{[ 3 ]}

Однако вычитание фона требует, чтобы фоновое изображение уже было доступно, и, к сожалению, это не всегда так. Традиционно поиск фонового изображения осуществляется вручную или автоматически среди видеоизображений при отсутствии объектов. Совсем недавно автоматическая генерация фона посредством обнаружения объектов , медиальной фильтрации , медоидной фильтрации , аппроксимированной медианной фильтрации , линейного прогнозирующего фильтра , непараметрической модели , фильтра Калмана и адаптивного сглаживания была предложена ; однако большинство этих методов имеют высокую вычислительную сложность и ресурсоемки. ^{[ 1 ]}^{[ 4 ]}

Алгоритм Текномо-Фернандеса также является алгоритмом автоматической генерации фона. Однако его преимуществом является скорость вычислений, составляющая всего $O(R)$ -время, в зависимости от разрешения $R$ изображения и его точность достигается в пределах управляемого количества кадров. Для создания фонового изображения требуется не менее трех кадров из видео, при условии, что для каждой позиции пикселя фон встречается в большинстве видео. Кроме того, это можно выполнить как для полутонового, так и для цветного видео. ^{[ 1 ]}

Предположения

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

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

Для каждой позиции пикселя большинство значений пикселей во всем видео содержат значение пикселя фактического фонового изображения (в этой позиции). ^{[ 1 ]}

Поскольку каждая часть фона отображается в большей части видео, все фоновое изображение не обязательно должно появляться ни в одном из его кадров. Ожидается, что алгоритм будет работать точно. ^{[ 1 ]}

Генерация фонового изображения

Уравнения

Для трех кадров последовательности изображений $x_{1}$ , $x_{2}$ , и $x_{3}$ , фоновое изображение $B$ получается с помощью
$B=x_{3}(x_{1}\oplus x_{2})+x_{1}x_{2}$ ^{[ 1 ]}
Функция логического режима $S$ таблицы возникает, когда количество 1 записей превышает половину количества изображений, так что ^{[ 1 ]}
$S={\begin{cases}1,&{\text{if }}\sum _{i=1}^{n}x_{i}\geq \left\lceil {\frac {n}{2}}+1\right\rceil ,{\text{ and }}n\geq 3\\0,&{\text{otherwise}}\end{cases}}$
Для трех изображений фоновое изображение $B$ можно принять за значение

{\bar {x}}_{1}x_{2}x_{3}+x_{1}{\bar {x}}_{2}x_{3}+x_{1}x_{2}{\bar {x}}_{3}+x_{1}x_{2}x_{3}

^{[ 1 ]}

Алгоритм генерации фона

На первом уровне из последовательности изображений случайным образом выбираются три кадра для создания фонового изображения путем их объединения с помощью первого уравнения. Это дает лучшее фоновое изображение на втором уровне. Процедура повторяется до желаемого уровня. $L$ . ^{[ 1 ]}

Теоретическая точность

На уровне $\ell$ , вероятность $p_{\ell }$ то, что предсказанный модальный бит является фактическим модальным битом, представлено уравнением $p_{\ell }=(p_{\ell -1})^{3}+3(p_{\ell -1})^{2}(1-p_{\ell -1})$ . В таблице ниже приведены вычисленные значения вероятности на нескольких уровнях с использованием некоторых конкретных начальных вероятностей. Можно заметить, что даже если модальный бит в рассматриваемой позиции находится на уровне 60% кадров, вероятность точного определения модального бита уже составляет более 99% на 6 уровнях. ^{[ 1 ]}

Таблица расчетных вероятностей — В этой таблице приведены вычисленные значения вероятности на нескольких уровнях с использованием некоторых конкретных начальных вероятностей. Можно заметить, что даже если модальный бит в рассматриваемой позиции находится на уровне 60% кадров, вероятность точного определения модального бита уже составляет более 99% на шести уровнях.

Пространственная сложность

Требование к пространству алгоритма Текномо – Фернандеса определяется функцией $O(RF+R3^{L})$ , в зависимости от разрешения $R$ изображения, номер $F$ кадров в видео и желаемое количество $L$ уровней. Однако тот факт, что $L$ вероятно, не превысит 6, уменьшает пространственную сложность до $O(RF)$ . ^{[ 1 ]}

Временная сложность

Весь алгоритм работает в $O(R)$ -время, только в зависимости от разрешения изображения. Вычисление модального бита для каждого бита можно выполнить в $O(1)$ -время, в течение которого вычисление результирующего изображения из трех заданных изображений может быть выполнено за $O(R)$ -время. Количество изображений, подлежащих обработке. $L$ уровни это $O(3^{L})$ . Однако, поскольку $L\leq 6$ , тогда это на самом деле $O(1)$ , таким образом, алгоритм работает в $O(R)$ . ^{[ 1 ]}

Варианты

вариант алгоритма Текномо-Фернандеса, включающий метод Монте-Карло, Был разработан названный CRF. Были реализованы две разные конфигурации CRF: CRF9,2 и CRF81,1. Эксперименты с некоторыми цветными видеопоследовательностями показали, что конфигурации CRF превосходят алгоритм TF с точки зрения точности. Однако алгоритм TF остается более эффективным с точки зрения времени обработки. ^{[ 5 ]}

Приложения

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м Текномо, Карди; Фернандес, Процессо (2015). «Создание фонового изображения с использованием логических операций». arXiv : 1510.00889 [ cs.CV ].
^ Абу, Патрисия Анджела; Фернандес, Процессо (2014). «Сравнение производительности алгоритма Текномо-Фернандеса в цветовых пространствах RGB и HSV». 2014 Международная конференция по гуманоидам, нанотехнологиям, информационным технологиям, связи и управлению, окружающей среде и менеджменту (HNICEM) . стр. 1–6. doi : 10.1109/HNICEM.2014.7016262 . ISBN 978-1-4799-4020-2 . S2CID 15493318 .
^ Перейти обратно: ^а ^б Абу, Патрисия Анджела (март 2015 г.). Улучшение алгоритма моделирования фонового изображения Текномо – Фернандеса для сегментации переднего плана (доктор философии). Университет Атенео де Манила.
^ Абу, Патрисия Анджела; Фернандес, Процессо (март 2016 г.). Модификация алгоритма Текномо-Фернандеса для точного вычитания фона в реальном времени . Филиппинский конгресс по информатике.
^ Абу, Патрисия Анджела; Чу, Вариан Шервин; Фернандес, Процессо. «Алгоритм генерации фона на основе Монте-Карло» . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

Дальнейшее чтение

Чу, Вариан Шервин Б. (2013). Реконструкция фонового изображения с использованием случайной выборки кадров и логических битовых операций (Диссертация). Университет Атенео де Манила.
Абу, Патрисия Анджела Р. (2015). Улучшение алгоритма моделирования фонового изображения Текномо-Фернандеса для сегментации переднего плана (Диссертация). Университет Атенео де Манила.

Внешние ссылки

Генерация фонового изображения с использованием логических операций - описывает алгоритм TF, его предположения, процессы, точность, временную и пространственную сложность, а также примеры результатов.
В этом исследовании был разработан алгоритм генерации фона на основе Монте-Карло – вариант алгоритма Текномо – Фернандеса, который включает метод Монте-Карло .

[TF-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м Текномо, Карди; Фернандес, Процессо (2015). «Создание фонового изображения с использованием логических операций». arXiv : 1510.00889 [ cs.CV ].

[PCTF-2] Абу, Патрисия Анджела; Фернандес, Процессо (2014). «Сравнение производительности алгоритма Текномо-Фернандеса в цветовых пространствах RGB и HSV». 2014 Международная конференция по гуманоидам, нанотехнологиям, информационным технологиям, связи и управлению, окружающей среде и менеджменту (HNICEM) . стр. 1–6. doi : 10.1109/HNICEM.2014.7016262 . ISBN 978-1-4799-4020-2 . S2CID 15493318 .

[ITF-3] Перейти обратно: ^а ^б Абу, Патрисия Анджела (март 2015 г.). Улучшение алгоритма моделирования фонового изображения Текномо – Фернандеса для сегментации переднего плана (доктор философии). Университет Атенео де Манила.

[RTTF-4] Абу, Патрисия Анджела; Фернандес, Процессо (март 2016 г.). Модификация алгоритма Текномо-Фернандеса для точного вычитания фона в реальном времени . Филиппинский конгресс по информатике.

[CRF-5] Абу, Патрисия Анджела; Чу, Вариан Шервин; Фернандес, Процессо. «Алгоритм генерации фона на основе Монте-Карло» . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]