About BufferedImage and the GUI Layout

The starting program for the lab already uses an object of type BufferedImage. You will need to use the setRGB() and getRGB() methods in that object. This section discusses these methods and tells you a little about BufferedImages in general.

A BufferedImage is an object that represents a rectangular drawing surface that is stored in the computer's memory but is not shown on the screen. You can obtain a graphics context for drawing on the image, and you can easily copy the image onto the screen (or into another BufferedImage). The BufferedImage class is in the package java.awt.image, and they are discussed in Section 13.1

If image is a variable of type BufferedImage, you can create a buffered image that is width pixels wide and height pixels tall by saying:

     image = new BufferedImage( width, height, BufferedImage.TYPE_INT_ARGB );

The third parameter is a constant that says how the colors of pixels in the image are represented. There are other types of images, but INT_ARGB is the most common. For this type of image, a color is represented as a 32-bit integer with 8 bits for each color component, alpha, red, green, and blue. Colors are usually written as hexadecimal numbers such as 0xFFFF0000, which represents a pure red. (The alpha component has to do with transparency and should always be hexadecimal FF for standard opaque colors.)

You can get a graphics context of type Graphics2D for drawing on the buffered image by calling image.createGraphics(). However, for this program, you will be getting and setting the colors of individual pixels. For that, you can use

      int color = image.getRGB(x,y);

to get the integer that codes the color of the pixel at position (x,y), that is, in row y and column x of the image; and you can use

      image.setRGB( x, y, color );

where color is an int, to set the color of the pixel at (x,y). These methods will throw an exception if x or y is outside the valid range for the width and height of the image.

For this program, you will only need three colors, to represent a filled square, an empty square, and an empty square that has been "marked" as part of blob-counting or percolation testing. These colors are already defined in the program as constants:

private final static int COLOR_EMPTY = 0xFF000000;
private final static int COLOR_FILLED = 0xFFFFFFFF;.
private final static int COLOR_MARKED = 0xFFFF0000;

You can, for example, use a test such as "if (image.getRGB(x,y) == COLOR_EMPTY)" to test whether a square is empty, and you can "mark" a square by saying "image.setRGB(COLOR_MARKED);".

The program defines a class named Display to define a panel that displays a copy of the BufferedImage. The image is 2048-by-2048 pixels, which is too large to display on the screen at one time, so the program puts a Display in a JScrollPane before adding it to the main panel. The display is 2048-by-2048, so it shows the entire image, but the scroll pane has a preferred size of 750-by-750, so only part of the image is visible at one time. The scroll pane provides scroll bars that the user can adjust to see other parts of the image. This is set up in the Percolation constructor with the commands:

display.setPreferredSize( new Dimension(2048,2048) );
JScrollPane scroller = new JScrollPane( display );
scroller.setPreferredSize( new Dimension( 750, 750 );
add( scroller, BorderLayout.CENTER );

The constructor also makes a panel of type Box to hold buttons and other controls. So far, the box only holds an input box for the fill ratio and a button that the user can press to make a new grid of squares. You will be adding additional controls to the box.

Finally, there is a JLabel named message that you can use to show messages to the user. The constructor creates the label and places it at the bottom of the main panel. You can use message.setText(someText) to display a message to the user.

Part 1: Blob Counting and Mouse Clicks

Time to get to work...

You can start by adding some mouse interaction to the program. The program should respond to a mouse click on the display by marking and counting the blob at the (x,y) position where the user clicked. You will have to add a mouse listener to the display. There are at least three ways to define listeners: (1) by declaring that the main class itself "implements MouseListener", and using this as the listener object; (2) by using a separate class to represent the listener; and (3) by using an anonymous inner class. Using the last technique, you can do the following in the constructor:

        
display.addMouseListener( new MouseAdapter() {
    public void mousePressed(MouseEvent e) {
        int x = e.getX();
        int y = e.getY();
          .
          .
          .
    }
});

In the mousePressed method, if the user clicks a pixel that is not empty, you should simply display a message to that effect to the user (by calling message.setText). If the user has clicked an empty pixel in the image, you want to mark all the empty pixels that can be reached from the initial pixel by sequences of horizontal and vertical moves. You also want to count the number of pixels that you mark; that number is the size of the "blob" at (x,y). To do this, you will have to write a method, discussed below, for marking a blob and counting its squares. Call the method, then tell the user the size of the blob by setting the text in the JLabel.

You should also call display.repaint() after marking the blob, in order for the change to appear on the screen. Whenever you change the image, you have to call display.repaint(). I won't point this out again.

You will need a method to mark and count a blob. The recursive method in Section 9.1 has a problem: In this very large image, the recursion can go too deep. With a fill ratio of 0.6 or higher, you would be very likely to get stack overflow errors in the recursion. It's possible to increase the stack size in the Java Virtual Machine, but a better solution in this case, I think, is to use a queue to implement the algorithm. I used a queue of Points. Point is a built-in class. An object pt of type Point has two public instance variables, pt.x and pt.y, of type int, so you can use an object of type Point to represent the coordinates of a pixel.

In fact, you don't have to implement a queue of points yourself. You can just use a variable of type LinkedList<Point> as a queue. Use the list's add and remove methods for the queue's enqueue and dequeue operations.

Here is the algorithm for blob counting using a queue, assuming that (x,y) is the position in the image where you want to count the blob:

            
if there is not an empty square at (x,y)
   return 0
count = 0
start with an empty queue of Points
mark position (x,y)   [by changing its color to COLOR_MARKED]
add (x,y) to the queue
while the queue is not empty {
    remove a point, (x,y), from the queue
    count++
    if (x-1,y) is in the image and is empty
        mark position (x-1,y)
        add (x-1,y) to the queue
    if (x+1,y) is in the image and is empty
        mark position (x+1,y)
        add (x+1,y) to the queue
    if (x,y-1) is in the image and is empty
        mark position (x-1,y)
        add (x,y-1) to the queue
    if (x,y+1) is in the image and is empty
        mark position (x,y+1)
        add (x,y+1) to the queue
}
return count

You should write a method to implement this algorithm, and you should call that method in your mouse handler when the user clicks an empty pixel in the image. (You will need the method again later for other purposes.)

At this point, you should be able to run the program and click the image. If you click an empty square, the blob at that position should turn red, and you should be told the number of pixels in the blob. I suggest that you try it for several different fill ratios: 0.55, 0.59, 0.6, and 0.7. (And maybe even for fill ratio 1.0.)

Part 2: Percolation (and Clearing)

The goal is to experiment with percolation, which means trying to find a path of empty squares from the top of the image to the bottom. But with the blob marking method in hand, this is easy! Just go across the top row of pixels, and call the blob-marking method for each pixel in that row. Then go along the bottom row of pixels, and check whether any them have been marked, that is, whether their color is red. If so, you have percolation. Really, before running this test, you need to go through the image and change any pixel that has already been marked back to empty.

You can write methods -- named, for example, clear and testPercolation -- to implement the operations changing all marked squares back to empty and of testing for percolation.

So, the main question is when to test for percolation. The GUI needs some way of letting the user ask for a percolation test to be run. There are basically two ways to do that: With a menu command or with a button. For this program, we are only using buttons. You want to add a button to the strip of controls along the right edge of the Percolation panel, and you want to program that button to do a percolation test.

You will need an instance variable of type JButton to represent the button. The Percolation constructor should create the button and add it to the box of controls. It should also set up an ActionListener for the button. You can imitate what is already done for the refillButton. One nice touch is to add some empty space between the two buttons. You can do this by adding a "vertical strut" to the controls:

controls.add(Box.createVerticalStrut(40));

Finally, you need to handle a click on the button by adding appropriate code to the actionPerformed method. In this case, you just want to call your method for testing for percolation.

While you are at it, add another button for clearing the grid. When the user clicks that button, you should call your clear method.

Part 3: An Overview Display

Since the image is too big to show on the screen all at once, I would like you to add a small "overview display" to show a reduced-size copy of the image. (By the way, I expected the overview to be an averaged-out gray, but apparently Java "samples" pixels from the image, so the overview actually shows -- somewhat deceptively -- the same sort of random colors as the full image. You could probably get the averaging effect by turning on anti-aliasing, but I don't think it would look as good.)

For the overview, you can use a second object of type Display, the same class that is used for the big image. You just have to set the size of the overview display to be 128-by-128. You will need a second instance variable of type Display. The percolation constructor should create the overview display and add it to control box. Remember that any time you change the main image, you also have to call the repaint() method of the overview display so that it will also reflect the change.

The thing that makes Boxes not-so-easy to use is that they can do strange things when sizing and lining up components. A component might, for example, end up much larger than you would like and have its center lined up with the left edges of other components. (That's what I found happened when I added a panel to a box.) To fix the size problem, you might have to set a maximum and/or a minimum size for the component. Here's what I had to do with the overview display, instead of just setting the preferres:

overviewDisplay.setMinimumSize(new Dimension(128,128));
overviewDisplay.setMaximumSize(new Dimension(128,128));
overviewDisplay.setAlignmentX(LEFT_ALIGNMENT);

You might notice that I did something similar with the fill ratio input box.

Part 4: Blob Stats

The only piece of functionality that is still missing in the program is the ability to gather some statistics about the blobs. You should add a "Blob Stats" button to your interface, and you should write a method to implement it. The goal is to count the blobs in the image, find their average size, and find something that I call the average neighborhood. The average size is the total number of pixels in all the blobs, divided by the number of blobs. However, there is a problem with this statistic: What I really want to know is, if I click a blob, how big should I expect it to be? That's not the same as the average size, since you are more likely to click on a large blob than a small blob. Suppose that there is one giant blob and a large number of much smaller blobs (which is pretty much what happens when the fill ratio is large). In that case, the average blob size can be pretty small. But a random click is very likely to land in the single giant blob, which means that the expected blob size should be pretty large.

To get a better statistic, we can do the following: For each pixel that is in some blob, take the size of the blob that contains that pixel (that is, the size of that pixel's "neighborhood"). Add up all these numbers, and divide by the number of pixels in all the blobs. If a blob contains N pixels, than the number N gets added into the sum not just once but N times, once for each pixel in the blob. N  is added to the sum N times -- another way to do the same thing is to simply add N² to the sum. So to compute the average neighborhood size, we need to find the sum of all the squared sizes of the blobs as well as the sum of all the sizes. (The second sum gives the total number of pixels in all the blobs.) The average neighborhood size is the sum of the squared sizes divided by the sum of the sizes. Anyway, the blob stats method should do the following:

clear any existing marks from the image
count = 0
sizeSum = 0
squaredSizeSum = 0
for each pixel
   if that pixel is empty
      count++
      call the method to mark the blob and find its size
      add the size to sizeSum
      add the square of the size to squaredSizeSum
the average blob size is sizeSum divided by count
the average neighborhood size is squaredSizeSum divided by sizeSum
report the results in a message to the user

One warning: When you compute the square of the size, you will be working with large numbers that can exceed the capacity of a 32-bit integer. In particular, if size is of type int, then the value of size*size might be incorrect because the correct value can't be represented as an int! Saying ((long)size)*size would give the correct value. Making size long (or double) in the first place would also work. For the same reason, the type of squaredSizeSum should be long (or double).

One final remark: To output double numbers nicely on the command line, you would probably use System.out.printf. You can't do that in a GUI. However, the String class contains a static method

        String.format(formatString, val1, val2, ...)

that returns the same string that would be printed out by

        System.out.printf(formatString, val1, val2, ...)

You can use this along with message.setText to display nicely formated strings. (There is already an example in the actionPerformed method.)

You should have enough information to get the blob stats command working. The results that you can get from this command are interesting. In particular, the average neighborhood size shows a very sharp increase between fill ratios of about 0.59 and 0.60. This is the phase transition. The average neighborhood is the real measure of how far you can expect liquid to be able to spread through the grid. On an infinite grid, the average neighborhood size actually becomes infinite at the phase transition, and the transition is infinitely sharp. For finte grids, the larger the grid, the sharper the phase transition.

If someone wanted to do it, perhaps even for a final projet, there are a lot of experiments that could be run. You might, for example, create many grids for each fill ratio and find and graph the average of their average neighborhood sizes. You could also graph the probability of percolation. You could see how the graphs depend on grid size. You might see how different types of grid change the result. For example, what if we allow neighbors in the diagonal directions? You might even look at the three-dimensional cases. For these experiments, you would presumably want non-GUI programs that could do a lot of calculations and save the results.