A scheme for resampling binaryimage data from a rectangular grid to a regular hexagonal grid and an associated tree - structured pixel - indexing scheme keyed to the level of resolution have been devised. This scheme could be utilized in conjunction with appropriate image - data - processing algorithms to enable automated retrieval and/or recognition of images. For some purposes, this scheme is superior to a prior scheme that relies on rectangular pixels: One example of such a purpose is recognition of fingerprints, which can be approximated more closely by use of line segments along hexagonal axes than by line segments along rectangular axes. This scheme could also be combined with algorithms for query - image - based retrieval of images via the Internet.

The Tree-Structured Indexing Scheme provides information on both locations and levels of resolution. In each group of seven pixels that constitute one pixel at the next coarser level of resolution, the zeroth pixel is the central one.
A binary image on a rectangular grid is generated by raster scanning or by sampling on a stationary grid of rectangular pixels. In either case, each pixel (each cell in the rectangular grid) is denoted as either bright or dark, depending on whether the light level in the pixel is above or below a prescribed threshold. The binary data on such an image are stored in a matrix form that lends itself readily to searches of line segments aligned with either or both of the perpendicular coordinate axes.

The first step in resampling onto a regular hexagonal grid is to make the resolution of the hexagonal grid fine enough to capture all the binary-image detail from the rectangular grid. In practice, this amounts to choosing a hexagonal-cell width equal to or less than a third of the rectangular-cell width. Once the data have been resampled onto the hexagonal grid, the image can readily be checked for line segments aligned with the hexagonal coordinate axes, which typically lie at angles of 30°, 90°, and 150° with respect to say, the horizontal rectangular coordinate axis. Optionally, one can then rotate the rectangular image by 90°, then again sample onto the hexagonal grid and check for line segments at angles of 0°, 60°, and 120° to the original horizontal coordinate axis. The net result is that one has checked for line segments at angular intervals of 30°. For even finer angular resolution, one could, for example, then rotate the rectangular-grid image ±45° before sampling to perform checking for line segments at angular intervals of 15°.

In the tree-structured pixel-indexing scheme, the smallest hexagonal pixels in nearest-neighbor groups of seven constitute larger pixels, which, in turn, are grouped into still larger pixels (see figure), and so forth, proceeding from the finest resolution to the coarsest. Each pixel is identified by a sequence of integers in order of increasing resolution. In other words, the first integer in an address denotes the coarsest pixel that contains the location in question, the second integer denotes whichever one of the seven subpixels of the coarsest pixel contains the location of interest, and so forth down to the last integer, which denotes the smallest hexagonal cell that contains the location of interest.

For some purposes — especially performing quick searches for images that match query images, it is useful to resample a binary image data from finer hexagonal grids onto coarser hexagonal grids. In such a case, each pixel at the next coarser level of resolution is made exactly hexagonal and considered dark if more than three of its seven component pixels are dark.

This work was done by Gordon G. Johnson of the University of Houston for Johnson Space Center. For further information, contact the Johnson Commercial Technology Office at (281) 483-3809. MSC-22901


NASA Tech Briefs Magazine

This article first appeared in the April, 2004 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.