UNIVERSIDADE ESTADUAL PAULISTA "JÚLIO DE MESQUITA FILHO" FACULDADE DE CIÊNCIAS - CAMPUS BAURU DEPARTAMENTO DE COMPUTAÇÃO BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO VICTOR HUGO DA SILVA DIAS DETECÇÃO DE IMAGENS EDITADAS POR SEAM CARVING BAURU 2018 VICTOR HUGO DA SILVA DIAS DETECÇÃO DE IMAGENS EDITADAS POR SEAM CARVING Trabalho de Conclusão de Curso do Curso de Ciência da Computação da Universidade Esta- dual Paulista “Júlio de Mesquita Filho”, Facul- dade de Ciências, Campus Bauru. Orientador: Profa. Dra. Simone das Graças Do- mingues Prado Coorientador: Prof. Dr. Kelton Augusto Pon- tara da Costa BAURU 2018 Victor Hugo da Silva Dias Detecção de imagens editadas por seam carving/ Victor Hugo da Silva Dias. – Bauru, 2018- 31 p. : il. (algumas color.) ; 30 cm. Orientador: Profa. Dra. Simone das Graças Domingues Prado Trabalho de Conclusão de Curso – Universidade Estadual Paulista “Júlio de Mesquita Filho” Faculdade de Ciências Ciência da Computação, 2018. 1. Pericia Computacional 2. Seam Carving Victor Hugo da Silva Dias Detecção de imagens editadas por seam carving Trabalho de Conclusão de Curso do Curso de Ciência da Computação da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Faculdade de Ciências, Campus Bauru. Banca Examinadora Prof. Dr. Kelton Augusto Pontara da Costa Co-orientador Prof. Associado. Aparecido Nilceu Marana Convidado 1 Prof. Dr. Clayton Reginaldo Pereira Convidado 2 Bauru, 14 de novembro de 2018. Resumo Seam carving é um método de redimensionamento de imagens simples e que mantém o conteúdo. Considerando que pode causar problemas na análise das imagens por parte da perícia forense computacional, a proposta deste trabalho foi determinar a técnica ou técnicas que possam ser aplicadas para detectar o uso em uma imagem sem ter o conhe- cimento da original de forma eficiente. Durante o desenvolvimento, foi comparado o uso de 3 técnicas em um mesmo conjunto de imagens e duas técnicas apresentaram um bom desempenho. Palavras-chave: Seam, carving, redimensionamento, imagens, perícia, forense, compu- tacional Abstract Seam carving is a simple content-aware image resizing. Considering that it may cause problems with Computational Forensic Expertise, the purpose of this work was to deter- mine a good technique that can be applied to detect it use in an image without being aware of the original one. During the development, we compared the use of 3 techniques in the same set of images. Keywords: Seam, carving, content-aware, image, forensic Lista de ilustrações Figura 1 – Imagem de sapatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Figura 2 – Figura 1 com remoção de um sapato . . . . . . . . . . . . . . . . . . . . . 15 Figura 3 – Imagem de uma arvore de cerejeira com seam e half seam representado . . . 15 Figura 4 – Ilustrando o conceito de LBP com 𝑅 = 1 e 𝑃 = 8 . . . . . . . . . . . . . . 17 Figura 5 – Representação de vizinhança circular e retangular . . . . . . . . . . . . . . 19 Figura 6 – Representação de vizinhança 5x5 em uma imagem com o pixel central 𝑍0 . . 19 Figura 7 – Exemplo hiperplano obtido por uma SVM com a aplicação de uma função kernel 𝜑 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Figura 8 – Arquitetura de uma Rede Neural por Convolução típica. . . . . . . . . . . 22 Figura 9 – Imagem com seam carving aplicado. . . . . . . . . . . . . . . . . . . . . . 24 Figura 10 – Imagem com seam carving aplicado. . . . . . . . . . . . . . . . . . . . . . 24 Figura 11 – Imagem com seam carving aplicado. . . . . . . . . . . . . . . . . . . . . . 25 Figura 12 – Versão original da figura 9 . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Figura 13 – Versão original da figura 10 . . . . . . . . . . . . . . . . . . . . . . . . . 26 Figura 14 – Versão original da figura 11 . . . . . . . . . . . . . . . . . . . . . . . . . 26 Figura 15 – Taxas de acerto e erros da SVM linear para o método do Yin et al. (2015) . 27 Figura 16 – Taxas de acerto e erros da SVM quadrática para o método do Ye e Shi (2017) 28 Figura 17 – Quadro resumo de eficiência dos métodos implementados . . . . . . . . . . 29 Lista de tabelas Tabela 1 – Notações utilizadas para definição de Seams . . . . . . . . . . . . . . . 13 Tabela 2 – Notações utilizadas para definição de LBP . . . . . . . . . . . . . . . . 17 Tabela 3 – Notações utilizadas para definição de LDP . . . . . . . . . . . . . . . . 18 Tabela 4 – Acurácia para o método do Yin et al. (2015) . . . . . . . . . . . . . . 27 Tabela 5 – Acurácia para o método do Ye e Shi (2017) . . . . . . . . . . . . . . . 28 Lista de abreviaturas e siglas LBP Local Binary Pattern LDP Local Derivative Pattern SVM Support Vector Machine CNN Convolutional Neural Network Lista de símbolos ∑︀ Somatória ∈ Pertence ≥ Maior ou igual que > Maior que 𝛼 Alpha 𝜑 Phi (minusculo) Sumário 1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1 Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Objetivo Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 DEFINIÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1 Seam Carving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.1 Seams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Gradiente em imagens . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.1 Filtro Sobel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Local Binary Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Local Derivative Pattern . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.1 Vizinhança . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4.2 Derivada de primeira ordem . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.3 LDP de segunda ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.4 LDP de ordem n-ésima . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Support Vector Machine . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.6 Convolutional Neural Networks . . . . . . . . . . . . . . . . . . . . . . 21 3 MÉTODO DE PESQUISA . . . . . . . . . . . . . . . . . . . . . . . 23 3.1 Base de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 RESULTADOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5 CONCLUSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 11 1 Introdução Seam carving é uma técnica para redimensionamento de imagens, aprimoramento do conteúdo e remoção de objetos definida e proposta por Avidan e Shamir (2007) como uma alternativa mais eficaz para métodos que usam constantes geométricas. Como o método pode ser usado para adulterar o conteúdo de imagens e, potenci- almente, para atividade ilegais, conforme colocado por Piva (2013), torna-se necessário o desenvolvimento de ferramentas capazes de detectar a veracidade de uma imagem. Yin et al. (2015) desenvolveu um trabalho utilizando Local Binary Pattern (LBP) do qual foram extraídos 24 parâmetros sendo que 18 foram similares aos propostos por RYU, LEE e LEE (2014) e 6 foram definidos com base na aplicação do half seam. Tais parâmetros foram utilizados em uma Support Vector Machine (SVM), que consiste em um conjunto de métodos para analise de dados e reconhecimento de padrões por meio do aprendizado supervisionado de máquina. Ye e Shi (2017) propôs o uso de um modelo estatístico avançado para realizar a detecção da aplicação do seam carving em imagens não comprimidas em escala de cinza utilizando uma SVM para classificação a partir de características extraídas, princi- palmente, pelo uso de Local Derivative Pattern (LDP), que foi comparada ao LBP por Zhang et al. (2010). Cieslak, Costa e Papa (2018) utilizou do LBP, como Yin et al. (2015), associado a uma Convolutional Neural Network (CNN). Em sua publicação é colocado que não foi encontrado nenhum método que havia utilizado uma CNN para determinar se ocorreu alguma adulteração em uma imagem por meio de Seam Carving. 1.1 Problema Como imagens podem ser facilmente submetidas como material probatório para diversos fins como em tribunais de justiça, ao considerar a facilidade da aplicação do seam carving seja para remoção de evidências ou inclusão de informações visuais, faz-se necessário uma forma de validar a veracidade da imagem e qualidade do material como prova. Afim de verificar a credibilidade de uma imagem existem duas classes de aborda- gens que são utilizadas: a) abordagem ativa como uso de assinaturas digitais criptográficas; b) abordagem passiva que consiste no uso de técnicas forenses. Capítulo 1. Introdução 12 Os métodos definidos no inicio deste capitulo pertencem à categoria de abordagem passiva. Todavia, devido às formas de execução distintas das pesquisas, não possuem uma forma direta de comparação de eficiência pois as características das imagens utilizadas distinguem, por exemplo, em resolução espacial e padrão de cores. Considerando essa situação e que buscando evitar a utilização de imagens editadas para fins de comprovação em diversos aspectos, principalmente em foro legal, aplicar o melhor método de verificação se faz adequado, e, para tanto, são necessárias informações sobre eficiência dos métodos existentes. Torna-se adequado o fornecimento de um meio de comparação para os métodos que é um dos objetivos deste trabalho. Fornecer esse meio de comparação é o que foi buscado por meio deste trabalho sendo que para tal comparação foi utilizada a taxa de acertos, falsos positivos e falsos negativos dos métodos. 1.2 Objetivo Geral Determinar a eficácia quanto a taxa de acertos, falsos positivos e falsos negativos dos métodos atualmente propostos para detecção da aplicação de seam carving em um mesmo conjunto de dados. 1.3 Objetivos Específicos a) implementar os métodos mencionados no inicio deste capitulo; b) determinar uma base comum de dados para aplicação das implementações; c) analisar os resultados das aplicações; d) avaliar os métodos com os resultados obtidos. 13 2 Definições 2.1 Seam Carving É uma técnica proposta por Avidan e Shamir (2007) para o redimensionamento de imagens de forma com que o conteúdo seja preservado utilizando de seams ótimos para isso. Para definir a importância visual é utilizado uma função de energia para os pixels da imagem em que o valor obtido representa a importância visual. As regiões de baixa energia são as manipuladas com a inserção ou remoção de seams de forma a alterar a proporção e tamanho da imagem em que foi aplicada com a conservação das informações tidas como importantes por serem regiões com menor im- portância. Ou seja, não são criados artefatos visuais pelo redimensionamento da imagem. 2.1.1 Seams Para as definições foi utilizada a notação descrita na Tabela 1. Tabela 1 – Notações utilizadas para definição de Seams Notação Definições s Conjunto de pixels que forma o seam e(x) Função de energia aplicada ao pixel x E(x) Função de energia aplicada ao seam s I(i,j) Intensidade do pixel na linha i e coluna j da imagem I Fonte: Elaborado pelo autor Seams são caminhos de pixels conexos podendo ser horizontal ou vertical. No primeiro caso, consiste em um caminho da esquerda para direita sendo que para cada coluna somente 1 pixel será atribuido para s que neste caso terá a notação 𝑠𝑦. Para o caso vertical, a situação é análoga porém o caminho é do topo até a base da imagem, a restrição é para linha e a notação é 𝑠𝑥. É definido no método de detecção proposto por Yin et al. (2015) o half seam que consiste na aplicação parcial de um seam, mais precisamente, é limitado pela metade da dimensão da imagem em que está sendo trabalhada. Utilizando-os é possível remover ou adicionar pedaços à imagem de forma menos restritiva que com a manipulação simplesmente das colunas ou linhas da imagem. Capítulo 2. Definições 14 A energia de um seam é definida pela equação: 𝐸(𝑠) = ∑︁ 𝑒(𝑝), 𝑝 ∈ 𝑠 (2.1) Sendo que e(p) pode ser definido de diversas formas e, dentre as testadas por Avidan e Shamir (2007), as que apresentaram melhor desempenho foram duas: a) 𝑒𝐻𝑜𝐺: Uma aproximação da magnitude do gradiente; b) 𝑒1: Combinação de 𝑒1 com histogramas de gradientes. No caso de 𝑒1, a definição é a seguinte: 𝑒𝐻𝑜𝐺(𝑝) = ⃒⃒⃒⃒ ⃒ 𝜕𝑝 𝜕𝑥 ⃒⃒⃒⃒ ⃒ + ⃒⃒⃒⃒ ⃒𝜕𝑝 𝜕𝑦 ⃒⃒⃒⃒ ⃒ (2.2) Enquanto no de 𝑒𝐻𝑜𝐺 é: 𝑒1(𝑝) = ⃒⃒⃒ 𝜕𝑝 𝜕𝑥 ⃒⃒⃒ + ⃒⃒⃒ 𝜕𝑝 𝜕𝑦 ⃒⃒⃒ 𝑚𝑎𝑥(𝐻𝑜𝐺(𝐼(𝑥, 𝑦))) (2.3) O seam ótimo é determinado como 𝑠* = 𝑚𝑖𝑛(𝐸(𝑠)) 2.1.2 Exemplos A fim de evidenciar quão bem funciona a técnica para remoção de conteúdo da imagem, o que não é o objetivo principal da mesma, podem ser visualizadas as figuras 1 e 2. A figura 1 é a imagem não editada e a figura 2 é a mesma imagem com a remoção de um sapato. Figura 1 – Imagem de sapatos Fonte: Avidan e Shamir (2007) Capítulo 2. Definições 15 Figura 2 – Figura 1 com remoção de um sapato Fonte: Avidan e Shamir (2007) Para facilitar o entendimento do que foi definido na seção 2.1.1 a Figura 3 re- presenta a escolha de um seam 𝑠𝑥 representado pela linha vermelha e um half seam representado pela linha azul. Figura 3 – Imagem de uma arvore de cerejeira com seam e half seam representado Fonte: Yin et al. (2015) 2.2 Gradiente em imagens O operador gradiente resulta em um vetor de duas componentes que são definidas como segue: 𝜕𝑓 𝜕𝑥 = lim ℎ→0 𝑓(𝑥 + ℎ, 𝑦) − 𝑓(𝑥, 𝑦) ℎ (2.4) 𝜕𝑓 𝜕𝑦 = lim ℎ→0 𝑓(𝑥, 𝑦 + ℎ) − 𝑓(𝑥, 𝑦) ℎ (2.5) Capítulo 2. Definições 16 Todavia em uma imagem não é possível que ℎ → 0 pois a menor distância entre os pontos, que são os pixels da imagem, é 1. Assim sendo, é necessário o uso de aproximações para obter o gradiente de uma imagem e existem diversas propostas de como os operadores de Laplace, Roberts, Prewitt, Kirsch ou de Sobel, os quais são explicados por Sonka, Hlavac e Boyle (2014). Vale mencionar que a aproximação mais intuitiva seria tomar ℎ → 0 como ℎ = 1 por ser a menor distância entre os pixels mas não foi adotada, pois, existem alguns filtros que cumprem o objetivo, como evidenciado pelos operadores acima mencionados e com facilidade de encontrar referência como Facon (2006), Vairalkar e Nimbhorkar (2012) e Sonka, Hlavac e Boyle (2014). Considerando que o gradiente, que foi utilizado neste trabalho, é composto pelas derivadas de primeira ordem evidenciadas pelas funções 2.4 e 2.5, nem todas essas apro- ximações são adequadas e que, durante o desenvolvimento dos algoritmos deste trabalho para o método a função de energia definida pela função 2.2, foi utilizado a aproximação obtida pela aplicação do operador de Sobel que já possuía uma implementação no pacote scikit-image de Python, não será feito o detalhamento de todos os operadores. 2.2.1 Filtro Sobel Para aplicação deste filtro são utilizadas três matrizes: ℎ1 = ⎡⎢⎢⎢⎣ 1 2 1 0 0 0 −1 −2 −1 ⎤⎥⎥⎥⎦ (2.6) ℎ2 = ⎡⎢⎢⎢⎣ 0 1 2 −1 0 1 −2 −1 0 ⎤⎥⎥⎥⎦ (2.7) ℎ3 = ⎡⎢⎢⎢⎣ −1 0 1 −2 0 2 −1 0 1 ⎤⎥⎥⎥⎦ (2.8) Como é necessário a aproximação das derivadas em x e y, somente serão utilizadas as matrizes representadas por 2.6 e 2.8 para obter a aproximação, respectivamente, de 𝜕𝑓 𝜕𝑦 e 𝜕𝑓 𝜕𝑥 conforme definido em Sobel (1968). 2.3 Local Binary Pattern Para as definições foi utilizada a notação descrita na Tabela 2. Capítulo 2. Definições 17 Tabela 2 – Notações utilizadas para definição de LBP Notação Definições 𝑝𝑖 Pixel i de uma vizinhança 𝑝𝑐 Pixel central R Raio utilizado na vizinhança P Quantidade de pixels utilizado da vizinhança Fonte: Elaborado pelo autor Consiste em um operador para análise local de textura de imagens em escala de cinza que, segundo Zhang et al. (2010), possui um excelente desempenho tanto em relação a velocidade e quanto a classificação. Para obtenção do valor de um pixel pela aplicação do LBP são utilizados os P pixels de sua vizinhança de raio R e os valores são concatenados gerando o valor desejado. Cada um dos valores são gerados pela seguinte função: 𝑓(𝑝𝑣, 𝑝𝑐) = ⎧⎨⎩0, se 𝑝𝑣 − 𝑝𝑐 ≥ 0 1, caso contrário (2.9) A partir disso é possível chegar que para cada um dos pixels central o valor de seu LBP é definido por: 𝐿𝐵𝑃𝑃,𝑅 = 𝑃 −1∑︁ 𝑖=0 𝑓(𝑝𝑖, 𝑝𝑐)2𝑖 (2.10) Figura 4 – Ilustrando o conceito de LBP com 𝑅 = 1 e 𝑃 = 8 Fonte: Yin et al. (2015) 2.4 Local Derivative Pattern Para as definições foi utilizada a notação descrita na tabela 3. Capítulo 2. Definições 18 Tabela 3 – Notações utilizadas para definição de LDP Notação Definições 𝐼(𝑝) Intensidade do pixel p 𝑝𝛼 Posição no eixo 𝛼 do pixel p 𝐿𝐷𝑃 𝑖 𝛼(𝑝) LDP de ordem i na direção 𝛼 do pixel p 𝐿𝐷𝑃 ′ 𝛼(𝑝) LDP de primeira ordem na direção 𝛼 do pixel p 𝐿𝐷𝑃 ′′ 𝛼 (𝑝) LDP de segunda ordem na direção 𝛼 do pixel p D Distância adotada pela vizinhança de um pixel central N Quantidade de pixels utilizados de uma vizinhança Fonte: Elaborado pelo autor LDP é um descritor de alta ordem derivativa de textura local e é um conceito mais completo que abrange o da seção 2.3, pois, o LBP pode ser considerado como o descritor de primeira ordem não direcional do LDP. Com sua utilização é possível extrair mais informações da perspectiva derivativa bem como a sensibilidade para alterações locais aumenta. Além disso, a partir da ter- ceira ordem, como o método fica muito sensível a ruido da imagem, sua utilização não é adequada para detecção de edição que é o objetivo tratado por este trabalho e isso é explicitado por Ye e Shi (2017) na publicação em que divulgou o seu método. As derivadas direcionais utilizadas pelo LDP podem ser em quatro direções: a) 𝛼 = 0∘ b) 𝛼 = 45∘ c) 𝛼 = 90∘ d) 𝛼 = 135∘ Porém, como os seams são horizontais ou verticais, só as direções 𝛼 = 0∘ e 𝛼 = 90∘ são utilizadas pelo método de detecção. 2.4.1 Vizinhança A escolha da vizinhança no método pode ser circular ou retangular. No primeiro caso, é necessário realizar a interpolação bilinear de pontos que não estejam no centro do pixel, o que reduz a perda de informação dos pixels da vizinhança pois mais são utilizados. A interpolação bilinear para encontrar a intensidade do pixel p localizado entre os 𝑍9, 𝑍10, 𝑍24 e 𝑍1 é obtida pela aplicação da equação 2.11. Vale mencionar que 𝑍9𝑥 e 𝑍24𝑥 Capítulo 2. Definições 19 estão sendo denotadas por 𝑥1, 𝑍1𝑥 e 𝑍10𝑥 por 𝑥2, 𝑍9𝑦 e 𝑍10𝑦 por 𝑦2 e 𝑍1𝑦 e 𝑍24𝑦 por 𝑦1. 𝐼(𝑝) = 𝐼(𝑍24) (𝑥2 − 𝑥1)(𝑦2 − 𝑦1) (𝑥2 − 𝑝𝑥)(𝑦2 − 𝑝𝑦)+ 𝐼(𝑍1) (𝑥2 − 𝑥1)(𝑦2 − 𝑦1) (𝑝𝑥 − 𝑥1)(𝑦2 − 𝑝𝑦)+ 𝐼(𝑍9) (𝑥2 − 𝑥1)(𝑦2 − 𝑦1) (𝑥2 − 𝑝𝑥)(𝑝𝑦 − 𝑦1)+ 𝐼(𝑍10) (𝑥2 − 𝑥1)(𝑦2 − 𝑦1) (𝑝𝑥 − 𝑥1)(𝑝𝑦 − 𝑦1) (2.11) Vale mencionar que o denominador (𝑥2 − 𝑥1)(𝑦2 − 𝑦1), para o caso desenvolvido, poderia ser omitido pois a distância será sempre 1. Na Figura 5 são representadas duas vizinhanças retangulares indicadas por (a) e (b) e, também, duas vizinhas circulares cujas indicações são (c) e (d). Figura 5 – Representação de vizinhança circular e retangular Fonte: Ye e Shi (2017) Figura 6 – Representação de vizinhança 5x5 em uma imagem com o pixel central 𝑍0 Fonte: Ye e Shi (2017) Capítulo 2. Definições 20 2.4.2 Derivada de primeira ordem A derivada de primeira ordem utilizada por este método é obtida pelas seguintes aplicações, utilizando a notação da figura 6 𝑙 ′ 𝛼=0∘(𝑍0) = 𝐼(𝑍0) − 𝐼(𝑍4) (2.12) 𝑙 ′ 𝛼=45∘(𝑍0) = 𝐼(𝑍0) − 𝐼(𝑍3) (2.13) 𝑙 ′ 𝛼=90∘(𝑍0) = 𝐼(𝑍0) − 𝐼(𝑍2) (2.14) 𝑙 ′ 𝛼=135∘(𝑍0) = 𝐼(𝑍0) − 𝐼(𝑍1) (2.15) 2.4.3 LDP de segunda ordem Para a obtenção do LDP de segunda ordem é utilizada a concatenação de bits obtidos pela aplicação do LDP de primeira ordem com seu valor delimitado entre 1 e 0 pela função de codificação binária 2.16. 𝑓(𝑙′ 𝛼(𝑍0), 𝑙 ′ 𝛼(𝑍𝑖)) = ⎧⎨⎩0, se 𝑙 ′ 𝛼(𝑍0).𝑙 ′ 𝛼(𝑍𝑖)) > 0 1, caso contrário (2.16) Sendo que o LDP de segunda ordem na direção 𝛼 é obtido da seguinte forma: 𝐿𝐷𝑃 2 𝛼 = {𝑓(𝑙′ 𝛼(𝑍0), 𝑙 ′ 𝛼(𝑍1)), ..., 𝑓(𝑙′ 𝛼(𝑍0), 𝑙 ′ 𝛼(𝑍𝑖))} (2.17) Conforme pode ser observado pela formula 2.17, cada bit descreve a relação entre, pelo menos, 3 pixels. Por exemplo, no caso de 𝑓(𝑙′ 𝛼=90(𝑍0), 𝑙 ′ 𝛼=90(𝑍1)) os pixels 𝑍0, 𝑍2, 𝑍1 e 𝑍10 são envolvidos e 𝑓(𝑙′ 𝛼=90(𝑍0), 𝑙 ′ 𝛼=90(𝑍2)) envolve 𝑍0, 𝑍2 e 𝑍11. 2.4.4 LDP de ordem n-ésima Para o cálculo do LDP de ordem 𝑛 é realizado o cálculo da ordem 𝑛 − 1 na mesma direção. Como pode ser observado no caso de segunda ordem descrito na subseção 2.4.3 utiliza da derivada de primeira ordem descrita em 2.4.2. Assim sendo, para o cálculo de terceira ordem usaria a derivada de segunda que, por sua vez, usa de primeira. Isso vale, analogamente, para qualquer ordem superior. Capítulo 2. Definições 21 2.5 Support Vector Machine Consiste em um método de aprendizagem de máquina supervisionado podendo ser utilizado para classificação ou analise de regressão. Para os métodos que a utilizam neste trabalho, é utilizado para classificação em imagens editadas ou originais. Nesse caso, a SVM encontra um hiperplano divisor por meio do conjunto de trei- namento. Utilizando a maior distância marginal dos pontos que seja possível. A partir desse hiperplano, para novos dados, a classificação é obtida pela região em que ele ficar associado. Para classificação não linear, pode ser utilizada uma função kernel que leva o conjunto de dados para uma dimensão de ordem superior em que seja possível fazer uma separação linear. Figura 7 – Exemplo hiperplano obtido por uma SVM com a aplicação de uma função kernel 𝜑 Fonte: Elaborado pelo autor 2.6 Convolutional Neural Networks Podem ser vistas como uma representação de uma classe maior de modelos ba- seados na arquitetura de Hubel e Wiesel, os quais realizaram um estudo sobre o córtex primário de gatos em 1962. Nesse estudo foi identificado, basicamente, dois tipos de célu- las: a) Células simples: Possuem uma tarefa análoga à etapa de filtragem por banco de máscaras b) Células complexas: Executam tarefa semelhante à etapa de amostragem das CNNs O primeiro modelo que simulou uma Rede Neural por Convolução em computa- dor foi o amplamente conhecido “Neocognitron (FUKUSHIMA; MIYAKE, 1982)”, o qual aplicava um algoritmo de treinamento não supervisionado na etapa de filtragem por banco de máscaras, bem como um algoritmo de treinamento supervisionado na última camada da rede. Posteriormente, LeCun et al. (LECUN et al., 1989; LECUN et al., 1990) simpli- Capítulo 2. Definições 22 ficaram essa arquitetura propondo a utilização do algoritmo de retropropagação para o treinamento da rede como um todo de maneira supervisionada. Com o decorrer do tempo, várias aplicações que fizeram uso de CNNs foram surgindo. Essencialmente, uma CNN consiste em uma sequência de três camadas de proces- samento de imagem. A partir de uma imagem de entrada, é extraído uma representação de alto nível da mesma, chamada de imagem multibandas, cujos atributos dos pixels são concatenados em um vetor de características para posterior aplicação de técnicas de re- conhecimento de padrões. A Figura 8 apresenta a arquitetura de uma Rede Neural por Convolução. Figura 8 – Arquitetura de uma Rede Neural por Convolução típica. Fonte: Imagem cedida pelos autores de Cieslak, Costa e Papa (2018) Em cada camada da CNN são executadas três operações, sendo a primeira delas um convolução com um banco de filtros, a segunda uma amostragem e a terceira uma etapa de normalização. Conforme pode ser observado na Figura 8, existe ainda a possibilidade de ser realizada uma operação de normalização no início de todo o processo. 23 3 Método de Pesquisa Para a realização dos objetivos propostos foi cumprido sequencialmente os objeti- vos específicos da Seção 1.3. A implementação dos métodos propostos utilizando LBP e SVM (YIN et al., 2015), modelo estatístico associado a uma SVM (YE; SHI, 2017) e LBP associado a uma CNN Cieslak, Costa e Papa (2018) foi realizada utilizando as definições das publicações refe- renciadas e que foram mencionadas no Capítulo 1. Valendo ressaltar que algumas informações não foram disponibilizadas nessas pu- blicações, por exemplo, na publicação do Yin et al. (2015) em relação a derivada direcional na imagem, não foi explicitado qual método de derivação foi utilizado e, neste trabalho, o filtro Scharr foi utilizado. Enquanto para o que foi especificado nas publicações, como o uso de SVM, a especificação foi mantida no desenvolvimento deste trabalho. Com a finalidade de testar as implementação e fazer a análise estatística dos resul- tados, a base de dados disponibilizada pela Sam Houston State University, foi utilizada por todas as implementações realizadas sendo 20% das imagens selecionadas para valida- ção e 80% para o treinamentos dos métodos de classificação. Quanto a análise da eficácia das técnicas implementadas foi realizada sob o aspecto de precisão dos resultados obtidos pela obtenção das taxas de falsos positivos e acerto. Inicialmente foi considerado realizar a análise do tempo de execução, também, todavia durante o desenvolvimento algumas bibliotecas utilizavam Cython que consiste em uma linguagem compilada que gera pacotes de extensão para Python. Tal situação gerava um problema para comparação pois o tempo de execução para os códigos interpretados, como o caso de Python, é muito maior que os compilados mesmo que o tempo de execução fosse mensurado em um mesmo dispositivo para todas as técnicas. Após efetuada a análise, os métodos foram classificados de acordo com sua eficácia para o conjunto de dados aplicado de acordo com os resultados obtidos. 3.1 Base de Dados A base de dados utilizada possui 5150 imagens em 2 dimensões espaciais que são: 1234 x 1858 e 1858 x 1234. Além disso, para cada imagem, está disponível na base a versão com seam carving aplicado e a versão original. As figuras abaixo são algumas imagens da base que foram utilizadas durante o treinamento e validação das SVM e CNN. As três primeiras sofreram aplicação de seam Capítulo 3. Método de Pesquisa 24 carving e as seguintes são as versões originais dessas imagens Figura 9 – Imagem com seam carving aplicado. Fonte: Base de dados cedida pela Sam Houston State University Figura 10 – Imagem com seam carving aplicado. Fonte: Base de dados cedida pela Sam Houston State University Capítulo 3. Método de Pesquisa 25 Figura 11 – Imagem com seam carving aplicado. Fonte: Base de dados cedida pela Sam Houston State University Figura 12 – Versão original da figura 9 Fonte: Base de dados cedida pela Sam Houston State University Capítulo 3. Método de Pesquisa 26 Figura 13 – Versão original da figura 10 Fonte: Base de dados cedida pela Sam Houston State University Figura 14 – Versão original da figura 11 Fonte: Base de dados cedida pela Sam Houston State University 27 4 Resultados Para o método do Yin et al. (2015) obteve-se 51.8% de maior acurácia, 23% de falsos negativos e 25.2% de falsos positivos, o detalhamento desses dados pode se visua- lizado na tabela 4 e imagem 15. Sendo que a imagem 15 exibe o detalhamento da SVM linear que obteve o melhor resultado. Vale mencionar que para as Figuras 15 e 16 as cores foram utilizadas para intro- duzir uma interpretação visualmente rápida, onde os campos vermelhos representam falso positivo ou falso negativo, dependendo da coluna de acordo com a classe real, denotada do lado esquerdo, e a classificada pela SVM, disponível abaixo. Tabela 4 – Acurácia para o método do Yin et al. (2015) Kernel Acurácia (%) Linear 51.8 Quadrático 43.5 Cúbico 38.1 Gaussiano com escala 1/4 12.5 Gaussiano com escala 1 39.7 Gaussiano com escala 4 47.5 Fonte: Elaborado pelo autor Figura 15 – Taxas de acerto e erros da SVM linear para o método do Yin et al. (2015) Fonte: Elaborado pelo autor Enquanto para o método do Ye e Shi (2017) os resultados foram 92.5% de maior Capítulo 4. Resultados 28 acurácia, 3% de falsos negativos e 4.5% de falsos positivos e, seguindo a mesma lógica do caso anterior, podem ser visualizados na Tabela 5 e Figura 16 o detalhamento para o kernel quadrático. Tabela 5 – Acurácia para o método do Ye e Shi (2017) Kernel Acurácia (%) Linear 88.5 Quadrático 92.5 Cúbico 82.5 Gaussiano com escala 1/4 22.5 Gaussiano com escala 1 61.5 Gaussiano com escala 4 56.0 Fonte: Elaborado pelo autor Figura 16 – Taxas de acerto e erros da SVM quadrática para o método do Ye e Shi (2017) Fonte: Elaborado pelo autor Por fim, para o método Cieslak, Costa e Papa (2018) foi obtida uma acurácia de 79.46%, 11.51% de falsos positivos e 9,03% de falso negativos. Em resumo, considerando as melhores eficiências, os resultados obtidos são os representados pela figura 17 Capítulo 4. Resultados 29 Figura 17 – Quadro resumo de eficiência dos métodos implementados Fonte: Elaborado pelo autor 30 5 Conclusão Dentre os métodos testados, o que apresentou maior desempenho na mesma base foi o que utilizava LDP, método do Ye e Shi (2017) para extração de características. Tal método superou em 13,04% o método Cieslak, Costa e Papa (2018) que, por sua vez, superou em 27.66% o método do Yin et al. (2015). Como o método Cieslak, Costa e Papa (2018) usa a mesma técnica, no caso LBP, para extração de características que o Yin et al. (2015), pode ser que criando um método variante que utilize LDP como o Ye e Shi (2017) gere ganhos significativos. A acurácia do método Yin et al. (2015) ficou abaixo do esperado mas, como na publicação original os resultados foram superiores, parece ser adequado executar em mais bases de dados para ter uma perspectiva melhor da situação. Além disso, como existem diversos outros classificadores além da SVM que foi majoritariamente utilizada e o uso de CNN teve uma ótima eficiência para um conjunto de características que a SVM não obteve tão grau de acerto, também é possível considerar a classificação por meio de outros classificadores. 5.1 Trabalhos Futuros Pelo exposto no início deste capítulo, os seguintes itens podem ser executados em trabalhos futuros: a) Criação de um método misto utilizando CNN e LDP b) Execução dos métodos em mais bases de dados c) Utilização de novos classificadores para os métodos e comparação dos resultados 31 Referências AVIDAN, S.; SHAMIR, A. Seam carving for content-aware image resizing. ACM Trans. Graph., ACM, New York, NY, USA, v. 26, n. 3, jul. 2007. ISSN 0730-0301. CIESLAK, L. F. da S.; COSTA, K.; PAPA, J. Seam carving detection using convolutional neural networks. 2018. FACON, J. Técnicas de processamento digital de imagens aplicadas à área da saúde. XIII Escola Regional de Informática da SBC-Paraná, 2006. FUKUSHIMA, K.; MIYAKE, S. Neocognitron: A new algorithm for pattern recognition tolerant of deformations and shifts in position. Pattern Recognition, v. 15, n. 6, p. 455 – 469, 1982. ISSN 0031-3203. LECUN, Y.; BOSER, B.; DENKER, J.; HENDERSON, D.; HOWARD, R.; HUBBARD, W.; JACKEL, L. Handwritten digit recognition with a back-propagation network. In: MORGAN KAUFMANN PUBLISHERS. Advances in neural information processing systems 2, NIPS 1989. [S.l.], 1990. p. 396–404. LECUN, Y.; BOSER, B.; DENKER, J. S.; HENDERSON, D.; HOWARD, R. E.; HUBBARD, W.; JACKEL, L. D. Backpropagation applied to handwritten zip code recognition. Neural computation, v. 1, n. 4, p. 541–551, 1989. PIVA, A. An overview on image forensics. v. 2013, jan. 2013. RYU, S.-J.; LEE, H.-Y.; LEE, H.-K. Detecting trace of seam carving for forensic analysis. IEICE Transactions on Information and Systems, E97.D, n. 5, p. 1304–1311, 2014. SOBEL, I. History and definition of the so-called"sobel operator", more appropriately named the sobel-feldman operator. Sobel, I., Feldman, G.,"A 3x3 Isotropic Gradient Operator for Image Processing", presented at the Stanford Artificial Intelligence Project (SAIL) in, v. 2015, 1968. SONKA, M.; HLAVAC, V.; BOYLE, R. Image processing, analysis, and machine vision. [S.l.]: Cengage Learning, 2014. VAIRALKAR, M. K.; NIMBHORKAR, S. Edge detection of images using sobel operator. International Journal of Emerging Technology and Advanced Engineering, Citeseer, v. 2, n. 1, p. 291–293, 2012. YE, J.; SHI, Y.-Q. An effective method to detect seam carving. Journal of Information Security and Applications, v. 35, p. 13 – 22, 2017. ISSN 2214-2126. YIN, T.; YANG, G.; LI, L.; ZHANG, D.; SUN, X. Detecting seam carving based image resizing using local binary patterns. Computers Security, v. 55, p. 130 – 141, 2015. ISSN 0167-4048. ZHANG, B.; GAO, Y.; ZHAO, S.; LIU, J. Local derivative pattern versus local binary pattern: Face recognition with high-order local pattern descriptor. IEEE Transactions on Image Processing, v. 19, n. 2, p. 533–544, Feb 2010. ISSN 1057-7149. Folha de rosto Folha de aprovação Resumo Abstract Lista de ilustrações Lista de tabelas Lista de abreviaturas e siglas Lista de símbolos Sumário Introdução Problema Objetivo Geral Objetivos Específicos Definições Seam Carving Seams Exemplos Gradiente em imagens Filtro Sobel Local Binary Pattern Local Derivative Pattern Vizinhança Derivada de primeira ordem LDP de segunda ordem LDP de ordem n-ésima Support Vector Machine Convolutional Neural Networks Método de Pesquisa Base de Dados Resultados Conclusão Trabalhos Futuros Referências