A review of graph-based methods for image analysis in digital histopathology

  • Harshita Sharma Computer Vision & Remote Sensing Technical University Berlin
  • Norman Zerbe Dept. Digital Pathology and IT Institute of Pathology Charité - Universitätsmedizin Berlin
  • Sebastian Lohmann Dept. Digital Pathology and IT Institute of Pathology Charité - Universitätsmedizin Berlin
  • Klaus Kayser Dept. Digital Pathology and IT Institute of Pathology Charité - Universitätsmedizin Berlin
  • Olaf Hellwich Computer Vision & Remote Sensing Technical University Berlin
  • Peter Hufnagl Dept. Digital Pathology and IT Institute of Pathology Charité - Universitätsmedizin Berlin


Digital image analysis of histological datasets is a currently expanding field of research. With different stains, magnifications and types of tissues, histological images are inherently complex in nature and contain a wide variety of visual information. Several image analysis techniques are being explored in this direction. However, graph-based methods are gaining most popularity, as these methods can describe tissue architecture and provide adequate numeric information for subsequent computer-based analysis. Graphs have the ability to represent spatial arrangements and neighborhood relationships of different tissue components, which are essential characteristics observed visually by pathologists during investigation of specimens. In this paper, we present a comprehensive review of the graph-based methods explored so far in digital histopathology. We also discuss the current limitations and suggest future directions in graph-based tissue image analysis.


Download data is not yet available.

Author Biography

Harshita Sharma, Computer Vision & Remote Sensing Technical University Berlin
PhD student at Computer Vision & Remote Sensing, Technical University Berlin


[1] Weidner N, Cote RJ, Suster S, and Weiss LM. Modern Surgical Pathology: 2-Volume Set, Expert Consult-Online & Print. Elsevier Health Sciences, 2009.

[2] Rolls G. An introduction to specimen preparation. http://www.leicabiosystems.com/
pathologyleaders/an-introduction-to-specimen-preparation/, May 2011.

[3] Pawlina W and Ross M. Histology: A Text and Atlas. Lippincott Williams & Wilkins, Baltimore, MD, 2006.

[4] Rochow TG and Tucker PA. Introduction to microscopy by means of light, electrons, X-rays, or acoustics. Springer Science & Business Media, 1994.

[5] Sucaet Y and Waelput W. Digital Pathology. SpringerBriefs in Computer Science. Springer, 2014.

[6] Trudeau RJ. Introduction to Graph Theory. Dover Publications, New York, 1993.

[7] Lejeune Dirichlet G. Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. Journalfu¨r die reine und angewandteMathematik, 40:209–227, 1850.

[8] Voronoi G. Nouvelles applications des paramètres continus á la thèorie des formes quadratiques. Journal für die reine und angewandte Mathematik (Crelle’s Journal), 133:198-287, 1907.

[9] Toussaint GT. Some unsolved problems on proximity graphs. In Dearholt D and Harary F, editors, Proceedings of the First Workshop on Proximity Graphs. Memoranda in Computer and Cognitive Science MCCS, pages 91–224. Citeseer, 1991.

[10] Aurenhammer F and Klein R. Voronoi diagrams. Handbook of computational geometry, 5:201– 290, 2000.

[11] Rozenberg G and Salomaa A. Current trends in theoretical computer science: essays and tutorials, volume 40. World Scientific, 1993.

[12] Delaunay B. Sur la sph`ere vide. A la m´emoire de Georges Vorono¨ı. Bulletin of Academy of Sciences oftheUSSR, (6):793–800, 1934.

[13] Gabriel KR and Sokal RR. A new statistical approach to geographic variation analysis. Systematic Biology, 18(3):259–278, 1969.

[14] Matula DW and Sokal RR. Properties of Gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geographical analysis, 12(3):205–222, 1980.

[15] Toussaint GT. The relative neighbourhood graph of a finite planar set. Pattern recognition, 12(4):261–268, 1980.

[16] Graham RL and Hell P. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1):43–57, 1985.

[17] Czumaj A and Sohler C. Testing euclidean minimum spanning trees in the plane. ACM Transactions on Algorithms(TALG), 4(3):31, 2008.

[18] Preparata FP and Shamos MI. Introduction. In Computational Geometry, pages 1–35. Springer, 1985.

[19] Fortune S. A sweepline algorithm for voronoi diagrams. Algorithmica, 2(1-4):153–174, 1987.

[20] Shamos MI and Hoey D. Closest-point problems. In Foundations of Computer Science, 1975. 16th Annual Symposium on, pages 151–162. IEEE, 1975.

[21] Green PJ and Sibson R. Computing dirichlet tessellations in the plane. The Computer Journal, 21(2):168–173, 1978.

[22] Okabe A, Boots B, Sugihara K, and Chiu SN. Spatial tessellations: concepts and applications of Voronoi diagrams, volume 501. John Wiley & Sons, 2009.

[23] Lloyd S. Least squares quantization in PCM. Information Theory, IEEE Transactions on, 28(2):129–137, 1982.

[24] Bowyer A. Computing dirichlet tessellations. The Computer Journal, 24(2):162–166, 1981.

[25] Watson DF. Computing the n-dimensional delaunay tessellation with application to voronoi polytopes. The computer journal, 24(2):167–172, 1981.

[26] Lawson CL. Software for C1 Surface Interpolation. In Mathematical Software III (J. Rice, editor), pages 161–194, 1977.

[27] Zimmer H. Voronoi and delaunay techniques. Proceedings of Lecture Notes, Computer Sciences, 8, 2005.

[28] Lingas A. A linear-time construction of the relative neighborhood graph from the delaunay triangulation. Computational Geometry, 4(4):199–208, 1994.

[29] Eppstein D. Spanning trees and spanners. Handbook of computational geometry, pages 425–461, 1999.

[30] Edelsbrunner H. Algorithms in combinatorial geometry, volume 10. Springer Science & Business Media, 1987.

[31] Kirkpatrick DG and Radke J. A framework for computational morphology. In Toussaint GT, editor, Computational Geometry, Machine Intelligence and Pattern Recognition, volume 2, pages 217–248. Elsevier, North-Holland, 1985.

[32] Jaromczyk JW and Toussaint GT. Relative neighborhood graphs and their relatives. Proceedings ofthe IEEE, 80(9):1502–1517, 1992.

[33] Johnson W and Mehl R. Reaction Kinetics in processes of nucleation and growth. Transactions of American Institute of Mining and Mettalurgical Engineers, 135:416–458, 1939.

[34] Anton F, Mioc D, and Gold CM. The voronoi diagram of circles and its
application to the visualization of the growth of particles. In Transactions on Computational Science III, pages 20–54. Springer, 2009.

[35] Anton F, Mioc D, and Gold CM. Dynamic additively weighted voronoi diagrams made easy. In Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG’98), 1998.

[36] O’Callaghan JF. An alternative definition for neighborhood of a point. IEEE Transactions on Computers, 24(11):1121–1125, 1975.

[37] Kayser K. Neighborhood condition and application of syntactic structure analysis in histopathology.ActaStereol,6:373–384,1987.

[38] Gunduz C, Yener B, and Gultekin S. The cell graphs of cancer. In ISMB/ECCB (Supplement of Bioinformatics), pages 145–151, 2004.

[39] Bilgin C, Demir C, Nagi C, and Yener B. Cell-graph mining for breast tissue modeling and classification. InEngineeringinMedicineandBiologySociety,2007.EMBS 2007.29thAnnual InternationalConferenceofthe IEEE, pages 5311–5314. IEEE, 2007.

[40] Sanfeliu A and Fu KS. A distance measure between attributed relational graphs for pattern recognition. Systems, Man and Cybernetics, IEEE Transactions on, (3):353–362, 1983.

[41] Sharma H, Alekseychuk A, Leskovsky P, Hellwich O, Anand R, Zerbe N, and Hufnagl P., Determining similarity in histological images using graph-theoretic description and matching methods for content-based image retrieval in medical diagnostics. Diagnostic pathology, 7(1):134, 2012.

[42] Wallis WD. A beginner’s guide to graph theory. Springer Science & Business Media, 2010.

[43] West DB. Introduction to Graph Theory. Prentice Hall, 2 edition, September 2000.

[44] Volkmann L. Estimations for the number of cycles in a graph. Periodica Mathematica Hungarica, 33(2):153–161, 1996.

[45] Haralick RM, Shanmugam K, and Dinstein IH. Textural features for image classification. Systems, Man and Cybernetics, IEEE Transactions on, 3(6):610–621, 1973.

[46] Brouwer AE and Haemers WH. Spectra of graphs. Springer Science & Business Media, 2011.

[47] Wilson RC, Hancock ER, and Luo B. Pattern vectors from algebraic graph theory. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27(7):1112–1124, 2005.

[48] Luo B, Wilson RC, and Hancock ER. Spectral embedding of graphs. Pattern recognition, 36(10):2213–2230, 2003.

[49] Dusser C, Rasigni M, Palmari J, Rasigni G, Llebaria A, and Marty F. Minimal spanning tree analysis of biologicalstructures. Journal oftheoretical biology, 125(3):317–323, 1987.

[50] Dussert C, Rasigni G, and Llebaria A. Quantization of directional properties in biological structures using the minimal spanning tree. Journal of theoretical biology, 135(3):295–302, 1988.

[51] Taylor TJ and Vaisman II. Graph theoretic properties of networks formed by the delaunay tessellation of protein structures. Physical Review E, 73(4):041925, 2006.

[52] Samudrala R and Moult J. A graph-theoretic algorithm for comparative modeling of protein structure. Journalofmolecularbiology,279(1):287–302, 1998.

[53] Patra S and Vishveshwara S. Backbone cluster identification in proteins by a graph theoretical method. BiophysicalChemistry,84(1):13–25,2000.

[54] Godreche C, Kostov I, and Yekutieli I. Topological correlations in cellular structures and planar graph theory. Physicalreviewletters, 69(18):2674, 1992.

[55] Dumay AC, van der Geest RJ, Gerbrands JJ, Jansen E, and Reiber J. Consistent inexact graph matching applied to labelling coronary segments in arteriograms. In Pattern Recognition, 1992. Vol. III. Conference C: Image, Speech and Signal Analysis, Proceedings, 11th IAPR International Conferenceon, pages 439–442. IEEE, 1992.

[56] Ravasz E, Somera AL, Mongru DA, Oltvai ZN, and Baraba´si AL. Hierarchical organization of modularity in metabolic networks. science, 297(5586):1551–1555, 2002.

[57] Schaller G and Meyer-Hermann M. Multicellular tumor spheroid in an off-lattice voronoi-delaunay cellmodel. PhysicalReviewE, 71(5):051910, 2005.

[58] Barabasi AL and Oltvai ZN. Network biology: understanding the cell’s functional organization. Nature Reviews Genetics, 5(2):101–113, 2004.

[59] Aittokallio T and Schwikowski B. Graph-based methods for analysing networks in cell biology. Briefings in bioinformatics, 7(3):243–255, 2006.

[60] Fu KS. Syntactic methods in pattern recognition. Elsevier, 1974.
[61] Van Diest P, Kayser K, Meijer G, and Baak J. Syntactic structure analysis. Pathologica, 87(3):255–262, 1995.

[62] Prewitt J and Wu S. An application of pattern recognition to epithelial tissues. In Proceedings of the Annual Symposium on Computer Application in Medical Care, page 15. American Medical Informatics Association, 1978.

[63] Prewitt JM. Interactive decision-making for picture processing. In Decision and Control including the 16th Symposium on Adaptive Processes and A Special Symposium on Fuzzy Set Theory and Applications, 1977 IEEE Conference on, pages 373–379. IEEE, 1977.

[64] Prewitt JM. Graphs and grammars for histology: An introduction. In Proceedings of the Annual Symposium on Computer Application in Medical Care, page 18. American Medical Informatics Association, 1979.

[65] Sanfeliu A. An application of a distance measure between graphs to the analysis of muscle tissue patterns. School of Electrical Engineering, Purdue University, 1981.

[66] Gurcan MN, Boucheron LE, Can A, Madabhushi A, Rajpoot NM, and Yener B. Histopathological image analysis: A review. Biomedical Engineering, IEEE Reviews in, 2:147–171, 2009.

[67] Darro F, Kruczynski A, Etievant C, Martinez J, Pasteels JL, and Kiss R. Characterization of the differentiation of human colorectal cancer cell lines by means of voronoi diagrams. Cytometry, 14(7):783–792, 1993.

[68] Keenan SJ, Diamond J, Glenn McCluggage W, Bharucha H, Thompson D, Bartels PH, and Hamilton PW. An automated machine vision system for the histological grading of cervical intraepithelial neoplasia (CIN). The Journal of pathology, 192(3):351–362, 2000.

[69] Altunbay D, Cigir C, Sokmensuer C, and Gunduz-Demir C. Color graphs for automated cancer diagnosis and grading. Biomedical Engineering, IEEE Transactions on, 57(3):665–674, 2010.

[70] Raymond E, Raphael M, Grimaud M, Vincent L, Binet JL, and Meyer F. Germinal center analysis with the tools of mathematical morphology on graphs. Cytometry, 14(8):848–861, 1993.

[71] Meijer G, Van Diest P, Fleege J, and Baak J. Syntactic structure analysis of the arrangement of nuclei in dysplastic epithelium of colorectal adenomatous polyps. Analytical and quantitative cytology and histology/the International Academy of Cytology [and] American Society of Cytology, 14(6):491–498, 1992.

[72] van Diest PJ, Fleege JC, and Baak J. Syntactic structure analysis in invasive breast cancer: analysis of reproducibility, biologic background, and prognostic value. Human pathology, 23(8):876–883, 1992.

[73] Coleman K, Van Diest PJ, Baak J, and Mullaney J. Syntactic structure analysis in uveal melanomas. British journal of ophthalmology, 78(11):871–874, 1994.

[74] Zaitoun A, Al Mardini H, and Record C. Quantitative assessment of gastric atrophy using the syntactic structure analysis. Journal of clinical pathology, 51(12):895–900, 1998.

[75] Kayser K, G¨ortler J, Borkenfeld S, and Kayser G. How to measure diagnosis associated information in virtualslides. Diagnostic Pathology, 6(1):1–9, 2011.

[76] Weyn B, van de Wouwer G, Kumar-Singh S, van Daele A, Scheunders P, Van Marck E, and Jacob W. Computer-assisted differential diagnosis of malignant mesothelioma based on syntactic structure analysis. Cytometry, 35(1):23–29, 1999.

[77] Guillaud M, MacAulay CE, Le Riche JC, Dawe C, Korbelik J, and Lam S. Quantitative architectural analysis of bronchial intraepithelial neoplasia. In BiOS 2000 The International Symposium on Biomedical Optics, pages 74–81. International Society for Optics and Photonics, 2000.

[78] Landini G and Othman IE. Architectural analysis of oral cancer, dysplastic, and normal epithelia. Cytometry Part A, 61(1):45–55, 2004.

[79] Basavanhally A, Agner S, Alexe G, Bhanot G, Ganesan S, and Madabhushi A. Manifold learning with graph-based features for identifying extent of lymphocytic infiltration from high grade, her2+ breast cancer histology. Image Anal. Appl. Biol.(in Conjunction MICCAI), New York [Online]. Available: http://www.miaab.org/miaab-2008-papers/27-miaab-2008-paper-21.pdf, 2008.

[80] Ulam S. Patterns of growth of figures: Mathematical aspects. In Kepes G, editor, Module, Proportion, Symmetry, Rhythm, pages 64–74. Braziller, 1966.

[81] Sudbø J, Bankfalvi A, Bryne M, Marcelpoil R, Boysen M, Piffko J, Hemmer J, Kraft K, and Reith A. Prognostic value of graph theory-based tissue architecture analysis in carcinomas of the tongue. Laboratoryinvestigation,80(12):1881–1889, 2000.

[82] Sudbø J, Marcelpoil R, and Reith A. New algorithms based on the Voronoi Diagram applied in a pilot study on normal mucosa and carcinomas. Anal Cell Pathol., 21(2):71–86, 2000.

[83] Sudbø J, Marcelpoil R, and Reith A. Caveats: numerical requirements in graph theory based quantitation of tissue architecture. Analytical Cellular Pathology, 21(2):59–69, 2000.

[84] Sudbø J, Aamdal S, Reith A, and Sudbø A. Chemoprevention of oral cancer. In Cancer Chemoprevention,pages 383–399. Springer, 2005.

[85] Kayser K, Shaver M, Modlinger F, Postl K, and Moyers J. Neighborhood Analysis of Low Magnification Structures (Glands) in Healthy, Adenomatous, and Carcinomatous Colon Mucosa. Pathology-Research and Practice, 181(2):153–158, 1986.

[86] Kayser K. Application of structural pattern recognition in histopathology. In Syntactic and structuralpattern recognition, pages 115–135. Springer, 1988.

[87] Kayser K, Kiefer B, Toomes H, and Burkhard H. Analysis of adenomatous structures in histopathology. Analytical and quantitative cytology and histology/the International Academy of Cytology [and] American Society of Cytology, 9(3):273–278, 1987.

[88] Kayser K, Kiefer B, Burkhardt H, and Shaver M. Syntactic structure analysis of bronchus carcinomas-first results. Acta Stereol, 4(2):249–253, 1985.

[89] Kayser K, Fitzer M, Bu¨lzebruck H, Bosslet K, and Drings P. TNM stage, immunohistology, syntactic structure analysis and survival in patients with small cell anaplastic carcinoma of the lung.Journalofcancerresearchandclinicaloncology, 113(5):473–480,1987.

[90] Albert R, Schindewolf T, Baumann I, and Harms H. Three-dimensional image processing for morphometric analysis of epithelium sections. Cytometry, 13(7):759–765, 1992.

[91] Bilgin CC, Bullough P, Plopper GE, and Yener B. ECM-aware cell-graph mining for bone tissue modeling and classification. Data mining and knowledge discovery, 20(3):416–438,2010.

[92] Waxman BM. Routing of multipoint connections. Selected Areas in Communications, IEEE Journal on, 6(9):1617–1622, 1988.

[93] Demir C, Gultekin SH, and Yener B. Augmented cell-graphs for automated cancer diagnosis. In ECCB/JBI, page 12, 2005.

[94] Demir C, Gultekin SH, and Yener B. Spectral analysis of cell-graphs of cancer. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York, 2004.

[95] Demir C, Gultekin SH, and Yener B. Learning the topological properties of brain tumors. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 2(3):262–270, 2005.

[96] Gunduz-Demir C. Mathematical modeling of the malignancy of cancer using graph evolution. Mathematical biosciences, 209(2):514–527, 2007.

[97] Lund A, Bilgin C, Hasan M, McKeen L, Stegemann J, Yener B, Zaki M, and Plopper G. Quantification of spatial parameters in 3d cellular constructs using graph theory. BioMed Research International, 2009, 2009.

[98] McKeen-Polizzotti L, Henderson KM, Oztan B, Bilgin CC, Yener B, and Plopper GE. Quantitative metric profiles capture three-dimensional temporospatial architecture to discriminate cellular functional states. BMC medical imaging, 11(1):11, 2011.

[99] Ficsor L, Varga VS, Tagscherer A, Tulassay Z, and Molnar B. Automated classification of inflammation in colon histological sections based on digital microscopy and advanced image analysis. Cytometry Part A, 73(3):230–237, 2008.

[100] Ficsor L, Varga V, Berczi L, Miheller P, Tagscherer A, Wu MLc, Tulassay Z, and Molnar B. Automated virtual microscopy of gastric biopsies. Cytometry Part B: Clinical Cytometry, 70(6):423–431, 2006.

[101] Ali S, Veltri R, Epstein JA, Christudass C, and Madabhushi A. Cell cluster graph for prediction of biochemical recurrence in prostate cancer patients from tissue microarrays. In SPIE Medical Imaging, pages 86760H–86760H. International Society for Optics and Photonics, 2013.

[102] Fatakdawala H, Xu J, Basavanhally A, Bhanot G, Ganesan S, Feldman M, Tomaszewski JE, and Madabhushi A. Expectation–maximization-driven geodesic active contour with overlap resolution (emagacor): Application to lymphocyte segmentation on breast cancer histopathology. Biomedical Engineering, IEEE Transactions on, 57(7):1676–1689, 2010.

[103] Kayser K, Sandau K, B¨ohm G, Kunze KD, and Paul J. Analysis of soft tissue tumors by an attributed minimum spanning tree. Analytical and quantitative cytology and histology/the International Academy of Cytology [and] American Society of Cytology, 13(5):329–334, 1991.

[104] Chaudhuri B, Rodenacker K, and Burger G. Characterization and featuring of histological section images. Pattern recognitionletters, 7(4):245–252, 1988.

[105] Dougherty ER. An introduction to morphological image processing. Tutorial texts in optical engineering, 1992.

[106] de Assis Zampirolli F, Stransky B, Lorena AC, and de Melo Paulon FL. Segmentation and classification of histological images-application of graph analysis and machine learning methods. In Graphics, Patterns and Images(SIBGRAPI), 2010 23rd SIBGRAPI Conference on, pages 331–338. IEEE, 2010.

[107] Zampirolli FdA. Neighborhood graphs built with morphological operators. Revista de Informa´tica Aplicada/Journal of Applied Computing, 4(2), 2010.

[108] Lee G, Sparks R, Ali S, Shih NN, Feldman MD, Spangler E, Rebbeck T, Tomaszewski JE, and Madabhushi A. Co-Occurring Gland Angularity in Localized Subgraphs: Predicting Biochemical Recurrence in Intermediate-Risk Prostate Cancer Patients. PloSone, 9(5):e97954, 2014.

[109] Hamilton P, Allen D, Watt P, Patterson C, and Biggart J. Classification of normal colorectal mucosa and adenocarcinoma by morphometry. Histopathology, 11(9):901–911, 1987.

[110] Hamilton P, Anderson N, Bartels P, and Thompson D. Expert system support using bayesian belief networks in the diagnosis of fine needle aspiration biopsy specimens of the breast. J Clin Pathol, 47(4):329–36, 1994.

[111] Hamilton PW, Bartels PH, Thompson D, Anderson NH, Montironi R, and Sloan JM. Automated location of dysplastic fields in colorectal histology using image texture analysis. The Journal of pathology, 182(1):68–75, 1997.

[112] Walker RF, Jackway P, Lovell B, and Longstaff I. Classification of cervical cell nuclei using morphological segmentation and textural feature extraction. In Intelligent Information Systems, 1994. Proceedings of the 1994 Second Australian and New Zealand Conference on, pages 297–301. IEEE, 1994.

[113] Wiltgen M, Gerger A, and Smolle J. Tissue counter analysis of benign common nevi and malignant melanoma. International journal of medical informatics, 69(1):17–28, 2003.

[114] Zhao D, Chen Y, and Correa N. Statistical categorization of human histological images. In Image Processing, 2005. ICIP 2005. IEEE International Conference on, volume 3, pages III–628. IEEE, 2005.

[115] Yang L, Chen W, Meer P, Salaru G, Goodell LA, Berstis V, and Foran DJ. Virtual microscopy and grid-enabled decision support for large-scale analysis of imaged pathology specimens. Information Technology in Biomedicine, IEEE Transactions on, 13(4):636–644, 2009.

[116] Kong J, Sertel O, Shimada H, Boyer K, Saltz J, and Gurcan M. Computer-aided Evaluation of Neuroblastoma on Whole-slide Histology Images: Classifying Grade of Neuroblastic Differentiation. Pattern Recogn., 42(6):1080–1092, June 2009.

[117] Sertel O, Kong J, Shimada H, Catalyurek U, Saltz JH, and Gurcan MN. Computer-aided prognosis of neuroblastoma on whole-slide images: Classification of stromal development. Pattern recognition, 42(6):1093–1103, 2009.

[118] Wong E and Fu K. A Parallel Algorithm for Muscle Tissue Images Classification. In Proceedings/the... Annual Symposium on Computer Application [sic] in Medical Care. Symposium on Computer Applications in Medical Care, pages 751–754. American Medical Informatics Association, 1983.

[119] D´ıaz G and Romero E. Histopathological image classification using stain component features on a PLSA model. In Progressin Pattern Recognition, Image Analysis, Computer Vision, and Applications, pages 55–62. Springer, 2010.

[120] Deligdisch L, Kerner H, Cohen C, Dargent D, and Gil J. Morphometric differentiation between responsive tumor cells and mesothelial hyperplasia in second-look operations for ovarian cancer. Human pathology, 24(2):143–147, 1993.

[121] Thiran JP and Macq B. Morphological feature extraction for the classification of digital images of canceroustissues. Biomedical Engineering, IEEE Transactionson, 43(10):1011–1020,1996.

[122] Nedzved A, Belotserkovsky A, Lehmann T, and Ablameyko S. Morphometrical feature extraction on color histological images for oncological diagnostics. In 5th International Conference on Biomedical Engineering, pages 14–16, 2007.

[123] Roula M, Diamond J, Bouridane A, Miller P, and Amira A. A multispectral computer vision system for automatic grading of prostatic neoplasia. In Proceedings IEEE International Symposium on Biomedical Imaging, pages 193–196, 2002.

[124] Rajpoot K and Rajpoot NM. Hyperspectral colon tissue cell classification. MSc DSIP Dissertation, Faculty of Computing Sciences & Engineering, De Montfort University, UK, September 2003.

[125] De Wouwer V, Marck V, Dyck V, et al. Wavelets as chromatin texture descriptors for the automated identification of neoplastic nuclei. Journal of microscopy, 197(1):25–35, 2000.

[126] Jafari-Khouzani K and Soltanian-Zadeh H. Multiwavelet grading of pathological images of prostate. Biomedical Engineering, IEEE Transactions on, 50(6):697–704, 2003.

[127] Qureshi H, Sertel O, Rajpoot N, Wilson R, and Gurcan M. Adaptive discriminant wavelet packet transform and local binary patterns for meningioma subtype classification. In Medical Image Computing and Computer-Assisted Intervention–MICCAI 2008, pages 196–204. Springer, 2008.

[128] Kayser K and Stute H. Minimum Spanning Tree, Voronoi’s Tesselation, Johnson-Mehl Diagrams in Human Lung Carcinoma. Pathology-Research and Practice, 185(5):729–734, 1989.

[129] Kayser K, Stute H, Bubenzer J, and Paul J. Combined morphometrical and syntactic structure analysis as tools for histomorphological insight into human lung carcinoma growth. Analytical cellular pathology: the journal of the European Society for Analytical Cellular Pathology, 2(3):167–178, 1990.

[130] Kayser K, Liewald F, Kremer K, and Tacke M. Integrated optical density (IOD), syntactic structure analysis, and survival in operated lung carcinoma patients. Pathology-Research and Practice, 190(11):1031–1038, 1994.

[131] Kayser K, Liewald F, Kremer K, Tacke M, Storck M, Faber P, and Bonomi P. Alteration of integrated optical density and intercellular structure after induction chemotherapy and survival in lung carcinoma patients treated surgically. Analytical and quantitative cytology and histology/the International Academy of Cytology [and] American Society of Cytology, 16(1):18–24, 1994.

[132] Kayser K, Jacinto S, B¨ohm G, Fritz P, Kunze W, Nehrlich A, and Gabius H .Application of Computer-assisted Morphometry to the Analysis of Prenatal Development of Human Lung. Anatomia, histologia, embryologia, 26(2):135–139, 1997.

[133] Kayser K, Bovin N, Zeng F, Zeilinger C, and Gabius H. Binding capacities to blood-group antigens A, B and H, DNA and MST measurements, and survival in bronchial carcinoma. Radiol. Oncol, 28:282–286, 1994.

[134] Kayser K, Kayser C, Rahn W, Bovin NV, and Gabius HJ. Carcinoid tumors of the lung: Immuno-and ligandohistochemistry, analysis of integrated optical density, syntactic structure analysis, clinical data, and prognosis of patients treated surgically. Journal of surgical oncology, 63(2):99–106, 1996.

[135] Kayser K, Kayser C, Rahn W, Bovin NV, and Gabius HJ. Carcinoid tumors of the lung: Immuno-and ligandohistochemistry, analysis of integrated optical density, syntactic structure analysis, clinical data, and prognosis of patients treated surgically. Journal of surgical oncology, 63(2):99–106, 1996.

[136] Kayser K, Richter B, Stryciak R, and Gabius HJ. Parameters derived from integrated nuclear fluorescence, syntactic structure analysis, and vascularization in human lung carcinomas. Analytical Cellular Pathology, 15(2):73–83, 1997.

[137] Kayser K, Trott J, B¨ohm G, Huber M, Kaltner H, Andr´e S, and Gabius HJ. Localized fibrous tumors (LFTs) of the pleura: Clinical data, asbestos burden, and syntactic structure analysis appliedtonewlydefined angiogenic/growth-regulatory effectors. Pathology-ResearchandPractice, 201(12):791–801, 2005.

[138] Kayser K, Borkenfeld S, Djenouni A, and Kayser G. Texture and object related image analysis inmicroscopic images. DiagnosticPathology,1(1), 2015.

[139] Weyn B, Van De Wouwer G, Koprowski M, Van Daele A, Dhaene K, Scheunders P, Jacob W, and Van Marck E. Value of morphometry, texture analysis, densitometry, and histometry in the differential diagnosis and prognosis of malignant mesothelioma. The Journal of pathology, 189(4):581–589, 1999.

[140] Weyn B, Tjalma W, Vermeylen P, Van Daele A, Van Marck E, and Jacob W. Determination of tumour prognosis based on angiogenesis-related vascular patterns measured by fractal and syntactic structure analysis. Clinical Oncology, 16(4):307–316, 2004.

[141] Doyle S, Hwang M, Shah K, Madabhushi A, Feldman M, and Tomaszeweski J. Automated Grading of Prostate Cancer using architectural and textural image Features. 4th IEEE International Symposium on Biomedical Imaging, pages 1284–1287, 2007.

[142] Doyle S, Agner S, Madabhushi A, Feldman M, and Tomaszewski J. Automated grading of breast cancer histopathology using spectral clustering with textural and architectural image features. In Biomedical Imaging: From Nano to Macro, 2008. ISBI 2008. 5th IEEE International Symposium on, pages 496–499. IEEE, 2008.

[143] Doyle S, Feldman MD, Shih N, Tomaszewski J, and Madabhushi A. Cascaded discrimination of normal, abnormal, and confounder classes in histopathology: Gleason grading of prostate cancer. BMC bioinformatics, 13(1):282, 2012.

[144] Doyle S, Hwang M, Naik S, Feldman M, Tomaszeweski J, and Madabhushi A. Using manifold learning for content-based image retrieval of prostate histopathology. In MICCAI 2007 Workshop on Content-based Image Retrieval for Biomedical Image Archives: Achievements, Problems,and Prospects, pages 53–62. Citeseer, 2007.

[145] Madabhushi A, Doyle S, Lee G, Basavanhally A, Monaco JP, Master SR, Tomaszewski JE, and Feldman MD. Review: Integrated diagnostics: a conceptual framework with examples. Clinical Chemistry and Laboratory Medicine,48:989–998, 2010.

[146] Basavanhally AN, Ganesan S, Agner S, Monaco JP, Feldman MD, Tomaszewski JE, Bhanot G, and Madabhushi A. Computerized image-based detection and grading of lymphocytic infiltration in her2+ breast cancer histopathology. Biomedical Engineering, IEEE Transactions on, 57(3):642–653, 2010.

[147] Basavanhally A, Ganesan S, Feldman MD, Shih N, Mies C, Tomaszewski J, and Madabhushi A. Multi-field-of-view framework for distinguishing tumor grade in ER+ breast cancer from entire histopathology slides. IEEE Trans. Biomed. Engineering, 60(8):2089–2099, 2013.

[148] Choi HK, Jarkrans T, Bengtsson E, Vasko J, Wester K, Malmstro¨m PU, and Busch C. Image analysis based grading of bladder carcinoma. Comparison of object, texture and graph based methods and their reproducibility. Analytical Cellular Pathology, 15(1):1–18, 1997.

[149] Guillaud M, Cox D, Adler-Storthz K, Malpica A, Staerkel G, Matisic J, Van Niekerk D, Poulin N, Follen M, and MacAulay C. Exploratory analysis of quantitative histopathology of cervical intraepithelial neoplasia: Objectivity, reproducibility, malignancy-associated changes, and human papillomavirus. Cytometry Part A, 60(1):81–89, 2004.

[150] Huang CH, Veillard A, Roux L, Lom´enie N, and Racoceanu D. Time-efficient sparse analysis of histopathological whole slide images. Computerized medical imaging and graphics, 35(7):579– 591, 2011.

[151] Aksoy S, Marchisio GB, Tusk C, and Koperski K. Interactive classification and content based retrieval of tissue images. In International Symposium on Optical Science and Technology, pages 71–81. International Society for Optics and Photonics, 2002.

[152] Lee LQ and Lumsdaine A. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2002.

[153] Microsoft. QuickGraph, Graph Data Structures And Algorithms for .NET. https://quickgraph.codeplex.com/documentation, 2011.

[154] Andres B, Beier T, and Kappes JH. OpenGM: A C++ Library for Discrete Graphical Models. CoRR, abs/1206.0111, 2012.

[155] Dezso B, Jüttner A, and Kov´acs P. LEMON–an open source C++ graph template library. Electronic Notes in Theoretical Computer Science, 264(5):23–45, 2011.

[156] Fisher D, Omadadhain J, Smyth P, White S, and Boey YB. Analysis and visualization of network data using JUNG. Journal of Statistical Software, 10(2):1–35, 2005.

[157] MathWorks. Computational Geometry. http://de.mathworks.com/help/matlab/computational-geometry.html/, 1994-2015.

[158] MathWorks. Bioinformatics Toolbox. http://de.mathworks.com/products/bioinfo/, 1994-2015.

[159] MathWorks. Symbolic Math Toolbox. http://de.mathworks.com/products/symbolic/, 1994- 2015.

[160] BenDi. Fortune’s Voronoi algorithm implemented in C#.
http://www.codeproject.com/KB/ recipes/fortunevoronoi.aspx, 2013.

[161] EmguCV. Emgu CV: OpenCV in .NET (C#, VB, C++ and more), 2013.

[162] Bradski G and Kaehler A. Learning OpenCV: Computer vision with the OpenCV library. ”O’Reilly Media, Inc.”, 2008.

[163]OpenCV. Planar Subdivisions. http://docs.opencv.org/modules/legacy/doc/planar_subdivisions.html, 2010.

[164] NetTopologySuite. NetTopologySuite. https://github.com/NetTopologySuite/NetTopologySuite, 2006.

[165] Davis M. JTS Topology Suite. http://tsusiatsoftware.net/jts/main.html, 2012.

[166] Davis M. Secrets of the JTS Topology Suite. Free and Open Source Software for Geospatial, 2007.

[167] Guibas L and Stolfi J. Primitives for the manipulation of general subdivisions and the computation of voronoi. ACM Transactions on Graphics (TOG), 4(2):74–123, 1985.

[168] Lischinski D. Incremental delaunay triangulation. In Heckbert PS, editor, Graphics gems IV, volume 4, pages 47–59. Morgan Kaufmann, 1994.

[169] Nielsen M. Delaunay Triangulation in C#. http://paulbourke.net/papers/triangulate/morten.html, 2006.

[170] Bourke P. Efficient triangulation algorithm suitable for terrain modelling. In Pan Pacific Computer Conference, Beijing, China, 1989.

[171] Sydorchuk A. Boost.Polygon Voronoi Library. http://www.boost.org/doc/libs/1_54_0/libs/polygon/doc/index.htm, 2012.

[172] Demming R and Duffy DJ. Introduction to the Boost C++ Libraries; Volume IFoundations. Datasim Education BV, 2010.

[173] Liang W. Poly2Tri: Fast and Robust Simple Polygon Triangulation With/Without Holes by Sweep Line Algorithm, 2005.

[174] Domiter V and Zcalik B. Sweep-line algorithm for constrained delaunay triangulation. International Journal of Geographical Information Science, 22(4):449–462, 2008.

[175] Zerbe N, Hufnagl P, and Schlu¨ns K. Distributed computing in image analysis using open source frameworks and application to image sharpness assessment of histological whole slide images. Diagn Pathol, 6(Suppl 1):S16, 2011.

[176] Wienert S, Heim D, Saeger K, Stenzinger A, Beil M, Hufnagl P, Dietel M, Denkert C, and Klauschen F. Detection and Segmentation of Cell Nuclei in Virtual Microscopy Images: A Minimum-Model Approach. Scientific Reports, 2, 2012.

[177] Sharma H, Zerbe N, Heim D, Wienert S, Behrens HM, Hellwich O, and Hufnagl P. A Multi- resolution Approach for combining Visual Information Using Nuclei Segmentation and Classification in Histopathological Images. In Proceedings of the International Conference on Computer Vision Theory and Applications, pages 37–46,
How to Cite
SHARMA, Harshita et al. A review of graph-based methods for image analysis in digital histopathology. Diagnostic Pathology, [S.l.], aug. 2015. ISSN 2364-4893. Available at: <http://www.diagnosticpathology.eu/content/index.php/dpath/article/view/61>. Date accessed: 26 nov. 2020. doi: https://doi.org/10.17629/www.diagnosticpathology.eu-2015-1:61.
Review Articles


Digital histopathology, graph-based methods, whole slide images, medical image analysis, image understanding, tissue architecture, spatial arrangement