Now the general image recognition algorithms are k-means algorithm and word bag model. But the algorithm is very complex, and it is very difficult for ordinary people to learn. I have invented a very simple image recognition algorithm, ordinary people can understand it at a glance.

0 引言

图像识别，是指利用计算机对图像进行处理、分析和理解，以识别各种不同模式的目标和对象的技术。图像的传统识别流程分为四个步骤：图像采集→图像预处理→特征提取→图像识别。

现在通用的图像识别算法是k-means 算法以及词袋模型。但是该算法非常复杂，对于普通人学习起来难度极大。本人发明了一种非常简单的图像识别算法，普通人一看就懂，下面举出一个例子进行说明。

识别3000 年前的6 种动物。如图1 所示。

图1 不同的动物符号Fig.1 Different animal symbols

每组数据包含一个 H 行 W 列的字符矩阵（H＜=200, W＜=50），每个字符为4 个相邻像素点的十六进制（例如 对应的字符是9c）。转化为二进制后1 表示黑点，0 表示白点。

输入满足：

不会出现上述6 种符号之外的其它符号。

输入至少包含一个动物，且每个黑像素都属于一个动物。

每个动物都是一个四连块，并且不同动物不会相互接触，也不会相互包含。

如果两个黑像素有公共顶点，则它们一定有一个相同的相邻黑像素（有公共边）。

动物的形状一定和表6-9 中的图形拓扑等价（可以随意拉伸但不能拉断）。

要求按照字典序输出所有动物。例如图6-11 中的输出应为AKW。

1 解题思路

每个动物都是一个四连块，即所有黑点都连在一起，而中间有一些白色的洞。

题目表中的6 个动物从左到右依次有1，3，5，4，0，2 个洞，各不相同。

这样只要数一数输入的动物有几个“白洞”，就能准确知道它是哪个动物。

算法步骤如下：

（1）先确定第一个动物的外框（值都是1），然后填充该外框。

（2）确定该动物的边界（长方形[(minx,miny)- (maxx,maxy)]）。

（3）先找动物边界外面（在长方形[(minx,miny)- (maxx, maxy)]内，后面相同）的洞，

然后填充；继续找动物外面的洞，然后填充；直到动物边界外面没有洞为止。

（4）然后找动物内部的洞，找到一个洞，然后填充；继续找动物内部的洞，然后填充；

直到动物内部没有洞为止。

（5）然后继续查找其它动物（值依次递增），重复步骤（1）到步骤（4），直到找不到动物为止。

（6）输出结果。

2 输入数据格式及输出结果

2.1 输入数据

2.2 输出结果

实际行数是82，列数是100

查找动物的外围空气

minx=0, miny=9, maxx=47, maxy=35

未访问的空气白洞位置是x0=0, y0=9

…

动物体内的一个白洞位置是（4, 21）

查找动物的外围空气

minx=6, miny=63, maxx=67, maxy=88

未访问的空气白洞位置是x0=6, y0=63

…

查找动物的外围空气

minx=47, miny=24, maxx=81, maxy=67

未访问的空气白洞位置是x0=48, y0=24

…

动物体内的一个白洞位置是（51, 43）

动物体内的一个白洞位置是（60, 30）

发现了3 个动物

AKW

3 算法设计

3.1 数据类型和初始化

char sign[6]; //代表该动物的字符 set＜char> S;

int H, H2, W; //H2 为实际行数

…

int blocks; //连通块个数

bool types[6]; //该洞数存在，则为真

int dx[4] = {-1, 0, 1, 0}; int dy[4] = { 0, 1, 0, -1};

…

//6 个动物从左到右依次有1，3，5，4，0，2个洞

void Init() //初始化

{ sign[1] = 'K'; sign[3] = 'J'; sign[5] = 'D';

sign[4] = 'S';sign[0] = 'W'; sign[2] = 'A'; }

3.2 主函数

3.3 查找所有动物

3.4 查找该动物中的洞个数

3.5 查找第一个未访问的空气白洞