一种简单的图像识别技术

摘  要： 图像识别，是指利用计算机对图像进行处理、分析和理解，以识别各种不同模式的目标和对象的技术，是应用深度学习算法的一种实践应用。图像的传统识别流程分为四个步骤：图像采集→图像预处理→特征提取→图像识别。现在通用的图像识别算法是k-means算法以及词袋模型。但是该算法非常复杂，对于普通人学习起来难度极大。本人发明了一种非常简单的图像识别算法，普通人一看就懂。

关键词： 动物;洞;种子填充;图像识别;特征

中图分类号： TP391. 41    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.12.048

本文著录格式：童小明. 一种简单的图像识别技术[J]. 软件，2019，40（12）：218221+225

A Simple Image Recognition Technology

TONG Xiao-ming

（Xinyu Xingang Middle School， Jiangxi Xinyu 338000）

【Abstract】： Image recognition refers to the technology of using computer to process， analyze and understand images to identify objects and objects of different modes. The traditional image recognition process is divided into four steps： image acquisition image preprocessing feature extraction image recognition.

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.

【Key words】： Animal; Cave; SeedFilling; ImageRecognition; Features

0  引言

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

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

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

图1  不同的动物符号

Fig.1  Different animal symbols

每组数据包含一个H行W列的字符矩阵（H<=200， W<=50），每个字符为4个相邻像素点的十六进制（例如10011100对应的字符是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  输入数据

100 25

0000000000000000000000000

0000000000000000000000000

……

0000000000000000000000000

0000000000000000000000000

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 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  主函數

int main（）

{

初始化

读取输入数据到buffer中[2]

fin.close（）[1];

确定实际行数为H2， 实际列数为W*4 [6]

查找所有动物

逐一判断6种动物，如果该动物存在，则输出它的字符表示[10]。

fout.close（）[1];

程序结束

}

3.3  查找所有动物

void FindAllSigns（）

{

将访问标志visited设置为0

blocks = 0;

//开始查找连通块

while （true）

{

found = false;

遍历buffer中的每行每列的每个字符，如果buffer[i][j]=1（边界字符），

并且访问标志visited[i][j]=0，则

{ blocks++; found = true; goto FINDHOLLOW; //找到了一个连通块  }

FINDHOLLOW：

if （found）

{

用该动物编号blocks从指定位置（i，j）开始填充外框（所有黑点1）

int hollows = 0;

从指定位置（i，j）开始确定该连通块的类型（有几个洞hollows）

types[hollows] = true;

}

else break;

}

输出发现了几个动物

}

3.4  查找该动物中的洞个数

//（x，y）是该动物的起始位置，number是该动物的编号

void FindHollows（...）

{

minx=H-1， maxx=0， miny=W-1， maxy=0;

确定[minx， maxx]， [miny， maxy] [4]; 输出[minx， maxx]， [miny， maxy]

用该动物编号number填充矩形框内动物外面的空气（所有白洞）

while（true）

{

找第一个未访问的空气白洞，返回未访问的空气白洞位置是（x0，y0）

如果没有找到未访问的白洞，则退出

输出未访问的空气白洞位置（x0， y0）

用该动物编号number，从位置（x0，y0）开始填充矩形框内动物外面的空气白洞

hollows=0;

//开始找动物内的白洞个数

while（true）

{

找动物体内的第一个白洞所在位置（x0， y0）

if（x0 == -1 && y0 == -1） break; //没有找到

输出动物体内的一个白洞位置（x0， y0）

用该动物编号number填充动物体内的从位置（x0，y0）开始的白洞

hollows++;

}

}

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

void FindFirstAirWhiteHollow（...）

{

//从上到下搜索

for（i=minx;i <= maxx;i++）

{

从左到右找，先跳过连续的'0'+number

if （j > maxy） continue;

//判断是否是动物内部的洞

得到[minx， maxx]， [miny， maxy] 内部位置（i，j）开始的左右边界和上下边界[5]

如果是动物内部的洞，则判断下一个洞

if（visited[i][j] == '0' && buffer[i][j] == '0'） { x0=i， y0=j;  return; }

从右到左找，先跳过连续的'0'+number

代码与上面类似

}

//从下到上搜索

与上述代码块类似

x0=y0=-1;

}

3.6  种子填充[3] （找外框）

void FloodFill（...）

{

如果（x，y）已经填充，则返回

遍历四个方向

{

int x2 = x + dx[i]， y2 = y + dy[i];

如果坐标非法，则判断下一个方向

如果位置（buffer[x2][y2]未填充，则从位置（x2，y2）开始用number填充

}

}

3.7  种子填充[3] （找空洞）

//（x，y）是该动物的第一个洞的起始位置，number是該动物的编号

bool FloodFill0（...）

{

bool ret = true;

如果x或y到达边界，则返回假;如果（x，y）已经填充，则返回真

visited[x][y] = '0'+number;

其它与“种子填充[3] （找外框）”相同

}

3.8  当上下走时确定左右边界

void GetLeftRight（...）

{

int y0 = y;

往左一直走，如果y

if （buffer[x][y] == '1'） { L = y; break;}

y = y0;

往右一直走，如果y>maxy，则R=maxy

if （buffer[x][y] == '1'） { R = y; break; }

}

3.9  当左右走时确定上下边界

与上述代码类似，大家可以模仿写出。

4  调试输出结果[9]

实际行数是82，列数是100

初始地图中，三个动物外框都用1表示，三个动物内部和外面都用0表示。

4.1  查找第一个动物

（1）初始状态，第一个动物边界全部填充1

（2）查找动物的外围空气

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

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

中间状态，第一个动物的边框中，动物的左上部外围空气全部填充1

…

（3）最终，第一个动物的边框内部全部填充1

4.2  查找第二个动物

（1）初始状态，第一个动物边界全部填充2

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

（2）查找动物的外围空气

…

（3）最终，第二个动物的边框内部全部填充2，但是左下部个别格子为0

4.3  查找第三个动物

（1）初始状态，第一个动物边界全部填充3

…

11111111111110000000033000000000000000002222222

00000000000000000003333333333000000000002222222

00000000000000000033333333333300000000002222222

00000000000000003333333333333330000000002222222

00000000000000033333000000033333300000002222222

00000000000000333330000000000333300000002222222

00000000000003333000000000000003330000002222222

00000000000003330000000000000000333000002222222

00000000000033300000000000000000333300002222222

00000000000333300000000000000000033300002222222

00000033300333300000000000000000003330002222222

00003333333333000000000000000000003330002222222

00003333333333000000000000000000003330002222222

00033330033330000000000000000000003333002222222

00033300003330000000000000000000000330033222222

00033000003333000000000000000000000333333332222

00333000000333000000000000000000003333333333222

00333000000333000000000000000000003333302333222

00333000000333300000000000000000003333002233322

00333000000033330000000000000000033330002233322

00333000000033330000000000000000033300002233322

00333000000003333000000000000000333000000033300

00330000000000333300000000000003330000000033000

03330000000000033333000000000033300000000033000

03330000000000003333333300333333000000000033000

03330000000000000333333333333330000000000333000

03330000000000000000033333333000000000000333000

03333300000000000000000333000000000000000333000

03333333333330000000000000000000000000000333000

03333333333333333333300000000000000000000333000

00000003333333333333333333330000000000000330000

00000000000000333333333333333333333000000330000

00000000000000000000003333333333333333333330000

00000000000000000000000000000333333333333330000

00000000000000000000000000000000000033333330000

注意到3和2有些交叉，但并不影響算法的正确性。

（2）查找动物的外围空气

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

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

（下转第225页）