Converta imagens em preto e branco em gráficos ASCII usando decomposição de matriz não negativa

Em geral, converter uma imagem em gráficos ASCII é uma tarefa bastante demorada, mas existem algoritmos que automatizam esse processo. Este artigo discute a abordagem proposta pelos pesquisadores Paul D. O'Grady e Scott T. Rickard em "Conversão automática de arte em imagens ASCII de imagens binárias usando restrições não negativas" . O método descrito descreve a representação do processo de conversão de imagem como um problema de otimização e a solução desse problema usando uma decomposição de matriz não negativa. Abaixo está uma descrição do algoritmo em questão, bem como sua implementação:

Descrição do algoritmo

A imagem original é dividida em blocos de tamanho onde e - largura e altura de um caractere em pixels. Se a largura \ altura da imagem não for um múltiplo da largura \ altura do caractere, a imagem será cortada ou suplementada com áreas brancas do tamanho desejado.


Cada um blocos obtidos após a partição ser representada como um vetor de comprimento cujos valores são as intensidades de cor dos pixels da imagem (valores de 0 a 255, em que o pixel branco corresponde ao valor 0 e o pixel preto corresponde a 255). Os vetores resultantes devem ser normalizados usando a norma :

Os vetores normalizados são reescritos na forma de colunas, formando uma matriz o tamanho .

A matriz resultante precisa ser representado como um produto de matrizes e todos os elementos dos quais não são negativos:

Matrix conhecido antecipadamente: é construído de forma semelhante à matriz , mas, em vez de seções da imagem original, são usadas imagens de todos os símbolos usados ​​na geração de gráficos ASCII. Se o kit aplicável incluir caracteres, em seguida, a matriz terá um tamanho .
Resta apenas escolher uma matriz de modo a minimizar o valor de alguma função objetiva que caracteriza a diferença entre e trabalho . A seguinte dependência é usada como uma função:

Essa expressão combina essencialmente várias funções objetivas: quando é convertido para a distância euclidiana ao quadrado, em se aproxima da distância da divergência Kullback-Leibler e, quando - à distância de Itakura-Saito (divergência Itakura-Saito).

Seleção direta de matrizes produzido da seguinte forma: inicializado com valores aleatórios de 0 a 1, após o qual seus valores são atualizados iterativamente de acordo com a regra a seguir (o número de iterações é definido com antecedência):

Cada valor corresponde ao grau de semelhança caractere do conjunto com ª seção da imagem.


Portanto, para determinar qual caractere deve ser substituído seção, basta encontrar o valor máximo em quinta coluna da matriz . O número da linha na qual esse valor está localizado será o número do caractere desejado no conjunto. Você também pode inserir algum valor limite. e se o valor máximo encontrado for menor que esse limite, a seção da imagem será substituída por um espaço. O uso de um espaço pode ter um efeito positivo na aparência da imagem resultante em comparação com o uso de um símbolo com um baixo grau de similaridade.

Implementação

O algoritmo é implementado em C #. Os gráficos ASCII são gerados usando 95 caracteres (de 0x20 a 0x7E) com um tamanho de 11x23 pixels; A fonte usada é Courier. Abaixo está o código fonte da função para converter a imagem original em gráficos ASCII:

public static char[,] ConvertImage( Bitmap image, double beta, double threshold, ushort iterationsCount, ushort threadsNumber, Action<int> ProgressUpdated) { int charNumHor = (int)Math.Round((double)image.Width / glyphWidth); int charNumVert = (int)Math.Round((double)image.Height / glyphHeight); int totalCharactersNumber = charNumVert * charNumHor; int glyphSetSize = wNorm.ColumnCount; Matrix<double> v = SplitImage(image, charNumVert, charNumHor); Matrix<double> h = Matrix<double>.Build.Random( glyphSetSize, totalCharactersNumber, new ContinuousUniform()); int progress = 0; ushort step = (ushort)(iterationsCount / 10); for (ushort i = 0; i < iterationsCount; i++) { UpdateH(v, wNorm, h, beta, threadsNumber); if((i + 1) % step == 0) { progress += 10; if(progress < 100) { ProgressUpdated(progress); } } } var result = GetAsciiRepresentation(h, charNumVert, charNumHor, threshold); ProgressUpdated(100); return result; } 

Considere cada etapa individualmente:

1) Calculamos quantos caracteres cabem na largura e altura da imagem:

 int charNumHor = (int)Math.Round((double)image.Width / glyphWidth); int charNumVert = (int)Math.Round((double)image.Height / glyphHeight); 

Usando os valores calculados, dividimos a imagem original em blocos do tamanho necessário. Para cada bloco, escrevemos os valores da intensidade da cor do pixel na coluna correspondente da matriz (se necessário, expandimos a imagem original adicionando zero valores correspondentes a pixels brancos à matriz), após o que normalizamos todas as colunas:

 private static Matrix<double> SplitImage( Bitmap image, int charNumVert, int charNumHor) { Matrix<double> result = Matrix<double>.Build.Dense( glyphHeight * glyphWidth, charNumHor * charNumVert); for (int y = 0; y < charNumVert; y++) { for (int x = 0; x < charNumHor; x++) { for (int j = 0; j < glyphHeight; j++) { for (int i = 0; i < glyphWidth; i++) { byte color = 0; if ((x * glyphWidth + i < image.Width) && (y * glyphHeight + j < image.Height)) { color = (byte)(255 - image.GetPixel( x * glyphWidth + i, y * glyphHeight + j).R); } result[glyphWidth * j + i, charNumHor * y + x] = color; } } } } result = result.NormalizeColumns(2.0); return result; } 

2) Preencha a matriz valores aleatórios de 0 a 1:

 Matrix<double> h = Matrix<double>.Build.Random( glyphSetSize, totalCharactersNumber, new ContinuousUniform()); 

Aplicamos a regra de atualização um número especificado de vezes a seus elementos:

 for (ushort i = 0; i < iterationsCount; i++) { UpdateH(v, wNorm, h, beta, threadsNumber); if((i + 1) % step == 0) { progress += 10; if(progress < 100) { ProgressUpdated(progress); } } } 

A atualização direta dos elementos da matriz é implementada da seguinte forma (infelizmente, os problemas associados à divisão por zero são resolvidos usando algumas muletas):

 private static void UpdateH( Matrix<double> v, Matrix<double> w, Matrix<double> h, double beta, ushort threadsNumber) { const double epsilon = 1e-6; Matrix<double> vApprox = w.Multiply(h); Parallel.For( 0, h.RowCount, new ParallelOptions() { MaxDegreeOfParallelism = threadsNumber }, j => { for (int k = 0; k < h.ColumnCount; k++) { double numerator = 0.0; double denominator = 0.0; for (int i = 0; i < w.RowCount; i++) { if (Math.Abs(vApprox[i, k]) > epsilon) { numerator += w[i, j] * v[i, k] / Math.Pow(vApprox[i, k], 2.0 - beta); denominator += w[i, j] * Math.Pow(vApprox[i, k], beta - 1.0); } else { numerator += w[i, j] * v[i, k]; if (beta - 1.0 > 0.0) { denominator += w[i, j] * Math.Pow(vApprox[i, k], beta - 1.0); } else { denominator += w[i, j]; } } } if (Math.Abs(denominator) > epsilon) { h[j, k] = h[j, k] * numerator / denominator; } else { h[j, k] = h[j, k] * numerator; } } }); } 

3) O último passo é selecionar um símbolo adequado para cada seção da imagem, localizando os valores máximos nas colunas da matriz :

 private static char[,] GetAsciiRepresentation( Matrix<double> h, int charNumVert, int charNumHor, double threshold) { char[,] result = new char[charNumVert, charNumHor]; for (int j = 0; j < h.ColumnCount; j++) { double max = 0.0; int maxIndex = 0; for (int i = 0; i < h.RowCount; i++) { if (max < h[i, j]) { max = h[i, j]; maxIndex = i; } } result[j / charNumHor, j % charNumHor] = (max >= threshold) ? (char)(firstGlyphCode + maxIndex) : ' '; } return result; } 

A imagem resultante é gravada no arquivo html. O código fonte completo do programa pode ser encontrado aqui .

Exemplos de imagens geradas

Abaixo estão exemplos de imagens geradas em vários valores de parâmetros e o número de iterações. A imagem original tinha um tamanho de 407x500 pixels, respectivamente, a imagem resultante tinha um tamanho de 37x22 caracteres.

Conclusão

No algoritmo considerado, as seguintes desvantagens podem ser distinguidas:

1. Processamento de imagem longo: dependendo do tamanho da imagem e do número de iterações, seu processamento pode levar de várias dezenas de segundos a várias dezenas de minutos.
2. Processamento de baixa qualidade de imagens detalhadas. Por exemplo, uma tentativa de converter uma imagem de um rosto humano produz o seguinte resultado:
   
   
   

Ao mesmo tempo, reduzir o número de partes aumentando o brilho e o contraste da imagem pode melhorar significativamente a aparência da imagem resultante:


Em geral, apesar das desvantagens acima, podemos concluir que o algoritmo fornece resultados satisfatórios.