Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Patent
1996-11-15
2000-02-22
Mai, Tan V.
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
708603, 708493, G06F 1714, G06F 738, G06F 700
Patent
active
060291850
DESCRIPTION:
BRIEF SUMMARY
TECHNICAL FIELD
The present invention relates to an arithmetic unit of a computer system, and in particular, to a discrete cosine high-speed arithmetic unit suitable for achieving calculation of a sum of products using a plurality of constant function values and compressing and decompressing data at a high speed. Moreover, the present invention relates to a high-speed Hartley transform arithmetic unit suitable for calculating a sum of products using a plurality of constant function values and thereby executing the Hartley transform processing, which is related to a Fourier transform, at a high speed. Additionally, the present invention relates to image processing, and in particular, to a Hough transform circuit to achieve a Hough transform in which straight line components of an image are detected, the circuit being suitable for calculating a sum of products using a plurality of constant function values and executing the Hough transform processing at a high speed.
BACKGROUND ART
In the voice and image processing, there has been widely employed a discrete Fourier transform (DFT) and its variations such as a discrete cosine transform and a discrete Hartley transform. In these transform processes, a plurality of trigonometric functions are utilized to primarily calculate sums of products between the trigonometric functions and data items. In general, the calculation cost of multiplication is higher than that of addition and subtraction. Consequently, there have been devised several high-speed calculation algorithms in which the number of multiplications are advantageously reduced using relationships between trigonometric functions, e.g., the formula of double angle and the formula of half-angle. These algorithms have been briefly described in pages 115 to 142 of the "Nikkei Electronics" No. 511 published on Oct. 15, 1990. In practice, the trigonometric functions are stored as constants in a memory. Particularly, due to the relatively small number of figures of the values, there has been also adopted a method in which the results of products between data items and trigonometric functions are stored in a memory. In addition, it is possible to utilize a known method in which each trigonometric function value is calculated in a CORDIC method using the principle of rotation of coordinates and/or a formula of approximate expression of function.
In image processing, the Hough transform is often employed because the transform is advantageously applicable even when the data contains noises due to the detection of straight lines in the image. When the coordinates of an arbitrary pixel are expressed as (x,y), the Hough transform is defined as
FIG. 23 shows the geometric relationship of the transform. R stands for the length of a perpendicular drawn from the origin of the coordinate system to a straight line passing the pixel (x,y). Letter .theta. denotes the angle between the perpendicular and the positive direction of the x axis. In an actual application, for an arbitrary pixel, the angle .theta. takes a plurality of discrete values ranging from 0 to .pi. such that R of expression (1) is calculated for each value of .theta.. R is also discretized and its frequency of occurrence is attained in the form of voting for all pixels so that (R, .theta.) having the highest number of votes obtained is detected as a straight line component.
A plurality of trigonometric functions are stored as constants in a memory for use in calculation later. Or, in the conventional method in which the value of each trigonometric function is directly calculated using, e.g., the CORDIC method, even when the number of multiplications is reduced by a clever algorithm, a considerable amount of multiplications are still necessary. Furthermore, it is not practical to provide a multiplier for each of the multiplications, namely, the multiplier is to be sequentially used. This is cause of hindrance to the high-speed operation. Additionally, since an arbitrary input is assumed in a multiplier, even when a value at a digit place of binary input data
REFERENCES:
patent: 4791598 (1988-12-01), Liou et al.
patent: 5249146 (1993-09-01), Uramoto et al.
patent: 5357453 (1994-10-01), Kim et al.
patent: 5477469 (1995-12-01), Motomura
patent: 5598361 (1997-01-01), Nagamatsu et al.
patent: 5737256 (1998-04-01), Nakagawa et al.
Japanese Journal, "Nikkei Electronics", No. 511, Oct. 15, 1990, pp. 115-142.
Technical Report of The Institute of Electronics, Information And Communication Engineers, Sep. 1994, pp. 39-46.
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E78-A, No. 8, Aug. 1995, pp. 957-962.
Transactions of Information Processing Society of Japan, vol. 31, No. 8 (Tokyo), Oct. 15, 1993, pp. 1242-1250.
Hitachi , Ltd.
Mai Tan V.
LandOfFree
Discrete cosine high-speed arithmetic unit and related arithmeti does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Discrete cosine high-speed arithmetic unit and related arithmeti, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discrete cosine high-speed arithmetic unit and related arithmeti will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-529309