roboforum.ru

Пусть X - квадрат 4х4 бита, его будем одновременно считать целым числом 0..2^16-1

Пусть Rotate(X,A) - квадрат полученный из исходного вращением на А*90 градусов (пусть А от 0 до 3)

В общем вводим функцию I(X) от квадрата X, независимую от вращения этого квадрата:

I(X) = min(Rotate(X,A), по всем А от 0 до 3)

Очевидно, что упорядоченное по возрастанию множество значений Q этой функции имеет размер не менее 2^16/4. Кроме того Z из области значений I(X) тогда и только тогда, когда I(Z)=Z.

Теперь будем считать, что N(Y) - функция, возвращающая по Y из Q её порядковый номер среди Q.

Если у нас есть квадрат, то N(Y) можно рассчитать просто перебрав все квадраты меньше Y, проверяя на их принадлежность Q.

Если же у нас известны N(Y) с некоторым шагом (скажем с шагом 64), тогда мы сможем существенно быстрее выяснять номер своего квадрата, просто опускаясь не до нулевого элемента Q, а до ближайшего известного.

Вы ввели инвариант по углу.
Теперь можно вместо 6 бит использовать всего 2 для определения поворота/отражения.

А вот дальше с оптимизацией декодирования чтото жесткое написано.

zubr писал(а):Вы ввели инвариант по углу.
Теперь можно вместо 6 бит использовать всего 2 для определения поворота/отражения.

2 бита принципиально не могут отвечат за повороты и отражения, потому как поворотов 4 штуки + отражение

По поводу жесткой оптимизации - задавайте вопросы

как же не могут?
вы берете минимум от всех поворотов - выходит вы повороты учли.
С отражениями я поспешил. Но можно ведь и их под минимум засунуть? Тогда и их учтем.
Правда выйдет (2^16)/8 - тоесть 3 бита.

чтобы не думать много - проверил ваш вариант.
матлаб сказал что в минимуме от всех поворотов в вашем варианте остается 16455 уникальных чисел.
Видно отсеялись поворото-нечувствительные варианты. Не думал что их много будет.

не жесткая оптимизация - а жесткое описание.
заявлены дествия без коментариев и объяснений.

zubr писал(а):не жесткая оптимизация - а жесткое описание.
заявлены дествия без коментариев и объяснений.

Затрудняюсь понять, что именно нужно комментить...

Есть функция N(Y) извлечения порядкового номера квадрата X, по его образу Y=I(X).

Тупой способ реализации функции - перебираем Z от Y вниз до 0 квадраты и считаем сколько там Z, удовлетворяющих Z=I(Z).

Оптимизированный - можем перебирать вниз не до 0, а до некоторого Z0=I(Z0), для которого знаем N(Z0).

=DeaD= писал(а):Есть функция N(Y) извлечения порядкового номера квадрата X, по его образу Y=I(X).

Выходит N - обратная функция от I ?

=DeaD= писал(а):Тупой способ реализации функции - перебираем Z от Y вниз до 0 квадраты и считаем сколько там Z, удовлетворяющих Z=I(Z).

Вот тут туго входт. На основании чего?

Добавлено спустя 1 час 53 минуты 35 секунд:
Но не суть важно.
Я исходную идею оценил
Но дальше IMHO муть.
Исходя из того что мы на метке рисуем минимальные квадраты (тоесть из множества Q).
Не проще ли получив квадрат Y неизвестной ориентации из картинки, просто взять минимальный поворот от него?
Тоесть X=I(X) и X=I(Y). Быстро и никаких переборов.
Заодно побочно узнаем насколько повернут квадрат, если функция минимума даст нам индекс минимального поворота A.

Еще можно как вариант сделать метки более контрастными для цветной камеры.
Либо брать основные цвета RBG или CMY.
Либо неестественные/редкие: оранжевый квадрат, внутри: фиолетовый =1, желтый =0.
Последний вариант и на нецветной камере сработает.

zubr писал(а):

=DeaD= писал(а):Есть функция N(Y) извлечения порядкового номера квадрата X, по его образу Y=I(X).

Выходит N - обратная функция от I ?

Совсем нет, N - фукнция извлечения порядкового номера образа I(x) по самому образу (т.е. тупо находим положение образа в списке образов отсортированных по порядку).

zubr писал(а):

=DeaD= писал(а):Тупой способ реализации функции - перебираем Z от Y вниз до 0 квадраты и считаем сколько там Z, удовлетворяющих Z=I(Z).

Вот тут туго входт. На основании чего?

Видимо вы не так поняли что такое N(Y) поэтому тут проблемы. Сейчас стало яснее?

zubr писал(а):Исходя из того что мы на метке рисуем минимальные квадраты (тоесть из множества Q).

На метке можно рисовать любые квадраты X, только смысл у них будет один - I(X).

zubr писал(а):Не проще ли получив квадрат Y неизвестной ориентации из картинки, просто взять минимальный поворот от него? Тоесть X=I(X) и X=I(Y). Быстро и никаких переборов.

Можно взять. проблема в том, что мы не сможем тогда в маяк заносить любую информацию, а это ерунда какая-то, зачем вам телефон по которому нельзя говорить 3/4 слов?

zubr писал(а):Заодно побочно узнаем насколько повернут квадрат, если функция минимума даст нам индекс минимального поворота A.

Ну информация об ориентации может быть извлечена только если все Rotate(X,A) разные при А=0..3

ок. ключевое слово 'отсортированных'

=DeaD= писал(а):Можно взять. проблема в том, что мы не сможем тогда в маяк заносить любую информацию, а это ерунда какая-то, зачем вам телефон по которому нельзя говорить 3/4 слов?

Можем. Но не любую Для любой - нужен бесконечный квадрат.
У нас будет в данном случае 16455 уникальных квадратов - этого достаточно для кодирования номера метки.
Если вас смущает что они не подряд - отсортируйте.
Мне странно внести инвариант по углу и не использовать его..

Все познается в сравнении - 3/4 отличный результат! Оставшимися словами вполне можно передавать информацию.
В исходном алгоритме при квадрате 4x4 необходимо 6 служебных бит - то есть по этому телефону нельзя говорить 63/64 слов

Мы можем выбрать такие квадраты чтобы был только один минимум.

zubr писал(а):ок. ключевое слово 'отсортированных'

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

Но вообще надо еще контроль целостности обязательно, можно его делать какими-нибудь БЧХ-кодами, тогда надёжней и можно даже сколько-то ошибок допускать, но сложнее, а можно как я - контрольной суммой.

Так, теоретические результаты - есть!

Теперь спустимся на грешную землю.
Ограничим скорость нашего маленького робота 10см/с
размер нашей метки 1см
Итого, на анализ каждой метки у нас <100mS
Памяти у нас не более 4КБайт (Mega8)
Меток должно быть не менее 16384
то есть наше итоговое поле 128x128

2mandigit: А какие гарантии по расположению метки в кадре? Какие размеры кадра в пикселях? Оперативки вроде на 8-й меге всего 1кб.

=DeaD= писал(а):2mandigit: А какие гарантии по расположению метки в кадре? Какие размеры кадра в пикселях? Оперативки вроде на 8-й меге всего 1кб.

Размер кадра 16x16, каждый пиксель6 бит
Следовательно, кадр в памяти займет 256 байт

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

Собственно, с моей точки зрения, обработчик выстраивается в некий стек:

анализ корректности
анализ блока метки
формирование блока метки
идентификация метки
получение изображения

в том случае, если новое измерение прошло через весь стек - образуется результат.

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

2mandigit: Чего-то какая-то неберучка получается, 16х16пикселей, если есть гарантия, что метка всегда есть в кадре, значит она имеет размеры не более 8х8пикселей, иначе можем долго видеть часть двух меток и всё.

При этом 8х8 пикселей будут размыты, значит реально до 4х4пикселя можно увидеть, а нам еще надо отличать эту метку от шума, а значит мы 100% не пролезаем в 16 бит нужной информации

Хуже того - я не представляю как без существенных потерь полезных пикселей детектировать метку на кадре...

смотрите кака прелесть http://www.youtube.com/watch?v=5M-oAmBDcZk
этим сделано http://en.wikipedia.org/wiki/ARToolKit

=DeaD= писал(а):2mandigit: Чего-то какая-то неберучка получается, 16х16пикселей, если есть гарантия, что метка всегда есть в кадре, значит она имеет размеры не более 8х8пикселей, иначе можем долго видеть часть двух меток и всё.

При этом 8х8 пикселей будут размыты, значит реально до 4х4пикселя можно увидеть, а нам еще надо отличать эту метку от шума, а значит мы 100% не пролезаем в 16 бит нужной информации

Хуже того - я не представляю как без существенных потерь полезных пикселей детектировать метку на кадре...

Размер метки 4x4 + сетка (на картинке выше пример виден хорошо)

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

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