On Chamfer Distances on the Square and Body-Centered Cubic Grids: An Operational Research Approach

Abstract

Linear programming is used to solve optimization problems. Thus, finding a shortest path in a grid is a good target to apply linear programming. In this paper, specific bipartite grids, the square and the body-centered cubic grids are studied. The former is represented as a diagonal square grid having points with pairs of either even or pairs of odd coordinates (highlighting the bipartite feature). Therefore, a straightforward generalization of the representation describes the body-centered cubic grid in 3D. We use chamfer paths and chamfer distances in these grids; therefore, weights for the steps between the closest neighbors and steps between the closest same type points are fixed, and depending on the weights, various paths could be the shortest one. The vectors of the various neighbors form a basis if they are independent, and their number is the same as the dimension of the space studied. Depending on the relation of the weights, various bases could give the optimal solution and various steps are used in the shortest paths. This operational research approach determines the optimal paths as basic feasible solutions of a linear programming problem. A directed graph is given containing the feasible bases as nodes and arcs with conditions on the used weights such that the simplex method may step from one feasible basis to another one. Thus, the optimal bases can be determined, and they are summarized in two theorems. If the optimal solution is not integer, then the Gomory cut is applied and the integer optimal solution is reached after only one Gomory iteration. Chamfer distances are frequently used in image processing and analysis as well as graphics-related subjects. The body-centered cubic grid, which is well-known in solid state physics, material science, and crystallography, has various applications in imaging and graphics since less samples are needed to represent the signal in the same quality than on the cubic grid. Moreover, the body-centered cubic grid has also a topological advantage over the cubic grid, namely, the neighbor Voronoi cells always share a full face.