The maximum subarray problem is used to identify the subarray of a two-dimensional array, where the sum of elements is maximized. In terms of image processing, the solution has been used to find the brightest region within an image. Two parallel algorithms of the maximum subarray problem solve this problem in O(n) and O(log n) time. A field programmable gate array implementation has verified theoretical maximum performance; however, extensive customization is required, restricting general application. A more convenient platform for this work is a graphics processor unit since it offers a flexible trade-off between hardware customization and performance. Implementation of the maximum subarray algorithm on a graphics processor unit is discussed in this article for rectangular solutions and convex extensions are explored.
KEYWORDS: Image processing, Field programmable gate arrays, Radio optics, Very large scale integration, Algorithm development, Clocks, Astronomical imaging, Radio astronomy, Radio telescopes, Wavefront sensors
The maximum sub-array algorithm has been implemented within a field programmable gate array as an efficient centroiding method for wavefront slope estimation. However, a convenient platform for this work is a graphics processor unit (GPU). Translation of the maximum subarray algorithm to a GPU has been performed and shows significant performance gains compared to a single-core CPU. Recently, this algorithm has been applied to radio telescope images acquired for the Australian square kilometer array pathfinder project. This paper provides an overview of the maximum subarray algorithm and shows how this can be utilized for optical and radio telescope applications.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.