/* * lmap.c -- Datastructure 'lm_t' and operations. * * lm_t is a temporary datastructure, used by function 'processImage()'. * * See the header file lmap.h for comments on 'lm_t', and for comments * on the implementation of the lm_t functions. * */ #include "lmap.h" /* lm_t, lmElem_t */ #include "comp.h" /* comp_t */ #include#include /* malloc(), free() */ #include /* INT_MAX, INT_MIN */ /**************************************************************************** * Local functions ****************************************************************************/ #ifdef DEBUG # include # include static void DBG_print( char const * pFmt, ... ) { va_list ap; va_start( ap, pFmt ); vprintf( pFmt, ap ); va_end( ap ); } static void DBG_dumpUF( lm_t const * pLM ) { printf( "\tUsed: { " ); label_t k; for ( k = pLM->iUsedFirst; k != LABEL_EMPTY; k = pLM->pArr[k].next ) { printf( "%u(%d) ", k, pLM->pArr[k].iLine ); } printf( "} " ); printf( "Free: { " ); for ( k = pLM->iFreeFirst; k != LABEL_EMPTY; k = pLM->pArr[k].next ) { printf( "%u ", k ); } printf( "}\n" ); } #else /*DEBUG */ # define DBG_print( a, ... ) /*empty replacement value*/ # define DBG_dumpUF( a ) /*empty replacement value*/ #endif /*DEBUG */ #ifdef DEBUG /* Check that 'lbl' holds a valid label number. */ static void __checkLabel( lm_t const * pLM, label_t lbl ) { assert( lbl != LABEL_EMPTY ); assert( lbl < pLM->N ); } #else /*DEBUG */ # define __checkLabel( a, b ) /*empty replacement value*/ #endif /*DEBUG */ /* Clear the data for one component */ static void __comp_clear( comp_t * p ) { p->pixels = 0; p->bary_x = 0; p->bary_y = 0; p->min_x = INT_MAX; p->min_y = INT_MAX; p->max_x = INT_MIN; p->max_y = INT_MIN; } static int __min( int a, int b ) { return ( a <= b ? a : b ); } static int __max( int a, int b ) { return ( a >= b ? a : b ); } /* * Basic operations on the free and used lists. * * The free list only implements stack operations (push, pop). * * The used list implements the following operations: * - Insert a given label number at the beginning of the list (push); * - Remove a given label number from the list, where this label number * can sit at any position in the list (remove). */ static void freelist_push( lm_t * pLM, label_t i1 ) { __checkLabel( pLM, i1 ); if ( pLM->iFreeFirst != LABEL_EMPTY ) { pLM->pArr[ pLM->iFreeFirst ].prev = i1; } pLM->pArr[i1].next = pLM->iFreeFirst; pLM->pArr[i1].prev = LABEL_EMPTY; pLM->iFreeFirst = i1; pLM->pArr[i1].uf = 0; /* Mark label i1 as free */ } static label_t freelist_pop( lm_t * pLM ) /*Return popped label.*/ { assert( pLM->iFreeFirst != LABEL_EMPTY ); /*Free list must not be empty.*/ label_t i1 = pLM->iFreeFirst; pLM->iFreeFirst = pLM->pArr[i1].next; pLM->pArr[ pLM->iFreeFirst ].prev = LABEL_EMPTY; return i1; } /* Insert label i1 at the beginning of the used list */ static void usedlist_push( lm_t * pLM, label_t i1 ) { __checkLabel( pLM, i1 ); if ( pLM->iUsedFirst != LABEL_EMPTY ) { pLM->pArr[ pLM->iUsedFirst ].prev = i1; } pLM->pArr[i1].next = pLM->iUsedFirst; pLM->pArr[i1].prev = LABEL_EMPTY; pLM->iUsedFirst = i1; if ( pLM->iUsedLast == LABEL_EMPTY ) { pLM->iUsedLast = i1; } /* Mark label i1 as used. */ pLM->pArr[i1].uf = 1; } /* Remove any label i1 from the used list */ static void usedlist_remove( lm_t * pLM, label_t i1 ) { __checkLabel( pLM, i1 ); assert( pLM->pArr[i1].uf == 1 ); /*Label 'i1' must be in the used list. */ assert( pLM->iUsedFirst != LABEL_EMPTY ); /*Used list must not be empty.*/ assert( pLM->iUsedLast != LABEL_EMPTY ); /*Used list must not be empty.*/ if ( pLM->pArr[i1].prev == LABEL_EMPTY ) { pLM->iUsedFirst = pLM->pArr[i1].next; } else { label_t iPrev = pLM->pArr[i1].prev; pLM->pArr[iPrev].next = pLM->pArr[i1].next; } if ( pLM->pArr[i1].next == LABEL_EMPTY ) { pLM->iUsedLast = pLM->pArr[i1].prev; } else { label_t iNext = pLM->pArr[i1].next; pLM->pArr[iNext].prev = pLM->pArr[i1].prev; } } /**************************************************************************** * Exported functions ****************************************************************************/ /* * lm_alloc() -- * * User instantiates an lm_t instance, then calls lm_alloc to * allocate the internal members of that lm_t instance. * * Parameter: * in_nLabels = the number of different labels that the map must store. * * Returns 0 on failure, 1 on success. */ int lm_alloc( lm_t * pLM, int in_nLabels ) { pLM->pArr = (lmElem_t*)malloc( (in_nLabels+1) * sizeof(lmElem_t) ); if ( pLM->pArr == NULL ) { return 0; } pLM->N = in_nLabels+1; return 1; } /* * lm_free() -- * Deallocate the internal members of the fl_t instance. */ void lm_free( lm_t * pLM ) { free( pLM->pArr ); } /* lm_clearDataOfLabel() -- * Clear compData, lblEq, and iLine of the label 'lbl'. */ void lm_clearDataOfLabel( lm_t * pLM, label_t lbl ) { __checkLabel( pLM, lbl ); lmElem_t * p = pLM->pArr + lbl; __comp_clear( &( p->compData ) ); p->lblEq = LABEL_EMPTY; p->iLine = 0; } /* lm_init() -- * Initialize lm_t instance for beginning with a new image: * - Each label's comp_t data is made empty * - Each label has empty equivalence (i.e. maps to no other label) * - All labels in the free list; used list empty. */ void lm_init( lm_t * pLM ) { label_t k; /* Clear compData, lblEq, and iLine */ for ( k = 1; k < pLM->N; k++ ) /*element 0 unused.*/ { lm_clearDataOfLabel( pLM, k ); } /* Initialize the free and used lists: All labels are initially in * the free list */ pLM->iFreeFirst = 1; pLM->iUsedFirst = LABEL_EMPTY; pLM->iUsedLast = LABEL_EMPTY; for ( k = 1; k < pLM->N; k++ ) /*element 0 unused.*/ { pLM->pArr[k].prev = ( k > 1 ? k-1 : LABEL_EMPTY ); pLM->pArr[k].next = ( k < pLM->N-1 ? k+1 : LABEL_EMPTY ); pLM->pArr[k].uf = 0; } } /* lm_getFreeLabel -- * Take the first free label, * remove it from the free list and insert it into the used list. * Return this label. */ label_t lm_getFreeLabel( lm_t * pLM ) { label_t i1 = freelist_pop( pLM ); usedlist_push( pLM, i1 ); return i1; } /* lm_returnLabel() -- * Remove the label 'i1' from the used list, * and insert it into the free list. */ void lm_returnLabel( lm_t * pLM, label_t i1 ) { usedlist_remove( pLM, i1 ); freelist_push( pLM, i1 ); } /* lm_updateLineNr() -- * Register that label 'lbl' was last used in line number 'in_iLine'. * * Implementation: * We have to keep the used list sorted, * from new (= large) line numbers at the beginning * to old (= small) line numbers at the end. * Therefore apart from changing the line number of the item 'lbl' * we also move the item 'lbl' to the beginning of the used list. */ void lm_updateLineNr( lm_t * pLM, label_t lbl, int in_iLine ) { __checkLabel( pLM, lbl ); assert( pLM->pArr[lbl].uf ); /* The new iLine of 'lbl' can't be smaller than its old value. */ assert( in_iLine >= pLM->pArr[lbl].iLine ); /* Change line number. */ pLM->pArr[lbl].iLine = in_iLine; /* Move item 'lbl' to the beginning of the used list. * * (As an optimization, we do this only when necessary, namely when * item 'lbl' is not already at the beginning. This optimization makes * sense because with big solid components, long strings of pixels with * the same label occur often.) */ if ( pLM->iUsedFirst != lbl ) { /* Assert the correct used-list ordering: The iLine of the new list * head must not be smaller than that of the previous list head. */ assert( in_iLine >= pLM->pArr[ pLM->iUsedFirst ].iLine ); usedlist_remove( pLM, lbl ); usedlist_push( pLM, lbl ); /*Insert at beginning.*/ } } /* lm_addEquiv() -- * Register the equivalence that label 'from' maps to label 'to'. */ void lm_addEquiv( lm_t * pLM, label_t from, label_t to ) { __checkLabel( pLM, from ); label_t * pEq = &( pLM->pArr[from].lblEq ); /* Check old value of lblEq */ assert( (*pEq == LABEL_EMPTY) || (*pEq == to) ); *pEq = to; } /* lm_getEquiv() -- * Retrieve equivalence. * Returns LABEL_EMPTY if 'from' does not map to any other component. */ label_t lm_getEquiv( lm_t * pLM, label_t from ) { __checkLabel( pLM, from ); return pLM->pArr[from].lblEq; } /* lm_addPixelToComp() -- * Add to the comp_t of with label 'lbl' the data for the single * pixel at location in_x, in_y. */ void lm_addPixelToComp( lm_t * pLM, label_t lbl, int in_x, int in_y ) { __checkLabel( pLM, lbl ); comp_t * pC = &( pLM->pArr[lbl].compData ); pC->pixels += 1; pC->bary_x += (double)in_x; pC->bary_y += (double)in_y; pC->min_x = __min( pC->min_x, in_x ); pC->min_y = __min( pC->min_y, in_y ); pC->max_x = __max( pC->max_x, in_x ); pC->max_y = __max( pC->max_y, in_y ); } /* lm_mergeCompIntoComp() -- * Merge component lblSrc into lblDst (i.e. add the comp_t data for * component lblSrc into the comp_t of component lblDst), * then clear the entry for label 'lblSrc' in the component list. */ void lm_mergeCompIntoComp( lm_t * pLM, label_t lblDst, label_t lblSrc ) { __checkLabel( pLM, lblDst ); __checkLabel( pLM, lblSrc ); comp_t * pDst = &( pLM->pArr[lblDst].compData ); comp_t * pSrc = &( pLM->pArr[lblSrc].compData ); pDst->pixels += pSrc->pixels; pDst->bary_x += pSrc->bary_x; pDst->bary_y += pSrc->bary_y; pDst->min_x = __min( pDst->min_x, pSrc->min_x ); pDst->min_y = __min( pDst->min_y, pSrc->min_y ); pDst->max_x = __max( pDst->max_x, pSrc->max_x ); pDst->max_y = __max( pDst->max_y, pSrc->max_y ); __comp_clear( pSrc ); } /* * Finalize the center-of-mass computation for the component with * label 'lbl', * and then write this final comp_t for label 'lbl' to output. */ void lm_outComp( lm_t * pLM, label_t lbl, void (*usrOutComp)( comp_t const * ) ) { __checkLabel( pLM, lbl ); comp_t * pC = &( pLM->pArr[lbl].compData ); pC->bary_x /= (double)(pC->pixels); pC->bary_y /= (double)(pC->pixels); usrOutComp( pC ); } /* * lm_purgeOldLabels -- * Purge from lm_t all labels that have a line number smaller than in_iY. * * Writes the comp_t for the purged labels to the output, using the * user-defined function 'usrOutComp()'. * * Implementation: * Since the used list is always kept sorted on iLine from new (=large) * line numbers at the beginning to old (=small) line numbers at the end, * we don't need to SEARCH the used list for the labels to be removed. * We can simply remove labels from the END of the used list. */ void lm_purgeOldLabels( lm_t * pLM, int in_iY, /*Line Number. */ void (*usrOutComp)( comp_t const * ) ) /*Callback fn. */ { DBG_dumpUF( pLM ); #ifdef DEBUG /* Assert the condition that the used list is sorted on * line number (iLine), from large to small. */ int iLinePrev = INT_MAX; label_t j; for ( j = pLM->iUsedFirst; j != LABEL_EMPTY; j = pLM->pArr[j].next ) { assert( pLM->pArr[j].iLine <= iLinePrev ); iLinePrev = pLM->pArr[j].iLine; } #endif label_t kRem; while ( kRem = pLM->iUsedLast, (kRem != LABEL_EMPTY) && (pLM->pArr[kRem].iLine < in_iY) ) { DBG_print( "\tPurge label %u\n", kRem ); if ( pLM->pArr[kRem].compData.pixels > 0 ) { DBG_print( "\tComponent %u --> out\n", kRem ); lm_outComp( pLM, kRem, usrOutComp ); } lm_clearDataOfLabel( pLM, kRem ); /*Init for reuse of label.*/ lm_returnLabel( pLM, kRem ); } }