1Fall 2007 CAP 5937 – Topics in Pen-Based User Interfaces ©Joseph J. LaViola Jr.Features Extraction for Sketch-Based RecognitionLecture #8: Feature ExtractionJoseph J. LaViola Jr.Fall 2007Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Recall Pen-Based Interface DataflowRaw StrokeDataPreprocessing SegmentationFeature ExtractionAndAnalysisClassificationInk ParsingSketchUnderstandingMake Inferences2Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Feature Extraction and Analysis What came first, the feature or the machine learning algorithm? Want to distinguish sketch components from one another Good features are critical Extract important information geometrical, statistical, contextual Examples include arc length, histograms, cusps, aspect ratio self-intersections, stroke area, etc…Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Finding Features Challenging problem need fast algorithms for gathering information features must be good discriminators Often trial and error Can be domain specific3Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Geometric Features (1) Number of strokes if you know how many strokes a symbol has, you can break up your recognizer into pieces (i.e., recognizer for 1 stroke symbols, recognizer for 2 stroke symbols …) Cusps smooth vs. jagged strokes distance between cusps useful for when cusps areclose together/far apartFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Geometric Features (2) Aspect ratio (width / height) tall vs. flat Self Intersections loops vs. no loops strokes with write over distance between self intersections also useful use line segment intersection algorithmloopswrite over4Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Geometric Features (3) First and last distance  Strokes where first and last points are close together vs. far apart simple computation – Arc length many different symbols have varying arc lengths simple computation as well –1ppn−∑=−−=niiippl21Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Geometric Features (4) Stroke area area defined by the vectors created with the initial stroke point and consecutive stroke points. good discriminator for straight vs. curved lines()()scalar a is u whereusgnu21 and uGiven i21ii1211iiniiiareaiiivvvsppvpprrrrrrrr××⋅×=−=−=∑−=++5Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Geometric Features (5) Fit line feature sophisticated approach to finding how close a stroke is to a straight line finds a least-squares approximation to a line using principal components and then uses this approximation to find the distance of the projection of the stroke points onto the approximated line outputs a value in [0,1] What is another name for this approach?Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Fit Line Feature Implementation6Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Statistical Features (1) Side ratios first and last point of strokes have variable locations with respect to the bounding box Approach take the x coordinates of the first and last point of a stroke  subtract them from the left side of the symbol’s bounding box (i.e., the bounding box’s leftmost x value) divide by the bounding box width.1stand last point on right side of bbox1stand last point on left side of bboxFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Statistical Features (2) Top and Bottom ratios similar to side ratios except we are dealing with ycoordinate approach take y coordinate of the first and last point of a stroke subtract from the top of the symbol’s bounding box (i.e., the bounding box’s topmost y value) these values are divided by the bounding box height.1stand last points close to top of bbox1stand last points are at the bottom of bbox7Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Statistical Features (3) Point Histogram distribution of point locations in stroke bounding box discrimination where point concentrations are high  approach  break up box into n x m grid Count number of points in each sub box divide by total number of pointsFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Statistical Features (4) Angle Histogram similar to point histogram except dealing with angles Approach put angles into bins of n degrees⎟⎟⎠⎞⎜⎜⎝⎛⋅==≤≤−=−jj1jvvarccos)0,1( and 2for vGiven rrrrrxxnippjiiα8Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.The Rubine Feature Set (Rubine 1991) Part of Rubine’s gesture recognition system we will see this next class Stroke  P = total number of points p = middle point first point (x0,y0,t0) last point (xP-1,yP-1,tP-1) compute xmin, ymin, xmax, ymaxFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Feature f1 Cosine of starting angle()202202021)()()cos(yyxxxxf−+−−==α9Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Feature f2 Sine of starting angle202202022)()()()sin(yyxxyyf−+−−==αFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Feature f3 Length of diagonal of bounding box (gives an idea of the size of the bounding box)2minmax2minmax3)()( yyxxf −+−=10Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Feature f4 Angle of diagonal gives an idea of the shape of the bounding box (long, tall, square)⎟⎟⎠⎞⎜⎜⎝⎛−−=minmaxminmax4arctanxxyyfFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Feature f5 Distance from start to end of stroke2012015)()( yyxxfPP−+−=−−11Fall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Feature f6 Cosine of ending angle5016)()cos(fxxfP−==−βFall 2007 CAP 5937 – Topics in Pen-based User Interfaces ©Joseph J. LaViola Jr.Feature f7 Sine of ending