## 5 Image Compression
First of all, background subtraction would not be useful, not only because of the sunlight changes, but also because the birds fly in and out frequently. Second, the biologist requested for higher resolution images (200 \(\times\) 200) than 128 \(\times\) 128 for their purposes, leaving us no memory space for running any kind of algorithm that required additional memory. Thus, we needed to develop a new image compression algorithm for our bird nest deployment. For this reason, we have investigated two types of run-length encoding (RLE) on the Cyclops. One was the simple run-length encoding, where everything is encoded in to [length][byte], and another was the 'PackBits' algorithm. PackBits is a fast, simple loss-less compression scheme for run-length encoding of data originally developed by Apple. These schemes were chosen because the encoding operation at the mote-end is simple and can be done on-the-fly without requiring a full image size buffer. We modified these two algorithms into lossy algorithms, so that a sequence of values within a threshold  
Figure 1: A “background subtraction-based object detection algorithm”example. range consists of a 'run' (in our image data, each byte represents a gray scale value ranging between zero and 255). In other words, a 'run' consists of values where the difference between the minimum and the maximum values within that run are less than the threshold. For example, if the threshold is 10 and the original image data are {1, 2, 1, 3, 2, 3, 2, 2, 15, 20, 15, 20, 100, 110, 105, 105, 100, 110}, then this image is compressed into {[8][2],[4][18],[6][105]} and will later be decompressed to image data {2, 2, 2, 2, 2, 2, 2, 2, 18, 18, 18, 105, 105, 105, 105, 105, 105}. The threshold value trades-off image quality for increased compression, and setting it to zero is equivalent to using the original loss-less algorithm. Figure 2 depicts examples from our investigation where you can see that we can achieve a significant data reduction if we can tolerate some lossiness in the images after decompressing the lossy-encoded data. In general, PackBits has better compression performance than simple RLE. One downside of PackBits is that it requires 100% reliable data delivery; if any packet is lost, we cannot decompress it, whereas we can always decompress the simple RLE as long as the fragment size is in even numbers. This is not a problem for us, since Tenet has a reliable transport protocol, but it can cause errors if you are testing it without reliability. One concern for using reliable communication is that it may cause extra retransmissions and, hence, energy consumption. If the images with packet losses are readable and energy overhead is considerable, simple RLE might be a better choice. To validate this, we have conducted an experiment to see the image quality of simple RLE with some packet losses. Figure 3 shows the result of this experiment. The average packet delivery ratio of our deployment was around 82%, with the worst node having 50% packet reception rate (PRR). As you can see from the figure, images with packet losses are not of good quality; our biologist greatly preferred less frequent 100% images over more frequent 80% images. Furthermore, an image with 50% packet loss is not  
Figure 2: Lossy version of the “simple run-length encoding” (RLE) and “PackBits” algorithms with a threshold example. readable. Lastly, the average PRR of 82% translates into ETXof around 1.21, which means that the extra energy consumed by retransmissions are around 21% on average. Our decision was that it is worth spending 21% extra energy to collect 100% images rather than compromising the image quality. Another reason that the biologists wanted high quality images was to perform offline image processing at the backend to automatically detect the presence/absence of birds and also to count the number of eggs from the 100,000+ images that we have collected. This is a separate line of image processing research, which required complete images.