icl::utils::FastMedianList Class Reference

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

#include <FastMedianList.h>

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. More...
	FastMedianList (const FastMedianList &l)
	Copy cosntructor. More...
FastMedianList &	operator= (const FastMedianList &l)
	Assign operator. More...
	~FastMedianList ()
	destructor More...
void	init (int size, int t2=-1, int t3=-1, int t4=-1)
	initialization function More...
int	add (int index)
	add a new datum More...
void	add (int index, int val)
	add a new datum (deprecated) More...
int	median ()
	calculates the median value More...
void	clear ()
	resets the internal lookup table More...
int	mean ()
	calculates the mean value (not accelerated) More...
int	variance ()
	calculates the variance of contained elements More...
int	getSize ()
	returns the current count of elements More...

Protected Attributes
int	m_iCount
	internal element count More...
int	m_iSize
	internal storage of max size More...
int	m_iT2
	deprecated variable More...
int	m_iT3
	deprecated variable More...
int	m_iT4
	deprecated variable More...
int *	m_piTable
	internal counter array More...

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

FastMedianList() [1/2]

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!

FastMedianList() [2/2]

icl::utils::FastMedianList::FastMedianList ( const FastMedianList &  l )

inline

Copy cosntructor.

~FastMedianList()

icl::utils::FastMedianList::~FastMedianList ( )

inline

destructor

Member Function Documentation

add() [1/2]

int icl::utils::FastMedianList::add ( int  index )

inline

add a new datum

add() [2/2]

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

inline

add a new datum (deprecated)

clear()

void icl::utils::FastMedianList::clear ( )

inline

resets the internal lookup table

getSize()

int icl::utils::FastMedianList::getSize ( )

inline

returns the current count of elements

init()

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

inline

initialization function

mean()

int icl::utils::FastMedianList::mean ( )

inline

calculates the mean value (not accelerated)

median()

int icl::utils::FastMedianList::median ( )

inline

calculates the median value

operator=()

FastMedianList& icl::utils::FastMedianList::operator= ( const FastMedianList &  l )

inline

Assign operator.

variance()

int icl::utils::FastMedianList::variance ( )

inline

calculates the variance of contained elements

Member Data Documentation

m_iCount

int icl::utils::FastMedianList::m_iCount

protected

internal element count

m_iSize

int icl::utils::FastMedianList::m_iSize

protected

internal storage of max size

m_iT2

int icl::utils::FastMedianList::m_iT2

protected

deprecated variable

m_iT3

int icl::utils::FastMedianList::m_iT3

protected

deprecated variable

m_iT4

int icl::utils::FastMedianList::m_iT4

protected

deprecated variable

m_piTable

int* icl::utils::FastMedianList::m_piTable

protected

internal counter array

---

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

• /Users/alneuman/vm/icl/ICLUtils/src/ICLUtils/FastMedianList.h