Revision history [back]

I found a simple way to answer :

double getMedian(Mat hist) {
    // binapprox algorithm

    long n = hist.total();
    int[] histBuff = new int[(int) n];
    hist.get(0, 0, histBuff);
    // Compute the mean and standard deviation
    // int n = x.length;
    double sum = 0;
    // int i;
    for (int i = 0; i < n; i++) {
        sum += histBuff[i];
    }
    double mu = sum / n;

    sum = 0;
    for (int i = 0; i < n; i++) {
        sum += (histBuff[i] - mu) * (histBuff[i] - mu);
    }
    double sigma = Math.sqrt(sum / n);

    // Bin x across the interval [mu-sigma, mu+sigma]
    int bottomcount = 0;
    int[] bincounts = new int[1001];
    for (int i = 0; i < 1001; i++) {
        bincounts[i] = 0;
    }
    double scalefactor = 1000 / (2 * sigma);
    double leftend = mu - sigma;
    double rightend = mu + sigma;
    int bin;

    for (int i = 0; i < n; i++) {
        if (histBuff[i] < leftend) {
        bottomcount++;
        } else if (histBuff[i] < rightend) {
        bin = (int) ((histBuff[i] - leftend) * scalefactor);
        bincounts[bin]++;
        }
    }

    double median = 0;
    // If n is odd
    if ((n % 2) != 0) {
        // Find the bin that contains the median
        int k = (int) ((n + 1) / 2);
        int count = bottomcount;

        for (int i = 0; i < 1001; i++) {
        count += bincounts[i];

        if (count >= k) {
            median = (i + 0.5) / scalefactor + leftend;
        }
        }
    }

    // If n is even
    else {
        // Find the bins that contains the medians
        int k = (int) (n / 2);
        int count = bottomcount;

        for (int i = 0; i < 1001; i++) {
        count += bincounts[i];

        if (count >= k) {
            int j = i;
            while (count == k) {
            j++;
            count += bincounts[j];
            }
            median = (i + j + 1) / (2 * scalefactor) + leftend;
        }
        }
    }
    return median;
    }