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

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

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

該当のソースコード

analyze.py
1import cv2
2import numpy as np
3import matplotlib.pyplot as plt
4import methods
5
6
7# 入力画像読込
8# 画像サイズ（500(width) x 218(height) pix）
9img = cv2.imread('images/madslide12.jpg', cv2.IMREAD_COLOR)
10
11# オリジナル画像保存
12# import pdb; pdb.set_trace()
13org = img.copy()
14cv2.imwrite('results/original.png', org)
15
16# 画像ファイル
17#   - 画像データを処理プログラムに送る
18methods.image(org,img)
19
20# PyMeanShift
21#   - 第１引数：探索範囲、第２引数：探索色相、第３引数：粗さ
22methods.meanshift(12,3,200)
23
24# ヒストグラム均一化
25methods.contrast()
26
27# 類似色統合
28methods.clustering()
29
30# ブロック分割
31methods.division()
32
33# カラーラベリング
34methods.labeling()

methods.py
1import cv2
2import matplotlib.pyplot as plt
3import matplotlib as mpl
4import numpy as np
5import pymeanshift as pms
6import os
7import sys
8from PIL import Image
9# sys.setrecursionlimit(8000) # 200 x 113 pix
10sys.setrecursionlimit(30000)  # 500 x 281 pix
11plt.gray()
12
13
14def image(_org,_img):
15  global org,img,h,w,c
16  global bo,go,ro,al
17  
18  org,img = _org,_img
19  h,w,c = img.shape
20  bo,go,ro = cv2.split(org)
21  al = 0.55
22
23def meanshift(spatial_radius,range_radius,min_density):
24  global img
25  (img,labels,num) = pms.segment(cv2.cvtColor(img,cv2.COLOR_BGR2Lab),spatial_radius,range_radius,min_density)
26  img = cv2.cvtColor(img, cv2.COLOR_Lab2BGR)
27  cv2.imwrite('results/meanshift.png',img)
28
29def contrast():
30  global img
31  hsv = cv2.cvtColor(img, cv2.COLOR_BGR2HSV)
32  h,s,v = cv2.split(hsv)
33
34  clahe = cv2.createCLAHE(clipLimit=2.0, tileGridSize=(3, 3))
35  result = clahe.apply(v)
36
37  hsv = cv2.merge((h,s,result))
38  img = cv2.cvtColor(hsv, cv2.COLOR_HSV2BGR)
39  cv2.imwrite("results/contrast.png", img)
40
41def division():
42  global block
43  hs,ws,cnt = 113,200,1
44
45  if ((h>hs)&(w>ws)):
46    for j in range(0,h,hs):
47      for i in range(0,w,ws):
48        if (((j+hs)<h)&((i+ws)<w)):
49          div = np.zeros((hs,ws,c),dtype=int)
50          div[0:hs,0:ws] = img[j:j+hs,i:i+ws]
51        else:
52          if (((i+ws)>w)&((j+hs)>h)):
53            div = np.zeros((h-j,w-i,c),dtype=int)
54            div[0:h-j,0:w-i] = img[j:h,i:w]
55          elif ((j+hs)>h):
56            div = np.zeros((h-j,ws,c),dtype=int)
57            div[0:h-j,0:ws] = img[j:h,i:i+ws]
58          else:
59            div = np.zeros((hs,w-i,c),dtype=int)
60            div[0:hs,0:w-i] = img[j:j+hs,i:w]
61        cv2.imwrite('results/division/division{}.png'.format(cnt),div)
62        cnt += 1
63  block = cnt
64  print('block number :',block)
65
66def clustering():
67  global img
68  im = Image.open('results/contrast.png')
69  im_q = im.quantize(colors=128, method=0, dither=1)
70  im_q.save('results/clustering.png')
71  img = cv2.imread('results/clustering.png', cv2.IMREAD_COLOR)
72
73def approximation(pix1,pix2):
74  dif = abs(pix1.astype(np.int8)-pix2.astype(np.int8))
75  d1,d2,d3 = dif[0],dif[1],dif[2]
76  dv = 10
77  if ((d1<dv)&(d2<dv)&(d3<dv)):
78    return True
79  else:
80    return False
81
82def relabeling(j,i,pix):
83  # 同色領域にラベル付与
84  if ((j>=1)&(i>=1)&(j<_la.shape[0]-1)&(i<_la.shape[1]-1)):
85    _dm[j,i] = label
86    la[j-1,i-1] = label*5,label*10,label*30
87
88    # 8近傍
89    if (approximation(pix,_la[j-1,i-1])&(_dm[j-1,i-1]==0)):
90      relabeling(j-1,i-1,pix)
91    if (approximation(pix,_la[j,i-1])&(_dm[j,i-1]==0)):
92      relabeling(j,i-1,pix)
93    if (approximation(pix,_la[j+1,i-1])&(_dm[j+1,i-1]==0)):
94      relabeling(j+1,i-1,pix)
95    
96    if (approximation(pix,_la[j-1,i])&(_dm[j-1,i]==0)):
97      relabeling(j-1,i,pix)
98    if (approximation(pix,_la[j+1,i])&(_dm[j+1,i]==0)):
99      relabeling(j+1,i,pix)
100    
101    if (approximation(pix,_la[j-1,i+1])&(_dm[j-1,i+1]==0)):
102      relabeling(j-1,i+1,pix)
103    if (approximation(pix,_la[j,i+1])&(_dm[j,i+1]==0)):
104      relabeling(j,i+1,pix)
105    if (approximation(pix,_la[j+1,i+1])&(_dm[j+1,i+1]==0)):
106      relabeling(j+1,i+1,pix)
107
108def _labeling(div):
109  global _dm,dm,_la,la,label
110  dh,dw = div.shape[0],div.shape[1]
111  _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)
112
113  _la[1:dh+1,1:dw+1] = div
114  label = 1
115
116  for j in range(1,dh+1):
117    for i in range(1,dw+1):
118      # ダミー配列にラベル付けされている画素ならば処理を行わない
119      if (_dm[j,i]==0):
120        # 注目画素値取得
121        pix = div[j-1,i-1]
122        # ラベリング
123        relabeling(j,i,pix)
124        # ラベル更新
125        label += 1
126
127  print('label number :',label)
128
129  dm = np.zeros((dh,dw,c),dtype=int)
130  dm = _dm[1:dh+1,1:dw+1]
131
132  la = la.astype(np.uint8)
133  
134  return dm,la
135
136def labeling():
137  global label
138  label = 1
139  dir = 'results/division'
140  n = (sum(os.path.isfile(os.path.join(dir,name)) for name in os.listdir(dir)))
141
142  for i in range(4,n+1):
143    div = cv2.imread('results/division/division{}.png'.format(i),cv2.IMREAD_COLOR)
144    # dh,dw = div.shape[0],div.shape[1]
145    # d,l = np.zeros((dh,dw),dtype=int),np.zeros((dh,dw,c),dtype=int)
146    d,l = _labeling(div)
147    np.savetxt('results/dummy/dummy{}.txt'.format(i),d,fmt='%d')
148    cv2.imwrite('results/dummy/dummy{}.png'.format(i),d)
149    cv2.imwrite('results/labeling/labeling{}.png'.format(i),l)

試したこと

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

A_kirisaki

2021/01/19 07:56

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

ppaul

2021/01/19 09:16

質問と関係ありませんが、以下は大丈夫ですか？ >>> 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]

vamrat

2021/01/19 10:25

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

vamrat

2021/01/19 10:42 編集

ppaulさん、指摘ありがとうございます指摘いただいた通り >>> dif = abs(pix1.astype(np.int8)-pix2.astype(np.int8)) >>> print(dif) [255 255 255] が期待する値です int8をintに直したところこの値になりました

A_kirisaki

2021/01/19 11:51

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

vamrat

2021/01/19 11:53

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

A_kirisaki

2021/01/19 12:08

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

vamrat

2021/01/19 13:39

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

行動規範の内容に同意します

回答1件

ベストアンサー

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

Python
1import cv2
2import numpy as np
3import pymeanshift as pms
4from PIL import Image
5from collections import deque
6
7def meanshift(rgb_img, spatial_radius, range_radius, min_density):
8    lab_img, labels, num_seg = pms.segment(cv2.cvtColor(rgb_img, cv2.COLOR_BGR2Lab), spatial_radius, range_radius,min_density)
9    new_rgb_img = cv2.cvtColor(lab_img, cv2.COLOR_Lab2BGR)
10    return (new_rgb_img, labels, num_seg)
11
12def contrastize(rgb_img):
13    hsv_img = cv2.cvtColor(rgb_img, cv2.COLOR_BGR2HSV)
14    h, s, v = cv2.split(hsv_img)
15
16    clahe = cv2.createCLAHE(clipLimit=2.0, tileGridSize=(3, 3))
17    new_v = clahe.apply(v)
18
19    hsv_clahe = cv2.merge((h, s, new_v))
20    new_rgb_img = cv2.cvtColor(hsv_clahe, cv2.COLOR_HSV2BGR)
21    return new_rgb_img
22
23def cluster(contrast_img):
24    img = Image.fromarray(contrast_img)
25    img_q = img.quantize(colors=128, method=0, dither=1)
26    a = np.asarray(img_q)
27    return np.stack([a]*3, axis=2)
28
29def approximation(pix1, pix2):
30    dif = abs(pix1 - pix2)
31    dv = 10
32    return (dif < dv).all()
33
34def neighbours(idx, lim):
35    w, h, _ = lim
36    i, j = idx
37    return sorted([
38            (i + n, j + m)
39            for n in range(-1, 2)
40            for m in range(-1, 2)
41            if not (n == 0 and m == 0) and i + n >= 0 and j + m >= 0 and i + n < w and j + m < h
42            ])
43
44
45def relabel(dummy, src, idx, labels, label):
46    q = deque([idx])
47    while len(q) > 0:
48        idx = q.popleft()
49        labels[idx] = (label * 5, label * 10, label * 30)
50        dummy[idx] = label
51        ns = neighbours(idx, src.shape)
52        q.extendleft(n for n in ns if approximation(src[n], src[idx]) and dummy[n] == 0)
53
54
55def label(filename):
56    src = cv2.imread(filename)
57    if src is None:
58        raise Exception
59    (img_shifted, labels, num_seg) = meanshift(src, 12, 3, 200)
60    img_cont = contrastize(img_shifted)
61    img_cluster = cluster(img_cont)
62
63    h, w, c = src.shape
64    dummy = np.zeros((h, w), dtype=int)
65    labels = np.zeros((h, w, c), dtype=int)
66    label = 1
67
68    it = np.nditer(img_cluster, flags=['multi_index'], op_axes=[[0, 1]])
69    for n in it:
70        if dummy[it.multi_index] == 0:
71            relabel(dummy, img_cluster, it.multi_index,labels, label)
72            label += 1
73
74    cv2.imwrite('result.png', labels.astype(np.uint8))
75
76if __name__ == '__main__':
77    label('Lenna_big.png')