001package org.openimaj.demos.sandbox.tldcpp.tracker; 002 003/** 004 * Fast array median computation 005 * 006 * @author Sina Samangooei (ss@ecs.soton.ac.uk) 007 * 008 */ 009public class FastMedian { 010 private static void ELEM_SWAP(float[] a, int ai, float[] b, int bi) 011 { 012 final float t = a[ai]; 013 a[ai] = b[bi]; 014 b[bi] = t; 015 } 016 017 /** 018 * Returns median of the array. Changes array! 019 * <p> 020 * This Quickselect routine is based on the algorithm described in 021 * "Numerical recipes in C", Second Edition, Cambridge University Press, 022 * 1992, Section 8.5, ISBN 0-521-43108-5 023 * <p> 024 * This code by Nicolas Devillard - 1998. Public domain. 025 * 026 * @param arr 027 * the array 028 * @param n 029 * length of array 030 * @return the median of the array 031 */ 032 public static float getMedianUnmanaged(float arr[], int n) 033 { 034 int low, high; 035 int median; 036 int middle, ll, hh; 037 038 low = 0; 039 high = n - 1; 040 median = (low + high) / 2; 041 for (;;) 042 { 043 if (high <= low) /* One element only */ 044 return arr[median]; 045 046 if (high == low + 1) 047 { /* Two elements only */ 048 if (arr[low] > arr[high]) 049 ELEM_SWAP(arr, low, arr, high); 050 return arr[median]; 051 } 052 053 /* Find median of low, middle and high items; swap into position low */ 054 middle = (low + high) / 2; 055 if (arr[middle] > arr[high]) 056 ELEM_SWAP(arr, middle, arr, high); 057 if (arr[low] > arr[high]) 058 ELEM_SWAP(arr, low, arr, high); 059 if (arr[middle] > arr[low]) 060 ELEM_SWAP(arr, middle, arr, low); 061 062 /* Swap low item (now in position middle) into position (low+1) */ 063 ELEM_SWAP(arr, middle, arr, low + 1); 064 065 /* Nibble from each end towards middle, swapping items when stuck */ 066 ll = low + 1; 067 hh = high; 068 for (;;) 069 { 070 do 071 ll++; 072 while (arr[low] > arr[ll]); 073 do 074 hh--; 075 while (arr[hh] > arr[low]); 076 077 if (hh < ll) 078 break; 079 080 ELEM_SWAP(arr, ll, arr, hh); 081 } 082 083 /* Swap middle item (in position low) back into correct position */ 084 ELEM_SWAP(arr, low, arr, hh); 085 086 /* Re-set active partition */ 087 if (hh <= median) 088 low = ll; 089 if (hh >= median) 090 high = hh - 1; 091 } 092 } 093 094 /** 095 * Calculates the median of the array. Doesn't change the array (operates on 096 * a copy internally). 097 * 098 * @param arr 099 * the array 100 * @param n 101 * length of array 102 * @return the median 103 */ 104 public static float getMedian(float arr[], int n) 105 { 106 final float[] temP = new float[n]; 107 System.arraycopy(arr, 0, temP, 0, n); 108 ; 109 float median; 110 median = getMedianUnmanaged(temP, n); 111 return median; 112 } 113}