• Status: Solved
• Priority: Medium
• Security: Public
• Views: 1614

Quad Tree Decomposition of an Image

Hello Java Guru's

Please help me in implementing one of the techniques of Image Processing. I want to take an image and decompose that image in a quad tree datastructure. Quad Tree datastructure is similar like binary tree but having four branches. THe image will be divided in to four quadrants (A,B,C,D) then these quadrants will further subdivided into four until it reaches the single pixel value.

Please tell me some API or Code from which i can easily implement this.

Thanks
Zubair
0
ZUBAIR
• 9
• 6
1 Solution

Commented:
This quadtree approach is a bit risky. It is not a given that all images and subsections of images can be divided into 4 sections (eg: if image is much longer than it is high)

Anyway here is a small class to build such a class tree. In the situation abowe it will produce some nodes with xSize or ySize equal to 0.

public class QuadTreeNode {

static final byte  NE = 0, SE = 1, SW = 2, NW = 3;

QuadTreeNode[] subNodes = null;

ImageInfo      pic = null;    // this will be info on the image, such as average color
// avg color deviation, most extreeme colors, etc

int xSize, ySize;                // size of image segment

QuadTreeNode( int xMin, int yMin, int xMax, int yMax, Image pic ) {
this xSize = xMax - xMin;
this.ySize = yMax - yMin;
if ( xsize > 1 || ySize > 1 ) {
this.subNodes = new QuadTreeNode[4];
subNodes[NW] = new QuadTreeNode( xMin, yMin, (xMin+xMax)/2, (yMin+yMax)/2, pic );
subNodes[SW] = new QuadTreeNode( xMin, (yMin+yMax)/2, (xMin+xMax)/2, yMax, pic );
subNodes[SE] = new QuadTreeNode( (xMin+xMax)/2, (yMin+yMax)/2, xMax, yMax, pic );
subNodes[NE] = new QuadTreeNode( (xMin+xMax)/2, yMin, xMax, (yMin+yMax)/2, pic );
}
// extract image data from that piece of image, evt synthesizing from the subnodes just created.

}//endconstructor

regards JakobA
0

Author Commented:
it's not clear - any other comments
0

Author Commented:
thanks for your answer- after struggling a bit, i have done it with the help of your code.

Anywayz one last question is how will this image will be breaked - if you could tell me small code to how to read an image and then split that image according to the above algorithm -

I will be really grateful
Thanks
Zubair
0

Commented:
'breaked' ?   I assume below that by this you mean 'interpreted' or 'understood'

As the recursion proceed it arraives at  pieces of image  that are a single pixel.  Such a piece of image is fully described by just giving its colorvalue.

But if there is a large areea on the picture that are all the same color, it may be that most of that area can also be described with just a colorvalue.  The purpose of the algorithm usually is to identify such areas so the imagefile can be compressed by defining large parts of the image with a single value.

The imagedata needed to determing when such compression is possible is collected in the variable 'pic'.
ImageInfo      pic = null;    // this will be info on the image, such as average color
// avg color deviation, most extreeme colors, etc
if the color deviation is zero. then the more detailed info obtained by further recursion is actually unnessesarry, this whole quadrant is all the same color.

But note that we cannot find the info in 'pic' without doing the recursion fully.The method collect all the 'pic' values in a quad tree. and then later you go through the tree and cut all unnessesarry branches, twigs or leaves off the tree. The resulting tree can then be written to a file as a compacted image.  below is an example of one (out of very many) ways that could be done:

Each 'pic'  variable are written in the file as a value for average color, and a set of 4 bits, the 4 bits represent the 4 sections that piece of image could be split into. if a bit is 0 the corresponding section of image is not in the file.

At the very start of the file are written the width and height of the image.  so:

4,4,red,'0000'
is a picture 4 pixel high and 4 pixel wide with a uniform red color
r r r r
r r r r
r r r r
r r r r

4,4,green,'1111',yellow,'0000',blue,'0000',blue,'0000',yellow,'0000'
is a picture composed of 4 squares (each 2 pixel wide and high), alernately yellow and blue.
y y b b
y y b b
b b y y
b b y y
4,4,green,'0111',yellow,'0000',green,'1111',yellow,'0000',blue,'0000',blue,'0000',yellow,'0000',blue,'0000'
g g y b
g g b y
y y b b
y y b b
If you think a bit you will se that the way the file is to be interpreted is actulally built into the file with the quadrant bits:
4,4,                           //General info (often you also have a palette here)
green,'0111',          //(All)      there will be 3 subquadrants described for this
yellow,'0000',         //(All,SE)     no further description
green,'1111',          //(All,NW)    all 4 subquadrants described
yellow,'0000',           //(All,NW,NE)     no further description
blue,'0000',              //(All,NW,SE)     no further description
blue,'0000',              //(All,NW,NW)     no further description
yellow,'0000',           //(All,NW,SW)     no further description
blue,'0000'            //(All,SW)     no further description

This is far from the best way of encoding the image-data, just an understandable one :-)

regards JakobA
0

Author Commented:
thanks

:) it is some thing easy to understand but damn hard to implement :).

I have picked ub the concept, could you provide me with some sample code or a link, that would really be more helpful.

thanks

0

Commented:
Sorry, I know of no simple links for this. Also your instructors must have future plans needing quad rather than binary tree that I do not underdtand. I should not interfere too much where i cannot even secondguess.
0

Author Commented:
HI Jakoba
Please have a look on the question below, i think you can answer it.

Thanks

http://www.experts-exchange.com/Programming/Programming_Languages/Java/Q_21444805.html
0

Author Commented:
Hi JakobA

Thanks for your help. You have been of great help to me- I really don't have words to thank you.

Jakob i am working on a image segmentation algorithm, and half part is done which was decomposing of the image and storing it in the quad tree with all the statistical data.

Now the second level is to find the seed regions and then merge the neighboring regions of the image and make a clear boundary.

Now please tell me what should i do next. As very few days are left to submit this project

Thanks Zubair
0

Commented:
> Thanks for your help. You have been of great help to me- I really don't have
> words to thank you.

You are welcome :-))

> Jakob i am working on a image segmentation algorithm, and half part is done
> which was decomposing of the image and storing it in the quad tree with all
> the statistical data.
>
> Now the second level is to find the seed regions and then merge the neighboring
> regions of the image and make a clear boundary.

The 'merge the neighbouring regions' is impicit in the answer at your other question
(Q_21444805) where branches with 'same color and no variance' are pruned from the
tree.

> Now please tell me what should i do next. As very few days are left to submit
> this project

Alas, I cannot. Sofar I have just been using common sense and general programming
competence. I do not really understand what is meant by Technical terms like 'seed
regions' or 'a clear boundary'.

regards JakobA
0

Author Commented:
HI JakobA

Please have a look on this question

http://www.experts-exchange.com/Programming/Programming_Languages/Java/Q_21452213.html

Regards Zubair
0

Author Commented:
HI Jakob.A

I hope you have received my message.

Thanks & Regards
Zubair
0

Commented:
to look at http:Q_21452213.html ?  Yes I read that, but was unable to give a worthwhile answer, so kept quiet :)
0

Author Commented:
0

Commented:
Sorry. no missed that. That e-address get inundated by ca 200 spam mail daily. I miss most 'real' mail to it except what I have filters for. try <same name> @ gmail.com that is faily spamfree sofar.
0

Author Commented:
Thanks Jakob , i have send the mail again at your new address . Please have a look at it and reply me back as soon as possible.
Thanks Zubair
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Featured Post

• 9
• 6
Tackle projects and never again get stuck behind a technical roadblock.