Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1999-09-18
2003-06-10
Do, Anh Hong (Department: 2624)
Image analysis
Image compression or coding
Adaptive coding
C382S232000, C382S243000, C358S426010, C358S001150
Reexamination Certificate
active
06577769
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to the fields of data compression, and more particularly, to compressing 3D multimedia transfers over a network connection.
BACKGROUND
3D multimedia includes video conferencing, interactive games, web-page content, audio/visual (A/V)recordings, to name but a few (hereafter collectively “A/V data”). A/V data requires significant storage space, as well as substantial bandwidth to transmit the data over a network. Since most data recipients do not have sufficient bandwidth to receive the A/V data in its original form, A/V data has traditionally been retrieved over a local high-speed bus or specialized high-speed data links.
For example, consider computerized games. Games include simple single-user simulators for pinball, cards, gambling, fighting, etc., or more complex multiple-player turn-taking games where each player competed against the game and ultimately compared scores. Well-known high-tech gaming systems include the Nintendo® and Sony PlayStation® gaming systems. These and other games use geometry to describe two and three-dimensional objects within gaming models. In particular, complex object surfaces are usually represented by a combination of one or more basic object shapes, such as splines, non-uniform rational splines (NURBs), texture maps, and (monohedral) triangle tesselation. Typically, an arbitrary object is defined by triangle tesselation, each triangle having associated spatial coordinate tuples X, Y (and perhaps Z), color, normal, and other attributes. This information, when multiplied by hundreds or thousands of polygons in moderately complex objects, amounts data that must be retrieved from dedicated graphics systems and local storage of graphics data. The data transfer requirements prohibit play against remote players. Although some games have been designed to use a modem to directly call a remote player and establish a game, this solution was often clumsy, slow, and inconsistent; rich content transfer was infeasible.
Or, consider video conferencing applications. As with games, these applications concern transferring large volumes of data. However, these applications must transfer the data to remote locations (e.g., conference participants). Therefore, they have required high-speed data links, e.g., at a minimum, a 128 K-bit bonded ISDN connection to the remote participant, or more preferably, a T1 or faster frame-relay connection. Unfortunately, these speedy connection backbones are not generally available to users, and require complex technical support to maintain an active link. Conferencing also shares the modem-game limitation of requiring direct user-to-user connections.
With the recent advent of ubiquitous low-cost Internet connections, it has become a relatively straightforward matter to form a network communication link between multiple remote participants. This has spurred interest in using these generally available links to transfer A/V data. Unfortunately, due to the cost and technical complexity of maintaining ISDN, Frame Relay, and other high-speed links, Internet connections are commonly relatively slow modem-based connections. Since modem connections only generally realize an average modem bit rate of 14-40 KBits per second, these connections are not able to transfer, in reasonable time, rich game content, conferencing data, or other A/V data. This problem is exacerbated with each additional remote participant, since A/V data must now be distributed to multiple recipients—further consuming bandwidth resources.
In an effort to reduce bandwidth constraints, and take advantage of the easily-available slow networking connections, there have been efforts to compress A/V data. For example, data and geometry compression has previously been used to reduce information content in 2D and 3D models. Previous compression attempts include image compression (e.g., JPEG), defining objects with shared features (e.g., shared edges), small texture maps for large areas, etc. Examples of some of these and other techniques can be found in U.S. Pat. No. 5,740,409 which teaches a 3D graphics accelerator for compressed geometry, and U.S. Pat. Nos. 5,793,371, 5,867,167, and 5,870,094 which teach various methods for more-efficiently encoding 3D models. These compression techniques are readily applicable to A/V game data (which use models), as well as other A/V data representing data in a compatible compressible format, such as Moving Picture Experts Group (MPEG) digital video encoding.
In addition to geometry compression, general purpose data compression procedures has also been applied to A/V data. Such techniques include Huffman encoding (See Huffman, “A Method For Construction Of Minimum Redundancy Codes”, Proceedings IRE, 40, 10 pages 1098-1100 (September 1952)), Tunstall encoding (See Tunstall Doctoral thesis, “Synthesis of Noiseless Compression Codes”, Georgia Institute of Technology (September 1967)), and Lempel-Ziv encoding (See “A Universal Algorithm For Sequential Data Compression”, IEEE Transactions on Information Theory, IT-23, 3, pages 337-343 (May, 1977)), and run-length encoding of model data (see, e.g., U.S. Pat. No. 3,656,178). These general purpose compression techniques are applicable to all data formats.
Unfortunately, even after application of general purpose and geometric compression, there still remains a significant amount of information that needs to be transferred before games, conferencing, viewers of 3D multimedia, interactive 3D chat rooms, and other applications of A/V data appear to operate as if they are retrieving their data from local storage or high-speed links. Thus, some further data reduction is needed.
SUMMARY
A computing-device implemented method for compressing data, where such devices include a computer, personal digital assistant (PDA), home appliance, and the like. A distance is determined between a reference point in a model, and a bounding box for a model object defined according to a data collection, each element within the collection having a first data size. A data reduction factor is selected based, at least in part, on the distance. The data collection is compressed according to the distance by mapping each data of the first data size to data having a second data size smaller than the first data size. Other compression methods and apparatus are disclosed.
REFERENCES:
patent: 3656178 (1972-04-01), De Maine et al.
patent: 5155772 (1992-10-01), Brandman et al.
patent: 5367620 (1994-11-01), Ito et al.
patent: 5388209 (1995-02-01), Akagiri
patent: 5552898 (1996-09-01), Deschuytere
patent: 5583977 (1996-12-01), Seidl
patent: 5638498 (1997-06-01), Tyler et al.
patent: 5710916 (1998-01-01), Barbara et al.
patent: 5740409 (1998-04-01), Deering
patent: 5751809 (1998-05-01), Davis et al.
patent: 5790979 (1998-08-01), Liedtke
patent: 5793371 (1998-08-01), Deering
patent: 5852710 (1998-12-01), Shiohara et al.
patent: 5867167 (1999-02-01), Deering
patent: 5870094 (1999-02-01), Deering
patent: 5930813 (1999-07-01), Padgett et al.
patent: 5977979 (1999-11-01), Clough et al.
patent: 6246422 (2001-06-01), Emberling et al.
patent: 6249604 (2001-06-01), Huttenlocher et al.
patent: 6304940 (2001-10-01), Beardsley
patent: 6313838 (2001-11-01), Deering
Searfoss, G.: “Bounding Box Data Compression”, Dr. Bob's Journal of Software Tools, Apr. 1990, USA, vol. 15, No. 4, pp. 56-64, 108, XP000981336 ISSN: 1044-789X p. 58, paragraph 1-paragraph 10.
Deering, M.: “Geometry Compression” Computer Graphics Proceedings (Siggraph), US, New York, IEEE, Aug. 6, 1995, pp. 13-20, XP000546211, ISBN: 0-89791-704-4 p. 15, left-hand column, paragraph 7—right-hand column, paragraph.
Naphatali Rishe, “Interval-based aproach to lexicographic representation and compression of numeric data”, Data and Knowledge Engineering, 8, 4(1992), pp. 339-351., Copyright 1992.
Kenyon Jeremy A.
Smith Peter D.
Do Anh Hong
Schwabe Williamson & Wyatt P.C.
WildTangent, Inc.
LandOfFree
Data compression through adaptive data size reduction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression through adaptive data size reduction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression through adaptive data size reduction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3108514