[C] 인접한 직사각형 합쳐서 최대 만들기

여러 개의 인접한 직사각형을 합치는 알고리즘 입니다! (아직 버그가 있습니다.....ㅜ)

저 같은 경우에는 라벨링 후 처리 로 사용하려고 만들었습니다.

라벨링을 해도 잘 안 합쳐지는 게 간혹 있더라고요. 

그리고 isolated 된 부분의 경우, 간혹 라벨이 포개어져서? 나오기도 합니다.

간략하게 그림으로 그리면 아래와 같습니다.

input: 직사각형들

output: input을 모두 포함하는 최대 직사각형

※ C언어 입니다. (코드 못짬 주의)

void MK_maxNmin(int a, int b, int c, int d, int *max, int *min){ //4개 정수에서 최대, 최소 구하기
 int arr[4];
 int i;
 arr[0] = a; arr[1] = b; arr[2] = c; arr[3] = d;
 *max = a;
 *min = a;
 for(i=1; i < 4; i++){
     if(*max < arr[i])
         *max = arr[i];
     if(*min > arr[i])
         *min = arr[i];
 }
        
}
int mergeLabel(MK_Label *labels, MK_Label *dst,int labelNum){
    //아주 인접한 label은 합친다.
    int left1, right1, top1, bottom1;
    int left2, right2, top2, bottom2; //비교 라벨
    int left3, right3, top3, bottom3; //최종 라벨
    int i,j,a,b;
    MK_Label tmp[20]; //input 개수가 최대 20개여야 함.
    int labelCnt = 0;
    int intersectionCnt=0; //겹친 횟수 세는 변수
    int x=0, y=0;
    int overlapFlag=0; //이미 탐색 됐는지 mark 하는 변수
    for(i=0; i<20; i++){
        for(j=0; j<4; j++){
            rectArr[i][j]=0; //rectArr 초기화
        }
    }
    for(i=0; i<labelNum; i++){
        if(labelCnt > 19)
            break;
        if(intersectionCnt == labelNum-1) //라벨 모두 탐색했으면
            break;
        intersectionCnt = 0;
        //라벨링 박스 주변 영역의 좌표저장
        left1 = labels[i].boundingRect.x;
        top1 = labels[i].boundingRect.y;
        right1 = labels[i].boundingRect.x + labels[i].boundingRect.width-1;
        bottom1 = labels[i].boundingRect.y + labels[i].boundingRect.height-1;
        //다른 라벨과 위치 비교
        for(j = i+1; j< labelNum; j++){
            //다른 라벨 꼭지점 저장
            left2 = labels[j].boundingRect.x;
            top2 = labels[j].boundingRect.y;
            right2 = labels[j].boundingRect.x + labels[j].boundingRect.width-1;
            bottom2 = labels[j].boundingRect.y + labels[j].boundingRect.height-1;
            for(a=0; a<y; a++){
                b=0;
                if(rectArr[a][b] == left2 && rectArr[a][b+1] == right2 && rectArr[a][b+2] == top2 && rectArr[a][b+3] == bottom2) // 현재 탐색라벨이 이미 탐색됐다면 표시하고, 겹침을 고려하지 않음
                    overlapFlag = 1;
                else if(rectArr[a][b] == left1 && rectArr[a][b+1] == right1 && rectArr[a][b+2] == top1 && rectArr[a][b+3] == bottom1)
                    overlapFlag =1;
            }
            
            if( (top1-5 > bottom2+5) || (bottom1+5 < top2-5) || (left1 > right2) || (right1 < left2)){ //수직 방향으로 5px 인접하면 합침. (이 부분에서 인접범위 조절 가능)
                if(overlapFlag == 1)
                    continue;
                if(j==labelNum-1){
                    if(intersectionCnt>0){//마지막 회차, 적어도 한번 이상 겹쳤으면 최대영역 좌표 저장
                        tmp[labelCnt].boundingRect.x = left3;
                        tmp[labelCnt].boundingRect.y = top3;
                        tmp[labelCnt].boundingRect.width = right3 - left3+1;
                        tmp[labelCnt].boundingRect.height = bottom3 - top3+1;
                        tmp[labelCnt].center.x = (right3+left3)/2;
                        tmp[labelCnt++].center.y = (top3+bottom3)/2;
                    }
                    else{//한번도 안겹쳤으면 원래 좌표 저장
                        tmp[labelCnt].boundingRect.x = labels[i].boundingRect.x;
                        tmp[labelCnt].boundingRect.y = labels[i].boundingRect.y;
                        tmp[labelCnt].boundingRect.width = labels[i].boundingRect.width;
                        tmp[labelCnt].boundingRect.height = labels[i].boundingRect.height;
                        tmp[labelCnt].center.x = labels[i].center.x;
                        tmp[labelCnt++].center.y = labels[i].center.y;
                    }
                }
                continue;
            }
            //두 라벨이 겹치는 경우
            rectArr[y][x++] = left2; rectArr[y][x++] = right2; rectArr[y][x++] = top2; rectArr[y][x++] = bottom2; y++; x=0;
            rectArr[y][x++] = left1; rectArr[y][x++] = right1; rectArr[y][x++] = top1; rectArr[y][x++] = bottom1; y++;
            MK_maxNmin(left1, left2, right1, right2, &right1, &left1);
            MK_maxNmin(top1, top2, bottom1, bottom2, &bottom1, &top1);
            right3 = right1; left3 = left1; bottom3 = bottom1; top3 = top1; //최대 좌표 저장
            intersectionCnt ++; //겹친 횟수 증가
        
            if(j == labelNum-1){ //마지막 회차, 적어도 한번 이상 겹쳤으면 최대영역 좌표 저장
                tmp[labelCnt].boundingRect.x = left1;
                tmp[labelCnt].boundingRect.y = top1;
                tmp[labelCnt].boundingRect.width = right1 - left1+1;
                tmp[labelCnt].boundingRect.height = bottom1 - top1+1;
                tmp[labelCnt].center.x = left1 + (right1 - left1+1)/2;
                tmp[labelCnt++].center.y = top1 + (bottom1 - top1+1)/2;
                
            }
        }
    }
    //merge 된 라벨 다시 옮기기
    for(i=0; i < labelCnt; i++){
        dst[i] = tmp[i];
    }
    return labelCnt;
}

저는 위로 5px, 아래로 5px 인접하는 직사각형을 합쳤습니다. 

인접하는 범위를 조절하려면 line 46을 수정하시면 됩니다.

사용된 구조체 입니다. 저는 openCV를 사용할 수 없기에ㅜ 만들어서 쓰고 있습니다.

아마 cv::Rect를 사용하셔도 될 것 같습니다.

typedef struct // 라벨
{
    MK_Point    center;                            // 중심점
    MK_Rect     boundingRect;                    // 박스
}MK_Label;
 
 
typedef struct MK_Point    
{
    int x;
    int y;
}MK_Point;
 
typedef struct MK_Rect     
{
    int width;
    int height;
    int x;
    int y;
}MK_Rect;

위 코드는 아직 버그? 가 있는 것 같습니다ㅜ

output이 최대 직사각형이 나오긴 하지만..

혹시 간단한 버그 해결 방법을 아시는 분은...ㅎㅎ 

알려주시면 정말 감사하겠습니다.