�������������������������ABC�����D��EB�F���D��������������E�E���D���F���D���F���������

�������������������AB�CD�ECB�C�FC��C�C�����BBC�E����B��������������

�C����B����CB���� ��C��!B�����

��"#B ��$��BC%&� �'� ���C(�����$�����C�C� ����B)C�CB��CB��� � ��C��!B�����

�C����B�**��C����C���+,-.-�D��-�-/���0�0-�

1B����C'�B�D�2�B(��,���3�-

4����B�C%&� � 5����BC'�6 � * � 7��)�B��'C'� � ��C'$C� � '� � �C����C���

8�����$���'������$�C%&�-

�-��$��BC%&� � '� � ��C(���- � �-!B���9��C � ����B)C�CB- � :-;BC'�����

��B�C���C'�- � "-4���?�$��-

>?�$��������(�@�D�8�C(��B��B��)C���A�����B)C���$����C��

.C�C)BC�*BC)�������(�@��5C�AD�B'�6D��-8�C(��B��B��)C�-���-�8���B)C��!B��B����-�:-�E�B�C����'�(BC'����-��"-� $��'�C��'���C��-��=-�8�C(��'C�C�C��-���-�8���B)C��C�C�A����5EC�B��C���6-

FB�C�'�������BC%&�D�.B����C������'��8�C(���

>��$�C%&�D�E���B�������@��C�'C�����$�C%&�

�C�C��GC���C'�BCD�.B�3-�4B-�2�B(��,���3��58����7E8�!E.6.B�3-�4B-�H9����.�'B����58����7E8�!E.6.B�3-�4B-�I$�,B���>��(�5F ����7E8�!E.6

4C�C�'C�'�3��CD��=�0���0�0

.B�(BC�C�'��.J�*;BC'$C%&�D�E���BC'�������@��C�'C�����$�C%&�

Instituto de ComputaçãoUniversidade Estadual de CampinasReuperação de Imagens Multiesala IntervalarCarlos Elias Arminio Zampieri1julho de 2010

Bana Examinadora:• Jorge Stol� (Orientador)• Hélio PedriniInstituto de Computação - UNICAMP• Wu Shin TingFauldade de Engenharia Elétria e Computação - UNICAMP• Riardo da Silva Torres (Suplente Interno)Instituto de Computação - UNICAMP• Léo Pini Magalhães (Suplente Externo)Fauldade de Engenharia Elétria e Computação - UNICAMP1Suporte �naneiro de: Bolsa do CNPq (proesso 133110/2009-5) 2009�2011.iv

ResumoNeste trabalho apresentamos um método geral para busa de imagem por onteúdo (BIPC,CBIR) em grandes oleções de imagens, usando estimação intervalar multiesala de distânia.Consideramos espei�amente busas por exemplo, em que o objetivo é enontrar a imagemda oleção que é mais próxima a uma imagem dada, segundo alguma função de distâniade imagens. Neste trabalho não prouramos desenvolver métrias que melhor atendem asintenções do usuário; em vez disso, supondo que a métria está esolhida, apresentamos umalgoritmo genério (que denominamos MuSIS, de Multisale Image Searh) para realizar abusa de maneira e�iente usando aritmétia intervalar. Estimativas intervalares das distân-ias entre imagens são usadas para eliminar rapidamente imagens andidatas, onsiderandoapenas versões reduzidas das mesmas, de maneira semelhante ao paradigma de otimizaçãobranh-and-bound. Como parte deste trabalho, desenvolvemos estimadores intervalares e�a-zes para distânia eulidiana e algumas variantes da mesma, inluindo métrias sensíveis aogradiente em esalas variadas. Experimentos indiaram que o método promove signi�ativaredução de ustos em relação à busa exaustiva. Apesar de menos e�iente do que outrosmétodos omumente usados para BIPC, o algoritmo MuSIS sempre retorna a resposta exata� isto é, a imagem mais próxima na métria esolhida � e não apenas uma aproximação.A abordagem MuSIS é ompatível om uma ampla variedade de funções de distânia, sema neessidade de pré-alular ou armazenar desritores espeí�os para ada função.

v

AbstratWe present a general method for ontent-based image retrieval (CBIR) in large image ol-letions, using multisale interval distane estimation. We onsider spei�ally queries byexample, where the goal is to �nd the image in the olletion that is losest to a givenimage, a

ording to some image distane funtion. In this work we do not aim to developmetris that best meet the user's intentions; instead, assuming that the metri is hosen,we desribe an algorithm (wih we all MuSIS, for MultiSale Image Searh) to performthe searh e�iently using interval arithmeti. Interval estimates of the image distanes areused to quikly disard andidate images after examining only small versions of them, in amanner similar to the branh-and-bound optimization paradigm. As part of this work, wedeveloped e�etive interval estimators for the Eulidean distane and for some variationsof it, inluding metris that are sensitive to the gradient at various sales. Experimentsindiate that the method yields signi�ant ost savings over exhaustive searh. Althoughless e�ient than other methods ommonly used for CBIR, the MuSIS algorithm alwaysreturns the exat answer � that is, the nearest image in metri hosen � and not just anapproximation thereof. The MuSIS approah is ompatible with a wide variety of distanefuntions without the need to pre-ompute or store spei� desriptors for eah funtion.

vi

SumárioResumo vAbstrat vi1 Preliminares 11.1 Contextualização e Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Busa Multiesala por Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Prinípios do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.4 Métrias para Imagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.5 Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.6 Publiações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Notações e De�nições 42.1 Imagens e Pixels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Métrias para Apliação em Imagens . . . . . . . . . . . . . . . . . . . . . . 42.3 Espaços de Cor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3.1 Espaço RGB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3.2 Espaço YUV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3.3 Espaço Yuv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.4 Operações om Imagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.5 Pirâmide de Imagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.5.1 Bloos de Pixels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.5.2 Aritmétia Intervalar . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.6 Métodos de Redução de Esala . . . . . . . . . . . . . . . . . . . . . . . . . 92.6.1 Redução Intervalar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.6.2 Redução por Média e Desvio Padrão . . . . . . . . . . . . . . . . . . 103 Busa Multiesala de Imagens 123.1 Estimadores de Distânia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.2 Busa Intervalar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.2.1 Corretude e Terminação . . . . . . . . . . . . . . . . . . . . . . . . . 143.2.2 E�iênia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15vii

3.2.3 Como o Candidato é Esolhido . . . . . . . . . . . . . . . . . . . . . 153.2.4 In�uênia da Função Disrepânia . . . . . . . . . . . . . . . . . . . . 163.3 Extensão para Resultados Multiplos . . . . . . . . . . . . . . . . . . . . . . . 164 Distânia Eulidiana 174.1 De�nição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.2 Imagens om Diferentes Domínios . . . . . . . . . . . . . . . . . . . . . . . . 184.3 Estimativas da Distânia Eulidiana . . . . . . . . . . . . . . . . . . . . . . . 194.3.1 Estimativa por Redução Intervalar . . . . . . . . . . . . . . . . . . . 194.3.2 Estimativa por Média e Desvio Padrão . . . . . . . . . . . . . . . . . 205 Distânia Eulidiana Cumulativa 235.1 Estimação Intervalar da Distânia Cumulativa . . . . . . . . . . . . . . . . . 246 Distânia de Gradiente 266.1 Forma vs Cor na Métria Eulidiana . . . . . . . . . . . . . . . . . . . . . . 266.2 Gradiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266.3 Gradiente Normalizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286.4 Distânia de Gradiente Normalizado . . . . . . . . . . . . . . . . . . . . . . 306.5 Usando Gradiente Normalizado no MuSIS . . . . . . . . . . . . . . . . . . . 306.5.1 Gradiente na Base Original, om Métria Monoesala . . . . . . . . . 306.5.2 Gradiente na Base Original, om Métria Cumulativa . . . . . . . . . 316.6 Gradiente em Cada Nível da Pirâmide . . . . . . . . . . . . . . . . . . . . . 337 Métrias para Imagens Coloridas 367.1 Distânia Eulidiana RGB . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367.2 Distânia Eulidiana Yuv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367.3 Distânia de Gradiente Yuv . . . . . . . . . . . . . . . . . . . . . . . . . . . 377.4 Operador Cartoon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387.5 Estimadores de Métrias para Imagens Coloridas . . . . . . . . . . . . . . . . 398 Bases de Imagens 408.1 Bases AL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418.2 Base C1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428.3 Base C2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438.4 Base CR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458.5 Base FF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468.6 Base JS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 Testes de Desempenho 499.1 Metodologia de Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499.2 Comparando Heurístias de Seleção de Candidatos . . . . . . . . . . . . . . . 50viii

9.3 Comparando Estimadores AI e µσ . . . . . . . . . . . . . . . . . . . . . . . . 519.4 Métria Normal e Métria de Gradiente . . . . . . . . . . . . . . . . . . . . . 519.5 Métrias Monoesala versus Multiesala . . . . . . . . . . . . . . . . . . . . . 5210 Conlusões e Trabalhos Futuros 54Bibliogra�a 56

ix

Lista de Tabelas5.1 Distânias d da imagem A em relação a B e C da �gura 5.1. . . . . . . . . . 246.1 Termos da distânia distH∗2 em ada esala da pirâmide para as imagens da�gura 6.10, om β = 2. Nesta tabela dr(G,H) = dist2(µG(r), µH(r)) e analo-gamente para dr(G,K). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326.2 Termos de dist⋆ em ada esala da pirâmide, para as imagens da �gura 6.12,om β = 2. Nesta tabela, dr(A,B) = dist2(δA(r)), δB(r)) e analogamente paradr(A,C). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348.1 As bases usadas nos testes, om as dimensões, esala máxima m, o número deimagens N e a origem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409.1 Custo relativo da busa por uma amostragem de imagens usando as heurístiade esolha para ada base de imagens. . . . . . . . . . . . . . . . . . . . . . 509.2 Comparação do desempenho do MuSIS om os dois tipos de estimadores:intervalar (AI) e média-desvio (µσ). . . . . . . . . . . . . . . . . . . . . . . . 519.3 Comparação do desempenho do MuSIS om a métria eulidiana dist2, e ommétrias de gradiente normalizado distH2 e busa força-bruta. . . . . . . . . . 529.4 Comparação do desempenho do MuSIS om métrias monoesala e multies-ala umulativa om parâmetros β = 1/2, 1 e 2 em relação à força-bruta (FB).Exeto nas duas ultimas linhas, os valores são o número p[k]de álulos de dis-tânia dist2 e/ou o número q[k]de álulos de estimadores dist(k)2 exeutados.(Note que q[k]= 0 no nível k = 0 e no algoritmo de força bruta) . . . . . . . 529.5 Comparação do desempenho do MuSIS om métrias de gradiente monoes-ala e multiesala umulativa om parâmetros β = 1/2, 1 e 2 em relação àforça-bruta (FB). Exeto nas duas ultimas linhas, os valores são o númerop[k]de álulos de distânias dist2 e/ou o número q[k]de estimadores distH(k)2exeutados. (Note que q[k]= 0 no nível k = 0 no algoritmo força bruta, e paradist⋆2 em todos os níveis) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

x

Lista de Figuras2.1 Uma imagem e seus anais de or (R, G, B). . . . . . . . . . . . . . . . . . . 52.2 Uma imagem I (esq.) e os níveis i = 3 e k = 5 da pirâmide de imagens I,mostrando os onjuntos D(0:k)[p] e D(i:k)[p], para o pixel p de I(k). . . . . . . 82.3 Uma imagem monoromátia (no alto), e as versões reduzidas I(1), I(2) . . . I(m)produzidas pelo proesso de redução intervalar. Cada nível onsiste de umaimagem inferior I(k)↓ (esq) e uma imagem superior I(k)↑ (dir). . . . . . . . . 102.4 Uma imagem monoromátia, e as versões reduzidas obtidas por redução mé-dia e desvio. Cada nível onsiste de uma imagem de média µI(k) (esq) e umaimagem de desvio padrão σI(k) (dir). . . . . . . . . . . . . . . . . . . . . . . 113.1 Duas iterações suessivas do algoritmo MuSIS. . . . . . . . . . . . . . . . . . 134.1 Quatro imagens e suas respetivas másaras binárias. . . . . . . . . . . . . . 184.2 Resultado da distânia eulidiana apliada sobre três imagens monoromátias(ao alto) om domínios efetivos de�nidos por másaras (em baixo). Temosdist2(A,B) = 0.166572 < dist2(A,C) = 0.216247. . . . . . . . . . . . . . . . 184.3 Três imagens A,B e C usadas para exempli�ar estimadores intervales dadistânia dist2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.4 Estimadores da distânia eulidiana dist(k)2 (A(k),B(k)) e dist2(A(k),C(k)) alu-lados em várias esalas da pirâmide intervalar pelas fórmulas (4.2)�(4.5). . . 214.5 Estimadores da distânia eulidiana dist(k)2 (A(k),B(k)) e dist2(A(k),C(k)) al-ulados em várias esalas das pirâmides reduzidas por média-desvio padrão,pelas fórmulas (4.6)�(4.9). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.1 Três imagens monoromátias. . . . . . . . . . . . . . . . . . . . . . . . . . . 246.1 Três imagens monoromátias. Neste exemplo, dist2(A,B) = 0.110640 <dist2(A,C) = 0.433529. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266.2 Uma imagem I (esq.) e a imagem gradiente |▽I| orrespondente (dir.). . . . 276.3 Imagens-gradiente das três imagens da �gura 6.1. Neste exemplo, dist▽2 (A,B) =0.165780 > dist▽2 (A,C) = 0.030366. . . . . . . . . . . . . . . . . . . . . . . . 276.4 Três imagens monoromátias e suas imagens gradiente. Neste exemplo,dist▽2 (A,B) = 0.092293 < dist

▽

2 (A,C) = 0.112663. . . . . . . . . . . . . . . . 28xi

6.5 Uma imagem monoromátia (esq.) e sua imagem de gradiente normalizado|HI| (dir.). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296.6 Uma imagemmonoromátia I (esq.) e três imagens de gradiente normalizadoHI om diferentes valores do parâmetro ǫ. . . . . . . . . . . . . . . . . . . . 296.7 Resultado da operação |H| apliada às imagens da �gura 6.4. Temos dist2(|HA| , |HB|) =0.091912 > dist2(|HA| , |HC|) = 0.015626. . . . . . . . . . . . . . . . . . . . . 306.8 Pirâmide obtida a partir da redução da base om imagens gradiente. . . . . . 306.9 Resultado da operação H apliada sobre três imagens monoromátias. Temosdist2(HA,HB) = 0.105913 < dist2(HA,HC) = 0.167085. . . . . . . . . . . . . 316.10 Distânia eulidiana umulativa om gradiente normalizado apliado à baseoriginal. Temos distH∗2 (A,B) = 0.079349 > distH∗2 (A,C) = 0.059057, om oparâmetro β = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326.11 Pirâmide obtida a partir da redução da base original om gradiente H apliadoa ada nível. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336.12 Distânia eulidiana umulativa om o gradiente H apliado a ada nível dapirâmide. Temos dist⋆(A,B) = 0.391287 > dist⋆(A,C) = 0.160042, om oparâmetro β = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347.1 Distânia eulidiana de imagens oloridas no espaço RGB. Temos dist2(A,B) =0.242803 > dist2(A,C) = 0.098406. . . . . . . . . . . . . . . . . . . . . . . . 377.2 Uma imagem olorida (esq.) e sua imagem gradiente olorida (dir.) obtidaapliando a operação H a ada anal no espaço RGB. . . . . . . . . . . . . . 377.3 Uma imagem olorida (esq.) e o resultado do operador artoon (dir.). . . . . 388.1 Algumas imagens da base ALOI-VIEW. . . . . . . . . . . . . . . . . . . . . 418.2 Algumas imagens da base ALNT02. . . . . . . . . . . . . . . . . . . . . . . . . 418.3 Algumas imagens da base ALGT01 (monoromátias). . . . . . . . . . . . . . 428.4 Algumas imagens da base ALGT01 (oloridas). . . . . . . . . . . . . . . . . . 428.5 Algumas imagens da base Calteh-101. . . . . . . . . . . . . . . . . . . . . 428.6 Algumas imagens da base C1NT01. . . . . . . . . . . . . . . . . . . . . . . . . 438.7 Algumas imagens da base C1GT01 (monoromátias). . . . . . . . . . . . . . 438.8 Algumas imagens da base C1GT01 (oloridas). . . . . . . . . . . . . . . . . . 438.9 Algumas imagens da base Calteh-256. . . . . . . . . . . . . . . . . . . . . 448.10 Algumas imagens da base C2NT01. . . . . . . . . . . . . . . . . . . . . . . . . 448.11 Algumas imagens da base C2GT01 (monoromátias). . . . . . . . . . . . . . 448.12 Algumas imagens da base C2GT01 (oloridas). . . . . . . . . . . . . . . . . . 448.13 Algumas imagens da base Corel. . . . . . . . . . . . . . . . . . . . . . . . . 458.14 Algumas imagens da base CRNT01. . . . . . . . . . . . . . . . . . . . . . . . . 458.15 Algumas imagens da base CRGT01 (monoromátias). . . . . . . . . . . . . . 458.16 Algumas imagens da base CRGT01 (oloridas). . . . . . . . . . . . . . . . . . 468.17 Algumas imagens da base Free Photos Nature. . . . . . . . . . . . . . . . . 46xii

8.18 Algumas imagens da base FFNT01. . . . . . . . . . . . . . . . . . . . . . . . . 468.19 Algumas imagens da base FFGT01 (monoromátias). . . . . . . . . . . . . . 478.20 Algumas imagens da base FFGT01 (oloridas). . . . . . . . . . . . . . . . . . 478.21 Algumas imagens da base JSNT01. . . . . . . . . . . . . . . . . . . . . . . . . 478.22 Algumas imagens da base JSGT01 (monoromátias). . . . . . . . . . . . . . 478.23 Algumas imagens da base JSGT01 (oloridas). . . . . . . . . . . . . . . . . . 48

xiii

Capítulo 1Preliminares1.1 Contextualização e MotivaçãoEste trabalho visa estudar métodos e ténias omputaionais para busa ou reuperaçãode imagens em grandes banos de imagens, em espeial utilizando a aritmétia intervalar erepresentações multiesala de imagens.Repositórios de imagens são utilizados pelas mais diversas áreas, omo mediina, iêniasda terra, jornalismo, arqueologia, biologia, marketing, segurança, et [16℄. Banos omentenas de milhares (ou milhões) de imagens são ada vez mais omuns. Um exemplo é oEarth Observing System da Nasa, que obtém terabytes de dados de imagens todos os dias[11℄. Em tais banos, a loalização visual de imagens de interesse é imprátiavel e, portanto,há uma grande neessidade de métodos omputaionais e�ientes para busa de imagens.Imagens digitais podem ser obtidas de diversas fontes, omo âmeras digitais, apturade quadros de vídeo, digitalização de fotos e doumentos utilizando-se sanners (de mesa oude mão), et [18℄. Imagens também podem ser produzidas arti�ialmente por ténias deomputação grá�a ou tipogra�a digital.Há muitas maneiras de efetuar busas em banos de dados de imagens.Os sistemas de busas por meta-dados são baseados em textos assoiados a ada imagem(rótulos, legendas, palavras-have, et). Grandes busadores omo Google e Yahoo utilizamvariantes deste método, onde rótulos são extraídos de textos que aompanham as imagens.Esta abordagem, apesar de ser relativamente fáil de implementar, é inviável para grandesoleções de imagens não rotuladas, pois a riação de rótulos adequados é extremamentedispendiosa.Uma alternativa à busa por meta-dados é a busa de imagens por onteúdo (BIPC; eminglês, ontent based image retrieval ou CBIR) [6, 7, 10, 19, 8℄. Nesta abordagem, a busautiliza propriedades intrínseas das imagens, omo distribuição de ores, forma, textura, et.Por exemplo, o usuário espei�a ertas propriedades das imagens desejadas, e a resposta éuma lista ontendo as imagens que melhor se enquadram nessas espei�ações.Neste trabalho onsideramos apenas busas por onteúdo; mais preisamente, busas por1

1.2. Busa Multiesala por Exemplo 2exemplo, em que o objetivo é enontrar a imagem da oleção que é mais próxima a umaimagem-modelo dada, segundo alguma função de distânia de imagens. Este oneito éde�nido mais formalmente no apítulo 2.1.2 Busa Multiesala por ExemploNesta dissertação, apresentamos um novo método geral para busa em grandes oleções deimagens. Nosso algoritmo, que denominamos MuSIS (de Multisale Image Searh) ombinamétodos multiesala om aritmétia intervalar, e pode ser utilizado om diversas funções dedistânia. O algoritmo básio está desrito no apítulo 3.Ressaltamos que neste projeto (ao ontrário de muitos trabalhos desta área) o objetivonão é desenvolver métrias que melhor re�etem os desejos dos usuários, mas sim aelerar abusa para uma métria espei�ada. Portanto, os ritérios tradiionais de avaliação paraalgoritmos BIPC (preisão, sensibilidade, auráia, et) não se apliam; o únio ritériorelevante é o usto da busa.Aliás, observamos que as métrias eulidianas que, por simpliidade de exposição, resol-vemos utilizar nos testes são sabidamente frágeis e inadequadas para a maioria das apliaçõesreais. Porém o algoritmo básio pode ser estendido para métrias mais so�stiadas.1.3 Prinípios do AlgoritmoA ténia geral de análise multiresolução ou multiesala baseia-se na deomposição dosobjetos em estudo (no aso, uma imagem) em várias amadas, ada uma ontendo detalhesde tamanhos diferentes [15℄. No nosso trabalho, supomos que para ada imagem da baseé onstruída previamente uma pirâmide de imagens reduzidas em várias esalas. Este pré-proessamento está detalhado no apítulo 2.Nosso algoritmo omeça alulando a distânia entre a imagem dada e ada uma das ima-gens da base, na esala mais reduzida. O resultado desse álulo é uma estimativa intervalarpara as distânias exatas (na esala original) entre essas imagens. As estimativas intervalaressão usadas para eliminar rapidamente imagens andidatas, de maneira semelhante ao para-digma de otimização branh-and-bound [14℄. Quando neessário, as estimativas de distâniassão realuladas em esalas ada vez mais detalhadas, que permite eliminar mais imagensaté obtermos a imagem desejada.Nossos experimentos indiaram que o algoritmo MuSIS é muito mais e�iente do quea busa exaustiva. Apesar de menos e�iente do que outros métodos omumente usadospara este problema, nossa abordagem sempre retorna a resposta exata � isto é, a imagemda base que é mais próxima à imagem-exemplo na métria esolhida � e não apenas umaaproximação da mesma. A ténia permite onsultas om uma ampla variedade de funçõesde distânia, sem a neessidade de alular ou armazenar desritores espeí�os para adafunção.

1.4. Métrias para Imagens 31.4 Métrias para ImagensNos apítulos 4 a 7 desrevemos a apliação do algoritmo MuSIS para várias métrias deomparação de imagens, derivadas da métria eulidiana.No apítulo 5, em partiular, desrevemos o oneito de métria multiesala, espeial-mente interessante para uso om o algoritmo MuSIS, que é uma média ponderada dos valoresda distânia eulidiana apliada a todas as esalas de resolução.No apítulo 6, onsideramos métrias que levam em onta os gradientes das imagens,e não apenas seus valores. Para esse �m introduzimos um operador espeial, o gradientenormalizado. Finalmente, no apítulo 7 desrevemos extensões destas métrias para imagensoloridas.1.5 TestesNo apítulo 8, desrevemos as bases de imagens utilizadas nos testes. No apítulo 9, apre-sentamos testes quantitativos, om várias métrias e bases, que mostram seu desempenhorelativamente à busa exaustiva e justi�am algumas esolhas feitas no desenvolvimento doalgoritmo.1.6 PubliaçõesOs resultados deste trabalho foram publiados em ongressos naionais e internaionais [23,22, 21℄. A implementação (em Gnu C) esta disponível em http://www.liv.i.uniamp.br/~eaz/soure.html e as bases de testes estão disponíveis em http://www.liv.i.uniamp.br/~eaz/bases.html.

Capítulo 2Notações e De�nições2.1 Imagens e PixelsNeste trabalho, supomos que uma imagem I do bano de imagens é representada por umafunção �nita de um erto domínio D ⊂ Z × Z para um espaço V de ores om dimensão�nita c. Assim o valor de I em um ponto p do domínio, hamado pixel e denotado por I[p],é uma lista de c números, as amostras do pixel.Neste trabalho, geralmente supomos que as amostras são números reais � que são apro-ximadas por números em ponto �utuante de preisão limitada na memória do omputador,e quantizadas para uma pequena seleção de valores quando armazenadas em arquivos deimagens.Para simpli�ar, vamos supor que todas as imagens na base têm o mesmo tamanho eformato nx×ny. Por simpliidade, onsideramos prinipalmente bases de imagens monoro-mátias; porém, os algoritmos aqui desritos podem ser failmente estendidos para trabalharom imagens oloridas (veja apítulo 7) e de diferentes tamanhos (veja seção 4.2).2.2 Métrias para Apliação em ImagensNeste trabalho, onsideramos um aso partiular da busa por onteúdo, a busa por simi-laridade. Nesta modalidade, é forneida uma imagem modelo, e o resultado da busa são asimagens da base mais semelhantes à mesma, segundo uma função distânia qualquer.Uma função distânia para imagens é uma função dist que, para ada par de imagensA,B atribui um número real dist(A,B) que mede a dissimilaridade entre elas. A função distpode ser uma métria ou função distânia no sentido matemátio do termo [9℄. Ou seja,uma função que satisfaz as seguintes propriedades:1. dist(A,A) = 0 para qualquer A2. dist(A,B) > 0 para quaisquer A,B om A 6= B4

2.3. Espaços de Cor 53. dist(A,B) = dist(B,A) para quaisquer A,B4. dist(A,B)

2.4. Operações om Imagens 6e proessamento de imagens. A onversão do espaço RGB para YUV é dada por umatransformação linear de oordenadas, espei�amente

Y

U

V

=

0.2989 0.5866 0.1144

−0.14713 −0.28886 0.436

0.615 −0.51499 −0.10001

R

G

B

(2.1)A transformação inversa é

R

G

B

=

1 0 1.13983

1 −0.39465 −0.5806

1 −0.51499 0

Y

U

V

(2.2)2.3.3 Espaço YuvO espaço Yuv é uma transformação não-linear do espaço YUV, onde os anais de rominâniaU, V são divididos pela luminânia Y, de forma a torná-los independentes do ganho daâmera e da intensidade da iluminação que inide sobre os objetos das imagens. Nestetrabalho usamos as fórmulasu = U

1 + δ

Y + δv = V

1 + δ

Y + δ(2.3)A onversão inversa é

U = uY + δ

1 + δV = v

Y + δ

1 + δ(2.4)O parâmetro δ é um valor pequeno usado para evitar divisão por zero. Neste trabalho usamos

δ = 0.0001.2.4 Operações om ImagensPodemos de�nir o máximo, o mínimo, o valor médio, o valor médio quadrátio e a raiz médiaquadrada de um onjunto P ⊆ D de pixels de uma imagem I, pelas fórmulasmaxP I = max { I[p] : p ∈ P } (2.5)minP I = min { I[p] : p ∈ P } (2.6)

avgP I =1

#P

∑

p∈P

I[p] (2.7)msqP I =

1

#P

∑

p∈P

(I[p])2 (2.8)

2.5. Pirâmide de Imagens 7rmsP I =

√

msqP I =

√

1

#P

∑

p∈P

(I[p])2 (2.9)onde #P é a ardinalidade de P . De�nimos também a variânia varP I e o desvio padrão(ou simplesmente desvio) devP I pelas fórmulasvarP I = msqP (I − avgP I) (2.10)

devP I =√

varP I = rmsP (I − avgP I) (2.11)Em todas as operações, omitiremos o subsrito P quando ele é o domínio D da imagem.No aso de imagens oloridas, onvenionaremos que as fórmulas (2.5 � 2.9) são apliadasa ada anal de or, separadamente, produzindo um resultado que também é uma or de V.2.5 Pirâmide de ImagensPara ada imagem I, de�ne-se uma pirâmide de imagens I(0), I(1), . . . , I(m), em que I(0) é umaimagem de mesmo tamanho que a imagem original I, e ada I(k) é uma imagem análoga aI(0), mas om dimensões reduzidas por um fator de 1/2k em ada direção (portanto, um fatorde 1/4k em área).Cada imagem I(k) é um nível da pirâmide, e o índie k é a esala desse nível. A últimaesala m é um parâmetro do algoritmo; geralmente m é o menor inteiro tal que I(m) possuium únio pixel (ou uma únia linha ou oluna), ou então o maior valor de k tal que 2k dividenx e ny. O espaço de valores U das imagens I(k) pode ser diferente do espaço de valores Vda imagem original I; por exemplo, V pode ser o espaço de or visual (RGB), enquanto queU pode ser outro espaço de or (YUV, Yuv, et.) ou o resultado de outras transformaçõesloais da imagem, omo gradiente, variânia, et. Estas possibilidades serão disutidas naseção 2.6.2.5.1 Bloos de PixelsCada pixel p de uma versão reduzida I(k) da imagem é alulado a partir de um erto onjuntoD(0:k)[p] de pixels de I.Por exemplo, se o domínio das imagens é o quadrado {0.. 2m − 1} × {0.. 2m − 1}, adabloo D(0:k)[p] é um quadrado om 2k × 2k pixels de D. Veja a �gura 2.2. Espei�amente

D(0:k)[p] =

{

2kp+ r : r ∈{

0.. 2k − 1}

×{

0.. 2k − 1}} (2.12)Mas geralmente, para quaisquer esalas i, k om i < k, e ada pixel p de I(k), de�nimoso bloo D(i:k)[p], omo sendo o menor onjunto de pixels do nível i que depende dos mesmospixels da imagem original que o pixel I(k)[p]. Isto é, tal que

D(0:k)[p] =

⋃

q∈D(i:k)[p]

D(0:i)[q] (2.13)

2.5. Pirâmide de Imagens 8No exemplo aima, D(i:k)[p] é um bloo om 2k−i × 2k−i pixels dentro do quadrado{0.. 2m−i − 1} × {0.. 2m−i − 1}, espei�amente

D(i:k)[p] =

{

2k−ip+ r : r ∈{

0.. 2k−i − 1}

×{

0.. 2k−i − 1}} (2.14)

I = I(0) I(i) I(k)

Figura 2.2: Uma imagem I (esq.) e os níveis i = 3 e k = 5 da pirâmide de imagensI, mostrando os onjuntos D(0:k)[p] e D(i:k)[p], para o pixel p de I(k).2.5.2 Aritmétia IntervalarA ténia de aritmétia intervalar (AI) foi desenvolvida por R. Moore em 1960 [17℄ paraobter garantia de resultados em álulos om dados inertos e/ou operações aproximadas.A aritmétia intervalar tem sido usada esporadiamente em proessamento de imagens, porexemplo, para a quantização de ores e inserção de maras d'água em imagens.Um intervalo é um par de números v̄ = [v̄↓, v̄↑] que representam o onjunto de todosos valores reais x tal que v̄↓ ≤ x ≤ v̄↑. Se v↓ = v↑, o intervalo é dito exato, e representao onjunto trivial (unitário) {v̄↓} = {v̄↑}. Se v̄↓ > v̄↑ o intervalo é o onjunto vazio, queé denotado por [ ]. Os extremos de um intervalo podem ser in�nitos (−∞ ou +∞); empartiular, o intervalo [−∞,+∞] representa o onjunto de todos os números reais (�nitos)

R. Moore observou que qualquer operação elementar z ← f(x, y) sobre grandezas ordináriaspode ser substituída por uma operação sobre intervalos z̄ ← f ∗(x̄ , ȳ), de tal forma que ointervalo alulado z̄ garantidamente ontém o resultado ordinário z, para quaisquer operan-dos ordinários x, y ontidos nos intervalos x̄ , ȳ . Por exemplo, o mínimo, o máximo, a somae a subtração de dois intervalos x̄ = [x̄↓_ x̄↑] e ȳ = [ȳ↓_ ȳ↑] são os intervalosmin(x̄, ȳ) = [min(x̄↓, ȳ↓)_min(x̄↑, ȳ↑)]max(x̄, ȳ) = [max(x̄↓, ȳ↓)_max(x̄↑, ȳ↑)]

x̄+ ȳ = [x̄↓+ ȳ↓_ x̄↑+ ȳ↑]x̄− ȳ = [x̄↓ − ȳ↑_ x̄↑ − ȳ↓] (2.15)

2.6. Métodos de Redução de Esala 9O quadrado de um intervalo x̄ é um pouo mais ompliado:x̄2 =

[(x̄↓)2 _ (x̄↑)2] se x̄↓ ≥ 0,[(x̄↑)2 _ (x̄↓)2] se x̄↑ ≤ 0,[0_max((x̄↓)2, (x̄↑)2)] aso ontrário. (2.16)No álulo destas fórmulas, deve-se tomar uidado para que erros de arredondamento eaproximações sejam sempre no sentido de aumentar a largura do intervalo; isto é, aumentaro valor de z̄↑ e diminuir o valor de z̄↓.As operações elementares da AI podem ser ombinadas para realizar álulos mais om-pliados. Desta maneira, qualquer fórmula pode ser substituída por uma versão intervalar damesma, que produz um intervalo que garantidamente ontém o resultado da formula original.Uma operação importante em AI é a junção ū ∨ v̄ de dois intervalos ū, v̄ , de�nida omosendo o menor intervalo que ontem ū e v̄ � ou seja, ū ∨ v̄ = [min {ū↓, v̄↓} ,max {ū↑, v̄↑}].Note que ū∨v̄ é o mesmo que a união de onjuntos u∪v somente se um dos dois intervalo é va-zio, ou se eles tem pelo menos um valor em omum. Esta operação é assoiativa e tem o inter-valo vazio [ ] omo um elemento neutro. Outra operação é a interseção de dois intervalos ū∧v̄que é simplesmente a interseção dos onjuntos, isto é, ū ∧ v̄ = [max {ū↓, v̄↓} ,min {ū↑, v̄↑}].Note que esta fórmula produz um intervalo w vazio (om w↓ > w↑) se os dois intervalos nãotem interseção.2.6 Métodos de Redução de EsalaNa abordagem do trabalho, ada pixel das imagens em esala reduzida I(k) pode ser obtidode várias maneiras. Apresentamos a seguir duas maneiras, a redução intervalar e a reduçãopor média e desvio. Outras maneiras de onstruir a pirâmide serão disutidas no apítulo 6.2.6.1 Redução IntervalarNa redução intervalar, ada pixel p de I(k) é um intervalo I(k)[p] = [I(k)[p]↓, I(k)[p]↑] queontém os valores dos pixels do bloo D(0:k)[p] da imagem I. Isto é,

I(k)[p]↓ = min

D(0:k)[p] I (2.17)

I(k)[p]↑ = max

D(0:k)[p] I (2.18)Podemos, portanto, interpretar ada nível I(k) da pirâmide om uma imagem intervalar. Vejaa �gura 2.3 . Alternativamente, podemos ver I(k) omo um par de imagens I(k)↓ e I(k)↑, onde

I(k)↓[p] = I(k)[p]↓ e I(k)↑[p] = I(k)[p]↑.Observe que I(0)[p]↓ = I(0)[p]↑ = I[p]. Portanto, as imagens reduzidas na esala 0 nãopreisam ser armazenadas pois são idêntias à original I.

2.6. Métodos de Redução de Esala 10

Figura 2.3: Uma imagem monoromátia (no alto), e as versões reduzidasI(1), I(2) . . . I(m) produzidas pelo proesso de redução intervalar. Cada nível on-siste de uma imagem inferior I(k)↓ (esq) e uma imagem superior I(k)↑ (dir).Cada imagem intervalar I(k) pode ser obtida om relativamente pouo trabalho a partirda imagem anterior I(k−1). Espei�amente, ada pixel I(k)[p] é a junção dos quatro pixelsintervalares I(k−1)[q] tal que q ∈ P (k−1:k)[p].O usto total (em tempo e espaço) de alular a pirâmide é então menor que (1 + 1/4 +

1/42+· · ·+1/4m−1) < 4/3 ≈ 1.333 vezes o usto de alular o nível I(1). Portanto, se a imagemI tem n pixels, o usto é O(n). Uma vez que ada pixel de I(k) onsiste de dois valores de V, oespaço neessário para armazenar a pirâmide toda é 1+2(1/4+1/42+· · ·+1/4m) < 5/3 ≈ 1.67vezes o espaço usado pela imagem original.2.6.2 Redução por Média e Desvio PadrãoOutra forma de onstruir a pirâmide é usar a redução por média e desvio padrão. Nestaabordagem, ada pixel de I(k) é o par onstituído da média µI(k)[p] e do desvio padrãoσI(k)[p] dos pixels do bloo D(0:k)[p] da imagem I, ou seja

µI(k)[p] = avgD

(0:k)[p] I (2.19)σI(k)[p] = dev

D(0:k)[p] I (2.20)

2.6. Métodos de Redução de Esala 11Veja a �gura 2.4. Observe que µI(0)[p] = I[p] e σI(0)[p] = 0, portanto o nível 0 da pirâmidenão preisa ser armazenado.

Figura 2.4: Uma imagem monoromátia, e as versões reduzidas obtidas por redu-ção média e desvio. Cada nível onsiste de uma imagem de média µI(k) (esq) e umaimagem de desvio padrão σI(k) (dir).Assim omo na redução intervalar, a redução por média e desvio padrão pode ser feitainrementalmente. Ou seja, o nível I(k) pode ser alulado a partir do nível I(k−1) pelasfórmulasµI(k)[p] = avg

D(0:k−1) [p]µI(k−1) (2.21)

σI(k)[p] =√

avgD

(0:k−1) [p](σI(k−1)) + varD

(0:k−1)[p](µI(k−1)) (2.22)Assim, omo na redução intervalar, o espaço oupado por esta pirâmide é 1+2(1/4+1/42+· · · + 1/4m) < 5/3 ≈ 1.67 vezes o espaço oupado pela imagem original, e o usto total deonstruir esta pirâmide é O(n) para uma imagem I om n pixels.

Capítulo 3Busa Multiesala de ImagensA idéia fundamental do algoritmo de busa multiesala intervalar (que denominamos MuSISdo inglês multisale interval searh) é utilizar estimadores intervalares da função de disre-pânia para desartar imagens da base, sem preisar examinar ou omparar as imagens naesala original.3.1 Estimadores de DistâniaO método geral de busa proposto exige o álulo de estimativas da disrepânia dist(A,B)entre duas imagens a partir de suas versões reduzidas. Ou seja, para ada disrepânia dist,preisamos de�nir uma família de estimadores intervalares dist(k) que operam sobre imagensreduzidas em ada esala k.Um estimador intervalar dist(k) reebe duas imagens reduzidas A(k),B(k) na esala k,e devolve um intervalo dist(k)(A(k),B(k)) = [dist(k)(A(k),B(k))↑, dist(k)(A(k),B(k))↓], tal que,garantidamente, dist(A,B) ∈ dist(k)(A(k),B(k)).Para simpli�ar, esrevemos dist(k)(A,B) em vez de dist(k)(A(k),B(k)) uma vez que o su-persrito (k) nas imagens reduzidas é sempre igual ao do estimador. Entretanto, é importanteobservar que dist(k) usa apenas o nível k das pirâmides A,B (e possívelmente os níveis su-periores) e não as pirâmides inteiras. Nas seções 4.3 e 5.1 mostramos omo alular estesestimadores para várias funções de disrepânia.3.2 Busa IntervalarO algorítmo MuSIS mantém um onjunto C de andidatos que ontém a imagem resposta,ou seja, as imagens B∗ da base que são mais próximas à imagem de onsulta A, em algumamétria arbitrária dist. O onjunto é progressivamente podado, até se reduzir a apenas umaimagem, que deve ser a resposta desejada B∗.Cada elemento do onjunto C é uma quádrupla t = (t.B, t.B, t.k, t.d), onde t.B é umponteiro para uma imagem do bano; t.B é a pirâmide pré-alulada de t.B; t.k é uma12

3.2. Busa Intervalar 13esala de resolução; e t.d é uma estimativa intervalar para dist(A, t.B), alulada a partirdas versões reduzidas A(k) e t.B(k).O algorítmo mantém também um intervalo global d∗ tal que dist(A,B∗) ∈ d∗. Uma vezque dist(A,B∗) = min {dist(A, t.B) : t ∈ C} então podemos tomar d∗ omo sendo o mínimode todos os intervalos t.d em C, ou sejad∗↓ = min { t.d↓ : t ∈ C }

d∗↑ = min { t.d↑ : t ∈ C }(3.1)A situação geral durante a busa é ilustrada na �gura 3.1(topo). No eixo x está indiada aposição do andidato na �la, e no eixo y a estimativa intervalar t.d da distânia. Cada barrade erro india o intervalo estimado t.d para uma quádrupla t em C. As linhas traejadashorizontais indiam o intervalo d∗. Neste exemplo, d∗↑ e d∗↓ são determinados pelos limitesinferior e superior do andidato de número 0. A ada iteração, o algoritmo remove umandidato t da lista, realula a estimativa intervalar d′ = dist(k−1)(A, t.B) para a próximaesala k′ = t.k − 1, e reinsere o andidato atualizado (t.B, t.B, k′, d′) na lista, atualizando

d∗ de aordo om d′. Após esta atualização é geralmente possível eliminar da lista C algunsandidatos que não podem ser a imagem desejada.A �gura 3.1(baixo) ilustra o resultado dessas operações. Nesta iteração o andidato 0 érealulado e passou a ser o andidato 21. O limiar inferior d∗↓ passou a ser de�nido pelonovo andidato 0, e o limiar superior d∗↑ �ou reduzido ao do andidato realulado 21. Estamudança em d∗↑ permitiu ao algoritmo desartar mais de 20% dos andidatos da �la, semnuna alular a distânia exata entre A e as respetivas imagens t.B. 0

0.2

0.4

0.6

0.8

1

0 10 20 30 40 50 60 70 80 90 100 110

0

0.2

0.4

0.6

0.8

1

0 10 20 30 40 50 60 70 80 90 100 110Figura 3.1: Duas iterações suessivas do algoritmo MuSIS.

3.2. Busa Intervalar 14A desrição detalhada do algoritmo é apresentada abaixo.1. Seja m o nível máximo na pirâmide de A. Iniialize o onjunto C om todas as quá-druplas (B,B, m + 1, [0 _ 1]) tal que B está na base. Iniialize d∗ om o intervalo[0_ 1].2. Seja (B,B, k, d) um andidato om o mínimo d↓. Se é o únio andidato, retorne Bomo a resposta da busa; e pare. Caso ontrário seja (B′,B′, k′, d′) um andidato omo segundo menor d↓. Se d↑ ≤ d′↓, então retorne B omo resposta da busa; e pare.3. Esolha um andidato t = (B,B, k, d) de C om k > 0. Calule uma nova estimativaintervalar d′ = dist(k−1)(A,B)∩d. Substitua a quádrupla t na lista C por t′ = (B,B, k−1, d′). Atualize o intervalo d∗, de aordo om a de�nição (3.1).4. Remova de C toda quádrupla (B,B, k, d) ujo intervalo d está inteiramente aima ded∗, ou seja, que tem d↓ > d∗↑. Repita a partir do passo 2.Uma vez que o novo intervalo d′ = dist(k−1)(A,B) ∩ d alulado no passo 3 usa maisinformações (imagens mais detalhadas) que as usadas para alular d, espera-se que ele sejapelo menos tão preiso quanto d, ou seja, d′ ⊆ d. Porém, dependendo de omo a estimativa

dist(k−1) é alulada, isto pode não ser sempre verdade.Neste aso, se ambos intervalos são orretos (ou seja, ambos ontêm a distânia exatadist(A,B)), sua interseção é orreta também. O omando d′ ← dist(k−1)(A,B) ∩ d asseguraque d′↑ ≤ d↑ e d′↓ ≥ d↓. Portanto, para atualizar o limite superior d∗↑ de d∗ é su�ientefazer d∗↑ ← min {d∗↑, d′↑}. Para atualizar o limite inferior d∗↓ e�ientemente, preisamosmanter as quádruplas em uma estrutura de dados heap, ordenada pelo d↓, om mínimo naraiz.3.2.1 Corretude e TerminaçãoO laço prinipal do algoritmo preserva o seguinte invariante: Existe uma quádrupla (B,B, k, d)na �la C tal que B é a imagem B∗ do bano que é mais próxima a A. Esta a�rmação é ob-viamente válida no iníio do algoritmo. Supondo que os intervalos t.d são válidos � isto é,a distânia dist(A, t.B) ∈ t.d para ada t ∈ C � o passo 4 somente elimina uma quádruplat′′se dist(A, t′′.B) é garantidamente maior que dist(A,B′), onde B′ é a imagem andidata emC que de�ne d∗↑.Além disso, a ada passo o algoritmo elimina uma ou mais quádruplas, e/ou derementao ampo k de alguma quádrupla. Em uma quádrupla om k = 0, o intervalo d deve ser umintervalo trivial om d↓ = d↑ = dist(A,B). Portanto, no passo 2, se todas as quádruplas deC tem k = 0, então deve-se ter d↓ = d↑ = d∗↓ = d∗↑, e então o algoritmo para. Isso garanteque se o algoritmo hega ao passo 3, este passo pode ser exeutado. Isto também garanteque o algoritmo termina. Com isso, a terminação e orretude do algoritmo estão provadas.

3.2. Busa Intervalar 153.2.2 E�iêniaNo passo 3, se d′↑ < d∗↑ então d∗↑ será reduzido, e possivelmente alguma outra quádruplaserá removida de C na próxima iteração do passo 4. Por outro lado, se d′↓ > d∗↑, a quádruplat pode ser desartada. É laro que pode não oorrer nenhuma destas duas ondições, asoem que nenhum andidato é eliminado.O pior aso para o algoritmo é quando nenhuma das quádruplas é eliminada, e a iteraçãoontinua até que todas as quádruplas tenham k = 0. Neste aso, dist(k)(A,B) será aluladapara todas as N imagens B na base e todas as esalas k de 0 a m. Supondo que a versãointervalar de dist é C vezes mais ustosa que a versão simples, e que o usto de obter a imagemB(k) e alular dist(k)(A(k),B(k)) é aproximadamente Dn para imagens om n pixels, então nopior aso o usto de alular todas estas distânias será NDn(1+C/4+C/42+ · · ·+C/4m),que é inferior a NDn(1+C/3). Em omparação, o algoritmo de força bruta tem usto NDn.Portanto, o pior aso do algoritmo é somente 1 + C/3 vezes mais aro que o algoritmo deforça bruta.Se o usto de alular dist é mais do que linear no tamanho da imagem, o overhead doalgoritmo MuSIS no pior aso é ainda menor. Ou seja, se dist(A,B) usta aproximadamenteDnr para imagens om n pixels, então o overhead do MuSIS, no pior aso, é C/4r +C/42r +· · ·+ C/4mr que é menor que C/(4r − 1).No entanto, o desempenho no aso médio pode ser muito melhor que no pior aso. Cadaquádrupla (B,B, k, d) om k > 0 que é eliminada no passo 4 terá usto CDn(1/4k+1/4k+1+· · ·+ 1/4m) ≤ ((C/3)/4k−1)Dn operações, mas esta eliminação evita o álulo da distâniadist(A,B) na resolução original, que é Dn. Nesse aso, a razão entre os dois ustos (MuSISe força bruta) será (C/3)/4k−1, que é normalmente menor que 1 quando k ≥ 2. Portanto, seum número su�iente de quádruplas forem eliminadas quando elas tem um valor k grande,a eonomia ompensará o overhead.3.2.3 Como o Candidato é EsolhidoNo passo 3, existem muitas estratégias possíveis que podem ser usadas para seleionar aquádrupla do andidato (B,B, k, d) para ser re�nada.Uma possibilidade é esolher o andidato não trivial (om k > 0) que é �melhor� emalgum sentido (menor d↓, maior d↑, ou menor média (d↓+ d↑)/2), na esperança de que esseandidato seja a resposta desejada. Outra possibilidade é esolher o andidato que é �pior�por um desses ritérios, na esperança que ele seja prontamente eliminado.Na maioria dos nossos testes esolhemos o andidato om menor d↓; em aso de empate,esolhemos o de maior esala k.Observe que não podem existir dois andidatos t, t′ na lista C om t.k = t′.k = 0, umavez que um dos dois (o que tem maior d↓) deveria ter sido exluído no passo 4.

3.3. Extensão para Resultados Multiplos 163.2.4 In�uênia da Função DisrepâniaA orretude do algoritmo MuSIS é independente da função de disrepânia de imagens dist.De fato, dist não preisa ser uma métria no sentido matemátio do termo. Além disso, asubstituição de dist por qualquer função monótona dist′(A,B) = f(dist(A,B)) não altera ofunionamento do algoritmo, portanto resultará na mesma imagem B∗, om mesmo usto deproessamento.No entanto, mudanças mais radiais na função dist podem ter um impato signi�ativona e�iênia do algoritmo. Se dist depende inteiramente de detalhes pequenos que estão pre-sentes somente em níveis da pirâmide abaixo de um erto nível r, então nenhuma quádruplaserá desartada de C até que ela tenha k ≤ r. Por esta razão, o MuSIS omo desrito aimaserá ine�az para busas em bases de impressões digitais, ou de textos digitalizados.3.3 Extensão para Resultados MultiplosO algoritmo MuSIS pode ser alterado para obtenção das M melhores respostas, ou seja, dasM imagens do bano mais próximas à imagem A. Para isso é neessário alterar a de�niçàodo intervalo d∗ de modo que ele ontenha garantidamente as distânias de A a essas Mimagens. O algoritmo deve parar apenas quando M = 0 no iníio do passo 2. Ou seja, d∗↓ontinua de�nido pela equação (3.1), mas d∗↑ passa a ser o M-ésimo menor valor de t.d↑,dentre todos os andidatos t em C.No passo 2, em vez de simplesmente parar, o algoritmo deve aresentar a imagem B aoonjunto-resposta e derementar M .

Capítulo 4Distânia EulidianaA métria mais básia para avaliar a disrepânia entre duas imagens é a distânia eulidi-ana normalizada. Neste apítulo vamos de�nir essa distânia e mostrar omo ela pode serestimada a partir das imagens reduzidas.4.1 De�niçãoSupondo que as imagens A,B têm o mesmo domínio D, a distânia eulidiana normalizadaentre elas é dada pordist2(A,B) =

1

#D

√

∑

p∈D

|A[p]− B[p]|2 (4.1)Dito de outra forma, dist2(A,B) é rms(A − B), a raiz da média quadrátia da imagemdiferença A−B. Se o valor de ada pixel é um número real entre 0 e 1, o valor de dist2(A,B)também será um número entre 0 e 1. Observe que a função dist2 é uma métria no sentidomatemátio; em partiular, o valor da fórmula (4.1) é zero se e somente se as imagens sãoidêntias, e dist2(A,B)

4.2. Imagens om Diferentes Domínios 184.2 Imagens om Diferentes DomíniosEm muitas bases, as imagens têm tamanhos e/ou aspetos diferentes, e/ou estão aompa-nhadas por másaras binárias que espei�am a parte relevante da imagem, isto é o domínioefetivo da mesma. Veja a �gura 4.1.

Figura 4.1: Quatro imagens e suas respetivas másaras binárias.Para estender a métria eulidiana para tais imagens, pode-se supor que qualquer pixel A[p]situado fora do domínio efetivo da imagem A é uma or nula om valor espeial Φ, tal que|Φ− u| = |u− Φ| = 1 para qualquer or normal u ∈ V; om a ressalva que |Φ− Φ| = 0.Então a fórmula (4.1) pode ser usada, tomando-se P omo sendo a união dos domíniosefetivos de todas as imagens na base.

A B C

Masc.A Masc.B Masc.C

Figura 4.2: Resultado da distânia eulidiana apliada sobre três imagens monoro-mátias (ao alto) om domínios efetivos de�nidos por másaras (em baixo). Temosdist2(A,B) = 0.166572 < dist2(A,C) = 0.216247.Observe que as imagens A e C têm distânia maior que A e B, pois apesar de terem oresmais próximas, seus domínios efetivos (de�nidos pelas másaras) são mais disrepantes.

4.3. Estimativas da Distânia Eulidiana 19Entretanto, esta solução tem vários inonvenientes. Em primeiro lugar, pois diferençasnos parâmetros fotométrios e/ou de posiionamento (omo rotação e translação) afetamsigni�ativamente o valor da distânia. Portanto, objetos idêntios fotografados em ondiçõesdistintas podem ter disrepânias próximas a 1. Portanto, omo dito na seção 4.1, estavariante da distânia eulidiana também exige que a imagem prourada B∗ e a imagem dadaA estejam alinhadas e om fatores fotométrios iguais ou bem próximos.4.3 Estimativas da Distânia EulidianaUma maneira sistemátia de obter estimadores intervalares é usar a aritmétia intervalarde�nida na seção 2.5.2.4.3.1 Estimativa por Redução IntervalarPara muitos tipos de imagens, omo fotogra�as de ambientes internos ou externos, a distâniaeulidiana dist2(A,B) entre duas imagens pode ser estimada de forma e�iente a partir desuas versões intervalares reduzidas A(k),B(k) em qualquer esala k. Basta avaliar a fórmula(4.1) para dist2(A(k),B(k)), om as operações da aritmétia intervalar (2.15). Ou seja,alula-se

dist(k)2 ↓(A,B) =

√

√

√

√

1

#D(k)

∑

p∈D(k)

[dst↓(A(k)[p],B(k)[p])]2 (4.2)dist

(k)2 ↑(A,B) =

√

√

√

√

1

#D(k)

∑

p∈D(k)

[dst↑(A(k)[p],B(k)[p]]2 (4.3)ondedst↓(a, b) =

0 se [a↓ _ a↑] ∩ [b↓ _ b↑] 6= {} ,|a↓ − b↑| se a↓ > b↑,|a↑ − b↓| se a↑ < b↓ (4.4)

dst↑(a, b) = max{a↑ − b↓, b↑ − a↓} (4.5)Estas fórmulas produzem um intervalo d que ontém garantidamente a distânia exatadist2(A,B) na esala original, e é muitas vezes pequeno su�iente para permitir deidirqual de dois andidatos B′, B′′ é o mais pareido om a imagem A. Para ilustrar estes on-eitos, vamos mostrar estimadores para as distânias dist2(A,B) e dist2(A,C), onde A,B eC são as imagens mostradas na �gura 4.3.

4.3. Estimativas da Distânia Eulidiana 20A B C

Figura 4.3: Três imagens A,B e C usadas para exempli�ar estimadores intervalesda distânia dist2.As �guras 4.4(a) a 4.4(h) ilustram as estimativas destas distânias aluladas nas esalas dek = 7 (1 × 1 pixels) até k = 0 (128 × 128 pixels). Em ada sub-�gura, as imagens são asversões reduzidas A(k), B(k) e C(k) das imagens A, B e C, obtidas om redução intervalar.Em ada par, a imagem da esquerda é o limite inferior (A↓, B↓ ou C↓) e a da direita é olimite superior (A↑, B↑ ou C↑). As barras horizontais mostram as estimativas intervalaresdist

(k)2 (A,B) e dist(k)2 (A,C). Observe que os intervalos alulados para a esala k = 2 sãosu�ientes para deidir que dist2(A,B) < dist2(A,C), de forma que a distânia dist2 nãopreisa ser alulada nas esalas k ≤ 2.4.3.2 Estimativa por Média e Desvio PadrãoOutra maneira de obter uma estimativa intervalar e�iente para dist2(A,B) é utilizar asimagens reduzidas por média e desvio padrão, µA(k), σA(k), µB(k) e σB(k). As estimativas são

dist(k)2 ↓(A,B) =

√

√

√

√

1

#D(k)

∑

p∈D(k)

[dst ↓(A(k)[p], B(k)[p])]2 (4.6)dist

(k)2 ↑(A,B) =

√

√

√

√

1

#D(k)

∑

p∈D(k)

[dst ↑(A(k)[p], B(k)[p])]2 (4.7)ondedst↓(a, b) =

√

(µa− µb)2 + (σa− σb)2 (4.8)dst↑(a, b) =

√

(µa− µb)2 + (σa + σb)2 (4.9)Estas fórmulas também forneem um intervalo que garantidamente ontém a distâniadist2(A,B) na esala original.As �guras 4.5(a) a 4.5(h) ilustram estimativas de dist2(A,B) e dist2(A,C) para as imagensda �gura 4.3. Em ada sub-�gura, as imagens são versões reduzidas A(k), B(k) e C(k) de trêsimagens A, B e C, obtidas om redução por média e desvio padrão. Em ada par, a imagemda esquerda é a média (µA, µB ou µC), e a da direita é o desvio padrão (σA, σB ou σC). Asbarras horizontais mostram as estimativas intervalares dist(k)2 (A(k),B(k)) e dist(k)2 (A(k),C(k)),om várias esalas de resolução � desde k = 7 (1 × 1 pixels) até k = 0 (original, 128 × 128pixels). Observe que os intervalos alulados para a esala k = 5 já são su�ientes para deidirque dist2(A,B) < dist2(A,C), de forma que a distânia dist2 não preisa ser alulada nasesalas k ≤ 5.

4.3. Estimativas da Distânia Eulidiana 21A(7) = B(7) =

dist(7)2 (A,B)

A(7) = C(7) =

dist(7)2 (A,C)(a) Esala k = 7.

A(6) = B(6) =

dist(6)2 (A,B)

A(6) = C(6) =

dist(6)2 (A,C)(b) Esala k = 6.

A(5) = B(5) =

dist(5)2 (A,B)

A(5) = C(5) =

dist(5)2 (A,C)() Esala k = 5.

A(4) = B(4) =

dist(4)2 (A,B)

A(4) = C(4) =

dist(4)2 (A,C)(d) Esala k = 4.

A(3) = B(3) =

dist(3)2 (A,B)

A(3) = C(3) =

dist(3)2 (A,C)(e) Esala k = 3.

A(2) = B(2) =

dist(2)2 (A,B)

A(2) = C(2) =

dist(2)2 (A,C)(f) Esala k = 2.

A(1) = B(1) =

dist(1)2 (A,B)

A(1) = C(1) =

dist(1)2 (A,C)(g) Esala k = 1.

A(0) = B(0) =

dist(0)2 (A,B)

A(0) = C(0) =

dist(0)2 (A,C)(h) Esala k = 0.Figura 4.4: Estimadores da distânia eulidiana dist(k)2 (A(k),B(k)) e dist2(A(k),C(k)) alula-dos em várias esalas da pirâmide intervalar pelas fórmulas (4.2)�(4.5).

4.3. Estimativas da Distânia Eulidiana 22A(7) = B(7) =

dist(7)2 (A,B)

A(7) = C(7) =

dist(7)2 (A,C)(a) Esala k = 7.

A(6) = B(6) =

dist(6)2 (A,B)

A(6) = C(6) =

dist(6)2 (A,C)(b) Esala k = 6.

A(5) = B(5) =

dist(5)2 (A,B)

A(5) = C(5) =

dist(5)2 (A,C)() Esala k = 5.

A(4) = B(4) =

dist(4)2 (A,B)

A(4) = C(4) =

dist(4)2 (A,C)(d) Esala k = 4.

A(3) = B(3) =

dist(3)2 (A,B)

A(3) = C(3) =

dist(3)2 (A,C)(e) Esala k = 3.

A(2) = B(2) =

dist(2)2 (A,B)

A(2) = C(2) =

dist(2)2 (A,C)(f) Esala k = 2.

A(1) = B(1) =

dist(1)2 (A,B)

A(1) = C(1) =

dist(1)2 (A,C)(g) Esala k = 1.

A(0) = B(0) =

dist(0)2 (A,B)

A(0) = C(0) =

dist(0)2 (A,C)(h) Esala k = 0.Figura 4.5: Estimadores da distânia eulidiana dist(k)2 (A(k),B(k)) e dist2(A(k),C(k)) alu-lados em várias esalas das pirâmides reduzidas por média-desvio padrão, pelas fórmulas(4.6)�(4.9).

Capítulo 5Distânia Eulidiana CumulativaA distânia eulidiana (4.1) é a base para muitas outras funções de disrepânia maisso�stiadas. Neste apítulo vamos desrever uma dessas métrias, a distânia eulidianamultiesala umulativa dist∗2 e mostrar omo obter estimativas intervalares da mesma parauso no algoritmo MuSIS.Esta métria é uma média ponderada das distânias eulidianas em todas as esalasreduzidas, isto é,dist∗2(A,B) =

m∑

r=0

λr dist2(µA(r), µB(r)) (5.1)onde m é a esala máxima da pirâmide. Cada peso λr é um número real, entre 0 e 1, tal quea soma de todos os m pesos é igual a 1. Em geral usamos os λr em progressão geométriaom uma erta razão β, ou seja

λr = βr (β − 1)

βm − 1(5.2)No aso partiular β = 1, os pesos são todos iguais, λr = 1/(m+ 1). No aso limite β = 0,temos λ0 = 1, λr = 0 para todo r > 1; ou seja, dist∗2 reduz-se à distânia simples (monoesala)

dist2.A justi�ativa para o uso de dist∗2(A,B) é que a distânia simples dist2 dá igual impor-tânia a diferenças em detalhes de qualquer tamanho. Em ontraste, se β > 1, a distâniamultiesala dist∗2 privilegia as diferenças nos níveis mais reduzidos. Se β < 1, ela privilegiaas diferenças nos níveis mais detalhados. Por exemplo, onsidere estas imagens:23

5.1. Estimação Intervalar da Distânia Cumulativa 24A B C

Figura 5.1: Três imagens monoromátias.Para estas imagens, obtemos as seguintes distânias:Tabela 5.1: Distânias d da imagem Aem relação a B e C da �gura 5.1.Métria d d(A,B) d(A,C)dist2 0.631527 0.424313

dist∗2(β = 1/2) 0.589009 0.400259dist∗2(β = 2) 0.035757 0.139088Note que dist2 onsidera A e C mais similares que A e B devido aos detalhes pequenos(listras horizontais vs. vertiais), enquanto que dist∗2 om β = 2 dá mais peso à forma geral(quadrado vs. irulo) e onsidera A e B mais similares que A e C.5.1 Estimação Intervalar da Distânia CumulativaA distânia eulidiana umulativa pode ser estimada e�ientemente nas esalas reduzidasdas pirâmides A,B, quer obtidas por redução intervalar (4.2�4.3), quer por média e desviopadrão (4.6�4.7).Suponha que queremos alular uma estimativa dist∗2 (r)(A,B) para dist∗2(A,B) usandoapenas os níveis r, r + 1, . . . , m das pirâmides A,B. Para isto basta dividir a fórmula (5.1)em quatro partes.

dist∗2(A,B) = λ0d0 +r−1∑

k=1

λkdk + λrdr +m∑

k=r+1

λkdk (5.3)onde dr = dist2(µA(r), µB(r)), para todo r. A primeira parte λ0d0 é simplesmente λ0 dist2(A,B),portanto, podemos usar para este termo qualquer uma das estimativas intervalares dist(r)2 (A,B)desenvolvidas no apítulo 4, alulada a partir de A(r),B(r) e multipliar esse intervalopelo peso λ0. A tereira parte λrdr pode ser alulada diretamente a partir das imagensµA(r), µB(r). Para a quarta parte ∑mk=r+1 λkdk, basta aumular os valores de λrdr previa-mente alulados para todos os níveis superiores. Estas duas partes são aluladas exata-mente, gerando intervalos triviais.

5.1. Estimação Intervalar da Distânia Cumulativa 25Finalmente, para a segunda parte ∑r−1k=1 λkdk, observamos que a distânia dk, para todok < r, enontra-se no intervalo u = [dr−ε, dist(k)2 (A,B)↑+ε], onde ε é a magnitude esperadados erros de quantização nas imagens A(r) e B(r). Portanto, uma estimativa para a segundaparte ∑r−1k=1 λkdk é o intervalo u multipliado por∑mk=r+1 λk. A soma destes quatro intervalosem aritmétia intervalar ontem dist∗2(A,B).

Capítulo 6Distânia de GradienteNeste apítulo de�nimos algumas métrias que ombinam distânia eulidiana, om dete-tores de borda; e mostramos omo obter estimativas intervalares dessas métrias para usono MuSIS.6.1 Forma vs Cor na Métria EulidianaSe as imagens do bano foram obtidas sob ondições fotométrias variáveis (diferentes níveisde iluminação, ajustes de brilho e ontraste, et), a distânia eulidiana é geralmente inade-quada, pois ela é muito mais sensível aos valores dos pixels do que à forma dos objetos. Vejaa �gura 6.1.A B C

Figura 6.1: Três imagens monoromátias. Neste exemplo, dist2(A,B) = 0.110640 <dist2(A,C) = 0.433529.6.2 GradienteUma maneira de orrigir este problema é utilizar uma função distânia que seja mais sensívelàs bordas do que às partes onstantes da imagem. A forma mais simples de obter este efeitoé utilizar as derivadas espaiais da imagem.De modo geral, o gradiente ▽f de uma função f de�nida sobre o Rn é a lista de derivadaspariais de f em relação a ada oordenada, ou seja, ▽f = (∂f/∂x1, ∂f/∂x2, . . . , ∂f/∂xn).26

6.2. Gradiente 27Em proessamento de imagens, em partiular, o gradiente ▽I de uma imagem onsiste dasderivadas da intensidade em relação às oordenadas x e y do domínio.▽I[p] =

(

∂I

∂x[p],

∂I

∂y[p]

) (6.1)Na prátia, o gradiente ▽I de uma imagem é geralmente alulado pelo operador Sobel [20℄,que alula o valor aproximado de ▽I[p] a partir de 9 pixels de I dentro de uma janela de3× 3 pixels ao redor do ponto p.O módulo do gradiente |▽I[p]| é muito usado na deteção de bordas de objetos emimagens. O resultado desse operador apliado a uma imagemmonoromátia é outra imagemmonoromátia onheida omo imagem gradiente. Veja a �gura 6.2. (Para que a imagemgradiente tenha o mesmo tamanho da original, é neessário um tratamento espeial ao longodas bordas.)

→Figura 6.2: Uma imagem I (esq.) e a imagem gradiente |▽I| orrespondente (dir.).Uma solução parial para o problema dos efeitos fotométrios seria usar a métria dist▽2 (A,B) =dist2(|▽A|, |▽B|) para omparar as imagens. Observe que, na imagem gradiente, regiões omum valor uniforme qualquer tornam-se regiões de valor zero e, portanto, não afetam o va-lor da distânia dist▽2 . Ou seja, dist▽2 depende apenas das bordas e outras regiões onde aintensidade varia rapidamente.

|▽A| |▽B| |▽C|

Figura 6.3: Imagens-gradiente das três imagens da �gura 6.1. Neste exemplo,dist▽2 (A,B) = 0.165780 > dist

▽

2 (A,C) = 0.030366.Porém, o valor do operador gradiente na borda ainda é proporional à intensidade da ilu-minação dos pixels. Ou seja, se J [p] = 2I[p] para todo pixel p, então |▽J [p]| = 2 |▽I[p]|.Esta araterístia signi�a duas imagens de um mesmo objeto A,B om diferenças apenasna intensidade de iluminação possuem imagens-gradiente om valores diferentes, e portantosua distânia dist▽2 será maior que zero. Este problema é ilustrado na �gura 6.4.

6.3. Gradiente Normalizado 28A B C

▽A ▽B ▽C

Figura 6.4: Três imagens monoromátias e suas imagens gradiente. Neste exemplo,dist▽2 (A,B) = 0.092293 < dist

▽

2 (A,C) = 0.112663.6.3 Gradiente NormalizadoPara eliminar a dependênia da iluminação, em nosso trabalho utilizamos um operadorespeial, o gradiente normalizado,HI[p] =

S3×3I[p]√

V5×5I[p](6.2)onde S3×3I é a imagem gradiente |▽I| alulada pelo operador de Sobel om uma janelade 3 × 3 pixels, e V5×5I é a variânia ponderada da imagem I alulada em uma janelade 5 × 5 pixels, usando pesos aproximadamente gaussianos dentro de ada janela. Maisespei�amente, S3×3I é o resultado da onvolução da imagem I om a matriz de oe�ientes

S =

−1 0 1

−2 0 2

−1 0 1

(6.3)A variânia V5×5I[p] é de�nida pela fórmulaV5×5I[p] =

1

256

∑

r

V[r](I[p− r]− µ)2 (6.4)onde V é a matriz de pesos

6.3. Gradiente Normalizado 29V =

1 4 6 4 1

4 16 24 16 4

6 24 36 24 6

4 16 24 16 4

1 4 6 4 1

(6.5)e µ é a média loal alulada om esses mesmos pesos, isto é,µ =

1

256

∑

r

V[r]I[p− r] (6.6)Nos dois asos, r varia sobre os pares de índies da matriz V, {−2 · · ·+ 2} × {−2 · · ·+ 2}Observe que o gradiente normalizadoH é insensível à iluminação, isto é, se J [p] = α+βI[p]para todo pixel p em alguma janela 5 × 5, ainda assim temos HJ [p] = HI[p] para o pixelentral dessa janela para qualquer α > 0 e qualquer β.→Figura 6.5: Uma imagem monoromátia (esq.) e sua imagem de gradiente norma-lizado |HI| (dir.).Na prátia é preferivel usar uma versão modi�ada da fórmula (6.2).

HI =S3×3I[p]

√

V5×5I[p] + ǫ2(6.7)onde ǫ2 é a variânia do ruído esperado na imagem. Esta alteração suprime ontornos falsosdevido ao ruído, em regiões onde a imagem �limpa� teria valor uniforme.Note que esta alteração destrói a invariânia fotométria: H(αI) 6= HI, espeialmentenas regiões mais esuras da imagem.

Original ǫ = 0.002 ǫ = 0.02 ǫ = 0.2

Figura 6.6: Uma imagem monoromátia I (esq.) e três imagens de gradiente nor-malizado HI om diferentes valores do parâmetro ǫ.

6.4. Distânia de Gradiente Normalizado 306.4 Distânia de Gradiente NormalizadoO operador H permite eliminar a in�uenia da iluminação na busa por onteúdo. Espei�a-mente, podemos substituir a distânia eulidiana dist2(A,B) entre as imagens pela distâniaeulidiana de gradiente normalizado, de�nida pordistH2 (A,B) = dist2(|HA| , |HB|) (6.8)Desta forma somente as posições das bordas da imagem são relevantes, e não suas intensi-dades. Veja a �gura 6.7.

HA HB HC

Figura 6.7: Resultado da operação |H| apliada às imagens da �gura 6.4. Temosdist2(|HA| , |HB|) = 0.091912 > dist2(|HA| , |HC|) = 0.015626.6.5 Usando Gradiente Normalizado no MuSISO gradiente normalizado pode ser usado no MuSIS de três maneiras: apliado às imagens dabase original, om distânia eulidiana monoesala; idem, om distânia eulidiana umula-tiva; ou sobre a pirâmide de imagens, umulativamente.6.5.1 Gradiente na Base Original, om Métria MonoesalaPara usar o MuSIS om a distânia distH2 , basta fazer um pré-proessamento da base antes deonstruir as pirâmides. Ou seja, ada imagem I da base é substituída pela imagem G = |HI|orrespondente na busa, apliamos a mesma operação à imagem dada A e apliamos oMuSIS a estas imagens om distânia eulidiana dist2, omo desrito no apítulo 3.

I µG(0) µG(1) µG(2) µG(3) µG(4) µG(5) µG(6)

H

→Figura 6.8: Pirâmide obtida a partir da redução da base om imagens gradiente.Em prínipio, a e�iênia do algoritmo MuSIS para esta base pré-proessada deve ser om-parável à observada nas busas sobre o bano original, pois estamos usando a mesma função

6.5. Usando Gradiente Normalizado no MuSIS 31distânia dist2 e os mesmos estimadores desritos no apítulo 4. Dependendo das imagens,entretanto, a busa pode �ar mais ou menos e�iente, pois o pré-proessamento geralmentealtera a distribuição das distânias.Observe que o gradiente H é sensível apenas a detalhes om 3 a 5 pixels de largura.Portanto, om qualquer das duas métrias distH2 e distH∗2 , a apliação do gradiente apenas naesala original neessariamente dá mais peso a detalhes pequenos das formas dos objetos doque às suas formas gerais. Veja a �gura 6.9.A B C

HA HB HC

Figura 6.9: Resultado da operação H apliada sobre três imagens monoromátias.Temos dist2(HA,HB) = 0.105913 < dist2(HA,HC) = 0.167085.Uma vez que a distânia distH2 é a própria dist2, ela pode ser estimada a partir dos níveismenores das pirâmides pelas fórmulas desenvolvidas no apítulo 4.6.5.2 Gradiente na Base Original, om Métria CumulativaO pré-proessamento I → |HI| também pode ser ombinado om a distânia eulidianamultiesala umulativa. Isto é, podemos usar a métria distH∗2 de�nida pordistH∗2 (A,B) = dist

∗

2(G,H) =

m∑

r=0

λr dist2(µG(r), µH(r)) (6.9)onde G = |HA| e H = |HB|.

6.5. Usando Gradiente Normalizado no MuSIS 32A B C

G = |HA| H = |HB| K = |HC|

µG(1) µH(1) µK(1)

µG(2) µH(2) µK(2)

µG(3) µH(3) µK(3)

µG(4) µH(4) µK(4)... ... ...µG(8) µH(8) µK(8)Figura 6.10: Distânia eulidiana umulativa om gradiente normalizado apliadoà base original. Temos distH∗2 (A,B) = 0.079349 > distH∗2 (A,C) = 0.059057, om oparâmetro β = 2.Tabela 6.1: Termos da distânia distH∗2 em ada esala da pirâmide para as imagens da�gura 6.10, om β = 2. Nesta tabela dr(G,H) = dist2(µG(r), µH(r)) e analogamentepara dr(G,K).

r dr(G,H) λrdr(G,H) dr(G,K) λrdr(G,K) λr8 0.002649 0.000000 0.002540 0.000000 0.5009787 0.011651 0.005268 0.002568 0.000625 0.2504896 0.017937 0.007820 0.016793 0.005209 0.1252455 0.030051 0.009850 0.024176 0.006647 0.0626224 0.038129 0.010592 0.043941 0.008122 0.0313113 0.055107 0.011190 0.075704 0.009160 0.0156562 0.073220 0.011467 0.108838 0.009637 0.0078281 0.094251 0.011581 0.143853 0.009826 0.0039140 0.106725 0.011581 0.164302 0.009831 0.001957Total 0.42972 0.079349 0.582715 0.059057 1.000000Observe que as imagens µG(r) e µH(r) são menos semelhantes que µG(r) e µK(r) para k ≥ 5

6.6. Gradiente em Cada Nível da Pirâmide 33e mais semelhantes para k ≤ 4. A distânia distH∗2 pode ser estimada pelas mesmas fórmulasusadas para estimar dist∗2 (ap. 5).6.6 Gradiente em Cada Nível da PirâmideUma maneira mais e�az de forneer mais peso à forma geral dos objetos é apliar o gradienteH em ada nível da pirâmide, depois da redução. Ou seja, para ada imagem I e ada nívelr alulamos uma imagem δI(r) = H(µI(r)). Veja �gura 6.11. De�nimos então dist⋆(A,B) =∑

k λk dist2(δA(k), δB(k)). A �gura 6.12 e a tabela 6.2 mostram o álulo de dist⋆()2 .

µI(0) µI(1) µI(2) µI(3) µI(4) µI(5) µI(6)

H2↓ H2↓ H2↓ H2↓ H2↓ H2↓ H2↓

δI(0) δI(1) δI(2) δI(3) δI(4) δI(5) δI(6)Figura 6.11: Pirâmide obtida a partir da redução da base original om gradiente Hapliado a ada nível.

6.6. Gradiente em Cada Nível da Pirâmide 34A B C

δA(0) =∣

∣HµA(0)∣

∣ δB(0) =∣

∣HµB(0)∣

∣ δC(0) =∣

∣HµC(0)∣

∣

δA(1) =∣

∣HµA(1)∣

∣ δB(1) =∣

∣HµB(1)∣

∣ δC(1) =∣

∣HµC(1)∣

∣

δA(2) =∣

∣HµA(2)∣

∣ δB(2) =∣

∣HµB(2)∣

∣ δC(2) =∣

∣HµC(2)∣

∣

δA(3) =∣

∣HµA(3)∣

∣ δB(3) =∣

∣HµB(3)∣

∣ δC(3) =∣

∣HµC(3)∣

∣

δA(4) =∣

∣HµA(4)∣

∣ δB(4) =∣

∣HµB(4)∣

∣ δC(4) =∣

∣HµC(4)∣

∣... ... ...δA(8) =

∣

∣HµA(8)∣

∣ δB(8) =∣

∣HµB(8)∣

∣ δC(8) =∣

∣HµC(8)∣

∣Figura 6.12: Distânia eulidiana umulativa om o gradiente H apliado a adanível da pirâmide. Temos dist⋆(A,B) = 0.391287 > dist⋆(A,C) = 0.160042, om oparâmetro β = 2.Tabela 6.2: Termos de dist⋆ em ada esala da pirâmide, para as imagens da �-gura 6.12, om β = 2. Nesta tabela, dr(A,B) = dist2(δA(r)), δB(r)) e analogamentepara dr(A,C).r dr(A,B) λrdr(A,B) dr(A,C) λrdr(A,C) λr8 0.000000 0.000000 0.000000 0.000000 0.5009787 0.000000 0.000000 0.000000 0.000000 0.2504896 0.220548 0.027622 0.063926 0.008006 0.1252455 0.314205 0.047299 0.101334 0.014352 0.0626224 0.352410 0.058333 0.251319 0.022221 0.0313113 0.292032 0.062905 0.290341 0.026767 0.0156562 0.212835 0.064571 0.271129 0.028889 0.0078281 0.154082 0.065174 0.218061 0.029743 0.0039140 0.106725 0.065383 0.164302 0.030064 0.001957Total 1.652837 0.391287 1.360412 0.160042 1.000000Observe que δA(r) e δB(r) são menos semelhantes que δA(r) e δC(r) para r ≤ 3.

6.6. Gradiente em Cada Nível da Pirâmide 35Esta versão da distânia umulativa de gradiente pode ser estimada e�ientemente nasesalas reduzidas da pirâmide. Suponha que queremos alular uma estimativa dist⋆(r)2 (A,B)para dist⋆2(A,B) usando apenas os níveis r, r+1, . . . , m das pirâmides A,B. Para isso, omo�zemos na seção 5, dividimos a fórmula (6.9) em três partes:dist

⋆(r)2 (A,B) =

r−1∑

k=0

λkdk + λrdr +

m∑

k=r+1

λkdk (6.10)onde dr = dist2(δA(r), δB(r)), para todo r.A segunda parte λrdr pode ser alulada diretamente a partir das imagens δA(r), δB(r).Para a tereira parte ∑mk=r+1 λkdk, apenas aumulamos os valores de λkdk que obtivemosanteriormente quando alulamos os estimadores dist⋆(k)2 (A,B) para k = r + 1, r + 2, . . . , m.Estas duas partes são aluladas exatamente, gerando intervalos triviais.Quanto à primeira parte, infelizmente não é possível estimar as distânias dk = dist2(δA(k), δB(k))para k < r onsiderando as imagens de esalas maior ou igual a r. Supomos então o pioraso, ou seja, usamos omo estimativa para dk o intervalo [0, 1℄. Portanto, a estimativa paraa primeira parte ∑r−1k=1 λkdk é [0,∑r−1k=0 λk].A soma destes três intervalos em aritmétia intervalar deve onter dist⋆(A,B).

Capítulo 7Métrias para Imagens ColoridasAs métrias e estimativas desritas no apítulo 5 e 6 podem ser failmente adaptados paratrabalhar om imagens oloridas.Neste apítulo vamos de�nir brevemente algumas das métrias deste tipo, sem desreveros respetivos estimadores.7.1 Distânia Eulidiana RGBA métria eulidiana pode ser trivialmente estendida para imagens oloridas. Basta tratar oíndie do anal de or omo uma tereira dimensão do domínio da imagem. Ou seja, bastaalular a fórmula (4.1) om [p, c] em vez de [p]:dist2(A,B) =

√

1

#K

∑

c∈K

1

#P

∑

p∈P

|A[p, c]− B[p, c]|2 (7.1)onde K é o onjunto dos índies dos anais de or. Esta extensão pode ser apliada a todasas métrias disutidas neste trabalho.7.2 Distânia Eulidiana YuvNo entanto, em muitas apliações, a diferença entre tons de or (por exemplo: vermelho ouverde) é muito signi�ativa, ao ontrário das diferenças de brilho (laro ou esuro). Veja�gura 7.1.36

7.3. Distânia de Gradiente Yuv 37A B C

Figura 7.1: Distânia eulidiana de imagens oloridas no espaço RGB. Temosdist2(A,B) = 0.242803 > dist2(A,C) = 0.098406.Nessas apliações, uma solução melhor é onverter as imagens do espaço de or RGB para oespaço Yuv (luminâniaY, rominânia relativa u, v) antes de alular a distânia eulidiana.Desta forma, a diferença de brilho afeta apenas um anal (Y) enquanto que nos outros doisa distânia leva em onta apenas o tom da or. Podemos atribuir pesos à luminânia erominânia, isto é,

distY uv2 (A,B) =√

η|Y A− Y B|2 + κ(|uA− uB|2 + |vA− vB|2) (7.2)onde |I|2 = rms I e os parâmetros η e κ são esolhidos pelo usuário om η + 2κ = 1. Assim,por exemplo, se η = 1 e κ = 0 obtemos a distânia eulidiana sobre a versão monoromátiadas imagens, enquanto que om η = 0 e κ = 1 obtemos uma métria que leva em onta apenasos tons das ores e não seu brilho. No exemplo da �gura 7.1, om η = 0, κ = 1/2, temosdistY uv2 (A,B) = 0.234256 > dist

Y uv2 (A,C) = 0.038292, no exemplo da �gura 7.1, depoisde onverter as imagens A,B,C para Yuv, temos dist2(A,B) = 0.234256 > dist2(A,C) =

0.038292 om η = 1/3, κ = 1/3.7.3 Distânia de Gradiente YuvComo observamos na seção 3.1, a distânia eulidiana � tanto no espaço RGB quanto noespaço Yuv � é mais sensível a valores dos pixels do que à formas dos objetos. Uma maneirade soluionar este problema é apliar o operador gradiente normalizado |H| sobre as imagens.Veja a �gura 7.2.→Figura 7.2: Uma imagem olorida (esq.) e sua imagem gradiente olorida (dir.)obtida apliando a operação H a ada anal no espaço RGB.Entretanto, esta transformação é muito drástia e elimina não só os efeitos da iluminaçãona métria, mas também o efeito das formas.

7.4. Operador Cartoon 387.4 Operador CartoonPara tornar a métria sensível à borda mas sem ignorar as ores de áreas uniformes, podemosutilizar a norma de gradiente apenas para omparar o anal Y, e usar distânia eulidiananormal para os anais u,v. Ou seja, usamos a distâniadistHY uv2 =

√

η|HY A− HY B|2 + κ(|uA− uB|2 + |vA− vB|2) (7.3)Para visualizar onvenientemente o efeito desta transformação, usamos uma variante dooperador gradiente normalizado no espaço Yuv, que hamamos de operador artoon. Esteoperador onsiste em apliar o gradiente normalizado ao anal de iluminação Y apenas,mantendo os anais u, v inalterados. Mais exatamente, o operador artoon é de�nido pelosseguintes passos apliados a ada pixel:1. Conversão do espaço de ores RGB para YUV;2. Conversão do espaço de ores YUV para Yuv;3. Apliação do gradiente normalizado H sobre o anal luminânia Y;4. Substituição de Y por 1/2− Y/2;5. Conversão do espaço Yuv para YUV;6. Conversão do espaço YUV para RGB.No passo 1, apliamos a fórmula (2.1) sobre ada pixel I[p]. Esta fase apenas separa ailuminação, mas mantém os anais de rominânia proporionais à luminânia. No passo 2usamos as fórmulas (2.3) para esalar os anais U e V obtendo o espaço Yuv, eliminandoportanto o efeito da luminânia sobre a rominânia. A apliação do gradiente normalizado(6.2), no anal Y (passo 3) destaa as bordas dos objetos (onde geralmente há sua or debrilho e não apenas de tom).No passo 4, a esala do anal Y reduzida e invertida de modo que o valor 0.0 passa a ser0.5 e o valor 1.0 passa a ser 0.0. Desta forma, regiões de or onstante �am om Y = 0.5, eas bordas �am om Y = 0. Assim, quando o pixel é onvertido de volta para o espaço RGB(equações (2.3) e (2.2)), as áreas de or uniforme e brilho tornam-se áreas de or uniforme,om a mesma tonalidade original mas om brilho �xo 0.5. Veja a �gura 7.3.

→Figura 7.3: Uma imagem olorida (esq.) e o resultado do operador artoon (dir.).Em partiular, regiões de or preta (0, 0, 0) ou qualquer tom de inza (Y, Y, Y ) são transfor-madas em regiões de inza médio (0.5, 0.5, 0.5).

7.5. Estimadores de Métrias para Imagens Coloridas 397.5 Estimadores de Métrias para Imagens ColoridasQualquer métria de�nida neste apítulo pode ser utilizada no MuSIS mediante o pré-proessamento adequado da base. Todas estas métrias possuem versões monoesala e mul-tiesala, esta última om pré-proessamento do nível 0 ou de toda pirâmide. Entretanto, porser uma variante do gradiente normalizado, a parte da distânia artoon referente ao anal Ysó pode ser efetivamente estimada quando se usa uma métria umulativa omo na seção 5.1.Por outro lado, a parte da distânia referente aos anais u e v, onde a distânia eulidianaé apliada diretamente, pode em tese ser e�ientemente estimada a partir das esalas maisreduzidas. Não abordaremos este problema neste trabalho.

Capítulo 8Bases de ImagensNos testes utilizamos algumas bases om 1000 a 20000 imagens, de várias naturezas e pro-veniênias. As bases utilizadas estão relaionadas na tabela 8.1 e são desritas em maisdetalhes nas seções 8.1�8.6.Tabela 8.1: As bases usadas nos testes, om as dimensões, esala máxima m, onúmero de imagens N e a origem.Base Dimensões m Num. Imagens OrigemALNT01 192× 192 6 1653 ALOI-VIEWC1NT01 128× 128 7 2842 Calteh-101C2NT01 128× 128 7 14442 Calteh-256CRNT01 256× 256 8 19998 CorelCRNT02 128× 128 7 3841 CorelFFNT01 256× 256 8 3462 Free Photos NatureJSNT01 192× 192 6 1000 JSCada base de testes ontém imagens de tamanho uniforme, onforme exigido pela imple-mentação. Para satisfazer esta exigênia, ada imagem bruta (obtida da fonte externa) foisubmetida a um proesso de regularização: se a imagem bruta tem dimensões inferiores aoespei�ado ela é eliminada, senão ela é ortada om uma janela de tamanho máximo easpeto apropriado, entrada no domínio bruto. Esta versão ortada é então reduzida paraas dimensões espei�adas. Este método mantém a esala relativa dos dois eixos. Deidimoseliminar as imagens pequenas, ao invés de ampliá-las, pois esta alternativa riaria muitasimagens �borradas� que poderiam distorer as onlusões dos testes, espeialmente nas es-alas mais detalhadas. Cada base tem uma versão olorida e uma versão monoromátia(anal Y apenas).Para nossas bases usamos um padrão sistemátio de nomenlatura, {NN}{P}{S}{V V }de forma a failitar a identi�ação omo mostrado a seguir:• As duas primeiras letras {NN} indiam a origem externa das imagens;40

8.1. Bases AL 41• A tereira letra {P} de�ne se as imagens são naturais (N) ou de gradiente (G). Na versãomonoromátia foi apliado o operador gradiente normalizado, e na versão olorida ooperador artoon;• A quarta letra {S} de�ne se a base é ompleta (T) ou uma amostra relativamentepequena (S) da mesma;• Os dois últimos números {V V } indiam a versão da base.8.1 Bases ALNossa base AL foi obtida a partir do subonjunto ALOI-VIEW da base da base ALOI (Ams-terdam Library of Objet Images) [1℄. A base ALOI-VIEW possui 72000 imagens oloridasde 1000 objetos diversos, ada um fotografado em 72 posições (diferindo de rotação de 5◦ emtorno de seu eixo vertial). Em todas as imagens, o objeto foi fotografado ontra um fundohomogêneo relativamente esuro. Veja a �gura 8.1.

Figura 8.1: Algumas imagens da base ALOI-VIEW.Para ada imagem há uma másara binária que permite distinguir o objeto do fundo. Abase AL foi obtida sorteando imagens da ALOI-VIEW obtendo a base ALNT01 om 1653imagens (veja �gura 8.2). Para ada objeto, tomamos a imagem om rotação 0◦, e zeroou mais imagens om outras rotações. Estas foram sorteadas de modo a obter no máximoaproximadamente 2000 imagens. Para ada imagem determinamos a janela envolvente doobjeto a partir da másara. Imagens nas quais o objeto possui dimensões inferiores ao espe-i�ado foram desartados. Caso ontrário, a janela da imagem é reortada e regularizadaomo expliado anteriormente.Figura 8.2: Algumas imagens da base ALNT02.

8.2. Base C1 42A base ALGT01, om 1652 imagens foi gerada a partir da base ALNT01 pela apliação dogradiente normalizado (seção 4.1). Veja a �gura 8.3.Figura 8.3: Algumas imagens da base ALGT01 (monoromátias).

Figura 8.4: Algumas imagens da base ALGT01 (oloridas).8.2 Base C1A base C1 foi derivada da base Calteh-101 [2℄, esta base possui 9144 imagens om dimensõesmáximas de 300×200 pixels. Esta base apresenta araterístias variadas de forma, textura,or, iluminação, et; mostrando-se assim omo uma base interessante em busas genériasom objetos diversos em ambientes habituais, distribuídos em 102 lasses omo érebro,piano, helióptero, et. Segundo a doumentação, parte destas imagens foi fotografada emsetembro de 2003 pelos autores, e parte foi obtida via o serviço de busa do Google Images.Algumas amostras desta base são apresentadas na �gura 8.5.

Figura 8.5: Algumas imagens da base Calteh-101.

8.3. Base C2 43Da base Calteh-101, sorteamos era de 3000 imagens que foram regularizadas para 128×128pixels. Após o pré-proessamento restaram 2841 imagens em nossa base C1NT01. Veja a�gura 8.6.Figura 8.6: Algumas imagens da base C1NT01.A base C1GT01 om 2842 imagens foi obtida a partir da base C1NT01 pela apliação dogradiente normalizado (seção 4.1). Veja a �gura 8.7.

Figura 8.7: Algumas imagens da base C1GT01 (monoromátias).Figura 8.8: Algumas imagens da base C1GT01 (oloridas).8.3 Base C2Nosso onjunto C2 é a base Calteh-256 [3℄, suessora da base Calteh-101. Ela foi oletadade maneira similar em 2006, porém om maior rigor na �ltragem e lassi�ação. Ela estádividida em 257 lasses, totalizando 30608 imagens diversas, organizada em grupos � arros,pianos, asas, et � om diversos ambientes e ondições de iluminação, angulos, fundo, et.Veja �gura 8.9.

8.3. Base C2 44

Figura 8.9: Algumas imagens da base Calteh-256.Todas as imagens foram pré-proessadas da forma que imagens om dimensões inferiores a128×128 foram desartadas e o restante das imagens foram ortadas e/ou redimensionadas,obtendo a base de testes C2NT01 om 14441 imagens. Observe alguns exemplos na �gura 8.10.

Figura 8.10: Algumas imagens da base C2NT01.Outra base gerada derivada da Calteh-256 é a C2GT01, onde sobre as imagens da base C2NT01é apliado o gradiente normalizado, obtendo imagens omo as apresentadas na �gura 8.11.Figura 8.11: Algumas imagens da base C2GT01 (monoromátias).

Figura 8.12: Algumas imagens da base C2GT01 (oloridas).

8.4. Base CR 458.4 Base CRNossa base CR foi extraída da Corel Gallery Magi - Stok Photo Library 2 [4℄, que é disponi-bilizada para �ns aadêmios. Ela possui originalmente 20000 imagens distribuídas em váriasategorias, resoluções e ambientes. Exemplos de imagens podem ser vistos na �gura 8.13.Figura 8.13: Algumas imagens da base Corel.A regularização dessa oleção ompleta para o tamanho 256× 256 deu origem à nossa basede teste CRNT01, om 19997 imagens. A base CRNT02 é uma amostra de CRNT01 om 3841imagens e dimensões 128×128, esolhidas aleatoriamente sem repetições. Veja a �gura 8.14.Figura 8.14: Algumas imagens da base CRNT01.O gradiente normalizado foi apliado sobre as imagens das bases CRNT01 e CRNT02 gerandoas bases CRGT01 e CRGT02. Veja a �gura 8.15.

Figura 8.15: Algumas imagens da base CRGT01 (monoromátias).

8.5. Base FF 46

Figura 8.16: Algumas imagens da base CRGT01 (oloridas).8.5 Base FFNossa base FP foi derivada da oleção Free Photos Nature, disponibilizada gratuitamentepara uso não omerial [5℄, representando uma grande oleção de fotogra�as diversas, or-ganizada em 171 seções om 3542 ategorias, totalizando mais de 129600 imagens. Esta éonstituída basiamente de imagens livres enontradas na web ou forneidas pelos usuáriosdo site. Veja a �gura 8.17.Figura 8.17: Algumas imagens da base Free Photos Nature.Nossa base FFNT01 foi obtida pela regularização de um subonjunto desta base om 3489imagens para dimensões 128× 128 resultando em 3462 imagens. Veja a �gura 8.18.

Figura 8.18: Algumas imagens da base FFNT01.Da mesma forma apresentadas nas bases anteriores, apliamos o gradiente sobre a baseFFNT01 obtendo a base FFGT01 exempli�ada na �gura 8.19.

8.6. Base JS 47

Figura 8.19: Algumas imagens da base FFGT01 (monoromátias).Figura 8.20: Algumas imagens da base FFGT01 (oloridas).8.6 Base JSA base JS ontém 1000 imagens inluindo era de 300 fotos de fragmentos de erâmia,bem omo outras imagens geométrias diversas, om dimensões 256 × 256 pixels. Veja a�gura 8.21.

Figura 8.21: Algumas imagens da base JSNT01.Para nossos testes renomeamos a base para JSNT01. Partindo da base JSNT01 obteve-se abase JSGT01 om a apliação do gradiente sobre a luminosidade das imagens (�gura 8.22) ea ombinação om os anais de or omo é mostrado na �gura 8.23.Figura 8.22: Algumas imagens da base JSGT01 (monoromátias).

8.6. Base JS 48

Figura 8.23: Algumas imagens da base JSGT01 (oloridas).

Capítulo 9Testes de Desempenho9.1 Metodologia de TestesNos testes, o algoritmo MuSIS foi usado para prourar apenas uma imagem resposta Bmais próxima a uma imagem dada A. Em ada teste, a imagem modelo A foi esolhidaaleatóriamente dentre as imagens da própria base, porém exluída da base durante a busa.Para avaliar o desempenho do algoritmo MuSIS, usamos o us