roboforum.ru

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

 

Код в квадрате?

Автомат, адаптивный автомат ... разум

Re: Код в квадрате?

Сообщение Виталий » 29 янв 2009, 09:15

Простое сравнение с шаблоном скорее всего ничего не даст.

Мне кажется, что эта задача, решенная от начала и до конца может в будущем иметь и большое практическое применение. Возможно, даже тянет на патент.

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

Re: Код в квадрате?

Сообщение =DeaD= » 29 янв 2009, 09:44

mandigit писал(а):PS В отличие от твоей задачи нам хорошо известны размеры метки.

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

Тупо с шаблонами сравнивать? координаты перебирать и хотя-бы 48 углов поворота - это уже 8*8*48 операций сравнения матриц размером 8*8, уже имеем 200'000 составных операций - и это только на 1 метку проверять, а если их куча? Мне кажется не проходим.

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

Добавлено спустя 1 минуту 13 секунд:
Виталий писал(а):
Мне кажется, что эта задача, решенная от начала и до конца может в будущем иметь и большое практическое применение. Возможно, даже тянет на патент.

Не тянет. Такая задача решена уже много раз.

Согласен, вот пример: http://www.thg.ru/mobile/20051223/print.html
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24053
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: Pascal / C++ / PHP / 1C
ФИО: Антон Ботов

Re: Код в квадрате?

Сообщение mandigit » 29 янв 2009, 11:50

Виталий писал(а):Простое сравнение с шаблоном скорее всего ничего не даст.

Аргументы есть?

=DeaD= писал(а):Тупо с шаблонами сравнивать? координаты перебирать и хотя-бы 48 углов поворота - это уже 8*8*48 операций сравнения матриц размером 8*8, уже имеем 200'000 составных операций - и это только на 1 метку проверять, а если их куча? Мне кажется не проходим.

По-моим предварительным оценкам достаточно 8 углов поворота. Если матрица шаблона 8x8=64, то 512 операций. Весь экран 16x16, следовательно матрицу шаблона можно перемещать по i=0..8, j=0..8 - то-же 512. 512*512 = 262000 операций. Предположим на каждую операцию 10 тактов - получится 2,5*10^6 тактов. Что позволяет на 15МГц проводить идентификацию 6 раз/сек. Пока алгоритм не реализован точнее сказать сложно.

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

Идея - есть. Принцип может быть таким-же, как в автосигнализации.
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: Код в квадрате?

Сообщение =DeaD= » 29 янв 2009, 12:35

mandigit писал(а):По-моим предварительным оценкам достаточно 8 углов поворота. Если матрица шаблона 8x8=64, то 512 операций. Весь экран 16x16, следовательно матрицу шаблона можно перемещать по i=0..8, j=0..8 - то-же 512. 512*512 = 262000 операций. Предположим на каждую операцию 10 тактов - получится 2,5*10^6 тактов. Что позволяет на 15МГц проводить идентификацию 6 раз/сек. Пока алгоритм не реализован точнее сказать сложно.

Это чтобы 1 метку распознавать, а 2 метки проверять - уже 3 раза/секунду будет?

mandigit писал(а):Идея - есть. Принцип может быть таким-же, как в автосигнализации.

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

Re: Код в квадрате?

Сообщение mandigit » 29 янв 2009, 12:58

=DeaD= писал(а):Это чтобы 1 метку распознавать, а 2 метки проверять - уже 3 раза/секунду будет?


Распознавать не метку, как содержимое, а метку как окружение.
То есть надо найти белый квадрат, окаймляющий метку! Только один!
А что там за метка - этому программному уровню не интересно.

В автосигналках есть такой код ReeLoq. Там есть принцип, согласно которому последовательность кодов может быть нарушена, но есть механизм синхронизации.
Поскольку мы знаем, какие коды расположены рядом - можно ожидать, что найденный код будет расположен с предыдущим. Если это не так - в следующем цикле найденный код сверяется с текущим и если они близкорасположенные - принимается решение о ресинхронизации.
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: Код в квадрате?

Сообщение =DeaD= » 29 янв 2009, 13:03

mandigit писал(а):Распознавать не метку, как содержимое, а метку как окружение.
То есть надо найти белый квадрат, окаймляющий метку! Только один!
А что там за метка - этому программному уровню не интересно.

Вопрос в том, что в 16х16 пикселей очень мало чего помещается.

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

Re: Код в квадрате?

Сообщение mandigit » 29 янв 2009, 14:29

=DeaD= писал(а):Вопрос в том, что в 16х16 пикселей очень мало чего помещается.

Белый квадрат окаймляющий метку какой шириной в пикселях гарантируем? Даже если 2 пикселя (а потом начинается другая метка), тогда уже надо не 16х16 пикселей, а 24х24 пикселя. Да и внутри 4х4 пикселя если могут быть любыми, это значит, что там может например не быть пикселей вообще и в координатах ячеек близких к (0,0) эти белые квадраты не ясно будет как искать, там будет чистый лист с одиноко стоящими пикселями.


Проблем - много. Нет 24x24 кадра, и памяти столько нет и вычислительного ресурса столько нет :crazy:

Но у нас получается разбивать сложные задачи (нерешаемые) на более простые (решаемые). И думать можно не о нерешаемости проблем, а как их можно порешать :beer:
Конечно, нужны фундаментальные основы, но у меня есть впечатление, что мы многое уже придумали. Собственно, если решимся двигаться дальше - следующий шаг - формализация и разбиение на независимые подзадачи. Возможно, придется упрощать саму задачу, что-бы суметь уложиться в имеющиеся ресурсы.
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: Код в квадрате?

Сообщение =DeaD= » 29 янв 2009, 16:04

Главная гипотеза, которую надо опровергнуть - нельзя на плоскости расположить маркеры так, чтобы в кадре 16х16 пикселей влезал целиком хотя-бы 1 маркер и содержал не менее 16 бит информации.

Кстати, это мы еще его прямым считали, что должен вмещаться в 8х8 пикселей, а по хорошему под углом 45 градусов он ведь тоже должен вмещаться, значит реально на маяк есть 5.67 пикселей :)

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

Re: Код в квадрате?

Сообщение mandigit » 29 янв 2009, 20:36

Ладно, нужно все подетальней продумать!
Наверное, пока все обсудили!? :beer:
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: Код в квадрате?

Сообщение Виталий » 29 янв 2009, 20:57

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

Re: Код в квадрате?

Сообщение =DeaD= » 29 янв 2009, 21:03

2mandigit: Ну еще не всё, есть еще мысль - может быть не выкладывать всю инфу в 1 маркер, а только частичную? Типа 4-6 бит и всё? И располагать их в некой регулярной структуре, тогда мы конечно имеем шанс проморгать маркеры и потерять координаты, но это надо подряд типа 3-4 маркера проморгать по 1 координате...

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

Re: Код в квадрате?

Сообщение Виталий » 29 янв 2009, 22:12

Я предлагаю другой подход, который позволит хранить даже больше чем 16 бит.
Предположим задачу пометки маркера и его нахождения мы решили.

В области данных у маркера могут присутствовать не только черно-белые изображения, но и в оттенках серого. Каждому градиенту серости сопоставим свое число. Всего градиентов следует выбрать 3 или 4. Т.е. Мы будем работать в троичной или четверичной системе, что позволит повысить емкость маяка.

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

Re: Код в квадрате?

Сообщение mandigit » 29 янв 2009, 22:44

=DeaD= писал(а):2mandigit: Ну еще не всё, есть еще мысль - может быть не выкладывать всю инфу в 1 маркер, а только частичную? Типа 4-6 бит и всё? И располагать их в некой регулярной структуре, тогда мы конечно имеем шанс проморгать маркеры и потерять координаты, но это надо подряд типа 3-4 маркера проморгать по 1 координате...

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


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

Сегодня напечатал тестовую поверхность. Наверное, первым этапом в алгоритме должно быть определение ориентации поверхности. Возможно для этого стоит использовать структуру, наподобие такой:
Вложения
sh.pdf
(1.8 КиБ) Скачиваний: 12
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

Re: Код в квадрате?

Сообщение =DeaD= » 29 янв 2009, 23:10

Виталий писал(а):Я предлагаю другой подход, который позволит хранить даже больше чем 16 бит.

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

Re: Код в квадрате?

Сообщение Виталий » 30 янв 2009, 09:06

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

Пред.

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

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

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

Mail.ru counter