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

<p><a href="http://www.mecs-press.org/ijigsp/ijigsp-v4-n5/IJIGSP-V4-N5-1.pdf">K. Santle Camilus, V. K. Govindan, A Review on Graph Based Segmentation;
I.J. Image, Graphics and Signal Processing, 2012, 5, 1-13</a></p>

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

CC BY-SA 3.0
2013-12-29T10:39:44.403Z
2013-12-29T10:39:44.403Z
Marzio De Biasi
<p>unfortunately as pointed out in many comments the question is still a little too vague to be very specific. graphs are used in <em>very many</em> contexts in image analysis. however as mentioned in other answer(s), indeed one of the main uses is <a href="http://en.wikipedia.org/wiki/Image_segmentation" rel="nofollow">image segmentation</a>, 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.</p>

<ul>
<li><a href="http://www4.comp.polyu.edu.hk/~cslzhang/paper/PR_2012_review.pdf" rel="nofollow">A Survey of Graph Theoretical Approaches to Image Segmentation</a>, Peng, Zhang, Zhang</li>
<li><a href="http://www.ijsce.org/attachments/File/v2i6/F1121112612.pdf" rel="nofollow">Survey on Image Segmentation Using Graph
Based Methods</a> Nalina.P, Muthukannan.K</li>
<li><a href="http://su.digitaluniversity.ac/downloads/2%20_1.pdf" rel="nofollow">GRAPH THEORETICAL APPROACHES FOR IMAGE SEGMENTATION</a> Basavaprasad B., Ravindra S. Hegadi</li>
</ul>

CC BY-SA 3.0
2013-12-29T16:55:15.183Z
2013-12-29T16:55:15.183Z
vzn
<p>This paper may be useful and it may lead you in the right direction. "Graph-theoretical Methods In Computer Vision," available at <a href="http://www.cs.toronto.edu/~sven/Papers/graph02.pdf" rel="nofollow">http://www.cs.toronto.edu/~sven/Papers/graph02.pdf</a>".</p>

CC BY-SA 3.0
2013-12-29T15:35:20.277Z
2013-12-30T05:53:35.843Z
2013-12-30T05:53:35.843Z
lgidwani
<p>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. </p>

<p>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 <a href="http://link.springer.com/article/10.1007/s11042-011-0938-3" rel="nofollow">this article</a>, a method is proposed for converting an image to graph, which is called <strong>irregular pyramids</strong>. So all I want to know is whether there are other methods for such propose?</p>

CC BY-SA 3.0
2013-12-26T17:03:38.320Z
it's not clear what you are asking. what do you expect from such a graph?
Sasho Nikolov
CC BY-SA 3.0
2013-12-26T17:06:51.060Z
@Sasho Nikolov:  As I said,  I want to work on spatial relations of regions and partitions of the graph which is a converted form of an image.  Is it clear?
Gigili
CC BY-SA 3.0
2013-12-26T17:10:57.550Z
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?
Sasho Nikolov
CC BY-SA 3.0
2013-12-26T17:19:30.127Z
@Sasha Nikolov: l'll compute a spatial descriptor and will apply some graph matching methods on the graphs afterwards. I am afraid I don't get your exact meaning.
Gigili
CC BY-SA 3.0
2013-12-26T19:16:51.737Z
Gigili, I'm going to agree with Sasho Nikolov.  Your question is too vague to answer in its current form.  You should start by telling us what your real problem is: e.g., how you will use the graph, what criteria or metrics you will use for evaluating any candidate method, etc.  You should also tell us what approaches you have considered so far and what research you've done already.  (Google is not a replacement for a literature survey; and FYI, we expect you to do serious research on your own before asking here, and make a serious effort to ask a polished, clearly-posed question.)
D.W.
CC BY-SA 3.0
2013-12-26T21:00:39.867Z
OK then, I will try to edit my question accordingly.
Gigili
CC BY-SA 3.0
2013-12-27T01:31:09.177Z
I think this is a more a AI/Vision and Computer Graphics/Image Processing question than a TCS question and therefore seems more suitable for [stats.se] or [cs.se].
Kaveh
CC BY-SA 3.0
2013-12-29T10:17:17.233Z
@SashoNikolov: I've edited my question to add more information.
Gigili
CC BY-SA 3.0
2013-12-29T10:18:02.360Z
Also, @D.W. and other people. I hope it's in the scope of this site now and would appreciate any helps.
Gigili
CC BY-SA 3.0
2013-12-29T10:29:47.293Z
Ok, I didn't see the edit. I delete the commen.
Marzio De Biasi
CC BY-SA 3.0
2013-12-29T14:08:36.710Z
_I haven't done much research yet_ — Then it's too early to ask here.
Jeffε
CC BY-SA 3.0
2013-12-29T14:13:48.203Z
@JɛﬀE: I meant I haven't carried out extensive research to be able to post its results here, as they asked me.
Gigili
CC BY-SA 3.0
2013-12-29T15:46:07.893Z
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).
Sasho Nikolov
CC BY-SA 3.0
2013-12-29T15:48:59.140Z
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.
Sasho Nikolov
<graph-theory><image-processing>
Methods of converting an image to graph
Gigili
# Methods of converting an image to graph

(Asked by: username_0 on 2013-12-26)

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](http://link.springer.com/article/10.1007/s11042-011-0938-3), 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?

**Tags:** graph-theory, image-processing

> **Comments:**
> **username_1**: it's not clear what you are asking. what do you expect from such a graph?  
> **username_0**: @username_1:  As I said,  I want to work on spatial relations of regions and partitions of the graph which is a converted form of an image.  Is it clear?  
> **username_1**: 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?  
> **username_0**: @Sasha Nikolov: l'll compute a spatial descriptor and will apply some graph matching methods on the graphs afterwards. I am afraid I don't get your exact meaning.  
> **username_2**: username_0, I'm going to agree with username_1.  Your question is too vague to answer in its current form.  You should start by telling us what your real problem is: e.g., how you will use the graph, what criteria or metrics you will use for evaluating any candidate method, etc.  You should also tell us what approaches you have considered so far and what research you've done already.  (Google is not a replacement for a literature survey; and FYI, we expect you to do serious research on your own before asking here, and make a serious effort to ask a polished, clearly-posed question.)  
> **username_0**: OK then, I will try to edit my question accordingly.  
> **username_3**: I think this is a more a AI/Vision and Computer Graphics/Image Processing question than a TCS question and therefore seems more suitable for [stats.se] or [cs.se].  
> **username_0**: @SashoNikolov: I've edited my question to add more information.  
> **username_0**: Also, @username_2 and other people. I hope it's in the scope of this site now and would appreciate any helps.  
> **username_4**: Ok, I didn't see the edit. I delete the commen.  
> **username_5**: _I haven't done much research yet_ — Then it's too early to ask here.  
> **username_0**: @JɛﬀE: I meant I haven't carried out extensive research to be able to post its results here, as they asked me.  
> **username_1**: 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).  
> **username_1**: 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.  

---

## 3 answers

### Answer by username_7 on 2013-12-29. Score: 6 | Accepted answer

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>".


---

### Answer by username_4 on 2013-12-29. Score: 6

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](http://www.mecs-press.org/ijigsp/ijigsp-v4-n5/IJIGSP-V4-N5-1.pdf)

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. ...


---

### Answer by username_6 on 2013-12-29. Score: 0

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](http://en.wikipedia.org/wiki/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.

* [A Survey of Graph Theoretical Approaches to Image Segmentation](http://www4.comp.polyu.edu.hk/~cslzhang/paper/PR_2012_review.pdf), Peng, Zhang, Zhang
* [Survey on Image Segmentation Using Graph
  Based Methods](http://www.ijsce.org/attachments/File/v2i6/F1121112612.pdf) Nalina.P, Muthukannan.K
* [GRAPH THEORETICAL APPROACHES FOR IMAGE SEGMENTATION](http://su.digitaluniversity.ac/downloads/2%20_1.pdf) Basavaprasad B., Ravindra S. Hegadi


---

