Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 16.10.2012, 02:50
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

Фильтрация заливкой vs медианной
Пользуясь виртуальными вэб-камерами ManyCam и SplitCam заметил, что отделение фона достаточно прилично снижает производительность, по-видимому, медианным фильтром. Причём, шум всё же пробивается в виде моршин и складок или вспышек огней гирлянд за спиной.

С декабря 2010 я занялся своим способом фильтрации, используя не математический медианный автомат, а классический алгоритм заливки фигур с подсчётом содержащихся пикселей. Если их число меньше порогового, фигура кадра считается помехой и повторной заливкой удаляется (пусть даже она в ⅓ кадра).
Никакие RGB не трогаются, только Alpha. Потому все годные объекты кадра заливкой попутно индексируются от 1 до 253 с сохранением объёма пикселей в таблице.
Тем самым, после такой фильтрации можно по Альфа-индексу находить отдельные объекты, сортировать по размеру, исключать из кадрам и производить операции (зеркало, перемещение, дублирование).

Сам алгоритм заливки изначально писался на Си. Сейчас он представляет всего 144 инструкции ассемблера законченного кода и требует от 15 тактов на пиксел до 400, в зависимости от сложности фрейма.
(исключены все ветвления методом вычисления, задействованы все регистры, включая mm0 для промежуточных указателей)

Ниже представляю таблицу для оценки (можно заметить, бег по вертикали сильно бьёт по производительности):
Код:
Разрешение Кадр/сек.  Млн.такт/кадр Такт/пиксел: Шумный текст на шуме
4096x4096   2..8  fps ~268..960mtpf  15..57 tpp
3072x2304   5..8  fps ~268..418mtpf  37..59 tpp
2048x1536  12..13 fps ~172..185mtpf  54..58 tpp
1536x1152  23..25 fps ~ 95..101mtpf  53..57 tpp
1280x960   34..37 fps ~ 63..69 mtpf  51..56 tpp
1024x768   53..57 fps ~ 41..45 mtpf  53..57 tpp
 800x600   89..100fps ~ 23..26 mtpf  49..55 tpp
 768x576   96..108fps ~ 22..24 mtpf  49..56 tpp
 704x576  109..118fps ~ 20..21 mtpf  49..54 tpp
 640x480  134..156fps ~ 15..17 mtpf  49..58 tpp
 352x288  480..612fps ~  3..4  mtpf  38..49 tpp
 320x240  711..845fps ~  2..3  mtpf  36..43 tpp
Разрешение Кадр/сек.  Млн.такт/кадр Такт/пиксел: Горизонтальный зиг-заг
4096x4096   4..8  fps ~268..569mtpf  15..33 tpp
3072x2304   9..9  fps ~240..242mtpf  34..34 tpp
2048x1536  22..22 fps ~107..107mtpf  34..34 tpp
1536x1152  38..39 fps ~ 60..61 mtpf  34..34 tpp
1280x960   55..56 fps ~ 42..42 mtpf  34..34 tpp
1024x768   85..86 fps ~ 27..28 mtpf  35..35 tpp
 800x600  131..133fps ~ 18..18 mtpf  37..38 tpp
 768x576  141..143fps ~ 16..16 mtpf  37..38 tpp
 704x576  137..151fps ~ 15..17 mtpf  39..42 tpp
 640x480  173..195fps ~ 12..13 mtpf  39..44 tpp
 352x288  793..948fps ~  2..3  mtpf  24..29 tpp
 320x240 1072..1251fps~  1..2  mtpf  24..29 tpp
Разрешение Кадр/сек.  Млн.такт/кадр Такт/пиксел: Вертикальный зиг-заг
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
Тестирование заняло одну минуту зависания в REALTIME_PRIORITY_CLASS с использованием RDTSC. Примерный fps расчитывался из тактовой частоты (Pentium-IV 2.4GHz).

Почему я не могу выгуглить описание и оценку официального фильтра заливкой для сравнения с моим?

Вот демка:

Последний раз редактировалось Vertex, 16.10.2012 в 03:07.
  #2  
Старый 16.10.2012, 14:53
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Речь идет об объединении пикселов в группы (что-то типа connected component labeling) по совпадению (или близости) цвета?

В OpenCV подобного случайно нет?
  #3  
Старый 29.11.2012, 08:41
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

FloodFill
По цвету или нет, у меня делается следующее:
Допустим в Paint'е мы нарисовали сотню эллипсов разного размера белого цвета заливки.
Наша задача состоит в том, чтобы подсчитать число пикселей в каждом эллипсе. А наиболее эффективно это сделать FloodFill-трассировкой. Т.е. выполнить обычную GDI-FloodFill заливку. С той разницей, что нужно подсчитывать количество пикселей.
Если это число меньше требуемого, считаем фигуру слишком малой, незначительной. Т.е. помехой. И заливаем нулями.

У меня процесс идёт только в Альфа-битах (RGBQUAD rgbReserved).
У меня не слишком накрученный математический аппарат. Просто беру два кадра - текущий и предыдущий. Вычитаю их попиксельно, сравнивая RGB и по результатам вычитания записываю в rgbReserved 0x00 или 0xFF.
А потом все эти 0xFF цепочки FloodFill'ю индексами от 1 до 254. Получаю в кадре до 254 объектов (связанных областей пикселей).

Мне советовали использовать SIMD-технологию, чтобы махом по 4-16 пикселей заливать, так-как путали мою заливку с заливкой-фильтром, где просто пиксел гасится, если вокруг него пусто. Или зажигается, если вокруг него полно соседей.
Но в моём случае это не такая заливка с линейным сканированием кадра. У меня используется стек координат и позиция нелинейно блуждает по пикселам объекта.
  #4  
Старый 03.12.2012, 06:33
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Посмотри всё-таки упомянутый алгоритм connected component labeling, он прост в реализации.
  #5  
Старый 14.12.2012, 08:34
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

Connected-component labeling
Хм, в принципе, да: Connected-component labeling - это моя т.н. заливка.
Однако стандартный CCL-алгоритм - линейный и требует несколько проходов. А если из-за разрыва индекс выходит за рамки байта, это становится проблемой. Кстати, я одно время пытался преодолеть препятствие. Но, в конце-концов решил, что FloodFill-заливка много удобнее. Хотя, с виду выглядит несколько сложнее.

Как я показал в gif'ке, алгоритм работает, весь расписан на ассемблере и порядок инструкций оптимизирован (проверял перестановкой инструкций с подсчётом тактов).

Кстати, эта тема - не вопрос, а просто делюсь опытом с альтернативными методами.

Последний раз редактировалось Vertex, 14.12.2012 в 08:41.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра