python - Girar la imagen y cortar los bordes negros

algorithm opencv

Question

Mi aplicación: estoy tratando de rotar una imagen (usando OpenCV y Python)

Por el momento, he desarrollado el siguiente código que rota una imagen de entrada, rellenando con bordes negros, dándome A. Lo que quiero es B - la ventana de recorte de área más grande posible dentro de la imagen girada. Yo llamo a esto el cuadro boundED alineado con el eje.

Esto es esencialmente lo mismo que Rotar y recortar , sin embargo, no puedo obtener la respuesta para que esa pregunta funcione. Además, esa respuesta aparentemente solo es válida para imágenes cuadradas. Mis imágenes son rectangulares

Código para dar 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

Answer 1

Rotación y recorte en TensorFlow

Yo personalmente necesitaba esta función en TensorFlow y gracias por Aaron Snoswell, pude implementar esta función.

def _rotate_and_crop(image, output_height, output_width, rotation_degree, do_crop):
    """Rotate the given image with the given rotation degree and crop for the black edges if necessary
    Args:
        image: A `Tensor` representing an image of arbitrary size.
        output_height: The height of the image after preprocessing.
        output_width: The width of the image after preprocessing.
        rotation_degree: The degree of rotation on the image.
        do_crop: Do cropping if it is True.
    Returns:
        A rotated image.
    """

    # Rotate the given image with the given rotation degree
    if rotation_degree != 0:
        image = tf.contrib.image.rotate(image, math.radians(rotation_degree), interpolation=''BILINEAR'')

        # Center crop to ommit black noise on the edges
        if do_crop == True:
            lrr_width, lrr_height = _largest_rotated_rect(output_height, output_width, math.radians(rotation_degree))
            resized_image = tf.image.central_crop(image, float(lrr_height)/output_height)    
            image = tf.image.resize_images(resized_image, [output_height, output_width], method=tf.image.ResizeMethod.BILINEAR, align_corners=False)

    return image

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
    Source: http://stackoverflow.com/questions/16702966/rotate-image-and-crop-out-black-borders
    """

    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
    )

Si necesita más implementación de ejemplos y visualización en TensorFlow, puede usar este repositorio . Espero que esto pueda ser útil para otras personas.

Answer 2

Corrección a la solución más favorecida dada anteriormente por Coprox el 27 de mayo de 2013: cuando cosa = cosb infinito resulta en las dos últimas líneas. Resuelve añadiendo "cosa igual cos" en el selector if anterior.

Además: si no conoce los nx y ny originales no girados, pero solo tiene el marco girado (o la imagen), encuentre el cuadro que contiene esto (lo hago eliminando los bordes en blanco = monocromos) y ejecute el programa en sentido inverso. su tamaño para encontrar nx y ny. Si la imagen se giró en un marco demasiado pequeño para que se cortara a lo largo de los lados (en forma octogonal) primero encuentro las extensiones xey para el marco de contención completo. Sin embargo, esto tampoco funciona para ángulos alrededor de 45 grados donde el resultado se cuadra en lugar de mantener la relación de aspecto no girado. Para mí, esta rutina solo funciona correctamente hasta 30 grados.

¡Sigue siendo una gran rutina! Resolvió mi molesto problema en la alineación de imágenes astronómicas.

Answer 3

Entonces, después de investigar muchas soluciones reclamadas, finalmente encontré un método que funciona; La respuesta de Andri y Magnus Hoff en Calcular el rectángulo más grande en un rectángulo girado .

El siguiente código de Python contiene el método de interés - largest_rotated_rect - y una breve demostración.

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 

    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()

Simplemente coloque esta imagen (recortada para demostrar que funciona con imágenes no cuadradas) en el mismo directorio que el archivo anterior, luego ejecútela.

Answer 4

Felicidades por el gran trabajo! Quería usar tu código en OpenCV con la biblioteca C ++, así que hice la conversión que sigue. Tal vez este enfoque podría ser útil para otras personas.

#include <iostream>
#include <opencv.hpp>

#define PI 3.14159265359

using namespace std;

double degree_to_radian(double angle)
{
    return angle * PI / 180;
}

cv::Mat rotate_image (cv::Mat image, double angle)
{
    // Rotates an OpenCV 2 image about its centre by the given angle
    // (in radians). The returned image will be large enough to hold the entire
    // new image, with a black background

    cv::Size image_size = cv::Size(image.rows, image.cols);
    cv::Point image_center = cv::Point(image_size.height/2, image_size.width/2);

    // Convert the OpenCV 3x2 matrix to 3x3
    cv::Mat rot_mat = cv::getRotationMatrix2D(image_center, angle, 1.0);
    double row[3] = {0.0, 0.0, 1.0};
    cv::Mat new_row = cv::Mat(1, 3, rot_mat.type(), row);
    rot_mat.push_back(new_row);


    double slice_mat[2][2] = {
        {rot_mat.col(0).at<double>(0), rot_mat.col(1).at<double>(0)},
        {rot_mat.col(0).at<double>(1), rot_mat.col(1).at<double>(1)}
    };

    cv::Mat rot_mat_nontranslate = cv::Mat(2, 2, rot_mat.type(), slice_mat);

    double image_w2 = image_size.width * 0.5;
    double image_h2 = image_size.height * 0.5;

    // Obtain the rotated coordinates of the image corners
    std::vector<cv::Mat> rotated_coords;

    double image_dim_d_1[2] = { -image_h2, image_w2 };
    cv::Mat image_dim = cv::Mat(1, 2, rot_mat.type(), image_dim_d_1);
    rotated_coords.push_back(cv::Mat(image_dim * rot_mat_nontranslate));


    double image_dim_d_2[2] = { image_h2, image_w2 };
    image_dim = cv::Mat(1, 2, rot_mat.type(), image_dim_d_2);
    rotated_coords.push_back(cv::Mat(image_dim * rot_mat_nontranslate));


    double image_dim_d_3[2] = { -image_h2, -image_w2 };
    image_dim = cv::Mat(1, 2, rot_mat.type(), image_dim_d_3);
    rotated_coords.push_back(cv::Mat(image_dim * rot_mat_nontranslate));


    double image_dim_d_4[2] = { image_h2, -image_w2 };
    image_dim = cv::Mat(1, 2, rot_mat.type(), image_dim_d_4);
    rotated_coords.push_back(cv::Mat(image_dim * rot_mat_nontranslate));


    // Find the size of the new image
    vector<double> x_coords, x_pos, x_neg;
    for (int i = 0; i < rotated_coords.size(); i++)
    {
        double pt = rotated_coords[i].col(0).at<double>(0);
        x_coords.push_back(pt);
        if (pt > 0)
            x_pos.push_back(pt);
        else
            x_neg.push_back(pt);
    }

    vector<double> y_coords, y_pos, y_neg;
    for (int i = 0; i < rotated_coords.size(); i++)
    {
        double pt = rotated_coords[i].col(1).at<double>(0);
        y_coords.push_back(pt);
        if (pt > 0)
            y_pos.push_back(pt);
        else
            y_neg.push_back(pt);
    }


    double right_bound = *max_element(x_pos.begin(), x_pos.end());
    double left_bound = *min_element(x_neg.begin(), x_neg.end());
    double top_bound = *max_element(y_pos.begin(), y_pos.end());
    double bottom_bound = *min_element(y_neg.begin(), y_neg.end());

    int new_w = int(abs(right_bound - left_bound));
    int new_h = int(abs(top_bound - bottom_bound));

    // We require a translation matrix to keep the image centred
    double trans_mat[3][3] = {
        {1, 0, int(new_w * 0.5 - image_w2)},
        {0, 1, int(new_h * 0.5 - image_h2)},
        {0, 0, 1},
    };


    // Compute the transform for the combined rotation and translation
    cv::Mat aux_affine_mat = (cv::Mat(3, 3, rot_mat.type(), trans_mat) * rot_mat);
    cv::Mat affine_mat = cv::Mat(2, 3, rot_mat.type(), NULL);
    affine_mat.push_back(aux_affine_mat.row(0));
    affine_mat.push_back(aux_affine_mat.row(1));

    // Apply the transform
    cv::Mat output;
    cv::warpAffine(image, output, affine_mat, cv::Size(new_h, new_w), cv::INTER_LINEAR);

    return output;
}

cv::Size largest_rotated_rect(int h, int w, double 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 

    // Converted to Python by Aaron Snoswell (https://.com/questions/16702966/rotate-image-and-crop-out-black-borders)
    // Converted to C++ by Eliezer Bernart

    int quadrant = int(floor(angle/(PI/2))) & 3;
    double sign_alpha = ((quadrant & 1) == 0) ? angle : PI - angle;
    double alpha = fmod((fmod(sign_alpha, PI) + PI), PI);

    double bb_w = w * cos(alpha) + h * sin(alpha);
    double bb_h = w * sin(alpha) + h * cos(alpha);

    double gamma = w < h ? atan2(bb_w, bb_w) : atan2(bb_h, bb_h);

    double delta = PI - alpha - gamma;

    int length = w < h ? h : w;

    double d = length * cos(alpha);
    double a = d * sin(alpha) / sin(delta);
    double y = a * cos(gamma);
    double x = y * tan(gamma);

    return cv::Size(bb_w - 2 * x, bb_h - 2 * y);
}

// for those interested in the actual optimum - contributed by coproc
#include <algorithm>
cv::Size really_largest_rotated_rect(int h, int w, double 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.
  if (w <= 0 || h <= 0)
    return cv::Size(0,0);

  bool width_is_longer = w >= h;
  int side_long = w, side_short = h;
  if (!width_is_longer)
    std::swap(side_long, side_short);

  // since the solutions for angle, -angle and pi-angle are all the same,
  // it suffices to look at the first quadrant and the absolute values of sin,cos:
  double sin_a = fabs(math.sin(angle)), cos_a = fabs(math.cos(angle));
  double wr,hr;
  if (side_short <= 2.*sin_a*cos_a*side_long)
  {
    // 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 = x/sin_a;
    hr = x/cos_a;
    if (!width_is_longer)
      std::swap(wr,hr);
  }
  else
  { 
    // fully constrained case: crop touches all 4 sides
    double cos_2a = cos_a*cos_a - sin_a*sin_a;
    wr = (w*cos_a - h*sin_a)/cos_2a;
    hr = (h*cos_a - w*sin_a)/cos_2a;
  }

  return cv::Size(wr,hr);
}

cv::Mat crop_around_center(cv::Mat image, int height, int width)
{
    // Given a OpenCV 2 image, crops it to the given width and height,
    // around it''s centre point

    cv::Size image_size = cv::Size(image.rows, image.cols);
    cv::Point image_center = cv::Point(int(image_size.height * 0.5), int(image_size.width * 0.5));

    if (width > image_size.width)
        width = image_size.width;

    if (height > image_size.height)
        height = image_size.height;

    int x1 = int(image_center.x - width  * 0.5);
    int x2 = int(image_center.x + width  * 0.5);
    int y1 = int(image_center.y - height * 0.5);
    int y2 = int(image_center.y + height * 0.5);


    return image(cv::Rect(cv::Point(y1, x1), cv::Point(y2,x2)));
}

void demo(cv::Mat image)
{
    // Demos the largest_rotated_rect function
    int image_height = image.rows;
    int image_width = image.cols;

    for (float i = 0.0; i < 360.0; i+=0.5)
    {
        cv::Mat image_orig = image.clone();
        cv::Mat image_rotated = rotate_image(image, i);

        cv::Size largest_rect = largest_rotated_rect(image_height, image_width, degree_to_radian(i));
        // for those who trust math (added by coproc):
        cv::Size largest_rect2 = really_largest_rotated_rect(image_height, image_width, degree_to_radian(i));
        cout << "area1 = " << largest_rect.height * largest_rect.width << endl;
        cout << "area2 = " << largest_rect2.height * largest_rect2.width << endl;

        cv::Mat image_rotated_cropped = crop_around_center(
                    image_rotated,
                    largest_rect.height,
                    largest_rect.width
                    );

        cv::imshow("Original Image", image_orig);
        cv::imshow("Rotated Image", image_rotated);
        cv::imshow("Cropped image", image_rotated_cropped);

        if (char(cv::waitKey(15)) == ''q'')
            break;
    }

}

int main (int argc, char* argv[])
{
    cv::Mat image = cv::imread(argv[1]);

    if (image.empty())
    {
        cout << "> The input image was not found." << endl;
        exit(EXIT_FAILURE);
    }

    cout << "Press [s] to begin or restart the demo" << endl;
    cout << "Press [q] to quit" << endl;

    while (true)
    {
        cv::imshow("Original Image", image);
        char opt = char(cv::waitKey(0));
        switch (opt) {
        case ''s'':
            demo(image);
            break;
        case ''q'':
            return EXIT_SUCCESS;
        default:
            break;
        }
    }

    return EXIT_SUCCESS;
}

Answer 5

Hay una manera fácil de solucionar este problema que utiliza otro módulo llamado PIL (útil solamente si está de acuerdo con no usar opencv)

El siguiente código hace exactamente lo mismo y roa cualquier imagen de tal manera que no obtendrá los píxeles negros

from PIL import Image

def array_to_img(x, scale=True):
    x = x.transpose(1, 2, 0) 
    if scale:
        x += max(-np.min(x), 0)
        x /= np.max(x)
        x *= 255
    if x.shape[2] == 3:
        return Image.fromarray(x.astype("uint8"), "RGB")
    else:
        return Image.fromarray(x[:,:,0].astype("uint8"), "L")



def img_to_array(img):
    x = np.asarray(img, dtype=''float32'')
    if len(x.shape)==3:
        # RGB: height, width, channel -> channel, height, width
        x = x.transpose(2, 0, 1)
    else:
        # grayscale: height, width -> channel, height, width
        x = x.reshape((1, x.shape[0], x.shape[1]))
    return x



if __name__ == "__main__":
    # Calls a function to convert image to array
    image_array = img_to_array(image_name)
    # Calls the function to rotate the image by given angle
    rotated_image =  array_to_img(random_rotation(image_array, rotation_angle))

    # give the location where you want to store the image
    rotated_image_name=<location_of_the_image_>+''roarted_image.png''
    # Saves the image in the mentioned location
    rotated_image.save(rotated_image_name)

Answer 6

Inspirado por el asombroso trabajo de Coprox, escribí una función que forma junto con el código de Coprox una solución completa (para que pueda ser utilizada copiando y pegando con no-brainer). La función rotate_max_area a continuación simplemente devuelve una imagen girada sin límite negro.

def rotate_bound(image, angle):
    # CREDIT: https://www.pyimagesearch.com/2017/01/02/rotate-images-correctly-with-opencv-and-python/
    (h, w) = image.shape[:2]
    (cX, cY) = (w // 2, h // 2)
    M = cv2.getRotationMatrix2D((cX, cY), -angle, 1.0)
    cos = np.abs(M[0, 0])
    sin = np.abs(M[0, 1])
    nW = int((h * sin) + (w * cos))
    nH = int((h * cos) + (w * sin))
    M[0, 2] += (nW / 2) - cX
    M[1, 2] += (nH / 2) - cY
    return cv2.warpAffine(image, M, (nW, nH))


def rotate_max_area(image, angle):
    """ image: cv2 image matrix object
        angle: in degree
    """
    wr, hr = rotatedRectWithMaxArea(image.shape[1], image.shape[0],
                                    math.radians(angle))
    rotated = rotate_bound(image, angle)
    h, w, _ = rotated.shape
    y1 = h//2 - int(hr/2)
    y2 = y1 + int(hr)
    x1 = w//2 - int(wr/2)
    x2 = x1 + int(wr)
    return rotated[y1:y2, x1:x2]

Answer 7

La matemática detrás de esta solución / implementación es equivalente a esta solución de una pregunta análoga , pero las fórmulas se simplifican y evitan singularidades. Este es el código python con la misma interfaz que largest_rotated_rect de la otra solución, pero largest_rotated_rect un área más grande en casi todos los casos (siempre el óptimo comprobado):

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

Aquí hay una comparación de la función con la otra solución:

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

Con el ángulo a en [0,pi/2[ el cuadro delimitador de la imagen girada (ancho w , altura h ) tiene estas dimensiones:

• ancho w_bb = w*cos(a) + h*sin(a)
• altura h_bb = w*sin(a) + h*cos(a)

Si w_r , h_r son el ancho y la altura óptimos calculados de la imagen recortada, las inserciones del cuadro delimitador son:

• en dirección horizontal: (w_bb-w_r)/2
• en dirección vertical: (h_bb-h_r)/2

Prueba:

Buscar el rectángulo alineado del eje entre dos líneas paralelas que tiene área máxima es un problema de optimización con un parámetro, por ejemplo, x como en esta figura:

Denotemos la distancia entre las dos líneas paralelas (resultará ser el lado más corto del rectángulo girado). Entonces los lados a , b del rectángulo solicitado tienen una relación constante con x , sx , resp., A saber, x = a sen α y (sx) = b cos α:

Así que maximizar el área a*b significa maximizar x*(sx) . Debido al "teorema de altura" para triángulos en ángulo recto, sabemos que x*(sx) = p*q = h*h . Por lo tanto, el área máxima se alcanza en x = sx = s/2 , es decir, las dos esquinas E, G entre las líneas paralelas están en la línea media:

Esta solución solo es válida si este rectángulo máximo encaja en el rectángulo girado. Por lo tanto, el EG diagonal no debe ser más largo que el otro lado l del rectángulo girado. Ya que

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

tenemos la condición s ≤ l sen 2 α, donde s y l son el lado más corto y más largo del rectángulo girado.

En el caso de s> l sen 2 α, el parámetro x debe ser más pequeño (que s / 2) y st todas las esquinas del rectángulo buscado están cada una en un lado del rectángulo girado. Esto lleva a la ecuación

x * cot α + (sx) * tan α = l

dando x = sin α (l cos α - s sin α) / cos 2 α. A partir de a = x / sin α y b = (sx) / cos α obtenemos las fórmulas utilizadas anteriormente.

Answer 8

Solución Swift

Gracias a coproc por su gran solución. Aquí está el código en swift

// Given a rectangle of size.width x size.height 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.
func rotatedRectWithMaxArea(size: CGSize, angle: CGFloat) -> CGSize {
    let w = size.width
    let h = size.height

    if(w <= 0 || h <= 0) {
        return CGSize.zero
    }

    let widthIsLonger = w >= h
    let (sideLong, sideShort) = widthIsLonger ? (w, h) : (w, h)

    // 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:
    let (sinA, cosA) = (sin(angle), cos(angle))
    if(sideShort <= 2*sinA*cosA*sideLong || abs(sinA-cosA) < 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
        let x = 0.5*sideShort
        let (wr, hr) = widthIsLonger ? (x/sinA, x/cosA) : (x/cosA, x/sinA)
        return CGSize(width: wr, height: hr)
    } else {
        // fully constrained case: crop touches all 4 sides
        let cos2A = cosA*cosA - sinA*sinA
        let (wr, hr) = ((w*cosA - h*sinA)/cos2A, (h*cosA - w*sinA)/cos2A)
        return CGSize(width: wr, height: hr)
    }
}