The median cut algorithm is a popular algorithm for color quantization, but can be applied to virtually any point clustering problem. In outline, it works as follows:
* Let B be a set of boxes containing points, initially containing only a single box containing all points.
* While the number of boxes in B is less than desired number of clusters...
o Find the largest side length of any side of any box.
o Cut that box into two boxes along its largest side in such a way that half the contained points fall into each new box.
o Shrink the two new boxes so that they are just large enough to contain their points.
If anyone need any help how to do without my code just post comment I will try to give proper direction to do it.
CoDe
*****************************************************************************
/**
* @(#)box.java
*
*
* @author sharma
* @version 1.00 2011/7/8
*/
public class Box {
public double R = 0;
public double G = 0;
public double B = 0;
public Box()
{
R = 0;
G = 0;
B = 0;
}
public Box(double[] rgb) {
R = rgb[0];
G = rgb[1];
B = rgb[2];
}
}
/**
* @(#)rBox.java
*
*
* @author
* @version 1.00 2002/1/2
*/
public class rBox {
public double R = 0;
public double G = 0;
public double B = 0;
public double mR = 0;
public double mG = 0;
public double mB = 0;
public rBox() {
R = 0;
G = 0;
B = 0;
}
public rBox(double rr,double rg,double rb,double mr,double mg,double mb)
{
R = rr;
G = rg;
B = rb;
mR = mr;
mG = mg;
mB = mb;
}
}
/**
* @(#)Func.java
*
*
* @author sharma
* @version 1.00 2011/7/8
*/
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
import java.util.ArrayList;
import java.awt.image.Raster;
import java.awt.image.WritableRaster;
public class Func {
public static boolean[][][] rgbflag = new boolean[350][350][350];
public static BufferedImage imagetaker(String Img) {
BufferedImage img = null;
try {
img = ImageIO.read(new File(Img));
} catch (IOException ex) {
}
return img;
}
public static ArrayList imageSplit(BufferedImage image) {
ArrayList inRGB = new ArrayList();
Raster r = image.getData();
double[] dem = new double[4];
for (int i = 0; i < image.getWidth(); i++) {
for (int j = 0; j < image.getHeight(); j++) {
r.getPixel(i, j, dem);
int R = (int) dem[0];
int G = (int) dem[1];
int B = (int) dem[2];
// if (!rgbflag[R][G][B]) {
inRGB.add(new Box(dem));
// }
rgbflag[R][G][B] = true;
}
}
return inRGB;
}
public static int longdim(ArrayList inRGB) {
int r_mn = 10000, r_mx = 0;
int g_mn = 10000, g_mx = 0;
int b_mn = 10000, b_mx = 0;
for (int i = 0; i < inRGB.size(); i++) {
r_mn = Math.min((int) inRGB.get(i).R, r_mn);
r_mx = Math.max((int) inRGB.get(i).R, r_mx);
g_mn = Math.min((int) inRGB.get(i).G, g_mn);
g_mx = Math.max((int) inRGB.get(i).G, g_mx);
b_mn = Math.min((int) inRGB.get(i).B, b_mn);
b_mx = Math.max((int) inRGB.get(i).B, b_mx);
}
int def_R = r_mx - r_mn;
int def_G = g_mx - g_mn;
int def_B = b_mx - b_mn;
if((def_R > def_G) && (def_R > def_B))
return 1;
else if((def_G > def_R) && (def_G > def_B))
return 2;
else
return 3;
}
public static Box medValue(ArrayList inRGB, int LOD) {
Box med = new Box(new double[]{0,0,0});
if (inRGB.size() == 1) {
med = inRGB.get(0);
}
else {
double avg = 0;
double totalValue = 0;
double Ravg = 0;
double Gavg = 0;
double Bavg = 0;
for (int i = 0; i < inRGB.size(); i++) {
Ravg = Ravg+inRGB.get(i).R;
Gavg = Gavg+inRGB.get(i).G;
Bavg = Bavg+inRGB.get(i).B;
if (LOD == 1) {
totalValue = totalValue + inRGB.get(i).R;
}
else if (LOD == 2) {
totalValue = totalValue + inRGB.get(i).G;
}
else if (LOD == 3) {
totalValue = totalValue + inRGB.get(i).B;
}
}
//System.out.println(Ravg+" *"+Gavg+" *"+Bavg);
avg = totalValue / inRGB.size();
Ravg = Ravg / inRGB.size();
Gavg = Gavg / inRGB.size();
Bavg = Bavg / inRGB.size();
// System.out.println(Ravg+" |"+Gavg+" |"+Bavg);
double minDistance = 1000000.0;
double tempDis = 0;
for (int i = 0; i < inRGB.size(); i++) {
if (LOD == 1) {
tempDis = Math.abs(avg - inRGB.get(i).R);
}
else if (LOD == 2) {
tempDis = Math.abs(avg - inRGB.get(i).G);
}
else if (LOD == 3) {
tempDis = Math.abs(avg - inRGB.get(i).B);
}
if (minDistance > tempDis) {
minDistance = tempDis;
med.R = inRGB.get(i).R;
med.G = inRGB.get(i).G;
med.B = inRGB.get(i).B;
}
}
med.R = Ravg;
med.G = Gavg;
med.B = Bavg;
}
return med;
}
public static void view(ArrayList pix)
{
int sz = pix.size();
System.out.println("total :"+sz);
for(int i=0;i LOT = new ArrayList();
ArrayList Pseg = new ArrayList();
int px,py;
public Median(String ImageLoc,int lim) {
BufferedImage InImage = Func.imagetaker(ImageLoc);
ArrayList inRGB = Func.imageSplit(InImage);
man(inRGB,lim);
//genLOT(inRGB, Func.longdim(inRGB), lim);
// Func.view(LOT);
outImage(InImage);
}
public void man(ArrayList inRGB,int lim)
{
int[] siz = new int[1010];
int[] st = new int[1010];
ArrayList Seg = new ArrayList();
siz[0] = 0;
siz[1] = inRGB.size();
st[1] = 0;
int sz = 1,pos=0,len;
len = inRGB.size();
for(int i=0;i mx)
{
mx = siz[j];
pos = j;
}
}
// select segment to divide
Seg.clear();
int p=st[pos];
for(int j=p;j=pos+1;j--)
{
siz[j+1] = siz[j];
st[j+1] = st[j];
// System.out.print("i :"+siz[j+1]);
}
++sz;
siz[pos+1] = py;
siz[pos] = px;
st[pos+1] = st[pos]+siz[pos];
px =0;py=0;
/* System.out.println("max :"+mx);
for(int j=1;j<=sz;j++)
{
System.out.print("st: "+st[j]+" "+siz[j]+" ");
}
System.out.println();*/
}
for(int i=1;i<=sz;i++)
{
System.out.println("i :"+i+" "+siz[i]);
}
int tot=0;
for(int i=1;i<=sz;i++)
{
Seg.clear();
tot += siz[i];
for(int j=st[i];j inRGB) {
ArrayList Seg1 = new ArrayList();
ArrayList Seg2 = new ArrayList();
Box mbox;
int LOD = Func.longdim(inRGB);
mbox = Func.medValue(inRGB, LOD);
int p=0,q=0;
for (int i = 0; i < inRGB.size(); i++) {
double realRGB = 0;
double medRGB = 0;
if (LOD == 1) {
realRGB = inRGB.get(i).R;
medRGB = mbox.R;
}
else if (LOD == 2) {
realRGB = inRGB.get(i).G;
medRGB = mbox.G;
}
else if (LOD == 3) {
realRGB = inRGB.get(i).B;
medRGB = mbox.B;
}
if (realRGB <= medRGB) {
Seg1.add(inRGB.get(i));
++p;
}
else if (realRGB > medRGB) {
Seg2.add(inRGB.get(i));
++q;
}
}
Pseg.clear();
for(int i=0;i< LOT.size(); i++) {
if (RGB.R == LOT.get(i).R && RGB.G == LOT.get(i).G && RGB.B == LOT.get(i).B ) {
nearRGB.R = LOT.get(i).mR;
nearRGB.G = LOT.get(i).mG;
nearRGB.B = LOT.get(i).mB;
break;
}
}
return nearRGB;
}
void outImage(BufferedImage image) {
BufferedImage imageOut = new BufferedImage(image.getWidth(), image.getHeight(), BufferedImage.TYPE_BYTE_INDEXED);
WritableRaster raster = imageOut.getRaster();
Raster r = image.getData();
double[] rgb = new double[4];
for (int i = 0; i < image.getWidth(); i++) {
for (int j = 0; j < image.getHeight(); j++) {
r.getPixel(i, j, rgb);
Box rgbNew = nearRGB(new Box(rgb));
double sample[] = {rgbNew.R, rgbNew.G, rgbNew.B};
raster.setPixel(i, j, sample);
}
}
ImageWriter writer = null;
Iterator iter = ImageIO.getImageWritersByFormatName("jpg");
if (iter.hasNext()) {
writer = iter.next();
}
File f = new File("D:\\output.jpg");
ImageOutputStream imageOutputStream;
try {
imageOutputStream = ImageIO.createImageOutputStream(f);
writer.setOutput(imageOutputStream);
} catch (IOException ex) {
ex.printStackTrace();
}
try {
writer.write(new IIOImage(imageOut, null, null));
} catch (IOException ex) {
ex.printStackTrace();
}
// drawImage(imageOut, "jpg", "D:\\output.jpg");
}
public static void drawImage(BufferedImage img, String format, String fileLoc) {
try {
ImageIO.write(img, format, new File(fileLoc));
} catch (IOException ex) {
}
}
}
/**
* @(#)sr_med.java
*
* sr_med application
*
* @author sharma
* @version 1.00 2011/7/8
*/
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import javax.swing.*;
public class sr_med extends Frame{
Image im,tmp;
int iw,ih;
int[] pixels;
boolean flag=false;
int ans=0;
TextField tx,limi;
String st;
public sr_med(){
super("MedianImage");
Panel pdown;
Button load,run,save,quit;
addWindowListener(new WindowAdapter(){
public void windowClosing(WindowEvent e){
System.exit(0);
}
});
pdown = new Panel();
pdown.setBackground(Color.lightGray);
load=new Button("Load");
run = new Button("Run");
quit=new Button("Quit");
tx = new TextField(30);
limi = new TextField(10);
this.add(pdown,BorderLayout.SOUTH);
pdown.add(tx);
pdown.add(load);
pdown.add(limi);
pdown.add(run);
pdown.add(quit);
load.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
jLoad_ActionPerformed(e);
}
});
run.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
jRun_ActionPerformed(e);
}
});
quit.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
jQuit_ActionPerformed(e);
}
});
}
public void jLoad_ActionPerformed(ActionEvent e){
st = tx.getText();
MediaTracker tracker = new MediaTracker(this);
im=Toolkit.getDefaultToolkit().getImage(st);
tracker.addImage(im,0);
System.out.println(st);
try{
tracker.waitForID(0);
}catch(InterruptedException e2){ e2.printStackTrace();}
iw=im.getWidth(this);
ih=im.getHeight(this);
pixels=new int[iw*ih];
try{
PixelGrabber pg=new PixelGrabber(im,0,0,iw,ih,pixels,0,iw);
pg.grabPixels();
}catch (InterruptedException e3) {
e3.printStackTrace();
}
ImageProducer ip=new MemoryImageSource(iw,ih,pixels,0,iw);
tmp=createImage(ip);
flag=true;
repaint();
}
public void jRun_ActionPerformed(ActionEvent e){
String sp = limi.getText();
int n = Integer.parseInt(sp);
System.out.println(n);
new Median(st,n);
MediaTracker tracker = new MediaTracker(this);
im=Toolkit.getDefaultToolkit().getImage("D:\\output.jpg");
tracker.addImage(im,0);
// System.out.println(st);
try{
tracker.waitForID(0);
}catch(InterruptedException e2){ e2.printStackTrace();}
try{
PixelGrabber pg=new PixelGrabber(im,0,0,iw,ih,pixels,0,iw);
pg.grabPixels();
}catch (InterruptedException e3) {
e3.printStackTrace();
}
ImageProducer ip=new MemoryImageSource(iw,ih,pixels,0,iw);
tmp=createImage(ip);
flag=true;
ans = 0;
repaint();
}
public void jQuit_ActionPerformed(ActionEvent e){
JOptionPane op =new JOptionPane();
int exit=op.showConfirmDialog(this,"Are you sure? ?","Warning!",JOptionPane.YES_NO_OPTION);
if(exit==JOptionPane.YES_OPTION)
{
System.exit(0);
}else{ }
}
public void paint(Graphics g){
if(flag){
g.drawImage(tmp,10+ans,20+ans,this);
}else { }
}
public static void main(String[] args) {
sr_med mi = new sr_med();
mi.setLocation(50,50);
mi.setSize(600,600);
mi.show();
}
}
Try to modify the genLO
Picture of Output
