Jag accepterar att kakor lagras på min dator

Läs mer

Improving the primal-dual algorithm for the transportation problem in the plane.

Improving the primal-dual algorithm for the transportation problem in the plane. Beställ tryckt exemplar Lägg i kundvagnen
Författare: Kaijser Thomas
Ort: Linköping
Sidor: 55
Utgivningsår: 2000
Publiceringsdatum: 2000-03-16
Rapportnummer: (FOA-R--99-01379-504)
Nyckelord transportproblemet i planet, primaldualalgoritmen, Kantorovichavståndet, bildavstånd, euclidean transportation problem, primal-dual algorithm, search reduction, Kantorovich metric, 76, E7007
Sammanfattning Transportproblemet i planet - hur man på billigaste sätt förflyttar en samling föremål från en lokalisering i planet till en annan lokalisering i planet - är ett flera hundra år gammalt problem. De senaste åren har lösningen till detta problem funnit tillämpning inom bildanalysen speciellt för att upptäcka likheter och skillnader mellan bilder. En stor nackdel i detta sammanhang är dock den långa beräkningstiden. I denna uppsats presenteras några nya resultat med vars hjälp beräkningstiden för att finna lösningen till transportproblemet i planet kan reduceras avsevärt. Som kostnadsfunktion har använts en avståndsfunktion för punkter i planet, nämligen dels det vanliga euklidiska avståndet, dels kvadraten på det euklidiska avståndet. Den sistnämnda avståndsfunktionen har den fördelen att den är heltalsvärd för punkter i planet vars koordinater är heltal.
Abstract The transportation problem in the plane - how to move a set of objects from one set of points to another set of points in the cheapest way - is a very old problem going back several hundreds of years. In recent years the solution of the problem has found applications in the analysis of digital images when searching for similarities and discrepancies between images. The main drawback, however, is the long computation time for finding the solution. In this paper we present some new results by which the time for solving the transportation problem in the plane can be reduced substantially. As cost-function we choose a distancefunction between points in the plane. We consider both the case when the distance-function is equal to the ordinary Euclidean distance, as well as the case when the distance-function is equal to the square of the Euclidean distance. This latter distance-function has the advantage that it is integer-valued if the coordinates of the points in the plane are integers.

Kundvagn

Inga rapporter i kundvagnen

FOI, Totalförsvarets forskningsinstitut

FOI
Totalförsvarets forskningsinstitut
164 90 Stockholm

Tel: 08-555 030 00
Fax: 08-555 031 00

Orgnr: 202100-5182