はじめに

トポロメモリーというカードゲームを知っていますか。カードに書かれた位相同型な図形を見つけたらカードを奪い合うというゲームです。このゲームを友人と遊んだときに位相同型な熟語を探すゲームを追加でやったので、これの解をopencvの力を借りて解析してみようと思います。

環境

OS:macOSX
Python: 3.6.8
opencv: 4.0.0.21
numpy: 1.15.0

手段

辞書としてmecab辞書を使用します。全部の名詞辞書(228297個)から探します。

抽出

csvファイルを1つずつ開けて見出し語のみ抽出します。numpy.arrayに変換してからスライスします。これを全部繋げます。

csvnoun.py

import csv
import codecs
import numpy as np
from functools import reduce
csvs = [
    "Noun.csv",
    "Noun.adjv.csv",
    "Noun.adverbal.csv",
    "Noun.demonst.csv",
    "Noun.nai.csv",
    "Noun.name.csv",
    "Noun.number.csv",
    "Noun.org.csv",
    "Noun.others.csv",
    "Noun.place.csv",
    "Noun.proper.csv",
    "Noun.verbal.csv"
]
filedelimitor = "~/mecab-ipadic-2.7.0-20070801/"
def csv_1(csv_file):
    with codecs.open(filedelimitor+csv_file, "r","euc_jp") as f:
        reader = csv.reader(f)
        csv_words = [k for k in reader]
        csv_words_np = np.array(csv_words)
        return(csv_words_np[:,0].tolist())

words = reduce(lambda x,y:x+y,[csv_1(k) for k in csvs])
print(words[0:10])
print("個数:",len(words))

手元環境では2秒くらいかかります。

生成

opencvでは日本語文字の出力が面倒なためpillowで生成します。

char_img.py

import cv2
from PIL import Image, ImageDraw, ImageFont
import numpy as np

img = Image.new("L",(500, 500),"white")
char = "あ"
jpfont = ImageFont.truetype("/System/Library/Fonts/ヒラギノ角ゴシック W4.ttc",500)
draw = ImageDraw.Draw(img)
draw.text((0,0),char,font=jpfont,fill="black")
img_cv = np.array(img,dtype=np.uint8)

OSX以外で動かす場合はjpfontを適切なfontに変更してください。

解析

opencvにはcv2.findContoursという関数があるのでこれを使います。2値画像の輪郭を検出する関数です。
(参考:http://labs.eecs.tottori-u.ac.jp/sd/Member/oyamada/OpenCV/html/py_tutorials/py_imgproc/py_contours/py_contours_begin/py_contours_begin.html)
フラグ(第二引数)をRETR_TREEにした時、hierarcyに全階層構造が保持されます。この階層構造を使います。hierarcyは[Next, Previous, First_Child, Parent]の構造で格納されます。このうち、parentを全て調べることで構造がわかるので、parentのみを使います。First_childやNextを用いて探索したほうが計算量的には少なくすみますが複雑な字であっても20パーツを超えることはないため全探索しています。
cv2.findContoursは背景を0とするので0がchildのものがいちばん外側の線になります。parentが偶数であるものが線の部分なので、偶数のあるインデックスを親にしている要素をカウントします。
最後に文字列を文字ごとに変換し、繋げ、検索のためにこれをソートして返します。

string_topology.py

topology_dic = {}
jpfont = ImageFont.truetype("/System/Library/Fonts/ヒラギノ角ゴシック W4.ttc",500)

def char_topology(char):
    if char in topology_dic:
        return topology_dic[char]
    else:
        img = Image.new("L",(500, 500),"white")
        draw = ImageDraw.Draw(img)
        draw.text((0,0),char,font=jpfont,fill="black")
        img_cv = np.array(img,dtype=np.uint8)
        ret,thresh = cv2.threshold(img_cv,127,255,0)
        contours, hierarchy = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
        img_cv_con = np.zeros((500,500,3),np.uint8)
        cv2.drawContours(img_cv_con,contours,-1,(0,255,0),3)
        parent = [k[3] for k in hierarchy[0]]
        topology = [parent.count(k)
                    for k in range(len(parent)) if parent[k]%2 == 0]
        topology_dic[char] = topology
        return topology

def string_topology(string):
    topology = reduce(lambda x,y:x+y,[char_topology(k) for k in string])
    topology.sort()
    return topology

検索

リストの文字列をトポロジーに変換して一致するものを出力します。

search.py

in_topology = string_topology(sys.argv[1])
print(in_topology)
for k in words:
    if in_topology == string_topology(k):
        print(k)

コード

全部つなげるとこうなります。

same_topology.py

import cv2
import os
from PIL import Image, ImageDraw, ImageFont
import numpy as np
from functools import reduce
import csv
import codecs
import sys

csvs = [
    "Noun.csv",
    "Noun.adjv.csv",
    "Noun.adverbal.csv",
    "Noun.demonst.csv",
    "Noun.nai.csv",
    "Noun.name.csv",
    "Noun.number.csv",
    "Noun.org.csv",
    "Noun.others.csv",
    "Noun.place.csv",
    "Noun.proper.csv",
    "Noun.verbal.csv"
]
filedelimitor = "~/mecab-ipadic-2.7.0-20070801/"
def csv_1(csv_file):
    with codecs.open(filedelimitor+csv_file, "r","euc_jp") as f:
        reader = csv.reader(f)
        csv_words = [k for k in reader]
        csv_words_np = np.array(csv_words)
        return(csv_words_np[:,0].tolist())

words = reduce(lambda x,y:x+y,[csv_1(k) for k in csvs])

topology_dic = {}
jpfont = ImageFont.truetype("/System/Library/Fonts/ヒラギノ角ゴシック W4.ttc",500)

def char_topology(char):
    if char in topology_dic:
        return topology_dic[char]
    else:
        img = Image.new("L",(500, 500),"white")
        draw = ImageDraw.Draw(img)
        draw.text((0,0),char,font=jpfont,fill="black")
        img_cv = np.array(img,dtype=np.uint8)
        ret,thresh = cv2.threshold(img_cv,127,255,0)
        contours, hierarchy = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
        img_cv_con = np.zeros((500,500,3),np.uint8)
        cv2.drawContours(img_cv_con,contours,-1,(0,255,0), 3)
        parent = [k[3] for k in hierarchy[0]]
        topology = [parent.count(k)
                    for k in range(len(parent)) if parent[k]%2 == 0]
        topology_dic[char] = topology
        return topology

def string_topology(string):
    topology = reduce(lambda x,y:x+y,[char_topology(k) for k in string])
    topology.sort()
    return topology



in_topology = string_topology(sys.argv[1])
print(in_topology)
for k in words:
    if in_topology == string_topology(k):
        print(k)

出力結果

$ python topology.py 東京
[0, 0, 0, 1, 4]
焼串
蓮台
尻取り
連枝
抜き取り
和算
美童
用達し
後事
事案
房事
火の車
細み
裏金
留金
巨弾
...

第一引数と位相同型な熟語が出力されます。手元環境では30秒くらいで出力されます。

補足

今回は豆腐文字についての処理を行っていませんが本来すべきです(ipa辞書なら豆腐にならずに出力できると思います...)。
「回」と「ロロ」が位相同型ではないのではないか、という指摘を受けたのですが連続性からみて位相同型のはずです。~~多分。~~(筆者の数学の知識不足だと思うので識者の方はコメントしてくれるとありがたいです)