PS-1

Starter code: PS-1.zip
Note: this assignment relies on ImageIOLibrary.java, ImageGUI.java, and VideoGUI.java being somewhere in your cs10 IntelliJ project, as well as the JavaCV library (which you should have installed in SA-0).

Goal: to build a webcam-based painting program, in which some portion of the image (say your hand, or a marker tip) acts as a "paintbrush".

Core computational problem: to identify the paintbrush in the webcam image. Here we base the recognition solely on color, so it should have a fairly uniform and distinct color. For example, I could wear a dark blue shirt and do torso-based painting, or I could use the green cap of a marker and more delicately paint something. (Both such "paintbrushes" below are recolored to distinguish them.)

Provided for you are scaffolds for the two classes you need to complete: RegionFinder.java and CamPaint.java. TODO comments indicate what you need to fill in; you may also want to define additional helper methods, instance variables, etc. To help you develop and debug, a test driver is also provided: RegionsTest.java that relies on smiley.png and baker.png being a directory called cs10/pictures.

Task 1: Region growing algorithm (50 pts)

To find uniformly-colored regions, we employ a "region growing" (aka "flood fill") algorithm. Region growing initializes a new region at some point that has approximately a specified target color. It then looks at each of the point's neighbors (8 neighbors plus the point if the point is not near the edge of the window). Those that are also approximately the target color become members of the region, and their neighbors also need to be considered. The process continues until no neighbor-of-neighbor-of... points are the desired color. Thus the "flood fill" name: we expand outward from an initial point, as if a bucket of paint had been spilled there and spread to all the pixels of its same color. That detects one region; start again from another point (not already considered) to detect another region.

The basic structure of the algorithm is as follows:

Loop over all the pixels
  If a pixel is unvisited and of the correct color
    Start a new region
    Keep track of which pixels need to be visited, initially just that one
    As long as there's some pixel that needs to be visited
      Get one to visit
      Add it to the region
      Mark it as visited
      Loop over all its neighbors
        If the neighbor is of the correct color
          Add it to the list of pixels to be visited
    If the region is big enough to be worth keeping, do so

The target color is specified by mouse press, as in our simpler color point tracking example in class. The flood fill identifies connected regions of points that are approximately that target color. There may be several such regions on the image. The paintbrush is the largest such region.

Task 1.1: Find regions (25 pts)

In RegionFinder.java, fill in findRegions() based on the pseudocode above.

The built-in Java Point class holds x and y coordinates. We can package up a list of them and think of it as a region. A list of these lists is then our set of regions.

We need to keep track of the neighbors (and neighbors of neighbors...) that need to be visited in the region we are growing. An ArrayList can do that. Initialize it with the mouse click point. Then in a loop, remove a point from the list, and handle it by adding its (up to 8) neighbors to the to visit list (if they are close enough to the target color – see Task 1.2 below). Two other classes that we'll use more extensively soon have the same ability: Stack lets us push and pop objects, while Queue lets us enqueue and dequeue. Any of these approaches is fine.

We also need to keep track of which points we've visited, so that we don't revisit them. An additional image provides a convenient way to do that, as it's exactly the same structure of the one we're looking at. It starts off as all black (getRGB() is 0), and we can change the color of an (x,y) position to something else (say setRGB() to 1) when we visit it. Thus we don't keep going to a pixel again and again, instead we only visit each pixel one time.

visited = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
...
if (visited.getRGB(x, y) == 0) {
  ...
   visited.setRGB(x, y, 1);
}

Q1. Why would we not also use an ArrayList to keep track of points we have visited?

Store all the regions you find (above the minRegion threshold) in the regions list.

Task 1.2: Color matching (5 pts)

In RegionFinder.java, fill in colorMatch().

There are many ways we could test color similarity. In my solution, I simply compared the absolute value of each channel (red, green, blue), and made sure each channel is less than the maxColorDiff threshold instance variable. Euclidean distance is also fine.

Task 1.3: Finding the largest region (10 pts)

In RegionFinder.java, fill in largestRegion(). Should be self-explanatory.

Task 1.4: Recoloring (10 pts)

In RegionFinder.java, fill in recolorImage(). In the copied image recoloredImage, recolor each found region to a (different) uniform random color.

Testing

Once all of RegionFinder.java is complete, you can run RegionsTest.java to test your code (feel free to change the target colors).

For example, here's what I get for the brick-ish regions (R=130, G=100, B=100) with at least 50 pixels in the usual Baker image, recolored to random colors:

Submit a corresponding image from running your region growing algorithm on baker.png. Depending on choices of parameters, it may be somewhat different from mine; that's okay.

Q2. Briefly describe the implementation and parameter choices you made and their impact on the detected regions.

Task 2: Webcam painting (20 pts)

The basic idea is that the region finder gives regions for each frame of the camera, the largest of which is considered the paintbrush. The paintbrush leaves a trail over time as it moves around (on an otherwise white canvas). That's the painting. For example:

The basic structure is like other webcam code. I've provided some instance variables and key commands to set the tracking color, save snapshots, and control which image is being shown (in the handleKeyPress method).

In general, webcam processing can be flaky. Work in a well-lit room. Do all the core development with static images first via the test code (i.e., no webcam required).

Task 2.1: Handle mouse press (5 pts)

Here is a video showing how it works:

In CamPaint , fill in handleMousePress() . Set the target color for the paintbrush.

Task 2.2: Draw the new image (15 pts)

In CamPaint , fill in handleImage() to display the appropriate image depending on the display mode ('w', 'r', or 'p').

If 'w': show the live webcam with no processing.

If 'r': use your region finder to find regions of the target color and show the randomly recolored image (as in the static version from Task 1).

If 'p': show the painting! Use your region finder to find the paintbrush (the largest region), then update the painting. That is, the pixels within the paintbrush should be recolored to paintColor in the painting, thereby leaving a trail. You can color them however you like; my sample solution is monochromatic, but you could transfer colors from the webcam, allow the user to set colors, etc.

Testing

Submit screenshots of you / your partner's work, both an image of webcam with recolored regions and a resulting painting.

Q3. Briefly describe any limitations or clunkiness you encountered with your region growing and painting algorithms. How might you might you improve on those?

Extra credit

You may obtain extra credit for extending and enhancing the app. Only do this once you are completely finished with the specified version. In your write-up, explain what you did and how it works.

[10 pts each] Allow multiple brushes, allow pause/restart of the painting, easy change of colors and brushes, etc.
[15 pts] Account for the size, shape, and trajectory of the specified paintbrush to filter out some of the spurious ones

What to submit

Submit a single zip file to Canvas containing these files:

Completed versions of RegionFinder.java and CamPaint.java
Screenshots of the static region finding on baker.png
Screenshots of region finding on your webcam in action and resulting painting(s)
Document with your answers and discussion of the green-highlighted questions above (number them, please)

If you worked with a partner and wrote one solution, both partners should each submit the same code. Note your partnership with an @author tag for each partner in your code, and also list both partners in the Canvas submission text box. One of the submissions will be graded and both partners will receive the same grade.

Grading Rubric

Total of 100 points

Correctness (70 points)

5	Matching color
5	Starting region growing at appropriate pixels
5	Keeping track of visited pixels
5	Keeping track of to-visit pixels
5	Visiting correctly colored neighbors
5	Keeping big-enough groups of points as the regions
10	Recoloring image based on detected regions
10	Finding the largest region
5	Drawing the appropriate image
5	Setting tracking color
10	Updating the painting according to the paintbrush

Structure (10 points)

4	Good decomposition of and within methods
3	Proper used of instance and local variables
3	Proper use of parameters

Style (10 points)

3	Comments included within methods and for new methods
4	Consistent and informative names for variables, methods, parameters
3	Clean and consistent layout (blank lines, indentation, no line wraps, etc.)

Testing & discussion (10 points)

2	Answer to the three (3) Questions (Q1, Q2, and Q3) for each green highlighted textbox
4	Static image (Baker) region detection and discussion
4	Webcam region detection, painting, and discussion