Алгоритм Текномо – Фернандеса - Википедия - Teknomo–Fernandez algorithm

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

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

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

История

Алгоритм TF генерирует цветное фоновое изображение и использует его для вычитания фона.

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

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

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

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

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

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

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

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

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

Уравнения

Для трех кадров последовательности изображений ${ displaystyle x_ {1}}$ , ${ displaystyle x_ {2}}$ , и ${ displaystyle x_ {3}}$ , фоновое изображение ${ displaystyle B}$ получается с использованием
${ Displaystyle B = x_ {3} (x_ {1} oplus x_ {2}) + x_ {1} x_ {2}}$ ^[1]
Функция логического режима ${ displaystyle S}$ таблицы возникает, когда количество записей 1 больше половины количества изображений, так что^[1]
${ displaystyle S = { begin {case} 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 {иначе}} end {case}}}$
Для трех изображений фоновое изображение ${ displaystyle B}$ можно принять за значение

{ displaystyle { 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]

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

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

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

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

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

Космическая сложность

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

Сложность времени

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

Варианты

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

Приложения

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

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

внешняя ссылка

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

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

[PCTF-2] Абу, Патрисия Анджела; Фернандес, Просесо. «Сравнение производительности алгоритма Текномо-Фернандеса в цветовом пространстве RGB и HSV». Цитировать журнал требует | журнал = (помощь)

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

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

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

[1]

[2]

[3]

[4]

[5]