Method for aligning a lattice of points in response to features in a digital image

• US 20040006450A1
• Filed: 07/15/2003
• Published: 01/08/2004
• Est. Priority Date: 12/08/2000
• Status: Active Grant

• Current Assignee: Landmark Graphics Corporation (Halliburton Company)
• Original Assignee: Landmark Graphics Corporation (Halliburton Company)
• Inventors: Hale, Ira David
• Granted Patent: US 7,050,612 B2
• Time in Patent Office: Days
• US Class Current: 702/189
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

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.

Claims

1. 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.

2. The method of claim 1,

wherein said adjusting the set of points comprises adjusting locations of the set of points one or more times according to the composite function of spatial coordinates of the set of points.

3. The method of claim 1,

wherein said adjusting the set of points according to a composite function comprises adjusting the set of points to extremize the composite function.

4. The method of claim 3,

wherein said adjusting the set of points to extremize the composite function comprises adjusting the set of points to converge towards an extremum of the composite function.

5. The method of claim 1, whereby weights in said weighted combination are chosen to balance a desired extent of regularity of said set with a desired extent of responsivity of said set to said features in said image.

6. The method of claim 1, wherein said generating the mesh comprises generating a space-filling mesh from the set of points.

7. The method of claim 1, wherein the mesh comprises N-dimensional mesh elements, the method further comprising identifying a union of boundaries of a subset of said mesh elements, and wherein said union of boundaries corresponds to a boundary between regions of interest in said image.

8. The method of claim 1,

wherein said generating the set of points comprises generating the set of points in a subset of space sampled by the image, wherein said generating employs a distance function that specifies, for each point in said set, a preferred distance from the point in the set to other points in the set nearby said point.

9. The method of claim 8, wherein said generating the set of points comprises:

reading a first tentative set point from a queue;

examining a first neighborhood around said first tentative set point to determine if none of the set points in a current state of the set is contained in the first neighborhood; and

if the first neighborhood contains none of the set points in the current state of the set, executing an update operation comprising;

adding the first tentative set point to the set, and

appending new tentative set points to the queue, wherein said new tentative set points are assigned coordinate positions corresponding to an exactly regular set with respect to the first tentative set point and the distance function.

10. The method of claim 9, wherein said generating the set of points further comprises:

storing one or more seed points on the queue; and

repeatedly performing said reading, examining and conditionally executing the update operation until the subset of said space is filled.

11. The method of claim 8, wherein said generating the set of points comprises randomly adding points to the set at positions sampled by the image, and wherein a probability. of adding a point to the set at one of said sampled positions is determined by the distance function evaluated at said one sampled position.

12. The method of claim 1, wherein said generating the set of said points comprises computing a value of the first function, wherein said computing the value of the first function comprises:

evaluating a functional form at image sample positions in a neighborhood of a set point to obtain local function values;

adding the local function values to corresponding samples in an array representing an atomic potential field;

repeatedly performing said evaluating and said adding for each of the set points;

computing an atomic potential field value corresponding to each of the set points, based on one or more samples in the array representing the atomic potential field; and

adding the atomic potential field value for each the set points to determine the value of the first function.

13. The method of claim 12, wherein the functional form comprises a function of distance from the set point divided by a nominal distance function evaluated in the neighborhood of the set point.

14. The method of claim 1, wherein said generating the set of said points further comprises:

computing derivatives of the composite function with respect to each of the spatial coordinates of the points; and

determining an updated set of values for the spatial coordinates of the points based on the derivatives.

15. The method of claim 1, wherein the image attains at least one of a minimal value or maximal value along at least a subset of said features in said image.

16. 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.

17. The memory medium of claim 16,

wherein said adjusting the set of points comprises adjusting locations of the set of points one or more times according to the, composite function of spatial coordinates of the set of points.

18. The memory medium of claim 16,

wherein said adjusting the set of points according to a composite function comprises adjusting the set of points to extremize the composite function.

19. The memory medium of claim 18,

wherein said adjusting the set of points to extremize the composite function comprises adjusting the set of points to converge towards an extremum of the composite function.

20. The memory medium of claim 16, whereby weights in said weighted combination are chosen to balance a desired extent of regularity of said set with a desired extent of responsivity of said set to said features in said image.

21. The memory medium of claim 16, wherein said generating the mesh comprises generating a space-filling mesh from the set of points.

22. The memory medium of claim 16, wherein the mesh comprises N-dimensional mesh elements, the method further comprising identifying a union of boundaries of a subset of said mesh elements, and wherein said union of boundaries corresponds to a boundary between regions of interest in said image.

23. The memory medium of claim 16,

wherein said generating the set of points comprises generating the set of points in a subset of space sampled by the image, wherein said generating employs a distance function that specifies, for each point in said set, a preferred distance from the point in the set to other points in the set nearby said point.

24. The memory medium of claim 23, wherein said generating the set of points comprises:

reading a first tentative set point from a queue;

examining a first neighborhood around said first tentative set point to determine if none of the set points in a current state of the set is contained in the first neighborhood; and

if the first neighborhood contains none of the set points in the current state of the set, executing an update operation comprising;

adding the first tentative set point to the set, and

appending new tentative set points to the queue, wherein said new tentative set points are assigned coordinate positions corresponding to an exactly regular set with respect to the first tentative set point and the distance function.

25. The memory medium of claim 24, wherein said generating the set of points further comprises:

storing one or more seed points on the queue; and

repeatedly performing said reading, examining and conditionally executing the update operation until the subset of said space is filled.

26. The memory medium of claim 23, wherein said generating the set of points comprises randomly adding points to the set at positions sampled by the image, and wherein a probability of adding a point to the set at one of said sampled positions is determined by the distance function evaluated at said one sampled position.

27. The memory medium of claim 16, wherein said generating the set of said points comprises computing a value of the first function, wherein said computing the value of the first function comprises:

evaluating a functional form at image sample positions in a neighborhood of a set point to obtain local function values;

adding the local function values to corresponding samples in an array representing an atomic potential field;

repeatedly performing said evaluating and said adding for each of the set points;

computing an atomic potential field value corresponding to each of the set points, based on one or more samples in the array representing the atomic potential field; and

adding the atomic potential field value for each the set points to determine the value of the first function.

28. The memory medium of claim 27, wherein the functional form comprises a function of distance from the set point divided by a nominal distance function evaluated in the neighborhood of the set point.

29. The memory medium of claim 16, wherein said generating the set of said points further comprises:

computing derivatives of the composite function with respect to each of the spatial coordinates of the points; and

determining an updated set of values for the spatial coordinates of the points based on the derivatives.

30. The memory medium of claim 16, wherein the image attains at least one of a minimal value or maximal value along at least a subset of said features in said image.

37. The method of claim 17, wherein the image potential energy comprises a sum of image potential field values, and wherein each of said image potential field values corresponds to an evaluation of an image potential field at one of the set points.

38. The method of claim 37, wherein the image includes features of interest, the method further comprising generating the image potential field by processing the image so that the image potential field attains a first potential value along one or more of said features of interest and a second potential value away from said features of interest.

39. The method of claim 38, wherein the first potential value is a maximum potential value.

40. The method of claim 38, wherein the first potential value is a minimum potential value.

31. 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.

32. 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.

33. 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.

34. The method of claim 33, wherein said object comprises an underground reservoir of one or more fluids, and wherein the execution of the process comprises a simulation of the flow of said fluids based on said mesh.

35. The method of claim 33, wherein one of said pair-wise distances corresponds to one pair of said set points, and wherein the pair-wise distance comprises a ratio of (a) a distance between the points in the pair of set points and (b) a value of a nominal distance function evaluated in the neighborhood of the pair of set points.

36. 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.

41. The method of claim 36, wherein the atomic potential energy comprises a sum of atomic potentials for pairs of said set points.

42. The method of claim 41, wherein the atomic potential for one of said pairs of said set points is a function of normalized distance between the points in the pair, and wherein the normalized distance equals the ratio of an unnormalized distance between the points in the pair and a local value of a nominal distance function.

43. The method of claim 42 further comprising:

smoothing the image to generate a smoothed image; and

assigning values to the nominal distance function based on values of the smoothed image.

44. The method of claim 36, further comprising generating a mesh from the final set of points, wherein the mesh is usable to encode information associated with the image.

45. The method of claim 44, further comprising performing a simulation of a physical process using the mesh.

46. The method of claim 36, wherein said combination comprises a linear combination α

A+β

B, where A is the atomic potential energy, wherein B is the image potential energy, and wherein coefficients α and

β

control an extent of positional sensitivity of said set of points with respect to features in the image and an extent of regularity of said set of points.

47. The method of claim 36 further comprising:

acquiring a series of images; and

performing said initializing and adjusting on each of said images in said series to generate a corresponding series of final sets.

48. The method of claim 36 further comprising:

acquiring subsequent images;

encoding differences in the subsequent images using the final set of points to generate image codes; and

transmitting the image codes onto a transmission medium.

49. 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.

50. The method of claim 49, wherein said operating on the first image to generate the image potential field comprises detecting edges in said first image, and wherein said features of interest comprise edges in said first image.

51. The method of claim 49, wherein said operating on said image to generate the image potential field comprises:

identifying features of interest in the image;

assigning a first constant value to the image potential field at first spatial locations corresponding to at least a subset of said features of interest; and

assigning a second constant value to the image potential field at second spatial locations not corresponding to said features of interest.

52. The method of claim 51, wherein said first constant value is a maximum value of said image potential field.

53. The method of claim 51, wherein said first constant value is a minimum value of said image potential field.

54. The method of claim 51, wherein said operating on said image to generate the image potential field further comprises smoothing a first version of the image potential field, generated by said assigning the first constant value and the second constant value, to obtain a second version of the image potential field.

55. The method of claim 54, wherein said second version of the image potential field is used to compute the image potentials for a first set of repetitions of said repeatedly adjusting locations, and wherein said first version of the image potential function is used to compute the atomic image potentials for a second set of repetitions of said repeatedly adjusting locations.

56. The method of claim 49 further comprising:

randomly displacing the locations of said set of points in said space; and

performing multiple iterations of said randomly displacing and said repeatedly adjusting to obtain a succession of local extrema of the total potential energy.

57. The method of claim 49, further comprising initializing the set of points in the region of space corresponding to said image prior to said repeatedly adjusting, wherein said initializing employs a distance function that specifies a preferred distance from each point in said set to other points nearby said point, and wherein said preferred distance is a function of location in said region.

58. The method of claim 57, wherein said initializing the set of points in the region of space comprises:

reading a first tentative set point from a queue;

examining a first neighborhood around said first tentative set point to determine if the first neighborhood contains no points of said set; and

if the first neighborhood contains no points of said set, executing an update operation comprising;

adding the first tentative set point to the set, and

appending new tentative set points to the queue, wherein said new tentative set points are assigned coordinate positions corresponding to an exactly regular set with respect to the first tentative set point and the distance function.

59. The method of claim 58 further comprising:

storing one or more seed points on the queue; and

repeatedly performing said reading, examining and conditionally executing the update operation until the subset of said space is filled.

60. The method of claim 58 wherein the first neighborhood around said first tentative set point is an N-dimensional ball with diameter proportional to the distance function evaluated at the first tentative set point, wherein N is the dimension of said space corresponding to said image.

61. The method of claim 49, further comprising initializing the set of points in the region of space corresponding to said image, wherein said initializing the set of points in the region of space comprises:

computing a local probability value at a candidate position in the region based on a distance function;

generating a random number value;

determining if the random number value satisfies an inequality condition with respect to the local probability value; and

conditionally adding the candidate position to the set of points if the random number value satisfies the inequality condition with respect to the local probability value.

62. The method of claim 61, wherein said initializing the set of points further comprises:

moving the candidate position through a set of image positions sampled by said first image; and

performing said computing, generating, determining and conditionally adding for each of said image positions.

63. The method of claim 49, wherein the combination is of the form (1−

β

)A+β

B, wherein A is the atomic potential energy, B is the image potential energy, and wherein parameter β

takes any value in the range from zero to one inclusive.

64. The method of claim 49 further comprising triangulating the set of points to generate a mesh from the set of points, wherein said mesh comprises a union of mesh elements, and wherein the vertices of the mesh elements are the set points.

65. The method of claim 64, wherein said triangulating the set of points comprises performing a Delaunay triangulation of the set of points.

66. The method of claim 64 further comprising identifying a union of boundaries of said mesh elements which approximates one or more of said features of interest.

67. The method of claim 64 further comprising performing a simulation on the mesh, wherein the simulation generates output representing a behavior of a physical system.

68. The method of claim 67, wherein the physical system comprises an underground reservoir comprising one or more fluids.

69. 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.

70. 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.

71. The memory medium of claim 70, wherein the program instructions are further executable to generate a space-filling mesh from the set of points.

72. The memory medium of claim 71, wherein the mesh comprises N-dimensional mesh elements, wherein the program instructions are further executable to identify a union of boundaries of a subset of said mesh elements, and wherein said union of boundaries corresponds to a boundary between regions of interest in said image.

73. The memory medium of claim 70, wherein the program instructions are further executable to initialize the set of points in a subset of the space sampled by an image prior to said optimizing, wherein said initializing employs a distance function that specifies a preferred distance from each point in said set to other points nearby said point, and wherein said preferred distance is a function of location in said space.

74. The memory medium of claim 73, wherein said initializing the set of points comprises:

reading a first tentative set point from a queue;

examining a first neighborhood around said first tentative set point to determine if the first neighborhood contains no points of said set; and

if the first neighborhood contains no points of said set, executing an update operation comprising;

adding the first tentative set point to the set, and

appending new tentative set points to the queue, wherein said new tentative set points are assigned coordinate positions corresponding to an exactly regular set with respect to the first tentative set point and the distance function.

75. The memory medium of claim 72, wherein said initializing the set of points comprises randomly adding points to said set at positions sampled by said image, and wherein a probability of adding a point to said set at one of said sampled positions is determined by the distance function evaluated at said one of said sampled positions.

76. The memory medium of claim 70, wherein said optimizing the set of said points comprises repeatedly computing a value of the first function, wherein said computing the value of the first function comprises:

evaluating a functional form at image sample positions in a neighborhood of a set point to obtain local function values;

adding the local function values to corresponding samples in an array representing an atomic potential field;

repeatedly performing said evaluating and said adding for each of the set points;

computing an atomic potential field value corresponding to each of the set points, based on one or more samples in the array representing the atomic potential field; and

adding the atomic potential field value for each the set points to determine the value of the first function.

77. The memory medium of claim 76, wherein the functional form comprises a function of distance from the set point divided by a nominal distance function evaluated in the neighborhood of the set point.

78. 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.