Saturday, September 10, 2016

Hierarchical clustering

One of the key algorithms in crunch is determining how to group together block endpoints into clusters. Crunch uses a bottom up clustering approach at the 8x8 pixel (or 2x2 DXTn block) "macroblock" level, then it switches to top down. The top down method is extremely sensitive to the vectors chosen to represent each block during the clusterization step. The algorithm crunch uses to compute representative vectors (used only during clusterization) was refined and tweaked over time. Badly chosen representative vectors cause the clustering step to product crappy clusters (i.e. nasty artifacts).

Anyhow, an alternative approach would be entirely bottom up. I think this method could require less tweaking. Some reading:

https://en.wikipedia.org/wiki/Hierarchical_clustering

https://onlinecourses.science.psu.edu/stat505/node/143

Also Google "agglomerative hierarchical clustering". Here's a Youtube video describing it.

No comments:

Post a Comment