algorithm - 프로그래머 - 히스토그램 에서 가장 큰 직사각형




회전 된 사각형에서 가장 큰 사각형 계산 (6)

@ 앤드 리가 테스트 한 것처럼 width > height 이미지에서 제대로 작동하지 않습니다. 그래서 저는 (두 개의 삼각 함수만으로) 코드를 수정하고 최적화했습니다 :

calculateLargestRect = function(angle, origWidth, origHeight) {
    var w0, h0;
    if (origWidth <= origHeight) {
        w0 = origWidth;
        h0 = origHeight;
    }
    else {
        w0 = origHeight;
        h0 = origWidth;
    }
    // Angle normalization in range [-PI..PI)
    var ang = angle - Math.floor((angle + Math.PI) / (2*Math.PI)) * 2*Math.PI; 
    ang = Math.abs(ang);      
    if (ang > Math.PI / 2)
        ang = Math.PI - ang;
    var sina = Math.sin(ang);
    var cosa = Math.cos(ang);
    var sinAcosA = sina * cosa;
    var w1 = w0 * cosa + h0 * sina;
    var h1 = w0 * sina + h0 * cosa;
    var c = h0 * sinAcosA / (2 * h0 * sinAcosA + w0);
    var x = w1 * c;
    var y = h1 * c;
    var w, h;
    if (origWidth <= origHeight) {
        w = w1 - 2 * x;
        h = h1 - 2 * y;
    }
    else {
        w = h1 - 2 * y;
        h = w1 - 2 * x;
    }
    return {
        w: w,
        h: h
    }
}

최신 정보

또한 비례 rectange 계산을 위해 다음 함수를 게시하기로 결정했습니다.

calculateLargestProportionalRect = function(angle, origWidth, origHeight) {
    var w0, h0;
    if (origWidth <= origHeight) {
        w0 = origWidth;
        h0 = origHeight;
    }
    else {
        w0 = origHeight;
        h0 = origWidth;
    }
    // Angle normalization in range [-PI..PI)
    var ang = angle - Math.floor((angle + Math.PI) / (2*Math.PI)) * 2*Math.PI; 
    ang = Math.abs(ang);      
    if (ang > Math.PI / 2)
        ang = Math.PI - ang;
    var c = w0 / (h0 * Math.sin(ang) + w0 * Math.cos(ang));
    var w, h;
    if (origWidth <= origHeight) {
        w = w0 * c;
        h = h0 * c;
    }
    else {
        w = h0 * c;
        h = w0 * c;
    }
    return {
        w: w,
        h: h
    }
}

난 회전 사각형 내부에 포함될 수있는 가장 큰 (영역에서) 사각형을 계산하는 가장 좋은 방법을 찾으려고 노력하고있어.

일부 사진은 내가 의미하는 것을 시각화하는 데 도움이됩니다 (희망 사항).

입력 사각형의 너비와 높이가 주어지며 회전 할 각도도 지정됩니다. 출력 사각형이 회전하거나 비뚤어지지 않습니다.

나는 그것이 코너 케이스 (아무 말장련 의도도)를 취급 할 것인지 확실하지 않은 장시간 경로를 따라 내려갈 것이다. 나는 이것에 대한 우아한 해결책이 확실하다. 어떤 팁?

EDIT : 출력 직사각형 포인트는 반드시 입력 사각형을 만질 필요는 없습니다. (미스터 E 덕분에)


Coproc은이 문제를 다른 스레드 ( https://.com/a/16778797 )에서 간단하고 효율적인 방법으로 해결했습니다. 또한, 그는 거기에 아주 좋은 설명과 파이썬 코드를 주었다.

아래에는 그의 솔루션을 구현 한 Matlab이 있습니다.

function [ CI, T ] = rotateAndCrop( I, ang )
%ROTATEANDCROP Rotate an image 'I' by 'ang' degrees, and crop its biggest
% inner rectangle.

[h,w,~] = size(I);
ang = deg2rad(ang);

% Affine rotation
R = [cos(ang) -sin(ang) 0; sin(ang) cos(ang) 0; 0 0 1];
T = affine2d(R);
B = imwarp(I,T);

% Largest rectangle
% solution from https://.com/a/16778797

wb = w >= h;
sl = w*wb + h*~wb;
ss = h*wb + w*~wb;

cosa = abs(cos(ang));
sina = abs(sin(ang));

if ss <= 2*sina*cosa*sl
    x = .5*min([w h]);
    wh = wb*[x/sina x/cosa] + ~wb*[x/cosa x/sina];
else
    cos2a = (cosa^2) - (sina^2);
    wh = [(w*cosa - h*sina)/cos2a (h*cosa - w*sina)/cos2a]; 
end

hw = flip(wh);

% Top-left corner
tl = round(max(size(B)/2 - hw/2,1));

% Bottom-right corner
br = tl + round(hw);

% Cropped image
CI = B(tl(1):br(1),tl(2):br(2),:);

먼저 각도가 0 또는 pi / 2의 배수 인 사소한 경우를 처리합니다. 그런 다음 가장 큰 직사각형은 원래 직사각형과 같습니다.

일반적으로 내부 사각형은 외부 사각형의 경계에 3 점을 갖습니다. 그렇지 않으면 하나의 꼭지점이 아래쪽에 오도록 하나의 꼭지점이 왼쪽에 있도록 이동 될 수 있습니다. 그런 다음 두 개의 나머지 정점 중 하나가 경계를 칠 때까지 내부 직사각형을 확대 할 수 있습니다.

외부 직사각형 R1과 R2의 변을 호출합니다. 일반성을 잃지 않고 R1 <= R2라고 가정 할 수 있습니다. 내부 사각형 H와 W의 변을 호출하면,

H cos a + W sin a <= R1
H sin a + W cos a <= R2

경계에 적어도 3 점이 있기 때문에 이러한 불평등 중 적어도 하나는 실제로 평등이어야합니다. 첫 번째 것을 사용합시다. 그것을 쉽게 알 수 있습니다 :

W = (R1 - H cos a) / sin a

그래서 그 지역은

A = H W = H (R1 - H cos a) / sin a

파생 상품을 가져올 수 있습니다. H이고 0과 같아야합니다.

dA/dH = ((R1 - H cos a) - H cos a) / sin a

위의 W에 대한 식을 사용하여 H를 풀면 다음과 같이됩니다.

H = R1 / (2 cos a)
W = R1 / (2 sin a)

이것을 두 번째 부등식으로 대치하면 어떤 조작을 한 후에,

R1 (tan a + 1/tan a) / 2 <= R2

왼쪽의 인수는 항상 적어도 1입니다. 부등식이 충족되면 솔루션이 생깁니다. 만족스럽지 않으면 해답은 두 부등식을 등식으로 만족하는 해입니다. 다른 말로하면, 그것은 바깥 사각형의 네면을 모두 터치하는 사각형입니다. 이것은 쉽게 풀릴 수있는 2 개의 미지수가있는 선형 시스템입니다.

H = (R2 cos a - R1 sin a) / cos 2a
W = (R1 cos a - R2 sin a) / cos 2a

원래 좌표의 관점에서 볼 때 다음과 같습니다.

x1 = x4 = W sin a cos a
y1 = y2 = R2 sin a - W sin^2 a 
x2 = x3 = x1 + H
y3 = y4 = y2 + W

미안하지만 여기서 파생물을 내지 못해서 미안하지만 며칠 전이 문제를 Mathematica에서 풀어서 Mathematica가 아닌 사람들이 읽을 수있는 다음 절차를 생각해 냈습니다. 의심스러운 경우 http://reference.wolfram.com/mathematica/guide/Mathematica.html 참조하십시오.

아래 절차는 알파로 회전 된 너비 w와 높이 h의 다른 사각형에 맞는 최대 면적을 가진 사각형의 너비와 높이를 반환합니다.

CropRotatedDimensionsForMaxArea[{w_, h_}, alpha_] := 
With[
  {phi = [email protected][alpha, Pi, -Pi/2]},
  Which[
   w == h, {w,h} Csc[phi + Pi/4]/Sqrt[2],
   w > h, 
     If[ Cos[2 phi]^2 < 1 - (h/w)^2, 
       h/2 {Csc[phi], Sec[phi]}, 
       Sec[2 phi] {w Cos[phi] - h Sin[phi], h Cos[phi] - w Sin[phi]}],
   w < h, 
     If[ Cos[2 phi]^2 < 1 - (w/h)^2, 
       w/2 {Sec[phi], Csc[phi]}, 
       Sec[2 phi] {w Cos[phi] - h Sin[phi], h Cos[phi] - w Sin[phi]}]
  ]
]

편집 : 아래의 매쓰 매 티카 (Mathematica) 대답은 잘못되었습니다. - 제가 정말로 생각하고있는 것보다 약간 다른 문제를 해결하고있었습니다.

정말로 묻고있는 문제를 해결하려면 다음 알고리즘을 사용하십시오.

최대 빈 사각형 문제

이 알고리즘을 사용하여 회전 된 사각형의 경계를 형성하는 유한 양의 점을 나타냅니다 (아마도 100 정도이므로 모서리를 포함해야합니다). 이것은 종이에 기술 된 집합 S입니다.

.

.

.

.

.

후손을 위해 나는 원래의 게시물을 다음과 같이 남겼습니다.

면적이 가장 큰 안쪽 사각형은 항상 사각형의 아래쪽 중간 모서리 (다이어그램에서 알파 근처의 모서리)가 외부 사각형의 너비의 절반에 해당하는 사각형입니다.

나는 속임수를 쓰고 Mathematica를 사용하여 나를위한 대수를 풀었습니다.

이것으로부터 내부 사각형의 최대 면적이 각도의 1/4 분의 2 배에 해당한다는 것을 알 수 있습니다.

이제이 최적 조건에 대한 하단 모서리의 x 값이 무엇인지 알아야합니다. 내 지역 수식에서 mathematica의 Solve 함수를 사용하여 다음을 얻습니다.

아래쪽 모서리의 x 좌표가 너비의 절반과 같습니다.

이제 확실히하기 위해, 나는 우리의 대답을 경험적으로 테스트 할 것입니다. 아래의 결과를 통해 모든 테스트 중 가장 높은 영역 (실제로는 철저하지는 않지만 포인트를 얻음)은 하단 모서리의 x 값 = 외부 사각형의 너비의 절반이라고 볼 수 있습니다.


이 작업을 수행하는 가장 쉬운 방법은 다음과 같습니다. :)

Step 1
//Before Rotation

int originalWidth = 640;
int originalHeight = 480;

Step 2
//After Rotation
int newWidth = 701;  //int newWidth = 654;  //int newWidth = 513;
int newHeight = 564; //int newHeight = 757; //int newHeight = 664;

Step 3
//Difference in height and width
int widthDiff ;
int heightDiff;
int ASPECT_RATIO = originalWidth/originalHeight; //Double check the Aspect Ratio

if (newHeight > newWidth) {

    int ratioDiff = newHeight - newWidth;
    if (newWidth < Constant.camWidth) {
        widthDiff = (int) Math.floor(newWidth / ASPECT_RATIO);
        heightDiff = (int) Math.floor((originalHeight - (newHeight - originalHeight)) / ASPECT_RATIO);
    }
    else {
        widthDiff = (int) Math.floor((originalWidth - (newWidth - originalWidth) - ratioDiff) / ASPECT_RATIO);
        heightDiff = originalHeight - (newHeight - originalHeight);
    }

} else {
    widthDiff = originalWidth - (originalWidth);
    heightDiff = originalHeight - (newHeight - originalHeight);
}

Step 4
//Calculation
int targetRectanleWidth = originalWidth - widthDiff;
int targetRectanleHeight = originalHeight - heightDiff;

Step 5
int centerPointX = newWidth/2;
int centerPointY = newHeight/2;

Step 6
int x1 = centerPointX - (targetRectanleWidth / 2); 
int y1 = centerPointY - (targetRectanleHeight / 2);
int x2 = centerPointX + (targetRectanleWidth / 2);
int y2 = centerPointY + (targetRectanleHeight / 2);

Step 7
x1 = (x1 < 0 ? 0 : x1);
y1 = (y1 < 0 ? 0 : y1);




geometry