A tree structure that is used to compress PNG images. More...

#include "quadtree.h"

Collaboration diagram for Quadtree:

Classes
class	QuadtreeNode
	A simple class representing a single node of a Quadtree. More...

Public Member Functions
	Quadtree ()
	The no parameters constructor takes no arguments, and produces an empty Quadtree object, i.e. More...

	Quadtree (PNG const &source, int resolution)
	This constructor's purpose is to build a Quadtree representing the upper-left d by d block of the source image. More...

	Quadtree (Quadtree const &other)
	Copy constructor. More...

	~Quadtree ()
	Destructor; frees all memory associated with this Quadtree. More...

Quadtree const &	operator= (Quadtree const &other)
	Assignment operator; frees memory associated with this Quadtree and sets its contents to be equal to the parameter's. More...

void	buildTree (PNG const &source, int resolution)
	Deletes the current contents of this Quadtree object, then turns it into a Quadtree object representing the upper-left d by d block of source. More...

RGBAPixel	getPixel (int x, int y) const
	Gets the RGBAPixel corresponding to the pixel at coordinates (x, y) in the bitmap image which the Quadtree represents. More...

PNG	decompress () const
	Returns the underlying PNG object represented by the Quadtree. More...

void	clockwiseRotate ()
	Rotates the Quadtree object's underlying image clockwise by 90 degrees. More...

void	prune (int tolerance)
	Compresses the image this Quadtree represents. More...

int	pruneSize (int tolerance) const
	This function is similar to prune; however, it does not actually prune the Quadtree. More...

int	idealPrune (int numLeaves) const
	Calculates and returns the minimum tolerance necessary to guarantee that upon pruning the tree, no more than numLeaves leaves remain in the Quadtree. More...

void	printTree (std::ostream &out=std::cout) const
	Given: prints the leaves of the Quadtree using a preorder traversal. More...

bool	operator== (Quadtree const &other) const
	Given: compares the current Quadtree with the parameter Quadtree, and determines whether or not the two are the same. More...

Private Member Functions
void	printTree (std::ostream &out, QuadtreeNode const *current, int level) const
	Given: prints the contents of the Quadtree using a preorder traversal. More...

bool	compareTrees (QuadtreeNode const firstPtr, QuadtreeNode const secondPtr) const
	Given: compares the subQuadtree rooted at firstPtr with the subQuadtree rooted at secondPtr, and determines whether the two are the same. More...

Private Attributes
QuadtreeNode *	root
	pointer to root of quadtree More...

Detailed Description

A tree structure that is used to compress PNG images.

Constructor & Destructor Documentation

Quadtree::Quadtree ( )

The no parameters constructor takes no arguments, and produces an empty Quadtree object, i.e.

one which has no associated QuadtreeNode objects, and in which root is NULL.

Quadtree::Quadtree	(	PNG const &	source,
		int	resolution
	)

This constructor's purpose is to build a Quadtree representing the upper-left d by d block of the source image.

This effectively crops the source image into a d by d square.

You may assume that d is a power of two, and that the width and height of source are each at least d.

Perhaps, to implement this, you could leverage the functionality of another function you have written in 5.1...

Parameters

source	The source image to base this Quadtree on
resolution	The width and height of the sides of the image to be represented

Quadtree::Quadtree ( Quadtree const & other )

Copy constructor.

Simply sets this Quadtree to be a copy of the parameter.

Parameters

other The Quadtree to make a copy of

Quadtree::~Quadtree ( )

Destructor; frees all memory associated with this Quadtree.

Member Function Documentation

Quadtree const & Quadtree::operator= ( Quadtree const & other )

Assignment operator; frees memory associated with this Quadtree and sets its contents to be equal to the parameter's.

Parameters

other The Quadtree to make a copy of

Returns: A constant reference to the Quadtree value that was copied

void Quadtree::buildTree	(	PNG const &	source,
		int	resolution
	)

Deletes the current contents of this Quadtree object, then turns it into a Quadtree object representing the upper-left d by d block of source.

You may assume that d is a power of two, and that the width and height of source are each at least d.

Parameters

source	The source image to base this Quadtree on
resolution	The width and height of the sides of the image to be represented

RGBAPixel Quadtree::getPixel	(	int	x,
		int	y
	)		const

Gets the RGBAPixel corresponding to the pixel at coordinates (x, y) in the bitmap image which the Quadtree represents.

Note that the Quadtree may not contain a node specifically corresponding to this pixel (due, for instance, to pruning - see below). In this case, getPixel will retrieve the pixel (i.e. the color) of the square region within which the smaller query grid cell would lie. (That is, it will return the element of the nonexistent leaf's deepest surviving ancestor.) If the supplied coordinates fall outside of the bounds of the underlying bitmap, or if the current Quadtree is "empty" (i.e., it was created by the default constructor) then the returned RGBAPixel should be the one which is created by the default RGBAPixel constructor.

Parameters

x	The x coordinate of the pixel to be retrieved
y	The y coordinate of the pixel to be retrieved

Returns: The pixel at the given (x, y) location

PNG Quadtree::decompress ( ) const

Returns the underlying PNG object represented by the Quadtree.

If the current Quadtree is "empty" (i.e., it was created by the default constructor) then the returned PNG should be the one which is created by the default PNG constructor. This function effectively "decompresses" the Quadtree. A Quadtree object, in memory, may take up less space than the underlying bitmap image, but we cannot simply look at the Quadtree and tell what image it represents. By converting the Quadtree back into a bitmap image, we lose the compression, but gain the ability to view the image directly.

Returns: The decompressed PNG image this Quadtree represents

void Quadtree::clockwiseRotate ( )

Rotates the Quadtree object's underlying image clockwise by 90 degrees.

(Note that this should be done using pointer manipulation, not by attempting to swap the element fields of QuadtreeNodes. Trust us; it's easier this way.)

void Quadtree::prune ( int tolerance )

Compresses the image this Quadtree represents.

If the color values of the leaves of a subquadtree don't vary by much, we might as well represent the entire subtree by, say, the average color value of those leaves. We may use this information to effectively "compress" the image, by strategically trimming the Quadtree.

Consider a node \(n\) and the subtree, \(T_n\) rooted at \(n\), and let \(avg\) denote the component-wise average color value of all the leaves of \(T_n\). Component-wise average means that every internal node in the tree calculates its value by averaging its immediate children. This implies that the average must be calculated in a "bottom-up" manner.

Due to rounding errors, using the component-wise average is not equivalent to using the true average of all leaves in a subtree. If a node \(n\) is pruned, the children of \(n\) and the subtrees for which they are the roots are removed from the Quadtree. Node \(n\) is pruned if the color value of no leaf in \(T_n\), differs from \(avg\) by more than tolerance. (Note: for all average calculations, just truncate the value to integer.)

We define the "difference" between two colors, \((r_1, g_1, b_1)\) and \((r_2, g_2, b_2)\), to be \((r_2 - r_1)^2 + (g_2 - g_1)^2 + (b_2 - b_1)^2\).

To be more complete, if the tolerance condition is met at a node \(n\), then the block of the underlying image which \(n\) represents contains only pixels which are "nearly" the same color. For each such node \(n\), we remove from the Quadtree all four children of \(n\), and their respective subtrees (an operation we call a pruning). This means that all of the leaves that were deleted, corresponding to pixels whose colors were similar, are now replaced by a single leaf with color equal to the average color over that square region.

The prune function, given a tolerance value, prunes the Quadtree as extensively as possible. (Note, however, that we do not want the prune function to do an "iterative" prune. It is conceivable that by pruning some mid-level node \(n\), an ancestor \(p\) of \(n\) then becomes prunable, due to the fact that the prune changed the leaves descended from \(p\). Your prune function should evaluate the prunability of each node based on the presence of all nodes, and then delete the subtrees based at nodes deemed prunable.)

Note: You should start pruning from the root of the Quadtree.

Parameters

tolerance The integer tolerance between two nodes that determines whether the subtree can be pruned.

int Quadtree::pruneSize ( int tolerance ) const

This function is similar to prune; however, it does not actually prune the Quadtree.

Rather, it returns a count of the total number of leaves the Quadtree would have if it were pruned as in the prune function.

Parameters

tolerance The integer tolerance between two nodes that determines whether the subtree can be pruned.

Returns: How many leaves this Quadtree would have if it were pruned with the given tolerance.

int Quadtree::idealPrune ( int numLeaves ) const

Calculates and returns the minimum tolerance necessary to guarantee that upon pruning the tree, no more than numLeaves leaves remain in the Quadtree.

Essentially, this function is an inverse of pruneSize; for any Quadtree object theTree, and for any positive integer tolerance it should be true that

 theTree.pruneSize(theTree.idealPrune(numLeaves)) <= numLeaves

Once you understand what this function is supposed to do, you will probably notice that there is an "obvious" implementation. This is probably not the implementation you want to use! There is a fast way to implement this function, and a slow way; you will need to find the fast way. (If you doubt that it makes a significant difference, the tests in the given main.cpp should convince you.)

Parameters

numLeaves The number of leaves you want to remain in the tree after prune is called.

Returns: The minimum tolerance needed to guarantee that there are no more than numLeaves remaining in the tree.

Note: The "obvious" implementation involves a sort of linear search over all possible tolerances. What if you tried a binary search instead?

void Quadtree::printTree ( std::ostream & out = std::cout ) const

Given: prints the leaves of the Quadtree using a preorder traversal.

bool Quadtree::operator== ( Quadtree const & other ) const

Given: compares the current Quadtree with the parameter Quadtree, and determines whether or not the two are the same.

Parameters

other Reference to a const Quadtree object, against which the current Quadtree will be compared

Returns: True if the Quadtrees are deemed "equal", and false otherwise

Note: This method relies on the private helper method compareTrees()

void Quadtree::printTree	(	std::ostream &	out,
		QuadtreeNode const *	current,
		int	level
	)		const

private

Given: prints the contents of the Quadtree using a preorder traversal.

Parameters

current	Pointer to the root of the subQuadtree which we wish to print
level	Current recursion depth; used for determining when to terminate recursion (see note below)

bool Quadtree::compareTrees	(	QuadtreeNode const *	firstPtr,
		QuadtreeNode const *	secondPtr
	)		const

private

Given: compares the subQuadtree rooted at firstPtr with the subQuadtree rooted at secondPtr, and determines whether the two are the same.

Parameters

firstPtr	Pointer to the root of a subtree of the "first" Quadtree under consideration
secondPtr	Pointer to the root of a subtree of the "second" Quadtree under consideration

Returns: True if the subQuadtrees are deemed "equal", and false otherwise

Member Data Documentation

QuadtreeNode* Quadtree::root

private

pointer to root of quadtree

The documentation for this class was generated from the following files:

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation