JPH08114870A - Method and device interpolating multi-dimension - Google Patents

Abstract

PURPOSE: To save hardware resources and to increase an operational speed by imparting a maximum value of a weight coefficient for interpolation with a specified numerical formula when N-dimensional interpolation is performed. CONSTITUTION: When the N-dimensional interpolation is performed, the maximum value of the weight coefficient for the interpolation is imparted by M×2N<-1> when an interpolation interval is M, and the maximum value of the weight coefficient is suppressed. For instance, in the case of the three-dimensional interpolation, a weight generator 5 for the vicinity receives low-order four bits of an R address generator 1, the low-order four bits of a G address generator 2, the low-order four bits of a B address generator 3 and an output of four-ary counter and generates the weight coefficient of seven bits, and the weight generator 6 for the distant place generates the weight coefficient of seven bits similarly. Then, a weight coefficient space is bisected for the vicinity and the distant plate and one side is made for the vicinity, and the other side is made the distant place. In such a manner, since an axial symmetry in the spatial area of the weight coefficient is used, since it is a three-dimensional space in such a case, the necessary weight generator is sufficient for 1/2<3> =1/8 of intrinsic capacity.

Description

Detailed Description of the Invention

[0001]

FIELD OF THE INVENTION The present invention relates to a multidimensional interpolation method and apparatus.

[0002]

2. Description of the Related Art In a color image printing apparatus or the like, in order to improve the visual characteristics of a printed image, the read color image data is color-converted to another color system. . As this color conversion device, L
Some use a UT (look-up table) and an interpolation calculation device. This device uses the input image data as an address to access the LUT, outputs the converted image data, and outputs L
For the image data not stored in the UT, the output of the LUT at the grid point position is multiplied by a weighting coefficient, which is an interpolation calculation device, to perform interpolation.

The following are conventional color conversion devices. (1) Cubic interpolation (8-point interpolation. British Patent 1369702)
No.) FIG. 6 is an explanatory diagram of cubic interpolation. (A) is the original space, and (b) is the conversion destination space. The original space is R, G,
The B space and the destination space are the Y, M, and C spaces. First,
As shown in the figure, it is divided into eight rectangular parallelepipeds with an arbitrary point P in the cube shown in (a) as an axis. The volume of each divided space is Vi (i = 0 to 7). At this time, the interpolated value of the point P'mapped in the conversion destination space is given by the following equation.

[0004]

[Equation 1]

Here, Pi is the value of the original space that has already been obtained, Vi is the volume of the eight rectangular parallelepipeds forming the cube V divided by the point P, and V is the volume of the original rectangular parallelepiped. (2) Triangular pyramid interpolation (4-point interpolation. JP-A-53-12320)
(No. 1) FIG. 7 is an explanatory diagram of triangular pyramid interpolation. Triangular pyramid interpolation is a method of inputting image data into a memory space in which data corresponding to three-dimensional image data input is stored and obtaining converted data. Divide into pyramids, determine which of the divided triangular pyramids the point corresponding to the input value is included in the image data input, and then the value at each vertex of the determined triangular pyramids (4) Is used to find the internal points by interpolation.

In FIG. 7, (a) shows a state in which a cube having one side length L is divided into six triangular pyramids by the axis connecting the respective vertices from the origin a, and (b) is an exploded view thereof. Is. At this time, the interpolation value P ′ of a point within an arbitrary triangular pyramid is given by the following equation. P ′ = (L−A) × P1 + (A−B) × P2 + (B−C) × P3 + C (2) Here, A, B, and C indicate the lower digits of the input data, and A>
It is assumed that B> C is satisfied, and Pi is a value (three-dimensional coordinate value) in the space of the other party already obtained.

(3) Triangular prism interpolation (6-point interpolation. Reference KK
anamori, H .; Kotera, O .; Yamad
a, H.A. Motomura, R .; Iikawa, T .; F
umoto, Fast color processo
r with programmable inter
Polation by small memory
(PRISM), Journal of Electro
nic Imaging, 2 (3), 213-224
(1993)) In this interpolation method, the three triangular pyramids shown in (2) are combined into one to form a triangular prism, and interpolation is performed from data of a total of 6 points.

(4) Interpolation by parallel processing (US Pat. No. 4,837,722) When arranging color LUTs in parallel, each LUT has only the necessary points alternately, and the total LUT size is a single LUT. It is the same as having it. In addition, all weighting factors are R
It is stored and held by the OM.

[0009]

In the case of the cubic interpolation, since the volume of the rectangular parallelepiped on the opposite side of the point where the point for which the weighting coefficient is desired is divided is used, the weight calculated by M ³ when the maximum interpolation interval is M. It was necessary to generate a coefficient. For example,
When M = 17, it becomes 4913, and when it is configured by hardware, a data line of 13 bits is required, and since the bit width of the multiplier has to be widened,
It was disadvantageous in terms of cost and hardware scale. Furthermore,
When performing interpolation calculation, if one color has 8 bits, (8 + 1
3) Bits were required, and it was not possible to simultaneously calculate four colors with a 64-bit register.

In the case of the triangular pyramid interpolation, the maximum value of the weighting factor is M (interpolation interval), and the number of data lines can be greatly saved. However, when the calculation is performed purely for calculating the interpolation coefficient, it is necessary to make a determination for dividing the unit cube into 5 to 6, and this determination becomes complicated. In order to avoid such a problem, there is also a method of calculating and storing it in the form of an LUT in advance, but in this case, when the interpolation interval is M, it becomes M ³ , for example, when M = 17, 4913 words. Had to remember the data.
Further, since the number of interpolation points is small (4 points), there is a problem in accuracy.

In the case of the triangular prism interpolation, there is a problem that the anisotropy is high and the error becomes large depending on the interpolation direction. In the case of the parallel processing interpolation, since the weight coefficient is provided as the LUT, when the lattice spacing M increases, the LUT
There was a problem that the size increased.

Further, as a problem common to these prior arts, when the interpolation interval M is a power of 2, bit shift can be used instead of division at the final stage, but M is 2
If it is not a power of 0, bit shift cannot be performed and division must be performed at the final stage, resulting in an increase in circuit scale and an increase in operation time.

The present invention has been made in view of the above problems, and an object of the present invention is to provide a multidimensional interpolation method and apparatus capable of saving hardware resources and increasing the operation speed. .

[0014]

According to a first invention for solving the above-mentioned problems, when N-dimensional interpolation is performed, the maximum value of the weighting coefficient for the interpolation is M ×
The feature is that it is given as 2 ^N-1 and multidimensional interpolation is performed.

In this case, when performing the interpolation calculation of the N-dimensional LUT, it is necessary to simultaneously multiply the weight data by a weighting factor for a plurality of color data among the values of three colors to four colors of the LUT, which requires a hardware resource. This is preferable in terms of saving and speeding up the interpolation calculation.

A second invention for solving the above-mentioned problems is N
When dimensional interpolation is performed, a weighting factor is generated for an address of (M + 1) / 2 with respect to the interpolation interval M, and multidimensional interpolation is performed.

In this case, when performing the interpolation calculation of the N-dimensional LUT, it is possible to save hardware resources by simultaneously multiplying a plurality of color data among the values of three colors to four colors of the LUT by a weighting coefficient. However, it is preferable for speeding up the interpolation calculation.

A third invention for solving the above-mentioned problems is N
In the case of performing dimension interpolation, when the maximum weighting coefficient does not become a power of 2, the data stored in the color LUT is divided in advance, and it is stored as a power of 2.

A fourth invention for solving the above-mentioned problems is N
The dimensional interpolating device is characterized in that it is provided with means for giving the maximum value of the weighting coefficient for interpolation at M × 2 ^N−1 at the interpolation interval M.

In this case, when performing the interpolation calculation of the N-dimensional LUT, it is hard to provide a means for multiplying a plurality of color data among the values of three colors to four colors of the LUT by the weighting coefficient at the same time. This is preferable for saving wear resources and speeding up the interpolation calculation.

A fifth invention for solving the above-mentioned problems is N
The dimensional interpolating device is characterized by including means for generating a weighting coefficient for an address of (M + 1) / 2 with respect to the interpolation interval M.

In this case, when performing the interpolation calculation of the N-dimensional LUT, it is hard to provide a means for multiplying a plurality of color data among the three-color to four-color values of the LUT by the weighting factor at the same time. This is preferable for saving wear resources and speeding up the interpolation calculation.

A sixth invention for solving the above-mentioned problems is N
The dimensional interpolating device is characterized in that it has means for dividing the data to be stored in the color LUT in advance when the maximum weighting coefficient does not become a power of 2 and multiplying it by a power of 2 for storage.

[0024]

[Action]

(First invention) The maximum value of the weighting factor for the interpolation is given by M × 2 ^N−1 at the interpolation interval M so that the maximum value of the weighting factor is suppressed. As a result, it is possible to save hardware resources and speed up the calculation time.

Here, M × 2 ^N-1 was obtained as follows. The present invention is an extension of the triangular pyramid interpolation. In FIG. 7A, the cube is divided into six triangular pyramids with the diagonal of the cube as the axis, but all combinations are made for this axis. That is, a-g, b-h, c-e, d in the figure
-F When the weight coefficients in the triangular pyramid interpolation when the respective axes are changed are all calculated and averaged, the above-mentioned M × 2 ^N-1 is obtained. According to the present invention, as a result of obtaining and averaging the weighting factors for the axes in all directions, the influence of the directionality of the axes is eliminated.

In this case, when performing the interpolation calculation of the N-dimensional LUT, hardware resources are saved by multiplying a plurality of color data among the three-color to four-color values of the LUT by weighting factors at the same time. It is possible to save the cost and speed up the interpolation calculation.

(Second Invention) In the second invention for solving the above-mentioned problems, in the case of performing N-dimensional interpolation, the weighting coefficient is applied to the address of (M + 1) / 2 with respect to the interpolation interval M. By generating and performing multidimensional interpolation, it is possible to reduce the memory capacity for generating weighting factors and save hardware resources.

The weighting factor has the property of being line-symmetric in any direction with respect to the lattice point in the small space. This will be described with reference to the drawings. FIG. 8 is an explanatory diagram (one-dimensional case) of the property of the weight coefficient. The vertical axis represents the weighting coefficient, and the horizontal axis represents the distance between the grid points Q1 and Q2. In the figure, f1
Is a weighting characteristic for Q1, and f2 is a weighting characteristic for Q2. The distance at this time is the interpolation interval M. Considering the axis S passing through the center (M / 2) of this M, the weighting factors are line-symmetric with respect to this axis S.

That is, the right half of the characteristic f1 overlaps the left half of the characteristic f2 when folded back with respect to the axis S, and the right half of the characteristic f2 overlaps the left half of the characteristic f1 when folded back with respect to the axis S. For example, the weighting factors W1 and W of the right half of the characteristic f1
2 and W3 are the weighting factors W of the left half of the characteristic f2.
1 ′, W2 ′, W3 ′, and the right half weighting factors W4, W5 of the characteristic f2 become equal to the left half weighting factors W4 ′, W5 ′ of the characteristic f1, respectively. The address comes to M as shown in the figure, but when it exceeds S, Q1 and Q2 are switched. For example, the weighting coefficient of the characteristic f1 is sequentially generated according to the address, and when the address exceeds M / 2, the characteristic is switched from the previous f1 to f2 and the weighting coefficient of the left half of f2 is used.

Therefore, as the data of the weight coefficient, the axis S
It is only necessary to have the data on the left side, and it is not necessary to have the data on the right side of the axis S. In this way, the number of weighting factor occurrences can be reduced. The data amount of the necessary weighting coefficient is 1/2 in the one-dimensional case and 1 in the two-dimensional case.
It becomes 1/8 in the case of / 4 and 3 dimensions. In this way, the amount of data can be smaller than the originally required weighting factor data.

Since it is necessary to include the value W0 on the axis S as the address to be generated, the address is up to (M + 1) / 2 in consideration of the case where M is an even number.

According to the present invention, it is possible to reduce the number of weighting factors and save hardware resources. In this case, when performing the interpolation calculation of the N-dimensional LUT, by multiplying a plurality of color data among the values of the three colors or four colors of the LUT by the weighting factor at the same time, the hardware resources are saved, The interpolation calculation can be speeded up.

(Third invention) When the maximum weighting coefficient does not become a power of 2, the data to be stored in the color LUT is divided in advance, and a power of 2 is multiplied and stored. As a result, the division by the weighting factor, which is performed at the end of the interpolation calculation, can be performed only by shifting the data (shifting to the right), and the calculation time can be shortened.

(Fourth Invention) A means for giving the maximum value of the weighting coefficient for the interpolation at the interpolation interval M by M × 2 ^{N −1} is provided to suppress the maximum value of the weighting coefficient. As a result, it is possible to save hardware resources and speed up the calculation time. The process of ^obtaining M × 2 ^N−1 is the same as in the case of the first invention.

In this case, when performing the interpolation calculation of the N-dimensional LUT, by providing means for multiplying a plurality of color data among the values of three colors to four colors of the LUT by the weighting coefficient at the same time, Saves wear resources,
The interpolation calculation can be speeded up.

(Fifth Invention) When N-dimensional interpolation is performed, the weighting factor is (M + 1) for the interpolation interval M.
A means for generating an address of / 2 is provided. The reason is the same as in the case of the second invention. As a result, the number of weighting factors can be reduced, and hardware resources can be saved.

In this case, when performing the interpolation calculation of the N-dimensional LUT, by providing means for simultaneously multiplying a plurality of color data among the values of the three colors to four colors of the LUT by the weight coefficient, Saves wear resources,
The interpolation calculation can be speeded up.

(Sixth Invention) When the maximum weight coefficient does not become a power of 2, a means for dividing the data to be stored in the color LUT in advance and multiplying by 2 and storing the data is provided. The reason is the same as in the case of the third invention. As a result, the division by the weighting factor at the end of the interpolation calculation can be performed only by shifting the data (right shift),
The calculation time can be shortened.

[0039]

Embodiments of the present invention will be described below in detail with reference to the drawings. FIG. 1 is a configuration block diagram showing an embodiment of the present invention, and shows a case of N = 3, that is, three-dimensional interpolation. This embodiment receives R, G, B data and converts these data into new Rnew, Gnew, Bnew data. The numbers in the data lines in the figure indicate the number of bits.

In the figure, 1 is an R address generator that receives R (Red) data and a counter output and generates a corresponding address, and 2 is G that receives G (Green) data and a counter output and generates a corresponding address. The address generator 3 is a B address generator that receives B (Blue) data and generates a corresponding address. Reference numeral 4 denotes a 2-bit output quaternary counter that counts the clock CLK. When the upper bit of the output of the counter 4 is C1 and the lower bit is C0, C0 is stored in the R address generator 1,
C1 is input to the G address generator 2, respectively. The R address generator 1 and the G address generator 2 generate an 8-bit output, and the B address generator 3 performs parallel processing on the B axis, so that two types of 4-bit addresses are generated as upper addresses. The other R and G axes are calculated in time series.

5 is the lower 4 bits of the R address generator 1,
When the lower 4 bits of the G address generator 2, the lower 4 bits of the B address generator 3 and the output of the quaternary counter 4 are received, 7
A neighborhood weight generator for generating a bit weight coefficient, 6 is similarly the lower 4 bits of the R address generator 1, the lower 4 bits of the G address generator 2, and the lower 4 bits of the B address generator 3.
It is a weight generator for the distance, which receives the output of the bit and the quaternary counter 4 and generates a weight coefficient of 7 bits. For neighborhood,
For distant, the weighting factor space is divided into two, and one is for the neighborhood,
The other is for distance. In the present invention, as a result of using the line symmetry in the spatial area of the weighting factor, in the case of this embodiment, the required weight generator is 1 / (2 ³ ) = the original capacity because it is a three-dimensional space. Only 1/8. Therefore, the memory capacity is significantly reduced, and the hardware resources can be saved.

The upper 10 bits of the R address generator 1, the upper 4 bits of the G address generator 2, the two upper 4 bits of the B address generator 3, and the outputs of the weight generators 5 and 6 are used as new signals. An R processing unit that generates R data Rnew, 20 is the upper 4 bits of the R address generator 1, the upper 4 bits of the G address generator 2, and the B address generator 2
A G processing unit which receives the upper 4 bits of the type and the outputs of the weight generators 5 and 6 and generates new G data Gnew, 30 is the upper 4 bits of the R address generator 1, the upper 4 bits of the G address generator 2, A new B is generated by receiving the two types of upper 4 bits of the B address generator 3 and the outputs of the weight generators 5 and 6.
The B processing unit generates data Bnew. G processing unit 2
Although the configuration of the 0 and B processing units 30 is not shown, only the data stored in the color LUT is different, and the R processing unit 1
The configuration is the same as 0.

In the R processing unit 10, 11 is the upper 4 bits of the R address generator 1 and the upper 4 bits of the G address generator 2.
B, a color LUT for B neighborhood that receives one of the upper 4 bits of the B address generator 3, 12 is the upper 4 bits of the R address generator 1, the upper 4 bits of the G address generator 2, and the B address generator 3 It is a color LUT for the far B that receives the other upper 4 bits. These color LUT1
Reference numerals 1 and 12 are composed of memories in which the same data is stored in the upper and lower sides, for example. For example, a dual port RAM that can read two pieces of data at the same time is used. These LUTs
11, 12 are input of R, G, B data 0, 17, 34,
... 16 × 16 × corresponding to the combination of 238 and 255
16 × 10 pieces of data are stored. And output 10
Of the bits, 1 bit indicates a sign and 1 bit indicates a value exceeding 255.

13 is a multiplier for multiplying the output of the color LUT 11 and the output of the weight generator 5, and 14 is the color LUT 1.
2 is a multiplier for multiplying the output of 2 and the output of the weight generator 6. These multipliers 13 and 14 have color LUTs 11 and 1
A 10-bit output of 2 and a 7-bit output of the weight generators 5 and 6 are received, and a 16-bit output (of which 1 bit is a sign) is used. Reference numeral 15 is an adder that adds the outputs of the multipliers 13 and 14. The adder 15 includes multipliers 1 and 1
Receiving each 16 bits of 4 and outputting 16 bits (of which 1 bit is a code) data.

Reference numeral 16 is an integrator which integrates the outputs of the adder 15. The integrator 16 integrates only the value of the output of the quaternary counter, that is, the calculation result of four times. Reference numeral 17 is a divider for dividing the output of the integrator 16 by a weighting coefficient.
The divider 17 receives the 16-bit output of the integrator 16 and outputs 8-bit data. The output of the divider 17 becomes the converted new R data Rnew. The operation of the circuit thus configured will be described below.

The image data R, G and B are input to the respective address generators 1, 2 and 3 and the respective address generators 1 to 1 are inputted.
3 generates address data according to the following algorithm.

R address generator The input is A (0 to 255), and the upper digit of the output is X (0 to
15), the lower digit is Y (0 to 8), the upper input of the counter 4 is C0 (0, 1), and the lower digit is C1 (0, 1). The algorithm expressed in C language is as follows. Li (i = 1 to 8) indicates a line number. In the above algorithm, the remainder when L1: A is divided by 17 (A% 17) is 8 or less, and the remainder when L2: A is divided by 17 is taken as the value of Y. L3: X when A is divided by 17 and C0 is added to the quotient
Value of. L4: At this time, when X becomes larger than 15, the value of X is fixed to 15. When the condition of L5: L1 is not satisfied, that is, when the remainder when A is divided by 17 is 9 or more, the value of Y is obtained by subtracting the remainder when L is divided by 17 from L6: 17. L7: A value obtained by dividing the input A by 17 and adding (1-C0) is set as the value of X. L8: At this time, when X becomes larger than 15, the value of X is fixed at 15.

With such an algorithm, each time R data is input, the upper 4 bits of the R address generator 1 output the value of X and the lower 4 bits output the value of Y.

G address generator The operation is similar to that of the R address generator 1. That is,
The input is A (0 to 255) and the upper digit of the output is X (0 to
15), the lower digit is Y (0 to 8), the upper input of the counter 4 is C0 (0, 1), and the lower digit is C1 (0, 1). The algorithm expressed in C language is as follows. B address generator In this case, since parallel processing is performed for B, two higher-order 4-bit addresses are output at one time. In addition, the output of the quaternary counter 4 is not input because it is not necessary to divide it. The address generation algorithm is as follows, where X0 is for the vicinity of the upper digit and X1 is for the far portion of the upper digit. In the above algorithm, L1: the remainder (A% 17) when input A is divided by 17 is 8
In the following cases, L2: the remainder when the input A is divided by 17 is taken as the Y value. L3: X0 is the quotient when input A is divided by 17. L4: X of input A divided by 17 plus 1
Set to 1. L5: At this time, when X0 becomes larger than 15, the value of X0 is fixed to 15. L6: At this time, when X1 becomes larger than 15, the value of X1 is fixed to 15. When the condition of L7: L1 is not satisfied, that is, when the remainder when A is divided by 17 is 9 or more, the value of Y is obtained by subtracting the remainder when L is divided by 17 from L8: 17. L9: Input A is divided by 17, and 1 is added to X0.
Value of. L10: A value obtained by dividing the input A by 17 is set as the value of X1. L11: At this time, when X0 becomes larger than 15, the value of X0 is fixed to 15. L12: At this time, when X1 becomes larger than 15, the value of X1 is fixed to 15.

With such an algorithm, every time B data is input, the upper 4 bits of the B address generator 3 output the values of the two systems X0 and X1 and the lower 4 bits output the value of Y. It

Of the outputs of the address generators 1 to 3 thus generated, the upper data is the color LUT1.
1, 12 and the lower data enters the weight generators 5, 6. Of these, one upper data of the B address generator 3 enters the color LUT 11, and the other upper data enters the color LUT 12.

Here, the operation of the weight generators 5 and 6 will be described in detail. Due to the line symmetry of the weighting factors, the weight generators 5 and 6 store only the original 1/8 capacity data, and the 1/8 capacity data covers the entire range. To this end, each of the address generators 1 to 1 generates an address as follows.

For example, when the weighting interval M = 17, the original lower data is 0, 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14, 15, 16 occur, whereas in the present invention, 0, 1, 2, 3, 4, 5,
6, 7, 8, 8, 7, 6, 5, 4, 3, 2, 1 occur. That is, if an address is generated up to the midpoint of the interval M,
It is generated by folding the address from the midpoint. As a result, the lower data generated by the address generator is (M + 1) /
There are two types. For example, when M = 17, (17+
1) / 2 = 9 different values and data in the range of 0 to 8. By the way, when M = 16, (16 + 1) / 2
= 8.5, the decimal point is ignored and there are 8 different values.

At the same time, when the lower data is larger than the middle point of the lattice spacing, the output of the upper data is generated by reversing the reference lattice points in the order of +1, +0 instead of + 0, + 1. Let As a result, the weighting coefficient for the neighborhood is given to the neighboring grid points, and the weighting coefficient for the far distance is given to the distant lattice points. The address generator 3 for B has a fixed built-in two types of addresses for far and near, and generates an address according to an input.

The weight generators 5 and 6 receiving such addresses generate the weighting factors calculated in Tables 1 and 2 according to the converted addresses (lower data). Table 1 shows coefficients for weight calculation (for neighborhood), and Table 2 shows coefficients for weight calculation (for distance).

[0056]

[Table 1]

[0057]

[Table 2]

In these tables, r, g, and b are lower addresses (lower data generated from the address generators 1 to 3, r is from the R address generator, g is from the G address generator, and b is B. Generated from the address generator),
It takes a value of 0-8. C, R, G and B are coefficients for calculating weighting coefficients. These coefficients C, R, G, B are r,
The values shown in the table are taken according to the value of the quaternary counter 4 according to the magnitude relation between g and b. FIG. 2 shows a triangular pyramid applied according to the magnitude relation of r, g, and b (see FIG. 7). The weight coefficient to be generated is represented by the following equation.

W = M × C + r × R + g × G + b × B (3) For example, in the first combination r>g> b in Table 1, when the counter value = [00], the weighting factor to be generated is (3 )
From the formula, W = 4 × 17 + (− 4) × r + (− 2) × g + (− 1) × b. As can be seen, the weighting factor W is
The value is an integer of 0 to 68, and the sum of the weighting factors in the case of eight times of multiplication (to interpolate at 8 points to obtain the value of one point in the space) is 68.

The color LUTs 11 and 12 receive the outputs of the above-mentioned address generators 1 to 3 as an address and output a value corresponding to the address. The output of the color LUT 11 enters the multiplier 13, and the output of the color LUT 12 outputs the multiplier 1.
Enter 4. On the other hand, the outputs of the weight generators 5 and 6 are input to the other inputs of the multipliers 13 and 14, respectively. These multipliers 13 and 14 simultaneously multiply the output of the color LUT and the output of the weight generator. According to the present invention, since the sum of the weighting factors becomes equal to or less than 255 by performing the simultaneous multiplication, it is possible to perform the three-color simultaneous processing by the 8-point interpolation which cannot be performed by the conventional 64-bit CPU with the weighting factor of the rectangular parallelepiped. Become. As a result, the calculation speed can be significantly increased.

The outputs of these multipliers 13 and 14 enter the adder 15 and are added. The output of the adder 15 enters the integrator 16 and is integrated. The above operation is repeated four times, ie, 00, 01, 10, 11 which are the outputs of the counter 4 to perform interpolation calculation of 8 points. The integrator 16 calculates the sum total of these eight interpolation operations. The value accumulated by this integrator 16 is
(Result × sum of weighting factors), the subsequent divider 17
Is divided by the weighting factor (68 in this case). From the divider 17, new data Rnew of R converted by the interpolation calculation is output.

In this case, when the weighting coefficient of the divider 17 is not a power of 2 (as is the case with the above 68), division by the divider is necessary. However, the weighting factor is 2
When it is a power of, it is simply shifted to the right by the power, so that the divider is virtually unnecessary. Therefore,
If the data to be stored in the color LUTs 11 and 12 is divided by the weighting coefficient 68 in advance and is multiplied by 2 and stored, the divider 17 becomes unnecessary. If linear data is held in the color LUT, there is no difference between the final result obtained by using the divider and the final result obtained by the above operation.

The case of obtaining R data has been described above, but the same applies to the case of obtaining G data and B data. Various methods can be considered for the method of generating the weight coefficient by the weight generator. Whether all of the above equation (3) is performed in advance and the result is stored in the form of ROM, or the actual calculation is performed each time, or an intermediate method is taken depends on the hardware configuration. The following are some implementation methods.

(1) Method of Making All into ROM As shown in FIG. 3, a 16 KB ROM is used as an input address, 4 bits for each color. In ROM,
Pre-calculated weighting factors are stored. And
The 4-bit address of each of r, g, and b and the 2-bit output of the counter are received, and the 7-bit weight coefficient data stored in the corresponding address is output.

(2) Method of using encoder FIG. 4 shows a method of generating a weighting coefficient using an encoder. Paying attention to the range of the lower digits being 0 to 8, the first encoder 41 with 8-bit input and 7-bit output outputs r, g
The data corresponding to the input of is output and combined into one 7-bit data. For example, an LUT is used as the first encoder 41. The output of the first encoder 41 takes a value of 0-80. Next, the output of the first encoder 41 and the b input are encoded by the second encoder 42 to be combined into one piece of data. Finally, the output of the second encoder 42 and the output of the counter are input to the ROM 43, which outputs 7-bit weighting coefficient data. In this way, encoding is performed in two stages, and 0
By setting the value of ˜728 to the output range, the encoded output of the second stage is 10 bits, so that the size of the ROM 43 is 4 KB. By using the encoder, in the example shown in FIG. 3, the ROM capacity is 16 KB as compared with the ROM capacity of 16 KB.

(3) Method of obtaining all by calculation In this method, the equation (3) is calculated each time.
Since ROM is unnecessary, it takes a long time to calculate,
Not suitable for speeding up.

FIG. 5 is a block diagram showing another embodiment of the present invention, in which interpolation is performed using a central processing unit. Also in this case, three-dimensional interpolation is shown. Upon receiving the R, G, B data, the address generating means 50 generates a three-dimensional color LUT address as shown by 60. Color L
The UT stores four types of data of Y, M, C, and K as shown by 61. Here, since the last sequence in the interpolation calculation, division, is performed only by shifting,
The data stored in the color LUT is stored after being multiplied by 64/68. Therefore, the maximum value at this time is 25
It is 240 instead of 5.

The maximum value of the volume of the rectangular parallelepiped is about 13 bits (17 ³ when M = 17). If 13 bits are added to 8 bits of the original data, a calculation width of 21 bits is required. In this case, an attempt to calculate four colors at the same time requires a CPU with an extremely large number of bits. In the case of the present invention, since the maximum is 7 bits, multiplication of 8 bits and 7 bits does not exceed 16 bits. Therefore, it is 16 × 3 (in case of 3 colors) and CP of 64 bits
If U is used, it is possible to perform simultaneous 3-color simultaneous interpolation with 8-point interpolation.

When the R, G and B image data are input to the address generating means 50, the address generating means 50 calculates and outputs the upper digit and the lower digit as in the case of the above embodiment. The upper digit selects the color LUT, and the lower digit enters the weighting factor generating means 51 to generate the weighting factor. Color LU
The Y, M, C, K data read from T is rearranged in the 64-bit register 52 as shown in the figure.

The color LUT data required for eight multiplication accumulations is loaded into register 52, while the corresponding weighting factor data is provided. The calculation of this weighting factor is shown in Table 1.
Color LU as given by Table 2 and also required
The position of T depends on the lower bit, and the address generating means 50
It changes according to the output of.

The i-th LUT data and the i-th weighting factor Wi are multiplied by the accumulator (or ALU) 53. The multiplication result is sent to the integration register 54. This calculation is performed eight times, and the summation is performed by the summation register 54. When the integration of 8 times is completed, shift right by 6 bits. This is equivalently multiplied by 1/64. The shifted converted data is rearranged to correct it into a predetermined image format.

Next, modifications and applications of the present invention will be described. As the weight generating means, it is possible to use the volume of a rectangular parallelepiped on the opposite side that divides the conventional grid points. However, in this case, strictly speaking, the number of generated bits of the weighting coefficient is increased from 7 bits in the embodiment to 13 bits, and at the same time, it is necessary to use a high cost and wide bit width for the multiplier and the adder. Disappear.

It is confirmed that the weight coefficient is symmetric with respect to the grid point.
It is possible to use a method that does not save money. However, this place
In this case, the address generator does not need a counter input,
When the ROM is used, the memory capacity is half (in the embodiment
512 bytes to 256 bytes), and simple calculation
There are advantages. However, the weight generator in ROM
In the case of creating, in the embodiment, 2916 (= 9³× 4) Work
From 19652 (= 17 ³× 4) increase to words
Therefore, the total memory capacity will increase.

In the embodiment, the parallel processing and the serial processing (time series processing) are combined, but complete parallel processing or serial processing (example in FIG. 5) is also possible.

In the embodiment, the case of N = 3, that is, the case of three-dimensional interpolation has been shown, but the present invention can be easily expanded in the same manner in the case of four or more dimensions.
In the case of four dimensions, there are 24 types of weighting factors.
However, when the weighting coefficient is composed of ROM, it can be reduced to 1/16.

When the central processing unit simultaneously executes the interpolation calculation, it is possible to use the 32-bit register twice instead of the 64-bit at a time.

[0077]

As described above in detail, according to the first aspect of the present invention, the maximum value of the weighting coefficient for interpolation is given as M × 2 ^N−1 at the interpolation interval M, and the weighting is performed. The maximum value of the coefficient is suppressed. As a result, it is possible to save hardware resources and speed up the calculation time.

In this case, when performing the interpolation calculation of the N-dimensional LUT, hardware resources are saved by multiplying a plurality of color data among the values of three colors to four colors of the LUT at the same time. It is possible to save the cost and speed up the interpolation calculation.

According to the second invention, when N-dimensional interpolation is performed, the weighting coefficient is (M
It is possible to reduce the memory capacity for generating the weighting factor and to save the hardware resources by performing the multidimensional interpolation for the +1) / 2 address.

According to the present invention, it is possible to reduce the number of weighting factors, save hardware resources,
The amount of interpolation calculation can also be reduced. In this case,
When performing the interpolation calculation of the N-dimensional LUT,
By multiplying a plurality of color data among the values of colors to four colors by the weighting factor at the same time, it is possible to save hardware resources and speed up the interpolation calculation.

According to the third invention, when the maximum weighting coefficient does not become a power of 2, the data to be stored in the color LUT is divided in advance and is multiplied by a power of 2 and stored. As a result, the division by the weighting factor, which is performed at the end of the interpolation calculation, can be performed only by shifting the data (shifting to the right), and the calculation time can be shortened.

According to the fourth aspect of the present invention, means for giving the maximum value of the weighting coefficient for interpolation at M × 2 ^N−1 at the interpolation interval M is provided to suppress the maximum value of the weighting coefficient. This can save hardware resources,
The calculation time can be shortened. In this case, when performing the interpolation calculation of the N-dimensional LUT, the LUT
By providing a means for simultaneously multiplying a plurality of color data by the weighting coefficient among the values of 3 to 4 colors, the hardware resources can be saved and the interpolation operation can be speeded up.

According to the fifth invention, when N-dimensional interpolation is performed, the weighting coefficient is set to (M
A means for generating +1) / 2 addresses is provided.
The reason is the same as in the case of the second invention. As a result, the number of weighting factors can be reduced, and hardware resources can be saved.

In this case, when performing the interpolation calculation of the N-dimensional LUT, by providing means for simultaneously multiplying a plurality of color data among the values of the three to four colors of the LUT by the weighting factor, the hardware Saves wear resources,
The interpolation calculation can be speeded up.

According to the sixth aspect of the invention, when the maximum weighting coefficient does not become a power of 2, the data to be stored in the color LUT is divided in advance, and a means for storing a power of 2 is stored.
The reason is the same as in the case of the third invention. As a result, the division by the weighting factor, which is performed at the end of the interpolation calculation, can be performed only by shifting the data (shifting to the right), and the calculation time can be shortened.

As described above, according to the present invention, it is possible to provide a multidimensional interpolation method and device which can save hardware resources and increase the operation speed, and are extremely effective in practice.

[Brief description of drawings]

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

FIG. 2 is a diagram showing a triangular pyramid applied according to the magnitude relationship of r, g, and b.

FIG. 3 is a configuration diagram when a ROM is used as a weight generator.

FIG. 4 is a configuration diagram when an encoder is used as a weight generator.

FIG. 5 is a configuration diagram showing another embodiment of the present invention.

FIG. 6 is an explanatory diagram of cubic interpolation.

FIG. 7 is an explanatory diagram of triangular pyramid interpolation.

FIG. 8 is an explanatory diagram of properties of weighting factors.

[Description of Reference Signs] 1 R address generator 2 G address generator 3 B address generator 4 quaternary counter 5 weight generator 6 weight generator 10 R processing unit 11 color LUT 12 color LUT 13 multiplier 14 multiplier 15 addition Device 16 Accumulator 17 Divider 20 G processing unit 30 B processing unit

Claims (10)

[Claims] 1. When performing N-dimensional interpolation, the maximum value of the weighting coefficient for the interpolation is M ×, when the interpolation interval is M.
A multidimensional interpolation method characterized by performing multidimensional interpolation given by 2 ^N-1 . 2. The method according to claim 1, wherein when performing the interpolation calculation of the N-dimensional LUT, a plurality of color data among the values of three colors to four colors of the LUT are simultaneously multiplied by a weighting coefficient. Multidimensional interpolation method. 3. When performing N-dimensional interpolation, a weighting coefficient is generated for an address of (M + 1) / 2 with respect to an interpolation interval M, and multidimensional interpolation is performed. Method. 4. An interpolation calculation of an N-dimensional LUT, wherein a plurality of color data among the values of 3 to 4 colors of the LUT are simultaneously multiplied by a weighting factor. Multidimensional interpolation method. 5. When performing N-dimensional interpolation, when the maximum weighting coefficient does not become a power of 2, the data to be stored in the color LUT is divided in advance and stored as a power of 2. Multidimensional interpolation method. 6. An N-dimensional interpolating apparatus, comprising means for giving a maximum value of a weighting coefficient for interpolation at M × 2 ^N−1 at an interpolation interval M. 7. A means for multiplying a plurality of color data among the three-color to four-color values of the LUT by a weighting factor at the same time when performing the interpolation calculation of the N-dimensional LUT. The multidimensional interpolation device according to claim 6. 8. A multidimensional interpolating device, wherein in the N-dimensional interpolating device, means for generating a weighting coefficient for an address of (M + 1) / 2 with respect to an interpolation interval M is provided. 9. A means for multiplying a plurality of color data among the values of three to four colors of the LUT by a weighting factor at the same time when performing the interpolation calculation of the N-dimensional LUT. The multidimensional interpolation device according to claim 8. 10. An N-dimensional interpolating device is provided with means for dividing the data to be stored in the color LUT in advance and multiplying it by a power of 2 when the maximum weight coefficient is not a power of 2. And a multi-dimensional interpolation device.