We help IT Professionals succeed at work.

K-Means in C#

raheelasadkhan
on
4,784 Views
Last Modified: 2011-12-09
I have an implementation of the K-Means algorithm in C# that needs some serious performance tuning. The code is pasted in the message below.

There are two classes used Image and DominantColor
   Image simply openes up image files and retrieves the RGB/HSV/HSV values while the DominantColor class computes clusters.

Any ideas would be appreciated.
Comment
Watch Question

Author

Commented:
public static void main ()
{
   bool                           result            = false;
   long                           ticks            = 0;
   string                           filename         = "";
   double                           seconds            = 0.0D;
   Clustering.Library.Image            image            = null;
   Clustering.Library.DominantColor      dominantColor      = null;

   filename   = @"C:\Temp\Pics\SomeImage.gif";

   image      = new Clustering.Library.Image();
   result      = image.Open(filename, out message);

   if (result)
   {
      dominantColor   = new Clustering.Library.DominantColor();
      ticks         = System.DateTime.Now.Ticks;
      dominantColor.Compute(image);
      seconds         = System.Math.Round(((double) (System.DateTime.Now.Ticks - ticks)) / 10000000D, 2);
      System.Windows.Forms.MessageBox.Show("Operation took: " + seconds.ToString() + " second(s)");
   }
}

namespace Clustering.Library
{
   public class Image: System.IDisposable
   {
      //****************************************************************************************************/
      // Constants
      //****************************************************************************************************/

      //****************************************************************************************************/
      // Enumerations
      //****************************************************************************************************/

      //****************************************************************************************************/
      // Structures
      //****************************************************************************************************/

      //****************************************************************************************************/
      // Members
      //****************************************************************************************************/

      private      bool         _Disposed      = false;

      private      int            _Width         = 0;
      private      int            _Height         = 0;
      private      int            _BitsPerPixel   = 0;
      private      int            _BytesPerPixel   = 0;
      private      int            _SizeInBytes   = 0;
      private      int            _SizeInPixels   = 0;
      private      byte   []      _R            = null;
      private      byte   []      _G            = null;
      private      byte   []      _B            = null;
      private      byte   []      _RGB         = null;
      private      float   []      _H            = null;
      private      float   []      _S            = null;
      private      float   []      _V            = null;
      private      float   []      _HSV         = null;

      //****************************************************************************************************/
      // Constructors / Initialization / Destructors
      //****************************************************************************************************/

      public Image ()
      {
         this.Initialize();
      }

      public void Initialize ()
      {
         this.Width         = 0;
         this.Height         = 0;
         this.BitsPerPixel   = 0;
         this.BytesPerPixel   = 0;
         this.SizeInBytes   = 0;
         this.SizeInPixels   = 0;

         this._R      = null;
         this._G      = null;
         this._B      = null;
         this._RGB   = null;
         this._H      = null;
         this._S      = null;
         this._V      = null;
         this._HSV   = null;
      }

      ~Image ()
      {
         // Do not re-create Dispose clean-up code here.
         //   Calling Dispose(false) is optimal in terms of readability and maintainability.
         this.Dispose(false);
      }

      //****************************************************************************************************/
      // Proterties
      //****************************************************************************************************/

      public int Width
      {
         get   {return(this._Width);}
         set   {this._Width = value;}
      }

      public int Height
      {
         get   {return(this._Height);}
         set   {this._Height = value;}
      }

      public int SizeInBytes
      {
         get   {return(this._SizeInBytes);}
         set   {this._SizeInBytes = value;}
      }

      public int SizeInPixels
      {
         get   {return(this._SizeInPixels);}
         set   {this._SizeInPixels = value;}
      }

      public int BytesPerPixel
      {
         get   {return(this._BytesPerPixel);}
         set   {this._BytesPerPixel = value;}
      }

      public int BitsPerPixel
      {
         get   {return(this._BitsPerPixel);}
         set   {this._BitsPerPixel = value;}
      }

      public byte [] R
      {
         get   {return(this._R);}
      }

      public byte [] G
      {
         get   {return(this._G);}
      }

      public byte [] B
      {
         get   {return(this._B);}
      }

      public byte [] RGB
      {
         get   {return(this._RGB);}
      }

      public float [] H
      {
         get   {return(this._H);}
      }

      public float [] S
      {
         get   {return(this._S);}
      }

      public float [] V
      {
         get   {return(this._V);}
      }

      public float [] HSV
      {
         get   {return(this._HSV);}
      }

      //****************************************************************************************************/
      // Indexers
      //****************************************************************************************************/

      //****************************************************************************************************/
      // Functions
      //****************************************************************************************************/

      public bool Open (string filename, out string message)
      {
         float               r, g, b;
         byte   []            buffer   = null;
         System.Drawing.Color   color;
         System.Drawing.Image   image   = null;
         System.Drawing.Bitmap   bitmap   = null;

         message      = "";

         try
         {
            image   = System.Drawing.Image.FromFile(filename);

            this.BytesPerPixel   = 3;
            this.BitsPerPixel   = this.BytesPerPixel * 8;
            this.Width         = image.Width;
            this.Height         = image.Height;
            this.SizeInPixels   = this.Width * this.Height;
            this.SizeInBytes   = this.Width * this.Height * this.BytesPerPixel;

            try
            {
               bitmap   = new System.Drawing.Bitmap(image);

               try
               {
                  buffer      = new byte [this.SizeInBytes];
                  for (int y=0, i=0; y<this.Height; y++)
                  {
                     for (int x=0; x<this.Width; x++, i+=this.BytesPerPixel)
                     {
                        color   = bitmap.GetPixel(x, y);

                        buffer[i+0]   = color.R;
                        buffer[i+1]   = color.G;
                        buffer[i+2]   = color.B;
                     }
                  }

                  //System.Runtime.InteropServices.Marshal.Copy(bitmapData.Scan0, buffer, 0, this.SizeInBytes);

                  // Asssign RGB, R, G, B
                  this._RGB   = buffer;
                  this._R      = new byte [this.SizeInPixels];
                  this._G      = new byte [this.SizeInPixels];
                  this._B      = new byte [this.SizeInPixels];
                  for (int i=0, j=0; i<this.SizeInPixels; i++, j+=3)
                  {
                     this._R[i]   = buffer[j+0];
                     this._G[i]   = buffer[j+1];
                     this._B[i]   = buffer[j+2];
                  }
                  // Asssign HSV, H, S, V
                  this._H      = new float [this.SizeInPixels];
                  this._S      = new float [this.SizeInPixels];
                  this._V      = new float [this.SizeInPixels];
                  this._HSV   = new float [this.SizeInBytes];
                  for (int i=0, j=0; i<this.SizeInPixels; i++, j+=3)
                  {
                     r   = this._R[i] / 255.0F;
                     g   = this._G[i] / 255.0F;
                     b   = this._B[i] / 255.0F;
                     this.RgbToHsv(r, g, b, out this._H[i], out this._S[i], out this._V[i]);
                     this.HSV[j+0]   = this._H[i];
                     this.HSV[j+1]   = this._S[i];
                     this.HSV[j+2]   = this._V[i];
                  }
               }
               catch (System.Exception exception)
               {
                  message
                     +=   System.Environment.NewLine
                     +   "   - "
                     +   exception.Message;
               }

               bitmap.Dispose();
            }
            catch (System.Exception exception)
            {
               message
                  +=   System.Environment.NewLine
                  +   "   - "
                  +   exception.Message;
            }

            image.Dispose();
         }
         catch (System.Exception exception)
         {
            message
               +=   System.Environment.NewLine
               +   "   - "
               +   exception.Message;
         }

         if (message.Length == 0)
         {
            return (true);
         }
         else
         {
            message
               = "The following error(s) occured:"
               + message
               ;

            this.Close();

            return (false);
         }
      }

      /// <summary>
      /// This function is included only for reference. The copy memory methos is extremely fast
      /// but does not yet work properly
      /// </summary>
      /// <param name="filename"></param>
      /// <param name="message"></param>
      /// <returns></returns>
      public bool OpenFast (string filename, out string message)
      {
         float               r, g, b;
         byte   []            buffer   = null;
         System.Drawing.Image   image   = null;
         System.Drawing.Bitmap   bitmap   = null;

         message      = "";

         try
         {
            image   = System.Drawing.Image.FromFile(filename);

            this.BytesPerPixel   = 3;
            this.BitsPerPixel   = this.BytesPerPixel * 8;
            this.Width         = image.Width;
            this.Height         = image.Height;
            this.SizeInPixels   = this.Width * this.Height;
            this.SizeInBytes   = this.Width * this.Height * this.BytesPerPixel;

            try
            {
               bitmap   = new System.Drawing.Bitmap(image);

               try
               {
                  System.Drawing.Imaging.BitmapData   bitmapData   = bitmap.LockBits
                     (
                     new System.Drawing.Rectangle(0, 0, bitmap.Width, bitmap.Height),
                     System.Drawing.Imaging.ImageLockMode.ReadWrite,
                     System.Drawing.Imaging.PixelFormat.Format24bppRgb
                     );

                  try
                  {
                     buffer      = new byte [this.SizeInBytes];

                     System.Runtime.InteropServices.Marshal.Copy(bitmapData.Scan0, buffer, 0, this.SizeInBytes);

                     // Asssign RGB, R, G, B
                     this._RGB   = buffer;
                     this._R      = new byte [this.SizeInPixels];
                     this._G      = new byte [this.SizeInPixels];
                     this._B      = new byte [this.SizeInPixels];
                     for (int i=0, j=0; i<this.SizeInPixels; i++, j+=3)
                     {
                        this._R[i]   = buffer[j+0];
                        this._G[i]   = buffer[j+1];
                        this._B[i]   = buffer[j+2];
                     }
                     // Asssign HSV, H, S, V
                     this._H      = new float [this.SizeInPixels];
                     this._S      = new float [this.SizeInPixels];
                     this._V      = new float [this.SizeInPixels];
                     this._HSV   = new float [this.SizeInBytes];
                     for (int i=0, j=0; i<this.SizeInPixels; i++, j+=3)
                     {
                        r   = this._R[i] / 255.0F;
                        g   = this._G[i] / 255.0F;
                        b   = this._B[i] / 255.0F;
                        this.RgbToHsv(r, g, b, out this._H[i], out this._S[i], out this._V[i]);
                        this.HSV[j+0]   = this._H[i];
                        this.HSV[j+1]   = this._S[i];
                        this.HSV[j+2]   = this._V[i];
                     }
                  }
                  catch (System.Exception exception)
                  {
                     message
                        +=   System.Environment.NewLine
                        +   "   - "
                        +   exception.Message;
                  }

                  bitmap.UnlockBits(bitmapData);
               }
               catch (System.Exception exception)
               {
                  message
                     +=   System.Environment.NewLine
                     +   "   - "
                     +   exception.Message;
               }

               bitmap.Dispose();
            }
            catch (System.Exception exception)
            {
               message
                  +=   System.Environment.NewLine
                  +   "   - "
                  +   exception.Message;
            }

            image.Dispose();
         }
         catch (System.Exception exception)
         {
            message
               +=   System.Environment.NewLine
               +   "   - "
               +   exception.Message;
         }

         if (message.Length == 0)
         {
            return (true);
         }
         else
         {
            message
               = "The following error(s) occured:"
               + message
               ;

            this.Close();

            return (false);
         }
      }

      public void Close ()
      {
         this.Initialize();
      }

      public void RgbToHsv (float r, float g, float b, out float h, out float s, out float v)
      {
         float   min      = 0;
         float   max      = 0;
         float   delta   = 0;

         if (r < g)
         {
            if (r < b)
               min   = r;
            else
               min   = b;
         }
         else
         {
            if (g < b)
               min   = g;
            else
               min   = b;
         }

         if (r > g)
         {
            if (r > b)
               max   = r;
            else
               max   = b;
         }
         else
         {
            if (g > b)
               max   = g;
            else
               max   = b;
         }

         delta   = max - min;

         if (max == 0)
         {
            h   = -1.0F;
            s   = -1.0F;
            v   = 0.0F;
         }
         else
         {
            if (min == max)
            {
               h   = -1.0F;
               s   = 0.0F;
               v   = max;
            }
            else
            {
               if (max == r)
               {
                  if (g < b)
                  {
                     h   = 60 * ((g - b) / delta) + 360.0F;
                  }
                  else
                  {
                     h   = 60 * ((g - b) / delta) + 0.0F;
                  }
               }
               else if (max == g)
               {
                  h   = 60 * ((b - r) / delta) + 120.0F;
               }
               else if (max == b)
               {
                  h   = 60 * ((r - g) / delta) + 240.0F;
               }
               else
               {
                  h   = -1.0F;
               }
               s   = delta / max;
               v   = max;
            }
         }
      }

      //****************************************************************************************************/
      // Interface Implementation: System.IDisposable
      //****************************************************************************************************/

      // Implement System.IDisposable.
      //   Do not make this method virtual.
      //   A derived class should not be able to override this method.
      public void Dispose ()
      {
         this.Dispose(true);
         // This object will be cleaned up by the Dispose method.
         //   Take this object off the finalization queue and prevent finalization code for this object from executing a second time.
         System.GC.SuppressFinalize(this);
      }

      // Dispose (bool this._Disposing) executes in two distinct scenarios.
      //   If disposing equals true, the method has been called directly or indirectly by a user's code. Managed and unmanaged resources can be disposed.
      //   If disposing equals false, the method has been called by the runtime from inside the finalizer and you should not reference other objects.
      //   Only unmanaged resources can be disposed.
      private void Dispose (bool disposing)
      {
         if (!this._Disposed)
         {
            // If disposing equals true, dispose all managed and unmanaged resources.
            if (disposing)
            {
               // Dispose managed resources here.
               this.Close();
            }

            // Call the appropriate methods to clean up unmanaged resources here.
            //   If disposing is false, only the following code is executed.
            //   Dispose unmanaged resources here.
         }
         this._Disposed   = true;        
      }

   }
}

namespace Clustering.Library
{
   //****************************************************************************************************/
   // Structures
   //****************************************************************************************************/

   public struct DataPoint
   {
      public      double      H;
      public      double      S;
      public      double      V;
      public      int         ClusterIndex;

      public DataPoint (double h, double s, double v)
      {
         this.ClusterIndex   = -1;

         this.H            = h;
         this.S            = s;
         this.V            = v;
      }

      public void Initialize ()
      {
         this.ClusterIndex   = -1;

         this.H            = 0D;
         this.S            = 0D;
         this.V            = 0D;
      }
   }

   public class DominantColor: System.IDisposable
   {
      //****************************************************************************************************/
      // Constants
      //****************************************************************************************************/

      public   const   int         CLUSTER_COUNT         = 20;
      public   const   double      MEANS_CUTOFF_TO_END      = 0.001D;

      //****************************************************************************************************/
      // Members
      //****************************************************************************************************/

      private      bool                           _Disposed      = false;

      // The main array of data points that will hold the image data
      private      Clustering.Library.DataPoint   []      _DataPointCollection;
      // Simple int array to hold the cluster index for each data point
      //   Length will be the same as _DataPointCollection
      private      int                        []      _ClusterIndexCollection;
      // An array of ArrayList objects. The array will be of length CLUSTER_COUNT and
      //   will hold one ArrayList for each cluster. Each ArrayList will store only the
      //   data point index from _DataPointCollection. I've used this approach since it
      //   saves memory and the BinarySearch feature in ArrayList objects is lightning fast.
      // This array is not neccessary but I've included it since this aproach increases
      //   performance dramatically
      private      System.Collections.ArrayList   []      _ClusterIndexCollectionCollection;
      // Simple data point array to hold the mean of each cluster
      //   Length will be the same as CLUSTER_COUNT
      private      Clustering.Library.DataPoint   []      _MeanCollection;
      // Simple data point array to hold the old mean of each cluster
      //   Length will be the same as CLUSTER_COUNT
      private      Clustering.Library.DataPoint   []      _MeanOldCollection;

      public DominantColor ()
      {
         this.Initialize();
      }

      public void Initialize ()
      {
         this._DataPointCollection            = null;
         this._ClusterIndexCollection         = null;
         this._ClusterIndexCollectionCollection   = null;
         this._MeanCollection               = null;
         this._MeanOldCollection               = null;
      }

      public void Initialize (int rowCount)
      {
         this.Initialize();

         this._DataPointCollection      = new Clustering.Library.DataPoint[rowCount];
         for (int i=0; i<this._DataPointCollection.Length; i++)
         {
            this._DataPointCollection[i].Initialize();
         }

         this._ClusterIndexCollection   = new int [rowCount];
         for (int i=0; i<this._ClusterIndexCollection.Length; i++)
         {
            this._ClusterIndexCollection[i]   = -1;
         }

         this._ClusterIndexCollectionCollection   = new System.Collections.ArrayList [CLUSTER_COUNT];
         for (int i=0; i<this._ClusterIndexCollectionCollection.Length; i++)
         {
            this._ClusterIndexCollectionCollection[i]   = new System.Collections.ArrayList();
         }

         this._MeanCollection   = new Clustering.Library.DataPoint [CLUSTER_COUNT];
         for (int i=0; i<this._MeanCollection.Length; i++)
         {
            this._MeanCollection[i].H   = 0D;
            this._MeanCollection[i].S   = 0D;
            this._MeanCollection[i].V   = 0D;
         }

         this._MeanOldCollection   = new Clustering.Library.DataPoint [CLUSTER_COUNT];
         for (int i=0; i<this._MeanOldCollection.Length; i++)
         {
            this._MeanOldCollection[i].H   = 0D;
            this._MeanOldCollection[i].S   = 0D;
            this._MeanOldCollection[i].V   = 0D;
         }
      }

      ~DominantColor ()
      {
         // Do not re-create Dispose clean-up code here.
         //   Calling Dispose(false) is optimal in terms of readability and maintainability.
         this.Dispose(false);
      }

      //****************************************************************************************************/
      // Properties
      //****************************************************************************************************/

      public Clustering.Library.DataPoint [] DataPointCollection
      {
         get   {return (this._DataPointCollection);}
      }

      public int [] ClusterIndexCollection
      {
         get   {return (this._ClusterIndexCollection);}
      }

      public System.Collections.ArrayList [] ClusterIndexCollectionCollection
      {
         get   {return (this._ClusterIndexCollectionCollection);}
      }

      public Clustering.Library.DataPoint [] MeanCollection
      {
         get   {return (this._MeanCollection);}
      }

      public Clustering.Library.DataPoint [] MeanOldCollection
      {
         get   {return (this._MeanOldCollection);}
      }

      //****************************************************************************************************/
      // Functions
      //****************************************************************************************************/

      public void Compute (Clustering.Library.Image image)
      {
         int            indexDataPoint      = 0;
         double         distanceCurrent      = 0.0D;
         double         distanceClosest      = 0.0D;
         int            clusterIndex      = -1;
         int            displacement      = 0;
         int            clusterIndexTemp   = 0;
         System.Random   random            = null;

         // Initialize
         this.Initialize(image.SizeInPixels);
         //   Data
         for (int i=0; i<image.SizeInPixels; i++)
         {
            this._DataPointCollection[i].H   = image.H[i];
            this._DataPointCollection[i].S   = image.S[i];
            this._DataPointCollection[i].V   = image.V[i];
         }

         // Create initial clusters by assigning one random row to each
         random   = new System.Random();
         for (int i=0; i<CLUSTER_COUNT; i++)
         {
            indexDataPoint      = random.Next(0, this._DataPointCollection.Length);
            while (this._DataPointCollection[indexDataPoint].ClusterIndex >= 0)
            {
               indexDataPoint      = random.Next(0, this._DataPointCollection.Length);
            }

            this.AssignDataPointToCluster(i, indexDataPoint);
            this.ComputeClusterMean(i);
         }

         // Assign all unassigned data points to the relevant cluster
         for (int i=0; i<this._DataPointCollection.Length; i++)
         {
            // Filter out only unassigned data points
            switch (this._DataPointCollection[i].ClusterIndex)
            {
               case -1:
               {
                  clusterIndex   = -1;
                  for (int j=0; j<CLUSTER_COUNT; j++)
                  {
                     switch (j)
                     {
                        case 0:
                        {
                           distanceClosest   = this.EuclideanDistance(ref this._DataPointCollection[i], ref this._MeanCollection[j]);

                           clusterIndex   = j;

                           break;
                        }
                        default:
                        {
                           distanceCurrent   = this.EuclideanDistance(ref this._DataPointCollection[i], ref this._MeanCollection[j]);

                           if (distanceCurrent < distanceClosest)
                           {
                              distanceClosest   = distanceCurrent;

                              clusterIndex   = j;

                              break;
                           }

                           break;
                        }
                     }
                  }

                  // No validation checks needed since assigned data points have already been filtered out
                  //   and clusterIndex will always hold a valid value
                  displacement++;
                  this.AssignDataPointToCluster(clusterIndex, i);
                  this.ComputeClusterMean(clusterIndex);

                  break;
               }
            }
         }

         // All data points have already been assigned to some cluster
         //   This loop re-assigns each one
         while (true)
         {
            displacement   = 0;
            for (int i=0; i<this._DataPointCollection.Length; i++)
            {
               clusterIndex   = -1;
               for (int j=0; j<CLUSTER_COUNT; j++)
               {
                  switch (j)
                  {
                     case 0:
                     {
                        distanceClosest   = this.EuclideanDistance(ref this._DataPointCollection[i], ref this._MeanCollection[j]);

                        clusterIndex   = j;

                        break;
                     }
                     default:
                     {
                        distanceCurrent   = this.EuclideanDistance(ref this._DataPointCollection[i], ref this._MeanCollection[j]);

                        if (distanceCurrent < distanceClosest)
                        {
                           distanceClosest   = distanceCurrent;

                           clusterIndex   = j;

                           break;
                        }

                        break;
                     }
                  }
               }

               // Avoid redundant reassigning to same cluster
               if (this._DataPointCollection[i].ClusterIndex != clusterIndex)
               {
                  // The data point was already assigned to another cluster
                  //   Due to reassignment, the From and To cluster Mean values
                  //   will be affected so we need to recalculate new Mean values
                  //   for both
                  displacement++;
                  clusterIndexTemp   = this._DataPointCollection[i].ClusterIndex;
                  this.AssignDataPointToCluster(clusterIndex, i);
                  this.ComputeClusterMean(clusterIndex);
                  this.ComputeClusterMean(clusterIndexTemp);
               }
            }

            // I'm probably wrong but I figured that zero displacement could act as a potential
            //   terminating condition. Not sure what to do here
            if ((clusterIndex == -1) || (displacement == 0))
            {
               break;
            }
         }
      }

      // These variables are exclusive to the AssignDataPointToCluster function and should not be accessed elsewhere
      //   Declared at class level for performance.
      private      int      _AssignDataPointToClusterIndexTemp         = 0;
      private      int      _AssignDataPointToClusterIndexClusterOld   = 0;
      private void AssignDataPointToCluster (int indexCluster, int indexDataPoint)
      {
         this._AssignDataPointToClusterIndexClusterOld   = this._DataPointCollection[indexDataPoint].ClusterIndex;

         if (this._AssignDataPointToClusterIndexClusterOld >= 0)
         {
            // Remove data point this._IndexTemp from old cluster array list
            this._AssignDataPointToClusterIndexTemp      = this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].BinarySearch(indexDataPoint);
            this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].RemoveAt(this._AssignDataPointToClusterIndexTemp);
         }

         this._DataPointCollection[indexDataPoint].ClusterIndex   = indexCluster;
         this._ClusterIndexCollection[indexCluster]            = indexDataPoint;

         this._AssignDataPointToClusterIndexTemp   = this._ClusterIndexCollectionCollection[indexCluster].BinarySearch(indexDataPoint);
         if (this._AssignDataPointToClusterIndexTemp < 0)
         {
            this._ClusterIndexCollectionCollection[indexCluster].Insert(~this._AssignDataPointToClusterIndexTemp, indexDataPoint);
         }
      }

      // These variables are exclusive to the EuclideanDistance function and should not be accessed elsewhere
      //   Declared at class level for performance.
      private      double      _EuclideanDistanceResult      = 0.0D;
      // Passing the parameters by reference is good to avoid unnecessary copying since we are using structs
      private double EuclideanDistance (ref Clustering.Library.DataPoint dataPoint1, ref Clustering.Library.DataPoint dataPoint2)
      {
         this._EuclideanDistanceResult   = 0.0D;

         this._EuclideanDistanceResult
            = System.Math.Pow(dataPoint1.H - dataPoint2.H, 2.0D)
            + System.Math.Pow(dataPoint1.S - dataPoint2.S, 2.0D)
            + System.Math.Pow(dataPoint1.V - dataPoint2.V, 2.0D)
            ;

         return (System.Math.Sqrt(this._EuclideanDistanceResult));
      }

      // These variables are exclusive to the EuclideanDistance function and should not be accessed elsewhere
      //   Declared at class level for performance.
      private      int      _ComputeClusterMeanIndexDataPoint            = 0;
      private      int      _ComputeClusterMeanClusterDataPointCount      = 0;
      private void ComputeClusterMean (int indexCluster)
      {
         for (int i=0; i<CLUSTER_COUNT; i++)
         {
            this._MeanOldCollection[i].H   = this._MeanCollection[i].H;
            this._MeanOldCollection[i].S   = this._MeanCollection[i].S;
            this._MeanOldCollection[i].V   = this._MeanCollection[i].V;
         }

         for (int i=0; i<CLUSTER_COUNT; i++)
         {
            this._MeanCollection[i].H   = 0D;
            this._MeanCollection[i].S   = 0D;
            this._MeanCollection[i].V   = 0D;
         }

         for (int i=0; i<CLUSTER_COUNT; i++)
         {
            for (int j=0; j<this._ClusterIndexCollectionCollection[i].Count; j++)
            {
               this._ComputeClusterMeanIndexDataPoint   = (int) this._ClusterIndexCollectionCollection[i][j];
               this._MeanCollection[i].H   += this._DataPointCollection[this._ComputeClusterMeanIndexDataPoint].H;
               this._MeanCollection[i].S   += this._DataPointCollection[this._ComputeClusterMeanIndexDataPoint].S;
               this._MeanCollection[i].V   += this._DataPointCollection[this._ComputeClusterMeanIndexDataPoint].V;
            }
         }

         for (int i=0; i<CLUSTER_COUNT; i++)
         {
            this._ComputeClusterMeanClusterDataPointCount   = this._ClusterIndexCollectionCollection[i].Count;
            switch (this._ComputeClusterMeanClusterDataPointCount)
            {
               case 0:
               {
                  this._MeanCollection[i].H   = 0D;
                  this._MeanCollection[i].S   = 0D;
                  this._MeanCollection[i].V   = 0D;

                  break;
               }
               default:
               {
                  this._MeanCollection[i].H   /= this._ComputeClusterMeanClusterDataPointCount;
                  this._MeanCollection[i].S   /= this._ComputeClusterMeanClusterDataPointCount;
                  this._MeanCollection[i].V   /= this._ComputeClusterMeanClusterDataPointCount;

                  break;
               }
            }
         }
      }

      //****************************************************************************************************/
      // Interface Implementation: System.IDisposable
      //****************************************************************************************************/

      // Implement System.IDisposable.
      //   Do not make this method virtual.
      //   A derived class should not be able to override this method.
      public void Dispose ()
      {
         this.Dispose(true);
         // This object will be cleaned up by the Dispose method.
         //   Take this object off the finalization queue and prevent finalization code for this object from executing a second time.
         System.GC.SuppressFinalize(this);
      }

      // Dispose (bool this._Disposing) executes in two distinct scenarios.
      //   If disposing equals true, the method has been called directly or indirectly by a user's code. Managed and unmanaged resources can be disposed.
      //   If disposing equals false, the method has been called by the runtime from inside the finalizer and you should not reference other objects.
      //   Only unmanaged resources can be disposed.
      private void Dispose (bool disposing)
      {
         if (!this._Disposed)
         {
            // If disposing equals true, dispose all managed and unmanaged resources.
            if (disposing)
            {
               // Dispose managed resources here.
               this.Initialize();
            }

            // Call the appropriate methods to clean up unmanaged resources here.
            //   If disposing is false, only the following code is executed.
            //   Dispose unmanaged resources here.
         }
         this._Disposed   = true;        
      }

   }
}
This one is on us!
(Get your first solution completely free - no credit card required)
UNLOCK SOLUTION

Author

Commented:
Thanks for your input.

This was my first time with the algorithm and I had a lot of help from Andy at (https://www.experts-exchange.com/Programming/Programming_Languages/C_Sharp/Q_21871415.html). I was too busy trying to understand clustering concepts to analyze the code. Towards the end, I went for a straight linear approach instead of taking advantage of OO features.

Your first suggestion is a killer. Instead of iterating through 2 entire clusters, remembering the totals will probably reduce computing time drastically. I did suspect the AssignDataPointToCluster() method as a major culprit.

Regarding HashTables vs ArrayLists, I'm not too familiar with the internal workings of HashTables but I imagine they operate on some sort of Binary Tree storage concept. If that is the case, the BinarySearch feature of ArrayLists should be comparable in performance. I'll try HashTables anyways.

Regarding EuclideanDistance, you're absolutely right again. Since I don't need the actual values apart from comparison, the Sqrt can be skipped. And, of course, should have thought of Pow vs * as well.

Regarding initialization, I'm already working on splitting the image into square tiles since the decrease in performance is exponential on image size.

As far as the terminating condition is concerned, the clusters do have to be perfect. That is one of the restrictions I have to live by.

Regarding the Image.Open method, the performance is very fast (1 second for a 1000x1000 image). Bemoving the R, G, B, RGB, H, S, V arrays will definately save a lot of memory and reduce paging overhead.

Regarding huge flat arrays vs structured data, I took that approach because sometimes, flat C styled code allows room for 'dirty' optimizations, normally not allowed by structured code. Also, I am of the impression that heap access would be faster than stack (structs vs classes). One thing I was not sure about was if an array of structures stays on the heap or the stack.

Thanks for the code sample. I'll make the above optimizations in my code and test performance against your approach.

Overall though, the AssignDataPointToCluster() optimization would far outshadow all others combined. Thanks again.

Khan

Author

Commented:
LOL

After changing the ComputeMean approach to what you suggested, a 500x500 image that used to take 1186 seconds now takes 8 seconds!!!

Going to go ahead with the rest of the optimizations just for laughs :).

Khan

Author

Commented:
ComputeMean is not used anymore and here is the updated AssignDataPointToCluster() function:

      private void AssignDataPointToCluster (int indexCluster, int indexDataPoint)
      {
         this._AssignDataPointToClusterIndexClusterOld   = this._DataPointCollection[indexDataPoint].ClusterIndex;

         if (this._AssignDataPointToClusterIndexClusterOld >= 0)
         {
            // Remove data point this._IndexTemp from old cluster array list
            this._AssignDataPointToClusterIndexTemp      = this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].BinarySearch(indexDataPoint);
            this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].RemoveAt(this._AssignDataPointToClusterIndexTemp);

            this._MeanOldSum[this._AssignDataPointToClusterIndexClusterOld].H   = this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].H;
            this._MeanOldSum[this._AssignDataPointToClusterIndexClusterOld].S   = this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].S;
            this._MeanOldSum[this._AssignDataPointToClusterIndexClusterOld].V   = this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].V;

            this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].H      -= this._DataPointCollection[indexDataPoint].H;
            this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].S      -= this._DataPointCollection[indexDataPoint].S;
            this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].V      -= this._DataPointCollection[indexDataPoint].V;
         }

         this._DataPointCollection[indexDataPoint].ClusterIndex   = indexCluster;
         this._ClusterIndexCollection[indexCluster]            = indexDataPoint;

         this._AssignDataPointToClusterIndexTemp   = this._ClusterIndexCollectionCollection[indexCluster].BinarySearch(indexDataPoint);
         if (this._AssignDataPointToClusterIndexTemp < 0)
         {
            this._ClusterIndexCollectionCollection[indexCluster].Insert(~this._AssignDataPointToClusterIndexTemp, indexDataPoint);

            this._MeanOldSum[indexCluster].H   = this._MeanSum[indexCluster].H;
            this._MeanOldSum[indexCluster].S   = this._MeanSum[indexCluster].S;
            this._MeanOldSum[indexCluster].V   = this._MeanSum[indexCluster].V;

            this._MeanSum[indexCluster].H      += this._DataPointCollection[indexDataPoint].H;
            this._MeanSum[indexCluster].S      += this._DataPointCollection[indexDataPoint].S;
            this._MeanSum[indexCluster].V      += this._DataPointCollection[indexDataPoint].V;
         }
      }

Author

Commented:
Sorry about that. I missed out an important step. Here is the correct code. Have I skipped anyhitng out?

      private void AssignDataPointToCluster (int indexCluster, int indexDataPoint)
      {
         this._AssignDataPointToClusterIndexClusterOld   = this._DataPointCollection[indexDataPoint].ClusterIndex;

         if (this._AssignDataPointToClusterIndexClusterOld >= 0)
         {
            // Remove data point this._IndexTemp from old cluster array list
            this._AssignDataPointToClusterIndexTemp      = this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].BinarySearch(indexDataPoint);
            this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].RemoveAt(this._AssignDataPointToClusterIndexTemp);

            // Assign Old mean
            this._MeanOldCollection[this._AssignDataPointToClusterIndexClusterOld].H   = this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].H;
            this._MeanOldCollection[this._AssignDataPointToClusterIndexClusterOld].S   = this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].S;
            this._MeanOldCollection[this._AssignDataPointToClusterIndexClusterOld].V   = this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].V;

            // Calculate new sum
            this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].H      -= this._DataPointCollection[indexDataPoint].H;
            this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].S      -= this._DataPointCollection[indexDataPoint].S;
            this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].V      -= this._DataPointCollection[indexDataPoint].V;

            // Calculate new mean
            this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].H   = this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].H / this._MeanSum.Length;
            this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].S   = this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].S / this._MeanSum.Length;
            this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].V   = this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].V / this._MeanSum.Length;
         }

         this._DataPointCollection[indexDataPoint].ClusterIndex   = indexCluster;
         this._ClusterIndexCollection[indexCluster]            = indexDataPoint;

         this._AssignDataPointToClusterIndexTemp   = this._ClusterIndexCollectionCollection[indexCluster].BinarySearch(indexDataPoint);
         if (this._AssignDataPointToClusterIndexTemp < 0)
         {
            this._ClusterIndexCollectionCollection[indexCluster].Insert(~this._AssignDataPointToClusterIndexTemp, indexDataPoint);

            // Assign Old mean
            this._MeanOldCollection[indexCluster].H   = this._MeanCollection[indexCluster].H;
            this._MeanOldCollection[indexCluster].S   = this._MeanCollection[indexCluster].S;
            this._MeanOldCollection[indexCluster].V   = this._MeanCollection[indexCluster].V;

            // Calculate new sum
            this._MeanSum[indexCluster].H      += this._DataPointCollection[indexDataPoint].H;
            this._MeanSum[indexCluster].S      += this._DataPointCollection[indexDataPoint].S;
            this._MeanSum[indexCluster].V      += this._DataPointCollection[indexDataPoint].V;

            // Calculate new mean
            this._MeanCollection[indexCluster].H   = this._MeanSum[indexCluster].H / this._MeanSum.Length;
            this._MeanCollection[indexCluster].S   = this._MeanSum[indexCluster].S / this._MeanSum.Length;
            this._MeanCollection[indexCluster].V   = this._MeanSum[indexCluster].V / this._MeanSum.Length;
         }
      }
Hashtables are faster than binary trees for insert and lookup. Internally, they're usually implemented as a growable array of "buckets" The hashtable computes a "hashcode" for the element you're inserting, and uses that as an index into the array. It puts the element in the bucket (the bucket is usually a short linked list so it can hold multiple entries). Then when you want to retrieve an element, it computes the hashcode again, and it only has to look through one bucket. If there are on average N buckets for N entries, the buckets are small, os it does only a few comparisons instead of log(n). Most hashtables (including the .NET one) support inserting a key _and_ a value. Hashcodes are computed based on the key, so you can look up the data even if you only know its key (typically a name or ID). This is why they're sometimes called "dictionaries".
http://en.wikipedia.org/wiki/Hashtable

An array of structures (or any other data) is allocated on the stack or the heap depending on how you allocate it, not on the structure itself. In .NET almost everything is allocated on the heap anyway. Essentially every time you call "new", you get heap memory, whether it's a struct or a class. _Locally_ declared simple types go on the stack, as do locally declared structs. In .NET, I believe arrays are always on the heap.  Traditionally stack variables are accessed faster than heap variables, but these day's it's almost the same. The important difference is that _creating_ heap objects is more expensive.

Question - what's the application of this? Are you sorting images by color for some sort of art project?

Author

Commented:
Regarding Hashtables, I read the article on Wikipedia which was quite helpful. I'll give it a try and let you know if there is a noticeable increase in performance.

Also, I read up on Arrays of Structures and they do get declared as value types so are faster than classes.

I'm writing this code for an image manipulation software. I'm not at liberty to give details but overall, it's an ACDSee-like tool with specialized features for a specific industry.

Author

Commented:
I made another mistake in the AssignDataPointToCluster() function. I'm pasting the new tested code below for anyone who might want it.

Author

Commented:
public static void main ()
{
   bool                           result            = false;
   long                           ticks            = 0;
   string                           filename         = "";
   double                           seconds            = 0.0D;
   Clustering.Library.Image            image            = null;
   Clustering.Library.DominantColor      dominantColor      = null;

   filename   = @"C:\Temp\Pics\SomeImage.gif";

   image      = new Clustering.Library.Image();
   result      = image.Open(filename, out message);

   if (result)
   {
      dominantColor   = new Clustering.Library.DominantColor();
      ticks         = System.DateTime.Now.Ticks;
      dominantColor.Compute(image);
      seconds         = System.Math.Round(((double) (System.DateTime.Now.Ticks - ticks)) / 10000000D, 2);
      System.Windows.Forms.MessageBox.Show("Operation took: " + seconds.ToString() + " second(s)");
   }
}

namespace Clustering.Library
{
   public class Image: System.IDisposable
   {
      //****************************************************************************************************/
      // Constants
      //****************************************************************************************************/

      //****************************************************************************************************/
      // Enumerations
      //****************************************************************************************************/

      //****************************************************************************************************/
      // Structures
      //****************************************************************************************************/

      //****************************************************************************************************/
      // Members
      //****************************************************************************************************/

      private      bool         _Disposed      = false;

      private      int            _Width         = 0;
      private      int            _Height         = 0;
      private      int            _BitsPerPixel   = 0;
      private      int            _BytesPerPixel   = 0;
      private      int            _SizeInBytes   = 0;
      private      int            _SizeInPixels   = 0;
      private      byte   []      _R            = null;
      private      byte   []      _G            = null;
      private      byte   []      _B            = null;
      private      byte   []      _RGB         = null;
      private      float   []      _H            = null;
      private      float   []      _S            = null;
      private      float   []      _V            = null;
      private      float   []      _HSV         = null;

      //****************************************************************************************************/
      // Constructors / Initialization / Destructors
      //****************************************************************************************************/

      public Image ()
      {
         this.Initialize();
      }

      public void Initialize ()
      {
         this.Width         = 0;
         this.Height         = 0;
         this.BitsPerPixel   = 0;
         this.BytesPerPixel   = 0;
         this.SizeInBytes   = 0;
         this.SizeInPixels   = 0;

         this._R      = null;
         this._G      = null;
         this._B      = null;
         this._RGB   = null;
         this._H      = null;
         this._S      = null;
         this._V      = null;
         this._HSV   = null;
      }

      ~Image ()
      {
         // Do not re-create Dispose clean-up code here.
         //   Calling Dispose(false) is optimal in terms of readability and maintainability.
         this.Dispose(false);
      }

      //****************************************************************************************************/
      // Proterties
      //****************************************************************************************************/

      public int Width
      {
         get   {return(this._Width);}
         set   {this._Width = value;}
      }

      public int Height
      {
         get   {return(this._Height);}
         set   {this._Height = value;}
      }

      public int SizeInBytes
      {
         get   {return(this._SizeInBytes);}
         set   {this._SizeInBytes = value;}
      }

      public int SizeInPixels
      {
         get   {return(this._SizeInPixels);}
         set   {this._SizeInPixels = value;}
      }

      public int BytesPerPixel
      {
         get   {return(this._BytesPerPixel);}
         set   {this._BytesPerPixel = value;}
      }

      public int BitsPerPixel
      {
         get   {return(this._BitsPerPixel);}
         set   {this._BitsPerPixel = value;}
      }

      public byte [] R
      {
         get   {return(this._R);}
      }

      public byte [] G
      {
         get   {return(this._G);}
      }

      public byte [] B
      {
         get   {return(this._B);}
      }

      public byte [] RGB
      {
         get   {return(this._RGB);}
      }

      public float [] H
      {
         get   {return(this._H);}
      }

      public float [] S
      {
         get   {return(this._S);}
      }

      public float [] V
      {
         get   {return(this._V);}
      }

      public float [] HSV
      {
         get   {return(this._HSV);}
      }

      //****************************************************************************************************/
      // Indexers
      //****************************************************************************************************/

      //****************************************************************************************************/
      // Functions
      //****************************************************************************************************/

      public bool Open (string filename, out string message)
      {
         float               r, g, b;
         byte   []            buffer   = null;
         System.Drawing.Color   color;
         System.Drawing.Image   image   = null;
         System.Drawing.Bitmap   bitmap   = null;

         message      = "";

         try
         {
            image   = System.Drawing.Image.FromFile(filename);

            this.BytesPerPixel   = 3;
            this.BitsPerPixel   = this.BytesPerPixel * 8;
            this.Width         = image.Width;
            this.Height         = image.Height;
            this.SizeInPixels   = this.Width * this.Height;
            this.SizeInBytes   = this.Width * this.Height * this.BytesPerPixel;

            try
            {
               bitmap   = new System.Drawing.Bitmap(image);

               try
               {
                  buffer      = new byte [this.SizeInBytes];
                  for (int y=0, i=0; y<this.Height; y++)
                  {
                     for (int x=0; x<this.Width; x++, i+=this.BytesPerPixel)
                     {
                        color   = bitmap.GetPixel(x, y);

                        buffer[i+0]   = color.R;
                        buffer[i+1]   = color.G;
                        buffer[i+2]   = color.B;
                     }
                  }

                  //System.Runtime.InteropServices.Marshal.Copy(bitmapData.Scan0, buffer, 0, this.SizeInBytes);

                  // Asssign RGB, R, G, B
                  this._RGB   = buffer;
                  this._R      = new byte [this.SizeInPixels];
                  this._G      = new byte [this.SizeInPixels];
                  this._B      = new byte [this.SizeInPixels];
                  for (int i=0, j=0; i<this.SizeInPixels; i++, j+=3)
                  {
                     this._R[i]   = buffer[j+0];
                     this._G[i]   = buffer[j+1];
                     this._B[i]   = buffer[j+2];
                  }
                  // Asssign HSV, H, S, V
                  this._H      = new float [this.SizeInPixels];
                  this._S      = new float [this.SizeInPixels];
                  this._V      = new float [this.SizeInPixels];
                  this._HSV   = new float [this.SizeInBytes];
                  for (int i=0, j=0; i<this.SizeInPixels; i++, j+=3)
                  {
                     r   = this._R[i] / 255.0F;
                     g   = this._G[i] / 255.0F;
                     b   = this._B[i] / 255.0F;
                     this.RgbToHsv(r, g, b, out this._H[i], out this._S[i], out this._V[i]);
                     this.HSV[j+0]   = this._H[i];
                     this.HSV[j+1]   = this._S[i];
                     this.HSV[j+2]   = this._V[i];
                  }

                  this._R      = null;
                  this._G      = null;
                  this._B      = null;
                  this._RGB   = null;
                  this._HSV   = null;

                  System.GC.Collect();
               }
               catch (System.Exception exception)
               {
                  message
                     +=   System.Environment.NewLine
                     +   "   - "
                     +   exception.Message;
               }

               bitmap.Dispose();
            }
            catch (System.Exception exception)
            {
               message
                  +=   System.Environment.NewLine
                  +   "   - "
                  +   exception.Message;
            }

            image.Dispose();
         }
         catch (System.Exception exception)
         {
            message
               +=   System.Environment.NewLine
               +   "   - "
               +   exception.Message;
         }

         if (message.Length == 0)
         {
            return (true);
         }
         else
         {
            message
               = "The following error(s) occured:"
               + message
               ;

            this.Close();

            return (false);
         }
      }

      /// <summary>
      /// This function is included only for reference. The copy memory methos is extremely fast
      /// but does not yet work properly
      /// </summary>
      /// <param name="filename"></param>
      /// <param name="message"></param>
      /// <returns></returns>
      public bool OpenFast (string filename, out string message)
      {
         float               r, g, b;
         byte   []            buffer   = null;
         System.Drawing.Image   image   = null;
         System.Drawing.Bitmap   bitmap   = null;

         message      = "";

         try
         {
            image   = System.Drawing.Image.FromFile(filename);

            this.BytesPerPixel   = 3;
            this.BitsPerPixel   = this.BytesPerPixel * 8;
            this.Width         = image.Width;
            this.Height         = image.Height;
            this.SizeInPixels   = this.Width * this.Height;
            this.SizeInBytes   = this.Width * this.Height * this.BytesPerPixel;

            try
            {
               bitmap   = new System.Drawing.Bitmap(image);

               try
               {
                  System.Drawing.Imaging.BitmapData   bitmapData   = bitmap.LockBits
                     (
                     new System.Drawing.Rectangle(0, 0, bitmap.Width, bitmap.Height),
                     System.Drawing.Imaging.ImageLockMode.ReadWrite,
                     System.Drawing.Imaging.PixelFormat.Format24bppRgb
                     );

                  try
                  {
                     buffer      = new byte [this.SizeInBytes];

                     System.Runtime.InteropServices.Marshal.Copy(bitmapData.Scan0, buffer, 0, this.SizeInBytes);

                     // Asssign RGB, R, G, B
                     this._RGB   = buffer;
                     this._R      = new byte [this.SizeInPixels];
                     this._G      = new byte [this.SizeInPixels];
                     this._B      = new byte [this.SizeInPixels];
                     for (int i=0, j=0; i<this.SizeInPixels; i++, j+=3)
                     {
                        this._R[i]   = buffer[j+0];
                        this._G[i]   = buffer[j+1];
                        this._B[i]   = buffer[j+2];
                     }
                     // Asssign HSV, H, S, V
                     this._H      = new float [this.SizeInPixels];
                     this._S      = new float [this.SizeInPixels];
                     this._V      = new float [this.SizeInPixels];
                     this._HSV   = new float [this.SizeInBytes];
                     for (int i=0, j=0; i<this.SizeInPixels; i++, j+=3)
                     {
                        r   = this._R[i] / 255.0F;
                        g   = this._G[i] / 255.0F;
                        b   = this._B[i] / 255.0F;
                        this.RgbToHsv(r, g, b, out this._H[i], out this._S[i], out this._V[i]);
                        this.HSV[j+0]   = this._H[i];
                        this.HSV[j+1]   = this._S[i];
                        this.HSV[j+2]   = this._V[i];
                     }
                  }
                  catch (System.Exception exception)
                  {
                     message
                        +=   System.Environment.NewLine
                        +   "   - "
                        +   exception.Message;
                  }

                  bitmap.UnlockBits(bitmapData);
               }
               catch (System.Exception exception)
               {
                  message
                     +=   System.Environment.NewLine
                     +   "   - "
                     +   exception.Message;
               }

               bitmap.Dispose();
            }
            catch (System.Exception exception)
            {
               message
                  +=   System.Environment.NewLine
                  +   "   - "
                  +   exception.Message;
            }

            image.Dispose();
         }
         catch (System.Exception exception)
         {
            message
               +=   System.Environment.NewLine
               +   "   - "
               +   exception.Message;
         }

         if (message.Length == 0)
         {
            return (true);
         }
         else
         {
            message
               = "The following error(s) occured:"
               + message
               ;

            this.Close();

            return (false);
         }
      }

      public void Close ()
      {
         this.Initialize();
      }

      public void RgbToHsv (float r, float g, float b, out float h, out float s, out float v)
      {
         float   min      = 0;
         float   max      = 0;
         float   delta   = 0;

         if (r < g)
         {
            if (r < b)
               min   = r;
            else
               min   = b;
         }
         else
         {
            if (g < b)
               min   = g;
            else
               min   = b;
         }

         if (r > g)
         {
            if (r > b)
               max   = r;
            else
               max   = b;
         }
         else
         {
            if (g > b)
               max   = g;
            else
               max   = b;
         }

         delta   = max - min;

         if (max == 0)
         {
            h   = -1.0F;
            s   = -1.0F;
            v   = 0.0F;
         }
         else
         {
            if (min == max)
            {
               h   = -1.0F;
               s   = 0.0F;
               v   = max;
            }
            else
            {
               if (max == r)
               {
                  if (g < b)
                  {
                     h   = 60 * ((g - b) / delta) + 360.0F;
                  }
                  else
                  {
                     h   = 60 * ((g - b) / delta) + 0.0F;
                  }
               }
               else if (max == g)
               {
                  h   = 60 * ((b - r) / delta) + 120.0F;
               }
               else if (max == b)
               {
                  h   = 60 * ((r - g) / delta) + 240.0F;
               }
               else
               {
                  h   = -1.0F;
               }
               s   = delta / max;
               v   = max;
            }
         }
      }

      //****************************************************************************************************/
      // Interface Implementation: System.IDisposable
      //****************************************************************************************************/

      // Implement System.IDisposable.
      //   Do not make this method virtual.
      //   A derived class should not be able to override this method.
      public void Dispose ()
      {
         this.Dispose(true);
         // This object will be cleaned up by the Dispose method.
         //   Take this object off the finalization queue and prevent finalization code for this object from executing a second time.
         System.GC.SuppressFinalize(this);
      }

      // Dispose (bool this._Disposing) executes in two distinct scenarios.
      //   If disposing equals true, the method has been called directly or indirectly by a user's code. Managed and unmanaged resources can be disposed.
      //   If disposing equals false, the method has been called by the runtime from inside the finalizer and you should not reference other objects.
      //   Only unmanaged resources can be disposed.
      private void Dispose (bool disposing)
      {
         if (!this._Disposed)
         {
            // If disposing equals true, dispose all managed and unmanaged resources.
            if (disposing)
            {
               // Dispose managed resources here.
               this.Close();
            }

            // Call the appropriate methods to clean up unmanaged resources here.
            //   If disposing is false, only the following code is executed.
            //   Dispose unmanaged resources here.
         }
         this._Disposed   = true;        
      }

   }
}

namespace Clustering.Library
{
   //****************************************************************************************************/
   // Structures
   //****************************************************************************************************/

   public struct DataPoint
   {
      public      double      H;
      public      double      S;
      public      double      V;
      public      int         ClusterIndex;

      public DataPoint (double h, double s, double v)
      {
         this.ClusterIndex   = -1;

         this.H            = h;
         this.S            = s;
         this.V            = v;
      }

      public void Initialize ()
      {
         this.ClusterIndex   = -1;

         this.H            = 0D;
         this.S            = 0D;
         this.V            = 0D;
      }
   }

   public class DominantColor: System.IDisposable
   {
      //****************************************************************************************************/
      // Constants
      //****************************************************************************************************/

      public   const   int         CLUSTER_COUNT         = 20;
      public   const   double      MEANS_CUTOFF_TO_END      = 0.001D;

      //****************************************************************************************************/
      // Members
      //****************************************************************************************************/

      private      bool                           _Disposed      = false;

      // The main array of data points that will hold the image data
      private      Clustering.Library.DataPoint   []      _DataPointCollection;
      // Simple int array to hold the cluster index for each data point
      //   Length will be the same as _DataPointCollection
      private      int                        []      _ClusterIndexCollection;
      // An array of ArrayList objects. The array will be of length CLUSTER_COUNT and
      //   will hold one ArrayList for each cluster. Each ArrayList will store only the
      //   data point index from _DataPointCollection. I've used this approach since it
      //   saves memory and the BinarySearch feature in ArrayList objects is lightning fast.
      // This array is not neccessary but I've included it since this aproach increases
      //   performance dramatically
      private      System.Collections.ArrayList   []      _ClusterIndexCollectionCollection;
      // Simple data point array to hold the mean of each cluster
      //   Length will be the same as CLUSTER_COUNT
      private      Clustering.Library.DataPoint   []      _MeanCollection;
      // Simple data point array to hold the sum of each cluster
      //   Length will be the same as CLUSTER_COUNT
      private      Clustering.Library.DataPoint   []      _MeanSum;
      // Simple data point array to hold the old mean of each cluster
      //   Length will be the same as CLUSTER_COUNT
      private      Clustering.Library.DataPoint   []      _MeanOldCollection;
      // Simple data point array to hold the old sum of each cluster
      //   Length will be the same as CLUSTER_COUNT
      private      Clustering.Library.DataPoint   []      _MeanOldSum;

      public DominantColor ()
      {
         this.Initialize();
      }

      public void Initialize ()
      {
         this._DataPointCollection            = null;
         this._ClusterIndexCollection         = null;
         this._ClusterIndexCollectionCollection   = null;
         this._MeanSum                     = null;
         this._MeanCollection               = null;
         this._MeanOldSum                  = null;
         this._MeanOldCollection               = null;
      }

      public void Initialize (int rowCount)
      {
         this.Initialize();

         this._DataPointCollection      = new Clustering.Library.DataPoint[rowCount];
         for (int i=0; i<this._DataPointCollection.Length; i++)
         {
            this._DataPointCollection[i].Initialize();
         }

         this._ClusterIndexCollection   = new int [rowCount];
         for (int i=0; i<this._ClusterIndexCollection.Length; i++)
         {
            this._ClusterIndexCollection[i]   = -1;
         }

         this._ClusterIndexCollectionCollection   = new System.Collections.ArrayList [CLUSTER_COUNT];
         for (int i=0; i<this._ClusterIndexCollectionCollection.Length; i++)
         {
            this._ClusterIndexCollectionCollection[i]   = new System.Collections.ArrayList();
         }

         this._MeanSum         = new Clustering.Library.DataPoint [CLUSTER_COUNT];
         for (int i=0; i<this._MeanSum.Length; i++)
         {
            this._MeanSum[i].H   = 0D;
            this._MeanSum[i].S   = 0D;
            this._MeanSum[i].V   = 0D;
         }

         this._MeanCollection   = new Clustering.Library.DataPoint [CLUSTER_COUNT];
         for (int i=0; i<this._MeanCollection.Length; i++)
         {
            this._MeanCollection[i].H   = 0D;
            this._MeanCollection[i].S   = 0D;
            this._MeanCollection[i].V   = 0D;
         }

         this._MeanOldSum      = new Clustering.Library.DataPoint [CLUSTER_COUNT];
         for (int i=0; i<this._MeanOldSum.Length; i++)
         {
            this._MeanOldSum[i].H   = 0D;
            this._MeanOldSum[i].S   = 0D;
            this._MeanOldSum[i].V   = 0D;
         }

         this._MeanOldCollection   = new Clustering.Library.DataPoint [CLUSTER_COUNT];
         for (int i=0; i<this._MeanOldCollection.Length; i++)
         {
            this._MeanOldCollection[i].H   = 0D;
            this._MeanOldCollection[i].S   = 0D;
            this._MeanOldCollection[i].V   = 0D;
         }
      }

      ~DominantColor ()
      {
         // Do not re-create Dispose clean-up code here.
         //   Calling Dispose(false) is optimal in terms of readability and maintainability.
         this.Dispose(false);
      }

      //****************************************************************************************************/
      // Properties
      //****************************************************************************************************/

      public Clustering.Library.DataPoint [] DataPointCollection
      {
         get   {return (this._DataPointCollection);}
      }

      public int [] ClusterIndexCollection
      {
         get   {return (this._ClusterIndexCollection);}
      }

      public System.Collections.ArrayList [] ClusterIndexCollectionCollection
      {
         get   {return (this._ClusterIndexCollectionCollection);}
      }

      public Clustering.Library.DataPoint [] MeanCollection
      {
         get   {return (this._MeanCollection);}
      }

      public Clustering.Library.DataPoint [] MeanOldCollection
      {
         get   {return (this._MeanOldCollection);}
      }

      //****************************************************************************************************/
      // Functions
      //****************************************************************************************************/

      public void Compute (Clustering.Library.Image image)
      {
         int            indexDataPoint      = 0;
         double         distanceCurrent      = 0.0D;
         double         distanceClosest      = 0.0D;
         int            clusterIndex      = -1;
         int            displacement      = 0;
         int            clusterIndexTemp   = 0;
         System.Random   random            = null;

         // Initialize
         this.Initialize(image.SizeInPixels);
         //   Data
         for (int i=0; i<image.SizeInPixels; i++)
         {
            this._DataPointCollection[i].H   = image.H[i];
            this._DataPointCollection[i].S   = image.S[i];
            this._DataPointCollection[i].V   = image.V[i];
         }

         // Create initial clusters by assigning one random row to each
         random   = new System.Random();
         for (int i=0; i<CLUSTER_COUNT; i++)
         {
            indexDataPoint      = random.Next(0, this._DataPointCollection.Length);
            while (this._DataPointCollection[indexDataPoint].ClusterIndex >= 0)
            {
               indexDataPoint      = random.Next(0, this._DataPointCollection.Length);
            }

            this.AssignDataPointToCluster(i, indexDataPoint);
            //this.ComputeClusterMean(i);
         }

         // Assign all unassigned data points to the relevant cluster
         for (int i=0; i<this._DataPointCollection.Length; i++)
         {
            // Filter out only unassigned data points
            switch (this._DataPointCollection[i].ClusterIndex)
            {
               case -1:
               {
                  clusterIndex   = -1;
                  for (int j=0; j<CLUSTER_COUNT; j++)
                  {
                     switch (j)
                     {
                        case 0:
                        {
                           distanceClosest   = this.EuclideanDistance(ref this._DataPointCollection[i], ref this._MeanCollection[j]);

                           clusterIndex   = j;

                           break;
                        }
                        default:
                        {
                           distanceCurrent   = this.EuclideanDistance(ref this._DataPointCollection[i], ref this._MeanCollection[j]);

                           if (distanceCurrent < distanceClosest)
                           {
                              distanceClosest   = distanceCurrent;

                              clusterIndex   = j;

                              break;
                           }

                           break;
                        }
                     }
                  }

                  // No validation checks needed since assigned data points have already been filtered out
                  //   and clusterIndex will always hold a valid value
                  displacement++;
                  this.AssignDataPointToCluster(clusterIndex, i);
                  //this.ComputeClusterMean(clusterIndex);

                  break;
               }
            }
         }

         // All data points have already been assigned to some cluster
         //   This loop re-assigns each one
         while (true)
         {
            displacement   = 0;
            for (int i=0; i<this._DataPointCollection.Length; i++)
            {
               clusterIndex   = -1;
               for (int j=0; j<CLUSTER_COUNT; j++)
               {
                  switch (j)
                  {
                     case 0:
                     {
                        distanceClosest   = this.EuclideanDistance(ref this._DataPointCollection[i], ref this._MeanCollection[j]);

                        clusterIndex   = j;

                        break;
                     }
                     default:
                     {
                        distanceCurrent   = this.EuclideanDistance(ref this._DataPointCollection[i], ref this._MeanCollection[j]);

                        if (distanceCurrent < distanceClosest)
                        {
                           distanceClosest   = distanceCurrent;

                           clusterIndex   = j;

                           break;
                        }

                        break;
                     }
                  }
               }

               // Avoid redundant reassigning to same cluster
               if (this._DataPointCollection[i].ClusterIndex != clusterIndex)
               {
                  // The data point was already assigned to another cluster
                  //   Due to reassignment, the From and To cluster Mean values
                  //   will be affected so we need to recalculate new Mean values
                  //   for both
                  displacement++;
                  clusterIndexTemp   = this._DataPointCollection[i].ClusterIndex;
                  this.AssignDataPointToCluster(clusterIndex, i);
                  //this.ComputeClusterMean(clusterIndex);
                  //this.ComputeClusterMean(clusterIndexTemp);
               }
            }

            // I'm probably wrong but I figured that zero displacement could act as a potential
            //   terminating condition. Not sure what to do here
            if ((clusterIndex == -1) || (displacement == 0))
            {
               break;
            }
         }
      }

      // These variables are exclusive to the AssignDataPointToCluster function and should not be accessed elsewhere
      //   Declared at class level for performance.
      private      int      _AssignDataPointToClusterIndexTemp         = 0;
      private      int      _AssignDataPointToClusterIndexClusterOld   = 0;
      private void AssignDataPointToCluster (int indexCluster, int indexDataPoint)
      {
         this._AssignDataPointToClusterIndexClusterOld   = this._DataPointCollection[indexDataPoint].ClusterIndex;

         if (this._AssignDataPointToClusterIndexClusterOld >= 0)
         {
            // Remove data point this._IndexTemp from old cluster array list
            this._AssignDataPointToClusterIndexTemp      = this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].BinarySearch(indexDataPoint);
            this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].RemoveAt(this._AssignDataPointToClusterIndexTemp);

            // Compute new Mean value after removal
            this._MeanOldCollection[this._AssignDataPointToClusterIndexClusterOld].H   = this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].H;
            this._MeanOldCollection[this._AssignDataPointToClusterIndexClusterOld].S   = this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].S;
            this._MeanOldCollection[this._AssignDataPointToClusterIndexClusterOld].V   = this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].V;

            this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].H      -= this._DataPointCollection[indexDataPoint].H;
            this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].S      -= this._DataPointCollection[indexDataPoint].S;
            this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].V      -= this._DataPointCollection[indexDataPoint].V;

            this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].H   = this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].H / this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].Count;
            this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].S   = this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].S / this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].Count;
            this._MeanCollection[this._AssignDataPointToClusterIndexClusterOld].V   = this._MeanSum[this._AssignDataPointToClusterIndexClusterOld].V / this._ClusterIndexCollectionCollection[this._AssignDataPointToClusterIndexClusterOld].Count;
         }

         this._DataPointCollection[indexDataPoint].ClusterIndex   = indexCluster;
         this._ClusterIndexCollection[indexCluster]            = indexDataPoint;

         this._AssignDataPointToClusterIndexTemp   = this._ClusterIndexCollectionCollection[indexCluster].BinarySearch(indexDataPoint);
         if (this._AssignDataPointToClusterIndexTemp < 0)
         {
            this._ClusterIndexCollectionCollection[indexCluster].Insert(~this._AssignDataPointToClusterIndexTemp, indexDataPoint);

            // Compute new Mean value after insertion
            this._MeanOldCollection[indexCluster].H   = this._MeanCollection[indexCluster].H;
            this._MeanOldCollection[indexCluster].S   = this._MeanCollection[indexCluster].S;
            this._MeanOldCollection[indexCluster].V   = this._MeanCollection[indexCluster].V;

            this._MeanSum[indexCluster].H      += this._DataPointCollection[indexDataPoint].H;
            this._MeanSum[indexCluster].S      += this._DataPointCollection[indexDataPoint].S;
            this._MeanSum[indexCluster].V      += this._DataPointCollection[indexDataPoint].V;

            this._MeanCollection[indexCluster].H   = this._MeanSum[indexCluster].H / this._ClusterIndexCollectionCollection[indexCluster].Count;
            this._MeanCollection[indexCluster].S   = this._MeanSum[indexCluster].S / this._ClusterIndexCollectionCollection[indexCluster].Count;
            this._MeanCollection[indexCluster].V   = this._MeanSum[indexCluster].V / this._ClusterIndexCollectionCollection[indexCluster].Count;
         }
      }

      // These variables are exclusive to the EuclideanDistance function and should not be accessed elsewhere
      //   Declared at class level for performance.
      private      double      _EuclideanDistanceResult      = 0.0D;
      // Passing the parameters by reference is good to avoid unnecessary copying since we are using structs
      private double EuclideanDistance (ref Clustering.Library.DataPoint dataPoint1, ref Clustering.Library.DataPoint dataPoint2)
      {
         this._EuclideanDistanceResult   = 0.0D;

         this._EuclideanDistanceResult
            = (dataPoint1.H - dataPoint2.H) * (dataPoint1.H - dataPoint2.H)
            + (dataPoint1.S - dataPoint2.S) * (dataPoint1.S - dataPoint2.S)
            + (dataPoint1.V - dataPoint2.V) * (dataPoint1.V - dataPoint2.V)
            ;

         // The actual distance should be passed through Sqrt but is removed for performance.
         //return (System.Math.Sqrt(this._EuclideanDistanceResult));
         return (this._EuclideanDistanceResult);
      }

      //****************************************************************************************************/
      // Interface Implementation: System.IDisposable
      //****************************************************************************************************/

      // Implement System.IDisposable.
      //   Do not make this method virtual.
      //   A derived class should not be able to override this method.
      public void Dispose ()
      {
         this.Dispose(true);
         // This object will be cleaned up by the Dispose method.
         //   Take this object off the finalization queue and prevent finalization code for this object from executing a second time.
         System.GC.SuppressFinalize(this);
      }

      // Dispose (bool this._Disposing) executes in two distinct scenarios.
      //   If disposing equals true, the method has been called directly or indirectly by a user's code. Managed and unmanaged resources can be disposed.
      //   If disposing equals false, the method has been called by the runtime from inside the finalizer and you should not reference other objects.
      //   Only unmanaged resources can be disposed.
      private void Dispose (bool disposing)
      {
         if (!this._Disposed)
         {
            // If disposing equals true, dispose all managed and unmanaged resources.
            if (disposing)
            {
               // Dispose managed resources here.
               this.Initialize();
            }

            // Call the appropriate methods to clean up unmanaged resources here.
            //   If disposing is false, only the following code is executed.
            //   Dispose unmanaged resources here.
         }
         this._Disposed   = true;        
      }

   }
}
So I could use this code for a project towards certain data points?

Gain unlimited access to on-demand training courses with an Experts Exchange subscription.

Get Access
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Empower Your Career
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE

Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Unlock the solution to this question.
Join our community and discover your potential

Experts Exchange is the only place where you can interact directly with leading experts in the technology field. Become a member today and access the collective knowledge of thousands of technology experts.

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.