Primeiramente eu aconselharia a reduzir as dimensões dessas imagens.
Pois se for aplicar um K-means pode acontecer o problema de Course Of dimensionality que faz com algoritmos que usam distâncias entre um ponto e outro percam precisão.
Porem não digo literalmente reduzir o tamanho da imagem mas sim utilizar um PCA ou SVD para isso pois irá conservar informações relevantes da imagem.
Existem outras formas de clusters como hierarchical clustering e Autoencouders que podem ser uteis também.
Outro ponto importante é a memória necessária para lidar com essa quantidade de imagens. dependendo do algoritmo e da quantidade de memoria de seu computador você pode trava-lo.
Existem métodos mais diretos como comparação de pedações da imagem A com a imagem B.(mas não acredito que seja muito bom.)
Emfim existem várias formas de se fazer esse tipo de clusterização.