How to searching for in kdtree when dynamic elements are considered

Paul Harris paulharris at computer.org
Mon Nov 16 23:37:09 UTC 2009


Hi Jsl,

I'm not sure exactly what you are talking about, but if all you are doing is
transformations, then what I would do is *when* you are querying the tree,
transform the query location into the coordinate system of the tree.

eg, you build the tree with the plain image ABC, let the tree coordinate
system be X,Y

then you want to find a point close to x,y then you search for X,Y=x,y

if you then transform image ABC by adding 10 to y... so therefore X=x Y=y-10
where X,Y are the tree coordinates, and x,y are the transformed coordinates.

Then if you want to find a point (21,56), then you transform into tree
coords : (21,46) and then search.
remember, X=x, Y=y-10   so X=21, Y=56-10

any rotation, translation etc can reversed.  matrix multiplications make
this simple and quick to do.

that way you can avoid rebuilding the tree with each iteration, which would
be expensive.

cheers
Paul

2009/11/17 jsl n <jsantam.hm at hotmail.com>

>  Hi,
>
>    I'm using kdtree for searching for the closest point between two images.
> The kdtree stores the points of one (fixed) of the two images and the
> second
> one is iteratively transformed (rotated, translated, etc). The closest
> point is
> computed for each moved point each iteration.
>
> This is the procedure, but, what happen if the fixed image (the one that
> the
> kdtree stores) is also transformed each iteration? should I build a new
> kdtree
> each iteration? I need to know if there is an efficient solution for this
> dynamic
> situations where all the image points (of the fixed image) are transformed
> in
> the same way.
>
> Thanks in advance.
>
> ------------------------------
> 49 habitantes, 49 expertos en Windows 7. Así es Sietes, ¡Visítalo!<http://www.sietesunpueblodeexpertos.com/>
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20091117/b42fadae/attachment.htm>


More information about the libkdtree-devel mailing list