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:
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.
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.
Crie uma nova região (uma matriz) e adicione o pixel a ela.
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.
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):
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):
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:
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. :)