Deadline for sending applications: 30 November 2013. Project proposed by Radu Horaud, Marianne Clausel, and Georgios Evangelidis.
An example of color-depth data represented as a undirected weighted graph, or a meshed surface and keypoints detected on this graph. See reference [5] for more details.
The most successful image representation frameworks are based on the detection and localization of interest points, or keypoints [1]. Interest points are present in an image whenever the local image structure is rich, e.g., presence of edges or of texture. Combined with local image descriptors [2], interest points are the features of choice for representing visual content, e.g., the bag-of-words paradigm [3], for the purposes of image indexing or of object recognition. These interest-point detectors and local descriptors were also extended to image sequences (videos) and a number of spatio-temporal detectors and descriptors have been recently proposed. These methods consider a small volume in the image-time domain and extend two-dimensional (2D) interest points to 3D (2D+time), [4]. While these 2D and 3D keypoint detection methods are powerful tools for describing data, they are limited to regular-grid domains, e.g., images and image sequences, and their extension to non-regular domains, such as graphs, is far from being straightforward. For example, non-regular data are delivered by 3D visual sensors. A 3D sensor, such as the Kinect camera, delivers both a depth image and a color image that can be easily aligned. The depth data correspond to a 3D cloud of points. This suggests that the color-depth (or RGB-D) data can in turn be described as a weighted undirected graph: each graph vertex corresponds to a 3D point and each graph edge has a weight that corresponds to the similiarity between two vertices. This graph can be enriched with color information that can then be viewed as a scalar-valued function (or vector-valued, depending on the color representation being used) defined over the graph vertices. The advantage of this graph representation is that it simulataneously embeds the two main pieces of information conveyed with visual data: photometry and geometry [5]. Moreover, it conveys the intrinsic geometric structure of 3D scenes or objects. There were attempts to apply classical image processing techniques in the graph setting. But processing graph data in the same way as 2D or 3D regular-grid data ignores key dependencies arising from the irregular domain. First, it is of high importance to take into account the underlying graph structure [6], and this is not at all an obvious task, as is on regular grids. Second, many concepts that are well understood in image and signal processing (filtering, convolution, etc.) become technically challenging in the graph domain [6]. This is problematic because these concepts reside at the core of many keypoint detection methods, i.e., multi-resolution data representation and detection of discontinuities. The objective of this master projet is twofold:
- Establish a concise state of the art in the emerging field of data processing on graphs that combines spectral graph theory with computational harmonic analysis;
- Apply concepts from this new research field to visual-data processing, investigate ways to characterize color-depth data, and develop a method to extract local structures (keypoints) using wavelets on graphs [7].
We seek a very motivated candidate that should have strong background in signal processing and applied mathematics, as well as very good programming skills in C and Matlab. References [1] K. Mikolajczyk and C. Schmid. Scale & affine invariant interest point detectors. International Journal of Computer Vision, 60(1), 63–86, 2004. [2] K. Mikolajczyk and C. Schmid. A performance evaluation of local descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(10), 1615–1630, 2005. [3] G. Csurka, C. R. Dance, L. Fan, J. Willamowski, C. Bray. Visual categorization with bags of keypoints. ECCV Workshop on Statistical Learning in Computer Vision, 2004 [4] I. Laptev. On space-time interest points. International Journal of Computer Vision, 64(2–3), 107–123, 2005. [5] A. Zaharescu, E. Boyer, and R. Horaud. Keypoints and local descriptors of scalar functions on 2D manifolds. International Journal of Computer Vision, 2012. [6] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega and P. Vandergheynst. The emerging field of signal processing on graphs. IEEE Signal Processing Magazine, 2012. [7] D. Hammond, P. Vandergheynst, and R. Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 2009.
