Improving Performance and Accuracy of Local PCA

Vaclav Gassenbauer (1, 2) , Jaroslav Křivánek (3) , Kadi Bouatouch (1) , Bouville Christian (1) , Mickaël Ribardière (1, 4)

1 FRVSense - FRVSense
2 FEL CTU - Faculty of Electrical Engineering [Prague]
3 ITI - Institut teoretické informatiky
4 CSTB - Centre Scientifique et Technique du Bâtiment

Local Principal Component Analysis (LPCA) is one of the popular techniques for dimensionality reduction and data compression of large data sets encountered in computer graphics. The LPCA algorithm is a variant of k-means clustering where the repetitive classification of high dimensional data points to their nearest cluster leads to long execution times. The focus of this paper is on improving the efficiency and accuracy of LPCA. We propose a novel SortCluster LPCA algorithm that significantly reduces the cost of the point-cluster classification stage, achieving a speed-up of up to 20. To improve the approximation accuracy, we investigate different initialization schemes for LPCA and find that the k-means++ algorithm [AV07] yields best results, however at a high computation cost. We show that similar ideas that lead to the efficiency of our SortCluster LPCA algorithm can be used to accelerate k-means++. The resulting initialization algorithm is faster than purely random seeding while producing substantially more accurate data approximation.

Analyse en composantes principales locale (LPCA) est l'une des techniques les plus répandues pour la compression des très grands volumes de données que l'on rencontre en infographie. L'algorithme LPCA est une variante du regroupement en k-means où la classification répétitive de points de haute dimensionnalité vers le groupe le plus proche conduit à de très longs temps d'exécution. Le but de cet article est de d'améliorer l'efficacité et la précision du LPCA. Nous proposons un nouvel algorithme SortCluster LPCA qui réduit significativement le coût de la classification point-cluster conduisant à une accélération dans un rapport t 20. Pour améliorer la précision de l'approximation, nous comparons différentes méthodes d'initialisation et trouvons que l'algorithme k-means++ donne les meilleurs résultats mais à un coût de calcul important. Nous montrons que des idées similaires qui améliorent l'efficacité de notre algorithme SortCluster LPCA peuvent être utilisés pour accélérer k-means++. L'algorithme d'initialisation qui en résulte est plus rapide que le simple choix aléatoire tout en produisant des approximations sensiblement meilleures.

Domaines: Synthèse d'image et réalité virtuelle [cs.GR]

Vaclav Gassenbauer, Jaroslav Křivánek, Kadi Bouatouch, Bouville Christian, Mickaël Ribardière. Improving Performance and Accuracy of Local PCA. Computer Graphics Forum, 2011, 30 (7), ⟨10.1111/j.1467-8659.2011.02047.x⟩. ⟨hal-00658792⟩