## 2 Partial Differential Equations in Image Compression
### Binary Tree Structure  
During the triangulation process, a binary tree structure is formed in which each triangle is represented by a node, while the triangles that are no longer divided are represented by a leaf. A triangle is divided into two subordinate triangles. To save this tree structure, a preorder traversal is performed and a 1 is stored for each node and a 0 for each leaf. Additional space saving is achieved by storing two numbers _minimum tree depth_ and _maximum tree depth_. The minimum tree depth is the tree depth up to which all nodes are dividing (all values are 1 s), and the maximum tree depth is the depth above which nodes are not divided any more (all values are 0 s). The process of creating a binary tree structure is shown in Figure 2. In Figure 2a, the process is shown for a square image and, in Figure 2b, the resulting binary tree is generated. First, the image is divided by its main diagonal, then the process is repeated for the newly created triangles. To compress the grey values in all vertices, a zigzag traversal of the sparse image is performed and stored in the grey value stream. The pseudocode can be seen in the following text below:  
Figure 1: BTTC process. (**a**) Original image. (**b**) Triangle division process. (**c**) Reconstruction of inner values by interpolation. (**d**) Repeated triangle division process. Main algorithm: Image is grayscale image:  
Step 1. roottriangle = new Triangle(0,0,Image.width,Image.height)  
Step 2. Btree root = new Node(roottriangle,\")  
Step 3. CreateChildNodes(root)  
Step 4. EncodeImage(root)  
Recursive procedure CreateChildNodes(node):  
Step 1. Let t = node.triangle  
Step 2. midx = t.x + t.width/2, midy = t.y + t.width/2  
Step 3. topleft = new Triangle(t.x,t.y,midx-t.x,midy-y)  
Step 4. botright = new Triangle(midx,midy,t.x+t.width-midx,y+t.height+midy)  
Step 5. tlaverage = ComputeAverageColorValue(topleft)  
Step 6. braverage = ComputeAverageColorValue(botright)  
Step 7. If tlaverag\(\
eq\)braverage then  
node.left = new Node(tltriangle,node.code+'0')  
node.right = new Node(brtriangle,node.code+'1')  
CreateChildNodes(node.left)  
CreateChildNodes(node.right)  
Procedure EncodeImage(node):  
Step 1. If node=NULL return  
Step 2. Print node.code  
Step 3. EncodeImage(node.left)  
Step 4. EncodeImage(node.right)  
Finally, due to the high similarity of the tree structure, the data stream is compressed using Huffman coding [40]. The final compressed file format consists of the following:  
* Image height and width (4 byte);
* Minimum and maximum binary tree depth (2 byte);
* Binary tree structure in binary form (1 bit for every node);
* Huffman coded gray values. **-** First value of gray value in stream (1 byte);  
**-** Minimum and maximum Huffman binary tree depth (2 byte);  
**-** Huffman binary tree binary characters (1 bit for every node);  
**-** Gray values coded with Huffman coding. We have further improved this encoding by a lossy requantization step that reduces the number of grey values in the original image from 256 to 64. Figure 2: Process of creating the B-tree structure. (**a**) Process of dividing the triangles. (**b**) Corresponding binary tree structure. Binary Tree Decoding and Interpolation  
Decompression of the encoded image is performed in two steps. In the first step, a reconstruction of the mask image is performed, and the stored grey values are placed in appropriate locations so that the sparse image can be created. For the reconstruction of the mask vertices, a tree is created in the same order as it was saved. The second step is the image interpolation, where the vertex mask is used as the interpolation mask. In their BTTC scheme, [PERSON] et al. [23] used linear interpolation. In this study, homogeneous diffusion, biharmonic and triharmonic smoothing, absolute monotone Lipschitz extension (AMLE), Charbonnier diffusion, and edge-enhancing diffusion are tested. To check the quality of the interpolation methods, two methods of quantitative error analysis were used.