webエンジニアさもの挑戦

RubyやPython, JavaScriptなど勉強したことなど、IT関連の記事を書いています

ビットコイン取引高日本一の仮想通貨取引所 coincheck bitcoin

python画像処理入門7 繰り返し部分の高速化

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

こんにちは、エンジニアのさもです。ブンバボーンしてますか?

画像処理第7回目は少し画像処理から離れてアルゴリズムのお話です。

今までの実装を見直し、ボトルネックになっていた2重のfor文を何とか高速化したいと思います。

目次

はじめに

これまでの画像処理の実装では、1ピクセル一つ一つに対して処理を行ってきました。この場合、2重のfor文を使っていたのですごく時間がかかっていました。

そこで、この2重for文を解消し高速化する方法を2種類紹介したいと思います。(※jitは使わないです)

実装例では、平滑化フィルタを対象に高速化します。

1つ目の方法は、im2colというメソッドを使って、フィルタをかける処理をドット積で一気に計算します。

2つ目の方法は、私が考えた方法で、少しずらした画像をフィルタの大きさ分重ね合わせることで、フィルタをかけたときと同じ計算がされるようにします。

スポンサーリンク

遅いソースコード

これまで使ってきた平滑化フィルタです。

ざっくり説明すると、画像のピクセル一つ一つを走査するようにループをまわし、1ピクセルごとに8近傍との平均をとります

from PIL import Image, ImageDraw
import numpy as np

#平均化フィルタをかけた画像を返す
def mean_filter(img, filter_size):
  w, h = img.size
  filter_size = (filter_size - 1) // 2
  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


# 画像ファイルの読み込み
img = Image.open("../images/hu.jpg").convert("RGB")
# 平滑化フィルタにかけて保存する
mean_filter(img, 3).save("./faster0_hu.jpg")

今回は高速化ということで、for文以外で高速化できるところも直していきます。

上記のコードを以下のように修正しました。

インターフェースは同じなのでメソッドのみ書いておきます

def mean_filter2(img, filter_size):
  w, h = img.size
  filter_size = (filter_size - 1) // 2
  image_pixcels = np.array(list(img.getdata())).reshape(h, w, 3)
  filtered_pixcels = np.zeros((h, w, 3))
  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
      filtered_pixcels[y][x] = image_pixcels[y1:y2 + 1, x1:x2 + 1].reshape(x_size * y_size, 3).mean(axis = 0)
  filtered_img = Image.new('RGB', (w, h))
  filtered_pixcels = np.array(list(map(int, filtered_pixcels.reshape(w * h * 3))))
  filtered_img.putdata(list(map(tuple, filtered_pixcels.reshape(w * h, 3))))
  return filtered_img

修正したところは、

  • 4行目
    • 画像オブジェクトから画素の配列を取るところを、getdataメソッドを使っています
    • getdataメソッドの出力は画素が1直線に並んでいる形なので、reshapeしています
  • 14行目
    • ループで毎回putpixelsするのをやめて、配列にフィルタをかけた後の画素を蓄積しています
  • 17行目
    • putdataメソッドで画像を一気に画像オブジェクトへはめ込んでいます
    • 16行目で値をint型に直しています

要するに、遅いgetpixel,putpixelをやめて、高速なgetdata, putdataを使うようにしました。

getdata, putdataに限りませんが、一括で操作してくれるメソッドの方がはるかに速度が速いです。

上記の修正で、640×360サイズの画像なら平均0.6秒早くなりました!

高速化前が4.2秒程度で、高速化後が3.6秒程度でした

imscolを使った方法

im2colメソッドとは

im2colは画素の配列をフィルタをかけやすい配列へ変換するメソッドです。

頑張ってソースコードを解説しようとしたのですが、力及びませんでした。

代わりにこちらの解説をお読みください。

ソースコードは、下記の書籍にて公開されているソースコードからお借りしました。

以下、im2colとその逆の操作を行うcol2imメソッドです。

import numpy as np
def im2col(input_data, filter_h, filter_w, stride=1, pad=0):
  N, C, H, W = input_data.shape
  out_h = (H + 2*pad - filter_h)//stride + 1
  out_w = (W + 2*pad - filter_w)//stride + 1

  img = np.pad(input_data, [(0,0), (0,0), (pad, pad), (pad, pad)], 'constant')
  col = np.zeros((N, C, filter_h, filter_w, out_h, out_w))

  for y in range(filter_h):
      y_max = y + stride*out_h
      for x in range(filter_w):
          x_max = x + stride*out_w
          col[:, :, y, x, :, :] = img[:, :, y:y_max:stride, x:x_max:stride]
  col = col.transpose(0, 4, 5, 1, 2, 3).reshape(N*out_h*out_w, -1)
  return col

def col2im(col, input_shape, filter_h, filter_w, stride=1, pad=0):
    N, C, H, W = input_shape
    out_h = (H + 2*pad - filter_h)//stride + 1
    out_w = (W + 2*pad - filter_w)//stride + 1
    col = col.reshape(N, out_h, out_w, C, filter_h, filter_w).transpose(0, 3, 4, 5, 1, 2)

    img = np.zeros((N, C, H + 2*pad + stride - 1, W + 2*pad + stride - 1))
    for y in range(filter_h):
        y_max = y + stride*out_h
        for x in range(filter_w):
            x_max = x + stride*out_w
            img[:, :, y:y_max:stride, x:x_max:stride] = col[:, :, y, x, :, :]

    return img[:, :, pad:H + pad, pad:W + pad]

im2colを使った実装

上記2つのメソッドをutil.pyというファイルを作って保存しておきます。

im2colを使った実装は以下のようになりました。

こちらもインターフェースは変わっていないので、メソッドのみ書きます

from PIL import Image, ImageDraw
import numpy as np
# im2col,col2imのインポート
from utils import im2col, col2im

def mean_filter(img, filter_size):
  w, h = img.size
  pad_size = (filter_size - 1) // 2

  # im2colメソッドに渡すため、(1, 3, h, w)という形にしておく
  image_pixcels = np.array([list(img.getdata())]).reshape(1, h, w, 3).transpose(0, 3, 1, 2)
  # im2colで変換する
  col = im2col(image_pixcels, filter_size, filter_size, stride=1, pad=pad_size)

  # フィルタの定義
  # 3×3なら[1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 1/9]みたいになる
  filter = np.zeros((filter_size ** 2, 1)) + (1 / filter_size ** 2)

  # フィルタと変換後の画素配列とのドット積
  # これでフィルタをかけたことになる
  out = np.dot(col.reshape(-1, filter_size ** 2), filter).reshape(w * h, -1)

  # col2imで元の大きさに戻す
  filtered_pixels = col2im(out, image_pixcels.shape, 1, 1).transpose(0, 2, 3, 1)[0]

  # 値を整数にする
  new_pixels = np.array(list(map(int, filtered_pixels.reshape(w * h * 3, 1))))
  new_pixels = new_pixels.reshape(w * h, 3)

  filtered_img = Image.new('RGB', (w, h))
  filtered_img.putdata(list(map(tuple, new_pixels)))
  return filtered_img

ざっくりと説明すると、「im2colで変換して、フィルタとのドット積を行い、col2imで元の形に戻す」です。

処理速度を計測すると0.7秒でした!

フィルタの大きさを3から7にすると、実行速度は0.98秒くらいです。

オリジナルのアルゴリズム

もう存在するかもしれませんが、自分で考えてみたアルゴリズムです。

といっても、変わったことをしているわけではありません。

どんなアルゴリズム

まず簡単のために以下のような3×3の画像へフィルタをかけたいと思います。

f:id:s-uotani-zetakansu:20170907005149p:plain

フィルタをかける際は、まず0パディングします。

f:id:s-uotani-zetakansu:20170908122655p:plain

0パディングとは、画像の周りに値が0の画素を追加することです。

なぜこんなことをするかというと、

例えば、元の画像の(0,0)の位置とその周辺との平均を取ろうとしたとき、(-1, 0)や(-1,-1)など存在しない画素を取得できないからです。

0パディングした元画像の、(0, 0)の位置にある画素を平滑化フィルタにかけるというのは、以下の画像のようなイメージです

f:id:s-uotani-zetakansu:20170908124334p:plain

この操作を全ての画素に順番に行ったのが、始めに紹介した平滑化フィルタです。

私が考えたアルゴリズムは、この操作を一気に全ての画素に対して行う方法です。

そのために、まず、次のような9個の画素の配列を考えます。

f:id:s-uotani-zetakansu:20170907005141p:plain

真ん中は元画像に0パディングした配列ですが、その他は、少しずつずらせています。

次に、全ての配列に1/9をかけて重ね合わせ(足し合わせる)ます。

するとどうでしょう。

例えば、足し合わせた後の(1,1)の位置の値に注目してみます。

この値は、元の画像に0パディングした画像の配列の(1,1)の位置へ平滑化フィルタをかけた値と同じになっています。

f:id:s-uotani-zetakansu:20170908135506p:plain

全ての位置について、その周囲8近傍の値へ1/9をかけて足し合わせているので、結果、一気にフィルタをかけたことになります。

説明が下手で申し訳無いですが、ざっくりとアルゴリズムはこんな感じになります。

実装する

実装してみます。こちらもインターフェースは同じなので、メソッドだけです

def mean_filter(img, filter_size):
  w, h = img.size
  padding_size = (filter_size - 1) // 2
  add_size = padding_size * 2
  pixels = np.array(list(img.getdata())).reshape(h, w, 3)
  mask = np.zeros((h + add_size, w + add_size, 3))

  filter = np.zeros((filter_size, filter_size)) + (1/filter_size ** 2)

  for i in range(filter_size):
    for j in range(filter_size):
      # 9個の配列を用意する代わりに、少しずらしながら足し合わせている
      # * filter[i][j]の部分は * 1/9でもいいが、
      # 平滑化フィルタ以外のフィルタにも適応できるようにしている
      mask[i:h + i, j:w + j] += pixels * filter[i][j]

  # 0パディングした一回り大きな配列から、元のサイズと同じ配列を取り出してる
  new_pixels = mask[padding_size:h+padding_size,padding_size:w+padding_size]
  # 値の整数化
  new_pixels = np.array(list(map(int, new_pixels.reshape(w * h * 3, 1))))
  new_pixels = new_pixels.reshape(w * h, 3)
  filtered_img = Image.new('RGB', (w, h))
  filtered_img.putdata(list(map(tuple, new_pixels)))
  return filtered_img

処理時間は平均0.6秒でした!!

高速化前に比べると速度は6倍になっています!

im2colのときと同様に、フィルタのサイズを7にすると、0.84秒でした。

とても早くなってびっくりです!

最後に

今回は高速化をしてみました。

jitを使えばさらに速くなると思うのですが、なかなかインストールにはまってしまい、なんとかアルゴリズムで高速化しようという試みでした。

動くプログラムを作るのも好きなのですが、リファクタリングや高速化、コードを短くすることも好きです。やりだすとはまってしまいますよね。

ではでは!

読者登録をしていただけると、ブログを続ける励みになりますので、よろしくお願いします。