Прямой матричный метод

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

Под матрицей перестановок понимается квадратная матрица, у которой в каждой строке и каждом столбце отличен от нуля только один элемент, равный единице [5].

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

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

Если рассматривать цифровое изображение как квадратную матрицу размерности , элементы которой находятся в пределах от 0 до 255, задающую полутоновое отображение пикселов растра, то при умножении такой матрицы на матрицу перестановок и транспонированную к ней происходит перемешивание пикселов изображения

(7)

Известно [5] следующее свойство матрицы перестановок :

(8)

где ‑ единичная матрица.

Согласно (8) для обратного преобразования матрицы достаточно умножить её на справа и на слева

(9)

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

Итоговая сложность матричного перемножения (9) будет равна: , что может занять достаточно большой промежуток времени при обработке больших изображений, поэтому необходимо сократить количество операций.

Метод перестановок

В силу специального вида матрицы перестановок P алгоритм умножения матриц может быть заменён на перестановки, а сама P представлена в виде кортежа перестановок, где i- й позиции кортежа ставится в соответствие позиция перестановки. При этом пропадает необходимость в матричном умножении. Оно заменяется на перестановку строк и столбцов матрицы цифрового изображения. Различия в реализации этих методов приведены в таблице 1.

Таблица 1 - Различия в реализации методов

Прямой матричный метод	Метод перестановок
1 for p:=0 to length (Матрица) -1 do 2 for i:=0 to length (Матрица) -1 do 3 for j:=0 to length (Матрица) -1 do 4 for k:=0 to length (Матрица) -1 do 5 Temp [ i,p ] :=Temp [ i,p ] + (МатрПерест[ i,k ] * Матрица[ k,j ] * МатрПерест[ p,j ])	1 for i:=0 to length (Матрица)- 1 do 2 for j:=0 to length (Матрица)- 1 do 3 Temp [ i,j ] := Матрица[Перест[ i ], j ]; 4 for j:=0 to length (Матрица)- 1 do 5 for i:=0 to length (Матрица)- 1 do 6 Матрица[ i, Перест[ j ]] := Temp [ i,j ];
Количество операций сложения, умножения и присвоения:		Количество операций присвоения:

где

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

Date: 2016-07-22; view: 353; Нарушение авторских прав