This paper presents a novel method of retrieving images by learning the commonality of instances from a set of training examples. The proposed scheme uses a coarse-to-fine algorithm to find the desired visual concepts from a set of instances for successful image retrieval. The learner at the coarse stage attempts to partition training data into two smaller compact sets (relevant and irrelevant) to reduce the size of the training examples, thus improving the efficiency of concept learning at the refined stage. At the refined stage, a proposed verification scheme is employed to verify each instance obtained at the coarse stage by examining its indexing and filtering capabilities based on a pool of images. Due to this extra examination step, the desired visual concepts can be learned more accurately, leading to significant improvement in image retrieval. Since no time-consuming optimization process is involved, all the desired visual concepts can be learned online. Experimental results are provided to verify the superiority of the proposed method.