Image Component Library (ICL)
|
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. | |
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 |
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.
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
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
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