PythonによるAIプログラミング入門 ―ディープラーニングを始める前に身につけておくべき15の基礎技術

付録A退屈なことはPythonにやらせよう —— 4色問題篇

相川 愛三

本付録は日本語版オリジナルの記事です。

「7章 ヒューリスティック探索」では、制約充足問題（CSP）の例として4色問題を解いて、地図を塗り分けました。しかしながら、例題の地図から領域の隣接関係を調べるのはとても面倒です。実際に、原書には隣接関係の洗い出しに間違いがありました。

そこで本稿では、画像処理を応用して自動的に隣接関係を調べ、さらにCSPを解いて地図を塗り分けてみます。

例として図A-1の白地図map.pngを対象にします。次のコードを入力して、画像を読み込んで表示します。

%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
import cv2

org_image = cv2.imread('map.png')
plt.imshow(org_image)
plt.show()

図A-1　　

A.1　領域の番号付け

まず、線によって分割される各領域に識別番号を付けます。

OpenCVには、cv2.findContours()という領域の輪郭抽出をする便利な関数があります。しかしながら、境界線が細いと領域をうまく分離できないことがあるため、まず境界線を太くします。

境界線を太くするには、各領域を縮める処理をします。グレースケールに変換してから、モルフォロジー処理のcv2.erode()を用います。ここでは3×3のカーネルを用いて領域を縮めています。 ...