Mediun Cut Image Compression source code in java



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
T class .(Hint use sort instead of my divission by average value)


Picture of Output

Shift Reduce algorithm source code in c for Compiler

#include
#include
#include
#include
#include

using namespace std;


struct stru1
{
    char non_ter[1],pro[25];
}cfg[25];

int n,st=-1,j,i,t=-1,m;
int v,c,p=1;
char str[20],stack[20],ch,tmp[10];

void match(int k);
void matchl(int k);


int main()
{

    printf("Enter the number of productions:\n");
    scanf("%d",&n);
    printf("\n");
    printf("Enter the productions on LEFT and RIGHT sides:\n");

    for(i=0;i\n");
        scanf("%s",cfg[i].pro);
        printf("\n");
    }
    printf("Enter the input string:\n");
    scanf("%s",str);
    printf("\n");

    i=0;
    do
    {
        ch=str[i];
        stack[++st]=ch;
        tmp[0]=ch;
        match(1);
        i++;
    }while(str[i]!='\0');

    c=st;
    v=st;
    puts(stack);
    printf("\n");

    while(st)
    {
        --st;
        v=st;
        t=-1;
        p=0;
        while(v<=c)
        {
            tmp[++t]=stack[v++];
            p++;
        }
        matchl(p);
    }

    cfg[0].non_ter[1]='\0';
    if(strcmp(stack,cfg[0].non_ter)==0)
    printf("String is present in Grammar G\n");
    else
    printf("String is not present in Grammar G\n");
}

void match(int k)
{
    for(j=0;j<=y);

                tmp[t]='\0';
                puts(stack);
                printf("\n");
                break;
            }
        }
    }
}

/*
3
E
a

E
E+E

E
E*E

a*a+a


*/

Iterative Deeping algorithm source code in C++

 Source code of iterative deeping search is given.
# include <stdio.h>
# include <iostream>
# include <sstream>
# include <algorithm>
# include <string.h>
# include <string>
# include <math.h>
# include <queue>
# include <vector>



using namespace std;



int node,edge;
vector<int>adj[100];
bool flag[100];
int dist[100],par[100],leb[100];

int bfs(int s,int e,int lev)
{
   int i,cur,head,tail,que[10000],l=0;
   head = tail = 0;
   que[head++] = s;
   flag[s] = 1;
   dist[s] = 0;
   par[s] = -1;
   leb[s] = 0;

   memset(leb,0,sizeof(leb));
   while(head != tail)
   {
       cur = que[tail++];

       if(leb[cur] == lev)
       {
           return 0 ;
       }
       cout << cur <<"= Child : ";

       for(i=0;i<adj[cur].size();i++)
       {
           if(flag[adj[cur][i]] == 0)
           {
               cout << adj[cur][i]<<" ";
               que[head++] = adj[cur][i];

               flag[adj[cur][i]] = 1;
               dist[adj[cur][i]] = dist[cur]+1;
               par[adj[cur][i]] = cur;
               leb[adj[cur][i]] = leb[cur] + 1;
               if(adj[cur][i] == e)
               {
                 return dist[cur];
               }
           }

       }
       cout<<"|";

   }
 return 0;

}

int main()
{
    int i,j,k,l,x,y,c,lev;
    while(cin >> node >> edge)
    {
            for(i=1;i<=edge;i++)
            {
                cin >> x >> y;
                adj[x].push_back(y);
                adj[y].push_back(x);
                flag[x] = flag[y] = 0;
            }
            int s,e;
            cin >> s >> e>> lev;
            for(j=1;j<=lev;j++)
            {
                memset(flag,false,sizeof(flag));
                cout<<"Level :"<<j<<endl;
                l = bfs(s,e,j);
                cout<< endl;
                //cout<< l<<endl;

                //printpath(e);
                if(l == 0)cout<<"Not found Yet"<<endl;
                else {cout<<"Found After traverse : "<<l<<" Depping : "<<j<<endl;break;}

            }

    }

    return 0;

}
/* 4 5 1 2 2 3 3 4 2 4 1 3 1 4 3 */

A*Star Serach source code in C++

#include <iostream>

#include <string>

#include <map>

#include <queue>

#include <stack>

#include <algorithm>

#include <list>

#include <set>

#include <cmath>

#include <cstring>



#include <stdio.h>

#include <string.h>

#include <sstream>

#include <stdlib.h>

#include <vector>

#include <iomanip>

#include <ctime>



using namespace std;





int dx[]={1,0,-1,0};int dy[]={0,1,0,-1};

int fx,fy,dist[100][100],row,col;



int distance(int x,int y,int p,int q);

int heuristic(int x,int y);

//vector<string>board;

int board[100][100];



struct pq

{

    int x,y,cost,h,total_cost;



    pq(int _x,int _y,int _cost)

    {

        x=_x;y=_y;cost=_cost;

        h=heuristic(x,y);

        total_cost=cost+h;

    }

    bool operator<(const pq &b)const

    {

        return total_cost>b.total_cost;    // Min Priority Queue

    }

};



int distance(int x,int y,int p,int q)

{

    if(board[p][q]>board[x][y]) return 3;

    if(board[p][q]==board[x][y]) return 2;

    return 1;

}





int heuristic(int x,int y)

{

    // manhatan distance

    return abs(x-fx)+abs(y-fy);

}



int astar(int x,int y)

{

    int i,j,m,n,cost,cnt;

    priority_queue<pq>Q;



    Q.push(pq(x,y,0));

    memset(dist,-1,sizeof(dist));



    while(!Q.empty())

    {

        pq P=Q.top();

        Q.pop();

        x=P.x;y=P.y;



        cout<< x<<" "<<y<<endl;

        if(dist[x][y]!=-1) continue;



        dist[x][y]=P.cost+P.h;



        cout<<"here"<<endl;

        for(i=0;i<4;i++)

        {

            m=x+dx[i];

            n=y+dy[i];

            if(m>=0 && m<row && n>=0 && n<col)

            {

                cout<<m<<" "<<n<<endl;

                cost=distance(x,y,m,n);

                Q.push(pq(m,n,cost+P.cost));

            }

        }

    }



}



int main()

{

    int i,j,k,sx,sy,c,p,q;

    string st;

    cout<<"Board Description :"<<endl;

    cin >> k>>c;

    row = k;col = c;

    for(i=0;i<k;i++)

    {

        for(j=0;j<c;j++)

        {

          scanf("%1d",&board[i][j]);

        }



    }

    cout<<"Start :";

    cin >>sx>>sy;

    cout<<"Goal :";

    cin>>fy>>fx;

    astar(sy,sx);

    cout<< dist[fy][fx];



    return 0;

}



/*



5 5

34567

23456

12345

23456

34567



0 2

2 2



*/