Распечатать запись Распечатать запись

Математики кодируют изображения с помощью судоку

Вот уж воистину никогда не догадаться, что может найти применение в жизни. Казалось бы, судоку — просто забавная головоломка. А вот ведь и ее использовали для алгоритма кодирования изображений!

Ультрасовременный алгоритм кодирования изображений использует новый тип матрицы, созданный на основе головоломки судоку.

Числовая головоломка судоку состоит из таблички 9 \times 9 клеток, которые должны быть заполнены цифрами от 1 до 9.

Имеется ряд дополнительных ограничений. Каждая цифра может появиться только один раз в каждом столбце, один раз в каждой строке и один раз в каждом из девяти блоков 3\times3, входящих в состав таблицы. Решение головоломки приведено ниже. В начале игры игрокам известно расположение некоторого количества цифр из этого решения.

Благодаря судоку возник целый ряд интересных для математиков задач. Ранее в этом году, например, была решена задача о минимальном количестве ключей для судоку, которое дает к единственное решение (таких ключей 17).

Теперь Ю Ву из Университета Тафтса в Медфорде и его коллеги использовали судоку для решения другой задачи — проблемы кодирования изображений перед их отправкой.

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

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

Но Ву и его коллеги говорят, что можно определить элементы массива по-другому, если подумать о нем, как о таблице судоку. В этом случае каждый элемент содержит цифру от 1 до 9, которая удовлетворяет правилам судоку. Другими словами, в дополнение к номерам строки и столбца, каждому элементу соответствует цифра.

Таким образом, в приведенной выше таблице элементу в первой строке и первом столбце (1,1) также соответствует цифра 8, элемент (1,2) связан с цифрой 7, элемент (1,3) — с цифрой 4 и т.д.

К тому же каждый элемент связан также с блоком 3\times3, а сами блоки пронумерованы так, как показано на рисунке. Таким образом, элемент (1,1) связан с блоком 1, элемент (2,8) — с блоком 7, элемент (8,5) с блоком 6, и так далее.

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

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

Эти функции преобразования являются ключом к кодированию изображений. Начнем с изображения 9\times9 пикселей. Наложить решение судоку на него так, что каждый пиксель может теперь быть представлен координатами в новой системе координат.

Теперь, применяя одну из функций преобразования, меняем позиции пикселей, смешивая изображение.

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

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

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

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

Удивительно, сколько судоку может сделать для человечества!

Источник: http://www.technologyreview.com/view/428639/mathematicians-encrypt-images-using-mathematics/

Оставьте свой отзыв

Добавить изображение