Member Avatar for jemimaloh

I'm doing a project on geometric hashing. Of which i am unsure about the basis generation (meaning, finding only a pair coordinates that coincide with the X-axis) from all the invariant points in the coordinate file of a given 2D model which would have been hashed already. This case being, we could also orientate the model in space further, so that all 2D models in the database can be automatically go through an appropriate offset.

Your help is greatly appreciated.

Edited by jemimaloh because: n/a
  • 3 Contributors
  • 5 Replies
  • 128 Views
  • 1 Week Discussion Span
  • Latest Post Latest Post by jemimaloh

Dani AI

Generated

A compact, practical guide to generate 2D bases from model invariant points and what to watch for when you implement geometric hashing.

has the right theory background; the key engineering steps are stable basis selection, consistent coordinate projection, quantization for noise tolerance, and efficient storage of the basis descriptor. asked for code-level detail and pointed toward background reading — below are concrete, implementable points you can turn into Java.

  • Basis construction: pick an ordered pair (A, B). Use A as the origin and the unit vector from A to B as the X axis; take the perpendicular as Y. Skip any pair with distance < epsilon (numeric instability) or pairs that are too close compared to noise.
  • Projection: for every model point P compute coordinates relative to that frame: x = dot(P - A, Xunit); y = dot(P - A, Yunit). Use these (x,y) plus the point label when making a hash key.
  • Quantization and hashing: quantize x,y by a cell size tuned to expected localization error. Pack quantized x,y,label into a compact integer/long key and insert the tuple (modelID, basisDescriptor) into the hash table.
  • Recognition: do the same for query bases, accumulate votes per (modelID,basisDescriptor), then for top hypotheses compute the rigid transform implied by the two frames and refine with a small ICP/Procrustes fit if needed.

Practical tips and cautions: choose a minimum separation to avoid degenerate bases; limit the number of bases per model (randomly or by distance ranking) to control memory; to handle reflections either store both orientations or include orientation bits in the key; tune cell size experimentally with synthetic rotated/noisy queries. For Java, favor primitive arrays and packed integer/long keys, reuse preallocated objects, and use a high-performance primitive map (or a single large array with chaining) to reduce GC overhead.

Recommended Answers

All 5 Replies

Member Avatar for NormR1

Do you have the algorithm that you want to write in Java?
Once you get that, someone can help you with your problems coding it.

Member Avatar for jemimaloh

Yups. Geometric hashing is the algorithm that i am using.
There's a preprocessing and a recognition phase.

preprocessing:

var
Mu the Model structure
H the hash table
F the hash function
Pl the label of atom Ap

begin
for each model Mu
do
for each (ordered, noncollinear) triple (ai, ak,ar) extracted from Mu
do calculate the reference frame Rikr
for each atom p extracted from Mu
do calculate F = F (Rikr, Ap, Pl);
H(F)U(Mu, Rikp)
end
end
end
end


recognition phase:

Compare the query structure with each model structure in the hash table
var
v two-dimensional vote table
H the hash table
F the hash functiion
qL the label of atom Aq
M the model structure
R a reference frame

begin
repeat
initialize the vote table V to 0
choose 3 atoms (Bj, Bl, Bs) in the query as basis,
defining the reference frame Rjls
for each atom q in the query do
calculate F = F(Rjls, Bq, Ql)
for each pair (M, R) in reference H(F)
do V ( M, R) := V(M, R) + 1
end
until satisfactory conincidence set is found or all queries ref. frames are used.
end


Excerpt from Protein bioinformatics: an algorithm approach to sequence and structure analysis I. Eidhammer, I.Jonassen, and W.R. Taylor copyright 2004 John Wiley & Sons, Ltd ISBN: 0-470-84839-1


If anyone could even explain to me just a segment of it, I'll be really really grateful. Thanks!

Member Avatar for NormR1

You're going to have to make some effort to code it.
For example what is the code for this statement:
do calculate F = F (Rikr, Ap, Pl);
or this:
calculate F = F(Rjls, Bq, Ql)
or this:
do V ( M, R) := V(M, R) + 1

Member Avatar for Taywin

You do not understand how the algorithm go or you do not understand how to apply Java to it??? If you do not understand the algorithm, you could look at wikipedia. If you do not know how to apply Java to the algorithm, that may need a little more work for you.

Member Avatar for jemimaloh

I don't know how to apply java to it but i am quite sure that i understand the algorithm cause I've read 20 over PDFs on it..

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.