Clustering is used to organize data for efficient retrieval. A popular technique for clustering is based on k-Means such that the data is partitioned into k clusters. In k-Means clustering a set of n data points in d-dimensional space Rd, an integer k is given and the problem is to determine a set of k-points in Rd called centers, to minimize the mean squared distance from each point to its nearest center. In this method, the number of clusters is predefined and the technique is highly dependent on the initial identification of elements that represent the clusters well. A large area of research in clustering has focused on improving the clustering process such that the clusters are not dependent on the initial identification of cluster representation. In this paper, a modified technique, which grows the clusters without the need to specify the initial cluster representation, has been proposed. Initially a local search single swap heuristic can identify the number of clusters and its centers in the interpolated (bicubic) multispectral image. Then the regular k-Means clustering is implemented using the results of the previous process for the true image data set. The technique achieves an impressive speed up of the clustering process even when the number of clusters is not specified initially and the classification accuracy is improved within a fewer number of iterations.