Image analysis – Image transformation or preprocessing – Walsh – hough – or hadamard transform
Reexamination Certificate
1998-03-10
2002-08-06
Mehta, Bhavesh (Department: 2621)
Image analysis
Image transformation or preprocessing
Walsh, hough, or hadamard transform
C382S282000, C708S202000, C708S400000
Reexamination Certificate
active
06430319
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique of effecting conversion processing of two-dimensional data. More particularly, it relates to a data conversion processing circuit which, using the Hough transform, effects processing for data conversion which projects two-dimensional data on a plurality of straight lines with different inclinations.
2. Description of the Related Art
The Hough transform is a technique for extracting a figure such as a straight line and circle from an image, and is effective in detecting a straight line as described later. Moreover, when the Hough transform is used to carry out pattern matching, the number of arithmetic operations can be reduced. From this viewpoint, the Hough transform is thought to be applicable to motion detection of an animated image or graphic recognition. The Hough transform is actually adopted as a pre-process for processing visual information, and is thought to help to reduce the number of subsequent arithmetic operations or to help to facilitate learning processes in a neural network. Accordingly, if the Hough transform can be easily carried out, information processing that requires a large number of arithmetic operations according to the existing methods, such as compression of moving image data and graphic recognition, can be achieved relatively easily. In view of this, there is an increasing demand for an art of carrying out the Hough transform with the number of arithmetic operations being as small as possible.
To begin with, the Hough transform will be described briefly with reference to
FIGS. 1
a
and
1
b
. As shown in
FIG. 1
a
, assuming that an angle, formed by a perpendicular extending from an origin to a straight line L in the system of x and y coordinates and the x axis, is &thgr;, and the length of the perpendicular is &rgr;, the straight line L is expressed as x·cos &thgr;+y·sin &thgr;=&rgr;. When the line L passes through a point (u, V), an equality of u·cos &thgr;+v·sin &thgr;=&rgr; is established. When a trajectory (&thgr;, &rgr;) where the angle &thgr; and length &rgr; satisfy the equality is drawn in a &rgr;-&thgr; space, a sine curve shown in
FIG. 1
b
is produced. Likewise, when a trajectory (sine curve) linking points (u′, v′) is drawn, a point of intersection between the two trajectories shall be a point (&thgr;
0
, &rgr;
0
) In this case, x·cos &thgr;
0
+y·sin &thgr;
0
=&rgr;
0
expresses a straight line passing through two points (u, v) and (u′, v′).
Based on the foregoing principle, a trajectory linking N points in an image is drawn in the &rgr;-&thgr; space, and the cross point of the trajectory is obtained in order to define a straight line fitted to the set of points in the image. This processing is referred to as the Hough transform. For obtaining the cross point, after the elements of an array expressing the &rgr;-&thgr; space are each initialized to 0, every time the trajectory (sine curve) passes through an element, a value of image data is added to the element. Finally, elements having large values are extracted. Thus, when the Hough transform is employed, a graphic of a straight line can be extracted from (that is, detected in) an image.
Assuming that image data at any point (x, y) in the original system of x and y coordinates is a(x, y), the Hough transform AH(&rgr;, &thgr;) of the image data is expressed as follows:
AH
(&rgr;, &thgr;)=∫∫
a
(
x, y
)·&dgr;(&rgr;−
x
·cos &thgr;−
y
·sin &thgr;)
dxdy
(1)
This expression means that a value a(x, y) is added to the sine curve expressed as &rgr;=x·cos &thgr;+y·sin &thgr; in the &rgr;-&thgr; space.
A normally adopted method is such that according to the expression (1), the length &rgr; (=x·cos &thgr;+y·sin &thgr;) is calculated with the x and y coordinates fixed and with the angle &thgr; varied. In the prior art, calculations of cos &thgr; and sin &thgr; are needed, and thus the number of arithmetic operations becomes increased.
The foregoing method based on the expression (1) requires a considerable number of arithmetic operations for calculating x and y coordinates of data to be added to each other. However, an essential arithmetic operation with respect to the Hough transform is addition of data a(x, y), indicated by the expression (1). The calculation of x and y coordinates is not a principal part of the Hough transform. The number of arithmetic operations required for the calculation of x and y coordinates can be further reduced by efficiently selecting data serving as an addend.
However, no known art has provided a means capable of efficiently specifying x and y coordinates that locate data serving as an addend. This poses a problem that operations needed for projecting two-dimensional data on a plurality of straight lines having different inclinations, cannot be achieved at a high speed.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a data conversion processing circuit capable of carrying out the Hough transform by performing a small number of arithmetic operations and eventually contributing to an increase in processing speed.
For accomplishing the object, according to the present invention, operations are carried out with an angle &thgr; fixed so that x and y coordinates locating data serving as an addend can be produced efficiently. Moreover, for different angles &thgr;, the operations are carried out in a time-division manner.
Specifically, when the aforesaid expression (1) is rewritten, the following expression is drawn out:
AH
(&rgr;, &thgr;)=∫
a
(&rgr;·cos &thgr;−
t
·sin &thgr;, &rgr;·sin &thgr;+
t
·cos &thgr;)
dt
(2)
This expression indicates that when the angle &thgr; is fixed, addition should be carried out in the direction of t perpendicular to the direction of &rgr;. As seen from this expression, once coordinates (x, y) locating data serving as an addend, that is, (&rgr;·cos &thgr;−t·sin &thgr;, &rgr;·sin &thgr;+t·cos &thgr;) can be obtained efficiently, the Hough transform can be carried out efficiently.
According to the method based on the expression (1), the operations are carried out with the x and y coordinates fixed. Input data a(x, y) should therefore be fetched once. By contrast, according to the present invention, since the operations are carried out with the angle &thgr; fixed, the same input data a(x, y) is used many times at different time instants. For improving efficiency, the input data a(x, y) should be fetched into a storage area to which access can be achieved quickly. Among the fetched data items, x and y coordinates that locate data serving as an addend are produced according to the angle &thgr;, and data serving actually as an addend is selected according to the coordinate data. The selected data are summed up. This results in a Hough transform expressed in the &rgr;-&thgr; space.
For realizing the operations, a data conversion processing circuit in accordance with the present invention comprises a data storage unit in which data located by x and y coordinates is stored, a coordinate generation unit for sequentially producing x and y coordinates locating data that serves as an addend according to an angle &thgr; relative to the x axis, and generating a selection signal used to select data located by the x and y coordinates, a data selection unit for selecting data, which serves as an addend, from among data items stored in the data storage unit, and an addition unit for adding the selected data. For producing coordinates and selecting data, the Hough transform given by the expression (2) is employed.
According to the present invention, in the data conversion processing circuit, a change in coordinates (&rgr;·cos &thgr;−t·sin &thgr;, &rgr;·sin &thgr;+t·cos &thgr;), which is used to select input data a(x, y), due to a change in element t is expressed as (&Dgr;t·sin &thgr;, &Dgr;t·cos &thgr;) and substantially independent of &rgr; and t. Consequently, t
Fujitsu Limited
Kassa Yosef
Mehta Bhavesh
Staas & Halsey
LandOfFree
Data conversion processing circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data conversion processing circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data conversion processing circuit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2898381