Adding Shape-Based Search Technology
New technology with implications for Automatic Target Recognition (ATR) in satellite imagery is being investigated in The Research Department at Space Imaging (Thornton, Colo.). Look Dynamics (Longmont, Colo.) has developed a technology that allows the encoding of image clips as shape information through optical processing. The resultant shape information from a number of images may be stored in a database for subsequent search. To search a shape database, a model image clip is passed through the encoding system to obtain its shape information, which is then used to find matches. The technology requires no knowledge of specific image objects (such as definitions for ‘airplane’ or ‘truck’) prior to the creation of the databases. Thus, an image needs to be passed through the optical engine only once to enable searching of its contents and does not require reprocessing when new search models are defined.
The availability of satellite data has increased tremendously in recent years. The advent of commercial satellites carrying high-resolution sensors has also increased the amount of data available for study and processing. Far more pixels exist than can be inspected by human eyes. Automated processing methods for analyzing these pixels are becoming more and more crucial as the manpower required to review those pixels further and further surpasses that which is available.
The technology developed by Look Dynamics could be part of a potential solution to this now-intractable problem. Encoding an image by its content, as shapes, could require significantly less storage than pixel data. Because the processing is optical, the generation of databases of such shapes is far faster than could be achieved by a comparable system based on conventional digital processing technology. Another key factor is that the nature of the search objects does not need to be known when the image encoding is done and the databases are generated. Entire archives of imagery could be encoded as shape representations for later object search and retrieval.
|Figure 1: Generation and storage of shape information(Charles deGaulle International Airport, Paris)|
The technology was originally created for image-based searches of the internet. The new exploration of this technology applies it to satellite imagery. We believe it may be applicable not only to wide-area search, but to feature extraction and change detection as well.
The majority of approaches to image storage and retrieval rely on some combination of color, texture and shape information extracted from the imagery. One texture-based approach (Puzicha et al. 1997) uses Gabor filtering to achieve image segmentation and subsequent image retrieval. Manjunath and Ma (1996) use Gabor filters to characterize texture as well, in conjunction with a user interface that allows the analyst to delineate a portion of an image (containing some uniform texture) to use as a query. There are also approaches which use color or shape information only. Stricker and Orengo (1995) attempt to improve the utility of color histogram measures for image indexing and retrieval by characterizing objects with the dominant features of the color distribution instead of the entire color histogram. Folkers and Samet (2002) use Fourier descriptors to approximate basic geometric shapes that, in some spatial arrangement, can characterize objects in a logo database.
The Look Dynamics system is unique in that it is an analog-based approach to a problem which has traditionally been approached from a purely software standpoint. The optical portion of the system can process 260 square kilometers in one second, a far greater speed than any software implementation.
To enable the searching of image databases by shape, Look Dynamics has developed technology combining analog and digital processing. This proprietary imagery has the potential to rapidly extract, store and search for patterns from all types of imagery. Look Dynamics’ new application has two components: an optical engine that extracts patterns from images and a database in which the pattern information is stored.
Various approaches to indexing images by shape have been proposed, but none have been sufficiently robust or fast to use in real-world applications. While a system may be able to handle a few thousand images, it will not scale to larger databases due to the processing required. This limitation is inherent to the complexity of extracting shapes and patterns from imagery. Algorithms implemented on digital processors are simply not fast enough. The Look Dynamics system uses an optical engine to carry out the shape extraction and encoding at optical speeds. This system does not perform optical correlation, and it does not use the optical engine for searching. Instead, the optical engine provides an encoding process that extracts a characterization of the shape information within an image. These characterizations, or “fingerprints,” are then stored in a database that can be searched in software.
With the Look Dynamics system, an image is brought in only one time. Preprocessing is performed on the image using a pair of Intel computers, and it is loaded into a custom electronic board that drives the input spatial light modulator (SLM) and controls system timing. The image is displayed on the SLM, and the shapes are extracted optically as a whole (not pixel-by-pixel) and detected on a photo-diode array. Another Intel computer takes the output of the photo-diode array and converts it to the shape fingerprint, which is stored in the database.
To “load” a satellite image into a Shape Feature Database, a full image is divided into subsections (image clips) that can be fed to the optical engine. These 512 x 512 pixel subsections are down-sampled to the SLM’s 8 bit resolution, then contrast stretched and edge enhanced before formation on the SLM. Laser light reflected off the SLM projects the image as collimated beams of light, which pass through a lens and onto Look Dynamics’ proprietary silicon chip, the Antilles. The Antilles chip breaks the image into Fourier components and reprojects them to an image sensor. Line segments “seen” at the sensor are stored as shapes in the database.
For each image clip, the shape characterization or fingerprint is extracted and stored in the database together with information about the source image and section number. In the future, the database should be able to contain shape-based characterizations of millions of images, prebuilt and waiting to be searched. When a client formulates a query, he can use an image or a (scanned) map or drawing. The query can ask for images and locations within them that match, contain, or are similar to the example. The system encodes the query example by shape using the optical processor and then searches the database for similar shapes. The query returns what it finds with a score or confidence measure.
Encoding of the imagery as shapes that can be searched upon and matched implies a number of applications for this technology. Wide-area search, feature extraction (roads, buildings or any of a number of natural or man-made objects), and change detection are all current problems that this technology may help solve.
Efficient shape database search implies that this technology could be used as a focus of attention for any of the aforementioned applications. Quickly narrowing in to areas likely to contain objects or changes which need to be identified or found would be an extremely effective prefilter. The kind of pixel-intensive processing necessary for accurate object identification or change detection is not feasible over large amounts of image data. The Look Dynamics technology could point the more compute-intensive algorithms to areas likely to contain content of interest. Using the optical processing technology in tandem with a suite of software-based solutions tailored to individual applications could create a powerful hardware-software hybrid technology for a number of image-processing applications.
Space Imaging and Look Dynamics have worked together to adapt this technology for satellite imagery. We have established a performance baseline using a number of IKONOS image clips. Following an initial round of investigation, we have identified areas for improvement. We are currently involved in modifying the system to incorporate these improvements and plan to periodically re-evaluate system performance as the improvements are made. We look forward to realizing the full potential of this technology and the opportunity to utilize it in conjunction with IKONOS data for image processing applications.
Folkers, A., and H. Samet, “Content-Based Image Retrieval Using Fourier Descriptors on a Logo Database,” 16th International Conference on Pattern Recognition, vol. 3, August 2002, pp. 30,521-30,524.
Manjunath, B. S., and W. Y. Ma, “Texture Features for Browsing and Retrieval of Image Data,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(8), August 1996, pp. 837-842.
Puzicha, J., T. Hofmann, and J. M. Buhmann, “Non-Parametric Similarity Measures for Unsupervised Texture Segmentation and Image Retrieval,” Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition, San Juan, June 1997, pp. 267-272.
Stricker, M., and M. Orengo, “Similarity of Color Images,” SPIE Conference on Storage and Retrieval for Image and Video Databases III, vol. 2420, February 1995, pp. 381-392.