This paper presents a simple approach to improve the image retrieval accuracy in the Void-and-Cluster Block Truncation Coding compressed domain. The proposed approach directly derives an image descriptor from the Ordered Dither Block Truncation Coding (ODBTC) data stream without performing the decoding process. The Color Histogram Feature (CHF) is generated from the two ODBTC color quantizer, while the Halftoning Local Derivative Pattern (HLDP) is constructed from the ODBTC bitmap image. The similarity between two images are measured from their CHF and HLDP features. Three schemes are involved to improve the image retrieval accuracy, including the similarity weight optimization, feature reweighting, and user relevance feedback optimization. An evolutionary stochastic algorithm is exploited to optimize the similarity weight and feature weight in the nearest neighbor distance computation, as well as in the query update of relevance feedback optimization. Section 5 shows that the proposed scheme yields a promising result, and thus it can be a very effective candidate in addressing the content-based image retrieval and image classification task. Copyright 2015 Elsevier B.V. All rights reserved.