Problem with Array Passing/Kmeans Algorithm

chongl · #1 11-Jul-2007, 20:23

Hi all...my name is Larry and I am a new member to the forum. I have registered since I am having trouble with my homework. Please bear with me as I am not a CS major, but an EE/CE major, so I am aware that my code is very inefficient.

I came across a K-Means algorithm code on a website and am writing a program for my image processing class. I am trying to incorporate the code and specifying the person as the source. However, I am very new to C++ and can not get an array to pass to the program correctly. I was also wondering what the num_points and dimensions variables refer to (if anyone is familiar with K means clustering). I basically have 12 "test" images that I must cluster into 4 groups. Each of the 12 images has 9 feature points associated with it. I have hardcoded these values in the function call (hope I have the parameters correct).

My greatest problem is that I got my program to compile but it seems to error out when it gets to the function call. I put a print statement right before the call and it shows up, and when the function call is commented out the program runs fine.

Another problem I am having is with the float Laws 3D arrays. I have tried to make them 2D arrays, and the program compiles. But when I try to run the program, it just errors out. I tried to put a print statement at the very beginning of the code, but it doesn't print. I can not figure out why it works fine when I am using a 3D array. I only need a 2D array for my use.

I am using Bloodshed Dev C++ compiler on Windows XP. The K-means algorithm code I am using is written for C/C++ by Roger Zhang (I saved the file as a C++ file) and can be found here:

cs.smu.ca

Link is disabled so the site is here: cs.smu.ca/~r_zhang/code/kmeans.c

If I have violated some posting rules, please let me know...Thanks in advance!

My code is listed below.

CPP / C++ / C Code:

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <fstream>
#include <math.h>

using namespace std;

extern int *k_means(double**, int, int, int, double, double**);

// Here we assume the image is of size 256*256 and is of raw format
// You will need to make corresponding changes to accommodate images of different sizes and types

#define Size 256
#define Size2 64

int main(int argc, char *argv[])

{
	// file pointer
	FILE *file;
	int BytesPerPixel;
	
	if(argc < 1){
		cout << "usage: program_name" << endl;
		return 0;
	}
	if(argc < 2){
		BytesPerPixel = 1; // default is grey image
	}else{
		BytesPerPixel = atoi(argv[2]);
	}
	
	// image data arrays
	unsigned char Imagedata[Size][Size][BytesPerPixel];
	unsigned char Imagedata2[258][258][BytesPerPixel];
	unsigned char Imagedata3[258][258][BytesPerPixel];
	unsigned char BoundaryExtend[256+26][256+26][0];
	unsigned char Sample1[64][64][BytesPerPixel];
	unsigned char Sample2[64][64][BytesPerPixel];
	unsigned char Sample3[64][64][BytesPerPixel];
	unsigned char Sample4[64][64][BytesPerPixel];
	unsigned char Sample5[64][64][BytesPerPixel];
	unsigned char Sample6[64][64][BytesPerPixel];
	unsigned char Sample7[64][64][BytesPerPixel];
	unsigned char Sample8[64][64][BytesPerPixel];
	unsigned char Sample9[64][64][BytesPerPixel];
	unsigned char Sample10[64][64][BytesPerPixel];
	unsigned char Sample11[64][64][BytesPerPixel];
	unsigned char Sample12[64][64][BytesPerPixel];
	float Laws1[256][256][0];
	float Laws2[256][256][0];
	float Laws3[256][256][0];
	float Laws4[256][256][0];
	float Laws5[256][256][0];
	float Laws6[256][256][0];
	float Laws7[256][256][0];
	float Laws8[256][256][0];
	float Laws9[256][256][0];  
	double kmeans[12][9];
	
	// declare variables
	int k = 0;
	int l = 0;
	int m = 0;
	int n = 0;
	int x0, x1, x2, x3, x4, x5, x6, x7, x8;
	int Pixel;        
	
	k = 0;
	while (k < 12)
	{
          l = 0;
          while (l < 9)
          {
                kmeans[k][l] = 0;
                l++;
                }
                k++;
                }
   

	// read image into image data matrix
    if (!(file=fopen("sample1.raw","rb")))
    {
         cout << "Cannot open file: " << "sample1.raw" << endl;
	     exit(1);
    }
	fread(Sample1, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file); 
    if (!(file=fopen("sample2.raw","rb")))
    {
         cout << "Cannot open file: " << "sample2.raw" << endl;
	     exit(1);
    }
	fread(Sample2, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file); 	
    if (!(file=fopen("sample3.raw","rb")))
    {
         cout << "Cannot open file: " << "sample3.raw" << endl;
	     exit(1);
    }
	fread(Sample3, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file);
    if (!(file=fopen("sample4.raw","rb")))
    {
         cout << "Cannot open file: " << "sample4.raw" << endl;
	     exit(1);
    }
	fread(Sample4, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file);
    if (!(file=fopen("sample5.raw","rb")))
    {
         cout << "Cannot open file: " << "sample5.raw" << endl;
	     exit(1);
    }
	fread(Sample5, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file);
    if (!(file=fopen("sample6.raw","rb")))
    {
         cout << "Cannot open file: " << "sample6.raw" << endl;
	     exit(1);
    }
	fread(Sample6, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file);
    if (!(file=fopen("sample7.raw","rb")))
    {
         cout << "Cannot open file: " << "sample7.raw" << endl;
	     exit(1);
    }
	fread(Sample7, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file);
    if (!(file=fopen("sample8.raw","rb")))
    {
         cout << "Cannot open file: " << "sample8.raw" << endl;
	     exit(1);
    }
	fread(Sample8, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file);
    if (!(file=fopen("sample9.raw","rb")))
    {
         cout << "Cannot open file: " << "sample9.raw" << endl;
	     exit(1);
    }
	fread(Sample9, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file);
    if (!(file=fopen("sample10.raw","rb")))
    {
         cout << "Cannot open file: " << "sample10.raw" << endl;
	     exit(1);
    }
	fread(Sample10, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file);
    if (!(file=fopen("sample11.raw","rb")))
    {
         cout << "Cannot open file: " << "sample11.raw" << endl;
	     exit(1);
    }
	fread(Sample11, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file);
    if (!(file=fopen("sample12.raw","rb")))
    {
         cout << "Cannot open file: " << "sample12.raw" << endl;
	     exit(1);
    }
	fread(Sample12, sizeof(unsigned char), Size2*Size2*BytesPerPixel, file);
	fclose(file);	
////////////////////////////////////////////////////////////////////////////////////////////////




    k = 0;
    while (k < 256)
    {
        l = 0;
        while (l < 256)
        {
            Pixel = Imagedata[k][l][0];
            Imagedata2[k+1][l+1][0] = Pixel;    
            //cout << Pixel << endl;                           
            l++;
        }
        k++;
    } 	

              ///////////////////Boundary Extension
              //Imagedata3 is boundary extended and Imagedata2 is destination of image data

              Imagedata2[0][0][0] = Imagedata2[0][0][0];
              Imagedata2[0][257][0] = Imagedata2[0][255][0];
              Imagedata2[257][0][0] = Imagedata2[255][0][0];
              Imagedata2[257][257][0] = Imagedata2[255][255][0];              
    
              //Boundary extension for the non-corners 
              l = 0;  
              while (l < 256)
              {
                   Imagedata2[0][l+1][0] = Imagedata2[0][l][0];
                   Imagedata2[257][l+1][0] = Imagedata2[255][l][0];     
                   l++;
              }
              k = 0;
              while (k < 256)
              {
                    Imagedata2[k+1][0][0] = Imagedata2[k][0][0];
                    Imagedata2[k+1][257][0] = Imagedata2[k][255][0];         
                    k++;
              }                  
              //////////////////////////////////////////////////////////////////////

//Creating the Menu

    cout << endl;    
    cout << endl << "Problem 2A ";

    int option;
    option = 49;
    
    if (option == 49)
    {
         k = 0;
         while (k < 256)
         {
              l = 0;
              while (l < 256)
              {
                   //cout << (int)Imagedata2[k][l][0] << endl;
                   x0 = Imagedata2[k-1][l-1][0];
                   x1 = Imagedata2[k-1][l][0];
                   x2 = Imagedata2[k-1][l+1][0];
                   x3 = Imagedata2[k][l-1][0];
                   x4 = Imagedata2[k][l][0];        //center
                   x5 = Imagedata2[k][l+1][0];
                   x6 = Imagedata2[k+1][l-1][0];
                   x7 = Imagedata2[k+1][l][0];
                   x8 = Imagedata2[k+1][l+1][0];
                   
                   Laws1[k][l][0] = ((1 * x0) + (2 * x1) + (1 * x2) + 
                                     (2 * x3) + (4 * x4) + (2 * x5) + 
                                     (1 * x6) + (2 * x7) + (1 * x8)) / 36;
                                              
                   Laws2[k][l][0] = ((-1 * x0) + (0 * x1) + (1 * x2) + 
                                     (-2 * x3) + (0 * x4) + (2 * x5) + 
                                     (-1 * x6) + (0 * x7) + (1 * x8)) / 12;
                                              
                   Laws3[k][l][0] = ((-1 * x0) + (2 * x1) + (-1 * x2) + 
                                     (-2 * x3) + (4 * x4) + (-2 * x5) + 
                                     (-1 * x6) + (2 * x7) + (-1 * x8)) / 12;
                                              
                   Laws4[k][l][0] = ((-1 * x0) + (-2 * x1) + (-1 * x2) + 
                                     ( 0 * x3) + ( 0 * x4) + ( 0 * x5) + 
                                     ( 1 * x6) + ( 2 * x7) + ( 1 * x8)) / 12;
                                              
                   Laws5[k][l][0] = ((-1 * x0) + (0 * x1) + ( 1 * x2) + 
                                     ( 0 * x3) + (0 * x4) + ( 0 * x5) + 
                                     ( 1 * x6) + (0 * x7) + (-1 * x8)) / 4;
                                              
                   Laws6[k][l][0] = ((-1 * x0) + ( 2 * x1) + (-1 * x2) + 
                                     ( 0 * x3) + ( 0 * x4) + ( 0 * x5) + 
                                     ( 1 * x6) + (-2 * x7) + ( 1 * x8)) / 4;
                                              
                   Laws7[k][l][0] = ((-1 * x0) + (-2 * x1) + (-1 * x2) + 
                                     ( 2 * x3) + ( 4 * x4) + ( 2 * x5) + 
                                     (-1 * x6) + (-2 * x7) + (-1 * x8)) / 12;
                                              
                   Laws8[k][l][0] = (( 1 * x0) + (0 * x1) + (-1 * x2) + 
                                              (-2 * x3) + (0 * x4) + ( 2 * x5) + 
                                              ( 1 * x6) + (0 * x7) + (-1 * x8)) / 4;
                                              
                   Laws9[k][l][0] = (( 1 * x0) + (-2 * x1) + ( 1 * x2) + 
                                     (-2 * x3) + ( 4 * x4) + (-2 * x5) + 
                                     ( 1 * x6) + (-2 * x7) + ( 1 * x8)) / 4;                                                                                                                                                                                                                                                                                                                                                                             
                   l++;
              }
              k++;
         }             

         float sum1 = 0;
         float sum2 = 0;
         float sum3 = 0;
         float sum4 = 0;
         float sum5 = 0;
         float sum6 = 0;
         float sum7 = 0;;
         float sum8 = 0;
         float sum9 = 0;
         
         k = 0;         
         while (k < 256)
         {
              l = 0;
              while (l < 256)
              {
                   sum1 = sum1 + Laws1[k][l][0] * Laws1[k][l][0];
                   sum2 = sum2 + Laws2[k][l][0] * Laws2[k][l][0];
                   sum3 = sum3 + Laws3[k][l][0] * Laws3[k][l][0];
                   sum4 = sum4 + Laws4[k][l][0] * Laws4[k][l][0];
                   sum5 = sum5 + Laws5[k][l][0] * Laws5[k][l][0];
                   sum6 = sum6 + Laws6[k][l][0] * Laws6[k][l][0];
                   sum7 = sum7 + Laws7[k][l][0] * Laws7[k][l][0];
                   sum8 = sum8 + Laws8[k][l][0] * Laws8[k][l][0];
                   sum9 = sum9 + Laws9[k][l][0] * Laws9[k][l][0];                                                                                                                                                        
                   l++;
              }
              k++;
         }
         sum1 = sum1 / (256 * 256);
         sum2 = sum2 / (256 * 256);
         sum3 = sum3 / (256 * 256);
         sum4 = sum4 / (256 * 256);
         sum5 = sum5 / (256 * 256);
         sum6 = sum6 / (256 * 256);
         sum7 = sum7 / (256 * 256);
         sum8 = sum8 / (256 * 256);
         sum9 = sum9 / (256 * 256);
         
         cout << sum1 << endl;
         cout << sum2 << endl;
         cout << sum3 << endl;
         cout << sum4 << endl;
         cout << sum5 << endl;
         cout << sum6 << endl;
         cout << sum7 << endl;
         cout << sum8 << endl;
         cout << sum9 << endl;
         
         int numberClusters = 4;
         cout << "test";
         //data is 2D Array...followed by num_points and dimensions
//   int *c = k_means(data_points, num_points, dim, 20, 1e-4, 0);
   int *c = k_means((double **)kmeans, 12, 9, numberClusters, 1e-4, 0);
   for (int i = 0; i < 12; i++) {
      printf("data point %d is in cluster %d\n", i, c[i]);
   }
   free(c);         

         
    }
/////////////////////////////////////////////////////////////////////////////////////////////////////////
   	return 0;
}

davekw7x · #2 12-Jul-2007, 13:40

Quote:

Originally Posted by chongl

My greatest problem is that I got my program to compile but it seems to error out when it gets to the function call.

Well I have a number of problems with your code.

1. Maybe not a biggie for you, but bad news for others. Standard C++ does not allow variable-length arrays so things like the following won't compile with some commonly-used C++ compilers:

CPP / C++ / C Code:

    int BytesPerPixel;
.
.
.
    unsigned char Imagedata[Size][Size][BytesPerPixel];

This feature of the latest C standard may be available with some C++ compilers (GNU, for example). But it's not standard C++. If your C++ compiler accepts it, with no errors, then changing it won't solve your problem, so don't worry about it for now. I just thought I would mention it in case some other people want to help and they find that their compiler gags on this.

2. A biggie. Standard C++ does not allow array dimensions to be zero, so things like the following will not be accepted by some C++ compilers:

CPP / C++ / C Code:

    unsigned char BoundaryExtend[256+26][256+26][0];

Even if your compiler accepts declarations of objects with size equal to zero, absolutely nothing good can come from it. You don't use BoundaryExtend anywhere, but if you ever tried to store or retrieve information from that array, it would be illegal (undefined behavior up to and including program crash, or maybe even worse, some silent bug that would not show up in testing but would bite you in the butt later).

The amount of memory allocated to an array is the product of the individual dimension sizes. If you absolutely need a 3-D array for some purpose not obvious in the code that you posted, you can make the third dimension [1] instead of [0]. But I can't imagine the situation where that is necessary or sufficient to get your application working.

As far as the Lawsx[][][] arrays, just make the declarations 2-D, like

CPP / C++ / C Code:

    float Laws1[256][256]; // and for the other Lawsx stuff

And change the assignments accordingly

CPP / C++ / C Code:

        Laws1[k][l] = whatever

3. This is the last biggie, and it's a dusie: You say that you "got my program to compile," and I'm thinking that the only you got it to compile was by lying to the compiler:

CPP / C++ / C Code:

    double kmeans[12][9];
.
.
.

   int *c = k_means((double **)kmeans, 12, 9, numberClusters, 1e-4, 0);

Why did you put the cast on kmeans? I know why: because the compiler wouldn't accept it otherwise. The function takes a pointer to pointer to double. You don't have a pointer to pointer; you have a 2-Dimension array of doubles. They are not the same. Never have been. Never will be. You can make the compiler accept that statement by lying, but the code inside the function will not work. Never could work. Never will work. The way that the compiler generates code to access the elements of an array defined by pointer-to-pointer is different from the way the code accesses elements of a 2-Dimension array. The user program can use [][] notation to access either type, but the compiled code is quite different.

I'm not trying to give you a hard time, but this is not uncommon: Someone with no experience with a language gets some canned program from somewhere and tries to cobble up some kind of application without any basic understanding.

To prove my honorable intentions and not just flame you for not knowing, I offer a suggestion. Give it what it needs.

CPP / C++ / C Code:

	//double kmeans[12][9];
        double **kmeans;
        kmeans = new double *[12];
        for (int i = 0; i < 12; i++) {
            kmeans[i] = new double[9];
        }

You have created the equivalent of a 2-D array, but now it is in the form that the function needs.

Now, I have some other concerns, that may or may not be a problem. You have more than a few megabytes of storage allocated by things like

CPP / C++ / C Code:

    float Laws1[256][256]; // nine of these plus some others

If you fix the kmeans thing like I showed above and the program still crashes with no error messages, it is just possible that your compiler/linker won't support this much automatic storage. You might have to go back and make all of these "static", (the memory comes from another place). That is:

CPP / C++ / C Code:

    static float Laws1[256][256]; // and for other large arrays

In fact, why don't you do it now:

CPP / C++ / C Code:

	static float Laws1[256][256];
	static float Laws2[256][256];
	static float Laws3[256][256];
	static float Laws4[256][256];
	static float Laws5[256][256];
	static float Laws6[256][256];
	static float Laws7[256][256];
	static float Laws8[256][256];
	static float Laws9[256][256];

(You won't be able to make the variable-length arrays "static", but the Laws are the big hitters. Change them.)

One final note: If you are going to put the kmeans code in a separate file, the easiest way to get it to compile properly with the C++ code of your main() function is to call the other one kmeans.cpp. The kmeans code is C code, but will compile OK as C++ also. Make sure they both get compiled as C++. (Otherwise linking C code with C++ code requires a little more work).

Regards,

Dave

"No one was born knowing this stuff, you know."
---davekw7x

chongl · #3 14-Jul-2007, 18:36

Dave...Thank you for schooling me...I managed to get the program working because of you. The static portion fixed the exact issue I was trying to describe, and defining the array as you specified made it work.

Under point 1, my arrays are not dynamic. They are fixed sizes due to the #define.

Again...I would like to express my gratitude for your assistance. I was not able to PM you to deliver this more personally.

Larry

davekw7x · #4 14-Jul-2007, 19:39

Quote:

Originally Posted by chongl

Under point 1, my arrays are not dynamic. They are fixed sizes due to the #define.

Quite a few are variable length arrays, since BytesPerPixel is a variable whose value is obtained from a command line argument. As I mentioned, this is not part of the C++ Standard, but if your compiler accepts them, and things work as you wish, I am happy (really).

I just thought I would mention it in case some of the readers of this thread try it with Borland or Microsoft compilers like the ones that I have used. Or if GNU users turn on the "-pedantic" command line switch to make sure that the code complies with the Standard (Won't work.)

I am very glad to have been given the chance to help.

Good Luck!

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
How to sort in C++ alphabetically	wilen	C++ Forum	5	20-Apr-2007 15:43
problem with filling a char array in a windows GUI app.	ryver	C++ Forum	1	13-Aug-2006 09:22
Need help deleting the last element in the array	headphone69	C++ Forum	2	15-Mar-2006 20:31
template comiling problems - need expert debugger!	crq	C++ Forum	1	01-Feb-2005 22:26
Problem in array	Kay Chan	C Programming Language	2	05-Oct-2004 22:16

Problem with Array Passing/Kmeans Algorithm

Re: Problem with Array Passing/Kmeans Algorithm

Re: Problem with Array Passing/Kmeans Algorithm

Re: Problem with Array Passing/Kmeans Algorithm