Wavelet Transform Data Compression with an Error Level Guarantee for Z-Map Models
Nobuyuki Umezu*,†, Kazuki Asai**, and Masatomo Inui*
4-12-1 Nakanarusawa, Hitachi, Ibaraki 316-8511, Japan
6-27-18 Minami Oi, Shinagawa-ku, Tokyo 140-3748, Japan
This paper proposes an algorithm to compress CAD models in a grid-based Z-map representation while keeping the compression artifacts within a specified value (the maximum difference allowed by the user). A wavelet transform is used for decomposing the input shape into lower and higher frequency patterns. A significant reduction in the data size can be achieved by deleting higher frequency components. We employ a tree structure called the error range (ER) tree to manage error occurrences and determine where to prune branches without increasing the resulting errors in the data compression. The widely used reversible compression method, gzip, is then used to obtain the final compressed model data output. We conducted a series of experiments with 12 sample shape models on a 512 × 512 grid. With a maximum error of 10 μm (a typical value specified for NC milling), the proposed method reduces the data by 90.9% on average and the computational cost of 19 ms is extremely low. The proposed method can be extended to larger CAD models in real applications.
-  W. P. Wang and K. K. Wang, “Real-time Verification of Multiaxis NC Programs with Raster Graphics,” Proc. of IEEE Conference on Robotics and Automation, pp. 166–171, 1986.
-  M. Inui and R. Kakio, “Fast Visualization of NC Milling Result Using Graphics Acceleration Hardware,” Proc. IEEE Conference on Robotics and Automation, pp. 3089–3094, 2000.
-  M. Inui and R. Ishizuka, “Data Compression Method of Z-MAP Model Representing Milling Result Shape,” International Symposium on Flexible Automation (ISFA), pp. 343–348, 2006.
-  Autodesk, System Requirements for AutoCAD 2016, https:// knowledge.autodesk.com/support/autocad/troubleshooting/caas/ sfdcarticles/sfdcarticles/System-requirements-for-AutoCAD-2016. html [accessed September 7, 2015]
-  SOLIDWORKS, Hardware & System Requirements, https://www. solidworks.com/sw/support/SystemRequirements.html [accessed September 7, 2015]
-  G. K. Wallace: “The JPEG still Picture Compression Standard,” IEEE Trans. Consumer Electronics, Vol.38, No.2, pp. 18–34, 2002.
-  D. Taubman and M. L. Marcellin, “JPEG2000: standard for interactive imaging,” Proc. of IEEE, Vol.90, No.8, pp. 1336–1357, 2002.
-  C. E. Jacobs, A. Finkelstein, and D. H. Salesin, “Fast multiresolution image querying,” Proc. ACM Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp. 277–286, 1995.
-  T. Chen et al., “Sketch2Photo: internet image montage,” Proc. of ACM SIGGRAPH Asia, Art., Vol.124, 2009.
-  N. Kashyap and G. R. SINHA, “Image Watermarking Using 3-Level Discrete Wavelet Transform (DWT),” International Journal of Modern Education and Computer Science, Vol.4, pp. 50–56, 2012.
-  Y. Jeffrey, S. Vitter, and M. Wang, “Wavelet-based histograms for selectivity estimation,” Proc. of ACM International Conference on Management of Data (SIGMOD), pp. 448–459, 1998.
-  G. Minos and P. B. Gibbons, “Wavelet Synopses with Error Guarantees,” Proceedings of the ACM SIGMOD, pp. 476-487, Vol.22, 2002.
-  M. Garofalakis and A. Kumar, “Deterministic Wavelet Thresholding for Maximum-Error Metrics,” Proc. of Symposium on Principles of Database Systems (PODS), pp. 166–176, 2004.
-  K. Panagiotis and N. Mamoulis, “One-Pass Wavelet Synopses for Maximum-Error Metrics,” Proc. of International Conference on Very Large Data Bases (VLDB), pp. 421–432, 2005.
-  M. Adler, “zlib Home Site,” http://www.zlib.net/ [accessed September 7, 2015]
-  T. Van Hook, “Real-time shaded NC milling display,” Proc. of ACM Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp. 15–20, 1986.
-  J. Shade, S. Gortler, and L. He, R. Szeliski, “Layered depth images,” Proc. ACM Conference on Computer Graphics and Interactive Techniques (SIGGRAPH), pp. 231–242, 1998.
-  M. Inui and N. Umezu, “GPU acceleration of 5-axis milling simulation in triple dexel representation,” Proc of International Symposium on Flexible Automation (ISFA), 2010.
-  A. Sullivan, H. Erdim, R. N. Perry, and S. F. Frisken, “High accuracy NC milling simulation using composite adaptively sampled distance fields,” Computer Aided Design, Vol.44, No.6, pp. 522-536, 2012.
-  M. Inui, N. Umezu, and Y. Shinozuka, “A Comparison of Two GPU Accelerated Geometric Milling Simulation Methods,” Transactions of ISCIE (the Institute of Systems, Control and Information Engineers), Vol. 26, No.3, pp. 95–102, 2013.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 International License.