Agglomerative Hierarchical Clustering on Images

My goal is to implement the agglomerative hierarchical clustering algorithm on an RGB image to cluster every pixel until some stopping criteria is reached. In order to do so, I assumed that each pixel belongs to a cluster initially. Then, to merge pixels, it is necessary to calculate the distance between every other pixel, which makes agglomerative hierarchical cluster inefficient in terms of computational time, especially if the image is large.

I somehow need to get around this problem, but don’t exactly know what approaches would help.

One thing came to my mind is to apply SLIC to obtain superpixels and select each superpixel as a cluster at the beginning. If this sounds reasonable, what similarity metrics should I consider to merge superpixels ?