Processing weighted points of interest. Is there a name for this task/algorithm?

Question

Is there a name for the following problem? Is there a measure of quality of a given solution? How can we even define what a proper solution is?

Context: I want to detect long lines (most lines over 1000 pixel long) in an image. It is known that most of the lines have similar alignment. To detect those I use the Standard Hough Transform. To detect long lines I need a high angle resolution of the accumulator. Now the idea is not to use an equidistant partition of the angle axis but to create a new partition based on the number of votes for each angle.

The Problem: Given weights $$a_0, \ldots, a_{n-1} \in [0,1] \text{ with } \sum_{k=0}^{n-1}a_k = 1$$ which correspond to the equidistant partition of the interval $[0,1[$ $$0, \frac{1}{n}, \frac{2}{n}, ..., \frac{n-1}{n},$$ return a new partition with less or equal elements which is "finer" around points with larger weights and "coarser" around points with smaller weights. E.g. given the weights $(0.75, 0, 0, 0.25)$ on the partition $(0, 0.25, 0.5, 0.75)$ the result should be a new partition like $(-0.083, 0.0, 0.083, 0.75)$. As $0$ seems to be a point of interest there are three points near it which reflects that.

My solution: The idea is to treat the vector of weights as a density function and to use the quantile function of its cumulative distribution function (cdf).

Example: Given the weights $(0, 0.5, 0, 0.5, 0)$ we construct the density function:

Then the cdf looks like this:

Now we shift the given equidistant partition by $+1/(2n) = 1/10$ and put its values into the quantile function, i.e. we put those values on the $y$-axis and search for corresponding $x$-values of the cdf as marked by the blue lines. $y=0.5$ is omitted since it "cannot decide" which peak it contributes to. The so obtained $x$-values are shifted by $-1/(2n) = -1/10$ and returned as the new partition. The returned partition in this example is $(0.14, 0.22, 0.58, 0.66)$.

Here is a C++ function which performes those tasks, where the vector "weights" represents the input weights and "sample" contains the new partition after execution:

#include <vector>
using std::vector;

void weighted_partition(vector<double>& sample, const vector<double>& weights) {
    const int n = (int)weights.size();
    double y;
    double F = 0.0;
    int i = 0;

    for (int j = 1; j < 2*n; j += 2) {
        y = (double)j/(2*n);

        while (F < y) {
            F += weights[i];
            ++i;
        }

        if (F == y) {
            continue;
        }

        --i;
        F -= weights[i];

        sample.push_back((y - F + weights[i] * i) / (weights[i] * n) - 1.0/(2.0 * n));
    }
}

This algorithm seems to return solutions which are intuitively correct but how can you define "correct"?

Answer 1

Solution to your algorithm problem

There's a simple solution to your algorithmic problem. Treat the $a_0,a_1,\dots,a_{k-1}$ as a probability distribution. Apply kernel smoothing to turn this into a smooth probability distribution. At this point, you have a probability density function (pdf). Now compute a cumulative density function (cdf), and find the $n+1$ quartiles of the cdf. These endpoints of your new bins.

This is "optimal", in the sense that given all of the information available to you, it gives the optimal bin-sizing for a particular distribution. We could prove this by proving that for a particular pdf, this definition of bins ensures that each bin has exactly $1/n$ probability mass falling within it.

Other approaches to your computer vision task

The Hough transform might not be optimal. There are other approaches you could also try. For instance, there are algorithms for detecting lines that are approximately horizontal. So, the following approach might be better:

• Find one long line and approximately find its angle.

• Rotate the image so that it is approximately horizontal (since the lines are all approximately parallel, that means all the lines will now be approximately horizontal).

• Find all long, approximately-horizontal lines.

The problem of finding long, approximately-horizontal lines has been studied in the literature on image processing and deskewing scanned documents. Or, if you want a free tool, take a look at existing tools, e.g., Leptonica, pagetools, ImageMagick (convert -deskew), and others.

Another standard approach is to apply the Hough transform twice:

• First use the Hough transform to get a rough estimate of the angle. For instance, you might sweep over some range of possible angles, sensitive to 1 degree or 0.1 degree increments.

• Then, use a second Hough transform to get a rough estimate of the angle. Now you have a much narrower range of possible angles (1 degree or 0.1 degree wide); do the Hough transform over this narrower range, sensitive to 0.01 degree increments (say).

This is more efficient then doing a single Hough transform sensitive to 0.01 degree increments.