sexta-feira, 10 de outubro de 2014

pgAFIS: o Elefante Biométrico

Tecnologias biométricas são cada vez mais empregadas em aplicações civis. Um exemplo disso é que nas eleições deste ano, 21,6 milhões de brasileiros (15% do total de eleitores do país) em 762 municípios (entre eles 15 capitais) deverão usar a biometria nas urnas eletrônicas, visando reduzir os riscos de erros, fraudes e lentidão.


Na Índia, uma iniciativa pioneira do governo promete criar o maior banco de dados biométricos do mundo. No país existem mais de meio bilhão de pessoas que não possuem qualquer espécie de identificação, o que torna impossível a elas receber auxílios governamentais, abrir conta em banco, solicitar empréstimos, obter carteira de motorista, entre outros. Com a expectativa de cadastrar os dados biométricos de mais de um milhão de pessoas ao dia, o projeto espera ter até o final do ano os registros dos 1,2 bilhão de indianos em seu banco de dados.


Diante disso, ao vasculhar sobre o tema, descobri que os códigos fontes de rotinas biométricas FBI/NIST são públicos. Tais rotinas são o coração dos sistemas AFIS (Automatic Fingerprint Identification System), e dentre elas duas se destacam: o extrator de características (feature extractor) e o comparador de minúcias (matcher).


Estudando esse código do NIST, em linguagem C, resolvi criar o suporte a tais funcionalidades de forma nativa no meu SGBD preferido, o PostgreSQL. E assim nasceu o pgAFIS (Automated Fingerprint Identification System support for PostgreSQL), um módulo capaz de fornecer funcionalidades de extração de características e comparação de minúcias a partir de instruções SQL dentro do PostgreSQL.

Mas como funciona isso na prática?

Bem, comecemos pela modelagem de dados. É preciso criar uma tabela em que sejam armazenadas as informações das impressões digitais, tal como descrito a seguir:

Table "public.fingerprints"
 Column |     Type     | Modifiers 
--------+--------------+-----------
 id     | character(5) | not null
 pgm    | bytea        | 
 wsq    | bytea        | 
 mdt    | bytea        | 
 xyt    | text         | 
Indexes:
    "fingerprints_pkey" PRIMARY KEY, btree (id)
  • "pgm" guarda imagens originais das impressões digitais (PGM)
  • "wsq" guarda imagens comprimidas das impressões digitais (WSQ)
  • "mdt" guarda os templates das digitais do tipo XYTQ em formato binário (MDT)
  • "xyt" guarda os dados das minúcias das digitais em formato textual
O tipo de dados usado nessas colunas é o "bytea" (um array de bytes), similar ao BLOB em outros SGBDs. Os formatos PGM e WSQ são abertos e muito conhecidos no mercado. Já o formato MDT eu que inventei. :D

Em seguida, as impressões digitais devem ser obtidas em formato cru (raw) e armazenadas na coluna "pgm" dessa tabela. O formato PGM é uma espécie de bitmap (mapa de bits), onde não existe compressão. Os leitores de impressão digital gravam arquivos obtidos com esse formato.


Agora é que o pgAFIS entra em cena! Uma função é capaz de converter os dados binários de um conteúdo PGM no formato WSQ (uma espécie de JPEG criado pelo NIST/FBI). Isso é feito com a execução dessa instrução SQL:

UPDATE fingerprints
SET wsq = cwsq(pgm, 2.25, 300, 300, 8, null);

A segunda etapa em que age o pgAFIS é na extração das características locais das impressões digitais (as minúcias) a partir do conteúdo WSQ. O resultado são as informações do tipo XYTQ (coordenadas horizontal e vertical, ângulo de inclinação e qualidade) de cada minúcia. Novamente, basta executar uma instrução SQL:

UPDATE fingerprints
SET mdt = mindt(wsq, true);

Para ter uma ideia de volume: imagens de impressões digitais em formato PGM de 300x300 pixels de 90 kB ao serem comprimidas no formato WSQ ocupam 28 kB de espaço. Ao extrair as minúcias e gerar o respectivo conteúdo no formato MDT (específico do pgAFIS), esse ocupa míseros 150 bytes! A versão textual do MDT, em XYT, ocupa um pouco mais: cerca de 300 bytes!

afis=>
SELECT id,
  length(pgm) AS raw_bytes,
  length(wsq) AS wsq_bytes,
  length(mdt) AS mdt_bytes,
  length(xyt) AS xyt_chars
FROM fingerprints
LIMIT 5;

  id   | pgm_bytes | wsq_bytes | mdt_bytes | xyt_chars 
-------+-----------+-----------+-----------+-----------
 101_1 |     90015 |     27895 |       162 |       274
 101_2 |     90015 |     27602 |       186 |       312
 101_3 |     90015 |     27856 |       146 |       237
 101_4 |     90015 |     28784 |       154 |       262
 101_5 |     90015 |     27653 |       194 |       324
(5 rows)

Tais processos fazem parte da etapa de obtenção dos dados biométricos, representada na figura abaixo:


Muito legal, mas fazemos o quê com esse monte de dados binários? As comparações biométricas!

Os sistemas biométricos são capazes de realizar duas operações essenciais de comparação: verificação e identificação.

Na verificação, também chamada de autenticação ou busca [1:1], uma impressão digital de amostra é comparada contra uma única digital já armazenada no banco de dados. Tal processo pode ser visualizado na figura abaixo:


E eis que o pgAFIS ataca novamente! Com ele, essa operação também pode ser realizada através de uma simples instrução SQL:

SELECT (bz_match(a.mdt, b.mdt) >= 20) AS match
FROM fingerprints a, fingerprints b
WHERE a.id = '101_1' AND b.id = '101_6';

Nessa instrução, a impressão digital identificada como "101_1" é comparada à "101_6". Caso o nível de similaridade entre as duas seja pelo menos 20, podemos considerar que ambas são iguais, ou seja, referem-se ao mesmo dedo de uma mesma pessoa. Trata-se de um procedimento rápido, pois a identificação da pessoa é informada no início e o sistema precisa apenas retornar um valor lógico: "sim" ou "não".

Já a identificação ou busca [1:N] é um processo custoso para o sistema, uma vez que uma impressão digital de amostra deve ser comparada contra todos os registros existentes no banco de dados biométricos. Além disso, o retorno é um conjunto de possíveis identificações encontradas no banco, ou seja, as consideradas mais similares à amostra segundo o algoritmo de comparação. Esse processo pode ser visualizado na figura abaixo:


Mesmo com essa ressalva de que o processo pode onerar o servidor, o pgAFIS oferece um recurso para lidar com esse risco: a limitação no número de possíveis suspeitos. Em linguagem SQL, um exemplo de busca seria assim:

SELECT a.id AS probe, b.id AS sample,
  bz_match(a.mdt, b.mdt) AS score
FROM fingerprints a, fingerprints b
WHERE a.id = '101_1' AND b.id != a.id
  AND bz_match(a.mdt, b.mdt) >= 23
LIMIT 3;
Nesse exemplo, são retornadas as três impressões digitais que mais se assemelham à identificada como "101_1".

Gostou? Divirta-se! Contribua! Os códigos estão disponibilizados no GitHub: https://github.com/hjort/pgafis.


quinta-feira, 12 de setembro de 2013

TV Serpro - Conectado: banco de dados espaciais PostGIS

Na primeira edição do programa Conectado da TV Serpro, discuto sobre o funcionamento do banco de dados espaciais PostGIS.