JP3048227B2 - Multidimensional interpolation device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a color processing technique for digital color image data, and more particularly to a multidimensional interpolation which can be applied to color processing for reproducing the same color as an original in a color copying machine, a color printer, a color monitor and the like. Related to the device .

[0002]

2. Description of the Related Art In recent years, copiers and printers have become widespread in offices and are used on a daily basis. Recently, color documents have been output directly from a computer to a color printer, and printed color documents have been printed with a color copier. Copied in large quantities. As described above, when printing or copying a color document or image, there is a problem that the color of the document or image output by the device is different and sufficient color reproducibility cannot be secured. This depends on the type of color output device,
This is because the color of the printed matter is different because the dye is a toner, a dye, or an ink. Furthermore, while the RGB color data handled by the computer is colored by additive color mixture, the printer prints by subtractive color mixture, and the color mixture is also present in the pigment itself due to unnecessary absorption of the pigment. It is.

In order to solve the problem of color reproducibility between devices for color images and the like, a color processing method for improving the color reproducibility of an image device has been developed, and the color reproducibility of the device has been gradually improved. .

[0004] For example, in a PostScript printer, input image data is corrected based on a color rendering dictionary (CRD) representing the characteristics of a device so that a desired color is reproduced, and then printed.

In an electrophotographic color copying machine,
After color correction of RGB color data obtained by a color scanner using a matrix operation or a three-dimensional lookup table, printing is performed by a color engine.

Hereinafter, an example of a color correction method using a three-dimensional lookup table will be described.

FIG. 5 shows a flow of image signal processing in a general color copying machine.

A color document 401 is scanned by a scanner 402 in RG mode.
The data is read as B data, subjected to printer color correction by the color correction unit 403, printed by the printer 404, and output as a duplicate image 405.

FIG. 6 is a functional block diagram when the color correction unit 403 performs a three-dimensional interpolation operation using a three-dimensional lookup table (3D-LUT). Input signal (R,
G and B) are separated into an upper bit and a lower bit by an image input unit 501, and the upper bit is used to extract a plurality of grid point data used for an interpolation operation from a 3D-LUT (three-dimensional lookup table) 502. , And the lower bits are used by the weight coefficient calculator 503 to calculate a weight coefficient required for the interpolation operation. The interpolation calculation unit 504 performs weight multiplication of the output from the weight coefficient calculation unit 503 and the output from the 3D-LUT 502 to obtain an image output C corresponding to the input point.
MYK is calculated.

FIG. 7 shows a state in which a three-dimensional input color space (RGB space) is divided by a limited number in each axis direction and is divided into unit solids. The color correction data at the lattice points of the unit solid is stored as lattice point data in the 3D-LUT 502, and an output value color-corrected corresponding to the input is obtained from the lattice point data by an interpolation operation.

A three-dimensional color correction method in which interpolation is performed by using eight grid point data and eight interpolation coefficients as color correction data and three-dimensionally interpolated by a cubic interpolation method will be described as a first conventional example.

In Conventional Example 1, as shown in FIG. 8, a unit solid is divided into eight by three planes perpendicular to each axis from an input data point.
The output value at the input point position is obtained by performing a product-sum operation on the eight grid point data as weight coefficients of the grid point data opposing each volume. In this case, the color correction data Pout is calculated from the equation (1) by interpolation.

[0013]

(Equation 1) Here, the weighting coefficient Wijk is the lattice point data P (1-i) (1-j) (1-
k), and

[0014]

(Equation 2) It is represented by Δx, Δy, and Δz are distances representing the distance from the reference point (P000) of the input data in each unit solid based on the length of each side of the unit solid.

As a second conventional example, there is a method in which a unit solid is divided into a plurality of tetrahedrons and an interpolation operation is performed in the tetrahedron, which is described in, for example, Japanese Patent Publication No. 58-16180. As shown in FIG. 9, the unit solid is divided into six tetrahedrons, and the interpolation output is calculated by equation (3) depending on which tetrahedron the input point belongs to.

[0016]

(Equation 3) Next, when a color image is represented by four color signals of CMYK, it can be dealt with by expanding the input of the first conventional example to four dimensions. That is, an interpolation operation is performed within a unit hypercube formed by dividing each axis of the four-dimensional input space by a limited number.
Using 2 × 2 × 2 × 2 = 16 hypersolid volumes divided by a vertical plane from the input image point in the unit hypercube to the four axes as weighting coefficients, interpolation calculation in the case of four-dimensional input can be performed by the following equation.

[0017]

(Equation 4) This is also expressed as in equation (5).

[0018]

(Equation 5) Further, when this is extended to N dimensions, an N-dimensional interpolation calculation output PoutN is calculated by the equation (6).

[0019]

(Equation 6) A method in which Conventional Example 2 is extended to four dimensions is disclosed in
-226866. The interpolation method described in the same publication divides a four-dimensional interpolated solid into 24 hyperpentahedrons, determines which hyperpentahedron the input point belongs to,
Four-dimensional interpolation is performed by the product-sum operation of the output values at the five vertices of the hyperpentahedron and the five weighting coefficients. In this case, the number of product-sum operations is reduced to 5 times as compared with 16 times required when conventional example 1 is expanded to four dimensions. There are 20 types compared to the 16 types of the first conventional example.

[0020]

In the first conventional example, as the number of dimensions of the input color signal increases, the number of product-sum operations rapidly increases. For example, when a four-dimensional color correction is performed by a cubic interpolation method and an interpolation operation is performed by a four-dimensional lookup method, one pixel is calculated by using 1 as a weight coefficient calculation.
Six multiplications of 3 times = 48 times and calculation of the interpolated output value require 16 product-sum operations. 8x2 = 16 for three-dimensional case
There is a problem that the calculation amount is extremely increased as compared with the multiplication of the number of weight coefficients and the product-sum operation of eight times. Further, in the case of multi-dimension, more multiplication is required, and in the case of N-dimension, the operation is

[0021]

(Equation 7) is necessary.

Further, since the number of grid point data for performing the interpolation operation is 2 to the Nth power, the number of memory accesses to the multi-dimensional lookup table increases, and the calculation speed decreases.

Further, the conventional example 2 has a drawback that the number of types of calculation of the weight coefficient increases and the calculation formula increases. Calculating in advance and storing it in the ROM prevents the number of calculations from increasing, but has the disadvantage that the memory capacity of the ROM increases as the number of dimensions increases. For example, if the lower 4 bits of the input signal are used for calculating the weight coefficient, when performing four-dimensional interpolation, a ROM of (2 (4 (bit) × 4 (dimension) = 16) = 64 K words) is used for the weight coefficient. Is required. As the number of interpolation dimensions increases, the memory capacity rapidly increases.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-mentioned problems of the prior art, and suppresses an increase in the number of multiplications when performing multidimensional interpolation. Can be expanded to multiple dimensions , and the operation speed is further increased
It is an object of the present invention to provide a multidimensional interpolation device capable of achieving the following.

[0025]

According to the present invention, the following means are taken to solve the above-mentioned problems.

According to the first aspect of the present invention, each of the N-dimensional input points
Axis data is converted to upper data (Oh1, Oh2, ..., Oh
N) and lower data (Ol1, Ol2, ..., OlN).
Data division part to divide, and each unit hypercube top in N-dimensional space
Output data corresponding to points is not duplicated (N + 1)
N-dimensional divided memory divided and stored in
Interpolation coefficient selector that sorts and outputs the
And the order for determining the order of the size of the lower data
A determination unit, and the unit hypercube according to the order determination result
Before each end point when N ridge lines are sequentially selected from the origin of
The relative address from the origin of the unit hypercube (C1, C2,
.., CN) and the relative address generator
Address (C1, C2, ..., CN) and the upper data
(Oh1, Oh2, ..., OhN) N-dimensional interpolated hypercube
(N + 1) divided memories corresponding to each vertex of
Select signal Mi (i is a memory number and 0 to N
Number) and the address of each vertex in the (N + 1) divided memories
The signal MAi is

(Equation 2) Here,% indicates the remainder of the division, and / indicates the quotient of the integer division.
The generated as shown (N + 1) number of address generators
To the memory selected by the select signal Mi.
(N) for distributing the corresponding address signal MAi
+1) address selectors and the size of the lower data
Used for interpolation coefficient calculation based on the
Is the output data of the N-dimensional divided memory
A data selector to be selected from the interpolation coefficient selector.
The output was selected as the interpolation coefficient by the data selector.
A configuration including an interpolation operation unit that performs an interpolation operation on output data
Take.

According to such a multidimensional interpolation device, the Nth order
Each of the interpolated hypercubes is determined by the order of magnitude of each axis position of the original input point.
Select the output data corresponding to the vertices,
Output data corresponding to each vertex can be easily obtained.
The increase in the number of multiplications that occurs in multidimensional interpolation
it can. Moreover, each unit hypercube vertex in the N-dimensional space
The corresponding output data without duplication (N + 1)
Corresponding to each vertex of one interpolated hypersolid
Output data to be extracted in parallel
Compared to accessing the serial many times
The operating speed can be increased.

[0028]

[0029]

[0030]

[0031]

[0032]

[0033]

[0034]

[0035]

[0036]

[0037]

[0038]

[0039]

[0040]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be specifically described below.

(Embodiment 1) In Embodiment 1, a multidimensional unit hypercube (here, N
Is defined by a line connecting its origin and its diagonal point and N ridge lines which are orthogonal and connected to each other of a hypercube. Divided into pieces of N-dimensional super stereoscopic performs interpolation calculation in the N-dimensional super stereoscopic this <br/>.

When such hypercube interpolation is used, the N ridge lines from which the interpolated hypercube is selected are perpendicular to each other and parallel to each axial direction of the N-dimensional space. The value obtained by adding the linear sum of the quantities to the origin output value is the output of the multidimensional interpolation operation.

Therefore, the interpolation operation is performed by multiplying the output difference value of the end point of the ridge line by the distance from the origin on each ridge line and cumulatively adding the multiplied value to the output value of the origin of the multidimensional cubic lattice. Can do things.

Here, orthogonal to each other from the unit hypercube
Describes a method of selecting the N-dimensional super solid having N number of ridge lines (interpolation super solid).

FIG. 1 is an explanatory diagram of a dividing method in the case of five dimensions (N = 5). Referring to FIG.
A method of selecting five ridge lines from a unit hypercube formed by upper signals of a five-dimensional input signal having five axes of Z, A, and B will be described.

FIG. 1A shows the input upper signals (Xh, Yh, Z).
h, Ah, Bh) shows the relation between the unit hypercube selected by (h, Ah, Bh) and each input axis.
The directions of the dimensional axis and the five-dimensional axis are shown. FIG. 1B shows a case where the relationship of Δx>Δy>Δa>Δz> Δb is obtained by ordering the lower signals (Δx, Δy, Δz, Δa, Δb) of the input signal. This indicates that the ridge line in the X-axis direction, which is the maximum ranking direction, is selected from the five ridge lines extending from the origin O of the hypercube. FIG.
(3) is a second ridge line extending from an end point of the first ridge line and excluding the direction of the first ridge line.
The ridge line in the Y direction, which is the second order of the lower signal, is selected from the ridge lines. FIG. 1 (4) shows, as a third ridge line, a ridge line newly extending from an end point of the second ridge line and a third order of lower-order signals from three ridge lines excluding the first and second ridge line directions. The ridge line in the A direction, which is the name, is selected. FIG. 1 (5) shows the fourth ridge line as the fourth ridge line newly extending from the end point of the third ridge line and excluding the first, second, and third ridge lines from the two ridge lines. The ridge line in the Z direction, which is the second ranking, is selected. Fig. 1 (6)
Is the last ridge line, the ridge line newly extending from the end point of the fourth ridge line, the remaining one ridge line excluding the first, second, third, and fourth ridge line directions, and the fifth rank of the lower signal The ridge line in the B direction, which is the name, is selected as the fifth ridge line.
Finally, a supersolid surrounded by six vertices of a total of six line end points connecting the end point of the fifth ridge line and the origin of the unit hypercube is selected as the interpolation solid. The position of the input signal in the five-dimensional space is in the selected interpolated hypercube, and this hypercube is used as the interpolated solid.

When such an interpolation solid selection algorithm is used, FIG. 1 can be easily extended to N dimensions, which can be said to be a rational interpolation solid selection method. In addition, there are N types of selection for the selection of the first ridge line, and (N-1) types of selection for the selection of the second ridge line, hereinafter (N-2), (N-
3),. . . , 2, 1 type, there is a total of N
! Since there is a choice of types, the unit interpolation hypercube is N! It can be seen that the image is divided into a plurality of interpolated hypercubes.

According to such an embodiment, a multidimensional interpolation solid to be interpolated by selecting N edges of the N-dimensional interpolation solid based on the input signal is specified, and a read address of the multidimensional memory is determined. (N + 1) grid point data required for the interpolation operation can be extracted. That is, by rearranging the lower signals of the input signal in the descending order, and sequentially selecting the ridges in the axial direction of the signal having the larger lower signal, the N ridges which are orthogonal and connected to each other can be rationally formed. You can choose. Also, by reading the data of the multidimensional memory at the end point position of the connected ridge line, the N-dimensional hypercube lattice point data can be read in order. Since the interpolation operation is performed using the ordered grid point data and the ordered lower signals, an increase in the number of multiplications that occurs when performing multidimensional interpolation can be suppressed.

The present invention can be applied to a color adjustment device that simulates a print result by converting print data having four or more color data such as CMYK into RGB data, and a color correction device for four-color data. Also, when there are four or more colors,
The same technique can be easily applied.

Second Embodiment A second embodiment is an example in which the multidimensional interpolation method of the first embodiment is applied to a multidimensional color correction device.

This multi-dimensional color correction apparatus includes an input signal dividing means for dividing an input multi-dimensional color signal into an upper part and a lower part, and calculates in advance output values of discrete input points in an N-dimensional input color space. Multidimensional memory means for storing and storing, unit hypercube selecting means for selecting a unit hypercube using the signal of the upper part as an address signal and selecting one unit hypercube corresponding to the upper part from the multidimensional memory; N! Constituting a unit hypercube for performing an interpolation operation from the unit hypercube obtained Means for ordering the lower parts in descending order in order to select one from the (N + 1) planes, means for selecting N mutually connected and orthogonal ridge lines from the unit hypercube according to the ordering result, The data reading means for reading out the output data of the total (N + 1) points of the end points of the N ridge lines and the respective connection positions from the multidimensional memory in the connection order, and ordered (N + 1) lattice point output data. An interpolation calculation unit that performs multidimensional interpolation using the lower part as a weight coefficient.

In order to increase the speed of the multidimensional color correction apparatus, the multidimensional memory is divided into (N + 1) sub memories in the above configuration, and grid point data is stored. (N + 1) hyper-solid grid point data required for interpolation can be simultaneously read out by the address generators.

By adopting such a configuration, it is possible to avoid a time loss caused by accessing the multidimensional memory (N + 1) times.

(Embodiment 3) FIG. 2 is a block diagram showing a flow of signal processing of a four-dimensional color correction apparatus according to the present embodiment. In FIG. 2, reference numeral 201 denotes an input signal CMYK input by the data division unit, which is divided into upper parts Ch, Mh, Yh,
Kh and the lower parts Δc, Δm, Δy, Δk are divided and output. 202 is an address generator for selecting the unit hypercube selected by the upper signal, and 203 is a multidimensional memory which stores output values at positions corresponding to the upper bits of the input signal, respectively. Outputs the memory value of the grid point. Reference numeral 204 denotes a lower-order signal ranking determination unit 206
Selector for selecting five grid point data necessary for interpolation from 16 multi-dimensional memories according to the output from the controller 205. The lower part of the input signal ranked with the five selected grid point data is assigned a weight coefficient. Is an interpolation operation unit that performs a product-sum operation. Reference numeral 206 denotes an input lower-order order determining unit. Based on the result, the selector 207 rearranges the input lower-order signals in descending order or controls the operation of the selector 204 as a selection signal to select the grid point data. I do. The corrected color signal is output from an output line 208.

In FIG. 2, the output is one-dimensional.
If ２０５ 205 are multiplexed, it is possible to take out only the multiplexed outputs. Also, by rewriting the contents of the multidimensional memory, it is possible to sequentially obtain color signal outputs.

The operation of the four-dimensional color correction device configured as described above will be described in detail.

The input signal is converted into an 8-bit four-color signal as a CM signal.
The data division unit 201 divides the YK signal into upper data and lower data. Here, it is divided into upper 4 bits and lower 4 bits.

[0058]

(Equation 8) The lower-order signals Δc, Δm, Δy, and Δk are determined by the order determining unit 206 in order of magnitude, and are rearranged by the interpolation coefficient selector 207 based on the order determination result. The results are Δmax, Δmid-high, Δmid-low, and Δmin.

[0059]

(Equation 9) These rearranged coefficients are input to the interpolation calculation unit 205.

On the other hand, the upper data Ch, Mh, Yh, Kh
Is input to the address generation unit 202, selects a unit four-dimensional hypercube starting from the origin of the four-dimensional space indicated by the address of the upper data, and stores the data of the 16 vertices of the hypercube in the multidimensional memory 203. Remove from From the extracted 16 grid point data, the order determination unit 206
The five data required for the four-dimensional interpolation operation are extracted in order according to the judgment result of (1). The data is taken out by the data selector 204, but P0 and P4
Since the lattice point positions are determined, the data selector 204 actually selects three types, P1, P2, and P3.

Specifically, the selector signal S1 of the first vertex P1 of the four-dimensional interpolation solid is

[0062]

(Equation 10) Set to. Next, the selector signal S2 of the second vertex P2
To

[0063]

[Equation 11] Set to. Further, the selector signal S of the third vertex P3
3

[0064]

(Equation 12) Set to.

According to the three selector signals, 1 to 14
P1, P2, and P3 data are selected from the number-th multidimensional memory data. The selector signals are (0, 0, 0, 0) and (1,
If the values other than (1, 1, 1) are taken and the binary representation of the selector signal is displayed in decimal, it corresponds to the values of 1 to 14, which corresponds to FIG.
Corresponds to the output number of the multidimensional memory.

The interpolation calculation unit 205 calculates the interpolation output Pout by the calculation of the equation (13) using the weight coefficient data of the equation (9) and the grid point data P0 to P4 of the coordinates of the equations (10) to (12). Get.

[0067]

(Equation 13) In the above description, four-dimensional interpolation is taken as an example, but it can be easily extended to N-dimensional interpolation. It expands equation (8) to N dimensions to separate N sets of upper and lower signals, and (9)
The order determination of the lower part is extended from four to N in the equation, the number of selected grid points becomes (N + 1), and the number of product-sum operations in equation (13) is extended to N. .

According to such an embodiment, the lower-order signal is used as it is as the weighting factor in the interpolation operation, and even in the case of the multidimensional interpolation operation, there is an effect that the number of operations does not increase so much as the dimension increases.

(Embodiment 4) FIG. 3 is a block diagram showing the flow of signal processing of the four-dimensional color correction apparatus according to the present embodiment.

In this embodiment, the multidimensional memory 203 used in the third embodiment is divided into five parts corresponding to five vertices of a four-dimensional super-interpolated solid. The four-dimensional input signal CMY
K is an upper part Ch, Mh, Yh,
Kh and lower parts Δc, Δm, Δy, Δk, and the lower part signals are ordered by the order determination unit 306 in the descending order. low, Δ
It is the same as in the third embodiment that the data is rearranged to min and input to the interpolation calculator 305.

Next, how the multidimensional memory is divided into five memories will be described with reference to FIG. When the reference point of the four-dimensional unit hypercube is represented by (0, 0, 0, 0), it is assumed that the reference point is stored in Mem0, and the four points that have moved one along the hypercube ridge line from this reference point are Since only one of these four points is selected in the process of selecting an interpolated solid, even if these four points are stored in the same memory Mem1, they are not redundantly read from Mem1 as grid points of the interpolated solid. , 0, 0, 0), (0, 1, 0, 0),
(0, 0, 1, 0) and (0, 0, 0, 1) are stored in Mem1. Next, the four points that have moved one edge line with (1, 0, 0, 0) as the origin are not read out in the same manner, so (2, 0, 0, 0), (1, 1, 0) , 0),
(1, 0, 1, 0) and (1, 0, 0, 1) are stored in Mem2. Next, the four points that have moved one edge line with (1, 1, 0, 0) as the origin are not read out in the same manner, so (2, 1, 0, 0), (1, 2, 0) , 0),
(1, 1, 1, 0) and (1, 1, 0, 1) are stored in Mem3. Next, the four points that have moved one ridge line with (1, 1, 1, 0) as the origin are not read out in the same manner, so (2, 1, 1, 0), (1, 2, 1) , 0),
(1, 1, 2, 0) and (1, 1, 1, 1) are stored in Mem4. FIG. 4 shows the types of memory in which the values of the vertices of the interpolation solid are stored in which memory by the above method.

As described above, by dividing the multidimensional memory and dividing and storing the grid point data, five kinds of 4
Since the values of the dimension table can be read at the same time, the reading speed becomes (N + 1) times for parallel reading as compared with the case of sequentially accessing and reading the multidimensional memory, thereby enabling high-speed operation.

Here, the reference point of the four-dimensional unit hypercube is M
Although em0 is used, for example, the reference point of the unit hypercube adjacent in the X-axis direction is stored in Mem1, and the memory of the reference point changes depending on the position of the unit hypercube. Therefore, the method of memory division storage will be described in detail.

In the case of four-dimensional data, the input four-dimensional color space is equally divided into four equal parts by four bits on each axis, and each axis has 17 grid points including the last grid point. Therefore, if the address of each grid point is (x, y, z, k) and the grid point data of this point is P (x, y, z, k), P (x, y, z,
The memory type (Mem0 to 4) for storing k) and its memory address are determined by equation (14).

[0075]

[Equation 14] Here,% indicates the remainder of the division, and / indicates the quotient of the integer division. When these are extended to N dimensions,
If each axis is divided into 16, and the multidimensional address of each grid point is (A1, A2, A3,... AN) i, the type of memory Mi to be stored and its memory address Ai are (15)
It is represented by an equation.

[0076]

(Equation 15) A method of generating a read address for each divided memory stored based on the above principle will be described.

The correction address generated by the correction address generator 309 in FIG. 3 is a relative address of the address of each end point from the unit hypercube origin when four edges are sequentially selected from the origin of the unit hypercube. For example, in the case of FIG. 4, the output of each correction address generator 302 is
The origin of the four-dimensional interpolation solid is (0, 0, 0, 0), the first vertex is (1, 0, 0, 0), and the second vertex is (1, 0, 0).
(1, 0, 0), (1, 1, 1, 0) for the third vertex, and (1, 1, 1, 1) for the fourth vertex.

From the absolute address of each vertex obtained by adding this value and the absolute address of the origin, the type and address of the memory storing the grid point data of each vertex can be calculated by equation (15). That is, assuming that the origin memory address O of the unit interpolation hypercube and the output of the address corrector for each lattice point P are C, the address A of each lattice point is

[0079]

(Equation 16) Can be represented by Therefore, the memory type Mi and the address MAi storing the output value at the position of each vertex are:

[0080]

[Equation 17] Is represented by

Here, the address generator 302
The memory type Mi corresponding to the lattice points P0 to P4 and the respective addresses MAi were calculated. Address selector 3
Reference numeral 10 switches the memory address MAi to the address of the corresponding memory Mem0 to Mem4 using Mi as the select signal SELi. The switching of the memory address for each of the lattice points P0 to P4 is described below. The following correspondence table is P0
To P4. SEL signal (SELi = Mi) Type of memory for distributing addresses 0 Mem0 1 Mem1 2 Mem2 3 Mem3 4 Mem4 Further, the read data is selected by the data selector 304 in the same correspondence table as described above and input to the interpolation operation unit 308. Is done. The interpolation calculation unit 308 calculates by the equation (13) as in the third embodiment.

The fourth embodiment can also be easily extended to multi-dimensions. When the data is expanded to N dimensions, the division memory 303 in FIG. 3 is divided into (N + 1) pieces, and the corresponding address generators 302 and correction address generators 309 are expanded to (N + 1) pieces. Also, the order determination unit 306,
The input and output of the interpolation coefficient selector 307 and the data division unit 301 are N sets, and the input and output of the data selector 304 are (N +
1) Expanded to a set. In this case, the expression (17) is extended to the expression (18).

[0083]

(Equation 18) Although the multi-dimensional color correction apparatus has been described as an example, the present invention can also be applied to general multi-dimensional spatial coordinate interpolation processing.

[0084]

As described above, according to the present invention, the interpolation solid by the N-dimensional interpolation method (N is an integer of 4 or more) is defined by the origin and the unit of the unit hypercube selected by the N sets of input higher-order signals. N! Surrounded by one line connecting the diagonal points of the hypercube and the ridges of N unit hypercubes that are orthogonal to each other and can be connected continuously. By selecting an N-dimensional hypercube having N edges selected in the same direction as when the input lower-order signals are arranged in descending order of the input lower-order signals from the types of N-dimensional hypercubes, the interpolation coefficient for interpolation is lower than the input lower-order signal. Only the signals are exchanged in the order of magnitude, and the number of times of multiplication is N and the interpolation operation can be executed.

According to the present invention, the multidimensional memory is divided into (N + 1) pieces as sub memories, so that the output data corresponding to each vertex is divided into a plurality of sub memories without overlapping the unit hypercube. Since the stored data and the output data corresponding to each vertex can be read from the multidimensional memory at the same time, the operation can be speeded up and can be easily expanded to multidimensional.

[Brief description of the drawings]

FIG. 1 is a state transition diagram illustrating a state in which an edge of an interpolated hypercube is selected from a unit hypercube according to Embodiment 1 of the present invention.

FIG. 2 is a block diagram of a multidimensional color correction device according to a third embodiment of the present invention.

FIG. 3 is a block diagram of a multidimensional color correction device according to Embodiment 4 of the present invention.

FIG. 4 is a conceptual diagram showing a relationship between grid point data of an interpolation solid and a sub memory.

FIG. 5 is a functional block diagram of a conventional color copying machine.

FIG. 6 is a block diagram of a conventional color correction device.

FIG. 7 is a division diagram of an input color space when a color is corrected using a three-dimensional table.

FIG. 8 is an explanatory diagram of a conventional three-cube interpolation method.

FIG. 9 is a space division diagram in a conventional tetrahedral interpolation method.

[Explanation of symbols]

 201 data division unit 202 address generation unit 203 multidimensional memory 204 data selector 205 interpolation calculation unit 206 order determination unit 207 interpolation coefficient selector 208 interpolation output terminal 302 address generator 303 division memory 304 data selector 305 interpolation calculation unit 306 order determination unit 307 Interpolation coefficient selector 309 Correction address generator

──────────────────────────────────────────────────続 き Continuation of front page (72) Inventor Hideto Motomura 3-10-1, Higashi-Mita, Tama-ku, Kawasaki-shi, Kanagawa Prefecture Matsushita Giken Co., Ltd. (56) References JP-A-7-141489 (JP, A) JP-A-7-99587 (JP, A) JP-A-5-328113 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) G06T 5/00-5/50 G06T 1/00 -1/60 G09G 5/00-5/36 H04N 1/46-1/62 G06F 17/17

Claims (1)

(57) [Claims] 1. The data of each axis of an N-dimensional input point is stored in a high-order data.
(Oh1, Oh2,..., OhN) and lower data (Ol
1, Ol2,..., OlN);
Output data corresponding to each unit hypercube vertex in N-dimensional space
Is divided and stored in (N + 1) memories without duplication.
And the lower-order data are arranged in ascending order.
An interpolation coefficient selector for replacing and outputting the lower-order data;
Order determination unit for determining the order of the size of
N ridges from the origin of the unit hypercube
From the unit hypercube origin of each end point when sequentially selected
Generating relative addresses (C1, C2,..., CN)
A positive address generator and the relative addresses (C1, C2,
.., CN) and the upper data (Oh1, Oh2,.
hN) corresponding to each vertex of the N-dimensional interpolation hypercube (N +
1) Select signal Mi (i is selected) for selecting the divided memories
(Memory number, integer from 0 to N) and (N + 1) divisions
The address signal MAi of each vertex in the memory is expressed by : Here,% indicates the remainder of the division, and / indicates the quotient of the integer division.
The generated as shown (N + 1) number of address generators
To the memory selected by the select signal Mi.
(N) for distributing the corresponding address signal MAi
+1) address selectors and the size of the lower data
Used for interpolation coefficient calculation based on the
Is the output data of the N-dimensional divided memory
A data selector to be selected from the interpolation coefficient selector.
The output was selected as the interpolation coefficient by the data selector.
Multi-order comprising an interpolation operation unit for performing an interpolation operation on output data
Original interpolator.