In this paper, we present a novel and fast algorithm for highly parallel implementation of the RANSAC on a many-core MIMD architecture, the Tilera. RANSAC is widely used in image processing applications for homography model estimation. It also represents one of the most computation intensive image processing tasks since it requires evaluation of a large number of models from a given data set. Therefore, increasing the efficiency in its computation by exploiting a massive degree of parallelism is the key enabling factor for many of its applications. Emerging highly parallel architectures such as Tilera provide such an opportunity of exploiting parallelism in many computations. In addition to its low power consumption and excellent GOPs per Watt performance, radiation-hard version of Tilera has also been developed which makes it one of the best candidates for future aerospace applications. In this paper, we first present a novel variant of the RANSAC by incorporating the concept of backtracking. We then present this variant as a cooperative search algorithm with excellent features for highly parallel implementation. In fact, our parallel implementation results in an asynchronous algorithm with a very limited communication requirement. Any processor performs a global broadcasting if and when it finds a partial solution better than previous one. We present our results for an extensive set of data with varying degree of outliers. Our practical results clearly demonstrate that excellent speedup in the computation is achieved by using 57 cores of the Tilera. In fact, for certain cases, our Cooperative Search Algorithms even achieve super-linear speedup, i.e., a speedup greater than 57. We discuss that such a result could have been indeed expected and can be used for other applications.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A cooperative search algorithm for highly parallel implementation of RANSAC for model estimation on Tilera MIMD architecture


    Beteiligte:

    Erschienen in:

    Erscheinungsdatum :

    01.03.2012


    Format / Umfang :

    699178 byte





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Highly parallel and fast implementation of stereo vision algorithms on MIMD many-core Tilera architecture

    Safari, Saeed / Fijany, Amir / Diotalevi, Francesco et al. | IEEE | 2012


    A parallel rendering algorithm for MIMD architectures

    Crockett, Thomas W. / Orloff, Tobias | TIBKAT | 1991


    Very low power parallel implementation of stereo vision algorithm on a solar cell powered MIMD many core architecture

    Diotalevi, Francesco / Fijany, Amir / Montvelishsky, Michael et al. | IEEE | 2011


    An implementation of the multifrontal solution algorithm on MIMD computers

    CALALO, RUEL / NOUR-OMID, BAHRAM / WRIGHT, MARY | AIAA | 1992


    A Fast Algorithm for Parallel Computation of Multibody Dynamics on MIMD Parallel Architectures

    Fijany, A. / Kwan, G. / Bagherzadeh, N. et al. | British Library Conference Proceedings | 1993