Clumping Along

Discussion

Chet brought the real target sheet with the holes in it, and we looked at it to see whether our hit selection had done anything really odd. (We didn’t count the holes on the sheet again. I’ll try to talk him into doing that.) One thing we discovered was that an interesting area toward the bottom of the picture seems to be an artifact in the picture, not representing any holes in the sheet. This probably calls for a better camera, better picture-taking setup, and possibly even some image processing on the pictures.

However, we question whether all this will make any real difference in the quality of the analysis. After all, we’re talking about shot pellets fired out of the barrel of a gun, and the randomness from that probably swamps any details of the photo processing. A pixel’s variation in the pictures isn’t likely to make any difference to the results.

Code Merging

We actually did a little programming as well. Our purpose in writing the PatterningSheet class Tuesday was to isolate the Raster processing into one class, leaving Hit processing in the ShotPattern class. That amounted to removing a few methods from ShotPattern, creating a PatterningSheet in ShotPattern, and calling its getHits() method. We cleaned up a couple of names, and we converted ShotPattern’s raw List to a typed List of Hit. The result looks like this:

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

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

    public ShotPattern(String fileName) {
        PatterningSheet sheet = new PatterningSheet(fileName);
        hits = sheet.getHits();
    }

    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;
    }

}

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<Hit> getHits() {
        List<Hit> hits = new ArrayList<Hit>();
        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(yOffset, xOffset, y, x));
            }
        }
        return hits;
    }   

    private Hit makeHit(int yOffset, int xOffset, int y, int x) {
        Hit hit = new Hit(x,y);
        List<Point> additionalPoints = additionalPointsInThisHit(x,y);
        for (Point point: additionalPoints)
            hit.addPoint(point);
        hit.translateBMP(xOffset, yOffset);
        return hit;
    }

    private List<Point> additionalPointsInThisHit(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;
    }
}

Along the way, we tweaked Hit and Point a tiny bit, resulting in these:

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 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;
    }

    public void translateBMP(int xOffset, int yOffset) {
        for (Point point: points)
            point.translateBMP(xOffset, yOffset);
    }
}

public class Point {
    private int x;
    private int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public void translateBMP(int xOffset, int yOffset) {
        x = x - xOffset;
        y = - (y - yOffset); // negated because BMP is upside down.
    }

}

The big item here is translateBMP(), which is there to translate the hits so that 0,0 is in the center of the picture, and to invert the Y axis because BMP files are stored upside down. Equivalent code was in the old Hit processing in ShotPattern. Chet felt that centering in the middle of the paper was better because he might crop the pictures differently but would always be trying to keep the center in approximately the center of the picture.

My guess is that it won’t matter in the longer term, because we’ll have a center marker on the picture, representing the point of aim.

Our center of mass test on the big picture moved, which didn’t surprise us, since we are now clumping hits, and using the first pixel found in the clump as the clump’s location. We experimented with using the center of mass of each hit, and it had essentially no effect on the answer, so we took that code out and accepted the new result.

I expect that this is a bit controversial. The original center of mass was the center of all the pixels, treating each as weighing the same. Now we have some hits with just one pixel in them, and some with many. Surely the ones with many should count for more in the center of mass. Surely what we’re doing is somehow mathematically incorrect. I’m expecting cards and letters to come pouring in, although the holidays may keep the mail down a bit.

Nonetheless, we tried it both ways and found no reason to prefer the more complex calculation: it moves the center about a dozen pixels or less in the big picture. And there’s no reason to accept either one as “true”. As customer, Chet decided to stick with the simple implementation and made us rip out the more complex one. Works for me.

The Mailbox

Kelly Anderson

We’ve had a few interesting items in the mail box. On one of the lists, Kelly Anderson was leaping on me for counting the dots on that big picture, saying that some kind of coloring of the picture might have told me what I needed to know, and would have resulted in the ability to produce output in about the same amount of time as it took me to count things.

Well, I counted them while watching tv, and don’t think I could have coded output in the same amount of time with the same (very limited) application of brain power. More to the point, I don’t see how coloring that big bmp file would have told me what I wanted to know, namely how many dots are on it, and how many the program counted.

Someone posted a thought late on in the conversation that suggested that if we were breaking one “contiguous” clump into more than one Hit, coloring each Hit a different color might help us see whether that was working. I can see that, although with 700 hits in 3 megapixels, I’m not optimistic about the approach even then.

We will need output, and I look forward to working on it soon. But what I wanted to know yesterday was how many dots my eyes saw in that picture, and how many the computer saw. I felt that counting was the best way to do that, and still do.

Had there been 7000 dots in 30 megapixels … I’m not sure what I’d do to check that result. Perhaps just rely on smaller tests, or perhaps compute the value two different ways?

Kristoffer Roupe

Kristoffer inquired whether we had considered quadtrees, and asked:

Or are your first approaches just "getting in the dirt" with the problem to get a better feeling of it, and then when properly soaked with dirt, lifting your head and look around [to see] what others have to say about it?

Now in fact we do generally choose simpler solutions to begin with, and find that quite often, the simple solutions stick around much longer than one might expect. It’s not clear to me just what problem quadtrees would solve for us, though I believe they can be extended to arbitrary shape partitions on the graphical space. But since we’re basically going to just count the dots in any given space once and then draw our pictures … what would be the benefit?

One very valuable lesson that I learned from Kent Beck was that while it is great to have a deep bag of tricks – and after nearly a half-century of interesting programming, I have – it’s important always to reach only as far down in the bag as one must. I think that some programmers have a tendency to use the most powerful tool they can think of to solve problems, and I like to choose the least powerful tool that might work, instead.

If nothing else, readers will get a look at what happens when simpler approaches are taken, and my reading of our history in these articles is that good things generally happen.

Carl Manaster

Carl has actually written some code to address the problem we’re working on. He took a different approach, basically processing hit collections where we processed pixels. I’ll include his code here for your edification. I’ve looked it over but not reviewed it in detail. Here you go:

public class TouchableTest extends TestCase {
    public void testTouches() throws Exception {
        TouchableInteger a = new TouchableInteger(3);
        TouchableInteger b = new TouchableInteger(4);
        assertFalse(a.touches(a));
        assertTrue(a.touches(b));
    }

    public void testMakeSetOfAdjacentIntegers() throws Exception {
        Touchable[] values = makeTouchables(new Integer[] {1, 2, 3,    5,    7, 8});
        Set<TouchableSet> set = new TouchableGrouper(values).getSets();
        assertEquals(3, set.size());
        for (Touchable value : values)
            assertContainsExactlyOnce(set, value);
    }

    private Touchable[] makeTouchables(Integer[] integers) {
        Touchable[] result = new Touchable[integers.length];
        for (int i = 0; i < integers.length; ++i)
            result[i] = new TouchableInteger(integers[i]);
        return result;
    }

    public void testThereAreNoProblemsWithSelfComparisons() throws Exception {
        Touchable[] values = makeTouchables(new Integer[] {1, 2, 3, 4, 5, 6, 7, 8});
        Set<TouchableSet> set = new TouchableGrouper(values).getSets();
        assertEquals(1, set.size());
        for (Touchable value : values)
            assertContainsExactlyOnce(set, value);
    }

    private void assertContainsExactlyOnce(Set<TouchableSet> set2, Touchable value) {
        int count = 0;
        for (TouchableSet set : set2)
                if (set.contains(value))
                    count++;
        assertEquals(1, count);
    }

}

public interface Touchable {
    boolean touches(Touchable t);
}

public class TouchableInteger implements Touchable {
    private final int i;

    public TouchableInteger(int i)      {this.i = i;}

    public boolean touches(Touchable t) {
        if (!(t instanceof TouchableInteger))
            return false;
        TouchableInteger that = (TouchableInteger) t;
        return Math.abs(this.i - that.i) == 1;
    }

}

public class TouchableSet {
    private final HashSet<Touchable> set = new HashSet<Touchable>();

    public TouchableSet(Touchable t)            {add(t);}
    public void add(Touchable t)                {set.add(t);}
    public int size()                           {return set.size();}
    public boolean isEmpty()                    {return set.isEmpty();}
    public String toString()                    {return set.toString();}
    public boolean contains(Touchable t)        {return set.contains(t);}

    public void consume(TouchableSet that) {
        this.set.addAll(that.set);
        that.set.clear();
    }

    public boolean hasAnyAdjacentElements(TouchableSet that) {
        for (Touchable i : this.set)
            for (Touchable j : that.set)
                if (i.touches(j))
                    return true;
        return false;
    }

}

public class TouchableGrouper {
    private Set<TouchableSet> sets;

    public TouchableGrouper(Touchable[] touchables) {
        makeOneSetPerElement(touchables);
        consolidateAdjacentSets();
        discardEmpties();
    }

    public Set<TouchableSet> getSets() {return sets;}

    private void makeOneSetPerElement(Touchable[] touchables) {
        sets = new HashSet<TouchableSet>();
        for (Touchable touchable : touchables)
            sets.add(new TouchableSet(touchable));
    }

    private void consolidateAdjacentSets() {
        for (TouchableSet a : sets)
            for (TouchableSet b : sets)
                if (a != b && a.hasAnyAdjacentElements(b))
                    b.consume(a);
    }

    private void discardEmpties() {
        Set<TouchableSet> nonEmpties = new HashSet<TouchableSet>();
        for (TouchableSet set : sets)
            if (!set.isEmpty())
                nonEmpties.add(set);
        sets = nonEmpties;
    }

}

Summary So Far

The creation of the PatterningSheet went very smoothly Tuesday, and it plugged into ShotPattern as easily as one could have wished. The code is not yet as smooth as we like, nor has the process overall been as smooth as we might have liked. I think the simple approach has served us well, but we’ve been learning a bit more slowly and clumsily than I’m used to, not only in the infamous bowling game, which you’d think we’d be pretty good at, but also in other exercises like Sudoku. I think that most of our trouble is coming because we’re not sure either of the technology or the stories. Whatever the reasons, things feel a bit rough to me.

You’ll want to keep an eye on us to see how things go. Will we begin to cut too many corners, or will we keep our eye on the ball and keep things clean enough to serve? Will we succumb to the repeated calls to pull high tech solutions out of our bag of tricks, or will we cleave to the simple style for which we are justly, um, known? You’ll have to keep an eye on us to find out.

Tomorrow we expect to figure out a few stories, and perhaps some acceptance tests. I’m anxious to get to drawing some pictures, but we may not have much time for that. Next week is Christmas, so there may be a delay until there can be more pair programming. That means I might go off the rails all on my own.

Thanks for watching, and thanks for commenting!