/* ----------------------- */ /* --- ecc_rosenfeld.c --- */ /* ----------------------- */ // Copyright (c) 2013-2014 Lionel Lacassagne, All Rights Reserved // Laboratoire de Recherche en Informatique // Universite Paris-Sud / CNRS /* -- Contient les implementations avancees de l'algorithme de Rosenfeld -- */ #include #include #include #ifdef CLI #include "nrc_os_config.h" #include "nrc.h" #endif #include "util.h" #include "ecc_common.h" #include "ecc_features.h" #include "ecc_rosenfeld.h" // --------------------------------- uint32 FindRoot(uint32 *T, uint32 e) // --------------------------------- { uint32 r; r = e; while (T[r] < r) { r = T[r]; } return r; } // -------------------------------------------------------------- uint32 FindRoot_Features(uint32 *T, uint32 e, RegionStats *Stats) // -------------------------------------------------------------- { // ne sert pas, sauf a creer des backdoors uint32 r; r = FindRoot(T,e); RegionStats_Accumulate_Stats1_From_Index(Stats, r, e); return r; } // ---------------------------------------- void SetRoot(uint32 *T, uint32 e, uint32 r) // ---------------------------------------- { while (T[e] < e) { e = T[e]; } T[e] = r; } // ----------------------------- uint32 Find(uint32 *T, uint32 e) // ----------------------------- { // never used in Rosenfeld ? uint32 r; r = FindRoot(T, e); SetRoot(T, e, r); return r; } // ------------------------------------------- uint32 Union0(uint32 *T, uint32 ei, uint32 ej) // ------------------------------------------- { // version de la publication uint32 ri, rj; ri = FindRoot(T, ei); if (ei!=ej) { rj = FindRoot(T, ej); if (ri > rj) { ri = rj; } SetRoot(T, ej, ri); } SetRoot(T, ei, ri); return ri; } // ----------------------------------------- uint32 Union1(uint32 *T, uint32 i, uint32 j) // ----------------------------------------- { // version modifiee Lionel Lacassagne uint32 r, ri, rj; uint32 k; ri = FindRoot(T, i); rj = FindRoot(T, j); if (ri != rj) { r = ri < rj ? ri : rj; SetRoot(T, i, r); SetRoot(T, j, r); } else { r = ri; k = i > j ? i : j; SetRoot(T, k, r); } return ri; } // ------------------------------------------- uint32 Union2(uint32 *T, uint32 ei, uint32 ej) // ------------------------------------------- { return Union0(T, ei, ej); // original //return Union1(T, ei, ej); // Lionel Lacassagne } /* -------------------------------------------------------------- */ uint32 Union4(uint32 *T, uint32 e1, uint32 e2, uint32 e3, uint32 e4) /* -------------------------------------------------------------- */ { uint32 r12, r34; r12 = Union2(T, e1, e2); r34 = Union2(T, e3, e4); return Union2(T, r12, r34); } // --------------------------------------------------------------- uint32 updateTable_Rosenfeld(uint32 *T, uint32 e, uint32 epsillon) // --------------------------------------------------------------- { // notations e == v, epsillon == u avec v>u (v forcement different de u) return Union0(T, e, epsillon); // original } // -------------------------------------------------------------------------------------------- uint32 updateTable_Features_Rosenfeld(uint32 *T, uint32 e, uint32 epsillon, RegionStats *Stats) // -------------------------------------------------------------------------------------------- { uint32 r; // racine totale = epsillon uint32 re; // racine de e > r re = FindRoot(T, e); // backdoor: sans cela Accumulate est faux r = updateTable_Rosenfeld(T, e, epsillon); RegionStats_Accumulate_Stats1_From_Index(Stats, epsillon, re); return r; } // ---------------------------- void Flatten(uint32 *T, int ne) // ---------------------------- { // equivalent a solveTable_Rosenfeld // fermeture transitive sans pack // (presence de trous dans les numeros d'etiquettes) int32 i, k; k = 1; for (i = 1; i <= ne; i++) { T[i] = T[T[i]]; } } // ---------------------------- int FlattenL(uint32 *T, int ne) // ---------------------------- { // equivalent a solvePackTable_Rosenfeld // fermeture transitive *avec* pack // (pas de trous dans les numeros d'etiquettes) int32 i, k; k = 1; for (i = 1; i <= ne; i++) { if ((int) T[i] < i) { T[i] = T[T[i]]; } else { T[i] = k; k++; } } return k - 1; } // ---------------------------------------------- uint32 solveTable_Rosenfeld(uint32 *T, uint32 ne) // ---------------------------------------------- { // equivalent a Flatten // fermeture transitive sans pack // (presence de trous dans les numeros d'etiquettes) uint32 e; for (e = 1; e <= ne; e++) { T[e] = T[T[e]]; } return ne; } // -------------------------------------------------- uint32 solvePackTable_Rosenfeld(uint32 *T, uint32 ne) // -------------------------------------------------- { // equivalent a FlattenL // fermeture transitive *avec* pack // (pas de trous dans les numeros d'etiquettes) uint32 e; uint32 na = 0; // ancetre packe for (e = 1; e <= ne; e++) { if (e != T[e]) { T[e] = T[T[e]]; } else { T[e] = ++na; } } return na; } // --------------------------------------------------------------------------- uint32 solveTable_Features_Rosenfeld(uint32 *T, uint32 ne, RegionStats *Stats) // --------------------------------------------------------------------------- { // fermeture transitive *sans* pack // (presence de trous dans les numeros d'etiquettes) // Calculs des Features pour la composante uint32 e, r; for (e = 1; e <= ne; e++) { r = T[T[e]]; if (r < e) { T[e] = r; RegionStats_Accumulate_Stats1_From_Index(Stats, r, e); } } return ne; } // ------------------------------------------------------------------------------- uint32 solvePackTable_Features_Rosenfeld(uint32 *T, uint32 ne, RegionStats *Stats) // ------------------------------------------------------------------------------- { // fermeture transitive *avec* pack // Calculs des Features pour la composante uint32 e, r; uint32 na = 0; for (e = 1; e <= ne; e++) { r = T[T[e]]; if (r < e) { T[e] = r; RegionStats_Accumulate_Stats1_From_Index(Stats, r, e); } else { // r == e <=> ancetre na++; T[r] = na; RegionStats_Copy_Stats1_From_Index(Stats, na, r); } } return na; } // ============================================ // == line-labeling (lineLabeling_*) ========== // ============================================ // ------------------------------------------------------------------------------------------------------------------ uint32 lineLabeling_Rosenfeld_UF_Org1_4C(uint8 **X, int i, int width, uint32 **E, uint32 *T, uint32 ne, uint32 nemax) // ------------------------------------------------------------------------------------------------------------------ { int j; uint8 x; uint32 e; uint32 e2,e4; uint32 r2,r4; // version de WU avec union find // correct: on remonte a la racine for (j = 0; j < width; j++) { x = X[i][j]; if (x) { e2 = E[i - 1][j]; e4 = E[i][j - 1]; // nouvel element if ((e2 == 0) && (e4 == 0)) { e = ++ne; E[i][j] = e; } else { // etiquettes identiques if (e2 == e4) { e = e2; E[i][j] = e; } else { // cas general r2 = FindRoot(T, e2); r4 = FindRoot(T, e4); e = ui32MinNonNul2(r2, r4); ECC_DEBUG(printf("%d->%d %d->%d min = %d\n", e2, r2, e4, r4, e)); if ((e2) && (e2 != e)) SetRoot(T, e2, e); if ((e4) && (e4 != e)) SetRoot(T, e4, e); E[i][j] = e; } } } else { E[i][j] = 0; } // x } // j return ne; } // ------------------------------------------------------------------------------------------------------------------ uint32 lineLabeling_Rosenfeld_UF_Org1_8C(uint8 **X, int i, int width, uint32 **E, uint32 *T, uint32 ne, uint32 nemax) // ------------------------------------------------------------------------------------------------------------------ { int j; uint8 x; uint32 e; uint32 e1, e2, e3, e4; uint32 r1, r2, r3, r4; for (j = 0; j < width; j++) { x = X[i][j]; if (x) { e1 = E[i-1][j-1]; e2 = E[i-1][j ]; e3 = E[i-1][j+1]; e4 = E[i ][j-1]; // nouvel element if ((e1==0) && (e2==0) && (e3==0) && (e4==0)) { e = ++ne; E[i][j] = e; } else { // etiquettes identiques if((e1 == e2) && (e1 == e3) && (e1 == e4)) { e = e1; E[i][j] = e; } else { // cas general r1 = FindRoot(T, e1); r2 = FindRoot(T, e2); r3 = FindRoot(T, e3); r4 = FindRoot(T, e4); e = ui32MinNonNul4(r1, r2, r3, r4); // modification 2014: // ek est remplacé par rk = Quick-Union //if((r1) && (r1 != e)) SetRoot(T, r1, e); //if((r2) && (r2 != e)) SetRoot(T, r2, e); //if((r3) && (r3 != e)) SetRoot(T, r3, e); //if((r4) && (r4 != e)) SetRoot(T, r4, e); // modification 2015: // rk remplace par ek, comme dans l'algorithme original if((r1) && (r1 != e)) SetRoot(T, e1, e); if((r2) && (r2 != e)) SetRoot(T, e2, e); if((r3) && (r3 != e)) SetRoot(T, e3, e); if((r4) && (r4 != e)) SetRoot(T, e4, e); E[i][j] = e; } } } else { E[i][j] = 0; } // x } // j return ne; } // ------------------------------------------------------------------------------------------------------------------ uint32 lineLabeling_Rosenfeld_UF_Org2_4C(uint8 **X, int i, int width, uint32 **E, uint32 *T, uint32 ne, uint32 nemax) // ------------------------------------------------------------------------------------------------------------------ { int j; uint8 x; uint32 e; uint32 e2, e4; uint32 r2, r4; for(j=0; j%d %d->%d min = %d\n", e2, r2, e4, r4, e)); if((e2) && (e2 != e)) SetRoot(T, e2, e); if((e4) && (e4 != e)) SetRoot(T, e4, e); E[i][j] = e; } else { if(e2) { r2 = FindRoot(T, e2); e = r2; SetRoot(T, e2, e); // inutile E[i][j] = e; } else { r4 = FindRoot(T, e4); e = r4; SetRoot(T, e4, e); // inutile E[i][j] = e; } } } } } else { E[i][j] = 0; } // x } // j return ne; } // ------------------------------------------------------------------------------------------------------------------ uint32 lineLabeling_Rosenfeld_UF_Org3_4C(uint8 **X, int i, int width, uint32 **E, uint32 *T, uint32 ne, uint32 nemax) // ------------------------------------------------------------------------------------------------------------------ { // version Org1, mais sans le cas des etiquettes identiques. Nouveaute 2015 int j; uint8 x; uint32 e; uint32 e2,e4; uint32 r2,r4; // version de WU avec union find // correct: on remonte a la racine for(j=0; j %d\n", ne, na)); if (Stats) { ECC_FEATURES(featuresComputation(E, height, width, Stats)); } // optimal table reset for next call initT(T, ne); return na; } // --------------------------------------------------------------------------------------------------------------------------- uint32 Rosenfeld_UF_Org1_8C(uint8 **X, int height, int width, uint32 **E, uint32 *T, uint32 *A, uint32 nemax, RegionStats *Stats) // --------------------------------------------------------------------------------------------------------------------------- { uint32 ne, na=-1; // nombre d'etiquettes, d'ancetres //uint32 nemax = height * width /2; ECC_VERBOSE(printf("====================================\n")); ECC_VERBOSE(printf("=== Rosenfeld Union-Find Org1 8C ===\n")); ECC_VERBOSE(printf("====================================\n")); // version de WU avec union find // correct: on remonte a la racine ne = Rosenfeld_UF_Org1_8C_pass1(X, height, width, E, T, nemax, Stats); ECC_VERBOSE2(display_ui32vector_number(T, 0, ne, "%3d", "T")); ECC_VERBOSE2(display_ui32matrix_positive(E,0, height-1, 0, width-1, 3, "E0")); //Flatten(T, ne); na = ne; ECC_SOLVE(na = FlattenL(T, ne)); ECC_LABEL2(applyTable(E, height, width, T, E)); ECC_VERBOSE2(display_ui32matrix_positive(E,0, height-1, 0, width-1, 3, "E1")); ECC_VERBOSE(printf("%d -> %d\n", ne, na)); if(Stats) { ECC_FEATURES(featuresComputation(E, height, width, Stats)); } // optimal table reset for next call initT(T, ne); return na; } // --------------------------------------------------------------------------------------------------------------------------- uint32 Rosenfeld_UF_Org2_4C(uint8 **X, int height, int width, uint32 **E, uint32 *T, uint32 *A, uint32 nemax, RegionStats *Stats) // --------------------------------------------------------------------------------------------------------------------------- { uint32 ne, na = -1; // nombre d'etiquettes, d'ancetres ECC_VERBOSE(printf("====================================\n")); ECC_VERBOSE(printf("=== Rosenfeld Union-Find Org2 4C ===\n")); ECC_VERBOSE(printf("====================================\n")); // version de WU avec union find // correct: on remonte a la racine // avec traitement des cas particuliers qd e2 ou e4 est nulle et pas l'autre // fait gagner sur les petites granularites ne = Rosenfeld_UF_Org2_4C_pass1(X, height, width, E, T, nemax, Stats); ECC_VERBOSE2(display_ui32vector_number(T, 0, ne, "%3d", "T")); ECC_VERBOSE2(display_ui32matrix_positive(E,0, height-1, 0, width-1, 3, "E0")); //Flatten(T, ne); na = ne; ECC_SOLVE(na = FlattenL(T, ne)); ECC_LABEL2(applyTable(E, height, width, T, E)); ECC_VERBOSE2(display_ui32matrix_positive(E,0, height-1, 0, width-1, 3, "E1")); ECC_VERBOSE(printf("%d -> %d\n", ne, na)); if(Stats) { ECC_FEATURES(featuresComputation(E, height, width, Stats)); } // optimal table reset for next call initT(T, ne); return na; } // --------------------------------------------------------------------------------------------------------------------------- uint32 Rosenfeld_UF_Org3_4C(uint8 **X, int height, int width, uint32 **E, uint32 *T, uint32 *A, uint32 nemax, RegionStats *Stats) // --------------------------------------------------------------------------------------------------------------------------- { uint32 ne, na = -1; // nombre d'etiquettes, d'ancetres //uint32 nemax = height * width /2; ECC_VERBOSE(printf("====================================\n")); ECC_VERBOSE(printf("=== Rosenfeld Union-Find Org3 4C ===\n")); ECC_VERBOSE(printf("====================================\n")); // version de WU avec union find // correct: on remonte a la racine ne = Rosenfeld_UF_Org3_4C_pass1(X, height, width, E, T, nemax, Stats); ECC_VERBOSE2(display_ui32vector_number(T, 0, ne, "%3d", "T")); ECC_VERBOSE2(display_ui32matrix_positive(E,0, height-1, 0, width-1, 3, "E0")); //Flatten(T, ne); na = ne; ECC_SOLVE(na = FlattenL(T, ne)); ECC_LABEL2(applyTable(E, height, width, T, E)); ECC_VERBOSE2(display_ui32matrix_positive(E,0, height-1, 0, width-1, 3, "E1")); ECC_VERBOSE(printf("%d -> %d\n", ne, na)); if(Stats) { ECC_FEATURES(featuresComputation(E, height, width, Stats)); } // optimal table reset for next call initT(T, ne); return na; } // --------------------------------------------------------------------------------------------------------------------------- uint32 Rosenfeld_UF_Org3_8C(uint8 **X, int height, int width, uint32 **E, uint32 *T, uint32 *A, uint32 nemax, RegionStats *Stats) // --------------------------------------------------------------------------------------------------------------------------- { uint32 ne, na=-1; // nombre d'etiquettes, d'ancetres //uint32 nemax = height * width /2; ECC_VERBOSE(printf("====================================\n")); ECC_VERBOSE(printf("=== Rosenfeld Union-Find Org1 8C ===\n")); ECC_VERBOSE(printf("====================================\n")); // version de WU avec union find // correct: on remonte a la racine ne = Rosenfeld_UF_Org3_8C_pass1(X, height, width, E, T, nemax, Stats); ECC_VERBOSE2(display_ui32vector_number(T, 0, ne, "%3d", "T")); ECC_VERBOSE2(display_ui32matrix_positive(E,0, height-1, 0, width-1, 3, "E0")); //Flatten(T, ne); na = ne; ECC_SOLVE(na = FlattenL(T, ne)); ECC_LABEL2(applyTable(E, height, width, T, E)); ECC_VERBOSE2(display_ui32matrix_positive(E,0, height-1, 0, width-1, 3, "E1")); ECC_VERBOSE(printf("%d -> %d\n", ne, na)); if(Stats) { ECC_FEATURES(featuresComputation(E, height, width, Stats)); } // optimal table reset for next call initT(T, ne); return na; }