How to segment a matrix into N regions with sizes XYZ?

Hi everyone,

I have a matrix (i.e. 100 x 100, but the shape may vary) and I want to segment it into contiguous regions with specific numbers of elements. So for example 3 contiguous regions, with sizes equal to 2450, 3350 and 4200 elements. As if the matrix had been segmented by k-means but into regions with these exact areas.

Ideally I would also like have some control over roughly where these regions are formed around (i.e. I would like to give 3 points, one of which must be contained within each region), but this is not so important.

This is part of an image segmentation process where we detect N segments in an image and want to recreate a facsimile image with the same number of segments with the same areas.

I have coded an iterative process which starts with N starting points and adds elements to each one consequtively until the whole image is filled, but this is not fast enough and also does not replicate the original segments very well.

I could assign values to a matrix (i.e. 2450 1s, 3350 2s, 4200 3s) based on linear indices but then the resulting segments would be very blocky and may not be contiguous. I could assign these values to random positions and then iteratively move them to congregate around specific points, but that would likely also be a slow process.

Is there such a thing as a 2D topographical sorting algorithm?

Thanks for any help.

[Rik]

Should the areas be rectangular, or can they be any shape as long as they are contiguous and the specified size?

[Neurolab]

No, in fact they should probably not be rectangular. The original images we are trying to replicate are segmented based on a nearest neighbor approach, so the regions look like the sort of facets that would be produced by k-means clustering. Here is an example:

I want to make a new image, with regions with similar properties and identical areas but in different places.

[Matt J]

Why not just apply a random area-preserving transformation to the image, like a random rotation or shear?

[Neurolab]

I'm not sure how to do an area-preserving transformation in Matlab... do you know what I should look into for that?

[Matt J]

I'm not sure how to do an area-preserving transformation in Matlab

See imwarp.

[Neurolab]

I have researched down this path before but did not find anything helpful. imwarp is not an area-preserving transformation, it is a way to apply transformations, and I dont know of any area-preserving transformations in Matlab's library.

Also, as far as I know, regardless of the transformation imwarp always uses some form of interpolation, so the regions in the output image will not have the same areas as the input - even nearest neighbor interpolation may repeat or omit values from the input image.

[Matt J]

Translations, rotations, and affine shearings all preserve area.

[Neurolab]

Yes, but these transformations do not solve my issue:

I want to make a new image with the same dimensions, the same number of regions, with the same surface areas, but with different shapes and/or in different places.

This is an example generated using the slow algorithm I described before:

This algorithm has some issues, in addition to being slow, because the areas are 'grown' from seed points they sometimes end up split (like the orange region). These regions also do not have straight sides like the ones in the first image, so it is not really a good replication of the regions.

An affine transformation on the first image above will result in something with a different shape. Rotating the image does not work for my purposes as I'm interested in the segments within the image, the rotation of the image is not important, same with a tenslation of the image.

An affine transformation/rotation/translation on the regions in the image above will change their shape, but then they will not fit together.

[Matt J]

Can you not introduce a surrounding squish region whose area you would allow to change? Affine transformations can be designed that preserve straight lines, area, and boundary continuity (so most of the properties you've mentioned) but forcing them also to respect the same rectangular image boundaries is probably a tall order.

[Neurolab]

No, unfortunately not.

Answer 1

[Pratik]

Hi Neurolab,

As per my understanding, you want to segment a matrix into N regions with predetermined sizes. You have few approaches for the same and a common issue with them is the speed of the algorithm.

Segmenting a matrix into contiguous regions with specific sizes is an interesting challenge, particularly if you want to control where the regions form. There is no built-in function in MATLAB as of now that can do this.

For an efficient solution, you might consider implementing your algorithm in a compiled language like C++ and call it from MATLAB using a MEX-function.

Please refer to the following documentation for more information on creating high-performance functions, implemented in modern C++, that can be called from MATLAB:

www.mathworks.com/help/matlab/cpp-mex-file-applications.html

Also, documentation about best practices for using MEX Functions to Accelerate MATLAB Algorithm can be referred:

www.mathworks.com/help/coder/ug/best-practices-for-using-mex-functions-to-accelerate-matlab-algorithms.html

I hope this helps!