Concurrent Image Convolution1. Task Description2. Pseudo-code3. Code Implementation in java4. Resulti. Intput Imageii. Output Imageiii. Performance Analysis
Concurrent Image Convolution
- Various image effects can be created by performing a convolution.
-
Convolution is a mathematical operation which describes a rule of how to combine two functions or pieces of information to form a third function. The feature map (or input data) and the kernel are combined to form a transformed feature map. The convolution algorithm is often interpreted as a filter, where the kernel filters the feature map for certain information. A kernel, for example, might filter for edges and discard other information.
-
- Figure 1: Convolving an image with an edge detector kernel.
1. Task Description
- Given an input image, an output image is constructed by computing each output pixel value as a weighted summation of the corresponding input pixel and the pixels forming its immediate neighbourhood in the input image.
- Use multithreading to speed up the execution of convolution. Provide a graph of the relative speedup of multithreaded versions over the single-threaded version for 1–8 threads.
2. Pseudo-code
If weights are stored in an array (a kernel), the following pseudo-code summarizes a naive, but simple approach:
xxxxxxxxxx
for each row:
for each pixel in the row
set r, g, b accumulators to zero
// Logically center the kernel on the given pixel.
// A sum is computed by adding the product of each kernel
// weight and its corresponding input pixel value (per channel).
// This sum is the output pixel value (per channel).
for each kernel row:
for each value in the kernel row:
if the input pixel offset by the kernel displacement is
within the image dimensional bounds, then:
for each channel r, g, and b separately:
multiply the pixel colour value by the corresponding
kernel value
add result to accumulator
endif
constrain r, g, and b values to be within 0 to 255
set output image pixel to final r, g, b value (with alpha of 0xff)
3. Code Implementation in java
x
import java.awt.image.*;
import java.io.*;
import javax.imageio.*;
import java.awt.Color;
public class imageConv
{
// Number of threads to use
public static int threads = 1;
public static int width;
public static int height;
// Time data field
public static long timeNow;
public static long timeEnd;
public static long exe_time;
public static long[] allTimes = new long[6];
// Basic kernel
public static int[][] kernel = {
{-1,-1,-1},
{-1,8,-1},
{-1,-1,-1},
};
public static BufferedImage img;
public static BufferedImage outputimage;
public static void main(String[] args)
{
try
{
if (args.length > 0)
threads = Integer.parseInt(args[0]);
// read in an image from a file
img = ImageIO.read(new File("image.jpg"));
// store the dimensions locally for convenience
width = img.getWidth();
height = img.getHeight();
// create an output image
outputimage = new BufferedImage(width,height,BufferedImage.TYPE_INT_ARGB);
// ------------------------------------
// The easiest mechanisms for getting and setting pixels are the
// BufferedImage.setRGB(x,y,value) and getRGB(x,y) functions.
// Note that setRGB is synchronized (on the BufferedImage object).
// Consult the javadocs for other methods.
// The getRGB/setRGB functions return/expect the pixel value in ARGB format, one byte per channel. For example,
// int p = img.getRGB(x,y);
// With the 32-bit pixel value you can extract individual colour channels by shifting and masking:
// int red = ((p>>16)&0xff);
// int green = ((p>>8)&0xff);
// int blue = (p&0xff);
// If you want the alpha channel value it's stored in the uppermost 8 bits of the 32-bit pixel value
// int alpha = ((p>>24)&0xff);
// Note that an alpha of 0 is transparent, and an alpha of 0xff is fully opaque.
// ------------------------------------
// add timing
for (int num = 0; num < 6; num++)
{
// Create N threads using a loop
Thread[] mThreads = new Thread[threads];
// Distribute portions of work to n threads, integer division throw away remainder by default
int thread_work = (height/threads);
int last_thread_extra = (height%threads);
// intialize start and end position
int start = 0;
int end = thread_work;
timeNow = System.currentTimeMillis();
for (int i = 0; i < threads; i++)
{
// special case: when it is the last thread
if (i == threads - 1 )
{
end = end + last_thread_extra;
mThreads[i] = new Thread(new RunnableImage(start, end));
mThreads[i].start();
break;
}
// all threads exclude the last
mThreads[i] = new Thread(new RunnableImage(start,end));
mThreads[i].start();
// increment start and end position for next thread
start = start + thread_work;
end = end + thread_work;
}
// Wait for each thread to finish
try
{
// System.out.println("Waiting for threads to finish.");
for (int j = 0; j < threads; j++)
{
mThreads[j].join();
}
}
catch (InterruptedException e)
{
System.out.println("Main thread Interrupted!");
}
// all threads end, get end time
timeEnd = System.currentTimeMillis();
exe_time = timeEnd - timeNow;
System.out.println(exe_time);
allTimes[num] = exe_time;
}
// Discard first execution time and get average
long AccumTime = 0;
for (int i = 0; i < allTimes.length; i++)
{
if (i == 0)
continue;
AccumTime += allTimes[i];
}
AccumTime /= 5;
System.out.println("Number of threads: " + threads + "\n" + "Average time is: " + AccumTime);
// Write out the image
File outputfile = new File("output_image.png");
ImageIO.write(outputimage, "png", outputfile);
}
catch (Exception e)
{
System.out.println("ERROR " + e);
e.printStackTrace();
}
}
}
x
class RunnableImage implements Runnable
{
private int start;
private int end;
// Constructor
public RunnableImage(int start, int end)
{
this.start = start;
this.end = end;
}
// synchronize method when set RGB
synchronized void set(int j, int i, int rgb)
{
q1.outputimage.setRGB(j, i, rgb);
}
public void run()
{
// for each row
for (int i = start; i < end; i++)
{
// for each pixel in row
for (int j = 0; j < q1.width; j++)
{
// set R, G, B accum, accumulators to zero
int accumR = 0, accumG = 0, accumB = 0;
// for each kernel row
for (int k_row = 0; k_row < q1.kernel.length; k_row++)
{
// for each value in kernel row
// each value's location is (k_row,k_col)
for (int k_col = 0; k_col < q1.kernel[0].length; k_col++)
{
// check bounds
if ( (0 <= (j-1)) && ((j+1) < q1.width) && (0 <= (i-1)) && ((i+1) < q1.height))
{
int p = q1.img.getRGB(j + k_col - 1, i + k_row - 1);
int red = ((p>>16) & 0xff);
int green = ((p>>8) & 0xff);
int blue = (p & 0xff);
accumR += (red * q1.kernel[k_row][k_col]);
accumG += (green * q1.kernel[k_row][k_col]);
accumB += (blue * q1.kernel[k_row][k_col]);
}
}
}
// constrain r, g, and b values to be within 0..255
if (accumR < 0) accumR = 0;
if (accumG < 0) accumG = 0;
if (accumB < 0) accumB = 0;
if (accumR > 255) accumR = 255;
if (accumG > 255) accumG = 255;
if (accumB > 255) accumB = 255;
// combine r,g,b together
Color c = new Color(accumR, accumG, accumB);
int rgb = c.getRGB();
set(j, i, rgb);
}
}
}
}
4. Result
i. Intput Image
ii. Output Image
iii. Performance Analysis
- From the test result, it can be observed that one thread takes a longer time than the others. As the number of threads increases to 2, the average execution has an obvious decline. For number of threads from 2 to 8, their performance is almost the same. Since a program is divided into sequential part and parallel part. The speedup is limited. In this test, the best performance is 2247.2 milliseconds while 5 Threads are used.