Summary:
Herot's short paper gave a brief, but comprehensive, look at sketch interaction systems in the mid 70s.
The paper first looks at a general recognizer, HUNCH, that tries to see if accurate knowledge can be obtained without using a specific domain. The system takes data drawn on a large tablet with a special pencil, and the raw input data is recorded by the computer. The HUNCH system used another application, called STRAIT, that found corners in data by examining the user's pen speed. The system also used a process called latching to snap endpoints of close lines together. Unfortunately, the HUNCH system had problem with consistency between different users. Users drawing at different pen speeds produced different corners, and the latching technique sometime distorted an intended image, such as oversnapping lines in a cube. The system also handles overtraced lines by merging lines together, provides some 3D image inference through unexplained techniques, and can create floor maps by looking at boxed rooms and doorways.
Context is an important part of a sketch, and Herot recognizes this fact by mentioning how data interpretations should have context information. The context should be specified to the computer as to avoid issues of recognizing the domain. Herot briefly mentions a top-down processing for recognizing sketches with a context architecture.
Lastly, Herot mentions that user input is a key component of a sketch recognition system that should not be ignored. More complex interfaces need to be developed so that a user can interact with a program and correct mistakes, and corner finding algorithms need to be tuned for an individual user.
Discussion:
Although none of the topics mentioned in Herot are new to me, the fact that all of these issues were mentioned in a paper written in 1976 is surprising. For instance, I had been under the assumption that using pen speed to detect corners was a relatively new fad.
I also am very surprised that the system tried (and from the one example, succeeded) at incorporating 3D image analysis. I remember reading a paper about using edges and vertices to detect whether an image is 3D, but I cannot seem to recall the author involved, so it's hard for me to construct a timeline for that research.
Showing posts with label corner finding. Show all posts
Showing posts with label corner finding. Show all posts
Monday, October 15, 2007
Thursday, September 20, 2007
A Curvature Estimation for Pen Input Segmentation in Sketch-based Modeling
Summary:
Kim and Kim propose a new corner detection system that utilizes local changes around corners.
The system starts by resampling the points of the stroke so that all points within the stroke are equidistant from one another. The curvature value at a point is typically set to equal the distance around the point divided by the changes over stroke length. By having a constant stroke distance, the system allows the direction values (calculated the same as in Sezgin and Yu) to equal the curvature values.
The final curvature value around each point is determined by two new metrics: local convexity and local monotonicity. Local convexity measures the "support" for a potential corner point. This value is calculated by looking at a window around the point and adding all of the curvature points of the same sign as the point's curvature. Local monotonicity examines the same window of points around a possible corner, but this time each point is examined in sequence, starting from the center. The curvature value can only be added if it is less than the previous point's and the same sign; if these two requirements are not met the algorithm stops and returns the current curvature.
The algorithm found the correct corners approximately 95% of the time.
Discussion:
Proposing two new (seemingly easy to implement) curvature metrics could provide corner finders with more techniques to solidify between good corners and noisy data. The paper was only published recently so I'm not sure how much of an impact it has caused yet.
The main issue I would have liked discussed more in the paper would have been where this corner finder differed from others in results. I know what types of shapes Sezgin's corner finder does well with (polylines, simple arcs) but I have yet to seen a corner finder that can continually find distinguish truly tough corners, such as a smooth line-arc transition. Kim & Kim's paper even doesn't count this transition as a corner (see Fig. 14, shapes 13 and 20). Their paper even vaguely states their accuracy rating as being "about 95 percent." I would think that if the curvature calculations were significantly better than previous corner finders' that the authors would want to show more proof. I guess we'll see how well the new metrics work this weekend...
Kim and Kim propose a new corner detection system that utilizes local changes around corners.
The system starts by resampling the points of the stroke so that all points within the stroke are equidistant from one another. The curvature value at a point is typically set to equal the distance around the point divided by the changes over stroke length. By having a constant stroke distance, the system allows the direction values (calculated the same as in Sezgin and Yu) to equal the curvature values.
The final curvature value around each point is determined by two new metrics: local convexity and local monotonicity. Local convexity measures the "support" for a potential corner point. This value is calculated by looking at a window around the point and adding all of the curvature points of the same sign as the point's curvature. Local monotonicity examines the same window of points around a possible corner, but this time each point is examined in sequence, starting from the center. The curvature value can only be added if it is less than the previous point's and the same sign; if these two requirements are not met the algorithm stops and returns the current curvature.
The algorithm found the correct corners approximately 95% of the time.
Discussion:
Proposing two new (seemingly easy to implement) curvature metrics could provide corner finders with more techniques to solidify between good corners and noisy data. The paper was only published recently so I'm not sure how much of an impact it has caused yet.
The main issue I would have liked discussed more in the paper would have been where this corner finder differed from others in results. I know what types of shapes Sezgin's corner finder does well with (polylines, simple arcs) but I have yet to seen a corner finder that can continually find distinguish truly tough corners, such as a smooth line-arc transition. Kim & Kim's paper even doesn't count this transition as a corner (see Fig. 14, shapes 13 and 20). Their paper even vaguely states their accuracy rating as being "about 95 percent." I would think that if the curvature calculations were significantly better than previous corner finders' that the authors would want to show more proof. I guess we'll see how well the new metrics work this weekend...
Monday, September 17, 2007
A Domain-Independent System for Sketch Recognition
Summary:
Yu and Cai's paper attempts to find corners in strokes by utilizing the stroke's direction and curvature information. Unlike Sezgin's corner finder, Yu and Cai's does not use speed data.
The corner finder first cheks to see if the stroke can be approximated by a primitive shape such as a line, arc, or circle. If not, the stroke is divided into two smaller strokes at the point of highest curvature. The system again checks to see if each of the subsections can be approximated by primitives, and the cycle of splitting the stroke and checking continues.
At each primitive approximation step, the corner finder looks at the direction graph of the segment to determine whether the segment is likely to be a line or an arc. The direction graph for a line is flat, whereas direction graphs for arcs and circles are sloped. To fit a line to the segment a least squares fit is used. To fit an arc to a stroke, a line is fitted between the first and last points of the segment. An arc is then formed to include the two end points and the point on the original stroke perpendicular to the midpoint of the line. The "center" of this arc (which can be viewed as a segment of a circle) is found, and to determine the error of the arc fit the corner finder calculates the difference between the area of the original stroke and the area of the beautified arc fit.
A circle is just another case for arc fitting, except the slope of the arc should be above or around 2 pi.
If the stroke intersects itself, another fit should be computed that takes into account the self-intersection points as corners. The best fit between the original computation method and the new, self-intersection method is taken to be the final corner set.
The corner finder "cleans up" the best fit by merging or removing segments. If a segment is short in length and not connected to two other segments it is removed (eliminates hooks). If a segment is short in length and connected to two other segments it is split down its midpoint and the two sections are attached to the larger shapes. If two segments have similar angles and proximity (touching, almost connected) then they are merged.
The paper also includes some basic object recognition, but it really is no more than some simple geometric classification combined with the fitting methods already described.
The system worked very well on lines, arcs, and polylines. Correct corner rates on these cases were in the mid to upper 90s. Yet, on hybrid line and arc shapes the system had mixed results. The system still failed to find corners where lines and arcs smoothly transition into one another and obtained a 70% accuracy in these cases. The accuracy for other cases was around 90%.
Discussion:
Yu and Cai's paper shows another method for corner finding, this time without using speed data. Yet, their approach was very similar to Sezgin's. Although it was described differently, the system still essentially looks at the current corner fit, adds another possible corner, and analyzes the fit again.
The main change in this system is the way that it handles circles and arcs. The approach would seem to be more accurate on some cases, such as circles. Also, looking at the slope of a large portion of the direction graph seems like a good technique to distinguish between lines and arcs.
Overall I was disappointed with the system's accuracy. It doesn't appear to be very significant from Sezgin's. The main issue I have with the corner finder is that the system still only uses curvature values to find corners. In a project I worked on last year I had to find edges within a digital image, and I think a modified edge detection algorithm might work well for finding corners. You start off by looking at a small segment of points and determine the least squares fit. Keep adding chunks of points to the segment until your least squares fit starts to level. When the fit starts to change again, backtrack a little and add a corner. Then repeat, creating a new segment starting at your new corner.
The method can detect more subtle differences in curvature that a global curvature threshold will not detect (the threshold for each segment is the local change). I'll probably implement this later if I have the time and see how it goes. I know one issue with this approach is that it can be computationally intensive if you have long segments.
Yu and Cai's paper attempts to find corners in strokes by utilizing the stroke's direction and curvature information. Unlike Sezgin's corner finder, Yu and Cai's does not use speed data.
The corner finder first cheks to see if the stroke can be approximated by a primitive shape such as a line, arc, or circle. If not, the stroke is divided into two smaller strokes at the point of highest curvature. The system again checks to see if each of the subsections can be approximated by primitives, and the cycle of splitting the stroke and checking continues.
At each primitive approximation step, the corner finder looks at the direction graph of the segment to determine whether the segment is likely to be a line or an arc. The direction graph for a line is flat, whereas direction graphs for arcs and circles are sloped. To fit a line to the segment a least squares fit is used. To fit an arc to a stroke, a line is fitted between the first and last points of the segment. An arc is then formed to include the two end points and the point on the original stroke perpendicular to the midpoint of the line. The "center" of this arc (which can be viewed as a segment of a circle) is found, and to determine the error of the arc fit the corner finder calculates the difference between the area of the original stroke and the area of the beautified arc fit.
A circle is just another case for arc fitting, except the slope of the arc should be above or around 2 pi.
If the stroke intersects itself, another fit should be computed that takes into account the self-intersection points as corners. The best fit between the original computation method and the new, self-intersection method is taken to be the final corner set.
The corner finder "cleans up" the best fit by merging or removing segments. If a segment is short in length and not connected to two other segments it is removed (eliminates hooks). If a segment is short in length and connected to two other segments it is split down its midpoint and the two sections are attached to the larger shapes. If two segments have similar angles and proximity (touching, almost connected) then they are merged.
The paper also includes some basic object recognition, but it really is no more than some simple geometric classification combined with the fitting methods already described.
The system worked very well on lines, arcs, and polylines. Correct corner rates on these cases were in the mid to upper 90s. Yet, on hybrid line and arc shapes the system had mixed results. The system still failed to find corners where lines and arcs smoothly transition into one another and obtained a 70% accuracy in these cases. The accuracy for other cases was around 90%.
Discussion:
Yu and Cai's paper shows another method for corner finding, this time without using speed data. Yet, their approach was very similar to Sezgin's. Although it was described differently, the system still essentially looks at the current corner fit, adds another possible corner, and analyzes the fit again.
The main change in this system is the way that it handles circles and arcs. The approach would seem to be more accurate on some cases, such as circles. Also, looking at the slope of a large portion of the direction graph seems like a good technique to distinguish between lines and arcs.
Overall I was disappointed with the system's accuracy. It doesn't appear to be very significant from Sezgin's. The main issue I have with the corner finder is that the system still only uses curvature values to find corners. In a project I worked on last year I had to find edges within a digital image, and I think a modified edge detection algorithm might work well for finding corners. You start off by looking at a small segment of points and determine the least squares fit. Keep adding chunks of points to the segment until your least squares fit starts to level. When the fit starts to change again, backtrack a little and add a corner. Then repeat, creating a new segment starting at your new corner.
The method can detect more subtle differences in curvature that a global curvature threshold will not detect (the threshold for each segment is the local change). I'll probably implement this later if I have the time and see how it goes. I know one issue with this approach is that it can be computationally intensive if you have long segments.
Wednesday, September 12, 2007
Sketch Based Interfaces: Early Processing for Sketch
Summary:
Sezgin et al.'s paper describes a way to find corners (vertices) of freely drawn symbols in order to break the symbol into lines and arcs. These lines and arcs can then be used to define the symbol, which can be passed into a geometrical recognizer for classification.
The vertex finding algorithm works by locating points of high curvature and minimum pen speed. Curvature is defined as being the change in direction at a given point, and speed is the change in arc length over time. Although the paper does not mention this, the curvature value for a point can be found by using a least squares fit over a window of points from p - k to p + k, and taking the slope of the fit (while watching for vertical lines, of course). Once we have the curvature and speed values for each point in the stroke we can find the local minima points that drop below a speed threshold and local maxima points that rise above a curvature threshold. In this paper the speed threshold is taken to be 90% of the average speed, and the curvature threshold is equal to the average curvature. These minima and maxima are possible vertices for speed and curvature, respectively.
Take the intersection of both the speed and curvature corners to get a starting set of possible corners, and now Sezgin et al. go through the remaining corners and calculate "fits" for each. The curvature metric is equal to the magnitude of the average of two curvature values some k window of points away, divided by the arc length between those points. The speed metric is just 1 - (speed at point / max speed). The remaining corner candidates are then sorted in their respective lists according to high metric value.
The algorithm then takes one remaining corner from each set (remaining speed and remaining curvature) and generates two new "hybrid fits": current corner set + speed candidate, current corner set + curvature candidate. The hybrid fits are then tested using a least squares algorithm between each vertex, and the fit with the least error becomes another possible corner fit for our stroke. More fits are generated until all remaining candidate corners are used up. The best fit is chosen based on an error threshold, and then the one with the least number of corners is chosen from those below the threshold.
Since a least squares fitting does not work with curved regions, for any arcs in a stroke the algorithm approximates the arc using a Bezier curve approximation. If the error on the curve we are trying to approximate is greater than a threshold we split the arc at the middle and create two new curve approximations. These curves are used to determine if fit errors.
The system can then beautify the sketch, which is a trivial process if we already have all of the vertices and the Bezier curve approximations. Overall the system had great results, and users "praised" the research because it allowed them to draw objects free-hand. The system accurately found the corners 96% of the time.
Discussion:
This paper is a cornerstone for vertex finding, pun intended. The research is well discussed, the algorithms are relatively easy to implement, and the results are fantastic.
The main thing that I would have liked to see included in the paper was a mention of where and how the algorithm can make a mistake. From my experience I know that corner finding is difficult on poorly drawn circles. Speed variations for circles can be slight, and if the circle looks more like an oval (as in the number 0) there can be a small protrusion or bump at the bottom of the circle that acts as a corner. I'd be interested to see how his system performed on these types of shapes.
Also, thresholds are very tricky when you take into account shapes that include both polylines and arcs. If it is a complex shape that needs to be drawn in a single stroke a user can sometimes pause in the middle of drawing to think about how to draw the next section. This pause will definitely hit as being a vertex, but it destroys the speed average and hurts the finding of more subtle corners.
Sezgin et al.'s paper describes a way to find corners (vertices) of freely drawn symbols in order to break the symbol into lines and arcs. These lines and arcs can then be used to define the symbol, which can be passed into a geometrical recognizer for classification.
The vertex finding algorithm works by locating points of high curvature and minimum pen speed. Curvature is defined as being the change in direction at a given point, and speed is the change in arc length over time. Although the paper does not mention this, the curvature value for a point can be found by using a least squares fit over a window of points from p - k to p + k, and taking the slope of the fit (while watching for vertical lines, of course). Once we have the curvature and speed values for each point in the stroke we can find the local minima points that drop below a speed threshold and local maxima points that rise above a curvature threshold. In this paper the speed threshold is taken to be 90% of the average speed, and the curvature threshold is equal to the average curvature. These minima and maxima are possible vertices for speed and curvature, respectively.
Take the intersection of both the speed and curvature corners to get a starting set of possible corners, and now Sezgin et al. go through the remaining corners and calculate "fits" for each. The curvature metric is equal to the magnitude of the average of two curvature values some k window of points away, divided by the arc length between those points. The speed metric is just 1 - (speed at point / max speed). The remaining corner candidates are then sorted in their respective lists according to high metric value.
The algorithm then takes one remaining corner from each set (remaining speed and remaining curvature) and generates two new "hybrid fits": current corner set + speed candidate, current corner set + curvature candidate. The hybrid fits are then tested using a least squares algorithm between each vertex, and the fit with the least error becomes another possible corner fit for our stroke. More fits are generated until all remaining candidate corners are used up. The best fit is chosen based on an error threshold, and then the one with the least number of corners is chosen from those below the threshold.
Since a least squares fitting does not work with curved regions, for any arcs in a stroke the algorithm approximates the arc using a Bezier curve approximation. If the error on the curve we are trying to approximate is greater than a threshold we split the arc at the middle and create two new curve approximations. These curves are used to determine if fit errors.
The system can then beautify the sketch, which is a trivial process if we already have all of the vertices and the Bezier curve approximations. Overall the system had great results, and users "praised" the research because it allowed them to draw objects free-hand. The system accurately found the corners 96% of the time.
Discussion:
This paper is a cornerstone for vertex finding, pun intended. The research is well discussed, the algorithms are relatively easy to implement, and the results are fantastic.
The main thing that I would have liked to see included in the paper was a mention of where and how the algorithm can make a mistake. From my experience I know that corner finding is difficult on poorly drawn circles. Speed variations for circles can be slight, and if the circle looks more like an oval (as in the number 0) there can be a small protrusion or bump at the bottom of the circle that acts as a corner. I'd be interested to see how his system performed on these types of shapes.
Also, thresholds are very tricky when you take into account shapes that include both polylines and arcs. If it is a complex shape that needs to be drawn in a single stroke a user can sometimes pause in the middle of drawing to think about how to draw the next section. This pause will definitely hit as being a vertex, but it destroys the speed average and hurts the finding of more subtle corners.
Subscribe to:
Posts (Atom)