at.ac.sbg.cosy.soccerbot.recognition.splitmerge
Class QuadNode

java.lang.Object
  extended by at.ac.sbg.cosy.soccerbot.recognition.splitmerge.QuadNode

public class QuadNode
extends java.lang.Object

Library for linear (array) representation of quadtree nodes

Author:
Peter Wild

Constructor Summary
QuadNode()
           
 
Method Summary
static int calculateMaxHierarchy(int size)
          Calculates the maximum hierarchy level if image is decomosed using quadtrees.
static int calculateSize(int mayHierarchy)
          Creates a new array of QuadNode int values that can be indexed using the method position() with the Quad_Tree format (quad_h, quad_x, quad_y).
static int child_position(int child_num, int position)
          Returns all child positions (as linear array positions) of a given quadtree node (as linear array position).
static int hierarchyNeighbor(int neighbor_num, int position)
          Calculates the position of neighbor situated at the right/lower/left/upper side of the quadtree node, if it exists, else returns -1 as error value.
static int lowerRight(int position, int imageHierarchy)
          Calculates the lower right coordinate of a quadNode within the observed image.
static int parent_position(int position)
          Returns parent position (as linear array positions) of a given quadtree node (as linear array position).
static int position(int quad_h, int quad_x, int quad_y)
          Conversion Quad_Tree format (quad_h, quad_x, quad_y) -> Linear array.
static int quad_h(int position)
          Reversing the formula from QuadNode.position this calculates the first parameter quad_h of the Quad_Tree format (quad_h, quad_x, quad_y) out of the linear representation.
static int quad_x(int quad_h, int position)
          Reversing the formula from QuadNode.position this calculates the second parameter quad_x of the Quad_Tree format (quad_h, quad_x, quad_y) out of the linear representation.
static int quad_y(int quad_h, int position)
          Reversing the formula from QuadNode.position this calculates the second parameter quad_y of the Quad_Tree format (quad_h, quad_x, quad_y) out of the linear representation.
static int upperLeft(int position, int imageHierarchy)
          Calculates the upper left coordinate of a quadNode within the observed image.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

QuadNode

public QuadNode()
Method Detail

calculateMaxHierarchy

public static int calculateMaxHierarchy(int size)
Calculates the maximum hierarchy level if image is decomosed using quadtrees.

Parameters:
size - > 0, has to be a power of 2 (1,2,4,8,16,32,64,128,256,512) image width of square image
Returns:
maxumum hierarchy of quadtree for full decomposition

calculateSize

public static int calculateSize(int mayHierarchy)
Creates a new array of QuadNode int values that can be indexed using the method position() with the Quad_Tree format (quad_h, quad_x, quad_y).

Parameters:
mayHierarchy - maximum hierarchy
Returns:
array holding full Quad Tree information to a square image of size 2^{maxHierarchy}

position

public static int position(int quad_h,
                           int quad_x,
                           int quad_y)
Conversion Quad_Tree format (quad_h, quad_x, quad_y) -> Linear array. Calculates array position according to formula of geometric series: position = (1 - 4^{quad_h}) / (1 - 4) + quad_x + quad_y * (2^{quad_h}), that is position = #slots_occupied_by_previous_hierarchies + #columns + #lines*line_length.

Parameters:
quad_h - >= 0 Hierarchy level quad_h starting at 0 - whole image
quad_x - >= 0, < 2^{quad_h} Quadtree node raster distance from left (column) x-position quad_x starting at 0 - leftmost
quad_y - >= 0, < 2^{quad_h} Quadtree node raster distance from top (line) y-position quad_y starting at 0 - top
Returns:
Quadtree array position p ( 0 <= p < (1 - 4^{max_h}) / (1 - 4))

quad_h

public static int quad_h(int position)
Reversing the formula from QuadNode.position this calculates the first parameter quad_h of the Quad_Tree format (quad_h, quad_x, quad_y) out of the linear representation. The formula is derived inverting position = (1 - 4^{quad_h}) / (1 - 4) + quad_x + quad_y * (2^{quad_h), since (1 - 4^{quad_h}) / (1 - 4) is monotone ascending and the additional part A = quad_x + quad_y * (2^{quad_h)) can be bounded by 4^{quad_h}.

Parameters:
position - linear array position of quadtree node
Returns:
quad_h for Quad_Tree format

quad_x

public static int quad_x(int quad_h,
                         int position)
Reversing the formula from QuadNode.position this calculates the second parameter quad_x of the Quad_Tree format (quad_h, quad_x, quad_y) out of the linear representation. The formula is derived using position = (1 - 4^{quad_h}) / (1 - 4) + quad_x + quad_y * (2^{quad_h).

Parameters:
quad_h - >= 0 Hierarchy level quad_h starting at 0 - whole image
position - linear array position of quadtree node
Returns:
quad_x for Quad_Tree format

quad_y

public static int quad_y(int quad_h,
                         int position)
Reversing the formula from QuadNode.position this calculates the second parameter quad_y of the Quad_Tree format (quad_h, quad_x, quad_y) out of the linear representation. The formula is derived using position = (1 - 4^{quad_h}) / (1 - 4) + quad_x + quad_y * (2^{quad_h).

Parameters:
quad_h - >= 0 Hierarchy level quad_h starting at 0 - whole image
position - linear array position of quadtree node
Returns:
quad_y for Quad_Tree format

child_position

public static int child_position(int child_num,
                                 int position)
Returns all child positions (as linear array positions) of a given quadtree node (as linear array position). Calculates positions according to the following formula: position -> (quad_h, quad_x, quad_y) -> child 0: (quad_h + 1, 2*quad_x, 2*quad_y) -> child 1: (quad_h + 1, 2*quad_x + 1, 2*quad_y) -> child 2: (quad_h + 1, 2*quad_x, 2*quad_y + 1) -> child 3: (quad_h + 1, 2*quad_x + 1, 2*quad_y + 1)

Parameters:
child_num - >= 0, < 4 child number
position - linear array position of quadtree node to which childs are to be calculated
Returns:
linear array position of child child_num

parent_position

public static int parent_position(int position)
Returns parent position (as linear array positions) of a given quadtree node (as linear array position). Calculates position according to the following formula: position -> (quad_h, quad_x, quad_y) -> parent: (quad_h - 1, ceil(quad_x/2), ceil(quad_y/2))

Parameters:
position - linear array position of quadtree node to which parent is to be calculated
Returns:
linear array position of parent

upperLeft

public static int upperLeft(int position,
                            int imageHierarchy)
Calculates the upper left coordinate of a quadNode within the observed image.

Parameters:
position - linear array position of quadtree node to which image coordinate is to be calculated
imageHierarchy - Level, at which the image is contained (for which it starts at index 0)
Returns:
upper left pixel coordinate (starting at upper left index 0) where QuadNode starts

lowerRight

public static int lowerRight(int position,
                             int imageHierarchy)
Calculates the lower right coordinate of a quadNode within the observed image.

Parameters:
position - linear array position of quadtree node to which image coordinate is to be calculated
imageHierarchy - Level, at which the image is contained (for which it starts at index 0)
Returns:
lower right pixel coordinate (starting at upper left index 0) where QuadNode ends

hierarchyNeighbor

public static int hierarchyNeighbor(int neighbor_num,
                                    int position)
Calculates the position of neighbor situated at the right/lower/left/upper side of the quadtree node, if it exists, else returns -1 as error value.

Parameters:
neighbor_num - >= 0, < 4 neighbor number (0: right, 1: lower, 2: left, 3: upper)
position - linear array position of quadtree node to which image coordinate is to be calculated
Returns:
linear array position of neighboring node at the same hierarchy level