Embedded Systems November 2000 Vol13_12

Issue link:

Contents of this Issue


Page 105 of 189

;; ID :II i1 LISTING f* medfil t. c Median filter in C Median filter in C*/ #include f* Size of the data buffer; Length of the sequence. */ #define NWIDTH 11 /* Smaller than any datum */ #define STOPPER 0 int medfilterCint datum) { struct pair { f* Pointers forming List Linked in sorted order *f struct pair *point; /* Values to sort */ unsigned int value; }; f* Buffer of nwidth pairs */ static struct pair buffer[NWIDTHJ; f* pointer into circular buffer of data */ static struct pair *datpoint={buffer}; f* chain stopper. */ static struct pair small={NULL,STOPPER} f* pointer to head (Largest) of Linked List.*/ static struct pair big={&small,O} ; f* pointer to successor of replaced data item *f struct pair *SUccessor f* pointer used to scan down the sorted List *f struct pair *scan f* previous value of scan *f struct pair *scanold f* pointer to median */ struct pair *median; f* No stoppers allowed. */ ifCdatum == STOPPER) datum = STOPPER + 1; f* increment and wrap data in pointer.*/ if( C++datpoint - buffer) >= NWIDTH) datpoint=buffer; f* Copy in new datum *f datpoint->value=datum f* save pointer to old value's successor */ successor=datpoint->point f* median initially just before head of chain *f median = &big f* scanold initially points to scan pointer. *f scanold = &big f* points to first (Largest) datum in chain *f scan = big.point f* Loop through the chain *f Listing 1 continued on p. 108 104 NOVEMBER 2000 Embedded Syst ems Programming Every median calcula tio n leaves us with a sorted array that is very nearly wha t we need in orde• - to p.-oduce the next median value. All we need to do is to remove the oldest data value from the list and me rge in the newly mea- sured one. That i all , I say, but to do it requires accessing the data a rray in two incompatible ways: in time order (removing the oldest) and in orde r of magnitude (me rge in the next). One scheme fo r doing that is shown in Figure 2. The fi gure shows each measw-ed datum be ing re presented as a two- eleme nt structure. These structures contain bo th the o bse rved value and a po inte r to the structure holding th e next smalle r value. The struc- tures are stored in time o • -de r in the circu la r buffe r buffe r, with da t poi nt indicating th e o ld est value. Simply in crementing da t poi nt (and wra p- ping it when necessary) and sto ring th e next datum takes care of re plac- ing th e o ld est d a ta value by the newest. (Actually it d oes tha t replace- me n t o nly afte r the array is fu ll . Befo re the n it ju t fi lls the a rray, as we wo uld wa nt it to d o.) The structure big hold a pointe r to the structure holding the la rgest datum; its value field is unused , but it must be a structure like the othe rs so it can be pointed to by the same kind of po in te rs. The structure smalL is an end marker. It must hold a null pointer to fail equality compa risons with othe r list pointe rs. In its value field it needs a stoppe r, some thing smalle r th an any datum. Having replaced the old data value, all we need to do is to upda te the links. The re are two tasks involved , and if we add a third we find tha t the same logic will handle starting up from an empty array. (A chess player might call that "array fi ll ing en passant.") The obvi- ous two tasks are to remove the old datum from the linked list and link in the new one in its proper place. The third task is to step a pointer down tha t list half as fas t as we scan fo r other purposes, and stop our scan a t the end

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems November 2000 Vol13_12