간단한 윤곽선 검출로 정사각형 찾기 (Find Squares with Simple Edge Detection)

삼성 C형 전체 링크

 

에지 디텍션은 영상의 밝기의 변화를 검출하여 윤곽선을 찾는 방법이다.

여기서는 간단히 2차원 배열에 겹쳐져 있는 정사각형을 검출해보자.

 

makeRectangle 함수는 좌표 (sr, sc) ~ (er, ec)의 사각형을 모두 1로 증가시키는 함수다.

#define MAX (20)

int originalMap[MAX][MAX];

void makeRectangle(int sr, int sc, int er, int ec)
{
	for (int r = sr; r < er; r++)
		for (int c = sc; c < ec; c++)
			originalMap[r][c]++;
}

 

여기서 만들 정사각형의 최소 사이즈는 4라고 가정한다.

makeRectangle(5, 5, 10, 10); // 길이가 5인 정사각형
makeRectangle(8, 7, 17, 16); // 길이가 9인 정사각형
makeRectangle(1, 1, 7, 7);   // 길이가 6인 정사각형
makeRectangle(9, 1, 13, 19); // 높이가 4, 너비가 18인 직사각형

 

아래 함수를 실행하면 2차원 배열의 상태를 알 수 있다.

1보다 큰 값은 사각형이 여러 개 겹친 상태다.

showMap(originalMap);

 

makeRectangle로 호출된 부분을 표시하면 다음과 같다.

 

showMap 함수는 아래를 참고하자.

void showMap(int map[MAX][MAX])
{
	for (int r = 0; r < MAX; r++)
	{
		for (int c = 0; c < MAX; c++)
			printf("%2d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

---

윤곽선 검출

 

위의 2차원 배열은 하나의 픽셀로 볼 수 있다.

윤곽선은 갑작스러운 밝기 변화에 대해 나타나기 때문에, 배열 값의 차이(미분)를 이용해 윤곽선을 검출한다.

for (int i = 0; i < MAX; i++)
	for (int k = 0; k < MAX; k++)
		tmpMap[i + 1][k + 1] = map[i][k];

for (int i = 1; i <= MAX; i++)
	for (int k = 1; k <= MAX; k++)
		diffMap[i][k] = tmpMap[i][k] - tmpMap[i][k - 1];

 

2차원 배열의 픽셀의 오른쪽 값을 픽셀의 왼쪽 값으로 빼면 1이나 -1이 연속되는 구간이 생기게 된다.

이 구간이 바로 정사각형의 왼쪽과 오른쪽의 모서리가 될 확률이 높다.

갑작스럽게 밝기가 변하는 곳이 모서리가 될 확률이 높기 때문이다.

original vs diff

 

이제 1과 -1이 연속되는 구간이 생긴 2차원 배열 diff에서 다시 윤곽선이 될 만한 곳을 체크한다. 

즉, 왼쪽과 오른쪽을 검출하였으니, 위와 아래도 검출한다.

#define LEFT_UP (0)
#define RIGHT_UP (1)
#define LEFT_DOWN (2)
#define RIGHT_DOWN (3)

for (int i = 1; i <= MAX; i++)
{
	for (int k = 1; k <= MAX; k++)
	{
		if (diffMap[i][k] < diffMap[i + 1][k])
		{
			squareCheck[LEFT_UP][i][k] = 1;
			squareCheck[RIGHT_DOWN][i][k] = 1;
		}
		else if (diffMap[i][k] > diffMap[i + 1][k])
		{
			squareCheck[RIGHT_UP][i][k] = 1;
			squareCheck[LEFT_DOWN][i][k] = 1;
		}
	}
}

 

위의 코드는 아래의 0 / 1 또는 -1 / 0의 좌표를 squareCheck에 표시한다.

 

이제 위의 정보를 바탕으로 사각형을 찾아보자.

주어진 정사각형의 최소 사이즈는 4이므로 아래와 같이 4 부터 큰 길이를 찾는다.

int minSize = 4;
for (int i = 1; i <= MAX; i++)
{
	for (int k = 1; k <= MAX; k++)
	{
		for (int size = minSize; i + size <= MAX && k + size <= MAX; size++)
		{
			if (squareCheck[LEFT_UP][i][k] == 1 &&
				squareCheck[RIGHT_UP][i][k + size] == 1 &&
				squareCheck[LEFT_DOWN][i + size][k] == 1 &&
				squareCheck[RIGHT_DOWN][i + size][k + size] == 1)
			{
				printf("Square : %d %d %d %d, length : %d\n", i, k, i + size, k + size, size);
			}
		}
	}
}

 

diff하면서 한 칸씩 옮겼기 때문에 원래 입력된 좌표보다 k가 1씩 증가하였다.

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (20)

int originalMap[MAX][MAX];

void makeRectangle(int sr, int sc, int er, int ec)
{
	for (int r = sr; r < er; r++)
		for (int c = sc; c < ec; c++)
			originalMap[r][c]++;
}

void showMap(int map[MAX][MAX])
{
	for (int r = 0; r < MAX; r++)
	{
		for (int c = 0; c < MAX; c++)
			printf("%2d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void showMap(int map[MAX + 1][MAX + 1])
{
	for (int r = 0; r < MAX; r++)
	{
		for (int c = 0; c < MAX; c++)
			printf("%2d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

#define LEFT_UP (0)
#define RIGHT_UP (1)
#define LEFT_DOWN (2)
#define RIGHT_DOWN (3)

void edgeDetection(int map[MAX][MAX])
{
	int tmpMap[MAX + 1][MAX + 1] = { 0 };
	int diffMap[MAX + 1][MAX + 1] = { 0 };
	int squareCheck[4][MAX + 1][MAX + 1] = { 0 };

	for (int i = 0; i < MAX; i++)
		for (int k = 0; k < MAX; k++)
			tmpMap[i + 1][k + 1] = map[i][k];

	for (int i = 1; i <= MAX; i++)
		for (int k = 1; k <= MAX; k++)
			diffMap[i][k] = tmpMap[i][k] - tmpMap[i][k - 1];

	showMap(diffMap);

	for (int i = 1; i <= MAX; i++)
	{
		for (int k = 1; k <= MAX; k++)
		{
			if (diffMap[i][k] < diffMap[i + 1][k])
			{
				squareCheck[LEFT_UP][i][k] = 1;
				squareCheck[RIGHT_DOWN][i][k] = 1;
			}
			else if (diffMap[i][k] > diffMap[i + 1][k])
			{
				squareCheck[RIGHT_UP][i][k] = 1;
				squareCheck[LEFT_DOWN][i][k] = 1;
			}
		}
	}

	int minSize = 4;
	for (int i = 1; i <= MAX; i++)
	{
		for (int k = 1; k <= MAX; k++)
		{
			for (int size = minSize; i + size <= MAX && k + size <= MAX; size++)
			{
				if (squareCheck[LEFT_UP][i][k] == 1 &&
					squareCheck[RIGHT_UP][i][k + size] == 1 &&
					squareCheck[LEFT_DOWN][i + size][k] == 1 &&
					squareCheck[RIGHT_DOWN][i + size][k + size] == 1)
				{
					printf("Square : %d %d %d %d, length : %d\n", i, k, i + size, k + size, size);
				}
			}
		}
	}

}

int main()
{
	makeRectangle(5, 5, 10, 10); // 길이가 5인 정사각형
	makeRectangle(8, 7, 17, 16); // 길이가 9인 정사각형
	makeRectangle(1, 1, 7, 7);   // 길이가 6인 정사각형
	makeRectangle(9, 1, 13, 19); // 높이가 4, 너비가 18인 직사각형

	//showMap(originalMap);

	edgeDetection(originalMap);

	return 0;
}