Yu - A Domain-Independent System for Sketch Recognition
Yu's sketch system is very similar to Sezgin's. In both a sketch is segmented into lines and curves by finding perceived corners. Ideally, these corners match those that a human would perceive in an idealized version of the sketch, namely those corners that the human drawer intended are maintained and extraneous corners or jitter in the drawing are smoothed out. Like Sezgin, direction and curvature graphs are constructed; however, Yu does not use speed. Additionally, rather than choosing corners based on certainty metrics, Yu iteratively subdivides line segments a the highest point on the curvature graph to achieve a tighter fit. Yu begins by approximating the sketch as a single, horizontal line segment on either the direction graph (or actual sketch). If this approximation is close enough in a least-squares sense (under a threshold), the segment is accepted, while if not, the segment is subdivided at the maximal curvature point and each segment is fitted. Circles are fitted to a line on the direction graph whose slope is 2*PI/n (n=num of points on the segment). Overtraced circles are broken into multiple segments, and if they appear similarly shaped are replaced by a single "average" circle. Arc are represented by portions of circles. Yu also introduces a set of clean up rules that should help to fit the calculated shape to the intended one. This cleanup consists of deleting very small segments and merging segment that are similarly oriented and connect or overlap. As shown in Yu's examples, this can greatly reduce the number of corner and help achieve shapes that are much closer to the intended shape.
Yu's idea of adding corners that best improve the least squares accuracy of the sketch seems a much better idea than the metrics used by Sezgin. From the programming of Sezgin's algorithm on the class data, I'd frequently see that the best curvature point and the best speed point to add were often very close to each other. Due to this, initially one of the sets of points is largely ignored as the "best" point to add from it has been taken care of by a very close point in the other set, and other points that may improve the sketch neglected because they are good enough according to the metric. Usually this meant nearly all of the curvature and speed point needed to be added to the final fit to achieve a decent fit, severely overestimating the number of points. As clean-up method like Yu's could help alleviate this somewhat, but it seems that being able to skip those points and not add them at all would be more optimal
skip to main |
skip to sidebar
Summary and discussion of assigned readings for the Fall 20007 Sketch Recognition class
About Me
The Required Stuff
Year: PhD 3rd year
Email: p r i s c u s 2 7 @ gmail.com
Academic Interests: Neural Networks, Human Cognition, Manifold Learning
Relevant Experience: Classes - Machine Learning, Pattern Classification
Why are you taking this class?
Not only does the subject sound interesting, it also seems like a technology that will be very relevant to the future use of computers. Also, it sounded like a cool class to gain some knowledge in the area of human-computer interaction in a hands-on way.
What do you hope to gain?
A better understanding of how humans use handwritten/drawn information to communicate and also how we understand this information. How people recognize what is depicted.
5 to 10 years from now?
Not really sure. Hopefully I'll have graduated. I'd like to go into a teaching career, preferably at the university level, though teaching at a lower level of education and being able to provide an introduction to computer science at the high school or younger level would also be interesting.
Nonacademic interests:
Swing (and other forms of) dancing, Computer and console gaming, Sci-fi and fantasy literature.
Fun Story:
Since this has recently been told to everyone I know, I'll tell it. When I was about 5 or 6 years old, we were heading out to the car to go to church. I was dressed to the nines, new shoes, new slacks, a button up shirt, hair slicked back. My mom looks over at me and says, "Well Paul, you sure look sharp today." And I instantly burst into tears. Because as we all know, one of the very first things you learn is that sharp is very, very bad and you should never touch sharp things.
Email: p r i s c u s 2 7 @ gmail.com
Academic Interests: Neural Networks, Human Cognition, Manifold Learning
Relevant Experience: Classes - Machine Learning, Pattern Classification
Why are you taking this class?
Not only does the subject sound interesting, it also seems like a technology that will be very relevant to the future use of computers. Also, it sounded like a cool class to gain some knowledge in the area of human-computer interaction in a hands-on way.
What do you hope to gain?
A better understanding of how humans use handwritten/drawn information to communicate and also how we understand this information. How people recognize what is depicted.
5 to 10 years from now?
Not really sure. Hopefully I'll have graduated. I'd like to go into a teaching career, preferably at the university level, though teaching at a lower level of education and being able to provide an introduction to computer science at the high school or younger level would also be interesting.
Nonacademic interests:
Swing (and other forms of) dancing, Computer and console gaming, Sci-fi and fantasy literature.
Fun Story:
Since this has recently been told to everyone I know, I'll tell it. When I was about 5 or 6 years old, we were heading out to the car to go to church. I was dressed to the nines, new shoes, new slacks, a button up shirt, hair slicked back. My mom looks over at me and says, "Well Paul, you sure look sharp today." And I instantly burst into tears. Because as we all know, one of the very first things you learn is that sharp is very, very bad and you should never touch sharp things.
2 comments:
Sezgin's algorithm relies on the "best" corners being the first ones to find, yet if the corners aren't drawn with sharp angles the algorithm fails for the exact reason you said. The algorithm doesn't try to find the least amount of corners for the highest fit (lowest error). Instead, if the error still isn't low enough, the algorithm just pummels the stroke with more corners.
I don't think Yu's idea is "much better." I think both have their pros and cons, especially when Sezgin showed a strong case for the utility of speed data. Perhaps curvature is all we need in our particular data set, but what if we had polylines with intentional corners (speed-based) that were nearly colinear? Sezgin would find the vertex, in this case, while Yu may not. At least, it would be harder for Yu to find the vertex because Sezgin's speed metric would put it right on top.
Post a Comment