/*
* lmap.h -- Datastructure 'lm_t' and operations.
*
* lm_t is a temporary datastructure, used by function 'processImage()'.
*
*/
#ifndef _LMAP_H_
#define _LMAP_H_
/*****************************************************************************
*
* lm_t -- "Label Map" data structure
* ----
*
* This data structure combines the following four logical container
* data types:
*
* 1- Map: label --> comp_t.
* Quick access to the comp_t data with counts for the component
* given the label of the component.
*
* 2- Map: label --> label.
* Register of equivalence mappings from one component label to
* component another label.
*
* 3- List of free labels.
* 4- List of used labels.
* These allow iteration over the used labels,
* and moving any used label to the free list.
*
*---
*
* Logically, 1 and 2 are MAP (associative array) datastructures: We specify
* the label of the four-connected component as the key, and want to retrieve
* the data for this label.
*
* For number 4, the used list, a stack or list isn't sufficient, because
* we want to be able to remove any given user label from the used list
* (in order then to return it to the free list), which needs random access
* into the used list. So number 4 also needs to be a "map".
*
* In each case, the key into the map is label number of a component.
*
*
*---
*
* In our application, the above logical datatypes are used for storing
* temporary data while processing the input image line by line. The
* maximum possible number of labels needed while computing the new
* lineAccumulator contents (for the current line) from the previous
* lineAcc is the maximum possible number of different components that
* can occur in two successive lines. The latter equals Size_X, the number
* of pixels in a horizontal line, as shown in the diagram below.
*
* +---+---+---+---+---+---+---+
* | X | . | X | . | X | . | X | line i
* +---+---+---+---+---+---+---+
* | . | X | . | X | . | X | . | line i+1
* +---+---+---+---+---+---+---+
*
* |<-------Size_X pixels----->| . = black pixel (blank)
* X = white pixel
*
* This means that for our application, each of the four logical
* datatypes only needs to hold data for at most Size_X different
* label values.
*
* The fastest possible map for integer keys is a simple old-fashioned
* array. The very limited range of label values makes the array
* implementation suitable.
*
* Therefore I implemented the MAP datatypes all as a fixed-size array,
* where the aray index is the label number. The array size is N = Size_X+1:
* label number 0 (which represents the empty label value) is unused, and
* therefore the first array element is also unused.
*
* Since all four logical datatypes use the same label range, and the
* data stored by all of them concern the same set of components, it
* was possible to combine the four into one single array, as follows:
*
* index
* +-----------+--------+-------+-------+
* 1 | compData | lblEq | prev | next | -- data for label '1'
* +-----------+--------+-------+-------+
* 2 | compData | lblEq | prev | next | -- data for label '2'
* +-----------+--------+-------+-------+
* 3 | compData | lblEq | prev | next | -- data for label '3'
* +-----------+--------+-------+-------+
* ... ... ... ... ...
* +-----------+--------+-------+-------+
* N-1 | compData | lblEq | prev | next | -- data for label 'N-1'
* +-----------+--------+-------+-------+
*
* The array elements are 'structs' (lmElem_t) with the following members:
*
* comp_t compData -- Current counter values for the component.
* This implements logical datatype "1".
*
* label_t lblEq -- Stores the mapping "label1 --> lblEq", where
* label1 is the index of the current array element.
* This implements logical datatype "2".
*
* label_t prev -- Index (pointer) to previous item in free list
* or in used list.
*
* label_t next -- Index (pointer) to previous item in free list
* or in used list.
*
* The fields 'prev' and 'next' implement the free list and the used list,
* which are both double-linked lists implemented in a fixed-size array.
* The free list being the counterpart of the used list (if a given label
* is in one list, it is not in the other, and vice versa), it is possible
* and convenient to combine the free-list and used-list implementations,
* and in the array implementation used here I have done so.
* Both lists are chains of lmElem_t structs, with the array index of the
* first list element stored outside the array (in iFreeFirst for the free
* list and in iUsedFirst for the used list).
*
*
*---
*
* The array elements contain two more members, not yet mentioned above:
*
* int uf -- Boolean that tells whether the element is in the
* used list (uf = 1) or in the free list (uf = 0).
* This member is not absolutely necessary and is only
* used as an extra check.
*
* int iLine -- Line number in the image in which the label was
* last used.
*
* The member 'iLine' is important; it is needed for the recycling of
* label numbers that are no longer used. As explained in the comments
* at the start of "processimage.c", this recycling is necessary to
* make it possible to keep the set of label numbers down to a very
* limited set (which in turn is necessary to make the array
* implementation realistic for the MAP containers).
*
* The algorithm in "processimage.c" updates the iLine for a label (by a
* call to "lm_updateLineNr()") whenever the label is used. The member
* iLine therefore always contains the line number in which the label was
* last used. Labels not used since line L can therefore be recognized
* from the fact that their iLine is less than (or equal to) L.
*
* After the processing of each complete line, the algorithm in
* "processimage.c" calls the function "lm_purgeOldLabels()" to return
* old labels that are no longer used to the free list. Parameter to the
* function is a threshold line number L (meaning that everything older
* than L must be recycled).
*
* To prevent that "lm_purgeOldLabels()" has to do a SEARCH through the
* used list to find all labels with iLine < L, the operations on lm_t
* make sure that the used list is always kept SORTED on the line
* number iLine, from the newest items (large iLine value) at the
* beginning to the oldest items (small iLine value) at the end.
* The sort order is maintained by inserting NEW labels (with the
* latest iLine values) into the used list at the beginning; and by
* implementing the function "lm_updateLineNr()" in such a way that a
* label that is updated to a newer (= larger) line number is moved to
* the beginning of the used list.
* With this sorted used list, the function "lm_purgeOldLabels()" no
* longer needs to search; all it has to do is simply to remove items
* from the END of the used list (as long as iLine < L).
*
*/
#include "comp.h" /* comp_t */
#include "label.h" /* label_h, LABEL_EMPTY */
/*************************************************************************
* Structs
************************************************************************/
/* struct lmElem_t --
* Element of the array lm_t::pArr[].
* lm_t::pArr[k] stores the data for label number 'k'.
*
* Notes:
* - If the label has no equivalence data, then lblEq == LABEL_EMPTY.
* - If the label has empty comp_t data, this is represented as
* compData.pixels == 0.
*/
typedef struct lmElem_
{
comp_t compData; /* Component data. */
label_t lblEq; /* Mapping to the label 'lblEq' (equivalence). */
int iLine; /* Line number where label used last. */
int uf; /* 0 = free, 1 = used. */
label_t prev; /* Prev label in free/used list. */
label_t next; /* Next label in free/used list. */
}
lmElem_t;
/* struct lm_t --
* One datastructure for all four logical containers.
*
* Notes:
* - iFreeFirst has value LABEL_EMPTY if the free list is empty.
* - iUsedFirst has value LABEL_EMPTY if the used list is empty.
*/
typedef struct lm_ /*Label Map. */
{
label_t N; /* Size of array pArr[]. */
lmElem_t * pArr;
label_t iFreeFirst; /* First item in free list. */
label_t iUsedFirst; /* First item in used list. */
label_t iUsedLast; /* Last item in used list. */
}
lm_t;
/*************************************************************************
* Function protoypes
************************************************************************/
/*
* 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 );
/*
* lm_free() --
* Deallocate the internal members of the fl_t instance.
*/
void lm_free( lm_t * pLM );
/* lm_clearDataOfLabel() --
* Clear compData, lblEq, and iLine of the label 'lbl'.
*/
void lm_clearDataOfLabel(
lm_t * pLM,
label_t lbl );
/* 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 );
/* 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 );
/* 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 );
/* lm_updateLineNr() --
* Register that label 'lbl' was last used in line number 'in_iLine'.
*/
void lm_updateLineNr(
lm_t * pLM,
label_t lbl,
int in_iLine );
/* lm_addEquiv() --
* Register the equivalence that label 'from' maps to label 'to'.
*/
void lm_addEquiv(
lm_t * pLM,
label_t from,
label_t 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 );
/* 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 );
/* 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 );
/*
* Finalize the center-of-mass computation for the component with
* label 'lbl',
* and then call the usr-defined function 'usrOutComp()' to write
* this final comp_t for label 'lbl' to output.
*/
void lm_outComp(
lm_t * pLM,
label_t lbl,
void (*usrOutComp)( comp_t const * ) );
/*
* lm_purgeOldLabels --
* Purge from lm_t all labels that have a line number smaller than in_iY.
*
* Write the comp_t for the purged labels to the output, using the
* user-defined function 'usrOutComp()'.
*/
void lm_purgeOldLabels(
lm_t * pLM,
int in_iY, /*Line Number. */
void (*usrOutComp)( comp_t const * ) ); /*Callback fn. */
#endif /*_LMAP_H_ */