RGB-куб, сечение куба семейством плоскостей
Каждый однородно окрашенный объект проецируется в RGB-куб как точечный кластер или кластер в форме отрезка кривой с преимущественной ориентацией вдоль оси яркости.
Необходимо находить в цветовом пространстве кластеры типа криволинейных отрезков:
1. разбиение цветового пространства на слои семейством плоскостей, нормальных к главной диагонали цветового пространства;
2. послойная кластеризация с помощью алгоритма поиска водоразделов;
3. сборка кластеров;
4. обратное проецирование на плоскость изображения с целью получения карты сегментации.
Нужно использовать разбиение изображения на небольшие, плотно покрывающие изображение, прямоугольные области, каждая из которых сегментируется независимо. При этом при сегментации текущей области анализируется цветовое распределение, взятое по большей области. При этом объект, далёкий от текущей области, уже не зашумляет её локальное цветовое распределение, а близкие объекты вносят существенный вклад, даже если их вклад по площади в сегментируемую область мал. Для устранения границ между «областями внимания» используется процедура слияния областей с помощью ГСО. Функция для меры несходства определенна.
Всё это используется, чтобы выделить на изображении однородно окрашенные объекты. Для связи точек RGB-куба c реальными координатами пробовал описать следующее (пишу в Delphi 7):
type Pixel=record
x,y: integer;
end;
var KUB: array[0..255,0..255,0..255] of Pixel; - Structure large
Как описать нечто подобное?
"1. разбиение цветового пространства на слои семейством плоскостей, нормальных к главной диагонали цветового пространства;", насколько я понимаю плоскости пересекают оси в точках одинаковой интенсивности. Однако с реализацией этого проблемы. Для визуализации можно использовать OpenGL. По сути это главный вопрос.
2. Непонятно назначение приведенной структуры. Что такое x и y? Если координаты точки на картинке, то что тогда хранит цветовой куб? Координаты нужных точек? Но при этом с одной стороны на картинке может быть более одной точки какого-либо цвета (а в кубе для нее отведена строго одна ячейка), а с другой - бОльшая часть ячеек останется пустыми.
"Непонятно назначение приведенной структуры", это именно коор. точек, но сейчас я понимаю, что это неправильный подход. Все эти манипуляции я делал для того, чтобы как-то связать гистограмму с реальными координатами. Возможно я что-то упустил, но непонятно, как после того, как я нашел кластер в форме отрезка кривой, определить координаты этой области.
Поэтому лучше отмечать вопросы при помощи вопросительных знаков в конце предложения.
И не использовать без надобности местоимения. Я, например, не понял, о какой именно "этой области" идет речь в последнем предложении.
Я имел ввиду координаты однородно окрашенного объекта.
Мне посоветовали использовать oprical flow, сейчас изучаю литературу по этой теме и мне кажется, что оптический поток и вправду более подходит. Сейчас интересует как представить изображение в виде слоев разного разрешения в форме пирамиды Гаусса?
1. Разбиваем изображение на блоки.
2. Находим для каждого блока вектор движения.
3. Обходим блоки и помечаем их, в зависимости от схожести направления векторов и т.п.
Проблема в выборе метода расчета векторов движения. Необходимо использовать метод, который бы не занимал много машинного времени при вычислениях, и при этом количество ложных векторов (не соотв. реальному движению объектов интереса) было как можно меньше (желательно приближалось к количеству, как при полном переборе). Кто что посовеует? Может обработка векторов после их нахождения или предобработка изображения для уменьшения области поиска?
На самом деле меньше, был перерыв, сейчас появилось время и я снова занялся этим проектом.
Вектор движения определяет положение блока пикселей текущего кадра относительно предыдущего или можно сказать, что он представляет собой горизонтальное и вертикальное смещение на координаты x, y текущего блока пикселей. Т.е. движение представляется в виде вектора с координатами x, y, исходя их того, что интенсивность пикселя остается постоянной. При этом вектор находится не для каждого пикселя, а для блока пикселей. Результатом работы алгоритма для текущего блока пикселей является нахождение наиболее похожего на него блока на ссылочном кадре и вычисление вектора движения или смещения текущего блока относительно найденного. В свою очередь оптический поток (optical flow) есть векторное поле, элементы которого определяют движение
конкретных пикселей при переходе от предыдущего изображения к последующему. Не знаю насколько понятно получилось, но как-то так.
Расписать задачу больше, чем на экран и не указать самого главного...
Или за прошедший месяц задача радикально изменилась?
Понял, что совершенно не понимаю поставленной задачи.
Что же требуется?
Разработка специфичного механизма компресии, учитывающего особенности движущегося изображения?
Детектирование движения для охранной системы?
Разработка системы motion capture?
Автоматизированный ввод данных для научного/стстистического анализа?
Задача распознавания образов, использующая характеристики их движения?
Что-то другое?
Да, извините - вина за мной. Собственно задача осталась прежней, но изменился поход к её решению и исходные данные. Полностью задача состоит в следующем:
Есть последовательность кадров с подвижной камеры. Камера установленна в автомобиле (на панели или в районе зеркала), центр области слежения кадра соответствует осевой (оптической) линии камеры. Необходимо выделять на кадрах последовательности объекты и определять дистанцию от камеры до них. Сейчас работаю по выделению объектов. Мне необходимо определять центр каждого нестатичного объекта (преимущественно это автомобили и др. транспортные средства), превышающего по размеру опредленный предел. Сейчас изучаю подход на основе оптического потока. На настоящий момент он мне кажется наиболее перспективным и рациональным для данной задачи. Постараюсь его описать более лаконично, чем в предыдущий раз:
Есть два кадра, первый снят во время t0 (далее предыдущий кадр), а второй во время t (далее текущий кадр). Кадры разбиваются на блоки пикселов и для каждого блока пикселов текущего кадра находится вектор движения (определяет смещение блока пикселов по x и y, относительно предыдущего кадра, основываясь на том, что интенсивность каждого пиксела постоянна). После этого производится обход блоков и сравнение их векторов движения, при этом блоки с похожими (по направлению, длине и т.п.) векторами движения объеденяются. Все эти действия направленны на сегментацию изображений, т.е. на выделение объектов отличных от статичного фона.
Проблема следующая: необходимо подобрать (как вариант усовершенствовать/разработать) быстрый алгоритм нахождения векторов движения (для начала можно предположить, что у нас нет проблем с освещеностью, что текстура объектов хорошо выраженна). Главными требованиями для этого алгоритма будут: небольшая вычислительная сложность (соотв. время вычислений), и минимальное кол-во ложных векторов движения, не соотв. реальному движению нестатичных объектов. В идеале это кол-во должно приближаться к количеству, как при методе полного перебора (где-то ~35% от общего количества). В сущности проблема в выборе алгоритма. Однако можно подумать в направлении предварительной обработки изображений для сужения зоны поиска и/или последующего исключения ложных векторов вижения, чтобы снизить риск рассегментации и потери объекта. В общем проблема такая. Может кто что посоветует?
И еще чуть-чуть по поводу терминологии. Не подумайте, что я придираюсь, но действительно непонятен смысл.
От полного перебора в подавляющем большинстве случаев стремяться уйти, т.к. это очень много. http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%BD%D1%8B%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D0%B1%D0%BE%D1%80 Вы же указываете этот случай в качестве желаемого. Вероятно, Вы имеете в виду не полный перебор, а что-то другое.
Нет, в данном случае блок пикселей получается так: разбиваем весь кадр на квадраты, например 4*4, тогда блок пикселей будет состоять из 16 пикселей.
От полного перебора в подавляющем большинстве случаев стремяться уйти, т.к. это очень много. http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%BD%D1%8B%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D0%B1%D0%BE%D1%80 Вы же указываете этот случай в качестве желаемого. Вероятно, Вы имеете в виду не полный перебор, а что-то другое.
Да действительно, от полного перебора (именно brute force) нужно уйти, так как это не подходит по времени вычислений. Однако в данном случае полный перебор даёт самые лучшие результаты по кол-ву ложных векторов движения. Необходим алгоритм, результаты работы которого были бы близки к результату работы алгоритма полного перебора. Т.е. в данном случае эффективность работы алгоритма оценивается по сравнению алгоритмом полного переборп.
Или под "разбиением на блоки" подразумевается всего лишь снижение разрешения (скажем, вчетверо по каждой оси), чтобы снизить вычислительную нагрузку?
А что пордразумевается под полным перебором? Сравнение среднего цвета каждого из блоков одного кадра с каждым из блоков другого?
Не совсем Вас понял. Пожалуйста, разверните эту мысль по-подробней. То, что я пытаюсь применить - это алгоритм блочного совпадения (Block Matching Algorithm - BMA). Результатом работы алгоритма для блока пикселей является нахождения наиболее похожего на него блока пикселей на ссылочном кадре и вычисление вектора движения или смещения текущего блока относительно найденного. Существуют различные критерии определения совпадения блоков пикселей. Наиболее популярные: суммарная квадратичная ошибка (дает более аккуратное совпадение, однако более вычислительно сложное), суммарная абсолютная разница (в BMA используется чаще, но менее хорош в определении совпадения, требует меньше вычислений), взаимная корреляция, максимальное количество совпадающих пикселей. (см. атач)
Нет. Разбиение на блоки - это именно разбиение на блоки. Но упомянутый Вами вариант, я тоже рассматриваю. Когда изображение предствляется совокупностью слоев с разным разрешением в виде пирамиды Гаусса или Лапласа. В этом случае на изображении с низким разрешением может быть оцененно быстрое движение. Далее оценки полученные на уровне с более низким разрешением уточняются на уровнях с более высоким разрешением.
Да, полный перебор - определение векторов движения для всех блоков кадра. Такое определение является избыточным: если в блоке кадра t нет значимых изменений относительно кадра t-1, то с большой вероятностью вектор движения равен нулю. Искать векторы движения надо только в тех блоках, где произошли какие-либо изменения.
Для примера одномерный случай.
У нас есть 2 кадра, каждый из которых мы разбиваем регулярной сеткой на блоки по 4 пикселя.
Нас интересует, скажем, 6-й блок. Он сместился на 10 пикселей (2.5 блока), после чего на втором кадре половина его попала 8-й блок, а половина - в 9-й.
Ни 8-й, ни 9-й блок втоого кадра не похожи на 6-й блок первого. Что делать?
Похоже, мы так и не пришли к общему знаменателю с тем, что такое полный перебор.
Пусть у нас картинка 320х240. Т.е. 64000 пикселей. Мы бьем ее на блоки 4х4, получаем 80х60 = 4800 блоков.
Полный перебор - это сравнение каждого из 4800 блоков первого кадра с каждым из 4800 блоков второго, т.е. 4800^2 = 23040000 блочных операций. Учитывая, что в блочной (векторной) операции сравнения 16-пиксельных блоков примерно 32 скалярных операции, получаем, что полный перебор у нас займет порядка миллиарда операций.
Действительно ли под термином "полный перебор" мы понимаем одно и то же?