The spatial critical points of an image are defined by the zeros of the gradient. They may be embedded on a discrete grid, but, in general, they do not coincide with the grid points. Rather, they lie somewhere in between them. This paper examines the influence of the structure of the grid, with respect to detecting all critical points, including maxima, minima, and saddle points.

The distribution of critical points of different types on a manifold M of genus g is related to the Euler number &khgr;(M) = 2(1 - g) = m₊ - s + m_-, where m₊, s, and m_- are the numbers of maxima, saddle points, and minima, respectively. This formula is closely related to Euler’s formula for polygonal tessellations, where &khgr;(M) = 2(1 - g) = v - e + f, where v, e, and f are the numbers of vertices, edges, and faces, respectively. Increasing or decreasing the scale of the grid may result in the annihilation or creation of critical points in pairs, such that the Euler number is unchanged. Therefore, each annihilated pair must include exactly one saddle point, and one extremum (maximum or minimum). The creation and annihilation of pairs of critical points can be the basis for deriving a unique rooted ordered binary tree from the Gaussian scale space image that represents the image in a topological sense. In addition, when the scale of the grid is considered as a third dimension, the critical points form curves in scale space.

There are only three types of planar, symmetric, or isotropic two-dimensional point grids, namely, square, triangular, and hexagonal grids. The triangular grid has a dual relationship to the hexagonal grid, and is the least suitable of the three for neighborhood relations related to critical point analysis. Furthermore, the hexagonal grid is found to be highly preferred in finding saddle points in two dimensions, for two reasons. First, the hexagonal grid respects the Euler number &khgr;(M) defined above, and guarantees that all saddle points are located. Second, for a hexagonal grid, the saddle points can be unambiguously assigned to the cells corresponding to pixels. Furthermore, the hexagonal critical point detection can easily be transferred to a rectangular grid, by artificially translating each even row of the image by a half-cell.

The procedure discussed in this paper is limited to two dimensions. The situation becomes very complicated in three dimensions. Mathematically, this problem relates to the optimal tiling problem dating back to Kepler in 1611, who conjectured that the face-centered cubic lattice was the most efficient of all arrangements. Implementation of this structure is possible, but complicated. There have been recent attempts to study similar tessellations using truncated octahedral and rhombic dodecahedral tilings.