Pular para o conteúdo
</> Entendendo Algoritmos

OCR com KNN

OCR é reconhecer caracteres em imagens. O livro mostra que o KNN resolve isso: cada imagem vira uma lista de características (aqui, os 35 pixels de uma grade 5 × 7) e o dígito é o mais comum entre as imagens de treino mais parecidas. Desenhe um número e veja quem são os vizinhos.

Explicação do algoritmo: escolha um nível para ler.

{ }Ver o código
// cada imagem é uma lista de pixels (0 ou 1); a distância é quantos pixels diferem
function reconhecerDigito(pixels, treino, k) {
  const vizinhos = treino
    .map((ex) => ({
      digito: ex.digito,
      distancia: ex.pixels.reduce((s, p, i) => s + (p !== pixels[i] ? 1 : 0), 0),
    }))
    .sort((a, b) => a.distancia - b.distancia)
    .slice(0, k);

  const votos = {};
  for (const v of vizinhos) votos[v.digito] = (votos[v.digito] ?? 0) + 1;

  // dígito mais votado (em empate, o do vizinho mais próximo)
  const maisVotos = Math.max(...Object.values(votos));
  return vizinhos.find((v) => votos[v.digito] === maisVotos).digito;
}
Clique nos quadrados para desenhar
Começar de um dígito
Dígito reconhecido
3
Pixels diferentes do vizinho mais próximo
0
Votação entre os 5 vizinhos
3
3
8
2
Vizinhos mais próximos
  1. 3dist. 0
  2. 8dist. 2
  3. 3dist. 3
  4. 3dist. 3
  5. 8dist. 3

O treino tem 30 imagens: o modelo de cada dígito e duas versões com 3 pixels trocados. A distância entre duas imagens é o número de pixels em que elas diferem. É uma demonstração simples: um OCR real usa imagens maiores e muito mais exemplos.