再帰関数でのカラー画像をラベリングするプログラムでオーバーフローする

Question

再帰関数プログラムでオーバーフローが発生する

Pythonでカラー画像を類似色を同一領域としてラベリング（１つの領域ごとに番号を付ける）処理を行うプログラムを書いています

例えば、以下のような画像を同じような色の領域ごとに分割します（出力画像は領域の境界が分かるように疑似カラーを付けてあります）

大きなサイズの画像ではオーバーフローが起きてしまうため画像を９ブロック程に分割して１ブロックずつ処理を行いました
しかし、ブロック分割を行って処理を行ってもオーバーフローが発生してしまいます

オーバーフローを回避する方法等教えていただけたら幸いです

エラーメッセージは以下のようになっています

発生している問題・エラーメッセージ

PS C:\Users\cs17090\Saji-Lab\researchSaji\programs> py .\analyze.py       
label number : 53
label number : 36
label number : 26
Traceback (most recent call last):
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
138, in relabeling
    relabeling(j+1,i,pix)
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
138, in relabeling
    relabeling(j+1,i,pix)
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
138, in relabeling
    relabeling(j+1,i,pix)
  [Previous line repeated 19 more times]
  
（中略）

  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
141, in relabeling
    relabeling(j-1,i+1,pix)
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
138, in relabeling
    relabeling(j+1,i,pix)
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
138, in relabeling
    relabeling(j+1,i,pix)
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
138, in relabeling
    relabeling(j+1,i,pix)
  [Previous line repeated 4 more times]
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
133, in relabeling
    relabeling(j+1,i-1,pix)
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
138, in relabeling
    relabeling(j+1,i,pix)
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
138, in relabeling
    relabeling(j+1,i,pix)
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
138, in relabeling
    relabeling(j+1,i,pix)
  [Previous line repeated 32 more times]
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
130, in relabeling
    if (approximation(pix,_la[j,i-1])&(_dm[j,i-1]==0)):
  File "C:\Users\cs17090\Saji-Lab\researchSaji\programs\methods.py", line 
84, in approximation
    if ((d1<dv)&(d2<dv)&(d3<dv)):
MemoryError: Stack overflow

該当のソースコード

import cv2
import numpy as np
import matplotlib.pyplot as plt
import methods


# 入力画像読込
# 画像サイズ（500(width) x 218(height) pix）
img = cv2.imread('images/madslide12.jpg', cv2.IMREAD_COLOR)

# オリジナル画像保存
# import pdb; pdb.set_trace()
org = img.copy()
cv2.imwrite('results/original.png', org)

# 画像ファイル
#   - 画像データを処理プログラムに送る
methods.image(org,img)

# PyMeanShift
#   - 第１引数：探索範囲、第２引数：探索色相、第３引数：粗さ
methods.meanshift(12,3,200)

# ヒストグラム均一化
methods.contrast()

# 類似色統合
methods.clustering()

# ブロック分割
methods.division()

# カラーラベリング
methods.labeling()

import cv2
import matplotlib.pyplot as plt
import matplotlib as mpl
import numpy as np
import pymeanshift as pms
import os
import sys
from PIL import Image
# sys.setrecursionlimit(8000) # 200 x 113 pix
sys.setrecursionlimit(30000)  # 500 x 281 pix
plt.gray()


def image(_org,_img):
  global org,img,h,w,c
  global bo,go,ro,al
  
  org,img = _org,_img
  h,w,c = img.shape
  bo,go,ro = cv2.split(org)
  al = 0.55

def meanshift(spatial_radius,range_radius,min_density):
  global img
  (img,labels,num) = pms.segment(cv2.cvtColor(img,cv2.COLOR_BGR2Lab),spatial_radius,range_radius,min_density)
  img = cv2.cvtColor(img, cv2.COLOR_Lab2BGR)
  cv2.imwrite('results/meanshift.png',img)

def contrast():
  global img
  hsv = cv2.cvtColor(img, cv2.COLOR_BGR2HSV)
  h,s,v = cv2.split(hsv)

  clahe = cv2.createCLAHE(clipLimit=2.0, tileGridSize=(3, 3))
  result = clahe.apply(v)

  hsv = cv2.merge((h,s,result))
  img = cv2.cvtColor(hsv, cv2.COLOR_HSV2BGR)
  cv2.imwrite("results/contrast.png", img)

def division():
  global block
  hs,ws,cnt = 113,200,1

  if ((h>hs)&(w>ws)):
    for j in range(0,h,hs):
      for i in range(0,w,ws):
        if (((j+hs)<h)&((i+ws)<w)):
          div = np.zeros((hs,ws,c),dtype=int)
          div[0:hs,0:ws] = img[j:j+hs,i:i+ws]
        else:
          if (((i+ws)>w)&((j+hs)>h)):
            div = np.zeros((h-j,w-i,c),dtype=int)
            div[0:h-j,0:w-i] = img[j:h,i:w]
          elif ((j+hs)>h):
            div = np.zeros((h-j,ws,c),dtype=int)
            div[0:h-j,0:ws] = img[j:h,i:i+ws]
          else:
            div = np.zeros((hs,w-i,c),dtype=int)
            div[0:hs,0:w-i] = img[j:j+hs,i:w]
        cv2.imwrite('results/division/division{}.png'.format(cnt),div)
        cnt += 1
  block = cnt
  print('block number :',block)

def clustering():
  global img
  im = Image.open('results/contrast.png')
  im_q = im.quantize(colors=128, method=0, dither=1)
  im_q.save('results/clustering.png')
  img = cv2.imread('results/clustering.png', cv2.IMREAD_COLOR)

def approximation(pix1,pix2):
  dif = abs(pix1.astype(np.int8)-pix2.astype(np.int8))
  d1,d2,d3 = dif[0],dif[1],dif[2]
  dv = 10
  if ((d1<dv)&(d2<dv)&(d3<dv)):
    return True
  else:
    return False

def relabeling(j,i,pix):
  # 同色領域にラベル付与
  if ((j>=1)&(i>=1)&(j<_la.shape[0]-1)&(i<_la.shape[1]-1)):
    _dm[j,i] = label
    la[j-1,i-1] = label*5,label*10,label*30

    # 8近傍
    if (approximation(pix,_la[j-1,i-1])&(_dm[j-1,i-1]==0)):
      relabeling(j-1,i-1,pix)
    if (approximation(pix,_la[j,i-1])&(_dm[j,i-1]==0)):
      relabeling(j,i-1,pix)
    if (approximation(pix,_la[j+1,i-1])&(_dm[j+1,i-1]==0)):
      relabeling(j+1,i-1,pix)
    
    if (approximation(pix,_la[j-1,i])&(_dm[j-1,i]==0)):
      relabeling(j-1,i,pix)
    if (approximation(pix,_la[j+1,i])&(_dm[j+1,i]==0)):
      relabeling(j+1,i,pix)
    
    if (approximation(pix,_la[j-1,i+1])&(_dm[j-1,i+1]==0)):
      relabeling(j-1,i+1,pix)
    if (approximation(pix,_la[j,i+1])&(_dm[j,i+1]==0)):
      relabeling(j,i+1,pix)
    if (approximation(pix,_la[j+1,i+1])&(_dm[j+1,i+1]==0)):
      relabeling(j+1,i+1,pix)

def _labeling(div):
  global _dm,dm,_la,la,label
  dh,dw = div.shape[0],div.shape[1]
  _dm,_la,la = np.zeros((dh+2,dw+2),dtype=int),np.zeros((dh+2,dw+2,c),dtype=int),np.zeros((dh,dw,c),dtype=int)

  _la[1:dh+1,1:dw+1] = div
  label = 1

  for j in range(1,dh+1):
    for i in range(1,dw+1):
      # ダミー配列にラベル付けされている画素ならば処理を行わない
      if (_dm[j,i]==0):
        # 注目画素値取得
        pix = div[j-1,i-1]
        # ラベリング
        relabeling(j,i,pix)
        # ラベル更新
        label += 1

  print('label number :',label)

  dm = np.zeros((dh,dw,c),dtype=int)
  dm = _dm[1:dh+1,1:dw+1]

  la = la.astype(np.uint8)
  
  return dm,la

def labeling():
  global label
  label = 1
  dir = 'results/division'
  n = (sum(os.path.isfile(os.path.join(dir,name)) for name in os.listdir(dir)))

  for i in range(4,n+1):
    div = cv2.imread('results/division/division{}.png'.format(i),cv2.IMREAD_COLOR)
    # dh,dw = div.shape[0],div.shape[1]
    # d,l = np.zeros((dh,dw),dtype=int),np.zeros((dh,dw,c),dtype=int)
    d,l = _labeling(div)
    np.savetxt('results/dummy/dummy{}.txt'.format(i),d,fmt='%d')
    cv2.imwrite('results/dummy/dummy{}.png'.format(i),d)
    cv2.imwrite('results/labeling/labeling{}.png'.format(i),l)

試したこと

再帰処理を減らす、関数の引数を減らす、無駄な処理を減らす等負荷が軽くなるようなことを中心に行いましたが、途中でオーバーフローしてしまいました

Comments

[A_kirisaki]

できればソースコード全文載せていただければ再現しやすいのでよろしくおねがいします。あと relabeling の global を忘れている？

[ppaul]

質問と関係ありませんが、以下は大丈夫ですか？

>>> pix1 = np.array([0, 0, 0], dtype=int)
>>> pix2 = np.array([255, 255, 255], dtype=int)
>>> print(pix1)
[0 0 0]
>>> print(pix2)
[255 255 255]
>>> dif = abs(pix1.astype(np.int8)-pix2.astype(np.int8))
>>> print(dif)
[1 1 1]

[mu-ro]

A_kirisakiさん、ありがとうございます
ソースコード全文を掲載しました
それから確かにrelabelingでglobalが欲しかったかもしれないです！

[mu-ro]

ppaulさん、指摘ありがとうございます

指摘いただいた通り
>>> dif = abs(pix1.astype(np.int8)-pix2.astype(np.int8))
>>> print(dif)
[255 255 255]
が期待する値です

int8をintに直したところこの値になりました

[A_kirisaki]

全面的に書き換えていっすか

[mu-ro]

本当ですか？！もし書き換えていただけるならお願いしたいです！

[A_kirisaki]

それだけ我慢ならねえコードを見てしまったってことっすよーーー！！

[mu-ro]

すみませーーーん、、、、、

Answer 1

出来ました。だいたい書き直しです。

import cv2
import numpy as np
import pymeanshift as pms
from PIL import Image
from collections import deque

def meanshift(rgb_img, spatial_radius, range_radius, min_density):
    lab_img, labels, num_seg = pms.segment(cv2.cvtColor(rgb_img, cv2.COLOR_BGR2Lab), spatial_radius, range_radius,min_density)
    new_rgb_img = cv2.cvtColor(lab_img, cv2.COLOR_Lab2BGR)
    return (new_rgb_img, labels, num_seg)

def contrastize(rgb_img):
    hsv_img = cv2.cvtColor(rgb_img, cv2.COLOR_BGR2HSV)
    h, s, v = cv2.split(hsv_img)

    clahe = cv2.createCLAHE(clipLimit=2.0, tileGridSize=(3, 3))
    new_v = clahe.apply(v)

    hsv_clahe = cv2.merge((h, s, new_v))
    new_rgb_img = cv2.cvtColor(hsv_clahe, cv2.COLOR_HSV2BGR)
    return new_rgb_img

def cluster(contrast_img):
    img = Image.fromarray(contrast_img)
    img_q = img.quantize(colors=128, method=0, dither=1)
    a = np.asarray(img_q)
    return np.stack([a]*3, axis=2)

def approximation(pix1, pix2):
    dif = abs(pix1 - pix2)
    dv = 10
    return (dif < dv).all()

def neighbours(idx, lim):
    w, h, _ = lim
    i, j = idx
    return sorted([
            (i + n, j + m)
            for n in range(-1, 2)
            for m in range(-1, 2)
            if not (n == 0 and m == 0) and i + n >= 0 and j + m >= 0 and i + n < w and j + m < h
            ])


def relabel(dummy, src, idx, labels, label):
    q = deque([idx])
    while len(q) > 0:
        idx = q.popleft()
        labels[idx] = (label * 5, label * 10, label * 30)
        dummy[idx] = label
        ns = neighbours(idx, src.shape)
        q.extendleft(n for n in ns if approximation(src[n], src[idx]) and dummy[n] == 0)


def label(filename):
    src = cv2.imread(filename)
    if src is None:
        raise Exception
    (img_shifted, labels, num_seg) = meanshift(src, 12, 3, 200)
    img_cont = contrastize(img_shifted)
    img_cluster = cluster(img_cont)

    h, w, c = src.shape
    dummy = np.zeros((h, w), dtype=int)
    labels = np.zeros((h, w, c), dtype=int)
    label = 1

    it = np.nditer(img_cluster, flags=['multi_index'], op_axes=[[0, 1]])
    for n in it:
        if dummy[it.multi_index] == 0:
            relabel(dummy, img_cluster, it.multi_index,labels, label)
            label += 1

    cv2.imwrite('result.png', labels.astype(np.uint8))

if __name__ == '__main__':
    label('Lenna_big.png')

2048x2048 でもスタックオーバーフローしませんでした。遅いですが。毎回 approximation を計算しているところがとりあえずは改善できそうかなという気はします。速度を求めるならアルゴリズム自体の改善が必要そうですね。


グローバル変数はもうこりごり。

Comments

[mu-ro]

本当にありがとうございます！！！approximation関数を導入してからオーバーフローを起こすようになったのでどうしようと思っていたので助かりました、コードを読んで理解したいと思います！
それから無事に大きいサイズでも動作しました、ありがとうございます！