Câmpus de São José do Rio Preto Mariele Pedro de Souza Classificação de imagens tridimensionais por meio de homologia persistente e imagem de persistência São José do Rio Preto 2022 Mariele Pedro de Souza Classificação de imagens tridimensionais por meio de homologia persistente e imagem de persistência Dissertação apresentada como parte dos requisitos para obtenção do título de Mestre em Matemática, junto ao Programa de Pós- Graduação em Matemática, do Instituto de Biociências, Letras e Ciências Exatas da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Câmpus de São José do Rio Preto. Orientador: Prof. Dr. Thiago de Melo Financiadora: CNPq São José do Rio Preto 2022 S729c Souza, Mariele Pedro de Classificação de imagens tridimensionais por meio de homologia persistente e imagem de persistência. / Mariele Pedro de Souza. -- São José do Rio Preto, 2022 111 p. Dissertação (mestrado) - Universidade Estadual Paulista (Unesp), Instituto de Biociências Letras e Ciências Exatas, São José do Rio Preto Orientador: Thiago de Melo 1. Matemática. 2. Topologia algébrica. 3. Análise topológica de dados. 4. Homologia persistente. 5. Agrupamento. I. Título. Sistema de geração automática de fichas catalográficas da Unesp. Biblioteca do Instituto de Biociências Letras e Ciências Exatas, São José do Rio Preto. Dados fornecidos pelo autor(a). Essa ficha não pode ser modificada. Mariele Pedro de Souza Classificação de imagens tridimensionais por meio de homologia persistente e imagem de persistência Dissertação apresentada como parte dos requisitos para obtenção do título de Mestre em Matemática, junto ao Programa de Pós- Graduação em Matemática, do Instituto de Biociências, Letras e Ciências Exatas da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Câmpus de São José do Rio Preto. Financiadora: CNPq Comissão Examinadora Prof. Dr. Thiago de Melo Orientador Profa. Dra. Evelin Meneguesso Barbaresco Departamento de Matemática - Unesp São José do Rio Preto Prof. Dr. Northon Canevari Leme Penteado Departamento de Matemática - Universidade Federal do Cariri São José do Rio Preto 08 de setembro de 2022 À minha brasilidade de nunca desistir. AGRADECIMENTOS Muitos se ufanam: “Não devo nada a ninguém.” Engano: devemos muito a todos. (CORALINA, Cora).1 Agradeço ao Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) pelos vinte e quatro meses de bolsa concedida, por meio do processo número 132281/2020-1. Ajuda essencial em um período de horrores vivido pela pandemia. Agradeço aos que estiveram comigo por todos estes longos meses, que contri- buíram à sua maneira para que este trabalho fosse realizado. À minha família, pelo privilégio financeiro e por aceitarem a minha dedicação. Aos meus irmãos, em par- ticular, que sempre me lembravam que “só estudar” significava muito mais que isso. Aos grandes amigos que a matemática me deu, que entendiam o meu desespero e me encorajaram a concluir mais este grau acadêmico (Mateus e Maurício, vocês foram essenciais). Agradeço à Professora Doutora Évelin Meneguesso Barbaresco por ter me aco- lhido pacientemente, me apresentado à Topologia e estar disposta a me acompanhar em algo novo. Ao meu orientador, Professor Doutor Thiago de Melo, toda minha gratidão pelos ensinamentos, por me acompanhar durante estes meses e entender o meu tempo. 1Disponível em: https://poemasfrasesemensagens.wordpress.com/. https://poemasfrasesemensagens.wordpress.com/category/brasileiros-e-portugueses/cora-coralina/ O conhecimento serve para encantar pessoas, não para humilhá-lhas. (CORTELLA, Mario Sergio). [6] RESUMO O trabalho desenvolvido traz um estudo sobre o agrupamento de imagens tridimensio- nais por meio da Análise Topológica de Dados (TDA). Nos primeiros capítulos, as prin- cipais definições da Topologia Algébrica são apresentadas para construção e enten- dimento dos cálculos realizados posteriormente. À seguir, são desenvolvidos progra- mas na linguagem computacional Python para o estudo das mais de cento e cinquenta imagens, de vinte categorias distintas. Os agrupamentos foram realizados segundo a distância entre diagramas de persistência e imagens de persistência. As análises fi- nais foram realizadas por meio de escalonamento multidimensional, dendrogramas e algoritmo k-means. Palavras-chave: Topologia. Análise topológica de dados. Diagrama de persistência. Agrupamento. ABSTRACT The work developed brings a study on the clustering of three-dimensional images th- rough the Topological Data Analysis (TDA). In the first chapters, the main definitions of Algebraic Topology are presented for the construction and understanding of the cal- culations performed later. Next, programs are developed in the computer language Python for the study of more than one hundred and fifty images, from twenty different categories. Groupings were performed according to the distance between persistence diagrams and persistence images. Final analyses were performed using multidimensi- onal scaling, dendrograms, and the k-means algorithm. Keywords: Topology. Topological data analysis. Persistence diagram. Clustering. Lista de Figuras 2.1 Pontos Geometricamente dependentes e independentes. . . . . . . . . . . . 22 2.2 Exemplos de k-simplexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Tipos de face do σ2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4 Simplexos propriamente unidos e uma união imprópria . . . . . . . . . . . 24 2.5 Realização geométrica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.6 2-simplexo orientado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.7 Exemplo de 1-simplexo e 2-simplexo . . . . . . . . . . . . . . . . . . . . . . 28 3.1 Complexo de Cěch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Complexo VR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 Diagrama de Voronoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4 Complexo Alpha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.5 Filtração de um complexo simplicial . . . . . . . . . . . . . . . . . . . . . . 34 3.6 Nascimento e morte na sequência de grupos de homologia . . . . . . . . . . 36 3.7 Complexo simplicial filtrado. . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.8 Barcode e Diagrama de Persistência . . . . . . . . . . . . . . . . . . . . . . 37 3.9 Diagrama de Persistência H0 . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.10 Gaussiana de uma Imagem de Persistência . . . . . . . . . . . . . . . . . . 44 4.1 Exemplos de imagens do banco de dados. . . . . . . . . . . . . . . . . . . . 46 4.2 Imagens com quantidade de pontos diferentes. . . . . . . . . . . . . . . . . 47 4.3 PDs de imagens com diferente quantidade de pontos . . . . . . . . . . . . . 51 4.4 Diagrama de Persistência do Cubo. . . . . . . . . . . . . . . . . . . . . . . 52 4.5 Escala de cor utilizada para colorir as imagens. . . . . . . . . . . . . . . . . 53 4.6 Table 3, 56 pontos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.7 Potted Plant 8, 1.325 pontos. . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.8 Head 5, 2.034 pontos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.9 Fighter Jet 1, 4.427 pontos. . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.11 Matriz de Distância Bottleneck . . . . . . . . . . . . . . . . . . . . . . . . 58 4.12 Distância Bottleneck de até 0, 01 . . . . . . . . . . . . . . . . . . . . . . . 61 4.14 Imagem próxima à Fighter jet 9. . . . . . . . . . . . . . . . . . . . . . . . . 62 4.15 Distância Bottleneck entre Fighter Jet 9 e Biplane 6. . . . . . . . . . . . . 63 4.16 Table 0, 60 pontos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.17 Cubo - untitled3, 8 pontos. . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.18 Matriz de Distância Euclidiana . . . . . . . . . . . . . . . . . . . . . . . . 70 4.19 Matriz de Distância Euclidiana com peso . . . . . . . . . . . . . . . . . . . 71 4.20 Distância Euclidiana de até 0.01 . . . . . . . . . . . . . . . . . . . . . . . . 72 4.21 Distância Euclidiana com peso de até 0.0001 . . . . . . . . . . . . . . . . . 72 4.23 Imagem próxima à Biplane 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.25 Imagem próxima à Helicopter 8 . . . . . . . . . . . . . . . . . . . . . . . . 74 14 LISTA DE FIGURAS 15 4.26 Matriz de Distância do Máximo . . . . . . . . . . . . . . . . . . . . . . . . 75 4.27 Matriz de Distância do Máximo com peso . . . . . . . . . . . . . . . . . . 76 4.28 Distância do Máximo de até 0.001 . . . . . . . . . . . . . . . . . . . . . . . 76 4.29 Distância do Máximo com peso de até 0.00001 . . . . . . . . . . . . . . . . 76 4.31 Imagem próxima à Deskchair 1 . . . . . . . . . . . . . . . . . . . . . . . . 77 4.33 Imagem próxima à Fish 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.34 Matriz de Distância da Soma . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.35 Matriz de Distância da Soma com peso . . . . . . . . . . . . . . . . . . . . 79 4.36 Distância da Soma de até 0.1 . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.37 Distância da Soma com peso de até 0.001 . . . . . . . . . . . . . . . . . . . 80 4.39 Imagem próxima à Fish 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.41 Imagem próxima à Flying Bird 4 . . . . . . . . . . . . . . . . . . . . . . . 82 5.1 MDS distância bottleneck. . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.2 MDS distância bottleneck de 5 categorias. . . . . . . . . . . . . . . . . . . 86 5.3 MDS distância euclidiana com peso de 5 categorias. . . . . . . . . . . . . . 87 5.4 MDS distância do máximo com peso de 5 categorias. . . . . . . . . . . . . 87 5.5 MDS distância da soma com peso de 5 categorias. . . . . . . . . . . . . . . 87 5.6 Exemplo de dendrograma. . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.7 Dendrograma truncado da matriz de distância bottleneck. . . . . . . . . . 90 5.8 Dendrograma truncado da matriz da soma. . . . . . . . . . . . . . . . . . . 91 5.9 Dendrograma truncado da Distância da Soma com peso . . . . . . . . . . . 91 5.10 Dendrograma horizontal da Distância Bottleneck . . . . . . . . . . . . . . 92 5.11 Dendrograma da Distância da Soma com peso . . . . . . . . . . . . . . . . 93 6.1 Folhas verdes do dendrograma 5.10. . . . . . . . . . . . . . . . . . . . . . . 103 6.2 Folhas verdes do dendrograma 5.11. . . . . . . . . . . . . . . . . . . . . . . 104 Lista de Programas 4.1 Programa para gerar as matrizes de pontos e armazenar as informações. . . 48 4.2 Função que calcula H1 de um arquivo, por meio de sua matriz de pontos. . 49 4.3 Programa para gerar os PDs das imagens com até 1.000 pontos. . . . . . . 49 4.4 Função para exibir o diagrama de persistência de uma imagem. . . . . . . 50 4.5 Função para gerar o diagrama de persistência (nascimento, persistência) e imagem de persistência com peso. . . . . . . . . . . . . . . . . . . . . . . . 54 4.6 Função para gerar a imagem de persistência. . . . . . . . . . . . . . . . . . 55 4.7 Calcular a distância bottleneck entre os Diagramas de Persistência. . . . . 58 4.8 Função para tornar uma matriz simétrica quando precisa excluir última coluna vazia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.9 Função para inserir nome das colunas e índices, em uma matriz. . . . . . . 59 4.10 Função para filtrar as imagens mais próximas. . . . . . . . . . . . . . . . . 60 4.11 Função que exibe a nuvem de pontos das imagens filtradas. . . . . . . . . . 62 4.12 Função para calcular a distância Bottleneck entre dois diagramas de per- sistência e gerar o gráfico. . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.13 Encontrar tamanho ideal para intervalo de nascimento e persistência. . . . 65 4.14 Função para calcular distância entre as matrizes das imagens de persistência. 69 5.1 Função para separar os arquivos em categorias. . . . . . . . . . . . . . . . 84 5.2 Função para criar coluna de categorias nos csv’s. . . . . . . . . . . . . . . 85 5.3 Função para gerar MDS de uma matriz de distâncias. . . . . . . . . . . . . 85 5.4 Função para gerar dendrogramas de uma matriz de distâncias. . . . . . . . 90 5.5 Função para calcular o agrupamento K-means. . . . . . . . . . . . . . . . . 98 16 Sumário 1 Introdução 19 2 Conhecimento preliminar 21 3 Diagrama de Persistência 31 3.1 Complexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.1 Complexo de Cěch . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.2 Complexo de Vietoris-Rips (VR) . . . . . . . . . . . . . . . . . . . 32 3.1.3 Complexo Alpha . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.1.4 Filtração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2 Homologia Persistente . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2.1 A matriz bordo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.3 Distância Bottleneck . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4 Imagem de Persistência . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4 Trabalho Desenvolvido 45 4.1 Banco de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2 Diagrama de Persistência . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.3 Imagem de Persistência . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.4 Distância entre os Diagramas de Persistência . . . . . . . . . . . . . 56 4.4.1 Distância Bottleneck . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.5 Distância entre as Imagens . . . . . . . . . . . . . . . . . . . . . . . . 63 4.5.1 Distância Euclidiana . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.5.2 Distância do Máximo . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.5.3 Distância da Soma . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5 Resultados 83 5.1 MDS - Multidimensional Scaling . . . . . . . . . . . . . . . . . . . . 83 5.2 Dendrograma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.2.1 K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6 Conclusão 103 Referências 105 A Lista de bibliotecas utilizadas na pesquisa 107 A.1 Documentação das Bibliotecas . . . . . . . . . . . . . . . . . . . . . . 108 B QR-Codes 109 B.1 Notas de Rodapé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 17 18 SUMÁRIO B.1.1 Agradecimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 B.1.2 Capítulo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 B.1.3 Capítulo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 B.1.4 Capítulo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 B.1.5 Capítulo 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 B.2 Referências Bibliográficas . . . . . . . . . . . . . . . . . . . . . . . . . 111 B.3 Site . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 1 Introdução A Análise Topológica de Dados (Topological Data Analysis, ou TDA, em in- glês) é um ramo recente da Matemática que tem se desenvolvido de maneira bastante rápida e obtido sucessos em aplicações, como, por exemplo, na iden- tificação de subtipos de câncer de mama, na classificação de objetos tridimen- sionais, na classificação de lesões hepáticas, na identificação de dois tipos de diabetes, entre outras. [18] O trabalho será desenvolvido com o objetivo de agrupar (cluster) imagens tridimensi- onais. Para isso, no Capítulo 2, é feita uma introdução teórica às ferramentas topológicas: simplexos, complexos, triangularização, ciclo, bordo e grupos de homologia. No Capítulo 3 as definições envolvem a base para a análise topológica de dados. Infor- mações sobre tipos de complexos, filtrações e persistência são desenvolvidas. O Diagrama de persistência e Barcode são apresentados para as primeiras análises. Neste trecho, são também desenvolvidos, os conceitos de Distância entre diagramas de persistência e imagem de persistência, estes, essenciais para o desenvolvimento do estudo. É no Capítulo 4 que o banco de dados das imagens tridimensionais é apresentado e lapidado. Por fim, o Capítulo 5 avalia os resultados do estudo por meio do Escalonamento Multidimensional (MDS), do Dendrograma e pelo método de clusterização K-means. Todas as funções elaboradas para o estudo foram desenvolvidas em linguagem de programação Python e estão exibidas no texto. No apêndice A está a biblioteca completa utilizada para a execução dos programas, bem como o link para algumas informações sobre elas. O apêndice B traz como facilidade para o leitor tradicional, àquele que prefere o toque, os códigos QR’s de todas as referências do trabalho (bibliográficas e notas de rodapé), além do acesso à um site, onde estão disponíveis todas as imagens utilizadas no estudo e alguns gráficos de difícil leitura. 19 2 Conhecimento preliminar A topologia é uma abstração da geometria; trata de conjuntos tendo uma es- trutura que permite a definição de continuidade para funções e um conceito de “proximidade” de pontos e conjuntos. Essa estrutura, chamada de “topologia” no conjunto, foi originalmente determinada a partir das propriedades de con- juntos abertos em espaços euclidianos, particularmente no plano euclidiano. (PICCORILLO, Lisa).1 Para que o desenvolvimento do trabalho faça sentido e possa ser compreendido, algu- mas definições e resultados são essenciais. Este capítulo tem como referência o livro do Croom (1978) [9], a dissertação de Mestrado do Ronchi (2020) [20], o artigo de Cerda (et al., 2021) [3], as notas de aula do Menegon (2021) [15] e o livro do Munkres (1930) [16]. Definição 2.1 (Pontos geometricamente independentes). Seja A = {a0, a1, . . . , ak} um conjunto de k+1 pontos em Rn é dito geometricamente independente quando nenhum hiperplano2 de dimensão k − 1 contém todos os pontos de A. Assim, o conjunto {a0, a1, . . . , ak} ser geometricamente independente, significa que todos os pontos são distintos; que quaisquer três pontos não pertencem à uma reta, quaisquer quatro pontos não pertencem à um plano, e, em geral, quaisquer p + 1 pontos não pertencem à um hiperplano de dimensão p− 1 ou menos. Observação 2.2. Equivalentemente, os pontos a0, . . . , an são tais que os vetores diferença a1 − a0, a2 − a0, . . . , an − a0 são linearmente independentes em Rm. Exemplo 2.3. Na Figura 2.1, os pontos {A,B,C} são geometricamente dependentes, pois pertencem a um hiperplano de R2, ou seja, uma reta. Já os pontos {A,B,D}, {A,C,D} ou {B,C,D} são geometricamente independentes. 1Disponível em: https://www.bbc.com/portuguese/geral-53020787. 2Disponível em: https://eu-provo.blogspot.com/2022/02/dissertacao-mestrado.html. 21 https://www.bbc.com/portuguese/geral-53020787 https://eu-provo.blogspot.com/2022/02/dissertacao-mestrado.html 22 Conhecimento preliminar Figura 2.1: Pontos Geometricamente dependentes e independentes. Fonte: Própria autora Definição 2.4 (k-simplexo). Seja {a0, . . . , ak} um conjunto de k + 1 pontos geometrica- mente independentes no Rn. O simplexo geométrico k-dimensional, ou k-simplexo, σk, gerado por estes pontos é o conjunto de todos os pontos x em Rn para o qual existem números reais não negativos λ0, . . . , λk de modo que x = k∑ i=0 λiai e k∑ i=0 λi = 1 Observe a Figura 2.2. Os números λ0, . . . , λk são as coordenadas baricêntricas3 do ponto x e os pontos a0, . . . , ak são os vértices de σk. Figura 2.2: Exemplos de k-simplexos, com k ∈ {0, 1, 2, 3}. Fonte: Própria autora. 3Disponível em: https://eu-provo.blogspot.com/2022/04/coordenadas-baricentricas.html. https://eu-provo.blogspot.com/2022/04/coordenadas-baricentricas.html Conhecimento preliminar 23 Definição 2.5 (k-simplexo aberto). O conjunto de todos os pontos x, com todas as coordenadas baricêntricas positivas, do simplexo σk são chamados de k-simplexo geo- métrico aberto gerado por {a0, . . . , ak}. Também conhecido como interior de σk, é definido por Int(σk) = σk −∂σk, onde ∂σk é a fronteira (2.9) de σk. Observe na imagem 2.2 que o 0-simplexo é um conjunto unitário, um 1-simplexo é uma aresta, um 2-simplexo é um triângulo (interior e bordo), e um 3-simplexo é um tetraedro (interior e bordo). Um 0-simplexo aberto é, também, um conjunto unitário, um 1-simplexo aberto é um segmento sem as extremidades, um 2-simplexo aberto é o interior de um triângulo, e um 3-simplexo aberto é o interior do tetraedro. Definição 2.6 (Dimensão de um simplexo). Seja σk um k-simplexo gerado pelos vértices {a0, . . . , ak}. O número k é a dimensão do simplexo σ. Definição 2.7 (Faces de um simplexo). Qualquer simplexo gerado por um subconjunto de {a0, . . . , ak} é uma face de σk; assim, dizer que um simplexo σm é uma face de um simplexo σk, m ⩽ k, significa que cada vértice de σm é um vértice de σk. Por outro lado, temos que σk é coface de σm. As faces de σk geradas por {a1, . . . , ak} são chamadas faces opostas à a0. As faces de σk, com exceção da própria σk, são chamadas faces próprias de σk. O simplexo σk gerado por {a0, . . . , ak} será denotado por σk = ⟨a0, . . . , ak⟩. Exemplo 2.8. Seja o 2-simplexo σ2 = ⟨a0, a1, a2⟩. Acompanhe na Figura 2.3. A dimensão de σ2 é 2, suas faces são o próprio 2-simplexo, juntamente com os 1-simplexos ⟨a0, a1⟩, ⟨a1, a2⟩ e ⟨a0, a2⟩, e os 0-simplexos ⟨a0⟩, ⟨a1⟩ e ⟨a2⟩. Assim, ⟨a0, a1⟩ é uma 1-face de σ2 e σ2 é uma 2-coface de ⟨a0, a1⟩. As faces próprias são os 1-simplexos ⟨a0, a1⟩, ⟨a1, a2⟩ e ⟨a0, a2⟩, e os 0-simplexos ⟨a0⟩, ⟨a1⟩ e ⟨a2⟩. As faces opostas à ⟨a0⟩ são o 1-simplexo ⟨a1, a2⟩ e os 0-simplexos ⟨a1⟩ e ⟨a2⟩. Figura 2.3: Tipos de face do σ2. Fonte: Própria autora. Definição 2.9. A união de todas as faces próprias de um simplexo σk é a fronteira de σk, denotada por ∂σk. Observação 2.10. Um q-simplexo tem ( q + 1 d+ 1 ) d-faces e q∑ d=0 ( q + 1 d+ 1 ) = 2q+1 faces no total. 24 Conhecimento preliminar De fato, para d = 0, temos:( q + 1 0 + 1 ) = ( q + 1 1 ) = (q + 1)! 1!(q + 1 − 1)! = (q + 1)q! 1!q! = q + 1 que equivale a quantidade de vértices de um simplexo. Para o total de faces: q∑ d=0 ( q + 1 d+ 1 ) = ( q + 1 1 ) + ( q + 1 2 ) + · · · + ( q + 1 q + 1 ) = (q + 1) + · · · + 1 = 2q+1 pelo Teorema das linhas do Triângulo de Pascal.4 Exemplo 2.11. Seja σ2 = ⟨a0, a1, a2⟩ o 2-simplexo do exemplo 2.8. Verifiquemos a quantidade de faces de σ2. Pela observação 2.10, temos que: 2∑ d=0 ( 2 + 1 d+ 1 ) = ( 3 1 ) + ( 3 2 ) + ( 3 3 ) = 3! 1!2! + 3! 2!1! + 1 = 3 + 3 + 1 = 7 Definição 2.12 (Simplexos propriamente unidos). Dois simplexos σm e σn são propri- amente unidos se eles não possuem interseção ou se σm ∩ σn for uma face de ambos. Observe exemplos na Figura 2.4. Figura 2.4: Os simplexos em a) e b) são propriamente unidos, os do item c) é uma união imprópria. Fonte: Própria autora. Definição 2.13 (Complexo simplicial geométrico). Um complexo geométrico (ou complexo simplicial ou complexo) é uma família finita K de simplexos geométricos unidos propriamente e que apresentam uma propriedade onde, cada face de um elemento de K é também um elemento de K, ou seja, dado σ ∈ K, temos que para toda face τ ⊂ σ, satisfaz τ ∈ K. A dimensão de K é o maior inteiro positivo m tal que K tenha um m-simplexo. 4Disponível em: https://eu-provo.blogspot.com/2022/04/teorema[...].html https://eu-provo.blogspot.com/2022/04/teorema-das-linhas-triangulo-de-pascal.html Conhecimento preliminar 25 Definição 2.14 (Complexo simplicial abstrato). Seja X um conjunto finito com pontos quaisquer. Seja Y um conjunto de subconjuntos não-vazios de X. Dizemos que Y é um complexo simplicial abstrato de X se para todo σ ∈ Y , temos que todo subconjunto σ′ ⊂ σ, σ′ ⊂ Y . Cada elemento σ ∈ Y é chamado de simplexo. Exemplo 2.15. Sejam X = {a, b, c} e Y = {{a}, {b}, {c}, {a, b}, {a, c}}. Temos que Y é um complexo simplicial abstrato. Tome o simplexo σ = {a, b}. Note que seus subconjuntos {a} e {b} pertencem a Y . O mesmo acontece para o simplexo τ = {a, c}. Logo, Y é, de fato, um complexo simplicial abstrato. Definição 2.16 (Esquema de vértices). Sejam K é um complexo simplicial e V o conjunto dos vértices de K. Tome como K a coleção de todos os subconjuntos {a0, . . . , an} de V tal que os vértices {a0, . . . , an} gerem um simplexo de K. A coleção K é chamada de esquema de vértices de K. Observação 2.17. A coleção K é um exemplo particular de um complexo simplicial abstrato. Teorema 2.18. a) Todo complexo abstrato S é isomorfo ao esquema de vértices de algum complexo simplicial K. b) Dois complexos simpliciais são linearmente isomorfos se, e somente se, seus esque- mas de vértices são isomorfos como complexos simpliciais abstratos. Demonstração. a) Dado um conjunto de índices J , seja ∆J a coleção de todos os simplexos EJ gerados por subconjuntos finitos de uma base {ϵα} de EJ . Assim, ∆J é um complexo simplicial. Se σ e τ são simplexos de ∆J , então a união do conjunto de seus vértices é geometri- camente independente e gera um simplexo de ∆J . ∆J será chamado por complexo de dimensão infinita. Agora, considere um complexo abstrato S com um conjunto de vértices V . Escolha um cojunto de índices J grande o suficiente para que haja uma função injetora f : V → {ϵα}α∈J (pode ser considerado J = V ). Um subcomplexo K de ∆J é o complexo geométrico gerado por f(a0), . . . , f(an) de um simplexo abstrato {a0, . . . , an} ∈ S. Logo, K é um complexo simplicial e S é isomorfo ao esquema de vértices de K; f é a correspondência necessária entre seus conjuntos de vértices. b) Segue imediatamente do Lema abaixo, disponível na página 22 da referência [16]. Lema: Seja f : K → L uma aplicação bijetora tal que os vértices v0, . . . , vn ∈ K geram um simplexo em K se, e somente se, f(v0), . . . , f(vn) gerarem um simplexo em L. Então, a aplicação simplicial induzida g : |K | → |L | é um homeomorfismo (bijetora com inversa contínua). A aplicação g é chamada de homeomorfismo simplicial ou isomorfismo, de K com L. 26 Conhecimento preliminar Demonstração Lema: Cada simplexo σ ∈ K é levado por g à um simplexo τ ∈ L, de mesma dimensão. Para mostrar o homeomorfismo, é suficiente mostrar que h : τ → σ induzida pela correspondência de vértices f−1 é a inversa de g : σ → τ . Note que se x = ∑ tivi, então g(x) = ∑ tif(vi), por definição, assim, h(g(x)) = h( ∑ tif(vi)) = ∑ tif −1(f(vi)) bijetora= ∑ tivi = x. Definição 2.19 (Realização geométrica). Se o complexo simplicial abstrato S é isomorfo com o esquema de vértices do complexo simplicial K, chamamos K de realização geo- métrica de S. Ela é unicamente determinada por um isomorfismo linear. Exemplo 2.20. Considere o complexo abstrato Y = {{a0, a1, a2, a3}, {a0, a1, a2}, {a0, a1, a3}, {a0, a2, a3}, {a1, a2, a3}, {a0, a1}, {a1, a2}, {a2, a0}, {a0, a3}, {a1, a3}, {a2, a3}, {a0}, {a1}, {a2}, {a3}}. A realização geométrica pode ser feita de mais de uma forma, Figura 2.5: Figura 2.5: Realização geométrica. Fonte: Própria autora. Definição 2.21 (Operador geométrico). A união dos elementos de K com o subespaço topológico Euclidiano é denotado por |K | e é chamado de operador geométrico de K ou um poliedro associado com K. Observação 2.22. Todo espaço métrico compacto pode ser indefinidamente aproximado por poliedros, garante o teorema de P. S. Alexandroff (1928). Assim, ao trabalharmos complexos com números finitos de simplexos, nos dá a garantia da existência. Definição 2.23 (Espaço triangularizável). Seja X um espaço topológico. Se existe um complexo geométrico K cujo operador geométrico |K | é homeomorfo a X, então X é dito ser um espaço triangularizável, e o complexo K é chamado de triangularização de X. Definição 2.24 (k-simplexo orientado). Um k-simplexo orientado, k ⩾ 1, é obtido de um k-simplexo σk = ⟨a0, . . . , ak⟩ escolhendo uma ordem para seus vértices. A orientação é indicada como na Figura 2.6. Observação 2.25. A ordem dos vértices de um simplexo realmente importa. ⟨v0, v1, . . . , vn⟩ ≠ ⟨v1, v0, . . . , vn⟩ Conhecimento preliminar 27 Figura 2.6: 2-simplexo orientado τ 2 = ⟨a0, a1, a2⟩. Fonte: Própria autora. Definição 2.26 (Cadeia). Seja K um complexo simplicial. Uma p-cadeia em K é uma função cp do conjunto de p-simplexos orientados σp de K para os inteiros, cp : K → Z, tal que cp(−σp) = −cp(σp), onde −σp é a orientação oposta de σp. A 0-cadeia é uma função dos 0-simplexos de K para os números inteiros. Com a operação de adição pontual induzida pelos inteiros, a família de p-cadeias forma um grupo chamado grupo de p-cadeia de K. Este grupo é denotado por Cp(K). Se p < 0 ou p > dimK, Cp(K) representa o grupo trivial. Se σp é um p-simplexo orientado, a cadeia elementar cp correspondente a σp é a função definida da seguinte forma: • cp(σp) = 1, • cp(−σp) = −1, • cp(τ p) = 0, para cada p-simplexo orientado τ p ̸= σp. Essa p-cadeia elementar é denotada por gσp, onde g = cp(σp) ∈ Z. Com essa notação, uma p-cadeia dp arbitrária pode ser expressa como uma soma formal finita, dp = ∑ i giσ p i , gi ∈ Z de p-cadeias elementares, onde o índice i varia em todos os p-simplexos de K. Observação 2.27. Por abuso de notação, usamos o símbolo σ para denotar não apenas um simplexo, ou um simplexo orientado, mas também para denotar a cadeia elementar c correspondente ao simplexo orientado σ. Para facilitar a distinção, sendo σk = ⟨a0, . . . , ak⟩ um simplexo orientado, a k-cadeia correspondente será denotada por [a0, . . . , ak]. Observação 2.28. O grupo de cadeias Cp(K) é isomorfo à soma direta do grupo Z (ou qualquer outro grupo ou anel comutativo) sobre a família de p-simplexos de K. Isto é, se K tem αp p-simplexos, então Cp(K) é isomorfo à soma direta de αp cópias de Z. Um isomorfismo é dado pela correspondência αp∑ i=1 giσ p i ⇔ ( g1, g2, . . . , gαp ) ⇔ Z1 ⊕ Z2 ⊕ · · · ⊕ Zαp 28 Conhecimento preliminar Definição 2.29 (Homomorfismo fronteira). Seja σp = ⟨a0, . . . , ap⟩ um p-simplexo ori- entado de um K complexo qualquer, com p > 0. Definimos o homomorfismo fronteira ∂p : Cp(K) → Cp−1(K), tal que: ∂p (σp) = ∂p[a0, . . . , ap] = n∑ i=0 (−1)i[a0, . . . , âi, . . . , an], onde âi significa que o vértice ai foi removido da sequência. Como Cp(K) é o grupo trivial para p < 0, o operador ∂p é o homomorfismo trivial para p ⩽ 0. Exemplo 2.30. Calcular as fronteiras dos simplexos: Figura 2.7: a) 1-simplexo [a0, a1], b) 2-simplexo [a0, a1, a2]. a) ∂1[a0, a1] = (−1)0[a1] + (−1)1[a0] = [a1] − [a0] b) ∂2[a0, a1, a2] = (−1)0[a1, a2]+(−1)1[a0, a2]+(−1)2[a0, a1] = [a1, a2]−[a0, a2]+[a0, a1] Definição 2.31 (Ciclo). Seja K um complexo orientado. Se p é um inteiro positivo, um p-ciclo em K é uma p-cadeia zp tal que ∂p(zp) = 0. O kernel (ou núcleo) do ∂p : Cp(K) → Cp−1(K) é um subgrupo de Cp(K) chamado de grupo de p-ciclos e denotado por Zp(K) (por conta da palavra alemã “Zyklus” que significa “ciclo”). Definição 2.32 (Bordo). Se p ⩾ 0, a p-cadeia bp é um p-bordo em K, se houver (p+ 1)-cadeia σp+1 tal que ∂p+1(σp+1) = bp. A imagem do ∂p+1 : Cp+1(K) → Cp(K) é um subgrupo de Cp(K) chamada de grupo de p-bordos e denotado por Bp(K). Observação 2.33. • O 0-ciclo, tal como a 0-cadeia, é zero; logo, o grupo Z0(K) é trivial. • Se n é a dimensão de K, então não há p-cadeia em K para p > n. • Intuitivamente, um p-ciclo é uma combinação linear de p-simplexos que faz um circuito completo. • Os p-ciclos que circundam “buracos” são aqueles que não são bordos, isto é, Zp(K) ̸⊂ Bp(K). Conhecimento preliminar 29 • A composição5 ∂n ◦ ∂n+1 = 0, ou seja, Bp(K) ⊂ Zp(K). Definição 2.34 (Grupo de Homologia). Se K é um complexo orientado e p é um inteiro não negativo, o p-ésimo grupo de homologia de K é dado pelo quociente: Hp(K) = Zp(K)/Bp(K) e as classes [zp] ∈ Hp(K) são chamadas de classes de homologia. Observação 2.35. Dois ciclos representando a mesma classe de homologia são ditos homólogos. Isso significa que a diferença entre eles é uma fronteira. Definição 2.36 (Complexo de cadeias). Uma sequência de homomorfismos de grupos abelianos Cn+1 ∂n+1−−−→ Cn ∂n−→ Cn−1 → · · · → C1 ∂1−→ C0 ∂0−→ 0 com ∂n ◦ ∂n+1 = 0 para cada n, é dita um complexo de cadeias. 5Disponível na aula 15, pagina 6 da referência [15] e na página 14 da referência [23]. 3 Diagrama de Persistência 3.1 Complexos Como visto no capítulo anterior, um complexo simplicial é uma família de simple- xos (2.13) e eles são a base para a construção dos resultados posteriores, como ciclos (2.31), bordos (2.32) e os grupos de homologia (2.34). Foi visto, que a realização geométrica (2.19) nem sempre é única, assim, para um conjunto de pontos, é possível construir os complexos segundo alguns parâmetros. Veremos as opções clássicas.1 3.1.1 Complexo de Cěch Definição 3.1 (Complexo de Cěch). Sejam X um conjunto de pontos em Rn e r > 0 um valor fixo real. O complexo de Cěch é um complexo simplicial onde os vértices (0-simplexos) são elementos de X e o conjunto de pontos {x0, . . . , xk} define um k-simplexo se k⋂ i=0 B(xi, r) ̸= ∅, onde B(xi, r) = {x ∈ Rn | d(xi, x) < r} é uma bola aberta centrada em xi, com raio r, para uma distância d. Veja na Figura 3.1. Denotamos o complexo de Cěch para um valor real r > 0 de um conjunto X por Cr(X). Figura 3.1: Dado um conjunto de pontos, à esquerda temos um parâmetro r, com a distância euclidiana aplicado e à direita, o Complexo de Cěch resultante. Fonte: Própria autora. 1Nesta seção as definições e resultados tem como referência a dissertação [20] e o artigo [3]. 31 32 Diagrama de Persistência A ideia do Complexo de Cěch é que, se duas bolas se intersectam, adicionamos um 1-simplexo (aresta), se três bolas se intersectam, adicionamos um 2-simplexo, ou seja, um k-simplexo é adicionado ao complexo simplicial abstrato quando há interseção de k + 1 bolas, centradas nos vértices, com raio r > 0 e distância d. 3.1.2 Complexo de Vietoris-Rips (VR) Definição 3.2 (VR Complexo). Sejam X um conjunto de pontos em Rn e r > 0 um valor fixo real. O complexo de VR é um complexo simplicial onde os vértices (0-simplexos) são elementos de X e o conjunto de pontos {x0, . . . , xk} define um k- simplexo, σk = ⟨x0, . . . , xk⟩, se diam(σk) ⩽ 2r. Considere a Figura 3.2. Denotamos o VR complexo para um valor real r de um conjunto X por VRr(X). Figura 3.2: Dado um conjunto de pontos, à esquerda temos um parâmetro r, com a distância euclidiana aplicado e à direita, o VR complexo resultante. Fonte: Própria autora. Para o Complexo de Vietoris-Rips, um k-simplexo é adicionado ao complexo simplicial abstrato se a distância entre os vértices, dois à dois, for menor ou igual a 2r, onde r é o raio das bolas centradas nos vértices, construídas por uma distância d. Observação 3.3. Temos que Cr(X) ⊆ VRr(X) ⊆ C2r(X) como relação entre os comple- xos. Demonstração. Seja X ⊂ Rn um conjunto de pontos. Tome σk = ⟨x0, . . . , xk⟩ um k-simplexo, tal que x0, . . . , xk ∈ X. Se σk ∈ Cr(X), então k⋂ i=0 B(xi, r) ̸= ∅. Como k⋂ i=0 B(xi, r) ̸= ∅, temos que diam(σk) ⩽ 2r. Logo, σk ∈ VRr(X). Da mesma forma, se diam(σk) ⩽ 2r, então k⋂ i=0 B(xi, 2r) ̸= ∅. Portanto, Cr(X) ⊆ VRr(X) ⊆ C2r(X). Observação 3.4. Do ponto de vista computacional, o complexo VR é mais viável (ou seja, menor armazenamento e complexidade de tempo) do que Cěch. Pois, no complexo de Cěch o computador precisa armazenar todas as distâncias e verificar se há interseção em cada nível; já no complexo de VR, a informação sobre as distâncias são suficientes para a construção dos simplexos. Complexos 33 3.1.3 Complexo Alpha Definição 3.5 (Diagrama de Voronoi). Dado um subconjunto X = {x0, . . . , xk}, X ⊂ Rn, definimos a célula de Voronoi associada ao ponto xi sendo: Vi = {x ∈ Rn | d (xi, x) ⩽ d (xj, x) ,∀j ∈ 0, . . . , k} , em que d é a distância euclidiana usual. Como mostra a Figura 3.3. Figura 3.3: Diagrama de Voronoi de um conjunto de pontos. Fonte: Própria autora. Na prática, para a construção do Diagrama, basta considerar as delimitações das mediatrizes dos pontos, dois à dois. Definição 3.6 (Complexo Alpha). Sejam um conjunto de pontos X em Rn e r > 0 um valor fixo real. O complexo Alpha de X é um complexo simplicial onde os vértices (0-simplexos) são os elementos de X e o conjunto de pontos {x0, . . . , xk} define um k-simplexo se, k⋂ i=0 R (xi, r) ̸= ∅, onde R(xi, r) = B(xi, r) ∩ Vi, para todo i ∈ {0, . . . , k}. Observe a Figura 3.4. Denotamos o complexo Alpha para um valor real r de um conjunto X por Ar(X). Observação 3.7. Para o complexo Alpha, temos a seguinte relação: Ar(X) ⊂ Cr(X). Demonstração. Seja X ⊂ Rn um conjunto de pontos. Tome σk = ⟨x0, . . . , xk⟩ um k-simplexo, tal que x0, . . . , xk ∈ X. Se σk ∈ Ar(X), então k⋂ i=0 R(xi, r) ̸= ∅. Como k⋂ i=0 R(xi, r) = k⋂ i=0 ( B(xi, r) ∩ Vi ) ̸= ∅, temos que k⋂ i=0 B(xi, r) ̸= ∅. Logo, σk ∈ Cr(X). Portanto, Ar(X) ⊂ Cr(X). 34 Diagrama de Persistência Figura 3.4: Dado um conjunto de pontos, à esquerda temos um parâmetro r interseccio- nado com Diagrama de Voronoi e à direita, o Complexo Alpha resultante. Fonte: Própria autora. 3.1.4 Filtração A ideia da filtração de um complexo, é separá-lo em subconjuntos de forma crescente, onde o seu menor subconjunto é composto pelos vértices do complexo e aumenta a medida que se anexa os simplexos de acordo com um parâmetro, até que atinja sua totalidade. Para as definições que seguem, são mencionados o artigo [3], a dissertação [20] e o livro [11]. Definição 3.8 (Subcomplexo). Seja K um complexo simplicial. K ′ é um subcomplexo de K se K ′ ⊆ K e K ′ for também um complexo simplicial. Definição 3.9 (Filtração). Seja K um complexo simplicial. Uma filtração de K é uma sequência de subcomplexos Ki ⊂ K, de tal forma que, ∅ ⊆ K0 ⊆ K1 ⊆ · · · ⊆ Kn−1 ⊆ Kn = K. Em outras palavras, a filtração de um complexo é a sucessão de acréscimos de sub- complexos de K. A Figura 3.5 exemplifica. Neste caso, K é dito complexo simplicial filtrado. ⊂ ⊂ ⊂ ⊂ ⊂ ··· K0 K1 K2 K3 K4 Figura 3.5: Fragmento de uma filtração de um complexo simplicial de VR obtida pela variação do parâmetro ri = (i+ 1) · 0,5 para cada Ki ∈ K. Imagem fora de escala. Fonte: Própria autora. Quando os simplexos são determinados por proximidade de acordo com uma função distância, como nos casos do complexo de Cěch, VR complexo e complexo Alpha, uma Homologia Persistente 35 filtração de um complexo simplicial K é obtida por uma sequência de valores positivos 0 < r1 < r2 < · · · < rn, onde o complexo Ki corresponde ao parâmetro ri. Definição 3.10 (Função Nível de Filtração). Seja K um complexo simplicial finito fil- trado, ∅ ⊆ K0 ⊆ K1 ⊆ · · · ⊆ Kn = K. A função de nível de filtração ψ é definida em {r0, r1, . . . , rn} por ψ(ri) = Ki. Definição 3.11 (Nascimento ou morte). Nascimento é um conceito para descrever o ní- vel de filtração quando uma nova característica topológica aparece. Similarmente, morte refere-se ao nível de filtração quando uma característica topológica desaparece. Então, um intervalo persistente (nascimento, morte) é uma “vida” de uma característica to- pológica dada. Uma filtração pode ser entendida como um método para construir todo o complexo simplicial K a partir de uma ‘família’ de sub-complexos ordenados incrementalmente de acordo com alguns critérios, onde cada nível i corres- ponde ao ‘nascimento’ ou ‘morte’ de uma característica topológica. [...]. [3] Observação 3.12. Na filtração, os simplexos se unem aos criados primeiro; assim, o simplexo que morre na união, recebe o nome do simplexo mais antigo do complexo. Esta regra é chamada de regra mais antiga. 3.2 Homologia Persistente A Topologia de Persistência consiste no estudo de propriedades de espaços topológicos com filtrações. A Topologia de Persistência permite analisar os dados representados por uma função filtração e examinar como as propriedades de seus conjuntos de subníveis persistem quando se percorre a filtração.[14] Em um complexo simplicial filtrado, há uma evolução topológica expressa pela sequên- cia de grupos de homologia. Nesta seção, foram utilizadas as referências [11], [22] e [4]. Definição 3.13 (Sequência de grupos de homologia de uma filtração). Seja um complexo simplicial K com uma filtração, ∅ ⊂ K1 ⊂ K2 ⊂ · · · ⊂ Kn−1 ⊂ Kn = K. Definimos uma aplicação inclusão f : Ki → Kj, onde i ⩽ j. Assim, temos um homo- morfismo induzido f i,j p : Hp(Ki) → Hp(Kj), para cada dimensão p. Logo, a filtração corresponde a sequência de grupos de homologia conectada por homomorfismos, para cada dimensão p. 0 = Hp(K0) → Hp(K1) → · · · → Hp(Kn−1) → Hp(Kn) = Hp(K). O p-ésimo grupo de homologia persistente é a imagem do homomorfismo induzido pela inclusão, Im ( f i,j p ) = Hi,j p , para 0 ⩽ i ⩽ j ⩽ n. 36 Diagrama de Persistência A medida que avançamos na filtração, de Ki−1 à Ki, podemos ganhar novas classes de homologia e podemos perder algumas quando se tornam triviais ou se fundem. Coletamos as classes que nasceram nela ou as que nasceram antes, e morreram após a união com outro grupo. Quando uma classe morre, ela se funde à outra mais antiga, de acordo com a sequência dos simplexos criados. Os grupos de homologia persistente consistem nas classes de homologia de Ki que ainda estão vivas em Kj ou, mais formalmente, Hi,j p = Zp(Ki)/ (Bp(Kj) ∩ Zp(Ki)). Estes, são espaços vetoriais2 com coeficientes em um corpo; neste trabalho, usaremos o corpo Z2. Temos tal grupo para cada dimensão p e cada par de índices i ⩽ j. Definição 3.14 (Nascimento e morte na sequência de grupos de homologia). Seja γ uma classe de homologia de dimensão p em Hp (Ki), isto é, γ ∈ Hp(Ki). Dizemos que γ nasce em Ki se γ /∈ Im ( f i−1,i p ) ; e, se γ nasce em Ki, diremos que γ morre ao entrar em Kj se γ se fundir com uma classe mais velha, conforme vamos de Kj−1 para Kj. Assim, f i,j−1 p (γ) /∈ Im ( f i−1,j−1 p ) , mas f i,j p (γ) ∈ Im ( f i−1,j p ) . Figura 3.6: A classe γ nasce em Ki pois não está na imagem (sombreada) de Hp (Ki−1). Além disso, γ morre entrando em Kj já que esta é a primeira vez que sua imagem se funde com a imagem de Hp (Ki−1). Fonte: (EDELSBRUNNER, HARER, 2010, p. 151)[11] Definição 3.15 (Persistência). Se γ nasce em Ki e morre entrando em Kj, então chama- mos a diferença no valor da função de persistência, pers(γ) = aj − ai e representamos pelo par (i, j) = (nascimento,morte). Às vezes preferimos ignorar os valores reais da função e considerar a diferença no índice, j − i, que chamamos de persistência de índice da classe. Se γ nasce em Ki mas nunca morre, então definimos sua persistência assim como sua persistência de índice para infinito, (i,∞). Observação 3.16. Nascimentos e mortes também podem ser definidos para uma sequên- cia de espaços vetoriais que não são necessariamente grupos de homologia. Tudo o que se precisa é uma sequência finita e homomorfismos da esquerda para a direita, que, para espaços vetoriais, são geralmente chamados de funções lineares. Existem duas formas de visualizar esses intervalos, através dos barcodes (código de barras) ou dos diagramas de persistência (PD). Essas ferramentas indicam em quais 2Disponível em: https://eu-provo.blogspot.com/2022/07/espaco-vetorial.html. https://eu-provo.blogspot.com/2022/07/espaco-vetorial.html Homologia Persistente 37 parâmetros de escala as características topológicas aparecem pela primeira vez (“nasce”) e não mais permanecem (“morre”). Em um barcode, um segmento de linha horizontal começa no nascimento de cada característica e termina quando ela morre, ou seja, dese- nhamos uma barra do comprimento do intervalo [i, j). Por outro lado, um diagrama de persistência exibe informações homológicas como pontos (i, j) no plano cartesiano. Os eixos horizontal e vertical codificam os parâmetros de nascimento e morte, respectiva- mente. Como todos as características morrem depois de nascer, significa que os pontos estarão no meio plano positivo, acima da diagonal. Normalmente, pontos próximos à dia- gonal são considerados como ruído, enquanto aqueles mais distantes da diagonal sugerem características topológicas mais significativas. Exemplo 3.17. Considere o complexo simplicial de Cěch da Figura 3.7, com uma filtração obtida pelo acréscimo do parâmetro ri = 0, 5 para Ki. Tome a seguinte ordenação: ⊂ ⊂ K1 K2 K3 Figura 3.7: Complexo simplicial filtrado. Fonte: Própria autora. Para H0, temos: (a) Barcode de H0. (b) Diagrama de Persistência de H0. Figura 3.8: Tipos de representação da persistência do complexo da Figura 3.7. Fonte: Própria autora. 38 Diagrama de Persistência 3.2.1 A matriz bordo ∂ Seja K um complexo simplicial filtrado e sejam σ1, . . . , σn os simplexos de K. Colo- caremos uma ordenação de tal maneira que os simplexos de Ka precedam os simplexos de Kb, para a < b e, se ambos estiverem no mesmo nível Ka da filtração, as faces dos simplexos são priorizadas, ou seja, se σi é face de σj, então σi < σj. Assim, a ordem de construção dos simplexos é preservada, bem como a construção de novos simplexos. Nesse contexto, apresentamos o seguinte: Definição 3.18 (Matriz bordo). A matriz bordo de K, denotada por ∂, é uma matriz n× n em que cada entrada tem o seguinte valor δ(i, j) = 1, se o simplexo σi é face de σj e dim(σj) = dim(σi) + 1 0, caso contrário. Na matriz bordo, cada coluna e cada linha representa um simplexo de K e, abusando da notação, citamos suas linhas e colunas com o nome dos simplexos. Com a matriz construída, usaremos um algoritmo para sua redução, descrito a seguir. Para cada coluna σj, será denotado por low(j) o maior inteiro i ∈ {1, . . . , n} tal que δ(i, j) = 1. Assim, para cada coluna σj, enquanto houver low(jd) = low(jc), para d > c, com c, d ∈ {1, . . . , n}, faremos σjd = σjc + σjd , ou seja, trocaremos uma coluna pela sua soma com outra coluna. Definição 3.19 (Matriz reduzida). Uma matriz bordo estará reduzida quando, para quaisquer colunas jc, jd não nulas, low(jc) ̸= low(jd). Para as colunas nulas, o low é dito indefinido. As colunas da matriz reduzida admitem as seguintes interpretações: • quando a coluna de σj for nula, dizemos que o simplexo σj é positivo, pois nele nasce um ciclo; • quando a coluna de σj for não-nula, existe um i tal que low(j) = i. Dizemos que o simplexo σj é negativo, pois nele morre um ciclo. Ciclo este, que nasceu com a adição com o simplexo σi. Exemplo 3.20. Usaremos para a construção da matriz bordo a filtração do complexo simplicial da Figura 3.7. Encontraremos a matriz reduzida e faremos a sua interpretação. ⊂ ⊂ K1 K2 K3 Homologia Persistente 39 ∂(K2)14×14 = σ1 σ2 σ3 σ4 σ5 σ6 σ7 σ8 σ9 σ10 σ11 σ12 σ13 σ14  σ1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 σ2 0 0 0 0 0 0 0 0 1 0 1 0 0 0 σ3 0 0 0 0 0 0 0 1 0 1 1 1 0 0 σ4 0 0 0 0 0 0 0 0 0 0 0 1 1 0 σ5 0 0 0 0 0 0 1 0 0 0 0 0 0 0 σ6 0 0 0 0 0 0 0 1 0 0 0 0 1 0 σ7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 σ8 0 0 0 0 0 0 0 0 0 0 0 0 0 1 σ9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 σ10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 σ11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 σ12 0 0 0 0 0 0 0 0 0 0 0 0 0 1 σ13 0 0 0 0 0 0 0 0 0 0 0 0 0 1 σ14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Esta matriz é construída, usualmente, sobre o corpo Z2 = {0, 1}, assim, 1 + 1 = 0. Analisando para reduzir a matriz, temos: • low(13) = low(8), logo σ13 = σ8 + σ13; • low(11) = low(10), logo σ11 = σ10 + σ11; • low(11) = low(9), logo σ11 = σ9 + σ11; • low(13) = low(12), logo σ13 = σ12 + σ13. Após este processo, esta é a matriz resultante: R(K2) = σ1 σ2 σ3 σ4 σ5 σ6 σ7 σ8 σ9 σ10 σ11 σ12 σ13 σ14  σ1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 σ2 0 0 0 0 0 0 0 0 1 0 0 0 0 0 σ3 0 0 0 0 0 0 0 1 0 1 0 1 0 0 σ4 0 0 0 0 0 0 0 0 0 0 0 1 0 0 σ5 0 0 0 0 0 0 1 0 0 0 0 0 0 0 σ6 0 0 0 0 0 0 0 1 0 0 0 0 0 0 σ7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 σ8 0 0 0 0 0 0 0 0 0 0 0 0 0 1 σ9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 σ10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 σ11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 σ12 0 0 0 0 0 0 0 0 0 0 0 0 0 1 σ13 0 0 0 0 0 0 0 0 0 0 0 0 0 1 σ14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 As colunas nulas σ1, σ2, σ3, σ4, σ5, σ6, σ11 e σ13 são ditas positivas, pois é onde acontece o nascimento de ciclos: por meio dos 0-simplexos de σ1 à σ6 para H0; dos 1-simplexos σ11 e σ13 para H1. Fazendo um pareamento entre os simplexos, relacionando a coluna com o valor low correspondente, concluímos, pela definição de δ(i, j), que: 40 Diagrama de Persistência • low(7) = 5 ⇒ σ5 é face de σ7 e dim(σ7) = dim(σ5) + 1; • low(8) = 6 ⇒ σ6 é face de σ8 e dim(σ8) = dim(σ6) + 1; • low(9) = 2 ⇒ σ2 é face de σ9 e dim(σ9) = dim(σ2) + 1; • low(10) = 3 ⇒ σ3 é face de σ10 e dim(σ10) = dim(σ3) + 1; • low(12) = 4 ⇒ σ4 é face de σ12 e dim(σ12) = dim(σ4) + 1; • low(14) = 13 ⇒ σ13 é face de σ14 e dim(σ14) = dim(σ13) + 1; Para cada relação, temos um intervalo de persistência, de acordo com o nível de nascimento do simplexo: • [σ5, σ7) = [1, 2), pois σ5 nasceu em K0 e σ7 nasceu em K1; • [σ6, σ8) = [1, 2), pois σ6 nasceu em K0 e σ8 nasceu em K1; • [σ2, σ9) = [1, 3), pois σ2 nasceu em K0 e σ9 nasceu em K2; • [σ3, σ10) = [1, 3), pois σ3 nasceu em K0 e σ10 nasceu em K2; • [σ4, σ12) = [1, 3), pois σ4 nasceu em K0 e σ12 nasceu em K2; • [σ13, σ14) = [3, 3), pois σ13 nasceu em K2 e σ14 nasceu em K2; • [σ1,∞) = [1,∞), pois σ1 nasceu em K0 e não se relaciona com nenhum outro simplexo; • [σ11,∞) = [3,∞), pois σ11 nasceu em K2 e não se relaciona com nenhum outro simplexo. Os simplexos que não se relacionam com nenhum outro são o σ1 e o σ11. Portanto, o diagrama de persistência para H0 da filtração é representado pelos pontos (1, 2), (1, 3) e (1,∞). É exatamente o mesmo obtido pela interpretação geométrica da filtração, na Figura 3.8b. Os pontos (3, 3) e (3,∞) não são considerados pois pertencem à H1. 3.3 Distância Bottleneck A capacidade de calcular distâncias entre diagramas de persistência permite concluir tarefas de Machine Learning (ML - aprendizado de máquina) que dependem apenas da dis- tância entre objetos, como por exemplo, alguns algoritmos de agrupamento. Desta forma, os PDs podem ser pensados como uma estatística para agrupar os espaços topológicos subjacentes (ou outros objetos).[4] A distância bottleneck, é uma métrica padrão utilizada para calcular a distância entre os Diagramas de Persistência. Os resultados e definições apresentados nesta seção têm como referência as disserta- ções [20], [22] e o livro [11]. Distância Bottleneck 41 Figura 3.9: Diagrama de Persistência de H0 do complexo simplicial filtrado Fonte: Própria autora. Definição 3.21 (Métrica L∞). Sejam x = (a, b) e y = (p, q) dois pontos do plano. A métrica L∞ é dada por: d∞(x, y) = d∞((a, b), (p, q)) = max{| a− p |, | b− q |}. Para pontos no infinito, é dada da seguinte forma: d∞((−∞, b), (−∞, q)) = | b− q |, d∞((a,+∞), (p,+∞)) = | a− p |, d∞((−∞,+∞), (−∞,+∞)) = ∞. Pontos em regiões diferentes, como (a, b) e (p,+∞), possuem distância igual a ∞. Quando a distância for entre um ponto do plano à diagonal ∆ = {(x, x) | x ∈ R}3 d∞((x, y),∆) = inf d∞ ((x, y), (a, a)) = = max { (y − x) 2 , (y − x) 2 } = 1 2(y − x) Definição 3.22 (Distância Bottleneck). Sejam X e Y dois diagramas de persistência de mesma cardinalidade. Considere as bijeções η : X → Y , tome o supremo das distâncias entre os pontos e suas imagens correspondentes segundo a norma L∞ e o mínimo sobre todas as bijeções. Obtemos a distância bottleneck (distância de gargalo) entre os diagramas, por: W∞(X, Y ) = inf η : X→Y { sup x∈X [d∞(x, η(x))] } A ideia da distância que acabamos de ver é que dois diagramas estão próximos um do outro se existe uma bijeção entre eles que não leva a um ponto muito longe. Mostremos que a função, como definida, é de fato, uma métrica. 3A distância de um ponto ao conjunto é o ínfimo de todas as distâncias do ponto até os elementos do conjunto. No caso, a distância entre um ponto do plano à diagonal, será a distância do ponto até sua projeção ortogonal na diagonal. 42 Diagrama de Persistência • W∞(X,X) = 0 e W∞(X, Y ) > 0 Se W∞(X, Y ) = 0, significa que inf η : X→Y { sup x∈X [ d∞ ( x, η(x) )]} = 0 e ainda, que sup x∈X [ d∞ ( x, η(x) )] = 0. Seja x = (a, b) ∈ X e considere a bijeção x 7→ η(x) = (ηa, ηb), onde (ηa, ηb) será a notação usada para as coordenadas do ponto da imagem de x por η. Temos: sup x∈X [ d∞ ( x, η(x) )] = sup x∈X [max {| a− ηa |, | b− ηb |}] = 0 e ainda |x− η(x) | ⩾ 0, para cada x ∈ X. Uma vez que tomamos o máximo das distâncias, | a− ηa | = 0 = | b− ηb |, portanto, a = ηa e b = ηb. Assim, como tomamos o máximo das diferenças e temos como resultado 0, segue que para todos os x ∈ X, |x − η(x) | = 0, e portanto, x = ηx. Por tomarmos o ínfimo das bijeções, sucede que a bijeção η é a função identidade, η = Id. Logo, Y = η(X) = Id(X) = X. Reciprocamente, se X = Y , ao tomarmos o ínfimo das bijeções η : X → X, teremos que |x− Id(x) | = 0 e o resultado segue. • W∞(X, Y ) = W∞(Y,X) Como η : X → Y são bijeções, implica que existe η−1 : Y → X e, assim, x = η−1(y), para x ∈ X e para algum y ∈ Y , daí d∞ ( x, η(x) ) = d∞ ( η−1(y), η(η−1(y)) ) = d∞ ( η−1(y), y ) = d∞ ( y, η−1(y) ) , pois L∞ é métrica. Portanto, d∞ ( x, y ) = d∞ ( y, x ) e assim, temos o resultado. • W∞(X,Z) ⩽ W∞(X, Y ) +W∞(Y, Z) Para a desigualdade triangular, sejam α : X → Y e β : Y → Z bijeções. Tome η = β ◦ α : X → Z. Assim, d∞ ( x, η(x) ) = d∞ ( x, β(α(x)) ) = d∞ ( x+ α(x), β(α(x)) + α(x) ) ⩽ ⩽ d∞ ( x, α(x) ) + d∞ ( α(x), β(α(x)) ) ⩽ ⩽ sup x∈X d∞ ( x, α(x) ) + sup y∈Y d∞ ( y, β(y) ) , para todo x ∈ X. Logo, como é para qualquer elemento de X, sup x∈X d∞ ( x, β(α(x)) ) ⩽ sup x∈X d∞ ( x, α(x) ) + sup y∈Y d∞ ( y, β(y) ) Imagem de Persistência 43 Agora, como a distância Bottleneck é o ínfimo por definição, temos que: W∞(X,Z) ⩽ sup x∈X d∞ ( x, β(α(x)) ) ⩽ sup x∈X d∞ ( x, α(x) ) + sup y∈Y d∞ ( y, β(y) ) , para quaisquer bijeções α : X → Y e β : Y → Z. Em particular, W∞(X,Z) − sup x∈X d∞ ( x, α(x) ) ⩽ sup y∈Y d∞ ( y, β(y) ) , para todo β : Y → Z. Tomando o ínfimo das bijeções β : Y → Z em ambos os lados, W∞(X,Z) − sup x∈X d∞ ( x, α(x) ) ⩽ W∞(Y, Z), para todo α : X → Y . Por fim, consideramos W∞(X,Z) −W∞(Y, Z) ⩽ sup x∈X d∞ ( x, α(x) ) , para todo α : X → Y . Agora, tomando o ínfimo das bijeções α : X → Y , W∞(X,Z) −W∞(Y, Z) ⩽ W∞(X, Y ) E portanto, W∞(X,Z) ≤ W∞(X, Y ) +W∞(Y, Z), como queríamos. Assim, por W∞ satisfazer todos os três axiomas de métrica, pode ser chamado de distância. 3.4 Imagem de Persistência A distância Bottleneck é, computacionalmente, muito dispendiosa e também limitada, pois muitas técnicas de aprendizado de máquina, além das técnicas de agrupamentos, requerem mais do que uma matriz de distância de pares, como por exemplo a classificação de árvore de decisão e redes neurais. Além disso, uma representação vetorial dos diagramas de persistência possibilita o uso de métricas padrões como por exemplo, a métrica da soma (conhecida como métrica do táxi), a métrica euclidiana e a métrica infinito (3.21) (que é uma generalização da métrica do máximo). Essas medidas são mais eficientes, como poderemos ver no próximo capítulo. Para então, fazer uma representação vetorial do diagrama de persistência, uma aborda- gem utilizada é tomar cada ponto do diagrama de persistência (b, d) ∈ PD como o centro de uma distribuição normal bidimensional 4, centralizando uma Gaussiana em cada ponto e sobrepondo uma grade. Uma imagem é definida atribuindo a cada quadrado da grade 4Mais informações disponíveis em [13], página 45. 44 Diagrama de Persistência um valor de pixel. Formalmente, definimos I(p), o valor de cada pixel p dentro de uma imagem, pela seguinte equação: I(p) = ∫∫ p  ∑ (b,d)∈P D 1 2πσxσy e − 1 2 ( (x−b)2 σ2 x + (y−d)2 σ2 y ) dydx, (3.1) onde σx e σy são as variância da gaussiana na direção x e y, respectivamente, e não é assumida nenhuma correlação cruzada. Como o diagrama de persistência é um multiconjunto de pontos, permitimos várias gaussianas com o mesmo centro na soma. Esta definição de pixel pondera igualmente as gaussianas definidas em pontos próxi- mos à diagonal (que podem ser considerados como ruído) e distantes da diagonal (que representam um sinal forte). Essa ponderação pode eliminar pontos importantes do dia- grama, caso a quantidade de pontos próximos a diagonal seja grande. Para contornar este problema, usa-se uma função peso que pode ser apresentada de variadas formas. Para os cálculos deste trabalho, usamos um parâmetro n, onde a imagem é construída segundo a persistêncian, que proporciona maior relevância aos elementos fora da diagonal.5 Exemplo 3.23. Considere o complexo K0 utilizado na sessão anterior 3.7. Com auxílio do Software Geogebra, conseguimos efetuar o cálculo da somatória da equação (3.1) com o objetivo de visualizar a ideia da criação das imagens de persistência. Figura 3.10: Diferentes perfis da somatória calculada para os pontos do gráfico. Fonte: Própria autora. 5As informações desta seção foram retiradas do artigo [4]. 4 Trabalho Desenvolvido A clusterização de dados (agrupamento de dados), ganha holofotes com a informati- zação da vida, onde informações aos montes são disponibilizadas a cada segundo pelas redes. Além da problemática de dados falsos, a quantidade monstruosa dificulta uma análise assertiva sem a ajuda de ferramentas eletrônicas, que auxiliam na organização e filtragem desses dados. Quando estes dados estão planilhados, há uma gama de possibilidades acessíveis para filtração e análise. Exemplos são o Microsoft Excel e, mais atualmente, o Power BI (Bussiness Inteligence). Porém, quando as informações têm formas mais elaboradas, como imagens, a análise também se mostra mais complexa. Visto isto, o trabalho foi desenvolvido buscando possibilidades de análise e agrupa- mento para imagens em três dimensões (3D), utilizando ferramentas topológicas por meio da linguagem de programação Python. As páginas seguintes conterão a descrição do pipeline (passo a passo) das atividades realizadas para interpretar as dados, as dificuldades do processo e resultados obtidos. Todas as imagens presentes no texto foram, ou geradas pelo programa desenvolvido, ou capturas de tela de arquivos produzidos. 4.1 Banco de dados As imagens para a pesquisa são de domínio público e foram retiradas do banco de dados do curso Cos 429 de outono sobre Visão Computacional do Departamento de Informática, da Universidade de Princeton.[7] São 200 arquivos com extensão “.ply” (Polygon File Format ou Stanford Triangle For- mat)1, de variados tamanhos, divididos em 20 categorias: biplane (avião biplano), desk chair (cadeira de escritório), dining chair (cadeira de jantar), fighter jet (avião a jato), fish (peixe), flying bird (pássaro), guitar (violão), handgun (revólver), head (cabeça), heli- copter (helicóptero), human armns out (braços humanos), human (humanos), potted plant (plantas em vaso), race car (carro de corrida), sedan (carro sedan), shelves (prateleiras), ship (navio), sword (espada), table (mesa) e vase (vaso). Acrescentei à esta miscelânea, o desenho de um cubo, feito por mim no programa Blender2, para auxiliar nos testes, entendimento do processo e elaboração do programa, 1“O padrão PLY foi desenvolvido na Universidade de Stanford [. . . ] como um meio de armazenar dados 3D simples [...]. O arquivo PLY armazena objetos como uma lista de polígonos planos que podem ter as seguintes propriedades definidas: cor e transparência, descrição da superfície e coordenadas espaciais.” [12] 2“[. . . ] é um programa de computador de código aberto, desenvolvido pela Blender Foundation, para modelagem, animação, texturização, composição, renderização, edição de vídeo e criação de aplicações interativas em 3D.” [17] 45 46 Trabalho Desenvolvido já que por ser simples, possibilita verificações manuais. Na Figura 4.1 podemos ver alguns exemplos de imagens do banco de dados utilizado. (a) Biplane 0 (b) Guitar 9 (c) Untitled 3 (d) Potted plant 1 Figura 4.1: Exemplos de imagens do banco de dados. Fonte: Captura de tela pelo Fotos. É possível perceber, observando as imagens, pequenos pontos na estrutura. São eles, que sustentam os objetos e são a fonte de informação utilizada para as análises. Também se nota que, para que as formas tenham aparência mais arredondada, elas precisam de uma quantidade maior de pontos, visto que as imagens são formadas por segmentos de retas ligando os pontos, e não curvas (Figura 4.2). Diagrama de Persistência 47 (a) Shelves 7, 56 pontos. (b) Fish 7, 4.117 pontos. (c) Human 8, 148 pontos. Figura 4.2: Imagens com quantidade de pontos diferentes. Fonte: Captura de tela pelo Fotos. 4.2 Diagrama de Persistência Após o reconhecimento das imagens e categorização por meio de dicionários, as ima- gens originalmente em formato .ply foram convertidas para o formato matricial, onde as colunas equivalem aos eixos x, y e z e as linhas variam de acordo com a quantidade de pontos de cada figura. As informações obtidas foram armazenadas em um dicionário, no formato {Imagem: (matriz de pontos, quantidade de pontos)}. 1 pasta = '...' # local onde as imagens estão armazenadas 2 3 arquivos = '...' # lista de nomes dos arquivos 4 48 Trabalho Desenvolvido 5 pcds = {} # dicionário para armazenar a matriz de pontos da imagem e a quantidade de pontos↪→ 6 7 for i in arquivos: 8 pcd = o3d.io.read_point_cloud(pasta+i) # lê a nuvem de pontos dos arquivos↪→ 9 pontos = np.asarray(pcd.points) # converte o formato open3d para numpy array, (n,3)=(linhas, colunas: eixos x, y e z)↪→ 10 ponto = np.unique(pontos, axis=0) # pontos sem repetição, axis=0: percorre linhas, axis=1: percorre colunas↪→ 11 quantidade = len(ponto) # quantidade de pontos do arquivo, sem repetição↪→ 12 13 pcds.update({i: (ponto, quantidade)}) Programa 4.1: Programa para gerar as matrizes de pontos e armazenar as informações. Exemplo 4.1. Matriz de pontos e quantidade de pontos do Cubo 4.1c 1 print(pcds['untitled3.ply']) (array([[-1.52003551, 0.57333529, 0.60064852], [-1.180071, -1.26249039, -0.11640674], [-0.51576865, 1.36078799, -0.93927568], [-0.17580414, -0.47503772, -1.65633094], [0.17580414, 0.47503772, 1.65633094], [0.51576865, -1.36078799, 0.93927568], [1.180071, 1.26249039, 0.11640674], [1.52003551, -0.57333529, -0.60064852]]), 8) Para a análise topológica dos dados, por meio da homologia, os espaços são dados por complexos, que possibilitam extrair informações geométricas. Neste ponto, a informação sobre as imagens são vetores com entradas tridimensionais (valores para x, para y e z, do plano cartesiano) – as coordenadas dos pontos. Para a criação dos complexos, as informações atuais foram filtradas pelo método de Vietoris- Rips (3.1.2) e armazenados. Estes complexos criados pela filtração são utilizados no cálculo do diagrama de persistência por meio da ferramenta Rips do pacote ripser dis- ponível para Python. O diagrama foi calculado em H1 com coeficientes no corpo Z2 = {0, 1}. A escolha do H1 foi visando melhores resultados, visto que H0, que são o número de componentes conexas, retornaria a quantidade de pontos e a escolha do corpo, para simplificar os cálculos - o que exige menos para o processamento dos dados. 1 def H1(arquivo): 2 3 rips = Rips(maxdim=1, coeff=2) # maxdim: H_1, coeff: Z_2 Diagrama de Persistência 49 4 diagrama_h1 = rips.fit_transform(arquivo)[1] # [1]: H_1, [0]: H_0 e sem, calcula H_0 e H_1↪→ 5 6 return diagrama_h1 Programa 4.2: Função que calcula H1 de um arquivo, por meio de sua matriz de pontos. O cálculo do diagrama de persistência resulta em pares ordenados com informações de (nascimento, morte) dos simplexos de acordo com a filtração do complexo, que neste caso, é dado pela nuvem de pontos da imagem. 3.15 Devido a morosidade do cálculo do diagrama de persistência para imagens com muitos pontos e a limitação da máquina3, os diagramas foram gerados em blocos, de acordo com a quantidade de pontos das imagens: de 0 à 999 pontos; 1.000 à 1.999 pontos; 2.000 à 2.999 pontos e de 3.000 à 4.999. 1 # Gerar o diagrama de persistência com menos de 1000 pontos 2 3 pasta_pd = 'caminho da pasta onde os arquivos PDs serão salvos' 4 5 arquivos_menores = [] 6 7 for j in pcds.keys(): 8 if pcds[j][1] < 1000: 9 arquivos_menores.append(j) 10 pd = H1(pcds[j][0]) 11 12 # salvar o diagrama em um csv 13 pd_file = 'pd_'+j.split('.')[0]+'.csv' # string do nome do arquivo a ser criado↪→ 14 np.savetxt(pasta_pd+pd_file, pd, delimiter=',') Programa 4.3: Programa para gerar os PDs das imagens com até 1.000 pontos. Após a iteração para todas as imagens que seguiam o parâmetro posto, obteve-se uma amostra de 158 imagens, onde 100 possuem até 999 pontos, 31 de 1.000 − 1.999, 6 de 2.000 − 2.999 e, as demais 21 pertencem ao bloco de 3.000 − 4.999 pontos. Em razão desta “filtragem”, os nomes das imagens utilizadas para o estudo foram armazenados para utilização futura, como é possível observar na linha 5 do Programa 4.3. 3Os programas foram executados pelo “Google Colaboratory”. Também conhecido como “Colab”, é um produto do Google Research, área de pesquisas científicas do Google. O Colab permite que qualquer pessoa escreva e execute código Python arbitrário pelo navegador e é especialmente adequado para aprendizado de máquina, análise de dados e educação. Mais tecnicamente, o Colab é um serviço de notebooks hospedados do Jupyter que não requer nenhuma configuração para usar e oferece acesso sem custo financeiro a recursos de computação como GPUs.” [5](grifo nosso) 50 Trabalho Desenvolvido Exemplo 4.2. Pares de pontos do diagrama de persistência do Cubo 4.1c. 1 H1(pcds['untitled3.ply'][0]) Rips(maxdim=1, thresh=inf, coeff=2, do_cocycles=False, n_perm = None, verbose=True)↪→ array([[2.0, 2.82842708], [2.0, 2.82842708], [2.0, 2.82842708], [2.0, 2.82842708], [2.0, 2.82842708]]) Observando os exemplos 4.1 e 4.2, nota-se que os 8 pontos do cubo formam uma cadeia de 5 complexos, que nascem e morrem no mesmo nível de filtração. Na imagem 4.4, as barras de H1, que são 5, estão sobrepostas - por apresentarem o mesmo valor - por isso a aparência é de existir apenas um ponto. Como vimos em 3.8b, os pares de pontos da persistência de um complexo filtrado podem ser plotados em um Diagrama, chamado Diagrama de Persistência. No Pro- grama 4.4 podemos observar como o diagrama pode ser executado em Python, utilizando a ferramenta plot. 1 def PD(arquivo, pontos_pd, salvar=False, caminho_salvar=''): 2 3 if salvar and caminho_salvar == '': 4 print('Para salvar é necessário escolher um caminho') 5 return None 6 7 rips = Rips(maxdim=1, coeff=2) # calcula o diagrama de persistência 8 rips.plot(pontos_pd, labels='H_1') # plota o diagrama de persistência 9 plt.title('Diagrama de persistência: {}'.format(arquivo.split('.')[0]))↪→ 10 if salvar: 11 plt.savefig(caminho_salvar+arquivo.split('.')[0]+'.png') 12 gráfico = plt.show() 13 14 return gráfico Programa 4.4: Função para exibir o diagrama de persistência de uma imagem. Diagrama de Persistência 51 (a) Flying Bird 0, 233 pontos. (b) Helicopter 9, 1.201 pontos. (c) Sedan 7, 2.170 pontos. (d) Guitar 5, 4.694 pontos. Figura 4.3: PDs de imagens com diferente quantidade de pontos Exemplo 4.3. Diagrama de persistência do Cubo 4.1c. 1 pontos_pd_cubo=np.array([[2, 2.82842708], [2, 2.82842708], [2, 2.82842708], [2, 2.82842708], [2, 2.82842708]])↪→ 2 3 PD('untitled3.ply', pontos_pd_cubo, salvar=True, caminho_salvar='onde salvar a imagem')↪→ 52 Trabalho Desenvolvido Figura 4.4: Diagrama de Persistência do Cubo. 4.3 Imagem de Persistência Como visto na seção 3.4, do capítulo anterior, a imagem de persistência (PI) é uma forma de representar as informações dos pares de persistência de um complexo, por meio de um vetor. Para gerar a imagem utilizamos o pacote PersistenceImager da biblioteca persim. Ele permite a escolha de parâmetros para a criação das imagens, são eles: • Resolução da Imagem: a resolução corresponde ao tamanho do pixel, ao tamanho da grade quadriculada que será posta sobre a imagem. • Distribuição: é o método de distribuição de probabilidade que será associado aos pontos do diagrama de persistência. • Ponderação: a ponderação é usada para ajustar os dados de forma a obter re- presentações mais fidedignas. No diagrama de persistência, os pontos próximos às diagonais são considerados ruídos, isto é, têm pequena relevância para os resultados; e, se em grande número, podem maquiar a imagem, destacando pontos não impor- tantes. Assim, a ponderação permite que pontos com maior persistência ganhem pesos maiores para ganhar destaque nas imagens. O programa irá analisar os dados de persistência segundo os parâmetros escolhidos e gerar uma matriz de pontos (o tamanho da matriz está relacionado ao tamanho do pixel, tamanho dos pontos e tamanho dos eixos escolhidos). Posteriormente, os dados da matriz são renderizados (processados digitalmente), resultando em uma imagem pseudo- colorida4. 4A imagem pseudo-colorida relaciona cores à valores, segundo um fatiamento de intensidade. [19] Imagem de Persistência 53 Figura 4.5: Escala de cor utilizada para colorir as imagens. 1 def PI_peso(caminho_pasta_arquivos, nome_arquivo, pixel, n, 2 salvar=False, caminho_salvar=''): 3 4 if salvar and caminho_salvar == '': 5 print('Para salvar é necessário escolher um caminho') 6 return None 7 8 arquivos = caminho_pasta_arquivos 9 string = nome_arquivo 10 sigma = 0.5 11 n = n 12 p = pixel 13 14 nome = arquivos+string 15 a = np.loadtxt(nome, delimiter=',') 16 a = a*100 17 18 maior = max(max(a[:, 0]), max(a[:, 1])) 19 20 pimgr = PersistenceImager(pixel_size=p, weight_params={'n': n}, 21 kernel_params={'sigma': [[sigma, 0], 22 [0, sigma]]}, birth_range=(0, maior*1.10), 23 pers_range=(0, maior*1.10)) 24 pimg = pimgr.transform(a) 25 if salvar: 26 np.savetxt(caminho_salvar+'nome_salvar'+'.csv', pimg, 27 delimiter=',') 54 Trabalho Desenvolvido 28 29 # diagrama de persistância 30 31 rips = Rips(maxdim=1, coeff=2) 32 33 # persitência x nascimento 34 35 pimgr.plot_diagram(a) 36 if salvar: 37 plt.savefig(caminho_salvar+'nome_salvar'.png') 38 plt.show() 39 40 # gerar imagem de persistência 41 42 plt.title('Imagem de Persistência: {}'.format(string)) 43 pimgr.plot_image(pimg) 44 if salvar: 45 plt.savefig(caminho_salvar+'nome_salvar'+'.png') 46 plt.show() Programa 4.5: Função para gerar o diagrama de persistência (nascimento, persistência) e imagem de persistência com peso. 1 def PI(caminho_pasta_arquivos, nome_arquivo, pixel, salvar=False, 2 caminho_salvar=''): 3 4 if salvar and caminho_salvar == '': 5 print('Para salvar é necessário escolher um caminho') 6 return None 7 8 arquivos = caminho_pasta_arquivos 9 string = nome_arquivo 10 p = pixel 11 12 nome = arquivos+string 13 a = np.loadtxt(nome, delimiter=',') 14 a = a*100 15 16 maior = max(max(a[:, 0]), max(a[:, 1])) 17 18 pimgr = PersistenceImager(pixel_size=p, birth_range=(0, maior*1.10), 19 pers_range=(0, maior*1.10)) 20 pimg = pimgr.transform(a) 21 if salvar: 22 np.savetxt(caminho_salvar+'nome_salvar+'.csv', pimg, 23 delimiter=', ') 24 25 # gerar imagem de persistência 26 Imagem de Persistência 55 27 plt.title('Imagem de Persistência: {}'.format(string)) 28 pimgr.plot_image(pimg) 29 if salvar: 30 plt.savefig(caminho_salvar+'nome_salvar'+'.png') 31 plt.show() Programa 4.6: Função para gerar a imagem de persistência. Nesta pesquisa, foi usada uma resolução de 0.1 pixel, com Distribuição Gaussiana. Foram geradas imagens com e sem ponderação para comparação dos resultados obtidos. É importante observar que, diferentemente do Diagrama de Persistência, as imagens são construídas pelo par (nascimento, persistência). Por esta razão, foram construídos diagramas com este par para facilitar a comparação dos resultados obtidos. As imagens geradas pelo programa podem ser conferidas em 4.6, 4.7, 4.8 e 4.9. (a) PD (n,p) (b) PI padrão (c) PI com peso Figura 4.6: Table 3, 56 pontos. (a) PD (n,p) (b) PI padrão (c) PI com peso Figura 4.7: Potted Plant 8, 1.325 pontos. 56 Trabalho Desenvolvido (a) PD (n,p) (b) PI padrão (c) PI com peso Figura 4.8: Head 5, 2.034 pontos. (a) PD (n,p) (b) PI padrão (c) PI com peso Figura 4.9: Fighter Jet 1, 4.427 pontos. Exemplo 4.4. Imagem de persistência do Cubo (4.1c). (a) PD (n,m) (b) PD (n,p) (c) PI padrão (d) PI com peso 4.4 Distância entre os Diagramas de Persistência 4.4.1 Distância Bottleneck Como visto na Seção 3.3, essa distância encontra o mínimo de todas as bijeções possí- veis entre todos os pontos. Ela foi usada para comparar a distância entre os diagramas de persistência. Como as imagens possuem um número grande de pontos, seus respectivos Distância entre os Diagramas de Persistência 57 diagramas também contém. Logo, calcular todas alternativas, foi um processo extrema- mente demorado, levando 15.818, 04 minutos, isto é, cerca de 10, 98 dias. 1 pasta_pd = '...' # caminho da pasta dos arquivos PDs 2 3 pasta = os.listdir(pasta_pd) 4 t = len(pasta) 5 6 distâncias = np.zeros((t, t)) 7 8 tempos = np.zeros((t, t)) 9 10 for i in [10]: # a linhas foram iteradas de forma manual 11 for j in range(i+1, t): 12 13 print(i, j) 14 15 s_time = time.process_time() 16 17 a = os.listdir(pasta_pd)[i] 18 b = os.listdir(pasta_pd)[j] 19 20 print('Distância de %s até %s' % (a, b)) 21 22 a1 = np.loadtxt(pasta_pd+a, delimiter=',') 23 b1 = np.loadtxt(pasta_pd+b, delimiter=',') 24 25 distance_bottleneck, matching = persim.bottleneck(a1, b1, 26 matching=True) 27 28 distâncias[i, j] = distance_bottleneck 29 30 e_time = time.process_time() 31 tempos[i, j] = e_time-s_time 32 33 print('*Distância: %.4f, tempo de execução: %.2f segundos.' % 34 (distâncias[i, j], tempos[i, j])) 35 36 # aqui salvar as distâncias em um csv 37 38 f = open('caminho do arquivo', 'a') # (nome do arquivo a ser criado/aberto, r=read / a=apend)↪→ 39 np.savetxt(f, distâncias[i], newline=',') # (onde salvar, o que acrescentar, como separar a próxima informação - se não colocar nada vai pra próxima linha) ↪→ ↪→ 40 f.write("\n") # encerra a linha que foi acrescentada e cria uma nova 41 f.close() # fecha o arquivo 42 43 # aqui salvar o tempo de execução em um csv 44 58 Trabalho Desenvolvido 45 g = open('caminho do arquivo', 'a') 46 np.savetxt(g, tempos[i], fmt='%.2f', newline=',') 47 g.write("\n") 48 g.close() Programa 4.7: Calcular a distância bottleneck entre os Diagramas de Persistência. A ideia foi comparar a distância entre todos os diagramas de persistência obtidos, ou seja, cada diagrama foi comparado com outros 157. Para diminuir o tempo de pro- cessamento, as informações foram armazenadas em uma Matriz158x158 superior, iteradas manualmente linha à linha utilizando o Programa 4.7 e exportadas para um arquivo de texto (.csv)5. Após feito, organizou-se as informações tornando a matriz simétrica e referenciando o nome das imagens de acordo com as distâncias calculadas, por meio das funções 4.8 e 4.9 definidas abaixo, resultando na matriz da Figura 4.11. Figura 4.11: Recorte da matriz de distância Bottleneck. 1 def simetrica(caminho_arquivo, salvar=False): 2 3 arquivo = np.genfromtxt(caminho_arquivo, delimiter=',')[:, :-1] # [linhas, colunas]↪→ 4 5 matriz_simétrica = arquivo+arquivo.T 6 7 # salvar o arquivo alterado 8 if salvar: 9 np.savetxt(caminho_arquivo, matriz_simétrica, delimiter=',') 5“Um arquivo CSV (Valores Separados por Vírgula) é um tipo especial de arquivo que [...] em vez de armazenar informações em colunas, [...] armazenam informações separadas por vírgulas” [8] Distância entre os Diagramas de Persistência 59 10 11 return matriz_simétrica Programa 4.8: Função para tornar uma matriz simétrica quando precisa excluir última coluna vazia. 1 def rotulos(caminho_arquivo, caminho_nome, salvar=False): 2 3 nome = np.loadtxt(caminho_nome, delimiter=',', dtype=str) 4 arquivo = pd.read_csv(caminho_arquivo, sep=',', header=None) 5 6 arquivo.columns = nome # inserir nome das colunas 7 arquivo.index = nome # inserir coluna de índices 8 9 if salvar: 10 arquivo.to_csv(caminho_arquivo, index=True) 11 12 return arquivo Programa 4.9: Função para inserir nome das colunas e índices, em uma matriz. Por meio da matriz, é possível conhecer a distância topológica entre quaisquer imagens do estudo. Porém, como a matriz é extensa, não está claro quais delas são mais ou menos próximas. Para facilitar a análise, criou-se uma função que filtra as imagens que são mais próxi- mas, como definido no Programa 4.10. Na distância bottleneck, o parâmetro de distância máxima escolhido foi de 0, 01. Teste com números maiores, trouxeram uma lista de tamanho considerável e com medida 0, 001, retornou uma lista vazia, ou seja, nenhuma imagem tem distância menor do que 0, 001. Parte da matriz resultante pode ser observada na imagem 4.12. 1 def filtro(caminho_arquivo, parâmetro): 2 3 arquivo = pd.read_csv(caminho_arquivo, delimiter=',', header=None) 4 5 nome_novo = caminho_arquivo[:-4] 6 nome_parâmetro = str(parâmetro) 7 arquivo_novo = nome_novo+' menor que '+nome_parâmetro+'.csv' 8 9 n = np.size(arquivo, 0) 10 11 # criar arquivo novo com uma linha 12 13 vetor = np.arange(1, n+1) 14 15 g = open(arquivo_novo, 'a+') 16 np.savetxt(g, vetor, newline=',', fmt='%d') 17 g.write('\n') 18 g.close() 60 Trabalho Desenvolvido 19 20 # filtrar distâncias menores que um parâmetro 21 22 parecidos = {} 23 24 for i in range(1, n): 25 nome_linha = arquivo.iloc[i, 0] 26 for j in range(1, n-1): 27 distância = arquivo.iloc[i, j] 28 nome_coluna = arquivo.iloc[0, j] 29 if float(distância) < parâmetro and float(distância) != 0: 30 if nome_linha in parecidos.keys(): 31 parecidos[nome_linha].append(nome_coluna) 32 else: 33 parecidos[nome_linha] = [nome_coluna] 34 else: 35 continue 36 37 # salvar o nome dos arquivos em um csv 38 39 if nome_linha in parecidos.keys(): 40 g = open(arquivo_novo, 'a+') 41 np.savetxt(g, parecidos[nome_linha], fmt='%s', newline=',') 42 g.write('\n') 43 g.close() 44 45 print(parecidos) 46 47 # excluir colunas vazias e acrescentar o índice no arquivo novo 48 49 arquivo2 = pd.read_csv(arquivo_novo, delimiter=',') 50 51 arquivo2 = arquivo2.dropna(how='all', axis=1) 52 arquivo2.index = parecidos.keys() 53 54 arquivo2.to_csv(arquivo_novo, index=True) Programa 4.10: Função para filtrar as imagens mais próximas. Distância entre os Diagramas de Persistência 61 Figura 4.12: Recorte da matriz de imagens que possuem distância bottleneck menor do que 0, 01. Objetivando comparar visualmente estas imagens ditas parecidas, imagens de seus pontos foram gerados por meio da função descrita no programa 4.11. 1 def grafico(caminho_arquivo, nome_arquivo, caminho_pasta_imagens, 2 salvar=False, caminho_salvar='', tipo=''): 3 4 if salvar and caminho_salvar == '': 5 print('Para salvar é necessário escolher um caminho') 6 return None 7 8 arquivo = pd.read_csv(caminho_arquivo) 9 n = len(arquivo.columns) 10 11 linha = arquivo.loc[arquivo.iloc[:, 0] == nome_arquivo] # arquivo.iloc[linha,coluna]↪→ 12 13 for j in range(0, n): 14 nome = str(linha.iloc[0, j]) 15 if nome != 'nan': 16 pcd = o3d.io.read_point_cloud(caminho_pasta_imagens+'/'+nome) # ler a nuvem de pontos "point cloud" dos arquivos↪→ 17 pontos = np.asarray(pcd.points) 18 fig = px.scatter_3d(x=pontos[:, 0], y=pontos[:, 1], 19 z=pontos[:, 2], title=nome) 20 fig.update_layout(scene_camera=dict(up=dict(x=0, y=2, z=0), 21 center=dict(x=0, y=0, z=0), 22 eye=dict(x=-2, y=1, z=2.5)), 23 scene=dict(xaxis=dict( 24 backgroundcolor='white', 25 color='black', gridcolor='#f0f0f0', 26 title_font=dict(size=8), 27 tickfont=dict(size=8)), 28 yaxis=dict(backgroundcolor='white', 29 color='black', gridcolor='#f0f0f0', 30 title_font=dict(size=8), 31 tickfont=dict(size=8)), 32 zaxis=dict(backgroundcolor='white', 33 color='black', gridcolor='#f0f0f0', 62 Trabalho Desenvolvido 34 title_font=dict(size=8), 35 tickfont=dict(size=8)))) 36 fig.update_traces(marker=dict(size=3, 37 line=dict(color='black',width=0.1))) 38 fig.update(layout_coloraxis_showscale=False) 39 if salvar and tipo == 'png': 40 fig.write_image('nome_imagem'+'.png') 41 if salvar and tipo == 'html': 42 fig.write_html('nome_imagem'+'.html') 43 fig.show() Programa 4.11: Função que exibe a nuvem de pontos das imagens filtradas. Foram escolhidas as imagens próximas à Fighter jet 9, linha 4 da tabela 4.12 para serem geradas, como exemplo. (a) Fighter jet 9 (b) Biplane 6 Figura 4.14: Imagem próxima à Fighter jet 9. Além da nuvem de pontos, a Figura 4.14 destaca a imagem original e o diagrama de persistência, visto que os cálculos da distância utilizam a informação deste. A seguir, encontra-se o programa 4.12 criado para o cálculo e exibição do gráfico referente a distância entre duas imagens. Distância entre as Imagens 63 1 def bottle(caminho_pasta_pd, nome_arquivo1, nome_arquivo2, salvar=False, 2 caminho_salvar=''): 3 4 if salvar and caminho_salvar == '': 5 print('Para salvar é necessário escolher um caminho') 6 return None 7 8 arquivo1 = np.loadtxt(pasta_pd+'/pd_'+nome_arquivo1+'.csv', 9 delimiter=',') 10 arquivo2 = np.loadtxt(pasta_pd+'/pd_'+nome_arquivo2+'.csv', 11 delimiter=',') 12 13 distancia_bottleneck, matching = persim.bottleneck(arquivo1, arquivo2, 14 matching=True) 15 persim.bottleneck_matching(arquivo1, arquivo2, matching, 16 labels=['{} $H_1$'.format(nome_arquivo1), 17 '{} $H_1$'.format(nome_arquivo2)]) 18 plt.title("Distância {:.4f}".format(distancia_bottleneck)) 19 if salvar: 20 plt.savefig(caminho_salvar+'nome arquivo'+'.png') 21 plt.show() Programa 4.12: Função para calcular a distância Bottleneck entre dois diagramas de persistência e gerar o gráfico. Figura 4.15: Distância Bottleneck entre Fighter Jet 9 e Biplane 6. 4.5 Distância entre as Imagens As imagens de persistência são representações vetoriais dos pares – (nascimento, per- sistência) – de um complexo simplicial filtrado. 64 Trabalho Desenvolvido A informação matricial de uma imagem de persistência pode ser representada de forma pseudo-colorida, de acordo com os parâmetros escolhidos, como vimos na seção 4.3. Estas matrizes possibilitam a comparação entre as imagens de forma simplificada e computacionalmente rápida. Basta medir a distância entre as respectivas entradas das matrizes por meio de uma métrica. Para este trabalho, as comparações foram feitas em três métricas6: Euclidiana, do Máximo e da Soma, utilizando a biblioteca scipy.spatial.distance do Python, que calcula estas distâncias de forma automática. Observando as Figuras 4.6, 4.7, 4.8 e 4.9, imagem (a), é possível notar que o tamanho dos eixos de cada gráfico diferem. Isto acontece devido à filtração de cada imagem, ou seja, ao tamanho do nascimento e persistência de cada simplexo. Então, para que a comparação seja possível, é preciso que as imagens tenham um tama- nho padrão e, por consequência, uma matriz de mesma dimensão. Para isso, verificou-se os intervalos de nascimento e persistência de cada imagem e foi tomado o maior deles, como descreve o Programa 4.13. 1 pasta_pd = '...' # caminho da pasta dos PDs 2 3 maior_nascimento = 0 4 menor_nascimento = 100 5 6 maior_persistencia = 0 7 menor_persistencia = 100 8 9 for i in os.listdir(pasta_pd): 10 pd = np.loadtxt(pasta_pd+i, delimiter=',') 11 pd = pd*10 12 13 maior_n = max(pd[:, 0]) 14 menor_n = min(pd[:, 0]) 15 16 maior_p = max(pd[:, 1]-pd[:, 0]) 17 menor_p = min(pd[:, 1]-pd[:, 0]) 18 19 if maior_n > maior_nascimento: 20 maior_nascimento = maior_n 21 22 if menor_n < menor_nascimento: 23 menor_nascimento = menor_n 24 25 if maior_p > maior_persistencia: 26 maior_persistencia = maior_p 27 28 if menor_p < menor_persistencia: 29 menor_persistencia = menor_p 30 31 print('O menor nascimento é %.4f e o maior nascimento é %.4f' % 32 (menor_nascimento, maior_nascimento)) 33 print('A menor persistência é %.4f e a maior persistência é %.4f' % 6Disponível em: https://eu-provo.blogspot.com/2022/06/metrica.html. https://eu-provo.blogspot.com/2022/06/metrica.html Distância entre as Imagens 65 34 (menor_persistencia, maior_persistencia)) Programa 4.13: Encontrar tamanho ideal para intervalo de nascimento e persistência. O menor nascimento é 0.0000 e o maior nascimento é 20.0000 A menor persistência é 0.0000 e a maior persistência é 8.2843 Agora, com a informação de intervalo ideal, foram escolhidos os intervalo de nasci- mento [0, 21) e persistência [0, 9) e, assim, novas imagens de persistência foram geradas. Proporcionando matrizes de tamanho 210 × 90. Para criar as novas imagens, foi utilizado o Programa 4.5, alterando a=a*10 (para gerar uma matriz menor), excluindo o valor maior e mudando os intervalos dos eixos: birth_range=(0, 21) e pers_range=(0, 9). Exemplo 4.5. Imagem de persistência da figura Table 0 gerada com o novo intervalo. # matriz Imagem de Persistência com peso, Table 0 [[4.43687043e-05 4.55904777e-05 4.59203323e-05 ... 4.92015251e-41 4.92015251e-41 4.92015251e-41] [5.07785578e-05 5.21780197e-05 5.25566964e-05 ... -7.02544954e-27 -7.02544954e-27 -7.02544954e-27] [5.69705388e-05 5.85418491e-05 5.89678858e-05 ... 3.93613845e-40 3.93613845e-40 3.93613845e-40] ... [0.00000000e+00 0.00000000e+00 0.00000000e+00 ... 0.00000000e+00 0.00000000e+00 0.00000000e+00] [0.00000000e+00 0.00000000e+00 0.00000000e+00 ... 0.00000000e+00 0.00000000e+00 0.00000000e+00] [0.00000000e+00 0.00000000e+00 0.00000000e+00 ... 0.00000000e+00 0.00000000e+00 0.00000000e+00]] (210, 90) # dimensão da matriz (colunas, linhas) Para fins de comparação, também foram geradas informações com o Programa 4.6 com as mesmas alterações anteriores, mantendo apenas a característica de que estas, serão imagens padrão, sem alteração do peso. # matriz Imagem de Persistência, Table 0 [[2.58341637e-03 2.61237989e-03 2.61550571e-03 ... 2.12176010e-20 1.00305745e-20 4.62959311e-21] [2.75012925e-03 2.78117233e-03 2.78470842e-03 ... 3.42070664e-20 1.56886907e-20 7.19962957e-21] [2.89938850e-03 2.93232708e-03 2.93626392e-03 ... 5.40048043e-20 66 Trabalho Desenvolvido 2.57180156e-20 1.13187536e-20] ... [0.00000000e+00 0.00000000e+00 0.00000000e+00 ... 0.00000000e+00 0.00000000e+00 0.00000000e+00] [0.00000000e+00 0.00000000e+00 0.00000000e+00 ... 0.00000000e+00 0.00000000e+00 0.00000000e+00] [0.00000000e+00 0.00000000e+00 0.00000000e+00 ... 0.00000000e+00 0.00000000e+00 0.00000000e+00]] (210, 90) (a) PD (n,p) (b) PI com peso (c) PI padrão Figura 4.16: Table 0, 60 pontos. Exemplo 4.6. Imagem de persistência do Cubo 4.1c após ajuste de intervalos. # matriz Imagem de Persistência com peso, Untitled 3 [[7.62851927e-201 3.91005281e-200 1.96449915e-199 ... 1.53806986e-171 1.38757027e-171 1.22705062e-171] [4.06076038e-199 2.08137215e-198 1.04572854e-197 ... 8.18734663e-170 7.38621766e-170 6.53175059e-170] [2.11883045e-197 1.08602189e-196 5.45642015e-196 ... 4.27200763e-168 3.85399320e-168 3.40814792e-168] ... [1.70471125e-028 8.73762097e-028 4.38997882e-027 ... 3.43705626e+001 3.10074152e+001 2.74203540e+001] Distância entre as Imagens 67 [1.45304610e-028 7.44769305e-028 3.74188980e-027 ... 2.92964642e+001 2.64298156e+001 2.33723093e+001] [1.21404985e-028 6.22270043e-028 3.12642574e-027 ... 2.44777972e+001 2.20826535e+001 1.95280442e+001]] (210, 90) (a) PD (n,p) (b) PI com peso (c) PI padrão Figura 4.17: Cubo - untitled3, 8 pontos. Depois de todos os ajustes nas imagens, as distâncias entre as matrizes com infor- mações das Imagens de Persistência foram calculadas, gerando seis arquivos diferentes: Distância Euclidiana para imagens com e sem peso, Distância do Máximo para imagens com e sem peso e Distância da Soma para imagens com e sem peso. 1 def distancia(caminho_arquivo, distância='euclidiana', salvar=False, 2 caminho_salvar='', nome_arquivo=''): 3 4 if salvar and caminho_salvar == '': 5 print('Para salvar é necessário escolher um caminho') 6 return None 7 8 # filtrar arquivos da pasta 9 10 arquivos = [] 11 12 for i in os.listdir(caminho_arquivo): 13 if i.endswith('.csv'): 68 Trabalho Desenvolvido 14 arquivos.append(i) 15 16 n = len(arquivos) 17 18 # criar matrizes para distâncias e tempos 19 20 matriz_distancia = np.zeros((n, n)) 21 matriz_tempo = np.zeros((n, n)) 22 23 for i in range(n): 24 for j in range(i+1, n): 25 26 tempo_inicial = time.process_time() 27 28 print('*Distância de %s até %s' % (arquivos[i], arquivos[j])) # mensagem criada para acompanhar o processo↪→ 29 30 # ler arquivo 31 a1 = np.loadtxt(caminho_arquivo+'/'+arquivos[i], 32 delimiter=',') 33 b1 = np.loadtxt(caminho_arquivo+'/'+arquivos[j], 34 delimiter=',') 35 36 # vetorizar a matriz 37 a2 = a1.flatten() 38 b2 = b1.flatten() 39 40 # calcular as distâncias 41 if distância == 'euclidiana': 42 distancia = ssd.euclidean(a2, b2) 43 if distância == 'máximo': 44 distancia = ssd.chebyshev(a2, b2) 45 if distância == 'soma': 46 distancia = ssd.cityblock(a2, b2) 47 48 # guardar as informações nas matrizes 49 tempo_final = time.process_time() 50 51 matriz_distancia[i, j] = distancia 52 matriz_tempo[i, j] = tempo_final-tempo_inicial 53 54 print('Distância %s: %.4f, tempo de execução: %.4f segundos.' 55 % (distância, matriz_distancia[i, j], 56 matriz_tempo[i, j])) 57 58 # salvar informações 59 60 if salvar: 61 62 # salvar as distâncias em um csv Distância entre as Imagens 69 63 arquivo_salvar = open(caminho_salvar+'nome arquivo.csv', 'a') # (nome do arquivo a ser criado/aberto, r=read, a=apend)↪→ 64 np.savetxt(arquivo_salvar, matriz_distancia[i], newline=',') # (onde salvar, o que acrescentar, como separar a próxima informação - se não colocar nada vai pra próxima linha) ↪→ ↪→ 65 arquivo_salvar.write("\n") # encerra a linha que foi acrescentada e cria uma nova↪→ 66 arquivo_salvar.close() # fecha o arquivo 67 68 # salvar o tempo de execução em um csv 69 arquivo_tempo = open(caminho_salvar +'nome_arquivo.csv', 'a') 70 np.savetxt(arquivo_tempo, matriz_tempo[i], fmt='%.4f', 71 newline=',') # fmt: qual o formato que você deseja salvar, neste caso, um número com 4 casas decimais ↪→ ↪→ 72 arquivo_tempo.write("\n") 73 arquivo_tempo.close() 74 75 return matriz_distancia Programa 4.14: Função para calcular distância entre as matrizes das imagens de persistência. Este programa 4.14 é único para as três métricas, sendo suficiente a alteração da opção distância. As matrizes geradas, são apenas numéricas, superiores e possuem a última coluna vazia, pela forma como foram construídas e gravadas – por linhas. Objetivando torná-las mais claras, além da exclusão da coluna vazia; o nome dos arquivos foram inseridos como índices para linhas e colunas, por meio dos programas 4.8 e 4.9. Desta forma, ao abrir o arquivo gerado, é possível encontrar a distância entre duas imagens, procurando pela linha e coluna correspondentes. 4.5.1 Distância Euclidiana A métrica Euclidiana é a mais conhecida dentre as três, utilizada desde o ensino básico. Esta métrica encontra o caminho mais curto entre dois pontos, e seu algoritmo é obtido pelo Teorema de Pitágoras. Definição 4.7 (Distância Euclidiana). Considere o espaço euclidiano Rn. Sejam as n- uplas p = (x1, . . . , xn) e q = (y1, . . . , yn), que são pontos deste espaço. Temos: Deucliana(p, q) = √ (x1 − y1)2 + · · · + (xn − yn)2 Exemplo 4.8. Considere os pontos A = (2, 3) e B = (6, 6) do plano. Temos que a distância euclidiana entre eles é dada por: Deucliana(A,B) = √ (2 − 6)2 + (3 − 6)2 = √ 16 + 9 = √ 25 = 5 70 Trabalho Desenvolvido As Figuras 4.18 e 4.19 são as matrizes de distância euclidiana resultantes, geradas pelos Programas 4.14, 4.8 e 4.9. Para calcular a Distância Euclidiana, foram necessários 16, 49 minutos e para a Distância Euclidiana para as imagens com peso, 15, 71 minutos. Figura 4.18: Recorte da matriz de distância euclidiana. Distância entre as Imagens 71 Figura 4.19: Recorte da matriz de distância euclidiana das imagens com peso. Como já dito, é possível conhecer a distância entre as imagens por observação, pela facilidade que os índices proporcionam. Nota-se também, que o parâmetro peso na criação das imagens influencia diretamente nas distâncias entre elas. Porém, como a matriz gerada é muito grande, não é possível perceber quais imagens são mais próximas, isto é, mais parecidas segundo os cálculos realizados. Assim, utilizou-se o Programa 4.10 para constatar e destacar quais se assemelham. Para uma distância escolhida, o programa retorna um dicionário, como abaixo, e cria uma matriz que elenca o nome das imagens que apresentam tal proximidade, como em 4.18 e 4.19. Figuras que não estão dentro deste parâmetro, não são citadas. # imagens (sem peso) com distância de até 0.01 {'biplane4.ply': ['ship6.ply'], 'desk_chair1.ply': ['human3.ply'], 'desk_chair2.ply': ['dining_chair6.ply'], 'desk_chair7.ply': ['dining_chair0.ply', 'dining_chair6.ply', 'fish3.ply', 'handgun2.ply'], [...], 'ship3.ply': ['flying_bird5.ply'], 'ship6.ply': ['biplane4.ply', 'flying_bird9.ply'], 'ship9.ply': ['handgun7.ply', 'human4.ply', 'handgun8.ply']} ↪→ ↪→ ↪→ ↪→ ↪→ A diferença entre distâncias resultantes é grande, como podemos perceber nos trechos exibidos nas Figuras 4.18 e 4.19. Sendo assim, foram usados critérios diferentes nas filtragens das imagens com e sem peso para obter um melhor resultado. 72 Trabalho Desenvolvido Figura 4.20: Matriz de Imagens padrão que possuem distância euclidiana menor do que 0, 01. Figura 4.21: Matriz de Imagens com peso que possuem distância euclidiana menor do que 0, 0001. Os filtros gerados causam um certo estranhamento ao entender como próximas, figuras diferentes, como por exemplo biplane 4 e ship 6, na segunda linha da Figura 4.20. Para observação, foi construído um código para gerar a nuvem dos pontos das figuras classificadas semelhantes. As figuras abaixo mostram as imagens originais em 3D, sua nuvem de pontos e o Diagrama de Persistência, para comparação ocular. Distância entre as Imagens 73 (a) Biplane 4 (b) Ship 6 Figura 4.23: Imagem próxima à Biplane 4 - linha 2 da Figura 4.20. (a) Helicopter 8 74 Trabalho Desenvolvido (b) Ship 8 Figura 4.25: Imagem próxima à Helicopter 8 - linha 9 da Figura 4.21. É importante observar que a semelhança entre as imagens, é topológica e pode ser melhor entendida ao observar os diagramas de persistência, que foram acrescentados com este objetivo particular. A seguir, serão feitas as mesmas comparações que nesta subseção, porém com as métricas do máximo e da soma. 4.5.2 Distância do Máximo A métrica do máximo, também conhecida como métrica de Chebyshév ou do tabuleiro de xadrez, é uma das principais métricas da topologia e é definida como segue. Definição 4.9 (Distância do Máximo). Considere o espaço euclidiano Rn. Sejam as n-uplas p = (x1, . . . , xn) e q = (y1, . . . , yn), que são pontos deste espaço. Temos: Dmáximo(p, q) = max { |x1 − y1 |, . . . , |xn − yn | } . Exemplo 4.10. Considere os pontos A = (2, 3) e B = (6, 6) do plano. Temos que a distância do máximo entre eles é dada por: Dmáximo(A,B) = max { | 2 − 6 |, | 3 − 6 | } = max{4, 3} = 4. Distância entre as Imagens 75 Para as imagens de persistência com e sem pesos, foram geradas as seguintes ma- trizes de distância. Sendo que levaram 17 minutos para as distâncias entre as imagens padrão 4.26 e 16, 25 minutos para o cálculo entre as imagens com peso 4.27. Figura 4.26: Parte da matriz de distância do máximo. 76 Trabalho Desenvolvido Figura 4.27: Parte da matriz de distância do máximo das imagens com peso. Utilizando o mesmo programa 4.10, com um parâmetro máximo de 0, 001 para imagens padrão e de 0, 00001 para imagens com peso, obtivemos os arquivos listados nas Figuras 4.28 e 4.29. Figura 4.28: Matriz de Imagens padrão que possuem distância do máximo menor do que 0, 001. Figura 4.29: Matriz de Imagens padrão que possuem distância do máximo menor do que 0, 00001. Distância entre as Imagens 77 Dentre as comparações realizadas, as imagens próximas à Desk chair 1 da linha 4 da Figura 4.28 e à Fish 5 da linha 4 da Figura 4.29 foram geradas para observação. (a) Deskchair 1 (b) Human 3 Figura 4.31: Imagem próxima à Deskchair 1 - linha 4 da Figura 4.28. (a) Fish 5 78 Trabalho Desenvolvido (b) Ship 5 Figura 4.33: Imagem próxima à Fish 5 - linha 4 da Figura 4.29. 4.5.3 Distância da Soma Por fim, a métrica da soma, também conhecida como métrica de Manhattan ou ainda, como métrica do táxi, tem como ideia medir a distância entre dois pontos “contornando quarteirões”. Definição 4.11 (Distância da Soma). Considere o espaço euclidiano Rn. Sejam as n-uplas p = (x1, . . . , xn) e q = (y1, . . . , yn), que são pontos deste espaço. Temos: Dsoma(p, q) = |x1 − y1 | + · · · + |xn − yn |. Exemplo 4.12. Considere os pontos A = (2, 3) e B = (6, 6) do plano. Temos que a distância da soma entre eles é dada por: Ds(A,B) = | 2 − 6 | + | 3 − 6 | = 4 + 3 = 7. Distância entre as Imagens 79 Para esta métrica, foram produzidos os resultados a seguir. O tempo gasto para gerar a matriz de distância entre as imagens padrão 4.34 foi de 16, 47 minutos e dentre as imagens com peso 4.35, um tempo de 15, 81 minutos. Figura 4.34: Parte da matriz de distância da soma. Figura 4.35: Parte da matriz de distância da soma das imagens com peso. Utilizando o mesmo programa 4.10, utilizando um parâmetro máximo de 0.1 para as imagens padrão e de 0.001 para imagens com peso, obtivemos os arquivos 4.36 e 4.37. 80 Trabalho Desenvolvido Figura 4.36: Matriz de Imagens padrão que possuem distância da soma menor do que 0, 1. Figura 4.37: Matriz de Imagens padrão que possuem distância do máximo menor do que 0, 001. Dentre as comparações realizadas, as imagens próximas à Fish 2 da linha 3 da Fi- gura 4.36 e à Flying Bird 4 da linha 4 da Figura 4.37 foram geradas para observação. Distância entre as Imagens 81 (a) Fish 2 (b) Fish 4 Figura 4.39: Imagem próxima à Fish 2 - linha 3 Figura 4.36. (a) Flying Bird 4 82 Trabalho Desenvolvido (b) Deskchair 1 Figura 4.41: Imagem próxima à Flying Bird 4 - linha 4 da Figura 4.37. 5 Resultados No capítulo anterior, os dados foram preparados: gerados, organizados e filtrados e estão prontos para serem analisados. Serão feitas três análises: o Escalonamento Multidimensional, a construção de Den- drogramas e a utilização do algoritmo K-means. 5.1 MDS - Multidimensional Scaling A técnica do Escalonamento Multidimensional é usada para representar espa- cialmente, em 2D ou 3D, uma matriz de proximidades (semelhança ou disse- melhança) entre uma série de objetos de modo que possam ser mais facilmente visualizados.1 Existem dois tipos principais de MDS: métrico (clássico) e não métrico. [10] • MDS métrico: conhecido como Principal Component Analysis (PCA), tenta mo- delar a semelhança/diferença de dados calculando distâncias entre cada par de pon- tos usando suas coordenadas geométricas, medindo as distâncias em uma escala linear; • MDS não métrico: foi projetado para lidar com dados ordinais, como classificação de preferência feita por clientes, por exemplo, onde a ordem importa e não seu valor absoluto. Visto isto, a nossa análise será feita pelo método métrico, por meio das bibliotecas Python sklearn.datasets - load_digits, sklearn - manifold e sklearn.manifold - MDS. O MDS métrico calcula distâncias entre cada par de pontos no espaço original de alta dimensão e transforma para um espaço de menor dimensão, preservando a distância entre os pontos da melhor forma possível. Este resultado é obtido pelo processo: 1. o algoritmo calcula distâncias entre cada par de pontos, dij; 2. tenta otimizar a função custo (5.1), encontrando um conjunto de coordenadas em um espaço de menor dimensão que minimiza o valor do Stress. StressD(x1, . . . , xn) = √ ∑ i ̸=j=1,...,n (dij − ∥xi − xj∥)2,