JPH0799545B2 - Pipeline histogram calculation circuit - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Outline] In order to pipeline the density histogram calculation processing for storing the calculation result in a memory, one input density value is input with the density value input so far during the pipeline processing. A correction value is obtained by detecting the number of density values that are the same as the density value, and the correction value is supplied to the pipeline calculation means together with the memory contents read by the input density value. As a result, the density histogram for the input density value can be correctly calculated by the pipeline addition processing, and the high-speed density histogram calculation processing can be realized by a small-scale circuit.

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a high-speed density histogram calculation circuit by pipeline calculation processing, and particularly to a high-speed pipeline histogram calculation circuit suitable for high-speed calculation of a density histogram of input pixels in image processing. .

[Conventional technology]

In image processing, the density histogram is widely used for various image processing such as contrast correction and area extraction. This density histogram is obtained by accumulating the number of pixels for each density value from the image.

As a method of calculating the density histogram of this image, the conventionally calculated density histogram is stored in the memory, the memory content of the address corresponding to the density value of a certain input pixel is read, "1" is added to the content, and the memory is read again. The method of writing to the same address of, and the method of storing in the counter corresponding to each density value of the input pixel were used.

[Problems to be solved by the invention]

In the above-mentioned image density histogram calculation method, the method of storing the density histogram in the memory has an advantage that an inexpensive and small-scale memory can be used. However, since one operation of the density histogram calculation processing requires three operations of a density histogram read operation from the memory, an addition operation, and a rewriting operation of the calculated density histogram, the density histogram calculation processing takes time. There is a problem that the calculation process cannot be speeded up.

On the other hand, the method of storing in the counter of (1) can easily speed up the calculation process of the density histogram by using a high-speed counter, but on the other hand, the maximum value of the density histogram, for example, a maximum of 2 in the case of 4096 × 4096 image. There is a problem that the hardware becomes large-scale and expensive because it requires a counter up to ²⁴ .

It is an object of the present invention to provide a small-scale and inexpensive density histogram calculation circuit capable of high-speed processing by pipeline-processing the density histogram calculation processing when storing the density histogram of an image in a memory. .

[Means for solving problems]

In the method of storing the density histogram of the image in the memory, when calculating the density histogram of the input pixel, the read time of the memory is t _mr , the calculation (addition) time is t _ad , and the rewriting time to the memory is t _mw. Then, it takes t _mr + t _ad + t _mw time for one concentration histogram calculation processing time.

As a general method for accelerating the arithmetic processing including a plurality of operations in this way, a method of pipeline processing is known. If the density histogram calculation process can be pipelined, the calculation time for a certain input pixel is t _mr + t _ad + t _mw by independently performing the memory read process, calculation process, and memory write process. However, it is possible to obtain (n + 1) t _max as the overall throughput. Here, n is the number of pixels that are continuously input, and t _max is the maximum value among t _mr , t _ad , and t _mw .

However, in the image density histogram calculation process, each process of memory reading, calculation, and writing to the memory cannot be performed independently, so these processes cannot be immediately pipelined.

That is, if the density histogram calculation processing of the image is pipelined as it is, when m pixels of the same density value are continuously input during the pipeline processing, the cumulative value of the density value read from the memory up to that point is accumulated. This is because if the value is S, the pipeline processing result will be "S + 1", and a correct processing result that sequentially accumulates from "S + 1" to "S + m + 1" cannot be obtained.

The present invention solves this problem and enables the pipeline of image density histogram calculation processing.

The means taken by the present invention to solve the above-mentioned problems in the method of storing the density histogram in the memory will be described below.
A description will be given with reference to FIG.

FIG. 1 is a block diagram showing the basic configuration of the present invention.

In FIG. 1, 110 is a memory in which the already calculated results of the density histogram are stored.

Reference numeral 120 denotes an input register means, which has a number of register stages corresponding to the number of arithmetic stages of the pipeline arithmetic means, and sequentially shifts and stores the density value as input data.

Reference numeral 130 denotes a correction value generating means, which generates a correction value for calculating a density histogram based on the density value stored in each register stage of the input register means 120.

Reference numeral 140 denotes a pipeline calculation means, which calculates the density histogram by pipeline processing using the contents of the memory 110 read based on the input density value and the correction value as input.

Reference numeral 150 denotes an address selecting means, which selects the input density value as a read address for the memory 110, and the input register means 12
The density value output from 0 is selected as the write address for storing the processing result of the pipeline calculation means 140 in the memory 110.

[Action]

When there is one input IP, it is selected by the address selection means 150, and the memory 110 is selected by the address obtained from the input density value.
Is read and input to the pipeline calculation means 140.

Meanwhile, the input IP is added to the register means 120.

The correction amount generating means 130 generates a correction value for calculating the density histogram based on the density value between the register stages in the register stage 120. That is, now pipeline calculation means
It is assumed that m inputs of the same density value as the input IP have been input during the arithmetic processing in 140, and at the time when the input IP is added, the arithmetic processing is being performed on n inputs including the m input.

Assuming that the density histogram value read from the memory 110 is S using the density value of the input IP as an address, if only this S is input to the pipeline calculating means 140, the pipeline calculating means 140 performs the calculation processing of “S + 1”. And the correct result "S + m + 1" cannot be obtained. That is, the density histogram value S of the memory 110 read when the input IP is added indicates the density histogram value for which the cumulative processing for n inputs being processed in the pipeline calculation means 140 is not completed. Depends on.

The correction value generating means 130 detects m inputs having the same density value as the density value of the input IP from the n-1 inputs existing in each register stage (not shown) of the register means 120. Then, the number m is added to the pipeline calculation means 140 as the correction amount m + 1.

The pipeline calculation means 140 receives the contents S of the memory 110 read out based on the density value of the input IP and the correction value m + 1 generated by the correction value generation means 130 as an input to perform pipeline calculation processing, and correct processing is performed. The result "S + m + 1" is output.

The address selecting means 150 receives the input from the register means 120.
When the density value of the IP is output, it is selected as the write address, and the processing result “S + m” for the density value of the input IP output from the pipeline operation means 140 at that time is selected.
+1 ”is stored in the memory 110.

As described above, the density histogram calculation process is pipelined, and the correct density histogram can be calculated at high speed even if the same density value is continuously or discontinuously input during the pipeline calculation process.

[Example I]

Example I, which is one example of the present invention, will be described with reference to FIG.

FIG. 2 is a block diagram showing the configuration of the embodiment I.

(A) Configuration of Embodiment I In FIG. 2, the memory 110, the input register means 120, the correction value calculating means 130, the pipeline calculating means 140, and the address selecting means 150 are as described in FIG.

Reference numeral 160 denotes a sampling register, which is composed of a flip-flop FF, and samples the input pixel density value supplied from the outside of the circuit at constant time intervals with the clock CK so as to be a signal synchronized with the clock CK inside the circuit.

Reference numeral 170 denotes a memory register, and the contents of the memory 110 read out by using the pixel density value of the sampling register 160 added via the address selection means 150 as an address are stored one clock later than the sampling register 160, and the output thereof. Is supplied to the biline calculation means 140.

The input register means 120, 120 ₀ in the input register stage, the contents of the sampling register 160 is stored in one clock later than the sampling register 160. Again 121 ₁
To 121 _n in the register stages of the n stages corresponding to the operation number n of the pipeline processing unit 140 is composed of Furipufuroppu (FF), stores the density value of each input pixel is sequentially shifted in synchronism with the clock CK To be done.

It should be noted that the number n of register stages of the input register means 120 and the number n of operation stages of the pipeline operation means 140 described later are the same, and n is composed of n which is equal to or larger than the number of digits by which the histogram value can be expressed in binary. .

In the correction value generating means 130, 131 _{1 to} 131 _n are comparators,
The comparator 131j (j = 1 to n) includes the corresponding register stage 121j (j = 1 to n) in the input register means and the input register stage.
Compare the contents of 120 ₀ , and output “1” if they are equal, and output “0” if they are not equal. Reference numeral 132 denotes a correction value table, which generates a correction value based on the inputs from the comparators 131 _{1 to} 131 _n and adds it to the pipeline calculating means 140. Specifically, a value obtained by adding 1 to the addition value of the "1" input supplied from the comparators 131 _{1 to} 131 _n is generated.

In the pipeline operation means 140, 141 _{1 to} 141 _n are n operation stages, each addition stage 141j (j = 1 to n) is a pipelined adder 142j, and an operation register 144j for storing the addition result. And an arithmetic register 143j for storing the pending data. The addition process of each of the adders 142 _{1 to} 142 _n is completed within one clock.

FIG. 4 shows a concrete example of the pipeline arithmetic means 140 shown in FIG. Note that FIG. 4 shows a case where the number of operation stages n is 4.

In FIG. 4, the memory 170 and the correction value table 132 are used to respectively input the input register stage 12 as described later.
Memory 110 density values recorded in 1 ₀ as an address
The histogram value S and the correction value m + 1 thus read out are input.

The adder 142 ₁ adds the least significant digit of the histogram value S and the correction value m + 1, and the addition result is the operation register 144 ₁
To, and the data other than the addition result carry the least significant digit is stored in the arithmetic register 143 _1.

The adder 142 _2, carry the least significant and the second digit of the sum is performed, the result of addition operation register 144 _2, carry a third digit or more data than the second digit to the arithmetic register 143 ₂ Is stored.

Pipeline addition operation corresponding to each digit is performed sequentially,
In the final fourth (n) digit, the operation register 143 _{4 (n)}
And the data stored in the arithmetic register 1444 _(n) is output to the memory 110 as the data following the lower order.

(B) Operation of Embodiment I The density values of pixels input from outside the circuit at fixed time intervals are sampled by the sampling register 160 in synchronization with the clock CK, and the input register stage 121 ₀ and the address selecting means are selected.
Supplied to 150. Now, let the input pixel be IP.

The address selection means 150 selects the density value of the input pixel IP, reads it out, and uses it as the address, which is the content S of the memory 110.
Is read and stored in the memory register 170.

The density value of the input pixel IP is stored in the input register stage 121 ₀ with a delay of 1 clock from the sampling register 160, and the content S of the memory 110 is stored in the memory register 170 with a delay of 1 clock from the sampling register 160. It

Each comparator 131j (j = 1 to 0) in the correction value generating means 130
Is the corresponding register stage 121j (j in the input register means.
= 1 to n) pixel density value is compared with the input image 0000 density value,
If they match, "1" is output, and if they do not match, "0" is output and supplied to the correction value table 132.

The correction value table 132 generates a value obtained by adding 1 to the addition value of the "1" input supplied from each of the comparators 131 _{1 to} 131 _n . As a result, the pipeline calculation means 140 is input at the time of inputting the pixel IP.
If there are m input pixels having the same density value as the input pixel IP among the n input pixels being processed, the detected pixel value is detected and added to the pipeline calculation means 140 as a correction value m + 1.

The pipeline calculation means 140 outputs the calculation process of outputting "S + m + 1" based on the memory contents S input from the memory register 170 and the correction value m + 1 input from the correction value table 132. The pipeline processing described in FIG. Run by.

As a result, the correct density histogram value “S + m + 1” is calculated and stored in the arithmetic registers 143 _n and 144 _n .
At that time, the density value of the input image IP is sequentially shifted and stored in the register means 121 _n in the input register means 120 from the previous stage.

The address selecting means 150 selects the density value of the pixel IP of the register means 121 _n , and uses this as the write address for the density histogram “S” stored in the calculation registers 143 _n and 144 _n.
+ M + 1 ”is stored in the memory 110.

To explain the operation in more detail, the density value is input and held in the sampling register 160 at time t = t ₀ , and is transferred to the input register stage 121 ₀ at t = t ₀ +1 when the next clock is input.

On the other hand, at t = t ₀ , the address selecting means 150 selects the sampling register 160 and uses the density value as an address in the memory 1.
The ten records are read and stored in the memory register 170 at t = t ₀ +1.

On the other hand, at t = t ₀ +1 the address selection means 150
Select the output of the sampling register 160, memory 1
When the reading of the record is completed from 10, the address selecting means 150
Selects the register stage 121 _n , outputs the address (density value) of the memory 110, and stores S + m + 1 added by the addition stage 141 _n in the memory corresponding to the output address.

The above processing is repeated until the density value input to the sampling register 160 reaches the final value, and the histogram result is recorded in the memory 110.

In the pipeline calculation means 140, first, t = t ₀ +
At 1, the histogram S up to the present time stored in the memory 110 with the density value recorded in the register stage 120 ₀ as an address is read and recorded in the memory register 170. Further, m + 1 is output from the correction value table 132 (the correction value m + 1 will be described later).

At time t = t ₀ +2, the histogram value S up to the present recorded in the memory register 170 and the correction value m output from the correction value table 132 as described in FIG.
+1 is moved to the addition stage 141 ₁ , and addition is performed on the least significant digit (first digit) of S and m + 1. Further, the density value recorded in the register stage 121 ₀ is transferred to the register stage 121 ₁ .

At time t = t + 3, the addition of the second digit of S and m + 1 is performed.

After that, addition is sequentially performed from the lower digit, and t = t + n + 1
Then, the addition of the most significant digit is completed, and the addition result of S + m + 1 is obtained.

Therefore, in the addition stage 141 _j , the addition of the jth digit of S and m + 1 to the density value recorded in the register stage 121 _j is executed.

The reason why m + 1 is output from the correction value table 132 is that the histogram value S read from the memory 110 at t = t ₀ +1 and recorded in the memory register 170 has the same density value as the register stage 121 _0. register stage 121 _1-12
Even _if it exists in 1 _n, the histogram addition for that density value is not added in S.

Therefore, in the correction value table 132, the register stage 121 ₀
The same density value register stages and density values recorded in the 121 ₁
1 for the number of m recorded in ~ 121 _n and its own concentration
The output is m + 1, which is the sum of the numbers.

The pixel density histogram calculation processing by the above pipeline calculation processing is performed by the clock C from the sampling register 160.
This is executed for each pixel density value that is sequentially input at each clock in synchronization with K.

Example II

When the number of operation stages of the pipeline operation means is one, the circuit configuration can be simplified as compared with the case of the embodiment I.
Example II is an example in which the arithmetic means of the pipeline arithmetic means has one stage, and FIG. 3 is a block diagram showing the configuration of the embodiment II.

In FIG. 3, input register means 120 correction value generating means 1
The configuration other than 30 and the pipeline calculation means 140, that is, the memory 110, the address selection means 150, the sampling register 160, and the memory register 170 are the same as in FIG.

The input register means 120 comprises an input register stage 121 ₀ and one register stage 121 ₁ .

The correction value generating means 130 is composed of one comparator 131.
The comparator 131 is an input register stage in the input register means 120.
The density values of 121 ₀ and the register stage 121 ₁ are compared, and if they match, a correction value “1” is generated, and if they do not match, a correction value “0” is generated. Since the output of the comparator 131 can be directly used as the correction value, it is not necessary to provide the correction value table as in the first embodiment. Pipeline operation means 140,
One operation stage 14 including an adder 142 and an operation register 143
Composed of 1. The adder 142 in the calculation stage 141 adds “1” to the density histogram value S input from the memory register 170.
And the correction value input from the comparator 131 are added, and the result is stored in the arithmetic register 143.

With the above arrangement, when the input register density value stage 121 ₀ concentration values and calculation register 143 are equal, the correct density histograms are calculated "S + 2" addition processing is performed in the adder 142.

The other operation is the same as that of the embodiment I, and thus the detailed description of the operation is omitted.

Although the respective embodiments in the case of calculating the density histogram of the image have been described above, the present invention is not limited to these embodiments and can be used in the calculation processing of the density histogram of various inputs. Is.

〔The invention's effect〕

As described above, according to the present invention, the following various effects can be obtained.

(A) It is possible to pipeline the density histogram calculation processing when the calculated density histogram is stored in the memory.

(B) Therefore, it is possible to realize a density histogram calculation circuit capable of high-speed processing with a small-scale and inexpensive structure.

[Brief description of drawings]

FIG. 1 ... Illustration of basic configuration of the present invention, FIG. 2 ... Illustration of configuration of Example I of the present invention, FIG. 3 ... Illustration of configuration of Example II of the present invention, Fourth Figure: A concrete example of the pipeline arithmetic means of the embodiment I of the present invention. 1 to 4, 110 ... Memory, 120 ... Input register means, 130 ... Correction value generating means, 140 ... Pipeline calculating means, 150 ...
Address selection means, 160 ... Sampling register, 170
...... Memory register.

Claims (1)

[Claims] 1. An input register having a memory for storing a density histogram calculation result and a number of register stages corresponding to the number of arithmetic stages of a pipeline arithmetic means, wherein the concentration values are sequentially shifted and stored as input data. Means, a correction value generating means for generating a correction value for calculating a density histogram based on the density value stored in each register stage of the input register means, and a memory read out based on the input density value. Pipeline calculation means for calculating a density histogram by pipeline processing using the contents and the correction value as input, and an input density value selected as a read address for the memory, and the density value output from the input register means of the pipeline calculation means. Address selection means for selecting the calculation result as a write address to be stored in the memory, and Pipeline histogram calculation circuit.