Finding largest Rectangles in Images, through Optimization

Question

The problem: I have a binary image, with multiple objects. I need to find a way to fit the largest possible Square in these irregular objects. see image attached below

I tried to formulate this as an optimization problem using boundingbox of each labelled object as initial guess and a cost function as shown below. Bounding Box rows are assumed as initial guess for colums as well since its a square.

Using the same approach as Stefan's answer on stackoverflow: fitting a circle to a binary image For my parameters I cannot figure out how to optimize the parameters against this simple cost function

import scipy.optimize as optimize
import numpy as np
import skimage.draw as draw
import skimage.measure as measure

def cost(params):
   baser,basec,deltar = params
   ycords = range(int(baser),int(baser + deltar))
   xcords = range(int(basec),int(basec + deltar))
   coords = draw.polygon(ycords,xcords,shape=region.image.shape)    
   template = np.zeros_like(region.image)
   template[coords] = 1
return -np.sum(template == region.image)
labels , nlabels = measure.label(img,neighbors=4,return_num=True)
regions = measure.regionprops(labels.astype(int))

for region in regions:
   minr, minc, maxr, _ = region.bbox
   baser = minr
   basec = minc
   deltar = maxr-minr   # One parameter in case of square

   print "intial :", baser,basec,deltar
   OptimizeResult = optimize.fmin(cost,(baser,basec,deltar),disp=True)

    baser,basec,deltar = OptimizeResult 
    print "final : " , OptimizeResult
    # the above 2 are same. and so the results don't change

The params do not change, optimization stops at iteration 0. and cost does not change as well. I have tried different solvers, and optimize.minimize. the params don't change.

Ideally I would want a rectangle in each of the regions. each region(binary object) color coded in different color

Please also comment if optimization is a good way to solve these problems.

The Annotated image as requested is posted below.The rectangles(assume squares after edit) on a few objects are in BLACK (sorry for poor color choice)

Please annotate the image with the solution that you are after. — , Oct 20 '16 at 12:16
This can be addressed using erosions with a rectangular structuring element. For a given element width, increase the height until the regions vanish; then restart with an increased width. This will give you (w, h) curves for every shape. — , Oct 20 '16 at 18:46
I dislike the optimization-based approach here. One of the most simple approaches will use some [labeling-algorithm](http://scikit-image.org/docs/dev/api/skimage.measure.html?highlight=label#label) to get information of connected pixels. Then, naivly, you can just loop over the four dimensions of (x,y,x_length,y_length) and check if all labeled pixels (the vals define an cropped-image) are the same. Of course it's possible to prune away candidates if the volume is lower than the current best (if you create your loop to check the bigggest ones first) **edit:** forgot rotations. — sascha, Oct 20 '16 at 18:49
The problem with optimization (compared to the approach you linked): (1) A rectangle has one more degree of freedom (2) You would probably need to do this in an iterative way, marking used pixels. This means you have to incorporate this into the optimization-problem which might be not trivial (without discrete variables) (3) While the problem might be convex, not every formulation of it will be convex. This results in only locally-optimal solutions.(4)If you prepare your image, the problem of finding the biggest rectangle within a polygon is a polynomially-solvable problem ->use these algs — sascha, Oct 20 '16 at 18:55
@sascha Your explanation helped a lot, Convinced that convex optimization is not a good idea, but I'm still not sure why it didn't work out. I tried your suggestions: I changed the parametrization to (x,y,x+x_length,y+y_length) and tried to fit it with a square as you said in 1) have one less degrees of freedom, and be the same as Stefan's fitting Circle answer. so the Square params now: (x,y, length). didn't work out either. I tried swithching solvers too 4) which algorithms are you referring to? broken link? — Irtaza, Oct 20 '16 at 21:25
@iratzhash How do you expect help here? You did not provide a link to your image, you did not post self-running code including some **current** assumptions (started with rectangles; now squares). It's obvious that your current code will be trouble. You are using unconstrained optimization and sometime the parameters will generate infeasible values in regards to draw_polygon for example (as nothing is bounded and you got many dims). For Stefan it's working, as he starts at some centre and has a less hard opt-problem(less dims) so it's unlikely, that the start-point is reaching some trouble-val. — sascha, Oct 20 '16 at 21:45
@sascha Changed the code in the question, not there is one less parameter, so same degrees of freedom as a circle in Stefan's Answer. I take the Intial guess of square length parameter from the rows of bounding box. Assume the annotations are largest Squares in regions, instead of rectangles. By dimensions what are you referring to, Aren't the number of parameters now same to Stefan's answer (x0,y0,deltar) ? — Irtaza, Oct 21 '16 at 05:51
@sascha : To avoid suboptimal solutions, The regionprops.centroid can be a good guess for (x0,y0) and the larger of the bbox dimensions for length param. I tried that now, still does not converge, What could be a better cost function? — Irtaza, Oct 21 '16 at 06:03
@YvesDaoust So I errode the image with rectangle selem in 2 loops unitl image vanishes and save the height and width. How to use these curves to find a rectangle? — Irtaza, Oct 21 '16 at 09:13
@iratzhash: depending on what you call the "largest" rectangle, find the maximum of W+H or W.H. This is trivial. — , Oct 21 '16 at 09:15

Finding largest Rectangles in Images, through Optimization

0 Answers0