High-performance band combine function

Details High-performance band combine function High-performance band combine function

2000-05-23

2003-03-25

Tung, Kee M. (Department: 2676)

Computer graphics processing and selective visual display system

Computer graphics display memory system

Logical operations

C345S559000

Reexamination Certificate

active

06538657

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to the field of graphics and image processing as performed in a digital system. More specifically, the present invention is a band combine function for converting a source image of n bands to a destination image of m bands, especially when performed on a parallel processing system.
In a digital system, images are stored by pixels of the image. One pixel is represented by some number of bits or bytes of memory in the digital system. Furthermore, the image is typically represented by a two-dimensional array of pixels. The image may have multiple two-dimensional arrays of pixels. One array, or “band,” represents a particular feature of the image. For example, an image may be a color image in RGB format. A first band of the image represents the red components. A second band represents-the green components. And, a third band represents the blue components.
Band combine is used in image processing for many different purposes. For example, band combine may be used to convert an image from one color space to another, such as converting video images in YUV format to RGB format for display on a monitor. Conversely, band combine may also be used to convert an image from RGB format to YUV format. Furthermore, band combine may be used to extract the luminance information from a color image, which may be used to create a black-and-white image. Band combine may be used to highlight particular features of the image according to desired bias values. For example, specific features of a topographic image may be shown in a particular color.
The band combine function is performed by a matrix multiplication operation: D=A*S. S is a vector representing a source pixel. D is a vector representing a destination pixel. A is a transformation matrix, also containing bias values. Matrix A may contain user-defined values. Further, a user may select or define the bias values. For example, to band combine a three-banded source image to obtain a three-banded destination image, the matrix representation would be:
[
d0
d1
d2
]
=
[
a
b
c
d
e
f
g
h
i
j
k
l
]
*
[
s0
s1
s2
1
]
The values in the transformation matrix may be floating point numbers. The variables d, h, and l are bias values. Using matrix multiplication, the resulting computations that are to be performed on each pixel of the image are:
d
0
=
a*s
0
+
b*s
1
+
c*s
2
+
d,
d
1
=
e*s
0
+
f*s
1
+
g*s
2
+
h,
and
d
2
=
i*s
0
+
j*s
1
+
k*s
2
+
l.
Despite improvements in digital processing technology, mathematics operations such as multiply and add are still relatively time consuming. Hence, functions such as the band combine function, which are very computation intensive, require substantial amounts of computing resources and time. Further, as users demand more from the technology, these types of image processing operations will even become more complex. For example, the resolution of images is typically increasing, which leads to greater numbers of pixels per image. Accordingly, the band combine function will take proportionately longer to execute for higher resolution images. Therefore, it becomes increasingly important to improve the techniques used to generate the band combine function, so that the function may be performed more quickly and more efficiently.
As can be seen, an improved technique for generating the band combine function is needed.
SUMMARY OF THE INVENTION
The present invention is a high-performance band combine function to transform a source image of n bands to a destination image of m bands. More specifically, this function performs an arbitrary interband linear combination of a source image using a transformation matrix. The transformation matrix may be of arbitrary size, and can be used to produce a destination image which has a different number of bands from the source image. For example, a RGB image can be converted to a black-and-white image.
In a band combine function of the present invention, a source image vector of pixels is multiplied with the transformation matrix having n+1 columns and m rows. The values in the transformation matrix may be user-selected. The values in the transformation matrix may be floating point numbers. The product of the source image vector and the transformation matrix is a destination image vector. The pixels of the destination image vector, which are the result of the band combine function, may be displayed on a computer monitor.
In the present invention, a digital system is optimized to rapidly evaluate the band combine function. The present invention provides techniques of evaluating the band combine function where many of the computational intensive tasks are performed in concurrently and in parallel. To perform this function in a digital system, the pixels of the source image are converted to a partitioned format. The source pixel bands are multiplied with the transformation matrix values using partitioned arithmetic. In the digital system, a plurality of partitioned arithmetic operations may be performed in parallel. For example, a floating point/graphics unit in the digital system may perform a plurality of multiply operations in a single clock cycle. Further, in one embodiment of the present invention, the matrix multiplication operation may be performed on at least two bands of a pixel at a time. Effectively, this increases the rate at which the band combine function operates. Furthermore, the operations of the band combine function may be pipelined with other processor operations in order to further increase execution speed.
More specifically, the band combine function of the present invention includes the following steps: A first band of a pixel is stored in a first portion of a first register. A second band of the pixel is stored in a second portion of the first register. A first value of a transformation matrix is stored in a first portion of a second register. And, a second value of the transformation matrix is stored in a second portion of the second register. In another embodiment of the present invention, the first portion of the first register and the first portion of the second register are multiplied to obtain a first product. The second portion of the first register and the second portion of the second register are multiplied to obtain a second product. These multiplying steps may be performed concurrently in the digital system.
Other objects, features, and advantages of the present invention will become apparent upon consideration of the following detailed description and the accompanying drawings, in which like reference designations represent like features throughout the figures.


REFERENCES:
patent: 5185856 (1993-02-01), Alcorn et al.
patent: 5268995 (1993-12-01), Diefendorff et al.
patent: 5394349 (1995-02-01), Eddy
patent: 5504823 (1996-04-01), Yoon
patent: 5533185 (1996-07-01), Lentz et al.
patent: 5555321 (1996-09-01), Ogura et al.
patent: 5598483 (1997-01-01), Purcell et al.
patent: 5734874 (1998-03-01), Van Hook et al.
patent: 5768429 (1998-06-01), Jabbi et al.
patent: 94/03795 (1992-03-01), None
patent: 94/07208 (1994-03-01), None
“i860™ Microprocessor Family,”Intel Microprocessors, vol. II, 1991.
“MC88110 Second Generation RISC Microprocessor User's Manual,” Motorola, Inc., 1991, 44 pages.
Hung et al., “Statistical Inverse Discrete Cosine Transforms For Image Compression,” SPIE, vol. 2187, Apr. 1994, pp. 196-205.
Gwennap, “Ultrasparc Unleashes SPARC Performance,” Microprocessor Rpt., vol. 8, No. 13, Oct. 3, 1994, p. 1.
Gwennap, “Ultrasparc Adds Multimedia Instructions,”, Microprocessor Report, Dec. 1994, pp. 16-18.
Galbi, Dave, et al., “FA 17.1: An MPEG-1 Audio/Video Decoder with Run-Length Compressed Antialiased Video Overlays,” IEEE International Solid-State Circuits Conference, Digest of Technical Papers, Feb. 17, 1995, 0-7803-2495-1/95, pp. 286-288.
Pearson, “A Low-Cost, High-Performance PA-RISC Workstation with Built-in Graphics, Multimedia, and Networking Capabilities,” Hewlett-Packard Jor., Apr. 1995, vol. 46, No. 2, pp. 6-11

Affiliated with

Also associated with

Rating

High-performance band combine function does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with High-performance band combine function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-performance band combine function will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3036175