Image interpolation method, medium and system

An image interpolation method interpolating image information of a point in a space constructed by a plurality of planes. According to the method, a reliable interpolated value can be rapidly obtained by searching for the nearest plane to the point, obtaining information about a plane facing the nearest plane using image information of one or more vertices of the plane facing the nearest plane, and interpolating the image information of the point using the image information of the one or more vertices of the nearest plane and the obtained information about the plane facing the nearest plane.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of Korean Patent Application No. 10-2006-0070454, filed on Jul. 26, 2006, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.

BACKGROUND

One or more embodiments of the present invention relate to interpolation, and more particularly, to a method, medium and system interpolating image information of a point in a three-dimensional space using image information of nearby vertices.

2. Description of the Related Art

Interpolation is used to estimate a value of a point using known values at other points.

Interpolation techniques may be developed to improve reliability of interpolated values or to increase interpolation speed. There is a trade-off between improvement in the reliability of the interpolated values and the speed of interpolation.

Accordingly, a new interpolation method capable of securing suitable reliability and suitable interpolation speed is needed.

SUMMARY

One or more embodiments of the present invention provide an image interpolation method capable of rapidly obtaining a reliable interpolated value.

One or more embodiments of the present invention also provide an image interpolation system capable of rapidly obtaining a reliable interpolated value.

One or more embodiments of the present invention also provide a computer-readable recording medium having embodied thereon a computer program for executing an image interpolation method capable of rapidly obtaining a reliable interpolated value.

To achieve at least the above and/or other aspects and advantages, embodiments of the present invention include an image interpolation method interpolating image information of a point in a space formed by a plurality of planes. The method includes searching for a nearest plane to the point, obtaining information about a plane facing the nearest plane using image information of one or more vertices of the plane facing the nearest plane, and interpolating the image information of the point using the image information of the one or more vertices of the nearest plane and the obtained information about the plane facing the nearest plane.

To achieve at least the above and/or other aspects and advantages, embodiments of the present invention include an image interpolation system interpolating image information of a point in a space formed by a plurality of planes. The system includes a base-plane searching unit to search for a nearest plane to the point, an operation unit to compute information about a plane facing the nearest plane using image information of one or more vertices of the plane facing the nearest plane, and an interpolation unit to interpolate the image information of the point using the image information of the one or more vertices of the nearest plane and the computed information about the plane facing the nearest plane.

To achieve at least the above and/or other aspects and advantages, embodiments of the present invention include at least one medium including computer readable code to control at least one processing element in a computer to implement a method of interpolating image information of a point in a space formed by a plurality of planes. The method includes searching for a nearest plane to the point, obtaining information about a plane facing the nearest plane using image information of one or more vertices of the plane facing the nearest plane, and interpolating the image information of the point using the image information of the one or more vertices of the nearest plane and the obtained information about the plane facing the nearest plane.

DETAILED DESCRIPTION OF EMBODIMENTS

FIG. 1illustrates a field of the invention.

In order to display an authorized three-dimensional (3D) graphic data on a two-dimensional (2D) screen, the 3D graphic data generally needs to be rendered, that is, visualized.

Texture mapping is one of the procedures for rendering the 3D graphic data. Texture mapping may be used to apply a 2D image for representing a texture (hereinafter, referred to as “texture image”) to a 3D model represented by the 3D graphic data.

In order to perform the rendering, a distance (hereinafter, referred to as “viewpoint distance”) between the 3D model and a viewpoint may need to be defined. The longer the viewpoint distance, the lower the texture image resolution applied to the 3D model may be. On the contrary, the shorter the viewpoint distance, the higher the texture image resolution applied to the 3D model may be.

In order to perform texture mapping, a plurality of texture images with respect to a plurality of viewpoints may be stored in a rendering device. As shown inFIG. 1, three texture images110,120, and130with respect to three viewpoints may be stored in the rendering device. Here, the number of texture images is three for convenience of description and other quantities may be used.

InFIGS. 1A-1D, a relationship between the viewpoints and the resolution of the texture images is schematically shown.

The resolution (for example, 512×512 pixels) of the texture image110shown inFIG. 1Bmay be twice that (for example, 256×256 pixels) of the texture image120shown inFIG. 1C. The resolution of the texture image120shown inFIG. 1(c) may be twice that (for example, 128×128 pixels) of the texture image130shown inFIG. 1D.

It may be impossible for the rendering device to store texture images with respect to all possible viewpoints. Therefore, when a texture image140that is to be applied to the 3D model is not stored in the rendering device, the texture image140that is to be applied to the 3D model may need to be interpolated using the stored texture images.

Various interpolation techniques may be used in rendering fields, and furthermore in various image processing fields. The various interpolation techniques may also be used in the image interpolation method, medium and system, according to an embodiment of the present invention.

FIG. 2illustrates linear interpolation. The linear interpolation may indicate an interpolation that is to be performed in one-dimension (1D).

As shown inFIG. 2, a value at a third point214may be interpolated using a value (a) at a first point210(for example, color information) and a value (b) at a second point212. Specifically, the value at the third point214may be interpolated using Equation 1.
Interpolated value at the third point 214=a*(1−p)+b*p,[Equation 1]

where p is positive value satisfying 0≦p≦1.

FIG. 3illustrates a bilinear interpolation. The bilinear interpolation may indicate an interpolation to be performed in two-dimensions (2D).

As shown inFIG. 3, a value at a third point370may be interpolated using a value (for example, color information) at a first vertex310, a value at a second vertex320, a value at a third vertex330, and a value at a fourth vertex340, for example.

Specifically, the value at the third point370may be interpolated using Equation 2.
Interpolated value at a first point 350=value at the first vertex 310*(1−c)+value at the second vertex 320*c;[Equation 2]

Interpolated value at a second point360=value at the third vertex330*c+value at the fourth vertex340*(1−c);

Interpolated value at the third point370=interpolated value at the first point350*(1−d)+interpolated value at the second point360*d; and

FIG. 4illustrates a trilinear interpolation. The trilinear interpolation indicates an interpolation to be performed in three-dimensions (3D).

As shown inFIG. 4, a value at a point I may be interpolated using a value (for example, color information) at a first vertex P1and values at second to eighth vertices P2to P8.

Specifically, the value at the point I may be interpolated using Equation 3.
Interpolated value at a first pointC1=value at the second vertexP2*(1−e)+value at the third vertexP3*e;[Equation 3]
Interpolated value at a second point C2=value at the first vertex P1*(1−e)+value at the fourth vertexP4*e;[Equation 3]

Interpolated value at a third point C3=value at the sixth vertex P6*(1−e)+value at the seventh vertex P7*e;

Interpolated value at a fourth point C4=value at the fifth vertex P5*(1−e)+value at the eighth vertex P8*e;

Interpolated value at a fifth point C5=interpolated value at the first point C1*f+interpolated value at the second point C2*(1−f);

Interpolated value at a sixth point C6=interpolated value at the third point C3*f+interpolated value at the fourth point C4*(1−f);

Interpolated value at the point I=interpolated value at the fifth point C5*g+interpolated value at the sixth point C6*(1−g); and

An improved interpolation method (hereinafter, referred to as pyralinear interpolation method) as compared with the interpolation techniques illustrated inFIGS. 2 to 4will be disclosed below.

FIG. 5illustrates an image interpolation system according to an embodiment of the present invention. The image interpolation system includes, for example, a normalization unit510, a base-plane searching unit520, a storage unit530, an operation unit540, and an interpolation unit550.

The normalization unit510may normalize location information on vertices input through an input terminal IN1. The location information may be 3D information and may include x-axis, y-axis, and z-axis information, for example.

Hereinafter, for convenience of description, it may be assumed that the vertices input though the input terminal IN1correspond to vertices of a plurality of cubes, and a cube including the point1, as shown inFIG. 4, of which image information to be interpolated is among the plurality of cubes. In addition, color information, in which white is represented by 0, and gray is represented by one of 1 to 254, may be an example of the image information described for one or more embodiments of the present invention.

The base-plane searching unit520may search for the nearest plane to the point1, for example, of which the image information is to be interpolated among six planes S1to S6which constitute the cube. Hereinafter, for convenience of description, it may be assumed that the nearest plane is the plane S3.

The storage unit530may store image information about the vertices input through the input terminal IN1.

According to a first embodiment of the present invention, the operation unit540may read image information of one or more vertices, for example, P2, P3, P6, and P7of the plane S6facing the plane S3, found by the base-plane searching unit520stored in the storage unit530.

In addition, the operation unit540may compute information on an oppositely facing plane, e.g., S6, using the read image information (the read image information of the vertices P2, P3, P6, and P7). The information on the facing plane may indicate any image information that may be computed using the image information of the vertices of the plane facing the plane found by the base-plane searching unit520. For example, the operation unit540may average the read image information (the read image information of the vertices P2, P3, P6, and P7), thereby computing the information about the facing plane.

Alternatively, according to a second embodiment of the present invention, the operation unit540may read the image information of the one or more vertices P1, P4, P5, and P8of the plane S3found by the base-plane searching unit520stored in the storage unit530.

In addition, the operation unit540may estimate the image information of the one or more vertices P2, P3, P6, and P7of the plane S6facing the plane found by the base-plane searching unit520using the read image information (e.g., the read image information of the vertices P2, P3, P6, and P7). For example, the operation unit540may estimate that the image information of the one or more vertices P2, P3, P6, and P7of the facing plane S6is an average of the read image information (e.g., the read image information of the vertices P1, P4, P5, and P8). Furthermore, the operation unit540may compute the information about the facing plane using the estimated image information (e.g., the estimated image information of the vertices P2, P3, P6, and P7). For example, the operation unit540may compute the information about the facing plane by averaging the estimated image information (e.g., the estimated image information of the vertices P2, P3, P6, and P7). However, as exemplified above, when the operation unit540estimates that the pieces of the image information of the one or more vertices P2, P3, P6, and P7of the facing plane S6are the same, the operation unit540may determine that one piece of the image information among the pieces of the estimated image information (e.g., the pieces of the estimated image information of the one or more vertices P2, P3, P6, and P7) is the information on the facing plane.

According to the first embodiment of the present invention, the interpolation unit550may read the image information of one or more vertices P1, P4, P5, and P8of the plane S3found by the base-plane searching unit520stored in the storage unit530. On the other hand, according to the second embodiment of the present invention, the interpolation unit550may receive the read image information (the read image information of the vertices P1, P4, P5, and P8) from the operation unit540.

The interpolation unit550may interpolate the image information of the point I using the read image information (the read image information of the vertices P1, P4, P5, and P8) and the information on the facing plane computed, for example, by the operation unit540.

According to the first embodiment, the image information that is to be read from the storage unit530may be the image information of the vertices P1, P4, P5, and P8of the plane S3and the image information of the vertices P2, P3, P6, and P7of the plane S6. On the contrary, according to a second embodiment, the image information of the vertices P2, P3, P6, and P7of the plane S6need not be read from the storage unit530. Therefore, in the second embodiment, the frequency of communication with the storage unit530may be remarkably reduced.

FIG. 6illustrates the base-plane searching unit520shown inFIG. 5according to an embodiment (520A) of the present invention. The searching unit520may include, for example, a first comparator610, a subtracter620, a mirroring information generator630, a second comparator640, a mirroring checking unit650, and a base-plane determination unit660.

The first comparator610may compare each component of the coordinates (e, g, f) of the point I of which the image information is to be interpolated using a reference value, e.g., 0.5. Since location information of all the vertices may be normalized by the normalization unit510, each component of the coordinates (e.g. f) of the point I may range from 0 to 1.

As described inFIG. 4, e indicates a distance between the point I and the plane S1, g indicates a distance between the point I and the plane S2, and f indicates a distance between the point I and the plane S3.

That is, when the coordinate (e) of the x-axis component of the point I is equal to or less than 0.5, the point I is closer to the plane S1than to the plane S4. When the coordinate (g) of the y-axis component of the point I is equal to or less than 0.5, the point I is closer to the plane S2than to the plane S5. When the coordinate (f) of the z-axis component of the point I is equal to or less than 0.5, the point I is closer to the plane S3than to the plane S6. Hereinafter, for convenience of description and as an example, it may be assumed that (e.g. f)=(0.4, 0.7, 0.2).

Specifically, when it is determined by the first comparator610that the coordinate (e) of the x-axis component of the point I is equal to or less than 0.5, the first comparator610may determine that the point I is closer to the plane S1than to the plane S4and output the coordinate (0.4) to the second comparator640.

Similarly, when it is determined by the first comparator610that the coordinate (g) of the y-axis component of the point I is equal to or less than 0.5, the first comparator610may determine that the point I is closer to the plane S5than to the plane S2and output the coordinate (0.7) to the subtracter620.

Similarly, when it is determined by the first comparator610that the coordinate (f) of the z-axis component of the point I is equal to or less than 0.5, the first comparator610may determine that the point I is closer to the plane S3than to the plane S6and output the coordinate (0.2) to the second comparator640.

Finally, the first comparator610may reduce candidates of the nearest plane to the point I from six planes S1, S2, S3, S4, S5, and S6to three planes S1, S5, and S3.

On the other hand, the subtracter620, the mirroring information generator630, the second comparator640, the mirroring checking unit650, and the base-plane searching unit660may search for the nearest plane to the point I among the three planes S1, S5, and S3.

The subtracter620may operate only when it is determined by the first comparator610that the coordinates are greater than 0.5. Specifically, when it is determined by the first comparator610that the coordinates are greater than 0.5 (0.7>0.5), the subtracter620may change the coordinate (0.7) of the point I to the result (0.3)′ by subtracting the coordinate (0.7) of the point I from 1 and may output the changed coordinate (0.3)′ to the second comparator640.

The mirroring information generator630may generate mirroring information according to instructions of the first comparator610and the subtracter620, for example. In an embodiment, the mirroring information may be constructed using three bits. For example, when it is determined by the first comparator610that the coordinates are equal to or less than 0.5, the mirroring information generator630may generate a bit that represents 0, according to the instruction of the first comparator610. In addition, when it is determined by the first comparator610that the coordinates are greater than 0.5, and the subtracter620operates, the mirroring generator630may generate a bit that represents 1. Under the aforementioned assumption, the mirroring information generator630may generate the mirroring information that represents 010.

The second comparator640may compare coordinates (0.4, 0.2)′ received from the first comparator610with the coordinate (0.3)′ received from the subtracter620. Accordingly, the second comparator640may search for the least value among the coordinates (0.4, 0.2)′ received from the first comparator610and the coordinate (0.3)′ received from the subtracter620and may output the found coordinate (0.2) to the mirroring checking unit650.

The mirroring checking unit650may check whether the mirroring is to be performed or not by analyzing the mirroring information (last ‘0’ of 010) related to the axis component (z-axis component) of the coordinate received from the second comparator640. When the mirroring bit is 0, mirroring may not need to be performed. On the contrary, when the mirroring bit is 1, mirroring may need to be performed.

When it is checked that the mirroring need not be performed, the base-plane determination unit660may determine that the plane S3to be the nearest plane to the point I according to the coordinate (0.2) received from the second comparator640may be the plane that is to be searched for by the base-plane searching unit510.

When it is determined that the mirroring needs to be performed, the base-plane determination unit660may determine that the plane S6(that is, the mirrored plane) facing the plane S3to be the nearest plane to the point I according to the coordinate (0.2) received from the second comparator640is the plane that is to be searched for by the base-plane searching unit510, which differs from the aforementioned assumption.

FIG. 7illustrates a storage unit530, for example as shown inFIG. 5.FIG. 8illustrates an interpolation unit550, for example as shown inFIG. 5. Specifically,FIG. 8illustratesFIG. 4, such that the plane S3found by the base-plane searching unit520may be the base-plane of the lattice.

The storage unit530may store the image information and an operation rule of the interpolation unit550in a form of a look-up table (LUT) as shown inFIG. 7.

When the plane found by the base-plane searching unit520is the plane S3, the operation rule stored in the storage unit530may be that interpolations between the vertices P1and P4, or P5and P8located in parallel with the x-axis may be performed, and an interpolation between the points C2and C4located in parallel with the y-axis may be performed, and an interpolation between the points C8and A located in parallel with the z-axis may be performed. It may need to be determined which interpolation is performed first of the interpolation between the vertices P1and P4and the interpolation between the vertices P5and P8. According to the operation rule stored in the storage unit530, the interpolation between the vertices P1and P4may be performed first. In addition, according to the operation rule stored in the storage unit530, the information on the facing plane may be an average of the pieces of the image information of the vertices P2, P3, P6, and P7.

The interpolation unit550may read the stored operation rule and performs interpolation according to the read operation rule.

As described above, the interpolation unit550may interpolate the image information of the point I using the image information of the one or more vertices P1, P4, P5, and P8of the plane S3found by the base-plane searching unit520, and the information on the facing plane computed by the operation unit540.

Finally, the interpolation unit550may interpolate the image information of the point I using Equation 4.
Interpolated image information of the second pointC2=image information of the first vertexP1*(1−e)+image information of the fourth vertexP4*e;[Equation 4]

Interpolated image information of the fourth point C4=image information of the fifth vertex P5*(1−e)+image information of the eighth vertex P8*e;

Interpolated image information of the eighth point C8=interpolated image information of the second vertex P2*g+interpolated image information of the fourth point C4*(1−g); and

Interpolated image information of the point I=interpolated image information of the eighth point C8*(1−f)+information on the facing plane*f.

Referring to Equation 4, the information on the facing plane may be treated as image information of an intersection point A between an extension line connecting the eighth point C8and the point I and the plane S6.

FIG. 9illustrates an image interpolation method, according to an embodiment of the present invention.

The planes surrounding the point may be searched for the plane nearest to the point at which the image information is to be interpolated, for example by the base-plane searching unit520, in operation910.

Information about the facing plane may be obtained, e.g., by the operation unit540, using the image information of the one or more vertices of the plane facing the plane found in operation910, in operation920.

The image information of the point using the image information of the one or more vertices of the plane found in operation910may be interpolated e.g., using the interpolation unit550and the information about the facing plane obtained in operation920, in operation930.

In addition to the above described embodiments, embodiments of the present invention may also be implemented through computer readable code/instructions in/on a medium, e.g., a computer readable medium, to control at least one processing element to implement any above described embodiment. The medium can correspond to any medium/media permitting the storing and/or transmission of the computer readable code.

The computer readable code may be recorded/transferred on a medium in a variety of ways, with examples of the medium including recording media, such as magnetic storage media (e.g., ROM, floppy disks, hard disks, etc.) and optical recording media (e.g., CD-ROMs, or DVDs), and transmission media such as carrier waves, as well as through the Internet, for example. Thus, the medium may further be a signal, such as a resultant signal or bitstream, according to embodiments of the present invention. The media may also be a distributed network, so that the computer readable code is stored/transferred and executed in a distributed fashion. Still further, as only an example, the processing element could include a processor or a computer processor, and processing elements may be distributed and/or included in a single device.

As described above, the image interpolation method, medium and system according to embodiments of the present invention have an advantage of rapidly obtaining a reliable interpolated value. Specifically, in the image interpolation method according to an embodiment of the present invention, that is, in the pyralinear interpolation method, interpolation may be performed faster than, for example, in the trilinear interpolation method. More specifically, the linear interpolation may need to be performed four to eight times in order to perform the trilinear interpolation once, depending an an embodiment of the present invention. In addition, in the pyralinear interpolation according to the first embodiment of the present invention, because the read image information of the eight vertices is needed to perform the pyralinear interpolation once, and similarly the read image information of the eight vertices is needed to perform the trilinear interpolation once, though in the pyralinear interpolation, remarkably small numbers of linear interpolations are performed, the value interpolated by the pyralinear interpolation may approach the value interpolated by the trilinear interpolation. On the other hand, since the base-plane searching unit520, which in one or more embodiments, is one of the important components of the image interpolation system, may be embodied by a low priced operation unit such as a comparator instead of a high priced operation unit such as a multiplier, and thus the image interpolation system according to embodiments of the present invention may be embodied at low cost.