这是一个的C++PTree图像压缩作业作业
Goals and Overview
In this PA (Programming Assignment) you will:

learn about representing images using a binary tree
learn to design more complex recursive algorithms
learn about a possible method of image compression using space-partitioning trees

Part 1: The PTree Class
A PTree is a binary tree whose nodes represent rectangular regions of a PNG image. The root represents the
entire image. The two children (referred to as A and B), of any node nd represent two equal or roughly equal
horizontal or vertical partitions of nd’s image region. Every node also contains:

a pixel representing the average colour of the pixels in its rectangular region
the upper-left image coordinates of its rectangular region
the width of its rectangular region in pixels, and
the height of its rectangular region in pixels
Building a PTree

The contructor of the PTree receives a PNG image of non-zero dimensions.
The region for each node is split as equally as possible, and symmetrically, into two smaller regions along the
longer of the two dimensions of the node being split. See the documentation in ptree.h for details about how to
determine the split axis and how to determine the dimensions and coordinates of the split pieces. A freshly
constructed PTree will have a leaf node corresponding to each individual pixel of the original image.
For example, a 5×3 image will be progressively split into the regions shown in the image below:
which has the corresponding tree structure below:
Note that due to required symmetry of splitting, every node in the tree has exactly 0, or 2 children (i.e. full); there
will never be a node with only one child.
To complete this part of the assignment, you should complete (or modify) the following functions:
In class PTree:
PTree(PNG& imIn)
PTree(const PTree& other)
PTree& operator=(const PTree& other)
~PTree()
void Clear()
void Copy(const PTree& other)
PNG Render() const
int Size() const
int NumLeaves() const
Node* BuildNode(PNG& im, pair ul, unsigned int w,
unsigned int h)
void FlipHorizontal()
void FlipVertical()
Many of the functions above will require private recursive helpers. It is up to you to add the declarations into
ptree-private.h, giving them appropriate signatures, and implementing them in ptree.cpp.
Advice: The constructor (which will use BuildNode) is critical for all of the other tree functionality. It is
recommended to focus your efforts into first correctly implementing BuildNode and Render which are used in
most of the testing functions.
Part 2: Image compression using PTrees
As a result of the hierarchical structure of the tree, along with each node storing the average colour of its
rectangular region, we can trim away portions of the tree representing areas without fine pixel-level detail. This is
achieved by the Prune function, which receives a tolerance parameter. This function attempts, starting near the
top of a freshly built tree, to remove all of the descendants of a node, if all of the leaf nodes below the current
node have colour within tolerance of the node’s average colour.
In this way, areas of the image with little colour variability can be replaced with a single rectangle of solid colour,
while areas with fine pixel detail can remain detailed. The image quality may be reduced, but fine details will still
be visible, and the size of the structure used to store the image data will also be reduced. An example of the
pruning effect is demonstrated in the pair of images below.
Original image (upscaled):
Rendered image after pruning at tolerance 0.05 (upscaled):

The tree constructed from the original image contains 57,344 leaf nodes; one for each pixel in the image.
The tree obtained after pruning contains 6,518 leaf nodes.
To complete this part of the assignment, you should complete (or modify) the following functions:
In class PTree:
void Prune(double tolerance)

It may be helpful to write two recursive helpers for this function.
Testing
We have provided a test file testPTree.cpp which includes a basic set of tests. It is highly recommended to add
to or modify the existing tests, especially to add tests which run your functions on tiny PNG images. The test
executable can be compiled by typing