Image Component Library (ICL)
Public Member Functions | Protected Attributes | List of all members
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...
 
FastMedianListoperator= (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: