一種簡單的圖像識別技術(shù)

摘 ?要： 圖像識別，是指利用計(jì)算機(jī)對圖像進(jìn)行處理、分析和理解，以識別各種不同模式的目標(biāo)和對象的技術(shù)，是應(yīng)用深度學(xué)習(xí)算法的一種實(shí)踐應(yīng)用。圖像的傳統(tǒng)識別流程分為四個(gè)步驟：圖像采集→圖像預(yù)處理→特征提取→圖像識別?，F(xiàn)在通用的圖像識別算法是k-means算法以及詞袋模型。但是該算法非常復(fù)雜，對于普通人學(xué)習(xí)起來難度極大。本人發(fā)明了一種非常簡單的圖像識別算法，普通人一看就懂。

關(guān)鍵詞： 動(dòng)物;洞;種子填充;圖像識別;特征

中圖分類號： TP391. 41 ? ?文獻(xiàn)標(biāo)識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.12.048

本文著錄格式：童小明. 一種簡單的圖像識別技術(shù)[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 ?引言

圖像識別，是指利用計(jì)算機(jī)對圖像進(jìn)行處理、分析和理解，以識別各種不同模式的目標(biāo)和對象的技術(shù)。圖像的傳統(tǒng)識別流程分為四個(gè)步驟：圖像采集→圖像預(yù)處理→特征提取→圖像識別。

現(xiàn)在通用的圖像識別算法是k-means算法以及詞袋模型。但是該算法非常復(fù)雜，對于普通人學(xué)習(xí)起來難度極大。本人發(fā)明了一種非常簡單的圖像識別算法，普通人一看就懂，下面舉出一個(gè)例子進(jìn)行說明。

識別3000年前的6種動(dòng)物。如圖1所示。

圖1 ?不同的動(dòng)物符號

Fig.1 ?Different animal symbols

每組數(shù)據(jù)包含一個(gè)H行W列的字符矩陣（H<=200， W<=50），每個(gè)字符為4個(gè)相鄰像素點(diǎn)的十六進(jìn)制（例如10011100對應(yīng)的字符是9c）。轉(zhuǎn)化為二進(jìn)制后1表示黑點(diǎn)，0表示白點(diǎn)。

輸入滿足：

不會(huì)出現(xiàn)上述6種符號之外的其它符號。

輸入至少包含一個(gè)動(dòng)物，且每個(gè)黑像素都屬于一個(gè)動(dòng)物。

每個(gè)動(dòng)物都是一個(gè)四連塊，并且不同動(dòng)物不會(huì)相互接觸，也不會(huì)相互包含。

如果兩個(gè)黑像素有公共頂點(diǎn)，則它們一定有一個(gè)相同的相鄰黑像素（有公共邊）。

動(dòng)物的形狀一定和表6-9中的圖形拓?fù)涞葍r(jià)（可以隨意拉伸但不能拉斷）。

要求按照字典序輸出所有動(dòng)物。例如圖6-11中的輸出應(yīng)為AKW。

1 ?解題思路

每個(gè)動(dòng)物都是一個(gè)四連塊，即所有黑點(diǎn)都連在一起，而中間有一些白色的洞。

題目表中的6個(gè)動(dòng)物從左到右依次有1，3，5，4，0，2個(gè)洞，各不相同。

這樣只要數(shù)一數(shù)輸入的動(dòng)物有幾個(gè)“白洞”，就能準(zhǔn)確知道它是哪個(gè)動(dòng)物。

算法步驟如下：

（1）先確定第一個(gè)動(dòng)物的外框（值都是1），然后填充該外框。

（2）確定該動(dòng)物的邊界（長方形[（minx，miny）- （maxx，maxy）]）。

（3）先找動(dòng)物邊界外面（在長方形[（minx，miny）- （maxx， maxy）]內(nèi)，后面相同）的洞，

然后填充;繼續(xù)找動(dòng)物外面的洞，然后填充;直到動(dòng)物邊界外面沒有洞為止。

（4）然后找動(dòng)物內(nèi)部的洞，找到一個(gè)洞，然后填充;繼續(xù)找動(dòng)物內(nèi)部的洞，然后填充;

直到動(dòng)物內(nèi)部沒有洞為止。

（5）然后繼續(xù)查找其它動(dòng)物（值依次遞增），重復(fù)步驟（1）到步驟（4），直到找不到動(dòng)物為止。

（6）輸出結(jié)果。

2 ?輸入數(shù)據(jù)格式及輸出結(jié)果

2.1 ?輸入數(shù)據(jù)

100 25

0000000000000000000000000

0000000000000000000000000

……

0000000000000000000000000

0000000000000000000000000

2.2 ?輸出結(jié)果

實(shí)際行數(shù)是82，列數(shù)是100

查找動(dòng)物的外圍空氣

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

未訪問的空氣白洞位置是x0=0， y0=9

…

動(dòng)物體內(nèi)的一個(gè)白洞位置是（4， 21）

查找動(dòng)物的外圍空氣

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

未訪問的空氣白洞位置是x0=6， y0=63

…

查找動(dòng)物的外圍空氣

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

未訪問的空氣白洞位置是x0=48， y0=24

…

動(dòng)物體內(nèi)的一個(gè)白洞位置是（51， 43）

動(dòng)物體內(nèi)的一個(gè)白洞位置是（60， 30）

發(fā)現(xiàn)了3個(gè)動(dòng)物

AKW

3 ?算法設(shè)計(jì)

3.1 ?數(shù)據(jù)類型和初始化

char sign[6]; //代表該動(dòng)物的字符

set S;

int H， H2， W; //H2為實(shí)際行數(shù)

…

int blocks; //連通塊個(gè)數(shù)

bool types[6]; //該洞數(shù)存在，則為真

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

…

//6個(gè)動(dòng)物從左到右依次有1，3，5，4，0，2個(gè)洞

void Init（） //初始化

{ sign[1] = 'K'; sign[3] = 'J'; sign[5] = 'D'; sign[4] = 'S';sign[0] = 'W'; sign[2] = 'A'; }

3.2 ?主函數(shù)

int main（）

{

初始化

讀取輸入數(shù)據(jù)到buffer中[2]

fin.close（）[1];

確定實(shí)際行數(shù)為H2， 實(shí)際列數(shù)為W*4 [6]

查找所有動(dòng)物

逐一判斷6種動(dòng)物，如果該動(dòng)物存在，則輸出它的字符表示[10]。

fout.close（）[1];

程序結(jié)束

}

3.3 ?查找所有動(dòng)物

void FindAllSigns（）

{

將訪問標(biāo)志visited設(shè)置為0

blocks = 0;

//開始查找連通塊

while （true）

{

found = false;

遍歷buffer中的每行每列的每個(gè)字符，如果buffer[i][j]=1（邊界字符），

并且訪問標(biāo)志visited[i][j]=0，則

{ blocks++; found = true; goto FINDHOLLOW; //找到了一個(gè)連通塊 ?}

FINDHOLLOW：

if （found）

{

用該動(dòng)物編號blocks從指定位置（i，j）開始填充外框（所有黑點(diǎn)1）

int hollows = 0;

從指定位置（i，j）開始確定該連通塊的類型（有幾個(gè)洞hollows）

types[hollows] = true;

}

else break;

}

輸出發(fā)現(xiàn)了幾個(gè)動(dòng)物

}

3.4 ?查找該動(dòng)物中的洞個(gè)數(shù)

//（x，y）是該動(dòng)物的起始位置，number是該動(dòng)物的編號

void FindHollows（...）

{

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

確定[minx， maxx]， [miny， maxy] [4]; 輸出[minx， maxx]， [miny， maxy]

用該動(dòng)物編號number填充矩形框內(nèi)動(dòng)物外面的空氣（所有白洞）

while（true）

{

找第一個(gè)未訪問的空氣白洞，返回未訪問的空氣白洞位置是（x0，y0）

如果沒有找到未訪問的白洞，則退出

輸出未訪問的空氣白洞位置（x0， y0）

用該動(dòng)物編號number，從位置（x0，y0）開始填充矩形框內(nèi)動(dòng)物外面的空氣白洞

hollows=0;

//開始找動(dòng)物內(nèi)的白洞個(gè)數(shù)

while（true）

{

找動(dòng)物體內(nèi)的第一個(gè)白洞所在位置（x0， y0）

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

輸出動(dòng)物體內(nèi)的一個(gè)白洞位置（x0， y0）

用該動(dòng)物編號number填充動(dòng)物體內(nèi)的從位置（x0，y0）開始的白洞

hollows++;

}

}

3.5 ?查找第一個(gè)未訪問的空氣白洞

void FindFirstAirWhiteHollow（...）

{

//從上到下搜索

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

{

從左到右找，先跳過連續(xù)的'0'+number

if （j > maxy） continue;

//判斷是否是動(dòng)物內(nèi)部的洞

得到[minx， maxx]， [miny， maxy] 內(nèi)部位置（i，j）開始的左右邊界和上下邊界[5]

如果是動(dòng)物內(nèi)部的洞，則判斷下一個(gè)洞

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

從右到左找，先跳過連續(xù)的'0'+number

代碼與上面類似

}

//從下到上搜索

與上述代碼塊類似

x0=y0=-1;

}

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

void FloodFill（...）

{

如果（x，y）已經(jīng)填充，則返回

遍歷四個(gè)方向

{

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

如果坐標(biāo)非法，則判斷下一個(gè)方向

如果位置（buffer[x2][y2]未填充，則從位置（x2，y2）開始用number填充

}

}

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

//（x，y）是該動(dòng)物的第一個(gè)洞的起始位置，number是該動(dòng)物的編號

bool FloodFill0（...）

{

bool ret = true;

如果x或y到達(dá)邊界，則返回假;如果（x，y）已經(jīng)填充，則返回真

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

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

}

3.8 ?當(dāng)上下走時(shí)確定左右邊界

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 ?當(dāng)左右走時(shí)確定上下邊界

與上述代碼類似，大家可以模仿寫出。

4 ?調(diào)試輸出結(jié)果[9]

實(shí)際行數(shù)是82，列數(shù)是100

初始地圖中，三個(gè)動(dòng)物外框都用1表示，三個(gè)動(dòng)物內(nèi)部和外面都用0表示。

4.1 ?查找第一個(gè)動(dòng)物

（1）初始狀態(tài)，第一個(gè)動(dòng)物邊界全部填充1

（2）查找動(dòng)物的外圍空氣

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

未訪問的空氣白洞位置是x0=0， y0=9

中間狀態(tài)，第一個(gè)動(dòng)物的邊框中，動(dòng)物的左上部外圍空氣全部填充1

…

（3）最終，第一個(gè)動(dòng)物的邊框內(nèi)部全部填充1

4.2 ?查找第二個(gè)動(dòng)物

（1）初始狀態(tài)，第一個(gè)動(dòng)物邊界全部填充2

動(dòng)物體內(nèi)的一個(gè)白洞位置是（4， 21）

（2）查找動(dòng)物的外圍空氣

…

（3）最終，第二個(gè)動(dòng)物的邊框內(nèi)部全部填充2，但是左下部個(gè)別格子為0

4.3 ?查找第三個(gè)動(dòng)物

（1）初始狀態(tài)，第一個(gè)動(dòng)物邊界全部填充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）查找動(dòng)物的外圍空氣

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

未訪問的空氣白洞位置是x0=48， y0=24

（下轉(zhuǎn)第225頁）