Abstract
This thesis is concerned with the mathematical aspects related to the optimal cutting of an object whose three-dimensional shape has been accurately and robustly reconstructed using appropriately developed computer-vision tools. First, a brief introduction to various one- and two-dimensional packing problems is presented. The Constrained Rectangle Packing problem which allows for defects to be modeled is then formulated and an efficient algorithm for solving it is presented. The two-stage stock-cutting problem according to which a set of rectangular pieces of prespecified dimensions are to be cut from a general shape object with general shape holes or defective regions is then investigated. It is shown how mathematical morphological operators can be vised in order to determine the optimal shifting for a given cutting pattern and proved that the problem of obtaining the optimal cutting pattern is NP-hard. However, the optimal solution to the unconstrained problem using mathematical programming is proposed. For the general problem good sub-optimal solutions are obtained using the technique of simulated annealing. Stereo-vision techniques are then employed for the accurate shape determination of the object to be cut. A three-dimensional reconstruction technique based on projective geometry is formally analysed and guidelines for its robust application are given. Finally, emphasis is placed on the correspondence problem, which becomes very difficult in the case of non-coplanar features and cameras set at 90 degrees from each other. It is shown how to cast the problem into an optimisation framework and a branch and bound algorithm is used in order to obtain the optimal solution. For increased robustness a Hough-Transform-like algorithm is also suggested. Both synthetic and real experimental results are presented throughout the thesis in order to illustrate the validity and usefulness of the proposed algorithms.