GPU-accelerated PSF Estimation with a
Cooperative Particle Swarm Optimization
Kiepenheuer Institute for Solar Physics
Freiburg, 04.06.2013
Peter F. Perroni¹, Daniel Weingaertner¹, Torsten Waldmann²
1) Department of Informatics, UFPR, Curitiba, Brazil
2) Kiepenheuer Institute for Solar Physics, Freiburg, Germany
Vision, Robotics and Images Research Group, UFPR
1
Brasil
Vision, Robotics and Images Research Group, UFPR
2
Paraná
Vision, Robotics and Images Research Group, UFPR
3
Curitiba
Vision, Robotics and Images Research Group, UFPR
4
Curitiba
Vision, Robotics and Images Research Group, UFPR
5
Universidade Federal do Paraná
Vision, Robotics and Images Research Group, UFPR
6
Informatics Department
31 Professors
Undergraduate (Bachelor, 8 semesters)
Computer Science: 80 students/year
Biomedical informatics: 30 students/year
Graduate (MSc & PhD)
Algorithms, Image Processing, Computer
Vision, Artificial Intelligence
Databases, Computer-Human Interface
Computer Networks, Embedded Systems
Vision, Robotics and Images Research Group, UFPR
7
Summary
The Problem
Existing solution
Proposed solution
Particle Swarm Optimization (PSO)
Cooperative PSO
OpenCL
Implementation
Results
Discussion
Vision, Robotics and Images Research Group, UFPR
8
The Problem
Images from ground-based telescopes suffer
from distortions caused by the atmosphere
Pressure, temperature variations
Diffraction changes
Noise
Point Spread Function (PSF)
Describes the impulse response
function of an imaging system to an
input point, i.e., describes how an
“ideal” pixel of the object is reproduced
in the image.
Vision, Robotics and Images Research Group, UFPR
9
Phase & Zernike Polynomials
Vision, Robotics and Images Research Group, UFPR
10
PSF Estimation Method
Random
Phase
Generate n Random
Numbers (ϒ)
Estimated
PSF
Object
Convolve
Long exposure
Image
Estimated
Image
Repeat Until:
A number of iterations Or
A satisfactory result
UFPR
- MScand
in Images
Computer
Vision,
Robotics
Research Group, UFPR
Cost
Image
11
Existing Solution
Simulated Annealing (SA)
Easy implementation
Based on slow cooling of a material
Evaluates one neighbor solution at a time
Slow convergence in high dimensions
First steps
Understanding existing code (Waldmann,
Lühe; 2010)
Refactoring existing code
Re-implement for GPGPU using CUDA
Vision, Robotics and Images Research Group, UFPR
12
Refactored & Re-implemented
Simulated Annealing
Vision, Robotics and Images Research Group, UFPR
13
Convergence of SA
Vision, Robotics and Images Research Group, UFPR
14
Particle Swarm Optimization
Based on the dynamics of a bird flock
Find good “food” regions in search space
Does not guaranty optimal solution
Stochastic optimization
Population (or Swarm) composed of
particles, each of which is a solution
Vision, Robotics and Images Research Group, UFPR
15
Particle Swarm Optimization
Particle moves towards the best personal
solution (pBest) and global solution (gBest)
Weights guide this drive towards the best
Collaborative behavior enforced
Vision, Robotics and Images Research Group, UFPR
16
Particle Swarm Optimization
Vision, Robotics and Images Research Group, UFPR
17
Cooperative PSO
Cooperative Particle Swarm Optimization
Divide the problem in K sub-problems (subswarms)
Each sub-swarm has only a partial solution
Fitness evaluation of a particle is done by
joining its values with other swarms gBest's
A swarm gBest refers only to its part of the
solution
Global solution is obtained by joining the
gBest from all sub-swarms
Vision, Robotics and Images Research Group, UFPR
18
Cooperative PSO
Vision, Robotics and Images Research Group, UFPR
19
Cooperative PSO
Context function (group the dimension)
Check the fitness of the particle's position
against fitness of the particle's pBest
Check the fitness of the particle's pBest
against fitness of the swarm's gBest
Vision, Robotics and Images Research Group, UFPR
20
OpenCL
Open Computing Language (OpenCL)
Heterogeneous GPGPU computing
Hardware independent
One program can use all OpenCL devices
Code reusability
Single Instruction Multiple Data Paradigm
Private (fast) and shared (slower) memory
Vision, Robotics and Images Research Group, UFPR
21
OpenCL
Vision, Robotics and Images Research Group, UFPR
22
CPSO with OpenCL
Vision, Robotics and Images Research Group, UFPR
23
CPSO with OpenCL
Vision, Robotics and Images Research Group, UFPR
24
CPSO with OpenCL
Vision, Robotics and Images Research Group, UFPR
25
PSF with OpenCL
Vision, Robotics and Images Research Group, UFPR
26
CPSO Calibration
Several parameters must be adjusted
What is the best number of particles and
swarms?
What is the smallest number of cycles
required to achieve good results?
Otherwise defined values:
w; c1; c2; reset;
range=[-2,+2]
nZernikes=50
Vision, Robotics and Images Research Group, UFPR
27
CPSO Calibration
Vision, Robotics and Images Research Group, UFPR
28
CPSO Calibration
Worst Result
Vision, Robotics and Images Research Group, UFPR
29
CPSO Calibration
Vision, Robotics and Images Research Group, UFPR
30
Experimental Results
Hardware
Intel Core i7-975 CPU
6 GiB RAM
Nvidia Tesla C2050 GPU
Debian GNU-Linux
Images
One image of the Sun 64x64 pixels
Randomly generated PSF
Corrupted artificial image
3950 seconds for 100 images
Vision, Robotics and Images Research Group, UFPR
31
Experimental Results
Vision, Robotics and Images Research Group, UFPR
32
Experimental Results
Vision, Robotics and Images Research Group, UFPR
33
Experimental Results
Vision, Robotics and Images Research Group, UFPR
34
Experimental Results
Vision, Robotics and Images Research Group, UFPR
35
Experimental Results
Vision, Robotics and Images Research Group, UFPR
36
Number of Zernikes
Increase in the number of Zernikes, keeping
all remaining configurations
Vision, Robotics and Images Research Group, UFPR
37
Increasing Image Size
Compare convergence of similar images but
with different size (128x128 pixels)
All configurations are kept the same
High number of cycles (2 million)
Convergence curves:
Similar curves mean nSwarms and nParticles
can be the same
Different curves mean a new calibration is
needed
How fast convergence occurs: adjust nCycles
Vision, Robotics and Images Research Group, UFPR
38
Convergence Curves
Vision, Robotics and Images Research Group, UFPR
39
Conclusions
Problem well suited for CPSO
Problem well suited for GPGPU
Calibration can be reused for similar images
Performance little affected by the number of
Zernikes used
Vision, Robotics and Images Research Group, UFPR
40
Contact
Master Thesis of Peter F. Perroni
Available at:
web.inf.ufpr.br/vri/alumni/peter-frank-perroni-msc-2013
Contact:
[email protected]
http://web.inf.ufpr.br/danielw
Vision, Robotics and Images Research Group, UFPR
41