こんにちは、エンジニアのさもです。

今回は、以前投稿したpythonによる画像処理入門の続編になります。

はじめに
k平均法とは
- ざっくりとした説明
- ざっくりとしたアルゴリズムの説明
実装
実行
よりよくするために
- フィルタリング
- 処理の終了するタイミング
最後に

はじめに

今回はk平均法というアルゴリズムを使って、画像の減色処理を実装してみたいと思います。

以下の画像を使っていきます。

f:id:s-uotani-zetakansu:20170827233653j:plain

こちらを減色処理すると以下のようになります。

f:id:s-uotani-zetakansu:20170827233754j:plain

油絵っぽい感じですかね。

k平均法とは

k平均法とは、教師なしクラスタリングの一つです。

ざっくりとした説明

クラスタリング

クラスタリングというのは、データの集合をいくつかのクラスへ分類するアルゴリズムです。

今回の実装では、画像の各画素のリストを入力データとして、それらをk個のクラス（k色）に分類することで、画像をk色だけで表現します。

教師なし

私も勉強中なので厳密な定義は他の書籍などにお任せしますが、イメージとしては、

教師なしというのは、自分で書いた読書感想文を、自分で校閲し、書き直すアルゴリズムで、

対する教師ありというのは、問題集で問題を解き、答え合わせをし、それをフィードバックする。というアルゴリズムだと思っています。

ざっくりとしたアルゴリズムの説明

ざっくりとk平均法のアルゴリズムを説明します。

まず、仮のクラスとして、ランダムな値をもつk個のクラスを用意しておきます。
画像内の全ての画素を順に見ていき、一番近い値を持つクラスを見つけておきます。
クラスに属している画素の平均の値を求め、その値でクラスの値を置き換えます。これを全てのクラスについて行います。
１～３を何度も繰り返しているうちに、クラス分けが変化しなくなります。そこで処理を終了します。

実装

実装の準備

必要なライブラリや、画像処理の基本的な処理の詳細は pythonによる画像処理入門 - ブンバボーンな毎日をご参照いただければと思います。

Anacondaを使っている場合は、主な作業はpillow(PIL:PythonImageLibraly)のインストールのみです。

その他、加工してみたい画像を用意しておきましょう。

外枠を実装する

kmeanの実装は長くなってしまうので、一旦外枠だけ作っておきたいと思います。

以下のようにkmean.pyを作成してください。ファイル名は適宜置き換えてください

from PIL import Image, ImageDraw
import numpy as np
from numpy.random import randint

# k平均法による減色処理
def k_mean(original_img, k):
  return original_img

# 画像ファイルの読み込み
filename = "hu.jpg"
img = Image.open("./" + filename).convert("RGB")

# k平均法による減色処理
reduce_img = k_mean(img, 5)

# 画像データの更新とファイル出力
reduce_img.save("./reduce_" + filename)

一旦この段階で動作確認をします。コンソールに以下のコマンドを打ち込んで実行します

python kmean.py

reduce_元画像のファイル名の画像ファイルが作成されれば成功です。

作成された画像は元画像と同じになっています。

解説

まだこの段階では入力された画像をそのまま返すだけです。

この後、kmeanメソッドを実装していきます。

kmeanメソッドは、引数に元画像と、分類するクラスの数を渡します。

kmeanメソッドの返り値は減色処理を施された画像そのものです。画像を入力して画像が返ってくる、というインターフェースにしたいと思います。

randintはランダムな整数値を返すメソッドですが、この段階では使っていません。kmeanを実装していくときに使います。

kmeanメソッドを実装する

以下がk_meanメソッドの中身になります。

# k平均法による減色処理
def k_mean(original_img, k):
  #STEP1
  w, h = original_img.size

  # 画像を扱いやすい２次配列に変換
  img_pixels = np.array([[img.getpixel((x,y)) for x in range(w)] for y in range(h)])
  # 減色画像用の２次配列も用意しておく
  reduce_img_pixels = np.array([[(0, 0, 0) for x in range(w)] for y in range(h)])

  # 代表色の初期値をランダムに設定
  class_values = []
  for i in range(k):
    class_values.append(np.array([randint(256), randint(256), randint(256)]))

  #STEP2
  # 20回繰り返す
  for i in range(20):
    #STEP2-1
    print("ranning at iteration No." + str(i))
    sums = []
    for i in range(k):
      sums.append(np.array([0, 0, 0])) 
    sums_count = [0] * k

    #STEP2-2
    # 各画素のクラスを計算
    for x in range(w):
      for y in range(h):
        min_d = (256 ** 2) * 3
        class_index = 0
        # 一番近い色（クラス）を探索
        for j in range(k):
          d = sum([x*x for x in img_pixels[y][x] - class_values[j]])
          if min_d > d:
            min_d = d
            class_index = j
        sums[class_index] += img_pixels[y][x]
        sums_count[class_index] += 1
        reduce_img_pixels[y][x] = tuple(list(map(int, class_values[class_index])))

    #STEP2-3
    # 代表色を更新
    for m in range(k):
      class_values[m] = sums[m] / sums_count[m]

  # STEP3
  # ２次元配列から加工後の画像へ変換
  reduce_img = Image.new('RGB', (w, h))
  for x in range(w):
    for y in range(h):
      reduce_img.putpixel((x, y), tuple(reduce_img_pixels[y][x]))

  return reduce_img

解説

とりあえず実行したいという方は実行へお進みください。

まず、変数について説明しておきます。

w, h
- 元画像のサイズです。wが横幅、hが縦幅です
img_pixels
- 元画像を２次元配列（実際は３次元になる）へ変換しています。
- ちょうど画像の画素の位置と二次配列での位置が同じになっています。
- 二次配列の各要素は１つの画素値（RGB）になっていますが、画素値はRGBの配列になっているので、実際は３次元配列です。
- [10,124,1]のような配列が二次元的に並んでいます。
reduce_img_pixels
- 加工後の画素値を入れていく二次配列です。最後、この二次配列から画像を生成して返します
class_values
- 代表色の配列です。k個の代表色のリストです。
sums
- 平均を求めるための変数です。
- sumsは配列になっていて、要素は、各代表色に対応しています。
- 要素は、ある代表色に属している画素値の合計になっています。
sums_count
- こちらも平均を求めるための変数です。
- sums_countも配列になっていて、要素は、各代表色に対応しています。
- 要素は、ある代表色に属している画素の個数になります。
- sumsをsums_countで割ることで、平均が求められます。
reduce_img
- メソッドの返り値です。
- reduce_img_pixelsから作られます。

次に、ざっくりと処理の流れを見ていきます。

STEP1.
- まず画像のサイズ、画素の二次配列、クラスのリストなど、処理に必要な変数の初期化を行います。
- class_valuesの値をランダムに設定しています。ランダムでもうまくいくところがk平均法のいいところなのですが、実行毎に出力される結果が変わってしまいます。
STEP2.
- メインで計算を行うステップです。この中身をもう少し詳しく見ていきます。
- 本当は、クラス分けが完了するまで処理を続けるのですが、そうするとめちゃめちゃ時間がかかってしまうので、20回で終わらせておきます。
STEP2-1.
- 変数の初期化です。処理時間が長いので、今何回目の処理なのか表示するようにしています。
STEP2-2.
- 元画像のすべての画素について、一番近いクラスを見つけます。
- 見つけたら、sumsへ画素値を足しておき、sums_countを一つ増やしておきます。
- 最後にreduce_img_pixelsの画素値を一番近いクラスの値で置き換えます。
- 画素の近い遠いというのは、RGBをXYZ空間と見たときのいわゆる普通の距離です。
- 空間内で点と点を結んだ線の長さ（の２乗）になります
STEP2-3.
- 元画像全てに対してクラス分けしたところで、クラスに属している画素値の平均を求め、その平均値をクラスの新しい値として更新します。
- あるクラスに属している画素値の合計はSTEP2-2でsums_countへ蓄積されています。
STEP3
- 画像のインスタンスを新しく作成し、reduce_img_pixelsを元に画像を作成します。
- 画像の一つ一つの画素をputpixcelメソッドで置いていく感じです。

実行

k_meanメソッドが実装できたので、動かしてみます。

コマンドは先ほどと同じです。

python kmean.py

結構時間がかかります。

コンソールに

ranning at iteration No.0
ranning at iteration No.1

と表示されるので、眺めながら待ちます。

しばらくすると処理がとまり、reduce_元画像ファイル名というファイルが出来上がります。

よりよくするために

処理結果をよりよくするちょっとした工夫を紹介したいと思います。

フィルタリング

画像にノイズがあたくさんある場合には、そのノイズの色に引っ張られてうまくいかなくなります。

そんなときに、画像をぼかすように平滑化処理を行います。

以下に平滑化フィルタの一つである平均化フィルタの実装例を書いておきます。

平均化フィルタを簡単に説明すると、注目している画素値を、注目している画素値とその周りにある画素値の平均で置き換えるフィルタです。

こちらも入力・出力が画像なので、次のメソッドを書いておき、k_meanメソッドを呼ぶときに、k_mean(mean_filter(img, 1), 5)としてください

# 平均化フィルタをかけた画像を返す
def mean_filter(img, filter_size):
  w, h = img.size
  image_pixcels = np.array([[img.getpixel((x,y)) for x in range(w)] for y in range(h)])
  filtered_img = Image.new('RGB', (w, h))
  for x in range(w):
    for y in range(h):
      x1 = max(0, x - filter_size)
      x2 = min(x + filter_size, w -1)
      y1 = max(0, y - filter_size)
      y2 = min(y + filter_size, h - 1)
      x_size = x2 - x1 + 1
      y_size = y2 - y1 + 1
      mean_r, mean_g, mean_b = image_pixcels[y1:y2 + 1, x1:x2 + 1].reshape(x_size * y_size, 3).mean(axis = 0)
      filtered_img.putpixel((x,y), (int(mean_r), int(mean_g), int(mean_b)))
  return filtered_img

上記の例では3×3のサイズのフィルターを利用しています。

filter_size * 2 + 1がフィルタの横・縦幅になるので、 filter_sizeを2にすると5×5のサイズのフィルターになります。

大きなサイズのフィルターを利用すれば、ノイズの影響は小さくなります。

処理の終了するタイミング

今回の実装では、とりあえずクラス分けを20回繰り返したら処理を終わる、というようにしていました。

ですが、これでは、十分にクラス分けができていないまま終わってしまう。クラス分けが完了しているのに、無駄な処理を続けてしまう。という問題があります。

そこで、変化量を見比べて、ある値よりも小さくなったら処理を終了するというようにします。

例えば、STEP2-2の中で計算されるmin_dの合計を計算しておき、前回のクラス分けの時の合計との差が、今回の合計の0.1%未満になったら処理を終了する。などとします。

最後に

最後までお読みいただきありがとうございました。

前回の画像処理の入門の応用として減色処理を実装してみました。

これが何に応用できるかはまだ分かっていませんが（笑）

今後もこのシリーズは続けていくので楽しみにしていてください。

webエンジニアの日常

RubyやPython, JSなど、IT関連の記事を書いています

pythonによる画像処理入門part2 k平均法による減色処理