medians_1D.h File Reference

Function prototypes for 1-D median search. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef float	pixelvalue
	Typedef for input data.
Functions
void	swap (pixelvalue *, pixelvalue *)
	Function implementing basic pixel swapping algorithm.
pixelvalue	quick_select (pixelvalue a[], int n)
	Function implementing quickselect algorithm.
pixelvalue	kth_smallest (pixelvalue *, int, int)
	Rank-order filter for Wirth's algorithm (requires macro).
pixelvalue	wirth (pixelvalue a[], int n)
	Function wrapper for kth_smallest to get Wirth's median.
pixelvalue	torben (pixelvalue a[], int n)
	Function implementing Torben's algorithm.

---

Detailed Description

Function prototypes for 1-D median search.

These are various C routines for doing a 1-dimensional median search. QuickSelect and Wirth are the fastest for nominal size input data, but require a copy of the array in memory. Torben is much slower in general, but operates on a read-only data set of arbitrary size.

All the functions take the same input parameters and return the same output. The typedef should be changed as appropriate for the input data.

Definition in file medians_1D.h.

---

Typedef Documentation

typedef pixelvalue

Typedef for input data.

This should be changed according to the data being filtered, e.g., filtering 8-bit gray-scale images would use "int".

Definition at line 105 of file medians_1D.h.

---

Function Documentation

pixelvalue kth_smallest	(	pixelvalue *	,
		int	,
		int
	)

Rank-order filter for Wirth's algorithm (requires macro).

Function : kth_smallest()

• In : array of elements, # of elements in the array, rank k
• Out : one element
• Job : find the kth smallest element in the array
• Note : use the median_WIRTH() function to get the median

Reference:

Author: Wirth, Niklaus (1976) Algorithms + data structures = programs, Prentice-Hall, Englewood Cliffs, NJ. Original code by Nicolas Devillard - 1998. Public domain. Modified by Stephen Arnold <stephen.arnold@acm.org> August 2005.

pixelvalue quick_select	(	pixelvalue	a[],
		int	n
	)

Function implementing quickselect algorithm.

Function : quick_select()

• In : array of elements, # of elements in the array
• Out : one element

Definition at line 70 of file medians_1D.c.

References swap().

Referenced by bench().

                                    {
    int low, high ;
    int median;
    int middle, ll, hh;

    low = 0 ; high = n-1 ; median = (low + high) / 2;
    for (;;) {
        if (high <= low) /* One element only */
            return a[median] ;

        if (high == low + 1) {  /* Two elements only */
            if (a[low] > a[high])
                swap(&a[low], &a[high]) ;
            return a[median] ;
        }

    /* Find median of low, middle and high items; swap into position low */
        middle = (low + high) / 2;
        if (a[middle] > a[high])    swap(&a[middle], &a[high]) ;
        if (a[low] > a[high])       swap(&a[low], &a[high]) ;
        if (a[middle] > a[low])     swap(&a[middle], &a[low]) ;

    /* Swap low item (now in position middle) into position (low+1) */
        swap(&a[middle], &a[low+1]) ;

    /* Nibble from each end towards middle, swapping items when stuck */
        ll = low + 1;
        hh = high;
        for (;;) {
            do ll++; while (a[low] > a[ll]) ;
            do hh--; while (a[hh]  > a[low]) ;

            if (hh < ll)
            break;

            swap(&a[ll], &a[hh]) ;
        }
        
        /* Swap middle item (in position low) back into correct position */
        swap(&a[low], &a[hh]) ;
        
        /* Re-set active partition */
        if (hh <= median)
            low = ll;
        if (hh >= median)
            high = hh - 1;
    }
}   

Here is the call graph for this function:

Here is the caller graph for this function:

void swap	(	pixelvalue *	a,
		pixelvalue *	b
	)

Function implementing basic pixel swapping algorithm.

Macro left-over from initial implementation. Need to change to a real function and let the compiler do the work

Definition at line 53 of file medians_1D.c.

Referenced by kth_smallest(), and quick_select().

                                        {
    register pixelvalue t;
    t=*a; *a=*b; *b=t;
    return;
}

Here is the caller graph for this function:

pixelvalue torben	(	pixelvalue	m[],
		int	n
	)

Function implementing Torben's algorithm.

Function : torben()

• In : array of elements, # of elements in the array
• Out : one element

Definition at line 178 of file medians_1D.c.

Referenced by bench().

                              {
    int         i, less, greater, equal, half;
    pixelvalue  min, max, guess, maxltguess, mingtguess;

    half = (n+1)/2 ;
    min = max = m[0] ;
    for (i=1 ; i<n ; i++) {
        if (m[i]<min) min=m[i];
        if (m[i]>max) max=m[i];
    }

    while (1) {
        guess = (min+max)/2;
        less = 0; greater = 0; equal = 0;
        maxltguess = min ;
        mingtguess = max ;
        for (i=0; i<n; i++) {
            if (m[i]<guess) {
                less++;
                if (m[i]>maxltguess) maxltguess = m[i] ;
            } else if (m[i]>guess) {
                greater++;
                if (m[i]<mingtguess) mingtguess = m[i] ;
            } else equal++;
        }
        if (less <= half && greater <= half) break ;
        else if (less>greater) max = maxltguess ;
        else min = mingtguess; 
    }
    if (less >= half) return maxltguess;
    else if (less+equal >= half) return guess;
    else return mingtguess;
}

Here is the caller graph for this function:

pixelvalue wirth	(	pixelvalue	a[],
		int	n
	)

Function wrapper for kth_smallest to get Wirth's median.

Function : wirth()

• In : array of elements, # of elements in the array
• Out : one element

Definition at line 163 of file medians_1D.c.

References kth_smallest().

Referenced by bench().

                             {
    return kth_smallest(a,n,(((n)&1)?((n)/2):(((n)/2)-1)));
}

Here is the call graph for this function:

Here is the caller graph for this function:

---