I have a series of points (x,y) and each point has a colour (in the LAB colour space). I need to associate points by similar colour and then spatially. So the end result is each point becomes part of a local cluster or segment.

Is there a specific data structure that is suited to such a scenario? I'm trying to find a data structure that can efficiently find the n surrounding points of a specific point.

Essentially I need to select point P and find the surrounding points. For each surrounding point (Q); measure the Euclidean colour distance between P and Q, if the distance is within a threshold, these points get the same label. Then repeat for point Q until Q is surrounded by points of its own label or points that are too dissimilar to accumulate.

I'm aware of machine learning algorithms that could achieve what I want; SVM (Support Vector Machines) however it is not quite fast enough. If there is a data structure that can perform this faster its more desirable.


You seem to be describing a linkage-based hierarchical clustering algorithm. However, you have an unusual metric: Two points don't have a scalar distance, but a separate coordinate-distance and color-distance. This may or may nor be a problem.

The act of finding all elements within a given distance is a range search or range query. This requires a concept of distance/metric. You may therefore have to perform range searches based on the coordinate-metric first and filter the result set to account for your color-metric. While this approach is not generally possible, it works fine here because the color-distance component strictly increases total distance.

Even absent any metric, k-d trees can be used to organize multi-dimensional data. A k-d tree is a binary tree that partitions on a different dimension for each level. This allows somewhat efficient range queries because we can skip sub-trees if all their elements must be out of range, given the metric. The search space is effectively delimited by a hypercube rather than a hypersphere defined by the query's range. There are more efficient spatial data structures such as ball trees, but k-d trees are easy to implement.

While tree based data structures have attractive algorithmic complexities, these don't necessarily matter. For smaller data sets, a flat array of coordinates that you scan linearly might have better performance due to cache effects. If the coordinates are on a densely populated grid (e.g. because you are processing a bitmap) then you can get rid of explicit coordinates as you can easily calculate the offsets of all neighbors.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.