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

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$?

-
Would it make sense to increase the dimensionality of all descriptors to $d=\max(\{\dim(x1),\dim(x2),...,\dim(xT)\})$ by padding with zeroes or resampling? –  marcos Apr 9 '12 at 6:39
Further context, the reason why my descriptors are of varying dimensionality is that they are edge-based directional features of different kinds, as opposed to the standard d-dimensional SIFT local descriptors ubiquitously used in image classification. –  marcos Apr 9 '12 at 18:33
In order to cluster, you must first define what is "similar". According to your edge-based directional features, can you tell us how two vectors from two different sets of features should be considered similar? If not, this is probably not a valid question. –  Memming Apr 9 '12 at 19:00
Memming, thanks for your comment. I'd hope someone would help me define a meaningful similarity measure between different-length image descriptors (to later build a Fisher Vector) as part of the answer –  marcos Apr 10 '12 at 4:44

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.

-
If the OP did as you suggest, replacing the Euclidean distance by a time warping measure, then k-means would no longer be admissible since the centroid would not necessarily be the optimal cluster center. –  Suresh Venkatasubramanian Apr 10 '12 at 3:16
Thank you EMS! It seems that I should go tweak my feature extraction so as to produce same-length descriptors. There are other people involved in feature extraction, so I was trying to aggregate everyone's work using a Fisher Vector without having to modify extraction scripts. –  marcos Apr 10 '12 at 4:40
Suresh, I thought K-means was similarity measure-agnostic. If we replace L2 distance by "time warping distance", what does K-means care? The centroid would be optimal w.r.t. the measure used. –  marcos Apr 10 '12 at 4:49
marcos is correct, the centroid would simply be in a different space that includes all admissible time/space warpings. This may or may not be appropriate depending on the application, but well-defined cluster centers would still exist and classification in that warped space could still be done with k-means. However, in some numerical results it is reported that higher order kernel SVMs work better to account for the weird shape that such a manifold of warped features can have. –  EMS Apr 10 '12 at 5:49