In computer era, all information such as texts, signals, images, videos, sounds and so on are digitalized, encoded, stored, transmitted or broadcasted as numbers, or called “data.” The information may be represented in one of many different forms which can be processed by computers. The data of information are interpreted via mathematical transforms between different forms – computable or perceptible. Thus mathematics has been playing the most crucial role in the advance of information technology.
At QualVisual, we focus on innovating new mathematical concepts and methods for representing information data in more efficient ways. Our software products implement and demonstrate the new research achievements.
I. System compression theory
1. Recovers data sets from 25% or less samples in numerically or perceptually lossless manner;
2. Accelerates signal, image and video acquisition by 4 times faster, without loss of signal quality;
3. Realizes scalable coding, printing or display without data input in image and video transmission;
4. Extends basic concepts, knowledge and methodologies in linear algebra and signal processing.
A data set can be exactly recovered from 25% samples.
Since 2009, we proposed and built the new mathematical theory of system compression. It reveals and describes the "polymorphism" of systems of linear equations, which means a system of linear equations may mutate between different "states": complete, overcomplete or underdetermined. We discovered a variety of practical conditions and methods for realizing the mutations in real time. A complete system of linear equations can be completely reconstructed from its underdetermined subsystem. As a result, a data set can be exactly recovered from its subset. This mathematical discovery can be applied to significantly accelerating signal, image and video acquisition in many engineering applications, including medical imaging, remote sensing, wireless communication, satellite technology and so on. In addition, it also may fundamentally change the methodology of data compression. It may realize scalable coding in perceptually lossless quality without data input in audio, image and video compression technologies. Our software products Rapid and Savvy respectively demonstrate the miraculous performance of system compression theory in 2D image and 1D signal acquisitions.
Our system compression method makes revolutionary improvement as compared with compressed sensing theory. System compression fundamentally differs from compressed sensing in both mathematical rationale and technical performance. Compressed sensing relies on signal sparsity and convex optimization as core principles. The sufficiency of sparsity is measured in terms of coherence of an underdetermined system of linear equations. Besides, compressed sensing theory advocates random sampling models for generating the underdetermined system. It claims that its random sampling models produce optimal or nearly optimal results. In fact, convex optimization such as linear programming and orthogonal matching pursuit rely on very sophisticated, iterative computations which become very slow and unstable in high dimensional systems. Even worse, the mathematical conditions for compressed sensing impose excessively sparse representations on subject signals, which may severely deteriorate signal quality. For concrete evidence, click here to see the performance of two most representative products of compressed sensing by MIT and Rice University, in comparison with our system compression method which dispenses with both sparse representation and convex optimization. Hence it fundamentally improves both signal quality and computation speed. Moreover, system compression forbids random sampling in practice, because random sampling undermines the chance of complete system reconstruction. The high quality and high speed make system compression a truly applicable method in engineering practice. In objective effect, our system compression method undoubtedly nullifies compressed sensing theory with overwhelming superiority in technical performance.
colossal Big Data handleable data essence
System compression method can facilitate handling big data. The colossal volume of big data poses serious challenges to data analytics, storage and transmission. By our system compression method, big data can be distilled by extracting the data essence from big datasets in real time. The data essence preserves all the information of big data but occupies only one tenth or one hundredth of the volume of raw data. Apparently, diminished data volume can help to improve the velocity of data analytics, storage and transmission. More importantly, in many applications, the data distillation process may purify data ingredient. Purified data ingredient and diminished data volume can contribute together to significantly boost the veracity of data analytics. It facilitates gaining insights more accurately and more efficiently. The whole big dataset can be reconstructed from the data essence at any time. Our system compression method is suitable for a wide variety of big data.
II. New approach to time-frequency analysis
For more than one century, time-frequency analysis has been one fundamental methodology in information theory and signal processing engineering. In tradition, the time domain of a signal is divided into intervals at first. Interval by interval, local frequency spectra are computed and processed separately within the time intervals. In other words, the signals are analyzed and processed in the time-oriented approach. A major drawback of this approach is that it neglects the dependency between the signal contents within adjacent intervals. To overcome this drawback, we proposed a new, frequency-oriented approach to time-frequency analysis. After local frequency spectra are all computed, transform coefficients are rearranged into frequency bands. Signal analysis and processing occur within the frequency bands. By this way, the statistical dependency between signal data in adjacent time intervals can be conveniently exploited. The new method can help greatly to improve technical performance in many applications such as data compression, feature extraction and watermarking. Click here to see more details.
III. New mathematical transforms
Mathematical transforms such as discrete Fourier transform (DFT), wavelet and discrete cosine transform (DCT) have been playing important roles in the advance of sciences and technologies for centuries. Besides new mathematical theories and methods, we have proposed a variety of new mathematical transforms mainly including:
(1). Real-valued discrete Fourier transform (RDFT)
Fourier transform has been serving the human world for two centuries. The rapid advances of most modern sciences and technologies have benefited directly from this great work of Joseph Fourier. However, it actually suffers a serious drawback in practice. In engineering applications, most signals are real-valued signals to which the traditional complex-valued Fourier transform is a redundant transform, which means that half coefficients are sufficient to represent and reconstruct the original signal, because half Fourier coefficients are conjugate to and hence can be derived from another half. We proposed new, real-valued discrete Fourier transform (RDFT) which can eliminate the transform redundancy. RDFT coefficients may hold whole information for Fourier coefficients but only take half amount of data. Therefore, RDFT may double the efficiency of computing, storing and transmitting Fourier coefficients than traditional Fourier transform. Even better, RDFT matrix shares many good properties with Fourier matrix including orthogonality, symmetric structure and fast algorithms (butterfly FFT etc). In particular, RDFT is more suitable for system compression applications than existing transforms such as DFT, wavelet, DCT and so on.
(2). Lifting Hadamard transform
Hadamard transform has been adopted by international video coding standard H.264 (2003) and image coding standard JPEG XR (2009). For enhanced efficiency in both software and hardware implementation, we independently designed lifting steps for 4*4 and 8*8 Hadamard transform. The lifting steps make the transform eligible for lossless data compression.
(3). Strictly equiangular frames
Equiangular frames are well known to have minimal coherence which is desirable for sparse and l1-minimal signal representations. However, ordinary equiangular frames are not maximally robust which is also desirable. We discovered the existence of "strictly equiangular frames" which have both minimal coherence and maximal robustness. We further found a convenient method to build strictly equiangular frames from Hadamard matrices.
IV. New image/video compression methods
Image and video data compression is the core engine for the advance and ubiquity of multimedia technology. The advance of data compression technology has been heavily relying on the advance of mathematics, from designs of new mathematical transforms to new results of mathematical analysis. Based on our mathematical works, we innovated a series of novel algorithms and methods for image and video data compression technology, partly including:
(1). Highly efficient 2D scan pattern
In general, an image or video data compression system comprises three main procedures: transform (wavelet or DCT), quantization and entropy coding. Transform and quantization identify and eliminate the unessential or less essential data elements from the data set. Entropy coding engines scan the whole data set for essential data elements (nonzero transform coefficients) and record the scanning result, i.e., the values and locations of the essential data elements. Hence scan pattern plays an important role in determining compression performance.
In DCT-based compression systems such as JPEG (1989), MPEG (1991-98), H.264 (2003) and HEVC (2013), a famous 1D linear zigzag scan pattern is employed. It scans the DCT coefficients from low frequency to high frequency within a transform block. This scan pattern exploits the fact that most energy of 2D image signals concentrate at low frequencies in DCT domain.
Wavelet transform fulfills multiresolution analysis. Wavelet coefficients distribute in a pyramid of scale bands. There are three famous wavelet-based image coding algorithms: EZW (Shapiro, 1993), SPIHT (Said & Pearlman, 1996) and EBCOT of JPEG2000 (Taubman, 1999). EZW and SPIHT scan wavelet coefficients along the zerotree structure. This scan pattern exploits the interscale (or interband) dependency between wavelet coefficients. The actual scanning process is linearized into a 1D pattern in practice. EBCOT scans wavelet coefficients in a 1D one-by-one, column-by-column linear pattern within a code block. It exploits the intrascale (or intraband) dependency between wavelet coefficients. However, the fact is that most energy of 2D image signals 2-dimentionally distributes around edge areas in wavelet domain. Therefore, 1D scan patterns inevitably cause loss of coding efficiency.
We proposed a highly efficient 2D scan pattern for wavelet-based image and video compression systems. It exploits both interscale and intrascale dependency between wavelet coefficients. In addition, the whole scanning process is guided by a separately encoded value map which signifies the locations of essential data elements or nonzero wavelet coefficients. The locations of significant data are reached in a 2D quadtree structure. Besides enhanced coding efficiency, our method offers dramatically reduced algorithmic and computational complexity. Our software product Lucid demonstrates the high performance of our image coding method.
(2). Bandwise rearrangement method
We proposed bandwise rearrangement technique for implementing time-frequency analysis in frequency-oriented approach. After transform in all time intervals, the coefficients at the same frequency are rearranged into one frequency band. The dependency between adjacent coefficients inside a frequency band reflects the dependency between signal contents in adjacent time intervals. The rearrangement provides a convenient platform for exploiting the intraband dependency between local frequency spectra of adjacent intervals. Click here to see more details, including the coefficient distribution before and after bandwise rearrangement.