roboforum.ru

У меня есть идея как поиск повернутого смещенного и отмасштабированного в разумных пределах изображения на другом изображении сделать за O(W*H*360*log(W*H)) в случае картинок не являющихся шумом. А если очень-очень хорошо подумать и ограничить масштабы (типа считать что искомый объект имеет линейные размеры не менее 10% от линейных размеров изображения, то еще можно сильно улучшить. При этом алгоритм естественно замечательно параллелится и может быть доработан до поиска объектов произвольной формы, лишь бы они не были значительно "разрежены".

Было бы интересно послушать людей профессионально занимающихся темой технического зрения и распознавания образов, какие сейчас есть алгоритмы решающие эту же задачу и какой объем операций они требуют.

_________________
Проект [[Open Robotics]] - Универсальные модули для построения роботов

По твоему описанию могу сказать: ну круто, фигле. Нет конкретики для размышления.

Раскажи в общих чертах свою идею. Если есть код - лучше так.

Размышлений на тему работоспособности предлагаемого мной алгоритма пока не стоит, минусы его вообще я и так отчетливо представляю, мне интересно с другими сравнить Какие методы есть общеизвестные с которыми можно померяться свойствами (скорость/качество)?

PS: Идею рассказать - пока жаба давит

_________________
Проект [[Open Robotics]] - Универсальные модули для построения роботов

Оценка времени действительно крутая (!!!), а постоянный множитель перед этой оценкой есть, можт он то все и испортит?
Если распознавание зиждится на выделении признаков и их сопоставлении (?), тогда первое что приходит на ум: рыть в сторону методов поиска инвариантных к масштабированию/вращению [или афинным искажениям] дескрипторов. Таких сейчас не мало [для расмышлений], и из области физиологии глаза все это пришло.

Постоянный множитель не сильно большой, но надо пробовать на практике.


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

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

А где можно почитать про эти дескрипторы?

PS: Еще боязно, что линейные искажения при взглядах "чуть под углом" значительно попортят практическую применяемость метода. Всё-таки ведь объекты не всегда под 1 углом видятся перпендикулярно камере

PPS: Таки скажет ктонибудь про какие-то общеизвестные способы распознавания образов и их временную сложность?

_________________
Проект [[Open Robotics]] - Универсальные модули для построения роботов

Про дескрипторы:
http://en.wikipedia.org/wiki/Special:Search?search=Computer+vision+descriptor
Ссылок в этих introduction'ах хватит надолго
[Лучше сначала про Scale-Space]

Про sift-дескрипторы (презентация 10Мб)
http://www.cse.huji.ac.il/course/2006/compvis/lectures/SIFT.ppt

Огромное спасибо за ссылки! Будем изучать, может быть даже найду велосипед, который я изобрел

_________________
Проект [[Open Robotics]] - Универсальные модули для построения роботов

Весь вопрос в том, откуда взялся логарифм. =)
Ну и все же я думаю так O(W*H*360*log(W*H)) = O(n*log(n));

_________________
Все новости о моих проектах http://savethebest.ru

Умничаем значит? И я так же думаю, просто я дал более подробную информацию. Если для ваших супер-ЭВМ множитель 360 это тьфу, то я преклоняюсь

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

_________________
Проект [[Open Robotics]] - Универсальные модули для построения роботов

У меня есть алгоритм распознавания за O(n). Правда не очень сложного объекта - пикселя. =)
Ну и в связ со всеми этими делами интересно мне было бы узнать, а какая же оценка для нейронных сетей?
(они кстати неплохо превращаются в параллельный алгоритм). Для сетей типа победитель получает все сложность составляет O(n);

Так что пока нет конкретики сложно что-то обсуждать.
Давай алгоритм, всеравно ты его не продашь.

_________________
Все новости о моих проектах http://savethebest.ru

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

_________________
Проект [[Open Robotics]] - Универсальные модули для построения роботов

Блин, ну конечно интересно.
Ну, а то, что не продашь - гарантия. =)

_________________
Все новости о моих проектах http://savethebest.ru

Ну вот ты за 10 рублей бы наверное уже купил так что это лишь вопрос согласования цены )))

_________________
Проект [[Open Robotics]] - Универсальные модули для построения роботов

Давай те выкладывайте все свои мысли, если будет понятно как оно все работает, значит идея уже кем-то придумана и давно! Да и от теории до практики путь долгий. Будет шанс родить что-то поновее, если много разных мнений соединить, мозговой штурм т.c.

PS: Все спецы на инглише только говорят, так что тут их точно не бывает!

Ладно, не буду жмотиться расскажу несколько основных ходов:

Постановка задачи - будем искать одну картинку прямоугольной формы на другой (пока без поворотов), неизвестными будем полагать расположение и масштаб (здесь надо сделать оговорку - будем полагать, что искомая картинка видна целиком и не сильно уменьшена);

Часто используемая субзадача - поиск в требуемом диапазоне координат и масштабов уменьшенного до нужной степени искомого образца.

Основные 3 метода, комбинация которых должна дать требуемую оценку по времени:

1. Быстрая оценка среднего значения цвета в прямоугольном регионе - подготовка кэша промежуточных данных занимает O(W*H) и памяти пропорционально W*H*log2(W*H), потом за константу можно мгновенно извлечь средний цвет в любом регионе.

2. Быстрое сравнение образца с проверяемой областью - сначала сравниваем средний цвет, если сильно отклоняемся, то вылетаем, иначе то же самое сверяем в каждой из его подчастей (например, тупо делим на 4 части перекрест, если размеры близки к квадрату или по одному измерению, если размеры близки к полоске), если сумма отклонений всё еще мала - идем дальше и т.п.;

3. Верхний перебор по отрезкам проверяемых масштабов и соответствующее масштабирование шага - если мы ищем образец 100х100 в картинке 300х300 и считаем что масштаб будет из диапазона 0.5-1.5, то можно искать сначала с шагом 5 пикселей и уже если прошли несколько уровней отсечки методом 2, тогда только начинать точный перебор пикселей.

Добавлено спустя 8 часов 8 минут 37 секунд:
Куда все пропали? В патентное бюро убежали?

_________________
Проект [[Open Robotics]] - Универсальные модули для построения роботов