Superpixel algorithm implemented in Java

This Superpixel code has been stored on my hard drive for a year. Too bad, I have only very little time for my recreational image processing programming.

But here is my interpretation for Superpixel algorithm in Java programming language. The computational process itself is iterative, but I am using the Cluster objects to make the algorithm slightly easier to understand and follow. Without objects, it could be slightly faster, I have not tried to code that kind of version myself.


Interesting things to try:

• change the proximity modifier 'm' from small to large
• change the cell size 'S' from small to large

Notes

1. The algorithm does not ensure superpixel connectivity, thus the result may have orphan pixels from 'wrong' cluster inside of other cluster.
2. This algorithm works in RGB color space, some other color space (Lab for example) could give you better end results.
3. The distance calculation can be done also using "approximated" distance without square root calculations, for performance reasons.

Links
Image segmentation in Wikipedia: http://en.wikipedia.org/wiki/Image_segmentation
SLIC Superpixels - http://ivrg.epfl.ch/research/superpixels
jSLIC code in the GitHub - https://github.com/Borda/ij-CMP-BIA


Example images

Values used: left S=16, m=130, right S=24, m=130

Values used: left S=16, m=130, right S=24, m=130

Values used: left S=16, m=130, right S=24, m=130

Example usage
Using command line

java popscan.Superpixel "C:\java\flamingo.png" c:\java\sp_flamingo.png 16 130

Source

package popscan;

import java.awt.Color;

import java.awt.image.BufferedImage;

import java.io.File;

import java.util.Arrays;

import java.util.Vector;

import javax.imageio.ImageIO;

/**

* @author tejopa, 2014

* @version 1

* http://popscan.blogspot.com

*/

public class Superpixel {

// arrays to store values during process

double[] distances;

int[] labels;

int[] reds;

int[] greens;

int[] blues;

Cluster[] clusters;

// in case of instable clusters, max number of loops

int maxClusteringLoops = 50;

/**

* @param args

*/

public static void main(String[] args) {

if (args.length!=4) {

System.out.println("Usage: java popscan.Superpixel"

+ " [source image filename]"

+ " [destination image filename]"

+ " [cell width S (1-255)]"

+ " [proximity modifier m (1-255)");

return;

}

// parse arguments

String src = args[0];

String dst = args[1];

double S = Integer.parseInt(args[2]);

double m = Double.parseDouble(args[3]);

BufferedImage img = loadImage(src);

Superpixel sp = new Superpixel();

BufferedImage dstImage = sp.calculate(img,S,m);

// save the resulting image

saveImage(dst, dstImage);

}

public Superpixel() {    }

public BufferedImage calculate(BufferedImage image,

double S, double m) {

int w = image.getWidth();

int h = image.getHeight();

BufferedImage result = new BufferedImage(w, h,

BufferedImage.TYPE_INT_RGB);

long start = System.currentTimeMillis();

// get the image pixels

int[] pixels = image.getRGB(0, 0, w, h, null, 0, w);

// create and fill lookup tables

distances = new double[w*h];

Arrays.fill(distances, Integer.MAX_VALUE);

labels = new int[w*h];

Arrays.fill(labels, -1);

// split rgb-values to own arrays

reds = new int[w*h];

greens = new int[w*h];

blues = new int[w*h];

for (int y=0;y<h;y++) {

for (int x=0;x<w;x++) {

int pos = x+y*w;

int color = pixels[pos];

reds[pos]   = color>>16&0x000000FF;

greens[pos] = color>> 8&0x000000FF;

blues[pos]  = color>> 0&0x000000FF;

}

}

// create clusters

createClusters(image, S, m);

// loop until all clusters are stable!

int loops = 0;

boolean pixelChangedCluster = true;

while (pixelChangedCluster&&loops<maxClusteringLoops) {

pixelChangedCluster = false;

loops++;

// for each cluster center C

for (int i=0;i<clusters.length;i++) {

Cluster c = clusters[i];

// for each pixel i in 2S region around

// cluster center

int xs = Math.max((int)(c.avg_x-S),0);

int ys = Math.max((int)(c.avg_y-S),0);

int xe = Math.min((int)(c.avg_x+S),w);

int ye = Math.min((int)(c.avg_y+S),h);

for (int y=ys;y<ye;y++) {

for (int x=xs;x<xe;x++) {

int pos = x+w*y;

double D = c.distance(x, y, reds[pos],

greens[pos],

blues[pos],

S, m, w, h);

if ((D<distances[pos])&&(labels[pos]!=c.id)) {

distances[pos]         = D;

labels[pos]            = c.id;

pixelChangedCluster = true;

}

} // end for x

} // end for y

} // end for clusters

// reset clusters

for (int index=0;index<clusters.length;index++) {

clusters[index].reset();

}

// add every pixel to cluster based on label

for (int y=0;y<h;y++) {

for (int x=0;x<w;x++) {

int pos = x+y*w;

clusters[labels[pos]].addPixel(x, y,

reds[pos], greens[pos], blues[pos]);

}

}

// calculate centers

for (int index=0;index<clusters.length;index++) {

clusters[index].calculateCenter();

}

}

// Create output image with pixel edges

for (int y=1;y<h-1;y++) {

for (int x=1;x<w-1;x++) {

int id1 = labels[x+y*w];

int id2 = labels[(x+1)+y*w];

int id3 = labels[x+(y+1)*w];

if (id1!=id2||id1!=id3) {

result.setRGB(x, y, 0x000000);

//result.setRGB(x-1, y, 0x000000);

//result.setRGB(x, y-1, 0x000000);

//result.setRGB(x-1, y-1, 0x000000);

} else {

result.setRGB(x, y, image.getRGB(x, y));

}

}

}

// mark superpixel (cluster) centers with red pixel

for (int i=0;i<clusters.length;i++) {

Cluster c = clusters[i];

//result.setRGB((int)c.avg_x, (int)c.avg_y,

//Color.red.getRGB());

}

long end = System.currentTimeMillis();

System.out.println("Clustered to "+clusters.length

+ " superpixels in "+loops

+" loops in "+(end-start)+" ms.");

return result;

}

/*

* Create initial clusters.

*/

public void createClusters(BufferedImage image,

double S, double m) {

Vector<Cluster> temp = new Vector<Cluster>();

int w = image.getWidth();

int h = image.getHeight();

boolean even = false;

double xstart = 0;

int id = 0;

for (double y=S/2;y<h;y+=S) {

// alternate clusters x-position

// to create nice hexagon grid

if (even) {

xstart = S/2.0;

even = false;

} else {

xstart = S;

even = true;

}

for (double x=xstart;x<w;x+=S) {

int pos = (int)(x+y*w);

Cluster c = new Cluster(id,

reds[pos], greens[pos], blues[pos],

(int)x, (int)y, S, m);

temp.add(c);

id++;

}

}

clusters = new Cluster[temp.size()];

for (int i=0;i<temp.size();i++) {

clusters[i] = temp.elementAt(i);

}

}

/**

* @param filename

* @param image

*/

public static void saveImage(String filename,

BufferedImage image) {

File file = new File(filename);

try {

ImageIO.write(image, "png", file);

} catch (Exception e) {

System.out.println(e.toString()+" Image '"+filename

+"' saving failed.");

}

}

/**

* @param filename

* @return

*/

public static BufferedImage loadImage(String filename) {

BufferedImage result = null;

try {

result = ImageIO.read(new File(filename));

} catch (Exception e) {

System.out.println(e.toString()+" Image '"

+filename+"' not found.");

}

return result;

}

class Cluster {

int id;

double inv = 0;        // inv variable for optimization

double pixelCount;    // pixels in this cluster

double avg_red;     // average red value

double avg_green;    // average green value

double avg_blue;    // average blue value

double sum_red;     // sum red values

double sum_green;   // sum green values

double sum_blue;     // sum blue values

double sum_x;       // sum x

double sum_y;       // sum y

double avg_x;       // average x

double avg_y;       // average y

public Cluster(int id, int in_red, int in_green,

int in_blue, int x, int y,

double S, double m) {

// inverse for distance calculation

this.inv = 1.0 / ((S / m) * (S / m));

this.id = id;

addPixel(x, y, in_red, in_green, in_blue);

// calculate center with initial one pixel

calculateCenter();

}

public void reset() {

avg_red = 0;

avg_green = 0;

avg_blue = 0;

sum_red = 0;

sum_green = 0;

sum_blue = 0;

pixelCount = 0;

avg_x = 0;

avg_y = 0;

sum_x = 0;

sum_y = 0;

}

/*

* Add pixel color values to sum of previously added

* color values.

*/

void addPixel(int x, int y, int in_red,

int in_green, int in_blue) {

sum_x+=x;

sum_y+=y;

sum_red  += in_red;

sum_green+= in_green;

sum_blue += in_blue;

pixelCount++;

}

public void calculateCenter() {

// Optimization: using "inverse"

// to change divide to multiply

double inv = 1/pixelCount;

avg_red   = sum_red*inv;

avg_green = sum_green*inv;

avg_blue  = sum_blue*inv;

avg_x = sum_x*inv;

avg_y = sum_y*inv;

}

double distance(int x, int y,

int red, int green, int blue,

double S, double m, int w, int h) {

// power of color difference between

// given pixel and cluster center

double dx_color =  (avg_red-red)*(avg_red-red)

+ (avg_green-green)*(avg_green-green)

+ (avg_blue-blue)*(avg_blue-blue);

// power of spatial difference between

// given pixel and cluster center

double dx_spatial = (avg_x-x)*(avg_x-x)+(avg_y-y)*(avg_y-y);

// Calculate approximate distance D

// double D = dx_color+dx_spatial*inv;

// Calculate squares to get more accurate results

double D = Math.sqrt(dx_color)+Math.sqrt(dx_spatial*inv);

return D;

}

}

}

Fisheye lens equation - Simple fisheye effect with one function

I am interested in many kind of computer algorithms, including algorithms for computer graphics, digital image processing and 3D-graphics.

In one of my projects I needed to have "fish eye lens" like effect, and tried to find easy equation or ready function from the internet. To my surprise, there were not complete functions available, just theories and images how it can be achieved. 

Here is a brief tutorial and loop how to create fish eye -effect to any image. The function is written in Java, but as you can see, it is easily rewritten with any programming language. 

If you find this article and function useful and you will use it in your own projects, please refer where the source came. In any case, leave a comment. Questions and requests are welcome!

What is fish eye effect?

Fish eye effect is a mirror effect which happens when the image is drawn on to a surface of a sphere or a hemisphere. The surface does not need to be a perfect sphere, it can also be paraboloid or have other kind of curve as a surface.

Common effect is, that the image is "zoomed" in the center and "shrink" at the edges. The image is usually round (because we are dealing with spheres) but the image can also be clipped to be square.

Mathematics

What we need is a function which maps any pixel from the image to a surface of a sphere. 

In this fish eye effect, we are not using equations for a sphere, but an equation for unit circle:

x^2 + y^2 = 1 

Solving y

y^2 = 1 - x^2

and then finally

y = sqrt(1 - x^2) 

Because we are limiting all our values between 0.0 and 1.0, we can create values for nice arc when x goes from 0.0 to 1.0.

For example, in the image we have marked x-position 0.75, and we can calculate y-position substituting x in y = sqrt(1 - x^2), which gives us y = 0.66.

For our purpose, we will flip the curve with subtracting the result from 1.0:

d = 1 - sqrt(1 - x^2)

This curve will give us values for the difference of the distance of the source pixel and destination pixel, from the center of the image, when mapping from plane to sphere. 

The new distance is then the original distance added with the difference:

r' = r + d  (r' > r)

Polar coordinates

The normal screen coordinates (two dimensional Cartesian coordinates, simply x- and y-axis) are difficult when dealing with trigonometric functions, because the input values are typically between -1 to 1 and the angles are in radians from 0 to 2*PI.

Everything becomes more easier when you change the screen coordinates (x,y) to polar coordinates (r, theta). This is done with simple functions:

From Cartesian to polar:

    r = sqrt(y^2 + x^2)

    theta = atan2(y, x)

    
From polar to Cartesian:

    x = r cos(theta)
    y = r sin(theta)

In polar coordinates, any point in the image can be accessed with the angle (theta) and distance from center (r).

Now we are able to map any (x,y) pixel to polar coordinate (r,theta), then CHANGE the r, and map it back to (x',y'), and the pixel remains at the same line going through center of the image!

Algorithm 

What we need:

1. the distance from center of the source image to any pixel (x,y) in the same image
2. the position (x', y') where the pixel belongs in the fish eye image

In the following pseudo code, we are using polar coordinates. The key part in the whole process is to use polar coordinates and this fact: The actual pixel translation from 2D-image to sphere surface is done with manipulating the distance from center (r).

Pseudo code:

for each pixel (x,y)

    normalize (x,y) to (nx, ny) to be in range [-1,1]

    calculate distance from (nx, ny) to center (0,0)

    convert (nx,ny) to polar coordinates

    calculate new distance from center on the sphere surface
        The new distance is r' = r + (1 - sqrt(1 -r^2)) / 2

    translate (nx, ny) back to screen coordinates (x',y')

The image above shows how Points P1 and P2 will be displaced to P1' and P2', so that the angle remains the same. In other words, the point is displaced along the original line towards the edge of the unit circle. The distance from the center tells us how big is the displacement. In the center and near the center the displacement value is zero or almost zero. Near the edges displacement value grows towards value of 1.0.

The image above gives the idea behind the displacement value. For every pixel in the result image plane, there is a pixel from source image plane. In here, the source image plane is stretched and curved. It may be easier to understand, if you think a one single line instead of the plane. Along that line, the pixels are almost normal at the center, but towards the ends, the pixels are fetched further and further away from the center.

Most important thing

The most important thing is to understand, that for each result pixel, there is a source pixel, on the same line going through the center, but with a greater distance.

The source 

public static int[] fisheye(int[] srcpixels, double w, double h) {

    /*

     *    Fish eye effect

     *    tejopa, 2012-04-29

     *    http://popscan.blogspot.com

     *    http://www.eemeli.de

     */

    // create the result data

    int[] dstpixels = new int[(int)(w*h)];            

    // for each row

    for (int y=0;y<h;y++) {                                

        // normalize y coordinate to -1 ... 1

        double ny = ((2*y)/h)-1;                        

        // pre calculate ny*ny

        double ny2 = ny*ny;                                

        // for each column

        for (int x=0;x<w;x++) {                            

            // normalize x coordinate to -1 ... 1

            double nx = ((2*x)/w)-1;                    

            // pre calculate nx*nx

            double nx2 = nx*nx;

            // calculate distance from center (0,0)

            // this will include circle or ellipse shape portion

            // of the image, depending on image dimensions

            // you can experiment with images with different dimensions

            double r = Math.sqrt(nx2+ny2);                

            // discard pixels outside from circle!

            if (0.0<=r&&r<=1.0) {                            

                double nr = Math.sqrt(1.0-r*r);            

                // new distance is between 0 ... 1

                nr = (r + (1.0-nr)) / 2.0;

                // discard radius greater than 1.0

                if (nr<=1.0) {

                    // calculate the angle for polar coordinates

                    double theta = Math.atan2(ny,nx);         

                    // calculate new x position with new distance in same angle

                    double nxn = nr*Math.cos(theta);        

                    // calculate new y position with new distance in same angle

                    double nyn = nr*Math.sin(theta);        

                    // map from -1 ... 1 to image coordinates

                    int x2 = (int)(((nxn+1)*w)/2.0);        

                    // map from -1 ... 1 to image coordinates

                    int y2 = (int)(((nyn+1)*h)/2.0);        

                    // find (x2,y2) position from source pixels

                    int srcpos = (int)(y2*w+x2);            

                    // make sure that position stays within arrays

                    if (srcpos>=0 & srcpos < w*h) {

                        // get new pixel (x2,y2) and put it to target array at (x,y)

                        dstpixels[(int)(y*w+x)] = srcpixels[srcpos];    

                    }

                }

            }

        }

    }

    //return result pixels

    return dstpixels;

} 

Example pictures 

Original

After applying fish eye function