Accurate
Primitive Sketch Recognition and Beautification
Summary:
The
primary contribution of this paper is introducing a low-level sketch
recognition and beautification system that uses two new features and a novel
ranking algorithm.
The two
new features are:
(1) Normalized
Distance between Direction Extremes(NDDE): The distance between the point with
highest direction value( change of y over change of x ) and the point with
lowest direction value, divided by the length of the stroke.
(2) Direction
Change Ratio( DCR ): The maximum change in direction divided by the average
change in direction.
The
novel ranking algorithm is used to assign a score to interpretations of input sketch.
The one with lower score is a better interpretation of the input sketch.
The
score table of primitives is as follows,
An
example about how the ranking algorithm works:
Implementation:
The
architecture of the low-level sketch recognizer in this paper:
In
pre-recognition stage,
(1)
Remove consecutive, duplicate points
from the stroke. These points can occur in systems with a high sampling rate.
(2)
A series of graphs and values
are computed for the stroke, including direction graph, speed graph, curvature
graph and corners.
(3)
Compute the NDDE and DCR
mentioned in Summary Section.
(4)
Remove “tails”( the endpoints
of strokes ) before sending the stroke to each of the shape tests.
(5)
Test whether the stroke is
overtraced( shapes make multiple revolutions ) and closed.
In test
stage,
(1) Line
Test
1) Fit a
least square line to the stroke points.
2) Determine
the least square error, which must below a certain threshold.
3) The
feature area of the line is divided by stroke length to get an error which must
be within a threshold.
4) Verify
the stroke is not overtraced and only contains 3 corners.
(2) Polyline
Test
1) Break
the stroke into substrokes at the calculated corners.
2) send
each sub-stroke to the line test and keep track of the sum of least squares
errors as well as the sum of the feature area errors.
3) Check
three conditions.
(3) Ellipse
Test
1)
calculate the ideal major axis, center and minor axis.
2) check
to make sure the some conditions apply.
(4) Circle
Test
1)
calculating an ideal radius, center.
2) pass
some conditions
3)
verify it is better fit a circle rather than an ellipse by calculating the
major/minor axis ratio, which must be near certain threshold value.
4)
feature area error verification
(5) Arc
Test
1)
calculate the ideal center point of the arc.
2)
calculate the ideal radius of the arc.
3) test:
not closed or overtraced and must have high NDDE value and low DCR value.
4)
calculate the feature area of the arc and make sure its error is below a
certain threshold.
(6) Curve
Test
1)
calculate d+1 control points and estimate the control points by solving a
system of equations.
2)
generate the ideal curve according to the Bezier curve formula.
3) test:
low DCR value as well as a low least square error.
(7) Spiral
Test
1) break
the stroke up at every 2pi interval.
2) test:
most be overtraced, NDDE must be high, each sub-stroke is fit to a circle, box
radius must be less than a threshold and centers of consecutive sub-strokes
must be close to each other
3)
calculate the distance between endpoints and divide it by stroke length
(helpful for distinguishing spirals from helixes)
(8) Helix
Test
1)
choose constant radius and the major axis.
2) find
the starting and ending center points.
3) find
center point for the rest revolutions.
(9) Complex
Test
1) break
a stroke up into two sub-strokes at the point of highest curvature.
2) each
stroke is then recursively sent back into the recognizer.
3) add
an additional step: send sub-strokes to a secondary function which attempts to
recombine consecutive sub-strokes and check if they can be treated as a single
primitive.
4)
replace them.
In hierarchy
stage,
Sort
interpretations of sketch using the ranking algorithm mentioned in Summary
Section.
Bibliography:
B. Paulson and T. Hammond. Paleosketch: Accurate primitive sketch recognition and beautification. InIUI ’08: Proceedings of the 13th international conference on Intelligent User Interfaces, pages 1–10, New York, NY, USA, 2008. ACM Press.
