Не уверен, что это тут было, и не уверен, что это именно для программистов.
Но задам.

Представим себе, что мы разрабатываем свой стандарт QR-кода.

Наш QR-код размера NxN -- это квадратик из N x N пикселей. каждый пиксель чёрный или белый.
Трудность состоит в том, что когда мы сканируем код, мы не знаем, какой стороной повёрнут квадрат. Возможны все 4 варианта (0, 90, 180 и 270 градусов)
Вопрос: сколько разных уникальных чисел можно закодировать таким кодом, так, что бы считываемое число не зависело от ориентации квадрата.

Здравствуйте, Erop, Вы писали:

E>Вопрос? Сколько разных уникальных чисел можно закодировать таким кодом, так, что бы считываемое число не зависело от ориентации квадрата.

Чтобы не зависело, или чтобы можно было распознать ориентацию и восстановить закодированное?

Здравствуйте, Erop, Вы писали:

E>Не уверен, что это тут было, и не уверен, что это именно для программистов.
E>Но задам.

E>Мы разрабатываем свой стандарт QR-кода.

E>Наш QR-код размера NxN -- это квадратик из N x N пикселей. каждый пиксель чёрный или белый.
E>Трудность состоит в том, что когда мы сканируем код, мы не знаем, какой стороной повёрнут квадрат. Возможны все 4 варианта (0, 90, 180 и 270 градусов)
E>Вопрос? Сколько разных уникальных чисел можно закодировать таким кодом, так, что бы считываемое число не зависело от ориентации квадрата.

Не зависить будет, если квадрат будет состоять из одинаковых четвертинок, тогда как не поверни — будет одинаково выглядеть.

Здравствуйте, Erop, Вы писали:

E>Не уверен, что это тут было, и не уверен, что это именно для программистов.
E>Но задам.

E>Мы разрабатываем свой стандарт QR-кода.

E>Наш QR-код размера NxN -- это квадратик из N x N пикселей. каждый пиксель чёрный или белый.
E>Трудность состоит в том, что когда мы сканируем код, мы не знаем, какой стороной повёрнут квадрат. Возможны все 4 варианта (0, 90, 180 и 270 градусов)
E>Вопрос? Сколько разных уникальных чисел можно закодировать таким кодом, так, что бы считываемое число не зависело от ориентации квадрата.

Другими словами, все ваши изображения должны обладать осью симметрии 4-го порядка? В таком случае число вариантов для четных N: — 2^(N^2/4), для нечетных: 2^((N-1)^2/4 + (N-1)/2 + 1).

Здравствуйте, Erop, Вы писали:

E>Наш QR-код размера NxN -- это квадратик из N x N пикселей. каждый пиксель чёрный или белый.
E>Трудность состоит в том, что когда мы сканируем код, мы не знаем, какой стороной повёрнут квадрат. Возможны все 4 варианта (0, 90, 180 и 270 градусов)
E>Вопрос? Сколько разных уникальных чисел можно закодировать таким кодом, так, что бы считываемое число не зависело от ориентации квадрата.

Красим, к примеру, два верхних угла в черный цвет, нижний левый — в белый. Этого хватит для определения ориентации.
Остается 2^(N^2-3) вариантов.

Здравствуйте, Brice Tribbiani, Вы писали:

BT>Красим, к примеру, два верхних угла в черный цвет, нижний левый — в белый. Этого хватит для определения ориентации.
BT>Остается 2^(N^2-3) вариантов.

Для N = 2 явно субоптимально (два варианта против реально возможных шести), для N = 1 вообще фигня получается

Здравствуйте, Brice Tribbiani, Вы писали:

E>>Вопрос? Сколько разных уникальных чисел можно закодировать таким кодом, так, что бы считываемое число не зависело от ориентации квадрата.

BT>Красим, к примеру, два верхних угла в черный цвет, нижний левый — в белый. Этого хватит для определения ориентации.
BT>Остается 2^(N^2-3) вариантов.

Как я понял, задача распознавания ориентации даже не ставится. "Не зависело от ориентации квадрата" означает, что изображение не должно меняться от поворота картинки на 90 градусов. Нет разве?

Здравствуйте, Pzz, Вы писали:

Pzz>Чтобы не зависело, или чтобы можно было распознать ориентацию и восстановить закодированное?

Нужно уметь отличать одно число от другого, восстанавливать ориентацию не нужно

Здравствуйте, Qulac, Вы писали:

Q>Не зависить будет, если квадрат будет состоять из одинаковых четвертинок, тогда как не поверни — будет одинаково выглядеть.
Ну, очевидно, что можно больше чисел закодировать...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Qulac, Вы писали:

Q>>Не зависить будет, если квадрат будет состоять из одинаковых четвертинок, тогда как не поверни — будет одинаково выглядеть.
E>Ну, очевидно, что можно больше чисел закодировать...

Как?

Здравствуйте, rg45, Вы писали:

R>Другими словами, все ваши изображения должны обладать осью симметрии 4-го порядка? В таком случае число вариантов для четных N: — 2^(N^2/4), для нечетных: 2^((N-1)^2/4 + (N-1)/2 + 1).

1) Вовсе нет. Можно более хитрые кодировки же использовать.
Ну, скажем, можно три угловые точки всегда красить в белый, а одну в чёрный, и квадрат поворачивать так, что бы чёрный угол справа-вверху. Остальные пиксели перенумеровать и получим 2^(N*N-4) чисел, что для N = 10 сильно больше твоей оценки...

2) Почему на "Вы"? Тут же на "ты" принято?

p.s.
Можно, например, попробовать придумать кодировку для N == 2. Сколько устойчивых к повороту разных кодов можно предложить?

Скажем твоя формула для N == 2 даёт 2 разных числа.
Очевидно, что кодировка "число чёрных пикселей" даёт 5 разных чисел, а ещё больше можно?

Здравствуйте, Brice Tribbiani, Вы писали:

BT>Красим, к примеру, два верхних угла в черный цвет, нижний левый — в белый. Этого хватит для определения ориентации.
BT>Остается 2^(N^2-3) вариантов.

Например для N=2 это 2 числа.
кодировка "число чёрных пикселей" даёт 5 чисел...

А ещё больше можно?

Здравствуйте, Qulac, Вы писали:

Q>Как?

Ну в этом вопрос и состоит


Вернее нужно
1) Указать способ достичь максимум
2) Показать, что больше быть не может

Здравствуйте, Erop, Вы писали:

E>Мы разрабатываем свой стандарт QR-кода.

R>>Другими словами, все ваши изображения должны обладать осью симметрии 4-го порядка? В таком случае число вариантов для четных N: — 2^(N^2/4), для нечетных: 2^((N-1)^2/4 + (N-1)/2 + 1).

E>2) Почему на "Вы"? Тут же на "ты" принято?

А я разве "ваши" с большой буквы написал? Вы же разрабатываете свой стандарт кода, поэтому и картинки тоже ваши

Здравствуйте, rg45, Вы писали:

R>Как я понял, задача распознавания ориентации даже не ставится. "Не зависело от ориентации квадрата" означает, что изображение не должно меняться от поворота картинки на 90 градусов. Нет разве?

Нет, грубо говоря, надо написать программу, которой даёшь числа m > 0 и N > 0 и она печатает квадрат NxN или говорит, что m слишком велико
И вторую, которой даёшь квадрат NxN повёрнутый на неизвестный угол (из 0, 90, 180, 270), а она печатает m

при этом нужно, что бы программа отвергала как можно большие m.

Ну и спрашивают не программу, а зависимость максимального возможного m от N

Здравствуйте, Erop, Вы писали:

R>>Другими словами, все ваши изображения должны обладать осью симметрии 4-го порядка?

E>1) Вовсе нет. Можно более хитрые кодировки же использовать.
E>Ну, скажем, можно три угловые точки всегда красить в белый, а одну в чёрный, и квадрат поворачивать так, что бы чёрный угол справа-вверху. Остальные пиксели перенумеровать и получим 2^(N*N-4) чисел, что для N = 10 сильно больше твоей оценки...

Значит, я просто не верно трактовал выражение "не зависело от ориентации квадрата". Я бы вопрос переформулировал в таком случае: "как обеспечить распознавание ориентации с минимальными накладными расходами и какова при этом будет полезная емкость?". Правильно?

Здравствуйте, Erop, Вы писали:

R>>для нечетных: 2^((N-1)^2/4 + (N-1)/2 + 1).

Кстати, а почему такая хитрая формула? Казалось бы, число "уникальных" пикселей в "четвертушке" (N*N-1) / 4 ну и один центральный не забываем. И получаем 2^((N*N-1)/4 + 1)

Если ввести делений нацело (например как //), то можно и так: 2^( N*N//4 + 1 ) или 2^((N*N+3)//4), которая верна для любых N

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, rg45, Вы писали:

R>>Как я понял, задача распознавания ориентации даже не ставится. "Не зависело от ориентации квадрата" означает, что изображение не должно меняться от поворота картинки на 90 градусов. Нет разве?

E>Нет, грубо говоря, надо написать программу, которой даёшь числа m > 0 и N > 0 и она печатает квадрат NxN или говорит, что m слишком велико
E>И вторую, которой даёшь квадрат NxN повёрнутый на неизвестный угол (из 0, 90, 180, 270), а она печатает m

E>при этом нужно, что бы программа отвергала как можно большие m.

E>Ну и спрашивают не программу, а зависимость максимального возможного m от N

У квадрата нет какой-то выделенной ориентации, т.к он симметричен. Значит нужен не квадрат. Например: один пиксель в левом верхнем углу делаем черным, пиксели вокруг него всегда белые и не используются для записи, аналогично по остальным углам белые не используемые поля 2 на пикселея. Из-за черного пикселя симметрии нет и можно распознать ориентацию.

P.S. Наиболее оптимально это использовать не квадрат, а например прямоугольный треугольник. Вообще, нужно заметить, проблема поиска qr-кода не куда не девается. Вдруг почти все пиксели будут белыми, как тогда распознать границы qr-кода? Без особых меток тут ни как, а если есть метки, то можно узнать и ориентацию.

Здравствуйте, Erop, Вы писали:

E>Например для N=2 это 2 числа.
E>кодировка "число чёрных пикселей" даёт 4 числа...

5

Здравствуйте, rg45, Вы писали:

R>Значит, я просто не верно трактовал выражение "не зависело от ориентации квадрата". Я бы вопрос переформулировал в таком случае: "как обеспечить распознавание ориентации с минимальными накладными расходами и какова при этом будет полезная емкость?". Правильно?

Да, только определять ориентацию не надо