Kei Minagawa's Blog

皆川圭(@keimina)のブログ、Pythonで試したことを書いていきます

抽出した輪郭を間引いてみる

昨日はオブジェクトから輪郭を抽出する処理を書きました。今日は、
輪郭を等間隔に間引いたものの形状がどうなるか見てみます。前処理としてオリジナルデータのオブジェクト領域が小さかったのでscipyのzoom関数で2倍に拡大してから処理に入っています。あと、符号化もしてます。等間隔に間引くだけなら符号化する必要はないかもしれませんが、あとで何かに使えるかもしれないので、符号化してみました。

# -*- coding: utf-8 -*-
import random
import re
import numpy as np
from numpy import arange
import matplotlib.pyplot as plt
from scipy.ndimage import zoom

def rawObjectToMatrix(ro):
    ret = []
    lines = ro.splitlines()
    for line in lines:
        if line.strip()=="":
            continue
        ret.append(map(lambda x: 0 if x == " " else 1, line))
    whiteRow = [[0 for _ in xrange(len(ret[0]))]]
    return whiteRow + ret + whiteRow

def pb(lst2d):
    ret = ""
    for lst in lst2d:
        lst = map(abs, lst)
        ret += "".join(map(str, lst)) + "\n"
    print ""
    print ret

def readMyData():
    with open("a.txt", 'r') as fp:
        text = fp.read()
    objectRawDataList = re.split(r"\n\n", text)
    objectRawDataList = filter(lambda x: x != "", objectRawDataList)
    return map(lambda ro: rawObjectToMatrix(ro), objectRawDataList)

lst = readMyData()

sampleMatrix = zoom(np.array(lst[5]), 1.5)
pb(sampleMatrix)

height = sampleMatrix.shape[0]
width = sampleMatrix.shape[1]

mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, cn] == 1 and mat[rn + 1, cn] == 1:
            mat[rn, cn] = 0

out = mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[(height - 1) - rn, cn] == 1 and mat[(height - 1) - rn - 1, cn] == 1:
            mat[(height - 1) - rn, cn] = 0

out |= mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, cn] == 1 and mat[rn, cn + 1] == 1:
            mat[rn, cn] = 0

out |= mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, (width - 1) - cn] == 1 and mat[rn, (width - 1) - cn - 1] == 1:
            mat[rn, (width - 1) - cn] = 0

out |= mat  
pb(out)

firstPosFlat = out.flatten().argmax()
pos = firstPosFlat / width, firstPosFlat % width
startPos = pos
code = []
while True:
    if   out[pos[0] - 1, pos[1]    ] == 1:
        out[pos[0] - 1, pos[1]    ] = 2
        pos = pos[0] - 1, pos[1]
        code.append((-1, 0))
    elif out[pos[0] - 1, pos[1] + 1] == 1:
        out[pos[0] - 1, pos[1] + 1] = 2
        pos = pos[0] - 1, pos[1] + 1
        code.append((-1, 1))
    elif out[pos[0]    , pos[1] + 1] == 1:
        out[pos[0]    , pos[1] + 1] = 2
        pos = pos[0]    , pos[1] + 1
        code.append((0, 1))
    elif out[pos[0] + 1, pos[1] + 1] == 1:
        out[pos[0] + 1, pos[1] + 1] = 2
        pos = pos[0] + 1, pos[1] + 1
        code.append((1, 1))
    elif out[pos[0] + 1, pos[1]    ] == 1:
        out[pos[0] + 1, pos[1]    ] = 2
        pos = pos[0] + 1, pos[1]    
        code.append((1, 0))
    elif out[pos[0] + 1, pos[1] - 1] == 1:
        out[pos[0] + 1, pos[1] - 1] = 2
        pos = pos[0] + 1, pos[1] - 1
        code.append((1, -1))
    elif out[pos[0]    , pos[1] - 1] == 1:
        out[pos[0]    , pos[1] - 1] = 2
        pos = pos[0]    , pos[1] - 1
        code.append((0, -1))
    elif out[pos[0] - 1, pos[1] - 1] == 1:
        out[pos[0] - 1, pos[1] - 1] = 2
        pos = pos[0] - 1, pos[1] - 1
        code.append((-1, -1))
    if pos == startPos:
        break

pb(out)


mabiki = [1, 2, 4, 8, 16, 32]
for m in mabiki:
    pr = 0
    pc = 0
    p = []
    for n, c in enumerate(code):
        dr, dc = c
        pr += dr
        pc += dc
        if n % m == 0:
            p.append((pr, pc))

    x = map(lambda x: x[1], p)
    y = map(lambda x: x[0], p)
    x += [0]
    y += [0]
    fig, ax = plt.subplots(1)
    ax.plot(x, y)
    fig.savefig("/Users/kei/Desktop/mabiki%d.png"%m)

出力(上から順に、オリジナル, 2, 4, 8, 16, 32ステップごとにサンプルをとった場合の集合):
f:id:keimina:20160529120729p:plain
f:id:keimina:20160529120727p:plain
f:id:keimina:20160529120724p:plain
f:id:keimina:20160529120721p:plain
f:id:keimina:20160529120718p:plain
f:id:keimina:20160529120715p:plain

輪郭抽出

いきなりですが、輪郭抽出をPythonで実装しました。
ここでいう輪郭抽出とは画像にフィルタを適用する話ではありません。二値画像のオブジェクトの輪郭を綺麗に抽出したいのです。

すでに、このアルゴリズムがあるかは知りませんが、アルゴリズムのイメージだけ説明すると、上下左右の4方向から光をてらして光が当たる部分だけ取り出すという感じです。実際にはひたすら「連続する(1,1)を消していく」を4方向分行うだけです。

境界値処理は行っていません。以下のように入力データを加工したので、境界値の問題は発生しませんでした。

00000 < はじめと終わりの行データが非オブジェクト(0)である
00100 < 左端と右端の列データが非オブジェクト(0)である
01110
00100
00000

以下に、冗長だがよみやすいソースコードを記載していることを望みます。

# -*- coding: utf-8 -*-
import random
import re
import numpy as np
from numpy import arange

def rawObjectToMatrix(ro):
    ret = []
    lines = ro.splitlines()
    for line in lines:
        if line.strip()=="":
            continue
        ret.append(map(lambda x: 0 if x == " " else 1, line))
    whiteRow = [[0 for _ in xrange(len(ret[0]))]]
    return whiteRow + ret + whiteRow

def pb(lst2d):
    ret = ""
    for lst in lst2d:
        lst = map(abs, lst)
        ret += "".join(map(str, lst)) + "\n"
    print ""
    print ret

def readMyData():
    with open("a.txt", 'r') as fp:
        text = fp.read()
    objectRawDataList = re.split(r"\n\n", text)
    objectRawDataList = filter(lambda x: x != "", objectRawDataList)
    return map(lambda ro: rawObjectToMatrix(ro), objectRawDataList)

lst = readMyData()

sampleMatrix = np.array(lst[5])
pb(sampleMatrix)

height = sampleMatrix.shape[0]
width = sampleMatrix.shape[1]

mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, cn] == 1 and mat[rn + 1, cn] == 1:
            mat[rn, cn] = 0

out = mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[(height - 1) - rn, cn] == 1 and mat[(height - 1) - rn - 1, cn] == 1:
            mat[(height - 1) - rn, cn] = 0

out |= mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, cn] == 1 and mat[rn, cn + 1] == 1:
            mat[rn, cn] = 0

out |= mat
mat = sampleMatrix.copy()
for rn, _ in enumerate(mat):
    for cn, __ in enumerate(_):
        if mat[rn, (width - 1) - cn] == 1 and mat[rn, (width - 1) - cn - 1] == 1:
            mat[rn, (width - 1) - cn] = 0

out |= mat  
pb(out)

a.txtのデータはこちらになります。

   @@            
   @@@@          
   @@@@@@        
   @@@@@@@       
     @@@@@@      
       @@@@@@    
         @@@@    



            @@@@@@@ 
      @@@@@@@@@@@@  
   @@@@@@@@@@@@     
  @@@@@@@@@@@@      
  @@@@@@@           
  @@@@@             
  @@@               



                              
                    @@@@@@@@  
               @@@@@@@@@@@@@  
             @@@@@@@@@@@@@@@  
          @@@@@@@@@@@@@@@     
        @@@@@@@@@@@@@@@@      
      @@@@@@@@@@@@@@@         
    @@@@@@@@@@@@@@            
    @@@@@@@@@@@               
     @@@@@                    



                           @@@@       
                           @@@@@@@    
                            @@@@@@@   
                            @@@@@@@@  
                            @@@@@@@@  
                           @@@@@@@@@  
                           @@@@@@@@@  
  @@@@@                    @@@@@@@@@  
 @@@@@@@@                 @@@@@@@@@@  
 @@@@@@@@               @@@@@@@@@@@@  
 @@@@@@@@             @@@@@@@@@@@@@@  
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@    
 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@     
  @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@      
   @@@@@@@@@@@@@@@@@@@@@@@@@@@@       
      @@@@@@@@@@@@@@@@@@@@@@@         
            @@@@@@@@@@@@@@@@          



                                      @@@@@@@@@    
                                  @@@@@@@@@@@@@@@  
                              @@@@@@@@@@@@@@@@@@@  
                           @@@@@@@@@@@@@@@@@@@@@@  
                        @@@@@@@@@@@@@@@@@@@@@@@@@  
                      @@@@@@@@@@@@@@@@@@@@@@@@@@   
                    @@@@@@@@@@@@@@@@@@@@@@@@@@     
                  @@@@@@@@@@@@@@@@@@@@@@@@@@@      
               @@@@@@@@@@@@@@@@@@@@@@@@@@@@        
             @@@@@@@@@@@@@@@@@@@@@@@@@@@@          
           @@@@@@@@@@@@@@@@@@@@@@@@@@@             
          @@@@@@@@@@@@@@@@@@@@@@@@@                
         @@@@@@@@@@@@@@@@@@@@@@@                   
         @@@@@@@@@@@@@@@@@@@@@                     
          @@@@@@@@@@@@@@@@                         
           @@@@@@@@@@@                             




                                @@@@@@@@@              
                            @@@@@@@@@@@@@@@@           
                         @@@@@@@@@@@@@@@@@@@@@@        
                       @@@@@@@@@@@      @@@@@@@@@      
                     @@@@@@@@@            @@@@@@@@     
                     @@@@                    @@@@@     
                                             @@@@@@    
                                             @@@@@@    
                                             @@@@@@    
                   @@                       @@@@@@@    
                  @@@@                     @@@@@@@     
                  @@@@@@                  @@@@@@@@     
                   @@@@@@@@          @@@@@@@@@@@@      
                     @@@@@@@@@@@@@@@@@@@@@@@@@@@       
                        @@@@@@@@@@@@@@@@@@@@@@         
                             @@@@@@ @@@@@@@            

実行結果

0000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000011111111100000000000000
0000000000000000000000000000111111111111111100000000000
0000000000000000000000000111111111111111111111100000000
0000000000000000000000011111111111000000111111111000000
0000000000000000000001111111110000000000001111111100000
0000000000000000000001111000000000000000000001111100000
0000000000000000000000000000000000000000000001111110000
0000000000000000000000000000000000000000000001111110000
0000000000000000000000000000000000000000000001111110000
0000000000000000000110000000000000000000000011111110000
0000000000000000001111000000000000000000000111111100000
0000000000000000001111110000000000000000001111111100000
0000000000000000000111111110000000000111111111111000000
0000000000000000000001111111111111111111111111110000000
0000000000000000000000001111111111111111111111000000000
0000000000000000000000000000011111101111111000000000000
0000000000000000000000000000000000000000000000000000000


0000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000011111111100000000000000
0000000000000000000000000000111100000000011100000000000
0000000000000000000000000111000000111111000011100000000
0000000000000000000000011000001111000000110000011000000
0000000000000000000001100111110000000000001110000100000
0000000000000000000001111000000000000000000001000100000
0000000000000000000000000000000000000000000001000010000
0000000000000000000000000000000000000000000001000010000
0000000000000000000000000000000000000000000001000010000
0000000000000000000110000000000000000000000010000010000
0000000000000000001001000000000000000000000100000100000
0000000000000000001000110000000000000000001000000100000
0000000000000000000110001110000000000111110000001000000
0000000000000000000001110001111111111000000000110000000
0000000000000000000000001111100000010000000111000000000
0000000000000000000000000000011111101111111000000000000
0000000000000000000000000000000000000000000000000000000

これを見ると、ガタガタじゃないかと思われるが、人間の目には"1"の領域の輪郭がしっかり把握できるのは、"1"という文字を符号としてみているのではなく、画像としてみているー数百ドットではなく数万ドットやそれ以上として認識されているーからだと思います。

備忘録、Raspberry Piにシリアル接続する方法

1年くらいに購入したラズベリーパイMacでシリアル接続してみた。
結果、Arduino書き込みのために購入した、USB-シリアル変換ケーブルでシリアル接続できた。
配線は以下のとおり。

f:id:keimina:20160514174754j:plain
※ラズパイが3.3VなのでUSB-シリアル変換ケーブルも3.3Vに合わせる。

この状態で以下のコマンドを実行。
f:id:keimina:20160514184643p:plain

idとパスワードを入力
f:id:keimina:20160514184640p:plain

以上。

再帰を走らせた時の道筋

再帰を走らせた時の道筋が知りたくなったため、考察してみました。
具体的には、以下のPythonコードで表される再帰を考えます。

# -*- coding: utf-8 -*-
def recShow(n):
    if n == 5:
        return
    else:
        recShow(n + 1)
        recShow(n + 1)

recShow(1)

これが、どのような道筋をたどるのかを知りたかったため、
試行錯誤し、以下のようにしてみました。

# -*- coding: utf-8 -*-
def recShow(n, lst):
    if n == 5:
        lst.append("ret")
        return
    else:
        newlst = lst[:]
        newlst.append("a%d"%n)
        recShow(n + 1, newlst)
        newlst.append("b%d"%n)
        recShow(n + 1, newlst)
        print newlst
        
print ""
lst = []
recShow(1, lst)

出力は以下のようになります。

['a1', 'a2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'a3', 'b3']
['a1', 'a2', 'b2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'b2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'a2', 'b2', 'a3', 'b3']
['a1', 'a2', 'b2']
['a1', 'b1', 'a2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'a3', 'b3']
['a1', 'b1', 'a2', 'b2', 'a3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'b2', 'a3', 'b3', 'a4', 'ret', 'b4', 'ret']
['a1', 'b1', 'a2', 'b2', 'a3', 'b3']
['a1', 'b1', 'a2', 'b2']
['a1', 'b1']

最深層まで行ったら戻って、また行けるところまでいくというようなイメージはつかめました。
あと、aの次はb、そのbの次はa、というような、グローバルな視点で眺めるとaとbを行き交うことがわかりました。

絶対解けるマインスイーパのようなパズル「宝探し」の6x6の問題を作成した

表題の通り、「宝探し」の6x6をつくりました。頭の体操にどうぞ。

      2    
  2        
  4     2  
    2 3    
  4 2 3   3
  2     2 1
2 3       2
           
3     3 1  
2 3        
  3 2 1    
2     1    
    2      
2          
        2  
3   3   3 2
2 3   3   1
1     2    
    1 1 2  
    1 2    
2   3     2
  2     2  
           
2   3   2  
  2        
2   3 3 2  
  3     3  
  4     2  
2   2      
1   2      
      2    
      3    
2     2    
  3 3 4   2
  3 2      
  2   3 2  
    2 2    
    4   4  
    4      
2 2 3 4 4  
    2      
  2 2      
    2 3   3
3 4 4      
        3 2
2         2
  2        
2         2
    1 1    
2 3        
      2 3 3
4   5 5    
          3
2     4    
  2 2      
      4   2
3       3  
2     2    
2         1
1 1       1
2 2     2  
      3   3
          3
  2   4    
  3        
1 2   3 2  
2         2
3     2 3  
2          
2 4        
          2
2   2 2   2
  2       2
  2   3   3
3   2 3   3
      4 3  
        3  
      2    
    2 2   2
  2 2   3  
2 3        
1          
1 2   2    
    1      
    2 2   3
2     4    
  2       2
    4 4 3 2
      2    
  2        
1 2 2     2
  4        
    3   4 3
    4   3  
2   3      
2          
  2 2 2    
3          
  2   2   1
    1 2    
2   1 2    
      2    
        2 2
    2 4    
           
1 2     2  
1 2 2 3   2
1          
    2     2
    3 3   2
      3   2
           
  2 2     1
1 1 2      
1   2      
        2  
  4 2 3    
2   2 4    
2 4       2
1          
2 2   2   2
          4
           
  2 3 3 4  
1       2  
  1   3    
    2   2 1
           
      4 3  
        3  
  2       2
1 2 2 3 2  

必ず解けるマインスイーパのようなパズル「宝探し」の5x5の問題

絶対解けるマインスイーパのようなパズル「宝探し」の5x5の問題です。暇つぶしにどうぞ。

      1 1
        2
      3  
1   1    
  2      
         
1 2 2 2  
1 1 3    
         
         
  1   2 2
    3    
      2  
    1 1  
         
    1    
    2    
1   3 2  
  2      
1        
    1 1  
    2    
    2 3 2
  2      
         
    1   1
      2  
         
    1   1
      1 1
1 2 1    
      1  
         
      1  
      1 1
         
    1 1  
1 1 3   3
1        
         
1        
         
2     1  
         
2 3 2 2  
         
        1
      2 1
    1 2 2
1        
1   2    
2     1  
  1      
1 2      
         
    1 2 2
         
         
  1   1  
1   2    
    1    
2        
  1 2    
1        
  2 3    
         
         
1     1  
1 2      
  1 2    
        1
         
    1 3  
1   2    
    2 1  

必ず解けるマインスイーパのようなパズル「宝探し」の4x4の問題ができた

「宝探し」パズルの4x4ができたので問題提供します(10問)。みなさんとけますか。ルールは「マスの数字の周りにその数字の数だけ宝がある、宝のある場所を◯で埋めなさい」です。言いかえると絶対解けるマインスイーパです。それだけですが、以外に面白いと思います。ただし、2,3手先読めば解ける問題もそれ以上先読みが必要な問題もあるのでやさしくはないかもしれません。

1   1  
  2   2
2   2  
    2  
       
1 2 2  
2     2
2     2
    1 1
2   3  
  2    
  2 2  
  1    
2     1
1      
1 2   2
    1 1
      2
1 3    
1   2  
  1    
2 2 2  
2   2  
    1  
    1 1
      2
  2    
1 1 1  
    1 1
    2  
1   2  
  1   1
1   2  
2   4  
    2  
1 1    
1      
2     1
  3   2
  2   1