Skip to content

Several LCA implementations for faster saliency map

Baptiste Esteban requested to merge development/lca_epti into next

Implementation of the linear LCA algorithm described in The LCA Problem Revisited by Michael A. Bender and Martın Farach-Colton. This LCA is faster on hierarchies built on edge images, such as ones preprocessed by a Canny.

  • Implementation of a naive LCA as a functionality of the library and not only for the saliency map
  • Implementation of a base LCA, computing the Euler tour
  • Implementation of a templated class taking into parameter a RMQ algorithm
  • Implementation of the Sparse Table based RMQ (preprocessing in O(n log(n)) and query in O(1))
  • Implementation of the Linear RMQ (preprocessing in O(n) and query in O(1))
  • Implementation of a type erased LCA, used in the saliency map algorithm to choose at runtime the LCA to use, depending to the use case
  • Multiple LCA saliency map
  • Update documentation of the saliency map + add new page about the LCA algorithms proposed
  • Make tests
  • Make benchs
Edited by Baptiste Esteban

Merge request reports