hi guys, i am new in this forum, 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, i attached my project with my sample image, 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
mdawaina 0 Newbie Poster
/*
* | -----------\
* |
* |
* |
* |------------|
* |
* |
* |
* |
* |------------/
*/
#include <QtCore/QCoreApplication>
#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::GetImageRGB()
{
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(headsecond);
//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*headsecond.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::out | 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();
return a.exec();
}The attachment preview is chopped off after the first 10 KB. Please download the entire file.
#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::out | 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<< This attachment is potentially unsafe to open. It may be an executable that is capable of making changes to your file system, or it may require specific software to open. Use caution and only open this attachment if you are comfortable working with x-ms-bmp files.
mdawaina 0 Newbie Poster
What does the quadtree lib do?
the Quadtree lib inserts all the pixels into a quad tree (insert function), then the leafs of this tree is checked in order to delete every four same colors belong to one parent, this phase called simplification, and it produces the required quadtree, the leafs of this quadtree (which contains the compressed colors) are saved in other bitmap image
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.