roboforum.ru

Технический форум по робототехнике.

Тупое распознавание образа

Тупое распознавание образа

Сообщение =DeaD= » 28 ноя 2007, 22:41

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

Было бы интересно послушать людей профессионально занимающихся темой технического зрения и распознавания образов, какие сейчас есть алгоритмы решающие эту же задачу и какой объем операций они требуют.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Тупое распознавание образа

Сообщение Николай_Алексеевич » 29 ноя 2007, 12:46

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

Раскажи в общих чертах свою идею. Если есть код - лучше так.
Николай_Алексеевич
 
Сообщения: 44
Зарегистрирован: 11 дек 2006, 17:18
Откуда: Тольятти

Re: Тупое распознавание образа

Сообщение =DeaD= » 29 ноя 2007, 13:37

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

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

PS: Идею рассказать - пока жаба давит :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Тупое распознавание образа

Сообщение GraphD » 29 ноя 2007, 17:24

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

Re: Тупое распознавание образа

Сообщение =DeaD= » 29 ноя 2007, 17:41

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

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

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

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

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

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

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

PPS: Таки скажет ктонибудь про какие-то общеизвестные способы распознавания образов и их временную сложность? :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Тупое распознавание образа

Сообщение GraphD » 30 ноя 2007, 01:32

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

Про sift-дескрипторы (презентация 10Мб)
http://www.cse.huji.ac.il/course/2006/compvis/lectures/SIFT.ppt
GraphD
 
Сообщения: 157
Зарегистрирован: 01 окт 2005, 00:56
Откуда: С.-Петербург

Re: Тупое распознавание образа

Сообщение =DeaD= » 30 ноя 2007, 10:32

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

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

Огромное спасибо за ссылки! Будем изучать, может быть даже найду велосипед, который я изобрел :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Тупое распознавание образа

Сообщение Виталий » 30 ноя 2007, 13:12

Весь вопрос в том, откуда взялся логарифм. =)
Ну и все же я думаю так O(W*H*360*log(W*H)) = O(n*log(n));
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: Тупое распознавание образа

Сообщение =DeaD= » 30 ноя 2007, 13:26

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

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

Логарифм взялся от моих прикидочных оценок, как будут мои отсчения по вероятностям работать.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Тупое распознавание образа

Сообщение Виталий » 30 ноя 2007, 14:30

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

Так что пока нет конкретики сложно что-то обсуждать.
Давай алгоритм, всеравно ты его не продашь. :D
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: Тупое распознавание образа

Сообщение =DeaD= » 30 ноя 2007, 14:42

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

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

Интересно, да? :) а может и продам? :))) в общем сначала попробую сам всё собрать и посмотреть насколько эффективно на реальных изображениях ищется всё. А там и посмотрим.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Тупое распознавание образа

Сообщение Виталий » 30 ноя 2007, 14:52

Блин, ну конечно интересно.
Ну, а то, что не продашь - гарантия. =)
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: Тупое распознавание образа

Сообщение =DeaD= » 30 ноя 2007, 15:36

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

Ну вот ты за 10 рублей бы наверное уже купил :) так что это лишь вопрос согласования цены :))))
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Тупое распознавание образа

Сообщение GraphD » 30 ноя 2007, 21:43

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

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

PS: Все спецы на инглише только говорят, так что тут их точно не бывает! :D
GraphD
 
Сообщения: 157
Зарегистрирован: 01 окт 2005, 00:56
Откуда: С.-Петербург

Re: Тупое распознавание образа

Сообщение =DeaD= » 01 дек 2007, 18:09

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

Давай те выкладывайте все свои мысли, если будет понятно как оно все работает, значит идея уже кем-то придумана и давно! :pardon: Да и от теории до практики путь долгий. Будет шанс родить что-то поновее, если много разных мнений соединить, мозговой штурм т.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 секунд:
Куда все пропали? В патентное бюро убежали? :lol:
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

След.

Вернуться в Алгоритмы

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

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