Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1999-03-18
2002-10-08
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06462739
ABSTRACT:
BACKGROUND
The invention relates to smoothing a drawn curve which is rendered by a computer.
The generation and maintenance of diagrams on a computer typically require computer aided design (CAD) tools and graphics illustration software. In this process, users typically select one or more objects and place each object on a drawing sheet displayed on a monitor or other suitable display device. Users can also edit and manipulate these objects to achieve the desired appearance. To aid users in performing their lay-out tasks to generate digital drawings, common symbols or objects such as squares, rectangles, circles, and ovals, among others, are typically provided for the user to select and manipulate in creating at the design. Further, tools are also available to assist the user in drafting straight lines and curvilinear segments on the digital drawings.
The process of digitally drawing lines or curves is generally a trial and error process, especially when the curve is made up of a number of corners or segments. Attempts at drawing curves with multiple corners or segments generally result in curves which look noisy. The noise manifests itself as a sequence of jagged curves, each of which is defined by begin and end points. In addition to being visually undesirable, the editing, displaying and saving of the sequence of jagged curves can become quite complex. Thus, to improve the visual appearance and simplify the manipulation of noisy curves, it is desirable to use smoothed versions in lieu of the noisy curves.
The noise can be eliminated by suitable smoothing operations on the curves. To prevent distorting the shape of the curve, the smoothing operations need to preserve corners of the drawn curve. Potential distortions include rounding of the corners or shrinking of the curve which can be easily perceived by human observers.
Generally, given a path or curve represented by a set of points, the path can be smoothed using several techniques. One technique called a parametric technique fits one or more polynomials to a number of data points associated with the path. However, the parametric technique requires an a priori knowledge of an appropriate polynomials to use in fitting the data points. Further, the parametric technique does not preserve path corners.
A non-parametric technique can be used to reconstruct the curve. Generally, the non-parametric technique defines constraints that encompass data fidelity and smoothness requirements. An energy function is then defined in terms of the fidelity and smoothness constraints, and a path is constructed to approximate the curve which minimizes the energy function. The energy value is a composite of a number of factors, as follows:
E=D+&lgr;
2
*S
where D represents the distortion factor;
&lgr; is the smoothness parameter and larger values of &lgr; indicating greater smoothness; and
S is a smoothness function.
Additional factors or constraints can be imposed to achieve certain curve characteristics. One such constraint can be that the average departure of the transposed curve from the drawn curve be zero. This can be imposed as
&Sgr;(
x
i
−u
i
)=0
&Sgr;(
y
i
−v
i
)=0
Numerical methods are applied to evaluate the smoothing function and to identify the transposed curve with the minimal energy which fits between end-points of the drawn curve. The transposed curve with the lowest energy value E is selected as the smoothed curve.
SUMMARY
In general, the invention features a computer-implemented apparatus and method for smoothing a curve. The apparatus generates a smoothed curve from a noisily drawn, multi-segmented curve by minimizing an energy function for a transposed curve which fits between end-points of the drawn curve. The energy function has three components: a distortion component, a smoothing component and a shrink component. Numerical analysis methods are applied to evaluate the energy function and to identify the transposed curve with the lowest energy. The transposed curve with the lowest energy value is selected as the smoothed curve.
In one aspect, the apparatus generates a smoothed curve from a drawn curve by defining an energy constraint associated with the drawn curve, the energy constraint having a shrink component, a distortion component, and a smoothness component; and generating the smoothed curve by minimizing the energy constraint.
Implementations of the invention include one or more of the following. The energy constraint E may be expressed as:
E=D+&lgr;
2
*S+&ggr;
2
*B
where D is the distortion component, &lgr; is a smoothness parameter, S is the smoothness component, &ggr; is a shrink parameter and B is the shrink component. The shrink component may be defined as a function of the area enclosed between the drawn curve and the smoothed curve. The shrink component may also be defined as the square of the area enclosed between the drawn curve and the smoothed curve. The drawn curve includes one or more points and the smoothed curve includes one or more corresponding transposed points, further comprising approximating the enclosed area as the sum of areas enclosed between consecutive points on the drawn curve and the corresponding transposed points. The area enclosed between consecutive points on the drawn curve and the corresponding transposed points is determined by:
Area
i
=(
x
i+1
−x
i
, y
i+1
−y
i
)×(
u
i
−x
i
, v
i
−y
i
)
where (x
i
,y
i
) represent a point on the drawn curve, (u
i
,v
i
) represent a point on the smoothed curve, and X is the vector cross product.
The area enclosed between consecutive points on the drawn curve and the corresponding transposed points may also be determined by:
Area
i
=(
x
i+1
−x
i
, y
i+1
−y
i
)×((
u
i
−x
i
, v
i
−y
i
)+(u
i+1
−x
i+1
, v
i+1
−y
i+1
)).
The energy constraint may be minimized using a gradient descent method.
In another aspect, a computer system characterizes a drawn curve defined by a sequence of points on a two-dimensional space. The computer includes a display, a user input device, and a processor coupled to the display and the user input device. The processor has instructions embedded therein to:
determine a distortion component D associated with the smoothed curve in accordance with
D
=
∑
i
=
0
N
-
1
(
(
u
i
-
x
i
)
2
+
(
v
i
-
y
i
)
2
)
where (x
i
,y
i
) represent a point on the drawn curve (u
i
,v
i
) represent a point on the smoothed curve;
determine a smoothing component S associated with the smoothed curve in accordance with:
S
=
∑
i
=
0
N
-
1
(
u
i
-
u
i
+
1
)
2
+
(
v
i
-
v
i
+
1
)
2
determine a shrink component B for a systematic shift in accordance with:
B
=
[
∑
i
=
1
N
-
1
(
v
i
·
l
i
+
u
i
·
m
i
)
+
M
]
2
and
generate one or more smoothed curves, each curve having an energy value E expressed in terms of the distortion component, the smoothing component and the shrink component in accordance with:
E=D+&lgr;
2
*S+&ggr;
2
*B
where &lgr; is the smoothness parameter, &ggr; is the distortion parameter; and
select the smoothed curve with the minimum energy as the smoothed curve.
In another aspect, computer-implemented method generates a smoothed curve from a drawn curve by defining a function for one or more signed areas between the smoothed curve and the drawn curve; and generating the smoothed curve by applying the function as a constraint.
In another aspect, an apparatus for generating a smoothed curve from a drawn curve includes means for defining a function for one or more signed areas between the smoothed curve and the drawn curve; and means for generating the smoothed curve by applying the function as a constraint.
In yet another aspect, an apparatus for generating a smoothed curve from a drawn curve, includes means for defining an energy constraint associated with the drawn curve, the energy constraint having a shrink component, a distortion component, and a smoot
Abode Systems Incorporated
Blackman Anthony J.
Brier Jeffery
Fish & Richardson P.C.
LandOfFree
Curve smoothing without shrinking does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Curve smoothing without shrinking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Curve smoothing without shrinking will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2997079