Improvement of graph-based algorithms for image analysis

14 Novembre 2023

---

Catégorie : Stagiaire

---

Context

The efficient algorithms developed in the context of graphs have had a strong impact in the field of image processing and analysis. In this context, images are classically represented by regular graphs, called grids, in which the pixels are represented by vertices, and neighbor pixels are connected by (weighted) edges.

One of the main pre-processing tasks when dealing with images is to obtain a partition of the pixels into regions of interests [2], in which each region is homogeneous according to a given criterion (color, texture, ...). Among its several applications, one can cite object detection, recognition and tracking, image compression. In order to deal with the large amount of data currently available, one has to obtain high efficiency image pre-processing algorithms. The approach that we consider in this project is to apply the most recent advances in graph theory in order to improve the current image algorithms. In particular, grids are simple graphs that are planar and with maximum degree 4. Thus, it is expected that algorithms coming from parameterized complexity [1] can provide interesting improvement.

 

Tasks

In this internship, the selected student is expected to :

• Read and explain the basic bibliography on the two topics (images and graph theory).

• Propose some ideas for improvement of the known algorithms for image segmentation using elements from graph theory.

• Analyze the complexity of the given algorithm.

• It is not expected for the student to implement the algorithm but this can be done if wanted.

• The obtained results should be written down at the end of the internship. If the results are good enough, a scientific publication can be expected.

 

Application

It is expected from a candidate to have some solid notions of algorithmic. Basic notions of graph theory would be appreciated. If you are interested in this internship proposition, please send us your CV and transcripts to deise.santanamaia@univ-lille.fr and julien.baste@univ-lille.fr. The remuneration for the internship is regulated by French’s laws and should be around 540€ a month.

 

References

[1] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.

[2] Pedro F Felzenszwalb and Daniel P Huttenlocher. Efficient graph-based image segmentation. International journal of computer vision, 59:167–181, 2004.