For most of you, simply download ImageManipulation.zip and in Eclipse chose File → Import → Existing Project, selecting the .zip file.

For those who have an older version of Java, you can instead download multimedia.jar and in Eclipse make a new project in Eclipse right-click on the project name and select Build Path → Add External Archives, selecting the .jar file.

You’ll need any images you plan to use to be in your project folder, but not in your src/ folder.

Code Snippets

Load and Show

123

Picturep=newPicture("picture1.jpg");p.setTitle("Picture number 1");// optionalp.show();

Black and White

123456789101112

Picturep=newPicture("picture1.jpg");for(intx=0;x<p.getWidth();x+=1){for(inty=0;y<p.getHeight();y+=1){if(p.getPixel(x,y).getAverage()>130){// could use getRed or getGreen or getBlue insteadp.getPixel(x,y).setColor(newColor(255,255,255));}else{p.getPixel(x,y).setColor(newColor(0,0,0));}}}p.show();

The basic idea here to get the overall intensity of the color by adding up the red, green, and blue values and then taking the average. Remember that for a pixel to be gray (or black or white), all three RGB values have to be the same.

Resizing

With resizing, we will either be taking a fraction of the pixels (to make the image smaller) or duplicating pixels (to make the image bigger). We begin by creating a new image at the new size. Then, as we adjust the looping through our original image based on the scaling factor - we either skip pixels to make a smaller image or grab the same pixel multiple times to enlarge it.

Green Screen

Take two pictures, one in which the background is completely one solid color that you wouldn’t normally find in a “typical” picture. (This is one reason TV weathermen don’t wear green…) Then, as you loop through both pictures, pick the pixels from the background image if the matching pixel from the foreground image is green. Otherwise, take the pixel from the foreground image. Here are two images we can work with:

For the next few days, we are going to look at the algorithms behind some basic image manipulation.

First thing’s first: we need to know how to load in a picture into our Java programs. We will be using a class called Picture that was written at Georgia Tech specifically for use in CS 1 courses.

To get started, download this project and import it into Eclipse: ImageManipulation.zip

If the project doesn’t work for you, here’s a jar file that you can add to your build path (ask a TA for assistance) along with some pictures to work with:

This project has the Picture class preloaded in it, along with some very basic sample code with three images you can play with.

Drawing with Pixels

We started our programming journey by learning to draw pictures with the Turtle. But what exactly is a “picture” in the context of a computer program?

In effect, it’s a 2D array of pixels.

Well, what’s a pixel?

A pixel is the smallest display element of a picture. It could be dots on your monitor or TV, or how small an ink jet printer can put a dot on your paper (although we still typically call that “dots”). The pixel specifies what color (or components of colors) should be used to display that particular location in accordance with a color model. “Pixel” is short for “picture element.”

Printers (and paints and crayons…) use a subtractive color model. That is, as you add more color (paint), more light is absorbed. Thus, adding in all the colors makes the color black, as shown in the CMYK model below.

However, computer monitors (and all forms of light, like stage lighting) use an additive color model, like RGB.

So, as we add more and more colored lights, we get closer to white, not black!

In RGB, each of the three primary colors (Red, Green, and Blue) can have a value from 0 to 255. This allows for 16,777,216 colors (in theory)!

For example, (255,0,0) is red. But (128,0,0) is also red. It’s just not a “saturated” or bright as the first red. If all three values of , G, and B are the same, you get some shade of gray (or white or black).

Many pixels also have a fourth value - alpha. That tells the pixel how much to blend with any images behind the one that is currently “on top” and about to be drawn.

How many pixels?

It’s a big question when you buy a new camera. “How many megapixels is this thing?”

For reference:

An old, standard TV is about 852 x 480 = 400K pixels

A 1080p HD TV is 1920 x 1080 = 2M pixels

Many laptop monitors are 1680 x 1050 pixels

A “retina” MacBook has 2880 x 1800 pixels

An 8 megapixel camera has 3264 x 2448 pixels

So, why does resolution really matter if the monitors can’t display all that information?

Picture

The Picture class we will use has a Pixel class associated with it. Each Pixel has a Color associated with it, and we can get and set the RGB value of that Color in the Pixel.

Today, we’ll look at the Picture API and do some very basic grabbing of pixels and printing their RGB values to the screen.

Picturepict1=pictureList.get(0);pict1.show();// flip picture on y axisPictureflipped=newPicture(pict1.getWidth(),pict1.getHeight());for(intj=0;j<pict1.getHeight();j++){for(inti=0;i<pict1.getWidth();i++){Pixelsource=pict1.getPixel(i,j);Pixeldestination=flipped.getPixel(pict1.getWidth()-1-i,j);destination.setColor(source.getColor());}}flipped.show();// rotate picture 90 degrees clockwisePictureflipped2=newPicture(pict1.getHeight(),pict1.getWidth());for(intj=0;j<pict1.getHeight();j++){for(inti=0;i<pict1.getWidth();i++){Pixelsource=pict1.getPixel(i,j);Pixeldestination=flipped2.getPixel(pict1.getHeight()-1-j,pict1.getWidth()-1-i);destination.setColor(source.getColor());}}flipped2.show();// get negative of picturePicturenegative=newPicture(pict1.getWidth(),pict1.getHeight());for(intj=0;j<pict1.getHeight();j++){for(inti=0;i<pict1.getWidth();i++){Pixelsource=pict1.getPixel(i,j);Pixeldestination=negative.getPixel(i,j);Colorc=newColor(255-source.getRed(),255-source.getGreen(),255-source.getBlue());destination.setColor(c);}}negative.show();

We observed that for lists of just 13 elements, this could take several seconds to run
because it’s runtime scales with the factorial of the number of elements in the list.

Today we will continue our talk on Algorithms and complexity. Once we go over a few more search and sort algorithms we will then introduce image manipulation. For this you will need the Jar file below.

Okay, computer scientists! I’ve got two new algorithms for you! Let’s see if we can code them up and figure out what the complexity is!

I call them yolosearch and yolosort.

Here’s the pseudocode for yolosearch:

123

while(I haven't picked the number I'm looking for yet) {
pick a number at random from the list
}

We can even do advancedyolosearch!

12345678

make a copy of my list
while(I haven't picked the number I'm looking for yet) {
pick a number at random from the list
if it's not the number {
delete it from the list
}
}

There’s a slight problem with this algorithm. Every time we delete something from the list, all the indices change… so if we are looking for a particular index, this doesn’t work. If we are looking for a particular item from the list, it works fine.

What’s the complexity of these two searching algorithms? How do we know? Can we code them up?

Let’s take a look at yolosort now:

123

while(the list isn't in order) {
shuffle the list
}

How about this one? What’s the complexity? How can we code it up? How long will it take to run?

To design an algorithm, first make sure you can solve the problem yourself; then try to express your own actions in Java.

To search a list, we

Look at each element in turn, stopping when/if we find it.
In Java, this process becomes a simple for loop and is called Linear Search.
If the list has n elements, the loop might repeat as many as n times.

If we know the list is in some kind of order,
look at the middle element and then consider only half the list,
repeating until we find the element we want.
This is called Binary Search
If the list has n elements, we can cut it in half at most log_{2}(n) times.

To sort a list, we could

Compare neighboring elements, swapping them if they are out of order.
This is called Bubble Sort.
In general, this requires us to look across the list repeatedly;
roughly speaking, we have to walk the entire list (n elements)
n times, so the program might take as much as n^{2} times.

Find the smallest value and move it to a new list, the repeat until we can moved them all.
This is called Selection Sort.
Finding an element (linear search) takes n time, and we have n of them to find,
so we are still in n^{2} time overall, like bubble sort.

Split the list in half, sort each half, and then merge the two halves in order.
This is called Merge Sort.
Merging in takes time proportional to n,
and we can split at most log_{2}(n) times,
for a total of n log_{2}(n) time.

As a point of context,

There are around 8,000,000,000 people on Earth

Suppose we can handle a million people per second

Then we expect

linear search to take 8,000 seconds or about 2 hours

binary search to take 0.000033 seconds

bubble or selection sort to take over a trillion years, more than 70 times larger than the current estimated age of the universe

merge sort to take 264,000 seconds or about 3 days

Note that all of these are approximate, but they within an order of magnitude of the right answers

Today we’ll look at four particular algorithms that have been important in computing (well… at least in CS1) for a very long time.

Here are two searching and two sorting algorithms. We’ll do some in-class activities to show exactly how these algorithms work. We won’t really look at code yet - the purpose is to figure out just how “good” each of these algorithms is in various circumstances.