Скремблирование изображений с помощью матриц судоку

Головоломка судоку не только позволяет скоротать время в электричке, но и представляет собой интересную математическую задачу, для которой можно найти полезное применение.

Как известно, игровое поле судоку представляет собой квадрат размером 9×9, разделённый на меньшие квадраты со стороной в три клетки. В клетках расставлены числа таким образом, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась только один раз.

 

Судоку

 

Игровое поле судоку можно рассматривать как обыкновенную матрицу, каждая ячейка в которой имеет свои координаты, в соответствии с номером столбца и номера строки. Например, на матрице вверху элемент в пятом блоке с цифрой 9 описывается стандартной записью как (4,5), элемент в третьем столбце с цифрой 7 — как (8,3), элемент в шестой строчке с цифрой 2 — как (6,9).

Уникальность игрового поля судоку состоит в том, что ячейки в нём можно записывать не только по номеру строки/столбца, но и другими способами, поскольку существует чёткая взаимозависимость между элементами, а также дополнительная привязка к квадратам 3×3.

Группа учёных под руководством Ву (Yue Wu) из университета Тафтса в Массачусетсе описала шесть различных способов идентификации каждого элемента в матрице судоку, а также привела формулы, с помощью которых осуществляется преобразование из одного метода кодирования матрицы в другой. Казалось бы, зачем они это делали? Оказывается, такие свойства матриц делают их идеальным инструментом для скремблирования изображений.

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

Матрицы судоку отлично подходят для скремблирования. В научной работе Sudoku Associated Two Dimensional Bijections for Image Scrambling авторы сравнивают свой метод и программу Sudoku Associated Image Scrambler на его основе с существующими методами скремблирования — и приходят к выводу, что он не уступает ни одному из них, а во многих случаях превосходит аналоги.

 

Пример изображений

На иллюстрации: (a) оригинальное изображение; (b) один раунд скремблирования; (c) двенадцать раундов скремблирования; (d) двенадцать раундов скремблирования со сдвигом; (e) двенадцать раундов скремблирования в программе Sudoku Associated Image Scrambler.

Для изображения 256 x 256 пикселов существует как минимум 256!=2^1684 матриц судоку, так что изображение после скремблирования невозможно расшифровать случайно или даже методом брутфорса.

 

Напомним, недавно были созданы наручные часы для любителей судоку

 

Источник: http://www.xakep.ru/post/59079/

комментарии (0)

Добавить комментарий