algorithmlp.java

完整的模式识别库

/**
 * AlgorithmLP.java v6.0 Last Edited by: Ryan Irwin 05/23/2005
 * Nishant Aggarwal, Jun-Won Suh Created: 12/15/04
 *
 * Description: Linear Prediction algorithm. Determines the estimate of 
 * the data points based on the points given by the user. 
 * The appraoch is data interpolation [ based on cubic interpolation ],
 * Autocorrelation coefficients and Linear Predictor Coefficients [based
 * on Levinson Durbin Algorithm]
 */


//----------------------
// import java packages
//----------------------
import java.util.*;
import java.awt.*;

 
import java.awt.Graphics;
import javax.swing.JApplet; // import class Algorithm

public class AlgorithmLP extends Algorithm
{

    //-----------------------------------------------------------------
    //
    // static data members
    //
    //-----------------------------------------------------------------
    int lporder;
    int iporder;
    int scale;

    //-----------------------------------------------------------------
    //
    // primitive data members
    //
    //-----------------------------------------------------------------
    int output_canvas_d[][];   

    //-----------------------------------------------------------------
    //
    // instance data members
    //
    //-----------------------------------------------------------------
    String algo_id = "AlgorithmLP"; 
    Vector<MyPoint> support_vectors_d;
    Vector<MyPoint> decision_regions_d;

    // for original data
    //
    Vector<MyPoint> set1_d = new Vector<MyPoint>(40, 20);
    Vector<MyPoint> set2_d = new Vector<MyPoint>(40, 20);
    Vector<MyPoint> set3_d = new Vector<MyPoint>(40, 20);
    Vector<MyPoint> set4_d = new Vector<MyPoint>(40, 20);

    // for interpolation function
    //
    Vector<MyPoint> iset1 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> iset2 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> iset3 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> iset4 = new Vector<MyPoint>(40, 20); 

    // vector for mean-subtracted [zero-mean] data
    //
    Vector<MyPoint> mset1 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> mset2 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> mset3 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> mset4 = new Vector<MyPoint>(40, 20); 

    // for display purpose
    //
    Vector<MyPoint> display_set1 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> display_set2 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> display_set3 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> display_set4 = new Vector<MyPoint>(40, 20); 

    // to store autoCorrelation coefficient
   //
    double auto_co_1[];
    double auto_co_2[];
    double auto_co_3[];
    double auto_co_4[];

    // to store the average values for each class
    //
    double average1;
    double average2;
    double average3;
    double average4;

    // to store LP coefficient
    //
    double final_lpc_1[]; 
    double final_lpc_2[];
    double final_lpc_3[];
    double final_lpc_4[];

    // to store residual energy 
    //
    double estimate_err_1 = 0;	
    double estimate_err_2 = 0;	
    double estimate_err_3 = 0;
    double estimate_err_4 = 0; 

    // to store actual error energy
    //
    double actual_err_1 = 0;
    double actual_err_2 = 0;
    double actual_err_3 = 0;
    double actual_err_4 = 0;


    // to store the reflection coefficients
    //
    double ref_coeff_1[];
    double ref_coeff_2[];
    double ref_coeff_3[]; 
    double ref_coeff_4[];

    // to store the final results
    //
    Vector<MyPoint> y_estimate1 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> y_estimate2 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> y_estimate3 = new Vector<MyPoint>(40, 20); 
    Vector<MyPoint> y_estimate4 = new Vector<MyPoint>(40, 20); 

    //---------------------------------------------------------------
    //
    // class methods
    //
    //---------------------------------------------------------------


    /**
     * 
     * Implements the initialize() method in the base class. Initializes
     * member data and prepares for execution of first step. This method
     * "resets" the algorithm.
     *
     * @return   returns true if sets of data are valid
     *
     */
    public boolean initialize()
    {
	DisplayArea disp_area_d = new DisplayArea();
	point_means_d           = new Vector<MyPoint>();
	decision_regions_d      = new Vector<MyPoint>();
	support_vectors_d       = new Vector<MyPoint>();
	description_d           = new Vector<String>();

	step_count  = 3;
	lporder    = Classify.main_menu_d.lporder;
	iporder    = Classify.main_menu_d.iporder;
	scale      = lporder * iporder;

	// Add the process description for the LP algorithm
	//
	if (description_d.size() == 0)
	{
	    String str = new String("   0.  Checking for the Data Validity.");
	    description_d.addElement(str);
	    
	    str = new String("   1.  Displaying the Input Data Points.");
	    description_d.addElement(str);
	    
	    str = new String("   2.  Computing LP Parameters.");
	    description_d.addElement(str);
	    
	    str = new String("   3.  Displaying the Linear Predicted Signal");
	    description_d.addElement(str);

	}

	// set the data points for this algorithm
	//
	//	set1_d = (Vector)data_points_d.dset1.clone();
	//	set2_d = (Vector)data_points_d.dset2.clone();
	//	set3_d = (Vector)data_points_d.dset3.clone();
	//	set4_d = (Vector)data_points_d.dset4.clone();
	//
	set1_d = data_points_d.dset1;
	set2_d = data_points_d.dset2;
	set3_d = data_points_d.dset3;
	set4_d = data_points_d.dset4;	

	int max1 = set2_d.size();
	if (set1_d.size() > set2_d.size())
	    max1 = set1_d.size();

	int max2 = set4_d.size();
	if (set3_d.size() > set4_d.size())
	    max2 = set3_d.size();
	else
	    max2 = set4_d.size();

	if (max2 > max1)
	    max1 = max2;

	if (max1 > scale)
	    scale = max1;

	step_index_d = 0;

	if((checkdata_LP(set1_d) == true) && (checkdata_LP(set2_d) == true) 
	   && (checkdata_LP(set3_d) == true) && (checkdata_LP(set4_d) == true))
	{
	    pro_box_d.appendMessage((String)description_d.get(step_index_d));
	    pro_box_d.appendMessage("         Data points valid");
	    return true;	
	}
	else
        {
	    pro_box_d.appendMessage("\n" + "Invalid data");
	    pro_box_d.appendMessage("Clear and enter valid data" + "\n");
	    return false;
	}
    }

    /**
    * 
    * Validates the class entered by user for Linear Prediction  
    *
    * @param    lp
    * @return   true if data is Vector lp is valid. It is invalid
    *           if the size of lp is 1 or any element is larger than the
    *           the previous element
    * 
    */
    public boolean checkdata_LP(Vector lp)
    {
	if ( lp.size() == 1) 
	    return false;
	else
	   for(int i = 0; i <= lp.size() - 1 ; i++ )
	       for(int j = i + 1; j <= lp.size() - 1 ; j++ )
		   // amplitudes should be in time progression
		   //
		   if ( (((MyPoint)lp.elementAt(i)).x == 
			 ((MyPoint)lp.elementAt(j)).x) || 
			(((MyPoint)lp.elementAt(i)).x > 
			 ((MyPoint)lp.elementAt(j)).x) )
		       return false;

	return true;
    }

    /**
     *
     * Implementation of the run function from the Runnable interface.
     * Determines what the current step is and calls the appropriate method.
     *
     */
    public void run()
    {
	if (step_index_d == 1)
	{
	    disableControl();
	    step1();
	    enableControl();
	}
	if (step_index_d == 2)
	{
	    disableControl();
	    step2();
	    enableControl(); 
	}
	if (step_index_d == 3)
	{
	    disableControl();
	    step3(); 
	    enableControl(); 
       }
	
	// exit gracefully
	//
	return;
    }
    
    /**
     *
     * Displays data sets from input box in output box, clears the data
     * points from the Vector fro input data, zero-mean data,
     * does interpolation, and then finds mean of the interpolated data
     * interpolates the zero-mean data, displays the result
     *
     * @return   True
     *
     */
    boolean step1()
    {
	// set up progress bar
	//
	pro_box_d.setProgressMin(0);
	pro_box_d.setProgressMax(1);
	pro_box_d.setProgressCurr(0);

	output_panel_d.disp_area_d.output_points_d.removeAllElements();
	output_panel_d.disp_area_d.type_d.removeAllElements();
	output_panel_d.disp_area_d.color_d.removeAllElements();
	
      	// Display original data
	// size of the point made four times bigger
	// 
       if(set1_d.size() > 0 )
       {
	   display_set1.removeAllElements();
	   iset1.removeAllElements();
	   mset1.removeAllElements();

	   interpol(set1_d, display_set1);
	   average1 = mean(display_set1, mset1);
	   interpol(mset1, iset1);

	   output_panel_d.addOutput(set1_d, (Classify.PTYPE_INPUT * 4), 
				    data_points_d.color_dset1);
       }

       if(set2_d.size() > 0 )
       {
	   display_set2.removeAllElements();
	   iset2.removeAllElements();  
	   mset2.removeAllElements();

	   interpol(set2_d, display_set2);
	   average2 = mean(display_set2, mset2);
	   interpol(mset2, iset2);   
	  
	   output_panel_d.addOutput(set2_d, (Classify.PTYPE_INPUT * 4), 
				    data_points_d.color_dset2);
       }
       
       if(set3_d.size() > 0 )
       {
	   display_set3.removeAllElements();
	   iset3.removeAllElements();
	   mset3.removeAllElements();

	   interpol(set3_d, display_set3);
	   average3 = mean(display_set3, mset3);
	   interpol(mset3, iset3);

	   output_panel_d.addOutput(set3_d, (Classify.PTYPE_INPUT * 4), 
				    data_points_d.color_dset3);
       }
       
       if(set4_d.size() > 0 )
       {	
	   display_set4.removeAllElements();
	   iset4.removeAllElements();
	   mset4.removeAllElements();

	   interpol(set4_d, display_set4);
	   average4 = mean(display_set4, mset4);
	   interpol(mset4, iset4);
   
	   output_panel_d.addOutput(set4_d, (Classify.PTYPE_INPUT * 4), 
				    data_points_d.color_dset4);
       }

	pro_box_d.setProgressCurr(1);
	output_panel_d.repaint();
	return true;
    }
 
    /**
     *
     * Calculates the interpolated points for the data inputs   
     *
     * @param  v  input data points
     * @param  iset  interpolated data points
     *
     */
    public void interpol(Vector<MyPoint> v , Vector<MyPoint> iset)
    {	
	double sample;
	double d ;
	MyPoint r = new MyPoint();	
	
	double[] y2 = new double[v.size()];  
	double[] y  = new double[v.size()];
	double[] x  = new double[v.size()];
       
       for (int k = 0; k < v.size(); k++)
       {
	   x[k] = ((MyPoint)v.elementAt(k)).x;
	   y[k] = ((MyPoint)v.elementAt(k)).y;
       }

       // Reference:
       // "Numerical Recipe in C", Cambridge University Press, pp 113-116
       
       // total time interval of the data points calculated
       //
       d = ((MyPoint)v.lastElement()).x - ((MyPoint)v.firstElement()).x ; 
       
       // time step calculation
       //
       sample = d / scale;
       spline(x, y, y2, v.size());
       
       // iset holds new data points - interpolated values
       // First value added 
       //
       iset.addElement(new MyPoint((MyPoint)v.firstElement()));
       
       // Increment to next Time value
       //
      	r.x = sample + ((MyPoint)v.firstElement()).x;

	while (r.x <=  ((MyPoint)v.lastElement()).x)
	{
	    for(int j = 1; j < v.size(); j++)
	    {
		// the New Interpolated amplitude will be calculated
		// for the two points within which the time intervals 
		// lies, Hence, the condition check
		//
		if((r.x <= ((MyPoint)v.elementAt(j)).x ) && 
		   (r.x >=  ((MyPoint)v.elementAt(j - 1)).x)) 
		{
		    r.y = 0 ;
		    splint ((MyPoint)v.elementAt(j - 1), 
			    (MyPoint)v.elementAt(j), r, y2, (j - 1));

		    // New value appended to the array
		    //
		    iset.addElement(new MyPoint(r));
		    break; 
		}
	    }	    
   	    r.x = r.x + sample;
	}
	// sometimes the last element of the user entered 
	// values is missed out hence the condition to 
	// cross-check and put it in
	//
	if (((MyPoint)iset.lastElement()).x != ((MyPoint)v.lastElement()).x )
	    iset.addElement( new MyPoint((MyPoint)v.lastElement()));
    }

    /**
     *
     * Actually interpolates the points
     *
     * @param x    array containing the x coordinates of datapoints
     * @param y    array containing the y coordinates of datapoints
     * @param y2   array containing the interpolated y coordinates
     * @param size the size of the array to be interpolated
     * 
     */
    public void spline (double[] x, double[] y, double[] y2, int size )
    { 
	double[] u = new double[size];
	double p; 
	double sig; 
	
	y2[0] = 0;
	u[0] = 0;
	 
	for( int i = 1; i < size - 1; i++ )
	{ 
	    sig = ( x[i] - x[i - 1] ) / ( x[i + 1] - x[i - 1] ) ;
	    p = sig * y2[i - 1] + 2 ;
	    y2[i] = ( sig - 1) / p ;
	    u[i] = ( y[i + 1] - y[i] ) / ( x[i + 1] - x[i] ) ;
	    u[i] = ( 6 * u[i] / ( x[i + 1] - x[i - 1] ) 
		     - sig * u[i - 1] ) / p ;
	}
	y2[size - 1] = 0 ;
	
	// This is the back substitution loop of the tridiagonal algorithm
	//
	for(int i = size - 2; i >= 0; i-- )     
	    y2[i] = y2[i] * y2[i + 1] + u[i] ;
    }

    /**
     * Interpolates for a point between the two known points
     * using Cubic Interpolation
     *
     * @param   u1 start point for the interpolation
     * @param   u2 end point for the interpolation
     * @param   r  returning point, basically the interpolated point
     * @param   y2 array used for reassigning of r
     * @param   i  the sample number
     *
     */
    public void splint ( MyPoint u1, MyPoint u2, MyPoint r, 
			 double[] y2, int i )
    {
	double h;
	double a;
	double b;
 
	h = u2.x - u1.x ;
	a = ( u2.x - r.x ) / h ;
	b = ( r.x - u1.x ) / h ;
	r.y = a * u1.y + b * u2.y + ((a * a * a - a) * y2[i] 
	                             + ( b * b * b - b ) * y2[i + 1] ) 
	                                                 * ( h * h ) / 6 ; 
    }


    /**
     *
     * Calculates the mean and the zero-mean data points  
     *
     * @param    v orginal datapoints
     * @param    mv zero mean datapoints 
     *
     * @return   The average in a double
     * 
     */
    public double mean(Vector<MyPoint> v, Vector<MyPoint> mv)
    {
        double average = 0;
	MyPoint p      = new MyPoint();

       for(int i = 0; i < v.size(); i++ )
	   average = average + ((MyPoint)v.elementAt(i)).y;
       average = average / v.size();
       
       for(int i = 0; i < v.size(); i++ )
       {
	   p.y = ((MyPoint)v.elementAt(i)).y - average;