Thursday, April 5, 2012

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 ♂

16 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
  4. The sensor dust and other crud on your camera's sensor are most visible on images taken at small apertures or those taken on plain areas such as the sky. Hence you should use the Healing Brush to get rid of the dust spots on the photo.click reference

    ReplyDelete
  5. I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post. Compress JPEG Images Online

    ReplyDelete
  6. A compelling technique is to take your variable based math books and record every one of the conditions and ideas in a sheet of paper. Keep every idea on an alternate sheet. long division

    ReplyDelete
  7. Thanks for a very interesting blog. What else may I get that kind of info written in such a perfect approach? I’ve a undertaking that I am simply now operating on, and I have been at the look out for such info. power washing

    ReplyDelete
  8. Thanks for a very interesting blog. What else may I get that kind of info written in such a perfect approach? I’ve a undertaking that I am simply now operating on, and I have been at the look out for such info. water softener systems

    ReplyDelete
  9. Trigonometric calculators assist discover values of trigonometric capabilities. (Does "sohcahtoa" ring a bell?) All you need to do is input the perspective or radian cost and the calculator spits out the values of trig capabilities primarily based totally for your inputs.

    ReplyDelete
  10. Students of mathematician are so happy from your post. You make easy for them to cropping and scaling the image. So, I am providing to them Furnace Repair Services In Richland Hills TX. They can enjoyed own day happily.

    ReplyDelete
  11. In any case, you either 1.) let the picture outline run constantly or 2.) you turn off it when you're not utilizing it - which is more often than not, in this way abhorring your edge and afterward you'll forget about it.jpg-compress.com

    ReplyDelete
  12. This comment has been removed by the author.

    ReplyDelete
  13. These days, images are expected for a grouping of reasons, starting with applying for a global ID or an occupation or making a profile on a dating site. clipping path company

    ReplyDelete
  14. One of the most popular adventure activities in Russia is hiking, with the country's many mountain ranges providing ample opportunities for treks of varying difficulty levels. The Caucasus Mountains in the south of Russia, for example, offer stunning vistas and challenging trails, while the Altai Mountains in Siberia are renowned for their natural beauty and unique cultural experiences. Russia’s Adventure

    ReplyDelete
  15. Time and cost are the conspicuous reasons for ignoring photo necessities, however the genuine guilty party is the absence of information about the requirements and the open doors that exist for quality creation stills.
    amazon photo editing service

    ReplyDelete
  16. "The potential for AI to assist artists in their creative process is exciting." ai image generator

    ReplyDelete

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...