Hi all.
my project is about Quad Tree image compression, the problem is that it does
not succeed to encode large images, it works good for my small 8 by 8 image, i
work by QT c++ editor,, notice that when you input other images, it must be
.bmp format, must be squared ( height = width) and of the power 2 e.g. 256 by
256 or 512 by 512, i hope that you fix my problem
here is my code, i did not found any attachment facilities
//Quadtree.h
#ifndef QUADTREE_H
#define QUADTREE_H
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
template< class Type> class Quadtree
{
public:
// Node
struct Node
{
Type _data;
Node *NW; // Pointer to the NW Node
Node *SW; // Pointer to the NE Node
Node *SE; // Pointer to the SW Node
Node *NE; // Pointer to the SE Node
Node( )
{
NW = SW = SE = NE = NULL;
}
Node( Type data )
{
_data = data;
NW = SW = SE = NE = NULL;
}
~Node()
{
}
};
private:
Node *m_root; // First Node in the quadtree.
Node *m_iterate; // Used for iterating the quadtree.
Node *m_temp; // Used for temporary storage in various operations.
Type *QTarray;
Type *ColorArray;
int *structArray;
int *arr;
int counter;
int dataCounter;
unsigned dimension;
public:
/* Constructor */
Quadtree()
{
m_root = m_iterate = m_temp = NULL;
dimension = 0;
}
/* Destructor */
~Quadtree()
{
/* Empty. */
}
/* Return the first Node in the quadtree. */
Type* GetRoot()
{
if( m_root )
return m_root->_data;
else
return NULL;
}
/* Print out the quadtree. */
void Print( )
{
PrintNode(m_ root);
}
/* Recurse the quadtree and print the leaf nodes. */
void PrintNode(Node* current_node)
{
if( current_node != NULL ){
// If the NW node exists, all four child nodes exist
if( current_node- >NW != NULL ){
PrintNode(current_ node->NW) ;
PrintNode(current_ node->SW) ;
PrintNode(current_ node->SE) ;
PrintNode(current_ node->NE) ;
}
else{
// cout << (current_node- > _data) <<endl;
//treeStructure[ ]=0;
}
}
}
/* Insert the data into the quadtree. Quadtree must be empty before insertion.
*/
void Insert(Type *data, int size)
{
m_root = new Node();
dimension = size;
counter=0;
dataCounter= 0;
//insert the data
InsertNode(m_ root, data, size);
//collapse branches with same color leaves
Simplify(m_root, size);
//Print();
structArray= new int[41];
ColorArray= new Type[size*size] ;
arr=new int[41];
//---------- --------- ----
arr[0]=0;
arr[1]=0;
arr[2]=1;
arr[3]=0;
arr[4]=1;
arr[5]=1;
arr[6]=1;
arr[7]=1;
arr[8]=1;
arr[9]=0;
arr[10]=1;
arr[11]=1;
arr[12]=1;
arr[13]=1;
arr[14]=0;
arr[15]=0;
arr[16]=1;
arr[17]=1;
arr[18]=1;
arr[19]=1;
arr[20]=1;
arr[21]=1;
arr[22]=0;
arr[23]=1;
arr[24]=1;
arr[25]=1;
arr[26]=1;
arr[27]=1;
arr[28]=0;
arr[29]=0;
arr[30]=1;
arr[31]=1;
arr[32]=1;
arr[33]=1;
arr[34]=1;
arr[35]=0;
arr[36]=1;
arr[37]=1;
arr[38]=1;
arr[39]=1;
arr[40]=1;
//ColorArray[ 0]=assign( );
counter=0;
dataCounter= 0;
treeStruct(m_ root,0);
cout << "<"<<dataCounter< <">";
cout << endl;
// for(int i=40;i>=0;i- -)
// cout << structArray[ i];
// destructTree( m_root);
cout << endl;
// counter=0;
// treeStruct(m_ root,0);
counter=-1;
cout << endl;
cout << "the new tree";
cout << endl;
// constructTree( m_root, data,0);
counter=0;
cout << endl;
/* struct num{int x;};
num cc;
cc.x=10241024;
ofstream aa("file.txt" , ios:ut | ios::binary) ;
int z=10241024;
char y='f';
aa.write((char *)&cc, sizeof(struct num));
aa.close();
cc.x=7;
ifstream inbal("file. txt", ios::in | ios::binary) ;
inbal.read(( char *) &cc, sizeof(struct num));
cout << "********"<< endl;
cout << cc.x<<endl;
cout <<"********" << endl;
inbal.close( );*/
// treeStruct(m_ root,0);
// cout << "("<<counter< <")";
// for(int j=31;j>0;j-- )
// cout << arr[j];
}
/* Recurse the quadtree and insert all data. */
void InsertNode(Node* current_node, Type *data, int size){
//if at the pixel level, store the color data
if( (size) == 1)
{
current_node- >_data = data[0];
// cout << "("<<(int)current_ node->_data. r<<","<< (int)current_ node->_data.
g<<","<< (int)current_ node->_data. b<<")"<<endl;
}
else{
// cout << "hello";
//otherwise, divide area into fourths (size is the length of one side)
int n = (size/2);
Type* current_data = new Type[(n*n)];
//store the data to be passed to the NW node
int i=0;
for(int k=n; k< size; k++){
for( int j=0; j < n; j++){
current_data[ i] = data[k*size+ j];
i++;
}
}
//create the new leaf and pass it the new data
current_node- >NW = new Node();
InsertNode(current_ node->NW, current_data, n);
//store the data to be passed to the SW node
i=0;
for(int k=0; k< n; k++){
for( int j=0; j < n; j++){
current_data[ i] = data[k*size+ j];
i++;
}
}
//---------- --------- --------- --------- --------- -------
//create the new leaf and pass it the new data
current_node- >SW = new Node();
InsertNode(current_ node->SW, current_data, (size/2));
//store the data to be passed to the SE node
i=0;
for(int k=0; k< n; k++){
for( int j=n; j < size; j++){
current_data[ i] = data[k*size+ j];
i++;
}
}
//create the new leaf and pass it the new data
current_node- >SE = new Node();
InsertNode(current_ node->SE, current_data, (size/2));
//store the data to be passed to the NE node
i=0;
for(int k=n; k< size; k++){
for( int j=n; j < size; j++){
current_data[ i] = data[k*size+ j];
i++;
}
}
//---------- --------- --------- --------- ---------
//create the new leaf and pass it the new data
current_node- >NE = new Node();
InsertNode(current_ node->NE, current_data, n);
}
}
/* Get the size of the image. This returns the length of one of the sides. */
unsigned getSize(){
return dimension;
}
/* Get the image data. This returns an array of type Type*. */
Type* getData(){
return getData(dimension) ;
}
/* Initialize the image data array, build it, then return it. */
Type* getData(unsigned size){
QTarray = new Type[size * size];
buildArray(m_ root, size, size, 0);
return QTarray;
}
Type* getImage(){
return getImage(dimension) ;
}
Type* getImage(unsigned size){
// ColorArray= new Type[size * size];
//buildTree( m_root,size, size,0);
return ColorArray;
}
/*int* getArr(int size)
{
structArray= new int[size*size] ;
for(int i=0;i<size*size; i++)
structArray[ i]=0;
return structArray;
}*/
/* Recurse the quadtree and store the image data in the vector QTarray. */
void buildArray(Node* current_node, unsigned startSize, unsigned size, unsigned
index){
//if at the pixel level, store the color data
if (size == 1)
QTarray[index] = current_node- >_data;
else{
//otherwise, divide area into fourths (size is the length of one side)
unsigned n = size / 2;
//check to make sure that the current node has children before recursing deeper
// If the NW node exists, all four child nodes exist
if(current_node- >NW != NULL){
buildArray(current_ node->NW, startSize, n, index);
buildArray(current_ node->SW, startSize, n, index + n * startSize);
buildArray(current_ node->SE, startSize, n, index + n * startSize + n);
buildArray(current_ node->NE, startSize, n, index + n);
}
//if the current node does not have children and we are not at the pixel level,
//all pixels in the current area are the same color
else{
for(int i = 0; i < size; ++i){
for(int j = 0; j < size; ++j){
QTarray[index + j + i * startSize] = current_node- >_data;
}
}
}
}
}
/* From the bottom up, collapse any branches whose leaves are all the same
color. */
void Simplify(Node* current_node, int size){
//if at the pixel level, return to the node's parent
if(size == 1)
{
// cout << "("<<(int)current_ node->_data. r<<","<< (int)current_ node->_data.
g<<","<< (int)current_ node->_data. b<<")"<<endl;
//cout << "0";
return;
}
else{
//keep recursing until the pixel level is reached
Simplify(current_ node->NW, size/2);
Simplify(current_ node->SW, size/2);
Simplify(current_ node->SE, size/2);
Simplify(current_ node->NE, size/2);
//if any of the current node's children are not equal to NULL,
//they have children of their own and are not able to be collapsed
/* if( ( (current_node- >NW != NULL) || (current_node- >NE != NULL) ) ||
( (current_node- >SW != NULL) || (current_node- >SE != NULL) ) )
return;*/
cout << "("<<(int)current_ node->NW- >_data.r< <","<< (int)current_ node->NW-
>_data.g< <","<< (int)current_ node->NW- >_data.b< <")"<<endl;
//if all of the current node's children are the same, set the current node's
//value to that of its children, delete the children, and NULLify the pointers
if( ( (current_node- >NW->_data == current_node- >NE->_data) &&
(current_node- >NW->_data == current_node- >SW->_data) ) &&
(current_node- >NW->_data == current_node- >SE->_data) ) {
// cout <<"mohamed";
// cout << "("<<(int)current_ node->NW- >_data.r< <","<< (int)current_
node->SE- >_data.g< <","<< (int)current_ node->SE- >_data.b< <")"<<endl;
current_node- >_data = current_node- >NW->_data;
delete current_node- >NW;
delete current_node- >SW;
delete current_node- >SE;
delete current_node- >NE;
current_node- >NW = NULL;
current_node- >SW = NULL;
current_node- >SE = NULL;
current_node- >NE = NULL;
}
}
}
/* Simplify the quadtree to the specified depth. */
void granulateImage( unsigned quality){
return granulateImage( quality, dimension);
}
/* Simplify the quadtree to the specified depth and size. */
void granulateImage( unsigned quality, unsigned size){
Granulate(m_ root, size / pow( (float)2, (int)quality ), size);
}
/* From the bottom up, collapse any branches whose depth is greater than that
specified. */
void Granulate(Node* current_node, unsigned quality, int size){
//if at the pixel level, return to the node's parent
if(size == 1)
return;
//keep recursing until the pixel level is reached
// If the NW node exists, all four child nodes exist
if(current_node- >NW != NULL){
Granulate(current_ node->NW, quality, size/2);
Granulate(current_ node->SW, quality, size/2);
Granulate(current_ node->SE, quality, size/2);
Granulate(current_ node->NE, quality, size/2);
//average the colors of the children and collapse the branches as long as the
size is less
//than the desired quality (because the size is divided by two with each call
to Granulate(),
//it doubles as the recursive loop unwinds)
if(size <= quality){
current_node- >NW->_data = current_node- >NW->_data. average(current_ node->NE-
>_data);
current_node- >SW->_data = current_node- >SW->_data. average(current_ node->SE-
>_data);
current_node- >_data = current_node- >NW->_data. average(current_ node->SW-
>_data);
delete current_node- >NW;
delete current_node- >SW;
delete current_node- >SE;
delete current_node- >NE;
//cout <<"hello";
current_node- >NW = NULL;
current_node- >SW = NULL;
current_node- >SE = NULL;
current_node- >NE = NULL;
//cout <<"0";
}
}
}
void treeStruct(Node* current_node, unsigned index)
{
if (current_node- >NW != NULL)
{
cout <<"0";
treeStruct(current_ node->NW, 0);
treeStruct(current_ node->SW, 0);
treeStruct(current_ node->SE, 0);
treeStruct(current_ node->NE, 0);
}
else{
cout << "1";
ColorArray[dataCoun ter]= current_node- >_data;
dataCounter+ +;
}
counter++;
}
void destructTree( Node* current_node)
{
if(current_node- >NW != NULL)
{
destructTree( current_node- >NW);
destructTree( current_node- >SW);
destructTree( current_node- >SE);
destructTree( current_node- >NE);
delete current_node- >NW;
delete current_node- >SW;
delete current_node- >SE;
delete current_node- >NE;
current_node- >NW = NULL;
current_node- >SW = NULL;
current_node- >SE = NULL;
current_node- >NE = NULL;
}
}
void constructTree( Node* current_node, Type *data,int size )
{
// g:
if(counter>= 41)
{
return;
}
else
{
counter++;
if(arr[counter] ==0)
{
cout <<"yes";
current_node- >NW = new Node();
constructTree( current_node- >NW,data, size+1);
current_node- >SW = new Node();
constructTree( current_node- >SW,data, size+1);
current_node- >SE = new Node();
constructTree( current_node- >SE,data, size+1);
current_node- >NE = new Node();
constructTree( current_node- >NE,data, size+1);
}
else
{
cout << "("<<counter< <")";
return;
}
}
}
void buildTree(Node* current_node, unsigned startSize, unsigned size, unsigned
index)
{
/* if(size==1)
ColorArray[index] = current_node- >_data;
else{
//otherwise, divide area into fourths (size is the length of one side)
unsigned n = size / 2;
//check to make sure that the current node has children before recursing deeper
// If the NW node exists, all four child nodes exist
if(current_node- >NW != NULL){
buildArray(current_ node->NW, startSize, n, index);
buildArray(current_ node->SW, startSize, n, index + n);
buildArray(current_ node->SE, startSize, n, index + n * startSize);
buildArray(current_ node->NE, startSize, n, index + n * startSize + n);
}
}*/
// for(int i=31;i<36;i+ +)
// ColorArray[i] =current_ node->_data;
}
};
#endif // QUADTREE_H
// main.cpp
/*
* | -----------\
* |
* |
* |
* |----------- -|
* |
* |
* |
* |
* |----------- -/
*/
#include <QtCore/QCoreApplic ation>
#include <fstream>
#include <iostream>
//#include <stdio.h>
//#include <iostream>
#include <string>
#include "Quadtree.h"
using namespace std;
#pragma pack(2)
//the first header contains 14 bytes
typedef struct
{
unsigned short int type;
unsigned int size;
unsigned short int reserved1,reserved2 ;
unsigned int offset;
}Header;
#pragma pack() /* Default packing */
//the second header contains 40 bytes
typedef struct
{
unsigned int size;
int width,height;
unsigned short int bits;
unsigned int compression;
unsigned int imagesize;
int xresolution, yresolution;
unsigned int ncolors;
unsigned int importantcolors;
}Infoheader;
// the structure that represent a pexel
struct rgb_t
{
unsigned char r;
unsigned char g;
unsigned char b;
bool operator == (const rgb_t &arg) const{
return(((arg. r == r) && (arg.g == g)) && (arg.b == b));
}
rgb_t average(const rgb_t &arg) const{
rgb_t val;
val.r = (arg.r + r) / 2;
val.g = (arg.g + g) / 2;
val.b = (arg.b + b) / 2;
return val;
}
rgb_t operator / (const unsigned &arg) const{
rgb_t val;
val.r = r / arg;
val.g = g / arg;
val.b = b / arg;
return val;
}
}great;
class bmpimage
{
private:
unsigned char *m_pImageData;
public:
rgb_t *GetImageRGB( );
rgb_t *CreateRGB(/ *rgb_t* */);
};
rgb_t* bmpimage::GetImageR GB()
{
Header me;
unsigned size =me.size-56;
rgb_t* imageData = new rgb_t[size];
for (unsigned i = 0; i < size; ++i){
imageData[i] .r = m_pImageData[ i * 3 ];
imageData[i] .g = m_pImageData[ i * 3 + 1 ];
imageData[i] .b = m_pImageData[ i * 3 + 2 ];
}
return imageData;
}
rgb_t* bmpimage::CreateRGB (/* rgb_t* pImageData*/ ){
//Header me;
//Infoheader me2;
//unsigned size = me2.height*me2. width;
// cout << "**"<<size;
cout << endl;
//unsigned char* imageData = new unsigned char[size];
// for (unsigned i = 0; i < size; ++i){
// imageData[i * 3] = pImageData[i] .r;
// imageData[i * 3 + 1] = pImageData[i] .g;
// imageData[i * 3 + 2] = pImageData[i] .b;
// }
// return imageData;
}
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
bmpimage* m_tga = new bmpimage;
ifstream bmpfile("shape. bmp", ios::in | ios::binary) ;
if(!bmpfile)
cout << "image cannot be loaded" << endl;
Header headfirst;
Infoheader headsecond;
//great data1;
// rgb_t* school;
//reading the first 14 bytes
bmpfile.read( (char *)&headfirst, sizeof(headfirst) );
//int s= sizeof(headfirst) +sizeof(headseco nd);
//int d=headfirst. size;
//int f=headsecond. height;
//int z=d-s;
//cout <<d-s;
unsigned char* pImageData;
// school =new rgb_t[16];
unsigned char dd;
// cout << "height: " << (int)headsecond. height;
cout << endl;
// readnig the second 40 bytes
bmpfile.read( (char *)&headsecond, sizeof(headsecond) );
//cout << "height: " << (int)headsecond. height;
//////////// ///////// ///////// ///////// ///////// //// headfirst.size;
//bmpfile.seekg (54, ios::beg);
//int length = bmpfile.tellg( );
//unsigned size=headsecond. height;
//cout << size;
//********** ********* ********* ********* ********* **** ************ *******
// * |--------\
// * * | \
// * * | |
// * * | |
// * * |--------/
// * * |
// * * |
// * ----------- * |
// * * |
// * * |
// * * |
//* * |
//********** ********* ********* ********* ********* **** ************ *********
Quadtree<rgb_ t> image;
unsigned size = headsecond.height* headsecond. width;
pImageData=new unsigned char[size*3] ;
//reading the data
for(unsigned i=0;i<size*3; i++)
{
bmpfile.read( (char *)&dd,sizeof( char));
pImageData[i] =dd;
}
rgb_t* imageData = new rgb_t[size];
for (unsigned i = 0; i < size; ++i)
{
imageData[i] .r = pImageData[ i * 3 ];
imageData[i] .g = pImageData[ i * 3 + 1 ];
imageData[i] .b = pImageData[ i * 3 + 2 ];
}
image.Insert( imageData , headsecond.height) ;
rgb_t* idata = image.getImage( );
// the output
unsigned size2 =headsecond. height*headsecon d.width;
unsigned char* imageData2 = new unsigned char[size2 * 3];
for (unsigned i = 0; i < size2; ++i)
{
imageData2[i * 3] = idata[i].r;
imageData2[i * 3 + 1] = idata[i].g;
imageData2[i * 3 + 2] = idata[i].b;
}
/*
unsigned size =headfirst.size- 56;
rgb_t* imageData = new rgb_t[size];
for (unsigned i = 0; i < size; ++i){
imageData[i] .r = pImageData[ i * 3 ];
imageData[i] .g = pImageData[ i * 3 + 1 ];
imageData[i] .b = pImageData[ i * 3 + 2 ];
}
*/
//great ggg;
cout <<"--------- -----";
cout << endl;
//cout <<headfirst. size-56;/ / (int)imageData[ 15].b;
//bmpfile.read( (char *)&school,sizeof( char));
//cout.write( (char *)&school,2* sizeof(data1) );
cout << endl;
//cout <<(int)dd;// (int)pImageData[ 2];
cout << endl;
//school[0]. r='a';
/*for(int i=0;i<48;i++ )
{
cout <<(int)pImageData[ i];
cout << endl;
}*/
char fd;
bmpfile.close( );
//writing the bmp image
ofstream bmpf("shape_ enc.bmp", ios:ut | ios::binary) ;
bmpf.write(( char *)&headfirst, sizeof(headfirst ));
bmpf.write(( char *)&headsecond, sizeof(headsecond) );
for(int i=0;i<size2* 3;i++)
{
fd=imageData2[ i];
bmpf.write(( char *)&fd, sizeof(char) );
}
bmpf.close() ;
}
