Skip to main content

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 ♂

Comments

  1. Why dont you put your code out? Since it came out in HN. You may get more accurate algos

    ReplyDelete
  2. This is so amazing man :-)

    ReplyDelete
  3. This is still amazing !

    ReplyDelete

Post a Comment

Popular posts from this blog

Startup founders cheatsheet (Chief product officer)

Define your goals  The basic definition of "mission" and "vision" of the company is critical when we've past the stage of experimenting with the startup's model and helps you prioritise better. From the Expedia page it looks like this: "Our Mission is to Revolutionise Travel Through the Power of Technology", in this case, it is also helping the company know that leveraging and scaling with "technology" is imperative for the company (along with operations). 
Set 2-3 basic targets for the next 2-3 months (possibly 6 months) These might be pretty standard and should align with the mission / vision of the company. If your company wants to be the #1 company in Asia for travel, these basic targets might be: Scale to 100,000 app downloads across platformsIncrease revenue by 15%Increase daily unique visitors to 3 times the current value 
Image Source: Mind the product
Goals help define epics and create a huge backlog Now brainstorming how the targe…