2015
05-23

# Contour Tracing

In computer vision, objects of interest are often represented as regions of 1′s in a binary image (bitmap). An important task in the identification of objects is to trace the contour (also called border and boundary) in an object.

We assume that the bitmap does not contain any 1′s on the borders. To trace the contour of a single object, we can use a procedure known as the Moore boundary tracking algorithm as follows:

Scan from the top row to the bottom row, from left to right in each row, until an object pixel is found. Call this object pixel b0, and its west background neighbour c0.
Examine the 8 neighbours of b0, starting at c0 and proceeding in clockwise direction. Let b1 denote the first neighbour object pixel encountered, and c1 be the background neighbour immediately preceeding b1. Store the locations of b0 and b1, and append b0 and b1 to the contour.
Let b = b1 and c = c1
Let the 8 neighbours of b, starting at c and proceeding in a clockwise direction, be denoted as n1, n2, …, n8. Find the first object neighbour nk in this sequence.
Let b = nk, c = n(k-1). Append b to the contour.
Repeat steps 4 and 5 until b = b0 and the next contour point found is b1. The last two points b0 and b1 are repeated and should not be appended to the contour again.
The first steps of the algorithm is illustrated in the figure below (only the pixels on the boundary are labelled 1 in this bitmap):

In this problem, you will be given a bitmap with at most 200 rows and 200 columns. The bitmap contains a number of objects. You are to determine the length of the contour for each object in the bitmap using the procedure above. In the bitmap, a pixel intensity of 0 represents the background, and a pixel intensity of 1 represents an object pixel. Two pixels with intensity 1 belong to the same object if there is a path from one pixel to another consisting of only 1′s, and the path is allowed to follow in any of the 8 compass directions. The borders of the bitmap (first row, last row, first column, last column) contain only background pixels. Any object consisting of fewer than 5 pixels should be ignored as it is most likely noise. None of the objects in the bitmap has holes. Equivalently, there exists a path of background pixels following only the 4 main compass directions (N, S, E, W) for every pair of background pixels in the bitmap.

The input consists of a number of cases. Each case starts with two positive integers on a line, indicating the number of rows (R) and the number of columns (C) in the bitmap. The bitmap is given in the following R lines each containing a string of 0′s and 1′s of length C. The input is terminated by a case starting with R = C = 0. The last case should not be processed.

The input consists of a number of cases. Each case starts with two positive integers on a line, indicating the number of rows (R) and the number of columns (C) in the bitmap. The bitmap is given in the following R lines each containing a string of 0′s and 1′s of length C. The input is terminated by a case starting with R = C = 0. The last case should not be processed.

7 7
0000000
0011110
0111100
0011100
0111100
0111100
0000000
16 7
0000000
0011110
0111100
0011100
0111100
0111100
0000000
0011000
0100110
0000000
0001000
0010100
0010000
0111000
0111000
0000000
4 4
0000
0000
0010
0000
0 0

Case 1
14
Case 2
8 12 14
Case 3
no objects found

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <cstring>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <complex>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <queue>
#include <iterator>

typedef long long LL;
typedef long double LD;

using namespace std;
// START_PRINTING_HERE

const int MX=205,MQ=MX*MX;
const int dx[8]={0,-1,-1,-1,0,1,1,1};
const int dy[8]={-1,-1,0,1,1,1,0,-1};

int T,n,m,i,j,k,l,x,y,nx,ny,b0x,b0y,b1x,b1y,bx,by,cx,cy,fi,fr,cnt,qx[MQ],qy[MQ],u[MX][MX];
vector <int> ans;
char s[MX][MX];

int main() {
#ifndef LOCAL
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
#endif
while (++T) {
scanf("%d%d",&n,&m);
if (n==0 && m==0) break;
for (i=0; i<n; i++) scanf("%s",s[i]);
ans.clear();
for (i=0; i<n; i++) for (j=0; j<m; j++) if (s[i][j]=='1' && u[i][j]!=T) {
fi=0; fr=1;
qx[0]=i;
qy[0]=j;
u[i][j]=T;
while (fi<fr) {
x=qx[fi];
y=qy[fi++];
for (k=0; k<8; k++) {
nx=x+dx[k];
ny=y+dy[k];
if (nx>=0 && nx<n && ny>=0 && ny<m && s[nx][ny]=='1' && u[nx][ny]!=T) {
qx[fr]=nx;
qy[fr++]=ny;
u[nx][ny]=T;
}
}
}
if (fr<5) continue;
b0x=bx=i;
b0y=by=j;
cx=i;
cy=j-1;
cnt=0;
first=true;
while (++cnt) {
//                printf("%d %d %d %d\n",bx,by,cx,cy);
for (k=0; k<8; k++) if (cx-bx==dx[k] && cy-by==dy[k]) break;
for (l=0; l<8; l++) {
x=bx+dx[(k+l)%8];
y=by+dy[(k+l)%8];
//                    printf("look to %d %d\n",x,y);
assert(x>=0 && x<n && y>=0 && y<m);
if (s[x][y]=='1') break;
}
if (first) {
b1x=x;
b1y=y;
first=false;
} else if (b0x==bx && b0y==by && b1x==x && b1y==y) break;
cx=bx+dx[(k+l+7)%8];
cy=by+dy[(k+l+7)%8];
bx=x;
by=y;
}
ans.push_back(cnt-1);
//            puts("----");
}
printf("Case %d\n",T);
if (bad) puts("no objects found"); else {
sort(ans.begin(),ans.end());
for (i=0; i<ans.size(); i++) {
if (i) putchar(' ');
printf("%d",ans[i]);
}
puts("");
}
}
return 0;
}