quadtree assignment

[garywoot]

http://www.csd.uwo.ca/courses/CS1027b/assignments/asn4/asn4-description.html


basically, here's what i have so far in the QuadTree class:

Java:

public class QuadTree {                 /** Attributes **/         Picture pic;         QuadNode root;         int maxLevel;         double RedT;         double GreenT;         double BlueT;                 /**          * Constructor for QuadTree          * @param pic - the picture object          * @param root - the root          * @param maxLevel - the maximum level          * @param RedT - the red T          * @param GreenT - the green T          * @param BlueT - the blue T          */         public QuadTree (Picture pic, QuadNode root, int maxLevel, double RedT, double GreenT, double BlueT){                 this.pic = pic;                 this.root = root;                 this.maxLevel = maxLevel;                 this.RedT = RedT;                 this.GreenT = GreenT;                 this.BlueT = BlueT;         }                 /**          * Split helper method that splits the segments represented by it into 4 QuadNode nodes          * One for each of northEast, northWest, southEast, and southWest          * @param QuadNode node          */         public void split (QuadNode node){                         } }

As you can see, all I have is a constructor. That's the extent of my understanding of this assignment. I have no idea what this assignment is about (i've read it over 10 times). Can someone with experience tell me what I'm supposed to do?

Mod Edit:
Please wrap you code in either of the following in order to preserve whitespace (indentation) and to highlight the syntax.

code:

[syntax="java"] ... code ... [/syntax] [code] ... code ... [/code ]

[Insectoid]

You're basically supposed to compress the image, but without actually compressing it. Naturally, you're going to need to build a quadtree. Wikipedia explains it pretty well, but in short, every leaf should contain an pixel array and every non-leaf node should contain pointers to nodes or leaves. The size of the array should be (image width/node depth)*(image height/node depth). If the root were the only node, it would include only a 512*512 pixel array (since your sample image is 512*512). If the tree is of depth 1, each leaf is 256*256, since they are half as wide and tall as the total image. You can make good use of a union here, since leaves don't need child pointers and branches don't need arrays (wait, never mind. Java hasn't got unions, though you can accomplish the same thing with classes).

So that's what your tree should look like. In your split() function, you should split your 2D array into 4 smaller arrays corresponding to the 4 quarters of the image and assign each of those arrays to a child node.

The most important part is calculating the standard deviation of your pixels and deciding whether to split the node again, or call it a leaf and replace its entire array with one color. Lucky for you, your teacher has given you a class that does just that. So all that's really left to do, once your image is segmented, is to replace all the pixels in the array in each node with the average color of that segment.

Hopefully I explained that well enough.

[garywoot]

Insectoid @ Mon Apr 08, 2013 9:02 pm wrote:

You're basically supposed to compress the image, but without actually compressing it. Naturally, you're going to need to build a quadtree. Wikipedia explains it pretty well, but in short, every leaf should contain an pixel array and every non-leaf node should contain pointers to nodes or leaves. The size of the array should be (image width/node depth)*(image height/node depth). If the root were the only node, it would include only a 512*512 pixel array (since your sample image is 512*512). If the tree is of depth 1, each leaf is 256*256, since they are half as wide and tall as the total image. You can make good use of a union here, since leaves don't need child pointers and branches don't need arrays (wait, never mind. Java hasn't got unions, though you can accomplish the same thing with classes).

So that's what your tree should look like. In your split() function, you should split your 2D array into 4 smaller arrays corresponding to the 4 quarters of the image and assign each of those arrays to a child node.

The most important part is calculating the standard deviation of your pixels and deciding whether to split the node again, or call it a leaf and replace its entire array with one color. Lucky for you, your teacher has given you a class that does just that. So all that's really left to do, once your image is segmented, is to replace all the pixels in the array in each node with the average color of that segment.

Hopefully I explained that well enough.

I understand a bit better now, thanks.


For the split method, ------

nevermind i'll ttry it myself and update thread

[EZTRAWST]

Having any luck with this? It's a pretty neat idea.

[garywoot]

EZTRAWST @ Tue Apr 09, 2013 6:06 am wrote:

Having any luck with this? It's a pretty neat idea.

well I pretty much finished the assignment yesterday... but one thing: it doesn't work... and i have no idea why (my conceptual understanding of quadtrees is still very shallow so it's hard for me to debug)

i'm hesitant to publicly post my code because i might get a zero for "academic dishonesty" but here is my pseudo code for my constructor & split method

public QuadTree (MyPicture myPic, QuadNode root, int maxLevel, double RedT, double GreenT, double BlueT){
//set attributes to actual parameters passed in
//call helper method this.split(root);



public void split (QuadNode node){
if (!homogeneous (parameters) ){
//make new northeast quadnode
//set node's northeast child to to the new quadnode
this.split(northeast); //this recursively calls this method

//do the same thing for northwest, southwest, southeast
}


public boolean homogeneous (parameters){
blablabla
}

//i'm not sure if this method is right... is this how you check if it's a leaf?
public boolean isLeaf (Quadnode node){
if (node.getLevel() == this.maxLevel){
return true;
}
return false;

}


and then i have my preorder traversal methods, etc... i think these are fine

please don't quote/reply to my post (directly, with the button) so that i can edit some of the code out later... kind of paranoid considering my school uses next level software to check for online duplicates

[garywoot]

Edit by Clayton: Keep the vulgarity out of your posts. Thanks.

[Clayton]

garywoot @ Wed Apr 10, 2013 6:00 am wrote:

*snip*

I understand it's frustrating when you're working on something that doesn't seem to want to work and the deadline is fast approaching, but this is definitely not the attitude to take, especially on these forums. It doesn't help you or anyone else in any fashion. Take a step back and try looking at things from another angle.

[EZTRAWST]

I sent you a message.

[EZTRAWST]

Here's what I've got so far: http://pastebin.com/RQWBGR2z

I would really appreciate some help!

[garywoot]

I finished it, EZTRAWST, are you in the 1027 class?

[EZTRAWST]

Yes! Did you have a look at my code? Am I far off?

[garywoot]

EZTRAWST @ Wed Apr 10, 2013 7:34 pm wrote:

Yes! Did you have a look at my code? Am I far off?

Your drawsegmentation and paintsquares and isLeaf and isHomogeneous is a bit off. for the ishomogeneous, you modified the formula from the website -- don't.

For drawsegmentation and paintsquares (essentially the same thing except you're calling one method different), you have to take in all the nodes from the queue, dequeue them and enqueue them onto a temporary queue, dequeue from the temporary queue and save that in a current of type QuadNode while temp is not empty. then you have to call the drawWhiteSquares method. Then, enqueue current back into queue so you don't destroy that linkedQueue

for isHomogeneous, just copy and paste the formula from the website... don't modify anything

for isLeaf, also check that the other 3 children are null.

for your split, i did it a bit differently but yours should work..

Also, regarding your PM, if you need additional help i will try to check back in this thread tomorrow. I will also be at weldon library fifth floor the whole day tomorrow. I also have a compsci lab at 12:30-1:30 in middlesex college, so if you're in that class, let me know...

[EZTRAWST]

I got it working, thanks for the pointers!

[sarge]

Anyway to see what this final product looks like?