Towards structural analysis of solution spaces for ill-posed discrete 1D optimisation problems

To obtain a single best-suited solution, an ill-posed global optimisation problem is regularised. Conventional regularisation, that adds to the goal function a weighed smoothing term, is theoretically justified for linear and a number of non-linear ill-posed mathematical problems. But for inverse optical problems in computer vision such regularisation is mostly heuristic and thus guarantee neither unique, nor visually valid solution. Our recent concurrent propagation algorithm forms and stores in a compact graphical form an entire solution space for an one-dimensional (1D) discrete global optimisation, being ill posed due to a multiplicity of solutions. We discuss possibilities of guiding the selection of a valid solution by structural properties of the solution space. In application to ill-posed computational stereo vision, to match human 3D perception, the regularised solutions should keep boundaries of objects producing partially occluded regions of an observed 3D scene. Experiments with real stereo pairs show that a sizeable part of such boundaries and regions can be detected by analysing the entire solution space.