電腦多媒體影像、網路的蓬勃發展，使得影像的應用愈來愈頻繁。要如何讓影像可以壓縮的愈小，使其可以在有限的儲存空間存入更多的影像，使其可以在網路上更快地傳送，就成為了一個相當值得探討與研究的焦點。 小波影像壓縮是現在流行的一種影像壓縮技術，它透過將圖形轉換成小波係數並利用係數間的性質來達到壓縮的目的。其中一個關鍵的步驟，是如何將一個稀疏的01矩陣編碼成一串較短的01序列，從群試的角度出發這可以視為一個從矩陣中找出少數1的位置的問題，而群試正是用來有效率地找出藏在相對大量的目標物裡的少數特定物的一種方法。於是Hong, E.S. 與 Ladner, R.E發展了一套基於群式的編碼方法-GTW。本篇將會介紹並定義GTW的數學架構，並從群試理論的角度去探討GTW的另一種演算法。 The development of Internet and multimedia makes the usage of image are important issue. How to store more images in limited memory space and how to transmit images quickly on Internet becomes important topics. Image compression is minimizing the size in bytes of a graphics file without degrading the quality of the image to an unacceptable level. The reduction in file size allows more images to be stored in a given amount of memory space. It also reduces the time required for images to be sent over the Internet or downloaded from Web pages. Therefore, in order to achieve these goals, image compression plays an important role.
Wavelet image compression is a popular image compression technology. It turns an image into wavelet coefficients and use the correlation between wavelet coefficients to achieve the purpose of compression. One of the key issue is how to encode a “sparse” binary matrix, as short as possible, into a series of binary bits which contains the information of the original matrix. This can be regarded as a problem of identifying the 1's from the matrix.
Group testing is a subject that deals with identifying a small number of targets from a large number of objects efficiently. The basic idea is the group test. Given a subset $S$ of $M$, a group test on $S$ has two outcomes: “positive” means there exists at least one target in $S$; “negative” means there is no target in $S$. For a group test on a subset $S$ which is large, we can instantly exclude a large amount of objects from targets if the outcome is negative. On the other hand, it will not take many tests to identify a target if the outcome is positive and the subset is small. Through clever choices of subsets we can identify the few targets from a large number of objects efficiently. Since there are only 2 outcomes in each group test, we can use 1 to represent positive to a group test and use 0 to represent negative respectively. Thus, a series of group tests can output a series of binary bits and this can be regarded as a coding method. Hong, E.S. and Ladner, R.E developed a coding method based on group testing called GTW which gives a framework of group testing for wavelet image compression.
In this thesis, we first introduce and define the mathematical framework of GTW. And then explore the improvement of GTW from the perspective of group testing.