Binary Image에서 Object의 개수를 세는 방법 — Corner Pattern과 Induction 증명
Binary Image와 좌표 표현
Binary Image란 각 픽셀이 0(배경) 또는 1(전경)의 값만 가지는 이미지이다. 이 이미지에서 각 픽셀의 위치는 (row, col) 좌표로 표현한다.
임의의 픽셀을 기준으로 인접한 픽셀을 정의하는 방식에는 두 가지가 있다.
- 4-neighborhood: 상하좌우 4개의 픽셀만 인접으로 간주한다.
- 8-neighborhood: 상하좌우 + 대각선 방향까지 총 8개의 픽셀을 인접으로 간주한다.
이 글에서는 4-neighborhood 기준의 연결성을 사용한다.
문제 정의: "Object"란 무엇인가?
위 Binary Image에서 Object의 개수는 몇 개인가?
아마 모두가 자연스럽게 2개라고 답할 것이다.
하지만 이 질문에 답하기 위해서는 먼저 두 가지를 분명히 해야 한다.
- Object가 무엇인가?
- 왜 두 덩어리가 "서로 다른" Object인가?
이런 질문에 대해 고민하지 않았겠지만, 해당 질문을 하지 않은 채로 2개라고 답하는 것은 성급한 답변일 수 있다.
두 번째 질문에 대한 답을 생각하면 첫 번째 질문의 답도 자연스럽게 따라온다. 두 덩어리가 서로 다른 Object인 이유는, 한 덩어리의 어떤 픽셀에서 출발하여 인접한 전경 픽셀만을 따라가는 경로(path)가 다른 덩어리까지 존재하지 않기 때문이다.
따라서 Object를 다음과 같이 정의할 수 있다.
Object: 서로 간에 인접한 전경 픽셀들을 따라가는 경로(path)가 존재하는 픽셀들의 집합
과연 이런 정의를 내리지 않고 하는 답변도 옳다고 할 수 있을까?
이런 정의 없이 제대로 된 개수를 셀 수 있을까?
Corner Pattern을 이용한 Object 개수 세기
Object의 개수를 체계적으로 세기 위해 Corner Pattern이라는 방법을 사용할 수 있다.
Corner의 종류
전경 픽셀이 이루는 도형의 꼭짓점(corner)에는 두 가지 종류가 있다.
- External Corner (E): 도형의 바깥쪽으로 볼록한 꼭짓점
- Internal Corner (I): 도형의 안쪽으로 오목한 꼭짓점
빠짐없이 세는 방법: Raster Scan
Corner를 하나도 빼먹지 않고, 중복 없이 세려면 당연하게도 잘 세야한다.
무작정 세는 것이 아니라 잘.
이를 위해서는 체계적인 순서가 필요하다.
가장 기본적인 방법은 래스터 스캔(Raster Scan) 으로, 이미지의 왼쪽 위부터 오른쪽으로, 위에서 아래로 순차적으로 훑으면서 각 위치의 corner를 확인하는 것이다.
Object 개수 공식
이렇게 세어낸 External Corner의 수 E와 Internal Corner의 수 I에 대해 다음 공식이 성립한다.
# of Objects = (E - I) / 4
직관적으로, 아무런 홈이 없는 단순한 직사각형(예를 들면 3x3)은 External Corner만 4개이고 Internal Corner는 0개이므로 (4 - 0) / 4 = 1이 된다.
도형이 복잡해져 오목한 부분이 생기면 Internal Corner가 추가되지만, 그에 상응하는 External Corner도 함께 추가되어 E - I = 4가 유지된다.
하지만 이것은 직관일 뿐이다. 이 공식이 항상 성립한다는 것을 어떻게 증명할 수 있을까?
Mathematical Induction을 이용한 증명
Induction이란
Mathematical Induction(수학적 귀납법) 은 자연수에 대한 명제를 증명하는 기법이다.
- Base Case: n = 1일 때 명제가 성립함을 보인다.
- Inductive Step: n = k일 때 성립한다고 가정하면(귀납 가설), n = k + 1일 때도 성립함을 보인다.
이 두 단계를 보이면, 모든 자연수 n에 대해 명제가 성립한다고 결론 내릴 수 있다.
증명 전략
하나의 Object가 n개의 픽셀로 이루어져 있을 때 E - I = 4 임을 증명하려 한다.
- Base Case: 한 칸짜리 Object(n = 1)는 External Corner가 4개, Internal Corner가 0개이므로 E - I = 4. 성립한다.
- Inductive Step: 기존에 k개의 픽셀로 이루어진 Object에서 E(k) - I(k) = 4가 성립한다고 가정하자. 여기에 인접한 한 칸을 추가하여 k + 1개가 되었을 때, E(k+1) - I(k+1) = 4가 여전히 성립함을 보여야 한다.
이미지적으로 해당 전략을 다시 풀어서 표현하자면,
한 칸짜리 Object에서 임의의 인접한 방향에 한 칸씩 반복적으로 붙인다면 결국 어떤 형태의 Object라도 생성할 수 있다.
이 때 한 칸짜리는 이미 공식이 성립하니까, 한 칸을 추가할 때 여전히 E-I=4를 유지한다면, 결국 모든 형태의 Object에서 E-I=4라고 결론 내릴 수 있다.
핵심은 한 칸이 추가될 때 E - I의 변화량 Δ(E - I)가 항상 0임을 보이는 것이다.
그렇다면:
E(k+1) - I(k+1) = E(k) + ΔE - I(k) - ΔI = (E(k) - I(k)) + (ΔE - ΔI) = 4 + 0 = 4
을 증명하여 해당 공식이 항상 성립함을 보일 수 있을 것이다.
분석 범위: 3×3 Window
새로운 한 칸이 추가되었을 때, corner의 생성과 소멸이 발생하는 영역은 새로운 칸을 중심으로 한 3×3 window 뿐이다. 이 window 바깥의 corner는 전혀 영향을 받지 않는다.
새로운 칸(중심)의 4개 꼭짓점 각각은, 주변 픽셀 3개와 함께 2×2 영역을 형성한다.
좌상단, 우상단, 좌하단, 우하단 4개의 2x2 영역에 대해서 관찰해야한다는 듯이다.
이 2×2 영역 내 전경 픽셀의 수에 따라 corner 유형이 결정된다.
- 전경 픽셀 1개 → External Corner
- 전경 픽셀 3개 → Internal Corner
- 전경 픽셀 0, 2, 4개 → Corner 아님
중심에 새 칸을 추가하면 각 꼭짓점에서 전경 픽셀 수가 1 증가하므로, 가능한 변화는 다음과 같다.
- 0 → 1: Corner 아님 → External Corner 생성 → ΔE = +1 → Δ(E-I) = +1
- 1 → 2: External Corner 소멸 → ΔE = -1 → Δ(E-I) = 1
- 2 → 3: Internal Corner 생성 → ΔI = +1 → Δ(E-I) = 1
- 3 → 4: Internal Corner 소멸 → ΔI = -1 → Δ(E-I) = +1
따라서 4개 꼭짓점의 Δ(E-I)를 모두 합산하여 0이 되면 증명이 완성된다. 주변 칸의 배치에 따른 모든 경우를 아래에서 검증한다.
아래 그림에서
·는 아직 비어있는 중심 칸이며,1은 전경 픽셀,0은 배경이다. 회전이나 대칭으로 동일한 경우는 하나의 대표 배치만 확인한다.
경우 1: 주위에 아무 칸도 없는 경우
0 0 0
0 · 0
0 0 0
중심 칸이 기존 Object의 어떤 픽셀과도 인접하지 않으므로, 기존 Object에 칸을 "추가"하는 상황이 아니다. 이 경우는 Inductive Step의 전제(기존 Object에 연결된 칸을 추가)에 해당하지 않으므로 고려할 필요가 없다.
경우 2: 주위에 한 칸이 있는 경우
추가 전: 추가 후:
0 0 0 0 0 0
0 · 0 → 0 1 0
0 1 0 0 1 0
4개 꼭짓점의 변화:
- 좌상단: 0→1 → Δ(E-I) = +1
- 우상단: 0→1 → Δ(E-I) = +1
- 좌하단: 1→2 → Δ(E-I) = -1
- 우하단: 1→2 → Δ(E-I) = -1
합계: +1 +1 -1 -1 = 0 → Δ(E-I) = 0 ✓
경우 3: 주위에 두 칸이 있는 경우
추가 전: 추가 후:
0 0 0 0 0 0
0 · 0 → 0 1 0
1 1 0 1 1 0
4개 꼭짓점의 변화:
- 좌상단: 0→1 → Δ(E-I) = +1
- 우상단: 0→1 → Δ(E-I) = +1
- 좌하단: 2→3 → Δ(E-I) = -1
- 우하단: 1→2 → Δ(E-I) = -1
합계: +1 +1 -1 -1 = 0 → Δ(E-I) = 0 ✓
경우 4: 주위에 세 칸이 있는 경우
이 경우는 배치에 따라 두 가지 대표 형태가 존재한다.
형태 ① — 일자 배치
추가 전: 추가 후:
0 0 0 0 0 0
0 · 0 → 0 1 0
1 1 1 1 1 1
4개 꼭짓점의 변화:
- 좌상단: 0→1 → +1
- 우상단: 0→1 → +1
- 좌하단: 2→3 → -1
- 우하단: 2→3 → -1
합계: +1 +1 -1 -1 = 0 ✓
형태 ② — ㄱ자 배치
추가 전: 추가 후:
0 0 0 0 0 0
1 · 0 → 1 1 0
1 1 0 1 1 0
4개 꼭짓점의 변화:
- 좌상단: 1→2 → -1
- 우상단: 0→1 → +1
- 좌하단: 3→4 → +1
- 우하단: 1→2 → -1
합계: -1 +1 +1 -1 = 0 ✓
경우 5: 주위에 네 칸이 있는 경우
추가 전: 추가 후:
0 0 0 0 0 0
1 · 0 → 1 1 0
1 1 1 1 1 1
4개 꼭짓점의 변화:
- 좌상단: 1→2 → -1
- 우상단: 0→1 → +1
- 좌하단: 3→4 → +1
- 우하단: 2→3 → -1
합계: -1 +1 +1 -1 = 0 ✓
경우 6: 주위에 다섯 칸이 있는 경우
형태 ① — 양쪽 연결
추가 전: 추가 후:
0 0 0 0 0 0
1 · 1 → 1 1 1
1 1 1 1 1 1
4개 꼭짓점의 변화:
- 좌상단: 1→2 → -1
- 우상단: 1→2 → -1
- 좌하단: 3→4 → +1
- 우하단: 3→4 → +1
합계: -1 -1 +1 +1 = 0 ✓
형태 ② — 한쪽 대각 연결
추가 전: 추가 후:
1 0 0 1 0 0
1 · 0 → 1 1 0
1 1 1 1 1 1
4개 꼭짓점의 변화:
- 좌상단: 2→3 → -1
- 우상단: 0→1 → +1
- 좌하단: 3→4 → +1
- 우하단: 2→3 → -1
합계: -1 +1 +1 -1 = 0 ✓
경우 7: 주위에 여섯 칸이 있는 경우
추가 전: 추가 후:
1 0 0 1 0 0
1 · 1 → 1 1 1
1 1 1 1 1 1
4개 꼭짓점의 변화:
- 좌상단: 2→3 → -1
- 우상단: 1→2 → -1
- 좌하단: 3→4 → +1
- 우하단: 3→4 → +1
합계: -1 -1 +1 +1 = 0 ✓
경우 8: 주위에 일곱 칸이 있는 경우
추가 전: 추가 후:
1 0 1 1 0 1
1 · 1 → 1 1 1
1 1 1 1 1 1
4개 꼭짓점의 변화:
- 좌상단: 2→3 → -1
- 우상단: 2→3 → -1
- 좌하단: 3→4 → +1
- 우하단: 3→4 → +1
합계: -1 -1 +1 +1 = 0 ✓
경우 9: 주위에 여덟 칸이 있는 경우
1 1 1
1 · 1
1 1 1
이 경우 중심에 칸을 추가하면 구멍(hole)을 메우는 상황이 된다. 이 글에서는 구멍이 없는 Object를 다루고 있으므로 이 경우는 고려하지 않는다.
최종 Induction 정리
위의 모든 경우에서 Δ(E - I) = 0 임을 확인하였다. 이를 바탕으로 Induction을 완성한다.
증명하고자 하는 것: 하나의 Object가 n개의 픽셀로 이루어져 있을 때, E(n) - I(n) = 4 (n ≥ 1)
Base Case (n = 1):
한 칸짜리 Object는 External Corner 4개, Internal Corner 0개이므로
E(1) - I(1) = 4.
성립한다.
Inductive Step:
n = k일 때 E(k) - I(k) = 4 가 성립한다고 가정한다.
n = k + 1일 때, 즉 기존 Object에 인접한 한 칸을 추가하면:
- E(k+1) = E(k) + ΔE
- I(k+1) = I(k) + ΔI
따라서:
- E(k+1) - I(k+1) = E(k) + ΔE - I(k) - ΔI = (E(k) - I(k)) + (ΔE - ΔI) = 4 + 0 = 4
위의 경우 분석에서 모든 배치에 대해 ΔE - ΔI = 0 임을 보였으므로, n = k + 1일 때에도 E - I = 4 가 성립한다.
따라서 수학적 귀납법에 의해, 임의의 크기의 Object에 대해 E - I = 4가 항상 성립한다.
Object가 여러 개인 경우, 각 Object마다 E - I = 4이므로 전체 이미지에서는 E - I = 4 × (Object의 개수)가 된다. 이를 정리하면:
# of Objects = (E - I) / 4
결론
주어진 공식 (E - I) / 4 에 대해 Mathematical Induction을 통한 엄밀한 증명을 수행하였다.
먼저 "Object란 무엇인가?"라는 근본적인 질문에서 출발하여, Object를 연결된 경로가 존재하는 전경 픽셀들의 집합으로 명확히 정의하였다.
그 후 External Corner와 Internal Corner의 개념을 도입하고, 한 칸이 추가될 때 E - I의 변화량이 항상 0임을 9가지 경우로 나누어 모두 검증하였다.
이를 통해 Induction의 귀납 단계를 완성하고, 최종적으로 공식의 정당성을 증명하였다.
직관적으로 그럴듯해 보이는 공식도, 이처럼 체계적으로 경우를 나누고 하나하나 검증함으로써 비로소 "증명"이 된다.
스스로 고민하고 논리를 세워 증명하는 습관은, 어떤 분야에서든 사고력을 키우는 데 있어 가장 중요한 훈련이다.