rect Algorithmus
Verfasst: Montag 7. April 2014, 10:46
Hallo, ich habe folgenden Algorithmus im Internet gefunden, um das größte Rechteck in einem Binärbild zu finden. Leider Programmiere ich noch nicht lange und verstehe den Code nicht ganz. Ich möchte ihn gern Modifizieren um auch die Koordinaten des gefundenen Rechtecks zu erhalten und nicht nur seine Größe. Vielleicht könnt ihr mir ja helfen.
Code: Alles auswählen
from collections import namedtuple
from operator import mul
import cv2
Info = namedtuple('Info', 'start height')
def max_size(mat, value=0):
it = iter(mat)
hist = [(el==value) for el in next(it, [])]
max_size = max_rectangle_size(hist)
for row in it:
hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)]
max_size = max(max_size, max_rectangle_size(hist), key=area)
return max_size
def max_rectangle_size(histogram):
stack = []
top = lambda: stack[-1]
max_size = (0, 0) # height, width of the largest rectangle
pos = 0 # current position in the histogram
for pos, height in enumerate(histogram):
start = pos # position where rectangle starts
while True:
if not stack or height > top().height:
stack.append(Info(start, height)) # push
elif stack and height < top().height:
max_size = max(max_size, (top().height, (pos - top().start)),key=area)
start, _ = stack.pop()
continue
break # height == top().height goes here
pos += 1
for start, height in stack:
print 'pos',pos
print 'start',start
print 'height',height
max_size = max(max_size, (height, (pos - start)), key=area)
return max_size
def area(size):
return reduce(mul, size)
#Beispiel Binärbild:
#Y 0 1 2 X
arr = [[0, 0, 0, 0 ], #0
[0, 1, 0, 0 ], #1
[0, 0, 0, 0 ], #2
]
ausgabe = max_size(arr)
print ausgabe
#(3,2)