AlphaFill

Наряду с мощными библиотеками распознавания образов со сложными математическими методами, данная библиотека AlphaFill разрабатывается как простейщая альтернатива с использованием логических методов.
Альтернативой Connected-component labeling разработал алгоритм заливки связаных пикселей индивидуальным индексом, помещаемым в Alpha-биты RGBQuad.
На официальном сайте можно найти исходный код библиотеки, демонстрационную программу и описание библиотеки.

На данный момент в библиотеку включены три функции:

Также, функция ALPHA_Fill заполняет таблицу координат прямоугольников объектов. (вместо отдельной ALPHA_Cage)
Функция переписана заново и устранились некоторые недочёты прошлой версии. Теперь размер кадра может быть любым. Ведётся нормальный контроль достижения границ (без предварительного глушения пикселей, как ранее), одновременно введена возможность окраска подавленного фона выбранным цветом либо заданным изображением. Алгоритм насчитывает 198 инструкций (против 210 со всякими "костылями" ПЛЮС встроенный "ALPHA_Cage").

Функция ALPHA_Cage устарела и исключена из состава.

Когда мне понадобилось пользоваться в конференциях вэб-камерой, которой у меня нету до сих пор, я скачал ManyCam, чтобы с обычного видео глазка и платы захвата устроить вэб-конференцию.
Изучение возможностей утилиты меня озадачило в работе с chroma-screen для замены заднего плана комнаты на собственный. Оказалось, что ресурсов уходит порядочно и падает средний рейтинг кадров!
Это было летом 2010. В декабре, когда появилось настроение, я сел исследовать этот вопрос.
Сначала сделал два снимка комнаты с камеры со мной и без. Затем грубым способом в html странице посредством JavaScript и тэга canvas попробовал отделить собственное изображение от фона. Получилось! Снял серию кадров и получил около 50 кадров в минуту. Что ж, для JavaScript не так и плохо...

Затем открыл VC-проект. Написал, опять-таки, дубовый код через GetPixel/SetPixel и захвата кадра из окна VirtualDub. Прорисовка с отделением фона производилась на глазах со скоростью до 100 кадров в минуту. Надо было браться всеръёз.
Написал более нормальный код с работой над массивом пикселей прямо в памяти. Скорость достигала сотни кадров в секунду, хотя источником потока служил всё тот же VirtualDub. Фон подменялся, но имел уйму помех и "дыр". Нужно было писать фильтр.
Однако, все кадры имели 24 бита на пиксел и было очень неудобно производить операции. Так как отдельные карты служили тупо для AND-блиттинга, т.е. масками.
Пришлось всё перелопачивать на 32 бита с использованием Alpha-битов как маску. Алгоритм упростился и вместо кучи API-BitBlt комбинаций ввёлся цикл с копированием/отсеиванием слов прямо в памяти. Приступил к фильтрации.

Первое, что пришло в голову, это медианный способ. Начал иследовать окружающие пикселы и оценивать по количеству. Если их менее порогового значения, тестируемый пиксел считался помехой и гасился. Тем самым, картинка стала чище, но не идеально. Пришлось варьировать количеством опрашиваемых соседей аппертуры от 3x3 до 9x9. И понял таки, из-за чего ManyCam тормозит! Именно такая фильтрация является узким местом!

Недолго думая над тем, как отфильтровывать значительные помехи (от мелких "мушек" до крупных "жуков") я обратился к очень давнему и классическому алгоритму заливки замкнутых фигур. Ведь только им можно подсчитать количество пикселей в контуре с абсолютной точностью. Причём, производительность упадёт несущественно. Однако, у меня контур лежит за рамками RGB-области, в районе Alpha-канала. Придётся писать собственную функцию!

Так, все пикселы, которые отличаются от фона, получают код 0xFF в свой Alpha-канал. Остальные - ноль.
Функция заливки ищет пикселы с FF-кодом и начинает их "окрашивать" порядковым индексом от 1 до 254, на ходу подсчитывая число пикселей. Если количество ниже желаемого порога, область считается "помехой" ("мушкой" или "жуком") и повторно заливается, теперь уже нулями.
Тем самым, в отличии от медианного способа, метод заливки не так сильно тормозит систему и попутно создаёт список объектов с их размером.

Провозился весь декабрь и даже 31-го числа сидел перед голубой зановеской, мешая близким серверовать праздничный стол!
В итоге, перевёл на уровень ассемблера с mmx-инструкциями саму процедуру отделения фона, а также и процедуру заливки.  Которая показала себя на порядок лучше и быстрее, чем выдаёт официальные продукты - ManyCam и SplitCam.
И весь январь показывал племяннице, как в её любимых фильмах всё делают с помощью дешёвой графики.

Вот только терзает вопрос: Почему нигде не написано о применении алгоритма заливки для выделения областей в изображении и очистки от шума? Упоминается Connected-component labeling, требующий несколько проходов и часто не позволяющий разумно втиснуться в один байт Alpha-компоненты.

Гугл не даёт желаемых результатов. Хотелось бы знать, используются ли алгоритмы заливки в таком качестве и кто первый догадался их так использовать?
(Нашёл в http://zibben.narod.ru/ файл pdf-файл со словами заливка и обнаружил лишь построчную заливку.)

Если зрительно исследовать сам процесс заливки, не трудно заметить, что различные помехи имеют рванную структуру. Тогда как силуэт человека, кисти руки или другого предмета будут иметь более проявленную геометрическую форму.
Пока на практике я это не проверял и мне нужно продумать детали переделки алгоритма.

Итого. С помощью генерации рандомного шума в программе-тестере я оценил производительность моей процедуры заливки, которую сократил до 144 инструкций основного цикла, выбросив значительную часть ветвлений, заменив на вычислительные манипуляции и добавив сохранение промежуточного значения в регистре mm1. Проверка производительности заняла одну минуту в приоритете REALTIME_PRIORITY_CLASS:

XXXXxYYYY MIN..MAXfps  MIN..MAXmtps MIN..MAXtpp <- Горизонтальный зиг-заг
4096x4096   4..8  fps ~268..569mtpf  15..33tpp
3072x2304   9..9  fps ~240..242mtpf  34..34tpp
2048x1536  22..22 fps ~107..107mtpf  34..34tpp
1536x1152  38..39 fps ~ 60..61 mtpf  34..34tpp
1280x960   55..56 fps ~ 42..42 mtpf  34..34tpp
1024x768   85..86 fps ~ 27..28 mtpf  35..35tpp
 800x600  131..133fps ~ 18..18 mtpf  37..38tpp
 768x576  141..143fps ~ 16..16 mtpf  37..38tpp
 704x576  137..151fps ~ 15..17 mtpf  39..42tpp
 640x480  173..195fps ~ 12..13 mtpf  39..44tpp
 352x288  793..948fps ~  2..3  mtpf  24..29tpp
 320x240 1072..1251fps~  1..2  mtpf  24..29tpp
XXXXxYYYY MIN..MAXfps  MIN..MAXmtps MIN..MAXtpp <- Вертикальный зиг-заг
4096x4096   0..8  fps ~268..6681mtpf 15..398tpp
3072x2304   0..8  fps ~268..2653mtpf 37..374tpp
2048x1536   2..8  fps ~268..1172mtpf 85..372tpp
1536x1152   4..8  fps ~268..581mtpf 151..328tpp
1280x960    8..8  fps ~268..297mtpf 218..241tpp
1024x768    8..8  fps ~268..272mtpf 341..346tpp
 800x600   56..58 fps ~ 41..42 mtpf  85..89 tpp
 768x576   40..41 fps ~ 57..59 mtpf 131..134tpp
 704x576   71..72 fps ~ 33..33 mtpf  82..83 tpp
 640x480   93..99 fps ~ 24..25 mtpf  78..83 tpp
 352x288  475..529fps ~  4..5  mtpf  44..49 tpp
 320x240  541..764fps ~  3..4  mtpf  40..57 tpp
Resolution FPS      MTPF    TPP   <- Статический зашумлённый текст
4096x4096  2…8   ~268..945 15…56  
3072x2304  6…8   ~268..366 37…51  
2048x1536 13…15  ~158..176 50…56  
1536x1152 27…28  ~ 84..87  47…49  
1280x960  39…42  ~ 56..60  45…48  
1024x768  61…64  ~ 37..38  47…49  
 800x600 107…114 ~ 20..22  43…46  
 768x576 113…124 ~ 19..21  43…47  
 704x576 126…135 ~ 17..18  43…46  
 640x480 153…179 ~ 13..15  43…50  
 352x288 637…706 ~  3..3   33…37  
 320x240 934…1047~  2..2   29…33  

°fps - Frames Per Second (for Pentium-IV 2.4GHz (no HT), Radeon-7000 64Mb)
°tpp - Ticks Per Pixel (divide Ticks Per Frame by Frame Size)
°mtpf- MegaTicks Per Frame (divide Ticks Per Frame by million)

Как правило, заполнение вертикальных линий предельно напрягает процессор на больших разрешении и сравнивая все три таблицы, получим оценку в целом
Можно заметить очень даже не плохой результат.
Так, если захватывать поток с вэб-камеры при разрешении 640x480@30, моя процедура займёт всего около 17 млн тактов. Т.е. практически ничего, в сравнении с дальнейшими остальными вычислительными затратами последующей обработки кадра.

P.P.: В данный период веду разработку VirtualDub фильтра с моим алгоритмом. Благодаря отточенности быстродействия, позволяет выполнять линейные операции с фоном без особых проблем.
Думаю, скоро могу выложить его для публичной оценки.

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

Самое сложное - определить нормальные имена функций. Так, AlphaFill_Separation и AlphaFill_Indexing уж черезчур закрученные.
Здесь на распутье имён важно раз на совсем твёрдо решиться, чтобы не переименовывать десятки раз!
Скажем, возьмём библиотеки Bass и FMod, где имя функции префиксируется именем библиотеки.
На данный момент имеется три функции и они переименованы:
ALPHA_Mask - создаёт Альфа-маску по дифференции двух кадров;
ALPHA_Fill - заливает Альфа-индексом объекты кадра с зачисткой, определяет прямоугольные границы объектов, заменяет фон;
ALPHA_Cage - устарела и исключена.