Rotate image and crop out black borders


Question

My application: I am trying to rotate an image (using OpenCV and Python)

Rotating Images

At the moment I have developed the below code which rotates an input image, padding it with black borders, giving me A. What I want is B - the largest possible area crop window within the rotated image. I call this the axis-aligned boundED box.

This is essentially the same as Rotate and crop, however I cannot get the answer on that question to work. Additionally, that answer is apparently only valid for square images. My images are rectangular.

Code to give A:

import cv2
import numpy as np


def getTranslationMatrix2d(dx, dy):
    """
    Returns a numpy affine transformation matrix for a 2D translation of
    (dx, dy)
    """
    return np.matrix([[1, 0, dx], [0, 1, dy], [0, 0, 1]])


def rotateImage(image, angle):
    """
    Rotates the given image about it's centre
    """

    image_size = (image.shape[1], image.shape[0])
    image_center = tuple(np.array(image_size) / 2)

    rot_mat = np.vstack([cv2.getRotationMatrix2D(image_center, angle, 1.0), [0, 0, 1]])
    trans_mat = np.identity(3)

    w2 = image_size[0] * 0.5
    h2 = image_size[1] * 0.5

    rot_mat_notranslate = np.matrix(rot_mat[0:2, 0:2])

    tl = (np.array([-w2, h2]) * rot_mat_notranslate).A[0]
    tr = (np.array([w2, h2]) * rot_mat_notranslate).A[0]
    bl = (np.array([-w2, -h2]) * rot_mat_notranslate).A[0]
    br = (np.array([w2, -h2]) * rot_mat_notranslate).A[0]

    x_coords = [pt[0] for pt in [tl, tr, bl, br]]
    x_pos = [x for x in x_coords if x > 0]
    x_neg = [x for x in x_coords if x < 0]

    y_coords = [pt[1] for pt in [tl, tr, bl, br]]
    y_pos = [y for y in y_coords if y > 0]
    y_neg = [y for y in y_coords if y < 0]

    right_bound = max(x_pos)
    left_bound = min(x_neg)
    top_bound = max(y_pos)
    bot_bound = min(y_neg)

    new_w = int(abs(right_bound - left_bound))
    new_h = int(abs(top_bound - bot_bound))
    new_image_size = (new_w, new_h)

    new_midx = new_w * 0.5
    new_midy = new_h * 0.5

    dx = int(new_midx - w2)
    dy = int(new_midy - h2)

    trans_mat = getTranslationMatrix2d(dx, dy)
    affine_mat = (np.matrix(trans_mat) * np.matrix(rot_mat))[0:2, :]
    result = cv2.warpAffine(image, affine_mat, new_image_size, flags=cv2.INTER_LINEAR)

    return result
1
54
5/23/2017 11:54:15 AM

Accepted Answer

So, after investigating many claimed solutions, I have finally found a method that works; The answer by Andri and Magnus Hoff on Calculate largest rectangle in a rotated rectangle.

The below Python code contains the method of interest - largest_rotated_rect - and a short demo.

import math
import cv2
import numpy as np


def rotate_image(image, angle):
    """
    Rotates an OpenCV 2 / NumPy image about it's centre by the given angle
    (in degrees). The returned image will be large enough to hold the entire
    new image, with a black background
    """

    # Get the image size
    # No that's not an error - NumPy stores image matricies backwards
    image_size = (image.shape[1], image.shape[0])
    image_center = tuple(np.array(image_size) / 2)

    # Convert the OpenCV 3x2 rotation matrix to 3x3
    rot_mat = np.vstack(
        [cv2.getRotationMatrix2D(image_center, angle, 1.0), [0, 0, 1]]
    )

    rot_mat_notranslate = np.matrix(rot_mat[0:2, 0:2])

    # Shorthand for below calcs
    image_w2 = image_size[0] * 0.5
    image_h2 = image_size[1] * 0.5

    # Obtain the rotated coordinates of the image corners
    rotated_coords = [
        (np.array([-image_w2,  image_h2]) * rot_mat_notranslate).A[0],
        (np.array([ image_w2,  image_h2]) * rot_mat_notranslate).A[0],
        (np.array([-image_w2, -image_h2]) * rot_mat_notranslate).A[0],
        (np.array([ image_w2, -image_h2]) * rot_mat_notranslate).A[0]
    ]

    # Find the size of the new image
    x_coords = [pt[0] for pt in rotated_coords]
    x_pos = [x for x in x_coords if x > 0]
    x_neg = [x for x in x_coords if x < 0]

    y_coords = [pt[1] for pt in rotated_coords]
    y_pos = [y for y in y_coords if y > 0]
    y_neg = [y for y in y_coords if y < 0]

    right_bound = max(x_pos)
    left_bound = min(x_neg)
    top_bound = max(y_pos)
    bot_bound = min(y_neg)

    new_w = int(abs(right_bound - left_bound))
    new_h = int(abs(top_bound - bot_bound))

    # We require a translation matrix to keep the image centred
    trans_mat = np.matrix([
        [1, 0, int(new_w * 0.5 - image_w2)],
        [0, 1, int(new_h * 0.5 - image_h2)],
        [0, 0, 1]
    ])

    # Compute the tranform for the combined rotation and translation
    affine_mat = (np.matrix(trans_mat) * np.matrix(rot_mat))[0:2, :]

    # Apply the transform
    result = cv2.warpAffine(
        image,
        affine_mat,
        (new_w, new_h),
        flags=cv2.INTER_LINEAR
    )

    return result


def largest_rotated_rect(w, h, angle):
    """
    Given a rectangle of size wxh that has been rotated by 'angle' (in
    radians), computes the width and height of the largest possible
    axis-aligned rectangle within the rotated rectangle.

    Original JS code by 'Andri' and Magnus Hoff from Stack Overflow

    Converted to Python by Aaron Snoswell
    """

    quadrant = int(math.floor(angle / (math.pi / 2))) & 3
    sign_alpha = angle if ((quadrant & 1) == 0) else math.pi - angle
    alpha = (sign_alpha % math.pi + math.pi) % math.pi

    bb_w = w * math.cos(alpha) + h * math.sin(alpha)
    bb_h = w * math.sin(alpha) + h * math.cos(alpha)

    gamma = math.atan2(bb_w, bb_w) if (w < h) else math.atan2(bb_w, bb_w)

    delta = math.pi - alpha - gamma

    length = h if (w < h) else w

    d = length * math.cos(alpha)
    a = d * math.sin(alpha) / math.sin(delta)

    y = a * math.cos(gamma)
    x = y * math.tan(gamma)

    return (
        bb_w - 2 * x,
        bb_h - 2 * y
    )


def crop_around_center(image, width, height):
    """
    Given a NumPy / OpenCV 2 image, crops it to the given width and height,
    around it's centre point
    """

    image_size = (image.shape[1], image.shape[0])
    image_center = (int(image_size[0] * 0.5), int(image_size[1] * 0.5))

    if(width > image_size[0]):
        width = image_size[0]

    if(height > image_size[1]):
        height = image_size[1]

    x1 = int(image_center[0] - width * 0.5)
    x2 = int(image_center[0] + width * 0.5)
    y1 = int(image_center[1] - height * 0.5)
    y2 = int(image_center[1] + height * 0.5)

    return image[y1:y2, x1:x2]


def demo():
    """
    Demos the largest_rotated_rect function
    """

    image = cv2.imread("lenna_rectangle.png")
    image_height, image_width = image.shape[0:2]

    cv2.imshow("Original Image", image)

    print "Press [enter] to begin the demo"
    print "Press [q] or Escape to quit"

    key = cv2.waitKey(0)
    if key == ord("q") or key == 27:
        exit()

    for i in np.arange(0, 360, 0.5):
        image_orig = np.copy(image)
        image_rotated = rotate_image(image, i)
        image_rotated_cropped = crop_around_center(
            image_rotated,
            *largest_rotated_rect(
                image_width,
                image_height,
                math.radians(i)
            )
        )

        key = cv2.waitKey(2)
        if(key == ord("q") or key == 27):
            exit()

        cv2.imshow("Original Image", image_orig)
        cv2.imshow("Rotated Image", image_rotated)
        cv2.imshow("Cropped Image", image_rotated_cropped)

    print "Done"


if __name__ == "__main__":
    demo()

Image Rotation Demo

Simply place this image (cropped to demonstrate that it works with non-square images) in the same directory as the above file, then run it.

25
5/23/2017 12:09:45 PM

The math behind this solution/implementation is equivalent to this solution of an analagous question, but the formulas are simplified and avoid singularities. This is python code with the same interface as largest_rotated_rect from the other solution, but giving a bigger area in almost all cases (always the proven optimum):

def rotatedRectWithMaxArea(w, h, angle):
  """
  Given a rectangle of size wxh that has been rotated by 'angle' (in
  radians), computes the width and height of the largest possible
  axis-aligned rectangle (maximal area) within the rotated rectangle.
  """
  if w <= 0 or h <= 0:
    return 0,0

  width_is_longer = w >= h
  side_long, side_short = (w,h) if width_is_longer else (h,w)

  # since the solutions for angle, -angle and 180-angle are all the same,
  # if suffices to look at the first quadrant and the absolute values of sin,cos:
  sin_a, cos_a = abs(math.sin(angle)), abs(math.cos(angle))
  if side_short <= 2.*sin_a*cos_a*side_long or abs(sin_a-cos_a) < 1e-10:
    # half constrained case: two crop corners touch the longer side,
    #   the other two corners are on the mid-line parallel to the longer line
    x = 0.5*side_short
    wr,hr = (x/sin_a,x/cos_a) if width_is_longer else (x/cos_a,x/sin_a)
  else:
    # fully constrained case: crop touches all 4 sides
    cos_2a = cos_a*cos_a - sin_a*sin_a
    wr,hr = (w*cos_a - h*sin_a)/cos_2a, (h*cos_a - w*sin_a)/cos_2a

  return wr,hr

Here is a comparison of the function with the other solution:

>>> wl,hl = largest_rotated_rect(1500,500,math.radians(20))
>>> print (wl,hl),', area=',wl*hl
(828.2888697391496, 230.61639227890998) , area= 191016.990904
>>> wm,hm = rotatedRectWithMaxArea(1500,500,math.radians(20))
>>> print (wm,hm),', area=',wm*hm
(730.9511000407718, 266.044443118978) , area= 194465.478358

With angle a in [0,pi/2[ the bounding box of the rotated image (width w, height h) has these dimensions:

  • width w_bb = w*cos(a) + h*sin(a)
  • height h_bb = w*sin(a) + h*cos(a)

If w_r, h_r are the computed optimal width and height of the cropped image, then the insets from the bounding box are:

  • in horizontal direction: (w_bb-w_r)/2
  • in vertical direction: (h_bb-h_r)/2

Proof:

Looking for the axis aligned rectangle between two parallel lines that has maximal area is an optimization problem with one parameter, e.g. x as in this figure: animated parameter

Let s denote the distance between the two parallel lines (it will turn out to be the shorter side of the rotated rectangle). Then the sides a, b of the sought-after rectangle have a constant ratio with x, s-x, resp., namely x = a sin α and (s-x) = b cos α:

enter image description here

So maximizing the area a*b means maximizing x*(s-x). Because of "theorem of height" for right-angled triangles we know x*(s-x) = p*q = h*h. Hence the maximal area is reached at x = s-x = s/2, i.e. the two corners E, G between the parallel lines are on the mid-line:

enter image description here

This solution is only valid if this maximal rectangle fits into the rotated rectangle. Therefore the diagonal EG must not be longer than the other side l of the rotated rectangle. Since

EG = AF + DH = s/2*(cot α + tan α) = s/(2*sin αcos α) = s/sin 2α

we have the condition s ≤ lsin 2α, where s and l are the shorter and longer side of the rotated rectangle.

In case of s > lsin 2α the parameter x must be smaller (than s/2) and s.t. all corners of the sought-after rectangle are each on a side of the rotated rectangle. This leads to the equation

x*cot α + (s-x)*tan α = l

giving x = sin α(lcos α - ssin α)/cos 2α. From a = x/sin α and b = (s-x)/cos α we get the above used formulas.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon