Abstract
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.