Usando o Kinect em um jogo de fliperama

Conforme comentei nos meus artigos sobre o Microsoft Kinect, além dos jogos oficiais uma das coisas mais interessantes do novo acessório são os hacks e aplicações feitas em casa, com o Kinect ligado ao PC.

Do lançamento pra cá já apareceram inúmeros exemplos interessantes. Resolvi, por brincadeira, fazer algo também: usar o Kinect para controlar um jogo antigo de fliperama, o Gladiator (Taito, 1986), que costumava jogar bastante quando era criança!

Foi surpreendentemente fácil, o que demonstra a maturidade das ferramentas já disponíveis, desenvolvidas por cientistas e hackers do mundo todo, e também ofertadas gratuitamente pela PrimeSense, a empresa que desenvolveu o Kinect junto à Microsoft.

Dêem uma olhada no vídeo, e no artigo em meu blog pessoal a respeito:

Kinect MAME: Gladiator (Taito, 1986) by muriloq

Meu próximo passo, além de usar o Kinect para mais alguns jogos já sugeridos pelo pessoal, é adaptá-lo para softwares educativos e para comunicação assistida, especialmente os para autistas. O primeiro provavelmente será o Z.A.C. Browser (Zone for Autistic Children), que é o preferido do meu filho Max, de quatro anos.

Uncategorized 0 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)

Um cientista explica o Microsoft Kinect, Parte II

A recepção ao meu primeiro artigo explicando a tecnologia por trás do Kinect, o novo acessório da Microsoft sendo lançado essa semana, foi surpreendente, em vários aspectos. O primeiro foi a enorme quantidade de visitantes, comentários e elogios, o que obviamente me deixou muito feliz…

O segundo aspecto, entretanto, foi mais interessante e inesperado: o diretor de incubação da Microsoft Alex Kipman, responsável pelo desenvolvimento do Kinect (e brasileiro!), leu o artigo! E, para minha surpresa, explicou que eu estava enganado com relação à tecnologia usada para obter os resultados surpreendentes que descrevi no artigo anterior, e me apontou no caminho certo.

A minha primeira reação foi a de ficar com vergonha: afinal de contas dei uma explicação que fazia muito sentido mas que não estava totalmente correta, e para uma audiência enorme. Vergonha ou não, só existe uma alternativa correta nesse caso, que é assumir o engano e corrigir a informação, o que é o que faço hoje. Alguns amigos me consolaram dizendo que qualquer cientista erra, e esse é o único jeito de continuar aprendendo, e concordo com eles! Além do mais, é inegável que ser corrigido pelo próprio Alex Kipman é no mínimo algo bem empolgante!

O que continua valendo?

Expliquei no artigo anterior que a antiga Power Glove, o Wii e o Move retornam informações limitadas, e semelhantes. Todos retornam informação a respeito de um ou dois pontos no espaço; o que muda são os graus de liberdade (DOF, de degrees of freedom) retornados para o ponto. O ideal é que você tenha seis graus de liberdade, ou seja, que o sistema saiba não só a posição espacial do controle (as coordenadas x,y,z do controle) mas também os três ângulos (roll, pitch e yaw) que determinam para onde ele está inclinado. O Move e o Wiimotion Plus retornam isso, o que é bem bacana; a Power Glove, nos 1980s, já retornava x,y,z, yaw e roll, ou seja, 5DOF.

Seis graus de liberdade no Wiimote

Seis graus de liberdade no Wiimote

O problema desses sistemas é que eles se restringem à posição (mesmo que com 6DOF) apenas do controle propriamente dito. O Kinect, por sua vez, entrega informação 3D da cena inteira (ou seja, entrega um mapa de profundidade, como apontou o nic nos comentários do primeiro artigo). A partir desse mapa ele detecta a posição do corpo inteiro da pessoa que está em frente à câmera. Essa é a grande inovação, e a explicação continua valendo! O que muda é como esse mapa é construído, e quem desenvolveu o sensor.

Um conto de duas empresas israelenses

No artigo anterior eu disse que a tecnologia usada no Kinect veio da empresa israelense 3DV, que produzia a ZCam, uma câmera TOF (time-of-flight) que entrega um mapa de profundidade como o que era necessário. A 3DV foi comprada pela Microsoft há algum tempo. Pouco depois foi anunciado o Project Natal, que virou o Kinect, e mais tarde comunicaram que a tecnologia dele era de uma empresa israelense que fazia câmeras 3D

Meu engano foi assumir que a empresa israelense era a 3DV! Na verdade a Microsoft comprou a 3DV, mas com interesse no seu portfólio de patentes. conforme explicado no venturebeat.com. Como eu assumi que a tecnologia usada era a da 3DV, eu expliquei como funcionava a câmera dela, a ZCam, que é uma câmera TOF…

Mas o sensor do Kinect foi desenvolvido pela Microsoft, internamente, numa parceria com uma outra empresa israelense que produzia câmeras que retornam mapas de profundidade, a PrimeSense (foi aqui o Alex Kipman me corrigiu). Essa informação muda completamente a minha hipótese, porque a PrimeSense usa um outro método para detectar a profundidade na cena, baseado em luz estruturada (structured light)! E o Kinect não é idêntico aos produtos da própria PrimeSense, pois o sensor em si foi projetado especificamente para as necessidades da Microsoft.

O sensor de profundidade da PrimeSense

Explicada a confusão, posso explicar como funciona o sensor da PrimeSense. Como disse, o sensor do Kinect não é exatamente o mesmo sensor da PrimeSense, então pode ser que algum detalhe seja diferente do que vai ser descrito aqui, mas o princípio é simples de entender a partir de um pequeno exemplo.

Vamos começar por um projetor comum, como os que são usados em cinema e home theaters, ou mesmo um retroprojetor dos antigos, que usam transparências. Esse projetor é usado para projetar um quadriculado uniforme. Se você coloca o projetor perto da parede, o quadriculado aparece pequeno, com cada quadradinho ocupando pouco espaço. Similarmente, se você projeta numa parede bem distante, os quadrados aparecem enormes.

Se você entra na frente do projetor, o quadriculado é projetado em seu corpo. A parte do quadriculado que acerta você aparece de um tamanho, e a parte que acerta a parede lá no fundo aparece de outro… Ou seja, se você mede, na imagem da câmera, o tamanho de cada quadradinho do quadriculado você sabe, baseado no tamanho dele, a que distância ele está! O quadriculado é luz estruturada, ou seja, luz com uma estrutura bem definida que permite que você descubra informações sobre a cena baseado na forma como essa luz é refletida.

Note que você pode detectar a profundidade não só com o tamanho do quadradinho (esse é só um exemplo didático), mas também observando, por exemplo, como linhas que deveriam ser retas são distorcidas ao serem projetas em superfícies curvas.

Luz estruturada projetada em superfície irregular

Luz estruturada projetada em superfície irregular

Um ponto difícil é que você precisa de uma óptica bem precisa: quanto mais resolução tem o quadriculado, mais exata a sua medida. Para enxergar o quadriculado você precisa de uma câmera de alta resolução, e para medir em tempo real o tamanho de todos os quadradinhos você precisa de hardware e software dedicados, numa arquitetura paralela.

No Kinect o quadriculado é projetado com luz infravermelha, invisível, logo você não percebe. Qualquer câmera digital comum detecta infravermelho: se você filmar com seu celular um controle remoto comum de TV funcionando você consegue enxergar o LED infravermelho dele piscando toda vez que você aperta uma tecla. Isso é uma vantagem enorme, porque isso implica que com uma câmera de infravermelho comum você consegue enxergar o quadriculado! Não é preciso o hardware dedicado caro da 3DV, que descrevi no artigo anterior, em que cada “pixel” tem o equivalente a um cronômetro para medir o tempo de vôo. Provavelmente o custo foi a principal razão por terem escolhido a PrimeSense ao invés da 3DV, aliás.

Mas isso não significa que o Kinect seja simplesmente uma câmera infravermelho comum, porque o processamento em tempo real necessário para extrair o mapa de profundidade a partir da imagem do quadriculado é bem sofisticado. Ele usa um sensor (CCD) comum, mas tem bastante coisa por trás.

Ilustração do design de referência da PrimeSense

Ilustração do design de referência da PrimeSense

Alguns aspectos ainda não estão claros para mim: o padrão exato usado, por exemplo (não precisa ser necessariamente um quadriculado; linhas paralelas podem ser usadas, ou mesmo padrões bem sofisticados que codificam mais informação), a resolução desse padrão (e consequentemente a resolução do mapa de profundidade) e outros detalhes do algoritmo usado. Mas isso não afeta o entendimento de como o processo funciona.

Galantucci, L. M. , Percoco, G. and Dal Maso, U. 'Coded targets and hybrid grids for photogrammetric 3D digitisation of human faces', Virtual and Physical Prototyping, 3:3, 167 - 176

Galantucci, L. M. , Percoco, G. and Dal Maso, U. 'Coded targets and hybrid grids for photogrammetric 3D digitisation of human faces', Virtual and Physical Prototyping, 3:3, 167 - 176

Quem estiver interessado em maiores detalhes pode ler as patentes da Prime Sense, como por exemplo:

Conclusão

O fato do sensor do Kinetic usar luz estruturada desenvolvida em conjunto com a PrimeSense, ou uma câmera TOF da 3DV não muda o meu entusiasmo. O interessante, como já expliquei, é ter um mapa de profundidade em tempo real, de baixíssimo custo. O aprendizado de máquina usado para extrair informações de postura corporal a partir do mapa continua o mesmo, e as muitas aplicações que uma tecnologia assim tem também.

A comparação de preço que fiz com a SwissRanger SR4000 da Mesa Imaging agora não é mais tão justa, já que câmeras TOF são mesmo bem mais caras que câmeras baseadas em luz estruturada. Mas comparar, por exemplo, a resolução do mapa de profundidade e a velocidade com que ele é produzido continua válido.

Uma vez mais, gostaria de agradecer a todos os leitores pela atenção, e de me desculpar com eles pelo engano. Um agradecimento especial, é claro, vai para o leitor mais ilustre, o Alex Kipman, e pela atenção e gentileza dele ao me corrigir. Espero que a leitura tenha sido divertida!

Mundos Virtuais, Processamento de Sinais, Reconhecimento de Faces, Robótica, Visão Computacional 9 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (6 votes, average: 5,00 out of 5)

Um cientista explica o Microsoft Kinect

ATUALIZAÇÃO IMPORTANTE: Fiquei muito surpreso quando o próprio Alex Kipman, Diretor de Incubação pela Microsoft e responsável pelo Kinect, me corrigiu hoje, via Twitter! O Kinect não usa uma time-of-flight camera. A ZCam da 3DV que menciono é que usa, mas o Kinect não foi baseado nela, mas sim numa outra tecnologia chamada Light Coding ™, de outra empresa israelense, a PrimeSense. Quase tudo que eu disse no artigo ainda se aplica, e a explicação sobre como câmeras TOF funcionam está certa, mas a forma como o Kinect obtém a informação 3D é diferente da que descrevi. Prometo explicá-la em detalhes em um outro artigo. Peço desculpas pela enorme confusão, mas ser um cientista também é saber reconhecer os próprios erros, e fico imensamente agradecido ao Alex Kipman por ter me corrigido.

Murilo Queiroz, cientista da computação e mestre em engenharia eletrônica, explica porque o Kinect é a tecnologia mais impressionante do ano, com um nível de detalhe que você não encontra em lugar nenhum!

Em novembro a Microsoft lançará o Kinect, o novo acessório para o videogame Xbox 360. Com o Kinect, o jogador será capaz de controlar os jogos apenas com o próprio corpo, sem precisar de absolutamente mais nada. Do ponto de vista estritamente técnico o Kinect é o acessório mais revolucionário da história dos videogames, e provavelmente um dos produtos tecnológicos mais excitantes do ano.

Microsoft Kinetic

Microsoft Kinect

Entretanto não se vê tanto entusiasmo por aí. Depois do sucesso estrondoso do Wii, jogar com o corpo títulos como boliche ou tênis já não é mais novidade. E, recentemente, a Sony lançou o Move, para o Playstation 3, que tecnicamente é um Wiimote levemente melhorado. Afinal, o que o Kinect tem de tão diferente ?

Procurando por aí não se encontra uma boa explicação. Aliás, eu não achei nenhuma explicação técnica correta de como o Kinect funciona. Pelo contrário: achei reportagens publicadas em veículos conceituados que estão totalmente erradas com relação ao funcionamento do Kinect! Não admira quase todo mundo achar que se trata de mais uma cópia do Wii, como o Playstation Move…

Assim, resolvi explicar, tintim por tintim, o que é o Kinect, porque ele é diferente de qualquer coisa que você já viu antes, e porque eu digo que “usar o Kinect só para videogame é a coisa mais boba que alguém poderia fazer”. Prepare-se porque o artigo é longo, mas vale a pena!

Wii e Move

O Wii e o Move funcionam de forma muito parecida. Você tem um emissor de luz infravermelha (no Wii, preso à TV; no Move, no controle do jogador) e uma câmera de vídeo tradicional. A câmera enxerga a luz infravermelha e com isso detecta onde o jogador está apontando o controle. Isso é feito de forma 2D, ou seja, o resultado final é você ter uma posição na tela, como se fosse um mouse. Usando acelerômetros dentro do controle você consegue perceber a inclinação dele, e assim você consegue – com uma precisão razoável – saber a posição em que o controle está, além de onde ele está apontando.

Essa tecnologia existe há muito anos; a própria Sony lançou algo parecido para o Playstation 2, o EyeToy, que também é o nome da câmera usada pelo Move no Playstation 3. No final dos anos 1980 a Nintendo lançou um acessório que funcionava basicamente da mesma forma e que populou os sonhos de uma geração inteira, a Power Glove, para o Nintendo 8-bits, mas que infelizmente não funcionava muito bem. O Wii é só a segunda tentativa da Nintendo nessa mesma idéia.

Nintendo Power Glove, o ancestral do Wiimote

Nintendo Power Glove, o ancestral do Wiimote

Visão 3D tradicional

A visão 3D tradicional, que também existe há muitos anos e não funciona lá muito bem, imita a forma com que animais enxergam. Cada um dos nossos olhos vê uma imagem ligeiramente diferente (basta fechar alternadamente cada olho para perceber isso; é o que chamamos de paralaxe). O cérebro combina essas duas imagens e nos dá a percepção 3D. Se você entrega uma imagem ligeiramente diferente para cada olho você consegue essa mesma percepção 3D, e é isso que se fazem nos cinemas e TVs 3D, que voltaram à moda recentemente. Chamamos essa técnica de visão estereoscópica (áudio estéreo é o que manda som diferente para cada ouvido; imagem estéreo faz a mesma coisa, mas com os olhos).

No caso de visão, você usa duas câmeras para obter essas imagens diferentes, e um software calcula a posição 3D dos objetos baseada nas diferenças entre essas duas imagens. O problema é que dependendo da posição do objeto você precisa mudar o ângulo entre as duas câmeras, e o seu foco; e mesmo se você mantém isso fixo é bastante difícil obter um modelo 3D realmente bom.

Um pequeno robô com visão estereoscópica

Um pequeno robô com visão estereoscópica

Visão 3D do Kinect

Pássaros voam batendo as asas, mas isso não significa que essa seja a forma mais eficiente de fazer isso. A visão estéreo usa duas câmeras, imitando nossos dois olhos, mas assim como um avião voa mais longe, mais alto e mais rápido que qualquer pássaro é possível fazer visão 3D muito melhor de forma radicalmente diferente do que ocorre na natureza.

E é essa a abordagem do Kinect! O componente central dele é o que chamamos de câmera de tempo de vôo, ou time-of-flight (TOF) camera. Vou explicar com cuidado como ela funciona. Antes disso, e já que o assunto é inspiração na natureza, vamos falar de morcegos e golfinhos. Morcegos e golfinhos inspiraram o radar e o sonar. Funcionam baseado em eco: você emite um som (ou um pulso de rádio) e então mede o tempo que demora até o som bater no objeto e voltar. Como conhecemos a velocidade do som (ou da luz, no caso do radar) podemos calcular a que distância o objeto em que o som ou o pulso bateram está.

Imagine que você está numa sala totalmente escura, com uma câmera digital em um tripé. Quando você dispara o flash, a luz sai da câmera, viaja na velocidade da luz, e é refletida pelos objetos em frente a ela. A matriz de sensores (CCD) da câmera digital, que faz o papel do filme fotográfico de antigamente, detecta a luz que volta. Cada pixel na imagem que você obtém vem de um sensor nessa matriz, que indica quanta luz recebeu.

Agora imagine que há um cronômetro em cada sensor (lembrando que cada sensor corresponde a um pixel), que mede quanto tempo se passou entre o flash ser disparado e o “pixel” acender. Efetivamente cada cronômetro mede o tempo que a luz levou para sair do flash, refletir em algum objeto, e finalmente acertar o sensor. Fazendo a mesma conta usada no radar, você consegue descobrir a distância de cada pixel na imagem. Efetivamente cada sensor / pixel da câmera é um radar independente!

Funcionamento de um radar

Funcionamento de um radar

O problema, claro, é que estamos falando de luz. E, como sabemos, a velocidade da luz é altíssima, 300 mil kilômetros por segundo. Um radar aeronáutico mede quantos microssegundos um pulso de rádio leva para percorrer dezenas de quilômetros. Como seria possível medir com precisão o tempo que a luz leva para percorrer os poucos metros entre a câmera e a pessoa sendo filmada ? Essa conta é fácil de fazer: consideremos que a pessoa está a dois metros da câmera; a luz então tem que percorrer quatro metros no percurso de ida e volta. Na velocidade da luz, isso leva cerca de 13 nanossegundos. Esse é um período de tempo extremamente curto! Mas lembre-se que hoje temos computadores extremamente rápidos…

Os 2 GHz do seu computador significam que ele executa 2 bilhões de instruções em um segundo, ou seja, que uma instrução é executada a cada 60 nanossegundos. Como um cronômetro é muitíssimo mais simples que um processador, com a tecnologia de hoje é possível fazer um que tenha a precisão necessária.

E esse é o segredo do Kinect. O Kinect tem duas câmeras, o que faz muita gente desinformada achar que ele usa visão estereoscópica. Na verdade uma das câmeras é totalmente tradicional, colorida, como uma webcam qualquer. A outra é uma câmera TOF! O processo que descrevi acima, de acionar o flash e medir quanto tempo a luz leva para ir e voltar, é repetido 30 vezes por segundo. Você sequer vê o flash, e o sistema pode funcionar tanto no escuro quanto numa sala iluminada, porque é usada luz infravermelha. O flash pode ser acionado tão rapidamente porque na verdade ele é um pulso de laser infravermelho.

A imagem que essa segunda câmera fornece é em preto-e-branco; quanto menor o tempo medido pelos cronômetro do pixel mais branco ele aparece. Assim o vídeo da câmera TOF é um modelo 3D extremamente detalhado da imagem capturada – muito superior a qualquer coisa que você consegue usando visão estéreo comum. E isso é absolutamente surpreendente.

Modelo 3D gerado por uma câmera TOF

Modelo 3D gerado por uma câmera TOF

De onde veio ?

OK, a câmera de tempo de vôo do Kinect é uma “matriz de radares” e produz resultados espetaculares. Se é assim porque nunca ouvimos falar disso antes ?

Na verdade cientistas e pesquisadores da área de visão computacional conhecem as time of flight cameras desde 1998. O problema é que a tecnologia para construir cronômetros de precisão altíssima e fontes de luz que emitam pulsos extremamente curtos sempre foi caríssima.

A empresa suíça Mesa Imaging produz uma linha de câmeras TOF voltadas para pesquisa científica há vários anos, chamada SwissRanger. O melhor modelo é a SwissRanger SR4000, que custa US$ 9000 (isso mesmo que você leu, nove mil dólares). Ela tem uma resolução de 176×144 e opera entre 30 e 50 frames por segundo.

O câmera TOF do Kinect tem uma resolução de 320×240, muito superior à da SR4000, e entrega 30 frames por segundo, constantes. E custa US$ 150… Como a Microsoft consegue vender um produto superior por um preço sessenta vezes mais barato ? E quem desenvolveu essa tecnologia tão avançada ?

Tudo começou quando uma pequena empresa israelense,a 3DV Systems. Ela desenvolvia câmeras TOF desde 2000, e em 2007 anunciou o lançamento de uma câmera TOF de baixíssimo custo, a ZCam. Ela chegou a demonstrar em público a ZCam sendo usada num jogo de boxe, para controlar um avatar no mundo virtual Second Life, e para controlar o Windows Media Center. E então, do nada, a 3DV Systems sumiu do mapa.

Alguns meses depois a Microsoft anunciou que tinha comprado a 3DV Systems, e que a tecnologia da ZCam seria usada em um novo acessório para videogame, no então chamado “Project Natal” (o nome-código Natal foi dado em homenagem à cidade brasileira pelo coordenador do projeto, o brasileiro Alex Kipman).

Bom, isso explica a origem da tecnologia. E o preço baixíssimo ? É preciso lembrar que a SwissRanger é uma câmera usada praticamente apenas por pesquisadores. Há centenas, talvez milhares de laboratórios de visõa computacional mundo afora que possuem uma câmera TOF. Eu conversei um bom tempo a respeito com o Dr. Mário Campos, professor de robótica e visão computacional da UFMG e de quem fui aluno, e ele comentou que a SwissRanger é realmente impressionante mas o preço, proibitivo.

Mas a Microsoft pretende vender milhões de unidades do Kinect nos primeiros dias do lançamento. A escala de produção é totalmente diferente, e isso justifica a redução drástica nos preços. A Microsoft vai vender por uma merreca uma tecnologia a que apenas pesquisadores de ponta, com muita verba, tinham acesso, e isso fez todo mundo que conheço que se interessa profissionalmente por robótica e visão computacional ficar extremamente excitado.

E a Microsoft fez o quê ?

Não me interpretem mal: a câmera TOF é o componente mais importante e revolucionário do Kinect, e foi basicamente comprada pronta pela Microsoft, mas essa não é a única enorme inovação. A câmera TOF entrega um modelo 3D da cena, composto por voxels (um pixel é um ponto no espaço 2D; um voxel é um pequeno cubo no espaço 3D).

Isso é só metade do problema: para um jogo você precisa interpretar esse modelo de forma eficiente, ou seja, você precisa detectar o quê daquela imagem 3D corresponde a uma ou mais pessoas, e exatamente em que posição elas estão. É como um OCR, que pega uma fotografia de um jornal e detecta cada letra, retornando o texto que está efetivamente escrito lá.

Fazer isso num modelo de voxels é um problema extremamente difícil. Pense na enorme variação entre as pessoas: há altos e baixos, magros e gordos, crianças, adultos, cachorro passando na frente, mesinhas de centro na sala… O problema não é mais confundir o objeto com o fundo (coisa que acontece com câmeras 2D, que detectam pessoas baseadas na diferença de cor). É ver aquela “escultura de cubinhos” e interpretar que é uma pessoa fazendo o V da vitória.

Aprendizado de Máquina

Para isso a Microsoft usou técnicas de aprendizado de máquina (que aliás é uma das minhas áreas de pesquisa). A idéia é relativamente simples: ao invés de escrever um programa que resolve o problema, você escreve um programa que aprende a resolver o problema analisando milhares de exemplos.

Técnicas comuns de captura de movimentos usam uma roupa cheia de marcadores especiais para detectar a posição do corpo do autor, que é o que queremos fazer com o Kinect. Então simultaneamente filmamos o ator usando a técnica antiga e usando o Kinect, e damos os dados de posição corporal obtidos pela primeira técnica e o vídeo do Kinect para o algoritmo de aprendizado.

Andy Serkis interpretando o Gollum, de O Senhor dos Anéis

Andy Serkis interpretando o Gollum, de O Senhor dos Anéis

Com muito, muito esforço científico e muitos exemplos desse tipo o programa é capaz de aprender como detectar a posição do corpo a partir da imagem 3D vinda do Kinect. Além disso, algumas regras ajudam: sabemos que o tamanho das partes do corpo da pessoa não muda, por exemplo, e sabemos que joelhos e cotovelos não abrem mais de 180 graus.

Nesse ponto os pesquisadores da Microsoft usaram outro recurso interessante: compraram uma quantidade gigantesca de dados de captura de movimentos usados em filmes e jogos antigos, e processaram esses dados para inferir regras como as que mencionei acima.

A combinação de exemplos e regras desse tipo, e o uso intensivo de quantidades obscenas de recursos computacionais ao longo de vários meses, permitiu que o software aprendesse a detectar a posição do corpo de pessoas dos mais variados tamanhos, nas mais variadas posições e ações. O legal é que aprender o modelo requer muitíssimo esforço computacional, mas depois de aprendido executá-lo é algo bem leve – uma tarefa simples que pode ser feita por software, pelo próprio console de videogame. Daí não haver a necessidade do tal “processador extra no Kinect” de que alguns andaram reclamando.

Em termos de quantidade de dados e de pesquisadores envolvidos esse foi o maior projeto de aprendizado de máquina da história. E, não há como negar, o mérito disso tudo é da Microsoft.

O que mais ?

Além de uma câmera convencional, uma câmera de tempo de vôo e software sofisticado para detecção de posição do corpo em tempo real, a Microsoft também integrou ao Kinect microfones direcionais e um bom sistema de reconhecimento de voz. Esse sistema foi treinado (usando aprendizado de máquina, como no caso da posição do corpo) com vozes de milhares de pessoas diferentes, permitindo que ele detecte comandos simples de pessoas diferentes sem treinamento prévio para cada uma. Nada muito superior ao que já se encontra disponível em sistemas operacionais como o Windows 7 e o Mac OS X, mas um excelente complemento para o acessório.

A utilidade para jogos do Kinect vai muito além de “imitar o Wii”, como muita gente vive repetindo. A primeira diferença que nem sempre fica óbvia é que você não é obrigado a ficar de pé pulando e se sacudindo em frente à sua TV. O Kinect pode detectar a posição da sua cabeça e corpo enquanto você está sentado no sofá jogando confortavelmente com seu controle convencional.

Mas a idéia não era eliminar o controle ? Não necessariamente! Nenhum fã de first-person shooters (como Halo) ou simuladores de vôo e corrida vai querer jogar dando tiros com o dedo ou fingindo que está com um volante imaginário nas mãos. Esses hardcore gamers vão jogar com controle, com mouse e teclado ou com um bom volante com force-feedback (eu não abro mão do meu Logitech), obviamente. Mas com o Kinect é possível rastrear a sua cabeça e mudar a imagem na tela conforme a posição dela, como se você tivesse efetivamente olhando para cima e para os lados.

Pode parecer esquisito, mas já é uma técnica usada por muitos jogadores sérios no PC, que usam dispositivos como o TrackIR. Poder olhar para cima ou para os lados enquanto se joga é algo que faz tanta diferença que qualquer um que já tenha usado um rastreador de cabeça não consegue deixá-lo de lado, mesmo o tradicional sendo uma arataca dependurada no seu fone de ouvido ou boné. Só o TrackIR custa mais de US$ 120, e com o Kinect esse tipo de experiência estará disponível para qualquer um.

E essa é só mais uma possibilidade ligada a jogos. Eu particularmente, estou mirando muito, muito mais longe: com câmeras TOF de baixíssimo custo vai finalmente ser possível desenvolver de forma rápida e robusta robôs que enxergam direito, por exemplo. Um carro com câmeras TOF nos pára-choques seria capaz de detectar automaticamente e em tempo real outros carros, pedestres, vagas (e inclusive estacionar automaticamente) de forma muitíssimo melhor do que o que existe hoje. Câmeras TOF instaladas estrategicamente permitiriam que você controle qualquer coisa através de gestos. E com alguma engenhosidade é possível digitalizar esculturas e criar modelos 3D automaticamente simplesmente filmando o objeto.

Scanner 3D baseado em câmera TOF

Scanner 3D baseado em câmera TOF

As possibilidades são inúmeras. É uma inovação que traz uma preciosidade tecnológica caríssima e extremamente poderosa para o grande público. Eu mal posso esperar para colocarmos as mãos no Kinect – não só para nos divertirmos como jogadores, mas também para inventar uma miríade de coisas interessantes, como cientistas e hackers.

ATUALIZAÇÃO: Conforme apontou o leitor @Ramon, cometi um erro de ortografia: o nome do acessório da Microsoft é “Kinect”, não “Kinetic”, como escrevi. O adjetivo em inglês “kinetic”, que equivale ao nosso “cinético”, vem do grego kinétikós e significa ’móvel, que produz movimento’. Já o nome do acessório é um trocadilho com kinetic e connect, e não consta do dicionário.

ATUALIZAÇÃO 2: Ao contrário do que diz o artigo, a Power Glove for desenvolvida  pela Abrams Gentile Entertainment (AGE) e produzida pela Mattel (nos EUA) e pela PAX (no Japão), e não pela Nintendo. Obrigado pelo aviso, Madger!

Uncategorized 74 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5,00 out of 5)

Tatem e Trendzz na final do Desafio Brasil 2010

Na semana passada participamos – com duas empresas diferentes! – da final nacional do Desafio Brasil 2010.  Foi uma experiência tão rica, divertida e interessante que eu não poderia deixar de comentar a respeito!

O Desafio Brasil 2010 é uma competição de start-ups (empresas em estágios iniciais de desenvolvimento) de base tecnológica, que é promovida desde 2006 pelo GVcepe (Centro de Estudos em Private Equity e Venture Capital da Fundação Getúlio Vargas de São Paulo). O Desafio tem o apoio de diversos parceiros, dentre eles a Intel e (a partir desse ano) a Microsoft, e em sua edição mais recente também realizou finais regionais em 8 cidades brasileiras, incluindo Belo Horizonte.

Das mais de 160 empresas inscritas, 24 delas foram selecionadas para a final nacional. As 8 empresas selecionadas no primeiro dia do evento disputam, no dia seguinte, as 4 vagas para a final latino-americana do Desafio Intel, e os vencedores vão para os Estados Unidos participar do IBTEC (Intel+UC Berkeley Technology Entrepeneurship Challenge).

Além da competição propriamente dita o Desafio é uma oportunidade espetacular para networking e para ser visto e avaliado por investidores e outros players importantes da indústria de private equity e venture capital do Brasil, incluindo, é claro, os chamados investidores anjos. O simples fato de poder apresentar sua empresa incipiente a profissionais com grande relevância e experiência e receber deles feedback (ou, como se brincou muito durante o evento, “consultoria grátis”) já é razão mais do que suficiente para querer participar!

Entramos com duas start-ups, a Trendzz e a Tatem, ambas derivadas da nossa experiência de vários anos em suas respectivas áreas e sob os auspícios da fábrica de inovação Igenesis, a nova iniciativa do Vetta Labs.

Murilo Queiroz (esq) e Cassio Pennachin (dir) em seus stands da Trendzz e Tatem

Murilo Queiroz (esq) e Cassio Pennachin (dir) em seus stands da Trendzz e Tatem

A Trendzz é uma plataforma para monitoramento e análise da web e mídias sociais que “entende português”: por meio de técnicas sofisticadas de processamento de linguagem natural fornecemos mineração de opinião e análise de sentimento com alta precisão (aferida por uma avaliação científica rigorosa), extração inteligente de tópicos, palavras-chave e entidades (tais como pessoas, locais, organizações) e outras formas de análise de notícias e comentários. A Trendzz oferece uma aplicação corporativa com interface web e também a assinatura de uma interface de programação (API) que permite que sua tecnologia seja utilizada por outros sites e aplicações.

Já a Tatem é o nosso conjunto de soluções para o mercado financeiro, especificamente para a administração de carteiras e fundos de investimento, tanto nacionais quanto off-shore. Os produtos da Tatem surgiram de uma parceria estratégica com a Gávea Investimentos, gestora de um dos maiores fundos de investimento do Brasil, e compõem uma plataforma integrada que cobre vários aspectos da gestão das carteiras, incluindo risco, compliance e inteligência.

Tatem e Trendzz ganharam o primeiro e segundo lugares de suas respectivas bancas (houve duas) na eliminatória regional em Belo Horizonte. Também foram para a final nossos grandes amigos do Anuncie Lá, que oferecem uma plataforma de anúncios para redes sociais como Orkut e Facebook – você anuncia para seus amigos e conhecidos.

Paulo Moura Jr. no stand da Anuncie Lá

Paulo Moura Jr. em seu stand da Anuncie Lá

Aliás, a qualidade das start-ups mineiras foi muito comentada durante o Desafio – diversas pessoas incluindo jornalistas e investidores me perguntaram a respeito dessa “efervescência” que viam em Minas Gerais. Respondi mencionando, dentre outros fatores, o excelente trabalho da Aceleradora, uma iniciativa para preencher o gap que existe entre o “paradigma tecnológico” dos empreendedores e o “paradigma financista” dos investidores: uma empresa não é feita apenas com tecnologia, e sem um business plan coerente não há como uma idéia inovadora sair do lugar. Muitos participantes do Desafio disseram, tanto para mim quanto para as suas bancas, que a maior dificuldade deles é administração, marketing e vendas, não tecnologia, e o trabalho da Aceleradora já ajudou muitas start-ups mineiras a se aprimorarem nesses aspectos.

Os dois dias do evento começaram com o demo pit, uma feira aberta ao público onde cada empresa demonstrava seus produtos aos visitantes, investidores e avaliadores. O demo pit também servia para as start-ups conhecerem umas às outras, e a troca de idéias, contatos e conversas informais sobre interesses em comum deram um clima descontraído e muito empolgante para o Desafio – mais do que apenas networking posso dizer que fiz algumas boas amizades por lá!

Cassio Pennachin (dir), da Tatem, visitando a Ningo, uma solução para pesquisar, comparar e comprar produtos de diferentes lojas.

Cassio Pennachin (dir), da Tatem, visitando a Ningo, uma solução para pesquisar, comparar e comprar produtos de diferentes lojas.

Na parte da tarde ocorriam as avaliações, com apresentações de 12 minutos seguidas por uma sessão de perguntas e respostas de quinze minutos para a banca de avaliadores, composta por investidores e profissionais experientes. Fiquei positivamente impressionado com a qualidade de várias apresentações, que incluíam a de empresas que não eram da área de tecnologia de informação, como a startup de biotecnologia ProBio (que desenvolveu um gel para remineralização óssea capaz de simplificar muito os implantes dentários, dentre outras aplicações). Eu estava preocupado com a minha apresentação – fico bem mais à vontade falando de tecnologia do que de business – mas consegui dar um bom ritmo e fui bastante elogiado.

Ao final do primeiro dia foram anunciados os 8 finalistas que iriam reapresentar no dia seguinte, dessa vez em inglês e para uma outra banca de avaliação. A Tatem foi uma das aprovadas para a final, mas a Trendzz ficou de fora, por uma boa razão: as duas empresas da sua banca que foram aprovadas terminaram em primeiro e segundo lugares do Desafio, colocação aliás merecidíssima.

Na apresentação em inglês dos 8 finalistas achei particularmente interessante como foram aprovados tanto empresas muito maduras, com planos de negócio bem-definidos e propriedade intelectual consolidada, e também start-ups com produtos promissores mas em estágios mais iniciais (como por exemplo os estudantes baianos da Tesla, que apresentaram uma impressora braille de baixo custo). Essa diferença no nível de maturidade das start-ups se refletia também na qualidade das apresentações; infelizmente o baixo domínio do inglês, aliado à fatores como ansiedade, prejudicou muito pelo menos um candidato. Em contraste, algumas apresentações, como a do quarto lugar Pligus e a da Tatem (feita pelo Cassio Pennachin, do Vetta Labs / IGenesis), chamaram a atenção pela fluência e desenvoltura.

Durante todo o Desafio todos os organizadores faziam questão de ressaltar que o resultado da competição propriamente dita não deveria ser encarado com muita rigidez: mencionou-se várias vezes que muitas empresas que participaram do Desafio nos anos anteriores receberam investimentos mesmo não tendo vencido a competição (como por exemplo os participantes de 2009 Navegg e Descomplica), e que a exposição e a expansão do networking eram tão ou mais importantes que a colocação em si. Ainda assim, competição é competição, e no final do evento todos estavam ansiosos pela divulgação dos vencedores, que foram:

Motofog, dos vencedores da Fumajet, em funcionamento

Motofog, da vencedora Fumajet, em funcionamento

  1. Fumajet, com o Motofog, um produto que se tornou a sensação do evento. Após assistir à apresentação (estavam na minha banca, no primeiro dia) eu fiquei tão impressionado que fui conversar com o time e dizer que tinha certeza de que o primeiro lugar era deles! Eles desenvolveram um kit para instalação em motos de 125 cilindradas (dessas comuns que se vê em todo lugar) que substitui o escapamento da moto por um sistema computadorizado para termonebulização de produtos para o combate aos mosquitos que transmitem doenças como a dengue e a malária. A moto se transforma numa alternativa de baixíssimo custo para o combate a essas doenças, capaz de circular em locais onde não é possível chegar com a caminhonete normalmente usada para esse fim (o chamado “carro fumacê”), e com um alcance e segurança muito maiores que o de um aplicador a pé. Além disso a moto pode ser utilizada sem modificações para a aplicação de defensivos agrícolas, tendo como foco os microagricultores.
  2. Vorsprung, com uma interessantíssima solução para a coleta e reutilização de água de chuva, que inclui uma CPU capaz de avaliar em tempo real a qualidade da água coletada e descartar a água contaminada por poluição e outras impurezas do início da chuva. Isso faz com que seja muito mais fácil o tratamento e o reuso da água limpa coletada após essa primeira descarga, trazendo uma grande economia especialmente para instalações industriais.  Fiquei muito feliz com a vitória dos extremamente simpáticos Pablo Garcia e Ricardo Joaquim, com quem passei várias horas conversando de diversos assuntos, indo de preparação de dragsters a videogames para auxiliar a reabilitação com fisioterapia!
  3. Taw Itech, que desenvolveu uma “lousa digital” para escolas e universidades, que se destaca pelo grande porte e inovações em usabilidade, e cujo principal componente é uma caneta eletrônica desenvolvida pela empresa. Um dos comentários dos avaliadores foi que a ausência de um vídeo demonstrando o uso da lousa na prática dificultou a compreensão do funcionamento, vantagens e inovações do produto, observação com a qual tenho que concordar.
  4. Pligus, um produto para videoconferência e colaboração on-line, já usado por diversas empresas, escolas e pessoas do mundo todo. A Pligus foi a única empresa voltada para a Internet dentre as quatro que seguem para a próxima etapa do Desafio, e me chamou a atenção pela apresentação fluida e pelo fato de tudo ter sido por um único desenvolvedor, Gustavo Scanferla, aluno de comunicação e marketing e que partiu de uma idéia que teve aos 17 anos.

A nossa Tatem, de que já falei antes, ficou em um excelente quinto lugar, e já se prepara para uma nova fase com a entrada de dois novos sócios, executivos experientes atuando no mercado financeiro.

A participação da Trendzz resultou em várias manifestações de interesse de executivos da área de marketing digital e de um investidor anjo, e elogios suficientes para me deixar empolgadíssimo com o empreendedorismo e a inovação no Brasil.

A todos que participaram do evento e da sua organização, em especial aos organizadores Rafael Matioli e Márcio Filho, da FGV, ao Yuri Gitahy e Jacques Chicourel, mentores da Aceleradora, e Diego Gomes, do ReadWriteWeb Brasil meus sinceros agradecimentos e meus parabéns!

Inovação, Negócios 4 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5,00 out of 5)

Introdução à Inteligência Artificial Genérica

Andróide IBMDurante a VIII Semana de Informática na PUC Minas São Gabriel, que ocorreu de 04 a 07 de maio deste ano (2010), eu tive prazer de ministrar uma palestra para os alunos sobre um tema bastante polêmico, atual e que fascina muita gente. Intitulada “Introdução à Inteligência Artificial Genérica”, a apresentação, que durou aproximadamente 1:40h, iniciou com uma breve revisão da origem/história da área Inteligência Artificial (IA) e com uma descrição das diversas ramificações que emergiram dentro da disciplina, desde o seu surgimento. Foram ilustrados alguns projetos que deram o pontapé inicial às sub-áreas de pesquisa (ramificações), como planejamento de ações e tomada de decisão, aprendizado de máquina, além de dar uma visão geral sobre o estado-da-arte da IA Genérica. Um dos principais objetivos da IA Genérica é a criação de sistemas computacionais para a resolução de problemas gerais, que exijam inteligência para serem solucionados. Projetos importantes como OpenCog, OpenNars, HTM, entre outros, foram apresentados ao público, que demonstrou bastante interesse, principalmente com a possibilidade de poder contribuir com os projetos livres e de código aberto, como o OpenCog. Mas eu tinha reservado uma surpresa para eles. Uma densa viagem através das idéias, teorias e previsões do inventor e futurista Ray Kurzweil, sobre a evolução tecnológica.

É complicado falar de Inteligência Artificial Genérica atualmente sem mencionar a Singularidade (tecnológica), que é um assunto para vários posts. Mas, de forma geral, podemos entender a Singularidade (tecnológica) como um momento na história da humanidade onde o progresso tecnológico acontecerá de forma tão acelerada, que será impossível prever o impacto desta evolução no mundo. O resultado será máquinas andando sobre a terra com o objetivo de exterminar a humanidade uma mudança permanente e irreversível na forma com que vivemos.

Kurzweil aponta três vertentes tecnológicas que levarão a humanidade à Singularidade: Genética, Nanotecnologia e Robótica (GNR). A Inteligência Artificial é aplicável a todas elas. Dessa forma, foi possível traçar um paralelo entre IA e cada uma delas, exemplificando com alguns trabalhos.

Exponencial vs Linear

Kurtzweil também fez diversas diversas previsões sobre o futuro da tecnologia, inclusive que a Singularidade ocorrerá por volta de 2044. É importante dizer que tais previsões são fundamentadas em um detalhado estudo, por ele realizado, sobre a evolução tecnológica. Tal estudo permitiu a definição de um modelo comportamental para o processo evolutivo da tecnologia. Diferentemente do que muitos pensam, o modelo é exponencial e não linear. Então, quando algum cientista afirma que somente teremos uma Inteligência Artificial, semelhante às vistas em filmes e livros de ficção científica, daqui a vários séculos, ele está usando um modelo linear para defender seu ponto de vista e não o proposto por Kurzweil. Assim, baseando-se na premissa de que a tecnologia evolui exponencialmente, Kurzweil vêm fazendo previsões desde a década de 1980, sendo que várias já se concretizaram conforme previstas. Por exemplo, a explosão da Internet no início dos anos 90 e a derrota do campeão humano de xadrez para um computador no final da década de 1990 (Kasparov foi derrotado pelo Deep Blue em 1997).

Se tudo ocorrer conforme previsto por Kurzweil, teremos, nas próximas décadas, sistemas computacionais capazes de realizar cópias da nossa mente para um meio digital, computadores emulando o cérebro humano, nano robôs navegando em nossa corrente sanguínea e se comunicando com sistemas computacionais externos para nos dar capacidades sobre-humanas (mais inteligência, mais velocidade, mais resistência, etc.)

Ciborgues já existem! (DARPA)

Cyborgs já existem! (DARPA)

Andróides também (Prof. Ishiguro - Osaka University)

Andróides também (Prof. Ishiguro - Osaka University)

Conforme mencionado anteriormente, foram apresentados ao público alguns projetos de Inteligência Artificial Genérica. Como funcionam, para que servem, suas aplicações, além de outros detalhes. O projeto mais detalhado foi o OpenCog, dado que nós aqui do Labs desenvolvemos diversos módulos que o compõe atualmente. O OpenCog é um framework que tem como objetivo a criação de um sistema computacional pelo menos tão inteligente quanto um humano. Ele reúne uma série de ferramentas para planejamento de ações, raciocínio e tomada de decisão, inferência, aprendizado de máquina, etc. Ele conta também com um módulo para a representação de um agente inteligente que possui um corpo físico e está situado em um ambiente físico qualquer. Alguns vídeos de demonstração do OpenCog em ação podem ser vistos em:

Video 1) Visualização da AtomTable
Video 2) Agente aprendendo
Video 3) Respondendo perguntas
Video 4) Resolução de anáfora

Para finalizar a apresentação, foram lançadas algumas questões acerca de uma provável última criação do homem, a super-inteligência. Esta, pois, seria a última, uma vez que uma super inteligência poderia inventar qualquer coisa e/ou resolver qualquer problema que somente um humano seria capaz de fazê-lo, porém de forma mais eficiente. A criação de uma segunda, terceira,.., enésima geração de super-inteligências ficaria a cargo das super-inteligências, dado que o homem “original” e obsoleto não teria capacidade de realizar tal atividade. Uso o termo “original” para denominar o homem sem modificações, ou seja, sem implantes cibernéticos, sem nano robôs e outros recursos que venham torná-lo sobre-humano. No final das contas, a utilização da tecnologia para acelerar o lento processo evolutivo biológico não é novidade, mas será cada vez mais perceptível nas próximas décadas.

Os slides da apresentação podem ser visualizados no Slideshare.

Inteligência Artificial 10 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5,00 out of 5)

Mobilidade de agentes

Inaugurando a minha participação no blog do Vetta Labs, vou falar um pouco sobre mobilidade de agentes inteligentes.

Meu interesse por essa área se confunde com o surgimento dos primeiros jogos isométricos com pathfinding. Inicialmente, eu podia perder horas tentando tapear um NPC para ver se ele era inteligente de verdade. Claro que, com o tempo, a inteligência artificial nos jogos ficou mais elaborada, e eu passei a correr para me manter vivo mesmo. :P

Algoritmos de pathfinding consistem, basicamente, em um ou múltiplos agentes com destino definido distribuídos em um ambiente (mapa) determinado. Sendo assim, o agente deve se deslocar pelo ambiente respeitando suas restrições de movimento e obstáculos dinâmicos ou estáticos até atingir seu objetivo. Geralmente o algoritmo faz um cálculo de custo de deslocamento para definir a melhor direção ou trajetória a seguir. Além disso, o ambiente pode ter inúmeras características, o que viabiliza ou não a utilização de algoritmos de pathfinding específicos.

Path Planning

Muitos dizem que nada melhor do que um A* para começar. De fato, trata-se de um dos algoritmos mais utilizados no planejamento de caminhos em jogos e robótica. Diversos frameworks, controladores e game engines possuem esse algoritmo embutido; porém, são bastante enriquecedoras a sua implementação e a de algumas variações (RTA*, IDA*, GAA*, etc).

Em 2008, participei da elaboração de um artigo para o SBGames, fazendo experimentos com algoritmos de busca online e offline para MMOs. O objeto do meu estudo foi o path planning do jogo Ultima Online, o qual considero o melhor MMORPG de todos os tempos.

Como fruto desse experimento, pude entender de forma mais clara o porquê dos problemas de gameplay no pathfinding dos NPCs do jogo: era uma questão de otimização de recursos computacionais. Sendo assim, foi muito interessante estudar como os algoritmos clássicos de inteligência artificial são adaptados para melhorar o desempenho dos servidores, algo bastante exigido nesse gênero de jogo.



Path Follow

Outra estratégia bastante utilizada na mobilidade de agentes é a definição de trajetórias baseadas em checkpoints seqüenciais, gerando um caminho virtual. O agente, por sua vez, possui um atuador que corrige a sua direção e minimiza o desvio em relação ao segmento de reta corrente para manter-se na trajetória. É uma solução comum para agentes de jogos de corrida e para controle de UAVs na robótica, pois permitem uma margem de erro em relação à trajetória ótima.



Vector Fields

Como o próprio nome diz, trata-se de um conjunto de vetores que sugerem uma direção e/ou velocidade a partir de determinada coordenada ou região. Tais vetores podem ser dispostos na forma de um grid uniforme ou dispostos nos centros de polígonos em uma malha geométrica.

Esses algoritmos são muito utilizados para mobilidade de agentes em robótica e simuladores de física de modo geral.


Nos jogos digitais, também podem ser utilizados para simular fenômenos naturais, como a atuação do vento na vegetação, por exemplo.



Voronoi Diagrams

Os diagramas de Voronoi foram desenvolvidos com o objetivo de decompor espaços a partir de um conjunto de pontos de referência. As bordas da decomposição são formadas por linhas eqüidistantes a pontos vizinhos.

Esse algoritmo possui inúmeras aplicações computacionais. Na mobilidade de agentes, é utilizado na simulação de espaços superlotados, pois as bordas dos espaços decompostos indicam os caminhos mais seguros a passar entre diversos obstáculos.


Observando as células dos diagramas de Voronoi, percebemos uma grande semelhança com estruturas orgânicas, o que, de fato, faz sentido. Diversas estruturas naturais podem ser reproduzidas computacionalmente a partir de modelos matemáticos. As asas de uma libélula também podem ser reconstruídas a partir de diagramas de Voronoi, assim como a fragmentação de corpos rígidos em simulações de física.


Boids

Com o objetivo inicial de simular o comportamento da revoada de pássaros, esse algoritmo é muito utilizado em sistemas multiagentes. O curioso nesse tipo de algoritmo é que as ações individuais desempenhadas pelos agentes resultam em um comportamento de grupo coeso. Sendo assim, podemos simular, também, cardumes, manadas, enxames, etc…

Cada agente nesse sistema pode efetuar três ações básicas: distanciamento, alinhamento e aproximação em relação ao centro de massa. Isso permite que o grupo se desloque em massa, na mesma direção, sem que haja colisões entre os agentes.



Considerações finais

Nesse post apresentei uma visão bastante resumida da mobilidade de agentes e como eles podem ser utilizados em áreas distintas. Opções não faltam para solucionar problemas diversos em planejamento de caminhos, porém, antes de escolher um algoritmo, é preciso colocar na balança alguns fatores como: consumo de recursos computacionais, tempo de resposta, margem de erro, gameplay, entre outros.

Espero que tenham gostado e até o próximo post. :)

Robótica 2 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 4,00 out of 5)

Aplicações de impressão tridimensional

Ano passado eu escrevi sobre impressoras tridimensionais, ou fabbers. Estas máquinas, capazes de criar objetos tridimensionais de diversos materiais a partir de projetos computadorizados, estão se tornando cada vez mais populares e já foram assunto até de uma breve história do Cory Doctorow, Print Crime (em inglês). Naquele post falei principalmente de equipamentos para impressão, e agora vou falar de algumas das aplicações mais bacanas dessa tecnologia.

A Shapeways é um marketplace que oferece impressão 3D sob demanda. Eles possuem uma galeria de objetos que você pode imprimir, com a possibilidade de personalizar o projeto em alguns casos. Os modelos disponíveis incluem brinquedos, jóias, esculturas, maquetes e muitos outros, como o cubo de Rubik abaixo. Você pode também criar seu próprio projeto 3D, e eles oferecem ferramentas para facilitar a modelagem. E você pode criar sua própria loja dentro do ambiente deles, vendendo seus projetos.

Cubo de Rubik da Shapeways

Cubo de Rubik da Shapeways

Outra aplicação útil é a fabricação sob demanda de peças de reposição para equipamentos que já não são mais fabricados. O comediante e apresentador de TV Jay Leno, por exemplo, tem uma coleção enorme de carros antigos, alguns com mais de um século de idade. Ele tem a própria oficina para manutenção da coleção e, quando precisa trocar uma peça de um carro muito antigo, como esse carro a vapor de 1907, ele usa um scanner 3D e uma impressora de metal para gerar a nova peça, com dimensões perfeitas.

Mas a aplicação até agora mais revolucionária é para medicina. A Organovo, uma startup de San Diego, California, criou uma bioimpressora para medicina regenerativa. A bioimpressora, que está sendo implantada em laboratórios de pesquisa em medicina regenerativa ao redor do mundo, já é capaz de produzir tecidos simples, como pele, músculos e pequenos vasos sanguíneos. Os planos dos cientistas da empresa são de, em menos de dez anos, produzir vasos sanguíneos para tratamento de infarto, eliminando a necessidade de pontes de safena. Com mais pesquisa, será possível contruir estruturas mais complexas e, talvez algum dia, órgãos artificiais.

Um kit Makerbot

Um kit Makerbot

E para quem quer brincar com essas impressoras como hobby, a Makerbot vende kits de impressoras, assim como os suprimentos para impressão. Os kits custam a partir de US$750,00, e são bem feiosos, mas a qualidade da impressão é razoável. Embora os resultados não se aproximem do que é possível com impressoras industriais, essas custam cem vezes mais…

Eu quero um brinquedo desses no dia das crianças ;-). O que você faria com um?

Biotecnologia, Inovação 0 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 4,00 out of 5)

Analisando o Twitter usando Árvore de Palavras

Nesse artigo vou comentar sobre mais um projeto de processamento de linguagem natural que desenvolvemos aqui na Vetta Labs: um analisador de textos baseado em árvore de palavras.

Comecemos do princípio: uma concordância é um tipo especial de índice, onde se mostram junto de cada palavra algumas palavras que aparecem antes e depois dela. A primeira concordância foi criada no século XII, para a Bíblia em latim, e é mais ou menos desse jeito:

Ocorrências de "alegria" na Bíblia

Ocorrências de "alegria" na Bíblia (clique para aumentar)

Uma concordância era algo incrivelmente útil – basicamente o equivalente ao Google daquela época! – e extremamente caro de se fazer: a primeira da Bíblia em latim exigiu o trabalho de 500 monges e a primeira concordância da Bíblia Hebraica levou 10 anos para ser concluída. Hoje em dia, é claro, ninguém mais dá tanta importância a esse tipo de índice porque é muito mais fácil realizar a busca eletronicamente.

Mas concordâncias ainda têm muita utilidade prática. A Fernanda Viégas, da IBM, fez uma palestra interessantíssima na TEDx São Paulo chamada Revolução Visual, onde ela demonstra uma forma de visualização de textos baseada em concordâncias e numa estrutura de dados bem conhecida na Ciência da Computação, a árvore de sufixos (introduzida nos anos 1970). Chamada WordTree, esta visualização tem como ênfase a exploração interativa de textos curtos (no máximo do tamanho da Bíblia), e está publicamente disponível no site ManyEyes.

Veja um exemplo, criado por mim:

WordTree da letra de "Construção", de Chico Buarque

WordTree da letra de "Construção", de Chico Buarque (clique para aumentar)

A implementação da WordTree no ManyEyes me chamou a atenção, mas não se mostrou útil para mim por uma série de razões:

  • a quantidade máxima de texto suportada é centenas de vezes menor do que a que gostaria de processar
  • a WordTree não permite que voltemos ao trecho original do texto
  • qualquer texto e visualização submetida é obrigatoriamente público, o que impede o processamento de dados confidenciais
  • o uso é sempre interativo, não sendo possível o processamento em lote ou automático
  • não é permitido o uso do ManyEyes em aplicações comerciais
Resolvi, então, criar minha própria implementação de concordância baseada em árvore de sufixos. A idéia não é simplesmente explorar visualmente um texto específico, mas gerar automaticamente árvores de palavras a partir de itens do Twitter.

A motivação é simples: um dos mecanismos mais interessantes do Twitter é o Re-Tweet, ou RT, que é o gesto de alguém repetir o que foi postado por outra pessoa, como forma de manifestação de apoio (ao fazer RT de um item no Twitter você está divulgando aquele item para as pessoas para seus seguidores). Quanto maior o número de RTs mais divulgação um determinado item teve.

O sistema monitora o Twitter em tempo real, buscando itens com as palavras chave determinadas pelo usuário. Todos os dias (ou, por exemplo, a cada 1000 twits encontrados) uma nova árvore é gerada, que ilustra de forma bem interessante o que tem sido discutido a respeito daquele assunto. Veja um exemplo, gerado enquanto escrevia esse artigo a partir de twits a respeito do Campeonato Mineiro (nada contra o time do Atlético!):

Árvore gerada por twits do Cruzeiro

Árvore gerada por twits do Cruzeiro

Como a quantidade de textos processada é enorme – dezenas de milhares de itens por dia! – árvores de palavras geradas de forma ingênua são gigantescas. Para exibir apenas as informações relevantes, utilizamos técnicas de processamento de linguagem natural para podar a árvore.

Por exemplo, podemos exigir que determinados nós sempre contenham verbos, ou apenas sentenças em que a palavra escolhida funcione como sujeito sejam consideradas. Tudo isso, é claro, configurável e acessível através de uma interface web, com tudo a que o usuário tem direito (feeds RSS, interface AJAX, exibição de estatísticas a respeito de como a árvore foi construída, links para os itens originais…).

E como o assunto da vez são as Eleições 2010, vejam alguns exemplos, também produzidos nesse exato momento:

Árvore produzida por menções a Aécio Neves no Twitter

Árvore produzida por menções a Aécio Neves no Twitter

Também podemos gerar árvores reversas, que mostram o que precede determinada palavra, e árvores com maior profundidade, como exemplificado abaixo:

Árvore reversa (Aécio Neves no Twitter)
Árvore reversa (Aécio Neves no Twitter)

O mais interessante (e divertido!) disso tudo é que essa técnica de visualização permite ter uma avaliação instantânea do que “está rolando no Twitter”, em poucos segundos. Uma árvore de palavras condensa informação de milhares de itens e a exibe de forma intuitiva e direta – algo realmente raro num mundo em que a sobrecarga de informação é cada vez maior.

Data Mining, Internet, Linguagem Natural, Redes Sociais, Usabilidade, Visualização Cientifica, Web 2.0 11 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (4 votes, average: 4,75 out of 5)

Extração Inteligente de Palavras-Chave

Aqui na Vetta Labs desenvolvemos algumas tecnologias baseadas no processamento de linguagem natural, como já comentei em outro artigo. Hoje vou falar de uma nova aplicação que produzimos recentemente, que tem duas características bem interessantes: uma é suportar tanto textos em inglês quanto em português (o que é bastante incomum, já que as particularidades de nossa língua nem sempre são compatíveis com as técnicas mais conhecidas); a outra é que os resultados produzidos são muito fáceis de serem utilizados na prática, de forma simples, em por exemplo blogs e portais de conteúdo.

É comum sites associarem aos seus artigos frases ou palavras-chave relacionadas ao conteúdo. Essas palavras-chave podem funcionar como resumos do que é discutido, levar o usuário a outros artigos que tratam dos mesmos assuntos e também ajudar na categorização e indexação dos textos. Normalmente essas frases ou palavras-chave são escolhidas pelo próprio autor, ou então definidas pelos visitantes, de forma colaborativa (o que exige um grande número de visitas e “votos” para evitar resultados de baixa qualidade ou sem sentido).

O problema é que muitas vezes já temos uma grande coleção de textos sem palavras-chave definidas, e escolhê-las manualmente  é uma tarefa extremamente árdua.  Existem algumas ferramentas simples para detecção automática de palavras-chave, mas praticamente todas elas usam uma abordagem ingênua que dificilmente funciona bem: são usados dicionários, tabelas com palavras-chave pré-definidas, e  a aplicação simplesmente verifica se a palavra-chave na lista aparece no artigo. Essa alternativa é inútil se os artigos em questão são sobre assuntos pouco comuns, ou se as palavras-chave que desejamos são termos menos conhecidos.

Esse exatamente era o problema de dois dos nossos clientes: a h+ Magazine, uma revista eletrônica sobre trans-humanismo, singularidade e outras tendências tecnológicas e culturais, e o Ceticismo Aberto, um dos maiores sites do Brasil sobre ceticismo e divulgação científica.

Keywords through cyberspace (Digital Composite)

A solução que desenvolvemos utiliza técnicas de processamento estatístico de linguagem natural e aprendizado de máquina para extrair automaticamente frases e palavras-chave de milhares de artigos desses sites. As palavras-chave encontradas incluem neologismos, expressões, nomes próprios e termos obscuros que jamais apareceriam nos resultados de uma abordagem baseada em listas, e são automaticamente inseridas nos sistemas de gestão de conteúdo dos sites (baseados em WordPress e Drupal), permitindo seu uso imediato.

Nosso sistema inicialmente identifica frases ou palavras-chave candidatas criando sequências de até três ou quatro palavras. Cada candidata então é analisada, extraindo-se características como:

  • frequência no uso geral (palavras extremamente comuns não são importantes)
  • frequência no texto (palavras repetidas no artigo têm peso maior)
  • posição no texto (palavras no início ou no final do texto costumam ser mais representativas)
  • categoria gramatical (substantivos têm mais peso que preposições, por exemplo)
  • função sintática (frases sintaticamente incorretas ou incompletas são rejeitadas)
  • entidades ou lugares representados (o sistema identifica nomes próprios como Albert Einstein, Zumbi dos Palmares, Belo Horizonte ou São Luís do Paraitinga)

Note que combinar todas as essas informações extraídas e decidir se determinada candidata é ou não uma frase ou palavra-chave é uma tarefa complicadíssima. Para resolver esse problema, usamos um método de aprendizado supervisionado: utilizamos um pequeno número de artigos (em torno de 50 ou 100) que já tinham suas palavras-chave definidas manualmente pelos autores como exemplos positivos. Um algoritmo de aprendizado supervisionado analisa as informações acima dos exemplos positivos dados e aprende a identificar as palavras-chave, automaticamente. O interessante é que o modelo obtido é capaz de generalização, ou seja, apesar de ter aprendido “estudando” apenas 100 artigos ele é capaz de aplicar de forma correta as mesmas regras para artigos inéditos.

E os resultados são surpreendentes – às vezes é difícil convencer as pessoas de que as palavras-chave foram escolhidas automaticamente e não por uma pessoa capaz de ler e interpretar cada um dos artigos!

Notas

A nova versão do Ceticismo Aberto, já com as palavras-chave extraídas pelo sistema da Vetta Labs, entrou no ar no domingo 21 de Fevereiro, e a versão em inglês, para a h+ Magazine, deve ser disponibilizada publicamente em breve.

O projeto foi desenvolvido por Fabrício Aguiar (que já fez com a gente outras aplicações interessantes baseadas em linguagem natural), a partir de código escrito por Murilo Queiroz (que também coordenou o desenvolvimento) e diversos projetos de software livre, incluindo o WekaKEAOpenNLP, CoGrooRembrandt e OpenCalais.

Os arquivos de treinamento usados na versão para português foram criados  por Kentaro Mori, do Ceticismo Aberto, e muitas das idéias foram sugeridas inicialmente pelo Dr. Ben Goertzel.

Inteligência Artificial, Linguagem Natural 7 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5,00 out of 5)

Mineração de Opinião

É notável o crescimento da quantidade de informação disponível na Web nos últimos anos. Além dos conteúdos disponibilizados por empresas de notícias, os usuários passaram a compartilhar na Web seus conhecimentos, críticas e opiniões em blogs pessoais, sites de relacionamentos, microblogs, dentre outros meios. Com esse aumento da participação dos usuários nos conteúdos da Web, surgiu também uma nova área de pesquisa relacionada ao Processamento de Linguagem Natural, chamada de Mineração de Opinião e também conhecida como Análise de Sentimento.

A Mineração de Opinião visa identificar o sentimento que os usuários apresentam a respeito de alguma entidade de interesse (um produto específico, uma empresa, um lugar, uma pessoa, dentre outros) baseado nos conteúdos divulgados na Web. O objetivo principal é permitir que um usuário obtenha um relatório contendo o que as pessoas andam dizendo sobre algum item sem precisar encontrar e ler todas as opiniões e notícias a respeito.

Existem diversas aplicações para o uso da Mineração de Opinião, sendo algumas listadas abaixo:

  • análise de empresas na bolsa de valores: quem acompanha nosso Blog deve se lembrar do projeto stockmood.com, cujo objetivo é identificar o humor do mercado em relação às empresas negociadas na bolsa de valores baseado nas opiniões dos analistas, com o intuito de identificar a tendência dos preços das mesmas;
  • análise de um produto: uma empresa pode ter interesse na opinião dos usuários sobre um determinado produto. Por exemplo, a Apple (ou uma concorrente) pode realizar uma mineração de opinião para saber o que as pessoas andam dizendo sobre o iPhone 3G. Esses resultados podem ser usados com o intuito de melhorar os produtos ou mesmo para identificar estratégias de marketing. Uma aplicação desse tipo chamada Sentweet foi desenvolvida aqui no Labs para classificar a opiniões postadas no microblog Twitter;
  • análise de lugares: uma pessoa que vai viajar pode utilizar as opiniões de outras sobre o lugar pretendido para planejar o roteiro da viagem, evitando passeios desinteressantes;
  • análise de políticos: os eleitores podem identificar qual a opinião de outros eleitores sobre um determinado candidato político;
  • análise de filmes e jogos: também é possível minerar a opinião sobre filmes e jogos eletrônicos;

Basicamente, os passos envolvidos no processo de mineração de opinião são:

  1. coleta de conteúdos: visa buscar na Web conteúdos sobre o item de interesse, e também identificar se esse conteúdo é relativo a um fato ou uma opinião. Fatos devem ser descartados, já que o interesse  é nas opiniões dos usuários;
  2. classificação: a polaridade do conteúdo recuperado deve ser identificada. Geralmente, as polaridades usadas são positiva, negativa ou neutra;
  3. sumarização dos resultados: as classificações das diversas opiniões devem ser sumarizadas para o usuário, com o intuito de facilitar o seu entendimento sobre as mesmas. Essa sumarização pode ser em forma de texto ou gráfico.

O passo de coleta dos conteúdos está relacionado com recuperação da informação. Porém, deve utilizar técnicas mais avançadas capazes de identificar se o conteúdo é uma opinião ou um fato, o que não é uma tarefa trivial. No entanto, nem todo fato deve ser descartado, já que mesmo fatos podem conter algum tipo de opinião, e vice-versa. Essa distinção é importante para se ter uma acurácia maior no passo seguinte, de classificação.

Basicamente, a etapa de classificação dos conteúdos pode ser realizada com três técnicas diferentes, que são brevemente descritas abaixo:

  • aprendizagem de máquina: essa técnica requer que um conjunto de conteúdos seja previamente classificado para servir de base para o treinamento do modelo. A partir desse modelo treinado, novos conteúdos são classificados. Uma vantagem dessa abordagem é a utilização de algoritmos já consolidados e eficientes. Como desvantagens, podemos citar a necessidade do conjunto ser classificado para treinamento e que, para diferentes tópicos, diferentes conjuntos de treinamento são necessários. Por exemplo, um modelo treinado com um conjunto de conteúdos relacionados ao mercado financeiro não é adequado para classificar conteúdos sobre política;
  • seleção de palavras: essa abordagem envolve avaliar as palavras dos conteúdos e identificar aquelas positivas e negativas com base em uma lista de palavras previamente selecionadas. Com isso, é possível executar algoritmos para classificar o conteúdo como positivo, negativo ou neutro. Vantagens dessa técnica são a sua simplicidade e o fato de ser desnecessário classificar documentos previamente para treinamento, como na abordagem anterior. No entanto, o conjunto de palavras positivas e negativas deve ser selecionado e deve ser específico para cada tópico;
  • análise sintática: essa abordagem envolve analisar o conteúdo sintaticamente, identificando adjetivos e/ou advérbios (principalmente) que podem indicar polaridades dos textos. Como vantagem dessa abordagem, pode-se citar não ser necessário classificar previamente um conjunto de textos.   Porém, ela requer um analisador sintático eficiente e que os conteúdos sejam compostos por sentenças sintaticamente corretas.

Essas três abordagens podem ser adotadas em conjunto, formando um modelo híbrido, para tentar aumentar a acurácia da classificação.

O último passo, de sumarização dos resultados, pode ser apresentado de forma textual ou gráfica. A sumarização em forma de texto não é uma tarefa trivial, e é um tópico de pesquisa por si só. Ela envolve geração de linguagem natural com base em diversos conteúdos e existem várias propostas de pesquisadores para tal. Porém, ainda é um tópico em aberto, com várias dificuldades para serem enfrentadas. A sumarização em forma de gráfico é mais simples, e exige somente que uma forma fácil de ser lida e interpretada seja adotada.

Existem diversos desafios na área que devem ser tratados para que a mineração de opinião seja obtida com uma acurácia representativa. Várias dessas dificuldades estão relacionadas ao processamento de linguagem natural, que está diretamente  relacionado à mineração de opinião. Abaixo são descritas alguns desses desafios:

  • não é trivial distinguir se um texto é opinião ou fato, e principlamente identificar em um fato se existem opiniões embutidas;
  • textos podem conter sarcasmos e ironias, o que também não são fáceis de serem identificados e podem impactar os resultados;
  • um texto pode referenciar mais de um item de interesse (pode citar iPhone e iPod) com opiniões diferentes sobre os itens, o que pode confundir a classificação;
  • uso de pronomes para referenciar itens pode dificultar a identificação de sentenças que mencionam o item de interesse;
  • textos com palavras escritas erradas e com sentenças sintaticamente mal formadas (o que é bastante comum nos Blogs e redes sociais atualmente) dificultam a busca e classificação dos mesmos;
  • uso de termos do “Internetês”, como por exemplo “vc”, “fds” e “:)”, devem ser considerados no vocabulário;
  • propaganda disfarçada, em que blogueiros recebem dinheiro para falar bem de alguma empresa ou produto pode impactar os resultados.

Podemos perceber que a mineração de opinião é uma tendência da web com diversas aplicações interessantes, dado o grande número de dados disponibilizados pelos usuários. Porém, não é uma tarefa trivial de ser realizada, já que envolve vários desafios como os descritos nesse post. Esperamos que um dia seja possível termos um sumário automático das opiniões divulgadas pelos diversos internautas, com uma qualidade alta para nos ajudar nas diversas tomadas de decisões sobre os mais diferentes temas.

Data Mining, Linguagem Natural 2 Comentários

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5,00 out of 5)

« Previous Entries