Method for aligning a lattice of points in response to features in a digital image
AssigneeLandmark Graphics Corporation
InventorIra David Hale
Life of this patent
Estimating the term…
Abstract
A system and method for generating a lattice of points that respects features in a digital image. The method comprises a process for initializing the lattice, and a process for optimizing the configuration of that lattice with respect to the image features. The optimization process operates by adjusting points of the lattice to extremize a composite function of the spatial coordinates of the lattice points. The lattice points are interpreted as atoms. Each lattice point contributes a potential function to an atomic potential field. The image represents another potential field. The composite function is a weighted sum of the atomic and image potential fields evaluated at the lattice points.
Claims78
A computer-implemented method for generating a mesh characterizing an image, the method comprising:
- receiving the image;
- generating a set of points that span at least a portion of the image;
- adjusting the set of points according to a composite function of spatial coordinates of the set of points;
- wherein said composite function is a weighted combination of a first function of pair-wise distances between said points, and a second function of sampled values of said image near said points;
- and
- wherein the first function is a summation of terms, wherein each of said terms corresponds to one of said pair-wise distances between said points;
- and
- generating the mesh based on the adjusted set of points.
A memory medium comprising program instructions for generating a mesh characterizing an image, wherein the program instructions are executable to implement:
- generating a set of points that span at least a portion of the image;
- adjusting the set of points according to a composite function of spatial coordinates of the set of points;
- wherein said composite function is a weighted combination of a first function of pair-wise distances between said points, and a second function of sampled values of said image near said points;
- and
- wherein the first function is a summation of terms, wherein each of said terms corresponds to one of said pair-wise distances between said points;
- generating the mesh based on the adjusted set of points.
A computer-implemented method for generating a lattice of points responsive to features in a digital image, the method comprising:
- receiving the digital image;
- generating said lattice of points in a subset of space sampled by the image;
- adjusting said lattice of points to extremize a composite function of spatial coordinates of said points;
- wherein said composite function is a weighted combination of a first function of pair-wise distances between said points, and a second function of sampled values of said image near said points;
- wherein the first function is a summation of terms, wherein each of said terms corresponds to exactly one of said pair-wise distances between said points;
- and
- wherein said optimized lattice of points is usable to generate a mesh for execution of a process associated with said image.
A computer-implemented method for generating an N-dimensional set of points that respects features in an N-dimensional digital image, wherein N is an integer greater than zero, the method comprising:
- optimizing said set by adjusting said points to extremize a composite function of spatial coordinates of said points;
- wherein said composite function is a weighted combination of a first function of pair-wise distances between said points, and a second function of sampled values of said image near said points;
- wherein the first function is a summation of terms, wherein each of said terms corresponds to exactly one of said pair-wise distances between said points;
- and
- wherein said optimized set of points is usable to generate a mesh for execution of a process associated with said image.
A computer-implemented method for generating a representation of an object from an image of the object, the method comprising:
- adjusting locations of the points in the space one or more times according to a composite function of spatial coordinates of the points;
- wherein the composite function is a weighted combination of a first function of pair-wise distances between the points, and a second function of sampled values of said image near the points;
- wherein the first function is a summation of terms, wherein each of said terms corresponds to exactly one of said pair-wise distances between said points;
- and
- wherein said adjusting locations one or more times produces a final set of points that is usable to generate a mesh for execution of a process associated with said object.
A computer-implemented method for characterizing an image, the method comprising:
- adjusting locations of points in a set of points in a space sampled by the image one or more times to converge towards an extremum of a total potential energy, wherein said total potential energy comprises a combination of an atomic potential energy of the set and an image potential energy of the set;
- wherein the image potential energy is computed from the image and the locations of the set points;
- and
- wherein said adjusting locations one or more times produces a final set of points that is usable to encode information associated with the image.
A computer-implemented method for determining a set of points characterizing an image, the method comprising:
- operating on the image to generate an image potential field, wherein said image potential field attains an extremal potential value along features of interest in said image;
- repeatedly adjusting locations of said set of points in a region of space corresponding to said image to extremize a total potential energy,
- wherein said total potential energy comprises a combination of an atomic potential energy and an image potential energy,
- wherein the atomic potential energy comprises a sum of atomic potentials for pairs of said set points,
- wherein the image potential energy comprises a sum of image potentials, and
- wherein each of said image potentials corresponds to an evaluation of the image potential field at one of the set points.
A computer system configured to determine a set of points characterizing an image, the computer system comprising:
- a processor;
- a memory coupled to said processor and configured to store program instructions;
- and
- an input port for providing an image to said memory;
- wherein said processor is configured to read and execute the program instructions from said memory, wherein, in response to said execution of the program instructions, the processor is operable to:
- operate on the image to generate an image potential field, wherein said image potential field attains one or more extreme potential values along features of interest in said image;
- repeatedly adjust locations of said set of points in a region of space corresponding to said image to extremize a total potential energy,
- wherein said total potential energy comprises a combination of an atomic potential energy and an image potential energy,
- wherein the atomic potential energy comprises a sum of atomic potentials for pairs of said set points,
- wherein the image potential energy comprises a sum of image potentials, and
- wherein each of said image potentials corresponds to an evaluation of the image potential field at one of the set points.
A computer-readable memory medium configured to store program instructions, wherein the program instructions are executable to implement:
- optimizing said set by moving said points in a space sampled by an image to extremize a composite function of the spatial coordinates of said points;
- wherein said composite function is a weighted combination of a first function of pair-wise distances between said points, and a second function of sampled values of said image near said points;
- wherein the first function is a summation of terms, wherein each of said terms corresponds to exactly one of said pair-wise distances between said points;
- and
- wherein said optimized set of points is usable to generate a mesh for execution of a process associated with said image.
A method comprising:
- operating on an image to generate an image potential field, wherein said image potential field attains extremal potential values along features of interest in said image;
- repeatedly adjusting locations of a set of points in a region of space corresponding to said image to extremize a total potential energy,
- wherein said total potential energy comprises a combination of an atomic potential energy and an image potential energy,
- wherein the atomic potential energy comprises a sum of atomic potentials for pairs of said points of said set,
- wherein the image potential energy comprises a sum of image potentials, and
- wherein each of said image potentials corresponds to an evaluation of the image potential field at one of the points of said set.
Dependencies are inferred from the claim text.