Java image analysis - counting vertical lines

I need a little help on an image analysis algorithm in Java. I basically have images like this:

So, as you might guessed, I need to count the lines.

What approach do you think would be best?

T开发者_Go百科hanks, Smaug

A simple segmentation algorithm can help you out. Heres how the algorithm works:

• scan pixels from left to right and record the position of the first black (whatever the color of your line is) pixel.
• carry on this process unless you find one whole scan when you don't find the black pixel. Record this position as well.
• We are just interested in the Y positions here. Now using this Y position segment the image horizontally.
• Now we are going to do the same process but this time we are going to scan from top to bottom (one column at a time) in the segment we just created.
• This time we are interested in X positions.
• So in the end we get every lines extents or you can say a bounding box for every line.
• The total count of these bounding boxes is the number of lines.

You can do many optimizations in the algorithm according to your needs.

package ac.essex.ooechs.imaging.commons.edge.hough; 

import java.awt.image.BufferedImage; 
import java.awt.*; 
import java.util.Vector; 
import java.io.File; 

/** 
 * <p/> 
 * Java Implementation of the Hough Transform.<br /> 
 * Used for finding straight lines in an image.<br /> 
 * by Olly Oechsle 
 * </p> 
 * <p/> 
 * Note: This class is based on original code from:<br /> 
 * <a href="http://homepages.inf.ed.ac.uk/rbf/HIPR2/hough.htm">http://homepages.inf.ed.ac.uk/rbf/HIPR2/hough.htm</a> 
 * </p> 
 * <p/> 
 * If you represent a line as:<br /> 
 * x cos(theta) + y sin (theta) = r 
 * </p> 
 * <p/> 
 * ... and you know values of x and y, you can calculate all the values of r by going through 
 * all the possible values of theta. If you plot the values of r on a graph for every value of 
 * theta you get a sinusoidal curve. This is the Hough transformation. 
 * </p> 
 * <p/> 
 * The hough tranform works by looking at a number of such x,y coordinates, which are usually 
 * found by some kind of edge detection. Each of these coordinates is transformed into 
 * an r, theta curve. This curve is discretised so we actually only look at a certain discrete 
 * number of theta values. "Accumulator" cells in a hough array along this curve are incremented 
 * for X and Y coordinate. 
 * </p> 
 * <p/> 
 * The accumulator space is plotted rectangularly with theta on one axis and r on the other. 
 * Each point in the array represents an (r, theta) value which can be used to represent a line 
 * using the formula above. 
 * </p> 
 * <p/> 
 * Once all the points have been added should be full of curves. The algorithm then searches for 
 * local peaks in the array. The higher the peak the more values of x and y crossed along that curve, 
 * so high peaks give good indications of a line. 
 * </p> 
 * 
 * @author Olly Oechsle, University of Essex 
 */ 

public class HoughTransform extends Thread { 

    public static void main(String[] args) throws Exception { 
        String filename = "/home/ooechs/Desktop/vase.png"; 

        // load the file using Java's imageIO library 
        BufferedImage image = javax.imageio.ImageIO.read(new File(filename)); 

        // create a hough transform object with the right dimensions 
        HoughTransform h = new HoughTransform(image.getWidth(), image.getHeight()); 

        // add the points from the image (or call the addPoint method separately if your points are not in an image 
        h.addPoints(image); 

        // get the lines out 
        Vector<HoughLine> lines = h.getLines(30); 

        // draw the lines back onto the image 
        for (int j = 0; j < lines.size(); j++) { 
            HoughLine line = lines.elementAt(j); 
            line.draw(image, Color.RED.getRGB()); 
        } 
    } 

    // The size of the neighbourhood in which to search for other local maxima 
    final int neighbourhoodSize = 4; 

    // How many discrete values of theta shall we check? 
    final int maxTheta = 180; 

    // Using maxTheta, work out the step 
    final double thetaStep = Math.PI / maxTheta; 

    // the width and height of the image 
    protected int width, height; 

    // the hough array 
    protected int[][] houghArray; 

    // the coordinates of the centre of the image 
    protected float centerX, centerY; 

    // the height of the hough array 
    protected int houghHeight; 

    // double the hough height (allows for negative numbers) 
    protected int doubleHeight; 

    // the number of points that have been added 
    protected int numPoints; 

    // cache of values of sin and cos for different theta values. Has a significant performance improvement. 
    private double[] sinCache; 
    private double[] cosCache; 

    /** 
     * Initialises the hough transform. The dimensions of the input image are needed 
     * in order to initialise the hough array. 
     * 
     * @param width  The width of the input image 
     * @param height The height of the input image 
     */ 
    public HoughTransform(int width, int height) { 

        this.width = width; 
        this.height = height; 

        initialise(); 

    } 

    /** 
     * Initialises the hough array. Called by the constructor so you don't need to call it 
     * yourself, however you can use it to reset the transform if you want to plug in another 
     * image (although that image must have the same width and height) 
     */ 
    public void initialise() { 

        // Calculate the maximum height the hough array needs to have 
        houghHeight = (int) (Math.sqrt(2) * Math.max(height, width)) / 2; 

        // Double the height of the hough array to cope with negative r values 
        doubleHeight = 2 * houghHeight; 

        // Create the hough array 
        houghArray = new int[maxTheta][doubleHeight]; 

        // Find edge points and vote in array 
        centerX = width / 2; 
        centerY = height / 2; 

        // Count how many points there are 
        numPoints = 0; 

        // cache the values of sin and cos for faster processing 
        sinCache = new double[maxTheta]; 
        cosCache = sinCache.clone(); 
        for (int t = 0; t < maxTheta; t++) { 
            double realTheta = t * thetaStep; 
            sinCache[t] = Math.sin(realTheta); 
            cosCache[t] = Math.cos(realTheta); 
        } 
    } 

    /** 
     * Adds points from an image. The image is assumed to be greyscale black and white, so all pixels that are 
     * not black are counted as edges. The image should have the same dimensions as the one passed to the constructor. 
     */ 
    public void addPoints(BufferedImage image) { 

        // Now find edge points and update the hough array 
        for (int x = 0; x < image.getWidth(); x++) { 
            for (int y = 0; y < image.getHeight(); y++) { 
                // Find non-black pixels 
                if ((image.getRGB(x, y) & 0x000000ff) != 0) { 
                    addPoint(x, y); 
                } 
            } 
        } 
    } 

    /** 
     * Adds a single point to the hough transform. You can use this method directly 
     * if your data isn't represented as a buffered image. 
     */ 
    public void addPoint(int x, int y) { 

        // Go through each value of theta 
        for (int t = 0; t < maxTheta; t++) { 

            //Work out the r values for each theta step 
            int r = (int) (((x - centerX) * cosCache[t]) + ((y - centerY) * sinCache[t])); 

            // this copes with negative values of r 
            r += houghHeight; 

            if (r < 0 || r >= doubleHeight) continue; 

            // Increment the hough array 
            houghArray[t][r]++; 

        } 

        numPoints++; 
    } 

    /** 
     * Once points have been added in some way this method extracts the lines and returns them as a Vector 
     * of HoughLine objects, which can be used to draw on the 
     * 
     * @param percentageThreshold The percentage threshold above which lines are determined from the hough array 
     */ 
    public Vector<HoughLine> getLines(int threshold) { 

        // Initialise the vector of lines that we'll return 
        Vector<HoughLine> lines = new Vector<HoughLine>(20); 

        // Only proceed if the hough array is not empty 
        if (numPoints == 0) return lines; 

        // Search for local peaks above threshold to draw 
        for (int t = 0; t < maxTheta; t++) { 
            loop: 
            for (int r = neighbourhoodSize; r < doubleHeight - neighbourhoodSize; r++) { 

                // Only consider points above threshold 
                if (houghArray[t][r] > threshold) { 

                    int peak = houghArray[t][r]; 

                    // Check that this peak is indeed the local maxima 
                    for (int dx = -neighbourhoodSize; dx <= neighbourhoodSize; dx++) { 
                        for (int dy = -neighbourhoodSize; dy <= neighbourhoodSize; dy++) { 
                            int dt = t + dx; 
                            int dr = r + dy; 
                            if (dt < 0) dt = dt + maxTheta; 
                            else if (dt >= maxTheta) dt = dt - maxTheta; 
                            if (houghArray[dt][dr] > peak) { 
                                // found a bigger point nearby, skip 
                                continue loop; 
                            } 
                        } 
                    } 

                    // calculate the true value of theta 
                    double theta = t * thetaStep; 

                    // add the line to the vector 
                    lines.add(new HoughLine(theta, r)); 

                } 
            } 
        } 

        return lines; 
    } 

    /** 
     * Gets the highest value in the hough array 
     */ 
    public int getHighestValue() { 
        int max = 0; 
        for (int t = 0; t < maxTheta; t++) { 
            for (int r = 0; r < doubleHeight; r++) { 
                if (houghArray[t][r] > max) { 
                    max = houghArray[t][r]; 
                } 
            } 
        } 
        return max; 
    } 

    /** 
     * Gets the hough array as an image, in case you want to have a look at it. 
     */ 
    public BufferedImage getHoughArrayImage() { 
        int max = getHighestValue(); 
        BufferedImage image = new BufferedImage(maxTheta, doubleHeight, BufferedImage.TYPE_INT_ARGB); 
        for (int t = 0; t < maxTheta; t++) { 
            for (int r = 0; r < doubleHeight; r++) { 
                double value = 255 * ((double) houghArray[t][r]) / max; 
                int v = 255 - (int) value; 
                int c = new Color(v, v, v).getRGB(); 
                image.setRGB(t, r, c); 
            } 
        } 
        return image; 
    } 

}

Source: http://vase.essex.ac.uk/software/HoughTransform/HoughTransform.java.html

I've implemented a simple solution (must be improved) using Marvin Framework that finds the vertical lines start and end points and prints the total number of lines found.

Approach:

1. Binarize the image using a given threshold.
2. For each pixel, if it is black (solid), try to find a vertical line
3. Save the x,y, of the start and end points
4. The line has a minimum lenght? It is an acceptable line!
5. Print the start point in red and the end point in green.

The output image is shown below:

The programs output:

Vertical line fount at: (74,9,70,33)
Vertical line fount at: (113,9,109,31)
Vertical line fount at: (80,10,76,32)
Vertical line fount at: (137,11,133,33)
Vertical line fount at: (163,11,159,33)
Vertical line fount at: (184,11,180,33)
Vertical line fount at: (203,11,199,33)
Vertical line fount at: (228,11,224,33)
Vertical line fount at: (248,11,244,33)
Vertical line fount at: (52,12,50,33)
Vertical line fount at: (145,13,141,35)
Vertical line fount at: (173,13,169,35)
Vertical line fount at: (211,13,207,35)
Vertical line fount at: (94,14,90,36)
Vertical line fount at: (238,14,236,35)
Vertical line fount at: (130,16,128,37)
Vertical line fount at: (195,16,193,37)
Vertical lines total: 17

Finally, the source code:

import java.awt.Color;
import java.awt.Point;
import marvin.image.MarvinImage;
import marvin.io.MarvinImageIO;
import marvin.plugin.MarvinImagePlugin;
import marvin.util.MarvinPluginLoader;

public class VerticalLineCounter {

    private MarvinImagePlugin threshold = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.color.thresholding");

    public VerticalLineCounter(){
        // Binarize
        MarvinImage image = MarvinImageIO.loadImage("./res/lines.jpg");
        MarvinImage binImage = image.clone();
        threshold.setAttribute("threshold", 127);
        threshold.process(image, binImage);

        // Find lines and save an output image
        MarvinImage imageOut = findVerticalLines(binImage, image);
        MarvinImageIO.saveImage(imageOut, "./res/lines_out.png");
    }

    private MarvinImage findVerticalLines(MarvinImage binImage, MarvinImage originalImage){
        MarvinImage imageOut = originalImage.clone();
        boolean[][] processedPixels = new boolean[binImage.getWidth()][binImage.getHeight()];
        int color;
        Point endPoint;
        int totalLines=0;
        for(int y=0; y<binImage.getHeight(); y++){
            for(int x=0; x<binImage.getWidth(); x++){
                if(!processedPixels[x][y]){
                    color = binImage.getIntColor(x, y);

                    // Black?
                    if(color == 0xFF000000){
                        endPoint = getEndOfLine(x,y,binImage,processedPixels);

                        // Line lenght threshold
                        if(endPoint.x - x > 5 || endPoint.y - y > 5){
                            imageOut.fillRect(x-2, y-2, 5, 5, Color.red);
                            imageOut.fillRect(endPoint.x-2, endPoint.y-2, 5, 5, Color.green);
                            totalLines++;
                            System.out.println("Vertical line fount at: ("+x+","+y+","+endPoint.x+","+endPoint.y+")");
                        }
                    }
                }
                processedPixels[x][y] = true;
            }
        }
        System.out.println("Vertical lines total: "+totalLines);
        return imageOut;
    }

    private Point getEndOfLine(int x, int y, MarvinImage image, boolean[][] processedPixels){
        int xC=x;
        int cY=y;
        while(true){
            processedPixels[xC][cY] = true;
            processedPixels[xC-1][cY] = true;
            processedPixels[xC-2][cY] = true;
            processedPixels[xC-3][cY] = true;
            processedPixels[xC+1][cY] = true;
            processedPixels[xC+2][cY] = true;
            processedPixels[xC+3][cY] = true;

            if(getSafeIntColor(xC,cY,image)  < 0xFF000000){
                // nothing
            }
            else if(getSafeIntColor(xC-1,cY,image) == 0xFF000000){
                xC = xC-2;
            }
            else if(getSafeIntColor(xC-2,cY,image) == 0xFF000000){
                xC = xC-3;
            }
            else if(getSafeIntColor(xC+1,cY,image)  == 0xFF000000){ 
                xC = xC+2;
            }
            else if(getSafeIntColor(xC+2,cY,image)  == 0xFF000000){ 
                xC = xC+3;
            }
            else{
                return new Point(xC, cY);
            }
            cY++;
        }
    }
    private int getSafeIntColor(int x, int y, MarvinImage image){
        if(x >= 0 && x < image.getWidth() && y >= 0 && y < image.getHeight()){
            return image.getIntColor(x, y);
        }
        return -1;
    }
    public static void main(String args[]){
        new VerticalLineCounter();
        System.exit(0);
    }
}

It depends on how much they look like that.

1. Bring the image to 1-bit (black and white) in a way that preserves the lines and brings the background to pure white
2. Perhaps do simple cleanup like speck removal (remove any small black components).

Then,

1. Find a black pixel
2. Use flood-fill algorithms to find its extent
3. See if the shape meets the criteria for being a line (lineCount++ if so)
4. remove it
5. Repeat this until there are no black pixels

A lot depends on how good you do #3, some ideas

1. Use Hough just on this section to check that you have one line, and that it is vertical(ish)
2. (after #1) rotate it to the vertical and check its width/height ratio