imgtools logo Imgtools - manipulate Tk photo images

Home

Documentation

Download / Install

Development

The math behind it

Links

The math behind image transformations

On this page we present some of the math behind image transformations.

It is by no means a complete guide on image processing. It is just a collection of some aspects that were not obvious to figure out. For my own reference and for everyone interested in the topic.

Overview

Very short overview how scaling and rotating images is done:

  1. Determine the size of the destination image
  2. Calculate values for each pixel of the destination image:
    1. Apply coordinate translation, i.e. find out the position of the destination pixel relative to the source image.
    2. Calculate the values for the destination pixel, interpolating from the surrounding source pixels

Top

Rotation: Size of destination image

When rotating an image, the size of the destination image is not given. There are different approaches to determine that size. We are going to have a closer look at three of them (those available in imgtools), but there are yet other approaches not mentioned here.

Top

Keep size

Make the destination image the same size as the original one. Unless the angle of rotation is a multiple of 180°, there will be empty areas in the resulting image and, at the same time, not all of the source image will be visible.

From the mathematical point of view, this is the simplest variant for sure. There's nothing to calculate!

Top

No clipping

With this approach, we make the destination image large enough to contain all of the source image. This implies that the blank areas can become a considerable portion of the image.

This rotation method looks like this:

drawing on finding size of destination image

The dashed rectangle represents the rotated source image, the outer one is our destination image. θ is the angle of rotation, w s and h s are the width and height of the source image respectively. w d and h d are the sizes of the destination image - the sizes we need to calculate.

Let's see how we can calculate them:

Calculate a , b , c and d : ̲ a = w s cos ( θ ) b = h s sin ( θ ) c = w s sin ( θ ) d = h s cos ( θ ) Now for w d and h d : ̲ w d = a + b w d = w s cos ( θ ) + h s sin ( θ ) h d = c + d h d = w s sin ( θ ) + h s cos ( θ ) alignl underline {"Calculate" `a, b, c` "and" `d:} newline a = w_s cos(%theta) newline b = h_s sin(%theta) newline c = w_s sin(%theta) newline d = h_s cos(%theta) newline newline alignl underline {"Now for" `w_d` "and" `h_d:} newline w_d = a+b newline bold { w_d = w_s cos(%theta) + h_s sin(%theta) } newline newline h_d = c+d newline bold { h_d = w_s sin(%theta) + h_s cos(%theta) } newline newline

There is a problem with the formula above, though: it is valid only for the interval 0° ≤ θ ≤ 90°. For greather values of θ we get slightly different formulas (the derivation of these formulae is left as an excercise for the reader :-)):

For 90° θ 180° ̲ w d = w s ( cos ( θ ) ) + h s sin ( θ ) h d = w s sin ( θ ) + h s ( cos ( θ ) ) For 180° θ 270° ̲ w d = w s ( cos ( θ ) ) + h s ( sin ( θ ) ) h d = w s ( sin ( θ ) ) + h s ( cos ( θ ) ) For 270° θ 360° ̲ w d = w s cos ( θ ) + h s ( sin ( θ ) ) h d = w s ( sin ( θ ) ) + h s cos ( θ ) alignl underline { "For 90°" <= %theta <= "180°"} newline w_d = w_s (-cos(%theta)) + h_s sin(%theta) newline h_d = w_s sin(%theta) + h_s (-cos(%theta)) newline newline alignl underline { "For 180°" <=%theta<="270°"} newline w_d = w_s (-cos(%theta)) + h_s (-sin(%theta)) newline h_d = w_s (-sin(%theta)) + h_s (-cos(%theta)) newline newline alignl underline { "For 270°" <=%theta <= "360°"} newline w_d = w_s cos(%theta) + h_s (-sin(%theta)) newline h_d = w_s (-sin(%theta)) + h_s cos(%theta) newline

The difference between the formulae is only in the negation of the sin() and cos() values for some cases. Negation occurs exactly in those intervals where the corresponding function is negative. This means that we always get positive values for +/-sin(θ) and +/-cos(θ), which is handy, since negative distances are kinda hard to handle ;-).

It also means that we can derive a one-for-all formula:

w d = w s | cos ( θ ) | + h s | sin ( θ ) | h d = w s | sin ( θ ) | + h s | cos ( θ ) | bold {w_d = w_s abs { cos(%theta) } + h_s abs { sin(%theta) } } newline newline bold {h_d = w_s abs { sin(%theta) } + h_s abs { cos(%theta) } }

Top

No blank areas

Clip away all blank areas: make the the destination image small enough so there are no blank areas, yet try to make the destination image as large as possible. For angles of rotation that are not a multiple of 90°, portions of the source image will not be visible in the destination image.

This means that we have to inscribe a rectangle into the rotated source, such that each of its corners touches a side of the source rectangle.

All clipping size drawing

The image above shows the rotated source rectangle (green, dashed lines) and the destination rectangle we have to calculate (blue lines). w s and h s are the width and height of the source image, w d and h d are the dimensions of the destination image. a, b, c and d are distances needed in the equations below.

And here's some math!

a , b , c and d are: ̲ a = h d sin ( θ ) b = w d cos ( θ ) c = w d sin ( θ ) d = h d cos ( θ ) We have: ̲ { w s = a + b h s = c + d { w s = h d sin ( θ ) + w d cos ( θ ) h s = w d sin ( θ ) + h d cos ( θ ) { w d cos ( θ ) = w s h d sin ( θ ) h d cos ( θ ) = h s w d sin ( θ ) { w d = w s cos ( θ ) h d sin ( θ ) cos ( θ ) h d = h s cos ( θ ) w d sin ( θ ) cos ( θ ) In each equation substitute w d or h d from the other ̲ { w d = w s cos ( θ ) ( h s cos ( θ ) w d sin ( θ ) cos ( θ ) ) sin ( θ ) cos ( θ ) h d = h s cos ( θ ) ( w s cos ( θ ) h d sin ( θ ) cos ( θ ) ) sin ( θ ) cos ( θ ) { w d w d sin 2 ( θ ) cos 2 ( θ ) = w s cos ( θ ) h s sin ( θ ) cos 2 ( θ ) h d h d sin 2 ( θ ) cos 2 ( θ ) = h s cos ( θ ) w s sin ( θ ) cos 2 ( θ ) { w d cos 2 ( θ ) sin 2 ( θ ) cos 2 ( θ ) = w s cos ( θ ) h s sin ( θ ) cos 2 ( θ ) h d cos 2 ( θ ) sin 2 ( θ ) cos 2 ( θ ) = h s cos ( θ ) w s sin ( θ ) cos 2 ( θ ) With: ̲ cos 2 ( α ) sin 2 ( α ) = cos ( 2 α ) { w d = w s cos ( θ ) h s sin ( θ ) cos 2 ( θ ) cos 2 ( θ ) cos ( 2 θ ) h d = h s cos ( θ ) w s sin ( θ ) cos 2 ( θ ) cos 2 ( θ ) cos ( 2 θ ) { w d = w s cos ( θ ) h s sin ( θ ) cos ( 2 θ ) h d = h s cos ( θ ) w s sin ( θ ) cos ( 2 θ ) alignl underline { a, b, c` "and" `d` "are:"} newline a = h_d sin(%theta) newline b = w_d cos(%theta) newline c = w_d sin(%theta) newline d = h_d cos(%theta) newline newline alignl underline {"We have:"} newline left lbrace binom {w_s = a + b} {h_s = c + d} right none newline left lbrace binom {w_s = h_d sin(%theta) + w_d cos(%theta)} {h_s =w_d sin(%theta) +h_d cos(%theta)} right none newline left lbrace binom {w_d cos(%theta)= w_s - h_d sin(%theta)} {h_d cos(%theta) = h_s - w_d sin(%theta)} right none newline left lbrace binom {w_d = w_s over {cos(%theta)} - h_d {sin(%theta)} over {cos(%theta)} } {h_d = h_s over {cos(%theta)} - w_d {sin(%theta)} over {cos(%theta)}} right none newline newline alignl underline {"In each equation substitute" `w_d` "or" `h_d` "from the other" } newline left lbrace binom { w_d = w_s over {cos(%theta)} - left ( h_s over {cos(%theta)} - w_d {sin(%theta)} over {cos(%theta)}right ) { sin(%theta)} over {cos(%theta)}} { h_d = h_s over {cos(%theta)} - left ( w_s over {cos(%theta)} - h_d {sin(%theta)} over {cos(%theta)} right ) {sin(%theta)} over {cos(%theta)}} right none newline left lbrace binom {w_d - w_d {sin^2(%theta)} over {cos^2(%theta)} = w_s over {cos(%theta)} - h_s {sin(%theta)} over {cos^2(%theta)} } {h_d - h_d {sin^2(%theta)} over {cos^2(%theta)} = h_s over {cos(%theta)} - w_s {sin(%theta)} over {cos^2(%theta) }} right none newline left lbrace binom { w_d {cos^2(%theta) - sin^2(%theta)} over {cos^2(%theta)} = {w_s cos(%theta) - h_s sin(%theta) } over {cos^2(%theta)} } {h_d {cos^2(%theta) - sin^2(%theta)} over {cos^2(%theta)} = {h_s cos(%theta) - w_s sin(%theta) } over {cos^2(%theta)} } right none newline newline alignl underline { "With:"} `cos^2(%alpha) - sin^2(%alpha) = cos(2%alpha) newline left lbrace binom { w_d = {w_s cos(%theta) - h_s sin(%theta) } over {cos^2(%theta)} cdot { {cos^2(%theta)} over {cos(2%theta)}} } { h_d = {h_s cos(%theta) - w_s sin(%theta) } over {cos^2(%theta)} cdot { {cos^2(%theta)} over {cos(2%theta)}} } right none newline left lbrace bold {binom { w_d = {w_s cos(%theta) - h_s sin(%theta) } over {cos(2%theta)}} { h_d = {h_s cos(%theta) - w_s sin(%theta) } over { cos(2 %theta) } } } right none newline

As for the "no clipping" method, these formulas are valid only in the interval [0°, 90°]. To find a formula that's valid for all angles, we can figure out the other three, just as we did above, and then derive the "grand equation". Long story short, here it is:

w d = w s | cos ( θ ) | h s | sin ( θ ) | cos ( 2 θ ) h d = h s | cos ( θ ) | w s | sin ( θ ) | cos ( 2 θ ) bold {w_d = {w_s abs {cos(%theta)} - h_s abs { sin(%theta) } } over {cos(2%theta)}} newline newline bold {h_d = {h_s abs { cos(%theta) } - w_s abs { sin(%theta) } } over {cos(2 %theta)}}

They even look similar to the "no clipping" ones, they must be correct, right?

Uhm, let's try it out. Say we have a source image of size 800x600, and we rotate it by 10°. We get a destination image of 728x481 (rounded values) - looks good.

Another try: same image, but this time we rotate it by 40°. Ouch! The result is 1308 by -314. A negative height can't be right! And the width is way too large - not good either. So what's wrong?

We didn't say so, but we assumed that there always is a rectangle that fits into our rotated source and touches its sides with all four corners. This assumption, alas, is wrong.

All clipping size drawing 2

As we can see from the graphic, the destination image gets narrower with growing angle. At some point, our destination rectangle will be just a line that goes from one corner of the source to the opposite one. Past that point, there's no way to draw a rectangle that fits our requirements. If we keep rotating, at some point we will get a valid result again.

The limits for valid results are the angles formed by the diagonal of the source rectangle and its sides. For 0° ≤ θ ≤ 90° our formulas give valid results if:

θ < arctan ( a b ) θ > arctan ( b a ) ( means "or" ) Where a is the smaller value of w s and h s and b is the larger value of w s and h s %theta < arctan(a over b) or %theta > arctan(b over a) newline alignr "(" or` "means \"or\" )" newline "Where" `a` "is the smaller value of" ` w_s ` "and" ` h_s newline "and" `b` "is the larger value of" `w_s` "and" `h_s newline

Obvously, the requirement that destination touches source with all four corneres does not work - looks like we need to take another approach. What if only two corners of the destination image must touch source edges and the other two must be inside it? With that we face another problem, though: we won't get a unique result. For any combination of width, height and angle, there is an infinite number of rectangles that meet our requirements.

If we add the condition that the area of our destination image must be maximised, we might get a good result. This requirement makes perfect sense - after all we want to keep as much as possible of the original image!

As a first step we need to find a way to express h d in terms of w d (it could be the other way around as well). We begin with a graphical representation of the problem:

All clipping size drawing 3

We can see that the destination rectangle must touch the longer sides of source. If it touches the shorter sides, it will not be completely inscribed in source. This means that what we are going to find out next, is valid only if w s < h s . As usual, for this first step, we consider the interval 0° ≤ θ ≤ 90° for the angle.

The distances a , b , c and d are: ̲ a = w d tan ( θ ) = w d sin ( θ ) cos ( θ ) b = w d cos ( θ ) c = w s b = w s w d cos ( θ ) d = c sin ( θ ) = ( w s w d cos ( θ ) ) 1 sin ( θ ) = w s sin ( θ ) w d sin ( θ ) cos ( θ ) d = w s cos ( θ ) w d sin ( θ ) cos ( θ ) Now we can express h d in terms of w d : ̲ h d = a + d h d = w d sin ( θ ) cos ( θ ) + w s cos ( θ ) w d sin ( θ ) cos ( θ ) h d = w d sin 2 ( θ ) + w s cos ( θ ) w d sin ( θ ) cos ( θ ) h d = w d [ 1 sin 2 ( θ ) ] + w s cos ( θ ) sin ( θ ) cos ( θ ) With: ̲ 1 sin 2 ( α ) = cos 2 ( α ) h d = w d [ cos 2 ( θ ) ] + w s cos ( θ ) sin ( θ ) cos ( θ ) h d = cos ( θ ) ( w s w d cos ( θ ) ) sin ( θ ) cos ( θ ) h d = w s w d cos ( θ ) sin ( θ ) alignl underline {"The distances" `a, b, c` "and" `d` "are:"} newline a = w_d tan(%theta) = w_d {sin(%theta)} over {cos(%theta)} newline b = w_d over {cos(%theta)} newline c = w_s - b = w_s - w_d over {cos(%theta)}newline d = c over {sin(%theta)} = left (w_s - w_d over {cos(%theta)} right) cdot {1 over {sin(%theta)}} = w_s over {sin(%theta)} - w_d over {sin(%theta)cos(%theta)} newline d= {w_s cos(%theta) - w_d} over {sin(%theta) cos(%theta)} newline newline alignl underline {"Now we can express" `h_d` "in terms of" `w_d":"} newline h_d = a + d newline h_d = w_d{sin(%theta)}over {cos(%theta)} + {w_s cos(%theta) - w_d} over {sin(%theta) cos(%theta)} newline h_d = {w_d sin^2(%theta) + w_s cos(%theta) - w_d} over {sin(%theta) cos(%theta)} newline h_d = {-w_d left [ 1-sin^2(%theta) right ] + w_s cos(%theta)} over {sin(%theta)cos(%theta)} newline newline alignl underline {"With:"} `1-sin^2(%alpha) = cos^2(%alpha) newline h_d = {-w_d left[cos^2(%theta) right] + w_s cos(%theta)} over {sin(%theta)cos(%theta)} newline h_d = {cos(%theta)(w_s -w_d cos(%theta))} over {sin(%theta)cos(%theta)} newline h_d = {w_s -w_d cos(%theta)} over {sin(%theta)} newline

If we repeat this operation for the other three quadrants, we can determine a formula that's valid for any value of θ:

h d = w s w d | cos ( θ ) | | sin ( θ ) | bold { h_d = {w_s - w_d abs { cos(%theta)}} over {abs{sin(%theta)}}}

With that, we can express the area of the destination image as a function of w d . As it tunrs out, it's a quadratic function with negative a, which means it has a maximum and we can calculate the value of w d and h d at this maximum.

Express the area of destination as a function s ( w d ) s = w d h d s = w d w s w d | cos ( θ ) | | sin ( θ ) | s = | cos ( θ ) | | sin ( θ ) | w d 2 + w s | sin ( θ ) | w d The maximum of a quadratic function can be found at: x max = b 2 a Ergo, the width for which destination has maximal area is: w d = w s | sin ( θ ) | 1 2 ( | cos ( θ ) | | sin ( θ ) | ) w d = w s | sin ( θ ) | ( | sin ( θ ) | 2 | cos ( θ ) | ) w d = w s 2 | cos ( θ ) | This allows us to calculate h d as well: h d = w s w d | cos ( θ ) | | sin ( θ ) | h d = w s | sin ( θ ) | w s 2 | cos ( θ ) | | cos ( θ ) | | sin ( θ ) | h d = 2 w s w s 2 | sin ( θ ) | h d = w s 2 | sin ( θ ) | alignl "Express the area of destination as a function" `s_(w_d) newline s = w_d cdot h_d newline s = w_d {w_s -w_d abs{cos(%theta)}} over abs{sin(%theta)} newline s = -{abs{cos(%theta)} over abs{sin(%theta)}}{w_d}^2 + w_s over abs{sin(%theta)}w_d newline newline alignl "The maximum of a quadratic function can be found at:" newline x_max = -b over {2a} newline alignl "Ergo, the width for which destination has maximal area is:" newline w_d = -{w_s over abs{sin(%theta)}} cdot {1 over {2 left( -{ abs{cos(%theta)} over abs{sin(%theta)}} right) } } newline w_d = -{w_s over abs{sin(%theta)}} cdot left ( - { abs{sin(%theta)} over {2 abs{cos(%theta)}}} right ) newline bold { w_d = w_s over {2 abs{cos(%theta)}}} newline newline alignl "This allows us to calculate" `h_d` " as well:" newline h_d = {w_s -w_d abs{cos(%theta)}} over abs{sin(%theta)} newline h_d = w_s over abs{sin(%theta)} - {w_s over {2 abs{cos(%theta)}}} cdot {abs{cos(%theta)} over abs{sin(%theta)}} newline h_d = {2 w_s - w_s} over {2 abs{sin(%theta)}} newline bold {h_d = w_s over {2 abs{sin(%theta)}}} newline

As stated before, this formula works only if w s < h s . For the case where w s > h s we get similar formulas:

h d in terms of w d for h s < w s ̲ h d = h s w d | sin ( θ ) | | cos ( θ ) | This gives us: ̲ w d = h s 2 | sin ( θ ) | h d = h s 2 | cos ( θ ) | alignl underline {h_d` "in terms of" `w_d` "for" `h_s < w_s} newline h_d = {h_s - w_d abs { sin(%theta)}} over {abs{cos(%theta)}} newline newline alignl underline {"This gives us:"} newline bold { w_d = h_s over {2 abs{sin(%theta)}}} newline bold { h_d = h_s over {2 abs{cos(%theta)}}} newline

Is that it? Do these formula always give us valid results? Nope. Consider this:

All clipping size drawing 4

Turns out that the maximise-area approach works well if the angle is close to 45°. As we go towards 0° or 90°, at some point the destination rectangle reaches out of source!

Consider the point just before the destination image with maximised area starts becoming too large. In the example above, that's at about 17.26°. At this point, destination touches source with all four corners. Sounds familiar? Right, we've calculated that already. Looks like that effort was not vain, after all! Notice that there is another similar "turning point" somewhere between 45° and 90°, and two more in each of the other quadrants.

We are getting close to the solution for our problem. For angles between 0° and the first turning point, we well use the 4-corners approach we explored before. Between the turning points, the 2-corners-with-maximised-surface approach will give us a good result. After that, it's gonna be 4-corners again.

We have to figure out one last thing: where are these turning points?

For w s < w h and 0 ° θ 90 ° we have: ̲ 4 corners variant: w d = w s cos ( θ ) h s sin ( θ ) cos ( 2 θ ) 2 corners variant: w d = w s 2 cos ( θ ) The intersection point of the two functions is: ̲ w s 2 cos ( θ ) = w s cos ( θ ) h s sin ( θ ) cos ( 2 θ ) w s cos ( 2 θ ) = 2 cos ( θ ) ( w s cos ( θ ) h s sin ( θ ) ) w s cos ( 2 θ ) = 2 w s cos 2 ( θ ) 2 h s sin ( θ ) cos ( θ ) With: ̲ cos ( 2 α ) = cos 2 ( α ) sin 2 ( α ) w s [ cos 2 ( θ ) sin 2 ( θ ) ] = 2 w s cos 2 ( θ ) 2 h s sin ( θ ) cos ( θ ) 2 h s sin ( θ ) cos ( θ ) = 2 w s cos 2 ( θ ) w s cos 2 ( θ ) + w s sin 2 ( θ ) 2 h s sin ( θ ) cos ( θ ) = w s cos 2 ( θ ) + w s sin 2 ( θ ) With: ̲ cos 2 ( α ) + sin 2 ( α ) = 1 and: ̲ sin ( α ) cos ( α ) = 1 2 sin ( 2 α ) 2 h s 1 2 sin ( 2 θ ) = w s [ cos 2 ( θ ) + sin 2 ( θ ) ] h s sin ( 2 θ ) = w s 1 sin ( 2 θ ) = w s h s For any value of θ that beomes: ̲ | sin ( 2 θ ) | = w s h s And for w s > h s : ̲ | sin ( 2 θ ) | = h s w s alignl underline {"For" `w_s < w_h` "and" `0° <= %theta <= 90°` "we have:"} newline "4 corners variant:" `w_d = { w_s cos(%theta) - h_s sin(%theta) } over {cos(2%theta)} newline "2 corners variant:" `w_d = w_s over {2 cos(%theta)} newline newline alignl underline {"The intersection point of the two functions is:"} newline w_s over {2 cos(%theta)} = {w_s cos(%theta) - h_s sin(%theta) } over {cos(2%theta)} newline w_s cos(2 %theta) = 2cos(%theta)(w_s cos(%theta) - h_s sin(%theta)) newline w_s cos(2%theta) = 2 w_s cos^2(%theta) - 2 h_s sin(%theta)cos(%theta) newline newline alignl underline {"With:"} `cos(2%alpha) = cos^2(%alpha) - sin^2(%alpha) newline w_s[cos^2(%theta) - sin^2(%theta)] = 2 w_s cos^2(%theta) - 2 h_s sin(%theta)cos(%theta) newline 2h_s sin(%theta) cos(%theta) = 2 w_s cos^2(%theta) - w_s cos^2(%theta) + w_s sin^2(%theta) newline 2h_s sin(%theta) cos(%theta) = w_s cos^2(%theta) + w_s sin^2(%theta) newline newline alignl underline {"With:"} `cos^2(%alpha) + sin^2(%alpha) = 1 newline alignl underline {"and:"} `sin(%alpha)cos(%alpha) = 1 over 2 sin(2%alpha) newline 2h_s cdot {1 over 2 sin(2%theta)} = w_s[cos^2(%theta) + sin^2(%theta)] newline h_s sin(2%theta) = w_s cdot 1 newline sin(2%theta) = w_s over {h_s} newline newline alignl underline {"For any value of" `%theta` "that beomes:" } newline bold {abs {sin(2%theta)} = w_s over {h_s}} newline newline alignl underline {"And for"`w_s > h_s:} newline bold {abs {sin(2%theta)} = h_s over {w_s}} newline

Phew, that was some work. But we've got it now!

To sum it up: to find the dimensions for our destination image, we need first to find out on which side of those turning points we are. Depending on that, we will use either the 4-corners or the 2-corners variant. Formally, that would be:

Let r = a b Where a is the shorter side, b the longer side of the source image If | sin ( 2 θ ) | < r : ̲ w d = w s | cos ( θ ) | h s | sin ( θ ) | cos ( 2 θ ) h d = h s | cos ( θ ) | w s | sin ( θ ) | cos ( 2 θ ) If | sin ( 2 θ ) | r and w s < h s : ̲ w d = w s 2 | cos ( θ ) | h d = w s 2 | sin ( θ ) | If | sin ( 2 θ ) | r and w s h s : ̲ w d = h s 2 | sin ( θ ) | h d = h s 2 | cos ( θ ) | alignl "Let" `r = a over b` newline alignl "Where" `a` "is the shorter side," `b` "the longer side of the source image" newline newline alignl underline {"If" `abs {sin(2%theta)} < r :} newline bold {w_d = {w_s abs {cos(%theta)} - h_s abs{sin(%theta)} } over {cos(2%theta)}} newline bold { h_d = {h_s abs{ cos(%theta) } - w_s abs{ sin(%theta)} } over { cos(2 %theta) } } newline newline alignl underline {"If" `abs{sin(2%theta)} >= r` "and" `w_s < h_s:} newline bold { w_d = w_s over {2 abs{cos(%theta)}}} newline bold {h_d = w_s over {2 abs{sin(%theta)}}} newline newline alignl underline {"If" `abs{sin(2%theta)} >= r` "and" `w_s >= h_s:} newline bold { w_d = h_s over {2 abs{sin(%theta)}}} newline bold { h_d = h_s over {2 abs{cos(%theta)}}} newline

If we plot that, we get a pretty funny curve. Mountains!!

Mountains!

Top

Rotation and coordinate translation

Coordinate translation means to transform the coordinates of a point in the destination image to coordinates relative to the source image. To picture what that means, imagine to rotate the source image by θ degrees. Then lay the (not rotated) destination image over that. Now, take a needle and punch it through both images at the position we need to translate. Last, remove the needle and destination image and look where the needle punched the original image. The coordinages of that point in the source image are our translated coordinates. And it is from the source values at that point (and those near it) that we will calculate values for our destination pixel.

If we want to avoid all that needle punching and let our computer do the work instead, we need to express that in more algebraic terms. First, a drawing:

yet another drawing

We have two sets of coordinate axes here: the continuos lines are the axes of the destination image, the dashed lines the ones of the rotated source image.

P is a point for which we know the coordinates in destination. Those coordinates are the distances x d and y d . We need to find the coordinates in terms of source, x s and y s . While the origin for both coordinate systems is the same, the axes are rotated by θ degrees. That's why the source coordinates are going to be different.

Calculate a , b , c and d : ̲ a = x d tan ( θ ) = x d sin ( θ ) cos ( θ ) b = x d cos ( θ ) c = y d a = y d x d sin ( θ ) cos ( θ ) d = c sin ( θ ) = [ y d x d sin ( θ ) cos ( θ ) ] sin ( θ ) = y d sin ( θ ) x d sin 2 ( θ ) cos ( θ ) With that we can calculate x s ̲ x s = b + d x s = x d cos ( θ ) + y d sin ( θ ) x d sin 2 ( θ ) cos ( θ ) x s = x d x d sin 2 ( θ ) cos ( θ ) + y d sin ( θ ) x s = x d ( 1 sin 2 ( θ ) ) cos ( θ ) + y d sin ( θ ) With: ̲ 1 sin 2 ( θ ) = cos 2 ( θ ) x s = x d cos 2 ( θ ) cos ( θ ) + y d sin ( θ ) x s = x d cos ( θ ) + y d sin ( θ ) y s is a a little simpler: ̲ y s = c cos ( θ ) y s = [ y d x d sin ( θ ) cos ( θ ) ] cos ( θ ) y s = y d cos ( θ ) x d sin ( θ ) alignl underline {"Calculate" `a, b, c` "and" `d:} newline a = x_d tan( %theta ) = x_d { sin(%theta) } over { cos (%theta) } newline b = x_d over {cos(%theta)} newline c = y_d - a = y_d - x_d { sin(%theta) } over { cos(%theta) } newline d = c cdot sin( %theta) = left [ y_d - x_d { sin(%theta) } over { cos(%theta) } right ] sin( %theta ) = y_d sin( %theta ) - x_d {sin^2(%theta) } over { cos(%theta) } newline newline alignl underline {"With that we can calculate" `x_s`} newline x_s = b + d newline x_s = x_d over {cos(%theta)} + y_d sin( %theta ) - x_d {sin^2(%theta) } over { cos(%theta) } newline x_s = { x_d - x_d sin^2 (%theta) } over { cos(%theta) } + y_d sin( %theta ) newline x_s = { x_d(1-sin^2(%theta)) } over { cos(%theta) } + y_d sin( %theta ) newline alignl underline { "With:"} `1-sin^2( %theta ) = cos^2( %theta ) newline x_s = { x_d cos^2(%theta) } over { cos(%theta) } + y_d sin( %theta ) newline bold {x_s = x_d cos(%theta ) + y_d sin ( %theta )} newline newline alignl underline {y_s` "is a a little simpler:"} newline y_s = c cdot cos( %theta) newline y_s = left [ y_d - x_d { sin(%theta) } over { cos(%theta) } right ] cos( %theta ) newline bold {y_s = y_d cos( %theta ) - x_d sin( %theta )}

These equations are not quite what we want yet. You might have noticed that with those calculations our image will be rotated around the origin of the coordinate system. This means that we would rotate our image around the upper left corner, since in digital images the coordinate (0,0) refers to that corner. But... We want to rotate our image around the center!

In order to achieve this, we transform the destination coordinates to make them relative to the center of the image, apply the formula we just found and transform the result back to coordinates relative to the upper left corner.

In order to transform coordinages so they are relative to the center we must substract the distance from the pixel at (0,0) to the center of the image. Similarly, to transform back to a system relative to the top leftmost pixel, we add that distance.

At first thought, you'd probably say that this distance is half of width and height. Close, but wrong.

The center of an image is at the point that's exactly in the middle of the top leftmost and the bottom rightmost pixels.

The coordinates of the top leftmost pixel are: ( 0, 0 ) The coordinages of the bottom rightmost pixel are: ( w 1, h 1 ) where w and h are width and heigth. The middle point C between two coordinates is: C = ( x 2 x 1 2 , y 2 y 1 2 ) In consequence, the center O of an image has coordinates: O = ( w 1 2 , h 1 2 ) Wich are, by definition, the distances of the center from the origin. With that we can transform coordinates: x dO and y dO are coordinates in destination, relative to the center: x dO = x d w d 1 2 y dO = y d h d 1 2 Similarly, source coordinates relative to the upper left corner can be calculated from source coordinates relative to the center: x s = x sO + w s 1 2 y s = y sO + h s 1 2 Apply translation to the coordinates relative to the center: x sO = x dO cos ( θ ) + y dO sin ( θ ) y sO = y dO cos ( θ ) x dO sin ( θ ) Transform to coordinates relative to the upper left corner and resolve: x s = x sO + w s 1 2 = x dO cos ( θ ) + y dO sin ( θ ) + w s 1 2 x s = ( x d w d 1 2 ) cos ( θ ) + ( y d h d 1 2 ) sin ( θ ) + w s 1 2 x s = x d cos ( θ ) + y d sin ( θ ) w d 1 2 cos ( θ ) h d 1 2 sin ( θ ) + w s 1 2 y s = y sO + h s 1 2 = y dO cos ( θ ) x dO sin ( θ ) + h s 1 2 y s = ( y d h d 1 2 ) cos ( θ ) ( x d w d 1 2 ) sin ( θ ) + h s 1 2 y s = y d cos ( θ ) x d sin ( θ ) h d 1 2 cos ( θ ) + w d 1 2 sin ( θ ) + h s 1 2 alignl "The coordinates of the top leftmost pixel are:" `(0, 0) newline alignl "The coordinages of the bottom rightmost pixel are:" `(w-1, h-1) newline ~"where" `w` "and" `h` "are width and heigth." newline newline alignl "The middle point" `C` "between two coordinates is:" newline C = left({x2-x1} over {2}, {y2 - y1} over 2 right) newline alignl "In consequence, the center" `O` "of an image has coordinates:" newline O = left({w-1}over {2}, {h-1}over2 right) newline alignl "Wich are, by definition, the distances of the center from the origin." newline newline alignl "With that we can transform coordinates:" newline alignl x_dO` "and" `y_dO` "are coordinates in destination, relative to the center:" newline x_dO = x_d - {w_d-1} over 2 newline y_dO = y_d - {h_d-1} over 2 newline newline alignl "Similarly, source coordinates relative to the upper left corner" newline alignl "can be calculated from source coordinates relative to the center:" newline x_s = x_sO + {w_s-1} over 2 newline y_s = y_sO + {h_s-1} over 2 newline newline alignl "Apply translation to the coordinates relative to the center:" newline x_sO = x_dO cos(%theta ) + y_dO sin ( %theta ) newline y_sO = y_dO cos( %theta ) - x_dO sin( %theta ) newline newline alignl "Transform to coordinates relative to the upper left corner and resolve:" newline x_s = x_sO + {w_s-1} over 2 = x_dO cos(%theta ) + y_dO sin( %theta ) + {w_s-1} over 2 newline x_s = ( x_d -{w_d-1} over 2) cos(%theta ) + ( y_d - {h_d-1} over 2) sin ( %theta ) + {w_s-1} over 2 newline bold {x_s = x_d cos( %theta ) + y_d sin(%theta) - {w_d-1} over2 cos( %theta) - {h_d-1} over 2 sin( %theta) + {w_s-1} over 2} newline newline y_s = y_sO + {h_s-1} over 2 = y_dO cos( %theta ) - x_dO sin( %theta ) + {h_s-1} over 2 newline y_s = ( y_d - {h_d-1} over 2 ) cos( %theta ) - ( x_d - {w_d-1} over 2 ) sin( %theta) + {h_s-1} over 2 newline bold {y_s = y_d cos( %theta ) - x_d sin( %theta ) -{h_d-1} over 2 cos( %theta ) + {w_d-1} over 2 sin( %theta) + {h_s-1} over 2 } newline

Top

Interpolation

Now we know how to translate the coordinates of a destination pixel, i.e. we know its position in the source image. Most likely that position is not going to be an integer value, which means that it is somewhere in between known data points in the source image. To get a realistic value for our destination pixel, we must interpolate from the surrounding source pixels.

There are different flavours of interpolation, with different caracteristics in quality and computing time.

The most common interpolation methods in image processing are:

  • (Bi-)Cubic spline interpolation (there are different sub-types, the most common is the Catmull-Rom spline)
  • Lanczos interpolation
  • Linear interpolation
  • Nearest neighbour

There are lots of documents about this topic on the net, so we won't go in more detail here. Here are a few pointers you might find useful or interesting:

Top

Contact | Hosting: SourceForge.net | Valid HTML 4.0! | Last updated: February 2017