Em geral, três métodos de reconhecimento de padrões podem ser distinguidos: O método de enumeração. Neste caso, é feita uma comparação com o banco de dados, onde para cada tipo de objeto são apresentadas todas as possíveis modificações do display. Por exemplo, para reconhecimento óptico de imagem, você pode aplicar o método de classificar o tipo de um objeto em diferentes ângulos, escalas, deslocamentos, deformações etc. Para letras, você precisa classificar a fonte, as propriedades da fonte etc. no caso do reconhecimento de imagem sonora, respectivamente, uma comparação com alguns padrões bem conhecidos (por exemplo, uma palavra dita por várias pessoas).

A segunda abordagem é uma análise mais profunda das características da imagem. No caso do reconhecimento óptico, pode ser a determinação de várias características geométricas. A amostra de som, neste caso, é submetida à análise de frequência, amplitude, etc.

O próximo método é o uso de redes neurais artificiais (ANN). Esse método requer um grande número de exemplos da tarefa de reconhecimento durante o treinamento ou uma estrutura de rede neural especial que leva em consideração as especificidades dessa tarefa. No entanto, distingue-se pela maior eficiência e produtividade.

4. Histórico de reconhecimento de padrões

Vamos considerar brevemente o formalismo matemático do reconhecimento de padrões. Um objeto no reconhecimento de padrões é descrito por um conjunto de características básicas (recursos, propriedades). As características principais podem ser de natureza diferente: podem ser retiradas de um conjunto ordenado do tipo linha real, ou de um conjunto discreto (que, no entanto, também pode ser dotado de uma estrutura). Essa compreensão do objeto é consistente tanto com a necessidade de aplicações práticas de reconhecimento de padrões quanto com nossa compreensão do mecanismo de percepção humana de um objeto. De fato, acreditamos que quando um objeto é observado (medido) por uma pessoa, as informações sobre ele chegam ao cérebro por meio de um número finito de sensores (canais analisados), e cada sensor pode ser associado à característica correspondente do objeto. Além das feições que correspondem às nossas medidas do objeto, existe também uma feição selecionada, ou um grupo de feições, que chamamos de feições classificatórias, e descobrir seus valores para um determinado vetor X é a tarefa que natural e os sistemas de reconhecimento artificial funcionam.

É claro que, para estabelecer os valores dessas feições, é necessário ter informações sobre como as feições conhecidas se relacionam com as classificatórias. As informações sobre essa relação são dadas na forma de precedentes, ou seja, um conjunto de descrições de objetos com valores conhecidos de feições classificatórias. E de acordo com essa informação precedente, é necessário construir uma regra de decisão que definirá a descrição arbitrária do objeto do valor de suas características classificadoras.

Essa compreensão do problema de reconhecimento de padrões foi estabelecida na ciência desde os anos 50 do século passado. E então percebeu-se que tal produção não é nada nova. Métodos comprovados de análise de dados estatísticos, que foram usados ​​​​ativamente para muitas tarefas práticas, como, por exemplo, diagnósticos técnicos, foram confrontados com tal formulação e já existiam. Portanto, os primeiros passos do reconhecimento de padrões passaram sob o signo da abordagem estatística, que ditou o problema principal.

A abordagem estatística é baseada na ideia de que o espaço inicial dos objetos é um espaço probabilístico, e as feições (características) dos objetos são variáveis ​​aleatórias dadas nele. Em seguida, a tarefa do cientista de dados era apresentar uma hipótese estatística sobre a distribuição de características, ou melhor, sobre a dependência da classificação de características do resto, a partir de algumas considerações. A hipótese estatística, via de regra, era um conjunto parametricamente especificado de funções de distribuição de características. Uma hipótese estatística típica e clássica é a hipótese da normalidade dessa distribuição (existem muitas variedades de tais hipóteses nas estatísticas). Depois de formular a hipótese, restava testar essa hipótese em dados precedentes. Essa verificação consistia em escolher alguma distribuição do conjunto de distribuições dado inicialmente (o parâmetro da hipótese de distribuição) e avaliar a confiabilidade (intervalo de confiança) dessa escolha. Na verdade, essa função de distribuição era a resposta para o problema, apenas o objeto era classificado não de forma única, mas com algumas probabilidades de pertencer a classes. Os estatísticos também desenvolveram uma justificativa assintótica para tais métodos. Tais justificativas foram feitas de acordo com o seguinte esquema: estabeleceu-se um determinado funcional da qualidade de escolha da distribuição (intervalo de confiança) e mostrou-se que com o aumento do número de precedentes, nossa escolha com probabilidade tendendo a 1 tornou-se correta no sentido deste funcional (intervalo de confiança tendendo a 0). Olhando para o futuro, podemos dizer que a visão estatística do problema de reconhecimento acabou sendo muito frutífera não apenas em termos dos algoritmos desenvolvidos (que incluem métodos de cluster e análise discriminante, regressão não paramétrica, etc.), mas também posteriormente liderado por Vapnik para criar uma teoria estatística profunda de reconhecimento.

No entanto, há um forte argumento a favor do fato de que os problemas de reconhecimento de padrões não são reduzidos a estatísticas. Qualquer problema desse tipo, em princípio, pode ser considerado do ponto de vista estatístico e os resultados de sua solução podem ser interpretados estatisticamente. Para isso, basta assumir que o espaço de objetos do problema é probabilístico. Mas do ponto de vista do instrumentalismo, o critério para o sucesso de uma interpretação estatística de um determinado método de reconhecimento só pode ser a existência de uma fundamentação desse método na linguagem da estatística como um ramo da matemática. Justificação aqui significa o desenvolvimento de requisitos básicos para o problema que garantem o sucesso na aplicação deste método. No entanto, no momento, para a maioria dos métodos de reconhecimento, incluindo aqueles que surgiram diretamente no âmbito da abordagem estatística, essas justificativas satisfatórias não foram encontradas. Além disso, os algoritmos estatísticos mais usados ​​no momento, como discriminante linear de Fisher, janela de Parzen, algoritmo EM, vizinhos mais próximos, sem falar nas redes de crenças bayesianas, possuem uma natureza heurística fortemente pronunciada e podem ter interpretações diferentes das estatísticas. E, finalmente, a tudo o que foi dito acima, deve-se acrescentar que, além do comportamento assintótico dos métodos de reconhecimento, que é o principal problema da estatística, a prática do reconhecimento levanta questões de complexidade computacional e estrutural dos métodos que vão muito além da apenas a teoria da probabilidade.

No total, ao contrário das aspirações dos estatísticos de considerar o reconhecimento de padrões como uma seção da estatística, ideias completamente diferentes entraram na prática e na ideologia do reconhecimento. Um deles foi causado por pesquisas no campo do reconhecimento de padrões visuais e é baseado na seguinte analogia.

Como já foi observado, na vida cotidiana as pessoas resolvem constantemente (muitas vezes inconscientemente) os problemas de reconhecimento de várias situações, imagens auditivas e visuais. Tal capacidade para computadores é, na melhor das hipóteses, uma questão do futuro. A partir disso, alguns pioneiros do reconhecimento de padrões concluíram que a solução desses problemas em um computador deveria, em termos gerais, simular os processos do pensamento humano. A tentativa mais famosa de abordar o problema deste lado foi o famoso estudo de F. Rosenblatt sobre perceptrons.

Em meados da década de 1950, parecia que os neurofisiologistas haviam entendido os princípios físicos do cérebro (no livro "The New Mind of the King", o famoso físico teórico britânico R. Penrose questiona de maneira interessante o modelo de rede neural do cérebro, substanciando o papel essencial dos efeitos da mecânica quântica em seu funcionamento, embora, no entanto, esse modelo tenha sido questionado desde o início. Com base nessas descobertas, F. Rosenblatt desenvolveu um modelo para aprender a reconhecer padrões visuais, que ele chamou de perceptron. O perceptron de Rosenblatt é a seguinte função (Fig. 1):

Fig 1. Esquema do Perceptron

Na entrada, o perceptron recebe um vetor de objeto, que nas obras de Rosenblatt era um vetor binário mostrando qual dos pixels da tela está escurecido pela imagem e qual não está. Além disso, cada um dos sinais é alimentado na entrada do neurônio, cuja ação é uma simples multiplicação por um certo peso do neurônio. Os resultados são transmitidos ao último neurônio, que os soma e compara o valor total com um determinado limite. Dependendo dos resultados da comparação, o objeto de entrada X é reconhecido como necessário ou não. Em seguida, a tarefa de aprender o reconhecimento de padrões era selecionar os pesos dos neurônios e o valor do limiar para que o perceptron desse respostas corretas nas imagens visuais anteriores. Rosenblatt acreditava que a função resultante seria boa para reconhecer a imagem visual desejada, mesmo que o objeto de entrada não estivesse entre os precedentes. A partir de considerações biônicas, ele também criou um método para selecionar pesos e um limite, sobre o qual não vamos nos deter. Digamos apenas que sua abordagem foi bem-sucedida em uma série de problemas de reconhecimento e deu origem a toda uma área de pesquisa sobre algoritmos de aprendizado baseados em redes neurais, das quais o perceptron é um caso especial.

Além disso, várias generalizações do perceptron foram inventadas, a função dos neurônios era complicada: agora os neurônios podiam não apenas multiplicar os números de entrada ou adicioná-los e comparar o resultado com os limites, mas também aplicar funções mais complexas a eles. A Figura 2 mostra uma dessas complicações neuronais:

Arroz. 2 Diagrama da rede neural.

Além disso, a topologia da rede neural poderia ser muito mais complicada do que a considerada por Rosenblatt, por exemplo, esta:

Arroz. 3. Diagrama da rede neural de Rosenblatt.

As complicações levaram a um aumento no número de parâmetros ajustáveis ​​​​durante o treinamento, mas ao mesmo tempo aumentaram a capacidade de sintonizar padrões muito complexos. A pesquisa nesta área está agora em duas áreas intimamente relacionadas - várias topologias de rede e vários métodos de ajuste estão sendo estudados.

As redes neurais atualmente não são apenas uma ferramenta para resolver problemas de reconhecimento de padrões, mas têm sido usadas em pesquisas sobre memória associativa e compressão de imagens. Embora esta linha de pesquisa se sobreponha fortemente aos problemas de reconhecimento de padrões, é uma seção separada da cibernética. Para o reconhecedor no momento, as redes neurais nada mais são do que um conjunto de mapeamentos muito específico e parametricamente definido, que, nesse sentido, não apresenta vantagens significativas sobre muitos outros modelos de aprendizado semelhantes que serão brevemente listados a seguir.

Em conexão com esta avaliação do papel das redes neurais para o reconhecimento adequado (ou seja, não para a biônica, para a qual são de suma importância agora), gostaria de observar o seguinte: redes neurais, sendo um objeto extremamente complexo para matemática análises, com seu uso adequado, nos permitem encontrar leis nada triviais nos dados. Sua dificuldade de análise, no caso geral, explica-se por sua estrutura complexa e, consequentemente, possibilidades praticamente inesgotáveis ​​de generalização das mais diversas regularidades. Mas essas vantagens, como costuma acontecer, são uma fonte de possíveis erros, a possibilidade de retreinamento. Como será discutido posteriormente, essa visão dupla das perspectivas de qualquer modelo de aprendizado é um dos princípios do aprendizado de máquina.

Outra direção popular no reconhecimento são as regras lógicas e as árvores de decisão. Em comparação com os métodos de reconhecimento mencionados acima, esses métodos usam mais ativamente a ideia de expressar nosso conhecimento sobre o assunto na forma de provavelmente as estruturas mais naturais (em um nível consciente) - regras lógicas. Uma regra lógica elementar significa uma declaração como “se feições não classificadas estão na proporção X, então as classificadas estão na proporção Y”. Um exemplo dessa regra no diagnóstico médico é o seguinte: se a idade do paciente for superior a 60 anos e ele já tiver sofrido um ataque cardíaco, não faça a operação - o risco de resultado negativo é alto.

Para buscar regras lógicas nos dados, são necessárias 2 coisas: determinar a medida da “informatividade” da regra e o espaço das regras. E a tarefa de encontrar regras depois disso se transforma em uma tarefa de enumeração completa ou parcial no espaço das regras para encontrar a mais informativa delas. A definição do conteúdo da informação pode ser introduzida de várias formas, e não vamos nos deter nisso, considerando que esse também é algum parâmetro do modelo. O espaço de busca é definido da maneira padrão.

Após encontrar regras suficientemente informativas, inicia-se a fase de “montagem” das regras no classificador final. Sem aprofundar os problemas que surgem aqui (e são um número considerável), listamos 2 métodos principais de “montagem”. O primeiro tipo é uma lista linear. O segundo tipo é a votação ponderada, quando cada regra recebe um determinado peso, e o classificador refere o objeto à classe para a qual o maior número de regras votou.

De fato, a fase de construção de regras e a fase de "montagem" são realizadas juntas e, ao construir uma votação ou lista ponderada, a busca de regras em partes dos dados do caso é chamada repetidas vezes para garantir um melhor ajuste entre os dados e o modelo.

Método de iteração. Neste método, é feita uma comparação com um determinado banco de dados, onde para cada um dos objetos existem diferentes opções para modificar a exibição. Por exemplo, para reconhecimento óptico de imagens, você pode aplicar o método de iteração em diferentes ângulos ou escalas, deslocamentos, deformações, etc. Para letras, você pode iterar sobre a fonte ou suas propriedades. No caso do reconhecimento de padrões sonoros, há uma comparação com alguns padrões conhecidos (palavra falada por muitas pessoas). Além disso, uma análise mais profunda das características da imagem é realizada. No caso do reconhecimento ótico, esta pode ser a definição de características geométricas. A amostra de som, neste caso, é submetida à análise de frequência e amplitude.

O próximo método é uso de redes neurais artificiais(INS). Requer um grande número de exemplos da tarefa de reconhecimento ou uma estrutura de rede neural especial que leva em consideração as especificidades dessa tarefa. Mas, no entanto, esse método é caracterizado por alta eficiência e produtividade.

Métodos baseados em estimativas das densidades de distribuição de valores de recursos. Emprestado da teoria clássica das decisões estatísticas, em que os objetos de estudo são considerados como realizações de uma variável aleatória multidimensional distribuída no espaço de características de acordo com alguma lei. Eles são baseados no esquema Bayesiano de tomada de decisão, que apela para as probabilidades iniciais de objetos pertencentes a uma determinada classe e densidades de distribuição de atributos condicionais.

O grupo de métodos baseados na estimativa das densidades de distribuição de valores de feições está diretamente relacionado aos métodos de análise discriminante. A abordagem Bayesiana para a tomada de decisão é um dos métodos paramétricos mais desenvolvidos na estatística moderna, para o qual a expressão analítica da lei de distribuição (a lei normal) é considerada conhecida e apenas um pequeno número de parâmetros (vetores médios e matrizes de covariância ) precisam ser estimados. As principais dificuldades na aplicação deste método são consideradas a necessidade de lembrar toda a amostra de treinamento para calcular as estimativas de densidade e alta sensibilidade para a amostra de treinamento.

Métodos baseados em hipóteses sobre a classe de funções de decisão. Neste grupo, o tipo da função de decisão é considerado conhecido e seu funcional de qualidade é dado. Com base nesse funcional, a aproximação ótima para a função de decisão é encontrada a partir da sequência de treinamento. O funcional de qualidade da regra de decisão geralmente está associado a um erro. A principal vantagem do método é a clareza da formulação matemática do problema de reconhecimento. A possibilidade de extrair novos conhecimentos sobre a natureza de um objeto, em particular, conhecimentos sobre os mecanismos de interação de atributos, é fundamentalmente limitada aqui por uma dada estrutura de interação, fixada na forma escolhida de funções de decisão.

Método de comparação de protótipos. Este é o método de reconhecimento extensional mais fácil na prática. Aplica-se quando as classes reconhecíveis são mostradas como classes geométricas compactas. Em seguida, o centro do agrupamento geométrico (ou o objeto mais próximo do centro) é escolhido como o ponto protótipo.

Para classificar um objeto indeterminado, o protótipo mais próximo dele é encontrado, e o objeto pertence à mesma classe que ele. Obviamente, nenhuma imagem generalizada é formada neste método. Vários tipos de distâncias podem ser usados ​​como medida.

Método dos k vizinhos mais próximos. O método reside no fato de que, ao classificar um objeto desconhecido, é encontrado um determinado número (k) de espaço de características geometricamente mais próximo de outros vizinhos mais próximos com pertencimento já conhecido a uma classe. A decisão de atribuir um objeto desconhecido é feita analisando informações sobre seus vizinhos mais próximos. A necessidade de reduzir o número de objetos na amostra de treinamento (precedentes diagnósticos) é uma desvantagem desse método, pois reduz a representatividade da amostra de treinamento.

Com base no fato de que diferentes algoritmos de reconhecimento se comportam de maneira diferente na mesma amostra, surge a questão de uma regra de decisão sintética que usaria os pontos fortes de todos os algoritmos. Para isso, existe um método sintético ou conjuntos de regras de decisão que combinam os aspectos mais positivos de cada um dos métodos.

Concluindo a revisão dos métodos de reconhecimento, apresentamos a essência do que foi dito acima em uma tabela resumida, acrescentando alguns outros métodos usados ​​na prática.

Tabela 1. Tabela de classificação dos métodos de reconhecimento, comparação de suas áreas de aplicação e limitações

Classificação dos métodos de reconhecimento	Area de aplicação	Limitações (desvantagens)
Métodos de reconhecimento intensivo	Métodos baseados em estimativas de densidade	Problemas com uma distribuição conhecida (normal), a necessidade de coletar grandes estatísticas	A necessidade de enumerar todo o conjunto de treinamento durante o reconhecimento, alta sensibilidade à não representatividade do conjunto de treinamento e artefatos
Métodos baseados em suposições	As classes devem ser bem separáveis	A forma da função de decisão deve ser conhecida antecipadamente. A impossibilidade de levar em conta novos conhecimentos sobre correlações entre recursos
Métodos Booleanos	Problemas de pequena dimensão	Ao selecionar regras de decisão lógica, é necessária uma enumeração completa. Alta intensidade de trabalho
Métodos Linguísticos		A tarefa de determinar a gramática para um determinado conjunto de declarações (descrições de objetos) é difícil de formalizar. Problemas teóricos não resolvidos
Métodos extensionais de reconhecimento	Método de comparação de protótipo	Problemas de pequena dimensão do espaço de recursos	Alta dependência dos resultados da classificação na métrica. Métrica ideal desconhecida
k método do vizinho mais próximo		Alta dependência dos resultados da classificação na métrica. A necessidade de uma enumeração completa da amostra de treinamento durante o reconhecimento. Complexidade computacional
Algoritmos de cálculo de notas (ABO)	Problemas de pequena dimensão em termos de número de classes e recursos	Dependência dos resultados da classificação na métrica. A necessidade de uma enumeração completa da amostra de treinamento durante o reconhecimento. Alta complexidade técnica do método
As regras de decisão coletiva (CRC) são um método sintético.	Problemas de pequena dimensão em termos de número de classes e recursos	Complexidade técnica muito alta do método, o número não resolvido de problemas teóricos, tanto na determinação das áreas de competência de métodos específicos quanto nos próprios métodos específicos

Dom, 29 de março de 2015

Atualmente, existem muitas tarefas nas quais é necessário tomar alguma decisão em função da presença de um objeto na imagem ou classificá-lo. A capacidade de "reconhecer" é considerada a principal propriedade dos seres biológicos, enquanto os sistemas computacionais não possuem totalmente essa propriedade.

Considere os elementos gerais do modelo de classificação.

Classe- um conjunto de objetos que possuem propriedades comuns. Para objetos da mesma classe, a presença de "semelhança" é assumida. Um número arbitrário de classes pode ser definido para a tarefa de reconhecimento, mais de 1. O número de classes é indicado pelo número S. Cada classe tem seu próprio rótulo de identificação de classe.

Classificação- o processo de atribuição de rótulos de classe a objetos, de acordo com alguma descrição das propriedades desses objetos. Um classificador é um dispositivo que recebe um conjunto de características de um objeto como entrada e produz um rótulo de classe como resultado.

Verificação- o processo de combinar uma instância de objeto com um único modelo de objeto ou descrição de classe.

Debaixo caminho entenderemos o nome da área no espaço de atributos, na qual muitos objetos ou fenômenos do mundo material são exibidos. sinal- uma descrição quantitativa de uma propriedade particular do objeto ou fenômeno em estudo.

espaço de recurso este é um espaço N-dimensional definido para uma determinada tarefa de reconhecimento, onde N é um número fixo de recursos medidos para quaisquer objetos. O vetor do espaço de características x correspondente ao objeto do problema de reconhecimento é um vetor N-dimensional com componentes (x_1,x_2,…,x_N), que são os valores de características para o objeto dado.

Em outras palavras, o reconhecimento de padrões pode ser definido como a atribuição de dados iniciais a uma determinada classe, extraindo recursos ou propriedades essenciais que caracterizam esses dados da massa geral de detalhes irrelevantes.

Exemplos de problemas de classificação são:

• reconhecimento de caracteres;
• reconhecimento de fala;
• estabelecer um diagnóstico médico;
• previsão do tempo;
• reconhecimento facial
• classificação de documentos, etc.

Na maioria das vezes, o material de origem é a imagem recebida da câmera. A tarefa pode ser formulada como a obtenção de vetores de características para cada classe na imagem considerada. O processo pode ser visto como um processo de codificação, que consiste em atribuir um valor a cada característica do espaço de características para cada classe.

Se considerarmos 2 classes de objetos: adultos e crianças. Como recursos, você pode escolher altura e peso. Como se depreende da figura, essas duas classes formam dois conjuntos que não se interceptam, o que pode ser explicado pelas feições escolhidas. Porém, nem sempre é possível escolher os parâmetros medidos corretos como características das classes. Por exemplo, os parâmetros selecionados não são adequados para criar classes não sobrepostas de jogadores de futebol e jogadores de basquete.

A segunda tarefa de reconhecimento é a seleção de características ou propriedades das imagens originais. Esta tarefa pode ser atribuída ao pré-processamento. Se considerarmos a tarefa de reconhecimento de fala, podemos distinguir recursos como vogais e consoantes. O atributo deve ser uma propriedade característica de uma determinada classe, embora seja comum a essa classe. Signos que caracterizam as diferenças entre - signos interclasses. Características comuns a todas as classes não carregam informações úteis e não são consideradas como características no problema de reconhecimento. A escolha de características é uma das tarefas importantes associadas à construção de um sistema de reconhecimento.

Depois que as características são determinadas, é necessário determinar o procedimento de decisão ótimo para classificação. Considere um sistema de reconhecimento de padrões projetado para reconhecer várias classes M, denotadas como m_1,m_2,…,m 3. Então podemos assumir que o espaço da imagem consiste em M regiões, cada uma contendo pontos correspondentes a uma imagem de uma classe. Então o problema de reconhecimento pode ser considerado como a construção de limites separando M classes com base nos vetores de medição aceitos.

Resolver o problema de pré-processamento de imagens, extração de recursos e o problema de obter a solução e classificação ótima geralmente está associado à necessidade de avaliar vários parâmetros. Isso leva ao problema de estimação de parâmetros. Além disso, é óbvio que a extração de recursos pode usar informações adicionais com base na natureza das classes.

A comparação de objetos pode ser feita com base em sua representação na forma de vetores de medição. É conveniente representar os dados de medição como números reais. Então a similaridade dos vetores de características de dois objetos pode ser descrita usando a distância euclidiana.

onde d é a dimensão do vetor de características.

Existem 3 grupos de métodos de reconhecimento de padrões:

• Comparação de amostra. Este grupo inclui classificação pela média mais próxima, classificação pela distância ao vizinho mais próximo. Os métodos de reconhecimento estrutural também podem ser incluídos no grupo de comparação de amostras.
• Métodos estatísticos. Como o nome indica, os métodos estatísticos usam algumas informações estatísticas ao resolver um problema de reconhecimento. O método determina a pertença de um objeto a uma determinada classe com base na probabilidade. Em alguns casos, isso se resume a determinar a probabilidade a posteriori de um objeto pertencer a uma determinada classe, desde que as características desse objeto tenham tomado as devidas valores. Um exemplo é o método de regra de decisão bayesiana.
• Redes neurais. Uma classe separada de métodos de reconhecimento. Uma característica distintiva dos outros é a capacidade de aprender.

Classificação pela média mais próxima

Na abordagem clássica de reconhecimento de padrões, em que um objeto desconhecido para classificação é representado como um vetor de características elementares. Um sistema de reconhecimento baseado em características pode ser desenvolvido de várias maneiras. Esses vetores podem ser conhecidos pelo sistema antecipadamente como resultado do treinamento ou previstos em tempo real com base em alguns modelos.

Um algoritmo de classificação simples consiste em agrupar dados de referência de classe usando o vetor de expectativa de classe (média).

onde x(i,j) é o j-ésimo recurso de referência da classe i, n_j é o número de vetores de referência da classe i.

Então o objeto desconhecido pertencerá à classe i se estiver muito mais próximo do vetor de expectativa da classe i do que dos vetores de expectativa de outras classes. Este método é adequado para problemas em que os pontos de cada classe estão localizados de forma compacta e distantes dos pontos de outras classes.

Dificuldades surgirão se as aulas tiverem uma estrutura um pouco mais complexa, por exemplo, como na figura. Nesse caso, a classe 2 é dividida em duas seções não sobrepostas, que são mal descritas por um único valor médio. Além disso, a classe 3 é muito alongada, as amostras da 3ª classe com grandes valores de coordenadas x_2 estão mais próximas do valor médio da 1ª classe do que da 3ª classe.

O problema descrito em alguns casos pode ser resolvido alterando o cálculo da distância.

Levaremos em consideração a característica do "scatter" dos valores de classe - σ_i, ao longo de cada direção de coordenada i. O desvio padrão é igual à raiz quadrada da variância. A distância euclidiana em escala entre o vetor x e o vetor de expectativa x_c é

Essa fórmula de distância reduzirá o número de erros de classificação, mas, na realidade, a maioria dos problemas não pode ser representada por uma classe tão simples.

Classificação por distância ao vizinho mais próximo

Outra abordagem para a classificação é atribuir um vetor de característica desconhecida x à classe à qual esse vetor está mais próximo de uma amostra separada. Essa regra é chamada de regra do vizinho mais próximo. A classificação do vizinho mais próximo pode ser mais eficiente mesmo quando as classes são complexas ou quando as classes se sobrepõem.

Essa abordagem não requer suposições sobre os modelos de distribuição de vetores de recursos no espaço. O algoritmo usa apenas informações sobre amostras de referência conhecidas. O método de solução é baseado em calcular a distância x para cada amostra no banco de dados e encontrar a distância mínima. As vantagens desta abordagem são óbvias:

• a qualquer momento você pode adicionar novas amostras ao banco de dados;
• estruturas de dados de árvore e grade reduzem o número de distâncias calculadas.

Além disso, a solução será melhor se você procurar no banco de dados não um vizinho mais próximo, mas k. Então, para k > 1, fornece a melhor amostra da distribuição de vetores no espaço d-dimensional. No entanto, o uso eficiente dos valores de k depende se há o suficiente em cada região do espaço. Se houver mais de duas classes, será mais difícil tomar a decisão certa.

Literatura

• M. Castrillon, . O. Deniz, . D. Hernández e J. Lorenzo, "Uma comparação de detectores de face e características faciais com base na estrutura de detecção geral de objetos Viola-Jones", International Journal of Computer Vision, nº 22, pp. 481-494, 2011.
• Y.-Q. Wang, "An Analysis of Viola-Jones Face Detection Algorithm," IPOL Journal, 2013.
• L. Shapiro e D. Stockman, visão computacional, Binom. Laboratório do Conhecimento, 2006.
• Z. N. G., métodos de reconhecimento e sua aplicação, rádio soviética, 1972.
• J. Tu, R. Gonzalez, Princípios matemáticos de reconhecimento de padrões, Moscou: “Mir” Moscou, 1974.
• Khan, H. Abdullah e M. Shamian Bin Zainal, "Eficiente algoritmo de detecção de olhos e boca usando combinação de viola jones e detecção de pixel de cor de pele" International Journal of Engineering and Applied Sciences, no. Vol. 3 no 4, 2013.
• V. Gaede e O. Gunther, "Multidimensional Access Methods," ACM Computing Surveys, pp. 170-231, 1998.

• tutorial

Há muito tempo eu queria escrever um artigo geral contendo os fundamentos do Reconhecimento de Imagem, uma espécie de guia sobre métodos básicos, dizendo quando usá-los, quais tarefas eles resolvem, o que pode ser feito à noite no joelho e o que é melhor não pensar sem ter uma equipe de 20 pessoas.

Há muito tempo que escrevo alguns artigos sobre reconhecimento óptico, então, algumas vezes por mês, várias pessoas me escrevem com perguntas sobre esse assunto. Às vezes você tem a sensação de que vive com eles em mundos diferentes. Por um lado, você entende que uma pessoa provavelmente é um profissional em um tópico relacionado, mas sabe muito pouco sobre métodos de reconhecimento óptico. E o mais chato é que ele tenta aplicar um método de um campo de conhecimento próximo, que é lógico, mas não funciona totalmente no Reconhecimento de Imagem, mas não entende isso e fica muito ofendido se começar a contar algo do muito básico. E considerando que contar desde o básico é muito tempo, que muitas vezes não dá, fica ainda mais triste.

Este artigo foi desenvolvido para que uma pessoa que nunca tenha lidado com métodos de reconhecimento de imagem possa, em 10 a 15 minutos, criar em sua cabeça uma certa imagem básica do mundo correspondente ao tópico e entender em que direção deve cavar. Muitos dos métodos descritos aqui são aplicáveis ​​ao radar e ao processamento de áudio.
Vou começar com alguns princípios que sempre começamos a dizer a um cliente em potencial ou a uma pessoa que deseja começar a fazer Reconhecimento Óptico:

• Ao resolver um problema, vá sempre do mais simples. É muito mais fácil pendurar uma etiqueta laranja em uma pessoa do que segui-la, destacando-a em cascatas. É muito mais fácil pegar uma câmera com uma resolução maior do que desenvolver um algoritmo de super-resolução.
• Uma declaração de problema estrita em métodos de reconhecimento óptico é muito mais importante do que em problemas de programação de sistema: uma palavra extra no TK pode adicionar 50% do trabalho.
• Em problemas de reconhecimento, não há soluções universais. Você não pode fazer um algoritmo que simplesmente "reconheça qualquer inscrição". Uma placa na rua e uma folha de texto são objetos fundamentalmente diferentes. Provavelmente é possível fazer um algoritmo geral (um bom exemplo do Google), mas isso exigirá muito trabalho de uma grande equipe e consistirá em dezenas de sub-rotinas diferentes.
• OpenCV é a bíblia, que tem muitos métodos, e com a qual você pode resolver 50% do volume de quase todos os problemas, mas OpenCV é apenas uma pequena parte do que pode ser feito na realidade. Em um estudo, foi escrito nas conclusões: "O problema não é resolvido pelos métodos OpenCV, portanto, é insolúvel." Tente evitar isso, não seja preguiçoso e avalie sobriamente a tarefa atual do zero, sem usar modelos OpenCV.

É muito difícil dar algum tipo de conselho universal ou dizer como criar algum tipo de estrutura em torno da qual você possa construir uma solução para problemas arbitrários de visão computacional. O objetivo deste artigo é estruturar o que pode ser usado. Vou tentar dividir os métodos existentes em três grupos. O primeiro grupo é a pré-filtragem e a preparação da imagem. O segundo grupo é o processamento lógico dos resultados da filtragem. O terceiro grupo são os algoritmos de tomada de decisão baseados em processamento lógico. Os limites entre os grupos são muito arbitrários. Para resolver um problema, nem sempre é necessário aplicar métodos de todos os grupos; às vezes dois são suficientes e às vezes até um.

A lista de métodos apresentada aqui não está completa. Proponho adicionar nos comentários métodos críticos que não escrevi e atribuir 2 a 3 palavras acompanhantes a cada um.

Parte 1. Filtragem

Nesse grupo coloquei métodos que permitem selecionar áreas de interesse em imagens sem analisá-las. A maioria desses métodos aplica algum tipo de transformação uniforme a todos os pontos da imagem. Ao nível da filtragem, a imagem não é analisada, mas os pontos que são filtrados podem ser considerados áreas com características especiais.

Binarização de limiar, seleção de área de histograma

A transformação mais simples é a binarização da imagem pelo limiar. Para imagens RGB e em tons de cinza, o limite é o valor da cor. Existem problemas ideais em que tal transformação é suficiente. Suponha que você queira selecionar itens automaticamente em uma folha de papel em branco:




A escolha do limite pelo qual ocorre a binarização determina em grande parte o próprio processo de binarização. Neste caso, a imagem foi binarizada pela cor média. Normalmente, a binarização é feita com um algoritmo que seleciona adaptativamente um limite. Tal algoritmo pode ser a escolha de expectativa ou modo. E você pode escolher o maior pico do histograma.

A binarização pode dar resultados muito interessantes ao trabalhar com histogramas, inclusive a situação se considerarmos uma imagem não em RGB, mas em HSV. Por exemplo, segmente as cores de interesse. Com base neste princípio, é possível construir um detector de etiquetas e um detector de pele humana.

Filtragem clássica: Fourier, LPF, HPF

Métodos clássicos de filtragem de radar e processamento de sinal podem ser aplicados com sucesso em uma variedade de tarefas de Reconhecimento de Padrão. O método tradicional em radar, que quase nunca é utilizado em imagens em sua forma pura, é a transformada de Fourier (mais especificamente, a FFT). Uma das poucas exceções em que a transformada de Fourier 1D é usada é a compactação de imagem. Para análise de imagem, uma transformação unidimensional geralmente não é suficiente, você precisa usar uma transformação bidimensional com muito mais recursos.

Poucas pessoas realmente calculam, geralmente é muito mais rápido e fácil usar a convolução da região de interesse com um filtro pronto aguçado para frequências altas (HPF) ou baixas (LPF). Tal método, é claro, não permite a análise de espectro, mas em uma tarefa específica de processamento de vídeo, geralmente não é necessária uma análise, mas um resultado.


Os exemplos mais simples de filtros que enfatizam baixas frequências (filtro Gaussiano) e altas frequências (filtro Gabor).
Para cada ponto da imagem, uma janela é selecionada e multiplicada por um filtro de mesmo tamanho. O resultado dessa convolução é o novo valor do ponto. Ao implementar LPF e HPF, são obtidas imagens deste tipo:

Ondas

Mas e se usarmos alguma função característica arbitrária para convolução com o sinal? Em seguida, será chamado de "Wavelet Transform". Essa definição de wavelets não é correta, mas tradicionalmente, em muitas equipes, a análise de wavelets é a busca de um padrão arbitrário em uma imagem usando convolução com um modelo desse padrão. Existe um conjunto de funções clássicas usadas na análise de wavelets. Isso inclui a ondaleta de Haar, a ondaleta de Morlet, a ondaleta do chapéu mexicano e assim por diante. As primitivas de Haar, sobre as quais havia vários de meus artigos anteriores ( , ), referem-se a tais funções para um espaço bidimensional.


Acima estão 4 exemplos de wavelets clássicas. Wavelet 3D Haar, wavelet 2D Meyer, wavelet Mexican Hat, wavelet Daubechies. Um bom exemplo de uso da interpretação estendida de wavelets é o problema de encontrar um brilho no olho, para o qual o próprio brilho é uma wavelet:

As wavelets clássicas são geralmente usadas para , ou para sua classificação (a ser descrita abaixo).

Correlação

Depois de uma interpretação tão livre de wavelets de minha parte, vale a pena mencionar a correlação real subjacente a elas. Ao filtrar imagens, esta é uma ferramenta indispensável. Uma aplicação clássica é a correlação de fluxo de vídeo para encontrar deslocamentos ou fluxos ópticos. O detector de deslocamento mais simples também é, de certo modo, um correlacionador de diferenças. Onde as imagens não se correlacionam, houve movimento.

Filtragem de funções

Uma classe interessante de filtros são as funções de filtragem. Estes são filtros puramente matemáticos que permitem detectar uma função matemática simples em uma imagem (linha, parábola, círculo). É construída uma imagem acumulativa, na qual para cada ponto da imagem original é desenhado um conjunto de funções que a geram. A transformação mais clássica é a transformação de Hough para linhas. Nesta transformação, para cada ponto (x;y), é desenhado um conjunto de pontos (a;b) da reta y=ax+b, para os quais a igualdade é verdadeira. Obtenha lindas fotos:


(o primeiro plus para quem é o primeiro a encontrar uma pegadinha na foto e tal definição e explicá-lo, o segundo plus para quem é o primeiro a dizer o que é mostrado aqui)
A transformada de Hough permite que você encontre qualquer função parametrizável. Por exemplo, círculos. Há uma transformação modificada que permite pesquisar qualquer arquivo . Esta transformação é terrivelmente apreciada pelos matemáticos. Mas ao processar imagens, infelizmente, nem sempre funciona. Velocidade muito lenta, sensibilidade muito alta para a qualidade da binarização. Mesmo em situações ideais, preferi me virar com outros métodos.
A contrapartida da transformada de Hough para linhas é a transformada de Radon. É calculado através da FFT, que dá um ganho de performance em uma situação onde há muitos pontos. Além disso, pode ser aplicado a uma imagem não binarizada.

Filtragem de contorno

Uma classe separada de filtros é a filtragem de borda e contorno. Os caminhos são muito úteis quando queremos passar de trabalhar com uma imagem para trabalhar com objetos nessa imagem. Quando um objeto é bastante complexo, mas bem distinto, muitas vezes a única maneira de trabalhar com ele é selecionar seus contornos. Existem vários algoritmos que resolvem o problema da filtragem de contorno:

O mais usado é o Kenny, que funciona bem e cuja implementação é no OpenCV (o Sobel também está lá, mas ele procura contornos piores).

Outros filtros

Acima estão os filtros, cujas modificações ajudam a resolver 80-90% das tarefas. Mas além deles, existem filtros mais raros usados ​​em tarefas locais. Existem dezenas desses filtros, não vou listar todos. De interesse são os filtros iterativos (por exemplo ), bem como as transformadas ridgelet e curvlet, que são uma liga de filtragem clássica de wavelets e análise no campo de transformadas de radônio. A transformação Beamlet funciona lindamente na fronteira da transformação wavelet e análise lógica, permitindo destacar os contornos:

Mas essas transformações são muito específicas e adaptadas para tarefas raras.

Parte 2. Processamento lógico de resultados de filtragem

A filtragem fornece um conjunto de dados adequados para processamento. Mas muitas vezes você não pode simplesmente pegar e usar esses dados sem processá-los. Nesta seção, haverá vários métodos clássicos que permitem ir da imagem às propriedades dos objetos, ou aos próprios objetos.

Morfologia

A transição da filtragem para a lógica, a meu ver, são os métodos da morfologia matemática ( , ). Na verdade, essas são as operações mais simples de aumento e erosão de imagens binárias. Esses métodos permitem remover o ruído de uma imagem binária aumentando ou diminuindo os elementos disponíveis. Com base na morfologia matemática, existem algoritmos de contorno, mas geralmente eles usam algum tipo de algoritmo híbrido ou algoritmos em conjunto.

análise de contorno

Na seção sobre filtragem, algoritmos para obtenção de limites já foram mencionados. Os limites resultantes são simplesmente convertidos em contornos. Para o algoritmo de Canny isso acontece automaticamente, para outros algoritmos é necessária uma binarização adicional. Você pode obter um contorno para um algoritmo binário, por exemplo, com o algoritmo do besouro.
O contorno é uma característica única de um objeto. Muitas vezes, isso permite que você identifique o objeto ao longo do contorno. Existe um poderoso aparato matemático que permite fazer isso. O aparelho é chamado de análise de contorno ( , ).

Para ser sincero, nunca consegui aplicar a análise de contorno em problemas reais. São necessárias condições muito ideais. Ou não há fronteira ou há muito barulho. Mas, se você precisa reconhecer algo em condições ideais, a análise de contorno é uma ótima opção. Funciona muito rápido, bela matemática e lógica compreensível.

pontos singulares

Pontos-chave são características exclusivas de um objeto que permitem que o objeto seja associado a si mesmo ou a classes de objetos semelhantes. Existem dezenas de maneiras de selecionar esses pontos. Alguns métodos destacam pontos especiais em quadros vizinhos, alguns após um longo período de tempo e quando a iluminação muda, alguns permitem encontrar pontos especiais que permanecem assim mesmo quando o objeto gira. Vamos começar com métodos que nos permitem encontrar pontos especiais que não são tão estáveis, mas são calculados rapidamente, e então iremos em complexidade crescente:
Primeira série. Pontos singulares que são estáveis ​​por segundos. Esses pontos são usados ​​para guiar um objeto entre quadros de vídeo adjacentes ou para convergir imagens de câmeras vizinhas. Esses pontos incluem máximos locais da imagem, cantos na imagem (o melhor dos detectores, talvez, o detector Haris), pontos nos quais os máximos de dispersão são alcançados, certos gradientes, etc.
Segunda classe. Pontos singulares que são estáveis ​​ao mudar a iluminação e pequenos movimentos do objeto. Tais pontos servem principalmente para treinamento e posterior classificação dos tipos de objetos. Por exemplo, um classificador de pedestre ou um classificador de face é o produto de um sistema construído apenas sobre esses pontos. Algumas das wavelets mencionadas anteriormente podem ser a base para tais pontos. Por exemplo, primitivos de Haar, pesquisa de brilho, pesquisa de outros recursos específicos. Esses pontos incluem pontos encontrados pelo método de histogramas de gradientes direcionais (HOG).
Terceira classe. pontos estáveis. Conheço apenas dois métodos que fornecem estabilidade total e suas modificações. Isso e . Eles permitem que você encontre pontos-chave mesmo ao girar a imagem. O cálculo desses pontos leva mais tempo do que outros métodos, mas por um tempo bastante limitado. Infelizmente, esses métodos são patenteados. Embora na Rússia seja impossível patentear algoritmos, use-os para o mercado doméstico.

Parte 3. Treinamento

A terceira parte da história será dedicada a métodos que não funcionam diretamente com a imagem, mas que permitem tomar decisões. Basicamente, esses são vários métodos de aprendizado de máquina e tomada de decisão. Recentemente, Yandyks postou no Habr sobre este assunto, há uma seleção muito boa. Aqui está na versão de texto. Para um estudo sério do assunto, eu recomendo fortemente que você dê uma olhada neles. Aqui tentarei identificar vários métodos básicos usados ​​especificamente no reconhecimento de padrões.
Em 80% das situações, a essência da aprendizagem no problema de reconhecimento é a seguinte:
Há uma amostra de teste na qual existem várias classes de objetos. Que seja a presença/ausência de uma pessoa na foto. Para cada imagem, existe um conjunto de feições que foram destacadas por alguma feição, seja Haar, HOG, SURF ou alguma wavelet. O algoritmo de aprendizado deve construir tal modelo, segundo o qual será capaz de analisar a nova imagem e decidir qual dos objetos está na imagem.
Como isso é feito? Cada uma das imagens de teste é um ponto no espaço de características. Suas coordenadas são o peso de cada feição na imagem. Sejam nossos sinais: “A presença de olhos”, “A presença de um nariz”, “A presença de duas mãos”, “A presença de orelhas”, etc. Alocaremos todos esses sinais com os detectores que temos, que são treinados em partes do corpo semelhantes ao humano. Para uma pessoa em tal espaço, o ponto correto será . Para o macaco, ponto para o cavalo. O classificador é treinado em uma amostra de exemplos. Mas nem todas as fotografias mostravam mãos, outras não tinham olhos, e na terceira o macaco tinha nariz humano devido a um erro de classificação. O classificador humano treinável divide automaticamente o espaço de recursos de forma a dizer: se o primeiro recurso estiver no intervalo 0,5 Em essência, o objetivo do classificador é desenhar no espaço de características as áreas características dos objetos de classificação. Assim ficará a aproximação sucessiva da resposta para um dos classificadores (AdaBoost) no espaço bidimensional:


Existem muitos classificadores. Cada um deles funciona melhor em algumas de suas tarefas. A tarefa de selecionar um classificador para uma tarefa específica é em grande parte uma arte. Aqui estão algumas fotos legais sobre o tema.

Caso simples, separação unidimensional

Vamos pegar um exemplo do caso mais simples de classificação, quando o espaço de características é unidimensional, e precisamos separar 2 classes. A situação ocorre com mais frequência do que parece: por exemplo, quando você precisa distinguir dois sinais ou comparar um padrão com uma amostra. Digamos que temos uma amostra de treinamento. Neste caso, obtém-se uma imagem, onde o eixo X será uma medida de similaridade, e o eixo Y será o número de eventos com tal medida. Quando o objeto desejado é semelhante a si mesmo, obtém-se uma Gaussiana à esquerda. Quando não for semelhante - certo. O valor X=0,4 separa as amostras de forma que uma decisão errônea minimiza a probabilidade de tomar qualquer decisão errada. É a busca por tal separador que é a tarefa da classificação.


Pequena nota. O critério que minimiza o erro nem sempre será ótimo. O gráfico a seguir é um gráfico de um sistema de reconhecimento de íris real. Para tal sistema, o critério é escolhido de forma a minimizar a probabilidade de falsa admissão de um estranho ao objeto. Tal probabilidade é chamada de "erro de primeiro tipo", "probabilidade de falso alarme", "falso positivo". Na literatura inglesa "False Access Rate".
) AdaBusta é um dos classificadores mais comuns. Por exemplo, a cascata Haar é construída sobre ela. Geralmente usado quando é necessária classificação binária, mas nada impede o ensino para mais turmas.
SVM ( , , , ) Um dos classificadores mais poderosos com muitas implementações. Em princípio, nas tarefas de aprendizado que encontrei, funcionou de maneira semelhante ao adabusta. É considerado bastante rápido, mas seu treinamento é mais difícil que o do Adabusta e requer a escolha do kernel correto.

Existem também redes neurais e regressão. Mas para classificá-los brevemente e mostrar como eles diferem, é necessário um artigo muito maior do que este.
________________________________________________
Espero ter conseguido dar uma visão geral rápida dos métodos usados ​​sem mergulhar na matemática e na descrição. Talvez isso ajude alguém. Embora, é claro, o artigo esteja incompleto e não haja uma palavra sobre como trabalhar com imagens estéreo, ou sobre o LSM com o filtro de Kalman, ou sobre a abordagem bayesiana adaptativa.
Se você gostou do artigo, tentarei fazer a segunda parte com uma seleção de exemplos de como os problemas existentes de ImageRecognition são resolvidos.

E finalmente

O que ler?
1) Uma vez gostei muito do livro "Processamento de imagem digital" de B. Yana, que é escrito de forma simples e clara, mas ao mesmo tempo quase toda a matemática é dada. Bom para se familiarizar com os métodos existentes.
2) O clássico do gênero é R Gonzalez, R. Woods "Digital Image Processing". Por alguma razão, foi mais difícil para mim do que o primeiro. Muito menos matemática, mas mais métodos e imagens.
3) “Processamento e análise de imagens em problemas de visão de máquina” - escrito com base em um curso ministrado em um dos departamentos da PhysTech. Muitos métodos e sua descrição detalhada. Mas, na minha opinião, o livro tem dois grandes pontos negativos: o livro é fortemente focado no pacote de software que o acompanha, no livro muitas vezes a descrição de um método simples se transforma em selva matemática, da qual é difícil tirar o diagrama estrutural do método. Mas os autores criaram um site conveniente, onde quase todo o conteúdo é apresentado - wiki.technicalvision.ru Adicionar tags