Geometric Transformation and Interpolation

From BioenWiki

Jump to: navigation, search

Geometric Transformations are functions applied to images, which map one domain of element values to another domain. These transformations can produce a number of different results (e.g. scaling, rotations, projections, shearing, projection, etc.).

Because these transformations operate on a discrete domain, interpolation is used to provide an approximation of a point on the domain, where no exact value exists.

Contents

Affine Transformations

Affine Transformations are a subset of geometric transformations, where parallelism is preserved after being applied. Scaling, rotating, additive translations, and shearing are all examples of affine transformations. For example, after a square has been sheared, although the lengths of the sides and internal angles have been altered, the line segments on opposite sides will remain parallel.

Projection Transformations

Projection Transformations are functions, which usually do not preserve parallelism. These functions apply transformations that warp the image or project it to a lower dimension.

Interpolation

Interpolation is used when a transformation function applied to a discrete set of input values results in a value some where in between known elements. Some technique to approximate the result should be used. Interpolation in image processing and computer graphics is required to provide smoother transitions across the discrete domain.

Types of InterpolationDescriptionInterpolated Warped Image
Nearest neighborThe nearest neighbor algorithm returns the data value of the known element closest to a given point on the domain. For example, interpolating x = 1.2 between (1, 7) and (2, 83) using nearest-neighbor interpolation would return 7 since the point (1, 7) is closer to x = 1.2 than (2, 83)House interp nearest.png
Linear InterpolationLinear interpolation, like a weighted average, linearly approximates a value based on two data elements, which fall between it based on their distance from a given point. For example, if x=1.2, than x is 0.2 units away from the first element and 0.8 from the second, than x = (.8 * 7) + (.2 * 83). This interpolation allows the farther point to contribute to the interpolation although the first point has a much higher weight.

Linear interpolation can also be implemented on higher dimensions. In 2D, for instance, a point which falls in between four elements on can be linearly interpolated parallel to the x-axis for the two points above and two points below. These values are then interpolated parallel to the y-axis. This 2D interpolation is called bilinear interpolation

Let's say on XY coordinate system, we have a point (x, y). and its four neighbors are (xa, ya), (xa+1, ya), (xa, ya+1), and (xa+1, ya+1). Let's say these neighbor points are a, b, c, and d respectively.

For X coordinate, α is distance from xa to x and (1 - α) is distance from x to xa+1.

Similarly for Y coordinate, β is distance from ya to y and (1 - β) is distance from y to ya+1.

Then we have following bilinear function:

f(x,y)=αβ(d) + (1 - α)β(c) + (1 - α)(1-β)(a) + (1 - β)α(b)


House interp linear.png
Polynomial InterpolationPolynomial interpolation fits a discrete domain to some continuous polynomial of some degree and uses the value of this curve at the given point as the resultHouse interp cubic.png
Spline InterpolationA spline is a piece-wise polynomial. Spline interpolation is similar to polynomial interpolation, except multiple polynomials are generated for each segment of domain

Push-Forward vs Pull-Backward Transformations

An image, I(x), can be transformed to another image, I'(x) = I(h(x)), in two different ways: push forward or pull backwards.

  • When pushing forward an image, a source pixel is chosen in the original image and its destination's location is calculated in the new image. The problem with this is the location of its destination is most likely to fall between pixels. The new image's pixel values would still need to be calculated.
  • When pulling backward an image, a pixel is chosen in the new image and the location of its source value is calculated in reverse. The source location is in the original image and is most likely to fall between pixels. The value of this source would then be interpolated from its surrounding pixels. Fewer calculations are required with this method.
Transformation TechniqueIllustration
Push ForwardInterpolationPushForward.png
Pull BackwardInterpolationPullBackward.png
Pull BackwardPullFrom30degCntrClkwise.png


6640:Home 6640:Course Schedule
Personal tools