In order to perform an image processing task using compressed (encoded) data, image analysis system 100 may use storage interface 113 to obtain, for each superpixel, clustering information identifying the cluster to which the superpixel belongs, and then use that that cluster's centroid vector instead of the superpixel's feature vector. Because the clustering algorithm ensures that all superpixels in a given cluster are relatively similar, the centroid vector of the cluster can be a sufficiently good approximation of the feature vector of each superpixel in the cluster, and the greater the number of clusters used, the better the approximation can be.

As discussed above, some image processing tasks rely solely on the distance between two superpixels, i.e., the distance between the superpixels' feature vectors. Such tasks can approximate the distance between superpixels by using the distance between centroid vectors of the two clusters to which the superpixels have been assigned. The distance can be calculated in real time based on the centroid vectors, if the centroid vectors have been stored. Alternatively, the distance can be obtained directly (without additional calculations) from a table or another data structure, if the distances have been precalculated and stored, as discussed above.