[聊天] 接龍小遊戲 自動查表器

覺得小遊戲查表好麻煩，做了一個查表器

附上人權
http://i.imgur.com/vzuo7ru.jpg

# 實驗成果
v1
https://youtu.be/IcirpEYB2lY

v2,感謝小精靈改scrcpy
https://youtu.be/Nb9cCh4DmgY

# source code
aHR0cHM6Ly9wYXN0ZWJpbi5jb20vajhNY3F4RGE=

# 實驗環境
- Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
- 12G RAM
- MX500 SSD
- Ubuntu 19.10

# 辨識九宮格圖示
OpenCV提供大量函式，為此我們使用了 `matchTemplate` 辨識圖示，整體流程如下
1. 切割原始圖片成單張圖示(icon)，大小為106x106px
2. 調整大小至78x78px
3. 用 `matchTemplate` 比對148張既有圖示，排序 `min_val`，找出最大值所對應的圖示和ID

得益於Profiling工具的日新月異，我用cProfile分析單執行緒的 python script，發現最耗時的地方位於`templateMatching`，足足佔了整體執行時間97%‧

```bash
~$ python3 -m cProfile -s tottime ./tmp.py
0.7606322765350342
325680 function calls (318751 primitive calls) in 1.289 seconds

Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
1287 0.741 0.001 0.741 0.001 {matchTemplate}
28/17 0.162 0.006 0.240 0.014 {built-in method
_imp.create_dynamic}
280 0.045 0.000 0.045 0.000 {built-in method marshal.loads} 2 0.041 0.020 0.041 0.020 {imread}
```

### 全彩轉灰階
試著將全彩圖示轉換成灰階再進行比對
```bash
~$ python3 -m cProfile -s tottime ./tmp.py
0.2725179195404053
326034 function calls (319105 primitive calls) in 0.811 seconds

Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
1287 0.256 0.000 0.256 0.000 {matchTemplate}
```
看的出 maximum overhead 還是在`templateMatch`，但總執行時間足足少了65%‧

### 縮小圖示再比對
將兩邊要比對的78x78px縮小至26x26px，於是`matchTemplate`讓出寶座，整體執行時間更是來到 0.05s(-80%)，圖示辨識率也還是維持100%。
```
0.05796694755554199
326071 function calls (319142 primitive calls) in 0.613 seconds

Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
28/17 0.153 0.005 0.234 0.014 {built-in method
_imp.create_dynamic}
280 0.046 0.000 0.046 0.000 {built-in method marshal.loads} 2 0.043 0.022 0.043 0.022 {imread}
1287 0.042 0.000 0.042 0.000 {matchTemplate}
1175/1120 0.021 0.000 0.073 0.000 {built-in method
builtins.__build_class__}
```
為了減少執行時間，我們也測試圖片大小和辨識準確率關係，程式有做一些改動(印出正確率、存測試資料)，下方數據只是作為 Image size 的選取依據並非實際執行時間。測試腳本如下
```bash
for i in `seq 78 -2 1`;do icon_size=$i python3 tmp.py; done;
```
只用一張遊戲畫面圖片做測試
icon size | elapsed time (sec)| accurate rate %）
---|---|---
78x78|0.2452|100.0
26x26|0.0758|100.0
24x24|0.0447|100.0
22x22|0.0434|100.0
20x20|0.0390|100.0
18x18|0.0389|88.9
16x16|0.0339|77.8
14x14|0.0473|77.8
12x12|0.0277|66.7
10x10|0.0295|77.8
8x8|0.0248|55.6
6x6|0.0234|55.6
4x4|0.0221|11.1
2x2|0.0210|11.1

看來極限能到20x20px，取20x20的耗時較26x26減少30%

26x26
```
0.0584
326155 function calls (319226 primitive calls) in 0.573 seconds

Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
28/17 0.144 0.005 0.221 0.013 {built-in method
_imp.create_dynamic}
280 0.045 0.000 0.045 0.000 {built-in method marshal.loads} 1287 0.043 0.000 0.043 0.000 {matchTemplate}
```

20x20
```
0.0406
326057 function calls (319128 primitive calls) in 0.628 seconds

Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
28/17 0.158 0.006 0.242 0.014 {built-in method
_imp.create_dynamic}
280 0.050 0.000 0.050 0.000 {built-in method marshal.loads} 2 0.043 0.021 0.043 0.021 {imread}
1287 0.025 0.000 0.025 0.000 {matchTemplate}
```
不知道為什麼行的通...但是算了

### 使用python的sorted
Python的`sorted`使用名為Timsort的混合式排序演算法，使用`sorted`減少了0.0006秒的執行時間
```
0.0385->0.0379
```
```python=
# Before
def findIconId(img):
id = None
result = -1
for icon in icons.values():
min_val, max_val, min_loc, max_loc = cv.minMaxLoc(res)
if (result < min_val):
result = min_val
id = icon.id
return id

# After
def findIconId(img):
arr=[]
for icon in icons.values():
res = cv.matchTemplate(resized,icon.img,cv.TM_CCOEFF)
min_val, max_val, min_loc, max_loc = cv.minMaxLoc(res)
arr.append((min_val, icon.id))
arr = sorted(arr, key= lambda x: x[0],reverse=True)
return arr[0][1]
```
### Multithreading
最後手段，但用了反而增加時間，不予採用。
`0.0373->0.0494 secs`

你知道 python 的 multithreading 跟你想像的不一樣嗎？
:::success
"_Each thread that wants to run must wait for the GIL to be released by the
other thread, which means your multi-threaded Python application is actually
single threaded._"

https://medium.com/practo-engineering/threading-vs-multiprocessing-in-python-7b57f224eadb
:::

### 保險機制
遊戲中的過場畫面可不能拿來辨識，因此次要設計用一套方法來判斷何時該開始辨識
1. 用像素點顏色判斷白邊存在
2. 偵測白色反光，取圖示中心的點做判斷

兩項測試都通過後才會進行template matching
**valid**
> 
>
>**invalid**
> 
> 
> 
> 
> 
> 

### 辨識韻母
韻母只有一張圖要和38張圖比對，尺寸小，耗時短，不在此多著墨。

# 選取演算法
這部份沒什麼特別，目標就是最高分的圖示。以滿圖鑑為目標？不會多點幾次?

--

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.248.3.243 (臺灣) ※ 編輯: gR7P4zXH (118.161.105.58 臺灣), 03/08/2020 08:52:43

跑實驗閒暇時做的

講完R

沒有按鍵精靈

比較想去.net折衣服

我自己手動點，不算外掛喔

糞扣公開傷眼

好

請開spec

這是在家搞的

泳犬小遊戲?

影像公司泊車小弟

怎麼這麼多人知道git

不用學，這沒用到理論

凸了墓

都蕊咪發搜

站內信

大佬跑錯板了

感謝建議，但已達到可用標準，懶得再改

※ 編輯: gR7P4zXH (111.248.3.243 臺灣), 03/09/2020 03:20:04 ※ 編輯: gR7P4zXH (111.248.3.243 臺灣), 03/09/2020 03:30:37 ※ 編輯: gR7P4zXH (111.248.3.243 臺灣), 03/09/2020 03:57:56 ※ 編輯: gR7P4zXH (1.171.87.231 臺灣), 03/09/2020 04:49:11