Назад в библиотеку

Трекинг объектов в видеосигнале с использованием Compressive Sensing

Автор: Кракунов М., Бастрика М., Тецовик Дж.
Источник: Student paper submitted to The 8th Mediterranean Conference on Embedded Computing MECO'2019. [Ссылка]

Аннотация

В данной работе рассматривается возможность уменьшения размерности видео путём сокращения количества пикселей в видеосигнале, сохраняя при этом качество, необходимое для корректного трекинга объектов, путём применения технологии Compressive Sensing. Качество кадров видеофрагмента, содержащих отслеживаемый объект, постепенно изменяется, принимая разное значение количества пикселей на каждой итерации - от 45% до 1%. Используя алгоритм для задач трекинга, были получены удовлетворительные результаты, видимые на разности графиков траекторий оригинального и измененного видео.

Ⅰ. Введение

Compressive sensing

Благодаря распределённым системам, передающим значительное количество окружающих нас сигналов, появилась возможность применения алгоритмов сжатия, таких как Compressive Sensing (CS), для намного более эффективного использования вычислительных ресурсов. Для понятия алгоритмов семейства Compressive Sensing [1-15], необходимо упомянуть теорему Клода Шеннона, датируемую 1949 годом. Теорема гласит - если функция f(t) не содержит частот выше, чем W Hz, она полностью определяется путем задания ее ординат в серии точек, разнесенных на 1/(2W) секунды. Несмотря на то, что это фундаментальный принцип в области теории информации, суть CS заключается в том, чтобы избежать его. Теорема Шеннона утверждает, что разрешение изображения пропорционально количеству измерений. Удвоение разрешения требует удвоения измерений.

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

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

Система, описанная в данной работе, является недоопределённой. Недоопределённая система - это система, в которой данные измерения меньше числа неизвестных значений сигнала, что приводит к системе с бесконечным количеством решений. К счастью, эта проблема разрешима, если сигнал x сжимаем. Для определения распределённых объектов, выполняя как можно меньшее количество измерений, наилучшим подходом является измерение на случайно выбранных частотах.

b = Ax

где x - дискретный сигнал

b - вектор линейный измерений, сформированный путём взятия внутреннего произведения x с множеством линейно независимых векторов ai, i = 1,2,3m

A состоит из aiT

Таким образом, кодирование - это процесс получения b из x, а процесс декодирования - восстановление x из b. Предполагая, что b получен из очень разреженного сигнала, делаем вывод о малом количестве в нём ненулевых элементов. Наилучший подход к декодированию - это поиск самого редкого сигнала из всех, что принимают участие в измерении b

min { ǁ x ǁ0 : Ax = b}

где ǁxǁ0 - количество ненулевых значений в x

Из-за сложности решения путём перечисления «l0-норма» заменяется «l1-нормой»

min { ǁ x ǁ1 : Ax = b}

Если дан разреженный вектор x, мы можем записать его в виде взвешенной линейной комбинации

x = ∑N αj ψj

где ψj - вектор-столбец

αj - коэффициенты Фурье

Но только S из этих αj нулевые, остальные же являются отличными от нуля. S ≪ N, N - это количество пикселей.

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


Трекинг объектов

Трекинг - это процесс определения местоположения движущегося объекта или нескольких движущихся объектов во времени и восстановления траектории, по которой эти объекты прошли [16-23]. Самым простым известным методом является метод сопоставления блоков. Наблюдая за текущим кадром, мы принимаем во внимание блок пикселей. Идея состоит в том, чтобы оценить положение путем сравнения блоков в пределах области, содержащей целевой объект с опорным кадром [2]. Качество результата напрямую зависит от того, насколько область изображения в текущем кадре отлична от других частей кадра. Проблемы, возникающие во время трекинга, вызваны несколькими факторами, такими как низкая частота кадров во время быстрого движения объекта, помехи и шумы, вызванные загроможденным фоном и т.д. [3].

В данном исследовании были получены положение, скорость и ускорение мяча из видеофайла, записанного с помощью фиксированной камеры. Детектирование основано на методе вычитания фона из каждого кадра. Когда программа работает в 2D, предполагается, что все движения, скорость и ускорение находятся в вертикальной плоскости, перпендикулярной камере. В случае 3D мяч свободно движется.

Ⅱ. CV и трекинг

CS представляет собой инструмент для управления видео, по которому будет выполняться трекинг. Проблемы, которые все еще вызывают вопросы - это сложный фон, изменения яркости, но одной из самых сложных является проблема, включающая внезапное и/или кратковременное исчезновение реального объекта, то есть происходит окклюзия, в области, где установленные камеры не имеют возможности зрения. Для построения корректной траектории и реконструкции пути по предположениям, необходимо опираться на его положениях до и после исчезновения, а также на информации о скорости и ускорении.

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

Ⅲ. Результаты экспериментов

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


Эксперимент Ⅰ

Первое виде намного проще, а значит, намного более разрежено, чем второе. Из-за небольшого количества ненулевых коэффициентов это служит хорошим примером измерения сжатия. На рисунке 1 показано несколько кадров из исходного видео.

4/75 кадра исходного видео

Рисунок 1 – 4/75 кадра исходного видео

Продолжительность этого видео составляет 2,5 секунды, частота кадров составляет 24,32 кадра в секунду. В отличие от эксперимента с другим видео, которое будет обсуждаться позже, фон этого видео пуст. Это огромное преимущество, потому что фон не будет создавать никаких помех. В результате кадры хорошо восстанавливаются с использованием 45%, 30%, 20%, 10%, 5% и даже 1% доступных пикселей. На рисунках 2 и 3 представлено несколько восстановленных кадров с 1% и 5% доступных пикселей соответственно, а на рисунке 4 представлена разница между следом объекта, когда видео не сжато (красные точки) и когда только 1% (слева) и 5% (справа) из пикселей были взяты (синие точки).

4/75 кадра реконструированного видео (1%)

Рисунок 2 – 4/75 кадра реконструированного видео (1%)

4/75 кадра реконструированного видео (5%)

Рисунок 3 – 4/75 кадра реконструированного видео (5%)

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

Траектория мяча

Рисунок 4 – Траектория мяча, восстановленная из видео 1% (лево) и 5% (право)

Эксперимент Ⅱ

Второй эксперимент проводится с использованием гораздо менее разреженного видео, чем предыдущий. Движение шара более сложное, фон разнообразен и у объекта есть тень (рисунок 5).

4/75 кадра исходного видео

Рисунок 5 – 4/75 кадра исходного видео

4/75 кадра реконструированного видео (1%)

Рисунок 6 – 4/75 кадра реконструированного видео (1%)

4/75 кадра реконструированного видео (5%)

Рисунок 7 – 4/75 кадра реконструированного видео (5%)

4/75 кадра реконструированного видео (10%)

Рисунок 8 – 4/75 кадра реконструированного видео (10%)

4/75 кадра реконструированного видео (20%)

Рисунок 9 – 4/75 кадра реконструированного видео (20%)

Длительность видео составляет 2,3667 секунды, размер видеокадра - 512х512, а частота кадров составляет 30 кадров в секунду. На рисунках с 11 по 12 мы можем видеть, что с уменьшением процента оставшихся пикселей отклонение увеличивается. Только с 45% оставшихся пикселей достигается полное совпадение, тогда как с 1% сохраненных пикселей объект может отслеживаться с некоторой точностью, но трек смещается от исходного. Эксперименты проводились с использованием трех разных компьютеров с разными спецификациями. Таблица 1 показывает истекшее время алгоритма сжатия при различных процентах.

Траектория мяча

Рисунок 10 – Траектория мяча, восстановленная из видео 1% (лево) и 5% (право)

Траектория мяча

Рисунок 11 – Траектория мяча, восстановленная из видео 10% (лево) и 20% (право)

Траектория мяча

Рисунок 12 – Траектория мяча, восстановленная из видео 30% (лево) и 45% (право)

Таблица 1. Время, затраченное на CS алгоритм двух видео
CS [%] Figures from video 1 (75 fig.) [s] Figures from video 2 (71 fig.) [s]
1 50378.1878 51298.0946
5 36633.7740 30622
10 22632 31255
20 62553 21562.1477
30 12065.6284 15875.5255
45 6279 38944

Blue-i5-88250U CPU 1.6GHz RAM (12GB)

Black-i5-7300HQ CPU 2.50GHz RAM (16GB)

Red-i5-4210U CPU 1.7GHz RAM (4GB)


Кроме того, представлены результаты PSNR (Peak signal-to-noise ratio) на рисунке 13. Как видно из рисунков, высокое значение PSNR получено, когда сжатие будет выполнено в первом видео. Это означает, что видео сохранит свое качество даже при распознавании 1% пикселей. Такие результаты ожидаемы, учитывая простоту первого видео, однако результаты для второго видео сильно отличаются. Когда содержится 45% пикселей, первое видео имеет PSNR около 80 dB, а второе видео имеет PSNR около 30 bD.


PSNR

Рисунок 13 – PSNR первого (лево) и второго (право) видео с разными процентами покрытия

Заключение

В данной статье рассмотрено сжатие и трекинг объектов на двух видео. Второе видео было менее разреженным, чем первое. Первое видео содержит меньше деталей, чистый фон и более плавное движение. Данные факторы привели к выводу, что даже при сжатии до 1% пикселей видео очень схоже с исходным, а трекинг осуществлялся довольно точно. Из-за сложности второго видео результаты были не такими удовлетворительными, как с первым. Даже при сохранении 10% пикселей можно наблюдать явное снижение качества. Тем не менее, если этот алгоритм используется, когда строгая точность не является главной целью, результаты все еще удовлетворительны.

Литература

  1. Roummel F. Marcia and Rebecca M. Willett, “Compressive coded aperture video reconstruction”, Department of Electrical and Computer Engineering, Duke University Box 90291, Durham, NC 27708, USA 16th, European Signal Processing Conference (EUSIPCO 2008), Lausanne, Switzerland, August 25-29, 2008, copyright by EURASIP
  2. S. Stankovic, I. Orovic, E. Sejdic, “Multimedia Signals and Systems: Basic and Advance Algorithms for Signal Processing”, Springer-Verlag, New York, 2015
  3. Y. C. Eldar, G. Kutyniok, “Compressed Sensing Theory and Applications”, Cambridge University Press; 1 edition (June 29, 2012), 558 pages, ISBN-10: 1107005582
  4. LJ. Stankovic, S. Stankovic, M. Amin, “Missing Samples Analysis in Signals for Applications to L-estimation and Compressive Sensing”, Signal Processing, vol. 94, pp. 401-408, Jan. 2014
  5. M. Elad, “Sparse and Redudant Representations: From Theory to Applications in Signal and Image Processing”, Springer 2010
  6. D. Mackenzie “Compressed Sensing Makes Every Pixel Count”, Whats Happening in the Mathematical Sciences, Volume 7, pp. 115 127, 2009
  7. E. Sejdic, I. Orovic, S. Stankovic, “Compressive sensing meets timefrequency: An overview of recent advances in time-frequency processing of sparse signals”, Volume 77, June 2018, Pages 22-35
  8. I. Volaric, V. Sucic, S. Stankovic, “A Data Driven Compressive Sensing Approach for Time-Frequency Signal Enhancement”, Volume 141, December 2017, Pages 229-239
  9. E. Candes, J. Romberg, T. Tao, “Stable Signal Recovery from Incomplete and Inaccurate Measurements”, Applied and Computational Mathematics, University of California, Los Angeles, CA 90095 February, 2005
  10. A. Draganic, I. Orovic, S. Stankovic, “On some common compressive sensing recovery algorithms and applications” - Review paper, Facta Universitatis, Series: Electronics and Energetics, Vol 30, No 4 (2017), pp. 477-510
  11. S. Stankovic, I. Orovic, “An Approach to 2D Signals Recovering in Compressive Sensing Context”, Circuits Systems and Signal Processing, April 2017, Volume 36, Issue 4, pp. 1700-1713, 2016
  12. M. Brajovic, I. Orovic, M. Dakovic, S. Stankovic, “Gradient-based signal reconstruction algorithm in the Hermite transform domain”, Electronic Letters, Volume: 52, Issue: 1, pp. 41 - 43, 2015
  13. I. Orovic, A. Draganic, S. Stankovic, “Sparse Time-Frequency Representation for Signals with Fast Varying Instantaneous Frequency”, IET Radar, Sonar and Navigation, Vol. 9, Issue: 9, pp. 1260 - 1267, ISSN: 1751-8784
  14. A. G. Rad, A. Dehghani, and M. R. Karim, “Vehicle speed detection in video image sequences using CVS method”, International Journal of the Physical Sciences, vol. 5(17), pp. 2555-2563, 2010
  15. N. Saunier and T. A. Sayed, “Automated Road Safety Analysis with Video Data”, Transportation Research Records: Journal of Transportation Research Board, no. 2019, pp. 57-64, 2007
  16. S. Stankovic, I. Orovic, A. Krylov, “Video Frames Reconstruction based on Time-Frequency Analysis and Hermite projection method”, EURASIP Journal on Advances in Signal Processing,Special Issue on Time-Frequency Analysis and its Application to Multimedia signals, Vol. 2010, Article ID 970105, 11 pages, 2010
  17. I. Orovic, S. Park, S. Stankovic, “Compressive sensing in Video applications”, 21st Telecommunications Forum TELFOR, Nov. 2013
  18. I. Djurovic, S. Stankovic, “Estimation of time-varying velocities of moving objects in video-sequences by using time-frequency representations”, IEEE Transactions on Image Processing, Vol.12, No.5, pp.550-562, 2003
  19. A. Hakeem, K. Shafique, and M. Shah, “An object based video coding framework for video sequences obtained from static cameras”, in Proceedings of the 13th annual ACM International Conference on Multimedia, pp. 608-617, Singapore, November 2005
  20. I. Djurovic, S. Stankovic, A. Ohsumi, H. Ijima, “Motion parameters estimation by new propagation approach and time-frequency representations”, Signal Processing Image Communications, vol. 19, No. 8 pp. 755-770, 2004
  21. Jiyan Pan, Bo Hu, and Jian Qiu Zhang,“An Efficient Object Tracking Algorithm with Adaptive Prediction of Initial Searching Point”, Dept. of E. E., Fudan University. 220 Handan Road, Shanghai 200433, P.R.