Lecture 38 (Tychonievich) - Images part 2

Lecture Date: Friday, April 17

Setup

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
1
2
3
Picture p = new Picture("picture1.jpg");
p.setTitle("Picture number 1"); // optional
p.show();
Black and White
1
2
3
4
5
6
7
8
9
10
11
12
Picture p = new Picture("picture1.jpg");
for(int x = 0; x < p.getWidth(); x += 1) {
  for(int y = 0; y < p.getHeight(); y += 1) {
      if (p.getPixel(x, y).getAverage() > 130) {
          // could use getRed or getGreen or getBlue instead
          p.getPixel(x, y).setColor(new Color(255, 255, 255));
      } else {
          p.getPixel(x, y).setColor(new Color(0, 0, 0));
      }
  }
}
p.show();
Greyscale
1
2
3
4
5
6
7
8
Picture p = new Picture("picture1.jpg");
for(int x = 0; x < p.getWidth(); x += 1) {
  for(int y = 0; y < p.getHeight(); y += 1) {
      Pixel px = p.getPixel(x, y);
      px.setRed(px.getAverage());
  }
}
p.show();

From Lecture:

Code:


Lecture 38 (Sherriff) - Images 2

Lecture Date: Friday, April 17

More image manipulation algorithms today!

Our main algorithms for the day will be:

  • Grayscale
  • Resizing
  • Green Screen

Grayscale

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:

Today’s Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public static Picture greenscreen(Picture fore, Picture back) {
  Picture greenscreen = new Picture(fore.getWidth(), fore.getHeight());
  for (int row = 0; row < fore.getWidth(); row++) {
      for (int col = 0; col < fore.getHeight(); col++) {
          Pixel fore_p = fore.getPixel(row, col);
          Pixel back_p = back.getPixel(row, col);
          Pixel green_p = greenscreen.getPixel(row, col);
          
          if(fore_p.getGreen() > fore_p.getBlue() + fore_p.getRed() + 10) {
              green_p.setColor(back_p.getColor());
          } else {
              
              green_p.setColor(fore_p.getColor());
          }
      }
  }
  
  return greenscreen;
}

public static Picture grayscale(Picture pict) {
  Picture gray = new Picture(pict.getWidth(), pict.getHeight());

  for (int row = 0; row < pict.getWidth(); row++) {
      for (int col = 0; col < pict.getHeight(); col++) {
          Pixel p = pict.getPixel(row, col);
          Pixel dest = gray.getPixel(row, col);
          int intensity = p.getRed() + p.getGreen() + p.getBlue();
          dest.setRed(intensity / 3);
          dest.setGreen(intensity / 3);
          dest.setBlue(intensity / 3);
      }
  }

  return gray;

}

public static Picture scale(Picture pic, double scale) {
  int oldWidth = pic.getWidth();
  int oldHeight = pic.getHeight();
  
  Picture newImg = new Picture((int)(oldWidth * scale), (int)(oldHeight * scale));
  
  for(int row = 0; row < oldHeight*scale; row++) {
      for(int col = 0; col < oldWidth*scale; col++) {
          Pixel origPix = pic.getPixel((int)(col/scale), (int)(row/scale));
          newImg.getPixel(col, row).setColor(origPix.getColor());
      }
  }
  
  return newImg;
}



Lecture 37 (Sherriff & Tychonievich) - Images Intro

Lecture Date: Wednesday, April 15

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.

CMYK

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

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.

Example Code

Here are some example algorithms:

Example Image Algorithms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Picture pict1 = pictureList.get(0);
pict1.show();

// flip picture on y axis
Picture flipped = new Picture(pict1.getWidth(), pict1.getHeight());
for (int j = 0; j < pict1.getHeight(); j++) {
  for (int i = 0; i < pict1.getWidth(); i++) {
      Pixel source = pict1.getPixel(i, j);
      Pixel destination = flipped.getPixel(pict1.getWidth() - 1 - i,
              j);
      destination.setColor(source.getColor());
  }
}
flipped.show();

// rotate picture 90 degrees clockwise
Picture flipped2 = new Picture(pict1.getHeight(), pict1.getWidth());
for (int j = 0; j < pict1.getHeight(); j++) {
  for (int i = 0; i < pict1.getWidth(); i++) {
      Pixel source = pict1.getPixel(i, j);
      Pixel destination = flipped2.getPixel(
              pict1.getHeight() - 1 - j, pict1.getWidth() - 1 - i);
      destination.setColor(source.getColor());
  }
}
flipped2.show();

// get negative of picture
Picture negative = new Picture(pict1.getWidth(), pict1.getHeight());
for (int j = 0; j < pict1.getHeight(); j++) {
  for (int i = 0; i < pict1.getWidth(); i++) {
      Pixel source = pict1.getPixel(i, j);
      Pixel destination = negative.getPixel(i,j);
      Color c = new Color(255-source.getRed(), 255-source.getGreen(), 255-source.getBlue());
      destination.setColor(c);
  }
}
negative.show();

Sherriff:

Tychonievich:


Lecture 36 (Tychonievich) - Search and Sort

Lecture Date: Monday, April 13

We listed many kinds of sorting algorithms and implemeted a few:

Bogo Sort
1
2
3
4
5
public static void bogoSort(int[] list) {
  while (isOutOfOrder(list)) {
      shuffle(list);
  }
}

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.

We also coded mergeSort, but it was big and ugly.

From Lecture



Lecutre 36 (Sherriff) - Algorithm Design 2

Lecture Date: Monday, April 13

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:

1
2
3
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!

1
2
3
4
5
6
7
8
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:

1
2
3
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?


Lecture 35 (Tychonievich) - Search and Sort

Lecture Date: Friday, April 10

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

  1. 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.

  2. 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 log2(n) times.

To sort a list, we could

  1. 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 n2 times.

  2. 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 n2 time overall, like bubble sort.

  3. 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 log2(n) times, for a total of n log2(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

From Lecture


Lecture 35 (Sherriff) - Algorithm Design

Lecture Date: Friday, April 10

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

algorithms

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.


Lecture 22 (Edwards) - Algorithms

Lecture Date: Wednesday, April 8

Today we will continue looking at what makes a good program/algorithm, mainly looking at 3 things, how fast is it, is it easy to read, is it correct.

We will do this by considering robots and rooms, see code posted below.

After this we will talk about some algorithms that everyone who has taken a CS1 course should have seen.

illustration of type by location or by label

When is one better than the other? How do we even compare algorithms?

Code: