Análise de Voz e Vídeo
Reconhecimento de voz baseado em
modelos de palavras conectadas
André Vitor de Almeida Palhares
Roteiro
•
•
•
•
•
•
•
•
•
Introdução
Formalizando o problema
Two-level DP algorithm
Level building algorithm
One-state algorithm
Varias strings candidatas
Resumo dos algoritmos
Segmentação
Implementação
Introdução
• O reconhecimento da voz não é feito através
de palavras ou frases isoladas
• Antes as palavras eram entidades completas
– Poderiamos apenas encontrar o melhor
alinhamento de cada diferente palavra com a
entrada
• Não há uma distinção clara entre duas
palavras
Introdução
Introdução
• Exemplos
– Reconhecimento de strings derivadas de
vocabulários de tamanho pequeno-médio
– Strings de dígitos
– Sequencias de letras
Introdução
• O problema:
• Ri são palavras do vocábulario de v palavras
• T é uma string de palavras dividida em frames
t(1), t(2), ..., t(M)
Introdução
• Dada uma sequência de palavras faladas
fluentemente, qual o casamento ótimo que
existe pela concatenação de palavras do
vocábulário
• Problema de otimização
– Geralmente não se sabe o número de palavras L
– Não se sabe onde as palavras terminam/começam
– Não podemos resolver o problema de maneira
exaustiva (VL possibilidades)
Formalizando o problema
• Padrão de teste T = {t(1), t(2), ..., t(M)}, cada
t(m) é algum vetor spectral
• Ri palavras de um vocabulário de V palavras:
Ri = {ri(1), ri(2), ..., ri(Ni)}
• Devemos encontrar R*, uma sequência de
concatenação de palavras Ri que melhor casa
com T. Supondo que L seja o numero de
palavras em R*, temos:
• R* = {Rq*(1) Rq*(2)... Rq*(L)}
Formalizando o problema
• Para determinar R* (a melhor solução), vamos
construir um Rs arbitrário, da forma:
• Rs = {rs(1), rs(2),..., rs(Ns)}, onde Ns é a sua
duração total
• A distância entre Rs e T dada pelo DTW é:
• Onde d(.,.) é uma distancia spectral local, w(.)
é a função de warping
Formalizando o problema
Formalizando o problema
• Assim, devemos minimziar a funçao de
distancia e obter a menor distancia D*:
• O número de computações necessárias pra
esse cálculo é muito alto
• M = 300 frames, L = 7 palavras, 40 frames por
palavras em média e V = 10 palavras, teriamos
cerca de 3*1011 computações.
Two-level DP algorithm
• Quebra a computação da minimização em
dois estágios.
• No primeiro, casa cada palavra Rv com uma
porção arbitrária da string T:
– Cada palavra é casada com todas as combinações
possíveis de b, frame onde ela iniciaria e e, frame
onde ela terminaria. Assim, computariamos:
Two-level DP algorithm
• Assumindo um nivel de expansão/compressão
de no máximo 2, teríamos:
• A partir daí, podemos escolher a melhor Rv
entre quaisquer dois índices b e e:
Two-level DP algorithm
• Para a segunda fase do two-level dp, temos
que juntar de maneira ótima os melhores
mínimos entre os frames, minimizando a
distancia acumulada.
• Isso pode ser feito utilizando-se de
programaçao dinâmica
Two-level DP algorithm
• Para um último frame e de uma sequência de l
palavras, temos a menor distância dada por:
• Isto é, o melhor caminho de l palavras que
termina no frame e é aquele que tem a menor
distância entre todos os frames de início b,
concatenado com o melhor caminho de l-1
palavras que termina em b-1
Two-level DP algorithm
• Passo 1 – inicialização
• Passo 2 – Loop em e para l = 1
• Passo 3 – Recursão, loop em e pra l = 2,...,Lmax
• Passo 4, solução final
Level Building Algorithm
• O procedimento geral de alinhamento de um Rs
com um padrão de teste T pode ser visto da
seguinte maneira:
• Nesse caso, o alinhamento é feito frame a frame.
Level Building algorithm
• Uma maneira alternativa de computar esse
alinhamento é ao inves de alinhar frame a
frame, é alinhar fixando um nível horizontal
(que corresponde ao fim da primeira palavra
de Rs
• Este procedimento é iterado para todos os
frames num determinado intervalo e é
determinado que frames sao alcançados no
proximo nível (proxima palavra de Rs)
Level Building algorithm
• Para um único Rs, os procedimentos são análogos. Mas, no
caso do level building, podemos computar o alcance do
proximo nivel para todas as V palavras distintas antes de
computar o proximo nível
Level Building algorithm
• Diferença entre o two-level DP e o LB
– No LB, fazemos V warps por nivel, resultando em
V*L warps no total
– no two-level DP, fazemos um time warp pra cada
frame, tendo entao V*M time warps
• Como em geral M(o numero de frames) é bem
maior que L(o numero de palavras), ganhamos
em eficiencia
Level Building algorithm implementação
• Seja
a menor distância acumulada, no nível
l, usando o padrao Rv ao frame m do padrão de
teste.
• Iniciamos o algoritmo para o nível 1:
• R1 é alinhado com o início de T, com um DTW
padrão e o seu último frame é alinha-se com m,
dado num intervalo m11(1) <= m <= m12(1).
Guardamos
.
• Fazemos o mesmo com todos os padrões Rv,
obtendo as distancias abaixo:
Level Building algorithm implementação
• Assim, podemos definir o menor e o maior
intervalos para o proximo nivel da seguinte
maneira:
Level Building algorithm implementação
Level Building algorithm implementação
• Guardamos também os seguintes valores:
– Melhor distancia no level l para o frame m
– Indice da palavra que deu a distância acima
– Ponteiro para o melhor frame final do nível anterior
que leva a
• Com apenas estas informações, podemos
encontrar ainda o melhor alinhamento.
Level Building algorithm implementação
• A partir do nível 2, realizamos os mesmos
procedimentos do nível 1, porem agora há
varios frames dos quais podemos partir:
Level Building algorithm implementação
• Continuamos o algoritmo até atingir o nível Lmax e
assim obtemos a melhor solução D*, dada por:
• Um contra do algoritmo é que ele é sincronizado
atraves dos níveis e nao através dos
frames(quando se passa um nível, provavelmente
se acessa um frame ja computado). Assim, é
dificil implementar uma versao que funcione em
tempo real.
Level Building algorithm - exemplo
• Vocabulário dado por duas palavras: A e B
• Procuramos a solução com l = 4 níveis
Level Building algorithm – vários níveis
• Assumindo expansão/compressão no DTW de
no máximo 2, as restrições dadas pelas linhas
de máximo e mínimo são:
Level Building algorithm – vários níveis
• Podemos reduzir ainda mais computações
desnecessárias com o seguinte esquema de
restrições:
Level Building algorithm
• Ainda podemos melhorar o algoritmo LB em
diversos aspectos, utilizando algumas
técnicas:
– Reduzir o range para o início de cada nível
– Reduzir o range global
– Variar o range do final do padrão de teste T,
fazendo-o assim mais robusto
– Integrar uma gramática (através de uma máquina
de estados, por exemplo), que permita diminuir o
número de vocabulários por nível
One-state algorithm
• A idéia básica do algoritmo one-state é dada
pela figura abaixo, com o frame de teste T no
eixo horizontal e o eixo vertical com as
palavras Rv
One-state algorithm
• Para cada frame m de teste, calculamos em
relaçao a cada frame n dos padrões de palavras Rv
a distância acumulada dada por
• d(m,n,v) é a distância local entre o frame de teste
t(m) e o frame de referência rv(n)
• A recursão da fórmula é feita pra todos os frames
internos de Rv (n>=2)
• Para n = 1(frame de borda), a recursão é dada por
One-state algorithm
• Assim, a combinatória para frames internos
escolhe o melhor caminho interno naquela
palavra de referência
• A combinatória para frames de borda escolhe
entre um caminho horizontal da mesma
palavra de referencia ou o melhor frame final
de qualquer palavra de referência
One-state algorithm
• O caminho com a melhor solução é
• O maior problema com este algoritmo é que
ele não leva em conta informações a priori
sobre o número de palavras da entrada que
possamos ter.
• Para tal, devemos modificá-lo:
One-state algorithm
• A computação do algoritmo para cada frame
pode ser feita sincronamente
• Pode ser implementado pra reconhecimento
de voz em tempo real
• Cada d(m,n,v) será computada em cada um
dos níveis e utilizado em níveis subseqüentes
sem a necessidade de maiores cálculos.
Várias strings candidatas
• Podemos querer saber quais os n melhores
matching que existem
– E utilizar esta informação com uma gramática por
exemplo, para verificar qual delas é de fato a
correta
• Para tal, só precisamos guardar informações
não apenas sobre a menor distância obtida,
mas também sobre a segunda menor, etc.
Várias strings candidatas
• Duas melhores strings utilizando o algoritmo
LB
Resumo dos algoritmos
• Algoritmos Two-level DP, LB, one-state
• Todos os 3 algoritmos apresentados são
idênticos no que diz respeito a eles
retornarem a mesma melhor string
• Podem ser facilmente estendidos para
modelos estatísticos (HMMs)
• Permitem a inclusão de uma gramática para
aumentar a robustez do reconhecimento
Gramáticas para reconhecimento
de dígitos conectados
• Sem levar em conta o número de níveis
• Para 7 níveis
• Levando em conta perda ou inserção de um
digito a mais
Segmentação
• Um importante problema a ser levado em
conta é quais padrões serão utilizados durante
o reconhecimento
• Segmentação e rotulação manuais podem
levar a erros e inconsistência
• Criação de um procedimento automático de
segmentação
• Treinamento de padrões das strings
segmentadas
Segmentação
• Baseada no k-means:
– Inicialmente, temos um conjunto de treinamento
rotulado com palavras conectadas e um conjunto
de modelos de dígitos (isolados)
• 1. Utilizar qualquer algoritmo para segmentar
os arquivos do conjunto de treinamento
• 2. Atualiza-se o modelo das palavras,
utilizando-se algum algoritmo de clustering
• 3. Se ainda não convergiu, continua-se
iterando.
Segmentação
Implementação de um sistema de
reconhecimento
• Analise espectral: as características espectrais
do sinal de voz são retiradas (LPC, filter bank,
etc)
• Casamento de padrões: utilizando qualquer
algoritmo citado
• Pós processamento: Eliminação de candidatos
impossíveis, escolhendo o melhor.
Dúvidas
• ?