　自力での実装はできなかった。

成果物

github

自前で頑張って実装してみたが失敗した

再帰: 再帰回数超過エラーになった
while: 無限ループになって応答しなくなった
他:
- 範囲外まで塗りつぶし
- 範囲の一部が塗れない

　度重なる失敗で心が折れた。そこで調査することにした。　

情報源

Flood Fill

　よくあるペイントアプリのバケツ。隣接する同じ色のピクセルを指定した色で一斉に塗り替える。この塗りつぶしアルゴリズムをFloodFillというらしい。

ライブラリ

cv2.floodFill

cv2.floodFill(image, mask, seedPoint, newVal[, loDiff[, upDiff[, flags]]]) → retval, rect

　OpenCVとは、画像処理・画像解析・機械学習ライブラリ。

skimage.segmentation.flood_fill

flood_fill(image, seed_point, new_value, *, selem=None, connectivity=None, tolerance=None, in_place=False, inplace=None)

　Scikit-Imageとは、画像処理アルゴリズムを集めたライブラリ。

インストール

sudo pip3 install six
sudo pip3 install scikit-image

$ sudo pip3 install six
Looking in indexes: https://pypi.org/simple, https://www.piwheels.org/simple
Requirement already satisfied: six in /usr/lib/python3/dist-packages (1.12.0)
WARNING: You are using pip version 20.1; however, version 20.1.1 is available.
You should consider upgrading via the '/usr/bin/python3 -m pip install --upgrade pip' command.

$ sudo pip3 install scikit-image
Looking in indexes: https://pypi.org/simple, https://www.piwheels.org/simple
Collecting scikit-image
  Downloading https://www.piwheels.org/simple/scikit-image/scikit_image-0.17.2-cp37-cp37m-linux_armv7l.whl (28.3 MB)
     |████████████████████████████████| 28.3 MB 87 kB/s 
Collecting networkx>=2.0
  Downloading networkx-2.4-py3-none-any.whl (1.6 MB)
     |████████████████████████████████| 1.6 MB 1.3 MB/s 
Collecting matplotlib!=3.0.0,>=2.0.0
  Downloading https://www.piwheels.org/simple/matplotlib/matplotlib-3.2.1-cp37-cp37m-linux_armv7l.whl (11.9 MB)
     |████████████████████████████████| 11.9 MB 697 kB/s 
Requirement already satisfied: numpy>=1.15.1 in /usr/lib/python3/dist-packages (from scikit-image) (1.16.2)
Requirement already satisfied: pillow!=7.1.0,!=7.1.1,>=4.3.0 in /usr/local/lib/python3.7/dist-packages (from scikit-image) (7.1.2)
Collecting scipy>=1.0.1
  Downloading https://www.piwheels.org/simple/scipy/scipy-1.4.1-cp37-cp37m-linux_armv7l.whl (50.7 MB)
     |████████████████████████████████| 50.7 MB 778 bytes/s 
Collecting imageio>=2.3.0
  Downloading imageio-2.8.0-py3-none-any.whl (3.3 MB)
     |████████████████████████████████| 3.3 MB 3.7 MB/s 
Collecting tifffile>=2019.7.26
  Downloading tifffile-2020.5.11-py3-none-any.whl (132 kB)
     |████████████████████████████████| 132 kB 3.8 MB/s 
Collecting PyWavelets>=1.1.1
  Downloading https://www.piwheels.org/simple/pywavelets/PyWavelets-1.1.1-cp37-cp37m-linux_armv7l.whl (6.1 MB)
     |████████████████████▉           | 4.0 MB 455 kB/s eta 0:00:05
Collecting decorator>=4.3.0
  Downloading decorator-4.4.2-py2.py3-none-any.whl (9.2 kB)
Collecting kiwisolver>=1.0.1
  Downloading https://www.piwheels.org/simple/kiwisolver/kiwisolver-1.2.0-cp37-cp37m-linux_armv7l.whl (1.5 MB)
     |████████████████████████████████| 1.5 MB 401 kB/s 
Collecting python-dateutil>=2.1
  Downloading python_dateutil-2.8.1-py2.py3-none-any.whl (227 kB)
     |████████████████████████████████| 227 kB 4.0 MB/s 
Collecting cycler>=0.10
  Downloading cycler-0.10.0-py2.py3-none-any.whl (6.5 kB)
Collecting pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1
  Downloading pyparsing-2.4.7-py2.py3-none-any.whl (67 kB)
     |████████████████████████████████| 67 kB 527 kB/s 
Collecting imagecodecs>=2020.2.18
  Downloading https://www.piwheels.org/simple/imagecodecs/imagecodecs-2020.2.18-cp37-cp37m-linux_armv7l.whl (8.2 MB)
     |████████████████████████████████| 8.2 MB 407 kB/s 
Requirement already satisfied: six>=1.5 in /usr/lib/python3/dist-packages (from python-dateutil>=2.1->matplotlib!=3.0.0,>=2.0.0->scikit-image) (1.12.0)
ERROR: THESE PACKAGES DO NOT MATCH THE HASHES FROM THE REQUIREMENTS FILE. If you have updated the package versions, please update the hashes. Otherwise, examine the package contents carefully; someone may have tampered with them.
    PyWavelets>=1.1.1 from https://www.piwheels.org/simple/pywavelets/PyWavelets-1.1.1-cp37-cp37m-linux_armv7l.whl#sha256=1ae8c82b6bf4b74376122eb06b59dc98f5b2ccee9adcee1a0445b5959f6ea97e (from scikit-image):
        Expected sha256 1ae8c82b6bf4b74376122eb06b59dc98f5b2ccee9adcee1a0445b5959f6ea97e
             Got        fc8c5f16700ed2ec21bdb49238117eb6dd1d6c39fd63d0748825ae4ea5a5fcaf

WARNING: You are using pip version 20.1; however, version 20.1.1 is available.
You should consider upgrading via the '/usr/bin/python3 -m pip install --upgrade pip' command.

　エラー出た。アップデートしてみた。

sudo pip3 install -U scikit-image
Looking in indexes: https://pypi.org/simple, https://www.piwheels.org/simple
Collecting scikit-image
  Using cached https://www.piwheels.org/simple/scikit-image/scikit_image-0.17.2-cp37-cp37m-linux_armv7l.whl (28.3 MB)
Collecting PyWavelets>=1.1.1
  Downloading https://www.piwheels.org/simple/pywavelets/PyWavelets-1.1.1-cp37-cp37m-linux_armv7l.whl (6.1 MB)
     |████████████████████████████████| 6.1 MB 530 kB/s 
Collecting networkx>=2.0
  Using cached networkx-2.4-py3-none-any.whl (1.6 MB)
Collecting scipy>=1.0.1
  Using cached https://www.piwheels.org/simple/scipy/scipy-1.4.1-cp37-cp37m-linux_armv7l.whl (50.7 MB)
Requirement already satisfied, skipping upgrade: numpy>=1.15.1 in /usr/lib/python3/dist-packages (from scikit-image) (1.16.2)
Collecting tifffile>=2019.7.26
  Using cached tifffile-2020.5.11-py3-none-any.whl (132 kB)
Requirement already satisfied, skipping upgrade: pillow!=7.1.0,!=7.1.1,>=4.3.0 in /usr/local/lib/python3.7/dist-packages (from scikit-image) (7.1.2)
Collecting imageio>=2.3.0
  Using cached imageio-2.8.0-py3-none-any.whl (3.3 MB)
Collecting matplotlib!=3.0.0,>=2.0.0
  Using cached https://www.piwheels.org/simple/matplotlib/matplotlib-3.2.1-cp37-cp37m-linux_armv7l.whl (11.9 MB)
Collecting decorator>=4.3.0
  Using cached decorator-4.4.2-py2.py3-none-any.whl (9.2 kB)
Collecting imagecodecs>=2020.2.18
  Using cached https://www.piwheels.org/simple/imagecodecs/imagecodecs-2020.2.18-cp37-cp37m-linux_armv7l.whl (8.2 MB)
Collecting python-dateutil>=2.1
  Using cached python_dateutil-2.8.1-py2.py3-none-any.whl (227 kB)
Collecting pyparsing!=2.0.4,!=2.1.2,!=2.1.6,>=2.0.1
  Using cached pyparsing-2.4.7-py2.py3-none-any.whl (67 kB)
Collecting cycler>=0.10
  Using cached cycler-0.10.0-py2.py3-none-any.whl (6.5 kB)
Collecting kiwisolver>=1.0.1
  Using cached https://www.piwheels.org/simple/kiwisolver/kiwisolver-1.2.0-cp37-cp37m-linux_armv7l.whl (1.5 MB)
Requirement already satisfied, skipping upgrade: six>=1.5 in /usr/lib/python3/dist-packages (from python-dateutil>=2.1->matplotlib!=3.0.0,>=2.0.0->scikit-image) (1.12.0)
Installing collected packages: PyWavelets, decorator, networkx, scipy, imagecodecs, tifffile, imageio, python-dateutil, pyparsing, cycler, kiwisolver, matplotlib, scikit-image
Successfully installed PyWavelets-1.1.1 cycler-0.10.0 decorator-4.4.2 imagecodecs-2020.2.18 imageio-2.8.0 kiwisolver-1.2.0 matplotlib-3.2.1 networkx-2.4 pyparsing-2.4.7 python-dateutil-2.8.1 scikit-image-0.17.2 scipy-1.4.1 tifffile-2020.5.11
WARNING: You are using pip version 20.1; however, version 20.1.1 is available.
You should consider upgrading via the '/usr/bin/python3 -m pip

コード

　実行できるかテスト。

a.py

import numpy
from skimage.segmentation import flood_fill
ary = numpy.array(
    [0,0,1,0,
     0,0,1,0,
     0,0,1,1,
     0,0,0,0
    ]).reshape(4, 4)
print(ary)
print(flood_fill(ary, (0, 0), 9))

python3 a.py

　エラー。

Traceback (most recent call last):
  File "a.py", line 2, in <module>
    from skimage.segmentation import flood_fill
  File "/usr/local/lib/python3.7/dist-packages/skimage/segmentation/__init__.py", line 1, in <module>
    from .random_walker_segmentation import random_walker
  File "/usr/local/lib/python3.7/dist-packages/skimage/segmentation/random_walker_segmentation.py", line 44, in <module>
    from scipy.sparse.linalg import cg, spsolve
  File "/usr/local/lib/python3.7/dist-packages/scipy/sparse/linalg/__init__.py", line 113, in <module>
    from .isolve import *
  File "/usr/local/lib/python3.7/dist-packages/scipy/sparse/linalg/isolve/__init__.py", line 6, in <module>
    from .iterative import *
  File "/usr/local/lib/python3.7/dist-packages/scipy/sparse/linalg/isolve/iterative.py", line 10, in <module>
    from . import _iterative
ImportError: libf77blas.so.3: cannot open shared object file: No such file or directory

　以下エラーメッセージでググる。

ImportError: libf77blas.so.3: cannot open shared object file: No such file or directory

sudo apt install libatlas-base-dev

　上記ライブラリをインストール後、再度実行。

python3 a.py

[[0 0 1 0]
 [0 0 1 0]
 [0 0 1 1]
 [0 0 0 0]]
[[9 9 1 0]
 [9 9 1 0]
 [9 9 1 1]
 [9 9 9 9]]

　成功。(0,0)座標を起点にして9で塗りつぶした。

まとめ

sudo apt install libatlas-base-dev
sudo pip3 install six
sudo pip3 install scikit-image
sudo pip3 install -U scikit-image

a.py

import numpy
from skimage.segmentation import flood_fill
ary = numpy.array(
    [0,0,1,0,
     0,0,1,0,
     0,0,1,1,
     0,0,0,0
    ]).reshape(4, 4)
print(ary)
print(flood_fill(ary, (0, 0), 9))

python3 a.py

[[0 0 1 0]
 [0 0 1 0]
 [0 0 1 1]
 [0 0 0 0]]
[[9 9 1 0]
 [9 9 1 0]
 [9 9 1 1]
 [9 9 9 9]]

所感

　あー疲れた。まさか塗りつぶしでこれほど苦労するとは。さらにこれをPillowやQtのImageクラスに適用させねばならない。これからが本番。

対象環境

2020-05-22
Raspbierry pi 4 Model B
Raspbian buster 10.0 2019-09-26 ※
bash 5.0.3(1)-release
Python 3.7.3
scikit-image 0.17.2

$ uname -a
Linux raspberrypi 4.19.97-v7l+ #1294 SMP Thu Jan 30 13:21:14 GMT 2020 armv7l GNU/Linux

やってみる

アウトプットすべく己を導くためのブログ。その試行錯誤すらたれ流す。

バケツツールによる塗りつぶしアルゴリズムFloodFillについて

成果物