Premium
Image Flows and One‐Liner Graphical Image Representation
Author(s) -
MAKHERVAKS VADIM,
BAREQUET GILL,
BRUCKSTEIN ALFRED
Publication year - 2002
Publication title -
annals of the new york academy of sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.712
H-Index - 248
eISSN - 1749-6632
pISSN - 0077-8923
DOI - 10.1111/j.1749-6632.2002.tb04547.x
Subject(s) - dijkstra's algorithm , image (mathematics) , representation (politics) , algorithm , pruning , mathematics , process (computing) , edge detection , enhanced data rates for gsm evolution , graph , pyramid (geometry) , shortest path problem , image processing , computer science , artificial intelligence , combinatorics , geometry , agronomy , politics , political science , law , biology , operating system
A bstract : This paper introduces a novel graphical image representation consisting of a single curve—the one‐liner. The first step of the algorithm involves the detection and ranking of image edges. A new edge exploration technique is used to perform both tasks simultaneously. This process is based on image flows . It uses a gradient vector field and a new operator to explore image edges. Estimation of the derivatives of the image is performed by using local Taylor expansions in conjunction with a weighted least‐squares method. This process finds all the possible image edges without any pruning, and collects information that allows the edges found to be prioritized. This enables the most important edges to be selected to form a skeleton of the representation sought. The next step connects the selected edges into one continuous curve—the one‐liner. It orders the selected edges and determines the curves connecting them. These two problems are solved separately. Since the abstract graph setting of the first problem is NP‐complete, we reduce it to a variant of the traveling salesman problem and compute an approximate solution to it. We solve the second problem by using Dijkstra's shortest‐path algorithm. The full software implementation for the entire one‐liner determination process is available.