Topology-Based Method of Partition, Analysis, and Simplification of Dynamical Images and its Applications

• US 20070036434A1
• Filed: 08/01/2006
• Published: 02/15/2007
• Est. Priority Date: 08/15/2005
• Status: Abandoned Application

• Current Assignee: Peter Saveliev
• Original Assignee: Peter Saveliev
• Inventors: Saveliev, Peter
• Application Number:
  US11/461,479
• Publication Number:
  US 20070036434A1
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation

Abstract

A dynamical image of is an array of black-and-white images, or frames, of arbitrary dimension. Dynamical images are constructed from gray scale and color images, video sequences etc. A method of topological analysis and decomposition of dynamical images through computation of homology groups of the frames is provided. Each frame is partitioned into a collection of components, which, in turn, have tunnels, voids, and other higher dimensional cycles. The cycles in each frame are linked to the cycles in each adjacent frame to record how they merge and split. Further, the dynamical image is simplified by removing from frames all cycles that are small in terms of length, area, volume, etc, or lifespan. Applications of the method lie in image enhancement and restoration, motion tracking, computer vision, surface and curve reconstruction, scientific image analysis, image recognition and matching.

Claims

1. In a model of a video as a sequence of binary 2D images, wherein the improvement comprises a dynamical image:

a time-dependent stream of pluralities of objects called frames, aligned with each other and an adjacency relation defined on these frames.

2. A method of analyzing time-dependent images wherein:

homology groups of a filtration sequence of simplicial complexes are incrementally computed; and

comprising steps of;

A) processing an input image by providing a representation of the input image as a dynamical image comprising a set of frames;

B) analyzing the dynamical image by providing;

(1) a set of topological features of the set of frames of the dynamical image;

(2) a set of relations between the topological features of a pair of adjacent frames comprising at least one of;

matching, appearing, disappearing, merging, and splitting of topological features.

3. The method in claim 2 wherein the set of topological features computed by the analyzing in step (B) comprise a set of homology groups of each frame.

4. The method in claim 3 wherein parts (1) and (2) of the analyzing in step (B) are executed by applying a Mayer-Vietoris theorem to a difference of a pair of adjacent frames.

5. The method in claim 3, further comprising:

C) evaluating a saliency of a topological feature of the input image by computing a predetermined combination of sizes of a homology class corresponding to the topological feature in all frames of a lifespan of the homology class.

6. The image analysis method of claim 5, further including a classification step (D) comprising:

computing a distribution of the characteristics computed during evaluation step (C) of topological features of the dynamical image, and combinations of the characteristics.

7. The method in claim 6, further including varying the dynamical image, prior to the execution of the classification step (C), by at least one of:

applying morphological operations to the dynamical image,

removing homology classes from the dynamical image, and

creating new homology classes in the dynamical image.

8. The method in claim 5 wherein the dimension of the homology class is 0 and a size of the homology class in a frame is an integral over components corresponding to the homology class.

9. The method in claim 5 wherein a size of the homology class in a frame is an integral over an element of the homology class.

10. The method in claim 5 wherein a predetermined combination of sizes of the homology class in all frames of the lifespan of the homology class is a sum of the sizes.

11. The method in claim 10 wherein:

the dynamical image is a sequence of binary images created by thresholding a gray scale image,

a parameter of the dynamical image is the threshold of the gray scale image,

the homology class is that of an object in the image,

a size of the homology class in a frame is an area of the object in the frame,

whereby the method evaluates an importance of the object as a volume of a region bounded by a part of a graph of a gray scale function over the object.

12. The method in claim 10 wherein:

the dynamical image is a sequence of binary images created by thresholding a gray scale image,

a parameter of the dynamical image is a threshold of the gray scale image,

the homology class is that of an object in the gray scale image,

a size of the homology class in all frames of the lifespan of the homology class is equal to 1, and

whereby the method evaluates the importance of the object as a contrast thereof.

13. The method in claim 10 wherein:

the dynamical image is a sequence of frames of a video,

a parameter of the dynamical image is a number of the frame,

the homology class is that of an object in the video,

a size of the homology class in all frames of a lifespan of the homology class is equal to 1, and

whereby the method evaluates an importance of the object as an amount of time it is present on a screen.

14. The method in claim 10 wherein:

the input image is a gray-scale image that represents an object,

a first parameter of the dynamical image is a threshold of the gray-scale image of the object,

a second parameter of the dynamical image is a number of morphological operations applied to each threshold,

a size of the homology class in all frames of a lifespan of the homology class is equal to 1, and

whereby the method evaluates a perceived integrity of the object in terms of a likelihood of appearance of the homology class, such as a break, a tunnel, or a void, resulting from a loss of density.

15. The method in claim 14 wherein:

the homology class is a 0-homology class of a collection of points in the object,

whereby the method evaluates a degree of integrity of the object in terms of a likelihood of a loss of connectivity between a plurality of parts of the object, as a measure of resistance of the object to fracturing between the parts resulting from a loss of density.

16. The method in claim 14 wherein:

the homology class is a 1-homology class of a closed curve in the object,

whereby the method evaluates a degree of integrity of the object in terms a likelihood of a loss of separation of areas outside of the object adjacent to two opposite sides of a membrane on a closed curve contained in the object, as a measure of resistance of all such membranes to a tear resulting from a loss of density.

17. The method in claim 14 wherein:

the homology class is a 2-homology class of a closed surface in the object, and

whereby the method evaluates a degree of integrity of the object in terms a likelihood of an appearance of a bubble inside a closed surface, as a measure of resistance of a region bounded by the closed surface to an internal tear resulting from a loss of density.

18. The method in claim 3 wherein the frames are subcomplexes of a same cubical complex which is a rectangular array;

the analyzing in step (B) is executed by a method comprising the substeps of;

a) designating a frame from the set of frames as a designated frame;

b) representing the designated frame by an array N, wherein each entry in the array N has a value selected from 0 and 1;

c) selecting a frame adjacent to the designated frame and representing the adjacent frame by an array P, wherein each entry in array P has a value selected from 0 and 1;

d) selecting a cell of the designated frame as a selected cell;

e) after each substep (d), reading an entry Q in P and an entry R in N corresponding to the selected cell;

f) after each substep (e), if Q=0 and R=1, adding the selected cell to the designated frame; and

if Q=1 and R=0, removing the selected cell from the designated frame;

g) after each substep (f), updating a set of homology groups of the designated frame;

h) repeating substeps (d), (e), (f), and (g) until each cell in the designated frame has been selected as the selected cell; and

i) for each adjacent frame after completing substeps (d), (e), (f), (g), and (h) updating a set of homology groups of the adjacent frame;

whereby the set of homology groups of the designated frame is incrementally computed as cells are added and removed resulting in the computation of the set of homology groups of the adjacent frame in terms of set of homology groups of the designated frame;

j) repeating substeps (a) through (i) with a different frame as the designated frame until each of the set of frames has been designated.

19. The method in claim 18 wherein the set of homology groups is updated in substep (g) by a method comprising:

(i) in order to add a k-cell C;

computing its boundary B=D*C;

if there is a (k−

1)-generator A homologous to B or −

B, removing the homology class [A] of A provided k>

1;

if there is no such A, finding a k-chain K such that B=D*K, and adding the homology class [K−

C] of K−

C;

(ii) in order to remove a k-cell C;

computing its boundary B=D*C;

if there is a k-chain L with its boundary D*L homologous to B or −

B, removing the homology class [C−

L] of C−

L;

if there is no such L, adding the homology class [B] of B provided k>

1.

20. The method in claim 18 wherein the dimension of the image is equal to 2 and the set of homology groups are updated by a method comprising:

I. to add a 2-cell C having a plurality of vertices and a plurality of edges to the image;

(1) add each of the plurality vertices of the cell C unless a vertex is a vertex of another cell,

(2) add each of the plurality of edges unless an edge E is an edge of another cell following a rule comprising;

if the edge E connects two different 0-cycles, merge the two different 0-cycles into a new 0-cycle;

if the edge E connects a 0-cycle to itself, split the 0-cycle into a new 1-cycle and a new 0-cycle; and

if the edge E connects a 1-cycle to itself, split the 1-cycle into two new 1-cycles, and

(3) add the cell C itself by removing a 1-cycle consisting of its plurality of edges of the cell;

II. to remove a cell C having a plurality of edges and a plurality of vertices from the image;

(1) remove the cell itself by creating a 1-cycle consisting of the four edges of the cell,

(2) remove each of the plurality of edges provided an edge E is not an edge of another cell following a rule comprising;

if the edge E is a part of a 0cycle and a part of a 1cycle, merge the 0cycle and the 1-cycle into a new 0cycle;

if E is only a part of a 0-cycle, split the 0-cycle into two new 0-cycles;

if E is part of two 1-cycles, merge the two 1-cycles into a new 1-cycle, and

(3) remove each of the plurality of vertices of the cell C unless the vertex is a vertex of another cell.

21. The method in claim 2, further comprising:

computing topological features of the complements of the frames.

22. The image analysis method of claim 2, further comprising:

computing topological features of each of the frames relative to a part assigned to the frame.

23. The method in claim 2 wherein the topological features computed by the analyzing step (B) are a set of cohomology groups of the frames.

24. The method in claim 2 wherein the topological features computed by the analysis step (B) are the homotopy groups of the frames.

25. The method in claim 2 wherein:

the input image is a t-dimensional array of objects with s-vectors assigned to their points, and

the input processing step (A) is executed by creating the dynamical image with t temporal parameters and s color-like parameters, by following the procedure;

if a k^th component of a vector assigned to a point is larger than or equal to a value of the k^th color-like parameter, the point is included in a binary image that is a frame of a dynamical image corresponding to a given combination of parameters, whereby the method will convert an image with s parameters into a dynamical image.

26. The method in claim 2, further comprising a simplification step (D) comprising:

removing a topological feature from the dynamical image if the entry, created by the analyzing in step (B), corresponding to a topological feature is marked as inactive,

whereby the method will provide the user with complete control over a simplification process.

27. The method in claim 26 wherein:

the input image is a time-dependent t-dimensional array of cell complexes with s-vectors assigned to each cell, further comprising an output processing step (E) executed by following a procedure;

for each cell of the dynamical image as a selected cell and for each p=1, 2, . . . , s, if the selected cell belongs to a k^th element of a sequence of cell complexes corresponding to a p^th color-like parameter of the dynamical image but not to a (k+1)^th element, then a p^th coordinate of a vector assigned to the selected cell is set equal to k, whereby the dynamical image will be converted into an original format of the input image.

28. The method in claim 2 wherein the input image is a sequence of images and further comprises a tracking step comprising substeps of:

a) detecting a set of objects as a set of topological features of the dynamical image;

b) computing a velocity for each of the set of objects and a rate of change of sizes and shapes of each of the set of objects;

c) predicting locations, sizes, and shapes of each of the set of objects in a next frame, and

d) matching each of the set of objects to a corresponding object in the next frame,

whereby the method will track objects in the sequence.

29. A method of creating a new subcomplex with Betti numbers within a specified range from a given subcomplex of an ambient cell complex by a topologically constrained transformation comprising the steps of:

A) creating a target subcomplex with Betti numbers within the specified range;

B) creating a current subcomplex as a copy of the given subcomplex;

C) repeatedly morphing the current subcomplex toward the target subcomplex by adding and removing cells of the current subcomplex and stopping no later than the Betti numbers of the current subcomplex fall within the specified range; and

D) repeatedly morphing the current subcomplex toward the given subcomplex as a new target subcomplex by adding and removing cells of the current subcomplex, so that each adding or removing step is cancelled if the step results in the Betti numbers of the current subcomplex outside the specified range of Betti numbers, until the current subcomplex does not change; and

whereby the method cuts the given subcomplex into pieces and adds other topological features to the given subcomplex providing a resulting subcomplex.

30. The method as claimed in claim 29 wherein morphing the current subcomplex toward the target subcomplex in steps (C) and (D) comprises a sequence of operations each selected from a group comprising:

a) adding to the current subcomplex a cell adjacent to the current subcomplex, provided the cell belongs to the target subcomplex, and

b) removing from the current subcomplex a cell adjacent to the complement of the current subcomplex, provided the cell does not belong to the target subcomplex.

31. The method as claimed in claim 29 wherein an empty subcomplex is chosen as the target subcomplex, whereby the method executes by erosion of the given subcomplex followed by topology preserving dilation.

32. The method as claimed in claim 31 wherein a cell is added unless this step creates a cycle that belongs to a given homology class, whereby the method removes the homology class from the subcomplex by breaking all cycles in the homology class.

33. The method as claimed in claim 31 wherein the range of Betti numbers is chosen to have the k^th Betti number larger than that of the given subcomplex, whereby the method creates a subcomplex with more k-homology classes than the given subcomplex.

34. The method in claim 33, further comprising creating a new subcomplex containing all cells, and faces of all cells, of at least one member of the new homology classes, whereby the method creates and extracts pieces and other homology classes from the subcomplex as cell complexes.

35. The method in claim 29 wherein the ambient cell complex is chosen as the target subcomplex whereby the method executes by dilation of the given subcomplex followed by topology preserving erosion.

36. The method in claim 35 wherein the given subcomplex comprises cells that contain points of a given point cloud located in an ambient cell complex, whereby the method represents the point cloud as a subcomplex with Betti numbers within the specified range.

37. The method in claim 35 wherein,

for a given k-homology class of an original cell complex, an ambient cell complex is chosen with the k-Betti number equal to 0,

the given subcomplex is chosen to comprise all cells of a predetermined collection within the k-homology class and their faces, and

the method further comprises a step of:

adding the resulting subcomplex to the original cell complex, whereby the method removes the given k-homology class from the original cell complex by adding a collection of (k+1)-cells that will close the k-homology class with a membrane, leaving a rest of the original cell complex unaffected.

38. A method of removing a plurality of frames from a dynamical image, comprising, for each frame A in the plurality of frames, the steps of:

A) finding all topological features in the frame A that have a predetermined plurality of combinations of characteristics outside given ranges;

B) removing the topological features found in step (A) from the dynamical image;

C) choosing a set of one or several frames adjacent to the frame A and adding each cell of the frame A to the set of one or several frames;

D) updating an adjacency relation of the dynamical image by making each pair of frames adjacent to the frame A adjacent to each other; and

E) removing the frame A from the dynamical image.

39. The method in claim 38 wherein:

the dynamical image is an image given by an intensity function,

the plurality of frames is a plurality of values of the intensity function,

the topological features are objects in the frame A, and

the predetermined plurality of combinations of characteristics comprise contrasts and sizes of the objects, and

whereby the method provides a compression of a simplification of the image by reducing a number of bits per pixel.

40. A method of measuring a similarity of two aligned images, computed as a difference of a total size of a collection A of objects in one of the two aligned images and a total size of the collection B of all objects in an other of the two aligned images overlapping A, or zero if the difference is negative, added over all collections A in a given plurality of collections of objects.

41. The method in claim 40, further including:

varying the two aligned images by applying morphological operations to the two aligned images, removing homology classes from the two aligned images, and creating new homology classes in the two aligned images, prior to the execution of the method.

42. A method of finding a point in each of two given images represented by density functions f(x) and g(y) respectively, where x is a position in a first image and y is a position in a second image, as a way to align the first image and the second image, comprising the steps of:

A) finding the centers of mass a and b of the first image and the second image;

B) choosing a function of two variables p(z,r);

C) creating two new density functions F(x)=p(f(x),|x−

a|)) and G(y)=p(g(y),|y−

b|)), where |x−

a| is a distance from x to a, |y−

b| is a distance from y to b; and

D) computing centers of mass c and d of the first image and the second image with densities F(x) and G(y), respectively; and

whereby the method assigns a new density value to each pixel depending only on its current density and its distance to a in the first image and b in the second image, and provides a pair c, d of aligned points for each choice of the function p.

43. The method in claim 42, further including:

varying the first image and the second image by applying morphological operations to the first image and the second image, removing homology classes from the first image and the second image, and creating new homology classes in the first image and the second image, prior to the execution of the method.

44. A method of evaluating a saliency of a topological feature in an image of an object given by a density distribution function comprising computing the probability that a cycle corresponding to the topological feature is not homologous to zero, whereby the method evaluates a probability of a loss of integrity of the object.

45. The method in claim 44, further including

varying the image by applying morphological operations to the image, prior to the execution of the method.

46. The method in claim 44 wherein:

the cycle is a 0-cycle of a plurality of points in the object, and

whereby the method evaluates a probability of a loss of connectivity between a plurality of parts of the object, as a measure of resistance of the object to fracturing between the plurality of parts.

47. The method in claim 44 wherein:

the cycle is a 1-cycle of a closed curve in the object, and

whereby the method evaluates a probability of a loss of separation of areas outside of the object adjacent to two opposite sides of a membrane on a closed curve contained in the object, as a measure of resistance of all such membranes to a tear.

48. The method in claim 44 wherein:

the cycle is a 2-cycle of a closed surface in the object, and

whereby the method evaluates a probability of an appearance of a bubble inside a closed surface, as a measure of resistance of a region bounded by the closed surface to an internal tear.