Assignment 1: Problem Solving Example

First, an outline

Let's start with what we know:

We know both the input and output:
- The input is a 2D array.
- The output is a 2D array.

This suggests that, at least, the overarching method that "does the job" should look like this:

    public static double[][] strangeAverage (double[][] A)
    {
        // Make a new array B whose entries we compute,
        // perhaps calling other methods as needed.
        // return B;
    }

Does the 2D array have to be square?
- Each element of the second array depends on neighbors of the corresponding element in the first.
- There does not seem to be any requirement that the array be square.
Here's one important observation:
- Each element of B can be computed independently of any other element of B.
- This means we don't need to track anything through the iterations.

Let's now add just a little more detail:

    public static double[][] strangeAverage (double[][] A)
    {
        // We're doing to need space: same size  as A. And note that
        // the array could be rectangular.
	double[][] B = new double [A.length][A[0].length];

        // Since we are computing each element of B, at this time, 
        // we can fill in the outline of the iteration:
        for (int i ... ) {
            for (int j ...) {
                // Let some method do the work ...
                B[i][j] = findBoxAverageInSomeMethod (i, j)
            }
        }

        return B;
    }

What do we need to pass into the method that'll do the average for that particular element?

A1.3 Exercise: Before reading ahead, think about what needs to go into the method as parameters, and what the structure of that method ought to be.

Next steps: the nitty gritty of the computation

Notice that once we know which cell we're doing the average for, all we need is the location in the first array ... and of course the array itself.

                B[i][j] = boxAverage (A, i, j)

We'll call it boxAverage(). It returns a single number (the neighbor average) that goes into the i,j-th element of B.

What's nice is that, all we need now is the details of this method:

If we're at the i,j-th entry, how do we iterate through its neighbors?

A1.4 Exercise: Before reading ahead, try thinking through this.

The key observation: the neighborhood box is itself like a mini 2D array.
- Thus, if we can set up an iteration through this mini-array, we can sum up its values.
- Once we have the sum, we can compute the average.

The idea can be outlined as follows:

    static double boxAverage (double[][] A, int i, int j)
    {
	double sum = 0;

        // One row behind: i-1. One row ahead: i+1
        // Same thing for the column:
	for (int m=i-1; m<=i+1; m++) {
	    for (int n=j-1; n<=j+1; n++) {
    	        // m and n iterate through neighbors of i,j.
    	        // Accumlate A[m][n] in the sum.
	    }
	}
    
        // Compute average and return.
    }

However, there are two issues to resolve:
- There are "corner" cases (all four corners, and the edge rows and columns).
- The average will depend on how many values are counted in the corner cases.
How do we handle the special treatment for corner cases. There are a couple of options:
1. First handle the inner elements, then separately handle the special cases.
2. Try and integrate the special cases directly.

We'll use the latter approach as follows:

    static double boxAverage (double[][] A, int i, int j)
    {
        // ... initialize sum ..

	double sum = 0;

        // m and n iterate through potentially invalid locations
	for (int m=i-1; m<=i+1; m++) {
	    for (int n=j-1; n<=j+1; n++) {
                // Check if m and n are valid array locations
                // If so, then include in sum
                }
	    }
	}
    
        // Compute average and return ...
    }

With a little more detail ...

    static double boxAverage (double[][] A, int i, int j)
    {
	double sum = 0;

        // One row behind: i-1. One row ahead: i+1
        // Same thing for the column:
	for (int m=i-1; m<=i+1; m++) {
	    for (int n=j-1; n<=j+1; n++) {
                if ( isValidElement (A,m,n) ) {
                    // Include this in the sum, and increment a counter 
                    // to track the number values added sum.
                }
	    }
	}
    
        // Compute average and return.
        double avg = sum / count;
        return avg;
    }

Luckily for us, it's easy to determine whether any two integers m,n are valid array locations (array indices).

A1.4 Exercise: In StrangeAverage2D.java write up all the above code and complete the remaining parts to make it work.

To test your code, use the following in main()

    public static void main (String[] argv)
    {
	// Test 1:
	double[][] A = {
	    {0,1,0,1,0,1},
	    {1,0,1,0,1,0},
	    {0,1,0,1,0,1}
	};

	print (strangeAverage(A));

	// Test 2:
	double[][] A2 = {
	    {1,2,3,4},
	    {5,6,7,8},
	    {9,10,11,12},
	    {13,14,15,16}
	};

	print (strangeAverage(A2));
    }

    static void print (double[][] A)
    {
        // Neater printing with printf:
	for (int i=0; i<A.length; i++) {
	    for (int j=0; j<A[i].length; j++) {
		System.out.printf (" %6.3f", A[i][j]);
	    }
	    System.out.println ();
	}
	
    }

You should get

  0.500  0.500  0.500  0.500  0.500  0.500
  0.500  0.444  0.556  0.444  0.556  0.500
  0.500  0.500  0.500  0.500  0.500  0.500

  3.500  4.000  5.000  5.500
  5.500  6.000  7.000  7.500
  9.500 10.000 11.000 11.500
 11.500 12.000 13.000 13.500

An application

When your code is working, replace the code in main() with

        // Display an image, unmodified:
	ImageTool imTool = new ImageTool ();
	int[][] pixels = imTool.imageFileToGreyPixels ("eniac.jpg");
	imTool.showImage (pixels, "ENIAC");

        // Our strange-average uses a double array, so copy over
        // the integer pixels into a double 2D array:
	double[][] A = convertToDouble (pixels);

        // Our strange average:
	double[][] B = strangeAverage (A);

        // Convert back to an integer array, ENSURING that all
        // values are between 0 and 255. (Truncate if out of these bounds).
	int[][] pixels2 = convertToPixels (B);

        // Display the resulting image:
	imTool.showImage (pixels2, "ENIAC2");

A1.5 Exercise: Write the additional code needed to make this work. What is the effect on an image. You can use eniac.jpg or your own black-and-white JPEG image. You will also need ImageTool.java.

So, at last we know why the strange averaging method was used.

About this type of averaging:

This is one of several such "image operators", small computations that act on images.
They are called convolutions in the image processing literature.
Variations of the basic procedure allows one to sharpen an image, reduce noise, identify edges and so on.

Back to the assignment