G12 Differential Topology of Image Segmentation and Invariance

This part of the course is based on the paper of Thomas J. Tsao and Doris Y. Tsao, A topological solution to object segmentation and tracking (Proc. Natl. Acad. Sci. U.S.A. 2022).

Segmentation and invariance

Vision has to solve two basic problems:

• the segmentation problem: how the visual pixels of a single image are grouped into distinct objects;
• the invariance problem: how objects can be identified across images despite their changing appearance.

The slides illustrate both with photographs (from Tsao–Tsao): (A) a close-up of overlapping variegated leaves with three circled points, where one has to decide which of the points lie on the same leaf; (B) three photographs of the same horse, seen from the side, from behind and from the front. The main problem of invariance is that the appearance of the same object can change drastically with a change in perspective.

One could hand-pick multiple views of the same object and train classifiers to perform view-invariant detection. This delegates the problem to the hand-picker responsible for the training, which is the same biological visual system one wants to understand. The main idea of the mathematical approach is instead:

• segmentation of an image into separate surfaces through the detection of occluding contours (the spatial separation of visible surfaces);
• tracking of invariant surfaces through the detection of stereo diffeomorphisms (the overlap relations between surfaces visible from different views).

There are two aspects of the problem:

1. how surfaces in space are projected into ray spaces, and how diffeomorphisms in ray spaces encode surfaces;
2. how to compute these diffeomorphisms from images.

The first is an “encoding” problem, mathematically well posed; the second is a “detection” problem, subject to noise and ambiguity. The basic object is the perspective projection, a map from a 2D surface to a 2D ray space. Differential topology lets one view perspective projections as 2D-to-2D diffeomorphisms on regular domains separated by critical points.

A figure from Tsao–Tsao summarizes the framework in four panels, each pairing a photograph of a variegated leaf with a schematic drawing: (A) points project to ray space (a point seen from is recorded by two spherical angles); (B) surface contiguity is faithfully encoded (a surface patch carrying a letter “A” projects to domains , in the ray spaces of two observation points , , related by a map ); (C) at an occluding contour local diffeomorphisms break down, with an “owner side” of the contour and an accretion region on the other side; (D) surface persistence (a surface carrying “A B C” is followed through a chain of observation points by maps , , ).

The main properties of the approach:

• 3D space is mapped homeomorphically, through biprojection, onto a 3D submanifold of the product of a pair of 2D ray spaces;
• a scene in 3D space is a collection of 2D surfaces, and these are also mapped continuously into the product of two ray spaces;
• the topology of the surfaces is coded by perspective transformations between pairs of ray spaces;
• a mapping from a domain in one ray space to another ray space fully specifies a surface in the 3D environment;
• there are conditions under which partial samples can be associated with a single surface;
• transition vectors model movements of the eye and perspective transitions: perspective mappings and occluding contours are derived from changes of images.

Ray spaces and perspective projection

The groupoid of movement in observation space

Not all rigid motions of the ambient are available as shifts of perspective of the observer: the observer’s motion is restricted by the scene. One considers the set of arrows corresponding to the allowed motions, with a composition rule (the source of the next arrow equals the target of the previous one). This is a groupoid.

The perspective transition groupoid has as arrows the triples with and a rigid motion of that maps to . (A refined version, in which the arrows also act on rays, is given in the second half of these notes.)

Stereo projection

The product is a 4D space, and a stereo set is a 2D surface in this 4D space.

The figure shows the geometry of a perspective transition and the stereo projection (biprojection) of a point of the visual scene: projects to and to ; and are the points where the baseline meets the two spheres, and , are the angles between the baseline and the two rays.

Now take a domain and a diffeomorphism , applied as , which maps to a diffeomorphic image in . Its graph is a 2D submanifold embedded in the 4D space . Thus in a perspective transition the stereo projection encodes a surface, without loss of information, as a 2D submanifold of .

The slides illustrate this with a picture from Tsao–Tsao: a curved surface carrying a letter “A”, seen from two observation points. The patch projects to domains and on the two ray-space spheres, where the letter appears distorted in two different ways, and the two domains are related by the stereo diffeomorphism .

Occluding contours

Almost all points of a ray space are regular with respect to a perspective projection: they are regular values, since by Sard’s theorem the critical values of a differentiable map form a set of measure zero.

The slide’s cartoon shows the ray-space sphere of an observer and a cone of rays grazing a small round object; the cone continues past it and meets a background object (a cloud) along a ring.

In the figure, the point is on an occluding contour for but is a regular point for : the ray from through is tangent to the object, while the ray from crosses the object’s boundary transversally at (the occluding contour for is at ).

Singularities: folds and cusps

The relevant theory of singularities is in H. Whitney, On singularities of mappings of Euclidean spaces. I. Mappings of the plane into the plane (Annals of Mathematics 1955), and in V. I. Arnold, Catastrophe Theory (Springer 1984).

The slides use Arnold’s pictures. First, the fold of the projection of a sphere onto the plane:

Second, the cusp of the projection of a surface onto the plane. Arnold’s picture shows a pleated surface over the plane, its fold curve, and the image of the fold curve in the plane, which has a cusp. Here it is drawn for the normal form , given further below: the critical points form the parabola , whose image is a semicubical cusp.

Both singularities appear as occlusion contours. For a torus, the apparent contour consists of an outer fold curve and inner fold curves that end in cusps:

• Every point in a border of accretion is a critical value of the perspective projection.
• The singularities of a projection from a surface to the ray space are either fold points or cusp points (at the end of a fold contour).

Ownership of occluding contours

Figure–background perception problems show that a contour in a 2D image may be ambiguous as to which side it belongs to. The slide shows the classical black vase on a white background, whose outline can also be seen as two faces in profile. This ownership problem arises with 2D images, but it is usually resolved when one is allowed to change perspective (mapping 3D space with biprojections to ).

Accretion

The observation point moves from to , the occlusion contour point moves from to , and the accretion area is spanned by the angle in . The figure also marks the angle in spanned by the piece of the background that becomes visible from .

Illusory contours versus occluding contours

In a segmentation of a 2D image some contours are “illusory”: they do not separate different objects in 3D space. The slides show an example from Tsao–Tsao: two frames of a cluttered scene, their edge maps, and two kinds of contour segments compared between the frames. For a texture segment, the image regions on both sides of the contour map diffeomorphically from one frame to the other. For an occluding segment, the region on one side (the owner side) maps diffeomorphically, and the region on the other side does not.

The regions of a 2D image on the two sides of a contour can be seen as surfaces with boundary. A change of perspective maps them to two other regions, each the image under a diffeomorphism of surfaces with boundary. These two diffeomorphisms may or may not be restrictions of a single diffeomorphism of a 2D surface without boundary:

• if they glue, the contour is an illusory contour;
• if they do not glue to a single diffeomorphism, the contour is an obstruction (occluding) contour, with an intervening accretion region.

The slides illustrate the gluing with a standard picture: two manifolds with boundary , , with half-disc neighbourhoods , of boundary points glued by a diffeomorphism of the boundaries (); charts and to half-spaces; maps , between the two half-spaces; and the resulting chart in of the glued manifold.

• In a perspective transition, accretion and deletion happen only on the background side. This disambiguates the image–background ownership problem.
• Given a set of frame images of the same scene from varying observation points, there is a set of associated perspective transitions . Surfaces in the 3D scene have projection images and , related by the maps , where is the map induced by the transition as above.
• The contours on and the accretion zones on determine the occlusion contours and border ownership.

Computational aspect: receptive fields

The question is how receptive fields solve the correspondence problem between images taken from different perspectives. The slide shows vertically oriented Gabor filters (Gaussian envelopes times sinusoidal gratings), even and odd, as grayscale images: a pair , , and four further pairs , with , each a pattern of a few vertical light and dark stripes.

In a perspective transition, the measured response (to first-order approximation of the deformation) is a shift of the Gabor frame of a simple cell’s receptive field, apparently following an energy minimization process. The slides show measured changes of the receptive field of one Gabor simple cell: a stereo pair of aerial photographs of terrain, with a bar marking the receptive field, and below them a row of five receptive-field profiles .

Further mathematical considerations on the Tsao–Tsao model

Recall the two main geometric aspects of the problem:

1. how surfaces in space are projected into ray spaces, and how diffeomorphisms in ray spaces encode surfaces;
2. how to compute these diffeomorphisms from images.

The first is an “encoding” problem, mathematically well posed; the second is a “detection” problem, subject to noise and ambiguity.

• Perspective projection: a mapping from a 2D surface to a 2D ray space; differential topology gives 2D-to-2D diffeomorphisms on regular domains separated by critical points.
• Stereovision: two independent 2D ray spaces, and a mapping of 3D space to a submanifold of the 4-dimensional product of two ray spaces; the topology of surfaces is encoded through “perspective transformations” between ray spaces.

Geometries

• A ray is a half-line in Euclidean 3D space; the ray space is the 2D sphere (half-lines, so not ).
• The visual space is the sphere bundle with projection and fiber over : the points of (open and connected) together with the set of all possible observation directions (rays).
• The rigid motions form the special Euclidean group , with
• A change of perspective: observation points are related by a rigid motion of the ambient that moves to . It also acts on the visual space sphere bundle , mapping rays to rays .

The perspective transition groupoid

From here on denotes the region of the visual scene, and observation points lie in its complement.

Ray projections

• For an observation point and any point in , the ray projection is the ray in pointing in the direction of .
• For a region and different observation points , the stereo-projection (biprojection) map is
• Let be the straight line in that contains and . The map fails to be injective along , and gives an embedding
• A 2D surface has image , embedded in the 4D space .
• The restrictions to of the projections of to the two factors give smooth projections between 2D spaces.
• We generally assume that the visual scene is limited in 3D, so that it does not simultaneously meet all ray directions from the observer: for some direction .

Correspondences

A function is a correspondence, given by its graph . So correspondences can be viewed as more general “multivalued” functions.

Functions and have a composition , and the graphs and compose as where the are the projections of onto the pairwise products. This suggests the general definition.

When working with smooth manifolds this requires the intersection to be a smooth manifold. This is not always true, but transversality in differential topology ensures that it is “generally true”.

Transversality

If and intersect transversely in , then their intersection is a smooth manifold.

Transversality of and can be achieved by taking with submersions. General transversality then implies that, up to small deformations of the embeddings, the pullbacks and intersect transversely in the triple product .

Whitney’s theorems

By transversality, is a smooth manifold, and we then have the map Assume for simplicity and (the more general case is similar). Then the restriction of the projection is a map of an -dimensional manifold to a -dimensional manifold.

First deform slightly to an immersion with double points (with a sign, from the orientations). Then the Whitney trick: pairs of double points with opposite signs can be cancelled by deforming the immersion (and a small deformation can create a pair of opposite double points). This works when and the ambient manifold is simply connected; for , surfaces in a 4-manifold such as , the Whitney trick can fail.

The slide illustrates the trick with plane curves: a figure-eight curve has one double point; a small deformation adds a kink, creating a second double point; the region between the two double points (shaded) is then pushed across and shrunk until both double points disappear, leaving an embedded closed curve.

So, possibly after a smooth deformation, is an embedding of an -dimensional submanifold in .

• Equivalence classes of correspondences : correspondences are taken up to the equivalence that allows such deformations to achieve transversality and embeddings.
• Semigroupoid: in general correspondences are not invertible, so composition gives a semigroupoid (arrows with an associative composition, as in a groupoid, without inverses); the invertible correspondences are (equivalent to) graphs of diffeomorphisms.

Correspondences and visibility

• Correspondences are given by surfaces inside the product .
• The sub-correspondence accounts for the visibility condition for with respect to the observation points .
• Let be a non-transparent part of a visual scene. A visible point is one such that the ray from to contains no other point of ; these form the visible scene.
• For there are two visible surfaces, and .

Assume the surfaces , and are compact and smooth (possibly with boundary). Then the correspondences are also smooth surfaces in , and the ray projections are smooth maps between smooth 2D manifolds (possibly with boundary).

Critical sets and stable types

These are the fold and the cusp pictured earlier. The local quadratic or cubic equation near folds and cusps means that the fiber of the projection consists in general of two points near a fold curve, or three points near a cusp: only one of these points is in the visible surface . The fold curves (with their cusp endpoints) are the occluding contours of the visual scene.

The presence of folds and cusps for the two projections and detects how far the correspondence is from being the graph of an invertible function. When occluding contours are present, the correspondence describing the change of perspective fails to be the graph of a diffeomorphism.

Surfaces with boundary and accretion

• One uses the visible-surfaces correspondence instead of the whole .
• The surfaces and have boundary, and the boundary partly overlaps with the occluding contours of the projections and of .
• These are surfaces with boundary in the sense defined above: local charts , homeomorphisms of with open sets of (topology induced from ), with smooth coordinate changes , where smooth near a point of means extending to a smooth map on a neighborhood in .

The regions of a 2D image on the two sides of a contour are surfaces with boundary, mapped by the change of perspective to two other regions (each the image under a diffeomorphism of surfaces with boundary). As in the gluing picture above:

• if the two maps are restrictions of a single diffeomorphism of a 2D surface without boundary, the contour is an illusory contour;
• if they are not restrictions of a single diffeomorphism (they do not glue to a surface without boundary), the contour is an actual obstruction contour.

So the accretion region disambiguates image/background ownership and illusory/real contours.

The thin semigroupoid of ray projections

Consider the correspondences from the ray projections of a surface in visual space, Their composition satisfies provided each ray from the intermediate point meets at most once. In general the left-hand side also contains the pairs with two points of on the same ray from , and only the inclusion holds.

It just keeps track of the changes of stereo-perspective on a fixed surface in the visual scene.

The semigroupoid of visibility under ray projections

Now consider the correspondences with the visibility condition, The visibility condition creates a problem with composition: one only has (instead of ) since a point visible from and need not be visible from the intermediate point . To have composability (a semigroupoid structure) one needs to add the correspondences describing the part of the surface that remains visible from all the given intermediate viewpoints. This is a richer structure than the thin semigroupoid of the .

References

• Thomas J. Tsao, Doris Y. Tsao, A topological solution to object segmentation and tracking, Proc. Natl. Acad. Sci. U.S.A. 119 (41) (2022) e2204248119.
• H. Whitney, On singularities of mappings of Euclidean spaces. I. Mappings of the plane into the plane, Annals of Mathematics 62 (1955) no. 3, 374–410.
• V. I. Arnold, Catastrophe Theory, Springer, 1984.