利用电脑玩Android版“天天连萌”刷高分（二）——图像识别

上一篇只是提到了在PC端利用android sdk里面的工具进行截图，接下来这一篇将补充一点关于上一篇的内容，然后介绍一下程序的整个结构，以及如何进行《天天连萌》里面的图像识别和消除的搜索算法。

一、补充上篇的内容
首先补充一下上一篇忘了提及的内容。
在使用chimpchat时，需要添加几个jar包。这方面网上的资料很少，不过功夫不负有心人，嘿嘿。
需要添加的jar包如下：

• chimpchat.jar
• common.jar
• ddmlib.jar
• guava-13.0.1.jar

以上jar包都可以在android sdk里面的tools/lib目录中找到。

二、程序的设计
在这个程序里面我主要写了4个java文件：

• Main.java 只有一个main方法，程序的入口。
• Robot.java，程序的核心部分，进行游戏截图、图像转换为数组，搜索消除等。里面包含一个LianlianKan的内部类，它是用于搜索可以消除的方块的工具类。
• Point.java，表示在数组中的坐标位置的对象。
• ImageHash.java，图像识别的算法类，采用汉明距离算法进行图片相似检测。

三、图像识别及转换。
首先先截一张游戏界面的图。游戏里的方块是分布在中心的一个10*5（方块大小）的区域中的。所以先截下图，通过工具取得它的4个边的边距。以我的手机为例，它是800*480的分辨率的，截的图是竖屏的，左边距为48，右边距为72，上边距及下边距为115。每个游戏方块为57*72。如下图所示：

所以在Robot.java需要定义以上相关常量，代码如下：

/**
 * 主要操作类，进行截图，识别，转换，消除，按键等。
 * 
 * @author Geek_Soledad <a target="_blank" href=
 *         "http://mail.qq.com/cgi-bin/qm_share?t=qm_mailme&email=XTAuOSVzPDM5LzI0OR0sLHM_MjA"
 *         style="text-decoration:none;"><img src=
 *         "http://rescdn.qqmail.com/zh_CN/htmledition/images/function/qm_open/ico_mailme_01.png"
 *         /></a>
 */
public class Robot {
	/**
	 * 屏幕宽，视手机而修改
	 */
	private static final int SCREEN_WIDTH = 480;
	/**
	 * 屏幕高，视手机而修改
	 */
	private static final int SCREEN_HEIGHT = 800;

	/**
	 * 左边距，视手机而修改
	 */
	private static final int PADDING_LEFT = 48;
	/**
	 * 右边距，视手机而修改
	 */
	private static final int PADDING_RIGHT = 72;
	/**
	 * 上边距，视手机而修改
	 */
	private static final int PADDING_TOP = 115;
	/**
	 * 下边距，视手机而修改
	 */
	private static final int PADDING_BOTTOM = 115;
	/**
	 * 游戏方块列数
	 */
	private static final int BOX_COL = 5;
	/**
	 * 游戏方块行数
	 */
	private static final int BOX_ROW = 10;
	/**
	 * 图片宽
	 */
	private static final int IMAGE_WIDTH = (SCREEN_WIDTH - PADDING_LEFT - PADDING_RIGHT) / BOX_COL;
	/**
	 * 图片高
	 */
	private static final int IMAGE_HEIGHT = (SCREEN_HEIGHT - PADDING_TOP - PADDING_BOTTOM)
			/ BOX_ROW;
	/**
	 * 截除的边角宽，视手机而修改
	 */
	private static final int CORNER_WIDTH = 24;
	/**
	 * 截除的边角高，视手机而修改
	 */
	private static final int CORNER_HEIGHT = 27;

	/**
	 * 数组行数
	 */
	private static final int CODE_ROW = 12;
	/**
	 * 数组列数
	 */
	private static final int CODE_COL = 7;

	// ...
}

上面定义的常量当中还有CORNER_WIDTH及CORNER_HEIGHT，这是因为有时有些方块会有道具标示，或者是是“*2”的分数提示，所以截取小图进行图像识别的时候还要避开这一点。然后上面提到的数组行列数，这里的数组不是取得的图像的数组。而是为了便于比较计算，将每个图像对应一个int数字，bomb或为空时为0。它的行及列分别为12和7，而不是10和5，是因为考虑到连连看的规则而加上的外围边界。如下图所示：

然后还要定义两个成员变量，一个表示取得的方块矩阵，一个表示对应的数字矩阵，代码如下：

	private BufferedImage images[][] = new BufferedImage[BOX_ROW][BOX_COL];
	/**
	 * 表示图片的数组，为12 * 7个。 图片共有10*5个单位，但是在进行路径计算的时候还要考虑四周，所以是12 * 7 个单位。
	 */
	private int imageCodes[][];

从截屏取得的大图中获取方块小图代码如下：

		for (int i = 0; i < images.length; i++) {
			for (int j = 0; j < images[i].length; j++) {
				images[i][j] = image.getSubimage(j * IMAGE_WIDTH + PADDING_LEFT + 3, i
						* IMAGE_HEIGHT + PADDING_TOP + 3, IMAGE_WIDTH - CORNER_WIDTH - 3,
						IMAGE_HEIGHT - CORNER_HEIGHT - 3);
			}
		}

上面代码中的+3及-3，是为了不计算方块的边界，可看情况修改，因为当游戏中出现提示时，方块的边框是有流动动画的，它如果被计算在内的话也会影响图像识别。
取得图之后，我们可以通过计算每个图像对应的hash值，然后对每种图像定义一个值，这样在游戏开始后，通过汉明距离算法就可以把图像转换为一个二维数组，进行连连看的方块消除搜索。当然 ，采用这一算法，需要先截得包含这些方块图像的游戏界面，然后计算出它们各自的hash值，进行存储。除去bomb，共有28种方块图像，多进行几次游戏就可以全截取到了。关于图片转换为hash值及进行相似判断的代码将在后面给出。
下面贴上将方块图片转换为int二维数组的代码，其中image是截取的屏幕的大图，然后取得小图边计算它的hash值，再调用distance判断是哪个图像方块：

	/**
	 * 通过获取的截图设置num数组
	 */
	public void setNum(BufferedImage image) {
		imageCodes = new int[CODE_ROW][CODE_COL];
		for (int i = 0; i < images.length; i++) {
			for (int j = 0; j < images[i].length; j++) {
				images[i][j] = image.getSubimage(j * IMAGE_WIDTH + PADDING_LEFT + 3, i
						* IMAGE_HEIGHT + PADDING_TOP + 3, IMAGE_WIDTH - CORNER_WIDTH - 3,
						IMAGE_HEIGHT - CORNER_HEIGHT - 3);
				String hash = mImgHash.getHash(images[i][j]);
				int minDis = Integer.MAX_VALUE;
				for (int k = 0; k < GAME_IMAGE.length; k++) {
					int dis = mImgHash.distance(GAME_IMAGE[k], hash);
					if (dis <= 8 && dis < minDis) {
						imageCodes[i + 1][j + 1] = k + 1;
						minDis = dis;
						if (minDis <= 0) {
							break;
						}
					}
				}
				// System.out.print(imageCodes[i + 1][j + 1] + "\t");
			}
			// System.out.println();
		}
	}

上面的mImgHash是一个ImageHash对象，也是我定义的实现汉明距离算法的类。GAME_IMAGE存储了每个方块图像对应的hash值，是之前计算得到的，定义如下：

public class Robot {
	/**
	 * 表示每个方块图像的HASH值
	 */
	private static final String[] GAME_IMAGE = {
			"0110000100110010101000110111110000010010101001110"/* 煎蛋 */,
			"0000001100000000011110100101100110111100000110000"/* 紫猫 */,
			"0010000101010101010100101110100000110101001101111"/* 白菜 */,
			"0000001001101001100011100110101110010100000010011"/* 茄子 */,
			"1001100100000101001100100111001100101110110100010"/* 兔子 */,
			"1000010001000101111010100100100011010010111011000"/* 莲藕 */,
			"0010010010100100101100110101100011011010010010001"/* 红虾 */,
			"1000000000101000100010111000110000011001111011100"/* 玉米 */,
			"0001100001100101101001010100111001101010110101100"/* 闪电 */,
			"0000000000100001010100011111101010010000000100000"/* 狐狸 */,
			"1100000101000000011110111011010011011100001100000"/* 白云 */,
			"1000011000110101100000110100010001110011001100000"/* 菠萝 */,
			"1000111001100101101010110100100001110110101011000"/* 草莓 */,
			"0000000001110011100001000011001110111001001100110"/* 蘑菇 */,
			"1111011000110100111001110100000101011000011100111"/* 蓝鼠 */,
			"1000000000001000111100110000110011110000011011101"/* 太阳 */,
			"1001100000001101100010111000110001010001110011100"/* 月亮 */,
			"1011100000001110100100101100010100101001011011010"/* 雪人 */,
			"1000011001101101011000111100101001111100011001100"/* 熊猫 */,
			"1000000000000001010100001110101010111000010100000"/* 黄熊 */,
			"1000000110100011001110111001100110001100001001011"/* 彩虹 */,
			"1010100000001001001000101001010111011000111001000"/* 雪花 */,
			"1000110001110001100010100000100111010100010010000"/* 西瓜 */,
			"1000001101011000011110110001010011001001010110110"/* 香蕉 */,
			"0001100000001101000001000000001100001001110100000"/* 蓝果实 */,
			"1000100011101111010001000110001000000010010100110"/* 葡萄 */,
			"0000100000011100110000101010100000111000101000111"/* 红果实 */,
			"1001100000110001000110110011001110001011000110011"/* 黄梨 */, };
	// ...
}

在遍历GAME_IMAGE数组进行每个方块的相似识别时，通常距离小于5的都可以认为是相似图片，在这里会比较与哪一个图片的hash距离最小是因为取得的方块图片都较小，为避免识别错误需要对每个图片都进行距离判断（因为一开始我取的识别精度并不是5，而是8，极少数情况下会有图片识别错误）。

最后附上汉明距离算法的代码：

 * @(#)ImageHash.java	       Project:lianmeng
 * Date-Time:2013-10-11 下午7:40:20
 *
 * Copyright (c) 2013 CFuture09, Institute of Software, 
 * Guangdong Ocean University, Zhanjiang, GuangDong, China.
 * All rights reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package pw.msdx.lianmengassistant;

import java.awt.Graphics2D;
import java.awt.color.ColorSpace;
import java.awt.image.BufferedImage;
import java.awt.image.ColorConvertOp;

/*
 * pHash-like image hash. 
 * Author: Elliot Shepherd ([e-mail]
 * Based On: http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html
 * 
 * Optimize by Geek_Soledad.
 */
public class ImageHash {

	private int size = 8;
	private int smallerSize = 8;

	public ImageHash() {
		initCoefficients();
	}

	public ImageHash(int size, int smallerSize) {
		this.size = size;
		this.smallerSize = smallerSize;

		initCoefficients();
	}

	public int distance(String s1, String s2) {
		int counter = 0;
		for (int k = 0; k < s1.length(); k++) {
			if (s1.charAt(k) != s2.charAt(k)) {
				counter++;
			}
		}
		return counter;
	}

	// Returns a 'binary string' (like. 001010111011100010) which is easy to do
	// a hamming distance on.
	public String getHash(BufferedImage img) {
		/*
		 * 1. Reduce size. Like Average Hash, pHash starts with a small image.
		 * However, the image is larger than 8x8; 32x32 is a good size. This is
		 * really done to simplify the DCT computation and not because it is
		 * needed to reduce the high frequencies.
		 */
		img = resize(img, size, size);

		/*
		 * 2. Reduce color. The image is reduced to a grayscale just to further
		 * simplify the number of computations.
		 */
		img = grayscale(img);

		double[][] vals = new double[size][size];

		for (int x = 0; x < img.getWidth(); x++) {
			for (int y = 0; y < img.getHeight(); y++) {
				vals[x][y] = getBlue(img, x, y);
			}
		}

		/*
		 * 3. Compute the DCT. The DCT separates the image into a collection of
		 * frequencies and scalars. While JPEG uses an 8x8 DCT, this algorithm
		 * uses a 32x32 DCT.
		 */
		double[][] dctVals = applyDCT(vals);

		/*
		 * 4. Reduce the DCT. This is the magic step. While the DCT is 32x32,
		 * just keep the top-left 8x8. Those represent the lowest frequencies in
		 * the picture.
		 */
		/*
		 * 5. Compute the average value. Like the Average Hash, compute the mean
		 * DCT value (using only the 8x8 DCT low-frequency values and excluding
		 * the first term since the DC coefficient can be significantly
		 * different from the other values and will throw off the average).
		 */
		double total = 0;

		for (int x = 0; x < smallerSize; x++) {
			for (int y = 0; y < smallerSize; y++) {
				total += dctVals[x][y];
			}
		}
		total -= dctVals[0][0];

		double avg = total / (double) ((smallerSize * smallerSize) - 1);

		/*
		 * 6. Further reduce the DCT. This is the magic step. Set the 64 hash
		 * bits to 0 or 1 depending on whether each of the 64 DCT values is
		 * above or below the average value. The result doesn't tell us the
		 * actual low frequencies; it just tells us the very-rough relative
		 * scale of the frequencies to the mean. The result will not vary as
		 * long as the overall structure of the image remains the same; this can
		 * survive gamma and color histogram adjustments without a problem.
		 */
		StringBuilder hash = new StringBuilder();

		for (int x = 0; x < smallerSize; x++) {
			for (int y = 0; y < smallerSize; y++) {
				if (x != 0 && y != 0) {
					hash.append(dctVals[x][y] > avg ? "1" : "0");
				}
			}
		}
		return hash.toString();
	}

	private BufferedImage resize(BufferedImage image, int width, int height) {
		BufferedImage resizedImage = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
		Graphics2D g = resizedImage.createGraphics();
		g.drawImage(image, 0, 0, width, height, null);
		g.dispose();
		return resizedImage;
	}

	private ColorConvertOp colorConvert = new ColorConvertOp(
			ColorSpace.getInstance(ColorSpace.CS_GRAY), null);

	private BufferedImage grayscale(BufferedImage img) {
		colorConvert.filter(img, img);
		return img;
	}

	private static int getBlue(BufferedImage img, int x, int y) {
		return (img.getRGB(x, y)) & 0xff;
	}

	// DCT function stolen from
	// http://stackoverflow.com/questions/4240490/problems-with-dct-and-idct-algorithm-in-java

	private double[] c;

	private void initCoefficients() {
		c = new double[size];

		for (int i = 1; i < size; i++) {
			c[i] = 1;
		}
		c[0] = 1 / Math.sqrt(2.0);
	}

	private double[][] applyDCT(double[][] f) {
		int N = size;
		double[][] F = new double[N][N];
		for (int u = 0; u < N; u++) {
			for (int v = 0; v < N; v++) {
				double sum = 0.0;
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						sum += Math.cos(((2 * i + 1) / (2.0 * N)) * u * Math.PI)
								* Math.cos(((2 * j + 1) / (2.0 * N)) * v * Math.PI) * (f[i][j]);
					}
				}
				sum *= ((c[u] * c[v]) / 4.0);
				F[u][v] = sum;
			}
		}
		return F;
	}

}