How to run K-means clustering on data points of varying dimensionality?

Question

I'm trying to aggregate $T$ local image descriptors (i.e. histograms) into a vector, namely, the Fisher Vector as described in this paper by H. Jégou et al., Aggregating local image descriptors into compact codes, to perform image classification. As a first step, the algorithm calls for running K-means to assign each local descriptor $x_t$ to the nearest centroid $\mu_i$ in a bag-of-visual words (BOW) of $K$ words. This is straightforward when every $x_t$ and $\mu_i$ are $d$-dimensional. However, how does one perform K-means when the descriptors have varying dimensionality i.e. $\dim(x_t) \ne \dim(x_s)$ for some $t \ne s$ where $t, s \in 1..T$?

Answer 1

Have a look at this work on the Tracklet Descriptor. In this case, they need to compute distances between time series of different lengths, and they use a nice dynamic time warping approach to inflate/deflate the two time series in question to find a minimum distance between them based on an idea of optimally distorting them. Outside of a reasonable set of distortions, they define the distance to be infinite.

You could probably adapt this approach to define a distance between descriptors of different lengths. You need to be very careful and do some numerical testing though, because if you have undersampled a feature in a given part of the image because the set of features is sparser there, it can lead to very inaccurate numerical comparisons.

Another alternative is to use something like the Isomap algorithm which is a non-linear, manifold-based analogue of PCA. The idea here is project a set of points down onto a lower dimensional subset that captures the relevant topology best. It's normally used for dimensionality reduction, hence data sets are normally consisting of samples all of the same length, but it would be interesting to consider a modification that uses something like the dynamic time warping distance mentioned above to map mixed-size descriptors onto an optimal fixed lower dimensional space.

Lastly, it's not clear what your edge-based directionality features are. Are you using a form of Histogram of Oriented Gradient? If so, you really should be ensuring that the histograms are always of the same length. If not, you might consider using Histogram of Oriented Gradient instead of your current descriptor, because mixed-dimensionality descriptors often wind up having unforeseen modeling consequences and tend not to work well in practice, in addition to requiring more difficult distance calculations. If interested, I have a project page linked here that includes a lot of Python code for using Histogram of Oriented Gradient (including GPU code in PyCuda). The useful library scikits.image also has a built-in HoG function.