This paper proposes a formal framework for image and video retrieval using discrete Markov random fields(MRF). The training dataset consists of images with keywords (regions are not labeled). The model may be built using quantized region or point features generated from the training images. Unlike many previous techniques, our MRF based model doesn't require an explicit annotation step for retrieval. The model directly ranks all test images according to the posterior probability of an image given a query. Image and video retrieval experiments are performed on two standard datasets (one Corel datasets and a TRECVID3 dataset) which consist of 4,500 images and about 44,100 keyframes respectively. The results show that based on a large visual vocabulary the model runs extremely fast on even very large datasets while having comparable retrieval performance to continuous models.