pgAFIS: Biometric Elephant

Biometric technologies are increasingly used in civilian applications. One example is that in the 2014 elections, 21.6 million Brazilians (15% of the country's voters) in 762 municipalities (including 15 capitals) should use biometrics in electronic voting machines in order to reduce the risk of errors, fraud and slowness.

In India a government pioneering initiative promises to create the largest biometric database in the world. In the country there are over half a billion people who lack any kind of identification, making it impossible for them to receive government aid, open bank accounts, apply for loans, get a driver's license, among others. Expecting to register the biometric data of more than one million people a day, the project hopes to have by the end of 2014 the records of all 1.2 billion Indians in its database.

Thus, while scratching on the subject, I found out that the sourcecodes of biometric routines from FBI/NIST are public. Such routines are the heart of AFIS (Automatic Fingerprint & Identification System), among which two algorithms stand out: the characteristics extractor (feature extractor) and the comparator of minutiae (matcher).

After studying this NIST code (in C language), I decided to create support for such features natively on my favorite DBMS, PostgreSQL. And so it was born pgAFIS (Automated Fingerprint Identification System support for PostgreSQL), an extension capable of providing feature extraction and minutiae comparison from SQL statements within PostgreSQL.

But how does that work in practice?

Well, let's start by data modeling. You'll need to create in the database a table in which information of fingerprints will be stored, as described below:

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" stores fingerprints raw images (PGM)
• "wsq" stores fingerprints images in a compressed form (WSQ)
• "mdt" stores fingerprints templates in  XYTQ  type in a binary format (MDT)
• "xyt" stores fingerprints minutiae data in textual form

The data type used in these columns is "bytea" (an array of bytes), similar to BLOB in other DBMSs. PGM and WSQ formats are open and well-known in the market. On the other hand, MDT is a format I created. :D

Therefore, fingerprints images may be obtained in raw format and stored on "pgm" column in that table. PGM format is a kind of bitmap, where there is no compression. Fingerprint readers usually store image files using this format.

Now pgAFIS comes into play! A particular function is able to convert the binary data from a PGM content into a WSQ format (a kind of JPEG created by NIST/FBI). This is done by running this SQL statement:

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

The second step where pgAFIS acts is the extraction of the fingerprints local characteristics (the minutiae) from the WSQ content. The result is the information in XYTQ type (i.e., horizontal and vertical coordinates, slope angle and quality) of each minutia. Again, you'll only need to execute a single SQL statement:

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

To get an idea of storing volume: fingerprint images in the PGM format of 300x300 pixels of 90 kB, when compressed in the WSQ format occupy 28 kB of disk space. After extracting minutiae and generating the content in the MDT format (specific to pgAFIS), that data occupies measly 150 bytes! The textual version of MDT, XYT, takes a little more: about 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)

These processes are part of the of biometrics Retrieve of biometrics represented in the figure below:

Very cool, but what we do with this pile of binary data? Biometric comparisons!

Biometric systems are able to perform two essential comparison operations: Verification and Identification.

In Verification, also called Authentication or [1:1] Search, a sample fingerprint is compared against a single fingerprint already stored in the database. This process can be seen in the figure below:

And that's where pgAFIS strikes again! With this extension, this operation can also be performed through a simple SQL statement:

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';

In this statement, the fingerprint identified as "101_1" is compared to "101_6". If the level of similarity between the two is at least 20, we can consider that both are equal, that is, refer to the same finger of the same person. It is a quick procedure, because the identification of the person is given at the start and the system only needs to return a boolean value: "yes" or "no".

Oppositely, Identification or [1:N] Search is a costly process for the system, since a sample fingerprint must be compared against all existing records in the biometrics database. In addition, its feedback is a set of possible identifications found in the database, that is, those considered most similar to the sample according to the comparison algorithm. This process can be seen in the figure below:

Even with this exception that the process may adversely affect the server, pgAFIS provides a feature to handle this risk: the limitation on the number of possible suspects. In SQL, a search example would be like this:

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;

In this example, the three fingerprints that more resemble the one labeled "101_1" are returned.

Did you enjoy it? Have fun with it! Contribute! Source codes are available on GitHub at https://github.com/hjort/pgafis.

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.