Advanced Programming I Lecture Notes

25 April 2006 • Assignment 6 Code Review

Outline

• The problem.

• Some solutions.

• Testing

• Results

• Coding observations.

Geometric Hashing

• Geometric hashing is used in computer vision systems.

  • Recognize 3d objects in 2d images.

  • Generalized to other pattern-matching problems.

• Other problems not dealt with:

  • Imprecise geometric relations among points.

  • Extra data or spurious points.

The Problem

• The problem itself is relatively simple.

• The devil is in the details.

  • Geometric algorithms and special cases.

  • Floating-point numbers and comparisons.

  • Probabilistic algorithms and fuzzy reasoning.

The Hash Table

• Use either a hash table or a Bloom filter.

  • A Bloom filter has collision problems.

    • Use a higher-order Bloom filter.

  • A hash table also collides, but colliding points can be compared.

• The table size is ×2 or ×3 the larger number of points.

The Hash Function

• Hash both coordinates into an index.

  • Also distinguish between (a, b) and (b, a).

• Use dual hash functions.

  unsigned point::hash()
    return round(x*101)*round(y*97)
  
  template <typename T>
  unsigned hash_table::hash(const T & e)
    return e.hash() % size
  

A Good Hash?

• Maybe; probably not.

XOR Hashing

• Somebody told me that XOR (exclusive or) hashing was good.

  • Exclusive or: one or the other, but not both.

    XOR	0	1
    0	0	1
    1	1	0

• XOR bytes together, rather than adding or multiplying.

XOR Hashes

• (x*101 ^ y*97) % B.

Low-Order Bits

• Somebody told me that low-order bits tend to be less random than higher-order bits.

  • Fewer partial sums are involved.

  • Factors of 2 or 5.

• Get better results by throwing away some of the low-order bits.

Does It?

• (round(x*101)*round(y*97))/256 % B.

Does It?

• (round(x*101)*round(y*97))/2 % B.

Linear Congruential Hashing

• Use a random-number generator.

  unsigned point::random(double k)
    return (M*static_cast(k*11) + a) % s
  
  unsigned point::hash()
    return random(x)*random(y);
  
  template <typename T>
  unsigned hash_table(const T & e)
    return e.hash() % size
  

Linear Congruential Results

• M = 25173, a = 13849, s = 65536.

Other Verifications

• The eye and brain are good at picking out patterns.

• Plotting is good for recognizing bad hashes.

  • But not so good at recognizing good ones.

• Use other mathematical techniques for checking randomness.

• And don't forget that it's data dependent.

Coordinate Hashes

• Use two hash tables, one for each coordinate.

  • Storing (a, b) and (c, d) finds (a, d) and (c, b).

  • Store a tag in each table for each point.

    • Why not hash on the tag?

• Use two hash functions in a single table.

  • Same problem more severely due to higer load factors.

    • Adjustable via table size.

Test Cases

• Empty test.

• One- and two-point test.

• Scaled and rotated L test.

• Italic and bigger U test.

Test Results

	Tests
	1	2	3	4	5	6	7
1
2
3
4
5
6

Coding Notes

• Don't write a lot of code.

• Comment well.

Code Size

• Writing a lot of code is bad.

  • It takes time and effort.

  • It increases the chances of errors.

  files		3	5	5	7	6	5
  lines		309	446	440	647	997	549
  semicolons		122	152	181	234	321	207

Write Useful Comments

• Don't write comments that waste your time and the reader's time.

  // Assignment operator
  HashTable& operator=(const HashTable &)
  
  // Insert Function
  bool Insert(char*, char*, double, double)
  
  // Delete Function
  bool Delete(double, double)
  
  // Find Function
  bool Find(char*, char*, double, double, int &)
  
  

References

• Geometric Hashing: An Overview by Haim Wolfson and Isidore Rigoutsos in IEEE Computation in Science and Engineering, October-December 1997.