Correspondence between n-dimensional surface: vector fields...

Details Correspondence between n-dimensional surface: vector fields... Correspondence between n-dimensional surface: vector fields...

1999-03-11

2003-02-25

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Graphic manipulation

C345S646000, C345S647000

Reexamination Certificate

active

06525744

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The field of the invention is computer graphics and digital imaging generally and more specifically the generation of surfaces that belong to a class of surfaces.
2. Description of the Prior Art
When an object can be described by means of dimensional coordinates, a second object can be described using the coordinates of a first object and a description of a transformation by means of which the coordinates of the first object can be transformed into coordinates describing the second object.
FIG. 1
shows a simple example: curve
101
may be described by means of the coordinates of a set of points; shown are the points {a, b; c, d; e, f; g, h; i, j}. Curve
103
is described relative to curve
101
by the points {a+8,b;c+2,d;e, f;g+2,h;i+8,j}. It may also be described relative to curve
101
by means of the points of curve
101
and a vector field which describes the offsets that have to be added to the coordinates of the points making up curve
101
to obtain curve
103
; for the points a,b through i,j, vector field
106
has the values (8,0), (2,0) , (0,0) , (2,0), (8,0) . As can be seen from the foregoing, vector field
106
is based on a correspondence between the points {a,b;c,d;e,f;g,h;i,j} of curve
101
and the points {a+8,b;c+2,d;e,f;g+2,h;i+8,j} of curve
103
. In many cases, a vector field that describes how one object must be transformed to become a second object requires far fewer bits than a complete description of the second object, and vector fields are thus much used in computer graphics and digital imaging generally to save data storage space and/or network bandwidth.
When a vector field expresses a relationship between a first object and a second object, as it does with curves
101
and
103
of
FIG. 1
, the description of the first object and the vector field can be used to derive other objects that belong to a class of objects defined by the first object and the second object. In
FIG. 1
, three curves,
105
,
107
, and
109
are shown in dashed lines. These curves are different from, but clearly related to curves
101
and
103
. In some sense, they have characteristics that are defined by the characteristics of curves
101
and
103
. Each of the curves is generated by multiplying vector field A
106
by a fractional constant; with curve
105
, the constant is ¾; with curve
106
, it is ½; with curve
109
, it is ¼. It should be noted here that other curves that are related to curves
101
and
103
may be produced by multiplying vector field A
106
by constants whose values are outside the range [0,1].
Thus, in general, if one wants to generate a set of objects whose characteristics are defined by a first object and a second object, one can do so by making descriptions of the two objects, finding a vector field which, when applied to the first object, transforms the first object into an object that is similar to the second object, and then creating each object in the set of objects by manipulating the vector field and then applying the manipulated vector field to the first object to create the desired object. The technique is further not limited to two objects: the first object may have vector fields that describe transformations into a number of other objects, and objects belonging to the class defined by the first object and the other objects may be generated by combining the transformations specified in the vectors.
Objects generated by manipulating the vector field have many uses. For example, in image recognition systems, an image that is to be recognized must be compared with an example image; the image to be recognized is often a variation on the example image. For instance, the example image may be a photograph showing a smiling face; the image to be recognized may be frowning; by using vector fields as described above, the smiling face of the example image may be transformed into a frowning image and that image may be compared with the image to be recognized. Another use of such objects is what is termed “morphing”, that is, a sequence of images such that a first image turns gradually into a second image. If one has a vector field which transforms the first image into the second image, the sequence of images required to morph the first image into the second image can be made by manipulating the vector field and applying the manipulated vector field to the first image. For example, the vector field manipulation of
FIG. 1
could be seen as morphing the “frown” of curve
101
into the “smile” of curve
103
via curves
109
,
107
, and
105
.
The chief problem with generating sets of objects in this fashion is finding the vector field. One source of difficulty is automatically determining at all which vector field produces the “best” family of objects, that is, produces the family of objects that makes the smoothest transition between the first object and the second object; another source of difficulty is the computational cost of such a determination.
Where the objects are images, the vector fields are termed optical flows. For details on optical flows, see J. L. Barron, et al., “Performance of optical flow techniques”, in
Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition
, pp. 236-242, Champaign, Ill., 1992. Solutions for the problems of determining which vector field produces the best family of objects and for reducing the computational cost of such a determination when the objects are images are described in U.S. Pat. No. 5,745,668, Poggio, et al., Example-based image analysis and synthesis using pixelwise correspondence, issued Apr. 28, 1998, which is hereby incorporated by reference into the present patent application.
Images are, however, two-dimensional objects. Finding the best vector field with objects that are described using more than two dimensions presents further problems. In the following, an object that is described using more than two dimensions will be termed a surface. The problems of finding a vector field that can be applied to a given surface to generate members of a class of surfaces that is defined by two or more surfaces include the following:
finding a correspondence between the source and target objects upon which a vector field can be based that generates objects which preserves the characteristics of both the source surface and the target surface;
finding a way of quantifying correspondences between objects; and
finding a way to reduce the computational cost of finding the correspondences and thereby of finding the vector field.
It is an object of the present invention to overcome these problems and thereby make it possible to generate sets of surfaces that belong to a class defined by a first surface and one or more other surfaces from a description of the first surface and vector fields that describe how the first surface can be transformed into the other surfaces.
SUMMARY OF THE INVENTION
The problem of finding a correspondence is solved by defining the correspondence in terms of similarity to the target surface and amount of distortion of the source surface. In one aspect of the techniques, the distortion is measured by applying functions that measure structural changes to the source surface. In a preferred embodiment, the functions are directional spring functions for pairs of points in the source surface, the directional spring functions having the property that they respond to changes in distance and/or direction of the points relative to each other. In a further aspect of the techniques, the surfaces are represented by triangular meshes and the directional spring functions are applied to vertices that are adjacent to a given vertex in the triangular mesh and to any other vertex that is closer to the given vertex than the given vertex's most distant adjacent vertex.
The computational cost of finding the correspondence is reduced by first producing pairs of increasingly simplified representations of the source su

Affiliated with

Also associated with

Rating

Correspondence between n-dimensional surface: vector fields... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Correspondence between n-dimensional surface: vector fields..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Correspondence between n-dimensional surface: vector fields... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3144707