11

Tenho duas imagens (matrizes de pixels), sendo que uma delas está renderizada na tela. O objetivo é renderizar a segunda. No entanto performance é crítico e, no ambiente em que estou, renderizar cada pixel é bastante lento. Então renderizar a imagem inteira por cima da que já estava lá é impraticável. Nota: tudo precisa ser feito por software.

De forma a minimizar o tempo de renderização pretendo fazer um algoritmo que compute quais áreas das imagens foram alteradas para redesenhar apenas essas regiões. Considere o seguinte:

A = Tempo gasto na execução do algoritmo
R = Tempo gasto para inicializar a renderização de cada região
P = Tempo gasto para enviar um pixel
n = Número de regiões
m = Número de pixels em cada região

T = A + n×(R + m×P)

O objetivo é minimizar T.

Entendo que um algoritmo que minimize o número de regiões e o número de pixels enviados em cada uma é NP Complete e isso causaria um A exponencial. Então, como encontrar uma solução que seja boa, mesmo que não a melhor, em um período aceitável de tempo?

2 Respostas 2

10

Você não especificou o domínio da sua aplicação, mas dá pra imaginar que se trata de algo em que quadros são renderizados em sequência (como um vídeo, ou mais provavelmente, um jogo eletrônico) em um ambiente computacional restrito, e por isso é importante evitar custos desnecessários com a renderização na tela. Se esse entendimento está correto, então também se pode admitir que as imagens terão sempre as mesmas dimensões, certo? :)

Bom, supondo que é esse o caso, gostaria de propor uma solução para imagens manipuladas como matrizes bidimensionais de dimensões (n, m):

A = Matriz com os dados da imagem já renderizada
B = Matriz com os dados da nova imagem

A ideia inicial é calcular a diferença normalizada absoluta entre essas matrizes para produzir uma imagem binária de diferenças. As equações abaixo (com operações aritméticas sobre os elementos individuais das matrizes, isto é, Cij = Aij - Bij e Dij = abs(Cij/Cij)) demonstram a ideia:

(1) C = A - B
(2) D = abs(C / C)

Da equação 1 obtém-se uma nova matriz (C) com o resultado da diferença entre as duas matrizes originais (A e B). A equação 2 normaliza os valores em 0 ou 1, e ignora o signal. Assim, obtém-se a matriz binária (D).

A matriz binária D conterá o valor 0 nos pixels em que não há alteração e o valor 1 nos pixels em que há alteração entre as matrizes originais A e B. Por isso, ela serve como um mapa para as regiões em que há divergência entre as duas imagens. Note que esse cálculo tem complexidade quadrática em relação às dimensões das imagens (n*m).

No mesmo laço em que se calcula as diferenças da equação 1 já se pode calcular sua soma acumulada, de forma que com uma simples verificação é possível ignorar o melhor caso (se a soma acumulada for igual a 0, as imagens são completamente idênticas e não é necessário fazer mais nada a seguir).

Se a soma acumulada for diferente de 0, há diferenças entre as imagens e a matriz binária contém a identificação de onde essas diferenças ocorrem. Um algoritmo como o Crescimento de Região (Region Growing) pode ser então utilizado para segmentar as regiões de interesse.

A ideia é simples:

Inicialização:

  • Lista de pixels marcados como processados é definida vazia.
  • Lista de regiões é definida vazia.

Processamento:

  1. Na imagem binária (D), selecione aleatoriamente um pixel qualquer dentre os ainda não marcados como processados. Se não houver mais pixels não marcados, encerre.

  2. Marque o pixel atual como processado. Se ele tiver valor 0 (ou seja, não indica divergência), volte ao passo 1. Senão, prossiga.

  3. Crie uma nova região (uma matriz) e adicione o pixel a ela.

  4. Para cada pixel vizinho* ao pixel atual:

    4.1. Marque o pixel vizinho como processado. Se ele tiver valor 0 (ou seja, não indica divergência), volte ao passo 4. Senão, prossiga.

    4.2. Adicione o pixel vizinho à região.

    4.3. Processe recursivamente a partir do passo 4, fazendo com que o pixel vizinho seja o pixel atual.

  5. Volte ao passo 1.

* Pixels vizinhos são os 8 pixels "ao redor" do pixel atual.

Exemplificando, imagine que a comparação de duas imagens de dimensões (15 x 20), feita pelas equações 1 e 2 definidas no começo, produza a seguinte imagem binária (em que a cor branca representa 0 e a cor preta representa 1):

inserir a descrição da imagem aqui

Então, o processamento do algoritmo de Crescimento de Região pode ocorrer da seguinte forma (dependendo, é claro, dos pixels inicialmente selecionados aleatoriamente para cada nova região):

inserir a descrição da imagem aqui

Inicialmente (figura 0) tem-se apenas a imagem binária. Um pixel é sorteado aleatoriamente e inicia-se a primeira região (figura 1). Os vizinhos vão sendo adicionados recursivamente até que não exista mais vizinhança que indique divergências (figura 4). Dessa forma, um novo pixel é selecionado entre os ainda não marcados como processados (figura 5 - ilustra se, por acaso, já fosse sorteado um pixel numa região de diferença). E o processo se repete (figuras 6 em diante). Não está ilustrado nessas figuras, mas após o passo 14 (ou mesmo antes dos passos 5, 10 ou 13) o algoritmo ainda processaria os pixels das regiões vazias, mas simplesmente ignoraria-os até encontrar um de região de divergência ou até o final.

Ao final, as "áreas quadradas" que te interessam para renderização podem ser obtidas com os valores de menor e maior coordenadas x e y dos pixels em cada região:

inserir a descrição da imagem aqui

Note que esse algoritmo também tem complexidade quadratica no pior caso. De todas as formas, as diferenças devem ser pequenas no seu (suposto) domínio de problema, pois as alterações de um quadro para outro são localizadas. E como ignorar pixels de áreas sem divergência tem complexidade linear, no caso médio acho que pode ser uma boa solução. A manutenção da lista de pixels marcados como processados seguramente adiciona alguma complexidade, mas dependendo da estrutura de dados utilizada é possível se se ter a solução com complexidade em n*log(n).

Aliás, ao invés de calcular a imagem binária antes de processar o crescimento de região, pode-se fazer isso dinamicamente durante o processamento do algoritmo, utilizando o cálculo das duas equações do começo diretamente na avaliação de divergência de cada pixel (atual e vizinho), ao invés de uma consulta à matriz D.

Existem também outras abordagens que podem te ajudar, também baseadas em informações sobre a divergência entre as imagens (que, novamente, você pode pré-calcular ou não).

Uma possibilidade é utilizar o algoritmo Dividir e Juntar (Splitting and Merging), em que a ideia básica é ir subdividindo a imagem segundo uma Quadtree até encontrar regiões "uniformes" (e uniformidade, no seu caso, pode ser a maior quantidade possível de divergências na região). Removi a sugestão da divisão e conquista porque há outra resposta justamente com essa sugestão. :)

6
  • 1
    Creio que essa técnica é bastante interessante por reduzir o número de regiões, mas dependendo de como se deram as modificações os bounding boxes podem acabar bem grandes... Talvez uma boa saída nesse caso seria usar o algoritmo que você sugeriu no comentário à minha resposta (imagem integral) para analisar a "qualidade" de cada quadro (porcentagem de retrabalho). Se for boa o suficente, mantém, caso contrário pode-se tentar subdividir os quadros problemáticos.
    – mgibsonbr
    Commented 22/02/2014 às 22:53
  • 1
    Uma heurística poderia ser a soma abosoluta da imagem integral calculada sobre a imagem binária de diferenças. Se ela for próxima da área da imagem, isso indica que houve muitas mudanças. Dai, talvez seja mais eficiente (e fácil) simplesmente renderizar a imagem toda. :) Commented 22/02/2014 às 22:56
  • 2
    Um problema dessa sugestão é que se a matriz mudança for um "L" gigante, o bounding box fica muito maior que o realmente necessário. Talvez seja interessante aplicar o quadtree que o @mgibsonbr sugeriu em cada bounding box que isso gerar. Parece bastante bom. Quando tiver tempo experimentarei algumas variações dos dois. Commented 23/02/2014 às 0:04
  • É, realmente. Mas no final tudo depende do nível de detalhe que você quer chegar. Tendo os pixels agrupados em regiões seria possível até mesmo renderizá-los um a um (embora isso provavelmente não seja prático ou mesmo eficiente). E dependendo do lugar onde o "L" gigante se encontra, pode não ser possível separar bem suas partes (o @mgibsonbr apresentou um exemplo em que esse problema ocorre com três pixels). Além disso, talvez renderizar um "L" gigante mesmo com todos os pixels desnecessários seja suficiente para as suas metas de desempenho. Enfim, cabe mesmo uma avaliação das opções. :) Commented 23/02/2014 às 3:39
  • 1
    É interessante notar que esse algoritmo teria um resultado muito melhor na minha imagem de exemplo do que o que eu propus (3 regiões, 7 pixels repetidos). Eu acredito que na prática é uma solução melhor, exceto pro casos degenerados ("L gigante", "raio cortando a tela na diagonal", etc). Em outras palavras, esse possui um caso médio melhor, enquanto o meu possui um pior caso melhor. Reitero minha sugestão de usar esse e, se a qualidade dos bounding boxes for ruim (ex.: excessivamente grandes), aplicar o meu nas regiões problemáticas.
    – mgibsonbr
    Commented 23/02/2014 às 13:37
8

Você tem uma estimativa de R e P? Esse é um caso que permite grande flexibilidade nas soluções, uma vez que seu objetivo é "renderizar tudo o que mudou", mas não necessariamente "não renderizar nada que não mudou". Ou seja, ao criar uma região se admite incluir nela sub-regiões que não precisariam ser renderizadas novamente, se isso for aumentar a performance global. Por exemplo:

inserir a descrição da imagem aqui

Além disso, é importante determinar se seu objetivo é maximizar a performance real ou a performance percebida? Pois se seu algoritmo após N passos determinou um cenário em que a performance será X, vale a pena deixar o algoritmo continuar em busca de uma solução melhor ou não? (i.e. ao amentar A você sempre corre o risco de aumentar T, então se T = X for bom o suficiente pode ser melhor parar o algoritmo do que tentar reduzir n ou m ainda mais).

Sugestão de algoritmo: dividir e conquistar

Dadas essas características, sugiro implementar uma variação da representação em árvore quaternária: comece com sua imagem completa (n = 1) e veja quantos pixels são iguais (retrabalho) e sua proporção em relação ao todo. Considere se vale a pena multiplicar n por 4 para reduzir esse retrabalho ou não (com base em R e P). Se for, divida a imagem em quatro partes, e repita a análise para cada parte. Senão, pare.

inserir a descrição da imagem aqui

Esse algoritmo é sub-ótimo (repare nos 3 qudrados brancos em sequência na última imagem, que poderiam se juntar numa região só mas não vão), mas é simples, rápido e dá uma aproximação satisfatória. Você só tem que ajustar os parâmetros conforme as características de performance do seu caso particular.

Notas:

  • A complexidade do algoritmo é O(npixels * log4(npixels)) - pois ele dá [no máximo] uma passada na imagem inteira a cada divisão por 4.

  • Talvez seja interessante dividir a imagem por 2 e depois por 2 de novo (nos dois sentidos, pra ver qual tem resultado melhor) em vez de dividir direto por 4. No exemplo acima (assumindo que você continuou e dividiu a imagem de novo, obtendo n = 11) isso reduziria n em 2, às custas de um maior A.

  • Se P e R forem muito grandes em relação a A (i.e. não há problema num algoritmo mais custoso, desde que ele esprema cada pixel da sua imagem), talvez valha a pena uma busca empregando heurística, por exemplo A* ("A-estrela").

    Eu comecei a pensar em algo nesse caminho, mas diante da complexidade para implementar e testar, e diante da presença de uma solução mais simples, não dei prosseguimento. Se a solução proposta não for boa o bastante, posso acrescentar uma resposta alternativa nesse sentido.

3
  • 1
    Eu acho a abordagem de "dividir e juntar" (ou "conquistar") igualmente bacana para o problema. :) Para facilitar a avaliação da "uniformidade" das janelas em cada nível, pode-se utilizar uma imagem integral previamente calculada sobre os valores da diferença entre a imagem renderizada e a nova. Commented 22/02/2014 às 21:42
  • 1
    Uma janela totalmente uniforme (isto é, em que todos os pixels foram alterados) tem soma igual à sua área, enquanto que uma janela totalmente não uniforme (isto é, em que nenhum pixel foi alterado) tem soma zero. Com uma imagem integral dá pra achar as somas a cada nível da Quadtree de forma muito eficiente, e permite definir um limiar para fazer como você sugeriu e interromper o processamento ao se chegar em um nível "aceitável" de uniformidade na divisão da imagem. Commented 22/02/2014 às 21:53
  • 1
    @LuizVieira Ótima sugestão! Dessa forma não seria necessário dar mais uma passada na imagem a cada nível, como esperava, mas sim fazer essa análise em tempo constante - reduzindo a complexidade para O(log4(npixels)).
    – mgibsonbr
    Commented 22/02/2014 às 22:34

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .