A minimal line property preserving representation of line images

In line image understanding a minimal line property preserving (MLPP) graph of the image compliments the structural information in geometric graph rep resentations like the run graph. With such a graph and its dual it is possi ble to efficiently detect topological features like loops and holes and to make use of relations like containment. We present a new rule based method on dual graph contraction for transforming the run graph and its dual into MLPP graphs. A parallel O(log(longest curve)) algorithm is presented and re sults given.