Original js implementation of face detection

detector.js

// 
// 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.     
// 
// @Author Karthik Tharavaad 
//         [email protected]  


function draw_rect(r, my_canvas){
	var canvas_context = my_canvas.getContext("2d");  
	canvas_context.strokeRect( r.x, r.y, r.w, r.w ); 
}

function face_detect_one( canvas ){
	stats = get_img_stats(canvas); 
    console.log(stats.ii[1051]);
	return do_detect_greedy_big_to_small(stats.ii, stats.ii2, stats.width, stats.height);
}   

function face_detect_multi( canvas, progress_callback, result_callback ){
	stats = get_img_stats(canvas);      
	multiscale_detect(stats.ii, stats.ii2, stats.width, stats.height, progress_callback, result_callback );
}  


function get_img_stats(my_canvas){                    
	var canvas_context = my_canvas.getContext("2d");
	var image_width = my_canvas.width;
	var image_height = my_canvas.height;     
	var image_data = canvas_context.getImageData(0,0,image_width,image_height);
    iis =  compute_ii( image_data, image_width, image_height );
	return {width: image_width, height: image_height, ii: iis.ii, ii2: iis.ii2 };               
}



function compute_ii( image_data, image_width, image_height ){
	var ii_w = image_width+1;
	var ii_h = image_height+1;
	var ii = new Array( ii_w * ii_h );
	var ii2 = new Array( ii_w * ii_h );      
	                        
	for( var i=0; i<ii_w; i++ ){
		ii[i] = ii2[i] = 0;
	}                        
	                            
	for( var i=1; i<ii_w; i++ ){  
		ii[i*ii_w] = 0;       
		ii2[i*ii_w] = 0; 
		var rowsum = 0;
		var rowsum2 = 0;
		for( var j=1; j<ii_h; j++ ){
			var index = ((i-1)*4)*image_width + ((j-1)*4);  
			var red = image_data.data[index];
			var green = image_data.data[index+1];
			var blue = image_data.data[index+2];     
			var grey = ( 0.2989*red + 0.587*green + 0.114*blue )>>0;  // this is what matlab uses       
			rowsum += grey;
			rowsum2 += grey*grey;
			
			var ii_above = (i-1)*ii_w + j;        
			var ii_this = i*ii_w + j;
			
			ii[ii_this] = ii[ii_above] + rowsum;   
			ii2[ii_this] = ii2[ii_above] + rowsum2;        
		}               
	}
	return {ii: ii, ii2: ii2};
}       


function do_detect_greedy_big_to_small( ii, ii2, width, height ){               
	var s_w = width/20.0;
	var s_h = height/20.0;     
	var start_scale = s_h < s_w ? s_h : s_w;     
	var scale_update = 1 / 1.2;     
	for( var scale = start_scale; scale > 1; scale *= scale_update ){
		var w = (20*scale) >> 0;
		var endx = width - w - 1;
		var endy = height - w - 1;          
		var step = Math.max( scale, 2 ) >> 0;       
		var inv_area = 1 / (w*w);
		for( var y = 0; y < endy ; y += step ){
			for( var x = 0; x < endx ; x += step ){             
				var passed = detect_on_sub_image( x, y, scale, ii, ii2, w, width+1, inv_area);
				if( passed ) {
				  	return {x: x, y: y, w: w };   
				}                     
			} // end x             
		} // end y            
	}  // end scale           
	return null;
}       


function group_rects( ungrouped_rects ){
	var groups = new Array();
	for( var i=0; i<ungrouped_rects.length; i++ ){
		var to_be_grouped = ungrouped_rects[i];
		var was_added = false;
		for( var j=0; j<groups.length; j++ ){
			var group = groups[j];
			if( group_has_member(group, to_be_grouped ) ) {
				group.push( to_be_grouped );               
				was_added = true;
				break;
			}
		}
		
		if( ! was_added )  {
			var new_group = new Array();
			new_group.push( to_be_grouped );
			groups.push( new_group );
		} 
	}     
	
	var group_average_rects = new Array();
	for( var i=0; i<groups.length; i++ ){
		var group = groups[i];
		if( group.length < 2 ) return;
		group_average_rects.push( get_group_average(group) );
	}                                                     
	                          
	return group_average_rects;
}     

function get_group_average( group ){
	var tx=0;
	var ty=0;
	var tw = 0;
	for( var i=0; i<group.length; i++ ){
		tx += group[i].x; 
		ty += group[i].y; 
		tw += group[i].w; 
	}  
	
	tx /= group.length;
	ty /= group.length;
	tw /= group.length;
	return {x:tx,y:ty,w:tw};
}

function group_has_member( group, member_to_test ){
	for( var i=0; i<group.length; i++ ){
	  	if( are_neighbours( group[i], member_to_test ) )
			return true;
	}   
	return false;
}   
           

function are_neighbours( r1, r2 ){
	return test_neighbour(r1,r2) || test_neighbour(r2,r1);
}

function test_neighbour(r1, r2){
	var disth = r1.w*0.2;    
	return 		r2.x <= r1.x + disth &&
		        r2.x >= r1.x - disth &&
		        r2.y <= r1.y + disth &&
		        r2.y >= r1.y - disth &&
		        r2.x + r2.w <= r1.x + r1.w + disth &&
		        r2.x + r2.w >= r1.x + r1.w - disth &&
		        r2.y + r2.w <= r1.y + r1.w + disth &&
		        r2.y + r2.w >= r1.y + r1.w - disth;
}
 

// exhaustive, but slow
function multiscale_detect( ii, ii2, width, height, progressFn, resultFn ){
	var cw = 20;        
	var s_w = width/cw;
	var s_h = height/cw;     
	var max_scale = s_h < s_w ? s_h : s_w;          
	var to_return = new Array();                                  
	
	var scale_update = 1.2;
	 
	// while there is probably a better way to do this.. but i'm lazy
	var total_steps = 1;
	for( var s = max_scale; s>=1; s/=scale_update ){
		var w = (cw*s) >> 0;
		var step = Math.max(s,2) >>0;       
		var wsteps = 1 + ( ( width - w-1 ) / step ) >> 0;
		var hsteps = 1 + ( ( height - w-1) / step ) >> 0;    
		total_steps += ( wsteps *  hsteps );                 
		 
	}             
	// state variables
	var scale = max_scale;         
	var step = Math.max( scale,2) >>0;
	var w = (cw*scale)>>0;
	var inv_area = 1/(w*w);
	var endx = width - w - 1;
	var endy = height - w - 1; 
	var x = 0;
	var y = 0;
   
   	var num_steps = 0;
   
	(function step_detect(){
		var has_more = true;
		for( var i=0; i<1000; i++ ){
			if( detect_on_sub_image( x, y, scale, ii, ii2, w, width+1, inv_area) ){
				to_return.push( {x: x, y: y, w: w } );
			} 
			
			num_steps++;
			
			x += step;
			if( x > endx ){
				y += step;
				if( y > endy ){
					scale /= scale_update;                          
					if( scale < 1 ) {
						has_more = false;// we are done   
						break;
					}else{      
					  	x = 0;
					   	y = 0;
						step = Math.max( scale,2) >>0;
						w = (cw*scale)>>0;
						inv_area = 1/(w*w);
						endx = width - w - 1;
						endy = height - w - 1;      
					}
				} else { 
					x = 0;
				}
			}
		}           
		
		progressFn( num_steps, total_steps );             
		if( has_more ){
			setTimeout(arguments.callee, 0)         
		} else {
			resultFn(to_return);
		}
		
	})();
}  
                                    
function detect_on_sub_image( x, y, scale, ii, ii2, w, iiw, inv_area){             
	var mean = ( ii[(y+w)*iiw + x + w] + ii[y*iiw+x] - ii[(y+w)*iiw+x] - ii[y*iiw+x+w]  )*inv_area;
	var vnorm =  ( ii2[(y+w)*iiw + x + w] + ii2[y*iiw+x] - ii2[(y+w)*iiw+x] - ii2[y*iiw+x+w]  )*inv_area - (mean*mean);    
	vnorm = vnorm > 1 ? Math.sqrt(vnorm) : 1;
	
   	var passed = true;
	for( var i_stage = 0; i_stage < dat.length; i_stage++ ){
		var stage = dat[i_stage];  
		var trees = stage[0];  

		var stage_thresh = stage[1];
		var stage_sum = 0;
		                  
		for( var i_tree = 0; i_tree < trees.length; i_tree++ ){
			var tree = trees[i_tree];
			var current_node = tree[0];    
			var tree_sum = 0;
			while( current_node != null ){
				var vals = current_node[0];
				var node_thresh = vals[0];
				var leftval = vals[1];
				var rightval = vals[2];
				var leftidx = vals[3];
				var rightidx = vals[4];
				var rects = current_node[1];
				                       
				var rect_sum = 0;
				for( var i_rect = 0; i_rect < rects.length; i_rect ++ ){    
					var s = scale;
					var rect = rects[i_rect];
					var rx = (rect[0]*s+x)>>0;  
					var ry = (rect[1]*s+y)>>0;  
					var rw = (rect[2]*s)>>0;  
					var rh = (rect[3]*s)>>0;
					var wt = rect[4];     
					
					var r_sum =  ( ii[(ry+rh)*iiw + rx + rw] + ii[ry*iiw+rx] - ii[(ry+rh)*iiw+rx] - ii[ry*iiw+rx+rw] )*wt;    
					rect_sum += r_sum;  
				} 
				 
				rect_sum *= inv_area;                                                          
				     
				current_node = null;
				if( rect_sum >= node_thresh*vnorm ){
					if( rightidx == -1 ) 
						tree_sum = rightval;
				  	else
						current_node = tree[rightidx];
				} else {
					if( leftidx == -1 )
						tree_sum = leftval;
				  	else
						current_node = tree[leftidx];
				}
			} 
			stage_sum += tree_sum;
		} 
		                                                                                
		if( stage_sum < stage_thresh ){
			return false;
		}         
		
	           
	} 
	return true;
}