import java.awt.*;
import java.awt.image.*;
import java.applet.*;
import java.net.*;
import java.io.*;
import java.lang.Math;
import java.util.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.JApplet;
import javax.imageio.*;
import javax.swing.event.*;

public class opticalFlow {

	static int[] input1;
	static int[] input2;	
	static int[] output;
	int progress;
	int width;
	int height;
	int window;
	int displacement;

	public void opticalFlow() {
			progress=0;
		}

		public void init(int[] input1, int[] input2, int widthIn, int heightIn, int window, int displacement) {
			width=widthIn;
			height=heightIn;
			this.input1 = input1;
			this.input2 = input2;			
			output = new int[width*height];
			this.window = window;
			this.displacement = displacement;

		}
		public int[] process() {
			progress=0;

			// arrays to store the vectors
			int[] u = new int[width * height];
			int[] v = new int[width * height];

			// loop over the image
			for(int x1 = (window + displacement + 1); x1 < (width - window - displacement); x1++) {
				progress++;
				for(int y1 = (window + displacement + 1); y1 < (height - window - displacement); y1++) {

					int min = 9999999;
					int dx = 0;
					int dy = 0;


					// loop through the displacement area
					for(int x2 = (x1 - displacement); x2 < (x1 + displacement); x2++) {
						for(int y2 = (y1 - displacement); y2 < (y1 + displacement); y2++) {

							int sum = 0;

							// loop over the window area - (2 * window) + 1
							for(int i = -window; i < window; i++) {
								for(int j = -window; j < window; j++) {
									// sum pixel intensity difference squared over the window area
									sum += (int)Math.pow((double)((input1[(x1 + i) + (y1 + j) * width]&0xff) - (input2[(x2 + i) + (y2 + j) * width]&0xff)), 2);
								}
							}
							if(sum < min) {
								min = sum;
								dx = x2 - x1;
								dy = y2 - y1;
							}
						}
					}
					// set velocity 
					u[x1 + y1 * width] = dx;
					v[x1 + y1 * width] = dy;

				}
			}
			progress = width;
			// we now have the vectors of the optical flow and need to construct a graph
			int val;
			int step = 5;
			for(int x = 0; x < width; x++) {
				for(int y = 0; y < height; y++) {
					if((x % step != 0 || y % step != 0) || u[x + y * width] == v[x + y * width]) {
						val = 255;
						output[x + y * width] = 0xff000000 | (int)val << 16 | (int)val << 8 | (int)val;
					}
					else {
						int size = Math.abs(u[x + y * width] -  v[x + y * width]);
						int xv = u[x + y * width];
						int yv = v[x + y * width];
						line(x, y, x + (xv * 2), y + (yv * 2));
					}
				}
			}
			return output;
		}
		public int getProgress() {
			return progress;
		}
		
		public void line(int x0, int y0, int x1, int y1)
	    {
	        if(x1 > width) x1 = width;
		if(x1 < 0) x1 = 0;
	        if(y1 > height) y1 = height;
		if(y1 < 0) y1 = 0;
		int dx = x1 - x0;
	        int dy = y1 - y0;
			int val = 0;
	        output[x0 + y0 * width] = 0xff000000 | (int)val << 16 | (int)val << 8 | (int)val;
	        if (Math.abs(dx) > Math.abs(dy)) {          // slope < 1
	            float m = (float) dy / (float) dx;      // compute slope
	            float b = y0 - m*x0;
	            dx = (dx < 0) ? -1 : 1;
	            while (x0 != x1) {
	                x0 += dx;
	                output[x0 + Math.round(m*x0 + b) * width] = 0xff000000 | (int)val << 16 | (int)val << 8 | (int)val;
					if(val < 250) val += 25;
	            }
	        } else
	        if (dy != 0) {                              // slope >= 1
	            float m = (float) dx / (float) dy;      // compute slope
	            float b = x0 - m*y0;
	            dy = (dy < 0) ? -1 : 1;
	            while (y0 != y1) {
	                y0 += dy;
	                output[Math.round(m*y0 + b) + y0 * width] = 0xff000000 | (int)val << 16 | (int)val << 8 | (int)val;
					if(val < 250) val += 25;
	            }
	        }
	    }

	}