Hello all, I am a new guy and this is my first post.

I am a reseracher in GIS/CS in Perth, West Oz and I work specifically with spatial data structures. I have been programming all my stuff in C (and later in C++) under both Unix and Windows. It occured to me that many of my algorithms dealt with bit manipulation which led me to thinking in terms of asm, which led me to this forum. An example of the type of stuff I am dealing with follows:

A linear quadtree (lqt) node of level 0 is a unit level pixel, level 1 = 2x2 pixels, level 2 = 4x4, etc. You can see then, that an lqt is a means by which to compress 2D images by accumulating homogeneous regions into square tiles. The structures that I have been developing explicitly insert edge information into these essentailly raster structures. Which means that I must account for this edge information when perfoming a boolean operation such as union or intersection on two images stored in my hybrid lqt format.

A traditional lqt node has this structure (with possible variations): colour | level stored as a two byte pair.
My idea was to modify this structure to encode edge information so I split the level byte into two 4 bit regions:
level | edge. The new structure now looks like this colour | (level | edge). As an example the binary rep of the NW corner of a BLACK region (which has both north and west bits set) and covers an 8x8 tile looks like this:

0000000100110011

where
00000001 = BLACK
0011 = level 3 (ie 4^3 = 8)
0011 = NW (in the scheme SENW)

If I have two input streams (2 edge encoded qts) I need to assess the edge patterns for valid aggregation. By this I mean, if 4 quadrants can be validly promoted to a higher level, that is, say four level 2 tiles into one level 3 tile, I must do so otherwise the output lqt would be sub-optimal.

To demonstrate a valid promotion (assume colour is the same):
Q1 Q2 Q3 Q4
level 2: 0011 0110 1001 1100 <--edge patterns

To demonstrate an invalid promotion (assume colour is the same):
Q1 Q2 Q3 Q4
level 2: 1111 0110 1001 1100 <--edge patterns

The algorithm I use is this:

if ( ( Q1( val ) ADD ( Q4 ( val ) ) AND ( ( Q2( val ) ADD ( Q3 ( val ) ) )
NodeAgg( Current node, Level++, edges = ( Q1( val ) ADD ( Q4 ( val ) )
else
Output( Q1, Q2, Q3, Q4 )

So in example 1 we have 15 = 15 so NodeAgg is called
but in example 2 we have 27 != 15 so the Output function is called.

I am new to asm programming and ask advice on how best to code this algorithm.

Thnx (and I apologise for being so windy)
rob

:)
Posted on 2002-08-05 03:49:21 by gisgeek
if ( ( Q1( val ) ADD ( Q4 ( val ) ) AND ( ( Q2( val ) ADD ( Q3 ( val ) ) )

I am presuming
Q1(val) == 0011b
Q2(val) == 0110b
Q3(val) == 1001b
Q4(val) == 1100b

Hence
Q1( val ) ADD ( Q4 ( val ) == 1111b
Q2( val ) ADD ( Q3 ( val ) == 1111b
1111b AND 1111b == 1111b -> This is non zero - hence true!

In the invalid case:
Q1(val) == 1111
Q2(val) == 0110
Q3(val) == 1001
Q4(val) == 1100
Q1( val ) ADD ( Q4 ( val ) == 11011b
Q2( val ) ADD ( Q3 ( val ) == 01111b
11011b AND 01111b = 1011b -> This is non zero - hence true!

They both follow the same code path? I thought that second case was invalid?
Is there is an additional case in the if for the overflow (ie A + B is greater than 4 bits long)?

Or am I missing something here?

Mirno
Posted on 2002-08-05 05:56:30 by Mirno
gisgeek, I assume you mean == instead of AND, given your following statement.
if ( ( Q1( val ) ADD ( Q4 ( val ) ) [b]==[/b] ( ( Q2( val ) ADD ( Q3 ( val ) ) ) 

NodeAgg( Current node, Level++, edges = ( Q1( val ) ADD ( Q4 ( val ) )
else
Output( Q1, Q2, Q3, Q4 )

So in example 1 we have 15 = 15 so NodeAgg is called
but in example 2 we have 27 != 15 so the Output function is called.

It is hard to say much more than this:
   mov eax, Q1.val

mov edx, Q2.val
add eax, Q4.val
add edx, Q3.val

cmp eax, edx
jne output

inc level
invoke current_node, level, edx
jmp continue

output:
invoke Output, Q1, Q2, Q3, Q4
continue:
Posted on 2002-08-05 08:05:25 by bitRAKE
Thank you both for taking the time,

And yes Mirno I mistakenly used AND where == was required. (which would handle the possible overflow that you pointed out)

Thanks bitRake for the solution. I'll try to make the next question more challenging.

cheers

rob
:alright:
Posted on 2002-08-05 08:49:54 by gisgeek
Is this fractal compression you doing?
Posted on 2002-08-05 08:57:05 by bitRAKE
No, the compression isn't (necessarily) fractal, though there have been fractal methods applied to region quadtrees. The authors maintain that their solution provides "infinite" resolution but I suspect that this is a bit perpetual motion engine. Having said that, I admit that they have investigated and interesting line of work. Unfortunately the compression is lossy which is unsuitable for spatial science.

I am, however, investigating the Hausdorff fractal dimension as a tool to analyse spatial access methods based the regular decomposition of space such as Morton order (also known as Z ordering) (Faloutsos and Gaede: reference if you are interested). Also, there is value in fractal techniques as a complexity measure (ie shape analysis).

Cheers (windy again)
rob
Posted on 2002-08-05 09:54:45 by gisgeek
I've seen something similar used to generate octrees , mapping 3d space
in terms of three quadtrees, being the triaxial planes xz, xy,zy
I thought it was brilliant. Forget where I saw it though
:tongue: strange what sticks, aint it.
Posted on 2002-08-15 01:50:09 by Homer
I've seen wavelets do lossless compression,

wavelets dont work well on artificial type images, but would be perfect for image, terrain compression.

As far as i remember (never actually written any code for this - all theory :) for lossless you dont discard any of the co-efficients after the transform.


Quality is far better than jpeg at the same file size (for lossy compression)
Posted on 2002-08-15 11:52:39 by Terab