Image analysis – Image enhancement or restoration – Image filter
Reexamination Certificate
1998-04-07
2001-10-16
Rogers, Scott (Department: 2624)
Image analysis
Image enhancement or restoration
Image filter
C382S269000, C382S266000, C382S168000, C382S173000, C345S442000, C345S182000
Reexamination Certificate
active
06304677
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to methods and apparatus for interactive computer graphics.
Many forms of computer graphics systems provide various functionality: painting, drawing, three dimensional rendering, computer-assisted design (“CAD”), among others. A distinction which has developed with the advent of graphical user interfaces (“GUI”) in graphics systems is the form of input by a user. Some systems accept input as mathematical constructs, where a user (possibly another computer system) provides mathematical formulas or numerical points to cause the system to display a shape to match the input data. Some systems accept input as drawing motions, where a user manipulates an input device such as a mouse or tablet to cause the system to form an image matching the user's motions.
In a group of applications sometimes referred to as “drawing” applications, a user manipulates a graphical object to determine location, size, and other properties. The graphical object is then typically stored as parameters for an output primitive which operates according to one or more mathematical formulas. In a group of applications sometimes referred to as “painting” or “freehand” applications, a user moves a graphical pointer across areas of the computer display and the computer system stores the motions as a series of points. This form of input is generally more convenient and consistent with modern GUI standards. However, painting applications typically lack precision and are limited by display resolution capabilities. Drawing applications are typically limited in the complexity of shapes which may be created, often to lines and simple polygons. Some computer software applications incorporate both painting and drawing features, such as Adobe Illustrator.
Often a user wants to form a curve in graphics applications. One mathematical representation of a curve is a function to calculate a sequence of Bezier points. The definition of the function is complex and not easily supplied by a user. However, the resulting smooth image is desirable. Conventional graphics applications typically include tools for assisting a user in entering a Bezier curve. These tools typically include multiple elements which are adjusted by the user to approximate a desired shape. Freehand painting is generally a simpler input method. However, a smooth curve rarely results from freehand painting as controlled by a user. Similarly, a user may want to form a smooth curve from a digitized curve, such as one supplied from an optical character recognition device.
SUMMARY OF THE INVENTION
The invention provides methods and apparatus implementing a technique for entering a representation of a desired curve into a computer.
In general, in one aspect, the invention features a method for entering a representation of a desired curve into a computer and apparatus for implementing the method. The method includes receiving an input of an ordered sequence of points representing the desired curve; grouping the points of the sequence of points into one or more contiguous segments of points; smoothing the points of each segment to generate a segment of smoothed points for each segment of points; and fitting one or more mathematical curves to each segment of smoothed points, the one or more mathematical curves from each segment of smoothed points together forming the representation of the desired curve.
Among the advantages of the invention are one or more of the following. Finding corners after applying a high-frequency noise filter avoids finding corners at points where variation in curvature is the result of noise rather than an actual corner in the sequence. Applying smoothing between corners preserves corners while smoothing the sequence. Determining chords based on distance provides a reliable indication of curvature. Using multiple points within a distance to determine chords avoids problems with variation in point spacing. Open sequences are smoothed. Applying a sine transformation to a segment from an open sequence preserves the endpoints of the segment. A good curve fitting fidelity test results in a low number of sub-divisions. Dividing segments and recursively applying curve fitting provides a high fidelity fit. Applying smoothing before curve fitting preserves the endpoints of the segment. Applying smoothing before curve fitting also produces smooth results with few artifacts at curve fitting break points.
REFERENCES:
patent: 3626384 (1971-12-01), Davis
patent: 4771474 (1988-09-01), Takashima et al.
patent: 4949281 (1990-08-01), Hillenbrand et al.
patent: 5473742 (1995-12-01), Polyakov et al.
patent: 5636338 (1997-06-01), Moreton
patent: 5767458 (1998-06-01), Koolen
Proakis, John G., and Manolakis, Dimitris G., “Digital Signal Processing Principles, Algorithms, and Applications”, Third Edition, pp. 768-774 and pp. 787-790, Prentice Hall, Upper Saddle River, NJ, 07458.*
Pudet, Thierry, “Real Time Fitting of Hand-Sketched Pressure Brushstrokes”,Eurographics Proceedings,vol. 13, No. 3; pp. 205-220, 1994.
Taubin, Gabriel, et al., “Optimal Surface Smoothing as Filter Design”, Technical Report RC-20404, IBM Research, Mar. 1996.
Itoh, Koichi, et al., “A Curve Fitting Algorithm for Character Fonts”,Electronic Publishing,vol. 6, No. 3; pp. 195-205, 1993.
PostScript Language Reference Manual, Second Edition, Adobe Systems Incorporated, “Coordinate Systems and Transformations”; “Path Construction”; and “Painting”; pp. 150-164, 1990.
Knuth, Donald E.,Computers&Typesetting, “Pens”; “Paths”; “Transformations”; “Calligraphic Effects”; “Discreteness and Discretion”; pp. 20-29; 122-153; and 194-207; 1986.
Plass, Michael, et al., “Curve-Fitting with Piecewise Parametric Cubics”,Computer Graphics Proceedings, Annual Conference Series,vol. 17, No. 3, pp. 229-239, Jul. 1983.
Oliensis, J., “Local Reproducible Smoothing Without Shrinkage”,IEEE Transactions on Pattern Analysis and Machine Intelligence,vol. 15, No. 3, pp. 307-312, 1993.
Baudel, Thomas, “A Mark-Based Interaction Paradigm for Free-Hand Drawing”, User Interface Software and Technology Proceedings, Seventh Annual Symposium, pp. 185-192, Nov. 1994.
Adobe Systems Incorporated
Fish & Richardson P.C.
Rogers Scott
LandOfFree
Smoothing and fitting point sequences does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Smoothing and fitting point sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Smoothing and fitting point sequences will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2617395