Векторизация изображений

Для всех любителей и профессионалов этого нелегкого дела.

Модераторы: Почётные модераторы, Модераторы "Программирование"

Векторизация изображений

Сообщение Diablo » 13 окт 2010, 08:13

Имеется следующий код:
Код: Выделить всё
//(c)The Diablo, HELL Unlimited. All Rights Reserved. Distributed under the GNU General Public License.
#define uchar   unsigned
#define chkPixel(x,y,w,h)
#ifdef  BMP
void setPixel(char *raw,int w,int h,int x,int y,uchar r,uchar g,uchar b)
 {chkPixel(x,y,w,h){int i=(w*(h-y-1)+1+x)*3;raw[i-1]=r;raw[i-2]=g;raw[i-3]=b;}}
#else
void setPixel(char *raw,int w,int h,int x,int y,uchar r,uchar g,uchar b)
 {chkPixel(x,y,w,h){int i=(w*y+x)*3;raw[i]=r;raw[i+1]=g;raw[i+2]=b;}}
#endif

void getPixel(char *raw,int w,int h,int x,int y,uchar *r,uchar *g,uchar *b)
 {chkPixel(x,y,w,h){int i=(w*y+x)*3;*r=raw[i];*g=raw[i+1];*b=raw[i+2];}}

void RedEyeVec(char *raw,int w,int h,int *v,int s){int i,x,y;unsigned r,g,b,R,G,B;
 for(y=0;y<h;y++)for(getPixel(raw,w,h,0,y,&R,&G,&B),x=1;x<w;x++){getPixel(raw,w,h,x,y,&r,&g,&b);i=x+y*w-1;
  if(abs(r+g+b-R-G-B)>s)v[i>>3]|=0x00000001<<(i&7);R=r;G=g;B=b;}//x
 for(x=0;x<w;x++)for(getPixel(raw,w,h,x,0,&R,&G,&B),y=1;y<h;y++){getPixel(raw,w,h,x,y,&r,&g,&b);i=x+y*w-1;
  if(abs(r+g+b-R-G-B)>s)v[i>>3]|=0x00000100<<(i&7);R=r;G=g;B=b;}//y
}

int i=w*h/2,vs=i,*vec=(int*)malloc(i);memset(vec,0,i);

RedEyeVec(pnm,w,h,vec,3*10);

fsize=w*h*3;char *raw=(char*)malloc(fsize);memset(raw,255,fsize);
int x,y;
for(y=0;y<h;y++)for(x=1;x<w;x++){i=x+y*w-1;if(vec[i>>3]&(0x00000001<<(i&7)))setPixel(raw,w,h,x,y,0,0,0);}//x
for(x=0;x<w;x++)for(y=1;y<h;y++){i=x+y*w-1;if(vec[i>>3]&(0x00000100<<(i&7)))setPixel(raw,w,h,x,y,0,0,0);}//y

Суть кода - преобразование растровой картинки в контуры - там где есть резкая смена яркости получаем черную точку, иначе белый фон (255).
Суть проблемы - медленно - функция RedEyeVec обрабатывает примерно 20 кадров 640*480 в секунду на PentiumD 820 (2.8GHz)
Какие будут предложения? Склоняюсь к тому, чтобы переписать ф-цию на асме...
ЗЫ Все права защищены. Распостраняется по лицензии GNU GPL.
RedEye.png
RedEye
RedEye.png (13.86 КБ) Просмотров: 4751
Изображение
Аватара пользователя
Diablo
Флудер
 
Сообщения: 997
Зарегистрирован: 25 сен 2007, 12:42

Re: Векторизация изображений

Сообщение Diablo » 13 окт 2010, 09:33

Всё надо делать в реальном времени (см. сюдЫ) - потому так важно быстродействие...
Нашел прогу potrace - то что надо, но на входе должно быть ч/б. Скорость еще не проверял.
исходное изображение
Вложения
RedEye.rar
моя конверсия плюс векторизация potrace
(54.01 КБ) Скачиваний: 6
Изображение
Аватара пользователя
Diablo
Флудер
 
Сообщения: 997
Зарегистрирован: 25 сен 2007, 12:42

Re: Векторизация изображений

Сообщение Seven » 13 окт 2010, 10:03

В код не вникал, но бросилось в глаза
Код: Выделить всё
#define uchar   unsigned

т.е. беззнаковый чар делается беззнаковой шиной. (unsigned = unsigned int)
и еще, копай в сторону многозадачности (используй все ядра и процессоры)
и еще: иногда цикл вертят пока не выполнится какое то условие, а после его выполнения цикл вообще останавливают.... может тут тоже надо (повторю, в код не вникал)
Аватара пользователя
Seven
 
Сообщения: 1272
Зарегистрирован: 25 сен 2007, 09:12
Откуда: Магнитогорск

Re: Векторизация изображений

Сообщение aps » 13 окт 2010, 14:26

Если нужно засечь резкие изменения ЯРКОСТИ то зачем обрабатывать цветную картинку? Она же в три раза больше черно-белой . Если цвета жалко, в любом случае лучше обрабатывать весь пиксель сразу, а не по 3 цветовым составляющим-это будет куда как быстрее. Ну а дольше всего, конечно работает GetPixel. Кто же GDI функции использует там где быстродействие нужно :) . Лучше бери указатель на всю картинку, и работай с картинкой, как с массивом. Ну или DirectDraw юзай.
aps
 
Сообщения: 319
Зарегистрирован: 09 фев 2009, 01:41

Re: Векторизация изображений

Сообщение Diablo » 13 окт 2010, 15:18

Seven писал(а):В код не вникал, но бросилось в глаза
Код: Выделить всё
#define uchar   unsigned
т.е. беззнаковый чар делается беззнаковой шиной. (unsigned = unsigned int)

да, тест показал, что целочисленные(int) операции выполняются быстрее, чем char - процы то давно 32-битные, как минимум
Seven писал(а):и еще, копай в сторону многозадачности (используй все ядра и процессоры)

Обязательно буду) Но пока проц только двух-ядерный - прирост будет макс.100% - мне всё-равно с двух камер надо сразу обрабатывать, так что скорость будет та же
Seven писал(а):и еще: иногда цикл вертят пока не выполнится какое то условие, а после его выполнения цикл вообще останавливают.... может тут тоже надо (повторю, в код не вникал)

Ну это вряд-ли получится, т.к. приходится сравнивать ВСЕ(у меня только по гориз и верт) соседние пиксели
aps писал(а):Если нужно засечь резкие изменения ЯРКОСТИ то зачем обрабатывать цветную картинку? Она же в три раза больше черно-белой. Если цвета жалко, в любом случае лучше обрабатывать весь пиксель сразу, а не по 3 цветовым составляющим-это будет куда как быстрее.

Ессно, цветная в 3 раза больше, но для того чтоб обрабатывать grayscale, её сначала надо получить из цветной - тут же сразу делается эта грязная работа...
Камера выдает картинку в PJPG - вряд-ли есть быстрый(на асме) алгоритм для распаковки в режиме ч/б
А как можно обработать сразу весь пиксель? Например, если он серый 0x007F7F7F(альфа-канал не используется)
Прочитать конечно можно и 4 байта сразу в int, но как потом два таких int сравнивать? В любом случае надо будет делать сдвиг...
На асме можно сделать, что-то вроде:
Код: Выделить всё
lodsd ;esi-pointer, eax - 24/32-bit color
mov dx,ax ;duplicate
ror dx,16 ;high-part of eax
add al,ah
add al,dl

Но тогда возникает проблема с переполнением 8-битного регистра AL, придется проверять CARRY и куда-то сохранять старшую часть...
aps писал(а):Ну а дольше всего, конечно работает GetPixel. Кто же GDI функции использует там где быстродействие нужно :) . Лучше бери указатель на всю картинку, и работай с картинкой, как с массивом. Ну или DirectDraw юзай.

дык у меня и так вся картинка в памяти, как массив(char *raw), getPixel - самописная функция, никаких GDI & DirectRraw - це Linux)
Код: Выделить всё
void getPixel(char *raw,int w,int h,int x,int y,uchar *r,uchar *g,uchar *b)
{chkPixel(x,y,w,h){int i=(w*y+x)*3;*r=raw[i];*g=raw[i+1];*b=raw[i+2];}}

Возможно, стоит задействовать OpenGL и более модную CUDA, но у меня видюха слабенькая - GF6200LE
В принципе, 20fps не так мало - вся картинка обрабатывается за 50ms, но хочется быстрее...
Мне же еще кучу другой работы надо успеть выполнить, а она посложнее будет...
Изображение
Аватара пользователя
Diablo
Флудер
 
Сообщения: 997
Зарегистрирован: 25 сен 2007, 12:42

Re: Векторизация изображений

Сообщение Diablo » 13 окт 2010, 20:50

Итак... После небольших манипуляций, скорость выросла более чем в ДВА(!!!) раза
Код: Выделить всё
void RedEyeVec(char *raw,int w,int h,int *v,int s){int i,x,y;unsigned r,g,b,R,G,B;
 for(y=0;y<h;y++)for(i=w*y*3,R=raw[i],G=raw[i+1],B=raw[i+2],x=1;x<w;x++)
  {i=(w*y+x)*3;r=raw[i];g=raw[i+1];b=raw[i+2];i=x+y*w-1;if(abs(r+g+b-R-G-B)>s)v[i>>3]|=0x00000001<<(i&7);R=r;G=g;B=b;}//x
 for(x=0;x<w;x++)for(i=  x*3,R=raw[i],G=raw[i+1],B=raw[i+2],y=1;y<h;y++)
  {i=(w*y+x)*3;r=raw[i];g=raw[i+1];b=raw[i+2];i=x+y*w-1;if(abs(r+g+b-R-G-B)>s)v[i>>3]|=0x00000100<<(i&7);R=r;G=g;B=b;}//y
}

Функцию getPixel засунул(4 раза) непосредственно в RedEyeVec
Итого, около 20ms на картинку 640*480 - т.е. 50fps - вполне устраивает) На асме будет еще быстрее)
Выводы: в данном случае большая часть времени расходуется на передачу управления(и кучи переменных) другой функции.
Код: Выделить всё
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name   
100.00      0.02     0.02        1    20.00    20.00  RedEyeVec(char*, int, int, int*, int)
  0.00      0.02     0.00    37370     0.00     0.00  setPixel(char*, int, int, int, int, unsigned int, unsigned int, unsigned int)
  0.00      0.02     0.00        1     0.00     0.00  bmpInit(BmpHdr*, int, int)
Изображение
Аватара пользователя
Diablo
Флудер
 
Сообщения: 997
Зарегистрирован: 25 сен 2007, 12:42

Re: Векторизация изображений

Сообщение Minimaks » 13 окт 2010, 21:49

Есть же простые быстрые оптимизированные функции, которые занимаются такого рода обработкой изображений - может сорцы гимпа проще покапать чем свой велик изобретать?
ОП ООО "Минимакс (Питер)"
Minimaks
 
Сообщения: 234
Зарегистрирован: 28 июн 2010, 14:03

Re: Векторизация изображений

Сообщение Minimaks » 13 окт 2010, 21:52

Diablo писал(а):Выводы: в данном случае большая часть времени расходуется на передачу управления(и кучи переменных) другой функции.


Ну эт еще на лекциях читали, что переключение контекста много жрет CPU)

Если честно, не понимаю смысл это делать в реалтайме да и еще на такой скорости?
ОП ООО "Минимакс (Питер)"
Minimaks
 
Сообщения: 234
Зарегистрирован: 28 июн 2010, 14:03

Re: Векторизация изображений

Сообщение Diablo » 13 окт 2010, 22:55

Minimaks писал(а):Есть же простые быстрые оптимизированные функции, которые занимаются такого рода обработкой изображений - может сорцы гимпа проще покапать чем свой велик изобретать?

Ну кагбэ есть... Но там же идет матричная свертка, 3*3 скажем, т.е. сравнений гораздо больше - у меня по два на точку. Не думаю что можно выжать больше без асма...
Minimaks писал(а):Ну эт еще на лекциях читали, что переключение контекста много жрет CPU)

Дык а с чего контексту переключаться? Там же обычный call идет(внутри одной страницы, по-идее), ну и аргументы в стек кидаются...
Minimaks писал(а):Если честно, не понимаю смысл это делать в реалтайме да и еще на такой скорости?

Смысл - распознавание образов. С камеры. Оперативно. 8)
Причем надо в 3D - вот с этим еще долго буду биться... Функция по переводу 2D+Z в 3D у меня есть самописная, Z можно вычислить по сдвигу м/у двумя картинками/векторами. Но как определить что конкретная точка на двух картинках это одна и та же точка - хз. Бум думать)
ЗЫ USSR RoboTicks :D Магнитогорские шайтан-гуру такие суровые, что Челябинск отдыхает :twisted:
ЗЗЫ У нас в городе есть компания, разрабатывающая роботов, но я к ней никакого отношения не имею...
ЗЗЗЫ Вот куплю я себе ПлэйСтэйшн... :-) Третью, ессно) О желаемом количестве пока лучше промолчу, дабы народ не смущать)
Изображение
Аватара пользователя
Diablo
Флудер
 
Сообщения: 997
Зарегистрирован: 25 сен 2007, 12:42

Re: Векторизация изображений

Сообщение Diablo » 13 окт 2010, 23:09

после трассировки с помощью http://potrace.sourceforge.net/ (сама трассировка занимает ~250ms - явно придется переводить на асм)
http://diablo.pp.ru/RedEye.svg - аффтар при плохом освещении
http://diablo.pp.ru/RedEye0.svg - тут шума поменьше
Камера за 283р даёт отвратительное качество, похоже придется добавлять какие-то фильтры - сглаживание, цветокоррекцию...
Ну и освещение у меня далеко от идеала, автоэкспозиция и баланс белого сильно тупят...
Изображение
Аватара пользователя
Diablo
Флудер
 
Сообщения: 997
Зарегистрирован: 25 сен 2007, 12:42

Re: Векторизация изображений

Сообщение Minimaks » 13 окт 2010, 23:17

Diablo писал(а):Смысл - распознавание образов. С камеры. Оперативно. 8)


Понятие оперативно очень растяжимо - для некоторых и 1 ФПС - очень даже оперативно. Это что распознавание препятствий, или именно увидить объект в 3Д => смоделировать его?
В первом случае используются несколько другие методы, во втором (раз уж намекнул про роботов) смысла моделировать объект 30 раз в сек не имеет смысла.

И еще, векторы при таком разложении изображения будут иметь погрешность (например, рука на фоне моего шкафа имеет малое падение контраста или изменение освещение, ориентация против освещения, что нарушает баланс белого и как следствие смену контрастности). Получается, что робот будет усекать объект. Не знаю почему, но мне кажеться тогда уж лучще уводить глаза робота в другой спектр, не видимый.
Если это что то типа проекта OASIS, то опять скорость здесь не важна

А вообще, ты сам отвечаешь на свои вопросы - пиши на асме, дальше оптимизировать некуда =)
ОП ООО "Минимакс (Питер)"
Minimaks
 
Сообщения: 234
Зарегистрирован: 28 июн 2010, 14:03

Re: Векторизация изображений

Сообщение Diablo » 13 окт 2010, 23:34

Minimaks писал(а):Понятие оперативно очень растяжимо - для некоторых и 1 ФПС - очень даже оперативно. Это что распознавание препятствий, или именно увидить объект в 3Д => смоделировать его?
В первом случае используются несколько другие методы, во втором (раз уж намекнул про роботов) смысла моделировать объект 30 раз в сек не имеет смысла.

Хочется не только распознать объект но и определить его расположение в пространстве, траекторию движения. Мух в полёте сбивать :twisted:
Minimaks писал(а):И еще, векторы при таком разложении изображения будут иметь погрешность (например, рука на фоне моего шкафа имеет малое падение контраста или изменение освещение, ориентация против освещения, что нарушает баланс белого и как следствие смену контрастности). Получается, что робот будет усекать объект. Не знаю почему, но мне кажеться тогда уж лучще уводить глаза робота в другой спектр, не видимый.

Ну... Может какую подстветку делать? Вспышку там поставить и строб давать периодически в проблемных случаях...
А насчет невидимого спектра за идею спасибо, подумаю) Только вот где такие сенсоры надыбать и сколько они будут стоить...
Minimaks писал(а):Если это что то типа проекта OASIS, то опять скорость здесь не важна

Это что-то типа проекта Terminator :crazy: А скорость всегда важна... :oops:
Minimaks писал(а):А вообще, ты сам отвечаешь на свои вопросы - пиши на асме, дальше оптимизировать некуда =)

На асме сходу непросто писать... Тем-более когда нет чёткого алгоритма... Я и этот код на асм переведу, просто стало интересно почему так медленно...
Изображение
Аватара пользователя
Diablo
Флудер
 
Сообщения: 997
Зарегистрирован: 25 сен 2007, 12:42

Re: Векторизация изображений

Сообщение Seven » 14 окт 2010, 06:34

Diablo писал(а):Выводы: в данном случае большая часть времени расходуется на передачу управления(и кучи переменных) другой функции.

сделай эту функцию inline
Аватара пользователя
Seven
 
Сообщения: 1272
Зарегистрирован: 25 сен 2007, 09:12
Откуда: Магнитогорск

Re: Векторизация изображений

Сообщение Naevus » 14 окт 2010, 07:04

Diablo писал(а):А насчет невидимого спектра за идею спасибо, подумаю) Только вот где такие сенсоры надыбать и сколько они будут стоить...
Любая камера в ИК видит не хуже чем в видимом спектре. На камерах для видеосъемок специально ставят ик фильтр чтобы его отсекать. Посмотри - на любой камере, умеющей снимать в темноте есть рычаг для включения ночного режима - этот рычаг просто отодвигает фильтр от матрицы... Ну это все для камер которые съемкой занимаются, а не веб. но принцип действия то у них одинаковый.

Возьми пульт от любого ДУ и направь в свои камеры - на изображении должен быть очень яркий сигнал от ИК светодиода. Если получил - попробуй поискать ИК подсветку (или сам паяй или спроси у SAB - вроде их профиль)
Личный раздел- Список недругов- pater_leo - Выбрать отмеченных- Отправить- Да
Аватара пользователя
Naevus
Модератор
 
Сообщения: 10700
Зарегистрирован: 24 сен 2007, 21:52
Откуда: Магнитогорск

Re: Векторизация изображений

Сообщение Diablo » 14 окт 2010, 17:22

В-общем, всё оказалось намного банальнее. Я тупо забыл добавить флаги оптимизации GCC :pardon: При -O2 оба варианта дают 10ms - 100fps.
Только вот почему без оптимизации gcc генерит такой тормозной код, для меня до сих пор загадка... :unknown:
Naevus, спасибо, что просветил :) Действительно, камера отлично видит в ИК-диапазоне. Будем думать над подсветкой...
Не знаю, что за SAB. Нашел тут и тут.
Цены кусаются... 448р за двухметровую, и 896р за 14м (DC12V/0,7A). Мощнее в районе 3-4тыс.
Изображение
Аватара пользователя
Diablo
Флудер
 
Сообщения: 997
Зарегистрирован: 25 сен 2007, 12:42

Re: Векторизация изображений

Сообщение Naevus » 14 окт 2010, 18:56

Diablo писал(а):Не знаю, что за SAB.
Сорри. Вот
memberlist.php?mode=viewprofile&u=1059
и вот
http://www.atass.ru/
Личный раздел- Список недругов- pater_leo - Выбрать отмеченных- Отправить- Да
Аватара пользователя
Naevus
Модератор
 
Сообщения: 10700
Зарегистрирован: 24 сен 2007, 21:52
Откуда: Магнитогорск

Re: Векторизация изображений

Сообщение Diablo » 14 окт 2010, 19:11

Naevus писал(а):http://www.atass.ru/

Цены кусаются еще больше...
IR-6/20-880 20 град.; 6 м; 880 нм 12 V; 0,2 A; 0,035 кг; Ø 35х20 мм - 805
IR-6/40-880 40 град.; 4 м; 880 нм 12 V; 0,2 A; 0,035 кг; Ø 35х20 мм - 805
IR-6/120-880 120 град.; 2 м; 880 нм 12 V; 0,2 A; 0,035 кг; Ø 35х20 мм - 805
IR-6/160-880 160 град.; 1,5 м; 880 нм 12 V; 0,2 A; 0,035 кг; Ø 35х20 мм - 805
IR-6/20-940 20 град.; 6 м; 940 нм 12 V; 0,2 A; 0,035 кг; Ø 35х20 мм - 805
IR-6/40-940 40 град.; 4 м; 940 нм 12 V; 0,2 A; 0,035 кг; Ø 35х20 мм - 805
IR-6/120-940 120 град.; 2 м; 940 нм 12 V; 0,2 A; 0,035 кг; Ø 35х20 мм - 805
IR-6/160-940 160 град.; 1,5 м; 940 нм 12 V; 0,2 A; 0,035 кг; Ø 35х20 мм - 805

Уж лучше тогда сразу
ПИК-21 Наружный ИК прожектор.
Инфракрасный прожектор, Россия, дальность до 45 м, угол излучения - 30 град, длина волны - 870 нм, DC12V/0,7A
ЦЕНА: Розница: 3552 руб.

или хотя бы
ПИК-23 Наружный ИК прожектор малогаборитный.
Инфракрасный прожектор, Россия, дальность до 14 м, угол излучения - 80 град, длина волны - 870 нм, DC12V/0,7A. Варианты исполнения: болт,шпилька,пластина.
ЦЕНА: Розница: 896 руб.
Изображение
Аватара пользователя
Diablo
Флудер
 
Сообщения: 997
Зарегистрирован: 25 сен 2007, 12:42

Re: Векторизация изображений

Сообщение Naevus » 14 окт 2010, 20:01

Diablo писал(а):Цены кусаются еще больше...
Ну сорри, мое общение с ик подсветкой ограничивается прожектором БМП2 :oops:
Личный раздел- Список недругов- pater_leo - Выбрать отмеченных- Отправить- Да
Аватара пользователя
Naevus
Модератор
 
Сообщения: 10700
Зарегистрирован: 24 сен 2007, 21:52
Откуда: Магнитогорск

Re: Векторизация изображений

Сообщение Diablo » 14 окт 2010, 20:21

Naevus писал(а):Ну сорри, мое общение с ик подсветкой ограничивается прожектором БМП2 :oops:

Да нет, идея хороша, спору нет :) Прожектор БМП2 достать пожалуй нереал :D Глянул ИК-диоды
Самые мощные в районе 100мВт и 30р. Мне понравились L-53SF6C ИК светодиод d=5мм 860нм 100мВт(~40р) и TSAL5100 ИК светодиод d=5мм 940нм 130мВт(~30р)
Первый, как понял, импульсный. Второй - "поставка по запросу". Вот думаю штук 10 норм будет?
Те, что за 896р и бьют на 14м, какой мощности могут быть? DC12V/0,7A=8.4W чёт слабо верится, имхо, там встроен резистор и непосредственно диод жрёт 1-2Вт.
ЗЫ Друг предлагал мою КГ-5000 поставить - от нее в одном только ИК-спектре киловатт навен идет :D А если еще рефлектор поставить... :crazy:
Изображение
Аватара пользователя
Diablo
Флудер
 
Сообщения: 997
Зарегистрирован: 25 сен 2007, 12:42

Re: Векторизация изображений

Сообщение Naevus » 14 окт 2010, 20:38

Diablo писал(а):ЗЫ Друг предлагал мою КГ-5000 поставить - от нее в одном только ИК-спектре киловатт навен идет :D А если еще рефлектор поставить... :crazy:

Ну друг то прав - на бмп как раз обычная фара-луна, а когда нужен ИК - на нее просто надевают светофильтр. Светит канещ хуже чем без фильтра :) но в ТВН видно не хуже чем на авто с ближним.
Личный раздел- Список недругов- pater_leo - Выбрать отмеченных- Отправить- Да
Аватара пользователя
Naevus
Модератор
 
Сообщения: 10700
Зарегистрирован: 24 сен 2007, 21:52
Откуда: Магнитогорск

След.

Вернуться в Программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1