一種簡單的圖像識別技術

摘 ?要： 圖像識別，是指利用計算機對圖像進行處理、分析和理解，以識別各種不同模式的目標和對象的技術，是應用深度學習算法的一種實踐應用。圖像的傳統識別流程分為四個步驟：圖像采集→圖像預處理→特征提取→圖像識別。現在通用的圖像識別算法是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頁）