Увидеть незримое

  • Tutorial
Пару лет назад на Хабре проскакивало две статьи, в которых упоминался интересный алгоритм. Статьи, правда, были написаны нечитабильно. В стилистике «новости»(1, 2), но ссылка на сайт присутствовала, подробно можно было разобраться на месте (алгоритм за авторством MIT). А там была магия. Абсолютно волшебный алгоритм, позволяющий увидеть незримое. Оба автора на Хабре этого не заметили и сфокусировались на том, что алгоритм позволял увидеть пульс. Пропустив самое главное.



Алгоритм позволял усиливать движения, невидные глазу, показать вещи, которые никто никогда не видел живьём. Видео чуть выше – презентация c сайта MIT второй части алгоритма. Микросаккады, которые приведены начиная с 29ой секунды, раньше наблюдались только как отражения установленных на зрачках зеркалах. А тут они видны глазами.
Пару недель назад я опять натолкнулся на те статьи. Мне сразу стало любопытно: а что народ сделал за эти два года готового? Но… Пустота. Это определило развлечение на следующие полторы недели. Хочу сделать такой же алгоритм и разобраться, что с ним можно сделать и почему его до сих пор нет в каждом смартфоне, как минимум для измерения пульса.

В статье будет много матана, видео, картинок, немного кода и ответы на поставленные вопросы.

Начнём с математики (я не буду придерживаться какой-то одной определённой статьи, а буду мешать из разных частей разных статей, для более гладкого повествования). У исследовательской группы есть две основных работы по алгоритмической части:

1) Eulerian Video Magnification for Revealing Subtle Changes in the World;
2) Phase-Based Video Motion Processing.

В первой работе реализуется амплитудный подход, более грубый и быстрый. Его я и брал за основу. Во второй работе кроме амплитуды используется фаза сигнала. Это позволяет получить значительно более реалистичное и чёткое изображение. Видео выше прилагалось именно к этой работе. Минус – более сложный алгоритм и обработка, заведомо вылетающая из реального времени без применения видеокарты.

Начнём?


Что такое усиление движения? Усиление движения, это когда мы предсказываем в какую сторону сигнал смешается и сдвигаем его в эту сторону дальше.



Пусть у нас есть одномерный приёмник. На этом приёмнике мы видим сигнал I(x,t)=f(x). На картинке от нарисован чёрным (для некоторого момента t).В следующий момент времени сигнал I(x,t+1)= f(x+Δ) (синий). Усилить этот сигнал, это значит получить сигнал I’(x,t+1)= f(x+(1+α)Δ). Тут α – коэффициент усиления. Разложив его в ряд Тейлора его можно выразить как:



Пусть:



Что такое B? Грубо говоря это I(x,t+1)- I(x,t). Нарисуем:



Конечно, это неточно, но в качестве грубого приближения сойдёт (голубой график показыает форму такого «приближенонго» сигнала). Если мы домножим B на (1+α) это и будет «усиление» сигнала. Получаем (красный график):



В реальных кадрах может присутствовать несколько движений, каждое из которых будет идти с разной скоростью. Приведённый выше способ — линейный прогноз, без доработки он обломится. Но, есть классический подход для решения этой проблемы, который и использовался в работе — разложить движения по частотным характеристикам (как пространственным, так и временным).



На первом этапе происходит разложение изображения по пространственным частотам. Этот этап, кроме того, реализует получение дифференциала ∂f(x)/ ∂x. В первой работе не рассказано, как они его реализуют. Во второй работе, при использовании фазового подхода, амплитуда и фаза считалась фильтрами Габбора разного порядка:



Примерно так я и поступил, взяв фильтр:



И нормировав его значение, чтобы



Тут l — расстояния пикселя от центра фильтра. Конечно, я немного схалтурил, взяв такой фильтр только для одного значения окна σ. Это позволило значительно ускорить вычисления. При этом получается чуть более размазанная картинка, но я решил не стремиться за высокой точностью.

Вернёмся к формулам. Пусть мы хотим усилить сигнал, дающий характерный отклик на частоте ω в нашей временной последовательности кадров. Мы уже подобрали характерный пространственный фильтр с окном σ. Это даёт нам примерный дифференциал в каждой точке. Как понятно из формул — остаётся только временная функция, дающая отклик на наше движение и коэффициент усиления. Умножаем на синус той частоты, которую хотим усилить (это и будет функция, дающая временной отклик). Получаем:



Конечно, куда проще, чем в оригинальной статье, зато чуть-чуть меньше проблем со скоростью.

Код и результат


Исходники к первой статье выложены в открытом доступе на Матлабе:. Казалось бы, зачем изобретать велосипед и писать самому? Но был целый ряд причин, во многом завязанных на Матлаб:
  1. Если потом придёт в голову сделать что-то разумное и применимое, код на Матлабе куда сложнее использовать, чем C#+OpenCV, портирующийся за пару часов в с++.
  2. Оригинальный код ориентировался на работу с сохранёнными видео, имеющее постоянный битрейт. Чтобы можно было работать с камерами, подключёнными к компьютеру, обладающими переменным битрейтом нужно менять логику.
  3. Оригинальный код реализовывал самый простой из их алгоритмов, без всяких плюшек. Реализовать чуть более сложную версию с плюшками – уже пол работы. К тому же, не смотря на то, что алгоритм был оригинальным, параметры на его вводе были не те, что в статьях.
  4. Оригинальный код периодически приводил к мёртвому зависанию компа (даже без синего экрана). Может только у меня, но ведь некомфортно.
  5. В оригинальном коде был только консольный режим. Делать всё визуальным в Матлабе, который я знаю значительно хуже VS, было бы значительно дольше, чем всё переписать.

Исходники я выложил на github.com и достаточно подробно прокомментировал. Программа реализует захват видео с камеры и его анализ в реальном времени. Оптимизации получилось немного с запасом, но можно добиться подвисаний, расширяя параметры. Что обрезано во имя оптимизации:
  1. Использование кадра с уменьшенным размером. Значительно ускоряет работу. На форму не стал выводить управление размером кадра, но если откроете код, то строчка: "_capture.QueryFrame().Convert<Bgr, float>().PyrDown().PyrDown();" это оно
  2. Использование только одного пространственного фильтра. Для ситуации, когда известно желаемое движение потери некритичны. Управление параметром фильтра с формы (длинна волны фильтра Габора).
  3. Использование только одной частоты, подчёркивающей временной ряд. Конечно, можно было делать свёртку с заранее рассчитанным окном со спектром почти без потери производительности, но этот способ тоже неплохо работает. С формы управляется либо ползунком, либо вводом предельных значений.

Маленькая ремарка. Все результаты получены на обычной веб-камере в домашних условиях. При использовании камеры с хорошими параметрами + штатива + правильного освещения + подавления 50ГЦ помехи качество значительно улучшится. Моей целью не было получение красивой картинки или улучшенного алгоритма. Цель – добиться результата в домашних условиях. Ну, как бонус, хотелось бы ещё сделать запись пульса когда я играю в Starctaft 2… Любопытно же, насколько e-sport таки спорт.

В итоге логика работы получается:



Всё просто до безобразия. Например суммирование прирощения с кадром реализовано вообще так:

for (int x = 0; x < Ic[ccp].I.Width; x++)
  for (int y = 0; y < Ic[ccp].I.Height; y++)
  {
      FF2.Data[y, x, 0] = Alpha * FF2.Data[y, x, 0] / counter;
      ImToDisp.Data[y, x, 0] = (byte)Math.Max(0, Math.Min((FF2.Data[y, x, 0] + ImToDisp.Data[y, x, 0]), 255));
   }

(Да, я знаю, что при наличии OpenCV это не оптимальный способ).

Где-то 90% кода это не ядро, я обвес вокруг него. Но реализация ядра даёт уже неплохой результат. Видно как раздувается грудная клетка на пару десятков сантиметров при дыхании, видно как набухает вена, как качается голова в такт пульса.





Вот тут подробно объясняется, почему качается голова от пульса. По сути это отдача от вброса крови сердцем:



Немножко про красоту


Конечно, в MIT любят красивые результаты. И, поэтому, стараются сделать их как можно красивее. В результате у смотрящего создаётся впечатление, что эта частность это и есть целое. К сожалению нет. Разбухающую вену можно увидеть только при правильно поставленном освещении (тень должна рисовать узор кожи). Изменение цвета лица — только на хорошей камере без автокоррекции, с правильно поставленным светом и человеком, у которого имеются явные сложности с сердцем (в видео это грузный мужчина и недоношенный ребёнок). Например в примере с негром, у которого с сердцем всё хорошо, вы видите не колебание яркости кожи, а усиление изменения тени из-за микродвижений (тень аккуратно лежит сверху вниз).

Количественных характеристики


Но всё же. В видео явно видны дыхание и пульс. Давайте попробуем их получить. Самое простое, что приходит в голову — просуммированная разница между соседними кадрами. Так как при дыхании колеблется почти всё тело — эта характеристика должна быть заметна.
Полученный график прогоним через Фурье-преобразование, посчитав спектр (на графике набрана статистика где-то за 5 минут суммированием спектра, рассчитанного по 16-секундным отрезкам).



Виден явный пик на частотах 0.6-1.3, не свойственный шуму. Так как дыхание не синусоидальный процесс, а процесс, имеющий два явных всплеска (при вдохе-выдохе), то частота разностной картинки должна равняться двойной частоте дыхания. Частота дыхания у меня была где-то 10 вдохов за 30 секунд (0.3 HZ). Её удвоение — 0.6HZ. Что приблизительно равно выявленному максимуму спектрограммы. Но, понятно, о точном значении говорить не приходится. Кроме дыхания вытягивается множество мелкой моторики тела, которая значительно портит картину.
Имеется интересный пик на 2.625HZ. Судя по всему это пробивается наводка электросети на матрицу. По матрице ползут полосы, которые успешно дают максимум на этой частоте.

Между прочим, двойная частота пульса должна лежать примерно в том же диапазоне, а значит этот метод не должен на ней сработать. И действительно:



В таком спектре найти пульс нельзя.

В одной из работ MIT приведён другой способ для измерения частоты пульса: вычислять оптический поток на лице и определять его по частоте этого потока. Так я и сделал (на графике тоже спектры):




Лучше видно на графике на котором я откладывал количество максимумов спектра:



Почему максимум на частоте пульса *3 я не знаю как объяснить, но этот максимум точно есть и завязан на пульс:)
Хотелось бы отметить только, что для получения пульса таким способом нужно сидеть прямо и не двигаться. При игре в Старкрафт это невозможно, частота не снимается. Эх… А такая задумка! Придётся добывать пульсометр, ведь интересно теперь стало!

Итак, результат


В результате я достаточно чётко сформировал своё мнение о границах алгоритма, мне стало понятно, какие у него ограничения:
Почему он не стал популярным для измерения пульса? Качества для Web-камер компьютера хватает на границе, а то и не хватает. У android явно не хватит производительности. Остаются спецсредства для профессионального измерения. Но они будут очень дорогими и не стабильными к внешним условиям (засветка, мерцающий свет, темнота, тряска), а качество будет ниже, чем у проверенных средств съёмки пульса.
Почему алгоритм не используется для оценки колебаний домов, мостов, кранов? Опять же. Спецсредства дешевле и дают большую точность.
А где же его можно использовать и можно ли вообще? Думаю, что можно. Везде где нужна наглядность. Научные видеосъёмки, образовательные программы. Тренинг психиаторов, психологов, пикаперов (видны мельчайшие движения человека, усиливается мимика). Для анализа переговоров. Конечно, при этом использовать нужно не простую версию алгоритма, а ту версию, которая у них в последней работе и основана на фазовом подходе. При этом в реальном времени всё это сложно будет увидеть, производительности не будет хватать, разве что на видюхе всё распаралелить. Зато можно посмотреть постфактум.

Ничего не ново под луной


Когда читаешь работы товарищей и смотришь видео закрадывается подозрение. Где-то я всё это видел. Вот смотришь и думаешь, думаешь. А потом они показывают видео того, как с помощью этого же алгоритма берут и стабилизируют движение Луны, убирая шумы атмосферы. И тут как вспышка: «Да это же алгоритм подавления шумов, только с положительной обратной связью!!». И вместо того, чтобы подавлять паразитные движения, он их усиливает. Если взять α<0, тогда связь опять отрицательная и движения уходят!
Конечно, в алгоритмах подавления движения и тряски чуть другая математика и чуть другой подход. Но ведь по сути ровно тот же спектральный анализ пространственно-временной трубки.
Хотя говорить, что тут свиснули алгоритм глупо. В MIT реально заметили одну маленькую интересную особенность, развили её и получили целую теорию с такими красивыми и магическими картинками.

И напоследок: программист, будь аккуратен!


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

Подвал


Сайт про исследования MIT на тему усиления движения;
Мои исходники.

З.Ю. А подскажите пульсометр, который бы мог данные на комп скидывать и, желательно, какой-нить интерфейс под Android имел?
Поделиться публикацией
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 44
  • 0
    Хм. что-то с habrastorage.org/, он половину картинок не отдаёт статье. Сейчас поправить попробую.
    • 0
      Перезалил в другое место, теперь должно всё работать.
    • +1
      Это невероятно круто, но математика явно не для воскресной ночи.
      Надо будет днём по-нормальному во всё это въехать, код посмотреть, подумать.
      • +3
        Спасибо. В первые увидил дельную статью по теме, объясняющую плюсы и минусы.
        • 0
          Видимо у кого-то припекает. Но я искренне не понимаю кому и чем не угодил мой коментарий. Я вполне искренне сказал что впервые ( по крайней мере для себя ) увидел более или мене объективную статью по поводу данного алгоритма… Не знаю может я от жизни отстал или еще чего…
          • +9
            Подозреваю, что дело в "в первые увидил".
        • +1
          Определение пульса на смартфонах с помощью только лишь камеры (фронтальной, без прикосновения пальцем и тд) достаточно давно реализован в нескольких аппах, например в Cardiio. Принцип работы основан на разработках MIT Media Lab.
          • 0
            не знаете случайно android-версий? беглый поиск не помог.
          • +2
            Насколько я понял, принцип основан на изменении цвета лица и при плохом освещении уже не действует. Но все равно очень круто!
            • 0
              При недостаточно хорошем освещении программа использует стандартный метод с просвечиваением пальца вспышкой.
            • 0
              Но как я понимаю, активной подсветкой оно всё равно светит, она там говорят вовсю про «reflected light»?
              Эппл сторе я действительно плохо просматривал, думаю что у такой софтины должна была бы быть android — аналог, поэтому прорывал Play-market
              • 0
                Поиск показывает множество таких программ. На себе пробовал только Cardiograph.
                • 0
                  Они на затыкание пальцем или на анализ акселерометра все. Я их смотрел.
                  • +1
                    Плохо смотрели :) Вот такое приложение.
                    • 0
                      Круто! Сейчас потестирую.
                      • 0
                        А также есть похожее приложение и под iOS
                        • 0
                          youtu.be/xnuZ1kfVFPI
                          Захват пульса по фотографии. Они там на уровне шумов определяют… Не доверял бы я их показаниям...))
                          • 0
                            Печально( Сам раньше не пробовал, а тут андроид-девайса под рукой не оказалось. А вы фотку показывали камере вроде, да? Показалось, что совсем неподвижно лицо было. Если так, то может на реальное лицо среагирует?
                            • 0
                              Я показал фотку с планшета проге работающей на телефоне и снял камерой с компа)

                              Реальному лицу он тот же пульс выводит. То бишь скорее всего там какая-то реальная обработка, но выдающая произвольные результаты. Это примерно, как если бы я взял свой первый метод и сказал «он выводит пульс». Что-то бы он выводил. Но вот что? Некорректно поставленная задача в чистом виде.
                • +1
                  «Теперь могу видеть дождь...»
                  ))
                  • 0
                    Недавно ещё продемонстрировали, как с помощью видеозаписи можно считывать звук по изображению: www.youtube.com/watch?v=FKXOucXB4a8
                    • 0
                      Да, поподалось, но блин камера тысячу кадров в секунду… направленный микрофон или лазерный звукосниматель (кстати попроще дальномера должен делаться лазерного, а и того собирают в домашних условиях) подешевле и попрактичнее будут. ))
                      • 0
                        В последней части видеоролика показано, как то же самое проделывается с помощью камеры, снимающей 60 кадров в секунду, что куда более приближено к жизни.
                        • +1
                          Обратите внимание, что звук в конце ролика — гармонические колебания и довольно продолжительные (синтезатор играет). Есть такая теорема Котельникова (или Найквиста), что аналоговый сигнал (звук) можно восстановить при двойной частоте оцифровки. И, к сожалению, без априорных данных тут ничего не сделаешь. Ну например, спектр голоса и тем более музыки будет пошире 60Гц. Не говоря уж про случай, когда источников звука больше чем один и каждый в своей частоте. Если есть какие-то априорные данные о том, где ждем звук и какой, то можно и 60Гц. Но, как Антон и написал — «только подсветочку поставьте так, чтобы вены выделялись» ))). Эффектно, да. А по сути: расчитайте спектр по трубке плоская картинка — время и увидите спектр звука. Ну и под каждую задачу модифицировать алгоритм (подчеркнуть границы так или сяк). Но так-то здорово — пробуждает почти здоровый интерес к технике… прослушивающей технике у подрастающего поколения. У кого-то может длинный путь инженера начинался с усиления звука вибрации батареи ))).
                          • +1
                            Они вроде бы использовали свойства «катящегося затвора», чтобы увеличить частоту дискретизации. А насчет теоремы Котельникова, есть интересный блог nuit-blanche.blogspot.ru/, в котором освещаются новые разработки по теории compressed sensing, там есть масса примеров точного восстановления самых разнообразных сигналов при меньшей частоте дискретизации.
                            • 0
                              Да, если стоит задача и никаких других способов нет, то нужно бороться и при малой полосе. Если про сигнал что-то известно, то шанс есть. Но микрофон! обычный микрофон )))). почему бы не поставить
                    • 0
                      Впечатляет. Но непонятно, что делать с патентами, если захочешь что-то свое написать. У того же SURF, например есть свободные аналоги. А здесь?
                      • 0
                        Сложно сказать, где здесь патент вообще лежит и что он защищает. Нужно разбираться внимательно. Возможно, патентуется «усиление движения» — довольно спорно, что это нужно «в народном хозяйстве» (скорее оценка амплитуды и частоты полезно может быть). А математика, что лежит в основах алгоритма (ну кроме того, что в России вообще про патенты алгоритмов ничего не слышали), эквивалентно крутится. Ну например, спектр сигнала во времени — да всем известная вещь, фильтрация во времени — тоже, спектр в 2D x T — давно был, опять же фильтр применить — получатся до знака те же формулы. А если патентуется такая математика, то лично я не знаю, как стоит относиться в этом случае к патенту.

                        В SURF намного все интереснее, а тут же классическая обработка сигнала во временной и пространственных координатах. Но эффектно и неожиданно — это точно!
                        • 0
                          Это понятно. А вот что ожидать потом от того же google play, который по большим пустякам приложения выпиливает. Не хотелось бы потратить кучу времени, что бы выяснилось, что приложение нарушает патент. Я кстати, в свое время пытался связаться НАСА по-поводу алгоритма retinex, но безрезультатно. В итоге забил.
                      • +1
                        Здесь появляется простор для негласных методов анализа. Пример:
                        Собеседник пришел получать кредит или заключать контракт. Вы сидите напротив, ваша веб-камера направлена на него. На вашем мониторе в реальном времени пишется уровень стресса, пульс собеседника и другая аналитика, помогающая в приятии решения или в психологическом давлении на оппонента.
                        Пример №2:
                        Анализ записи выступления политика/известного деятеля/журналиста с целью прогнозирования стресса и лжи.
                        • 0
                          Рик Декард одобряет :)
                          • +1
                            Анализ записи выступления политика/известного деятеля/журналиста с целью прогнозирования стресса и лжи.


                            Сразу вспомнил байку
                            В одном отделе МУРа некоторое время успешно действовал детектор лжи. Было это в 70-х годах, когда о подобном приборе бытовали весьма фантастические представления.

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

                            Секрет же прибора заключался в том, что единственным действующим элементом его была лампочка, которую включали ногой под столом, когда допрашиваемый говорил неправду. Истинным детектором являлся сыщик, владелец аппарата, но ему воры и мошенники врать не стеснялись, ведь так принято; зато детектор лжи — другое дело, он вселял трепет пред могуществом науки.

                            Прикрыл это дело начальник — генерал-майор милиции, который каким-то образом прознал про детектор и явился проверить. Раскрывать ему правду не хотелось, но внятно объяснить происхождение прибора тоже не сумели. Да еще дернул черт нажать на кнопку во время тирады генерала про служебный долг и уважение к закону. Лампочка вспыхнула, следом за ней вспыхнул генерал и в расстроенных чувствах вылетел из комнаты. Кончилось дело тем, что он наклепал на самозваных экспериментаторов в КГБ, и соответствующие товарищи быстро и без лишних слов изъяли прибор. Надо полагать, что они разобрались в его устройстве, но вс, же обратно не вернули. Наверное, самим пригодился.

                            Источник: bajki.narod.ru/mb04.html
                            • 0
                              Ложь для профессионального политика — основа его карьеры, скорее всего волнуется когда правду говорит.
                              • +1
                                «Как определить что политик врет? Очень просто — у него губы шевелятся.»(с)нар.мудр.
                          • 0


                            Для тех, кто спешит — с 1:59.

                            UPD: промахнулся веткой, предназначалось комментарию выше.
                            • 0
                              Интересно, а можно ли видеть в почти темноте?
                              • 0
                                Где-то уже маячит стартап «only-real-orgasms.com»…
                                • 0
                                  Нечто похожее
                                  www.zbs-ilmenau.de/pdf/FWS2014_Stricker.pdf
                                  такой вот автомат, я так понимаю пульс меряет по цвету кожи, пейпер от 2014 года.

                                  а если загуглить «remote pulse measurement» то можно наткнуться и на такую статью
                                  web.media.mit.edu/~zher/papers/Poh-etal-OptExp.pdf

                                  Даже вот как то и не вериться, что это работает.
                                  • 0
                                    Так наши отечественные гении уже давно используют регистрацию микродвижений для распознавания эмоций и психоэмоционального состояния человека. Подробности: http://www.psymaker.com/ru/vibraimage/
                                    • 0
                                      То что кто-то что то продаёт ещё не значит что оно работает. Нет достаточно достоверных данных что и обычный детектор лжи работает.
                                      А эти ребята способности и склад характера людей определяют по «отпечаткам пальцев». Так что 100% это разводка:)
                                      • –1
                                        А почему Вы считаете, что способности нельзя по отпечаткам пальца определять? Вот их обоснование http://www.elsys.ru/downloads/reports/DermatoglyphicsBases.pdf выглядит вполне правдоподобно.
                                        А учитывая, что физиогномика (родственная дерматоглифике наука) уже давно доказала свою состоятельность, думается, что в этом что-то есть…
                                        • –1
                                          Я имел ввиду, что они умеют выделять микродвижения, ведь статья об этом… А вот по поводу алгоритмов обработки и корреляции с настоящими эмоциями это нужно проверять…
                                      • 0
                                        Похоже ещё 1 реализация:
                                        https://github.com/tschnz/Realtime-Video-Magnification

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