TSPアートへの挑戦（その１）

Contents

1 TSPアートへの挑戦（その１）

書籍「マス・アート～真理、美、そして方程式～」のp.118-127で紹介されている作品は人の顔や人の手をTSPを使って描いています。ここでは、標準画像データベースSIDBAのマンドリルの画像を使ってＴSＰアートに挑戦していこうと思います。

TSPアートを描くための手順

まずTSPアートを描くときの手順を考えてみます。それには大きく2つの手順があります。

１．用意した画像からその画像の特徴を表す点の集まりを抽出する

２．点の集まりに対して巡回セールスマン問題を解くことで点同士を結ぶ最短経路を見出し、それを描画する

以下で順にその手順を行っていきます。

点の集まりを抽出する

最初は、用意した画像（今回はマンドリル画像）からその画像の特徴を表す点の集まりを抽出してみます。抽出の流れは以下です。

マンドリル画像を読み込む
読み込んだ画像をグレースケール化する。その後、画像のサイズを調整今回は50×50pixelsまで落とす。
各画素の領域に、その画素値が90未満の場合その領域に2つの点を与え、画素値が130未満の場合その領域に1つの点を与え、画素値が130以上の場合その領域には点を与えないようにして、点の集まりを抽出する。

以上を実行すると、下記のような点の集まりを得ることができました。

巡回セールスマン問題を解く

マンドリル画像から点の集まりを抽出することができたので、あとはこれらの点の集まりに対して巡回セールスマン問題を解くだけです。今回は、「Vignette & Clarity（ビネット＆クラリティ）」というサイトの「8-6. vcoptで巡回セールスマン問題を解く（閉路はどうやるの？編）」にあるプログラムコードを参考に解いてみました。結果は以下の画像です。

考察

とりあえず、マンドリル画像でTSPアートに挑戦してみましたが、あまりうまくいったとは言えないですね。点の集まりの段階ではもう少しマンドリルっぽさが出ていましたが、TSPの結果はマンドリルっぽさがなくなっています。原因は何なんでしょうか。

原因と問題

今回の結果で言えば、マンドリルの眼のあたりはほぼ再現できていないように感じます。また、書籍「マス・アート～真理、美、そして方程式～」に掲載されている作品と見比べても、やはり今回作成したマンドリル画像での結果の方がかなり疎な感じがします。つまり、一番の原因は単純に点数が足りないのではないかと考えています。

今回実行したマンドリル画像からは1557個の点を抽出しています。この場合のTSPの結果による画像は上記のようになりました。点数を増やすことは簡単にできます。ただ、点数が多くなると、今度は巡回セールスマン問題を解くために長い時間が必要になります。実際、10000個の点を抽出して巡回セールスマン問題を解かせようとさせたところ、自分が使っているノートPCでは1日回しても終わる気配が全くありませんでした。つまり、点数を増やすためには、巡回セールスマン問題をもっと速く解くための対策が必要となります。

対策

１．巡回セールスマン問題を解くためのアルゴリズムを見直す

そもそも巡回セールスマン問題は点数が多くなるほど厳密に解くことが難しいそうです。ですので、巡回セールスマン問題は一般的に近似的に解くことが多いようです。その近似手法や近似アルゴリズムは多く提案されてます。そこでこれらの近似手法をきちんと勉強して、扱う問題に適しているもの、適していないものを区別しつつ、試行錯誤していく必要がありそうです。ネットで検索してみると、さまざまな課題に対する巡回セールスマン問題を解こうとしている人たちが多くいて、皆さん試行錯誤されています。そういう人たちの結果を参考にさせていただきつつ、今回のTSPアートに適した手法を調査、検証していきたいと思います。

２．マシンパワーを上げる

現在、使っているノートPCはGPUなど乗っていない普通のPCですので、今後お金に余裕が出てきたらもっと性能のよいPCを買って試してみたいですね。現状、こちらは期待できないので、まずはアルゴリズムを見ていくしかないかな。

プログラムコード

参考までに、今回使ったプログラムコード（Python）を載せておきたいと思います。

import numpy as np
import numpy.random as nr
import matplotlib.pyplot as plt
from vcopt import vcopt
from PIL import Image


#画像の読み込み
img = Image.open('Mandrill.png')
img_gray = img.convert("L")  # グレースケール変換

img_size = 50
img_resize = img_gray.resize((img_size,img_size)) # 縮小

#img_resize.show()

face_points_x = []
face_points_y = []
temp_x = []
temp_y = []

for x in range(img_size):
  for y in range(img_size):
    val= img_resize.getpixel((x,y))
    if val < 90: #画像の暗い部分は点を多く取得する
      temp_x = ( x + nr.rand(2) ) / img_size
      temp_y = ( img_size -1.0 - y + nr.rand(2) )  / img_size
    elif val < 130:
      temp_x = ( x + nr.rand(1) ) / img_size
      temp_y = ( img_size -1.0 - y + nr.rand(1) )  / img_size
    else: #画像の明るい部分は点無し
      temp_x = []
      temp_y = []
    
    face_points_x = np.append(face_points_x, temp_x)
    face_points_y = np.append(face_points_y, temp_y)


#巡回セールスマン問題の評価関数
def tsp_score(para):
    
    #paraの前後に0を付ける（0からスタートし0でゴールする）
    para_full = np.hstack((0, para, 0))
    
    #スコアの計算（今回は直接returnする）
    return np.sum(((face_points_x[para_full][:-1] - face_points_x[para_full][1:])**2 + (face_points_y[para_full][:-1] - face_points_y[para_full][1:])**2)**0.5)


#paraの可視化
def tsp_show_para(para, **info):
    
    #2-opt処理中の諸情報はinfoという辞書に格納されて渡されます
    #これらを受け取って使用することができます
    step_num = info['step_num']
    score = info['score']
    print(step_num)


face_points_num = len(face_points_x)
#適当に道順を作成（ただし0のpointは含まない）
para = np.arange(1, face_points_num)
nr.shuffle(para)

#2-opt法で最適化
para, score = vcopt().opt2(para,                          #para
                           tsp_score,                     #score_func
                           0.0,                           #aim
                           show_para_func=tsp_show_para,  #show_para_func=None
                           seed=1)                        #seed=None

#paraの前後に0を付ける（0からスタートし0でゴールする）
para_full = np.hstack((0, para, 0))

#プロット（および保存）
fig = plt.figure(figsize=(6, 6))
plt.plot(face_points_x[para_full], face_points_y[para_full])
#plt.scatter(face_points_x[para_full], face_points_y[para_full], marker="." ) # 点で描画

plt.xlim([0, 1]); plt.ylim([0, 1])

plt.axis("off")
plt.show()

fig.savefig("Mandrill_TSP.png")