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

Алгоритм Текномо–Фернандеса є ефективним алгоритмом для створення фонового зображення заданої відеопослідовності.

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

Історія ред.

Алгоритм Текномо-Фернандеса генерує кольорове фонове зображення та використовує його для віднімання фону.

Відстеження людей на відео зазвичай включає віднімання фону, щоб відокремити передній план від фону. Таким чином, після виділення зображень переднього плану, їх можна використати для необхідних алгоритмів поставленої задачі (наприклад, для відстеження руху, відстеження об’єктів і розпізнавання обличчя ). ^[1]

Однак для віднімання фону потрібно, щоб фонове зображення вже було доступним, і, на жаль, це не завжди так. Традиційно фонове зображення шукається вручну або автоматично серед зображень з відео, коли на них немає об’єктів. Нещодавно була запропонована автоматична генерація фону за допомогою виявлення об’єктів, медіальної фільтрації, медоїдної фільтрації, апроксимованої медіанної фільтрації, лінійного прогностичного фільтра, непараметричної моделі, фільтра Калмана та адаптивного згладжування ; однак більшість цих методів мають високу обчислювальну складність і ресурсомісткі. ^[4]

Алгоритм Текномо-Фернандеса також є алгоритмом автоматичного створення фону. Однак його перевагою є лише швидкість обчислення за час $O(R)$ , який залежить від роздільної здатності $R$ зображення, а його точність досягається в межах керованої кількості кадрів. Щоб створити фонове зображення, потрібно лише принаймні три кадри з відео, якщо припустити, що для кожного пікселя фон є у більшості кадрів. Крім того, це може працювати як для сірих, так і для кольорових відео.

Припущення ред.

Камера нерухома.
Освітленість середовища змінюється лише повільно відносно рухів людей у сцені.
Люди не проводять більшу частину часу в одному місці.

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

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

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

Створення фонового зображення ред.

Рівняння ред.

Вісім можливових значень трьох бінарних зображень і їх булева функція S
$x_{1}$	0	0	0	1	1	1
$x_{2}$	0	1	1	0	1	1
$x_{3}$	1	0	1	1	0	1
$S$	0	0	1	1	1	1

Для трьох бінарних кадрів з послідовності зображень (відео) $x_{1}$ , $x_{2}$ , і $x_{3}$ , фонове зображення $B$ отримують з рівняння
$B=x_{3}(x_{1}\oplus x_{2})+x_{1}x_{2}$ , де $\oplus$ це виключна диз'юнкція (XOR). ^[1]
Булева функція $S$ дорівнює одиниці, коли кількість одиниць перевищує половину кількості зображень, так що ^[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}}.$
Таким чином, для 3 зображень фонове зображення $B$ може бути прийнято як значення 1 у S, або $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 перевершують алгоритм Текномо–Фернандеса з точки зору точності. Однак алгоритм Текномо–Фернандеса залишається більш ефективним з точки зору часу обробки. ^[5]

Застосування ред.

Виявлення об'єктів
Виявлення обличчя
Розпізнавання обличчя
Виявлення пішоходів
Відеоспостереження
Захоплення руху
Взаємодія людини з комп’ютером
Кодування відео на основі вмісту
Моніторинг руху
Розпізнавання жестів у реальному часі

Див. також ред.

Список літератури ред.

↑ ^а ^б ^в ^г ^д ^е ^ж ^и ^к ^л ^м Teknomo, Kardi; Fernandez, Proceso (2015). «Background Image Generation Using Boolean Operations». arXiv:1510.00889 [cs.CV].
↑ Abu, Patricia Angela; Fernandez, Proceso (2014). Performance Comparison of the Teknomo-Fernandez Algorithm on the RGB and HSV Colour Spaces. 2014 International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM). с. 1—6. doi:10.1109/HNICEM.2014.7016262. ISBN 978-1-4799-4020-2.
↑ Abu, Patricia Angela (March 2015). Improving the Teknomo–Fernandez Background Image Modeling Algorithm for Foreground Segmentation (Ph.D). Ateneo de Manila University.
↑ Abu, Patricia Angela; Fernandez, Proceso (March 2016). Modifying the Teknomo–Fernandez Algorithm for Accurate Real-Time Background Subtraction. Philippine Computing Science Congress.
↑ Abu, Patricia Angela; Chu, Varian Sherwin; Fernandez, Proceso. A Monte-Carlo-based Algorithm for Background Generation.

Подальше читання ред.

Chu, Varian Sherwin B. (2013). Background image reconstruction using random frame sampling and logical bit operations (Дипломна робота). Ateneo de Manila University.
Abu, Patricia Angela R. (2015). Improving the Teknomo-Fernandez Background Image Modeling Algorithm for Foreground Segmentation (Дипломна робота). Ateneo de Manila University.

Зовнішні посилання ред.

Створення фонового зображення за допомогою логічних операцій – описує алгоритм Текномо–Фернандеса, його припущення, процеси, точність, часову та просторову складність, а також вибіркові результати.
У цьому дослідженні було розроблено алгоритм Монте-Карло для генерації фону – варіант алгоритму Текномо–Фернандеса, який включає метод Монте-Карло .

[TF-1] а ^б ^в ^г ^д ^е ^ж ^и ^к ^л ^м Teknomo, Kardi; Fernandez, Proceso (2015). «Background Image Generation Using Boolean Operations». arXiv:1510.00889 [cs.CV].

[PCTF-2] Abu, Patricia Angela; Fernandez, Proceso (2014). Performance Comparison of the Teknomo-Fernandez Algorithm on the RGB and HSV Colour Spaces. 2014 International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM). с. 1—6. doi:10.1109/HNICEM.2014.7016262. ISBN 978-1-4799-4020-2.

[ITF-3] Abu, Patricia Angela (March 2015). Improving the Teknomo–Fernandez Background Image Modeling Algorithm for Foreground Segmentation (Ph.D). Ateneo de Manila University.

[RTTF-4] Abu, Patricia Angela; Fernandez, Proceso (March 2016). Modifying the Teknomo–Fernandez Algorithm for Accurate Real-Time Background Subtraction. Philippine Computing Science Congress.

[CRF-5] Abu, Patricia Angela; Chu, Varian Sherwin; Fernandez, Proceso. A Monte-Carlo-based Algorithm for Background Generation.

[1]

[2]

[3]

[4]

[5]