Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > поиск "объектов" в двумерном массиве

Автор: relok 22.5.2011, 22:49

здравствуйте) идеи по этому поводу есть, но хочется спросить, мб имеются решения побыстрее и попроще (или есть ссылки на уже готовые алгоритмы, не знаю как это назвать): есть массив, к примеру  y    ^       6|  0 0 0 0 0 0 0 0 0 0 5|  0 0 0 0 0 0 0 0 0 0 4|  0 0 1 1 1 1 0 0 0 0 3|  0 0 1 1 0 1 1 0 0 0 2|  0 0 1 1 1 1 1 0 0 0 1|  0 0 0 1 0 0 0 0 0 0 0|  0 0 0 0 0 0 0 0 0 0    ------------------------> x       0 1 2 3 4 5 6 7 8 9  слева и снизу- индексы) смотрим на это не как на массив, а как будто это картинка. нолики - фон. единички составляют объект. нужно выделить объект рамкой (то есть найти наименьшее значение ИКС, наименьшее значение ИГРИК ,наибольшее значение ИКС, наибольшее значение ИГРИК - для объекта из единичек). Икс и Игрик соответственно не обязательно должны быть от одного пикселя(единички). объект не прерывается, если рядом хоть с одной единичкой есть еще одна (во всех 8- ми направлениях) для данного примера:  minX=2 minY=1 maxX=6 maxY=4 моя идея: делаем обход построчно слева направо снизу вверх.  находим первую единичку: 3,1 заходим в while(какая -то проверка) эту единичку заносим в массив, ищем всех ее друзей(в 8 направлениях) - 2,2  3,2 4,2 далее ищем друзей у 2,2 : 2,3 3,3 3,2(уже был) и 3,1(уже был) далее ищем друзей 3,2 , потом у 4,2  потом ищем друзей друзей , и друзей друзей друзей. пока последний друг  не найдет себе пару закончить думаю можно тогда, когда очередной пиксель (единичка) не найдет себе НОВУЮ (которой раньше не было) пару это мне кажется слишком "в лоб" мб есть попроще?) ps нужно для камеры . к примеру идет в кадре человек  - выделить его контуром.

Автор: borisbn 22.5.2011, 23:49

Цитата(relok @  22.5.2011,  22:49 ) это мне кажется слишком "в лоб"мб есть попроще?) мне кажется ты чего-то перемудрил    http://liveworkspace.org/code/de243fbac01941cbc9f6a2a4c2f77027 только индексы по Y ни "снизу", а "сверху"

Автор: relok 23.5.2011, 00:30

спасибо за внимание) но объектов может быть больше, и для каждого нужно будет рассчитать это дело

Автор: borisbn 23.5.2011, 00:45

Цитата(relok @  23.5.2011,  00:30 ) но объектов может быть больше, и для каждого нужно будет рассчитать это дело и тут вспоминается анекдот/байка: молодому бойцу дали задание: разобрать и почистить генератор. Читает он инструкцию: "Снимите крышку генератора". Ну, сказано - сделано, снимает. А она не поддаётся. Он и пласкогубцами и монтировкой поддеть пытался... Никак. В итоге взял зубило, молоток - сбил нахрен эту крышку. Читает инструкцию дальше: ", открутив предварительно 16 болтов"

Автор: relok 23.5.2011, 08:56

Цитата и тут вспоминается анекдот/байка: молодому бойцу дали задание: разобрать и почистить генератор. Читает он инструкцию: "Снимите крышку генератора". Ну, сказано - сделано, снимает. А она не поддаётся. Он и пласкогубцами и монтировкой поддеть пытался... Никак. В итоге взял зубило, молоток - сбил нахрен эту крышку. Читает инструкцию дальше: ", открутив предварительно 16 болтов" smile

Автор: borisbn 23.5.2011, 10:09

ну... как-то так. http://liveworkspace.org/code/7e75e4fd9bb1a9271248407349bf75db похоже на то, что ты писал в самом начале...

Автор: relok 23.5.2011, 17:13

спасибо) всё работает отлично но не мог бы ты объяснить как?) typedef vector< Rect > Objects; //вот от сюда

Автор: borisbn 23.5.2011, 17:21

relok, т.е. я правильно понял, что ты не знаешь, что такое вектор, но собираешься делать Цитата(relok @  22.5.2011,  22:49 ) нужно для камеры . к примеру идет в кадре человек  - выделить его контуром. IMHO стоит сначала почитать книжки, поднатаскаться с Си++, а затем уже писать распознавание контуров по видеоизображению... Не в обиду... Щаз убегаю. Приду домой - распишу что там да как

Автор: relok 24.5.2011, 09:01

Цитата relok, т.е. я правильно понял, что ты не знаешь, что такое вектор, но собираешься делать Цитата(relok @  22.5.2011,  22:49 Найти цитируемый пост) нужно для камеры . к примеру идет в кадре человек  - выделить его контуром. IMHO стоит сначала почитать книжки, поднатаскаться с Си++, а затем уже писать распознавание контуров по видеоизображению... Не в обиду... я знаю что такое вектор и как раз через него хотел делать) не додумался правда с самого начала сделать вектор структур (хотел вести 4 отдельных вектора) мне не очень понятна чудо рекурсия, которую ты используешь и которая волшебно работает

Автор: borisbn 24.5.2011, 10:50

Код // ф-ция go проверяет, есть ли в точке [y+y_inc][x+x_inc] единичный пиксел, и не был ли он уже учтён. // если оба условия выполняется, то делается то же самое для всех 8-ми соседей этой точки void go( int y, int x, int y_inc, int x_inc, Rect & rect ) {     y = y + y_inc; // сдвигаемся по y в указанную в параметрах сторону     x = x + x_inc; // сдвигаемся по x в указанную в параметрах сторону     //cout << y << " " << x << endl;     // если упёрлись в край картинки (вернее если вышли за край, то ничего проверять не нужно)     if ( y >= 0 && y < ROWS && x >= 0 && x < COLS )      {         // вот условие из описания ф-ции go (см. выше)         if ( array[ y ][ x ] != 0 && watched[ y ][ x ] == false )         {             //cout << "+" << endl;             watched[ y ][ x ] = true; // помечаем точку как просмотренную. больше её проверять не нужно             // увеличиваем границы текущего объекта до текущих координат             rect.left = std::min( rect.left, x );             rect.top = std::min( rect.top, y );             rect.right = std::max( rect.right, x );             rect.bottom = std::max( rect.bottom, y );             // собственно говоря делаем ТО ЖЕ САМОЕ для всех 8-ми соседей точки             go( y, x, -1, -1, rect ); // up left             go( y, x, -1, 0, rect );  // up             go( y, x, -1, 1, rect );  // up right             go( y, x, 0, -1, rect );  // left             go( y, x, 0, 1, rect );   // right             go( y, x, 1, 1, rect );   // down right             go( y, x, 1, 0, rect );   // down             go( y, x, 1, -1, rect );  // down left         }     } } int main() { ... ... // есть ли в ntreotq точке единичный пиксел, и не был ли он уже учтён      if ( array[ y ][ x ] != 0 && watched[ y ][ x ] == false )      {         // начинаем новый объект.                 Rect rect;                 rect.left = x;                 rect.top = y;                 rect.right = x;                 rect.bottom = y;         // после этого вызова все точки, граничащие с этой, а также граничащие с ними и т.д. и т.п.         // будут помечены, как просмотренные, войдут в созданный объект         // а границы этого нового объекта изменятся до min/max этих точек                 go( y, x, 0, 0, rect );         // добавить объект в список объектов                 objects.push_back( rect );      } как-то так

Автор: relok 24.5.2011, 17:18

спасибо тебе) рамкой выделяет движение в кадре но возникает переполнение стека, когда объект примерно равен 40%  кадра к слову: массив обрабатывается размером 128*96

Автор: borisbn 24.5.2011, 17:36

а как ты переводишь изображение (цветные, чёрно-белые или оттенки серого пикселы - без разницы) в массив 0-й и 1-ц ? Цитата(relok @  24.5.2011,  17:18 ) но возникает переполнение стека, когда объект примерно равен 40%  кадра ухудши разрешение в 2 раза по каждой оси. Обработай массив след.образом: Код const int K_ZOOM = 2; int array[ ROWS ][ COLS ] = ... int zoommed[ ROWS / 2 ][ COLS / 2 ]; for ( int y = 0; y < ROWS / K_ZOOM ; y++ ) {     for ( int x = 0; x < COLS / K_ZOOM ; x++ ) {         zoommed[ y ][ x ] = 0;         for ( int yy = 0; yy < K_ZOOM; yy++ ) {             for ( int xx = 0; xx < K_ZOOM; xx++ ) {                 zoommed[ y ][ x ] |= array[ y * K_ZOOM + yy ][ x * K_ZOOM + xx ];             }         }     } } а затем работай с zoommed

Автор: relok 24.5.2011, 17:50

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

Автор: borisbn 24.5.2011, 18:13

Цитата(relok @  24.5.2011,  17:50 ) я подумаю в четверг над этим а что за религия, не позволяющая в среду работать ? Про субботу знаю, про воскресенье - тоже  Цитата(relok @  24.5.2011,  17:50 ) а хотя если развертывание не составит проблем думаю умножение rect.left, rect.top etc на K_ZOOM - это не проблема  как насчёт вопроса Цитата(borisbn @  24.5.2011,  17:36 ) а как ты переводишь изображение (цветные, чёрно-белые или оттенки серого пикселы - без разницы) в массив 0-й и 1-ц ? ?

Автор: relok 24.5.2011, 18:31

Цитата как насчёт вопроса Цитата(borisbn @  24.5.2011,  17:36 Найти цитируемый пост) а как ты переводишь изображение (цветные, чёрно-белые или оттенки серого пикселы - без разницы) в массив 0-й и 1-ц ? ? если в массив нулей и единиц, то : исходное 640*480 есть базовый кадр, по нему строю яркостный массив: обхожу окном 5х5 , высчитываю сумму в окне и делю на 25 (средняя яркость, яркость у меня это Y от YUV) составляю массив из яркостей для базового, размером 128 * 96 потом для каждого приходящего с камеры кадра строю такой же затем заполняю массив - маску (128 на 96) - если в текущем квадрате абсолютная разность между средними яркостями текущего и базового больше какого-то порога, то ставлю 1, если нет, то оставляю 0. +в твоей идее то, что мне не придется сворачивать изображение, а только бинарную маску эту, получать координаты для прямоугольника, разворачивать координаты и по ним строить в кадре прямоугольник Цитата а что за религия, не позволяющая в среду работать ? Про субботу знаю, про воскресенье - тоже smile завтра в универ ехать нужно=) а в четверг можно продолжить мучать камеру

Автор: borisbn 24.5.2011, 19:19

Цитата(relok @  24.5.2011,  18:31 ) есть базовый кадр, по нему строю яркостный массив Цитата(relok @  24.5.2011,  18:31 ) потом для каждого приходящего с камеры кадра строю такой же Цитата(relok @  24.5.2011,  18:31 ) если в текущем квадрате абсолютная разность между средними яркостями текущего и базового больше какого-то порога, то ставлю 1, если нет, то оставляю 0 я думал над этой задачей - у меня получился практически такой же алгоритм, за исключением того, что для базовой картинки берётся не один кадр, а несколько (100...500) и для каждого пиксела считается средняя по времени яркость, при чём делается это не один раз, а всё время (скользящее накопление). Таким образом маленькие объекты (листья, капли дождя etc) не повлияют на базовую картинку. Плюс к тому учитывается то, что днём освещение больше, а вечером меньше... Think about it.

Автор: relok 24.5.2011, 21:40

Цитата я думал над этой задачей - у меня получился практически такой же алгоритм, за исключением того, что для базовой картинки берётся не один кадр, а несколько (100...500) и для каждого пиксела считается средняя по времени яркость, при чём делается это не один раз, а всё время (скользящее накопление). Таким образом маленькие объекты (листья, капли дождя etc) не повлияют на базовую картинку. Плюс к тому учитывается то, что днём освещение больше, а вечером меньше... Think about it.  а можно точнее про "скользящее накопление?" это схоже со скользящим средним?: +я представляю, как это (скользящее среднее или "Взвешенная скользящая средняя придаёт бо́льший вес последним значениям и меньший — ранним значениям") может справиться с медленной сменой освещения но как с листьями и дождем пока не пойму. подумаю над этим в четверг=) а за наводку спасибо)

Автор: borisbn 24.5.2011, 22:13

Цитата(relok @  24.5.2011,  21:40 ) это схоже со скользящим средним? почти. есть несколько вариантов. есть такой Цитата(relok @  24.5.2011,  21:40 ) придаёт бо́льший вес последним значениям и меньший — ранним значениям Код mean_val = mean_val / N + new_val; а есть такой вариант - запоминаются все N значений (в твоём случае - для каждого пиксела), самое ранне значение вычитается из суммы, а самое новое - добавляется в сумму и записывается на место самого раннего. Цитата(relok @  24.5.2011,  21:40 ) но как с листьями и дождем пока не пойму небольшое шевеление листьев, капли дождя, пыль, мухи - при накоплении дадут оч.маленький вклад в формирование базовой картинки. Если же работать по одному кадру, то может появляться много "тревог" на эти, вроде бы незначительные, изменения в картинке

Автор: relok 27.5.2011, 17:35

подумал про масштабирование - работает на больших объектах. единичные пока не тестировал но это я попозже внедрю) сейчас интересен динамический базовый Цитата а есть такой вариант - запоминаются все N значений (в твоём случае - для каждого пиксела), самое ранне значение вычитается из суммы, а самое новое - добавляется в сумму и записывается на место самого раннего. я вот этого не понял. то есть остальные N-1 значение статичны? а меняется только одно? вот как я это вижу: вектор на 300 элементов. каждый раз удаляется нулевой(самый ранний) элемент, а в конец вставляется новый. считается сумма и делится на 300.  в итоге получается: 1 2 3 4 5 +6= 2 3 4 5 6 +7= 3 4 5 6 7 +8= 4 5 6 7 8 +9= 5 6 7 8 9  только немного не понятно. применять это и к областям, в которых есть движение? в принципе, если человек идет по сцене, то это не повлияет никак. также может быть полезным, если машина стояла сначала, а потом уехала - так это место компенсируется со временем. но если человек встал, то через некоторое время он станет фоном и не будет ли лагать сильно, если даже считать вектор не для каждого пикселя, а для областей 5х5. это 128*96 * 300 +) еще и деление. скажи что думаешь по этому поводу=)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)