Elemar DEV

Negócios, tecnologia e desenvolvimento

Exemplo prático (e útil) de Emitting e IL

Olá pessoal, tudo certo?

Aplicação de filtros em imagens (com alto desempenho e flexibilidade)! Esse é o exemplo prático que apresento hoje para Emitting e IL.

Se você acompanha meu blog há algum tempo e não consegue ver utilidadade prática para Emitting e IL, eis um exemplo a considerar. Se você já faz emitting, perceberá o quanto a utilização de uma DSL pode colaborar com seu trabalho.

No post de hoje:

  • apresento uma pequena contextualização sobre o tema “tratamento de imagens digitais”;
  • apresento uma solução genérica, escrita toda em C#, para aplicação de filtros;
  • desenvolvo uma solução usando Emitting (e IL, consequentemente) com performance superior a obtida com C# puro (bem longa e complicada. Se prefirir, passe direto por ela);
  • mostro como é possível fazer emitting com mais facilidade usando FluentIL.

Todo o código de hoje está incluído como demo do projeto FluentIL e está disponível em https://github.com/ElemarJR/FluentIL

Sem mais delongas…

Contextualização para “tratamento de imagens digitais”

Algumas palavras imagens digitais

Toda imagem digital pode ser analizada como uma matriz de pontos coloridos. Essa matriz tem uma largura (a da imagem) e uma altura (duas dimensões). Logo, cada ponto dessa matriz possui uma coordenada.

Cada ponto da matriz (coordenada) está associado a uma cor. Essa cor é representada pela combinação (em diferentes intensidades) de cores básicas. Os sistemas de representação mais comum utilizados com imagens digitais têm como cores básicas o vermelho (R), o verde (G) e o azul (B).

Em sua representação mais simples, utiliza-se um número inteiro, de um byte (0..255), para representar cada elemento (cor básica) de uma cor. Com o sistema com RGB, utilizando um byte para cada cor, podemos representar 16777316 combinações diferentes (256x256x256)

Alterar uma imagem consiste em modificar o tamanho da matriz (consequentemente, largura e altura da imagem) ou modificar os valores das cores associados a cada coordenada.

Algumas palavras sobre filtros

Tratar uma imagem digital significa alterar seu estado (tamanho ou cores). Tratamentos mais comuns, como suavização, realce, geração de negativos, e detecção de limites ocorrem por meio de alguma computação entre um ponto da imagem e seus adjacentes.

Uma forma comum para representação de um filtro (resumo da computação que será realizada nos pontos de uma imagem) é a seguinte:

image

Na representação desse filtro, temos:

  • Uma matriz, representando a relação do ponto que está sendo processado (no centro) com seus adjacentes,onde cada casa indica o “peso” de cada ponto na composição da nova cor;
  • Um fator (multiplicação), que é utilizado para aumentar ou diminuir o peso da cor gerada pela combinação representada na matriz;
  • Um Bias (soma), que é utilizado para eventuais “correções” no resultado das operações executadas com a matriz e com o fator.

A propósito, o filtro indicado no exemplo funciona como um “detector de bordas” em uma imagem. Já o filtro que segue geraria o negativo de uma imagem

image

 

A aplicação dos dois filtros indicados em uma imagem como a que segue:

image

… geraria o seguinte resultado:

image

Como você já deve ter entendido, aplicar um filtro corresponde a realizar sua computação para cada ponto de uma imagem.

Representando filtros

Representar um filtro, em C#, é relativamente simples. Para o exemplo de hoje, criei a seguinte representação:

public struct Filter
{
  public readonly double [] Matrix;
  public readonly int Size;
  public readonly int Bias;

  public Filter(double[] matrix, int size = 3, int bias = 0) : this()
  {
    this.Matrix = matrix;
    this.Size = size;
    this.Bias = bias;

    var expectedLength = this.Size * this.Size;

    if (
      this.Size % 2 == 0 ||
      this.Matrix.Length != expectedLength
      )
      throw new ArgumentException("Matrix size is invalid!");
  }
}

Como pode perceber, minha representação não possui um atributo para o Fator. Para fins de simplicidade, optei por deixar os fatores constantes. Observe agora alguns filtros representados usando essa estrutura:

public static class Filters
{
  public static Filter Negative
  {
    get
    {
      return new Filter
      ( new double[] { -1 }, 1, 255 );
    }
  }

  public static Filter Edge
  {
    get
    {
      return new Filter
      (
          new double[] {
               1,  2,  1,
               0,  0,  0,
              -1, -2, -1,
          }, 3, 0 );
    }
  }

  public static Filter Sharpen
  {
    get
    {
      return new Filter (
          new double[] {
              -1, -1, -1,
              -1,  9, -1,
              -1, -1, -1
          }, 3, 0 );
    }
  }

  public static Filter Blur
  {
    get
    {
      return new Filter (
          new double[] {
              1, 1, 1, 1, 1,
              1, 1, 1, 1, 1,
              1, 1, 1, 1, 1,
              1, 1, 1, 1, 1,
              1, 1, 1, 1, 1
          }, 5, 0);
    }
  }
}

Como pode perceber, criar um novo filtro é operação simples. Repare também que as matrizes podem ter dimensões diferentes de 3×3.

Com algum trabalho, pode-se fazer uma interface para que o usuário defina novos filtros e esses não fiquem restritos ao código fonte.

Gostou da idéia? Que tal colaborar com o projeto desenvolvendo essa interface para esse exemplo?

Aplicando filtros usando somente código C#

Executando a aplicação de filtros somente com código C#

Já pegou o código fonte? Não? Então baixe agora e execute o aplicativo “ImageProcessing”, carregue uma imagem no menu file (prefira imagens grandes, para entender melhor o propósito do post) e aplique um dos filtros disponíveis no menu FiltersCS.

image

Observe que logo após a execução do filtro uma caixa de mensagem é apresentada indicando o tempo de execução do filtro.

Por questões de objetividade, não vou apresentar o código fonte para composição da interface ou operação básica do bitmap (isso está disponível em https://github.com/ElemarJR/FluentIL)

O código principal para aplicação do filtro em C#

A aplicação do filtro ocorre em um método que:

  • recebe um array com todos os bytes da imagem e outro onde devem ser colocados os novos valores correspondentes a resultante da aplicação do filtro;
  • além de algumas propriedades da imagem;
  • propriedades do filtro que está sendo aplicado.

Observe:

static void Run(byte[] src, byte[] dst,
    int stride, int bytesPerPixel, double[] filter, 
        int filterWidth, int bias)
{
  int srcBytesCount = src.Length;
  int filterCount = filter.Length;
  int filterHeight = filter.Length / filterWidth;

  for (int iDst = 0; iDst < srcBytesCount; iDst++)
  {
    double pixelsAccum = 0;
    double filterAccum = 0;

    for (int i = 0; i < filterCount; i++)
    {
      int yFilter = i / filterHeight;
      int xFilter = i % filterWidth;

      int iSrc = iDst + stride * (yFilter - filterHeight / 2) +
                bytesPerPixel * (xFilter - filterWidth / 2);

      if (iSrc >= 0 && iSrc < srcBytesCount)
      {
          pixelsAccum += filter[i] * src[iSrc];
          filterAccum += filter[i];
      }
    }

    if (filterAccum != 0)
        pixelsAccum /= Math.Abs(filterAccum);

    pixelsAccum += bias;
    dst[iDst] = pixelsAccum < 0 ? (byte)0 : 
			(pixelsAccum > 255 ? (byte)255 : (byte)pixelsAccum);
  }
}

Acredito que esse código seja simples entender. Basicamente, cada byte de dados da imagem está sendo processado conforme o filtro recebido.

O problema com essa implementação é a grande quantidade de “intruções” executadas para cada byte. Além do loop para percorrer a matriz do filtro, há o fato de que, na maioria dos casos, grande parte dos elementos da matriz estão zerados e não precisariam ser considerados (não produzem qualquer diferença no resultado final).

Gerando código on-the-fly para aplicação de filtros usando a biblioteca de Emitting do .NET Framework

Uma solução para otimização de um cenário como o exposto até aqui passa pela geração de código executável on-the-fly. Na prática, o que desejamos é:

  • evitar a execução de loops para percorrer cada elemento da matriz de filtros;
  • desconsiderar qualquer atividade para elementos da matriz que estejam “zerados”;
  • garantir um “IL” econômico para tratamento da imagem.

Como resultado, a aplicação do filtro fica extremamente mais veloz (até 3 vezes mais rápida, em meu computador)

Código principal para geração do método on-the-fly

Assim como procedi na apresentação do código C# para aplicação de filtro, mais uma vez, não apresento código de apoio.

Observe o código com Emitting (e IL) para geração de código on-the-fly:

static DynamicMethod CreateFilterMethodIL_Reference(byte[] src, byte[] dst,
    int stride, int bytesPerPixel, double[] filter, int filterWidth, int bias)
{
    int filterHeight = filter.Length / filterWidth;

    DynamicMethod result = new DynamicMethod(
        "DoFilter",
        typeof(void),
        new Type[] { typeof(byte[]), typeof(byte[]) },
        typeof(IlApplier));

    bool allwaysFilterNeg = true;
    bool neverFilterNeg = true;
    double negs = 0;
    for (int i = 0; i < filter.Length; i++)
    {
        if (filter[i] > 0) allwaysFilterNeg = false;
        if (filter[i] < 0)
        {
            neverFilterNeg = false;
            negs += filter[i];
        }
    }
    if (filter[filter.Length / 2] >= Math.Abs(negs)) neverFilterNeg = true;


    var ilgen = result.GetILGenerator();

    // criando as três variáveis usadas no corpo do método
    ilgen.DeclareLocal(typeof(int));        // iDst
    ilgen.DeclareLocal(typeof(double));     // pixelsAccum 
    ilgen.DeclareLocal(typeof(double));     // filterAccum

    ilgen.Emit(OpCodes.Ldc_I4_0);           // iDst = 0;
    ilgen.Emit(OpCodes.Stloc_0);

    // define um ponto de retorno .. goto .. 
    var top = ilgen.DefineLabel();
    ilgen.MarkLabel(top);

    ilgen.Emit(OpCodes.Ldc_R8, 0.0);
    ilgen.Emit(OpCodes.Dup);
    ilgen.Emit(OpCodes.Stloc_1);            // pixelsAccum = 0
    ilgen.Emit(OpCodes.Stloc_2);            // filterAccum = 0

    for (int i = 0; i < filter.Length; i++)
    {
        if (filter[i] == 0) continue;

        int yFilter = i / filterHeight;
        int xFilter = i % filterWidth;

        int offset = stride * (yFilter - filterHeight / 2) +
                bytesPerPixel * (xFilter - filterWidth / 2);

        var lessThanZero = ilgen.DefineLabel();
        var greaterThan = ilgen.DefineLabel();
        var loopBottom = ilgen.DefineLabel();

        // primeiro vetor na pilha
        ilgen.Emit(OpCodes.Ldarg_0);

        ilgen.Emit(OpCodes.Ldloc_0);
        if (offset > 0)
        {
            ilgen.Emit(OpCodes.Ldc_I4, offset);
            ilgen.Emit(OpCodes.Add);            // iDst + offset
        }

        ilgen.Emit(OpCodes.Dup);
        ilgen.Emit(OpCodes.Dup);

        ilgen.Emit(OpCodes.Ldc_I4_0);
        ilgen.Emit(OpCodes.Blt_S, lessThanZero); // if (iDst < 0)

        ilgen.Emit(OpCodes.Ldc_I4, src.Length);
        ilgen.Emit(OpCodes.Bge_S, greaterThan); // if (iDst > src.Length)

        ilgen.Emit(OpCodes.Ldelem_U1);
        ilgen.Emit(OpCodes.Conv_R8); // obtém o elemento de cor ne vetor

        if (filter[i] != 1) // se filtro for 1, não altera valor de referência
        {
            if (filter[i] == -1)
            {
                ilgen.Emit(OpCodes.Neg); // inverte o valor
            }
            else
            {
                // produto
                ilgen.Emit(OpCodes.Ldc_R8, filter[i]);
                ilgen.Emit(OpCodes.Mul);
            }
        }

        ilgen.Emit(OpCodes.Ldloc_1);
        ilgen.Emit(OpCodes.Add);
        ilgen.Emit(OpCodes.Stloc_1); // atualizando pixelsAccum

        ilgen.Emit(OpCodes.Ldc_R8, filter[i]);
        ilgen.Emit(OpCodes.Ldloc_2);
        ilgen.Emit(OpCodes.Add);
        ilgen.Emit(OpCodes.Stloc_2); // filterAccum

        ilgen.Emit(OpCodes.Br, loopBottom);

        // organizando a pilha para o próximo elemento do filtro
        ilgen.MarkLabel(lessThanZero);
        ilgen.Emit(OpCodes.Pop);
        ilgen.MarkLabel(greaterThan);
        ilgen.Emit(OpCodes.Pop);
        ilgen.Emit(OpCodes.Pop);

        ilgen.MarkLabel(loopBottom);
    }

    ilgen.Emit(OpCodes.Ldarg_1);        // dst
    ilgen.Emit(OpCodes.Ldloc_0);        // iDst

    var shouldSkipDivide = ilgen.DefineLabel();
    var copyQuotient = ilgen.DefineLabel();
    var pixelIsBlack = ilgen.DefineLabel();
    var pixelIsWhite = ilgen.DefineLabel();
    var done = ilgen.DefineLabel();

    ilgen.Emit(OpCodes.Ldloc_1);
    ilgen.Emit(OpCodes.Ldloc_2);

    ilgen.Emit(OpCodes.Dup);
    ilgen.Emit(OpCodes.Ldc_R8, 0.0);
    ilgen.Emit(OpCodes.Beq_S, shouldSkipDivide); // if (filterAccum != 0)

    if (!neverFilterNeg)
    {
        if (allwaysFilterNeg)
        {
            ilgen.Emit(OpCodes.Neg);
        }
        else
        {
            var absFilterAccum = ilgen.DefineLabel();
            ilgen.Emit(OpCodes.Dup);
            ilgen.Emit(OpCodes.Ldc_R8, 0.0);
            ilgen.Emit(OpCodes.Bge_S, absFilterAccum);
            ilgen.Emit(OpCodes.Neg);
            ilgen.MarkLabel(absFilterAccum);
        }
    }

    ilgen.Emit(OpCodes.Div); // pixelAccum / filterAccum
    ilgen.Emit(OpCodes.Br_S, copyQuotient);

    ilgen.MarkLabel(shouldSkipDivide);
    ilgen.Emit(OpCodes.Pop);

    ilgen.MarkLabel(copyQuotient);
    if (bias > 0)
    {
        ilgen.Emit(OpCodes.Ldc_R8, (double)bias);
        ilgen.Emit(OpCodes.Add);
    }

    ilgen.Emit(OpCodes.Dup);
    ilgen.Emit(OpCodes.Dup);

    ilgen.Emit(OpCodes.Ldc_R8, 0.0);
    ilgen.Emit(OpCodes.Blt_S, pixelIsBlack); // if (pixelsAccum < 0)

    ilgen.Emit(OpCodes.Ldc_R8, 255.0);
    ilgen.Emit(OpCodes.Bgt_S, pixelIsWhite); // if (pixelsAccum > 255)

    ilgen.Emit(OpCodes.Conv_U1); // cast para byte
    ilgen.Emit(OpCodes.Br_S, done);

    ilgen.MarkLabel(pixelIsBlack);
    ilgen.Emit(OpCodes.Pop);
    ilgen.Emit(OpCodes.Pop);
    ilgen.Emit(OpCodes.Ldc_I4_S, 0);
    ilgen.Emit(OpCodes.Br_S, done); // setando para 0

    ilgen.MarkLabel(pixelIsWhite);
    ilgen.Emit(OpCodes.Pop);
    ilgen.Emit(OpCodes.Ldc_I4_S, 255); // setando 255

    ilgen.MarkLabel(done);
    ilgen.Emit(OpCodes.Stelem_I1); // dst[iDst] = value;

    ilgen.Emit(OpCodes.Ldloc_0);
    ilgen.Emit(OpCodes.Ldc_I4_1);
    ilgen.Emit(OpCodes.Add);
    ilgen.Emit(OpCodes.Dup);
    ilgen.Emit(OpCodes.Stloc_0);    // iDst ++

    ilgen.Emit(OpCodes.Ldc_I4, src.Length);
    ilgen.Emit(OpCodes.Blt, top);

    ilgen.Emit(OpCodes.Ret);
    return result;
}

Começo o método definindo uma “assinatura” para o método que estamos escrevendo para aplicação de filtro. Repare que recebo apenas dois vetores de bytes (um com os valores atuais, outro onde devo colocar os bytes com os reultados). Logo depois, faço uma rápida análise do filtro que está será aplicado pelo método que estamos gerando. Nessa análise, identifico se a matriz do filtro contém fatores negativos (será util no emitting, mais adiante).

Método com assinatura definida, hora de definir que variáveis locais serão necessárias . Defino um ponto de retorno que é inicio o bloco de código que varre todos os bytes da imagem.

Depois, o código que trata cada elemento da matriz de filtro. Logo de cara, dispenso todos os elementos que estejam zerados. Depois, faço emitting para tratar produto e acumulo dos valores dos pontos dos bytes adjacentes.

Por fim, calculo o resultado da matriz (dividindo o somatório pelos pesos dos filtros) e aplici o bias. Além disso, garanto que o novo valor esteja no intervalo válido (0..255), armazenando o resultado no array destino.

Pronto, mas verboso, não acha?!

Gerando código on-the-fly para aplicação de filtros usando a biblioteca EasyIL

Como disse, o tempo de processamento de filtros usando os métodos gerados on-the-fly é muito melhor do que aquele atingido usando C# puro. Mas.. como é complicado e verboso! (Eu até gosto!)

O principal problema com emitting é a “proximidade” com IL. Isso implica em nada de loops com For ou desvios condicionais If..Else. Para diminuir a dor, usamos o EasyIL (nosso projeto open-source desenvolvido aqui no blog).

static DynamicMethod CreateFilterMethodIL(byte[] src, byte[] dst,
    int stride, int bytesPerPixel, double[] filter, int filterWidth, int bias)
{
    #region filter analysis
            
    int filterHeight = filter.Length / filterWidth;

    bool allwaysFilterNeg = true;
    bool neverFilterNeg = true;
    double negs = 0;
    for (int i = 0; i < filter.Length; i++)
    {
        if (filter[i] > 0) allwaysFilterNeg = false;
        if (filter[i] < 0)
        {
            neverFilterNeg = false;
            negs += filter[i];
        }
    }

    #endregion

    if (filter[filter.Length / 2] >= Math.Abs(negs)) neverFilterNeg = true;

    var result = IL.NewMethod()
        .WithParameter(typeof(byte[]), "src")
        .WithParameter(typeof(byte[]), "dest")
        .WithVariable(typeof(double), "pixelsAccum")
        .WithVariable(typeof(double), "filterAccum")
        .Returns(typeof(void))

        .For("iDst", 0, src.Length - 1)
            .LdcR8(0.0)
            .Dup()
            .Stloc("pixelsAccum", "filterAccum")

            .Repeater(0, filter.Length - 1, 1,
                (ind, body) => filter[ind] != 0,
                (index, body) =>
                {
                    body
                        .Ldarg("src")
                        .Ldloc("iDst")
                        .Add(IlApplier.ComputeOffset(index, filterWidth, stride, bytesPerPixel))

                        .Dup()
                        .LdcI4(-1)
                        .Ifgt()
                            .Dup()
                            .LdcI4(src.Length)
                            .Iflt()
                                .LdelemU1()
                                .ConvR8()
                                .Mul(filter[index])

                                .Ldloc("pixelsAccum")
                                .Add()
                                .Stloc("pixelsAccum")

                                .Ldloc("filterAccum")
                                .Add(filter[index])
                                .Stloc("filterAccum")

                            .Else()
                                .Pop().Pop()
                            .EndIf()
                        .Else()
                            .Pop().Pop()
                        .EndIf();
                }
            )

            .Ldarg("dest")
            .Ldloc("iDst")

            .Ldloc("pixelsAccum", "filterAccum")

            .Dup()
            .LdcR8(0)
            .IfNoteq()
                .EmitIf(!neverFilterNeg && allwaysFilterNeg, (r) => r.Neg())
                .EmitIf(!neverFilterNeg && !allwaysFilterNeg, (r) => r
                    .Dup().LdcR8(0.0)
                    .Iflt()
                        .Neg()
                    .EndIf()
                )
                .Div()
            .Else()
                .Pop()
            .EndIf()

            .Add((double)bias)

            .EnsureLimits(0.0, 255.0)
            .ConvU1()
            .StelemI1()
        .Next()
        .Ret();

    return result;
}

Tudo ficou mais simples, não acham!?

Bom, por hoje, era isso!

Smiley piscando

10 comentários em “Exemplo prático (e útil) de Emitting e IL

  1. Leandro Daniel
    11/02/2011

    Elemar, o que dizer… Sempre um posto divertido e instrutivo! Já tinha visto algumas implementações de filtros antes, mas sempre eram carregadas de muita matemática. Gostei muito da implementação que você fez, e toda a sequência de posts (de IL, bits etc) estão engendrando algo grande.

    Sinceramente, e falando muito sério, acho que você deveria dedicar-se na escrita de livros sobre algoritmos e assuntos afins (com foco na plataforma .NET). 🙂

    Obrigado por mais um post!

    Abraços,

    Leandro Daniel

  2. Pingback: Tweets that mention Exemplo prático (e útil) de Emitting e IL « Elemar DEV -- Topsy.com

  3. Olá Elemar, o Leandro está certo sobre os livros e também sobre os filtros, os códigos ficaram ótimos e fáceis de ler.

    Agora um detalhe legal de colocar no post, é uma comparação de desempenho utilizando as duas formas.

    Abraços.

  4. Pingback: FluentIL – Parte 3 – DSL Improvements « Elemar DEV

  5. Ari C. Raimundo
    23/02/2011

    Olá Elemar,

    Já tentou alterar o método Run da classe CsApplier para que o primeiro “for” seja em paralelo? Testei aqui e o ganho de performance (para grandes imagens) parece ser interessante.

    Parallel.For(0, srcBytesCount, (iDst) =>
    {
    double pixelsAccum = 0;
    double filterAccum = 0;

    for (int i = 0; i = 0 && iSrc < srcBytesCount)
    {
    pixelsAccum += filter[i] * src[iSrc];
    filterAccum += filter[i];
    }
    }

    if (filterAccum != 0)
    pixelsAccum /= Math.Abs(filterAccum);

    pixelsAccum += bias;
    dst[iDst] = pixelsAccum 255 ?
    (byte)255 : (byte)pixelsAccum);
    });

    Ótimo post !

    Abraços.

  6. Pingback: Proxies dinâmicos usando Emitting (avançado) – Parte 1/3 « Elemar DEV

  7. Pingback: Proxies dinâmicos usando Emitting (avançado) – Parte 2/3 « Elemar DEV

  8. Pingback: Aprender Intermediate Language é importante! Entenda o porquê. « Elemar DEV

  9. Pingback: Meu (nem tão) breve histórico com metaprogramação em .NET - Elemar Jr

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

Informação

Publicado às 10/02/2011 por em Emitting, Post e marcado , , , , , .

Estatísticas

  • 918.503 hits
%d blogueiros gostam disto: