icl::utils::FastMedianList Class Reference

Utility class for fast calculation of a median (calculating a median in O(N)) More...

#include <FastMedianList.h>

List of all members.

Public Member Functions
	FastMedianList (int size=0, int t2=-1, int t3=-1, int t4=-1)
	Create a new fast median list with given max size.
	FastMedianList (const FastMedianList &l)
	Copy cosntructor.
FastMedianList &	operator= (const FastMedianList &l)
	Assign operator.
	~FastMedianList ()
	destructor
void	init (int size, int t2=-1, int t3=-1, int t4=-1)
	initialization function
int	add (int index)
	add a new datum
void	add (int index, int val)
	add a new datum (deprecated)
int	median ()
	calculates the median value
void	clear ()
	resets the internal lookup table
int	mean ()
	calculates the mean value (not accelerated)
int	variance ()
	calculates the variance of contained elements
int	getSize ()
	returns the current count of elements
Protected Attributes
int	m_iCount
	internal element count
int	m_iSize
	internal storage of max size
int	m_iT2
	deprecated variable
int	m_iT3
	deprecated variable
int	m_iT4
	deprecated variable
int *	m_piTable
	internal counter array

---

Detailed Description

Utility class for fast calculation of a median (calculating a median in O(N))

The median of a set S is defined by the element of sorted S at indes |S|/2 To avoid the expensive sorting procedure of the list with runs in O(N*log(N)), the FastMedianList can be used.
It exploits the knowledge of the maximum expected value to accelerate median calculation. Naive approach:

        given: set S of length n

        1.  sort(S)                                             O(n*log(n))
        return S[n/2]
        

FastMedianList approach:

        given: an empty set S with max element M
        Create counter array A of size M initialized with 0     O(M)
        Create overall counter C = 0

        Set creation (iteratively) n times:

        given: next elem e                                      O(n)
        A[e]++
        C++

        Accessing median:                                       O(M)
        mass=0;
        HALF_C = C/2;
        for i=0..M
          mass+=A[i];
          if mass > HALF_C
            return i
          endif
        endfor

        Overall complexity                                       O(M+n)
        

The fast median list is faster if O(M+n) < O(n*log(n)). E.g. if we try to compute the median pixel x-position of an image of width 640. We have 640+n < n*log(n) --> 640 < n*(log(n)+1) which is true if n is larger than about 120.

---

Constructor & Destructor Documentation

icl::utils::FastMedianList::FastMedianList	(	int	size = 0,
		int	t2 = -1,
		int	t3 = -1,
		int	t4 = -1
	)		[inline]

Create a new fast median list with given max size.

t2,t3 and t4 are deprecated!

icl::utils::FastMedianList::FastMedianList

(

const FastMedianList &

l

)

[inline]

Copy cosntructor.

icl::utils::FastMedianList::~FastMedianList

(

)

[inline]

destructor

---

Member Function Documentation

int icl::utils::FastMedianList::add

(

int

index

)

[inline]

add a new datum

void icl::utils::FastMedianList::add	(	int	index,
		int	val
	)		[inline]

add a new datum (deprecated)

void icl::utils::FastMedianList::clear

(

)

[inline]

resets the internal lookup table

int icl::utils::FastMedianList::getSize

(

)

[inline]

returns the current count of elements

void icl::utils::FastMedianList::init	(	int	size,
		int	t2 = -1,
		int	t3 = -1,
		int	t4 = -1
	)		[inline]

initialization function

int icl::utils::FastMedianList::mean

(

)

[inline]

calculates the mean value (not accelerated)

int icl::utils::FastMedianList::median

(

)

[inline]

calculates the median value

FastMedianList& icl::utils::FastMedianList::operator=

(

const FastMedianList &

l

)

[inline]

Assign operator.

int icl::utils::FastMedianList::variance

(

)

[inline]

calculates the variance of contained elements

---

Member Data Documentation

int icl::utils::FastMedianList::m_iCount [protected]

internal element count

int icl::utils::FastMedianList::m_iSize [protected]

internal storage of max size

int icl::utils::FastMedianList::m_iT2 [protected]

deprecated variable

int icl::utils::FastMedianList::m_iT3 [protected]

deprecated variable

int icl::utils::FastMedianList::m_iT4 [protected]

deprecated variable

int* icl::utils::FastMedianList::m_piTable [protected]

internal counter array

---

The documentation for this class was generated from the following file:

• /home/jenkins/workspace/icl-manual-trunk/icl-manual/ICLUtils/src/ICLUtils/FastMedianList.h