roboforum.ru

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

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

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

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

Сообщение mandigit » 27 янв 2009, 18:24

Есть квадрат 4x4, каждая клетка может принять значение 0/1.
Положение квадрата в пространстве неопределено, например
0100
0010
1111
0000

кодирует то-же число, что и (повернуто на 90 град)
0100
0101
0110
0100

можно предположить, что таким образом можно закодировать более 2^14 чисел
(исходя из того, что каждое закодированное число приводит к не более, чем 4 запрещенным числам)

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

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

Сообщение Digit » 27 янв 2009, 18:30

Посмотри в сторону QCode - Dead с его помощью маяки маркировал.
Или я не о том? :oops:
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

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

Сообщение mandigit » 27 янв 2009, 18:39

Digit писал(а):Посмотри в сторону QCode - Dead с его помощью маяки маркировал.
Или я не о том? :oops:


Оно самое, только хочется эффективнее использовать имеющуюся информацию!
QCod'ом в квадрате 4x4 не закодируешь 2^14 чисел.
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

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

Сообщение =DeaD= » 27 янв 2009, 19:08

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

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

Сообщение mandigit » 27 янв 2009, 19:22

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

Ну, пока стоимость этого отжима видится очень дорогой :cry:
Но, вдруг, кто-то хорошо знакомый с арифметикой полиномов найдет простое решение.
Суть-то вот в чем:
матрица датчика 16x16, что-бы определить такую метку нужно разрешение в два раза больше, чем единичный элемент метки, а с учетом случайного положения метки нужно площадь охватывать, как два размера метки.
Получается, что информацию надо упаковать в квадрат 4x4, что составляет 16 бит
Если убрать 2 бита, получится что можно в таком коде зашифровать положение x=0..127, y=0..127
А если убрать 4 бита то только 0..63

В первом случае площадка при размере метки 1.28x1.28м
во втором 0.64x0.64
Аватара пользователя
mandigit
 
Сообщения: 583
Зарегистрирован: 28 ноя 2005, 12:05
Откуда: Москва

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

Сообщение zubr » 27 янв 2009, 19:43

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

За либу респект :)

А если у вас во внешнем черном квадрате одну точку белой сделать? Например ближайшую к угловой.
Будет метка после этого корректно определяться?
Код: Выделить всёРазвернуть
            int isGood=0;

            //Проверим на то, что по периметру центрального квадрата маяка размером 7х7 идут черные клетки, иначе ошибка
            for(int i=0; i<K; i++){
              if( res[0][i]==0 )  { isGood++; }; // считаем белые точки в черном контуре
              if( res[K-1][i]==0 ){ isGood++; };
              if( res[i][0]==0 )  { isGood++; };
              if( res[i][K-1]==0 ){ isGood++; };
            };
            isGood = (isGood > 1) ? 0 : 1; // разрешим одну белую точку

Если это работает и CV находит черный контур, то этой точки достаточно чтобы определить поворот или отражение.
За здравый смысл у нас принимается мнение большинства.
zubr
 
Сообщения: 431
Зарегистрирован: 20 ноя 2008, 19:31
Откуда: Чернобыль
прог. языки: асмемблер
ФИО: Валентин Семенович

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

Сообщение =DeaD= » 27 янв 2009, 20:32

mandigit писал(а):Если убрать 2 бита, получится что можно в таком коде зашифровать положение x=0..127, y=0..127
А если убрать 4 бита то только 0..63

Есть тупой метод, но он достаточно слабый по производительности, хотя смотря сколько у нас флэша под это дело отвести, если даём 2N байт флэша под служебные таблицы, тогда скорость распознавания маяка будет порядка 2^16/(2*N), то есть если 1Кбайт под служебные таблицы отдадим, тогда скорость будет порядка 64 операций достаточно сложных. В принципе терпимо на 8МГц-ах то... Надо такой метод?

Добавлено спустя 1 минуту 18 секунд:
zubr писал(а):А если у вас во внешнем черном квадрате одну точку белой сделать? Например ближайшую к угловой.
Будет метка после этого корректно определяться?

Если это работает и CV находит черный контур, то этой точки достаточно чтобы определить поворот или отражение.

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

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

Сообщение nest » 27 янв 2009, 20:43

может, прошвырнуться по известным типам штрих кодов ?
Аватара пользователя
nest
 
Сообщения: 977
Зарегистрирован: 21 янв 2005, 12:16
Откуда: Germany
Предупреждения: -4
прог. языки: asm

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

Сообщение =DeaD= » 27 янв 2009, 20:49

nest писал(а):может, прошвырнуться по известным типам штрих кодов ?

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

Больше всего похожи на то что нужно QR-коды - их сотиком можно распознавать, но надо сотик наводить для этого: http://ru.wikipedia.org/wiki/QR_%D0%BA%D0%BE%D0%B4
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

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

Сообщение zubr » 27 янв 2009, 20:50

Так нет же никаких противоречий с вашим методом.
Разница в одной белой точке. Не хотите ее использовать для оценки - не используйте.
А хотите - то +6 бит получите. Соответственно на мелких маяках интереснее становится.

Почему производительность может упасть? Можете потестить с белой точкой?

Я еще не собрал ваш код. Былдером лет 10 не пользовался.
Вот было бы здорово если бы был консольный тестик типа даешь картинку - получаешь картинку.
Тогда и оптимизировать будет на чем. И тестовые картинки страшные придумывать.
За здравый смысл у нас принимается мнение большинства.
zubr
 
Сообщения: 431
Зарегистрирован: 20 ноя 2008, 19:31
Откуда: Чернобыль
прог. языки: асмемблер
ФИО: Валентин Семенович

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

Сообщение =DeaD= » 27 янв 2009, 20:52

2zubr: в смысле в одной белой точке? Если из внешнего черного квадрата изъять 1 квадратик и сделать его белым - не будет распознаваться квадратный контур - верхний фильтр в поиске маяков, что сильно уронит производительность.

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

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

Сообщение zubr » 27 янв 2009, 21:02

у известных еще проблема с патентами..
но для понятия решаемых задач очень даже интересно http://www.id-russia.ru/Faq/Aztec/abtaztec.html

я имел в виду так (вариант 5x5):

11111
1xxx1
1xxx1
1xxx1
10111
За здравый смысл у нас принимается мнение большинства.
zubr
 
Сообщения: 431
Зарегистрирован: 20 ноя 2008, 19:31
Откуда: Чернобыль
прог. языки: асмемблер
ФИО: Валентин Семенович

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

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

zubr писал(а):я имел в виду так (вариант 5x5):

11111
1xxx1
1xxx1
1xxx1
10111

Так не пойдёт, как я и говорил, не сработает детектор квадрата на верхнем уровне алгоритма.

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

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

Сообщение nest » 27 янв 2009, 21:49

mandigit
мало одного квадрата - делаем 3х3 квадратов размерами 16х16.
наружние - для центрации/позиционирования. внутренний - данные.
ну или наоборот.

для мышного сенсора они всё равно мелкие нужны. ну и пусть будет мелкие хоть 3х3 сантиметра.
Аватара пользователя
nest
 
Сообщения: 977
Зарегистрирован: 21 янв 2005, 12:16
Откуда: Germany
Предупреждения: -4
прог. языки: asm

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

Сообщение mandigit » 27 янв 2009, 22:32

=DeaD= писал(а):... Надо такой метод?


Давай!

nest писал(а):мало одного квадрата - делаем 3х3 квадратов размерами 16х16.
наружние - для центрации/позиционирования. внутренний - данные.
ну или наоборот.
для мышного сенсора они всё равно мелкие нужны. ну и пусть будет мелкие хоть 3х3 сантиметра.


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

След.

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

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

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