# Methods of converting an image to graph

In my thesis on object recognition based on spatial relations and visual features, I need to convert the images to graphs to be able to work on their spatial relations. Could you introduce some methods you're familiar with along with their advantages and disadvantages? Google yielded no relevant results.

I haven't done much research yet, except for reading a few articles to get familiar with different approaches and methods and have a clear view of what I want to do. Going through this article, a method is proposed for converting an image to graph, which is called irregular pyramids. So all I want to know is whether there are other methods for such propose?

• it's not clear what you are asking. what do you expect from such a graph? Dec 26, 2013 at 17:03
• no, not really. what specifically do you need from the conversion of the graph to the image. what are you going to do with the graph? Dec 26, 2013 at 17:10
• I haven't done much research yet — Then it's too early to ask here. Dec 29, 2013 at 14:08
• I still have problems with this question. As far as I can understand, you want to take images and map them to graphs so that (connected?) regions in images that are 'similar' map to 'similar' (connected?) subgraphs. The fact that you did not define what you're looking for even at this level of precision is what I do not like. And then, you also need to define 'similar' in both domains (images and graphs).Until you do that, this is not really within the realm of TCS(it may fit cross validated). Dec 29, 2013 at 15:46
• On a side note, I think it's strange that you make up your mind to use graph matching before you know how to do the conversion to graphs. Why is graph matching the best choice for you apriori? I am not an expert, but I've heard SIFT features together with the earth-mover distance to compare histograms has had quite a bit of success in comparing images. Dec 29, 2013 at 15:48

This paper may be useful and it may lead you in the right direction. "Graph-theoretical Methods In Computer Vision," available at http://www.cs.toronto.edu/~sven/Papers/graph02.pdf".

I'm not an expert, but perhaps this recent survey can help you:

K. Santle Camilus, V. K. Govindan, A Review on Graph Based Segmentation; I.J. Image, Graphics and Signal Processing, 2012, 5, 1-13

Abstract: ... The major four categorizations we have employed for the purpose of review are: graph cut based methods, interactive methods, minimum spanning tree based methods and pyramid based methods. This review not only reveals the pros in each method and category but also explores its limitations. ...

unfortunately as pointed out in many comments the question is still a little too vague to be very specific. graphs are used in very many contexts in image analysis. however as mentioned in other answer(s), indeed one of the main uses is image segmentation, basically the representation of the local spatial areas of an image as a graph, and there are several surveys in this area. image segmentation seems to be sufficient for your application but it would be better if you were more specific about your application. here are several surveys on graph-based image segmentation.