QUIP: Querying Significant Patterns from Image Databases

Vishwakarma Singh Arnab Bhattacharya Ambuj K. Singh
Dept. of Computer Science, UCSB
{vsingh,arnab,ambuj} [at] cs.ucsb.edu

Chris Banna Geoffrey P. Lewis Steven K. Fisher
Dept. of Molecular, Cellular and Developmental Biology, UCSB
{banna,g_lewis,fisher} [at] lifesci.ucsb.edu


Images have become an extremely important dataset in many areas of science including biology, geography and astronomy due to their ability to reveal spatial information not immediately available from other data sources. In this paper, we introduce a novel approach, QUIP (QUerying Image Patterns), to retrieve significant spatial patterns from a large collection of such images. Such an ability will provide important clues to the domain scientists regarding the underlying processes that produce those images. The query pattern of interest is specified as a rectangular region from a tiled image. A scoring formula is designed to discriminate the significant foreground patterns from the irrelevant background of the region. Candidate database regions that match the query are translated into a score matrix of the pairwise aligned tiles. We show that the problem of finding the maximal scoring connected sub-region from the matrix is NPhard and develop an effective dynamic programming heuristic. To assist the user, each retrieved database pattern is assigned a p-value to indicate its statistical significance. Finally, in order to accelerate QUIP, we adopt the threshold algorithm to efficiently retrieve the candidate database matches and a bounding method to speed up p-value computation. We experiment with three datasets of microscopy images of retina. For each dataset, the results are significant for the domain scientists. Our method also has practical running time and scales well with database and query sizes.
[PDF] [BibTex]
V. Singh, A. Bhattacharya, A. K. Singh, C. Banna, G. P. Lewis and S. K. Fisher,
Center for Bio-Image Informatics, UCSB, 2007.
Node ID: 462 , DB ID: 266 , Lab: BIO , Target: Technical Report
Subject: [Managing Multimedia Databases] « Look up more