\documentclass[a4paper]{article}
\usepackage{listings}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage[colorlinks, urlcolor=blue]{hyperref}

\renewcommand{\familydefault}{\sfdefault}
\title{Relatório de trabalho prático \\
Processamento digital de imagens \\
Algoritmo Roberts para detecção de bordas}

\author{João Paulo Pizani Flor \\
Mauricio Oliveira Haensch}

\date{\today}

\lstset{
    tabsize=2,
    basicstyle=\footnotesize,
}

\begin{document}
    \maketitle
    \thispagestyle{empty}
    \pagebreak

    \section{Introdução}
        \paragraph{}
        Para o módulo de processamento digital de imagens da disciplina, o primeiro trabalho consiste
        na implementação de um algoritmo de detecção de bordas. Cada uma das equipes na qual a turma
        está dividida deve implementar um dos algoritmos pedidos, e os trabalhos devem seguir um padrão
        de formato para entrada e saída de forma a possibilitar a interoperabilidade entre os algoritmos
        de todas as equipes. O algoritmo a ser implementado por nossa equipe é o detector de Roberts.
        Seguem abaixo alguns requisitos pedidos para este trabalho:

        \begin{itemize}
            \item O primeiro parâmetro deve ser o nome da arquivo de entrada e o último parâmetro
                será o nome do arquivo de saída
            \item Atributos de entrada devem devem ser informados após o nome do arquivo de entrada
            \item Utilizar OPENCV de preferência, para diminuir o número de dependências
            \item O formato do arquivo de saída deve ser um formato de imagem (PNG, JPG, BMP, etc.)
        \end{itemize}

    \pagebreak
    \section{Ferramentas utilizadas}
        \paragraph{}
        Tanto a linguagem quanto bibliotecas utilizadas para implementação eram de livre
        escolha dos alunos. As ferramentas escolhidas para a implementação deste trabalho foram:

        \begin{description}
            \item[Linguagem de programação - Haskell:] Aplicações com grande necessidade de processamento
                (\emph{compute-intensive}) e (relativamente) pouca interação com o usuário se adequam
                perfeitamente ao paradigma de \emph{programação funcional}. A linguagem Haskell
                \footnote{\url{http://www.haskell.org}} é uma linguagem puramente funcional, com uma
                grande comunidade de usuários e bibliotecas para as mais diversas áreas de aplicação,
                incluindo processamento de imagens. Seu compilador gera código bastante otimizado, e
                código escrito em Haskell pode ser facilmente (automaticamente) paralelizado para a
                execução em multicores.
            \item[Biblioteca - Repa:] A biblioteca
                Repa\footnote{\url{http://http://hackage.haskell.org/package/repa}} (Regular,
                high-performance shape-polymorfic arrays) fornece a abstração de \emph{arrays paralelos}
                na linguagem Haskell, fazendo com que seja fácil expressar os mais diversos tipos de
                algoritmos sobre arrays multidimensionais em alto nível de abstração. Uma das operações
                disponíveis na biblioteca Repa é a \emph{convolução}, que é a operação central em nosso
                algoritmo de detecção de bordas. Os algoritmos escritos usando a Repa são automaticamente
                paralelos e podem ser executados aproveitando-se de todos os cores em um processador
                \emph{multicore}.
            \item[Sistema de compilação - Cabal:] O Cabal\footnote{\url{http://www.haskell.org/cabal}} é
                o sistema de compilação e empacotamento para programas e bibliotecas Haskell. Neste
                trabalho, especificamente, o Cabal nos permitiu instalar facilmente todas as bibliotecas
                necessárias (Repa e suas dependências). Além disso, com o Cabal pudemos facilmente gerar
                um executável \emph{ligado estaticamente} como resultado da compilação, fazendo com que
                nenhuma dependência seja necessária para executar nosso trabalho em máquinas Linux 32-bit.
        \end{description}

        \paragraph{}
        O trabalho foi desenvolvido no ambiente Linux/Ubuntu e para executá-lo é necessário apenas
        executar o binário enviado junto ao relatório, conforme o exemplo:
        \begin{verbatim}
        ./roberts <imagem_entrada.bmp> <imagem_saida.bmp>
        \end{verbatim}

    \pagebreak
    \section{Implementação}
        \subsection{Algoritmo de Roberts}
            \paragraph{}
            O algoritmo de Roberts é um dos mais simples para detecção de bordas, utilizando duas
            matrizes 2x2 para fazer a convolução da imagem original:
            \[
                \begin{bmatrix} 
                    +1 & 0 \\
                    0 & -1\\
                \end{bmatrix}
                \quad \mbox{e} \quad 
                \begin{bmatrix} 
                    0  & +1 \\
                    -1 & 0  \\
                \end{bmatrix}
            \]
            O código Haskell abaixo define e utiliza os dois \emph{Stencils} de convolução, robertsX
            e robertxY. A função ``mapStencil2'' aplica o stencil sobre um array, enquanto o parâmetro
            ``BoundClamp'' define a condição de borda (nesse caso, ignorar os elementos de borda):
            \lstinputlisting[language=Haskell]{stencils-relatorio.hs}

            \paragraph{}
            O gradiente pode ser então definido para um pixel (x,y) da imagem como o resultado da
            função abaixo, onde $G_x$ é o resultado obtido na convolução com a primeira matriz e
            $G_y$ o resultado obtido na convolução com a segunda matriz para um pixel (x,y):
            \[
                \nabla I(x,y) = G(x,y) = \sqrt{ G_x^2 + G_y^2 }
            \]
            O código Haskell abaixo, parte do arquivo Main.hs, enviado junto ao relatório, define o
            array resultante da detecção de bordas a partir da aplicação (ponto-a-ponto) da função
            ``magnitude'' no par de arrays resultantes da convolução no eixo X e Y:
            \lstinputlisting[language=Haskell]{magnitude-relatorio.hs}            

            \paragraph{}
            Já a direção do gradiente é definida pela função a seguir:
            \[
                \Theta(x,y) = \arctan{\left(\frac{G_y(x,y)}{G_x(x,y)}\right)}
            \]

        \subsection{Alguns resultados}
            \paragraph{}
            Além do arquivo binário executável, o código desenvolvido em Haskell também foi enviado
            junto relatório e se encontra nos arquivos \textit{src/Main.hs} e \textit{src/Stencils.hs}.
            A seguir serão demonstrados alguns resultados obtidos com a execução de nossa implementação:

            \paragraph{}
            A primeira figura utilizada como demonstração é uma imagem de uma válvula (original em
            \ref{fig:valve} e resultante em \ref{fig:valve_edges}). Para este exemplo, as bordas
            detectadas estão razoavelmente bem definidas. 

            \begin{figure}[h!]
                \begin{center}
                    \includegraphics[width=0.7\textwidth]{imgs/valve.png}
                \end{center}
                \caption{Imagem original.}
                \label{fig:valve}
            \end{figure}

            \begin{figure}[h!]
                \begin{center}
                    \includegraphics[width=0.7\textwidth]{imgs/valve_edges.png}
                \end{center}
                \caption{Imagem gerada com a detecção de bordas.}
                \label{fig:valve_edges}
            \end{figure}

            \paragraph{}
            A seguir um outro exemplo de imagem (figura original em \ref{fig:forest} e resultante
            em \ref{fig:forest_edges}). Para este exemplo pode ser observado que o ruído é maior
            e as bordas não ficam muito bem definidas, característica presente no algoritmo de Roberts
            por sua simplicidade.

            \begin{figure}[h!]
                \begin{center}
                    \includegraphics[width=0.7\textwidth]{imgs/forest.png}
                \end{center}
                \caption{Imagem original da floresta.}
                \label{fig:forest}
            \end{figure}

            \begin{figure}[h!]
                \begin{center}
                    \includegraphics[width=0.7\textwidth]{imgs/forest_edges.png}
                \end{center}
                \caption{Detecção de bordas aplicada à imagem da floresta.}
                \label{fig:forest_edges}
            \end{figure}

    \pagebreak
    \section{Referências}
        \begin{itemize}
            \item The Haskell Programming Language - \url{http://www.haskell.org/}
            \item Numeric Haskell: A Repa Tutorial -
                \url{http://www.haskell.org/haskellwiki/Numeric\_Haskell:\_A\_Repa\_Tutorial}
            \item Roberts Edge Detection - \url{http://en.wikipedia.org/wiki/Roberts\_Cross}
            \item How to generate a completely static binary of your Haskell program -
                \url{http://www.cs.virginia.edu/~wh5a/blog/SomeGHCnotesformyself.html}
        \end{itemize}

\end{document}
