Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-08-08
2003-10-21
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06636881
ABSTRACT:
TECHNICAL FIELD
This invention relates to a binary data counting device used in a process, such as a Hough transform, for area sampling or line sampling in a pattern recognition device or the like of FA (Factory Automation) equipment, in particular to an area information sampling device or a Hough transform device which are application devices of the binary data counting device.
In the above described process of area sampling, a binary data counting device is used for the process of counting the number of “1s” in the binary image in order to sample the area of the “1s” (for example, black) region in a binary image (for example, the background is “0” (for example, white)).
It also is used, in the process of Hough transform, in a process of counting the number of “1s” (for example, black) which exist in a particular Japanese hand drum shaped region in a binary image (for example, the background is “0” (for example, white)).
BACKGROUND ART
Conventionally there are two major methods of counting the number of “1s” or “0s” in the data expressed in a binary manner comprising N (N is an integer of 2 or more) bits so as to take out the counting result as multi-valued data. Here, the data expressed in a binary manner comprising N bits can also be expressed as binary data of N bit length.
One is the method where data are set in a register of N bits, 1 bit is shifted to the left at an ALU (Arithmetic and Logic Unit), the value of the bit of the MSB (Most Significant Bit) is set for carrying and, in the case when the value is the desired value, the value of the accumulator is incremented by 1. This method can be implemented easily with software for the MCU (Micro Controller Unit) or the DSP (Digital Signal Processor).
That requires three instructions for the processing of 1 bit, however, which has defect that the processing speed is slow. In practical image processing, the processing object tends to be large, for example, 10,000 pixels by 10,000 pixels and, therefore, it is desirable that at least N bits are processed for one instruction implementation period. Accordingly, there is a method of using a dedicated circuit of hardware as another means.
An example of the method for implementation with hardware is described with reference to FIG.
6
.
FIG. 6
shows, in the case of N=16, a configuration of the case where the number of “1s” is counted. First, with respect to data BDATA
15
to BDATA
0
, which are expressed in a binary manner and comprise 16 bits, every neighboring two bits are paired from the side of the LSB (Least Significant Bit) to make eight pairs in total. Then, those eight pairs are inputted into eight 1-bit adders AD
18
to AD
11
, respectively, to perform the addition. As a result of this eight pieces of 2-bit data are formed.
Next, in the same way as above, with respect to eight pieces of 2-bit data outputted, respectively, from the 1-bit adders AD
18
to AD
11
, every neighboring two pieces are paired from the side of the LSB to make four pairs in total. Then, those four pairs are inputted, respectively, into four 2-bit adders AD
24
to AD
21
to perform the addition. As a result of this four pieces of 3-bit data are formed.
Next, in the same way as the above, with respect to four pieces of 3-bit data outputted, respectively, from the 2-bit adders AD
24
to AD
21
, every neighboring two pieces are paired from the side of the LSB to make two pairs in total. Then, those two pairs are, respectively, inputted into the two 3-bit adders AD
32
and AD
31
to perform the addition. As a result of this two pieces of 4-bit data are formed.
Next, those two pieces of 4-bit data are inputted into the 4-bit adder AD
41
to perform the addition. As a result of this one piece of 5-bit data which corresponds to the number of “1s” in the data expressed in a binary system comprising sixteen bits is formed. That is to say, multi-valuing of the data expressed in a binary manner comprising sixteen bits is completed.
As described above, a counting device can be implemented by forming a network of adders.
On the contrary, in the case of N=16, fifteen adders in total are necessary, which are: 1-bit adder×16/2+2-bit adder×16/4+3-bit adder×16/8+4-bit adder×16/16. In addition, in the case of N=32, thirty one adders in total are necessary, which are: 1-bit adder×32/2+2-bit adder×32/4+3-bit adder×32/8+4-bit adder×32/16+5-bit adder×32/32. Accordingly, as hardware, not only the number of adders is enormous but also each of the adders themselves becomes complicated in the circuit configuration as the bit number increases, which leads to a large scale circuit as a whole.
As described in the above conventional examples there are the defects that though the former has a smaller circuit scale the process speed is too slow to be practical and though the latter is fast in the process speed compared to the former the circuit scale becomes large.
DISCLOSURE OF INVENTION
The purpose of the present invention is to provide a binary data counting device, an area information sampling device and a Hough transform device of which the processing speed is high and which can be implemented with a small circuit scale and at low cost.
A binary data counting device according to the first aspect of the invention counts the number of either one of the binary digit in the data expressed in a binary manner comprising N bits, which is provided with a shifter array for outputting the binary data of N bits. The shifter array comprises N×(N+1)/2 shifters of which the control input is each bit value of the data expressed in a binary manner comprising N bits.
N×(N+1)/2 shifters are mutually connected so that the binary data of N bits are outputted under the condition where one of the binary digits is filled in from one side in the same number as either one of the binary digits in the data expressed in a binary manner comprising N bits by controlling the operation of each shifter making up the shifter array with each bit value of the data expressed in a binary manner comprising N bits.
According to this configuration, the number of either one of the binary digits in the data expressed in a binary manner comprising N bits is counted and in the case of transform to a multi-valued numerical expression such as a decimal number or a hexadecimal number, the number of either one of the binary digits in the data expressed in a binary manner comprising N bits is not counted through a direct operation but the counting process of the binary data is implemented as in the following. That is to say, the binary data of N bits are outputted under the condition where the same number of one of the binary digits as the number of either one of the binary digits in the data expressed in a binary manner comprising N bits is filled in from one side by controlling the operation of each shifter making up the shifter array with each bit value of the data expressed in a binary manner comprising N bits.
That is to say, the process of counting the number of “1s” or “0s” in the data expressed in a binary manner comprising N bits is implemented by expressing binary data when filled in from, for example, the right side so as to be able to intentionally encode the number of “1s” or “0s” which are desired to be counted in the data expressed in a binary manner comprising N bits. In this case, it is possible that the operation of the shifter array can be completed with one clock and the circuit scale is much smaller in comparison to the adder. Accordingly, compared to a conventional example, the process of counting the number of “1s” or “0s” in the data expressed in a binary manner can be implemented with the processing speed being higher and the circuit scale being smaller so that an inexpensive binary data counting device can be provided. In addition, it is possible that the shift operation can be performed in a shorter span of time compared to the process of a multi-bit addition operation and, therefore, a process of higher speed than
Matsushita Electric - Industrial Co., Ltd.
Ngo Chuong Dinh
Stevens Davis Miller & Mosher LLP
LandOfFree
Binary data counter, area information extractor and huffman... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Binary data counter, area information extractor and huffman..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary data counter, area information extractor and huffman... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3152183