こんにちは、エンジニアのさもです。ブンバボーンしてますか？
画像処理第７回目は少し画像処理から離れてアルゴリズムのお話です。
今までの実装を見直し、ボトルネックになっていた２重のfor文を何とか高速化したいと思います。
スポンサーリンク
目次
はじめに
これまでの画像処理の実装では、１ピクセル一つ一つに対して処理を行ってきました。この場合、２重のfor文を使っていたのですごく時間がかかっていました。
そこで、この２重for文を解消し高速化する方法を２種類紹介したいと思います。（※jitは使わないです）
実装例では、平滑化フィルタを対象に高速化します。
１つ目の方法は、im2colというメソッドを使って、フィルタをかける処理をドット積で一気に計算します。
２つ目の方法は、私が考えた方法で、少しずらした画像をフィルタの大きさ分重ね合わせることで、フィルタをかけたときと同じ計算がされるようにします。
スポンサーリンク
遅いソースコード
これまで使ってきた平滑化フィルタです。
ざっくり説明すると、画像のピクセル一つ一つを走査するようにループをまわし、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の画像へフィルタをかけたいと思います。
フィルタをかける際は、まず0パディングします。
0パディングとは、画像の周りに値が０の画素を追加することです。
なぜこんなことをするかというと、
例えば、元の画像の(0,0)の位置とその周辺との平均を取ろうとしたとき、(-1, 0)や（-1,-1）など存在しない画素を取得できないからです。
０パディングした元画像の、(0, 0)の位置にある画素を平滑化フィルタにかけるというのは、以下の画像のようなイメージです
この操作を全ての画素に順番に行ったのが、始めに紹介した平滑化フィルタです。
私が考えたアルゴリズムは、この操作を一気に全ての画素に対して行う方法です。
そのために、まず、次のような9個の画素の配列を考えます。
真ん中は元画像に0パディングした配列ですが、その他は、少しずつずらせています。
次に、全ての配列に1/9をかけて重ね合わせ（足し合わせる）ます。
するとどうでしょう。
例えば、足し合わせた後の(1,1)の位置の値に注目してみます。
この値は、元の画像に0パディングした画像の配列の(1,1)の位置へ平滑化フィルタをかけた値と同じになっています。
全ての位置について、その周囲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を使えばさらに速くなると思うのですが、なかなかインストールにはまってしまい、なんとかアルゴリズムで高速化しようという試みでした。
動くプログラムを作るのも好きなのですが、リファクタリングや高速化、コードを短くすることも好きです。やりだすとはまってしまいますよね。
ではでは！
読者登録をしていただけると、ブログを続ける励みになりますので、よろしくお願いします。
