roboforum.ru

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

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

Николай_Алексеевич писал(а):По твоему описанию могу сказать: ну круто, фигле. Нет конкретики для размышления.
Раскажи в общих чертах свою идею. Если есть код - лучше так.

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

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

GraphD писал(а):Оценка времени действительно крутая (!!!), а постоянный множитель перед этой оценкой есть, можт он то все и испортит?

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

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

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

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

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

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

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

GraphD писал(а):Про дескрипторы:
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

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

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

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

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

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

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

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

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

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

GraphD писал(а):

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

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

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

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

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

Основные 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 секунд:
Куда все пропали? В патентное бюро убежали?