Optical Graph Recognition

Auer, Christopher and Bachmaier, Christian and Brandenburg, Franz Josef and Gleißner, Andreas and Reislhuber, Josef (2013) Optical Graph Recognition. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 529-540 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_47).

Full text not available from this repository.


Optical graph recognition (OGR) reverses graph drawing. A drawing transforms the topological structure of a graph into a graphical representation. Primarily, it maps vertices to points and displays them by icons and it maps edges to Jordan curves connecting the endpoints. OGR transforms the digital image of a drawn graph into its topological structure. It consists of four phases, preprocessing, segmentation, topology recognition, and postprocessing. OGR is based on established digital image processing techniques. Its novelty is the topology recognition where the edges are recognized with emphasis on the attachment to their vertices and on edge crossings. Our prototypical implementation $OGR^{up}$ shows the effectiveness of the approach and produces a GraphML file which can be used for further algorithmic studies and graph drawing tools.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_47
Classifications:S Software and Systems > S.999 Others
ID Code:1340

Repository Staff Only: item control page


Bachmaier, C., Brandenburg, F.J., Forster, M., Holleis, P., Raitner, M.: Gravisto: Graph Visualization Toolkit. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 502–503. Springer, Heidelberg (2005), http://gravisto.fim.uni-passau.de/

Borgefors, G.: Distance transformations in digital images. Computer Vision, Graphics and Image Processing 34(3), 344–371 (1986)

Bunke, H., Wang, P.S.: Handbook of Character Recognition and Document Image Analysis. World Scientific (1997)

Castleman, K.R.: Digital Image Processing. Prentice-Hall (1996)

Cauchie, J., Fioletb, V., Villers, D.: Optimization of an Hough transform algorithm for the search of a center. Pattern Recogn. 41, 567–574 (2008)

Chow, C.K., Kaneko, T.: Automatic boundary detection of the left ventricle from cineangiograms. Comput. Biomed. Res. 5(4), 388–410 (1972)

Condurache, A.P., Aach, T.: Vessel segmentation in angiograms using hysteresis thresholding. In: IAPR Conference on Machine Vision Applications 2005, pp. 269–272 (2005)

Davies, E.R.: A modified Hough scheme for general circle location. Pattern Recogn. Lett. 7(1), 37–43 (1988)

Davies, E.R.: Machine Vision: Theory, Algorithms, Practicalities, 2nd edn. Academic Press (1997)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall (1999)

Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156–5166 (2011)

Duda, R.O., Hart, P.E.: Use of the Hough transformation to detect lines and curves in pictures. Commun. ACM 15(1), 11–15 (1972)

Estrada, R., Tomasi, C.: Manuscript bleed-through removal via hysteresis thresholding. In: Proc. International Conference on Document Analysis and Recognition, ICDAR 2009. IEEE (2009)

Gonzalez, R.C., Woods, R.E.: Digital Image Processing, 2nd edn. Prentice-Hall (2002)

Huang, W., Eades, P., Hong, S.H.: Beyond time and error: A cognitive approach to the evaluation of graph drawings. In: Proc. Beyond Time and Errors: Novel Evaluation Methods for Information Visualization, BELIV 2008, pp. 3:1–3:8. ACM (2008)

Huang, W., Eades, P., Hong, S.H.: Measuring effectiveness of graph visualizations: A cognitive load perspective. Inform. Visual. 8(3), 139–152 (2009)

Huang, W., Hong, S.H., Eades, P.: Effects of crossing angles. In: Fujishiro, I., Li, H., Ma, K.L. (eds.) Proc. IEEE Pacific Visualization Symposium, PacificVis 2008, pp. 41–46. IEEE (2008)

Lauren, V., Pisinger, G.: Automated analysis of vessel diameters in MR images. Visualization, Imaging, and Image Processing, 931–936 (2004)

Pach, J.: Every Graph Admits an Unambiguous Bold Drawing. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 332–342. Springer, Heidelberg (2012)

Reislhuber, J.: Graph Recognition. Master’s thesis, University of Passau (2011), http://www.infosun.fim.uni-passau.de/br/publications/mt-reislhuber-2011.pdf

Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 292, 107–117 (1965)