• View
• Print
• Recent Changes
• Login

Blur is Butter

The key to cooking is salt and butter. The key to image processing is alpha and blur. The cameras we are using are noisy. Rouge pixels will always be popping up making your images look moth eaten and your tracking look twitchy. You can temper those rouge pixels with the pixels that surround it in space (blur) or in time (alpha).

• We know how do make a blur ourselves but using the processing's blur function will make neater code and is probably faster. Add something like this in your previous examples and see how much cleaner and smoother it seems.

        ...

video.read();

	video.filter(BLUR, 3);
	for (int row = 0; row < video.height; row++) {
        ...

You will also notice how much slower it is. To blur you go into a repeat loop at each pixel to consult the neighbors so it is very slow. In a previous example we looked for the average of all the qualifying pixels which is a kind of blur and later we will look at other cheaper ways to do it.

• You can also temper each pixel with its counterpart from previous frames. Each time a frame of video comes in lay it on top of another image (a buffer) using a level of alpha.

Find the Hidden Costs

Most of our applications want to work in realtime. With video we are already talking about visiting millions of pixels every second. With things like blurs and buffers, you are looking at repeat loops nested at every pixels. Before you go trying to make your code faster you should be sure what is costing you time. Quite often it is not what you think. For instance in Java quite often you can knock yourself out in analyzing the picture but painting to the screen takes forever. You can use a variable and a few lines of code to take the pulse of your project.

• First create a variable to keeping track of how long thing take. You might use a long instea of an int because Java gives you back the number of milliseconds since Jan 1, 1970 which is a lot of milliseconds. Processing gives you millis since the program started so an int will work.
  long elapsedTime;
• Start the stopwatch by recording the start time. Put this line right before the operation that you want to time.

        long startTime = millis();

• Get the ellapsed time with this line. Put this line right after the operation that you want to time.
  elapsedTime = millis() - startTime;
• Outputting this to the console will be messy so you might want to only print out when you ask.

         public void keyPressed() {
		 if (key == 't') {
			println("Elapsedtime " + elapsedTime);

		}

}

Clean up.

• You might run just run through the rect and throw out the small fry. This might be a means of ignoring rouge pixels. Notice we go through the list backwards for deleting. (It might really speed up your code if you don't make the object in the first place until it has reached a certain threshold of width).
  for (int j = newRects.size() - 1; j > -1; j--) {

		Rectangle newRect = (Rectangle) newRects.get(j);
		if (newRect.getHeight()*newRect.getWidth() < 100) newRects.remove(j); //if the area to small, loose it

}

• You might also consolidate rects that were close enough.
  public void consolidate(ArrayList<Rectangle> _shapes, int _consolidateReachX, int _consolidateReachY) {

		//check every combination of shapes for overlap 
		//make the repeat loop backwards so you delete off the bottom of the stack
		for (int i = _shapes.size() - 1; i > -1; i--) {
			//only check the ones up 
			Rectangle shape1 = _shapes.get(i);
			Rectangle inflatedShape1 = new Rectangle(shape1); //copy the existing box
			inflatedShape1.grow(_consolidateReachX, _consolidateReachY); //widen it's reach

			for (int j = i - 1; j > -1; j--) {
				Rectangle shape2 = _shapes.get(j);
				if (inflatedShape1.intersects(shape2) ){
					shape1.add(shape2);
					//System.out.println("Remove" + j);
					_shapes.remove(j);
					break;
				}
			}
		}

}

Containing Your Results

• The results of your tracking may just be two numbers, the center x and y of whatever you are tracking. Other times you will also need the width and height, for example you can guage the distance in the z direction based on the apparent width of an object. Still other times you will be looking for the the complete contour of the edge of an object. In any case you will need some data structure to hold the coordinates of all of these pixels. The main decision between the built in objects such as Point, Rectangle, and in Java or growing your own.
• If you are just keeping track of single point, simple int variables will suffice.
• Although width and height seems like just another two numbers, the rectangle object has many operations for things like finding overlap and for combining rectangles that would be a bit of work for you to create yourself. To create a an new Rectangle using the built-in class you would simply say:

     Rectangle myRect = new Rectangle(10,10,30,30);// rectangle with upperleft corner at 10, 10 and width 30, height 20

To create your own object you would need to create a class something like this:

     Box myBox = new Box(10,10,30,30);

But then you would be responsible for making a Box class to create box objects:

       public class Box {
		int leftMost , topMost , rightMost ,  bottomMost ; // sarts out top most
		Box(int _x, int _y, _width, _height) {
			leftMost = _x; 
			topMost = _y; 
			rightMost = _x + _width; 
			bottomMost = _y + _height; 
		}
	}

The Java Rectangles come with built-in functions for things like testing if a point is contained in a rectangle. For Java Rectangles you could simple say:

    if (myRect.contains(col,row))

But if you are rolling your own you would have to write the intersects function yourself:

	boolean contains(int _col, int _row) {
			// see if it is inside the area plus a little reach
			boolean inside = (_col >= leftMost - reach && _col <= rightMost + reach && _row >= topMost - reach && _row <= bottomMost + reach);
			// if it is inside see if the bounds next extending
			if (inside){
				if (_col <= leftMost) leftMost = _col;
				if (_col >= rightMost) rightMost = _col;
				if (_row >= bottomMost) bottomMost = _row;
				if (_row <= topMost) topMost = _row;
			}

			return inside;
		}

The payoff for rolling your own shapes comes if you want to record more information about each shape. For instance for persistence across frames you want to record the age of a shape or its last few positions. If your roll your own shape classes your code will be more portable to, for instance, J2ME (cellphones) which does not have the Rectangle or Point class. Once you are in the business of record all the points along an edge you might consider doing it yourself. The polygon object in Java is limiting, for instance you have to add each vertex in order, and it does not pay you back with a lot of functionality around finding intersections and combining shapes. For the edges you can just keep two arrays sized to the height of the screen. When you find a qualifying edge you add the x position to the array at the index of the y position.

public class Blob {

		int[][] endPoints;

		int leftMost;

		int rightMost;

		int topMost;

		int bottomMost;

		public Blob(int _height, int _width) {
			endPoints = new int[_height][2];
			leftMost = width;
			rightMost = 0;
			bottomMost = -1;
			topMost = height;

		}

		public int getArea() {
			if (bottomMost == -1) return 0;
			return (rightMost - leftMost) * (bottomMost - topMost);
		}

		void updateBounds(int _x, int _y) {

			if (_x > rightMost) rightMost = _x;
			if (_x < leftMost) leftMost = _x;
			if (_y < topMost) topMost = _y;
			if (_y > bottomMost) bottomMost = _y;
		}

		public void addLeft(int _x, int _y) {

			endPoints[_y][0] = _x;
			// if ( endPoints[_y][1] == 0) endPoints[_y][1] = _x;
			updateBounds(_x, _y);
		}

		public void addRight(int _x, int _y) {
			endPoints[_y][1] = _x;
			// if ( endPoints[_y][0] == 0) endPoints[_y][0] = _x;
			updateBounds(_x, _y);
		}

		public void add(Blob _b) {
			for (int i = Math.min(_b.topMost, topMost); i <= Math.max(_b.bottomMost, bottomMost); i++) {
				if (_b.endPoints[i][0] != 0) {
					if (_b.endPoints[i][0] < endPoints[i][0]) endPoints[i][0] = _b.endPoints[i][0];
				}
				if (_b.endPoints[i][1] > endPoints[i][1]) endPoints[i][1] = _b.endPoints[i][1];
			}
		}

		public void add(int _x, int _y) {
			int[] points = endPoints[_y];
			if (points[0] == 0 && points[1] == 0) {
				points[0] = _x;
				points[1] = _x;
			} else if (_x < points[0])
				points[0] = _x;
			else if (_x > points[1]) points[1] = _x;
			updateBounds(_x, _y);

		}

		public float closestDistance(Blob _otherBlob) {
			float heightThisBlob = bottomMost - topMost;

			float otherHeight = _otherBlob.bottomMost - _otherBlob.topMost;

			float smallestDistance = 30000;

			// sample 8 places in each polygon, compare that with 8 places in the other polygon
			for (float rowOfThisBlob = topMost; rowOfThisBlob <= bottomMost; rowOfThisBlob = rowOfThisBlob + heightThisBlob / 4) {
				// println("he" + otherHeight);
				int leftOfThisBlob = endPoints[(int) rowOfThisBlob][0];
				int rightOfThisBlob = endPoints[(int) rowOfThisBlob][1];
				if (leftOfThisBlob == 0 || rightOfThisBlob == 0) continue;
				for (float rowOfOtherBlob = _otherBlob.topMost; rowOfOtherBlob <= _otherBlob.bottomMost; rowOfOtherBlob = rowOfOtherBlob + otherHeight / 4) {
					int leftOfOtherBlob = _otherBlob.endPoints[(int) rowOfOtherBlob][0];
					int rightOfOtherBlob = _otherBlob.endPoints[(int) rowOfOtherBlob][1];
					if (leftOfOtherBlob == 0 || rightOfOtherBlob == 0) continue;

					float d = dist(leftOfThisBlob, rowOfThisBlob, leftOfOtherBlob, rowOfOtherBlob);
					if (d < smallestDistance) smallestDistance = d;
					d = dist(leftOfThisBlob, rowOfThisBlob, rightOfOtherBlob, rowOfOtherBlob);
					if (d < smallestDistance) smallestDistance = d;
					d = dist(rightOfThisBlob, rowOfThisBlob, leftOfOtherBlob, rowOfOtherBlob);
					if (d < smallestDistance) smallestDistance = d;
					d = dist(rightOfThisBlob, rowOfThisBlob, rightOfOtherBlob, rowOfOtherBlob);
					if (d < smallestDistance) smallestDistance = d;
				}
			}
			return smallestDistance;
		}

		public boolean contains(int _x, int _y) {
			int[] points = endPoints[_y];
			return (_x >= points[0] && _x <= points[1]);

		}

		public boolean test(int _x, int _y, PImage _img) {
			int offset = _y * _img.width + _x;
			// println(_y + " " + _x);
			int thisPixel = _img.pixels[offset];

			// test the pixel
			float r = red(thisPixel);
			float g = green(thisPixel);
			float b = blue(thisPixel);
			float closeness = dist(r, g, b, goalRed, goalGreen, goalBlue);
			return (closeness < threshold);
		}

		public void drawBlob() {

			if (bottomMost != -1) { // never found anything

				int lastX = -1;// endPoints[topMost][1];
				int lastY = -500;// topMost;
				int firstX = width;
				int firstY = -1;
				for (int row = topMost; row <= bottomMost; row++) {
					int xpos = endPoints[row][0];
					if (xpos != 0) {
						if (lastX == -1) {
							lastX = xpos;
							lastY = row;
							firstX = xpos;
							firstY = row;
							continue;
						}
						line(lastX, lastY, xpos, row);
						lastX = xpos;
						lastY = row;
					}
				}
				for (int row = bottomMost; row >= topMost; row--) {
					int xpos = endPoints[row][1];
					if (xpos != 0) {
						if (lastX == -1) {
							lastX = xpos;
							lastY = row;
							firstX = xpos;
							firstY = row;
							continue;
						}
						line(lastX, lastY, xpos, row);
						lastX = xpos;
						lastY = row;
					}
				}
				if (firstX != -1) line(lastX, lastY, firstX, firstY);

			}
		}
	}

Identity

When you are tracking multiple things you very often want to be able to tell them apart. The simplest method is to make each thing a separate color. The next easiest is to put a marker on each thing like a sort of bar code and try to read them. This isn't really easy but there are some great libraries for doing this for you. Sometime people think about having each thing emit a light and flash it in a distinctive sequence but that doesn't work that well for video frame rates (see light sensing diodes).

• Coninutity: It might be possible to maintain identity if you make the assumption that an item in one frame will be closest to the same item in the next frame. This is a pretty reasonable assumption and even better if you compare not to where the thing was but where it was moving to. This requires that you keep two lists, one for the new finds and a second, more eternal list of what you found before or what you expected to find.

     	                int[] distances = new int[expectedRects.size()*newRects.size()];
		  	int[][] pairings = new int[expectedRects.size()*newRects.size()][3]; //dist,expectedIndex,newIndex
			for (int i = 0; i < expectedRects.size(); i++) {
				Rectangle expectedRect = (Rectangle) expectedRects.get(i);
				float expectedX = expectedRect.x + expectedRect.width / 2;
				float expectedY = expectedRect.y + expectedRect.height /2;

				for (int j = 0; j < newRects.size(); j++) {
					int placeInArray = i*newRects.size() + j;
					Rectangle newRect = (Rectangle) newRects.get(j);
				       int dist = (int) (dist(expectedX, expectedY,(float) (newRect.x + newRect.width / 2), (float)(newRect.y + newRect.height / 2) ));
					distances[placeInArray] = dist;
					pairings[placeInArray] = new int[] {dist,i,j};

				}
			}

			// sort the distances
			Arrays.sort(distances);
			//keep track if these things have been spoken for already 
			boolean[] checkListForExpected = new boolean[expectedRects.size()];
			boolean[] checkListForNew = new boolean[newRects.size()];
			//keep a variable that knows if you you have found enough
			int found = 0;
			//go down the distances in order and find the pairing with the least distance
			for (int i = 0; i < distances.length; i++) {
				int closeOne = distances[i];
				for (int j = 0; j < pairings.length; j++){
					int[] thisPairing = pairings[j];
					int dist = thisPairing[0];
					int expectedIndex = thisPairing[1];
					int newIndex = thisPairing[2];
					//if this pairing has the distance you are after and it's parts are not spoken for
					if (dist == closeOne &&  checkListForNew[newIndex] == false && checkListForExpected[expectedIndex] == false) { 
                                              // not spoken for
						Rectangle expectedRect = (Rectangle) expectedRects.get(expectedIndex);
						Rectangle newRect = (Rectangle) newRects.get(newIndex);
						checkListForExpected[expectedIndex] = true; // mark this found as used
						checkListForNew[newIndex] = true;
						expectedRect.x = newRect.x;
						expectedRect.y = newRect.y;
						expectedRect.width = newRect.width;
						expectedRect.height = newRect.height;
						found++;

					}
					if (found >= newRects.size()) break;
				}
				if (found >= newRects.size()) break;
			}

Have High Expectations

• The way we have been going through and checking every pixel may not be necessary if you know what you are looking for. For instance if you are looking for someone's head you only really have to sample at something less than the width of their head and you will probably always hit one point in their head. Because you have saved so much time by not visiting every pixels, you can really knock yourself out once you hit a good one.
  for (int row = spacing; row < video.height; row = row + spacing) {

		for (int col = spacing; col < video.width; col = col + spacing) {

• Also once you have found the person's head you can start looking next time where you found the head. Chances are they have not moved that much in a 30th of a second and you will find it with the first check with any repeat loops

Become Outgoing

• If you get smart about only sampling the image at intervals, you will will want some way to find the edges of something if once you sampled in the middle of it. You could think of this sampling as planting seeds and you want to see if you can grow out from them.
• In this example you would radiate out in 8 spokes out from the seed.
  int[][] directions = { { 0, 1 },{ 1, 1 },{ 1, 0 },{1,-1}, { 0, -1 }, {-1,-1},{ -1, 0 },{-1,1} };
  for (int direction = 0; direction < directions.length; direction++) {

						// pull out the directions
						int[] thisDirection = directions[direction];
						// take a step in that direction
						int testx = col + thisDirection[0];
						int testy = row + +thisDirection[1];

						// as long you don't go out of bounds of your video go in a
						// direction
						while (videoBounds.contains(testx, testy)) {

							int offset = testy*video.width + testx;

							//pixels[offset]  = myColor;
							// test the pixel
							int thisPixel = video.pixels[offset];
							//for debugging show that you tested the pixel
							video.pixels[offset] =0xff00ff00; //debugColor;
							float r = red(thisPixel);
							float g = green(thisPixel);
							float b = blue(thisPixel);
							float closeness = dist(r, g, b, goalRed, goalGreen, goalBlue);
							if (closeness > threshold) {// does not qualify
								break; // stop going in this direction
							}

							// take a step in this direction
							testx = testx + thisDirection[0];
							testy = testy + +thisDirection[1];
						}
						// add as far as you got in this direction to the rect
						thisRect.add(testx, testy);

					}

• In this example you would scan out horizontally:
  ArrayList myPolys = new ArrayList(); // make an empty list of rects

			fill(255, 0, 0);

			int debugColor = color(0, 0, 255);
			Rectangle videoBounds = new Rectangle(0, 0, video.width - 1, video.height - 1);
			for (int row = spacing; row < video.height; row = row + spacing) {
				for (int col = spacing; col < video.width; col = col + spacing) {
					// check to see if this point is already spoken for in another
					// rect
					boolean thisPointInsideExistingBlob = false;
					for (int i = 0; i < myPolys.size(); i++) {
						Polygon thisPoly = (Polygon) myPolys.get(i);
						if (thisPoly.contains(col, row)) {
							thisPointInsideExistingBlob = true;
							break;
						}
					}


					// if already in a another skip this iteration of the loop
					if (thisPointInsideExistingBlob)
						continue;

					//int[][] dirs = { { -1, 1 }, { 1, 1 }, { -1, -1 } }; // goes in quadrants starting with the upper left, the whole right side, and then the lower left, this worder is better for filling polygons.

					int[][] dirs = { { -1, -1 }, { 1, 1 }, { -1, -1 } }; // goes in quadrants starting with the upper left, the whole right side, and then the lower left, this worder is better for filling polygons.
					//Rectangle[] quadrantbounds = { new Rectangle(col,0,width-col,row),new Rectangle(col,row,width-col,height-row),new Rectangle(0,row,col,height-row), new Rectangle(0,0,col,row)};

					// make a hypothetical Polygon
					Polygon thisPoly = new Polygon();


					int testy = row;
					for (int direction = 0; direction < dirs.length; direction++) {
						// pull out the directions
						int[] thisDirection = dirs[direction];

						int testx = col; // reset back to the center x, repeats middle pixel but that is good so that know you will double back as far as you got away from the middle

						while (videoBounds.contains(testx, testy)) {

							// as long you don't go out of bounds of your video go in a
							// up or down
							int goodInThisLine = 0;
							while (videoBounds.contains(testx, testy)) {
								// as long you don't go out of bounds of your video go in a
								// side to side
								int offset = testy * video.width + testx;

								int thisPixel = video.pixels[offset];
								// for debugging show that you tested the pixel

								// test the pixel
								pixels[offset] = debugColor;
								float r = red(thisPixel);
								float g = green(thisPixel);
								float b = blue(thisPixel);
								float closeness = dist(r, g, b, goalRed, goalGreen, goalBlue);
								if (closeness < threshold) {// good one
									goodInThisLine++;
								} else {
									break; //bad one
								}

								testx = testx + thisDirection[0]; //increment x
							}
							// add as far as you got in this direction to the rect
							if (goodInThisLine == 0)
								break;
							testx = col + thisDirection[0]; // snap back to center
							testy = testy + thisDirection[1]; // take a step vertically in this direction
							thisPoly.addPoint(testx, testy);
						}

						if (direction == 1 && testy < row) testy = row ; //bring it back down to where it started
					}

Give a Few, Take a Few

• As you are radiating or scanning out you might not give up after one bad pixel. You might consider checking the next and even the next in case that was just a rough pixel or a bit of dirt. This is much cheaper than blurring.