Image analysis – Image transformation or preprocessing
Reexamination Certificate
1999-02-24
2003-06-10
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image transformation or preprocessing
C365S189011, C345S648000
Reexamination Certificate
active
06577776
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention generally relates to digital images, and more particularly, to transforming a video image and writing the transformed image to a random access memory.
Video programs represent individual images digitally with an ordered array of pixels. Each pixel has an associated value, e.g., three color intensities, that can be represented as a vector of binary digits. Often, the creation of a video program entails the manipulation or spatial transformation of an original digital image or portions thereof to produce a new digital image. The transformation uses the original values of the pixels to generate the new values of the pixels.
FIG. 1
illustrates the action of a spatial transformation on a Cartesian array of square pixels, e.g., the pixel P. The transformation includes a 2-dimensional (2D) translation and rotation. The transformation sends an original point X,Y into a new point X′, Y′ and sends an original pixel P into a square region R. Generally, such transformations do not conserve pixel boundaries. For example, the pixel P of the original image transforms to the region R, which overlaps several pixels P
1
, P
2
, P
3
, P
4
. Under a transformation, the image of a pixel can overlap several pixels.
Since the image of a pixel can overlap several pixels, one performs two steps to find the transformed value of a pixel. First, one finds which original pixels transform into an image pixel. Second, one interpolates the transformed value of the image pixel from original values of all of the pixels transforming thereto.
FIG. 2
shows a prior art system
10
for transforming a digital image. A first random access memory (RAM)
15
transmits the pixel values of the original image. A processor
20
couples to the first RAM
15
and can read pixel values therein. The processor
20
is adapted to determine the transformed pixel values from the original values stored in the first RAM
15
. The processor
20
couples to a second RAM
25
and can write the transformed pixel values thereto. The second RAM
25
will store the new image resulting from the transformation.
FIG. 3
illustrates a method
40
for transforming a digital image with the system
10
of FIG.
2
. At block
45
, the processor
20
selects a pixel. At block
50
, the processor
20
determines, which pixels transform to the selected pixel under the given transformation. At block
55
, the processor
20
reads, from the first RAM
15
, the original values of pixels, which transform to the selected pixel. At block
60
, the processor
20
determines the transformed or new value of the selected pixel from the original values of the pixels transforming thereto. At block
65
, the processor writes the new value of the selected pixel to the second RAM
25
. At block
70
, the processor
20
determines whether more pixels remain to be transformed. If more pixels remain, the processor
20
loops back to block
45
to select the next pixel to be transformed. After transforming all the pixels, the processor
20
stops.
Still referring to
FIG. 3
, the method
40
transforms the original image by processing pixels individually and sequentially. In particular, the reads of original pixel values from the first RAM
15
, at block
55
, and the writes of a new pixel value to the second RAM
25
, at block
60
, are both random memory accesses to the respective RAM's
15
,
25
. Random RAM accesses can be inefficient and slow processes, particularly for certain types of RAM's. The slowness of random memory accesses limits the speed at which one can transform images in video applications.
As an example, one can consider transforming a rectangular digital image composed of 480 horizontal lines having 720 pixels each. To transform at a standard rate of 60 frames per second, the processor
20
of
FIG. 2
must write to the second RAM
25
at a rate of about 720×480×60 or 21×10
6
pixels per second. If each storage location of the second RAM
25
is large enough to store the bits for the value of one pixel, the processor
20
needs to perform about 21×10
6
writes per second for video applications. For a typical synchronous dynamic (SDRAM), a write uses about 6 clocks. Thus, the SDRAM must be able to receive data at a frequency of about 126×10
6
Hertz to achieve the standard operation speed. Since standard SDRAM's operate up to about 100×10
6
Hertz, standard SDRAM's are too slow to use random accesses for processing 720×480 pixel images. Prior art methods cannot transform large or high-resolution video images, at standard speeds.
One method for processing large or high-resolution images at standard speeds entails constructing the first and second RAM's
15
,
25
of
FIG. 2
with high speed RAM's. High-speed RAM is more expensive and uses more power. Furthermore, high-speed RAM is generally smaller and not adapted to handle large and high-resolution digital images.
SUMMARY OF THE INVENTION
In a first aspect, the invention provides a method for transforming pixels of a digital image by a preselected transformation. The method includes receiving pixel values of a selected pixel block; determining transformed pixel values for an image block of the selected pixel block under the transformation; and burst writing the transformed pixel values to a memory.
A burst write comprises a series of multiple-location memory writes to memory locations for the values of adjacent pixels.
In a further aspect, the invention provides an electronic apparatus for transforming the pixels of a digital image by a preselected transformation. The apparatus includes a processor and an output memory. The processor receives pixel values of a selected pixel block and determines transformed pixel values for an image block of the selected pixel block under the transformation. The processor then burst writes the transformed pixel values of the image block to the output memory.
In a further aspect, the invention provides a method of transforming a digital image with a transformation. The method includes separating the image into multi-pixel regions, selecting a multi-pixel region, transforming the pixels of the selected multi-pixel region to find image pixels thereof under the transformation. The multi-pixel regions are mutually exclusive. The method further includes determining transformed values for the image pixels, burst writing the transformed values to a random access memory (RAM), and then, repeating the acts of selecting, transforming, determining, and burst writing for a second multi-pixel region.
In a further aspect, the invention provides a method of spatially transforming a digital image. The method comprises dividing the digital image up into sub-image portions and processing each sub-image portion. The acts of processing each sub-image portion include storing pixel values for the pixels of the sub-image portion to a sub-image RAM, determining new pixel values for image pixels of the sub-image portions from said pixel values stored in said sub-image RAM, and burst writing the new pixel values to a second RAM at addresses corresponding to the image pixels. The sub-image RAM provides for high-speed random accesses. The second RAM supports first and second types of access commands. The second type of access command is faster than a series of the first type of commands, which produces the same final state. The burst writes to the second RAM include a series of said second type of access commands.
In a further aspect, the invention provides a program storage device readable by a machine and tangibly embodying a program of executable instructions for a method of transforming the pixels of a digital image under a preselected transformation. The method includes receiving pixel values of a selected pixel block from a first device; determining transformed pixel values for an image block associated with the selected pixel block under the transformation; and burst writing the transformed pixel values of the image block to an output memory.
Other advantages
Fish & Richardson P.C.
Media 100 Inc.
Mehta Bhavesh M.
Patel Kanji
LandOfFree
Transforming video images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Transforming video images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transforming video images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3133630