Já existem muitos artigos excelentes escritos sobre o algoritmo Seam Carving , mas não pude resistir à tentação de explorar este algoritmo elegante, poderoso e ainda assim simples por conta própria e escrever sobre minha experiência pessoal com ele. Outro ponto que chamou minha atenção (como criador do repositório de algoritmos de javascript ) foi o fato de que a abordagem de Programação Dinâmica (DP) pode ser aplicada sem problemas para resolvê-lo. E, se você é como eu e ainda está em sua jornada de “algoritmos de aprendizagem”, esta solução algorítmica pode enriquecer seu arsenal pessoal de DP.
Portanto, com este artigo, quero fazer três coisas:
- Fornece um redimensionador interativo com reconhecimento de conteúdo para que você possa brincar com o redimensionamento de suas próprias imagens
- Explique a ideia por trás do algoritmo Seam Carving
- Explique a abordagem de programação dinâmica para implementar o algoritmo (usaremos TypeScript para isso)
Redimensionamento de imagem com reconhecimento de conteúdo
O redimensionamento de imagem com reconhecimento de conteúdo pode ser aplicado quando se trata de alterar as proporções da imagem (ou seja, reduzir a largura, mantendo a altura) e quando a perda de algumas partes da imagem não é desejável. Nesse caso, fazer o dimensionamento direto da imagem distorceria os objetos nele. Para preservar as proporções dos objetos enquanto mudamos as proporções da imagem, podemos usar o algoritmo Seam Carving que foi introduzido por Shai Avidan e Ariel Shamir .
O exemplo abaixo mostra como a largura da imagem original foi reduzida em 50% usando redimensionamento sensível ao conteúdo (imagem à esquerda) e dimensionamento direto (imagem à direita). Neste caso específico, a imagem da esquerda parece mais natural, pois as proporções dos balões foram preservadas.
A ideia do algoritmo Seam Carving é encontrar a emenda (sequência contínua de pixels) com a menor contribuição para o conteúdo da imagem e então esculpi-la (removê-la). Este processo se repete indefinidamente até obtermos a largura ou altura de imagem necessária. No exemplo abaixo, você pode ver que os pixels do balão de ar quente contribuem mais para o conteúdo da imagem do que os pixels do céu. Assim, os pixels do céu são removidos primeiro.
Encontrar a costura com a energia mais baixa é uma tarefa computacionalmente cara (especialmente para imagens grandes). Para tornar a pesquisa de costura mais rápida, a abordagem de programação dinâmica pode ser aplicada (veremos os detalhes de implementação abaixo).
Remoção de objetos
A importância de cada pixel (chamada energia do pixel) está sendo calculada com base na sua cor ( R, G, B, A) diferença entre dois pixels vizinhos. Agora, se definirmos a energia do pixel para algum nível realmente baixo artificialmente (ou seja, desenhando uma máscara em cima deles), o algoritmo Seam Carving executaria uma remoção de objeto para nós gratuitamente.
Mais exemplos
Aqui estão mais alguns exemplos de como o algoritmo lida com planos de fundo mais complexos.
As montanhas ao fundo estão sendo reduzidas suavemente, sem costuras visíveis.
O mesmo vale para as ondas do mar. O algoritmo preservou a estrutura da onda sem distorcer os surfistas.
Precisamos ter em mente que o algoritmo Seam Carving não é uma bala de prata e pode falhar ao redimensionar as imagens onde a maioria dos pixels são bordas (parece importante para o algoritmo). Nesse caso, ele começa a distorcer até as partes importantes da imagem. No exemplo abaixo, o redimensionamento da imagem com reconhecimento de conteúdo parece muito semelhante a um dimensionamento direto, pois para o algoritmo todos os pixels parecem importantes e é difícil para ele distinguir o rosto de Van Gogh do fundo.
Como funcionam os algoritmos do Seam Carving
Imagine que temos uma 1000 x 500 pximagem e queremos alterar seu tamanho para 500 x 500 pxtorná-la quadrada (digamos que a proporção do quadrado se encaixaria melhor no feed do Instagram). Podemos querer configurar vários requisitos para o processo de redimensionamento neste caso:
- Preserve as partes importantes da imagem (ou seja, se havia 5 árvores antes do redimensionamento, queremos ter 5 árvores também após o redimensionamento).
- Preserve as proporções das partes importantes da imagem (ou seja, as rodas dos carros circulares não devem ser espremidas nas rodas elípticas)
Para evitar alterar as partes importantes da imagem podemos encontrar a sequência contínua de pixels (a costura) , que vai de cima para baixo e tem a menor contribuição para o conteúdo da imagem (evita partes importantes) e depois removê-la. A remoção da costura reduzirá a imagem em 1 pixel. Vamos então repetir este passo até que a imagem tenha a largura desejada.
A questão é como definir a importância do pixel e sua contribuição para o conteúdo (no artigo original os autores estão usando o termo energia do pixel ). Uma das maneiras de fazer isso é tratar todos os pixels que formam as bordas como importantes. No caso de um pixel fazer parte da aresta sua cor teria uma diferença maior entre os vizinhos (pixels esquerdo e direito) do que o pixel que não faz parte da aresta.
Assumindo que a cor de um pixel é representada por 4 números ( R– vermelho, G– verde, B– azul, A– alfa), podemos usar a seguinte fórmula para calcular a diferença de cor (a energia do pixel):
Onde:
mEnergy– Energia (importância) do pixel do meio ([0..626]se arredondado)lR– Valor do canal vermelho para o pixel esquerdo ([0..255])mR– Valor do canal vermelho para o pixel do meio ([0..255])rR– Valor do canal vermelho para o pixel certo ([0..255])lG– Valor do canal verde para o pixel esquerdo ([0..255])- e assim por diante…
Na fórmula acima, estamos omitindo o canal alfa (transparência), por enquanto, assumindo que não há pixels transparentes na imagem. Posteriormente, usaremos o canal alfa para mascarar e remover objetos.
Agora, como sabemos como encontrar a energia de um pixel, podemos calcular o chamado mapa de energia que conterá as energias de cada pixel da imagem. Em cada etapa de redimensionamento, o mapa de energia deve ser recalculado (pelo menos parcialmente, mais sobre isso abaixo) e deve ter o mesmo tamanho da imagem.
Por exemplo, na 1ª etapa de redimensionamento teremos uma 1000 x 500imagem e um 1000 x 500mapa de energia. Na segunda etapa de redimensionamento, removeremos a costura da imagem e recalcularemos o mapa de energia com base na nova imagem reduzida. Assim, obteremos uma 999 x 500imagem e um 999 x 500mapa energético.
Quanto mais alta a energia do pixel, maior será a probabilidade de ele fazer parte de uma borda, sendo importante para o conteúdo da imagem e menos provável que seja necessário removê-lo.
Para visualizar o mapa de energia, podemos atribuir uma cor mais brilhante aos pixels com maior energia e cores mais escuras aos pixels com menor energia. Aqui está um exemplo artificial de como pode ser a parte aleatória do mapa de energia. Você pode ver a linha brilhante que representa a borda e que queremos preservar durante o redimensionamento.
Aqui está um exemplo real do mapa de energia para a imagem de demonstração que você viu acima (com balões de ar quente).
Podemos usar o mapa de energia para encontrar as junções (uma após a outra) com a energia mais baixa e, ao fazer isso, decidir quais pixels devem ser excluídos.
Encontrar a costura com a energia mais baixa não é uma tarefa trivial e requer a exploração de muitas combinações de pixels possíveis antes de tomar a decisão. Aplicaremos a abordagem de programação dinâmica para acelerá-la.
No exemplo abaixo, você pode ver o mapa de energia com a primeira costura de energia mais baixa encontrada para ele.
Nos exemplos acima, estávamos reduzindo a largura da imagem. Uma abordagem semelhante pode ser adotada para reduzir a altura da imagem. Precisamos “girar” a abordagem:
- comece a usar vizinhos de pixel superior e inferior (em vez dos esquerdo e direito ) para calcular a energia do pixel
- ao procurar uma costura, precisamos mover da esquerda para a direita (em vez de de cima para baixo )
Implementação em TypeScript
Você pode encontrar o código-fonte e as funções mencionadas abaixo no repositório js-image-carver .
Para implementar o algoritmo, usaremos o TypeScript. Se você deseja uma versão JavaScript, pode ignorar (remover) as definições de tipo e seus usos.
Por razões de simplicidade, vamos implementar o algoritmo de escultura de costura apenas para a redução da largura da imagem .
Redimensionamento de largura sensível ao conteúdo (a função de entrada)
Primeiro, vamos definir alguns tipos comuns que usaremos ao implementar o algoritmo.
// Type that describes the image size (width and height).
type ImageSize = { w: number, h: number };
// The coordinate of the pixel.
type Coordinate = { x: number, y: number };
// The seam is a sequence of pixels (coordinates).
type Seam = Coordinate[];
// Energy map is a 2D array that has the same width and height
// as the image the map is being calculated for.
type EnergyMap = number[][];
// Type that describes the image pixel's RGBA color.
type Color = [
r: number, // Red
g: number, // Green
b: number, // Blue
a: number, // Alpha (transparency)
] | Uint8ClampedArray;Em alto nível, o algoritmo consiste nas seguintes etapas:
- Calcule o mapa de energia para a versão atual da imagem.
- Encontre a costura com a energia mais baixa com base no mapa de energia (é aqui que aplicaremos a Programação Dinâmica).
- Exclua a costura com a costura de menor energia da imagem.
- Repita até que a largura da imagem seja reduzida ao valor desejado.
type ResizeImageWidthArgs = {
img: ImageData, // Image data we want to resize.
toWidth: number, // Final image width we want the image to shrink to.
};
type ResizeImageWidthResult = {
img: ImageData, // Resized image data.
size: ImageSize, // Resized image size (w x h).
};
// Performs the content-aware image width resizing using the seam carving method.
export const resizeImageWidth = (
{ img, toWidth }: ResizeImageWidthArgs,
): ResizeImageWidthResult => {
// For performance reasons we want to avoid changing the img data array size.
// Instead we'll just keep the record of the resized image width and height separately.
const size: ImageSize = { w: img.width, h: img.height };
// Calculating the number of pixels to remove.
const pxToRemove = img.width - toWidth;
if (pxToRemove < 0) {
throw new Error('Upsizing is not supported for now');
}
let energyMap: EnergyMap | null = null;
let seam: Seam | null = null;
// Removing the lowest energy seams one by one.
for (let i = 0; i < pxToRemove; i += 1) {
// 1. Calculate the energy map for the current version of the image.
energyMap = calculateEnergyMap(img, size);
// 2. Find the seam with the lowest energy based on the energy map.
seam = findLowEnergySeam(energyMap, size);
// 3. Delete the seam with the lowest energy seam from the image.
deleteSeam(img, seam, size);
// Reduce the image width, and continue iterations.
size.w -= 1;
}
// Returning the resized image and its final size.
// The img is actually a reference to the ImageData, so technically
// the caller of the function already has this pointer. But let's
// still return it for better code readability.
return { img, size };
};A imagem que precisa ser redimensionada está sendo passada para a função no formato ImageData . Você pode desenhar a imagem na tela e, em seguida, extrair os ImageData da tela assim:
const ctx = canvas.getContext('2d');
const imgData = ctx.getImageData(0, 0, imgWidth, imgHeight);A maneira de enviar e desenhar imagens em JavaScript está fora do escopo deste artigo, mas você pode encontrar o código-fonte completo de como isso pode ser feito usando o React no repositório js-image-carver .
Vamos quebrar cada passo ony ser um e implementar as calculateEnergyMap(), findLowEnergySeam()e deleteSeam()funções.
Calculando a energia do pixel
Aqui, aplicamos a fórmula de diferença de cor descrita acima. Para as bordas esquerda e direita (quando não há vizinhos à esquerda ou à direita), ignoramos os vizinhos e não os levamos em consideração durante o cálculo de energia.
// Calculates the energy of a pixel.
const getPixelEnergy = (left: Color | null, middle: Color, right: Color | null): number => {
// Middle pixel is the pixel we're calculating the energy for.
const [mR, mG, mB] = middle;
// Energy from the left pixel (if it exists).
let lEnergy = 0;
if (left) {
const [lR, lG, lB] = left;
lEnergy = (lR - mR) ** 2 + (lG - mG) ** 2 + (lB - mB) ** 2;
}
// Energy from the right pixel (if it exists).
let rEnergy = 0;
if (right) {
const [rR, rG, rB] = right;
rEnergy = (rR - mR) ** 2 + (rG - mG) ** 2 + (rB - mB) ** 2;
}
// Resulting pixel energy.
return Math.sqrt(lEnergy + rEnergy);
};Calculando o mapa de energia
A imagem com a qual estamos trabalhando tem o formato ImageData . Isso significa que todos os pixels (e suas cores) são armazenados em uma matriz Uint8ClampedArray plana ( 1D ) . Para fins de legibilidade, vamos apresentar algumas funções auxiliares que nos permitirão trabalhar com o array Uint8ClampedArray como com uma matriz 2D .
// Helper function that returns the color of the pixel.
const getPixel = (img: ImageData, { x, y }: Coordinate): Color => {
// The ImageData data array is a flat 1D array.
// Thus we need to convert x and y coordinates to the linear index.
const i = y * img.width + x;
const cellsPerColor = 4; // RGBA
// For better efficiency, instead of creating a new sub-array we return
// a pointer to the part of the ImageData array.
return img.data.subarray(i * cellsPerColor, i * cellsPerColor + cellsPerColor);
};
// Helper function that sets the color of the pixel.
const setPixel = (img: ImageData, { x, y }: Coordinate, color: Color): void => {
// The ImageData data array is a flat 1D array.
// Thus we need to convert x and y coordinates to the linear index.
const i = y * img.width + x;
const cellsPerColor = 4; // RGBA
img.data.set(color, i * cellsPerColor);
};Para calcular o mapa de energia, percorremos cada pixel da imagem e chamamos a getPixelEnergy()função descrita anteriormente contra ele.
// Helper function that creates a matrix (2D array) of specific
// size (w x h) and fills it with specified value.
const matrix = <T>(w: number, h: number, filler: T): T[][] => {
return new Array(h)
.fill(null)
.map(() => {
return new Array(w).fill(filler);
});
};
// Calculates the energy of each pixel of the image.
const calculateEnergyMap = (img: ImageData, { w, h }: ImageSize): EnergyMap => {
// Create an empty energy map where each pixel has infinitely high energy.
// We will update the energy of each pixel.
const energyMap: number[][] = matrix<number>(w, h, Infinity);
for (let y = 0; y < h; y += 1) {
for (let x = 0; x < w; x += 1) {
// Left pixel might not exist if we're on the very left edge of the image.
const left = (x - 1) >= 0 ? getPixel(img, { x: x - 1, y }) : null;
// The color of the middle pixel that we're calculating the energy for.
const middle = getPixel(img, { x, y });
// Right pixel might not exist if we're on the very right edge of the image.
const right = (x + 1) < w ? getPixel(img, { x: x + 1, y }) : null;
energyMap[y][x] = getPixelEnergy(left, middle, right);
}
}
return energyMap;
};O mapa de energia será recalculado a cada iteração de redimensionamento. Isso significa que será recalculado, digamos, 500 vezes se precisarmos diminuir a imagem em 500 pixels, o que não é o ideal. Para acelerar o cálculo do mapa de energia na 2ª, 3ª e outras etapas, podemos recalcular a energia apenas para os pixels que são colocados ao redor da emenda que será removida. Por razões de simplicidade, essa otimização é omitida aqui, mas você pode encontrar o código-fonte de exemplo no js-image-carver repo.
Encontrar a costura com a menor energia (abordagem de Programação Dinâmica)
Descrevi alguns princípios básicos da programação dinâmica no artigo Programação dinâmica vs Dividir e conquistar . Há um exemplo de DP baseado no problema de distância mínima de edição. Você pode querer dar uma olhada para obter um pouco mais de contexto.
O problema que precisamos resolver agora é encontrar o caminho (a costura) no mapa de energia que vai de cima para baixo e tem a soma mínima de energias de pixel.
A abordagem ingênua
A abordagem ingênua seria verificar todos os caminhos possíveis, um após o outro.
Indo de cima para baixo, para cada pixel, temos 3 opções (↙︎ ir para baixo-esquerda, ↓ ir para baixo, ↘︎ ir para baixo-direita). Isso nos dá a complexidade de tempo de O(w * 3^h)ou simplesmente O(3^h), onde we hestão a largura e a altura da imagem. Essa abordagem parece lenta.
A abordagem gananciosa
Também podemos tentar escolher o próximo pixel como um pixel com a energia mais baixa, esperando que a energia de emenda resultante seja a menor.
Essa abordagem não oferece a pior solução, mas não pode garantir que encontraremos a melhor solução disponível. Na imagem acima, você pode ver como a abordagem gananciosa escolheu em 5vez de 10no início e perdeu a cadeia de pixels ideais.
A parte boa dessa abordagem é que ela é rápida e tem uma complexidade de tempo de O(w + h), onde we hestão a largura e a altura da imagem. Nesse caso, o custo da velocidade é a baixa qualidade do redimensionamento. Precisamos encontrar um valor mínimo na primeira linha ( wcélulas transversais ) e, em seguida, exploramos apenas 3 pixels vizinhos para cada linha ( hlinhas transversais ).
A abordagem de programação dinâmica
Você deve ter notado que na abordagem ingênua nós somamos as mesmas energias de pixel repetidamente enquanto calculávamos a energia das junções resultantes.
No exemplo acima, você vê que para as duas primeiras costuras estamos reutilizando a energia da costura mais curta (que tem a energia de 235). Em vez de fazer apenas uma operação 235 + 70para calcular a energia da 2ª costura, estamos fazendo quatro operações (5 + 0 + 80 + 150) + 70.
O fato de estarmos reutilizando a energia da costura anterior para calcular a energia da costura atual pode ser aplicado recursivamente a todas as costuras mais curtas até a primeira costura da primeira linha. Quando temos esses subproblemas sobrepostos, é um sinal de que o problema geral pode ser otimizado por uma abordagem de programação dinâmica.
Portanto, podemos economizar a energia da costura atual no pixel específico em uma seamsEnergiestabela adicional para torná-la reutilizável para calcular as próximas costuras mais rapidamente (a seamsEnergiestabela terá o mesmo tamanho que o mapa de energia e a própria imagem).
Também devemos ter em mente que para um pixel específico na imagem (ou seja, o inferior esquerdo), podemos ter vários valores das energias das junções anteriores.
Como estamos procurando uma costura com a energia resultante mais baixa, faria sentido escolher a costura anterior com a energia resultante mais baixa também.
Em geral, temos três opções anteriores possíveis para escolher:
Você pode pensar assim:
- A célula
[1][x]: contém a menor energia possível da costura que começa em algum lugar da linha[0][?]e termina na célula[1][x] - A célula atual
[2][3]: contém a energia mais baixa possível da costura que começa em algum lugar da linha[0][?]e termina na célula[2][3]. Para calculá-lo, precisamos somar a energia do pixel atual[2][3](do mapa de energia) com omin(seam_energy_1_2, seam_energy_1_3, seam_energy_1_4)
Se preenchermos a seamsEnergiestabela completamente, o número mínimo na linha mais baixa será a energia de costura mais baixa possível.
Vamos tentar preencher várias células desta tabela para ver como funciona.
Depois de preencher a seamsEnergiestabela, podemos ver que o pixel de menor energia possui uma energia de 50. Por conveniência, durante a seamsEnergiesgeração de cada pixel, podemos economizar não apenas a energia da costura, mas também as coordenadas da costura de menor energia anterior. Isso nos dará a possibilidade de reconstruir facilmente o caminho da costura de baixo para cima.
A complexidade de tempo da abordagem DP seria O(w * h), onde we hsão a largura e a altura da imagem. Precisamos calcular as energias para cada pixel da imagem.
Aqui está um exemplo de como essa lógica pode ser implementada:
// The metadata for the pixels in the seam.
type SeamPixelMeta = {
energy: number, // The energy of the pixel.
coordinate: Coordinate, // The coordinate of the pixel.
previous: Coordinate | null, // The previous pixel in a seam.
};
// Finds the seam (the sequence of pixels from top to bottom) that has the
// lowest resulting energy using the Dynamic Programming approach.
const findLowEnergySeam = (energyMap: EnergyMap, { w, h }: ImageSize): Seam => {
// The 2D array of the size of w and h, where each pixel contains the
// seam metadata (pixel energy, pixel coordinate and previous pixel from
// the lowest energy seam at this point).
const seamsEnergies: (SeamPixelMeta | null)[][] = matrix<SeamPixelMeta | null>(w, h, null);
// Populate the first row of the map by just copying the energies
// from the energy map.
for (let x = 0; x < w; x += 1) {
const y = 0;
seamsEnergies[y][x] = {
energy: energyMap[y][x],
coordinate: { x, y },
previous: null,
};
}
// Populate the rest of the rows.
for (let y = 1; y < h; y += 1) {
for (let x = 0; x < w; x += 1) {
// Find the top adjacent cell with minimum energy.
// This cell would be the tail of a seam with lowest energy at this point.
// It doesn't mean that this seam (path) has lowest energy globally.
// Instead, it means that we found a path with the lowest energy that may lead
// us to the current pixel with the coordinates x and y.
let minPrevEnergy = Infinity;
let minPrevX: number = x;
for (let i = (x - 1); i <= (x + 1); i += 1) {
if (i >= 0 && i < w && seamsEnergies[y - 1][i].energy < minPrevEnergy) {
minPrevEnergy = seamsEnergies[y - 1][i].energy;
minPrevX = i;
}
}
// Update the current cell.
seamsEnergies[y][x] = {
energy: minPrevEnergy + energyMap[y][x],
coordinate: { x, y },
previous: { x: minPrevX, y: y - 1 },
};
}
}
// Find where the minimum energy seam ends.
// We need to find the tail of the lowest energy seam to start
// traversing it from its tail to its head (from the bottom to the top).
let lastMinCoordinate: Coordinate | null = null;
let minSeamEnergy = Infinity;
for (let x = 0; x < w; x += 1) {
const y = h - 1;
if (seamsEnergies[y][x].energy < minSeamEnergy) {
minSeamEnergy = seamsEnergies[y][x].energy;
lastMinCoordinate = { x, y };
}
}
// Find the lowest energy energy seam.
// Once we know where the tail is we may traverse and assemble the lowest
// energy seam based on the "previous" value of the seam pixel metadata.
const seam: Seam = [];
if (!lastMinCoordinate) {
return seam;
}
const { x: lastMinX, y: lastMinY } = lastMinCoordinate;
// Adding new pixel to the seam path one by one until we reach the top.
let currentSeam = seamsEnergies[lastMinY][lastMinX];
while (currentSeam) {
seam.push(currentSeam.coordinate);
const prevMinCoordinates = currentSeam.previous;
if (!prevMinCoordinates) {
currentSeam = null;
} else {
const { x: prevMinX, y: prevMinY } = prevMinCoordinates;
currentSeam = seamsEnergies[prevMinY][prevMinX];
}
}
return seam;
};Removendo a costura com a menor energia
Uma vez que encontramos a costura de menor energia, precisamos remover (para esculpir) os pixels que a formam a partir da imagem. A remoção está acontecendo deslocando os pixels à direita da costura 1pxpara a esquerda. Por motivos de desempenho, não excluímos realmente as últimas colunas. Em vez disso, o componente de renderização apenas ignorará a parte da imagem que está além da largura da imagem redimensionada.
// Deletes the seam from the image data.
// We delete the pixel in each row and then shift the rest of the row pixels to the left.
const deleteSeam = (img: ImageData, seam: Seam, { w }: ImageSize): void => {
seam.forEach(({ x: seamX, y: seamY }: Coordinate) => {
for (let x = seamX; x < (w - 1); x += 1) {
const nextPixel = getPixel(img, { x: x + 1, y: seamY });
setPixel(img, { x, y: seamY }, nextPixel);
}
});
};Remoção de objetos
O algoritmo Seam Carving tenta remover as costuras que consistem em pixels de baixa energia primeiro. Poderíamos alavancar esse fato e atribuindo baixa energia a alguns pixels manualmente (ou seja, desenhando na imagem e mascarando algumas áreas dela), poderíamos fazer o algoritmo Seam Carving para fazer a remoção de objetos gratuitamente.
Atualmente, em getPixelEnergy()função de que estávamos usando apenas os R, G, Bcanais de cor para calcular a energia do pixel. Mas também há o Aparâmetro (alfa, transparência) da cor que ainda não usamos. Podemos usar o canal de transparência para informar ao algoritmo que pixels transparentes são os pixels que queremos remover. Você pode verificar o código-fonte da função de energia que leva a transparência em consideração.
Aqui está como o algoritmo funciona para remoção de objetos.
