New algorithms are proposed for designing optimal binary vector quantizers. These algorithms aim to avoid the problem of the generalized Lloyd method of easily getting trapped into a poor local minimum. To improve the subjective quality of vector-quantized binary images, a constrained optimal binary VQ framework is proposed. Within this framework, the optimal VQ design can be done via an interesting use of linear codes.