RaveGrid: Raster to Vector Graphics for Image Data

Authors: Sriram Swaminarayan, Lakshman Prasad

We introduce RaveGrid ( http://www.lanl.gov/software/RaveGrid/ ), software that rapidly converts large, complex raster images comprised of pixels into vector images comprised of polygons of varying colors, shapes, and sizes representing image features. The vector representations, written as gzip compressed SVG files, typically have smaller file sizes than that of the corresponding raster images, can be scaled arbitrarily, and can be used to identify and tag objects in images based on the polygons constituting them.

Today, images are increasingly shared across computers, cell phones, TVs, Web pages etc., requiring compact file sizes for transmission and storage economy, quick and easy scaling to resolutions of various device screens, graphical and textual representations for incorporation into multimedia Web pages, and automated object identification for content-based search. Raster bitmap images, made up of pixels, are limiting in that, file sizes increase with image sizes, taxing storage and bandwidth resources. Scaling or rotating requires interpolation, taxing computing resources on small devices. They cannot be described economically in a Web language such as XML or SVG. Pixel-based representation is too primitive for describing content.

RaveGrid reduces millions of pixels to a few thousand polygons, typically resulting in significant data compression. Polygons are easily scaled without changing file size. Vector images are editable text files, seamlessly includable in multimedia Web documents. RaveGrid uses only a small subset of image pixels, namely edge pixels separating image features, to construct polygons by algorithms that emulate human visual perception. This not only enables rapid computation but also yields visually meaningful polygons. RaveGrid is at least ten times faster, and handles much larger images, than its competitors. In particular, satellite images are easily converted into vector images made up of polygons that conform to boundaries of image features. RaveGrid vectorizes images at about 0.5 megapixels per second on a Pentium 2.13 GHz laptop with 2 gigabytes of RAM.

RaveGrid is based on VISTA (Vectorized Image Segmentation via Trixel Agglomeration), a radically new, patented (US Pat. 7,127,104) method to decomposing images in terms of visually meaningful feature primitives. VISTA exploits both regional and edge cues in an image to obtain an efficient, data-adaptive representation using polygons instead of pixels. The essential idea behind this approach is the utilization of a sparse but salient subset of pixels in an image, namely edge pixels. These pixels, situated at feature boundaries, act as anchor points for a Delaunay triangulation of the image. The triangulation serves as an image-adaptive grid from which spatial relationships between feature boundaries can be computed. Based on these relationships, the triangles are then selectively merged to obtain polygons by means of grouping criteria that are modeled after perceptual organization principles, such as proximity, continuity, etc., long observed empirically in the workings of human vision.

In addition to significant data reduction, RaveGrid serves as a framework for extracting complex features by grouping polygons based on structural and spatial attributes computed from triangles comprising them, and developing automated feature detection and recognition algorithms. Indeed, the many digital images produced by devices ranging from simple point-and-shoot cameras to high-resolution image sensors on commercial and surveillance satellites have fostered a rapidly growing need to be able to identify the objects in a digital image. Large-scale survey and mapping of terrain for developing geographic information systems (GISs), content-based searching or blocking of images on the Internet are just a few applications that require object identification.

RaveGrid can be used to obtain geometric information about the structure of an image that can be easily combined in new ways to answer various queries about image content. The potential to address new queries with minimal recomputation on an image is important for developing the query-driven image search-and-retrieval engines of the future for the Internet and large databases. The underlying triangular composition of polygons produced by RaveGrid helps the software easily and readily compute a large and richly informative set of feature attributes such as relative sizes, color variability, linearity, shape structures, neighborhood connectivity, etc., that enable one to efficiently answer multiple queries about image content.