roboforum.ru

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

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

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

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

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

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

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

Добавлено спустя 1 минуту 13 секунд:

Виталий писал(а):

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

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

Согласен, вот пример: http://www.thg.ru/mobile/20051223/print.html

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

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

=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 писал(а):По-моим предварительным оценкам достаточно 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 писал(а):Идея - есть. Принцип может быть таким-же, как в автосигнализации.

?

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

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

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

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

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

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

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

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

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

Но у нас получается разбивать сложные задачи (нерешаемые) на более простые (решаемые). И думать можно не о нерешаемости проблем, а как их можно порешать
Конечно, нужны фундаментальные основы, но у меня есть впечатление, что мы многое уже придумали. Собственно, если решимся двигаться дальше - следующий шаг - формализация и разбиение на независимые подзадачи. Возможно, придется упрощать саму задачу, что-бы суметь уложиться в имеющиеся ресурсы.

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

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

Итого в картинку размером 5.67х5.67 пикселя надо поместить 16 бит информации и еще какой-то контроль, что это не битая информация

Ладно, нужно все подетальней продумать!
Наверное, пока все обсудили!?

А зачем именно 16 бит, а не 15 например?

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

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

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

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

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

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

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

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

Сегодня напечатал тестовую поверхность. Наверное, первым этапом в алгоритме должно быть определение ориентации поверхности. Возможно для этого стоит использовать структуру, наподобие такой:

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

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

С кучей градаций не покатит, а вот с некучей - вполне себе.