6533b7dbfe1ef96bd127111a

RESEARCH PRODUCT

Image processing applications in object detection and graph matching : from Matlab development to GPU framework

subject

description

Automatically finding correspondences between object features in images is of main interest for several applications, as object detection and tracking, flow velocity estimation, identification, registration, and many derived tasks. In this thesis, we address feature correspondence within the general framework of graph matching optimization and with the principal aim to contribute, at a final step, to the design of new and parallel algorithms and their implementation on GPU (Graphics Processing Unit) systems. Graph matching problems can have many declinations, depending on the assumptions of the application at hand. We observed a gap between applications based on local cost objective functions, and those applications with higher-order cost functions, that evaluate similarity between edges of the graphs, or hyperedges when considering hypergraphs. The former class provides convolution-based algorithms already having parallel GPU implementations. Whereas, the latter class puts the emphasis on geometric inter-feature relationships, transforming the correspondence problem to a purely geometric problem stated in a high dimensional space, generally modeled as an integer quadratic programming, for which we did not find GPU implementations available yet.Two complementary approaches were adopted in order to contribute to addressing higher-order geometric graph matching on GPU. Firstly, we study different declinations of feature correspondence problems by the use of the Matlab platform, in order to reuse and provide state-of-the-art solution methods, as well as experimental protocols and input data necessary for a GPU platform with evaluation and comparison tools against existing sequential algorithms, most of the time developed in Matlab framework. Then, the first part of this work concerns three contributions, respectively, to background and frame difference application, to feature extraction problem from images for local correspondences, and to the general graph matching problem, all based on the combination of methods derived from Matlab environment. Secondly, and based on the results of Matlab developments, we propose a new GPU framework written in CUDA C++ specifically dedicated to geometric graph matching but providing new parallel algorithms, with lower computational complexity, as the self-organizing map in the plane, derived parallel clustering algorithms, and distributed local search method. These parallel algorithms are then evaluated and compared to the state-of-the-art methods available for graph matching and following the same experimental protocol. This GPU platform constitutes our final and main proposal to contribute to bridging the gap between GPU development and higher-order graph matching.