Subscribed unsubscribe Subscribe Subscribe

k平均法による画像の減色処理のコード

AI Python Ruby 機械学習

 今回は下記書籍のk平均法による画像の減色処理のコードを Ruby で実装してみたいと思います。

ITエンジニアのための機械学習理論入門
https://www.amazon.co.jp/IT-ebook/dp/B016Q22IX2/

 サンプルコードはこちらで公開されています。

github.com

画像ファイルの読み込み

 Python版ではPILライブラリのImageクラスを使って画像ファイルを読み込み、RGBデータとして取得して配列にしています。

Python Imaging Library (PIL)

The Python Imaging Library Handbook

from PIL import Image

im = Image.open("photo.jpg")
pixels = list(im.convert('RGB').getdata())

 Ruby版では ImageMagick をインストールし、RMagick を使って画像を扱いました。

github.com

RMagick 2.12.0 User's Guide and Reference

https://rmagick.github.io/image2.html#export_pixels

 下記サイトを参考にさせていただき、 export_pixels メソッドで取得した 16bit のRGBデータを 8bit に変換しました。

d.hatena.ne.jp

irb(main):001:0> require 'rmagick'
=> true
irb(main):002:0> img = Magick::ImageList.new('./photo.jpg')
=> [./photo.jpg JPEG 520x346 520x346+0+0 DirectClass 8-bit 46kb]
scene=0
irb(main):003:0> img.export_pixels.map {|p| p / 257 }.each_slice(3).to_a

乱数の取得

 Python版ではランダムな整数を取得するために numpy.random.randint を使っています。

from numpy.random import randint

randint(256)

numpy.random.randint — NumPy v1.12 Manual

 このメソッドは引数に渡した整数未満のランダムな整数を返すと言うことで、引数もその範囲に含む random.randint とは動きが異なるようです。

qiita.com

 Ruby版では Random#rand メソッドが同様の挙動になります。

random = Random.new

random.rand(256)

class Random (Ruby 2.4.0)

Rubyでランダムな数値を得る方法 -- ぺけみさお

ゼロ徐算によるエラーの回避

 Python版ではk平均法によって新しい代表点を求める際に、下記のような計算を行なっています。

for i in range(k):
    center_new[i] = center_new[i] / num_points[i]

 このとき、特にクラスタ数が多いケースだと、あるクラスタに属する点がないときに num_points[i] が 0 になり、ゼロ徐算が発生します。 center_new[i] は ndarray のオブジェクトですが、通常の数値計算のゼロ徐算だとエラーになるのに対し、ndarrayに対するゼロ徐算はWarningで、エラーにはならないようです。

>>> np.array([100, 100, 100]) / 0                               
__main__:1: RuntimeWarning: divide by zero encountered in divide
array([0, 0, 0])                                                

 Ruby では Numo::NArray に対するゼロ徐算はエラーになります。

irb(main):085:0* Numo::NArray[100,100,100] / 0
ZeroDivisionError: error in NArray operation
        from (irb):85:in `/'
        from (irb):85
        from /usr/local/rbenv/versions/2.3.1/bin/irb:11:in `<main>'

 このエラーを回避するために、 num_points[i] が 0 の場合は、 Numo::NArray[0, 0, 0] を返すようにしました。

k.times do |i|
  if num_points[i] == 0
    center_new[i] = Numo::NArray[0, 0, 0]
    next
  end

  center_new[i] = center_new[i] / num_points[i]
end

画像ファイルの変更、保存

 Python版では読み込み時と同様にPILを使用し、元の画像にputdataで計算結果を反映し、ビットマップ形式の別ファイルとして保存しています。

im.putdata(result) # Update image
im.save("output%02d.bmp" % k, "BMP")

 Ruby版では Magick::Image#import_pixels で計算結果を反映して、 Magick::Image#write で別ファイルとして保存しました。読み込みの時に export_pixels で取得した配列データを 8bit に変換してRGB区切りの配列データにしたので、それとは逆に、一次元配列に戻して16bitに変換したものを渡しています。

img.import_pixels(0, 0, img.columns, img.rows, "RGB", result.flatten.map {|p| p * 257 })
img.write("bmp:output%02d.bmp" % k)

https://rmagick.github.io/image2.html#import_pixels

https://rmagick.github.io/image3.html#write

スクリプト全体

 ここまでの内容を踏まえて、コード全体としては下記のように実装しました。

# k平均法による画像の減色処理

require 'rmagick'
require 'numo/narray'

Colors = [2, 3, 5, 16]  # 減色後の色数

# k平均法による減色処理
def run_kmeans(pixels, k)
  cls = Array.new(pixels.size).fill(0)

  # 代表色の初期値をランダムに設定
  random = Random.new
  center = k.times.map { Numo::NArray[random.rand(256), random.rand(256), random.rand(256)] }
  puts "Initial centers: #{center.map(&:to_a)}"
  puts "========================"
  distortion = 0.0

  # 最大50回のIterationを実施
  50.times do |iter_num|
    center_new = Array.new(k).fill(Numo::NArray[0, 0, 0])
    num_points = Array.new(k).fill(0)
    distortion_new = 0.0

    # E Phase: 各データが属するグループ(代表色)を計算
    pixels.each_with_index do |point, pix|
      min_dist = 256 * 256 * 3
      point = Numo::NArray[*point]
      k.times do |i|
        d = (point - center[i]).cast_to(Numo::Int64).to_a.inject(0) {|sum, x| sum + (x ** 2) }
        if d < min_dist
          min_dist = d
          cls[pix] = i
        end

        center_new[cls[pix]] += point
        num_points[cls[pix]] += 1
        distortion_new += min_dist
      end
    end

    # M Phase: 新しい代表色を計算
    k.times do |i|
      if num_points[i] == 0
        center_new[i] = Numo::NArray[0, 0, 0]
        next
      end

      center_new[i] = center_new[i] / num_points[i]
    end
    center = center_new
    puts center.map(&:to_a).inspect
    puts "Distortion: J=#{distortion_new}"

    # Distortion(J)の変化が0.1%未満になったら終了
    if iter_num > 0 && distortion - distortion_new < distortion * 0.001
      break
    end
    distortion = distortion_new
  end

  # 画像データの各ピクセルを代表色で置き換え
  pixels.each_with_index do |point, pix|
    pixels[pix] = center[cls[pix]].to_a
  end

  pixels
end

Colors.each do |k|
  puts ""
  puts "========================"
  puts "Number of clusters: K=#{k}"

  # 画像ファイルの読み込み
  img = Magick::ImageList.new('./photo.jpg')
  pixels = img.export_pixels.map {|p| p / 257 }.each_slice(3).to_a

  # k平均法による減色処理
  result = run_kmeans(pixels, k)
  img.import_pixels(0, 0, img.columns, img.rows, "RGB", result.flatten.map {|p| p * 257 })
  img.write("bmp:output%02d.bmp" % k)
end

 これを実行するとターミナル上では下記のように、初期のランダムな代表点と、計算ごとに変化していく代表点と二乗歪み(J)の値が出力されます。

$ ruby 06-k_means.rb 

========================
Number of clusters: K=2
Initial centers: [[73, 209, 26], [101, 193, 89]]
========================
[[147, 136, 114], [177, 155, 141]]
Distortion: J=11686169170.0
[[140, 126, 102], [231, 210, 215]]
Distortion: J=5777512344.0
[[143, 126, 103], [237, 225, 228]]
Distortion: J=4710119998.0
[[143, 126, 104], [238, 228, 231]]
Distortion: J=4670715192.0
[[143, 126, 104], [238, 228, 231]]
Distortion: J=4668708398.0

========================
Number of clusters: K=3
Initial centers: [[214, 192, 131], [132, 203, 96], [118, 69, 71]]
========================
[[193, 169, 164], [99, 112, 65], [104, 83, 52]]
Distortion: J=8555090758.0
[[192, 173, 165], [102, 106, 61], [105, 55, 41]]
Distortion: J=6458497492.0
[[192, 173, 165], [101, 104, 60], [110, 46, 40]]
Distortion: J=6391712615.0
[[192, 173, 165], [100, 103, 59], [120, 41, 42]]
Distortion: J=6384285256.0
[[192, 173, 165], [96, 101, 56], [153, 33, 52]]
Distortion: J=6369689981.0
[[191, 173, 165], [94, 100, 55], [182, 35, 64]]
Distortion: J=6295123108.0
[[191, 174, 165], [93, 99, 54], [185, 38, 68]]
Distortion: J=6267370834.0
[[191, 174, 165], [93, 99, 54], [186, 40, 70]]
Distortion: J=6265803130.0

========================
Number of clusters: K=5
Initial centers: [[194, 128, 53], [20, 175, 19], [143, 69, 162], [10, 6, 13], [232, 145, 213]]
========================
[[164, 135, 117], [67, 100, 43], [219, 196, 202], [49, 63, 25], [235, 218, 223]]
Distortion: J=17277755636.0
[[174, 141, 131], [84, 99, 48], [235, 220, 224], [71, 50, 25], [245, 243, 244]]
Distortion: J=7740485201.0
[[179, 148, 140], [91, 101, 52], [237, 227, 230], [89, 45, 29], [250, 249, 249]]
Distortion: J=7006558605.0
[[182, 151, 144], [94, 102, 54], [238, 230, 233], [103, 42, 34], [251, 251, 251]]
Distortion: J=6813616639.0
[[183, 153, 146], [94, 102, 54], [239, 232, 234], [118, 38, 38], [252, 252, 252]]
Distortion: J=6752640626.0
[[183, 154, 147], [90, 99, 52], [239, 232, 235], [164, 29, 51], [252, 252, 252]]
Distortion: J=6699438034.0
[[182, 155, 147], [89, 98, 52], [239, 233, 235], [181, 32, 61], [252, 252, 252]]
Distortion: J=6536049096.0
[[182, 156, 147], [89, 98, 51], [239, 233, 235], [183, 35, 64], [252, 252, 252]]
Distortion: J=6513101512.0
[[182, 156, 147], [89, 98, 51], [239, 233, 235], [184, 36, 65], [252, 252, 252]]
Distortion: J=6510842397.0

========================
Number of clusters: K=16
Initial centers: [[240, 182, 207], [150, 87, 15], [121, 236, 188], [140, 204, 22], [66, 131, 79], [157, 120, 116], [17, 196, 63], [164, 6, 24], [34, 40, 245], [45, 113, 4], [229, 65, 229], [117, 158, 111], [114, 36, 146], [51, 62, 230], [
48, 35, 252], [14, 78, 55]]
========================
[[225, 210, 211], [118, 82, 56], [151, 171, 141], [124, 151, 86], [82, 111, 55], [176, 118, 115], [0, 0, 0], [176, 22, 51], [0, 0, 0], [49, 76, 26], [234, 96, 155], [125, 150, 99], [131, 57, 81], [0, 0, 0], [0, 0, 0], [38, 63, 27]]
Distortion: J=17994009460.0
[[226, 215, 214], [117, 78, 55], [169, 157, 139], [116, 141, 83], [78, 107, 48], [201, 99, 122], [24, 49, 15], [180, 25, 54], [0, 0, 0], [46, 72, 26], [224, 103, 146], [121, 147, 105], [153, 62, 72], [0, 0, 0], [0, 0, 0], [32, 57, 20]]
Distortion: J=12774225380.0
[[226, 216, 215], [115, 77, 53], [176, 153, 141], [112, 137, 80], [75, 105, 46], [210, 84, 119], [31, 57, 19], [179, 23, 52], [9, 21, 8], [49, 74, 28], [226, 116, 157], [125, 150, 107], [163, 67, 73], [0, 0, 0], [0, 0, 0], [33, 59, 20]]
Distortion: J=12102951219.0
[[226, 217, 216], [114, 77, 53], [181, 150, 142], [110, 136, 78], [74, 103, 44], [211, 74, 114], [34, 59, 20], [177, 22, 49], [14, 35, 10], [51, 76, 29], [226, 129, 164], [129, 152, 106], [168, 70, 77], [0, 0, 0], [0, 0, 0], [36, 62, 21]]
Distortion: J=11926470826.0
[[226, 217, 216], [113, 78, 53], [184, 148, 143], [109, 135, 77], [73, 102, 43], [210, 68, 109], [35, 61, 21], [174, 21, 47], [18, 41, 12], [52, 78, 30], [227, 135, 168], [131, 152, 106], [170, 73, 79], [0, 0, 0], [0, 0, 0], [39, 65, 21]]
Distortion: J=11849083461.0
[[226, 217, 216], [112, 79, 53], [186, 146, 144], [108, 135, 77], [72, 101, 43], [209, 64, 105], [37, 62, 21], [172, 20, 45], [20, 45, 13], [53, 79, 31], [227, 137, 170], [132, 152, 107], [169, 76, 80], [9, 18, 5], [0, 0, 0], [42, 67, 21]
]
Distortion: J=11816838760.0
[[226, 217, 216], [111, 80, 53], [188, 145, 144], [108, 135, 77], [72, 101, 42], [208, 60, 102], [38, 63, 22], [171, 19, 44], [22, 47, 14], [54, 79, 32], [227, 138, 171], [133, 152, 107], [168, 80, 81], [10, 27, 9], [0, 0, 0], [44, 69, 21
]]
Distortion: J=11800409417.0
[[226, 217, 216], [110, 81, 53], [189, 143, 144], [108, 135, 77], [71, 101, 42], [207, 58, 99], [39, 64, 22], [170, 19, 43], [23, 48, 14], [54, 79, 32], [228, 138, 171], [134, 153, 108], [167, 84, 82], [12, 33, 9], [0, 0, 0], [46, 71, 20]
]
Distortion: J=11789721844.0

 そして下記の元画像に対して、代表色を2色、3色、5色、16色に減色した画像が生成されます。元画像はPython版のサンプルコードと一緒に公開されているものをそのまま使わせていただきましたが、生成後の画像もPython版と同じようなものが生成できたので、問題なさそうです。

オリジナル画像
f:id:akanuma-hiroaki:20170202084457j:plain

2色
f:id:akanuma-hiroaki:20170202084508j:plain

3色
f:id:akanuma-hiroaki:20170202084509j:plain

5色
f:id:akanuma-hiroaki:20170202084510j:plain

16色
f:id:akanuma-hiroaki:20170202084511j:plain

 コードは下記にも公開しました。

github.com