Kei Minagawa's Blog

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

輪郭抽出

いきなりですが、輪郭抽出を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"という文字を符号としてみているのではなく、画像としてみているー数百ドットではなく数万ドットやそれ以上として認識されているーからだと思います。