Image Cropping and Scaling Algorithm using linear algebra
THE SCENARIO:
I had to formulate an algorithm to convert an image of some resolution - say L x M and
crop / re-size the image into a new resolution say P x R such that I cover the maximum amount
of points/pixels from the original image.
APPLICATION:
This can be pretty much applied in a generic way to all programs and websites in need of an optimized algorithm to rescale / reduce the size of the original image in their application such as profile images in social networks etc.
THE APPROACH:
To cover the maximum amount of pixels from the original image we have to focus on cropping the image
to the target aspect ratio first and then re-scaling it to the new resolution. Hence, the problem comes down to achieving the target aspect ratio that would help me capture the maximum amount of pixels of the original image so that I end up with an image which is pretty close to what the original image should have been in the new resolution.
DETAILS:
The signature of the function before we started writing the algorithm:
def generate_image_aspect_ratio(path, old_res, new_res=None):
pass
Moving to a new aspect ratio was basic maths, so I formulated the equation which would
give me a new resolution with the same aspect ratio viz:
(old_x - X) / (old_y - Y) = new_x / new_y ...(i)
where:
old_x * old_y = resolution of the original image
new_x * new_y = target resolution
X = the amount of pixels or points that should be cropped off via the x axis to achieve the target resolution
Y = the amount of pixels or points that should be cropped off via the y axis to achieve the target resolution
hence:
old_x / old_y = aspect ratio of the source
new_x / new_y = target aspect ratio
Now we have 2 variables X and Y that we need to minimize so that the highest amount
of pixels are captured from the original image.
The first thing I thought of to minimize these variables was to use differentiation,
but since equation is linear and it did not make sense to put dY/dX = 0 and get the maxima or minima.
One thing I observed here was the values of X of Y should be positive since we
cannot exceed the number of pixels of the original resolution.Hence if we plot a
graph or Y to X, the values we'd minimize would lie in the first quadrant (bulb lights up!):
Rearranging equation (i) to form the equation of a straight line:
Y = (new_y/new_x)X + (old_y - old_x*new_y/new_x) ...(ii)
analoguous to the equation of the straight line
Y = mX + c ...(iii)
where:
m = slope of the line = new_y/new_x ...(iv)
c = Y intercept of the line when X --> 0 = old_y - old_x *new_y/new_x ...(v)
Notice the slope of the line is always positive as new_y/new_x is always positive.
Hence the line would be at an acute angle to the positive x axis.
The Y intercept i.e. c is therefore the deciding factor on whether X should be zeroed
or Y so that both X and Y are positive.
Thus if:
c >= 0 we get the positive minimum value of Y = c at X = 0
and
c < 0 we get a positive minimum value of X = -c/m at Y = 0
So, once we have positive mimimum values of X and Y, we can crop the image to
the resolution (old_x - X) * (old_y -Y) which is of the exact/similar aspect ratio
of new_x/new_y.
The next step that follows is re-sizing the image to the resolution new_x * new_y.
This algorithm works for all scenarios viz old_x > new_x or old_x <= new_x or old_y > new_y
or old_y <= new_y. Using this algorithm reduces the number of comparisons to just one variable
that is the Y intercept c and also makes the computations easy.
The code would be published in an EDIT, request for the code via email or in comments.
Θ Ω Sushant ♂
