In vector guantization, it is desirable to design a codebook on an image-to-image basis, because the codewords should be the representative vectors which describe the image most properly. However, the conventional codebook design algorithms are iterative methods in which we can not predict the execution time, and the overhead for the transmission of a designed codebook increases as the codebook size gets lager. In this paper, we propose an algorithm which updates a vector centroid sequentially and removes the overhead for the replenishment of a codebook by introducing the interframe coding technique for image sequence coding. With the proposed replenishment technique, we can obtain almost the same performance as that of the LBG algorithm for each frame. The experimental results demonstrate that a bit rate as low as 0.375-0.5 bit/pixel is sufficient for a good image quality because a new label is transmitted only in the changing areas.