Skip to content

Instantly share code, notes, and snippets.

@Voldrix

Voldrix/seam_carving.c

Created July 22, 2024 00:31
Show Gist options
  • Save Voldrix/d3c7b0cd6cd5e8a29a1b295e1bf49d91 to your computer and use it in GitHub Desktop.
Save Voldrix/d3c7b0cd6cd5e8a29a1b295e1bf49d91 to your computer and use it in GitHub Desktop.
Download ZIP
Seam Carving with Sobel in C
Raw
seam_carving.c
unsigned char* rgb_to_monochrome(unsigned char *rgbImg, int width, int height, int colorspace, int weighted) { //RGB(A) -> Mono
unsigned char *monoImg = malloc(width * height);
int m = 0, n = 0;
register r = width * height;
//weighted averaging better matches human perception. Human eyes perceive green more strongly than red, and red more strongly than blue
//the standard weights are about .3R + .6G + .1B
//the weights here are adusted to make them faster to compute. The difference is minimal
if(colorspace == 3) { //RGB
if(weighted) //weighted averaging
while(r--)
monoImg[m++] = (rgbImg[n++] >> 2) + (rgbImg[n++] >> 1) + (rgbImg[n++] >> 2);
else //simple average method
while(r--)
monoImg[m++] = (rgbImg[n++] + rgbImg[n++] + rgbImg[n++]) / 3;
}
else { //RGBA
if(weighted) //weighted averaging
while(r--)
monoImg[m++] = ((rgbImg[n++] >> 2) + (rgbImg[n++] >> 1) + (rgbImg[n++] >> 2)) * (rgbImg[n++] / 255);
else //simple average method
while(r--)
monoImg[m++] = ((rgbImg[n++] + rgbImg[n++] + rgbImg[n++]) / 3) * (rgbImg[n++] / 255);
}
return monoImg;
}
/* monochrome Sobel convolution (x & y) */
unsigned char* sobel(unsigned char *srcImg, int width, int height, int colorspace) {
unsigned char (*p)[width * colorspace] = srcImg; //Multidimensional array pointer
unsigned char (*gradient)[width] = malloc(height * width); //Final filtered image, single channel
int x, y, z, w = width, h = height;
//greyscale copy of src img
unsigned char (*grayscale)[width] = rgb_to_monochrome(srcImg, width, height, colorspace, UNWEIGHTED_AVG);
//start sobel convolution (x & y)
//Corners
x = (p[0][1] - p[0][0] + p[1][1] - p[1][0]) >> 2;
y = (p[1][0] - p[0][0] + p[1][1] - p[0][1]) >> 2;
gradient[0][0] = sqrt(x*x + y*y); //Top Left
x = (p[0][w-1] - p[0][w-2] + p[1][w-1] - p[1][w-2]) >> 2;
y = (p[1][w-1] - p[0][w-1] + p[1][w-2] - p[0][w-2]) >> 2;
gradient[0][w-1] = sqrt(x*x + y*y); //Top Right
x = (p[h-2][1] - p[h-2][0] + p[h-1][1] - p[h-1][0]) >> 2;
y = (p[h-1][0] - p[h-2][0] + p[h-1][1] - p[h-2][1]) >> 2;
gradient[h-1][0] = sqrt(x*x + y*y); //Bottom Left
x = (p[h-2][w-1] - p[h-2][w-2] + p[h-1][w-1] - p[h-1][w-2]) >> 2;
y = (p[h-1][w-1] - p[h-2][w-1] + p[h-1][w-2] - p[h-2][w-2]) >> 2;
gradient[h-1][w-1] = sqrt(x*x + y*y); //Bottom Right
//Edges
for(int j = 1; j < width - 1; j++) {
//top row
x = grayscale[1][j+1] - grayscale[1][j-1] + 2 * grayscale[0][j+1] - 2 * grayscale[0][j-1];
y = grayscale[1][j-1] + grayscale[1][j+1] - grayscale[0][j-1] - grayscale[0][j+1] + 2 * grayscale[1][j] - 2 * grayscale[0][j];
x /= 6;
y >>= 3;
z = sqrt(x*x + y*y);
gradient[0][j] = (z > 255) ? 255 : z;
//bottom row
x = grayscale[h-2][j+1] - grayscale[h-2][j-1] + 2 * grayscale[h-1][j+1] - 2 * grayscale[h-1][j-1];
y = grayscale[h-1][j-1] + grayscale[h-1][j+1] - grayscale[h-2][j-1] - grayscale[h-2][j+1] + 2 * grayscale[h-1][j] - 2 * grayscale[h-2][j];
x /= 6;
y >>= 3;
z = sqrt(x*x + y*y);
gradient[h-1][j] = (z > 255) ? 255 : z;
}
//Rows + Row Edges
for(int i = 1; i < height - 1; i++) {
//left edge
x = grayscale[i-1][1] + grayscale[i+1][1] - grayscale[i-1][0] - grayscale[i+1][0] + 2 * grayscale[i][1] - 2 * grayscale[i][0];
y = grayscale[i+1][1] - grayscale[i-1][1] + 2 * grayscale[i+1][0] - 2 * grayscale[i-1][0];
x >>= 3;
y /= 6;
z = sqrt(x*x + y*y);
gradient[i][0] = (z > 255) ? 255 : z;
//right edge
x = grayscale[i-1][w-1] + grayscale[i+1][w-1] - grayscale[i-1][w-2] - grayscale[i+1][w-2] + 2 * grayscale[i][w-1] - 2 * grayscale[i][w-2];
y = grayscale[i+1][w-2] - grayscale[i-1][w-2] + 2 * grayscale[i+1][w-1] - 2 * grayscale[i-1][w-1];
x >>= 3;
y /= 6;
z = sqrt(x*x + y*y);
gradient[i][w-1] = (z > 255) ? 255 : z;
//rest of the row
for(int j = 1; j < width - 1; j++) {
x = grayscale[i-1][j+1] + grayscale[i+1][j+1] - grayscale[i-1][j-1] - grayscale[i+1][j-1] + 2 * grayscale[i][j+1] - 2 * grayscale[i][j-1];
y = grayscale[i+1][j-1] + grayscale[i+1][j+1] - grayscale[i-1][j-1] - grayscale[i-1][j+1] + 2 * grayscale[i+1][j] - 2 * grayscale[i-1][j];
x >>= 3;
y >>= 3;
z = sqrt(x*x + y*y);
gradient[i][j] = (z > 255) ? 255 : z;
}
}
free(grayscale);
return gradient;
}
void seam_carving(unsigned char *srcImg, int width, int height, int colorspace, int resizeWidth) {
if(resizeWidth < 8) return;
unsigned char *writePtr, *readPtr;
int x, y, z, *energyPtr;
register int r;
int *energyMap = malloc(sizeof(int) * width * height);
int *seam = malloc(sizeof(int) * height);
unsigned char *sobelImg = sobel(srcImg, width, height, colorspace);
while(width > resizeWidth) { //main seam removal loop
energyPtr = &energyMap[width * (height - 1)];
readPtr = &sobelImg[width * (height - 1)];
r = width;
while(r--) //copy bottom row from sobelImg to energy map
*energyPtr++ = *readPtr++;
for(int i = height - 2; i >= 0; i--) { //build energy map, bottom-up
x = width * i;
y = x + width;
energyMap[x] = sobelImg[x] + ((energyMap[y+1] < energyMap[y]) ? energyMap[y+1] : energyMap[y]); //left edge
energyMap[y-1] = sobelImg[y-1] + ((energyMap[y+width-2] < energyMap[y+width-1]) ? energyMap[y+width-2] : energyMap[y+width-1]); //right edge
for(int j = width - 2; j > 0; j--) { //rest of energy map
z = (energyMap[y+j-1] < energyMap[y+j]) ? energyMap[y+j-1] : energyMap[y+j];
energyMap[x+j] = sobelImg[x+j] + ((energyMap[y+j+1] < z) ? energyMap[y+j+1] : z);
}
}
/* start seam */
r = 0;
for(int i = 1; i < width; i++) //find lowest energy starting point in first row
r = (energyMap[i] < energyMap[r]) ? i : r; //idx pos
y = seam[0] = r;
for(int i = 1; i < height; i++) { //trace seam on energy map
x = y + width;
seam[i] = width;
if(x == width * i) //left edge
seam[i] += energyMap[x+1] < energyMap[x];
else if(x == width * (i+1) - 1) //right edge
seam[i] -= energyMap[x-1] < energyMap[x];
else { //middle (not a side edge)
r = (energyMap[x-1] < energyMap[x]) ? energyMap[x-1] : energyMap[x]; //relative advancement
if(energyMap[x+1] < r) seam[i] += 1;
else seam[i] -= energyMap[x-1] < energyMap[x];
}
y += seam[i]; //seam total (for finding the tail)
}
/* img array compacting */
//filter/gradient img
writePtr = readPtr = &sobelImg[seam[0]]; //trim seam from sobel filtered img
readPtr++;
for(int i = 1; i < height; i++) { //compact array, deleting seam
r = seam[i] - 1;
memcpy(writePtr, readPtr, r);
writePtr += r;
readPtr += r + 1;
}
r = height * width - y - 1; //last half of last line
while(r--) //compact the tail
*writePtr++ = *readPtr++;
/* compact src img */
writePtr = readPtr = &srcImg[seam[0] * colorspace]; //trim seam from src img
readPtr += colorspace;
for(int i = 1; i < height; i++) { //compact array, deleting seam
r = (seam[i] - 1) * colorspace;
memcpy(writePtr, readPtr, r);
writePtr += r;
readPtr += r + colorspace;
}
r = (height * width - y - 1) * colorspace; //last half of last line
while(r--) //compact the tail
*writePtr++ = *readPtr++;
width -= 1;
} //end seam carving loop
free(seam);
free(energyMap);
free(sobelImg);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment