A Lower-Bound Cascade for Lossless Pruning in Levenshtein-Based Contour Matching
Fragment książki (Rozdział monografii pokonferencyjnej)
MNiSW
5
spoza wykazu
| Status: | |
| Autorzy: | Skulimowski Stanisław |
| Dyscypliny: | |
| Aby zobaczyć szczegóły należy się zalogować. | |
| Wersja dokumentu: | Drukowana | Elektroniczna |
| Język: | angielski |
| Strony: | 71 - 84 |
| Efekt badań statutowych | NIE |
| Materiał konferencyjny: | TAK |
| Nazwa konferencji: | Prague Stringology Conference 2026 |
| Skrócona nazwa konferencji: | PSC 2026 |
| URL serii konferencji: | LINK |
| Termin konferencji: | 24 sierpnia 2026 do 25 sierpnia 2026 |
| Miasto konferencji: | Prague |
| Państwo konferencji: | CZECHY |
| Publikacja OA: | TAK |
| Licencja: | |
| Sposób udostępnienia: | Inne |
| Wersja tekstu: | Ostateczna wersja opublikowana |
| Czas opublikowania: | W momencie opublikowania |
| Data opublikowania w OA: | 24 sierpnia 2026 |
| Abstrakty: | angielski |
| Contour-based reassembly of fragmented two-dimensional objects requires a large number of Levenshtein comparisons between directional chain-code strings. This paper proposes a lossless pre-filtering strategy based on four lower bounds: string length, symbol-frequency histogram, signed directional turn histogram, and g-gram hit count. Candidates are rejected only when a bound proves that their distance must exceed the threshold; otherwise, exact verification is preserved. Experiments covered seeded synthetic strings, exhaustive whole-space validations, and real Afrosiyab relief contour data. No false negatives were observed in any tested configuration. In representative generated tests, survival decreased to 0.160%, reducing exact verification by 99.840% and yielding a 4.05× speedup. Real-data experiments confirmed strong parameter- dependent pruning under a redundancy-free unordered window-pair evaluation, with histogram filtering dominating equal-window settings. |
