4

I would like to divide an image into "rectangular" components that are similar according to some visual criterion:

For example I found these algorithms :

https://scikit-image.org/docs/dev/auto_examples/segmentation/plot_segmentations.html

which are able to divide an image into "superpixels", that may have an arbitrary shape. Is there an open source tool diving an image into regions of rectangular shape ? Just to be clear, the rectangles should constitute a partition of the original image.

Not sure this is the right SE community, this is my first message here. In case, feel free to suggest an other that may be more suited.

Update: after the comments, I am happy to rephrase the problem in the following way. Given a pixel of an image, find a "reasonable" bounding box containing the pixel. Of course the definition of reasonable is loosely defined up to now so I would be happy with different criteria.

Royi
  • 19,608
  • 4
  • 197
  • 238
Thomas
  • 143
  • 5
  • What are the visual criteria you want to use? Should the regions be potentially overlapping (e.g., object detection)? Should the rectangular sections have complete coverage like the linked example? – Ash Mar 09 '22 at 16:59
  • Hello Ash . Thanks a lot for your comment that helps me think a bit more on what I would like. (1) yes the regions could be potentially overalpping (even if not "should be") (2) The coverage should be ideally complete, but, if not possible, should be as large as possible. The idea is, given any pixel in the image, to find a rectangular region that is "semantically" similar to the given point. Of course, no perfect solution is possible in the general case, but something that goes in that direction. – Thomas Mar 09 '22 at 17:12
  • Another way to reframe the question could be this. Given a point in an image, find a reasonable bounding box containing it according to some visual criterion. – Thomas Mar 09 '22 at 17:45
  • It might be beneficial to look into pixel clustering algorithms (e.g. k-means). Once a cluster has been defined, you can use the clusters to define the bounds of the rectangular region of interest. The "reasonable" aspect of where to define the bounds could be related to an outlier detection/rejection method either you define, or which is already accounted for in the clustering algorithm. How to implement this clustering approach depends primarily on what the criteria (i.e. feature of distinction) is. – Ash Mar 10 '22 at 17:23
  • Thanks I can try to play with it, actually I am already starting to do this from the superpixels returned by scikit learn, that can be considered as a result of a clustering algorithm I guess, but I need to see if I am able to do a reasonable post processing. – Thomas Mar 10 '22 at 17:39
  • Ideas are of course welcome but I was hoping in some literature reference or even out of the box code :D – Thomas Mar 10 '22 at 17:40
  • Do you mean super pixels which are limited to a rectangle shape? – Royi Mar 11 '22 at 09:26
  • Yes exactly that is also a way to see the question – Thomas Mar 11 '22 at 11:14

1 Answers1

1

One answer for your question would be limiting Super Pixels to rectangle forms. It requires changing the code of a Super Pixel algorithm to constraint the shape of the Super Pixel. Another approach would be a Rectangle Super Pixel to begin with as in Jan Draegert - Efficient Superpixel Creation in High Resolution Images by Applying a PLANT.

But for the other variant, that show a rectangle neighborhood which is similar, things can be solved more interestingly.

I will sketch 2 optional solutions:

  1. Super Pixel Based.
  2. Optimization Based.

Super Pixel Based

In this case for each super pixel we find, per pixel, the biggest rectangle within the super pixel. This could be easily done by some simple operations in Image Processing.
Less accurate option would be the bounding box of each super pixel. See Obtain box2d() from Super Pixels Segments.

Optimization Based

Per pixel we minimize the function:

$$ \arg \min_{{r}_{1}, {r}{2}} \frac{1}{2} \sum_{k = -{r}_{1}}^{{r}_{1}} \sum_{l = -{r}_{2}}^{{r}_{2}} {\left( I \left[ i, j \right] - I \left[ i - k, j - l \right] \right)}^{2} - \lambda \left( {r}_{1} + {r}_{2} \right) $$

It searches for radii which define a rectangle around the pixel $ I \left[ i, j \right] $ which is similar yet tries to make it as bigger due to the regularization term. With the user selected $ \lambda $ we balance between very similar neighborhood to a large rectangle.

Since the optimization isn't easy it will be viable for small images only.

Royi
  • 19,608
  • 4
  • 197
  • 238
  • Thanks a lot for the suggestions ! (+1) . I guess the second algorithm should not be too expensive to be done for a single pixel. Calling $f(r_1,r_2)$ your function, probably one can use a recursive algorithm to evaluate it inside some cutoff range, and than take the minimum. I could try both approaches and compare ... Of course than doing so for each pixel is another story... – Thomas Mar 11 '22 at 13:57
  • I did not understand your sentence though "limit superpixels to rectangular forms". Is this your approach "Super Pixel Based" (i.e. find first a superpixel and than the bounding box containing it) or do you have some other idea in mind to impose that constraint ? – Thomas Mar 11 '22 at 14:04
  • @Thomas, I meant that in the "growing" phase of the super pixel we'll limit its growing to a rectangle shape. – Royi Mar 11 '22 at 16:48
  • Thanks Royi . I did not understand if this idea of growing superpixels of rectangular shapes is embodied just in your solution "Optimization Based", or if you are saying that it is trivial to adapt any algorithm creating superpixels with that constraint. – Thomas Mar 11 '22 at 16:56
  • Your solutions refer to the "other variant", but I did not understand what do you propose for the "first" variant. I guess for the first variant you mean when the rectangular superpixels consitute a partition of the image (so bounding boxes non overlapping), and the second when given a pixel one wants to find a bounding box. Could you clarify a bit ? – Thomas Mar 11 '22 at 16:59
  • @Thomas, Indeed. The first approach is Rectangle Super Pixels. It means the image is divide to exclusive segments. This require you take a super pixel code and modify its "growing" step. The 2 other solutions I suggested are from a pixel point of view. For each pixel its own bounding box. – Royi Mar 11 '22 at 18:00
  • Thanks also for the added reference, I will check it. In case I decide to try to change a code for superpixel creation, among the other trials, would you suggest one that you may thing is more easily amenable to such a modification? I am just crossing now the problem of superpixel creation and still have to orient myself through this space... – Thomas Mar 11 '22 at 19:18