Type of Document Master's Thesis Author Vinukonda, Phaneendra URN etd-04272011-105721 Title A Study of the Scale-Invariant Feature Transform on a Parallel Pipeline Degree Master of Science in Electrical Engineering (M.S.E.E.) Department Electrical & Computer Engineering Advisory Committee

Advisor Name Title Vaidyanathan, Ramachandran Committee Chair Gunturk, Bahadir K. Committee Member Rai, Suresh Committee Member Keywords

- SIFT
- Pipeline Model
Date of Defense 2011-04-12 Availability unrestricted AbstractUntitled Page In this thesis we study the running of the Scale Invariant Feature Transform (SIFT) algorithm on a pipelined computational platform. The SIFT algorithm is one of the most widely used methods for image feature extraction.

We develop a tile based template for running SIFT that facilitates the analysis while abstracting away lower-level details. We formalize the computational pipeline and the time to execute any algorithm on it based on the relative times taken by the pipeline stages. In the context of the SIFT algorithm, this reduces the time to that of running the entire image through a bottlenecked stage and the time to run either the first or last tile through the remaining stages. Through an experimental study of the SIFT algorithm on a broad collection of test images, we determined image feature fraction values, that relate the sizes of the image extracts as it the computation proceeds through the stages of the SIFT algorithm.

We show that for a single chip uniprocessor pipeline, the computational stage is the bottleneck. Specifically we show that for an N x N image with n x n tiles the overall time complexity is

here x is the neigborhood of the tile, p

θ (

(n+x) ^{2 }p _{i }Г _{0}+αβN^{2}x^{2}Г_{1}+

(αβ+γ)n ^{2}logxP _{0}Г _{2}) ; _{i }, p_{o}are the number of input, output pins of the chip, α,β,γ are the feature fractions, and Г_{0}, Г_{1}, Г_{2}are the input, compute, output clocks. The three terms in the expression represents the time complexities of input, compute and output stages. The input and output stages can be slowed down substantially without appreciate degradation of the overall performance. This slowdown can be traded off for lower power and higher signal quantity.For multicore chips, we show that for an N x N image on a P-core chip, the overall time complexity to process the image is

in addition to the quantities described earlier w is the window size used for the Gaussian blurring. Overall we establish that without improvements in the input bandwidth, the power of multicore processing cannot be used efficiently for SIFT.

θ (

N ^{2 }p _{i }Г _{0}+

(n ^{2}w^{2}+ αβn^{2}x^{2})P Г _{1}+

(αβ+γ)n ^{2}logxP _{0}Г _{2}) ; Files

Filename Size Approximate Download Time (Hours:Minutes:Seconds)

28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access Vinukonda_Phaneendra_Thesis.pdf1.08 Mb 00:05:01 00:02:34 00:02:15 00:01:07 00:00:05

Browse All Available ETDs by
( Author |
Department )

If you have questions or technical problems, please Contact LSU-ETD Support.