P System Implementation of Dynamic Programming Stereo
Designing parallel versions of sequential algorithms has attracted renewed attention, due to recent hardware advances, including various general-purpose multi-core and many-core processors, as well as special-purpose FPGA implementations. Psystems consist of networks of autonomous cells, such that each cell transforms its input signals in accord with its symbol-rewriting rules and feeds the output results into its immediate neighbours. Inherent massive intra- and inter-cell parallelisms make P systems a prospective theoretical testbed for designing efficient parallel and parallel-sequential algorithms. This paper discusses the capabilities of P systems to implement the symmetric dynamic programming stereo (SDPS) matching algorithm, which explicitly accounts for binocular or monocular visibility of 3D surface points. Given enough cells, the P system implementation speeds up the inner algorithm loop from O(nd) to O(n+d), where n is the width of a stereo image and d is the disparity range. The implementation gives also an insight into a more general SDPS that accounts for a possible multiplicity of solutions of the ill-posed problem of optimal stereo matching.
symmetric dynamic programming stereo (sdps) stereo matching parallel systems membrane computing