本稿では、画像処理の一種である輪郭追跡処理アルゴリズムを紹介します。輪郭追跡処理は与えられた画像の中からターゲット画像を背景から分離して抽出するための処理であり、輪郭情報があればターゲット画像の面積（＝画素数）や他の様々な特徴を得ることができます。
はじめに
マシンビジョンシステムなど、画像を取り扱うシステムは、およそ以下のような画像処理プロセスを踏みます。
- 画像データ入力
- フィルタリング（ノイズ除去、強調処理など）などの前処理
- 背景とターゲット画像を識別するための2値化処理
その後、パターン認識をしたり、文字や番号、バーコードを読み取ったり、あるいはターゲット画像の輪郭検出（追跡）など、それぞれのシステムに特化した処理を行って、目的とするアウトプットを行います。
本稿では、2値化と輪郭追跡にフォーカスし、ベタなコードでそれらを実現して、考え方を理解していきます。言語はとっつきやすいpythonを用いていますが、本番モノを造る際にはC/C++やJavaScriptへ移植するか、賢い人が作った市販・無料のライブラリを素直に活用するのが良いでしょう。ここでは理解のし易さを重視しています。また、画像データ入力は、サボるためにOpenCVのライブラリを活用しました。
どんなことをやるのか、全体像を視覚的に掴みましょう。
図１のような画像があって、背景より暗い部分がターゲット画像であり、これを抽出するために輪郭追跡した様子が図２です。 これを行うための処理を見ていきましょう。
画像データ入力とグレースケール化
入力画像データはカラーでもグレースケールでも良いですが、画像データをグレースケールに変換してその輝度情報（256階調）を扱います。
import cv2
im_rgb = cv2.imread("data/Particle.jpg")
print(im_rgb.shape)
# (225, 400, 3)
print(im_rgb.dtype)
im_gray = cv2.cvtColor(im_rgb, cv2.COLOR_BGR2GRAY)
print(im_gray.shape)
# (225, 400)
print(im_gray.dtype)
# uint82値化閾値の算出
画像全体における最頻度輝度値を算出して、それにある係数を乗じることで2値化のための閾値を求めます。その方法の一例として、画像全体の輝度値に関するヒストグラムを作成することで、背景とターゲットを分ける輝度値を決めます。最頻度輝度値が背景輝度値の代表と考え、この90％の輝度値を背景とターゲットを分ける輝度値としました。このやり方は一例であり、利用する画像データの特徴や、目的に応じて試行錯誤して最適な方法を探る必要があります。
この輝度ヒストグラムでは、輝度値160付近の集団が背景画素の輝度でり、そこから左の集団はターゲット画素の輝度値と考えられます。ここでは、最頻度輝度値は163であり、それに90％を乗じて147が得られ、これを2値化閾値としました。
def get_threshold_level(gray_img, ratio):
row_size = gray_img.shape[0]
column_size = gray_img.shape[1]
# 輝度の濃淡レベルは8bit（0-255：256段階）とする
histogram = [0]*256
_threshold_level = 0
# 輝度ヒストグラムの作成
for row in range(row_size):
for column in range(column_size):
histogram[gray_img[row][column]] += 1
# 最頻度輝度値の算出
mode = histogram.index(max(histogram))
_threshold_level = int(mode * 0.01 * ratio + 0.5)
return _threshold_level2値化処理
先の処理で2値化閾値が決まったので、これを境に明るい画素（＝背景）を0、暗い画素（＝ターゲット）として2値化します。
def binarizer(gray_img, threshold):
row_size = gray_img.shape[0]
column_size = gray_img.shape[1]
# 空の二次元配列を作成
bin_img = np.empty((row_size, column_size))
# 輝度値が閾値より暗ければ（小さければ）1に変換、そうでなければ0に変換し2値化する
for row in range(row_size):
for column in range(column_size):
if gray_img[row][column] > threshold:
bin_img[row][column] = 0
else:
bin_img[row][column] = 1
return bin_imgラスタースキャン
ラスタースキャンは、この後に行う輪郭追跡処理を行うためのスタート地点を見つける処理です。画像の左上端から右にスキャンし、下の行へ移って右にスキャンして、最初の1を見つけたらそれを輪郭追跡処理のスタート座標とします。
def raster_scan(bin_img):
_result = False
_start_point_row = 0
_start_point_column = 0
row_size = bin_img.shape[0]
column_size = bin_img.shape[1]
# 最初に1が登場する画素の位置を探して関数から抜ける。位置情報を返す。
for row in range(row_size):
for column in range(column_size):
if bin_img[row][column] == 1:
_start_point_row = row
_start_point_column = column
_result = True
return _result, _start_point_row, _start_point_column輪郭追跡処理
本稿の本丸の処理ですが、コードを見る前にここでの輪郭追跡の仕方を理解しましょう。以下の条件で処理を行います。
- 輪郭追跡は反時計回りで行い、スタート地点に戻ったら輪郭追跡は終了
- 追跡方向が複数ある場合は、より右側を選ぶ。（まっすぐと右側の２つ方向がある場合、右側を選ぶ）
この条件では、先の画像の場合、スタート地点から以下のように追跡して行きます。
これはどのように実現しているのか見ていきましょう。
現在の画素には、どの方向に進んできたかが分かれば、次に進むべき方向を絞ることができます。
例えば、現在の画素には左から右へまっすぐに進んできた場合を考えます。（下図の左上のパターン）この場合、左下と真下には１となる画素が無い（赤枠で示す画素）と断言できます。なぜなら先に示した条件に従えば、もし左下に１があればそちらに進んでいるはずだからです。方向は8パターンありますので、方向コードとして0から７を割り当てています。左から／右方向へ移動してきた場合は、Previous direction＝０（P=0)といて定義しています。そして、P=0なら、Next Directionは、５や６はあり得ず、７か０か１か２か３か４と推定されます。そのため、Pの値が決まれば、Nを探す順序を定義できますので、輪郭追跡を行うための、方向テーブルを作ります。
このように現在の画素を中心として近傍8画素のデータを見て、Previous directionからNext diresitonが分かれば、現在の画素からどちらの座標（ｘ、ｙ）へどう動かせば良いか判断できます。(ソースコード上では、serche_order テーブル）現在の画素の位置から動かす量はｘ方向またはｙ方向に０または１あるいは-1ですね。そしてこれもテーブル化しておけば、すっきり記述できるでしょう。(ソースコード上では、move_x, move_y テーブル）現在の画素の座標が動いていきスタート地点に戻れば輪郭追跡処理は終了です。
search_order = [
[7, 0, 1, 2, 3, 4, 5, 6],
[7, 0, 1, 2, 3, 4, 5, 6],
[1, 2, 3, 4, 5, 6, 7, 0],
[1, 2, 3, 4, 5, 6, 7, 0],
[3, 4, 5, 6, 7, 0, 1, 2],
[3, 4, 5, 6, 7, 0, 1, 2],
[5, 6, 7, 0, 1, 2, 3, 4],
[5, 6, 7, 0, 1, 2, 3, 4]
]
move_x = [1, 1, 0, -1, -1, -1, 0, 1]
move_y = [0, -1, -1, -1, 0, 1, 1, 1]
class Chaincode:
chain_position_x = [0]*image_size_max_x
chain_position_y = [0]*image_size_max_y
chain_position_yx = []
chaincode = [0]*chain_code_data_max
chaincode_length = 0
def making_chain_code(start_y, start_x, initial_direction, chaincode_reg, bin_img):
_current_x = start_x
_current_y = start_y
_first_direction = initial_direction
_around_binary_data = [0]*8
chaincode_reg.chain_position_x[0] = _current_x
chaincode_reg.chain_position_y[0] = _current_y
chaincode_reg.chain_position_yx.append([chaincode_reg.chain_position_y[0],
chaincode_reg.chain_position_x[0]])
while True:
# 注目画素の8近傍画素輝度データを取得
_around_binary_data[0] = bin_img[_current_y][_current_x + 1]
_around_binary_data[1] = bin_img[_current_y - 1][_current_x + 1]
_around_binary_data[2] = bin_img[_current_y - 1][_current_x]
_around_binary_data[3] = bin_img[_current_y - 1][_current_x - 1]
_around_binary_data[4] = bin_img[_current_y][_current_x - 1]
_around_binary_data[5] = bin_img[_current_y + 1][_current_x - 1]
_around_binary_data[6] = bin_img[_current_y + 1][_current_x]
_around_binary_data[7] = bin_img[_current_y + 1][_current_x + 1]
# 次に進むべき画素の位置を探す
for i in range(8):
direction = search_order[_first_direction][i]
if _around_binary_data[direction] == 1:
_current_x = _current_x + move_x[direction]
_current_y = _current_y + move_y[direction]
chaincode_reg.chaincode[chaincode_reg.chaincode_length] = direction
_first_direction = direction
chaincode_reg.chaincode_length += 1
if chaincode_reg.chaincode_length > chain_code_data_max:
return False
chaincode_reg.chain_position_x[chaincode_reg.chaincode_length] = _current_x
chaincode_reg.chain_position_y[chaincode_reg.chaincode_length] = _current_y
chaincode_reg.chain_position_yx.append(
[chaincode_reg.chain_position_y[chaincode_reg.chaincode_length],
chaincode_reg.chain_position_x[chaincode_reg.chaincode_length]])
break
if (_current_x == start_x) and (_current_y == start_y):
break
return True補足
スタート地点では、Previous directionという概念がありませんが、同じ考え方・処理で実行できるよう、画素パターンによって、 Previous directionを与えあげます。そのような処理も記述しています。
initial_direction_table = [0, 3, 2, 3, 1, 3, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4]
def get_initial_direction(start_y, start_x, bin_img):
initial_direction = 0
_current_x = start_x
_current_y = start_y
# 初期方向コードを得るための輝度データを取得
b4 = int(bin_img[_current_y][_current_x])
b3 = int(bin_img[_current_y][_current_x + 1])
b2 = int(bin_img[_current_y + 1][_current_x - 1])
b1 = int(bin_img[_current_y + 1][_current_x])
b0 = int(bin_img[_current_y + 1][_current_x + 1])
if b4 == 0:
initial_direction = 0
return initial_direction
code = (b3 << 3) + (b2 << 2) + (b1 << 1) + b0
initial_direction = initial_direction_table[code]
return initial_direction輪郭の重ね書き
これはデバッグ用機能です。輪郭追跡が想定どおりとなったかをパッと視覚的に確認するための処理です。輪郭追跡処理で得られている座標のリストデータを使って該当箇所を赤色にしているだけです。
def edge_paint(chain_yx, img_rgb):
new_img = copy.copy(img_rgb)
for yx in chain_yx:
new_img[yx[0]][yx[1]] = (0, 0, 255)
return new_imgチェーンコードからの画像パラメータ算出
ここでは、チェーンコードから画素数を計算する方法を紹介します。
下図は、離散グリーンの定理テーブルと呼ばれるもので、チェーンコードデータとテーブルの値を使ってかの式で画素数を求めることができます。
画素数 ＝ Σ（Xi× Dy(Ai-1, Ai) + Cy(Ai-1, Ai)
Xi : 輪郭データのX座標, Ai-1 : Previous direction Code, Ai : Next direction Code
d_table = [
[0, 1, 1, 1, 1, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 0],
[-1, 0, 0, 0, 0, -1, -1, -1],
[-1, 0, 0, 0, 0, -1, -1, -1],
[-1, 0, 0, 0, 0, -1, -1, -1],
[-1, 0, 0, 0, 0, -1, -1, -1]
]
c_table = [
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 1, 1, 1],
[1, 1, 0, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1],
[1, 1, 1, 1, 0, 1, 1, 1]
]
def calculate_image_parameter(chaincode_reg, parameters):
_pixel = 0
x = d = c = 0
# chaincode_reg.chain_position_x[chaincode_reg.chaincode_length] = chaincode_reg.chain_position_x[0]
chaincode_reg.chaincode[chaincode_reg.chaincode_length] = chaincode_reg.chaincode[0]
for i in range(1, chaincode_reg.chaincode_length+1):
x = chaincode_reg.chain_position_x[i]
d = d_table[chaincode_reg.chaincode[i-1]][chaincode_reg.chaincode[i]]
c = c_table[chaincode_reg.chaincode[i-1]][chaincode_reg.chaincode[i]]
_pixel += (x * d + c)
parameters.pixel_count = _pixel今回の例では、画素数は59になります。
輪郭の座標データや画素数情報があれば、他にもターゲット画像にパラメータを得ることができますが、今回はここまでとします。