This paper present a high-level recognition algorithm that allows for complete interspersing freedom, running in real-time through effective sub-tree pruning. Shapes are indexed as they are drawn using geometric properties and are inserted into hash table. This allows us to search quickly for all possible subsets of shapes facilitating higer level recognition.
Indexing Algorithm:
1. Domain-independent primitive recognition: uses Sezgin paper
2. Domain independent constraint indexing : All shapes are inserted into hash tables based on their geometric properties as soon as they are drawn or recognized.
3. High-level recognition: Each time a new line is drawn system checks if it can be part of any known shape built from it and all previous lines. It does this by putting the new line in each possible slot in each template, putting all uninterpreted previously drawn lines in other slots and treating problem as constraint satisfaction problem with geometric constraints refining values
Speedup of algo due to:
1. Heavy computing is performed in indexing stage(linear)
2. Subtrees are pruned as they are generated
3. Smart ordering of constraints.
Two tests were conducted
Stress Test
Multi domain test
My thoughts:
The idea of using hash table to store all shapes with similar properties is very innovative.
Indexing Algorithm:
1. Domain-independent primitive recognition: uses Sezgin paper
2. Domain independent constraint indexing : All shapes are inserted into hash tables based on their geometric properties as soon as they are drawn or recognized.
3. High-level recognition: Each time a new line is drawn system checks if it can be part of any known shape built from it and all previous lines. It does this by putting the new line in each possible slot in each template, putting all uninterpreted previously drawn lines in other slots and treating problem as constraint satisfaction problem with geometric constraints refining values
Speedup of algo due to:
1. Heavy computing is performed in indexing stage(linear)
2. Subtrees are pruned as they are generated
3. Smart ordering of constraints.
Two tests were conducted
Stress Test
Multi domain test
My thoughts:
The idea of using hash table to store all shapes with similar properties is very innovative.
Yes the idea of indexing and pruning is really nice and it is saving a lot of time over traditional approach to match infinitely many combinations of different sub shapes.
ReplyDelete