text: The typical content-based image retrieval problem is to find images within a database that are similar to a given query image. This paper presents a solution to a different problem, namely that of content based sub-image retrieval, i.e., finding images from a database that contains another image. Note that this is different from finding a region in a (segmented) image that is similar to another image region given as a query. We present a technique for CBsIR that explores relevance feedback, i.e., the user's input on intermediary results, in order to improve retrieval efficiency. Upon modeling images as a set of overlapping and recursive tiles, we use a tile re-weighting scheme that assigns penalties to each tile of the database images and updates the tile penalties for all relevant images retrieved at each iteration using both the relevant and irrelevant images identified by the user. Each tile is modeled by means of its color content using a compact but very efficient method which can, indirectly, capture some notion of texture as well, despite the fact that only color information is maintained. Performance evaluation on a largely heterogeneous dataset of over 10,000 images shows that the system can achieve a stable average recall value of 70 within the top 20 retrieved (and presented) images after only 5 iterations, with each such iteration taking about 2 seconds on an off-the-shelf desktop computer.
  @cite_3: Many database management systems support whole-image matching. However, users may only remember certain subregions of the images. In this paper, we develop Padding and Reduction Algorithms to support subimage queries of arbitrary size based on local color information. The idea is to estimate the best- case lower bound to the dissimilarity measure between the query and the image. By making use of multiresolution representation, this lower bound becomes tighter as the scale becomes finer. Because image contents are usually pre- extracted and stored, a key issue is how to determine the number of levels used in the representation. We address this issue analytically by estimating the CPU and I O costs, and experimentally by comparing the performance and accuracy of the outcomes of various filtering schemes. Our findings suggest that a 3-level hierarchy is preferred. We also study three strategies for searching multiple resolutions. Our studies indicate that the hybrid strategy with horizontal filtering on the coarse level and vertical filtering on remaining levels is the best choice when using Padding and Reduction Algorithms in the preferred 3-level multiresolution representation. The best 10 desired images can be retrieved efficiently and effectively from a collection of a thousand images in about 3.5 seconds.© (1997) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
summary: The paper by Leung and Ng @cite_3 investigates the idea of either enlarging the query sub-image to match the size of an image block obtained by the four-level multiscale representation of the database images, or conversely contracting the image blocks of the database images so that they become as small as the query sub-image. The paper presents an analytical cost model and focuses on avoiding I O overhead during query processing time. To find a good strategy to search multiple resolutions, four techniques are investigated: the branch-and-bound algorithm, Pure Vertical (PV), Pure Horizontal (PH) and Horizontal-and-Vertical (HV). The HV strategy is argued to be the best considering efficiency. However, the authors do not report clear conclusions regarding the effectiveness (e.g., Precision and or Recall) of their approach.