Today we think we'll work on consolidating pixels into actual hits, or an approximation thereof. Join us at Borders. If nothing else, you'll see a prodigious 18 minute spewing of code.

Our Cunning Plan

We talked a bit about how to proceed. I’ll type this up while Chet builds a test. Our existing ShotPattern object shows signs of a new class wanting to come into being, because it’s divided into two kinds of functionality. It has a bunch of methods that work with a Raster, and another batch of methods that deal with Hits, center of gravity, and the like. Take a look at the code below; I’ll highlight the Raster-focused bits and leave the Hit-focused bits alone:

public class ShotPattern {
    int width;
    int height;
    ArrayList<Hit> hits = new ArrayList<Hit>();

    public ShotPattern(ArrayList<Hit> hits) {
        this.hits = hits;
    }

    public ShotPattern(String fileName) {
        Raster farian = raster(fileName);
        width = farian.getWidth();
        height = farian.getHeight();
        int yOffset = height / 2;
        int xOffset = width / 2;    

        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                addHit(farian, yOffset, xOffset, y, x);
            }
        }
    }

    private void addHit(Raster raster, int yOffset, int xOffset, int y, int x) {
        if (isHit(raster, y, x)){
            int invertedYforBMP = -(y - yOffset);
            this.hits.add(new Hit(x - xOffset,invertedYforBMP));
        }
    }

    private boolean isHit(Raster raster, int y, int x) {
        int[] sampleArray = null;
        return (raster.getPixel(x, y, sampleArray))[0] == 0;
    }

    private Raster raster(String fileName) {
        BufferedImage img = null;
        try {
            img = ImageIO.read(new File(fileName));
        } catch (IOException e) {
        }

        Raster raster = img.getData();
        return raster;
    }

    public ShotPattern(int width, int height) {
        this.height = height;
        this.width = width;
    }

    public Hit centerOfMass() {
        if (hits.size() == 0) return new Hit(0,0);
        return new Hit(xCenter(), yCenter());
    }

    private int yCenter() {
        int sum = 0;
        for (Hit hit : hits) {
            sum += hit.getY();
        }
        return sum/hits.size();
    }

    private int xCenter() {
        int sum = 0;
        for (Hit hit : hits) {
            sum += hit.getX();
        }
        return sum/hits.size();
    }

    public void addHit(Hit hit) {
        hits.add(hit);
    }

    public void addHit(int x, int y) {
        addHit(new Hit(x,y));
    }

    public int[] analyzeDensity(int width, int height) {
        int[] result;
        int numX = this.width / width;
        int numY = this.height / height;
        result = new int[numX*numY];
        Rectangle rect = new Rectangle(width-1, height-1);
        int location = 0;
        for (int top = 0; top < this.height; top+= height) {
            for (int left = 0; left < this.width; left+=width) {
                rect.setLocation(left, top);
                result[location] = density(rect);
                location++;
            }
        }
        return result;
    }

    private int density(Rectangle rect) {
        int count = 0;
        for (Hit hit : hits) {
            if (rect.contains(hit.getX(), hit.getY()))
                count++;
        }
        return count;
    }

    public int[] analyzePolar() {   
        Wedge[] wedges = createWedges();
        for (Wedge wedge: wedges) {
            for ( Hit hit: hits) {
                wedge.tally(hit);
            }
        }
        int tally = 0;
        int[] result = new int[16];
        for (Wedge wedge: wedges) {
            result[tally++] = wedge.count();
        }
        return result;
    }

    private Wedge[] createWedges() {
        Wedge[] wedges = new Wedge[16];
        int wedge = 0;
        int deltaR = 30;
        double deltaTheta = Math.PI/4;
        for (int radius = 0; radius < 60; radius += deltaR) {
            for (double theta = 0; theta < 2*Math.PI; theta += deltaTheta) {
                wedges[wedge++] = new Wedge(radius, radius+deltaR, theta, theta+deltaTheta);
            }
        }
        return wedges;
    }
}

We’d like to begin pulling the Raster material away from the Hit material. The Hit material seems to belong with the ShotPattern, and the Raster material with some other class.

We discussed a few design options, and came up with this one: We’ll create a new object, PatterningSheet, that represents the picture of the sheet of target paper. Our ShotPattern object will create one of these, pointing to a file name, and ask it to create a list of Hits. The PatterningSheet will search the bitmap, creating the Hit list, using an approach like we talked about last time, searching the bits around a given pixel, and if there are adjacent ones, adding them to the current hit. The PatterningSheet will return the Hit list, and will be disposed of. (We noticed that we haven’t closed any files in the existing code, and we’re hoping that the Raster and other such objects have done all that for us. If any closing needs to be done, it’ll all be in the PatterningSheet.)

Having built the PatterningSheet in TDD style, we’ll then plug it into ShotPattern, and everything should be just fine. Some tests may want to be moved or changed, because when we’re done, the ShotPattern will be looking at Hits containing more than one pixel.

It’s also worth noting that the Hit object will wind up being extended along the way to include more than one point. At this moment, I’m not inclined to TDD that, because I expect the TDD on the PatterningSheet will drive that behavior into Hit. We’ll see what happens, and I’ll try to remember to talk about it later.

Begin with a test. We created a BMP file with just two pixels in it:

image

And wrote this test and implementation:

public class PatterningSheetTest {

    final String folder = "Data\\";

    @Test
    public void twoHitsOn7x12() {
        PatterningSheet sheet = new PatterningSheet(folder + "twoHitsOn7x12.bmp");
        List hitList = sheet.getHits();
        assertEquals(2, hitList.size());
    }
}
public class PatterningSheet {

    public PatterningSheet(String string) {
    }

    public List getHits() {
        return new ArrayList();
    }
}

This gives us a red bar, because we expect two Hits, and of course our fake return is returning zero.

We proceed by copying some code over from ShotPattern, which knows how to read a Raster, and modifying it just enough to make it work. At the moment, our addHit method is just returning single pixels, which is fine, because our twoHitsOn7x12 file has just two pixels in it. Our resulting green bar comes from this code:

public class PatterningSheet {
    private String fileName;

    public PatterningSheet(String fileName) {
        this.fileName = fileName;
    }

    public List getHits() {
        int[] pixelArray = null;
        ArrayList hits = new ArrayList();
        WritableRaster farian = raster(fileName);
        int width = farian.getWidth();
        int height = farian.getHeight();
        int yOffset = height / 2;
        int xOffset = width / 2;    

        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if ((farian.getPixel(x, y, pixelArray)[0]) == 0)
                    hits.add(makeHit(farian, yOffset, xOffset, y, x));
            }
        }
        return hits;
    }   

    private Hit makeHit(WritableRaster farian, int offset, int offset2, int y, int x) {
        return new Hit(x,y);        
    }

    private WritableRaster raster(String fileName) {
        BufferedImage img = null;
        try {
            img = ImageIO.read(new File(fileName));
        } catch (IOException e) {
        }

        WritableRaster raster = (WritableRaster) img.getData();
        return raster;
    }
}

That code is all new, of course. I highlighted one bit: the makeHit() method. The idea is that the makeHit() method gets called as soon as the main scan loop finds a pixel that is zero (black) (remind me to improve the expressiveness of that), and that makeHit() will be the place where the searching gets done to find all the adjacent pixels.

The bar is green.

We added another picture, with big hits where the single pixels were:

image

… and wrote a corresponding test and this code:

public class PatterningSheet {
    private String fileName;

    public PatterningSheet(String fileName) {
        this.fileName = fileName;
    }

    public List getHits() {
        int[] pixelArray = null;
        ArrayList hits = new ArrayList();
        WritableRaster farian = raster(fileName);
        int width = farian.getWidth();
        int height = farian.getHeight();
        int yOffset = height / 2;
        int xOffset = width / 2;    

        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if ((farian.getPixel(x, y, pixelArray)[0]) == 0)
                    hits.add(makeHit(farian, yOffset, xOffset, y, x));
            }
        }
        return hits;
    }   

    private Hit makeHit(WritableRaster farian, int offset, int offset2, int y, int x) {
        Hit hit = new Hit();
        hit.addPoint(new Point(x,y));
        List<Point> points = adjacentPoints(x,y);
        for (Point point: points)
            hit.addPoint(point);
        return hit;
    }

    private List<Point> adjacentPoints(int x, int y) {
        return new ArrayList<Point>();
    }

    private WritableRaster raster(String fileName) {
        BufferedImage img = null;
        try {
            img = ImageIO.read(new File(fileName));
        } catch (IOException e) {
        }

        WritableRaster raster = (WritableRaster) img.getData();
        return raster;
    }
}

We added a little code in Hit, as well, like this:

public class Hit {
    private List<Point> points = new ArrayList<Point>();
    private double r;
    private double theta;

    public Hit(int x, int y) {
        this.addPoint(new Point(x,y));
    }

    public void addPoint(Point point) {
        points.add(point);
    }

    public Hit() {

    }

    public int getX() {
        return points.get(0).getX();
    }

    public int getY() {
        return points.get(0).getY();
    }

    @Override
    public int hashCode() {
        final int PRIME = 31;
        int result = 1;
        result = PRIME * result + getX();
        result = PRIME * result + getY();
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Hit other = (Hit) obj;
        if (getX() != other.getX())
            return false;
        if (getY()!= other.getY())
            return false;
        return true;
    }

    @Override
    public String toString() {
        return "Hit(" + getX() + "," + getY() + ")";
    }

    public double r() {
        r = Math.sqrt(getX()*getX()+getY()*getY());
        return r;
    }

    public double theta() {
        theta = Math.atan2((double)getY(), (double) getX());
        if (theta < 0) theta += 2*Math.PI;
        return theta;
    }
}

This is just a refactoring, in that it keeps our simple test green, and the more complex one is still red. These changes just make a place for the adjacentPixels code to live.

Then a Bigger Bite

At this point, all had gone smoothly, with only five or ten minutes between green bars. Now it was time to make the step to processing adjacent pixels to find all the continguous pixels in a Hit. Basically, I thought I knew what was needed, and I just typed what follows into PatterningSheet, in a “by intention” style:

private Hit makeHit(WritableRaster farian, int offset, int offset2, int y, int x) {
        Hit hit = new Hit();
        hit.addPoint(new Point(x,y));
        List<Point> points = adjacentPoints(x,y);
        for (Point point: points)
            hit.addPoint(point);
        return hit;
    }

    private List<Point> adjacentPoints(int x, int y) {
        ArrayList<Point> points = new ArrayList<Point>();
        points.add(new Point(x,y));
        for (int i = 0; i < points.size(); i++) {
            for (Point point: candidates(points.get(i))) {
                if (wasOn(point)) {
                    points.add(point);
                }
            }
        }
        return points;
    }

Here, adjacentPoints() creates a list of points, starting with our current point. It loops over that list adding to it as it goes. For each point it finds, it considers the candidate contiguous points, and if those points were “on”, i.e. black, adds them to the list. This will continue until the candidates find no new black pixels.

The word “wasOn” is important: each pixel found on will be turned off, so that we won’t loop forever finding the same points.

Then I coded candidates():

   private List<Point> candidates(Point point) {
        List<Point> candidates = new ArrayList<Point>();
        int x = point.getX();
        int y = point.getY();
        for (int newX = x-1; newX <= x+1; newX++)
            for (int newY = y-1; newY <= y+1; newY++) {
                if ( newX != x || newY != y)
                candidates.add(new Point(newX, newY));
            }
        return candidates;
    }

… which just picks all the points directly next to the input point. We don’t include the input point, since we’ve already looked at it.

Then for wasOn:

   private boolean wasOn(Point point) {
        int x = point.getX();
        int y = point.getY();
        if (x < 0 || y < 0) return false;
        if (x >= farian.getWidth() || y >= farian.getHeight()) return false;
        return wasZero(x,y);
    }

    private boolean wasZero(int x, int y) {
        int wasZero = farian.getPixel(x, y, pixelArray)[0];
        farian.setPixel(x, y, whiteArray);
        return wasZero == 0;
    }

This, too, is straightforward. We check for points outside the Raster, which are of course not on. Then we return whether the point in question was zero. That’s implemented by looking at the pixel, and setting it from black to white, ensuring that it’s only counted twice. Just for completeness, here’s the code for the whiteArray:

    private int[] whiteArray = new int[] {1};

I really just typed all this in, with some help from Chet, mostly on obvious mistakes and forgettings. It took 18 minutes. We ran the tests, and the second “BigHit” test went green. I had a little trepidation, but was around 85 percent sure that it would.

Too Big a Bite

I’ve commented often that when I go 20 minutes without a green bar, I’ve probably gone too long. Chet and I had discussed, before I started this code-spitting exercise, that it would take a little while. Had it not “just” worked, we’d have been morally obligated to do it over in smaller bites, though we might have fallen down and debugged instead. But in fact it worked.

Frankly, I feel that this bit of code was more a tribute to my brain (the size of a planet, you’ll recall), than to any particular technique that we could recommend to anyone. We spoke along the way of doing incremental tests, and didn’t, primarily because we would have had to make some things public that we had made private. (Does this suggest that this object needs some splitting? We should think about that.)

During the 18 minute gap, I was on a roll, and I think Chet just watched it happen. I don’t recall a lot of discussion, and I think maybe he felt just swept along.

In any case, my assessment is that this was not an ideal way to proceed, though I imagine that many of you would consider twenty straight minutes of programming to be a mere moment in a long day of programming. I enjoyed doing it, and certainly it worked. So, no harm no foul, one might suggest. I think it was risky, but on the other hand it only risked twenty minutes – plus however long we might have debugged on it.

And it was the end of the session. So Chet typed in one more test, to process our actual picture of a shotgun blast:

   @Test
    public void about1500() {
        PatterningSheet sheet = new PatterningSheet(folder + "PB270011.bmp");
        List hitList = sheet.getHits();
        assertEquals(0, hitList.size());
    }

Our recollection was that Chet had counted about 1500 holes on the paper, so we expected this to get about 1500 Hits. To our surprise, it got 773. We broke for lunch, somewhat confused.

At and After Lunch

Mostly we discussed the fries at Buffalo Wildwings. I ordered the disc ones, well-done at the suggestion of our waitress, who we were trying to convince we were mystery shoppers. They were crunchy and pretty good.

We also discussed the program, and how it could be finding half the holes it should find. We imagined some different kinds of tests we could build, with odd patterns and so on. But we could imagine no way that the code we had written could possibly skip a gap and find something that it shouldn’t.

At home, I did a few experiments. I found an interesting area in the big file, that looks like this:

image

That looks like four Hits to me, three singles and a six-pixel one. (I wonder whether it looks like five hits to Chet, on the paper, that is, whether the big one has some white in the middle of the two right angle things, that the picture didn’t pick up.)

So I instrumented our code with some println statements, and searched the resulting text file for the coordinates of those pixels, which I knew from playing with the file in Paint and other tools. Sure enough, the code had found four Hits there, just as one would hope for.

Then I extracted a subset of the big picture and actually counted the pixels in it.

image

Note that the center bottom section, listed as 5, should clearly be 8. When I added up those numbers, I got the same number that my test found on that subset.

Biting the bullet, I counted the whole file:

image

I got 770, the computer gets 773. Close enough. I’m sure that the program is correctly computing what we set out to compute. There is some question whether that is what we should want, of course. Perhaps our definition of connected is too free, and we shouldn’t consider two pixels diagonally connected to be connected. Or maybe Chet just needs a better camera with lots more pixels. (The real purpose of this whole exercise.) In any case, I’m now convinced that the code is doing exactly what we set out to make it do.

Summing Up

We did add some code to Hit, but it was pretty simple, and it was required in order to make the PatterningSheet work. We didn’t write tests directly on Hit to support it. For documentation purposes, it perhaps needs to be there. For development purposes, it did not.

I’m not sure just what we should do for an “acceptance test” on all this. We could do a FitNesse test on the 773 file, but other than going through the motions, what would be the point? I’ll see whether Chet feels more conscientious about this when next we meet.

There has been plenty of thinking “behind the scenes” on this one, though there has been no code written. The fundamental shape of the code I wrote was clear in my mind before I started: get the candidates, test them and remove them from the picture. I hadn’t thought about the inner methods about wasOn() and wasZero(), but they are, I think, pretty obvious if you’re used to thinking about pixels. And I am.

This reminds me of the earlier discussion and email about whether grubbing around in the bits was a good idea. I’m not really sure – certainly the Raster object is a useful one that I’m glad we found. But I do feel that I’m getting the benefit of lots of general experience in doing graphics, acquired over the years. I’ll be interested to hear from readers, especially those without such experience, regarding whether this code could have just flowed out of their fingers as it did out of mine. And, of course, any other comments will be welcome as well.

The code, which I’ll include below, is not yet pretty. We have gotten to “make it work”, but not to “make it right” at this point. After all, we only had a couple of hours. Today we’re taking the wives to lunch in Ann Arbor. Tomorrow, we’ll do some more code. Stay tuned.

public class PatterningSheet {
    private String fileName;
    private WritableRaster farian;
    private int[] pixelArray = null;
    private int[] whiteArray = new int[] {1};

    public PatterningSheet(String fileName) {
        this.fileName = fileName;
    }

    public List getHits() {
        ArrayList hits = new ArrayList();
        farian = raster(fileName);
        int width = farian.getWidth();
        int height = farian.getHeight();
        int yOffset = height / 2;
        int xOffset = width / 2;    

        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if ((farian.getPixel(x, y, pixelArray)[0]) == 0)
                    hits.add(makeHit(farian, yOffset, xOffset, y, x));
            }
        }
        return hits;
    }   

    private Hit makeHit(WritableRaster farian, int offset, int offset2, int y, int x) {
        Hit hit = new Hit();
        hit.addPoint(new Point(x,y));
        List<Point> points = adjacentPoints(x,y);
        for (Point point: points)
            hit.addPoint(point);
        return hit;
    }

    private List<Point> adjacentPoints(int x, int y) {
        ArrayList<Point> points = new ArrayList<Point>();
        points.add(new Point(x,y));
        for (int i = 0; i < points.size(); i++) {
            for (Point point: candidates(points.get(i))) {
                if (wasOn(point)) {
                    points.add(point);
                }
            }
        }
        return points;
    }

    private boolean wasOn(Point point) {
        int x = point.getX();
        int y = point.getY();
        if (x < 0 || y < 0) return false;
        if (x >= farian.getWidth() || y >= farian.getHeight()) return false;
        return wasZero(x,y);
    }

    private boolean wasZero(int x, int y) {
        int wasZero = farian.getPixel(x, y, pixelArray)[0];
        farian.setPixel(x, y, whiteArray);
        return wasZero == 0;
    }

    private List<Point> candidates(Point point) {
        List<Point> candidates = new ArrayList<Point>();
        int x = point.getX();
        int y = point.getY();
        for (int newX = x-1; newX <= x+1; newX++)
            for (int newY = y-1; newY <= y+1; newY++) {
                if ( newX != x || newY != y)
                candidates.add(new Point(newX, newY));
            }
        return candidates;
    }

    private WritableRaster raster(String fileName) {
        BufferedImage img = null;
        try {
            img = ImageIO.read(new File(fileName));
        } catch (IOException e) {
        }

        WritableRaster raster = (WritableRaster) img.getData();
        return raster;
    }
}