How can I deform an image to fit a shape, but keep the same pixel values?

Hi everybody,

I have an image region which has an irregular shape (a polygon with no holes). I have a second region with a different shape but this will always have the exact same number of pixels (again, a polygon with no holes).

I want to deform the image to fit into the second region, I want the structure of the image to stay the same as far as possible but I also want all the pixel values to be reused in the new region, I do not want new pixel values to be created, so I can't use interpolation. As far as I can tell, Matlab doesn't have an image transformation algorithm which works without interpolation in this way.

My first thought is to calculate the distance and angle of each pixel relative to the image centroid, then assign pixels to their distance/angle nearest neighbor in the second region. However, finding nearest neighbors is quite slow, I feel like this is a brute force approach and there may be a more elegant solution I have missed?

For example, if we imagine that each pixel was attached to its surrounding neighbors by elastic, we could ask how the image can be deformed to fit inside the second region while minimising the amount of 'tension' in the elastic. I know things like this exist for other purposes but can't really find something equivalent for images.

Any suggestions or help would be greatly appreciated.

Answer 1

[DGM]

For the moment I'm going to assume that the input and output polygons have the same number of vertices or can be made to have the same number of vertices by some means of making neighboring edges colinear where necessary.

% an image
inpict = imread('blacklight2.jpg');

% these points describe a polygon
boxm = [183.4 251.2; 133.4 402.8; 217.3 463.5; 320.7 483.1; 390.3 286.8; 285 252.9]; % [x y]

% assert that this is where they're supposed to be
boxf = [843.4 459.9; 679.3 443.8; 616.9 563.4; 661.5 690; 806 709.6; 900.5 565.1]; % [x y]

% for sake of clarity, show these polygons over the image
imshow(inpict,'border','tight'); hold on
plot(boxm(:,1),boxm(:,2),'y','linewidth',2)
plot(boxf(:,1),boxf(:,2),'r','linewidth',2)

% deform the image using nearest-neighbor interpolation
TF = fitgeotrans(boxm,boxf,'pwl');
outview = imref2d(size(inpict));
outpict = imwarp(inpict,TF,'fillvalues',0,'interp','nearest','outputview',outview);

% again, draw the polygons for reference
imshow(outpict,'border','tight'); hold on
plot(boxm(:,1),boxm(:,2),'y','linewidth',2)
plot(boxf(:,1),boxf(:,2),'r','linewidth',2)

I could probably come up with a better image to work with, but I'm in the middle of something. I might come back to this, but even if I don't, I think it's fairly apparent that the image has been altered in an understandable manner given the position and orientation of the two hexagons.

Note that the entire image is deformed, even regions outside the cage. If it's desired to extract the region inside the initial polygon and then move it alone to the destination polygon, that can be done by using the vertex lists to generate at least one polygonal mask (e.g. poly2mask()) and then doing simple logical composition between the source and destination images as the intended result requires.

[Neurolab]

I'm aware of the fitgeotrans > imref2d > imwarp pipeline, but unfortunately I do not want to create values through interpolation, I want to rearrange the set of existing pixels into the new shape (the starting image and target region always have the exact same number of pixels). I don't think there is an algorithm which fits this pipeline and that works without interpolation?

[DGM]

Oh good gravy. I don't know how I missed that. I read the constraint as "maintain a fixed set of possible colors", not "maintain a fixed population of pixels".

If area is assured to be constant and the shape doesn't get silly (no holes or self-intersection), it seems do-able, but I don't know of something off the top of my head that would make it convenient to do.

As to whether there's an elegant way, I'm generally not the one to ask. The closest I've done is a useless unidirectional sifting filter that's naive and slow.

Answer 2

[Image Analyst]

You cannot do it without "new" pixel values being interpolated especially if you enlarge the region. For example if the source region is a million pixels and the destination region is two million pixels and you use ONLY the original million pixels, then there will be a million "unassigned" pixels, which may show up as dots or holes in your destination image. If by "new" pixel values you meant values not in the original image, then some interpolation routines let you specify 'nearest' so that it will use the nearest existing pixel value rather than interpolating a new value.

Conversely if the destination region is smaller, you'd have to "throw away" pixels to make it fit into the new, smaller shape.

To warp an image see imwarp or see Steve's blog:

Spatial transformations Defining and applying custom transforms Steve on Image Processing

[Neurolab]

The image and the region will always both have exactly the same number of pixels, so the problem can be thought of as how to rearrange the pixels of the image to fit the new shape and I want to do this without interpolation.

I realize I can interpolate using nearest neighbors, and this would not create new values, but some values may be excluded or duplicated and for statistical reasons I would like the exact same set of pixels used.

Maybe something similar to elastic deformation: https://elasticdeform.readthedocs.io/en/latest/README.html where pixels are moved using displacement vectors. The problem is that these implementations, like the one in that link, also use interpolation, so the resulting image does not necessarily have the same pixel values as the original.

[Image Analyst]

It sounds like you're talking about the Fixed Point Theorem

https://en.wikipedia.org/wiki/Fixed-point_theorem

An example is if you had a milky film on the top of your coffee in a mug and then you stirred it. The white particles would just rearrange themselves. The theorem says that there will always be one point that remains in the same place.

I don't know how to do this in MATLAB and of course it depends on the function or movement vectors for each point.

Why can't you just do a regular rubber sheet stretch like imwarp does? What's wrong with that?

[Neurolab]

I did start by using the nearest neighbor (where nearest equals the pixel location in the second region with the closest distance and angle from the region's centroid). With this method the pixels surrounding the centroid often remain the same, acting as a fixed-point, while distal pixels are the ones that tend to move around the most. This is fine for my purposes, it is just a bit slow and a bit of a brute force approach.

The problem with imwarp and interpolation is that I am doing this process as part of a statistical test. I want to measure a structural phenomenon in the image and then calculate the statistical likelihood of this occuring by chance. As part of the project I'm working on, what we want to do is segment the original image based on the structure we are interested in, create a new image where these segments have been assigned new, random positions and then assess the structure in the new image. After doing this 1000 times we will generate a null distribution for the original image and can say if the structure is statistically significant or not. Interpolation will intrododuce new pixel values, which changes the statistical propoerties of the image (mean, standard devation, min, max etc) and also makes assumptions about the image properties (linear, bilinear, spline etc), which we want to avoid.

[Matt J]

It is dubious to attach importance to discrete image properties like the number of pixels in a certain region. The pixelization of an image is, after all, an artificial way of representing an object that is continuous. If you captured the image with the same object in a different position or orientation. The number of pixels covering the region would change.

[Neurolab]

The 'images' I'm working with are actually bivariate histograms of point data, so the 'pixels' (bins) do have a statistical meaning.