This thesis processes the work of developing CPU code and GPU code for Thomas Kaijsers algorithm for calculating the kantorovich distance and the performance between the two is compared. Initially there is a rundown of the algorithm which calculates the kantorovich distance between two images. Thereafter we go through the CPU implementation followed by GPGPU written in CUDA. Then the results are presented. Lastly, an analysis about the results and a discussion with possible improvements is presented for possible future applications.

The goal of this thesis is to study the use of the Kantorovich-Rubinstein distance as to build a descriptor of sample complexity in classification problems. The idea is to use the fact that the Kantorovich-Rubinstein distance is a metric in the space of measures that also takes into account the geometry and topology of the underlying metric space. We associate to each class of points a measure and thus study the geometrical information that we can obtain from the Kantorovich-Rubinstein distance between those measures. We show that a large Kantorovich-Rubinstein distance between those measures allows to conclude that there exists a 1-Lipschitz classifier that classifies well the classes of points. We also discuss the limitation of the Kantorovich-Rubinstein distance as a descriptor.

Apresentamos o problema do transporte ótimo de Monge-Kantorovich com duas medidas de probabilidade conhecidas e que possuem suporte em um conjunto de cardinalidade finita. O objetivo é determinar condições que permitam construir um acoplamento destas medidas que minimiza o valor esperado de uma função de custo conhecida e que assume valor nulo apenas nos elementos da diagonal. Apresentamos também um resultado relacionado com a solução do problema de Monge-Kantorovich em espaços produto finitos quando conhecemos soluções para o problema nos espaços marginais. / We present the Monge-Kantorovich optimal problem with two known probability measures on a finite set. The objective is to obtain conditions that allow us to build a coupling of these measures that minimizes the expected value of a cost function that is known and is zero only on the diagonal elements. We also present a result that is related with the solution of the Monge-Kantorovich problem in finite product spaces in the case that solutions to the problem in the marginal spaces are known.

Abordamos o problema do transporte otimo de Monge-Kantorovich no caso em que o custo e dado pelo quadrado da distância. Tal custo tem uma estrutura que permite a obtenção de resultados mais ricos do que o caso geral. Nosso objetivo e determinar se h a soluções para tal problema e caracteriza-las. Al em disso, tratamos informalmente do problema de transporte otimo para um custo geral. / We analyze the Monge-Kantorovich optimal transportation problem in the case where the cost function is given by the square of the Euclidean norm. Such cost has a structure which allow us to get more interesting results than the general case. Our main purpose is to determine if there are solutions to such problem and characterize them. We also give an informal treatment to the optimal transportation problem in the general case.

Abordamos o problema do transporte otimo de Monge-Kantorovich no caso em que o custo e dado pelo quadrado da distância. Tal custo tem uma estrutura que permite a obtenção de resultados mais ricos do que o caso geral. Nosso objetivo e determinar se h a soluções para tal problema e caracteriza-las. Al em disso, tratamos informalmente do problema de transporte otimo para um custo geral. / We analyze the Monge-Kantorovich optimal transportation problem in the case where the cost function is given by the square of the Euclidean norm. Such cost has a structure which allow us to get more interesting results than the general case. Our main purpose is to determine if there are solutions to such problem and characterize them. We also give an informal treatment to the optimal transportation problem in the general case.

Abordamos o problema do transporte otimo de Monge-Kantorovich no caso em que o custo e dado pelo quadrado da distância. Tal custo tem uma estrutura que permite a obtenção de resultados mais ricos do que o caso geral. Nosso objetivo e determinar se h a soluções para tal problema e caracteriza-las. Al em disso, tratamos informalmente do problema de transporte otimo para um custo geral. / We analyze the Monge-Kantorovich optimal transportation problem in the case where the cost function is given by the square of the Euclidean norm. Such cost has a structure which allow us to get more interesting results than the general case. Our main purpose is to determine if there are solutions to such problem and characterize them. We also give an informal treatment to the optimal transportation problem in the general case.

Apresentamos o problema do transporte ótimo de Monge-Kantorovich com duas medidas de probabilidade conhecidas e que possuem suporte em um conjunto de cardinalidade finita. O objetivo é determinar condições que permitam construir um acoplamento destas medidas que minimiza o valor esperado de uma função de custo conhecida e que assume valor nulo apenas nos elementos da diagonal. Apresentamos também um resultado relacionado com a solução do problema de Monge-Kantorovich em espaços produto finitos quando conhecemos soluções para o problema nos espaços marginais. / We present the Monge-Kantorovich optimal problem with two known probability measures on a finite set. The objective is to obtain conditions that allow us to build a coupling of these measures that minimizes the expected value of a cost function that is known and is zero only on the diagonal elements. We also present a result that is related with the solution of the Monge-Kantorovich problem in finite product spaces in the case that solutions to the problem in the marginal spaces are known.

<p>A transportation plan is a byproduct from the calculation of the Kantorovich distance between two images. It describes a transformation from one of the images to the other. This master thesis shows how transportation plans can be used for video coding and how to process the transportation plans to achieve a good bitrate/quality ratio. Various parameters are evaluated using an implemented transportation plan video coder.</p><p>The introduction of transform coding with DCT proves to be very useful, as it reduces the size of the resulting transportation plans. DCT coding roughly gives a 10-fold decrease in bitrate with maintained quality compared to the nontransformed transportation plan coding.</p><p>With the best settings for transportation plan coding, I was able to code a test sequence at about 5 times the bitrate for MPEG coding of the same sequence with similar quality.</p><p>As video coding using transportation plans is a very new concept, the thesis is ended with conclusions on the test results and suggestions for future research in this area.</p>

Abordaremos a teoria do transporte otimo demonstrando o teorema da dualidade de Kantorovich para uma classe ampla de funções custo. Tal resultado desempenha um papel de suma importância na teoria do transporte otimo. Uma ferramenta importante utilizada e o teorema da dualidade de Fenchel-Rockafellar, aqui enunciado e demonstrado em bastante generalidade. Demonstramos tamb em o teorema da dualidade de Kantorovich-Rubinstein, que trata do caso particular da função custo distância. / We analyze the optimal transport theory proving the Kantorovich duality theorem for a wide class of cost functions. Such result plays an extremely important role in the optimal transport theory. An important tool used here is the Fenchel-Rockafellar duality theorem, which we state and prove in a general case. We also prove the Kantorovich-Rubinstein duality theorem, which deals with the particular case of cost function given by the distance.

Abordaremos a teoria do transporte otimo demonstrando o teorema da dualidade de Kantorovich para uma classe ampla de funções custo. Tal resultado desempenha um papel de suma importância na teoria do transporte otimo. Uma ferramenta importante utilizada e o teorema da dualidade de Fenchel-Rockafellar, aqui enunciado e demonstrado em bastante generalidade. Demonstramos tamb em o teorema da dualidade de Kantorovich-Rubinstein, que trata do caso particular da função custo distância. / We analyze the optimal transport theory proving the Kantorovich duality theorem for a wide class of cost functions. Such result plays an extremely important role in the optimal transport theory. An important tool used here is the Fenchel-Rockafellar duality theorem, which we state and prove in a general case. We also prove the Kantorovich-Rubinstein duality theorem, which deals with the particular case of cost function given by the distance.