4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – Ash
    Commented Mar 9, 2022 at 16:59
  • $\begingroup$ 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. $\endgroup$
    – Thomas
    Commented Mar 9, 2022 at 17:12
  • $\begingroup$ 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. $\endgroup$
    – Thomas
    Commented Mar 9, 2022 at 17:45
  • $\begingroup$ 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. $\endgroup$
    – Ash
    Commented Mar 10, 2022 at 17:23
  • $\begingroup$ 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. $\endgroup$
    – Thomas
    Commented Mar 10, 2022 at 17:39

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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... $\endgroup$
    – Thomas
    Commented Mar 11, 2022 at 13:57
  • $\begingroup$ 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 ? $\endgroup$
    – Thomas
    Commented Mar 11, 2022 at 14:04
  • $\begingroup$ @Thomas, I meant that in the "growing" phase of the super pixel we'll limit its growing to a rectangle shape. $\endgroup$
    – Royi
    Commented Mar 11, 2022 at 16:48
  • $\begingroup$ 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. $\endgroup$
    – Thomas
    Commented Mar 11, 2022 at 16:56
  • $\begingroup$ 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 ? $\endgroup$
    – Thomas
    Commented Mar 11, 2022 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.