Picture Lab – Activity 6
Mirroring pictures

Exercises:
1. Write the method mirrorVerticalRightToLeft that mirrors a picture around a mirror placed vertically from right to left. Hint: you can copy the body of mirrorVertical and only change one line in the body of the method to accomplish this. Write a class (static) test method called testMirrorVerticalRightToLeft in PictureTester to test this new method and call it in the main method.

1. Write the method mirrorHorizontal that mirrors a picture around a mirror placed horizontally at the middle of the height of the picture. Mirror from top to bottom as shown in the pictures below (Figure 8). Write a class (static) test method in PictureTester to test this new method and call it in the main method.

2. Write the method mirrorHorizontalBotToTop that mirrors the picture around a mirror placed horizontally from bottom to top. Hint: you can copy the body of mirrorHorizontal and only change one line to accomplish this. Write a class (static) test method in PictureTester to test this new method and call it in the main method.

3. Challenge — Work in groups to figure out the algorithm for the method mirrorDiagonal that mirrors just a square part of the picture from bottom left to top right around a mirror placed on the diagonal line (the diagonal line is the one where the row index equals the column index). This will copy the triangular area to the left and below the diagonal line as shown below. This is like folding a square piece of paper from the bottom left to the top right, painting just the bottom left triangle and then (while the paint is still wet) folding the paper up to the top right again. The paint would be copied from the bottom left to the top right as shown in the pictures below (Figure 9). Write a class (static) test method in PictureTester to test this new method and call it in the main method.
   

April 27th, 2015

Picture Lab
A9: Simple edge detection

Detecting edges is a common image processing problem. For example, digital cameras often feature face detection. Some robotic competitions require the robots to find a ball using a digital camera, so the robot needs to be able to “see” a ball.

One way to look for an edge in a picture is to compare the color at the current pixel with the pixel in the next column to the right. If the colors differ by more than some specified amount, this indicates that an edge has been detected and the current pixel color should be set to black. Otherwise, the current pixel is not part of an edge and its color should be set to white (Figure 12). How do you calculate the difference between two colors?

public void edgeDetection(int edgeDist)
  { 
    Pixel leftPixel = null;
    Pixel rightPixel = null;
    Pixel[][] pixels = this.getPixels2D();
    Color rightColor = null;
    for (int row = 0; row < pixels.length; row++)
    {
      for (int col = 0; col < pixels[0].length-1; col++)
       {
         leftPixel = pixels[row][col];
         rightPixel = pixels[row][col+1];
         rightColor = rightPixel.getColor();
         if (leftPixel.colorDistance(rightColor) > edgeDist)
            leftPixel.setColor(Color.BLACK);
         else
            leftPixel.setColor(Color.WHITE);
       }
     }
   }

Classwork:
Exercises
1. Notice that the current edge detection method works best when there are big color changes from left to right but not when the changes are from top to bottom. Add another loop that compares the current pixel with the one below and sets the current pixel color to black as well when the color distance is greater than the specified edge distance.

2. Work in groups to come up with another algorithm for edge detection.

How image processing is related to new scientific breakthroughs
Many of today’s important scientific breakthroughs are being made by large, interdisciplinary collaborations of scientists working in geographically widely distributed locations, producing, collecting, and analyzing vast and complex datasets.

One of the computer scientists who works on a large interdisciplinary scientific team is Dr. Cecilia Aragon. She is an associate professor in the Department of Human Centered Design & Engineering and the eScience Institute at the University of Washington, where she directs the Scientific Collaboration and Creativity Lab. Previously, she was a computer scientist in the Computational Research Division at Lawrence Berkeley National Laboratory for six years, after earning her Ph.D. in Computer Science from UC Berkeley in 2004. She earned her B.S. in mathematics from the California Institute of Technology.

Her current research focuses on human-computer interaction (HCI) and computer-supported cooperative work (CSCW) in scientific collaborations, distributed creativity, information visualization, and the visual understanding of very large data sets. She is interested in how social media and new methods of computer-mediated communication are changing scientific practice. She has developed novel visual interfaces for collaborative exploration of very large scientific data sets, and has authored or co-authored many papers in the areas of computer-supported cooperative work, human-computer interaction, visualization, visual analytics, image processing, machine learning, cyberinfrastructure, and astrophysics.

In 2008, she received the Presidential Early Career Award for Scientists and Engineers (PECASE) for her work in collaborative data-intensive science. Her research has been recognized with four Best Paper awards since 2004, and she was named one of the Top 25 Women of 2009 by Hispanic Business Magazine. She was the architect of the Sunfall data visualization and workflow management system for the Nearby Supernova Factory, which helped advance the study of supernovae in order to reduce the statistical uncertainties on key cosmological parameters that categorize dark energy, one of the grand challenges in physics today.

Cecilia Aragon is also one of the most skilled aerobatic pilots flying today. A two-time member of the U.S. Aerobatic Team, she was a medalist at the 1993 U.S. National Championships and the 1994 World Aerobatic Championships, and was the California State Aerobatic Champion.

THE END

April 23rd, 2015

Picture Lab – Activity 7
Mirroring pictures

Classwork:
Activity 7:
A7: Mirroring part of a picture

public void mirrorTemple()
  { 
    int mirrorPoint = 276;
    Pixel leftPixel = null;
    Pixel rightPixel = null;
    int count = 0;
    Pixel[][] pixels = this.getPixels2D();

    // loop through the rows
    for (int row = 27; row < 97; row++)
    { 
      // loop from 13 to just before the mirror point
      for (int col = 13; col < mirrorPoint; col++)
      {
        leftPixel = pixels[row][col];
        rightPixel = pixels[row][mirrorPoint - col + mirrorPoint];
        rightPixel.setColor(leftPixel.getColor());
      }
    }
   }

Questions
1. How many times would the body of this nested for loop execute?

for (int row = 7; row < 17; row++)
         for (int col = 6; col < 15; col++)

2. How many times would the body of this nested for loop execute?

       for (int row = 5; row <= 11; row++)
         for (int col = 3; col <= 18; col++)

Exercises
1. Check the calculation of the number of times the body of the nested loop executes by adding an integer count variable to the mirrorTemple method that starts out at 0 and increments inside the body of the loop. Print the value of count after the nested loop ends.

2. Write the method mirrorArms to mirror the arms on the snowman (“snowman.jpg”) to make a snowman with 4 arms. Write a class (static) test method in PictureTester to test this new method and call it in the main method.

3. Write the method mirrorGull to mirror the seagull (“seagull.jpg”) to the right so that there are two seagulls on the beach near each other. Write a class (static) test method in PictureTester to test this new method and call it in the main method.

Homework:
A8: Creating a collage

public void copy(Picture fromPic, int startRow, int startCol)
{
  Pixel fromPixel = null;
  Pixel toPixel = null;
  Pixel[][] toPixels = this.getPixels2D();
  Pixel[][] fromPixels = fromPic.getPixels2D();
for (int fromRow = 0, toRow = startRow; fromRow < fromPixels.length && toRow < toPixels.length; fromRow++, toRow++)
{
  for (int fromCol = 0, toCol = startCol; fromCol < fromPixels[0].length && toCol < toPixels[0].length; fromCol++, toCol++)
   {
      fromPixel = fromPixels[fromRow][fromCol];
      toPixel = toPixels[toRow][toCol];
      toPixel.setColor(fromPixel.getColor());
   } 
  } 
}

public void createCollage()
  { 
    Picture flower1 = new Picture("flower1.jpg");
    Picture flower2 = new Picture("flower2.jpg");
    this.copy(flower1,0,0);
    this.copy(flower2,100,0);
    this.copy(flower1,200,0);
    Picture flowerNoBlue = new Picture(flower2);
    flowerNoBlue.zeroBlue();
    this.copy(flowerNoBlue,300,0);
    this.copy(flower1,400,0);
    this.copy(flower2,500,0);
    this.mirrorVertical();
    this.write("collage.jpg");
  }

Exercises
1. Create a second copy method that adds parameters to allow you to copy just part of the fromPic. You will need to add parameters that specify the start row, end row, start column, and end column to copy from. Write a class (static) test method in PictureTester to test this new method and call it in the main method.

2. Create a myCollage method that has at least three pictures (can be the same picture) copied three times with three different picture manipulations and at least one mirroring. Write a class (static) test method in PictureTester to test this new method and call it in the main method.

April 19th, 2016

Picture Lab – Activity 5

Classwork:
1. Open Picture.java and look for the method getPixels2D. Is it there?
2. Open SimplePicture.java and look for the method getPixels2D. Is it there?
3. Does the following code compile?
DigitalPicture p = new DigitalPicture();
4. Assuming that a no-argument constructor exists for SimplePicture, would the following
code compile?
DigitalPicture p = new SimplePicture();
5. Assuming that a no-argument constructor exists for Picture, does the following code
compile?
DigitalPicture p = new Picture();
6. Assuming that a no-argument constructor exists for Picture, does the following code
compile?
SimplePicture p = new Picture();
7. Assuming that a no-argument constructor exists for SimplePicture, does the following
code compile?
Picture p = new SimplePicture();

More Questions:
List nameList = new ArrayList();
Why wouldn’t you just declare nameList to be of the type ArrayList?

What do you think you will see if you modify the beach picture in the images folder to set all the blue values to zero?

Do you think you will still see a beach?

Exercises
1. Open PictureTester.java and run its main method. You should get the same results as running the main method in the Picture class. The PictureTester class contains class (static) methods for testing the methods that are in the Picture class.

2. Uncomment the appropriate test method in the main method of PictureTester to test any of the other methods in Picture.java. You can comment out the tests you don’t want to run. You can also add new test methods to PictureTester to test any methods you create in the Picture class.

Homework:
Exercises
3. Using the zeroBlue method as a starting point, write the method keepOnlyBlue that will keep only the blue values, that is, it will set the red and green values to zero. Create a class (static) method to test this new method in the class PictureTester. Be sure to call the new test method in the main method in PictureTester.

4. Write the negate method to negate all the pixels in a picture. To negate a picture, set the red value to 255 minus the current red value, the green value to 255 minus the current green value and the blue value to 255 minus the current blue value. Create a class (static) method to test this new method in the class PictureTester. Be sure to call the new test method in the main method in PictureTester.

5. Write the grayscale method to turn the picture into shades of gray. Set the red, green, and blue values to the average of the current red, green, and blue values (add all three values and divide by 3). Create a class (static) method to test this new method in the class PictureTester. Be sure to call the new test method in the main method in PictureTester.

6. Challenge — Explore the “water.jpg” picture in the images folder. Write a method fixUnderwater() to modify the pixel colors to make the fish easier to see. Create a class (static) method to test this new method in the class PictureTester. Be sure to call the new test method in the main method in PictureTester.

A4: Two-dimensional arrays in Java

Exercises

1. Write a getCount method in the IntArrayWorker class that returns the count of the number of times a passed integer value is found in the matrix. There is already a method to test this in IntArrayWorkerTester. Just uncomment the method testGetCount() and the call to it in the main method of IntArrayWorkerTester.
2. Write a getLargest method in the IntArrayWorker class that returns the largest value in the matrix. There is already a method to test this in IntArrayWorkerTester. Just uncomment the method testGetLargest() and the call to it in the main method of IntArrayWorkerTester.
3. Write a getColTotal method in the IntArrayWorker class that returns the total of all integers in a specified column. There is already a method to test this in IntArrayWorkerTester. Just uncomment the method testGetColTotal() and the call to it in the main method of IntArrayWorkerTester.

A3: Exploring a picture

Questions

1. What is the row index for the top left corner of the picture?
2. What is the column index for the top left corner of the picture?
3. The width of this picture is 640. What is the right most column index?
4. The height of this picture is 480. What is the bottom most row index?
5. Does the row index increase from left to right or top to bottom?
6. Does the column index increase from left to right or top to bottom?
7. Set the zoom to 500%. Can you see squares of color? This is called pixelation. Pixelation means displaying a picture so magnified that the individual pixels look like small squares.

Homework:
Picture Lab Activity 3

Exercises

1. Modify the main method in the PictureExplorer class to create and explore a different picture from the images folder.
2. Add a picture to the images folder and then create and explore that picture in the main method. If the picture is very large (for instance, one from a digital camera), you can scale it using the scale method in the Picture class.
   For example, you can make a new picture (“smallMyPicture.jpg” in the images folder) one-fourth the size of the original (“myPicture.jpg”) using:

   Picture p = new Picture("myPicture.jpg");
   Picture smallP = p.scale(0.25,0.25);
   smallP.write("smallMyPicture.jpg");
   
   

Sorting

The selection and insertion, are relatively simple, but they are inefficient sequential sorts that use a pair of nested loops and require roughly n^2 comparisons to sort a list of n elements.

More efficient sorts are algorithms that lend themselves to a recursive implementation.
In addtion, the Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

Quick Sort

The quick sort algorithm sorts a list by partitioning the list using an arbitrary chosen partition element and then recursively sorting the sublists on either side of the partition element.

General Strategy:
• First, choose one element of the list to act as a partition element.
• Next, partition the list so that all elements less than the partition element are to the left of that element and all elements greater than the partition element are to the right.
• Finally, apply this quick sort strategy recursively to both partitions.
• The choice of the partition element is arbitrary, we will use the first element in the list.
• For efficiency reasons, it would be nice if the partition element divided the list roughly in half, but the algorithm will work no matter what element is chosen as a partition

Example:

90 65  7   305 120 110 8

we would choose 90 as our partition element.

We would then rearrange the list, swapping the elements that are less than 90 to the left side and those that are greater than 90 to the right side, yielding:

8  65  7   90  120 110 305

We would then apply the quick sort algorithm separately to both partitions. This process continues until a partition contains only one element, which is inherently sorted. Once the initial partition element is determined and placed, it is never considered or moved again.

Here is the book version of the quicksort code:

//-----------------------------------------------------------------
   //  Sorts the specified array of integers using quick sort.
   //-----------------------------------------------------------------
   public static void quickSort (int[] numbers)
   {
      doQuickSort(numbers, 0, numbers.length - 1);
   }
   //-----------------------------------------------------------------
   //  Recursively sorts the portion of the given array beginning
   //  at start and ending at end.
   //-----------------------------------------------------------------
   private static void doQuickSort (int[] numbers, int start, int end)
   {
      if (start < end)
      {
         int middle = partition(numbers, start, end);
         doQuickSort(numbers, start, middle);
         doQuickSort(numbers, middle + 1, end);
      }
   }

   //-----------------------------------------------------------------
   //  Partitions the array such that each value in [start, middle]
   //  is less than or equal to each value in [middle + 1, end].
   //  The index middle is determined in the procedure and returned.
   //-----------------------------------------------------------------
   private static int partition (int[] numbers, int start, int end)
   {
      int pivot = numbers[start];
      int i = start - 1;
      int j = end + 1;

      // As the loop progresses, the indices i and j move towards each other.
      // Elements at i and j that are on the wrong side of the partition are
      // exchanged. When i and j pass each other, the loop ends and j is
      // returned as the index at which the elements are partitioned around.
      while (true)
      {
         i = i + 1;
         while (numbers[i] < pivot)
            i = i + 1;

         j = j - 1;
         while (numbers[j] > pivot)
            j = j - 1;

         if (i < j)
         {
            int tmp = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = tmp;

         }
         else 
         {
           return j;
         }
      }
   }

Wikimedia Commons

Classwork:
1. Trace the quick sort using the data above using the code.

[90,   65, 7,  305,    120,    110,    8]

2. Write the pseudocode looking at the code.

Homework:
4. Under what conditions you have the worse case?
5. What data would yield to a best case and average case?
6. What is the big O notation for this sort for each case?
7. Can you think of a non-recursive QuickSort?
8. Write code for QuickSorting objects. Include compareTo() and toString() methods of the object’s class.

NOTE: WHAT FOLLOWS IS FOR YOUR ENRICHMENT ONLY
It is not part of the AP curriculum.

import java.util.Arrays;

// When we partition data we are dividing it into
// two parts. All items with data above a defined value
// will go in one part and the rest will go in the other

// The value that defines in which group data will go
// is known as the pivot value

public class Partitioning {

    private static int[] theArray;

    private static int arraySize;

    public static void main(String[] args) {

        Partitioning partitionArray = new Partitioning(10);

        partitionArray.generateRandomArray();

        System.out.println(Arrays.toString(Partitioning.theArray));

        // Every item smaller than 35 will be on the left and
        // everything bigger will be on the right

        partitionArray.partitionArray(35);

        System.out.println(Arrays.toString(Partitioning.theArray));

    }

    public void partitionArray(int pivot) {

        // If leftPointer finds an item that is greater
        // than pivot it stops and waits for the rightPointer
        // to find a value less than pivot. Then the items
        // are switched

        // Starts at the left side of array before index 0

        int leftPointer = -1;

        // Starts at the right side of the array after the last index

        int rightPointer = arraySize;

        while (true) {

            // Cycle through array until the end is reached
            // or an item bigger than pivot is found. Then
            // wait for rightPointer to finish cycling

            while (leftPointer < (arraySize - 1)
                    && theArray[++leftPointer] < pivot)
                ;

            printHorzArray(leftPointer, rightPointer);

            System.out.println(theArray[leftPointer] + " in index "
                    + leftPointer + " is bigger than the pivot value " + pivot);

            // Cycle through array until the beginning is reached
            // or an item smaller than pivot is found.

            while (rightPointer > 0 && theArray[--rightPointer] > pivot)
                ;

            printHorzArray(leftPointer, rightPointer);

            System.out.println(theArray[rightPointer] + " in index "
                    + rightPointer + " is smaller than the pivot value "
                    + pivot);

            printHorzArray(leftPointer, rightPointer);

            // When the 2 pointers meet at the middle break
            // out of the while loop

            if (leftPointer >= rightPointer)
                break;

            else {

                // Swap the values in the pointers

                swapValues(leftPointer, rightPointer);

                System.out.println(theArray[leftPointer] + " was swapped for "
                        + theArray[rightPointer]);

            }

        }

    }

    public void swapValues(int indexOne, int indexTwo) {

        int temp = theArray[indexOne];
        theArray[indexOne] = theArray[indexTwo];
        theArray[indexTwo] = temp;

    }

    Partitioning(int newArraySize) {

        arraySize = newArraySize;

        theArray = new int[arraySize];

        generateRandomArray();

    }

    public void generateRandomArray() {

        for (int i = 0; i < arraySize; i++) {

            // Generate a random array with values between
            // 10 and 59

            theArray[i] = (int) (Math.random() * 50) + 10;

        }

    }

    static void printHorzArray(int i, int j) {

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        for (int n = 0; n < arraySize; n++) {

            System.out.format("| %2s " + " ", n);

        }

        System.out.println("|");

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        for (int n = 0; n < arraySize; n++) {

            System.out.print(String.format("| %2s " + " ", theArray[n]));

        }

        System.out.println("|");

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        if (i != -1) {

            // Number of spaces to put before the F

            int spacesBeforeFront = 5 * i + 1;

            for (int k = 0; k < spacesBeforeFront; k++)
                System.out.print(" ");

            System.out.print("L");

            // Number of spaces to put before the R

            int spacesBeforeRear = (5 * j + 1 - 1) - spacesBeforeFront;

            for (int l = 0; l < spacesBeforeRear; l++)
                System.out.print(" ");

            System.out.print("H");

            System.out.println("\n");

        }

    }

}

import java.util.Arrays;

// The Quick Sort is normally the fastest sorting algorithm

public class QuickSort {

    private static int[] theArray;

    private static int arraySize;

    public static void main(String[] args) {

        QuickSort theSort = new QuickSort(10);

        theSort.generateRandomArray();

        System.out.println(Arrays.toString(QuickSort.theArray));

        theSort.quickSort(0, 9);

        System.out.println(Arrays.toString(QuickSort.theArray));

    }

    QuickSort(int newArraySize) {

        arraySize = newArraySize;

        theArray = new int[arraySize];

        generateRandomArray();

    }

    public void quickSort(int left, int right) {

        if (right - left <= 0)
            return; // Everything is sorted

        else {

            // It doesn't matter what the pivot is, but it must
            // be a value in the array

            int pivot = theArray[right];

            System.out.println("Value in right " + theArray[right]
                    + " is made the pivot");

            System.out.println("left = " + left + " right= " + right
                    + " pivot= " + pivot + " sent to be partitioned");

            int pivotLocation = partitionArray(left, right, pivot);

            System.out.println("Value in left " + theArray[left]
                    + " is made the pivot");

            quickSort(left, pivotLocation - 1); // Sorts the left side

            quickSort(pivotLocation + 1, right);

        }

    }

    public int partitionArray(int left, int right, int pivot) {

        int leftPointer = left - 1;

        int rightPointer = right;

        while (true) {

            while (theArray[++leftPointer] < pivot)
                ;

            printHorzArray(leftPointer, rightPointer);

            System.out.println(theArray[leftPointer] + " in index "
                    + leftPointer + " is bigger than the pivot value " + pivot);

            while (rightPointer > 0 && theArray[--rightPointer] > pivot)
                ;

            printHorzArray(leftPointer, rightPointer);

            System.out.println(theArray[rightPointer] + " in index "
                    + rightPointer + " is smaller than the pivot value "
                    + pivot);

            printHorzArray(leftPointer, rightPointer);

            if (leftPointer >= rightPointer) {

                System.out.println("left is >= right so start again");

                break;

            }

            else {

                swapValues(leftPointer, rightPointer);

                System.out.println(theArray[leftPointer] + " was swapped for "
                        + theArray[rightPointer]);

            }

        }

        swapValues(leftPointer, right);

        return leftPointer;

    }

    public void swapValues(int indexOne, int indexTwo) {

        int temp = theArray[indexOne];
        theArray[indexOne] = theArray[indexTwo];
        theArray[indexTwo] = temp;

    }

    public void generateRandomArray() {

        for (int i = 0; i < arraySize; i++) {

            // Generate a random array with values between
            // 10 and 59

            theArray[i] = (int) (Math.random() * 50) + 10;

        }

    }

    static void printHorzArray(int i, int j) {

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        for (int n = 0; n < arraySize; n++) {

            System.out.format("| %2s " + " ", n);

        }

        System.out.println("|");

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        for (int n = 0; n < arraySize; n++) {

            System.out.print(String.format("| %2s " + " ", theArray[n]));

        }

        System.out.println("|");

        for (int n = 0; n < 61; n++)
            System.out.print("-");

        System.out.println();

        if (i != -1) {

            // Number of spaces to put before the F

            int spacesBeforeFront = 6 * (i + 1) - 5;

            for (int k = 0; k < spacesBeforeFront; k++)
                System.out.print(" ");

            System.out.print("L" + i);

            // Number of spaces to put before the R

            int spacesBeforeRear = 5 * (j + 1) - spacesBeforeFront;

            for (int l = 0; l < spacesBeforeRear; l++)
                System.out.print(" ");

            System.out.print("R" + j);

            System.out.println("\n");

        }

    }

}

Looking beyond java and more mathematical: