Transcript Parallel Edge Detection - Guy Tel-Zur

Parallel Edge Detection
Daniel Dobkin
Asaf Nitzan
We’ll talk about…
 Introduction to Image Processing
 What are edges? Why do we need to find them?
How do we find them?
 Motivation to parallelize this process
 OpenMP implementation
What is an image?
 2-D / 3-D array of pixels
 Color channels
 RGB – 3 channels
 Grayscale – 1 channel
 1 byte per channel
values of 0-255
A closer look at pixels
R = 225
G = 157
B = 168
R = 201
G = 120
B = 137
Edges
 A sharp change in values of adjacent
pixels
 Motivation to find edges
 A very basic feature in image
processing
Finding Edges
 First, convert image from RGB to
Grayscale
 Convolve the image with a special 2-D
operator
 A greater change in intensity indicates a
more prominent edge
 Sobel operator:
Finding Edges - Example
217 221 44
213
13
2
24
3
2
 For Sobel x filter: -617
 For Sobel y filter: -669
 So now we have 2 numbers, now what?
 We calculate the magnitude and the orientation of the gradient:
𝑀=
𝐺𝑥 2 + 𝐺𝑦 2
𝐺𝑦
𝜃 = 𝑎𝑟𝑐𝑡𝑎𝑛
𝐺𝑥
Motivation to Parallelize
 Large amount of computations
 800 x 600 pixels = 480,000 pixels  5.5 million additions,
2 million multiplications
 Especially when it comes to real-time video…
 24 fps = 11.5 million pixels  132 million additions,
48 million multiplications…
openMP
 Processors access same shared memory
 Each processor performs the region of image assigned to
him
 Reduced communication - There is no need to broadcast
the pixels of the image to all other processors
openMP Implementation
 Multithreading
 Master thread forks a number of threads which execute code
in parallel
A
B
C
Original Image
D
fork
Master thread
Parallel task –
Sobel filtering
join
A
B
C
D
Master thread
Pseudocode
Load Image from Main memory
Allocate memory to new image
Set number of threads
#pragma omp parallel for \
shared(inputImage, outputImage, width, height)\
private(StartPixel, NumOfThreads, Rank , xPixel, yPixel)
for each Pixel in region
Convert RGB value to greyscale
Compute gradient using Sobel filter
Store result in filtered image
Join all threads
Store new image to disk
openMP Implementation
Filtered Image
Original Image
Processor 1
A
B
C
D
Processor 2
Processor 3
Processor 4
Sobel
A
Sobel
B
Sobel
C
Sobel
D
Main Memory
Speedup Graph
 Linear Speedup due to
low communication
cost
http://www.cs.rit.edu/~ptt/courses/4003-531/