1. 概述
利用Arnold變換（又稱貓臉變換）可以對(duì)圖像進(jìn)行置亂劫映，使得原本有意義的圖像變成一張無(wú)意義的圖像诡必。該變換可以在其它圖像處理前對(duì)圖像做預(yù)處理吭产，例如在數(shù)字盲水印嵌入前對(duì)水印進(jìn)行置亂格二。也可以用于普通的圖像加密。
通常一次Arnold變換達(dá)不到理想效果齿诉，需要對(duì)圖像進(jìn)行連續(xù)多次的變換筝野。Arnold變換具有周期性，即對(duì)圖像連續(xù)進(jìn)行Arnold變換粤剧，最終又能得到原圖像歇竟。變換的周期和圖像的尺寸有關(guān)。
當(dāng)圖像是一張方形的圖像時(shí)抵恋，Arnold變換存在逆變換焕议。經(jīng)過(guò)N次Arnold變換后的數(shù)據(jù)可以通過(guò)N次逆變換恢復(fù)數(shù)據(jù)。
Arnold變換不僅可以用于圖像置亂弧关，也可以用于其它數(shù)據(jù)的置亂和加密盅安。
2. 狹義的貓臉變換
2.1 公式
狹義的貓臉變換即最簡(jiǎn)單的一種變換。網(wǎng)絡(luò)上絕大部分關(guān)于Arnold變換的博客都是狹義Arnold變換世囊。
其矩陣運(yùn)算公式為：
轉(zhuǎn)化為多項(xiàng)式為：
其中mod()是取模運(yùn)算别瞭，N是正方形圖像的邊長(zhǎng)，(x', y')是像素點(diǎn)(x, y)變換后的坐標(biāo)茸习。
注意求模運(yùn)算(mod) ≠ 求余運(yùn)算(%) 畜隶。在被除數(shù)是負(fù)數(shù)時(shí)兩者存在差別，例如： -5 mod(6) = 1, 但 -5 % 6 = -5号胚。
/**
* 求模運(yùn)算
*/
private int mod(int number, int mod) {
return (number % mod + mod) % mod;
}
2.2 物理意義和示意圖
置亂的實(shí)質(zhì)是新位置與舊位置的映射籽慢，且該映射是一一對(duì)應(yīng)的。下圖是一次貓臉變換的示意圖：
- (a)是原圖
- (b)是先做水平方向的錯(cuò)切
- (c)是在(b)的基礎(chǔ)上再做一次豎直方向的錯(cuò)切
- (d)是對(duì)圖像求模猫胁，即切割回填操作箱亿，得到變換后的圖像。
如果你想知道為什么要這樣變換弃秆，為什么是水平錯(cuò)切一個(gè)單位届惋，豎直錯(cuò)切兩個(gè)單位：
實(shí)際上這里水平錯(cuò)切的長(zhǎng)度是一倍圖像的高度，豎直錯(cuò)切的長(zhǎng)度是一倍圖像的高度加一倍圖像的寬度菠赚。由于圖像的寬高相等脑豹，所以這里看起來(lái)是水平錯(cuò)切一個(gè)單位，豎直兩個(gè)單位衡查。
為什么這樣子錯(cuò)切瘩欺，是因?yàn)?strong>置亂的實(shí)質(zhì)是新位置與舊位置的映射，且該映射是一一對(duì)應(yīng)的。
也就是說(shuō)俱饿，其它錯(cuò)切形式可能造成多個(gè)點(diǎn)移動(dòng)到同一個(gè)位置歌粥，導(dǎo)致圖像信息的丟失。例如下面兩種錯(cuò)切方式：
其他錯(cuò)切情形
第一種是水平和豎直方向都錯(cuò)切一個(gè)單位拍埠，第二種是水平一個(gè)單位失驶，豎直三個(gè)單位≡婀海可以看出嬉探，取模后兩種錯(cuò)切方式都有部分區(qū)域重疊了。因此錯(cuò)切的單位是有一定要求的坷虑，詳見(jiàn)后文廣義的Arnold變換甲馋。
2.3 代碼實(shí)現(xiàn)
2.3.1 Java泛型的實(shí)現(xiàn)
此處寬高需要相等是方便后續(xù)的逆變換。
public class Arnold<T> {
/**
* 貓臉變換
* @param origin 原始圖像
* @param dest 用于保存變換后的圖像
* @param count 變換的次數(shù)
*/
public void arnold(T[][] origin, T[][] dest, int count) {
int newY, newX;
while (count > 0) {
for (int row = 0; row < origin.length; row++) {
for (int col = 0; col < origin[0].length; col++) {
newX = (col + row) % origin.length;
newY = (col + 2 * row) % origin.length;
dest[newY][newX] = origin[row][col];
}
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
}
2.3.2 適用于Android的一維數(shù)組形式
/**
* 貓臉變換
* @param origin 原始圖像迄损，寬高必須一致
* @param dest 用于保存輸出
* @param SIZE 寬和高
* @param count 變換的次數(shù)
*/
public void arnold(int[] origin, int[] dest, int SIZE, int count) {
int oldY, oldX, newY, newX;
while (count > 0) {
for (int index = 0; index < origin.length; index++) {
oldX = index % SIZE;
oldY = index / SIZE;
newX = (oldX + oldY) % SIZE;
newY = (oldX + 2 * oldY) % SIZE;
dest[newY * SIZE + newX] = origin[index];
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
2.3.3 實(shí)際運(yùn)行結(jié)果
如圖所示，一次變換后账磺，原圖得到了一定程度的置亂芹敌，但還能分辨出原始圖像的信息，6次變換后圖像已看不出原始圖像的信息垮抗。
3. 狹義貓臉變換的逆變換
當(dāng)一張圖片的寬度和高度相同時(shí)氏捞，Arnold變換具有逆變換。雖然Arnold變換具有周期性冒版，可以通過(guò)一直變換下去得到原圖液茎，但是周期越長(zhǎng)，恢復(fù)原圖也越長(zhǎng)辞嗡。通過(guò)逆變換可以較為方便地把變換后的圖像恢復(fù)捆等。
3.1 逆變換公式
轉(zhuǎn)換為多項(xiàng)式為：
3.2 代碼實(shí)現(xiàn)
3.2.1 泛型形式的實(shí)現(xiàn)
/**
* 貓臉逆變換
* @param origin 原始圖像
* @param dest 用于保存變換后的圖像
* @param count 變換的次數(shù)
*/
public void inverseArnold(T[][] origin, T[][] dest, int count) {
int newY, newX;
while (count > 0) {
for (int row = 0; row < origin.length; row++) {
for (int col = 0; col < origin[0].length; col++) {
newX = (col + row) % origin.length;
newY = (col + 2 * row) % origin.length;
dest[newY][newX] = origin[row][col];
}
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
3.2.2 適用于Android的一維數(shù)組形式
/**
* 貓臉逆變換
* @param origin 原圖
* @param dest 保存變換后的圖像
* @param SIZE 寬高
* @param count 變換次數(shù)
*/
public void inverseArnold(int[] origin, int[] dest, int SIZE, int count) {
int oldY, oldX, newY, newX;
while (count > 0) {
for (int index = 0; index < origin.length; index++) {
oldX = index % SIZE;
oldY = index / SIZE;
newY = mod((oldY - oldX), SIZE);
newX = mod((2 * oldX - oldY), SIZE);
dest[newY * SIZE + newX] = origin[index];
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
逆變換的效果當(dāng)然就是把圖像復(fù)原了。此處就不在貼效果圖了续室。
4. 廣義的貓臉變換
4.1 公式
如前文所述栋烤，只要錯(cuò)切的單位滿足取模回填后挺狰，原圖與變換后的圖能夠一一對(duì)應(yīng)明郭，那么該變換就是有效的。滿足這個(gè)條件的公式是：
其逆變換公式為：
4.2 代碼實(shí)現(xiàn)
這里只列出了用于Android的一維數(shù)組形式：
4.2.1 廣義正變換
/**
* 廣義貓臉變換
* @param origin 原圖
* @param dest 變換后的圖
* @param SIZE 圖像寬度和高度
* @param count 變換次數(shù)
*/
public void arnold(int[] origin, int[] dest, int SIZE, int count, int a, int b) {
final int ab_plus_1 = a * b + 1;
int oldY, oldX, newY, newX;
while (count > 0) {
for (int index = 0; index < origin.length; index++) {
oldX = index % SIZE;
oldY = index / SIZE;
newX = (oldX + a * oldY) % SIZE;
newY = (b * oldX + ab_plus_1 *oldY) % SIZE;
dest[newY * SIZE + newX] = origin[index];
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
4.2.2 廣義逆變換
/**
* 廣義貓臉逆變換
* @param origin 原圖
* @param dest 變換后的圖
* @param SIZE 圖像寬度和高度
* @param count 變換次數(shù)
*/
public void inverseArnold(int[] origin, int[] dest, int SIZE, int count, int a, int b) {
final int ab_plus_1 = a * b + 1;
int oldY, oldX, newY, newX;
while (count > 0) {
for (int index = 0; index < origin.length; index++) {
oldX = index % SIZE;
oldY = index / SIZE;
newX = mod(ab_plus_1 * oldX - a * oldY, SIZE);
newY = mod(oldY - b * oldX, SIZE);
dest[newY * SIZE + newX] = origin[index];
}
count--;
origin = Arrays.copyOf(dest, dest.length);
}
}
5. 利用Arnold變換進(jìn)行加密
對(duì)于廣義Arnold變換丰泊，當(dāng)a薯定、b、count任何一個(gè)值不同時(shí)瞳购，變換后圖像也是不相同的话侄。因此，可以把（a苛败、b满葛、count）作為加密參數(shù)對(duì)圖像進(jìn)行加密径簿。此外，還可以對(duì)圖像的不同部分進(jìn)行不同的加密嘀韧，使得更難破解篇亭。例如，可以把圖像分為四份（甚至可以有交集）锄贷，分別對(duì)每一份子圖進(jìn)行加密译蒂，這樣又增大了破解的難度。
Arnold加密后谊却，如果圖像被破壞了柔昼，例如壓縮、涂改等炎辨。解密后的圖像依然能恢復(fù)一部分?jǐn)?shù)據(jù)捕透。
下圖是以參數(shù)（7，11碴萧，4）加密的圖像乙嘀，以及對(duì)加密后的圖像進(jìn)行涂抹后再解密的結(jié)果。
- (a) 原圖
- (b) 加密后的圖像
- (c) 涂抹
- (d) 解謎后的圖像
可以看出Arnold變換有較高的魯棒性破喻，即使添加了多個(gè)較大的圓也能恢復(fù)出原圖的大致信息虎谢。
根據(jù)Arnold變換的原理，我們還可以用來(lái)加密其它數(shù)據(jù)曹质，而不僅僅是圖像婴噩。
轉(zhuǎn)載須注明出處：http://www.reibang.com/p/39727dbaffd9
