Image analysis – Color image processing
Reexamination Certificate
2000-09-11
2002-05-28
Mehta, Bhavesh (Department: 2621)
Image analysis
Color image processing
C382S199000, C382S242000, C345S441000
Reexamination Certificate
active
06396947
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the conversion of a raster image into a vector format, particularly to an apparatus and method for converting a raster image comprising a plurality of pixels into a plurality of data tags representing at least one shape in the raster image.
BACKGROUND OF THE INVENTION
Image processing generally refers to the manipulation of pictorial data using computers. Computer Aided Design (CAD) is one example of how computers are used to draft complex engineering drawings such as mechanical, architectural or electrical drawings. Other examples of image processing include the manipulation of still photographs or cinema to achieve various effects such as feature enhancement, three-dimensional rendering, or animation. However, the term “image processing” is not limited to pictures it generally refers to the digitization and computer processing of any analog signal that represents something physical and perceptible in the world. An audio signal can be digitized and processed with computers to perform manipulations such as noise reduction or voice recognition; modulated electrical signals, such as telecommunications or cardiograms, can be digitized and processed by computers to extract pertinent information, and so on. The common factor in image processing is the need to digitize the continuous-time analog signal into a discrete-time digital signal that can be operated on by computers using boolean mathematics implemented in transistor logic circuits.
A common format for storing and manipulating digitized signals is simply to represent the digital data as a bit-map of pixels, where each pixel represents a particular characteristic (e.g., magnitude or color) of the analog signal. Typically, a picture is digitized into a bit-map of individual pixels where each pixel represents a color of the image in a very small, localized area. When the pixels are displayed as a congregation, the original picture appears without loss of perception to the human eye as long as there is sufficient resolution (number of pixels) both in spatial and color contexts. A black and white picture can be represented with one-bit pixels, where the state of the bit (
0
or
1
) represents the two colors, black and white. To digitize a picture comprising multiple colors, each pixel is represented using n-bits such that each pixel can take on one of
2
n
different colors. The process of converting an analog image into a bit-map image is referred to as “rasterizing” the image.
There are several well known problems with raster images that limit or inhibit the full potential of computer manipulation. The amount of memory necessary to store a large photograph having many colors (thousands or even millions of colors) can be immense, and the problem is exacerbated when attempting to digitize a series of photographs such as a scene in a movie. Not only do raster images require large amounts of storage memory, but processing such a large amount of data can be slow, particularly when attempting to transfer raster images over a network such as the Internet.
Another problem inherent with the raster format is an inability to perform many of the desired image processing functions, such as three-dimensional rendering or animation. Even a simple operation such as magnifying the image results in a granular distortion caused by enlarging the pixels of the image as illustrated in FIGS.
1
A and
1
AA. It is possible to perform digital signal processing when magnifying a raster image by effectively re-sampling the image to attenuate the granular distortion that occurs due to the fixed resolution. However, this process only reduces the granular distortion rather than eliminate it. Furthermore, resampling the image is time consuming and not practical in many applications. Other operations, such as electronic focusing and automatic imaging, are simply not possible when the image is stored in a raster format.
The alternative is to convert the raster image into a mathematical format known as vectors. A vector is a mathematical description of the image which is not constrained by a fixed resolution as with raster data. Furthermore, vectors allow for a much more diverse range of image manipulations due to the mathematical representation of the image. A simple example of a vector is a line beginning at a particular X,Y point in a Cartesian plane and ending at another X,Y point in that plane. To date, however, converting raster images into a series of linear vectors has been largely unsuccessful. This is due to the immense number of different possible patterns that raster images can form. For example, a 3 by 3 pixel matrix of a nine color picture can take on about 21,000 different possible patterns. Each possibility must be accounted for when converting the image into a set of linear vectors. If just one more pixel is added to the matrix, the complexity increases exponentially. Consequently, techniques for converting raster images into linear vectors normally operate on only a small section of the image at a time. The problem with this approach is that the resulting vectorized image appears fragmented due to discontinuities when the individual sections are combined.
There have been other attempts to convert a raster image using vectors that are more abstract mathematical representations. For example, a technique referred to as wavelets attempts to represent the raster image as a series of interconnected mathematical equations. With wavelets, a particular feature of the image might be represented using a number of polynomials which approximate the feature contours. The problem with this technique, however, is that the equations become extremely complex unless the operation is constrained to only a small group of pixels. But again, distortion due to fragmentation occurs when attempting to combine the individual equations into a complete image. A similar distortion occurs with using fractals, a method where the image is represented using a library of different shapes which approximate the various features of an image. Similar to wavelets, however, discontinuities occur with fractals when attempting to combine the individual shapes which causes distortion due to fragmentation.
Another known method for raster to vector conversion, referred to as the Automatic Bezier Curve technique, draws Bezier curves through tags that are placed somewhat arbitrarily on the image. Unlike fractals or wavelets, Bezier techniques cannot convert complicated pictures without losing information. On the other hand, the Bezier technique can sequence equations together over a large number of pixels which reduces the amount of fragmentation typically associated with other techniques.
The Bezier method is illustrated in FIG.
1
B. The first step is to identify the color borders for each feature in the image, and then to place somewhat arbitrarily tags on the borders. These tags then become the new representation of the image. When the image is to be displayed, these tags are converted into a rasterized format by drawing Bezier curves through the tags as shown in FIG.
1
B. The problem with the Bezier conversion technique is that it has a hard time dealing with complicated images. When tags are placed some definition is lost. In a complex image, many tags are placed resulting in a great deal of loss in picture definition. Even more severe is that the Bezier technique only looks at simple borders. In complex images, there is usually an interaction of shades that catch the eye. The Bezier curve technique treats all of these different shades as either borders or points. This often results in a vector representation that is more complicated than a raster representation; in effect, the Bezier solution can actually be worse than the problem.
There have been other attempts to represent the feature contours of an image using mathematics capable of spanning more than just a small area on the image. For example, U.S. Pat. No. 4,777,651 discloses a method of pixel-to-vector conversion where the line and edge features of the image are converted
Colorcom Ltd.
Mehta Bhavesh
Sheerin Howard H.
Sherali Ishrat
LandOfFree
Placing tags on surface string sequences representing a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Placing tags on surface string sequences representing a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Placing tags on surface string sequences representing a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2872920