3D二値化画像データの部分fillのプログラムを改良した話

16840 ワード
fill 3D Python Python テキストリンク

前回作ったFillプログラムはスタックオーバーフローしていた

前回の記事で作成したプログラムはスタックオーバーフローを起こしていました。
原因は至極明快で、再起呼び出ししているため一定以上繰り返しがたまるとメモリを圧迫してしまうのです。
研究で使うくらいのデータなら問題ないかなと思いスルーしていたのですが、実際に利用しているデータでもオーバーフローしてしまったので、アルゴリズムを変えようと思いました。

環境

python 3.7.4

ライブラリは特に使ってないです。

解決手法

メモリを圧迫してしまうのが原因だったので、再起呼び出しではなくforを使って繰り返し処理することで解決しようと思いました。
ただ、毎回すべてのセルを見て処理していくのではあまりに時間がかかってしまうので、自身のセルの６方向(上下左右＋Z軸上下)を塗りつぶす関数を作成し、探索するセルの座標を保存して、そのセルに対してのみ処理を行うようにします。
文章で書いてもわからんので、処理の順番を書いてみます。

状態

まずは、セルにどのような状態があるかを表として示します。

状態記号 状態の内容
0 二値化のうちの片方
1 二値化のうちの片方
2 塗りつぶし後のセル

処理

では実際の処理の内容です。
初めの１点については繰り返しはしません(当然ではありますが。)

  1. 初めの1点を定める
  2. 定めた点の座標をlistに入れる(z,y,x)
  3. listからデータを取り出していく。(取り出したデータはlistから削除する)
  4. 該当のセルを塗りつぶす(2にする)
  5. 該当セルの6方向の座標をlistに入れる(すでに探索済みだったり塗りつぶし対象でない場合は入れない)
  6. 3~5をlistが空になるまで繰り返す

こんな感じです。
前回は1セルずつ探索していきましたが、今回は探索するセルをあらかじめ覚えて、一気に処理する、みたいなイメージです。

実装

ではコードを見ていきます。
まずはメインとなる繰り返し処理を行う関数です。

new_fill.py
def fill(data, plot):
    stack=[]
    end_stack=[]
    data, defaultvalue= plot_point(data, plot, stack) # 最初の一点を指定する

    while stack: # 空ではない限り繰り返す
        for pop_data in stack: # stackからデータを取り出していく
            stack.remove(pop_data) # 取り出したデータは削除しておく
            data = step_fill(data, pop_data["x"], pop_data["y"], pop_data["z"], defaultvalue, stack) # 塗りつぶし関数
            end_stack.append(pop_data) # 探索済みのデータとして保存しておく
    return data

こんな感じになっています。

上でも言っていますが、探索するセルのデータを保存していって、探索するセルがなくなったら終わり
という単純なプログラムになってます。

最初の一点を指定するプログラムは前回のものとほとんど同じです。
相違点としては、座標のデータをstackに入れるようにしたので、返り値が変わり、内部でstackに入れ込むようにしています。

new_fill.py
def plot_point(data, plot, stack):
    defaultvalue = data[plot["z"]][plot["y"]][plot["x"]]
    data[plot["z"]][plot["y"]][plot["x"]]=2
    stack.append(plot)
    return data, defaultvalue

stack.append(plot)が加わっただけですね。

そして、周囲を塗りつぶす関数ですが、こちらはもともと再起呼び出しを行っていた関数です。
今回は単純に自身を塗りつぶし、周囲の探索済みでない座標をstackに入れる
といった関数になっています。

new_fill.py
def step_fill(data, x, y, z, defaultvalue, stack):
    data[z][y][x]=2

    if (data[z][y][x-1]==defaultvalue) and (not {"x":x-1, "y":y, "z":z} in stack):
        stack.append({"x":x-1, "y":y, "z":z})

    if (data[z][y][x+1]==defaultvalue) and (not {"x":x+1, "y":y, "z":z} in stack):
        stack.append({"x":x+1, "y":y, "z":z})

    if (data[z][y-1][x]==defaultvalue) and (not {"x":x, "y":y-1, "z":z} in stack):
        stack.append({"x":x, "y":y-1, "z":z})

    if (data[z][y+1][x]==defaultvalue) and (not {"x":x, "y":y+1, "z":z} in stack):
        stack.append({"x":x, "y":y+1, "z":z})

    if (data[z-1][y][x]==defaultvalue) and (not {"x":x, "y":y, "z":z-1} in stack):
        stack.append({"x":x, "y":y, "z":z-1})

    if (data[z+1][y][x]==defaultvalue) and (not {"x":x, "y":y, "z":z+1} in stack):
        stack.append({"x":x, "y":y, "z":z+1})
    return data

単純ですね。
なんかもっときれいに書けそうな気がするので、考えておきます。

以上の3つで3次元塗りつぶしの実装ができます。

ちなみに以前の元の実験の時間を比べてみました。

以前のfill 今回のfill
1 0.004987001419067383 0.12566423416137695
2 0.003987789154052734 0.10970711708068848
3 0.003989219665527344 0.11269998550415039
4 0.004986763000488281 0.11568784713745117
5 0.00598454475402832 0.11369585990905762
6 0.015959978103637695 0.11469197273254395
7 0.004986763000488281 0.11768507957458496
8 0.003989934921264648 0.11369562149047852
9 0.003988981246948242 0.1136932373046875
10 0.005983829498291016 0.11469554901123047
平均 0.00588448047637 0.115191650390625

処理時間は大体200倍になってしまってますね。
もしかすると無駄な処理が混ざってるかもしれないのでまた考えてみようと思います。