Open Access Open Badges Research

Determining similarity in histological images using graph-theoretic description and matching methods for content-based image retrieval in medical diagnostics

Harshita Sharma12*, Alexander Alekseychuk2, Peter Leskovsky2, Olaf Hellwich2, RS Anand1, Norman Zerbe3 and Peter Hufnagl3

Author Affiliations

1 , Electrical Engineering Department, IIT Roorkee, India

2 Computer Vision and Remote Sensing Group, Technical University, Berlin, Germany

3 Dept. Digital Pathology and IT, Institute of Pathology, Charité - Universitätsmedizin Berlin, Berlin, Germany

For all author emails, please log on.

Diagnostic Pathology 2012, 7:134  doi:10.1186/1746-1596-7-134

Published: 4 October 2012



Computer-based analysis of digitalized histological images has been gaining increasing attention, due to their extensive use in research and routine practice. The article aims to contribute towards the description and retrieval of histological images by employing a structural method using graphs. Due to their expressive ability, graphs are considered as a powerful and versatile representation formalism and have obtained a growing consideration especially by the image processing and computer vision community.


The article describes a novel method for determining similarity between histological images through graph-theoretic description and matching, for the purpose of content-based retrieval. A higher order (region-based) graph-based representation of breast biopsy images has been attained and a tree-search based inexact graph matching technique has been employed that facilitates the automatic retrieval of images structurally similar to a given image from large databases.


The results obtained and evaluation performed demonstrate the effectiveness and superiority of graph-based image retrieval over a common histogram-based technique. The employed graph matching complexity has been reduced compared to the state-of-the-art optimal inexact matching methods by applying a pre-requisite criterion for matching of nodes and a sophisticated design of the estimation function, especially the prognosis function.


The proposed method is suitable for the retrieval of similar histological images, as suggested by the experimental and evaluation results obtained in the study. It is intended for the use in Content Based Image Retrieval (CBIR)-requiring applications in the areas of medical diagnostics and research, and can also be generalized for retrieval of different types of complex images.

Virtual Slides

The virtual slide(s) for this article can be found here: webcite.

Attributed Relational Graphs (ARG); Region of Interest (ROI); Breast tissue biopsy; Connected components; Graph-theoretic; A* search