To reduce the coding time of the conventional method, a fast sequential image fractal compression algorithm was proposed on the basis of the principle of optimal fuzzy clustering (OFC) for an unsupervised sample set with the category number settled by the algorithm itself. We utilized the cost function defined by the OFC algorithm to obtain the best category number corresponding to the minimum value of the function. Firstly the Linde-Buzo-Gray (LBG) algorithm was realized to acquire a rough cluster of the domain pool. Then the optimal category number was obtained by implementing our algorithm with small computational cost. Finally the more precise category was gained and the detail of the reconstructed image efficiently preserved. As a global optimal algorithm, OFC not only helps LBG eliminate the local minima, but also effectively compensates for the arbitrary interference in hard clustering problem. Soft clustering of the domain blocks allows classified searches instead of global ones and takes less coding time, and therefore clearly outperforms to the classic method relying on reduction of the size of the domain pool by classification. In computer simulation, OFC-based algorithm for the fractal coding scheme achieved excellent performance. For some standard and sequential medical images, the results denoted that the encoding speed was improved by about 5 folds without affecting the signal-to-noise ratio and compression ratio, and the quality of the reconstructed image could be better retained.