Abam, de Berg, and Hachenberger. Streaming Algorithms for Line Simplification
The authors present a greedy algorithm that allows for the simplification of a polyline path to a simpler representative path on the fly, or as points along the path are being generated. The reasoning behind path simplification is a largely matter of storage space (not being able to store as many points as could be generated over long -- possibly infinite -- periods of time) rather then forming an idealized (or intentional) shape as usually seen in the sketch recognition setting. After discussing background information and previous approaches, they begin with the discussion of how their algorithm works. To begin, while the number of points does not exceed storage capacity, all points are stored. However, once the limit is exceeded their algorithm comes into play. Each point is stored in a priority queue with an associated error as the priority. The error assigned to a point is the error that would be generated by removing that point from the path (reducing a path p(i-1)p(i)p(i+1) to p(i-1)p(i+)). This error is measured in two way, Hausdorff error and Fréchet error, whose implementations are detailed towards the end of the paper. The errors are applicable to different types of paths, namely Hausdorff is only applicable to convex and xy-monotone paths. For arbitrary paths and the Fréchet error, they achieve a 4*sqrt(2)-competitive error with respect to an optimal offline algorithm (or at most 4*sqrt(2) time the optimal error).
This would be a novel concept to apply to the corner finding problem in sketch recognition, except for a problem, namely, in this method, the number of points (and therefore corners) is fixed a priori. One solution to this problem would be to use the set of points produced by this method as a set of candidate points similar to curvature points and speed points in Sezgin. This still runs into other problems, however. By limiting the number of points, we also limit the complexity of the figure, for example, choosing to remember only four points eliminates any figure with more than 3 segments. While extreme, this problem scales up, arbitrarily limiting user input. Though it seems unlikely that a user will require to be able to input drawings with 100 segments at a time, the possibility for such a sketch still exists. Additionally, if this set of points is used as candidate points in Sezgin, a quality metric must be assigned, possibly based on the Hausdorff and Fréchet errors, which could be feasible given the efficiency the authors assign to the error oracles.
Subscribe to:
Post Comments (Atom)
2 comments:
When you brought up your criticisms on the paper limiting the number of points during class some time ago, I didn't really how much of a problem it would be. It did seem to make some more sense when Dr. Hammond brought up the case of Abam's techniques being more ideal in the scribbling sense. My own criticisms differed a bit in that the points aren't limited enough when it's scaled up to a bazillion points, since points removed on a add-one-delete-one basis only cuts storage space by half (making it only a more pronounced simplification compared to taking even points). Perhaps the technique is most useful in the case when there are not too few or too many points? I wonder what that would be...
To both Pauls: the point of this algorithm isn't sketch. It's simply data compression. You choose how many points you store a priori. You don't care about corners and such, because that's not the domain of the algorithm.
Post a Comment