は、私はここの回答でコードを追跡しようとしている最大の長方形

Question

の位置を取得します。コレクション

import namedtuple 
from operator import mul 
import numpy as np 
import functools 

x = np.zeros(shape=(4,5)) 
x[0][0] = 1 
x[0][1] = 1 
x[0][2] = 1 
x[0][3] = 1 
x[1][0] = 1 
x[1][1] = 1 
x[1][2] = 1 
x[1][3] = 1 
print(x) 
print(max_size(x)) 

Info = namedtuple('Info', 'start height') 

def find_maximum_frame(mat, value=1): 
    """Find height, width of the largest rectangle containing all `value`'s.""" 
    it = iter(mat) 
    hist = [(el==value) for el in next(it, [])] 
    max_size, _ = max_rectangle_size(hist) 
    old_size = (0,0) 
    coordinates = None 
    for y,row in enumerate(it): 
     hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)] 
     new_rect, c = max_rectangle_size(hist) 
     max_size = max(max_size, new_rect, key=area) 
     if max_size[0]*max_size[1] > old_size[0]*old_size[1]: 
      coordinates = [c[0], (y+2)-max_size[0]] 
     old_size = max_size 
    return [max_size, coordinates] 

def max_rectangle_size(histogram): 
    """Find height, width of the largest rectangle that fits entirely under 
    the 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 
       print(stack) 
      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 
    coordinates = [0,0] 
    old_size = (0,0) 
    for start, height in stack: 
     max_size = max(max_size, (height, (pos - start)), key=area) 
     if max_size[0]*max_size[1] > old_size[0]*old_size[1]: 
      coordinates = [start,height] 
     old_size = max_size 
    return [max_size, coordinates] 

def area(size): 
    return functools.reduce(mul, size) 

から

上記のコードは、長方形の左上隅を見つけるために、私の例でに動作しているようですが、私は大きな画像でそれをしようとすると、それは壊しだと私ができますなぜデバッグできません。ここ

Answer 1

J.F.セバスチャンのanswerのGist versionを修正液：

from collections import namedtuple 

Info = namedtuple('Info', 'start height') 

# returns height, width, and position of the top left corner of the largest 
# rectangle with the given value in mat 
def max_size(mat, value=0): 
    it = iter(mat) 
    hist = [(el==value) for el in next(it, [])] 
    max_size_start, start_row = max_rectangle_size(hist), 0 
    for i, row in enumerate(it): 
     hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)] 
     mss = max_rectangle_size(hist) 
     if area(mss) > area(max_size_start): 
      max_size_start, start_row = mss, i+2-mss[0] 
    return max_size_start[:2], (start_row, max_size_start[2]) 

# returns height, width, and start column of the largest rectangle that 
# fits entirely under the histogram 
def max_rectangle_size(histogram): 
    stack = [] 
    top = lambda: stack[-1] 
    max_size_start = (0, 0, 0) # height, width, start 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_start = max(
        max_size_start, 
        (top().height, pos - top().start, top().start), 
        key=area) 
       start, _ = stack.pop() 
       continue 
      break # height == top().height goes here 

    pos += 1 
    for start, height in stack: 
     max_size_start = max(max_size_start, (height, pos - start, start), 
      key=area) 

    return max_size_start 

def area(size): return size[0]*size[1] 

コードは、位置がテストに追加されるとGist versionからすべてのテストを通過します。ここで、例えば、第1の試験：

self.assertEqual(max_size(self.__s2m(""" 
    0 0 0 0 1 0 
    0 0 1 0 0 1 
    0 0 0 0 0 0 
    1 0 0 0 0 0 
    0 0 0 0 0 1 
    0 0 1 0 0 0""")), ((3, 4), (2, 1))) 

サイズ（3,4）の矩形は位置（2,1）にある。