Trabalho de formatura Marcos Farah Nagato

Esta é a monografia do meu trabalho de formatura supervisionado (MAC-499) - 2002 pelo Bacharelado em Ciência da Computação do IME-USP.

Ele foi realizado em dupla com Alfredo Roberto Júnior.
Supervisor - Professor Doutor Flávio Soares Corrêa da Silva

Projeto afinador eletrônico

1) Parte técnica

    Definição / especificação do projeto;
    Forma de organização da dupla e atribuição de responsabilidades;
    Estimativa inicial de prazos e andamento do projeto;
    Métricas post-mortem do andamento do projeto;
    Participação em treinamento;
   Ferramentas e técnicas utilizadas;
       a) Linguagem de programação Java
       b) "The Java Sound API"
       c) Notas musicais e freqüências
       d) Formatos de som
       e) Achando a freqüência com representação PCM
       f) Fast Fourier Transform
       g) Projeto "Software Livre"
    Estrutura final do programa
    Técnicas relevantes para o projeto, porém inexploradas por razões quaisquer;
    Forma de acompanhamento do professor supervisor do projeto;
    Comentários sobre o resultado final;
    Figuras ilustrativas do programa em funcionamento;
    Link onde o programa poderá ser obtido e
    Bibliografia utilizada para o desenvolvimento do projeto

2) Relação do projeto com o BCC

    Desafios e frustrações encontrados;
    Lista das disciplinas mais relevantes para o projeto;
    Interação com membros da equipe que tenham agido como mentores do trabalho;
    Observações sobre a aplicação de conceitos estudados na prática e
    Se eu continuasse atuando na área de desenvolvimento deste projeto, que passos tomaria para aprimorar os conhecimentos técnicos/metodológicos/comerciais/científicos relevantes para esta atividade?

1) Parte técnica

Definição / especificação do projeto

O projeto consiste em produzir um software que simule um afinador musical eletrônico no computador, ou seja, que receba sons de um microfone ligado ao mesmo e os compare com as 12 notas conhecidas, dizendo da qual se aproxima mais e se é mais grave ou mais aguda que esta nota. O resultado é apresentado por uma interface gráfica amigável. Além disso, outro objetivo importante é a disponibilização deste software para uso público na internet sob uma licença de software livre.

Este é um modelo específico para violão e guitarra, mas ele ilustra bem como funciona um afinador:

Ele recebe uma entrada de som via microfone e entrada direta de áudio também. A freqüência predominante é detectada e comparada com as freqüências das notas conhecidas.
Para exibir o resultado, a nota aproximada é destacada (no caso só aparecem as notas que correspondem às cordas de um violão ou guitarra na afinação padrão - E, A, D, G, B, E). É indicado também o quão distante daquela nota está o som recebido (no caso um medidor é movido e algumas luzes são acesas).

Forma de organização da dupla e atribuição de responsabilidades

Não houve uma divisão bem organizada das tarefas entre os membros, mas buscamos sempre dividi-las de alguma forma. Algumas vezes as coisas foram feitas juntamente.

Estimativa inicial de prazos e andamento do projeto

As estimativas eram basicamente:

    - Teste da biblioteca de som no Linux, para decisão de portabilidade para o mesmo.
    - Estudo detalhado sobre a biblioteca de som, incluindo a escolha de um formato de representação de som no computador, como capturar o som dentro do programa através de um microfone e como descobrir qual a nota "olhando" a representação escolhida.
    - Projeto de um protótipo do programa sem levar em consideração a interface gráfica.
    - Implementação do protótipo.
    - Projeto do programa final com a interface gráfica.
    - Implementação do software final.

Não foram estipulados prazos específicos para cada atividade mas era esperado ter o protótipo sem interface antes de novembro.

Métricas post-mortem do andamento do projeto

    - O teste da biblioteca de som no Linux não foi possível pois não conseguimos fazer o microfone funcionar neste sistema operacional. Resolvemos não perder muito tempo com isso, afinal, pelo fato do programa ser em Java é muito mais fácil rodá-lo em qualquer sistema operacional (mais fácil do que C pelo menos). Assim, acreditamos que o programa funciona em qualquer sistema com um jdk 1.3 ou acima instalado, que tenha os pacotes do Java 2 e uma placa de som compatível com a Java Sound API. As placas usadas para testar o software foram uma SiS 7018 e uma SoundBlaster 16 em diferentes versões do Windows. Em ambos sistemas o programa funcionou perfeitamente.
    - A biblioteca Java Sound foi estudada mas não precisou ser estudada muito detalhadamente pois a parte de hardware é quase totalmente transparente ao programador. Só foi necessário pegar um programa-exemplo que grava o som e modificá-lo um pouco. A seguir foi pesquisado o formato de som PCM, que será explicado mais adiante. Depois, foram feitas as tentativas de descobrir a freqüência, como também será detalhado mais adiante.
    - O projeto do protótipo sem interface foi bem rápido pois a arquitetura se mostrou bem simples. Na verdade o programa principal consta basicamente de um laço infinito com alguns poucos passos!
    - No fundo não houve uma implementação de protótipo pois o software final estava sempre em mente. Ele foi implementado aos poucos, foi um processo contínuo que só demorou por causa das tentativas fracassadas (a serem explicadas).
    - A interface só trouxe de novo duas classes (de janelas) que não estavam na estrutura inicial. Não foi necessário alterar o resto do programa pois por falta de tempo não foi possível fazer uma interface elaborada, com mais funcionalidades.
    - A implementação do software acabou se misturando à do protótipo, como já explicado. E quando se projetou a interface a implementação também foi imediata.

Participação em treinamento

Não participei de nenhum treinamento específico pois já tinha uma relativa experiência com Java e Swing.

Ferramentas e técnicas utilizadas

Aqui detalhamos o que foi feito no nosso projeto e como tudo foi feito.

a) Linguagem de programação Java

    Decidimos no início do projeto pela escolha da linguagem Java. Isto pelo seu aspecto de grande abertura técnica não só para desenvolver nosso projeto, como também para dar suporte às modificações que fossem necessárias, algo ao nosso ver essencial, dado o caráter mutável do nosso trabalho (principalmente pelas vários meios de tratamento de sinais - no nosso caso ondas sonoras).
   Outro motivo que nos levou à utilização da linguagem Java foi o formato que imporíamos ao nosso projeto. Um produto baseado no conceito de "software livre", com código aberto, pronto para possíveis melhorias e modificações. Nada mais intuitivo então que empregarmos uma das mais utilizadas linguagens atuais, tanto na WEB quanto na criação de software empresarial (utilização esta devido, como dito antes, ao grande leque de ferramentas disponíveis aos seus usuários).
    O ponto culminante para o emprego desta ferramenta, tornando o projeto um "fruto legítimo" da linguagem Java, foi o problema de captação do sinal vindo da placa de som do micro em uso. Esta parecia ser a principal barreira a ser vencida, que inclusive nos levou a um estudo inicial (mínimo) do funcionamento de tais placas. Porém, conforme o projeto foi tomando maior corpo, algumas posições foram ficando mais claras e com a ajuda do professor Flávio Soares Corrêa da Silva e do professor Fábio Kon descobrimos uma biblioteca Java para tratamento de ondas sonoras, "The Java Sound API" (inclusão do pacote javax.sound.sampled). Tínhamos a partir desse momento encontrado todo o suporte técnico para o início da programação por si só.
    Outro ponto a favor da linguagem Java é a facilidade de portar a aplicação para diversos sistemas operacionais, através dos arquivos .class. Porém, o programa só foi realmente testado em Windows, com a ajuda do JBuilder.

b) "The Java Sound API"

Biblioteca que possibilita uma interface entre a placa de som do microcomputador e o programa que a utiliza. Guarda um conjunto de métodos para o manuseio das ondas sonoras captadas pela placa de som. Uma grande vantagem da biblioteca é que a parte de hardware é quase totalmente transparente ao programador. Usamos um método para gravação de som, adaptado de um tutorial da Java Sound API, que utiliza uma classe chamada AudioSystem que se encarrega automaticamente de reconhecer a placa de som usada e transformar a entrada do microfone em um vetor de bytes.

c) Notas musicais e freqüências

    Um dos pontos do nosso projeto é a busca por um padrão baseado nas 12 notas musicais nas ondas que leríamos da placa de som. Para isso é necessário uma breve explicação do funcionamento desta idéia em vista do aspecto freqüência da onda!
    Cada nota musical é marcada por uma determinada freqüência, por exemplo a nota musical C (dó) tem freqüência de 55hz, e obviamente outras ondas sonoras também terão uma determinada freqüência. Nosso programa então verifica a freqüência da onda lida pela placa de som e tenta mostrar de qual das 12 freqüências (notas) ela se aproxima mais. Uma outra observação é que as 12 notas se repetem periodicamente, assim um dó por exemplo pode ser muito grave ou muito agudo. Estas diferentes freqüências de uma mesma nota são chamadas de oitavas.
   A idéia geral até agora foi simples, porém a pergunta essencial é "Como fazemos isso?"

d) Formatos de som

Há diversas formas de se representar som digitalmente em um computador. Alguns formatos mais conhecidos popularmente são Wave (arquivos .wav), MP3 (.mp3) e Real Audio (.ra). Outro formato é o Pulse-Code Modulation (PCM), que foi o escolhido para usarmos pois a Java Sound API já o possui definido em uma de suas classes (AudioFormat.Encoding).
Para entendermos como funciona o formato PCM vejamos abaixo a figura de uma onda representando um som qualquer.

Quando queremos representar o som digitalmente num computador, precisamos discretizar esta onda. A forma usada pelo formato PCM consiste em guardar num vetor as amplitudes em determinados intervalos de tempo. O valor da amplitude (ou de cada posição do vetor) precisa estar em um intervalo finito também. Assim a discretização da onda é feita em duas formas, em duas dimensões, como mostrado na figura abaixo.

   Quanto aos possíveis valores da amplitude, pode-se por exemplo usar 8 bits para cada posição do vetor (no nosso caso foi sucifiente usar 8 bits). O valor da amplitude pode ser então de -127 a 127. Uma característica do formato PCM é que ele realiza um mapeamento linear da intensidade do som para este intervalo. Outros formatos (como mu-law) usam mapeamentos não-lineares.
   A discretização na dimensão horizontal corresponde a uma taxa de frames por segundo. Um frame é uma amostra do som em um determinado instante. No nosso caso usamos uma taxa de 16000 frames por segundo. Isto equivale a 16000 posições no nosso vetor de bytes (taxa de samples por segundo). Observamos que um frame pode conter vários canais, cada um correspondendo a um sample em um determinado instante. Ou seja, se a gravação for em modo estéreo serão utilizados 2 canais. No nosso caso usamos 1 canal apenas (mono) para simplificar a representação e o algoritmo de busca de freqüência. Se usássemos 6 canais um frame teria 6 bytes e um segundo de som teria 16000 * 6 = 96000 bytes. Se além disso usássemos 2 bytes para representar a amplitude teríamos 192000 bytes por segundo (12 bytes por frame).
   Tudo isso é para deixar claro que a taxa de frames por segundo difere da taxa de samples por segundo. Usamos um formato mais simples por conveniência.

e) Achando a freqüência com representação PCM

    A partir daí tomamos alguns rumos para tentar achar a freqüência do som:
    - O primeiro rumo foi o de pegar um intervalo da onda (duas cristas consecutivas), acharmos desta forma o comprimento da onda e aplicarmos a equação: freqüência = taxa de amostras (samples) por segundo / comprimento da onda (distância entre duas cristas consecutivas). Porém esta maneira mostrou-se ineficiente dadas as grandes irregularidades que as ondas lidas apresentavam e nenhum padrão aceitável era alcançado;
    - O segundo foi buscar a freqüência contando diretamente o número de cristas encontradas no vetor. Esse número é dividido pelo intervalo de tempo a que o vetor equivale (obtido através da taxa de samples por segundo), e o resultado é a freqüência. Nenhum padrão aceitável foi encontrado!
    - Terceiro método: uso da Fast Fourier Transform (FFT).

Dadas as dificuldades até aquele presente momento decidimos fazer uma pesquisa por tratamento de sinais tanto em livros como na WEB. E verificamos o uso de uma ferramenta muito utilizada quando se fala processamento de sinais, a Fast Fourier Transform (FFT). Quando de seu uso verificamos que a FFT acabava por dar diferentes coeficientes para as freqüências de um sinal, onde o maior valor ia para as freqüências que mais apareciam neste sinal.
Percebemos então que a leitura da onda da placa de som vinha com grande quantidade de outras freqüências (ruídos), o que impedia uma leitura direta da freqüência da onda (explicando mais claramente o insucesso das outras tentativas).

f) Fast Fourier Transform

A transformada de Fourier é uma técnica matemática de separar as freqüências de um certo sinal indicando a magnitude de cada freqüência do sinal (as freqüências com maiores valores são as de maior intensidade no sinal).
O algoritmo da FFT (Fast Fourier Transform) calcula o espectro do sinal mais rápido que o algoritmo da DFT (Discrete Fourier Transform), o que pode ser observado tendo em vista a complexidade de ambos os códigos: FFT - O (Nlog2N), DFT - O (N^2). Uma desvantagem da FFT é que o sinal digital discreto de entrada precisa ser proporcional a uma potência de 2 (facilmente resolvido completando com zeros caso o tamanho do vetor de entrada fuja a esse padrão, ou descartando parte da informação até termos uma potência de 2). A FFT pode ser usada para uma ou duas dimensões (processamento de imagens).

Equação da DFT:

,
onde N é o número de amostras do sinal.
Link sobre FFT

g) Projeto "Software Livre"

Um dos pontos do nosso projeto foi o aspecto "produzir um software livre", usando a licença GPL (General Public License), abordando uma das principais vertentes de produção de software recente. Abaixo damos uma dimensão do que é um software livre:

"Software livre se refere à liberdade dos usuários executarem, copiarem, distribuírem, estudarem, modificarem e aperfeiçoarem o software. Mais precisamente, ele se refere a quatro tipos de liberdade, para os usuários do software:

       - A liberdade de executar o programa, para qualquer propósito (liberdade no. 0).
       - A liberdade de estudar como o programa funciona, e adaptá-lo para as suas necessidades (liberdade no. 1). Acesso ao código fonte é um pré-requisito para esta liberdade.
       - A liberdade de redistribuir cópias de modo que você possa ajudar ao seu próximo (liberdade no. 2).
       - A liberdade de aperfeiçoar o programa, e liberar os seus aperfeiçoamentos, de modo que toda a comunidade se beneficie (liberdade no. 3). Acesso ao código fonte é um pré-requisito para esta liberdade.

        Um programa é software livre se os usuários tem todas essas liberdades. Portanto, você deve ser livre para redistribuir cópias, seja com ou sem modificações, seja de graça ou cobrando uma taxa pela distribuição, para qualquer um em qualquer lugar. Ser livre para fazer essas coisas significa (entre outras coisas) que você não tem que pedir ou pagar pela permissão.
        Você deve também ter a liberdade de fazer modificações e usá-las privativamente no seu trabalho ou lazer, sem nem mesmo mencionar que elas existem. Se você publicar as modificações, você não deve ser obrigado a avisar a ninguém em particular, ou de nenhum modo em especial.
        A liberdade de utilizar um programa significa a liberdade para qualquer tipo de pessoa física ou jurídica utilizar o software em qualquer tipo de sistema computacional, para qualquer tipo de trabalho ou atividade, sem que seja necessário comunicar ao desenvolvedor ou a qualquer outra entidade em especial.
        A liberdade de redistribuir cópias deve incluir formas binárias ou executáveis do programa, assim como o código fonte, tanto para as versões originais quanto para as modificadas. Está ok se não for possível produzir uma forma binária ou executável (pois algumas linguagens de programação não suportam este recurso), mas deve ser concedida a liberdade de redistribuir essas formas caso seja desenvolvido um meio de criá-las.
        De modo que a liberdade de fazer modificações, e de publicar versões aperfeiçoadas, tenha algum significado, deve-se ter acesso ao código fonte do programa. Portanto, acesso ao código fonte é uma condição necessária ao software livre.
        Para que essas liberdades sejam reais, elas tem que ser irrevogáveis desde que você não faça nada errado; caso o desenvolvedor do software tenha o poder de revogar a licença, mesmo que você não tenha dado motivo, o software não é livre. Entretanto, certos tipos de regras sobre a maneira de distribuir software livre são aceitáveis, quando elas não entram em conflito com as liberdades principais. Por exemplo, copyleft (apresentado de forma bem simples) é a regra de que, quando redistribuindo um programa, você não pode adicionar restrições para negar para outras pessoas as liberdades principais. Esta regra não entra em conflito com as liberdades; na verdade, ela as protege.
        Portanto, você pode ter pago para receber cópias do software GNU, ou você pode ter obtido cópias sem nenhum custo. Mas independente de como você obteve a sua cópia, você sempre tem a liberdade de copiar e modificar o software, ou mesmo de vender cópias.
        "Software Livre" NÃO significa "não-comercial". Um programa livre deve estar disponível para uso comercial, desenvolvimento comercial, e distribuição comercial. O desenvolvimento comercial de software livre não é incomum; tais softwares livres comerciais são muito importantes.
         Regras sobre como empacotar uma versão modificada são aceitáveis, se elas não acabam bloqueando a sua liberdade de liberar versões modificadas. Regras como "se você tornou o programa disponível deste modo, você também tem que torná-lo disponível deste outro modo" também podem ser aceitas, da mesma forma (note que tal regra ainda deixa para você a escolha de tornar o programa disponível ou não). Também é aceitável uma licença que exija que, caso você tenha distribuído uma versão modificada e um desenvolvedor anterior peça por uma cópia dele, você deva enviar uma.
        Às vezes regras de controle de exportação e sanções de comércio podem limitar a sua liberdade de distribuir cópias de programas internacionalmente. Desenvolvedores de software não tem o poder para eliminar ou sobrepor estas restrições, mas o que eles podem e devem fazer é se recusar a impô-las como condições para o uso dos seus programas. Deste modo, as restrições não afetam as atividades e as pessoas fora da jurisdição destes governos.
        Quando falando sobre o software livre, é melhor evitar o uso de termos como "dado" ou "de graça", porque estes termos implicam que a questão é de preço, não de liberdade.
        Finalmente, note que critérios como os estabelecidos nesta definição do software livre requerem cuidadosa deliberação quanto à sua interpretação. Para decidir se uma licença se qualifica como de software livre, nós a julgamos baseados nestes critérios para determinar se ela se segue o nosso espírito assim como as palavras exatas. Se uma licença inclui restrições impensadas, nós a rejeitamos, mesmo que nós não tenhamos antecipado a questão nestes critérios. Às vezes um requerimento de alguma licença levanta uma questão que requer excessiva deliberação, incluindo discussões com advogados, antes que nós possamos decidir se o requerimento é aceitável. Quando nós chegamos a uma conclusão sobre uma nova questão, nós freqüentemente atualizamos estes critérios para tornar mais fácil determinar porque certas licenças se qualificam ou não."
    (texto extraído de www.gnu.org. Copyright (C) 1996, 1997, 1998, 1999, 2000 Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111, USA)

        Um dos argumentos de empresas monopolistas (a Microsoft seria o melhor exemplo) para derrubar o software livre é que este sistema não funciona, pois não há garantia nenhuma de evolução.
        Os desenvolvedores neste tipo de sistema possuem diversas motivações e as interações entre estas devem ser estudadas. Eric Raymond sugere que a principal motivação é a reputação como bons programadores em determinados ambientes. Provavelmente, o que realmente ocorre é muito mais complexo. Deve-se notar que as reputações são muito importantes para se realizar classificações, como no Google, por exemplo.
         Um software livre pode evoluir facilmente, no sentido de mudar para melhor, não sendo necessário começar do zero mas sim fazer um reaproveitamento do que já existe, o que é uma característica da cultura hacker.
        O software livre agride o modelo do software proprietário, principalmente no quesito da propriedade intelectual.
        Embora o valor comercial do software livre seja considerável (o preço da distribuição Debian do sistema operacional GNU/Linux giraria em torno de um bilhão de dólares), o software é gratuito e livre. As liberdades garantidas por este paradigma nem de longe podem ser alcançadas por softwares proprietários.

Livro com capítulo sobre transformadas de Fourier:
Shape Analysis and Classification - Theory and Practice - Luciano da Fontoura Costa e Roberto Marcondes Cesar Jr. - CRC Press LLC 2001 - ISBN: 0-8493-3493-4.

Livro Digital audio with Java - Craig A. Lindley - Prentice Hall PTR 2000 - ISBN: 0-13-087676-3. Código do livro aqui. Este livro contém o código da FFT que foi usado no programa.

2) Relação do projeto com o BCC