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

Content Provider	IEEE Xplore Digital Library
Author	Fijany, A. Diotalevi, F.
Copyright Year	2012
Description	Author affiliation: Italian Institute of Technology, Via Morego 30, 16163 Genova, Italy (Fijany, A.; Diotalevi, F.)
Abstract	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.
Starting Page	1
Ending Page	14
File Size	699178
Page Count	14
File Format	PDF
ISBN	9781457705564
ISSN	1095323X
e-ISBN	9781457705571
DOI	10.1109/AERO.2012.6187227
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-03-03
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computational modeling Data models Tiles Computer architecture Engines Estimation Computational efficiency
Content Type	Text
Resource Type	Article
Subject	Aerospace Engineering Space and Planetary Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in