M.Sc Thesis

M.Sc StudentMakhervaks Vadim
SubjectImage Flows and One-Liner Graphical Image Representation
DepartmentDepartment of Applied Mathematics
Supervisors PROF. Alfred Bruckstein
PROF. Gill Barequet


This thesis introduces a novel graphical image representation comprising a single curve - the one-liner. Building one-liner representation consists of several steps. The first step involves the detection and linking of the image edges. We use a new technique to simultaneously perform both tasks. We refer to this technique as edge exploration. This process is based on the concept of "image flows." It uses the image-gradient vector field and a new edge-exploration operator to find and rank image edges. Estimating the derivatives of the image is performed by using local Taylor expansions in conjunction with a weighted least-squares estimation method. The edge-exploration process finds all the possible image edges without any pruning. During this process we also collect information that allows to prioritize the found detected edges; enabling us to select the most important edges of the image. The set of selected edges provides the frame for the subsequent one-liner representation. The next step consists of connecting the image selected edges into a single continuous curve the "one-liner." This step involves the ordering of the selected edges and  finding curves connecting them. We solve these two problems separately. We prove that an abstract graph setting of the first problem is NP-Complete. However, we reduce this problem to a variant of the Euclidean Traveling Salesman Problem (TSP) and compute an approximate solution to it by using a readily-available TSP solver. We solve the problem of finding connection curves by using Dijkstra's famous shortest-path algorithm. A full software implementation for the entire one-liner determination process enabled us to extensively experiment with various input images. The thesis provides several representative one-liner examples and statistics on running the software on various inputs.