[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1504
  • Last Modified:

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
Asked:
ZUBAIR
  • 9
  • 6
1 Solution
 
JakobACommented:
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

    }//endclass QuadTreeNode

regards JakobA
0
 
ZUBAIRAuthor Commented:
it's not clear - any other comments
0
 
ZUBAIRAuthor 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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
JakobACommented:
'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
 
ZUBAIRAuthor 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
 
JakobACommented:
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
 
ZUBAIRAuthor 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
 
ZUBAIRAuthor 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
 
JakobACommented:
> 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
 
ZUBAIRAuthor 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
 
ZUBAIRAuthor Commented:
HI Jakob.A

I hope you have received my message.

Thanks & Regards
Zubair
0
 
JakobACommented:
to look at http:Q_21452213.html ?  Yes I read that, but was unable to give a worthwhile answer, so kept quiet :)
0
 
ZUBAIRAuthor Commented:
No i have emailed you yesterday, i hope you have received that email. I got your email address from your home page
0
 
JakobACommented:
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
 
ZUBAIRAuthor 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

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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