package vnt;
/**
 * Endpoint_Prune.java - v1.0
 * Began: July 11, 2005
 * Last Updated: July 28, 2005 
 * 
 * Copyright (C) 2005 - Michael D. Miller - mdm162@truman.edu
 * Truman State University
 * 100 E. Normal
 * Kirksville, MO - 63501
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */

import ij.*;
import ij.gui.*;
import java.awt.*;
import java.awt.Color.*;
import ij.plugin.filter.PlugInFilter;
import ij.process.*;
import java.io.*;
import ij.io.*;
import java.lang.String.*;
import java.lang.Math.*;
import ij.plugin.filter.*;

import Coordinate.*;
import java.util.Stack;

/**
 * <p>Plug-in for ImageJ that takes a grayscale distance map skeleton
 * image and generates a pruned skeleton.</p>
 * 
 * <p>The pruning removes all endpoints shorter than a
 * particular length. Due to the need to accomodate multiple
 * zoom factors, this length is NOT hard coded.</p> 
 * 
 * @author Michael Miller - Truman State University
 * @version 1.0
 * @since 1.0
 */
public class Endpoint_Prune extends VascularNetworkToolkit implements PlugInFilter {

    /**
     * The longest length in which pruning will occur. Any length longer will not be pruned.
     */
    private int pruneLength;
    /**
     * If true, isolated objects will be pruned. This should generally be false (inhibited networks will be largely isolated structures). 
     */
    private boolean pruneIsolated; 
    /**
     * A copy of the pixel[][] array that remembers before traversals.
     */
    private int [][] backupPixel;

    /**
    * Specifies the preconditions for the plug-in.
    * If this method succeeds then run() is called.
    *
    * Pre: ImageJ is running and an 8-bit grayscale image is open. The plug-in was just activated.
    * <br />Post: Either an argument was processed, the image was not saved to a local folder, or the plug-in is cleared to run on the image.
    * @param arg Required by the interface. The argument list passed to the plug-in.
    * @param imp Required by the interface. The ImagePlus datastructure holding (among other things) information to grab path and filename.
    * @return If DONE is returned, ImageJ quits without run()'ing the plug-in. Otherwise, the plug-in signals to ImageJ that this plugin only handles 8-bit (256 grayscale) and will not change the original image.
    * @see #run
    */
    public int setup(String arg, ImagePlus ip) {
        if (arg.equals("about")) { 
            showAbout("Endpoint Prune","  * Inputs a skeleton and outputs a pruned image. All endpoints less than a particularly length are deleted. (Copyright 2005. Michael Miller mdm162@truman.edu)");
            return DONE; // exit without run()
        }

        // will only save if this succeeds
        getFileInformation(ip);
                    
        return DOES_8G+NO_CHANGES; // success, run()
    }

    /**
     * Receives a grayscale image (specifically a thinned distance map
     * skeletonization) and computes lengths of endpoints. 
     * 1) Parses the image for possible node locations.
     * 2) Identifies endpoints (node and their connected edge).
     * 3) Estimates the total length.
     * 4) Removes the end segment if the total length is less than or equal to a particular amount.
     * 
     * Note: An additional parameter decides if isolated points should be deleted. 
     *  
     * Pre: The image was cleared to run by the setup() method.
     * <br />Post: The image is processed by the distance map and ridge tracing routines. A new distance map skeleton image is drawn. 
     * @param bp Required by the interface. The access information to the original image.
     * @see #setup
     * @see #setPruneLength
     * @see #setPruneIsolated
     * @see #generatePruning
     */
    public void run(ImageProcessor bp){ 
        // get the width and height information
        getDimensions(bp);
        // set prune length
        setMaxLengthToPrune(3);
        // set isolated toggle
        setPruneIsolated(false);
        // load the distance-map skeleton into memory
        pixel = VascularNetworkToolkit.LoadImage(bp);
        backupPixel = new int[width][height];

        // perform pruning
        int count = 0;
        do {
            // keep pruning until we can prune no more!
            if (displayDebugText)
                System.out.println("Attempting to prune -- iteration: "+ count++);
        }while(!generatePruning());
        // display the result
        drawPrunedImage();
        // save the pruned skeleton image
        saveFile("pruned");
        return;
    }

    /**
     * Sets the longest length of endpoint segments which will be pruned.
     * 
     * Pre: This should be set before pruning is requested.
     * <br />Post: If no error occurs, the new prune length is set. 
     * @param length The desired maximal length of endpoint segments that will be pruned. All lengths equal to or less than this value will be pruned. Negative values are ignored and return an error.
     * @return Returns -1 on error. Otherwise returns the new prune length.
     * @see #pruneLength
     */
    public int setMaxLengthToPrune(int length) {
        if (length < 0) {
            return -1;
        }
        pruneLength = length;
        return pruneLength;
    }
    
    /**
     * This param is a toggle on whether or not an endpoint segment
     * should be deleted that isolated (degree 0, a component by itself).
     *
     * Pre: This should be set before pruning is requested.
     * <br />Post: The toggle is set based on the given input.
     * @param prune If true, then isolated components will be deleted. When false, isolated components will be preserved.
     * @see #pruneIsolated     
     */
    public void setPruneIsolated(boolean prune) {
        pruneIsolated = prune;
        if (displayDebugText) {
            if (pruneIsolated)
                System.out.println("Pruning will remove isolated points.");
            else
                System.out.println("Pruning will NOT remove isolated points.");
        }
    }

    /**
     * Copies the pixel[][] array onto the backupPixel[][] array.
     * 
     * @return Returns true if there were no problems. Returns false if no copying was performed.
     * Pre: Assumes both arrays exist and are of identical size. Assumes the width and height variables are initialized properly.
     * <br />Post: backupPixel[][] is overwritten by pixel[][]. 
     */
    private boolean createBackup() {
        if (pixel.length != backupPixel.length)
            return false;
        if ((width < 1) || (height < 1))
            return false;

        int x,y;
        for(y=0; y<height; y++) {
            for(x=0; x<width; x++) {
                backupPixel[x][y] = pixel[x][y]; 
            }
        }
        return true;
    }

    /**
     * Restores the pixel[][] array from the copied backupPixel[][] array.
     * 
     * @return Returns true if there were no problems. Returns false if no copying was performed.
     * Pre: Assumes both arrays exist and are of identical size. Assumes the width and height variables are initialized properly.
     * <br />Post: pixel[][] is restored from the previously copied backupPixel[][]. 
     */
    private boolean restoreBackup() {
        if (pixel.length != backupPixel.length)
            return false;
        if ((width < 1) || (height < 1))
            return false;

        int x,y;
        for(y=0; y<height; y++) {
            for(x=0; x<width; x++) {
                 pixel[x][y] = backupPixel[x][y]; 
            }
        }
        return true;
    }
    
    /**
     * Computes the pruned skeleton onto a newly created image.
     * (Ideally this method is meant to be called repeatedly until it returns true.)
     * 
     * Pre: The pixel data is loaded with the pruned, thinned distance map skeletonization.
     * <br />Post: A pruning is performed on the data in the pixel[] memory based on the pruneLength and pruneIsolated options.
     * @return Returns false if any modifications were made to the data. When no further pruning is performed, the method returns true. 
     * @see #setPruneLength
     * @see #setPruneIsolated
     */
    public boolean generatePruning() {      
        if ((width < 1) || (height < 1)) {
            return false;
        }

        int x=0, y=0, i=0, color=0, count=0, size=0, deleteCount=0, components=0;
        Stack searchStack = new Stack();
        Coordinate skeleton;
        
        int endPoints=0, branchPoints=0, isolatedPoints=0;
        
        // get a count of the number of potential nodes
        for(y=0; y<height; y++) {
            for(x=0; x<width; x++) {
                // only concerned about skeletal pixels
                if (pixel[x][y] != WHITE) {
                    skeleton = new Coordinate(x,y,pixel[x][y]);
                    components = getWhiteComponents(skeleton); 
                    // is this a potential candidate for pruning?
                    // this algorithm looks for 1 (endpoints) components
                    if (components == 0) {
                        isolatedPoints ++;
                    } else if (components == 1) {
                        // node!
                        endPoints ++;
                    } else if (components >= 3) {
                        branchPoints ++;
                    }
                }
            }
        }
        if (displayDebugText)
            System.out.println("Isolated: "+isolatedPoints+" -- End Points: "+endPoints+" -- Branch Points: "+branchPoints);
        count = endPoints;
        // create a datastructure that holds all nodes and information about them
        Coordinate [] centers = new Coordinate [count];
        // create a datastructure that will hold all the ones to be deleted
        Coordinate [] deleted = new Coordinate [count];
        // fill the array of potential nodes
        count = 0;
        for(y=0; y<height; y++) {
            for(x=0; x<width; x++) {
                // only concerned about skeletal pixels
                if (pixel[x][y] != WHITE) {
                    skeleton = new Coordinate(x,y,pixel[x][y]);
                    components = getWhiteComponents(skeleton); 
                    // is this a potential candidate for pruning?
                    // this algorithm looks for 1 (endpoints) components
                    if (components == 1) {
                        // node!
                        centers[count] = skeleton;
                        count++; 
                    }
                }
            }
        }

        // create a backup
        createBackup();
        
        // traverse the image and build deletion information
        // all the traversed pixels are turned black
        boolean neighborBranchPoint;
        boolean hitBranch;
        deleteCount = 0;
        for(i=0; i<count; i++) {

            hitBranch = false;
            size = 0;
            searchStack.clear();
            searchStack.push(centers[i]);
            while (!searchStack.isEmpty()) {
                skeleton = (Coordinate)searchStack.pop();
                x = skeleton.getX();
                y = skeleton.getY();
                // make sure we didn't already place this pixel
                color = getColor(x,y); 
                if (color != WHITE && color != BLACK) {
                    size ++;
                    // if we are next to a branch point, don't add more neighbors
                    // but if we aren't go ahead
                    neighborBranchPoint = isNeighborBranchingPoint(skeleton);
                    setColor(x, y, BLACK);
                    if (!neighborBranchPoint) {
                        // check the cardinal directions to add 8-connected
                        for (x=skeleton.getX()-1; x<=skeleton.getX()+1; x++) {
                            for (y=skeleton.getY()-1; y<=skeleton.getY()+1; y++) {
                                color = getColor(x,y);          
                                if (color != WHITE && color != BLACK) {
                                    searchStack.push(new Coordinate(x, y, color));
                                }
                            }
                        }
                    } else { // record that we hit a branch point
                        hitBranch = true;
                    }
                }
            }
            if (size > 0 && size <= pruneLength) {
                if ((!pruneIsolated && hitBranch) || pruneIsolated) {
                    // mark this for deletion, it was too short
                    deleted[deleteCount] = centers[i];
                    deleteCount ++;
                }
            }
        }

        // reload the backup into memory
        restoreBackup();
        
        // push all the delete targets onto the stack
        searchStack.clear();
        for(i=0; i<deleteCount; i++) {
            searchStack.push(deleted[i]);
        }
        // delete everything until we find branch points
        // all pixels to be deleted will be turned black
        while (!searchStack.isEmpty()) {
            skeleton = (Coordinate)searchStack.pop();
            x = skeleton.getX();
            y = skeleton.getY();
            // make sure we didn't already place this pixel
            color = getColor(x,y); 
            if (color != WHITE && color != BLACK) {
                neighborBranchPoint = isNeighborBranchingPoint(skeleton);
                setColor(x, y, BLACK);
                // erase (in the image) the 3x3 area around the found pixel
                // check the cardinal directions to add 8-connected
                if (!neighborBranchPoint) {
                    for (x=skeleton.getX()-1; x<=skeleton.getX()+1; x++) {
                        for (y=skeleton.getY()-1; y<=skeleton.getY()+1; y++) {
                            color = getColor(x,y);          
                            if (color != WHITE && color != BLACK) {
                                searchStack.push(new Coordinate(x, y, color));
                            }
                        }
                    }
                }
            }
        }
        
        // now actually delete all the black pixels
        for(y=0; y<height; y++) {
            for(x=0; x<width; x++) {
                 if (getColor(x,y) == BLACK) {
                     setColor(x,y,WHITE);
                 }
            }
        }
        
        if (deleteCount > 0)
            return false;
        // else, nothing was deleted
        return true;
    }   
    
    /**
     * Draws the pruned skeleton onto a newly created image.
     * 
     * Pre: The pruning operation has already been performed. The pixel data is loaded with the pruned, thinned distance map skeletonization.
     * <br />Post: A new image is created and displayed.
     * @see #setPruneLength
     * @see #setPruneIsolated
     * @see #generatePruning
     */
    public void drawPrunedImage() {
        int x=0, y=0;
        // draw a copy of the pre-pruned skeleton
        String title = "Pruned Skeletonization";
        ImagePlus imp = NewImage.createByteImage (title, width, height, 1, NewImage.FILL_WHITE);
        ImageProcessor nip = imp.getProcessor();

        for(y=0; y<height; y++) {
            for(x=0; x<width; x++) {
                nip.putPixel(x,y,pixel[x][y]);
            }
        }
        // show final image 
        IJ.wait(100);
        imp.show();
        IJ.selectWindow(title);
    }
}