#include "const.h"
#include "macros.h"
/* ======================================================== */
/* A simple approach to component labeling similiar to */
/* L. Thurfjell, E. Bengtsson, and B. Nordin, A new three- */
/* dimensional connected components labeling algorithm with */
/* simultaneous object feature extraction capability, */
/* GMIP 54, 1992, 357-364. */
/* Note: there is an error in the algorithm above. It has */
/* corrected in this implementation. */
/* ======================================================== */
void ComponentLabeling(A, Rows, Cols, NoOfLabels, Area)
int Rows, Cols, A[][Cols], *NoOfLabels, Area[];
{
int Label=0, Upper, Left, MinL, MaxL;
int Equiv[MAX_LABELS];
int i, j, k;
/* First pass */
for (i=0; i<Rows; i++)
for (j=0; j<Cols; j++) {
if (A[i][j]==0) continue;
Upper = (i==0) ? 0 : A[i-1][j];
Left = (j==0) ? 0 : A[i][j-1];
if ((Upper==0) && (Left==0)) {
Label++;
if (Label >= MAX_LABELS) {
printf("Error in component labeling: equivalence table too small\n");
printf("Increase the value of MAX_LABELS in const.h !!!\n");
exit(1);
}
A[i][j] = Equiv[Label] = Label;
continue;
}
if (Upper==0) {
A[i][j] = Left;
continue;
}
if (Left==0) {
A[i][j] = Upper;
continue;
}
if (Upper==Left) {
A[i][j] = Upper;
continue;
}
/* Record label equivalence */
MinL = Min(Upper, Left);
MaxL = Max(Upper, Left);
A[i][j] = MinL;
while (Equiv[MaxL] != MaxL) MaxL = Equiv[MaxL];
while (Equiv[MinL] != MinL) MinL = Equiv[MinL];
if (MaxL >= MinL)
Equiv[MaxL] = MinL;
else
Equiv[MinL] = MaxL;
}
/* Build equivalence class */
*NoOfLabels = 0;
for (k=1; k<=Label; k++) {
if (Equiv[k] == k) {
(*NoOfLabels)++;
Equiv[k] = *NoOfLabels;
} else
Equiv[k] = Equiv[Equiv[k]];
}
/* Second pass */
if (*NoOfLabels >= MAX_REGIONS) {
printf("Error in component labeling: region area list too small\n");
printf("Increase the value of MAX_REGIONS in const.h !!!\n");
exit(1);
}
for (k=1; k<=*NoOfLabels; k++) Area[k] = 0;
for (i=0; i<Rows; i++)
for (j=0; j<Cols; j++) {
if (A[i][j]==0) continue;
A[i][j] = Equiv[A[i][j]];
Area[A[i][j]]++;
}
}
/* ============================================ */
/* Component labeling constrained to image area */
/* R1 <= row <= R2, C1 <= col <= C2 */
/* ============================================ */
void ConstrainedComponentLabeling(A, Cols, R1, R2, C1, C2, NoOfLabels, Area)
int Cols, R1, R2, C1, C2, A[][Cols], *NoOfLabels, Area[];
{
int Label=0, Upper, Left, MinL, MaxL;
int Equiv[MAX_LABELS];
int i, j, k;
/* First pass */
for (i=R1; i<=R2; i++)
for (j=C1; j<=C2; j++) {
if (A[i][j]==0) continue;
Upper = A[i-1][j];
Left = A[i][j-1];
if ((Upper==0) && (Left==0)) {
Label++;
if (Label >= MAX_LABELS) {
printf("Error in constrained component labeling: equivalence table too small\n");
printf("Increase the value of MAX_LABELS in const.h !!!\n");
exit(1);
}
A[i][j] = Equiv[Label] = Label;
continue;
}
if (Upper==0) {
A[i][j] = Left;
continue;
}
if (Left==0) {
A[i][j] = Upper;
continue;
}
if (Upper==Left) {
A[i][j] = Upper;
continue;
}
/* Record label equivalence */
MinL = Min(Upper, Left);
MaxL = Max(Upper, Left);
A[i][j] = MinL;
while (Equiv[MaxL] != MaxL) MaxL = Equiv[MaxL];
while (Equiv[MinL] != MinL) MinL = Equiv[MinL];
if (MaxL >= MinL)
Equiv[MaxL] = MinL;
else
Equiv[MinL] = MaxL;
}
/* Build equivalence class */
*NoOfLabels = 0;
for (k=1; k<=Label; k++) {
if (Equiv[k] == k) {
(*NoOfLabels)++;
Equiv[k] = *NoOfLabels;
} else
Equiv[k] = Equiv[Equiv[k]];
}
/* Second pass */
if (*NoOfLabels >= MAX_REGIONS) {
printf("Error in constrained component labeling: region area list too small\n");
printf("Increase the value of MAX_REGIONS in const.h !!!\n");
exit(1);
}
for (k=1; k<=*NoOfLabels; k++) Area[k] = 0;
for (i=R1; i<=R2; i++)
for (j=C1; j<=C2; j++) {
if (A[i][j]==0) continue;
A[i][j] = Equiv[A[i][j]];
Area[A[i][j]]++;
}
}
